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.

1. paper → caper (substitució de la 'p' per la 'c')
2. caper → carer (substitució de la 'p' per la 'r')
3. 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:

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost

for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j

for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution

)

return d[lenStr1, lenStr2]

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.

C++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
 int N1 = s1.size();
 int N2 = s2.size();
 int i, j;
 vector<int> T(N2+1);

 for (i = 0; i <= N2; i++)
 T[i] = i;

 for (i = 0; i < N1; i++) {
 T[0] = i+1;
 int corner = i;
 for (j = 0; j < N2; j++) {
 int upper = T[j+1];
 if (s1[i] == s2[j])
 T[j+1] = corner;
 else
 T[j+1] = min(T[j], min(upper, corner)) + 1;
 corner = upper;
 }
 }
 return T[N2];
}

C#

public int LevenshteinDistance(string s, string t, out double percentatge)
{
 percentatge = 0;

 // d és una matriu amb m+1 files i n+1 columnes
 int cost = 0;
 int m = s.Length;
 int n = t.Length;
 int[,] d = new int[m + 1, n + 1]; 

 // Verifica que existeixi alguna cosa per comparar
 if (n == 0) return m;
 if (m == 0) return n;

 // Omple la primera columna i la primera fila.
 for (int i = 0; i <= m; d[i, 0] = i++) ;
 for (int j = 0; j <= n; d[0, j] = j++) ;


 /// recorre la matriu omplint cada un dels pesos.
 /// i columnes, j files
 for (int i = 1; i <= m; i++)
 {
 // recorre per j
 for (int j = 1; j <= n; j++)
 { 
 /// si són iguals en posiciones equidistants el pes és 0
 /// en cas contrari el pes és 1.
 cost = (s[i - 1] == t[j - 1]) ? 0 : 1; 
 d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, //Supressió
 d[i, j - 1] + 1), //Inserció 
 d[i - 1, j - 1] + cost); //Substitució
 }
 }

 /// Calculem el percentatge de canvis en la paraula.
 if (s.Length > t.Length)
 percentatge = ((double)d[m, n] / (double)s.Length);
 else
 percentatge = ((double)d[m, n] / (double)t.Length); 
 return d[m, n]; 
}

Java

Implementada com una classe estàtica.

public class LevenshteinDistance {
 private static int minimum(int a, int b, int c) {
 if(a<=b && a<=c)
 {
 return a;
 } 
 if(b<=a && b<=c)
 {
 return b;
 }
 return c;
 }

 public static int computeLevenshteinDistance(String str1, String str2) {
 return computeLevenshteinDistance(str1.toCharArray(),
 str2.toCharArray());
 }

 private static int computeLevenshteinDistance(char [] str1, char [] str2) {
 int [][]distance = new int[str1.length+1][str2.length+1];

 for(int i=0;i<=str1.length;i++)
 {
 distance[i][0]=i;
 }
 for(int j=0;j<=str2.length;j++)
 {
 distance[0][j]=j;
 }
 for(int i=1;i<=str1.length;i++)
 {
 for(int j=1;j<=str2.length;j++)
 { 
 distance[i][j]= minimum(distance[i-1][j]+1,
 distance[i][j-1]+1,
 distance[i-1][j-1]+
 ((str1[i-1]==str2[j-1])?0:1));
 }
 }
 return distance[str1.length][str2.length];

 }
}

Perl

 sub fastdistance
 {
 my $word1 = shift;
 my $word2 = shift;

 return 0 if $word1 eq $word2;
 my @d;

 my $len1 = length $word1;
 my $len2 = length $word2;

 $d[0][0] = 0;
 for (1.. $len1) {
 $d[$_][0] = $_;
 return $_ if $_!=$len1 && substr($word1,$_) eq
 substr($word2,$_);
 }

 for (1.. $len2) {
 $d[0][$_] = $_;
 return $_ if $_!=$len2 && substr($word1,$_) eq
 substr($word2,$_);
 }

 for my $i (1.. $len1) {
 my $w1 = substr($word1,$i-1,1);
 for (1.. $len2) {
 $d[$i][$_] = _min($d[$i-1][$_]+1, 
 $d[$i][$_-1]+1,
 $d[$i-1][$_-1]+($w1 eq
 substr($word2,$_-1,1) ?
 0 : 1));
 }
 }
 return $d[$len1][$len2];
 }

 sub _min
 {
 return $_[0] < $_[1]
 ? $_[0] < $_[2] ? $_[0] : $_[2]
 : $_[1] < $_[2] ? $_[1] : $_[2];
 }

Python

def distance(str1, str2):
 d=dict()
 for i in range(len(str1)+1):
 d[i]=dict()
 d[i][0]=i
 for i in range(len(str2)+1):
 d[0][i] = i
 for i in range(1, len(str1)+1):
 for j in range(1, len(str2)+1):
 d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+(not str1[i-1] == str2[j-1]))
 return d[len(str1)][len(str2)]

