Non-greedy matching
-
Heyo,
ich hab' in meinem aktuellen Projekt eine Token-Kette und möchte darin spezielle Patterns matchen. Wenn nun alle oder alle ausser eins der Matchers (oder wie heissen die?) greedy sind, dann ist der resultierende Algorithmus trivial (bzw. der naive Algorithmus ist effizient).
Wenn ich nun non-greedy Tokens habe, dann ist die Laufzeit des naiven Algorithmus , was nicht sehr zufriedenstellend ist, da sich normalerweise im Bereich von bis bewegt.
Wenn ich danach google, dann bekomme ich nur Regex-Zeug 'raus. Was ist ein effizienter (und nicht zu komplexer) Algorithmus, der das macht?
Gruss
-
Kannst du mal ein Beispiel zeigen?
-
ShadowClone schrieb:
Kannst du mal ein Beispiel zeigen?
Jap:
class CriterionT { public: typedef std::pair<SizeT, SizeT> LimitsT; protected: LimitsT Limits{ 1, 1 }; public: virtual bool IsMatch(InstructionT const& Instruction) = 0; LimitsT GetLimits() const { return{ this->Limits.first, std::max({ this->Limits.first, this->Limits.second, SizeT{ 1 } }) }; } }; class MatchMakerT { std::vector<std::shared_ptr<CriterionT>> Criteria; public: template<typename ForwardIteratorT> bool IsMatch(ForwardIteratorT First, ForwardIteratorT Last) { auto CriterionIter = this->Criteria.begin(); SizeT ConsecutiveMatches = 0; for(; First != Last && CriterionIter != this->Criteria.end(); ++First) { if((**CriterionIter).IsMatch(*First)) { if(++ConsecutiveMatches == (**CriterionIter).GetLimits().first) { ConsecutiveMatches = 0; ++CriterionIter; } } else { break; } } return CriterionIter == this->Criteria.end(); } template<typename ForwardIteratorT> ForwardIteratorT FirstMatch(ForwardIteratorT First, ForwardIteratorT Last) { for(; First != Last && !this->IsMatch(First, Last); ++First); return First; } };
Alles Unwichtige 'rausgestrichen, aber der Problemherd (
MatchMakerT::IsMatch
) ist zu sehen. Der Code funktioniert soweit; sprich, er matched alles korrekt aber eben nur greedily.Zur Erklärung wie
Limits
funktioniert / funktionieren sollte:Limits.first
ist die Anzahl der Tokens, die greedily gematched werden und die zwingend vorhanden sein müssen für einen kompletten Match, beim Rest trifft weder noch zu.Mir ist klar, dass diese Implementation von
FirstMatch
bei Weitem nicht optimal ist, aber das ist im Gegensatz zuIsMatch
unproblematisch. Der naive Algorithmus fürIsMatch
wäre, für alle zu matchenden TokensLimits.first
..Limits.second
durchzuiterieren (für greedy Tokens wäre das keine Schleife, daLimits.first = Limits.second
). Und dieser Algorithmus hätte meinen beschränkten komplexitätstheoretischen Fähigkeiten nach eine Laufzeitkomplexität von .
-
Kannst Du bitte nochmal versuchen die Aufgabenstellung zu formulieren? Eventuell mit einem Beispiel? Derzeit verstehe ich nur Bahnhof.
-
Jester schrieb:
Kannst Du bitte nochmal versuchen die Aufgabenstellung zu formulieren? Eventuell mit einem Beispiel? Derzeit verstehe ich nur Bahnhof.
Ok.
Angenommen, es existieren die Tokens A, B und C, dann könnte eine Tokenkette beispielsweise so aussehen: AABBABCCBA
Nun möchte ich verschiedene Patterns in dieser Tokenkette erkennen können. Beispielsweise würde das Pattern A beim Index 0 gefunden werden, das Pattern B bei 2, das Pattern AB bei 1 und das Pattern % (Wildcard, matched jedes Token, so wie . in Regex) auch bei 0. Das funktioniert alles schon mal im bestehenden Code.
Was es nun noch geben sollte, ist, dass ich den einzelnen Tokens im Pattern Limits zuordnen kann. Beispielsweise wird das Pattern C{2,2} hier AABBABCCBA gematched, genau so wie auch das Pattern CC. In der Tat gibt es zwischen C{2,2} und CC, resp. zwischen C{1,1} und C keinen Unterschied. Ergo sind die Limits eines Tokens auch immer standardmässig {1,1}, sind sie nicht explizit spezifiziert.
Diese Syntax ist ähnlich zu Regex. Beispielsweise ist B%{0,∞}B äquivalent zu B.*?B und B{2,3} ist äquivalent zu B{2,3}?
Ein paar Beispiele:
AB{1,∞}A ist hier: AABBABCCBA
A%{1,∞}A ist hier: AABBABCCBA
B%B ist hier: AABBABCCBA
B%{0,∞}B ist hier: AABBABCCBA
B%{1,∞}B ist hier: AABBABCCBA
B%{4,∞}B ist hier: AABBABCCBA
Kurz zusammengefasst: In diesen geschwungenen Klammern bedeutet die erste Zahl, wie viele dieser Tokens mindestens und absolut zwingend vorkommen müssen, und die zweite Zahl, wie viele davon maximal vorhanden sein können.
Wie im drittletzten Beispiel zu sehen ist, versucht der Matcher möglichst wenig von %{0,∞} zu matchen (lazy / non-greedy). Wäre er greedy, so wäre zwischen dem drittletzten, dem zweitletzten und dem letzten Beispiel kein Unterschied.Spezialfall:
B%{0,∞}B%{0,∞}C ist hier: AABBABCCBA und der Match sieht ohne die Wildcards so aus: AABBABCCBA.
Wenn mehrere solcher Limits vorhanden sind, dann wird von rechts nach links vorgegangen. Sprich, wenn ein Match existiert, sodass man nur das rechte Limit "ausschöpft", dann ist das der Match.Meine Frage ist, wie ein effizienter Algorithmus aussähe, der Patterns dieser Art matched. Der naive Algorithmus wäre es, für jedes Limit eine Laufvariable zu erstellen und sie dann von rechts nach links zu inkrementieren:
In B%{0,∞}B%{0,∞}C sähen die Laufvariablen so aus:
1,0,1,0,1
1,0,1,1,1
1,0,1,2,1 Match
1,0,1,3,1 Match
1,0,1,4,1
1,0,1,5,1 Pattern zu gross, gleiches Verhalten, als wenn die Limits verlassen würden
1,1,1,0,1
1,1,1,1,1
...
1,2,1,0,1 Match
1,2,1,1,1 Match
...
Wie ich aber erwähnt habe, ist dieser Algorithmus sehr ineffizient.
-
Mal ne naive Frage: Was genau stimmt mit Regex nicht, wenn das Feature anscheinend ein Subset von Regex ist? Ist Regex zu lahm? Dann wirst du das wahrscheinlich nicht schneller hinkriegen, weil hier viel Erfahrungen miteingeflossen sind.
-
Ich arbeite mit
InstructionT
s, nicht mitchar
s, wie im Snippet zu sehen ist. Aber vielleicht kann man tatsächlich 'nstd::regex_traits<InstructionT>
schreiben, dass das funktioniert. Hat jemand schon 'mal 'was Ähnliches gemacht?
InstructionT
ist ein POD-Typ, bestehend aus einerenum class
und einerunion
. Deroperator==
ist darauf definiert.
-
asfdlol schrieb:
Ich arbeite mit
InstructionT
s, nicht mitchar
s, wie im Snippet zu sehen ist. Aber vielleicht kann man tatsächlich 'nstd::regex_traits<InstructionT>
schreiben, dass das funktioniert. Hat jemand schon 'mal 'was Ähnliches gemacht?
InstructionT
ist ein POD-Typ, bestehend aus einerenum class
und einerunion
. Deroperator==
ist darauf definiert.Der Ansatz scheint mir sinnvoll und hier würde ich auch meine Zeit und Energie investieren. Tutorials konnte ich leider keine finden. Evtl. kannst du auf den Code der Standard-Libs zugreifen und dort die Implementierungen für
char
undwchar_t
einsehen.
-
der algorithmus nennt sich "optimal parsing" (falls ich die aufgabenstellung richtig verstand).