JPH10341165A

JPH10341165A - 少量データへの適応を加速するデータ圧縮方法

Info

Publication number: JPH10341165A
Application number: JP10095782A
Authority: JP
Inventors: Robert A Rust; ロバート・エー・ラスト
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1997-04-09
Filing date: 1998-04-08
Publication date: 1998-12-22
Also published as: KR19980081237A; US5886655A; KR100536980B1

Abstract

(57)【要約】【課題】効率よくデータを圧縮および圧縮解除する方法
および装置を提供する。【解決手段】算術圧縮器が、文脈モデルを使用して、デ
ータの一部を圧縮し圧縮解除する。カウンタは処理され
たデータ量をカウントする。圧縮の後、カウンタのカウ
ントが増分される。カウントが事前定義の量より小さい
場合、第１の文脈モデルが選択され、カウントが事前定
義の量より大きい場合は、第２の文脈モデルが選択され
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、算術的に符号化す
る方法および装置に関し、さらに詳細には、大量のデー
タについては高い圧縮率を維持しながら少量のデータへ
の適応を加速する、文脈モデルに関する。

【０００２】

【従来の技術】デジタル・データ信号の流れを、圧縮さ
れたデジタル符号信号に符号化し、圧縮されたデジタル
・コード信号を元のデータにデコード（復号）するデー
タ圧縮システムは、従来技術として公知である。データ
圧縮とは、所与の形式のデータを、原文よりも少ないス
ペースですむ代替形式に変換しようとする処理を言う。
データ圧縮システムの目標は、所与のデジタル情報の本
文を保持するために必要な記憶量または伝送するために
必要な時間量を節約することである。

【０００３】実際に役立つために、汎用デジタル・デー
タ圧縮システムはある基準を満足しなければならない。
このシステムは、双方向性(reciprocity)を有しなけれ
ばならない。データ圧縮システムが双方向性特性を有す
るためには、情報をいささかでも改変または損失するこ
となく、圧縮データを元の形に再拡張またはデコードす
ることが可能でなければならない。デコードされたデー
タと元のデータが、互いに同一であり、区別不可能でな
ければならない。双方向性特性は、情報理論で使用され
る厳密な無雑音性と同義語である。応用例によっては、
双方向性特性に厳密に固執しない。そのような適用例の
具体例はグラフィック・データを扱うものである。人間
の目は雑音に対しそれほど敏感ではないので、圧縮・圧
縮解除処理中に生じる情報のいくらかの改変または損失
は受け入れられる。

【０００４】このシステムは、データ圧縮および圧縮解
除システムが通信している相手の装置により提供され受
諾されるデータ速度に関して充分な性能を提供しなけれ
ばならない。データの圧縮できる速度は、圧縮システム
への入力データ処理速度により決定され、通常は、１秒
あたり数百万バイト（メガバイト／秒）である。通常、
１メガバイト／秒を超える、今日のディスク、テープお
よび通信システムにおいて達成されるデータ速度を維持
するのに充分な性能が必要である。したがって、データ
圧縮および圧縮解除システムは、システム全体に悪影響
を与えないためには、充分に広い帯域幅を有していなけ
ればならない。データ圧縮および圧縮解除システムの性
能は、通常、圧縮および圧縮解除に必要な計算および統
計データを記憶し圧縮および圧縮解除処理をガイドする
ために利用される、ランダム・アクセス・メモリ（ＲＡ
Ｍ）などのシステム構成要素の速度により制限される。
圧縮装置の性能は、圧縮器中の１入力文字あたり必要な
プロセッサ・サイクル数により特徴づけられる。サイク
ル数が少ないほど、性能は高くなる。

【０００５】データ圧縮および圧縮解除システムの設計
についての他の重要な基準は、圧縮比により特徴づけら
れる圧縮効率である。圧縮比とは、圧縮されない形式の
サイズを圧縮形式のサイズで割った比である。データを
圧縮可能にするには、データが冗長性を有していなけれ
ばならない。圧縮効率は、圧縮手順が入力データの冗長
性をどれだけ有効に使用するかにより決定される。通常
のコンピュータ記憶データにおいて、冗長性は、たとえ
ば、ディジット、バイト、文字など個々の記号の不均一
な利用、および共通語、ブランク・レコード・フィール
ドなどの記号シーケンスの頻繁な繰り返しで生じる。

