如何在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已修復，那麼您可以簡單地將其作爲預算開始。