We present a survey of results concerning Lempel–Ziv data compression on？parallel and distributed systems, starting from the theoretical approach to parallel time？complexity to conclude with the practical goal of designing distributed algorithms with low？communication cost. Storer’s extension for image compression is also discussed.
References
[1]
Lempel, A.; Ziv, J. On the Complexity of Finite Sequences. IEEE Trans. Inf. Theory 1976, 22, 75–81.
[2]
Lempel, A.; Ziv, J. A Universal Algorithm for Sequential Data Compression. IEEE Trans. Inf. Theory 1977, 23, 337–343.
[3]
Ziv, J.; Lempel, A. Compression of Individual Sequences via Variable-Rate Coding. IEEE Trans. Inf. Theory 1978, 24, 530–536.
[4]
Crochemore, M.; Rytter, W. Efficient Parallel Algorithms to Test Square-freeness and Factorize Strings. Inf. Proc. Lett. 1991, 38, 57–60.
[5]
De Agostino, S. Parallelism and Dictionary-Based Data Compression. Inf. Sci. 2001, 135, 43–56.
[6]
De Agostino, S. P-complete Problems in Data Compression. Theor. Comput. Sci. 1994, 127, 181–186.
[7]
De Agostino, S.; Silvestri, R. Bounded Size Dictionary Compression: SCk-Completeness and NC Algorithms. Inf. Comput. 2003, 180, 101–112.
[8]
Cinque, L.; De Agostino, S.; Lombardi, L. Scalability and Communication in Parallel Low-Complexity Lossless Compression. Math. Comput. Sci. 2010, 3, 391–406.
[9]
De Agostino, S. Almost Work-Optimal PRAM EREW Decoders of LZ-Compressed Text. Parallel Proc. Lett. 2004, 14, 351–359.
[10]
Belinskaya, D.; De Agostino, S.; Storer, J.A. Near Optimal Compression with respect to a Static Dictionary on a Practical Massively Parallel Architecture. Proceedings IEEE Data Compression Conference 1995; IEEE Computer Society: Washington, DC, USA, 1995; pp. 172–181.
De Agostino, S. LZW versus Sliding window Compression on a Distributed System: Robustness and CommunicationUnpublished work. 2011.
[13]
Storer, J.A. Lossless Image Compression using Generalized LZ1-Type Methods. Proceedings IEEE Data Compression Conference 1996; IEEE Computer Society: Washington, DC, USA, 1996; pp. 290–299.
[14]
Storer, J.A.; Helfgott, H. Lossless Image Compression by Block Matching. Comput. J. 1997, 40, 137–145.
[15]
Storer, J.A.; Szimansky, T.G. Data Compression via Textual Substitution. J. ACM 1982, 24, 928–951.
[16]
Rodeh, M.; Pratt, V.R.; Even, S. Linear Algorithms for Compression via String Matching. J. ACM 1980, 28, 16–24.
[17]
Mc Creight, E.M. A Space-Economical Suffix Tree Construction Algorithm. J. ACM 1976, 23, 262–272.
[18]
Welch, T.A. A Technique for High-Performance Data Compression. IEEE Comput. 1984, 17, 8–19.
[19]
De Agostino, S.; Storer, J.A. On-Line versus Off-line Computation for Dynamic Text Compression. Inf. Proc. Lett. 1996, 59, 169–174.
[20]
De Agostino, S.; Silvestri, R. A Worst Case Analisys of the LZ2 Compression Algorithm. Inf. Comput. 1997, 139, 258–268.
[21]
Storer, J.A. Data Compression: Methods and Theory. Comput. Sci. Press 1988, 413.
[22]
Fiala, E.R.; Green, D.H. Data Compression with Finite Windows. Commun. ACM 1988, 32, 490–505.
[23]
Waterworth, J.R. Data Compression System. U.S. Patent 4,701,745, 1987.
[24]
Brent, R.P. A Linear Algorithm for Data Compression. Aust. Comput. J. 1987, 19, 64–68.
[25]
Whiting, D.A.; George, G.A.; Ivey, G.E. Data Compression Apparatus and Method. U.S. Patent 5,016,009, 1991.
[26]
Gailly, J.; Adler, M. The Gzip homepage. Available online: http://www.gzip.org (accessed on 6 September 2011).
[27]
Hartman, A.; Rodeh, M. Optimal Parsing of Strings. In Comb. Algorithms Words; Apostolico, A., Galil, Z., Eds.; Springer: Berlin, Germany, 1985; pp. 155–167.
[28]
Crochemore, M.; Rytter, W. Jewels of Stringology; World Scitific Publishing Co.: Singapore, 2003.
[29]
De Agostino, S. Bounded Size Dictionary Compression: Relaxing the LRU Deletion Heuristic. Int. J. Found. Comput. Sci. 2006, 17, 1273–1280.
[30]
Farach, M.; Muthikrishnan, S. Optimal Parallel Dictionary Matching and Compression. Proc. SPAA 1995, 244–253.
[31]
De Agostino, S. Work-Optimal Parallel Decoders for LZ2 Data Compression. Proceedings IEEE Data Compression Conference 2000; IEEE Computer Society: Washington, DC, USA, 2000; pp. 393–399.
Rice, R.F. Some Practical Universal Noiseless Coding Technique—part I. Technical Report JPL-79-22; Jet Propulsion Laboratory: Pasadena, CA, USA, 1979.
[40]
Cinque, L.; De Agostino, S.; Liberati, F.; Westgeest, B. A Simple Lossless Compression Heuristic for Grey Scale Images. Int. J. Found. Comput. Sci. 2005, 16, 1111–1119.
[41]
Cinque, L.; De Agostino, S.; Lombardi, L. Binary Image Compression via Monochromatic Pattern Substitution: Effectiveness and Scalability. Proc. Prague Stringol. Conf. 2010, 103–115.
