C＃：高效地搜索大字符串发生其他字符串

我正在使用C＃来连续搜索大字符串中的多个字符串“关键字”，这是大于4kb。这段代码不断循环，睡眠不会在保持合理的速度的同时减少足够的CPU使用。缓冲是关键字匹配方法。C＃：高效地搜索大字符串发生其他字符串

我发现了一些可能性，它们都具有相似的效率。

1）http://tomasp.net/articles/ahocorasick.aspx - 我没有足够的关键字使其成为最有效的算法。

2）正则表达式。使用实例级别，编译正则表达式。 - 提供比我需要的更多功能，效率不够。

3）String.IndexOf。 - 我需要做一个“智能”版本，因为它提供了足够的效率。循环访问每个关键字并调用IndexOf不会削减它。

有谁知道任何算法或方法，我可以用来实现我的目标？

2009-06-23 Jon Willis

拾遗从下面的评论，字符串的转换的回避信息，并保持在东西[字节数组]（http://stackoverflow.com/a/283648/512671）可能是最快的;并为字节数组实现一个定制的Boyer-Moore更快 – zanlok 2013-03-22 18:51:02

你是否一直在寻找相同的关键字？尝试Boyer-Moore。它需要对关键字进行一些预处理，但之后会获得速度。

来源

2009-06-23 08:27:00

我还没有尝试过，但你看过Rabin-Karp？显然它有一个糟糕的最坏情况复杂性，但通常相当不错。

你的关键词是什么样的？特别是，它们是否总是由空格（或类似的东西）分隔？如果是这样，你可以基本上查看字符串，一旦寻找“单词”，然后创建一个单词到该单词索引列表的映射，或者可能只对您感兴趣的关键字这样做。

如果您可以提供有关确切情况的更多详细信息（例如关键字，分隔符以及您需要的搜索结果），这将有所帮助。

来源

2009-06-23 08:23:23

我一直在试图利用Rabin-Karp。问题是，所有的实现都使用一个静态模式长度来加速他们的算法。我无法做到这一点，当我在没有恒定模式长度的情况下实现它时，计算时间呈指数增长。 – 2009-06-25 15:51:48

哦：我正在搜索的文本长度12286.我的模式始终是更短长度 - 从10到约50个字符的任意位置，只是转换为十六进制字符串的话。（前。BitConverter.ToString（ENCODING.GetBytes（“无后坐力”）））所有我需要的是知道我的任何图案出现在文本中。 – 2009-06-25 15:56:18

并且在这些单词之前和之后总是有空格吗？如果是这样，你可以迭代文本中的单词，并使用正常的HashSet 来检测每个单词是否是关键字？ – 2009-06-25 16:14:11

我开发了一个高效利用的IndexOf的这个问题：

A better way to replace many strings - obfuscation in C#

它使用的关键字的列表，并在字符串中的下一个位置。这样，您只需为每个关键字调用一次IndexOf，然后再为每次找到的匹配调用一次。当您替换大字符串中的关键字时，它非常有效，因为您可以从开始到结束处理字符串，而不是为每个关键字处理整个字符串。我不知道你为什么要寻找字符串中的关键字，以及你如何处理字符串，但也许这对你的情况可能有用。

来源

2009-06-23 08:39:14 Guffa

其实我之前必须解决这个问题，它有点儿有趣。我有20k的html页面，每个页面都有一个标题，并且希望所有其他页面上出现的标题链接到具有该标题的页面。听起来和你想要完成的事情非常相似。

该方法：

进程的文件的通过将其变成其中单词被确定为连续的字母数字序列与几个特殊字符{字，空白}的链接列表的文本，而空白就是导致下一个单词的一切。
对于我想链接到的页面的每个“标题”，重复步骤1中的过程。
然后将第1步中链接列表中节点的每个单词添加到二进制排序列表中。
现在，你只需要第2步走，从每一个标题链接列表中的第一个字，并寻求到从第3步二进制排序列表您可能会发现几命中，甚至软命中当一个字是复数，所以你可能你需要测试二进制列表中的几个起始节点。
将文档处理为步骤1中描述的表单后，通过插入新节点和/或修改空白值实际上非常容易修改。一旦完成，您只需遍历整个列表并将其全部转储到流中。

这听起来比现在要复杂得多，花了大约两天的时间才得到它的效果。

但是你解决它，有乐趣:)

来源

2010-04-13 16:13:03

我只是张贴这一个类似的线程，但它可能是更多的与此有关。

我做了类似的搜索，基本上找的约45K字节的文本内的长约10-50个字节的关键字。我搜索了超过900万个关键字的1900个关键字，因此尽可能快地获得这些关键字也是一个类似的优先事项。

因此，我发现使用.NET 4的最快方法是并行Regex IsMatch。

这里获得总场比赛的一个例子 -

needles.AsParallel ().Sum (l => Regex.IsMatch (haystack , Regex.Escape (l)) ? 1 : 0);

这适用于我的情况（上图），它比序的indexOf并行比较快55％，在我的测试至少在排序数据大小我的正在使用。我也想象只有在使用多核机器时才会提高速度。

如果有人可以找到更快的方法会感兴趣吗？

来源

2010-04-16 11:34:53 gary

C＃：高效地搜索大字符串发生其他字符串

回答

相关问题