JP3006766B2

JP3006766B2 - 圧縮された状態におけるデータをエンコードし、デコードし、伝送する方法と装置

Info

Publication number: JP3006766B2
Application number: JP1508289A
Authority: JP
Inventors: クラーク、アラン・ダグラス
Original assignee: プリテイッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー
Priority date: 1988-07-05
Filing date: 1989-07-04
Publication date: 2000-02-07
Anticipated expiration: 2015-02-07
Also published as: AU626317B2; ATE92224T1; DE68907812D1; HK130194A; ES2041997T3; EP0350281B1; CA1330838C; DE68907812T2; US5153591A; GB8815978D0; JPH04500571A; AU4037089A; WO1990000837A1; EP0350281A1

Description

【発明の詳細な説明】（技術分野）本発明はデータを圧縮する方法および装置、圧縮され
たデータをデコードする方法および装置、データを送信
する方法、および圧縮されたデータを利用するデータ処
理装置に関する。上記方法および装置はサーチツリー
（検索木）を有するディクショナリを必要とする適応ス
トリングエンコード技術とこのサーチツリーを維持する
ための手段をすべて利用する。本発明は特殊だが専用的
ではないZiv−Lempelアルゴリズムを利用する適応スト
リングエンコードに適用できる。このアルゴリズムの基
本的な手法はIEEE Transactions IT−23,3rd May 1977
pp337−343“A Universal Algorithm for Sequential D
ata Compression"−J.Ziv and A.Lempelに記載されてい
る。

（背景技術）基本的なZiv−Lempelエンコーダは各エントリ（登
録）が関連するインデックス番号を持つディクショナリ
を有する。初め、ディクショナリはソースである基本的
なアルファベットのみを含む。エンコード処理中、新し
いディクショナリエントリは単独のシンボルを存在する
エントリに追加することによって作られる。ディクショ
ナリはソースアルファベットの接続されたシンボルのサ
ーチツリー構造であると考えられるだろう。ツリーにお
けるノード（節点）はツリーの根で始まるシンボルの特
別のシーケンスに対応し、データはツリーにおけるノー
ドに対応する圧縮されていない入力データのシンボルの
ストリングを認識し、適合したノードに対応するメモリ
位置のインデックスを送信することによって圧縮され
る。対応するサーチツリーは圧縮されたデータを表すイ
ンデックスを受信するデコーダに供給され、圧縮された
データをそれ本来の構成に復元するために逆処理がデコ
ーダによって行われる。エンコーダのサーチツリーは、
さらにシンボルのストリングが入力データにおいて識別
されるエンコード処理中に徐々に成長し、圧縮されたデ
ータをデコードするためのデコーダをイネーブルにする
ために、そのサーチツリーはエンコーダのサーチツリー
に対応するように更新しなければならない。

Ziv−Lempelアルゴリズムはサーチツリーをその基本
的な構成で記憶するために無限に大きなメモリを必要と
するので、Ziv−Lempelアルゴリズムを実際に実行する
のが困難であることがわかってきた。しかしながら、Su
ssenguth（ACM Sort Symposium 1962）によって開示さ
れている“trie"構造のようなデータ構造の使用によっ
て、テキストストリングに関連した記憶効率やサーチ時
間が大きく向上できる。EPA127815（Miller ＆ Wegma
n）やEPA129439（Welch）には、trie構造の使用を基に
したZiv−Lempelアルゴリズムと同じ手法が開示されて
いる。

EPA127,815（Miller ＆ Wegman）では、メモリ効率を
高め、エンコード処理をスピードアップするZiv−Lempe
lアルゴリズムについての改良手法が記載されている。
ディクショナリは、単独のキャラクタを含む各ノードと
プレフィックスストリングを表す親ノードに対するポイ
ンタと共に、ツリーの構造で保持される。ハッシュテー
ブルは、適合したサブストリングと次の入力キャラクタ
が与えられた場合、拡張されたサブストリングがディク
ショナリにあるかどうかを判定するために用いられる。
しかしながら、ハッシュテーブルには、ディクショナリ
をエンコードするのに用いられる基本的なツリー構造の
記憶に対して必要なメモリに加えて、十分な容量のメモ
リや処理時間が必要である。

EPA129,439（Welch）では、入力メッセージにおける
シンボルのストリングが認識および記憶される高速デー
タ圧縮伸張装置および方法が開示されている。ストリン
グはストリングテーブルに入力され、ストリングテーブ
ルにおいて、Ｎ個（典型的にはＮは１から４）のハッシ
ュテーブルアドレスのセットを与えるために先のコード
信号と拡張キャラクタを含むハッシュキーを利用するハ
ッシュ機能によってサーチされる。Ｎ個のRAM位置はシ
ーケンシャルにサーチされ、もしアイテムがＮ個の位置
にない場合、そのアイテムはテーブルにないとみなされ
る。この手順は圧縮効率を減少するといわれるが、実質
的に実行が簡単であるといわれる。

US 4,612,532（Bacon et al）では、Ziv−Lempelアル
ゴリズムを基にせず、キャラクタが発生する頻度の順序
で、各キャラクタが通常続くキャラクタの“follow se
t"テーブルに関連したキャラクタの流れの動的エンコー
ドのためのシステムが開示されている。それらのテーブ
ルは予め決められた長さを有し、それゆえ、ツリーの枝
分れの度合は必らず制限される。

米国公報（US4,464,650）は、Ziv−Lempelアルゴリズ
ムに基づいて、入力データを圧縮する方法について開示
している。この方法は、メモリを備えたプロセッサにデ
ータの連続記号を送り込み、入力データの記号ストリン
グ（列）から、記号ストリングを表現するパス（path）
を有するメモリに、記号の探索木の形式でディクショナ
リを発生し、以前に探索木に格納されたパスを有する入
力データに記号ストリングを整合し、さらに格納された
パスから入力データに応じた圧縮出力データを発生する
各ステップからなる。しかしながら、回路群に利用され
るデータ構造は高度に複雑であり、さらにハッシング
（hashing）機能が要求されている。

説明される型のエンコーダの実現に固有の特殊な問題
は、探索木が利用可能なメモリ空間の限界まで成長した
ときに発生する。新たなストリングを記憶するためのメ
モリ空間の確保のために、探索木のサイズを引き下げる
（即ち、刈り取る）ことが必要である。このような機能
を実現するいくつかの周知の方法がある。後えばコンピ
ュータ・アーキテクチャと並列処理という書籍（Hwang
とBriggs著、McGraw Hill 1985年）に掲載されてい
る。通常使用される技術として、MillerとWegman（EPA1
27815に記載）によりZiv−Lempelアルゴリズムを適用し
たLRU法（Least Recently Used）がある。さらに、Ma
yneとJames（Computer journal 1975年18,2 157〜16
0ページに記載されているInformation Compression b
y Factorising Commo Srings）により同類のストリ
ング・エンコーディング・アルゴリズムを適用したLFU
法（Least Frequently Used）、FIFO（First In Fi
rst Out）、LIFO（Last In First Out）、CLOCKア
ルゴリズムおよびランダム置換え法がある。後半の４つ
の技術は、Ziv−Lempelアルゴリズムを適用しない内容
である。圧縮効果に不利益をもたらす初期状態に戻すと
きに、探索木をリセットすることが知られている。ま
た、メモリ容量が不足したときに、データ交換特性に悪
影響を及ぼすため、新たなストリングの追加を中止する
ことが知られている。

本発明の目的は、これらの先行技術に関する改善を提
供することにある。このような目的を達成するために、
本発明は以下のような構成を有する方法を提供すること
にある。この方法は、探索記憶領域を有するメモリを備
えたプロセッサによりデータの連続記号を読出し、入力
データの記号ストリング（列）から、記号ストリングを
表現するパス（path）を有するメモリに記号の探索木の
形式でディクショナリを発生し、以前に探索木に格納さ
れたパスを有する入力データに記号ストリングを整合
し、さらに格納されたパスから入力データに応じた圧縮
出力データを発生する各ステップからなる。探索木に格
納された記号群は、２つの異なるタイプのリンクしてい
るポインタによりパスの構成にリンクされている。格納
された記号群間の第１のタイプのポインタは、これらの
記号群が入力された記号順に位置を与えられた記号の中
から二者択一が可能であることを指示している。さら
に、格納された記号群間の第２のタイプのポインタは、
これらの記号群の両者が必要に応じて、記号順に発生す
ることが可能であることを指示している。このような構
成において、メモリが満杯のとき、探索木の一連の索引
記憶領域が探索木のノードを含むならば、テストされて
削除される。この探索木は、他のノードを指示する第２
のタイプのリンクしているポインタを備えておらず、さ
らに新たなディクショナリ・エントリ（辞書エントリ、
辞書登録）のために利用可能な自由記憶領域も備えてい
ない。

前記のような見地において、接頭語（prefix）が形成
されていない木により表現されているストリングの幾つ
かまたは全部の削除に応じて、探索木の索引記憶領域の
テストおよび削除を行なう。この特徴は制限されたサイ
ズのメモリに高度に複雑な探索木を格納することを可能
し、前記の米国公報（US4,464,650）とEPA127815の両者
の構成と比較すれば、有用な簡単化を実現することがで
きる。

また、米国公報（US4,464,650）は、対応する圧縮デ
ータをデコードする方法について開示している。この方
法は、メモリを備えたプロセッサにデータの連続記号を
送り込み、記号の探索木の形式でディクショナリをメモ
リに格納し、さらに圧縮データをデコードデータに変換
するための探索木を利用する各ステップからなる。

他の見地として、本発明は前記の方法により圧縮され
た圧縮データをデコードする方法を提供する。この方法
は、メモリを備えたプロセッサが圧縮データの連続文字
列を読出し、圧縮データから組み立てられた記号群の探
索木の形式でディクショナリをメモリに格納し、さらに
圧縮データをデコードデータに変換するための探索木を
利用する各ステップからなる。探索木に格納された記号
群は、２つの異なるタイプのリンクしているポインタに
よりパスの構成にリンクされている。格納された記号群
間の第１のタイプのポインタは、これらの記号群が同一
記号数と同一の接頭語を有する記号群のデコードされた
異種のストリングを関連付け、そのような異種のストリ
ングの各最後の記号であることを指示している。さら
に、格納された記号群間の第２のタイプのポインタは、
これらの記号群がデコードされた出力記号のストリング
の連続した記号群であることを指示している。このよう
な構成において、メモリが一杯の時には、前記探索木の
一連のインデックスされた索引記憶領域は、もしもその
索引記憶領域が他のノードに向いている前記第２のタイ
プのリンクしているポインタを有しない探索木のノード
を含む場合にはテストされ削除され、結果として自由に
された索引記憶領域は新しいディクショナリのエントリ
が可能となる。

また、US4,464,650には、入力データの連続した受信
シンボルを受信可能なプロセッサと、メモリと、入力デ
ータにおけるシンボルのストリングを表すパスを有する
シンボルのサーチツリーをメモリに格納する手段と、入
力データにおけるシンボルストリングとサーチツリー内
の予め格納されたパスとの整合をとり、入力データに対
応する圧縮された出力データを格納されたパスから発生
する手段とを具備する入力データ圧縮のためのエンコー
ダも開示している。

この発明の別の見地によれば、入力データを圧縮する
エンコーダであって、入力データの連続したシンボルを
受信可能なプロセッサと、指標付きメモリロケーション
を有するメモリと、入力データにおけるシンボルのスト
リングを表すパスを有するシンボルのサーチツリーをメ
モリに格納する手段と、入力データのシンボルストリン
グとサーチツリー内の予め格納されたパスとの整合をと
り、入力データに対応する圧縮された出力データを格納
されたパスから発生する手段とを具備し、サーチツリー
内の格納されたシンボルは２つの別個のタイプの連結ポ
インタによって前記パスを形成するように連結されてお
り、格納されたシンボル間における第１タイプのポイン
タは、これら格納されたシンボルが入力シンボルシーケ
ンスの所定の位置において択一可能なシンボルであるこ
とを示し、格納されたシンボル間における第２タイプの
ポインタは、これら格納されたシンボルが入力シンボル
シーケンスにおいて順番に双方とも発生することを示す
エンコーダにおいて、使用時において、プロセッサが、
メモリが満たされた時、サーチツリーのシーケンシャル
な指標付きロケーションを検査し、別のノードを示す第
２タイプの連結ポインタを有しないサーチツリーのノー
ドを含むメモリロケーションを削除して、新規辞書エン
トリ可能な空きメモリロケーションを結果として得るこ
とを決定するように構成されることを特徴とするエンコ
ーダが提供される。

また、US4,464,650は、圧縮データの連続したシンボ
ルを受信可能なプロセッサと、メモリと、辞書をシンボ
ルのサーチツリーの形式でメモリに格納する手段とを具
備し、プロセッサが、サーチツリーを利用して圧縮デー
タをデコードされたデータに変換するように構成されて
いる圧縮データのデコードのためのデコーダを開示して
いる。

この発明の他のもう一つの見地によれば、圧縮データ
をデコードするデコーダであって、圧縮データの連続し
たシンボルを受信可能なプロセッサと、指標付きメモリ
ロケーションを有するメモリと、辞書をシンボルのサー
チツリーの形式でメモリに格納する手段とを具備し、プ
ロセッサが、圧縮データからサーチツリを構築し、サー
チツリーを利用して圧縮データをデコードされたデータ
に変換するように構成され、サーチツリーにおける格納
されたシンボルが２つの別個のタイプの連結ポインタに
よって連結され、格納されたシンボル間の第１タイプの
ポインタは、これらシンボルが異なったデコードされた
シンボルのストリングに関係し、その異なったデコード
されたストリングが同一数のシンボルを有しており、こ
れらシンボルがこのような異なったストリングのそれぞ
れの最終シンボルあり、格納されたシンボル間の第２タ
イプのポインタは、これらシンボルがデコードされた出
力シンボルのストリングにおける連続したシンボルであ
ることを示すデコーダにおいて、使用時に、プロセッサ
が、メモリが満たされた時、サーチツリーのシーケンシ
ャルな指標付きロケーションを検査し、別のノードを示
す第２タイプの連結ポインタを有しないサーチツリーの
ノードを含むメモリロケーションを削除して、新規辞書
エントリ可能な空きメモリロケーションを結果として得
ることを決定するように構成されることを特徴とするデ
コーダが提供される。

さらに、この発明の特徴は従属クレームに記載されて
いる。

この発明に利用できる他の特徴は、コンピュータ、19
84,6月、第８乃至19頁の論文“A Technique for High−
Performance Data Compression"にWelchによって記載さ
れている。この論文は、参考文献として本願に添付され
ており、この論文は、Ziv−Lempelアルゴリズムの初期
性能の改良方法を記載している。最初の段階では、辞書
はほとんど空であり、入力データのシンボルストリング
のエンコードには少ない数のビットで十分である。辞書
が成長すると、コードワードサイズは予め決められた最
大値まで増大する。これは、１万個から２万個までシン
ボルのエンコードの処理性能を改善できるが、処理の複
雑さの増大はいなめない。

この発明の実施例を以下図１乃至図13を参照して説明
する。

図１はこの発明において用いられるサーチ・ツリー
（search tree）を示す図、図２はこの発明において用
いられる他のサーチ・ツリーを示す図、図３はこの発明
にしたがうデータ・コンプレション・プロセスにおける
サーチ・ツリーの展開を示す図、図４はこの発明に用い
られるエンコード用アルゴリズムの基本的なフロー・ダ
イアグラム、図５はこの発明に用いられるデコード用ア
ルゴリズムの基本的なフロー・ダイアグラム、図６はこ
の発明にしたがうデータ・コンプレッション・プロセス
におけるサーチ・ツリーの“リーフ（leaf）”の挿入を
示すダイアグラム、図７はこの発明の辞書を更新するた
めのアルゴリズムを示すフロー・ダイアグラム、図８は
図３（ａ）のサーチ・ツリーの示す図、図９はこの発明
の辞書のアルゴリズムのフロー・ダイアグラム、図10は
この発明にしたがうエンコーダを用いるデータ処理シス
テムの概略的なダイアグラム、図11はこの発明にしたが
うデコーダを用いるデータ処理システムの概略的なダイ
アグラム、図12はこの発明にしたがうエンコーダおよび
デコーダを組込んでいる通信システム部の概略的なダイ
アグラム、図13はメモリの指定されたメモリ・ロケーシ
ョン・アレジメントを示すダイアグラムである。

図１を参照すると、簡素化されたサーチ・ツリーが示
されており、シンボルS1には他の三つの異なるシンボル
S2、S3、S4のいずれか一つが従属している。一例とし、
シンボルS1、S2、S3、S4にはそれぞれ、“c"、“a"、
“e"、“h"が割り当てられ、それによりこのサーチ・ツ
リーは４本のストリング“c"、“ca"、“ce"、“ch"を
示している。したがって、シンボルS1は上記したような
“第２のタイプの”リンク用ポインタ、すなわちダウン
・ポインタＤによってシンボルS2にリンクしている。シ
ンボルS2、S3およびS4は、シンボルS1の後の入力データ
におけるストリングで生じる異なるシンボルであるの
で、それらシンボルは上記したような“第１のタイプ
の”、すなわち右側ポインタＲおよび左側ポインタＬに
よってリンクしている。同様の技術がバイナリ・ツリー
（例えば、デー・クナス（D.Knuth）著“コンピュータ
・プログラミング技術”、第１巻および第３巻）の表示
に用いられている。しかしながら、このデータ構造はｍ
−aryサーチ・ツリーを示すのに用いられている。

リンク用ポインタＤおよびＲを用いることによってシ
ンボルS1からシンボルS2、S3、S4のいずれかにサーチ・
ツリーを介してサーチすることも可能である。また、左
側ポインタＬにしたがうことによってシンボルS4の左側
にサーチすることも可能である。図１（ｂ）において
は、二つのシンボル位置がポインタによってリンクされ
て示されており、これらはフリー・メモリ・ロケーショ
ンのリストを形成している。このリストはサーチ・ツリ
ーからは分離されているけれども、メモリ・ロケーショ
ンはフリー・リストとサーチ・ツリーとの間に移送され
る。入力データのシンボル用総記憶容量はサーチ・ツリ
ーのメモリ・ロケーションおよびフリー・リストにおけ
るメモリ・ロケーションを含んでいる。シンボルS1乃至
S4の一つを特定するためにはシンボルの“親”、すなわ
ち直接先行するダウンポインタＤに接続されたシンボル
を知ることが必要である。これは各場合において、例え
ば親インジケータＰによって指示され、文字“c"がシン
ボルS1として格納された場合には、それはシンボルS2、
S3、S4の親となり、親インジケータＰは“c"のメモリ・
ロケーションを指示する。図１の実施例においては、親
インジケータＰはデコーダのサーチ・ツリーにおいての
み要求され、エンコーダのサーチ・ツリーには要求され
ていない。そうでない場合には、エンコーダのサーチ・
ツリーとデコーダのサーチ・ツリーとは同じである。

