1

我想使用 C++ 或 C 在大型（> 500 MB）文本文件中找到一些值。我知道可能的匹配值只能存在于每行的开头，并且它的长度正好是十个字符。好的，我可以逐行读取整个文件，使用 substr() 搜索值或使用正则表达式，但这有点难看而且非常慢。我考虑使用嵌入式数据库（例如 Berkeley DB），但我要搜索的文件是非常动态的，每次都将其导入数据库时​​遇到问题。由于内存的限制，无法一次将整个文件加载到内存中。提前谢谢了。

4

5 回答 5

3

这似乎不太适合 C/C++。由于问题的定义需要解析整行文本，并在前 10 个字符上执行模式匹配，因此解释的东西，如 python 或 perl 似乎更简单。

怎么样：

import os
pattern ='0123456789'   # <-- replace with pattern

with open('myfile.txt') as f:
    for line in f:
        if line.startswith(pattern):
            print "Eureka!'
于 2012-04-05T19:08:56.810 回答
2

我看不出你将如何比使用 stdio 库更快地做到这一点，将每一行依次读入缓冲区，然后使用,strchr或类似的东西。鉴于您对问题的描述，这已经是相当理想的了。没有什么魔法可以避免逐行遍历文件以查找您的模式。strcmpstrncmp

也就是说，如果您在行首处理正好十个字符的固定模式，那么这里几乎肯定不需要正则表达式——这会不必要地慢，而且我不会使用正则表达式库。

如果你真的，真的需要在最后几微秒内完成，并且模式实际上是恒定的并且在一行的开头，你可能可以memchr在读入缓冲区中查找 "\npattern" 或一些这样的（也就是说，在您的搜索中包括换行符），但您听起来好像模式不是完全恒定的。假设它不是完全恒定的，最明显的方法（见第一段）是最明显的事情。

于 2012-04-05T19:05:47.273 回答
1

如果您要查找大量值，那么您想使用Aho-Corasick。该算法允许您创建一个单一的有限状态机，它可以同时搜索集合中任何字符串的所有出现。这意味着您可以一次搜索文件并找到您要查找的每个值的所有匹配项。上面的维基百科链接有一个 Aho-Corasick 的 C 实现的链接。如果您想查看我编写的 Go 实现，可以查看此处。

如果您正在寻找单个或很少数量的值，那么您最好使用Boyer-Moore。尽管在这种情况下您可能只想使用 grep，它可能与您为此应用程序编写的任何内容一样快。

于 2012-04-05T19:43:50.850 回答
0

在搜索之前使用内存映射文件怎么样？

http://beej.us/guide/bgipc/output/html/multipage/mmap.html

一种方法可能是加载和搜索内存中的第一个 64 MB，卸载它然后加载下一个 64 MB，依此类推（以 4 KB 的倍数，这样您就不会忽略任何可能在块边界处拆分的文本）

还可以查看 Boyer Moore 字符串搜索

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

于 2012-04-05T19:14:32.433 回答
0

是的，这可以快速完成。到过那里。做到了。但是，很容易引入错误。

诀窍在于管理缓冲区的末尾，因为您将读取一个充满数据的缓冲区，搜索该缓冲区，然后继续下一个。由于该模式可能跨越两个缓冲区之间的边界，因此您最终会编写大部分代码来涵盖这种情况。

无论如何，在边界情况之外，您有一个如下所示的循环：

unsigned short *p = buffer;
while( (p < EOB) && ( patterns[*p] ) ) ++p;

这假设 EOB 已被适当地初始化，并且 patterns[] 是一个包含 65536 个值的数组，如果您不能位于模式的开头，则为 0，如果可以，则为 1。

根据您的 CR/LF 和字节顺序约定，设置为 1 的模式可能包括 \nx 或 \rx，其中 x 是 10 个字符模式中的第一个字符。或者 x\n 或 x\r 用于其他字节顺序。如果您不知道字节顺序或约定，您可以包括所有四个。

一旦有了候选位置（EOL 后跟第一个字节），您就可以检查剩余的 9 个字节。构建模式数组是提前离线完成的。两个字节模式适合一个足够小的数组，这样您在进行索引时不会有太多的内存抖动，但是您可以像使用单字节一样快两倍地压缩数据。

您可以在其中添加一个疯狂的优化，那就是在缓冲区的末尾写一个标记，并将其放入您的模式数组中。但是那个哨兵必须是不能出现在文件中的东西。不过，它将循环缩减为一项测试、一项查找和一项增量。

于 2012-04-05T19:28:01.843 回答