[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.