【０００６】汎用データ圧縮手順もまた、従来の当技術
分野で公知であり、Ｈｏｆｆｍａｎ法、Ｔｕｎｓｔａｌ
ｌ法およびＬｅｍｐｅｌ−Ｚｉｖ法の３つの重要な手順
がある。Ｈｏｆｆｍａｎ法は広く知られ、使用されてい
る。Ｄ．Ａ．Ｈｏｆｆｍａｎの論文「A Method For Con
struction Of Minimum Redundancy Codes（最小冗長コ
ード構成法）」、Proceedings IRE、４０、１０、１０
９８〜１１００頁（１９５２年９月）を参照されたい。
Ｔｕｎｓｔａｌｌアルゴリズムについては、Ｂ．Ｐ．Ｔ
ｕｎｓｔａｌｌの博士論文「Synthesis of Noiseless C
ompression Codes（無雑音圧縮コードのシステム設
計）」、Georgia Institute of Technology（１９６７
年９月）を参照されたい。Ｌｅｍｐｅｌ−Ｚｉｖ法につ
いては、Ｊ．ＺｉｖとＡ．Ｌｅｍｐｅｌの共著論文「A
Universal Algorithm For SequentialData Compression
（逐次データ圧縮の普遍的アルゴリズム）」IEEE Trans
actions on Information Theory、ＩＴ−２３、３、３
３７〜３４３頁（１９７７年５月）のＬｅｍｐｅｌ−Ｚ
ｉｖ手順を参照されたい。

【０００７】最初に開発された汎用データ圧縮手順の１
つは、Ｈｏｆｆｍａｎ法である。簡単に説明すると、Ｈ
ｏｆｆｍａｎ法は記号の全長セグメントを可変長語にマ
ップする。Ｈｏｆｆｍａｎデータ圧縮手順には２つの制
限がある。第１に、Ｈｏｆｆｍａｎ手順は、圧縮される
入力データが記号の固定長セグメントに解析(parse)さ
れるという拘束の下で動作する。Ｈｏｆｆｍａｎ手順
は、この拘束の下で得ることのできる最良の圧縮比を提
供するが、拘束が緩和されると、他の手順を利用するこ
とによりはるかによい圧縮比を得ることが可能である。
第２に、Ｈｏｆｆｍａｎコーディングには、ソース・デ
ータの統計的特性のすべての知識が必要とされる。Ｈｏ
ｆｆｍａｎ手順は、各固定長入力セグメントが生じる確
率が既知であるという仮定の下で動作する。Ｈｏｆｆｍ
ａｎ手順のこの要件は、実際に、データの処理中に必要
な統計値を累積するこの手順の適応版を使用することに
より満足することができる。しかし、この方法は面倒で
あり、かなりの作業用記憶スペースを必要とし、適応中
の性能は最適とは言い難い。

【０００８】Ｔｕｎｓｔａｌｌアルゴリズムは、記号の
可変長セグメントを固定長２進語にマップするもので、
固定長の拘束が入力セグメントではない出力セグメント
に適用される、Ｈｏｆｆｍａｎ手順の補完物である。Ｈ
ｏｆｆｍａｎ手順と同様に、Ｔｕｎｓｔａｌｌ手順に
は、ソース・データの確率の予知が必要とされる。この
場合も、この予知要件は、データの処理中に統計値を累
積する適応版を利用することにより、ある程度満足する
ことができる。

【０００９】Ｌｅｍｐｅｌ−Ｚｉｖ手順は記号の可変長
セグメントを可変長２進語にマップする。入力または出
力セグメントに拘束がないとき、これは漸近的に最適で
ある。この手順では、入力データ・ストリングが適応的
に成長したセグメントに解析され、各セグメントは入力
データからの１つの新しい記号を接尾させ入力ストリン
グの早期の部分のそっくりなコピーから構成される。作
成されるコピーは、可能な最長のものであり、早期に解
析されたどのセグメントとも一致するように強制される
ことはない。出力のセグメントに置き換わるコード語
は、早期にコピーされた部分が開始する場所を示すポイ
ンタ、コピーの長さ、および新しい記号からなる情報を
含む。

【００１０】ＨｏｆｆｍａｎまたはＳｈａｎｎｏｎ−Ｆ
ａｎｏコーディングはデータを圧縮する完全な手段であ
るように思える。しかし、事実はそうではない。前述の
ように、このコーディング方法は、記号の確率が１／２
の整数べきであるときだけ最適であるが、通常はそうは
ならない。

【００１１】算術コーディング技法には、この制限はな
い。すなわち、この技法はメッセージを単一ユニットと
して取り扱う（Ｈｏｆｆｍａｎコーディングでは、あら
ゆる単一の可能なメッセージの列挙が必要となるはずの
技法）のと同じ効果を達成し、したがって、どのソース
についても圧縮効率に結び付いた理論エントロピーを達
成する。

【００１２】算術コーディングにおいては、次から次へ
と判断が符号化されて、番号ライン沿いに、より小さ
く、より少ない包含間隔がうまく定義される。算術コー
ディングに関する追加情報はＧ．Ｇ．Ｌａｎｇｄｏｎ、
Ｊｒ．の論文「An Introduction To Arithmetic Encodi
ng（算術コーディング入門）」、IBM Journal of Resea
rch and Development、Ｖｏｌ．２８、ｎ．２、１３５
〜１４９ページ、１９８４年３月、およびＤ．Ｒ．Ｈｅ
ｌｍａｎ、Ｇ．Ｇ．ＬａｎｇｄｏｎＪｒ、およびＪ．
Ｊ．Ｒｉｓｓａｎｅｎの論文「Arithmetic Compression
Code Control Parameters Approximation（算術圧縮コ
ード制御パラメータ近似法）」、Ｖｏｌ．２３、ｎ．１
１、５１１２〜５１１４ページ、１９８１年４月、およ
びＬａｎｇｄｏｎ、Ｊｒ．他の米国特許第４，９０５，
２９７号「Arithmetic Coding Encoder And Decoder Sy
stem（算術コーディング・エンコーダおよびデコーダ・
システム）」に出ている。

【００１３】前述の論文に言及されているように、算術
コーディングは、各判断が複数の可能な排他的結果また
は「イベント」を有すると規定する。各結果またはイベ
ントは、データ中で記号により表される。たとえば、イ
メージング環境にあっては、各判断は所与のピクセルが
黒であるか否かに対応する。判断の結果は、ピクセルが
黒の場合はＹ（すなわちＹＥＳ）で、ピクセルが黒でな
い場合はＮ（すなわちＮＯ）で表される。したがって、
複数の判断は一連の記号、たとえばＹＮＮＹ・・・で表
される。

【００１４】従来の算術コーディング技法によると、確
率ラインはその上に定義された現間隔を備える。最初の
現間隔は、０ないし１である。現間隔はセグメントに分
割され、セグメントは次の判断の１つの可能な結果に対
応する。各判断の可能な結果が２つだけの場合、現間隔
は２つのセグメントに分割される。各セグメントの長さ
は、それぞれの関連する確率に基づく。それぞれの確率
は、固定したままにすることも、判断データが入力され
るにつれて適応させることもできる。

【００１５】圧縮効果をもたらすのは、より大きな頻度
で生じる記号に対する大きなセグメントの相関関係であ
る。前に引用した論文（「An Introduction To Arithme
ticEncoding」）には、各判断が「ａ」イベント（確率
５０％）、「ｂ」イベント（確率２５％）、「ｃ」イベ
ント（確率１２．５％）、または「ｄ」イベント（確率
１２．５％）という結果をもたらす可能性がある、４記
号算術コーディングの例が述べられている。２進形式で
４つのイベントを表すためには、各判断ごとに２ビット
が必要である。この場合、イベントはそれぞれ、００、
０１、１０、１１で表される。起こる可能性の高い「ａ
ａｂ」などの３２の判断では、直行符号化データは、０
００００１になり、６ビットが必要になる。しか
し、同論文の１３７頁に見られるように、算術コーディ
ング手法では、シーケンス「ａａｂ」を値０．００１で
表すことができる。この情報は６ビットではなく、３ビ
ットで表すことができる。このビット結果は、比較的高
い関連する確率を有する連続イベントとして保存され
る。

【００１６】多くのイベントが行われ、これについて低
い確率および比較的短いライン・セグメントがある場
合、保存性は低下する。前に言及した確率を使用して、
一連のイベント「ｄｄ」は符号化されたデータでは１１
１１で表されるはずであるが、算術コーディングによ
れば、「ｄｄ」イベントは、１１１１１１で表される。
より大きなセグメントは、実際に、それに対応してより
大きい頻度で生じるイベントに対応することを条件とし
て、確率の低い記号に必要な追加ビットよりは、確率の
高い記号が生じるときに達成される保存の方が重要とな
る。

【００１７】算術コーディングは、圧縮ラン全体を通し
てデータに適応し、過去を決して忘れない。これは、そ
の辞書の内容を絶えず失う多くのＬＺベースの方式とは
逆である。ＬＺは辞書を再構築し、したがって、データ
の次のセクションに適応する。ＬＺ方式では、１ＫＢの
データは１００ＫＢのデータと全く同じに圧縮される。
算術コーディングではラン全体を通してその確率を改善
し続けるが、１ＫＢのデータでは算術コーディングがそ
の適応を最適化する機会がなかったので、同じ程度の改
善は得られない。しかし、算術コーディングは１ＫＢの
データをＬＺ方式よりもよく圧縮する。

【００１８】算術コーディングは確率表を使用し、イメ
ージ上に統計値を記憶する。各ビットが圧縮されると
き、ビットをどのように扱うべきかを決定するために、
表にアクセスする。表が大きいほど、最終／最適状態に
移るのに時間がかかる。しかし、表が大きいほど、より
多くの情報が各ビットに利用できるので、大きなイメー
ジほど圧縮比がよくなる。簡単な実験の示すところで
は、大きな表から利益を受ける分岐点は１０ＫＢあたり
であり、この点より後では、大きな表は著しくよい圧縮
比をもたらす。

【００１９】プリンタの動作中に、いくつかの異なるタ
イプのイメージが作られる。あるイメージのサイズは１
００ＫＢないし２００ＫＢであり、他のイメージのサイ
ズは僅か４００Ｂまたはそれより小さいこともある。こ
の小さなイメージに、フォント・キャッシュが大いに役
立っている。ユニークな各文字が最初に作成され、フォ
ント・キャッシュに記憶されてから、印字が開始され
る。頁に応じて、フォント・キャッシュが使用するスペ
ースの量が頁のレンダリングが成功するかどうかによっ
て問題になることがある。

【００２０】同一のプリンタがＬＡＮ環境で使用される
場合、フォントの使用法が一層重要になる。異なる何人
かのユーザが、各自の好みのフォントおよびポイント・
サイズを使用して、印字ジョブを送ることができる。新
しい各ジョブについて、プリンタは、要求された文字が
すでに前のジョブのフォント・キャッシュにセットされ
て存在しているかどうか判定する。存在しない場合は、
この文字をレンダリングするのに時間がかかる。プリン
タの記憶装置がフォント・キャッシュ文字で一緒なの
で、直ちに必要ではない、他の文字用の場所をあけるた
めにフォント・キャッシュから除去しなければならない
場合が生じる。したがって、フォント・キャッシュ文字
が長く、特に複数のジョブにわたって残っているほど、
ユーザが自分のプリントアウトを早く受け取る。フォン
ト・キャッシュ作成まで長時間待つこともまれではな
い。このことは、電源投入後、最初の頁を印字するとき
に、最もよく見られる。

【００２１】

【発明が解決しようとする課題】本発明の課題は、大き
なイメージの圧縮比に小さな影響しか与えずに、フォン
ト・キャッシュ・データ（すなわち、小さなファイル）
に対して改善された圧縮比を提供する方法および装置を
提供することである。

【００２２】

【課題を解決するための手段】本発明を達成するため
に、データを圧縮および圧縮解除する方法が提供され
る。この方法は、処理されるデータ量のカウントに基づ
いて文脈モデルを選択することによって達成される。算
術圧縮器が、文脈モデルを使用して、データの一部を圧
縮し圧縮解除する。カウンタは処理されたデータ量をカ
ウントする。圧縮の後、カウンタのカウントが増分され
る。カウントが事前定義の量より小さい場合、第１の文
脈モデルが選択され、カウントが事前定義の量より大き
い場合は、第２の文脈モデルが選択される。任意の数の
文脈モデルが定義でき、適当な判断点が選択できる。

