JPH11145848A - 改善されたデータ圧縮効率を提供する方法及び事前圧縮器 - Google Patents

改善されたデータ圧縮効率を提供する方法及び事前圧縮器

Info

Publication number
JPH11145848A
JPH11145848A JP10228812A JP22881298A JPH11145848A JP H11145848 A JPH11145848 A JP H11145848A JP 10228812 A JP10228812 A JP 10228812A JP 22881298 A JP22881298 A JP 22881298A JP H11145848 A JPH11145848 A JP H11145848A
Authority
JP
Japan
Prior art keywords
data
byte
data byte
run
counter
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
Application number
JP10228812A
Other languages
English (en)
Other versions
JP3065585B2 (ja
Inventor
David John Craft
デビット・ジョン・クラフト
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH11145848A publication Critical patent/JPH11145848A/ja
Application granted granted Critical
Publication of JP3065585B2 publication Critical patent/JP3065585B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

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/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • 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
    • 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/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

(57)【要約】 【課題】 データを圧縮するための改善された方法及び
装置を提供すること。 【解決手段】 データ圧縮器に、改善されたデータ圧縮
効率を提供するための方法が開示される。非圧縮データ
・ストリームをデータ圧縮ユニットに送信する前に、非
圧縮データ・ストリームからの入来データ・バイトが、
最初に非圧縮データ・ストリームからの先行データ・バ
イトと比較される。入来データ・バイトと先行データ・
バイトとの一致に応答して、第１のカウンタ値が増分さ
れる。第１のカウンタ値が事前設定値に達した後、入来
データ・バイトとその先行データ・バイトとの続く一致
に応答して、第２のカウンタ値が増分される。入来デー
タ・バイトのランの完了時に、そのラン部分の代わり
に、第２のカウンタ値が最終的にデータ圧縮ユニットに
送信される。それによりデータ圧縮ユニットは、非圧縮
データ・ストリーム内におけるランの発生後、迅速にそ
の最適な圧縮率を再開することができる。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は一般に、データを圧
縮する方法及び装置に関し、特に、適応データ圧縮を実
行する方法及び装置に関する。更に詳細には、本発明は
適応データ圧縮器のための改善されたデータ圧縮効率を
提供する方法及び装置に関する。
【０００２】
【従来の技術】圧縮のために圧縮アルゴリズムに提供さ
れるデータのタイプは、非常に変化し得る。従って、大
抵の圧縮アルゴリズムは、広い範囲のデータ・タイプに
渡り、優れた圧縮性能を達成するために、事実上適応型
である。従来のLempel-Ziv1（ＬＺ＿１）及びLempel-Zi
v2（ＬＺ＿２）圧縮アルゴリズムは、この概念をある程
度実現する。
【０００３】ＬＺ＿１では、処理されるあらゆるバイト
が、初期には空の履歴バッファに移動される。この履歴
バッファはバイト幅シフト・レジスタと見なされ、一旦
履歴バッファが完全に充填されると、各新たな入来バイ
トが最も古いデータ・バイトを履歴バッファから追い出
す。履歴バッファ内の現内容が入来データと比較され、
まだ履歴バッファ内に留まる以前に発生した入来データ
・バイトのマッチング・ストリングまたはシーケンスが
識別される。この入来データ・シーケンスが次に、履歴
バッファ内のマッチング・ストリングの開始ポイント、
及びマッチング・ストリングの長さを提供するより小さ
な形式に符号化され、このことがＬＺ＿１圧縮アルゴリ
ズムの基本を構成する。ＬＺ＿１伸張器は、ＬＺ＿１圧
縮器内の履歴バッファと同一のデータ履歴を有する履歴
バッファを保持し、参照を復号するとき、単にこうした
ストリングをその出力として複写する。
【０００４】ＬＺ＿２では、データ・シーケンスの辞書
が保持され、これらの辞書入力の参照がＬＺ＿２圧縮ア
ルゴリズムの基本を構成する。入来データが辞書入力の
１つに合致するとき、長さを符号化する必要はない。な
ぜなら、長さも辞書内に保持されるからである。従っ
て、ＬＺ＿２圧縮アルゴリズムからの圧縮された出力デ
ータは、通常、辞書入力を表す数字のシーケンスを含む
だけである。適応ＬＺ＿２技法は、入来データにもとづ
き連続的に新たな辞書入力を追加する。ＬＺ＿１の場合
同様、ＬＺ＿２圧縮器及びＬＺ＿２伸張器の両者は、同
一の構造で始まり、同一の構造を保持するが、ＬＺ＿２
の場合には、辞書がフルになるとき、異なる管理方法が
使用される。
【０００５】通常、圧縮データ・ストリームは、一般
に"ラン（runs）"として知られる同一の文字のシーケン
スを含むことが、しばしば見い出される。例えば、実行
可能コードは、しばしば、"00"文字の相当量のランを含
む。また、コード・コンパイラは、しばしば、行列また
は変数を既知の状態に初期化するために、ヌル・データ
を生成する。更に、データベース・ソフトウェアは、し
ばしば、全て空白または全て０の文字を有するデータ・
フィールドを割当てる。更にバイナリ・ビットマップ・
イメージ・データは、しばしば、全て空白の８画素を表
す大量の"空白（whitespace）"（通常"00"文字）を含
む。その他に、特に１画素当たり１バイトにより符号化
されるグレイ・スケールまたはカラー・イメージ・デー
タは、同一データ・バイトの長いランを含み得る。
【０００６】これらの種類のランは、データ圧縮器内に
おいて、不要で非生産的な適応化をもたらし得る。更
に、ＬＺ＿１の履歴バッファまたはＬＺ＿２の辞書は、
ランからの同一データ・バイトにより容易にオーバフロ
ーし得るので、データ圧縮器がランの後にその最適な圧
縮率を再開するには、しばらくの時間がかかる。結果的
に、データ圧縮器がランの発生後、その最適な圧縮効率
をより迅速に再開できるように、より優れたデータ圧縮
効率をデータ圧縮器に提供する方法及び装置を提供する
ことが望まれる。
【０００７】
【発明が解決しようとする課題】従って、本発明の目的
は、データを圧縮するための改善された方法及び装置を
提供することにある。
【０００８】本発明の別の目的は、適応データ圧縮を実
行する改善された方法及び装置を提供することにある。
【０００９】更に本発明の別の目的は、適応データ圧縮
器のためのより優れたデータ圧縮効率を提供する改善さ
れた方法及び装置を提供することにある。
【００１０】
【課題を解決するための手段】本発明の方法によれば、
非圧縮データ・ストリームがデータ圧縮ユニットに送信
される。しかしながら、非圧縮データ・ストリームをデ
ータ圧縮ユニットに送信する前に、非圧縮データ・スト
リームからの入来データ・バイトが、最初に非圧縮デー
タ・ストリームからの先行データ・バイトと比較され
る。入来データ・バイトと先行データ・バイトとの一致
に応答して、第１のカウンタ値が増分される。第１のカ
ウンタ値が事前設定値に達した後、入来データ・バイト
とその先行データ・バイトとの続く一致に応答して、第
２のカウンタ値が増分される。入来データ・バイトのラ
ンの完了時にそのラン部分の代わりに、第２のカウンタ
値が最終的にデータ圧縮ユニットに送信される。それに
よりデータ圧縮ユニットは、非圧縮データ・ストリーム
内におけるランの発生後、迅速にその最適な圧縮率を再
開することができる。
【００１１】
【発明の実施の形態】本発明はLempel-Ziv1及びLempel-
Ziv2などの、たくさんのタイプの適応データ圧縮アルゴ
リズムと共に実現され得る。当業者であれば、本発明が
ハードウェアまたはソフトウェアのいずれかにより実現
され得ることが理解できよう。
【００１２】Ｉ．符号器及び復号器 図１を参照すると、本発明の好適な実施例が組み込まれ
得るデータ圧縮ユニットのブロック図が示される。図示
のように、圧縮ユニット１０は、制御装置１１及びラン
ダム・アクセス・メモリ（ＲＡＭ）または連想記憶装置
（ＣＡＭ）１２に接続される。任意のタイプの圧縮アル
ゴリズムが圧縮ユニット１０内で実現され得る。適応圧
縮アルゴリズムの例には、当業者には周知のLempel-Ziv
1及びLempel-Ziv2などの従来のアルゴリズム、または適
応無損失データ圧縮（ＡＬＤＣ：Adaptive Lossless Da
ta Compression）などの、より現代的なアルゴリズムが
含まれる。ＡＬＤＣについては、"QIC Development Sta
ndard QIC-154"、Rev．A、10 Mar 94、Quarter-Inch Ca
rtridge Drive Standards、nc．で詳細に述べられてい
る。Lempel-Ziv1の履歴バッファ或いはLempel-Ziv2の辞
書などの選択される圧縮アルゴリズムに関連付けられる
全てのデータ構造が、ＲＡＭ／ＣＡＭ１２内に保持され
る。それ自体、ＲＡＭ／ＣＡＭ１２の最適サイズは、圧
縮ユニット１０内で使用される圧縮アルゴリズムのタイ
プに依存する。動作中、最初に非圧縮データ・ストリー
ムが圧縮ユニット１０により、データ送信装置１３から
受信される。データ符号化の後、圧縮されたデータ・ス
トリームが、次にデータ受信装置１４に伝送される。
【００１３】図２を参照すると、本発明の好適な実施例
が組み込まれ得るデータ伸張ユニットのブロック図が示
される。図示のように、伸張ユニット１５は制御装置１
６及びＲＡＭ１７に接続される。ＲＡＭ１２同様、伸張
ユニット１５の全てのデータ構造がＲＡＭ１７内に保持
され、ＲＡＭ１７のサイズは、圧縮ユニット１０内で使
用される圧縮アルゴリズムのタイプに依存する。動作
中、圧縮されたデータ・ストリームが、最初に伸張ユニ
ット１５によりデータ送信装置１９から受信される。デ
ータ復号の後、圧縮解除されたデータ・ストリームが、
伸張ユニット１５からデータ受信装置１８に伝送され
る。
【００１４】図３を参照すると、本発明の好適な実施例
に従い、図１の圧縮ユニット１０に対して、改善された
圧縮効率を提供するデータ事前圧縮器のブロック図が示
される。事前圧縮ユニット２０は、好適にはデータ送信
装置１３と圧縮ユニット１０との間に結合される。図示
のように、事前圧縮ユニット２０は、第１のレジスタ２
２、第２のレジスタ２３、比較器２４、第１のカウンタ
２５、第２のカウンタ２６、及びマルチプレクサ２１を
含む。
【００１５】動作中、非圧縮データ・ストリームからの
各入来データ・バイトが、最初に第１のレジスタ２２に
記憶される。この入来データ・バイトは、非圧縮データ
・ストリームからの別の入来データ・バイトの到来時
に、第２のレジスタ２３に送信される。従って、第２の
レジスタ２３は、非圧縮データ・ストリームからの前の
（すなわち直前の）データ・バイトの値を保持する。次
に比較器２４により、第１のレジスタ２２に記憶される
入来データ・バイトが、第２のレジスタ２３に記憶され
る前のデータ・バイトと比較される。第１のカウンタ２
５は当初、０にリセットされ、比較器２４により第１の
レジスタ２２に記憶されるデータ・バイトと、第２のレ
ジスタ２３に記憶されるデータ・バイトとの一致が示さ
れる度に増分される。他方、第１のレジスタ２２に記憶
されるデータ・バイトと、第２のレジスタ２３に記憶さ
れるデータ・バイトとが不一致の場合、第１のカウンタ
２５は再度、０にリセットされる。また、非圧縮データ
・ストリームからの入来データ・バイトは、第１のレジ
スタ２２に記憶されるデータ・バイト（すなわち入来デ
ータ・バイト）と、第２のレジスタ２３に記憶されるデ
ータ・バイトとが不一致の場合、マルチプレクサ２１を
介して圧縮ユニット１０に送信される。
【００１６】第１のカウンタ２５に関連付けられる事前
設定値が存在し、一旦この事前設定値に達すると、非圧
縮データ・ストリームからの前のデータ・バイトと一致
する任意の追加の入来データ・バイトが廃棄される。こ
のことは、非圧縮データ・ストリーム内のラン条件の発
生を意味する。この時点で、入来データ・バイトとその
前のデータ・バイトとの一致条件に対して、第２のカウ
ンタ２６が代わりに増分される。入来データ・バイトと
その前のデータ・バイトとの不一致が最終的に発生する
と、第２のカウンタ２６内に記憶された累算カウントが
圧縮ユニット１０に渡され、不一致の入来データ・バイ
トがそれに続く。
【００１７】第１のカウンタ２５の事前設定値は、かな
り小さいべきであり、ラン・レングス４に対応して値と
して３を取るべきである。このことがほとんどの非圧縮
データ・ストリームに対して極めて最適であることが判
明している。従って、事前設定値４未満のランを含む非
圧縮データ・ストリームからの全てのデータ・バイト
は、単に圧縮ユニット１０に渡され、そこで使用される
圧縮アルゴリズムに従い処理される。
【００１８】ほとんどの適応圧縮アルゴリズムは文字ベ
ースであるので、カウンタ２５、２６は好適には文字と
同一のサイズであり、通常８ビット長である。ランが事
前設定値と丁度同一の長さの場合、カウント値"００"が
圧縮ユニット１０に渡される。ランが事前設定値よりも
１バイト長い場合には、カウント値"０１"が圧縮ユニッ
ト１０に渡される（以下同様）。８ビット文字が使用さ
れる場合、最高値がカウント継続文字として使用され
る。
【００１９】図４を参照すると、本発明の好適な実施例
に従い、データ事前圧縮器の改善されたデータ圧縮効率
を提供する方法の状態図が示される。状態（００）から
開始し、使用可能フラグ、第１のカウンタ、第２のカウ
ンタが０にリセットされ、次に状態（０１）に移行す
る。状態（０１）では、事前圧縮器がデータ・バイト入
力要求を待機する。状態（０２）では、使用可能フラグ
が０にセットされているか否かを判定し、肯定の場合、
状態（０４）に移行し、否定の場合、状態（０３）に移
行する。
【００２０】状態（０３）では、以前に保管された新た
なデータ・バイトが圧縮器に転送される。状態（０４）
では、データ・バイトがデータ送信装置からフェッチさ
れ、状態（０５）に移行する。状態（０５）では、第１
のカウンタが事前設定限度か否かが判定され、肯定の場
合、状態（０８）に移行し、否定の場合、状態（０７）
に移行する。
【００２１】状態（０６）では、新たなデータ・バイト
が前のバイトと同一か否かが判定され、肯定の場合、状
態（０８）に移行し、否定の場合、状態（０７）に移行
する。
【００２２】状態（０７）では、第１のカウンタが０に
リセットされ、状態（０９）に移行する。状態（０８）
では、第１のカウンタが１増分され、次に状態（０９）
に移行する。状態（０９）では、新たなデータ・バイト
が圧縮器に転送され、次に状態（０１）に移行する。
【００２３】状態（１０）では、新たなデータ・バイト
が前のバイトと同一か否かが判定され、肯定の場合、状
態（１３）に移行し、否定の場合、状態（１１）に移行
する。状態（１２）では、使用可能フラグが１にセット
され、次に状態（０１）に移行する。
【００２４】状態（１３）では、第２のカウンタが１増
分され、次に状態（１４）に移行する。状態（１４）で
は、第２のカウンタがその最大値か否かが判定され、肯
定の場合、状態（１５）に移行し、否定の場合、状態
（０４）に移行する。
【００２５】状態（１５）では、第２のカウンタ値が圧
縮器に転送され、次に状態（１６）に移行する。状態
（１６）では、第２のカウンタ値が"０１"にリセットさ
れ、次に状態（０１）に移行する。
【００２６】図５を参照すると、本発明の好適な実施例
に従う、対応するデータ事後圧縮器のハイレベル状態図
が示される。状態（００）から開始し、拡張フラグ、第
１のカウンタ、第２のカウンタが０にリセットされ、次
に状態（０１）に移行する。
【００２７】状態（０１）では、伸張器からの新たなデ
ータ・バイトの出力を待機する。状態（０２）では、拡
張フラグが０にセットされているか否かを判定し、肯定
の場合、状態（１３）に移行し、否定の場合、状態（０
３）に移行する。
【００２８】状態（０３）では、新たなデータ・バイト
値が第２のカウンタにロードされる。状態（０４）で
は、第２のカウント値がその最大値であるか否かが判定
され、肯定の場合、状態（０９）に移行し、否定の場
合、状態（０５）に移行する。
【００２９】状態（０５）では、拡張フラグが０にリセ
ットされ、次に状態（０６）に移行する。状態（０６）
では、第２のカウンタ値が０か否かが判定され、肯定の
場合、状態（００）に移行し、否定の場合、状態（０
７）に移行する。状態（０７）では、前のデータ・バイ
トが出力に転送され、次に状態（０８）に移行する。状
態（０８）では、第２のカウンタが１減分され、次に状
態（０６）に移行する。
【００３０】状態（０９）では、拡張フラグが１にセッ
トされ、次に状態（１０）に移行する。状態（１０）で
は、前のデータ・バイトが出力に転送され、次に状態
（１１）に移行する。状態（１１）では、第２のカウン
タが１減分され、次に状態（１２）に移行する。状態
（１２）では、第２のカウンタ値が１よりも大きいか否
かが判定され、肯定の場合、状態（１０）に移行し、否
定の場合、状態（０１）に移行する。
【００３１】状態（１３）では、第１のカウンタが事前
設定限度か否かが判定され、肯定の場合、状態（０３）
に移行し、否定の場合、状態（１４）に移行する。
【００３２】状態（１４）では、新たなデータ・バイト
値が出力に転送され、次に状態（１５）に移行する。状
態（１５）では、新たなデータ・バイトが前のバイトと
同一か否かが判定され、肯定の場合、状態（１７）に移
行し、否定の場合、状態（１６）に移行する。状態（１
６）では、第１のカウンタ値が０にリセットされ、次に
状態（０１）に移行する。状態（１７）では、第１のカ
ウンタが１増分され、次に状態（０１）に移行する。
【００３３】表１は、本発明の好適な実施例に従う、入
力データ・ストリームにもとづく、事前圧縮ユニット２
０からの結果を示す例である。この例では、事前設定値
が３にセットされ、また８ビット記号（１バイト）が使
用される。
【００３４】
【表１】
【００３５】上述のように、本発明は圧縮ユニットに改
善されたデータ圧縮効率を提供するための方法及び装置
を提供する。圧縮ユニットが例証の目的のために、本開
示全体を通じて使用されるが、当業者であれば、上述の
事前圧縮器が、対応する事後伸張器を使用しなければな
らないことが理解できよう。こうした事後伸張器は、好
適には、図２の伸張ユニット１５とデータ受信装置１８
の間に結合される。
【００３６】事後伸張器は事前圧縮器の逆の操作を実行
する。伸張ユニットから出力される各データ・バイト
が、その前のデータ・バイトと比較され、カウンタが増
分またはリセットされる。カウンタが事前設定値に達す
ると、次のデータ・バイトが、ランの継続を構成する最
終値出力の追加の複写数を示すカウントとして処理され
なければならず、更に圧縮データ・バイトを復号する前
に、複写されなければならない。
【００３７】事前圧縮器及び事後伸張器の両者におい
て、カウントが次の記号に継続されなければ、最大カウ
ント記号値がこの値のカウントを示すために使用され、
これが同一の規則に従い処理されなければならない。こ
のように、カウント継続文字の使用は、任意の長さのラ
ンの符号化を可能にし、ある記号のラン・レングスが事
前に設定されたしきい値に丁度等しいときに欠点を有す
る。
【００３８】ハードウェアの点で、本発明は単に、前の
データ記号を保持するための余分なレジスタ、比較器、
及びカウンタの他に、少量の制御論理回路を要求するだ
けである。実際、連想記憶装置（ＣＡＭ）ベースの圧縮
器では、レジスタが既にハードウェア内に存在するが、
いずれにしても、本発明を実現するために使用される余
分なシリコン面積は僅かである。
【００３９】更に、本発明は任意の種類の圧縮アルゴリ
ズムに適用可能であり、明らかにそれ自体、長いランの
データに対しては、相当な圧縮を提供することができる
（８ビット記号において２５０：１を上回る）。汎用適
応圧縮アルゴリズムでは、このことは重要な利点であ
る。なぜなら、こうした圧縮アルゴリズムは一般に、入
来データのストリームがその圧縮アルゴリズムに適する
ように使用されるべきか否かに関係無しに適応するから
である。例えばLempel-Ziv1アルゴリズムは、長いラン
の同一データに対して、最大圧縮率約９０：１を達成で
きるに過ぎない。
【００４０】まとめとして、本発明の構成に関して以下
の事項を開示する。
【００４１】（１）データ圧縮ユニットに改善されたデ
ータ圧縮効率を提供する方法であって、前記データ圧縮
ユニットにより受信される非圧縮データ・ストリームか
らの入来データ・バイトと、前のデータ・バイトとを比
較するステップと、前記入来データ・バイトと前記前の
データ・バイトとの一致に応答して、第１のカウンタ値
を増分するステップと、前記第１のカウンタ値が、前記
非圧縮データ・ストリーム内のランを示す事前設定値に
達したことに応答して、第２のカウンタ値を増分するス
テップと、前記非圧縮データ・ストリーム内の前記ラン
を前記第２のカウンタ値により置換するステップと、前
記非圧縮データ・ストリームを前記データ圧縮ユニット
に伝送し、該圧縮ユニットが、前記非圧縮データ・スト
リーム内における前記ランの発生後、迅速に最適な圧縮
率を再開できるようにするステップと、を含む、方法。 （２）前記入来データ・バイトと前記前のデータ・バイ
トとの不一致に応答して、前記第１のカウンタをリセッ
トするステップを含む、前記（１）記載の方法。 （３）前記第２のカウンタ値を増分するステップが、前
記入来データ・バイトと前記前のデータ・バイトとの続
く一致に応答して、前記第２のカウンタ値を増分するス
テップを含む、前記（１）記載の方法。 （４）前記入来データ・バイトを廃棄するステップを含
む、前記（３）記載の方法。 （５）前記ランの完了が、前記入来データ・バイトと前
記前のデータ・バイトとの不一致により示される、前記
（１）記載の方法。 （６）データ圧縮ユニットに改善されたデータ圧縮効率
を提供する方法であって、前記データ圧縮ユニットによ
り受信される非圧縮データ・ストリームからの入来デー
タ・バイトと、前のデータ・バイトとを比較することに
より、前記非圧縮データ・ストリームを事前処理するス
テップと、前記非圧縮データ・ストリーム内のランの開
始を示す、前記入来データ・バイトと前記前のデータ・
バイトとの一致に応答して、第１のカウンタ値を増分す
るステップと、前記非圧縮データ・ストリーム内の前記
ランの残りの部分を示す、前記第１のカウンタ値が事前
設定値に達した後の、前記入来データ・バイトと前記前
のデータ・バイトとの続く一致に応答して、第２のカウ
ンタ値を増分するステップと、前記非圧縮データ・スト
リーム内の前記ランの前記残りの部分を、前記第２のカ
ウンタ値により置換するステップと、前記第２のカウン
タ値が埋め込まれた前記非圧縮データ・ストリームを前
記データ圧縮ユニットに伝送し、該圧縮ユニットが、前
記非圧縮データ・ストリーム内における前記ランの発生
にも関わらず、迅速に最適な圧縮効率を再開できるよう
にするステップと、を含む、方法。 （７）前記入来データ・バイトと前記前のデータ・バイ
トとの不一致に応答して、前記第１のカウンタをリセッ
トするステップを含む、前記（６）記載の方法。 （８）前記入来データ・バイトを廃棄するステップを含
む、前記（６）記載の方法。 （９）前記ランの完了が、前記入来データ・バイトと前
記前のデータ・バイトとの不一致により示される、前記
（６）記載の方法。 （１０）データ圧縮ユニットに改善されたデータ圧縮効
率を提供する事前圧縮器であって、前記データ圧縮ユニ
ットにより受信される非圧縮データ・ストリームからの
入来データ・バイトと、前のデータ・バイトとを比較す
る比較器と、前記比較器に接続され、前記入来データ・
バイトと前記前のデータ・バイトとの一致の数をカウン
トする第１のカウンタと、前記比較器に接続され、前記
第１のカウンタが事前設定値に達した後に、前記入来デ
ータ・バイトと前記前のデータ・バイトとの一致の数を
カウントする第２のカウンタと、前記入来データ・バイ
トのランの完了時に、前記第２のカウンタの値を前記デ
ータ圧縮ユニットに送信し、該圧縮ユニットが、前記非
圧縮データ・ストリーム内における前記ランの発生後、
迅速にその最適な圧縮率を再開できるようにする、送信
装置と、を含む、事前圧縮器。 （１１）前記入来データ・バイトと前記前のデータ・バ
イトとの不一致に応答して、前記第１のカウンタをリセ
ットするリセット手段を含む、前記（１０）記載の事前
圧縮器。 （１２）前記第２のカウンタの増分の間に、前記入来デ
ータ・バイトを廃棄する手段を含む、前記（１０）記載
の事前圧縮器。 （１３）前記ランの完了が、前記入来データ・バイトと
前記前のデータ・バイトとの不一致により示される、前
記（１０）記載の事前圧縮器。 （１４）前記非圧縮データ・ストリーム内の前記ラン
を、前記第２のカウンタ値により置換する手段を含む、
前記（１０）記載の事前圧縮器。
【図面の簡単な説明】
【図１】本発明の好適な実施例が組み込まれ得る圧縮ユ
ニットのブロック図である。
【図２】本発明の好適な実施例が組み込まれ得るデータ
伸張ユニットのブロック図である。
【図３】本発明の好適な実施例に従い、データ圧縮ユニ
ットに改善された圧縮効率を提供するデータ事前圧縮器
のブロック図である。
【図４】本発明の好適な実施例に従い、データ事前圧縮
器のための改善されたデータ圧縮効率を提供する方法の
状態図である。
【図５】本発明の好適な実施例に従い、データ事後圧縮
器のための改善されたデータ圧縮効率を提供する方法の
状態図である。
【符号の説明】
１０ 圧縮ユニット １１、１６ 制御装置 １２、１７ ランダム・アクセス・メモリ（ＲＡＭ）ま
たは連想記憶装置（ＣＡＭ） １３ データ送信装置 １４、１８ データ受信装置 １５ データ伸張ユニット ２０ 事前圧縮ユニット ２１ マルチプレクサ ２２ 第１のレジスタ ２３ 第２のレジスタ ２４ 比較器 ２５ 第１のカウンタ ２６ 第２のカウンタ

Claims (14)

    【特許請求の範囲】
  1. 【請求項１】データ圧縮ユニットに改善されたデータ圧
    縮効率を提供する方法であって、 前記データ圧縮ユニットにより受信される非圧縮データ
    ・ストリームからの入来データ・バイトと、前のデータ
    ・バイトとを比較するステップと、 前記入来データ・バイトと前記前のデータ・バイトとの
    一致に応答して、第１のカウンタ値を増分するステップ
    と、 前記第１のカウンタ値が、前記非圧縮データ・ストリー
    ム内のランを示す事前設定値に達したことに応答して、
    第２のカウンタ値を増分するステップと、 前記非圧縮データ・ストリーム内の前記ランを前記第２
    のカウンタ値により置換するステップと、 前記非圧縮データ・ストリームを前記データ圧縮ユニッ
    トに伝送し、該圧縮ユニットが、前記非圧縮データ・ス
    トリーム内における前記ランの発生後、迅速に最適な圧
    縮率を再開できるようにするステップと、 を含む、方法。
  2. 【請求項２】前記入来データ・バイトと前記前のデータ
    ・バイトとの不一致に応答して、前記第１のカウンタを
    リセットするステップを含む、請求項１記載の方法。
  3. 【請求項３】前記第２のカウンタ値を増分するステップ
    が、前記入来データ・バイトと前記前のデータ・バイト
    との続く一致に応答して、前記第２のカウンタ値を増分
    するステップを含む、請求項１記載の方法。
  4. 【請求項４】前記入来データ・バイトを廃棄するステッ
    プを含む、請求項３記載の方法。
  5. 【請求項５】前記ランの完了が、前記入来データ・バイ
    トと前記前のデータ・バイトとの不一致により示され
    る、請求項１記載の方法。
  6. 【請求項６】データ圧縮ユニットに改善されたデータ圧
    縮効率を提供する方法であって、 前記データ圧縮ユニットにより受信される非圧縮データ
    ・ストリームからの入来データ・バイトと、前のデータ
    ・バイトとを比較することにより、前記非圧縮データ・
    ストリームを事前処理するステップと、 前記非圧縮データ・ストリーム内のランの開始を示す、
    前記入来データ・バイトと前記前のデータ・バイトとの
    一致に応答して、第１のカウンタ値を増分するステップ
    と、 前記非圧縮データ・ストリーム内の前記ランの残りの部
    分を示す、前記第１のカウンタ値が事前設定値に達した
    後の、前記入来データ・バイトと前記前のデータ・バイ
    トとの続く一致に応答して、第２のカウンタ値を増分す
    るステップと、 前記非圧縮データ・ストリーム内の前記ランの前記残り
    の部分を、前記第２のカウンタ値により置換するステッ
    プと、 前記第２のカウンタ値が埋め込まれた前記非圧縮データ
    ・ストリームを前記データ圧縮ユニットに伝送し、該圧
    縮ユニットが、前記非圧縮データ・ストリーム内におけ
    る前記ランの発生にも関わらず、迅速に最適な圧縮効率
    を再開できるようにするステップと、 を含む、方法。
  7. 【請求項７】前記入来データ・バイトと前記前のデータ
    ・バイトとの不一致に応答して、前記第１のカウンタを
    リセットするステップを含む、請求項６記載の方法。
  8. 【請求項８】前記入来データ・バイトを廃棄するステッ
    プを含む、請求項６記載の方法。
  9. 【請求項９】前記ランの完了が、前記入来データ・バイ
    トと前記前のデータ・バイトとの不一致により示され
    る、請求項６記載の方法。
  10. 【請求項１０】データ圧縮ユニットに改善されたデータ
    圧縮効率を提供する事前圧縮器であって、 前記データ圧縮ユニットにより受信される非圧縮データ
    ・ストリームからの入来データ・バイトと、前のデータ
    ・バイトとを比較する比較器と、 前記比較器に接続され、前記入来データ・バイトと前記
    前のデータ・バイトとの一致の数をカウントする第１の
    カウンタと、 前記比較器に接続され、前記第１のカウンタが事前設定
    値に達した後に、前記入来データ・バイトと前記前のデ
    ータ・バイトとの一致の数をカウントする第２のカウン
    タと、 前記入来データ・バイトのランの完了時に、前記第２の
    カウンタの値を前記データ圧縮ユニットに送信し、該圧
    縮ユニットが、前記非圧縮データ・ストリーム内におけ
    る前記ランの発生後、迅速にその最適な圧縮率を再開で
    きるようにする、送信装置と、 を含む、事前圧縮器。
  11. 【請求項１１】前記入来データ・バイトと前記前のデー
    タ・バイトとの不一致に応答して、前記第１のカウンタ
    をリセットするリセット手段を含む、請求項１０記載の
    事前圧縮器。
  12. 【請求項１２】前記第２のカウンタの増分の間に、前記
    入来データ・バイトを廃棄する手段を含む、請求項１０
    記載の事前圧縮器。
  13. 【請求項１３】前記ランの完了が、前記入来データ・バ
    イトと前記前のデータ・バイトとの不一致により示され
    る、請求項１０記載の事前圧縮器。
  14. 【請求項１４】前記非圧縮データ・ストリーム内の前記
    ランを、前記第２のカウンタ値により置換する手段を含
    む、請求項１０記載の事前圧縮器。
JP10228812A 1997-09-19 1998-08-13 改善されたデータ圧縮効率を提供する方法及び事前圧縮器 Expired - Fee Related JP3065585B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/934335 1997-09-19
US08/934,335 US5874907A (en) 1997-09-19 1997-09-19 Method and apparatus for providing improved data compression efficiency for an adaptive data compressor

Publications (2)

Publication Number Publication Date
JPH11145848A true JPH11145848A (ja) 1999-05-28
JP3065585B2 JP3065585B2 (ja) 2000-07-17

Family

ID=25465369

Family Applications (1)

Application Number Title Priority Date Filing Date
JP10228812A Expired - Fee Related JP3065585B2 (ja) 1997-09-19 1998-08-13 改善されたデータ圧縮効率を提供する方法及び事前圧縮器

Country Status (8)

Country Link
US (1) US5874907A (ja)
EP (1) EP0903867B1 (ja)
JP (1) JP3065585B2 (ja)
KR (1) KR100300789B1 (ja)
DE (1) DE69833094T2 (ja)
MY (1) MY115600A (ja)
SG (1) SG66494A1 (ja)
TW (1) TW410505B (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000059226A (ja) * 1998-07-28 2000-02-25 Xerox Corp 最小マッチ長が３のプリマッチストリングマッチアレイ

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6624761B2 (en) 1998-12-11 2003-09-23 Realtime Data, Llc Content independent data compression method and system
US6604158B1 (en) * 1999-03-11 2003-08-05 Realtime Data, Llc System and methods for accelerated data storage and retrieval
US6601104B1 (en) * 1999-03-11 2003-07-29 Realtime Data Llc System and methods for accelerated data storage and retrieval
DE19962971A1 (de) * 1999-12-24 2001-06-28 Bosch Gmbh Robert Verfahren zur Datenübertragung über ein Bussystem
US20010047473A1 (en) * 2000-02-03 2001-11-29 Realtime Data, Llc Systems and methods for computer initialization
US20030191876A1 (en) * 2000-02-03 2003-10-09 Fallon James J. Data storewidth accelerator
US9143546B2 (en) 2000-10-03 2015-09-22 Realtime Data Llc System and method for data feed acceleration and encryption
US7417568B2 (en) * 2000-10-03 2008-08-26 Realtime Data Llc System and method for data feed acceleration and encryption
US8692695B2 (en) 2000-10-03 2014-04-08 Realtime Data, Llc Methods for encoding and decoding data
US7386046B2 (en) * 2001-02-13 2008-06-10 Realtime Data Llc Bandwidth sensitive data compression and decompression
EP1451708B1 (en) * 2001-12-10 2012-03-28 SAP Portals Israel Ltd. Apparatus and method for optimized and secured reflection of network services to remote locations
DE10301362B4 (de) * 2003-01-16 2005-06-09 GEMAC-Gesellschaft für Mikroelektronikanwendung Chemnitz mbH Blockdatenkompressionssystem, bestehend aus einer Kompressionseinrichtung und einer Dekompressionseinrichtung, und Verfahren zur schnellen Blockdatenkompression mit Multi-Byte-Suche
US9614772B1 (en) 2003-10-20 2017-04-04 F5 Networks, Inc. System and method for directing network traffic in tunneling applications
US7103685B1 (en) * 2004-01-16 2006-09-05 Xilinx, Inc. Bitstream compression with don't care values
US8024483B1 (en) 2004-10-01 2011-09-20 F5 Networks, Inc. Selective compression for network connections
US7109895B1 (en) * 2005-02-01 2006-09-19 Altera Corporation High performance Lempel Ziv compression architecture
US7937510B1 (en) 2005-02-01 2011-05-03 Altera Corporation Lempel Ziv compression architecture
US7482954B1 (en) 2005-02-25 2009-01-27 Xilinx, Inc. Bitstream compression for a programmable device
US7783781B1 (en) 2005-08-05 2010-08-24 F5 Networks, Inc. Adaptive compression
US8533308B1 (en) 2005-08-12 2013-09-10 F5 Networks, Inc. Network traffic management through protocol-configurable transaction processing
US8275909B1 (en) * 2005-12-07 2012-09-25 F5 Networks, Inc. Adaptive compression
US7882084B1 (en) 2005-12-30 2011-02-01 F5 Networks, Inc. Compression of data transmitted over a network
US7873065B1 (en) 2006-02-01 2011-01-18 F5 Networks, Inc. Selectively enabling network packet concatenation based on metrics
US8565088B1 (en) 2006-02-01 2013-10-22 F5 Networks, Inc. Selectively enabling packet concatenation based on a transaction boundary
US8417833B1 (en) 2006-11-29 2013-04-09 F5 Networks, Inc. Metacodec for optimizing network data compression based on comparison of write and read rates
US9106606B1 (en) 2007-02-05 2015-08-11 F5 Networks, Inc. Method, intermediate device and computer program code for maintaining persistency
US8238677B2 (en) * 2008-03-07 2012-08-07 International Business Machines Corporation Adaptive lossless data compression method for compression of color image data
GR1008346B (el) * 2013-11-04 2014-11-03 Νικολαος Χρηστου Πετρελλης Μεθοδος και συσκευη παρεμβολης για πιστοτερη αναπαρασταση και συμπιεση σηματος
US11158364B2 (en) 2019-05-31 2021-10-26 Micron Technology, Inc. Apparatuses and methods for tracking victim rows
US11158373B2 (en) * 2019-06-11 2021-10-26 Micron Technology, Inc. Apparatuses, systems, and methods for determining extremum numerical values
US11462291B2 (en) 2020-11-23 2022-10-04 Micron Technology, Inc. Apparatuses and methods for tracking word line accesses
US11482275B2 (en) 2021-01-20 2022-10-25 Micron Technology, Inc. Apparatuses and methods for dynamically allocated aggressor detection
US11863209B2 (en) * 2021-08-18 2024-01-02 Pixart Imaging Inc. Integrated circuit and method capable of minimizing circuit area of non-volatile memory circuit
US12165687B2 (en) 2021-12-29 2024-12-10 Micron Technology, Inc. Apparatuses and methods for row hammer counter mat

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2396479A1 (fr) * 1977-06-30 1979-01-26 Cit Alcatel Installation de transmission de fac-simile a reduction de redondance
US4626829A (en) 1985-08-19 1986-12-02 Intelligent Storage Inc. Data compression using run length encoding and statistical encoding
US4679094A (en) * 1986-10-14 1987-07-07 The Associated Press Method for compression and transmission of video information
US5016009A (en) * 1989-01-13 1991-05-14 Stac, Inc. Data compression apparatus and method
JPH088642B2 (ja) * 1989-07-27 1996-01-29 富士通株式会社 網点画像データ圧縮装置
CA2077271C (en) * 1991-12-13 1998-07-28 David J. Craft Method and apparatus for compressing data
US5486826A (en) * 1994-05-19 1996-01-23 Ps Venture 1 Llc Method and apparatus for iterative compression of digital data
US5612693A (en) * 1994-12-14 1997-03-18 International Business Machines Corporation Sliding window data compression using a toroidal bit shift register
KR100254402B1 (ko) * 1994-12-19 2000-05-01 전주범 줄-길이 부호화방법 및 줄-길이 부호화기
US5608396A (en) * 1995-02-28 1997-03-04 International Business Machines Corporation Efficient Ziv-Lempel LZI data compression system using variable code fields
US5627534A (en) * 1995-03-23 1997-05-06 International Business Machines Corporation Dual stage compression of bit mapped image data using refined run length and LZ compression

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000059226A (ja) * 1998-07-28 2000-02-25 Xerox Corp 最小マッチ長が３のプリマッチストリングマッチアレイ

Also Published As

Publication number Publication date
DE69833094D1 (de) 2006-03-30
EP0903867B1 (en) 2006-01-04
TW410505B (en) 2000-11-01
DE69833094T2 (de) 2006-08-31
KR100300789B1 (ko) 2001-09-22
MY115600A (en) 2003-07-31
EP0903867A1 (en) 1999-03-24
SG66494A1 (en) 1999-07-20
JP3065585B2 (ja) 2000-07-17
KR19990029322A (ko) 1999-04-26
US5874907A (en) 1999-02-23

Similar Documents

Publication Publication Date Title
JP3065585B2 (ja) 改善されたデータ圧縮効率を提供する方法及び事前圧縮器
US8090027B2 (en) Data compression using an arbitrary-sized dictionary
US6633242B2 (en) Entropy coding using adaptable prefix codes
US5293379A (en) Packet-based data compression method
JP3141001B2 (ja) 符号化方法及びデータ圧縮器、並びにコンピュータ・プログラムを記録した記録媒体
US5003307A (en) Data compression apparatus with shift register search means
US5532694A (en) Data compression apparatus and method using matching string searching and Huffman encoding
KR100314419B1 (ko) 변형렘펠-지브1을인코딩하기위한방법및장치
US20070150497A1 (en) Block data compression system, comprising a compression device and a decompression device and method for rapid block data compression with multi-byte search
CA2128127A1 (en) Method and system for data compression
CN1630984A (zh) 增量和连续的数据压缩
US9362948B2 (en) System, method, and computer program product for saving and restoring a compression/decompression state
JP2003524983A (ja) 複数コーダを用いる最適化ロスレス圧縮のための方法及び装置
JPH07170196A (ja) ２値シンボルの符号化・復号化回路
US6289130B1 (en) Method for real-time lossless data compression of computer data
JP3839604B2 (ja) データ処理方法
JP3266419B2 (ja) データ圧縮・伸長方式
JP3653226B2 (ja) 埋込みランレングス符号化によるデータ圧縮方法および装置
US6522270B1 (en) Method of coding frequently occurring values
US6583736B1 (en) Bitcode sequence coding of frequently occurring values
JP3143030B2 (ja) データ圧縮方法及びその装置並びにデータ伸長方法及びその装置
KR20080045842A (ko) 이미지 압축 및 복원을 위한 장치 및 방법
JPH08116270A (ja) データ圧縮方法及びその装置並びにデータ伸長方法及びその装置
JPH0659857A (ja) データ圧縮装置

Legal Events

Date Code Title Description
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090512

Year of fee payment: 9

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100512

Year of fee payment: 10

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110512

Year of fee payment: 11

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110512

Year of fee payment: 11

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120512

Year of fee payment: 12

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120512

Year of fee payment: 12

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130512

Year of fee payment: 13

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130512

Year of fee payment: 13

S531 Written request for registration of change of domicile

Free format text: JAPANESE INTERMEDIATE CODE: R313531

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130512

Year of fee payment: 13

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

S802 Written request for registration of partial abandonment of right

Free format text: JAPANESE INTERMEDIATE CODE: R311802

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130512

Year of fee payment: 13

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140512

Year of fee payment: 14

S633 Written request for registration of reclamation of name

Free format text: JAPANESE INTERMEDIATE CODE: R313633

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

LAPS Cancellation because of no payment of annual fees