如何使用 kd 树来确定字符串相似度？
我正在尝试利用 k-近邻来解决字符串相似性问题，即给定一个字符串和一个知识库，我想输出与给定字符串相似的 k 个字符串。是否有任何教程解释如何利用 kd 树有效地进行字符串的 k 最近邻查找？字符串长度不会超过 20 个字符。
I am trying to utilize k-nearest neighbors for the string similarity problem i.e. given a string and a knowledge base, I want to output k strings that are similar to my given string. Are there any tutorials that explain how to utilize kd-trees to efficiently do this k-nearest neighbor lookup for strings? The string length will not exceed more than 20 characters.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
可能是我大约一年前读过的最热门的博客文章之一：莱文斯坦自动机。看看那篇文章。它不仅提供了算法的描述，还提供了要遵循的代码。从技术上讲，它不是 kd 树，但它与现实世界中可能遇到/使用的字符串匹配和字典校正算法非常相关。
他还有另一篇关于 BK-trees< /a> 在字符串的模糊匹配和存在拼写错误的字符串查找方面表现得更好。这是另一个包含 BK-tree 源代码的资源（这个是我无法验证准确性或正确实施。）
Probably one of the hottest blog posts I had read a year or so ago: Levenstein Automata. Take a look at that article. It provides not only a description of the algorithm but also code to follow. Technically, it's not a kd-tree but it's quite related to the string matching and dictionary correction algorithms one might encounter/use in the real world.
He also has another blog post about BK-trees which are much better at the fuzzy matching for strings and string look ups where there are mispellings. Here is another resource containing source code for a BK-tree (this one I can't verify the accuracy or proper implementation.)