Title :
Efficient implementation of the generalized Tunstall code generation algorithm
Author :
Baer, Michael B.
Author_Institution :
VMware, Inc., San Francisco, CA, USA
fDate :
June 28 2009-July 3 2009
Abstract :
A method is presented for constructing a Tunstall code that is linear time in the number of output items. This is an improvement on the state of the art for non-Bernoulli sources, including Markov sources, which require a (suboptimal) generalization of Tunstall´s algorithm proposed by Savari and analytically examined by Tabus and Rissanen. In general, if n is the total number of output leaves across all Tunstall trees, s is the number of trees (states), and D is the number of leaves of each internal node, then this method takes O((1 + (log s)/D)n) time and O(n) space.
Keywords :
Huffman codes; Markov processes; computational complexity; linear codes; trees (mathematics); Huffman optimal fixed-to-variable-length coding method; Markov source; Tunstall tree; generalized Tunstall code generation algorithm; linear time code; nonBernoulli source; time-space complexity; Algorithm design and analysis; Block codes; Markov processes; Random variables;
Conference_Titel :
Information Theory, 2009. ISIT 2009. IEEE International Symposium on
Conference_Location :
Seoul
Print_ISBN :
978-1-4244-4312-3
Electronic_ISBN :
978-1-4244-4313-0
DOI :
10.1109/ISIT.2009.5205733
