Patternmatching mathematischer Ausdrücke

Martok · Verfasst: Sa 04.01.14 02:14

Mahlzeit!

Adventsrätsel vorbei, ihr möchtet doch bestimmt neue, komplizierte Probleme, oder? Super, ich hab da was

Das Problem an sich ist wie schon lange der Ausdrucks-Pattern-Matcher für Tau. Ich habe also zwei Ausdrücke, von denen einer (das Pattern) bestimmte freie Variablen beinhaltet. Ergebnis der gesuchten Funktion ist die Aussage, ob der Ausdruck passt und (mindestens) eine Zuordnung zu den freien Variablen, die passt.

In aufsteigender Komplexität der Aussage:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

Einfacher Fall: eine Variable->ein Element
> match(hold(1+2), pattern(hold(1+x),{x}))
= {x:=2}

Komplett andere Struktur
> match(hold(1+2), pattern(hold(x*y),{x,y}))
= <NULL>

Assoziativität: Variable kann auch Gruppen von Ausdrücken meinen
> match(hold(1+2+3+4), pattern(hold(1+x),{x}))
= {x:=2+3+4}

Kompliziertes Beispiel: Es gibt eine ganze Menge mögliche Zuordnungen, aber nur diese passt exakt
> match(hold(1+2+3+5+4+2+3), pattern(hold(1+x+y+4+x),{x,y}))
= {x:=2+3, y:=5}

1 und 2 sind noch einfach, 2 geht auch noch, aber dann wirds haarig. Besonders, wenn man auch noch Kommutativgesetze beachten will (was man natürlich will) gehen mir schlicht die Ideen aus.

Die Ausdrucksbäume sind relativ einfach: gleichrangige Operationen werden schon vom Parser zusammengesucht, so dass die Ausdrücke im letzten Beispiel so aussehen:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

Ausdruck:
  _plus()
    1
    2
    3
    5
    4
    2
    3
Pattern:
  _plus()
    1
    x
    y
    4
    x

Mein aktueller Ansatz findet sich hier, ich bin mir aber ziemlich sicher dass es damit nix wird und was anderes her muss. Deswegens die Frage hier.

Da ich weiß, dass hier einige schon mit Matheparsern gearbeitet haben... irgendwelche Ideen? Wenn mir jemand einen guten Algorithmus beschreiben kann, würde ich das sogar runterprogrammieren... aber mir fällt einfach nichts ein was alle Konstellationen versteht.

Clevere Ideen?

Viele Grüße,
Sebastian

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Xion · Verfasst: Sa 04.01.14 12:32

Klingt für mich wie das Problem des kleinsten gemeinsamen Unifikators (wobei nur auf einer Seite bei dir Variablen auftauchen).

Einen Algorithmus für dieses Problem gibt es bereits:
de.wikipedia.org/wik...fikation_%28Logik%29

Allerdings kann dieser nur Terme unifizieren, wie im ersten Beispiel, wo + die Trennung vorgibt und jede Variable genau einen Gegenpart hat, die +-Zeichen also als Trenner fungieren! Dein drittes Beispiel klappt damit nicht.

Ich würde in etwa so vorgehen:
Erstmal am Anfang gucken. Im ersten Beispiel stimmen 1 und + überein. x liegt am Ende und kann den ganzen Rest übernehmen -> klappt.

Im zweiten Beispiel ebenfalls:
x muss alles übernehmen, bis das erste * auftritt. Es tritt aber kein * auf. Also klappt das nicht. (oder du machst x=1+2 und y=1

).

Im dritten Beispiel:
1 und + stimmen überein. x kann den Rest übernehmen -> passt.

Im vierten Beispiel:
1 und + stimmen überein. Für x gibts jetzt mehrere Möglichkeiten:
x = 2
x = 2+3
...
x = 2+3+5+4+2+3
Wir haben aber noch das Terminal 4. Im hinteren Teil gibt es nur eine 4. Davor muss außerdem noch y kommen. Also gibt es für x nur die Möglichkeiten:
x = 2
x = 2+3

Rechnen wir erstmal mit 2 weiter. Dann haben wir:
hold(1+2+3+5+4+2+3)
hold(1+2+y+4+2)
Stimmt hinten schon nichtmehr überein. Klappt nicht!

Rechnen wir nun mit 2+3 weiter. Dann haben wir:
hold(1+2+3+5+4+2+3)
hold(1+2+3+y+4+2+3)
Nun können wir y=5 setzen und es -> passt
Das hätte man auch gleich sehen können, da die 4 übereinstimmen muss, nach der 4 nur x kommt, also x das Ende übernehmen muss.

