| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-07-25 14:30 二元情報源に対する畳語分解を用いたデータ圧縮法 ○真矢 滋・山本博資（東大）  IT2013-14 |
|
| 抄録 | （和） | LZ78 符号で用いられる増分分解は増分分解木を用いて実現できるが，横尾は増分分解木とCBT 符号と組 み合わせることにより，二元データ系列を効率よく圧縮できることを示している．しかし，増分分解木は，木の更新 時に葉の対が１つしか増加しないため，分解木の成長が遅くデータ系列の特徴を反映した分解木ができるまでに時間 がかかるという欠点がある．他方，二元系列の複雑度を定義するために，我々は増分分解とT-符号で使用されるT- 分解の中間の特性を持つ畳語分解を提案し，畳語分解木の成長が増分分解木より速く，またT-分解木のように速く成 長しすぎることもないことを示した．そこで，本稿では，畳語分解木を用いた二元系列に対するユニバーサルなデー タ圧縮符号を提案する．そして，二元定常エルゴード情報源に対して，提案符号がある条件の下でユニバーサルにエ ントロピーレートを漸近的に達成できることを証明する．また，コーパスを用いて，提案符号が横尾符号よりよい圧 縮率を達成できることを示す． |
| （英） | The incremental parsing used in the LZ78 code can be implemented by the incremental parsing tree, and Yokoo showed that binary data sequences can be compressed efficiently by combining the incremental parsing tree and the CBT code. But, the incremental parsing tree has a defect such that the growth speed of the tree is slow because only one pair of leaves is incremented at each updating. On the other hand, we proposed the reduplicative parsing to define a new complexity of binary sequences, and we showed that the growth speed of the reduplicative parsing tree is moderate compared with the incremental parsing tree and T-parsing tree, which is used for T-codes. In this paper, we propose new universal compression codes based on the reduplicative parsing tree for binary sequences, and we prove theoretically that the proposed codes can attain the entropy rate universally for any stationary ergodic binary sources under a certain condition. Furthermore, we show that a proposed code can attain better compression than Yokoo code for corpuses. |
|
| キーワード | （和） | ユニバーサルデータ圧縮符号 / 増分分解 / 畳語分解 / 横尾符号 / 分解木 / / / |
| （英） | universal data compression code / incremental parsing / reduplicative parsing / Yokoo code / parsing tree / / / | |
| 文献情報 | 信学技報, vol. 113, no. 153, IT2013-14, pp. 17-22, 2013年7月. | |
| 資料番号 | IT2013-14 | |
| 発行日 | 2013-07-18 (IT) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IT2013-14 |
|
| 研究会情報 | |
| 研究会 | IT |
| 開催期間 | 2013-07-25 - 2013-07-26 |
| 開催地（和） | 早稲田大学 西早稲田キャンパス |
| 開催地（英） | Nishi-Waseda campus, Waseda University |
| テーマ（和） | フレッシュマンセッション，一般 |
| テーマ（英） | freshman session, general |
| 講演論文情報の詳細 | |
| 申込み研究会 | IT |
| 会議コード | 2013-07-IT |
| 本文の言語 | 日本語 |
| タイトル（和） | 二元情報源に対する畳語分解を用いたデータ圧縮法 |
| サブタイトル（和） | |
| タイトル（英） | A Data Compression Scheme based on Reduplicative Parsing for Binary Sources |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ユニバーサルデータ圧縮符号 / universal data compression code |
| キーワード(2)（和/英） | 増分分解 / incremental parsing |
| キーワード(3)（和/英） | 畳語分解 / reduplicative parsing |
| キーワード(4)（和/英） | 横尾符号 / Yokoo code |
| キーワード(5)（和/英） | 分解木 / parsing tree |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 真矢 滋 / Shigeru Maya / |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Univ. of Tokyo) |
| 第2著者 氏名（和/英/ヨミ） | 山本 博資 / Hirosuke Yamamoto / |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Univ. of Tokyo) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-07-25 14:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IT |
| 資料番号 | IT2013-14 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.153 |
| ページ範囲 | pp.17-22 |
| ページ数 | 6 |
| 発行日 | 2013-07-18 (IT) |
[研究会発表申込システムのトップページに戻る]