Leiten Sie den minimalen regulären Ausdruck von der Eingabe ab

9

Ich habe einen entfernten "Agenten", der "Ja" oder "Nein" zurückgibt, wenn er eine Zeichenfolge ausgibt. Die Kommunikation mit diesem Agenten ist teuer, daher hoffe ich, eine Bibliothek zu finden, die es mir ermöglicht, bei positivem und negativem Feedback iterativ einen regulären Ausdruck zu erstellen, während ich über die Konstruktion intelligent bin. Dies würde mir erlauben, Antworten auf der sendenden Seite zu cachen.

Angenommen, wir fragen den Agenten mit "gut" ab und erhalten ein "Ja". Der anfängliche abgeleitete reguläre Ausdruck sollte "gut" sein.

Angenommen, ich frage dann mit "goop" ab und erhalte ein "ja". Ich würde erwarten, dass der abgeleitete reguläre Ausdruck "goo [dp]" ist, nicht "gut | goop".

Und so weiter.

Ich brauche keine Rückverfolgung oder irgendwelche anderen nichtlinearen Zeitoperationen in meiner abgeleiteten Regex. Vermutlich wäre der erzeugte Regex ein DFA unter der Haube. Kennt irgendjemand irgendwelche c / c ++ Bibliotheken für reguläre Ausdrücke, die dazu in der Lage sind? Alternativ wären Gründe, warum dies eine dumme Idee und bessere Lösungen für mein wirkliches Problem sind, auch nützlich.

    
tgoodhart 28.09.2011, 23:46
quelle

2 Antworten

5

Anstelle eines regulären Ausdrucks könnten Sie eine Trie verwenden.

Dann fährst du für jeden neuen String einen Knoten für jedes Zeichen. Ich vermute, dass Sie auch ein Marker-Zeichen für das Ende der Zeichenfolge möchten - sobald Sie dieses Zeichen erreicht haben, enthält der Knoten die Ja / Nein-Antwort.

    
Trejkaz 29.09.2011 00:01
quelle
0

Nun, es sei denn, ich verpasse etwas in Ihrer Situation, ich denke, dass das Gedächtnis billig genug ist, um einfach einen dummen Cache zu implementieren - sagen wir eine ungeordnete Karte von <std::string, bool> . Das ist nicht nur viel einfacher zu erstellen, es wird wahrscheinlich auch schneller sein, da Sie eine Hash-Karte erstellen. Der einzige Nachteil dabei ist, wenn Sie den Remote-Service mit einem Bazillion verschiedener Schlüssel abfragen würden, dann ist dies möglicherweise nicht der beste Ansatz.

    
Matt 28.09.2011 23:54
quelle

Tags und Links