当前位置：文江博客话题详情

使用 C++ 在非常大的文本文件 (10 GB) 中搜索多个单词最快的方法

发布于 2024-12-08 02:03:53 字数 226 浏览 1 评论 0原文

我有这个程序，我必须在非常大的文本文件中搜索特定值及其行号，并且同一值可能会多次出现。

我尝试过一个简单的 C++ 程序，它逐行读取文本文件并使用 strstr 搜索值，但它花费了很长的时间gggggggggggggg

我还尝试使用 grep 使用系统命令，但仍然花费了很多时间，没有以前那么长了，但时间还是太多了。

我正在寻找一个可以用来加快搜索速度的库。有什么帮助和建议吗？谢谢：）

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夜司空 2024-12-15 02:03:53

关于速度有两个问题：实际需要的时间
读取数据以及搜索所需的时间。

一般来说，读取文件最快的方法是 mmap 它（或者
Windows 下的等效项）。如果整个
文件不适合地址空间，但您在地址空间中提到了 10GB
标头；如果您在程序中所做的只是搜索，那么这不应该创建
任何问题。

更一般地说，如果速度是一个问题，请避免在
字符串。读取大块并拾取行（如 char[]）
其中，无需复制，速度明显更快。（作为一个简单的
妥协，当一条线穿过块边界时，您可能需要复制。
如果您正在处理 MB 或更多的块，这应该不会太严重
经常;我在较旧的 16 位机器上使用过这种技术，带有块
32KB，并且仍然获得了显着的性能改进。）

关于搜索，如果您正在搜索单个固定的
字符串（不是正则表达式或其他模式匹配），您可能
想尝试一下BM搜索。如果您要搜索的字符串是
相当长，这可以与其他方法产生显着差异
搜索算法。（我认为 grep 的某些实现将
如果搜索模式实际上是固定字符串，并且是，请使用此选项
足够长的时间才能产生影响。）

回复收藏 0 原文

请远离我 2024-12-15 02:03:53

使用多线程。每个线程可以负责搜索文件的一部分。例如，在 4 核机器上生成 12 个线程。第一个线程查看文件的前 8%，第二个线程查看文件的第二个 8%，依此类推。您需要调整每个核心的线程数以保持 cpu 的最大利用率。由于这是一个 I/O 密集型操作，您可能永远无法达到 100% 的 CPU 利用率。

使用此设计，向线程提供数据将成为瓶颈。映射文件的内存可能会有所帮助，但最终磁盘一次只能读取一个扇区。这将成为你难以解决的瓶颈。您可能会考虑启动一个线程，该线程除了将所有数据读入内存外什么都不做，并在数据加载时启动搜索线程。

回复收藏 0 原文

决绝 2024-12-15 02:03:53

由于文件是连续的野兽，从头到尾搜索是您可能无法回避的事情，但是您可以做一些事情。

如果数据是静态的，您可以生成一个较小的查找文件（替代方案，带有主文件的偏移量），如果多次重复相同的字符串使索引文件小得多，那么这很有效。如果文件是动态的，您可能需要偶尔（离线）重新生成索引文件，

而不是逐行读取，而是从文件中读取更大的块（例如几 MB）以加速 I/O。

回复收藏 0 原文

两人的回忆 2024-12-15 02:03:53

如果您想使用库，可以使用 xapian。

您可能还想在搜索之前尝试对文本进行标记，我还建议您也尝试正则表达式，但如果您没有该文本的索引，这将花费很多时间，所以我绝对建议您尝试xapian 或一些搜索引擎。

回复收藏 0 原文

赏烟花じ飞满天 2024-12-15 02:03:53

如果您的大文本文件不经常更改，则创建一个带有表的数据库（例如 SQLite）：

create table word_line_numbers
  (word varchar(100), line_number integer);

读取您的文件并在数据库中为每个单词插入一条记录，如下所示：

insert into word_line_numbers(word, line_number) values ('foo', 13452);
insert into word_line_numbers(word, line_number) values ('foo', 13421);
insert into word_line_numbers(word, line_number) values ('bar', 1421);

创建单词索引：

create index wird_line_numbers_idx on word_line_numbers(word);

然后您可以找到使用此索引快速查找单词的行号：

select line_number from word_line_numbers where word='foo';

为了提高速度（因为数据库大小较小）和复杂性，您可以使用 2 个表：words(word_id 整数主键，word not null) 和 word_lines （word_id 整数不为空引用单词， line_number 整数不为空）。

If your big text file does not change often then create a database (for example SQLite) with a table:

create table word_line_numbers
  (word varchar(100), line_number integer);

Read your file and insert a record in database for every word with something like this:

insert into word_line_numbers(word, line_number) values ('foo', 13452);
insert into word_line_numbers(word, line_number) values ('foo', 13421);
insert into word_line_numbers(word, line_number) values ('bar', 1421);

Create an index of words:

create index wird_line_numbers_idx on word_line_numbers(word);

And then you can find line numbers for words fast using this index:

select line_number from word_line_numbers where word='foo';

For added speed (because of smaller database size) and complexity you can use 2 tables: words(word_id integer primary key, word not null) and word_lines(word_id integer not null references words, line_number integer not null).

回复收藏 0 原文

远昼 2024-12-15 02:03:53

我会尝试首先将尽可能多的文件加载到 RAM 中（文件的内存映射是一个不错的选择），然后在多个处理器上同时搜索其中的部分内容。您需要在缓冲区边界附近特别小心，以确保没有遗漏任何单词。另外，您可能想尝试比典型的 strstr() 更有效的方法，请参阅这些：
Boyer–Moore 字符串搜索算法
 Knuth–Morris–Pratt 算法

回复收藏 0 原文

~没有更多了~