string - 在数百万个字符串中寻找最相似的字符串

Question

假设我有一个包含数百万个单词的字典(单词列表)。给定一个查询词，我想从那个庞大的列表中找到最相似的词。

假设我的查询是elepant，那么结果很可能是elephant。

如果我说的是fentist，结果可能是dentist。

当然假设 elephant 和 dentist 都出现在我的初始单词列表中。

我可以为此使用什么样的索引、数据结构或算法以便查询速度快？希望复杂度为 O(log N)。

我有什么:最天真的做法是创建一个“距离函数”(计算两个词之间的“距离”，根据它们的不同程度)，然后在O(n) 将查询与列表中的每个单词进行比较，并返回距离最近的那个。但我不会使用它，因为它很慢。

Answer 1

您描述的问题是最近邻搜索 (NNS)。解决 NNS 问题的方法主要有两种:精确和近似。

如果你需要一个精确的解决方案，我会推荐一个metric tree，比如M-tree，MVP-tree，和 BK 树。这些树利用三角不等式来加速搜索。

如果您愿意接受近似解，还有更快的算法。近似方法的当前技术水平是 Hierarchical Navigable Small World (hnsw) . Non-Metric Space Library (nmslib)提供了 hnsw 的有效实现以及其他几种近似 NNS 方法。

(您可以使用 Hirschberg's algorithm 计算 Levenshtein 距离)