Data Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution

Abstract

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 $\approx 1.82$ bit/character. Extrapolating to infinitely long input, the true value of the entropy is estimated as $\approx 0.8$ bit/character.

6 pages, including 3 figures

Cited by in corpus (9)

• Data compression and learning in time sequences analysis
• Randomness, Information, and Complexity
• Analysis of the phase transition in the $2D$ Ising ferromagnet using a Lempel-Ziv string parsing scheme and black-box data-compression utilities
• On Hilberg's Law and Its Links with Guiraud's Law
• Non Sequential Recursive Pair Substitution: Some Rigorous Results
• Dynamical systems and computable information
• Problems with information theoretic approaches to causal learning
• A computational mechanics approach to estimate entropy and (approximate) complexity for the dynamics of the 2D Ising Ferromagnet
• Non-sequential recursive pair substitutions and numerical entropy estimates in symbolic dynamical systems