Selected data compression: A refinement of Shannon’s principle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

The Shannon Noiseless coding theorem (the data-compression principle) asserts that for an information source with an alphabet X= { 0, …, ℓ- 1 } and an asymptotic equipartition property, one can reduce the number of stored strings (x0, …, xn-1) ∈ Xn to ℓnh with an arbitrary small error-probability. Here h is the entropy rate of the source (calculated to the base ℓ). We consider further reduction based on the concept of utility of a string measured in terms of a rate of a weight function. The novelty of the work is that the distribution of memory is analyzed from a probabilistic point of view. A convenient tool for assessing the degree of reduction is a probabilistic large deviation principle. Assuming a Markov-type setting, we discuss some relevant formulas and examples.

Original languageEnglish (US)
Title of host publicationAnalytical and Computational Methods in Probability Theory - 1st International Conference, ACMPT 2017, Proceedings
EditorsVladimir V. Rykov, Nozer D. Singpurwalla, Andrey M. Zubkov
PublisherSpringer Verlag
Pages309-321
Number of pages13
ISBN (Print)9783319715032
DOIs
StatePublished - 2017
Event1st International Conference Analytical and Computational Methods in Probability Theory, ACMPT 2017 - Moscow, Russian Federation
Duration: Oct 23 2017Oct 27 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10684 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Conference Analytical and Computational Methods in Probability Theory, ACMPT 2017
Country/TerritoryRussian Federation
CityMoscow
Period10/23/1710/27/17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Selected data compression: A refinement of Shannon’s principle'. Together they form a unique fingerprint.

Cite this