JPH0710048B2 - 同一の連続したデータ単位のランを検出し圧縮する方法 - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は、データのランを検出する方法に関するもので
ある。より具体的には、本発明は、データ圧縮に適し
た、前もって指定されたデータのランまたは同一の連続
するデータのランを検出する方法に関するものである。

B.従来の技術 最近のコンピュータは、１つまたは複数の中央演算処理
装置と１つの記憶機構とを含むホスト・プロセッサを必
要とする。プロセッサは与えられた命令に従って、記憶
装置に記憶されたデータを処理する。したがって記憶装
置は、プロセッサが必要とするデータを記憶する能力
と、コンピュータの全体的動作を実行可能にすることの
できる速度でプロセッサにデータを転送する能力を備え
る必要がある。すなわち、コンピュータの記憶装置の費
用と性能は、コンピュータ・システムの商業上の成否に
とって極めて重要である。

今日のコンピュータは大量のデータ記憶容量を必要とす
るので、コンピュータの記憶装置は多くの形で利用可能
である。高速であるが高価な形の記憶装置は、主にマイ
クロチップから構成される主記憶装置である。利用可能
な他の形の記憶装置は周辺記憶装置と呼ばれ、磁気直接
アクセス記憶装置（DASD）、磁気テープ記憶装置、光記
録装置、および磁気または光大容量記憶ライブラリがあ
る。これら他の形式の記憶装置はいずれも、主記憶装置
よりも大きな記憶密度を有し、したがってより安価であ
る。しかし、これら他の記憶装置は主記憶装置が提供す
るような性能は提供しない。たとえば、駆動機構の読取
り書込み機構の下にテープまたはディスクを正しく位置
決めするのに要する時間は、主記憶装置の高速で純粋に
電気的なデータ転送速度とは比べものにならない。コン
ピュータ・システム内の全データをただ１つの形式の記
憶装置に記憶するのは非効率的である。全データを主記
憶装置内に記憶するのは費用がかかり過ぎるし、全デー
タを周辺記憶装置の１つに記憶すると性能が低下する。

代表的なコンピュータ・システムは、主記憶装置と１つ
または複数の形式の周辺記憶装置とを含み、これらをデ
ータ記憶階層に配列する。データ記憶階層は、性能と費
用に関する使用者の要件に合わせて配列される。このよ
うな階層では、主記憶装置はしばしば１次データ記憶装
置と呼ばれ、階層の次の段階は２次データ記憶装置と呼
ばれ、以下同様である。一般に、階層の最高段階は、記
憶密度が最低で、性能と費用が最高である。階層の段階
を下降するに従って、記憶密度は一般に増加し、性能は
一般に低下し、費用は一般に低減する。必要に応じて階
層構造の異なる段階の間でデータを転送することによっ
て、記憶装置の費用が最小になり、性能が最大になる。
したがって、データは、プロセッサがそれを必要とする
と期待される間に限って主記憶装置に記憶される。階層
は、多くの形をとることができ、どれだけの数のデータ
記憶装置や記憶段階を含んでいてもよく、２つの異なる
記憶段階の間で直接データを転送できるものでもよい。
当技術分野で周知のように、データの転送には、入出力
チャネル、制御装置またはキャッシュ記憶装置を使用す
ることができる。

データは、ビットと呼ばれる論理０または論理１とし
て、ディジタル形式で記憶装置に記憶される。ビット
は、システムに対してシステムが理解できる形式でその
データが提示されるように、正確な順序で記憶される
（すなわち符号化される）。たとえば、00000000という
８個のビットの組（またはバイト）は文字“a"を表す。
同様に00000001は“A"を表し、00000010は“b"を表し、
11111111は“＄”を表す。さらに、バイトが実際にどん
な２進データを表すことも可能である。種々の符号化方
式が当技術分野で知られてている。

特定のデータをさらに符号化して、そのデータを保持す
るために必要な記憶装置内の記憶空間量を減少すること
ができれば、データ記憶階層の使用効率が向上する。こ
のようなより進んだ符号化は、一般にデータ短縮または
データ圧縮と呼ばれる（以下では単に「圧縮」と称す
る）。データの繰返し部分を、通常はそれを符号化した
もの（以下では「コード」と称する）で置き換える。典
型的にはデータは特定の形式の記憶装置に記憶される前
に圧縮され、読取り時に圧縮解除されて、処理のためホ
スト・プロセッサによって理解される形式に戻される。
種々の圧縮技法が当技術分野で知られている。異なる形
式のデータ圧縮に関する若干の基礎知識が、米国特許第
3694813号明細書に出ている。

データ圧縮の１つの技法は、同一なデータのランをコー
ドで置き換えるものである。データのランとは、連続し
た一連のデータ単位（すなわちデータの１部分）であ
り、ラン内の個々のデータ単位は連続している。ラン内
の個々のデータ単位は同一である必要はない。たとえ
ば、0101は、４ビットのランである。同一なデータのラ
ンとは、互いに等しい２個以上のランである（すなわち
0101と0101は、それぞれ４ビットの同一なランであ
る）。１個だけの同一なデータのランはあり得ない。す
なわち、互いに同一であるためには、少なくとも２つの
データのランがなければならない。繰り返すことが判明
したデータの各部分に対してコードが割り当てられる。
コードはそれを用いずに記憶された実際のデータよりも
短く、そのランが最初に現れた記憶アドレスを参照する
など種々の方法で、繰返しデータを表す。それ以降でラ
ンが繰り返されるたびごとに、記憶装置内でそのランを
表すために実際のデータの代りに前記のコードを使用
し、それによってこのデータを記憶するのに必要な記憶
容量が減少する。この形式のデータ圧縮の例は、米国特
許第4446516号、第4491934号、第4626824号および第470
1745号の各明細書に出ている。

データ圧縮の別の技法は、データの同一の連続したラン
をコードで置き換えるものである。同一の連続したラン
とはその中の各データ単位が同一であるランを指す。し
たがって、「同一の連続したラン」は、各ランが１個の
データ単位の繰返しから構成されている複数のランを指
す。この用語は複数のランがそれぞれ互いに同一である
ことを意味するわけではない。たとえば、0000と1111
は、それぞれ４ビットの同一の連続したランであるが同
一のランではない。１個だけのデータの同一の連続した
ランは、この用語がそのラン全体を通じて同一であるラ
ンを指すので、存在し得る。前記のコードは、繰り返さ
れるデータ単位と、この単位の繰返しの回数（すなわち
ラン長）とを示す２進データである。たとえば、全ビッ
トが０のバイト78個からなるランは、１個の全ビットが
０のバイトと数78の２進表現によって表現できる。デー
タは、このようにデータの同一の連続したランをコード
で置き換えることによって圧縮される。この形式のデー
タ圧縮の１例は、米国特許第4586027号明細書に出てい
る。

前述の技法は、データをどう圧縮するかに関するもので
ある。データを圧縮できるためには、まず圧縮に適した
データの有無を検出しなければならない。圧縮可能なデ
ータの検出は、データの繰返し部分の検出とその部分が
繰り返される回数の検出とを含んでいる。繰返しの回数
が必要なのは、圧縮の際に、不当に性能を低下させずに
実際に記憶空間が節約されるようにするためである。記
憶空間は常に節約されるとは限らない。ある部分が１回
だけ繰り返され、その部分が非常に短いため、その部分
を表すために用いられるコードがその部分自体よりも大
きい場合には節約されない。また、圧縮と圧縮解除を行
なうためのオーバヘッド（すなわち処理時間）が記憶空
間の節約という利益を上回るならば、記憶空間が多少節
約される程度では労力に値しない場合もある。データ圧
縮に伴うオーバヘッドの一部は圧縮可能なデータの検出
の結果であるので、この検出をできるだけ効率的に行な
うことが重要である。

現在の多重仮想記憶（MVS）オペレーティング・システ
ム環境では、データ機能記憶管理サブシステムと呼ばれ
る１系列のコンピュータ・プログラムを使用してデータ
記憶階層を管理することができる。データ機能データ・
セット・サービス（以下DFDSSと略す）と呼ばれる前記
系列内の任意選択のプログラムを用いて、直接アクセス
記憶装置（DASD）のある態様を管理することができる。
詳細にいえば、DFDSSの機能には、ある形式のDASDから
別の形式のDASDへのデータの移動、データ・セットのバ
ックアップと回復、および自由空間の断片の削減または
除去がある。選択されたデータ・セットのバックアップ
は、通常はDASD上にあるこのデータ・セットを、追加の
記録媒体、通常は磁気テープにコピーまたは「ダンプ」
することによって達成される。DFDSSはデータ・セット
をダンプする際にデータ圧縮を用いる。

データを圧縮するために、初期バージョンのDFDSSで
は、バイト列を探索して圧縮に適したデータを探し出し
ていた。バイト列を検査して、３バイト以上の同一の連
続するランを識別していた。このようなバイトのランを
検出する技法は、システム/370のCOMPARE LOGICAL CHAR
ACTER（論理文字比較）機械語命令を用いて隣接するバ
イトの対を単純比較するものであった。所与のバイト列
が圧縮可能か検査するために、最初の機械語命令で第１
バイトがそれに隣接する第２バイトと比較された。第１
バイトと第２バイトが同一であった場合、その旨が一時
的記憶位置に記録され、第２の機械語命令で第２バイト
がそれに隣接する第３バイトと比較された。第２バイト
と第３バイトも同一であった場合、その旨が再び記録さ
れ、したがって３つ以上の同一の連続したバイトの圧縮
可能なランが存在することがわかった。次にこの手順を
繰り返して、第３バイトとそれに隣接する第４バイト、
第４バイトとそれに隣接する第５バイト、第５バイトと
それに隣接する第６バイトなどが、それぞれ別の機械語
命令によって、同一の連続するバイトのランの終りに達
するまで比較された。ランの終りに達した時、ランが実
際に圧縮された。次に、直前の同一の連続するバイトの
ランの識別中に最後に比較されたバイトの対そのものを
比較する（すなわちその比較を繰り返す）ことから始め
て、新しい同一の連続するバイトのランを求めて探索が
再開された。

