On the bit-complexity of Lempel-Ziv compression

ABSTRACT

One of the most famous and investigated lossless data-compression schemes is the one introduced by Lempel and Ziv about 30 years ago [37]. This compression scheme is known as "dictionary-based compressor" and consists of squeezing an input string by replacing some of its substrings with (shorter) codewords which are actually pointers to a dictionary of phrases built as the string is processed. Surprisingly enough, although many fundamental results are nowadays known about the speed and effectiveness of this compression process (see e.g. [23, 28] and references therein), "we are not aware of any parsing scheme that achieves optimality when the LZ77-dictionary is in use under any constraint on the codewords other than being of equal length" [28, pag. 159]. Here optimality means to achieve the minimum number of bits in compressing each individual input string, without any assumption on its generating source. In this paper we investigate three issues pertaining to the bit-complexity of LZ-based compressors, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space. These theoretical results will be sustained by some experiments that will compare our novel LZ-based compressors against the most popular compression tools (like gzip, bzip2) and state-of-the-art compressors (like the booster of [14, 13]).

REFERENCES

• 1: Amihood Amir , Gad M. Landau , Esko Ukkonen, Online timestamped text indexing, Information Processing Letters, v.82 n.5, p.253-259, June 15, 2002 [doi>10.1016/S0020-0190(01)00275-7]
• 2: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.295-304, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301323]
• 3: József Békési , Gábor Galambos , Ulrich Pferschy , Gerhard J. Woeginger, Greedy algorithms for on-line data compression, Journal of Algorithms, v.25 n.2, p.274-289, Nov. 1997 [doi>10.1006/jagm.1997.0885]
• 4: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 5: R. Cilibrasi and P. M. B. Vitányi. Clustering by compression. IEEE Transactions on Information Theory, 51(4):1523--1545, 2005.
• 6: M. Cohn , Roger I. Khazan, Parsing with suffix and prefix dictionaries, Proceedings of the Conference on Data Compression, p.180, March 31-April 03, 1996
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: Graham Cormode , S. Muthukrishnan, Substring compression problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Maxime Crochemore , Lucian Ilie , W. F. Smyth, A Simple Algorithm for Computing the Lempel Ziv Factorization, Proceedings of the Data Compression Conference, p.482-488, March 25-27, 2008 [doi>10.1109/DCC.2008.36]
• 10: G. Della Penna, F. Mignosi, A. Langiu, and A. Ulisse. On dictionary-symbolwise data compression. Personal Communication, 2008.
• 11: P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194--203, 1975.
• 12: P. Fenwick. Universal codes. In Lossless Compression Handbook, pages 55--78. Academic Press, 2003.
• 13: Paolo Ferragina , Raffaele Giancarlo , Giovanni Manzini, The engineering of a compression boosting library: theory vs practice in BWT compression, Proceedings of the 14th conference on Annual European Symposium, p.756-767, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_67]
• 14: Paolo Ferragina , Raffaele Giancarlo , Giovanni Manzini , Marinella Sciortino, Boosting textual compression in optimal linear time, Journal of the ACM (JACM), v.52 n.4, p.688-713, July 2005 [doi>10.1145/1082036.1082043]
• 15: P. Ferragina and G. Navarro. Site pizza&chili (http://pizzachili.di.unipi.it or http://pizzachili.dcc.uchile.cl).
• 16: E. R. Fiala , D. H. Greene, Data compression with finite windows, Communications of the ACM, v.32 n.4, p.490-505, April 1989 [doi>10.1145/63334.63341]
• 17: T. Gagie and G. Manzini. Space-conscious compression. In Procs MFCS, LNCS 4708, Springer, pages 206--217, 2007.
• 18: Richard F. Geary , Rajeev Raman , Venkatesh Raman, Succinct ordinal trees with level-ancestor queries, ACM Transactions on Algorithms (TALG), v.2 n.4, p.510-534, October 2006 [doi>10.1145/1198513.1198516]
• 19: Gzip home page. http://www.gzip.org.
• 20: J. Katajainen , T. Raita, An approximation algorithm for space-optimal encoding of a text, The Computer Journal, v.32 n.3, p.228-237, June 1989 [doi>10.1093/comjnl/32.3.228]
• 21: Jyrki Katajainen , Timo Raita, An analysis of the longest match and the greedy heuristics in text encoding, Journal of the ACM (JACM), v.39 n.2, p.281-294, April 1992 [doi>10.1145/128749.128751]
• 22: S. T. Klein. Efficient optimal recompression. Computer Journal, 40(2/3):117--126, 1997.
• 23: S. Rao Kosaraju , Giovanni Manzini, Compression of Low Entropy Strings with Lempel--Ziv Algorithms, SIAM Journal on Computing, v.29 n.3, p.893-911, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539797331105]
• 24: M. Lewenstein, V., Mäkinen, and S. J. Puglisi. Personal communications.
• 25: Yossi Matias , Süleyman Cenk Şahinalp, On the optimality of parsing in dynamic dictionary based data compression, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.943-944, January 17-19, 1999, Baltimore, Maryland, United States
• 26: E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257--276, 1985.
• 27: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 28: N. Rajpoot and C. Sahinalp. Handbook of Lossless Data Compression, chapter Dictionary-based data compression, pages 153--167. Academic Press, 2002.
• 29: David Salomon, Data Compression: The Complete Reference, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 30: E. J. Schuegraf and H. S. Heaps. A comparison of algorithms for data base compression by use of fragments as language elements. Information Storage and Retrieval, 10(9--10):309319, 1974.
• 31: M. E. Gonzalez Smith , J. A. Storer, Parallel algorithms for data compression, Journal of the ACM (JACM), v.32 n.2, p.344-373, April 1985 [doi>10.1145/3149.3152]
• 32: W. Szpankowski. Asymptotic properties of data compression and suffix trees. IEEE Transactions on Information Theory, 39(5):1647--1659, 1993.
• 33: Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996 [doi>10.1145/234752.234753]
• 34: Dan E. Willard, Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree, SIAM Journal on Computing, v.29 n.3, p.1030-1049, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539797322425]
• 35: Ian H. Witten , Timothy C. Bell , Alistair Moffat, Managing Gigabytes: Compressing and Indexing Documents and Images, John Wiley & Sons, Inc., New York, NY, 1994
• 36: J. Ziv. Classification with finite memory revisited. IEEE Transactions on Information Theory, 53(12):4413--4421, 2007.
• 37: J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transaction on Information Theory, 23:337--343, 1977.
• 38: J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5):530--536, 1978.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression