Was ist die Hamming-Distanz? Konzept, Implementierung und praktische Anwendungen

Die Hamming-Distanz misst die Anzahl der Positionen, an denen sich zwei gleich lange Sequenzen unterscheiden. Sie ist einfach, schnell und besonders nützlich bei Strings, Bitfolgen und binären Merkmalen.

Grundidee

Beispiel:

karolin
kathrin

Positionsweiser Vergleich:

k a r o l i n
k a t h r i n
    ↑ ↑ ↑

Drei Positionen unterscheiden sich:

Hamming Distance = 3

In der klassischen Definition müssen beide Sequenzen dieselbe Länge besitzen.

Formale Definition

Für zwei Sequenzen x und y der Länge n:

H(x, y) = Σ [x[i] ≠ y[i]]

Jede unterschiedliche Position zählt als 1.

Algorithmus

1. Prüfen, ob beide Eingaben gleich lang sind.
2. Zähler mit 0 initialisieren.
3. Alle Positionen durchlaufen.
4. Bei einem Unterschied den Zähler erhöhen.
5. Zähler zurückgeben.

function hammingDistance(a, b):
    if length(a) != length(b):
        error

    distance = 0

    for i from 0 to length(a) - 1:
        if a[i] != b[i]:
            distance++

    return distance

TypeScript

function hammingDistance(a: string, b: string): number {
  if (a.length !== b.length) {
    throw new Error("Inputs must have the same length.");
  }

  let distance = 0;

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      distance++;
    }
  }

  return distance;
}

Komplexität

Time Complexity: O(n)
Space Complexity: O(1)

Jede Position wird einmal geprüft, zusätzlicher Speicher ist praktisch nicht nötig.

Binäre Zahlen und XOR

Bei zwei Ganzzahlen ist XOR besonders praktisch.

1010
XOR
1110
----
0100

Jedes gesetzte Bit im XOR-Ergebnis repräsentiert eine unterschiedliche Bitposition.

Hamming Distance = Anzahl der 1-Bits in (x XOR y)

Mit Brian Kernighans Technik:

function hammingDistanceBits(x: number, y: number): number {
  let value = x ^ y;
  let distance = 0;

  while (value !== 0) {
    value &= value - 1;
    distance++;
  }

  return distance;
}

value & (value - 1) entfernt in jedem Durchlauf ein gesetztes Bit.

Praktische Anwendungen

Fehlererkennung und Codierung

Die Hamming-Distanz ist wichtig für Error Detection und Error-Correcting Codes.

Digitale Kommunikation

Bitmuster können effizient verglichen werden, um Unterschiede in übertragenen Daten zu erkennen.

Computer Vision

Binäre Deskriptoren von Bildmerkmalen lassen sich mit der Hamming-Distanz schnell vergleichen.

Machine Learning

Für binäre oder kategorial codierte Feature-Vektoren kann sie als einfache Distanzmetrik dienen.

A = [1, 0, 1, 1, 0]
B = [1, 1, 1, 0, 0]

Distance = 2

Hamming-Distanz vs. Levenshtein-Distanz

Die Hamming-Distanz vergleicht nur korrespondierende Positionen und setzt normalerweise gleiche Längen voraus.

Die Levenshtein-Distanz erlaubt dagegen:

• Insert
• Delete
• Replace

Für cat und cats ist die klassische Hamming-Distanz nicht definiert, während die Levenshtein-Distanz 1 beträgt.

Wann ist sie geeignet?

Die Hamming-Distanz ist sinnvoll, wenn Sequenzen gleich lang sind, Positionen relevant sind und nur Unterschiede beziehungsweise Substitutionen gezählt werden sollen.

Wenn Einfügen und Löschen ebenfalls berücksichtigt werden müssen, ist Levenshtein meist geeigneter.

Typische Interviewfrage

Gegeben sind zwei Ganzzahlen x und y. Wie viele Bits müssen geändert werden, um x in y zu verwandeln?

Lösung:

1. x XOR y berechnen
2. gesetzte Bits zählen

Beispiel:

1 = 0001
4 = 0100
XOR = 0101

Die Distanz ist 2.

Fazit

Die Hamming-Distanz zählt die Positionen, an denen zwei gleich lange Sequenzen voneinander abweichen.

Bei Strings reicht eine lineare Schleife. Für Integer ist XOR + Set-Bit Counting die typische Lösung. Durch O(n) Laufzeit und O(1) zusätzlichen Speicher ist die Methode einfach und effizient.