5

これは面接の質問であり、効率に関する懸念でした。ログファイルのような非常に大きなファイル（GB単位）がある場合。ファイルの終わりから「error」や「java」などの単語の10番目の出現を見つけるにはどうすればよいですか。ファイル全体をスキャンして、逆の順序で発生を見つけることしか考えられません。しかし、私はそれが正しい方法だとは思いません！（できればCまたはJavaでのコーディング）

また、別のことを知りたいです。インタビュアーがそのファイルが非常に大きいと具体的に言及する場合、コードを書き始めるときに考慮すべき要素は何ですか（スキャンは本当にコストのかかる問題であることを忘れないでください）

4

3 に答える 3

4

大きなテキスト内の単語を検索するには、ボイヤームーアアルゴリズムが広く使用されています。

原則（実際の例についてはリンクを参照）：ファイル内のある場所（インデックス）で比較を開始するときに、比較対象のテキストの最初の文字が検索対象の単語にまったく含まれていない場合、比較する必要はありません。他の[wordLength-1]文字とテキスト、およびインデックスは単語の長さの前に移動できます。文字が単語に含まれている場合、ここでは正確ではありませんが、数文字だけシフトされている場合は、比較も数文字だけシフトできます...

  • 単語の長さとテキストとの類似性によっては、検索が大幅に高速化される場合があります（naiveSearchTime / wordLengthまで）。

編集ファイルの最後から検索するので、単語の最初の文字（最後ではない）が最初に比較されます。たとえば、「2001 a space odyssey」で「space」を検索すると、単語スペース「s」はオデッセイの最初の「y」と比較されます。次の比較は、テキストスペース「c」に対する同じ「s」です。
そして最後に、n番目のオカレンスを見つけるために、単語が見つかるたびに単純なカウンター（ nに初期化）がデクリメントされ、0に達するとそれだけです。

アルゴリズムは理解しやすく、実装も簡単です。面接に最適です。

ファイルを1回だけ検索するのか、それとも数回検索するのかを尋ねることもできます。複数回検索する場合は、ファイルから単語にインデックスを付けることをお勧めします。つまり、単語が含まれているかどうか、どこに、何回かなどをすばやく見つけることができる構造をメモリ内に作成します...私はTrieアルゴリズムも理解しやすく、非常に高速であることが好きです（文章）。その複雑さはO（wordLength）です。

-

インタビュアーが「非常に大きなファイル」について言及する場合、考慮すべき多くの要因があります。

  • 上記の検索アルゴリズム
  • テキストはメモリに収まりますか？（たとえば、すべてを処理する場合）ファイルシークアルゴリズムを実装する必要がありますか（つまり、一度にメモリ内のファイルの一部のみを使用します）
  • ファイルはどこにありますか？メモリ（高速）、ハードディスク（低速ですが、少なくともローカル）、リモート（通常は低速、接続の問題、リモートへのアクセス、ファイアウォール、ネットワーク速度など）
  • ファイルは圧縮されていますか？（圧縮を解除すると、さらに多くのスペースが必要になります）
  • ファイルは1つのファイルまたは複数のチャンクで構成されていますか？
  • テキストまたはバイナリが含まれていますか？テキストの場合、その言語は文字が出現する可能性を示します（たとえば、英語ではYがフランス語よりもはるかに頻繁に出現します）。
  • 必要に応じて、ファイルの単語にインデックスを付けることを提案します
  • より簡単に処理できる小さなファイルを作成するために、大きなファイルからより単純なファイルを作成することを提案します（繰り返しの単語を削除するなど）。

..。

于 2013-01-16T05:22:02.647 に答える
1

この質問に対する答えには2つの部分があります。1つは、使用されるアルゴリズムであり、任意の適切な文字列検索アルゴリズム（Boyer Moore / KMP / Trieなど）にすることができます。他の部分はIOです。ファイルから実際に逆方向に読み取ることができないため、処理を高速化するには、次のような方法が適しています。

  1. たとえば10MBのメモリのチャンクを割り当てます
  2. for（i = 1;（filesize -10MB * i）> = 0; i ++）{
  3. （ファイルサイズ-10MB * i）をシークし、10MBをメモリに読み込みます
  4. 現在のチャンク内の文字列を逆方向に検索し、カウンターをインクリメントします
  5. カウンターが10になったら停止します

これは非常にIO指向の質問であり、マルチスレッドシステムまたは複数のマシンを使用してこのアプローチを改善できます。このアプローチでは、検索とファイルからメモリへの読み取り（つまり、手順3と4）を並行して実行できます。

これはC++コードですが、Javaでそれを行う方法を知っています。

于 2013-01-16T05:51:00.977 に答える
0

@AlexeyFrunze によるコメントに追加して、関連記事を参照してください: read file backwards (last line first)。しかしおそらく、インタビュアーは、限られたメモリの問題にどのように対処するかを確認するために、通常の順方向に読むという解決策に興味を持っていました.

@ring0 によるすばらしい投稿なので、非常に大きなファイルで、kが 10 のように小さい末尾からk番目の単語を具体的に見つける問題についてのみ言及します。その後、逆方向に検索します。

サイズkのキューとも呼ばれる先入れ先出しバッファーを維持できます。このキューには、一致に遭遇したときに一致の位置を保存できます。より多くの一致を見つけるにつれて、以前のものを忘れてしまいます。を指定してゼロに初期化すると、キューイングに対処できます。ファイルの最後に到達したら、const int k = 10;long match_pos[k];countmatch_pos[count % k] = pos

if (count >= k)
{
    int kth_match_pos = match_pos[(count + 1) % k];
    // ...
}

はバッファ内の最も古いエントリをチェックするため、 nバイト ( nは) に戻ることができますpos - kth_match_pos。関連するコンテキストもキューに格納されている場合、シークは必要ありません。

于 2013-01-16T05:52:31.163 に答える