如何在n维空间中找到k最接近的值？

Question

我读过关于kd-trees的内容，但是当空间的维度很高时，它们效率很低。我有一个值的数据库，我想查找在查询的特定汉明距离内的值。例如，数据库是一个32位数字的列表，我想查找所有与查询值不同的小于3位的数字。

我听说有关多变量分区树的地方，但找不到一个很好的参考。我知道min-Hash给出了一个很好的近似值，但是我想要一个确切的答案。

Answer 1

汉明距离与levenshtein distance密切相关，与用于拼写校正的算法类似。

一种可行的方法是branch-and-bound在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 */ 
    } 
} 

的想法是你走在整个线索，跟踪的当前三元节点与原始单词之间的距离。您可以通过预算您可以容忍多少距离来修剪搜索。这是有效的，因为当你深入到线索时，距离永远不会减小。

然后，您重复执行此操作，预算从零开始逐步增加，直到您打印出您想要的匹配。由于每次散步比后来散步的节点少得多，所以不会伤害您进行多次散步。如果k已修复，那么您可以简单地将其作为预算开始。