加快字符串搜索算法

我用这简单的算法搜索文件的一些文字和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

加快字符串搜索算法

回答

相关问题