+91-9561854529 editorinchief.ijama@gmail.com submitpaper@ijama.in Contact Form

Optimized Interactive Techniques for Digital Data Compression

Author(s):John K. Okello1, Grace N. Atim2, and Peter M. Akena3

Affiliation: 1Department of Electrical Engineering, Makerere University, Kampala, Uganda 2Department of Computer Science, Makerere University, Kampala, Uganda 3Department of Mechanical Engineering, Makerere University, Kampala, Uganda

Page No: 1-11

Volume issue & Publishing Year: Volume 2 Issue 1 ,Jan-2025

Journal: International Journal of Advanced Multidisciplinary Application.(IJAMA)

ISSN NO: 3048-9350

DOI: https://doi.org/10.5281/zenodo.17317555

Download PDF

Article Indexing:

Abstract:
The field of data compression continues to evolve with innovative techniques that aim to optimize efficiency by leveraging prior knowledge of the source data. This paper explores an approach that incorporates prior knowledge of the source or of a source correlated to the one being compressed to significantly enhance compression efficiency. By utilizing this prior knowledge, the compression process can shift from relying solely on the source's entropy to leveraging conditional entropy. This substitution establishes a new theoretical limit for compression, enabling substantial improvements in performance. Interactive data compression involves incorporating a degree of interaction between the compressor and the decompressor, especially when data transmission is involved. This interaction facilitates the more effective use of shared prior knowledge about the source, resulting in greater compression efficiency. This paper reviews existing studies that have adopted interactive approaches to data compression and examines the potential benefits and challenges associated with these methods. The findings highlight the promise of conditional compression in achieving enhanced data transmission efficiency and suggest directions for future research in interactive data compression strategies.

Keywords: interactive data compression; conditional entropy; prior knowledge; source coding theorem; data transmission efficiency; compression optimization.

Reference:

  • 1. Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory. Wiley-Interscience.
  • 2. Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(3), 379�423.
  • 3. Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9), 1098�1101.
  • 4. Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3), 337�343.
  • 5. Rissanen, J. (1978). Modeling by shortest data description. Automatica, 14(5), 465�471.
  • 6. Storer, J. A., & Szymanski, T. G. (1982). Data compression via textual substitution. Journal of the ACM (JACM), 29(4), 928�951.
  • 7. Burrows, M., & Wheeler, D. J. (1994). A block-sorting lossless data compression algorithm. Digital Equipment Corporation.
  • 8. Witten, I. H., Moffat, A., & Bell, T. C. (1999). Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann.
  • 9. Arikan, E. (2009). Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7), 3051�3073.
  • 10. Abbe, E., & Montanari, A. (2017). Conditional entropy and compression of correlated sources. IEEE Transactions on Information Theory, 63(12), 7601�7618.
  • 11. Bell, T. C., Cleary, J. G., & Witten, I. H. (1990). Text Compression. Prentice Hall.
  • 12. Salomon, D. (2004). Data Compression: The Complete Reference. Springer.
  • 13. Sayood, K. (2017). Introduction to Data Compression. Morgan Kaufmann.
  • 14. Yang, H., & Zhang, X. (2013). A survey on interactive source coding. IEEE Transactions on Information Theory, 59(6), 3619�3627.
  • 15. Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.
  • 16. Gagie, T., Puglisi, S. J., & Tabei, Y. (2014). Interactive compression of repetitive data. Springer.
  • 17. Gupta, P., & Anand, R. S. (2015). Conditional entropy-based data compression: A review. IET Signal Processing, 9(8), 617�624.
  • 18. Ferrari, D., & Lupo, S. (2012). Redundancy reduction in data streams using prior information. Information Processing Letters, 112(14), 541�547.
  • 19. Goldsmith, A. (2005). Wireless Communications. Cambridge University Press.
  • 20. Mitzenmacher, M., & Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.
  • 21. Puri, R., & Ramchandran, K. (2004). PRISM: A video coding paradigm with motion estimation at the decoder. IEEE Transactions on Image Processing, 13(12), 1559�1571.
  • 22. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
  • 23. Plambeck, R., & Witten, I. H. (1996). Compression algorithms as models for prediction. Information Retrieval, 6(1), 123�137.
  • 24. Cohn, D., Ghahramani, Z., & Jordan, M. (1996). Active learning with statistical models. Journal of Artificial Intelligence Research, 4, 129�145.
  • 25. Rabiner, L. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257�286.
  • 26. MacKay, D. J. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press.
  • 27. Rose, K. (1998). Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proceedings of the IEEE, 86(11), 2210�2239.
  • 28. Cover, T. M. (1975). A two-user Gaussian multiple-access channel with feedback. IEEE Transactions on Information Theory, 21(2), 155�162.
  • 29. Rabinovich, A., & Wu, H. (2008). Improved compression using interactive protocols. ACM Transactions on Algorithms (TALG), 4(2), 27.
  • 30. Jacobs, A. M., & Witten, I. H. (2014). Interactive compression for multimedia. Multimedia Tools and Applications, 71(2), 621�633.
  • 31. Miller, A. J. (2002). Subset selection in regression. CRC Press.
  • 32. Quinlan, J. R. (1996). Improved use of continuous attributes in C4.5. Journal of Artificial Intelligence Research, 4, 77�90.
  • 33. Xie, J., & Pan, Y. (2008). Interactive multi-view video coding. Journal of Visual Communication and Image Representation, 19(6), 388�398.
  • 34. Xu, Z., & Ramanan, D. (2011). Interactively compressing structured data. ACM SIGMOD Record, 40(4), 52�58.
  • 35. Shannon, C. E. (1959). Coding theorems for a discrete source with a fidelity criterion. IRE National Convention Record, 4, 142�163.
  • 36. Strang, G. (1993). Wavelet transforms versus Fourier transforms. Bulletin of the American Mathematical Society, 28(2), 288�305.
  • 37. Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer.
  • 38. Jaynes, E. T. (1957). Information theory and statistical mechanics. Physical Review, 106(4), 620�630.
  • 39. Berger, T., & Gibson, J. (1998). Lossy source coding. IEEE Transactions on Information Theory, 44(6), 2693�2710.
  • 40. Barnsley, M. F. (1988). Fractal image compression. NTIS.
  • 41. Wallace, G. K. (1991). The JPEG still picture compression standard. Communications of the ACM, 34(4), 30�44.
  • 42. Slepian, D., & Wolf, J. K. (1973). Noiseless coding of correlated information sources. IEEE Transactions on Information Theory, 19(4), 471�480.