Sehr geehrte Expertin, sehr geehrter Experte,
ich möchte eine Funktion schreiben, mit der ich innerhalb eines n-langen Strings gleiche Zeichenfolgen bestimmen kann. Wenn es dann noch geht, wäre es gut, wenn man auch den Abstand mit ausgeben könnte. Also es soll nicht nach etwas gesucht werden, dass ich schon kenne, sondern nach etwas, wo ich nicht weiß, wie es aussieht.
Ich bedanke mich schon einmal im Voraus für Deine Hilfe.
MfG Ascawath
Hallo, wenn zwischen den Zeichenfolgen Lerrzeichen vorhanden sind, kann man den String in ein array umwandeln.
<?php $str = "Hello world. It's a beautiful day.";Hallo Friedrich,
wenn ich jetzt den String in einem Array übertragen habe, wie suche ich dann die gleichen Zeichenfolgen?
Es kann ja sowohl unbestimmt lang sein, aber mindestens 2 Zeichen lang sein. Und die Buchstaben können stehen ja auch nicht fest.
MfG Ascawath
Durch Google habe ich das gefunden:
http://stackoverflow.com/questions/6281255/php-find-…
Zudem glaube ich, dass algorithmisch die Verwendung von Tries gut geeignet ist:
http://de.wikipedia.org/wiki/Trie
Da scheint es noch nichts bei PHP eingebaut zu geben. Zudem ist PHP sicher nicht die schnellste Sprache üfr solche Operationen. Aber hier habe ich Code gefunden. Vielleicht hilft das:
http://phpir.com/tries-and-wildcards
Viel Erfolg!
Hallo
sicher wäre der erste Ansatz, den String in ein Array von Buchstabenfolgen gleicher Länge zu zerlegen.
Und dann durch das Array gehen und mit preg_match das Vorkommen im String der einzelnen Zeichenfolgen untersuchen.
Das Vorkommen an einer bestimmten Position, also Abstand, läßt sich dann relativ leicht prüfen.
Komplex wird es, wenn man nicht weiß, wie lange diese Teilstrings sein können.
Weil - so wie ich es verstehe, können die ja 1-n Buchstaben lang sein.
Also wie man das vernünftig machen kann, da müßte ich jetzt auch einen Tag mich rein verkopfen.
Dazu fehlt mir leider gerade die Zeit.
Vielleicht gibts auch ne einfache Lösung.
Bekannt ist mir keine.
Gruß, Regina
Hallo Ascawath,
diese Frage ist nicht gerade trivial zu beantworten.
Mein Vorschlag wäre, mal nach Algorithmen Ausschau zu halten, die dabei helfen können. Vielleicht ein Suffix Tree?
Suchbegriffe wären „algorithm“, „string“, „groups“ und so weiter.
Leider habe ich gerade keine Zeit, die Suche selbst durchzuführen, das Thema ist sehr interessant.
Viel Erfolg wünsche ich!
Hallo,
ehe es zu Missverständnissen kommt, wäre ein Beispiel
nicht schlecht 
)
Gruß
Mirko Meichsner
Danke für die Info.
Eine Frage hattest du ja nicht, oder?
Hallo,
Nach etwas suchen, von dem man nicht mal weiß, wie es aussieht, ist etwas schwierig. Könntest du das Problem genauer, am Besten mit einem Beispiel, angeben? Die Frage ist ja auch, ab wann für dich eine Zeichenkette beginnt. Ich interpretiere das so: Bei der Eingabe von „aabab“ gibt der Algorithmus die Zeichenketten [„a“, „b“, „ab“] aus. Für den Abstand wäre die Frage, welchen Abstand du willst: z.B. den kleinsten zwischen zwei gleichen Zeichenketten, die maximale Spannweite (letztes Auftreten - erstes Auftreten)…
Ich hab leider nicht verstanden, was deine Frage ist. Vielleicht kannst du das ja genauer fassen.
Ein Beispiel wäre zudem sehr hilfreich
Hi,
Danke für deine schnelle Antwort, ich werde mal suchen, vielleicht hilft es mir ja.
MfG Ascawath
Hallo,
Ok.
Angenommen ich habe einen String
$string = „Dvc hdoe dcg zsa Ooft nrr lrwzsfei fogv dvcf hovnz Zanmuiio ddo ixr pmytrvwzizbg ckoe khcc jimuyixr fpxxtdyaizbg Dmu wsa bofpvxat yo zc dvxa veph gvrfvvcc suiugijxvemoa rsed ead xvccd nvmu yoe ckrladr vlfpvmxei jimn dvc wvoee tn ryul wnl wrgv zizc bzsz ikrcccgei iemchcc fogv en xlvzrni hny aixrg zsa iyph frrrserzxqemof Zbtewxvs bnunubmhoa Ikwa rnt nnni jocv ndmut qnnu fo qrkgkcpo jiz vcc rs wvr oehjpst rnbz“;
Ist jetzt zwar etwas lang, erfüllt aber sein Zweck.
Jetzt möchte ich in diesem String alle gleichen Zeichenfolgen, mit deren Position ausgeben lassen.
Ein Beispiel:
Am Anfang kommt „DVC“ vor und etwas später folgt „DVCF“ (Groß-, Kleinschreibung nicht berücksichtigt). Jetzt möchte ich deren Position im String haben, also quasi die erste Position des letzten gefundenen subtrahiert von der Position der ersten gefundenen Kette, ist ja dann das Intervall.
Gibt es dafür quasi ein Befahl, oder eine Reihe von Befehlen, um das zu realisieren?
MfG Ascawath
Hallo,
Ok.
Angenommen ich habe einen String
$string = „Dvc hdoe dcg zsa Ooft nrr lrwzsfei fogv dvcf hovnz Zanmuiio ddo ixr pmytrvwzizbg ckoe khcc jimuyixr fpxxtdyaizbg Dmu wsa bofpvxat yo zc dvxa veph gvrfvvcc suiugijxvemoa rsed ead xvccd nvmu yoe ckrladr vlfpvmxei jimn dvc wvoee tn ryul wnl wrgv zizc bzsz ikrcccgei iemchcc fogv en xlvzrni hny aixrg zsa iyph frrrserzxqemof Zbtewxvs bnunubmhoa Ikwa rnt nnni jocv ndmut qnnu fo qrkgkcpo jiz vcc rs wvr oehjpst rnbz“;
Ist jetzt zwar etwas lang, erfüllt aber sein Zweck.
Jetzt möchte ich in diesem String alle gleichen Zeichenfolgen, mit deren Position ausgeben lassen.
Ein Beispiel:
Am Anfang kommt „DVC“ vor und etwas später folgt „DVCF“ (Groß-, Kleinschreibung nicht berücksichtigt). Jetzt möchte ich deren Position im String haben, also quasi die erste Position des letzten gefundenen subtrahiert von der Position der ersten gefundenen Kette, ist ja dann das Intervall.
Gibt es dafür quasi ein Befahl, oder eine Reihe von Befehlen, um das zu realisieren?
MfG Ascawath
Hallo,
Ok.
Angenommen ich habe einen String
$string = „Dvc hdoe dcg zsa Ooft nrr lrwzsfei fogv dvcf hovnz Zanmuiio ddo ixr pmytrvwzizbg ckoe khcc jimuyixr fpxxtdyaizbg Dmu wsa bofpvxat yo zc dvxa veph gvrfvvcc suiugijxvemoa rsed ead xvccd nvmu yoe ckrladr vlfpvmxei jimn dvc wvoee tn ryul wnl wrgv zizc bzsz ikrcccgei iemchcc fogv en xlvzrni hny aixrg zsa iyph frrrserzxqemof Zbtewxvs bnunubmhoa Ikwa rnt nnni jocv ndmut qnnu fo qrkgkcpo jiz vcc rs wvr oehjpst rnbz“;
Ist jetzt zwar etwas lang, erfüllt aber sein Zweck.
Jetzt möchte ich in diesem String alle gleichen Zeichenfolgen, mit deren Position ausgeben lassen.
Ein Beispiel:
Am Anfang kommt „DVC“ vor und etwas später folgt „DVCF“ (Groß-, Kleinschreibung nicht berücksichtigt). Jetzt möchte ich deren Position im String haben, also quasi die erste Position des letzten gefundenen subtrahiert von der Position der ersten gefundenen Kette, ist ja dann das Intervall.
Gibt es dafür quasi ein Befahl, oder eine Reihe von Befehlen, um das zu realisieren?
MfG Ascawath
Ich hab leider nicht verstanden, was deine Frage ist.
Vielleicht kannst du das ja genauer fassen.
Ein Beispiel wäre zudem sehr hilfreich
Hi,
Danke für deine schnelle Antwort. Ich werde es mal versuchen, vielleicht finde ich ja eine Möglichkeit.
MfG Ascawath
Hi,
Danke für deine schnelle Antwort.
Ich werde es mal damit probieren, wenn ich etwas finde.
Danke.
MfG Ascawath
Hallo,
Habe gerade keine Zeit, um mir genauere GEdanken zu machen, aber spontan würde ich eine Schleife basteln, in der mit strpos oder vergleichbaren Funktionen (php.net) der n-zeichen lange String durchgeforstet wird, im Falle eines Fundes, einfach ab der Fundstelle +1 weiter suchen.
Dort könnte man dann auch die einzelnen Fundstellen in ein Array packen und anschliessend die Abstände ausrechnen.
Evtl. gibts auch nen einfacheren Weg, nur das wäre das erste was mir einfällt dazu.
MfG
Hallo,
da es ja nicht bekannt ist wo sich der erste Fund befindet, müsste man die Sache recrusiv angehen.
Das geht nur zeichenweise.
So nach dem Motto:
Die Frage die sich stellt, ab wie viel Zeichen
aufgehört werden soll und sind zwei Zeichen schon eine Übereinstimmung.
Das währe dann ein mehrdimensionales Array mit einigen Schleifen.
Meines Wissens gibt es keine vordefinierte
Function in PHP.
Gruß
Mirko Meichsner
Hallo,
es gibt ja schon ein paar Antworten. Ich versuche mal einige theoretische Hinweise zu geben. Die Implementierung solltest du selbst machen, da es doch etwas aufwändig ist. Vorgefertigt gibt es hier nichts, du kannst aber einige Funktionen nutzen um dir die Ähnlichkeitssuche zu vereinfachen.
Ich würde zunächst mal den String in ein Array überführen. Als Trennzeichen für die einzelnen Elemente kannst du " " nehmen, da ich mal davon ausgehen, das dich leerzeichen nicht interessieren.
Du musst dir jetzt erstmal merken, welche Positionen die jeweiligen Teile im Gesamtstring haben, das geht zB über ein Array unter Nutzung der Zeichenkettenlänge (Vergiss die Leerzeichen dabei nicht zu addieren)
Jetzt müsstest du dir eine Tabelle bauen, die jede Zeichenkette im Array mit jeder anderen Vergleicht. Die Tabelle wird in diesem Zusammenhang vermutlich ein mehrdimensionales Array sein.
Da du ja nicht nur 1:1 Vergleichen willst, sondern auch ähnliche Zeichenkettenn haben willst (wie in deinem Bespiel; DVC und DVCF sind nicht gleich sondern ähnlich) würde ich dir empfehlen, dafür einen vordefinierten Algorithmus zur Ähnlichkeitssuche nehmen, z.B. LEVENTHSTEIN. Dieser rechnet dir die Distance zwischen den beiden Zeichenketten deiner Tabelle aus.
Es gibt noch eine paar andere Algorithmen, in PHP ist dieser aber definitiv vorhanden und bietet recht brauchbare Ergebnisse. Vermutlich musst du hier aber auch ein wenig experimentieren.
Wenn du das Ergebnis hast, musst du dich eigentlich nur noch entscheiden, welche Distanz du jetzt maximal für ähnlich akzeptieren würdest.
Das Ergebnis kannst du jetzt ausgeben und dir für jede Kombination die jeweiligen Positionen aus deiner zweiten Tabelle ausgeben lassen.
Vor dem Ausgeben wäre es vielleicht noch geschickt, die Pärchen zu sortieren und die Dupleten zu entfernen.
Wenn du das ganze dann noch in eine Funktion packst, hast du deinen Befehl
Ich hoffe ich konnte dir damit ein Stück weiterhelfen.
Viele Grüße,
Honeyhead
Hallo,
Ich könnte spontan diesen Algorithmus anbieten (Komplexität O(n^2)):
Sei bekannt ein Array aller bisher gesehenen Zeichenketten mit Zeichenkette als Schlüssel und Index der letzten Position als Wert.
ausgabe ist ein Array aller doppelten Zeichenketten mit Startindex als Schlüssel und Endindex als Wert.
n ist die Länge des Strings.
Für alle i von 0 bis n-1:
Für alle k von 0 bis i:
Leider habe ich gerade kein PHP zur Verfügung und konnte das nur in Python testen.