Für größere Ausdrücke wird das natürlich sehr langsam, weil sich die Möglichkeiten der einzelnen Variablen multiplizieren. Für kleine Ausdrücke würde es aber wohl reichen, von vorne zu beginnen und jeweils alle Möglichkeiten für die Variablen zu testen. Verbesserungen sind natürlich möglich, aber die Komplexität verbessern diese wohl nicht.

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Martok · Verfasst: Sa 04.01.14 14:03

Moin!

Es ist doch immer gut, Leute zu kennen die den Spaß studiert haben :zustimm:

Xion hat folgendes geschrieben :

Einen Algorithmus für dieses Problem gibt es bereits:
de.wikipedia.org/wik...fikation_%28Logik%29

Weitergeklickt zu Prolog: ich weiß jetzt, wo Mathematica 90% seiner Wurzeln her hat... :shock:

Das erklärt, warum der Patternmatcher da so gut ist. Das war mal ein Prolog-Interpreter

Xion hat folgendes geschrieben :

Allerdings kann dieser nur Terme unifizieren, wie im ersten Beispiel, wo + die Trennung vorgibt und jede Variable genau einen Gegenpart hat, die +-Zeichen also als Trenner fungieren! Dein drittes Beispiel klappt damit nicht.

Und damit ist das leider am Thema vorbei, Assoziativität bedingt eben das.

Im Weiteren beschreibst du dann relativ exakt meinen unvollständigen Algorithmus, allerdings auf einer anderen Datenstruktur: Rekursives Generieren aller möglichen Variablenzuordnungen und dann rausfiltern der Kombinationen, die Widerspruchsfrei auf den Zielausdruck matchen. Den Operator braucht man aufgrund der ausgeplätteten Baumstruktur (vermutlich) nicht mehr prüfen, Unifikation von Listen auf Listen dürfte reichen. Der Rest ergibt sich dann, da alle nicht-atomaren Knoten Funktionsaufrufe sind.

Oh, und über das O(n!) für vollständige Kommutativität will ich gar nicht nachdenken. Das muss definitiv anders gehen; auch wenn wir mal von n < 10 ausgehen können ist das immer noch zu viel :roll:

Grüße,
Sebastian

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Xion · Verfasst: Sa 04.01.14 15:28

Ist folgende Unifikation auch erwünscht?

markieren

Quelltext

1:
2:

> match(hold(1+2+3+5+4+5), pattern(hold(1+x+y+4+x),{x,y}))
= {x:=2+3, y:=5}

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Martok · Verfasst: Sa 04.01.14 19:42

Bis auf Weiteres nicht, diese Transformation ist etwas was über Rules realisiert werden soll, deswegen darf die hier noch nicht erfasst werden. Mathematica macht das zwar, ich finde es aber erstmal sinnvoller den Ausdruck so wie er ist matchen zu können.

markieren

Quelltext

1:	> rule(hold(x+y), {x:='Number',y:='Number'}, hold(eval(x+y)))

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Martok · Verfasst: So 05.01.14 04:35

Update:

FinnO hat mich auf das Projekt symja - A Java computer algebra system hingewiesen. Das ist nicht nur interessant weil das aussieht wie Mathematica, sondern auch weil es OpenSource ist und der Patternmatcher schön raus-objektorientiert ist.

Zusammen mit der Erklärung von user profile icon

Xion zu Unifikation hab ich festgestellt, dass mein Code gar nicht so schlecht war - ich den nur nicht konsequent zuende gebaut hab und es ein paar Abkürzungen gibt, die mir massive Codeduplikation ersparen. Das tue ich grade, und es sieht gut aus. Alle Beispiele von oben funktionieren. Mir gehen sogar langsam die Testcases aus

markieren

Quelltext

1:
2:

> match(hold(1/2/3), pattern(hold(x/y),{x,y}))
= {x:=1/2, y:=3}

Update2: mit indirekter Hilfe von user profile icon

Horst_H ist jetzt auch der kommutative Teil fertig :zustimm:

Wenn man die Permutationen auf der Seite der freien Variablen berechnet ist das wesentlich weniger, da kaum ein Pattern mehr als 2 oder 3 freie Variablen hat. Unterschiedliche Belegungen sind an der Stelle sowieso äquivalent, so dass man einfach die billigere Lösung nehmen kann.

markieren

Quelltext

1:
2:

> match(hold(1+42+2+23+3), pattern(hold(3+1+2+y),{y}))
= {y:=42+23}

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme