algorithm - ejemplo - código huffman canónico
necesita ayuda sobre cómo codificar palabras usando el código huffman (4)
Eche un vistazo a Huffman Coding with F # , una publicación de blog que presenta un codificador / decodificador Huffman escrito en F #. Es corto y claro.
¿Cómo codifica palabras usando el código Huffman como NECESIDAD?
La codificación de Huffman básicamente utiliza cadenas de bits de longitud variable para representar tokens (generalmente caracteres con un par de excepciones). Cuanto más común es un token, más corto es el bit-length y esto es (generalmente) dinámico a medida que se procesa el flujo.
Generalmente hay dos tokens especiales, ESCAPE y END-STREAM.
La codificación mantiene un diccionario que es básicamente una búsqueda de las secuencias de bits para obtener un token. Inicialmente contiene solo los dos tokens especiales.
Las secuencias de bits iniciales para ESCAPE y END_STREAM podrían ser 0 y 1 (que es lo que realmente no importa al principio). Cuando el codificador recibe un carácter que no está en el diccionario, emite ESCAPE y el token de longitud completa, luego lo agrega y asigna nuevas secuencias de bits, en función de la frecuencia de todos los tokens.
Entonces su ''N'' puede dar como resultado la secuencia de salida:
0 xxxxxxxx
| +- token code for N
+--- ESCAPE
y el nuevo diccionario:
ESCAPE:00
END-STREAM:01
N:1
Entonces su ''E'' puede dar como resultado la secuencia de salida:
0 xxxxxxxx 0 yyyyyyyy
+- token code for E
y el nuevo diccionario:
ESCAPE:00
END-STREAM:01
N:10
E:11
Su próxima E no dará como resultado una salida ESCAPE ya que ya está en el diccionario, por lo que acaba de emitir su código (11). Cambiará el diccionario ya que E ahora tiene un conteo más alto. Esto no importará en nuestra situación ya que todos los caracteres tienen dos dígitos binarios pero, en un ejemplo más complicado, la longitud del bit de la señal ''E'' se acortará.
Cuando llega la D, la secuencia de salida se convierte en:
0 xxxxxxxx 0 yyyyyyyy 11 0 zzzzzzzz
| +- token code for D
+------ second E
y el nuevo diccionario:
ESCAPE:00
END-STREAM:011
N:010
E:11
D:10
De modo que puede ver que, a medida que ingresan más caracteres, la longitud de bits de los comunes disminuye y la del poco frecuente aumenta, lo que le proporciona la compresión. N (o D) en este caso obtiene un código de 3 dígitos, mientras que E se pega con un código de 2 dígitos porque hay más de ellos.
La belleza es que no necesita almacenar el diccionario con el archivo ya que las secciones de ESCAPE también lo compilan dinámicamente para la compresión.
Además, debido a que NUNCA hay una ficha END-STREAM hasta el final, su longitud de bit sigue creciendo. Similar para ESCAPE, aunque todavía hay muchos personajes nuevos entrando, su longitud de bits permanece corta, pero, cuando no llegan nuevos personajes, corre el mismo destino que END-STREAM.
El mejor caso para un flujo de entrada (ASCII de 8 bits) es un archivo que contiene nada más que millones del mismo carácter. Esto cuesta 9 bits para el primer personaje, luego 1 bit para cada carácter adicional y luego 2 bits para el final del flujo. Ese rápido se aproxima a una relación de compresión de 1 por 8 (97.5%).
El peor de los casos es exactamente uno de cada personaje que cuesta 9 bits por personaje más el final del flujo, esto en realidad expande el flujo en un 12.5%.
Creo que te refieres a Huffman Coding . Es un algoritmo para comprimir datos sin pérdida. En pocas palabras, reemplaza los bits de datos contiguos más largos y repetitivos en la representación más pequeña posible (que es cómo funciona la mayoría de la compresión). Por ejemplo, una página HTML puede asignar el <DIV muy común al número binario 01 reduciendo los 32 bits de cada <DIV a solo 2 bits.
Esa es la idea básica. El otro truco es cómo elegir los números para que no tenga que usar un tamaño fijo o un separador. Esto se hace usando un árbol Huffman . Lea el artículo de Wikipedia para más.
Eche un vistazo a mi proyecto Huffman en C #: https://github.com/kad0xf/HuffmanSharp