JP3224813B2 - 圧縮データ・アクセス - Google Patents

Description

【発明の詳細な説明】 本発明は、圧縮データへのアクセスを改善するやり方
で、テープへの記憶のため、ユーザ・データを圧縮する
方法に関する。

ホストからデータが到達したとき、それをテープに書
き込む前に圧縮してテープ記憶容量を増大させるため
に、データ圧縮能力を有するテープ・ドライブ（DCドラ
イブ）を備えることが知られている。DCドライブは、テ
ープから圧縮データを読み取り、ホストに送る前にデー
タを復元する（decompress）こともできる。ホストは、
また、ユーザ・データのソフトウェア圧縮および／また
は復元をすることもできる。

２つ以上のタイプのデータ圧縮がある。例えば、指定
レコード、ファイルなどの分離マークをデータストリー
ムから除去して、該マークの位置に関する情報をインデ
ックスに記憶することにより、ユーザ・データを効率的
に圧縮する。別の全く異なるアプローチでは、データの
冗長性を除去することにより、例えば、ユーザ・データ
・ワードを、元のデータを回復することのできるコード
・ワードまたは記号と置き換えることにより、ユーザ・
データを圧縮する。用語“データ圧縮”または略号DCを
用いるとき、本書で言及されるのは後者のタイプであ
る。

データを圧縮するための幾つかの異なるアルゴリズム
が知られている。あるアプローチでは、データを圧縮す
るときに動的に作成される辞書（dictionary）を用い
て、ユーザ・データをコード・ワードに変換する。辞書
は、復元中に、再び動的に、再生成される。このアプロ
ーチを用いるアルゴリズムは、LEMPEL ZIV WELCHアル
ゴリズムまたはLZWアルゴリズムである。

データ圧縮中、LZWアルゴリズムに従って動作するDC
ドライブは、新しい辞書がいつスタートされるか（RESE
Tコード・ワード）、およびデータがいつフラッシュさ
れるか、すなわち、バッファに保持された、圧縮を待つ
小量のデータが、それ以上の入力データが該バッファに
送られる前にいつ送られるか（FLUSHコード・ワード）
を示すコード・ワードをデータストリームに挿入する。

LZWアルゴリズムを用いて、テープ上の圧縮データの
一部の復元を達成するため、関連辞書を再生成すること
ができるようにするのにRESETコード・ワードから復元
を開始することが必要である。一般に、新しい辞書を、
データの便宜的なポイント、例えばレコードのはじめに
おいてスタートすることができるように、新しい辞書を
始める前にFLUSH操作が行われる。

データ圧縮の別のアプローチでは、選択された量の最
新非圧縮データストリーム（‘ヒストリ・バッファ’ま
たは‘スライディング・ウインドウ’または‘スライデ
ィング辞書’と呼ばれる）を参照し、ヒストリ・バッフ
ァに現れる入力データストリームの項目を、ヒストリ・
バッファの中のどこに位置するかを示すコード・ワード
／トークンと置き換える。このアプローチは、第一Lemp
el ZivアルゴリズムまたはLZ1として知られている。復
元中に、ヒストリ・バッファも参照され、コード・ワー
ド／トークンに遭通すると、ヒストリ・バッファからの
関連ストリングが置き換えられて、元のデータストリー
ムが再構成される。

このアプローチでは、RESETコマンドにはストリ・バ
ッファをクリアする作用があり、FLUSHコマンドにはル
ックアヘッド・バッファをクリアする作用がある。

したがって、フラッシュ操作は一般に、比較的わずか
な生データを通したり、またはデータストリームの便宜
的なポイントにおいてデータ圧縮を再開する前に、圧縮
を待っているデータにおいて圧縮操作を完了させるもの
と考えることができる。これは、ソフトウェアまたはハ
ードウェアにより圧縮が行われる場合でも適用される。

本発明に依れば、下記のステップを備えた、ユーザ・
データをテープ上に記憶するための圧縮方法が提供され
る：すなわち、 複数のレコードに構成されたユーザ・データ・ワード
のストリームを受信するためのステップと； 該データから得られる辞書を用いて、ユーザ・データ
の少なくとも一部をコード・ワードに変換することを含
む圧縮アルゴリズムに従って前記ユーザ・データを圧縮
するステップと； を備え、開始連続辞書間で複数のフラッシュ動作を実行
することにより特徴づけられる。

本書では、用語‘コード・ワード’は、LZWアルゴリ
ズムとともに広く用いられる。一般に、この用語は、い
ずれかの記号またはトークン、またはデータ圧縮中にユ
ーザ・データの一部を置き換えるために用いる他の表記
を扱うために意図されている。用語‘辞書’は、バイト
・ストリングの集まりおよび圧縮データを非圧縮データ
に変換する際に用いるための対応するコード・ワードを
扱うように意図されている。すでに述べたデータ圧縮ア
ルゴリズムのいずれにおいても、辞書は、データ圧縮中
に生成され、圧縮データ自体に含まれている。

本発明の利点は、辞書を作るために用いる量よりも少
ないデータのセグメントを、その圧縮された形式のテー
プから選択的に回復することができることである。言い
換えれば、辞書内のFLUSHコード・ワードは、コンパイ
ルするために用いたり、または該辞書を用いるところ
の、データのセグメント間に“クリーン・ブレーク（cl
ean break）”をもたらすことである。たとえば、FLUS
Hコード・ワードは、各レコードの終わりにおいてデー
タストリームに挿入することができる。

該方法は、ユーザ・データと区別することができるよ
うな方法で、フラッシュ動作が起きた位置の表示を、テ
ータ上に記憶することを含むことが望ましい。

この特徴を実施する１つの方法は、各レコードに関す
る圧縮バイト・カウント（CBC）、または１対のFLUSH動
作間で定義される他のデータ・セグメントを記憶するこ
とである。

該方法は、ユーザ・データと区別することができるよ
うな方法で、新しい辞書の始めの位置の表示を、テープ
に記憶することを含むことが望ましい。

この特徴を実施する１つの方法は、各新しい辞書の始
めに用いられる特定圧縮アルゴリズムについての情報を
テープに記憶することである。

説明するある実施例では、該方法は、ユーザ・データ
のレコード構造とは無関係に、圧縮ユーザ・データを複
数のグループとしてテープに書き込み、各グループの始
めまたはその近くで新しい辞書を始めることを含む。該
方法は、各グループの最初の新しいレコードの始めにお
いて新しい辞書を始めることを含むことが望ましい。

この特徴は、データ・グループの間のリンケージを減
らすことによりデバイス・コントローラで要求されるバ
ッファ・スペースの量を減少させる一助になること、す
なわち２つ以上のデータ・グループをバッファに記憶す
るために必要とする可能性を少なくするという点であ
る。さらに、該グループのデータ・セグメントを復元す
るために、特定グループの外側を見る必要のないことも
利点である。

説明する別の実施例では、方法は、ユーザ・データ・
レコードを、１つのエンティティが１つ以上のレコード
を含む複数のエンティティに組織し、各エンティティの
終わりでフラッシュ動作を実行することを備えている。

この特徴により、１つのエンティティ毎にデータを選
択的に復元することができる。

さらに、この方法は、すでに述べた理由により、各グ
ループの最初の新しいエンティティの始めにおいて新し
い辞書を始めることを含むことができる。

本発明は、さらに前に定義したような方法に従って動
作する、ユーザ・データを圧縮したり、圧縮ユーザ・デ
ータをテープに記憶するための記憶装置を提供する。

本発明の特定の実施例を、添付の図面を参照して、一
例としてここに記述する。

第Ａ図及び第Ｂ図は、LZWデータ圧縮アルゴリズムに
関する図である。

第Ｃ図はLZ1アルゴリズムに従って使用されるバッフ
ァの図式的表現図である。

第Ｄ図はRINTINTINがLZ1アルゴリズムに従ってどのよ
うに圧縮されるかを示す図表である。

第１図はコンピュータ・データを記憶する構成を示す
複部分図であって、 （ａ）はユーザ（ホスト）によってデータ記憶装置に
送られる論理的分離マーク及びデータ・レコードのシー
ケンスを表す図である。

（ｂ）及び（ｃ）は、第１図（ａ）のシーケンスをテ
ープ上に記憶する２つの異なる構成を示す図である。

第２図はグループ・インデックスの図である。

第３図及び第3A図は、一般のブロック・アクセス・テ
ーブル図である。

第４図及び第4A図は特定のブロック・アクセス・テー
ブル図である。

第５図乃至第７図はコンピュータ・データを記憶する
さらなる構成図である。

第８図はグループのブロック・アクセス・テーブルに
関する可能な有効エントリ（entry）を示す図である。

第９図及び第10図は、コンピュータ・データを記憶す
る構成のさらなる図である。

第11図は、ヘリカル走査を用い、本発明を具現化する
データ記憶装置の部分を形成するテープ・デッキの主な
物理的コンポーネントを示す図である。

第12図はヘリカル走査を使ってテープ上に記録された
２つのデータ・トラックの図式的表現図である。

第13図は本データ記憶方法に従って記録されたデータ
・トラックの主なデータ領域のフォーマットの図式的表
現図である。

第14図は本発明のデータ記憶方法に従って記録された
データ・トラックのサブ・データ領域のフォーマットの
図式的表現図である。

第15図は、本方法、すなわちデータ領域内のグループ
におけるデータ・フレームの構成及び各グループのフレ
ームに記録されたインデックスの詳細の両方を示す図で
ある。

第16図は本発明を具現化するデータ記憶装置の主なコ
ンポーネントのブロック図である。

第17図及び第18図はデータ圧縮プロセッサに関するブ
ロック図である。

第19図はデータ記憶装置のグループ・プロセッサの、
より詳細な機能ブロック図である。

第20A図及び第20B図は、テープ上の特定のレコードに
関する探索において、ドライブ装置により実施されるア
ルゴリズムの流れ図である。

特定のDCアルゴリズムの詳細を含むデータ圧縮に関す
るさらなる情報がまず与えられる。

データ圧縮プロセスの目的は、データから冗長性を除
去することにある。圧縮効率の測度の１つは、“圧縮
比”と呼ばれ、 復元される入力の長さ／圧縮される入力の長さ として定義される。

これは、データ圧縮プロセスの達成測度である。圧縮
比が大きくなれば、圧縮効率もそれだけ高くなる。

データ圧縮を実施する方法の１つでは、入力文字のパ
ターンを認識して、コード化する、すなわち、置換方法
が用いられる。

LZWアルゴリズムによれば、独特なストリングをなす
入力文字が見つかると、それらは辞書に入力され、数値
が割り当てられる。辞書は、データの圧縮時に、動的に
形成され、復元時に、データから再生される。一旦、辞
書エントリが存在すると、データ・ストリーム内にその
後に発生する該エントリは、数値またはコード・ワード
に置き換えることができる。留意すべきは、このアルゴ
リズムは、ASCIIテキスト・データの圧縮に制限される
ものではないという点である。その原理は、２進ファイ
ル・データ・ベース、イメージング・データ等にも等し
く当てはまる。

各辞書エントリは、２つの項目、すなわち、（１）ア
ルゴリズムがデータ内で見つけた独特なストリングをな
すデータ・バイトと、（２）このバイトの組合せを表わ
したコード・ワードから構成される。辞書には、4096ま
でのエントリを納めることができる。第１の８つのエン
トリは、特定の条件のフラグを立て、その制御を行なう
ために用いられる予約コード・ワードである。次の256
のエントリには、０〜255のバイト値が含まれている。
従って、これら256の項目のいくつかは、ASCIIテキスト
文字に関するコード・ワードである。残りの位置は、他
の辞書位置を指示し、結局は、バイト値０〜255の１つ
を指示することによって終了する連係リスト・エントリ
である。この連係リスト・データを用いることによっ
て、可能性のあるバイトの組合せは、２バイト〜128バ
イトの長さの範囲内になるので、その記憶に過剰に広い
メモリ・アレイを用いなくてもすむようにすることがで
きる。

さらに詳細に後述するハードウェアの実施案の場合、
辞書は、構築してから、23ビット幅のランダム・アクセ
ス・メモリ（RAM）のバンクに記憶される。各メモリ・
アドレスには、下位８ビットによるバイト値、次の12ビ
ットによるエントリを表わすコード・ワードまたはポイ
ンタ、及び、上位３ビットによる３つの条件フラグを含
むことができる。コード・ワードを表わすのに用いられ
る出力バイト・ストリームにおけるビット数は、９ビッ
ト〜12ビットの範囲であり、０〜4095の範囲の辞書エン
トリに対応する。辞書構築段階において、辞書に512の
エントリが作成されるまで、各コード・ワード毎に、９
ビットが用いられ、512番目のエントリの後は、コード
・ワードに10ビットが用いられ、1024番目のエントリの
後は、コード・ワードに11ビットが用いられ、最後の20
48エントリについては、コード・ワードに12ビットが用
いられる。辞書が満杯になると、それ以上のエントリ
は、作成されず、後続の全てのコード・ワードは、長さ
が12ビットになる。任意の辞書エントリに関するメモリ
・アドレスは、エントリ値に対して複雑な操作を施すこ
とによって決定される。辞書には、4096のエントリを納
めることができるので、辞書全体の支援には、4Kバイト
のRAMしか必要ないように思われる。これは、実際、復
元時にあてはまることである。しかし、圧縮時には、辞
書の構築段階において生じる辞書の“衝突”のため、4K
バイトを超えるRAMが必要になる。これは、２つの異な
るストリング／文字の組合せが、辞書RAM内における同
じ場所にマッピングが施される場合があり、辞書RAMに
おける資源は有限であることと、圧縮時における辞書構
築のプロセスが複雑であるためである。辞書の衝突が生
じると、２つの衝突値が、２つの新しい位置について再
計算され、もとの位置に衝突位置のフラグが立てられ
る。

