A method of training parse trees for efficient VF coding based on MDL principle

• 吉田 諭史

• 喜田 拓也

Bibliographic Information

Other Title

• 効率よいVF符号のためのMDL原理に基づく分節木の訓練手法

Abstract

本稿では，VF 符号における辞書データ構造を訓練することで VF 符号の性能を向上させる方法について論じる．ここで議論する VF 符号とは，分節木と呼ばれる木構造を用いて入力テキストを可変長のブロックに分割し，各ブロックに固定長の符号語を割り当てることでテキスト圧縮を達成する情報源符号化方法である．VF 符号の圧縮率は分節木によって決定されるが，入力テキストに対して最適な分節木を構築することは NP 困難であることが知られている．そのため，最適に近い分節木を構築するために，入力テキストを繰り返し走査しつつ分節木を訓練させるという手法が提案されている．しかしながら，既存の手法では，符号化の際に事前に符号語長をパラメータとして与える必要があった．符号語長を長くすればテキストの分割数は減少するが，逆に分節木を保存するコストが増大し最終的なデータ圧縮率を低下させうる．本稿では，MDL 原理に基づく指標を示し，それによって分節木に登録する文字列を貪欲に決定していく訓練アルゴリズムを提案する．このアルゴリズムは，訓練する過程において符号語長を自動的に調節する．In this paper, we discuss a method to improve the performance of VF codes by training the dictionary data structures. A VF code, we discuss here, is a source coding scheme that parses an input text into variable-length blocks with a dictionary tree, which is called a parse tree, and then encodes them by fixed-length codewords. Although the compression ratio of a VF code depends on the parse tree, the problem of constructing the optimal tree for an input text is NP-hard. Thus, the methods that train the parse tree by scanning the text repeatedly in order to reconstruct the tree so that it closes to the optimal one, have been proposed so far. However, the existent algorithms need the codeword length as a parameter before encoding the input. Although the number of parsed blocks decreases when we set the codeword length long, the compression ratio can be depressed since the cost for storing the parse tree increases. In this paper, we present a criterion based on the MDL principle and propose a training algorithm that greedily determines strings to be entered into the parse tree according to the criterion. The proposed algorithm automatically adjusts the codeword length while the training.

Journal

• 研究報告 情報基礎とアクセス技術（IFAT）

  研究報告 情報基礎とアクセス技術（IFAT） 2011 (14), 1-6, 2011-07-26

Details

• CRID: 1574231876753431296
• NII Article ID: 110008583043
• NII Book ID: AN10114171
• Text Lang: ja
• Data Source:
  • CiNii Articles