  ̌      ̌   
P 49 (2021/2022) 5 25
Razdalje urejanja 1. del
H        L                   
M B̌, J D
V sistemih procesiranja naravnega jezika, ki se
ukvarjajo z obdelavo jezika v obliki besedila, se
večinoma ukvarjamo z analizo besedil. Besedila
praviloma najprej pošljemo skozi cevovod predob-
delave besedil, kjer kot rezultat dobimo značilke,
ki jih lahko uporabimo v nadaljnjih korakih obde-
lave.
Določena opravila na področju procesiranja narav-
nega jezika zahtevajo primerjave med različnimi be-
sedili. Dober primer tega sta preverjanje črkovanja
in implementacija iskalnikov. Pri preverjanju črko-
vanja s primerjavo dveh besed iščemo napake v vho-
dnem besedilu, pri implementaciji iskalnikov pa
iščemo tista besedila, ki so najbolj podobna vhodne-
mu iskalnemu vnosu. Pri izvajanju primerjave med
besedili se lahko poslužujemo razdalj urejanja (angl.
edit distances), znane tudi kot urejevalne razdalje, ki
na vhodu ponavadi prejmejo dva niza, na izhodu pa
vrnejo število, ki pomeni razliko med njima.
V tem prispevku bomo na primerih podrobneje
predstavili delovanje Hammingove razdalje [1], ki
spada med preprostejše razdalje urejanja, in Leven-
shteinove razdalje [3], ki je predstavnik bolj dovrše-
nih razdalj urejanja. Pogledali si bomo tudi nekatere
omejitve, ki nastopajo ob uporabi omenjenih razdalj
urejanja. Ker obstaja kar nekaj različnih razdalj ure-
janja, bomo nekatere druge podrobneje predstavili v
naslednjem delu prispevka.
Razdalje urejanja so za določene naloge v pro-
cesiranju naravnega jezika ključnega pomena, zato
se uporabljajo kot prvi korak obdelave besedila po
predobdelavi. Da bi bolje razumeli uporabo razdalj
urejanja določenih nalog procesiranja naravnega je-
zika, si najprej preglejmo področje razdalj urejanja
in določene definicije operacij, ki se pojavljajo v iz-
računih takšnih razdalj.
Razdalje urejanja
Vsaka razdalja urejanja je lahko formalno definirana
na vhodnih nizih a in b ter na abecedi Σ, ki pred-
stavlja nabor znakov, ki se lahko pojavijo v nizih a
in b. Razdalja urejanja d(a,b) je po definiciji naj-
manjše število operacij, ki jih potrebujemo, da iz
enega niza dobimo drugega [4]. Operacije, ki jih pri
tem lahko uporabimo so vstavljanje znaka (ang. in-
sertion), brisanje znaka (ang. deletion) in zamenjava
znaka (ang. substitution). Dodatno poznamo še po-
sebno obliko zamenjave znaka, transpozicijo (ang.
transposition), kjer se zamenjata dva poljubna znaka
v nizu, vsi ostali pa ostanejo nespremenjeni. Raz-
lika med tema dvema tipoma zamenjave je, da smo
s transpozicijo omejeni na zamenjavo znakov, ki so
v nizu, pri navadni zamenjavi pa lahko znak zame-
njamo s poljubnim znakom, tudi takšnim, ki se ne
pojavi v nizu.
Obstaja več tipov razdalj urejanja, ki dovoljujejo
različne nabore operacij. Hammingova razdalja do-
voljuje samo zamenjavo znakov, medtem ko Leven-
shteinova razdalja dovoljuje vstavljanje, brisanje in
zamenjavo znakov. Njena različica, imenovana Da-
merau-Levenshteinova razdalja, ob vseh že omenje-
  ̌      ̌   
P 49 (2021/2022) 526
nih operacijah dovoljuje še transpozicijo znakov. Na
koncu lahko omenimo še Jarovo in Jaro-Winklerjevo
razdaljo, ki dovoljujeta samo transpozicijo znakov.
Predmet tega prispevka sta Hammingova in Leven-
shteinova razdalja, zato si podrobneje poglejmo
njuno delovanje na primerih.
Hammingova razdalja
Hammingova razdalja, poimenovana po ameriškem
matematiku Richardu Hammingu, je najpreprostejša
razdalja urejanja. Ta razdalja urejanja dovoljuje sa-
mo zamenjavo znakov, kar pomeni, da lahko deluje
samo nad dvema nizoma iste velikosti. To je tudi
njena glavna slabost, saj vemo, da so besede v ka-
teremkoli naravnem jeziku lahko različnih velikosti.
Kljub tej slabosti pa je ta razdalja zelo pomembna
v teoriji kodiranja, predvsem na področjih stiskanja
podatkov, kriptografije, zaznavanja in popravljanja
napak ter pri uporabi na kvantnih računalnikih [2].
Na področju procesiranja naravnega jezika se ta raz-
dalja sicer v praksi redko uporablja, vendar predsta-
vlja odlično osnovo za razlago vseh ostalih v praksi
bolj uporabljenih razdalj urejanja.
Delovanje Hammingove razdalje za primerjavo
dveh enako dolgih nizov znakov oziroma besed je
izjemno preprosto. Niza poravnamo po znakih, nato
pa primerjamo istoležna znaka med seboj. Če sta
znaka enaka, je utež enaka 0, sicer pa 1. Hammin-
govo razdaljo lahko tako definiramo tudi z uporabo
logične funkcije ekskluzivni ali oziroma XOR. Zapisa
ham(a, b) in a
⊕
b sta torej ekvivalentna, vendar se
prvi pogosteje uporablja na področju procesiranja
naravnega jezika, drugi pa na področju teorije ko-
diranja. Na koncu seštejemo vse uteži in rezultat je
vrednost, ki predstavlja razdaljo med nizoma a in b.
V spodnjem zgledu si poglejmo delovanje Hammin-
gove razdalje nad različnimi vhodnimi nizi.
Zgled
Imejmo vhodna niza a = rezultat in b = konzulat.
Kot vidimo, sta niza a in b enake dolžine (|a| = |b| =
8), saj sicer ne moremo izračunati Hammingove raz-
dalje. Niza smo po znakih istoležno zapisali v tabelo.
Ujemajoči znaki so označeni z modro barvo, uteži
neujemanja (1) so označene z rdečo barvo, uteži uje-
manja (0) pa z zeleno barvo (slika 1).
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
ham(a,b) 1 1 1 1 1 1 0 0 = 6
b k o n z u l a t
a r e z u l t a t
SLIKA 1.
Primer izračuna Hammingove razdalje za vhodna niza
a = rezultat in b = konzulat
Izračun razdalje začnemo s primerjavo prvega
znaka v obeh nizih. V našem primeru sta to znaka
»r« in »k«, ki nista enaka, zato je utež enaka 1. Nato
nadaljujemo z drugim znakom v obeh nizih. To sta
znaka »e« in »o«, ki znova nista enaka in zato je utež
znova enaka 1. Podobno nadaljujemo vse do sed-
mega znaka v obeh nizih, kjer ugotovimo ujemanje
v znaku »a«. Utež je tukaj enaka 0. Enako se zgodi
pri osmem znaku v obeh nizih, kjer se niza ujemata v
znaku »t«. Po prehodu smo ugotovili, da imamo med
nizoma a in b šest neujemanj in dve ujemanji. Sledi
še samo zadnji korak izračuna razdalje, ki je sešte-
vek vseh uteži. Razdalja med nizoma ham(a, b) je
torej enaka 6, kar pomeni, da sta niza različna.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
ham(a,b) 0 0 0 0 0 0 0 0 = 0
b r e z u l t a t
a r e z u l t a t
SLIKA 2.
Primer izračuna Hammingove razdalje za vhodna niza
a = rezultat in b = rezultat
Če primerjamo dva enaka niza, lahko hitro ugoto-
vimo, da je Hammingova razdalja enaka 0. Takšno
situacijo lahko vidimo na sliki 2, kjer smo uporabili
vhodna niza a = rezultat in b = rezultat. Na sliki
3, kjer smo uporabili vhodna niza a = rezultat in
b = galerija, lahko vidimo, da je Hammingova razda-
lja enaka dolžini niza a ali b. To pomeni, da sta niza
a in b povsem različna.
S Hammingovo razdaljo lahko ugotavljamo podo-
bnosti med nizi iste velikosti, kar pa zelo omeji smi-
selnost njene uporabe pri naravnem jeziku,
kjer so besede različnih velikosti. Hammingova raz-
dalja v tem primeru ni primerna, saj ne dovoljuje
vstavljanja ali brisanja znakov. Zaradi tega potrebu-
  ̌      ̌   