前述の例で説明を続けると、第１バイトと第２バイトが
同一でなかった場合でも、第２バイトと第３バイトが比
較された。しかし、同一バイト検出の記録は、それが発
生しなかったため、保持されなかった。第２バイトと第
３バイトが同一であるとわかった場合、その旨が記録さ
れ、前述のように３つ以上の同一の連続するバイトを求
めて比較が続行された。第２バイトと第３バイトが同一
でなかった場合も、比較は続行されるが、同一バイト検
出の記録は保持されなかった。このようにして、バイト
列全体が検査されるまで、比較が続行された。

C.発明が解決しようとする課題 別々の機械語命令で、隣接するバイトの対それぞれをす
べて比較することによって、圧縮可能データを検出する
という前述の技法は非効率的である。必要な機械語命令
の数を減らせる技法があれば効率が改善されるはずであ
る。したがって、あるデータのランを検出する改良され
た方法が求められている。

前記のことを考慮に入れた上で、本発明の主目的は、あ
るデータのランを検出するための方法およびプログラム
を改善することである。

本発明のもう１つの目的は、事前に指定されたまたは同
一の連続するデータ・ランを検出するための改良された
方法を提供することである。

本発明のもう１つの目的は、必要な機械語命令数を減少
させる、前記のデータ・ランを検出するための方法を提
供することである。

本発明のもう１つの目的は、前記のデータ・ランの検出
を含むデータ圧縮のための方法を提供することである。

D.課題を解決するための手段 本発明の前記その他の目的は、ある種のシステム/370機
械語命令の利点を利用することによって達成される。原
始データ列内の隣接するビットの対それぞれに対して、
１個の機械語命令で論理操作すなわち排他的論理和（XO
R）が実行される。前記の操作のために、原始データ・
バイト列がまず一時列にコピーされる。次にこれら２個
の列に対して１個のXOR機械語命令で排他的論理和操作
が実行される。一時列内の第１バイトが原始列内の第２
バイトとXORされ、一時列内の第２バイトが原始列内の
第３バイトとXORされ、一時列内の第３バイトが原始列
内の第４バイトとXORされ、以下同様にしてバイトの比
較データ列が得られる。同一の連続するデータ・ランを
探し出す際、全ビットが０のバイトを求めて比較データ
列が順次探索される。全ビットが０のバイトは、２個の
バイトのXORによって、この２個のバイトが同一である
と決定されたことを示している。この順次探索は、１個
のTranslate and Test（変換後テスト）（TRT）機械語
命令で行なわれる。全ビットが０のバイトが見つかる
と、比較データ列内の後続のバイトが検査される。後続
のバイトがやはり全ビットが０である場合、原始列内に
３個の同一の連続するバイトが見つかったことになり、
これは圧縮可能であると見なされる。バイトの同一の連
続するラン内の次のバイトが、更に探索することによっ
て探し出される。比較データ列内の後続のバイトが全ビ
ットが０のバイトではない場合、次のバイト（すなわ
ち、比較データ列内の前記の後続バイトの次のバイト）
から、全ビットが０のバイトを求めて探索が再開され
る。

E.実施例 具体的に図面を参照すると、同一の番号は様々な図で同
じ特徴または構造要素を表す。様々な形式および能力の
複数の周辺データ記憶装置を有する多重ホスト・プロセ
ッサ・データ処理環境で実施されるものとして本発明を
説明する。少数の周辺データ記憶装置を有する単一ホス
ト・プロセッサ環境でも本発明は実施でき、また多種の
異なるシステム構造と共にでも本発明が実施できること
を理解されたい。

第１図を参照して、多重ホスト環境におけるデータ記憶
階層について説明する。このシステムは、２個以上のホ
スト・プロセッサ（図にはホスト・プロセッサ10とホス
ト・プロセッサ11を示す）を含み、これらは、それぞれ
論理演算機構、主記憶装置、入出力チャネル（第１図に
は図示せず）など、ホスト・プロセッサの通常の構成部
分を含む。各ホスト・プロセッサは単一プロセッサでも
多重プロセッサでもよい。ホスト・プロセッサは、種々
のオペレーティング・システムを使用するが、これは本
発明の理解にとって重要ではない。図のデータ記憶階層
で使用できるホスト・プロセッサの１例は、IBM3090メ
インフレーム・コンピュータである。各ホスト・プロセ
ッサ内に、本発明を使用するコンピュータ・プログラム
があり、その詳細をこれから説明する。

