On Generalizations and Improvements to the Shannon-Fano Code

D Várkonyi, P Hudoba



DOI: http://dx.doi.org/10.14513/actatechjaur.v10.n1.405

Abstract


This paper examines the possibility of generalizing the Shannon-Fano code for cases where the output alphabet has more then 2 (n) symbols. This generalization is well-known for the famous Huffman code. Furthermore, we will be looking at possible improvements to the algorithm, as well as other entropy based lossless data compression techniques, based on the same ideas as the Shannon-Fano code. All algorithms discussed in the paper were implemented by us in C++, and we will be illustrating our hypotheses with test results, made on an average performance PC.


Keywords


compression, lossless, entropy, Shannon-Fano

Full Text:

PDF

References


Shannon CE: A mathematical theory of communication, Bell System Technical Journal, Vol. 27, pp 379-423, 1948

Fano RM: The transmission of information, Technical report no. 65, Research Laboratory of Electronics, Massachusetts Institute of Technology, 1949

Huffman D: A method for the construction of minimum-redundancy codes, Proceedings of the IRE, Vol. 40, No. 9, pp 1098-1101, 1952

Cover TM, Thomas JA: Elements of information theory, 2nd edition, New Jersey, John Wiley & Sons, Inc., 2006, ISBN: 9780471241959

Jones GA, Jones JM: Information and coding theory, London, Springer, 2000, ISBN: 9781852336226

Yeung RW: Information theory and network coding, London, Springer, 2008, ISBN: 9780387792330

Sayood K: Introduction to data compression, 2nd edition, London, Academic Press 2000, ISBN: 9781558605589

Sayood K: Lossless compression handbook, London, Academic Press 2003, ISBN: 9780126208610

Witten IH, Moffat A, Bell TC: Managing gigabytes: compressing and indexing documents, and images, 2nd edition, London, Academic Press, 1999, ISBN: 9781558605701

Salomon D: Data compression: The complete reference, London, Springer, 1997, ISBN: 9780387982809

Salomon D, Motta G: Handbook of data compression 5th edition, London, Springer, 2010, ISBN: 9781848829022

Drozdek G: Elements of data compression, Pacific Grove, Brooks/Cole publishing, ISBN: 9780534384487




Acta Technica Jaurinensis

ISSN 1789-6932 (Print)
ISSN 2064-5228 (Online)

© Szechenyi Istvan University, Gyor, Hungary