Calcul d'une distance relative Levenshtein - logique?

Question

J'utilise à la fois Soundexing Daitch-Mokotoff et Damerau-Levenshtein pour savoir si une entrée d'utilisateur et une valeur dans l'application sont «identiques».

La distance de Levenshtein est-elle supposée être utilisée comme valeur absolue? Si j'ai un mot de 20 lettres, une distance de 4 n'est pas si mauvaise. Si le mot a 4 lettres ...

Ce que je fais maintenant est de prendre la distance/longueur pour obtenir une distance qui reflète mieux quel pourcentage du mot a été changé.

Est-ce une approche valide/éprouvée? Ou est-ce simplement stupide?

Answer 1

La distance de Levenshtein est-elle censée être utilisée comme valeur absolue?

Il semblerait que cela dépende de vos besoins. (Pour clarifier: la distance de Levenshtein est une valeur absolue, mais comme le PO l'a souligné, la valeur brute peut ne pas être aussi utile que pour une application donnée en tant que mesure qui tient compte de la longueur du mot. sont vraiment plus intéressés par similitude que la distance en soi.)

J'utilise les deux Daitch-Mokotoff Soundexing et Damerau-Levenshtein pour savoir si une entrée utilisateur et une valeur dans l'application sont « les mêmes ".

Sons comme vous essayez de déterminer si l'utilisateur destiné leur entrée à être identique à une valeur donnée de données?

Faites-vous des vérifications orthographiques? ou une entrée non conforme conforme à un ensemble de valeurs connu? Quelles sont vos priorités?

• Réduire au minimum les faux positifs (essayer de faire que tous les mots suggérés sont très « similaires », et la liste des suggestions est courte)
• Réduire au minimum les faux négatifs (essayez de vous assurer que la chaîne l'utilisateur prévu est dans la liste des suggestions, même si elle fait la longue liste)
• Maximize précision de correspondance moyenne

Vous pourriez finir par utiliser la distance Levenshtein d'une façon de déterminer si un mot doit être proposé dans une liste de suggestions; et une autre façon de déterminer comment commander la liste de suggestions. Il me semble, si j'ai déduit votre but correctement, que la chose principale que vous voulez mesurer est similitude plutôt que la différence entre deux chaînes. En tant que tel, vous pouvez utiliser Jaro or Jaro-Winkler distance, qui tient compte de la longueur des chaînes et le nombre de caractères en commun:

Le dj distance Jaro de deux données chaînes s1 et s2 est

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

où:

• m est le nombre de caractères qui correspond à
• t est le nombre de transpositions

la distance Jaro-Winkler utilise un préfixe échelle p qui donne des notes plus favorables à des chaînes qui correspondent de la commençant par une longueur de préfixe ensemble l.

Answer 2

La distance levenshtein est une valeur relative entre deux mots. La comparaison de la LD à la longueur n'est pas par exemple pertinent

cat

-> scato = 1 (75% similaire ??)

différence -> différences = 1 (90% similaire ??)

Ces deux les mots ont des distances lev de 1, c'est-à-dire qu'ils diffèrent par un caractère, mais comparés à leurs longueurs, le second ensemble semble être «plus» similaire.

J'utilise Soundexing pour classer les mots qui ont la même distance lev par exemple

cat et fat ont tous deux une LD de 1 par rapport à kat, mais le mot est plus susceptible d'être kat que la graisse lors de l'utilisation soundex (en supposant le mot est orthographié de manière incrémentielle, pas tapé incorrectement!)

Donc la réponse courte est juste d'utiliser la distance lev pour déterminer la similarité.