文献

J-GLOBAL ID：201302203882780298   整理番号：13A1340300

二元情報源に対する畳語分解を用いたデータ圧縮法

A Data Compression Scheme based on Reduplicative Parsing for Binary Sources

著者 (2件)： 真矢滋 (東大 大学院情報理工学系研究科) ,  山本博資 (東大 大学院新領域創成学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 153(IT2013 11-31)  ページ： 17-22  発行年： 2013年07月18日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： LZ78符号で用いられる増分分解は増分分解木を用いて実現できるが,横尾は増分分解木とCBT符号と組み合わせることにより,二元データ系列を効率よく圧縮できることを示している。しかし,増分分解木は,木の更新時に葉の対が1つしか増加しないため,分解木の成長が遅くデータ系列の特徴を反映した分解木ができるまでに時間がかかるという欠点がある。他方,二元系列の複雑度を定義するために,我々は増分分解とT-符号で使用されるT-分解の中間の特性を持つ畳語分解を提案し,畳語分解木の成長が増分分解木より速く,またT-分解木のように速く成長しすぎることもないことを示した。そこで,本稿では,畳語分解木を用いた二元系列に対するユニバーサルなデータ圧縮符号を提案する。そして,二元定常エルゴード情報源に対して,提案符号がある条件の下でユニバーサルにエントロピーレートを漸近的に達成できることを証明する。また,コーパスを用いて,提案符号が横尾符号よりよい圧縮率を達成できることを示す。(著者抄録)

シソーラス用語： *データ圧縮 ,  *符号化 ,  情報源 ,  エルゴード性 ,  分解 ,  *符号 ,  木【グラフ】 ,  エントロピー
準シソーラス用語： 圧縮符号化 ,  二元情報源 ,  増分分解 ,  畳語分解 ,  *データ圧縮符号 ,  LZ78符号 ,  CBT符号 ,  分解木 ,  横尾符号

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (3件)： 情報源 ,  分解 ,  データ圧縮