Context tables: a tool for describing text compression algorithms
Hidetoshi Yokoo · 2002
This paper introduces the notion of a context table, which is a common basis for describing and analyzing text compression algorithms. A context table stores all substrings in a text as their lexicographic orders. Examples of compression algorithms described in terms of context table concepts include LZ77 and the block-sorting algorithm. Since these algorithms are designed to work with an arbitrary source distribution, they can be expected to serve as an entropy estimator. A primal use of a context table is to reveal the capability of estimating the entropy. A context table makes it easy to understand several characteristic quantities including the recurrence time of a substring, the conditional recurrence time, and the length of the shortest unique substring. With the help of these concepts, some relations among apparently independent algorithms are established.