4

kd ツリーについて読みましたが、空間の次元が高い場合は非効率的です。値のデータベースがあり、クエリから特定のハミング距離内にある値を見つけたいと考えています。たとえば、データベースは 32 ビットの数値のリストであり、クエリ値との差が 3 ビット未満のすべての数値を見つけたいとします。

MultiVariate Partition trees についてどこかで聞いたことがありますが、適切なリファレンスが見つかりませんでした。min-Hash の方が適切な近似値を提供することは知っていますが、正確な答えが欲しいです。

4

1 に答える 1

1

ハミング距離はレーベンシュタイン距離と密接に関連しており、スペル修正に使用されるアルゴリズムに似ています。

機能する方法は、 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は、それを予算として単純に開始できます。

于 2010-03-06T13:57:25.937 に答える