# Distància de Levenshtein

La distància de Levenshtein també anomenada distància d'edició o distància entre paraules és en teoria de la informació i la informàtica, el nombre mínim d'edicions requerides per a transformar una cadena de caràcters en una altra. Una edició pot ser la inserció, la supressió o la substitució d'un caràcter. Porta el nom del matemàtic i científic rus Vladimir Levenshtein, que va considerar aquesta distància el 1965. És útil en programes que determinen com són de similars dues cadenes de caràcters, com és el cas dels correctors ortogràfics, els sistemes de correcció per al reconeixement òptic de caràcters i el programari per ajudar a la traducció del llenguatge natural basat en la memòria de traducció.

## Definició

Matemàticament, la distància de Levenshtein entre dues cadenes $a,b$ (de longitud $|a|$ i $|b|$ respectivament) està donat per $\operatorname {lev} _{a,b}(|a|,|b|)$ on
    $\qquad \operatorname {lev} _{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ if}}\min(i,j)=0,\\\min {\begin{cases}\operatorname {lev} _{a,b}(i-1,j)+1\\\operatorname {lev} _{a,b}(i,j-1)+1\\\operatorname {lev} _{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}\end{cases}}&{\text{ d'una altra manera.}}\end{cases}}$
on $1_{(a_{i}\neq b_{j})}$ és la funció indicatriu igual a 0 quan $a_{i}=b_{j}$ i igual a 1 d'una altra manera, i $\operatorname {lev} _{a,b}(i,j)$ és la distància entre els primers $i$ caràcters de $a$ i els primers $j$ caràcters de $b$.
S'ha de tenir en compte que el primer element al mínim correspon a la supressió (des de $a$ fins a $b$), el segon a la inserció i el tercer a coincidir o no coincidir, depenent de si els respectius símbols són iguals.

### Exemple

Per exemple, la distància de Levenshtein entre "paper" i "carrer" és de 3 perquè es necessiten com a mínim tres edicions per passar d'una cadena de caràcters a una altra, i no hi ha manera de fer-ho en menys edicions.
* paper → caper (substitució de la 'p' per la 'c')
* caper → carer (substitució de la 'p' per la 'r')
* carer → carrer (inserció de la 'r' entre la 'r' i la 'e')

## Relació amb altres mètodes de càlcul de distància d'edició

La Distància Levenshtein no és l'única forma coneguda de calcular la distància d'edició. Hi ha variacions que es poden obtenir en canviar el conjunt d'operacions permeses edició. Per exemple:
* La longitud de la subseqüència comuna més llarga s'obté només a partir de la inserció i la supressió.
* La distància de Damerau-Levenshtein permet la inserció, la supressió, la substitució i a més la transposició de dos caràcters adjacents.
* La distància de Hamming només permet la substitució (i per tant, només s'aplica a les cadenes de caràcters de la mateixa longitud).
La distància d'edició, en general, es defineix com un indicador parametritzable en el qual està disponible un repertori d'operacions d'edició, i a cada operació se li assigna un cost (pot ser infinit). Això és més generalitzat pels algorismes d'alineament de seqüències d'ADN, com ara l'algorisme de Smith-Waterman, que fan que el cost d'una operació depengui d'on s'apliqui.

## L'algorisme

Es tracta d'un algorisme de tipus bottom-up (de baix a dalt) comú en la programació dinàmica. S'utilitza una matriu (n + 1) × (m + 1), on n i m són les longituds de les cadenes de caràcters. A continuació l'algorisme en pseudocodi per a una funció LevenshteinDistance, que agafa dues cadenes de caràcters, str1 de longitud lenStr1 i str2 de longitud lenStr2, i calcula la distància Levenshtein entre elles:
L'invariant mantingut durant l'algorisme és que pugui transformar el segment inicial str1[1..i] en str2[1..j] amb un mínim de d[i,j] operacions. Al final, l'element ubicat a la part inferior dreta de la matriu conté el resultat.

## Implementació

A continuació es pot veure la implementació de la funció per a diferents llenguatges de programació. Altres llenguatges d'alt nivell com PHP o les funcions d'usuari de MySQL ja incorporen la implementació per a ser utilitzada.

### Java

Implementada com una classe estàtica.

### ColdFusion
## Aplicacions

* El projecte ASJP Arxivat 2014-01-27 a Wayback Machine. utilitza la distància de Levenshtein total en una llista de paraules de diferents llengües del món, per a mesurar la similitud o proximitat d'aquestes. Amb aquesta distància calculada es proposa una classificació filogenètica temptativa de les llengües del món.
* La distància de Damerau-Levenshtein és una generalització de la distància de Levenshtein utilitzada pels correctors ortogràfics i en la detecció de fraus en llistes de dades.

## Referències

* ↑ «ASJP - World Language Tree». Arxivat de l'original el 2010-01-13. [Consulta: 19 març 2011].

## Vegeu també

* Índex de Jaccard
* Algorisme de Needleman-Wunsch