Hamming-Distanz
Die Hamming-Distanz zwischen zwei Zeichenketten gleicher Länge ist die Anzahl der Positionen, an denen sich die jeweiligen Zeichen unterscheiden.
Einfach gesagt beantwortet sie eine sehr konkrete Frage: An wie vielen Stellen muss ich ein Zeichen austauschen, um aus einer Zeichenkette die andere zu machen?
Seien \( s \) und \( t \) zwei Zeichenketten der Länge \( n \). Dann ist die Hamming-Distanz \( D_H(s, t) \) definiert durch:
$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$
Dabei steht \( s_i \) für das Zeichen an Position \( i \) in \( s \) und \( t_i \) für das entsprechende Zeichen in \( t \). Die Funktion \( \delta(s_i, t_i) \) ist gleich 1, wenn sich die beiden Zeichen unterscheiden, und 0, wenn sie identisch sind.
Wichtig ist: Die Hamming-Distanz ist nur für Zeichenketten gleicher Länge \( n \) definiert.
Beispiele
Beginnen wir mit einem einfachen Fall:
$$ s = \text{"karbon"} $$
$$ t = \text{"carbon"} $$
Hier beträgt die Hamming-Distanz 1, da sich die beiden Wörter nur im ersten Zeichen unterscheiden (k statt c).
Beispiel 2
Ein zweites Beispiel zeigt, wie mehrere Unterschiede gezählt werden:
$$ s = \text{"thing"} $$
$$ t = \text{"thank"} $$
Diese beiden Wörter unterscheiden sich an genau zwei Positionen:
an der dritten Position («i» gegen «a») und an der fünften Position («g» gegen «k»).
Von der Distanz zur Metrik
Die Hamming-Distanz ist mehr als nur ein praktisches Zählverfahren. Sie erfüllt die grundlegenden Eigenschaften einer Metrik und definiert damit einen metrischen Raum.
- Nichtnegativität und Definitheit
$$ D_H(x, y) \geq 0 \quad \text{und} \quad D_H(x, y) = 0 \ \text{genau dann, wenn} \ x = y $$
Die Distanz ist immer größer oder gleich null und wird genau dann null, wenn beide Zeichenketten identisch sind. - Symmetrie
$$ D_H(x, y) = D_H(y, x) $$
Es spielt keine Rolle, in welcher Reihenfolge man vergleicht. Das Ergebnis bleibt gleich. - Dreiecksungleichung
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
Der direkte Abstand zwischen zwei Zeichenketten ist nie größer als der Weg über eine dritte.
Damit wird die Menge aller Zeichenketten fester Länge zu einem metrischen Raum.
Metrische Topologie
Jede Metrik erzeugt automatisch eine Topologie. Im Fall der Hamming-Distanz basiert diese auf dem Begriff der Nähe zwischen Zeichenketten.
Für eine Zeichenkette \( x \) und einen Radius \( r > 0 \) definiert man die offene Kugel:
$$ B(x, r) = \{ y \mid D_H(x, y) < r \}. $$
Diese Kugeln enthalten alle Zeichenketten, die sich nur wenig von \( x \) unterscheiden. Aus ihnen lassen sich alle offenen Mengen der Topologie zusammensetzen.
Hinweis. Ist die zugrunde liegende Menge endlich, etwa bei binären Zeichenketten fester Länge, dann ist die induzierte Topologie diskret. Jede einzelne Zeichenkette ist gleichzeitig offen und abgeschlossen. Wählt man beispielsweise \( r = 1 \), so enthält die offene Kugel nur das Zentrum selbst.
In diesem Fall ist also jede Teilmenge automatisch offen.
Konkretes Beispiel
Betrachten wir die Menge:
$$ X = \{000, 001, 011, 110, 111 \} $$
Für \( r = 2 \) gilt:
$$ B(x, r) = \{ y \mid D_H(x, y) < 2 \}. $$
Das bedeutet: Es werden genau die Zeichenketten aufgenommen, die sich in höchstens einer Position unterscheiden.
- Um \( 000 \) : $$ B(000, 2) = \{000, 001\} $$
- Um \( 001 \) : $$ B(001, 2) = \{001, 000, 011 \} $$
- Um \( 011 \) : $$ B(011, 2) = \{011, 001, 111\} $$
- Um \( 110 \) : $$ B(110, 2) = \{110, 111\} $$
- Um \( 111 \) : $$ B(111, 2) = \{111, 011, 110\} $$
Diese Mengen bilden eine Basis der Topologie. Jede weitere offene Menge entsteht durch Vereinigung solcher Kugeln.
Hinweis. Die Bedingung \( D_H(x, y) < 2 \) schließt alle Elemente mit Abstand genau 2 aus. Für abgeschlossene Kugeln verwendet man stattdessen $$ C(x, r) = \{ y \mid D_H(x, y) \leq 2 \}. $$
Ein Beispiel für eine offene Menge ist:
$$ B(000, 2) \cup B(110, 2) $$
Mit $ B(000, 2) = \{000, 001\} $ und $ B(110, 2) = \{110, 111\} $ ergibt sich:
$$ \{000, 001, 110, 111\}. $$
Auch diese Menge ist offen, da sie als Vereinigung offener Kugeln entsteht.
Die Hamming-Distanz liefert damit nicht nur ein einfaches Vergleichsmaß, sondern eine vollständige mathematische Struktur, die von der Metrik bis zur Topologie reicht.