P 49 (2021/2022) 5 27
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
ham(a,b) 1 1 1 1 1 1 1 1 = 8
b g a l e r i j a
a r e z u l t a t
SLIKA 3.
Primer izračuna Hammingove razdalje za vhodna niza
a = rezultat in b = galerija
jemo razdaljo urejanja, ki bo pri izračunu razdalje
dovoljevala tudi ti dve operaciji in nam s tem omogo-
čila primerjavo nizov različnih velikosti. Ena najbolj
uporabljenih razdalj urejanja s takšno lastnostjo je
Levenshteinova razdalja, ki jo bomo opisali v nada-
ljevanju.
Levenshteinova razdalja
Začetki ideje o razdalji med nizi različnih velikosti,
ki upošteva operacije vstavljanja, brisanja in zame-
njave znakov, segajo v leto 1965, ko je sovjetski ma-
tematik Vladimir Levenshtein predstavil novo razda-
ljo, imenovano Levenshteinova razdalja. Ta je zaradi
upoštevanja večjega nabora operacij hitro postala ti-
sta razdalja, ki se je začela uporabljati tudi v praksi.
Na področju procesiranja naravnega jezika se ta raz-
dalja pogosto uporablja v implementacijah popra-
vljanja pravopisa, saj lahko z njo določimo napake v
črkovanju in jih glede na vsebino besedila tudi ustre-
zno zamenjamo s pravilno črkovanimi besedami.
Levenshteinova razdalja ima nekaj zanimivih ma-
tematičnih lastnosti:
Spodnjo mejo vrednosti razdalje predstavlja abso-
lutna razlika velikosti dveh primerjanih nizov.
Zgornjo mejo vrednosti razdalje predstavlja veli-
kost daljšega izmed obeh primerjalnih nizov.
Vrednost razdalje bo enaka 0 takrat, ko sta oba
niza enaka.
Če sta niza enakih velikosti, bo vrednost Hammin-
gove razdalje tudi zgornja meja vrednosti Leven-
shteinove razdalje.
Za Levenshteinovo razdaljo velja tudi trikotniška
neenakost, in sicer Levenshteinova razdalja med
dvema nizoma ne bo nikoli večja od vsote njunih
vrednosti Levenshteinovih razdalj v primerjavi s
tretjim nizom.
Primeri za te matematične lastnosti so podani v
kodi na javno dostopnem repozitoriju GitHub [5].
Izračun Levenshteinove razdalje lahko implemen-
tiramo rekurzivno ali iterativno. Rekurzivni način je
zelo naiven in neučinkovit, saj v tem primeru več-
krat računamo vrednost Levenshteinove razdalje pri
istih podnizih. Zaradi tega se bomo v tem prispevku
osredotočili na iterativni način izračuna Levenshtei-
nove razdalje, ki je bistveno bolj učinkovit in se prav
tako uporablja v praktičnih implementacijah. V ite-
rativnem načinu izračuna uporabimo pristop dina-
mičnega programiranja, kjer uteži za vsako opera-
cijo nad nizi shranimo v pomožno matriko. V tem
prispevku bomo privzeli, da je uporaba vseh ope-
racij enakovredna, torej bo uporaba vseh operacij
ovrednotena z utežjo 1. Vrednost te uteži lahko po
želji tudi spremenimo, če želimo dodatno obtežiti
uporabo katere od operacij. Iterativni način imple-
mentacije, ki si ga bomo pogledali na zgledu, je si-
cer zelo podoben postopku, ki se uporablja v algo-
ritmih za poravnavo sekvenc DNK, kot so algoritmi
Needleman-Wunsch, Wagner-Fischer ali Smith-
Waterman.
Zgled
Imejmo dva vhodna niza a = telefon in b = lepota.
Vidimo, da sta niza različnih dolžin (|a| = 7, |b| = 6).
V primeru bomo uporabili iterativni način izračuna
Levenshteinove razdalje. Z algoritmom za izračun
Levenshteinove razdalje bomo želeli ugotoviti sku-
pno število operacij, ki jih potrebujemo, da niz a
spremenimo v niz b. Najprej pripravimo pomožno
matriko, kamor bomo shranjevali vmesne vrednosti
Levenshteinove razdalje. Niz a po črkah razpore-
dimo v prvi stolpec, niz b pa po črkah razporedimo
v prvo vrstico. Pri tem vsako črko opremimo s šte-
vilom, ki predstavlja indeks in se začne z 1. Po tem
koraku dobimo matriko prikazano na sliki 4 levo.
Izračun Levenshteinove razdalje nadaljujemo s
prehodom skozi vsak element pomožne matrike in
izračunom vrednosti vseh praznih elementov. To
storimo z operatorjem, ki obsega 4 elemente in ga
predstavimo kot matriko velikosti 2 × 2. Spodnji
desni element operatorja poravnamo s praznim ele-
mentom pomožne matrike, ki ga želimo izračunati.
Vidimo, da operator prekriva vrednosti pomožne
matrike, ki jih bomo uporabili za izračun praznega
  ̌      ̌   
