FSMX情報源に対するベイズ符号のメモリ量削減アルゴリズム  [in Japanese] An Algorithm of Bayes Coding for FSMX Sources to Reduce Required Memory Size  [in Japanese]

Search this Article

Author(s)

    • 中野 晶 NAKANO Akira
    • 早稲田大学理工学部経営システム工学科 Department of Industrial Management Systems Engineering, School of Schience and Engineering, Waseda University
    • 小林 直人 KOBAYASHI Naoto
    • 早稲田大学理工学部経営システム工学科 Department of Industrial Management Systems Engineering, School of Schience and Engineering, Waseda University
    • 松嶋 敏泰 MATSUSHIMA Toshiyasu
    • 早稲田大学理工学部経営システム工学科 Department of Industrial Management Systems Engineering, School of Schience and Engineering, Waseda University

Abstract

ベイズ符号は, 情報源の確率分布のクラスは既知であり, そのパラメータは未知である場合のユニバーサル情報源符号化法で, ベイズ基準のもとで冗長度を最小にする符号である.FSMX情報源に対してベイズ符号を構成するアルゴリズムとして, 松嶋らのアルゴリズムが提案されている.このアルゴリズムでは文脈木を用いて符号化確率を計算するが, 長さnの系列を符号化する際に必要なメモリ量は理論的にO(n)で与えられておらず, 系列によっては莫大なメモリ量が必要となる.本研究では, 松嶋らのアルゴリズムを改良し, 符号化に必要なメモリ量がO(n)となる, FSMX情報源に対するベイズ符号化アルゴリズムを提案し, その性能を評価する.このアルゴリズムで符号化する際に必要な計算量は, 従来法と同等になる.

Bayes code is one of universal source codings, such that a class of the probabilistic model of source is known but the parameters of the probabilistic model are not known. Bayes code provides Bayes optimality in term of redundancy. Matsushima proposed Bayes coding algorithm for FSMX sources. In his algorithm, coding probability is calculated using a context tree. The algorithm, however, needs enormous memory if it encodes some sequences, because upper bound of required memory size is not less or equal to O(n) for sequence size n. In this paper, we propose Bayes coding algorithm for FSMX sources to reduce required memory size, and we investigate its performance. In addition, if we encode sequence x^n in our algorithm, required memory size is O(n). Time complexity of our algorithm is equivalent to Matsushima's algorithm.

Journal

  • IEICE technical report. Information theory

    IEICE technical report. Information theory 105(191), 47-52, 2005-07-15

    The Institute of Electronics, Information and Communication Engineers

References:  4

Cited by:  1

Codes

  • NII Article ID (NAID)
    110003224960
  • NII NACSIS-CAT ID (NCID)
    AN10013083
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    09135685
  • NDL Article ID
    7390592
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  CJPref  NDL  NII-ELS 
Page Top