Hammingafstand
De Hammingafstand tussen twee tekenreeksen van gelijke lengte is het aantal posities waarop de overeenkomstige symbolen van elkaar verschillen.
De maat werd ontwikkeld door de Amerikaanse wiskundige Richard Hamming en speelt een belangrijke rol in de informatietheorie, foutdetectie en coderingstheorie.
In de praktijk geeft de Hammingafstand aan hoeveel symbolen moeten worden gewijzigd om de ene tekenreeks in de andere om te zetten.
Beschouwen we twee tekenreeksen \( s \) en \( t \) met lengte \( n \), dan wordt de Hammingafstand \( D_H(s, t) \) gedefinieerd door:
$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$
Hierbij stellen \( s_i \) en \( t_i \) de symbolen voor op positie \( i \) in respectievelijk \( s \) en \( t \). De functie \( \delta(s_i, t_i) \) neemt de waarde 1 aan wanneer \( s_i \neq t_i \), en 0 wanneer beide symbolen identiek zijn.
De Hammingafstand is alleen gedefinieerd voor tekenreeksen met dezelfde lengte \( n \).
Een eenvoudig voorbeeld
Beschouw de volgende twee tekenreeksen:
$$ s = \text{"karbon"} $$
$$ t = \text{"carbon"} $$
De Hammingafstand tussen \( s \) en \( t \) is gelijk aan 1, omdat beide woorden slechts verschillen in de eerste letter.
Voorbeeld 2
Hieronder staat een tweede voorbeeld met twee Engelse woorden:
$$ s = \text{"thing"} $$
$$ t = \text{"thank"} $$
Deze tekenreeksen verschillen op twee posities:
bij de derde letter (« i » tegenover « a ») en bij de vijfde letter (« g » tegenover « k »).
De Hammingafstand tussen beide woorden is dus gelijk aan 2.
De metrische topologie van de Hammingafstand
De Hammingafstand definieert een metrische ruimte, omdat zij voldoet aan de fundamentele eigenschappen van een metriek.
Voor elk drietal tekenreeksen \( x \), \( y \) en \( z \) van gelijke lengte gelden de volgende eigenschappen:
- Niet-negativiteit
$$ D_H(x, y) \geq 0 \quad \text{en} \quad D_H(x, y) = 0 \ \text{dan en slechts dan als} \ x = y $$
De Hammingafstand is altijd positief of nul, omdat zij het aantal verschillen tussen twee tekenreeksen telt. Alleen identieke tekenreeksen hebben afstand nul. - Symmetrie
$$ D_H(x, y) = D_H(y, x) $$
Het maakt geen verschil in welke volgorde twee tekenreeksen worden vergeleken. De afstand blijft hetzelfde. - Driehoeksongelijkheid
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
De directe afstand tussen \( x \) en \( z \) kan nooit groter zijn dan de afstand via een tussenliggende tekenreeks \( y \).
Omdat aan deze eigenschappen wordt voldaan, definieert de Hammingafstand een metrische ruimte op de verzameling van tekenreeksen met vaste lengte.
Vanuit deze metriek kan vervolgens een topologie worden opgebouwd.
Meer bepaald maakt de Hammingafstand het mogelijk een metrische topologie te definiëren.
Voor elke tekenreeks \( x \) met lengte \( n \) en elke straal \( r \) definieert men een open bol \( B \) met middelpunt \( x \) als:
$$ B(x, r) = \{y \mid D_H(x, y) < r\}. $$
Deze open bollen vormen een basis van de metrische topologie, omdat elke open verzameling kan worden geschreven als een unie van zulke bollen.
Opmerking. Wanneer de verzameling van mogelijke tekenreeksen eindig is, zoals bij binaire tekenreeksen van vaste lengte, ontstaat een discrete topologie. Elke tekenreeks kan dan zowel als open als gesloten worden beschouwd. Door bijvoorbeeld \( r = 1 \) te kiezen, bevat een open bol slechts één enkel element.
De Hammingafstand induceert dus op eindige verzamelingen een discrete metrische topologie.
Voorbeeld
Beschouw de volgende verzameling binaire tekenreeksen van lengte drie:
$$ X = \{000, 001, 011, 110, 111 \} $$
Onderzoek nu de open bollen met straal \( r = 2 \):
$$ B(x, r) = \{y \mid D_H(x, y) < 2 \} $$
Elke open bol bevat alle tekenreeksen die op hoogstens één positie verschillen van het middelpunt.
- Open bol met middelpunt \( 000 \) : $$ B(000, 2) = \{000, 001\} $$ Alleen \( 001 \) verschilt op één positie van \( 000 \).
- Open bol met middelpunt \( 001 \) : $$ B(001, 2) = \{001, 000, 011 \} $$ Zowel \( 000 \) als \( 011 \) ligt op afstand 1 van \( 001 \).
- Open bol met middelpunt \( 011 \) : $$ B(011, 2) = \{011, 001, 111\} $$ De tekenreeksen \( 001 \) en \( 111 \) verschillen telkens op één positie van \( 011 \).
- Open bol met middelpunt \( 110 \) : $$ B(110, 2) = \{110, 111\} $$ Alleen \( 111 \) verschilt op één positie van \( 110 \).
- Open bol met middelpunt \( 111 \) : $$ B(111, 2) = \{111, 011, 110\} $$ De tekenreeksen \( 011 \) en \( 110 \) liggen op afstand 1 van \( 111 \).
Deze open bollen vormen de basis van de geïnduceerde topologie, omdat alle andere open verzamelingen kunnen worden verkregen via unies van zulke bollen.
Opmerking. Omdat een open bol de grenspunten niet bevat, gebruikt men een strikte ongelijkheid: $$ B(x, r) = \{ y \mid D_H(x, y) < 2 \} $$ Voor gesloten verzamelingen gebruikt men daarentegen de niet-strikte ongelijkheid: $$ C(x, r) = \{ y \mid D_H(x, y) \le 2 \} $$
Neem bijvoorbeeld de unie van de bollen \( B(000, 2) \) en \( B(110, 2) \):
$$ B(000, 2) \cup B(110, 2) $$
Aangezien:
$$ B(000, 2) = \{000, 001\} $$
en
$$ B(110, 2) = \{110, 111\} $$
volgt:
$$ B(000, 2) \cup B(110, 2) = \{000, 001, 110, 111\} $$
Ook deze verzameling is dus open binnen de geïnduceerde topologie.
Op die manier ontstaat een metrische topologie gebaseerd op de Hammingafstand, waarbij open verzamelingen worden opgebouwd uit open bollen met vaste straal.
En zo verder.
