C++搜索算法 - 处理大量数据

Question

我有一个代码在文件中搜索字符串,文件可以是1毫克或1克或更大.

我使用ReadFile()WinAPI 获取文件数据并转换为十六进制,然后在转换数据中搜索字符串(之前是十六进制).

我用这个代码进行搜索(字符串搜索):

std::string searchStr = "48656C6C6FA"
std::string fileData = ToHex(inputString);

if(fileData.find(searchStr, 0) != std::string::npos)
{
    std::cout << FileName;
}

在2900个文件中搜索字符串大约需要11秒.

有没有其他搜索算法或功能更快？这种方式(上面)有时会错过字符串而不是完美的工作.

Answer 1

如果你有一个更小的文件(如几百兆,甚至几百兆字节,取决于存储系统的数量已经),那么读这一切到内存,否则我建议使用内存映射文件.如果要映射的文件很大,可以使用滑动窗口或双缓冲算法将数据块从文件读入内存.

然后搜索字节的特定序列,您可以通过文件的内容做一个线性搜索,寻找第一您搜索序列的字节(在的情况下,0x48656C6C6FA这是0xFA).如果找到,则尝试将序列中的第二个字节(在示例中0xC6)与文件中的下一个字节匹配,依此类推,直到匹配整个序列.

如果第二个(或连续)字节不匹配,则继续搜索第一个字节.

这具有O(n)复杂度,其中n是文件中的字节数.除非您事先知道您搜索的数据位于文件的特定部分,否则这是您将获得的最佳数据.

如果SSD上存在文件,则可以使用线程进行搜索,每个文件一个线程.但并非所有2900文件同时存在,这将淹没处理器.相反,有4-8个线程在进行搜索(取决于系统的核心数量),并且只要一个线程完成一个文件,就会接下来.

不能在旋转磁盘驱动器上使用,因为它会在磁头正在尝试读取磁头时来回扫描磁盘.