ホスト・プロセッサ10および11は、共通DASD12に接続さ
れている。共通DASD12は高性能ディスク式データ記憶装
置から構成される。共通DASD12には、データ記憶管理プ
ログラムの実行に際してホスト・プロセッサ10と11の動
作を調整するために望ましい制御データ構造（図示せ
ず）が記憶されている。L0 DASDで表した高性能DASD14
は、ホスト・コンピュータ10および11によって直接アク
セスされるデータ・セットを記憶し、ホスト・プロセッ
サ10および11によって生成されたデータ・セットを受け
取ってこれを記憶する。L1 DASDで表した低性能DASD15
は、ホスト・プロセッサ10および11によってアクセスさ
れる頻度が高性能DASD14に記憶されたデータ・セットよ
りも低いデータ・セットを記憶する。DASD14に記憶され
たデータ・セットがホスト・プロセッサ10および11によ
るアクセスを受けずに長時間経過した時は、データ記憶
管理プログラムが自動的にデータ・セットをDASD14から
DASD15に移し、ホスト・プロセッサが頻繁にアクセスす
るデータ・セットのみをDASD14内に保持することによっ
て、ホスト・プロセッサ10および11によるデータ・セッ
トのアクセスを改善する。DASD14および15は、データ記
憶管理プログラムによって生成されるデータ記憶階層の
２つの段階を表す。図のデータ記憶階層に使用できるDA
SDの例は、IBM3380 DASDまたはIBM3390 DASDである。各
DASDはデータ・ボリュームを記憶すると言われる。

データ記憶階層内のさらに低い段階は、MSSで表した大
容量記憶システム（MSS）16、およびTAPEで表したテー
プ駆動装置17で代表される。MSS16およびDASD12、14、1
5は、そこに記憶された全データ・セットへの自動的な
アクセスを提供する。MSS16は記録媒体に対する読取り
および書込みのための１つまたは複数の手段と、MSS16
内にある記憶セルと読取りおよび書込みのための手段と
の間で前記の媒体を転送するための自動化された手段と
を含む。記録媒体は磁気テープ、磁気ディスクまたは光
ディスクでよく、読取りおよび書込みのための手段はテ
ープ駆動装置、磁気ディスク駆動装置または光ディスク
駆動装置でよい。MSS16はその中に記録媒体を挿入また
は取外しするための手段も含むことがある。図のデータ
記憶階層内で使用できるMSSの１例は、IBM3850 MSSであ
る。テープ駆動装置17は、保管用その他の長時間のデー
タ記憶、バックアップなど、ほとんどアクセスされず通
常はテープの取付け取外しに操作員の介入を必要とする
用途に用いられる。図のデータ記憶階層内で使用できる
テープ駆動装置の１例は、IBM 3480磁気テープ駆動装
置である。MSS16内の各ディスク（またはその面）ある
いはテープ、あるいはテープ駆動装置17内の各テープは
データ・ボリュームを記憶する。システム操作員および
システム・コンソールは、図を簡単にするため、第１図
には示してない。

図のデータ記憶階層内で、点線は追加可能なシステム構
成部品を示す。数台のホスト・プロセッサをほぼ図の通
りに階層の各段階の数個のデータ記憶装置に接続するこ
とができる。追加のシステム構成部品を追加できるかど
うかは、各構成部品の接続性のみによって制限される。
図を簡単にするため、チャネルや制御装置などデータ記
憶階層の各段の間にある構成部品は第１図には示してな
い。

主記憶装置を１次データ記憶装置として用い、周辺記憶
装置を２次記憶装置として用いる代表的なコンピュータ
において、プロセッサは、データが主記憶装置内に記憶
されている場合に限って命令を実行するためデータにア
クセスできる。プロセッサの行なう作業がその時点で主
記憶装置内に記憶されていないデータを必要とする場
合、プロセッサは周辺記憶装置から主記憶装置にデータ
を呼び戻しまたは格上げする。必要なデータが記憶され
ている周辺記憶装置が故障すると、プロセッサがそのデ
ータを利用できなくなる可能性がある。このような使用
可能性の喪失を避けるため、複製コピーが異なる周辺記
憶装置上に存在するようにデータを管理することができ
る。ある周辺記憶装置から他の周辺記憶装置にデータを
コピーまたは「ダンプ」することによって、１個の周辺
記憶装置に障害が発生した場合でも、プロセッサはダン
プされたデータを利用できるようになる。

