JP3298894B2 - 即時辞書更新がストリング探索とインターリーブされたデータ圧縮解凍システム - Google Patents

Description

【発明の詳細な説明】 発明の背景 1.発明の分野 本発明は辞書ベースのデータ圧縮解凍に関するもので
あり、特に圧縮解凍用の辞書の更新方法に関するもので
ある。

2.従来技術の説明 Lempel−Ziv（LZ）のアルゴリズムはLZ2として知られ
ており、広く使用されている多数の辞書ベースのデータ
圧縮（compression）解凍（decompression）システムの
理論的な基礎を与えるものである。LZ2はJacob ZivとAb
raham Lempelの論文「Compression Of Individual Sequ
ences Via Variable−Rate Coding」,the IEEE Transac
tions on Information Theory,Vol.IT−24,No.5,Septem
ber 1978,pages 530−536に発表されている。LZWとして
知られているあらゆる所で用いられているデータ圧縮解
凍装置は、V.42 bisモデムの圧縮解凍の標準として採用
され、1985年12月10日に発行されたWelchの米国特許第
4,558,302号に記載されている。LZWはまた、GIFおよびT
IFF画像通信規格において用いられるデータ圧縮解凍と
しても採用されている。LZ2の変形は1989年10月24日に
発行されたStorerの米国特許第4,876,541号に記載され
ている。LZ辞書ベースの圧縮解凍装置のその他の例は、
1984年８月７日に発行されたEastman等の米国特許第4,4
64,650号;1989年３月21日に発行されたMiller等の米国
特許第4,814,746号;1992年10月６日に発行されたClark
等の米国特許第5,153,591号;1993年12月８日に発行され
たLempel等の欧州特許出願公告第0 573 208 A1号に記
載されている。

上記の装置では、入力文字データのストリームが辞書
に記載されている文字ストリングと一文字ずつ比較さ
れ、それとの突合せが行われる。一般には、最長の一致
（longest match）が求まるまで、文字ごとの比較が続
けられる。一致に基づいて圧縮コードが出力され、１つ
または２つ以上の追加の文字ストリングで辞書が更新さ
れる。Storerの特許（'541）では、現在の最長一致スト
リングのゼロでないプレフィックスの全てを前の最長一
致ストリングと連結することによって、辞書は更新され
る。従って、現在の最長一致にＮ文字があれば、現在の
最長一致を求めた後でＮストリングが辞書に追加され
る。Storerの特許では、これはAll Prefixes（AP）更新
法と呼ばれている。

他のタイプのデータ圧縮解凍方法はRun−Length Enco
ding（RLE）と呼ばれるものである。RLEのアルゴリズム
は、繰返す文字または文字群のランを、その文字または
文字群とそのラン長さを表す圧縮コードを与えることで
圧縮する。従って、RLEは、同じ文字または文字のグル
ープの長いランを符号化するのに効果的である。例え
ば、RLEはデータファイルのはじめに含まれる長い空白
の連続を圧縮するのに有効である。また、RLEは画像の
圧縮においても有効であり、陸と空の画像の空の部分の
ように、画像が同じ値を持つ連続したピクセルの長いラ
ンを含む場合に有効である。

上記のLZ辞書ベースの圧縮解凍アルゴリズムは繰返す
文字または文字群の長いランを圧縮するのには特に有効
ではない。AP更新法を用いても、長いランを圧縮するに
は、数多くの圧縮コード出力が必要になる。

辞書ベース装置のこのような欠点は、従来はランレン
グスエンコーダにデータを加えて、符号化されたランレ
ングスのデータをLZ辞書ベースの装置に加えることによ
って克服してきた。このようなアーキテクチャにおい
て、ランレングスエンコーダは辞書ベース圧縮器の前端
部で使用されて、ランレングス復号器は辞書ベース解凍
器の出力端で使用される。そのような装置には、装置が
大きくなり、高価で、管理費が高くなり、そして処理時
間が長くなると言う不利がある。

繰返し文字ランを処理する他の手法は、1994年10月19
日公表された英国特許出願GB2 277 179 Aに開示されて
いる。従来のLZ法が入力データ文字ストリームを圧縮
し、その圧縮コードストリームを解凍するために用いら
れている。圧縮アルゴリズムから生じた出力コードは、
現在生成される圧縮コードがランに起因するものかどう
かを確定するために監視される。そうである場合は、ラ
ンが完了したことを監視が指示するまで、圧縮器出力は
ディスエーブルされる。それから、圧縮コードの出力が
再イネーブルされる。受信したコードから、解凍器は抜
けたコードを「埋める。」 発明の概要 本発明は辞書ベースのデータ圧縮解凍装置で実施さ
れ、上記の欠陥を克服する。ストリングＡが辞書中に存
在するとき、ストリングAAA...Aは、その長さに関係な
く２つの圧縮コード記号に符号化される。したがって、
例えば空白やゼロのような繰返し文字のストリング、ま
たは同じ値を持つ連続する画像ピクセルのような文字群
などは、最初の遭遇時に非常に効率よく符号化される。

本発明の圧縮アルゴリズムでは、各入力文字が読まれ
一致照合される間にストリングが圧縮辞書に取込まれ
る。従来は、最長一致が達成されて出力圧縮コード記号
が求まった時に、１つまたは２つ以上の更新ストリング
が辞書に加えられる。アルゴリズムの動作は次の通りで
ある。部分的なストリングＷと文字Ｃが辞書中に存在す
る度に、ストリングPWの拡張文字としてＣを付けた新し
いストリングが辞書に加えられる。ここで、Ｐは最後の
伝送出力圧縮コード記号で送られたストリングである。
したがって、ストリングＷが一致したとき、ストリング
探索プロセスでストリングＰとＷの文字が一致したの
で、ストリングＰはＷの文字で拡張される。これは、
「実行中（on−the−fly）」の辞書更新と呼べるもの
で、辞書の更新は即時であり文字ごとにストリング探索
でインターリーブされる。このように、入力と記憶され
ているストリングＷとの文字ごとの一致照合が行われる
とき、各一致文字が成長するストリングPWの末尾に付加
される。更新プロセスは入力データ文字が辞書中の最長
ストリングＷと一致した時に終わる。

一致照合されるストリングＷが先に一致照合されたス
トリングＰと一致するとき、上記のランレングス符号化
の利点が実現される。このように成った時に、圧縮器は
解凍器では認識されない圧縮コード記号を伝送する。解
凍器は、圧縮辞書と同期を保つために未認識コードプロ
セスを使用するが、このプロセスは、現在割り当てられ
ている解凍コード、未認識コード、先に復号されたスト
リングおよび先に復号されたストリングの文字数に基づ
いている。

図面の簡単な説明 図１は、本発明の実施例において使用されるデータ圧
縮サブシステムの略ブロック図である。

図２は、図１の圧縮器の圧縮コード出力を回復するデ
ータ解凍サブシステムの略ブロック図である。

図3aは、図１および図２の辞書の探索樹のノードの具
象的なデータ構造を示す図である。

図3bは、図１および図２の辞書の探索樹のノードの実
際的なデータ構造を示す図である。

図４は、図3aのデータ構造に従って図１および図２の
辞書の探索樹のノードを図示する概略ノード図である。

図4aは、図４のノードを使用するデータ記憶を図示す
る部分的な探索樹の模式図である。

図５は、図3bのデータ構造に従って図１および図２の
辞書の探索樹のノードを図示する概略ノード図である。

図5aは、図５のノードを使用し図4aと同じストリング
をストアする部分的な探索樹の模式図である。

図６は、本発明にしたがってデータ圧縮を行うために
図１の圧縮サブシステムによって実行される動作を図示
する制御フローチャートである。図６のフローチャート
は全ての単一文字ストリングで初期化される圧縮辞書に
基づいている。

図７は、図６に従って生成される圧縮コードを解凍す
る図２の解凍サブシステムによって実行される動作を図
示する制御フローチャートである。図７のフローチャー
トは全ての単一文字ストリングで初期化される解凍辞書
に基づいている。

図８は、図７および図10の未認識のコード処理を図示
する制御フローチャートである。

図９は、無初期化圧縮辞書に基づく図６に類似の制御
フローチャートである。

図10は、無初期化解凍辞書に基づく図７に類似の制御
フローチャートである。図10の解凍フローチャートは図
９に従って生成される圧縮コードを解凍する。

図11a〜図11eは、代表的な入力データ文字ストリーム
を圧縮する時の圧縮辞書の連続する状態を図示する部分
的な探索樹の模式図である。

図12a〜図12gは、入力データ文字ストリームが繰返し
文字群である時の圧縮辞書の連続する状態を図示する部
分的な探索樹の模式図である。

好ましい実施例の説明 図１において、入力11に加えられる入力データ文字信
号のストリームを出力12の対応する圧縮コード信号のス
トリームに圧縮するデータ圧縮サブシステム10が図示さ
れている。文字ストリングをストアする辞書13は、上に
引用した参考資料に記載の方法で一般にRAMまたはCAMの
ようなメモリで実現されている。文字ストリングは探索
樹データベース構造に公知の方法でストアされている。
探索樹は、辞書13の記憶場所にストアされている互いに
連結されたノードから構成されている。辞書13の記憶場
所には周知の方法でアドレス14でアクセスすることがで
きる。

探索樹ノードのデータ構造はノード番号16、文字フィ
ールド17および関連するノードポインタのフィールド18
を含むノード15で図示されている。ノード番号16は探索
樹のノードを特定し、ノード15が蓄えられているメモリ
アドレス14が便宜上ノード番号として利用される。文字
フィールド17はノードのデータ文字値を含むために用い
られる。フィールド18は、ノード15を親ノード、子供ノ
ードおよび同胞ノードなど関連する探索樹ノードに周知
の方法でリンクするポインタを含んでいる。

圧縮サブシステム10は双方向データバス21と双方向制
御バス22を介して辞書13に結合されている探索／更新制
御部20を含んでいる。探索／更新制御部20は現文字レジ
スタ23、現一致照合レジスタ24（match register）およ
び前一致照合レジスタ25として表されるワーキングレジ
スタを含んでいる。更に、探索／更新制御部20は、圧縮
コード値を辞書13にストアされている文字ストリングに
割り当てるコード発生器26を含んでいる。コード発生器
26はコード番号を逐次に、またはハッシングによるよう
に疑似ランダムに割り当てる。割り当てられたコードに
より、メモリアドレス14を介して辞書13の記憶場所にア
クセスする。このようにして、周知のように、アドレス
14（ノード番号16）は辞書13にストアされているストリ
ングの圧縮コードとして利用される。

探索／更新制御部20は後述の方法で図６および図９の
動作フローチャートに従って圧縮サブシステム10の動作
を制御する制御装置27を含む。

圧縮サブシステム10は入力11で受け取られる入力デー
タ文字ストリームのバッファとして働く文字レジスタ30
を含んでいる。個々の入力データ文字は、後述の動作に
従って文字レジスタ30からバス31を介して現文字レジス
タ23に加えられる。探索／更新制御部20は、制御バス32
を介して文字レジスタ30から入力文字データを受け取る
ことを制御する。

圧縮サブシステム10の動作は簡単に言えば次の通りで
ある。入力データ文字は逐次的に現文字レジスタ23に挿
入され、最長一致が得られるまで辞書13に記憶されてい
るストリングに対して探索が行われる。現一致照合レジ
スタ24はこのプロセスで利用される。最長一致ストリン
グのノード番号16が圧縮コードとして出力12から与えら
れる。これらの探索動作は上記に引用した参考資料に記
載されているものと同じである。本発明にしたがって、
入力データ文字が探索されるストアされた辞書ストリン
グの文字を一致照合する間に、辞書13は、一致照合され
る現入力文字で前圧縮出力コードに応答してストリング
を拡張することによって更新される。前一致照合レジス
タ25はこのプロセスで利用される。前一致照合ストリン
グは、このようにして拡張されるが、入力文字が引き続
き取込まれて一致照合されている間は、一致照合に使用
可能である。したがって、更新ストリングは、文字ごと
のストリング探索とインターリーブされた形で直ちに辞
書13に加えられる。