そのノードＳが親であるサーチ・ツリー内のノード
は、Ｓの従属ノード、あるいはＳの従属体と呼称され
る。Ｓの従属ノードはＳで示されるストリングに単一文
字を付加することによって形成されたそのストリングを
示す。アルファベットを構成するシンボルのようにいく
つかのノードについては、多数の従属ノードが存在する
ことができる。

図２はより好ましい実施例が示されており、左側ポイ
ンタＬは除外されており、親ポインタＰはエンコーダお
よびデコーダのサーチ・ツリー内に生じる。そうでない
場合には、サーチ・ツリー構造は、図１に示されるそれ
と同じになる。再びくり返して言うと、シンボル・ロケ
ーションのフリー・リストは図２（ｂ）に示すメモリ内
に保持される。

辞書あるいはサーチ・ツリーは、通常、根源となるシ
ンボルの基本セット、あるいはそれから派生した基本長
に二つ以上のシンボルのストリングを示すエントリ（登
録）、あるいはノードのみを含んでいる。多くの適用例
においては、通常のアルファベットの他に付加的なシン
ボルを提供するのが望ましい。そのためには、例えば文
字の繰返し発生をエンコード（ラン・レングス（run l
ength）・エンコード）するための、あるいはストリン
グ・マッチング・プロセス（図13参照）の異常終了を指
示するための手段を必要とする。

シーケンスabcababcabcの符号化は符号化処理中にお
ける検索ツリーの評価を示す第３図及びこの第３図に示
される探索ツリー（木）を表す辞書の実際の内容を示す
テーブルＩを参照して以下に説明する。以下に示される
ように検索ツリーは辞書エントリ１〜ＭのポインタＤ
Ｒ及びＰをメモリに使用できる最大値に設定することに
よって延ばされる。

テーブルＩ（ａ）及び第３（ａ）図に示されるように
辞書は最初、辞書エントリ１、２及び３にそれぞれ記憶
されているシンボルa,b及びｃだけを含んでいる。これ
らは所定の順序で記憶されても良く、従って、辞書エン
トリ１は辞書エントリ１に位置する右側リンクポインタ
２によって辞書エントリ２にリンクされる。好適な方法
は各シンボルの通常の値をテーブルのその位置に一致す
ることである。故に、Ｎシンボルのセットは範囲０〜Ｎ
−１または１〜Ｎ内の通常の値を割り当てられる。この
割当はシンボルを数として表す二値パターンに単に関連
することを含んでも良い。メモリのこれらの内容は第３
（ａ）図に示されるような構成を含んでいる。

多くの応用において、これらの構成の最初のものが好
ましい場合、可能なシンボルのいくつかだけが発生す
る。可能なシンボルのほとんどが発生する応用におい
て、第２の方法が初期文字の検索時間を減少させる。従
って、この第２の方法を以下に説明する。

シーケンスの最初のシンボル、この例では、“a"がエ
ンコーダに入力される。このシンボルはストリングの最
初の文字を表すので、エンコーダは文字の通常の値、こ
の例では、１を使用し、この文字に対応する検索ツリー
内のノードを直接にアクセスする。このノードはエンコ
ーダに知られ、文字で始まる全てのストリングを表すツ
リーの根を形成する。

シーケンスの次のシンボルがエンコーダによって受け
入れられ、現ノードのＤポインタが従属ノードのリスト
を捜し出すために使用される。エンコーダは一般的に次
のシンボルを従属ノードに含まれるシンボルの１つに整
合しようとする。この試みはノード１がある従属性を有
していないのでこの例のように失敗すると、現ノード／
辞書エントリのインデックスを表すコードワード、この
例では、数字１を表すものが送信される。不整合のシン
ボルが新しいストリングの最初を形成するために使用さ
れる。

エンコーダはストリングが再度発生したときにこのス
トリングがもっと効果的に符号化されるように検索ツリ
ーにストリングabを加えることができる。これはこの例
において検索ツリー（辞書）に新しいノード（エント
リ）ナンバー４を作ることによって達成される。テーブ
ルＩ（ｂ）及び第３（ｂ）図に示されるようにノードが
文字“b"を有し、従属ノードに対するＤポインタは最初
ゼロに設定され、ノードの親に従属するリストを他のノ
ードに対するＲポインタはこの例ではゼロに設定され、
親に対するポインタはこの例では１に設定される。

この処理は“b"が新しいストリングの最初の文字とし
て使用される状態で繰り返される。シーケンスの次のシ
ンボルが“c"であり、それゆえ、上述した処理を用い
て、エンコーダはツリーの中のストリング“bc"を見つ
けようとする。このシーケンスはエンコーダには知られ
ていない。故に、ストリング“b"を表すノードのインデ
ックスがデコーダと交信され、ストリング“bc"が検索
ツリーに加えられる。文字“c"が新しいストリングの最
初を形成するために使用される。更新辞書はテーブルＩ
（ｃ）及び第３（ｃ）図の対応する検索ツリーに示され
る。

次の記号ａ、この例ではシーケンスの中の第４番目の
記号が読み出され、検索ストリングに付加される。エン
コーダはその辞書の中でストリングcaの位置を捜し出す
ことを試みる。このストリングは未だ存在しないので、
ｃに対応する辞書へのエントリの指標は、デコーダに通
信され、指標／文字対（3,a）とも見なされるストリン
グcaが辞書（検索ツリー）に加えられる。これにより、
表Ｉ（ｄ）に示す辞書と、第３（ｄ）図に示す検索ツリ
ーが発生される。整合がとれなかった文字ａは新しい検
索ストリングを開始するために使われる。

次の記号ｂが読み出され、検索ストリングに付加さ
れ、ストリングabが形成される。記号ａに対応するＤポ
インタはａの従属変数のリストの位置を捜し出すために
使われる。エンコーダはＲポインタを用いて従属変数の
リストの中から検索ストリングの最後の文字を検索す
る。この例では、指標４で調べられた第１の辞書へのエ
ントリは文字ｂを含むので、エンコーダは検索ストリン
グを辞書エントリと整合する。

入力シーケンス中の第６番目の文字である次の記号ａ
がエンコーダにより読まれ、検索ストリングに付加さ
れ、ストリングabaが形成される。エンコーダは最後に
整合された辞書エントリのＤポインタ、ここでは４、を
用いてストリングabの従属変数のリストの位置を捜し出
す。辞書には従属変数が既知ではないので、表Ｉ
（ｅ）、第３（ｅ）図に示すように、新ストリングab
a、または（4,a）が辞書に加えられる。指標４がデコー
ダに通信され、整合されなかった文字ａが新検索ストリ
ングを開始させるために使われる。

表Ｉ（ｅ）は第３（ｅ）図に対応する。

エンコーダは次の記号を読出し、検索ストリングに付
加し、新検索ストリングabを形成する。エンコーダは上
述した手続を用いてこの新検索ストリングを辞書中で検
索し、辞書エントリ４と整合させる。次の記号ｃを読出
し、検索ストリングに付加し、新検索ストリングabcを
形成する。エンコーダはabの従属変数のリストを検索す
ることにより、この新検索ストリングの位置を捜し出そ
うと試みるが、abcを発見することに失敗する。abの指
標、すなわち４はデコーダに通信され、表Ｉ（ｆ）、第
３（ｆ）図に示すように、新ストリング（4,c）がエン
トリ番号８として辞書に加えられる。

次のストリング・エンコーディング・サイクルの間
に、エンコーダは、ストリング′ca′を辞書中のエント
リー６と整合させ、６をデコーダーに送り、cab又は
（6,b）を辞書に加える。以降のサイクルの間に、エン
コーダは、ストリング′bc′を辞書中のエントリー５と
整合させ、（5,x）を辞書に加え得る。ｘは示されたシ
ーケンスの最後に続く文字である。

このようにシーケンス′abcababcabc′は、インデッ
クス値1234465のリストを使用してエンコードされ得、
それは程度の小さい圧縮を与える。もし、エンコーダよ
り同じシーケンスに再び出くわすようなことがあると、
エンコーダはそれを′abc′（辞書エントリ８）とし
て、′aba′（辞書エントリ７）として、′bc′（辞書
エントリ５）として、′abc′（辞書エントリ８）とし
てエンコードするだろうし、結果的には、シーケンス87
58を伝送することになる。もし記号シーケンスが少なく
とも12回あったとすると、エンコーダは、一つの単一指
標値によってそれを代表し、そのため程度の大きい圧縮
を与える。

エンコーディングアルゴリムズは第４図により詳しく
示される。ステップｉにて変数は初期化され、そのと
き、繰返して、入力メッセージ中の文字に係る最長可能
シーケンスは、ステップiiの検索ツリーストリング上で
位置合わせ（map）される。例えば、入力メッセージの
端にあるシーケンスbcは、第３（ｆ）図中のストリング
bc上で位置合わせ（map）される。ステップiiiでは、整
合されたストリング（例えばbc）又は複数のエンコード
した表現に対応する終了ノード指標が与えられると、検
索ストリングはそれ以降の文字入力メッセージをセット
する（ステップiv）。

