Dominique Bontemps ; Stephane Boucheron ; Elisabeth Gassiat - Adaptive compression against a countable alphabet

dmtcs:2995 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2995
Adaptive compression against a countable alphabet

Authors: Dominique Bontemps 1; Stephane Boucheron ORCID-iD2; Elisabeth Gassiat ORCID-iD3

This paper sheds light on universal coding with respect to classes of memoryless sources over a countable alphabet defined by an envelope function with finite and non-decreasing hazard rate. We prove that the auto-censuring (AC) code introduced by Bontemps (2011) is adaptive with respect to the collection of such classes. The analysis builds on the tight characterization of universal redundancy rate in terms of metric entropy by Haussler and Opper (1997) and on a careful analysis of the performance of the AC-coding algorithm. The latter relies on non-asymptotic bounds for maxima of samples from discrete distributions with finite and non-decreasing hazard rate.


Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: adaptive compression,countable alphabets,lossless data compression,minimax,redundancy,universal coding,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1002/9781118032770
  • 10.1002/9781118032770
Szpankowski/Average

Consultation statistics

This page has been seen 155 times.
This article's PDF has been downloaded 189 times.