我试图利用k近邻来解决字符串相似性问题，即给定一个字符串和一个知识库，我想输出与给定字符串相似的k个字符串。有没有教程可以解释如何利用kd树来高效地对字符串进行k近邻查找？字符串长度不得超过20个字符。
最佳答案
可能是一年前我读过的最热门的博客之一：Levenstein Automata。看看那篇文章。它不仅提供了算法的描述，还提供了后续的代码。从技术上讲，它不是KD树，但它与在现实世界中可能遇到/使用的字符串匹配和字典校正算法非常相关。
他还有另一篇关于BK-trees的博客文章，这篇文章在字符串模糊匹配和字符串查找方面做得更好。这里是另一个包含BK-tree的源代码的资源（这一个我不能验证准确性或正确的实现）。