図１を続いて参照して、図２において、圧縮サブシス
テム10の出力12から供給される圧縮コード信号から元の
入力データストリームの文字を回復する解凍サブシステ
ム40が図示されている。従って、解凍サブシステム40は
入力41で入力圧縮コード信号を受け取り、対応する回復
された文字ストリングを出力42から出力する。解凍サブ
システム40は、好ましくはメモリRAMで実施される辞書4
3を含んでいる。辞書43は、圧縮サブシステム10の辞書1
3に含まれるものと同じ探索樹データベースを含むよう
に構成され、また更新される。各々の入力圧縮コードが
入力41で受け取られるとき、辞書43は、辞書13にストア
されているものと同じデータ文字ストリングを含むよう
に更新される。辞書43にストアされている探索樹データ
ベース構造は辞書43の記憶場所にストアされている互い
にリンクしたノードから構成されている。辞書43の記憶
場所は周知の方法でアドレス44によってアクセスするこ
とができる。

探索樹ノードのデータ構造は、辞書13のノード15に関
して上で説明したように、ノード番号46、文字フィール
ド47および関連するノードポインタのフィールド48を含
むノード45で図示されている。辞書13に関して上で説明
したように、ノード番号46は探索樹ノードを特定し、ノ
ード45がストアされているメモリアドレス44はノード番
号として利用される。文字フィールド47は、ノードのデ
ータ文字値を含むために利用される。フィールド48は、
上記のようにノード45を親、子供および同胞ノードなど
の関連する探索樹ノードにリンクするポインタを含む。

解凍サブシステム40は、双方向データバス51および双
方向制御バス52を介して辞書43に結合された回復／更新
制御部50を含んでいる。回復／更新制御部50は、現在受
信コードレジスタ53と前ストリングレジスタ54として表
されるワーキングレジスタを含んでいる。本発明によっ
て、回復／更新制御部50は図８に関して詳細に説明され
る未認識コード処理部55を含む。

回復／更新制御部50は、更に、圧縮コード値を辞書43
にストアされている文字ストリングに割り当てるコード
発生器56を含んでいる。コード発生器56は、逐次的に、
またはハッシングによるように疑似ランダムにコード番
号を割り当てる。装置の互換性のために、コード発生器
56は、圧縮サブシステム10のコード発生器26で利用され
ているのと同じプロセスとアルゴリズムを利用してコー
ド番号の割り当てを行う。割り当てられたコードによっ
て、メモリアドレス44を介して辞書43の記憶場所にアク
セスする。このようにして、圧縮サブシステム10に関し
て上に説明したように、アドレス44（ノード番号46）が
辞書43にストアされているストリングのコードとして利
用される。

回復／更新制御部50は、後で説明する方法で図７、図
８、および図10の動作フローチャートにしたがって、解
凍サブシステム40の動作を制御する制御装置57を含んで
いる。

解凍サブシステム40は、入力41で受け取られる圧縮コ
ード信号のバッファとして働くコードレジスタ60を含
む。個々の圧縮コード信号は、後で説明する動作にした
がって、コードレジスタ60からバス61を介して現在受信
コードレジスタ53に加えられる。回復／更新制御部50
は、制御バス62を介してコードレジスタ60からの圧縮コ
ード信号の受け取りを制御する。

解凍サブシステム40の動作は簡単に言えば次のようで
ある。現在受信コードレジスタ53に挿入された入力圧縮
コード信号は、アドレス44を介して辞書43にストアされ
ている対応するストリングにアクセスする。回復プロセ
スが、関連するノードポインタ48を利用して探索樹を逆
方向にたどってストリングのノードを追跡する時に、ス
トリングの文字は文字フィールド47から回復される。ス
トリングから回復された文字は適当な順序で出力42から
供給される。これらのストリング回復動作は上に引用し
た参考資料に記載されているものと同じである。辞書43
は、現在回復されるストリングの各文字で先に回復され
たストリングを拡張することによって更新される。前ス
トリングレジスタ54はこのプロセスで利用される。

対応するストリングが辞書43にストアされていない未
認識圧縮コード信号は、繰返し文字または文字群のスト
リングを圧縮する圧縮サブシステム10に呼応して受け取
られる。未認識圧縮コード信号が受け取られたときに
は、未認識コード処理55が、未認識圧縮コード信号に対
応するストリングを回復するために用いられる。更に、
圧縮プロセスの間に圧縮サブシステム10の辞書13にスト
アされた更新ストリングに対応する更新ストリングが解
凍サブシステム40の辞書43にもストアされる。未認識コ
ード処理55の詳細は図８に関して後に説明される。

図3aにおいて、辞書13と43の探索樹のノードに関する
具象的なデータ構造が図示されている。本発明の好まし
い実施例では、同じノードデータ構造が圧縮サブシステ
ム10と解凍サブシステム40の両方で利用されるので、図
１と図２の両方のなじみの参照数字が図3aに示されてい
る。ノード番号16、46と文字フィールド17、47は上で説
明した。関連ノードポインタフィールド18、48は、親ポ
インタフィールド66と子ポインタフィールド67を含む。
周知の方法で、親ポインタフィールド66は、現在ノード
15、45の親ノードのノード番号を含み、そして子ポイン
タフィールド67は現在ノード15、45の子ノードのノード
番号を含む。

当技術分野ではよく理解されている方法で、圧縮サブ
システム10は次のようにして探索樹を下方に辿って探索
を行う。子ノードの文字値が現在ノードにある時に、い
ずれかの子ノードが現入力文字と一致するかどうかを確
定するために、子ノードの文字値が調べられる。一致す
るものがあれば、その子ノードは現在ノードとなる。そ
して、現入力文字と一致する子ノードを持たない現在ノ
ードに出会うまで、このプロセスは次の入力文字につい
て繰返される。このようになった時に、最長一致のスト
リングが辞書13に見出されて、そのノード番号がこの最
長一致ストリングの圧縮コード信号として用いられる。
探索樹の前方向へ辿る探索が、親ポインタフィールド66
がナル値を持つ根ノードから始まる。

同様の方法で、周知であるが、現在ノード番号と現入
力文字のハッシング関数から探索すべき次のノードを見
出すことによって、前方への探索を行うことができる。
このような実施例では、子ポインタフィールド67は利用
されないだろう。Welchの特許（'302）は、LZWアルゴリ
ズムのハッシュ探索の実施例を開示している。

周知の方法で、図3aのデータ構造は、圧縮コード信号
に対応するデータ文字ストリングを回復するために探索
樹を逆方向に辿る探索において、解凍サブシステム40に
よっても用いられる。圧縮コード信号がノード番号46の
アドレスを指定し、そして文字値は文字フィールド47に
ストアされている。親ポインタフィールド66のノード番
号は親ノードにアクセスするために用いられ、そしてそ
こに文字値がストアされている。このプロセスは、根ノ
ードに到達するまで続けられる。文字は順序が逆のこの
プロセスによって回復されるので、LIFOスタックまたは
適当に構成された出力バッファのような機構が文字順序
を逆にして元のデータ文字ストリングを回復するために
利用される。

圧縮辞書13または解凍辞書43にストアされているスト
リングは次のようにして拡張される。空記憶場所の次の
使用可能コードはコード発生器26または56によって与え
られ、そのノード番号は拡張されるノードや子ポインタ
67に加えられる。拡張されるノードのノード番号は空記
憶場所の親ポインタフィールド66に挿入される。拡張文
字の文字値は空記憶場所の文字フィールド17または47に
挿入される。

図3bにおいて、辞書13および43の探索樹のノードに関
する実際のデータ構造が図示されている。このデータ構
造と圧縮解凍装置におけるその実施はClarkの特許（'59
1）に説明されている。図3aについて説明したように、
図3bのデータ構造は圧縮辞書13と解凍辞書43の両方で利
用できるので、図１と図２の両方のよく知られている参
照数字が示されている。さらにまた、ノード番号16、46
および文字フィールド17、47は先に説明されている。図
3bのデータ構造において、関連ノードポインタフィール
ド18、48は、親ポインタフィールド70、子ポインタフィ
ールド71および同胞ポインタフィールド72から成ってい
る。親ポインタフィールド70は図3aの親ポインタフィー
ルド66について先に説明したのと同じ方法で利用され
る。子ポインタフィールド71と同胞ポインタフィールド
72が図3aの子ポインタフィールド67に置き換わる。図3b
のデータ構造において、親ノードはその子のポインタフ
ィールド71を使用して子ノードの１つのノード番号を指
し、その指された子ノードはその同胞ポインタフィール
ド72を用いてその同胞ノードの１つのノード番号を指
す。指された同胞ノードが、今度は、その同胞ポインタ
フィールド72を用いて更に進んだ同胞ノードを指す。こ
のようにして、親ノードの全ての子のポインタが同胞ノ
ードのリンクされたリストに含まれるようになる。

入力文字の存在を同胞のリストで探索することを除け
ば、下方への探索は図3aに関して上に説明した方法で行
われる。ストリング回復のための逆方向への探索は、図
3aに関して上に説明した方法で行われ、子と全ての同胞
の親ポインタフィールドを親のノード番号に設定するこ
とで実現される。探索を容易にするために、同胞リスト
は昇順文字値の順序で配列することができる。

子のないノード（子ポインタフィールド＝０）で表さ
れるストリングの拡張は、次に使用可能なコードを割り
当てること、上記のように、次に使用可能な空記憶場所
を指定することおよびこの空記憶場所のノード番号を拡
張されるノードの子ポインタフィールド71に挿入するこ
とによって行われる。この新しくつくられた子ノードの
親ポインタフィールド70は親のノード番号に設定され、
拡張文字値が新しくつくられた子の文字フィールドに挿
入される。拡張されるノードが既に子を持っている場合
には、新しい同胞ノードがつくられて、同胞リストの適
当なノードの同胞ポインタフィールド72を調整すること
で同胞リストに挿入される。親のノード番号は新しくつ
くられた同胞ノードの親ポインタフィールド70に挿入さ
れる。

図４および図4aにおいて、図４は図3aのデータ構造に
したがって探索樹ノード80を模式的に図示する。アドレ
ス（ノード番号）、文字値、親ノードおよび子ノードが
説明文で表されるようになっている。図4aは図４のノー
ド80の配列を利用するデータの蓄積を図示する部分的な
探索樹を表すものである。図4aの部分的な探索樹は、ス
トリングab、acおよびadをストアするノード81、82、83
および84から構成されている。このようにして、親ノー
ド81の子ポインタフィールド67（図3a）は子ノード82、
83および84のノード番号を含んでおり、一方で、子ノー
ド82、83および84の親ポインタフィールド66は各々親ノ
ード81のノード番号を含んでいる。

図５および図5aにおいて、図５は図3bのデータ構造に
したがって探索樹ノード90を模式図的に図示する。アド
レス（ノード番号）、文字値、親ノード、子ノードおよ
び同胞ノードが説明文で表されるようになっている。図
5aは、図５のノード90の配列を利用する部分的な探索樹
を表すものであり、ノード91、92、93および94から成っ
ている。図5aの部分的な探索樹は、図4aのそれと同じス
トリングをストアしている。このようにして、親ノード
91の子ポインタフィールド71（図3b）は子ノード92のノ
ード番号に設定される。子ノード92の同胞ポインタフィ
ールド72は同胞ノード93のノード番号に設定され、同胞
ノード93の同胞ポインタフィールド72は同胞ノード94の
ノード番号に設定される。子ノード92、93および94の親
ポインタフィールド70はそれぞれ親ノード91のノード番
号に設定される。

次の図６〜図10の詳細な説明において、図3bのデータ
構造、図５の対応するノード配列および図5aの対応する
探索樹構造の項で、動作の説明がされる。コードはハッ
シングによるように疑似ランダムに割り当てることがて
きることは知られているが、コードはコード発生器26お
よび56によって逐次的に割り当てられるものと考えられ
る。ハッシングの実施例では、次に続くアドレスを決め
るためにノード番号コードと文字はハッシュされる。そ
のようなハッシングの実施例では、子および同胞のポイ
ンタは利用されないだろう。しかし、図６〜図10のフロ
ーチャートでは、オペレーティグブロックのCODE＝NEXT
AVAILABLE CODEが次の順番のコードまたは次のハッシ
ュコードのいずれかを完全に取り囲んでいる。順次コー
ド割当ての実施例では、これらの動作ブロックはより具
体的には、CODE＝CODE＋１である。

図６において、図１と図3bを引続き参照して、本発明
によってデータ圧縮を行うために、探索／更新制御部20
が実行する詳細な動作を示す制御フローチャートが図示
されている。制御部27は動作の実行を制御するための状
態マシンのような適当な回路を含んでいるものと考えら
れる。

図６のフローチャートは、全ての単一文字ストリング
で初期設定される圧縮辞書13に基づいている。従って、
ブロック100は、それぞれのコード（ノード番号）にス
トアされる単一文字ストリングの全てで辞書13をクリア
して初期化することができるようになっている。この動
作は、単一文字ストリングをストアするためにノード番
号を逐次的に割り当てるコード生成器26を使用して行わ
れる。ASCIIの実施では、最初の256コードが、256の単
一文字ストリングをストアするためにコード発生器26に
よって割り当てられる。初期設定は、初期化された記憶
場所の文字フィールド17を圧縮が行われるアルファベッ
トのそれぞれの文字の文字値に設定することによって達
成される。これらの初期化された記憶場所の親ポインタ
フィールド70、子ポインタフィールド71および同胞ポイ
ンタフィールド72はゼロに設定される。初期化された記
憶場所が辞書13にストリングをストアするための根ノー
ドを与え、したがってこれらの初期化された記憶場所の
親ポインタフィールド70はゼロのままになっていること
が理解される。

これらの動作によって、辞書13の初期の記憶場所はそ
れぞれの単一文字ストリングを含むように設定される。
ASCIIの実施では、辞書13の最初の256の記憶場所はそれ
ぞれの256の単一文字ストリングを含んでいる。ブロッ
ク100の動作において、辞書13の残りの記憶場所はその
フィールドの全てをゼロに設定することでクリアされ
る。ASCIIの実施では、266以上のノード番号を持つ辞書
の記憶場所はクリアされる。

ブロック101で、現一致照合レジスタ24はゼロに設定
され、ブロック102で前一致照合レジスタ25がゼロに設
定される。ブロック103で、次の入力文字が現文字レジ
スタ23に入れられる。

ブロック104で、現文字で連結されている現一致照合
ストリングが辞書中にあるかどうかを確定するために探
索が行われる。先に引用した参考資料に説明されている
手順など、どのような周知の適応な辞書探索の手順でも
利用できる。ここにおいて、具体的には、ゼロでない現
一致照合に対しては、現一致照合レジスタ24は現一致照
合ストリングのノード番号を含んでいる。現一致照合ノ
ードの子ポインタフィールド71で指された子が入力文字
と比較される。入力文字が現在ノードの子と一致すれ
ば、その時ブロック104の判定は肯定の答えとなり、YES
のパスが取られる。子ノードが現文字と一致しない場合
には、子ノードの指す同胞リストが調べられて、現文字
が同胞と一致するかどうか確定される。一致があれば、
YESのパスが取られる。しかし、現在ノードが子がない
か、または現文字が現在ノードのどの子とも一致しない
ときには、ブロック104のNOのパスが取られる。

現一致照合がゼロであれば、ブロック104は辞書13中
で現文字に等しい文字値を持っている根ノードを探す。
辞書13は全ての単一文字ストリングで初期化されている
ので、ブロック104からYESの分岐が自動的に取られる。

ブロック104からYESの分岐が取られたときには、図６
の圧縮処理は、現文字で連結される現一致照合が辞書13
中で発見されて、更に長いストリングの探索が続けられ
る点にある。従って、ブロック105で現一致照合は更新
されて、新しい現一致照合は現文字で連結された現存の
現一致照合に等しく設定されるようになる。これは現一
致照合レジスタ24のノード番号を適当に更新することに
よって達成される。現一致照合がゼロでない時には、現
一致照合レジスタ24は上記の現文字と一致照合した子の
ノード番号（または同胞のノード番号）で更新される。
現一致照合がゼロであれば、現一致照合レジスタ24は現
文字と一致照合した単一文字ストリングのノード番号で
更新される。単一文字ノード番号は周知の方法でアルゴ
リズム的に得ることができ、または初期化された現文字
値を求めて記憶場所を探索することで見出すことができ
る。

ブロック104からNOの分岐が取られたならば、現文字
で連結される現一致照合は辞書13にストアされるストリ
ングと一致しない。辞書13中で見出された現一致照合
は、入力データ文字ストリームとの最長一致を与えるも
のであり、そしてブロック104で現一致照合と連結され
た現文字はその一致を「破った」。この点で、ブロック
106が最長一致を表す圧縮コード信号を与える。最長一
致のこのコードは現一致照合レジスタ24に有るものであ
り、現一致照合のノード番号である。

ブロック107では、現一致照合レジスタ24の内容が前
一致照合レジスタ25に移される。このようにして、前一
致照合レジスタ25は今は現在最長一致を表す記憶場所の
ノード番号をストアする。前一致照合レジスタ25は後で
説明される方法で辞書13を更新することで利用される。

現一致照合が前一致照合としてストアされた後は、ブ
ロック110において現文字は現一致照合としてストアさ
れる。したがって、ブロック110は、次の一致照合の最
初または根文字として、先の一致を壊した不一致入力文
字を利用して次の最長一致するストリングの探索を始め
る。したがって、ブロック110において、現一致照合レ
ジスタ24は、現文字の値を持つ初期化された単一文字根
ノードのノード番号に設定される。これはアルゴリズム
的になされるか、またはブロック105に関して先に説明
した方法で探索することでなされるかのいずれかであ
る。

ブロック110は、また、次のロジックで実現すること
もできる。ブロック110におけるように現一致照合を現
文字に設定しないで、現一致照合をゼロに設定し、そし
て処理をブロック104の入力に返すことができる。この
代替え処理の結果は、辞書の初期化のために常にブロッ
ク104のYESのパスに通じることになり、このようにして
ブロック105に至る。より少ない処理ステップで、示さ
れるように、ブロック110によって同じ結果が達成され
ることが理解される。しかし、このロジックは図９の無
初期化圧縮処理で使用される。

ブロック105に達したとき、現一致照合の現文字拡張
が辞書に見出されて、本発明にしたがって、現文字を利
用して前一致照合を拡張して辞書13にストアされる更新
ストリングを与える。しかし、最初の入力文字だけが受
け取られた後でブロック105に達したときには、前一致
照合がなくそして辞書13は、その時点では更新はされな
いだろう。したがって、判定ブロック111は前一致照合
がゼロであるかどうかを確定する。これは、ブロック10
2でゼロに初期設定された前一致照合レジスタ25を調べ
ることで達成される。前一致照合がゼロであれば、辞書
の更新をバイパスしてブロック111からYESのパスが取ら
れる。最初の入力文字が処理された後で、ブロック105
に達した時には、前の一致はゼロではなくて、ブロック
111からNOのパスが取られて、本発明によって辞書の更
新が行われる。

したがって、ブロック112で、コード発生器26は次の
使用可能なコードをあたえる。次の使用可能なコード
は、更新ストリングをストアする次に使用可能な空辞書
記憶場所のノード番号である。ブロック113で、現文字
によって連結された前一致照合は、辞書13中でこの次に
使用可能なコードでアクセスされるこの次に使用可能な
空記憶場所にストアされる。

ブロック113の記憶は次のようにして達成される。ブ
ロック112の次に使用可能なコードによってアクセスさ
れる次に使用可能な空記憶場所の親ポインタフィールド
70は、前一致照合レジスタ25にある前一致照合のノード
番号に設定される。この次の空記憶場所の文字フィール
ド17は現文字レジスタ23から現文字の値に設定される。
前一致照合親ノードはこの新しくつくられたノードと次
のようにしてリンクされている。前の一致親ノードのノ
ード番号は前の一致レジスタ25中にある。前一致照合親
ノードが子がなければ（子ポインタフィールド＝０）、
ブロック112の次の使用可能なコードは、新しくつくら
れた子のノード番号であるが、この前一致照合親の子ポ
インタフィールド71に挿入される。前一致照合親が既に
子を持っていれば、新しくつくられたノードのこの次に
使用可能なコードノード番号は前一致照合親の子の同胞
リストに挿入される。そのリストの同胞の同胞ポインタ
フィールド72を調整して、新しくつくられた同胞を収納
し、したがって適当な同胞ノード番号を新しくつくられ
た同胞の同胞ポインタフィールド72に挿入するようにす
ることによって、これは行われる。

ブロック114は前一致照合レジスタ25を更新するため
に用いられ、ブロック113に関して説明されたように、
現文字によって拡張された前に一致照合されたストリン
グのノード番号を指し示すようにする。これは、新しく
つくられた子または同胞のノード番号を、ブロック113
に関して説明されたように、前一致照合レジスタ25に挿
入することによって達成される。このノード番号は、ブ
ロック112に関して説明される次に使用可能なコードで
あり、コード発生器26によって与えられる。

ブロック112〜114によって辞書更新が行われた後に、
現文字レジスタ23の現入力文字が入力データストリーム
の最後の入力文字であるかどうかを確定するために判定
ブロック115が入れられている。また、ブロック115に
は、ブロック111のYESのパスから入り、先の説明された
ように辞書更新をバイパスする。現文字が最後の文字で
あれば、ブロック115からYESのパスを取りブロック116
に至り、そこで現一致照合のコードが出力される。ブロ
ック116にしたがって供給された圧縮コード出力は現一
致照合レジスタ24内に存在する。ブロック116にしたが
って、圧縮コードを出力したのち、ブロック117が入れ
られて処理を終える。

しかし、現文字レジスタ23の現文字が最後の入力文字
でなければ、ブロック115からNOの分岐が取られて、パ
ス118によりブロック103の入力に帰る。ブロック103に
したがって、次の入力文字が現文字レジスタ23に挿入さ
れて、図６のデータ圧縮処理が続けられる。

一時的に処理を中止することが望ましい場合には、パ
ス118のホールドブロック119で中止が行われる。

上記より理解されることであるが、ブロック103〜105
は最長一致ストリングを辞書13で探索することを制御
し、ブロック106は最長一致に対応する圧縮コード出力
を与える。ブロック110は、前ストリング一致照合サイ
クルで不一致を生じた文字から始めて、次の最長一致の
探索を始める。

ブロック107および112〜114は、本発明にしたがって
辞書13の更新を制御する。ブロック104が現入力文字が
現一致照合の拡張に成功したと決定した時に、ブロック
112〜114はこの文字を拡張される過程にある前の一致ス
トリングと連結する。このようにして、辞書更新は即時
に且つ文字ごとにストリング探索とインターリーブして
行なわれる。

一致照合される現在ストリングが拡張される前ストリ
ングと同じ探索樹のパスにある時には、繰返し文字また
は文字群のストリングを効率よく圧縮する現在アルゴリ
ズムの特性が実現されることが理解される。そのような
入力ストリングは、図８および図12に関して後で更に説
明されるが、その長さに関係なく２つの圧縮コード信号
に圧縮される。

