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财政年度进行的，用于开发和实现基于Digram字符串匹配的高速无噪声数据压缩算法，我们获得了以下结果：1。字典的更新算法与lzmw代码的更新算法相似。在LZMW代码中，字典中的所有字符串都是唯一的，而我们的代码可以多次存储相同的字符串。因此，我们的压缩率无法以较高的lzmw代码胜过。但是，由于该算法的设计本质上是递归的，因此实现更容易，并且编码速度远高于LZMW.2的速度。该算法在编码的早期阶段记录了更长的字符串。结果，压缩的性能很快提高。因此，它更适合于在实际长度上压缩序列3。我们发现，通过常用的整数编码编码字典中的位置是不够的。我们需要分配由事件的概率决定的编码长度。由于字母的大小根据输入序列长度的增加而增加，因此我们具有所谓的“具有大字母的源建模”问题。因此，我们开发了平滑概率分布的估计算法。预计这些结果将成为未来无损压缩方案的基本技术。