Ruby

class String
 def levenshtein(other)
 other = other.to_s
 distance = Array.new(self.size + 1, 0)
 (0..self.size).each do |i|
 distance[i] = Array.new(other.size + 1)
 distance[i][0] = i
 end
 (0..other.size).each do |j|
 distance[0][j] = j
 end

 (1..self.size).each do |i|
 (1..other.size).each do |j|
 distance[i][j] = [distance[i - 1][j] + 1,
 distance[i][j - 1] + 1,
 distance[i - 1][j - 1] + ((self[i - 1] == other[j - 1]) ? 0 : 1)].min
 end
 end
 distance[self.size][other.size]
 end
end

puts "casa".levenshtein "calle" #=> 3

PHP

<?
 $lev = levenshtein($input, $word);
?>

Delphi

function LevenshteinDistance(Str1, Str2: String): Integer;
var
 d : array of array of Integer;
 Len1, Len2 : Integer;
 i,j,cost:Integer;
begin
 Len1:=Length(Str1);
 Len2:=Length(Str2);
 SetLength(d,Len1+1);
 for i := Low(d) to High(d) do
 SetLength(d[i],Len2+1);

 for i := 0 to Len1 do
 d[i,0]:=i;

 for j := 0 to Len2 do
 d[0,j]:=j;

 for i:= 1 to Len1 do
 for j:= 1 to Len2 do
 begin
 if Str1[i]=Str2[j] then
 cost:=0
 else
 cost:=1;
 d[i,j]:= Min(d[i-1, j] + 1, // deletion,
 Min(d[i, j-1] + 1, // insertion
 d[i-1, j-1] + cost) // substitution
);
 end;
 Result:=d[Len1,Len2];
end;

VB.NET

 Public Function Levenshtein(ByVal s1 As String, ByVal s2 As String) As Integer
 Dim coste As Integer = 0
 Dim n1 As Integer = s1.Length
 Dim n2 As Integer = s2.Length
 Dim m As Integer(,) = New Integer(n1, n2) {}
 For i As Integer = 0 To n1
 m(i, 0) = i
 Next
 For i As Integer = 1 To n2
 m(0, i) = i
 Next
 For i1 As Integer = 1 To n1
 For i2 As Integer = 1 To n2
 coste = If((s1(i1 - 1) = s2(i2 - 1)), 0, 1)
 m(i1, i2) = Math.Min(Math.Min(m(i1 - 1, i2) + 1, m(i1, i2 - 1) + 1), m(i1 - 1, i2 - 1) + coste)
 Next
 Next
 Return m(n1, n2)
 End Function

ActionScript 3.0

public class StringUtils 
{ 
 public static function levenshtein(s1:String, s2:String):int
 {		
 if (s1.length == 0 || s2.length == 0)
	 return 0;

 var m:uint = s1.length + 1;
 var n:uint = s2.length + 1;
 var i:uint, j:uint, cost:uint;
 var d:Vector.<Vector.<int>> = new Vector.<Vector.<int>>();

 for (i = 0; i < m; i++)
 {
 d[i] = new Vector.<int>();
 for (j = 0; j < n; j++)
 d[i][j] = 0;
 }
			
 for (i = 0; i < m; d[i][0] = i++) ;
 for (j = 0; j < n; d[0][j] = j++) ;

 for (i = 1; i < m; i++)
 {
	 for (j = 1; j < n; j++)
 { 
 cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
 d[i][j] = Math.min(Math.min(d[i - 1][j] + 1,
 d[i][j - 1] + 1),
 d[i - 1][j - 1] + cost);
 }
 }
			
 return d[m-1][n-1];
 }
}

ColdFusion

<cfscript>
function levDistance(s,t) {
	var d = ArrayNew(2);
	var i = 1;
	var j = 1;
	var s_i = "A";
	var t_j = "A";
	var cost = 0;
	
	var n = len(s)+1;
	var m = len(t)+1;
	
	d[n][m]=0;
	
	if (n is 1) {
		return m;
	}
	
	if (m is 1) {
		return n;
	}
	
	 for (i = 1; i lte n; i=i+1) {
 d[i][1] = i-1;
 }

 for (j = 1; j lte m; j=j+1) {
 d[1][j] = j-1;
 }
	
	for (i = 2; i lte n; i=i+1) {
 s_i = Mid(s,i-1,1);

	 for (j = 2; j lte m; j=j+1) {
 	t_j = Mid(t,j-1,1);

		if (s_i is t_j) {
 cost = 0;
 }
 else {
 cost = 1;
 }
		d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1);
		d[i][j] = min(d[i][j], d[i-1][j-1] + cost);
 }
 }
	
 return d[n][m];
}
</cfscript>

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.

Vegeu també

• Índex de Jaccard
• Algorisme de Needleman-Wunsch