テキスト圧縮のためのユニバーサル符号(<特集>データ圧縮)

概要

論文の詳細を見る
This paper surveys some universal codes for text compression from a unifying viewpoint. As is well known in information theory, the data compression limit of a source is given by its entropy rate. Since universal codes are designed to work with an arbitrary source distribution, they can be expected to serve as entropy estimators. In order to reveal the capability of estimating the entropy, we introduce the notion of a context table, in which all the substrings in a text are enumerated in lexicographic order. A context table is useful to intuitively understand several important quantities including the recurrence time of a substring, the conditional recurrence time, and the length of the shortest unique substring. In terms of these quantities we characterize the Ziv-Lempel code and sort-based symbol ranking codes. Some relations among these apparently independent codes are established by the help of context table concepts.
日本応用数理学会の論文
1998-06-15