文献

J-GLOBAL ID：201002206417710108   整理番号：10A0868654

期待符号語長を最小にするSuffix tree上の最適文脈に基づくデータ圧縮法

Data Compression based on the Optimal Context Determined by the Minimal Expected Codeword Length in a Suffix Tree

著者 (2件)： 友國恵太 (東大 大学院新領域創成科学研究科) ,  山本博資 (東大 大学院新領域創成科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 110  号： 137(IT2010 11-33)  ページ： 7-12  発行年： 2010年07月15日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,suffix treeと算術符号を用いてバイト単位で符号化するデータ圧縮法を取り扱う。suffix treeを用いたPPM^*や動的な反辞書法と同様に,符号化が終了した系列から作成されたsuffix treeを用いて,次の文字を算術符号化する。符号化に用いる文脈の決定に閾値を用いる方法と,符号語長の期待値が最小となる文脈を選択する方法の2つの符号化法を提案する。Calgary Corpusに対する圧縮性能を比較することにより,提案符号化法が大きいファイルサイズの文書データについてPPM^*を上回る圧縮性能を達成できることを示す。(著者抄録)

シソーラス用語： *データ圧縮 ,  長さ ,  データ構造 ,  文字列 ,  文脈 ,  *算術符号 ,  期待値
準シソーラス用語： *サフィックス木 ,  *符号長

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

引用文献 (15件)：

• FIALA, E. Data compression with finite windows. Communications of the Association for Computing Marchinery. 1989, 32, 4, 490-505
• LARSSON, N. Extended application of suffix trees to data compression. Proc. of the IEEE Data Compression Conference, Mar.-Apr. 1996. 1996, 190-199
• 太田. 反辞書に基づく動的算術符号化. 第29回情報理論とその応用シンポジウム予稿集, Nov. 2006. 2006, 2, 513-516
• 太田. 反辞書による適応型データ圧縮法のモデリング. 第30回情報理論とその応用シンポジウム予稿集, Nov. 2007. 2007, 1, 388-391
• OTA, T. On the sliding window variations of antidictionaries data compression using dynamic suffix trees. Proc. of 2008 Int'l Symp. on Information Theory and its Applications (ISITA2008), Dec. 2008, 1105-1110

タイトルに関連する用語 (4件)： 期待 ,  符号語長 ,  文脈 ,  データ圧縮