加快字符串搜索算法

我用這簡單的算法搜索文件的一些文字和taging所在的頁面，我發現它加快字符串搜索算法

for (int i = 1; i <= a.PageCount; i++) 
{ 
    Buf.Append(a.Pages[i].Text); 
    String contain = Buf.ToString(); 
    if (contain != "") 
    { 
     // Inside is dictionary of keys and value contain page where I found it 
     foreach (KeyValuePair<string, List<string>> pair in inside) 
     { 
       if (contain.Contains(pair.Key)) 
        inside[pair.Key].Add((i).ToString()); 
     } 
    } 

    Buf.Clear(); 
}

我都沒有問題，但是當我在700多頁的文檔搜索而我正在尋找超過500個按鍵，它的速度非常慢，需要大約1-2分鐘才能通過，有什麼辦法可以加速它？我正在使用c＃

謝謝！

來源

2012-02-10 Martin Ch

什麼樣的文件是？你能開始確定什麼鍵實際上在整個文件中，然後在逐頁的基礎上搜索那些鍵？ – 2012-02-10 21:27:45

它的pdf文件，但它沒有關係的文件格式，它的產品目錄和一些頁面包含產品類型的表 - 我需要創建索引的所有鍵 - 它們在哪裏 - 他在頁面 – 2012-02-10 21:30:24

的幾點：

擺脫Buf;只需將a.Pages[i].Text直接分配給contain：
inside[pair.Key]浪費時間查找與該密鑰關聯的值;浪費時間是因爲你在pair.Value中有更便宜的參考。
如果你有一個整數值列表，爲什麼你將它們存儲爲字符串？

示例代碼：

for (int i = 1; i <= a.PageCount; i++) 
{ 
    String contain = a.Pages[i].Text 
    if (contain != "") 
    { 
     // Inside is dictionary of keys and value contain page where I found it 
     foreach (KeyValuePair<string, List<int>> pair in inside) 
     { 
      if (contain.Contains(pair.Key)) 
       pair.Value.Add(i); 
     } 
    } 
}

最後，確保Pages事實上確實使用基於一個指標。集合更通常是零索引。

編輯因爲Pages是一本字典：

foreach (KeyValuePair<int, Page> kvp in a.Pages) 
{ 
    string contain = kvp.Value.Text; 
    if (contain == "") 
     continue; 
    foreach (KeyValuePair<string, List<int>> pair in inside) 
     if (contain.Contains(pair.Key)) 
      pair.Value.Add(kvp.Key); 
}

多少次您的時間，第一個代碼示例？時間可能因許多外部因素而異。一個方法的單次運行比另一個單一運行更快或更慢的事實並沒有真正地告訴你很多，特別是因爲我提出的建議可能無法解決大部分問題。

正如別人指出的，主要問題是，你打電話contain.Contains(pair.Key) 35萬次;這可能是你的瓶頸。您可以剖析該方法以確定是否屬實。如果爲爲真，那麼像可變變量所建議的Rabin Karp算法可能是您最好的選擇。

來源

2012-02-10 21:46:39 phoog

我試過了，但花了比以前更長的時間，我不知道爲什麼。頁面是字典類型，是的，它的頁面來自pdfLibNet，它們的索引從1 – 2012-02-10 21:59:45

@MartinCh如果它是一個字典類型，那麼你可以使用「foreach（KeyValuePair <...'在那裏，雖然好處是更小 - 你節省了700查找而不是350K。 – phoog 2012-02-10 22:06:07

謝謝，經過我運行代碼分析後，我發現，那Pages []。Text佔用了大約89％的處理時間，所以出現主要問題 – 2012-02-10 22:23:05

[

編輯：下面是無關緊要的，因爲你是在循環結束時結算BUF（但請注意，你並不真的需要BUF，string pageText = a.Pages[i].Text是你所需要的）

什麼是Buf？你已經

Buf.Append(a.Pages[i].Text);

難道不是強制Contains通過規模越來越大串看？我很驚訝你沒有耗盡700頁的內存。

]

有更有效的方式，看是否any of a set of strings出現在另一個string。例如，您可以準備密鑰的樹形結構，因此您不必多次進行比較。

見Rabin-Karp Algorithm

一定要考慮現有的第三方庫，必須有一些。

來源

2012-02-10 21:28:34

清除Buf在最後循環的每次迭代（在底部） – hatchet 2012-02-10 21:33:20

我假設'Buf'是一個StringBuilder。它在每次迭代中都被清除，因此除了減慢程序速度外，它什麼都不做。 – dtb 2012-02-10 21:33:22

謝謝，糾正我的答案。 – 2012-02-10 21:35:08

我沒有700頁來進行測試，但你可以嘗試使用正則表達式：

var s = Stopwatch.StartNew(); 
var r = new Regex(string.Join("|", from x in inside select Regex.Escape(x.Key))); 

for (int i = 1; i <= a.PageCount; i++) 
{ 
    foreach (Match match in r.Matches(a.Pages[i].Text)) 
    { 
     inside[match.Value].Add(i.ToString()); 
    } 
} 

Console.WriteLine(s.Elapsed);

來源

2012-02-10 21:29:59 dtb

他有很多搜索關鍵。即使對於一個單一的，我懷疑'正則表達式'可以更快的非通配符匹配，但我可能是錯的。 – 2012-02-10 21:41:28

我試過了 - 正則表達式需要126秒，我的版本93秒 – 2012-02-10 21:50:17

標準性能/調試程序 - 註釋掉的代碼和測量件。一次添加一個，直到它變得糟糕。這可能是你的問題領域。例如，您可以從評論整個foreach開始。

它看起來像有一些可能複雜/昂貴的對象在使用 - 內部，Buf等。註釋掉這些使用並將它們一次一個放回去。

來源

2012-02-10 21:33:30 n8wrl

似乎沒有必要 - 有500個密鑰和700個頁面，他的算法對一個文本頁面進行了350,000次搜索。這可能是時間正在採取的時間。 – hatchet 2012-02-10 21:40:49

加快字符串搜索算法

回答

相關問題