ファイルの中でバイト列を検索する（C＃）

Question

私はファイルを検索する必要がある（非常に大きくなる可能性があります）バイトシーケンスのためにライブラリを使用することはできませんそうする。だから、私は引数としてバイト配列をとり、与えられたシーケンスに続くバイトの位置を返す関数が必要です。この機能は高速である必要はなく、単に機能しなければなりません。任意の助けいただければ幸いです:)

Answer 1

それは速くあなたがこの使用できるようにしていない場合：

int GetPositionAfterMatch(byte[] data, byte[]pattern) 
{ 
    for (int i = 0; i < data.Length - pattern.Length; i++) 
    { 
    bool match = true; 
    for (int k = 0; k < pattern.Length; k++) 
    { 
     if (data[i + k] != pattern[k]) 
     { 
     match = false; 
     break; 
     } 
    } 
    if (match) 
    { 
     return i + pattern.Length; 
    } 
    } 
} 

をしかし、私は実際にそれがだ、クヌース - モリス - プラット法を使用することをお勧めいたしますでしょうアルゴリズムは、主に文字列のIndexOfメソッドのベースとして使用されます。上記のアルゴリズムは、実際には遅く実行され、小さな配列や小さなパターンに対して実行されます。

Answer 2

Turrauの作品で指摘されているような単純なアプローチは、高速である必要はないと言われているので、おそらく十分です。特に実用的な目的でアルゴリズムは最悪の場合O（n * m）。 （あなたのパターンによると思います）。

最適解を得るには、末尾がO（n + m）の部分一致を使用するKnuth-Morris-Pratt algorithmをチェックアウトすることもできます。

Answer 3

ここでは、私がボーイアムーア型検索を行うために使用したコードの抜粋です。これはpcapファイルを扱うことを意味しているので、レコードごとにレコードを処理しますが、ロングバイナリファイルを検索するだけでも簡単に変更できます。それはある種のテストコードから抽出されたものなので、私はあなたが追随するためのすべてを得たことを願っています。また、ウィキペディアでボイラー・ムーアを検索することもあります。

int[] badMatch = new int[256]; 
byte[] pattern; //the pattern we are searching for 

//badMath is an array of every possible byte value (defined as static later). 
//we use this as a jump table to know how many characters we can skip comparison on 
//so first, we prefill every possibility with the length of our search string 
for (int i = 0; i < badMatch.Length; i++) 
{ 
    badMatch[i] = pattern.Length; 
} 

//Now we need to calculate the individual maximum jump length for each byte that appears in my search string 
for (int i = 0; i < pattern.Length - 1; i++) 
{ 
    badMatch[pattern[i] & 0xff] = pattern.Length - i - 1; 
} 

// Place the bytes you want to run the search against in the payload variable 
byte[] payload = <bytes> 

// search the packet starting at offset, and try to match the last character 
// if we loop, we increment by whatever our jump value is 
for (i = offset + pattern.Length - 1; i < end && cont; i += badMatch[payload[i] & 0xff]) 
{ 
    // if our payload character equals our search string character, continue matching counting backwards 
    for (j = pattern.Length - 1, k = i; (j >= 0) && (payload[k] == pattern[j]) && cont; j--) 
    { 
    k--; 
    } 
// if we matched every character, then we have a match, add it to the packet list, and exit the search (cont = false) 
    if (j == -1) 
    { 
    //we MATCHED!!! 
    //i = end; 
    cont = false; 
    } 
}