図７において、図２および図3bを引続き参照にして、
図６にしたがって生成される圧縮コードを解凍する回復
／更新制御部50の実行するる動作を描く制御フローチャ
ートが図示されている。図７は全ての単一文字ストリン
グで初期化された解凍辞書43に基づいている。制御57は
動作の実行を制御するために、状態マシンのような適当
な回路を含むものとして考えられる。

ブロック130にしたがって、解凍辞書43はクリアされ
初期化される。辞書43に関するブロック130の動作はブ
ロック100と圧縮辞書13に関して先に説明されたものと
同じである。

ブロック131で、前ストリングレジスタ54はゼロにク
リアされブロック132で入力圧縮コードが現在受信コー
ドレジスタ53に挿入される。

判定ブロック133を伴う処理が続き、この判定ブロッ
ク133では、現在受信コードレジスタ53にある現在受信
コードに対応するストリングが辞書43のなかにあるかど
うかが決められる。通常は、辞書43は現在受信コードに
対応するストリングを含んでいる。現在受信コードが、
繰返し文字または文字群に遭遇する圧縮器から生じたも
のである時に、例外が起きる。ブロック133の判定は、
現在受信コードをアドレスとして用いて辞書43にアクセ
スして、アクセスした辞書の記憶場所がクリアされてい
るかどうかを確定することで遂げられる。辞書がクリア
されていれば、現在受信コードに対応するストリングは
辞書にない。代わりに、逐次コード割当て（代入）の実
施例では、フロック133の判定は、現在受信コードがコ
ード発生器56の現存するコードより小さいかまたは等し
いかどうかを確定することで遂げられるであろう。現在
受信コードがコード発生器56の現存するコード以下であ
るときには、現在受信コードに対応するストリングが辞
書43中にある。しかし、現在受信コードが現存コードよ
りも大きい時には、現在受信コードに対応するストリン
グが辞書43中にまだない。

現在受信コードに対応するストリングが辞書43中にな
ければ、ブロック133からNOのパスを取って、未認識コ
ード処理を実行するブロック55に至る。未認識コード処
理の詳細は図８に関して説明される。

現在受信コードに対応するストリングが辞書43にある
ときには、ブロック133からYESのパスを取ってブロック
134に至る。ブロック134で、現在受信コードに対応する
ストリングの文字が、適当な周知の辞書探索プロセス
（例えば、Welchの特許（'302）の図５、またはClarkの
特許（'591）の図５）によって回復される。ブロック13
5で、パラメータｎが与えられて、ブロック134で回復さ
れた文字の数に等しく設定される。ブロック136で、イ
ンデックスｉは１に設定される。インデックスｉは、ブ
ロック134で回復されたストリングのｎ個の文字を一ス
テップずつたどって、回復されたストリングの文字がそ
の最初の文字から始まって出力されるようにする。この
ようにして、ブロック137は現在受信コードストリング
のｉ番目の文字を出力するように備えられている。

判定ブロック140は、前ストリングがゼロに等しいか
どうかを確定するために含まれている。この試験は、前
ストリングレジスタ54の内容がゼロかどうかを確定する
ことによって果たされる。前ストリングレジスタ54がゼ
ロであれば、ブロック140からYESのパスを取って、辞書
更新をバイパスする。ブロック140の機能は図６のブロ
ック111に関して先に説明したものと同じである。した
がって、ブロック140からのYESのパスは最初の受け取り
入力コードに呼応する時だけ取られる。

前ストリングレジスタ54がゼロでない時には、ブロッ
ク140からNOのパスを取り、ブロック141で辞書43の次の
空記憶場所に次の使用可能なコードがコード発生器56に
よってあたえられる。ブロック142で、現在受信コード
に対応するストリングのｉ番目の文字と前ストリングが
連結されて、この次の空記憶場所にストアされる。ブロ
ック143で、前ストリングレジスタ54が更新されて、ブ
ロック142の拡張された前ストリングのノード番号をス
トアする。ブロック141〜143の実行で行われる動作は図
６のブロック112〜114に関して先に説明されたものと同
じである。図７では前ストリングレジスタ54が使用され
るが、図６では前一致照合レジスタ25が含まれている。

ブロック144で、インデックスｉは１つインクリメン
トされる。判定ブロック140からのYESのパスもブロック
144の入力に加えられて、先に述べたようにブロック141
〜143の辞書更新処理がバイパスされるようにされる。
判定ブロック145で、インデックスｉはｎ＋１に達した
かどうかを確定する試験が行われる。インデックスｉが
ｎ＋１に等しくないときには、ブロック145からNOのパ
スを取り、ブロック137の入力に処理を返す。ブロック1
37および140〜145を通る処理がｉ＝ｎ＋１となるまで続
けられる。

このようにして、現在受信コードストリングのｎ個の
文字はブロック137から正しい順序で出力され、そして
前の回復ストリングは現在受信コードストリングの接頭
部の全てで拡張される。ブロック141〜143の処理によっ
て、図６のブロック112〜114によって圧縮辞書13にスト
アされるのと同じストリングが解凍辞書43にストアされ
る。ブロック141〜143にしたがって解凍辞書43にストア
されるストリングは、ブロック112〜114にしたがって圧
縮辞書13にストアされるストリングとそれぞれ同じアド
レスからストアされる。

インデックスｉがｎ＋１の値に達した時に、ブロック
145からYESのパスを取ってブロック146に至る。ブロッ
ク146で、現在受信コードストリングは、次の入力コー
ドを処理する用意に、前ストリングに取って代わる。こ
れは、現在受信コードレジスタ53の中味を前ストリング
レジスタ54に挿入することによって達成される。未認識
コード処理55はブロック146への入力として存在してい
る。

丁度処理されたばかりの現在受信コードが最後の入力
コードでない場合には、判定ブロック147はブロック147
のNOのパスを介してブロック132の入力に処理を返す。
処理はパス148を介してブロック132に返り、次の入力圧
縮コードの処理を始める。一時的に処理を中止すること
が望ましいときには、パス148中にあるホールドブロッ
ク149で行われる。解凍器のホールドブロック149は圧縮
器のホールドブロック119に対応する。

ブロック147で、現在受信コードが最後の入力コード
であるときには、ブロック147からYESのパスを取って、
ブロック150に至り、処理を終結する。

ブロック141〜143が、現在受信コードの接頭部で先に
回復されたストリングを拡張してストアることによって
辞書43を更新している間に、一方で、ブロック134およ
び137が、現在受信コードに対応するストリングの文字
を回復して出力することが理解される。

図８において、未認識コード処理55の詳細が図示され
ている。ブロック160で、インデックスｉは１に設定さ
れ、そして説明される理由でモジュロｎにインクリメン
トされる。ブロック161で、前ストリングのｎ個の文字
が回復される。前ストリング回復サイクルにおいては、
これは現在受信コードストリングであったので、前スト
リングはｎ個の文字を持っている。ブロック161は、ブ
ロック134に関して先に説明した周知の辞書ストリング
回復プロセスを用いて、前ストリングレジスタ54の内容
を持つ辞書43にアクセスすることによって実現される。

ブロック162で、コード発生器56は次の使用可能コー
ドを次の空辞書記憶場所に供給する。ブロック163で、
前ストリングのｉ番目の文字で拡張された前ストリング
がこの次の空記憶場所にストアされる。ブロック164
で、前ストリングレジスタ54を更新してこの拡張された
前ストリングのノード番号をストアすることで、前スト
リングはブロック163の拡張された前ストリングで置換
えられる。ブロック162〜164の辞書更新の動作は、ブロ
ック141〜143に関して先に説明したものと似ている。先
に説明したように、ブロック141〜143の辞書更新の実施
については、図６のブロック112〜114に関して詳細に説
明された。ブロック162〜164の処理においては、前スト
リングレジスタ54が用いられる。

判定ブロック165で、コード発生器56によって現在与
えられたコードが現在受信コードレジスタ53中の現在受
信コードに等しいかどうかを確定するためにの試験が行
われる。コード発生器56の現存コードが現在受信コード
の値に達していないときには、ブロック165からNOのパ
スを取ってブロック166に至る。そこで、インデックス
ｉは１だけインクリメントされたモジュロｎになる。コ
ード発生器56の現存コードが現在受信コードに等しくな
るまで、処理はブロック162の入力に折り返されて、追
加の更新ストリングをストアする。

ブロック165がコード発生器56の現存コードが現在受
信コードレジスタ53中の現在受信コードに等しいことを
知らせた時に、ブロック165からYESのパスを取り、ブロ
ック167に至る。ブロック165がコードが現在受信コード
に等しいと指示した時に、未認識現在受信コードに対応
するストリングは直ちに解凍辞書43にストアされること
が理解される。

ブロック167で、現在受信コードに対応する文字は回
復されて、各文字は最初の文字から始めて出力される。
ブロック167は、現在受信コードレジスタ53の内容を持
つ辞書43にアクセスして、ブロック134に関して先に説
明した周知の辞書ストリング回復手順を使用して実現さ
れる。

以上より理解されることであるが、ブロック160〜167
の処理によって、未認識圧縮入力コードに対応するスト
リングは組み立てられ、解凍辞書43にストアされ、そし
てその文字が回復されて出力される。図６の圧縮器が未
認識コードに係わるストリングを生成してストアすると
き、圧縮器は伝送されるコードに対応するストリングを
超えるｎストリングをストアすることが更に理解され
る。このことは図12に関連して更に明らかにされる。こ
れらのｎストリングを組み立ててストアする圧縮器の処
理は次の通りである。

処理は、インデックスｉが１だけインクリメントされ
たモジュロｎのブロック170に移る。ブロック171〜173
はそれぞれブロック162〜164の処理を繰返す。したがっ
て、パラメータｎが１つだけディクリメントされるブロ
ック174に進む。そこで、パラメータｎは判定ブロック1
75で試験されて、ｎがゼロに等しいかどうかを確定され
る。ｎがゼロでなければ、NOのパスを取り、ブロック17
5からブロック170の入力に戻る。パラメータｎがゼロの
値になったときに、未認識コード処理はブロック175のY
ESのパスで出て行く。

ブロック166と170において、インデックスｉはインク
リメントされたモジュロｎとなり、ブロック163と172に
したがってストアされているストリングに適当な文字値
を与えることを容易にする。使用されるｎの値はブロッ
ク135（図７）で与えられるものであり、ブロック174の
ディクリメントに先立っている。文字値はブロック161
にしたがって回復される前ストリングのｎ個の文字の値
であり、ｉのインデックスがつけられている。ブロック
161にしたがって回復される前ストリングのｎ個の文字
は、ブロック163と172にしたがって組み立てられてスト
アされてるストリングのｎ文字接頭部を形成する。

図８の処理は、逐次コード割当てまたはハッシングの
ような疑似ランダムコード割当てを含む、コード発生器
26と56で使用されるあらゆる種類のコード割当てプロセ
スに対して機能する。コード割当てプロセスが逐次であ
るときには、図８のロジックは次のように簡単にするこ
とができる。

逐次コード割当てについて、ブロック165の試験は「C
ode＝Crrent Received Code＋ｎ」となる。ブロック170
〜175は削除されて未認識コード処理はブロック167から
外にでる。

以上より理解されることであるが、ブロック167は未
認識受信コードに対応するストリングの文字を回復し、
且つ、ブロック163と172は、図６に関して先に説明した
ように繰返し文字または文字群のストリングが生じたと
きに、圧縮辞書13にストアされているのと同じストリン
グを解凍辞書43にストアする。

