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 .
| ||
Clase | Similitud de cadenas | |
---|---|---|
Estructura de datos | cuerda | |
Rendimiento en el peor de los casos | ||
Rendimiento en el mejor de los casos | ||
Rendimiento medio | ||
Complejidad espacial en el peor de los casos |
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 .
Definición
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]
Ejemplos de
Los símbolos pueden ser letras, bits o dígitos decimales, entre otras posibilidades. Por ejemplo, la distancia de Hamming entre:
- " ka rol in " y " ka thr in " es 3.
- " k a r ol in " y " k e r st in " es 3.
- " k athr in " y " k erst in " es 4.
- 10 1 1 1 01 y 10 0 1 0 01 es 2.
- 2 17 3 8 96 y 2 23 3 7 96 es 3.
Propiedades
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 sólo si las dos palabras son idénticos, y se satisface la desigualdad del triángulo , así: [2] en efecto, si fijamos tres palabras un , b y c , a continuación, cada vez que hay una diferencia entre el i ésimo carta de una y la i ésimo carta de c , entonces debe haber una diferencia entre el i ésimo carta de una y i ésimo carta de b , o entre el i ésimo carta de b y el i ésimo carta de c . Por lo tanto la distancia de Hamming entre un y c no es mayor que la suma de las distancias de Hamming entre un y b y entre b y c . La distancia de Hamming entre dos palabras un y b también puede ser visto como el peso de Hamming de una - b para una elección apropiada de la - operador, tanto como la diferencia entre dos números enteros puede ser visto como una distancia de cero en la línea número. [ aclaración necesaria ]
Para cadenas binarias una y b la distancia de Hamming es igual al número de unos ( recuento de la población ) en un XOR b . [3] El espacio métrico de longitud 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 entratando cada símbolo de la cadena como una coordenada real; con esta incrustación, las cuerdas 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.
Detección y corrección de errores
La distancia mínima de Hamming se utiliza para definir algunas nociones esenciales en la teoría de la codificación , como los códigos de detección y corrección de errores . En particular, se dice que un código C es un error k que detecta si, y solo si, la distancia de Hamming mínima entre dos de sus palabras de código es al menos k +1. [2]
Por ejemplo, considere el código que consta de dos palabras de código "000" y "111". La distancia de martillo entre estas dos palabras es 3 y, por lo tanto, es k = 2 detección de errores. Lo que significa que si se invierte un bit o se invierten dos bits, se puede detectar el error. Si se invierten tres bits, "000" se convierte en "111" y no se puede detectar el error.
Se dice que un código C tiene k errores de corrección si, para cada palabra w en el espacio de Hamming subyacente H , existe como máximo una palabra de código c (de C ) tal que la distancia de Hamming entre w y c sea como máximo k . En otras palabras, un código es k -errores corrigiendo si, y solo si, la distancia mínima de Hamming entre dos de sus palabras de código es al menos 2 k +1. Esto se entiende más fácilmente geométricamente, ya que cualquier bola cerrada de radio k centrada en distintas palabras de código está disjunta. [2] Estas bolas también se denominan esferas de Hamming en este contexto. [4]
Por ejemplo, considere el mismo código de 3 bits que consta de dos palabras de código "000" y "111". El espacio de Hamming consta de 8 palabras 000, 001, 010, 011, 100, 101, 110 y 111. La palabra de código "000" y las palabras de error de un solo bit "001", "010", "100" son todas menores que o igual a la distancia de Hamming de 1 a "000". Asimismo, la palabra de código "111" y sus palabras de error de un solo bit "110", "101" y "011" están todas dentro de 1 distancia de Hamming del "111" original. En este código, un error de un solo bit siempre está dentro de la distancia de 1 Hamming de los códigos originales, y el código puede corregir 1 error , es decir, k = 1 . La distancia mínima de Hamming entre "000" y "111" es 3, lo que satisface 2k + 1 = 3 .
Por lo tanto, un código con una distancia de Hamming mínima d entre sus palabras de código puede detectar como máximo d -1 errores y puede corregir errores ⌊ ( d -1) / 2⌋. [2] Este último número también se denomina radio de empaquetamiento o capacidad de corrección de errores del código. [4]
Historia y aplicaciones
La distancia de Hamming es el nombre de Richard Hamming , que introdujo el concepto en su papel fundamental en los códigos de Hamming , detección de errores y códigos de corrección de errores , en 1950. [5] análisis del peso de Hamming de bits se utiliza en varias disciplinas, incluyendo la teoría de la información , teoría de la codificación y criptografía .
Se utiliza en telecomunicaciones para contar el número de bits invertidos en una palabra binaria de longitud fija como una estimación del error y, por lo tanto, a veces se denomina distancia de señal . [6] Para cadenas q -ary sobre un alfabeto de tamaño q ≥ 2, la distancia de Hamming se aplica en el caso del canal q-ary simétrico , mientras que la distancia Lee se usa para codificación por desplazamiento de fase o, más generalmente, canales susceptibles a errores de sincronización. porque la distancia de Lee explica errores de ± 1. [7] Si o ambas distancias coinciden porque cualquier par de elementos de o difieren en 1, pero las distancias son diferentes para mayores .
La distancia de Hamming también se usa en sistemática como una medida de distancia genética. [8]
Sin embargo, para comparar cadenas de diferentes longitudes, o cadenas donde no solo se deben esperar sustituciones sino también inserciones o eliminaciones, una métrica más sofisticada como la distancia de Levenshtein es más apropiada.
Ejemplo de algoritmo
La siguiente función, escrita en Python 3, devuelve la distancia de Hamming entre dos cadenas:
def hamming_distance ( cadena1 , cadena2 ): dist_counter = 0 para n en gama ( len ( cadena1 )): si cadena1 [ n ] ! = string2 [ n ]: dist_counter + = 1 retorno dist_counter
O, en una expresión más corta:
suma ( xi ! = yi para xi , yi en zip ( x , y ))
La función hamming_distance()
, implementada en Python 2.3+ , calcula la distancia de Hamming entre dos cadenas (u otros objetos iterables ) de igual longitud creando una secuencia de valores booleanos que indican discrepancias y coincidencias entre las posiciones correspondientes en las dos entradas y luego sumando la secuencia con Falso y los valores verdaderos se interpretan como cero y uno.
def hamming_distance ( s1 , s2 ) -> int : "" "Devuelve la distancia de Hamming entre secuencias de igual longitud." "" if len ( s1 ) ! = len ( s2 ): raise ValueError ( "Indefinido para secuencias de longitud desigual. " ) devuelve la suma ( el1 ! = el2 para el1 , el2 en zip ( s1 , s2 ))
donde la función zip () fusiona dos colecciones de igual longitud en pares.
La siguiente función C calculará la distancia de Hamming de dos enteros (considerados como valores binarios, es decir, como secuencias de bits). El tiempo de ejecución de este procedimiento es proporcional a la distancia de Hamming más que al número de bits en las entradas. Calcula el bit a bit exclusivo o de las dos entradas, y luego encuentra el peso de Hamming del resultado (el número de bits distintos de cero) utilizando un algoritmo de Wegner (1960) que encuentra y borra repetidamente el bit distinto de cero de orden más bajo. Algunos compiladores admiten la función __builtin_popcount que puede calcular esto utilizando hardware de procesador especializado cuando esté disponible.
int hamming_distance ( sin signo x , sin signo y ) { int dist = 0 ; // Los operadores ^ establecen en 1 solo los bits que son diferentes para ( unsigned val = x ^ y ; val > 0 ; ++ dist ) { // Luego contamos el bit establecido en 1 usando la forma de Peter Wegner val = val & ( val - 1 ); // Establecer en cero el orden más bajo de val 1 } // Devuelve el número de bits diferentes return dist ; }
Una alternativa más rápida es utilizar la instrucción de ensamblaje de conteo de población ( popcount ). Ciertos compiladores como GCC y Clang lo hacen disponible a través de una función intrínseca:
// Distancia de Hamming para enteros de 32 bits int hamming_distance32 ( unsigned int x , unsigned int y ) { return __builtin_popcount ( x ^ y ); }// Distancia de Hamming para enteros de 64 bits int hamming_distance64 ( unsigned long long x , unsigned long long y ) { return __builtin_popcountll ( x ^ y ); }
Ver también
- Cadena más cercana
- Distancia Damerau-Levenshtein
- distancia euclidiana
- Problema de Gap-Hamming
- Código gris
- Índice de Jaccard
- Distancia de Levenshtein
- Distancia de Mahalanobis
- Distancia de Mannheim
- Índice de similitud de Sørensen
- Memoria distribuida escasa
- Escalera de palabra
Referencias
- ^ Waggener, Bill (1995). Técnicas de modulación de código de pulso . Saltador. pag. 206. ISBN 9780442014360. Consultado el 13 de junio de 2020 .
- ^ a b c d Robinson, Derek JS (2003). Una introducción al álgebra abstracta . Walter de Gruyter . págs. 255-257. ISBN 978-3-11-019816-4.
- ^ Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. págs. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
- ^ a b Cohen, G .; Honkala, I .; Litsyn, S .; Lobstein, A. (1997), Covering Codes , North-Holland Mathematical Library, 54 , Elsevier , págs. 16-17, ISBN 9780080530079
- ^ Hamming, RW (abril de 1950). "Códigos de detección y corrección de errores" (PDF) . Revista técnica de Bell System . 29 (2): 147–160. doi : 10.1002 / j.1538-7305.1950.tb00463.x . ISSN 0005-8580 .
- ^ Ayala, José (2012). Diseño de sistemas y circuitos integrados . Springer . pag. 62. ISBN 978-3-642-36156-2.
- ^ Roth, Ron (2006). Introducción a la teoría de la codificación . Prensa de la Universidad de Cambridge . pag. 298. ISBN 978-0-521-84504-5.
- ^ Pilcher, Christopher D .; Wong, Joseph K .; Pillai, Satish K. (18 de marzo de 2008). "Inferir la dinámica de transmisión del VIH a partir de relaciones de secuencia filogenética" . PLOS Medicine . 5 (3): e69. doi : 10.1371 / journal.pmed.0050069 . ISSN 1549-1676 . PMC 2267810 . PMID 18351799 .
Otras lecturas
- Este artículo incorpora material de dominio público del documento de la Administración de Servicios Generales : "Norma Federal 1037C" .
- Wegner, Peter (1960). "Una técnica para contar unos en una computadora binaria". Comunicaciones de la ACM . 3 (5): 322. doi : 10.1145 / 367236.367286 . S2CID 31683715 .
- MacKay, David JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge: Cambridge University Press . ISBN 0-521-64298-1.