P 49 (2021/2022) 528
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
n 7
o 6
f 5
e 4
l 3
e 2
t 1
0 1 2 3 4 5 6
l e p o t a
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
n 7
o 6
f 5
e 4
l 3
e 2
t 1 1
0 1 2 3 4 5 6
l e p o t a
SLIKA 4.
Levo: Inicializacija pomožne matrike za niza a = telefon in
b = lepota. Desno: Prekrivanje operatorja in prvi izračun
praznega elementa v pomožni matriki.
elementa pomožne matrike. To prikazuje slika 4 de-
sno, kjer smo operator poravnali tako, da primer-
jamo prvi črki obeh nizov. To sta črki »t« in »l«,
ki sta označeni s svetlo sivo barvo. Z modro barvo
so označene vrednosti v pomožni matriki, ki jih pre-
kriva operator. Z zeleno barvo je označen prazen
element, katerega vrednost želimo izračunati. Sledi
izračun vrednosti praznega elementa pomožne ma-
trike. Če se črki, ki ju primerjamo, razlikujeta, potem
poiščemo minimalno vrednost elementov, ki jih pre-
kriva operator, in prištejemo utež. Utež pove za ko-
likšno vrednost kaznujemo razlikovanje zaradi do-
dajanja, brisanja ali zamenjave znaka v primeru ne-
ujemanja. Ker smo se odločili, da bomo vse opera-
cije tretirali kot enakovredne, bo utež v našem pri-
meru vedno enaka 1. Na sliki 4 desno vidimo, da
smo za prazen element pomožne matrike (označen
z zeleno barvo) na prej opisan način dobili vrednost
1. Izbirali smo minimalno vrednost med tremi pre-
kritimi vrednostmi pomožne matrike (označenimi z
modro barvo) in sedaj vidimo, da je minimalna vre-
dnost enaka 0. Tej vrednosti prištejemo utež, ki je
enaka 1, in s tem dobimo končno vrednost elementa,
ki je enaka 1. Slika 5 levo prikazuje nadaljevanje iz-
računa, kjer primerjamo črki »t« in »e«, na sliki 5
desno pa vidimo izračunano celotno prvo vrstico po-
možne matrike, kjer smo med izračuni naleteli na
ujemanje v črki »t«.
Če se črki, ki ju primerjamo, ujemata, potem je
vrednost praznega elementa pomožne matrike ena-
ka vrednosti elementa pomožne matrike, ki se na-
haja levo diagonalno od praznega elementa pomo-
žne matrike. To pomeni, da prevzamemo doseda-
njo vrednost razdalje, saj smo naleteli na ujemanje.
Na sliki 5 desno vidimo, da smo za prazen element
pomožne matrike (označen z zeleno barvo) prevzeli
vrednost 4 iz elementa, ki je levo diagonalno od nje-
ga (označen z oranžno barvo).
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
n 7
o 6
f 5
e 4
l 3
e 2
t 1 1 2
0 1 2 3 4 5 6
l e p o t a
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
n 7
o 6
f 5
e 4
l 3
e 2
t 1 1 2 3 4 4 5
0 1 2 3 4 5 6
l e p o t a
SLIKA 5.
Nadaljevanje izračunov vrednosti praznih elementov v prvi vr-
stici pomožne matrike. Levo: Izračun vrednosti pri primerjavi
črk »t« in »e«. Desno: Izračun vrednosti pri ujemanju v črki »t«.
Postopek nadaljujemo tako dolgo, dokler ne iz-
računamo vseh vrednosti praznih elementov v po-
možni matriki. Končno stanje vrednosti pomožne
matrike prikazuje slika 6 levo. Ko izračunamo vse
vrednosti pomožne matrike, odčitamo spodnji desni
element pomožne matrike (označen z rdečo barvo).
Ta vrednost predstavlja Levenshteinovo razdaljo
med nizoma a in b, ki pove, da je za pretvorbo niza
a v b potrebnih pet operacij. Za nekatere naloge v
procesiranju naravnega jezika je ta vrednost že do-
volj, saj lahko definiramo metriko podobnosti. Naj
bo lev(a, b) Levenshteinova razdalja med nizoma a
in b. Levenshteinovo podobnost med nizoma a in b
označimo kot simlev(a, b) in definiramo z enačbo
simlev(a, b) =
|a| + |b| − lev(a, b)
|a| + |b| , (1)
kjer sta |a| in |b| dolžini nizov a in b. Vrednost
simlev(a, b) je na intervalu [0,1] in predstavlja po-
  ̌      ̌   
