文字列のパーティショニングのスペース上で計算を実行するための賢明な効率的なアルゴリズムはありますか？

Question

私は、文字列のコレクションを分割するためにあらゆる可能な方法を反復処理し、それぞれに簡単な計算を実行している必要統計的プロジェクトに取り組んでいます。具体的には、それぞれの可能な部分文字列にはそれに関連付けられた確率があり、パーティション内の部分文字列確率の積のすべての部分にわたって合計を取得しようとしています。

例えば、文字列が 'ABC' である場合、 'A'、 'B'、 'C​​'、「AB、 'BC' と 'ABC' の確率が存在するであろう。文字列には、 'abc'、 'ab | c'、 'a | bc'、 'a | b | c'の4つのパーティションがあります。アルゴリズムは、各分割のための成分確率の積を見つけ、次に4つの結果の数を合計する必要がある。

現在、私は（上の例のために例えば00、01、10、11）のパーティションの整数のバイナリ表現を使用してPythonのイテレータを書いたし、単純に整数を介して実行されます。残念ながら、これは20文字以上の文字列では非常に遅いです。

は、誰もが簡単に一度にすべてのパーティション1を通じて実行せずにこの操作を実行するための巧妙な方法を考えることはできますか？私は今、これに数日間執着してきました。いくつかのコメントに応えて

はここにいくつかのより多くの情報です：
は、文字列は何でもすることができ、例えば、「foobarに（foo2は）」 - 私たちのアルファベットは小文字の英数字がプラス括弧のすべての3つのタイプ（「（」、 "["、 "{"）、ハイフンとスペース。
目標は、個々の 'ワード' 尤度与えられた文字列の可能性を得ることである。したがって、L（S = 'ABC'）= P（ 'ABC'）+ P （ 'AB'）P（ 'C'）+ P（ 'A'）、P（ 'BC'）+ P（ 'A'）、P（ 'B'）、P（ 'C'）（ここで、「P（ 'ABC 'abc'）は、文字列 'abc'を観察する統計的尤度である）

Answer 1

Dynamic Programming溶液（I、右の質問を理解している場合）：

def dynProgSolution(text, probs): 
    probUpTo = [1] 
    for i in range(1, len(text)+1): 
    cur = sum(v*probs[text[k:i]] for k, v in enumerate(probUpTo)) 
    probUpTo.append(cur) 
    return probUpTo[-1] 

print dynProgSolution(
    'abc', 
    {'a': 0.1, 'b': 0.2, 'c': 0.3, 
    'ab': 0.4, 'bc': 0.5, 'abc': 0.6} 
) 

複雑さはO（N 2 ）ので、それは容易にN = 20のための問題を解決することです。

なぜこの作品がどのように：

• すべてはあなたがprobs['a']*probs['b']を掛けます、あなたはまた、乗算乗算と加算のDistributive Propertyからprobs['ab']
• おかげで、あなたは一緒にこれら二つを合計し、このシングルを掛けることができますすべての継続によって合計されます。
• すべての可能な最後の部分文字列に対して、その確率で前のパスのすべての確率の合計を掛け合わせることで、それで終わるすべての分割の合計を加算します。 （代替フレージングをいただければ幸いです。私のpythonが私の英語よりも優れている。）

Answer 2

まず、ボトルネックを見つけるためのプロファイル。

ボトルネックは、単に可能パーティションの膨大な数であれば、私はおそらくmultiprocessingを経由して、並列化をお勧めします。まだ十分でない場合は、Beowulfクラスタを調べることがあります。

ボトルネックは、計算が遅いだけということであれば、それはctypes経由で行うことは非常に簡単ですC.に砲撃してみてください。

また、パーティションをどのように格納しているのかよく分かりませんが、1つの文字列とsuffix arrayを使用することで、メモリ消費量をかなり減らすことができます。ボトルネックがスワッピングやキャッシュミスの場合は、大きな勝利になるかもしれません。

Answer 3

あなたの部分文字列が長い文字列で何度も再利用することになるだろうとしているので、memoizing技術を使用して値をキャッシュするように思えます試してみるべき明白なこと。これは単に時間と空間のトレードオフです。最も簡単な実装は、辞書を使用して値を計算するときにキャッシュすることです。すべての文字列計算の辞書検索を行います。それが辞書にない場合は、それを計算して追加します。その後の呼び出しでは、事前に計算された値が使用されます。辞書ルックアップが計算より速い場合、あなたは運がいいです。

私は...あなたは、Pythonを使用している実感がありますが、Perlでこれを行う場合は、あなたも、任意のコードを記述する必要はありません、関心のあるサイドノートとして、組み込みのMemoize moduleはあなたのためのキャッシングを行います！

Answer 4

あなたは、私はそれが生命チェンジャーになるか分からないけれども連想算術の性質（および文字列連結）に基づいて、小さなリファクタリングによる計算量のわずかな削減を得ることができます。コアの考え方は、次のとおりです。

「abcdefghik」、一般性を失うことなく、10-long。素朴なアプローチでは、p（a）に9テールの多くのパーティション、p（ab）に8テールなどの多くのパーティションを掛けます。特にp（a）とp（b）はp（ab）〜3の乗算とそれらの間の2つの合計のように、8テール（すべて）の同じパーティションに正確に乗算されます。だからアウトファクタ：

(p(ab) + p(a) * p(b)) * (partitions of the 8-tail) 

、我々は1つの製品及び1点の合計を保存した、2回の乗算と、この部分のための1つの和までです。 'b'のちょうど右のスプリットポイントですべてのパーティションをカバーします。それはちょうど「C」の分割とパーティションになると、

(p(abc) + p(ab) * p(c) + p(a) * (p(b)*p(c)+p(bc)) * (partitions of the 7-tail) 

節約は内部リファクタリングに一部のおかげで、マウント - もちろん一つは、ダブルカウントに注意する必要がありますけれども。私はこのアプローチが一般化されるかもしれないと考えています - 中間点から始めて、左と右の部分に対して別々に（そして再帰的に）分割したすべてのパーティションを考慮して、乗算と加算を行います。そこに分割されていないすべてのパーティションを追加します。この例では、左側が左側に 'abcde'、右側に 'fghik'があり、2番目の部分は 'ef'が離れているのではなく、すべてのパーティションです。 'を新しいスーパーレターXとして追加すると、短い文字列abcdXghik（もちろん、THATの部分文字列の確率はオリジナルに直接マップされます。たとえば、新しい文字列のp（cdXg）は元のp（cdefg）とまったく同じです）。

Answer 5

itertoolsモジュールを調べる必要があります。それは非常に速いあなたのためのジェネレータを作成することができます。あなたの入力文字列を与えると、それはすべての可能な順列を提供します。必要なものによっては、combinations()ジェネレータもあります。私はあなたが "abc"を見ているときに "b | ca"を見ているのかどうかは分かりませんが、いずれにせよ、このモジュールはあなたにとって有益なことを証明するかもしれません。