假设我有数以百万计的单词的词典(单词列表)。给定一个查询词，我想从最相似的庞大列表中找到该词。
因此，假设我的查询是elepant，那么结果很可能是elephant。
如果我的单词是fentist，则结果可能是dentist。
当然，假设elephant和dentist都出现在我的初始单词列表中。
我可以使用哪种索引，数据结构或算法来快速查询？希望O(log N)的复杂性。
我所拥有的:最天真的事情是创建一个“距离函数”(根据两个词之间的差异来计算两个单词之间的“距离”)，然后在O(n)中将查询与列表中的每个单词，然后返回距离最近的单词。但是我不会使用它，因为它很慢。
最佳答案
您所描述的问题是最近邻居搜索(NNS)。解决NNS问题的主要方法有两种:精确和近似。
如果需要确切的解决方案，我建议使用度量树，例如 M-tree ， MVP树和 BK树。这些树利用三角形不等式来加快搜索速度。
如果您愿意接受一个近似的解决方案，那么可以使用更快的算法。近似方法的当前技术水平为Hierarchical Navigable Small World (hnsw)。 Non-Metric Space Library (nmslib)提供了hnsw以及其他几种近似NNS方法的有效实现。
(您可以使用Hirschberg's algorithm计算Levenshtein距离)