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

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

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 ${\displaystyle R^{n}}$ 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

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

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

• Código de Hamming
• Distância de Levenshtein

Notas

Referências

• 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

• 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.