Alphabetic codes revisited
Raymond W. Yeung · IEEE Transactions on Information Theory · 1991
An alphabetic code for an ordered probability distribution (P/sub k/) is a prefix code in which P/sub k/ is assigned to the kth codeword of the coding tree in left-to-right order. This class of codes is applied to binary test problems. Several earlier results on alphabetic codes are unified and enhanced. The characteristic inequality for alphabetic codes that is analogous to the Kraft inequality for prefix codes is also derived. It is shown that if (P/sub k/) is in ascending or descending order, L/sub min,/ the expected length of an optimal alphabetic code, is the same as that of a Huffman code for the unordered distribution (P/sub k/). An enhancement of Gilbert and Moore's (1959) merging property of all optimal alphabetic code is proved. Two lower bounds and a new upper bound on the expected length of an optimal alphabetic code are also proven, and a simple method is proposed for constructing good alphabetic codes when optimality is critical.>
Cited by 49 works. doi:10.1109/18.79913
Authors
References
- Information Theory and Reliable Communication
- Variable-Length Binary Encodings
- Optimal Binary Identification Procedures
- Application of heuristic search and information theory to sequential fault diagnosis
- Data Structures and Algorithms
- An improved bound for weight-balanced tree
- Local redundancy and progressive bounds on the redundancy of a Huffman code
- Circuit pack troubleshooting via semantic control. I. Goal selection