Study of Sort-Based Data Compression Algorithms

基于排序的数据压缩算法研究

基本信息

批准号：
11680339
负责人：
HIDETOSHI Yokoo
金额：
$ 1.41万
依托单位：
Gunma University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11680339/
关键词：
Data compression universal coding sorting block sorting context sorting statistical model lossless compression adaptive alphabet decomposition ユニバーサル符号、ソート法モデリング PPM プレフィクスリスト

项目摘要

We have analyzed several sort-based algorithms for lossless data compression and developed new data structures and algorithms which supersede existing ones. Sort-based lossless compression methods studied in this project include the block-sorting data compression method and the context-sorting method. They all define a total order on the set of symbol candidates based on the similarity between the current context and previous contexts. The context similarity essentially produces a partial order, which is in turn converted into a total order by the help of an artificial transformation. We have proposed a new adaptive model which can avoid such an artificial transformation. In the proposed model, we keep a partial order on the set of symbol candidates. When predicting an upcoming symbol, we can group symbol candidates into several equivalence classes according to their contexts. The proposed scheme adaptively decomposes the source alphabet into such equivalence classes. These sub-alphabets are sequentially traversed to encode an upcoming symbol. We use the PPM-like escape mechanism to indicate an alphabet which includes an upcoming symbol. The symbol is then encoded using a probability distribution estimated over that sub-alphabet. Simulation results show that the proposed method outperforms PPM* and the block-sorting algorithm.

我们已经分析了几种基于排序的算法，用于无损数据压缩，并开发了取代现有数据的新数据结构和算法。该项目中研究的基于排序的无损压缩方法包括块分类数据压缩方法和上下文分类方法。他们都根据当前上下文和以前的上下文之间的相似性在一组符号候选者上定义了总顺序。上下文相似性本质上会产生部分秩序，这又借助人工转换将其转换为总顺序。我们提出了一种新的自适应模型，该模型可以避免这种人工转换。在拟议的模型中，我们在候选符号的集合上保留部分顺序。在预测即将到来的符号时，我们可以根据其上下文将符号候选者分为几个等价类。所提出的方案将源字母表自适应地分解为这样的等效类别。这些子字符序列地穿越以编码即将到来的符号。我们使用类似PPM的逃生机制来指示一个字母，其中包括即将到来的符号。然后，使用该子字母表上估计的概率分布对该符号进行编码。仿真结果表明，所提出的方法的表现优于ppm*和块状算法。