Distanța de Hamming

Hamming distance (code distance) - numărul de poziții în care caracterele corespunzătoare a două cuvinte de aceeași lungime sunt diferite [1] . Mai general, distanța Hamming este aplicată șirurilor de aceeași lungime a oricărui alfabet q - ary și servește ca metrică a diferenței (o funcție care determină distanța într-un spațiu metric ) a obiectelor de aceeași dimensiune.

Metrica a fost formulată inițial de Richard Hamming în timpul petrecut la Bell Labs pentru a defini o măsură a diferenței dintre cuvintele de cod ( vectori binari ) într-un spațiu vectorial de cuvinte de cod: în acest caz, distanța Hamming dintre două secvențe binare (vectori) și lungimea. este numărul de poziții în care sunt diferite. În această formulare, distanța Hamming a fost inclusă în Dicționarul NIST de algoritmi și structuri de date . Distanța Hamming este un caz special al metricii Minkowski (cu o definiție adecvată a scăderii): $d(x,y)$ $X$ $y$ $n$

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

Două cuvinte cu o distanță Hamming de 1 se numesc vecini.

În unele sisteme numerice, cum ar fi codul Gray , numerele întregi codificate care diferă cu 1 au o distanță Hamming de 1. Se spune că astfel de numere sunt „adiacente”.

Codarea vecinilor este importantă în proiectarea dispozitivelor logice, unde trebuie evitate cursele logice .

Exemple

$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 {Red}r}o{\ culoare {Red}s}e{\color {Red}s}} )=3$

Proprietăți

Un set de cuvinte de lungime egală formează un spațiu metric , unde pentru fiecare pereche de elemente spațiale este definit un număr - distanța Hamming care satisface axiomele metricii: $d(x,y)$

$d(x,\;y)=0\Săgeată stânga la dreapta x=y$ ( axioma identității ).
$d(x,\;y)=d(y,\;x)$ ( axioma de simetrie ).
$d(x,\;z)\leqslant d(x,\;y)+d(y,\;z)$ ( axioma triunghiului sau inegalitatea triunghiului ).

Din axiome rezultă că distanța este nenegativă, deoarece $0=d(x,x)\leqslant d(x,y)+d(y,x)=2\cdot d(x,y)$ .
Dacă reprezentăm inegalitatea triunghiului ca $d(x,y)\leqslant d(x,z)+d(y,z)$ pentru toti si $X y$ $z$

atunci axioma simetriei rezultă din axioma identității și inegalitatea triunghiului.

Distanța de hamming este întotdeauna:

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

unde este lungimea cuvintelor în caractere.

n

Distanța Hamming în bioinformatică și genomică

Pentru acizii nucleici ( ADN și ARN ), posibilitatea hibridizării a două lanțuri polinucleotidice cu formarea unei structuri secundare - o dublă helix - depinde de gradul de complementaritate a secvențelor de nucleotide ale ambelor lanțuri. Pe măsură ce distanța Hamming crește, numărul de legături de hidrogen formate din perechi de baze complementare scade și, în consecință, stabilitatea lanțului dublu scade. Pornind de la o anumită distanță Hamming, hibridizarea devine imposibilă.

În divergența evolutivă a secvențelor de ADN omoloage , distanța Hamming este o măsură prin care se poate judeca timpul care a trecut de la divergența omologilor, de exemplu, lungimea segmentului evolutiv care separă genele omoloage și o genă precursoare.

Vezi și

Note

↑ Hamming distance: numărul de poziții de cifre în care cifrele corespunzătoare a două cuvinte binare de aceeași lungime sunt diferite ( Federal Standard 1037C Arhivat la 2 martie 2009 la Wayback Machine ).

Literatură

Blahut R. Teoria și practica codurilor de control al erorilor. — M .: Mir , 1986. — 576 p.

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun