Levenshteinova razdalja/Primer algoritma

Iz MaFiRaWiki

Želimo izračunati razdaljo med nizoma TORBA in BORBA, kar pomeni, da želimo izračunati minimalno vrednost operacij (zamenjave, izbrisi in/ali vstavljanja črk(znakov)), da iz prvega niza dobimo drugi niz.

1. Konstruiramo matriko m×n in v prvo vrstico matrike vpišemo cifre od 0 do n, v prvi stolpec pa cifre od 0 do m:

b o r b a
0 1 2 3 4 5
t 1
o 2
r 3
b 4
a 5


2. V naslednjih korakih preverjamo enakost znakov prvega in drugega niza, ter računamo posamezne elemente matrike:

  • i = 1:

d[1][0] = 1 (že imamo)

Dolžina med nizoma “T” in “B”: pove nam, koliko operacij potrebujemo, da iz “T” dobimo “B”: d[1][1] = minimum (d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + r) = minimum (d[0][1] + 1, d[1][0] + 1, d[0][0] + 1) = minimum (2, 2, 1) = 1
Oglejmo si ta izračun bolj podrobno:

  • d[0][1] + 1: iščemo minimalno število operacij, iz niza “T” dobimo prazen niz “” + 1(še ena operacija) = 1 + 1 = 2
  • d[1][0] + 1: iščemo minimalno število operacij, da iz praznega niza (“”) dobimo niz “B”+ 1(še ena operacija) = 1 + 1 = 2
  • d[0][0] + r : iščemo minimalno število operacij, da iz praznega niza(“”) dobimo prazen niz(“”) + 1(ker znak T ni enak znaku B) = 1 + 0 = 1

Minimum teh treh izračunov (2, 2, 1) nam da dolžino 1.


Dolžina med nizoma “TO” in “B”: pove nam, koliko operacij potrebujemo, da iz “TO” dobimo “B”: d[1][2] = minimum (d[0][2] + 1, d[1][1] + 1, d[0][1] + r) = 2

Dolžina med nizoma “TOR” in “B”: pove nam, koliko operacij potrebujemo, da iz “TOR” dobimo “B”: d[1][3] = minimum (d[0][3] + 1, d[1][2] + 1, d[0][2] + r) = 3

Dolžina med nizoma “TORB” in “B”: pove nam, koliko operacij potrebujemo, da iz “TORB” dobimo “B”: d[1][4] = minimum (d[0][4] + 1, d[1][3] + 1, d[0][3] + r) = 3

Dolžina med nizoma “TORBA” in “B”: pove nam, koliko operacij potrebujemo, da iz “TORBA” dobimo “B”: d[1][5] = minimum (d[0][5] + 1, d[1][4] + 1, d[0][4] + r) = 4


Izračunane dolžine vstavimo v drugi stolpec matrike:

b o r b a
0 1 2 3 4 5
t 1 1
o 2 2
r 3 3
b 4 3
a 5 4


  • i = 2:

d[2][0] = 2 (že imamo)

Dolžina med nizoma “T” in “BO”: pove nam, koliko operacij potrebujemo, da iz “T” dobimo “BO”: d[2][1] = minimum (d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + r) = minimum (d[1][1] + 1, d[2][0] + 1, d[1][0] + r) = minimum (2, 3, 2) = 2

Dolžina med nizoma “TO” in “BO”: pove nam, koliko operacij potrebujemo, da iz “TO” dobimo “BO”: d[2][2] = minimum (d[1][2] + 1, d[2][1] + 1, d[1][1] + r) = 1
Oglejmo si ta izračun bolj podrobno:

  • d[1][2] + 1 : iščemo minimalno število operacij, da iz niza “TO” dobimo niz “B” + 1(še ena operacija) = 2 + 1 = 3
  • d[2][1] + 1 : iščemo minimalno število operacij, da iz niza “T” dobimo “BO” + 1(še ena operacija) = 2 + 1 = 3
  • d[1][1] + r : iščemo minimalno število operacij, da iz niza “T” dobimo niz “B” + 0 (ker je znak O enak znaku O) = 1 + 0 = 1

Minimum teh treh izračunov (3, 3, 1) nam da dolžino 1.


Dolžina med nizoma “TOR” in “BO”: pove nam, koliko operacij potrebujemo, da iz “TOR” dobimo “BO”: d[2][3] = minimum (d[1][3] + 1, d[2][2] + 1, d[1][2] + r) = 2

Dolžina med nizoma “TORB” in “BO”: pove nam, koliko operacij potrebujemo, da iz “TORB” dobimo “BO”: d[2][4] = minimum (d[1][4] + 1, d[2][3] + 1, d[1][3] + r) = 3

Dolžina med nizoma “TORBA” in “BO”: pove nam, koliko operacij potrebujemo, da iz “TORBA” dobimo “BO”: d[2][5] = minimum (d[1][5] + 1, d[2][4] + 1, d[1][4] + r) = 4


Izračunane dolžine vstavimo v tretji stolpec matrike:

b o r b a
0 1 2 3 4 5
t 1 1 2
o 2 2 1
r 3 3 2
b 4 3 3
a 5 4 4


  • i = 3:

d[3][0] = 3 (že imamo)

Dolžina med nizoma “T” in “BOR”: pove nam, koliko operacij potrebujemo, da iz “T” dobimo “BOR”: d[3][1] = minimum (d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + r) = minimum (d[2][1] + 1, d[3][0] + 1, d[2][0] + r) = minimum (3, 4, 3) = 3

Dolžina med nizoma “TO” in “BOR”: pove nam, koliko operacij potrebujemo, da iz “TO” dobimo “BOR”: d[3][2] = minimum (d[2][2] + 1, d[3][1] + 1, d[2][1] + r) = 2

Dolžina med nizoma “TOR” in “BOR”: pove nam, koliko operacij potrebujemo, da iz “TOR” dobimo “BOR”: d[3][3] = minimum (d[2][3] + 1, d[3][2] + 1, d[2][2] + r) = 1

Dolžina med nizoma “TORB” in “BOR”: pove nam, koliko operacij potrebujemo, da iz “TORB” dobimo “BOR”: d[3][4] = minimum (d[2][4] + 1, d[3][3] + 1, d[2][3] + r) = 2

Dolžina med nizoma “TORBA” in “BOR”: pove nam, koliko operacij potrebujemo, da iz “TORBA” dobimo “BOR”: d[3][5] = minimum (d[2][5] + 1, d[3][4] + 1, d[2][4] + r) = 3


Izračunane dolžine vstavimo v četrti stolpec matrike:

b o r b a
0 1 2 3 4 5
t 1 1 2 3
o 2 2 1 2
r 3 3 2 1
b 4 3 3 2
a 5 4 4 3


  • i = 4:

d[4][0] = 4 (že imamo)

Dolžina med nizoma “T” in “BORB”: pove nam, koliko operacij potrebujemo, da iz “T” dobimo “BORB”: d[4][1] = minimum (d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + r) = minimum (d[3][1] + 1, d[4][0] + 1, d[3][0] + r) = minimum (4, 5, 4) = 4

Dolžina med nizoma “TO” in “BORB”: pove nam, koliko operacij potrebujemo, da iz “TO” dobimo “BORB”: d[4][2] = minimum (d[3][2] + 1, d[4][1] + 1, d[3][1] + r) = 3
Oglejmo si ta izračun bolj podrobno:

  • d[3][2] + 1 : iščemo minimalno število operacij, da iz niza “TO” dobimo niz “BOR” + 1(še ena operacija) = 2 + 1 = 3
  • d[4][1] + 1 : iščemo minimalno število operacij, da iz niza “T” dobimo niz “BORB” + 1(še ena operacija) = 3 + 1 = 4
  • d[3][1] + r : iščemo minimalno število operacij, da iz niza “T” dobimo niz “BOR” + 1 (ker znak O ni enak znaku B) = 3 + 1 = 4

Minimum teh treh izračunov (3, 4, 4) nam da dolžino 3.


Dolžina med nizoma “TOR” in “BORB”: pove nam, koliko operacij potrebujemo, da iz “TOR” dobimo “BORB”: d[4][3] = minimum (d[3][3] + 1, d[4][2] + 1, d[3][2] + r) = 2

Dolžina med nizoma “TORB” in “BORB”: pove nam, koliko operacij potrebujemo, da iz “TORB” dobimo “BORB”: d[4][4] = minimum (d[3][4] + 1, d[4][3] + 1, d[3][3] + r) = 1

Dolžina med nizoma “TORBA” in “BORB”: pove nam, koliko operacij potrebujemo, da iz “TORBA” dobimo “BORB”: d[4][5] = minimum (d[3][5] + 1, d[4][4] + 1, d[3][4] + r) = 2


Izračunane dolžine vstavimo v peti stolpec matrike:

b o r b a
0 1 2 3 4 5
t 1 1 2 3 4
o 2 2 1 2 3
r 3 3 2 1 2
b 4 3 3 2 1
a 5 4 4 3 2


  • i = 5:

d[5][0] = 5 (že imamo)

Dolžina med nizoma “T” in “BORBA”: pove nam, koliko operacij potrebujemo, da iz “T” dobimo “BORBA”: d[5][1] = minimum (d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + r) = minimum (d[4][1] + 1, d[5][0] + 1, d[4][0] + r) = minimum (5, 6, 5) = 5

Dolžina med nizoma “TO” in “BORBA”: pove nam, koliko operacij potrebujemo, da iz “TO” dobimo “BORBA”: d[5][2] = minimum (d[4][2] + 1, d[5][1] + 1, d[4][1] + r) = 4

Dolžina med nizoma “TOR” in “BORBA”: pove nam, koliko operacij potrebujemo, da iz “TOR” dobimo “BORBA”: d[5][3] = minimum (d[4][3] + 1, d[5][2] + 1, d[4][2] + r) = 3

Dolžina med nizoma “TORB” in “BORBA”: pove nam, koliko operacij potrebujemo, da iz “TORB” dobimo “BORBA”: d[5][4] = minimum (d[4][4] + 1, d[5][3] + 1, d[4][3] + r) = 2

REZULTAT: Dolžina med nizoma “TORBA” in “BORBA”: pove nam, koliko operacij potrebujemo, da iz “TORBA” dobimo “BORBA”: d[5][5] = minimum (d[4][5] + 1, d[5][4] + 1, d[4][4] + r) = 1


Izračunane dolžine vstavimo v šesti stolpec matrike.

Končni rezultat:

b o r b a
0 1 2 3 4 5
t 1 1 2 3 4 5
o 2 2 1 2 3 4
r 3 3 2 1 2 3
b 4 3 3 2 1 2
a 5 4 4 3 2 1

Rešitev je številka, ki je v skrajnem desnem spodnjem kotu tabele; torej 1.
Minimalno število operacij, ki jih potrbujemo, da niz "torba" spremenimo v niz "borba", je 1.

V tem primeru zamenjamo črko "t" nadomestimo s črko "b".

Osebna orodja