ユニバーサルデータ圧縮における一般的な文脈木重みつけ方式について

• 鈴木 讓

  大阪大学理学部数学科

書誌事項

タイトル別名

• On A Generalized Context Tree Weighting Scheme for Universal Data Compression

抄録

情報源の知識を仮定しないデータ圧縮(ユニバーサルデータ圧縮)は、実用的・理論的見地から種々の検討がなされている。本論文では、各系列が生成する確率を推定して算術符号を利用する枠組を前提とした議論をすすめている。特に、系列の各データの発生確率が直前の深さ数データに依存する場合に、その状態ごとのデータの発生確率(パラメータ)のみならず、その状態の区切り方(モデル)までも未知な条件でのデータ圧縮の考察を行なった。近年提案された文脈木重みつけ(CTW)方式は、深さおよび系列長の積のオーダの計算量でで符号化・復号化を可能としている。本論文では、CTW方式がモデルに関して特定の重みづけをしている点を指摘し、その制約をほぼ排除する一般的な枠組を提案している。さらに、実用的な側面で本方式が適用できる例をあげ、その有効性を確認している。
This paper addresses a generalized Context Tree Weighting(CTW) method.The original CTW method which was originally proposed by Willems,Shtarkov,and Tjalkens assumes a specific weight over the models represnted as Finite State Machine(FSM)X with bounded depth D(FSMX(D)).On the other hand,the weight proposed in GCTW successfully fits to a given prior over the models although it cannot always represent the exact prior because of its simplicity. The computational order of encoding and decoding and the model class(FSMX(D))are the same in CTW and GCTW.

収録刊行物

• 電子情報通信学会技術研究報告. IT, 情報理論

  電子情報通信学会技術研究報告. IT, 情報理論 94 (171), 19-24, 1994-07-23

  一般社団法人電子情報通信学会

キーワード

• ユニバーサルデータ圧縮
• 文脈木重みつけ(CTW)方式
• モデル
• パラメータ
• FSM X

詳細情報

• CRID: 1572261552261070720
• NII論文ID: 110003197394
• NII書誌ID: AN10013083
• 本文言語コード: en
• データソース種別:
  • CiNii Articles