Wörter und Sätze suchen

[Xin]

So, eins der nächsten Projekte, an die ich mich setzen werde ist eine Art Satzsuche.

Dabei gibt es ein vergleichsweise einfaches Problem: Es gibt keine Information, wie lang oder groß ein Satz ist. Es geht lediglich darum, Textbausteine einer gewissen Länge wieder zu finden.

Beispiel: Es gibt den Ursprungstext:
"Die Sonne scheint, die Wiese ist grün und der Ball ist rund."

Dieser Satz wird geändert in:
"Die Sonne scheint, der Himmel lacht, die Wiese ist grün und der Ball ist rund."
Hier möchte ich herausfinden, dass "der Himmel lacht, " hinzugekommen ist.

"Die Sonne scheint und der Ball ist rund."
Hier möchte ich herausfinden, dass "die Wiese ist grün" entfernt wurde.


"Die Sonne scheint, der Himmel lacht und der Ball ist rund."
Hier möchte ich herausfinden, dass "die Wiese ist grün" entfernt wurde und "der Himmel lacht" eingefügt wurde.


"Die Sonne scheint, die Wiese ist grün, der Himmel lacht und der Ball ist eckig."
", der Himmel lacht" hinzu, "rund" raus, "eckig" rein.


Und jetzt noch etwas gemeines:
"Die Wiese ist grün, die Sonne scheint und der Ball ist rund."
Hier möchte ich erfahren, dass "Wiese ist grün" und "Sonne scheint" verschoben wurde.

Ein Wort ist immer etwas, was zwischen Leerzeichen, Tabs, Punktion, Zeilenanfang und -ende steht.
Grundsätzlich könnte ein "Satz" aus einem Wort bestehen. Ich brauche eine recht klare Änderungsbeschreibung eines Strings.

Wie würdet ihr so einen Algorithmus angehen? ^^

[cloidnerux]

http://blog.notdot.net/2007/4/Damn-Cool ... 1-BK-Trees