Levenshtein Abstand: Wie besser in den Griff Worte Positionen tauschen?

StackOverflow https://stackoverflow.com/questions/828132

Frage

Ich habe einen gewissen Erfolg hatte Vergleich Strings mit der PHP levenshtein Funktion.

Doch für zwei Strings, die Zeichenketten enthalten, die Positionen getauscht haben, zählt der Algorithmus diejenigen, die als neue Teil.

Zum Beispiel: 

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

werden behandelt, als mit weniger gemeinsam als: 

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

Ich würde es vorziehen, einen Algorithmus, der sah, dass die erst beide waren ähnlich.

Wie kann ich mich über eine Vergleichsfunktion kommen, die Substrings, die eingeschaltet haben Position als deutliche identifizieren können bearbeitet?

Ein möglicher Ansatz, den ich gedacht habe, ist, alle Wörter in der Zeichenfolge in alphabetischer Reihenfolge zu bringen, vor dem Vergleich. Das nimmt die ursprüngliche Reihenfolge der Worte vollständig aus dem Vergleich. Ein Nachteil dieser ist jedoch, dass eine viel größere Störung schaffen kann nur den ersten Buchstaben eines Wortes zu ändern, als ein Wechsel ein einzelner Buchstabe verursachen sollte.

Was ich versuche zu erreichen, zwei Fakten über Menschen zu vergleichen, die freien Text-Strings sind, und entscheiden, wie wahrscheinlich diese Tatsachen sind die gleiche Tatsache anzuzeigen. Die Fakten könnten die Schule jemand besucht werden, der Name des Arbeitgebers oder Verleger, zum Beispiel. Zwei Datensätze können die gleiche Schule anders geschrieben, Worte in einer anderen Reihenfolge, zusätzliche Worte, usw., also die Anpassung etwas unscharf sein muss, wenn wir eine gute Vermutung zu machen, dass sie auf die gleiche Schule verweisen. So weit es funktioniert sehr gut für Rechtschreibfehler (I einen phoenetic Algorithmus bin mit ähnlich oben auf die alle metaphone), aber sehr schlecht, wenn Sie die Reihenfolge der Worte, um den Schalter scheint gemeinsam in einer Schule: „xxx College“ vs "College of xxx".

War es hilfreich?

Lösung

N-Gramm

Verwenden Sie N-Gramm , die Unterstützung Multiple- Charakter Umstellungen im gesamten Text .

Die allgemeine Idee ist, dass man die beiden Strings in Frage in allen möglichen 2-3 Zeichen Substrings aufgeteilt (n-Gramm) und die Anzahl der gemeinsamen n-Gramm zwischen den beiden Strings als ihre Ahnlichkeitsmetrik zu behandeln. Dies kann dann normalisiert werden, indem die freigegebene Anzahl durch die Gesamtzahl von n-Grammen in dem längeren Kettenteilungs. Dies ist trivial zu berechnen, aber ziemlich mächtig.

Für die Beispielsätze: 

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

A und B Aktien 18 2-Gramm

A und C teilen nur 8 2-Gramm

aus 20 Gesamt möglich.

Dies ist im Detail in dem Gravano et al diskutiert. Papier .

TF-IDF und Kosinusähnlichkeit

Eine nicht ganz so trivial Alternative, aber in der Informationstheorie geerdet wäre Begriff Begriff frequenz inverse Dokumentfrequenz (TF-IDF) die Token wiegen, Satz Vektoren konstruieren und dann a href = verwenden < "https://en.wikipedia.org/wiki/Cosine_similarity" rel = "noreferrer" > Kosinusähnlichkeit als Ahnlichkeitsmetrik.

Der Algorithmus ist:

  1. berechnen 2-Zeichen-Token-Frequenzen (tf) pro Satz.
  2. Berechnen inverse Satz Frequenzen (IDF), die ein Logarithmus eines Quotienten aus der Anzahl aller Sätze in dem Korpus (in diesem Fall 3) von der Anzahl wie oft ein bestimmtes Token über alle Sätze unterteilt wird. In diesem Fall th ist in allen Sätzen, so dass es Null Informationsgehalt hat (log (3/3) = 0). idf Formel
  3. Produzieren die TF-IDF-Matrix durch entsprechende Zellen in der TF- und IDF Tabellen multipliziert wird. TFIDF
  4. Schließlich berechnen Cosinus-Ähnlichkeitsmatrix für alle Satzpaare, wobei A und B sind Gewichte von der TF-IDF-Tabelle für die entsprechenden Token. Der Einstellbereich reicht von 0 (nicht ähnlich) bis 1 (gleich).
    Kosinusähnlichkeit
    Ähnlichkeitsmatrix

