Presentation | 2002/3/11 Asymptotic Performance of a Sequential MPM Code Hiroshi TAKEKAWA, Hirosuke YAMAMOTO, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Multilevel Pattern Matching (MPM) code, which is one of Grammar-based universal lossless data compression codes, can attain O(1/log n) maximum redundancy for any finite-state information sources. But, since the MPM code encodes data sequences blockwisely, coding delay cannot be avoided. In order to improve this defect, we proposed a sequential MPM code that encodes and decodes data sequences sequentially in a previous paper [3]. In this paper, we investigate the asymptotic performance of the sequential MPM code and we prove that it can attain the same maximum redundancy O(1/log n) for any finite-state sources as the original MPM code. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | MPM code / Grammar-based code / Universal Lossless Data Compression / Sequential coding |
Paper # | IT2001-73 |
Date of Issue |
Conference Information | |
Committee | IT |
---|---|
Conference Date | 2002/3/11(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 Theory (IT) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Asymptotic Performance of a Sequential MPM Code |
Sub Title (in English) | |
Keyword(1) | MPM code |
Keyword(2) | Grammar-based code |
Keyword(3) | Universal Lossless Data Compression |
Keyword(4) | Sequential coding |
1st Author's Name | Hiroshi TAKEKAWA |
1st Author's Affiliation | Department of Information Engineering, The University of Tokyo() |
2nd Author's Name | Hirosuke YAMAMOTO |
2nd Author's Affiliation | Department of Mathematical Informatics, The University of Tokyo |
Date | 2002/3/11 |
Paper # | IT2001-73 |
Volume (vol) | vol.101 |
Number (no) | 725 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |