Pourcentage de matchs avec correspondance à distance Levenshtein
j'essaie de faire correspondre un seul terme de recherche avec un dictionnaire de correspondances possibles en utilisant un algorithme de distance de Levenshtein. L'algorithme retourne une distance exprimée en nombre d'opérations nécessaires pour convertir la chaîne de recherche dans la chaîne trouvée. Je veux présenter les résultats dans la liste classée en pourcentage du top "N" (disons 10) matches.
puisque la chaîne de recherche peut être plus longue ou plus courte que les chaînes de dictionnaires individuelles, quelle serait la logique appropriée pour exprimer la distance en pourcentage, ce qui refl èterait qualitativement à quel point "en pourcentage" est chaque résultat de la chaîne de requête, avec 100% indiquant une correspondance exacte.
j'ai considéré les options suivantes:
Q = query string
M = matched string
PM = Percentage Match
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100
L'Option 1 a la possibilité de pourcentages négatifs dans le cas où la distance est supérieure à la longueur de la chaîne de recherche, où la chaîne de correspondance est longue. Par exemple, la recherche "ABC" jumelée à" ABC Corp. " donnerait lieu à une correspondance négative. cent.
L'Option 2 ne semble pas donner un pourcentage uniforme pour un ensemble de Mi, car chaque calcul pourrait utiliser un dénominateur différent et, par conséquent, les valeurs de pourcentage résultantes ne seraient pas normalisées.
le seul autre moyen auquel je peux penser est de laisser tomber la comparaison de la distance de lev_distance à l'une ou l'autre des longueurs de chaîne, mais plutôt de présenter les distances de comparaison des correspondances "N" supérieures comme un rang de centile inverse (100-percentile-rank).
tous pensées? Existe-il des approches mieux? Je dois rater quelque chose car la distance Levenshtein est probablement l'algorithme le plus commun pour les correspondances floues et ce doit être un problème très commun.
6 réponses
j'ai eu un problème similaire et ce fil m'a aidé à trouver une solution. Espérons qu'il puisse aider les autres aussi.
int levDis = Lev_distance(Q, Mi)
int bigger = max(strlen(Q), strlen(Mi))
double pct = (bigger - levDis) / bigger
il devrait retourner 100% si les deux chaînes sont exactement les mêmes et 0% si elles sont totalement différentes.
(désolé si mon anglais n'est pas très bon)
pour résoudre ce problème, J'ai calculé les opérations maximales autorisées, ce qui correspond à la distance de Levenshtein. La formule que j'ai utilisé est:
percent = 0.75; // at least 75% of string must match
maxOperationsFirst = s1.length() - s1.length() * percent;
maxOperationsSecond = s2.length() - s2.length() * percent;
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond));
il calcule des opérations maximales pour chaque chaîne, je crois que le calcul est facile à comprendre. J'utilise la valeur minimale des deux résultats et je l'arrondis au nombre entier le plus proche. Vous pouvez sauter cette partie et utiliser juste la valeur des opérations max à partir de l'une ou l'autre des chaînes, cela dépend vraiment de vos données.
Une fois vous avez le nombre d'opérations maximum, vous pouvez le comparer avec le résultat de levenshtein et déterminer si la chaîne est acceptable. Vous pouvez ainsi utiliser n'importe quelle méthode étendue de levenshtein, par exemple distance de damerau–Levenshtein, qui comptent les fautes d'orthographe,ex: test -> tset, seulement en tant qu'opération 1, ce qui est très utile pour vérifier les entrées de l'utilisateur où ces fautes d'orthographe se produisent très souvent.
j'espère que cela vous aidera à obtenir une idée sur la façon de résoudre ce problème.
(1 - (levNum / Math.max(s.length,t.length) ) ) *100
devrait être correct
il s'agit essentiellement de l'option 2 mentionnée dans ma question. Toutefois, permettez-moi de démontrer un problème avec cette approche.
Q = "ABC Corp" (len = 8)
M1 = "ABC"
M2 = "ABC Corporati"
M3 = "ABC Corp"
J'ai choisi M1 et M2 de telle sorte que leurs distances Lev soient identiques (5 chacune). En utilisant l'option 2, Les pourcentages de correspondance seraient
M1 = (1 - 5/8)*100 = 37.5%
M2 = (1 - 5/13)*100 = 61.5%
M3 = 100%
Qu'en est celui-ci:
100 - ( ((2*Lev_distance(Q, Mi)) / (Q.length + Mi.length)) * 100 )
donne la même distance sur (Q, M1) et (Q,M2)
nombre Maximum de distance levenshtein est [l1, l2].max. Je pense que c'est vrai. Mais nous ne devons pas diviser par elle.
gem install levenshtein diff-lcs
Diff::LCS.lcs "abc", "qwer"
=> []
Levenshtein.distance("abc", "qwer").to_f / [3, 4].max
=> 1.0
Diff::LCS.lcs "abc", "cdef"
=> ["c"]
Levenshtein.distance("abc", "cdef").to_f / [3, 4].max
=> 1.0
Diff::LCS.lcs "1234", "34567890"
=> ["3", "4"]
Levenshtein.distance("1234", "34567890").to_f / [4, 8].max
=> 1.0
Levenshtein ne ressemble pas à un moyen fiable de comparer les cordes en %. Je ne veux pas traiter les chaînes de caractères 100%.
je peux vous recommander juste d'analyser la différence entre chaque séquence et LCS.
def get_similarity(sequence_1, sequence_2)
lcs_length = Diff::LCS::Internals.lcs(sequence_1, sequence_2).compact.length
lcs_length.to_f * 2 / (sequence_1.length + sequence_2.length)
end