ANÁLISIS TEÓRICO DEL ALGORITMO DE COMPRESIÓN LLRUN PARA LA COMPRESIÓN DE CADENAS DE BITS SPARSE

  • Carlos Rincón Universidad del Zulia
  • David Bracho Universidad del Zulia
  • Alfredo Acurero Universidad del Zulia
Palabras clave: compresión, cadenas de bits sparse, LLRUN, rendimiento

Resumen

La presente investigación tuvo como finalidad realizar un análisis teórico sobre el funcionamiento del algoritmo de compresión LLRUN, para determinar su posible uso en la compresión de cadenas de bits sparse. Fraenkel y Klein (1985) plantearon un método para comprimir cadenas de bits sparse mezclando las técnicas run length encoding (RLE), Gamma coding y Huffman coding, mostrando un rendimiento prometedor. El resultado del presente estudio permitió determinar que LLRUN ofrece una relación de compresión teórica entre 87,5% y 50%, siendo una herramienta efectiva para la compresión de cadenas de bits sparse.

Citas

Elias, P. (1975). Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory. Volumen 21, edición 2. (194-203).

Fraenkel, A. y Klein, S. (1985). Novel compression of Sparse Bit-Strings-Preliminary report. En Apostolico, A. y Galil, Z. (editors). Combinatorial Algorithms on Words. Volumen 12, NATO ASI Series F. Estados Unidos. Springer-Verlag.

Golomb, S. (1966). Run-length encodings (Corresp.). Information Theory, IEEE Transactions. Volumen 12, número 3. (Pp. 399-401).

Huffman, D. (1952). A method for the construction of minimum redundancy codes. Proceedings of the IRE. Volumen 40, edición 9. (Pp. 1098-1101).

Rincón, C.; Rodríguez, D.; Acurero, A.; Bracho, D. y Jakymec, J. (2009). Algoritmo de compresión probabilístico basado en la teoría de la información. Octava Conferencia Iberoamericana en Sistemas, Cibernética e Informática, CISCI 2009. Julio, Estados Unidos.

Rincón, C.; Bracho, D.; Acurero, A. (2012). Efecto del tamaño del alfabeto en el rendimiento de un algoritmo de compresión probabilístico. Revista Enl@ce. Volumen 13, número 3. (Pp. 83-93).

Shannon, C. (1948). A mathematical theory of communication. The Bell Systems Technical Journal. Volumen 27. (Pp. 379-423, 623-656).
Publicado
2015-07-02
Sección
Artículos