Hamingova distanca

Hamingova distanca između dva niza iste dužine predstavlja broj pozicija na kojima se njihovi simboli razlikuju.

To je jedna od najvažnijih mjera sličnosti u informatici, teoriji kodiranja i obradi podataka. Koristi se za otkrivanje grešaka pri prenosu informacija, poređenje binarnih nizova i analizu digitalnih kodova.

Drugim riječima, Hamingova distanca pokazuje koliko je izmjena potrebno da bi se jedan niz pretvorio u drugi.

Ako posmatramo dva niza \( s \) i \( t \) dužine \( n \), Hamingova distanca \( D_H(s, t) \) definiše se formulom:

$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$

pri čemu \( s_i \) i \( t_i \) označavaju simbole na poziciji \( i \), dok funkcija \( \delta(s_i, t_i) \) ima vrijednost 1 kada su simboli različiti, odnosno 0 kada su jednaki.

Važno je naglasiti da je Hamingova distanca definisana samo za nizove iste dužine.

Kako funkcioniše Hamingova distanca

Ideja je veoma jednostavna: porede se simbol po simbol dva niza iste dužine, a zatim se prebrojavaju pozicije na kojima postoji razlika.

Na primjer, posmatrajmo sljedeće nizove:

$$ s = \text{"karbon"} $$

$$ t = \text{"carbon"} $$

Ova dva niza razlikuju se samo po prvom slovu, pa je njihova Hamingova distanca jednaka:

$$ D_H(s,t)=1 $$

Još jedan primjer:

$$ s = \text{"thing"} $$

$$ t = \text{"thank"} $$

U ovom slučaju nizovi se razlikuju na dvije pozicije:

• u trećem slovu: « i » naspram « a »
• u petom slovu: « g » naspram « k »

Zbog toga je:

$$ D_H(s,t)=2 $$

Zašto je Hamingova distanca važna

Hamingova distanca ima ključnu ulogu u teoriji kodiranja i digitalnim komunikacijama.

Kada se podaci prenose preko mreže ili memorijskih sistema, može doći do promjene pojedinih bitova usljed šuma ili tehničkih grešaka. Hamingova distanca omogućava otkrivanje i ispravljanje takvih grešaka.

Na primjer, ako dva binarna koda imaju veliku Hamingovu distancu, mnogo je lakše otkriti da je tokom prenosa došlo do greške.

Zbog toga se ovaj koncept koristi u:

• teoriji kodiranja
• telekomunikacijama
• kriptografiji
• bioinformatici
• obradi signala
• vještačkoj inteligenciji

Metrička topologija indukovana Hamingovom distancom

Hamingova distanca nije samo praktičan alat u informatici. Ona takođe definiše pravi metrički prostor.

Da bi neka funkcija bila metrika, mora zadovoljiti tri osnovna svojstva:

1. Nenegativnost

   $$ D_H(x, y) \geq 0 \quad \text{i} \quad D_H(x, y)=0 \iff x=y $$

   Distanca nikada ne može biti negativna. Jednaka je nuli samo kada su nizovi potpuno identični.

2. Simetrija

   $$ D_H(x, y)=D_H(y, x) $$

   Redoslijed poređenja ne mijenja rezultat.

3. Nejednakost trougla

   $$ D_H(x, z)\leq D_H(x, y)+D_H(y, z) $$

   Direktna distanca između dva niza nikada nije veća od zbira distanci preko posrednog niza.

Pošto su ova svojstva zadovoljena, Hamingova distanca definiše metrički prostor.

Iz takve metrike moguće je konstruisati i odgovarajuću metričku topologiju.

Otvorene kugle u Hamingovom prostoru

Za niz \( x \) i radijus \( r \), otvorena kugla definiše se kao skup svih nizova čija je Hamingova distanca od \( x \) manja od \( r \):

$$ B(x,r)=\{y \mid D_H(x,y)<r\} $$

Ove otvorene kugle predstavljaju osnovne gradivne elemente topologije.

Napomena. Ako je skup svih nizova konačan, tada topologija indukovana Hamingovom distancom postaje diskretna topologija. U tom slučaju svaki pojedinačni niz može se posmatrati i kao otvoren i kao zatvoren skup.

Primjer topologije indukovane Hamingovom distancom

Posmatrajmo skup binarnih nizova dužine tri:

$$ X = \{000, 001, 011, 110, 111\} $$

Za radijus \( r = 2 \), otvorene kugle određuju se uslovom:

$$ B(x,r)=\{y \mid D_H(x,y)<2\} $$

To znači da svaki niz unutar kugle može da se razlikuje od centralnog niza u najviše jednoj poziciji.

• Kugla sa centrom u \( 000 \)

  $$ B(000,2)=\{000,001\} $$

  Niz \( 001 \) razlikuje se od niza \( 000 \) u samo jednom bitu.

• Kugla sa centrom u \( 001 \)

  $$ B(001,2)=\{001,000,011\} $$

  Nizovi \( 000 \) i \( 011 \) nalaze se na distanci 1 od niza \( 001 \).

• Kugla sa centrom u \( 011 \)

  $$ B(011,2)=\{011,001,111\} $$

  Nizovi \( 001 \) i \( 111 \) razlikuju se od niza \( 011 \) u jednoj poziciji.

• Kugla sa centrom u \( 110 \)

  $$ B(110,2)=\{110,111\} $$

  Niz \( 111 \) nalazi se na distanci 1 od niza \( 110 \).

• Kugla sa centrom u \( 111 \)

  $$ B(111,2)=\{111,011,110\} $$

  Nizovi \( 011 \) i \( 110 \) najbliži su nizu \( 111 \).

Ove otvorene kugle formiraju bazu topologije, jer se svi ostali otvoreni skupovi mogu dobiti njihovim unijama.

Napomena. Pošto se koristi stroga nejednakost \( D_H(x,y)<2 \), u otvorenu kuglu ulaze samo nizovi čija je distanca strogo manja od 2. Da se koristi uslov \( D_H(x,y)\leq2 \), dobio bi se zatvoreni skup.

Na primjer:

$$ B(000,2)\cup B(110,2) $$

pošto je:

$$ B(000,2)=\{000,001\} $$

i:

$$ B(110,2)=\{110,111\} $$

njihova unija iznosi:

$$ B(000,2)\cup B(110,2)=\{000,001,110,111\} $$

Prema tome, i ovaj skup predstavlja otvoren skup u topologiji indukovanoj Hamingovom distancom.

Na taj način Hamingova distanca ne definiše samo mjeru razlike između nizova, već i kompletnu metričku strukturu sa jasno definisanom topologijom.