Eficiencia de algoritmos de compresión de archivos en tablets android

Isaac Torres, Leonardo Larrea, Carlos Gualán, Freddy Tandazo, Jorge García
Facultad de Ingeniería en Electricidad y Computación
Escuela Superior Politécnica del Litoral
Campus “Gustavo Galindo”, Km 30,5 vía Perimetral. Casilla 09-01-5863, Guayaquil, Ecuador ismatorr@espol.edu.ec, jalarrea@espol.edu.ec, camagual@espol.edu.ec, fatandaz@espol.edu.ec, joregarc@espol.edu.ec

Resumen

En el presente trabajo se buscó determinar el algoritmo de compresión de archivos más eficiente según su grupo, de acuerdo a dos factores, éstos son, tiempo de compresión y porcentaje de compresión, los grupos de algoritmos son: algoritmos estadísticos, algoritmos híbridos y algoritmos de diccionario. Para ello se hizo un muestreo estratificado de archivos con respecto a su tamaño y su redundancia de información. Para analizar la eficiencia de cada algoritmo se utilizó diferencias de medias y varianzas entre el tiempo de compresión y el porcentaje de compresión. Los resultados fueron que los archivos muy pequeños, en lugar de disminuir su tamaño, éstos aumentan. Para los archivos medianos, los algoritmos híbridos y de diccionario tienen un mejor tiempo de compresión y descompresión que los algoritmos estadísticos, mientras que para los archivos grandes, los algoritmos híbridos tienen una clara ventaja sobre los algoritmos estadísticos y de diccionario.

Palabras Claves: ESPOL, factores, universidad.

Abstract

In the present study, we want to determine the most efficient algorithm by group, according to two factors, these are, compression time and compression percentage, the groups of compression algorithms are : statistical algorithms, hybrid algorithms and dictionary algorithms . It was used a stratified sampling of files regarding its size and its information redundancy. To analize each algorithm’s efficiency, it was used mean and variance differences between compression time and compression percentage. The overall results were that there’s no compression percentage for little sized files ,those files increase their size instead of decreasing it. On the other hand, hybrids and dictionary algorithms have a better compression time than statistical algorithms for medium sized files, meanwhile hybrids algorithms have a clear advantage over statistical and dictionary algorithms for big sized files.

Keywords: ESPOL, factors, university.

1. Introducción

En los actuales momentos el almacenamiento de información en sistemas embebidos se ha vuelto un problema crítico, una de las posibles formas de sobrellevarlo es la compresión de archivos, con ello, los algoritmos encargados de dicha compresión juegan un papel fundamental para resolver dicho problema.
Los algoritmos de compresión se clasifican en algoritmos estadísticos, algoritmos híbridos y algoritmos de diccionario. Los algoritmos estadísticos poseen un mejor tiempo de compresión con relación al resto, por otro lado los algoritmos de diccionario poseen un mejor porcentaje de compresión y los algoritmos híbridos combinan características de los otros dos tipos de algoritmos.
Resulta simple mencionar algoritmos de Diccionario como [2], lo que hace básicamente es formar un diccionario de datos y buscar secuencias repetidas dentro de los datos, y cada vez que encuentra una de ellas la remplaza por un puntero a la zona en la que comienza la primera secuencia, más la longitud que se debe tomar a partir de esa posición este último es el utilizado en este experimento.
En un estudio realizado por [1], se usa un algoritmo diferente para cada archivo en particular y los algoritmos de compresión son escogidos de acuerdo a niveles de compresión.
Al respecto[2], han realizado estudios en los cuales se selecciona dinámicamente un algoritmo de compresión de acuerdo al archivo, esta selección se basa en predecir su uso futuro al estudiar el retardo para cada nivel de compresión para cada archivo, su objetivo es aumentar el espacio de almacenamiento disponible.
En otro estudio[4],usan técnicas de compresión de código, ellos creen que muchas instrucciones en tiempo de decodificación pueden ser escondidas particularmente en el caso del código comprimido, de manera que éste es descomprimido antes de ser insertado en la cache, esto resulta en una reducción en el tamaño de los programas almacenados en tiempo de ejecución.
En otro trabajo, [6] compararon 3 esquemas populares, basados en los radios de compresión, dichos esquemas pertenecen a 3 categorías de Arquitecturas, Arquitecturas para la reducción de espacio de almacenamiento, Arquitecturas de bajo consumo y Arquitecturas para la flexibilidad.

Nuestra propuesta fue comprimir y descomprimir archivos de diferentes tamaños y tipos, usando algoritmos estadísticos, algoritmos de diccionario y algoritmos híbridos, obteniendo así su tasa de compresión y tiempo de compresión, luego compararlos con el fin de obtener el algoritmo más eficiente para cada grupo.

2. Metodología

Para la investigación de cual es el algoritmo más eficiente, se consideró como sujetos de estudio a un grupo de archivos, a los cuales se los dividió inicialmente en tres grupos, de acuerdo al tamaño de los archivos, dichos grupos son : archivos pequeños (0-5 mb), archivos medianos(5-15 mb) y archivos grandes(>15 mb). Luego, para cada clasificación por tamaño se realizó una nueva clasificación, esta vez por la redundancia en la información de cada archivo, ésto es, se los clasificó de acuerdo a un factor de repetición en su información, así teniendo 30 archivos para cada familia a subgrupo para un total de 90 por cada tamaño considerado. A continuación se comprimió y descomprimió cada archivo, usando un algoritmo estadístico, un algoritmo de diccionario y un algoritmo híbrido, de manera que se obtuvo el tiempo de compresión, tiempo de descompresión y porcentaje de compresión, para medirlos se utilizó un software llamado Gzip, en el cual se cambiaba el algoritmo de compresión de acuerdo a la prueba que se realizaba.
Se aplicaron pruebas de regresión lineal y Kruskal Wallis para probar estadísticamente según nuestros resultados cual algoritmo resulta más eficiente para cada grupo, estos análisis fueron efectuados usando el programa estadístico “R”. 3.1. Estadística Descriptiva

Luego de haber realizado los análisis correspondientes, se obtuvo que la media de los archivos considerados como de tamaño pequeño son 1,86 Mb , los de medianos 14,08 Mb y por último los grandes 43,32; el factor promedio general de compresión con el Estadístico es del 11,45% ,el factor de compresión del método de diccionario es del 20,45% y el Hibrido es del 15,46% con un promedio de redundancia utilizado del 20,11 %, distinguimos que considerando el subgrupo pequeños estos tienen un promedio de compresión, con Estadístico del 5,46%, con Diccionario del 7,09% y un 6,56% con el Hibrido, con un factor de redundancia promedio para estos últimos de 9,08%, considerando el subgrupo Medianos, tenemos un promedio de compresión para estadístico del 5,98%, con Diccionario del 7,96% y un 8,54% con el hibrido, con un factor de redundancia del 11,64%, con el subgrupo Grandes tenemos un factor de compresión con Diccionario del 30,05%, con Estadísticos un factor de compresión del 20,90% y con Híbridos un factor de compresión del 24,69%, todos estos con un factor de redundancia del 45,99%, siendo esto últimos los que presentan un notable valor de redundancia.
Los tiempos Promedio de Compresión y Descompresión por otro lado para los considerados en el Grupo de Péquenos con el algoritmo de Diccionario son del 0,874 s y 0,589 s, para Estadístico son de 0,546 s y 0,453 s y para Hibrido del 0,675 s, y 0,467 s respectivamente. Por otro lado para los Medianos los tiempos promedio de Compresión y Descompresión son para Diccionario de 1,678 s y 0,789, para Estadístico de 0,987 s y 0,967s , y por ultimo de para Hibrido de 1,245 s y 1,045 s respectivamente.

3.2. Estadística Inferencial
Para probar estadísticamente el algoritmo más eficiente para cada grupo de archivos se procedió a efectuar una prueba de homogeneidad de hipótesis usando la prueba Levene, el cual dió como resultado que las varianzas de cada grupo no son homogéneas. Luego, se procedió a hacer una prueba de diferencia de medias usando la prueba Kruskall-Wallis, la cual dió como resultado que sí hay diferencia significativa de medias.
Nivel de Redundancia 1
Prueba de Hipótesis para factor de compresión con un nivel de redundancia de 0 y 0.33 de los archivos que fueron sometidos a los tres diferentes algoritmos
H0: mu1=m2=m3
Ho: mu1 ≠m2≠m3
El valor obtenido de p es 2.2e-16 donde existe evidencia estadística para rechazar la hipótesis nula

Nivel de Redundancia 2
Prueba de Hipótesis para factor de compresión con un nivel de redundancia de 0.33 y 0.66 de los archivos que fueron sometidos a los tres diferentes algoritmos
H0: mu1=m2=m3
Ho: mu1 ≠m2≠m3
El valor obtenido de p es 7.192e-15 donde existe evidencia estadística para rechazar la hipótesis nula

Nivel de Redundancia 3
Prueba de Hipótesis para factor de compresión con un nivel de redundancia de 0.6 y 0.1 de los archivos que fueron sometidos a los tres diferentes algoritmos
H0: mu1=m2=m3
Ho: mu1 ≠m2≠m3
El valor obtenido de p es 1.151e-13 donde existe evidencia estadística para rechazar la hipótesis nula

Correlación, Relación Lineal para archivos de nivel 1 en compresores de tipo Diccionario

Hipótesis de correlación
H0:r=0
H0:r≠0

El valor obtenido es de 0.971875 por lo que existe evidencia estadística para no rechazar la hipótesis nula y afirmamos que el coeficiente de correlación no es significativamente diferente de 0

Relación Lineal

H0:β=0
H0:β≠0

En esta relación se ha estimado en un R = 0.01958 , que indica una relación negativa entre el tamaño del archivo y el tiempo de compresión

Para la muestra correspondiente a los archivos de tipo pequeños con un nivel de redundancia de tipo 1 se puede concluir que existe una relación negativa entre el tamaño del archivo y el tiempo de compresión lo que significa que ha mayor tamaño del archivo mayor será el tiempo de compresión

En vista de los resultados anteriores, se optó por efectuar regresiones entre las variables “Tiempo de Compresión” y “Porcentaje de compresión”.
Figura 1: Regresión lineal para archivos medianos con poca redundancia, comprimidos con algoritmos de diccionario

Figura 1: Regresión lineal para archivos medianos con poca redundancia, comprimidos con algoritmos de diccionario

Figura 2: Regresión lineal para archivos pequeños con redundancia, comprimidos con algoritmos híbridos

Figura 2: Regresión lineal para archivos pequeños con redundancia, comprimidos con algoritmos híbridos

Figura 3: Regresión lineal para archivos medianos con poca redundancia, comprimidos con algoritmos estadísticos

Figura 3: Regresión lineal para archivos medianos con poca redundancia, comprimidos con algoritmos estadísticos

En los gráficos anteriores se puede ver la tendencia de las variables Tiempo de compresión y Porcentaje de compresión. Los modelos de regresión usados fueron estimados con un 95 % de confianza

3. Discusión y Conclusiones.

En la presente investigación se consideraron una variedad de variables que determinarían un factor importante a la hora de comprimir un archivo, como el tamaño, la redundancia de información y el algoritmo utilizado, En el transcurso del experimento pudimos notar que en los archivos pequeños muy por debajo del 1 mb, sucedía algo peculiar el archivo al ser comprimido pesaba más del tamaño original, dándose a notar que su factor de redundancia era muy pequeño y pudimos inferir que al generar los datos de compresión que empaquetan los archivos estos aumentaban el tamaño original, nada beneficioso para la compresión.
Por otro lado la velocidad promedio de los algoritmos Hibrido y Diccionario en el Grupo Considerado los Medianos(5-15 mb) está por debajo de la velocidad de Compresión y Descompresión del algoritmo Estadístico, en este caso recomendamos el uso del ultimo mencionado. En el Caso del grupo considerados Grandes, establecemos una gran ventaja al usar algoritmo Hibrido tanto en tiempo de Compresión y Descompresión , de los demás, ya que pudimos notar que existe mucha evidencia estadística para aseverar esto.

4. Referencias bibliográficas

[1] Baint L. & Dick R. (2008). Adaptive Filesystem Compression for Embedded Systems. Design an Test in Europe, 1374 – 1377.

[2] Chakraborty D., Mukherjee J. & Gosh S. (2010). An Efficient Data Compression Algorithm Using Differential Feature Extraction. Department of Computer Science & Engineering and Information Technology, St. Thomas College of Engineering &Technology, Kolkata, West Bengal, India.

[3] Campos A. (2000) . Compression Programming. Recuperado el 1 de Junio del 2012. Disponible en http://www.arturocampos.com/cp_ch0.htm

[4] Lekatsas H. & Wolf W. (1998). Code Compression for Embedded Systems . DAC ’98 Proceedings of the 35th Annual Design Automation Conference, 516 – 521.

[5] Simpson M. (2003). Analysis of Compression Techniques for Program Data. Clemson : Clemson University.

[6] Sundaresan K. & Mahapatra N. (2003). Code Compression Techniques for Embedded Systems and their Effectiveness. VLSI, 2003.Proceedings.IEEE Computer Society Annual Symposium on, 262 – 263.

[7] Bratko A. , Cormack G. , Filipic V. (2006). Spam Filtering Using Statistical Data Compression models. Journal of Machine Learning Research 7, 2673 – 2698.

[8] R Development Core Team (2010). R: A language and environment for statistical computing. R Foundation for Statistical computing, Vienna, Austria.