STATISTIK-FORUM.de

[Willy]

Hallo zusammen

Ich habe wieder ein neues Problem. Evtl. fällt jemandem was kluges dazu ein. Folgende Problemstellung:

Ich habe eine sehr lange Zeichenkette (die Anzahl der Zeichen liegt im zweistelligen Millionenbereich) die aus ca. 50-100 verschiedenen Zeichen besteht. Ich will innerhalb der Zeichenkette ähnliche Sequenzen finden, die ca. 20-200 Zeichen lang sind.

Natürlich könnte man das Problem lösen, indem man mit einem einfachen Distanzmaß (z.B. Levenshtein-Distanz) alle möglichen Sequenzen miteinander vergleicht. Aber das wäre natürlich ein extremer Rechenaufwand. Ich habe versucht den Suchraum zu begrenzen indem ich nur Zeichenketten miteinander vergleiche die mit der selben Dreierfolge beginnen und enden und zwischen 20 und 200 Zeichen lang sind. Aber selbst so würde es noch immer Tage dauern.

Weiß jemand eine bessere Lösung?

MfG
Willy