Hispanopedia WikiEl algoritmo de fusión de paquetes es un algoritmo de tiempo O (nL) para encontrar un código de Huffman óptimo limitado en longitud para una distribución dada en un alfabeto dado de tamaño n , donde ninguna palabra de código es más larga que L . Es un algoritmo voraz y una generalización del algoritmo original de Huffman . La fusión de paquetes funciona reduciendo el problema de construcción de código al problema binario del coleccionista de monedas . [1]
El problema del coleccionista de monedas
Supongamos que un coleccionista de monedas tiene varias monedas de distintas denominaciones, cada una de las cuales tiene un valor numismático que no está relacionado con su denominación. El coleccionista de monedas se ha quedado sin dinero y necesita utilizar parte de su colección de monedas para comprar algo de valor N. Desea seleccionar un subconjunto de monedas de su colección de valor numismático mínimo cuyas denominaciones sumen 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 fusión de paquetes
Supongamos 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 coleccionista de monedas primero separa sus monedas en listas, una para cada denominación, ordenadas por valor numismático. Luego empaqueta las monedas de denominación más pequeña en pares, comenzando por el par de menor valor numismático total. Si queda una moneda, será la moneda de mayor valor numismático de esa denominación y se deja de lado y se ignora de ahí en adelante. Estos paquetes se fusionan luego en la lista de monedas de la siguiente denominación más pequeña, nuevamente en orden de valor numismático. Los artículos en esa lista se empaquetan entonces en pares y se fusionan en la siguiente lista más pequeña, y así sucesivamente.
Por último, 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. El coleccionista de monedas selecciona entonces la N de menor valor de ellas.
Tenga en cuenta que el tiempo del algoritmo es lineal en el número de monedas.
Reducción de la codificación Huffman limitada por longitud al problema del coleccionista de monedas
Sea L la longitud máxima que se permite que tenga cualquier palabra de código. Sean p 1 , …, p n las frecuencias de los símbolos del alfabeto que se van a codificar. Primero ordenamos los símbolos de modo que p i ≤ p i +1 . Creamos L monedas para cada símbolo, de denominaciones 2 −1 , …, 2 − L , cada una de valor numismático p i . Utilizamos el algoritmo de combinación de paquetes para seleccionar el conjunto de monedas de valor numismático mínimo cuyas denominaciones sumen n − 1. Sea h i el número de monedas de valor numismático p i seleccionadas. El código Huffman óptimo de longitud limitada codificará el símbolo i con una cadena de bits de longitud h i . El código Huffman canónico se puede construir fácilmente mediante un método simple de abajo hacia arriba voraz, dado que se conocen los h i , 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 Huffman óptimos de longitud limitada ", muestra cómo esto puede mejorarse a O(nL) -tiempo y O(n) -espacio. La idea es ejecutar el algoritmo una 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 de tiempo pero que solo requiere espacio lineal. [1]
Se han realizado muchas otras mejoras al algoritmo de fusión de paquetes para reducir la constante multiplicativa y hacerlo más rápido en casos especiales, como aquellos problemas que tienen p i repetidos . [3] El enfoque de fusió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 teoría de grafos tienen una mejor complejidad espacial asintótica que el algoritmo de fusión de paquetes, pero estos no han tenido tanta aplicación práctica.
Referencias
- ^ ab Larmore, Lawrence L. ; Hirschberg, Daniel S. (1990). "Un algoritmo rápido para códigos Huffman óptimos de longitud limitada". Revista de la Asociación de Maquinaria Computacional . 37 (3): 464–473. doi : 10.1145/79147.79150 . S2CID 11696729.
- ^ Moffat, Alistair; Turpin, Andrew (octubre de 1997). "Sobre la implementación de códigos de prefijo de redundancia mínima". IEEE Transactions on Communications . 45 (10): 1200–1207. doi :10.1109/26.634683.
- ^ Witten, Ian H. ; Moffat, Alistair; Bell, Timothy Clinton (1999). Managing Gigabytes: Compresión e indexación de documentos e imágenes (2.ª ed.). Morgan Kaufmann Publishers . 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 óptimos". Revista SIAM de Computación . 23 (6): 1283–1312. doi :10.1137/s0097539792231167.
Enlaces externos
- Baer, Michael B. (2006). "Veinte (o más) preguntas: codificación de prefijos con longitud limitada por D -arios". arXiv : cs.IT/0602085 .
- Moffat, Alistair; Turpin, Andrew; Katajainen, Jyrki (marzo de 1995). Construcción de códigos de prefijo óptimos con uso eficiente del espacio . Conferencia sobre compresión de datos del IEEE. Snowbird, Utah, EE. UU. doi :10.1109/DCC.1995.515509.
- Una implementación del algoritmo de fusión de paquetes "[1]"
- Un codificador de entropía rápido que utiliza un algoritmo de fusión de paquetes [2]
