Gibt es geschickt effiziente Algorithmen, um eine Berechnung über den Raum von Partitionierungen einer Zeichenfolge zu erfüllen?

Question

Ich arbeite an einem Projekt, die statistischen Iterieren jede erdenkliche Art und Weise über beinhaltet eine Sammlung von Strings und Ausführen eine einfache Berechnung auf jedem zu partitionieren. Insbesondere hat jede mögliche Teilkette eine Wahrscheinlichkeit mit ihm verbunden, und ich versuche, die Summe über alle Partitionen des Produkts der Teil Wahrscheinlichkeit in der Partition zu erhalten.

Zum Beispiel, wenn die Zeichenfolge 'abc', dann gäbe es Wahrscheinlichkeiten für 'a' sein, 'b', 'c', ‚ab, 'bc' und 'abc'. Es gibt vier mögliche Aufteilungen der Zeichenfolge: 'abc', 'ab | c', 'a | bc' und 'a | b | c'. Der Algorithmus muss das Produkt der Komponentenwahrscheinlichkeiten für jede Unterteilung finden, dann die vier resultierenden Zahlen summiert.

Zur Zeit habe ich eine Python Iterator geschrieben, die binären Darstellungen von ganzen Zahlen für die Partitionen verwendet (zB 00, 01, 10, 11 für das Beispiel oben) und einfach die ganzen Zahlen durchläuft. Leider ist dies ungeheuer langsam für Saiten länger als 20 oder so Zeichen.

Kann jemand denken Sie an einem cleveren Weg, um diese Operation auszuführen, ohne einfach durch jede Partition einen nach dem anderen ausgeführt wird? Ich habe jetzt seit einigen Tagen auf diesem stecken.

Als Reaktion auf einige Kommentare hier sind einige weitere Informationen:
Der String kann so gut wie alles, zB „foobar (foo2)“ - unser Alphabet ist Kleinalphanumerische sowie alle drei Arten von Klammern ( „(“, „[“, „{“), Bindestriche und Leerzeichen
. Das Ziel ist es, die Wahrscheinlichkeit, dass die String einzelne ‚Wort‘ Wahrscheinlichkeiten gegeben zu bekommen. So L (S = 'abc') = P ( 'abc') + P ( 'ab') P ( 'c') + P ( 'a') P ( 'bc') + P ( 'a') P ( 'b') P ( 'C') (hier "P ( 'abc')" bezeichnet die Wahrscheinlichkeit, dass das 'Wort' 'abc', während "L (S = 'ABC')" ist die statistische Wahrscheinlichkeit des Beobachtens die Zeichenfolge 'abc').

Answer 1

Dynamische Programmierung Lösung (wenn ich die Frage richtig verstanden):

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

Die Komplexität ist O (N ² ), so wird das Problem für N = 20.

leicht lösen

Wie warum funktionierts:

• Alles, was Sie von probs['a']*probs['b'] multiplizieren Sie auch multiplizieren mit probs['ab']
• Dank der Verteiler- Property von Multiplikation und Addition, können Sie die beiden Summe zusammen und multiplizieren Sie mit all seinen Fortsetzungen diese einzelne Summe.
• Für jede mögliche letzte Teilkette, fügt die Summe aller Splits mit der Endung durch seine Wahrscheinlichkeit Zugabe durch die Summe aller Wahrscheinlichkeiten der bisherigen Pfade multipliziert. (Alternative Formulierung würde geschätzt. Mein Python ist besser als mein Englisch ..)

Answer 2

Als erstes Profil, den Engpass zu finden.

Wenn der Engpass ist einfach die massive Anzahl von möglichen Partitionen, empfehle ich Parallelisierung, möglicherweise über multiprocessing . Wenn das immer noch nicht genug ist, kann man sich in einem Beowulf Cluster.

Wenn der Engpass gerade ist, dass die Berechnung langsam ist, versuchen Sie, C. Beschuss aus Es ist ziemlich einfach über ctypes .

Auch ich bin nicht wirklich sicher, wie Sie die Partitionen sind speichern, aber Sie könnten wahrscheinlich Squash Speicherverbrauch ein ziemlich gutes Stück für eine Saite mit und Suffixarray . Wenn Ihr Engpass und / oder Cache-Misses Swapping, das könnte ein großer Gewinn sein.

Answer 3

Ihre Strings werden wieder verwendet werden immer und immer wieder durch die längeren Saiten, so die Werte Cachen mit einem memoizing Technik scheint wie eine offensichtliche Sache zu versuchen. Dies ist nur ein Raum-Zeit-Handel ab. Die einfachste Implementierung ist ein Wörterbuch Cache-Werte zu verwenden, wie Sie sie berechnen. Führen Sie ein Wörterbuch-Lookup für jede Zeichenfolge Berechnung; wenn es nicht im Wörterbuch enthalten ist, berechnen und es hinzuzufügen. Anschließende Anrufe Verwendung des im Voraus berechneten Wertes. Wenn die Wörterbuchsuche schneller als die Berechnung ist, haben Sie Glück.

Ich weiß, Sie Python verwenden, aber ... als eine Randnotiz, die von Interesse sein kann, wenn Sie dies in Perl zu tun, haben Sie nicht einmal einen Code schreiben; die eingebaute Memoize Modul wird für Sie das Caching tun!

Answer 4

Sie können eine geringe Verringerung der Menge der Berechnung durch einen kleinen Refactoring erhalten basierend auf assoziativen Eigenschaften der Arithmetik (und String-Verkettung) obwohl ich nicht sicher bin, dass es ein Leben Wechsler sein. Die Kernidee würde wie folgt aussehen:

Sehen Sie eine längere Zeichenfolge beispiels 'Abcdefghik', 10 lang, für Bestimmtheit w / o Verlust der Allgemeinheit. In einem naiven Ansatz werden Sie p (a) durch die Anzahl der Partitionen des 9-tail, p (ab) durch die Anzahl der Partitionen des 8-tail werden multipliziert, etc; insbesondere p (a) und p (b) multipliziert werden genau die gleichen Partitionen des 8-Schwanz (alle von ihnen) als p (ab) wird - 3 Multiplikationen und zwei Summen unter ihnen. So dass ausklammern:

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

und wir sind bis zu 2 Multiplikationen und 1 Summe für diesen Teil, 1 Produkt und 1 Summe gespart hat. alle Partitionen mit einem Split-Punkt genau richtig von ‚b‘ zu decken. Wenn es um die Partitionen mit einem Split nur rechts von ‚c‘,

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

die Einsparungen montieren, zum Teil dank der internen Refactoring - obwohl natürlich muss man über eine Doppelzählung vorsichtig sein. Ich denke, dass dieser Ansatz verallgemeinert werden kann - mit dem Mittelpunkt beginnen und alle Partitionen zu berücksichtigen, die eine Spaltung dort haben, separat (und rekursiv) für den linken und rechten Teil, Multiplikation und Addition; dann fügen Sie alle Partitionen, die nicht über eine Spaltung haben z.B. die Hälften ‚abcde‘ auf der linken Seite und ‚fghik‘ auf der rechten Seite zu sein, der zweite Teil ist über alle Partitionen in dem Beispiel, wo ‚ef‘ zusammen sind und nicht auseinander - so „Zusammenbruch“ alle Wahrscheinlichkeiten unter Berücksichtigung, dass ‚ef "als neuer‚superletter‘X, und Sie sind links mit einem String eine kürzeren,‚abcdXghik‘(natürlich die Wahrscheinlichkeiten für den Teil jener Karte direkt an die Originale, zum Beispiel der p (cdXg) in der neuen Zeichenfolge nur genau die p (CDEFG) im Original).

Answer 5

Sie sollten das itertools Modul suchen. Es kann einen Generator erstellen für Sie, dass es sehr schnell. Angesichts Ihrem Eingabestring, wird es Sie mit allen möglichen Permutationen bieten. Je nachdem, was Sie benötigen, gibt es auch einen combinations() Generator. Ich bin mir nicht ganz sicher, ob man sich freuen „b | ca“, wenn Sie auf der Suche sind „abc“, aber so oder so, kann dieses Modul als nützlich erweisen, um Sie

.