Levenshtein Modifikationen und Metaphone

In Bezug auf andere Antworten. Damerau-Levenshtein modificication unterstützt nur die Umsetzung der zwei benachbarte Zeichen. Metaphone wurde entworfen Worte übereinstimmen, die die gleichen und nicht klingen Ähnlichkeitsanpassung.

Andere Tipps

Es ist einfach. Verwenden Sie einfach die Damerau-Levenshtein Abstand auf die Wörter anstelle von Buchstaben.

Explodieren

auf Räume, sortieren das Array, implodieren, dann tun die Levenshtein.

Sie können auch versuchen, diese. (Nur ein zusätzlicher Vorschlag) 

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

Dies wird zeigen, dass die 1. und 2. ähnliche sind als eins und drei und zwei und drei.

Ich habe in einer Rechtschreibprüfung Umsetzung levenshtein.

Was Sie für Fragen ist Umstellungen als 1 Bearbeitung zählen.

Dies ist einfach, wenn Sie weg zu zählen Umstellungen von einem Wort wünschen. Doch für die Umsetzung von Worten 2 oder mehr entfernt, der zusätzlich zu dem Algorithmus Worst-Case-Szenario !(max(wordorder1.length(), wordorder2.length())). einen nichtlineare Teilalgorithmus zu einem bereits quadratischen Algorithmus Hinzufügen ist keine gute Idee.

Dies ist, wie es funktionieren würde. 

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

JUST zum Anfassen Umstellungen. Wenn Sie alle Umstellungen wollen, würden Sie haben für jede Position von diesem Punkt arbeiten nach hinten Vergleich 

1[n] == 2[n-2].... 1[n] == 2[0]....

Sie sehen also, warum sie nicht enthalten diese in der Standardmethode.

Nehmen Sie diese Antwort und die folgende Änderung: 

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

Dies ist für Wörterbuchsuche in einem Trie, sondern auf ein einziges Wort für die Anpassung, es ist die gleiche Idee. Sie tun Branch-and-gebunden, und an jedem Punkt können Sie Änderungen vornehmen können Sie mögen, so lange wie Sie es eine Kosten geben.

Beseitigen Sie doppelte Wörter zwischen den beiden Strings und dann Levenshtein verwenden.

Ich glaube, dies ein gutes Beispiel ist ein Vektorraum Suchmaschine .

in dieser Technik wird jedes Dokument wird im wesentlichen ein Vektor mit so vielen Dimensionen, wie es unterschiedliche Worte in dem gesamten Korpus; ähnliche Dokumente dann die benachbarten Gebiete in diesem Vektorraum besetzen. eine schöne Eigenschaft dieses Modells ist, dass Abfragen sind auch nur Dokumente: eine Anfrage zu beantworten, können Sie einfach ihre Position im Vektorraum berechnen, und die Ergebnisse sind die nächsten Dokumente, die Sie finden können. Ich bin sicher, es gibt Get-and-go-Lösungen für PHP gibt.

Ergebnisse von Vektorraum fuzzify, könnte man bedenkt, ergeben / ähnliche Verarbeitung natürlicher Sprache Technik zu tun, und verwenden levenshtein zur sekundären Anfragen nach ähnlichen Wörtern zu erstellen, die in Ihrem gesamten Wortschatz vorkommen.

Wenn die erste Zeichenfolge A und die zweite ist, B:

  1. Split A und B in Worte
  2. Für jedes Wort in A, finden Sie das am besten passende Wort in B (mit levenshtein)
  3. das Wort von B entfernen und es in B * auf dem gleichen Index wie das passende Wort in A gesetzt.
  4. Jetzt vergleichen A und B *

Beispiel: 

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

Sie können Schritt 2, indem sie es in mehreren Durchgängen verbessern tun, finden nur genau auf den ersten übereinstimmt, dann schließen Treffer für Wörter in A zu finden, die keinen Begleiter in B haben * noch, dann weniger enge Matches usw.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top