データの使用可能性を管理するためのコンピュータ・プ
ログラム、好ましい実施例では本発明をサブルーチンと
して含むコンピュータ・プログラムは、多重仮想記憶
（MVS）オペレーティング・システム環境内の記憶管理
データ機能であるデータ機能データ・セット・サービス
（DFDSS）である。DFDSSの全般的説明は、IBM解説書SH2
6−4388−１、「データ機能データ・セット・サービ
ス、バージョン２、リリース5.0、使用者の手引き（DAT
A FACILITY DATA SET SERVICES VERSION 2 RELEASE 5.
0,“User′s Guide"）」、およびIBM解説書SC24−4389
−１、「データ機能データ・セット・サービス、バージ
ョン２、リリース5.0、解説書（DATA FACILITY DATA SE
T SERVICES VERSION 2 RELEASE 5.0,Reference）」に出
ている。DFDSSはアプリケーション・プログラムであ
り、ホスト・プロセッサ内に常駐する命令を含む。DFDS
Sはデータ機能システム管理記憶装置（DFSMS）の一部で
ある。DFSMSは、記憶管理サブシステム（SMS）やデータ
機能階層記憶管理プログラム（DFHSM）など、DFDSSと共
に動作し、またはDFDSSと独立に動作する他の機能を含
む。DFHSMは、IBM解説書SH35−0093−04、「データ機能
階層記憶管理機構、バージョン２、リリース5.0、使用
者の手引き（DATA FACILITY HIERARCHICAL STORAGE MAN
AGER,VERSION 2 RELEASE 5.0,“User′s Guide"）」に
説明が出ている。

DFDSSは、通常はMSS16またはテープ17内でデータのコピ
ーを作成することによって、データの使用可能性を保持
する。データをダンプする際に、それぞれの周辺記憶装
置内で使用される記憶空間は、データ圧縮によって最小
になる。前記のデータ圧縮符号化技法は、データ・バイ
トの同一の連続するランをコードで置き換えることを伴
う技法である。どの符号化方法を使用するかは、３バイ
ト以上のデータ・バイトの同一の連続するランだけが圧
縮可能と見なされる点を除いて重要ではない。したがっ
て本発明は、３つ以上のデータ・バイトの同一の連続す
るランをその正確なラン長を含めて検出する。

第２図を参照して、データ圧縮のために同一の連続する
データ・ランを検出するための好ましい実施例に関し
て、本発明の方法を説明する。この方法は、ステップ20
から始まり、任意のバイト数の原始データ列を入力バッ
ファ（第１図には図示せず）内の位置に入れる。列内の
正確なバイト数は、このサブルーチンを呼び出した側が
制御する引数によって決まる。ステップ21で、原始デー
タ列が入力バッファ内の別の位置にコピーされ、それに
よって一時データ列を生成する。後に説明するように、
プログラムの拘束条件によって制限されている場合、原
始列の一部分または「セグメント」だけが一時列として
コピーできることもある。このコピー操作は、セグメン
トの大きさに応じてシステム/370のMOVE（移動）機械語
命令１個で達成できる。好ましい実施例では、原始列の
768バイトのセグメントが一時列としてコピーされる。

ステップ22で、システム/370のXOR命令が、原始列（そ
の第１バイトは除く）と一時列とに作用する。一時列の
第１バイトが原始列の第２バイトとXOR（排他的論理
和）操作され、一時列の第２バイトが原始列の第３バイ
トとXORされ、一時列の第３バイトが原始列の第４バイ
トとXORされ、以下同様である。これは原始列の隣接す
るバイトの対をそれぞれXORすることと等価である。XOR
は、オペランドが同一であれば論理０を返し、オペラン
ドが同一でなければ論理１を返す論理操作である。バイ
トに作用する際、XORはその中の各ビット対（たとえば
各バイトの第１ビット同士）毎の状態に応じて０または
１を１個返す。２個の８ビット・バイトをXORする時
は、その結果も８ビット・バイトである。XORされる２
個のバイトが同一である場合、その結果得られるバイト
は全ビットが０のバイトである。XORされる２個のバイ
トが同一でない場合、その結果生じるバイトは全ビット
が０のバイト以外のなんらかのバイトであり、元のバイ
トの個々のビットの類似性に応じて変わる。８ビット・
バイトの列がXORされる時は、結果は８ビット・バイト
の列であり、各バイトは前述の通りである。この命令の
結果が一時列内にコピーされ、比較データ列と呼ばれ
る。したがって、１個の機械語命令が、原始データ列内
の隣接バイトの対のそれぞれに論理XOR操作を行なった
結果生じる比較列をもたらす。

ステップ23で、１個のシステム/370命令TRTが比較列に
作用する。同一の隣接バイトの対を求めて比較列が探索
される。既に説明したように、同一の隣接するバイトの
対は、比較列内で最初の全ビットが０のバイトによって
示される。探索は順次的である。すなわち探索は、比較
列の先頭から始まり、比較列の末尾に向かって１バイト
ずつ進行し、全ビットが０のバイトが見つかり、それに
よって原始列内のバイトの同一の連続するランの先頭が
示されるまで続行される。したがって、システム/370ア
ーキテクチャの256バイト限界による拘束を除き、同一
の隣接する対に先行する同一でない隣接するバイトの数
がいくつであっても、１個の機械語命令を使って原始列
内で最初の同一の隣接するバイト対を探し出す。

前記のTRT命令は比較列内の各バイトをテーブルに対す
るインデックスとして使用する。比較列内の各バイトの
値は、（ステップ24で示されるように）次の行動を指示
するテーブル内の位置を指す。テーブル内の全ての位置
は、比較列内の全ビットが０のバイトが指すものを除
き、同一の次の行動を指示する。好ましい実施例では、
１個のTRT命令が最高256バイトまでの列に作用すること
ができ、テーブルは長さ256バイトにすぎないが、それ
ぞれの長さは変わることがある。

ステップ24で、ステップ23のTRT命令で比較列内で最初
の全ビットが０のバイトが見つかったかどうかによって
流れが分岐する。比較列内で最初の全ビットが０のバイ
トが識別された場合、流れはステップ25に進んで、比較
列内の次のバイトがやはり全ビットが０のバイトであ
り、比較列内で最初の全ビットが０のバイトによって表
される原始列内の同一の隣接するバイトの対から始ま
る、圧縮可能な同一の連続するバイトのランが存在する
ことを示すかどうかを判定する。比較列全体を探索して
も全ビットが０のバイトが識別されなかった場合、原始
列内にバイトの同一の連続するランが存在しないので、
流れはステップ27に分岐する。ステップ27で、原始列が
入力バッファから出力バッファへコピーされる。例外が
１つあり、全ビットが０のバイトを見つける前にセグメ
ントの終りに達した場合、出力バッファに即座にコピー
することはせず、その代りに次のセグメント内で探索を
続行する。前記の原始列はバイトの同一の連続するラン
を含んでいないため、コピーされたデータは全く圧縮さ
れていない。コピーされたデータと共に記録される制御
コードが、そのデータが非圧縮形式であることを示す。

ステップ25では、原始列内に同一の隣接するバイトの対
が存在することがわかった。前述のように、圧縮可能な
ためには最低３バイトの同一の連続するランが必要であ
る。したがって、ステップ25で、３番目の同一の連続す
るバイトを求めて探索する。これは、システム/370のCO
MPARE IMMEDIATE（即値比較）命令を用いて達成され
る。COMPARE IMMEDIATE命令は１個のバイトにしか作用
できず、列全体に作用できないが、この場合にはこれで
充分である。作用されるバイトが、命令の最初で指定さ
れたバイトと比較される。ステップ25では、COMPARE IM
MEDIATE命令を用いて、検出された最初の全ビットが０
のバイトの直後に続く比較列のバイトを全ビットが０の
バイトと比較する。検出された最初の全ビットが０のバ
イトの直後に続くバイトがやはり全ビットが０のバイト
である場合、原始列内に少なくとも３個の同一の連続す
るバイトがあり、このバイトの同一の連続するランは圧
縮可能である。そこで流れはステップ26に進んで、比較
列内で最初の全ビットが０のバイトによって表される原
始列内の同一の隣接するバイトの対から始まるバイトの
同一の連続するランのラン長を決定する。

次に、検出された最初の全ビットが０のバイトの直後に
続くバイトが全ビットが０のバイトではない場合、（比
較列内で最初の全ビットが０のバイトによって表される
原始列内の同一の連続するバイトの対で始まり、かつそ
れで終わる）原始列内には２バイトだけ同一の連続する
バイトがあり、したがってこのバイトの同一の連続する
ランが圧縮可能ではないことを示す。次に流れはステッ
プ23に戻り、次の同一の隣接するバイトの対を求めて比
較列を探索する。この場合もシステム/370のTRT命令１
個を使用するが、探索は列の先頭から始まるのではな
く、ステップ25が中断した位置から始まる。すなわち、
ステップ25で比較された２個のバイトの直後に続く比較
列内のバイトから探索が始まる。これが可能なのは、ス
テップ25で比較された２個のバイトは同一ではなく、し
たがって再び探索する必要がないことが既にステップ25
で判定されているためである。ステップ23の開始位置
は、比較列の、以前のサイクルで探索済みの部分が探索
されないようにするため、ステップ23ないし25を通じ
て、各後続サイクルで同様に設定される。したがって、
ステップ23ないし25では、原始列のまだ検査されていな
い部分から３バイト以上の同一の連続するランを探すだ
けである。

