2016-10-08 14 views
1

私はメモリにロードする余裕がない膨大なファイルがあり、内部で見つける必要があるバイトシーケンスがあります。巨大なファイルをメモリにロードせずに検索する方法はありますか?

これは私が今使用しているものである:

public static byte[] GetRangeFromStream(ref FileStream fs, long start_index, long count) 
{ 
    byte[] data = new byte[count]; 
    long prev_pos = fs.Position; 
    fs.Position = start_index; 
    fs.Read(data, 0, data.Length); 
    fs.Position = prev_pos; 
    return data; 
} 

public static long GetSequenceIndexInFileStream(byte[] seq, ref FileStream fs, long index, bool get_beginning = true) 
{ 
    if (index >= fs.Length) 
     return -1; 

    fs.Position = index; 

    for (long i = index; i < fs.Length; i++) 
    { 
     byte temp_byte = (byte)fs.ReadByte(); 

     if (temp_byte == seq[0] && IsArraysSame(seq, GetRangeFromStream(ref fs, i, seq.Length))) //compare just first bytes and then compare seqs if needed 
      return i; 
    } 

    return -1; 
} 
+1

シーケンスをメモリに格納しますか?はいの場合、チャンク内のファイルを読み込み、各チャンク内のシーケンスを検索します。シーケンスが2つのチャンクに分割されている場合の処理​​について覚えておいてください。 – janisz

+0

誰があなたを落としてしまったのか、なぜ、それが完璧に良い技術的な質問なのかは分かりません。 – PhillipH

+0

@janisz - はい、それは合っていますが、最初のバイトを比較してseqを比較するのではなく、常に 'seq'と' chunk'を比較します。それとも、私はあなたを間違って理解していますか? – Kosmos

答えて

0

Knuth Moriss Pratt algorithmの修正版を使用することを提案します。 アルゴリズムkmp_search: 入力: 文字のストリーム、S(テキストが検索される) 文字の配列、W(ワードが求め) 出力: 整数(Sゼロベースの位置WにKMPアルゴリズムはテキストで後戻りしないので)

define variables: 
    an integer, m ← 0 (the beginning of the current match in S) 
    an integer, i ← 0 (the position of the current character in W) 
    an array of integers, T (the table, computed elsewhere) 

while m + i < length(S) do 
    if W[i] = S[m + i] then 
     if i = length(W) - 1 then 
      return m 
     let i ← i + 1 
    else 
     if T[i] > -1 then 
      let m ← m + i - T[i], i ← T[i] 
     else 
      let m ← m + 1, i ← 0 

(if we reach here, we have searched all of S unsuccessfully) 
return the length of S 

