Rang en pourcentage des correspondances en utilisant la correspondance Levenshtein Distance

Je suis en train d'essayer de correspondre à un seul terme de recherche à l'encontre d'un dictionnaire des correspondances possibles à l'aide d'un algorithme 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 tiens à vous présenter les résultats classés pourcentage de la liste de "N" (par exemple 10) matchs.

Depuis la chaîne de recherche peut être plus longue ou plus courte que l'individu dictionnaire des chaînes, ce qui serait une logique appropriée pour exprimer la distance en pourcentage, ce qui serait qualitativement refelct comment fermer "en pourcentage" est chaque résultat à la chaîne de requête, à 100%, indiquant une correspondance exacte.

Je l'ai considéré comme l'une des 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 négatif pourcentages dans le cas où la distance est plus grande que celle de la recherche de la longueur des chaînes, où le match de la chaîne est longue. Par exemple la requête "ABC" appariés avec "ABC" serait un résultat négatif, match pour cent.

L'Option 2 ne semble pas donner une cohérence pourcentage d'un ensemble de Mi, comme chaque calcul serait peut-être utiliser un autre dénominateur et donc la résultante des valeurs en pourcentage ne serait pas normalisée.

Seule autre façon que je peux penser à est de fossé de la comparaison de la lev_distance en string longueurs, mais au lieu de présenter l'comparée des distances de haut "N" correspond qu'une inversion de rang centile (100 percentile-rank).

Toute pensée? Existe-il des approches mieux? Je dois être en manque de quelque chose comme Levenshtein est probablement le plus commun de l'algorithme pour les correspondances floues, et ce doit être un problème très commun.

source d'informationauteur user1368587