c++ - 制作字典图的有效方法

Question

在汉明距离 = 1 的情况下，制作字典中单词图的最有效方法是什么？

Answer 1

汉明距离仅针对长度相等的单词定义，因此您实际上会为字典中的每个单词长度创建一个不相交的图表。如果你的意思是 levenshtein distance，它允许插入和删除，那么你确实会有一个图。

一个选择是构造一个 BK-tree从你的字典。虽然严格来说不是图，但它允许您提出相同的问题(获取具有给定距离的元素列表)，并且需要 O(n log n) 的时间来构造。

另一种选择是蛮力法:对于每个词，测试它与所有候选词的距离。您可以将候选词缩小到相同长度的词(或者长度少一或多一倍，用于 levenshtein)。这是 O(n^2) 最坏的情况，但如果您不多次构建图表，这可能是可以接受的。

理论上，可能有一种 O(n log n) 的方法来构建图 - 在简单的情况下，构建 BK 树，然后从中生成图是 O(mn log n)，其中 m 是平均值每个节点的边数 - 但我不知道一个优雅的。