| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2011-03-04 09:00 最小期待符号語長とESC確率推定切換え法に基づく改良PPM* ○友國恵太・山本博資（東大）  IT2010-104 ISEC2010-108 WBS2010-83 |
|
| 抄録 | （和） | PPMにおいて用いられるESCはsuffix tree上のあるノードで新しい文字が出現することを意味する．これまでにそのESC確率を推定するための様々な手法が提案されてきた．しかし，それらのESC確率の推定値はESCの実際の頻度分布と大きくずれる場合があり，このずれがPPMの圧縮率を悪くしている．Calgary Corpus, Canterbury Corpus, Large Corpusに対して，PPMXで用いられるESC確率の推定値は，suffix tree上の枝数が多いノードにおいてはESCの実際の頻度分布とよく一致しているが，枝数が少ないノードにおいてはESCの実際の頻度分布よりも低く見積もられる．そこで本稿では，ESCの実際の頻度分布により近い推定値を出力できるように，suffix tree上のそれぞれのノードの枝数に応じて，PPMXの推定法とその改良推定法を切り換える手法(ESC確率推定切換え法)を提案する．友國-山本はPPM*の改良法として，符号語長の期待値が最小となる文脈のもとで符号化を行う手法(期待値法)を提案している．この期待値法とESC確率推定切換え法を組み合わせて用いた場合，それぞれのCorpusに対して，現在PPMファミリーの中で最も良い圧縮率を達成するPPMZよりも良い圧縮率が得られることを示す． |
| （英） | For the PPM data compression algorithm, several methods have been proposed to estimate the ESC probability, where ESC represents the occurrence of a new symbol at a node in the suffix tree used in the PPM. However, the estimated ESC probability is often deviated from the actual frequencies of ESC, and this deviation worsens the compression rate of the PPM. In this paper, we propose a new method to estimate the ESC probability. We show by Calgary, Canterbury, and Large Corpuses that the estimation method of PPMX is a good estimator when a node in the suffix tree has many child nodes, but the estimated ESC probability is much lower than the actual frequency when a node has a few child nodes. So, in our method, the ESC probability is estimated by switching the original and our modified estimation methods of PPMX based on the number of child nodes at each node. By combining this ESC probability estimation method and a variant of PPM, in which a coding context is determined based on the minimum expected codeword length, we show by the evaluation of compression rate for the corpuses that the proposed PPM can beat the PPMZ, which was the best variant in the family of PPM. | |
| キーワード | （和） | PPM / ESC確率 / データ圧縮 / suffix tree / 算術符号 / / / |
| （英） | PPM / escape probability / data compression / suffix tree / arithmetic coding / / / | |
| 文献情報 | 信学技報, vol. 110, no. 442, IT2010-104, pp. 235-242, 2011年3月. | |
| 資料番号 | IT2010-104 | |
| 発行日 | 2011-02-24 (IT, ISEC, WBS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IT2010-104 ISEC2010-108 WBS2010-83 |
|
| 研究会情報 | |
| 研究会 | ISEC IT WBS |
| 開催期間 | 2011-03-03 - 2011-03-04 |
| 開催地（和） | 大阪大学 |
| 開催地（英） | Osaka University |
| テーマ（和） | 一般：情報通信基礎サブソサイエティ合同研究会 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | IT |
| 会議コード | 2011-03-ISEC-IT-WBS |
| 本文の言語 | 日本語 |
| タイトル（和） | 最小期待符号語長とESC確率推定切換え法に基づく改良PPM* |
| サブタイトル（和） | |
| タイトル（英） | An improved PPM* Algorithm based on the Minimal Expected Codeword Length and Switching Escape Probability Estimation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | PPM / PPM |
| キーワード(2)（和/英） | ESC確率 / escape probability |
| キーワード(3)（和/英） | データ圧縮 / data compression |
| キーワード(4)（和/英） | suffix tree / suffix tree |
| キーワード(5)（和/英） | 算術符号 / arithmetic coding |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 友國 恵太 / Keita Tomokuni / トモクニ ケイタ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Univ. of Tokyo) |
| 第2著者 氏名（和/英/ヨミ） | 山本 博資 / Hirosuke Yamamoto / ヤマモト ヒロスケ |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Univ. of Tokyo) |
| 講演者 | 第1著者 |
| 発表日時 | 2011-03-04 09:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IT |
| 資料番号 | IT2010-104, ISEC2010-108, WBS2010-83 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.442(IT), no.443(ISEC), no.444(WBS) |
| ページ範囲 | pp.235-242 |
| ページ数 | 8 |
| 発行日 | 2011-02-24 (IT, ISEC, WBS) |
[研究会発表申込システムのトップページに戻る]