在文本文件中搜索字符串的更快捷方式

Question

我需要使用C#在一组文本文件中搜索大约13个字符的字符串.文本文件的数量正在变化,范围在100-1000之间.文件大小可以在1KB到10MB之间.

我尝试了打开每个文件的天真方式,逐行读取并查看字符串是否存在(使用index.of),但这太慢了.我也试过使用Boyer-Moore算法,它确实提高了时间,持续5秒,但这仍然感觉很慢.

有关如何加快搜索速度的想法吗？

Answer 1

根据您想要进行"搜索"的次数,您想要使用搜索引擎.如果您想要搜索很多次,请使用搜索引擎,否则:不要.我将在这里描述如何实现这两个场景.

使用搜索引擎时:听起来你正在寻找子串,这意味着你应该使用自己喜欢的搜索引擎索引你的文件,最好是你可以定制的(lucene,terrier等).这里你需要的技术是索引三元组,即:所有3个字符的组合都必须被索引.F.ex.:'foobar'将产生'foo','oob','oba'和'bar'.搜索时,您希望对查询执行相同操作,并使用所有这些三元组的AND发出搜索引擎查询.(这将在文档的发布列表上运行合并连接,这将返回他们的ID或您在发布列表中放置的任何内容).

或者,您可以实现后缀数组并将文件索引一次.如果要搜索短(1-2个字符)子字符串,这将提供更多的灵活性,但在索引方面更难维护.(在CWI/Amsterdam有一些研究用于快速索引后缀数组)

当你只想搜索几次时,要使用的算法是Boyer-Moore(我通常使用[Graham A. Stephen,String Search]中描述的Boyer-moore-sunday)或编译的DFA(你可以构建它们)来自NFA,这更容易制作).但是,这只会给你一个小的速度增加,原因很简单,因为磁盘IO可能是你的瓶颈,并且比较你需要解码的一堆字节是非常快的.

您可以做的最大改进是不是逐行读取文件,而是以块为单位.如果可以,则应将NTFS配置为使用64 KB的块大小,并以64 KB的倍数读取文件 - 在单次读取中认为4 MB或更多.我甚至建议使用异步IO,以便您可以同时读取和处理(以前读取的数据).如果你正确地执行它,那应该已经在大多数现代硬件上为你提供了10 MB的瞬间实现.

最后但同样重要的是,在整个信息检索过程中使用的一个巧妙的技巧也是使用快速压缩算法压缩数据.由于磁盘IO比内存/ CPU操作慢,这也可能有所帮助.谷歌的Snappy压缩器是快速压缩算法的一个很好的例子.

Answer 2

您应该考虑使用操作系统文件搜索内容。查看Microsoft Windows Search 3.x SDK

或者您可以使用 PLINQ 在文件数组中进行搜索。请参阅此链接：

使用 Directory.GetFiles 和 PLINQ 进行文件内容和目录搜索