我有一个很大的字符串列表（超过 200,000 个），我想将它们与给定的字符串进行比较。给定的字符串是由用户插入的，因此可能略有不正确。
我希望做的是在将每个字符串添加到列表时创建某种预先计算的哈希值。该哈希将包含诸如字符串长度、所有字符的添加等信息。
我的问题是，这样的东西已经存在了吗？肯定会有一些东西可以让我避免在列表中的每个字符串上运行Levenshtein 距离吗？
或者也许我还没有想到第三种选择？
问问题
1570 次
1 回答
3
听起来您想使用某种模糊哈希。有很多可用的哈希函数可以做这样的事情。经典的旧“ SOUNDEX ”算法甚至可能有效。
另一个想法 - 如果您估计输入错误的概率很低，那么您实际上可能会在 99.9% 的时间内直接命中，然后退回到 SOUNDEX，它可能会捕获 90% 的剩余案例，然后搜索整个列出剩余 0.01% 的时间。
还值得检查这个讨论： 如何在大型字符串数据库中找到字符串的最佳模糊匹配
于 2010-08-12T23:41:40.447 回答