Berechnung einer relativen Levenshtein-Distanz - sinnvoll?

Question

Ich benutze sowohl Daitch-Mokotoff soundexing und Damerau-Levenshtein, um herauszufinden, ob ein Benutzereintrag und ein Wert in der Anwendung "gleich" sind.

Soll die Levenshtein-Distanz als absoluter Wert verwendet werden? Wenn ich ein Wort mit 20 Buchstaben habe, ist eine Entfernung von 4 nicht so schlecht. Wenn das Wort 4 Buchstaben hat ...

Was ich jetzt mache, ist die Entfernung/Länge, um eine Distanz zu erhalten, die besser widerspiegelt, wie viel Prozent des Wortes geändert wurde.

Ist das ein gültiger/bewährter Ansatz? Oder ist es einfach dumm?

Answer 1

Soll der Levenshtein-Abstand als absoluter Wert verwendet werden?

Es scheint als würde es auf Ihre Anforderungen abhängen. (Um zu verdeutlichen: Levenshtein Entfernung ist ein absoluter Wert, aber wie das OP darauf hingewiesen hat, ist der Rohwert möglicherweise nicht so nützlich wie für eine gegebene Anwendung als eine Maßnahme, die die Länge des Wortes berücksichtigt. Dies liegt daran, dass wir in Ähnlichkeit ist wirklich mehr interessiert als die Entfernung per se.)

ich verwende beide Daitch-Mokotoff soundexing und Damerau-Levenshtein zu herauszufinden, ob ein Benutzereintrag und ein Wert in der Anwendung ist „die gleiche ".

Klingt wie Sie versuchen, ob der Benutzer bestimmt ihren Eintritt zu bestimmen, die gleiche wie ein bestimmten Datenwert zu sein?

Machst du Rechtschreibprüfung? oder konforme ungültige Eingabe zu einem bekannten Satz von Werten? Was sind Ihre Prioritäten?

• minimieren Fehlalarme (versuchen Sie alle vorgeschlagenen Wörter sehr „ähnlich“, um sicherzustellen, sind, und die Liste der Vorschläge ist kurz)
• falsche Negative minimieren (versuchen, um sicherzustellen, dass die Zeichenfolge der gewünschten Benutzer in der ist Liste der Vorschläge, auch wenn er die Liste lang) Genauigkeit
• Maximize durchschnittlicher Matching macht

das könnte dir am Ende mit der Levenshtein-Distanz in einer Art und Weise, um zu bestimmen, ob ein Wort sollte in einer Vorschlagsliste angeboten werden; und eine andere Möglichkeit zu bestimmen, wie die Vorschlagsliste zu bestellen ist.

Es scheint mir, wenn ich Ihren Zweck richtig abgeleitet habe, dass das Kernstück, das Sie messen möchten, Ähnlichkeit eher als Unterschied zwischen zwei Saiten ist. Als solche könnten Sie Jaro or Jaro-Winkler distance, die gemeinsam die Länge der Saiten und die Anzahl der Zeichen berücksichtigt:

(m/|s1| + m/|s2| + (m - t)/m)/3 

ist

Der Jaro Abstand dj von zwei gegebenen Strings s1 und s2

wobei:

• m die Anzahl der passenden Zeichen
• t ist die Anzahl der Transpositionen

Jaro-Winkler Abstand benutzt ein Präfix Skala p die günstigere Ratings Strings gibt, die für eine Reihe Präfixlänge l vom beginnen lassen.

Answer 2

Der Levenshtein-Abstand ist ein relativer Wert zwischen zwei Wörtern. Vergleicht man die LD auf die Länge nicht relevant zB

Katze -> kv = 1 (75% ähnlich ??)

Differenz -> Unterschiede = 1 (90% ähnlich ??)

Diese beiden Wörter haben lev-Abstände von 1, dh sie unterscheiden sich um ein Zeichen, aber im Vergleich zu ihren Längen scheint die zweite Menge "ähnlicher" zu sein.

Ich benutze soundexing Worte Rang, die die gleiche lev Entfernung zB

cat und fat beide haben einen LD von 1 relativ zu kat, aber das Wort ist eher zu kat als Fett, wenn soundex mit (unter der Annahme haben Das Wort ist falsch geschrieben, nicht falsch eingegeben!)

Also die kurze Antwort ist nur die lev-Abstand verwenden, um die Ähnlichkeit zu bestimmen.