Algorithmus zur Erkennung sich wiederholender/ähnlicher Zeichenfolgen in einem Datenkorpus - z. B. E-Mail-Betreffs, in Python

Question

Ich lade gerade eine lange Liste meiner E-Mail-Betreffzeilen herunter, um E-Mail-Listen zu finden, bei denen ich vor Jahren Mitglied war und die ich aus meinem Google Mail-Konto löschen möchte (das ziemlich langsam wird).

Ich denke dabei vor allem an Newsletter, die oft von derselben Adresse kommen und in der Betreffzeile den Namen des Produkts/der Dienstleistung/der Gruppe wiederholen.

Ich weiß, dass ich nach dem häufigen Auftreten von Sendungen von einer bestimmten E-Mail-Adresse suchen/sortieren könnte (und das habe ich auch vor), aber ich würde diese Daten gerne mit sich wiederholenden Betreffzeilen korrelieren....

Bei vielen Betreffzeilen würde ein String-Treffer nicht funktionieren, aber "Google-Freunde: Unsere neuesten Nachrichten" "Google Friends: Was wir heute machen" sind einander ähnlicher als eine zufällige Betreffzeile, wie z. B: "Virgin Airlines hat heute ein tolles Angebot" "Machen Sie einen Flug mit Virgin Airlines"

Wie kann ich also beginnen, automatisch Trends/Beispiele von Zeichenketten zu extrahieren, die möglicherweise ähnlicher sind?

Ansätze, die ich in Erwägung gezogen und wieder verworfen habe ("weil es einen besseren Weg geben muss"):

• Extrahieren aller möglichen Teilzeichenketten und Ordnen nach Häufigkeit ihres Auftretens sowie manuelles Auswählen der relevanten Teilzeichenketten
• Das erste Wort oder die ersten zwei Wörter werden entfernt, und dann wird das Auftreten der einzelnen Teilstrings gezählt
• Vergleich des Levenshtein-Abstands zwischen Einträgen
• Eine Art Ähnlichkeitsindex für Zeichenketten ...

Die meisten davon wurden wegen massiver Ineffizienz oder der Wahrscheinlichkeit eines enormen manuellen Eingriffs abgelehnt. Ich schätze, ich brauche eine Art Fuzzy-String-Matching ?

Ich kann mir zwar vorstellen, dass es auch anders geht, aber ich bin auf der Suche nach etwas Allgemeinerem, so dass ich meinen Satz von Werkzeugen erweitert habe, anstatt ein spezielles Gehäuse für diesen Datensatz zu entwickeln.

Ich bin mir nicht sicher, ob es eine gute Möglichkeit gibt, eine Datenstruktur zu erstellen, die darstellt, wie wahrscheinlich/unwahrscheinlich zwei Nachrichten Teil derselben E-Mail-Liste" sind, oder indem ich alle meine E-Mail-Betreffe/Absenderadressen in Pools von wahrscheinlichen verwandten" E-Mails und nicht verwandten E-Mails filtere - aber das ist ein Problem, das nach diesem gelöst werden muss.

Für jeden Hinweis wären wir dankbar.

Answer 1

Ich würde zunächst jede Zeichenfolge in einen Satz oder mehrere Sätze von Wörtern umwandeln (ohne Berücksichtigung von Satzzeichen und Unterschieden in der Groß- und Kleinschreibung). (Wenn das nicht ausreicht, könnte ich in einem zweiten Durchgang Paare oder sogar Dreiergruppen benachbarter Wörter, so genannte Bigramme und Trigramme, versuchen). Das wichtigste Maß für die Ähnlichkeit zwischen den so reduzierten Zeichenketten ist, welche Wörter, die no Hochfrequenz insgesamt (nicht the , and etc;-) sind beiden Zeichenketten gemeinsam, so dass eine einfache Mengenüberschneidung (oder Multiset-Überschneidung, aber für Ihren einfachen Anwendungsfall denke ich, dass nur Mengen ausreichen, insbesondere Mengen von Bigrammen) ausreichen sollten, um die "Gemeinsamkeit" zu messen. Ein Wort, das in beiden Strings vorkommt, sollte umso mehr wert sein, je seltener es ist, daher ist der negative Logarithmus der Häufigkeit des Wortes im gesamten Korpus ein ausgezeichneter Ausgangspunkt für diese Heuristik.

Answer 2

Glattes BLEU

Möglicherweise können Sie die glatt - BLEU Punktzahl zwischen den Probanden. BLEU ist ein Bewertungsmaßstab, mit dem bewertet wird, wie ähnlich die von einem maschinellen Übersetzungssystem erstellten Übersetzungen den von Menschen erstellten Übersetzungen sind. Smooth BLEU wird wie der normale BLEU-Score berechnet, mit dem Unterschied, dass man zu den n-Gramm-Match-Zahlen eins hinzufügt, um zu vermeiden, dass bei der Bewertung kurzer Textsegmente irgendetwas mit null multipliziert wird.

Smooth-BLEU sollte viel schneller als die Levenshtein-Distanz zu berechnen, aber dennoch Erfassung von Informationen zur Wortstellung da es sich mit n-gramm Übereinstimmungen und nicht nur Übereinstimmungen zwischen einzelnen Wörtern.

Leider habe ich keinen Hinweis auf eine Python-BLEU-Implementierung, aber Sie finden eine Perl-Implementierung von NIST aquí .