追加した次の文字ストリングが辞書に無い場合、スト
リング整合処理は、通常は終了する。しかし、他の場合
には、例えば、最後の文字の受取りからある時間内にソ
ースから文字を受取らない場合、ストリング長がバッフ
ァリミットを超えるある最大値に達した場合、エンコー
ダがストリングのエンコードを開始してからある特定の
時間インターバルが生じた場合、またはスペースシンボ
ルがデータ中に存在した場合にはストリングの整合は例
外的に終了する。これらの例のうちの第２例では、デコ
ーダは例外的な終了が有ることを推察できるであろう。
第１及び第３の例では、エンコーダは終了したストリン
グを示す指標（インデックス）の送信に続いて指示を送
信する。この指示はソースアルファベットのオリジナル
の値以外の付加的制御記号で、これが単一コードワード
としてエンコードされ得る。

整合ストリングの指標及び次の整合がとれなかった文
字は辞書に加えられなければならない。これらが直ちに
辞書に加えられると、エンコーダは、デコーダが辞書エ
ントリと等しい構造を与えるに十分な情報を受取る前
に、新しいエントリの使用を開始する。こうして以前の
指標／文字対はストアされ（ｖ）、そして提示された指
標／文字対もストアされる（vi）。辞書が一杯になった
ら、幾つかの格納スペースを確保するための処理が行わ
れる。新しい辞書エントリを加える処理及び格納スペー
スを確保する処理を以下に説明する。更新（アップデイ
ト）処理で使用される前に、ストアされた指標／文字対
により参照される辞書エントリが削除されないようにす
るために、辞書エントリは以下に説明する手続きを経
て′new′がマークされる。

第５図は対応するデコーデイングアルゴリズムを示し
ている。ステップｉにて変数は初期化される。受け取ら
れたコードワードは、伝送された指標ｊを回復するため
のステップii中で初めデコードされる。なお、指標Ｊは
エンコードされたストリングを示す。Ｊの値は、デコー
ダに対し該デコーダがエンコーディグストリングに対応
する辞書エントリデーコーダを直接にアクセスすること
を可能とする。前記ツリーはエントリＪからストリング
の根（頭）に向って再トレースし見直され、そして当該
ストリングはステップiiiにて読み出される。例えば、
値８が第３（ｆ）図の検索ツリーを持つデコーダにより
受取られたならば、辞書エントリー８のツリーのリーフ
（leaf:字）において記号ｃが見出だされ、そしてｐポ
インタ７及び４を根のａに向けて再トレースし、このシ
ーケンスcbaを読み出す。このシーケンスは、そのとき
オリジナルシーケンスabcを再度発生するべく次のステ
ップiv中で逆転され、それがステップｖ中では制御文字
により制御されないならば、デコーダアルゴリズムは辞
書を最新する処理を行う。

更新された検索ツリーの一例は第６図に示され、そし
て対応するメモリの内容は表IIで示される。

テーブルIIがテーブルＩ（ｆ）に対応し、さらに、辞
書エントリｎにシーケンスabbが付加されていることが
理解できる。このシーケンスをサーチツリーに追加する
ために、ノード７とノード８のリンクが切断され、テー
ブルIIと第６図に示されるように、新しいノードがこれ
らの間に接続される。値ｎと値８を有する新しい右向き
のリンクポインタ（リンキングポインタ）Ｒは第６図に
下線を付して示され、新しい符号ｂも下線を付して示さ
れる。第６図に概念的に示されるサーチツリーの変更
は、テーブルIIの辞書エントリー７のＲポインタの値を
８からｎに変更すること、及び辞書エントリｎに新しい
Ｒポインタ８とＰポインタ４を追加することにより行わ
れる。

更新アルゴリズムが第７図のフローダイアグラムに正
式に示される。このアルゴリズムはエンコーダーとデコ
ーダーの両方に適用される。第１に、辞書が満杯状態か
否かがステップｉで検出される。辞書が満杯の場合、サ
ーチツリーは削られなければならず、この処理手続は第
９図を参照して以下に説明される。しかし、ここでは、
このような事態が発生していないと仮定する。この場
合、空白メモリスロットがフリースロット（第2b図に示
される）からステップiiにおいて取得される。ステップ
iiiで、新しいシンボル（テーブルIIの場合はｂ）がメ
モリスロット（テーブルIIの場合はｎ）に書き込まれ、
必要なポインタ（テーブルIIの場合は辞書エントリーの
Ｒ）が再セットされる。ステップivにおいて、新しいエ
ントリの親ノードが現存する従属関係を有するか否かが
チェックされる。現存する従属関係を有する場合、ステ
ップｖにおいて、上述の例のような従属関係リスト内に
新しいエントリが挿入される。現存する従属関係を有し
ない場合、ステップviにおいて、新しいエントリが親ノ
ードに接続され、親のＤポインタが新しいエントリのメ
モリ参照番号にセットされ、新しいエントリのＰポイン
タが親ノードのメモリレファレンスにセットされる。

第８図を参照して、第８（ａ）図はテーブルIIと第６
図に図示される更新処理手続に続くサーチツリーの状態
を示す。これらのサーチツリーのシンボルは、もしこれ
らの点においてサーチツリーが成長していない場合に
は、有用ではないと考えられる。ここで、前記サーチツ
リーはそれから下方向に延びるＤリンキングポインタを
有しない（そして、該サーチツリーはマッチされたシン
ボルシーケンスの終端で発生する）。そのようなサーチ
ツリー（検索木）の“デッドリーフ”（枯葉）は破線で
第８（ａ）図に示される。そして、第６図に示される更
新処理手続において追加された新しいエントリｂは、そ
こからの新たなサーチツリーの成長を期待できる“ニュ
ーリーフ”（若葉）であることを示すためにそのように
マークされる。

従って、それは刈り込み（削除）から保護される。以
前の最近の繰り返しにおいて追加されたツリーの他の葉
も保護されることも考察される。

第８（ａ）図に破線で示されるサーチツリーのシンボ
ルは刈り込まれ、その結果、第８（ｂ）図の新しいサー
チツリーと４つの刈り込まれたシンボルのフリーリスト
となる。新しいエントリｂは保存される。確認のため、
サーチツリーの種々のシンボルに対応する実際のシンボ
ルの流れは第８図に示され、第６図の更新処理手続にお
いて付加されたシンボルシーケンスabbが保存される点
から考えると、シンボルの流れbc,ca,abaとabcは削除さ
れる。

刈込み手順は、正式に第９図に示されている。ステッ
プｉにおいて、辞書は、充分で且つ簡潔にする準備が整
っているか否かをチェックされ、もし、整っていればメ
モリのポインターは、列の最初に続く辞書エントリ、即
ちテーブルIIのシンボルｂと第８（ａ）図に従うエント
リ４にセットされる。ステップiiiにおいて、このエン
トリは、そこから延長しているダウンポインターを有し
ているかどうか決められ、第８（ａ）図の場合は、シン
ボルｂがダウンポインター７を有していることがわか
る。従って、このエントリはエンドノードではなく、ア
ルゴリズムはポインターをステップvi（又、どの新たな
フラッグをもクリアにする）において、次のエントリに
進ませ、それによって、ステップviiを介して次のエン
トリに進みシーケンスabaのシンボルａは、エンドンノ
ードとなる。従って、アルゴリズムは、次いで、新たな
エントリフラッグによって、刈込み（削除）手順に対し
て保護されているかどうかをチェックし、そうでないの
で、ステップｖでエントリを抹消し、対応するメモリ位
置をフリーリストに加え、ポインターを再セットする。
前記ポインターの再セット動作は簡単にテーブルIIと第
６図から類推して第８図から推し計ることができる。

この手順は、偶発的に、新たなエントリフラッグによ
って、保護されている以外の“エンドノード”（即ち、
これらから他のシンボルに延長されているダウンポイン
ターＤを有していない）の全てを抹消する結果をもたら
す。このことは、辞書の更新を完了し、アルゴリズム
は、次いで、エンコーデングアルゴリズムの場合に、第
４図のステップviと、デコーデングアルゴリズムの場合
に第５図のステップiiに進むことができる。辞書の更新
と、簡潔にする手順は、エンコーダとデコーダの両者の
サーチツリに同様に行なわれる。この簡潔にする手順は
単一の手順で辞書の全てのメモリ個所をテストするとい
う事実から見ると、簡潔にする手順は、いろいろな方
法、即ちステージ毎の多くのメモリ個所、ステージ毎の
多くのフリーのメモリ個所で決められるステージで行な
われる。

メモリと手順を増やすことで、簡潔にするアルゴリズ
ムのパフォーマンスを改良することのできる追加の手順
として、エンコーダからのコードワード出力は、これら
出力が用いられる周波数のある態様に依存する長さが割
り当てられる。このために、二つの方法が以下のように
述べられ、これは伝達される辞書インデクスを表すコー
ドワードを発生する第４図（iii）に示さにれるエレメ
ントに適応される。

第１の方法は、以下の先行技術文献に記載され公知さ
れている。“ミニマムリダンダンシーコードの構成方
法”ディエーホフマン著、会報IRE40,9,巻1952（A Meth
od for the Construction of Minimum Redundancy,by D
A Huffman,proc IRE Vol 40,9,1952）、“マシマティ
カルセオリーオブコミュニケショーン”シーイーシャノ
ン著、ベルシステムテクニカルジャーナル、27巻、1948
（A Methmatical Theory of Comunication,by C E Shan
non,Bell System Technical Journal,vol 27,1948），
及び“算数コーディングの入門”、ジーランドン著、ア
イビーエムジヤーナルオブリサーチアンドデペロップメ
ント、28,2,巻1984（An Introduction to Arithmetic C
oding" by G hangdon,IBM Journal of Research and De
veropment,Vol,28,2,1984）周波数のカウントは各辞書エントリと関連付けられて
いて、エントリが使用される毎に増加する。この周波数
は、辞書エントリによって表わされた一連の発生の可能
性と先行文献において限定されている手順に従って割り
当てられたコードワードを計算するために用いられる。
一連の可能性に関連するコードワード長hsは、 −log₂（Ps）＜hs＜１−log₂（Ps）で表わされる。

第２の方法は第１の方法より、一般的に効果は少ない
が、手段としては簡単である。

追加のＵポインターは各辞書エントリと関係してい
て、サーチツリーの構成には関係なく辞書のエントリの
LFU（leant frequency used）リストを形成するため
に、使用される。このリストは、一連の周波数順序を、
似た形で決めるために使用される。又、長さインデクス
は各辞書エントリに関連している。

辞書エントリが使用されると、辞書エントリをカレン
トエントリの上に位置させるためにＵポインタを用い、
Ｕポインタと二つのエントリの長さインデクスを交換す
ることによって、LFUリストは、繰り上げられる。この
ようにして、より、しばしば用いられたエントリはLFU
リストの開始点に向って移動される。長さインデクスは
リストの要素の順序と関連付けられ、即ち、最も頻繁に
使用された辞書エントリは、長さエントリ１を有する。
コードは固定または動的ベースに基づいて、及び、長さ
インデクスに基づいて割り当てられたコードワード及
び、低いインデクスを伴う辞書エントリに割り当てられ
ているより短いコードワード上に発生する。この第２の
方法は、同様なリストを挙げているようにEPA127,815の
ミラー及びベグマン（Miller and Wegman）によって述
べられている簡潔アルゴリズムに適応するのが好まし
い。しかしながら、長さインデクスをそれらのデータ構
成に加えることが必要である。広く用いられている辞書
エントリをリンクされたリストにおけるその真上のエン
トリと交換するための、Ｕポインターの使用に代えて、
交互の手順は、リンクされたリストにおけるトップの位
置に、広く用いられている辞書エントリを動かすことで
あり、以前にトップの位置にあるエントリは第２の位置
等に移動される。リンクされたリストは、略、最近使用
されたファンクションを表わしていて、それによって、
ある時刻に使用されなかったエントリはリストの下に押
し下げられ、そして頻繁に使用されたエントリはリスト
のトップの位置に置かれることになる。

追加の手順は、追加の開始時刻を使用することでエン
コーダのパフォーマンスを改良することができるので、
辞書は初めに、例えば′th′，′tha′，′the′，′T
h′，′The′，…を規則正しく、生ずるよう通常、知ら
れている一連の文字を含ませることができる。

追加の手順が行えるものとして、もし辞書が記憶され
るメモリが、通常のケースとして、大記憶装置が存在す
るとき、又はメモリが不揮発性である時に、連続するメ
ッセージの伝達間に情報を保持することができるなら
ば、辞書は前のメッセージをエンコーデングしたり、デ
コーディングしたりする間、記憶された一連のセットを
最初に含ませることができる。例えば、伝達装置は前の
伝達装置と通じた第２の伝達装置と呼ぶことができる。
各々のエンコーダとデコーダの対は、公知の原則に従っ
て、ある単純なチェックサムを発生することによって及
び前記チェックサムを比較することによってそれらの辞
書を比較することができる。

もし、辞書が同等でない場合には、ある知られている
最初の状態に再セットされる。

エンコーダとデコーダとの間のリンクにエラーがある
場合のアルゴリズムの信頼性を向上させるための他の方
法として、デコーダはエラーを示すものである空いてい
る、またはフリーな（自由に使用できる）状態の辞書の
エントリーに対応するコードワードを受信したときエン
コーダのリセットまたはその辞書の再初期化を要求す
る。これらの方法は、オートマティックリピートリクエ
ストのようなエラー検出方法が通常用いられることか
ら、普通には用いられない。他の方法として、エンコー
ダによってチェックサムが周期的に算出され、これがデ
コーダへ送られ、デコーダ側で同様にして算出された値
と比較するようにした方法がある。

第10図は大容量記憶装置、例えばディスク装置１に記
憶された非圧縮データを対応する圧縮データに変換する
ためのデータ処理回路を示す。これによって大容量記憶
装置からメモリを取り出すことができる。マイクロプロ
セッサμＰを有するエンコーダ２がメモリ３と結合さ
れ、このメモリ３には上述のアルゴリズムによるサーチ
ツリーが記憶される。遅延回路４は、新しいシンボルが
大容量記憶装置から受入れられる以前にディクショナリ
ーが必らず更新されるようにするためのものである。

第11図は大容量記憶装置１中の圧縮データを非圧縮デ
ータに変換するためのデコーダ回路を示す。このデコー
ダ回路はメモリ３に接続されたデコーダ５を有し、メモ
リ３中には上述のアルゴリズムによって更新されるサー
チツリーが記憶される。

第12図はターミナル６とこれに関連したインターフェ
ース７とを示す。このインターフェース７は、メモリ３
と遅延装置４とに接続されたエンコーダ２、およびメモ
リ３に接続されたデコーダ５とによって通信リンクとの
間でデータの送受を行なうために設けられている。この
エンコーダとデコーダとに接続されたメモリ３には、上
述のアルゴリズムによってディクショナリーが記憶され
る。図12の回路によって、通信リンクの反対側に接続さ
れた対応する装置（図示せず）との間で通信が可能であ
る。

第13図はメモリ位置の配置を示す。第13図において、
メモリの各行はインデックスによって識別され、シンボ
ル、ダウンまたはディペンデントポインタＤ、右ポイン
タＲおよびペアレントポインタＰを記憶するための各セ
クションを有する。２つのオプションのセクションは所
望に応じて最小の頻度で使用されたポインタ（または周
波数カウント）および長さインデックスのためにメモリ
の右側に示されている。

行０乃至Ｎ−１は基本ソースシンボルセットを含み、
行Ｎ乃至Ｎ＋Ｍ−１はＭ個の制御シンボルを含み、行Ｎ
＋Ｍ以下は使用時に圧縮処理により記憶されたストリン
クを含む。

ソースエンコーダを設計する場合には、エンコーダの
入力がソースアルファベットからの独立したシンボルで
あると仮定することが多い。従ってこのシンボルのサイ
ズは既知である。最近の多くの通信システムでは同期伝
送方式が用いられ、ここではデータは独立した文字とし
てではなく連続したビット列として取り扱われる。

非２進形のシンボルを２進形で出力する同期ソースの
ためのソースエンコーダを設計する場合には、種々の方
法が考えられる。シンボルサイズが一定で未知の場合に
は、最適ソースコード形式が得られる文字長をサーチに
よって見付けることができる。例えば、データのサンプ
ルを取得でき、仮定された文字サイズが１から最大ビッ
ト数へ変換され、各々の場合について情報内容が見積ら
れ、この情報内容と文字サイズとの比が最大の圧縮比を
達成するために設定される。

各シンボルｊの発生の確率Pjが予測され、シーケンス
ｎ当りのビット数はシンボルの情報内容、を増加させるために変更される。

直列エンコーディング法を用いれば他の方法も可能で
ある。この場合、シンボルサイズは自由に選定される。
これは、ソースシンボルの各列はこれらが異なる長さの
ビット列に変換されたときにも、その独自性を失わない
という仮定に基づいている。セグメントサイズ（セグメ
ントは仮定シンボルを示す）を選択するのには多くの考
えるべき点がある。

長さＣのセグメントに対して、セグメントおよびシン
ボルのソースビット列中の位置相互間には同期関係がな
いので、各シンボル列はセグメント中のＣビット位置と
一致する。このことは、いかなるシンボル列に対しても
少なくともＣ種の列変化が可能であり、従って、短かい
セグメントは、ディクショナリー空間のより経済的な使
用を可能とする。

コード化されたバイナリストリング長はセグメントサ
イズに比例するが、コードワード長は既知のストリング
数の対数に比例するので、短いセグメントは長いセグメ
ントよりもディクショナリ空間をより有効に使用できな
い。これは、ジブ・ランペル・アルゴリズム（Ziv−Lam
pel algorithm）に特に関連していて、そのジブ・ラン
ペル・アルゴリズムでは、メモリ空間の大きな部分がシ
ンボルストレージよりもむしろポインターに向けられて
いる。

従って、入力データがキャラクタを表わすバイナリビ
ットのストリームからなり、サーチツリーに蓄積された
シンボルがバイナリビットのシーケンスから構成される
本発明に基づく好ましい実施例では、シーケンス当りの
ビット数はプロセッサによって選択され（プロセッサは
ユーザからの外部コマンド信号に応答してもよい）、入
力データのシンボル当りのビット数は未知か或いはプロ
セッサにより選択されたシーケンス当りのビット数とは
異なっている。

この方法の変形例では、シーケンス当りのビット数は
初期に変化させられ、入力データと出力データ間の結果
として得られる圧縮比は、サーチツリーの蓄積されたシ
ンボルに対するシケンス当りのビット数を選択する前に
モニタされる。

こうして、圧縮比を最大にするためにプロセッサによ
って選択されるシケンス当りのビット数を最適化でき
る。しかしながら、メモリ容量や処理速度のような他の
要因がプロセッサによって選択されるべきシーケンス当
りの最適ビット数に影響を与えるかもしれない。

上述の実施例は、圧縮の効率の点ではわずかに次善で
あるが、メモリの利用や実行速度の点では遥かに効率が
よい削除法を使用している。その実施例は、ディクショ
ナリを作るために使用される２つのデータ構造と、スト
リングを表現するために使用されるシステマティックな
サーチツリー構造と、Sussenguthにより議論されたよう
な、サーチツリーの素子を蓄積するために使用されるデ
ィクショナリのシステマティックな表表現とから形成さ
れている。ところで、サーチツリーの素子が蓄積される
順番は完全にランダムである。この方法は、削除される
べきサーチツリー部分の選択がツリー内の選択された部
分の順序に依存しないという意味から、ランダム削除戦
略に近い。しかし、削除のために候補を選択するアルゴ
リズムがディクショナリの表表現を介するステッピング
を含んでいるので、本当はランダムではない。これはク
ロック（CLOCK）近似に幾らか似ているが、表表現の位
置に基づいてなされる削除のための候補要素の選択が、
サーチツリー内で要素の位置によって評価される点で異
なっている。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献特開昭59−231683（ＪＰ，Ａ) 特開昭60−116228（ＪＰ，Ａ)

Claims

(57)【特許請求の範囲】