図９において、図１と図3bを引続き参照して、本発明
にしたがってデータ圧縮を行うために、探索更新制御部
20の実行する詳細な動作の制御フローチャートが図示さ
れている。制御27は、動作の実行を制御するために、状
態マシンのような、適当な回路を含むものとして考えら
れる。図９のフローチャートは無初期化圧縮辞書13に基
づいている。図９の無初期化の実施では、最初に文字が
遭遇された時に、未圧縮形の文字の伝送を伴ってゼロコ
ードが伝送される。ゼロコードは、そのような文字が圧
縮器によって伝送されたという指示を解凍器に与える。
最初に遭遇する文字は、圧縮辞書13にストアされて、文
字との次の遭遇に関して記憶信号文字ストリングまたは
根ノードとして機能する。最初に遭遇する文字の格納以
外では、図９のフローチャートは図６のものと同じよう
に機能する。

ブロック180で、辞書13はクリアされる。辞書のクリ
アは、図3bのフィールド17と70〜72をゼロに設定する。

図９のフローチャートはブロック181〜187と190〜194
を含んでいる。これらのブロックは、図６のブロック10
1、103〜107および112〜117とそれぞれ同じである。図
６のこれらのブロックに関する先の説明は、次のことを
除いて、図９のこれらのブロックに適用する。

ブロック183において、現一致照合がゼロであるとき
には、辞書13での探索は単一文字ストリングが既に辞書
に根ノードとして取込まれているかどうかを確定するた
めに行われる。単一文字ストリングが既に辞書にあれ
ば、ブロック183からYESのパスを取り、そうでなければ
NOのパスを取る。ブロック184において、現一致照合が
ゼロの時には、現一致照合レジスタ24はブロック183で
一致照合された単一文字根ノードのノード番号で更新さ
れる。更に、逐次コード割当ての実施におけるブロック
187に関して、この無初期化の実施では、全ての辞書記
憶場所が入力で遭遇するストリングのストアに使用可能
であるので、コード割当ては１から始まる。また、注意
することとして、辞書更新をバイパスする図６のブロッ
ク111は図９では必要がない。この理由は次の通りであ
る。この無初期化の実施では、最初の入力文字は、下で
説明されるように、最初に遭遇されて前一致照合に次の
繰返しを与える文字である。

更に、ブロック185は図６のブロック106に対応する。
ブロック185では、ブロック106におけるように、圧縮出
力コードが現一致照合レジスタ24に存在している。しか
し、ブロック185では、現一致照合がゼロであるとき、
このゼロコードは、現入力文字が最初に遭遇された文字
であることを指示（指唆）して出力される。

図９のフローチャートは、現一致照合レジスタ24の内
容がゼロに等しいかどうかを確定する判定ブロック195
を含んでいる。現一致照合がゼロでなければ、ブロック
195からNOのパスを取ってブロック186に至り、そこで、
図６の対応するブロック107に関して先に説明されたよ
うに、現一致照合レジスタ24の内容が前一致照合レジス
タ25に移される。ブロック196で、現一致照合レジスタ2
4はゼロに設定されて、処理は183の入力に移る。ブロッ
ク186は次のストリングのパーシング動作に向けて辞書
更新の準備をし、ブロック196は次のストリング探索が
現文字レジスタ23にある文字から始まるようにする。

ブロック195からYESのパスを取った場合には、現一致
照合はゼロに等しく、現文字レジスタ23の文字は最初に
遭遇されたものである。このようにして、ブロック197
で、この文字が出力される。ブロック185はゼロ値の現
一致照合を出力したので、この最初に遭遇された現文字
は、ブロック197から出力されるが、上で説明したよう
にゼロコードが先にある。ブロック200で、次に使用可
能なコードが、辞書13の次に使用可能な空記憶場所を指
示してコード発生器26によって与えられる。ブロック20
1で、この次の空記憶場所に現文字レジスタ23の現文字
が単一文字ストリング根ノードとしてストアされる。ブ
ロック201の機能は、現文字レジスタ23からの文字をこ
の次の空記憶場所の文字フィールドにストアすることで
達成される。親ポインタフィールド70、子ポインタフィ
ールド71および同胞ポインタフィールド72は全て既にブ
ロック180でゼロにされている。

ブロック202で、前一致照合レジスタ25は、次のスト
リングのパーシング動作における辞書更新のためにブロ
ック201でつくられた根ノードに設定される。これは、
前一致照合レジスタ25に、ブロック201で新しくつくら
れたこの根ノードのノード番号を挿入することで達成さ
れる。このノード番号はブロック200で与えられたばか
りのコードになる。

判定ブロック203は、現文字レジスタ23にある文字が
最後の入力文字であるかどうかを確定するためにある。
最後でない場合には、ブロック203からNOのパスを取っ
てブロック182に至り、入力ストリームすら次のデータ
文字信号を取得する。しかし、ブロック203で試験され
た現文字が最後の入力文字であれば、ブロック203からY
ESのパスを取ってブロック194に至り、処理を終了す
る。

以上より理解されることであるが、ブロック182〜184
は辞書13を調べて最長一致ストリングを探索することを
制御し、ブロック185は最長一致に対応する圧縮コード
出力をあたえる。また、ブロック185は、最初に遭遇さ
れた文字の伝送に先立ってゼロコード出力を与える。ブ
ロック196は、先ず現一致照合レジスタ24をゼロにして
次の最長一致の探索を始める。このように、最長一致の
探索は、前記ストリング一致照合サイクルで不一致を引
き起こした文字から始まる。その文字は現文字レジスタ
にある。

ブロック186、187、190および191は本発明にしたがっ
て辞書13の更新を制御する。ブロック183が現入力文字
が現一致照合を拡張することに成功したと確定した時、
ブロック187、190および191は、拡張されるプロセスに
ある前に一致照合されたストリングとこの文字を連結す
る。ブロック195、197および200〜202は、最初に遭遇さ
れる文字の管理を制御する。ブロック202は、次のスト
リング一致照合サイクルにおける可能性のある拡張に向
けて前一致照合の文字の準備をする。図９のロジックか
ら理解されることであるが、最初に遭遇する文字が幾つ
か連続して受け取られるときには、これらの文字の最後
のものだけが次のストリング一致照合サイクルで拡張さ
れる。

図10において、図２と図3bを引続き参照して、図９に
したがって生成された圧縮コードを解凍するために、回
復更新制御部50の実行する動作を表す制御フローチャー
トが図示されている。図10のフローチャートは無初期化
解凍辞書に基づくものである。制御57は、動作の実行を
制御するために、状態マシンのような、適当な回路を含
むものとして考えられる。

ブロック210で、解凍辞書43は図９のブロック180に関
連して先に説明された方法でクリアされる。したがっ
て、解凍辞書43は図９の無初期化の辞書13と全く同じ方
法でクリアされる。

図10の解凍のフローチャートによって行われる動作
は、図９に関して先に論じた最初に遭遇される文字の管
理に関すること以外は、図７の解凍のフローチャートに
よって行われるものと同じである。したがって、図10
は、図７のブロック55、132〜137、141〜147および150
とそれぞれ同じ機能を行う55、211〜217および220〜226
を含んでいる。図７のブロック55、132〜137、141〜147
および150に関して先になされた説明は図10の対応する
ブロックに適用する。

図７のブロック140に対応するブロックは図10で使用
されていない。前に説明したように、ブロック140は前
ストリングレジスタ54がゼロのときには、辞書の更新を
バイパスする。これは、図７の初期化の実施では最初に
受け取る入力コードに呼応して起きる。図10の無初期化
の実施では、最初に受け取る入力コードは最初に遭遇さ
れる文字のものであり、それによって後に説明されるよ
うに次のサイクルでの更新に前ストリングを供給する。

ブロック217、220および221の処理は図９のブロック1
87、190および191によって圧縮辞書13にストアされたの
と同じストリングを解凍辞書43にストアする。ブロック
217、220および221にしたがって解凍辞書43にストアさ
れるストリングは、ブロック187、190および191にした
がって圧縮辞書13にストアされるストリングとそれぞれ
同じアドレスにストアされる。更に、ブロック55（図
８）の未認識コード処理が図10を背景にして行われると
き、図８のブロック163と172は、図９の圧縮器の動作に
関して繰返し文字または文字群のストリングが生じる時
に、圧縮辞書13にストアされるのと同じストリングを解
凍辞書にストアする。

具体的には、ブロック212は図７のブロック133に対応
する。ブロック133に関して先に行った説明がブロック2
12に適用される。但し、圧縮器が最初に遭遇した文字の
受け取りに先立つゼロの受信コードに関することは除
く。しかし、理解されることであるが、この状態は次に
説明する図10の他のブランチで処理されるので、ブロッ
ク212まで処理が進んだときには、現在受信コードはゼ
ロでなくなっている。

ブロック211で、入力圧縮コード信号は現在受信コー
ドレジスタ53に挿入される。判定ブロック230は、現在
受信コードがゼロかどうかを確定するために現在受信コ
ードレジスタ53の内容を試験する。現在受信コードがゼ
ロでにければブロック230から、NOのパスを取ってブロ
ック212に入り、そこで先に説明したように処理が進
む。

しかし、現在受信コードがゼロであれば、図９の圧縮
器が最初に遭遇した文字は予期されている。したがっ
て、この文字はブロック231から入力される。現在受信
コードレジスタ53が一時的にこの文字をホールドするた
めに利用される。ブロック232で、コード発生器56が解
凍辞書43の次の空記憶場所に対応する次に使用可能なコ
ードを与える。ブロック233で、入力文字は単一文字根
ノードとしてこの次の空記憶場所にストアされる。これ
は、図９のブロック201に関して上に説明した方法でブ
ロック233で達成される。このようにして、解凍サブシ
ステム40は、圧縮システム10が図９の無初期化実施で圧
縮辞書13にストアするのと同じ単一文字ストリングを同
じアドレスで解凍辞書43にストアする。

ブロック234で、解凍器の回復データ出力と圧縮器で
受け取られる入力データの間の整合性を保つために、ブ
ロック231で受け取られた文字が出力される。これは、
文字が一時的にストアされていた現在受信コードレジス
タ53からこの文字を出力することで果たされる。

ブロック235で、パラメータｎは１に設定される。最
初に遭遇されて丁度処理されたばかりのこの文字が、も
し圧縮器の入力で繰返し、未認識圧縮コードを生成すよ
うな場合には、次の解凍サイクルで行われる未認識コー
ド処理55に対してｎ＝１が適当な値である。

ブロック236で、前ストリングレジスタ54は、次のス
トリング回復サイクルにおける辞書更新のために、ブロ
ック233でつくられた根ノードに設定される。これは、
ブロック233で新しくつくられたこの根ノードのノード
番号を前ストリングレジスタ54に挿入することによって
達成される。このノード番号はブロック232で与えられ
たばかりのコードである。図10のロジックから理解され
るであろうが、最初に遭遇する文字が幾つか連続して受
け取られる場合には、図９に関して説明されたものと同
じ様な方法で、その最後の文字だけが次のストリング回
復サイクルで拡張される。

ブロック236の出力はブロック225に入力を与えて、上
に説明した処理を続ける。

図11a〜図11eにおいて、代表的な入力データストリー
ムを圧縮するときの、圧縮辞書13の連続した状態が図示
されている。辞書の状態は部分探索樹で模式図的に表さ
れている。示されているように、圧縮される入力ストリ
ームは「abcfghx」である。図示されているコンマは、
ストリングの構文解析を表しており、仮想的なもので、
入力データには含まれない。下線は現入力文字を示して
いる。図11aに示されるように、辞書13は初めにストリ
ング「abc」と「fgh」をストアしている。図11aにおい
て、ストリング「abc」は最長の一致照合ストリングと
して丁度一致照合されたところであり、「abc」のコー
ドは矢印240で表されるように出力されている。したが
って、ストリング「abc」は仮想コンマ241で表されるよ
うに入力から構文解析される。

図11bで、次の入力文字「ｆ」は矢印242で表されるよ
うに、ストリング「fgh」の最初の文字と一致する。本
発明にしたがって、図11aにおいて先の圧縮コードとし
て伝送されたストリング「abc」は、矢印243で表される
ように、文字「ｆ」で拡張される。

