Hammerafstand

Hamming distance (kodeafstand) - antallet af positioner, hvor de tilsvarende tegn i to ord af samme længde er forskellige [1] . Mere generelt anvendes Hamming-afstand til strenge af samme længde som et hvilket som helst q - ary alfabet og fungerer som en differensmetrik (en funktion, der bestemmer afstanden i et metrisk rum ) for objekter af samme dimension.

Metrikken blev oprindeligt formuleret af Richard Hamming under hans tid hos Bell Labs for at definere et mål for forskellen mellem kodeord (binære vektorer ) i et vektorrum af kodeord: i dette tilfælde Hamming-afstanden mellem to binære sekvenser (vektorer) og længden er antallet af stillinger, hvor de er forskellige. I denne formulering blev Hamming-afstanden inkluderet i NIST Dictionary of Algorithms and Data Structures . Hamming-afstanden er et specialtilfælde af Minkowski-metrikken (med en passende definition af subtraktion): $d(x,y)$ $x$ $y$ $n$

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

To ord med en Hamming-afstand på 1 kaldes naboer.

I nogle talsystemer, såsom Gray-koden , har kodede heltal, der adskiller sig med 1, en Hamming-afstand på 1. Sådanne tal siges at være "tilstødende".

Nabokodning er vigtig i logisk enhedsdesign, hvor logiske racer skal undgås .

Eksempler

$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 {Himmelblå}t}o{\color {Himmelblå}n}e{\color {Himmelblå}d}} ,\mathrm {{\color {Rød}r}o{\ farve {Rød}s}e{\color {Rød}s}} )=3$

Egenskaber

Et sæt ord af lige længde danner et metrisk rum , hvor der for hvert par rumelementer er defineret et tal - Hamming-afstanden , der opfylder metrikkens aksiomer: $d(x,y)$

$d(x,\;y)=0\venstrehøjrepil x=y$ ( identitetsaksiom ).
$d(x,\;y)=d(y,\;x)$ ( symmetriaksiom ).
$d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ ( trekantaksiom eller trekantsulighed ).

Det følger af aksiomerne, at afstanden er ikke-negativ, da $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Hvis vi repræsenterer trekanten ulighed som $d(x,y)\leqslant d(x,z)+d(y,z)$ for alle og $x,y$ $z$

så følger symmetriaksiomet af identitetsaksiomet og trekantens ulighed.

Hammerafstand er altid:

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

hvor er længden af ord i tegn.

n

Hamming distance i bioinformatik og genomik

For nukleinsyrer ( DNA og RNA ) afhænger muligheden for hybridisering af to polynukleotidkæder med dannelsen af en sekundær struktur - en dobbelthelix - af graden af komplementaritet af nukleotidsekvenserne i begge kæder. Efterhånden som Hamming-afstanden stiger, falder antallet af hydrogenbindinger dannet af komplementære basepar, og følgelig falder stabiliteten af dobbeltkæden. Startende fra en eller anden grænse Hamming-afstand, bliver hybridisering umulig.

I den evolutionære divergens af homologe DNA-sekvenser er Hamming-afstanden et mål, hvormed man kan bedømme den tid, der er gået siden divergensen af homologer, for eksempel længden af det evolutionære segment, der adskiller homologe gener og et precursor-gen.

Se også

Noter

↑ Hamming distance: Antallet af cifferpositioner, hvor de tilsvarende cifre i to binære ord af samme længde er forskellige ( Federal Standard 1037C Arkiveret 2. marts 2009 på Wayback Machine ).

Litteratur

Blahut R. Teori og praksis for fejlkontrolkoder. — M .: Mir , 1986. — 576 s.

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng