ÜBERSICHT
Ich habe eine Menge von möglichen gültigen Teilen, die ich verwenden kann, um einen Text zu teilen (wenn möglich).
Wie kann ich einen gegebenen Text unter Verwendung dieser Chunks aufteilen, so dass das Ergebnis hinsichtlich der Anzahl der resultierenden Chunks optimiert (minimiert) wird?
TEST SUITE
%Vor%FRAGE
Wie kann ich dieses Problem auf Python lösen, ohne einen Brute-Force-Ansatz zu verwenden?
Entschuldigung, die Implementierung ist ein bisschen hacky. Aber ich denke, es gibt immer die optimale Antwort zurück. (Allerdings nicht bewiesen.) Es ist eine schnelle und vollständige Implementierung in Python und liefert die richtigen Antworten für alle vorgeschlagenen Anwendungsfälle.
Der Algorithmus ist rekursiv und funktioniert wie folgt:
Wenn der Algorithmus fertig ist, sollten alle möglichen Pfade (und die nicht möglichen, d. h. keine Übereinstimmung am Ende) genau einmal durchlaufen worden sein.
Um Schritt 2 effizient durchzuführen, erstelle ich einen Patricia-Baum für die Auswahlmöglichkeiten, damit die möglichen Chunks, die zum Anfang des Textes passen, schnell nachgeschlagen werden können.
%Vor%Ich schätze, die Komplexität ist etwas wie O (L * N * log (C)), wobei L die Länge des Textes, N die Größe des Vokabulars und C die Anzahl der Wahlmöglichkeiten ist.
BEARBEITEN: Enthält den fehlenden Testfall.
Mit der dynamischen Programmierung können Sie eine Liste (l0, l1, l2, ... ln-1) erstellen, wobei n die Anzahl der Zeichen in Ihrer Eingabezeichenfolge und li die minimale Anzahl an Blöcken ist, die Sie benötigen, um das Zeichen i des zu erreichen Eingabezeichenfolge Die Gesamtstruktur würde wie folgt aussehen:
Die minimale Anzahl von Chunks für Ihre gesamte Zeichenfolge ist dann ln-1 . Sie können die tatsächlichen Chunks erhalten, indem Sie die Liste zurückverfolgen (was die Aufzeichnung der verwendeten Chunks erfordert).
Das Abrufen der Auswahlmöglichkeiten, die Suffixe sind, kann beschleunigt werden, indem ein Trie (der umgekehrten Auswahlzeichenfolgen) verwendet wird. Die Worst-Case-Komplexität wird weiterhin O(n * c * lc) sein, wobei n für die Länge der Eingabezeichenfolge steht, c für die Anzahl der Auswahlmöglichkeiten und lc für die maximale Länge der Auswahlmöglichkeiten. Diese Komplexität tritt jedoch nur bei Auswahlmöglichkeiten auf, die verschachtelte Suffixe sind (z. B. 0 , 10 , 010 , 0010 ...). In diesem Fall degeneriert der Trie zu einer Liste. Im Durchschnitt sollte die Laufzeit viel weniger sein. Unter der Annahme, dass die Anzahl der abgerufenen Auswahlen vom Trie immer eine kleine Konstante ist, ist es O(n * lc) (tatsächlich ist der lc Faktor wahrscheinlich auch kleiner).
Hier ist ein Beispiel:
%Vor%Bedeutung: Wir können die Zeichenfolge mit 2 Chunks zusammenstellen. Die Rückverfolgung gibt die Stücke in umgekehrter Reihenfolge wieder: "10", "100".
get_it_done function erzeugt zuerst mapping , wobei Schlüssel die Häufigkeitsbereiche jedes choice in number sind. Sortiert es dann nach dem ersten Element in jeder Taste von mapping dict. Der nächste Schritt ist das Erstellen von graph . Dann können wir mithilfe von find_shortest_path function den kürzesten Weg finden, um das Ergebnis auf die optimale Weise zu erstellen. Am Ende können wir mapping wieder verwenden, um choices entsprechend ihren Bereichen zurückzugeben. Wenn es einen Bereich gibt, haben wir eine Situation, in der alle Zahlen die gleichen zwei Werte haben, also sind die Regeln unterschiedlich. Wir können Zahlen direkt von choices (absteigend sortiert) sammeln, bis die Länge des Ergebnisses der Länge eines number entspricht.
Tags und Links python algorithm string split computer-science