如何使用kd

本文介绍了如何使用kd-tree确定字符串相似度?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试利用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.

推荐答案

可能是我大约一年前读过的最热门的博客文章之一: Levenstein自动机.看看那篇文章.它不仅提供了算法描述，而且提供了后续代码.从技术上讲，它不是kd树，而是与现实世界中可能遇到/使用的字符串匹配和字典校正算法非常相关.

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.

他还有另一篇关于 BK的博客文章-trees 更好地用于字符串的模糊匹配和存在拼写错误的字符串查找.这是另一个资源，其中包含 BK-树的源代码(这是我无法验证准确性或正确的实施方式.)

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.)