ステップ26で、バイトの同一の連続するランの末尾が識
別される。これはシステム/370のCOMPARE IMMEDIATE命
令とCOMPARE LONG（LONG値比較）命令を用いて達成され
る。まず、COMPARE IMMEDIATE命令を用いて、比較列内
の次のバイトを同一の連続するランの全ビットが０のバ
イトと比較する。好ましい実施例では、比較列内で全ビ
ットが０ではないバイトが見つかるまで、最大で８回ま
でCOMPARE IMMEDIATE命令を繰り返す。他の実施例で
は、繰返し回数は何回でも良い。繰返し回数の上限に達
した後、COMPARE LONG命令を用いて比較列内の全ビット
が０ではないバイトを探し出す。COMPARE LONG命令は、
データ列の対全体に作用する点を除き、COMPAREIMMEDIA
TE命令と同じである。この場合は、COMPARE LONG命令を
用いて、比較列の残りの部分を同一の連続するランの全
ビットが０のバイトと比較する。レジスタを用いて、比
較される列の開始アドレスと、最後に比較されたバイト
の（列の末尾から数えた）カウントとを追跡する。全ビ
ットが０ではないバイトを識別せずに比較列の末尾に達
した場合、原始列に対して同じ操作を続ける。その場
合、比較列はそのような中断を表す。ただし、原始列内
の全ビットが０ではないバイトを識別することではな
く、同一の連続するラン内の原始バイトと同一ではない
バイトを実際に識別することが目的である。

ステップ27で、原始列の実際に検査された部分が出力バ
ッファに記憶される。原始列の実際に検査された部分と
は、プログラムの流れの中でステップ27に到達した最後
の時以降に３バイト以上の同一の連続するランがあるか
どうか検査された部分である。ステップ27に到達するの
は、前述のようにステップ24で原始列の残りの部分に同
一の隣接するバイトの対が見つからなかったとき、また
はステップ26でこの原始列内で３バイト以上の同一の連
続するランの末尾を見つけた後に限られる。したがっ
て、ステップ26の完了後にステップ27に到達したと仮定
すると、原始列の出力バッファに記憶された部分は圧縮
可能なバイトのランを含んでおり、その前に圧縮不能な
バイトのランがあることもある。

データ・ランはすべて出力バッファ内に記憶されるが、
圧縮可能であると判明したデータ・ランだけが圧縮形式
で記憶される。既に説明したものに加えて、ステップ23
ないし26で使用されるレジスタが、圧縮可能なデータ・
ランの位置および圧縮不可能なデータ・ランの位置を識
別するために使用される。各データ・ランと共に１個の
制御バイトが出力バッファに記憶され、この制御バイト
に続くランが圧縮されているか否かを示し、これによっ
て必要な時にデータの復元を可能にする。好ましい実施
例では、ステップ23ないし26を実施する機械語命令のシ
ーケンス中で３個の記憶レジスタが用いられる。ステッ
プ23で探索される最初のバイトのアドレスが１つのレジ
スタに記憶され、３バイト以上の同一の連続するランが
ある場合、その第１バイトのアドレスが第２のレジスタ
に記憶される。第３のレジスタは、第２のレジスタでそ
の先頭バイトが示されている３バイト以上の同一の連続
するランの末尾の次のバイトのアドレスを保持する。こ
れらのレジスタは制御バイトに必要な情報を計算するた
めに使用される。

ステップ28で、圧縮可能データが存在するかどうか検査
がまだの部分が原始列内に残っているか否かに応じて制
御が分岐する。このようなデータが残っている場合、流
れはステップ23に戻って、比較列内の同一の隣接するバ
イトの対を求める探索が、ステップ27の中断した位置か
ら始まる。すなわち、ステップ26で最後に比較された２
バイトの直後に続く比較列内のバイトから探索が始ま
る。これが可能なのは、ステップ26で比較された２バイ
トが同一ではなく、したがって再度探索する必要はない
とステップ26で判定されたためである。この場合も、ス
テップ23の開始位置は、比較列の、以前のサイクルで既
に探索済みの部分が探索されないように、各後続サイク
ルで同様に設定される。ステップ27の後、原始列内にデ
ータが残っていない場合、ステップ28でプログラムは終
了する。

本明細書で開示されたシステム/370の機械語命令に関す
るより詳しい情報は、IBM解説書SA22−7200−00、「エ
ンタープライズ・システム・アーキテクチャ/370、解説
書（ENTERPRISE SYSTEM ARCHITECTURE/370,“Principle
s of Operation"）」に出ている。

