Distância de Hamming
A distância de Hamming entre duas cadeias de mesmo comprimento é o número de posições em que os seus símbolos diferem.
De forma simples, ela indica quantas substituições são necessárias para transformar uma cadeia na outra.
Sejam \( s \) e \( t \) duas cadeias de comprimento \( n \). A distância de Hamming \( D_H(s, t) \) é definida por:
$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$
onde \( s_i \) e \( t_i \) representam os símbolos na posição \( i \), e \( \delta(s_i, t_i) \) vale 1 quando os símbolos são diferentes e 0 quando são iguais.
Essa distância só está definida para cadeias de mesmo comprimento.
Exemplo
Considere as cadeias:
$$ s = \text{"karbon"} $$
$$ t = \text{"carbon"} $$
A distância de Hamming é 1, pois elas diferem apenas na primeira posição.
Exemplo 2
Outro exemplo:
$$ s = \text{"thing"} $$
$$ t = \text{"thank"} $$
Nesse caso, a distância é 2, porque há diferenças na terceira e na quinta posições.
Uma distância que define um espaço métrico
A distância de Hamming não é apenas uma forma de comparar cadeias. Ela também define um espaço métrico, pois satisfaz três propriedades fundamentais:
- Não negatividade
$$ D_H(x, y) \geq 0 \quad \text{e} \quad D_H(x, y) = 0 \ \text{se, e somente se,} \ x = y $$
A distância nunca é negativa e só é zero quando as cadeias são idênticas. - Simetria
$$ D_H(x, y) = D_H(y, x) $$
Comparar \( x \) com \( y \) produz o mesmo resultado que comparar \( y \) com \( x \). - Desigualdade triangular
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
A distância direta entre duas cadeias nunca é maior do que a soma das distâncias intermediárias.
Por satisfazer essas propriedades, a distância de Hamming permite definir uma topologia métrica.
Bolas abertas e vizinhança
Em um espaço métrico, a noção de proximidade é descrita por meio de bolas abertas.
Dada uma cadeia \( x \) e um raio \( r \), define-se a bola aberta centrada em \( x \) como:
$$ B(x, r) = \{y \mid D_H(x, y) < r\}. $$
Esse conjunto contém todas as cadeias que diferem de \( x \) em menos de \( r \) posições.
Essas bolas formam a base da topologia, pois qualquer conjunto aberto pode ser obtido como união dessas bolas.
Observação. Quando o conjunto de cadeias é finito, como no caso de cadeias binárias de comprimento fixo, a topologia induzida pela distância de Hamming é a topologia discreta. Isso significa que cada cadeia é, ao mesmo tempo, um conjunto aberto e fechado.
Exemplo com cadeias binárias
Considere o conjunto:
$$ X = \{000, 001, 011, 110, 111 \} $$
Tomando um raio \( r = 2 \), a bola aberta centrada em \( x \) contém todas as cadeias que diferem de \( x \) em no máximo uma posição (pois a desigualdade é estrita).
- Centro \( 000 \): $$ B(000, 2) = \{000, 001\} $$
- Centro \( 001 \): $$ B(001, 2) = \{001, 000, 011 \} $$
- Centro \( 011 \): $$ B(011, 2) = \{011, 001, 111\} $$
- Centro \( 110 \): $$ B(110, 2) = \{110, 111\} $$
- Centro \( 111 \): $$ B(111, 2) = \{111, 011, 110\} $$
Essas bolas constituem a base da topologia induzida para esse raio.
Observação. A condição \( D_H(x, y) < 2 \) implica diferença em apenas uma posição. Se utilizássemos \( \leq 2 \), incluiríamos também as cadeias a distância exatamente igual a 2, obtendo conjuntos fechados.
Por exemplo:
$$ B(000, 2) \cup B(110, 2) = \{000, 001, 110, 111\} $$
Esse conjunto é aberto na topologia induzida.
Em resumo, a distância de Hamming não apenas mede diferenças entre cadeias, mas também estrutura um espaço topológico no qual a noção de proximidade é claramente definida.
E assim por diante.
