An Efficient Algorithm for the Bayes Codes using an Unlimited Depth Context Tree

T. Matsushima and S. Hirasawa (Japan)


Data compression, Image sources, Distortionless source coding, Bayes universal codes, Context tree models.


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 con text 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 us ing a new unlimited depth context tree. The space complex ity 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 con text tree is investigated.

Important Links:

Go Back