dorsal/arxiv
View SchemaData Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution
| Authors | Peter Grassberger |
|---|---|
| Categories | |
| ArXiv ID | physics/0207023 |
| URL | https://arxiv.org/abs/physics/0207023 |
Abstract
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.
{
"annotation_id": "e475c023-3ae4-4a52-a10b-ad75e7ae7bb7",
"date_created": "2026-03-02T18:00:39.476000Z",
"date_modified": "2026-03-02T18:00:39.476000Z",
"file_hash": "a60eab56c3de530543c6bbc3b630ee4dd2ff23022cddd17e63964666474c8136",
"private": false,
"record": {
"abstract": "We argue that Non-sequential Recursive Pair Substitution (NSRPS) as suggested\nby Jim\\\u0027enez-Monta\\~no and Ebeling can indeed be used as a basis for an optimal\ndata compression algorithm. In particular, we prove for Markov sequences that\nNSRPS together with suitable codings of the substitutions and of the substitute\nseries does not lead to a code length increase, in the limit of infinite\nsequence length. When applied to written English, NSRPS gives entropy estimates\nwhich are very close to those obtained by other methods. Using ca. 135 GB of\ninput data from the project Gutenberg, we estimate the effective entropy to be\n$\\approx 1.82$ bit/character. Extrapolating to infinitely long input, the true\nvalue of the entropy is estimated as $\\approx 0.8$ bit/character.",
"arxiv_id": "physics/0207023",
"authors": [
"Peter Grassberger"
],
"categories": [
"physics.data-an",
"cond-mat.stat-mech",
"physics.comp-ph"
],
"title": "Data Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution",
"url": "https://arxiv.org/abs/physics/0207023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1bf1b9e4-32d5-494d-bda8-22fce81ec5e7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}