Re: Java Diff Funtion-

[Paul Eggert]

> From: "Burr, Rod L" <address@hidden>
> Date: Wed, 2 Oct 2002 20:25:45 -0400

> However, from my perception, the algorithm, instead, sets off in a
> 'search pattern' to locate common records that have already been
> located

The initial prepass uses hashing to identify unique lines, which must
be different.  This is an optimization, though.  Even without this
part of the prepass, the algorithm would work correctly.  It would
just be slower, since it would need to look at the unique lines as
well as the non-unique lines.

> and I have not yet identified how the 'common records'
> are actually processed, once they've been identified.

That is the core of the algorithm, and it's what is discussed in
Myers's paper.

You might try looking at the Handbook of Theoretical Computer Science:
it may help you to understand things better.  That book should be in
your company's library.  I'll add the following reference to the GNU
diff manual.

  This and related algorithms are surveyed by Alfred V. Aho in section
  6.3 of ``Algorithms for Finding Patterns in Strings'', Handbook
  of Theoretical Computer Science (Jan Van Leeuwen, ed.), Vol. A,
  Algorithms and Complexity, Elsevier/MIT Press, 1990, pp. 255--300.


> This message is in MIME format. Since your mail reader does not
> understand this format, some or all of this message may not be
> legible.

Please configure your mail client to send plain text email as plain
text.  Other formats slow me down.  Thanks.