Come normalizzare la distanza di Levenshtein per la massima lunghezza di allineamento piuttosto che per la lunghezza della stringa?

Question

Problema: Alcuni pacchetti R dispongono di implementazioni a distanza di Levenshtein per calcolare la somiglianza di due stringhe, ad es. http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html. Le distanze calcolate possono essere facilmente normalizzate per la lunghezza della stringa, ad es. dividendo la distanza di Levenshtein per la lunghezza della corda più lunga coinvolta o dividendola per la media delle lunghezze delle due stringhe. Per alcune applicazioni in linguistica (ad es. Dialettometria e ricerca del multilinguismo ricettivo), tuttavia, si raccomanda di normalizzare la distanza grezza di Levenshtein per la lunghezza dell'allineamento meno costoso (Heeringa, 2004: 130-132). Questo tende a produrre misure di distanza che hanno più senso da un punto di vista linguistico percettivo.

Esempio: La stringa tedesca "tsYklUs" (Zyklus = ciclo) può essere convertito nel suo affine svedese "sYkEl" (cyckel = (BI) ciclo) in un allineamento 7 slot con due inserti (I) e due sostituzioni (S) per un costo totale di trasformazione 4. normalizzato Levenshtein distanza: 4/7

(a)

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

è anche possibile convertire le stringhe in un allineamento 8 slot con 3 inserimenti (I) e 1 cancellazione (D), anche per un costo totale di allineamento di 4. normalizzato Levenshtein distanza: 4/8

(B)

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

Quest'ultimo allineamento più senso linguisticamente, perché allinea la [l] -phonemes tra loro anziché con [E] e [U] vocali.

Domanda: Qualcuno sa di qualsiasi funzione R che mi permettesse di normalizzare distanze Levenshtein per l'allineamento più lunga di minor costo, piuttosto che per la lunghezza della stringa corretta? Grazie per il tuo contributo!

Riferimento: W.J. Heeringa (2004), di misurazione delle differenze di pronuncia dialettale utilizzando Levenshtein distanza. Tesi di dottorato, Università di Groningen. http://www.let.rug.nl/~heeringa/dialectology/thesis/

Modifica - Soluzione: Penso di aver trovato una soluzione. La funzione adist può restituire l'allineamento e sembra di default all'allineamento più lungo a basso costo.Per riprendere l'esempio precedente, ecco l'allineamento associato con sykel-tsyklus:

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

Per calcolare distanze di lunghezza normalizzata, come raccomandato dal Heeringa (2004), possiamo scrivere una funzione modesta:

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

Per l'esempio precedente, questo restituisce

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

questa funzione un LSO restituisce le distanze normalizzati corretti per Heeringa di (2004: 131) Esempi:

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

per confrontare diverse paia di stringhe:

> 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

Nel caso in cui eventuali linguisti inciampare su questo post, mi piacerebbe sottolineare che gli algoritmi forniti dal pacchetto RecordLinkage non sono necessariamente ottimali per confrontare stringhe non ASCII, ad esempio:

> 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