セジウィックは彼の著書「アルゴリズム」の中で、三分探索木を使用すると、「クエリ単語の特定のハミング距離内にあるすべての単語を見つけることができる」と書いています。Dr. Dobb's の記事
私の本能は、各 String を繰り返し処理しn、 と異なる文字数のカウンターを維持するsことですが、それが最も効率的なソリューションであるとは主張していません。ただし、これは O(n) になるため、これが既知のパフォーマンスの問題または学術的な問題でない限り、それを使用します。
文字列が固定長の場合、2 つの文字列間のハミング距離を計算して類似性を判断できます。これは文字列の長さで O(n) です。したがって、最悪のケースは、文字列を m 単語と比較するためのアルゴリズムが O(nm) であるということです。
別の方法として、メモリを大量に消費する高速な解決策は、辞書をマップに前処理することです。キーはタプル (p, c) で、p は文字列内の位置、c は文字列内のその位置の文字、値はその位置に文字を持つ文字列です (したがって、「the」はマップ内の{(0, 't'), "the"}, {(1, 'h'), "the"}, {(2, 'e'), "the"})。マップをクエリするには、クエリ文字列の文字を繰り返し処理し、取得した文字列を使用して結果マップを作成します。キーは文字列、値はプライマリ マップから文字列が取得された回数です (つまり、クエリ文字列 "the" では、キー "thx" の値は 2 になり、キー "tee" の値は1 の値)。ついに、
結果マップが完成したときに K と等しくない可能性があるキーを破棄することで、メモリを節約できます。たとえば、K が 5 で N が 8 の場合、クエリ文字列の 4 番目から 8 番目の文字に到達すると、結果マップにまだ含まれていない取得済み文字列を破棄できます。一致する文字。または、クエリ文字列の 6 番目の文字を処理し終わったら、結果マップを反復処理して、値が 3 未満のすべてのキーを削除できます。
必要に応じて、メイン メモリを節約するために (また、プログラムを再起動するたびに辞書を事前に計算する必要がないように)、事前に計算されたプライマリ マップを NoSql キー値データベースなどにオフロードできます。
タプル (p, c) をキーとしてプライマリ マップに格納する代わりに、位置と文字を文字列に連結することができます (つまり、(5, 't') は「5t」になり、(12, 'x') ）は「12x」になります）。
各入力文字列のどこに一致する文字があるかわからない場合、特定の文字列について、チェックインする順序に関係なく、すべての文字をチェックする必要がある場合があります。不一致の総数の合計を保持します。iがこれまでの不一致の数である場合、文字列に残っているチェックされていない文字よりも少ない場合にfalse戻りi == kます。truek-i
文字列の長さと許容される不一致の数によっては、これらのチェックを実行するよりも文字列全体を反復する方が速い場合や、数文字ごとに実行する方が速い場合があることに注意してください。試してみて、最速のパフォーマンスを得る方法を確認してください。