JP2003502930A - ランレングス符号化／復号化が組み込まれているｌｚｗデータ圧縮装置と方法 - Google Patents

Abstract

(57)【要約】 ランレングス符号化／復号化が組み込まれているＬＺＷデータ圧縮／伸張装置と方法が開示されている。ＬＺＷデータ圧縮器では、文字ランが入力文字ストリームの中に出現したことが判断され、ランカウントが圧縮器コードカウンタ内の既存コードに加算されて、ランカウントを表す圧縮器コード出力を生成する。ＬＺＷデータ伸張器は、伸張器コードカウンタ内の既存コードを、受け取られた圧縮コードから減算して、ランカウントを回復する。別の特徴によれば、大きな長さのランは、選択された事前決定定数をランカウントから減算することによって、ランカウントをシステム最大コード以下に減少することで処理される。この減少ランカウントは、選択された事前決定定数を表す予約コードが前に置かれて、圧縮器によって出力される。受け取られた予約コードとその後に置かれた減少カウントに応答して、伸張器は、受け取られた予約コードに対応する選択された事前決定定数を、受け取られた減少カウントに加算して、オリジナルランカウントを回復する。

Description

【発明の詳細な説明】

【０００１】関連出願との相互参照 米国特許出願第０９／２６４，２６９号（Ｃｏｏｐｅｒ）、１９９９年３月８
日出願、発明の名称「ランレングス符号化が組み込まれているデータ圧縮方法と
装置（Ｄａｔａ Ｃｏｍｐｒｅｓｓｉｏｎ Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒ
ａｔｕｓ ｗｉｔｈ Ｅｍｂｅｄｄｅｄ Ｒｕｎ−Ｌｅｎｇｔｈ Ｅｎｃｏｄｉ
ｎｇ）」。

【０００２】 米国特許出願第０９／３００，８１０号（Ｃｏｏｐｅｒ）、１９９９年４月２
７日出願、発明の名称「数学的ラン処理を使用したランレングス符号化が組み込
まれているデータ圧縮方法と装置（Ｄａｔａ Ｃｏｍｐｒｅｓｓｉｏｎ Ｍｅｔ
ｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｗｉｔｈ Ｅｍｂｅｄｄｅｄ Ｒｕｎ−
Ｌｅｎｇｔｈ Ｅｎｃｏｄｉｎｇ Ｕｓｉｎｇ Ｍａｔｈｅｍａｔｉｃａｌ Ｒ
ｕｎ Ｐｒｏｃｅｓｓｉｎｇ）」。

【０００３】 上記特許出願第０９／２６４，２６９号および第０９／３００，８１０号は、
引用により本明細書の一部になっている。

【０００４】発明の背景 １． 発明の分野 本発明はＬＺＷデータ圧縮と伸張システムに関し、具体的には、ランレングス
符号化（エンコード）と復号化（デコード）がＬＺＷ圧縮と伸張処理内に組み込
まれているＬＺＷデータ圧縮と伸張システムに関する。

【０００５】

【０００６】 ２． 従来技術の説明 Ａｂｒａｈａｍ Ｌｅｍｐｅｌ教授とＪａｃｏｂ Ｚｉｖ教授は、今日ではそ
の使用が普及しているＬＺデータ圧縮と伸張システムの理論的基礎を築いた。両
教授の独創的な論文の２つは、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉ
ｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， ＩＴ−２３−３， Ｍａｙ １９７７
， ｐｐ． ３３７−３４３とＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉ
ｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， ＩＴ−２４−５， Ｓｅｐｔｅｍｂｅ
ｒ １９７８， ｐｐ． ５３０−５３６に掲載されている。ＬＺＷとして知ら
れ、Ｖ．４２ ｂｉｓモデム圧縮と伸張に関する標準として採用されているデー
タ圧縮と伸張システムは、幅広く使用されており、米国特許第４，５５８，３０
２号（Ｗｅｌｃｈ）、１９８５年１２月１０日特許交付に記載されている。ＬＺ
Ｗは、ＧＩＦとＴＩＦＦ画像（イメージ）通信プロトコルで使用されている圧縮
と伸張標準として採用されている。

【０００７】 ランレングス符号化（ｒｕｎ−ｌｅｎｇｔｈ ｅｎｃｏｄｉｎｇ ＲＬＥ）
と名付けられた別タイプのデータ圧縮と伸張は、文字およびランの長さを示す圧
縮コードを得ることによって反復的文字ランを圧縮している。従って、ＲＬＥは
、同一文字の長いストリングを符号化するのに効果的になっている。例えば、Ｒ
ＬＥは、データファイルの先頭に入れておくことができる長いブランクのシーケ
ンスを圧縮するのに効果的になっている。また、ＲＬＥは、ランド・スカイ（ｌ
ａｎｄ−ｓｋｙ）画像のスカイ部分におけるように、画像が同じ値をもつ連続ピ
クセルの長いランを含んでいるような画像圧縮にも効果的になっている。

【０００８】 従来技術では、ランレングス符号化は、以下に示す米国特許に例示されている
ようにＬＺシステムと結合されている。すなわち、特許第４，９２９，９４６号
（Ｏ’Ｂｒｉｅｎ他）１９９０年５月２９日特許交付、特許第４，９７１，４０
７号（Ｈｏｆｆｍａｎ）１９９０年１１月２０日特許交付、特許第４，９８８，
９９８号（Ｏ’Ｂｒｉｅｎ）１９９１年１月２９日特許交付、特許第５，２４７
，６３８号（Ｏ’Ｂｒｉｅｎ他）１９９３年９月２１日特許交付、特許第５，３
８９，９２２号（Ｓｅｒｏｕｓｓｉ他）１９９５年２月１４日特許交付、および
特許第５，８６１，８２７号（Ｗｅｌｃｈ他）１９９９年１月１９日特許交付。

【０００９】 いくつかの従来システムでは、ランレングス符号化は、データをランレングス
符号器（エンコーダ）に入力し、次にランレングス符号化データをＬＺベースの
システムに入力することによってＬＺシステムと結合されている。このようなア
ーキテクチャでは、ランレングス符号器は圧縮器（ｃｏｍｐｒｅｓｓｏｒ）のフ
ロントエンド（前端側）で利用され、ランレングス復号器（デコーダ）は伸張器
（ｄｅｃｏｍｐｒｅｓｓｏｒ）の出力側で利用されている。このようなシステム
には、機器、費用、制御オーバヘッドおよび処理時間が増加するという欠点があ
る。そのようなシステムは、特許第４，９７１，４０７号と特許第４，９８８，
９９８号に例示されている。

【００１０】 特許第５，３８９，９２２号のＬＺＷベースのシステムでは、圧縮器からのあ
る種の出力コードは、反復的入力データ文字のランが出現したとき除去されてい
る。紛失したコードは、伸張器の入力側に特殊なラン強化エンジン（ｒｕｎ ｅ
ｎｈａｎｃｅｍｅｎｔ ｅｎｇｉｎｅ）を利用することによって再生成されてい
る。

【００１１】 特許第５，８６１，８２７号のシステムの圧縮器では、部分的ストリングＷと
文字Ｃが見つかったとき、新しいストリングは、ＣをストリングＰＷ上の延長文
字（ｅｘｔｅｎｓｉｏｎ ｃｈａｒａｃｔｅｒ）としてストアされている。ここ
で、Ｐは、最後に伝送された出力圧縮コードの中で伝達されたストリングである
。この圧縮アルゴリズムによると、文字のランは、その長さに関係なく、２つの
圧縮コードで符号化されている。このシステムの伸張器は、圧縮器との同期を保
つために特殊なコードプロセス（正式に認められていない）を使用している。

【００１２】 特許第４，９２９，９４６号のシステムでは、ランは、あらかじめ決めた予約
参照値（ｒｅｓｅｒｖｅｄ ｒｅｆｅｒｅｎｃｅ ｖａｌｕｅｓ）セットの中の
１つに続けて、そのランの反復カウントを送信することによって示されている。
予約参照値は、予約参照値の後に続く反復カウントの中のビット数が減少される
ように定義されている。検出されるすべてのランの圧縮ストリーム内に予約参照
値を使用する要件は、圧縮を減少するのに役立っている。さらに、このシステム
は、見かけ上は、比較的小さな長さのランを処理することに制限されている。特
許第５，２４７，６３８号に記載されている内容は、特許第４，９２９，９４６
号の記載内容と類似している。

【００１３】 データ文字ランの符号化を行う別のデータ圧縮システムは、前記特許出願第０
９／２６４，２６９号に開示されている。この特許出願の圧縮器では、ランは、
連続的に数字が大きくなって行くセグメントがランに存在するかどうかを判断す
るために、入力を連続的に先読み（ルックアヘッド）することによって処理され
ている。

【００１４】 データ文字ランの符号化を行う、さらに別のデータ圧縮システムは、前記特許
出願第０９／３００，８１０号に開示されている。この特許出願の圧縮器では、
ランは、ランに存在する連続的に数字が大きくなって行くセグメントに対応する
それぞれの出力コードを、ランの長さから数学的に判断することによって処理さ
れている。

【００１５】 本発明の目的は、ランレングス符号化と復号化をＬＺＷデータ圧縮／伸張シス
テムに組み込むことであり、そこでは、ランの存在を伸張器に知らせるために特
殊な予約コードを送信しないで済むようにしている。本発明の別の目的は、長さ
が非常に大きいランの処理を可能にすることである。

【００１６】発明の概要 本発明によれば、入力データ文字のランがいつ出現したかを判断することによ
って、およびラン文字カウントを圧縮器コードカウンタからの既存コード値と結
合して、ランカウントを表す圧縮器出力を生成することによって、周知のＬＺＷ
データ圧縮／伸張システムの機能が強化される。伸張器は、伸張器コードカウン
タ内の既存コード値を使用して、圧縮器出力からランカウントを回復する。本発
明の別の特徴では、非常に大きな長さのランは、選択された事前決定プロセスに
よってランカウントを減少し、選択された事前決定プロセスを表す予約コード（
ｒｅｓｅｒｖｅｄ ｃｏｄｅ）を前に置いて、減少ランカウントを出力すること
によって処理されている。予約コードを受け取ると、それに応答して、伸張器は
、受け取った予約コードに対応する事前決定プロセスを適用し、受け取った減少
ランカウントを事前決定プロセスに従って増加することによってオリジナルラン
カウントを回復する。

【００１７】好適実施形態の説明 図１を参照して説明すると、図１には、入力端１１から入力された入力データ
文字のストリームを圧縮し、対応する圧縮コードのストリームを出力端１２から
出力するデータ圧縮器１０が示されている。圧縮器１０はワーキングレジスタ（
ｗｏｒｋｉｎｇ ｒｅｇｉｓｔｅｒｓ）を具備し、これらのレジスタは、カレン
ト文字レジスタ（Ｃｕｒｒｅｎｔ Ｃｈａｒａｃｔｅｒ ｒｅｇｉｓｔｅｒ）１
３、カレントマッチレジスタ（Ｃｕｒｒｅｎｔ Ｍａｔｃｈ ｒｅｇｉｓｔｅｒ
）１４、コードサイズレジスタ（Ｃｏｄｅ Ｓｉｚｅ ｒｅｇｉｓｔｅｒ）１５
、ルックアヘッドバッファ（Ｌｏｏｋ−Ａｈｅａｄ Ｂｕｆｆｅｒ）１６、カウ
ントレジスタ（Ｃｏｕｎｔ ｒｅｇｉｓｔｅｒ）１７、最大コードレジスタ（Ｍ
ａｘｃｏｄｅ ｒｅｇｉｓｔｅｒ）２０、文字一時レジスタ（Ｃｈａｒａｃｔｅ
ｒ Ｔｅｍｐ ｒｅｇｉｓｔｅｒ）２１、および予約コードレジスタ（Ｒｅｓｅ
ｒｖｅｄ Ｃｏｄｅ ｒｅｇｉｓｔｅｒ）２２と名付けられている。圧縮器１０
は、さらに、以下で説明するように、本発明に従ってラン文字と非ラン文字を処
理するために使用されるコード値を順次に生成するためのコードカウンタ（Ｃｏ
ｄｅ Ｃｏｕｎｔｅｒ）２３を含んでいる。

