Distanța Levenshtein

În teoria informației și teoria limbajului , distanța Levenshtein , sau distanța de editare , este o măsură pentru diferența dintre două șiruri. Introdus de omul de știință rus Vladimir Levenshtein în 1965 ^[1] , este folosit pentru a determina cât de asemănătoare sunt două corzi. Se aplică de exemplu pentru algoritmi simpli de verificare a ortografiei și pentru a căuta similaritate între imagini, sunete, texte etc.

Distanța Levenshtein dintre două șiruri A și B este numărul minim de modificări elementare care permit transformarea lui A în B. Prin modificare elementară se înțelege

ștergerea unui caracter,
înlocuirea unui personaj cu altul sau
inserarea unui caracter.

De exemplu, sunt necesare două modificări pentru a transforma „bara” în „biro”:

„bar” → „bir” (înlocuirea „a” cu „i”)
"bir" → "biro" (inserarea lui 'o')

Nu este posibil să transformați primul cuvânt în al doilea cu mai puțin de două modificări, astfel încât distanța Levenshtein dintre „bară” și „biro” este 2.

Algoritm

Un algoritm utilizat în mod obișnuit pentru a calcula distanța Levenshtein necesită utilizarea unei matrice de ( n + 1) × ( m + 1), unde n și m reprezintă lungimile celor două șiruri. Următorul pseudocod reprezintă o funcție LevenshteinDistance care ia ca argumente două șiruri str1 și str2 de lungime lenStr1 și lenStr2 și calculează distanța Levenshtein:

 int LevenshteinDistance ( char str1 [1..lenStr1], char str2 [1..lenStr2])
   // pentru fiecare i1 și i2, d [i1, i2] va conține distanța dintre Levenshtein
   // primele i1 caractere ale str1 și primele i2 caractere ale str2;
   // d este o matrice de lenStr1 + 1 rânduri și lenStr2 + 1 coloane
   declarați int d [0..lenStr1, 0..lenStr2]
   // i1 și i2 sunt folosite pentru a itera peste str1 și str2
   declara int i1, i2, cost
 
   pentru i1 de la 0 la lenStr1
       d [i1, 0]: = i1
   pentru i2 de la 0 la lenStr2
       d [0, i2]: = i2
 
   pentru i1 de la 1 la lenStr1
       pentru i2 de la 1 la lenStr2
           dacă str1 [i1 - 1] = str2 [i2 - 1] atunci cost: = 0
                                                   d [i1, i2]: = d [i1-1, i2-1]
                                              altfel cost: = 1
                 d [i1, i2]: = minim (
                               d [i1 - 1, i2] + 1, // inserare
                               d [i1, i2 - 1] + 1, // ștergere
                               d [i1 - 1, i2 - 1] + cost // înlocuire
                                       )
 
   returnează d [lenStr1, lenStr2]

Este posibil să se reducă ocuparea memoriei algoritmului anterior observând că la fiecare pas de iterație este suficient să se păstreze două rânduri ale matricei, cea curentă și cea anterioară. Folosind acest expedient este posibil să reduceți ocuparea memoriei de la O (mn) la O (m).

Implementare

Implementarea matricei

Acesta este codul C al implementării algoritmului de distanță Levenshtein folosind matrici

 int Levenshtein_distance ( char * x , char * y ) {
    int m = strlen ( x );
    int n = strlen ( y );

    registru int i , j ;

    int distanta ;

    int ** d = ( int ** ) malloc (( m + 1 ) * sizeof ( int * ));

    pentru ( i = 0 ; i <= m ; i ++ )
        d [ i ] = ( int * ) malloc (( n + 1 ) * sizeof ( int ));

    pentru ( i = 0 ; i <= m ; i ++ )
        d [ i ] [ 0 ] = i ;

    pentru ( j = 1 ; j <= n ; j ++ )
        d [ 0 ] [ j ] = j ;

    pentru ( i = 1 ; i <= m ; i ++ ) {
        pentru ( j = 1 ; j <= n ; j ++ ) {
            if ( x [ i - 1 ] ! = y [ j - 1 ]) {
                int k = minim (
                    d [ i ] [ j - 1 ],
                    d [ i - 1 ] [ j ],
                    d [ i - 1 ] [ j - 1 ]
                );
                d [ i ] [ j ] = k + 1 ;
            } altceva {
                d [ i ] [ j ] = d [ i - 1 ] [ j - 1 ];
            }
        }
    }

    distanță = d [ m ] [ n ];

    pentru ( i = 0 ; i <= m ; i ++ )
        gratuit ( d [ i ]);

    gratuit ( d );
    distanta de retur ;
}

