An efficient decoding technique for Huffman codes. (English) Zbl 1013.68067
Summary: We present a new data structure for Huffman coding in which in addition to sending symbols in order of their appearance in the Huffman tree one needs to send codes of all circular leaf nodes (nodes with two adjacent external nodes), the number of which is always bounded above by half the number of symbols. We decode the text by using the memory efficient data structure proposed by H. C. Chen, Y. L. Wang and Y.-F. Lan [Inf. Process. Lett. 69, 119-122 (1969)].
MSC:
| 68P05 | Data structures |
References:
| [1] | Chen, H.-C.; Wang, Y.-L.; Lan, Y.-F., A memory-efficient and fast Huffman decoding algorithm, Inform. Process. Lett., 69, 119-122 (1999) · Zbl 1338.68050 |
| [2] | Chung, K. L., Efficient Huffman decoding, Inform. Process. Lett., 61, 97-99 (1997) · Zbl 1336.68045 |
| [3] | Hashemian, R., Memory efficient and high-speed search Huffman coding, IEEE Trans. Comm., 43, 10, 2576-2581 (1995) · Zbl 0978.94514 |
| [4] | Huffman, D. A., A method for construction of minimum redundancy codes, Proc. IRE, 40, 1098-1101 (1952) · Zbl 0137.13605 |
| [5] | Katona, G. O.H.; Nemetz, T. O.H., Huffman codes and self-information, IEEE Trans. Inform. Theory, 22, 3, 337-340 (1978) · Zbl 0343.94014 |
| [6] | Mandal, J. N., An approach towards development of efficient data compression algorithms and correction techniques, Ph.D. Thesis (2000), Jadavpur University: Jadavpur University India |
| [7] | Schack, R., The length of a typical Huffman codeword, IEEE Trans. Inform. Theory, 40, 4, 1246-1247 (1994) · Zbl 0811.94026 |
| [8] | Vitter, J. S., Design and analysis of dynamic Huffman codes, J. ACM, 34, 4, 825-845 (1987) · Zbl 0637.94002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
