Análisis empírico del efecto del tamaño de la información de entrada en el desempeño de herramientas de compresión sin pérdida

Empirical analysis of the effect of input data size on the performance of lossless compression tools

Este artículo presenta un estudio empírico del efecto que tiene el tamaño de la información de entrada en el desempeño de algoritmos de compresión sin pérdida. Se analizan tres medidas diferentes de desempeño y se crea un nuevo grupo de archivos basado en los corpus de Calgary y Canterbury. Este grupo de archivos también incluye dos archivos complejos. Se demuestra que para archivos grandes la tasa de compresión de algoritmos sin pérdida se mantiene relativamente constante y luego cambia por un pequeño factor cada 10 MB de información. Finalmente, se muestra que el tiempo de ejecución del proceso de compresión y descompresión es una función lineal basada en el tamaño del archivo de entrada.

INTRODUCCIÓN

La compresión de datos sin pérdida ha demostrado ser un mecanismo útil para mejorar el almacenamiento y la transmisión de información, ya que permite que la información comprimida pueda ser recuperada sin ningún tipo de error o modificación. Generalmente este tipo de compresión puede ser logrado mediante dos métodos diferentes [Bell et al., 1989]: método de diccionario y método de codificación estadística. En el primero se almacena un historial de patrones bajo la suposición de que los símbolos recientemente observados pueden encontrarse nuevamente en las cadenas producidas de la información introducida que se está evaluando. En el segundo se crea un modelo estadístico de la información de entrada, y la información es comprimida de acuerdo con la probabilidad de ocurrencia de un símbolo en el modelo.

Un gran número de algoritmos de compresión sin pérdida —o también conocidos como algoritmos de compresión reversible— han sido publicados y muchos de ellos se han usado con éxito en la industria. Por ejemplo, herramientas como compress y pack fueron incluidas en las primeras versiones del sistema UNIX, para ejecutar codificación por los métodos de diccionario y estadística respectivamente.

Se han llevado a cabo muchos esfuerzos investigativos para contrastar y comparar los diferentes algoritmos [Arnold y Bell, 1997, y Bell et al., 1989], sin embargo, no fue posible verificar la existencia de alguna investigación que relacione el tamaño y el tipo de mensaje1 con el desempeño de la herramienta de compresión cuando el tamaño del mensaje es considerablemente grande (por ejemplo, 20 MB). Por esta razón, el propósito de esta investigación es realizar un análisis empírico del impacto de la información de entrada en el desempeño de herramientas de compresión sin pérdida. Como medidas de desempeño se han escogido la tasa de compresión —definida como la relación entre la longitud de salida y la longitud de entrada—, el tiempo real que se toma la herramienta para comprimir un archivo y el tiempo real que se toma la herramienta para descomprimirlo.