Wiederkehrende Patterns in einem Text finden

[Meflin]

Moin moin!

Ich bin mir sicher, es gibt dazu mindestens fünf Algorithmen von klugen Köpfen, aber meine Suche blieb erfolglos.

Gegeben sei ein Text / string, beispielsweise

Zitat:

Die Poincaré-Vermutung galt lange als das bedeutendste ungelöste Problem in der Topologie, einem Teilgebiet der Mathematik. Sie ist benannt nach Henri Poincaré und wurde von diesem 1904 formuliert. Im Jahr 2000 zählte das Clay Mathematics Institute die Poincaré-Vermutung unter die sieben bedeutendsten ungelösten mathematischen Probleme und lobte für die Lösung einen Preis von einer Million US-Dollar aus.

Die Fett markierten Teile (exemplarisch ausgewählt) sollen gefunden werden, also alle Teilstrings einer beliebigen Länge oder mehrerer beliebiger Längen X, die in dem gegebenen Text öfter vorkommen.

Das Problem dabei: man hat keinen Suchpattern, da man ja vorher sozusagen nicht weiß, nach was man überhaupt suchen muss.

Wie geht man da vor?

[tr909]

Ich habe mal folgendes gebastelt. Nicht geprüft und von der Performence her wohl auch nicht so doll. Zwei memos. In memo1 steht der zu untersuchende Text, in memo2 wird pro übereinstimmung einmal das Suchpattern ausgegeben.
lenSub gibt die lenge des Suchpatterns an. In diesem beispiel 3. Zu beginn werden die ersten 3 Zeichen kopiert und dann mit allen Zeichenketten der Länge drei des Textes verglichen. Und so weiter, wobei das Suchpattern jedes mal einen Schritt im Text weiter geht.

Delphi-Quellcode:

procedure TForm2.Button1Click(Sender: TObject);
var
  s : string;
  I: Integer;
  sub : string;
  comp : string;
  j: Integer;
  lenSub : integer;
begin
  s := '';
  lenSub := 3;
  for I := 0 to memo1.lines.count - 1 do
    s := s + memo1.lines[i];
  for I := 1 to length(s)-lenSub-1 do
  begin
  sub := copy (s,i,lenSub);
  for j := lenSub+1+i to length(s)-lenSub-1-i do
  begin
    comp := copy (s,j,lenSub);
    if UpperCase(comp) = UpperCase(sub)  then
      memo2.Lines.add(sub);
  end;
  end;
end;

Gruß
tr909

*edit* Besser wäre wohl folgender Ansatz. Zuerst alle möglichen ungleichen Pattern einer Länge ermitteln. Dann mit diesen Werten eine mit Hilfe von z.B. dem Knuth-Morris-Pratt-Algorithmus suchen.
*edit*

[SirThornberry]

du hast sozusagen mehrere suchpaddern?! Wie willst du das Ergebnis aufbereitet haben? Willst du nur Positionen wissen wo die Abschnitte auftauchen oder willst du auch im Ergebnis haben was an der Stelle gefunden wurde?

[Meflin]

Zitat von SirThornberry:

du hast sozusagen mehrere suchpaddern?! Wie willst du das Ergebnis aufbereitet haben? Willst du nur Positionen wissen wo die Abschnitte auftauchen oder willst du auch im Ergebnis haben was an der Stelle gefunden wurde?

Es sind nicht nur mehrere, sondern sogar verdammt viele Patterns. Eigentlich hat man ja garkeinen Pattern gegeben, sondern die Patterns werden gesucht

Ob Position oder auch Wert dürfte doch für die Vorgehensweise ziemlich egal sein oder? Mir geht es hauptsächlich darum, die Patterns zu zählen, und möglichst lange Patterns zu finden, die möglichst oft in einer gegebenen Zeichenkette vorkommen.

@tr909: der Ansatz wird zweifelsfrei funktionieren. Aber wenn der Text länger wird, muss das verdammt ineffizient werden

[SirThornberry]

es sind keine pattern gegeben sondern werden gesucht? Das verwirrt mich. Man kann doch nicht nach etwas suchen wenn man nicht weiß wonach man sucht.

[negaH]

Gut dann formulieren wir die Aufgabe um.
Gegeben ist ein beliebig langer Text. Gesucht ist ein Baum der die im Text enthaltenen Redundanzen anzeigt.

Hat man einen längeren Text auf diese Art&Weise analysiert, zb. eben diesen Baum mit allen Redundanzen im Text erzeugt, so hat man die perfekte verlustfreie Komprimierung !

Ich schlage vor du sucht bei den Komprimieralgorithmen, zb. Huufman Tree angewendet auf lange Textphrasen statt nur Buchstaben.

Als Lösungsansatz folgender

Ein Tree, bei dem quasi alle vkommenden Buchstaben des Alphabethes auf einem Level liegen. Ausgehend von einer Node im Baum stellen deren Childrens quasi ein Wort im Text dar.

Nun wird der Text einfach sequenitell Buchstabe für Bichstabe durchgegangen. Es gibt fest definierte Texttrennzeichen/Satzzeichen. Man fügt für jeden Buchstaben des Textes eine Node in den Baum ein. Je tiefer die Äste im Baum werden desto länge die gefundenen Phasen. Hm, das ist denoch keine gute Lösung, kompliziertes Problem das du da aufwirfst.

Gruß Hagen

[tr909]

[quote="Meflin"]

Zitat von SirThornberry:

@tr909: der Ansatz wird zweifelsfrei funktionieren. Aber wenn der Text länger wird, muss das verdammt ineffizient werden

Deshalb würde ich auch eher zu dem Ansatz den ich editiert habe tendieren. Ist halt nur die Frage ob man das "herausfinden" der Pattern effektiver machen kann. Danach kann man einen "beliebigen" effizienten Pattern-Match-Algo verwenden. Ich habe das ganze ja sequentiell durchsucht. Da ist KMP schon um Längen schneller.

Gruß
tr909

[Meflin]

Zitat von negaH:

Hm, das ist denoch keine gute Lösung, kompliziertes Problem das du da aufwirfst.

Oha, wenn du das sagst ...

Danke für die Anregung, werde ich mir mal näher zu Gemüte führen.
Btw: Ich brauche das für keinen bestimmten Zweck. Dieses Problem überdenke ich im Moment sozusagen "Just for Fun"

@tr909: Ich meinte auch den Ansatz im Edit Die Pattern-Matching-Algorithmen sind sicher nicht mehr groß Optimierungsfähig, aber allein der Ansatz, erstmal ALLE MÖGLICHEN Patterns zu bilden erscheint mir zu aufwendig!

[Gausi]

Wenn man weiß, welche Pattern man finden möchte, gibt es diverse schnelle Algorithmen.

Da wäre zum einen der Aho-Corasick-Algorithmus (ca. 1977) (Prinzip vergleichbar mit dem Algorithmus von Knuth, Morris und Pratt, nur auf Multipattern erweitert). Dann gibts Commentz-Walter (ca. 1979), den ich nocht nicht richtig verstanden habe, und den Wu-Manber-Algorithmus (ca 1994), der in den meisten Fällen am schnellsten ist. Wenn extrem viele Pattern simultan gesucht werden sollen, dann vielleicht noch den Set-Backward-Oracle-Matching-Algorithmus (ca. 1999) anschauen. Obs danach nocht interessante Weiterentwicklungen gibt, weiß ich nicht.

Um die Muster zu bestimmen, die man sucht, könnte man den Text in eine Baumstruktur speichern, die ca. O(n^2) Platz benötigen wird. An den Knoten sind die Zeichen des Textes gespeichert. Zuerst fügt man den gesamten Text zeichenweise ein, dann den Text ohne das erste Zeichen, dann ohne das zweite etc. Das einfügen immer so, dass schon vorhandene Kanten weitergenutzt werden, und dass ein Weg von der Wurzel zu einem Blatt ein Suffix des Textes ist. Beim Aufbau merken, wenn eine Kante mehrfach benutzt wird und diesen Wert an der Kante speichern.
Den fertigen Baum sucht man dann ausgehend von der Wurzel möglichst lange Wege mit hohen Kantenwerten, und erstellt daraus seine Musterliste.
Die Idee ist bei mir noch nicht ganz ausgereift, aber das mit dem Baum hat Hagen ja schon eingeworfen, so komplett falsch kann das also nicht sein

[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