Grössten gemeinsamen Teilstring aus 2 Strings?

[visionmaster]

$str1 = strtolower("CMC Concept - Der groesste Pool");
$str2 = strtolower("CMC    Conceptagentur fuer Marketing  und Communication GmbH");

Ich möchste den grössten gemeinsamen Teilstring herausfiltern der eben in beiden Strings vorhanden ist, obiges Bsp. sollte z.B. 'CMC Concept' ausgeben.

Wenn ich das Subtring kenn nach dem ich suchen soll, dann wäre das kein Problem. Aber wie finde ich eben den grössten Teilstring beider Strings?

Besten Dank!

[dedlfix]

Ich möchste den grössten gemeinsamen Teilstring herausfiltern der eben in beiden Strings vorhanden ist, obiges Bsp. sollte z.B. 'CMC Concept' ausgeben.

Vielleicht damit? http://de3.php.net/manual/en/function.strspn.php

[visionmaster]

Ich möchste den grössten gemeinsamen Teilstring herausfiltern der eben in beiden Strings vorhanden ist, obiges Bsp. sollte z.B. 'CMC Concept' ausgeben.

Vielleicht damit? http://de3.php.net/manual/en/function.strspn.php

strspn() hilft an dieser Stelle leider nicht weiter, da es eben nicht aufeinanderfolgende Zeichen findet.
"Ermittelt die Anzahl der Zeichen am Anfang von str1, die aus dem in str2 übergebenen Zeichenvorrat stammen."

Ich möchte eben den grössten gemeinsamen Teilstring herausfiltern der eben in beiden Strings vorhanden ist, obiges Bsp. sollte z.B. 'CMC Concept' ausgeben.

Vielen Dank!

[wahsaga]

hi,

Ich möchte eben den grössten gemeinsamen Teilstring herausfiltern der eben in beiden Strings vorhanden ist, obiges Bsp. sollte z.B. 'CMC Concept' ausgeben.

wenn's dafür nichts fertiges gibt (in PHP wäre mir nichts bekannt), solltest du dich mal mit backtracking beschäftigen.

gruß,
wahsaga

[visionmaster]

Hallo wahsaga,

Ich möchte eben den grössten gemeinsamen Teilstring herausfiltern der eben in beiden Strings vorhanden ist, obiges Bsp. sollte z.B. 'CMC Concept' ausgeben.

wenn's dafür nichts fertiges gibt (in PHP wäre mir nichts bekannt), solltest du dich mal mit backtracking beschäftigen.

backtracking? könntest du das näher erläutern damit ich weiss nach was ich suchen muss.

ich hatte vor beide strings mit explode in ein array von strings umzuwandeln. dann jedes array-element des arrays 1 durchgehen und mit jedem array-element des anderen arrays 2 mit strpos() vergleichen. liefert $pos != false dann mache mit dem nächsten array-element weiter. mach so lange weiter bis $pos == false.

da es sich möglicherweise nicht um den grössten gemeinsamen string hadelt, merke den gefunden string in einem neuen array zusammen mit der anzahl der array-elemente die hierfür notwendig waren.

mache mit array 1 weiter, dort wo man aufgehört hat und suche weiter. dann wiederholt sich das ganze.

wenn array 1 durchgelaufen wurde, beenden.

danke.

[wahsaga]

hi,

backtracking? könntest du das näher erläutern damit ich weiss nach was ich suchen muss.

na ja, suchen solltest du nach "backtracking" - das ist eine art von algorithmus, der bei solch vergleichsweise komplexen aufgabenstellungen ein(!) weg zu einer lösung sein kann.

gruß,
wahsaga

[Biesterfeld]

Hej,

da es dazu offensichtlich noch keine konkrete Antwort gab, möchte ich ganz kurz ein bekanntes Prinzip aus der Bioinformatik vorstellen. Dieses Problem ist allerdings in sofern noch komplexer, als dass auch Lücken zwischen den Teilstrings zugelassen werden. Von dieser Problemstellung aus, ist folgende Vorgehensweise sinnvoll, ob sie aber u.U. für obiges Problem nicht zu aufwendig ist, kann ich schlecht abschätzen.

Was gemacht wird, ist dass beide Strings in einer binären Matrix (einem sog. Dotplot) repräsentiert werden, um ihre Ähnlichkeit darzustellen.

Bsp.: String 1 Autobahnplanke
      String 2 Kaffeeautomat

A u t o b a h n p l a n k e
               K                         *
               a *         *         *
               f
               f
               e                           *
               e                           *
               a *          *        *
               u   *
               t     *
               o       *
               m
               a *          *        *
               t      *

