Berechnen einer relativen Levenshtein-Distanz - sinnvoll?

Question

Ich verwende sowohl Daitch-Mokotoff soundexing und Damerau-Levenshtein um herauszufinden, ob ein Benutzereintrag und einen Wert in der Anwendung sind „das gleiche“.

Is Levenshtein Abstand sollte als absoluten Wert verwendet werden? Wenn ich ein 20-Buchstaben-Wort habe, ist ein Abstand von 4 nicht so schlimm. Wenn das Wort hat 4 Buchstaben ...

Was ich jetzt tue, um den Abstand / Länge nimmt einen Abstand zu bekommen, dass besser widerspiegelt, was Prozentsatz des Wortes geändert wurde.

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

Answer 1

  

Is Levenshtein Abstand sein soll   als absoluter Wert verwendet?

Es scheint, als wäre es Ihre Anforderungen hängen von. (Zur Klarstellung: Levenshtein Abstandes ein absoluter Wert, sondern als die OP wies darauf hin, der Rohwert kann nicht so nützlich sein wie für eine bestimmte Anwendung als Maßnahme, die die Länge des Wortes berücksichtigt . Das ist, weil wir wirklich mehr Interesse an Ähnlichkeit als Distanz per se.)

sind

  

Ich verwende sowohl Daitch-Mokotoff   soundexing und Damerau-Levenshtein zu   Wenn ein Benutzer Eintrag herausfinden und ein Wert   in der Anwendung ist "die gleiche".

Sounds wie Sie versuchen, um zu bestimmen, ob der Benutzer bestimmt ihren Eintritt das gleiche wie einen gegebenen Datenwert sein?

Tun Sie die Rechtschreibprüfung? oder konforme ungültige Eingabe in einen bekannten Satz von Werten? Was sind Ihre Prioritäten?

• minimieren Fehlalarme (versuchen Sie sicher, dass alle vorgeschlagenen Wörter zu machen, sind sehr „ähnlich“, und die Liste der Vorschläge ist kurz)
• Minimieren falsche Negative (versuchen, um sicherzustellen, dass die Zeichenfolge der Benutzer soll in der Liste der Vorschläge ist, auch wenn er die Liste macht lang)
• Maximize durchschnittliche Anpassungsgenauigkeit

Sie können die Levenshtein-Distanz in einer Art und Weise am Ende mit, um zu bestimmen, ob ein Wort sollte in einer Vorschlagsliste angeboten werden; und eine andere Art und Weise zu bestimmen, wie die Vorschlagsliste bestellen.

Es scheint mir, wenn ich Ihren Zweck richtig geschlossen habe, dass der Kern, was Sie messen wollen, ist Ähnlichkeit anstatt Unterschied zwischen zwei Strings. Als solche könnten Sie Jaro oder Jaro-Winkler Abstand verwenden, die nimmt die Länge der Saiten zu berücksichtigen und die Anzahl der Zeichen gemeinsam:

  

Der DJ Jaro Abstand von zwei gegeben   Strings s1 und s2

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

     

Dabei gilt:

     

  
• m ist die Anzahl der passenden Zeichen
  
• t ist die Zahl der Umstellungen
  

     

Jaro-Winkler Abstand benutzt ein Präfix   Skala p das gibt günstiger   Bewertungen zu Strings, die aus dem Match   Anfang für eine Reihe Präfixlänge l .

Answer 2

Der levenshtein Abstand ist ein relativer Wert zwischen zwei Worten. Vergleicht man die LD auf die Länge nicht relevant zB

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

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

Diese beiden Wörter haben lev Abständen von 1, dh sie um ein Zeichen unterscheiden, aber im Vergleich zu ihren Längen der zweite Satz scheint zu sein ‚mehr‘ ähnlich.

Ich verwende soundexing auf Rang Wörter, die gleich lev Abstand zB

haben

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

So die kurze Antwort benutzen Sie einfach den lev Abstand die Ähnlichkeit zu bestimmen.