Levenshteinova razdalja

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Levenshteinova razdalja (angl. Levenshtein distance ali edit distance) med dvema nizoma predstavlja minimalno število operacij, ki jih potrebujemo za preoblikovanje enaga niza v drugega. Operacije so izbris, vstavljanje in zamenjava znakov. Pri računanju razdalje med nizi zahtevamo, da se niz, ki ga najprej definiramo preoblikuje v drugi niz. Dolžini nizov sta lahko poljubni.

Definicija:
Naj bo s niz in s(i) i-ti element(i-ta crka) niza s. Za znaka a in b velja:

  • r(a, b) = 0, če a = b
  • r(a, b) = 1, sicer.


Naj bosta s in t niza, med katerima želimo izračunati Levenshteinovo razdaljo.

Pozor!!! V razlagi je povsod zamešan pojem vrstice in stolpca, kar bi bilo potzrebno popraviti!

Napolnimo prvo vrstico matrike: d(i, 0) = i; i = 0, 1,..., n
Napolnimo prvi stolpec matrike: d(0, j) = j; j = 0, 1,..., n
Za druge pare črk uporabimo: d(i, j) = min(d(i-1, j) + 1, d(i, j-1) + 1, d(i-1, j-1) + r(s(i), t(j))), kjer je 
d(i-1, j) + 1 - število operacij za izbris, 
d(i, j-1) + 1 - število operacij za vstavljanje in
d(i-1, j-1) + r(s(i), t(j)) - število operacij za zamenjavo znakov.


Primera:

  1. String s = "torba" in String t = "torba", potem je razdalja(s,t) = 0, ker sta niza identična.
  2. String s = "torba" in String t = "borba", potem je razdalja(s,t) = 1, ker črko "t" iz niza s nadomestimo s črko "b" iz niza t.

Različnejša kot sta niza, tem večja je njuna razdalja.

Implementacija v Javi

public class Levenshtein{
  String a,b;
  
  /*public Levenshtein(){}*/
  
  int r(int i,int j){
    //ce sta crki nizov na (i-1). mestu in (j-1).mestu enaki,
    //vrnemo nic, drugace vrnemo 1.
    if (a.charAt(i-1) == b.charAt(j-1)) return 0;
    return 1;
  }
  
  int distance(int i,int j){
    if (j == 0) return i; //napolnimo 1. vrstico      
    if (i == 0) return j; //napolnimo 1. stolpec
      
    // izracunamo minimum: 3 moznosti
    // (i-1,j)+1 izbris  
    // (i,j-1)+1 vstavek
    // (i-1,j-1) + r(i,j) zamenjava
    // s pomocjo teh operacij izracunamo njihov minimum.
    int d = distance(i-1, j) + 1;
    int t = distance(i, j-1) + 1;
    if (t < d) d = t;
    t = distance(i-1, j-1) + r(i, j);
    if (t < d) d = t;
    return d;
  }
  
  public int distance(String a1, String b1){
    a = a1; 
    b = b1;
    return distance(a.length(), b.length());
  }
    
  //primerjamo niza
  public void compare(String a,String b){
    System.out.println("a:" + a + "  b:" + b + "  razdalja:" + distance(a,b));
  }
  
  //TEST
  public static void main(String argv[]){
    Levenshtein l = new Levenshtein();
    l.compare("QWERTY","ASDFGH");
    l.compare("Mojca","Miha");
  }
}

Razlaga algoritma po korakih

1. korak:

Naj bo n dolžina niza s.
Naj bo m dolžina niza t.
Če n = 0, vrni m //če prvega niza ni, bomo niza “izenačili” tako, da bomo v drugem nizu izbrisali vse črke, torej bomo m-krat                  
                   opravili operacijo izbris znaka.
Če m = 0, vrni n //če drugega niza ni, bomo niza “izenačili” tako, da bomo v prvem nizu izbrisali vse črke, torej bomo n-krat 
                   opravili operacijo izbris znaka
Konstruiramo matriko z (n + 1) vrsticami in (m + 1) stolpci.

2. korak:

Napolnimo prvo vrstico s številkami od 0 do m.
Napolnimo prvi stolpec s številkami od 0 do n.

3. korak:

Pregledamo vsak znak niza s (i od 1 → n). 
Pregledamo vsak znak niza t (j od 1 → m). 

3.1. korak:

Primerjamo i-ti znak niza s in j-ti znak niza t:
Če je s[i] enak t[j], je r = 0.
Če s[i] ni enak t[j], je r = 1. 

3.2. korak: Naj bo element d[i][j] minimalno število operacij, ki jih potrebujemo, da iz i znakov prvega niza dobimo prvih j znakov drugega niza. Kako pa to izračunamo?

d[i-1][j] pove, kako najhitreje prvih i-1 znakov predelamo v prvih j znakov drugega niza. Če torej v prvem nizu i-ti znak zbrišemo, dobimo ravno situacijo, ki jo obravnava d[i-1][j]. Torej je prvi kandidat za minimalno število operacij:

   a. d[i-1][j] + 1 //za izbris (kandidat nad d[i][j] + 1)

d[i][j-1] pove, kako najhitreje prvih i znakov predelamo v prvih j-1 znakov drugega niza. Če torej predelanemu nizu, ki ga dobimo z d[i-1][j] operacijami dodamo j-ti znakm dobimo položaj, kot ga opisuje d[i][j]. Torej je drugi kandidat za minimalno število operacij:

   b. d[i][j-1] + 1 // vstavek (kandidat levo od d[i][j] + 1)

Če vemo, kako iz prvih i-1 znakov dobimo prvih j-1 znakov drugega niza, do "podaljšanja" obeh nizov za 1 pridemo bodisi tako, da i-ti znak zamenjamo z j-tim, ali pa sprememba sploh ni potrebna (če sta znaka enaka). Ravno to pa nam pove r. Torej je tretji kanidat

c. d[i-1][j-1] + r // substitucija (kandidat diagonalno levo nad d[i][j] + r)

In katero od teh treh možnosti izbrati? Seveda najboljšo! Torej je

 d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + r). 

4. korak:

Rešitev: Minimalno število operacij, da iz prvega niza dobimo drugi niz.

Uporaba algoritma

Algoritem razdalje med nizi se uporablja:
- pri preverjanju pravopisnih napak
- pri DNA analizah
- za odkrivanje plagiatov
- pri merjenju razlik med dialekti
- pri odpravljanju govornih napak...

Viri

Osebna orodja