Research on Adaptive Lossless Data Compression -The Context Tree Weighting Method with a Finite Window-

自适应无损数据压缩研究-有限窗口上下文树加权方法-

基本信息

批准号：
13650400
负责人：
KAWABATA Tsutomu
金额：
$ 1.22万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13650400/
关键词：
source coding data compression bayes code context tree weighting method lossless redundancy zero-redundancy finite window 無歪無歪データ圧縮有限窓CTW法 Laplace推定量算術符号マルコフ情報源

项目摘要

The lossless data compression is a fundamental subject both in information and communication theory. The model-based method is a major approach in the subject, and there source estimation is combined with the arithmetic coding. A most popular source model is the so called tree model, and for this the context tree weighting (CTW) method is an ideal estimation method. The CTW method can be modified to be based on a finite window it can follow up to a change of source probability. A crucial argument here is the computability of a sub-probability estimator, which enables the usage of arithmetic coder. A yielded estimator, we have discovered, is called FWCTW (finite window CTW). In our research this period we pursued a reduction of the redundancy even when some source parameters annihilate. We first discovered that a Laplace estimator reduces the first order redundancy in such a source, and published the result in a Transaction of IEICE. Second, we proposed and reported a new finite window based coder, with a zero-redundancy property, which had lacked in the Laplace estimator. The CTW method can be looked as being intended to achieve the min-max redundancy. Hence we studied this target through one of a collaborated work. Especially, in this view, a most useful min-max code would be non-sequential, and in such a code, an important tool would be an optimal representation of estimated parameter in term of information metric. This is realized by a multi-dimensional two stage quantization : a combination of a first stage quantizer and a compressor for a lattice quantizer. We achieved substantial progress in this theme, which would contribute also in the study of FWCTW.

无损数据压缩是信息和通信理论中的一个基本主题。基于模型的方法是该主题的主要方法，并且源估计与算术编码相结合。最受欢迎的源模型是所谓的树模型，为此，上下文树的加权（CTW）方法是理想的估计方法。可以修改CTW方法以基于有限窗口，可以跟进源概率的更改。这里的关键参数是亚概率估计器的可计算性，它可以使用算术编码器。我们发现，屈服的估计器称为FWCTW（有限窗口CTW）。在我们的研究中，即使某些源参数歼灭，我们也会降低冗余。我们首先发现拉普拉斯估计量减少了这种来源中的一阶冗余，并在IEICE交易中发布了结果。其次，我们提出并报告了一个新的有限窗口编码器，具有零额定属性，该属性缺乏拉普拉斯估计器。 CTW方法可以看作是为了实现最小的最大冗余。因此，我们通过合作的工作之一研究了这个目标。尤其是，在这种观点中，最有用的最小最大代码将是不顺序的，在这样的代码中，重要的工具将是信息指标术语中估计参数的最佳表示。这是由多维的两个阶段量化实现的：第一阶段量化器和晶格量化器的压缩机的组合。我们在这个主题上取得了重大进展，这也将在FWCTW的研究中做出贡献。