[schifti]

Hi,

ich hab zwei Wörter (Subjects von Mails) und möchte nun feststellen, wie wahrscheinlich String 2 gleich, oder sehr ähnlich mit String 1 ist.

Ich hab bis jetzt leider nur den Ansatz, das ich alle Wörter der Strings in ein Array packe und mit array_diff vergleiche, welche Wörter in beiden Strings gleich oft vorkommen.

Wisst ihr vielleicht, ob es da nicht schon etwas gibt, an das ich nicht gedacht hatte, oder wie man am besten prüfen kann wie hoch die Wahrscheinlichkeit ist, das beide Strings sehr ähnlich oder gleich sind?

Ich bin für jeden Tipp dankbar.

Ach ja, die Funktion muss evtl. irgendwann mal mehrere Tausend Datensätze prüfen.

[Jann Hendrik]

Und du bist sicher, dass du das mit den Mitteln von PHP lösen willst?

[schifti]

Es kann auch gerne was in SQL, Perl oder so sein, so lange ich die Sprache schon mal gehört habe (also kein C, Delphi usw.).

[xardias]

Wenn es wirklich darum geht das ganze effizient zu gestalten würde ich wirklich eher zu einer performanteren Sprache greifen und da kommen eigentlich C oder C++ am ehesten in Frage. In PHP oder Perl wird es sicher auch funktionieren, so lange das ganze danach schnell genug für dich läuft ist ja alles prima. Wenn nicht wäre da jedoch der erste und effektivste Optimierungsansatz die Sprache zu wechseln .

Aber mal ganz allgemein zum Thema. Das ist keine unbekannte Sache es gibt viele Algorithmen dazu. Siehe:
http://en.wikipedia.org/wiki/Fuzzy_string_searching

Über die Levenshtein Distanz könnte man das z.B. realisieren:
http://en.wikipedia.org/wiki/Levenshtein_distance

Unter http://en.wikipedia.org/wiki/Edit_distance findest du weitere Algorithmen u.A. ein Link zu einer Perl implementierung der Wagner-Fischer-Distanz das düfte für dich somit sehr interessant sein.

[schifti]

Ahhhha. Super. Das mit dem Levenstein-Dings sieht gut aus.
Da muss ich dann nur noch ausschecken, ab welchem wert die Betreffs garantiert nicht mehr ähnlich sind.
Danke!

[Basti]

Die Levenshtein-Funktion ist schon seit 4.0.1 in PHP implementiert:

http://php.net/manual/en/function.levenshtein.php

Bastian

[MrNiceGuy]

Vielleicht wäre auch SoundEx noch eine Alternative?! Aber bevor ich hier Schelte kassieren sollte: Ich habe selber noch nie derartige Implementierungen benutzen müssen, von daher kenne ich weder Vor- oder gar Nachteile bestimmter Implementationen. Deswegen bitte nicht hauen, wenn SoundEx nicht so das Tollste sein sollte, habe nur irgendwann mal davon gehört:

http://php.net/soundex

[schifti]

Ich glaub ich Pfeif auf die Performance... (oder ich lagere das in Cronjobs aus).
Jo, das mit similar_text und soundex scheint auf den ersten 20 Test schon mal sehr gut zu funktionieren.

Noch mals vielen Dank!

[$traight-$hoota]

Zitat von MrNiceGuy

Vielleicht wäre auch SoundEx noch eine Alternative?! Aber bevor ich hier Schelte kassieren sollte: Ich habe selber noch nie derartige Implementierungen benutzen müssen, von daher kenne ich weder Vor- oder gar Nachteile bestimmter Implementationen. Deswegen bitte nicht hauen, wenn SoundEx nicht so das Tollste sein sollte, habe nur irgendwann mal davon gehört:

http://php.net/soundex

das war auch mein erster gedanke, weil ich davon schonma eher was gehört hab.
aber für diesen fall is levensthein imo besser, da sich damit als fester wert eine ähnlichkeit der schreibweise ergibt und nicht wie bei soundex des klangs (wobei metaphone da noch besser wäre, allerdings mehr auf englische aussprache bezogen).

[MrNiceGuy]

Vielleicht wäre eine Kombination aus Beidem die richtige Wahl!?

[Sekundentakt]

Zitat von MrNiceGuy

Vielleicht wäre eine Kombination aus Beidem die richtige Wahl!?

Nein, eher unwahrscheinlich. Die ausgegebenen Werte sind sehr unterschiedlich (logisch, bei verschiedenen Schlüsseln), noch dazu sind die Ergebnisse mitunter verfälscht, wenn du beides verwendest. So wird zum Beispiel "mathe" und "mate" bei Soundex als gleichwertig erkannt, wohingegen eine Überprüfung mittels Metaphone darauf hiwneist, dass es Unterschiede gibt.

Wenn du effektiv vergleichen willst, würde ich eine Mischung aus metaphone und similar_text empfehlen. Erst wertest du die Geschichte via metaphone aus und vergleichst dann die metaphone-Werte via similar_text miteinander.
Du lässt dann eine gewisse Fehlertolleranz, falls nötig, zu, indem du alles ausgibst, was bis zu (beispielsweise) 90% übereinstimmt.
Fertig .

[Sekundentakt]

Noch eine kleine Anmerkung:
Wenn du levenshtein verwendest sind folgende Betreffs völlig unterschiedlich:
Frage (Bestellungen)
Bestellung (Frage)

bei Metaphone ebenso.

Ich weiß nicht, was du letzten Endes mit deinen E-Mails machen willst, aber du kannst eigentlich immer, sofern der Betreff nicht irgendwie vorgegeben werden kann, davon ausgehen, dass du hin und wieder E-Mails falsch sortierst. Du kannst das ganze Konstrukt natürlich - sofern sich der Aufwand lohnt - immer noch einmal verbessern, damit es noch genauer arbeitet.

Zum Fallbeispiel:
Similar_Text stellt beim obrigen Beispiel eine Übereinstimmung von 65% fest, hast du den String einmal durch metaphone(); gejagt, und den Wert gespeichert und überprüfst dann beide Texte auf Ähnlichkeit, erhälst du eine 70%ige Übereinstimmung.

Anderes Beispiel:
Betreffs:
mate
mathe

(man achte auf den Rechtschreibfehler)

Nachdem der Betreff auf die selbe Weise überprüft wurde, bei der im obrigen Beispiel eine 70%ige Übereinstimmung festgestellt wurde, erreicht dieses Beispiel nur eine 50%ige Übereinstimmung.

Eine Überprüfung des reinen Betreff-Strings OHNE metaphone(); hingegen gibt eine 88,89%ige Übereinstimmung aus.

Das Problem bei metaphone wird sein, dass das th einen eigenen Wert darstellt, und nicht wie für die deutschen Worte benötigt, t und h jeweils eigenständige Werte darstellen.

Levenshtein macht in diesem Falle überhaupt keinen Sinn, da du mit Levenshtein nur errechnest, wie viele Zeichen z.B. verändert werden müssen, um von "mate" auf "mathe" zu kommen. Was bedeutet das? Praktisch, auf dieses Fallbeispiel angewendet heißt das, dass du die Betreffs (korrigiert mich, wenn ich mich irre) schon vorher kennen musst, oder es eine Vorstellung geben muss, was in den Betreffs drinnen zu stehen hat, um diese miteinander zu vergleichen.

Wenn du z.B. weißt, dass du E-Mails mit dem Betreff "Mathe" kriegst, ist Levenshtein eine super Methode, auch diejenigen Mails in die richtige Kategorie zu sortieren, die einige Tippfehler enthalten, wie in diesem Fallbeispiel das vergessene "h".

Und zur Soundex-Idee: Probiers aus, ich war von Soundex aber etwas enttäuscht, da mit zunehmender Zeichenkettenlänge die Ungenauigkeiten immer deutlicher zu spüren waren.

[schifti]

Ja, deshalb dachte ich auch an eine Kombination... wenn Levenshtein wenige Zeichen ersetzten muss und die anderen Checks >= 40% sind, dann gebe ich die gefundenen Betreff-Zeilen noch mal zum auswählen aus.
Wenn die Zeichen zum ersetzten zu groß sind, aber die anderen Funktionen mehr als 80% sagen, dann sind die Betreff's "gleich".

Ich will so ein Spam-Archiv bauen und dort zählen, welche Spammails wie oft und wann das erste und letzte mal vorkommen. Daher sollte ich erkennen, das z.B. folgende Strings "gleich" sind:

"You have new mail from Olga"
und
"1 neew message!"
(wenn es beides mal um Pe....-Vergrößerung geht).

Die Betreff-Zeilen, sind zu bestimmten Sätzen im Body "nur" ein weiterer Check, ob beide Mails der gleiche Spam sind....

Ich möchte halt möglichst gut sagen können das Mail 1 (old) die gleich Spammail wie Mail2 ist, wobei sich einige Sachen unterscheiden.
......
Da bin ich glaub noch bissle länger mit beschäftigt

Wenn ich was gutes, funktionierendes hinbekommen hab, poste ich es hier.

Danke für eure Hilfe.

[Sekundentakt]

Erst einmal:
Eine Maschine kann nicht denken. Eine Maschine kann auch nicht wirklich sagen, ob etwas relevant ist, oder nicht. Sie kann versuchen auf Grundlage bestimmter Suchmuster eine Relevanz auszugeben. Ob das was du dann aber findest, wirklich zu dem passt, was du gesucht hast, hängt davon ab, wie gut deine Suchmaske ist.

Das bedeutet, dass

"You have new mail from Olga"
und
"1 neew message!"

Nie und nimmer über eine der Funktionen als gleiche Strings anerkannt werden. Die einzige Gemeinsamkeit wäre ja hier das "new".

Was du machen könntest, wäre den Inhalt der Mails miteinander zu vergleichen (was ich über similar_text alleine machen würde, da du hier nicht auf Worstellung, sondern nur auf den Aufbau der Spammails achten musst).

Du könntest, wenn eine Übereinstimmung des Inahltes vorhanden ist, festlegen, dass beide Betreffs sich WAHRSCHEINLICH mit ähnlichen Inhalten befassen werden.

------
Eine Frage aus reiner Neugier: Was bringt es mir als Besucher am Ende, deine Seite besucht zu haben? Welchen Nutzen ziehe ich darauß?