2002/07/05 by Peter Grassberger, Grassberger, Peter · 1 citation
Computer Science · Physics and Astronomy · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Physics (physics.comp-ph) #Data Analysis #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech) #Statistics and Probability (physics.data-an) #cond-mat.stat-mech #physics.comp-ph #physics.data-an #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.physics/0207023
6 pages, including 3 figures
arxiv created 2002/07/05 · openalex publication_date 2002/07/05 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We argue that Non-sequential Recursive Pair Substitution (NSRPS) as suggested by Jiménez-Montaño and Ebeling can indeed be used as a basis for an optimal data compression algorithm. In particular, we prove for Markov sequences that NSRPS together with suitable codings of the substitutions and of the substitute series does not lead to a code length increase, in the limit of infinite sequence length. When applied to written English, NSRPS gives entropy estimates which are very close to those obtained by other methods. Using ca. 135 GB of input data from the project Gutenberg, we estimate the effective entropy to be ≈ 1.82 bit/character. Extrapolating to infinitely long input, the true value of the entropy is estimated as ≈ 0.8 bit/character.