[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: large file support in diff utils

From: Paul Eggert
Subject: Re: large file support in diff utils
Date: Tue, 12 Apr 2005 00:45:42 -0700
User-agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.4 (gnu/linux)

Chuck Swiger <address@hidden> writes:

> Paul Eggert wrote:
>> Chuck Swiger <address@hidden> writes:
>>> I mention this because I'd be curious to know what the memory and
>>> running time (big-O) of diff is.
>> That's discussed in the references, at least in theory.
> It's not in the manpage, and I didn't see anything in the info pages, either.
> Can you generalize off-hand?

Here's a quote from doc/diffutils.texi:

The basic algorithm is described
by Eugene W. Myers in ``An O(ND) Difference Algorithm and its Variations'',
@cite{Algorithmica} Vol.@: 1 No.@: 2, 1986, pp.@: 251--266; and in ``A File
Comparison Program'', Webb Miller and Eugene W. Myers,
@cite{Software---Practice and Experience} Vol.@: 15 No.@: 11, 1985,
pp.@: 1025--1040.
The algorithm was independently discovered as described by E. Ukkonen in
``Algorithms for Approximate String Matching'',
@cite{Information and Control} Vol.@: 64, 1985, pp.@: 100--118.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]