【００１８】 圧縮器１０は、さらに、以下で詳しく説明するように、カレント文字レジスタ
１３内の文字とルックアヘッドバッファ１６内の文字との比較を行って、ランが
始まろうとしているかどうかを判断するためのルックアヘッド比較ロジック（ｌ
ｏｏｋ−ａｈｅａｄ ｃｏｍｐａｒｉｓｏｎ ｌｏｇｉｃ）２４を含んでいる。
圧縮器１０は、さらに、本発明に従ってラン処理を実行するとき使用されるカウ
ント減少テーブル（Ｃｏｕｎｔ Ｒｅｄｕｃｔｉｏｎ Ｔａｂｌｅ）２５を含ん
でいる。カウント減少テーブル２５には、以下で説明するように、リミット２５
が設けられている。カウント減少テーブル２５とリミット２６の詳細は、図２を
参照して以下に説明されている。

【００１９】 圧縮器１０は、さらに、本発明に従って以下で説明するように、レジスタ１７
内のカウント値を、コード減少テーブル２５に従って減少するためのカウント減
少ロジック（ｃｏｕｎｔ ｒｅｄｕｃｔｉｏｎ ｌｏｇｉｃ）２７を含んでいる
。さらに、圧縮器１０には、以下で説明するように、図３と図４のオペレーショ
ンフローチャートに従って圧縮器１０のオペレーションを制御するためのコント
ロール３０が含まれている。

【００２０】 また、以下で説明するように、圧縮器１０と協働して文字ストリングをストア
しておくためのディクショナリ（Ｄｉｃｔｉｏｎａｒｙ）３５も含まれている。
データは、制御バス３７の制御下に置かれている双方向データバス３６を介して
、圧縮器１０とディクショナリ３５の間でやりとりされる。

【００２１】 さらに、入力端１１から受け取られた入力データ文字ストリームを置いておく
ための入力文字バッファ（Ｉｎｐｕｔ Ｃｈａｒａｃｔｅｒ Ｂｕｆｆｅｒ）４
０が含まれている。個々の入力データ文字は、以下に説明するオペレーションに
従って、入力文字バッファ４０からバス４１を経由して、カレント文字レジスタ
１３、カレントマッチレジスタ１４およびルックアヘッドバッファ１６に入力さ
れる。圧縮器１０は、入力文字バッファ４０から制御バス４２を経由して、入力
データ文字を取得することを制御している。

【００２２】 要約して説明すると、圧縮器１０のオペレーションは以下の通りである。入力
データ文字は入力文字バッファ４０からフェッチされ、それに対して従来のＬＺ
Ｗデータ圧縮が行われて、出力端１２から圧縮コードストリームが得られる。周
知のように、コードカウンタ２３は、ディクショナリ３５にストアされている延
長ストリング（ｅｘｔｅｎｄｅｄ ｓｔｒｉｎｇ）にコード値を割り当てるため
に累進的にインクリメントされる。本明細書では、圧縮器１０は、この分野では
当然に理解されるように、可変長コードであるものとして説明されている。コー
ドカウンタ２３内のカウントが、最大コードレジスタ２０にストアされている最
大カウントまで達すると、レジスタ１５内のコードサイズがインクリメントされ
る。ＬＺＷ圧縮アルゴリズムは、前記特許第４，５５８，３０２号に詳しく説明
されている。

【００２３】 ルックアヘッドバッファ１６とルックアヘッド比較ロジック２４を使用して、
連続する入力文字が調べられ、ｎ（例えば、ｎ＝３）個のルックアヘッド文字が
カレント文字レジスタ１３内の文字と同一であれば、ＬＺＷプロセスはランレン
グス符号化に移って文字ランを処理する。ラン内の文字の数は、カレント文字レ
ジスタ１３、カウントレジスタ１７および文字一時（Ｔｅｍｐ）レジスタ２１を
使用してカウントされる。カウントレジスタ１７内のランカウントが、最大コー
ドレジスタ２０内の最大コードとコードカウンタ２３内の現存コードとの差より
小であるか等しければ、カウントレジスタ１７内のランカウントとコードカウン
タ２３内の現存コードの和が出力される。さもなければ、ランカウントがシステ
ム最大コードより小であれば、第１予約コードが出力され、その後に続いて、シ
ステム最大コードサイズを使用したランカウントが出力される。ランカウントが
システム最大コードより大か等しければ、カウントは、減少カウントがシステム
最大コード以下になるように、選択された事前決定プロセスによって減少される
。選択された事前決定プロセスに対応する別の予約コードが出力され、その後に
続いて、減少カウントが出力される。

【００２４】 ここで説明している実施形態は、説明の便宜上、ＡＳＣＩＩに準拠して実装さ
れたものとして示されている。ＡＳＣＩＩ環境では、８ビットの文字サイズが使
用され、２５６文字のアルファベットをサポートしている。可変長コードによる
実装では、コードサイズは９ビットから始まり、コード５１２、１０２４、２０
４８などでは、それぞれ１０、１１、１２ビットといったように順次に増加して
行くことが可能になっている。このようなシステムでは、最大コードサイズは１
２ビットが使用され、最大システムコードは４０９６になっているのが代表的で
ある。

【００２５】 このようなＡＳＣＩＩ準拠の実装では、予約コードのセットは、最大文字値よ
りも大きくなっていると好都合であり、以下で説明するように、予約コード２５
７から始まるようにすると好都合である。以下に説明する実施形態では、第１予
約コードは、予約コード２６１で終わるように利用されている。従って、ＡＳＣ
ＩＩ準拠の実装では、マルチ文字ストリングを表すためのコードカウンタ２３か
らの第１利用可能コードは、コード２６２から始まっている。以上から理解され
るように、周知のように、例えば、１２ビットの固定長コード出力に基づく実施
形態を予想することも可能である。

【００２６】 図２を参照して説明すると、図２には、図１のカウント減少テーブル２５とリ
ミット２６の詳細が示されている。カウント減少テーブル２５は、複数の選択可
能な事前決定プロセスを定義し、ランカウント値がシステム最大コードより小の
値に、あらかじめ決めた方法で減少されるようにしている。また、カウント減少
テーブル２５は、それぞれのプロセスに対応する予約コードも定義している。テ
ーブル２５の行５０−５３の各々は、プロセスの１つを定義している。具体例を
示すと、システム最大コードは２¹²、つまり、４０９６になっている。例えば、
プロセス５０は、２¹²より大か等しいが、２ｘ２¹²より小であるカウント値に対
して選択されている。プロセス５０では、テーブルの減少カウント欄に示すよう
に、この範囲にあるランカウントは２¹²だけ減少されている。プロセス５０の予
約コードは２５８である。説明の便宜上、各カウント範囲の上限値は、テーブル
のそのように名付けた欄に１０進値で示されている。使用されるパラメータにつ
いては、テーブルから理解されるように、システムによって処理される最大ラン
カウントは、２０４８０文字以下のランに制限されている。さらに、テーブルか
ら理解されるように、このリミットは、テーブルに別の行を追加することだけで
大きくなっていく。

【００２７】 カウント減少テーブル２５は、ＡＳＣＩＩ環境で使用されるように設定されて
おり、そこでは、文字は８ビットで表され、文字値は０−２５５の範囲になって
いる。予約コードは２５７−２６１として選択されている。従って、マルチ文字
ストリングを表すための第１利用可能コードは２６２である。具体例を示すと、
システム最大コードサイズは１２ビットであるので、得られるシステム最大コー
ドは４０９６である。システム最大コード以下のランカウントは、以下で説明す
るように、２５７の予約コード値で表される形で処理することができる。テーブ
ルの第１行は、そのような関係を示している。

【００２８】 引き続き図１を参照して説明すると、従来のＬＺＷ処理では、カレント文字レ
ジスタ１３、カレントマッチレジスタ１４、コードサイズレジスタ１５、コード
カウンタ２３、およびディクショナリ３５が利用されている。本発明によるラン
処理でも、コードカウンタ２３が利用されているが、それと共に、ルックアヘッ
ドバッファ１６、カウントレジスタ１７、最大コードレジスタ２２、文字一時（
Ｔｅｍｐ）レジスタ１７、予約コードレジスタ２２、ルックアヘッド比較ロジッ
ク２４、カウント減少テーブル２５、リミット２６、およびカウント減少ロジッ
ク２７が利用されている。図３と図４のコントロールフローチャートは、圧縮器
１０によって実行されるオペレーションの詳細を示している。コントロール３０
は、ステートマシンのように、これらのオペレーションの実行を制御する該当回
路を内蔵しているものと考えられている。

【００２９】 引き続き図１を参照しながら、図３を参照して説明すると、ブロック６０で、
コードカウンタ２３は、図２のカウント減少テーブル２５の予約コードセットに
示されている予約コードの後に置かれた第１利用可能コードに初期化される。従
って、図示の実施形態では、コードカウンタ２３は、２６２にセットされる。ブ
ロック６１では、コードサイズレジスタ１５は、開始コードサイズ、例えば、Ａ
ＳＣＩＩ準拠の実施形態では、９ビットに初期化される。さらに、最大コードレ
ジスタ２０は、コードサイズの対応する最大コードにセットされる。このことか
ら理解されるように、９ビットの最大コードは５１１である。ブロック６０に示
す予約コードとブロック６１に示す最大コードは、以下に説明するように、本発
明によるラン処理で利用される。

【００３０】 ブロック６２では、第１入力文字がフェッチされてカレントマッチレジスタ１
４に入れられ、ブロック６３では、次に続く文字がフェッチされてカレント文字
レジスタ１３に入れられる。カレントマッチレジスタ１４内の値は、カレント文
字レジスタ１３内の次の文字と一緒になって、この分野では周知のように、２文
字ストリングを構成している（例えば、特許第４，５５８，３０２号を参照）。

【００３１】 処理はブロック６４から継続され、そこでは、ディクショナリ３５がサーチさ
れ、カレント文字で連結されたカレントマッチを構成するストリングがディクシ
ョナリ３５にあるかどうかが判断される。ディクショナリサーチプロシージャは
、ブロック６４の機能を実行するものとしてこの分野では周知である（例えば、
特許第４，５５８，３０２号と特許第５，８６１，８２７号を参照）。

【００３２】 ブロック６４で、ストリングがディクショナリ３５内に見つかると、ブロック
６４からのＹＥＳブランチがとられて、ブロック６５に移る。ブロック６５では
、カレントマッチレジスタ１４の内容は、ストリングが見つかったことを示す標
識を含むように更新される。この分野では周知のように、ストリングはコードが
関連付けられており、一般的に、現在マッチしているストリングのストリングコ
ードはカレントマッチレジスタ１４の中にセットされる。ブロック６５の機能が
具体的にどのように実装されているかの詳細は周知である（例えば、特許第４，
５５８，３０２号と特許第５，８６１，８２７号を参照）。現在マッチしている
ストリングでカレントマッチレジスタ１４を更新した後、コントロールはブロッ
ク６３に戻り、次の入力データ文字がフェッチされて、カレント文字レジスタ１
３に入れられる。このようにして、ブロック６３−６５で形成されたループは、
入力データ文字ストリームをディクショナリ３５にストアされたストリングと比
較し、それとの最長マッチが見つけられる。

【００３３】 ブロック６４では、現在マッチしているストリングをブロック６３でフェッチ
された次の文字と連結した結果として、ディクショナリ３５に存在しない延長ス
トリングが得られたときは、ブロック６４からのＮＯブランチがとられて、ブロ
ック６６に移ることになる。ブロック６６では、ディクショナリ３５に見つから
なかったこの延長ストリングはディクショナリに入力され、コードカウンタ２３
の現存コードが、このストアされた延長ストリングに割り当てられる。ブロック
６６の機能が具体的にどのように実装されているかの詳細は周知である（例えば
、特許第４，５５８，３０２号を参照）。

