Dependency Data Compression with Self-Organizing Lists

概要

論文の詳細を見る
A locally adaptive data compression scheme developed by Bentley, Sleator, Tarjan and Wei, so called BSTW algorithm, is known as one of the most efficient data compression algorithms due to its simplicity, speed and one pass properfy. Horspool and Cormack investigated this form of algorithm and found it inferior to other more popular techniques such as Ziv and Lempel coding. This paper proposes a dependency data compression algorithm (DDC) as a more efficient alternative. The DDC algorithm is similar to the BSTW algorithm but takes advantage of dependent occurrences of data, i.e., occurrences of symbols which depend on preceding symbols. A prediction model of next symbols is built based on previous contexls and self organizing code tables. Compression of data can be achieved by employing shorter codes for symbols which are located near the beginning of the code table. The model is simple and improves the compression performance. This paper first describes the models and then investigates many types of self organizing lists. By comparing experimentally with other algorithms currently in use, we demonstrate the efficiency of the DDC algorithm.
一般社団法人情報処理学会の論文
1994-06-15