Optimal Alphabet Partitioning for Semi-Adaptive Coding of Sources of Unknown Sparse Distributions

Practical applications that employ entropy coding for large alphabets often partition the alphabet set into two or more layers and encode each symbol by using some suitable prefix coding for each layer. In this paper we formulate the problem of optimal alphabet partitioning for the design of a two layer semi-adaptive code and give a solution based on dynamic programming. However, the complexity of the dynamic programming approach can be quite …