3. Non-greedy matching

Non-greedy matching

  • F

    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 mm non-greedy Tokens habe, dann ist die Laufzeit des naiven Algorithmus O(nm)O(n^m), was nicht sehr zufriedenstellend ist, da sich nn normalerweise im Bereich von 10310^3 bis 10510^5 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

    0
  • ?

    Kannst du mal ein Beispiel zeigen?

    0
  • F

    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 zu IsMatch unproblematisch. Der naive Algorithmus für IsMatch wäre, für alle zu matchenden Tokens Limits.first .. Limits.second durchzuiterieren (für greedy Tokens wäre das keine Schleife, da Limits.first = Limits.second ). Und dieser Algorithmus hätte meinen beschränkten komplexitätstheoretischen Fähigkeiten nach eine Laufzeitkomplexität von O(nm)O(n^m).

    0
  • J

    Kannst Du bitte nochmal versuchen die Aufgabenstellung zu formulieren? Eventuell mit einem Beispiel? Derzeit verstehe ich nur Bahnhof.

    0
  • F

    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.

    0
  • ?

    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.

    0
  • F

    Ich arbeite mit InstructionT s, nicht mit char s, wie im Snippet zu sehen ist. Aber vielleicht kann man tatsächlich 'n std::regex_traits<InstructionT> schreiben, dass das funktioniert. Hat jemand schon 'mal 'was Ähnliches gemacht?
    InstructionT ist ein POD-Typ, bestehend aus einer enum class und einer union . Der operator== ist darauf definiert.

    0
  • ?

    asfdlol schrieb:

    Ich arbeite mit InstructionT s, nicht mit char s, wie im Snippet zu sehen ist. Aber vielleicht kann man tatsächlich 'n std::regex_traits<InstructionT> schreiben, dass das funktioniert. Hat jemand schon 'mal 'was Ähnliches gemacht?
    InstructionT ist ein POD-Typ, bestehend aus einer enum class und einer union . Der operator== 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 und wchar_t einsehen.

    0
  • R

    der algorithmus nennt sich "optimal parsing" (falls ich die aufgabenstellung richtig verstand).

    0
Anmelden zum Antworten