??? Pattern Matching (ein wenig Theorie)

[FighterFigger]

Hallo (Ich hoffe ... es ist hier das richtige Forum dafür)

zu aller erst - der entsprechende Ausschnitt kann hier eingesehen werden.

Wir haben im Magazin ACM (Januar 1998)gelesen. Dabei haben wir in einem

Artikel von Nadia Nedjah folgende Formeln für die maximale Größe eines

deterministischen left-to-right matching Automaten gefunden:

height(Atree) <= sum(|pi|); mit i element [1,n]

breadth(Atree) <= prod(|pi| + 1); mit i element [1,n]

Wobei p die einzelnen gegebenen Muster sind, mit denen zu matchen ist

und |p| die Anzahl ihrer Symbole.

Unsere Frage:

Wie ist Gräf auf diese beiden Formeln gekommen? Sind die überhaupt

richtig? Wenn ja, kann mir irgendjemand diese Formeln anschaulich und

leicht verständlich erklären, so daß ich verstehe wie diese zustande

gekommen sind?

Besten Dank im Voraus

Volker Subat :marine

[Bako]

[OT]

Ich habs mal ins Algorithmik-Forum verschoben, das ist thematisch noch am Ähnlichsten.

[/OT]

[Klotzkopp]

@FighterFigger:

Auf welche Quelle verweist denn die [2] in dem Artikel?

[Orffi]

Um eine defintive Aussage zu geben, ist es zu wenig Text. Ich weiß zum Beispiel nicht was \pi nun genau ist. Es ist vom Prinzip her eine worst-case Abschätzung. Man möchte wissen, wie der Baum schlimmstenfalls aussehen kann.

Die Höhe eines Baumes ist der größte Abstand von der Wurzel zu irgendeinem Knoten. Wenn ich die Elemente von \pi untereinander Schreibe, dann habe habe ich die Höhe |\pi|. Wenn ich nun alle \pi_i, i\in{1,..,n} untereinander schreibe, dann hätte ich die Summe \sum_{i=1}^n\|\pi_i\|Und höher, das leuchtet wohl ein, kann der Baum nicht sein.

Wenn man sich die Breite des Baumes ansieht, dann ist bei einem binären Baum (sagt der Text was über die Baumart aus??) der Höhe n die Breite n+1. Wenn ich jetzt meinen Baum aus \pi_1 aufbaue und dann an jedes Blatt den Baum \pi_2 anhänge, dann komme ich auf die Breite des Baumes. Wenn ich zwei Bäume der Breite 3 und 4 habe, dann habe ich bei dem neuen Baum die Breite 12. Man kann das beweisen, vollständige Indunktion ist die Methode der Wahl, ist aber nicht sonderlich spannend.

HTH

Jan

[Crush]

Aufgrund der dürftigen Informationen kann man sicherlich nicht viel handfestes aussagen, höchstens spekulieren. Die Bezeichnung der Breite könnte genau so gut auch im Zusammenhang von Pattern-Mismatches stehen (verschieben des Vergleichsmusters).

[FighterFigger]

[2] verweist auf:

A. Gräf. Left-to-right tree pattern matching. In: Proceedings Rewriting Techniques and Applications

(RTA \'91, Como). Springer, Berlin, 1991, pp. 323-334.

Gräf selber hat diese 2 Formeln in seiner Diplomarbeit verwendet, antwortet aber leider nicht auf unsere ANfrage.

\pi ist jeweils ein "Item" in einem Patternset, in diesem Fall vom Ausgangpunkt, also die einzelnen gegebenen Muster.

|\pi| ist jeweils ihre Länge.

Das Problem ist, daß der Automat zwar wirklich nicht höher sein kann, als die Summation dieser, aber er kann auch nicht mal annähernd dies erreichen. Da frage ich mich, ob das dann wirklich der Worstcase ist, wenn mit zunehmenden Komplexität die Differenz zwischen berechnetem und tatsächlichem worst Case immer größer wird.

Schließlich ist das bei der Breite noch schlimmer, wo diese Differenz mehr als im Quadrat zu wachsen scheint.

Es ist leider so, daß der Schlimmste Fall, den ich mir vorstellen kann später nichtmal zu 5% den Wert der Rechnung erreicht.

Ich hoffte und hoffe, daß irgendjemand diese Formel schon einmal sah oder die Rechnung eines Baum-Automaten dieser Art bereits vornahm. Ich verlange aber nicht von euch, daß ihr jetzt extra neu alles herleitet

Mir scheinen Gräfs Formeln viel zu hoch gegriffen, und das ist gerade für eine worstCaseBetrachtung nicht gesund ... oder?

Danke aber für dieses Interesse, da mein Referat unbedingt fertig werden muß und niemand sonst sich diesem Problem auch nur mit einer Zeile widmete :e@sy :OD

[Orffi]

Ich kenne den Text nicht und kann halt nur, wie Crush schon meinte, spekulieren. \pi ist also ein Item, aber wie sind diese "Items" aufgebaut. Sie haben ja ein Länge, sind Items also Buchstabenketten? Viel Neues kann ich also nicht beisteuern.

Aber jetzt zur allgemeinen Analyse: Es gibt drei Fälle:

*worst case: Das ist wirklich der schlechteste Fall. Es geht hier nicht darum, wie häufig dieser auftreten kann, sondern nur wie der Baum aussieht, wenn "alles schief geht, was schief gehen kann". Wie auch immer das "Schiefgehen" aussieht.

*average case:

Hier geht es um die durchschnittliche Laufzeit (oder wie in diesem Fall: Baumgröße).

*best case:

Das Gegenteil vom worst case. Wenn also alles "zusammen paßt". Auch hier geht es nicht um Wahrscheinlichkeiten, wie oft er auftritt, sondern nur, wie beim worst case, wie er aussieht.

HTH

Jan

[FighterFigger]

worst Case ist mir klar, danke trotzdem für deine Antwort, denn sie Bestätigt es nochmals:

Original geschrieben von Orffi

wenn "alles schief geht, was schief gehen kann". Wie auch immer das "Schiefgehen" aussieht.

Aber der Automat muß nunmal diese Ausmaße erreichen können, im absolut schlimmstemn Fall. Und das ist nichtmal mit Augezukneifen und Abstraktion erreichbar - befürchte ich.

Ich werde weiter forschen, und sollte ich auf Ergebnisse stoßen, sie für das nächste Opfer dieser Aufgabe hier posten

Bis in Kürze @ Community

[FighterFigger]

Die Gruppe hatte nun eine annehmbare Lösung geliefert, die dann wohl zur Note 1 führte.

Eine Woche nach dem Referat hat dann auch Herr Prof. Gräf sich geäußert, und mit scheint, daß unsere Ansicht richtig war.

... soviel nur, um euch den Versprochenen Abschluß zu liefern.

Danke an alle, die sich hier dem Thema annahmen und an alle, die die Fachinformatiker.de-Community bilden

[Crush]

Und wo sind die Ergebnisse nun?

[FighterFigger]

Sie sind nicht druckreif formuliert, ich könnte bei Interesse aber gerne Die entwickelten Texte zuschicken ...

... aber >>Off Topic<<:

"Ego Shooter Server Admin" ... hmmmm

Das erinnert mich daran, daß ich "Team Shooter Platoon CoLeader" bin :bimei ... wie sieht es denn bei euch aus? ... gibt es öffentliche Angebote?

[Crush]

Kannst Du mir gerne zuschicken.

Was für Angebote?