在输入流中查找字符串

Question

我有一个很大的二进制文件（几个GB，无法将其加载到内存中），我想要在其中搜索所有出现的字符串 "icpf"。

我尝试使用 std::search 进行搜索，但是遇到了问题，因为 std::search 仅适用于前向迭代器，而不适用于输入迭代器。

标准库提供了快速的替代方法吗？还是我需要手动编写搜索代码（读取文件块然后对其进行 std::search，或者忽略一切直到 'i' 并手动检查接下来的三个字符）？

- zennehoy

Answer 1

标准库提供了一个快速的替代方法吗？

尽管标准C++库提供了搜索文本流的方法，但它并没有为二进制流提供可比较的算法。

还是我需要手动编写搜索程序（一次读入一块，然后在其中使用 std::search 进行搜索，或者忽略一切直到出现“i”，然后手动检查接下来的三个字符）？

编写“跳过和搜索”方法可能会很棘手，因为很容易编写一个跳过条目的解决方案。例如，如果您正在寻找包含“icpicpf”的文件中的“icpf”，那么一个一次处理一个字符的简单程序将无法在丢弃“icpi”前缀后找到“icpf”后缀。

如果您要自己编写代码，请考虑实现 Knuth-Morris-Pratt 算法。网上有许多实现，它可以正确地处理流，因为它逐个字符考虑，从不后退。

- Sergey Kalinichenko

Answer 2

最快的方法是将整个文件加载到内存中，然后搜索内存。

下一个最佳选择是保持硬盘运转。也许有一个线程将数据块读入缓冲区，另一个线程搜索缓冲区。

按顺序读取大块数据到缓冲区中，然后搜索缓冲区是一种好的技术，但不如前面的方法高效。

您可以逐行读取，使用std :: getline和std :: string。这不像块读取那样快，因为输入函数正在搜索换行符（并在std :: string中分配内存）。

最糟糕的情况可能是逐个字符地阅读。读取单个字符的函数开销很大（通常读取大块数据的开销相同）。

不，没有用于搜索文件的标准C ++库函数。一些操作系统具有用于搜索文件的实用程序；也许您可以使用其中之一。

编辑1：
瓶颈在于输入数据。一旦将数据输入缓冲区，就有许多有效的搜索算法，而不是暴力搜索（搜索第一个字母，然后搜索下一个字母等）。

在互联网上搜索“字符串搜索算法”。

- Thomas Matthews

---

什么文件需要缓存/流式传输才能读取？比如，如果它很大，比如超过4Gb。它需要按块搜索，或者更好的是按需流式传输。 - Sandburg

Answer 3

我不知道任何纯标准库的解决方案，但内核已经实现了预取功能，因此可以通过mmap()将文件映射到所需的前向迭代器：（省略错误处理）

size_t search(int fd, size_t fileSize) {
    auto start = reinterpret_cast<char*>(
        ::mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0));
    ::madvise(start, fileSize, MADV_SEQUENTIAL);
    auto pattern = "icpf";
    auto offset = std::search(start, start+fileSize, pattern, pattern+4);
    return offset - start;
}

相信内核可以正确地进行惰性加载、预取和丢弃，这需要一点点信任。另一方面，如果你可以相信任何人做到这一点，那可能就是内核开发人员。

免责声明：我实际上没有在多GB文件上测试过这个。

- Benno