我需要使用 C# 在一组文本文件中搜索大约 13 个字符的字符串。文本文件的数量在变化，范围在 100-1000 之间。文件的大小可以在 1KB 到 10MB 之间。
我尝试了打开每个文件的幼稚方式，逐行读取并查看字符串是否存在（使用index.of），但这太慢了。我还尝试使用 Boyer-Moore 算法，该算法确实将时间缩短了 5 秒，但这仍然感觉很慢。
关于如何加快搜索速度的任何想法？
问问题
7101 次
5 回答
9
根据您要进行“搜索”的次数，您是否要使用搜索引擎。如果您想搜索很多次，请使用搜索引擎，否则：不要。我将在这里描述如何实现这两种场景。
使用搜索引擎时：听起来您正在寻找子字符串，这意味着您应该使用您最喜欢的搜索引擎来索引您的文件，最好是您可以自定义的搜索引擎（lucene、terrier 等）。您在这里需要的技术是索引三元组，即：所有 3 字符组合都必须被索引。F.ex.: 'foobar' 将生成 'foo','oob','oba' 和 'bar'。搜索时，您希望对查询执行相同操作，并使用所有这些三元组的 AND 发出搜索引擎查询。（这将在文档的发布列表上运行合并连接，这将返回他们的 ID 或您在发布列表中放置的任何内容）。
或者，您可以实现后缀数组并索引您的文件一次。如果您想搜索短（1-2 个字符）子字符串，这将提供更多的灵活性，但就索引而言更难维护。（在 CWI/Amsterdam 有一些关于快速索引后缀数组的研究）
当您只想搜索几次时，要使用的算法是 Boyer-Moore（我通常使用 Boyer-moore-sunday，如 [Graham A. Stephen，String Search] 中所述）或编译后的 DFA（您可以构造它们）来自 NFA，更容易制作）。然而，这只会给你带来一点速度提升，原因很简单，磁盘 IO 可能是你的瓶颈，并且比较你需要解码的一堆字节非常快。
您可以做出的最大改进不是逐行读取文件，而是分块读取。如果可以的话，您应该将 NTFS 配置为使用 64 KB 的块大小，并以 64 KB 的倍数读取文件 - 考虑一次读取 4 MB 或更多。我什至建议使用异步 IO，以便您可以同时读取和处理（以前读取的数据）。如果你做得正确，那应该已经在大多数现代硬件上为你提供了 10 MB 的瞬间实现。
最后但同样重要的是，在整个信息检索中使用的一个巧妙技巧也是使用快速压缩算法压缩数据。由于磁盘 IO 比内存/cpu 操作慢，这可能也会有所帮助。Google 的 Snappy 压缩器是快速压缩算法的一个很好的例子。
于 2013-02-12T07:57:41.353 回答
3
您应该考虑对内容使用操作系统文件搜索。查看Microsoft Windows Search 3.x SDK
或者您可以利用 PLINQ 在文件数组中进行搜索。请参阅此链接：
于 2013-02-12T07:17:51.160 回答
3
想到两个选择：
读取内存中的文本文件，然后一次搜索整个字符串。
如果这被证明太慢或太占用内存，请使用像 Apache Lucene 这样的索引器。有一个可用于 .NET 的好用且简单的 SDK，称为 Lucene.net
这里对其做一个小介绍：http: //www.codeproject.com/Articles/29755/Introducing-Lucene-Net
于 2013-02-12T07:26:22.233 回答
1
您可以使用 Microsoft 的索引服务来搜索要添加到目录中的文件夹中的文档。这是一篇非常好的文章，您可以使用它来搜索您的文本文件
于 2013-02-12T09:00:11.010 回答
1
如果您的计算机可以处理它，请尝试将所有文本文件加载到内存中（使用此处显示的技术，然后评估内存中的文本。
如果您不能一次处理所有文件，那么对最小的文件执行此操作。文件 I/O 将是您最大的开销，因此您希望尽可能地减少它。
于 2013-02-12T07:29:41.887 回答