rss

Artictles

Hi, thanks for visiting this page. Here I write about technology, in-depth analysis of some problems, sport management, among others. If you like these things, you will be glad to read the articles. Also, you can comment or ask questions whenever you want. I will try to respond as soon as possible...

Compresión de datos en tiempo real Bookmark

El término compresión de datos se refiere al proceso de reducción del volumen de datos necesario para poder representar una determinada información, a fin de permitir una transmisión o almacenamiento más eficaz. Antes de continuar, se debe aclarar que los términos datos e información no son sinónimos, es decir, los datos son el medio a través del cual se conduce la información.

Compresión de datos en tiempo real

A partir de esta idea, deseo implementar un algoritmo de compresión que opere en tiempo real con datos electrocardiográficos y que permita recuperar los datos originales (sin perdida).  En la literatura existen varios algoritmos que pueden ser útiles y que discutiré a continuación.

El algoritmo de compresión Shannon-Fano, se basa en conocer la probabilidad de aparición de cada símbolo en un mensaje, dada sus probabilidades, se puede construir una tabla de códigos de longitud diferente (aunque pueden ser unívocamente decodificados).

Otro algoritmo de dos pasos, introducido por Huffman en 1951, produce un código de longitud variable, usando la frecuencia de aparición de los datos, compartiendo la mayoría de las características del código de Shannon-Fano mencionado anteriormente.

Ahora bien, existen ciertos inconvenientes con los dos algoritmos mencionados anteriormente. En primer lugar, la única forma de conocer qué secuencias son más probables es examinar de principio a fin aquello que se quiere comprimir. Eso obliga a dar dos pasadas por los datos, causando perdida de velocidad en la compresión e incapacidad de utilizar el compresor como un filtro digital. Con estos modelos de compresión sólo se pueden ofrecer soluciones parciales y poco eficientes a mi objetivo: comprimir datos de ECG.

En vista de lo anterior, hace falta algún algoritmo o tipo de codificación que sea capaz de adaptarse a su fuente, que a partir de ella genere el código más acertado posible y lo transmita junto con la fuente sin llegar a hacer inútil la compresión por el overhead que implica enviar el código junto con los datos, y que además empiece a hacer todo esto desde el primer momento en el que le van llegando los datos al compresor o descompresor, sin tener que llegar a conocer todo el mensaje.

El algoritmo de codificación Huffman adaptiva cumple con las incógnitas anteriores. Este algoritmo fue publicado por primera vez por Faller [2] y Gallager [3]. Luego este fue mejorado por Knuth [4]. El resultado de este algoritmo es referido como el algoritmo FGK. En 1987 Vitter [5] publicó una versión avanzada de la codificación Huffman adaptiva, referida como algoritmo V.

A continuación explicare cada uno de estos algoritmos, realizando un ejemplo para cada uno, con una fuente de datos similar, realizando comparaciones significativas. Seguido de la implementación en lenguaje de programación C++ de la codificación Huffman Adaptiva usando el algoritmo FGK y el algoritmo Vitter. Por ultimo, comprobare el funcionamiento de las clases implementadas en la plataforma de adquisición, almacenamiento, visualización y procesamiento de señales electrocardiográficas: eMonitor.

Codificación sin perdida

Codificación Shannon-Fano.

Este método fue desarrollado por Claude Shannon en los laboratorios Bell y simultáneamente por R. M. Fano en MIT. Este método se basaba en conocer la probabilidad de aparición de cada símbolo en un mensaje. Dadas las probabilidades, se puede construir una tabla de códigos que tiene varias propiedades importantes:

Diferentes códigos tienen diferentes números de bits.

Los códigos para símbolos con probabilidades bajas tienen más bits, y los códigos para símbolos con probabilidades altas tienen menos bits.

Aunque los códigos son de longitud diferente, pueden ser unívocamente decodificados.

Algoritmo Shannon-Fano

Para explicar este algoritmo seguire una secuencia de pasos para codificar el siguiente mensaje de texto:

DDABEBADACABAAECDCBAEACABCBAADDEAACAEAB

Para una secuencia de símbolos, se calcula la correspondiente lista de frecuencias de aparición de los símbolos, y se ordena en orden decreciente:

Tabla 1. Tabla de frecuencias para el mensaje de texto

Tabla 1. Tabla de frecuencias para el mensaje de texto

