data-structures - 实现 "Get all strings with Levenshtein distance less than X"的方法

我想知道是否有一个有效的数据结构来执行“检索levenshtein距离小于X的所有字符串”。

我感兴趣的几件事:

算法说明。

现有数据库/编程语言中是否存在现有实现？

我可以引用的论文/文章？

最佳答案

这是度量空间中以levenshtein距离作为度量(或距离)函数的最近邻居搜索

VP-tree是解决该问题的方法之一

此Python VP-tree implementation是一个工作演示，演示了VP-tree的工作方式，例如在单词列表上运行它，它提供了一个交互式 shell 程序，您可以在其中键入单词，并返回列表中的单词，该单词与单词的距离不超过X打字