DocumentCode
2949894
Title
Relative redundancy for large alphabets
Author
Orlitsky, Alon ; Santhanam, Narayana ; Zhang, Junan
Author_Institution
Dept. of ECE, UC San Diego, CA
fYear
2006
fDate
9-14 July 2006
Firstpage
2672
Lastpage
2676
Abstract
Standard redundancy measures the excess number of bits required to encode a sequence of a given length when the underlying distribution is not known. Relative redundancy measures the same increase, but as a function of the sequence´s minimum description length. We consider the relative redundancy of i.i.d. distributions over large alphabets and show that, like standard redundancy, relative redundancy too increases with the alphabet size. We then consider compression of patterns of i.i.d. strings. Again analogous to standard redundancy, we show that the relative redundancy of patterns of large, or even infinite alphabet i.i.d. distributions is negligible compared to the patterns´ minimum description length
Keywords
data compression; redundancy; sequential codes; large alphabets; relative redundancy; sequence encoding; standard redundancy; Compression algorithms; Length measurement; Measurement standards;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory, 2006 IEEE International Symposium on
Conference_Location
Seattle, WA
Print_ISBN
1-4244-0505-X
Electronic_ISBN
1-4244-0504-1
Type
conf
DOI
10.1109/ISIT.2006.262138
Filename
4036457
Link To Document