具有许多输入的 C# 高效子串

Question

假设我不想使用外部库或十几行额外的代码(即清晰的代码，不代码高尔夫代码)，我可以比 string.Contains 更好地处理输入字符串集合和要检查的关键字集合？

显然，可以使用 objString.Contains(objString2) 进行简单的子字符串检查。然而，有许多著名的算法在特殊情况下可以做得比这更好，尤其是在处理多个字符串的情况下。但是将这样的算法插入我的代码中可能会增加长度和复杂性，因此我宁愿使用某种基于内置函数的快捷方式。

例如输入将是字符串的集合、肯定关键字的集合和否定关键字的集合。输出将是第一个关键字集合的子集，所有这些关键字至少有 1 个肯定关键字但有 0 个否定关键字。

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

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

编辑:

很多人只提供愚蠢的改进，如果有的话，这些改进不会比智能使用的 contains 调用好很多。有些人试图更智能地调用 Contains，这完全忽略了我的问题。所以这是一个尝试解决的问题示例。 LBushkin 的解决方案是某人提供的解决方案的一个示例，该解决方案可能渐近地优于标准包含:

假设您有 10,000 个长度为 5-15 个字符的肯定关键字、0 个否定关键字(这似乎让人感到困惑)和 1 个 1,000,000 字符串。检查1,000,000字符串是否包含至少1个肯定关键字。

我认为一种解决方案是创建一个 FSA。另一个是分隔空格并使用哈希。

Answer 1

您对“否定和肯定”关键字的讨论有些困惑 - 可以通过一些澄清来获得更完整的答案。

与所有与性能相关的问题一样 - 您应该首先编写简单版本，然后对其进行概要分析以确定瓶颈所在 - 这些问题可能不直观且难以预测。话虽如此……

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

搜索索引可以是排序数组(用于二进制搜索)或字典。字典可能会更快 - 因为字典在内部是具有 O(1) 查找的 HashMap ，而且字典会自然地消除搜索源中的重复值 - 从而减少您需要执行的比较次数。

一般的搜索算法是:

对于您要搜索的每个字符串:

• 获取您正在搜索的字符串并将其标记为单个单词(以空格分隔)
• 将标记填充到搜索索引(排序数组或字典)
• 在索引中搜索您的“否定关键字”，如果找到，则跳至下一个搜索字符串
• 在索引中搜索您的“正面关键词”，找到后将其添加到字典中(您还可以跟踪该词出现的频率)

这是一个在 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# 3.0 中使用基于字典的索引和 LINQ 的版本:

注意:这不是最符合 LINQ 的方法，我可以使用 Union() 和 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;
    }