Distância de Hamming
Na teoria da informação, a distância de Hamming entre duas strings de mesmo comprimento é o número de posições nas quais elas diferem entre si. Vista de outra forma, ela corresponde ao menor número de substituições necessárias para transformar uma string na outra, ou o número de erros que transformaram uma na outra.
 |
 |
 | |
 | |
História e aplicações editar
A distância de Hamming é assim chamada em homenagem a Richard Hamming, que introduziu o conceito em um artigo fundamental sobre códigos de Hamming Error detecting and error correcting codes em 1950.[1] Nas telecomunicações, ela é utilizada para sinalizar erros na transmissão de palavras binárias de comprimento fixo entre um emissor e um receptor, e por isso é algumas vezes chamada de "distância do sinal". Esta forma de análise de bits é usada em várias disciplinas incluindo a teoria da informação, a teoria de códigos e a criptografia. No entanto, para comparar strings de tamanhos diferentes, ou nas quais não apenas substituições mas também inserções e remoções devem ser esperadas, é mais apropriado usar uma métrica mais sofisticada como a distância de Levenshtein.
Para strings q-árias sobre um alfabeto de tamanho q ≥ 2 a distância de Hamming é aplicada no caso da modulação ortogonal, enquanto a distância de Lee é usada para modulação de fase. Se q = 2 ou q = 3 ambas as distâncias coincidem
A distância de Hamming também é usada em sistemática como uma medida da distância genética.[2]
Em uma grade (tal como um tabuleiro de xadrez), os pontos a uma distância de Lee de 1 unidade constituem uma vizinhança de Von Neumann de tal ponto.
Propriedades especiais editar
Para um comprimento n fixado, a distância de Hamming é uma métrica no espaço vetorial das palavras daquele comprimento, uma vez que ela obviamente cumpre as condições de ser não negativa, de distinguir apenas palavras que sejam distintas e de simetria, e pode-se mostrar facilmente por indução completa que ela também verifica a desigualdade triangular. A distância de Hamming entre duas palavras a e b também pode ser vista como o peso de Hamming de a − b escolhendo-se o operador − adequadamente.
Para strings binárias a e b, a distância de Hamming é igual ao número de uns em a XOR b. O espaço métrico das strings binárias de comprimento n, com a métrica de Hamming é conhecido como cubo de Hamming; ele é equivalente como espaço métrico ao conjunto das distâncias entre vértices em um grafo hipercubo. Também é possível interpretar uma string binária de comprimento n como um vetor em tratando cada símbolo da string como uma coordenada real; com essa imersão, as strings formam os vértices de um hipercubo de dimensão n, e a distância de Hamming entre as strings é equivalente à métrica do taxi entre os vértices.
Exemplos editar
A distância de Hamming entre:
- "elabore" e "melhore" é 4.
- 2173896 e 2233796 é 3.
- 11011 e 10011 é 1.
Neste terceiro exemplo, se a cadeia de bits A(11011) fosse emitida e chegasse ao receptor como A'(10011), poderia ser usada a operação XOR da seguinte maneira:
- 11011
- XOR 10011
- 01000
A quantidade de bits encontrados nessa operação, é a Distância de Hamming entre a palavra transmitida e a recebida. Deste modo, conclui-se que a distância de Hamming entre as strings do exemplo é 1, pois apenas 1 bit foi encontrado após a operação XOR.
Usa-se normalmente esta teoria nos mapas de Karnaugh, servindo para simplificar expressões algébricas usadas para a construção de circuitos.
Algoritmo de exemplo editar
A função Python hamming_distance() calcula a distância de Hamming entre duas strings (ou outros objetos iteráveis) de mesmo comprimento, criando uma sequência de a zeros e uns indicando diferenças e correspondências entre as posições correspondentes das duas entradas, e então somando a sequência.
- Python
def hamming_distance(s1, s2):
assert len(s1) == len(s2)
return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
A seguinte função C calculará a distância de Hamming entre dois inteiros (considerados como valores binários, isto é, como sequências de zeros e uns). O tempo de execução deste procedimento é proporcional à distância de Hamming em vez do número de bits nas entradas. Ela calcula o ou exclusivo bit a bit entre as duas entradas, e então determina o peso de Hamming do resultado (o número de bits não nulos) usando um algoritmo de Wegner (1960) que repetidamente procura e limpa o bit não nulo de menor ordem.
- C
unsigned hamdist(unsigned x, unsigned y)
{
unsigned dist = 0, val = x ^ y;
// Count the number of set bits
while(val)
{
++dist;
val &= val - 1;
}
return dist;
}
- Matlab / Octave
function [dist] = hamdist(x, y)
dist = x ~= y;
end
Ver também editar
Notas editar
Referências editar
- O artigo em inglês, a partir do qual parte deste foi traduzido, incorporava material em domínio público do documento da Administração dos Serviços Gerais "Federal Standard 1037C".
- Hamming, Richard W. (1950), «Error detecting and error correcting codes» 🔗 (PDF), Bell System Technical Journal, 29 (2): 147–160, MR 0035935, consultado em 11 de outubro de 2010, cópia arquivada (PDF) em 25 de maio de 2006
- HEFEZ, Abramo; VILLELA, Maria Lúcia T. (2002). Códigos Corretores de Erros. Rio de Janeiro: IMPA
- Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (março de 2008), «Inferring HIV transmission dynamics from phylogenetic sequence relationships», PLoS Med., 5 (3): e69, PMC 2267810
, PMID 18351799, doi:10.1371/journal.pmed.0050069. - Roman, Steven (1997). Introduction to Coding and Information Theory. [S.l.]: Springer. ISBN 0-387-94704-3
- Tanenbaum, Andrew S.. Redes de Computadores. 4ªEd. Ed. Elsevier
- Wegner, Peter (1960), «A technique for counting ones in a binary computer», Communications of the ACM, 3 (5): 322, doi:10.1145/367236.367286
Ligações externas editar
- Exemplo de distância de Hamming (em inglês)
- Hamming Code Tool Ferramenta para gerar códigos de Hamming
- set_matcher Ferramenta para comparar duas famílias de conjuntos a partir da mesma população base usando a distância de Hamming.