Geodesic
Analytical review of compression algorithms of digital information
Problemy fiziki, matematiki i tehniki, no. 2 (2016), pp. 77-83.

Voir la notice de l'article provenant de la source Math-Net.Ru

A brief review and analysis of existing algorithms for compression of digital information are presented. The advantages and disadvantages of data compression algorithms depending on the type of digital information are considered. The software implemented on the basis of the considered algorithms is specified.
Mots-clés : information, compression, data compression, image compression, compression algorithm
Keywords: algorithm, archive program, context modeling, encoding of information. 
@article{PFMT_2016_2_a11,
     author = {V. V. Kirichenko},
     title = {Analytical review of compression algorithms of digital information},
     journal = {Problemy fiziki, matematiki i tehniki},
     pages = {77--83},
     publisher = {mathdoc},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PFMT_2016_2_a11/}
}
TY  - JOUR
AU  - V. V. Kirichenko
TI  - Analytical review of compression algorithms of digital information
JO  - Problemy fiziki, matematiki i tehniki
PY  - 2016
SP  - 77
EP  - 83
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PFMT_2016_2_a11/
LA  - ru
ID  - PFMT_2016_2_a11
ER  - 
%0 Journal Article
%A V. V. Kirichenko
%T Analytical review of compression algorithms of digital information
%J Problemy fiziki, matematiki i tehniki
%D 2016
%P 77-83
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PFMT_2016_2_a11/
%G ru
%F PFMT_2016_2_a11
V. V. Kirichenko. Analytical review of compression algorithms of digital information. Problemy fiziki, matematiki i tehniki, no. 2 (2016), pp. 77-83. http://geodesic.mathdoc.fr/item/PFMT_2016_2_a11/

[1] R. V. L. Hartley, “Transmission of information”, Bell System Technical Journal, 7:3 (1928), 535–563 | DOI

[2] C. E. Shannon, “A mathematical theory of communication”, The Bell System Technical Journal, 27 (1948), 379–423 | DOI | MR | Zbl

[3] D. A. Huffman, “A method for the construction of minimum redundancy codes”, J. Proc. of IRE, 40 (1952), 1098–1101 | DOI | Zbl

[4] J. Ziv, A. Lempel, “A universal algorithm for sequential data compression”, IEEE Transactions on Information Theory, 23:3 (1977), 337–343 | DOI | MR | Zbl

[5] J. Ziv, A. Lempel, “Compression of individual sequences via variable-rate coding”, IEEE Transactions on Information Theory, 24:5 (1978), 530–536 | DOI | MR | Zbl

[6] T. A. Welch, “A technique for high-performance data compression”, IEEE Computer, 17:6 (1984), 8–19 | DOI

[7] DEFLATE Compressed Data Format Specification v.l.3 (RFC 1951), , IETF Tools (Date of access: 28.09.2015) https://tools.ietf.org/html/rfc1951

[8] D. S. Vatolin i dr., Metody szhatiya dannykh. Ustroistvo arkhivatorov, szhatie izobrazhenii i video, DIALOG-MIFI, M., 2002, 384 pp.

[9] J. J. Rissanen, G. G. Langdon, “Universal modeling and coding”, IEEE Transactions on Information Theory, 27:1 (1981), 12–23 | DOI | MR | Zbl

[10] J. G. Cleary, I. H. Witten, “Data compression using adaptive coding and partial string matching”, IEEE Transactions on Communications, 3:4 (1984), 396–402 | DOI

[11] C. Bloom, Solving the problems of context modeling, , California Institute of Technology (Date of access: 28.09.2015) http://www.cbloom.com/papers/ppmz.zip

[12] D. F. Shkarin, “Povyshenie effektivnosti algoritma RRM”, Problemy peredachi informatsii, 34:3 (2001), 44–54

[13] M. Burrows, D. J. Wheeler, A Blocksorting Lossless Data Compression Algorithm, SRC Research Report 124 , HP Labs, Digital Systems Research Center, Palo Alto, 1994 (Date of access: 29.09.2015) http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf

[14] A. Brown, Digital preservation guidance note 5: image compression, , The national archives, 2003 (Date of access: 29.09.2015) https://www.nationalarchives.gov.uk/documents/selecting-file-formats.pdf

[15] B. Ya. Ryabko, “Data Compression by Means of a “Book Stack””, Problems of Information Transmission, 16:4 (1980), 265–269 | MR | Zbl

[16] P. M. Fenwick, “Block sorting text compression”, Papers from the Australasian Computer Science Conference, ACSC'96 (Melbourne, Australia, Feb. 1996), Melbourne, 1996, 193–202

[17] T. S. Bell, I. H. Witten, J. G. Cleary, “Modeling for text compression II”, ACM Computer Survey, 24:4 (1989), 555–591

[18] V. S. Miller, M. N. Wegman, “Variations on a theme by Ziv and Lempel”, Combinatorial Algorithms on Words, Papers from the conference (Berlin, 1984), NATO ASI Series, F12, ed. A. Apostolico et al., Springer-Verlag, 1984, 131–140 | MR

[19] T. C. Bell, A unifying theory and improvements for existing approaches to text compression, Dissertation, Ph. D., Dept. of Computer Science, Univ. of Canterbury, New Zealand, Canterbury, 1987, 9 pp.

[20] E. R. Fiala, D. H. Greene, “Data compression with infinite windows”, Commun. ACM, 32:4 (1989), 490–505 | DOI

[21] P. E. Bender, J. K. Wolf, “New asymptotic bounds and improvements on the Lempel-Ziv data compression algorithm”, IEEE Transactions on Information Theory, 37:3 (1991), 721–727 | DOI

[22] R. N. Williams, “An Extremely Fast ZivLempel Data Compression Algorithm”, Data Compression Conference, Papers from the conference (Snowbird, Utah, 8–11 April, 1991), 362–371

[23] M. Roden, V. R. Pratt, S. Even, “Linear algorithm for data compression via string matching”, J. ACM, 28:1 (1981), 6–24 | MR

[24] C. Bloom, New Techniques in Context Modeling and Arithmetic Encoding, (Date of access: 29.09.2015) http://www.cbloom.com/papers/context.pdf

[25] D. T. Hoang, P. M. Long, J. S. Vitter, “Multiple-dictionary compression using partial matching”, Proceedings of Data Compression Conference, Papers from the conference (Washington, DC, USA, March 1995), 272

[26] A. N. Zemlyachenko, V. V. Lukin, “Szhatie izobrazhenii bez vizualno zametnykh iskazhenii”, Radioelektronnye i kompyuternye sistemy, 2011, no. 3, 73–79

[27] Standardisation of Group 3 Facsimile apparatus for document transmission. CCITT Recommendations T.4, Fascicle VII.2, , ITU, 1980 (Date of access: 30.09.2015) https://www.itu.int/rec/dologin_pub.asp?lang=e&id=T-REC-T.4-198811-S!!PDF-E&type=items

[28] Facsimile Coding Schemes and Coding Control Functions for Group 4 Facsimile Apparatus, Recommendation T.6, Volume VII, Fascicle VII.3, , ITU (Date of access: 30.09.2015) https://www.itu.int/rec/dologin_pub.asp?lang=e&id=T-REC-T.6-198811-I!!PDF-E&type=items

[29] Nguen Din Min, Razrabotka metodiki otsenki kachestva szhatykh izobrazhenii, Dis. kand. tekhn. nauk.: 25.00.35, M., 2006, 163 pp.

[30] G. K. Wallace, “The JPEG still picture compression standard”, Communication of ACM, 34:4 (1991), 30–44 | DOI

[31] M. Narasimha, A. Peterson, “On the Computation of the Discrete Cosine Transform”, IEEE Transactionson Communications, 26:6 (1978), 934–936 | DOI | Zbl

[32] Information technology — JPEG 2000 image coding system, v. 1, Core coding system: ISO/IEC 15444-1, 2001

[33] Portable Network Grafics, (Date of access: 30.09.2015) http://libpng.org/pub/png/

[34] D. E. Walker, R. A. Amsler, “The use of machine-readable dictionaries in sublanguage analysis”, Analysis languages in restricted domains: Sublanguage description and processing, Papers from the conference (Hillsdale, NJ, USA, 1986), eds. R. Grishman et al., NJ, 1986, 69–83

[35] L. E. Baum, T. Petrie, G. Soules, N. Weiss, “A maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains”, Ann. Math. Stat., 41 (1970), 164–171 | DOI | MR | Zbl

[36] L. R. Rabiner, B. H. Juang, “An Introduction to Hidden Markov models”, IEEE ASSP Mag., 1986, Jan., 4–16 | DOI

[37] S. E. Levinson, L. R. Rabiner, M. Sondni, “An introduction to the application of the theory of probabilistic function of a Markov process to automatic speech recognition”, Bell Syst. Tech. J., 62:4 (1983), 1035–1074 | DOI | MR | Zbl

[38] D. Jagger, Fast Ziv–Lempel decoding using RISC architecture, Res. Rept., Dept. of Computer Science, Univ. of Canterbury, New Zealand, 1989

[39] M. E. Gonzalez-Smith, J. A. Storer, “Parallel algorithms for data compression”, J. ACM, 32:2 (1985), 344–373 | DOI | MR | Zbl

[40] D. M. Young, “MacWrite file formats”, Wheels for the mind, Newsletter of the Australian Apple University Consortium (University of Western Australia, Nedlands, WA 6009, Australia), Nedlands, 1985, 34

[41] R. Hunter, A. H. Robinson, “International digital facsimile coding standards”, Proceedings of the IEEE, 68:7 (1980), 854–867 | DOI

[42] M. Auslander, W. Harrison, V. Miller, M. Wegman, “PCTERM: A terminal emulator using compression”, Proceedings of the IEEE, 1985, 860–862

[43] I. H. Witten, J. Cleary, “Picture coding and transmission using adaptive modelling of quad trees”, Proceeding of the International Electrical, Electronics conference 1, Papers from the conference (Toronto, Canada, 1983), Toronto, 1983, 222–225