Hammingova vzdálenost

Hammingova vzdálenost (kódová vzdálenost) - počet pozic, ve kterých se liší odpovídající znaky dvou slov stejné délky [1] . Obecněji platí, že Hammingova vzdálenost je aplikována na řetězce stejné délky všech q -árních abeced a slouží jako rozdílová metrika (funkce, která určuje vzdálenost v metrickém prostoru ) objektů stejné dimenze.

Metriku původně formuloval Richard Hamming během svého působení v Bellových laboratořích , aby definoval míru rozdílu mezi kódovými slovy (binárními vektory ) ve vektorovém prostoru kódových slov: v tomto případě Hammingova vzdálenost mezi dvěma binárními sekvencemi (vektory) a délka . je počet pozic, ve kterých se liší. V této formulaci byla Hammingova vzdálenost zahrnuta do NIST Dictionary of Algorithms and Data Structures . Hammingova vzdálenost je speciální případ Minkowského metriky (s vhodnou definicí odčítání): $d(x,y)$ $X$ $y$ $n$

d_{ij}=\součet _{k=1}^{p}\left|x_{ik}-x_{jk}\right|

Dvě slova s Hammingovou vzdáleností 1 se nazývají sousedé.

V některých číselných systémech, jako je Grayův kód , zakódovaná celá čísla, která se liší o 1, mají Hammingovu vzdálenost 1. Taková čísla jsou prý „sousední“.

Sousední kódování je důležité při návrhu logických zařízení, kde je třeba se vyhnout logickým závodům .

Příklady

$d(10{\color {SkyBlue}1}1{\color {SkyBlue}1}01,10{\color {Červená}0}1{\color {Červená}0}01)=2$
$d(2{\color {SkyBlue}17}3{\color {SkyBlue}8}96,2{\color {Červená}23}3{\color {Červená}7}96)=3$
$d(\mathrm {{\color {SkyBlue}t}o{\color {SkyBlue}n}e{\color {SkyBlue}d}} ,\mathrm {{\color {Red}r}o{\ barva {Červená}s}e{\barva {Červená}} )=3$

Vlastnosti

Sada slov o stejné délce tvoří metrický prostor , kde je pro každou dvojici prostorových prvků definováno číslo - Hammingova vzdálenost , která splňuje axiomy metriky: $d(x,y)$

$d(x,\;y)=0\Šipka doleva doprava x=y$ ( axiom identity ).
$d(x,\;y)=d(y,\;x)$ ( axiom symetrie ).
$d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ ( trojúhelníkový axiom nebo trojúhelníková nerovnost ).

Z axiomů vyplývá, že vzdálenost je nezáporná, od $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Pokud trojúhelníkovou nerovnost znázorníme jako $d(x,y)\leqslant d(x,z)+d(y,z)$ pro všechny a $x, y$ $z$

pak axiom symetrie vyplývá z axiomu identity a trojúhelníkové nerovnosti.

Hammingova vzdálenost je vždy:

d(x,\;y)\leqslant n,

kde je délka slov ve znacích.

n

Hammingova vzdálenost v bioinformatice a genomice

U nukleových kyselin ( DNA a RNA ) závisí možnost hybridizace dvou polynukleotidových řetězců se vznikem sekundární struktury - dvoušroubovice - na míře komplementarity nukleotidových sekvencí obou řetězců. S rostoucí Hammingovou vzdáleností klesá počet vodíkových vazeb tvořených komplementárními páry bází a v souladu s tím klesá stabilita dvojího řetězce. Počínaje nějakou hraniční Hammingovou vzdáleností je hybridizace nemožná.

V evoluční divergenci homologních sekvencí DNA je Hammingova vzdálenost měřítkem, podle kterého lze posoudit čas, který uplynul od divergence homologů, například délku evolučního segmentu oddělujícího homologní geny a prekurzorový gen.

Viz také

Poznámky

↑ Hammingova vzdálenost: Počet pozic číslic, ve kterých se liší odpovídající číslice dvou binárních slov stejné délky ( Federal Standard 1037C Archived 2 March 2009 at Wayback Machine ).

Literatura

Blahut R. Teorie a praxe kódů kontroly chyb. — M .: Mir , 1986. — 576 s.

Struny
Míry podobnosti řetězců	Vzdálenost Damerau - Loewenstein Levenshteinská vzdálenost Hammingova vzdálenost Podobnost Jaro-Winkler
Hledání podřetězců	Boyer-Mooreův algoritmus Algoritmus Boyer-Moore-Horspool Knuth-Morris-Prattův algoritmus Rabin-Karpův algoritmus funkce předpony Z-funkce Algoritmus Aho - Korasik
palindromy	palindromový strom Manažerův algoritmus
Sekvenční zarovnání	Algoritmus Needleman-Wunsha Smith-Watermanův algoritmus
Struktury přípon	Pole přípon Přípona automat příponový strom předponový strom
jiný	rozebrat Shoda vzorů Největší společná podsekvence Největší společný podřetězec