ハミング距離はレーベンシュタイン距離と密接に関連しており、スペル修正に使用されるアルゴリズムに似ています。
機能する方法は、 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
は、それを予算として単純に開始できます。