VF符号と算術符号の組合せ手法による圧縮性能の向上について A Combination of VF Coding with Arithmetic Coding for Efficient Compression

この論文にアクセスする

この論文をさがす

著者

    • 喜田 拓也 KIDA TAKUYA
    • 北海道大学 大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

抄録

本稿では,VF 符号に算術符号を組み合わせることで,検索の効率と圧縮率とを保つ方法について議論する.ここで議論する VF 符号とは,分節木と呼ばれる圧縮のための辞書木を用いて元のテキストを可変長のブロックに分割し,各ブロックに固定長の符号語を割り当てることでデータ圧縮を達成する情報源符号化方法である.VF 符号は,近年,パターン照合を高速化することのできるデータ圧縮法として見直されている.VF 符号は,符号語長が固定であるという制限から,分節木が小さいときには圧縮性能が低い.圧縮率を向上させるには分節木を大きくすればよいが,逆にパターン照合時の前処理に時間がかかり全体の検索の速度を低下させてしまう.そこで,VF 符号の出力を,展開が早い他の符号化方法で符号化することで,圧縮率と検索速度の両方を保つ方法が考えられる.本稿では,代表的な VF 符号である Tunstall 符号および VF 符号の中では優れた圧縮性能を持つ STVF 符号に Range Coder を組み合わせた圧縮方法について,その圧縮性能を実験的に評価した.その結果,符号語長が短い場合において,それぞれおよそ 18 ~ 20%,7 ~ 15% の圧縮率改善が見られた.In this paper, we discuss about a method to preserve both search efficiency and compression ratio by combining VF coding with arithmetic coding. A VF code, we discuss here, is a source coding scheme that parses an input text into variable-length blocks with a dictionary tree, called parse tree, and then encodes them by fixed-length codewords. It is reevaluated recently since it can accelerate pattern matching on the text. As the codewords are fixed length, a VF code usually has low compression ratios when its parse tree is small. Although we can obtain higher compression ratios when we make the parse tree large enough, pattern matching speed will decline since we take much more time to preprocess such large tree for compressed pattern matching. One of the natural trade-off solutions is to encode outputs of a VF code with the other compression method whose decompression speed is fast. We would be able to do fast pattern matching on such compressed text by decoding it to a sequence of VF codewords once and then searching on the sequence without decoding the codewords. In this paper, we investigated a combination of Tunstall codes or STVF codes with Range coder. The experimental results show that those combinations can improve the compression ratios about 18 ~ 20% and 7 ~ 15%, respectively, when the codeword length is short.

収録刊行物

  • 研究報告データベースシステム(DBS)

    研究報告データベースシステム(DBS) 2010-DBS-150(10), 1-8, 2010-07-28

    情報処理学会

参考文献:  17件中 1-17件 を表示

各種コード

  • NII論文ID(NAID)
    110008003671
  • NII書誌ID(NCID)
    AN10112482
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • NDL 記事登録ID
    025063911
  • NDL 請求記号
    YH247-911
  • データ提供元
    CJP書誌  NDL  NII-ELS  IPSJ 
ページトップへ