AN EFFICIENT ALGORITHM FOR THE BAYES CODES USING AN UNLIMITED DEPTH CONTEXT TREE

摘要

Recently, distortionless data compression codes have been used for not only text sources but also image sources. The Bayes code is one of the optimal distortionless universal codes whose conversion rate to the entropy of a source achieves theoretical lower bound. The Bayes code on context tree models is known as a useful data compression code for text files. However the space complexity of the Bayes coding algorithm is impractical for image sources. In this paper, we propose an efficient Bayes coding algorithm using a new unlimited depth context tree. The space complexity of the proposed algorithm is linear order of the source sequence length. Moreover, the asymptotic code length of the Bayes coding algorithm using the unlimited depth context tree is investigated.