図11cにおいて、次の入力文字「ｇ」は記憶ストリン
グ「fgh」の第２文字と一致する。そして、前の拡張さ
れたストリング「abcf」は一致入力文字「ｇ」で拡張さ
れる。同様にして、図11dで、入力文字「ｈ」はストリ
ング「fgh」の第３文字と一致して、成長する前ストリ
ングの語尾に付加されてここでストリング「abcfgh」を
形成する。

図11eにおいて、次の入力文字「ｘ」はストリング「f
gh」の一致を破り、矢印244で表されるように最長一致
「fgh」のコードが出力される。ストリング「fgh」は、
仮想コンマ245で表されるように、入力から構文解析さ
れた。

図11a〜図11eから理解されることであるが、ストアさ
れているストリング「abc」は一致照合されたストリン
グ「fgh」の全ての接頭部で拡張され、また辞書の更新
は即時に、そして現一致照合されるストリングの各文字
を一致照合することとインターリーブして行われる。こ
のようにして、図11bで、ストリング「abcf」は次の繰
返しで一致照合に使用可能となった。図11cで、ストリ
ング「abcfg」は次の繰返しで一致照合に使用可能とな
ったし、図11dで、ストリング「abcfgh」は次の繰返し
で一致照合に使用可能となった。

更に、図11a〜図11eから理解されることであるが、解
凍器は「abc」と「fgh」について連続した圧縮出力コー
ドを受け取る。「fgh」の出力コードが受け取られた時
に、解凍器は、前に受け取った圧縮コードに対応して回
復されたストリング「fgh」とストリング「abc」を用い
て、図11a〜図11eに説明され且つ図示されるストリング
を組み立ててストアする。

図12a〜図12gにおいて、本発明の即時の且つインター
リーブされた辞書更新の面によって提供される優れたラ
ンレングス符号化の方法が実証されている。上で論じら
れたように、本発明は繰返し文字または文字群のラン
を、ランの長さとは関係のない２つの圧縮コード記号に
圧縮する。図12a〜図12gは、入力データ文字ストリーム
が繰返し文字群である場合における圧縮辞書13の状態を
連続的に図示する部分探索樹の模式図的表現である。入
力データストリームは「abababax」として例示されてい
る。このサンプル入力において、繰返し文字群のランは
文字群の断片で終わっていることに気がつく。次に述べ
る動作は完全な文字群によるランの終結にも応用可能で
ある。図11a〜図11eにおけるように、仮想のコンマがス
トリングの構文解析を表し、下線が現入力文字を表す。

図12aにおいて、圧縮辞書13は最初の２つの入力文字
によって一致照合されるストリング「ab」をストアして
いる。したがって、「ab」のコードが矢印250で表され
るように出力される。入力からのストリング「ab」の構
文解析は仮想のコンマ251で示される。

図12bにおいて、現入力文字「ａ」は、矢印252で示さ
れるように、ストアされたストリング「ab」の最初の文
字と一致する。「ab」のコードは先の圧縮コードとして
伝送されたので、一致する文字「ａ」が、矢印235で示
されるように、ストリング「ab」の語尾に付加される。
ここで、圧縮辞書13は一致照合に使用できるストリング
「aba」をストアする。

図12cにおいて、次の入力文字「ｂ」はストアされて
いるストリング「aba」の第２の文字と一致する。した
がって、ストリング「aba」はこの文字で拡張される。
このようにして、圧縮辞書13は、ここで、一致照合に使
用できるストリング「abab」をストアする。

入力文字の一致照合とストリング拡張のこのようなシ
ーケンスは、次の３つの入力文字について図12d〜図12f
に図示されている。このように、図12dでストリング「a
baba」がストアされて一致照合に使用可能になり、図12
eでストリング「ababab」がストアされて一致照合に使
用可能となり、図12fでストリング「abababa」がストア
されて一致照合に使用可能になる。

この繰返しのシーケンスが続くとき、入力文字の一致
照合とストアされるストリングの拡張が探索樹の同じブ
ランチで行われて、一致を破る文字が受け取られるまで
続くことが分かる。このようにして続いている時に、コ
ード発生器26（図１）は絶えず新しいコードを供給し
て、新しくつくられたノードにストリングをストアでき
るようにする。この点まで、解凍器は圧縮器で起きてい
る、図12b〜図12fに図示される活動に気付いていない。
解凍器の受け取る最後の情報は、図12aに関して記載さ
れるストリング「ab」の出力コードであった。

図12gにおいて、圧縮辞書13に「ababax」はないの
で、入力文字「ｘ」は一致を破る。したがって、最長一
致「ababa」のコードが矢印254で示されるように出力さ
れる。したがって、このストリングは仮想のコンマ255
で表されるように入力から構文解析される。図12gから
理解されることであるが、２つの追加されたストリング
が最も長い一致照合されたストリングを越えて圧縮器の
辞書13にストアされている。これらのストリングはノー
ド256と257で表される。

このようにして、図12a〜図12gから理解されることで
あるが、繰返し文字群のストリング「ababa」は参照数
字250と254で示される２つのコード記号に圧縮された。
更に、理解されることであるが、文字グループ「ab」の
繰返しランは図12fを越えて図示されているより長いラ
ンで続いたとしても、たった２つのコード記号だけが圧
縮に使用される。繰返しランは繰返す文字グルーブの一
部分で終わるが、完全なグループ「ab」で終結するよう
に続けることもできることがわかる。

前記より理解されることであるが、図12gに参照数字2
54で示される出力コードは、解凍器は未だストリング
「ababa」をストアしていないので、解凍器では認識さ
れない。図８の未認識コード処理により、図12bおよび
図12cに示されるその接頭部と同様に、ストリング「aba
ba」が組み立てられてストアされる。更に、未認識コー
ド処理により、図12gに参照数字256と257で示される追
加の拡張されたストリングが組み立てられてストアされ
る。

図８で、ブロック160〜167の処理が、矢印254で示さ
れる未認識圧縮コードに対応して、「ababa」を組み立
て、ストアし、さらに出力する。ブロック170〜175の処
理は、追加のストリング256と257を組み立ててストアす
る。

図12a〜図12gの例において、未認識コード処理で使用
された前ストリングはストリング「ab」であり、これ
は、解凍器が図12aに対応してストリング回復サイクル
を行った時に、解凍器辞書に既にストアされた。図８に
おいて、パラメータｎは２であり、インデックスｉはイ
ンクリメントされるモジュロ２であり、図12b〜図12fに
図示されるストリングを組み立てるためにブロック163
と172に連続的に繰返して文字「ab」を与える。

以上より理解されることであるが、繰返し文字または
繰返し文字群のランが不一致文字によってまたは入力文
字を使い切ったことによって終結される時に、未認識コ
ードコード処理によって適当なストリングが組み合てら
れて回復される。ランは、繰返し文字群の多文字群の断
片で、または完全なグループで終結する。図12a〜図12g
は不一致文字「ｘ」での終結を示し、また繰返しグルー
プの断片での終結を図示している。図12gで、ランは繰
返しグループ「ab」の断片「ａ」で終結している。繰返
しグループが完全なグループ「ab」で終結するとき、そ
の適当な動作は上記の説明から容易に理解される。

以上より理解されることであるが、上記の処理は辞書
13および43にストアされストリングの接頭部の特性を保
存する。即ち、ストアされたストリングの接頭部も辞書
に存在する。

上記の実施例は、入力データ文字信号のストリームを
圧縮している。入力データ文字は、任意の対応する文字
ビットサイズを有するどのようなアルファベットサイズ
でもよい。例えば、データ文字は、８ビット文字の256
文字ASCIIアルファベットのようなアルファベットを越
えるどのような本文、例えばASCII文字、であってもよ
い。また、入力データは、１ビットサイズの文字を有す
る２進文字アルファベット１と０を越える２進文字であ
ってもよい。例えば、このようなアルファベットはビッ
トマップの画像で生じる。下線の引かれた２進データの
２文字アルファベットを越えて、本文データの圧縮をす
ることができることは理解される。

上記の実施例は、最長一致の探索の観点から説明され
た。理解されることであるが、本発明による即時の且つ
インターリーブされた更新処理は、必ずしも最長ではな
いストリングを一致照合するシステムにおいても使用で
きる。

本発明の上記の実施例は、ハードウェア、ファームウ
ェア、ソフトウェアまたはそれらの組合せで実現できる
ことが理解される。種々の上記の機能を行えるように、
個別回路部品を容易に実現することができる。ソフトウ
ェアによる実施では、適当なマイクロプロセッサを、上
記のフローチャートから容易に作られる符号化でプログ
ラムして使用できる。

本発明はその好ましい実施例で説明されたが、使用さ
れた単語は制限するものではなくて説明の目的のもので
有り、また、添付の請求の範囲内で、より広い面から見
た本発明の真の範囲と精神から逸脱することなく変更可
能であることは理解されるべきことである。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 クーパー，アルバート，ビー. アメリカ合衆国 10021 ニューヨーク 州 ニューヨーク 20 イースト 74 ティーエイチ ストリート ナンバー 14シー (56)参考文献 特開 昭60−116228（ＪＰ，Ａ) 特開 平４−156109（ＪＰ，Ａ) 特開 平４−256192（ＪＰ，Ａ) 特開 平４−265020（ＪＰ，Ａ) 特開 平４−306019（ＪＰ，Ａ) 国際公開96／21283（ＷＯ，Ａ１) (58)調査した分野(Int.Cl.⁷，ＤＢ名) H03M 7/42

Claims (50)

(57)【特許請求の範囲】
1. 【請求項１】データ文字ストリーム（11）を圧縮コード
   ストリーム（12）に圧縮するデータ圧縮装置（10）であ
   って、 データ文字ストリングをストアする記憶手段であって、
   各前記ストリングは関連するコード（16）を有する記憶
   手段（13）と、 前記データ文字ストリームを前記ストアされたストリン
   グと比較することによって、前記データ文字ストリーム
   を探索し、所定の一致が確定するまで文字ごとの一致照
   合を行う手段（103〜105）と、 前記所定の一致と関連するコードを出力して、前記圧縮
   コードストリームを供給する手段（106）と、 拡張されたストリングを前記記憶手段に取込む手段であ
   って、前記拡張されたストリングの取込みは前記文字ご
   との一致照合によるデータ文字の一致照合とインターリ
   ーブされ、前記拡張されたストリングは、最後に出力し
   たコードに応答する先に一致照合したストリングを拡張
   したストリングにより構成され、該拡張は前記文字ごと
   の一致照合の間に一致照合される各データ文字で順に行
   われ、前記文字ごとの一致照合の間に一致照合される前
   記データ文字ごとに１つの拡張されたストリングが取込
   まれ、前記文字ごとの一致照合による前記データ文字の
   一致照合とインターリーブされた前記拡張されたストリ
   ングの取込みは前記所定の一致が確定するまで続く手段
   （107、112〜114）と、 それぞれのコードを前記拡張されたストリングに割り当
   てる手段（112）とを具えたことを特徴とするデータ圧
   縮装置。
2. 【請求項２】前記取込む手段は、各前記データ文字が一
   致照合される時で次のデータ文字が一致照合される前に
   前記拡張されたストリングの１つを前記記憶手段に取込
   むように動作することを特徴とする請求項１に記載の装
   置。
3. 【請求項３】前記所定の一致は、前記データ文字ストリ
   ームと前記ストアされたストリングとの間の最長の一致
   により構成され、 前記出力する手段は前記圧縮コードストリームを供給す
   るために前記最長一致と関連するコードを出力するよう
   に動作することを特徴とする請求項２に記載の装置。
4. 【請求項４】前記装置は連続するストリング一致照合サ
   イクルで動作し、最長の一致照合されたストリングの各
   々は前記連続するサイクルで確定され、現サイクルは先
   のサイクルに続き、 前記先に一致照合したストリングは前記先のサイクルで
   一致照合され、前記最後に供給したコードは前記先のサ
   イクルで供給され、 前記文字ごとの一致照合は前記現サイクルで行われ、前
   記先に一致照合したストリングは前記現サイクルの間に
   前記各データ文字で拡張されることを特徴とする請求項
   ３に記載の装置。
5. 【請求項５】前記探索する手段および前記取込む手段
   は、部分ストリングＷおよびデータ文字Ｃを一致照合す
   るときに、前記データ文字ＣをストリングPWの拡張文字
   として（但し、Ｐは前記先に一致照合したストリングで
   あり、Ｗは現サイクルで一致照合されるプロセスにあ
   る）前記拡張されたストリングの１つを前記記憶手段に
   取込むように動作することを特徴とする請求項４に記載
   の装置。
6. 【請求項６】前記探索する手段は、前記文字ごとの一致
   照合の間にデータ文字が一致しない時を確定すること
   で、前記最長一致が達成された時を確定するように動作
   し、 前記探索する手段は、一致しなかった前記データ文字か
   ら次のストリング一致照合サイクルを始める手段（11
   0）を含むことを特徴とする請求項４に記載の装置。
7. 【請求項７】それぞれ関連するコードを有する全ての単
   一文字ストリングで前記記憶手段を初期化する手段（10
   0）をさらに具えたことを特徴とする請求項１に記載の
   装置。
8. 【請求項８】圧縮されていない形で最初に遭遇したデー
   タ文字を、そのようなデータ文字を出力するという指示
   に続いて出力する手段と、 前記最初に遭遇したデータ文字を前記記憶手段に単一文
   字ストリングとして取込む手段とをさらに具えたことを
   特徴とする請求項１に記載の装置。
9. 【請求項９】前記指示はゼロコードにより構成されるこ
   とを特徴とする請求項８に記載の装置。
10. 【請求項１０】前記ストリングはリンクされた樹木構造
    で前記記憶手段にストアされ、前記データ文字ストリー
    ムは繰返し文字により構成された繰返し文字ストリング
    を含み、 前記装置は前記繰返し文字ストリングをその長さに関係
    なく２つの圧縮コードに圧縮するように動作することを
    特徴とする請求項４に記載の装置。
11. 【請求項１１】前記先に一致照合したストリングは前記
    繰返し文字により構成され、 前記探索する手段は前記繰返し文字ストリングを前記樹
    木を辿るパスで一致照合するように動作し、 前記取込む手段は前記拡張されたストリングを前記パス
    に取込むように動作し、 それによって、前記繰返し文字ストリングをその長さに
    関係なく２つの圧縮コードに圧縮することを特徴とする
    請求項10に記載の装置。
12. 【請求項１２】前記ストリングはリンクされた樹木構造
    で前記記憶手段にストアされ、前記データ文字ストリー
    ムは繰返し文字群により構成された繰返し文字群ストリ
    ングを含み、 前記装置は前記繰返し文字群ストリングをその長さに関
    係なく２つの圧縮コードに圧縮するように動作すること
    を特徴とする請求項４に記載の装置。
13. 【請求項１３】前記先に一致照合したストリングは前記
    繰返し文字群により構成され、 前記探索する手段は前記繰返し文字群ストリングを前記
    樹木を辿るパスで一致照合するように動作し、 前記取込む手段は前記拡張されたストリングを前記パス
    に取込むように動作し、 それによって、前記繰返し文字群ストリングをその長さ
    に関係なく２つの圧縮コードに圧縮することを特徴とす
    る請求項12に記載の装置。
14. 【請求項１４】データ文字ストリームに応答する、デー
    タ圧縮器によって供給された圧縮コードストリーム（4
    1）を受け取り、前記圧縮コードストリームから前記デ
    ータ文字ストリーム（42）を回復するように動作するデ
    ータ解凍装置（40）であって、 データ文字ストリングをストアする記憶手段（43）であ
    って、各前記ストリングは関連するコード（46）を有す
    る記憶手段と、 現在受信圧縮コードで前記記憶手段にアクセスし、前記
    現在受信圧縮コードに応答するストリングを前記記憶手
    段から回復して、そのデータ文字を回復する手段（132
    〜137、144、145）と、 拡張されたストリングを前記記憶手段に取込む手段であ
    って、前記拡張されたストリングは、先に受信した圧縮
    コードに応答する先に回復したストリングを拡張したス
    トリングにより構成され、該拡張は前記現在受信圧縮コ
    ードに応答する前記回復したストリングの各データ文字
    で順に行われる手段（140〜146）と、 それぞれのコードを前記拡張されたストリングに割り当
    てる手段（141）と、 未認識の圧縮コードの受け取りに応じて、更に拡張され
    たストリング（163）を前記記憶手段に更に取込む手段
    であって、前記更に拡張されたストリングは、前記先に
    受信した圧縮コードに応答する前記先に回復したストリ
    ングを拡張したストリングにより構成され、該拡張は前
    記先に回復したストリングの各データ文字によって順
    に、連続して繰返して、前記未認識の圧縮コードに応答
    するストリングが取込まれるまで行われる手段（160〜1
    66）と、 それぞれのコードを前記更に拡張されたストリングに割
    り当てる手段（162）と、 前記未認識の圧縮コードに応答する前記ストリングのデ
    ータ文字を供給して、前記データ文字を回復する手段
    （167）とを具えたことを特徴とするデータ解凍装置。
15. 【請求項１５】前記更に取込む手段は、追加の拡張され
    たストリング（172）を前記記憶手段に取込むように動
    作し、前記追加の拡張されたストリングは、前記未認識
    の圧縮コード信号に応答する前記ストリングを更に拡張
    したストリングにより構成され、該拡張は前記先に回復
    したストリングのデータ文字によって順に、前記追加の
    拡張されたストリングがある数だけ前記記憶手段に取込
    まれるまで行われ、前記ある数は前記先に回復したスト
    リングを構成するデータ文字の数に等しく（170〜17
    5）、 それぞれのコードを前記追加の拡張されたストリングに
    割り当てる手段（171）を含むことを特徴とする請求項1
    4に記載の装置。
16. 【請求項１６】前記装置は連続するストリング回復サイ
    クルで動作し、それぞれのストリングは前記連続するサ
    イクルで回復され、現サイクルは先のサイクルに続き、 前記先に回復したストリングは前記先のサイクルで回復
    され、前記先に受信した圧縮コードは前記先のサイクル
    で受け取られ、 前記現在受信圧縮コードは前記現サイクルの間に受け取
    られ、 前記取込む手段は前記現サイクルの間に前記拡張された
    ストリングを前記記憶手段に取込むように動作すること
    を特徴とする請求項15に記載の装置。
17. 【請求項１７】前記未認識の圧縮コードは前記現サイク
    ルの間に受け取られ、 前記更に取込む手段は前記更に拡張されたストリングと
    前記追加の拡張されたストリングを、前記現サイクルの
    間に、前記記憶手段に取込むように動作することを特徴
    とする請求項16に記載の装置。
18. 【請求項１８】それぞれ関連するコードを有する全ての
    単一文字ストリングで前記記憶手段を初期化する手段
    （130）をさらに具えたことを特徴とする請求項14に記
    載の装置。
19. 【請求項１９】前記圧縮コードストリームは、圧縮され
    ていない形のデータ文字を、そのようなデータ文字を受
    信中であるという指示の後に含み、 前記圧縮されていない形の前記データ文字は、前記デー
    タ圧縮器が前記データ文字ストリームにおいて最初に遭
    遇したデータ文字に応答し、 前記装置は、 圧縮されていない形で受け取られる前記データ文字を前
    記記憶手段に単一文字ストリングとして取込む手段と、 圧縮されていない形で受け取られる前記データ文字を出
    力する手段とをさらに具えたことを特徴とする請求項14
    に記載の装置。
20. 【請求項２０】前記指示はゼロコードにより構成される
    ことを特徴とする請求項19に記載の装置。
21. 【請求項２１】前記データ文字ストリームは繰返し文字
    により構成された繰返し文字ストリングを含み、前記デ
    ータ圧縮器は前記繰返し文字ストリングを２つの連続し
    た圧縮コードに圧縮するように動作し、 前記ストリングはリンクした樹木構造で前記記憶手段に
    ストアされることを特徴とする請求項17に記載の装置。
22. 【請求項２２】前記先に受信した圧縮コードは前記連続
    した圧縮コードの第１のコードにより構成され、前記未
    認識の圧縮コードは前記連続した圧縮コードの第２のコ
    ードにより構成され、 前記先に回復したストリングは前記繰返し文字により構
    成され、前記未認識の圧縮コードに応答する前記ストリ
    ングは前記繰返し文字ストリングにより構成され、 前記先に回復したストリングは前記樹木を辿るパスにス
    トアされ、 前記取込む手段と前記更に取込む手段は前記更に拡張さ
    れたストリングと前記追加の拡張されたストリングを前
    記パスに取込むように動作することを特徴とする請求項
    21に記載の装置。
23. 【請求項２３】前記データ文字ストリームは繰返し文字
    群により構成された繰返し文字群ストリングを含み、前
    記データ圧縮器は前記繰返し文字群ストリングを２つの
    連続した圧縮コードに圧縮するように動作し、 前記ストリングはリンクされた樹木構造で前記記憶手段
    にストアされることを特徴とする請求項17に記載の装
    置。
24. 【請求項２４】前記先に受信した圧縮コードは前記連続
    した圧縮コードの第１のコードにより構成され、前記未
    認識の圧縮コードは前記連続した圧縮コードの第２のコ
    ードにより構成され、 前記先に回復したストリングは前記繰返し文字群により
    構成され、前記未認識の圧縮コードに応答する前記スト
    リングは前記繰返し文字群ストリングにより構成され、 前記先に回復したストリングは前記樹木を辿るパスにス
    トアされ、 前記取込む手段と前記更に取込む手段は前記更に拡張さ
    れたストリングと前記追加の拡張されたストリングを前
    記パスに取込むように動作することを特徴とする請求項
    23に記載の装置。
25. 【請求項２５】前記更に取込む手段は、前記先に回復し
    たストリング、前記先に回復したストリングを構成する
    データ文字の数、前記未認識の圧縮コード、および前記
    更に拡張されたストリングに割り当てられた前記コード
    に従って前記更に拡張されたストリングを生成するよう
    に動作し、前記更に拡張されたストリングの１つは前記
    未認識の圧縮コードに応答するストリングであることを
    特徴とする請求項14に記載の装置。
26. 【請求項２６】データ文字ストリーム（103）を圧縮コ
    ードストリーム（116）に圧縮するデータ圧縮方法（図
    ６）であって、 データ文字ストリングを記憶手段（13）にストアするス
    テップであって、各前記ストリングは関連するコード
    （16）を有するステップと、 前記データ文字ストリームを前記ストアされたストリン
    グと比較する（104）ことによって、前記データ文字ス
    トリームを探索し、所定の一致が確定するまで文字ごと
    の一致照合を行うステップ（103〜105）と、 前記所定の一致と関連するコードを出力して、前記圧縮
    コードストリームを供給するステップ（106）と、 拡張されたストリングを前記記憶手段に取込むステップ
    であって、前記拡張されたストリングの取込みは前記文
    字ごとの一致照合によるデータ文字の一致照合とインタ
    ーリーブされ、前記拡張されたストリングは、最後に出
    力したコードに応答する先に一致照合したストリングを
    拡張したストリングにより構成され、該拡張は前記文字
    ごとの一致照合の間に一致照合される各データ文字で順
    に行われ、前記文字ごとの一致照合の間に一致照合され
    る前記データ文字ごとに１つの拡張されたストリングが
    取り込まれ、前記文字ごとの一致照合による前記データ
    文字の一致照合とインターリーブされた前記拡張された
    ストリングの取込みは前記所定の一致が確定するまで続
    くステップ（107、112〜114）と、 それぞれのコード信号を前記拡張されたストリングに割
    り当てるステップ（112）とを具えたことを特徴とする
    データ圧縮方法。
