Tokenize den Text auf einige spezifische Regeln abhängig. Algorithmus in C ++

https://stackoverflow.com/questions/903133

05-09-2019
|

Frage

Ich schreibe ein Programm, das die Eingabe von Text auf einigen spezifischen Regeln abhängig wird tokenize. Ich bin mit C ++ für diese.

Regeln

Letter 'a' should be converted to token 'V-A'
Letter 'p' should be converted to token 'C-PA'
Letter 'pp' should be converted to token 'C-PPA'
Letter 'u' should be converted to token 'V-U'

Dies ist nur ein Beispiel und in Echtzeit Ich habe um mehr als 500 Regeln wie diese. Wenn ich Eingang am Bereitstellung als ' appu ', sollte es tokenize wie ' V-A + C-PPA + V-U '. Ich habe einen Algorithmus, dies zu tun implementiert und wollte sicherstellen, dass ich das Richtige tue.

Algorithm

Alle Regeln werden in einer XML-Datei mit der entsprechenden Zuordnung zu dem Token gehalten werden. So etwas wie

<rules>
  <rule pattern="a" token="V-A" />
  <rule pattern="p" token="C-PA" />
  <rule pattern="pp" token="C-PPA" />
  <rule pattern="u" token="V-U" />
</rules>

1 - Wenn die Anwendung gestartet wird, diese XML-Datei lesen und die Werte halten in einem ' std :: map '. Dies wird bis zum Ende der Anwendung (Singletonmuster Implementierung) zur Verfügung.

2 - Iterate die Eingabetextzeichen. Für jedes Zeichen, suchen Sie nach einem Spiel. Wenn sie gefunden wird, wird mehr gierig und für weitere Spiele suchen, indem Sie die nächsten Zeichen aus dem Eingabetext nehmen. Tun Sie dies, bis wir eine keine Übereinstimmung zu bekommen. Also für die Eingabe von Text ' appu ', ersten Blick auf eine Übereinstimmung für ' a '. Wenn Sie gefunden wird, versuchen, mehr Spiel zu erhalten, indem das nächste Zeichen aus dem Eingabetext nehmen. So wird es versuchen, passen ' ap ' und hat keine Übereinstimmungen. Also es gibt nur.

. 3 - Ersetzen Sie die Buchstaben ‚a‘ aus dem Eingabetext als wir ein Zeichen dafür bekamen

. 4 - Wiederholen Sie Schritt 2 und 3 mit den übrigen Zeichen im Eingangstext

Hier ist eine einfache Erklärung der Schritte

input-text = 'appu'
tokens-generated=''

// First iteration
character-to-match = 'a'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ap'
pattern-found = false

tokens-generated = 'V-A'

// since no match found for 'ap', taking the first success and replacing it from input text
input-text = 'ppu'

// second iteration
character-to-match = 'p'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'pp'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ppu'
pattern-found = false

tokens-generated = 'V-A + C-PPA'

// since no match found for 'ppu', taking the first success and replacing it from input text
input-text = 'u'

// third iteration
character-to-match = 'u'
pattern-found = true

tokens-generated = 'V-A + C-PPA + V-U'  // we'r done!

Fragen

1 - Ist dieser Algorithmus für dieses Problem sieht gut aus, oder gibt es einen besseren Weg, dieses Problem zu lösen

2 - Ist dies die richtige Methode, std :: map eine gute Wahl ist hier? Oder muss ich meinen eigenen Schlüssel / Wert-Container erstellen?

3 - Gibt es eine Bibliothek zur Verfügung, die Zeichenfolge wie die oben tokenize kann

Jede mögliche Hilfe geschätzt

Lösung

So können Sie durch alle Token in der Karte gehen nach Übereinstimmungen suchen? Genauso gut könnte man eine Liste oder ein Array verwenden, gibt; es wird unabhängig eine ineffiziente Suche sein.

