Distancia Hamming entre dos cadenas iguales con repetición.

Question

La distancia Hamming entre dos cadenas de igual longitud es el número de caracteres que son diferentes entre sí, en la misma posición, entre dos cadenas de igual longitud. También se puede decir que es el número de "ediciones" que hay que hacer para cambiar una cadena por la otra. Por ejemplo, si tenemos $s_1=\text{Anna}$ y $s_2=\text{Sara}$ entonces la distancia de Hamming es $3$ o si tenemos $s_3=\text{Casablanca}$ y $s_4=\text{Blackjacks}$ entonces la distancia Hamming sería $9$ . Pero qué pasa si tenemos el siguiente ejemplo: $s_5=\text{Google}$ y $s_6=\text{Baangs}$ . Si hacemos los siguientes cambios: $\text{G} \to \text{B}, \text{o} \to \text{a}, \text{g} \to \text{n}, \text{l} \to \text{g}, \text{e} \to \text{s}$ lo que da una distancia Hamming de $5$ pero si se tiene en cuenta el número de posiciones en las que los caracteres son diferentes, obtenemos $6$ .

Mi pensamiento inicial aquí es que sólo se nos permite cambiar un carácter a la vez, por lo que cuando cambiamos un $\text{o}$ a un $\text{a}$ Sólo hemos cambiado uno de los $\text{o's}$ y tenemos que hacerlo de nuevo para el segundo $\text{o}$ .

Answer 1

Es $6$ en ese caso. Un ejemplo aún mejor sería la distancia de Hamming entre las palabras binarias. En este caso, sólo tenemos $1$ y $0$ por lo que si las cosas fueran como tú dices, la distancia de Hamming entre dos palabras binarias sería como máximo $2$ ( $0$ 's a $1$ y $1$ 's a $0$ 's). Pero está claro que este no es el caso.

Para evitar este tipo de confusión, podemos definir la distancia de Hamming entre dos cadenas con la misma longitud $S_1 = a_1a_2...a_n$ y $S_2 = b_1b_2...b_n$ como el tamaño del conjunto de índices donde los caracteres difieren. Matemáticamente, podemos escribir

$$d(S_1,S_2) = |\{i|a_i \ne b_i\}|$$