如何使用kd树来确定字符串相似度？

Question

我正在尝试利用k最近邻算法解决字符串相似性问题，即给定一个字符串和一个知识库，我想输出与我的给定字符串相似的k个字符串。是否有任何教程可以解释如何利用kd树来高效地进行这种字符串的k最近邻查找？字符串长度不会超过20个字符。

- Legend

---

你的两个字符串之间的相似度指标是什么？scipy.spatial.cKDtree 是快速且可靠的，适用于20维，但仅支持Lp度量。 - denis

Answer 1

可能是我一年前读过的最热门的博客文章之一：Levenstein自动机。看看那篇文章吧。它不仅提供了算法的描述，还提供了可供参考的代码。从技术上讲，它不是kd-tree，但它与人们在实际应用中遇到/使用的字符串匹配和字典纠错算法密切相关。

他还有另一篇关于BK-trees的博客文章，这些树在模糊匹配字符串和查找包含拼写错误的字串时要好得多。这里有另一个包含源代码的资源，可以用来做BK-tree（这个我无法验证其准确性或正确实现）。

- wheaties

---

Levenshtein自动机令人印象深刻，然而，在实现它之后，我只能说预计算版本在距离增加时很快就会爆炸（节点方面）。实际上，在Trie中搜索非常快速，但是自动机在距离为4及以上时开始变得非常庞大。 - Matthieu M.

@Matthieu M. 你有什么其他建议？ - wheaties

我没有实现（认真的）任何其他机制，所以我没有任何建议。如果您可以接受最大距离为3，那么请使用它，否则，您将不得不自行探索，恐怕我无能为力 :) - Matthieu M.

@MatthieuM.，嵌套自动机怎么样？例如，允许编辑距离达到3+3。 - 0x90