我正在尝试根据集合计算字符串的编辑距离以找到最接近的匹配项。我目前的问题是集合非常大（大约 25000 个项目），所以我不得不将集合缩小到只有相似长度的字符串，但这仍然只能将其缩小到几千个字符串，这仍然很慢。是否有允许快速查找类似字符串的数据结构，或者是否有另一种方法可以解决这个问题？
问问题
684 次
3 回答
8
听起来像BK-tree可能是你想要的。这是一篇讨论它们的文章：http: //blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。一个快速的谷歌产生了一些 Java 实现。
于 2012-02-04T08:50:22.227 回答
6
Levenshtein Automata 允许从大型词典中快速选择一组单词，以便它们与给定单词的给定 Levenshtein 距离内。
请参阅：Schulz K, Mihov S. (2002)使用 Levenshtein-Automata 进行快速字符串校正。
于 2012-02-04T10:32:52.023 回答
2
如果你的“相似”标准定义了一个总排序，你应该能够定义一个比较器并使用一个树集来找到最接近的匹配项（例如使用天花板和地板方法）。
于 2012-02-04T08:42:32.493 回答