¿Cómo se normaliza la distancia de Levenshtein para obtener la longitud máxima de alineación en lugar de la longitud de la cuerda?

Question

Problema: Algunos paquetes R presentan implementaciones de distancia Levenshtein para calcular la similitud de dos cadenas, p. http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html. Las distancias calculadas se pueden normalizar fácilmente para la longitud de la cuerda, p. dividiendo la distancia de Levenshtein por la longitud de la cuerda más larga involucrada o dividiéndola por la media de las longitudes de las dos cuerdas. Para algunas aplicaciones en lingüística (por ejemplo, investigación de dialectometría y multilingüismo receptivo), sin embargo, se recomienda normalizar la distancia bruta de Levenshtein para la longitud de la alineación de menor costo más larga (Heeringa, 2004: 130-132). Esto tiende a producir medidas de distancia que tienen más sentido desde un punto de vista lingüístico-perceptual.

Ejemplo: La cadena alemana "tsYklUs" (Zyklus = ciclo) se puede convertir en su cognado sueca "sYkEl" (cyckel = ciclo (bi)) en una alineación 7-ranura con dos inserciones (I) y dos sustituciones (s) para un costo total transformación de 4. normalizado Levenshtein distancia: 4/7

(a)

t--s--Y--k--l--U--s 
---s--Y--k--E--l--- 
=================== 
I-----------S--S--I = 4 

también es posible convertir las cuerdas en una alineación de 8 ranuras con 3 inserciones (I) y 1 eliminación (D), también para un costo de alineación total de 4. Normalizado Levenshtein distancia: 4/8

(B)

t--s--Y--k-----l--U--S 
---s--Y--k--E--l------ 
====================== 
I-----------D-----I--I = 4 

Esta última alineación tiene más sentido lingüísticamente, porque se alinea la [l] -phonemes uno con el otro en vez de con el [E] y [U] vocales.

Pregunta: ¿Alguien sabe de cualquier función R que me permita normalizar las distancias levenshtein para la alineación más larga de menor costo en lugar de para la longitud de la cadena correcta? ¡Gracias por tu aporte!

Referencia: W. J. Heeringa (2004), Medición de diferencias de la pronunciación dialectal utilizando Levenshtein distancia. Tesis doctoral, Universidad de Groningen. http://www.let.rug.nl/~heeringa/dialectology/thesis/

Edición - Solución: Creo que encontré una solución. La función adist puede devolver la alineación y parece ajustarse por defecto a la alineación de bajo costo más larga.Para ocupar el ejemplo anterior, aquí está la alineación asociado con sykel a tsyklus:

> attr(adist("sykel", "tsyklus", counts = TRUE), "trafos") 
    [,1]  
[1,] "IMMMDMII" 

Para calcular distancias longitud normalizada según lo recomendado por Heeringa (2004), podemos escribir una función modesta:

normLev.fnc <- function(a, b) { 
    drop(adist(a, b)/nchar(attr(adist(a, b, counts = TRUE), "trafos"))) 
} 

Para el ejemplo anterior, esto devuelve

> normLev.fnc("sykel", "tsyklus") 
[1] 0.5 

esta función una lso devuelve las distancias normalizadas correctos para Heeringa (2004: 131) Ejemplos:

> normLev.fnc("bine", "bEi") 
[1] 0.6 
> normLev.fnc("kaninçen", "konEin") 
[1] 0.5555556 
> normLev.fnc("kenEeri", "kenArje") 
[1] 0.5 

para comparar varios pares de cuerdas:

> L1 <- c("bine", "kaninçen", "kenEeri") 
> L2 <- c("bEi", "konEin", "kenArje") 
> diag(normLev.fnc(L1, L2)) 
[1] 0.6000000 0.5555556 0.5000000 

Answer 1

En caso de cualquier lingüistas se tropiezan con este post, me gustaría señalan que los algoritmos proporcionados por el paquete RecordLinkage no son necesariamente óptimo para comparar cadenas que no son ASCII, por ejemplo:

> levenshteinSim("väg", "way") 
[1] -0.3333333 
> levenshteinDist("väg", "way") 
[1] 4 
> levenshteinDist("väg", "wäy") 
[1] 2 
> levenshteinDist("väg", "wüy") 
[1] 3