【００３４】 処理はブロック６７へ進み、そこでは、コードカウンタ２３内のコードがテス
トされ、コードサイズの増加が必要であるかどうかが判断される。必要であれば
、処理はブロック６８へ進み、そこでは、コードサイズレジスタ１５が１だけイ
ンクリメントされる。コードサイズの増加が必要である場合、最大コードレジス
タ２０内の値も、新コードサイズに従って増加される。最大コードの値は、新コ
ードサイズのビット数によってサポートされる最大コードまで増加される。例え
ば、１０ビットの最大サイズは、最大コードが（２¹⁰ １）＝ １０２３にな
っている。最大コードレジスタ２０内の値は、以下に図４を参照して説明するよ
うに、本発明のラン処理で利用される。ブロック６７でコードサイズの増加が必
要でなければ、このブロック６８はバイパスされ、処理はブロック６９から継続
される。ブロック６９では、コードカウンタ２３が１だけインクリメントされる
。

【００３５】 処理はブロック７０から継続され、そこでは、カレントマッチのコードが、圧
縮器の出力端１２から得られた圧縮コードストリームの一部として出力される。
カレントマッチのコードは、カレントマッチレジスタ１４から得られる。カレン
トマッチがマルチ文字ストリングであるときは、そのストリングのコードはカレ
ントマッチレジスタ１４に置かれており、ブロック６４に関して上述したように
、ディクショナリ３５に見つかった最長マッチになっている。以上から理解され
るように、ブロック７０で出力されるカレントマッチは、シングル文字となるこ
ともできる。このケースでは、出力コードは文字の値である。ブロック７０の機
能がどのように実装されているかの詳細は、この分野では周知である（例えば、
特許第４，５５８，３０２号と特許第５，８６１，８２７号を参照）。

【００３６】 処理はブロック７４から継続され、そこでは、レジスタ１３内のカレント文字
が、カレント文字の後に続く次のｎ個のルックアヘッド文字と突き合わせテスト
され、これらが同一であるかどうかが判断される。このプロセスは、ルックアヘ
ッドバッファ１６の中にフェッチされた該当文字を利用して、ロジック２４によ
って実行される。例えば、ｎは、便宜上、３に等しくセットすることができる。

【００３７】 ブロック７４では、カレント文字は、カレント文字の後に続く次のｎ個のルッ
クアヘッド文字と比較され、同一文字のランが始まろうとしているかどうかが判
断される。カレント文字が次のｎ個のルックアヘッド文字と同一であれば、ブロ
ック７４のＹＥＳブランチがとられ、ラン処理ブロック７５に移ることになる。
ラン処理ブロック７５の詳細は、図４に示されている。

【００３８】 ｎ個のルックアヘッド文字の１つがカレント文字にマッチ（合致）していなけ
れば、ブロック７４のＮＯブランチがとられ、従来のＬＺＷデータ圧縮処理が続
行される。

【００３９】 従って、処理はブロック７６から続行され、そこでは、カレントマッチレジス
タ１４は、カレント文字レジスタ１３内の文字にセットされる。その後、ブロッ
ク７７で、現在のカレント文字の後に続く次の入力データ文字がフェッチされ、
カレント文字レジスタ１３に入れられる。以上から理解されるように、ブロック
７６では、カレントマッチレジスタ１４は、前の処理でミスマッチとなった入力
データ文字にセットされる。ブロック７６と７７の機能がどのように実装されて
いるかの詳細は、この分野では周知である（例えば、特許第４，５５８，３０２
号と特許第５，８６１，８２７号を参照）。その後、コントロールはブロック６
４に戻り、現在、カレントマッチレジスタ１４に置かれているカレントマッチコ
ードと、現在、カレント文字レジスタ１３に置かれているカレント文字とを使用
して、新しいＬＺＷデータ圧縮サイクルが開始される。

【００４０】 以上から理解されるように、ブロック７４と７５、ブロック６１と６８で最大
コード示している個所、およびブロック６０で予約コードを示している個所を除
き、図３の残り部分は、標準ＬＺＷデータ圧縮処理が行われることを示している
。従って、ＬＺＷデータ圧縮のどの公知実装を利用しても、本発明のＬＺＷデー
タ圧縮側面を実現することが可能である。

【００４１】 引き続き図１乃至図３を参照しながら、図４を参照して説明すると、図４には
、図３のブロック７５でのラン処理の詳細が示されている。ラン処理はブロック
８０から開始され、そこでは、カレント文字レジスタ１３内の文字が圧縮器１０
の出力端１２から得られている。ブロック８１では、カウントレジスタ１７内の
カウントは０にセットされる。処理はブロック８２から続けられ、そこでは、レ
ジスタ１３内のカレント文字が文字一時（Ｔｅｍｐ）レジスタ２１に格納される
。その後、ブロック８３で、カレント文字の後に続く次の文字がフェッチされ、
カレント文字レジスタ１３に入れられる。

【００４２】 ブロック８４では、カレント文字レジスタ１３内のフェッチされた文字は、文
字一時（Ｔｅｍｐ）レジスタ２１内の先行文字と比較され、相互が等しいかどう
かが判断される。カレント文字が文字一時（Ｔｅｍｐ）レジスタ内の文字と等し
ければ、文字ランは継続するので、ブロック８４からのＹＥＳブランチがとられ
る。しかるに、カレント文字が文字一時（Ｔｅｍｐ）レジスタ内の文字と等しく
なければ、文字ランは、カレント文字レジスタ１３に置かれているミスマッチ文
字で終わっている。ブロック８４で、文字ランの終わりが示されたときは、そこ
からＮＯブランチがとられる。

【００４３】 ブロック８４からのＹＥＳブランチはブロック８５に入り、そこでは、カウン
トレジスタ１７内のカウントがテストされ、カウントが１だけインクリメントさ
れたとき、カウント減少プロセスで設定されたリミット２６以下のままになって
いるかどうかが判断される。リミット２６は図２を参照して上述した通りであり
、そこで説明した実装でのリミットは、２０４８０文字に等しくなっている。以
上から理解されるように、このリミットは実装に固有のものであり、図２を参照
して上述したように、別の行をカウント減少テーブル２５に追加することだけで
大幅に大きくすることが可能である。

【００４４】 Ｃｏｕｎｔ＋１がブロック８５でリミット以下であれば、処理はブロック８６
から続けられ、そこでは、カウントレジスタ１７内のカウントが１だけインクリ
メントされる。従って、カウントレジスタ１７内のランカウントは、ブロック８
３でフェッチされたばかりのラン文字で、ブロック８４で文字一時（Ｔｅｍｐ）
レジスタ２１内の文字にマッチ（合致）するラン文字をカウントするようにイン
クリメントされる。その後、処理はループに入ってブロック８２に戻り、ランの
文字のカウントが続けられる。

【００４５】 ブロック８１−８６では、ランの文字をカウントするためのロジックが実行さ
れる。他のロジック構成を利用してこの機能を実行するようにしても、同じ効果
が得られる。

【００４６】 ランがブロック８４で終了していたか、あるいは次のカウントがブロック８５
でリミットよりも大きくなる場合には、それぞれのＮＯブランチはブロック９０
に進むことになる。ブロック９０では、テストが行われ、カウントレジスタ１７
内のカウントがコードカウンタ２３内のコードを差し引いた最大コードより小で
あるか等しいかどうかが判断される。ブロック９０のテストは、ブロック８１−
８６で設定されたラン文字のカウントを受け入れるだけの十分なカウントが、カ
レントコードサイズでコードカウンタ２３に残っているかどうかを判断するため
に行われる。そうであれば、どの特殊な予約コードを使用しなくても、ラン文字
のカウントを伸張器に送って、ラン情報が受信されようとしていることを伸張器
に知らせることができる。

【００４７】 従って、ブロック９０からのＹＥＳブランチがとられてブロック９１に移り、
そこでは、カウントレジスタ１７内のカウントがコードカウンタ２３からのコー
ドに加算され、その結果の値はカウントレジスタ１７内にセットされる。その後
、処理はブロック９２に移り、そこでは、カウンタレジスタ１７内のカウントが
圧縮器１０の出力端１２から得られる。

【００４８】 その後、処理は図３のブロック７６に戻り、ＬＺＷ処理ループに再び入る。

【００４９】 ブロック９０で、カウントがコードカウンタ内のコードを差し引いた最大コー
ドより大であれば、ブロック９０からのＮＯブランチがとられ、ブロック９３に
移る。ブロック９３は、ラン文字のカウントが大きすぎて、ブロック９１と９２
の処理では受け入れられないとき使用される処理への入口である。ブロック９３
の後に続く処理は、図２を参照して上述したように、カウント減少テーブル２５
に示されているプロシージャを使用する。ブロック９３から入った処理では、圧
縮器１０は、テーブル２５に示されている予約コードの１つを出力することによ
って、ランが出現したことを通知する。

【００５０】 従って、ブロック９３では、カウントがテストされ、それがシステム最大コー
ドより小であるかどうかが判断される。そうであれば、処理はブロック９４へ移
り、そこでは、予約コードレジスタ２２は第１予約コード値にセットされる。図
２のテーブル２５の１行目に示すように、図示の実施形態の第１予約コードは２
５７になっている。

【００５１】 ブロック９５では、現在予約コードレジスタ２２に入っている第１予約コード
値は、圧縮器１０の出力端１２に現れる。その後、ブロック９６で、カウントレ
ジスタ１７からのカウントは圧縮器１０の出力端１２に現れる。圧縮器１０は、
システム最大コードサイズを使用してこのカウン値を出力する。上述したように
、最大コードサイズは、開示されている実施形態では、１２ビットになっている
。他のビットとコードサイズを利用して本発明を実施しても、同じ効果が得られ
る。ブロック９６からの処理は図３のブロック７６に戻り、ＬＺＷ処理ループに
再び入る。

【００５２】 ブロック９３で、カウントがシステム最大コードより小でないときは、処理は
、その後にブロック９８が続くブロック９７に入る。ブロック９７と９８では、
事前決定プロセスは、図２を参照して上述したように、カウントレジスタ１７内
のカウントの値に従ってプロセス５０−５３から選択される。従って、ブロック
９７では、図２に示すように、カウントレジスタ１７内のカウントは、選択され
た事前決定プロセスによって減少され、減少カウントがシステム最大コードより
小になるようにされる。この減少カウントは、その後、カウンタレジスタ１７内
にセットされる。例えば、減少前のカウントが３×２¹²より大か等しく、４×２ ¹² より小であれば、プロセス５２が選択され、そこでは、カウントレジスタ１７
内のカウントは３×２¹²だけ減少される。

【００５３】 ブロック９８では、予約コードレジスタ２２は、選択された事前決定プロセス
に対応する予約コード値にセットされる。従って、事前決定プロセス５２が選択
されたときは、予約コードレジスタ２２は２６０にセットされる。

【００５４】 その後、処理はブロック９５と９６から続けられ、そこでは、予約コードレジ
スタ２２からの予約コードとカウントレジスタ１７からのカウントは、ブロック
９７と９８で処理されたランが出現したことを通知し、そのランカウントを伝え
るために出力される。その後、処理は図３のブロック７６に戻り、ＬＺＷデータ
処理ループに再び入る。

【００５５】 ブロック９３−９８の処理から理解されるように、非常に大きなランを本発明
のシステムで受け入れることが可能である。図示の具体的実施形態では、事前決
定プロセス５３を利用して２０４７９文字ランを受け入れることが可能になって
いる。

【００５６】 引き続き図１を参照しながら、図５を参照して説明すると、図５には、入力端
１１１から入力された圧縮コードのストリームを伸張し、回復されたデータ文字
のストリームを出力端１１２から出力するデータ伸張器１１０が示されている。
図から理解されるように、圧縮器１０（図１）の出力端１２からの圧縮コードス
トリームは、伸張器１１０の入力端１１１に入力されると、圧縮器１０の入力端
１１に入力されたオリジナル入力データ文字ストリームが回復されて、伸張器１
１０の出力端１１２から出力されることになる。

【００５７】 伸張器１１０はワーキングレジスタを具備している。これらのレジスタは、カ
レントコードレジスタ１１３、先行コードレジスタ（Ｐｒｅｖｉｏｕｓ Ｃｏｄ
ｅ ｒｅｇｉｓｔｅｒ）１１４、コードサイズレジスタ１１５、およびカウント
レジスタ１１７と名付けられている。伸張器１１０は、さらに、以下で説明する
ように、到来圧縮コードを処理するために使用されるコード値を順次に生成する
ためのコードカウンタ１２３を含んでいる。以下の説明から理解されるように、
コードカウンタ１２３は、図１の圧縮器１０のコードカウンタ２３とロックステ
ップ（ｌｏｃｋ−ｓｔｅｐ）関係を保っている。

【００５８】 また、伸張器１１０は、データ文字ランを表している到来圧縮コードを処理す
るときに利用されるカウント増加テーブル（Ｃｏｕｎｔ Ｉｎｃｒｅａｓｅ Ｔ
ａｂｌｅ）１２５も含んでいる。カウント増加テーブル１２５の詳細は、図６を
参照して以下に説明されている。また、カウント増加テーブル１２５と一緒に利
用されて、到来減少カウント値を該当ランカウント値に復元するためのカウント
増加ロジック１２７も含まれている。カウント増加ロジック１２７とカウント増
加テーブル１２５は、図１の圧縮器１０のカウント減少ロジック２７とカウント
減少テーブル２５によって行われるカウント減少とは逆の働きをする。

【００５９】 伸張器１１０には、さらに、以下で説明するように、図７と図８のオペレーシ
ョンフローチャートに従って伸張器１１０のオペレーションを制御するコントロ
ール１３０が含まれている。

【００６０】 ディクショナリ１３５は、受け取られた圧縮コード入力に対応するデータ文字
ストリングをストアするために含まれている。伸張器１１０のオペレーションで
は、ディクショナリ１３５の内容は、図１の圧縮器１０のディクショナリ３５の
内容と同一に維持されている。ディクショナリ１３５は、双方向データバス１３
６と制御バス１３７を介して伸張器１１０に結合されている。

【００６１】 伸張器１１０には、入力端１１１から受け取られた入力圧縮コードを置いてお
くための入力コードバッファ１４０が含まれている。個々の入力コードは、以下
に説明するオペレーションに従って、入力コードバッファ１４０からバス１４１
を経由して、カレントコードレジスタ１１３に入力される。伸張器１１０は、入
力コードバッファ１４０から制御バス１４２を経由して入力コードを取得するこ
とを制御している。

【００６２】 要約して説明すると、伸張器１１０のオペレーションは次の通りである。カレ
ントコードレジスタ１１３にフェッチされたコードが調べられ、それがコードカ
ウンタ１２３の現存コードより大であるかどうかが判断される。そうであれば、
入力コードは、コードカウンタ１２３内の現存コードを、受け取られた入力コー
ドから減算することによって回復されたランカウントを表している。入力カレン
トコードが予約コードと等しければ、次の後続コードがフェッチされ、これはラ
ンカウントである。受け取られたランカウント値は、特定の予約コードの値に従
って処理される。入力データが文字ランを表しているどちらの場合も、文字は先
行コードレジスタ１１４から取得され、ランカウントは、以下で詳しく説明する
ように取得される。

【００６３】 入力カレントコードがコードカウンタ１２３の現存コードより小か等しければ
、標準ＬＺＷデータ圧縮が実行されて、入力カレントコードに対応するデータ文
字ストリングが回復される。延長ストリングは、ＬＺＷデータ圧縮の分野では周
知のように、ディクショナリ１３５にストアされる。

【００６４】 引き続き図５を参照しながら、図６を参照して説明すると、図６には、カウン
ト増加テーブル１２５の詳細が示されている。行１５０−１５３に示すように、
ランカウントは、図示のように、受け取られたそれぞれの予約コードに従って図
示の値を受け取られたコードに加算することによって、伸張器１１０で受け取ら
れた入力コードから回復される。具体的には、テーブル１２５の行１５０−１５
３は、予約コード２５８−２６１を受け取ると、それぞれに応答してカウントが
、それぞれ２¹²、２×２¹²、３×２¹²、または４×２¹²だけ増加されることを示
している。予約コード２５７に応答して、受け取られたカウントは、以下で詳し
く説明するように、増加されることなく直接に使用される。テーブル１２５の１
行目は、この関係を示している。

【００６５】 図７と図８のコントロールフローチャートは、伸張器１１０によって実行され
るオペレーションの詳細を示している。コントロール１３０は、ステートマシン
のように、オペレーションの実行を制御する該当回路を内蔵しているものと考え
られている。

【００６６】 引き続き図５と図６を参照しながら、図７を参照して説明すると、ブロック１
６０では、コードカウンタ１２３は、図３のブロック６０に関連して上述したの
と同じように初期化される。ブロック１６１では、コードサイズレジスタ１１５
は、図３のブロック６１に関連して上述したように、開始コードサイズに初期化
される。

【００６７】 ブロック１６２では、第１または次の入力圧縮コードがフェッチされ、カレン
トコードレジスタ１１３に入れられる。コントロールがブロック１６１からブロ
ック１６２に移ったときは、フェッチされるコードは第１コードになる。コント
ロールがラン処理からの図示リターン経路を通ってブロック１６２に入ったとき
は、フェッチされるコードは、第１コードではなく、次のコードになる。

【００６８】 ブロック１６３では、伸張器１１０は、カレントコードレジスタ１１３にフェ
ッチされた圧縮コードに対応するデータ文字のストリングを、その出力端１１２
から出力する。ディクショナリ１３５を使用してデータ文字ストリングを入力圧
縮コードから回復することは、ＬＺＷデータ圧縮の分野では周知である。ブロッ
ク１６３の機能が実装されている、多数の具体例は周知である（例えば、特許第
４，５５８，３０２号を参照）。

【００６９】 以上から理解されるように、カレントコードレジスタ１１３にフェッチされた
コードは、シングル文字ストリングを表している場合もあれば、マルチ文字スト
リングを表している場合もある。周知のように、このようなストリングは、コー
ドの値によって相互に区別されている。一般的に、マルチ文字ストリングは、ブ
ロック１６０に関連して上述した第１利用可能コードより大か等しいコードによ
って表されている。シングル文字ストリングを表すコードは、シングル文字に等
しい、つまり、シングル文字を表す値になっているので、第１利用可能コードよ
りも値が小さくなっている。

【００７０】 ブロック１６４では、カレントコードレジスタ１１３内のコードが先行コード
レジスタ１１４に転送される。ブロック１６５では、次の入力圧縮コードがカレ
ントコードレジスタ１１３にフェッチされる。

【００７１】 ブロック１６６では、カレントコードレジスタ１１３内のコードがテストされ
、それが予約コードに等しいかどうかが判断される。図示の実施形態では、予約
コードは、図６のカウント増加テーブル１２５に示すように２５７−２６１にな
っている。カレントコードが予約コードに等しくなければ、ブロック１６６から
のＮＯブランチがとられ、ブロック１６７に移る。ブロック１６７では、カレン
トコードレジスタ１１３内のコードがテストされ、それがコードカウンタ１２３
内の現存コードより大であるかどうかが判断される。カレントコードがコードカ
ウンタより大でなければ、ブロック１６７からのＮＯブランチがとられ、ブロッ
ク１６９に移る。

【００７２】 しかるに、カレントコードが予約コードに等しければ、ブロック１６６からの
ＹＥＳブランチがとられ、ラン処理ブロック１６８に移る。同様に、カレントコ
ードがコードカウンタより大であれば、ブロック１６７からのＹＥＳブランチが
とられ、ラン処理ブロック１６８に移る。伸張ラン処理の詳細は、以下に図８を
参照して説明されている。ランのコード（１つまたは複数の）が処理され、その
ランが回復されると、コントロールはブロック１６２に戻る。

【００７３】 ブロック１６９では、カレントコードレジスタ１１３内のコードがテストされ
、それがコードカウンタ１２３の現存コードより小であるか等しいかどうかが判
断される。（「より小」のテストだけが使用されるのは、ブロック１６６と１６
７の先行テストのためである）。カレントコードがコードカウンタより小であれ
ば、ブロック１６９からのＹＥＳブランチがとられ、ブロック１８０−１８５の
シーケンスに移る。カレントコードがコードカウンタに等しければ、ブロック１
６９からのＮＯブランチがとられ、ブロック１９０と１９１のシーケンスに移る
。以上から理解されるように、ブロック１８０−１８５は、周知の通常ＬＺＷデ
ータ伸張処理を表し、ブロック１９０と１９１は、周知の例外ケースＬＺＷデー
タ伸張処理を表している（例えば、特許第４，５５８，３０２号を参照）。

【００７４】 ブロック１８０では、カレントコードレジスタ１１３内のコードに対応するデ
ータ文字ストリングが、その出力端１１２から伸張器１１０によって出力される
。

【００７５】 ブロック１８１では、先行コードレジスタ１１４内のコードに対応していて、
カレントコードレジスタ１２３内のコードに対応するストリングの第１文字によ
って延長されたストリングを構成する延長ストリングをストアすることにより、
ディクショナリ１３５が更新される。このストアされた延長ストリングには、コ
ードカウンタ１２３の現存コードのストリングコード値が割り当てられる。

【００７６】 従来のＬＺＷ実装では、先行コードレジスタ１１４内のコードは、コードカウ
ンタ１２３によって割り当てられたコードが示しているロケーションに、延長文
字と一緒にディクショナリ１３５にストアされている。

【００７７】 ブロック１８２−１８４では、コードカウンタ１２３は１だけ進められ、コー
ドサイズのインクリメントは必要であれば行われる。コードサイズの増加が必要
でなければ、ブロック１８２のテストの結果、コードサイズインクリメントブロ
ック１８３はバイパスされることになる。コードサイズレジスタ１１５はこのプ
ロセスで利用される。コードカウンタ１２３を次のコードへインクリメントする
ことは、ブロック１８４で行われる。

【００７８】 ブロック１８５では、カレントコードレジスタ１１３内のコードは、先行コー
ドレジスタ１１４に転送される。従来のＬＺＷデータ伸張では、ブロック１８５
で先行コードレジスタ１１４内にセットされた先行コードは、その後に続くＬＺ
Ｗデータ伸張サイクルにおいて、ブロック１８１のディクショナリ更新機能で利
用されている。本発明のラン処理では、この先行コードは、図８を参照して以下
で説明するように、ラン文字を定義するために利用されている。ブロック１８５
からのコントロールはブロック１６５に戻される。

【００７９】 ＬＺＷ例外ケース処理が必要である場合は、ブロック１６９からのＮＯブラン
チがとられ、ブロック１９０に移り、そこでは、先行コードレジスタ１１４内の
コードに対応するストリングがそのストリングの第１文字によって延長され、伸
張器１１０の出力端１１２から得られる。ブロック１９１では、ブロック１９０
のこの延長ストリングは、コードカウンタ１２３内のコードの割り当てコードと
一緒にディクショナリ１３５にストアされる。その後、コントロールは前述した
ようにブロック１８２に進む。

【００８０】 図７のブロック１６０−１６５、１６９、１８０−１８５および１９０−１９
１は、従来のＬＺＷデータ伸張器によって実行される処理を構成している。これ
らの機能を実行するための実装は、多数のものが知られている（例えば、特許第
４，５５８，３０２号を参照）。

【００８１】 ブロック１６６−１６８は、従来のＬＺＷ伸張器に組み込まれた本発明による
伸張ラン処理を構成している。

【００８２】 図７から理解されるように、ブロック１８０−１８５と１９０−１９１の従来
のＬＺＷ処理では、処理がブロック１６５に戻されて、次のコードをカレントコ
ードレジスタ１１３にフェッチしている。これとは異なり、ブロック１６８のラ
ン処理では、処理はブロック１６２に戻されている。このようにすると、ランが
処理された後、ブロック１６４で先行コードレジスタ１１４が再初期化されるの
で、伸張器１１０は、圧縮器１０からの出力と同期を保ったままになるという効
果がある。

【００８３】 引き続き図５−７を参照しながら、図８を参照して説明すると、図８には、図
７のラン処理ブロック１６８の詳細が示されている。図７のブロック１６６と１
６７に関連して上述したように、カレントコードレジスタ１１３内のコードが予
約コードに等しくないが、コードカウンタ１２３内の現存コードより大であれば
、コントロールは図７のブロック１６７から図８のブロック２００へ移ることに
なる。ブロック２００では、コードカウンタ１２３内の現存コードは、カレント
コードレジスタ１１３内のコードから減算され、その結果はカウントレジスタ１
１７内にセットされる。ブロック２０１では、伸張器１１０は、カウントレジス
タ１１７内の数に等しい回数だけ、先行コードレジスタ１１４内に置かれている
文字を、その出力端１１２から反復的に出力する。このようにして、伸張器１１
０は、圧縮器１０によって圧縮されたデータ文字ランを回復する。その後、コン
トロールは図７のブロック１６２に戻される。

