我需要使用C#在一组文本文件中搜索一个大约13个字符长度的字符串。文本文件的数量是变化的，可能在100-1000之间。文件的大小范围可以在1KB和10MB之间。
我尝试了朴素的方法，即打开每个文件，逐行读取并查看是否存在该字符串（使用index.of），但这太慢了。我还尝试过使用Boyer-Moore算法，虽然时间有所改善，但仍然感觉很慢。
有什么想法可以加速搜索吗？
在文本文件中快速查找字符串的方法
15
- ocp1000
3
2你的减速可能来自逐行读取文件。将整个文件一次性读入内存并搜索它。 - dda
http://stackoverflow.com/questions/4289353/fastest-way-to-search-ascii-files-in-c-sharp-for-simple-keywords - Ofiris
你需要多次在同一文件上执行搜索吗？ - user626528
5个回答
9
根据你需要进行“搜索”的次数，你可以选择使用搜索引擎或不使用。如果你需要经常搜索，使用搜索引擎；否则就不用。下面我将介绍如何实现这两种情况。
使用搜索引擎时：看起来你正在寻找子字符串，这意味着你应该使用自己喜欢的搜索引擎对文件进行索引，最好是可定制的搜索引擎（如lucene、terrier等）。在这里你需要的技术是索引三元组，也就是说，所有的3个字符的组合都必须被索引。例如：'foobar'将生成'foo'、'oob'、'oba'和'bar'。当搜索时，你需要对查询执行相同的操作，并使用所有这些三元组的AND发出搜索引擎查询。（这将在文档的posting lists上运行合并连接，返回它们的ID或你放入posting lists中的任何内容）。
另外，你可以实现后缀数组并对文件进行一次索引。如果你想搜索短的（1-2个字符）子字符串，这会给你更多的灵活性，但从索引的角度来看，它更难维护。（CWI/阿姆斯特丹有一些关于快速索引后缀数组的研究）
当你只想搜索几次时，要使用的算法是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压缩器是一个快速压缩算法的好例子。
使用搜索引擎时：看起来你正在寻找子字符串，这意味着你应该使用自己喜欢的搜索引擎对文件进行索引，最好是可定制的搜索引擎（如lucene、terrier等）。在这里你需要的技术是索引三元组，也就是说，所有的3个字符的组合都必须被索引。例如：'foobar'将生成'foo'、'oob'、'oba'和'bar'。当搜索时，你需要对查询执行相同的操作，并使用所有这些三元组的AND发出搜索引擎查询。（这将在文档的posting lists上运行合并连接，返回它们的ID或你放入posting lists中的任何内容）。
另外，你可以实现后缀数组并对文件进行一次索引。如果你想搜索短的（1-2个字符）子字符串，这会给你更多的灵活性，但从索引的角度来看，它更难维护。（CWI/阿姆斯特丹有一些关于快速索引后缀数组的研究）
当你只想搜索几次时，要使用的算法是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压缩器是一个快速压缩算法的好例子。
- atlaste
3
你应该考虑使用带内容的操作系统文件搜索。查看Microsoft Windows Search 3.x SDK。
或者，您可以利用PLINQ搜索文件数组。请参阅此链接： 使用Directory.GetFiles和PLINQ进行文件内容和目录搜索。
或者，您可以利用PLINQ搜索文件数组。请参阅此链接： 使用Directory.GetFiles和PLINQ进行文件内容和目录搜索。
- Habib
2
1不是要打击你，但我能理解：你只是在将一个愚蠢的解决方案（基本上是IndexOf）与PLINQ并行化，这并不能使它成为一个好的解决方案 - 你基本上只是向它投入更多的硬件，从而使它更快。这就像告诉那个人在多个线程中读取和处理他的文件。使用他建议的Boyer-Moore算法比这个好得多。此外，我不确定MS Search是否支持自定义分词，这似乎是一个要求。所以，在我作为搜索专家的看来，这里有比你的答案更好的答案。抱歉...我很感激你的好意。 - atlaste
太棒了！PLINQ非常快速！而且只需要几行代码！我使用了ReadAllText，这是最快的方法。 - colin lamarre
3
我能提供两种方案：
1. 将您的文本文件读入内存，然后一次性搜索整个字符串。
2. 如果这种方法过于缓慢或需要大量内存，则可以使用索引程序，如Apache Lucene。对于.NET，有一个名为Lucene.net的易用SDK可供使用。
下面是一个小的介绍链接： http://www.codeproject.com/Articles/29755/Introducing-Lucene-Net
1. 将您的文本文件读入内存，然后一次性搜索整个字符串。
2. 如果这种方法过于缓慢或需要大量内存，则可以使用索引程序，如Apache Lucene。对于.NET，有一个名为Lucene.net的易用SDK可供使用。
下面是一个小的介绍链接： http://www.codeproject.com/Articles/29755/Introducing-Lucene-Net
- Wim Haanstra
1
如果您的计算机可以处理，请尝试将所有文本文件加载到内存中（使用此处显示的 技术），然后在内存中评估文本。
如果您无法一次处理所有文件，则请针对最小的文件执行此操作。文件I/O将是您的最大开销，因此您要尽可能地将其最小化。
如果您无法一次处理所有文件，则请针对最小的文件执行此操作。文件I/O将是您的最大开销，因此您要尽可能地将其最小化。
- Yaakov Ellis
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接