27. 【請求項２７】前記取込むステップは、各前記データ文
    字が一致照合される時で次のデータ文字が一致照合され
    る前に前記拡張されたストリングの１つを前記記憶手段
    に取込むステップを含むことを特徴とする請求項26に記
    載の方法。
28. 【請求項２８】前記所定の一致は、前記データ文字スト
    リームと前記ストアされたストリングとの間の最長の一
    致により構成され、 前記出力するステップは前記圧縮コードストリームを供
    給するために前記最長一致と関連するコードを出力する
    ステップを含むことを特徴とする請求項27に記載の方
    法。
29. 【請求項２９】前記方法が連続するストリング一致照合
    サイクルで動作し、最長の一致照合されたストリングの
    各々は前記連続するサイクルで確定され、現サイクルは
    先のサイクルに続き、 前記先に一致照合したストリングは前記先のサイクルで
    一致照合され、前記最後に供給したコードは前記先のサ
    イクルで供給され、 前記文字ごとの一致照合は前記現サイクルで行われ、前
    記先に一致照合したストリングは前記現サイクルの間に
    前記各データ文字で拡張されることを特徴とする請求項
    28に記載の方法。
30. 【請求項３０】前記探索するステップおよび前記取込む
    ステップは、部分ストリングＷおよびデータ文字Ｃを一
    致照合するときに、前記データ文字ＣをストリングPWの
    拡張文字として（但し、Ｐは前記先に一致照合したスト
    リングであり、Ｗは現サイクルで一致照合されるプロセ
    スにある）前記拡張されたストリングの１つを前記記憶
    手段に取込むように実行されることを特徴とする請求項
    29に記載の方法。
31. 【請求項３１】前記探索するステップは、前記文字ごと
    の一致照合の間にデータ文字が一致しない時を確定する
    ことで、前記最長一致が達成された時を確定するステッ
    プを含み、 前記探索するステップは、一致しなかった前記データ文
    字から次のストリング一致照合サイクルを始めるステッ
    プ（110）を含むことを特徴とする請求項29に記載の方
    法。
32. 【請求項３２】それぞれ関連するコードを有する全ての
    単一文字ストリングで前記記憶手段を初期化するステッ
    プ（100）をさらに具えたことを特徴とする請求項26に
    記載の方法。
33. 【請求項３３】圧縮されていない形で最初に遭遇したデ
    ータ文字を、そのようなデータ文字を出力するという指
    示に続いて出力するステップと、 前記最初に遭遇したデータ文字を前記記憶手段に単一文
    字ストリングとして取込むステップとをさらに具えたこ
    とを特徴とする請求項26に記載の方法。
34. 【請求項３４】前記指示はゼロコードにより構成される
    ことを特徴とする請求項33に記載の方法。
35. 【請求項３５】前記ストアするステップは前記ストリン
    グをリンクされた樹木構造で前記記憶手段にストアする
    ステップを含み、 前記データ文字ストリームは繰返し文字により構成され
    た繰返し文字ストリングを含み、 前記方法は前記繰返し文字ストリングをその長さに関係
    なく２つの圧縮コードに圧縮することを特徴とする請求
    項29に記載の方法。
36. 【請求項３６】前記先に一致照合したストリングは前記
    繰返し文字により構成され、 前記探索するステップは前記繰返し文字ストリングを前
    記樹木を辿るパスで一致照合するステップを含み、 前記取込むステップは前記拡張されたストリングを前記
    パスに取込むステップを含み、 それによって、前記繰返し文字ストリングをその長さに
    関係なく２つの圧縮コードに圧縮することを特徴とする
    請求項35に記載の方法。
37. 【請求項３７】前記ストアするステップは前記ストリン
    グをリンクされた樹木構造で前記記憶手段にストアする
    ステップを含み、 前記データ文字ストリームは繰返し文字群により構成さ
    れた繰返し文字群ストリングを含み、 前記方法は前記繰返し文字群ストリングをその長さに関
    係なく２つの圧縮コードに圧縮することを特徴とする請
    求項29に記載の方法。
38. 【請求項３８】前記先に一致照合したストリングは前記
    繰返し文字群により構成され、 前記探索するステップは前記繰返し文字群ストリングを
    前記樹木を辿るパスで一致照合するステップを含み、 前記取込むステップは前記拡張されたストリングを前記
    パスに取込むステップを含み、 それによって、前記繰返し文字群ストリングをその長さ
    に関係なく２つの圧縮コードに圧縮することを特徴とす
    る請求項37に記載の方法。
39. 【請求項３９】データ文字ストリームに応答する、デー
    タ圧縮器によって供給された圧縮コードストリーム（13
    2）を受け取り、前記圧縮コードストリームから前記デ
    ータ文字ストリーム（137）を回復するデータ解凍方法
    （図７）であって、 データ文字ストリングを記憶手段（43）にストアするス
    テップであって、各前記ストリングは関連するコード
    （46）を有するステップと、 現在受信圧縮コードで前記記憶手段にアクセスし、前記
    現在受信圧縮コード信号に応答するストリングを前記記
    憶手段から回復して、そのデータ文字を回復するステッ
    プ（132〜137、144、145）と、 拡張されたストリングを前記記憶手段に取込むステップ
    であって、前記拡張されたストリングは、先に受信した
    圧縮コードに応答する先に回復したストリングを拡張し
    たストリングにより構成され、該拡張は前記現在受信圧
    縮コードに応答する前記回復したストリングの各データ
    文字で順に行われるステップ（140〜146）と、 それぞれのコードを前記拡張されたストリングに割り当
    てるステップ（141）と、 未認識の圧縮コードの受け取りに応じて、更に拡張され
    たストリング（163）を前記記憶手段に更に取込むステ
    ップであって、前記更に拡張されたストリングは、前記
    先に受信した圧縮コードに応答する前記先に回復したス
    トリングを拡張したストリングにより構成され、該拡張
    は前記先に回復したストリングの各データ文字によって
    順に、連続して繰返して、前記未認識の圧縮コードに応
    答するストリングが取込まれるまで行われるステップ
    （160〜166）と、 それぞれのコードを前記更に拡張されたストリングに割
    り当てる（162）ステップと、 前記未認識の圧縮コードに応答する前記ストリングのデ
    ータ文字を供給して、前記データ文字を回復するステッ
    プ（167）とを具えたことを特徴とするデータ解凍方
    法。
40. 【請求項４０】前記更に取込むステップは、追加の拡張
    されたストリング（172）を前記記憶手段に取込むステ
    ップを含み、前記追加の拡張されたストリングは、前記
    未認識の圧縮コード信号に応答する前記ストリングを更
    に拡張したストリングにより構成され、該拡張は前記先
    に回復したストリングのデータ文字によって順に、前記
    追加の拡張されたストリングがある数だけ前記記憶手段
    に取込まれるまで行われ、前記ある数は前記先に回復し
    たストリングを構成するデータ文字の数に等しく（170
    〜175）、 それぞれのコードを前記追加の拡張されたストリングに
    割り当てるステップ（171）を含むことを特徴とする請
    求項39に記載の方法。
41. 【請求項４１】前記方法は連続するストリング回復サイ
    クルで動作し、それぞれのストリングは前記連続するサ
    イクルで回復され、現サイクルは先のサイクルに続き、 前記先に回復したストリングは前記先のサイクルで回復
    され、前記先に受信した圧縮コードは前記先のサイクル
    で受け取られ、 前記現在受信圧縮コードは前記現サイクルの間に受け取
    られ、 前記取込むステップは前記現サイクルの間に前記拡張さ
    れたストリングを前記記憶手段に取込むステップを含む
    ことを特徴とする請求項40に記載の方法。
42. 【請求項４２】前記未認識の圧縮コードは前記現サイク
    ルの間に受け取られ、 前記更に取込むステップは前記更に拡張されたストリン
    グと前記追加の拡張されたストリングを、前記現サイク
    ルの間に、前記記憶手段に取込むステップを含むことを
    特徴とする請求項41に記載の方法。
43. 【請求項４３】それぞれ関連するコードを有する全ての
    単一文字ストリングで前記記憶手段を初期化するステッ
    プ（130）をさらに具えたことを特徴とする請求項39に
    記載の方法。
44. 【請求項４４】前記圧縮コードストリームは、圧縮され
    ていない形のデータ文字を、そのようなデータ文字を受
    信中であるという指示の後に含み、 前記圧縮されていない形の前記データ文字は、前記デー
    タ圧縮器が前記データ文字ストリームにおいて最初に遭
    遇したデータ文字に応答し、 前記方法は、 圧縮されていない形で受け取られる前記データ文字を前
    記記憶手段に単一文字ストリングとして取込むステップ
    と、 圧縮されていない形で受け取られる前記データ文字を出
    力するステップとをさらに具えたことを特徴とする請求
    項39に記載の方法。
45. 【請求項４５】前記指示はゼロコードにより構成される
    ことを特徴とする請求項44に記載の方法。
46. 【請求項４６】前記データ文字ストリームは繰返し文字
    により構成された繰返し文字ストリングを含み、前記デ
    ータ圧縮器は前記繰返し文字ストリングを２つの連続し
    た圧縮コードに圧縮し、 前記ストアするステップは前記ストリングをリンクした
    樹木構造で前記記憶手段にストアするステップを含むこ
    とを特徴とする請求項42に記載の方法。
47. 【請求項４７】前記先に受信した圧縮コードは前記連続
    した圧縮コードの第１のコードにより構成され、前記未
    認識の圧縮コードは前記連続した圧縮コードの第２のコ
    ードにより構成され、 前記先に回復したストリングは前記繰返し文字により構
    成され、前記未認識の圧縮コードに応答する前記ストリ
    ングは前記繰返し文字ストリングにより構成され、 前記先に回復したストリングは前記樹木を辿るパスにス
    トアされ、 前記取込むステップと前記更に取込むステップは前記更
    に拡張されたストリングと前記追加の拡張されたストリ
    ングを前記パスに取込むステップを含むことを特徴とす
    る請求項46に記載の方法。
48. 【請求項４８】前記データ文字ストリームは繰返し文字
    群により構成された繰返し文字群ストリングを含み、前
    記データ圧縮器は前記繰返し文字群ストリングを２つの
    連続した圧縮コードに圧縮し、 前記ストアするステップは前記ストリングをリンクされ
    た樹木構造で前記記憶手段にストアするステップを含む
    ことを特徴とする請求項42に記載の方法。
49. 【請求項４９】前記先に受信した圧縮コードは前記連続
    した圧縮コードの第１のコードにより構成され、前記未
    認識の圧縮コードは前記連続した圧縮コードの第２のコ
    ードにより構成され、 前記先に回復したストリングは前記繰返し文字群により
    構成され、前記未認識の圧縮コードに応答する前記スト
    リングは前記繰返し文字群ストリングにより構成され、 前記先に回復したストリングは前記樹木を辿るパスにス
    トアされ、 前記取込むステップと前記更に取込むステップは前記更
    に拡張されたストリングと前記追加の拡張されたストリ
    ングを前記パスに取込むステップを含むことを特徴とす
    る請求項48に記載の方法。
50. 【請求項５０】前記更に取込むステップは、前記先に回
    復したストリング、前記先に回復したストリングを構成
    するデータ文字の数、前記未認識の圧縮コード、および
    前記更に拡張されたストリングに割り当てられた前記コ
    ードに従って前記更に拡張されたストリングを生成する
    ステップを含み、前記更に拡張されたストリングの１つ
    は前記未認識の圧縮コードに応答するストリングである
    ことを特徴とする請求項39に記載の方法。