仮想的な多重分節木による効率良いAIVF符号

• Item type: SIG Technical Reports(1)
• 公開日: 2009-07-21
• タイトル: 仮想的な多重分節木による効率良いAIVF符号
• タイトル / 言語: en
• タイトル: Efficient AIVF Codes with Virtual Multiple Parse Tree
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者名: 吉田, 諭史; 喜田, 拓也
• 著者名(英): Satoshi, Yoshida; Takuya, Kida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Yamamoto と Yokoo ら [2001] によって提案された多重分節木による AIVF 符号は，短い符号長で十分な圧縮率が得られる VF 符号 （可変ブロック固定長符号化） の一つである．しかしながら，情報源アルファベットのサイズを k とすると，k − 1個の分節木を構築するため，ただ一つの分節木を用いる一般的なVF符号化と比べて，符号・復号化時に多くの時間と領域が必要となる．本稿では，多重分節木を一つの分節木に統合し，その木の上で仮想的に多重分節木を模倣するアルゴリズムを示す．これにより，構築すべき分節木の総ノード数を Ω (k2) 個，削減することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10114171
• 書誌情報: 研究報告情報学基礎（FI）; 巻 2009-FI-95, 号 21, p. 1-7, 発行日 2009-07-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会