C＃高效的子串有很多投入

Question

假设我不想用了十几个外部库以上或代码，使多余的线（即清晰的代码，不代码高尔夫球代码），我可以做的比string.Contains更好处理一组输入字符串和一组关键字来检查？

显然，人们可以使用objString.Contains(objString2)做一个简单的子字符串检查。但是，在特殊情况下，有许多着名的算法能够做得比这更好，特别是在使用多个字符串的情况下。但是将这样的算法粘贴到我的代码中可能会增加长度和复杂性，所以我宁愿使用某种基于内置函数的快捷方式。

E.g.输入可以是字符串集合，正面关键字集合和负面关键字集合。输出将是第一批关键词的一个子集，所有这些关键词至少有1个肯定关键词，但是有0个否定关键词。

哦，请不要提及正则表达式作为建议的解决方案。

这可能是我的要求是相互排斥的（没有太多额外的代码，没有外部库或正则表达式，比String.Contains更好），但我想我会问。

编辑：

很多人只提供那些将被打多的使用智能调用包含愚蠢的改进，如果有的话。有些人试图更聪明地呼叫Contains，这完全忽略了我的问题。所以这里有一个解决问题的例子。 LBushkin的解决方案是提供解决方案的一个例子，它可能比标准包含的渐近式更好：

假设您有10,000个长度为5-15个字符，0个否定关键字（这似乎令人困惑）的正关键字和1个1,000,000字符串。检查1,000,000个字符的字符串是否至少包含1个肯定关键字。

我想一个解决方案是创建一个FSA。另一个是划分空间并使用散列。

Answer 1

那么，你可以调用一个字符串的Split（）方法。您可以使用Split（）将输入字符串拆分为单词数组，然后使用关键字对单词进行一对一检查。然而，我不知道是否或在什么情况下这比使用Contains（）更快。

Answer 2

如果添加此扩展方法：

public static bool ContainsAny(this string testString, IEnumerable<string> keywords) 
{ 
    foreach (var keyword in keywords) 
    { 
     if (testString.Contains(keyword)) 
      return true; 
    } 
    return false; 
} 

那么这就变成了一个一行语句：

var results = testStrings.Where(t => !t.ContainsAny(badKeywordCollection)).Where(t => t.ContainsAny(goodKeywordCollection)); 

这不一定是任何比做包含检查速度更快，但它会由于LINQ的结果流可以防止任何不必要的包含调用，所以可以有效地执行它们。此外，生成的代码是一行代码，非常好。

Answer 3

您对“负面和正面”关键词的讨论有点令人困惑 - 并且可以使用一些说明来获得更完整的答案。

与所有与性能有关的问题 - 您应该先编写简单的版本，然后对其进行配置以确定瓶颈的位置 - 这些可能不直观且难以预测。话说回来...

优化搜索的一种方法可能是（如果您总是搜索“单词” - 而不是可能包含空格的短语）可能会从您的字符串构建搜索索引。

搜索索引可以是排序数组（用于二进制搜索）或字典。一本字典可能会更快 - 这是因为字典内部带有O（1）查找的hashmaps，并且字典自然会消除搜索源中的重复值，从而减少需要执行的比较次数。

一般的搜索算法是：

对于您正在搜索对每个字符串：

• 拍摄正在内搜索字符串，并将其标记化到单个单词（由空格分隔）
• 填充搜索索引中的令牌（排序数组或字典）
• 在索引中搜索“否定关键字”（如果找到），跳至下一个搜索字符串
• 在索引中搜索您“积极关键字”，当一个人发现，将其添加到字典中，他们（你也可以跟踪的频率出现的字计数）

下面是一个使用的例子在C＃2.0排序后的数组和二进制搜索：

注：您可以切换从string[]到List<string>很轻松了，我留给你。

string[] FindKeyWordOccurence(string[] stringsToSearch, 
           string[] positiveKeywords, 
           string[] negativeKeywords) 
{ 
    Dictionary<string,int> foundKeywords = new Dictionary<string,int>(); 
    foreach(string searchIn in stringsToSearch) 
    { 
     // tokenize and sort the input to make searches faster 
     string[] tokenizedList = searchIn.Split(' '); 
     Array.Sort(tokenizedList); 

     // if any negative keywords exist, skip to the next search string... 
     foreach(string negKeyword in negativeKeywords) 
      if(Array.BinarySearch(tokenizedList, negKeyword) >= 0) 
       continue; // skip to next search string... 

     // for each positive keyword, add to dictionary to keep track of it 
     // we could have also used a SortedList, but the dictionary is easier 
     foreach(string posKeyword in positiveKeyWords) 
      if(Array.BinarySearch(tokenizedList, posKeyword) >= 0) 
       foundKeywords[posKeyword] = 1; 
    } 

    // convert the Keys in the dictionary (our found keywords) to an array... 
    string[] foundKeywordsArray = new string[foundKeywords.Keys.Count]; 
    foundKeywords.Keys.CopyTo(foundKeywordArray, 0); 
    return foundKeywordsArray; 
} 

