Hammingova razdalja

Iz MaFiRaWiki

Hammingova razdalja med binarnima vektorjema x=(x_1,\ldots,x_n) in y=(y_1,\ldots,y_n) je definirana kot d(x,y)=\sum_{i=1}^n |x_i - y_i|.

Idejo uporabimo pri razdalji med nizoma enakih dolžin. Hammingova razdalja med dvema nizoma pomeni število "komponent" (tj. istoležnih znakov), v katerih se dana niza razlikujeta. Razdaljo torej poiščemo tako, da vpeljemo novo tabelo dolžine n, za katero velja: na i-tem mestu je 1, če se niza na tem mestu razlikujeta, oziroma 0, če se ne. Končni rezultat bo vsota vseh elementov te tabele.

Časovna zahtevnost je linearna; napravimo ravno n primerjav.


Implementacija

Glej tudi

Osebna orodja