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是您要查找的子字符串/模式的长度。您需要使用字符串搜索算法

莫里斯-摩尔是“标准”，我认为：http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

• But还有很多：http://www-igm.univ-mlv.fr/~lecroq/string/

• including

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

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

但是，根据您要查找的内容，使用精心编制的正则表达式可能就足够了。参见Jeffrey's Friedl的大部头，以获得有关构建高效正则表达式的帮助(例如，无回溯)。

您可能还想参考一个好的算法文本。我偏爱Robert Sedgewick的 in various incarnations (C|C++|Java中的算法)

Answer 2

不幸的是，我不认为在C#中你可以做很多事情。

我发现Boyer-Moore算法对于这个任务来说非常快。但我发现，即使是这样，也无法像IndexOf那样快。我的假设是，这是因为我的代码在C#中运行时，IndexOf是在手工优化的汇编程序中实现的。

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

Answer 3

你看过这些问题(和答案)吗？

• Processing large text file in C#
• Is there a way to read large text file in parts?
• Matching a string in a Large text file?

如果你想做的只是阅读文本文件，那么现在这样做似乎是可行的。其他想法：

• 如果可以对数据进行预排序，例如当数据插入到文本文件中时，这可能会有所帮助。
• 您可以将数据插入数据库并根据需要进行查询。
• 您可以使用哈希表