Thanks for the great replies everybody! On Thu, 2006-06-08 at 10:54 -0400, Bob Carpenter wrote: > > Here's a thoughtful discussion of Hirschberg's > edit-distance algorithm: > > http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Hirsch/ > > In general, it appears to be *slower* than Levenstein, although > it only uses space proportional to the shorter string (vs. > Levenstein's product of the string lengths). > > They conclude it's only useful for space if the strings are long. > Looks reasonable, but I have no experience with this algorithm.
That is actually the article that made me want to run Hirschberg in the first place. > the edit-distance generalization of Aho-Corasick. The basic idea is > that instead of n iterations of string vs. string, you do one > iteration of string vs. trie. Cool. I really have to take a look at that. --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