【請求項１】インデックスされたメモリ位置を有するメ
モリ（３）が設けられたプロセッサ（μＰ）でデータの
連続するシンボル（a,b,c）を読むステップと、入力データのシンボルストリングからこのストリングを
表わすパスを有するシンボルのサーチツリーの形式で辞
書をメモリに発生させるステップと、入力データのシンボルストリングをサーチツリーに以前
蓄積されたパスと整合させて入力データに対応する圧縮
された出力データを蓄積されたパスから発生するステッ
プとからなり、前記サーチツリーに蓄積されたシンボルは２つの異なる
タイプのリンクしたポインタによって前記パスを形成す
るためにリンクされ、蓄積されたシンボル間の前記２つの異なるタイプのポイ
ンタの第１のタイプのポインタ（Ｒ）は、それら蓄積さ
れたシンボルが入力シンボルシーケンス中の所定の位置
で交換可能なシンボルであることを示すポインタであ
り、蓄積されたシンボル間の第２のタイプのポインタ（Ｄ）
は、それら蓄積されたシンボルの両者が、順番に可能な
入力シンボルシーケンスで発生することを示すポインタ
である入力データの圧縮方法において、前記メモリが一杯のときには、前記サーチツリーの順次
のインデックスされたメモリ位置が他のノードに向いて
いる前記第２のタイプ（Ｄ）のリンクしているポインタ
を有しないサーチツリーのノードを含むか否かについて
テストされ、第２のタイプ（Ｄ）のリンクしているポイ
ンタを有しないサーチツリーのノードを含む場合には削
除され、結果として自由にされたメモリ位置が新しい辞
書のエントリーを可能にすることを特徴とする入力デー
タの圧縮方法。
【請求項２】前記辞書を形成する全てのインデックスメ
モリ位置は記憶されるべく次のシンボルがフリーメモリ
位置に記憶される以前にテストされる請求項１記載の方
法。
【請求項３】前記サーチツリーの最近生成されたノード
は削除部分に保護されることによって限定される請求項
１または２記載の方法。
【請求項４】前記インデックスメモリ位置は、フリーリ
ストにポインタによって連結される前記サーチツリーの
ノードと、削除されるノードにバイパスするためにポイ
ンタをリセットすると共に前記フリーリストにそれらを
接続することによって除去される前記サーチツリーのノ
ードを含まず、それによって前記サーチツリーは全体が
接続されて維持される請求項１乃至３の何れか１項記載
の方法。
【請求項５】前記サーチツリーの各々のノードは関連し
たノードが使用される各々の時間インクリメントされる
それぞれのカウンタに関連されるもので、前記圧縮され
た出力データは最も短いコードワードが頻繁に使用され
るノードを表すような前記カウンタの内容に関連される
長さのコードワードから成る請求項１乃至４の何れか１
項記載の方法。
【請求項６】前記サーチツリーのノードは前記メモリに
順序付けて記憶されるもので、前記ノードが記憶される
順序はノードが使用される後にその序数の値を上げるこ
とによって再配置され、これにより滅多に使用しないノ
ードは低い序数を得て、除去される請求項１乃至４の何
れか１項記載の方法。
【請求項７】前記使用されるノードの序数の値は１上昇
され、前記使用されるノードのすぐ上の前記ノードの序
数の値は１減少され、これにより２つのノードは序数の
値を交換する請求項６記載の方法。
【請求項８】前記使用されるノードの序数の値は最大値
に上昇され、前記使用されるノードの全ての上のノード
の序数の値は１減少される請求項６記載の方法。
【請求項９】前記サーチツリーの各々のノードは関連し
た長さのインデックスを有し、前記圧縮された出力デー
タは前記最も短いコードワードが最も高い序数の値ノー
ドを表すような長さのインデックスに関連される長さの
コードワードから成る請求項６乃至８の何れか１項記載
の方法。
【請求項１０】前記入力データは一連のシンボルの間の
スペースシンボルを含み、前記サーチツリーの新しく記
憶されたパスを発生するプロセスはこのようなスペース
シンボルが検出されるとき終了される請求項１乃至９の
何れか１項記載の方法。
【請求項１１】前記入力データは文字を表している２進
ビット流から成り、前記サーチツリーに記憶される前記
シンボル（Ｓ）は各々一連の２進ビットで構成され、前
記一連のビットの数は前記プロセッサ（μＰ）によって
選択され、前記入力データの文字当りのビットの数は前
記プロセッサによって選択されるシーケンス当りのビッ
トの数とは異なるか、または未知数の何れかである請求
項１乃至10の何れか１項記載の方法。
【請求項１２】前記プロセッサ（μＰ）は使用者から外
部コマンド信号に応答して前記選択を実行するように構
成されている請求項11記載の方法。
【請求項１３】前記シーケンス当りのビット数は最初に
変化され、入力データと出力データとの結果として得ら
れる圧縮比が測定され、前記サーチツリーの記憶された
シンボルに対してシーケンス当りのビット数が前記測定
された圧縮比に基づいて選択される請求項11または12記
載の方法。
【請求項１４】前記サーチツリーの代替記憶シンボルの
順序付けられたリスト（S2,S3,S4）の第１の記憶シンボ
ル及び前記順序付けられたリストの連続的な記憶シンボ
ルに指示する第２のタイプの各連結ポインタ（Ｄ）は、
前記リストに各々連続する記憶シンボルに指示する前記
第１のタイプの連結ポインタ（Ｒ）によって接続される
請求項１または13記載の方法。
【請求項１５】前記第２タイプの各連結ポインタ（Ｄ）
は前記サーチウツリーの代替記憶シンボルのリストの内
の何れか１のシンボルを指示し、前記リストに於ける記
憶シンボルは、一方向を指示する前記第１タイプのポイ
ンタ（Ｒ）によって、及び反対方向を指示する前記第１
タイプのポインタ（Ｌ）によってもまた、互いに接続さ
れ、それにより前記リスト中の何れの記憶シンボルにも
アクセス可能とする請求項１乃至13の何れか１項記載の
方法。
【請求項１６】前記第１タイプの連結ポインタ（Ｒ）は
前記代替記憶シンボルのリストをサーチするために使用
され、それにより最も最近読み込まれた入力シンボルと
のマッチングをとり、マッチングする場合には、もしあ
れば、前記第２タイプのポインタ（Ｄ）を得る請求項14
または15記載の方法。
【請求項１７】入力データが処理される前に、前記入力
データ中に現われそうな一連のシンボルにそれぞれ対応
するシンボル（a,b,c）を記憶したメモリが最初に提供
され、前記最初に提供された記憶シンボルは、前記サー
チツリー中のノードとして記憶さている請求項１乃至16
の何れか１項記載の方法。
【請求項１８】前記辞書は、使用に於いて、関連デコー
ダから受けたコマンド信号に応答して再び初期化される
請求項１乃至17の何れか１項記載の方法。
【請求項１９】使用において、辞書のチェックサムが定
期的に算出され、対応する出力信号が発生される請求項
１乃至17の何れか１項記載の方法。
【請求項２０】前記辞書がさらなる使用のために維持さ
れ、そのようなさらなる使用の何れにも先だって前記辞
書のチェックサム算出を行なうことと、他のそのような
辞書から対応するチェックサムを受け取ることと、それ
らのチェックサムを比較することと、それらのチェック
サムが一致しない場合に前記辞書を再び初期化すること
とを含む請求項１乃至17の何れか１項記載の方法。
【請求項２１】データを圧縮し、この圧縮されたデータ
を大容量記憶媒体（１）に記憶するデータの記憶請求項
１乃至17の何れか１項記載の方法。
【請求項２２】メモリ（３）を有しているプロセッサ
（μＰ）で前記圧縮データの連続キャラクタを読み込
み、前記圧縮データから作られるシンボルのサーチツリ
ーの形をとる辞書を前記メモリに記載し、このサーチツ
リーを利用して前記圧縮データを復号化データに変換す
る過程を含み、前記サーチツリー中の記憶シンボル
（Ｓ）は２つの別個なタイプの連結ポインタによりリン
クされ、記憶シンボル間の第１タイプのポインタ（Ｒ）
は、それらのシンボルが同数のシンボル及び同じ接頭辞
を有するシンボルの異なった復号化ストリングと関連さ
れ且つそのような異なったストリングのそれぞれ最後の
シンボルであるということを示し、記憶シンボル間の第
２タイプのポインタ（Ｄ）は、それらのシンボルが復号
化出力シンボルのストリングに於ける連続シンボルであ
ることを示す圧縮データの復号化方法において、メモリが一杯の時には、前記サーチツリーの一連のイン
デックスされた索引記憶領域は、もしもその索引記憶領
域が他のノードに向いている前記第２のタイプ（Ｄ）の
リンクしているポインタを有しないサーチツリーのノー
ドを含む場合にはテストされ削除され、結果として自由
にされた索引記憶領域は新しい辞書のエントリーが可能
となることを特徴とする請求項１乃至20の何れか１に定
義されたような方法により圧縮されている圧縮データを
復号化する方法。
【請求項２３】前記辞書を形成する全てのインデックス
メモリ位置は、記憶されるべく次のシンボルがフリーメ
モリ位置に記憶される以前にテストされる請求項22に記
載の方法。
【請求項２４】前記サーチツリーの最近生成されたノー
ドは削除部分に保護されることによって限定される請求
項22または23記載の方法。
【請求項２５】前記インデックスメモリ位置は、フリー
リストにポインタによって連結される前記サーチツリー
のノードと、削除されるノードにバイパスするためにポ
インタをリセットすると共に前記フリーリストにそれら
を接続することによって除去される前記サーチツリーの
ノードを含まず、それによって前記サーチツリーは全体
が接続されて維持される請求項22乃至24の何れか１項記
載の方法。
【請求項２６】前記サーチツリーの各々のノードは、関
連したノードが使用される各々の時間インクリメントさ
れるそれぞれのカウンタに関連されるもので、最も短い
コードワードが最も頻繁に使用されるノードに対して割
り当てられ、デコードされるべき圧縮データは、最も短
かいコードワードが対応しているエンコーダサーチツリ
ーの最も頻繁に使用されているノードを表すコードワー
ドによって構成される請求項22乃至25の何れか１項記載
の方法。
【請求項２７】前記サーチツリーのノードは前記メモリ
に順序付けて記憶されるもので、前記ノードが記憶され
る順序はノードが使用される後にその序数の値を上げる
ことによって再配置され、これにより滅多に使用しない
ノードは低い序数を得て、除去される請求項22乃至25記
載の何れか１項記載の方法。
【請求項２８】前記使用されるノードの序数の値は１上
昇され、前記使用されるノードのすぐ上の前記ノードの
序数の値は１減少され、これにより２つのノードは序数
の値を交換する請求項27記載のエンコーダ。
【請求項２９】前記使用されるノードの序数の値は最大
値に上昇され、前記使用されるコードの全ての上のノー
ドの序数の値は１減少される請求項27記載の方法。
【請求項３０】前記サーチツリーの各々のノードは最も
短いコードワードが最も高い序数を有するノードを表す
ような関連した長さのインデックスを有し、前記デコー
ドされるべく圧縮された出力データは前記最も短いコー
ドワードが相当するエンコーダのサーチツリーの最も高
い序数の値ノードを表すような長さのインデックスに関
連される長さのコードワードから成る請求項27乃至29の
何れか１項記載の方法。
【請求項３１】前記サーチツリーの代替記憶シンボルの
順序付けられたリスト（S2,S3,S4）の第１の記憶シンボ
ル及び前記順序付けられたリストの連続的な記憶シンボ
ルに指示する第２のタイプの各連結ポインタ（Ｄ）は、
前記リストに各々連続する記憶シンボルに指示する前記
第１のタイプの連結ポインタ（Ｒ）によって接続される
請求項22記載の方法。
【請求項３２】前記第２タイプの各連結ポインタ（Ｄ）
は前記サーチツリーの代替記憶シンボルのリストの内の
何れか１のシンボルを指示し、前記リストに於ける記憶
シンボルは、一方向を指示する前記第１タイプのポイン
タ（Ｒ）によって、及び反対方向を指示する前記第１タ
イプのポインタ（Ｌ）によってもまた、互いに接続さ
れ、それにより前記リスト中の何れの記憶シンボルにも
アクセス可能とする請求項22記載の方法。
【請求項３３】デコーダは受信された圧縮されたデータ
が空いている、またはフリーなメモリ位置に相当するこ
とを検出して対応する出力信号を発生する過程を有する
請求項22乃至32の何れか１項記載の方法。
【請求項３４】前記辞書がさらなる使用の為に維持さ
れ、そのようなさらなる使用の何れにも先立って前記辞
書のチェックサム算出を行うことと、他のそのような辞
書から対応するチェックサムを受けとることと、それら
のチェックサムを比較することと、それらのチェックサ
ムが一致しない場合に前記辞書を再び初期化することを
含む請求項22乃至32の何れか１項記載の方法。
【請求項３５】請求項１乃至20の何れかに記載されたよ
うな方法によりデータを複号化することと、その結果の
圧縮データを遠隔位置に送信することと、請求項22又は
請求項23に記載されたような対応する方法により前記圧
縮データを復号化することを具備するデータの送信方
法。
【請求項３６】入力データの連続したシンボル（a,b,
c）を受信できるプロセッサ（μＰ）と、インデックス
メモリ位置を持つメモリ（３）と、前記入力データ内の
シンボルのストリングを示すパスを持ったシンボルの検
索ツリーを記憶する手段と、前記入力データ内のシンボ
ルストリングと前記検索ツリー内に先に記憶されたパス
とを突き合わせて、この記憶されたパスから前記入力デ
ータに対応する圧縮された出力データを発生する手段と
を備え、２つの異なる形式のポインタをリンクすること
により前記検索ツリー内に記憶されたシンボル（Ｓ）を
リンクして前記パスを形成するものであって、前記記憶
されたシンボル間の第１タイプ（Ｒ）ポインタは、これ
らの記憶シンボルが入力シンボルシーケンス内の所定位
置に於ける交替可能シンボルであることを示すものであ
り、前記記憶されたシンボル間の第２タイプ（Ｄ）ポイ
ンタは、これらの記憶シンボルともに、可能な入力シン
ボルシーケンス内で順に生じることを示すものであると
きに、使用時において、前記メモリ（３）が満杯であるかどう
かを決定し、前記検索ツリーの連続したインデックスメ
モリ位置をテストし、もしそれが、他のノードを指す前
記第２のタイプ（Ｄ）のリンク−ポインタを持たない前
記検索ツリーのノードを含むならばメモリ位置を削除
し、その結果得られたフリーメモリ位置を新たな辞書登
録に利用できるように、前記プロセッサ（μＰ）を構成
することを特徴とする入力データを圧縮するエンコー
ダ。
【請求項３７】前記辞書を形成する全てのインデックス
メモリ位置は記憶されるべく次のシンボルがフリーメモ
リ位置に記憶される以前にテストされるように、前記プ
ロセッサがさらに配置される請求項36記載の方法。
【請求項３８】前記サーチツリーの最近生成されたノー
ドは削除部分に保護するように前記プロセッサが配置さ
れる請求項36記載のエンコーダ。
【請求項３９】前記プロセッサは、フリーリストにポイ
ンタによって連結される前記サーチツリーのノードと、
削除されるノードにバイパスするようにポインタをリセ
ットすると共に前記フリーリストにそれらを接続するこ
とによって除去される前記サーチツリーのノードを含ま
ない前記インデックスメモリ位置を、ポインタによって
連結するように配置され、それによって前記サーチツリ
ーは全体が接続されて維持される請求項36記載のエンコ
ーダ。
【請求項４０】前記サーチツリーの各々のノードは関連
したノードが使用される各々の時間がインクリメントさ
れるそれぞれのカウンタに関連されるもので、前記プロ
セッサは最も短いコードワードが頻繁に使用されるノー
ドを表すような前記カウンタの内容に関連される長さの
コードワードから構成される圧縮された出力データを供
給するように構成される請求項36記載のエンコーダ。
【請求項４１】前記サーチツリーのノードは前記メモリ
に順序付けて記憶されるもので、ノードが使用される後
に、その序数の値を上げることによってそれらが記憶さ
れる前記順序に再配置され、これにより滅多に使用しな
いノードは低い序数を得て、低い序数を有するノードが
除去されるようにプロセッサを配置する請求項36記載の
エンコーダ。
【請求項４２】前記使用されるノードの序数の値は１上
昇され、前記使用されるノードのすぐ上の前記ノードの
序数の値は１減少され、これにより２つのノードは序数
の値を交換する請求項41記載のエンコーダ。
【請求項４３】前記使用されるノードの序数の値は最大
値に上昇され、前記使用されるノードの全ての上のノー
ドの序数の値は１減少される請求項41記載のエンコー
ダ。
【請求項４４】前記サーチツリーの各々のノードは関連
した長さのインデックスを有し、前記プロセッサは前記
最も短いコードワードが最も高い序数の値ノードを表す
ような長さのインデックスに関連される長さのコードワ
ードから構成している前記圧縮された出力データを形成
するように配置される請求項41乃至44の何れか１項記載
のエンコーダ。
【請求項４５】一連のシンボルの間のスペースシンボル
を含む前記入力データをエンコードし、前記プロセッサ
はこのようなスペースシンボルが検出されるとき前記サ
ーチツリーの新しく記憶されたパスを発生するプロセス
を終了させるように構成されている請求項36乃至44の何
れか１項記載のエンコーダ。
【請求項４６】文字を表している２進ビット流から構成
される入力データをエンコードし、サーチツリーに記憶
されるシンボル（Ｓ）は各々一連の２進ビットで構成さ
れ、入力データの文字当りのビット数が知られていれば
それと異なるようにシーケンス当りのビット数を選択す
るように前記プロセッサが構成されている請求項36乃至
45の何れか１項記載のエンコーダ。
【請求項４７】前記プロセッサ（μＰ）は使用者から外
部コマンド信号に応答して選択を実行するように構成さ
れている請求項46記載のエンコーダ。
【請求項４８】前記プロセッサによって選択される前記
一連のビット番号は最初に変化されるもので、前記入力
データと前記出力データの結果として得られる圧縮比が
測定され、前記サーチツリーの記憶されたシンボルのた
めの一連のビット番号が前記測定された圧縮比の基に選
択される請求項46または47記載のエンコーダ。
【請求項４９】前記サーチツリーの代替記憶シンボルの
順序付けられたリスト（S2,S3,S4）の第１の記憶シンボ
ル及び前記順序付けられたリストの連続的な記憶シンボ
ルに指示する第２のタイプの各連結ポインタ（Ｄ）は、
前記リストに各々連続する記憶シンボルに指示する前記
第１のタイプの連結ポインタ（Ｒ）によって接続される
請求項36乃至48の何れか１項記載のエンコーダ。
【請求項５０】前記第２タイプの各連結ポインタ（Ｄ）
は前記サーチツリーの代替記憶シンボルのリストの内の
何れか１のシンボルを指示し、前記リストに於ける記憶
シンボルは、一方向を指示する前記第１タイプのポイン
タ（Ｒ）によって、及び反対方向を指示する前記第１タ
イプのポインタ（Ｌ）によってもまた、互いに接続さ
れ、それにより前記リスト中の何れの記憶シンボルにも
アクセス可能とする請求項36乃至48記載の何れか１項記
載のエンコーダ。
【請求項５１】前記プロセッサは、使用に於いて、関連
デコーダから受けたコマンド信号に応答して前記辞書を
再び初期化する請求項36乃至50記載の何れか１項記載の
エンコーダ。
【請求項５２】前記プロセッサは、使用に於いて、前記
辞書のチェックサムを定期的に算出し、対応する出力信
号を発生する請求項36乃至50の何れか１項記載のエンコ
ーダ。
【請求項５３】前記辞書がさらなる使用のために維持さ
れ、そのようなさらなる使用の何れにも先だって前記辞
書のチェックサム算出を行ない、対応する出力信号を生
成するように、このチェックサムと使用に於いて関連デ
コーダから受けた対応するチェックサムを比較すること
と、それらのチェックサムが一致しない場合に前記辞書
を再び初期化状態にするように、前記プロセッサは配置
される請求項36乃至50何れか１項記載のエンコーダ。
【請求項５４】圧縮データの連続したシンボルを受信出
来るプロセッサ（μＰ）と、インデックスメモリ位置を
持つメモリ（３）と、シンボルの検索ツリーの形をとる
辞書を前記メモリに記憶する手段から構成され、前記圧
縮データから前記サーチツリーを構築し、このサーチツ
リーを利用して前記圧縮データを複号化データに変換す
るように前記プロセッサが構成され、前記サーチツリー
中の記憶シンボル（Ｓ）は２つの別個なタイプの連結ポ
インタによりリンクされ、記憶シンボル間の第１タイプ
のポインタ（Ｒ）は、それらのシンボルが同数のシンボ
ルを有するシンボルの異なった復号化ストリングと関連
され且つそのような異なったストリングのそれぞれ最後
のシンボルであるということを示し、記憶シンボル間の
第２タイプのポインタ（Ｄ）は、それらのシンボルが復
号化出力シンボルのストリングに於ける連続シンボルで
あるということを示す圧縮データの復号化方法に於い
て、使用時において、前記メモリ（３）が満杯であるか
どうかを決定し、前記検索ツリーの連続したインデック
スメモリ位置をテストし、もしそれが、他のノードを指
す前記第２のタイプ（Ｄ）のリンク−ポインタを持たな
い前記検索ツリーのノードを含むならばメモリ位置を削
除し、その結果得られたフリーメモリ位置を新たな辞書
登録に利用できるように、前記プロセッサ（μＰ）を構
成することを特徴とする圧縮データを復号化するデコー
ダ。
【請求項５５】使用において、前記サーチツリーの代替
記憶シンボルの順序付けられたリスト（S2,S3,S4）の第
１の記憶シンボル及び前記順序付けられたリストの連続
的な記憶シンボルに指示する第２のタイプの各連結ポイ
ンタ（Ｄ）は、前記リストに各々連続する記憶シンボル
に指示する前記第１のタイプの連結ポインタ（Ｒ）によ
って接続される請求項54記載のデコーダ。
【請求項５６】前記第２タイプの各連結ポインタ（Ｄ）
は前記サーチツリーの代替記憶シンボルのリストの内の
何れか１のシンボルを指示し、前記リストに於ける記憶
シンボルは、一方向を指示する前記第１タイプのポイン
タ（Ｒ）によって、及び反対方向を指示する前記第１タ
イプのポインタ（Ｌ）によってもまた、互いに接続さ
れ、それにより前記リストの何れの記憶シンボルにもア
クセス可能とする請求項54記載のデコーダ。
【請求項５７】さらに、前記辞書を形成する全てのイン
デックスメモリ位置は記憶されるべく次のシンボルがフ
リーメモリ位置に記憶される以前にテストされるように
前記プロセッサが構成される請求項54乃至56何れか１項
記載のデコーダ。
【請求項５８】前記サーチツリーの最近生成されたノー
ドは削除部分に保護するように前記プロセッサが配置さ
れる請求項54乃至56記載の何れか１項記載のデコーダ。
【請求項５９】前記プロセッサが、フリーリストにポイ
ンタによって連結される前記サーチツリーのノードと、
削除されるノードにバイパスするためにポインタをリセ
ットすると共に前記フリーリストにそれらを接続するこ
とによって除去される前記サーチツリーのノードを含ま
ない前記インデックスメモリ位置をポインタによって連
結するように配置され、それによって前記サーチツリー
は全体が接続されて維持される請求項54乃至58の何れか
１項記載のデコーダ。
【請求項６０】前記サーチツリーの各々のノードは関連
したノードが使用される各々の時間インクリメントされ
るそれぞれのカウンタに関連されるもので、前記圧縮さ
れた出力データは最も短いコードワードが頻繁に使用さ
れるノードを表すような前記カウンタの内容に関連され
る長さのコードワードから構成される請求項54乃至59の
何れか１項記載のデコーダ。
【請求項６１】前記サーチツリーのノードは前記メモリ
に順序付けて記憶されるもので、ノードが使用される後
に、その序数の値を上げることによって再配置され、こ
れにより滅多に使用しないノードは低い序数を得て、最
も低い序数を有するノードが除去されるようにプロセッ
サを配置する請求項54乃至59の何れか１項記載のデコー
ダ。
【請求項６２】前記使用されるノードの序数の値は１上
昇され、前記使用されるノードのすぐ上の前記ノードの
序数の値は１減少され、これにより２つのノードは序数
の値を交換する請求項61記載のデコーダ。
【請求項６３】前記使用されるノードの序数の値は最大
値に上昇され、前記使用されるノードの全ての上のノー
ドの序数の値は１減少される請求項61記載のデコーダ。
【請求項６４】前記サーチツリーの各々のノードは関連
した長さのインデックスを有し、前記プロセッサは前記
最も短いコードワードが最も高い序数の値ノードを表す
ような長さのインデックスに関連される長さのコードワ
ードから構成している前記圧縮された出力データを形成
するように配置される請求項61乃至63何れか１項記載の
デコーダ。
【請求項６５】使用時において、前記プロセッサは、受
信した圧縮データが空いている、またはフリーメなモリ
位置に対応することを検出したとき関連するエンコーダ
に伝送するための対応する出力信号を発生するように構
成されている請求項54乃至64何れか１項記載のデコー
ダ。
【請求項６６】前記辞書がさらに使用すべく維持され、
かつ、前記プロセッサが使用に先だって前記辞書に関し
てチェックサム計算を実行して関連するエンコーダに伝
送すべく関連する出力信号を発生し、このチェックサム
を使用時に前記エンコーダから受信した関連するチェッ
クサムと比較してチェックサムが一致しなかったときは
前記辞書を初期化すべく構成されている請求項54乃至65
何れか１項記載のデコーダ。
【請求項６７】請求項36乃至53の何れかに規定されたエ
ンコーダ（２）と、請求項54乃至66の何れかに規定され
た関連するデコーダ（５）と、前記エンコーダと前記デ
コーダとの間に圧縮データを伝送するデータリンクとを
具備するデータ処理装置。
【請求項６８】請求項36乃至50の何れかに規定されたエ
ンコーダ（２）と、請求項54乃至57の何れかに規定され
た関連するデコーダ（５）と、前記エンコーダとデコー
ダによってアクセス可能な大容量記憶媒体（１）とを具
備するデータ処理装置。