Eine wesentlich effizientere Art und Weise nur die Zeichen der Suche nach geeigneten zum Starten oder Weiterbildung eines Spiel, sie als eine speichern wäre Trie . Ein Nachschlag eines Briefes es würde Ihnen eine Sub-trie, die nur die Token enthält, die diesen Brief als den ersten Buchstaben, und dann fahren Sie gerade nach unten so weit suchen, wie Sie gehen können.

Edit: lassen Sie mich erklären dies ein wenig weiter

Zuerst sollte ich erklären, dass ich mit diesen die C ++ std::map nicht vertraut bin, über den Namen, die von diesen ein perfektes Beispiel macht, warum man die Theorie dieses Materials sowie als Details von bestimmten Bibliotheken insbesondere Programmierung lernt Sprachen: es sei denn, dass Bibliothek schlecht den Namen mißbraucht „map“ (was eher unwahrscheinlich ist), der Name selbst mir viel über die Eigenschaften der Datenstruktur erzählt. Ich weiß zum Beispiel, dass es geht um eine Funktion sein, die eine einzelne Taste und die Karte bekommen hat, wird sehr effizient zu suchen und den Wert zurück, mit diesem Schlüssel zugeordnet ist, und dass es wahrscheinlich auch eine Funktion, die eine Liste geben / array / was auch immer der alle Schlüssel, die Sie Ihren eigenen Code suchen konnte selbst mit.

Meine Interpretation Ihrer Datenstruktur ist, dass Sie eine Karte, wo die Schlüssel sind, was Sie ein Muster nennen, die eine Liste zu sein (oder Array oder etwas in der Art) von Zeichen, und die Werte sind Token. Sie können also gegeben, ein komplettes Muster, schnell das Token damit verbundenen finden.

Leider, während eine solche Karte ein gutes Spiel ist der XML-Eingabeformat auf eine interne Datenstruktur zu konvertieren, ist es nicht ein gutes Spiel zu den Durchsuchungen Sie tun müssen. Beachten Sie, dass Sie nicht ganze Muster nach oben, aber das erste Zeichen eines Musters, eine Reihe von möglichen Token, gefolgt von einer Lookup des zweiten Zeichens eines Musters aus dem Satz von Mustern von diesem ersten produziert Lookup , und so weiter.

Also, was Sie wirklich brauchen, ist nicht eine einzige Karte, aber Karten von Karten von Karten, die jeweils durch ein einzelnes Zeichen eingegeben. Ein Nachschlag von „p“ auf der obersten Ebene sollten Sie eine neue Karte geben, mit zwei Schlüsseln: p, die C-PPA Token produzieren, und „alles andere“, die Herstellung des C-PA Token. Dies ist effektiv eine Trie-Datenstruktur.

Ist das sinnvoll?

Es kann helfen, wenn Sie zum ersten Mal durch das Schreiben des Parsing-Code beginnen, auf diese Weise: jemand vorstellen, sonst werden die Funktionen schreiben die Lookups zu tun, was Sie brauchen, und er ist ein wirklich guter Programmierer und kann so ziemlich jede Magie tun, dass Sie wollen. Das Schreiben der Parsing-Code, konzentrieren sich auf die Herstellung, dass so einfach und sauber wie möglich, die Schaffung der Schnittstelle, diese beliebige Funktionen verwenden, müssen (obwohl sie nicht trivial bekommen und ersetzt das Ganze mit einer Funktion!). Jetzt können Sie auf die Lookup-Funktionen suchen Sie mit am Ende, und das sagt Ihnen, wie Sie Ihre Datenstruktur zugreifen müssen, die Sie auf die Art der Datenstruktur führen, die Sie benötigen. Sobald Sie das herausgefunden haben, können Sie dann herausfinden, wie es zu laden.

Andere Tipps

Diese Methode funktioniert. - Ich bin nicht sicher, dass es effizient ist, aber es sollte funktionieren
würde ich den Standard-std :: map verwenden, anstatt Ihr eigenes System.
Es gibt Werkzeuge wie lex (oder flex), die dafür verwendet werden können. Die Frage wäre, ob Sie die lexikalische Analyse regenerieren können, dass es, wenn die XML-Spezifikation Änderungen bauen würde. Wenn die XML-Spezifikation nicht häufig ändern, können Sie in der Lage sein, Werkzeuge zu verwenden, wie lex das Scannen und Zuordnen leichter zu tun. Wenn die XML-Spezifikation an der Laune das unter Verwendung des Programms ändern kann, dann ist lex wahrscheinlich weniger geeignet.

Es gibt einige Einschränkungen - vor allem, dass sowohl lex und flex C-Code generieren, anstatt C ++

Ich würde auch auf Pattern-Matching-Technologie suchen - die Art von Sachen, die insbesondere Anwendungen egrep. Dies hat den Vorzug, etwas, das zur Laufzeit verarbeitet werden kann (weil egrep tut es die ganze Zeit). Oder Sie könnten für eine Skriptsprache gehen -. Perl, Python, ... Oder könnten Sie so etwas wie PCRE (Perl Compatible Regular Expressions) Bibliothek betrachten

Noch besser wäre es, wenn Sie die Boost-Bibliothek verwenden werden, gibt es immer die Boost-tokenizer Bibliothek -> http://www.boost.org/doc/libs/1_39_0/libs/tokenizer/index.html

Sie können einen regulären Ausdruck verwenden (vielleicht die boost :: regex-Bibliothek). Wenn alle Muster sind nur Zeichenfolge aus Buchstaben, ein regulären Ausdruck wie „(a | p | pp | u)“ würde ein gieriges Spiel finden. Also:

Führen Sie einen regex_search das obige Muster mit dem nächsten Spiel finden
Schließen Sie den Match-Text in Ihre std :: map die replace-Text zu erhalten.
Drucken der nicht-angepassten verbraucht Eingang und ersetzen Text zu Ihrer Ausgabe, dann wiederholen 1 auf dem verbleibenden Eingang.

Und getan.

Es kann ein wenig kompliziert erscheinen, aber der effizienteste Weg, dies zu tun ist, um eine Grafik zu verwenden, um ein State-Diagramm darzustellen. Zuerst dachte ich, boost.statechart würde helfen, aber ich dachte, es ist nicht wirklich angemessen war. Dieses Verfahren kann effizienter sein, dass eine einfache std :: map, wenn es viele Regeln sind, die Anzahl der möglichen Zeichen begrenzt und die Länge des Textes zu lesen sind recht hoch.

Wie auch immer, ein einfaches Diagramm mit:

0) erstellen Graph mit "Start" Vertex

1) gelesen XML-Konfigurationsdatei und Vertices erstellen bei Bedarf (Übergang von einem „Zeichensatz“ (zB „PP“) mit einem weiteren einem (zB „PPA“)). Innerhalb jedes Eckpunkts, Speichern einer Übergangstabelle, um den nächsten Scheitelpunkten. Wenn „Schlüsseltext“ abgeschlossen ist, Zeichen Vertex als endgültig und speichert den resultierenden Text

2) lesen jetzt Text und interpretieren die Grafik verwenden. Beginnen Sie an der "Start" Vertex. (*) Verwendet Tabelle ein Zeichen zu interpretieren und zu neuem Scheitelpunkt zu springen. Wird kein neuer Vertex ausgewählt worden ist, kann ein Fehler ausgegeben werden. Andernfalls, wenn neue Ecke final ist, drucken Sie den resultierenden Text und springt zurück Vertex zu starten. Gehen Sie zurück zu (*), bis es nicht mehr Text zu interpretieren.

könnten Sie boost.graph die Grafik darzustellen, aber ich denke, es ist für zu komplex ist, was Sie brauchen. Machen Sie Ihre eigene Darstellung.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow