On universality of both Bayes codes and Ziv-Lempel codes for sources which emit data sequence by block unit

Takashi Ishida*, Masayuki Gotoh, Shigeichi Hirasawa


研究成果: Article査読

2 被引用数 (Scopus)


Ziv-Lempel (ZL) codes and Bayes codes are typical universal codes. An improved algorithm of the ZL code is widely used in compression software. On the other hand, practical use of Bayes codes is difficult due to the large amount of computation needed. However, a realizable algorithm in terms of computation effort has been constructed for the FSMX model group [9]. In this paper, an information source generating a sequence by word units is assumed as a model that can represent the probabilistic structure of actual data such as text data. The asymptotic compression performance of both codes is analyzed and evaluated for the information source class (information source for the block unit) with a constant (fixed) word length. As a result, it is found that Bayes code cannot directly be universal as a coding algorithm for symbol units. On the other hand, the ZL78 code can be directly universal. Also, a configuration method for the Bayes coding method is given for an information source with a block unit.

ジャーナルElectronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi)
出版ステータスPublished - 2003 1月 1

ASJC Scopus subject areas

  • 電子工学および電気工学