Comment python-Levenshtein.le ratio est calculé

En regardant plus attentivement le code en C, j'ai trouvé que cette contradiction apparente est due au fait que ratio traite de la "remplacer" opération d'édition différemment que les autres opérations (c'est à dire avec un coût de 2), tandis que distance traite tous de la même manière avec un coût de 1.

Ceci peut être vu dans les appels à l'intérieur levenshtein_common fonction faite dans ratio_py fonction:

https://github.com/miohtama/python-Levenshtein/blob/master/Levenshtein.c#L727

static PyObject*
ratio_py(PyObject *self, PyObject *args)
{
  size_t lensum;
  long int ldist;

  if ((ldist = levenshtein_common(args, "ratio", 1, &lensum)) < 0) //Call
    return NULL;

  if (lensum == 0)
    return PyFloat_FromDouble(1.0);

  return PyFloat_FromDouble((double)(lensum - ldist)/(lensum));
}

et par distance_py fonction:

https://github.com/miohtama/python-Levenshtein/blob/master/Levenshtein.c#L715

static PyObject*
distance_py(PyObject *self, PyObject *args)
{
  size_t lensum;
  long int ldist;

  if ((ldist = levenshtein_common(args, "distance", 0, &lensum)) < 0)
    return NULL;

  return PyInt_FromLong((long)ldist);
}

qui aboutit finalement à des coûts différents arguments envoyés à une autre fonction interne, lev_edit_distance, qui a la doc suivante extrait de:

@xcost: If nonzero, the replace operation has weight 2, otherwise all
        edit operations have equal weights of 1.

Code de lev_edit_distance():

/**
 * lev_edit_distance:
 * @len1: The length of @string1.
 * @string1: A sequence of bytes of length @len1, may contain NUL characters.
 * @len2: The length of @string2.
 * @string2: A sequence of bytes of length @len2, may contain NUL characters.
 * @xcost: If nonzero, the replace operation has weight 2, otherwise all
 *         edit operations have equal weights of 1.
 *
 * Computes Levenshtein edit distance of two strings.
 *
 * Returns: The edit distance.
 **/
_LEV_STATIC_PY size_t
lev_edit_distance(size_t len1, const lev_byte *string1,
                  size_t len2, const lev_byte *string2,
                  int xcost)
{
  size_t i;

[RÉPONDRE]

Donc, dans mon exemple,

ratio('ab', 'ac') implique une opération de remplacement (coût de 2), sur le total de la longueur des cordes (4), d'où 2/4 = 0.5.

Qui explique le "comment", je suppose que le seul aspect serait le "pourquoi", mais pour le moment je suis satisfait de cette compréhension.

OriginalL'auteur cjauvin

(lensum - ldist) /lensum

ldist n'est pas la distance, est la somme des coûts

Chaque numéro de la matrice qui n'est pas le match qui vient d'en haut, de gauche à droite ou en diagonale

Si le nombre vient de la gauche, il est d'une Insertion, il vient d'en haut, c'est une suppression, il s'agit de la diagonale, c'est un remplacement

L'insérer et de supprimer le coût de la 1, et la substitution d'un coût de 2.
Le coût de remplacement est de 2 parce que c'est un supprimer et insérer des

ab ac coût est de 2 parce que c'est un remplacement

>>> import Levenshtein as lev
>>> lev.distance("ab","ac")
1
>>> lev.ratio("ab","ac")
0.5
>>> (4.0-1.0)/4.0    #Erro, the distance is 1 but the cost is 2 to be a replacement
0.75
>>> lev.ratio("ab","a")
0.6666666666666666
>>> lev.distance("ab","a")
1
>>> (3.0-1.0)/3.0    #Coincidence, the distance equal to the cost of insertion that is 1
0.6666666666666666
>>> x="ab"
>>> y="ac"
>>> lev.editops(x,y)
[('replace', 1, 1)]
>>> ldist = sum([2 for item in lev.editops(x,y) if item[0] == 'replace'])+ sum([1 for item in lev.editops(x,y) if item[0] != 'replace'])
>>> ldist
2
>>> ln=len(x)+len(y)
>>> ln
4
>>> (4.0-2.0)/4.0
0.5

Pour plus d'informations: python-Levenshtein de calcul du ratio de

Un autre exemple:

Le coût est 9, paragraphe 4, remplacer => 4*2=8 et 1 supprimer 1*1=1, 8+1=9)

str1=len("google") #6
str2=len("look-at") #7
str1 + str2 #13

distance = 5 (Selon le vecteur (7, 6) = 5 de la matrice)

ratio (13-9)/13 = 0.3076923076923077

>>> c="look-at"
>>> d="google"
>>> lev.editops(c,d)
[('replace', 0, 0), ('delete', 3, 3), ('replace', 4, 3), ('replace', 5, 4), ('replace', 6, 5)]
>>> lev.ratio(c,d)
0.3076923076923077
>>> lev.distance(c,d)
5

OriginalL'auteur rafaelcb21