7

我正在尝试利用 k 最近邻来解决字符串相似性问题,即给定一个字符串和一个知识库,我想输出与给定字符串相似的 k 个字符串。是否有任何教程解释了如何利用 kd-trees 有效地对字符串进行 k-最近邻查找?字符串长度不会超过 20 个字符。

4

1 回答 1

8

可能是我大约一年前读过的最热门的博客文章之一:Levenstein Automata。看看那篇文章。它不仅提供了算法的描述,还提供了要遵循的代码。从技术上讲,它不是 kd-tree,但它与人们可能在现实世界中遇到/使用的字符串匹配和字典校正算法非常相关。

他还有另一篇关于BK-trees的博客文章,它在字符串的模糊匹配和存在拼写错误的字符串查找方面要好得多。这是另一个包含BK-tree源代码的资源(这个我无法验证准确性或正确实现。)

于 2011-04-17T22:26:30.930 回答