Distància de Levenshtein

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 de similars són 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ó.

Exemple[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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 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[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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++[modifica | modifica el codi]

#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#[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

 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[modifica | modifica el codi]

 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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

Delphi[modifica | modifica el codi]

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[modifica | modifica el codi]

 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[modifica | modifica el codi]

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[modifica | modifica el codi]

<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[modifica | modifica el codi]

  • El projecte ASJP 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.[1]
  • 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é[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. ASJP - World Language Tree