Was nun nur noch getan werden muss, ist die Matrix nach existierenden  Diagonalen auszuwerten. Um den Aufwand zu reduzieren empfiehlt es sich eine minimale Vorgabe zu machen (z.b. soll der String mindestens 3 Zeichen enthalten)und Abbruchbedingungen einzuführen:
  Der längste bisher gefunde String ist 5 Zeichen lang
  Wenn Restdiagonalenlänge kleiner 5 brich ab!

Wenn man auf die graphische Repräsentierung verzichtet kann man sich natürlich den Schritt über die Matrix sparen, sich aber das Vorgehen dennoch anhand derer veranschaulichen. Das Problem ist O(nm)-komplex.

Beste Grüße
Biesterfeld

[lulu]

Huhu

Was nun nur noch getan werden muss, ist die Matrix nach existierenden  Diagonalen auszuwerten.

Interessanter Lösungsansatz.
Das Problem hat mich dann auch nicht ruhen lassen und ich habe mit
folgendem Verfahren eine recht brauchbare Lösung gebastelt.

1. Halbiere den String B (den kürzeren) und prüfe jeden Teilstring auf
Übereinstimmungen in A.

2. Wenn es keine Treffer gibt halbiere erneut usw.

3. Wenn es Treffer gibt werden die Teilstrings gespeichert (jeweils mit ihrer Position in A und B.

4. Benachbarte Strings werden "zusammengeklebt".

5. Dann noch zeichenweise an Anfang und Ende auf weitere Übereinstimmungen des Teilstrings in A mit B prüfen und diese ggf. mit Anfügen.

6. Dann den längsten Treffer auswählen.

Das klappt auch bei längeren Texten in einer akzeptablen Geschwindigkeit.

Zum Vergleich habe ich auch mal die "Holzhammer"-Methode umgesetzt die
über zwei for-Schleifen alle möglichen Teilstrings durchgeht.

Die ist natürlich erwartungsgemäß bei längeren Zeichenketten hoffnungslos überfordert, und braucht dann gerne mal ein paar Sekunden.

Jetzt bin ich noch neugierig wozu man das brauchen könnte.

Was mir einfiel sind "diff"-ähnliche Programme und Lehrer/ Dozenten
die gucken wollen wer bei wem wo wieviel abgeschrieben hat ;-)

Vielleicht liest der Visionmaster ja auch noch mit ?

Viele Grüße

lulu

[Biesterfeld]

Hej Lulu,

Die ist natürlich erwartungsgemäß bei längeren Zeichenketten hoffnungslos überfordert, und braucht dann gerne mal ein paar Sekunden.

Auch wenn es wahrscheinlich nicht von allgemeinem Interesse ist, aber wie schon erwähnt kann das ein elementares Problem der Bioinformatik sein.

<exkurs>

Die Idee ist DNA-Sequenzen im Detail zu vergleichen. Das Dogma der Molekulargenetik besagt, dass eine DNA-Sequenz in eine RNA-Sequenz und schließlich in eine Proteinsequenz übersetzt wird. Proteine sind von sehr großem Interesse in der Biologie, weil jedes eine Funktion hat die letztendlich in ihrer Gesamtheit über die Funktion der Zelle/des Organismus verantwortlich ist.

Nun erfindet die Natur das Rad nicht immer wieder neu, bzw. ist das eine Kernaussage der Evolutionstheorie, dass sich Verwandschaftsverhältnisse von eineinader ableiten. Der Überträger dieser Information ist die DNA.

Weil es nun sehr aufwendig sein kann jedem Protein eine Funktion zuzuordnen (da stecken z.T. ganze Mannjahre an Laborarbeite dahinter), ist die Idee der Bioinformatik, eine unbekannte DNA-Sequenz, die für das untersuchte Protein verantwortlich ist, mit der einer bekannten Sequenz (und eines bekannten Proteins) zu vergleichen.

Art und der Grad der Homologie können Aufschluss geben. Das Problem ist allerdings insofern komplex, als dass

* ein Protein gerne durch bis zu 1000 DNA Buchtaben (A C T G) kodiert wird
    (und noch darüberhinaus)
  * die Evolution nicht vorgegeben hat, dass verwandte Homologien lückenlos
    sein müssen oder keine Substitutionen enthalten dürfen
  * die vorhandenen Lücken/Substitutionen in Abhängigkeit verschiedener
    Parameter unterschiedliche Wirkung auf die Funktion haben können (von
    vollkommen irrelevant, über geringfügige Funktionsänderung oder
    Funktionsverlust, zu total anderer Funktion)
  * Die Sequenz mit einer inzwischen _sehr_ großen Datenbank abgeglichen
    werden muss

Den geneigten Leser verweise ich auf Wikipedia, Stichwort: Sequenz-Alignment

</exkurs>

Beste Grüße
Biesterfeld