Odległość Hamminga - Hamming distance
| |||
Klasa | Podobieństwo ciągów | ||
---|---|---|---|
Struktura danych | strunowy | ||
Wydajność w najgorszym przypadku | |||
Wydajność w najlepszym przypadku | |||
Średnia wydajność | |||
Najgorsza złożoność przestrzeni |
W teorii informacji The odległość Hamminga pomiędzy obu łańcuchów o równej długości jest ilość położeń, w których odpowiednie symbole są różne. Innymi słowy, mierzy minimalną liczbę podstawień wymaganych do zmiany jednego ciągu w drugi lub minimalną liczbę błędów, które mogły spowodować przekształcenie jednego ciągu w drugi. W bardziej ogólnym kontekście odległość Hamminga jest jedną z kilku metryk ciągu do pomiaru odległości edycji między dwiema sekwencjami. Jego nazwa pochodzi od nazwiska amerykańskiego matematyka Richarda Hamminga .
Głównym zastosowaniem jest teoria kodowania , a dokładniej kody blokowe , w których ciągi o równej długości są wektorami na polu skończonym .
Definicja
Odległość Hamminga między dwoma ciągami symboli o równej długości to liczba pozycji, w których odpowiednie symbole są różne.
Przykłady
Symbolami mogą być między innymi litery, bity lub cyfry dziesiętne. Na przykład odległość Hamminga między:
- „ ka rol in ” i „ ka thr in ” to 3.
- " k a r ol in " i " k e r st in " to 3.
- " k athr in " i " k erst in " wynosi 4.
- 0000 i 1111 to 4.
- 2 17 3 8 96 i 2 23 3 7 96 wynosi 3.
Nieruchomości
Dla stałej długości n odległość Hamminga jest metryką zbioru słów o długości n (znaną również jako przestrzeń Hamminga ), ponieważ spełnia ona warunki nieujemności, symetrii, odległość Hamminga dwóch słów wynosi 0 wtedy i tylko wtedy, gdy te dwa słowa są identyczne, i spełnia nierówność trójkąta , a także: Rzeczywiście, jeśli naprawimy trzy słowa , b i c , a następnie, gdy istnieje różnica między i th list a ja th list z C , to nie musi być różnicy między i th list a i p literą B lub między ı -go literą z b i ı -go literą z C . Stąd odległość Hamminga między a i c nie jest większa niż suma odległości Hamminga między a i b oraz między b i c . Odległość Hamminga pomiędzy dwoma słowami a i b mogą być również postrzegane jako ciężar Hamminga od a - b dla odpowiedniego wyboru - operatora, podobnie jak różnica między dwiema liczbami całkowitymi mogą być postrzegane jako pewnej odległości od zera na osi liczbowej.
Ciągów binarnych i b odległość Hamminga jest równa liczbie jedynek ( count populacji ) w a XOR b . Przestrzeń metryczna długości n ciągów binarnych, z odległością Hamminga, jest znana jako sześcian Hamminga ; jako przestrzeń metryczna jest równoważna zbiorowi odległości między wierzchołkami w grafie hipersześcianowym . Można również postrzegać ciąg binarny o długości n jako wektor in , traktując każdy symbol w ciągu jako rzeczywistą współrzędną; przy tym osadzeniu struny tworzą wierzchołki n- wymiarowego hipersześcianu , a odległość Hamminga strun jest równoważna odległości Manhattan między wierzchołkami.
Wykrywanie błędów i korekcja błędów
Minimalna odległość Hamminga służy do określenia pewnych podstawowych pojęć w teorii kodowania , takie jak błąd wykrywania i korekcji błędów kodami . W szczególności mówi się , że kod C jest k błędem wykrywającym wtedy i tylko wtedy, gdy minimalna odległość Hamminga między dowolnymi dwoma jego słowami kodowymi wynosi co najmniej k +1.
Rozważmy na przykład kod składający się z dwóch słów kodowych „000” i „111”. Odległość Hamminga między tymi dwoma słowami wynosi 3, a zatem jest to wykrywanie błędu k =2. Co oznacza, że jeśli jeden bit zostanie odwrócony lub dwa bity zostaną odwrócone, błąd może zostać wykryty. Jeśli trzy bity są odwrócone, „000” staje się „111” i nie można wykryć błędu.
Mówi się, że kod C jest k-błędami korygującymi, jeśli dla każdego słowa w w bazowej przestrzeni Hamminga H istnieje co najwyżej jedno słowo kodowe c (z C ) takie, że odległość Hamminga między w i c wynosi co najwyżej k . Innymi słowy, kod jest k -błędami korygującymi wtedy i tylko wtedy, gdy minimalna odległość Hamminga między dowolnymi dwoma jego słowami kodowymi wynosi co najmniej 2 k +1. Jest to bardziej zrozumiałe geometrycznie, gdy dowolne zamknięte kule o promieniu k wyśrodkowane na odrębnych słowach kodowych są rozłączne. W tym kontekście kule te nazywane są również kulami Hamminga .
Rozważmy na przykład ten sam 3-bitowy kod składający się z dwóch słów kodowych „000” i „111”. Przestrzeń Hamminga składa się z 8 słów 000, 001, 010, 011, 100, 101, 110 i 111. Słowo kodowe „000” i jednobitowe słowa błędu „001”, „010”, „100” są mniejsze niż lub równa odległości Hamminga od 1 do „000”. Podobnie, słowo kodu „111” i jego jednobitowe słowa błędu „110”, „101” i „011” znajdują się w odległości 1 Hamminga od oryginalnego „111”. W tym kodzie błąd jednobitowy jest zawsze w odległości 1 Hamminga od oryginalnych kodów, a kod może mieć korekcję 1-błędu , czyli k=1 . Minimalna odległość Hamminga między „000” a „111” wynosi 3, co odpowiada 2k+1 = 3 .
Zatem kod z minimalną odległością Hamminga d między jego słowami kodowymi może wykryć co najwyżej błędy d- 1 i może korygować błędy ( d- 1)/2⌋. Ta ostatnia liczba jest również nazywana promieniem pakowania lub zdolnością do korekcji błędów kodu.
Historia i aplikacje
Odległość Hamminga pochodzi od Richarda Hamminga , który wprowadził pojęcie w swojej fundamentalnej pracy na Kod Hamminga , Błąd wykrywania i korekcji błędów kody , w 1950 roku Hamminga analizy wagowej bitów jest wykorzystywany w wielu dziedzinach, w tym teorii informacji , teorii kodowania i kryptografii .
Jest używany w telekomunikacji do zliczania liczby odwróconych bitów w słowie binarnym o stałej długości jako oszacowania błędu i dlatego jest czasami nazywany odległością sygnału . Dla q- arnych ciągów w alfabecie o rozmiarze q ≥ 2 odległość Hamminga jest stosowana w przypadku kanału symetrycznego q-ary , podczas gdy odległość Lee jest używana do kluczowania z przesunięciem fazowym lub ogólniej kanałów podatnych na błędy synchronizacji, ponieważ Lee odległość uwzględnia błędy ±1. Jeśli lub obie odległości pokrywają się, ponieważ dowolna para elementów z lub różni się o 1, ale odległości są różne dla większej .
Odległość Hamminga jest również używana w systematyce jako miara dystansu genetycznego.
Jednak do porównywania ciągów o różnych długościach lub ciągów, w których należy spodziewać się nie tylko podstawień, ale także wstawień lub usunięć, bardziej odpowiednia jest bardziej wyrafinowana metryka, taka jak odległość Levenshteina .
Przykład algorytmu
Poniższa funkcja, napisana w Pythonie 3, zwraca odległość Hamminga między dwoma ciągami znaków:
def hamming_distance(string1, string2):
dist_counter = 0
for n in range(len(string1)):
if string1[n] != string2[n]:
dist_counter += 1
return dist_counter
Lub w krótszym wyrażeniu:
sum(xi != yi for xi, yi in zip(x, y))
Funkcja hamming_distance()
zaimplementowana w Pythonie 2.3+ oblicza odległość Hamminga między dwoma ciągami (lub innymi iterowalnymi obiektami) o równej długości, tworząc sekwencję wartości logicznych wskazujących na niezgodności i dopasowania między odpowiednimi pozycjami w dwóch danych wejściowych, a następnie sumując sekwencję za pomocą False i wartości True są interpretowane jako zero i jeden.
def hamming_distance(s1, s2) -> int:
"""Return the Hamming distance between equal-length sequences."""
if len(s1) != len(s2):
raise ValueError("Undefined for sequences of unequal length.")
return sum(el1 != el2 for el1, el2 in zip(s1, s2))
gdzie funkcja zip() łączy w pary dwie kolekcje o równej długości.
Poniższa funkcja C obliczy odległość Hamminga dwóch liczb całkowitych (traktowanych jako wartości binarne, czyli jako ciągi bitów). Czas trwania tej procedury jest proporcjonalny do odległości Hamminga, a nie do liczby bitów na wejściach. Oblicza bitową wyłączność lub dwóch danych wejściowych, a następnie znajduje wagę Hamminga wyniku (liczbę niezerowych bitów) za pomocą algorytmu Wegnera (1960), który wielokrotnie znajduje i usuwa bit niezerowy najniższego rzędu. Niektóre kompilatory obsługują funkcję __builtin_popcount, która może to obliczyć przy użyciu wyspecjalizowanego sprzętu procesorowego, jeśli jest dostępny.
int hamming_distance(unsigned x, unsigned y)
{
int dist = 0;
// The ^ operators sets to 1 only the bits that are different
for (unsigned val = x ^ y; val > 0; ++dist)
{
// We then count the bit set to 1 using the Peter Wegner way
val = val & (val - 1); // Set to zero val's lowest-order 1
}
// Return the number of differing bits
return dist;
}
Szybszą alternatywą jest użycie instrukcji asemblera liczby populacji ( popcount ). Niektóre kompilatory, takie jak GCC i Clang, udostępniają je za pośrednictwem funkcji wewnętrznej:
// Hamming distance for 32-bit integers
int hamming_distance32(unsigned int x, unsigned int y)
{
return __builtin_popcount(x ^ y);
}
// Hamming distance for 64-bit integers
int hamming_distance64(unsigned long long x, unsigned long long y)
{
return __builtin_popcountll(x ^ y);
}
Zobacz też
- Najbliższy ciąg
- odległość Damerau–Levenshtein
- Odległość euklidesowa
- Problem z luką-Hammingiem
- Szary kod
- Indeks Jaccarda
- Odległość Levenshteina
- Odległość Mahalanobisa
- Odległość Mannheima
- Indeks podobieństwa Sørensena
- Rzadka pamięć rozproszona
- Drabina słowna
Bibliografia
Dalsza lektura
- Ten artykuł zawiera materiał z domeny publicznej z dokumentu General Services Administration : „Federal Standard 1037C” .
- Wegner, Piotr (1960). „Technika liczenia jedynek w komputerze binarnym”. Komunikaty ACM . 3 (5): 322. doi : 10.1145/367236.367286 . S2CID 31683715 .
- MacKay, David JC (2003). Teoria informacji, wnioskowanie i algorytmy uczenia się . Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 0-521-64298-1.