アルゴリズムの重要な特性は、圧縮と復元との結合で
ある。これら２つの動作は、圧縮及び復元プロセス時
と、バイト・ストリームに対するコード・ワードのパッ
キング及びアンパッキング時の両方において結びつけら
れる。圧縮アルゴリズムの特性により、圧縮プロセスと
復元プロセスを同期させることが必要になる。別の言い
方をすると、復元は、圧縮データの任意のポイントから
開始させることはできない。復元は、辞書が空またはリ
セットされていることが分っているポイントから開始す
る。この結合によって、アルゴリズムの基本的な利点の
１つが得られる。すなわち、辞書は、コード・ワードに
組み込まれているので、圧縮データと共に転送する必要
はない。同様に、パッキングとアンパッキングのプロセ
スも同期させなければならない。復元ハードウェアに対
して圧縮データを適正な順序で提示しなければならない
点に留意のこと。

第Ａ図は、上述の圧縮アルゴリズムに関する略グラフ
ィック図である。この例には、次の文字から成る入力デ
ータ・ストリームが示されている:RINTINTIN。圧縮プロ
セスの流れをたどるには、第Ａ図を上から下へ検分し、
左から始めて右へ進めるのが望ましい。辞書は、リセッ
トされ、８つの予約コード・ワード、及び、全てのASCI
I文字に関するコード・ワードを含む０〜255の第１の25
6エントリを納めるように初期設定されているものと仮
定する。

圧縮アルゴリズムは、データ・ストリーム内の各バイ
ト毎に下記のプロセスを実行する： 1.入力バイトを取る。

2.現在の入力シーケンスに関して辞書の探索を行ない、
一致すれば、別の入力バイトを取り、現在のシーケンス
に加え、一致した最大のシーケンスを記憶しておく。

3.一致するものがなくなるまで、ステップ２を繰り返
す。

4.現在の“不一致”シーケンスの新辞書エントリを作成
する。

5.一致した最大シーケンスに関するコード・ワードを出
力する。

この例では、圧縮アルゴリズムは、圧縮エンジンが最
初のＲを受け取った後、開始する。入力文字Ｒは、その
初期設定時に納められた文字Ｒに一致する。一致したの
で、DCエンジンは、別のバイトを受け取るが、これは文
字Ｉである。次に、シーケンスRIを求めて辞書の探索を
行なうが、一致するものは見あたらない。従って、新し
い辞書エントリはRIが作成され、最大の一致シーケンス
に関するコード・ワード（すなわち、文字Ｒに関するコ
ード・ワード）が、出力される。次に、DCエンジンは、
Ｉを求めて辞書を探索し、Ｒの場合とちょうど同じよう
に、一致を見つけ出す。もう１つの文字が入力され
（Ｎ）、シーケンスINに関して探索を開始する。INは、
どのエントリとも一致しないので、新しいエントリが作
成され、最大の一致シーケンスに関するコード・ワード
（すなわち、文字Ｉに関するコード・ワード）が、出力
される。このプロセスは、続行され、文字Ｎの探索が行
なわれる。Ｎが見つかると、次の文字が入力され、NTを
求めて辞書の探索が行なわれる。これは見つからないの
で、NTに関する辞書エントリが作成され、Ｎに関するコ
ード・ワードが出力される。同じシーケンスが、文字Ｔ
及びＩについても生じる。Ｔに関するコード・ワードが
出力され、TIに関する辞書エントリが作成される。

この時点まで、複数文字の一致がなかったので、圧縮
は行なわれなかった。実際、４つの８ビット文字が４つ
の９ビット・コード・ワードに置き換えられたというこ
とであって、出力ストリームは、わずかに拡張されただ
けである。（これは、32ビット対36ビットの拡張、すな
わち、1.125:1の圧縮比を表わしている。）しかし、次
の文字が入力されると、データ圧縮が開始する。この時
点で、DCエンジンは、INシーケンスの探索を行なう。一
致を見つけると、DCエンジンは、別の文字を受け取り、
INあの探索を開始する。一致が見つからなれければ、IN
Tに関する辞書エントリを作成し、シーケンスINに関し
てあらかじめ生成されたコード・ワードを出力する。こ
の場合、２つの８ビット文字が１つの９ビット・コード
・ワードに置き換えられ、圧縮比は16/9すなわち1.778:
1になっている。

このプロセスが、続行され、再び、２つの文字が単一
のコード・ワードに置き換えられる。DCエンジンは、前
のシーケンスからのＴで開始され、続いて、次の文字Ｉ
を受け取る。DCエンジンは、TIシーケンスを探索し、一
致するので、別のバイトが、入力される。次に、該チッ
プは、TINシーケンスの探索を行なう。一致するものが
ないので、TINエントリが作成され、TIに関するコード
・ワードが出力される。このシーケンスも、INシーケン
スが示した1.778:1の圧縮比を示す。この９バイトから
なるストリングに関する正味の圧縮比は、1.143:1であ
る。この例は、極めて少数のバイトからなるため、これ
は、特に大きい圧縮比ではない。データのサンプルが増
えると、記憶されるデータのシーケンスも増し、単一の
コード・ワードによって置き換えられるバイトのシーケ
ンスも増す。1:1〜110:1の範囲の圧縮比を得ることが可
能になる。

第Ｂ図には、復元プロセスの略図が示されている。こ
の例では、入力として前の圧縮例の出力が用いられる。
復元プロセスは、圧縮プロセスに極めてよく似ている
が、所定の辞書エントリの存在を探索する必要がないの
で、復元に関するアルゴリズムは、圧縮に関するアルゴ
リズムほど複雑ではない。２つのプロセスを結合するこ
とによって、復元時における適合する辞書エントリの存
在が保証される。該アルゴリズムは、入力コード・ワー
ドを利用して、辞書内のバイト・シーケンスを参照し、
次に、圧縮アルゴリズムと同じ規則を利用して、新しい
エントリを作成するだけである。このようにして、復元
アルゴリズムでは、データ・パケットとともに特別辞書
を送ることなく、圧縮データを回復することができる。

圧縮例の場合のように、辞書はリセットされ、０〜25
5の最初の256エントリを納めるように初期設定されてい
るものと仮定する。復元エンジンは、Ｒに関するコード
・ワードを受け取ることから開始する。復元エンジン
は、このコード・ワードを利用して、バイト値Ｒを参照
する。この値は、後入れ先出し（LIFO）スタックに納め
られ、チップから出力されるのを待つ。Ｒは、根コード
・ワード（最初の256エントリの１つ）であるため、こ
のコード・ワードについて、リストの終端に達したこと
になる。次に、チップから出力スタックがダンプされ
る。復元エンジンは、さらに、Ｉに関するコード・ワー
ドを入力し、それを利用して、バイト値Ｉを参照する。
やはり、この値は、根コード・ワードであるため、この
コード・ワードに関する出力シーケンスが、完了し、Ｉ
に関するバイト値が、出力スタックからポップされる。
この時点で、出力スタック（Ｉ）にプッシュされた最後
のバイト値と、前のコード・ワード（Ｒに関するコード
・ワード）を利用して、新しい辞書エントリが作成され
る。各エントリは、こうして作成され、１つのバイト値
と、シーケンスをなす次のバイト（前のコード・ワー
ド）に対するポインタを含んでいる。こうして、各辞書
エントリ毎に、連係リストが生成される。

次のコード・ワードが入力されて（Ｎに関するコード
・ワード）、該プロセスが反復される。今度は、Ｎが出
力され、バイト値Ｎと、Ｉに関するコード・ワードを含
む新しい辞書エントリが、作成される。Ｔに関するコー
ド・ワードが入力されると、Ｔが出力され、別の辞書エ
ントリが作成される。入力される次のコード・ワード
は、バイト・シーケンスINを表わす。復元エンジンは、
このコード・ワードを利用して、本例において前に生成
された第２の辞書エントリを参照する。このエントリに
は、出力スタックに納められたバイト値Ｎと、現在のコ
ード・ワードになるＩに関するコード・ワードに対する
ポインタが含まれている。この新しいコード・ワード
は、出力スタックに納められる次のバイト（Ｉ）を見つ
けるために用いられる。これは、根コード・ワードであ
るので、参照プロセスは、完了し、出力スタックが、逆
の順序でダンプされる。すなわち、まずＩが出力され、
これにＮが続くことになる。次の２つのコード・ワード
に関して、同じプロセスが反復され、もとのバイト・シ
ーケンスRINTINTINが回復することになる。

データ圧縮中にデータストリームに書き込まれる上述
した予約コード・ワードのうちの２つは、RESETおよびF
LUSH条件に関するコード・ワードである。RESETコード
・ワードは、新辞書の開始を意味する。FLUSHコード・
ワードは、DCチップがそのバッファをフラッシュ・アウ
トしたこと、すなわち連続データでバッファを再び一杯
にする前に、バッファに現在保持されているデータ（現
在の最長の一致を表す）に関するコード・ワードを出力
することを意味する。DCチップは、RESETおよびFLUSHコ
ード・ワードを、アルゴリズム従属方式でデータストリ
ームに書き込む。しかし、圧縮データへのアクセスを改
善するために、RESETおよびFLUSHコード・ワードのうち
のある１つを利用することができるように、テープ・フ
ォーマットは、特定RESETおよびFLUSHコード・ワードを
用いなければならないときに関する制約を課し、特定情
報の書込みも確実にする。

LZWアルゴリズム・プロセッサによるコード・ワード
出力は、各々８または16ビット以外にすることができる
ので、“パッカー”は普通、システムに含まれ、コード
・ワードを受け入れ、パックされたコード・ワードのバ
イトを出力する。このパッキング・プロセスは、その出
力からの部分的バイトを必然的に制止して、圧縮アルゴ
リズムにより次のコード・ワードが生成されるのを待
つ。この部分的コードワードは、圧縮システムに取り込
まれているが、その出力にまだ反映されていない追加デ
ータを表す。

あるポイントでは、圧縮エンジンを実施するシステム
で、圧縮装置に入るすべてのバイトをその出力で表すこ
とが要求される。これは、見つけたなかで現在の一致が
最長のものであること、したがってその現在の突合せコ
ード・ワードを出力すべきことを圧縮装置に知らせなけ
ればならないということを意味する。これは、いずれか
の部分的コード・ワードが圧縮システムからの出力であ
ることも意味している。これは、受信したすべてのバイ
トがその出力で表されるときに、圧縮装置が“フラッシ
ュ”されるFLUSH動作である。これは、その出力からの
データは制止しない。

辞書は、データから再構築しなければならないので、
復元は、コード・ワードRESETからしか開始されること
ができない。一方、復元の停止は、それが、特定の辞書
の終端でなかったとしても、後続の任意のFLUSHコード
・ワードで行なうことができる。これが、各レコードの
終りにコード・ワードFLUSHを配置し、辞書の構築に用
いられるものより小さいデータ・セグメントの選択的復
元を可能にすることが有利な理由である。

復元システムは、コード・ワードを復元装置に与える
アンパッキング・セクションを含む。復元装置には最長
一致を見つけるタスクがなく、したがって固有のバッフ
ァリングを伴わないが、アンパッカーは一度に１バイト
のデータを外界から取り込むことができるので、一般に
復元装置からの部分的コード・ワードを制止する。

圧縮中に“フラッシュ”状態の前の最終コード・ワー
ドが復元装置に与えられたならば、アンパッカーは残さ
れたビットを放棄しなければならない。これらのビット
は、次のコード・ワードの一部ではなく、むしろ圧縮中
にフラッシュ動作により導入されるパディングである。
したがって、アンパッカーは、圧縮中にどこでフラッシ
ュが起こったかを知らなければならない。

ほとんどのデータは、それまで参照されることがない
ので、辞書の開始時に、データの大部分は、圧縮せずに
排出される。この段階では、圧縮比は比較的小さい。従
って、圧縮効率を低下させるほど頻繁に辞書の再開を繰
り返すのは望ましくない。

現行辞書が一杯であるにもかかわらず圧縮比が高い場
合には、辞書をその静的状態に保つことができる。すな
わち、圧縮比が下がり、新辞書を開始することがより効
率的になるまで、エントリを１つも追加することはでき
ない。

LZ1アルゴリズムに従う際の基本的な考えは、テキス
トの共通ストリングを特別記号と置き換えることであ
る。この記号は、ストリングがより早くに伝送または記
憶されたこと、および復元装置が特別記号の代りに前の
発生を用いることのみ必要であることを知らせる。さら
にはっきり述べると、圧縮装置の出力は、サイテーショ
ン（citation）と呼ばれるストリングの前の出現の参照
と、イノベーションと呼ばれる非圧縮文字の参照とを交
互にすることにより得られる。イノベーションは、圧縮
出力では明らかに変化しない文字であり、復元装置で、
新しい、前に見えなかった文字の使用を認識することが
できるようにするため、備えられている。

アルゴリズムは、バッファ（‘ウインドウ’として知
られている）を必要とし、２つの部分に分けられる。大
部分のバッファには入力の過去のヒストリが含まれ、こ
れはすでに圧縮されている文字である。ウインドウの終
わりの小さな部分は、ルックアヘッド・バッファと呼ば
れ、圧縮すべき今後の文字を含む。この構造を用いると
きには、ルックアヘッド・バッファは残りのウインドウ
と比較される。

第Ｃ図を参照するが、バッファＢは、ウインドウ・バ
ッファＷおよびルックアヘッド・バッファＬに分けて示
してある。圧縮すべき入力データは、幾つかの文字、例
えば20文字の容量を有するルックアヘッド・バッファＬ
に記憶される。ウインドウ・バッファＷには、最も新し
い過去のデータのヒストリが含まれ、数千文字、例えば
4096文字の容量がある。生データは、ルックアヘッド・
バッファＬからウインドウ・バッファＷに入り、ウイン
ドウ・バッファＷの最も古いデータが捨てられる（ウイ
ンドウ・バッファＷが一杯になったとき）。こうした理
由により、ウインドウ・バッファＷは時々‘スライディ
ング・ウインドウ’と呼ばれる。

LZ1アルゴリズムのある実施にしたがい、データがル
ックアヘッド・バッファＬに入れられると、各文字はウ
インドウ・バッファＷの内容と比較あれる。ある文字で
一致が見つからなければ、その文字は、その生の状態、
すなわちイノベーションとして出力される。該文字は、
次にウインドウ・バッファＷにも入れられる。

ルックアヘッド・バッファＬのある文字で一致が見つ
かったならば、より長い一致を見つけることができるか
どうかを確認するために、次の文字も、一致文字と組み
合わせて考えられる。このプロセスは、別の文字を追加
することが、ウインドウ・バッファＷにもはや一致がな
いということを、意味するまで、繰り返される。コード
・ワード／記号は一致の長さを示し、ウインドウ・バッ
ファＷのその位置は出力され、関連ストリングがウイン
ドウ・バッファＷに追加される。

コード・ワード／記号は、参照の最初の文字がバッフ
ァよりも前にある限り、ルックアヘッド・バッファに達
するストリングを参照することが許容される。一致がル
ックアヘッド・バッファに達すると、LZ1圧縮装置は一
種のラン・レングス（run−length）エンコーディング
を行っている。一致がバッファよりも前の文字で始まる
場合には、圧縮装置“aaaaaa..."などの一続き（run）
を圧縮している。同様に、一致の最初の文字がバッファ
の前の幾つかの文字を始める場合には、圧縮装置は“ab
abab..."または“abcabcabc..."などの一続きを圧縮し
ている。

RINTINTIN例は、第Ｄ図に示すようなこのアプローチ
に従って圧縮され、これが圧縮すべき最初のデータであ
ること、すなわち最初にウインドウ・バッファＢが空で
あることを想定している。最初の４文字はイノベーショ
ンとしての出力である。５番目の文字Ｉはウインドウ・
バッファＷにあるので、次の文字^Nは、INがすでにウイ
ンドウ・バッファＷにあるかどうかをチェックするため
のものあると考えられる。ストリングINTも考えられる
が、それもまたウインドウ・バッファにある。しかし、
次の文字Ｉを追加することにより、ウインドウ・バッフ
ァＷにないストリングINTIを生成する。したがって、コ
ード・ワードは、ウインドウ・バッファＷのINTの位置
を示す出力であり、長さ３である。位置は‘オフセッ
ト’により示され、すなわち、ウインドウ・バッファＷ
において、現在の文字からどれくらい離れたところで一
致がスタートするかを示す。

次の文字Ｉは、ウインドウ・バッファの前のＩと一致
し、最終ストリングINは、ウインドウ・バッファの３文
字戻った該ストリングの場合と一致するので、出力コー
ド・ワードは＜3,2＞である。

復元中に、ウインドウ・バッファも保たれ、復元すべ
き入力データにコード・ワードが見つかると、復元は、
そのオフセットおよび長さにしたがってウインドウ・バ
ッファの適切なストリングを捜すこと、およびストリン
グを出力することが伴う。したがって、RINTINTIN例で
は、最初のコード・ワード＜3,3＞に遭遇すると、３文
字戻って始まる長さ３のストリング、すなわちINTが出
力される。次のコードワード＜3,2＞に遭遇すると、３
文字戻って始まる長さ２のストリング、すなわちINが出
力される。

RESETコマンドには、LZ1アプローチにしたがって、ウ
インドウ・バッファをクリアする作用がある。FLUSHコ
マンドには、ルックアヘッド・バッファをクリアする作
用がある。したがって、LZ1アプローチの‘辞書’は、
２つの連続するRESETコマンドの間でウインドウ・バッ
ファを‘スライド’するデータ量により表される。LZW
アルゴリズムに関しては、復元は最後のRESETから始め
なければならない。

多数のレコードにわたり辞書を共用する際、すなわち
各レコードの終わりでウインドウ・バッファをリセット
することのないときに、比較的短い一連のレコードに対
して圧縮比を改善することができるという利点がある。

FLUSHコマンドの作用は、すでに述べたようにルック
アヘッド・バッファのすべての内容を一致させることで
あり、それ以上のデータよりも前の出力をルックアヘッ
ド・バッファに入れることが許容される。連続RESETコ
マンド間でこのようにしてルックアヘッド・バッファを
フラッシュする際の利点は、辞書を作るために用いるよ
りも小さなデータ・セグメントを、選択的に復元するこ
とができる点である。これは、データ・レコードを、テ
ープに記憶された圧縮データに付加することが望まれる
場合に特に有益である。各データ・レコードの後でルッ
クアヘッド・バッファをフラッシュする場合には、現行
レコードの終わりよりも後で、それ以上のレコードを明
らかに付加することができるように、テープ上のいずれ
かの圧縮レコードの終わりを見つけることができる。

第Ｃ図は説明のために全く簡略化されていることが分
かる。ウインドウ・バッファは、過去のデータのセグメ
ントを定義する２つのポインタの形で実行するか、実際
に、他の適切な構成を用いることができる。

次に、圧縮か非圧縮かはともかくとして、テープに対
するデータ記憶の方法について説明する。

ユーザ（ホスト・コンピュータ）からテープ記憶装置
へのデータ供給には、記憶装置に送られる離散的パッケ
ージ（レコード）にするためのデータの物理的分離であ
るか、あるいは、特定の信号によってホストが表現する
高レベルな記録の概念的編成であるかはともかく、デー
タのユーザ分離を伴うのが普通である。このデータのユ
ーザ分離は、ホストにとって特に意味がある（この意味
は、テープ記憶装置には分らないのが普通であるが）。
従って、その存在が、入力データの物理的分離によって
記憶装置に伝えられたとしても、ユーザ分離を論理的セ
グメンテーションとみなすことが適切である。

第１図（ａ）には、既存のタイプのホストがテープ記
憶装置に対して供給できるユーザ・データと特殊な分離
信号のシーケンスが示されている。この例では、データ
は、可変長レコードR1〜R9として供給されるが、この物
理的分離の論理的意味は、ホストには分るが、記憶装置
には分らない。物理的分離以外に、ユーザ分離情報は、
特殊な“ファイル・マーク”信号FMの形で供給される。
ファイル・マークFMは、データ・レコードの間に挿入し
て、記憶装置に与えられるが、やはり、この分離の意味
は、記憶装置には分らない。レコードに対する物理的分
離によって、第１レベルの分離が得られ、一方、ファイ
ル・マークによって、第１レベルの分離と階層をなす第
２レベルの分離が得られる。

第１図（ｂ）には、テープ10に対して第１図（ａ）の
ユーザ・データ及びユーザ分離情報を記憶するための可
能性のある物理的編成の１つが示されているが、この編
成は、既知のデータ記憶方法に基づくものである。第１
図（ａ）と第１図（ｂ）との間におけるマッピングは、
簡単なものである−ファイル・マークFMは、一定周期の
バースト１として記録されるが、さもなければ、データ
・レコードとして扱われ、レコードR1〜R9とファイル・
マークFMは、信号の記録されていないブロック間ギャッ
プ２によって互いに隔てられる。ブロック間ギャップ２
は、記憶データを分離して、ユーザに分る論理単位のレ
コードにすることを可能ならしめ、ファイル・マークFM
（一定周期のバースト１）は、レコードをレコードの論
理的集合に分割する第２レベルの分離マークを形成す
る。

第１図（ｃ）には、テープ10に第１図（ａ）のユーザ
・データ及びユーザ分離情報を記憶するための、可能性
のある周知の第２の編成が示されている。この場合、ユ
ーザ・データは、それぞれ、グループの内容に関する情
報を含むインデックス４を備えた固定サイズのグループ
３に編成される。２つのグループ３間における境界は、
一定周期のバースト５によって表示することができる。
データをグループに分割するのは、純粋に、関係する記
憶装置の都合に合わせたものであり、ホストには明らか
なはずである。グループ内のユーザ・データは、いかな
る点においても物理的に分離しておらず、各レコード
は、先行レコードの終端からとぎれることなく続いてい
るだけであり、グループ内のデータを分離して、レコー
ドにし、さらに、ファイル・マークで区切られたレコー
ドの集合にすることに関した全ての情報が、グループの
インデックスに含まれている。本例の場合、レコードR1
〜R8とR9の第１の部分が、例示のグループ３に保持され
ている。

インデックス４の長さは、グループ内に存在する分離
マークの数及びレコードの数によって変動するのが一般
であるが、グループの終端に対するインデックス内の所
定位置にインデックス長を記録することによって、イン
デックスと最後のバイトとの境界を識別することができ
る。例えば、パディングといった未定義内容を有するス
ペースが、データ領域の終端とインデックスの第１のバ
イトの間に存在する可能性がある。

第２図には、インデックス４の内容が示されている
が、見ての通り、インデックスは、２つの主データ構
造、すなわち、グループ情報テーブル６及びブロック・
アクセス・テーブル７から構成される。ブロック・アク
セス・テーブル７のエントリ数は、グループ情報テーブ
ル６におけるブロック・アクセス・テーブル・エントリ
（BAT ENTRY）カウント・フィールドに記憶されてい
る。グループ情報テーブル６には、ファイル・マーク・
カウントFMC（記録の終端（BOR）マークには、現在のグ
ループに納められた任意のものが含まれるので、ファイ
ル・マークの数）、及び、レコード・カウントRC（定義
される）といった、各種カウントが含まれている。

ブロック・アクセス・テーブル７は、一連のアクセス
・エントリとして、グループの内容、及び、とりわけ、
グループに保持されたユーザ・データの論理的セグメン
テーションを示している（すなわち、グループ内におけ
る各レコード境界及び分離マークを表わしたエントリを
保持している）。アクセス・エントリは、グループ内容
の順番に並んでいる。

第３図を参照すると、ブロック・アクセス・テーブル
内のエントリは、それぞれ、エントリのタイプを示すFL
AGエントリと、その値を示すCOUNTエントリから構成さ
れる。FLAGフィールドは、８ビットであり、COUNTフィ
ールドは、24ビットである。FLAGフィールド内のビット
は、下記の意味を有している： SKP−セットされると、“スキップ・エントリ”を示
すSKIPビット。スキップ・エントリは、ユーザ・データ
によって取り上げられないグループ内のバイト数、すな
わち、（グループのサイズ）−（ユーザ・データ領域の
サイズ）を示す。

XFR−セットされると、テープに対するユーザ・デー
タの書込みを表わすDATA TRANSFERビット。

EOX−セットされると、テープに対するユーザ・デー
タ・レコードの書込みの終了を示すEND OF DATA TRA
NSFERビット。

CMP−セットされると、エントリが圧縮データに関連
したものであることを示すCOMPRESSIONビット。

EOT−このビット値は、この説明の目的には、関係が
ない。

MRK−セットされると、エントリが、データ・レコー
ドではなく、分離マークに関係していることを示すSEPA
RATOR MARKビット。

BOR−セットされると、データ・レコードの始端位置
を示すBEGINNING OF RECORDビット。

EOR−セットされると、テープ上におけるデータ・レ
コードの終端位置を示すEND OF RECORDビット。

第３図には、ブロック・アクセス・テーブル中に作成
可能なエントリの７つのタイプが示されている。SEPARA
TOR MARKエントリは、ドライブによってレコードとし
て扱われるので、BOR及びEORビットがセットされる。次
の４つのエントリは、データ転送に関する情報を表わし
ているので、それぞれ、XFRビットがセットされる。STA
RT PART OF RECORDエントリは、レコードの始端だけ
が、グループに入っており、レコードの次の部分が、後
続のグループにはみ出している場合に関するものであ
る。そのグループにはレコードの始端または終端がない
ので、MIDDLE PART OF RECORDエントリにセットされ
る唯一のビットは、データ転送ビットである。END PAR
T OF RECORDエントリは、FLAGにEORビットがされてお
らず−代りに、EORビットは、総レコード・バイト・カ
ウントを示すTOTAL COUNTエントリにセットされる。グ
ループに関するブロック・アクセス・テーブルの最後の
エントリは、常に、ユーザ・データによって取り上げら
れないグループ内のスペース量を示すSKIPエントリであ
る、すなわち、SKIPエントリに関するCountフィールド
内のエントリは、グループ・サイズ（例えば、126632バ
イト）からデータ領域サイズを引いたものである。

第１図（ｃ）に示すレコードのグループ３に関するブ
ロック・アクセス・テーブルの一例が、第４図に示され
ている。レコードR1〜８に関するカウント・エントリ
は、該レコードに関する総バイト・カウントであるが、
レコードR9に関するカウント・エントリは、R9のグルー
プ３内にある部分のバイト・カウントである。ファイル
・マークFMに関するカウント・エントリは、フォーマッ
トに従って０または１になる。SKIPエントリに関するカ
ウント・エントリは、126632からテーブルに既に現われ
たバイト・カウントの和を引いたものである（TOTAL C
OUNTエントリは含まない）。

別の実施例では、第3A図に示すようなグループのデー
タを圧縮するために用いるアルゴリズムを示している、
ブロック・アクセス・テーブルにさらに可能なエントリ
がある。COUNTフィールドに入力されるアルゴリズム番
号は、DCアルゴリズム番号の基準に準拠する望ましい番
号である。グループとしての圧縮レコードのためのデー
タ転送およびトータル・カウントFLAGエントリには、CM
Pビット・セットがある。したがって、グループの中の
圧縮および非圧縮レコードは、CMPビットに基づいてド
ライブにより区別することができる。例えば、第１図
（ｃ）において、偶数番号のレコードを圧縮レコードお
よび奇数番号のレコードを非圧縮レコードと仮定する
と、ブロック・アクセス・テーブルのエントリは第4A図
に示す通りである。第4A図では、UBCXはレコードＸの非
圧縮バイトを示し、CBCXはレコードＸの圧縮バイトを示
す。

第５図は、ユーザ・データおよび関連情報をテープに
記憶するための別の可能な構成を示す。再び、ユーザ・
データは、グループに、グループの内容についての情報
を含めるためのブロック・アクセス・テーブルを構成す
る圧縮データを含む場合でも、各グループに非圧縮され
たインデックスを含んだ、固定サイズのグループに構成
される。グループ間の境界は、一定周期のバーストによ
り示すことができる。

しかし、レコードだけによりグループ・インデックス
に情報を記憶することよりも、この実施例では、１つの
エンティティが１つ以上のレコードから成る“エンティ
ティ”によって、グループの内容についての情報を記憶
することが必要である。この実施例では、エンティティ
に、各々が同じ非圧縮長を有するｎ個の圧縮レコードを
含めることができる（ｎは１以上の数）。

第５図において、グループＧは、圧縮データの４つの
完全なレコードCR₁〜CR₄と、８バイトのヘッダー部分Ｈ
から成る単一のエンティティENTITY1（またはE1）によ
って構成される。レコードCR₁〜CR₄は、同じ非圧縮長を
有しているが、データ圧縮後は、当然異なる長さにな
る。

データ・ストリーム内における非圧縮状態のままのヘ
ッダー部分Ｈには、下記の情報が含まれている： H_L −ヘッダー長（４ビット）。（次の12ビット
は、予約されている）。

ALG ＃−データの圧縮に用いられる圧縮アルゴリズム
を表わした記憶数１バイト）。

UBC −エンティティ内のレコードに関する非圧縮バ
イト・カウント（３バイト）。

＃RECS−エンティティ内のレコード数（２バイト）。

任意選択により、エンティティ内における各レコード
の終端には、各レコードの圧縮バイト・カウントを納め
る後書き（trailer）部分を含むことが可能である。例
えば、後書き部分は、“レコードの終端”（EOR）のコ
ード・ワードのすぐ後に配置されることになる。この特
徴が存在する場合、ヘッダー部分において、ヘッダー長
H_Lの後に予約された12ビット中に、後書き部分の長さ、
例えば、３ビットを示すこともできる。

エンティティの各レコードに後書き（trailer）部分
を有する実施例の一例を第5A図に示す。後書き部分は、
各圧縮レコードの終わりにおいて、非圧縮データストリ
ームに書き込まれる。したがって、第5A図のエンティテ
ィには。ヘッダー部Ｈおよび、各々に非圧縮後書き部Ｔ
を有し、非圧縮されたときに同じ長さの４つの圧縮レコ
ードCR₁〜CR₄を含む。

各レコードの後書き部分TRには、レコードの圧縮バイ
ト・カウント（CBC）および巡回冗長検査（CRC）を含ん
でいる。後書き部分は、この例では各レコードの終わり
の６ビットを占める。後書き部分の長さ（T_L）は、ヘッ
ダー部Ｈに含まれ、ヘッダー部Ｈの最初のバイトの最後
の４ビットを占める。

後書き部分を含めることにより、SKIPカウント・エン
トリはそれに応じて小さくなるが、ブロック・アクセス
・テーブルＴのエントリの特性を変えることはない。

データストリームへの圧縮バイト・カウントの書込み
は、DCドライブまたは適するように構成された非DCドラ
イブで、リンク・リストにおけるポインタとして用い
て、各圧縮レコードが始まったり終わる位置を推定する
ことができる。

ヘッダーにヘッダー部分（及び、適合すれば、後書き
部分）の長さを含む利点は、それによって、この長さを
変えることが可能になり、同時に、所望の場合には、ド
ライブにヘッダーをスキップさせることができるという
ことである。

ブロック・アクセス・テーブルにおける各グループの
インデックスには、レコードの形ではなく、エンティテ
ィの形で、ただし、別様の場合には、第２図〜第４図に
関連して前述のように、情報が記録される。第５図に
は、エンティティE₁に関するブロック・アクセス・テー
ブルのエントリも示されいる。

ブロック・アクセス・テーブルＴ内に作成されるエン
トリのタイプは、第２図〜第４図に関連して解説のもの
と同様である。その相違は、この場合、FLAGフィールド
にCMPビットをセットすることによって、エントリがレ
コードではなく、エンティティに関するバイト・カウン
トに関連したものであることが示されるという点であ
る。

１つの可能性として、エンティティに圧縮レコードだ
けしか含めることができなくなるが、これは、望まし
い。従って、これは、FLAGフィールドにCMPビットをセ
ットすると、やはり、COUNTエントリが圧縮バイト・カ
ウントであることを表わすことになる。一方、もう１つ
の可能性として、エンティティに圧縮データと非圧縮デ
ータのいずれかを含み、例えば、エンティティ内のデー
タが非圧縮データであることを表わす、全てゼロといっ
た特定のアルゴリズム数を予約することが可能になる。

レコードではなく、エンティティの形で、ブロック・
アクセス・テーブルＴに情報を記憶することによって、
テープにレコードを書き込み、テープからレコードを読
み取ることに関連した記憶管理のオーバヘッドが減少す
る。第２図〜第４図に示す案を用いる場合には、グルー
プＧに関して、ブロック・アクセス・テーブル中に５つ
のエントリが必要になるが、この場合には、２つのエン
トリしか必要ない。

レコードをエンティティに編成すると、読取り及び書
込み時に必要なプロセッサの介入度が低下するので、同
じ非圧縮サイズの複数レコードを転送するのが容易にな
る。エンティティに含まれるレコードのシーケンスの書
込みに必要なプロセッサの介入は、ヘッダー部分の形成
と、ブロック・アクセス・テーブル内における適合する
エントリの作成だけということになる。対照的に、第１
図〜第４図に関連して説明した既知の案を用いると、各
レコード毎にプロセッサの介入が必要になる。圧縮され
たバイト・カウントは、圧縮プロセスの終了後まで未知
のため、これは、データ圧縮に関してとりわけ重要であ
る。従って、あるグループをデータで満たそうとする場
合、適合するレコード（及び対応するブロック・アクセ
ス・テーブルのエンティティ）数が、分らない。あるエ
ントリにブロック・アクセス・テーブルの要件を固定す
ることによって、どれだけのデータのレコードがグルー
プに納まるかに関係なく、グループ全体を１回のプロセ
ッサ介入で満たすことができるる。データの読取り時に
も、同様の利点が得られる。

第６図を参照すると、エンティティ（En）は２つ以上
のグループにまたがる場合もある、例えば、単一の比較
的長いレコードCR₁を含むエンティティE₁が、グループG
₁を充填して、グループG₂にまで入り込む。第６図に
は、グループG₁,G₂のブロック・アクセス・テーブル内
のエントリも示されている。グループ間の連係度を弱め
るため、新しいエンティティは、グループ内において、
できるだけ早く開始する、すなわち、前のレコードが圧
縮されていなければ、グループの開始部において、また
は、グループ内における最初の圧縮レコードの始端にお
いて、あるいは、前のレコードが圧縮されており、前の
グループからはみ出してきたものである場合には、最初
の新しい圧縮レコードの始端において開始する。従っ
て、圧縮レコードCR₁の終端において、次のエンティテ
ィE₂が開始する。エンティティE₂には、非圧縮長の等し
い、４つの圧縮レコードCR₂〜CR₅が含まれている。

グループには、圧縮データを含むエンティティと、非
圧縮データを含む“裸のレコード”とを混合したものを
納めることができるように企図されている。この構成の
一例が、ブロック・アクセス・テーブル内の対応するエ
ントリも示す第７図に示されている。

グループＧには、ヘッダー部分Ｈと、３つの圧縮レコ
ードCR₁,CR₂、及び、CR₃から成るエンティティが含まれ
ている。グループＧは、また、非圧縮レコードR₄（ヘッ
ダー部分を備えていない）も含んでいる。グループＧの
ブロック・アクセス・テーブルＴには、４つのエントリ
が含まれている： 第１のエントリは、グループ内のエンティティの全バ
イト・カウント、 第２のエントリは、ファイル・マーク・エントリ（レ
コードR₄の開始前に入力データ内におけるファイル・マ
ークの存在を示す）、 第３のエントリは、非圧縮レコードR₄の全バイト・カ
ウント、 最後のエントリは、SKIPエントリ。

第７図から注目されるのは、CMPビット（FLAGフィー
ルドの第４のビット）は、エンティティ・バイト・カウ
ント・エントリに対してセットされているが、裸のレコ
ード・バイト・カウント・エントリに対してはセットさ
れていないという点である。適切に構成された非DCドラ
イブは、CMPビットが関連するブロック・アクセス・テ
ーブル・エントリにセットされているか否かをチェック
することによって、圧縮データと非圧縮データが混在し
たテープ上において、前記データの識別を行なうことが
できる。

この案では、エンティティ内の分離マークが認められ
ない。例えば、ホストが、シーケンスをなす長さの等し
いレコードを送信中で、そのシーケンス内にファイル・
マークまたは他の分離マークが存在する場合、分離マー
クの前の第１組のレコードが、１つのエンティティに納
められ、分離マークが、テープに書き込まれ、ファイル
・マークに続くシーケンス内の１組のレコードが、第２
のエンティティに納められる。もちろん、２つのエンテ
ィティに関した対応するエントリと分離マークが、関連
グループのブロック・アクセス・テーブル内に作成され
る（この例には、１つのグループしか含まれていないも
のと仮定する）。

第８図には、グループのブロック・アクセス・テーブ
ルにおいて可能性のある有効なエントリのシーケンスが
示されている。第８図では、状態及びアクションが矩形
で指定され、ブロック・アクセス・テーブルのエントリ
が楕円で示されている。“スパン”レコード／エンティ
ティは、１つのグループから別のグループへ延びるもの
である。

エンティティの存在、及び、エンティティ内において
許容される複数圧縮レコードの存在を考慮に入れて、各
グループのインデックスにおけるグループ情報テーブル
のいくつかのフィールドは、次のように定義される。

レコード・カウント−このフィールドは、BOR以後、
現在のグループまで書き込まれた全てのグループに関す
るグループ情報テーブルの現在グループ・エントリ（下
記参照）におけるレコード数の値の合計を指定する４バ
イト・フィールドである。

現在グループ内のレコード数−このフィールドは、下
記の合計を指定する２バイトのフィールドである： ｉ）現在グループのブロック・アクセス・テーブルにお
ける分離マーク・エントリの数。

ii）現在グループのブロック・アクセス・テーブルにお
ける非圧縮レコード・エントリの総カウント数。

iii）現在グループのブロック・アクセス・テーブル内
における非圧縮レコード・エントリの全カウント数。

iv）現在グループのブロック・アクセス・テーブルにお
けるエンティティ・エントリの総カウントまたはエンテ
ィティ・エントリの全カウントが存在する、全てのエン
ティティ内における圧縮レコード数の合計。

ｖ）こうしたエントリが存在する場合、現在グループの
ブロック・アクセス・テーブルにエンティティ・エント
リの開始部分が存在する、エンティティ内の圧縮レコー
ド数−１。

vi）現在グループのブロック・アクセス・テーブルにお
けるエンティティ・エントリの総カウント数。

前レコードのグループ数−このフィールドは、分離マ
ーク、アクセス・ポイント・または、非圧縮レコードの
始端が生じた最高番号の前グループの実行番号を指定す
る２バイト・フィールドである。それには、こうした前
グループが存在しない場合、全てのゼロ・ビットが含ま
れることになる。

第１図〜第８図に関して解説した固定サイズのグルー
プにおけるレコードの編成に関連し、一般に、グループ
は、復元目的のため、互いに独立した状態に保つことが
望ましい。すなわち、一般に、RESETコード・ワード
は、各グループの始端またはその近くに配置することが
望ましい。これに関する２つの主たる理由のうち１つ
は、グループ間の連係を弱めることによって、コントロ
ーラにおいて必要とされるバッファ・スペース量の減少
に役立つ、すなわち、任意の時点においてバッファ内に
２つ以上のグループを納めなければならない可能性を低
下させることになるためである。グループの始めにおけ
る辞書RESETに対する別の理由は、グループの中央でレ
コードを選択的に復元することが所望されるときに、グ
ループの外側に出て関連辞書を開始させる必要のないこ
とである。

圧縮データへのアクセスを改善するように、各レコー
ドの後にFLUSH条件を付けることには利点がある（FLUSH
コード・ワードは“レコードの終わり（EOR）”コード
・ワードとも呼ばれる）。この特徴により、レコードの
前にあるRESETポイントから復元する必要性に応じて、
レコードを個々に復元することができる。各レコードの
終わりにFLUSH条件を付けることは、次のレコードから
のデータに入れることなく、各レコードのデータを復元
することができることを意味している。この特徴は、新
しいレコードを現行レコードの中心のポイントに付加す
ることを所望する場合にも有益である。

データ辞書を構成する圧縮データ量は、“圧縮オブジ
ェクト”と呼ばれる。圧縮オブジェクトは、第９図に示
すように、２グループ以上のデータにまたがる可能性が
ある。レコードが１つのグループからもう１つのグルー
プにオーバラップする場合、RESETコード・ワードは、
すぐ隣の圧縮レコードの始端において、データ・ストリ
ーム内に配置される。

第９図において、グループG₁は、３つの完全な圧縮レ
コードCR₁,CR₂,CR₃,及び、第４の圧縮レコードCR₄の最
初の部分から構成される。レコードCR₄の最後の部分
は、次のグループG₂に入り込んでいる。この例の場合、
レコードは、エンティティをなすようには編成されな
い。

データ圧縮時、グループG₁の始端において、辞書がリ
セットされる（第９図のＲで表示）。FLUSHコード・ワ
ード（Ｆで表示）が、各レコードの終端に位置するよう
にデータ・ストリームに挿入される。現在の辞書は、レ
コードCR₄が終了するまで継続し、その時点で、辞書が
リセットされる。従って、現在の圧縮オブジェクトは、
レコードCR₁〜CR₄から構成される。したがって、増大し
た効率のデータ圧縮により、辞書を、２つ以上の等しく
ない非圧縮長のレコードにわたり拡張して用いることが
できるという利点がある。

後で、例えば、レコードCR₃を選択的に復元すること
が所望の場合、これは、レコードCR₁の開始部、すなわ
ち、レコードCR₃を含む圧縮オブジェクトの開始部で復
元を開始し、レコードCR₃の終端まで、データの復元を
行なうことによって可能となる。レコードCR₃の終端に
おいて“明確な中断”が得られるようにする、すなわ
ち、レコードCR₃の終端において、FLUSHコード・ワード
のために、レコードCR₄の始端に入り込まないようにす
ることが可能になる。

したがって、‘アクセス・ポイント’間に点在される
フォーマットによりアクセス可能なFLUSHコード・ワー
ド（フォーマットによりアクセス可能なRESETコード・
ワード）を与えることにより、データ圧縮中に辞書を作
成するために用いるデータ量よりも小さなデータ・セグ
メントの選択的復元をすることができる。各レコードの
圧縮バイト・カウントはブロック・アクセス・テーブル
に記憶されるので、レコードの終わりにあるFLUSHコー
ド・ワードにアクセス可能である。

該フォーマットでは、‘アクセス・ポイント’を形成
する圧縮対象の始点、すなわちドライブで復元動作を開
始することのできるポイントは、幾つかの方法のうちの
１つにより示すことができる。アクセス・ポイントは、
各グループのブロック・アクセス・テーブルにおいて明
示的に記すことができる。この他に、アクセス・ポイン
トの存在は、ブロック・アクセス・テーブルの別のエン
トリにより示唆することができ、例えば、アルゴリズム
番号エントリの存在でさえ、該グループの最初の新レコ
ードのはじめにアクセス・ポイントを含むことがある。
また、アルゴリズム番号のビットは、新しい辞書が、該
グループの最初の新レコードのはじめにおいて開始する
ことを示すために確保しておくこともある。

レコードが、エンティティをなすように編成され、エ
ンティティが第５図〜第７図に関連して解説のグループ
をなすように編成される場合、比較的少量のデータを納
めたエンティティを共用する辞書の利点が得られるよう
にするため、圧縮オブジェクトが、第10図に示すよう
に、２つ以上のエンティティにまたがるようにすること
も可能である。

第10図には、圧縮データに関する３つの定サイズのグ
ループG₁,G₂,G₃が示されている。グループG₁には、完全
なレコードCR₁と、次のレコードCR₂の最初の部分が含ま
れている。レコードCR₁は、エンティティE₁における唯
一のレコードである。グループG₂には、レコードCR₂の
中間部分が含まれている。グループG₃には、レコードCR
₂の終端部分が含まれ、さらに、レコードCR₃等も含まれ
ている。エンティティE₂には、単一の比較的長いレコー
ドCR₂が含まれている。

圧縮時、辞書は、グループG₁の始端でリセットされる
が（Ｒで表示）、レコードCR₁は比較的短いので、圧縮
オブジェクトは、レコードCR₁及びエンティティを超え
て延び、レコードCR₂及びエンティティE₂を含んでい
る。圧縮オブジェクトは、レコードCR₂の終端で終了
し、新しい圧縮オブジェクトが、レコードCR₃の始端で
開始する。

他の可能性には、新辞書の開始を示すための、エンテ
ィティ・ヘッダーの非ゼロ・アルゴリズム番号の存在、
およびその他に、予め定められた値、例えばゼロなどを
用いるためのアルゴリズム番号ヘッダー・エントリがあ
る。

ブロック・アクセス・テーブルのエンティティの圧縮
バイト・カウントを書き込むことによりアクセス可能
な、各エンティティの終わりにあるFLUSHコード・ワー
ドの存在によって、１エンティティ毎に、レコードの選
択的復元をすることができる。例えば、第10図を参照す
るが、エンティティE₂（この例ではたまたま１つのレコ
ードCR₂）の内容は、レコードCR₃のはじめからデータを
得ることなく復元することができる。しかし、テープ・
フォーマットでアクセス可能な最も近い前の辞書の始点
であるエンティティE₁のはじめにあるRESETコード・ワ
ードから復元を開始しなければならない。第20A図およ
び第20B図に関して記述するエンティティ・ヘッダーの
情報を利用して１つのレコード毎にデータを復元するこ
ともできる。

エンティティの各レコードに、レコードの圧縮バイト
・カウントを含む後書き部分（第5A図に関してすでに述
べた通り）を含み、各レコードの終わりにFLUSHコード
・ワードがある場合、この特徴は、１つのレコード毎に
復元を達成するときに用いることができる。

各圧縮レコードでその固有のエンティティを有するよ
うに、テープ全体を書き込むことができる。これは、選
択的復元のためのレコードへのアクセスを改善するが、
８バイト・ヘッダー／レコードおよび４バイト・インデ
ックス・エントリ／レコードのオーバヘッドを伴う。ま
た、各エンティティのヘッダーを（少なくとも）スキッ
プするためにプロセッサの介在が要求されるので、多重
レコード転送も遅くなる。

もちろん、DCチップはレコードの中間部であっても、
アルゴリズムに従って、データ・ストリームにRESETコ
ード・ワードを挿入する。以上の説明は、テープ・フォ
ーマットによって強制され、認識され、利用されるRESE
Tコード・ワードに関するものである。

分かりやすくするために、第５図〜第10図では、エン
ティティおよび圧縮対象に、関連グループのインデック
スを含まない。

次に、本発明のヘリカル走査を実施するためのテープ
・フォーマットについて解説する。

後述の記憶方法及び装置は、DAT Conference Stand
ard（1988年３月、日本の東京にあるElectronic Indus
tries Association of Japanで決定）に基づくPCMオ
ーディオ・データの記憶に用いられるのと同様にフォー
マットでデータを記憶するヘリカル走査技法を利用す
る。ただし、本方法及び装置は、デジタル化オーディオ
情報よりもコンピュータ・データの記憶に適したもので
ある。

第11図には、テープ・カートリッジ17からのテープ10
が、巻き角が90゜になるように、回転ヘッド・ドラム12
を所定の角度で通過するヘリカル走査テープ・デッキ11
の基本レイアウトが示されている。動作時、テープ10
は、ピンチ・ローラ16がテープを押しつけるキャプスタ
ン15の回転によって、矢印Ｔが示す方向に、繰出しリー
ル13から巻取りリール14に移動し、同時に、ヘッド・ド
ラムは、矢印Ｒで示す方向に回転する。ヘッド・ドラム
12には、角度的に180゜間隔をあけて配置された２つの
読取り／書込みヘッドHA、HBが収容される。既知の方法
では、これらのヘッドHA、HBは、第12図に示すように、
オーバラップする斜めトラック20、21を、それぞれ、テ
ープ10に書き込むように構成されている。ヘッドHAが書
き込むトラックは、正のアジマスを有しており、一方、
HBが書き込むトラックは、負のアジマスを有している。
各対をなす正と負のアジマス・トラック20、21が、フレ
ームを構成する。第12図には、本発明の装置によって書
き込まれるようになっている各トラックの基本フォーマ
ットが示されている。各トラックは、２つのマージン区
域22、２つのサブ区域23、２つのATF（自動トラック追
従）区域24、及び、主区域25から構成される。ATF区域2
4は、ヘッドHA、HBが、既知の方法で正確にトラックを
追従できるようにする信号を供給する。主区域25には、
いくつかの補助的な情報も記憶されるが、主として、該
装置に供給されるデータ（ユーザ・データ）の記憶に用
いられる。主区域及びサブ区域に記憶される補助的情報
の項目は、サブ・コードとして知られており、例えば、
ユーザ・データ、テープに対するそのマッピング、いく
つかの記録パラメータ（フォーマットのアイデンティテ
ィ、テープ・パラメータ他）、及び、テープの使用記録
の論理的編成に関するものである。

次に、前述のDAT Conference Standardに適合する
ブロック・サイズに関する詳細を含む、主区域25及びサ
ブ区域23、のより詳細な説明を行なうものとする。

第13図には、トラックの主区域25に関するデータ・フ
ォーマットが示されている。主区域は、それぞれ、長さ
が36バイトの130のブロックから構成されている。最初
の２つのブロック26は、再生時におけるタイミングの同
期を容易にするタイミング・データ・パターンを納めた
プリアンブルである。残りの128のブロック27が、“主
データ区域”を構成する。主データ区域の各ブロック27
は、４バイトの“主ID"領域28と、32バイトの“主デー
タ”領域29から構成され、その構成は、第13図の下部に
示されている。

主ID領域28は、同期バイト、２つの情報を納めたバイ
トW1、W2、及びパリティ・バイトから構成される。バイ
トW2は、全体としてブロックに関連した情報（タイプ及
びアドレス）の記憶に用いられ、一方、バイトW1は、サ
ブ・コードの記憶に用いられる。

各ブロック27の主データ領域29は、一般に、ユーザ・
データとユーザ・データ・パリティの両方または一方に
よって構成される32のバイトから構成される。ただし、
所望の場合には、主データ領域にサブ・コードを記憶す
ることも可能である。

第14図には、トラックの各サブ区域23におけるデータ
・フォーマットが示されている。サブ領域は、それぞ
れ、長さが36バイトの11のブロックから構成される。最
初の２ブロック30は、プリアンブルであり、一方、最後
のブロック31は、ポストアンブルである。残りの８ブロ
ック32は、“サブ・データ区域”を構成する。各ブロッ
ク32は、４バイトの“サブID"領域33と、32バイトの
“サブ・データ”領域34から構成され、その構成は、第
14図の下部に示されている。

サブID領域33は、同期バイト、２つの情報を納めたバ
イトSW1、SW2、及び、パリティ・バイトから構成され
る。バイトSW2は、全体としてブロックに関する情報
（タイプ及びアドレス）及びサブ・データ領域34の構成
を記憶するのに用いられる。バイトSW1は、サブ・コー
ドの記憶に用いられる。

各ブロック32のサブ・データ領域34は、４つの８バイ
トの“パック"35にまとめられた32バイトから構成され
る。これらのパック35は、サブ・コードの記憶に用いら
れ、記憶されるサブ・コードのタイプは、各パックの最
初の半バイトを占めるパック・タイプ・ラベルによって
表示される。全偶数ブロックの第４のパック35は、ゼロ
にセットすることもできるし、さもなければ、第３のパ
ックと同じにする場合もあり、一方、全奇数ブロックの
第４のパックについては、そのブロック及び先行ブロッ
クの両方に関する最初の３つのパックについて、パリテ
ィ・チェック・データを記憶するために用いられる。

要するに、ユーザ・データは、各トラックの主データ
領域ブロック27の主データ領域29に記憶され、一方、サ
ブ・コードは、サブ・データ領域ブロック32のサブID及
びサブ・データ領域33、34と、主データ区域ブロック27
の主データ領域28、29の両方に記憶することができる。

本発明のため問題となるサブ・コードは、特定のトラ
ックが属しているテープ区域の識別に用いられる区域ID
サブ・コードと、レコード及び分離マークのカウントの
記憶に用いられるいくつかのサブ・コードである。区域
IDサブ・コードは、３つの位置に記憶される４ビット・
コードである。まず、該サブ・コードは、トラックのサ
ブ・データ区域における全ブロックのサブ・データ領域
34の第３と第４のパックに記憶される。次に、それは、
最初のブロックから始まる、トラックの全偶数サブ・デ
ータ区域ブロック32におけるサブID領域33のバイトSW1
に記憶される。このサブ・コードで識別されるテープ区
域については、第15図に関連して後述する。

レコード及び分離マークのカウントを記憶するために
用いられるサブ・コードが、テープのデータ区域内にお
ける各トラックのサブ・データ区域における全ブロック
のサブ・データ領域34の最初の２つのパック35に記憶さ
れる（第15図に関して後で参照のこと）。これらのカウ
ントは、前述のグループ情報テーブルにおけるカウント
と同じ累積カウントである。これらのカウントは、テー
プの高速探索に用いられ、このプロセスを容易にするた
め、グループを構成する１組のフレームにわたって一定
しており、グループをなすフレームのトラックに記憶さ
れるカウントは、グループの終端に適用可能なカウント
である。

次に、本記憶方法及び装置によって実現するテープに
沿ったフレームの一般的な編成について考察する。例え
ば、第15図を参照すると、テープは、３つの主たる区
域、すなわち、リード・イン区域36、データ区域37、及
び、データの終り（EOD）区域38に編成されることが分
る。テープの両端は、BOM（媒体の始端）及びEOM（媒体
の終端）と呼ばれる。ユーザ・データは、データ区域37
のフレームに記録される。リード・イン区域36には、記
録の始端BORマークと、システム情報が記憶されている
データ区域37の間の区域が含まれている。区域IDサブ・
コードは、システム区域、データ区域37、及び、EOD区
域38を互いに区別できるようにする。

データ区域のフレーム48は、それぞれ、一定数のフレ
ーム（例えば、22）からなるグループ39にまとめられ、
任意選択により、これらのグループ39は、所定の内容を
備えた１つ以上のアングル・フレームによって互いに分
離される。ユーザ・データ・レコードの編成に関連し
て、これらのグループは、第１図（ｃ）に関連して解説
のグループ３に対応する。従って、こうしたグループ39
にユーザ・データを組み入れても、ユーザ・データの論
理セグメンテーションとは無関係であり、このセグメン
テーションに関する情報（レコード・マーク、分離マー
ク）は、グループ内のユーザ・データの端に位置するイ
ンデックス40に納められる（インデックスは、実際に
は、グループ内におけるユーザ・データ空間を占有す
る）。第15図には、グループの最後のフレームの最終部
分を占めるインデックスが示されているが、これが正し
いのは、データがテープに記録される前に通常実施され
るバイトのインターリーブ動作に先立つデータ構成に関
してのみであるが、本目的のため、インターリーブ動作
を監視することができる。

実際には、インデックス内の情報は、グループにおけ
るトラックの主データ区域内で物理的に分散している。

第２図には、インデックス４の内容が示されており、
前述のように、インデックスは、２つの主データ構造、
すなわち、グループ情報テーブル及びブロック・アクセ
ス・テーブルから構成される。グループ情報テーブル
は、グループの終端における定位置に記憶され、グルー
プの内容と関係なく同じサイズである。対照的に、ブロ
ック・アクセス・テーブルは、グループの内容に従って
サイズが変動し、グループ情報テーブルから逆方向に延
びて、グループのフレームにおけるユーザ・データ区域
の残りの部分内に入り込む。ブロック・アクセス・テー
ブル内において、エントリはグループ情報テーブルから
実際のユーザ・データすなわち‘パッド’との境界へと
逆方向に作成される。