【００２３】データを圧縮または圧縮解除する装置も提
供され、この装置は算術圧縮器から作成される。この算
術圧縮器は、確率表、第１文脈モデル、および第２文脈
モデルを含む。シフト・レジスタが算術圧縮器に接続さ
れている。このシフト・レジスタはデータを受け取る。
カウンタが算術圧縮器に接続されている。このカウンタ
はデータの一部が事前定義の量より小さい場合は、デー
タの一部分を圧縮するために第１の文脈モデルを使用す
るよう、またデータの一部分が事前定義の量より大きい
場合は、データの一部分を圧縮するために第２の文脈モ
デルを使用するよう算術圧縮器に信号を送る。以下の詳
しい説明を添付の図面と共に考慮すれば、本発明がより
よく理解できるであろう。

【００２４】

【発明の実施の形態】本発明は、本明細書に示す特定の
実施形態に制限されるものではない。図１を参照する
と、本発明の好ましい実施形態のハードウェア実施例の
ブロック図が示されている。算術圧縮器１１１６がビッ
ト１０１を圧縮しようとし、イメージ／シフト・レジス
タ１１０７からのデータが文脈モデル１１１５に渡され
る。文脈モデル１１１５は、イメージ／シフト・レジス
タ１１０７からのデータを確率表１１１３中にマップす
る。圧縮器は確率表１１１３および文脈モデル１１１５
と共にビット１０１を圧縮する。次いで、圧縮データ
は、一般に記憶装置（図示せず）に書き出される。ビッ
ト１０１はイメージ／シフト・レジスタ１１０７中にシ
フトされ、イメージからの新しいビットが１０１中にシ
フトされる。

【００２５】圧縮解除は、一般に圧縮と同じ手段を使っ
て行われる。ただし、圧縮解除中には、算術圧縮器は圧
縮データを読み込み、確率表１１１３および文脈モデル
１１１５を使用してビット１０１を圧縮解除し記憶す
る。前記と同様に、ビット１０１が圧縮解除されると、
イメージ／シフト・レジスタ１１０７中のデータが左に
シフトされる。イメージ／シフト・レジスタ１１０７か
ら出るデータは、一般に記憶装置に記憶される。

【００２６】イメージが圧縮または圧縮解除されると
き、圧縮器１１１４は確率表１１１３を使用して、イメ
ージ上に統計値を記憶する。各ビットが圧縮／圧縮解除
されるとき、このビットをどのように扱うべきかを決定
するために、確率表１１１３アクセスする。確率表１１
１３が大きいほど、最終／最適状態に到達するのに時間
がかかる。しかし、確率表１１１３が大きいほど、多く
の情報がビット１０１に利用できるので、大きなイメー
ジの圧縮比がよくなる。

【００２７】圧縮されているビットの周りのデータのビ
ットを見ることにより、文脈モデル１１１５は確率表１
１１３中へのインデックスを発生する。インデクシング
の重要な態様は、アドレスされたロケーションに、符号
化／復号化されるビットの値に関する有用な情報が含ま
れていることである。さらに具体的に言うと、確率表を
インデックスするために使用されるビットは、符号化／
復号化されるビットの信頼できる予測を行うことができ
るように、重要な情報を提供できなければならない。予
測の信頼性が高いほど、イメージの圧縮性はよくなる。

【００２８】本発明は、圧縮ランの開始時に統計値を迅
速に追跡し、イメージのサイズが増大するにつれて従来
のペースにスローダウンする。これは、各イメージのス
タート時に、確率表のサイズを制限することにより達成
される。より多くのデータが圧縮器を通過するにつれ
て、表のサイズが拡張される。確率のサイズは、イメー
ジの最初の５．１ＫＢの文脈窓を徐々に開くことにより
制御できる。

【００２９】図３を参照すると、より多くのデータが圧
縮されるにつれて、２次元文脈モデル３００は拡張す
る。各ピクセルが確率表のアドレス・ラインに接続され
ている。ピクセル上の数字は、どの特定のアドレス・ビ
ットがそのピクセルによって制御されるかを示す。図３
のａを参照すると、データの最初の１００バイトについ
て、アドレス・ビット９、８、７、６、１および０が強
制的にゼロにされ、それによって図２のａに示すように
確率表のサイズが有効に縮小される。データの次の１Ｋ
バイトについて、図３のｂに示すように、アドレス・ビ
ット９、８および０が強制的にゼロにされ、図２のｂに
示すように確率表のサイズが有効に縮小する。データの
次の４Ｋバイトについて、図３のｃに示すように、アド
レス・ビット０が強制的にゼロにされ、図２のｃに示す
ように確率表のサイズが有効に縮小する。次いで、図３
のｄの文脈モデルおよび図２のｄに示す全体の確率表
が、残りのデータを圧縮するために使用される。

