Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Weighted Adaptive Huffman Coding

Abstract: 

Huffman coding is known to be optimal in case the alphabet is known in advance, the set of codewords is fixed and each codeword consists of an integral number of bits. If one of these conditions is violated, optimality is not guaranteed.
In the {\it dynamic\/} variant of Huffman coding the encoder and decoder maintain identical copies of the model; at each position, the model consists of the frequencies of the elements processed so far.
After each processed element $\sigma$, the model is updated by incrementing the frequency of $\sigma$ by 1, while the other frequencies remain the same.

An enhanced dynamic Huffman coding named {\it forward looking coding} \cite{KSS} starts with the full frequencies, similar to the static variant, and then decreases them progressively. For this method, after each processed element $\sigma$, the model is altered by {\it decrementing\/} the frequency of $\sigma$ by 1, while the other frequencies remain the same.
Forward looking Huffman coding has been shown to be always better by at least $m-1$ bits than static Huffman coding.
A hybrid method, exploiting both the classical backward and the new forward approaches is proposed in \cite{FKS}, and
has been shown to be always at least as good as the forward looking Huffman coding.

If the model is learned adaptively, as in the traditional backward looking codings, no description of the model is needed, since the model is updated by the encoder and the decoder in synchronization.
However, in the other mentioned versions, the details of the chosen model on which the method relies,
are needed for the decoding and
should be adjoined to the compressed file, for example, as an header.

The contribution of this work is as follows:
we first define a new generic coding method which we call {\it weighted\/} coding, encompassing all mentioned variants (static, forward and backward) as special cases.
Second, a new special case called {\it positional\/} is suggested, and shown to be always at least as good as the forward looking coding.
Third, we present empirical results that show practical improvements of the proposed method, even when the encoded file includes the model description.
It is important to stress that all the methods can in fact be applied to every adaptive coding technique, in particular to arithmetic coding or PPM.

up
0 users have voted:

Paper Details

Authors:
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira
Submitted On:
23 March 2020 - 11:05am
Short Link:
Type:
Poster
Event:

Document Files

Weighted_Adaptive_Huffman_Coding.pdf

(8)

Keywords

Additional Categories

Subscribe

[1] Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira, "Weighted Adaptive Huffman Coding", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5022. Accessed: Mar. 30, 2020.
@article{5022-20,
url = {http://sigport.org/5022},
author = {Aharon Fruchtman; Yoav Gross; Shmuel T. Klein; Dana Shapira },
publisher = {IEEE SigPort},
title = {Weighted Adaptive Huffman Coding},
year = {2020} }
TY - EJOUR
T1 - Weighted Adaptive Huffman Coding
AU - Aharon Fruchtman; Yoav Gross; Shmuel T. Klein; Dana Shapira
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5022
ER -
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira. (2020). Weighted Adaptive Huffman Coding. IEEE SigPort. http://sigport.org/5022
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira, 2020. Weighted Adaptive Huffman Coding. Available at: http://sigport.org/5022.
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira. (2020). "Weighted Adaptive Huffman Coding." Web.
1. Aharon Fruchtman, Yoav Gross, Shmuel T. Klein, Dana Shapira. Weighted Adaptive Huffman Coding [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5022