Hamming avstånd

Hamming distans (kodavstånd) - antalet positioner där motsvarande tecken i två ord av samma längd är olika [1] . Mer generellt tillämpas Hamming-avstånd på strängar av samma längd som valfritt q -ary- alfabet och fungerar som ett differensmått (en funktion som bestämmer avståndet i ett metriskt utrymme ) för objekt med samma dimension.

Måttet formulerades ursprungligen av Richard Hamming under hans tid på Bell Labs för att definiera ett mått på skillnaden mellan kodord (binära vektorer ) i ett vektorrum av kodord: i detta fall Hamming-avståndet mellan två binära sekvenser (vektorer) och längden är antalet positioner där de är olika. I denna formulering inkluderades Hamming-avståndet i NIST Dictionary of Algorithms and Data Structures . Hamming-avståndet är ett specialfall av Minkowski-måttet (med en lämplig definition av subtraktion): $d(x,y)$ $x$ $y$ $n$

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

Två ord med Hamming-avståndet 1 kallas grannar.

I vissa talsystem, som Gray-koden , har kodade heltal som skiljer sig med 1 ett Hamming-avstånd på 1. Sådana tal sägs vara "intilliggande".

Grannkodning är viktig i design av logiska enheter där logiska raser måste undvikas .

Exempel

$d(10{\color {SkyBlue}1}1{\color {SkyBlue}1}01,10{\color {Red}0}1{\color {Red}0}01)=2$
$d(2{\color {SkyBlue}17}3{\color {SkyBlue}8}96.2{\color {Red}23}3{\color {Red}7}96)=3$
$d(\mathrm {{\color {SkyBlue}t}o{\color {SkyBlue}n}e{\color {SkyBlue}d}} ,\mathrm {{\color {Röd}r}o{\ färg {Röd}s}e{\color {Röd}s}} )=3$

Egenskaper

En uppsättning ord av lika längd bildar ett metriskt mellanrum , där för varje par av rymdelement ett tal definieras - Hamming-avståndet som uppfyller metrikens axiom: $d(x,y)$

$d(x,\;y)=0\vänsterhögerpil x=y$ ( axiom för identitet ).
$d(x,\;y)=d(y,\;x)$ ( symmetrins axiom ).
$d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ ( triangelaxiom eller triangelolikhet ).

Det följer av axiomen att avståndet är icke-negativt, eftersom $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Om vi representerar triangeln olikhet som $d(x,y)\leqslant d(x,z)+d(y,z)$ för alla och $x,y$ $z$

då följer symmetriaxiomet av identitetsaxiomet och triangelolikheten.

Hammaravstånd är alltid:

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

var är längden på ord i tecken.

n

Hamming distans inom bioinformatik och genomik

För nukleinsyror ( DNA och RNA ) beror möjligheten till hybridisering av två polynukleotidkedjor med bildandet av en sekundär struktur - en dubbelhelix - på graden av komplementaritet hos nukleotidsekvenserna för båda kedjorna. När Hamming-avståndet ökar, minskar antalet vätebindningar som bildas av komplementära baspar och följaktligen minskar stabiliteten hos dubbelkedjan. Med utgångspunkt från något Hamming-avstånd, blir hybridisering omöjlig.

I den evolutionära divergensen av homologa DNA-sekvenser är Hamming-avståndet ett mått med vilket man kan bedöma tiden som har förflutit sedan divergensen av homologer, till exempel längden på det evolutionära segmentet som separerar homologa gener och en prekursorgen.

Se även

Anteckningar

↑ Hamming-avstånd: Antalet sifferpositioner där motsvarande siffror i två binära ord av samma längd är olika ( Federal Standard 1037C Arkiverad 2 mars 2009 på Wayback Machine ).

Litteratur

Blahut R. Teori och praktik av felkontrollkoder. — M .: Mir , 1986. — 576 sid.

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likheter
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen