EUVIMEDEUVIMED entdecken
Crossref

Pragmatic Lossless Compression: Fundamental Limits and Universality

Andreas Theocharous, Lampros Gavalakis, Ioannis Kontoyiannis

IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 4587-4601

DOI: 10.1109/tit.2026.3691268 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Andreas Theocharous und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref). Gefördert von: Engineering and Physical Sciences Research Council (EPSRC)-funded INFORMED-Artificial Intelligence (AI) Project, Cantab Capital Institute for the Mathematics of Information (CCIMI) and in part by the Churchill Trust Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using tools from large deviations and Gaussian approximation. When the source distribution is unknown, a universal achievability result is obtained with an explicit “price for universality” term. This is based on a fine combinatorial estimate on the number of sequences with small empirical entropy, which might be of independent interest. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is relatively short and where stringent guarantees are required on the excess-rate probability, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, more pragmatic rate, determined via the inverse error exponent function and the blocklength.

Förderung

  • Engineering and Physical Sciences Research Council (EPSRC)-funded INFORMED-Artificial Intelligence (AI) Project
  • Cantab Capital Institute for the Mathematics of Information (CCIMI) and in part by the Churchill Trust Fund

Zitieren

APA

Theocharous, A., Gavalakis, L., & Kontoyiannis, I. (2026). Pragmatic Lossless Compression: Fundamental Limits and Universality. IEEE Transactions on Information Theory, 72(7), 4587-4601. https://doi.org/10.1109/tit.2026.3691268

Vancouver

Theocharous A, Gavalakis L, Kontoyiannis I. Pragmatic Lossless Compression: Fundamental Limits and Universality. IEEE Transactions on Information Theory. 2026;72(7):4587-4601. doi:10.1109/tit.2026.3691268

BibTeX
@article{Theocharous2026,
  author = {Theocharous, Andreas and Gavalakis, Lampros and Kontoyiannis, Ioannis},
  title = {Pragmatic Lossless Compression: Fundamental Limits and Universality},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {7},
  pages = {4587--4601},
  doi = {10.1109/tit.2026.3691268}
}
Kostenlos starten →