Wiederkehrende Patterns in einem Text finden

[negaH]

Zitat:

Oha, wenn du das sagst

Ja. Die Sache ist die das das Problem NP vollständig sein könnte, also ein sehr hartes Problem. Garnichtmal das was am Ende als "Patternmatching Baum" rauskommt, das ist immer endlich, sondern die Frage wie lange man zur Erstellung des Baumes benötigt. Theoretisch ist es so das wenn der Text N Buchstaben hat dann benötigen wir minimal O(N^2 * Irgendwas(N)) schätze O(N^2 * Ln2(N)) oder so.

Auf alle Fälle ist es so das man den fertigen Baum einfach nach der Länge*Häufigkeit des Patterns sortiert. Dann nummertiert man diesen Baum durch, speichert diese Nummern + Positionen des Patterns plus sammt Baum in einer Datei und hat so den Text maximal komprimiert.

Gruß Hagen