講演名 | 2015-09-01 部分文字列数え上げ圧縮法の効率的な実現の一般化 佐久間 俊平(東北大), 成澤 和志(東北大), 篠原 歩(東北大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | Dub'eとBeaudoinによって2010年に考案された無ひずみデータ圧縮法である部分文字列数え上げ圧縮法に対し,金井と横尾はBurrows-Wheeler変換行列をうまく利用した効率的な実装方法を提案した.本論文は,この実装方法を一般化し,(1)バイト指向情報源に対してフェーズの区別を明示的に導入することで圧縮率を高める,(2) バイナリ文字列のみならず多値アルファベットの文字列をそのまま取り扱える,という2方向への拡張を示す. |
抄録(英) | CSE (Compression by Substring Enumeration), a lossless universal compression scheme was introduced by Dub'e and Beaudoin in 2010. Kanai and Yokoo proposed an efficient implementation for CSE by utilizing the Burrows-Wheeler transform. We extend it in two ways: (1) to deal with the explicit phase awareness for byte-oriented source; and (2) to treat multiple characters for a finite alphabet source. |
キーワード(和) | データ圧縮 / 符号化 / ユニバーサル符号 / BWT / CSE法 / ウェーブレット行列 |
キーワード(英) | BWT / coding / CSE / data compression / universal codes / Wavelet Matrix |
資料番号 | COMP2015-18 |
発行日 | 2015-08-25 (COMP) |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2015/9/1(から1日開催) |
開催地(和) | 信州大学 |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | 和田 幸一(法政大) |
委員長氏名(英) | Koichi Wada(Hosei Univ.) |
副委員長氏名(和) | 増澤 利光(阪大) |
副委員長氏名(英) | Toshimitsu Masuzawa(Osaka Univ.) |
幹事氏名(和) | 亀井 清華(広島大) / 古賀 久志(電通大) |
幹事氏名(英) | Sayaka Kamei(Hiroshima Univ.) / Hisashi Koga(Univ. of Electro-Comm.) |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
---|---|
本文の言語 | JPN |
タイトル(和) | 部分文字列数え上げ圧縮法の効率的な実現の一般化 |
サブタイトル(和) | 多値化とフェーズの導入 |
タイトル(英) | Generalization of Efficient Implementation of Compression by Substring Enumeration |
サブタイトル(和) | Finite Alphabet and Explicit Phase Awareness |
キーワード(1)(和/英) | データ圧縮 / BWT |
キーワード(2)(和/英) | 符号化 / coding |
キーワード(3)(和/英) | ユニバーサル符号 / CSE |
キーワード(4)(和/英) | BWT / data compression |
キーワード(5)(和/英) | CSE法 / universal codes |
キーワード(6)(和/英) | ウェーブレット行列 / Wavelet Matrix |
第 1 著者 氏名(和/英) | 佐久間 俊平 / Shumpei Sakuma |
第 1 著者 所属(和/英) | 東北大学(略称:東北大) Tohoku Univercity(略称:Tohoku Univ.) |
第 2 著者 氏名(和/英) | 成澤 和志 / Kazuyuki Narisawa |
第 2 著者 所属(和/英) | 東北大学(略称:東北大) Tohoku Univercity(略称:Tohoku Univ.) |
第 3 著者 氏名(和/英) | 篠原 歩 / Ayumi Shinohara |
第 3 著者 所属(和/英) | 東北大学(略称:東北大) Tohoku Univercity(略称:Tohoku Univ.) |
発表年月日 | 2015-09-01 |
資料番号 | COMP2015-18 |
巻番号(vol) | vol.115 |
号番号(no) | COMP-205 |
ページ範囲 | pp.13-20(COMP), |
ページ数 | 8 |
発行日 | 2015-08-25 (COMP) |