Se divide la lista en dos partes, de forma que la suma total de frecuencias de la mitad superior sea lo más cercana posible a la suma total de la parte inferior. A la mitad superior de la lista se le asigna el dígito binario 0, y a la mitad inferior se le asigna el dígito binario 1. Esto significa que los códigos de los símbolos en la primera mitad (gris claro) empezaran con 0 y los códigos en la segunda mitad (gris oscuro) empezarán todos con 1.

Tabla 2. Aplicación de la división entre B y C quedando dos grupos, uno suma 22 y otro 17

Tabla 2. Aplicación de la división entre B y C quedando dos grupos, uno suma 22 y otro 17

De manera recursiva se aplica el mismo procedimiento a cada una de las dos mitades, se subdivide en grupos y se agregan bits a los códigos hasta que cada grupo conste de un único símbolo.

Tabla 3. Tabla de Shannon para el mensaje de texto

Tabla 3. Tabla de Shannon para el mensaje de texto

La siguiente tabla muestra la cantidad de información o entropía (Referirse a la Teoría de la Información, Entropía) que contiene el mensaje según nuestro cuerpo teórico.

Tabla 4. Cantidad de información del mensaje de texto

Tabla 4. Cantidad de información del mensaje de texto

Sí se codifica los símbolos del ejemplo anterior usando los códigos ASCII (8-bit), se usaría 39 x 8 bits = 312 bits para el mensaje sin compresión.

Ahora bien, la tabla 4 se puede completar para formar la tabla 5, de donde se puede ver que sí se codifica los símbolos usando Shannon-Fano se necesitaría 89 bits.

Tabla 5. Datos usando los códigos de Shannon-Fano

Tabla 5. Datos usando los códigos de Shannon-Fano

Codificación Huffman

En 1951 D.A. Huffman introdujo un algoritmo de dos pasos, que produce un código de longitud variable, usando la frecuencia de aparición de los datos. Este algoritmo, comparte la mayoría de las características del código de Shannon-Fano explicado anteriormente.

A continuación explicare la forma de obtener el árbol de Huffman.

Algoritmo Huffman

Al igual que en el caso del algoritmo Shannon-Fano, se explicara el algoritmo de codificación de Huffman usando el siguiente mensaje de texto como fuente a codificar:

DDABEBADACABAAECDCBAEACABCBAADDEAACAEAB

El código o árbol de Huffman se construyen de abajo a arriba, comienza con las ramas del árbol y progresivamente se acercan hasta la raíz. Cada nodo inicial tiene un peso, que es la frecuencia de aparición del símbolo.

 

Figura 1. Estado inicial de árbol de Huffman para el mensaje de texto

Figura 1. Estado inicial de árbol de Huffman para el mensaje de texto

Se localizan los dos nodos libres con los pesos más bajos. Se crea un nodo padre para estos dos nodos. Se le asigna un peso igual a la suma de los dos nodos hijos. Se designa con un 0 el camino de uno de los nodos hijos que le lleva al padre en la decodificación, el otro es indudablemente un 1.

Figura 2. Creación del primer nodo en el árbol de Huffman

Figura 2. Creación del primer nodo en el árbol de Huffman

Se repiten los pasos previos hasta que solo quede un nodo libre. Se asigna la raíz del árbol a este nodo libre.

 

Figura 3. Creación del segundo nodo en el árbol de Huffman

Figura 3. Creación del segundo nodo en el árbol de Huffman

image

Figura 4. Creación del tercer nodo en el árbol de Huffman

Figura 5. Estado final del árbol de Huffman para el mensaje de texto

Figura 5. Estado final del árbol de Huffman para el mensaje de texto

También se puede obtener un árbol similar para el algoritmo Shannon-Fano usando la tabla 3, como se muestra en la siguiente figura.

Figura 6. Árbol de Shannon-Fano para el mensaje de texto

Figura 6. Árbol de Shannon-Fano para el mensaje de texto

Una vez formados los árboles o códigos de cada algoritmo, se puede realizar el segundo paso de la codificación, el cual corresponde a remplazar cada símbolo por su código en el árbol siguiendo la trayectoria desde la raíz del árbol hasta llegar al nodo o hoja del símbolo que se desea codificar. El resultado de este paso se muestra en la siguiente tabla.

Tabla 6. Tabla de códigos para Shannon-Fano y Huffman

Tabla 6. Tabla de códigos para Shannon-Fano y Huffman

A través de las figuras 5 y 6 y la tabla anterior, se puede obtener la siguiente tabla comparativa, entre el algoritmo Shannon-Fano y el algoritmo Huffman.

