El algoritmo de paquete de combinación es un O (nL) -Tiempo algoritmo para encontrar un óptimo código Huffman de longitud limitada para una distribución dada en un alfabeto determinado de tamaño n , donde no hay palabra de código es más larga que L . Es un algoritmo codicioso y una generalización del algoritmo original de Huffman . La combinación de paquetes funciona reduciendo el problema de construcción del código al problema del coleccionista de monedas binarias . [1]
El problema del coleccionista de monedas
Suponga que un coleccionista de monedas tiene varias monedas de varias denominaciones, cada una de las cuales tiene un valor numismático no relacionado con su denominación. El colector de la moneda se ha quedado sin dinero y necesita usar algo de su colección de monedas para comprar algo de coste N . Él desea seleccionar un subconjunto de las monedas de su colección de valor numismático mínimo cuya denominaciones total de N .
La versión binaria de este problema es que todas las denominaciones son potencias de 2, es decir, 1, 1/2, 1/4, etc. dólares.
Descripción del algoritmo de combinación de paquetes
Suponga que la denominación más grande es 1 dólar y que N es un número entero. (El algoritmo funciona incluso si estas suposiciones no se cumplen, mediante modificaciones triviales). El recolector de monedas primero separa sus monedas en listas, una para cada denominación, clasificadas por valor numismático. Luego empaqueta las monedas de denominación más pequeña en pares, comenzando por el par de valor numismático total más pequeño. Si queda una moneda, será la moneda de mayor valor numismático de esa denominación, y de ahora en adelante se reserva y se ignora. Estos paquetes luego se fusionan en la lista de monedas de la siguiente denominación más pequeña, nuevamente en orden de valor numismático. Los elementos de esa lista se empaquetan en pares y se combinan en la siguiente lista más pequeña, y así sucesivamente.
Finalmente, hay una lista de artículos, cada uno de los cuales es una moneda de 1 dólar o un paquete que consta de dos o más monedas más pequeñas cuyas denominaciones suman 1 dólar. También están ordenados por valor numismático. A continuación, el recolector de monedas selecciona el menor valor N de ellos.
Tenga en cuenta que el tiempo del algoritmo es lineal en el número de monedas.
Reducción de la codificación Huffman de longitud limitada al problema del coleccionista de monedas
Sea L la longitud máxima que se permite tener cualquier palabra de código. Sean p 1 ,…, p n las frecuencias de los símbolos del alfabeto a codificar. Primero ordenamos los símbolos de modo que p i ≤ p i +1 . Cree L monedas para cada símbolo, de denominaciones 2 −1 ,…, 2 - L , cada una de valor numismático p i . Utilice el algoritmo de combinación de paquetes para seleccionar el conjunto de monedas de valor numismático mínimo cuyas denominaciones suman n - 1. Sea h i el número de monedas de valor numismático p i seleccionadas. El código Huffman de longitud limitada óptima codificará el símbolo i con una cadena de bits de longitud h i . El código canónico de Huffman se puede construir fácilmente mediante un método codicioso de abajo hacia arriba, dado que los h i son conocidos, y esto puede ser la base para una rápida compresión de datos . [2]
Mejoras de rendimiento y generalizaciones
Con esta reducción, el algoritmo es O (nL) -tiempo y O (nL) -espacio. Sin embargo, el artículo original, " Un algoritmo rápido para códigos de Huffman de longitud limitada óptimos ", muestra cómo esto se puede mejorar a O (nL) -tiempo y O (n) -espacio. La idea es ejecutar el algoritmo por primera vez, manteniendo solo los datos suficientes para poder determinar dos subproblemas equivalentes que sumen la mitad del tamaño del problema original. Esto se hace de forma recursiva, lo que da como resultado un algoritmo que tarda aproximadamente el doble pero que solo requiere espacio lineal. [1]
Se han realizado muchas otras mejoras en el algoritmo de combinación de paquetes para reducir la constante multiplicativa y hacerla más rápida en casos especiales, como los problemas que tienen p i s repetidos . [3] El enfoque de combinación de paquetes también se ha adaptado a problemas relacionados, como la codificación alfabética . [4]
Se ha demostrado que los métodos que involucran la teoría de grafos tienen una mayor complejidad de espacio asintótico que el algoritmo de combinación de paquetes, pero estos no han tenido tanta aplicación práctica.
Referencias
- ↑ a b Larmore, Lawrence L .; Hirschberg, Daniel S. (1990). "Un algoritmo rápido para códigos Huffman de longitud limitada óptimos". Revista de la Asociación de Maquinaria Informática . 37 (3): 464–473. doi : 10.1145 / 79147.79150 .
- ^ Moffat, Alistair ; Turpin, Andrew (octubre de 1997). "Sobre la implementación de códigos prefijos de redundancia mínima". Transacciones IEEE sobre comunicaciones . 45 (10): 1200–1207. doi : 10.1109 / 26.634683 .
- ^ Witten, Ian H .; Moffat, Alistair ; Bell, Timothy Clinton (1999). Administrar Gigabytes: Comprimir e indexar documentos e imágenes (2 ed.). Editores Morgan Kaufmann . ISBN 978-1-55860-570-1. 1558605703.
- ^ Larmore, Lawrence L .; Przytycka, Teresa M. (1994). "Un algoritmo rápido para árboles binarios alfabéticos de altura limitada óptima". Revista SIAM de Computación . 23 (6): 1283-1312. doi : 10.1137 / s0097539792231167 .
enlaces externos
- Baer, Michael B. (2006). "Veinte (más o menos) preguntas: codificación de prefijo delimitado por longitud D -ary". arXiv : cs.IT/0602085 .
- Moffat, Alistair ; Turpin, Andrew; Katajainen, Jyrki (marzo de 1995). Construcción con uso eficiente del espacio de códigos de prefijo óptimos . Conferencia de compresión de datos IEEE. Snowbird, Utah, Estados Unidos. doi : 10.1109 / DCC.1995.515509 .
- Una implementación del algoritmo de combinación de paquetes " [1] "
- Un codificador de entropía rápido que utiliza un algoritmo de combinación de paquetes [2]