RECURSIVE GROUP CODING WITH DYNAMIC FREQUENCY MODELING

Н. В. Кожемякина, Н. Н. Пономаренко

Abstract


Task of entropy group coding of data for reduce of its statistical redundancy on base of recursive group coding is considered. Recursive group coding provides effective coding of symbols of large alphabets. It is fast and in some cases more effective alternative of such methods as arithmetical coding and Huffman coding. However applications of recursive group coding are restricted by usage of statistical frequency modeling. For such modeling frequencies (or probabilities) of symbols are calculated for entire text as well as information about size sand contents of groups are stored in compressed file. In this work a modification of recursive group coding are proposed which is able effectively compress texts statistically heterogeneous by frequency characteristics. A model for synthesizing of test texts is considered. Also a new metric for estimates of uniformity of a given text is proposed. It is shown that for considered test texts the proposed modifications of recursive group coding provide up to 65% less compressed data size than conventional method.

Keywords


recursive group coding, entropy coding, arithmetical coding, Huffman coding

References


Salomon, D. Data Compression - The Complete Reference. Springer-Verlag, 2004. 898 p.

Cleary, J., Witten, I. Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications., 1984, vol. 32, pp. 396-402.

Burrows, M., Wheeler, D. A block sorting lossless data compression algorithm. Technical Report 124: Digital Equipment Corporation. Systems Research Center Publ., 1994. 24 p.

Rissanen, J. Generalized kraft inequality and arithmetic coding. IBM J. Res. Develop, 1976, vol. 20, pp. 198-203.

Huffman, D. A. A method for the construction of minimum-redundancy codes. Proceedings of Institute of Radio Engineering, 1952, vol. 40, no. 9, pp. 1098- 1101

Ponomarenko, N., Lukin, V., Egiazarian, K., Astola, J. Fast recursive coding based on grouping of Symbols. Telecommunications and Radio Engineering, 2009, vol. 68, no. 20, pp. 1857-1863.

Ponomarenko, N. N., Kozhemyakina, N. V., Lukin, V. V. Metod entropiinogo rekursivnogo gruppovogo kodirovaniya [Method of entropy recursive group coding]. Radіoelektronnі і komp’yuternі sistemi, 2014, vol. 3, no. 67, pp. 20-26.

Kozhemyakina, N. V., Ponomarenko, N. N., Zelenskii, A. A. Sravnitel'nyi analiz effektivnosti metodov szhatiya dannykh pri kodirovanii simvolov bol'shikh alfavitov [Comparative analysis of data compression methods for encoding of symbols of large alphabets]. Sistemi obrobki іnformatsії, 2015, vol. 9, no. 134, pp. 74-78.

Kozhemyakina, N. V., Lukin, V. V., Ponomarenko, N. N., Miroshnichenko, A. I. JPEG szhatie izobrazhenii s primeneniem rekursivnogo gruppovogo kodirovaniya [JPEG image compression using recursive group coding]. Radіoelektronnі і komp’yuternі sistemi, 2015, vol. 3, no. 6,3 pp. 77-81.

Kozhemiakina, N., Lukin, V., Ponomarenko, N., Akulynichev A., Egiazarian, K., Astola, J. Method of data compression for traffic monitoring. IEEE Second International Scientific-Practical Conference «Problems of Infocommunications Science and Technology (PIC S&T – 2015)», Kharkov, Ukraine, 2015, pp. 153-156.

Ponomarenko, N. N., Kozhemyakina, N. V. Rekursivnoe gruppovoe kodirovanie s kolichestvom i razmerami grupp, ne zavisyashchimi ot kodiruemykh dannykh [Recursive group coding with fixed number and sizes of groups]. Radіoelektronnі і komp’yuternі sistemi, 2015, vol. 2, no. 72, pp. 112-115.

The WinRar committee home page: Data compression programs. Available at: http://www.rarlab.com (accessed 05.06.2016).

Kullback, S., Leibler, R. On information and sufficiency. The Annals of Mathematical Statistics, 1951, vol. .22, no. 1, pp. 79-86.




DOI: https://doi.org/10.32620/reks.2016.4.02

Refbacks

  • There are currently no refbacks.