【００８４】 カレントコードレジスタ１１３内の入力コードが、図６のカウント増加テーブ
ルに示された予約コードと等しければ、コントロールは図７のブロック１６６か
ら図８のブロック２０２へ移される。ブロック２０２では、次の入力コードは、
システム最大サイズを使用してカウントレジスタ１１７にフェッチされる。ブロ
ック２０３では、テストが行われ、カレントコードが第１予約コード値に等しい
かどうかが判断される。ここで説明している実施形態では、第１予約コードは、
図６に示すように、２５７になっている。ブロック２０３で、カレントコードが
第１予約コードに等しければ、コントロールはブロック２０１に移り、関連デー
タ文字ランが前述したように回復される。

【００８５】 しかるに、ブロック２０３で、カレントコードが第１予約コードに等しくなけ
れば、コントロールはブロック２０４に移り、そこでは、カウントレジスタ１１
７内のコードは、カレントコードレジスタ１１３内の別の予約コード値に対応す
る、選択された事前決定プロセスによって増加される。前述したように、カウン
ト増加テーブル１２５は、図６にその詳細を示すように、それぞれが予約コード
２５８−２６１に対応する特定の事前決定プロセス１５０−１５３を示している
。受け取られる予約コードに応じて、カウントは図示のように増加される。その
後、処理は、前述したようにブロック２０１から続けられて、関連データ文字ラ
ンが回復される。

【００８６】 前述したことから理解されるように、図示の実施形態では、２０４７９文字の
ランを受け入れることが可能である。図６のカウント増加テーブル１２５に別の
行を追加するだけで、もっと長いランを伸張器１１０で受け入れることも可能で
ある。当然のことであるが、前述したように、図２のカウント減少テーブル２５
には対応する別の行が追加されることになる。

【００８７】 以上から理解されるように、図８のブロック２００、２０３および２０４の機
能は、図５のカウントレジスタ１１７、コードカウンタ１２３およびカウント増
加テーブル１２５を使用して図５のカウント増加ロジック１２７によって実行さ
れる。

【００８８】 上述したラン処理のいずれにおいても、以上の説明から理解されるように、ラ
ン文字は図４の圧縮器ブロック８０で送信され、伸張器側では、図７のブロック
１８５の処理結果として、先行コードレジスタ１１４に都合よく置かれている。

【００８９】 引き続き図２、４、６、７および８を参照して説明すると、これらの図から理
解されるように、圧縮器（図２と図４）によって適用されるラン処理がどのよう
なものであっても、そのラン処理は伸張器のラン処理（図６と図８）によって逆
にされ、その結果、オリジナルラン入力データが回復される。

【００９０】 図４のブロック９０−９２の圧縮器処理は、図７と図８のブロック１６７、２
００および２０１によって逆にされる。本発明のこの側面では、ランのカウント
は、ブロック９１と９２の処理によって送信される。ランカウントと圧縮器コー
ドカウンタの現存コードの和は、ブロック９２で出力され、伸張器処理のブロッ
ク２００では、伸張器コードカウンタの現存コードは受け取られたコードから減
算されて、ランカウントが回復される。伸張器は、受け取られたコードが伸張器
コードカウンタの現存コードより大であることを、ブロック１６７で検出するこ
とにより、この文字ラン状態を認識する。本発明のこの処理を使用すると、ラン
の存在を知らせるために、予約コードを圧縮器から伸張器に送信しないで済むこ
とになる。

【００９１】 図４のブロック９３−９６の圧縮器処理は、図７と図８の伸張器ブロック１６
６と２０１−２０３によって逆にされる。このケースでは、第１予約コード値は
、この特定処理を伸張器に知らせるために利用される。上述した実施形態では、
予約コード値は２５７が使用されている。この処理では、ランカウントは、この
第１予約コードに続いて圧縮器によって送信される。伸張器は、この第１予約コ
ードを受け取ると、受け取ったランカウントを利用して文字ランを回復する。

【００９２】 図４のブロック９３、９７、９８、９５および９６の圧縮器ラン処理は、ブロ
ック１６６と２０１−２０４の伸張器処理によって逆にされる。ブロック９７と
９８の圧縮器処理では、ランカウントは、カウントがシステム最大コードより小
になるように、選択された事前決定プロセスによって減少され、選択された事前
決定プロセスに対応する予約コードが利用される。伸張器処理は予約コードを認
識し、選択された事前決定プロセスの逆プロセスを利用することによって、受け
取られたカウントをオリジナルランカウント値まで増加して、オリジナル文字ラ
ンを回復する。図２の圧縮器事前決定プロセス５０−５３は、それぞれ図６の伸
張器事前決定プロセス１５０−１５３に対応している。以上から明らかであるよ
うに、図６の伸張器事前決定プロセスは、図２の圧縮器事前決定プロセスを逆に
したものである。

【００９３】 本発明の上述した実施形態では、コード長が可変であるものとして説明されて
いる。上述した実施形態は、容易に理解できる若干の修正を加えることで、固定
コード長の環境で利用することも可能である。例えば、固定コード長の実施形態
では、１２ビットの固定コードサイズを利用することができる。このような構成
では、最大システムコードは４０９６になる。

【００９４】 固定コード長の実施形態では、図１と図５のコードサイズレジスタ１５と１１
５は利用されることがない。同様に、図３のブロック６１、６７および６８のコ
ードサイズ初期化、テストとインクメンテーションは、図７の対応するブロック
１６１、１８２および１８３と共に、不要になる。このような実施形態では、最
大コードは固定することになり、固定最大システムコード、例えば、４０９６と
等しくなる。この場合、図３、４、７および８のロジックは、システム最大コー
ドとシステム最大コードサイズが上述したように固定値になることを除けば、同
じままになる。

【００９５】 引き続き図１−４を参照しながら、図９を参照して説明すると、図９には、図
３と図４のフローチャートに従う圧縮器１０のオペレーション例が示されている
。図の上部には、入力データ文字ストリームが示されており、そこでは、順次文
字は文字順序番号で示されている。このようにしたのは、この例のステップを通
る文字の進行にたどって行くのを容易にするためである。当然に理解されるよう
に、順序番号は文字を識別するために示されたもので、実際のデータ文字ストリ
ームの中には現れない。

【００９６】 この例は、大部分が説明しなくても分かるようになっており、実行されるアク
ションは左側の欄に示され、これらのアクションに関係する図３と図４のブロッ
クは右側の欄に示されている。なお、文字 ”ａ” のランは４７文字の長さに
なっており、文字 “ｃ” のランは１５０００文字の長さになっている。

【００９７】 アクション１−８では、標準ＬＺＷデータ圧縮が、文字 “ａ（５）” まで
入力データ文字に対して行われる。いくつかのデータ圧縮サイクルが行われ、各
サイクルでは、右側の欄に示すように、ブロック７４を通りぬけて文字ランのテ
ストが行われる。ブロック７４は処理の中で図３に示す位置に置かれているので
、ディクショナリ３５に存在するすべてのストリングは、ブロック７４でラン処
理を呼び出す前に、図３のブロック６４でマッチングされる。従って、ＬＺＷ処
理は、ラン処理に優先して行われる。

【００９８】 アクション８では、図３のブロック７４は、カレント文字 “ａ（５）” が
、図の上部の入力データ文字ストリームに示すように、次のｎ個のルックアヘッ
ド文字と同一であることを認識する。その後、コントロールはブロック７５に移
り、ラン処理が行われる。以上から理解されるように、図示の文字 “ａ” の
ランは “ａ（４）” から始まっているとしても、文字 “ａ（４）” は、
アクション６でＬＺＷ処理の中に吸収されている。

【００９９】 アクション９では、文字 “ａ（５）” は、図４のブロック８０に従って出
力され、ランカウントが文字 “ａ（６）” から開始される。図４のブロック
８２−８６で構成されたループは文字をカウントし、アクション１２で、ミスマ
ッチ文字 “ｃ（１）” がフェッチされ、図示のように４５でカウントが中止
される。アクション１２では、図４のブロック９０は、図１のカウントレジスタ
１７内のカウント４５が最大コードとコードカウンタ２３内のコード２６６との
差より小であるかどうかを判断する。

【０１００】 アクション１３では、図４のブロック９１と９２はコードカウンタ値２６６を
カウント値４５と加算して、カウント３１１が得られ、出力される。その後、コ
ントロールは図３のブロック７６に戻ってＬＺＷ処理が再開され、そこでは、次
の文字 “ｃ（２）” がフェッチされ、ディクショナリが図示のように更新さ
れる。

【０１０１】 アクション１４−１８では、データ文字 “ｃ” の１５０００文字ランが処
理される。アクション１８では、図４のブロック９０と９３は、処理を図４のブ
ロック９７と９８に指示している。アクション１９では、カウント１４９９８は
、図２のプロセス５２を利用することによってカウント２７１０に減少されてい
る。対応する予約コード２６０は、図示のように図１の予約コードレジスタ２２
内にセットされる。このコードは、アクション１９に示すように図４のブロック
９５で出力され、その後に続いて減少カウント２７１０がアクション２０で出力
される。図４のブロック９６は、カウントの出力を示している。

【０１０２】 アクション２０−２２では、処理は図３のブロック７６でＬＺＷデータ圧縮に
戻る。

【０１０３】 図３と図４のブロックに関連する図９のアクションの、これ以上詳しい説明は
容易に理解されるので、簡略化のためにその説明は省略することにする。

【０１０４】 引き続き図５、６、７および８を参照しながら、図１０を参照して説明すると
、図１０には、図７と図８のフローチャートに従う伸張器１１０のオペレーショ
ン例が示されている。図１０のフォーマットは全体的に図９のフォーマットに類
似しているので、図９に関連して上述した説明は図１０に適用できる。図１０の
上部にある入力圧縮コードストリームは、図９に示す圧縮器の出力である。図か
ら明らかであるように、図１０の出力は、図９の上部に示す回復データ文字スト
リームである。

【０１０５】 アクション１−５では、従来のＬＺＷ伸張が行われ、文字 “ａ（５）” ま
でのオリジナルデータ文字ストリームが回復される。なお、ＬＺＷ例外ケース処
理はアクション４で行われ、そこでは、受け取られたカレントコードは伸張器コ
ードカウンタに等しくなっている（図７のブロック１６９のＮＯブランチ）。

【０１０６】 アクション６では、文字 “ａ” のランは、コード３１１を受け取ると、そ
れに応答して処理される。このケースでは、受け取られた圧縮コードは、伸張器
コードカウンタ内の値２６６より大になっている。図７のブロック１６７は処理
を図８のブロック２００と２０１に指示し、ラン文字の回復が行われる。アクシ
ョン７と８では、コントロールは図７のブロック１６２でＬＺＷ処理に戻り、文
字 “ｃ” のランの先頭が検出される。

【０１０７】 アクション９と１０では、文字 “ｃ” のランが処理される。アクション９
では、予約コード２６０が受け取られたことが、図７のブロック１６６で検出さ
れ、図８のブロック２０１−２０４のラン処理が呼び出される。アクション９で
は、カウント２７１０が受け取られ、アクション１０でランカウント１４９９８
に変換される。この変換は、図６のプロセス１５２を使用して図８のブロック２
０４で行われる。

【０１０８】 アクション１１−１３では、従来のＬＺＷ伸張により、入力圧縮コードストリ
ームの残り部分が復号化（デコード）される。図７と図８のブロックに関連する
図１０のアクションのこれ以上詳しい説明は容易に理解されるので、簡略化のた
めにその説明は省略されている。

【０１０９】 図３から理解されるように、ブロック７４のラン検出とブロック７５のラン処
理は、図３のＬＺＷ圧縮サイクルの途中個所に置かれ、ＬＺＷサイクルのその個
所では、最長マッチが出力され、ディクショナリが延長ストリングで更新され、
ミスマッチを引き起こした文字がフェッチされ、カレント文字レジスタ内に置か
れている。このようにすると、ディクショナリにすでにストアされているストリ
ングが完全に圧縮されるという利点が得られる。ミスマッチ文字がランの先頭に
ある場合は、その文字は図４のブロック８０で出力されるので、圧縮器ディクシ
ョナリにストアされているものと同じ延長ストリングを伸張器ディクショナリに
ストアすることが可能になる。図４のラン処理が終了したときは、ランに続くミ
スマッチ文字はカレント文字レジスタにあるので、図３のブロック７６で利用し
て、その個所からＬＺＷ処理を続けることができる。従って、図３のブロック７
６では、ＬＺＷプロセスで利用されたカレントマッチレジスタには、ブロック６
０−７０のＬＺＷ処理からか、あるいはラン処理ブロック７５からのミスマッチ
文字が受け入れられる。

【０１１０】 以上から理解されるように、図２と図６の事前決定プロセスは減算と加算を利
用して、それぞれカウントを減少し、増加している。本発明によれば、他のプロ
シージャを利用して、長いランを処理することが可能である。例えば、減算と加
算よりももっと大きな数を減少し、増加する能力をもつ、他の数学的プロシージ
ャを利用することが可能である。乗算法、除算法、累乗法およびハッシング法を
採用すると、この能力が得られる。

【０１１１】 当然に理解されるように、圧縮器１０と伸張器１１０で利用されているプロト
コルは、相互に対して互換性を有している必要がある。圧縮器と伸張器は、コー
ドサイズのように、同じアルファベットサイズと初期条件にわたって動作する必
要がある。上述した圧縮器と伸張器の実施形態は、ディクショナリが初期化され
ていなくても、シングル文字ストリングのすべてで初期化されていても、ディク
ショナリと共に容易に利用することができる。上述したように、シングル文字は
、それぞれの値によって圧縮コードと区別することができる。シングル文字は、
文字自体の値によって表すことも、他の周知のコーディング方式で表すこともで
きる。圧縮器で使用されるシングル文字プロトコルは、伸張器でも利用されるよ
うになっている必要がある。

【０１１２】 以上から理解されるように、圧縮器への入力は、任意の対応する文字ビットサ
イズをもつ、任意のサイズのアルファベットにわたることができる。例えば、デ
ータ文字は、８ビット文字の２５６文字ＡＳＣＩＩアルファベットのように、あ
るアルファベットにわたって、ＡＳＣＩＩ文字などのテキストにすることができ
る。入力データは、１ビットサイズの文字をもつ２文字バイナリアルファベット
１と０にわたってバイナリ文字にすることもできる。このことから理解されるよ
うに、テキストデータは、基礎となるバイナリデータの２文字アルファベットに
わたって圧縮することも可能である。

【０１１３】 以上の説明から理解されるように、本発明の上述した実施形態は、ハードウェ
ア、ファームウェア、ソフトウェア、またはこれらの組み合わせで実現すること
が可能である。ディスクリート回路コンポーネントは、上述した種々の機能を実
行するように容易に実現することができる。ソフトウェアによる実施形態では、
該当モジュールは、上述したフローチャートから容易に生成されるコーディング
でプログラミングされたものが利用できる。

【０１１４】 以上、本発明の好適実施形態について説明してきたが、当然に理解されるよう
に、そこで使用されているワードは限定的ワードではなく、記述的ワードであり
、広い側面での本発明の真の範囲と精神から逸脱しない限り、特許請求の範囲内
で種々の変更を行うことが可能である。

【図面の簡単な説明】

【図１】 本発明に従ってデータを圧縮するデータ圧縮器を示す概略ブロック図である。

【図２】 図１のカウント減少テーブルの詳細を示すチャートである。

【図３】 本発明に従ってデータ圧縮を行うために図１の圧縮器によって実行されるオペ
レーションを示すコントロールフローチャートである。

【図４】 本発明の特徴に従ってデータ圧縮を行うために図３のフローチャートに利用さ
れているラン処理ロジックを示すコントロールフローチャートである。

【図５】 図１の圧縮器によって圧縮されたデータを回復するために本発明に従って具現
化されているデータ伸張器を示す概略ブロック図である。

【図６】 図５のカウント増加テーブルの詳細を示すチャートである。

【図７】 本発明に従ってデータ伸張を行うために図５の伸張器によって実行されるオペ
レーションを示すコントロールフローチャートである。

【図８】 本発明の特徴に従ってデータ伸張を行うために図７のフローチャートに利用さ
れているラン処理ロジックを示すコントロールフローチャートである。

【図９】 図３と図４のコントロールフローチャートに従う図１の圧縮器のオペレーショ
ンを例示するチャートである。

【図１０】 図７と図８のコントロールフローチャートに従う図５の伸張器のオペレーショ
ンを例示するチャートである。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＣＹ， ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，Ｉ Ｔ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＧＷ，ＭＬ， ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＧＭ，Ｋ Ｅ，ＬＳ，ＭＷ，ＭＺ，ＳＤ，ＳＬ，ＳＺ，ＴＺ，ＵＧ ，ＺＷ)，ＥＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ， ＲＵ，ＴＪ，ＴＭ)，ＡＥ，ＡＬ，ＡＭ，ＡＴ，ＡＵ， ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，Ｃ Ｎ，ＣＲ，ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＤＭ，ＥＥ，ＥＳ ，ＦＩ，ＧＢ，ＧＤ，ＧＥ，ＧＨ，ＧＭ，ＨＲ，ＨＵ， ＩＤ，ＩＬ，ＩＮ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，Ｋ Ｒ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ ，ＭＡ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ， ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，Ｓ Ｉ，ＳＫ，ＳＬ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＴＺ，ＵＡ ，ＵＧ，ＵＺ，ＶＮ，ＹＵ，ＺＡ，ＺＷ

Claims (52)

【特許請求の範囲】
1. 【請求項１】 データ文字の入力ストリームを圧縮コードの出力ストリーム
   に圧縮するためのデータ圧縮方法であって、ＬＺＷデータ圧縮プロセスを含み、
   該ＬＺＷデータ圧縮プロセスは、データ文字のストリングをストアし、当該スト
   アされたストリングにそれぞれのコードをコードカウンタから割り当て、各々の
   該ストアされたストリングごとに前記コードカウンタをインクリメントするデー
   タ圧縮方法において、 データ文字のランが前記入力ストリームの中にいつ出現しているかを、該入力
   ストリームのあらかじめ決めた数の隣接データ文字が互に同一になっているかを
   検出することによって、検出し、 当該検出されたランの中のデータ文字をカウントして、ランカウントを取得し
   、 該コードカウンタ内の既存コードを前記ランカウントと結合することによって
   修正コードを取得し、 前記入力ストリームを前記ストアされたストリングと比較し、該ストアされた
   ストリングとの最長マッチ（合致）を判断し、それに割り当てられた前記コード
   を取得し、ランが前記入力ストリームの中に出現していないとき前記入力ストリ
   ームを、前記ＬＺＷデータ圧縮プロセスを使用して圧縮することによって、ＬＺ
   Ｗ圧縮コードを取得し、 前記修正コードと前記ＬＺＷ圧縮コードを出力して、前記出力ストリームを取
   得する ことを特徴とする方法。
2. 【請求項２】 請求項１に記載の方法において、前記修正コードを取得する
   ステップでは、前記修正コードがＬＺＷデータ伸張プロセスによって受け取られ
   たとき、受け取られた修正コードを、前記ＬＺＷデータ伸張プロセスで使用され
   たコードカウンタ内の既存コードと結合することによって、前記ランカウントが
   回復されることを特徴とする方法。
3. 【請求項３】 請求項１に記載の方法において、前記出力するステップでは
   、さらに、 前記検出されたランのデータ文字を、前記修正コードに先行して出力する ことを特徴とする方法。
4. 【請求項４】 請求項１に記載の方法において、 前記データ文字のランがいつ出現しているかを検出するステップ、前記検出さ
   れたランの中のデータ文字をカウントするステップ、前記修正コードを取得する
   ステップおよび前記修正コードを出力するステップは、ラン処理を実行するステ
   ップを含み、 前記ＬＺＷデータ圧縮プロセスの前記ストアするステップは、延長ストリング
   をストアするステップを含み、各々の延長ストリングは、前記データストリーム
   内の次の後続データ文字によって延長された最長マッチを含み、 前記方法では、さらに、 最長マッチを判断し、それに対応する延長ストリングをストアし、前記最長マ
   ッチに割り当てられたコードをス得した後で、前記ＬＺＷデータ圧縮プロセスを
   使用するステップの期間に前記ラン処理を実行する ことを特徴とする方法。
5. 【請求項５】 請求項２に記載の方法において、前記修正コードを取得する
   ステップでは、前記ＬＺＷデータ圧縮プロセスの前記コードカウンタ内の前記既
   存コードに前記ランカウントを加算することによって、前記修正コードを取得す
   ることを特徴とする方法。
6. 【請求項６】 請求項５に記載の方法において、前記ランカウントは、前記
   ＬＺＷデータ伸張プロセスの前記コードカウンタ内の前記既存コードを、前記受
   け取られた修正コードから減算することによって回復されることを特徴とする方
   法。
7. 【請求項７】 請求項４に記載の方法において、前記ＬＺＷデータ圧縮プロ
   セスは、前記入力ストリーム内の前記次の後続データ文字をフェッチすると、そ
   の結果として、前記ストアされたストリングとミスマッチが起こるようにして前
   記最長マッチを判断し、 前記フェッチされた入力データ文字はミスマッチ文字であり、 前記実行するステップでは、さらに、前記ミスマッチ文字から始まって前記ラ
   ン処理を実行し、 前記検出するステップでは、前記ランがいつ出現しているかを、あらかじめ決
   めた数の前記隣接データ文字が前記ミスマッチ文字といつ同一になっているかを
   検出することによって、検出する ことを特徴とする方法。
8. 【請求項８】 請求項７に記載の方法において、前記出力するステップでは
   、さらに、前記検出されたランのデータ文字を、前記修正コードに先行して出力
   し、 検出されたランの前記データ文字は前記ミスマッチ文字を含む ことを特徴とする方法。
9. 【請求項９】 データ文字の入力ストリームを圧縮コードの出力ストリーム
   に圧縮するためのデータ圧縮方法であって、ＬＺＷデータ圧縮プロセスを含み、
   該ＬＺＷデータ圧縮プロセスは、データ文字のストリングをストアし、当該スト
   アされたストリングにそれぞれのコードをコードカウンタから割り当て、各々の
   該ストアされたストリングごとに前記コードカウンタをインクリメントすること
   を含むデータ圧縮方法において、 データ文字のランが前記入力ストリームの中にいつ出現しているかを、該入力
   ストリームのあらかじめ決めた数の隣接データ文字が互にいつ同一になっている
   かを検出することによって、検出し、 当該検出されたランの中のデータ文字をカウントして、ランカウントを取得し
   、 選択された事前決定プロセスを使用して、前記ランカウントをあらかじめ決め
   た数以下に減少することによって減少カウントを取得し、 前記選択された事前決定プロセスに対応する予約コードを取得し、 前記入力ストリームを前記ストアされたストリングと比較し、前記ストアされ
   たストリングとの最長マッチ（合致）を判断し、それに割り当てられた前記コー
   ドを取得して、ランが前記入力ストリームの中に出現していないとき前記入力ス
   トリームを、前記ＬＺＷデータ圧縮プロセスを使用して圧縮することによって、
   ＬＺＷ圧縮コードを取得し、 前記予約コード、前記減少カウントおよび前記ＬＺＷ圧縮コードを出力して、
   前記出力ストリームを取得する ことを特徴とする方法。
10. 【請求項１０】 請求項９に記載の方法において、前記減少カウントを取得
    するステップおよび前記予約コードを取得するステップは、前記予約コードと前
    記減少コードとがＬＺＷデータ伸張プロセスによって受け取られたとき、前記選
    択された事前決定プロセスとは逆のプロセスを使用して、受け取られた減少カウ
    ントを増加することにより前記ランカウントが回復されるように前記予約コード
    と前記減少カウントを取得することを特徴とする方法。
11. 【請求項１１】 請求項９に記載の方法において、前記出力するステップで
    は、 検出されたランのデータ文字を、前記予約コードに先行して出力する ことを特徴とする方法。
12. 【請求項１２】 請求項９に記載の方法において、データ文字のランがいつ
    出現しているかを検出するステップ、前記検出されたランの中のデータ文字をカ
    ウントするステップ、前記減少カウントを取得するステップ、予約コードを取得
    ステップおよび前記予約コードと前記減少コードを出力するステップは、ラン処
    理を実行するステップを含み、 前記ＬＺＷデータ圧縮プロセスの前記ストアするステップは、延長ストリング
    をストアするステップを含み、各々の延長ストリングは、前記入力ストリーム内
    の次の後続データ文字によって延長された最長マッチを含み、 前記方法では、さらに、 最長マッチを判断し、それに対応する延長ストリングをストアし、前記最長マ
    ッチに割り当てられたコードを取得した後、前記ＬＺＷデータ圧縮プロセスを使
    用するステップの期間に前記ラン処理を実行する ことを特徴とする方法。
13. 【請求項１３】 請求項１０に記載の方法において、前記選択された事前決
    定プロセスでは、事前決定の定数を前記ランカウントから減少して、該ランカウ
    ントを前記あらかじめ決めた数以下に減少し、 前記予約コードは前記事前決定の定数に対応している ことを特徴とする方法。
14. 【請求項１４】 請求項１３に記載の方法において、前記ランカウントは、
    受け取られた予約コードに対応する事前決定の定数を前記受け取られた減少カウ
    ントに加算することによって回復されることを特徴とする方法。
15. 【請求項１５】 請求項１２に記載の方法において、前記ＬＺＷデータ圧縮
    プロセスは、前記入力ストリーム内の前記次の後続データ文字をフェッチすると
    、その結果として、前記ストアされたストリングとミスマッチが起こるようにし
    て前記最長マッチを判断し、 前記フェッチされた入力データ文字はミスマッチ文字であり、 前記実行するステップは、さらに、前記ミスマッチ文字から始まって前記ラン
    処理を実行し、 前記検出するステップは、前記ランがいつ出現しているかを、あらかじめ決め
    た数の前記隣接データ文字が前記ミスマッチ文字といつ同一になっているかを検
    出することによって検出する ことを特徴とする方法。
16. 【請求項１６】 請求項１５に記載の方法において、前記出力するステップ
    は、さらに、前記検出されたランのデータ文字を、前記修正コードに先行して出
    力し、 前記検出されたランのデータ文字は前記ミスマッチ文字を含んでいることを特
    徴とする方法。
17. 【請求項１７】 圧縮コードの入力ストリームを伸張して、その入力ストリ
    ームに対応するデータ文字の出力ストリームを回復するためのデータ伸張方法で
    あって、ＬＺＷデータ伸張プロセスを含み、該ＬＺＷデータ伸張プロセスは、デ
    ータ文字のストリングをストアし、当該ストアされたストリングにそれぞれのコ
    ードをコードカウンタから割り当て、各々のストアされたストリングごとに前記
    コードカウンタをインクリメントするデータ伸張方法において、 受け取られた入力圧縮コードを、前記コードカウンタ内の既存コードと比較し
    て、前記受け取られた入力圧縮コードがランカウントを表しているかどうかを判
    断し、 該受け取られた入力圧縮コードを前記コードカウンタ内の前記既存コードと結
    合することによって前記ランカウントを回復し、 前記受け取られた入力圧縮コードに先行して受け取られた圧縮コードによって
    表されているデータ文字を反復的に取得し、前記データ文字は、前記回復された
    ランカウントに対応する回数だけ反復的に取得することによって、回復されたラ
    ンを取得し、 受け取られた圧縮コードがランカウントを表していないとき、前記受け取られ
    た圧縮コードに対応する前記ストアされたストリングを、前記ＬＺＷデータ伸張
    プロセスを使用して取得することによって、ＬＺＷ回復ストリングを取得し、 回復されたランと前記ＬＺＷ回復ストリングを出力して、前記出力ストリーム
    を取得する ことを特徴とする方法。
18. 【請求項１８】 請求項１７に記載の方法において、前記比較するステップ
    では、 前記受け取られた入力圧縮コードを前記コードカウンタ内の既存コードと比較
    して、前記受け取られた入力圧縮コードが前記コードカウンタ内の前記既存コー
    ドより大であるかどうかを判断することによって、該受け取られた入力圧縮コー
    ドがランカウントを表していることを判断する ことを特徴とする方法。
19. 【請求項１９】 請求項１７に記載の方法において、前記回復するステップ
    では、 前記コードカウンタ内の前記既存コードを、前記受け取られた入力圧縮コード
    から減算することによって前記ランカウントを回復することにより、該回復され
    たランカウントを取得する ことを特徴とする方法。
20. 【請求項２０】 請求項１７に記載の方法において、前記ＬＺＷデータ伸張
    プロセスの前記ストアするステップでは、延長ストリングをストアし、 前記ストアするステップは、前記先行して受け取られた圧縮コードによって表
    されている前記データ文字によって延長された延長ストリングをストアする ことを特徴とする方法。
21. 【請求項２１】 請求項１７に記載の方法において、 前記受け取られた入力圧縮コードを比較するステップ、前記ランカウントを回
    復するステップ、前記データ文字を反復的に取得するステップ、前記回復された
    ランを出力するステップは、ラン処理を実行するステップを含み、 前記ＬＺＷデータ伸張プロセスは、第１圧縮コードがそこからフェッチされる
    初期処理ポイントを含み、 前記該方法では、さらに、 前記ラン処理を実行した後、前記初期処理ポイントに戻る ことを特徴とする方法。
22. 【請求項２２】 圧縮コードの入力ストリームを伸張して、その入力ストリ
    ームに対応するデータ文字の出力ストリームを回復するためのデータ伸張方法で
    あって、ＬＺＷデータ伸張プロセスを含み、該ＬＺＷデータ伸張プロセスは、デ
    ータ文字のストリングをストアし、当該ストアされたストリングにそれぞれのコ
    ードをコードカウンタから割り当て、各々の前記ストアされたストリングごとに
    前記コードカウンタをインクリメントするデータ伸張方法において、 受け取られた入力圧縮コードが予約コードに等しいかどうかを判断し、そこで
    は前記予約コードは、前記受け取られた予約コードに対応する選択された事前決
    定プロセスによって減少されたランカウントが続くことを表しており、 前記減少されたランカウントをフェッチし、 前記受け取られた予約コードに対応する前記選択された事前決定プロセスとは
    逆のプロセスを使用することによって、前記フェッチされた減少ランカウントを
    増加することによって前記ランカウントを回復し、 前記受け取られた予約コードに先行して受け取られた圧縮コードによって表さ
    れているデータ文字を反復的に取得し、前記データ文字は、前記回復されたラン
    カウントに対する回数だけ反復的に取得することによって、回復されたランを取
    得し、 受け取られた圧縮コードがランカウントを表していないとき、前記受け取られ
    た圧縮コードに対応する前記ストアされたストリングを、前記ＬＺＷデータ伸張
    プロセスを使用して得ることによって、ＬＺＷ回復ストリングを取得し、 回復されたランと前記ＬＺＷ回復ストリングを出力して、前記出力ストリーム
    を取得する ことを特徴とする方法。
23. 【請求項２３】 請求項２２に記載の方法において、前記選択された事前決
    定プロセスでは、前記受け取られた予約コードに対応する事前決定の定数を、前
    記ランカウントから減算することによって、前記減少ランカウントを取得するこ
    とを特徴とする方法。
24. 【請求項２４】 請求項２３に記載の方法において、前記回復するステップ
    では、 前記受け取られた予約コードに対応する前記事前決定の定数を、前記フェッチ
    された減少ランカウントに加算することによって前記ランカウントを回復する ことを特徴とする方法。
25. 【請求項２５】 請求項２２に記載の方法において、前記ＬＺＷデータ伸張
    プロセスの前記ストアするステップは、延長ストリングをストアするステップを
    含み、 前記ストアするステップは、前記先行して受け取られた圧縮コードによって表
    されているデータ文字によって延長された延長ストリングをストアするステップ
    を含む ことを特徴とする方法。
26. 【請求項２６】 請求項２２に記載の方法において、 前記受け取られた入力圧縮コードが予約コードと等しいかどうかを判断するス
    テップ、前記減少ランカウントをフェッチするステップ、前記ランカウントを回
    復するステップ、前記データ文字を反復的に取得するステップおよび前記回復さ
    れたランを出力するステップは、ラン処理を実行するこステップを含み、 前記ＬＺＷデータ伸張プロセスは、第１圧縮コードがそこからフェッチされる
    初期処理ポイントを含み、 前記方法では、さらに、 前記ラン処理を実行した後、前記初期処理ポイントに戻る ことを特徴とする方法。
27. 【請求項２７】 データ文字の入力ストリームを圧縮コードの出力ストリー
    ムに圧縮するためのデータ圧縮装置であって、ＬＺＷデータ圧縮器を含み、前記
    ＬＺＷデータ圧縮器は、データ文字のストリングをストアする手段と、前記スト
    アされたストリングにそれぞれのコードを割り当てるコードカウンタと、各々の
    該ストアされたストリングごとに前記コードカウンタをインクリメントする手段
    とを含むデータ圧縮装置おいて、 データ文字のランが前記入力ストリームの中にいつ出現しているかを、前記入
    力ストリームのあらかじめ決めた数の隣接データ文字が互にいつ同一であるかを
    検出することによって、検出する手段と、 前記検出されたランの中のデータ文字をカウントして、ランカウントを取得す
    る手段と、 前記コードカウンタ内の既存コードを前記ランカウントと結合することによっ
    て修正コードを取得する手段とを含み、 前記ＬＺＷデータ圧縮器は、前記入力ストリームを前記ストアされたストリン
    グと比較して、そのストリングとの最長マッチ（合致）を判断し、そのストリン
    グに割り当てられたコードを得ることによって、ランが前記入力ストリームの中
    に出現していないとき前記入力ストリームを圧縮することにより、ＬＺＷ圧縮コ
    ードを得るように動作し、 前記装置は、さらに、 前記修正コードと前記ＬＺＷ圧縮コードを出力して、前記出力ストリームを取
    得する手段を含む ことを特徴とする装置。
28. 【請求項２８】 請求項２７に記載の装置において、前記修正コードを取得
    する手段は、前記修正コードがＬＺＷデータ伸張器によって受け取られたとき、
    当該受け取られた修正コードを、前記ＬＺＷデータ伸張器におけるコードカウン
    タ内の既存コードと結合することによって前記ランカウントが回復されるように
    前記修正コードを得る手段を含むことを特徴とする装置。
29. 【請求項２９】 請求項２７に記載の装置において、前記出力する手段は、
    さらに、 前記検出されたランのデータ文字を、前記修正コードに先行して出力する手段
    を含むことを特徴とする装置。
30. 【請求項３０】 請求項２７に記載の装置において、 前記データ文字のランがいつ出現しているかを検出する手段、前記検出された
    ランの中の文字をカウントする手段、前記修正コードを取得する手段および前記
    修正コードを出力する手段は、ラン処理を実行する手段を含み、 前記ＬＺＷデータ圧縮器に含まれる前記ストアする手段は、延長ストリングを
    ストアする手段を含み、各々の延長ストリングは、前記入力ストリーム内の次の
    後続データ文字によって延長された最長マッチを含み、 前記実行する手段は、前記ＬＺＷデータ圧縮器が最長マッチを判断し、それに
    対応する延長ストリングをストアし、前記最長マッチに割り当てられたコードを
    取得した後、前記ラン処理を実行するように動作する ことを特徴とする装置。
31. 【請求項３１】 請求項２８に記載の装置において、前記修正コードを取得
    する手段は、 前記ランカウントを、前記ＬＺＷデータ圧縮器の前記コードカウンタ内の前記
    既存コードに加算することによって前記修正コードを取得する手段を含む ことを特徴とする装置。
32. 【請求項３２】 請求項３１に記載の装置において、前記ランカウントは、
    前記ＬＺＷデータ伸張器の前記コードカウンタ内の前記既存コードを、前記受け
    取られた修正コードから減算することによって回復されることを特徴とする装置
    。
