3 ms·
All string diff algorithms in alignment derive from previous innovations on raw strings. SW is a derivative of NW, which itself (although the paper does not a
by dekhn 10y ago
All string diff algorithms in alignment derive from previous innovations on raw strings. SW is a derivative of NW, which itself (although the paper does not admit it) derives from the work done on edit distance in the mid 60s). It's actually interesting that this algorithm was rediscovered independently multiple times within a short time frame.
Also, the "Myers" in the article has worked a bit with sequence alignment. He helped design the BLAST algorithm (with Altschul) as well as suffix arrays (with Manber), the algorithms that reassembled the human genome for Celera, and finally, dropped the ultimate bomb: https://academic.oup.com/bioinformatics/article/21/suppl_2/ii79/227189/The-fragment-assembly-string-graph https://academic.oup.com/bioinformatics/article/21/suppl_2/i...
- Animats 10y agoAll string diff algorithms in alignment derive from previous innovations on raw strings. For some applications, it's more useful to just take the hash of each line and compute line diffs from an array of hashes. Diff algorithms which ignore whitespace changes sometimes do this. Few algorithms recognize text re-ordering. This is a problem with Wikipedia diffs, where rearranging text is commonplace. Displaying the changes might require big arrows, but there's no problem with that today.
- WalterGR 10y agoFew algorithms recognize text re-ordering. WinMerge[1] does. Unfortunately it's no longer under development. (I've been looking for an equally-capable tool for Macs but have found nothing...) Do you know which algorithms recognize reordering? [1] http://winmerge.org/ http://winmerge.org/