私は100万語以上のファイルを持っています。私はコードを書こうとしています。単語が与えられた場合、その単語がファイルに存在するかどうかを調べる必要があります。ここのことは、各単語を26^(word.length()-1)回確認する必要があります。したがって、ファイル内のすべての単語を調べることは良い解決策ではありません。私はアルゴリズムをオンラインで見つけようとしましたが、感知できる答えはまだ見つかりませんでした。私はHashMapとTrieの両方について考えている最速の方法は、百万語のリストを与えられた単語の編集距離を見つける
EDIT 。ここでの実際の問題は、私が単語abcを持っていると言うことです。さて、私の仕事は、単語abcの1文字を正確に追加、削除、または置換して単語Xを作成し、Xがファイルに含まれているかどうかを確認することです。したがって、どのソリューションがより良いアプローチになるのか混乱します。
ファイル内の単語からtrieを作成できます。これは、ハッシュセットよりもはるかに少ないメモリを使用し、O（単語の文字数）で単語の存在を確認することができます。メモリが問題でない場合は、もちろんハッシュセットも行います（それはそれほど労力がかからないためです）。
単語を含むファイルを読み込むときにハッシュテーブルを作成します。一定の時間内に単語が存在するかどうかを確認することができます。
メモリ内のHashSetに単語を格納すると、O（1）ルックアップが表示されます。
ハッシュマップは行く方法です。すべての単語をHashMapに保存してから、地図を参照して単語が存在するかどうかを確認してください。もちろん、複数のルックアップが必要な場合にのみ便利です。
さらに実際的な解決策は、ディスクにHashMapを書き込んで、次にアプリケーションを実行するときにメモリにロードすることです。
タブラのHASTは、あなたの言葉は、「CAD」で、あなたは、この場合、1
の編集距離内のすべての単語を見つけるために探していると仮定し、より速い方法
FileInputStream inputStream = new FileInputStream("input.txt");
InputStreamReader streamReader = new InputStreamReader(inputStream, "UTF-8");
BufferedReader in = new BufferedReader(streamReader);
Map<String, Integer> map = new HashMap<String, Integer>();
for (String s; (s = in.readLine()) != null;) {
...
}
です次のことができます。
1）辞書の単語をHashMapに格納します。 2）編集距離が1〜 "cad"のすべての単語の組み合わせを生成します。 3）これらの各単語について、その単語がHashMapに存在するかどうかをテストします。
あなたの検索では、別の解決策は、Bloom Filterを使用することですなど
「お父さん」、「猫」、「車」、「若者」、などの言葉と一致する必要があります。要素がセットのメンバーであるかどうかをチェックするために使用される非常に高速でスペース効率のよいデータ構造。欠点は、それが偽陽性が可能であることを意味する確率的なデータ構造であるということです。
mビットの配列を持つことで動作します。フィルタに単語を追加するとき、単語は、それらのハッシュによって計算された位置でビットを1に設定するk個の異なるハッシュ関数に供給される。フィルタを調べるときは、同じハッシュに単語を送り、その位置にビットが設定されているかどうかを確認します。これらのビットのいずれかが0の場合、そのワードがセットに存在しないことが確かです。すべてが1の場合、他のワードを同じ位置にハッシュするときにこれらのビットが設定されている可能性があるためルックアップが必要です。
あなたは特定のファイルシステム/ OSまたは多くの検索を実行していますか？ –
私はそれを言ってくれましたが、あなたの言葉をデータベース（リレーショナル、キー/値、memcache）にすべて貼り付けて、それを調べる方がはるかに賢いでしょう。これは – ControlAltDel
のデータベースです@ LeonardoCooper：その1つのファイル、正確なテキストファイルです。 – noMAD