Wenn ich eine Zeichenfolge mit Wörtern und ohne Leerzeichen habe, wie soll ich diese Wörter parsen, wenn ich ein Wörterbuch / eine Liste mit diesen Wörtern habe?
Wenn meine Zeichenfolge beispielsweise "thisastringwithwords" lautet, wie könnte ich ein Wörterbuch verwenden, um eine Ausgabe "Dies ist eine Zeichenfolge mit Wörtern" zu erstellen?
Ich höre, dass die Verwendung der Datenstruktur Versuche helfen könnte, aber vielleicht, wenn jemand mit dem Pseudocode helfen könnte? Zum Beispiel dachte ich, dass Sie vielleicht das Wörterbuch in eine Trie-Struktur indizieren könnten und dann jedem Char den Trie folgen lassen; Problem ist, ich bin nicht vertraut mit, wie man das in (Pseudo-) Code macht.
Ich gehe davon aus, dass Sie eine effiziente Lösung wünschen, nicht die offensichtliche, bei der Sie wiederholt überprüfen, ob Ihr Text mit einem Wörterbuchwort beginnt.
Wenn das Wörterbuch klein genug ist, denke ich, dass Sie versuchen könnten, den Standard KMP -Algorithmus. Im Grunde bauen Sie einen endlichen Automaten in Ihrem Wörterbuch, der den Text Zeichen für Zeichen konsumiert und die konstruierten Wörter ergibt.
EDIT: Es schien, dass ich Versuche neu erfand.
Ich habe schon etwas ähnliches gemacht. Sie können kein einfaches Wörterbuch verwenden. Das Ergebnis wird unordentlich sein. Es hängt davon ab, ob Sie dies nur einmal oder als ganzes Programm tun müssen.
Meine Lösung war:
Jetzt müssen Sie eine "Tabelle der Möglichkeiten" erstellen. Weil viele Wörter zu 100% passen können, aber falsch sind. Je länger das Wort, desto sicherer ist es, dass dieses Wort das richtige ist.
Es ist CPU-intensiv, aber es kann präzise im Ergebnis arbeiten. Nehmen wir an, Sie verwenden ein kleines Wörterbuch mit 10.000 Wörtern und 3.000 davon mit einer Länge von 8 Zeichen. Sie müssen Ihren bigString beim Start mit allen 3.000 Wörtern vergleichen und nur wenn das Ergebnis gefunden wurde, kann es weitergehen das nächste Wort. Wenn Sie 200 Zeichen in Ihrem BigString haben, benötigen Sie ungefähr (2000 Zeichen / 8 durchschnittliche Zeichen) = 250 volle Schleifen Minimum mit Vergleich.
Für mich habe ich auch eine kleine Überprüfung von falsch geschriebenen Wörtern in die Vergleiche gemacht.
Beispiel für eine Prozedur (Kopieren nicht einfügen)
%Vor%Ich habe dir gesagt, dass es wie eine unmögliche Aufgabe aussieht. Aber Sie können sich diese Frage zum Thema SO ansehen - es kann Ihnen dabei helfen.
Dies ist das genaue Problem, das man beim programmatischen Parsen von Sprachen wie Chinesisch hat, wo zwischen Wörtern keine Leerzeichen stehen. Eine Methode, die mit diesen Sprachen arbeitet, besteht darin, den Text mit Interpunktion zu teilen. Das gibt dir Sätze. Als nächstes iterieren Sie die Phrasen und versuchen, sie in Wörter zu brechen, beginnend mit der Länge des längsten Wortes in Ihrem Wörterbuch. Nehmen wir an, die Länge beträgt 13 Zeichen. Nehmen Sie die ersten 13 Zeichen aus dem Satz und sehen Sie, ob es in Ihrem Wörterbuch ist. Wenn dem so ist, nehmen Sie es zunächst als korrektes Wort, gehen Sie im Satz vor und wiederholen Sie es. Andernfalls kürzen Sie Ihre Teilzeichenfolge auf 12 Zeichen, dann auf 11 Zeichen usw.
Das funktioniert sehr gut, aber nicht perfekt, weil wir aus Versehen Wörter in den Vordergrund gestellt haben, die an erster Stelle stehen. Eine Möglichkeit, diese Verzerrung zu entfernen und Ihr Ergebnis doppelt zu überprüfen, besteht darin, den Prozess am Ende des Ausdrucks zu wiederholen. Wenn Sie die gleichen Wortbrüche bekommen, können Sie es wahrscheinlich gut nennen. Wenn nicht, haben Sie ein überlappendes Wortsegment. Wenn Sie zum Beispiel Ihre Beispielphrase am Ende analysieren, erhalten Sie möglicherweise (zur Betonung nach hinten)
%Vor%Zunächst scheint das Wort Isis (ägyptische Göttin) das richtige Wort zu sein. Wenn Sie jedoch feststellen, dass "th" nicht in Ihrem Wörterbuch enthalten ist, wissen Sie, dass in der Nähe ein Wortsegmentierungsproblem auftritt. Lösen Sie dies, indem Sie mit dem Vorwärts-Segmentierungsergebnis "Dies ist" für die nicht-ausgerichtete Sequenz "thisis" gehen, da beide Wörter im Wörterbuch sind.
Eine weniger verbreitete Variante dieses Problems ist, wenn benachbarte Wörter eine Sequenz teilen, die in beide Richtungen gehen könnte. Wenn Sie eine Sequenz wie "archand" (um etwas zu machen) hatten, sollte es "Bogenhand" oder "Bogen und" sein? Die Methode zur Bestimmung besteht darin, eine Grammatikprüfung auf die Ergebnisse anzuwenden. Dies sollte sowieso für den ganzen Text gemacht werden.
Ok, ich werde einen Hand-Wellen-Versuch machen. Die perfekte (ish) Datenstruktur für Ihr Problem ist (wie Sie gesagt haben) ein Trie aus den Wörtern im Wörterbuch. Ein Trie wird am besten als DFA visualisiert, eine nette Zustandsmaschine, auf der man von einem Zustand zum nächsten übergeht neuer Charakter. Dies ist im Code sehr einfach, eine Java (ish) -Stil-Klasse wäre dies:
%Vor% Von hier an ist der Bau des Trie einfach. Es ist wie eine verwurzelte Baumstruktur mit jedem Knoten mit mehreren Kindern. Jedes Kind wird in einem Zeichenübergang besucht. Die Verwendung einer HashMap Art von Struktur verkürzt die Zeit, um nach den nächsten State -Mappings zu suchen. Alternativ, wenn alles, was Sie haben, 26 Zeichen für das Alphabet sind, würde ein fixed size array of 26 auch den Trick tun.
Wenn Sie nun annehmen, dass alles einen Sinn ergibt, haben Sie einen Trie, und Ihr Problem ist immer noch nicht vollständig gelöst. Hier fangen Sie an, Dinge wie reguläre Ausdrücke zu tun, gehen Sie den Trie hinunter, verfolgen Sie Zustände, die zu einem ganzen Wort im Wörterbuch passen (das ist, was ich die matchedWord für in der State Struktur hatte), verwenden eine Backtracking-Logik, um zu einem vorherigen Übereinstimmungszustand zu springen, wenn der aktuelle Pfad eine Sackgasse erreicht. Ich kenne es allgemein, aber angesichts der Trie-Struktur ist der Rest ziemlich einfach.
Wenn Sie Wörterbücher haben und eine schnelle Implementation benötigen, kann dies effizient mit dynamischer Programmierung in O (n ^ 2) -Zeit gelöst werden, vorausgesetzt, die Dictionary-Lookups sind O (1). Unten ist ein C # -Code, der die Extraktion von Teilzeichenfolgen und die Suche nach einem Wörterbuch verbessern könnte.
%Vor%Erstellen Sie ein Problem mit der Wortliste von / usr / share / dict / words und testen Sie mit
%Vor%Ich bekomme die Ausgabe "t hi sis eine Zeichenfolge mit Worten". Wie andere bereits erwähnt haben, wird dieser Algorithmus eine gültige Segmentierung (falls vorhanden) zurückgeben, jedoch ist dies möglicherweise nicht die von Ihnen erwartete Segmentierung. Das Vorhandensein kurzer Wörter reduziert die Segmentierungsqualität. Sie können möglicherweise Heuristik hinzufügen, um längere Wörter zu bevorzugen, wenn zwei gültige Untersegmentierungen ein Element eingeben.
Es gibt ausgefeiltere Methoden, die Maschinen mit endlichen Zuständen und Sprachmodelle verwenden, die mehrere Segmentierungen erzeugen und probabilistische Rangfolgen anwenden können.
Tags und Links algorithm c# data-structures text-segmentation