Novosibirsk State University Journal of Information Technologies
Scientic Journal

ISSN 2410-0420 (Online), ISSN 1818-7900 (Print)

Switch to

All Issues >> Contents: Volume 08, Issue No 4 (2010)

Generalization of known methods of string coding
Dmitry Sergeyevich Kovalev

Novosibirsk State University

UDC code: 519.72

The first part of this paper is about Huffman coding. Its key feature is a binary tree construction. This tree defines recursive partition of alphabet set to construct prefix codes. Generalization of binary tree to q-ary tree is well known. This paper gives Huffman coding generalization for any trees. The second part of this paper defines another approach to understanding Lembel-Ziv family of algorithms. The suggestion is that these algorithms encode a mapping associated with a string, not a string itself. The string is a fixed point of encoded mapping in this case.

Key Words
enumerative coding, LZ78, LZ77, Lempel-Ziv algorithms, Huffman coding

How to cite:
Kovalev D. S. Generalization of known methods of string coding // Vestnik NSU Series: Information Technologies. - 2010. - Volume 08, Issue No 4. - P. 5-14. - ISSN 1818-7900. (in Russian).

Full Text in Russian

Available in PDF

1. Huffman D. A. A Method for the Construction of Minimum-Redundancy Codes // Proceedings of the I.R.E. 1952. P. 1098–1102.
2. Fisher Y. Fractal Image Compression: Theory and Application. Springer Verlag, 1995.
3. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory, IT. 1977.Vol. 23 (3). P. 337–343.
4. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding // IEEE Transactions on Information Theory, IT. 1978. Vol. 24 (5). P. 530–536.
5. Cover T. M. Enumerative Source Encoding // IEEE Transactions on Information Theory. 1973. Vol. IT-19. P. 73–77.
6. Hartley R. V. L. Transmission of Information // Bell System Technical Journal. July 1928.
7. Shannon C. E. A Mathematical Theory of Communication // Bell System Technical Journal.
1948. Vol. 27. P. 379–423; 623–656.
8. Fano R. M. The transmission of information // Technical Report. 1949. No. 65.
9. Rissanen J. J. Generalized Kraft Inequality and Arithmetic Coding // IBM J. Res. Dev. May 1976. P. 198–203.
10. Kovalev D. S. Algoritm bystrogo kodirovaniya videodannykh // Materialy XLVI MNSK «Student i nauchno-tekhnichesky progress». Novosibirsk, 2008. C. 8–9.

Publication information
Main title Vestnik NSU Series: Information Technologies, Volume 08, Issue No 4 (2010).
Parallel title: Novosibirsk State University Journal of Information Technologies Volume 08, Issue No 4 (2010).

Key title: Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriâ: Informacionnye tehnologii
Abbreviated key title: Vestn. Novosib. Gos. Univ., Ser.: Inf. Tehnol.
Variant title: Vestnik NGU. Seriâ: Informacionnye tehnologii

Year of Publication: 2010
ISSN: 1818-7900 (Print), ISSN 2410-0420 (Online)
Publisher: Novosibirsk State University Press
DSpace handle

|Home Page| |All Issues| |Information for Authors| |Journal Boards| |Ethical principles| |Editorial Policy| |Contact Information| |Old Site in Russian|
© 2006-2017, Novosibirsk State University.