c#搜索大文本文件

Question

我正在尝试优化搜索大文本文件(300-600mb)中的字符串.使用我目前的方法,它需要太长时间.

目前我一直在使用IndexOf搜索字符串,但是花费的时间太长(20秒)来为每个字符串构建一个索引.

如何优化搜索速度？我试过Contains()但这也很慢.有什么建议？我正在考虑正则表达式匹配,但我没有看到有显着的速度提升.也许我的搜索逻辑是有缺陷的

例

while ((line = myStream.ReadLine()) != null)
{
    if (line.IndexOf(CompareString, StringComparison.OrdinalIgnoreCase) >= 0)
    {
        LineIndex.Add(CurrentPosition);
        LinesCounted += 1;
    }
}

Answer 1

您正在使用的强力算法在O(nm)时间内执行,其中n是要搜索的字符串的长度,m是您要查找的子字符串/模式的长度.您需要使用字符串搜索算法:

• 我认为Boyer-Moore是"标准":http: //en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

• 但是还有更多:http: //www-igm.univ-mlv.fr/~lecroq/string/

• 包括Morris-Pratt:http: //www.stoimen.com/blog/2012/04/09/computer-algorithms-morris-pratt-string-searching/

• 和Knuth-Morris-Pratt:http: //en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

但是,使用经过精心设计的正则表达式可能就足够了,具体取决于您要查找的内容.请参阅Jeffrey的Friedl 's tome,掌握正则表达式,以获得有关构建高效正则表达式的帮助(例如,无回溯).

您可能还想查阅一个好的算法文本.我偏爱罗伯特·塞奇威克的算法在其各种化身(算法在[C | C++ | Java的])

Answer 2

不幸的是，我不认为直接用 C# 可以做很多事情。

我发现 Boyer-Moore 算法对于这项任务来说非常快。但我发现没有办法让它像 一样快IndexOf。我的假设是，这是因为它IndexOf是在手动优化的汇编程序中实现的，而我的代码在 C# 中运行。

您可以在文章Fast Text Search with Boyer-Moore中查看我的代码和性能测试结果。