我了解kd-tree,但当空间维度很高时它们效率低下。我有一个值数据库,并希望查找与查询距离在一定的汉明距离内的值。例如,数据库是32位数字列表,我要查找所有与查询值相差不到3个bit的数字。
我听说过多变量分区树,但找不到好的参考资料。我知道min-Hash可以给出良好的近似值,但我想要精确答案。
我了解kd-tree,但当空间维度很高时它们效率低下。我有一个值数据库,并希望查找与查询距离在一定的汉明距离内的值。例如,数据库是32位数字列表,我要查找所有与查询值相差不到3个bit的数字。
我听说过多变量分区树,但找不到好的参考资料。我知道min-Hash可以给出良好的近似值,但我想要精确答案。
汉明距离与莱文斯坦距离密切相关,类似于用于拼写纠正的算法。
一种有效的方法是在trie中使用分支限界搜索。它需要的时间与距离呈指数关系,在近距离时,最多线性增长到字典大小。
如果字典是存储在二进制trie中的二进制单词,并且具有严格的汉明距离,则可以使用以下简单的伪代码:
walk(trie, word, i, hit, budget){
if (budget < 0 || i > word.length) return;
if (trie==NULL){
if (i==word.length) print hit;
return;
}
hit[i] = 0;
walk(trie.subtrie[0], word, i+1, hit, (word[i]==0 ? budget : budget-1));
hit[i] = 1;
walk(trie.subtrie[1], word, i+1, hit, (word[i]==1 ? budget : budget-1));
}
main(){
for (int budget = 0; ; budget++){
walk(trie, word, 0, hit, budget);
/* quit if enough hits have been printed */
}
}
这个想法是你遍历整个trie,跟踪当前trie节点和原始单词之间的距离。通过设置一个容忍的距离预算来修剪搜索范围。这样做的原因是随着你深入trie,距离永远不会减少。
然后,您可以从零开始并逐步增加预算,重复执行此操作,直到打印出所需的结果。由于每次遍历的节点数比后续遍历的节点数少得多,因此进行多次遍历并不会有太大影响。如果k是固定的,您可以将其作为预算的起点。