computational-geometry - 如何在 n 维空间中找到 k 最近值？

Question

我读过 kd-trees，但是当空间的维数很高时它们效率低下。我有一个值(value)数据库，我想找到查询的某个汉明距离内的值。例如，数据库是一个 32 位数字的列表，我想找到与查询值相差小于 3 位的所有数字。

我在某处听说过 MultiVariate Partition 树，但找不到好的引用资料。我知道 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 */
  }
}

这个想法是你遍历整个 trie，跟踪当前 trie 节点和原始单词之间的距离。您可以通过预算可以容忍的距离来修剪搜索。这是有效的，因为随着您深入到特里，距离永远不会减少。

然后您重复执行此操作，预算从零开始并逐步增加，直到打印出您想要的匹配项。由于每次遍历包含的节点比后续遍历少得多，因此进行多次遍历并没有什么坏处。如 k是固定的，您可以简单地将其作为预算开始。