加快字符串搜索算法

本文关键字：搜索算法 字符串 | 更新日期: 2023-09-27 18:24:00

我使用这个简单的算法来搜索文档中的一些文本，并标记我在哪个页面上找到它

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#

谢谢！

加快字符串搜索算法

几点：

  • 去掉Buf；只需将CCD_ 2直接分配给CCD_
  • CCD_ 4浪费时间查找与该密钥相关联的值；时间被浪费了，因为在CCD_ 5中对该对象的引用要便宜得多
  • 如果您有一个整数值列表，为什么要将它们存储为字符串

样本代码：

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实际上使用了基于一的索引。集合通常为零索引。

EDIT因为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)打了350000次电话；这可能是你的瓶颈。您可以对该方法进行评测，以确定这是否属实。如果是真的，那么像Miserable Variable建议的Rabin Karp算法可能是你的最佳选择。

[[

编辑：以下内容无关紧要，因为您在循环结束时清除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算法

一定要考虑现有的第三方库，一定有一些。

我没有700页可供测试，但您可以尝试使用regex:

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);

标准性能/调试过程-注释掉您的代码和度量。一次添加一个，直到"变得糟糕"这很可能是你的问题所在。

例如，您可以从注释掉整个foreach开始。

看起来有一些可能复杂/昂贵的对象在使用中——内部、Buf等。注释掉这些对象的用法，然后一次放回一个。

相关文章：