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
$1.82$ bit/character. Extrapolating to infinitely long input, the true
value of the entropy is estimated as $0.8$ bit/character.
Users
Please
log in to take part in the discussion (add own reviews or comments).