TY - GEN
T1 - Selected data compression
T2 - 1st International Conference Analytical and Computational Methods in Probability Theory, ACMPT 2017
AU - Suhov, Yuri
AU - Stuhl, Izabella
N1 - Funding Information:
Authors thank the Math. Department, Penn State University, for hospitality and support.
Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85039457663&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85039457663&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-71504-9_26
DO - 10.1007/978-3-319-71504-9_26
M3 - Conference contribution
AN - SCOPUS:85039457663
SN - 9783319715032
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 309
EP - 321
BT - Analytical and Computational Methods in Probability Theory - 1st International Conference, ACMPT 2017, Proceedings
A2 - Rykov, Vladimir V.
A2 - Singpurwalla, Nozer D.
A2 - Zubkov, Andrey M.
PB - Springer Verlag
Y2 - 23 October 2017 through 27 October 2017
ER -