2

サイズが 20 GB の大きなテキスト ファイルがあります。このファイルには、比較的短いテキスト行が含まれています (1 行あたり 40 ～ 60 文字)。ファイルはソートされていません。

20,000 個の一意の文字列のリストがあります。ファイルに表示されるたびに、各文字列のオフセットを知りたいです。現在、私の出力は次のようになります。

netloader.cc found at offset: 46350917
netloader.cc found at offset: 48138591
netloader.cc found at offset: 50012089
netloader.cc found at offset: 51622874
netloader.cc found at offset: 52588949
...
360doc.com found at offset: 26411474
360doc.com found at offset: 26411508
360doc.com found at offset: 26483662
360doc.com found at offset: 26582000

20,000 個の文字列を std::set にロードし (一意性を確保するため)、ファイルから 128 MB のチャンクを読み取り、string::find を使用して文字列を検索します (別の 128 MB のチャンクを読み取ることからやり直します)。これは機能し、約 4 日で完了します。読み取り境界が検索対象の文字列を壊す可能性については心配していません。もしそうなら、それはOKです。

もっと速くしたいです。1 日で検索を完了するのが理想的ですが、パフォーマンスが大幅に向上するのは素晴らしいことです。他のライブラリを避けながら、(必要に応じて) Boost を備えた標準 C++ を使用することを好みます。

だから私は2つの質問があります：

  1. 私が使用しているツールとタスクを考慮すると、4 日間の時間は合理的に思えますか?
  2. より速くするための最良のアプローチは何ですか？

ありがとう。

編集: Trie ソリューションを使用して、実行時間を 27 時間に短縮することができました。1日以内ではありませんが、確実に今でははるかに高速です。アドバイスをありがとう。

4

3 に答える 3

3

アルゴリズム的に、この問題にアプローチする最善の方法は、一度に文字を検索する行を格納するためにツリーを使用することだと思います。たとえば、探したい次のパターンがあるとします。

hand, has, have, foot, file

結果のツリーは次のようになります。 検索語のリストによって生成されるツリー

ツリーの生成は最悪の場合の O(n) であり、一般にサブリニア メモリ フットプリントがあります。

この構造を使用すると、巨大なファイルから一度に 1 文字ずつ読み取ることでファイルの処理を開始し、ツリーをたどることができます。

  • リーフ ノード (赤で表示されているノード) に到達すると、一致が見つかり、それを保存できます。
  • 赤の文字に対応する子ノードがない場合は、現在の行を破棄して、ツリーのルートから次の行のチェックを開始できます。

この手法では、一致をチェックし、巨大な 20 GB ファイルを 1 回だけスキャンするために線形時間 O(n) が発生します。

編集

上記のアルゴリズムは確かに適切ですが(誤検知は発生しません)、完全ではありません(いくつかの結果を見逃す可能性があります)。ただし、 goとgoneのような共通の語根を持つ検索語がないことを前提として、いくつかの小さな調整を行うだけで完全なものにすることができます。以下は、アルゴリズムの完全版の疑似コードです。

tree = construct_tree(['hand', 'has', 'have', 'foot', 'file'])
# Keeps track of where I'm currently in the tree
nodes = []
for character in huge_file:
  foreach node in nodes:
    if node.has_child(character):
      node.follow_edge(character)
      if node.isLeaf():
        # You found a match!!
    else:
      nodes.delete(node)
  if tree.has_child(character):
    nodes.add(tree.get_child(character))

nodes毎回チェックする必要があるのリストは、最大でチェックする必要がある最長の単語の長さであることに注意してください。したがって、それほど複雑になるべきではありません。

于 2013-05-03T14:40:39.633 に答える