Tabla 7. Tabla comparativa entre Shannon-Fano y Huffman para el mensaje de texto

Tabla 7. Tabla comparativa entre Shannon-Fano y Huffman para el mensaje de texto

Inconvenientes de la Codificación de Huffman

  • En primer lugar, la única forma de conocer qué secuencias son más probables es examinar de principio a fin aquello que se quiere comprimir. Eso obliga a dar dos pasadas por los datos: una para encontrar las secuencias que más se repiten (y con ellas elaborar el árbol de Huffman), más una segunda para codificar la fuente con el código así establecido. Este inconveniente es, a su vez, causa de:
    • Pérdida de velocidad en la compresión. Lo ideal sería poder ir comprimiendo según van llegando los datos para que empecemos a tener resultados de forma inmediata.
    • Imposibilidad de utilizar el compresor como un filtro. La necesidad de dar dos pasadas por los datos se puede satisfacer cuando se está actuando sobre archivos, en los que se puede aplicar operaciones para moverse a una posición deseada del mismo. Pero es muy común querer comprimir los datos que se obtienen a través de una tubería, donde estas operaciones no tienen sentido. Aunque ejemplificado desde el punto de vista del compresor, está claro que esta limitación afecta, igualmente, al descompresor.
  • Con la asignación de palabras código a secuencias hay que hacerse (en estos casos de codificación de fuentes genéricas) la pregunta de cuándo parar. Se pueden establecer y almacenar frecuencias de bytes, y se tendrá una tabla de 256 entradas, desde los más frecuentes a los más raros. Pero eso no basta: si estamos comprimiendo un texto, dependiendo del idioma en que esté escrito, encontramos que es más común que unas letras vayan acompañadas de otras. En español, por ejemplo, es muy raro encontrar las secuencias "ts", "aa" o "bq". En otros idiomas, o en archivos binarios, pueden darse más unas agrupaciones y menos otras. Si estas agrupaciones se tienen en cuenta en el código, se obtendrá un mayor radio de compresión, pero nos encontramos con una tabla de 256x256 = 65536 entradas.
  • Suponiendo que fueran aceptables la pérdida en velocidad, los problemas con las tuberías y los derivados del tamaño de las tablas, aún queda otro inconveniente por afrontar: dado que podemos encontrarnos con fuentes de lo más variadas y que por ello no es posible tener a priori códigos adaptados a cada una de ellas, conocidos en los dos extremos de la comunicación o en compresor y descompresor, no sólo es necesario guardar o transmitir la secuencia codificada, sino también el propio código necesario para descodificarla. Dependiendo de lo voluminoso que sea este (y por lo visto en el punto anterior, puede llegar a ser muy voluminosos), podría darse el caso de que juntando ambos sumandos, datos más código ocupen más que los datos originales sin comprimir.

Con este modelo de compresión sólo se pueden ofrecer soluciones parciales y poco eficientes a esta serie de problemas. Para el caso de los filtros no quedaría más remedio que guardar lo que le llega al compresor/descompresor por su entrada estándar en un archivo intermedio, y después comprimir ese archivo, lo cual, dependiendo de lo cuantiosa que sea la salida del filtro, podría implicar la imposibilidad de llevar a cabo la operación si en el disco duro no cupieran, simultáneamente, el archivo temporal sin comprimir más la salida del compresor, ya comprimida. Por la misma razón de espacio, la solución de guardar todos los datos en memoria durante la primera pasada y volver sobre ellos en la segunda soluciona el problema de las tuberías pero es de dudosa utilidad, a menos que se cuente con memoria infinita.

Para evitar tener que guardar o transmitir datos comprimidos y código necesario para descomprimirlos, se podría tratar de hacer un estudio de muchas fuentes y en función de él, sacar un único código que se aplicara a todas las fuentes. Evidentemente, eso sería poco eficiente. Por ser fruto del cálculo de una "media", probablemente no sería óptimo para ninguna fuente. Pero, al fin y al cabo, esta es la solución adoptada, por ejemplo, en el código Morse. En él, la asignación de puntos y rayas a las letras no es aleatoria: el punto se hace corresponder con la letra ``e'', la más frecuente en el idioma inglés. E igualmente con el resto de las letras: todas ellas codificadas en función de su frecuencia en el susodicho idioma. Mientras nos mantengamos en él, es razonablemente eficiente, pero en cuanto la transmisión se lleve a cabo en otro idioma, es probable que las letras más usadas sean también las que tienen un código de puntos y rayas más largo.

La pérdida de velocidad no tiene solución, ni siquiera una no óptima, si no se quiere usar un código genérico. Las dos pasadas hay que darlas, y hasta que no se haya llevado a cabo la primera, no es posible empezar a comprimir en la segunda.

En resumen, hace falta algún algoritmo o tipo de codificación que sea capaz de adaptarse a su fuente, que a partir de ella genere el código más acertado posible y lo transmita junto con la fuente sin llegar a hacer inútil la compresión por el overhead que implica enviar el código junto con los datos, y que además empiece a hacer todo esto desde el primer momento en el que le van llegando los datos al compresor o descompresor, sin tener que llegar a conocer todo el mensaje.

Codificación Huffman Adaptiva

El primer algoritmo de codificación Huffman adaptiva fue publicado por Faller [2] y Gallager [3]. Luego este fue mejorado por Knuth [4]. El resultado de este algoritmo es referido como el algoritmo FGK. En 1987 Vitter [5] publicó una versión avanzada de la codificación Huffman adaptiva, referida como algoritmo V.

Hasta el momento se requería conocer todos los símbolos del mensaje para obtener una frecuencia y poder calcular el código o árbol de Huffman. La codificación adaptiva permite comenzar el proceso de compresión sin conocer a priori los datos a codificar. Esto es posible ajustando el árbol Huffman en cada paso, basándose en los datos previamente vistos y sin tener información sobre los futuros. Para llevar a cabo este proceso, es necesario introducir un concepto nuevo: la propiedad hermano (Sibling Property).

Propiedad Hermano (Sibling Property)

Un árbol binario con p nodos con peso no negativo es un árbol de Huffman sí y solo si:

  1. Los p nodos tienen peso no negativos w1, w2, …., wp, y el peso de cada nodo interno es la suma de los pesos de sus nodos hijos
  2. Los nodos pueden ser numerados en orden no decreciente por su peso, tal que, los nodo 2j-1 y 2j sean hermano, para 1 ≤ j ≤ p-1, y su nodo padre es más grande en la numeración.

La primera condición se cumple también en la codificación Huffman que vimos anteriormente. La segunda condición se refiere al algoritmo Vitter, el cual explicaremos mas adelante.

La diferencia básica entre FGK y Vitter es que FGK no verifica el árbol entero para poner al día el peso de un nodo o usa cualquier tipo de esquema de clasificación numerado. Sólo verifica los nodos contra su hermano derecho o el hermano del padre.

Algoritmo FGK

En primer lugar debemos inicializar el árbol con el nodo raíz con dos nodos hijos: NYT y EOS. El nodo NYT (Not Yet Transmitted) de peso cero, nos sirve cuando llega un símbolo nuevo al codificador, con lo cual, se transmite el código del nodo NYT, seguido del valor sin codificar del nuevo símbolo. Luego se procede a actualizar el árbol. Por otro lado, el nodo EOS (End Of String) nos sirve para indicar fin del mensaje, transmitiendo el código del mismo al finalizar el mensaje.

Figura 7. Estado inicial del árbol de Huffman adaptivo en el algoritmo FGK

Figura 7. Estado inicial del árbol de Huffman adaptivo en el algoritmo FGK

Se entra en el siguiente ciclo de lectura y codificación:

  1. Se codifica el símbolo de entrada (ver figura 8)
    1. Sí se encuentra el símbolo en el árbol de Huffman, se transmite el código del mismo
    2. Sí no se encuentra el símbolo en el árbol de Huffman, se codifica según el código del nodo NYT seguido por el símbolo. Se incluye el símbolo nuevo en el árbol. En donde se encontraba el nodo NYT, se coloca un nodo interno cuyo hijo izquierdo será el mismo nodo NYT y el derecho será el símbolo nuevo.
  2. Se actualiza el árbol de Huffman (ver figura 9)
    1. Se busca un nodo con el mismo peso del símbolo en cuestión. Sólo se verifica los nodos contra su hermano derecho (sí el nodo en cuestión fuera izquierdo) o el hermano del padre.
    2. Sí el nodo actual es diferente del nodo encontrado en el paso anterior y tampoco es su padre, se intercambian.
    3. Incrementar el peso del símbolo en cuestión.
    4. Se coloca como nodo actual el padre del mismo. Sí el nodo actual no es el nodo raíz, se regresa al paso (2.1)
  3. Sí finalizo el mensaje se codifica el nodo EOS, de lo contrario se regresa al paso (1).