第15図には、データ区域グループ39内におけるサブ・
データ区域ブロック32の内容も示されている。前述のよ
うに、最初の２つのパックには、分離マーク・カウント
が含まれ、第２のパック35には、レコード・カウントRC
（定義済み）も含まれ、第３のパック35には、区域ID及
び絶対フレーム・カウントAFCが含まれている。グルー
プ内の全てのトラックに関して、カウントFMC、及び、
サブ、データ区域ブロックに保持されたRCは、グループ
・インデックス40のグループ情報テーブル41に保持され
たものと同じである。

第16図は、上述のテープ・フォーマットに従ってユー
ザ・データを圧縮し、記録するための記憶装置のブロッ
ク図である。該装置には、第11図に関連して部分的に既
述したテープ・デッキ11が含まれている。テープ・デッ
キ以外に、該装置には、バス55を介して該装置とホスト
・コンピュータ（不図示）のインターフェイスを行なう
インターフェイス・ユニット50、主データ区域及びサブ
・データ区域ブロック27及び32に納められ、そこから取
り出されるユーザ・レコード・データ及び分離データに
処理を施すデータ圧縮プロセッサ（DCP）及びフレーム
・データ・プロセッサ52から構成されるグループ・プロ
セッサ51、トラックの書込み／読取りを行ない、２つの
ヘッドHA,HBを適宜スイッチするための信号を合成／分
解する信号編成器53、及び、インターフェイス・ユニッ
ト50を介してコンピュータから受信する指令に応答し、
該装置の動作を制御するためのシステム・コントローラ
が含まれている。該装置の主コンポーネント・ユニット
のそれぞれについて、以下でさらに説明を行なうものと
する。

まず、データ圧縮プロセッサ（DCP）またはデータ圧
縮エンジンの構造及び動作について述べることにする。

第17図を参照するが、エンジンの中心部は、LZWアル
ゴリズムにしたがって、与えられたデータに圧縮および
復元を行うことのできるVLSIデータ圧縮チップ（DCチッ
プ）である。しかし、一度に、２つのプロセス（圧縮ま
たは復元）のうちの１つだけしかすることができない。
チップを流れるデータの速度を平滑にするために、DCチ
ップの入力および主力に、２つの先入れ先出し（FIFO）
メモリがある。一部のデータ・パターンでは、処理する
のに、他のパターンよりも多くのクロック・サイクル／
バイトを要するので、チップを流れるデータ速度は一定
ではない。瞬間データ速度は、現在の圧縮比および辞書
エントリの衝突回数により決まるが、そのいずれも、現
在のデータおよび最後の辞書RESET以来のデータの全シ
ーケンスにより異なる。サブシステムの第三セクション
は、現在の辞書エントリの局所記憶のために使用する外
部辞書メモリ（EDM）を形成するスタティックRAM列であ
る。該エントリには、文字、コード・ワード・ポイン
タ、および制御フラグを含む。

第18図には、DC集積回路のブロック図が示されてい
る。DCチップは、３つのブロック、すなわち、入力／出
力変換器（IOC）、圧縮及び復元変換器（CDC）、及び、
マイクロプロセッサ・インターフェイス（MPI）に分割
される。

MPIセクションは、DCチップを制御し、観測するため
の機能を提供する。該セクションには、６つの制御レジ
スタ、８つの状態レジスタ、２つの20ビット入力及び出
力バイト・カウンタ、及び、プログラマブル自動辞書リ
セット回路が含まれている。制御及び状態レジスタに対
するアクセスは、汎用８ビット・マイクロプロセッサ・
インターフェイス・バスを介して行なわれる。制御レジ
スタは、各種チップ機能を使用可能及び使用禁止にし、
該チップをさまざまな動作モード（圧縮、復元、排出、
または、モニタ）にする。状態レジスタは、チップ内の
20ビット・カウンタ及び各種状況フラグにアクセスす
る。

辞書をかなり頻繁にリセットすることによって、圧縮
比の改善が可能であることが分った。これは、特に、圧
縮されるデータ・ストリームに同様のバイト・ストリン
グがごくわずかしか含まれていない場合にあてはまる。
頻繁な辞書のリセットには、２つの重要な利点がある。
第１に、辞書をリセットすると、コード・ワード長が９
ビットに戻る。第２に、このデータ・ストリームを反映
した新しい辞書エントリを作成することができる（一種
の適応）。DCチップのインターフェイス・セクションに
は、圧縮比を動的にモニタし、適合すると、辞書を自動
的にリセットする回路要素が含まれている。データに冗
長性がほとんどないか、あるいは、全くなければ、ほと
んどのデータ圧縮アルゴリズムは、その出力を拡張す
る。

IOCセクションは、バイト・ストリームと可変長コー
ド・ワード（９ビット〜12ビットの範囲）のストリーム
との間における変換プロセスを管理する。８つの予約コ
ード・ワードのうちの２つが、IOCによって排他的に用
いられる。これらのコード・ワードの１つは、IOCに対
し、コード・ワードの長さを１つだけインクリメントし
なければならないことを命じるために用いられる。例え
ば、コード・ワード・サイズのプロセスは、CDCセクシ
ョンから切り離される−IOCは、独立したパイプ・ライ
ン・プロセスに従って処理を行なうので、CDCは、IOCに
よって減速することなく、圧縮または復元を行なうこと
が可能になる。

FLUSH（または‘レコードの終わり’（EOR））コード
・ワードである第二予約コード・ワードは、次のコード
・ワードがデータの現在のパケットに関連する最後のコ
ード・ワードであること、すなわちFLUSHコード・ワー
ドが実際には圧縮レコードの最後から２番目であること
をIOCに警告する。この情報から、IOCは、そのパッキン
グ・ルーチンを終了し、バイト境界で終わることを知
る。この特徴により、このパケットをその構成パケット
に復元する機能を維持しながら、多数の入力パケットを
１つの隣接出力パケットに圧縮することができる。IOC
は、警告することなく、データを入力から出力に直接送
ったり、データの可能な圧縮比をモニタしながらデータ
を送ることもできる。これらの特徴は、別のレベルの拡
張保護として用いることができる。

CDCセクションは、復元データから圧縮データへの変
換、及び、この逆を実施するエンジンである。このセク
ションは、最大データ・スループットに合わせて調整さ
れた制御、データ経路、及び、メモリ素子から構成され
る。CDCは、２つの12ビット・バスを介してIOCとインタ
ーフェイスする。圧縮時、IOCは、入力バイトをCDCセク
ションへ排出し、そこでコード・ワードに変換する。こ
れらのコード・ワードは、IOCに送られ、バイトをなす
ようにパックされて、チップから送り出される。逆に、
復元時に、IOCは、入力バイト・ストリームをコード・
ワードのストリームに変換し、これらのコード・ワード
をCDCセクションに送って、これらがバイト・ストリー
ムに変換され、IOCに送られるようにする。CDCセクショ
ンは、また、辞書エントリの記憶に用いられる外部RAM
に対して直接インターフェイスする。

CDCは、２つの予約コード・ワードを利用する。第１
の予約コード・ワードは、辞書がリセットされた場合に
はいつでも用いられる。このコード・ワードの発生によ
って、２つのアクションが生じる。すなわち、IOCは、
９ビットのコード・ワードをパックまたはアンパックす
る状態に戻り、CDCは、現在の辞書をリセットし、新し
い辞書の構築を開始する。辞書のリセットは、マイロプ
ロセッサの制御を介してMPIによって、あるいは、自動
リセット回路要素によって要求される。第２の予約コー
ド・ワードは、CDCが新しい辞書エントリを構築しよう
としていて、利用可能な外部RAMを使い果たすと、いつ
でも圧縮時に生成されることになる。この事象は、外部
RAMが十分であれば、めったに生じることはない。ただ
し、メモリの量が減少すると、CDCが遭遇する辞書衝突
が多くなりすぎて、新しい辞書エントリの構築ができな
くなる可能性が高くなる。外部メモリが小さくなり、不
可避的に辞書の衝突が増すと、データ・スループット及
び圧縮性能は、わずかに劣化する。CDCによる復元時に
は、復元プロセスが、圧縮プロセスと同じポイント辞書
エントリの構築を停止することを保証するため、この
“全辞書”コードも用いられる。

次に、第16図に戻ると、データ記憶装置は、コンピュ
ータからの指令に応答して、テープをロード／アンロー
ドし、データ・レコードまたは分離マークを記憶し、デ
ータ圧縮を可能にし、選択された分離マークまたはレコ
ードを探索し、次のレコードを読み返すように構成され
ている。

インターフェイス・ユニット50は、コンピュータから
指令を受けて、装置をコンピュータの間におけるデータ
・レコード及び分離マークの転送を管理するようになっ
ている。コンピュータから指令を受信すると、インター
フェイス・ユニット50は、システム・コントローラ54に
送り、該コントローラは、そのうち、インターフェイス
・ユニット50を介して、もとの指令に従うか否かを表わ
す返答をコンピュータに送り返す。該装置が、システム
・コントローラ54によって、コンピュータからの指令に
応答し、データの記憶または読取りを行なうようにセッ
ト・アップされると、インターフェイス・ユニット50
は、コンピュータとグループ・プロセッサ51の間におけ
るレコード及び分離マークの移送も制御する。

データ記憶時、グループ・プロセッサ51は、必要があ
れば、ユーザ・データを圧縮し、データ・レコードの形
でそれに与えられるユーザ・データを、それぞれ、デー
タ・グループに対応するデータ・パッケージに編成する
ように構成されている。プロセッサ51は、また、各グル
ープ毎に、インデックスと、対応するサブ・コードを構
成するようになっている。読取り時には、グループ・プ
ロセッサは、復元前に、テープから読み取られたグルー
プからデータ・レコード及び分離マークを回復できるよ
うにする逆プロセスを実施する。

グループ・プロセッサ51の形態が、第19図に示されて
いる。グループ・プロセッサ51の中心をなすのは、２つ
以上（例えば２つ）のグループをなすデータ量を保持す
るようになっているバッファ56である。入力データ及び
出力データに対するバッファ空間の割当ては、バッファ
空間マネージャ57によって制御される。プロセッサ51
は、第１のインターフェイス・マネージャ58を介してイ
ンターフェイス50と、第２のインターフェイス・マネー
ジャ59を介してフレーム・データ・プロセッサ52と通信
する。グループ化プロセスの全体的な制御は、記録時に
グループ・インデックス及び関連コードを生成し（機能
ブロック61）、読取り時にサブ・コードを生成する（機
能ブロック62）グループ化マネージャ60によって実施さ
れる。グループ化マネージャ60は、システム・コントロ
ーラ54と協調信号を交換するようになっている。

DCプロセッサDCPは、テープに記憶するためにデータ
を圧縮したり、あるいは、ホストによる読取りのために
データを復元したりする働きをする。制御信号の交換の
ため、DCプロセッサDCPと、インターフェイス・マネー
ジャ58、バッファ56、バッファ空間マネージャ57、及
び、グループ化マネージャ60との間で、相互接続が行な
われている。

グループ化マネージャ60は、また、圧縮データをエン
ティティに編集して、エンティティに関するヘッダー部
分を生成するエンティティ・マネージャ（EM）から構成
される。グループ化マネージャ60及びバッファ空間マネ
ージャ57は、制御コンポーネントであり、テープに書き
込むデータは、それらを介して送られるのではなく、バ
ッファ56からインターフェイス・マネージャ59へ直接送
られる。

記録時に、ホストが、データ・レコードを送り出す
際、インターフェイス・ユニット50は、バッファ空間マ
ネージャ57に対し（インターフェイス・マネージャ58を
介して）、プロセッサ51がレコードを受け取る準備が整
ったか否かを問い合わせる。バッファ空間マネージャ57
は、最初、‘待機’応答を送るが、そのうち、ホストか
らバファ56へのデータ・レコードの転送を可能にする。

データが圧縮される場合（システム・コントローラ54
からの制御信号に従って）、DCプロセッサは、前述のよ
うに、データ圧縮アルゴリズムに基づき、レコード内の
データの一部の代りにコード・ワードを用いる。

データストリームの特定ポイントでの、アクセス可能
なRESETおよびFLUSHコード・ワードの書込みは、簡単な
方法、例えば各レコード後のリセット、などにより指定
することができるならば、DCプロセッサDCPにプログラ
ムすることができる。この他に、あるいは同様に、フォ
ーマットにしたがうRESETおよびFLUSHコード・ワードの
書込みは、システム・コントローラ54により制御するこ
とができ、例えば、各レコードの終わりに自動的に書き
込まれるFLUSHコード・ワード、およびシステム・コン
トローラ54からの信号にしたがって書込まれるRESETコ
ード・ワードがある。

第19図は、‘インライン’システムと呼ぶことがあ
り、ここではDCプロセッサDCPがインタフェース・マネ
ージャ58とバッファ56の間に置かれている。圧縮中に、
データは、インタフェース・マネージャ58からDCプロセ
ッサを通りバッファ56に流れる。復元中に、データは、
バッファ56からDCプロセッサを通りインタフェース・マ
ネージャ56に流れる。インタフェース・マネージャ56と
DCプロセッサDCPとの間に著しいバッファリングはな
い。

システム透視図から圧縮中に“フラッシュ”状態が都
合よく得られる。Ｘバイトが入力し、Ｙバイトが出力す
る。

復元中の同じフラッシュ状態も同様に都合よく得られ
る。Ｙバイトが入力し、Ｘバイトが出力する。これらの
起こることができたり起こらなければならない境界は、
圧縮中のそれと同じである。圧縮中に特別FLUSHコード
・ワードを出力し、復元中の検出されたときにいつでも
フラッシュすることにより、圧縮／復元システムが幾つ
かの利点が得られる。

DCシステムを用いないバッファへの書込みでは、イン
タフェース・マネージャからバッファへのＮバイトの転
送をセットアップおよび完了することが伴う。DCシステ
ムを用いると、これは２回の転送になり、DCプロセッサ
へのＮバイトの転送、およびそこからバッファへのＭバ
イトの転送がある。転送が完了したならば、転送に対応
するすべてのデータをバッファの中に入れることが望ま
しい。したがって、DCシステムをフラッシュしなければ
ならない。

