(57)【要約】【課題】カノニカルハフマン符号化を含む半静的エントロピー符号化における符号化効率の向上を図る。【解決手段】セレクタ１は、複数のシンボルの列としての原データＭをシンボルの種類に応じて分割する。第１のＣＨ符号器２のそれぞれは、自己に対応付けられたシンボルの種類に応じた固有の辞書情報を用いて、セレクタ１によって分割されたデータを入力としたカノニカルハフマン符号化処理を行うことで、第１の符号列Ｍ'の一部を構成する個々の符号語を順次出力する。第２のＣＨ符号器３は、複数の第１のＣＨ符号器２で用いられる複数の辞書情報を集合化した第１の付加情報Ｅを入力としたカノニカルハフマン符号化処理を行うことで、第２の符号列Ｅ'と、辞書情報である第２の付加情報Ｅ''とを出力する。【選択図】図３
2006060274.tif 000002
【特許請求の範囲】
【請求項１】
半静的エントロピー符号化システムにおいて、
複数のシンボルの列としての原データを当該原データに含まれるシンボルの種類に応じて分割するセレクタと、
互いに並列に設けられており、それぞれが、自己に対応付けられたシンボルの種類に固有の辞書情報を用いて、前記セレクタによって分割されたデータを入力とした半静的エントロピー符号化処理を行うことによって、第１の符号列の一部を構成する個々の符号語を順次出力する複数の第１の半静的エントロピー符号器と、
前記複数の第１の半静的エントロピー符号器で用いられる複数の辞書情報を集合化した第１の付加情報を入力とした半静的エントロピー符号化処理を行うことによって、第２の符号列と、当該第２の符号列から前記第１の付加情報への復号時に必要な辞書情報である第２の付加情報とを出力する第２の半静的エントロピー符号器と
を有することを特徴とする半静的エントロピー符号化システム。
【請求項２】
前記第１の半静的エントロピー符号器のそれぞれは、前記第１の符号列を構成する個々の符号語の出力に先立ち、自己に対応付けられたシンボルの種類に応じた辞書情報を生成することを特徴とする請求項１に記載された半静的エントロピー符号化システム。
【請求項３】
一の種類のシンボルに対応付けられた前記第１の半静的エントロピー符号器は、当該一の種類のシンボルを遷移元とする各遷移状態に対応した符号語が記述されている辞書情報に基づいて、前記セレクタによって分割されたデータを符号語に変換することを特徴とする請求項１または２に記載された半静的エントロピー符号化システム。
【請求項４】
前記第１の半静的エントロピー符号器は、前記半静的エントロピー符号化処理として、カノニカルハフマン符号化処理を行うカノニカルハフマン符号器であることを特徴とする請求項１から３のいずれかに記載された半静的エントロピー符号化システム。
【請求項５】
前記第２の半静的エントロピー符号器は、前記半静的エントロピー符号化処理として、カノニカルハフマン符号化処理を行うカノニカルハフマン符号器であることを特徴とする請求項４に記載された半静的エントロピー符号化システム。
【請求項６】
請求項１から５のいずれかに記載された半静的エントロピー符号システムより出力された前記第１の符号列と、前記第２の符号列と、前記第２の付加情報とを用いて、前記原データの復号化を行う半静的エントロピー復号化システムにおいて、
前記第２の付加情報を辞書情報として用い、前記第２の符号列を入力とし、かつ、前記半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、前記第１の付加情報を復号する第１の半静的エントロピー復号器と、
前記第１の半静的エントロピー符号器によって復号された前記第１の付加情報を辞書情報として用い、前記第１の符号列を入力とし、かつ、前記半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、前記原データを構成する個々のシンボルを順次復号する複数の第２の半静的エントロピー復号器と
を有することを特徴とする半静的エントロピー復号化システム。
【請求項７】
半静的エントロピー符号化方法において、
それぞれが、複数のシンボルの列としての原データに含まれるシンボルの種類に対応して設けられているとともに、それぞれが、一の種類のシンボルを遷移元とする各遷移状態に対応した符号語が記述されている複数の辞書情報を生成する第１のステップと、
前記複数の辞書情報を集合化した第１の付加情報を入力とした半静的エントロピー符号化処理を行うことによって、第２の符号列と、当該第２の符号列から前記第１の付加情報への復号時に必要な辞書情報である第２の付加情報とを出力する第２のステップと、
前記複数の辞書情報を用いて、前記原データを入力とした半静的エントロピー符号化処理を行うことによって、第１の符号列を出力する第３のステップと
を有することを特徴とする半静的エントロピー符号化方法。
【請求項８】
前記第２のステップにおける前記半静的エントロピー符号化処理は、カノニカルハフマン符号化処理であることを特徴とする請求項７に記載された半静的エントロピー符号化方法。
【請求項９】
前記第３のステップにおける前記半静的エントロピー符号化処理は、カノニカルハフマン符号化処理であることを特徴とする請求項８に記載された半静的エントロピー符号化方法。
【請求項１０】
請求項７から９のいずれかに記載された半静的エントロピー符号方法より出力された前記第１の符号列と、前記第２の符号列と、前記第２の付加情報とを用いて、前記原データの復号化を行う半静的エントロピー復号化方法において、
前記第２の付加情報を辞書情報として用いて、前記第２の符号列を入力とし、かつ、前記半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、前記第１の付加情報を復号する第４のステップと、
前記第１の付加情報を辞書情報として用いて、前記第１の符号列を入力とし、かつ、前記半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、前記原データを構成する個々のシンボルを復号する第５のステップと
を有することを特徴とする半静的エントロピー復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半静的エントロピー符号化システム、半静的エントロピー復号化システム、半静的エントロピー符号化方法および半静的エントロピー復号化方法に関する。
【背景技術】
【０００２】
ハフマン符号化や算術符号化に代表されるエントロピー符号化は、対象シンボル列におけるシンボルの出現頻度に基づき、その総符号量の低減を図る手法である。特に、テキストファイルのように特定シンボル間の出現順序に強い相関がある場合、相関関係を記述する確率論的有限状態遷移モデルに基づいて、エントロピー符号を構成するマルコフモデル圧縮が有効になる。動的マルコフ圧縮といった近年のマルコフモデル圧縮の実装は、適応的算術符号を基礎としている点に注意する必要がある。適応的符号化は、半静的符号化と比較して多くの処理時間を必要とし、符号化効率も低いので、一見すると半静的符号化を用いてマルコフモデル圧縮を実装した方が有利であるかのように思われる。しかしながら、半静的符号化を用いた場合、シンボルの種類と遷移モデルの次元数との増加に伴って、出現頻度あるいはこれと等価な情報を記録するための付加的符号量（オーバーヘッド）が膨大になるという符号化効率上の問題が発生する。そのため、適応的符号化が選択された上で、これに起因する符号化効率の低下を考慮し、ハフマン符号よりも複雑な処理を要するが、符号化効率が高い算術符号が選択されたと考えられる。すなわち、マルコフモデル圧縮に関する研究は、符号化および復号の速度を犠牲にして、符号化効率の向上を目指す傾向にある。
【０００３】
なお、カノニカルハフマン符号に関して、例えば、特許文献１には、カノニカルハフマンコードツリーを用いて、メモリに可変長コードワードの長さを貯蔵せずに、入力データをコーディングする符号化手法が開示されている。また、特許文献２には、カノニカルハフマンコードツリーを用いて、符号化された可変長コードワードを復号化する復号化手法が開示されている。
【０００４】
【特許文献１】特開平１１−１９５９９９号公報
【特許文献２】特開平１０−１３２４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、近年のカノニカル表現の導入によるハフマン符号の性能改善は注目に値する。従来、出現頻度によって構成される二分木、すなわちハフマン木に基づくハフマン符号は、ハフマン木に関するオーバーヘッドが多く、木探索に多くの処理時間を必要とするという欠点があった。これに対して、カノニカルハフマン符号は、ハフマン符号と同一の符号化効率を保ちながら、ハフマン木の利用を排除することを可能にし、オーバーヘッドおよび処理速度に関する問題を改善している。すなわち、１次マルコフモデル圧縮を、カノニカルハフマン符号に基づいて実装することで、符号化効率の向上を図れる可能性がある。
【０００６】
本発明は、かかる事情に鑑みてなされたものであり、その目的は、カノニカルハフマン符号化を含む半静的エントロピー符号化における符号化効率の向上を図ることである。
【課題を解決するための手段】
【０００７】
かかる課題を解決するために、第１の発明は、セレクタと、互いに並列に設けられた複数の第１の半静的エントロピー符号器と、第２の半静的エントロピー符号器とを有する半静的エントロピー符号化システムを提供する。セレクタは、複数のシンボルの列としての原データをこれに含まれるシンボルの種類に応じて分割する。第１の半静的エントロピー符号器のそれぞれは、自己に対応付けられたシンボルの種類に応じた辞書情報を用いて、セレクタによって分割されたデータを入力とした半静的エントロピー符号化処理を行うことによって、第１の符号列の一部を構成する個々の符号語を順次出力する。第２の半静的エントロピー符号器は、複数の第１の半静的エントロピー符号器で用いられる複数の辞書情報を集合化した第１の付加情報を入力とした半静的エントロピー符号化処理を行うことによって、第２の符号列と、この第２の符号列から第１の付加情報への復号時に必要な辞書情報である第２の付加情報とを出力する。
【０００８】
ここで、第１の発明において、第１の半静的エントロピー符号器のそれぞれは、第１の符号列を構成する個々の符号語の出力に先立ち、自己に対応付けられたシンボルの種類に応じた辞書情報を生成することが好ましい。
【０００９】
第１の発明において、一の種類のシンボルに対応付けられた第１の半静的エントロピー符号器は、この一の種類のシンボルを遷移元とする各遷移状態に対応した符号語が記述されている辞書情報に基づいて、セレクタによって分割されたデータを符号語に変換することが好ましい。
【００１０】
第１の発明において、第１の半静的エントロピー符号器は、半静的エントロピー符号化処理として、カノニカルハフマン符号化処理を行うカノニカルハフマン符号器であってもよい。この場合、第２の半静的エントロピー符号器は、半静的エントロピー符号化処理として、カノニカルハフマン符号化処理を行うカノニカルハフマン符号器であることが好ましい。
【００１１】
第２の発明は、上記第１の発明にかかる半静的エントロピー符号システムより出力された第１の符号列と、第２の符号列と、第２の付加情報とを用いて、原データの復号化を行う半静的エントロピー復号化システムを提供する。この復号化システムは、第１の半静的エントロピー復号器と、複数の第２の半静的エントロピー復号器とを有する。第１の半静的エントロピー復号器は、第２の付加情報を辞書情報として用い、第２の符号列を入力とし、かつ、半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、第１の付加情報を復号する。また、複数の第２の半静的エントロピー復号器は、第１の半静的エントロピー復号器によって復号された第１の付加情報を辞書情報として用い、第１の符号列を入力とし、かつ、半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、原データを構成する個々のシンボルを順次復号する。
【００１２】
第３の発明は、半静的エントロピー符号化方法を提供する。この符号化方法は、それぞれが、複数のシンボルの列としての原データに含まれるシンボルの種類に対応して設けられているとともに、それぞれが、一の種類のシンボルを遷移元とする各遷移状態に対応した符号語が記述されている複数の辞書情報を生成する第１のステップと、複数の辞書情報を集合化した第１の付加情報を入力とした半静的エントロピー符号化処理を行うことによって、第２の符号列と、この第２の符号列から第１の付加情報への復号時に必要な辞書情報である第２の付加情報とを出力する第２のステップと、複数の辞書情報を用いて、原データを入力とした半静的エントロピー符号化処理を行うことによって、第１の符号列を出力する第３のステップとを有する。
【００１３】
ここで、第３の発明において、第２のステップにおける半静的エントロピー符号化処理は、カノニカルハフマン符号化処理であってもよい。この場合、第３のステップにおける半静的エントロピー符号化処理は、カノニカルハフマン符号化処理であることが好ましい。
【００１４】
第４の発明は、上記第３の発明にかかる半静的エントロピー符号方法より出力された第１の符号列と、第２の符号列と、第２の付加情報とを用いて、原データの復号化を行う半静的エントロピー復号化方法を提供する。この復号化方法は、第２の付加情報を辞書情報として用いて、第２の符号列を入力とし、かつ、半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、第１の付加情報を復号する第４のステップと、第１の付加情報を辞書情報として用いて、第１の符号列を入力とし、かつ、半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行うことによって、原データを構成する個々のシンボルを復号する第５のステップとを有する。
【発明の効果】
【００１５】
本発明によれば、複数の第１の半静的エントロピー符号器が別個に備える複数の辞書情報を第２の半静的エントロピー符号器にて符号化することによって、半静的エントロピー符号化における符号化効率の向上を図ることができる。
【発明を実施するための最良の形態】
【００１６】
まず、本実施形態にかかる符号化システムの具体的な構成の説明に先立ち、必要な要素技術について、ハフマン符号および適応的ハフマン符号、カノニカルハフマン符号、１次マルコフモデル圧縮の順序で概略的に説明する。
【００１７】
エントロピー符号化の代表例であるハフマン符号化は、シンボルの出現頻度計算のため、符号化の対象となるシンボル列としての原データを事前に走査した後、構成された符号語にシンボルを変換する半静的符号化である。これに対して、適応的ハフマン符号化は、一つのシンボル毎に出現頻度を更新し、随時、符号語へ変化させる適用的（動的）符号化である。ハフマン符号語は、出現頻度情報に基づき構成されたハフマン木において、葉から根に至る一連の枝をビット列で表現することで決定される。復号時には、符号列を１ビット毎に読み込み、枝を辿ることでシンボルを割り出す。ハフマン符号化は、ハフマン木に関するオーバーヘッドが大きく、木探索に多くの処理時間を要するという欠点がある。これに対して、適応的ハフマン符号化は、符号機構および復号機構がハフマン木の初期構造のみを共有し、ｋ番目のシンボルを処理する際に、ｋ−１番目までの出現頻度を利用する。このため、ハフマン木に関するオーバーヘッドがないという利点を有する。その反面、処理の進行とともにシンボルの出現頻度が速やかに安定しないと、符号化効率の低下が発生する。また、逐次的に出現頻度を計算し、ハフマン木の再構成を必要とするため、ハフマン符号化よりも多くの処理時間を必要とする。
【００１８】
ハフマン符号化では、出現頻度情報からシンボルと符号語との対応を図るため、復号機構に出現頻度情報を渡す必要がある。これに対して、カノニカルハフマン符号化では、出現頻度情報を正規化して、ハフマン符号で得られる符号語のビット長を直接算出しているので、このビット長から符号語を生成することができる。つまり、復号機構に出現頻度情報を渡す必要はなく、ビット長の情報を渡すだけで足りる。出現頻度値のデータ範囲は、１シンボルあたりファイルサイズ分まで増える場合があるが、ビット長では多くとも数十程度で済む。ビット長と出現頻度値との関係は、概ね次のような対数スケールになる。カノニカルハフマン符号化は、出現頻度情報を大きく減らすだけではなく、高速な処理速度と低メモリ消費量とを実現している。
ビット長＝− ｌｏｇ （出現頻度値／全出現数）
【００１９】
マルコフモデル圧縮では、出現頻度情報が膨大な量になるが、カノニカルハフマン符号を用いると対数スケールで減らすことができる。また、マルコフモデル圧縮以外の手法は、処理速度が低く、この点からもカノニカルハフマン符号の優位性は明かである。マルコフモデル圧縮では、複数のカノニカルハフマン符号を同時に扱うため、ビット長の情報が柱状の場合よりも増大するが、逆にビット長情報をシンボルとした２次圧縮を施すことで、ビット長情報のオーバーヘッドを更に減らすことができる。
【００２０】
カノニカルコードの一種であるカノニカルハフマン符号語は、出現頻度から算出した符号語長を用いて、符号語割り当て規則にしたがって決定される。そのため、符号器および復号器は、符号語長のみを共有する。特に、ハフマン木と比較して、出現頻度を正規化した語長は、より少ない符号量で記述できるため、効果的にオーバーヘッドを減らすことができる。この性質に加えて、復号は二分木探索を用いないテーブル参照によって実装できるため、より少ないワークスペースで高速に実行することができる。具体的には、カノニカルハフマン符号語の割り当て規則は、下記の３つの条件を満足する必要がある。
【００２１】
（割り当て規則の条件）
（条件１）符号語長はハフマン符号語と同じである。
（条件２）符号語を語長毎に並べた場合、符号語を非負整数値と対応し、かつ、シンボル順に連続する。
（条件３）符号語長がｌi，ｌjである符号語の非負整数値をｃi，ｃjとするとｌi＜ｌjの場合には、下式が成立する。
【数１】
2006060274.tif 000003
【００２２】
図１に示したカノニカルハフマン符号を用いて、カノニカルハフマン符号の特徴を具体的に説明する。まず、語長５の符号語に着目すると、シンボルＤの値は26、シンボルＥの値は27、シンボルＪの値は28、シンボルＫの値は29、シンボルＬの値は30になっており、シンボルＤ，Ｅ，Ｊ，Ｋ，Ｌの整列順に符号語の値が連続していることがわかる。これは（条件２）に基づく性質であり、５ビットだけ読み込まれた値が26から30の範囲に存在するならば、順序関係から直ちにシンボルが判定できることを意味している。また、シンボルＣの符号語1100は、語長５以上の符号語の上位４ビットに対して、値として常に小さくなる。これは、（条件３）に基づく性質であり、語長の判定以前に、その語長の範囲を特定することができることを意味している。
【００２３】
ｎ次マルコフモデル圧縮は、対象シンボルの直前に出現したｎ個のシンボルにより対象シンボルを予測するエントロピー符号化の一種である。特に、１次マルコフモデル圧縮では、対象シンボルに対して、その直前に出現したシンボルの確率を利用する。例えば、３種類のシンボル｛Ａ，Ｂ，Ｃ｝からなる下記のシンボル列を考える。
（シンボル列）
Ａ,Ｂ,Ａ,Ａ,Ｂ,Ｃ,Ｂ,Ｃ,Ａ,Ａ,Ｂ,Ｃ,Ａ,Ｂ,Ｃ,Ｂ,Ａ,Ｂ,Ｂ,Ｃ
【００２４】
このシンボル列に関して、例えばＡ（遷移元のシンボル）の次にＡ（遷移先のシンボル）が出現する確率、すなわち、遷移状態の出現確率として3/8が成り立つ。それぞれの遷移状態の出現確率を下表に示す。ここで、初期状態（すなわち、最前シンボルＡを遷移先とした遷移状態に関する遷移元）をＡとする。また、図２は、本ケースにおける状態遷移モデル（マルコフモデル）である。
（遷移確率表）
遷移元のシンボル    遷移先のシンボル    出現確率    ビットパターン
Ａ                  Ａ              3/8           0
Ａ                  Ｂ              5/8           1
Ａ                  Ｃ              0/8        なし
Ｂ                  Ａ              2/8          10
Ｂ                  Ｂ              1/8          11
Ｂ                  Ｃ              5/8           0
Ｃ                  Ａ              2/4           0
Ｃ                  Ｂ              2/4           1
Ｃ                  Ｃ              0/4        なし
【００２５】
同表に示したビットパターンは、各状態毎に構成されたハフマン符号である。通常のハフマン符号では総符号量が32ビットであるのに対して、同表によって変換された符号列”01100101000100101101110”の総符号量は23ビットとなる。当然ながら、この23ビット以外にもオーバーヘッド（付加情報）が必要になる。一般に、Ｌ種類のシンボルからなるｎ次状態遷移モデルは、Ｌn種類の遷移状態を有するため、最悪の場合では、オーバーヘッドは次元数に対して指数的に増加することになる。
【００２６】
半静的エントロピー符号化に基づく１次マルコフモデル圧縮のアルゴリズムは、次のようになる。対象シンボル集合をＳ＝｛ｓ1,ｓ2,・・・,ｓL｝、各状態におけるシンボルと符号語との対応表（以下「辞書」という）をＤi（i∈Ｓ）とし、入力シンボル列をＭ＝｛ｍ1,ｍ2,・・・,ｍn：ｍj∈Ｓ｝とする。この表記の下で、符号化と復号アルゴリズムは次のようになる。
【００２７】
（符号化アルゴリズム）
（１）Ｄi（for ∀i）を初期化、符号器と復号器との間で合意する初期シンボルをｐに格納し、ｋ＝１とする。
（２）Ｄpにｍkを登録する。
（３）ｐ＝ｍk、ｋ＝ｋ＋１とする。
（４）ｋ≦ｎである場合には（２）に戻る。
（５）Ｄo（for ∀i）について符号化用に辞書を構築する。
（６）符号器と復号器との間で合意する初期シンボルをｐに格納し、ｋ＝１とする。
（７）Ｄpを用いてｍkの符号語を出力する。
（８）ｐ＝ｍk、ｋ＝ｋ＋１とする。
（９）ｋ≦ｎである場合には（７）に戻る。
（１０）Ｄi（for ∀i）を出力する。
【００２８】
（復号化アルゴリズム）
（１）Ｄi（for ∀i）を復号用に再構築し、符号器と復号器との間で合意する初期シンボルをｐに格納する。
（２）Ｄpを用いて、シンボルを１つ復号して出力するとともに、これをｐに格納する。
（３）符号列が残っている場合には（２）に戻る。
【００２９】
符号化対象のシンボル集合は、８ビットの符号なし整数値を使用する。このとき、Ｌ256、Ｓ＝｛0,1,2,・・・,255｝となる。なお、半静的エントロピー符号器を用いる場合に必要となる出現頻度情報またはこれと等価な情報の取り扱いについては後述する。
【００３０】
つぎに、本実施形態にかかる符号化システムの具体的な構成について説明する。図３は、本実施形態にかかるカノニカルハフマン符号化システムのブロック図である。この符号化システムは、セレクタ１と、複数の第１のカノニカルハフマン符号器２（以下「第１のＣＨ符号器２」という）と、第２のカノニカルハフマン符号器３（以下「第２のＣＨ符号器３」という）とで構成されている。セレクタ１は、複数のシンボル列としての原データＭを、これに含まれるシンボルの種類に応じて分割する。例えば、原データＭ中に３種類のシンボルａ，ｂ，ｃが含まれている場合、原データＭは、シンボルａのデータと、シンボルｂのデータと、シンボルｃのデータといった３つの中間データに分割される。複数の第１のＣＨ符号器２は、セレクタ１の後段において互いに並列に設けられている。それぞれの第１のＣＨ符号器２は、シンボルの種類に対応付けられている。例えば、上記ケースにおいて、同図の最上に位置するＣＨ符号器２がシンボルａに、上から２番目のＣＨ符号器２がシンボルｂに、上から３番目のＣＨ符号器２がシンボルｃにそれぞれ対応付けられているといった如くである。第１のＣＨ符号器２の個数は、原データＭに含まれるシンボルの種類の数に相当する。また、それぞれのＣＨ符号器２は、自己に対応付けられたシンボルの種類に応じた固有の辞書情報を用いて、セレクタ１によって分割された中間データを入力としたカノニカルハフマン符号化処理を行う。これによって、第１の符号列Ｍ’の一部を構成する個々の符号語が順次出力される。第１の符号列Ｍ’は、それぞれのＣＨ符号器２より順次出力された個々の符号語を所定の規則（例えば、原データＭの時系列的な入力に応じた出力順）にしたがって、一列に集合化したものである。
【００３１】
第１の符号化情報Ｅは、複数の第１のＣＨ符号器２で用いられる複数の辞書情報を集合化したものである。例えば、上記ケースで３つのＣＨ符号器２のそれぞれに辞書情報ａ，ｂ，ｃが割り当てられている場合、３つの辞書情報ａ〜ｃを所定の規則（例えば、ａ，ｂ，ｃの降順）にしたがって、一列に集合化したものが第１の符号化情報Ｅとなる。第２のＣＨ符号器３は、第１の付加情報Ｅを入力としたカノニカルハフマン符号化処理を行うことによって、第２の符号列Ｅ'と、第２の付加情報Ｅ''とを出力する。第２の付加情報Ｅ''は、第２の符号列Ｅ'から第１の付加情報Ｅへの復号時に必要な辞書情報である。
【００３２】
図４は、本実施形態にかかるカノニカルハフマン符号化処理のフローチャートである。以下、図１０に示したシンボル列（５種類のシンボルａ〜ｅを含み、40個のシンボルを一列に並べたもの）を一例として参照しつつ、符号化処理の具体的な流れについて説明する。
【００３３】
ステップ１において、第１のＣＨ符号器２の構築が行われる。具体的には、原データＭに含まれるシンボルの種類の数に相当する個数の第１のＣＨ符号器２が設定される。原データＭがシンボルａ〜ｅによって構成されている場合、シンボルａに対応付けられたａ系ＣＨ符号器２と、シンボルｂに対応付けられたｂ系ＣＨ符号器２と、シンボルｃに対応付けられたｃ系ＣＨ符号器２と、シンボルｄに対応付けられたｄ系ＣＨ符号器２と、シンボルｅに対応付けられたｅ系ＣＨ符号器２とが設定される。そして、それぞれのＣＨ符号器２に対して、固有の辞書情報が設定される。周知のように「辞書情報」には、シンボルの遷移状態（遷移元→遷移先）と符号語との対応関係が記述されているが、「固有の辞書情報」とは、一のＣＨ符号器２に対応付けられた一種類のシンボルに特化したもの、換言すれば、一種類のシンボルを遷移元とした遷移状態に関する対応関係のみが記述されたものをいう。それぞれの辞書情報は、互いに別個独立に生成される。
【００３４】
図５は、ａ系ＣＨ符号器２にて用いられる辞書情報ａを示す。この辞書情報ａにおいて、遷移元はシンボルａに限定されており、これを遷移元とした各遷移状態について変換すべき符号語が記述されている。例えば、遷移元および遷移先のシンボルが共にａである遷移状態（ａ→ａ）に対しては、符号語”0”が割り当てられており、遷移元のシンボルがａで遷移先のシンボルがｂである遷移状態（ａ→ｂ）に対しては、符号語”100”が割り当てられている。割り当てられる符号語は、出現回数が多くなるほど、ビット長が短くなるように設定されている。図６は、ｂ系ＣＨ符号器２にて用いられる辞書情報ｂを示す。この辞書情報ｂにおいて、遷移元はシンボルｂに限定されており、これを遷移元とした各遷移状態と、変換すべき符号語との対応関係が記述されている。同様に、図７，８，９は、辞書情報ｃ，ｄ，ｅをそれぞれを示している。
【００３５】
ここで、カノニカルハフマン符号化において、出現頻度情報は各シンボルに割り当てられた符号語長と等価であるが、特に、符号語長０は、符号語の未割り当てを表すことができる。実装上の観点から、アルゴリズムとして認められるすべてのシンボルに符号語長を割り当て、未使用シンボルには０を与える。つまり、任意の辞書情報は、符号化対象のシンボル集合の要素数Ｌに対して、Ｌ個の符号語長情報を必要とする。そして、Ｌ個の遷移状態が存在し得る１次マルコフモデル圧縮では、最大Ｌ2個の符号語長情報を符号データと共に保持する必要がある。そこで、符号語長情報に対して、１次マルコフモデル圧縮の特性を利用した圧縮を行う。本実施形態では、符号語長情報に対するカノニカルハフマン符号化と、遷移状態を考慮した未使用シンボルの判定とを行うことで、符号語長情報の圧縮を行う。
【００３６】
ステップ１におけるセレクタ１と第１のＣＨ符号器２との間における具体的な動作は、概ね以下のようになる。まず、図５から図９に示した辞書情報ａ〜ｅにおいて、出現回数、符号語（およびビット長）がブランクに初期化される。セレクタ１は、原データＭの入力順序にしたがい、遷移元のシンボルに対応付けられたＣＨ符号器２に対して、遷移先のシンボルを順次分配する。それぞれのＣＨ符号器２は、シンボルの分配を受ける毎に、このシンボルに対応する出現回数として１を加算していく。例えば、シンボルの並び順がｂ，ｃの場合、セレクタ１は、遷移元となるシンボルｂに対応するｂ系ＣＨ符号器２を選択するとともに、このｂ系ＣＨ符号器２に対して、遷移先となるシンボルｃを分配する。そして、ｂ系ＣＨ符号器２は、自己の辞書情報ｂの遷移先”ｃ”の出現回数に１を加算する。なお、原データＭの先頭のシンボルａについては、遷移元となるシンボルが存在しないので、便宜上、符号化システムと復号化システムとの間で事前に取り決められたシンボル（本ケースでは”ａ”）が初期状態として設定される。したがって、先頭のシンボルａについては、ａ系ＣＨ符号器２に対してシンボルａが分配され、辞書情報ａの遷移先”ａ”の出現回数に１が加算される。このような分配を原データＭを構成するすべてのシンボルに関して行った後、周知の手法を用いて各遷移状態に固有の符号語を割り当てることによって、５つの辞書情報ａ〜ｅが完成する。以上の説明からわかるように、ステップ１における第１のＣＨ符号器２の構築は、各ＣＨ符号器２に固有の辞書情報ａ〜ｅを構築するプロセスということもできる。
【００３７】
ステップ２において、５つの辞書情報ａ〜ｅを集合化した第１の付加情報Ｅの符号化が行われる。すなわち、第２のＣＨ符号器３は、第１の付加情報Ｅを入力としたカノニカルハフマン符号化処理を行うことによって、第２の符号列Ｅ'と、辞書情報である第２の付加情報Ｅ''とを出力する。単一のＣＨ符号器３によるカノニカルハフマン符号化自体は公知であるから、当業者にとって、これ以上の説明は不要であろう。
【００３８】
続くステップ３において、変数ｐ，ｉが初期値に設定される。ここで、変数ｐは、ある遷移における遷移元シンボルを示す変数、換言すれば、セレクタ１の選択先（複数の第１のＣＨ符号器２のいずれか）を示す変数である。この変数ｐの初期値はａなので、シンボル列の先頭シンボルに依存することなく、最初の選択先としてａ系ＣＨ符号器２が一律に選択される。また、変数ｉは、シンボル列の先頭からの順番によって処理対象となるシンボルを特定する変数であり、図１０に示したように、先頭のシンボルａ（ｉ＝１）から最後尾のシンボルａに向かって、１つのシンボルの処理が終了する毎に１が加算されていく。この変数ｉの初期値は１なので、初期化によって、先頭のシンボルａが処理対象として設定される。
【００３９】
ステップ４〜７の一連の処理は、処理対象となるシンボルｍiの符号化処理を規定している。具体的には、まず、セレクタ１は、ｉ番目のシンボルｍiを読み込んで、変数ｐによって特定される選択先に対してシンボルｍiを出力する（ステップ４）。つぎに、シンボルｍiが入力された選択先となる第１のＣＨ符号器２は、自己に固有の辞書情報を用いて、このシンボルｍiの符号化を行う（ステップ５）。これによって得られた符号語ｍ'iは、第１の符号列Ｍ'の一部を構成する符号語として出力される（ステップ６）。そして、変数ｐの現在値（ｉ＝1の場合を除けばｍi-1）がシンボルｍiに更新される（ステップ７）。
【００４０】
ステップ８において、変数ｉがlast（図１０のシンボル列の場合にはlast＝40）であるか、すなわち、シンボル列の最後の処理が終了したか否かが判断される。このステップ８で否定判定された場合には、ステップ９において、変数ｉに１が加算されてシンボルをシフトさせた上で、ステップ４に戻る。これにより、最後のシンボルの処理が終了するまでステップ４〜９のループが繰り返され、シンボル列を構成する個々のシンボルを処理対象とした符号語への変換処理が順次行われる。そして、最後のシンボル（ｉ＝40）の処理が終了すると、ステップ８の判定結果が否定から肯定へと切り替わって上記ループを抜けるため、一連の処理が終了する。
【００４１】
以上の処理を、図１０に示したケースを例に具体的に説明する。まず、ｉ＝１，ｐ＝ａ（初期状態）において、セレクタ１は、ａ系ＣＨ符号器２を選択するとともに、これに先頭のシンボルｍ1（＝ａ）を出力する。ａ系ＣＨ符号器２は、図５に示した辞書情報ａを参照して、遷移先ｍ1＝ａ（遷移状態ａ→ａ）に対応する”0”を符号語ｍ'1として出力する。つぎに、ｉ＝２，ｐ＝ｍ1において、セレクタ１は、ａ系ＣＨ符号器２を選択するとともに、これにシンボルｍ2（＝ａ）を出力する。ａ系ＣＨ符号器２は、辞書情報ａを参照して、遷移先ｍ2＝ａ（遷移状態ａ→ａ）に対応する”0”を符号語ｍ'2として出力する。ｉ＝３，ｐ＝ｍ2では、ａ系ＣＨ符号器２が選択されるとともに、これにシンボルｍ3（＝ｂ）が出力される。この場合は、遷移先ｍ3＝ｂ（遷移状態ａ→ｂ）に対応する”100”が符号語ｍ'3として出力される。ｉ＝４，ｐ＝ｍ3では、ｂ系ＣＨ符号器２が選択されるとともに、これにシンボルｍ4（＝ｂ）が出力される。この場合は、図６に示した辞書情報ｂが参照されて、遷移先ｍ4＝ｂ（遷移状態ｂ→ｂ）に対応する”0”が符号語ｍ'4として出力される。ｉ＝５，ｐ＝ｍ4では、ｂ系ＣＨ符号器２にシンボルｍ5（＝ｃ）が出力されるとともに、辞書情報ｂが参照されて、遷移先ｍ5＝ｂ（遷移状態ｂ→ｃ）に対応する”101”が符号語ｍ'5として出力される。ｉ＝６，７では、ｃ系ＣＨ符号器２にシンボルｍ6，ｍ7（＝ｃ，ｄ）が出力されるとともに、図７に示した辞書情報ｃが参照されて、符号語ｍ'6，ｍ'7として符号語”0”，”110”が出力される。ｉ＝８，９では、ｄ系ＣＨ符号器２にシンボルｍ8，ｍ9（＝ｄ，ｅ）が出力されるとともに、図８に示した辞書情報ｄが参照されて、符号語ｍ'8，ｍ'9として符号語”0”，”111”が出力される。そして、ｉ＝１０では、ｅ系ＣＨ符号器２にシンボルｍ10（＝ｅ）が出力されるとともに、図９に示した辞書情報ｅが参照されて、符号語ｍ'10として符号語”0”が出力される。以下、ｉ＝40に至るまで上記処理が繰り返され、これによって、第１の符号列Ｍ'＝｛ｍ'1，ｍ'2，ｍ'3，・・・，ｍ'40｝が順次出力される。この符号化システムより、最終的に出力されるデータは、第１の符号列Ｍ'、第２の符号列Ｅ'および第２の付加情報Ｅ''の３つである。
【００４２】
つぎに、本実施形態にかかる復号化システムの具体的な構成について説明する。図１１は、本実施形態にかかるカノニカルハフマン復号化システムのブロック図である。この復号化システムは、第１のカノニカルハフマン復号器４（以下「第１のＣＨ復号器」という）と、セレクタ５と、複数の第２のカノニカルハフマン復号器６（以下「第２のＣＨ復号器６」という）とで構成されており、第２の付加情報Ｅ''、第２の符号列Ｅ'および第１の符号列Ｍを用いて、原データへの復号化を行う。
【００４３】
第１のＣＨ復号器４は、第２の付加情報Ｅ''を辞書情報として用い、第２の符号列Ｅ'を入力としたカノニカルハフマン復号化処理を行うことによって、第１の付加情報Ｅを復号する。これによって、第２のＣＨ復号器６において必要とされる個数分の辞書情報が抽出される。セレクタ５は、第２のＣＨ復号器６によって復号されたシンボルのフィードバックに基づいて、第１の符号列Ｍ'をシンボルの種類に応じて分割する。複数の第２のＣＨ復号器６は、セレクタ５の後段において互いに並列に設けられている。それぞれの第２のＣＨ復号器６は、シンボルの種類に対応付けられている。例えば、同図の最上に位置するＣＨ復号器６がシンボルａに、上から２番目のＣＨ復号器６がシンボルｂに、上から３番目のＣＨ復号器６がシンボルｃにそれぞれ対応付けられているといった如くである。第２のＣＨ復号器６の個数は、辞書情報の個数に相当し、これは結果的に、原データＭに含まれるシンボルの種類の数に相当する。それぞれのＣＨ復号器６は、自己に対応付けられたシンボルの種類に応じた固有の辞書情報を用いて、セレクタ５によって分割された中間データ（符号語）を入力としたカノニカルハフマン復号化処理を行って、個々の符号語からシンボルを順番に復号していく。これによって、第１の符号列Ｍ’を復号化した原データＭが複数のＣＨ復号器６より出力される。なお、セレクタ５による次の選択先を特定すべく、第２のＣＨ復号器６において復号されたシンボルはセレクタ５に随時フィードバックされる。
【００４４】
図１２は、本実施形態にかかるカノニカルハフマン復号化処理のフローチャートである。以下、図１０に示したシンボル列の復号について、図１３を適宜参照しつつ、復号化処理の具体的な流れについて説明する。
【００４５】
まず、ステップ１１において、第１の付加情報Ｅの復号化が行われる。すなわち、第１のＣＨ復号器４は、第２の付加情報Ｅ''を辞書情報として用い、第２の符号列Ｅ'を入力としたカノニカルハフマン復号化処理を行う。これによって、第１の付加情報Ｅが復号されて、符号化時に用いられた５つの辞書情報ａ〜ｅが抽出される。なお、単一のＣＨ復号器４によるカノニカルハフマン復号化自体は公知であるから、当業者にとって、これ以上の説明は不要であろう。
【００４６】
つぎに、ステップ１２において、第２のＣＨ復号器６の構築が行われる。具体的には、抽出された辞書情報ａ〜ｅの個数に相当する５つのＣＨ復号器６が設定される。そして、それぞれのＣＨ復号器６に対して、図５から図９に示した辞書情報ａ〜ｅが固有の辞書情報として個別に設定される。
【００４７】
続くステップ１３において、変数ｐ，ｉが初期値（ｐ＝ａ，ｉ＝１）に設定される。上述したように、変数ｐの初期値は符号化システムとの間で事前に取り決められている。
【００４８】
ステップ１４〜１７の一連の処理は、処理対象となるシンボルｍiの復号化処理を規定している。具体的には、まず、セレクタ５は、ｉ番目の符号語ｍ'iを読み込んで、変数ｐによって特定される選択先に対して符号語ｍ'iを出力する（ステップ１４）。つぎに、符号語ｍ'iが入力された一の第２のＣＨ復号器６は、自己に固有の辞書情報を用いて、この符号語ｍ'iの復号化を行う（ステップ１５）。これによって得られたシンボルｍiは、原データＭの一部を構成するシンボルとして出力される（ステップ１６）。そして、変数ｐの現在値（ｉ＝1の場合を除けばｍi-1）がシンボルｍiに更新される（ステップ１７）。
【００４９】
ステップ１８において、変数ｉがlast（＝40）であるか、すなわち、第１の符号語Ｍ'の最後の処理が終了したか否かが判断される。このステップ１８で否定判定された場合には、ステップ１９において、変数ｉに１を加算して処理対象となる符号語をシフトさせた上で、ステップ１４に戻る。これにより、最後の符号語の処理が終了するまでステップ１４〜１９のループが繰り返され、第１の符号列Ｍ'を構成する個々の符号語に関して、シンボルへの変換処理が行われる。そして、最後の符号語（ｉ＝40）の処理が終了すると、ステップ１８の判定結果が否定から肯定へと切り替わって上記ループを抜けるため、一連の処理が終了する。
【００５０】
以上の処理を、図１３に示したケースを例に具体的に説明する。まず、ｉ＝１，ｐ＝ａにおいて、セレクタ５は、ａ系ＣＨ復号器６を選択するとともに、これに先頭の符号語ｍ'1（”0”）を出力する。この時点において、符号語ｍ'1に対応するシンボルは未だ不明なので、セレクタ５は次の選択先を特定することはできない。ａ系ＣＨ復号器６は、図５に示した辞書情報ａを参照して、符号語ｍ'1からｍ1＝ａ（遷移状態ａ→ａ）を特定する。ａ系ＣＨ復号器６は、原データＭの一部を構成する出力データとしてシンボルａを出力するとともに、次の遷移元がシンボルａであることを通知すべく、ｐ＝ｍ1をセレクタ５にフィードバックする。つぎに、ｉ＝２，ｐ＝ｍ1において、セレクタ５は、ａ系ＣＨ復号器６を選択するとともに、これに符号語ｍ'2（＝”0”）を出力する。ａ系ＣＨ復号器６は、辞書情報ａを参照して、符号語ｍ'2からｍ2＝ａ（遷移状態ａ→ａ）を特定する。これによって、原データＭの一部を構成する出力データとしてシンボルａが出力されるとともに、ｐ＝ｍ2がセレクタ５にフィードバックされる。ｉ＝３，ｐ＝ｍ2では、ａ系ＣＨ復号器６が選択されるとともに、これに符号語ｍ'3（＝”100”）が出力される。この場合は、符号語ｍ'3から遷移先ｍ3＝ｂ（遷移状態ａ→ｂ）が特定される。これによって、原データＭの一部としてシンボルｂが出力されるとともに、ｐ＝ｍ3がセレクタ５にフィードバックされる。ｉ＝４，ｐ＝ｍ3では、ｂ系ＣＨ復号器６が選択されるとともに、これに符号語ｍ'4（＝”0”）が出力される。この場合は、図６に示した辞書情報ｂが参照されて、符号語ｍ4'に対応するシンボルｍ4＝ｂ（遷移状態ｂ→ｂ）が特定される。ｉ＝５，ｐ＝ｍ4では、ｂ系ＣＨ復号器６に符号語ｍ'5（＝”101”）が出力されるとともに、辞書情報ｂが参照されて、シンボルｍ5＝ｃ（遷移状態ｂ→ｃ）が特定される。ｉ＝６，７では、ｃ系ＣＨ復号器６に符号語ｍ6，ｍ7（＝”0”，”110”）が出力されるとともに、図７に示した辞書情報ｃが参照されて、シンボルｍ6，ｍ7（＝ｃ，ｄ）が特定される。ｉ＝８，９では、ｄ系ＣＨ復号器６に符号語ｍ'8，ｍ'9（＝”0”，”111”）が出力されるとともに、図８に示した辞書情報ｄが参照されて、シンボルｍ8，ｍ9（＝ｄ，ｅ）が特定される。そして、ｉ＝１０では、ｅ系ＣＨ復号器６に符号語ｍ'10（＝”0”）が出力されるとともに、図９に示した辞書情報ｅが参照されて、シンボルｅが特定される。以下、ｉ＝４０に至るまで上記の処理が繰り返され、これによって、原データＭ＝｛ｍ1，ｍ2，ｍ3，・・・，ｍ40｝が順次出力される。
【００５１】
本実施形態によれば、第１のＣＨ符号器２を複数並列に設けることによって、符号化効率の向上を図ることができる。以下、単一のＣＨ符号器では情報量が削減されないことを示した後、複数個のＣＨ符号器では情報量が削減可能なことを示す。なお、要素数Ｌのシンボル集合Ｓに対して、ＣＨ符号器は、Ｌ個の符号語長情報を生成する。シンボルｓjに対応する符号語長ｂjは、０≦ｂj≦Ｂmaxであり、このＢmaxは実装におけるＣＨ符号器固有の値として決定される。ただし、カノニカルハフマン符号化の原理として、Ｂmax≦Ｌ−１が常に成立する。
【００５２】
符号語長をシンボルとみなして、符号語長情報を符号化するＣＨ符号器を考える。これは、シンボル集合Ｓ'＝｛0,1,2,・・・,Ｂmax｝からなるメッセージＭ'＝｛ｍ'1,ｍ'2,・・・,ｍ'L：ｍ'j∈Ｓ'｝をカノニカルハフマン符号化することと等価である（以下Ｌ'＝|Ｓ'|とする）。Ｓ'の要素数Ｌ'より、この符号化で生成される符号語長ｂ'jは、式（１）のようになる。
０≦ｂ'j≦Ｂ'max≦Ｌ'−１＝Ｂmax      ・・・（１）
【００５３】
この符号化では、次の２種類の情報が生成される。
（１）Ｌ個の符号長情報のカノニカルハフマン符号列
（２）Ｌ'（Ｂmax＋１）個の符号長情報
【００５４】
（１）の情報量だけで比較する場合、情報量の圧縮は実現できる。しかしながら、（２）に関しては、シンボルの出現分布によっては、ｂj＝Ｌ'−１が成立し得るため、ｂ'jとｂjがとりうる値に範囲を等しくする必要がある。したがって、（２）は符号化対象の情報量と等しくなり、（１）で削減した情報量が（２）を上回ることはない。これにより、単一のＣＨ符号器２の符号語長情報にカノニカルハフマン符号化処理を施しても、情報量の削減には寄与しない。
【００５５】
つぎに、シンボル集合Ｓに対するＫ（＞１）個のＣＨ符号器が生成する符号語長情報を、単一のＣＨ符号器で符号化することを考える。この場合、先のケースと比較して、メッセージＭ'の要素数がＫＬに増えたことだけが異なり、式（１）が成り立つ。
【００５６】
この符号化では、次の２種類の情報が生成される。
（１'）ＫＬ個の符号長情報のカノニカルハフマン符号列
（２'）Ｌ'（Ｂmax＋１）個の符号長情報
【００５７】
（２'）はＳに対する１個のＣＨ符号器が生成する符号長情報の情報量と等しいため、（１'）によって情報量を１／Ｋ以上削減できれば、元の情報量より減少させることが可能になる。その結果、第１のＣＨ符号器２を複数並列に設け、これらが辞書情報として用いる第１の付加情報Ｅを再符号化することによって、符号化効率の向上を図ることができる。
【００５８】
なお、マルコフモデル圧縮のように、複数のＣＨ符号器を扱う場合、入力シンボル列のシンボル出現分布によっては多くの未使用シンボルが発生する。本実施形態では、未使用シンボルに対して符号語長０を割り当てている。符号語長情報の符号化を考える際、未使用シンボルの出現頻度の増加は、すべての未使用シンボルが要する符号量を増大させるだけでなく、０以外の語長に対する符号化効率をも悪化させる。そこで、状態遷移情報をもとに、予め未使用シンボルを排除することを考える。マルコフモデル圧縮の状態Ｄiで使用されるシンボルは、状態Ｄiから遷移可能な状態を示しており、メッセージの最後にはじめて表れるシンボルを除いて、シンボルは必ず状態を持つ。したがって、１次マルコフモデル圧縮においては、全状態の使用状況から、各辞書で使用され得るシンボルの集合を狭めることができる。そして、各辞書は、このシンボル集合に属するシンボルについてだけ符号語長情報を保持することで、未使用シンボルの排除が可能となる。なお、１次マルコフモデル圧縮における辞書Ｄiが使用状態となる条件は、シンボルｉがメッセージ中に出現したかどうかにほぼ等しく、また、各辞書内におけるシンボルの使用状態は、符号器に与えるシンボル列の出現分布に完全に依存する。
【００５９】
また、各状態におけるシンボルと符号語長情報の出力では、上記未使用シンボルの手法では除去できなかったシンボルについてのみ、符号語長をカノニカルハフマン符号化して出力する。状態間の出現傾向の隔たりにより、各々の状態でも多くの未使用シンボルが残る場合が考慮される。符号化効率を上げるためには、各状態における未使用シンボルのカノニカルハフマン符号量を減らすことが好ましい。そこで、状態の中で残った未使用シンボルが余りにも多い場合は、未使用シンボルのカノニカルハフマン符号化を避けることで、全体の付加情報の符号量の削減を図る。具体的には、状態毎に付加情報を次の２種類の形態で選択的に出力できるようにする。
【００６０】
（１）残された全シンボルのカノニカルハフマン符号の列挙
（２）使用シンボルとカノニカルハフマン符号との組の列挙
【００６１】
ここで、（２）を選択する場合、使用シンボルの個数情報も出力する必要があることに注意する。状態遷移を考慮した未使用シンボルの除外を行った結果、残されたシンボル総数をＲ、状態Ｄiで使用されるシンボル総数をＵiとし、（１）のカノニカルハフマン符号における１シンボルあたりの平均ビット数Ｂe1、（２）のそれをＢe2とする。（１）で要するビット数Ｃi1と、（２）で要するビット数Ｃi2は、下式によって表される。
【数２】
2006060274.tif 000004
【００６２】
Ｂe1とＢe2は、各状態の出力形態によって変化するため、アルゴリズム固定のＢmaxを用いて、（１）と（２）の選択基準となる。Ｒに対するＵiのしきい値を決定する。本実施形態で扱う上記定数は、Ｌ＝256，Ｂmax＝31であるので、（１）を選択する条件は５Ｒ＜１３Ｕiとなるが、（２）を選択した場合のシンボルの個数情報と、経験的なＢe1，Ｂe2の値を考慮して、２Ｒ＜１３Ｕiを採用している。
【００６３】
また、上述した実施形態では、カノニカルハフマン符号化を例に説明したが、本発明は、これに限定されるものではなく、半静的エントロピー符号化全般に対して広く適用可能である。半静的エントロピー符号化には、シャノン・ファノ（Shannon-Fano）符号化、ハフマン（Huffman）符号化、算術符号化等が含まれる。この場合、第１および第２のＣＨ符号器２，３に代えて、上記符号化処理を行う第１および第２の半静的エントロピー符号器を用いるとともに、第１および第２のＣＨ復号器４，６に代えて、第１および第２の半静的エントロピー復号器を用いればよい。これらの復号器は、半静的エントロピー符号化に対応する半静的エントロピー復号化処理を行う。
【００６４】
さらに、第１および第２の半静的エントロピー符号器は、同種の処理を行う必要は必ずしもなく、例えば、カノニカルハフマン符号化とシャノン・ファノ符号化との組み合わせといった如く、異種の処理であってもよい。この点は、第１および第２の半静的エントロピー復号器についても同様である。ただし、これらを同種の処理にすれば、符号化や復号化の処理を行うサブルーチンを共通化できるという利点がある。
【図面の簡単な説明】
【００６５】
【図１】カノニカルハフマン符号の一例を示す図
【図２】状態遷移モデルの一例を示す図
【図３】カノニカルハフマン符号化システムのブロック図
【図４】符号化処理のフローチャート
【図５】辞書情報ａの説明図
【図６】辞書情報ｂの説明図
【図７】辞書情報ｃの説明図
【図８】辞書情報ｄの説明図
【図９】辞書情報ｅの説明図
【図１０】カノニカルハフマン符号化処理の説明図
【図１１】カノニカルハフマン復号化システムのブロック図
【図１２】カノニカルハフマン復号化処理のフローチャート
【図１３】カノニカルハフマン復号化処理の説明図
【符号の説明】
【００６６】
１  セレクタ
２  第１のカノニカルハフマン符号器（第１のＣＨ符号器）
３  第２のカノニカルハフマン符号器（第１のＣＨ符号器）
４  第１のカノニカルハフマン復号器（第１のＣＨ復号器）
５  セレクタ
６  第２のカノニカルハフマン復号器（第２のＣＨ復号器）
【図１】
2006060274.tif 000005
【図２】
2006060274.tif 000006
【図３】
2006060274.tif 000007
【図４】
2006060274.tif 000008
【図５】
2006060274.tif 000009
【図６】
2006060274.tif 000010
【図７】
2006060274.tif 000011
【図８】
2006060274.tif 000012
【図９】
2006060274.tif 000013
【図１０】
2006060274.tif 000014
【図１１】
2006060274.tif 000015
【図１２】
2006060274.tif 000016
【図１３】
2006060274.tif 000017