本発明の他の実施例では、この方法およびプログラムを
用いて、前もって指定されたデータ・ランを検出する。
既に説明したステップ20ないし22は変更されないままで
ある。しかし、ステップ23ないし26は、所定のバイトが
見つかった時だけ分岐するように設計された単純なTRT
命令に変更される。たとえば、原始列内で文字“q"と
“u"がこの順で隣接して現れる場合をすべて探し出した
いと仮定する。これらの文字を表す２バイトに対してXO
Rを行なった結果は既知であるが、この結果がTRT命令用
のテーブル内で使用される。原始列全体が探索されるま
で、比較列内で見つかったこの結果の出現がすべて識別
される。より長いデータ・ランは追加のCOMPARE（比
較）命令によって識別できる。識別された出現は、デー
タ圧縮や、ワード・プロセッシングのためにテキストの
大きなブロック内である種の単語を単に探し出すなど、
他の目的に使用できる。

本発明をその好ましい実施例に関して説明してきたが、
本発明の趣旨、範囲および教示から逸脱することなく細
部に種々の変更を加え得ることが当業者には理解されよ
う。たとえば、圧縮可能であるためには、データの同一
の連続するランのバイト数が必ず３以上である必要はな
い。特定のデータ圧縮方式に関連する記憶空間の節約量
とオーバヘッドにより、圧縮が実用的であるために必要
な同一の連続するバイトの正確なバイト数が決まる。ま
た、バイトの代りに個々のビットなどデータ列の任意の
部分を比較することによって本発明を実施することもで
きる。最後に、本発明は、データの使用可能性を保持す
るためだけではなく、データ圧縮が必要ないかなる応用
分野においても、また他の適当な用途にも実施できる。

F.発明の効果 前述の方法およびプログラムは、必要な命令が少なくて
すむため、処理時間が短縮される。XOR命令は、COMPARE
命令とは違って、オペランドの類似性に基づいた直接的
な論理活動をもたらさないが、COMPARE命令が１対の隣
接バイトを対象とするのに対して、XOR命令は１個の機
械語命令でデータ列内のすべての隣接データ・バイトの
対に対して実行することができる。さらに、TRT命令
は、XOR結果の解釈が可能であり、全ビットが０のバイ
トを１個の機械語命令で探し出せる。したがって、一連
のCOMPARE命令の代りに２個の命令ですむ。最後に、同
一の連続するデータ・ランの末尾が見つかった時にわか
る情報の幅を認識することによって、次の同一の連続す
るデータ・ランを求める探索を、最後に比較された２バ
イトからではなく、その直後のバイトから始めることが
可能であり、これによって追加のオーバヘッドが節減さ
れる。本発明は、前もって指定したデータ・ランの位置
を決定するのにも使用できる。

【図面の簡単な説明】

第１図は、本発明が使用できるデータ記憶階層およびコ
ンピュータ・システムの概略ブロック図である。 第２図は、本発明の方法の流れ図である。

Claims (2)

【特許請求の範囲】
1. 【請求項１】処理装置及び記憶装置を有するコンピュー
   タ・システムで一連のデータ単位を有するデータ列内の
   同一の連続したデータ単位のランを検出し圧縮する方法
   であって、 前記一連のデータ単位内の連続したデータ単位よりなる
   対のデータ単位を各対毎に前記処理装置により排他的論
   理和操作し、対内の連続するデータ単位が同一であるこ
   とを示す第１の値か、対内の連続するデータ単位が異な
   ることを示す第２の値のいずれかを有する比較結果を各
   対毎に生成する比較段階と、 前記一連のデータ単位に対する各比較結果を前記記憶装
   置内の対応する一連のデータ単位を有する比較列内に記
   憶する記憶段階と、 前記記憶装置に記憶された前記比較列を前記処理装置で
   探索して、前記第１の値を有する比較結果を探して前記
   データ列内の前記一連のデータ単位内の同一の連続した
   データ単位のランを探し出す探索段階と、 前記探索により探し出された前記データ列内の前記一連
   のデータ単位内の少なくとも所定のラン長を有する同一
   の連続したデータのランを前記処理装置により圧縮する
   圧縮段階と、 よりなる方法。
2. 【請求項２】前記探索段階は、 最初の同一の連続したデータ単位の対が見つかるまで前
   記比較列を前記処理装置で調べることにより各対の連続
   したデータ単位が同一であるか否かを判定する段階と、 前記最初の同一の連続したデータ単位の対に続く最初の
   同一でない連続したデータ単位の対が見つかるまで、前
   記比較列を前記処理装置で調べることにより前記最初の
   同一の連続するデータ単位の対に続く連続するデータ単
   位の各対内のデータ単位が同一であるか否かを判定する
   段階と、 前記２つの判定段階を連続的に反復して前記データ列内
   の同一の連続したランの各々を見つけだし、該反復を、
   いずれのデータ単位も最後に見つけだされた同一の連続
   したデータ単位のラン内に含まれていないような最初の
   連続したデータ単位の対内のデータ単位が同一であるか
   否かの判定で開始し、前記データ列の終わりに達したと
   きに終わらせる段階と、 を更に含む請求項１記載の方法。