1

次のクラスは、非常に大きな文字列（テキストの小説全体）を解析し、それをタプルとして格納される連続する4文字の文字列に分割します。次に、計算に基づいて各タプルに確率を割り当てることができます。私はこれをモンテカルロ/遺伝的アルゴリズムの一部として使用して、構文のみに基づいて言語を認識するようにプログラムをトレーニングしています（文字の遷移のみ）。

これを行うより速い方法があるかどうか疑問に思います。任意の4文字のタプルの確率を調べるのに約400msかかります。関連するメソッド_Probablity（）は、クラスの最後にあります。

これは、私の別の投稿に関連する計算集約型の問題です。関数の妥当性を計算するためのアルゴリズム/モンテカルロ法

最終的には、これらの値を4Dマトリックスに保存したいと思います。しかし、アルファベットに26文字あることを考えると、これは非常に大きな作業になります。（26x26x26x26）。小説の最初の15000文字だけを取ると、パフォーマンスは1トン向上しますが、私のデータはそれほど有用ではありません。

テキスト'source'を解析するメソッドは次のとおりです。

    private List<Tuple<char, char, char, char>> _Parse(string src)
    {
        var _map = new List<Tuple<char, char, char, char>>(); 

        for (int i = 0; i < src.Length - 3; i++)
        {
          int j = i + 1;
          int k = i + 2;
          int l = i + 3;

          _map.Add
            (new Tuple<char, char, char, char>(src[i], src[j], src[k], src[l])); 
        }

        return _map; 
    }

そして、これが_Probabilityメソッドです。

    private double _Probability(char x0, char x1, char x2, char x3)
    {
        var subset_x0 = map.Where(x => x.Item1 == x0);
        var subset_x0_x1_following = subset_x0.Where(x => x.Item2 == x1);
        var subset_x0_x2_following = subset_x0_x1_following.Where(x => x.Item3 == x2);
        var subset_x0_x3_following = subset_x0_x2_following.Where(x => x.Item4 == x3);

        int count_of_x0 = subset_x0.Count();
        int count_of_x1_following = subset_x0_x1_following.Count();
        int count_of_x2_following = subset_x0_x2_following.Count();
        int count_of_x3_following = subset_x0_x3_following.Count(); 

        decimal p1;
        decimal p2;
        decimal p3;

        if (count_of_x0 <= 0 || count_of_x1_following <= 0 || count_of_x2_following <= 0 || count_of_x3_following <= 0)
        {
            p1 = e;
            p2 = e;
            p3 = e;
        }
        else
        {
            p1 = (decimal)count_of_x1_following / (decimal)count_of_x0;
            p2 = (decimal)count_of_x2_following / (decimal)count_of_x1_following;
            p3 = (decimal)count_of_x3_following / (decimal)count_of_x2_following;

            p1 = (p1 * 100) + e; 
            p2 = (p2 * 100) + e;
            p3 = (p3 * 100) + e; 
        }

        //more calculations omitted

        return _final; 
    }
}

編集-私は物事を片付けるためにもっと詳細を提供しています、

1）厳密に言えば、私はこれまで英語しか扱っていませんが、異なるアルファベットを考慮する必要があるのは事実です。現在、このペーパーで説明されているものと同様に、プログラムで英語のみを認識したいと考えています。http ://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf

2）n <= 4の文字のnタプルの確率を計算しています。たとえば、文字列「that」の合計確率を計算する場合、これらの独立したタプルに分解して、それぞれの確率を計算します。個別に最初に：

[t] [h]

[t] [h] [a]

[それ]

[t] [h]が最も重みが与えられ、次に[t] [h] [a]、次に[t] [h][a][t]が与えられます。私は4文字のタプルを単一のユニットとして見ているだけではないので、テキスト内の[t] [h][a][t]のインスタンスを合計数で割ることはできません。次の4タプルの。

各4タプルに割り当てられた値は、テキストに適合しすぎることはありません。これは、偶然にも多くの実際の英語の単語がテキストに表示されない可能性があり、不釣り合いに低いスコアを取得するべきではないためです。1次の文字遷移（2タプル）を強調すると、この問題が改善されます。3タプルに移動してから、4タプルで計算を調整します。

私は、メモリの浪費である同一のタプルを繰り返すのではなく、テキスト内でタプルが発生する頻度のカウントを単純に集計する辞書を思いつきました（Vilxが提案したものと同様）。これにより、ルックアップあたり約400ミリ秒から約40ミリ秒になりました。これは、かなり大きな改善です。しかし、私はまだ他の提案のいくつかを調べる必要があります。

4

5 に答える 5

1

データ構造を変更して高速化することをお勧めします...

Dictionary<char,Dictionary<char,Dictionary<char,Dictionary<char,double>>>>計算時に各「レベル」（Item1 ... Item4）にアクセスし、結果を最も内側にキャッシュするため、Dictionary次回はまったく計算する必要がないため、aの方がはるかに効率的だと思います。 ..

于 2011-09-19T07:15:12.170 に答える
1

yoiu確率法では、マップを8回反復します。それぞれの場所はリスト全体を繰り返し、カウントも繰り返します。.ToList（）広告を最後に追加すると、（潜在的に）処理速度が向上します。とはいえ、あなたの主な問題は、データを格納するために選択した構造が確率法の目的に適していないことだと思います。データを格納する構造が挿入時に暫定的な分布を計算するワンパスバージョンを作成できます。そうすれば、挿入が完了したときに（あまり遅くするべきではありません）、完了したか、以下のコードで必要なときに確率を安価に計算できるため、実行できます。

