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]

Reply via email to