を発見されたテキスト文字列がでストリーミングすることができます。ストリーミングの場合、到着する文字を処理するための償却された時間はƟ(1)ですが、最悪の場合の時間はƟ(min(m、n '))です(ストリーミングをサポートしていない単純なアルゴリズムとは別の改良です) ))ここで、n 'はこれまでに見たテキスト文字の数です。 Source

Referecne(Java)の実装はhere

package com.twitter.elephantbird.util; 

import java.io.IOException; 
import java.io.InputStream; 
import java.util.Arrays; 

/** 
* An efficient stream searching class based on the Knuth-Morris-Pratt algorithm. 
* For more on the algorithm works see: http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm. 
*/ 
public class StreamSearcher { 

    protected byte[] pattern_; 
    protected int[] borders_; 

    // An upper bound on pattern length for searching. Results are undefined for longer patterns. 
    public static final int MAX_PATTERN_LENGTH = 1024; 

    public StreamSearcher(byte[] pattern) { 
    setPattern(pattern); 
    } 

    /** 
    * Sets a new pattern for this StreamSearcher to use. 
    * @param pattern 
    *   the pattern the StreamSearcher will look for in future calls to search(...) 
    */ 
    public void setPattern(byte[] pattern) { 
    pattern_ = Arrays.copyOf(pattern, pattern.length); 
    borders_ = new int[pattern_.length + 1]; 
    preProcess(); 
    } 

    /** 
    * Searches for the next occurrence of the pattern in the stream, starting from the current stream position. Note 
    * that the position of the stream is changed. If a match is found, the stream points to the end of the match -- i.e. the 
    * byte AFTER the pattern. Else, the stream is entirely consumed. The latter is because InputStream semantics make it difficult to have 
    * another reasonable default, i.e. leave the stream unchanged. 
    * 
    * @return bytes consumed if found, -1 otherwise. 
    * @throws IOException 
    */ 
    public long search(InputStream stream) throws IOException { 
    long bytesRead = 0; 

    int b; 
    int j = 0; 

    while ((b = stream.read()) != -1) { 
     bytesRead++; 

     while (j >= 0 && (byte)b != pattern_[j]) { 
     j = borders_[j]; 
     } 
     // Move to the next character in the pattern. 
     ++j; 

     // If we've matched up to the full pattern length, we found it. Return, 
     // which will automatically save our position in the InputStream at the point immediately 
     // following the pattern match. 
     if (j == pattern_.length) { 
     return bytesRead; 
     } 
    } 

    // No dice, Note that the stream is now completely consumed. 
    return -1; 
    } 

    /** 
    * Builds up a table of longest "borders" for each prefix of the pattern to find. This table is stored internally 
    * and aids in implementation of the Knuth-Moore-Pratt string search. 
    * <p> 
    * For more information, see: http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm. 
    */ 
    protected void preProcess() { 
    int i = 0; 
    int j = -1; 
    borders_[i] = j; 
    while (i < pattern_.length) { 
     while (j >= 0 && pattern_[i] != pattern_[j]) { 
     j = borders_[j]; 
     } 
     borders_[++i] = ++j; 
    } 
    } 
} 

を見つけることができる同様の質問:Efficient way to search a stream for a string

+0

ありがとうございます。私もそれを調べます。 – Kosmos

+1

ええと...私はそれをテストし、修正版は鉱山版よりも2倍速く動作しません。私はそれを信じていない。すべてのシーケンスが実際に見つかったかどうかをテストする必要があります。 – Kosmos

+0

オフサイトのリソースにアクセスできない場合に備えて、リンクのコンテキストを提供してください。 – IInspectable

2

これを行うための最適な方法は、ファイルストリームのバイト単位だけあなたが探している文字列の最初のバイト探しを読むことです。あなたがマッチを得るとき、あなたはヒットする可能性があることを知っています。次のNバイト(Nは検索される文字列の長さ)を読み込み、ファイルから読み込まれたバイトの内容と検索されるバイトの配列比較を行います。

オープン時に適切なFileStreamバッファを設定して、ファイル読み込みバッファを.netで処理します。自分のバッファを作成するためにフォワードを読むことについて心配しないでください。時間の無駄です.netはうまくいきます。

このアプローチは、ファイルが本当に大きいです、あなたはI/Oバウンドでないなら、あなたは複数を作成することを検討可能性など、あなたがすべてのバイトを比較した配列ではなく、あなたがバッファ間で分割を気にしないでください

を意味し、タスクは、ファイル・ストリーム内の別の場所から始まる各.netタスク・ライブラリーを使用し、すべてのタスクが完了したら各タスクの結果を照合します。

+0

をチェックアウトして何かを理解していない。 'FileStream pf = new FileStream(tpls [i]、FileMode.Open、FileAccess.Read、FileShare.Read、256 * 1024 * 1024);'検索が劇的に遅くなったO_o – Kosmos

+1

それはそうではありません最適解です。最初のバイト一致が多くの不必要なチェックを引き起こす場合を比較するが、基本的な考え方が有効であるという観察を組み込む必要があるのは、 "不一致が発生したときに、"メイン "テキストストリング" S内の "単語そのものは、次の一致が始まる場所を決定するのに十分な情報を具体化します。 " – janisz

+0

バイトストリーム全体をメモリに読み込まないようにするには、バッファ付きチャンクで読み込む必要があります。 .netはそれを処理する完全に良いバッファリングされたファイルストリームを持っています。バッファ内の最初のバイトに対して読み込まれた各バイトのチェックは、どちらのアプローチで行っても必要ありません。最後のNバイトをスキップすることができます。ここで、Nは検索タームから1を引いたものですが、できることはすべてです。ファイルコンテンツのインデックスを作成したい場合は、それ以降の検索の速度は向上しますが、何が要求されているかはわかりません。 – PhillipH

1

あなたはfile mappingをチェックアウトする場合があります。大きなファイルを本質的にメモリバッファであるかのように扱うことができるため、メモリベースのAPIディスクファイルに使用することができます。ファイルI/Oを明示的に指定する必要はありません。

MSDN:

ファイルマッピングは、プロセスの仮想アドレス空間の一部と、ファイルの内容の関連性です。この関連付けを維持するためのファイルマッピングオブジェクト(セクションオブジェクトとも呼ばれます)が作成されます。ファイルビューは、プロセスがファイルの内容にアクセスするために使用する仮想アドレス空間の一部です。ファイルマッピングにより、プロセスはランダム入出力(I/O)とシーケンシャルI/Oの両方を使用できます。また、ファイル全体をメモリにマップすることなく、データベースなどの大きなデータファイルで効率的に処理を実行することもできます。複数のプロセスは、メモリマップファイルを使用してデータを共有することもできます。tell me more...

関連する問題