A continuación explicare el algoritmo FGK usando el mensaje de texto como fuente a:

DDABEBADACABAAECDCBAEACABCBAADDEAACAEAB

Ahora bien, el codificador no conoce todo el mensaje, con lo cual explicare el algoritmo según vayan llegando los datos al compresor (funcionaría de forma similar en el descompresor):

Se inicializa el árbol de Huffman como se muestra en la figura 7 (suponiendo que los símbolos se codifican ASCII de 8 bits).

Tabla 8. Codificación del símbolo nuevo D en el algoritmo FGK
Tabla 8. Codificación del símbolo nuevo D en el algoritmo FGK
 
Llegada del símbolo D. No se encuentra en el árbol, con lo cual debemos codificar según el código del nodo NYT seguido por el símbolo. Luego incluimos el símbolo nuevo en el árbol. Finalizando con la actualización del árbol.

Figura 8. Llegada de un símbolo nuevo. Inclusión del símbolo D en el algoritmo FGK (A)   Figura 8. Llegada de un símbolo nuevo. Inclusión del símbolo D en el algoritmo FGK (B)

Figura 8. Llegada de un símbolo nuevo. Inclusión del símbolo D en el algoritmo FGK

Figura 9. Actualización del árbol de Huffman adaptivo usando el Algoritmo FGK

Figura 9. Actualización del árbol de Huffman adaptivo usando el Algoritmo FGK

Figura 10. Estado del árbol de Huffman adaptivo después de la llegada del nuevo símbolo D una vez finalizada la actualización

Figura 10. Estado del árbol de Huffman adaptivo después de la llegada del nuevo símbolo D una vez finalizada la actualización

Llegada del símbolo D. Ya se encuentra en el árbol, con lo cual debemos codificar según el código del símbolo. Finalizando con la actualización del árbol.

Tabla 9. Codificación del símbolo D (ya existente) en el algoritmo FGK
Tabla 9. Codificación del símbolo D (ya existente) en el algoritmo FGK
 
Figura 11. Estado del árbol de Huffman adaptivo después de la llegada del símbolo D (ya existente) una vez finalizada la actualización en el algoritmo FGK
Figura 11. Estado del árbol de Huffman adaptivo después de la llegada del símbolo D (ya existente) una vez finalizada la actualización en el algoritmo FGK
 
De esta forma codificamos cada símbolo entrante. Una vez procesado todo el mensaje, nos encontramos con el árbol de Huffman que se muestra en la siguiente figura.
 
Figura 12. Estado final del árbol de Huffman adaptivo después de procesar el mensaje de texto usando el algoritmo FGK
Figura 12. Estado final del árbol de Huffman adaptivo después de procesar el mensaje de texto usando el algoritmo FGK
 
El desarrollo completo del ejemplo anterior, se mostrara mas adelante (archivo adjunto).

Algoritmo Vitter

El algoritmo de Vitter es muy similar al FGK, excepto que Vitter verifica el árbol entero para poner al día el peso de un nodo usando un esquema de clasificación numerado. El algoritmo Vitter funciona de la siguiente manera:

En primer lugar, debemos inicializar el árbol con el nodo raíz con dos nodos hijos: NYT y EOS similar al algoritmo FGK. El nodo NYT (Not Yet Transmitted) de peso cero, nos sirve cuando llega un símbolo nuevo al codificador, con lo cual, se transmite el código del nodo NYT, seguido del valor sin codificar del nuevo símbolo. Luego se procede a actualizar el árbol. Por otro lado, el nodo EOS (End Of String) nos sirve para indicar fin del mensaje, transmitiendo el código del mismo al finalizar el mensaje. Adicionalmente se crea un sistema de numeración basado en el segundo ítem de propiedad hermano vista anteriormente:

  1. Los p nodos tienen peso no negativos w1, w2, …., wp, y el peso de cada nodo interno es la suma de los pesos de sus nodos hijos
  2. Los nodos pueden ser numerados en orden no decreciente por su peso, tal que, los nodo 2j-1 y 2j sean hermano, para 1 ≤ j ≤ p-1, y su nodo padre es más grande en la numeración.
 
