Hammingova vzdálenost - Hamming distance

Hammingova vzdálenost
4bitový binární tesseract
4bitový binární tesserakt pro nalezení Hammingovy vzdálenosti.
Příklady Hammingovy vzdálenosti 4bitového binárního tesseraktu
Dva příklady vzdáleností: 0100 → 1001 má vzdálenost 3; 0110 → 1110 má vzdálenost 1
Třída Podobnost řetězců
Datová struktura tětiva
Nejhorší výkon
Nejlepší výkon
Průměrný výkon
Nejhorší prostorová složitost
3bitová binární kostka
3bitová binární kostka pro nalezení Hammingovy vzdálenosti
3-bitové binární krychle Hammingova vzdálenost příklady
Dva příklady vzdáleností: 100 → 011 má vzdálenost 3; 010 → 111 má vzdálenost 2
Minimální vzdálenost mezi libovolnými dvěma vrcholy je Hammingova vzdálenost mezi dvěma binárními řetězci.

V teorii informací je Hammingova vzdálenost mezi dvěma stejně dlouhými řetězci počtem pozic, ve kterých se odpovídající symboly liší. Jinými slovy, měří minimální počet substitucí potřebných ke změně jednoho řetězce na druhý nebo minimální počet chyb, které mohly transformovat jeden řetězec na druhý. V obecnějším kontextu je Hammingova vzdálenost jednou z několika řetězcových metrik pro měření vzdálenosti úprav mezi dvěma sekvencemi. Je pojmenována po americkém matematikovi Richardu Hammingovi .

Hlavní aplikace je v teorii kódování , konkrétněji v blokových kódech , ve kterých jsou řetězce stejné délky vektory přes konečné pole .

Definice

Hammingova vzdálenost mezi dvěma stejně dlouhými řetězci symbolů je počet pozic, ve kterých se odpovídající symboly liší.

Příklady

Symboly mohou být mimo jiné písmena, bity nebo desetinné číslice. Například Hammingova vzdálenost mezi:

  • ka roll in “ a „ ka thr in “ je 3.
  • k a r ol in “ a „ k e r st in “ je 3.
  • k Athr in “ a „ k erst in “ jsou 4.
  • 0000 a 1111 jsou 4.
  • 2 17 3 8 96 a 2 23 3 7 96 je 3.

Vlastnosti

Pro pevnou délku n je Hammingova vzdálenost metrika na množině slov o délce n (také známá jako Hammingův prostor ), protože splňuje podmínky nezápornosti, symetrie, Hammingova vzdálenost dvou slov je 0 právě tehdy, jsou -li obě slova shodná, a splňuje také nerovnost trojúhelníku : Opravíme -li tři slova a , b a c , pak kdykoli existuje rozdíl mezi i -tým písmenem a a i -tým písmenem o c , pak musí existovat rozdíl mezi i th písmeno a i th písmeno b , nebo mezi i -tého dopisu b a i -tého dopisu c . Hammingova vzdálenost mezi a a c tedy není větší než součet Hammingových vzdáleností mezi a a b a mezi b a c . Hammingova vzdálenost mezi dvěma slovy dobu a b může také být viděn jako Hammingova hmotnost o s - b na vhodnou volbou - operátora, stejně jako rozdíl mezi dvěma celými čísly může být viděn jako vzdálenost od nuly na číslo řádku.

U binárních řetězců a b vzdálenost Hammingova je roven počtu ty ( počtu obyvatel ) v s XOR b . Metrický prostor length- n binárních řetězců, přičemž vzdálenost Hammingova, je známý jako krychle Hammingova ; je ekvivalentní metrickému prostoru množině vzdáleností mezi vrcholy v hyperkrychlovém grafu . Je také možné zobrazit binární řetězec délky n jako vektor, přičemž každý symbol v řetězci je považován za skutečnou souřadnici; s tímto vložením řetězce tvoří vrcholy n -rozměrné hyperkrychle a Hammingova vzdálenost řetězců je ekvivalentní vzdálenosti Manhattanu mezi vrcholy.

Detekce chyb a opravy chyb

Minimální Hammingova vzdálenost se používá k definování některé základní pojmy v teorii kódování , jako je chybové detekce a chyby opravovat kódy . Zejména se říká , že kód C je detekce chyb k , a pouze pokud je minimální Hammingova vzdálenost mezi jakýmikoli dvěma jeho kódovými slovy alespoň k +1.

Zvažte například kód sestávající ze dvou kódových slov „000“ a „111“. Hammingova vzdálenost mezi těmito dvěma slovy je 3, a proto je k = 2 detekce chyb. Což znamená, že pokud je převrácen jeden bit nebo jsou převráceny dva bity, lze chybu zjistit. Pokud jsou převráceny tři bity, pak se z „000“ stane „111“ a chybu nelze detekovat.

O kódu C se říká, že opravuje chyby k, pokud pro každé slovo w v základním Hammingově prostoru H existuje nejvýše jedno kódové slovo c (od C ) tak, že Hammingova vzdálenost mezi w a c je maximálně k . Jinými slovy, kód opravuje chyby k pouze tehdy, pokud je minimální Hammingova vzdálenost mezi libovolnými dvěma jeho kódovými slovy alespoň 2 k +1. Toto je geometricky snáze pochopitelné, protože jakékoli uzavřené koule o poloměru k soustředěné na odlišných kódových slovech jsou disjunktní. Tyto koule se v této souvislosti také nazývají Hammingovy koule .

Zvažte například stejný 3bitový kód skládající se ze dvou kódových slov „000“ a „111“. Hammingův prostor se skládá z 8 slov 000, 001, 010, 011, 100, 101, 110 a 111. Kódové slovo „000“ a jednobitová chybová slova „001“, „010“, „100“ jsou menší než nebo rovná Hammingově vzdálenosti 1 až „000“. Stejně tak kódové slovo "111" a jeho jednobitová chybová slova "110", "101" a "011" jsou od Hammingové vzdálenosti od původního "111". V tomto kódu je chyba jednoho bitu vždy do 1 Hammingovy vzdálenosti od původních kódů a kód může být opraven na 1 chybu , tj. K = 1 . Minimální Hammingova vzdálenost mezi „000“ a „111“ je 3, což splňuje 2k+1 = 3 .

Kód s minimální Hammingovou vzdáleností d mezi svými kódovými slovy může detekovat nejvýše chyby d -1 a opravit chyby ⌊ ( d -1)/2⌋. Druhé číslo se také nazývá poloměr balení nebo schopnost kódu opravovat chyby .

Historie a aplikace

Hammingův vzdálenost je pojmenoval Richard Hamming , který představil koncepci ve svém základním dokumentu o Hamming kódy , Error detekci a opravy chyb kódy , v roce 1950 analýzu Hammingova váha bitů se používá v několika disciplínách, včetně informační teorie , teorii kódování a kryptografii .

Používá se v telekomunikacích k počítání počtu převrácených bitů v binárním slově s pevnou délkou jako odhad chyby, a proto se někdy nazývá vzdálenost signálu . Pro q -ary řetězce nad abecedou velikosti q  ≥ 2 je Hammingova vzdálenost použita v případě symetrického kanálu q-ary , zatímco Leeova vzdálenost se používá pro klíčování s fázovým posunem nebo obecněji kanály náchylné k chybám synchronizace, protože Lee vzdálenost odpovídá chybám ± 1. Pokud nebo se obě vzdálenosti shodují, protože jakýkoli pár prvků od nebo se liší o 1, ale vzdálenosti jsou u větších rozdílné .

Hammingova vzdálenost se také používá v systematice jako měřítko genetické vzdálenosti.

Pro porovnávání řetězců různých délek nebo řetězců, kde je třeba očekávat nejen substituce, ale také vložení nebo odstranění, je vhodnější sofistikovanější metrika, jako je Levenshteinova vzdálenost .

Příklad algoritmu

Následující funkce napsaná v Pythonu 3 vrací Hammingovu vzdálenost mezi dvěma řetězci:

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

Nebo v kratším výrazu:

sum(xi != yi for xi, yi in zip(x, y))

Funkce hamming_distance()implementovaná v Pythonu 2.3+ vypočítá Hammingovu vzdálenost mezi dvěma řetězci (nebo jinými iterovatelnými objekty) stejné délky vytvořením sekvence booleovských hodnot indikujících neshody a shody mezi odpovídajícími polohami ve dvou vstupech a sečtením sekvence pomocí False a True hodnoty jsou interpretovány jako nula a jedna.

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))

kde funkce zip () sloučí dvě kolekce stejné délky v párech.

Následující funkce C vypočítá Hammingovu vzdálenost dvou celých čísel (považována za binární hodnoty, tj. Jako sekvence bitů). Doba běhu této procedury je úměrná spíše Hammingově vzdálenosti než počtu bitů ve vstupech. Vypočítá bitově exkluzivní nebo dva vstupy a poté najde Hammingovu váhu výsledku (počet nenulových bitů) pomocí Wegnerova algoritmu (1960), který opakovaně najde a vymaže nenulový bit nejnižšího řádu. Některé kompilátory podporují funkci __builtin_popcount, která to může vypočítat pomocí specializovaného hardwaru procesoru, je -li k dispozici.

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;
}

Rychlejší alternativou je použít instrukci sestavení počtu obyvatel ( popcount ). Některé kompilátory, jako GCC a Clang, jej zpřístupňují pomocí vlastní funkce:

// 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);
}

Viz také

Reference

Další čtení