(57)【特許請求の範囲】
【請求項１】
入力データ記号を符号化する符号化方法であって、
ノードのセットと枝のセットとを含むツリー構造を決定するステップと、
前記ノードのセットに含まれるノードの各々のため、記号のセットにおける数値表現の中の１つのデータに対応する区画データを選択するステップであって、前記区画データは、前記記号のセットにおける既知の確率に対応していて、選択された前記区画データの各々は、前記ノードで記号を区画して生じる確率の不均衡を最大にする区画データであるステップと、
前記ノードのセットに含まれるノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに分岐される２つのノードに区画するステップであって、前記下向きに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画は、前記記号のセットを含む根ノードから始め、前記記号のセットに含まれる単一記号を含む葉ノードで終了するステップと、
前記ツリー構造における前記枝のセットに確率を割り当てるステップであって、この確率は、前記記号のセットに含まれる記号の確率に対応していて、確率の割り当てにおいて、ミス記号よりヒット記号を優先するステップと、
前記記号のセットに含まれる記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化するステップと
からなることを特徴とする符号化方法。
【請求項２】
前記ツリー構造はバイナリツリーであることを特徴とする請求項１に記載された符号化方法。
【請求項３】
前記区画データは単一ビットであることを特徴とする請求項１又は２に記載された符号化方法。
【請求項４】
前記ヒット記号を、前記ミス記号から区別するとき、前記ヒット記号が第一に用いられることを特徴とする請求項１、２及び３のいずれかに記載された符号化方法。
【請求項５】
前記ノードの前記枝の確率は、和が１となる１対の浮動小数点式の数として、表現されることを特徴とする請求項１、２、３及び４のいずれかに記載された符号化方法。
【請求項６】
前記１対の浮動小数点式の数に関連する前記値の間の前記不均衡が、他の未使用のビットを用いる全ての他の有り得る区画に関して最大となることを特徴とする請求項５に記載された符号化方法。
【請求項７】
入力データ記号を符号化する符号化方法であって、
記号のセットを文字列に順序付けるステップと、
前記記号のセットに含まれる各記号を、接頭語を含む文脈に結合するステップと、
前記記号のセットに対応する前記接頭語の予測テーブルを生成するステップと、
前記予測テーブルに対応し、ノードのセットを含み、前記記号のセットのビットごとの符号化に用いられるツリーを生成するステップと、
前記ノードのセットに含まれるノードの各々のため、前記記号のセットにおける二進表現の中の１つのデータに対応する区画データを選択するステップと、
前記ノードのセットに含まれる前記ノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに２つに分岐されるノードに区画するステップであって、前記下向きに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画が、前記記号のセットを含む根ノードから始め、前記記号のセットにおける単一記号を含む葉ノードで終了するステップと、
前記ツリーにある各枝に確率を、前記記号のセットに含まれる記号の確率に対応して、ミス記号よりヒット記号を優先しつつ、割り当てるステップと、
前記記号のセットに含まれる記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化するステップと
ことを特徴とする符号化方法。
【請求項８】
前記順序付けステップは、バロウズ・ホイラー変換と前方移行変換のうちの少なくとも１つの実行を含むことを特徴とする請求項７に記載された符号化方法。
【請求項９】
前記予測テーブルの生成ステップは、０次のテーブル、１次のテーブル、２次のテーブル及び３次のテーブルのうちの少なくとも１つの生成を含むことを特徴とする請求項７又は８に記載された符号化方法。
【請求項１０】
前記予測テーブルは、前記記号の既知の確率と拡張値を含み、前記拡張値は、前記ミス記号のサブセットの集合的な確率に相当することを特徴とする請求項７、８及び９のいずれかに記載された符号化方法。
【請求項１１】
前記区画ビットの選択ステップは、より高い優先順位を有する前記ヒット記号に関し、かつ、前記ミス記号に関して相対的な不均衡の決定を含むことを特徴とする請求項７、８、９及び１０のいずれかに記載された符号化方法。
【請求項１２】
前記ノードのセットは、根ノード、分岐ノードと終端の葉ノードを含むことを特徴とする請求項７、８、９、１０及び１１のいずれかに記載された符号化方法。
【請求項１３】
１つ以上の前記終端の葉ノードは、その確率値が事前知識または事前に得られている統計からの既知の記号、または、ある公式でモデル化されているが未知の記号に関連することを特徴とする請求項６又は１２に記載された符号化方法。
【請求項１４】
データを圧縮するために用いられることを特徴とする請求項１、２、３、４、５、６、７、８、９、１０、１１、１２及び１３のいずれかに記載された符号化方法。
【請求項１５】
コンピュータに、請求項１から５のいずれかに記載されたステップを実行させるためのプログラム。
【請求項１６】
コンピュータに、請求項７または８に記載されたステップを実行させるためのプログラム。
【請求項１７】
入力データ記号を符号化する符号化装置であって、
ノードのセットと枝のセットとを含むツリー構造を決定する決定手段と、
前記ノードのセットに含まれるノードの各々のため、記号のセットにおける数値表現の中の１つのデータに対応する区画データを選択する選択手段であって、前記区画データは、前記記号のセットにおける既知の確率に対応していて、選択された前記区画データの各々は、区画データとして選択可能な区画データの中で、前記ノードで前記シンボルの区画から生じる前記記号のグループの確率の不均衡を最大にする区画データである選択手段と、
前記ノードのセットに含まれる前記ノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに分岐される２つのノードに区画する区画手段であって、前記下向きに２つに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画が前記記号のセットを含む根ノードから始め、前記記号のセットに含まれる単一記号を含む葉ノードで終了する区画手段と、
前記ツリー構造における前記枝のセットに確率を、前記記号のセットに含まれる記号の確率に対応して、ミス記号よりヒット記号を優先しつつ割り当てる割当手段と、
前記記号のセットに含まれる記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化する符号化手段と
からなる符号化装置。
【請求項１８】
前記ツリー構造はバイナリツリーであることを特徴とする請求項１７に記載された符号化装置。
【請求項１９】
前記区画データは単一ビットであることを特徴とする請求項１７又は１８に記載された符号化装置。
【請求項２０】
前記ヒット記号を第一に用いて、前記ヒット記号と前記ミス記号とを区別することを特徴とする請求項１７、１８及び１９のいずれかに記載された符号化装置。
【請求項２１】
前記ノードの前記枝の確率は、合計すると１となる１対の浮動小数点式の数として表現されることを特徴とする請求項１７、１８、１９及び２０のいずれかに記載された符号化装置。
【請求項２２】
他の未使用のビットを用いて起こり得る他の全ての区画に比べ、前記１対の浮動小数点数と結びつけられる前記値の間の不均衡が最大となることを特徴とする請求項２１に記載された符号化装置。
【請求項２３】
１つ以上の前記終端葉は、その確率値が事前知識または事前に得られている統計から既知の記号、または、ある公式でモデル化されているが未知の記号に関連することを特徴とする請求項２２に記載された符号化装置。
【請求項２４】
入力データ記号を符号化する符号化装置であって、
記号のセットを文字列に順序付ける順序付け手段と、
前記記号のセットに含まれる各記号を、接頭語を含む文脈に結びつける関連手段と、
前記記号のセットに対応する前記接頭語のための予測テーブルを生成する予測テーブル生成手段と、
ノードのセットを含み、前記記号のセットをビットごとの符号化に用いられ、前記予測テーブルに対応するツリーを生成するツリー生成手段と、
前記記号のセットの二進表現におけるあるビットの位置に対応する区画ビットを、前記ノードのセットにおいて選択されたノードと結びつけて選択する選択手段と、
前記ノードのセットに含まれるノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに分岐される２つのノードに区画するステップであって、前記下向きに２つに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画が、前記記号のセットを含む根ノードから始め、前記記号のセットに対応する単一記号を含む葉ノードで終了する区画手段と、
前記ツリーにある各分岐ノードに確率を、前記記号のセットに含まれる記号の確率に対応して、ミス記号よりヒット記号をもつ記号を優先しつつ、割り当てる割当手段と、
前記記号のセットに含まれる記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化する符号化手段と
からなる符号化装置。
【請求項２５】
前記順序付け手段は、バロウズ・ホイラー変換と前方移行変換のうちの少なくとも１つを実行することを特徴とする請求項２４に記載された符号化装置。
【請求項２６】
前記予測テーブル生成手段は、０次のテーブル、１次のテーブル、２次のテーブル及び３次のテーブルのうちの少なくとも１つを生成することを特徴とする請求項２４又は２５に記載された符号化装置。
【請求項２７】
前記予測テーブルは、前記記号の既知の確率と、記号のサブセットの集合的な確率であってその個々の確率が前記ミス記号の確率に相当する拡張値とを含むことを特徴とする請求項２４、２５及び２６のいずれかに記載された符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ圧縮に関するものである。
【０００２】
【従来の技術】
データが効率的に格納や伝送されるためには、データの圧縮が非常に望ましい。データサイズが削減されるならば、貴重な周波数帯域幅を温存することができるし、通信チャネルもより効率的になる。同様に、圧縮されていないデータより、圧縮されているデータを格納するほうがメモリーの利用も少なくてすむ。ランレングス符号化(例えば、Ｚｉｖ−ＬｅｍｐｅｌやＰＫ  Ｚｉｐ）、ハフマン圧縮および算術符号化のような多様な異なる技術が、データが失われないように当該データを圧縮する方法として利用されている。これらのデータ損失のない技術は、バロウズ・ホイラー変換のような、圧縮を高める他のアルゴリズムと協働で実施することもできる。
【０００３】
ランレングス符号化の簡単な変形例では、 「ｔｈｅ」という語のように頻繁に繰り返される１つ以上のデータ列を識別する機能を含んでいる。そのような頻繁に繰り返されるデータ列は、その列自身より長さが実質上短い暗号化要素を用いて符号化されている。この技術とその変形例では、英文テキストの圧縮を４：１の比率くらいまでにすることが可能である。ランレングス符号化の変種でより複雑な符号化法も一般的に利用されている。ランレングス符号化の重大な欠点は、頻繁に繰り返される文字列がいつ時でも先験的に知ることができず、そのために所定セットの繰返し記号に対応する所定セットのコードが必要になっているところにある。データにある反復性の文字列がそれらの所定セットに含まれているものと一致しなければ、所望度合の圧縮ができないこともある。
【０００４】
ハフマン符号化やその変形例が、例えばモールス符号から始まって、ＵＮＩＸ(登録商標)のpack/unpackやcompress/uncompress(圧縮/解凍)の命令に至るまでの多様な事例で利用されている。ハフマン符号化やハフマン符号化の変形例では、キャラクタの相対頻度を判定して、特定の頻度に基づいてコードを割り当てている。繰り返し出現する頻度の高いキャラクタは、頻度の低いキャラクタより短いコードを持っているものである。好ましくは一番長いコードを最下層に据え、最上層に至って一番短いコードで終わるバイナリツリー構造が生成されている。最下層から読まれるのが好ましいのではあるが、復号器がビット符号化されたメッセージを受け取り、ツリー構造を下層の方へとたどっていることから、これらのツリー構造は、実際には最上層から読まれる。このように、最も頻繁に出現するキャラクタが最初に遭遇することになる。ハフマン符号化の問題点の１つには、キャラクタに割り当てられた確率が予測できないということにある。一般的に、ハフマンツリー構造は、特定のデータセットにあてはまるかどうか判断のつかない予め定まった頻度を用いて生成されている。
【０００５】
算術符号化も多様な環境で利用される。一般的には、データ要素の確率が恣意的であれば、算術符号化を用いて達成された圧縮率はハフマン符号化でのそれより高い。この算術符号化は、ハフマン符号化と同様に、データ要素の確率に基づいたデータ損失のない技術である。しかしながら、ハフマン符号化とは違って、算術符号化法では、幾つかの異なったコード語どころか単一の記号が生成される。データは、１と０との実数（自然数とは違って）に符号化される。残念ながら、算術符号化には、多数の問題点が残されている。第一に、算術符号化は、一般に他の技術と比較して符号化速度が非常に遅い。特にこの算術符号化が高次予測符号化方法で使われる場合に速度差が顕著な問題になる。第二に、算術符号化では、符号化の処理で用いられる確率分布区画をより正確に反映するので、記号の確率のモデリングが誤っている、或いは、不正確であれば、充分な性能を発揮することができない。
【０００６】
【発明が解決しようとする課題】
適応統計学を用いることにより、記号セットが事前認識できるかどうかに関わる問題点の一部に対処する対策がえられる。一般に、適応符号化アルゴリズムでは、記号一覧テーブルや接頭語一覧テーブルにない記号を符号化することができる。未知の記号が発見されたならば、拡張コード（ＥＳＣ値）がだされてコード化ストリームに入れられる。符号器は、より低次(order)の接頭語で符号化処理を継続し、符号化したビットストリームへ追加データを加える。最も低次の予測テーブル（たいていは、０次テーブル(order 0 table)）には、あらゆる出現し得る記号がそのテーブルから見つかるように、全ての発生し得る記号を含んでいなければならない。ＥＳＣコードは、確率を用いて符号化されていなければならない。しかしながら、新しい記号は予測不可能であるから、ＥＳＣコードの確率は、先行するデータから正確に推測することはできない。ある一定の接頭語に対するＥＳＣ値の確率はしばしば経験的に判断されているので、効率としては最適なものではない。このようにして、適応符号化アルゴリズムにＥＳＣコードを採用するには、２つの問題が浮上してくる。第一に、新しい記号についてはＥＳＣコードでは限られた情報しか得られない。従って、新しい記号に関する限り、低次の接頭語予測テーブルを用いて常に符号化されなければならない。第二に、ＥＳＣコードの確率は正確にモデル化できない。
【０００７】
従って、本発明の目的は、従来技術の問題点を伴わない、データ損失のない圧縮技術を提供することにある。
【０００８】
【課題を解決するための手段】
【０００９】
ある一面での本発明によれば、データ文字列の接頭語が評価され、その接頭語の後続するかもしれない全ての文字の確率が推測される。これら全ての確率から構成されるテーブルが、符号化された先行するデータから生成されるようにしている。好ましい実施の形態では、接頭語は１つ又は２つの要素で構成されている。接頭語のサイズは高度に変化するが、好ましくは接頭語は、記録される値の数を制限するために３次接頭語か又は、それより小さいものとしている。
【００１０】
別の面での本発明においては、バイナリツリーを構築している。ハフマン符号化におけるものとは異なるバイナリツリーが利用され、そのツリーは、予測テーブルに見い出せる記号ができるだけ不均衡となるように生成される。記号のＭ−ビット表現に対して、バイナリツリーはビットベース化された記号の区画に対応する各階層によってＭ階層化されてもよい。
【００１１】
好ましい実施の形態において、バイナリツリーは、全てのあり得る記号のすべてのセットを含む根から始まる。その根は２つの枝に分離し、それぞれがノードに導かれる。各ノードは、特定のビット位置において共有の値を有する記号のグループを含む。このビットにおいて記号が０値を有するなら、その記号は「ゼログループ」と呼ばれるグループに入れられる。このビットにおいて記号が１値を有するなら、その記号は「ワングループ」と呼ばれるグループに入れられる。例えば、記号がｂ２ｂ１ｂ０という３ビット表現で区画され、その中のｂ１ビットが用いられるなら、Ｘ０Ｘのような形式の全ての記号（１０１、０００のような）はゼログループに入れられ、Ｘ１Ｘのような形式の全ての記号（１１０、０１１のような）はワングループに入れられる。ここで、Ｘは０又は１のどちらかである。ノードを区画するための特定のビットを選択するにより、符号化の効率を最適化する並外れたルールを確立することができる。バイナリツリーは葉で終了し、葉のそれぞれは記号となる。
【００１２】
また別の面での本発明では、確率テーブルに表われず、従来の圧縮技術を用いて効率よく圧縮することが特に難しい記号を、効率よく評価及び符号化することが可能である。例えば、ハフマン符号化においては、未知の記号または拡張値の出現頻度が非常に高ければ、これによって短いコード（そして、そのために他の既知の記号に用いられるコードが長くなる）が要求される。好ましい実施の形態においては、記号は、結合されたバイナリツリーにおいて、根から葉までの進路をなぞるように符号化される。単一ステップにおいて記号を符号化する従来アプローチとは異なり、その好ましい実施の形態においては、記号は、バイナリツリーの階層に対応する各ステップを伴う、複数のステップで符号化される。記号は、少しずつ効果的に符号化される。このビット毎の分解により２つの利点が得られる。第一に、来ている記号がどのようなものかについて疑いがないとき、ビット毎の分解がＥＳＣ値の使用をもっと遅い時間に遅らせる。第二に、それがＥＳＣ値を特定の記号へ辿ってもいくことが回避され、より低次の接頭語を伴って再度、記号を符号化する必要を除去する。バイナリツリーが結局いずれかの進路に沿って記号に辿り着くに違いないので、符号化された進路により、記号の発見に導かれるのである。
【００１３】
【発明の実施の形態】
以下の説明では、本発明の好ましい実施の形態を、好ましい処理工程とデータ構造に関して説明する。本発明の実施の形態は、ここで説明する特定の処理工程とデータ構造を利用する、プログラム制御下で稼働する処理装置又はその他の回路を用いて実現できる。ここで説明される処理工程とデータ構造を実施するに当っては、過度の実験や更なる研究を行う必要はない。
【００１４】
（システム要素）
図１は、接頭語予測を用いる符号化システムのブロック図である。
【００１５】
接頭語予測（１００を以て示す）を用いる符号化システムは、演算装置１１０を含む。この演算装置１１０は、中央処理装置１１５、メモリー１２０及び操作者インタフェース１３０と接続したＩ／Ｏ部１２５からなる。メモリー１２０は、磁気ディスク、磁気テープ、光デバイス、光磁気デバイス或いは他の大容量記憶装置のような比較的大量の情報を格納するデバイスが備わっていてもよい。ここで使う「演算装置」という用語は、広義的な意味での装置であり、プログラムにより制御可能なプロセッサを有するか、パーソナルコンピュータ、ラップトップやパーソナルデジタルアシスタントのような、その他の一般的にチューリング機械の範疇にある装置を含むものを意味する。
【００１６】
メモリー１２０には、以下に挙げる４段階手続の命令１４５（図示せず）のセットから構成されたコンピュータプログラム１４０を含んでいる。
（１）データセットの順序付け
（２）バロウズ・ホイラー変換の実行
（３）予測接頭語の符号化の実行
（４）算術符号化の実行
好ましい実施の形態においては、メモリー１２０は、コンピュータプログラム１４０を用いて処理される一セットのデータ１５０を含んでもいる。
【００１７】
図２及び図３は、サンプル接頭語文字列の後に続くデータ要素の確率を示すテーブルのブロック図である。図示の実施の形態では、八個の記号、即ち｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝で、全てのセットを構成しているものとしている。
【００１８】
データ１５０の種類にもよるが、システム１００は、１次テーブル２１０、２次テーブル２３０、又は０次テーブル２５０、或いはそれら全てを生成する。これらのテーブルの一例を同図に示す。これらのテーブルと、そこにある記号はほんの一例であり、これに限定されるものではない。他の好ましい実施の形態においては、３次テーブルのような他のテーブルが生成されてもよい。
【００１９】
１次予測テーブル２１０は、１つ以上の接頭語記号２１５のセット、各接頭語記号２１５の後続する可能性のある１つ以上の記号２２０のセット、及び確率値２２５のセットを含んでいる。接頭語記号２１５は、特定の順序付けされた文字列のごく初めにあるものとして、識別される記号である。記号２２０のセットは、複数の現実の文字とＥＳＣ２２１との両方を含む。確率値２２５は、特定の記号２２０が当該の接頭語２１５の後続する確率を反映する。１次テーブル２１０において、各接頭語記号２１５の長さは１文字分に限定されている。
【００２０】
ＥＳＣは、現行のテーブルでは見つからない記号の集まりを反映する拡張値である。これら「拡張された」記号はミス記号(Miss symbols)と呼称される。それとは対照的に、予測テーブルに見い出せるこれらの記号は、ヒット記号(Hit symbols)と呼称される。一般的に、ＥＳＣ値の確率は、ミス記号の集まりということになるが、実際には、厳密に各特定記号ということにほとんどならない。しかしながら、ＥＳＣ記号は一般的に以下に述べるように、バイナリツリー構造の記号にさらに分解される。そのような場合、全てのミス記号にわたるＥＳＣ確率の傾向性分布を利用してもよい。テーブル２１０においては、ミス記号にわたり一様に分布するＥＳＣ確率を利用している。
【００２１】
２次予測テーブル２３０には、１つ以上の接頭語記号２３５のセットと、接頭語記号２３５の後続し得る１つ以上の記号２４０のセットと、確率値２４５とが含まれている。接頭語記号２３５は特定の文字列のごく初めにあるものとして識別される記号である。記号２４０のセットは、複数のヒット記号とＥＳＣ２４１との両方を含む。ＥＳＣは、現在の２次テーブルにおけるミス記号の集まりを反映する拡張値である。確率値２４５は、特定の記号２４０が当該の接頭語２３５に後続する確率を反映する。この２次テーブル２１０では、各接頭語記号２１５の長さは２文字分に限定されている。
【００２２】
０次予測テーブル２５０は、接頭語記号２５５のヌルセット、接頭語記号２５５に後続し得る１つ以上の記号２６０のセット、及び確率値２６５を含む。一般的に、この０次予測テーブルは符号化に接頭語を利用しない場合に適用する。０次予測テーブルには発生し得る全ての記号が含まれているから、記号２６０のセットは記号の全てのセットを含むが、ＥＳＣ値は含まない。確率値２６５は、特定の記号２４６が当該のヌル接頭語記号２５５に後続する確率を反映している。
【００２３】
図４は、特定の接頭語Ａのもとで記号をビットごとに符号化するプロセスを示すデータツリーを示している。この図に示した記号と値とはほんの一例であり、それに限定されるものではない。この特定のデータツリーは、接頭語２１５「Ａ」を有する文字列の初めにあてはまる、図２に示した１次テーブル２１０で用いた値と記号とに基づいている。さらに、記号は２値のビットｂ２ｂ１ｂ０で表現され、記号セット｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝のバイナリ表記については、次表のように表されるものとする。
【００２４】
【表１】
0003989745.tif 000002
このバイナリ表記はほんの一例であり、決してこれに限定されるものではない。他の二進値で記号が表記される場合、データのツリー構造は異なってくる。
【００２５】
データツリー３００は、トップダウンで読まれるように設計されたバイナリツリーである。根３０５には、記号の全てのセットが含まれている（特定の用途で発生し得る全記号）。分岐ノード（３１０、３２０、３３０、３４０、３５０、又は３６０で示した部分）には記号のサブセットが含まれている。末端のノードは葉と呼ばれ、各葉は単一な記号を含み、全セットの記号とは異なる記号である。ノードの左枝はゼログループと呼ばれ、右のグループがワングループと呼ばれる。ゼログループは０ビット値で表した枝と関連する。ワングループは１ビット値で表した枝と関連する。各枝は、ゼログループまたはワングループである下位ノードにおける記号の確率を表わす浮動小数点式の数と関連している。
【００２６】
バイナリデータツリー３００は、以下の３つのステップで構築される。
ステップ１．各ノード毎に根から開始する区画ビットを選択する。
ステップ２．各ノードにおいて全ての記号（ミス記号を含む）をゼログループとワングループへ区画する。その区画は、ステップ１にて選択された区画ビットでの記号の値に基づいて行う。この区画は、ビット毎に実行され、葉で終了し、そこで単一記号が符号化される。
ステップ３．そのツリーにおける各枝に確率が割り当てられる。
【００２７】
特定の区画ビットは、結果としてのゼロ及びワングループにおけるヒット記号（ＥＳＣ記号を除外する）の確率合計の不均衡を最大にするように選ばれている。区画ビットは、記号のバイナリ表記における二値のビットの１つでなければならない。例えば、同図において、区画ビットは、ｂ２、ｂ１又はｂ０のいずれかでなければならない。あるビットが親ノードで既に利用されているなら、それは下位側の子ノードでは再利用することができない。区画ビットがミス記号だけを含むゼロ又はワングループのいずれかになるなら、このビットの利用は、他の全ての残存するビットが同じ結果に導かれるまで遅らせるべきである。ノードが単一ヒット記号のみを含むのであれば、ヒット記号を含んでいるグループにおける全ての記号（ヒットとミスとの両方を含む）の確率合計を最大にするようにその区画ビットを選ぶ。ノードにヒット記号がなければ、区画ビットは、結果としてのゼロ及びワングループにおけるミス記号の不均衡を最大にするために選ばれる。
【００２８】
ノードの記号をゼロとワンにする区画は、選択された区画ビットにおける記号の値に依存する。区画ビットにおいて０値を有する記号はゼログループに入れられ、１値を有する記号はワングループに入れられる。所定のノードに対する区画ビットを確定するにあたり、ヒット記号が主な役割を果たす。しかしながら、一度、区画ビットが選択されると、そのノードにある全ての記号（ヒット又はミスを含む）は、同じ区画方法を用いて一緒に区画される。
【００２９】
区画処理が完了した後、バイナリツリーの構築の最終ステップとして、確率値をツリーにおける各枝に割り当てる。各ノードの左及び右枝の確率は、合計すると１になる。左及び右の確率は同時に割り当てられる。その割り当ては、２つのステップで行われる。最初に、ヒット記号の確率が、ゼログループとワングループのそれぞれについて合計される。以下の例は、ＺＰとＯＰの２つの合計の場合を示している。ＺＰとＯＰの一方又は両方が０ならば、そのＺＰとＯＰは、ゼログループとワングループにおける全ての記号（ヒットとミス）のそれぞれの確率を合計することにより再計算される。左枝の確率は、計算式ＺＰ／（ＺＰ＋ＯＰ）で求められる。同様に、右枝の確率は、計算式ＯＰ／（ＺＰ＋ＯＰ）で求められる。
【００３０】
バイナリデータツリー３００は、テーブル２１０に表記された値と確率を用いて構築される。根３０５は、記号の全てのセット（この場合は、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝）を含み、その内のＡ、Ｂ、Ｃ及びＤがヒット記号であり、Ｅ、Ｆ、Ｇ及びＨがミス記号である。全セットの記号はｂ２の値に基づいてゼロとワングループとに区画される。これらの記号のｂ２ビットが０であるから、ノード３１０におけるワングループには、Ｄ、Ｆ、Ｇ及びＨが含まれている。ｂ２は、ゼログループにおけるヒット記号（Ａ、Ｂ、Ｃ）の確率合計のＯＰは、０．９となり、ワングループにおけるヒット記号（Ｄ）の確率合計のＺＰは、０．０７となるから、最初の区画に選択される。ｂ１が０．６５（ゼログループのＡ、Ｅ、Ｆ、Ｇ）と０．３２（ワングループのＢ、Ｃ、Ｄ、Ｈ）の区画になり、ｂ０が０．８７（ゼログループのＡ、Ｂ、Ｄ、Ｆ）と０．１０（ワングループのＣ、Ｅ、Ｇ、Ｈ）の区画になるとすれば、これは最も不均衡な結果である。ツリーを下位の方へ辿っていけば、ノード３１０はｂ０で区画される。結果として構築されるツリーが同じ確率値を有しているから、ノード３２０は、ｂ１かｂ０のいずれかで区画されてもよい。ｂ１ビットがミス記号（ＦとＧ）だけを含んでいるゼログループとなる一方、ｂ０ビットがミス記号（ＤとＨ）だけを含んでいるワングループとなる。あいまいな表現をさけるため、より高い位置（例えば、左側において）のビットを選んでいる。
【００３１】
バイナリツリー３００における分岐の確率は、次のように求められる。ノード３０５のゼログループはノード３１０である。このノード３１０はヒット記号としてＡ，Ｂ及びＣを含む。ノード３０５のワングループはノード３２０である。ノード３２０においては唯一のヒット記号がＤである。これらのノードに対する確率値はテーブル２１０に表されている。ノード３１０においてゼログループに属するヒット記号の確率合計のＺＰは、０．６５＋０．１５＋０．１（Ａ，Ｂ及びＣの確率は、それぞれ０．６５、０．１５及び０．１）である。Ｄの確率が０．０７とすれば、ノード３２０においてワングループに属するヒット記号の確率合計のＯＰは、０．０７である。従って、ノード３０５の左枝は、ＺＰ／（ＺＰ＋ＯＰ）＝０．９２７８という確率を有し、右枝は、ＯＰ／（ＺＰ＋ＯＰ）＝０．０７２２という確率を有する。
【００３２】
ノード３６０はノード３２０のワングループである。ノード３６０がｂ０で区画されると、その結果に得られるワングループは単一のミス記号（Ｈ）を含む。従って、確率合計の計算においてミス及びヒット記号の両方が利用される。この場合、ＺＰ＝０．０７とＯＰ＝０．００７５であり、それぞれ、左枝には、０．９０３２の確率が導かれ、右枝には、０．００９６８の確率が導かれる。他のノードについても同様に扱われる。
【００３３】
ある特定の接頭語の下での記号Ｘの符号化は、下記の３ステップで行われる。
１．特定接頭語の予測テーブルに基づくバイナリツリーの構築
２．根から記号Ｘへの進路の識別
３．進路における各確率の符号化
【００３４】
例えば、同図において、記号Ｄは３つの確率である、０．０７２２、０．８３７８及び０．９０３２を用いて符号化されており、Ｅは０．９２７８、０．１１１１及び０．０６９８を用いて符号化されている。各確率値は、標準の算術符号化方法を用いて符号化される。
【００３５】
（利用の方法）
図５は接頭語予測符号化を用いたデータ圧縮方法を示すフローチャートである。
【００３６】
その方法４００はシステム１００により実行される。方法４００を説明するに当り、それが直列的に実行されるものとしているが、方法４００のステップは、非同期的に、或いは、パイプライン法で、分離した要素が協働して、又は並行して実行されることもあり、または、その他の手法で実行されるものであってもよい。
【００３７】
フローポイント４０５において、システム１００は、接頭語予測符号化を用いてデータ圧縮を開始できるようになっている。
【００３８】
ステップ４１０では、命令が与えられて特定のデータ１５０のセットを圧縮する。好ましい実施の形態においては、この命令は、ユーザが手動入力するリクエストでも、自動的に実行されるものでもどちらであってもよい。
【００３９】
ステップ４１５では、特定のデータのセットを順序付けるために、コンピュータプログラム１４０が命令セットを実行する。例えば、２次元のデータのセットが１次元に順序付けされることもあり得る。
【００４０】
ステップ４２０では、コンピュータプログラム１４０はバロウズ・ホイラー変換と前方移行変換(Move-to-front transform)を用いて、データ１５０の順序を変更すべく命令セットを実行する。データの中に含まれる記号の順序を変更すると、分布の確率が変ったり、入力値が位置インデックスにより取り替えられたりする。
【００４１】
ステップ４２５では、順序付けされ、且つ変換されたデータ１５０がメモリに格納される。
【００４２】
ステップ４３０では、コンピュータプログラム１４０が、順序付けされ且つ変換されたデータ１５０にある各記号に対する予測確率テーブルを生成する。そのテーブルは、記号の接頭語により調整される。他の好ましい実施の形態としては、確率テーブルを過去の確率値に基づかせてもよい。
【００４３】
ステップ４３５では、図４に示すように、コンピュータプログラム１４０が、各一組のゼロ及びワングループにおけるヒット記号（ミス記号を除外する）の確率合計の不均衡を最大にするようにバイナリツリーを生成する。各記号は、その記号に対する根に結合された一意の進路により表現される。進路は複数の枝からなり、各枝には暫定的な確率値が割り当てられる。記号の符号化は、根からその記号へ至る進路に割り当てられた確率値へ符号化することにより行われる。
【００４４】
ステップ４４０では、符号化された記号の接頭語のバイナリツリーをなぞり、その木の根からその記号までの進路上の確率を符号化する。好ましい実施の形態においては、確率値は算術符号化法を用いて符号化されるようにしている。このステップは、異なる接頭語及び異なる文字列を用いて、データセットの全体が符号化されるまで、複数回行われてよい。
【００４５】
ここでは好ましい実施の形態が開示されているが、本発明の概念、領域、意図が維持される範囲内において、多様な形態が可能であり、これらの多様な形態は、本明細書を熟読すれば当業者には容易に想到できるものである。
【００４６】
【発明の効果】
以上説明したとおり、本発明は、拡張コード（ＥＳＣ）の不正確なモデリング結果を削減することにより、適用性のある符号化アルゴリズムを用いて、損失が少ない圧縮の高度化を達成することが可能であり、効率的なデータ圧縮の技術を提供することができる。
【図面の簡単な説明】
【図１】  接頭語予測を用いる符号化システムのブロック図である
【図２】  サンプル接頭語文字列におけるデータ要素を示すテーブルのブロック図である。
【図３】  サンプル接頭語文字列におけるデータ要素を示すテーブルのブロック図である。
【図４】  サンプル接頭語文字列における確率分配を示すデータ木を示す図である。
【図５】  接頭語予測符号化を用いたデータ圧縮方法を示すフローチャートである。
【符号の説明】
１００  符号化システム
１１０  演算装置
１１５  中央処理装置
１２０  メモリ
１２５  Ｉ/Ｏ部
１３０  インターフェース
１４０  コンピュータプログラム
１５０  データ
２１０  オーダー１テーブル
２１５、２３５、２５５  接頭語記号
２２０、２４０、２６０  記号
２３０  オーダー２テーブル
２５０  オーダー０テーブル
２２５、２４５、２６５  確率値
【図１】
0003989745.tif 000003
【図２】
0003989745.tif 000004
【図３】
0003989745.tif 000005
【図４】
0003989745.tif 000006
【図５】
0003989745.tif 000007