查找字符串是否包含给定数组中的任何字符串的快速算法

我有一个包含约50个关键字和约50000个字符串的列表。我检查每个字符串是否包含至少一个关键字。我对匹配关键字或匹配关键字的数量不感兴趣。我只想要尽可能快地回到“真”或“假”的位置。查找字符串是否包含给定数组中的任何字符串的快速算法

所以，我敢打赌，有一个算法，在那里，远远胜过我目前的LINQ版本：

class MyEnumerableExtension 
{ 
    public static bool ContainsAny(this string searchString, IEnumerable<string> keywords) 
    { 
     return keywords.Any(keyword => searchString.Contains(keyword)) 
    } 
} 

bool foundAny = "abcdef".ContainsAny(new string[] { "ac", "bd", "cd" });

来源

2010-11-18 VVS

是不是跟你今天的其他问题Efficient algorithm for finding all keywords in a text一样，只是修改为一旦找到匹配就返回？

来源

2010-11-18 13:43:11

不，我有两个不同的问题，一个是在给定关键字列表中查找包含任何关键字的所有字符串;另一个是使用另一个关键字标记这些找到的字符串关键字列表。这些列表不同，目的不同。 – VVS 2010-11-18 13:47:58

好的，但解决方案在两个地方都是相同的algorthm（在这种情况下，一旦找到一个匹配项就会返回）。 – 2010-11-18 13:53:13

哎呦，我应该读直到结束。我认为你是对的，我可以修改算法，找到一个关键字后返回。因为我只需要构建关键字树，这应该是一个非常快速的解决方案。 – VVS 2010-11-18 13:53:51

有multiple algorithms搜索一组子的文字。

来源

2010-11-18 13:42:15 Carra

呦可以实施Knuth-Morris-Pratt algorithm。

来源

2010-11-18 13:42:33

搜索一个单词。有更好的搜索任何一个集合的算法。参见Wikipedia http://en.wikipedia.org/wiki/String_searching_algorithm #Algorithms_using_finite_set_of_patterns – 2010-11-18 13:44:36

快速分析显示您正在迭代搜索关键字。如果您可以一次搜索所有关键字，那么您的算法应该有一个全面的改进。一个正则表达式可以做到这一点，并将其与“编译”选项相结合，你应该开始看到性能增加（因为它将单一传递所有关键字的字符串）。但是，如果你有几个关键字，它只会对你有益。这里有一个快速的想法可以帮助你，但是请注意，我没有实际测试过你的算法。

 string[] keywords = { "ac", "bd", "cd" }; 
     string[] tosearch = { "abcdef" }; 
     string pattern = String.Join("|", keywords); 
     Regex regex = new Regex(pattern, RegexOptions.Compiled); 
     foundAny = regex.IsMatch(String.Join("|", tosearch));

另外请注意，只要您的关键字不包含任何正则表达式特殊字符（和您的搜索字符串不包含管道符号工作的。但是，特殊字符可以用转义序列来克服，而搜索字符串不必像我做的那样加入。

来源

2010-11-18 14:03:06 Les

查找字符串是否包含给定数组中的任何字符串的快速算法

回答

相关问题