Distancia de Hamming

La distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que sus símbolos difieren. Es una forma directa de medir cuánto se parecen dos secuencias del mismo tamaño: cuanto menor es la distancia, más se parecen. Por ejemplo, entre las cadenas binarias 1011101 y 1001001 los símbolos coinciden en cinco posiciones y difieren en dos —la tercera y la quinta—, de modo que su distancia de Hamming es 2.

Aunque el ejemplo clásico usa bits, la definición vale para cualquier alfabeto: entre las palabras «casa» y «cara» hay una sola posición distinta, así que su distancia es 1. Matemáticamente es una métrica en sentido estricto: nunca es negativa, vale cero solo cuando las cadenas son idénticas, es simétrica y cumple la desigualdad triangular. Esa condición de métrica es la que la hace fiable para comparar, ordenar y agrupar datos.

Origen: Hamming y los códigos correctores de errores

La medida la introdujo el matemático Richard Hamming en 1950, en su artículo «Error Detecting and Error Correcting Codes», publicado en el Bell System Technical Journal. Hamming trabajaba en los Laboratorios Bell y buscaba que una máquina detectara y corrigiera por sí misma los errores que aparecían al transmitir o almacenar datos. Su idea central sigue vigente: la distancia mínima de un código —la menor distancia de Hamming entre dos de sus palabras válidas— determina su capacidad de protección. Un código con distancia mínima d puede detectar hasta d−1 errores y corregir hasta la parte entera de (d−1)/2. Por eso los códigos de Hamming y sus descendientes están hoy en memorias, discos y comunicaciones digitales.

Usos en inteligencia artificial

En aprendizaje automático la distancia de Hamming aparece siempre que los datos se representan como cadenas binarias de longitud fija. Sirve para comparar huellas y hashes binarios: dos huellas cercanas en distancia de Hamming corresponden a objetos parecidos. Es la base de la búsqueda de vecinos más cercanos sobre representaciones binarias, donde se recupera el elemento cuya huella difiere en menos posiciones. También sustenta el hashing sensible a la localidad (LSH), una familia de técnicas que agrupa elementos similares en el mismo «cubo» para buscar entre millones de registros sin comparar todos con todos. Su cálculo es muy rápido —un XOR y un recuento de bits—, lo que la hace ideal para grandes volúmenes.

Frente a la distancia de edición

Conviene no confundir la distancia de Hamming con la distancia de edición o de Levenshtein, formalizada por Vladimir Levenshtein en 1966. La de Hamming solo cuenta sustituciones y exige que ambas cadenas midan lo mismo; la de Levenshtein permite además insertar y borrar símbolos, por lo que compara cadenas de longitudes distintas. Para «casa» y «cara» ambas dan 1, pero para «casa» y «asa» la de Levenshtein da 1 —un borrado— mientras que la de Hamming ni siquiera se define, porque las longitudes no coinciden. Elegir una u otra depende de si los datos tienen tamaño fijo o pueden desplazarse.