Efficient decoding of prefix codes

ABSTRACT

A special case of the data compression problem is presented, in which a powerful encoder transmits a coded file to a decoder that has severely constrained memory. A data structure that achieves minimum storage is presented, and alternative methods that sacrifice a small amount of storage to attain faster decoding are described.

REFERENCES

• 1: A. Apostolico , A. S. Fraenkel, Robust transmission of unbounded strings using Fibonacci representations, IEEE Transactions on Information Theory, v.33 n.2, p.238-245, March 1987 [doi>10.1109/TIT.1987.1057284]
• 2: Choueka, Y., et al. Huffman coding without bit-manipulation. Tech. Rep. CS86-05, Weizmann In_stitute of Scien_ce, Dept. of Applied Mathematics, Rehovot, Israel, 1986.
• 3: Connell, J. B, A Huffman-Shannon-Fano code. Proc. IEEE 61, 7 (July (1973), I046-1047.
• 4: Hankamer, M. A modified Huffman procedure with reduced memory requirements. IEEE Trans. Commun. 27, 6 (June 1979), 930-932.
• 5: Huffman, D. A. A method for the construction of minimum-redundancy codes. Proc. it~t: ,~u, u t~ept. 1952), 1098-1101.
• 6: Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987 [doi>10.1145/45072.45074]
• 7: Eugene S. Schwartz , Bruce Kallick, Generating a canonical prefix encoding, Communications of the ACM, v.7 n.3, p.166-169, March 1964 [doi>10.1145/363958.363991]
• 8: Andrzej Siemiński, Fast decoding of the Huffman codes, Information Processing Letters, v.26 n.5, p.237-241, Jan. 11, 1988 [doi>10.1016/0020-0190(88)90146-9]
• 9: James A. Storer, Data compression: methods and theory, Computer Science Press, Inc., New York, NY, 1987
• 10: Hatsukazu Tanaka, Data structure of Huffman codes and its application to efficient encoding and decoding, IEEE Transactions on Information Theory, v.33 n.1, p.154-156, January 2, 1987 [doi>10.1109/TIT.1987.1057265]
• 11: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Tables**

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

General Terms:
Algorithms, Performance