Title: Tunstall Parse Trees Optimum under Various Criteria
Abstract: The well known Tunstall algorithm for discrete memoryless sources [17] produces optimal variable-to-fixed length source codes that maximize the expected number of source letters per codeword. Tun stall algorithm achieves this result by constructing parse trees with maximum average height for the source output. In the first part of this paper we introduce a simple variant of Tun stall algorithm in order to optimizes additional natural cost functions of interest. For instance we show how to select, among all parse trees with maximum average height, those having minimum height, minimum variance, minimum external length, and more general natural parameters. In the second part of the paper we consider the problem of selecting, among all parse trees of height bounded by some parameter L, those parse trees having maximum average height. We motivate the problem, and we quantify the loss of performance these parse trees suffer with respect to unrestricted Tuns tall parse trees, when they are used as variable-to-fixed length encoding for a discrete memoryless source.
Publication Year: 2007
Publication Date: 2007-06-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot