<分区>
我需要使用 C# 在一组文本文件中搜索大约 13 个字符的字符串。文本文件的数量在变化,范围在 100-1000 之间。文件的大小可以在 1KB 到 10MB 之间。
我尝试了打开每个文件的天真方式,逐行读取它并查看字符串是否存在(使用 index.of),但这太慢了。我还尝试使用 Boyer-Moore 算法,它确实将时间缩短了 5 秒,但这仍然感觉很慢。
关于如何加快搜索的任何想法?
<分区>
我需要使用 C# 在一组文本文件中搜索大约 13 个字符的字符串。文本文件的数量在变化,范围在 100-1000 之间。文件的大小可以在 1KB 到 10MB 之间。
我尝试了打开每个文件的天真方式,逐行读取它并查看字符串是否存在(使用 index.of),但这太慢了。我还尝试使用 Boyer-Moore 算法,它确实将时间缩短了 5 秒,但这仍然感觉很慢。
关于如何加快搜索的任何想法?
最佳答案
取决于您要进行“搜索”的次数,您是否要使用搜索引擎。如果您想搜索很多次,请使用搜索引擎,否则:不要。我将在此处描述如何实现这两种情况。
当使用搜索引擎时:听起来您正在寻找子字符串,这意味着您应该使用您最喜欢的搜索引擎为您的文件编制索引,最好是您可以自定义的搜索引擎(lucene、terrier 等)。这里需要的技术是索引三元组,即:所有 3 个字符的组合都必须被索引。 F.ex.: 'foobar' 将生成 'foo'、'oob'、'oba' 和 'bar'。搜索时,您希望对查询执行相同的操作,并使用所有这些三元组的 AND 发出搜索引擎查询。 (这将在文档的发布列表上运行合并连接,这将返回他们的 ID 或您放入发布列表中的任何内容)。
或者,您可以实现后缀数组并对文件进行一次索引。如果您想搜索短的(1-2 个字符)子字符串,这将提供更多的灵 active ,但就索引而言更难维护。 (在 CWI/Amsterdam 有一些关于快速索引后缀数组的研究)
当您只想搜索几次时,要使用的算法是 Boyer-Moore(我通常使用 Boyer-moore-sunday,如 [Graham A. Stephen,String Search] 中所述)或编译的 DFA(您可以从 NFA 构造它们,这更容易制作)。然而,这只会给你带来很小的速度提升,原因很简单,磁盘 IO 可能是你的瓶颈,并且比较你需要解码的一堆字节是相当快的。
您可以做出的最大改进不是逐行读取文件,而是分块读取。如果可以的话,您应该将 NTFS 配置为使用 64 KB 的 block 大小,并以 64 KB 的倍数读取文件 - 认为单次读取 4 MB 或更多。我什至建议使用异步 IO,以便您可以同时读取和处理(以前读取的数据)。如果你做对了,那应该已经在大多数现代硬件上为你提供了 10 MB 的瞬间实现。
最后但并非最不重要的一点是,在整个信息检索过程中使用的巧妙技巧也是使用快速压缩算法来压缩数据。由于磁盘 IO 比内存/CPU 操作慢,这也可能有帮助。 Google 的 Snappy 压缩器是快速压缩算法的一个很好的例子。
关于c# - 在文本文件中搜索字符串的更快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14827350/