3

データ ファイルをバイナリ形式で読み取り、ファイル内のパターン (ヘッダー) の出現を検索する最も効率的な方法を探しています。cplusplus.com の例を使用して、ファイルをメモリに読み込みました。

#include <iostream>
#include <fstream>
using namespace std;

ifstream::pos_type size;
char * memblock;

int main () {
  ifstream file ("example.bin", ios::in|ios::binary|ios::ate);
  if (file.is_open())
  {
    size = file.tellg();
    memblock = new char [size];
    file.seekg (0, ios::beg);
    file.read (memblock, size);
    file.close();
  }
  else cout << "Unable to open file";
  return 0;
}

まず、これが私の目的のためにこれを行う最良の方法であるかどうか疑問に思っています。はいの場合、0x54 0x51 のようなパターンを検索する方法を見つけることができなかったか、memblock char 配列で同等のバイナリです。

4

3 に答える 3

0

あなたの目的のための効率的なアルゴリズム（理論的、漸近的な実行時間、および実用的な効率の両方の観点から）は、 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm およびhttp:/ /en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

読み取り可能な文字列を操作するのと同じように、一連のバイトを操作します。それらはビットのシーケンスでも機能します（ただし、この場合、通常は最適なオプションではありません。ビットごとの比較を避ける必要があり、パターンをシフトして比較することもできます。また、アルファベットには0と1のみが含まれます。文字列検索アルゴリズムがその可能性を最大限に活用できるようにします）が、あなたの質問（および可能な16進数表現）に関しては、これがあなたが望んでいるものだとは思いません.

ただし、ディスクからファイルを読み取っていて、パターンが長すぎない場合、プログラムの実行時間は、ディスクからの読み取りにかかる時間に大きく左右されます。その場合、Gam Erix によって投稿された素朴な解決策はまったく問題なく、実装がはるかに簡単です。

機械語よりも小さいパターンの別の最適化: パターンをより大きな型 (uint64_t など) として解釈し、パターン全体に対して単一の比較を使用するだけです (入力シーケンスの最後に到達したときに境界をチェックする必要があります)。

于 2013-06-11T13:38:02.473 に答える
0

各文字を読み取って、検索した最初の出現と比較し、一致する場合は、次のバイトが次の出現と一致するかどうかを確認します.fstreamを使用してバイナリでファイルを読み取ると、バイトが読み取られます.

于 2013-06-11T13:29:09.450 に答える