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

只需读取每个字符并将其与您搜索的第一个匹配项进行比较，如果匹配，则检查下一个字节是否与下一个匹配项匹配，当您使用 fstream 读取二进制文件时，它会读取字节。

于 2013-06-11T13:29:09.450 回答
0

我怀疑这是最有效甚至最快的方法，而且我没有声称拥有超级技术，但这是一种扫描位模式的方法。

//...
file.close();
//...
unsigned int pattern = 0x5451;
unsigned int mask
    = static_cast<unsigned int>(pow(2, 16) - 1) //generate 16-bit mask
;
unsigned int read_buff = static_cast<unsigned char>(memblock[1]);
    read_buff << 8;
    read_buff |= static_cast<unsigned char>(memblock[0]);

//start at index 2 since we already read 2 bytes.
for (ifstream::pos_type i = 2; i < fsize; i += 1) {

    for (char shift_count = 0; shift_count < 8; ++shift_count) {

        //put the third byte into read_buff
        if (shift_count == 0) {
            unsigned int read_byte = static_cast<unsigned char>(memblock[i]);
            read_byte <<= 16;
            read_buff |= read_byte;
        }

        unsigned int work_area = read_buff;
        work_area &= mask;

        if (work_area == pattern) {
            //happy dance
        }

        read_buff >>= 1;
    }
}
于 2013-06-11T20:02:00.493 回答
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，它们不包含允许字符串搜索算法发挥其全部潜力），但关于您的问题（以及可能的十六进制表示），我认为这不是您想要的。

但是，如果您正在从磁盘读取文件，并且模式不是太长，则程序的执行时间将很大程度上取决于从磁盘读取所需的时间。在这种情况下，Gam Erix 发布的简单解决方案非常好，而且更容易实现。

对小于机器字的模式的另一种优化：只需将模式解释为更大的类型（例如 uint64_t）并对整个模式使用单个比较（当您到达输入序列的末尾时，您必须检查边界）

于 2013-06-11T13:38:02.473 回答