(57)【特許請求の範囲】
【請求項１】
データベース・システムであって、
不揮発性メモリに記憶されるべきデータ・レコードを含む入力データ・ストリームと、
各々がデータ・レコードを含む複数の出力データ・ストリームであって、該データ・レコードが該データ・レコード中の識別子に従って各それぞれの出力データ・ストリームについて選択されたものである複数の出力データ・ストリームと、
該出力データ・ストリームの各々を介して該不揮発性メモリに対して周期的に書き込むためのデータを累積するランダム・アクセス・メモリと、
該出力データ・ストリームの各々と関連づけられた現辞書であって、入力データ・ストリーム中のデータ・レコードを圧縮し、および該入力データ・ストリームからの該圧縮されたデータ・レコードを、該現辞書と関連づけられた出力ストリームについて累積されているデータに付加するために各現辞書が維持されており、各現辞書の少なくとも一部分が圧縮された形式にて維持されているような現辞書と、
出力データ・ストリーム中の累積され圧縮されたデータ・レコードを該不揮発性メモリに周期的に書き込む手段と、の組み合わせを含むことを特徴とするデータベース・システム。
【請求項２】
請求項１に記載のデータベース・システムにおいて、
各現辞書が、圧縮される現辞書よりも短い移動辞書を用いて圧縮されるデータベース・システム。
【請求項３】
請求項１に記載のデータベース・システムにおいて、
該現辞書における以前にマッチしなかったデータ系列が、以前に圧縮されたデータ・ストリームにおけるマッチしないデータ系列に対するポインタにより置換されるデータベース・システム。
【請求項４】
請求項１に記載のデータベース・システムにおいて、
現辞書から到達し得る、初期圧縮辞書の部分が主メモリに記憶され、および該現辞書が該記憶された部分および既に圧縮されたデータ・ストリームを用いて再構成されるデータベース・システム。
【請求項５】
データベース・システムであって、
不揮発性メモリに記憶されるべきデータ・レコードを含む入力データ・ストリームと、
各々がデータ・レコードを含む複数の出力データ・ストリームであって、該データ・レコードが該データ・レコード中の識別子に従って各それぞれの出力データ・ストリームについて選択されるものである複数の出力データ・ストリームと、
該出力データ・ストリームの各々を介して該不揮発性メモリに対して周期的に書き込むためのデータを累積するランダム・アクセス・メモリと、
該出力データ・ストリームの各々と関連づけられた現辞書であって、該入力データ・ストリームからのデータ・レコードを圧縮するために、および該入力データ・ストリーム中の該圧縮されたデータ・レコードを、該現辞書と関連づけられた出力ストリームのために累積されているデータに付加するために、各現辞書が維持されており、そして圧縮が進行しても変化しない静的部分と、圧縮が進行するにつれ変化する動的部分とを含む区分けされた形式にて各現辞書が維持されているような現辞書と、
出力ストリームにおける累積され圧縮されたデータ・レコードを該不揮発性メモリに周期的に書き込む手段との組み合せを含むことを特徴とするデータベース・システム。
【請求項６】
請求項５に記載のデータベース・システムにおいて、
各それぞれの現辞書の該静的部分が包括的であり、各他の現辞書について実質的に同一であるデータベース・システム。
【請求項７】
請求項５に記載のデータベース・システムにおいて、
各それぞれの辞書の該静的部分が階層順序で配列された辞書データを含むデータベース・システム
【請求項８】
請求項５に記載のデータベース・システムにおいて、
各それぞれの現辞書の該静的部分が、該現辞書と関連づけられる該出力ストリームについて特有のものであるデータベース・システム。
【請求項９】
データベース・システムにおいて入力データ・ストリームを記憶する方法であって、
不揮発性メモリに記憶されるべきデータ・レコードを含む入力データ・ストリームを受信するステップと、
複数の出力データ・ストリームであって、その各々が該データ・レコード中の識別子に従って各それぞれの出力データ・ストリームについて選択されるデータ・レコードを含むような複数の出力データ・ストリームを生成するステップと、
該出力ストリームの各々を介して該不揮発性メモリに周期的に書き込むためのデータをランダム・アクセス・メモリに累積するステップと、
各々が圧縮された形式にて維持される現辞書であって、各出力ストリームと関連づけられた現辞書を維持するステップと、
該出力データ・ストリームと関連づけられた該現辞書に従って各それぞれの出力データ・ストリームについて選択されるデータ・レコードを圧縮するステップと、
各それぞれの出力データ・ストリームについての圧縮されたデータ・レコードを該出力データ・ストリームについての累積されたデータに付加するステップと、
出力データ・ストリーム中の累積され圧縮されたデータを該不揮発性メモリに周期的に書き込むステップと、を含むことを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、
現辞書を維持するステップが、各出力データ・ストリームと関連づけられる各辞書を圧縮される現辞書よりも短かい移動辞書を用いて圧縮されるステップを含む方法。
【請求項１１】
請求項９に記載の方法において、
現辞書を維持するステップが、
該現辞書中の以前にマッチしなかったデータ系列を、既に圧縮されたデータ・ストリーム中のマッチしないデータ系列に対するポインタにより置換するステップを含む方法。
【請求項１２】
請求項９に記載の方法において、さらに
現辞書から到達し得る初期圧縮辞書の部分を主メモリに記憶するステップと、
該記憶された部分および既に圧縮されたデータ・ストリームを用いて、該現辞書を再構成するステップとを含む方法。
【請求項１３】
入力データ・ストリームをデータベース・システムに記憶する方法であって、
不揮発性メモリに記憶されるべきデータ・レコードを含む入力データ・ストリームを受信するステップと、
複数の出力データ・ストリームであって、その各々が該データ・レコード中の識別子に従って各それぞれの出力データ・ストリームについて選択されたデータ・レコードを含む複数の出力データ・ストリームを生成するステップと、
該出力ストリームの各々を介して該不揮発性メモリに周期的に書き込むためのデータをランダム・アクセス・メモリに累積するステップと、
各出力ストリームと関連づけられた現辞書であって、それら現辞書の各々が、圧縮が進行しても変化しない静的部分と、圧縮が進行するにつれて変化する動的部分とを含む区分けされた形式にて維持される現辞書を維持するステップと、
各それそれの出力データ・ストリームについて選択されたデータ・レコードを、該出力データ・ストリームと関連づけられる現辞書に従って圧縮するステップと、
各それぞれの出力データ・ストリームについての圧縮されたデータ・レコードを、該出力データ・ストリームについての累積されたデータに付加するステップと、
出力データ・ストリーム中の累積され圧縮されたデータを該不揮発性メモリに書き込むステップと、を含むことを特徴とする方法。
【請求項１４】
請求項１３に記載の方法において、
各それぞれの現辞書の該静的部分が包括的であり、各他の現辞書について実質的に同一である方法。
【請求項１５】
請求項１３に記載の方法において、さらに
該現辞書と関連づけられる出力データ・ストリームの期待されるデータ系列に従って、各それぞれの現辞書の該静的部分を選択するステップを含む方法。
【請求項１６】
請求項１３に記載の方法において、
現辞書の該静的部分が階層を含み、現辞書に共通する静的部分の該階層のすべての部分が階層におけるより高いレベルに含まれている方法。
【請求項１７】
入力データ・ストリームをデータベース・システムに記憶する方法であって、
（１）不揮発性メモリに記憶されるべきデータ・レコードを含む入力データ・ストリームを受信するステップと、
（２）複数の出力データ・ストリームであって、その各々が該データ・レコード中の識別子に従って各それぞれの出力データ・ストリームについて選択されたデータ・レコードを含むような複数の出力データ・ストリームを生成するステップと、
（３）出力データ・ストリームについての累積されたデータが所定の量を越える時に、該データ出力ストリームの各々を介して該不揮発性メモリに周期的に書き込むためのデータをランダム・アクセス・メモリに累積するステップと、
（４）各出力ストリームと関連づけられる現辞書を維持するステップと、
（５）該出力データ・ストリームと関連づけられた現辞書に従って、各それぞれの出力データ・ストリームについて選択されたデータ・レコードを圧縮するステップと、
（６）各それぞれの出力データ・ストリームについての圧縮されたデータ・レコードを該出力データ・ストリームについての該累積されたデータに付加するステップと、
（７）出力データ・ストリーム中の累積され圧縮されたデータを、識別子グループとして該不揮発性メモリに周期的に書き込むステップと、
（８）該識別子グループのうちの１つについての圧縮されたデータを周期的に読み出すステップと、
（９）該周期的に読み出された該識別子グループを識別子グループとして圧縮を解除するステップと、
（１０）該圧縮が解除された識別子グループを該ステップ（１）における入力データ・ストリームとして供給するステップと、
（１１）該ステップ（２）ないし（７）を繰り返して、該識別子グループについてのデータを、該不揮発性メモリに記憶するためのより細かい識別子グループに分割するステップと、を含むことを特徴とする方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、レコードが内容に準じてクラスタ又はロケーションで不揮発性メモリに好都合に記憶される、大型データベース・システムなどに関する。
【０００２】
【従来技術】
多くのデータベース・システムは、各々入力レコードをディスク又は他の不揮発性メモリに記憶しなければならない、レコード・データの入力ストリームを包含している。後に、入力データストリームの指定分離部に、普通は、アクセスすることになる。全データが入力ストリームで受信した順でディスクに記憶されるならば、特定の課題、例えば、特定の顧客に属するレコードは、ディスクのランダム・ロケーションに分散することになる。この特定の課題に対応するデータの検索は、ディスクに関して数多くの異なるエリアのシークを要求する。ディスク上のシーク時間は非常に低速（数１０ミリ秒）なので、ディスクが１秒でサポートできる動作の数を制限することになる。
【０００３】
【発明が解決しようとする課題】
特定の課題に対応する全レコードの検索に必要なシーク数を小さくするために、入力ストリームのレコードは、同じ課題に関連するレコードが同じエリアに集中するように、ディスクのロケーションに好都合に記憶されている。そのために、入力ストリームのレコードは、そのディスクの適切な宛先に効果的に送られなければならない。理論的には、この問題は、各々レコードを入力ストリームから、ディスクの幾つかの出力ストリームの中の１つに、レコードに記憶済みのある識別子に基づいて、一定経路で送ることを包含している。
【０００４】
各々レコードをそのディスクの宛先ロケーションに直接送ることは、各々この書込がシークを要求するので、非常に高価になり、これは、システムが処理できるデータ量を大幅に減少することになる。一方で、ページ、又はシークが無いページのシーケンスのように、長く連続するエリアに書き込むと、非常に高速になり、ディスク・システムのほぼ全容量を活用して実行できることになる。本発明の目的は、書込の数を減少して、ディスク・システムに書き込める有効データを増加させ、システム・ハードウェアの限界内でデータ処理容量を増加させる技術を提供することにある。
【０００５】
【課題を解決するための手段】
２つの基本的な手法が本発明に準じて提案される。第１の手法は、主メモリ（ＲＡＭ）のレコードをバッファして、データをディスクに、（ａ）ディスクの特定のロケーションに宛先指定した十分なレコードがディスクに書き込めるだけ集まった時に又は（ｂ）データの宛先を指定したディスクがアイドル状態の時にだけ、書き込むものである。この手法は、非常に数多くの宛先がディスク上に存在する状態で用いる時に、巨大なバッファ・スペースを要求する（例えば、各々がディスクに別個の宛先を有する、数億人の顧客のレコード）。このような大型システムでは、本発明に準じて、出力ストリームが、メモリで圧縮され、十分なデータが累積される時に、すなわち、ページが満杯の時又は数ページのシーケンスの時に、ディスクに書き込まれる。第２の手法では、データは、ディスク上の中間段階エリアのシリーズを介してディスク上のその最終的な宛先に一定経路で送られる。長く連続する書込を用いると、シークの数は、各々レコードがディスクとメモリとの間を数回転送される場合でも減少する。
【０００６】
両方の手法では、単一のデータストリームが非常に数多くのデータストリームに分割され、それらは、次に圧縮され、十分なデータが集まると、ディスクに記憶される。殆どの圧縮演算では、辞書を維持し、辞書を参照しながら辞書に存在するデータストリームの任意の文字列を置換して行われる。単一データストリームだけ圧縮されるシステムの場合、現辞書をメモリに保持することは、圧縮ストリームが辞書と長く比較されるならば、全体的に問題にならない。本発明に準じて、しかし、圧縮されるデータストリームの数が多くて、辞書の数も大きい場合、圧縮に用いる現辞書の全てを記憶するメモリのスペースが重大な問題になる。本発明に準じて、辞書だけでなくデータストリームも圧縮する幾つかの技術について説明される。これらの技術を示す事例について次に述べる。
【０００７】
（１）辞書は、動的移動ウィンドウ２次辞書と、大域になり且つシステム全体に対して一度メモリに記憶できる静的２次辞書とを含むために、区分けできる。静的２次辞書は、階層において低いデータストリームに共通しない２次部をファクタに基づいて除外する階層に配置できる。静的２次辞書は、既知のデータ・シーケンスが現れると思われる特有のデータストリームに対応できる。
（２）圧縮演算は、大きな初期の辞書又は小さな辞書を辞書圧縮のために用いて、辞書に適用できる。
（３）圧縮できない、従って、圧縮データストリームと移動ウィンドウ辞書の両方に後で現れる、マッチしないデータ・シーケンスの冗長性は、マッチしないデータ・シーケンスに代わって、出力ストリームにポインタを挿入することにより、現辞書で除外できる。
（４）後の入力データを圧縮するためにメモリに現辞書を記憶する代わりに、データストリームから現辞書を再構成するために必要な初期辞書の部分だけ、メモリに記憶する必要がある。
【０００８】
本発明に準じるこれらの技術は、分離して又は組み合わせて用いると、多重出力データストリームの圧縮に用いる現辞書のメモリ要求を減少できる。
【０００９】
【実施例】
図１は、レコードに含まれている識別子に準じる、例えば、顧客名に準じるロケーションでディスクにレコードを記憶するバッファ・データベース・システムを示す流れ図である。入力レコードは、種々の識別子に対応してバッファ・メモリに累積され、次に、（ａ）特定のロケーションに宛先指定した十分なレコードがディスクに書き込めるだけ集まった時に又は（ｂ）宛先のディスクがアイドルの時に、ディスクに転送される。ここで、“メモリ”はコンピュータの主メモリ（ＲＡＭ）を意味し、“ディスク”はディスク・ドライブ又は他の不揮発性メモリを意味する。レコードをバッファ・メモリに累積することによって、多くのレコード又はページは、ディスクのレコード・ロケーションのシングル・シークに基づいてディスクに書き込むことができる。
【００１０】
記憶されるレコードを有する入力データストリーム１０は、分類ルーチン１２を通る。分類ルーチンは、入力レコードを、バッファ・メモリ２４〜２７に一時的に記憶される数多くの分離データストリームに分離する。分離データストリームは任意の希望した識別子又は識別子のグループに準じて分離できる。バッファ・メモリの数は分離データストリームの数に依存し、大きなデータベース・システムでは特に大きくなる。分離データストリームは、分類後に圧縮ルーチン１４〜１７で圧縮されて、付随するバッファ・メモリに記憶される任意のデータに加えられる。従って、レコードは、入力ストリームから幾つかの出力ストリームの中の１つに、レコードの識別子に準じて一定経路で送られるので、十分なデータが累積した時に、出力ストリームの累積データは、ディスクのロケーションのシングル・シークに基づいてディスク２０に転送できる。
【００１１】
図２は、入力データが２つもしくは２つ以上の段階で最終ディスク・ロケーションに転送されることを除いて、類似したシステムを例示している。入力データストリーム１０は、識別子のグループに従って分類ルーチン１２において分類されて、レコード・クラスタ３０としてディスクに記憶される。周期的に、レコード・クラスタにおける粗いグループが、ディスクから読み出され、圧縮解除ルーチン３４を通過して、ついで分類ルーチン１２に供給される。この分類ルーチンは、識別子の小さいグループに従ってレコードを分類する。このようにして、分類ルーチンを通る各経路においてレコードがより小さいグループの識別子又は単一の識別子に対応するレコードを含むより細かいレコード・グループ（例えば、細かいレコード・グループ３２）に分離される。
【００１２】
本発明は、更に全体的に応用できるが、広く用いられているウィンドウ設定したＬｅｍｐｅｌ−Ｚｉｖデータ圧縮演算で説明される。Ｌｅｍｐｅｌ−Ｚｉｖ演算は、Ｊａｃｏｂ  ＺｉｖとＡｂｒａｈａｍ  Ｌｅｍｐｅｌが情報理論に関するＩＥＥＥトランザクション、第１巻、ＩＴ−２３、Ｎｏ．３、１９７７年５月に発表した“逐次的データ圧縮のための普遍的な演算”という論文に説明されている。Ｌｅｍｐｅｌ−Ｚｉｖ演算のもとになる考えは、ｋバイトのウィンドウ・サイズを選択し、入力データの最後のｋバイトを用いて、入力データの次の部分をコード化することにある。この入力データの次の部分は、ある閾値より大きいならば、正確なマッチ部が“辞書”として用いられる今のウィンドウに存在する最長の文字列に準じてコード化される。マッチ部が存在する場合、データは、マッチ部の先頭のポインタと、マッチ部の長さを示すインジケータと置換される。マッチ部が存在しない場合、単一の文字がそのまま残る。ウィンドウは、符号化された文字の数だけ進められるので、それは、既に現れた入力の最後のｋバイトに再びなる。
【００１３】
従って、データ圧縮は、ある長さ以下で反復するデータ・シーケンスを検出して行われる。反復するシーケンスが検出されると、シーケンスは、前の発生事象と、反復シーケンスの長さを指摘するポインタと置換される。
【００１４】
Ｌｅｍｐｅｌ−Ｚｉｖ演算の動作が、右側から始まり、左側から右側に移行する、入力データストリーム４０を基準にして図３に図示してある。データストリーム４０のデータの初期ブロックは、ｋバイトの長さで、初期辞書４２を形成している。初期辞書とデータストリームの次のデータとの比較では、位置Ｐ２から始まる辞書の７バイト５４と正確にマッチする、７バイト５２があると想定している。これらの条件のもとで、移動ウィンドウ辞書が前方に７つ移動する。言い換えれば、辞書ウィンドウが前方に進んで前のマッチ部の７バイトを含むことになり、７バイトが立ち下がり端から外れる。ウィンドウがマッチ部のエリアを通過した後に、７バイトが、位置Ｐ２のポインタと長さ７と置換される。
【００１５】
演算はこの方式で継続し、ウィンドウ辞書が、正確なマッチ部の長さに準じて及び移動辞書シーケンスとマッチするデータの代わりに行われた長さ／ポインタ挿入により、データストリームに沿って移動する。例えば、辞書が最初のマッチの結果として７バイトだけ移動した後に、事例では次の１１バイト５６が、移動辞書の１１バイト５８に正確にマッチするものと見なされる。これらの１１バイトは、１１の長さ表示に基づいて、位置Ｐ２７のポインタと置換される。圧縮は、データストリームの末端に達するまで、この方式で継続する。
【００１６】
Ｌｅｍｐｅｌ−Ｚｉｖ圧縮演算が図１と２に示したシステムで用いられる場合、現辞書は、更なる新しい入力データ・レコードを加えるために、出力データストリームの各々に相応してメモリに保持しなければならない。例えば、レコードが数百万人の顧客名に準じて区分けされる大型データベース・システムの場合、多重出力ストリームの各々に関する現辞書は、コンピュータの主メモリに巨大なスペースを費やすと思われる。本発明は、保持しなければならない現辞書に必要なメモリ・スペースを減少するので、入力データを、既に累積されていたデータに追加できる。
【００１７】
図４Ａと４Ｂと４Ｃは、現辞書に必要なメモリ・スペースが辞書を区分けすることによって減少するので、現辞書は、静的部分と組み合わせて、小さい動的部分を含むことができる、本発明に準じる、技術を示している。
【００１８】
図４Ａは、区分けした現辞書が動的２次辞書部分６１〜６３と静的２次辞書部分６４〜６６とを有するシステムを示す。動的２次辞書はＬｅｍｐｅｌ−Ｚｉｖ演算に準じて圧縮のために用いられる。静的２次辞書は、データベースに存在すると推定されるデータ・シーケンスを含んでいて、多重データ・ストリームに共通して用いられる。辞書の静的部分は共通メモリ・ロケーション６０に記憶できるので、現辞書に対するメモリ要求が実質的に減少することになる。静的２次辞書は２次文字列を含んでいて、それは、包括的アプリケーションをもたせるのに適した圧縮される大部分の文字列に存在する。
【００１９】
図４Ａでは、入力データストリーム１０が分類ルーチン１２に進み、それは、入力データ・レコードを非常に数多くの分離データストリームに分類して、付随するバッファ・メモリに記憶する。データストリームは、各々、圧縮ルーチン２４〜２７で圧縮される。動的２次辞書は、圧縮が進むにつれて、Ｌｅｍｐｅｌ−Ｚｉｖに準じて変化するが、静的２次辞書は変わらない。静的辞書の存在が、有効圧縮のために必要な動的辞書のサイズを小さくする。静的２次辞書は全てのデータストリームに対して同じであり、メモリ６０に一度だけ記憶されるので、全ての現辞書の記憶に要求されるメモリも実質的に減少できる。
【００２０】
図４Ｂは、静的２次辞書６７〜６９が各々データストリームに限定されることを除いて、類似の区分けした現辞書を示している。多くのデータストリームが、位置に依存しない、顧客名又は識別子のように、ある内的な共通性を有している。これらが不変の静的２次辞書で捕獲されると、有効データ圧縮が短い動的辞書を用いて実現できる。
【００２１】
図４Ｃは、静的辞書がメモリ７０で階層順に記憶される別の区分け辞書の技術を示す。単純に図示するために、階層辞書７０が３つの２次部分を具備し、その３つの全てがデータストリームの１つに付随する静的２次辞書６４として用いられると想定している。階層２次部の中の２つだけ静的辞書６６に用いられ、１つの２次部だけ静的辞書６６に用いられている。この構成では、静的辞書で共通して用いられない２次部は、各々のレベルでファクタに基づいて除外される。現辞書を記憶するために要求される総メモリ・スペースは、共通メモリにおける静的辞書２次部の共通記憶のために小さくなる。
【００２２】
図５Ａと５Ｂと５Ｃは、現辞書に必要なメモリ・スペースがデータストリームの圧縮に用いる辞書を圧縮すると減少する、本発明に準じる、技術を示す。図５Ａに示すように、圧縮演算は、小さい辞書７４をプロセスで用いると、現辞書７６に適用できる。現辞書は７８に示す圧縮形態で記憶される。この手法を用いる場合に、現辞書は、アクセス時に圧縮を解除しなければならない。従って、スペースと時間の間に妥協が存在することになる。必要な時にだけ追加されるデータストリームの場合に、現辞書自体を圧縮状態に保つことは好都合なことである。
【００２３】
図５Ｂに、マッチしないシーケンスの冗長性が圧縮辞書で除外される、辞書圧縮の別の手法が図示してある。圧縮出力は、滑動ウィンドウ辞書に存在しなかった、マッチしないデータ・シーケンスをしばしば含んでいる。マッチしないデータ・シーケンスが、圧縮データストリームに現れるだけでなく、滑動ウィンドウ圧縮辞書にも後に現れる。従って、マッチしないデータ・シーケンスは、２回、すなわち、現辞書に１回と圧縮出力に１回、現れる。この冗長性は、出力ストリームの部分がメモリに存在する限り、マッチしないシーケンスを出力ストリームのポインタと置換することによって、図５Ｂに示した技術に準じて、除外される。
【００２４】
入力データストリーム８０は左側から右側に移動し、データストリームの初期部が初期辞書８２を形成している。滑動ウィンドウ辞書は、それがデータストリームに沿って移動すると変わる。シーケンスが滑動ウィンドウ辞書のデータ・シーケンスとマッチしてデータストリームに存在する場合、マッチしたシーケンスは、辞書に適したポインタと置換される。例えば、マッチしないシーケンス８４に出会うと、このデータは、圧縮されていない出力を通る。滑動辞書ウィンドウがポイント（ｉ）に達すると、マッチしないシーケンス８８は現辞書８６にも現れる。マッチしないシーケンスがメモリに２回現れるような冗長性は、マッチしないシーケンス８８を出力ストリームでシーケンス８４のポインタ８９と置換すると、本発明に準じて除去される。この構成では、圧縮演算を通ったデータストリームの部分が現辞書の圧縮解除に使用できることが必要である。この問題を防止するために、データがディスクに転送される時に、現辞書は、圧縮が解除され、次に、メモリに残っている出力データストリームの部分だけ用いて再び圧縮される。
【００２５】
図５Ｃは、最も効果的な辞書圧縮を普通は呈する、本発明に準じる、別の技術を示す。入力データストリーム９０は左側から右側に移動し、データストリームの初期部が初期辞書９２を形成している。滑動辞書は、それが出会ったデータに準じてデータストリームに沿って移動するにつれて、変化する。現辞書９４はデータ先行ポイント（ｉ）を有している。現辞書を保存する代わりに、この辞書は、初期辞書９５の記憶部と、次に続く圧縮データストリームとから再び構成される。
【００２６】
現辞書を再構成するために全体の初期辞書を記憶する代わりに、現辞書に対応する圧縮データから（直接的に又は間接的に）到達できる初期辞書の部分だけ保存する必要がある。初期辞書の他の部分は、ブランクで満たすことができるので、現辞書の再構成に影響しない。保持しなければならない初期辞書の部分は、再構成のポイントに対する距離が長くなるにつれて、単純に小さくなる。辞書ウィンドウを１ユニットだけ左側に滑動するには、それを用いて生成した全データがウィンドウ内の又はウィンドウの右側のデータでなければならない。従って、初期ウィンドウのデータに対する任意の通路は、新しいウィンドウを通過しなければならない。ブランクが現辞書の再構成に要求されない初期辞書の部分を満たしている場合、これは再構成に影響を及ぼさない。
【００２７】
【発明の効果】
本発明は、データベース・システムの好ましい実施例に準じて説明されてきた。しかし、本発明は、データ圧縮が包含できる種々の他のアプリケーションにも効果的である。本発明は添付の特許請求の範囲から特に定められる。
【図面の簡単な説明】
【図１】入力レコードがディスク記憶のために累積されるバッファ・システムを示す図である。
【図２】圧縮レコードのディスク記憶が段階的に行われるシステムを示す図である。
【図３】Ｌｅｍｐｅｌ−Ｚｉｖデータ圧縮演算の動作を示す図である。
【図４Ａ】共通の静的２次辞書を含むために区分けした圧縮辞書のセットを示す図である。
【図４Ｂ】圧縮されるデータストリームに限定した静的２次辞書を含むために区分けした圧縮辞書のセットを示す図である。
【図４Ｃ】静的階層の２次辞書を含むために区分けした圧縮辞書のセットを示す図である。
【図５Ａ】小さい辞書を用いて、入力データストリームを圧縮するために用いる辞書を圧縮する技術を示す図である。
【図５Ｂ】辞書の非圧縮データを、データストリームにおいて対応する非圧縮データのポイントと置換して、辞書を圧縮する技術を示す図である。
【図５Ｃ】データストリームと再構成に必要な初期辞書の部分とから現圧縮辞書を再構成する技術を示す図である。
【符号の説明】
１０        入力データストリーム
１２        分類ルーチン
１４，１５，１６，１７  圧縮ルーチン
２０        ディスク
２４，２５，２６，２７  バッファ・メモリ
【図１】
0003592476.tif 000002
【図２】
0003592476.tif 000003
【図３】
0003592476.tif 000004
【図４Ａ】
0003592476.tif 000005
【図４Ｂ】
0003592476.tif 000006
【図４Ｃ】
0003592476.tif 000007
【図５Ａ】
0003592476.tif 000008
【図５Ｂ】
0003592476.tif 000009
【図５Ｃ】
0003592476.tif 000010