Recabamos por diferentes espacios y así tener para ti la solución para tu duda, en caso de dudas puedes dejarnos tu comentario y te contestamos porque estamos para ayudarte.
Distancia de Levenshtein por 'ab' y 'ac' como a continuación:
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 en ab (o al revés)
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 es pareo (no distancia)
REFFRENCE, puede notar que está escrito
Matching %
p = (1 - l/m) × 100
Donde l es el levenshtein distance y m es el 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 dividen por la longitud de alineación, otros por la longitud máxima de uno de ambos? .., 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 una alineación global estándar considera la brecha. Esta es la diferencia (brecha) entre Needleman – Wunsch y Levenshtein, por lo que mucho papel usar distancia máxima entre dos secuencias (PERO ESTE ES MI PROPIO ENTENDIMIENTO, Y NO ESTOY SEGURO AL 100%)
Aquí están las TRANSACCIONES DE IEEE EN EL ANÁLISIS DE PAITERN: Cálculo de aplicaciones y distancia de edición normalizada en este papel Distancia de edición normalizada como sigue:
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).
Al observar más detenidamente el código C, descubrí que esta aparente contradicción se debe al hecho de que 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 distance los trata a todos por igual con un costo de 1.
Esto se puede ver en las llamadas al interno. levenshtein_common función hecha dentro ratio_py función:
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 distance_py función:
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);
lo que en última instancia da como resultado que se envíen diferentes argumentos de costos 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;
[ANSWER]
Entonces en mi ejemplo,
ratio('ab', 'ac') implica una operación de reemplazo (costo de 2), sobre la longitud total de las cadenas (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 esta comprensión.
(lensum - ldist) / lensum
ldist no es la distancia, es la suma de los costos
Cada número de array que no coincida viene de arriba, de izquierda o diagonal
Si el número viene de la izquierda, es una inserción, viene de arriba, es una eliminación, proviene de la diagonal, es un reemplazo.
La inserción 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 y una inserción
ab 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 obtener más información: cálculo de la relación 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)
la 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
Si tienes alguna perplejidad y forma de reformar nuestro post puedes ejecutar una nota y con placer lo estudiaremos.