下面是一个使用C＃中的基于字典的指数和LINQ 3.0版本：

注：这是不是最LINQ-Y办法做到这一点，我可以用联盟（）和SelectMany（）将整个算法写成一个大的LINQ语句 - 但我觉得这样更容易理解。

public IEnumerable<string> FindOccurences(IEnumerable<string> searchStrings, 
              IEnumerable<string> positiveKeywords, 
              IEnumerable<string> negativeKeywords) 
    { 
     var foundKeywordsDict = new Dictionary<string, int>(); 
     foreach(var searchIn in searchStrings) 
     { 
      // tokenize the search string... 
      var tokenizedDictionary = searchIn.Split(' ').ToDictionary(x => x); 
      // skip if any negative keywords exist... 
      if(negativeKeywords.Any(tokenizedDictionary.ContainsKey)) 
       continue; 
      // merge found positive keywords into dictionary... 
      // an example of where Enumerable.ForEach() would be nice... 
      var found = positiveKeywords.Where(tokenizedDictionary.ContainsKey) 
      foreach (var keyword in found) 
       foundKeywordsDict[keyword] = 1; 
     } 
     return foundKeywordsDict.Keys; 
    } 

Answer 4

首先摆脱所有包含负面词的字符串。我会建议使用Contains方法来做到这一点。我认为Contains（）比分裂，排序和搜索更快。

Answer 5

在我看来，做到这一点的最好方法是把你的匹配字符串（正面和负面）和计算他们的散列。然后通过你的百万字符串计算n个哈希值（对于长度为5-15的字符串，你的情况是10），并匹配你的匹配字符串的哈希值。如果你得到散列匹配，那么你做一个实际的字符串比较来排除误报。有很多好方法可以通过按长度分段匹配字符串并根据特定存储桶的字符串大小创建散列来优化此方法。

所以你喜欢的东西：

IList<Buckets> buckets = BuildBuckets(matchStrings); 
int shortestLength = buckets[0].Length; 
for (int i = 0; i < inputString.Length - shortestLength; i++) { 
    foreach (Bucket b in buckets) { 
     if (i + b.Length >= inputString.Length) 
      continue; 
     string candidate = inputString.Substring(i, b.Length); 
     int hash = ComputeHash(candidate); 

     foreach (MatchString match in b.MatchStrings) { 
      if (hash != match.Hash) 
       continue; 
      if (candidate == match.String) { 
       if (match.IsPositive) { 
        // positive case 
       } 
       else { 
        // negative case 
       } 
      } 
     } 
    } 
} 

Answer 6

如果你真的只是寻找空间分隔的话，这个代码将是一个非常简单的实现：

static void Main(string[] args) 
    { 
     string sIn = "This is a string that isn't nearly as long as it should be " + 
      "but should still serve to prove an algorithm"; 
     string[] sFor = { "string", "as", "not" }; 
     Console.WriteLine(string.Join(", ", FindAny(sIn, sFor))); 
    } 

    private static string[] FindAny(string searchIn, string[] searchFor) 
    { 
     HashSet<String> hsIn = new HashSet<string>(searchIn.Split()); 
     HashSet<String> hsFor = new HashSet<string>(searchFor); 
     return hsIn.Intersect(hsFor).ToArray(); 
    } 

如果你只是想一个是/否的答案（正如我现在看到的情况可能是这种情况）还有另一种哈希集“重叠”的方法，可能更好地优化为：

private static bool FindAny(string searchIn, string[] searchFor) 
    { 
     HashSet<String> hsIn = new HashSet<string>(searchIn.Split()); 
     HashSet<String> hsFor = new HashSet<string>(searchFor); 
     return hsIn.Overlaps(hsFor); 
    } 

Answer 7

要优化Contains（），您需要正面/负面词语的树（或trie）结构。

这应该加快一切（O（n）与O（nm），n =字符串的大小，m =平均字大小）和代码是相对较小的容易的&。