Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity

摘要

A general class of sequential codes for lossless compression of individual sequences on a finite alphabet is defined, including many types of codes that one would want to implement. The principal requirement for membership in the class is that the encoding and decoding operations be performable on a computer. The OPTA function for the class of codes is then considered, which is the function that assigns to each individual sequence the infimum of the rates at which the sequence can be compressed over this class of sequential codes. Two results about the OPTA function are obtained: (1) it is shown that any sequential code in the class compresses some individual sequence at a rate strictly greater than the rate for that sequence given by the OPTA function; and (2) it is shown that the OPTA function takes a value strictly greater than that of the Kolmogorov (1965) complexity rate function for some individual sequences.