我正在尝试利用 k 最近邻来解决字符串相似性问题,即给定一个字符串和一个知识库,我想输出与给定字符串相似的 k 个字符串。是否有任何教程解释了如何利用 kd-trees 有效地对字符串进行 k-最近邻查找?字符串长度不会超过 20 个字符。
问问题
3641 次
可能是我大约一年前读过的最热门的博客文章之一:Levenstein Automata。看看那篇文章。它不仅提供了算法的描述,还提供了要遵循的代码。从技术上讲,它不是 kd-tree,但它与人们可能在现实世界中遇到/使用的字符串匹配和字典校正算法非常相关。
他还有另一篇关于BK-trees的博客文章,它在字符串的模糊匹配和存在拼写错误的字符串查找方面要好得多。这是另一个包含BK-tree源代码的资源(这个我无法验证准确性或正确实现。)