Codificación de Huffman: ¿por qué no hay necesidad de un separador?

17 
Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Texto original:

Ojos misteriosos vistos cerca del lago

Codificado:
0000101100000110011100010101101101001111101011111100011001111110100100101

¿Por qué no hay necesidad de un separador en la codificación de Huffman?

coding-theory encoding-scheme huffman-coding BufBills
fuente
1
Porque cuando decodifica un valor binario, toma el fragmento de bits "de izquierda a derecha", lo que primero coincida con el valor del texto original. Al igual que en este caso, verá que el fragmento más a la izquierda (0000) coincide con E. Si hubiera algún símbolo con un valor de 000 en su código de caracteres, reemplazaría el 000 con ese símbolo y luego comenzaría a buscar nuevamente desde los bits restantes en una manera de "izquierda a derecha". Es por eso que no necesitas ninguna separación.
Syed Ali Hamza
1
La pregunta implica que generalmente se necesitan separadores. Ya sabes que no necesitas separadores Eerie eyes seen near lake(bueno, excepto el carácter de espacio). Pero los personajes en sí no necesitan separadores. ¿Por qué no es eso?
MSalters
intente decodificarlo usted mismo, nunca hay ambigüedad.
njzk2
@MSalters: Pero separadores son generalmente necesarios con las palabras de longitud variable: cat cheat for mice≠ catch eat form ice. Su analogía es defectuosa: cada letra es atómica; Las letras son trivialmente distinguidas e intrínsecamente separables. Una mejor analogía sería "¿Por qué puedes leer un guión cursivo (escrito a mano), cuando cada palabra es solo una línea larga, ondulada y auto intersectada?", E incluso esa es una analogía pobre, ya que puedes ver una palabra escrita a mano ( o incluso una parte de uno) y discernir las letras individuales, mientras que una cadena codificada por Huffman es un galimatías si no puede ver el comienzo.
G-Man dice 'Restablecer a Monica' el
@MSalters No veo tu punto. No necesito separadores para los caracteres porque estamos usando una codificación de ancho fijo: cada bloque sucesivo de ocho bits corresponde a un carácter. Pero la codificación de Huffman no es de ancho fijo, de ahí la pregunta.
David Richerby

Respuestas:

50

No necesita un separador porque los códigos de Huffman son códigos sin prefijo (también, inútilmente, conocidos como "códigos de prefijo"). Esto significa que ninguna palabra de código es un prefijo de ninguna otra palabra de código. Por ejemplo, la palabra de código para "e" en su ejemplo es 10, y puede ver que ninguna otra palabra de código comienza con los dígitos 10.

Esto significa que puede decodificar codiciosamente leyendo la cadena codificada de izquierda a derecha y generando un carácter tan pronto como haya visto una palabra de código. Por ejemplo, 0, 00 y 000 no codifican nada, así que sigue leyendo bits. Cuando lee 0000, eso codifica "E" y, dado que el código no tiene prefijo, sabe que no hay otra palabra de código 0000x, por lo que ahora puede generar "E" y comenzar a leer la siguiente palabra de código. Nuevamente, 1 no codifica nada pero 10 codifica "e". Ninguna otra palabra de código comienza con "10", por lo que puede generar "e". Y así.

David Richerby
fuente
1
Los códigos de prefijo también se conocen comúnmente como códigos instantáneos (véase, por ejemplo, Elementos de la teoría de la información de Cover & Thomas). Creo que el término código de prefijo aparece con mucha más frecuencia que el código sin prefijo.
Batman el
3
También vale la pena mencionar que para decodificar una secuencia de códigos Huffman concatenados, uno debe recibir el límite de palabra de código correcto para comenzar. Si uno intenta decodificar la secuencia en un límite de palabra de código incorrecto, el proceso de decodificación generará una secuencia incorrecta de símbolos de salida.
rwong
@rwong: si el código Huffman comienza sincronizado incorrectamente, puede continuar emitiendo símbolos incorrectos indefinidamente, pero cada vez que determina incorrectamente la longitud de un símbolo, se reducirá el número de posibles estados incorrectos.
supercat
@supercat Supongo que lo expresaría de una manera diferente: si un decodificador Huffman se configura inicialmente en un límite de palabra de código incorrecto y comienza a procesarse, existe la posibilidad (que puede ser cero o algo así y puede depender tanto del diccionario como del diccionario). contenido de flujo de bits) que podría aterrizar en un límite de palabra de código correcto por coincidencia en un tiempo finito, y cuando eso suceda producirá un resultado de decodificación correcto para los símbolos subsiguientes. Se han realizado algunas investigaciones sobre las propiedades (en el diccionario de palabras de código y en el flujo de bits) que garantizarían esta resincronización.
rwong
@rwong: si los datos originales fueran aleatorios con una distribución tal que los bits de la secuencia tuvieran una probabilidad independiente de ser uno o cero, la probabilidad de permanecer fuera de sincronización durante más de N símbolos decaería exponencialmente al aumentar N. Es más probable que los datos reales contengan patrones que podrían evitar la resincronización, pero en la práctica es poco probable que un error al comienzo de un archivo de texto de 100 MB corrompa todos los 100 MB de texto.
supercat
13

Es útil imaginarlo como un árbol. Simplemente está atravesando el árbol hasta llegar a un nodo hoja y luego reiniciando desde la raíz. Desde el algoritmo que codifica huffman, puede ver que este tipo de estructura se crea en el proceso.

https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

quietContest
fuente
66
El aspecto importante aquí es que todas las palabras de código válidas son hojas. Necesitaría separadores si tuviera símbolos en los nodos internos también.
MvG
3

Ningún código que no sea E comienza con 0000. Ningún código que no sea I comienza con 0001. Y así sucesivamente. Como caso extremo, ningún código que no sea e comienza con 01. No tiene cosas como E = 0000, espacio = 000, donde no sabría qué hacer si encuentra tres ceros.

Mire su cadena codificada: 0000101100000 ...

Lees el primer cero. Usted sabe que el código es uno de E, i, y, l, k, coma o espacio. El siguiente cero significa que no es k, coma o espacio, sino E, i, y o l. El siguiente cero significa que es E o i. El siguiente cero significa que es una E. Cuando sabes qué código es, sabes que has analizado todos los bits para ese código.

Entonces tienes 101100000 ... El 1 significa que tienes e, r, s, no a. El siguiente bit es 0, entonces el código es e. De nuevo, ya terminaste con ese personaje.

gnasher729
fuente
-2

No podemos usar separador en la codificación de Huffman porque el equivalente binario de cada letra no coincide con el código prefijado de ninguna letra, por lo que podemos hacerlo sin siquiera usar el separador.

Sandeep Das
fuente
3
¿No lo dije ya, solo sin los niveles confusos de muchas negaciones anidadas? (Y, por cierto, no es que no podamos usar un separador; solo que no necesitamos ).
David Richerby