| Presentation | 2013-03-07 Maximum Redundancy of Lossless Data Compression via Substring Enumeration for Markov Sources Ken-ichi IWATA, Mitsuharu ARIMURA, Yuki SHIMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Dube and Beaudoin proposed a technique of lossless data compression called compression via substring enumeration (CSE)in 2010. This paper evaluates an upper bound of the amount of bits used by the CSE tech- nique to encode any individual string from an unknown member of a known class of k-th order Markov processes. We compare the worst case maximum redundancy obtained by the CSE technique for any binary string with the least possible value of the worst case maximum redundancy obtained by the best fixed-to-variable length code sat- isfying the Kraft inequality. We clarify that the difference of the worst case maximum redundancies is at most log n+constant, where n denotes the length of a binary string to be encoded. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | lossless data compression / universal source coding / compression via substring enumeration / k-th order Markov sources / maximum redundancy |
| Paper # | IT2012-76,ISEC2012-94,WBS2012-62 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2013/2/28(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Maximum Redundancy of Lossless Data Compression via Substring Enumeration for Markov Sources |
| Sub Title (in English) | |
| Keyword(1) | lossless data compression |
| Keyword(2) | universal source coding |
| Keyword(3) | compression via substring enumeration |
| Keyword(4) | k-th order Markov sources |
| Keyword(5) | maximum redundancy |
| 1st Author's Name | Ken-ichi IWATA |
| 1st Author's Affiliation | Department of Information Science, University of Fukui() |
| 2nd Author's Name | Mitsuharu ARIMURA |
| 2nd Author's Affiliation | Department of Applied Computer Sciences, Shonan Institute of Technology |
| 3rd Author's Name | Yuki SHIMA |
| 3rd Author's Affiliation | Department of Information Science, University of Fukui |
| Date | 2013-03-07 |
| Paper # | IT2012-76,ISEC2012-94,WBS2012-62 |
| Volume (vol) | vol.112 |
| Number (no) | 461 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |