Levenshteinova razdalja/Se en primer algoritma

Iz MaFiRaWiki

1. Imamo niza "Mojca" in "Miha". Med njima želimo izračunati razdaljo, kar pomeni, da želimo izračunati minimalno število operacij, ki so potrebne za to, da niz "Mojca" spremenimo v niz "Miha".

M i h a
0 1 2 3 4
M 1 0 1 2 3
o 2 1 1 2 3
j 3 2 2 2 3
c 4 3 3 3 3
a 5 4 4 4 3


Razlaga: V prvo vrstico in v prvi stolpec matrike smo že napisali njene elemente.

Definicija Levenshteinove razdalje pravi: d(i, j) = min(d(i-1, j) + 1, d(i, j-1) + 1, d(i-1, j-1) + r(s(i), t(j))). Če s(i) = t(j), potem je r(s(i), t(j)) = 0, drugače pa 1.

Poglejmo, kaj se dogaja, ko indeks i teče od 1 do konca drugega niza("Miha"):

  • i = 1:
    • d[1][0] = 1 (že imamo)
    • d[1][1] = min(d(i-1, j) + 1, d(i, j-1) + 1, d(i-1, j-1) + r(s(i), t(j))) = min(d[0][1] + 1, d[1][0] + 1, d[0][0] + 0) = min(2, 2, 0) = 0
      V našem primeru je r(s(i), t(j)) = 0, ker je M = M.
    • d[1][2] = min(d[0][2] + 1, d[1][1] + 1, d[0][1] + 1) = min(3, 1, 2) = 1
    • d[1][3] = min(d[0][3] + 1, d[1][2] + 1, d[0][2] + 1) = min(4, 2, 3) = 2
    • d[1][4] = min(d[0][4] + 1, d[1][3] + 1, d[0][3] + 1) = min(5, 3, 4) = 3
    • d[1][5] = min(d[0][5] + 1, d[1][4] + 1, d[0][4] + 1) = min(6, 4, 5) = 4


  • i = 2:
    • d[2][0] = 2 (že imamo)
    • d[2][1] = min(d(i-1, j) + 1, d(i, j-1) + 1, d(i-1, j-1) + r(s(i), t(j))) = min(d[1][1] + 1, d[2][0] + 1, d[1][0] + 1) = min(1, 3, 2) = 1
    • d[2][2] = min(d[1][2] + 1, d[2][1] + 1, d[1][1] + 1) = min(2, 2, 1) = 1
    • d[2][3] = min(d[1][3] + 1, d[2][2] + 1, d[1][2] + 1) = min(3, 2, 2) = 2
    • d[2][4] = min(d[1][4] + 1, d[2][3] + 1, d[1][3] + 1) = min(4, 3, 3) = 3
    • d[2][5] = min(d[1][5] + 1, d[2][4] + 1, d[1][4] + 1) = min(5, 4, 4) = 4


  • i = 3:
    • d[3][0] = 3 (že imamo)
    • d[3][1] = min(d(i-1, j) + 1, d(i, j-1) + 1, d(i-1, j-1) + r(s(i), t(j))) = min(d[2][1] + 1, d[3][0] + 1, d[2][0] + 1) = min(2, 4, 3) = 2
    • d[3][2] = min(d[2][2] + 1, d[3][1] + 1, d[2][1] + 1) = min(2, 3, 2) = 2
    • d[3][3] = min(d[2][3] + 1, d[3][2] + 1, d[2][2] + 1) = min(3, 3, 2) = 2
    • d[3][4] = min(d[2][4] + 1, d[3][3] + 1, d[2][3] + 1) = min(4, 3, 3) = 3
    • d[3][5] = min(d[2][5] + 1, d[3][4] + 1, d[2][4] + 1) = min(5, 4, 4) = 4


  • i = 4:
    • d[4][0] = 4 (že imamo)
    • d[4][1] = min(d(i-1, j) + 1, d(i, j-1) + 1, d(i-1, j-1) + r(s(i), t(j))) = min(d[3][1] + 1, d[4][0] + 1, d[3][0] + 1) = min(3, 5, 4) = 3
    • d[4][2] = min(d[3][2] + 1, d[4][1] + 1, d[3][1] + 1) = min(3, 4, 3) = 3
    • d[4][3] = min(d[3][3] + 1, d[4][2] + 1, d[3][2] + 1) = min(3, 4, 3) = 3
    • d[4][4] = min(d[3][4] + 1, d[4][3] + 1, d[3][3] + 1) = min(4, 4, 3) = 3
    • d[4][5] = min(d[3][5] + 1, d[4][4] + 1, d[3][4] + 0) = min(5, 4, 3) = 3


Razdalja med nizoma(oz. minimalno število operacij, da niz "Mojca" preoblikujemo v niz "Miha") je 3.


Iz "Mojca" lahko dobimo "Miha" (s tremi operacijami) na več načinov:


POTI:
Ko izračunamo vse razdalje med znaki nizov in razdaljo med nizoma, lahko iz matrike razberemo tudi na kakšen način smo prišli do te razdalje (koliko je bilo npr. potrebnih brisanj, substitucij ali vstavljanj);

