4

編集：私はいくつかの非常に良い提案を受け取りました。それらを検討し、ある時点で回答を受け入れようとします

不要な単語のリスト（最終的には冒涜的ですが、何でもかまいません）を可能な限り迅速にフィルタリングしたい文字列（800k）の大きなリストがあります。

最終的に見たい結果は、次のようなリストになります

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

になるだろう

World,My,Name,Is,Yakyb

チェックされた後

Hell,Heaven.

これまでの私のコードは

 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;
    }

これは現在、800kワードを処理するのに約2.3秒（並列なしで9.5秒）かかりますが、これは1回限りのことであり、大したことではありません. しかし、学習プロセスとして、処理のより迅速な方法はありますか?

不要な単語のリストは 100 単語の長さです どの
単語にも句読点やスペースが含まれていません

  1. すべてのリストで重複を削除するための手順
  2. 配列の操作が速いかどうかを確認するステップ (そうではない) 興味深いことに、パラメーターの単語を文字列 [] に変更すると、25% 遅くなります
  3. AsParallel() を追加するステップにより、時間が ~2.3 秒に短縮されました
4

5 に答える 5

1

いくつかのこと

変更 1 (素晴らしくシンプル): Distinct メソッドで HashSet を使用することにより、実行を (わずかに) 高速化することができました。

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

Alteration 2 (Bear with me ;) ) : @Tim のコメントに関しては、contains ではブラック リストに記載されている単語を検索するのに十分な情報が得られない可能性があります。たとえば、竹下は通りの名前です。

単語の有限状態 (別名語幹) が必要であることは既に確認済みです。たとえば、Apple の場合、Apple として扱います。これを行うには、Porter Stemmer などのステミング アルゴリズムを使用できます。

単語をステム処理する場合は、Contains(x) を実行する必要がない場合があります。equals(x) を使用するか、HashCode をより適切に比較できます (最速の方法)。

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の単語を比較します。

ステマーを使用しても速度が低下することはありませんでした。これは、HashSet で補完したためです (フィルター処理されたリストの場合、bigO は 1 です)。これにより、結果のより大きなリストが返されました。

私は Lucene.Net コードにある Porter Stemmer を使用しています。これはスレッドセーフではないため、毎回新しいものを作成します。

変更 2、変更 2a の問題:ほとんどの自然言語処理と同様に、単純ではありません。いつ何が起こるか

  1. この単語は、禁止された単語「GrrArgh」の組み合わせです (Grr と Argh は禁止されています)。
  2. この単語は意図的に間違った「Frack」と綴られていますが、禁止された単語と同じ意味を持っています (フォーラムの参加者に申し訳ありません)。
  3. この単語は、スペース「G r r」でつづられます。
  4. あなたのバンドの言葉は単語ではなくフレーズです。悪い例: 「樽の息子」

フォーラムでは、人間を使用してこれらのギャップを埋めます。

または、ホワイト リストの導入が導入されます (bigO について言及しているとすれば、2n^2 のパフォーマンス ヒットがあると言えます。すべてのアイテムに対して 2 つのリストを実行しているため、先頭の制約を削除することを忘れないでください)。私の記憶が正しければ、あなたは n^2 のままですが、私の bigO は少し錆びています)

于 2013-02-24T19:20:33.837 に答える
1

WordContains~100 の Contains 呼び出しの代わりに単一の Aho-Corasick 検索を使用するようにメソッドを変更します(もちろん、Aho-Corasick 検索ツリーを 1 回だけ初期化します)。

オープンソースの実装はhttp://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=12383にあります。

クラスの初期化後、800k 文字列ごとにStringSearchメソッドを呼び出し ます。public bool ContainsAny(string text)

不要な単語のリストがどれだけ長くても、1 回の呼び出しには O(文字列の長さ) の時間がかかります。

于 2013-02-24T20:39:44.923 に答える
1

という方法を試してみてください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-22T22:37:13.633 に答える
0

ああ、「悪い」リストからの一致に基づいて単語をフィルタリングします。これは、多くのプログラマーの解釈をテストしてきた巧妙な問題です。スカンソープ出身の仲間が論文を書きました。

本当に避けたいのは、O(lm) で単語をテストするソリューションです。ここで、l はテストする単語の長さ、m は悪い単語の数です。これを行うには、悪い言葉をループする以外の解決策が必要です。これは正規表現で解決できると思っていましたが、典型的な実装では、内部のデータ構造が変更されるたびに増加することを忘れていました。他のソリューションの 1 つが言うように、Aho-Corasick はこれを行うアルゴリズムです。標準の実装ではすべてのマッチが検出されますが、最初のマッチでベイルアウトできるため、より効率的です。これは理論的に最適なソリューションを提供すると思います。

于 2013-02-22T22:45:01.587 に答える
0

これを行うためのより高速な方法を思いつくことができるかどうかに興味がありましたが、わずかな最適化しかできませんでした。これは、別の文字列内で発生する文字列のインデックスをチェックすることでした。これは、最初に「含む」よりもわずかに高速であるように思われ、次に大文字と小文字を区別しないように指定できるためです (それが役立つ場合)。

以下は、私が書いたテスト クラスです。100 万以上の単語を使用しており、すべてのケースで大文字と小文字を区別するテストを使用して検索しています。それはあなたの方法をテストし、私がその場で構築しようとしている正規表現もテストします。自分で試してみて、タイミングを確認できます。正規表現はあなたが提供した方法ほど速くは機能しませんが、間違って構築している可能性があります. (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-23T12:29:07.710 に答える