余談ですが、パントと空白を考慮に入れることをお勧めします。文の最初の文字/単語と単語の最初の文字は、サンプルデータの特性を含める分布の一部として句読点と空白を使用することにより、特定のテキストがどの言語で書かれているかを明確に示します。私たちは数年前にそれをしました。これを行うことで、3文字を使用することはほぼ同じであることが示されました（テストデータで3文字を使用しても失敗はなく、情報が不足すると誤った結果が得られる奇妙なテキストがほとんどであると仮定すると、ほぼ同じです） 。より多くを使用するように（7までテストします）、3文字の速度がそれを最良のケースにしました。

編集

これが私がC＃でそれを行うと思う方法の例です

class TextParser{
        private Node Parse(string src){
            var top = new Node(null);

            for (int i = 0; i < src.Length - 3; i++){
                var first = src[i];
                var second = src[i+1];
                var third = src[i+2];
                var fourth = src[i+3];

                var firstLevelNode = top.AddChild(first);
                var secondLevelNode = firstLevelNode.AddChild(second);
                var thirdLevelNode = secondLevelNode.AddChild(third);
                thirdLevelNode.AddChild(fourth);
            }

            return top;
        }
    }

    public class Node{
        private readonly Node _parent;
        private readonly Dictionary<char,Node> _children 
                         = new Dictionary<char, Node>();
        private int _count;

        public Node(Node parent){
            _parent = parent;
        }

        public Node AddChild(char value){
            if (!_children.ContainsKey(value))
            {
                _children.Add(value, new Node(this));
            }
            var levelNode = _children[value];
            levelNode._count++;
            return levelNode;
        }
        public decimal Probability(string substring){
            var node = this;
            foreach (var c in substring){
                if(!node.Contains(c))
                    return 0m;
                node = node[c];
            }
            return ((decimal) node._count)/node._parent._children.Count;
        }

        public Node this[char value]{
            get { return _children[value]; }
        }
        private bool Contains(char c){
            return _children.ContainsKey(c);
        }
    }

その場合、使用法は次のようになります。

var top = Parse(src);
top.Probability("test");
于 2011-09-19T07:37:38.530 に答える
1

わかりました、詳細を理解する時間がありませんが、これは本当に必要です

  • ニューラルクラシファイアネット（すぐに入手できるものを取り除けControllable Regex Mutilatorば、はるかに高いスケーラビリティで仕事をすることができます）-ブルートフォースよりもヒューリスティック

  • 試行を使用できます（Patricia Tries、別名基数木を使用して、スパースにできるデータ構造のスペース最適化バージョンを作成します（Dictionaries of Dictionaries of Dictionaries of Dictionaries ...私にはこれの近似のように見えます）

于 2011-09-19T07:50:13.413 に答える
1

現状では、解析関数でできることはあまりありません。ただし、タプルは、大量のテキストからの4つの連続した文字のように見えます。タプルをintに置き換えてから、文字値が必要なときにintを使用してテキストの大きな本文にインデックスを付けてみませんか。タプルベースの方法は、元のテキストが使用するメモリの4倍を効果的に消費します。通常、メモリはパフォーマンスのボトルネックであるため、使用するメモリはできるだけ少なくすることをお勧めします。

次に、テキストの本文で文字のセットと一致する数を見つけようとします。元のテキスト本文に対する単純な線形検索は、使用しているlinqステートメントとどのように比較されるのでしょうか。は.Whereメモリ割り当てを実行し（これは低速の操作です）、linqステートメントには解析オーバーヘッドがあります（ただし、コンパイラーはここで何か賢いことをする可能性があります）。探索空間をよく理解すると、最適なアルゴリズムを見つけやすくなります。

しかし、コメントで述べたように、264マトリックスを使用するのが最も効率的です。入力テキストを1回解析し、解析しながらマトリックスを作成します。おそらく、辞書のセットが必要になるでしょう。

SortedDictionary <int,int> count_of_single_letters; // key = single character
SortedDictionary <int,int> count_of_double_letters; // key = char1 + char2 * 32
SortedDictionary <int,int> count_of_triple_letters; // key = char1 + char2 * 32 + char3 * 32 * 32
SortedDictionary <int,int> count_of_quad_letters;   // key = char1 + char2 * 32 + char3 * 32 * 32 + char4 * 32 * 32 * 32

最後に、データ型に関する注意。decimalタイプを使用しています。CPUネイティブ型への直接マッピングがなく、データの処理にオーバーヘッドがあるため、これは効率的な型ではありません。代わりにダブルを使用してください。精度は十分だと思います。最も正確な方法は、確率を分子と分母の2つの整数として格納し、可能な限り遅く除算を行うことです。

于 2011-09-19T08:02:28.343 に答える
1

ここでの最善のアプローチは、たとえば、各10000文字の後にスパースストレージとプルーニングを使用することです。この場合の最適なストレージ構造はプレフィックスツリーです。これにより、確率の高速計算、更新、およびスパースストレージが可能になります。このjavadochttp://alias-i.com/lingpipe/docs/api/com/aliasi/lm/NGramProcessLM.htmlでより多くの理論を見つけることができます

于 2011-09-19T11:45:32.173 に答える