Torej, od desne spodnje številke matrike (rezultata) se vračamo proti začetku, in sicer tako, da med njenim levim sosedom, diagonalno levo in zgornjo številko poiščemo minimum. Tako dobimo neko pot ali več poti, ki nam povejo na koliko načinov lahko najdemo razdaljo med nizoma.

Naj bo element d[i][j] minimalno število operacij, ki jih potrebujemo, da iz i znakov prvega niza dobimo j znakov drugega niza:

element nad njim + 1: d[i-1][j] + 1. //izbris
njegov levi sosed + 1: d[i][j-1] + 1. // vstavek 
diagonalni element - levo- nad njim + r: d[i-1][j-1] + r. // substitucija

Naš primer:

  • 1. pot:

d[4][5] = 3 --> d[3][4] = 3 (diagonalni element – levo - nad d[4][5] --> do elementa d[4][5] smo prišli s substitucijo) --> d[3][3] = 2 (element nad d[3][4] --> do elementa d[3][4] smo prišli z izbrisom) --> d[2][2] = 1 (diagonalni element - levo- nad d[3][3] --> substitucija) --> d[1][1] = 0 (diagonalni element - levo- nad d[2][2] --> substitucija) --> d[0][0] = 0 (diagonalni element - levo- nad d[1][1] --> substitucija)

  • 2. pot:

d[4][5] = 3 --> d[3][4] = 3 (diagonalni element – levo - nad d[4][5] --> do elementa d[4][5]smo prišli s substitucijo) --> d[2][3] = 2 (diagonalni element – levo - nad d[3][4] --> do elementa d[3][4] smo prišli s substitucijo) --> d[2][2] = 1 (element nad d[2][3] --> do d[2][2] smo prišli z izbrisom) --> d[1][1] = 0 (diagonalni element - levo- nad d[2][2] --> substitucija) --> d[0][0] = 0 (diagonalni element - levo- nad d[1][1] --> substitucija)

  • 3. pot:

d[4][5] = 3 --> d[3][4] = 3 (diagonalni element – levo - nad d[4][5] --> do elementa d[4][5] smo prišli s substitucijo) --> d[2][3] = 2 (diagonalni element – levo - nad d[3][4] --> do elementa d[3][4] smo prišli s substitucijo) --> d[1][2] = 1 (diagonalni element – levo – nad d[2][3] --> do d[1][2] smo prišli s substitucijo) --> d[1][1] = 0 (element nad d[1][2] --> do d[1][2] smo prišli z izbrisom) --> d[0][0] = 0 (diagonalni element - levo- nad d[1][1] --> do d[1][1] smo prišli s substitucijo)


Npr:

  • Črko "o" iz "Mojca" nadomestimo s črko "i" iz "Miha".(substitucija ) --> Mijca

Črko "j" iz "Mijca" nadomestimo s črko "h" iz "Miha".(substitucija ) --> Mihca
Črko "c" iz "Mihca" izbrišemo.(izbris)--> Miha

substitucija + substitucija + izbris = 3 operacije


  • Črko "o" iz "Mojca" izbrišemo.(izbris) --> Mjca

Črko "j" iz "Mjca" nadomestimo s črko "i" iz "Miha".(substitucija ) --> Mica
Črko "c" iz "Mica" nadomestimo s črko "h" iz "Miha".(substitucija ) --> Miha

izbris + substitucija + substitucija = 3 operacije


  • Črko "o" iz "Mojca" nadomestimo s črko "i" iz "Miha".(substitucija ) --> Mijca

Črko "j" iz "Mijca" izbrišemo.(izbris) --> Mica
Črko "c" iz "Mica" nadomestimo s črko "h" iz "Miha".(substitucija ) --> Miha

substitucija + izbris + substitucija = 3 operacije

...


2. Imamo niza "ABC D" in "ABV". Med njima želimo izračunati razdaljo.

A B V
0 1 2 3
A 1 0 1 2
B 2 1 0 1
C 3 2 1 1
4 3 2 2
D 5 4 3 3


Poglejmo, kako napolnimo matriko:

    • d[1][0] = 1 (že imamo)
    • d[1][1] = min(d[0][1] + 1, d[1][0] + 1, d[0][0] + 0) = min(2, 2, 0) = 0
      V našem primeru je r(s(i), t(j)) = 0, ker je A = A.
    • d[1][2] = min(d[0][2] + 1, d[1][1] + 1, d[0][1] + 1) = min(3, 1, 2) = 1
    • d[1][3] = min(d[0][3] + 1, d[1][2] + 1, d[0][2] + 1) = min(4, 2, 3) = 2
    • d[1][4] = min(d[0][4] + 1, d[1][3] + 1, d[0][3] + 1) = min(5, 3, 4) = 3
    • d[1][5] = min(d[0][5] + 1, d[1][4] + 1, d[0][4] + 1) = min(6, 4, 5) = 4


  • i = 2:
    • d[2][0] = 2 (že imamo)
    • d[2][1] = min(d[1][1] + 1, d[2][0] + 1, d[1][0] + 1) = min(1, 3, 2) = 1
    • d[2][2] = min(d[1][2] + 1, d[2][1] + 1, d[1][1] + 0) = min(2, 2, 0) = 0
    • d[2][3] = min(d[1][3] + 1, d[2][2] + 1, d[1][2] + 1) = min(3, 1, 2) = 1
    • d[2][4] = min(d[1][4] + 1, d[2][3] + 1, d[1][3] + 1) = min(4, 2, 3) = 2
    • d[2][5] = min(d[1][5] + 1, d[2][4] + 1, d[1][4] + 1) = min(5, 3, 4) = 3


  • i = 3:
    • d[3][0] = 3 (že imamo)
    • d[3][1] = min(d[2][1] + 1, d[3][0] + 1, d[2][0] + 1) = min(2, 4, 3) = 2
    • d[3][2] = min(d[2][2] + 1, d[3][1] + 1, d[2][1] + 1) = min(1, 3, 2) = 1
    • d[3][3] = min(d[2][3] + 1, d[3][2] + 1, d[2][2] + 1) = min(2, 2, 1) = 1
    • d[3][4] = min(d[2][4] + 1, d[3][3] + 1, d[2][3] + 1) = min(3, 4, 1) = 2
    • d[3][5] = min(d[2][5] + 1, d[3][4] + 1, d[2][4] + 1) = min(4, 3, 3) = 3


Razdalja med nizoma(oz. minimalno število operacij, da niz "ABC D" preoblikujemo v niz "ABV") je 3. Če imamo niz s presledkom, potem presledek štejemo kot enega izmed elementov niza.



3. Imamo niza "ABC D" in "AB V". Med njima želimo izračunati razdaljo.

A B V
0 1 2 3 4
A 1 0 1 2 3
B 2 1 0 1 2
C 3 2 1 1 2
4 3 2 1 2
D 5 4 3 2 2


Poglejmo, kako napolnimo matriko:

    • d[1][0] = 1 (že imamo)
    • d[1][1] = min(d[0][1] + 1, d[1][0] + 1, d[0][0] + 0) = min(2, 2, 0) = 0
      V našem primeru je r(s(i), t(j)) = 0, ker je A = A.
    • d[1][2] = min(d[0][2] + 1, d[1][1] + 1, d[0][1] + 1) = min(3, 1, 2) = 1
    • d[1][3] = min(d[0][3] + 1, d[1][2] + 1, d[0][2] + 1) = min(4, 2, 3) = 2
    • d[1][4] = min(d[0][4] + 1, d[1][3] + 1, d[0][3] + 1) = min(5, 3, 4) = 3
    • d[1][5] = min(d[0][5] + 1, d[1][4] + 1, d[0][4] + 1) = min(6, 4, 5) = 4


  • i = 2:
    • d[2][0] = 2 (že imamo)
    • d[2][1] = min(d[1][1] + 1, d[2][0] + 1, d[1][0] + 1) = min(1, 3, 2) = 1
    • d[2][2] = min(d[1][2] + 1, d[2][1] + 1, d[1][1] + 0) = min(2, 2, 0) = 0
    • d[2][3] = min(d[1][3] + 1, d[2][2] + 1, d[1][2] + 1) = min(3, 1, 2) = 1
    • d[2][4] = min(d[1][4] + 1, d[2][3] + 1, d[1][3] + 1) = min(4, 2, 3) = 2
    • d[2][5] = min(d[1][5] + 1, d[2][4] + 1, d[1][4] + 1) = min(5, 3, 4) = 3


  • i = 3:
    • d[3][0] = 3 (že imamo)
    • d[3][1] = min(d[2][1] + 1, d[3][0] + 1, d[2][0] + 1) = min(2, 4, 3) = 2
    • d[3][2] = min(d[2][2] + 1, d[3][1] + 1, d[2][1] + 1) = min(1, 3, 2) = 1
    • d[3][3] = min(d[2][3] + 1, d[3][2] + 1, d[2][2] + 1) = min(2, 2, 1) = 1
    • d[3][4] = min(d[2][4] + 1, d[3][3] + 1, d[2][3] + 0) = min(3, 2, 1) = 1
    • d[3][5] = min(d[2][5] + 1, d[3][4] + 1, d[2][4] + 1) = min(4, 2, 3) = 2


  • i = 4:
    • d[4][0] = 4 (že imamo)
    • d[4][1] = min(d[3][1] + 1, d[4][0] + 1, d[3][0] + 1) = min(3, 5, 4) = 3
    • d[4][2] = min(d[3][2] + 1, d[4][1] + 1, d[3][1] + 1) = min(2, 4, 3) = 2
    • d[4][3] = min(d[3][3] + 1, d[4][2] + 1, d[3][2] + 1) = min(2, 3, 2) = 2
    • d[4][4] = min(d[3][4] + 1, d[4][3] + 1, d[3][3] + 1) = min(2, 3, 2) = 2
    • d[4][5] = min(d[3][5] + 1, d[4][4] + 1, d[3][4] + 1) = min(3, 3, 2) = 2


Razdalja med nizoma(oz. minimalno število operacij, da niz "ABC D" preoblikujemo v niz "AB V") je 2.

Osebna orodja