バッファからの読取りでは、バッファからインターフ
ェイス・マネージャへのＮバイトの転送をセットアップ
することが必要である。DCシステムを用いるときには、
バッファ56からDCプロセッサへのＭバイトの転送、およ
びそこからインターフェース・マネージャ58への転送に
なる。転送が完了したならば、再び、DCプロセッサをフ
ラッシュすることが望ましい。

一般に、複数レコードの転送は、レコードがより短か
ければ道理にかなうが、ホストは、１度に１つずつレコ
ードを転送する。

本システムでは、RESETおよびFLUSH機能が分離してい
る。これまでの記述では辞書のリセットについて何も示
唆していないことを書き留めておく。FLUSH機能は、RES
ET機能と全く分離されている。これらを分離することに
より、辞書に影響を及ぼしたり、圧縮比および処理量に
及ぼされるそれ以後の影響もなく、転送間の境界をデー
タに導入することができる。DCシステムは辞書を完全に
作成する前にフラッシュすることができるので、短レコ
ード・システムでさえ完全な辞書を用いることができ
る。非常に優れた圧縮比をもたらす“優れた”辞書が作
成されたならば、それ以上のレコード中に再び作成する
必要はない。RESETとFLUSHとを結合すると、これらの利
点は失われる。

グループ化マネージャ60は、バッファ空間マネージャ
57に接続されており、バッファ空間マネージャ57に対し
て、グループのインデックス区域内に入り込む前に、グ
ループがどれだけのデータを受け入れることができるか
を知らせる。バッファ空間マネージャ57は、最大数のバ
イトを現在グループに転送したか、あるいは、ホストか
ら最後のバイトを受け取った場合には、必ず、グループ
化マネージャに通告する。

ホストから転送される全てをグループ内に納めること
ができない場合、グループの境界に“またがる”と言
う。転送の最初の部分は、１つのグループに納められ、
残りの部分は、後続のグループに納められる。バッファ
空間マネージャ57は、ホストが構築される現在グループ
に納まる量を超えるデータを供給しようとする場合、グ
ループ化マネージャ60に知らせる。またがらなければ、
グループ・インデックスが更新され、グループ化マネー
ジャ60は、別の書込み指令を待つ。またがることになれ
ば、現在グループのインデックスが更新され、そのグル
ープは、テープに対する書込みに利用できる。次のグル
ープが開始され、ホストからのデータは、その新しいグ
ループの始端に直接入り込む。

レコードは、その一部を形成することになるグループ
内における、レコード・データの最終的な位置決めに対
応するバッファ位置へ転送される。レコード・サイズの
情報は、グループ化マネージャ60に送られる。ホストが
分離表示を送ると、これも、グループ化マネージャ60に
対して経路指定される。グループ化マネージャは、分離
マーク及びBORからのレコード・カウントを記憶してお
き、グループのインデックス及び分離カウンタ及びレコ
ード・カウントのサブ・コードの構成時にこの情報を利
用する。インデックスは、グループの終端におけるその
位置に適合するバッファ内の位置に構成される。

並行して、エンティティ・マネージャEMは、圧縮レコ
ード・データを含む、現在エンティティに関するエンテ
ィティ・ヘッダー部分を生成する。ヘッダー部分は、圧
縮されない。エンティティ・マネージャEMは、エンティ
ティ情報を管理する規則を確実に遵守する責任がある。
該規則は、次の通りである。

ａ）： ｉ）グループの始端後、できるだけ早く、 ii）ホストから送られるレコードの非圧縮サイズが、
変化すると、 iii）圧縮アルゴリズムが、変化すると、 新しいエンティティを開始する。

（上記ｉ）及びiii）に関して、アクセス・ポイントの
必要から、新しいエンティティの開始が必要になり、適
合する信号が、グループ化マネージャ60からデータ圧縮
プロセッサDCPに送られる。） ｂ）： ｉ）非圧縮レコードの記憶が必要な場合、 ii）分離マークの記憶が必要な場合、 エンティティを終了する。

各エンティティの形成によってBATエントリがトリガ
される。

グループが一杯になると、新しいグループが開始され
るまで、データ圧縮及びエンティティ構築のプロセスが
停止する。

入力データを圧縮すべきでない場合、データは、不変
のまま、DCプロセッサDCPを通過し、エンティティ・マ
ネージャEMは、非活動状態になる。復元レコードは、エ
ンティティの一部を形成することなく、直接グループを
なすように編成され、レコードに関する情報は、グルー
プ・インデックスに納められる。

グループ（そのインデックス及びサブ・コードを含
む）がアセンブルされると、フレーム・データ・プロセ
ッサ52に転送されて、22の順次フレームの主データ区域
及びサブ・データ区域を構成するブロックに編成され
る。フレームIDに関する情報は、データ・ストリーム内
にある。３フレーム分のデータ量の記憶が可能なフレー
ム・データ・プロセッサ52において、グループ・プロセ
ッサと小形バッファの間には、連続したデータ・ストリ
ームがある。

前述のように、テープに記録されたフレームのグルー
プ間に、１つ以上のアンブル・フレームを挿入するのが
望ましい場合ある。これは、フレーム・データ・プロセ
ッサ52が、グループ・プロセッサ51からの命令によっ
て、あるいは、プロセッサ52がグループ構造を承知して
いる場合には、自動的に、グループの終端にこうしたア
ンブル・フレームを生成するように構成することによっ
て、可能になる。

バッファ56を、２グループに相当するデータを保持す
ることができるようなサイズにすることにより、プロセ
ッサ51の全体の動作では、１つのグループを読み込み、
１つのグループを処理および出力して、できる限り容易
に保つことができる。書込み中には、ホストからのデー
タを用いて１つのグループを作成し、別のグループはテ
ープに書き込まれる。

テープからデータを読み取っている間、グループ・プ
ロセッサ51は、フレーム・データ・プロセッサ52からフ
レーム毎にユーザ・データとサブ・コードを受け取るよ
うになっており、該データは、バッファ56に書き込まれ
て、グループを形成する。次に、グループ・プロセッサ
51はグループ・インデックスにアクセスして、グループ
内におけるユーザ・データの論理的編成（レコード／エ
ンティティ構造、分離マーク）に関する情報、及び、デ
ータが圧縮されているか否かの表示を回復することがで
きる。

データが復元されると、あるいは、データは、圧縮さ
れているが、圧縮形式でホストに読み返されて、ソフト
ウェア復元が施されると、グループ・プロセッサ51は、
インターフェイス50を介してホストに要求されたレコー
ドまたは分離マークを送ることが可能になるが、この場
合、データは、不変のままDCプロセッサDCPを通過す
る。圧縮データのエンティティ・ヘッダー部分は、非DC
ドライブによってホストに送り返され、ホストによって
利用される。

データを圧縮して復元する場合、データは、すでに述
べたようにしてDCプロセッサDCPにより復元してから、
ホストに送られる。

各エンティティからのヘッダ部は、DCドライブで使用
されるが、DCプロセッサDCPに送られない。ヘッダ部の
アルゴリズム番号は、DCプロセッサDCPで用いるアルゴ
リズムと一致しているかどうかがチェックされる。さら
に、エンティティの圧縮レコード数はヘッダ部から得ら
れ、エンティティ・データをDCプロセッサDCPに送ると
きに行われるレコードのカウントダウンをすることがで
きる。

フレーム・データをアセンブルして、１グループ分の
データに戻すのを容易化するため、フレームがテープに
書き込まれる時、各フレーム毎に、グループ内シーケン
ス番号のタグを付けることができる。このグループ内番
号は、例えば、フレームの各トラックの主データ区域に
おける第１ブロックの主データ領域のヘッダーに含まれ
るサブ・コードとして示すことができる。このサブ・コ
ードは、読取りの際、グループ・プロセッサ51に送られ
ると、関連フレームがバッファ56内のどの位置に納めら
れるか判定するために用いられる。

フレーム・データ・プロセッサ52は、機能的に、主デ
ータ区域（MDA）プロセッサ65、サブ・データ区域（SD
A）プロセッサ66、及び、サブ・コード・ユニット67か
ら構成される（実際、これらの機能素子は、適合するプ
ロセスを実行する単一のマイクロプロセッサで構成する
ことができる）。

サブ・コード・ユニット67は、書込み時には、必要に
応じてプロセッサ65及び66にサブ・コードを与え、読取
り時には、プロセッサ65、66からサブ・コードを受け取
って、分配するようになっている。情報の内容に応じ
て、サブ・コードは、グループ・プロセッサ51またはシ
ステム・コントローラ54が生成／要求することができ、
分離マーク・カウント・サブ・コードは、例えば、グル
ープ・プロセッサ51によって判定／利用され、一方、区
域IDサブ・コードは、コントローラ54によって判定／利
用される。いくつかの書込みパラメータのような非変動
サブ・コードの場合、ユニット67にサブ・コードを永久
記憶することもできる。さらに、サブ・コード・ユニッ
ト67自体によって、便宜上、フレーム従属サブ・コード
を生成することも可能である。

MDAプロセッサ65は、関連するサブ・コードと共に、
１フレーム分のユーザ・データを１度に処理するように
なっている。例えば、プロセッサ65は、記録時、ユニッ
ト67からのサブ・コードと共にグループ・プロセッサ51
から１フレーム分のユーザ・データを受け取る。ユーザ
・データを受け取ると、プロセッサ65は、データをイン
ターリーブし、結果得られるデータ及びサブ・コードを
アセンブルして、フレームを構成する２つのトラックに
関する主データ区域ブロックを出力する前に、エラー補
正コードの計算を行なう。実際、ユーザ・データとサブ
・コードのアセンブル前に、データのスクランブリング
（ランダム化）を実施することで、トラック信号のデー
タ内容に関係なく、一貫したRFエンベロープを確保する
ことができる。

読取り時、プロセッサ65は、同じフレームに関連した
２組の主データ区域ブロックに対して逆のプロセスを実
施する。スクランブリングを施していない、エラー補正
を加えた、デインターリーブされたユーザ・データが、
グループ・プロセッサ51に送られ、サブ・コードが、ユ
ニット67によって切り離され、必要に応じて、プロセッ
サ51とシステム・コントローラ54のいずれかに分配され
る。

SDAプロセッサ66の動作は、トラックのサブ・データ
区域に関連したサブ・コードに従って動作し、これらの
サブ・コードをサブ・データ区域ブロックに合成した
り、サブ・データ区域ブロックを分解して、サブ・コー
ドにしたりするという点を除けば、プロセッサ65と同様
である。

信号編成器53は、記録（データ書込み）時に、ATF回
路80からのATF信号と共に、フレーム・データ・プロセ
ッサ52によって与えられる主データ区域ブロック及びサ
ブ・データ・区域ブロックをアセンブルし、各順次トラ
ックに記録される信号を形成するようになっているフォ
ーマッタ／セパレータ・ユニット70から構成される。ユ
ニット70が必要とする場合には、トラック信号に、必要
なプリアセンブル及びポストアンブル・パターンも挿入
される。ヘッド・ドラムの回転に応答してパルス発生器
81の出力が供給されるタイミング発生器71によって、ユ
ニット70の動作とヘッドHA、HBの回転を協調させるタイ
ミング信号が加えられる。ユニットから回線72に出力さ
れるトラック信号は、ヘッド・スイッチ73、それぞれの
ヘッド駆動増幅器74、及び、記録位置にセットされた記
録／再生スイッチ75を介して、ヘッドHA及びヘッドHBに
対し交互に送られる。ヘッド・スイッチ73は、適正に調
時されたタイミング発生器71からの信号によって動作す
る。

再生（データ読取り）時、ヘッドHA及びHBによって交
互に発生するトラック信号は、記録／再生スイッチ75
（この場合、再生位置にセットされている）、それぞれ
の読取り増幅器76、第２のヘッド・スイッチ77、及び、
クロック回復回路78を介して、フォーマッタ／セパレー
タ・ユニット70に送られる。ヘッド・スイッチ77の動作
は、ヘッド・スイッチ73と同じやり方で制御される。こ
の場合、ユニット70は、ATF信号を切り離して、回路80
に送り、主データ区域ブロック及びサブ・データ区域ブ
ロックをフレーム・データ・プロセッサ52に送る働きを
する。プロセッサ52には、クロック回復回路78からクロ
ック信号も送られる。

スイッチ75は、システム・コントローラ54の制御を受
ける。

テープ・デッキ11は、４つのサーボ、すなわち、キャ
プスタン15の回転を制御するためのキャプスタン・サー
ボ82、それぞれ、リール14、15の回転を制御する第１と
第２のリール・サーボ83、84、及び、ヘッド・ドラム12
の回転を制御するドラム・サーボ85から構成される。各
サーボには、両方とも、サーボによって制御される素子
に結合された、モータＭ及び回転検出器Ｄが含まれてい
る。リール・サーボ83、84には、媒体の始端（BOM）及
び媒体の終端（EOM）の検知手段86が連係しているが、
これらの手段86は、例えば、どちらであれ、テープの巻
取りのために駆動されているリール（テープの移動方向
によって決まる）のモータ電流は、BOM/EOMにおけるモ
ータの停動時には大幅に増加するので、モータ電流の検
知に基づくことが可能である。

テープ・デッキ11には、さらに、データ記録時に、テ
ープに対する記録のためのATF信号を発生する自動トラ
ック追従回路80が設けられている。読取り時、ATF回路8
0は、テープから読み取られたATFトラック信号に応答し
て、キャプスタン・サーボ82に調整信号を加え、ヘッド
HA、HBとテープに記録されたトラックとの適正なアライ
メントがとれるようにする。テープ・デッキ11には、ヘ
ッドHA、HBの回転に同期したタイミング・パルスを発生
するパルス発生器81も含まれている。

テープ・デッキ11の動作は、サーボ82〜85及びBOM/EO
M検知手段86に接続されたデッキ・コントローラ87の制
御を受ける。コントローラ87は、サーボに必要な距離だ
けテープを進めさせる働きをする（公称速度または高速
度で）。この制御は、設定されたテープ速度に適した時
間間隔だけサーボに付勢するか、あるいは、サーボに連
係した回転検出器Ｄのうち１つ以上の検出器からテープ
変位情報をフィードバックすることによって行なわれ
る。

デッキ・コントローラ87は、それ自体、システム・コ
ントローラ54が送り出す制御信号によって管理される。
デッキ・コントローラ87は、BOM及びEOMに達したことを
表わす信号をコントローラ54に対して出力するようにな
っている。

システム・コントローラ54は、コンピュータと記憶装
置の間における高レベルの対話を管理し、コンピュータ
が要求するロード／書込み／圧縮／復元／探索／読取り
／アンロードといった基本操作の実施時に、記憶装置の
他のユニットの機能に調整を施すという両方の働きをす
る。この後者に関して、コントローラ54は、デッキ11の
動作と記憶装置のデータ処理部分との調整を行なう働き
をする。

テープ・デッキ11の制御において、システム・コント
ローラは、デッキ・コントローラ87に対し、通常読取り
／書込み速度（Normal）でテープを移動させる要求、あ
るいは、高速度でテープを順方向または逆方向に移動さ
せる要求、すなわち高速送り（F.FWD）または高速巻戻
し（F.RWD）の要求を行なうことができる。デッキ・コ
ントローラ87は、BOMまたはEOMに到達すると、システム
・コントローラ54に報告するようになっている。

次に、復元のためにレコードの位置を突きとめる動作
について、第20A図及び第20B図に関連して解説する。

ホストがレコードを復元するように指令を出すと、コ
ントローラ54は、復元すべきレコードのレコード・カウ
ントに等しい値を備えた探索キーを生成する。現在のレ
コード・カウントは、グループ・プロセッサ51のグルー
プ化マネージャ60に保持されている。次に、テープが高
速度で（通常の何倍も速い）進められ（あるいは、適切
であれば、巻き戻され）、一方、ヘッド・ドラムは、テ
ープに対してヘッドHA、HBの相対速度を一定値に維持す
る速度で回転するが、このモードの場合、300毎に約１
つのトラックのサブ区域を読み取ることが可能である
（ステップ91a及び91b）。トラックのサブ区域の高速読
取りは、既知の技法であり、従って、詳細な説明は行な
わない。

第20A図には、高速順方向探索が示され、第20B図に
は、高速逆方向探索が示されている。

高速順方向探索時には（第20A図）、順次読み取られ
る各サブ区域毎に、各サブ・データ区域ブロックの第２
のパックに保持されたレコード・カウントと探索キー
が、コントローラ54によって比較される（ステップ92
a）。レコード・カウントが、探索キー未満の場合、探
索は続行されるが、レコード・カウントが、探索キー以
上の場合、高速順方向探索が終了し、テープは、高速順
方向読取り間の距離にほぼ等しい距離だけ後退する（ス
テップ93）。この結果、現在、ヘッド・ドラムと向かい
合ったトラックのサブ区域に保持されたレコード・カウ
ントが、必ず探索キー未満になる。

高速逆方向探索時には（第20B図）、順次読み取られ
る各サブ区域毎に、各サブ・データ・ブロックの第２の
パックに保持されたレコード・カウントと探索キーが、
コントローラ54によって比較される（ステップ92b）。
レコード・カウントが探索キーを越える場合、探索は続
行されるが、レコード・カウントが探索キー以下の場
合、高速巻戻しが停止される。

次に、高速正方向および高速逆方向探索では、テープ
はその通常の読取り速度で前進され（ステップ94）、各
連続するグループは次にテープから読み取られ、グルー
プ・プロセッサ51のバッファ56に一時的に記憶される。
各グループのインデックスに保持されるレコード・カウ
ントは、カウントが最初にサーチ・キーと等しくなるか
超えるまで、サーチ・キー（ステップ95）と比較され
る。この時、レコード・カウントをちょうど試験したば
かりのバッファ56のグループに、探索していたレコード
が存在するときに、読み取りが停止する。１つのレコー
ド毎にブロック・アクセス・テーブルにエントリをする
場合には、このグループのインデックスのブロック・ア
クセス・テーブルが検査されて、重要なレコードを識別
し（ステップ96）、最初のデータ・レコード・バイトの
バッファの中のアドレスが計算される（ステップ97）。
その後で、グループ・プロセッサ51は、検索していたレ
コードを見つけたこと、および次のデータ・レコードを
復元および読み込むことができることを、システム・コ
ントローラ54に通知する。すなわち、これはコントロー
ラからさらにホストに通知される（ステップ98）。探索
動作はこれで終了する。

もちろん、他の探索方法を実施することができるの
は、明らかである。

高速で探索中に、テープのデータ区域の境界を越える
と、その検出を行なうため、サブ区域の読取り時には、
必ず、システム・コントローラ54によって区域IDサブ・
コードのチェックが行なわれる。このサブ・コードによ
って、テープのデータ区域を越えて探索が行なわれたこ
とが示されると、テープ方向が逆転し、一般に、低速度
で探索が再開される。分りやすくするため、第20A図及
び第20B図からこの区域IDチェックは省略されている。

関係するレコードの位置を突きとめると、次のステッ
プは、レコード内におけるデータ圧縮にどのアルゴリズ
ムが用いられたかを示す、アルゴリズム番号をチェック
することである。これは、アルゴリズム番号が関連グル
ープのブロック・アクセス・テーブルに記憶されている
場合、該テーブルを調べることによって行なわれる。

アルゴリズム番号が、テープ・ドライブのDCチップ
（または、２つ以上のDCチップがある場合には、その一
方）が用いるアルゴリズムに対応する場合、次のステッ
プは、関係するレコードを含む圧縮オブジェクトの始端
を突きとめることである。これは、特定の記録フォーマ
ットに従って、さまざまな方法で実施することができ
る。

関係するレコードを含む圧縮オブジェクトの始端が見
つかると、復元が開始され、そのレコードの終端にある
FLUSH（または、EOR）コード・ワードに達するまで、続
行される。次に、復元レコードをホストに送ることが可
能になる。レコードの終端におけるFLUSHコード・ワー
ドの存在は、次のレコードの始端からデータの求めなく
ても、レコードの復元が確実に行なえることを表わして
いる。

圧縮レコードがエンティティをなすように編成される
と、関係するグループは、第20A図及び第20B図に関連し
て既述のように位置が突きとめられる。

従って、グループ内におけるエンティティ・ヘッダー
中の＃RECSエントリを用いることによって、関連するエ
ンティティの位置を突きとめることができる。復元は、
関連エンティティ内のアルゴリズムIDエントリをチェッ
クすることにはよって見つけることが可能なすぐ前のア
クセス・ポイントから開始され、そのエンティティ内の
圧縮データが、既に開始された辞書から続いていること
が示されると、アクセス・ポイントが見つかるまで、ス
キップして、前のエンティティ・ヘッダー等に戻る。関
連するレコードから得られる復元データだけしか保持さ
れない。従って、エンティティ・ヘッダーにデータが存
在することには、関連レコード及びアクセス・ポイント
が容易に見つかり、データ管理のプロセスを復元プロセ
スから切り離すことが可能になるという利点がある。レ
コードの圧縮バイト・カウントを含むエンティティにお
いて、各圧縮レコードの後に後書きがあれば、これらの
CBCは、復元時におけるFLUSHコード・ワードのカウント
ではなく（あるいは、だけではなく）、復元データの保
持の開始時点を確認するのに有効に役立てることができ
る。

従って、データ・ストリームにおける補助的情報の存
在は、選択されたレコード・すぐ前のアクセス・ポイン
トを見つけ、復元データを保持すべきポイントを確認す
るのに有効に利用することができる。

該探索手順は、特定の現行レコードを重ね書きするた
めに、新しいレコードを付加するためにポイントを見つ
けるときに同様に用いることができる。

本発明は、ヘリカル走査データ記録に限定されないこ
とが理解される。説明した圧縮アルゴリズムは例として
述べたものであり、本発明は、ユーザ・データから得ら
れる辞書を伴う異なるアルゴリズムにしたがって圧縮さ
れるデータの記憶にも適用することができる。

フロントページの続き (56)参考文献 Ｈｅｗｌｅｔｔ−Ｐａｃｋａｒｄ Ｊ ｏｕｒｎａｌ，Ｖｏｌ．40，Ｎｏ．３, Ｊｕｎｅ 1989，（Ｐａｌｏ Ａｌｔ ｏ，ＣＡ，ＵＳ）Ｍ．Ｊ．Ｂｉａｎｃｈ ｉ ｅｔ ａｌ．：“Ｄａｔａ ｃｏｍ ｐｒｅｓｓｉｎ ｉｎ ｈａｌｆ−ｉｎ ｃｈ ｒｅｅｌ−ｔｏ−ｒｅｅｌ ｔａ ｐｅ ｄｒｉｖｅ”，ｐａｇｅｓ 26− 31 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 5/00 G06F 3/06 301 G11B 20/12 102 H03M 7/40

Claims (10)

(57)【特許請求の範囲】
1. 【請求項１】以下の（ａ）から（ｄ）のステップを設け
   たユーザ・データ圧縮方法： （ａ）複数のレコード（CRn）に組織されたユーザ・デ
   ータのストリームを受信する； （ｂ）受け取ったユーザ・データからコンパイルされる
   辞書を含む第１の記憶手段（Ｗ）およびユーザ・データ
   を受け取り記憶する第２の記憶手段を使用し、前記第２
   の記憶手段に蓄積されたユーザ・データが前記辞書の何
   れのエントリとも一致しなくなるまで、選択されたユー
   ザ・データをコード・ワードに変換することをともなう
   圧縮アルゴリズムにしたがってユーザ・データを圧縮す
   る：このように圧縮されたユーザ・データは圧縮データ
   を形成し、前記アルゴリズムは、第１の記憶手段をクリ
   アして残りのユーザ・データから新たな辞書の生成を開
   始するリセット・ステップ（Ｒ）を含む； （ｃ）前記蓄積されたユーザ・データが前記辞書の何れ
   かのエントリに一致するか否かに関わりなく、前記第２
   の記憶手段に記憶された蓄積ユーザ・データに一致する
   １つまたは複数のコード・ワードを出力して第２の記憶
   手段をクリアするフラッシュ動作（Ｆ）を行う； （ｄ）前記辞書の生成の継起する２つの開始時点の間に
   前記フラッシュ動作（Ｆ）を複数回実行する。
2. 【請求項２】各レコード（CRn）の最後に前記フラッシ
   ュ動作（Ｆ）を実行することを特徴とする請求項１記載
   の方法。
3. 【請求項３】前記フラッシュ動作（Ｆ）の発生する位置
   を示す情報を出力し、それによって前記圧縮データ中で
   のこれらの位置を識別できるようにすることを特徴とす
   る請求項１または２記載の方法。
4. 【請求項４】前記新たな辞書（Ｒ）の生成の開始位置を
   示す情報を出力し、それによって前記圧縮データ中での
   これらの位置を識別できるようにすることを特徴とする
   請求項１から３のの何れかに記載の方法。
5. 【請求項５】以下のステップ（ｅ）及び（ｆ）を設けた
   ことを特徴とする請求項１から４の何れかに記載の方
   法： （ｅ）前記ユーザ・データのレコード構造に無関係に前
   記圧縮データをグループ（Gn）単位で出力する； （ｆ）前記グループ（Gn）の各々の先頭あるいはその近
   傍で前記新たな辞書（Ｒ）の生成を開始する。
6. 【請求項６】前記グループ（Gn）の各々の内の第１の新
   たなレコード（CRn）の先頭で前記新たな辞書（Ｒ）の
   生成を開始することを特徴とする請求項５記載の方法。
7. 【請求項７】以下のステップ（ｇ）及び（ｈ）を設けた
   ことを特徴とする請求項５記載の方法： （ｇ）ユーザ・データレコードをそれぞれが１つまたは
   複数のレコード（CRn）を含むエンティティ（En）に組
   織する； （ｈ） 各エンティティ（En）の最後に前記フラッシュ
   動作（Ｆ）を実行する。
8. 【請求項８】以下のステップ（ｉ）及び（ｊ）を設けた
   ことを特徴とする請求項５記載の方法： （ｉ）ユーザ・データ・レコードを夫々が１つまたは複
   数のレコード（CRn）を含むエンティティ（En）に組織
   する； （ｊ）各グループ（Gn）の第１の新たなエンティティ
   （En）の先頭で前記新たな辞書（Ｒ）の生成を開始す
   る。
9. 【請求項９】以下の（ａ）から（ｄ）を設けたことを特
   徴とするユーザ・データ圧縮装置： （ａ）複数のレコード（CRn）に組織されたユーザ・デ
   ータのストリームを受信するインターフェース手段； （ｂ）選択されたユーザ・データをコード・ワードに変
   換することをともなう圧縮アルゴリズムに従ってユーザ
   ・データを圧縮する圧縮手段：前記圧縮手段は、受け取
   ったユーザ・データからコンパイルされる辞書を含む第
   １の記憶手段（Ｗ）、そこに蓄積されたユーザ・データ
   が前記辞書の何れのエントリとも一致しなくなるまでユ
   ーザ・データを受け取り記憶する第２の記憶手段
   （Ｌ）、及び前記第１の記憶手段をクリアし、残りのユ
   ーザ・データから新たな辞書の生成を開始する手段
   （Ｒ）を含む； （ｃ）前記圧縮手段は、前記蓄積されたユーザ・データ
   が前記辞書の何れかのエントリに一致するか否かにかか
   わりなく、第２の記憶手段に記憶された蓄積ユーザ・デ
   ータに一致する１つまたは複数のコード・ワードを出力
   し、第２の記憶手段をクリアするフラッシュ動作（Ｆ）
   を実行するフラッシュ手段を含む； （ｄ）前記フラッシュ手段は連続する辞書の開始（Ｒ）
   の間で前記フラッシュ動作（Ｆ）を複数回実行するよう
   に構成されている。
10. 【請求項１０】前記フラッシュ手段は、各レコード（CR
    n）の最後に前記フラッシュ動作（Ｆ）を実行すること
    を特徴とする請求項９記載の装置。