• 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