3

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

たとえば、文字列が「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'）」は'word''abc'、 "L（S ='abc'）"は文字列'abc'を観測する統計的尤度です。

4

5 に答える 5

5

動的計画法ソリューション（私が質問を正しく理解した場合）：

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']はまた掛けるでしょうprobs['ab']
  • 乗算と加算の分配法則のおかげで、これら2つを合計して、この1つの合計にすべての継続を乗算できます。
  • 可能なすべての最後のサブストリングについて、その確率に前のパスのすべての確率の合計を掛けたものを加算することにより、それで終わるすべての分割の合計を加算します。（別の言い回しをいただければ幸いです。私のPythonは私の英語よりも優れています。）
于 2009-08-03T15:57:35.237 に答える
3

まず、プロファイルを作成してボトルネックを見つけます。

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

ボトルネックが計算が遅いということだけである場合は、Cにシェルアウトしてみてください。を介して行うのは非常に簡単ですctypes。

また、パーティションをどのように格納するかはよくわかりませんが、1つの文字列と接尾辞配列を使用することで、メモリ消費をかなり抑えることができます。ボトルネックがスワッピングやキャッシュミスである場合、それは大きな勝利になる可能性があります。

于 2009-08-03T15:40:49.370 に答える
1

サブ文字列は長い文字列によって何度も再利用されるため、メモ化手法を使用して値をキャッシュすることは、当然のことのように思われます。これは時間と空間のトレードオフにすぎません。最も簡単な実装は、ディクショナリを使用して、値を計算するときに値をキャッシュすることです。すべての文字列計算に対して辞書検索を実行します。辞書にない場合は、計算して追加します。以降の呼び出しでは、事前に計算された値が使用されます。辞書の検索が計算よりも速い場合は、幸運です。

Pythonを使用していることは承知していますが、興味深いことに、Perlでこれを行う場合は、コードを記述する必要すらありません。組み込みのメモ化モジュールがキャッシュを実行します。

于 2009-08-03T15:58:10.807 に答える
1

算術の結合法則（および文字列の連結）に基づく小さなリファクタリングによって、計算量がわずかに削減される可能性がありますが、それが人生を変えるものになるかどうかはわかりません。中心的なアイデアは次のとおりです。

一般性を失うことのない明確さのために、長い文字列、例えば「abcdefghik」、10の長さを考えてみてください。素朴なアプローチでは、p（a）に9テールの多くのパーティションを掛け、p（ab）に8テールの多くのパーティションを掛けます。特に、p（a）とp（b）は、p（ab）とまったく同じ8テール（すべて）のパーティションを乗算します。つまり、3回の乗算と2回の合計です。したがって、それを除外します。

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

そして、この部分では2つの乗算と1つの合計になり、1つの積と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」が一緒になっているすべてのパーティションについてです。離れて-したがって、その「ef」を新しい「スーパーレター」Xと見なすことにより、すべての確率を「折りたたむ」と、1つ短い文字列「abcdXghik」が残ります（もちろん、その部分文字列の確率は、オリジナル、e。g。新しい文字列のp（cdXg）は、元の文字列のp（cdefg）とまったく同じです。

于 2009-08-03T15:58:36.530 に答える
0

モジュールを調べる必要がありitertoolsます。それはあなたのために非常に速いジェネレーターを作成することができます。入力文字列を指定すると、可能なすべての順列が提供されます。必要に応じて、combinations()ジェネレーターもあります。「abc」を見ているときに「b|ca」を見ているかどうかはよくわかりませんが、どちらにしても、このモジュールが役立つかもしれません。

于 2009-08-03T16:16:28.670 に答える