Redundancy of symbol decomposition algorithms for memoryless source
Tsutomu Kawabata, You Yanagisawa · 2005
The symbol decomposition algorithm is proposed by Willems et. al. as an efficient and practical symbol predictor applicable for compressing multi-alphabet data. However, no theoretical analysis of the algorithm has been presented. In this paper, we first elucidate a natural parameterization that the algorithm assumes and derive a prior distribution on which the algorithm is based. Based on this framework, we first analyze the redundancy of the algorithm for memoryless source with a structured alphabet. Then we interpret the algorithm compared with the Krichevsky-Trofimov estimator for multi-alphabet, through the prior distribution over our parameterization. We demonstrate an effectiveness of the algorithm through a computer simulation of the redundancy, and also reveal a non-optimal character. Finally, we propose a practical modification of the symbol decomposition algorithm, and show that the it achieves the asymptotic optimal redundancy