什麼是最高效的（讀取時間）字符串搜索方法？ （C＃）

Question

我發現我的程序正在搜索大量冗長的字符串（20,000+），試圖找到一個特定的獨特短語。

在C＃中這樣做的最有效方法是什麼？

下面是當前的代碼，其工作原理是這樣的：

1. 搜索在startPos開始，因爲目標區域有些從一開始就
2. 它遍歷字符串，它會檢查，如果每個步驟中去除從那一點開始的子串從startMatchString開始，這是指示已經找到目標字符串的開始。 （目標字符串varys的長度）。
3. 從這裏創建一個新的子串（斬去標記目標字符串的開頭的11個字符）並搜索endMatchString

我已經知道，這是一個可怕的複雜和可能非常inefficent算法。 什麼是更好的方式來完成相同的結果？

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毫秒。
用你的方法搜索1次需要60秒，因爲它每次迭代都會創建一個新的字符串（O（n）），使得你的方法O（n^2）。

Answer 2

我會嘗試使用正則表達式，而不是我自己的滾動字符串搜索算法。您可以預編譯正則表達式以使其運行速度更快。

Answer 3

你可以使用正則表達式;它針對這種搜索和操作進行了優化。

您也可以嘗試的IndexOf ...

string result = string.Empty; 

if (startPos >= response.Length) 
    return result; 

int startingIndex = response.IndexOf(startMatchString, startPos); 
int rightOfStartIndex = startingIndex + startMatchString.Length; 

if (startingIndex > -1 && rightOfStartIndex < response.Length) 
{ 
    int endingIndex = response.IndexOf(endMatchString, rightOfStartIndex); 
    if (endingIndex > -1) 
     result = response.Substring(rightOfStartIndex, endingIndex - rightOfStartIndex); 
} 

return result; 

Answer 4

這取決於你想在字符串中找到什麼。如果你正在尋找一個特定的序列IndexOf/Contains是快速的，但如果你正在尋找通配符Regex爲這種搜索進行了優化。

Answer 5

對於很長的字符串，您無法擊敗Boyer-Moore搜索算法。這比我可能試圖在這裏解釋更復雜，但CodeProject網站有一個很好的文章。

Answer 6

正如之前所說的正則表達式是你的朋友。 你可能想看看RegularExpressions.Group。 這樣你可以命名匹配結果集的一部分。

Here is an example

Answer 7

有算法一大堆，

• 博耶和摩爾
• 週日
• 克努特莫里斯普拉特
• 拉賓，卡普

我會建議你簡稱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 8

下面是一個使用IndexOf一個例子（提防：從我的頭頂寫的，沒有測試）：

int skip = 11; 
int start = response.IndexOf(startMatchString, startPos); 
if (start >= 0) 
{ 
    int end = response.IndexOf(startMatchString, start + skip); 
    if (end >= 0) 
     return response.Substring(start + skip, end - start - skip); 
    else 
     return response.Substring(start + skip); 
} 
return string.Empty;