Lez*_*zan 5 java algorithm edit-distance pattern-matching data-structures
我试图计算字符串对集合的编辑距离,以找到最接近的匹配.我目前的问题是集合非常大(大约25000个项目),所以我不得不将集合缩小到相似长度的字符串,但仍然只会将其缩小到几千个字符串,这仍然非常慢.是否存在允许快速查找类似字符串的数据结构,还是有另一种方法可以解决此问题？
听起来像BK树可能是你想要的.这是一篇讨论它们的文章:http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees.一个快速的谷歌产生了一些Java实现.
Levenshtein Automata允许从大字典中快速选择一组单词,使得它们在给定单词的给定Levenshtein距离内.
参见:Schulz K,Mihov S.(2002)使用Levenshtein-Automata进行快速弦校正.