1

各行に 1 語ずつ、100 万語以上のファイルがあります。単語が与えられた場合、その単語がファイルに存在するかどうかを確認する必要があるコードを作成しようとしています。ここで重要なのは、各単語を26^(word.length()-1)何度もチェックする必要があるということです。したがって、ファイル内のすべての単語を確認することは、適切な解決策ではありません。オンラインでアルゴリズムを見つけようとしましたが、まだかなりの答えが見つかりませんでした。

編集HashMapaと の両方について考えましたTrie。ここでの実際の問題は、私が単語を持っていると言うことabcです。ここで、私のタスクは、単語 X を作成するために単語内の 1 文字だけを追加、削除、または置換しabc、X がファイル内にあるかどうかを確認することです。したがって、どのソリューションがより良いアプローチであるかについて混乱しています。

4

7 に答える 7

8

ファイル内の単語からトライを作成できます。これにより、ハッシュセットよりもはるかに少ないメモリを使用し、O(単語内の文字数) 内の単語の存在を確認できます。もちろん、メモリが問題にならない場合は、Hashset で十分です (これもはるかに少ない労力で構築されるため)。

于 2012-05-02T17:49:37.197 に答える
3

メモリ内の HashSet に単語を格納すると、O(1) ルックアップが得られます。

于 2012-05-02T17:50:39.173 に答える
1

単語が「cad」で、編集距離が 1 以内のすべての単語を探しているとします。

この場合、次のことができます。

1) 辞書の単語を HashMap に格納します。2) 「cad」までの編集距離が 1 の単語のすべての組み合わせを生成します。3) これらの単語のそれぞれについて、その単語が HashMap に存在するかどうかをテストします。

検索は、「お父さん」、「猫」、「車」、「若者」などの単語に一致する必要があります。

于 2012-05-02T18:11:26.047 に答える
0

別の解決策は、ブルームフィルターを使用することです。要素がセットのメンバーであるかどうかをチェックするために使用される、非常に高速でスペース効率の高いデータ構造。短所は、それが確率的なデータ構造であるということです。これは、誤検知が発生する可能性があることを意味します。

mビットの配列を持つことで機能します。フィルタにワードを追加すると、そのワードはk個の異なるハッシュ関数にフィードされ、それらのハッシュによって計算された位置でビットが1に設定されます。フィルタをクエリするときは、同じハッシュに単語をフィードし、ビットがそれらの位置に設定されているかどうかを確認します。これらのビットのいずれかが0の場合、その単語がセットに存在しないことは確かです。すべてが1の場合、他の単語を同じ位置にハッシュするときにこれらのビットが設定されている可能性があるため、ルックアップが必要です。

于 2012-05-02T18:20:29.727 に答える
0

タブラヘイストはより速い方法です

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;) {
   ...
}
于 2012-05-02T18:01:08.557 に答える
0

単語が含まれるファイルを読み込んで、ハッシュ テーブルを作成します。単語が一定時間内に存在するかどうかを確認できるはずです。

于 2012-05-02T17:50:28.850 に答える
0

HashMap がその方法です。すべての単語を HashMap に保存し、マップを調べて単語が存在するかどうかを確認します。もちろん、これは複数のルックアップが必要な場合にのみ役立ちます。

より実用的な解決策は、HashMap をディスクに書き込み、次にアプリケーションを実行するときにメモリにロードすることです。

于 2012-05-02T17:53:34.153 に答える