Fast data compression is gaining increasing importance in the re- cent times. Statistical compression methods and methods pertain- ing to textual substitution have been studied in great detail in the last few decades, however, the problem of compressing data at very high speeds with less compression trade-off still remains un- solved to a certain extent. General Purpose Graphic Processing Units (GPGPUs) are a powerful tool that allow large-scale parallel processing, owing to a large number of Streaming Multiprocessors. Recent studies on parallel methods for compression using tex- tual substitution show that considerable speed-ups can be obtained by using the Lempel-Ziv-Storer-Szymanski(LZSS)[9] lossless data compression algorithm on GPUs. In this paper, a parallel, space- efficient compression algorithm using GPGPUs for LZSS com- pression, along with a dynamic variation of the Knuth-Morris-Pratt (KMP) string-matching algorithm[2] is presented. The algorithm splits the input data into disjoint data chunks and performs com- pression on each chunk using the Dynamic KMP algorithm, inde- pendent of the compression of other chunks.

1. Ana Balevic. Parallel variable-length encoding on gpgpus. In Euro-Par 2009–Parallel Processing Workshops, pages 26–35. Springer, 2010.
2. Donald E Knuth, James H Morris, Jr, and Vaughan R Pratt. Fast pattern matching in strings. SIAM journal on computing,6(2):323–350, 1977.
3. SR Kodituwakku and US Amarasinghe. Comparison of loss- less data compression algorithms for text data. Indian journal of computer science and engineering, 1(4):416–425, 2010.
4. Adnan Ozsoy. Culzss-bit: a bit-vector algorithm for lossless data compression on gpgpus. In Proceedings of the 2014 In- ternational Workshop on Data Intensive Scalable Computing Systems, pages 57–64. IEEE Press, 2014.
5. Adnan Ozsoy and Martin Swany. Culzss: Lzss lossless data compression on cuda. In Cluster Computing (CLUSTER),2011 IEEE International Conference on, pages 403–411. IEEE, 2011.
6. Adnan Ozsoy, Martin Swany, and Anamika Chauhan. Pipelined parallel lzss for streaming data compression on gpgpus. In Parallel and Distributed Systems (ICPADS), 2012IEEE 18th International Conference on, pages 37–44. IEEE,2012.
7. Adnan Ozsoy, Martin Swany, and Arun Chauhan. Optimizing lzss compression on gpgpus. Future Generation Computer Systems, 30:170–178, 2014.
8. Akhtar Rasool and Nilay Khare. Parallelization of kmp string matching algorithm on different simd architectures: Multi- core and gpgpu's. International Journal of Computer Appli- cations, 49(11):26–28, 2012.
9. James A Storer and Thomas G Szymanski. Data compres- sion via textual substitution. Journal of the ACM (JACM),29(4):928–951, 1982.
10. Annie Yang, Hari Mukka, Farbod Hesaaraki, and Martin Burtscher. Mpc: A massively parallel compression algorithm for scientific data. In Cluster Computing (CLUSTER), 2015IEEE International Conference on, pages 381–389. IEEE,2015.
11. Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. Information Theory, IEEE Transactions on, 24(5):530–536, 1978.
12. Yuan Zu and Bei Hua. Glzss: Lzss lossless data compression can be faster. In Proceedings of Workshop on General Pur- pose Processing Using GPUs, page 46. ACM, 2014.

Lzss kmp culzss gpu gpu