JPH10341166A - データ量に適応するデータ圧縮方法 - Google Patents
データ量に適応するデータ圧縮方法Info
- Publication number
- JPH10341166A JPH10341166A JP10095783A JP9578398A JPH10341166A JP H10341166 A JPH10341166 A JP H10341166A JP 10095783 A JP10095783 A JP 10095783A JP 9578398 A JP9578398 A JP 9578398A JP H10341166 A JPH10341166 A JP H10341166A
- Authority
- JP
- Japan
- Prior art keywords
- data
- context model
- size
- compressor
- compression
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M7/4006—Conversion to or from arithmetic code
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N1/00—Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof
- H04N1/41—Bandwidth or redundancy reduction
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/005—Statistical coding, e.g. Huffman, run length coding
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Record Information Processing For Printing (AREA)
Abstract
(57)【要約】
【課題】効率よくデータを圧縮および圧縮解除する方法
および装置を提供する。 【解決手段】最初に元のデータのサイズが決定され、文
脈モデルが選択され、これを使用して、元のデータが圧
縮データに圧縮される。任意の数の文脈モデルが定義で
き、適当な選択値が選ばれる。圧縮解除するには、元の
データのサイズに基づいて文脈モデルを選択する。圧縮
データの一部である元のデータのサイズが所定の量より
小さい場合、第１文脈モデルが選択される。サイズが所
定の量より大きい場合は、第２文脈モデルが選択され
る。
および装置を提供する。 【解決手段】最初に元のデータのサイズが決定され、文
脈モデルが選択され、これを使用して、元のデータが圧
縮データに圧縮される。任意の数の文脈モデルが定義で
き、適当な選択値が選ばれる。圧縮解除するには、元の
データのサイズに基づいて文脈モデルを選択する。圧縮
データの一部である元のデータのサイズが所定の量より
小さい場合、第１文脈モデルが選択される。サイズが所
定の量より大きい場合は、第２文脈モデルが選択され
る。
Description
【０００１】
【発明の属する技術分野】本発明は、算術符号化の方法
および装置に関し、さらに詳細には、処理されるデータ
量に適応する算術圧縮器／圧縮解除器に関する。
および装置に関し、さらに詳細には、処理されるデータ
量に適応する算術圧縮器／圧縮解除器に関する。
【０００２】
【従来の技術】デジタル・データ信号の流れを、圧縮さ
れたデジタル符号信号に符号化し、圧縮されたデジタル
・コード信号を元のデータにデコード（復号）するデー
タ圧縮システムは、従来技術として公知である。データ
圧縮とは、所与の形式のデータを、原文よりも少ないス
ペースですむ代替形式に変換しようとする処理を言う。
データ圧縮システムの目標は、所与のデジタル情報の本
文を保持するために必要な記憶量または伝送するために
必要な時間量を節約することである。
れたデジタル符号信号に符号化し、圧縮されたデジタル
・コード信号を元のデータにデコード（復号）するデー
タ圧縮システムは、従来技術として公知である。データ
圧縮とは、所与の形式のデータを、原文よりも少ないス
ペースですむ代替形式に変換しようとする処理を言う。
データ圧縮システムの目標は、所与のデジタル情報の本
文を保持するために必要な記憶量または伝送するために
必要な時間量を節約することである。
【０００３】実際に役立つために、汎用デジタル・デー
タ圧縮システムはある基準を満足しなければならない。
このシステムは、双方向性(reciprocity)を有しなけれ
ばならない。データ圧縮システムが双方向性特性を有す
るためには、情報をいささかでも改変または損失するこ
となく、圧縮データを元の形に再拡張またはデコードす
ることが可能でなければならない。デコードされたデー
タと元のデータが、互いに同一であり、区別不可能でな
ければならない。双方向性特性は、情報理論で使用され
る厳密な無雑音性と同義語である。応用例によっては、
双方向性特性に厳密に固執しない。そのような適用例の
具体例はグラフィック・データを扱うものである。人間
の目は雑音に対しそれほど敏感ではないので、圧縮・圧
縮解除処理中に生じる情報のいくらかの改変または損失
は受け入れられる。
タ圧縮システムはある基準を満足しなければならない。
このシステムは、双方向性(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、ＩＴ−２３、３、３
３７〜３４３頁（１９７７年５月）のＬｅｍｐｅｌ−Ｚ
ｉｖ手順を参照されたい。
分野で公知であり、Ｈｏｆｆｍａｎ法、Ｔｕｎｓｔａｌ
ｌ法およびＬｅｍｐｅｌ−Ｚｉｖ法の３つの重要な手順
がある。Ｈｏｆｆｍａｎ法は広く知られ、使用されてい
る。Ｄ．Ａ．Ｈｏｆｆｍａｎの論文「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)さ
れるという拘束の下で動作する。Ｈｏｆｆｍａｎ手順
は、この拘束の下で得ることのできる最良の圧縮比を提
供するが、拘束が緩和されると、他の手順を利用するこ
とによりはるかによい圧縮比を得ることが可能である。
第２に、Ｈｏｆｆｍａｎコーディングには、ソース・デ
ータの統計的特性のすべての知識が必要とされる。Ｈｏ
ｆｆｍａｎ手順は、各固定長入力セグメントが生じる確
率が既知であるという仮定の下で動作する。Ｈｏｆｆｍ
ａｎ手順のこの要件は、実際に、データの処理中に必要
な統計値を累積するこの手順の適応版を使用することに
より満足することができる。しかし、この方法は面倒で
あり、かなりの作業用記憶スペースを必要とし、適応中
の性能は最適とは言い難い。
つは、Ｈｏｆｆｍａｎ法である。簡単に説明すると、Ｈ
ｏｆｆｍａｎ法は記号の全長セグメントを可変長語にマ
ップする。Ｈｏｆｆｍａｎデータ圧縮手順には２つの制
限がある。第１に、Ｈｏｆｆｍａｎ手順は、圧縮される
入力データが記号の固定長セグメントに解析(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 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」）には、各判断が「ａ」イベント（確率
５０％）、「ｂ」イベント（確率２５％）、「ｃ」イベ
ント（確率１２．５％）、または「ｄ」イベント（確率
１２．５％）という結果をもたらす可能性がある、４記
号算術コーディングの例が述べられている。２進形式で
４つのイベントを表すためには、各判断ごとに２ビット
が必要である。この場合、イベントはそれぞれ、００、
０１、１０、１１で表される。起こる可能性の高い「ａ
ａｂ」などの３２の判断では、直行符号化データは、０
０ ００ ０１になり、６ビットが必要になる。しか
し、同論文の１３７頁に見られるように、算術コーディ
ング手法では、シーケンス「ａａｂ」を値０．００１で
表すことができる。この情報は６ビットではなく、３ビ
ットで表すことができる。このビット結果は、比較的高
い関連する確率を有する連続イベントとして保存され
る。
で生じる記号に対する大きなセグメントの相関関係であ
る。前に引用した論文（「An Introduction To Arithme
ticEncoding」）には、各判断が「ａ」イベント（確率
５０％）、「ｂ」イベント（確率２５％）、「ｃ」イベ
ント（確率１２．５％）、または「ｄ」イベント（確率
１２．５％）という結果をもたらす可能性がある、４記
号算術コーディングの例が述べられている。２進形式で
４つのイベントを表すためには、各判断ごとに２ビット
が必要である。この場合、イベントはそれぞれ、００、
０１、１０、１１で表される。起こる可能性の高い「ａ
ａｂ」などの３２の判断では、直行符号化データは、０
０ ００ ０１になり、６ビットが必要になる。しか
し、同論文の１３７頁に見られるように、算術コーディ
ング手法では、シーケンス「ａａｂ」を値０．００１で
表すことができる。この情報は６ビットではなく、３ビ
ットで表すことができる。このビット結果は、比較的高
い関連する確率を有する連続イベントとして保存され
る。
【００１６】多くのイベントが行われ、これについて低
い確率および比較的短いライン・セグメントがある場
合、保存性は低下する。前に言及した確率を使用して、
一連のイベント「ｄｄ」は符号化されたデータでは１１
１１で表されるはずであるが、算術コーディングによ
れば、「ｄｄ」イベントは、１１１１１１で表される。
より大きなセグメントは、実際に、それに対応してより
大きい頻度で生じるイベントに対応することを条件とし
て、確率の低い記号に必要な追加ビットよりは、確率の
高い記号が生じるときに達成される保存の方が重要とな
る。
い確率および比較的短いライン・セグメントがある場
合、保存性は低下する。前に言及した確率を使用して、
一連のイベント「ｄｄ」は符号化されたデータでは１１
１１で表されるはずであるが、算術コーディングによ
れば、「ｄｄ」イベントは、１１１１１１で表される。
より大きなセグメントは、実際に、それに対応してより
大きい頻度で生じるイベントに対応することを条件とし
て、確率の低い記号に必要な追加ビットよりは、確率の
高い記号が生じるときに達成される保存の方が重要とな
る。
【００１７】算術コーディングは、圧縮ラン全体を通し
てデータに適応し、過去を決して忘れない。これは、そ
の辞書の内容を絶えず失う多くのＬＺベースの方式とは
逆である。ＬＺは辞書を再構築し、したがって、データ
の次のセクションに適応する。ＬＺ方式では、１ＫＢの
データは１００ＫＢのデータと全く同じに圧縮される。
算術コーディングではラン全体を通してその確率を改善
し続けるが、１ＫＢのデータでは算術コーディングがそ
の適応を最適化する機会がなかったので、同じ程度の改
善は得られない。しかし、算術コーディングは１ＫＢの
データをＬＺ方式よりもよく圧縮する。
てデータに適応し、過去を決して忘れない。これは、そ
の辞書の内容を絶えず失う多くのＬＺベースの方式とは
逆である。ＬＺは辞書を再構築し、したがって、データ
の次のセクションに適応する。ＬＺ方式では、１ＫＢの
データは１００ＫＢのデータと全く同じに圧縮される。
算術コーディングではラン全体を通してその確率を改善
し続けるが、１ＫＢのデータでは算術コーディングがそ
の適応を最適化する機会がなかったので、同じ程度の改
善は得られない。しかし、算術コーディングは１ＫＢの
データをＬＺ方式よりもよく圧縮する。
【００１８】算術コーディングは確率表を使用し、イメ
ージ上に統計値を記憶する。各ビットが圧縮されると
き、ビットをどのように扱うべきかを決定するために、
表にアクセスする。表が大きいほど、最終／最適状態に
移るのに時間がかかる。しかし、表が大きいほど、より
多くの情報が各ビットに利用できるので、大きなイメー
ジほど圧縮比がよくなる。簡単な実験の示すところで
は、大きな表から利益を受ける分岐点は１０ＫＢあたり
であり、この点より後では、大きな表は著しくよい圧縮
比をもたらす。
ージ上に統計値を記憶する。各ビットが圧縮されると
き、ビットをどのように扱うべきかを決定するために、
表にアクセスする。表が大きいほど、最終／最適状態に
移るのに時間がかかる。しかし、表が大きいほど、より
多くの情報が各ビットに利用できるので、大きなイメー
ジほど圧縮比がよくなる。簡単な実験の示すところで
は、大きな表から利益を受ける分岐点は１０ＫＢあたり
であり、この点より後では、大きな表は著しくよい圧縮
比をもたらす。
【００１９】プリンタの動作中に、いくつかの異なるタ
イプのイメージが作られる。あるイメージのサイズは１
００ＫＢないし２００ＫＢであり、他のイメージのサイ
ズは僅か４００Ｂまたはそれより小さいこともある。こ
の小さなイメージに、フォント・キャッシュが大いに役
立っている。ユニークな各文字が最初に作成され、フォ
ント・キャッシュに記憶されてから、印字が開始され
る。頁に応じて、フォント・キャッシュが使用するスペ
ースの量が頁のレンダリングが成功するかどうかによっ
て問題になることがある。
イプのイメージが作られる。あるイメージのサイズは１
００ＫＢないし２００ＫＢであり、他のイメージのサイ
ズは僅か４００Ｂまたはそれより小さいこともある。こ
の小さなイメージに、フォント・キャッシュが大いに役
立っている。ユニークな各文字が最初に作成され、フォ
ント・キャッシュに記憶されてから、印字が開始され
る。頁に応じて、フォント・キャッシュが使用するスペ
ースの量が頁のレンダリングが成功するかどうかによっ
て問題になることがある。
【００２０】同一のプリンタがＬＡＮ環境で使用される
場合、フォントの使用法が一層重要になる。異なる何人
かのユーザが、各自の好みのフォントおよびポイント・
サイズを使用して、印字ジョブを送ることができる。新
しい各ジョブについて、プリンタは、要求された文字が
すでに前のジョブのフォント・キャッシュにセットされ
て存在しているかどうか判定する。存在しない場合は、
この文字をレンダリングするのに時間がかかる。プリン
タの記憶装置がフォント・キャッシュ文字で一緒なの
で、直ちに必要ではない、他の文字用の場所をあけるた
めにフォント・キャッシュから除去しなければならない
場合が生じる。したがって、フォント・キャッシュ文字
が長く、特に複数のジョブにわたって残っているほど、
ユーザが自分のプリントアウトを早く受け取る。フォン
ト・キャッシュ作成まで長時間待つこともまれではな
い。このことは、電源投入後、最初の頁を印字するとき
に、最もよく見られる。
場合、フォントの使用法が一層重要になる。異なる何人
かのユーザが、各自の好みのフォントおよびポイント・
サイズを使用して、印字ジョブを送ることができる。新
しい各ジョブについて、プリンタは、要求された文字が
すでに前のジョブのフォント・キャッシュにセットされ
て存在しているかどうか判定する。存在しない場合は、
この文字をレンダリングするのに時間がかかる。プリン
タの記憶装置がフォント・キャッシュ文字で一緒なの
で、直ちに必要ではない、他の文字用の場所をあけるた
めにフォント・キャッシュから除去しなければならない
場合が生じる。したがって、フォント・キャッシュ文字
が長く、特に複数のジョブにわたって残っているほど、
ユーザが自分のプリントアウトを早く受け取る。フォン
ト・キャッシュ作成まで長時間待つこともまれではな
い。このことは、電源投入後、最初の頁を印字するとき
に、最もよく見られる。
【００２１】
【発明が解決しようとする課題】本発明の目的は、大き
なイメージの圧縮比に影響を与えずに、フォント・キャ
ッシュ・データ（すなわち、小さなファイル）の改善さ
れた圧縮比を提供する方法及び装置を提供することであ
る。
なイメージの圧縮比に影響を与えずに、フォント・キャ
ッシュ・データ（すなわち、小さなファイル）の改善さ
れた圧縮比を提供する方法及び装置を提供することであ
る。
【００２２】
【課題を解決するための手段】本発明は、元のデータを
圧縮データに圧縮する方法により達成される。最初に元
のデータのサイズが決定される。このサイズに基づい
て、文脈モデル(contextmodel)が選択される。この文脈
モデルを使用して、元のデータが圧縮データに圧縮され
る。任意の数の文脈モデルが定義でき、適当な選択値が
選ばれる。
圧縮データに圧縮する方法により達成される。最初に元
のデータのサイズが決定される。このサイズに基づい
て、文脈モデル(contextmodel)が選択される。この文脈
モデルを使用して、元のデータが圧縮データに圧縮され
る。任意の数の文脈モデルが定義でき、適当な選択値が
選ばれる。
【００２３】圧縮解除するには、元のデータのサイズに
基づいて文脈モデルを選択することが必要である。正し
い文脈モデルを検出する２つの方法が記述されている。
元のデータのサイズが所定の量より小さい場合、第１文
脈モデルが選択される。この場合、元のデータのサイズ
は圧縮データの一部である。サイズが所定の量より大き
い場合は、第２文脈モデルが選択される。別法として、
圧縮データからインジケータが取り出される。インジケ
ータは、元のデータを圧縮するためにどの文脈モデルが
使用されたか識別する。
基づいて文脈モデルを選択することが必要である。正し
い文脈モデルを検出する２つの方法が記述されている。
元のデータのサイズが所定の量より小さい場合、第１文
脈モデルが選択される。この場合、元のデータのサイズ
は圧縮データの一部である。サイズが所定の量より大き
い場合は、第２文脈モデルが選択される。別法として、
圧縮データからインジケータが取り出される。インジケ
ータは、元のデータを圧縮するためにどの文脈モデルが
使用されたか識別する。
【００２４】データを圧縮または圧縮解除する装置も提
供される。この装置は算術圧縮器から作成され、この算
術圧縮器には確率表、第１文脈モデルおよび第２文脈モ
デルを含んでいる。シフト・レジスタが算術圧縮器に接
続されている。シフト・レジスタはデータを受け取る。
データのサイズが所定の量より小さいとき、第１文脈モ
デルを使用してデータを圧縮するようコントローラが算
術圧縮器に信号で知らせ、そうでないときは、算術圧縮
器が第２文脈モデルを使用してデータを圧縮する。添付
の図面と共に以下の詳しい説明を考慮すれば、本発明を
一層よく理解できるであろう。
供される。この装置は算術圧縮器から作成され、この算
術圧縮器には確率表、第１文脈モデルおよび第２文脈モ
デルを含んでいる。シフト・レジスタが算術圧縮器に接
続されている。シフト・レジスタはデータを受け取る。
データのサイズが所定の量より小さいとき、第１文脈モ
デルを使用してデータを圧縮するようコントローラが算
術圧縮器に信号で知らせ、そうでないときは、算術圧縮
器が第２文脈モデルを使用してデータを圧縮する。添付
の図面と共に以下の詳しい説明を考慮すれば、本発明を
一層よく理解できるであろう。
【００２５】
【発明の実施の形態】本発明は、本明細書に示す特定の
実施形態に制限されるものではない。図１を参照する
と、本発明の好ましい実施形態のハードウェア実施例の
ブロック図が示されている。算術圧縮器１１１６がビッ
ト１０１を圧縮しようとし、イメージ／シフト・レジス
タ１１０７からのデータが文脈モデル１１１５に渡され
る。文脈モデル１１１５は、イメージ／シフト・レジス
タ１１０７からのデータを確率表１１１３中にマップす
る。圧縮器１１１４は確率表１１１３および文脈モデル
１１１５と共にビット１０１を圧縮する。次いで、圧縮
データは、一般に記憶装置（図示せず）に書き出され
る。ビット１０１はイメージ／シフト・レジスタ１１０
７中にシフトされ、イメージからの新しいビットが１０
１にシフトされる。
実施形態に制限されるものではない。図１を参照する
と、本発明の好ましい実施形態のハードウェア実施例の
ブロック図が示されている。算術圧縮器１１１６がビッ
ト１０１を圧縮しようとし、イメージ／シフト・レジス
タ１１０７からのデータが文脈モデル１１１５に渡され
る。文脈モデル１１１５は、イメージ／シフト・レジス
タ１１０７からのデータを確率表１１１３中にマップす
る。圧縮器１１１４は確率表１１１３および文脈モデル
１１１５と共にビット１０１を圧縮する。次いで、圧縮
データは、一般に記憶装置（図示せず）に書き出され
る。ビット１０１はイメージ／シフト・レジスタ１１０
７中にシフトされ、イメージからの新しいビットが１０
１にシフトされる。
【００２６】圧縮解除は、一般に圧縮と同じ方式で行わ
れる。ただし、圧縮解除中には、算術圧縮器は圧縮デー
タを読み込み、確率表１１１３および文脈モデル１１１
５を使用して、ビット１０１を圧縮解除し記憶する。前
記と同様に、ビット１０１が圧縮解除されると、イメー
ジ／シフト・レジスタ１１０７中のデータが左にシフト
される。イメージ／シフト・レジスタ１１０７から出た
データは、一般に記憶装置に記憶される。
れる。ただし、圧縮解除中には、算術圧縮器は圧縮デー
タを読み込み、確率表１１１３および文脈モデル１１１
５を使用して、ビット１０１を圧縮解除し記憶する。前
記と同様に、ビット１０１が圧縮解除されると、イメー
ジ／シフト・レジスタ１１０７中のデータが左にシフト
される。イメージ／シフト・レジスタ１１０７から出た
データは、一般に記憶装置に記憶される。
【００２７】圧縮器１１１４は確率表１１１３を使用し
て、イメージが圧縮または圧縮解除されるときに、その
イメージ上に統計値を記憶する。各ビットが圧縮／圧縮
解除されるとき、このビットをどのように扱うべきかを
決定するために、確率表１１１３にアクセスする。確率
表１１１３が大きいほど、最終／最適状態に到達するの
に時間がかかる。しかし、確率表１１１３が大きいほ
ど、各ビット１０１についてより多くの情報が利用でき
るので、より大きなイメージに対しての圧縮比がより良
くなる。
て、イメージが圧縮または圧縮解除されるときに、その
イメージ上に統計値を記憶する。各ビットが圧縮／圧縮
解除されるとき、このビットをどのように扱うべきかを
決定するために、確率表１１１３にアクセスする。確率
表１１１３が大きいほど、最終／最適状態に到達するの
に時間がかかる。しかし、確率表１１１３が大きいほ
ど、各ビット１０１についてより多くの情報が利用でき
るので、より大きなイメージに対しての圧縮比がより良
くなる。
【００２８】圧縮されているビットの周りのデータのビ
ットを見ることにより、文脈モデル１１１５は確率表１
１１３内へのインデックスを発生する。このインデック
シングの重要な態様は、アドレスされたロケーションに
は、符号化／復号化されるビットの値に関する有用な情
報が含まれていることである。さらに具体的に言うと、
確率表をインデックス化するために使用されるビット
は、重要な情報を提供できなければならず、その結果、
符号化／復号化されるビットの信頼できる予測を行うこ
とができる。予測の信頼性が高ければ高いほど、イメー
ジの圧縮性はよくなる。
ットを見ることにより、文脈モデル１１１５は確率表１
１１３内へのインデックスを発生する。このインデック
シングの重要な態様は、アドレスされたロケーションに
は、符号化／復号化されるビットの値に関する有用な情
報が含まれていることである。さらに具体的に言うと、
確率表をインデックス化するために使用されるビット
は、重要な情報を提供できなければならず、その結果、
符号化／復号化されるビットの信頼できる予測を行うこ
とができる。予測の信頼性が高ければ高いほど、イメー
ジの圧縮性はよくなる。
【００２９】本発明の好ましい実施形態では、処理され
るデータ・セットのサイズに対して最適化された文脈モ
デルが選択される。図３を参照すると、より大きなデー
タにつれて、２次元文脈モデル３００が拡張する。各ピ
クセルは確率表のアドレス・ラインに接続される。ピク
セル上の数字は、どの特定のアドレス・ビットがそのピ
クセルによって制御されるかを示す。図３のａを参照す
ると、１００バイトより少ないデータ・セットでは、ア
ドレス・ビット９、８、７、６、１および０が強制的に
ゼロにされ、図２のａに示すように確率表のサイズが効
果的に縮小される。１００バイトから１Ｋバイトの間の
データ・セットでは、図３のｂに示すようにアドレス・
ビット９、８および０が強制的にゼロにされ、図２のｂ
に示すように確率表のサイズが効果的に縮小される。１
Ｋバイトから４Ｋバイトの間のデータ・セットでは、図
３のｃに示すようにアドレス・ビット０が強制的にゼロ
にされ、図２のｃに示すように確率表のサイズが効果的
に縮小される。次に、図３のｄの文脈モデル、および図
２のｄに示す全体の確率表が、より大きなデータ・セッ
トを圧縮するために使用される。
るデータ・セットのサイズに対して最適化された文脈モ
デルが選択される。図３を参照すると、より大きなデー
タにつれて、２次元文脈モデル３００が拡張する。各ピ
クセルは確率表のアドレス・ラインに接続される。ピク
セル上の数字は、どの特定のアドレス・ビットがそのピ
クセルによって制御されるかを示す。図３のａを参照す
ると、１００バイトより少ないデータ・セットでは、ア
ドレス・ビット９、８、７、６、１および０が強制的に
ゼロにされ、図２のａに示すように確率表のサイズが効
果的に縮小される。１００バイトから１Ｋバイトの間の
データ・セットでは、図３のｂに示すようにアドレス・
ビット９、８および０が強制的にゼロにされ、図２のｂ
に示すように確率表のサイズが効果的に縮小される。１
Ｋバイトから４Ｋバイトの間のデータ・セットでは、図
３のｃに示すようにアドレス・ビット０が強制的にゼロ
にされ、図２のｃに示すように確率表のサイズが効果的
に縮小される。次に、図３のｄの文脈モデル、および図
２のｄに示す全体の確率表が、より大きなデータ・セッ
トを圧縮するために使用される。
【００３０】図１のブロック図にコントローラ１１０２
を追加して修正することにより、本発明を達成すること
ができる。図５に示すように、コントローラ１１０２の
タスクの１つは、処理されるビットの数を決定すること
である。コントローラ１１０２の出力が、どのビットを
マスクするかを、文脈モデル１１１５に信号で知らせ
る。コントローラ１１０２は、いくつかの他のタスク
（図示せず）を有する。
を追加して修正することにより、本発明を達成すること
ができる。図５に示すように、コントローラ１１０２の
タスクの１つは、処理されるビットの数を決定すること
である。コントローラ１１０２の出力が、どのビットを
マスクするかを、文脈モデル１１１５に信号で知らせ
る。コントローラ１１０２は、いくつかの他のタスク
（図示せず）を有する。
【００３１】図４に好ましい実施形態の流れ図を示す。
データを圧縮する前に、データのサイズが決定される
（５０３）。サイズがＸより小さい場合（５０３）、小
さい文脈モデル５０７が選択される。サイズがＸより大
きくＹより小さい場合（５０７）、中の文脈モデル５０
９が選択される。サイズがＹより大きくＺより小さい場
合（５１１）、大文脈モデル５１３が選択される。サイ
ズがＺより大きい場合、全文脈モデル５１５が選択され
る。文脈モデルが選択されると、選択された文脈モデル
を使用して、全体のデータが圧縮される（５１７）。基
礎となるアイデアを実施しながら本明細書に記述された
操作順序を変更できることを、当業者なら理解するであ
ろう。また、小、中、大、および全文脈モデルについて
前述したが、任意数の文脈モデルを定義することもで
き、Ｘ、Ｙ、Ｚ…について適切な値が選ばれる。
データを圧縮する前に、データのサイズが決定される
（５０３）。サイズがＸより小さい場合（５０３）、小
さい文脈モデル５０７が選択される。サイズがＸより大
きくＹより小さい場合（５０７）、中の文脈モデル５０
９が選択される。サイズがＹより大きくＺより小さい場
合（５１１）、大文脈モデル５１３が選択される。サイ
ズがＺより大きい場合、全文脈モデル５１５が選択され
る。文脈モデルが選択されると、選択された文脈モデル
を使用して、全体のデータが圧縮される（５１７）。基
礎となるアイデアを実施しながら本明細書に記述された
操作順序を変更できることを、当業者なら理解するであ
ろう。また、小、中、大、および全文脈モデルについて
前述したが、任意数の文脈モデルを定義することもで
き、Ｘ、Ｙ、Ｚ…について適切な値が選ばれる。
【００３２】データを圧縮解除するときも同様に、図４
の流れ図を使用することができる。しかし、圧縮されな
いデータのサイズは、圧縮されたデータのサイズと直接
関係はない。したがって、圧縮解除装置にファイルの元
のサイズを、またはデータを圧縮するためにどの文脈モ
デルが使用されたかを知らせる何らかの手段が、圧縮デ
ータに含まれていなければならない。好ましい実施形態
において、元のイメージの高さおよび幅が圧縮データの
一部として記憶される。他の実施形態では、圧縮されな
いファイル・サイズ、または、どの文脈モデルを使用す
るかを示すフラグを記憶することができる。適当な文脈
モデルが選択されると、データが圧縮解除される。
の流れ図を使用することができる。しかし、圧縮されな
いデータのサイズは、圧縮されたデータのサイズと直接
関係はない。したがって、圧縮解除装置にファイルの元
のサイズを、またはデータを圧縮するためにどの文脈モ
デルが使用されたかを知らせる何らかの手段が、圧縮デ
ータに含まれていなければならない。好ましい実施形態
において、元のイメージの高さおよび幅が圧縮データの
一部として記憶される。他の実施形態では、圧縮されな
いファイル・サイズ、または、どの文脈モデルを使用す
るかを示すフラグを記憶することができる。適当な文脈
モデルが選択されると、データが圧縮解除される。
【００３３】本発明は、大きなイメージの圧縮比に影響
を与えずに、フォント・キャッシュ・データ（すなわ
ち、小さなファイル）の改善された圧縮比を提供する。
ラテン文字に関する特定の場合、フォント・キャッシュ
文字の圧縮が４０％改善された。すなわち、従来の算術
コーディング圧縮技法に比べ４０％多い圧縮文字がフォ
ント・キャッシュに入ることになる。アドレス・ビット
をマスクする複雑さは非常に小さく、目立った量のロジ
ック量が設計に追加されるだけである。
を与えずに、フォント・キャッシュ・データ（すなわ
ち、小さなファイル）の改善された圧縮比を提供する。
ラテン文字に関する特定の場合、フォント・キャッシュ
文字の圧縮が４０％改善された。すなわち、従来の算術
コーディング圧縮技法に比べ４０％多い圧縮文字がフォ
ント・キャッシュに入ることになる。アドレス・ビット
をマスクする複雑さは非常に小さく、目立った量のロジ
ック量が設計に追加されるだけである。
【００３４】本発明の好ましい実施形態について説明し
たが、本発明の精神または添付の請求の範囲から逸脱す
ることなく、本発明に様々な修正を加えることができる
ことは、当業者には明らかであろう。
たが、本発明の精神または添付の請求の範囲から逸脱す
ることなく、本発明に様々な修正を加えることができる
ことは、当業者には明らかであろう。
【００３５】以上、本発明の実施例について詳述した
が、以下、本発明の各実施態様の例を示す。
が、以下、本発明の各実施態様の例を示す。
【００３６】（実施態様１）元のデータを圧縮データに
圧縮する方法であって、前記元のデータのサイズを判定
するステップ（５０１）と前記サイズに基づいて文脈モ
デル（図３）を選択するステップ（５０３〜５１５）と
前記文脈モデル（図３）を使用して、前記元のデータを
前記圧縮データに圧縮するステップ（５１７）とを含む
方法。
圧縮する方法であって、前記元のデータのサイズを判定
するステップ（５０１）と前記サイズに基づいて文脈モ
デル（図３）を選択するステップ（５０３〜５１５）と
前記文脈モデル（図３）を使用して、前記元のデータを
前記圧縮データに圧縮するステップ（５１７）とを含む
方法。
【００３７】（実施態様２）前記選択ステップ（５０３
〜５１５）が、前記サイズが所定の量よりも小さい場合
（５０３）に、第１の文脈モデル（５０５）を選択する
ステップと、前記サイズが所定の量よりも大きい場合
（５１１）に、第２の文脈モデル（５１５）を選択する
ステップとを含むことを特徴とする、実施態様１に記載
の方法。
〜５１５）が、前記サイズが所定の量よりも小さい場合
（５０３）に、第１の文脈モデル（５０５）を選択する
ステップと、前記サイズが所定の量よりも大きい場合
（５１１）に、第２の文脈モデル（５１５）を選択する
ステップとを含むことを特徴とする、実施態様１に記載
の方法。
【００３８】（実施態様３）圧縮データを記憶するステ
ップ（５１７）をさらに含む、実施態様１に記載の方
法。
ップ（５１７）をさらに含む、実施態様１に記載の方
法。
【００３９】（実施態様４）圧縮データを元のデータに
圧縮解除する方法であって、前記元のデータのサイズに
基づいて文脈モデル（図３）を選択するステップ（５０
３〜５１５）と前記文脈モデル（図３）を使用して、前
記圧縮データを前記元のデータに圧縮解除するステップ
（５１７）とを含む方法。
圧縮解除する方法であって、前記元のデータのサイズに
基づいて文脈モデル（図３）を選択するステップ（５０
３〜５１５）と前記文脈モデル（図３）を使用して、前
記圧縮データを前記元のデータに圧縮解除するステップ
（５１７）とを含む方法。
【００４０】（実施態様５）前記選択ステップ（５０３
〜５１５）が、前記サイズが所定の量より小さい場合
（５０３）に、第１文脈モデル（５０５）を選択するス
テップと、前記サイズが所定の量より大きい場合（５１
１）に、第２の文脈モデル（５１５）を選択するステッ
プとを含むことを特徴とする、実施態様４に記載の方
法。
〜５１５）が、前記サイズが所定の量より小さい場合
（５０３）に、第１文脈モデル（５０５）を選択するス
テップと、前記サイズが所定の量より大きい場合（５１
１）に、第２の文脈モデル（５１５）を選択するステッ
プとを含むことを特徴とする、実施態様４に記載の方
法。
【００４１】（実施態様６）前記文脈モデル（図３）が
前記圧縮データを圧縮するために使用されたことを、前
記圧縮データが示す場合に、第１文脈モデル（図３）を
選択するステップ（５０３〜５１５）と、前記第２文脈
モデル（図３）が前記圧縮データを圧縮するために使用
されたことを示す場合に、第２文脈モデル（図３）を選
択するステップとを含むことを特徴とする、実施態様４
に記載の方法。
前記圧縮データを圧縮するために使用されたことを、前
記圧縮データが示す場合に、第１文脈モデル（図３）を
選択するステップ（５０３〜５１５）と、前記第２文脈
モデル（図３）が前記圧縮データを圧縮するために使用
されたことを示す場合に、第２文脈モデル（図３）を選
択するステップとを含むことを特徴とする、実施態様４
に記載の方法。
【００４２】（実施態様７）前記選択ステップが、前記
圧縮データからインジケータを検索するステップと、ど
の文脈モデルを選択するか識別するために前記インジケ
ータを使用するステップとをさらに含むことを特徴とす
る、実施態様４に記載の方法。
圧縮データからインジケータを検索するステップと、ど
の文脈モデルを選択するか識別するために前記インジケ
ータを使用するステップとをさらに含むことを特徴とす
る、実施態様４に記載の方法。
【００４３】（実施態様８）データを圧縮する装置（図
５）であって、確率表（１１１３）、第１文脈モデル
（１１１５）および第２文脈モデル（１１１５）を備え
る、算術圧縮器（１１１６）と、前記算術圧縮器（１１
１６）に接続され、前記データを受け取るように構成さ
れたシフト・レジスタ（１１０１、１０１）と、前記算
術圧縮器（１１１６）に接続され、前記データのサイズ
が所定の量より小さい場合に、前記第１文脈モデル（１
１１５）を使用して前記データを圧縮するよう前記算術
圧縮器（１１１６）に信号で知らせ、あるいは、前記デ
ータのサイズが所定の量より大きい場合は、前記第２文
脈モデル（１１１５）を使用して前記データを圧縮する
よう前記算術圧縮器（１１１６）に信号で知らせる、前
記データのサイズを決定する手段（１１０２）とを含む
装置。
５）であって、確率表（１１１３）、第１文脈モデル
（１１１５）および第２文脈モデル（１１１５）を備え
る、算術圧縮器（１１１６）と、前記算術圧縮器（１１
１６）に接続され、前記データを受け取るように構成さ
れたシフト・レジスタ（１１０１、１０１）と、前記算
術圧縮器（１１１６）に接続され、前記データのサイズ
が所定の量より小さい場合に、前記第１文脈モデル（１
１１５）を使用して前記データを圧縮するよう前記算術
圧縮器（１１１６）に信号で知らせ、あるいは、前記デ
ータのサイズが所定の量より大きい場合は、前記第２文
脈モデル（１１１５）を使用して前記データを圧縮する
よう前記算術圧縮器（１１１６）に信号で知らせる、前
記データのサイズを決定する手段（１１０２）とを含む
装置。
【００４４】（実施態様９）前記第１文脈モデル（１１
１５）が、前記所定量より小さいデータ量に対して最適
化され、前記第２文脈モデル（１１１５）が、前記所定
量より大きいデータ量に対して最適化されることを特徴
とする、実施態様８に記載の装置。
１５）が、前記所定量より小さいデータ量に対して最適
化され、前記第２文脈モデル（１１１５）が、前記所定
量より大きいデータ量に対して最適化されることを特徴
とする、実施態様８に記載の装置。
【００４５】
【発明の効果】以上のように、本発明を用いると、大き
なイメージの圧縮比に影響を与えずに、小さなファイル
の改善された圧縮比を提供することができる。
なイメージの圧縮比に影響を与えずに、小さなファイル
の改善された圧縮比を提供することができる。
【図１】算術圧縮器のブロック図である。
【図２】使用される確率表の成長するサイズをグラフに
表す図である。
表す図である。
【図３】使用される確率表のサイズを調整するために、
所与の文脈モデルがどのように使用されるかを示す図で
ある。
所与の文脈モデルがどのように使用されるかを示す図で
ある。
【図４】好ましい実施形態の論理的な操作を示す流れ図
である。
である。
【図５】本発明による算術圧縮器のブロック図である。
１０１：ビット １１０２：コントローラ １１０７：イメージ／シフト・レジスタ １１１３：確率表 １１１４：圧縮器 １１１５：文脈モデル １１１６：算術圧縮器
Claims (1)
- 【請求項１】元のデータを圧縮データに圧縮する方法で
あって、 前記元のデータのサイズを判定するステップと 前記サイズに基づいて文脈モデルを選択するステップと
前記文脈モデルを使用して、前記元のデータを前記圧縮
データに圧縮するステップとを含む方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/832,681 US5880688A (en) | 1997-04-09 | 1997-04-09 | Arithmetic coding context model that adapts to the amount of data |
| US832,681 | 1997-04-09 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH10341166A true JPH10341166A (ja) | 1998-12-22 |
| JPH10341166A5 JPH10341166A5 (ja) | 2005-08-11 |
Family
ID=25262346
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10095783A Pending JPH10341166A (ja) | 1997-04-09 | 1998-04-08 | データ量に適応するデータ圧縮方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5880688A (ja) |
| JP (1) | JPH10341166A (ja) |
| KR (1) | KR19980081236A (ja) |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100303085B1 (ko) | 1998-04-24 | 2001-09-24 | 전주범 | 이진형상신호부호화장치및방법 |
| GB2362532B (en) * | 2000-05-15 | 2004-05-05 | Nokia Mobile Phones Ltd | Video coding |
| EP1322117A1 (fr) * | 2001-12-06 | 2003-06-25 | Koninklijke Philips Electronics N.V. | Dispositif de codage/décodage arithmétique |
| US20040249882A1 (en) * | 2003-06-04 | 2004-12-09 | Eidson John C. | Approximate information preservation using subsets |
| KR100718134B1 (ko) * | 2005-07-21 | 2007-05-14 | 삼성전자주식회사 | 비트율에 적응적인 영상 데이터 이진 산술 부호화/복호화장치 및 방법 |
| US20070096956A1 (en) * | 2005-10-31 | 2007-05-03 | Fujifilm Microdisks Usa Inc. | Static defined word compressor for embedded applications |
| US8843455B2 (en) | 2011-08-24 | 2014-09-23 | Google Inc. | System and method of font compression using selectable entropy encoding |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5023611A (en) * | 1989-07-28 | 1991-06-11 | At&T Bell Laboratories | Entropy encoder/decoder including a context extractor |
| US5045852A (en) * | 1990-03-30 | 1991-09-03 | International Business Machines Corporation | Dynamic model selection during data compression |
| US5717394A (en) * | 1993-02-10 | 1998-02-10 | Ricoh Company Ltd. | Method and apparatus for encoding and decoding data |
| US5414423A (en) * | 1993-04-29 | 1995-05-09 | International Business Machines Corporation | Stabilization of probability estimates by conditioning on prior decisions of a given context |
| KR960015195A (ko) * | 1994-10-31 | 1996-05-22 | 배순훈 | 트리 구조 이원 연산 코딩 장치 |
| US5710562A (en) * | 1995-08-31 | 1998-01-20 | Ricoh Company Ltd. | Method and apparatus for compressing arbitrary data |
| US5886655A (en) * | 1997-04-09 | 1999-03-23 | Hewlett-Packard Company | Arithmetic coding context model that accelerates adaptation for small amounts of data |
-
1997
- 1997-04-09 US US08/832,681 patent/US5880688A/en not_active Expired - Lifetime
-
1998
- 1998-04-08 JP JP10095783A patent/JPH10341166A/ja active Pending
- 1998-04-09 KR KR1019980012597A patent/KR19980081236A/ko not_active Ceased
Also Published As
| Publication number | Publication date |
|---|---|
| KR19980081236A (ko) | 1998-11-25 |
| US5880688A (en) | 1999-03-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5886655A (en) | Arithmetic coding context model that accelerates adaptation for small amounts of data | |
| US5745608A (en) | Storing data compressed with arithmetic coding in non-contiguous memory | |
| US6597812B1 (en) | System and method for lossless data compression and decompression | |
| US5016009A (en) | Data compression apparatus and method | |
| US5506580A (en) | Data compression apparatus and method | |
| US5126739A (en) | Data compression apparatus and method | |
| JP2713369B2 (ja) | データ圧縮装置及び方法 | |
| JP3459030B2 (ja) | 符号化システム | |
| US5857035A (en) | Arithmetic coding compressor for encoding multiple bit values | |
| US5229768A (en) | Adaptive data compression system | |
| US5874908A (en) | Method and apparatus for encoding Lempel-Ziv 1 variants | |
| US5673042A (en) | Method of and an apparatus for compressing/decompressing data | |
| US5877711A (en) | Method and apparatus for performing adaptive data compression | |
| JP3211640B2 (ja) | ２値化画像の圧縮のための二次元的方法およびシステム | |
| US6442680B1 (en) | Method and system for compressing reduced instruction set computer (RISC) executable code | |
| JPH10341166A (ja) | データ量に適応するデータ圧縮方法 | |
| US5901251A (en) | Arithmetic coding compressor using a context model that is adaptive to variable length patterns in bi-level image data | |
| EP0797348A2 (en) | A one dimensional context model for entropy encoding digital halftone images with arithmetic coding | |
| US5745603A (en) | Two dimensional context model obtained without a line buffer for arithmetic coding | |
| JP3266419B2 (ja) | データ圧縮・伸長方式 | |
| JP3283150B2 (ja) | データ圧縮・圧縮解除法 | |
| GB2305277A (en) | A lossy data compression method | |
| Reif et al. | REAL-TIME DYNAMIC COMPRESSION OF VIDEO ON A GRID-CONNECTED PAR-ALLEL COMPUTER | |
| JPH10108026A (ja) | 非可逆データ圧縮方法 | |
| JP3603099B2 (ja) | データの可逆符号化方法および装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| RD02 | Notification of acceptance of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7422 Effective date: 20050117 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050120 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050120 |
|
| RD04 | Notification of resignation of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7424 Effective date: 20050128 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20060901 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20060905 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20061204 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20061207 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20070424 |