Algorithm for "diff"ing files/strings 
Author Message
 Algorithm for "diff"ing files/strings

Both the GNU "diff" and "fhist" program reference algorithms for identifying
differences between files/strings.  My efforts to track down the algorithms
have failed - the works are no longer in print and the publisher doesn't
have an electronic copy.  Does someone know where I might find one or more
of:

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

Many thanks.

Chris.



Wed, 06 Aug 2003 21:21:45 GMT  
 Algorithm for "diff"ing files/strings
Quote:

> Both the GNU "diff" and "fhist" program reference algorithms for identifying
> differences between files/strings.  My efforts to track down the algorithms
> have failed - the works are no longer in print and the publisher doesn't
> have an electronic copy.  Does someone know where I might find one or more
> of:

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

> Many thanks.

> Chris.

Try a local university.  Before making the trip, go to their site and
search the catalog.

E Levac



Wed, 06 Aug 2003 23:21:29 GMT  
 Algorithm for "diff"ing files/strings

Quote:
> Both the GNU "diff" and "fhist" program reference algorithms for
identifying
> differences between files/strings.  My efforts to track down the
algorithms
> have failed - the works are no longer in print and the publisher doesn't
> have an electronic copy.  Does someone know where I might find one or more
> of:

Presumably the source code, whicj implememts the algorithms you are
interested in is available as part of GNU?

Quote:

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

These are not the correct newsgroups for this sort of thing, but "A software
tool sampler", Miller 1987, ISBN 0-13-821984-2 has algoroithms and C code
for a diff-like program which is used in the book to form part of a
roll-your own version control system.

NeilB



Wed, 06 Aug 2003 23:23:29 GMT  
 Algorithm for "diff"ing files/strings

Quote:
> Presumably the source code, whicj implememts the algorithms you are
> interested in is available as part of GNU?

Sure but it represents a specific implementation of the algorithm.  I was
interested in the original work for the description of the algorithm.

Quote:
> These are not the correct newsgroups for this sort of thing, but "A
software
> tool sampler", Miller 1987, ISBN 0-13-821984-2 has algoroithms and C code
> for a diff-like program which is used in the book to form part of a
> roll-your own version control system.

Shame.  Doesn't show up on amazon.co.uk

Thanks.

Chris.



Thu, 07 Aug 2003 06:13:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Error "free"-ing "malloc"-ed memory

2. "watch"ing a string with vc.NET

3. "cast"ing of char *

4. "create"ing a control derived from ccombobox

5. Comments on "Algorithm in C" or "Algorithm in C++"

6. C_"permutations algorithm"

7. "Until" Algorithm

8. Algorithm for "bit copy" function

9. Wanted: "tick" algorithm for graph axis

10. "Best fit" algorithm (help)

11. source code in "Algorithms in C"

12. Looking for binary "diff" and binary "diffupdt / patch"

 

 
Powered by phpBB® Forum Software