Sequence Partitioning and Compression Rate

Abstract

— In the lossless data compression, the process of splitting a data sequence into appropriate subsequences has a substantial role in improving compression rate. This study theoretically investigates effects of data sequence partition on the overall compression rate of data sets. For this proposes, we show that it is always possible to find a partition of data sequence such that the entropy rate at each subsequence is lower than entropy rate of original sequences. This motivates our work to figure out the overall compression rate of the partitioned data sequences. Then, the effects of sequence partitioning on overall compression rate are discussed to explore an optimal partitioning strategy. Finally, an optimization problem for the optimal partitioning of a data sequences is stated for future works

Keywords

• -

References

1. -
2. C.E. Shannon and Weaver W., The Mathematical Theory of Communication, Illinois, 1949.
3. T.M. Cover and J.A. Thomas, Elements of Information Theory, Wiley India Pvt Ltd., 1991.
4. D.A. Huffman, “A Method for the Construction of Minimum Redundancy Codes”, Proceedings of the IRE, 40, 1952, pp. 1098-1101. J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression”, IEEE Transactions on Information Theory, 23, 1977, pp. 337-342.
5. J. Ziv and A. Lempel, “Compression of Individual Sequences Via Variable-Rate Coding”, IEEE Transactions on Information Theory, 24, 1978, pp. 530--536.
6. R.R. Coifman, M.V. Wickerhauser, “Entropy-Based Algorithms for Best Basis Selection”, IEEE Transactions on Information Theory, 38, 1992, pp.713-718.
7. K. Skretting, J.H. Husoy, S.O. Aase , “Improved Huffman coding using recursive splitting”, Norwegian Signal Processing Society Conference (NORSIG-99),Norway, 1999. [8]
8. T.A. Welch, “A Technique for High-Performance Data Compression”, Computer, 1984, pp. 8-18,.

9. R.M. Hassan and B. Nath, “Data Compression Using Huffman Coding A Novel Approach”, International Conference on Applied Computing (IADIS-2005), Portugal,2005.
10. T. Bonny, J. Henkel, “Instruction Splitting for Efficient Code Compression”, Design Automation Conference, 2007. DAC '07. 44th ACM/IEEE, 2007, pp. 646-651.