查找字符串是否包含給定數組中的任何字符串的快速算法

我有一個包含約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

查找字符串是否包含給定數組中的任何字符串的快速算法

回答

相關問題