Re: Diff algorithms

Article View: gnu.misc.discuss

Article #73866

#73866

From: Scott Schwartz
Date: Thu, 18 Jul 1991 03:42

13 lines
1409 bytes

oz@ursa.ccs.yorku.ca (Ozan Yigit) writes:
   I think so too. The "GNU diff algorithm" is discussed in great detail
   [including source] in "A Software Tools Sampler"[2], and in an SP&E[3]
   article.

The cites you give are for an old (quadratic space) version of the
algorithm.  As the gnu code says in a comment, it uses: ``"An O(ND)
Difference Algorithm and its Variations", Eugene Myers, Algorithmica
Vol. 1 No. 2, 1986, p 251.'', which runs in linear space.  (There are
a number of other variants with interesting properties, but Gene's
version is pretty much the most practical.)  Anyway, this stuff isn't
patented, so don't worry.

Technical Details

Message-ID: <0vaH89hf1@cs.psu.edu>

Path: arc1-ca.pugleaf.net!gmdzi!unido!mcsun!uunet!wupost!psuvax1!news

References: <1991Jul11.024142.21012@hal.com> <1991Jul11.194739.20741@cs.utk.edu> <OZ.91Jul15171112@ursa.ccs.yorku.ca>

Show Full Headers

Complete Article Headers

X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 1025b4,7a79e28e4376aade
X-Google-Attributes: gid1025b4,public
X-Google-ArrivalTime: 1991-07-17 22:44:30 PST
Path: arc1-ca.pugleaf.net!gmdzi!unido!mcsun!uunet!wupost!psuvax1!news
From: schwartz@roke.cs.psu.edu (Scott Schwartz)
Newsgroups: gnu.misc.discuss
Subject: Re: Diff algorithms
Message-ID: <0vaH89hf1@cs.psu.edu>
Date: 18 Jul 91 03:42:31 GMT
References: <1991Jul11.024142.21012@hal.com> <1991Jul11.194739.20741@cs.utk.edu>
 <OZ.91Jul15171112@ursa.ccs.yorku.ca>
Sender: news@cs.psu.edu (Usenet)
Followup-To: gnu.misc.discuss
Organization: penn state university, computer science
Lines: 13
In-Reply-To: oz@ursa.ccs.yorku.ca's message of 15 Jul 91 22: 11:12 GMT
Nntp-Posting-Host: roke.cs.psu.edu

Reply to Parent Message