仮想的な多重分節木による効率良いAIVF符号 Efficient AIVF Codes with Virtual Multiple Parse Tree

この論文にアクセスする

この論文をさがす

著者

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

抄録

Yamamoto と Yokoo ら [2001] によって提案された多重分節木による AIVF 符号は,短い符号長で十分な圧縮率が得られる VF 符号 (可変ブロック固定長符号化) の一つである.しかしながら,情報源アルファベットのサイズを k とすると,k − 1個の分節木を構築するため,ただ一つの分節木を用いる一般的なVF符号化と比べて,符号・復号化時に多くの時間と領域が必要となる.本稿では,多重分節木を一つの分節木に統合し,その木の上で仮想的に多重分節木を模倣するアルゴリズムを示す.これにより,構築すべき分節木の総ノード数を Ω (k2) 個,削減することができる.The AIVF code with multiple parse trees presented by Yamamoto and Yokoo[2001] is one of the variable-length-to-fixed-length codes (VF codes), and it can achieve a good compression ratio even in a short codeword length. However it needs much time and space for both encoding and decoding than an ordinary VF code using just one parse tree, since it constructs k−1 parse trees when k is the size of the alphabet. In this paper, we present an algorithm that integrates the multiple parse trees into one and emulates encoding and decoding on it. We also present that we can reduce the total number of nodes which must be constructed, by Ω(k2).

収録刊行物

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

    研究報告データベースシステム(DBS) 2009-DBS-148(21), 1-7, 2009-07-21

    情報処理学会

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

各種コード

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