Context allocation with application to data compression

Abstract

Given a sequence of correlated symbols of a finite alphabet, the context or history of a substring (the sequence of symbols preceding the substring) provides information about likely future symbols for applications such as universal data compression or prediction. In this paper, we describe an approach to calculating optimal context and provide an application to a generalization of Lempel-Ziv coding.