Universal Data Compression by Digram

通过 Digram 进行通用数据压缩

基本信息

批准号：
09650404
负责人：
ITOH Shuichi
金额：
$ 0.7万
依托单位：
THE UNIVERSITY OF ELECTRO-COMMUNICATIONS
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09650404/
关键词：
lossless data compression pattern matching Lempel-Ziv digram algorithm predictive coding recursive algorithm bigram

项目摘要

This project was performed during the 1997-1998 fiscal years for developing and realizing a high-speed efficient noiseless data compression algorithm based on digram string matching, We have obtained the following results :1. The update algorithm of the dictionary is similar to that of LZMW code. In LZMW code, all the strings in the dictionary are unique, while our code could store the same string multiple times. Thus, ours can not out-perform LZMW code in compression rate. However, since the design of the algorithm is recursive in nature, the implementation is far easier and the coding speed is far faster than those of LZMW.2. The algorithm registers longer strings in the early stage of encoding. As the result, the performance of compression improves very quickly. Therefore, it is better suited for the compression of sequence at practical length.3. We found that it is not enough to encode the position in the dictionary by the commonly used integer encoding. We need to assign the codeword length decided by the probability of the occurrence. Since the size of the alphabet increases according to the increase of input sequence length, we have the so called "the modeling of the source with big alphabet" problem. Therefore we developed the estimation algorithm of smooth probability distribution.Those results are expected to contribute as a basic technology for the future lossless compression schemes.

该项目在1997-1998财年期间进行，旨在开发和实现基于二字母串匹配的高速高效无噪声数据压缩算法，我们获得了以下成果： 1．字典的更新算法与LZMW代码类似。在LZMW代码中，字典中的所有字符串都是唯一的，而我们的代码可以多次存储相同的字符串。因此，我们的代码在压缩率方面无法超越 LZMW 代码。然而，由于该算法的设计本质上是递归的，因此实现起来要容易得多，编码速度也远快于LZMW.2。该算法在编码的早期阶段注册较长的字符串。结果，压缩性能提高得非常快。因此，它更适合于实际长度的序列压缩。 3．我们发现通过常用的整数编码来对字典中的位置进行编码是不够的。我们需要分配由出现概率决定的码字长度。由于字母表的大小随着输入序列长度的增加而增加，因此存在所谓的“大字母表源的建模”问题。因此我们开发了平滑概率分布的估计算法。这些结果有望作为未来无损压缩方案的基础技术。