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

Question

我了解kd-tree，但当空间维度很高时它们效率低下。我有一个值数据库，并希望查找与查询距离在一定的汉明距离内的值。例如，数据库是32位数字列表，我要查找所有与查询值相差不到3个bit的数字。

我听说过多变量分区树，但找不到好的参考资料。我知道min-Hash可以给出良好的近似值，但我想要精确答案。

- Eyal

Answer 1

汉明距离与莱文斯坦距离密切相关，类似于用于拼写纠正的算法。

一种有效的方法是在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是固定的，您可以将其作为预算的起点。

- Mike Dunlavey