On-line stochastic processes in data compression
S. Bunton, Gaetano Borriello, Richard E. Ladner · 1996
The ability to predict the future based upon the past in finite-alphabet sequences has many applications, including communications, data security, pattern recognition, and natural language processing. By Shannon's theory and the breakthrough development of arithmetic coding, any sequence, a 1 a 2 \\Delta \\Delta \\Delta a n , can be encoded in a number of bits that is essentially equal to the minimal information-lossless codelength, P i \\Gamma log 2 p(a i ja 1 \\Delta \\Delta \\Delta a i\\Gamma1 ). The goal of universal on-line modeling, and therefore of universal data compression, is to deduce the model of the input sequence a 1 a 2 \\Delta \\Delta \\Delta a n that can estimate each p(a i ja 1 \\Delta \\Delta \\Delta a i\\Gamma1 ) knowing only a 1 a 2 \\Delta \\Delta \\Delta a i\\Gamma1 so that the ex...