Distanza di Hamming
Da Wikipedia, l'enciclopedia libera.
Nella teoria dell'informazione, la distanza di Hamming tra due stringhe di ugual lunghezza è il numero di posizioni nelle quali i simboli corrispondenti sono diversi. In altri termini, la distanza di Hamming misura il numero di sostituzioni necessarie per convertire una stringa nell'altra, o il numero di errori che hanno trasformato una stringa nell'altra.
Indice |
[modifica] Esempi
- La distanza di Hamming tra 1011101 e 1001001 è 2.
- La distanza di Hamming tra 2143896 e 2233796 è 3.
- La distanza di Hamming tra "dire" e "fare" è 2.
Il peso di Hamming di una stringa è la sua distanza di Hamming dalla stringa nulla (cioè dalla stringa costituita solo da zeri) della stessa lunghezza. Quindi è il numero di elementi diversi da zero di una stringa: per una stringa binaria è semplicemente il numero di 1; per esempio, il peso di Hamming di 11101 è 4.
[modifica] Proprietà
Per una fissata lunghezza n la distanza di Hamming è una metrica sullo spazio vettoriale delle stringhe aventi quella lunghezza, poiché soddisfa le condizioni di non negatività, identità di due elementi aventi distanza nulla, simmetria, e si può dimostrare mediante induzione completa che essa soddisfa anche la disuguaglianza triangolare.
La distanza di Hamming tra due elementi a e b è il peso di Hamming di a − b, per un'appropriata scelta dell'operatore " - ".
Per due stringhe binarie a e b essa è equivalente all'operazione a xor b. È anche equivalente alla distanza della geometria del taxi tra due vertici di un ipercubo n-dimensionale, dove n è la lunghezza delle stringhe.
[modifica] Storia e applicazioni
La distanza di Hamming prende il suo nome da Richard Hamming, che la introdusse nel suo fondamentale lavoro sui codici per il riconoscimento e la correzione degli errori. Viene usata nelle telecomunicazioni per contare il numero di bit errati in una parola binaria a lunghezza fissa, allo scopo di stimare l'errore. Per questo motivo viene anche chiamata distanza del segnale. L'analisi del peso di Hamming dei bit viene usata in diverse discipline, tra le quali la teoria dell'informazione, la teoria dei codici e la crittografia. Però, per confrontare stringhe di lunghezze differenti, o stringhe per le quali ci si aspettano anche inserimenti e cancellazioni, oltre alle sostituzioni, è più appropriato usare metriche più sofisticate, come la distanza di Levenshtein.
[modifica] Bibliografia
Adattato in parte da Federal Standard 1037C.
Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.
[modifica] Voci correlate
- Codice di Hamming
- Distanza di Levenshtein, una generalizzazione della distanza di Hamming
