Distancia de Hamming
La distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que sus caracteres no coinciden.
Dicho de otro modo, mide cuántas sustituciones mínimas son necesarias para transformar una cadena en la otra.
Si tomamos dos cadenas \( s \) y \( t \) de longitud \( n \), la distancia de Hamming \( D_H(s, t) \) se define como:
$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$
Donde \( s_i \) y \( t_i \) representan los caracteres en la posición \( i \) de las cadenas \( s \) y \( t \), y \( \delta(s_i, t_i) \) es una función que vale 1 cuando \( s_i \neq t_i \), y 0 en caso contrario.
La distancia de Hamming solo está definida para cadenas de la misma longitud \( n \).
Un ejemplo práctico
Consideremos las siguientes cadenas:
$$ s = \text{"karbon"} $$
$$ t = \text{"carbon"} $$
La distancia de Hamming entre \( s \) y \( t \) es 1, ya que solo difieren en la primera letra (k frente a c).
Ejemplo 2
Otro ejemplo de palabras en inglés con una distancia de Hamming igual a 2:
$$ s = \text{"thing"} $$
$$ t = \text{"thank"} $$
Estas cadenas difieren en dos posiciones:
En la tercera letra, “i” en “thing” frente a “a” en “thank”, y en la quinta, “g” frente a “k”.
Topología métrica basada en la distancia de Hamming
La distancia de Hamming define un espacio métrico, ya que satisface las siguientes propiedades para cualquier trío de cadenas \( x \), \( y \) y \( z \) de la misma longitud:
- No negatividad
$$ D_H(x, y) \geq 0 \quad \text{y} \quad D_H(x, y) = 0 \ \text{si y solo si} \ x = y $$
La distancia de Hamming nunca es negativa, ya que cuenta diferencias. Además, vale cero únicamente cuando ambas cadenas son idénticas. - Simetría
$$ D_H(x, y) = D_H(y, x) $$
La distancia es simétrica, porque comparar \( x \) con \( y \) produce el mismo resultado que comparar \( y \) con \( x \). - Desigualdad triangular
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
Para cualquier trío de cadenas, la distancia directa entre \( x \) y \( z \) nunca supera la suma de las distancias \( D_H(x, y) + D_H(y, z) \). Esto se debe a que toda diferencia entre \( x \) y \( z \) debe aparecer en al menos uno de los dos tramos intermedios.
Como cumple estas propiedades, la distancia de Hamming define un espacio métrico sobre el conjunto de cadenas de longitud fija.
En estos espacios, es posible construir una topología basada en la noción de cercanía definida por la métrica.
En particular, la distancia de Hamming permite definir una topología métrica.
Para cualquier cadena \( x \) de longitud \( n \) y un radio \( r \), se define una “bola abierta” (o entorno) $ B $ centrada en \( x \) como el conjunto de cadenas cuya distancia de Hamming respecto a \( x \) sea menor que \( r \):
$$ B(x, r) = \{y \mid D_H(x, y) < r\}. $$
Estas bolas abiertas forman una base para la topología métrica, ya que cualquier conjunto abierto se puede construir como unión arbitraria de ellas.
Nota. Como el conjunto de todas las cadenas binarias (o cadenas de símbolos) de longitud \( n \) es finito, la topología inducida por la distancia de Hamming sobre dicho conjunto es la topología discreta. En efecto, cada cadena puede considerarse simultáneamente como conjunto abierto y cerrado, ya que basta elegir un radio muy pequeño (por ejemplo, \( r = 1 \)) para obtener una bola abierta que contenga exclusivamente esa cadena.
Por tanto, la distancia de Hamming genera una topología métrica que, en conjuntos finitos de cadenas de igual longitud, es discreta.
Ejemplo
Consideremos el conjunto de algunas cadenas binarias de longitud tres:
$$ X = \{000, 001, 011, 110, 111 \} $$
La topología inducida por la distancia de Hamming con radio \( r = 2 \) se obtiene examinando las bolas abiertas de radio 2 centradas en cada elemento:
$$ B(x, r) = \{y \mid D_H(x, y) < 2 \} $$
Es decir, cada conjunto abierto está formado por las cadenas que difieren de la cadena central en exactamente una posición.
- Bola abierta centrada en \( 000 \): $$ B(000, 2) = \{000, 001\} $$ Solo \( 001 \) difiere de \( 000 \) en una posición.
- Bola abierta centrada en \( 001 \): $$ B(001, 2) = \{001, 000, 011 \} $$ Las cadenas \( 000 \) y \( 011 \) difieren de \( 001 \) en una posición.
- Bola abierta centrada en \( 011 \): $$ B(011, 2) = \{011, 001, 111\} $$ Las cadenas \( 001 \) y \( 111 \) están a una distancia de 1 de \( 011 \).
- Bola abierta centrada en \( 110 \): $$ B(110, 2) = \{110, 111\} $$ Solo \( 111 \) está a una posición de diferencia respecto a \( 110 \).
- Bola abierta centrada en \( 111 \): $$ B(111, 2) = \{111, 011, 110\} $$ \( 011 \) y \( 110 \) son las cadenas más próximas a \( 111 \).
Estas bolas definen la base de la topología inducida para el radio \( r = 2 \), ya que permiten generar otros conjuntos abiertos mediante sus uniones.
Nota. Un radio \( r = 2 \) implica que las cadenas difieren en una sola posición, ya que en una “bola abierta” no se incluyen los puntos frontera. Por eso usamos la desigualdad estricta $$ B(x, r) = \{ y \mid D_H(x, y) < 2 \} $$. En cambio, para definir conjuntos cerrados se usaría la desigualdad no estricta: $$ C(x, r) = \{ y \mid D_H(x, y) \le 2 \} $$
Por ejemplo, la unión de las bolas \( B(000, 2) \) y \( B(110, 2) \) es:
$$ B(000, 2) \cup B(110, 2) $$
Como sabemos que $ B(000, 2) = \{000, 001\} $ y $ B(110, 2) = \{110, 111\} $, su unión es:
$$ B(000, 2) \cup B(110, 2) = \{000, 001, 110, 111\} $$
Así, en esta topología, el conjunto $ \{000, 001, 110, 111\} $ es también un conjunto abierto.
En conclusión, este sistema define una topología métrica basada en la distancia de Hamming con radio \( r = 2 \), en la cual cada conjunto abierto se construye como unión de bolas abiertas de ese radio.
Y así sucesivamente.
