Hamming távolság

Hamming távolság (kód távolság) - azon pozíciók száma, amelyekben két azonos hosszúságú szó megfelelő karakterei különböznek [1] . Általánosabban fogalmazva, a Hamming-távolságot bármely q - ary ábécé azonos hosszúságú karakterláncaira alkalmazzák, és az azonos méretű objektumok különbségi metrikájaként (egy metrikus tér távolságát meghatározó függvényként) szolgál.

A mérőszámot eredetileg Richard Hamming fogalmazta meg a Bell Labs -nál töltött ideje alatt, hogy meghatározza a kódszavak (bináris vektorok ) közötti különbség mértékét a kódszavak vektorterében: ebben az esetben a Hamming-távolságot két bináris sorozat (vektor) között és a hosszúságot . azoknak a pozícióknak a száma, amelyekben különböznek. Ebben a megfogalmazásban a Hamming - távolság szerepelt a NIST Algorithms and Data Structures szótárában . A Hamming-távolság a Minkowski-metrika speciális esete (a kivonás megfelelő definíciójával): $d(x,y)$ $x$ $y$ $n$

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

Két szót, amelyek Hamming-távolsága 1, szomszédoknak nevezzük.

Egyes számrendszerekben, például a Gray-kódban , az 1-gyel eltérő kódolt egész számok Hamming-távolsága 1. Az ilyen számokat "szomszédosnak" nevezik.

A szomszédos kódolás fontos a logikai eszközök tervezésében, ahol el kell kerülni a logikai versenyeket .

Példák

$d(10{\color {SkyBlue}1}1{\color {SkyBlue}1}01,10{\color {Red}0}1{\color {Piros}0}01)=2$
$d(2{\color {SkyBlue}17}3{\color {SkyBlue}8}96.2{\color {Red}23}3{\color {Piros}7}96)=3$
$d(\mathrm {{\color {SkyBlue}t}o{\color {SkyBlue}n}e{\color {SkyBlue}d}} ,\mathrm {{\color {Red}r}o{\ szín {Red}s}e{\color {Red}s}} )=3$

Tulajdonságok

Egyenlő hosszúságú szavak halmaza egy metrikus teret alkot , ahol minden térelempárhoz egy szám van megadva - a Hamming-távolság , amely kielégíti a metrika axiómáit: $d(x,y)$

$d(x,\;y)=0\balra jobbra nyíl x=y$ ( identitás axiómája ).
$d(x,\;y)=d(y,\;x)$ ( szimmetria-axióma ).
$d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ ( háromszög axióma vagy háromszög egyenlőtlenség ).

Az axiómákból következik, hogy a távolság nem negatív, hiszen $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Ha a háromszög egyenlőtlenséget úgy ábrázoljuk $d(x,y)\leqslant d(x,z)+d(y,z)$ mindenkinek és _ $x,y$ $z$

akkor az azonosság axiómájából és a háromszög egyenlőtlenségből következik a szimmetriaxióma.

Hamming távolság mindig:

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

hol a szavak hossza karakterekben.

n

Hamming-távolság a bioinformatikában és a genomikában

Nukleinsavak ( DNS és RNS ) esetében két polinukleotid lánc hibridizációjának lehetősége egy másodlagos szerkezet - kettős hélix - kialakításával mindkét lánc nukleotidszekvenciájának komplementaritási fokától függ. A Hamming-távolság növekedésével a komplementer bázispárok által alkotott hidrogénkötések száma csökken, és ennek megfelelően csökken a kettős lánc stabilitása. Valamilyen határ Hamming távolságból kiindulva a hibridizáció lehetetlenné válik.

A homológ DNS-szekvenciák evolúciós divergenciájában a Hamming-távolság egy olyan mérték, amely alapján meg lehet ítélni a homológok eltérése óta eltelt időt, például a homológ géneket és a prekurzor gént elválasztó evolúciós szegmens hosszát.

Lásd még

Jegyzetek

↑ Hamming-távolság: Azon számjegyek száma, amelyekben két azonos hosszúságú bináris szó megfelelő számjegyei különböznek ( szövetségi szabvány, 1037C , archiválva : 2009. március 2., a Wayback Machine -nél ).

Irodalom

Blahut R. A hibaellenőrző kódok elmélete és gyakorlata. — M .: Mir , 1986. — 576 p.

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc