0

BK树（Burkhard-Keller 树）与模糊字符串搜索（例如拼写检查、单词推荐）相关联。并且所有的 BK 树搜索算法都与这里解释的相同。例如，如果我搜索 "aeek"，目的是返回"seek" 和 "peek" 。

现在，我的问题是，我正在尝试使用这种模糊字符串搜索算法从给定的字典中搜索所有相似的项目。例如，给定一个单词“seek”，我想在字典中查找所有相似的单词，例如“peek”、“geek”、“seat”等。但是我发现每个人都使用的 BK 树搜索算法并不是为此而设计的。

看看我的样本测试结果here。我发现如果喂词顺序不同，字典会有所不同，因此搜索结果也会有所不同。

我想要的是，使用我上面的示例测试，给定四本 Python 书籍中的任何一本，一个SearchAll函数将始终返回这四本 Python 书籍，而不管字典的构建顺序或搜索完成的顺序。

但是，我尝试了很多方法，但都失败了（例如，这是其中之一）。现在我举手寻求帮助。一个伪代码或通用算法描述就可以了。谢谢。

4

1 回答 1

1

你在bktree.go 的第77和106行有一个整数溢出：

k := d - r

由于d和的类型r是uint8， 的类型k也是uint8，所以当d < r,k最终大于时，d + r不会执行下一个循环。

你可以像这样修复它：

k := int16(d) - int16(r)
max_k  := int16(d) + int16(r)
if k < 1 {
    k = 1
}
for ; k <= max_k; k++ {
    ...
}
于 2017-08-27T09:46:19.757 回答