【００３０】図３のａのこの初期文脈モデル中で２つの
態様が重要である。第１に、ビット３０１の周りのピク
セルは、遠く離れたピクセルよりも使用されなければな
らない。したがって、アドレス・ビット５、４、３およ
び２が使用される。第２に、ほとんどすべてのイメージ
において、ゼロは１よりも普通である。そこで、マスク
されたビットを強制的にゼロにすることにより、マスク
を持ち上げた後、この態様が圧縮比のためになる。次の
ブロック（図３のｂ）で、ビット３０１に近いピクセル
がマスクされていない。この処理は、アドレス・ビット
のどれもがマスクされない最終ステージ（図３のｄ）ま
で続く。

【００３１】図１のブロック図にカウンタを追加して修
正することにより、本発明を達成することができる。図
５に示すように、カウンタ１１０２が処理されたビット
の数をカウントする。カウンタ１１０２の出力が文脈モ
デル１１１５に信号を送って、どのビットをマスクする
か指示する。追加ビットが処理されるとき、文脈モデル
１１１５は、前述のようにより少数のビットをマスクす
るよう命令される。

【００３２】図４に好ましい実施形態の流れ図を示す。
新しい各ファイルまたはイメージが処理されるとき、カ
ウンタが最初にリセットされる（４０１）。圧縮される
ビットがデータから取り出される（４０３）。カウント
がＸより小さい場合（４０５）、小文脈モデル４０７が
ビットを圧縮するために使用される（４１９）。同様に
して、カウントがＸよりも大きく、Ｙよりも小さい場合
は（４０９）、中文脈モデル４１１がビットを圧縮する
ために使用される（４１９）。カウントがＹよりも大き
くＺよりも小さい場合は４１３、大文脈モデル４１５が
ビットを圧縮するために使用される（４１９）。Ｚより
大きいバイトが処理されると、全文脈モデル４１７がビ
ットを圧縮するために使用される（４１９）。圧縮され
たデータは記憶される（４２１）。カウントが一つ増分
（インクリメント）され（４２３）、すべてのデータが
処理されたかどうか判定するために検査が行われる。次
のビットを処理する前に、シフト・レジスタ中のデータ
がシフトさせなければならない（４２６）。基本的アイ
ディアを実施しながら、本明細書に記載した操作順序が
変更できることを、当業者なら理解するであろう。ま
た、小、中、大、および全文脈モデルについて前述した
が、任意の数の文脈モデルが定義でき、Ｘ、Ｙ、Ｚ・・
・について適当な値が選択できる。

【００３３】本発明は、大きなイメージの圧縮比に小さ
な影響しか与えずに、フォント・キャッシュ・データ
（すなわち、小さなファイル）に対して改善された圧縮
比を提供する。ラテン文字の特定の場合、フォント・キ
ャッシュ文字の圧縮が４０％改善された。すなわち、従
来の算術コーディング圧縮技法と比較して４０％以上圧
縮された文字が、フォント・キャッシュに含まれる。ア
ドレス・ビットをマスクする複雑さは非常に小さく、設
計に著しい量のロジックが追加されるだけである。

【００３４】本発明の好ましい実施形態について説明し
たが、本発明の精神または添付の請求の範囲から逸脱す
ることなく、本発明に様々な修正を加えることができる
ことは、当業者にとって容易に理解されるであろう。

【００３５】以上、本発明の実施例について詳述した
が、以下、本発明の各実施態様の例を示す。

【００３６】（実施態様１）データを圧縮する方法であ
って、前記処理データの量のカウント（４０１）に基づ
いて文脈モデル（図３）を選択する（４０５〜４１５）
ステップと、前記文脈モデル（図３）を使用して、前記
データの一部を圧縮する（４１９）ステップとを含む方
法。

【００３７】（実施態様２）前記処理データの前記量を
カウントするためにカウンタ（１１０２）を使用するス
テップと、前記圧縮ステップ（４１９）の後に、前記カ
ウンタのカウントを増分するステップ（４２３）とをさ
らに含む実施態様１に記載の方法。

