Hammingin etäisyys

Hamming-etäisyys (koodietäisyys) - niiden paikkojen lukumäärä, joissa kahden samanpituisen sanan vastaavat merkit ovat erilaisia [1] . Yleisemmin Hamming-etäisyyttä sovelletaan minkä tahansa qary-aakkoston samanpituisiin merkkijonoihin, ja se toimii erometriikkana (funktio, joka määrittää etäisyyden metrisessa avaruudessa ) samankokoisten kohteiden kohdalla.

Mittarin muotoili alun perin Richard Hamming ollessaan Bell Labsissa määrittääkseen koodisanojen (binäärivektorien) välisen eron koodisanojen vektoriavaruudessa : tässä tapauksessa kahden binäärisekvenssin (vektorin) välinen Hamming-etäisyys ja pituus . on niiden paikkojen lukumäärä, joissa ne ovat erilaisia. Tässä sanamuodossa Hamming-etäisyys sisällytettiin NIST : n algoritmien ja tietorakenteiden sanakirjaan . Hamming-etäisyys on Minkowski-metriikan erikoistapaus (jossa on sopiva vähennyslasku): $d(x,y)$ $x$ $y$ $n$

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

Kahta sanaa, joiden Hamming-etäisyys on 1, kutsutaan naapuriksi.

Joissakin numerojärjestelmissä, kuten Gray-koodissa , koodattujen kokonaislukujen, jotka eroavat 1:llä, Hamming-etäisyys on 1. Tällaisten lukujen sanotaan olevan "vierekkäisiä".

Naapurikoodaus on tärkeää logiikkalaitteiden suunnittelussa, jossa logiikkakilpailuja on vältettävä .

Esimerkkejä

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

Ominaisuudet

Joukko yhtä pitkiä sanoja muodostaa metriavaruuden , jossa kullekin avaruuselementtiparille on määritelty luku - Hamming-etäisyys , joka täyttää metriikan aksioomat: ${\näyttötyyli d(x,y)}$

$d(x,\;y)=0\nuoli vasen oikealle x=y$ ( identiteetin aksiooma ).
$d(x,\;y)=d(y,\;x)$ ( symmetria-aksiooma ).
$d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ ( kolmion aksiooma tai kolmion epäyhtälö ).

Aksioomista seuraa, että etäisyys ei ole negatiivinen, koska $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Jos edustamme kolmion epäyhtälöä as $d(x,y)\leqslant d(x,z)+d(y,z)$ kaikille ja _ $x,y$ $z$

silloin symmetria-aksiooma seuraa identiteetin aksioomasta ja kolmio-epäyhtälöstä.

Hamming-etäisyys on aina:

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

missä on sanojen pituus merkeissä.

n

Hamming-etäisyys bioinformatiikassa ja genomiikassa

Nukleiinihappojen ( DNA ja RNA ) tapauksessa mahdollisuus kahden polynukleotidiketjun hybridisoitumiseen sekundaarirakenteen - kaksoiskierteen - muodostumiseen riippuu molempien ketjujen nukleotidisekvenssien komplementaarisuuden asteesta. Kun Hamming-etäisyys kasvaa, komplementaaristen emäsparien muodostamien vetysidosten määrä vähenee ja vastaavasti kaksoisketjun stabiilius heikkenee. Alkaen jostain raja-Hamming-etäisyydestä hybridisaatiosta tulee mahdotonta.

Homologisten DNA-sekvenssien evoluutiohajaantumisessa Hamming-etäisyys on mitta, jolla voidaan arvioida aika, joka on kulunut homologien eroamisesta, esimerkiksi homologisia geenejä ja esiastegeeniä erottavan evoluutiolohkon pituus.

Katso myös

Muistiinpanot

↑ Hamming-etäisyys: Niiden numeropaikkojen määrä, joissa kahden samanpituisen binäärisanan vastaavat numerot ovat erilaisia ( liittovaltion standardi 1037C, arkistoitu 2. maaliskuuta 2009 Wayback Machinessa ).

Kirjallisuus

Blahut R. Virheenhallintakoodien teoria ja käytäntö. — M .: Mir , 1986. — 576 s.

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
muu	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono