# Space-Efficient Huffman Codes Revisited

@article{Grabowski2021SpaceEfficientHC, title={Space-Efficient Huffman Codes Revisited}, author={Szymon Grabowski and Dominik K{\"o}ppl}, journal={ArXiv}, year={2021}, volume={abs/2108.05495} }

Canonical Huffman code is an optimal prefix-free compression code whose codewords enumerated in the lexicographical order form a list of binary words in non-decreasing lengths. Gagie et al. (2015) gave a representation of this coding capable to encode or decode a symbol in constant worst case time. It uses σ lg lmax + o(σ) + O(l 2 max) bits of space, where σ and lmax are the alphabet size and maximum codeword length, respectively. We refine their representation to reduce the space complexity to… Expand

#### References

SHOWING 1-10 OF 28 REFERENCES

Decoding of canonical Huffman codes with look-up tables

- Computer Science
- Proceedings DCC 2000. Data Compression Conference
- 2000

This paper presents an efficient algorithm for decoding canonical Huffman codes with lookup tables, which reads a number of bits at each step of the decoding process and outputs the corresponding symbol. Expand

Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes

- Computer Science, Mathematics
- SPIRE
- 2016

This paper shows how to store a nearly optimal alphabetic prefix-free code in bits such that it can be used to encode and decode any character in constant time under reasonable assumptions. Expand

Efficient and Compact Representations of Prefix Codes

- Computer Science, Mathematics
- IEEE Transactions on Information Theory
- 2015

Various heuristic, approximate, and optimal algorithms to generate length-restricted codes are compared, showing that the optimal ones are clearly superior and practical enough to be implemented. Expand

Space- and Time-Efficient Decoding with Canonical Huffman Trees

- Mathematics, Computer Science
- CPM
- 1997

A new data structure is investigated, which allows fast decoding of texts encoded by canonical Huffman codes, which is much lower than for conventional Huffman trees, and decoding is faster, because a part of the bit-comparisons necessary for the decoding may be saved. Expand

An efficient decoding technique for Huffman codes

- Computer Science
- Inf. Process. Lett.
- 2002

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… Expand

On the implementation of minimum redundancy prefix codes

- Computer Science
- IEEE Trans. Commun.
- 1997

A modified decoding method is described that allows improved decoding speed, requiring just a few machine operations per output symbol (rather than for each decoded bit), and usesjust a few hundred bytes of memory above and beyond the space required to store an enumeration of the source alphabet. Expand

Memory efficient and high-speed search Huffman coding

- Computer Science
- IEEE Trans. Commun.
- 1995

A tree clustering algorithm is proposed to speed up the process of search for a symbol in a Huffman tree and to reduce the memory size to avoid high sparsity of the tree. Expand

Universal codeword sets and representations of the integers

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1975

An application is the construction of a uniformly universal sequence of codes for countable memoryless sources, in which the n th code has a ratio of average codeword length to source rate bounded by a function of n for all sources with positive rate. Expand

Huffman Coding

- Computer Science
- Encyclopedia of Algorithms
- 2016

A tutorial on Huffman coding is presented, and some of the developments that have flowed as a consequence of Huffman’s original discovery are surveyed, including details of code calculation, and of encoding and decoding operations. Expand

Decoding prefix codes

- Computer Science
- Softw. Pract. Exp.
- 2006

It is found that table‐based decoding techniques offer fast operation, provided that the size of the table is kept relatively small, and that approximate coding techniques can offer higher decoding rates than Huffman codes with varying degrees of loss of compression effectiveness. Expand