什么是最有效(读取时间)字符串搜索方法？(C#)

Question

我发现我的程序正在搜索许多冗长的字符串(20,000+),试图找到一个特定的独特短语.

在C#中执行此操作的最有效方法是什么？

下面是当前的代码,它的工作原理如下:

1. 搜索从startPos开始,因为目标区域从一开始就有所消除
2. 它循环遍历字符串,在每一步它检查该点的子字符串是否以startMatchString开头,这是指示已找到目标字符串的开头.(目标字符串varys的长度).
3. 从这里创建一个新的子字符串(切掉标记目标字符串开头的11个字符)并搜索endMatchString

我已经知道这是一个非常复杂且可能非常无效的算法.有什么更好的方法来实现相同的结果？

string result = string.Empty;    
for (int i = startPos; i <= response.Length - 1; i++)
{
   if (response.Substring(i).StartsWith(startMatchString))
   {
       string result = response.Substring(i).Substring(11);
       for (int j = 0; j <= result.Length - 1; j++)
       {
           if (result.Substring(j).StartsWith(endMatchString))
           {
               return result.Remove(j)
           }
       }
   }
}
return result;

Answer 1

您可以使用String.IndexOf,但请确保使用StringComparison.Ordinal,否则可能会慢一个数量级.

private string Search2(int startPos, string startMatchString, string endMatchString, string response) {
    int startMarch = response.IndexOf(startMatchString, startPos, StringComparison.Ordinal);
    if (startMarch != -1) {
        startMarch += startMatchString.Length;
        int endMatch = response.IndexOf(endMatchString, startMarch, StringComparison.Ordinal);
        if (endMatch != -1) { return response.Substring(startMarch, endMatch - startMarch); }
    }
    return string.Empty;
}

在大约183 KB文件的40%处搜索1000次字符串大约需要270毫秒.没有StringComparison.Ordinal,它花了大约2000毫秒.
使用您的方法搜索一次花费超过60秒,因为它在每次迭代时创建一个新字符串(O(n)),使您的方法为O(n ^ 2).

Answer 2

有很多算法,

• 博耶和摩尔
• 星期日
• 克努特莫里斯普拉特
• 拉宾,卡普

我建议使用简化的Boyer-Moore,名为Boyer-Moore-Horspool.

C代码出现在维基百科上.对于java代码看看

http://www.fmi.uni-sofia.bg/fmi/logic/vboutchkova/sources/BoyerMoore_java.html

关于这些的一篇很好的文章可以在http://www.ibm.com/developerworks/java/library/j-text-searching.html下 找到.

如果你想使用内置的东西去正则表达式.

Answer 3

这取决于你想要在字符串中找到什么.如果您正在寻找特定的序列IndexOf/Contains是快速的,但如果您正在寻找通配符模式,Regex则针对此类搜索进行了优化.