如何使用kd树来判断字符串相似性？

Question

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

Answer 1

大约一年前，我读过一篇非常火的博客文章，标题是：Levenstein Automata。你可以去看看那篇文章。它不仅介绍了这个算法，还提供了可以跟着做的代码。虽然从技术上讲，它不是一个kd树，但它和我们在现实中可能会遇到的字符串匹配和字典纠错算法有很大的关系。

他还有另一篇关于BK-trees的博客文章，这种树在处理模糊匹配和查找拼写错误的字符串时效果更好。这里还有一个资源，里面有一个BK-tree的源代码（不过我不能确认这个代码的准确性或实现是否正确）。