int minimum ( int a , int b , int c ) {

/ * funcție care calculează minimum 3 valori * /

    int min = a ;

    dacă ( b < min ) min = b ;
    dacă ( c < min ) min = c ;

    retur min ;
}

Algoritm în AS3:

 funcție levenshteinDistance ( s1 : String , s2 : String ): int
{
  var m : int = s1 . lungime ;
  var n : int = s2 . lungime ;
  var matrice : Array = Array nou ();
  linia var : Array ;
  var i : int ;
  var j : int ;
  pentru ( i = 0 ; i <= m ; i ++)
  {
   line = new Array ();
   pentru ( j = 0 ; j <= n ; j ++)
   {
     dacă ( i ! = 0 ) linie . împinge ( 0 )
     altfel linie . împinge ( j );
   }
   linia [ 0 ] = i
   matrice . împingere ( linie );
  }
  var cost : int ; 
  pentru ( i = 1 ; i <= m ; i ++)
   pentru ( j = 1 ; j <= n ; j ++)
    {
      if ( s1 . charAt ( i - 1 ) == s2 . charAt ( j - 1 )) cost = 0
      altfel cost = 1 ;
      matrice [ i ] [ j ] = Math . min ( matrice [ i - 1 ] [ j ] + 1 , matrice [ i ] [ j - 1 ] + 1 , matrice [ i - 1 ] [ j - 1 ] + cost );
    }
  matrice de returnare [ m ] [ n ]; 
}

Implementare optimizată pentru memorie

Aceasta este urmată de implementarea optimizată de memorie a algoritmului de distanță Levenshtein. După cum sa spus anterior, pentru a calcula distanța Levenshtein este suficient să păstrați, la fiecare pas iterativ, rândul curent al matricei și cel care o precedă imediat.

 int Levenshtein_distance ( char * x , char * y ) {
    int m = strlen ( x );
    int n = strlen ( y );
    
    registru int i , j ;
    int distanta ;
    
    int * prev = malloc (( n + 1 ) * sizeof ( int ));
    int * curr = malloc (( n + 1 ) * sizeof ( int ));
    int * tmp = 0 ;
    
    pentru ( i = 0 ; i <= n ; i ++ )
        prev [ i ] = i ;

    pentru ( i = 1 ; i <= m ; i ++ ) {
        curr [ 0 ] = i ;
        pentru ( j = 1 ; j <= n ; j ++ ) {
            if ( x [ i - 1 ] ! = y [ j - 1 ]) {
                int k = minim ( curr [ j - 1 ], prev [ j - 1 ], prev [ j ]);
                curr [ j ] = k + 1 ;
            } altceva {
                curr [ j ] = prev [ j - 1 ];
            }
        }

        tmp = prev ;
        prev = curr ;
        curr = tmp ;
        
        memset (( void * ) curr , 0 , sizeof ( int ) * ( n + 1 ));
    }
    
    distanță = prev [ n ];
    
    liber ( curr );
    gratuit ( prev );
    
    distanța de întoarcere ;
}

Limite

Distanța Levenshtein are câteva limite superioare și inferioare simple:

este cel puțin diferența dintre lungimile celor două corzi;
este 0 dacă și numai dacă cele două șiruri sunt identice;
dacă lungimile celor două corzi sunt egale, distanța Levenshtein nu depășește distanța Hamming , adică egală cu lungimea corzilor;
limita superioară este egală cu lungimea celui mai lung șir.

Notă

^ Vezi articolul original în rusă

Bibliografie

( RU ) В.И. Левенштейн, Двоичные коды с исправлением выпадений, вставок и замещений символов, în Доклади, Сукад 163, nr. 4, 1965, pp. 845-8. Traducere: (EN) Levenshtein VI, Coduri binare capabile să corecteze ștergerile, inserțiile și inversările în Fizica sovietică Doklady, Vol. 10, 1966, pp. 707-10.
(EN) Eric Sven Ristad, Peter N. Yianilos, Learning String Edit Distance , 1997. Accesat la 22 iunie 2010.