P 49 (2021/2022) 5 29
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
n 7 6 5 5 4 4 5
o 6 5 4 4 3 4 5
f 5 4 3 3 4 4 5
e 4 3 2 3 3 4 5
l 3 2 2 2 3 4 5
e 2 2 1 2 3 4 5
t 1 1 2 3 4 4 5
0 1 2 3 4 5 6
l e p o t a
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
n 7 6 5 5 4 4 5
o 6 5 4 4 3 4 5
f 5 4 3 3 4 4 5
e 4 3 2 3 3 4 5
l 3 2 2 2 3 4 5
e 2 2 1 2 3 4 5
t 1 1 2 3 4 4 5
0 1 2 3 4 5 6
l e p o t a
SLIKA 6.
Izračun vrednosti Levenshteinove razdalje s polno pomožno
matriko in ponazoritev poti z minimalnim številom operacij nad
nizi. Levo: Končno stanje vrednosti v pomožni matriki. De-
sno: Ena izmed možnih poti, ki ponazarja minimalno število
operacij.
dobnost med nizoma a in b. Za naš primer izraču-
namo vrednost 0,615, kar interpretiramo kot 61,5 %
podobnost med nizoma a in b.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
vstavljanje *
zamenjava brisanje
SLIKA 7.
Operator za ugotavljanje zaporedja uporabljenih operacij.
Znak * označuje pozicijo trenutnega elementa.
V primeru, da bi želeli vedeti, katere operacije so
bile potrebne za pretvorbo niza a = telefon v niz
b = lepota, moramo rekonstruirati zaporedje izve-
denih operacij. To lahko storimo tako, da začnemo v
skrajnem spodnjem desnem elementu pomožne ma-
trike in znova upoštevamo matrični operator veliko-
sti 2 × 2 (slika 7). Cilj je priti v zgornji levi element
matrike z vrednostjo 0. Tvorili bomo torej pot po
pomožni matriki, odvisno od premika pa bomo iz-
vedeli, katera operacija je bila izvedena v tistem ko-
raku. Pri tem bomo niz a spreminjali v smeri iz de-
sne proti levi.
Ob ujemanju znakov se premaknemo levo diago-
nalno in ne izvedemo nobene operacije, saj gre za
ujemanje. Ob neujemanju znakov bo premik v levo
pomenil operacijo vstavljanja, premik navzgor bo
pomenil operacijo brisanja, premik po levi diagonali
pa bo pomenil operacijo zamenjave. Premiki si ve-
dno sledijo v smeri elementa z nižjo vrednostjo od
vrednosti elementa, v katerem se nahajamo. Pri tem
upoštevamo znake iz nizov a in b, ki predstavljajo
glavo stolpcev in vrstic. Grafični potek ene takšne
poti prikazuje slika 6 desno, izvedbo zaporedja ope-
racij pa prikazuje slika 8.
Zaključek
V tem prispevku smo predstavili osnovne lastnosti
razdalj urejanja, ki jih lahko uporabimo na področju
procesiranja naravnega jezika. Podrobneje smo si
pogledali delovanje Hammingove in Levenshteinove
razdalje urejanja. S Hammingovo razdaljo smo spo-
znali delovanje operacije zamenjave, z Levenshtei-
novo razdaljo pa tudi operaciji vstavljanja in brisa-
nja. Primera implementacije Hammingove in Leven-
shteinove razdalje v programskem jeziku Python sta
na voljo na javno dostopnem repozitoriju GitHub [5].
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
8 brisanje črke »t« tlepota → lepota
7 brisanje črke »e« telepota → tlepota
6 ni operacije (ujemanje v črki »l«) telepota
5 ni operacije (ujemanje v črki »e«) telepota
4 zamenjava črke »f« s »p« telefota → telepota
3 ni operacije (ujemanje v črki »o«) telefota
2 vstavljanje črke »t« telefoa → telefota
1 zamenjava črke »n« z »a« telefon → telefoa
# Operacija Rezultat
SLIKA 8.
Izvedba zaporedja operacij ob spre-
membi niza a = telefon v niz
b = lepota
         
