Hammingetäisyyksiä

Hammingetäisyyksiä ovat kahden yhtä pitkän merkkijonon erojen lukumäärä. Määritelmä: d_H(x,y) = |{ i ∈ {1,...,n} : x_i ≠ y_i }|, jossa x and y ovat merkkijonoja pituudeltaan n. Tämä on mitta, joka laskee, kuinka monta sijaintia joissa merkit eroavat.

Hammingetäisyydet muodostavat metrisen etäisyysfunktion sanapareille, joiden pituus on sama. Ne täyttävät kolme perusominaisuutta: ne ovat ei-negatiivisia, nolla vastaa identtisiä sanoja, ne ovat symmetristen ja ne toteuttavat kolmioepäsuoran. Laajennettuna ne pätevät mille tahansa kiinteän pituuden merkkijonon tilalle sanakirjoista Σ^n.

Sovellukset ja merkitys: Viestinnässä ja tallennuksessa Hammingetäisyyksiä käytetään mittaamaan virheitä sekä suunnittelemaan virheenkorjaus- ja havaitsemiskoodauksia. Koodin pienin etäisyys d_min määrittää, montako virhettä voidaan havaita ja mahdollisesti korjata: voi havaita jopa d_min − 1 virhettä ja korjata jopa floor((d_min − 1)/2) virhettä. Yleisiä sovelluksia ovat Hamming-koodit ja muut virheenkorjauskoodit sekä merkkijonojen vertailu, kun halutaan mitata samankaltaisuutta kiinteän pituuden merkkijonoille. Binary-tapauksessa d_H(x,y) = wt(x XOR y), missä wt on merkkijonon Hamming-tila (ei-nollien määrä).

Esimerkki: x = 01011 ja y = 11001. Erot paikoissa 1 ja 4, joten d_H(x,y) = 2. Tämä havainnollistaa, miten Hammingetäisyys mittaa eroa kahden merkkijonon välillä.