Odległość Hamminga
Odległość Hamminga (ang. Hamming distance), – wprowadzona przez Richarda Hamminga miara odmienności dwóch ciągów o takiej samej długości, wyrażająca liczbę miejsc (pozycji), na których te dwa ciągi się różnią. Innymi słowy jest to najmniejsza liczba zmian (operacji zastępowania elementu innym), jakie pozwalają przeprowadzić jeden ciąg na drugi.
Własności
Dla ustalonej długości odległość Hamminga jest metryką na przestrzeni wektorowej słów o tej długości.
Dla ciągów binarnych i odległość Hamminga jest równa liczbie jedynek w słowie XOR .
Przestrzeń metryczna słów binarnych o długości z odległością Hamminga, jest nazywana kostką Hamminga. Słowa binarne o długości można traktować jako wektory w przestrzeni przyjmując każdy symbol w łańcuchu jako współrzędną rzeczywistą; przy tym zanurzeniu takie łańcuchy stanowią wierzchołki -wymiarowej hiperkostki, a odległość Hamminga słów jest równoważna metryce taksówkowej pomiędzy wierzchołkami.
Opis
Ścisła implementacja zależy oczywiście od definicji użytych ciągów. Na przykład dwa ciągi bajtów zapisanych w pamięci komputera można, zależnie od potrzeb, potraktować jako ciągi binarne lub ciągi literowe zakodowane w ASCII; odpowiednio odległość Hamminga będziemy definiować jako liczbę różnych bitów lub różnych bajtów.
Przykłady:
- odległość pomiędzy ciągami
10011101
i10111001
wynosi 2. - odległość pomiędzy ciągami
zagrabić
izatrąbił
wynosi 3.
Uogólnieniem odległości Hamminga jest odległość Levenshteina, uwzględniająca nie tylko zamianę znaku na inny, ale także wstawianie i usuwanie znaków z ciągu (a więc obejmująca napisy o różnych długościach).