data-structures - 实现“获取所有 Levenshtein 距离小于 X 的字符串”的方法

Question

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

我感兴趣的几件事：

• 算法说明。
• 现有数据库/编程语言中是否有现有实现？
• 我可以参考的论文/文章？

Answer 1

这是度量空间中的最近邻搜索，以 levenshtein 距离作为度量（或距离）函数

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

这个Python VP-tree 实现是一个工作演示，展示了 VP-tree 如何在说单词列表上运行它它提供了一个交互式 shell，您可以在其中键入一个单词并返回该列表中不超过 X 距离的单词根据您输入的单词

Answer 2

听起来像是一个简单的广度优先搜索，每一代都与前一代相比只有一个“编辑”——并进行了检查以确保字符串出现在一个且只有一个级别。

这可以很容易地在一对循环中使用几个哈希集/哈希表来实现。