P 49 (2021/2022) 530
Čeprav operacije transpozicije v tem prispevku ni-
smo podrobneje obravnavali, je vredno omeniti, da
obstaja razširitev Levenshteinove razdalje, ki dovo-
ljuje tudi to operacijo. To je Damerau-Levenshteino-
va razdalja, ki se na področju procesiranja narav-
nega jezika pogosto uporablja za popravljanje črko-
vanja. Ker pa to ni edina zanimiva uporaba operacije
transpozicije, si bomo v drugem delu podrobneje po-
gledali dve razdalji urejanja, ki dovoljujeta izključno
to operacijo – to sta Jarova in Jaro-Winklerjeva raz-
dalja.
Literatura
[1] R. W. Hamming, Error detecting and error cor-
recting codes, The Bell System Technical Jour-
nal 29.2 (1950), 147–160. doi: 10.1002/j.1538-
7305.1950.tb00463.x.
[2] M. Khan in A. Miranskyy, String Comparison on
a Quantum Computer Using Hamming Distance,
arXiv: 2106.16173 [cs.ET], 2021.
[3] V. Iosifovich Levenshtein, Binary codes capable of
correcting deletions, insertions and reversals, So-
viet Physics Doklady 10.8 (1966), Doklady Aka-
demii Nauk SSSR, V163 No.4 845-848 1965, 707–
710.
[4] G. Navarro, A Guided Tour to Approxi-
mate String Matching, ACM Comput. Surv.
33.1 (2001), 31–88. ISSN: 0360-0300, doi:
10.1145/375360.375365, dostopno na
doi.org/10.1145/375360.375365, ogled
10. marca 2022.
[5] Procesiranje naravnega jezika – GitHub, do-
stopno na github.com/procesiranje-
naravnega-jezika/example-code/blob/
main/1b%5C%20-%5C%20Razdalje%5C%20ure-
janja%5C%201.%5C%20del%5C%20-%5C%20Ham-
mingova%5C%20in%5C%20Levenshteinova%5C-
%20razdalja, ogled 10. marca 2022.
×××
̌

̌
 49/4
Pravilna rešitev nagra-
dne križanke iz četrte
številke Preseka letnika
49 je Predobdelava be-
sedila. Med pravilnimi
rešitvami smo izžrebali
naslednje reševalce: Ana
Pestotnik Stres iz Lju-
bljane, Marko Belingar iz
Solkana in Neda Tompa
iz Odrancev, ki bodo na-
grade prejeli po pošti.
×××