2005/04/17 by Boris Ryabko, Ryabko, Boris, Jaakko Astola +1
Computer Science · Mathematics · #Advanced Data Compression Techniques #Algorithms and Data Compression #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0504079
submitted
openalex publication_date 2005/04/17 · arxiv created 2005/04/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of predicting a sequence x1,x2,... generated by a discrete source with unknown statistics is considered. Each letter xt+1 is predicted using information on the word x1x2... xt only. In fact, this problem is a classical problem which has received much attention. Its history can be traced back to Laplace. We address the problem where each xi belongs to some large (or even infinite) alphabet. A method is presented for which the precision is greater than for known algorithms, where precision is estimated by the Kullback-Leibler divergence. The results can readily be translated to results about adaptive coding.