JPH03204234A - 圧縮データ復元方法 - Google Patents
圧縮データ復元方法Info
- Publication number
- JPH03204234A JPH03204234A JP2313009A JP31300990A JPH03204234A JP H03204234 A JPH03204234 A JP H03204234A JP 2313009 A JP2313009 A JP 2313009A JP 31300990 A JP31300990 A JP 31300990A JP H03204234 A JPH03204234 A JP H03204234A
- Authority
- JP
- Japan
- Prior art keywords
- dictionary
- literal
- history
- hysteresis
- lexicon
- 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.)
- Granted
Links
- 239000000872 buffer Substances 0.000 claims abstract description 44
- 238000000034 method Methods 0.000 claims description 35
- 238000007906 compression Methods 0.000 description 28
- 230000006835 compression Effects 0.000 description 28
- 230000006870 function Effects 0.000 description 12
- 230000006837 decompression Effects 0.000 description 4
- 238000004891 communication Methods 0.000 description 3
- 238000013144 data compression Methods 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 230000003044 adaptive effect Effects 0.000 description 2
- 230000008569 process Effects 0.000 description 2
- 230000008901 benefit Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000015556 catabolic process Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000006731 degradation reaction Methods 0.000 description 1
- 238000012217 deletion Methods 0.000 description 1
- 230000037430 deletion Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000003780 insertion Methods 0.000 description 1
- 230000037431 insertion Effects 0.000 description 1
- 230000007246 mechanism Effects 0.000 description 1
- 238000003672 processing method Methods 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
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/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
- H03M7/3086—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing a sliding window, e.g. LZ77
-
- 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/42—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
Ａ、産業上の利用分野
本発明は、一般にデータ処理方法、より具体的には伝送
または記憶アプリケーションで圧縮データを復元する方
法に関するものである。
または記憶アプリケーションで圧縮データを復元する方
法に関するものである。
Ｂ、従来の技術及びその課題
圧縮とは、データの表現を最小にするためのデータの符
号化である。たとえば、圧縮を用いて、ファイルの必要
記憶容量を減少させ、チャネル上の通信速度を高める、
もしくは安全保護向上のための暗号化に先だって冗長度
を減少させることが可能になる。
号化である。たとえば、圧縮を用いて、ファイルの必要
記憶容量を減少させ、チャネル上の通信速度を高める、
もしくは安全保護向上のための暗号化に先だって冗長度
を減少させることが可能になる。
データ圧縮の１方法が、ジブ（Ｚｉｖ） とレンベル
（Ｌｅｍｐｅｌ）の論文″Ａ Ｕｎｉｖｅｒｓａｌ Ａ
ｌｇｏｒｉｔｈｍＦｏｒ ５ｅｑｕｅｎｔｉａｌ Ｄａ
ｔａ Ｃｏｍｐｒｅｓｓｉｏｎ ” ％ ＩＥＥＥＴｒ
ａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒ＋＋ａｔｉｏ
ｎ Ｔｈｅｏｒｙ、 Ｖ ｏ １ 。
（Ｌｅｍｐｅｌ）の論文″Ａ Ｕｎｉｖｅｒｓａｌ Ａ
ｌｇｏｒｉｔｈｍＦｏｒ ５ｅｑｕｅｎｔｉａｌ Ｄａ
ｔａ Ｃｏｍｐｒｅｓｓｉｏｎ ” ％ ＩＥＥＥＴｒ
ａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒ＋＋ａｔｉｏ
ｎ Ｔｈｅｏｒｙ、 Ｖ ｏ １ 。
ＩＴ−２３、Ｎｏ、３、ｐｐ、３３７−４３．１９７７
年５月に開示されている。レンペルージブ・アルゴリズ
ムは基本的に、データ列の履歴を後方参照し、一致が見
つかったとき、実際のデータを短縮された符号で置き換
える機構である。シンベル−ジブ法の種々の実施様態で
は、５１２（小テーブル）、１０２４（中テーブル）ま
たは４０９６（大テーブル）の特定の列または後方参照
を辞典または辞書に記録する。これらは、辞典に挿入さ
れる列の選択方法が異なる。
年５月に開示されている。レンペルージブ・アルゴリズ
ムは基本的に、データ列の履歴を後方参照し、一致が見
つかったとき、実際のデータを短縮された符号で置き換
える機構である。シンベル−ジブ法の種々の実施様態で
は、５１２（小テーブル）、１０２４（中テーブル）ま
たは４０９６（大テーブル）の特定の列または後方参照
を辞典または辞書に記録する。これらは、辞典に挿入さ
れる列の選択方法が異なる。
基本的なレンペルージブ・アルゴリズムに対する様々な
改良がある。１つは、バイトまたは文字拡張の改良であ
り、辞典内の各列は、辞典内の他の列の末尾に１つまた
は複数のバイトを°追加したものと同じである。もう１
つは、列拡張しンペルージブ・アルゴリズムであり、辞
典内の各列は、辞典内の他の２つの列を連結したもので
ある。はとんどの状況では、列拡張技法の方がよい圧縮
結果をもたらす。
改良がある。１つは、バイトまたは文字拡張の改良であ
り、辞典内の各列は、辞典内の他の列の末尾に１つまた
は複数のバイトを°追加したものと同じである。もう１
つは、列拡張しンペルージブ・アルゴリズムであり、辞
典内の各列は、辞典内の他の２つの列を連結したもので
ある。はとんどの状況では、列拡張技法の方がよい圧縮
結果をもたらす。
大テーブル列拡張しンペルージブ・アルゴリズムは、優
れた汎用適応データ圧縮技法であると一般に考えられて
いる。大テーブル列拡張しンペルージブ技法の欠点は、
圧縮を行う機械内にかなりのメモリと高速の中央演算処
理装置を必要とすることである。復元は、メモリ及びプ
ロセッサ・サイクルの点で相対的に低コストである。多
数の並列なデータ・ストリームの圧縮を支援しなければ
ならない装置では、一般にメモリの方が実行速度よりも
大きな問題である。これは、並列なデータ・ス） ＩＪ
−ムのすべてが同時に活動状態であるわけではなく、シ
たがってＣＰＵ負荷が最悪の場合に近くなることがほと
んどないためである。また、ＣＰＵに対する要求が過度
になったときの性能低下は、漸次的であり、破局的では
ない。すなわち、ある装置が支援しなければならないデ
ータ・ストリームの数は、プロセッサの実行速度の弱い
関数である。それとは対照的に、適応圧縮テーブル専用
のメモリは、データ・ストリームが遊休状態のときでも
割り当てられていなければならない。このため、特定の
装置が支援できるデータ・ストリームの数が効果的に制
限される。
れた汎用適応データ圧縮技法であると一般に考えられて
いる。大テーブル列拡張しンペルージブ技法の欠点は、
圧縮を行う機械内にかなりのメモリと高速の中央演算処
理装置を必要とすることである。復元は、メモリ及びプ
ロセッサ・サイクルの点で相対的に低コストである。多
数の並列なデータ・ストリームの圧縮を支援しなければ
ならない装置では、一般にメモリの方が実行速度よりも
大きな問題である。これは、並列なデータ・ス） ＩＪ
−ムのすべてが同時に活動状態であるわけではなく、シ
たがってＣＰＵ負荷が最悪の場合に近くなることがほと
んどないためである。また、ＣＰＵに対する要求が過度
になったときの性能低下は、漸次的であり、破局的では
ない。すなわち、ある装置が支援しなければならないデ
ータ・ストリームの数は、プロセッサの実行速度の弱い
関数である。それとは対照的に、適応圧縮テーブル専用
のメモリは、データ・ストリームが遊休状態のときでも
割り当てられていなければならない。このため、特定の
装置が支援できるデータ・ストリームの数が効果的に制
限される。
データが圧縮された後には、圧縮されたデータを使用す
る前にそれを復元する必要がある。
る前にそれを復元する必要がある。
Ｃ２課題を解決するための手段
本発明の復元方法は、２つのデータ構造、すなわち履歴
バッファおよび辞典（レキシコン）を効率的に利用する
。この場合、列とは、有限個の記号の集合のうちから選
択された一連の順序付けられたデータ記号であると定義
する。履歴バッファとは、最も最近に圧縮機能を通過し
た未圧縮のデータの正確な記録である。辞典とは、長さ
が１以上の列の集合である。
バッファおよび辞典（レキシコン）を効率的に利用する
。この場合、列とは、有限個の記号の集合のうちから選
択された一連の順序付けられたデータ記号であると定義
する。履歴バッファとは、最も最近に圧縮機能を通過し
た未圧縮のデータの正確な記録である。辞典とは、長さ
が１以上の列の集合である。
本発明の復元方法は、履歴参照、辞典参照およびリテラ
ル参照のシーケンスを含む入力データ・ストリームを記
号の出力ストリームに変換することによって動作する。
ル参照のシーケンスを含む入力データ・ストリームを記
号の出力ストリームに変換することによって動作する。
この復元方法は、復元効率が最大になるように履歴バッ
ファと辞典をインクリメンタルに更新する。この復元方
法は、変換操作を逆にして元のデータ・ストリームを正
確に再構成するための十分な情報を受は取る。この復元
機能は、圧縮されたデータ・ストリーム自体以外の追加
データは必要としない。
ファと辞典をインクリメンタルに更新する。この復元方
法は、変換操作を逆にして元のデータ・ストリームを正
確に再構成するための十分な情報を受は取る。この復元
機能は、圧縮されたデータ・ストリーム自体以外の追加
データは必要としない。
本発明の方法では、参照が入力データ・ストリームから
順次読み取られる。読み取られた参照が辞典参照である
場合、その辞典参照によって表される辞典の列が発行さ
れる。読み取られた参照が履歴参照である場合、その履
歴参照によって表される履歴の列が発行（ｅｍｉｔ）
される。読み取られた参照がリテラル参照である場合
、そのリテラル参照によって表される記号が発行される
。履歴列が発行される場合、その列は辞典に挿入される
。発行された各列は、それが履歴列、辞典列、リテラル
記号のいずれであっても、履歴バッファに付加される。
順次読み取られる。読み取られた参照が辞典参照である
場合、その辞典参照によって表される辞典の列が発行さ
れる。読み取られた参照が履歴参照である場合、その履
歴参照によって表される履歴の列が発行（ｅｍｉｔ）
される。読み取られた参照がリテラル参照である場合
、そのリテラル参照によって表される記号が発行される
。履歴列が発行される場合、その列は辞典に挿入される
。発行された各列は、それが履歴列、辞典列、リテラル
記号のいずれであっても、履歴バッファに付加される。
参照は、入力データ・ストリームが終りになるまでそこ
から順次読み取られる。
から順次読み取られる。
Ｄ、実施例
本発明の圧縮方法を第１図に図示する。本発明の圧縮方
法の最初のステップである、ブロック１１では、履歴バ
ッファ、辞典およびトークンをクリアする。トークンは
、データ・シーケンスの記号が付加される、作業用のサ
ブストリングである。
法の最初のステップである、ブロック１１では、履歴バ
ッファ、辞典およびトークンをクリアする。トークンは
、データ・シーケンスの記号が付加される、作業用のサ
ブストリングである。
トークン、履歴バッファおよび辞典は最初は空である。
履歴バッファは、Ｏの基底から始まる正の整数を指標と
する、記号値の１次元配列として実施される。履歴バッ
ファの長さは、ある値に固定される。履歴バッファの長
さはちょうど２の累乗であることが好ましい。好ましい
実施例では、多くの形式の２進データ・ファイルおよび
テキスト・ファイルで、８ビツト・パイ）２０４８個の
履歴バッファ長がうまく働く。
する、記号値の１次元配列として実施される。履歴バッ
ファの長さは、ある値に固定される。履歴バッファの長
さはちょうど２の累乗であることが好ましい。好ましい
実施例では、多くの形式の２進データ・ファイルおよび
テキスト・ファイルで、８ビツト・パイ）２０４８個の
履歴バッファ長がうまく働く。
履歴バッファ内の記号列は、オフセット値と長さ値を含
む履歴参照によって一義的に指定できる。
む履歴参照によって一義的に指定できる。
オフセット値とは、参照列内の最初の記号のバッファを
指すインデックスであると定義される。長さ値は、オフ
セットによって識別される記号がら始まる参照列に属す
る記号の数である。履歴参照の長さの最大値を選択する
ことが好ましい。可能な最大の圧縮比はこの値に直接相
関して増加するが、データ・ストリーム形式ごとに、そ
の値を超えると、各一致ごとに平均文字数に対して符号
化された列の長さの値が大きすぎるため、平均圧縮比が
低下し始めるという、最適の長さが存在する。
指すインデックスであると定義される。長さ値は、オフ
セットによって識別される記号がら始まる参照列に属す
る記号の数である。履歴参照の長さの最大値を選択する
ことが好ましい。可能な最大の圧縮比はこの値に直接相
関して増加するが、データ・ストリーム形式ごとに、そ
の値を超えると、各一致ごとに平均文字数に対して符号
化された列の長さの値が大きすぎるため、平均圧縮比が
低下し始めるという、最適の長さが存在する。
ちょうど２の累乗であることが好ましいのは、致を符号
化するのに必要なビット数が、次の２の累乗まで変化し
ないためである。すなわち、長さの値を次の２の累乗ぴ
ったりに釘付けしないでおくと、潜在的な圧縮比の浪費
となる。好ましい実施例では、２０４８文字の履歴バッ
ファに対して、履歴参照の最大層が８ビツト・バイト１
６個であればうまく働くことが判明している。
化するのに必要なビット数が、次の２の累乗まで変化し
ないためである。すなわち、長さの値を次の２の累乗ぴ
ったりに釘付けしないでおくと、潜在的な圧縮比の浪費
となる。好ましい実施例では、２０４８文字の履歴バッ
ファに対して、履歴参照の最大層が８ビツト・バイト１
６個であればうまく働くことが判明している。
辞典は、それぞれが１個から履歴参照の最大層によって
指定される数までの記号を含む列を保持できる、単純な
要素配列として実施される。圧縮の間、辞典内の列は、
補助ハツシュ・テーブルを用いてルック・アップされる
。補助ハツシュ・テーブルは、ハツシュ・テーブルがま
ばらで効率的であることを保証するため、辞典自体の数
倍の要素を含むべきである。本発明の好ましい実施例の
２０４８バイトの履歴バッファでは、辞典のサイズが１
０２４であればうまく働くことが判明している。このサ
イズの辞典は、ハツシュ・テーブルの過度な衝突を避け
るため、少なくとも２０４８個のエントリを備えたハツ
シュ・テーブルで支援すべきである。
指定される数までの記号を含む列を保持できる、単純な
要素配列として実施される。圧縮の間、辞典内の列は、
補助ハツシュ・テーブルを用いてルック・アップされる
。補助ハツシュ・テーブルは、ハツシュ・テーブルがま
ばらで効率的であることを保証するため、辞典自体の数
倍の要素を含むべきである。本発明の好ましい実施例の
２０４８バイトの履歴バッファでは、辞典のサイズが１
０２４であればうまく働くことが判明している。このサ
イズの辞典は、ハツシュ・テーブルの過度な衝突を避け
るため、少なくとも２０４８個のエントリを備えたハツ
シュ・テーブルで支援すべきである。
ハツシュ・テーブルは当業者にとって周知であり、テー
ブル内にルックアップされる列を含む記号に対して数学
的操作を行なうことによって形成される。この数学的操
作で、ハツシュ・テーブル指標として有効な範囲内の１
個の整数が与えられる。その指標が指すハツシュ・テー
ブル・エントリは、辞典内の対応するエントリのインデ
ックスを含んでいる。この間接指定により、辞典がほと
んど空である圧縮の初期段階の間に辞典エン） ＩＪの
指標を効率的に割り当てることが可能になる〇辞典の最
初のエントリから始めて、順次高位のエン） ＩＪを構
築して順序通り辞典を溝たすことによって、この段階の
間に指標の値を送るのに必要なビット数が少なくなると
いう利点を得ることができる。
ブル内にルックアップされる列を含む記号に対して数学
的操作を行なうことによって形成される。この数学的操
作で、ハツシュ・テーブル指標として有効な範囲内の１
個の整数が与えられる。その指標が指すハツシュ・テー
ブル・エントリは、辞典内の対応するエントリのインデ
ックスを含んでいる。この間接指定により、辞典がほと
んど空である圧縮の初期段階の間に辞典エン） ＩＪの
指標を効率的に割り当てることが可能になる〇辞典の最
初のエントリから始めて、順次高位のエン） ＩＪを構
築して順序通り辞典を溝たすことによって、この段階の
間に指標の値を送るのに必要なビット数が少なくなると
いう利点を得ることができる。
辞典自体に比べてまばらな状態にハツシュ・テーブルを
保つことにより、複数の列が同じハツシュ・テーブル指
標にハツシュされるとき（これをハツシュ・テーブルの
衝突と称する）にどんな形のオーバフロ一連鎖も必要と
せずに優、れた性能を実現することができる。このよう
な衝突は、必要に応じて古いデータを捨て、それを新し
いデータで置き換えることによって処理される。リンク
された辞典エントリのＬＲＵ待ち行列をハツシュ・テー
ブルと共に用いると、辞典が最終的に満杯になったとき
、辞典エントリの挿入と削除が容易になる。
保つことにより、複数の列が同じハツシュ・テーブル指
標にハツシュされるとき（これをハツシュ・テーブルの
衝突と称する）にどんな形のオーバフロ一連鎖も必要と
せずに優、れた性能を実現することができる。このよう
な衝突は、必要に応じて古いデータを捨て、それを新し
いデータで置き換えることによって処理される。リンク
された辞典エントリのＬＲＵ待ち行列をハツシュ・テー
ブルと共に用いると、辞典が最終的に満杯になったとき
、辞典エントリの挿入と削除が容易になる。
固定サイズの辞典内で新しいエントリの場所をあけるた
めにあるエントリを捨てざるを得ないときは、長時間使
用されなかったエントリを捨てた方がよい。ＬＲＵ待ち
行列を使用すると、それが効率的に行なえる。
めにあるエントリを捨てざるを得ないときは、長時間使
用されなかったエントリを捨てた方がよい。ＬＲＵ待ち
行列を使用すると、それが効率的に行なえる。
本発明の圧縮方法の次のステップであるブロック１３で
は、変数ＭＡＴＣＨをリテラル形式にセットする。ＭＡ
ＴＣＨは、記号の列が履歴バッファ内と辞典内のどちら
に複製されているかに応じて、リテラル、履歴または辞
典のいずれかの形式となる。列が履歴バッファにも辞典
にも複製されていない場合は、ＭＡＴＣＨはリテラル形
式になる。
は、変数ＭＡＴＣＨをリテラル形式にセットする。ＭＡ
ＴＣＨは、記号の列が履歴バッファ内と辞典内のどちら
に複製されているかに応じて、リテラル、履歴または辞
典のいずれかの形式となる。列が履歴バッファにも辞典
にも複製されていない場合は、ＭＡＴＣＨはリテラル形
式になる。
本発明の圧縮方法の次のステップであるブロック１５で
は、入力列から記号を読み取って、それをトークンに付
加する。当初は、トークンは１個の文字からなっている
。しかし、本発明の方法が進行して、履歴バッファと辞
典とが満杯になったとき、トークンは複数の文字からな
る列となる。
は、入力列から記号を読み取って、それをトークンに付
加する。当初は、トークンは１個の文字からなっている
。しかし、本発明の方法が進行して、履歴バッファと辞
典とが満杯になったとき、トークンは複数の文字からな
る列となる。
判断ブロック１７で、このトークンを辞典の内容と比較
する。当初は辞典が空であるため、一致は見つからない
。しかし、本発明の方法がしばらく進行した後には、辞
典に列が挿入され、一致が見つかるようになる。辞典で
一致が見つかった場合、ブロック１９で、ＭＡＴＣ）Ｉ
を対応する指標値を伴う辞典形式にセットし、次にブロ
ック１５に戻って、入力列から次の記号を読み取ってト
ークンに付加する。
する。当初は辞典が空であるため、一致は見つからない
。しかし、本発明の方法がしばらく進行した後には、辞
典に列が挿入され、一致が見つかるようになる。辞典で
一致が見つかった場合、ブロック１９で、ＭＡＴＣ）Ｉ
を対応する指標値を伴う辞典形式にセットし、次にブロ
ック１５に戻って、入力列から次の記号を読み取ってト
ークンに付加する。
トークンが辞典内で複製されていない場合、判断フロッ
ク２１で、このトークンヲ履歴バッファの内容と比較す
る。この場合も、当初は履歴バッファが空であるため、
履歴バッファ内での一致は見つからない。しかし、本発
明の圧縮方法がしばらく進行した後には、このトークン
が履歴バッファ内で複製されている可能性がある。この
トークンが履歴バッファ内で複製されている場合、ブロ
ック２３で、ＭＡＴＣＨをオフセットと長さの値とを伴
う履歴形式にセットし、ブロック１５に戻って、入力列
から次の記号を読み取ってトークンに付加する。次に、
ブロック１７で、トークンを再び辞典の内容と比較する
。本発明の圧縮方法では、トークンが履歴参照の最大長
辺下である限り、辞典内でも履歴バッファ内でもトーク
ンが複製されていない状態になるまで、記号をトークン
に付加して、そのトークンを辞典および履歴バッファの
内容と比較することを続ける。こうして本方法は、辞典
内または履歴バッファ内で複製されている、許容される
最長の文字列を形成する。この最長の文字列は、トーク
ンから最後の文字を除いたものである。本開示では、１
個のリテラルを列であると見なす。
ク２１で、このトークンヲ履歴バッファの内容と比較す
る。この場合も、当初は履歴バッファが空であるため、
履歴バッファ内での一致は見つからない。しかし、本発
明の圧縮方法がしばらく進行した後には、このトークン
が履歴バッファ内で複製されている可能性がある。この
トークンが履歴バッファ内で複製されている場合、ブロ
ック２３で、ＭＡＴＣＨをオフセットと長さの値とを伴
う履歴形式にセットし、ブロック１５に戻って、入力列
から次の記号を読み取ってトークンに付加する。次に、
ブロック１７で、トークンを再び辞典の内容と比較する
。本発明の圧縮方法では、トークンが履歴参照の最大長
辺下である限り、辞典内でも履歴バッファ内でもトーク
ンが複製されていない状態になるまで、記号をトークン
に付加して、そのトークンを辞典および履歴バッファの
内容と比較することを続ける。こうして本方法は、辞典
内または履歴バッファ内で複製されている、許容される
最長の文字列を形成する。この最長の文字列は、トーク
ンから最後の文字を除いたものである。本開示では、１
個のリテラルを列であると見なす。
本発明の圧縮方法は、許容される最長の列を形成し終え
た後に、その列を象徴する参照を発行する。判断ブロッ
ク２５でＭＡＴＣＨが辞典形式であった場合は、ブロッ
ク２７で、ＭＡＴＣＨによって指定された辞典参照が出
力または発行される。
た後に、その列を象徴する参照を発行する。判断ブロッ
ク２５でＭＡＴＣＨが辞典形式であった場合は、ブロッ
ク２７で、ＭＡＴＣＨによって指定された辞典参照が出
力または発行される。
ＭＡＴＣＨが辞典形式ではない場合は、履歴形式または
リテラル形式のいずれかである。判断ブロック２９でＭ
ＡＴＣＨが履歴形式であった場合は、ブロック３１で、
ＭＡＴＣＨによって指定された履歴参照が発行または出
力される。
リテラル形式のいずれかである。判断ブロック２９でＭ
ＡＴＣＨが履歴形式であった場合は、ブロック３１で、
ＭＡＴＣＨによって指定された履歴参照が発行または出
力される。
また、ＭＡＴＣＨが履歴形式であった場合は、履歴参照
によって指定された参照列が辞典に追加され、辞典のサ
イズが記録される。
によって指定された参照列が辞典に追加され、辞典のサ
イズが記録される。
ＭＡＴＣＨが履歴形式ではない場合、それはリテラル形
式である。ブロック３３で、トークン内の記号に対する
リテラル参照が発行または出力される。辞典参照、履歴
参照またはリテラル参照が発行された後、ブロック３５
で、参照列が履歴バッファに付加され、トークンの先頭
から削除される。
式である。ブロック３３で、トークン内の記号に対する
リテラル参照が発行または出力される。辞典参照、履歴
参照またはリテラル参照が発行された後、ブロック３５
で、参照列が履歴バッファに付加され、トークンの先頭
から削除される。
同時に、履歴バッファのサイズが記録される。次に、ト
ークンはブロック１３に戻り、入力記号列が終りになる
までこの処理を続ける。
ークンはブロック１３に戻り、入力記号列が終りになる
までこの処理を続ける。
代表的なデータ・ストリームの確率論的研究に基づいて
、下記の符号化方式が最適に近い結果を生むことが判明
した。
、下記の符号化方式が最適に近い結果を生むことが判明
した。
リテラル参照 ｏ＋ｒ記号」
履歴参照 １＋Ｏ＋ ｒオフセット」＋「長さ」
辞典参照 １＋１＋ ｒ指標」
１″およびＯ″は２進数の１桁を表し、「オフセット」
、「長さ」および「指標」は、特定の場合にそれらの潜
在的な最大値を表すのに必要な最小のビット数で符号化
されている。より具体的には、必要なビット数は、潜在
的な最大値を最も近い２の累乗に切り上げた値の、２を
底とする対数に等しい。たとえば、辞典が１２個のエン
トリを含む場合、１２は１６（次の２の累乗）に切上げ
られ、１６の２を底とする対数は４なので、指標を符号
化するのに必要なビット数は４である。
、「長さ」および「指標」は、特定の場合にそれらの潜
在的な最大値を表すのに必要な最小のビット数で符号化
されている。より具体的には、必要なビット数は、潜在
的な最大値を最も近い２の累乗に切り上げた値の、２を
底とする対数に等しい。たとえば、辞典が１２個のエン
トリを含む場合、１２は１６（次の２の累乗）に切上げ
られ、１６の２を底とする対数は４なので、指標を符号
化するのに必要なビット数は４である。
「記号」は記号自体の８ビツト表現である。
本発明の圧縮機能に入るデータは、８ビツト・バイトと
して処理されるが、圧縮機能から出力されるデータは自
由形式のビット・ストリームである。前述のリテラル参
照、履歴参照および辞典参照に対する符号化規則により
、復元機能でこの自由形式のビット・ストリームを容易
にかつ曖昧さなしに解析することが可能となる。
して処理されるが、圧縮機能から出力されるデータは自
由形式のビット・ストリームである。前述のリテラル参
照、履歴参照および辞典参照に対する符号化規則により
、復元機能でこの自由形式のビット・ストリームを容易
にかつ曖昧さなしに解析することが可能となる。
典型的なアプリケーション環境では、各リテラル記号を
符号化するのに必要なビット数は、圧縮機能と復元機能
とを相互接続するシリアル通信チャネルの基本ブロック
・サイズに等しくなる。たとえば、ＥＢＣＤＩＣ環境で
は、記号の値は８ビツトを用いて符号化され、代表的な
通信リンク上を流れる基本的情報単位は、８ビツト文字
に量子化される。リテラル参照を符号化するのに必要な
ビット数は、常にこのようなリンクの基本ブロック・サ
イズよりも１だけ大きいので、最後のデータ・ブロック
内に利用可能な追加ビットが存在する場合は、最後の有
効な参照の末尾に１個の０ビツトを追加することによっ
て、最後の有効な文字の末尾の後ろの使用されていない
ビットを復元機能に強制的に無視させることが常に可能
である。Ｏビットを用いてリテラル参照の先頭を模倣す
ることにより、圧縮されたデータ・ストリームが次のブ
ロック境界で打ち切られたためにその参照が完了できな
いことを知った復元機能は、最後のデータ・ブロック内
の余分なビットを自動的に無視する。言い換えれば、復
元機能は０ビツトを「見る」と、８ビツト・リテラルを
得ることを期待する。０ビツトの後に何も続かない場合
、復元機能はそのシーケンスが完了したことを「知る」
。
符号化するのに必要なビット数は、圧縮機能と復元機能
とを相互接続するシリアル通信チャネルの基本ブロック
・サイズに等しくなる。たとえば、ＥＢＣＤＩＣ環境で
は、記号の値は８ビツトを用いて符号化され、代表的な
通信リンク上を流れる基本的情報単位は、８ビツト文字
に量子化される。リテラル参照を符号化するのに必要な
ビット数は、常にこのようなリンクの基本ブロック・サ
イズよりも１だけ大きいので、最後のデータ・ブロック
内に利用可能な追加ビットが存在する場合は、最後の有
効な参照の末尾に１個の０ビツトを追加することによっ
て、最後の有効な文字の末尾の後ろの使用されていない
ビットを復元機能に強制的に無視させることが常に可能
である。Ｏビットを用いてリテラル参照の先頭を模倣す
ることにより、圧縮されたデータ・ストリームが次のブ
ロック境界で打ち切られたためにその参照が完了できな
いことを知った復元機能は、最後のデータ・ブロック内
の余分なビットを自動的に無視する。言い換えれば、復
元機能は０ビツトを「見る」と、８ビツト・リテラルを
得ることを期待する。０ビツトの後に何も続かない場合
、復元機能はそのシーケンスが完了したことを「知る」
。
第２図には、本発明の復元方法の流れ図が示されている
。最初のステップであるブロック３７で、履歴バッファ
および辞典をクリアする。「履歴バッファおよび辞典は
、前述した圧縮機能のそれと同じ構造である。履歴バッ
ファと辞典がクリアされた後、ブロック３９で、入力か
ら参照が読み取られ、それに従ってＭＡＴＣＨがセット
される。参照の第１ビツトがＯである場合、ＭＡＴＣＨ
はリテラル形式である。参照の第１ビツトが１である場
合、ＭＡＴＣＨは辞典形式または履歴形式のいずれかで
ある。１に続くビットが０である場合、ＭＡＴＣＨは履
歴形式である。１に続くビットが１である場合、ＭＡＴ
ＣＨは辞典形式である。
。最初のステップであるブロック３７で、履歴バッファ
および辞典をクリアする。「履歴バッファおよび辞典は
、前述した圧縮機能のそれと同じ構造である。履歴バッ
ファと辞典がクリアされた後、ブロック３９で、入力か
ら参照が読み取られ、それに従ってＭＡＴＣＨがセット
される。参照の第１ビツトがＯである場合、ＭＡＴＣＨ
はリテラル形式である。参照の第１ビツトが１である場
合、ＭＡＴＣＨは辞典形式または履歴形式のいずれかで
ある。１に続くビットが０である場合、ＭＡＴＣＨは履
歴形式である。１に続くビットが１である場合、ＭＡＴ
ＣＨは辞典形式である。
判断ブロック４１でＭＡＴＣＨが辞典形式であった場合
、ブロック４３で、ＭＡＴＣＨによって指定された辞典
の列が出力される。
、ブロック４３で、ＭＡＴＣＨによって指定された辞典
の列が出力される。
ＭＡＴＣＨが辞典形式ではない場合、判断ブロック４５
でＭＡＴＣＨが履歴形式であった場合は、ブロック４７
で、ＭＡＴＣＨによって指定された履歴列を出力し、そ
の列を辞典に追加し、現在の辞典のエン） ＩＪ数を記
録する。ＭＡＴＣＨが辞典形式でも履歴形式でもない場
合は、ブロック４９で、ＭＡＴＣＨによって指定された
リテラル記号が出力される。最後に、ブロック４３．４
７または４９でＭＡＴＣＨによって指定された列を出力
した後に、ブロック５１で、その列を履歴バッファに付
加し、現在の履歴バッファのサイズを記録して、入力列
が終りになるまでこの処理を繰り返す。
でＭＡＴＣＨが履歴形式であった場合は、ブロック４７
で、ＭＡＴＣＨによって指定された履歴列を出力し、そ
の列を辞典に追加し、現在の辞典のエン） ＩＪ数を記
録する。ＭＡＴＣＨが辞典形式でも履歴形式でもない場
合は、ブロック４９で、ＭＡＴＣＨによって指定された
リテラル記号が出力される。最後に、ブロック４３．４
７または４９でＭＡＴＣＨによって指定された列を出力
した後に、ブロック５１で、その列を履歴バッファに付
加し、現在の履歴バッファのサイズを記録して、入力列
が終りになるまでこの処理を繰り返す。
当初は、復元機能の辞典と履歴バッファは空である。し
かし、復元機能が受は取る最初の参照はリテラル形式で
ある。リテラル参照を処理する際には、これを履歴バッ
ファに追加する。復元機能は、その履歴バッファ内で一
致を見つけると、履歴参照を発行する。圧縮機能と復元
機能の履歴バッファは同一であるため、履歴参照は復元
機能の履歴バッファ内の正しい記号列を識別する。圧縮
機能が履歴参照を発行し、復元機能がそれを受は取ると
、その履歴参照によって参照される列が、圧縮機能およ
び復元機能の当該の辞典に挿入される。
かし、復元機能が受は取る最初の参照はリテラル形式で
ある。リテラル参照を処理する際には、これを履歴バッ
ファに追加する。復元機能は、その履歴バッファ内で一
致を見つけると、履歴参照を発行する。圧縮機能と復元
機能の履歴バッファは同一であるため、履歴参照は復元
機能の履歴バッファ内の正しい記号列を識別する。圧縮
機能が履歴参照を発行し、復元機能がそれを受は取ると
、その履歴参照によって参照される列が、圧縮機能およ
び復元機能の当該の辞典に挿入される。
本発明の方法は、このように２つのデータ構造すなわち
履歴バッファおよび辞典を使用して、データ列の効率的
な圧縮を達成する。履歴バッファを固定された深さに制
限し、履歴参照の最大長を相対的に小さな値に制限し、
辞典内のエントリの最大数を固定した数に制限すること
により、極めて効率的にメモリを利用し、ずっと大量の
メモリを必要とする方法に匹敵する圧縮比をもたらす、
相互に関連した１組のデータ構造を設計することが可能
である。
履歴バッファおよび辞典を使用して、データ列の効率的
な圧縮を達成する。履歴バッファを固定された深さに制
限し、履歴参照の最大長を相対的に小さな値に制限し、
辞典内のエントリの最大数を固定した数に制限すること
により、極めて効率的にメモリを利用し、ずっと大量の
メモリを必要とする方法に匹敵する圧縮比をもたらす、
相互に関連した１組のデータ構造を設計することが可能
である。
Ｅ１発明の効果
本発明によれば、従来のレンベルージブ・アルゴリズム
より効率を向上させたデータ圧縮に対応する復元方法が
提供される。
より効率を向上させたデータ圧縮に対応する復元方法が
提供される。
第１図は、本発明の圧縮方法を示す流れ図である。
第２図は、本発明の復元方法を示す流れ図である。
Claims (4)
- （１）リテラル参照、履歴参照および辞典参照のシーケ
ンスからなるデータを復元する方法であって、 （ａ）前記のシーケンスから参照を１つ読み取るステッ
プと、 （ｂ）前記参照が辞典参照である場合に、辞典列を発行
するステップと、 （ｃ）前記参照が履歴参照である場合に、履歴列を発行
するステップと、 （ｄ）ステップ（ｃ）で発行された履歴列を辞典に追加
するステップと、 （ｅ）前記参照がリテラル参照である場合に、リテラル
列を発行するステップと、 （ｆ）ステップ（ｂ）、（ｃ）または（ｅ）で発行され
た列を履歴バッファに追加するステップと、 （ｇ）前記の参照のシーケンスが終りになるまで、ステ
ップ（ａ）ないし（ｆ）を繰り返すステップと、を含む
ことを特徴とする方法。 - （２）請求項１に記載の方法であって、前記辞典参照が
指標値を含むことを特徴とする方法。 - （３）請求項１に記載の方法であって、前記履歴参照が
、履歴バッファへのオフセットと長さの値を含むことを
特徴とする方法。 - （４）請求項１に記載の方法であって、前記履歴バッフ
ァが固定した長さであることを特徴とする方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/458,116 US5184126A (en) | 1989-12-28 | 1989-12-28 | Method of decompressing compressed data |
| US458116 | 1999-06-29 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH03204234A true JPH03204234A (ja) | 1991-09-05 |
| JPH0779264B2 JPH0779264B2 (ja) | 1995-08-23 |
Family
ID=23819422
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2313009A Expired - Lifetime JPH0779264B2 (ja) | 1989-12-28 | 1990-11-20 | 圧縮データ復元方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5184126A (ja) |
| EP (1) | EP0435802B1 (ja) |
| JP (1) | JPH0779264B2 (ja) |
| DE (1) | DE69021854T2 (ja) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5001478A (en) | 1989-12-28 | 1991-03-19 | International Business Machines Corporation | Method of encoding compressed data |
| US5184126A (en) | 1989-12-28 | 1993-02-02 | International Business Machines Corporation | Method of decompressing compressed data |
| US5010345A (en) | 1989-12-28 | 1991-04-23 | International Business Machines Corporation | Data compression method |
| US6092070A (en) * | 1992-02-11 | 2000-07-18 | Telcordia Technologies, Inc. | Method and system for lossless date compression and fast recursive expansion |
| US5467087A (en) * | 1992-12-18 | 1995-11-14 | Apple Computer, Inc. | High speed lossless data compression system |
| US5640551A (en) * | 1993-04-14 | 1997-06-17 | Apple Computer, Inc. | Efficient high speed trie search process |
| JP3273119B2 (ja) * | 1995-09-29 | 2002-04-08 | 京セラ株式会社 | データ圧縮・伸長装置 |
| US5805086A (en) * | 1995-10-10 | 1998-09-08 | International Business Machines Corporation | Method and system for compressing data that facilitates high-speed data decompression |
| US5778255A (en) * | 1995-10-10 | 1998-07-07 | International Business Machines Corporation | Method and system in a data processing system for decompressing multiple compressed bytes in a single machine cycle |
| US6657565B2 (en) * | 2002-03-21 | 2003-12-02 | International Business Machines Corporation | Method and system for improving lossless compression efficiency |
| US6674373B1 (en) * | 2002-07-03 | 2004-01-06 | Storage Technology Corporation | System and method for data decompression |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59231683A (ja) * | 1983-06-01 | 1984-12-26 | インタ−ナシヨナル ビジネス マシ−ンズ コ−ポレ−シヨン | データ圧縮方法 |
| JPS60116228A (ja) * | 1983-06-20 | 1985-06-22 | ユニシス コーポレーション | ディジタル信号ストリーム圧縮方法及び圧縮装置 |
| JPS63151224A (ja) * | 1986-12-04 | 1988-06-23 | インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン | データ圧縮方法 |
| JPS6413222A (en) * | 1987-07-07 | 1989-01-18 | Kubota Ltd | Magnetic recording medium |
Family Cites Families (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4814746A (en) | 1983-06-01 | 1989-03-21 | International Business Machines Corporation | Data compression method |
| US4725815A (en) * | 1984-01-16 | 1988-02-16 | International Business Machines Corporation | Method for encoding and decoding a digital image |
| GB2172127B (en) * | 1985-03-06 | 1988-10-12 | Ferranti Plc | Data compression system |
| US4730348A (en) * | 1986-09-19 | 1988-03-08 | Adaptive Computer Technologies | Adaptive data compression system |
| US4899148A (en) * | 1987-02-25 | 1990-02-06 | Oki Electric Industry Co., Ltd. | Data compression method |
| US4881075A (en) * | 1987-10-15 | 1989-11-14 | Digital Equipment Corporation | Method and apparatus for adaptive data compression |
| US4876541A (en) * | 1987-10-15 | 1989-10-24 | Data Compression Corporation | Stem for dynamically compressing and decompressing electronic data |
| US4847619A (en) | 1987-10-19 | 1989-07-11 | Hewlett-Packard Company | Performance-based reset of data compression dictionary |
| US4906991A (en) * | 1988-04-29 | 1990-03-06 | Xerox Corporation | Textual substitution data compression with finite length search windows |
| US5003307A (en) | 1989-01-13 | 1991-03-26 | Stac, Inc. | Data compression apparatus with shift register search means |
| US5016009A (en) | 1989-01-13 | 1991-05-14 | Stac, Inc. | Data compression apparatus and method |
| US5184126A (en) | 1989-12-28 | 1993-02-02 | International Business Machines Corporation | Method of decompressing compressed data |
| US5001478A (en) | 1989-12-28 | 1991-03-19 | International Business Machines Corporation | Method of encoding compressed data |
| US5010345A (en) | 1989-12-28 | 1991-04-23 | International Business Machines Corporation | Data compression method |
-
1989
- 1989-12-28 US US07/458,116 patent/US5184126A/en not_active Expired - Fee Related
-
1990
- 1990-10-31 DE DE69021854T patent/DE69021854T2/de not_active Expired - Fee Related
- 1990-10-31 EP EP90480181A patent/EP0435802B1/en not_active Expired - Lifetime
- 1990-11-20 JP JP2313009A patent/JPH0779264B2/ja not_active Expired - Lifetime
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59231683A (ja) * | 1983-06-01 | 1984-12-26 | インタ−ナシヨナル ビジネス マシ−ンズ コ−ポレ−シヨン | データ圧縮方法 |
| JPS60116228A (ja) * | 1983-06-20 | 1985-06-22 | ユニシス コーポレーション | ディジタル信号ストリーム圧縮方法及び圧縮装置 |
| JPS63151224A (ja) * | 1986-12-04 | 1988-06-23 | インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン | データ圧縮方法 |
| JPS6413222A (en) * | 1987-07-07 | 1989-01-18 | Kubota Ltd | Magnetic recording medium |
Also Published As
| Publication number | Publication date |
|---|---|
| DE69021854T2 (de) | 1996-05-02 |
| EP0435802A2 (en) | 1991-07-03 |
| US5184126A (en) | 1993-02-02 |
| EP0435802A3 (en) | 1991-09-04 |
| EP0435802B1 (en) | 1995-08-23 |
| DE69021854D1 (de) | 1995-09-28 |
| JPH0779264B2 (ja) | 1995-08-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH03204232A (ja) | 圧縮データの符号化方法 | |
| JPH03204233A (ja) | データ圧縮方法 | |
| US5532694A (en) | Data compression apparatus and method using matching string searching and Huffman encoding | |
| US5406278A (en) | Method and apparatus for data compression having an improved matching algorithm which utilizes a parallel hashing technique | |
| EP0350281B1 (en) | Method and apparatus for encoding, decoding and transmitting data in compressed form | |
| US6876774B2 (en) | Method and apparatus for compressing data string | |
| US5970177A (en) | Data compression using selective encoding | |
| Yamaguchi et al. | An efficient method for compressing test data | |
| EP0582907A2 (en) | Data compression apparatus and method using matching string searching and Huffman encoding | |
| JPS6356726B2 (ja) | ||
| US5502439A (en) | Method for compression of binary data | |
| JPH03204234A (ja) | 圧縮データ復元方法 | |
| JPH03204235A (ja) | 圧縮データの復号方法 | |
| CA2770348A1 (en) | Compression of bitmaps and values | |
| JP2026010210A (ja) | 受信したデータを処理する装置 | |
| ВАЩЕНКО et al. | Determining optimal compression algorithm for files of different formats | |
| Rani et al. | A survey on lossless text data compression techniques | |
| JP7849406B2 (ja) | ストレージシステム | |
| Zia et al. | Two-level dictionary-based text compression scheme | |
| JP2825960B2 (ja) | データ圧縮方法及び復元方法 | |
| Robert et al. | New algorithms for random access text compression | |
| Blumer | Applications of DAWGs to data compression | |
| JP3058711B2 (ja) | データ圧縮及び復元方法 | |
| Ferreira et al. | Time and Memory Efficient Lempel-Ziv Compression Using Suffix Arrays | |
| JPH06149537A (ja) | データ圧縮方法及び復元方法 |