Distancia de Hamming
En teoría de la información , la distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que los símbolos correspondientes son diferentes. En otras palabras, mide el número mínimo de sustituciones necesarias para cambiar una cadena por otra, o la cantidad mínima de errores que podrían haber transformado una cadena en otra. En un contexto más general, la distancia de Hamming es una de varias métricas de cadena para medir la distancia de edición entre dos secuencias. Lleva el nombre del matemático estadounidense Richard Hamming .
Una aplicación importante es la teoría de la codificación , más específicamente para los códigos de bloque , en los que las cadenas de igual longitud son vectores sobre un campo finito .
La distancia de Hamming entre dos cadenas de símbolos de igual longitud es el número de posiciones en las que los símbolos correspondientes son diferentes. [1]
Los símbolos pueden ser letras, bits o dígitos decimales, entre otras posibilidades. Por ejemplo, la distancia de Hamming entre:
Para una longitud fija n , la distancia de Hamming es una métrica del conjunto de palabras de longitud n (también conocida como espacio de Hamming ), ya que cumple las condiciones de no negatividad, simetría, la distancia de Hamming de dos palabras es 0 si y solo si las dos palabras son idénticas, y también satisface la desigualdad del triángulo : [2] De hecho, si fijamos tres palabras a , byc , entonces siempre que haya una diferencia entre la i -ésima letra de ay la i -ésima letra de c, entonces debe haber una diferencia entre la i - ésima letra de ay la i - ésima letra de b , o entre la i -ésima letra de by la i -ésima letra de c . Por tanto , la distancia de Hamming entre ayc no es mayor que la suma de las distancias de Hamming entre ayby entre by c . La distancia de Hamming entre dos palabras ayb también puede verse como el peso de Hamming de a - bpara una elección adecuada del operador -, la diferencia entre dos números enteros puede verse como una distancia desde cero en la recta numérica. [ aclaración necesaria ]
Para cadenas binarias ayb , la distancia de Hamming es igual al número de unos ( recuento de población ) en un XOR b . [3] El espacio métrico de longitudes n cadenas binarias, con la distancia de Hamming, se conoce como el cubo de Hamming ; es equivalente como espacio métrico al conjunto de distancias entre vértices en un gráfico de hipercubo . También se puede ver una cadena binaria de longitud n como un vector en tratando cada símbolo en la cadena como una coordenada real; con esta incrustación, las cadenas forman los vértices de un hipercubo n -dimensional , y la distancia de Hamming de las cuerdas es equivalente a la distancia de Manhattan entre los vértices.