Figura 13. Estado inicial del árbol de Huffman adaptivo en el algoritmo de Vitter
Figura 13. Estado inicial del árbol de Huffman adaptivo en el algoritmo de Vitter
Se entra en el siguiente ciclo de lectura y codificación:
  1. Se codifica el símbolo de entrada (similar al algoritmo FGK , ver figura 8)
    1. Sí se encuentra el símbolo en el árbol de Huffman, se transmite el código del mismo.
    2. Sí no se encuentra el símbolo en el árbol de Huffman, se codifica según el código del nodo NYT seguido por el símbolo. Se incluye el símbolo nuevo en el árbol. En donde se encontraba el nodo NYT, se coloca un nodo interno cuyo hijo izquierdo será el mismo nodo NYT y el derecho será el símbolo nuevo.
  2. Se actualiza el árbol de Huffman (ver figura 14)
    1. Se busca un nodo con el mismo peso del símbolo en cuestión, usando el sistema de numeración. Se empieza por el número más alto después del nodo raíz. En caso que no tenga el mismo peso, se busca el siguiente nodo con un número menor, hasta llegar al nodo por el cual se empezó la búsqueda.
    2. Sí el nodo actual es diferente del nodo encontrado en el paso anterior y tampoco es su padre, se intercambian.
    3. Incrementar el peso del símbolo en cuestión.
    4. Se coloca como nodo actual el padre del mismo. Sí el nodo actual no es el nodo raíz, se regresa al paso (2.1).
  3. Sí finalizo el mensaje se codifica el nodo EOS, de lo contrario se regresa al paso (1).

Figura 14. Actualización del árbol de Huffman adaptivo usando el Algoritmo Vitter

Figura 14. Actualización del árbol de Huffman adaptivo usando el Algoritmo Vitter

 

A continuación explicare el algoritmo Vitter usando el mensaje de texto como fuente a codificar:

DDABEBADACABAAECDCBAEACABCBAADDEAACAEAB

De nuevo, el codificador no conoce todo el mensaje, con lo cual explicare el algoritmo según vayan llegando los datos al compresor (funcionaría de forma similar en el descompresor):

  1. Se inicializa el árbol de Huffman como se muestra en la figura 13.
  2. Llegada del símbolo D. No se encuentra en el árbol, con lo cual debemos codificar según el código del nodo NYT seguido por el símbolo. Luego incluimos el símbolo nuevo en el árbol. Finalizando con la actualización del árbol (suponiendo que los símbolos se codifican ASCII de 8 bits).
Tabla 10. Codificación del símbolo nuevo D en el algoritmo Vitter
Tabla 10. Codificación del símbolo nuevo D en el algoritmo Vitter
Figura 15. Estado del árbol de Huffman adaptivo después de la llegada del símbolo D una vez finalizada la actualización en el algoritmo Vitter
Figura 15. Estado del árbol de Huffman adaptivo después de la llegada del símbolo D una vez finalizada la actualización en el algoritmo Vitter
 
De esta forma codificamos cada símbolo entrante. Una vez procesado todo el mensaje, nos encontramos con el árbol de Huffman que se muestra en la siguiente figura.
Figura 16. Estado final del árbol de Huffman adaptivo después de procesar el mensaje de texto usando el algoritmo Vitter
Figura 16. Estado final del árbol de Huffman adaptivo después de procesar el mensaje de texto usando el algoritmo Vitter
El desarrollo completo del ejemplo anterior, se mostrara mas adelante (archivo adjunto).

Referencias

  1. D.A. Huffman, A Method for the Construction of Minimum-redundancy Codes, Proc. IRE, 1952, Vol. 40, no. 10, pp. 1098-1101.
  2. N. Faller, An Adaptive System for Data Compression, Record of the 7th Asilomar Conference on Circuits, Systems and Computers (Pacific Grove, Ca., Nov. 1973), pp. 593-597.
  3. R.G. Gallager, Variations on a Theme by Huffman, IEEE Trans. Inform. Theory, 1978, Vol. 24, no. 6, pp. 668-674.
  4. D.E. Knuth, Dynamic Huffman Coding, J. Algorithms, 1985, Vol. 6, no. 2, pp. 163-180.
  5. J.S. Vitter, Design and Analysis of Dynamic Huffman Codes, J. ACM, 1987, Vol. 34, no. 4, pp. 825-845.
  6. J.S. Vitter, ALGORITHM 673, Dynamic Huffman Codes, J. ACM, 1989, Vol. 15, no. 2, pp. 158-167.
Attached Files
blog comments powered by Disqus