Windowed Huffman coding algorithm with size adaption
Journal
IEE Proceedings, Part I: Communications, Speech and Vision
Journal Volume
140
Journal Issue
2
Pages
109-112
Date Issued
1993
Author(s)
Huang, H.C.
Abstract
The windowed Huffman algorithm is introduced. The Huffman code tree is constructed based on the probabilities of symbols' occurrences within finite history in this windowed algorithm. A window buffer is used to store the most recently processed symbols. Experimental results show that by choosing a suitable window size, the length of codes generated by the windowed Huffman algorithm is shorter than those generated by the static Huffman algorithm, dynamic algorithms, and the residual Huffman algorithm, and even smaller than that first-order entropy. Furthermore, three policies to adjust window size dynamically are also discussed. The windowed Huffman algorithm with an adaptive-size window performs as well as, or better than, that with an optimal fixed-size window. The new algorithm is well suited for online encoding and decoding of data with varying probability distributions.
Other Subjects
Codes (symbols); Computer programming; Decoding; Encoding (symbols); Online encoding; Probability distribution; Size adaptation; Windowed Huffman coding algorithm; Algorithms
Type
journal article