過濾器的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>不需要的字符串

回答

相關問題