过滤器的IEnumerable <string>不需要的字符串

编辑：我已经收到了一些非常好的建议，我将试图通过他们的工作，并接受一个答案在某些时候过滤器的IEnumerable <string>不需要的字符串

我有一个字符串（800K）的大名单，我想要在尽可能快的时间内过滤不需要的单词列表（最终亵渎但可能是任何东西）。

结果我最终希望看到的将是一个清单，如

Hello,World,My,Name,Is,Yakyb,Shell

将被核对

Hell,Heaven.

到目前为止我的代码是后成为

World,My,Name,Is,Yakyb

var words = items 
      .Distinct() 
      .AsParallel() 
      .Where(x => !WordContains(x, WordsUnwanted)); 

public static bool WordContains(string word, List<string> words) 
    { 
     for (int i = 0; i < words.Count(); i++) 
     { 
      if (word.Contains(words[i])) 
      { 
       return true; 
      } 
     } 
     return false; 
    }

这是目前需要约2.3秒（9.5瓦/平行）来处理800k字，作为一个关闭是没有什么大不了的。然而，作为一个学习过程，还有更快的处理方式吗？

的不受欢迎的词汇表是100个字的长
没有的话包含标点符号或空格注意消除重复所有列表中

一步

一步，看是否与阵列工作更快（它不）有趣的改变参数字为字符串[]使它慢25％
步骤添加进行AsParallel（）减少的时间来〜2.3秒

来源

2013-02-22 RoughPlace

是否要保留输入中的订单和/或重复项？ – dtb 2013-02-22 22:36:41

'shell'也会消失还是过滤词只是在开头？ – keyboardP 2013-02-22 22:41:24

你真的想按照你方法的建议（'word.contains'）去除单词部分位于“不想要的单词”列表中的单词吗？ – 2013-02-22 22:45:08

尝试使用名为Except的方法。

http://msdn.microsoft.com/en-AU/library/system.linq.enumerable.except.aspx

var words = new List<string>() {"Hello","Hey","Cat"}; 
var filter = new List<string>() {"Cat"}; 

var filtered = words.Except(filter);

而且怎么样：

var words = new List<string>() {"Hello","Hey","cat"}; 
var filter = new List<string>() {"Cat"}; 
// Perhaps a Except() here to match exact strings without substrings first? 
var filtered = words.Where(i=> !ContainsAny(i,filter)).AsParallel();  
// You could experiment with AsParallel() and see 
// if running the query parallel yields faster results on larger string[] 
// AsParallel probably not worth the cost unless list is large 
public bool ContainsAny(string str, IEnumerable<string> values) 
{ 
    if (!string.IsNullOrEmpty(str) || values.Any()) 
    { 
     foreach (string value in values) 
     { 
      // Ignore case comparison from @TimSchmelter 
      if (str.IndexOf(value, StringComparison.OrdinalIgnoreCase) != -1) return true; 

      //if(str.ToLowerInvariant().Contains(value.ToLowerInvariant())) 
      // return true; 
     } 
    } 

    return false; 
}

来源

2013-02-22 22:37:13 Jeremy

您是否有关于Except的Big-O性能的信息？我在MSDN上没有看到任何内容。 – 2013-02-22 22:38:09

'Except'可能不是他想使用的，因为它只匹配精确的字符串，而不匹配子字符串。 – 2013-02-22 22:39:37

反射器或使用共享源来查看它在底层做了什么。 – Jeremy 2013-02-22 22:39:48

啊，从 “坏” 名单过滤根据比赛的话。这是一个已经测试了许多程序员的consbreastution的clbuttic问题。我的伴侣从斯肯索普写了一篇论文。

你真正想要避免的是一个解决方案，它测试O（lm）中的单词，其中l是要测试的单词的长度，m是不良单词的数量。为了做到这一点，你需要一个解决方案，而不是循环不良的单词。我以为正则表达式可以解决这个问题，但我忘记了典型的实现有一个内部的数据结构，每次交替都会增加。正如其他解决方案之一所说，Aho-Corasick是这样做的算法。标准执行找到所有匹配，因为您可以在第一场比赛中进行救援，所以您的效率会更高。我认为这提供了一个理论上最佳的解决方案。

来源

2013-02-22 22:45:01 bmm6o

我很想看看我能否想出一个更快的方式来做到这一点 - 但我只管理了一个小优化。这是为了检查在另一个字符串中出现的字符串的索引，因为它首先看起来比'contains'稍快，然后让你指定大小写敏感性（如果这对你有用）。

下面包括的是我写的一个测试类 - 我已经使用了> 1百万字，并且在所有情况下都使用区分大小写的测试进行搜索。它测试你的方法，也是我试图建立的一个正则表达式。你可以自己尝试一下，看看时机;正则表达式不能像您提供的方法一样快，但是我可能会错误地构建它。我在（word1 | word2 ...）之前使用（？i）来指定正则表达式中的大小写不敏感（我想知道如何优化它 - 它可能会遭受经典的回溯问题！）。

随着更多“不需要”的单词被添加，搜索方法（无论是正则表达式还是提供的原始方法）似乎都会进步缓慢。

反正 - 希望这个简单的测试可以帮助你一下：

class Program 
{ 


    static void Main(string[] args) 
    { 
     //Load your string here - I got war and peace from project guttenburg (http://www.gutenberg.org/ebooks/2600.txt.utf-8) and loaded twice to give 1.2 Million words 
     List<string> loaded = File.ReadAllText(@"D:\Temp\2600.txt").Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries).ToList(); 

     List<string> items = new List<string>(); 
     items.AddRange(loaded); 
     items.AddRange(loaded); 

     Console.WriteLine("Loaded {0} words", items.Count); 

     Stopwatch sw = new Stopwatch(); 

     List<string> WordsUnwanted = new List<string> { "Hell", "Heaven", "and", "or", "big", "the", "when", "ur", "cat" }; 
     StringBuilder regexBuilder = new StringBuilder("(?i)("); 

     foreach (string s in WordsUnwanted) 
     { 
      regexBuilder.Append(s); 
      regexBuilder.Append("|"); 
     } 
     regexBuilder.Replace("|", ")", regexBuilder.Length - 1, 1); 
     string regularExpression = regexBuilder.ToString(); 
     Console.WriteLine(regularExpression); 

     List<string> words = null; 

     bool loop = true; 

     while (loop) 
     { 
      Console.WriteLine("Enter test type - 1, 2, 3, 4 or Q to quit"); 
      ConsoleKeyInfo testType = Console.ReadKey(); 

      switch (testType.Key) 
      { 
       case ConsoleKey.D1: 
        sw.Reset(); 
        sw.Start(); 
        words = items 
         .Distinct() 
         .AsParallel() 
         .Where(x => !WordContains(x, WordsUnwanted)).ToList(); 

        sw.Stop(); 
        Console.WriteLine("Parallel (original) process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count); 
        words = null; 
        break; 

       case ConsoleKey.D2: 
        sw.Reset(); 
        sw.Start(); 
        words = items 
         .Distinct() 
         .Where(x => !WordContains(x, WordsUnwanted)).ToList(); 

        sw.Stop(); 
        Console.WriteLine("Non-Parallel (original) process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count); 
        words = null; 
        break; 

       case ConsoleKey.D3: 
        sw.Reset(); 
        sw.Start(); 
        words = items 
         .Distinct() 
         .AsParallel() 
         .Where(x => !Regex.IsMatch(x, regularExpression)).ToList(); 

        sw.Stop(); 
        Console.WriteLine("Non-Compiled regex (parallel) Process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count); 
        words = null; 
        break; 

       case ConsoleKey.D4: 
        sw.Reset(); 
        sw.Start(); 
        words = items 
         .Distinct() 
         .Where(x => !Regex.IsMatch(x, regularExpression)).ToList(); 

        sw.Stop(); 
        Console.WriteLine("Non-Compiled regex (non-parallel) Process took {0}ms and found {1} matching words", sw.ElapsedMilliseconds, words.Count); 
        words = null; 
        break; 

       case ConsoleKey.Q: 
        loop = false; 
        break; 

       default: 
        continue; 
      } 
     } 
    } 

    public static bool WordContains(string word, List<string> words) 
    { 
     for (int i = 0; i < words.Count(); i++) 
     { 
      //Found that this was a bit fater and also lets you check the casing...! 
      //if (word.Contains(words[i])) 
      if (word.IndexOf(words[i], StringComparison.InvariantCultureIgnoreCase) >= 0) 
       return true; 
     } 
     return false; 
    } 
}

来源

2013-02-23 12:29:07 Jay

几件事情

维修1（简单好用）： 我能加快运行（分数）通过在Distinct方法上使用HashSet。

var words = new HashSet<string>(items) //this uses HashCodes 
     .AsParallel()...

维修2（熊与我;））： 关于@添的评论中，含有可能无法为你提供足够的搜索列入黑名单的话。例如竹下是一个街道名称。

你已经确定你想要这个词的有限状态（又名Stemmed）。例如苹果，我们会把它当作苹果。为此，我们可以使用干扰算法，如Porter Stemmer。

如果我们想要词干，那么我们可能不需要做Contains（x），我们可以使用equals（x）或甚至更好地比较HashCodes（最快的方法）。

var filter = new HashSet<string>(
    new[] {"hello", "of", "this", "and", "for", "is", 
     "bye", "the", "see", "in", "an", 
     "top", "v", "t", "e", "a" }); 

var list = new HashSet<string> (items) 
      .AsParallel() 
      .Where(x => !filter.Contains(new PorterStemmer().Stem(x))) 
      .ToList();

这将比较的话对他们的哈希码，INT == INT。

使用stemmer并没有减慢速度，因为我们用HashSet补充了它（对于过滤的列表，bigO为1）。这返回了一个更大的结果列表。

我使用位于Lucene.Net代码波特施特默尔，这不是线程因此，我们新的每次

问题与维修2时，维修2A：与大多数自然语言处理，它并不简单。当

这个词的屏蔽词“GrrArgh”（其中格儿和哎呀被取缔）
单词拼写故意错“弗兰克•”组合会发生什么，但仍然具有意义的禁止同单词（对不起，对于论坛ppl）
该单词拼写为空格“G rr”。
你带字是不是一个单词，短语，例如穷人：

随着论坛“一桶的儿子”，他们利用人类实现这些差距。

或者引入白名单（由于您提到了bigO，我们可以说这会导致2n^2的性能降低，因为我们为每个项目做了2个列表，不要忘记删除主导constaints，如果我没有记错你留下n^2，但我有点生锈我的bigO）

来源

2013-02-24 19:20:33 dbones

更改您的WordContains方法使用一个单一的Aho-Corasick搜索，而不是〜100包含调用（和当然只是初始化Aho-Corasick搜索树）。

你可以在这里找到一个开源的实现http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=12383。

在启动StringSearch类后，您将为每个800k字符串调用方法public bool ContainsAny(string text)。

无论您不想要的单词列表多长时间，单个调用都将花费O（字符串的长度）时间。

来源

2013-02-24 20:39:44

过滤器的IEnumerable <string>不需要的字符串

回答

相关问题