【００３８】（実施態様３）前記選択ステップ（４０５
〜４１５）が、前記カウントが事前定義した量より小さ
い場合に、第１の文脈モデル（４０７）を選択するステ
ップと、前記量が前記事前定義の量より大きい場合に、
第２の文脈モデル（４１５）を選択するステップとを含
むことを特徴とする、実施態様２に記載の方法。

【００３９】（実施態様４）前記データの圧縮部分を記
憶するステップ（４２１）をさらに含む（４１９）実施
態様１に記載の方法。

【００４０】（実施態様５）圧縮データを圧縮解除する
方法であって、処理済みの前記圧縮データの量のカウン
トに基づいて、文脈モデル（図３）を選択するステップ
（４０５〜４１５）と前記文脈モデル（図３）を使用し
て、前記圧縮データの一部を圧縮解除するステップ（４
１９）とを含む方法。

【００４１】（実施態様６）処理済みの前記圧縮データ
の前記量をカウントするためにカウンタ（１１０２）を
使用するステップと、前記圧縮解除ステップの後に、前
記カウンタカウントを増分するステップ（４２３）とを
さらに含む実施態様５に記載の方法。

【００４２】（実施態様７）前記選択ステップが、前記
カウントが事前定義の量より小さい場合（４０５）に、
第１文脈モデルを選択する前記ステップ（４０７）と前
記量が前記所定量より大きい場合に、第２の文脈モデル
を選択するステップ（４１５）とを含むことを特徴とす
る、実施態様６に記載の方法。

【００４３】（実施態様８）データを圧縮するための装
置（図５）であって、確率表（１１１３）、第１文脈モ
デル（１１１５）、および第２文脈モデル（１１１５）
を備える算術圧縮器（１１１６）と、前記算術圧縮器
（１１１６）に接続され、前記データを受け取るように
構成されたシフト・レジスタ（１１０１、１０１）と、
前記算術圧縮器（１１１６）に接続されたカウンタ（１
１０２）とを備え、前記カウンタ（１１０２）が、圧縮
すべきデータの一部分が事前定義の量より少ないとき、
前記部分を圧縮するために前記第１文脈モデル（１１１
５）を使用するよう前記算術圧縮器（１１１６）に信号
で知らせ、あるいは、前記部分が事前定義の量より多い
とき、前記部分を圧縮するために前記第２文脈モデル
（１１１５）を使用するよう前記算術圧縮器（１１１
６）に信号で知らせることを特徴とする装置。

【００４４】（実施態様９）前記第１文脈モデル（１１
１５）が、前記事前定義の量より少ないデータ量につい
て最適化され、前記第２文脈モデル（１１１５）が、前
記事前定義の量より多いデータ量について最適化されて
いることを特徴とする、実施態様８に記載の装置。

【００４５】（実施態様１０）前記第１文脈モデル（１
１１５）が、前記シフト・レジスタ（１１０１、１０
１）の内容を前記確率表（１１１３）の第１の部分にマ
ップし、前記第２文脈モデル（１１１５）が、前記シフ
ト・レジスタ（１１０１、１０１）の内容を前記確率表
（１１１３）の第２部分にマップすることを特徴とす
る、実施態様９に記載の装置。

【００４６】

【発明の効果】以上のように、本発明を用いると、大き
なイメージの圧縮比に小さな影響しか与えずに、小さな
ファイルに対して改善された圧縮比を提供することがで
きる。

【図面の簡単な説明】

【図１】算術圧縮器のブロック図である。

【図２】使用される確率表の成長するサイズをグラフで
表した図である。

【図３】使用される確率表のサイズを動的に調整するた
めに、所与の文脈モデルがどのように使用できるかを示
す図である。

【図４】好ましい実施形態の論理的操作を示す流れ図で
ある。

【図５】本発明による算術圧縮器のブロック図である。

【符号の説明】

１０１：ビット１１０２：カウンタ１１０７：イメージ／シフト・レジスタ１１１３：確率表１１１４：圧縮器１１１５：文脈モデル１１１６：算術圧縮器

Claims

【特許請求の範囲】

【請求項１】データを圧縮する方法であって、前記処理データの量のカウントに基づいて文脈モデルを
選択するステップと、前記文脈モデルを使用して、前記データの一部を圧縮す
るステップとを含む方法。