python - remove - levenshtein distance online

Cómo se calcula python-Levenshtein.ratio

Question

De acuerdo con la fuente python-Levenshtein.ratio :

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

se calcula como (lensum - ldist) / lensum . Esto funciona para

distance(''ab'', ''a'') = 1
ratio(''ab'', ''a'') = 0.666666

Sin embargo, parece romper con

distance(''ab'', ''ac'') = 1
ratio(''ab'', ''ac'') = 0.5

Siento que debo faltar algo muy simple ... pero ¿por qué no 0.75 ?

Answer 1

Al observar más detenidamente el código C, descubrí que esta aparente contradicción se debe al hecho de que la ratio trata la operación de edición "reemplazar" de manera diferente a las otras operaciones (es decir, con un costo de 2), mientras que la distance trata de la misma manera. con un costo de 1.

Esto se puede ver en las llamadas a la función interna levenshtein_common realizada dentro de la función ratio_py :

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));
}

y por la función distance_py :

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);
}

que en última instancia resulta en que se envíen diferentes argumentos de costo a otra función interna, lev_edit_distance , que tiene el siguiente fragmento de documento:

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

Código 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;

[RESPONDER]

Así que en mi ejemplo,

ratio(''ab'', ''ac'') implica una operación de reemplazo (costo de 2), sobre la longitud total de las cuerdas (4), por lo tanto 2/4 = 0.5 .

Eso explica el "cómo", supongo que el único aspecto restante sería el "por qué", pero por el momento estoy satisfecho con este entendimiento.

Answer 2

Aunque no hay un estándar absoluto, la distancia normalizada de Levensthein se define con mayor frecuencia ldist / max(len(a), len(b)) . Eso daría .5 para ambos ejemplos.

El max tiene sentido ya que es el límite superior más bajo en la distancia de Levenshtein: para obtener a de b donde len(a) > len(b) , siempre puede sustituir los primeros elementos de b de len(b) con los correspondientes de a , luego inserte la parte faltante a[len(b):] , para un total de len(a) operaciones de edición.

Este argumento se extiende de manera obvia al caso donde len(a) <= len(b) . Para convertir la distancia normalizada en una medida de similitud, réstela de uno: 1 - ldist / max(len(a), len(b)) .

Answer 3

(lensum - ldist) / lensum

ldist no es la distancia, es la suma de los costos

Cada número de la matriz que no coincide coincide con los de arriba, desde la izquierda o en diagonal

Si el número proviene de la izquierda, es una inserción, viene de arriba, es una eliminación, proviene de la diagonal, es un reemplazo.

El inserto y la eliminación tienen un costo de 1, y la sustitución tiene un costo de 2. El costo de reemplazo es 2 porque es una eliminación e inserción

El costo de CA es 2 porque es un reemplazo

>>> 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

Para más información: cálculo del cociente python-levenshtein.

Otro ejemplo:

El costo es 9 (4 reemplazar => 4 * 2 = 8 y 1 eliminar 1 * 1 = 1, 8 + 1 = 9)

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

distancia = 5 (según el vector (7, 6) = 5 de la matriz)

relación es (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

Answer 4

Levenshtein distancia para ''ab'' y ''ac'' como abajo:

entonces la alineación es:

  a c
  a b 

Longitud de alineación = 2
número de desajustes = 1

Levenshtein Distance es 1 porque solo se requiere una sustitución para transferir ac a ab (o revertir)

Relación de distancia = (Distancia de Levenshtein) / (Longitud de alineación) = 0.5

EDITAR

estas escribiendo

(lensum - ldist) / lensum = (1 - ldist/lensum) = 1 - 0.5 = 0.5.

Pero esto está emparejando (no la distancia)
REFFRENCE , usted puede notar su escrito

Matching %

p = (1 - l/m) × 100

Donde l es la levenshtein distance y m es la length of the longest of the two palabras:

_{( Aviso : algunos autores usan el más largo de los dos, yo usé la longitud de alineación)}

(1 - 3/7) × 100 = 57.14...  

  (Word 1    Word 2    RATIO   Mis-Match   Match%
   AB         AB         0       0        (1 - 0/2 )*100  = 100%  
   CD         AB         1       2        (1 - 2/2 )*100  = 0%   
   AB         AC        .5       1        (1 - 1/2 )*100  = 50%      

_{¿Por qué algunos autores se dividen por la longitud de alineación, otros por la longitud máxima de uno de los dos? ..., porque Levenshtein no considera la brecha. Distancia = número de ediciones (inserción + eliminación + reemplazo), mientras que el algoritmo de Needleman-Wunsch que es la alineación global estándar considera la brecha. Esta es la diferencia (brecha) entre Needleman – Wunsch y Levenshtein, por lo que gran parte del papel utiliza la distancia máxima entre dos secuencias ( PERO ESTA ES MI PROPIA COMPRENSIÓN, Y NO SOY SEGURO DEL 100% )}

Aquí está IEEE TRANSACTIONS ON PAITERN ANALYSIS: Cálculo de la distancia de edición normalizada y aplicaciones. En este documento, la distancia de edición normalizada es la siguiente:

Dadas dos cadenas X e Y sobre un alfabeto finito, la distancia de edición normalizada entre X e Y, d (X, Y) se define como el mínimo de W (P) / L (P) w, aquí P es una ruta de edición entre X e Y, W (P) es la suma de los pesos de las operaciones de edición elementales de P, y L (P) es el número de estas operaciones (longitud de P).