lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From karl wettin <ka...@snigel.net>
Subject Re: Edit-distance strategy (slicing and one vs. all algorithms)
Date Thu, 08 Jun 2006 22:57:10 GMT
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: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message