33. 【請求項３３】 請求項３０に記載の装置において、前記ＬＺＷデータ圧縮
    器は、前記入力ストリーム内の前記次の後続文字をフェッチすると、その結果と
    して、前記ストアされたストリングとミスマッチになるようにすることによって
    前記最長マッチを判断するように動作し、前記フェッチされた入力データ文字は
    ミスマッチ文字であり、 前記実行する手段は、さらに、前記ミスマッチ文字から始まって前記ラン処理
    を実行する手段を含み、 前記検出する手段は、さらに、前記ランがいつ出現しているかを、前記あらか
    じめ決めた数の前記隣接データ文字が前記ミスマッチ文字といつ同一になってい
    るかを検出することによって、検出する手段を含む ことを特徴とする装置。
34. 【請求項３４】 請求項３３に記載の装置において、前記出力する手段は、
    さらに、前記検出されたランのデータ文字を、前記修正コードに先行して出力す
    る手段を含み、 前記検出されたランの前記データ文字は前記ミスマッチ文字を含む ことを特徴とする装置。
35. 【請求項３５】 データ文字の入力ストリームを圧縮コードの出力ストリー
    ムに圧縮するためのデータ圧縮装置であって、ＬＺＷデータ圧縮器を含み、前記
    ＬＺＷデータ圧縮器は、データ文字のストリングをストアする手段と、前記スト
    アされたストリングにそれぞれのコードを割り当てるコードカウンタと、各々の
    該ストアされたストリングごとに前記コードカウンタをインクリメントする手段
    とをむデータ圧縮装置において、 データ文字のランが前記入力ストリームの中にいつ出現しているかを、該入力
    ストリームのあらかじめ決めた数の隣接データ文字が互にいつ同一になっている
    かを検出することによって、検出する手段と、 前記検出されたランの中のデータ文字をカウントして、ランカウントを取得す
    る手段と、 選択された事前決定プロセスを使用して、前記ランカウントをあらかじめ決め
    た数以下に減少することによって減少カウントを取得する手段と、 前記選択された事前決定プロセスに対応する予約コードを取得する手段と を含み、 前記ＬＺＷデータ圧縮器は、前記入力ストリームを前記ストアされたストリン
    グと比較して、そのストリングとの最長マッチ（合致）を判断し、そのストリン
    グに割り当てられたコードを取得することによって、ランが前記入力ストリーム
    の中に出現していないとき前記入力ストリームを圧縮することにより、ＬＺＷ圧
    縮コードを得るように動作し、 前記装置は、さらに、 前記予約コード、前記減少カウントおよび前記ＬＺＷ圧縮コードを出力して、
    前記出力ストリームを取得する手段を含む ことを特徴とする装置。
36. 【請求項３６】 請求項３５に記載の装置において、前記減少カウントを取
    得する手段および前記予約コードを取得する手段は、前記予約コードと前記減少
    カウントがＬＺＷデータ伸張器によって受け取られたとき、前記選択された事前
    決定プロセスの逆のプロセスを使用することによって前記受け取られた減少カウ
    ントを増加することによって前記ランカウントが回復されるように、該予約コー
    ドと該減少カウントを取得する手段を含むことを特徴とする装置。
37. 【請求項３７】 請求項３５に記載の装置において、前記出力する手段は、
    前記検出されたランのデータ文字を前記予約コードに先行して出力する手段を含
    むことを特徴とする装置。
38. 【請求項３８】 請求項３５に記載の装置において、前記データ文字のラン
    がいつ出現するかを検出する手段、前記検出されたランの中のデータ文字をカウ
    ントする手段、前記減少カウントを取得する手段、前記予約コードを取得する手
    段および前記予約コードと前記減少カウントを出力する前記手段は、ラン処理を
    実行する手段を含み、 前記ＬＺＷデータ圧縮器に含まれる前記ストアする手段は、延長ストリングを
    ストアする手段を含み、各ストリングは前記入力ストリームの中の次の後続デー
    タ文字によって延長された最長マッチを含み、 前記実行する手段は、該ＬＺＷデータ圧縮器が最長マッチを判断し、それに対
    応する延長ストリングをストアし、前記最長マッチに割り当てられたコードを取
    得した後、前記ラン処理を実行するように動作する ことを特徴とする装置。
39. 【請求項３９】 請求項３６に記載の装置において、前記選択された事前決
    定プロセスでは、事前決定の定数を前記ランカウントから減算して、該ランカウ
    ントを前記あらかじめ決めた数以下に減少し、 前記予約コードは前記事前決定の定数に対応している ことを特徴とする装置。
40. 【請求項４０】 請求項３９に記載の装置において、前記ランカウントは、
    前記受け取られた予約コードに対応する前記事前決定の定数を、前記受け取られ
    た減少カウントに加算することによって、回復されることを特徴とする装置。
41. 【請求項４１】 請求項３８に記載の装置において、前記ＬＺＷデータ圧縮
    器は、前記入力ストリーム内の前記次の後続文字をフェッチすると、その結果と
    して、前記ストアされたストリングとミスマッチになるようにすることによって
    前記最長マッチを判断するように動作し、 前記フェッチされた入力データ文字はミスマッチ文字であり、 前記実行する手段は、さらに、前記ミスマッチ文字から始まって前記ラン処理
    を実行する手段を含み、 前記検出する手段は、さらに、前記ランがいつ出現しているかを、前記あらか
    じめ決めた数の前記隣接データ文字が前記ミスマッチ文字といつ同一になってい
    るかを検出することによって、検出する手段を含む ことを特徴とする装置。
42. 【請求項４２】 請求項４１に記載の装置において、前記出力する手段は、
    さらに、前記検出されたランのデータ文字を、前記修正コードに先行して出力す
    る手段を含み、 前記検出されたランのデータ文字は前記ミスマッチ文字を含む ことを特徴とする装置。
43. 【請求項４３】 圧縮コードの入力ストリームを伸張して、その入力ストリ
    ームに対応するデータ文字の出力ストリームを回復するためのデータ伸張装置で
    あって、ＬＺＷデータ圧縮器を含み、前記ＬＺＷデータ伸張器は、データ文字の
    ストリングをストアする手段、当該ストアされたストリングにそれぞれのコード
    を割り当てるコードカウンタ、および各々のストアされたストリングごとに前記
    コードカウンタをインクリメントする手段を含むデータ伸張装置において、 受け取られた入力圧縮コードを、該コードカウンタ内の既存コードと比較して
    、前記受け取られた入力圧縮コードがランカウントを表しているかどうかを判断
    する手段と、 前記受け取られた入力圧縮コードを前記コードカウンタ内の既存コードと結合
    することによって前記ランカウントを回復する手段と、 前記受け取られた入力圧縮コードに先行して受け取られた圧縮コードによって
    表されているデータ文字を反復的に取得する手段であって、そこでは前記データ
    文字は、前記回復されたランカウントに対応する回数だけ反復的に取得すること
    によって、回復されたランを取得する手段と を含み、 前記ＬＺＷデータ伸張器は、受け取られた圧縮コードがランカウントを表して
    いないとき、前記受け取られた圧縮コードに対応する前記ストアされたストリン
    グを取得することにより、ＬＺＷ回復ストリングを得るように動作し、 前記装置は、さらに、 回復されたランと前記ＬＺＷ回復ストリングを出力して、前記出力ストリーム
    を取得する手段を含む ことを特徴とする装置。
44. 【請求項４４】 請求項４３に記載の装置において、前記比較する手段は、 前記受け取られた入力圧縮コードを前記コードカウンタ内の既存コードと比較
    して、前記受け取られた入力圧縮コードが前記コードカウンタ内の既存コードよ
    り大であるかどうかを判断することによって、前記受け取られた入力圧縮コード
    がランカウントを表していることを判断する手段を含むことを特徴とする装置。
45. 【請求項４５】 請求項４３に記載の装置において、前記回復する手段は、 前記コードカウンタ内の前記既存コードを、前記受け取られた入力圧縮コード
    から減算することによって前記ランカウントを回復することによって、回復され
    たランカウントを取得する手段を含むことを特徴とする装置。
46. 【請求項４６】 請求項４３に記載の装置において、前記ＬＺＷデータ伸張
    器に含まれる前記ストアする手段は、延長ストリングをストアする手段を含み、 前記ストアする手段は、前記先行して受け取られた圧縮コードによって表され
    ているデータ文字によって延長された延長ストリングをストアする手段を含む ことを特徴とする装置。
47. 【請求項４７】 請求項４３に記載の装置において、 受け取られた入力圧縮コードを比較する手段、前記ランカウントを回復する手
    段、前記データ文字を反復的に取得する手段および前記回復されたランを出力す
    る手段は、ラン処理を実行する手段を含み、 前記ＬＺＷデータ伸張器は、第１圧縮コードがそこからフェッチされる初期
    処理ポイントを含むように動作し、 前記装置は、さらに、 前記ラン処理を実行した後、前記初期処理ポイントに戻る手段を含む ことを特徴とする装置。
48. 【請求項４８】 圧縮コードの入力ストリームを伸張して、その入力ストリ
    ームに対応するデータ文字の出力ストリームを回復するためのデータ伸張装置で
    あって、ＬＺＷデータ伸張器を含み、該ＬＺＷデータ伸張器は、データ文字のス
    トリングをストアする手段、前記ストアされたストリングにそれぞれのコードを
    割り当てるコードカウンタ、および各々のストアされたストリングごとに前記コ
    ードカウンタをインクリメントする手段を含むデータ伸張装置において、 受け取られた入力圧縮コードが予約コードに等しいかどうかを判断する手段で
    あって、そこで前記予約コードは、該受け取られた予約コードに対応する選択さ
    れた事前決定プロセスによって減少されたランカウントが続くことを表している
    手段と、 前記減少されたランカウントをフェッチする手段と、 受け取られた予約コードに対応する前記選択された事前決定プロセスとは逆の
    プロセスを使用することによって、前記フェッチされた減少ランカウントを増加
    することによって前記ランカウントを回復する手段と、 前記受け取られた予約コードに先行して受け取られた圧縮コードによって表さ
    れているデータ文字を反復的に取得する手段であって、前記データ文字は、前記
    回復されたランカウントに対応する回数だけ得られるようにして、回復されたラ
    ンを取得する手段と を含み、 前記ＬＺＷデータ伸張器は、受け取られた圧縮コードがランカウントを表して
    いないとき、前記受け取られた圧縮コードに対応する前記ストアされたストリン
    グを、ＬＺＷ回復ストリングを取得するように動作し 前記装置は、さらに、 前記回復されたランと前記ＬＺＷ回復ストリングを出力して、前記出力ストリ
    ームを取得する手段を含む ことを特徴とする装置。
49. 【請求項４９】 請求項４８に記載の装置において、前記選択された事前決
    定プロセスは、前記受け取られた予約コードに対応する事前決定の定数を、前記
    ランカウントから減算することによって、前記減少ランカウントを取得すること
    を特徴とする装置。
50. 【請求項５０】 請求項４９に記載の装置において、前記回復する手段は、
    前記受け取られた予約コードに対応する事前決定の定数を、前記フェッチされた
    減少ランカウントに加算することによって前記ランカウントを回復する手段を含
    むことを特徴とする装置。
51. 【請求項５１】 請求項４８に記載の装置において、前記ＬＺＷデータ伸張
    器に含まれる前記ストアする手段は、延長ストリングをストアする手段を含み、 前記ストアする手段は、前記先行して受け取られた圧縮コードによって表され
    ているデータ文字によって延長された延長ストリングをストアする手段を含む ことを特徴とする装置。
52. 【請求項５２】 請求項４８に記載の装置において、 前記受け取られた入力圧縮コードが予約コードと等しいかどうかを判断する手
    段、前記減少ランカウントをフェッチする手段、前記ランカウントを回復する手
    段、データ文字を反復的に取得する手段および前記回復されたランを出力する前
    記手段は、ラン処理を実行する手段を含み、 前記ＬＺＷデータ伸張器は、第１圧縮コードがそこからフェッチされる初期処
    理ポイントを含むように動作し、 前記装置は、さらに、 前記ラン処理を実行した後、前記初期処理ポイントに戻る手段を 含むことを特徴とする装置。