distancia de hamming
En la 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 el número mínimo 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 en la teoría de la codificación , más específicamente en 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 sobre el conjunto de las palabras de longitud n (también conocido 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] En efecto, si fijamos tres palabras a , b y c , entonces siempre que haya una diferencia entre la i -ésima letra de a y la i ésima letra de c, entonces debe haber una diferencia entre la i -ésima letra de a y la i -ésima letra de b , o entre la i -ésima letra de b y la i -ésima letra de c . Por lo tanto, la distancia de Hamming entre a y c no es mayor que la suma de las distancias de Hamming entre a y b y entre b y c . La distancia de Hamming entre dos palabras a y b también se puede ver como el peso de Hamming de a − bpara una elección adecuada del operador −, tanto como la diferencia entre dos enteros puede verse como una distancia desde cero en la recta numérica. [ aclaración necesaria ]
Para las 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 longitud- n cadenas binarias, con la distancia de Hamming, se conoce como cubo de Hamming ; equivale 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 tratando cada símbolo de la cadena como una coordenada real; con esta incrustación, las cuerdas forman los vértices de un hipercubo de n dimensiones , y la distancia de Hamming de las cuerdas es equivalente a la distancia de Manhattan entre los vértices.
