在一组数百万字符串中查找最相似的字符串

Question

假设我有一个数百万字的字典(单词列表).给定一个查询词,我想从那个最相似的巨大列表中找到这个词.

所以,假设我的查询是elepant,那么结果很可能是elephant.

如果我的话fentist,结果可能是dentist.

当然,假设两个elephant和dentist存在于我最初的单词列表.

我可以使用什么样的索引,数据结构或算法来使查询快速？希望复杂性O(log N).

我所拥有的:最天真的事情是创建一个"距离函数"(根据它们的不同来计算两个单词之间的"距离")然后在O(n)中将查询与每个单词进行比较在列表中,返回距离最近的那个.但我不会用它,因为它很慢.

Answer 1

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

如果您需要精确的解决方案，我会推荐度量树，例如M 树、MVP 树和BK 树。这些树利用三角不等式来加速搜索。

如果您愿意接受近似解，还有更快的算法。近似方法的当前技术水平是分层可导航小世界（hnsw）。非度量空间库 (nmslib)提供了 hnsw 以及其他几种近似 NNS 方法的有效实现。