JPH0779263B2 - データ圧縮方法 - Google Patents
データ圧縮方法Info
- Publication number
- JPH0779263B2 JPH0779263B2 JP2313008A JP31300890A JPH0779263B2 JP H0779263 B2 JPH0779263 B2 JP H0779263B2 JP 2313008 A JP2313008 A JP 2313008A JP 31300890 A JP31300890 A JP 31300890A JP H0779263 B2 JPH0779263 B2 JP H0779263B2
- Authority
- JP
- Japan
- Prior art keywords
- dictionary
- token
- history
- history buffer
- duplicated
- 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.)
- Expired - Lifetime
Links
- 238000000034 method Methods 0.000 title claims description 53
- 238000013144 data compression Methods 0.000 title claims description 21
- 239000000872 buffer Substances 0.000 claims description 72
- 108010076504 Protein Sorting Signals Proteins 0.000 claims 4
- 238000007906 compression Methods 0.000 description 34
- 230000006835 compression Effects 0.000 description 34
- 230000006870 function Effects 0.000 description 16
- 230000006837 decompression Effects 0.000 description 9
- 238000004891 communication Methods 0.000 description 4
- 230000003044 adaptive effect Effects 0.000 description 3
- 230000008569 process Effects 0.000 description 3
- 230000006872 improvement Effects 0.000 description 2
- 238000012545 processing Methods 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
- 238000013500 data storage Methods 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
- 230000000694 effects Effects 0.000 description 1
- 238000005516 engineering process Methods 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
- 238000007639 printing Methods 0.000 description 1
- 238000003672 processing method Methods 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
- 239000002699 waste material Substances 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/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
-
- 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/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
- H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Description
【発明の詳細な説明】 A.産業上の利用分野 本発明は、一般にデータ処理方法、より具体的には伝送
または記憶用にデータを圧縮する方法に関するものであ
る。
または記憶用にデータを圧縮する方法に関するものであ
る。
B.従来の技術及びその課題 圧縮とは、データの表現を最小にするためのデータの符
号化である。たとえば、圧縮を用いて、ファイルの必要
記憶容量を減少させ、チャネル上の通信速度を高める、
もしくは安全保護向上のための暗号化に先だって冗長度
を減少させることが可能になる。
号化である。たとえば、圧縮を用いて、ファイルの必要
記憶容量を減少させ、チャネル上の通信速度を高める、
もしくは安全保護向上のための暗号化に先だって冗長度
を減少させることが可能になる。
データ圧縮の１方法が、ジブ（Ziv）とレンペル（Lempe
l）の論文“A Universal Algorithm For Sequential Da
ta Compression"、IEEE Transactions on Information
Theory,Vol.IT−23、No.3、pp.337−43、1977年５月に
開示されている。レンペル−ジブ・アルゴリズムは基本
的に、データ列の履歴を後方参照し、一致が見つかった
とき、実際のデータを短縮された符号で置き換える機構
である。レンペル−ジブ法の種々の実施態様では、512
（小テーブル）、1024（中テーブル）または4096（大テ
ーブル）の特定の列または後方参照を辞典または辞書に
記録する。これらは、辞典に挿入される列の選択方法が
異なる。
l）の論文“A Universal Algorithm For Sequential Da
ta Compression"、IEEE Transactions on Information
Theory,Vol.IT−23、No.3、pp.337−43、1977年５月に
開示されている。レンペル−ジブ・アルゴリズムは基本
的に、データ列の履歴を後方参照し、一致が見つかった
とき、実際のデータを短縮された符号で置き換える機構
である。レンペル−ジブ法の種々の実施態様では、512
（小テーブル）、1024（中テーブル）または4096（大テ
ーブル）の特定の列または後方参照を辞典または辞書に
記録する。これらは、辞典に挿入される列の選択方法が
異なる。
基本的なレンペル−ジブ・アルゴリズムに対する様々な
改良がある。１つは、バイトまたは文字拡張の改良であ
り、辞典内の各列は、辞典内の他の列の末尾に１つまた
は複数のバイトを追加したものと同じである。もう１つ
は、列拡張レンペル−ジブ・アルゴリズムであり、辞典
内の各列は、辞典内の他の２つの列を連結したものであ
る。ほとんどの状況では、列拡張技法の方がよい圧縮結
果をもたらす。
改良がある。１つは、バイトまたは文字拡張の改良であ
り、辞典内の各列は、辞典内の他の列の末尾に１つまた
は複数のバイトを追加したものと同じである。もう１つ
は、列拡張レンペル−ジブ・アルゴリズムであり、辞典
内の各列は、辞典内の他の２つの列を連結したものであ
る。ほとんどの状況では、列拡張技法の方がよい圧縮結
果をもたらす。
大テーブル列拡張レンペル−ジブ・アルゴリズムは、優
れた汎用適応データ圧縮技法であると一般に考えられて
いる。大テーブル列拡張レンペル−ジブ技法の欠点は、
圧縮を行う機械内にかなりのメモリと高速の中央演算処
理装置を必要とすることである。復元は、メモリ及びプ
ロセッサ・サイクルの点で相対的に低コストである。多
数の並列なデータ・ストリームの圧縮を支援しなければ
ならない装置では、一般にメモリの方が実行速度よりも
大きな問題である。これは、並列なデータ・ストリーム
のすべてが同時に活動状態であるわけではなく、したが
ってCPU負荷が最悪の場合に近くなることがほとんどな
いためである。また、CPUに対する要求が過度になった
ときの性能低下は、漸次的であり、破局的ではない。す
なわち、ある装置が支援しなければならないデータ・ス
トリームの数は、プロセッサの実行速度の弱い関数であ
る。それとは対照的に、適応圧縮テーブル専用のメモリ
は、データ・ストリームが遊休状態のときでも割り当て
られていなければならない。このため、特定の装置が支
援できるデータ・ストリームの数が効果的に制限され
る。
れた汎用適応データ圧縮技法であると一般に考えられて
いる。大テーブル列拡張レンペル−ジブ技法の欠点は、
圧縮を行う機械内にかなりのメモリと高速の中央演算処
理装置を必要とすることである。復元は、メモリ及びプ
ロセッサ・サイクルの点で相対的に低コストである。多
数の並列なデータ・ストリームの圧縮を支援しなければ
ならない装置では、一般にメモリの方が実行速度よりも
大きな問題である。これは、並列なデータ・ストリーム
のすべてが同時に活動状態であるわけではなく、したが
ってCPU負荷が最悪の場合に近くなることがほとんどな
いためである。また、CPUに対する要求が過度になった
ときの性能低下は、漸次的であり、破局的ではない。す
なわち、ある装置が支援しなければならないデータ・ス
トリームの数は、プロセッサの実行速度の弱い関数であ
る。それとは対照的に、適応圧縮テーブル専用のメモリ
は、データ・ストリームが遊休状態のときでも割り当て
られていなければならない。このため、特定の装置が支
援できるデータ・ストリームの数が効果的に制限され
る。
C.課題を解決するための手段 本発明の適応圧縮方法は、２つのデータ構造、すなわち
履歴バッファおよび辞典（レキシコン）を効率的に利用
して、通信またはデータ記憶環境に適した、汎用のスト
リーム本位のデータ圧縮を実行する。この場合、列と
は、有限個の記号の集合のうちから選択された一連の順
序付けられたデータ記号であると定義する。
履歴バッファおよび辞典（レキシコン）を効率的に利用
して、通信またはデータ記憶環境に適した、汎用のスト
リーム本位のデータ圧縮を実行する。この場合、列と
は、有限個の記号の集合のうちから選択された一連の順
序付けられたデータ記号であると定義する。
履歴バッファとは、最も最近に圧縮機能を通過した未圧
縮のデータの正確な記録である。辞典とは、長さが１以
上の列の集合である。
縮のデータの正確な記録である。辞典とは、長さが１以
上の列の集合である。
本発明の圧縮方法は、入力データ・ストリームを履歴参
照、辞典参照およびリテラル参照のシーケンスに変換す
ると同時に、圧縮効率が最大になるように履歴バッファ
と辞典をインクリメンタルに更新することによって動作
する。また本発明の圧縮方法は、前記の変換操作を逆に
して元のデータ・ストリームを正確に再構成するのに十
分な情報を、対をなす復元方法に提供する。復元機能
は、圧縮されたデータ・ストリーム自体以外の追加デー
タは必要としない。
照、辞典参照およびリテラル参照のシーケンスに変換す
ると同時に、圧縮効率が最大になるように履歴バッファ
と辞典をインクリメンタルに更新することによって動作
する。また本発明の圧縮方法は、前記の変換操作を逆に
して元のデータ・ストリームを正確に再構成するのに十
分な情報を、対をなす復元方法に提供する。復元機能
は、圧縮されたデータ・ストリーム自体以外の追加デー
タは必要としない。
本発明の方法では、辞典または履歴バッファ内でトーク
ンが見つからなくなるまで、記号が順次トークンに付加
される。詳細に言えば、記号をトークンに付加し、次に
そのトークンを辞典の内容と比較する。そのトークンが
辞典内に複製されている場合、次の記号をそのトークン
に付加し、このトークンを再び辞典の内容と比較する。
トークンが辞典内に複製されていない状態になるまで、
記号をトークンに順次付加する。次に、トークンを履歴
バッファの内容と比較する。トークンが履歴バッファ内
に複製されている場合は、次の記号をトークンに付加
し、このトークンを履歴バッファの内容を比較する。こ
のようにして辞典にも履歴バッファにも複製されたトー
クンが存在しなくなるまで、記号がトークンに付加され
る。したがって、本方法は、トークンの最後の文字を除
いた部分、すなわち辞典または履歴バッファ内で見つか
る最長の列と一致するものを見つける。辞典内で一致が
見つかった場合、辞典参照を発行（emit）する。履歴バ
ッファ内で一致が見つかった場合、履歴参照を発行す
る。履歴バッファ内でも辞典内でも一致が見つからない
場合は、リテラル参照を発行する。履歴参照が発行され
るときは、その履歴参照によって参照される記号の列を
辞典に追加する。したがって、辞典は、以前に複製され
た列から構築される。発行されたリテラル参照、履歴参
照または辞典参照によって表される参照列は、履歴バッ
ファに記憶される。参照を発行した後に、その参照列を
トークンから削除し、文字のシーケンスが終りになるま
でこの処理を繰り返す。
ンが見つからなくなるまで、記号が順次トークンに付加
される。詳細に言えば、記号をトークンに付加し、次に
そのトークンを辞典の内容と比較する。そのトークンが
辞典内に複製されている場合、次の記号をそのトークン
に付加し、このトークンを再び辞典の内容と比較する。
トークンが辞典内に複製されていない状態になるまで、
記号をトークンに順次付加する。次に、トークンを履歴
バッファの内容と比較する。トークンが履歴バッファ内
に複製されている場合は、次の記号をトークンに付加
し、このトークンを履歴バッファの内容を比較する。こ
のようにして辞典にも履歴バッファにも複製されたトー
クンが存在しなくなるまで、記号がトークンに付加され
る。したがって、本方法は、トークンの最後の文字を除
いた部分、すなわち辞典または履歴バッファ内で見つか
る最長の列と一致するものを見つける。辞典内で一致が
見つかった場合、辞典参照を発行（emit）する。履歴バ
ッファ内で一致が見つかった場合、履歴参照を発行す
る。履歴バッファ内でも辞典内でも一致が見つからない
場合は、リテラル参照を発行する。履歴参照が発行され
るときは、その履歴参照によって参照される記号の列を
辞典に追加する。したがって、辞典は、以前に複製され
た列から構築される。発行されたリテラル参照、履歴参
照または辞典参照によって表される参照列は、履歴バッ
ファに記憶される。参照を発行した後に、その参照列を
トークンから削除し、文字のシーケンスが終りになるま
でこの処理を繰り返す。
D.実施例 本発明の圧縮方法を第１図に図示する。本発明の圧縮方
法の最初のステップであるブロック11では、履歴バッフ
ァ、辞典およびトークンをクリアする。トークンは、デ
ータ・シーケンスの記号が付加される、作業用のサブス
トリングである。トークン、履歴バッファおよび辞典は
最初は空である。
法の最初のステップであるブロック11では、履歴バッフ
ァ、辞典およびトークンをクリアする。トークンは、デ
ータ・シーケンスの記号が付加される、作業用のサブス
トリングである。トークン、履歴バッファおよび辞典は
最初は空である。
履歴バッファは、０の基底から始まる正の整数を指標と
する、記号値の１次元配列として実施される。履歴バッ
ファの長さは、ある値に固定される。履歴バッファの長
さはちょうど２の累乗であることが好ましい。好ましい
実施例では、多くの形式の２進データ・ファイルおよび
テキスト・ファイルで、８ビット・バイト2048個の履歴
バッファ長がうまく働く。
する、記号値の１次元配列として実施される。履歴バッ
ファの長さは、ある値に固定される。履歴バッファの長
さはちょうど２の累乗であることが好ましい。好ましい
実施例では、多くの形式の２進データ・ファイルおよび
テキスト・ファイルで、８ビット・バイト2048個の履歴
バッファ長がうまく働く。
履歴バッファ内の記号列は、オフセット値と長さ値を含
む履歴参照によって一義的に指定できる。オフセット値
とは、参照列内の最初の記号のバッファを指すインデッ
クスであると定義される。長さ値は、オフセットによっ
て識別される記号から始まる参照列に属する記号の数で
ある。履歴参照の長さの最大値を選択することが好まし
い。可能な最大の圧縮比はこの値に直接相関して増加す
るが、データ・ストリーム形式ごとに、その値を超える
と、各一致ごとに平均文字数に対して符号化された列の
長さの値が大きすぎるため、平均圧縮比が低下し始める
という、最適の長さが存在する。ちょうど２の累乗であ
ることが好ましいのは、一致を符号化するのに必要なビ
ット数が、次の２の累乗まで変化しないためである。す
なわち、長さの値を次の２の累乗ぴったりに釘付けしな
いでおくと、潜在的な圧縮比の浪費となる。好ましい実
施例では、2048文字の履歴バッファに対して、履歴参照
の最大長が８ビット・バイト16個であればうまく働くこ
とが判明している。
む履歴参照によって一義的に指定できる。オフセット値
とは、参照列内の最初の記号のバッファを指すインデッ
クスであると定義される。長さ値は、オフセットによっ
て識別される記号から始まる参照列に属する記号の数で
ある。履歴参照の長さの最大値を選択することが好まし
い。可能な最大の圧縮比はこの値に直接相関して増加す
るが、データ・ストリーム形式ごとに、その値を超える
と、各一致ごとに平均文字数に対して符号化された列の
長さの値が大きすぎるため、平均圧縮比が低下し始める
という、最適の長さが存在する。ちょうど２の累乗であ
ることが好ましいのは、一致を符号化するのに必要なビ
ット数が、次の２の累乗まで変化しないためである。す
なわち、長さの値を次の２の累乗ぴったりに釘付けしな
いでおくと、潜在的な圧縮比の浪費となる。好ましい実
施例では、2048文字の履歴バッファに対して、履歴参照
の最大長が８ビット・バイト16個であればうまく働くこ
とが判明している。
辞典は、それぞれが１個から履歴参照の最大長によって
指定される数までの記号を含む列を保持できる、単純な
要素配列として実施される。圧縮の間、辞典内の列は、
補助ハッシュ・テーブルを用いてルック・アップされ
る。補助ハッシュ・テーブルは、ハッシュ・テーブルが
まばらで効率的であることを保証するため、辞典自体の
数倍の要素を含むべきである。本発明の好ましい実施例
の2048バイトの履歴バッファでは、辞典のサイズが1024
であればうまく働くことが判明している。このサイズの
辞典は、ハッシュ・テーブルの過度な衝突を避けるた
め、少なくとも2048個のエントリを備えたハッシュ・テ
ーブルで支援すべきである。
指定される数までの記号を含む列を保持できる、単純な
要素配列として実施される。圧縮の間、辞典内の列は、
補助ハッシュ・テーブルを用いてルック・アップされ
る。補助ハッシュ・テーブルは、ハッシュ・テーブルが
まばらで効率的であることを保証するため、辞典自体の
数倍の要素を含むべきである。本発明の好ましい実施例
の2048バイトの履歴バッファでは、辞典のサイズが1024
であればうまく働くことが判明している。このサイズの
辞典は、ハッシュ・テーブルの過度な衝突を避けるた
め、少なくとも2048個のエントリを備えたハッシュ・テ
ーブルで支援すべきである。
ハッシュ・テーブルは当業者にとって周知であり、テー
ブル内にルックアップされる列を含む記号に対して数学
的操作を行なうことによって形成される。この数字的操
作で、ハッシュ・テーブル指標として有効な範囲内の１
個の整数が与えられる。その指標が指すハッシュ・テー
ブル・エントリは、辞典内の対応するエントリのインデ
ックスを含んでいる。この間接指定は、辞典がほとんど
空である圧縮の初期段階の間に辞典エントリの指標を効
率的に割り当てることが可能になる。辞典の最初のエン
トリから始めて、順次高位のエントリを構築して順序通
り辞典を満たすことによって、この段階の間に指標の値
を送るのに必要なビット数が少なくなるという利点を得
ることができる。
ブル内にルックアップされる列を含む記号に対して数学
的操作を行なうことによって形成される。この数字的操
作で、ハッシュ・テーブル指標として有効な範囲内の１
個の整数が与えられる。その指標が指すハッシュ・テー
ブル・エントリは、辞典内の対応するエントリのインデ
ックスを含んでいる。この間接指定は、辞典がほとんど
空である圧縮の初期段階の間に辞典エントリの指標を効
率的に割り当てることが可能になる。辞典の最初のエン
トリから始めて、順次高位のエントリを構築して順序通
り辞典を満たすことによって、この段階の間に指標の値
を送るのに必要なビット数が少なくなるという利点を得
ることができる。
辞典自体に比べてまばらな状態にハッシュ・テーブルを
保つことにより、複数の列が同じハッシュ・テーブル指
標にハッシュされるとき（これをハッシュ・テーブルの
衝突と称する）にどんな形のオーバフロー連鎖も必要と
せずに優れた性能を実現することができる。このような
衝突は、必要に応じて古いデータを捨て、それを新しい
データで置き換えることによって処理される。リンクさ
れた辞典エントリのLRU待ち行列をハッシュ・テーブル
と共に用いると、辞典が最終的に満杯になったとき、辞
典エントリの挿入と削除が容易になる。固定サイズの辞
典内で新しいエントリの場所をあけるためにあるエント
リを捨てざるを得ないときは、長時間使用されなかった
エントリを捨てた方がよい。LRU待ち行列を使用する
と、それが効率的に行なえる。
保つことにより、複数の列が同じハッシュ・テーブル指
標にハッシュされるとき（これをハッシュ・テーブルの
衝突と称する）にどんな形のオーバフロー連鎖も必要と
せずに優れた性能を実現することができる。このような
衝突は、必要に応じて古いデータを捨て、それを新しい
データで置き換えることによって処理される。リンクさ
れた辞典エントリのLRU待ち行列をハッシュ・テーブル
と共に用いると、辞典が最終的に満杯になったとき、辞
典エントリの挿入と削除が容易になる。固定サイズの辞
典内で新しいエントリの場所をあけるためにあるエント
リを捨てざるを得ないときは、長時間使用されなかった
エントリを捨てた方がよい。LRU待ち行列を使用する
と、それが効率的に行なえる。
本発明の圧縮方法の次のステップであるブロック13で
は、変数MATCHをリテラル形式にセットする。MATCHは、
記号の列が履歴バッファ内の辞典内のどちらに複製され
ているかに応じて、リテラル、履歴または辞典のいずれ
かの形式となる。列が履歴バッファにも辞典にも複製さ
れていない場合は、MATCHはリテラル形式になる。
は、変数MATCHをリテラル形式にセットする。MATCHは、
記号の列が履歴バッファ内の辞典内のどちらに複製され
ているかに応じて、リテラル、履歴または辞典のいずれ
かの形式となる。列が履歴バッファにも辞典にも複製さ
れていない場合は、MATCHはリテラル形式になる。
本発明の圧縮方法の次のステップであるブロック15で
は、入力列から記号を読み取って、それをトークンに付
加する。当初は、トークンは１個の文字からなってい
る。しかし、本発明の方法が進行して、履歴バッファと
辞典とが満杯になったとき、トークンは複数の文字から
なる列となる。判断ブロック17で、このトークンを辞典
の内容と比較する。当初は辞典が空であるため、一致は
見つからない。しかし、本発明の方法がしばらく進行し
た後には、辞典に列が挿入され、一致が見つかるように
なる。辞典で一致が見つかった場合、ブロック19で、MA
TCHを対応する指標値を伴う辞典形式にセットし、次に
ブロック15に戻って、入力列から次の信号を読み取って
トークンに付加する。
は、入力列から記号を読み取って、それをトークンに付
加する。当初は、トークンは１個の文字からなってい
る。しかし、本発明の方法が進行して、履歴バッファと
辞典とが満杯になったとき、トークンは複数の文字から
なる列となる。判断ブロック17で、このトークンを辞典
の内容と比較する。当初は辞典が空であるため、一致は
見つからない。しかし、本発明の方法がしばらく進行し
た後には、辞典に列が挿入され、一致が見つかるように
なる。辞典で一致が見つかった場合、ブロック19で、MA
TCHを対応する指標値を伴う辞典形式にセットし、次に
ブロック15に戻って、入力列から次の信号を読み取って
トークンに付加する。
トークンが辞典内で複製されていない場合、判断ブロッ
ク21で、このトークンを履歴バッファの内容と比較す
る。この場合も、当初は履歴バッファが空であるため、
履歴バッファ内での一致は見つからない。しかし、本発
明の圧縮方法がしばらく進行した後には、このトークン
が履歴バッファ内で複製されている可能性がある。この
トークンが履歴バッファ内で複製されている場合、ブロ
ック23で、MATCHをオフセットと長さの値とを伴う履歴
形式にセットし、ブロック15に戻って、入力列から次の
記号を読み取ってトークンに付加する。次に、ブロック
17で、トークンを再び辞典の内容と比較する。本発明の
圧縮方法では、トークンが履歴参照の最大長以下である
限り、辞典内でも履歴バッファ内でもトークンが複製さ
れていない状態になるまで、記号をトークンに付加し
て、そのトークンを辞典および履歴バッファの内容と比
較することを続ける。こうして本方法は、辞典内または
履歴バッファ内で複製されている、許容される最長の文
字列を形成する。この最長の文字列は、トークンから最
後の文字を除いたものである。本開示では、１個のリテ
ラルを列であると見なす。
ク21で、このトークンを履歴バッファの内容と比較す
る。この場合も、当初は履歴バッファが空であるため、
履歴バッファ内での一致は見つからない。しかし、本発
明の圧縮方法がしばらく進行した後には、このトークン
が履歴バッファ内で複製されている可能性がある。この
トークンが履歴バッファ内で複製されている場合、ブロ
ック23で、MATCHをオフセットと長さの値とを伴う履歴
形式にセットし、ブロック15に戻って、入力列から次の
記号を読み取ってトークンに付加する。次に、ブロック
17で、トークンを再び辞典の内容と比較する。本発明の
圧縮方法では、トークンが履歴参照の最大長以下である
限り、辞典内でも履歴バッファ内でもトークンが複製さ
れていない状態になるまで、記号をトークンに付加し
て、そのトークンを辞典および履歴バッファの内容と比
較することを続ける。こうして本方法は、辞典内または
履歴バッファ内で複製されている、許容される最長の文
字列を形成する。この最長の文字列は、トークンから最
後の文字を除いたものである。本開示では、１個のリテ
ラルを列であると見なす。
本発明の圧縮方法は、許容される最長の列を形成し終え
た後に、その列を象徴する参照を発行する。判断ブロッ
ク25でMATCHが辞典形式であった場合は、ブロック27
で、MATCHによって指定された辞典参照が出力または発
行される。MATCHが辞典形式ではない場合は、履歴形式
またはリテラル形式のいずれかである。判断ブロック29
でMATCHが履歴形式であった場合は、ブロック31で、MAT
CHによって指定された履歴参照が発行または出力され
る。また、MATCHが履歴形式であった場合は、履歴参照
によって指定された参照列が辞典に追加され、辞典のサ
イズが記録される。
た後に、その列を象徴する参照を発行する。判断ブロッ
ク25でMATCHが辞典形式であった場合は、ブロック27
で、MATCHによって指定された辞典参照が出力または発
行される。MATCHが辞典形式ではない場合は、履歴形式
またはリテラル形式のいずれかである。判断ブロック29
でMATCHが履歴形式であった場合は、ブロック31で、MAT
CHによって指定された履歴参照が発行または出力され
る。また、MATCHが履歴形式であった場合は、履歴参照
によって指定された参照列が辞典に追加され、辞典のサ
イズが記録される。
MATCHが履歴形式ではない場合、それはリテラル形式で
ある。ブロック33で、トークン内の記号に対するリテラ
ル参照が発行または出力される。辞典参照、履歴参照ま
たはリテラル参照が発行された後、ブロック35で、参照
列が履歴バッファに付加され、トークンの先頭から削除
される。同時に、履歴バッファのサイズが記録される。
次に、トークンはブロック13に戻り、入力記号列が終り
になるまでこの処理を続ける。
ある。ブロック33で、トークン内の記号に対するリテラ
ル参照が発行または出力される。辞典参照、履歴参照ま
たはリテラル参照が発行された後、ブロック35で、参照
列が履歴バッファに付加され、トークンの先頭から削除
される。同時に、履歴バッファのサイズが記録される。
次に、トークンはブロック13に戻り、入力記号列が終り
になるまでこの処理を続ける。
代表的なデータ・ストリームの確率論的研究に基づい
て、下記の符号化方式が最適に近い結果を生むことが判
明した。
て、下記の符号化方式が最適に近い結果を生むことが判
明した。
リテラル参照 ０＋「記号」 履歴参照 １＋０＋「オフセット」＋「長さ」 辞典参照 １＋１＋「指標」 “1"および“0"は２進数の１桁を表し、「オフセッ
ト」、「長さ」および「指標」は、特定の場合にそれら
の潜在的な最大値を表すのに必要な最小のビット数で符
号化されている。より具体的には、必要なビット数は、
潜在的な最大値を最も近い２の累乗に切り上げた値の、
２の底とする対数に等しい。たとえば、辞典が12個のエ
ントリを含む場合、12は16（次の２の累乗）に切り上げ
られ、16の２を底とする対数は４なので、指標を符号化
するのに必要なビット数は４である。「記号」は記号自
体の８ビット表現である。
ト」、「長さ」および「指標」は、特定の場合にそれら
の潜在的な最大値を表すのに必要な最小のビット数で符
号化されている。より具体的には、必要なビット数は、
潜在的な最大値を最も近い２の累乗に切り上げた値の、
２の底とする対数に等しい。たとえば、辞典が12個のエ
ントリを含む場合、12は16（次の２の累乗）に切り上げ
られ、16の２を底とする対数は４なので、指標を符号化
するのに必要なビット数は４である。「記号」は記号自
体の８ビット表現である。
本発明の圧縮機能に入るデータは、８ビット・バイトと
して処理されるが、圧縮機能から出力されるデータは自
由形式のビット・ストリームである。前述のリテラル参
照、履歴参照および辞典参照に対する符号化規則によ
り、復元機能でこの自由形式のビット・ストリームを容
易にかつ曖昧さなしに解析することが可能となる。
して処理されるが、圧縮機能から出力されるデータは自
由形式のビット・ストリームである。前述のリテラル参
照、履歴参照および辞典参照に対する符号化規則によ
り、復元機能でこの自由形式のビット・ストリームを容
易にかつ曖昧さなしに解析することが可能となる。
典型的なアプリケーション環境では、各リテラル記号を
符号化するのに必要なビット数は、圧縮機能と復元機能
とを相互接続するシリアル通信チャネルの基本ブロック
・サイズに等しくなる。たとえば、EBCDIC環境では、記
号の値は８ビットを用いて符号化され、代表的な通信リ
ンク上を流れる基本的情報単位は、８ビット文字に量子
化される。リテラル参照を符号化するのに必要なビット
数は、常にこのようなリンクの基本ブロック・サイズよ
りも１だけ大きいので、最後のデータ・ブロック内に利
用可能な追加ビットが存在する場合は、最後の有効な参
照の末尾に１個の０ビットを追加することによって、最
後の有効な文字の末尾の後ろの使用されていないビット
を復元機能に強制的に無視させることが常に可能であ
る。０ビットを用いてリテラル参照の先頭を模倣するこ
とにより、圧縮されたデータ・ストリームが次のブロッ
ク境界で打ち切られたためにその参照が完了できないこ
とを知った復元機能は、最後のデータ・ブロック内の余
分なビットを自動的に無視する。言い換えれば、復元機
能は０ビットを「見る」と、８ビット・リテラルを得る
ことを期待する。０ビットの後に何も続かない場合、復
元機能はそのシーケンスが完了したことを「知る」。
符号化するのに必要なビット数は、圧縮機能と復元機能
とを相互接続するシリアル通信チャネルの基本ブロック
・サイズに等しくなる。たとえば、EBCDIC環境では、記
号の値は８ビットを用いて符号化され、代表的な通信リ
ンク上を流れる基本的情報単位は、８ビット文字に量子
化される。リテラル参照を符号化するのに必要なビット
数は、常にこのようなリンクの基本ブロック・サイズよ
りも１だけ大きいので、最後のデータ・ブロック内に利
用可能な追加ビットが存在する場合は、最後の有効な参
照の末尾に１個の０ビットを追加することによって、最
後の有効な文字の末尾の後ろの使用されていないビット
を復元機能に強制的に無視させることが常に可能であ
る。０ビットを用いてリテラル参照の先頭を模倣するこ
とにより、圧縮されたデータ・ストリームが次のブロッ
ク境界で打ち切られたためにその参照が完了できないこ
とを知った復元機能は、最後のデータ・ブロック内の余
分なビットを自動的に無視する。言い換えれば、復元機
能は０ビットを「見る」と、８ビット・リテラルを得る
ことを期待する。０ビットの後に何も続かない場合、復
元機能はそのシーケンスが完了したことを「知る」。
第２図には、本発明の復元方法の流れ図が示されてい
る。最初のステップであるブロック37で、履歴バッファ
および辞典をクリアする。履歴バッファと辞典がクリア
された後、ブロック39で、入力から参照が読み取られ、
それに従ってMATCHがセットされる。参照の第１ビット
が０である場合、MATCHはリテラル形式である。参照の
第１ビットが１である場合、MATCHは辞典形式または履
歴形式のいずれかである。１に続くビットが０である場
合、MATCHは履歴形式である。１に続くビットが１であ
る場合、MATCHは辞典形式である。
る。最初のステップであるブロック37で、履歴バッファ
および辞典をクリアする。履歴バッファと辞典がクリア
された後、ブロック39で、入力から参照が読み取られ、
それに従ってMATCHがセットされる。参照の第１ビット
が０である場合、MATCHはリテラル形式である。参照の
第１ビットが１である場合、MATCHは辞典形式または履
歴形式のいずれかである。１に続くビットが０である場
合、MATCHは履歴形式である。１に続くビットが１であ
る場合、MATCHは辞典形式である。
判断ブロック41でMATCHが辞典形式であった場合、ブロ
ック43で、MATCHによって指定された辞典の列が出力さ
れる。
ック43で、MATCHによって指定された辞典の列が出力さ
れる。
MATCHが辞典形式ではない場合、判断ブロック45でMATCH
が履歴形式であった場合は、ブロック47で、MATCHによ
って指定された履歴列を出力し、その列を辞典に追加
し、現在の辞典のエントリ数を記録する。MATCHが辞典
形式でも履歴形式でもない場合は、ブロック49で、MATC
Hによって指定されたリテラル記号が出力される。最後
に、ブロック43、47または49でMATCHによって指定され
た列を出力した後に、ブロック51で、その列を履歴バッ
ファに付加し、現在の履歴バッファのサイズを記録し
て、入力列が終りになるまでこの処理を繰り返す。
が履歴形式であった場合は、ブロック47で、MATCHによ
って指定された履歴列を出力し、その列を辞典に追加
し、現在の辞典のエントリ数を記録する。MATCHが辞典
形式でも履歴形式でもない場合は、ブロック49で、MATC
Hによって指定されたリテラル記号が出力される。最後
に、ブロック43、47または49でMATCHによって指定され
た列を出力した後に、ブロック51で、その列を履歴バッ
ファに付加し、現在の履歴バッファのサイズを記録し
て、入力列が終りになるまでこの処理を繰り返す。
当初は、復元機能の辞典と履歴バッファは空である。し
かし、復元機能が受け取る最初の参照はリテラル形式で
ある。リテラル参照を処理する際には、これを履歴バッ
ファに追加する。復元機能は、その履歴バッファ内で一
致を見つけると、履歴参照を発行する。圧縮機能と復元
機能の履歴バッファは同一であるため、履歴参照は復元
機能の履歴バッファ内の正しい記号列を識別する。圧縮
機能が履歴参照を発行し、復元機能がそれを受け取る
と、その履歴参照によって参照される列が、圧縮機能お
よび復元機能の当該の辞典に挿入される。
かし、復元機能が受け取る最初の参照はリテラル形式で
ある。リテラル参照を処理する際には、これを履歴バッ
ファに追加する。復元機能は、その履歴バッファ内で一
致を見つけると、履歴参照を発行する。圧縮機能と復元
機能の履歴バッファは同一であるため、履歴参照は復元
機能の履歴バッファ内の正しい記号列を識別する。圧縮
機能が履歴参照を発行し、復元機能がそれを受け取る
と、その履歴参照によって参照される列が、圧縮機能お
よび復元機能の当該の辞典に挿入される。
本発明の方法は、このように２つのデータ構造すなわち
履歴バッファおよび辞典を使用して、データ列の効率的
な圧縮を達成する。履歴バッファを固定された深さに制
限し、履歴参照の最大長を相対的に小さな値に制限し、
辞典内のエントリの最大数を固定した数に制限すること
により、極めて効率的にメモリを利用し、ずっと大量の
メモリを必要とする方法に匹敵する圧縮比をもたらす、
相互に関連した１組のデータ構造を設計することが可能
である。
履歴バッファおよび辞典を使用して、データ列の効率的
な圧縮を達成する。履歴バッファを固定された深さに制
限し、履歴参照の最大長を相対的に小さな値に制限し、
辞典内のエントリの最大数を固定した数に制限すること
により、極めて効率的にメモリを利用し、ずっと大量の
メモリを必要とする方法に匹敵する圧縮比をもたらす、
相互に関連した１組のデータ構造を設計することが可能
である。
E.発明の効果 本発明によれば、従来のレンペル−ジブ・アルゴリズム
よりもデータ圧縮の効率を向上させることができる。
よりもデータ圧縮の効率を向上させることができる。
第１図は、本発明の圧縮方法を示す流れ図である。 第２図は、本発明の復元方法を示す流れ図である。
フロントページの続き (56)参考文献 特開 平１−132222（ＪＰ，Ａ) 特開 平３−204232（ＪＰ，Ａ) 特開 平３−204234（ＪＰ，Ａ) 特開 平３−68219（ＪＰ，Ａ) 特公 昭63−56726（ＪＰ，Ｂ２) 特公 平５−68893（ＪＰ，Ｂ２) 特公 平２−6252（ＪＰ，Ｂ２) 米国特許5010345（ＵＳ，Ａ) 米国特許4814746（ＵＳ，Ａ) 米国特許4558302（ＵＳ，Ａ) 米国特許4843389（ＵＳ，Ａ) 米国特許4847619（ＵＳ，Ａ) 米国特許5184126（ＵＳ，Ａ) 米国特許5001478（ＵＳ，Ａ) 米国特許5003307（ＵＳ，Ａ) 米国特許5016009（ＵＳ，Ａ) 欧州特許出願公開438955（ＥＰ，Ａ) 欧州特許出願公開438956（ＥＰ，Ａ) 欧州特許出願公開435802（ＥＰ，Ａ) Ｊ．Ｚｉｖ，Ａ．Ｌｅｍｐｅｌ，“Ａ Ｕｎｉｖｅｒｓａｌ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｓｅｑｕｅｎｔｉａｌ Ｄａｔ ａ Ｃｏｍｐｒｅｓｓｉｏｎ”，ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ｉｎｆｏｒｍ．Ｔｈ ｅｏｒｙ，ｖｏｌ．ＩＴ−23，Ｎｏ．３, ＰＰ．337−349，Ｍａｙ 1977
Claims (15)
- 【請求項１】信号のシーケンスからなるデータを圧縮す
るデータ圧縮方法であって、 前記シーケンスの信号を固定長の履歴バッファに記録す
るステップと、 前記シーケンスからの信号列が前記履歴バッファ内に複
製されているとき、履歴参照を発行するステップと、 履歴参照によって発行された信号列を辞典内に記録する
ステップと、 前記シーケンスからの信号列が前記辞典内に複製されて
いるとき、辞典参照を発行するステップと を含むデータ圧縮方法。 - 【請求項２】前記履歴バッファの長さが、前記シーケン
スの長さより短いことを特徴とする請求項１記載のデー
タ圧縮方法。 - 【請求項３】前記辞典が固定したサイズを有することを
特徴とする請求項１記載のデータ圧縮方法。 - 【請求項４】前記シーケンスの信号が前記履歴バッファ
および辞典のいずれにも複製されていないとき、リテラ
ル参照を発行するステップを含む請求項１記載のデータ
圧縮方法。 - 【請求項５】前記辞典または前記履歴バッファのいずれ
かに複製される最長の信号列を形成するステップを含む
請求項１記載のデータ圧縮方法。 - 【請求項６】前記最長の記号列が、事前に選択された履
歴参照の最大長以下であることを特徴とする請求項５記
載のデータ圧縮方法。 - 【請求項７】前記形成ステップが、 トークンを形成するステップと、 前記トークンが前記辞典および前記履歴バッファのいず
れにも複製されていない状態になるまで、前記トークン
に前記シーケンスからの信号を順次付加するステップと を含む請求項５記載のデータ圧縮方法。 - 【請求項８】前記トークンに記号を順次付加する前記ス
テップが、 （ａ）前記トークンに１の記号を付加するステップと、 （ｂ）前記トークンを前記辞典の内容と比較するステッ
プと、 （ｃ）前記トークンが前記辞典内に複製されている場合
に、前記トークンに次の記号を付加するステップと、 （ｄ）前記トークンが前記辞書内に複製されていない状
態になるまで、ステップ（ｂ）及び（ｃ）を繰り返すス
テップと、 （ｅ）前記トークンを履歴バッファの内容と比較するス
テップと、 （ｆ）前記トークンが前記履歴バッファ内に複製されて
いる場合に、前記トークンに次の記号を付加するステッ
プと、 （ｇ）前記トークンが前記履歴バッファ内に複製されて
いない状態になるまで、ステップ（ｂ）乃至（ｆ）を繰
り返すステップと を含む請求項７記載のデータ圧縮方法。 - 【請求項９】前記トークンが事前に選択された履歴参照
の最大長以下である限り、ステップ（ｂ）乃至（ｆ）を
繰り返すステップを含む請求項８記載のデータ圧縮方
法。 - 【請求項１０】前記辞典が当初空であることを特徴とす
る請求項１記載のデータ圧縮方法。 - 【請求項１１】記号のシーケンスからなるデータを圧縮
するデータ圧縮方法であって、 （ａ）前記トークンが辞典内または履歴バッファ内のい
ずれにも複製されていない状態になるまで前記トークン
に記号を順次付加し、それによって辞典内または履歴バ
ッファ内のいずれかに複製され得る最長の参照列を形成
するステップと、 （ｂ）前記参照列が前記辞典内に複製されているときに
は、前記参照列を表す辞典参照を発行するステップと、 （ｃ）前記参照列が前記履歴バッファ内に複製されてい
るときには、前記参照列を表す履歴参照を発行するステ
ップと、 （ｄ）前記参照列が前記履歴バッファ内および前記辞典
のいずれにも複製されていないときには、リテラル参照
を発行するステップと、 （ｅ）ステップ（ｃ）において発行された履歴参照によ
って表される参照列を前記辞典に追加するステップと、 （ｆ）ステップ（ｂ）、（ｃ）又は（ｄ）で発行された
前記参照によって表される参照列を前記履歴バッファに
追加するステップと、 （ｇ）発行された前記参照によって表される参照列をト
ークンから削除するステップと、 （ｈ）前記記号のシーケンスが終わりになるまで、ステ
ップ（ａ）ないし（ｇ）を繰り返すステップと を含むデータ圧縮方法。 - 【請求項１２】前記履歴バッファが固定したサイズを有
することを特徴とする請求項11記載のデータ圧縮方法。 - 【請求項１３】前記トークンに記号を順次付加するステ
ップ（請求項11の（ａ））が、 （ａ）前記トークンに１の記号を付加するステップと、 （ｂ）前記トークンを前記辞典の内容と比較するステッ
プと、 （ｃ）前記トークンが前記辞典内に複製されている場合
に、前記トークンに次の記号を付加するステップと、 （ｄ）前記トークンが前記辞書内に複製されていない状
態になるまで、ステップ（ｂ）及び（ｃ）を繰り返すス
テップと、 （ｅ）前記トークンを履歴バッファの内容と比較するス
テップと、 （ｆ）前記トークンが前記履歴バッファ内に複製されて
いる場合に、前記トークンに次の記号を付加するステッ
プと、 （ｇ）前記トークンが前記履歴バッファ内に複製されて
いない状態になるまで、ステップ（ｂ）乃至（ｆ）を繰
り返すステップと を含む請求項11記載の圧縮方法。 - 【請求項１４】前記トークンが事前に選択された履歴参
照の最大長以下である限り、ステップ（ｂ）乃至（ｆ）
を繰り返すステップを含む請求項８記載のデータ圧縮方
法。 - 【請求項１５】記号のシーケンスからなるデータを圧縮
するデータ圧縮方法であって、 （ａ）トークン、固定した深さをもつ履歴バッファ、お
よび固定した数の利用可能エントリを有する辞典を形成
するステップと、 （ｂ）前記トークン、履歴バッファ、および辞典をクリ
アするステップと、 （ｃ）前記トークンに記号を１つ付加するステップと、 （ｄ）前記トークンを前記辞典の内容と比較するステッ
プと、 （ｅ）前記トークンが前記辞典内に複製されている場合
に、前記トークンに次の記号を付加するステップと、 （ｆ）前記トークンが事前に選択された履歴参照の最大
長以下である限り、前記トークンが前記辞典内に複製さ
れていない状態になるまで、ステップ（ｄ）および
（ｅ）を繰り返すステップと、 （ｇ）前記トークンを前記履歴バッファの内容と比較す
るステップと、 （ｈ）前記トークンが前記履歴バッファ内に複製されて
いる場合に、前記トークンに次の記号を付加するステッ
プと、 （ｉ）前記トークンが前記事前に選択された履歴参照の
最大長以下である限り、前記トークンが前記履歴バッフ
ァ内に複製されていない状態になるまで、ステップ
（ｄ）ないし（ｈ）を繰り返し、それによって前記履歴
バッファまたは前記辞典内で一致を見つけるステップ
と、 （ｊ）前記辞典内で一致が見つかった場合に、辞典参照
を発行するステップと、 （ｋ）前記履歴バッファ内で一致が見つかった場合に、
履歴参照を発行するステップと、 （ｌ）前記履歴バッファおよび前記辞典のいずれでも一
致が見つからなかった場合に、リテラル参照を発行する
ステップと、 （ｍ）ステップ（ｋ）で発行された履歴参照列を前記辞
典に追加するステップと、 （ｎ）ステップ（ｊ）、（ｋ）または（ｌ）で発行され
た参照列を前記履歴バッファに追加するステップと、 （ｏ）発行された前記参照によって表される参照列をト
ークンから削除するステップと、 （ｐ）記号のシーケンスが終わりになるまで、ステップ
（ｃ）ないし（ｏ）を繰り返すステップと を含むデータ圧縮方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US458119 | 1989-12-28 | ||
| US07/458,119 US5010345A (en) | 1989-12-28 | 1989-12-28 | Data compression method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH03204233A JPH03204233A (ja) | 1991-09-05 |
| JPH0779263B2 true JPH0779263B2 (ja) | 1995-08-23 |
Family
ID=23819442
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2313008A Expired - Lifetime JPH0779263B2 (ja) | 1989-12-28 | 1990-11-20 | データ圧縮方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5010345A (ja) |
| EP (1) | EP0438955B1 (ja) |
| JP (1) | JPH0779263B2 (ja) |
| DE (1) | DE69026924T2 (ja) |
Families Citing this family (26)
| 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 |
| NL9001368A (nl) * | 1990-06-15 | 1992-01-02 | Tel Developments B V | Beveiliging van voorwerpen of dokumenten. |
| US5151697A (en) * | 1990-10-15 | 1992-09-29 | Board Of Regents Of The University Of Washington | Data structure management tagging system |
| US5142282A (en) * | 1990-11-07 | 1992-08-25 | Hewlett-Packard Company | Data compression dictionary access minimization |
| US6092070A (en) * | 1992-02-11 | 2000-07-18 | Telcordia Technologies, Inc. | Method and system for lossless date compression and fast recursive expansion |
| US5396595A (en) * | 1992-04-24 | 1995-03-07 | Spacelabs Medical, Inc. | Method and system for compression and decompression of data |
| US5323155A (en) * | 1992-12-04 | 1994-06-21 | International Business Machines Corporation | Semi-static data compression/expansion method |
| US5467087A (en) * | 1992-12-18 | 1995-11-14 | Apple Computer, Inc. | High speed lossless data compression system |
| US5455576A (en) * | 1992-12-23 | 1995-10-03 | Hewlett Packard Corporation | Apparatus and methods for Lempel Ziv data compression with improved management of multiple dictionaries in content addressable memory |
| US5640551A (en) * | 1993-04-14 | 1997-06-17 | Apple Computer, Inc. | Efficient high speed trie search process |
| US5384568A (en) * | 1993-12-02 | 1995-01-24 | Bell Communications Research, Inc. | Data compression |
| US5502439A (en) * | 1994-05-16 | 1996-03-26 | The United States Of America As Represented By The United States Department Of Energy | Method for compression of binary data |
| US5635932A (en) * | 1994-10-17 | 1997-06-03 | Fujitsu Limited | Lempel-ziv compression with expulsion of dictionary buffer matches |
| US6154569A (en) * | 1995-03-16 | 2000-11-28 | Kabushiki Kaisha Toshiba | System and method for coding and/or decoding image including bit-map of different levels |
| US5970177A (en) * | 1995-06-07 | 1999-10-19 | America Online, Inc. | Data compression using selective encoding |
| US5694125A (en) * | 1995-08-02 | 1997-12-02 | Advance Hardware Architecture | Sliding window with big gap data compression system |
| JP3273119B2 (ja) * | 1995-09-29 | 2002-04-08 | 京セラ株式会社 | データ圧縮・伸長装置 |
| 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 |
| US5805086A (en) * | 1995-10-10 | 1998-09-08 | International Business Machines Corporation | Method and system for compressing data that facilitates high-speed data decompression |
| US6012062A (en) * | 1996-03-04 | 2000-01-04 | Lucent Technologies Inc. | System for compression and buffering of a data stream with data extraction requirements |
| US6535886B1 (en) * | 1999-10-18 | 2003-03-18 | Sony Corporation | Method to compress linguistic structures |
| EP1354411A1 (en) * | 2001-01-11 | 2003-10-22 | Koninklijke Philips Electronics N.V. | Data compression method with identifier of regressive string reference |
| JP4667108B2 (ja) * | 2005-04-11 | 2011-04-06 | パナソニック株式会社 | データ処理装置 |
| US7982636B2 (en) * | 2009-08-20 | 2011-07-19 | International Business Machines Corporation | Data compression using a nested hierachy of fixed phrase length static and dynamic dictionaries |
Citations (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4558302A (en) | 1983-06-20 | 1985-12-10 | Sperry Corporation | High speed data compression and decompression apparatus and method |
| US4814746A (en) | 1983-06-01 | 1989-03-21 | International Business Machines Corporation | Data compression method |
| US4843389A (en) | 1986-12-04 | 1989-06-27 | International Business Machines Corp. | Text compression and expansion method and apparatus |
| US4847619A (en) | 1987-10-19 | 1989-07-11 | Hewlett-Packard Company | Performance-based reset of data compression dictionary |
| US5001478A (en) | 1989-12-28 | 1991-03-19 | International Business Machines Corporation | Method of encoding compressed data |
| US5003307A (en) | 1989-01-13 | 1991-03-26 | Stac, Inc. | Data compression apparatus with shift register search means |
| US5010345A (en) | 1989-12-28 | 1991-04-23 | International Business Machines Corporation | Data compression method |
| 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 |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59231683A (ja) * | 1983-06-01 | 1984-12-26 | インタ−ナシヨナル ビジネス マシ−ンズ コ−ポレ−シヨン | データ圧縮方法 |
| 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 |
| JPS6413222A (en) * | 1987-07-07 | 1989-01-18 | Kubota Ltd | Magnetic recording medium |
| US4876541A (en) * | 1987-10-15 | 1989-10-24 | Data Compression Corporation | Stem for dynamically compressing and decompressing electronic data |
| US4881075A (en) * | 1987-10-15 | 1989-11-14 | Digital Equipment Corporation | Method and apparatus for adaptive data compression |
| US4906991A (en) * | 1988-04-29 | 1990-03-06 | Xerox Corporation | Textual substitution data compression with finite length search windows |
-
1989
- 1989-12-28 US US07/458,119 patent/US5010345A/en not_active Expired - Fee Related
-
1990
- 1990-10-31 DE DE69026924T patent/DE69026924T2/de not_active Expired - Fee Related
- 1990-10-31 EP EP90480179A patent/EP0438955B1/en not_active Expired - Lifetime
- 1990-11-20 JP JP2313008A patent/JPH0779263B2/ja not_active Expired - Lifetime
Patent Citations (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4814746A (en) | 1983-06-01 | 1989-03-21 | International Business Machines Corporation | Data compression method |
| US4558302A (en) | 1983-06-20 | 1985-12-10 | Sperry Corporation | High speed data compression and decompression apparatus and method |
| US4558302B1 (ja) | 1983-06-20 | 1994-01-04 | Unisys Corp | |
| US4843389A (en) | 1986-12-04 | 1989-06-27 | International Business Machines Corp. | Text compression and expansion method and apparatus |
| US4847619A (en) | 1987-10-19 | 1989-07-11 | Hewlett-Packard Company | Performance-based reset of data compression dictionary |
| 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 |
| 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 |
| US5184126A (en) | 1989-12-28 | 1993-02-02 | International Business Machines Corporation | Method of decompressing compressed data |
Non-Patent Citations (1)
| Title |
|---|
| Ｊ．Ｚｉｖ，Ａ．Ｌｅｍｐｅｌ，"ＡＵｎｉｖｅｒｓａｌＡｌｇｏｒｉｔｈｍｆｏｒＳｅｑｕｅｎｔｉａｌＤａｔａＣｏｍｐｒｅｓｓｉｏｎ"，ＩＥＥＥＴｒａｎｓ．ｏｎＩｎｆｏｒｍ．Ｔｈｅｏｒｙ，ｖｏｌ．ＩＴ−２３，Ｎｏ．３，ＰＰ．３３７−３４９，Ｍａｙ１９７７ |
Also Published As
| Publication number | Publication date |
|---|---|
| DE69026924D1 (de) | 1996-06-13 |
| JPH03204233A (ja) | 1991-09-05 |
| DE69026924T2 (de) | 1996-11-21 |
| EP0438955A1 (en) | 1991-07-31 |
| US5010345A (en) | 1991-04-23 |
| EP0438955B1 (en) | 1996-05-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0779262B2 (ja) | 圧縮データの符号化方法 | |
| JPH0779263B2 (ja) | データ圧縮方法 | |
| JP3006766B2 (ja) | 圧縮された状態におけるデータをエンコードし、デコードし、伝送する方法と装置 | |
| Bell | Better OPM/L text compression | |
| JP3273119B2 (ja) | データ圧縮・伸長装置 | |
| Deutsch | Rfc1951: Deflate compressed data format specification version 1.3 | |
| AU637826B2 (en) | Improved data compression apparatus | |
| US5970177A (en) | Data compression using selective encoding | |
| Yamaguchi et al. | An efficient method for compressing test data | |
| JPS6217418B2 (ja) | ||
| US6247015B1 (en) | Method and system for compressing files utilizing a dictionary array | |
| JPS6356726B2 (ja) | ||
| JPH0779264B2 (ja) | 圧縮データ復元方法 | |
| JPH0779265B2 (ja) | 圧縮データの復号方法 | |
| US5815096A (en) | Method for compressing sequential data into compression symbols using double-indirect indexing into a dictionary data structure | |
| US7253752B2 (en) | Coding apparatus, decoding apparatus, coding method, decoding method and program | |
| JPS6345131B2 (ja) | ||
| Anisimov et al. | Practical Word-based Text Compression Using the Reverse Multi-Delimiter Codes. | |
| JP2590287B2 (ja) | データ圧縮方法およびデータ圧縮装置 | |
| JPH08116269A (ja) | データ処理装置及びデータ処理方法 | |
| CN117200805B (zh) | 一种mcu的低内存占用的压缩和解压方法及装置 | |
| JP2025139901A (ja) | ストレージシステム | |
| JPH06149537A (ja) | データ圧縮方法及び復元方法 | |
| JPS6394366A (ja) | 英語文書圧縮装置 | |
| Ong | A multi-block data compression method based on arithmetic coding for a library database |