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

Question

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

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

Answer 1

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

一种有效的方法是在 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是固定的，您可以简单地以此作为预算。