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

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

2002-07-05

arxiv.org/abs/physics/0207023v1

Physics

Data Analysis, Statistics and Probability

6 pages, including 3 figures

Scientific paper

We argue that Non-sequential Recursive Pair Substitution (NSRPS) as suggested by Jim\'enez-Monta\~no 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.

Affiliated with

Also associated with

No associations

Rating

Data Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Data Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-587095