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's Friedl的书，Mastering Regular Expressions寻求有关构建高效正则表达式(例如，无回溯)的帮助。

您可能还想查阅好的算法文本。我偏爱 Robert Sedgewick 的 Algorithms在其 various incarnations ([C|C++|Java] 中的算法)