基于预先计算的哈希比较字符串距离

Question

我有一个大的列表（超过200,000）我想要比较给定的字符串的字符串。 给定的字符串是由用户插入的，因此它可能稍微不正确。

我希望做的是创建一些预先计算的哈希每个字符串添加到列表。这个哈希将包含诸如字符串长度，所有字符的添加等信息。

我的问题是，这样的事情已经存在了吗？肯定会有东西让我避免在列表中的每个字符串上运行Levenshtein distance？

或者还有第三个选项我还没有想过呢？

Answer 1

听起来像你想使用某种模糊散列。有很多可用的哈希函数可以做这样的事情。经典的“SOUNDEX”算法甚至可能工作。另一个想法 - 如果你估计出现错误输入的可能性很低，那么你可能实际上没有99.9％的直接命中时间，回到SOUNDEX可能会捕获剩余的90％的情况，然后在剩下的0.01％的时间内搜索整个列表。

也值得检查这个讨论： How to find best fuzzy match for a string in a large string database