JP3935952B2 - 頻度の高いキャラクタの組み合わせ、ワード及び／又はフレーズでプレフィルした辞書を用いるＬｅｍｐｅｌ―Ｚｉｖデータ圧縮技術 - Google Patents

Description

発明の背景
技術分野
本発明は、デジタル形式で格納したテキストデータをロスの無い方法で圧縮（compression）しかつ伸長（decompression）するための方法および装置に関する。換言すれば、オリジナルデータは最初圧縮されその後伸長処理を経て、そのオリジナルの形式に再構成される。このデータは、キャラクタのある特定セットの７または８ビット表現からなる、例えばＡＳＣＩＩコードの様に、予め特定された特定のアルファベットで記述されているものと仮定する。
従来技術の記載
従来技術において、異なるタイプの多くのテキスト圧縮技術が記載されている。ここに説明するテキスト圧縮技術は、LempelとZivによって開発されたテキスト圧縮技術こ基づいている。彼らはテキスト圧縮に対して２種類の、類似しているがしかし重大な相違点を有する技術を開発した。これら２種類の方法は、IEEE Transactions on Information Theory, Vol. IT 23, No. 3, pp. 337-343に記載の“A Universal Algorithm for Sequential Data Compression”と題された論文、およびIEEE Transactions on Information Theory, Vol. IT-24, No. 5, pp. 530-536に記載の“Compression of Individual Sequences via Variable-Rate Coding”と題された論文にその概略が記載され、さらに通常、それぞれＬＺ７７およびＬＺ７８として呼ばれる。
ＬＺ７７は、あたらしい材料を圧縮するために、固定サイズのウインドウ内に前もって圧縮された材料に対するポインタを使用する、テキスト圧縮技術である。固定サイズの“圧縮ウインドウ”は、局所性の原理、即ちそのデータが隣接のデータに最も類似していそうな事を見出すために圧縮される間、テキストデータに渡って移動させられる。以下にＬＺ７７の一例を、図１（Ａ）および（Ｂ）に関して説明する。
図１（Ａ）および（Ｂ）では、説明目的のために、８キャラクタの小さなウインドウサイズを仮定している。図１（Ａ）に示す様に、まだ圧縮されていないテキストは、このまだ圧縮されていないテキストに直接先行する圧縮されたテキストの８（までの）キャラクタを含む、８（までの）キャラクタウインドウの内容と比較される。まだ圧縮されていないテキストの最初から始まる、８キャラクタウインドウ内のシーケンスとの最も長い一致が識別される。図１（Ａ）において、８キャラクタウインドウからの最も長い一致は、“ＢＢ”である。このシーケンス（“ＢＢ”）に対するポインタ、その長さ（２）およびイクステンション（圧縮すべきテキスト中の一致の後における、次のキャラクタ）は、データ圧縮アルゴリズムの適用に依存して、送出されあるいは圧縮されさらに局所的に格納される。しかしながら８キャラクタウインドウ内にシーケンスの一致が見いだせない場合は、そのキャラクタそのものが送出される。一旦、ポインタによって指摘されたデータブロックが圧縮されかつその圧縮に関する情報が送出されると、そのウインドウは、ポインタ（ＢＢ）プラスもし有ればイクステンションによって言及されるキャラクタ数だけ移動させられる。更に、圧縮されるテキストの領域に対するポインタは、このキャラクタ数だけ更新される。図（１Ｂ）に示すように、この処理は、シフトされたデータに対して、圧縮されるデータが空になるまで繰り返される。
ＬＺ７８は、圧縮されるデータを圧縮辞書内に書き込むためのフレーズに分解することよって、テキスト圧縮を達成する点で、ＬＺ７７と相違している。これらのフレーズまたは辞書エントリに対するポインタは、次に新しいデータを圧縮するために使用される。最初、辞書は空の列（長さがゼロのフレーズ）のみを含んでいる。各ステップにおいて圧縮すべきフレーズは、このフレーズのプレフィックスが辞書中のエントリで有るように、新しいデータのスタートの時点で最も長いフレーズである。なおこのプレフィックスは、最後のキャラクタを取り除いたフレーズとして定義される。残りのキャラクタはイクステンションと呼ばれる。このように、第１のフレーズが発見されると、この第１のフレーズは、そのフレーズの最後でかつ唯一のキャラクタに続く空の列（これは辞書において最初に見いだされる唯一のエントリである）からなる辞書エントリに対するリファレンスとして、符号化される。このキャラクタは次に辞書中に配置され（辞書が満杯でないと仮定して）、更にフレーズを識別する処理およびそのプレフィックス（そのプレフィックスに一致する辞書エントリに対するリファレンスとして）およびイクステンションを送出する処理を繰り返す。そのまだ圧縮されていないデータは、辞書エントリの両方、すなわち：空の列および既に遭遇したキャラクタからなるフレーズ、と比較される。新しいデータ中の次のキャラクタが既に圧縮されたキャラクタと一致しない場合は、次にそれもまた空の列プラス圧縮されるキャラクタとして、圧縮される。この方法では、辞書中に発見されかつ可能な限り長く選択されたプレフィックスと、入力データのプレフィックスに続くキャラクタであるイクステンションとして、データの各フレーズが圧縮される。ＬＺ７８の一例を次に図２を参照して説明する。
図２は、短いキャラクタシーケンスに対するＬＺ７８圧縮の例を示す。図示するように、Ｅとして呼ばれる空の列を除いては、辞書は最初エントリを含まずにスタートし、圧縮すべきキャラクタシーケンスの開始を示すポインタは、圧縮すべきシーケンスの開始点に配置される。フレーズのプレフィックス、即ちＥが辞書中の唯一のエントリであるため、プレフィックスが辞書中に存在する最も長い最初のフレーズは、１キャラクタの長さである。最初のキャラクタは従って、Ｅ及び送出されるシーケンスの第１キャラクタに対するリファレンスとして符号化される。その後、この辞書は更新されて、使用された辞書エントリおよび圧縮シーケンス中でこのエントリに続くキャラクタとの連結からなるエントリを含むようになる。現在のポインタは次に圧縮されるキャラクタの数だけ移動させられ、さらにこの処理を繰り返し、圧縮すべきデータストリームが空になるまで次のフレーズを繰り返して識別しかつその圧縮された形状を送出する。当業者であれば理解しうるように、一旦辞書が形成されると、ＬＺ７８技術は実質的により強い圧縮を提供する。ＬＺ７８テキスト圧縮技術の特定の実施に関するさらに詳細な説明が、Eastman等の米国特許第４、４６４、６５０号に示されており、一方、Lempel-Zivコード技術の一般的でかつ優れた記載は、Bell等による「テキスト圧縮」（Englewood, Cliffs, New JerseyのPrentice Hall社より１９９０年発行）と題された教科書において見られる。
Lempel-Zivによって記載された様に、圧縮辞書の概念を用いた多くのデータ圧縮システムが従来技術において記載されている。
例えば、Giltner等は、米国特許第４、３８６、４１６号において、テレックスまたは類似のネットワーク上でデータを送出するために使用されるシステムを記載している。Giltner等によって記載されたシステムは２種類の辞書を使用している。第１の辞書は、データ言語からの頻出ワードによってプレフィル（pre-filled）されており、一方第２の辞書は最初空であるがデータ中に遭遇しかつ第１の辞書に存在しないワードによって満たされる。データを送出する場合、ワードが第１の辞書中に発見されると、エスケープコードと第１の辞書中のワードエントリ数が送出される。ワードが第１の辞書中に発見されない場合は、Huffmanコード技術を用いて圧縮されて後の利用のために第２の辞書の中に加えられる。その結果、そのワードに再び遭遇すると、このワードは、第２の辞書中のワードエントリ番号が、第２の辞書中のワードエントリ番号の後の第２の辞書を言及する事を示すエスケープコードを送出する事によって送出される。Giltner等は、“ワード”を、予め決められた数のキャラクタまたは空白あるいは空白と句読点との組み合わせによって囲まれたキャラクタシーケンスのいずれかであると定義している。テレックスまたは類似のネットワークによって扱われる全てのタイプのメッセージに共通する小さいがしかし固定数のワードを第１の辞書中に設け、さらに追加の“ワード”を第２の辞書中に格納する。しかしながら、Giltner等は、有効ワードの限定された定義外である頻繁に発生するテキストシーケンスについて触れてはいない。その結果、Giltner等は、テキスト間の圧縮がキャラクタシーケンスのレベルでなされた場合、テキストの類似性がより大きいという事実を利用してはいない。さらに、Giltner等は、テキスト中に頻繁に発生するワードを第１の辞書に対してどのように選択しその結果送出されるテキストタイプ内で頻出する有効ワードによってその辞書が満たされるかについて、触れていない。Giltner等はまた、最も適当なテキストライブラリをいかにして識別するか、または圧縮すべきドキュメントのジャンルの識別について、教示していない。さらに、Giltner等のライブラリは固定されており、ユーザは必要に応じて彼等自身のプレフィル辞書を作る事はできない。
同様に、Wengは米国特許第４、８８１、０７５号において、２種類の辞書を用いる“適応”データ圧縮技術について記載している。第１の辞書は、圧縮または伸長を実行するために使用され、一方第２の辞書は最近に入力されたデータの局所性をうまく反映させるように再構築される。第２の辞書は次に入力データを圧縮しまたは伸長するために使用され、一方第１の辞書は直近の入力データを用いて再構築される。Wengは圧縮が完了するまで、辞書間で繰り返し切り替えを行っている。
Kato等は、米国特許第４、８４７、６１９号において、適応圧縮技術の修正版について記載しており、ここでは圧縮システムにおける圧縮度をモニタし、圧縮度がしきい値以下になった場合辞書をリセットしている。辞書が早まってリセットされる事を防ぐために、辞書が十分に満たされるまでリセットの発生は許可されない。この技術はＬＺ圧縮技術またはその他の適応技術に関連して使用することができる。
米国特許第５、１５３、５９１号において、ClarkはLempel-Ziv圧縮アルゴリズムに対する修正版を記載しており、ここで辞書はツリーデータ構造として格納される。これによって、米国特許第４、４６４、６５０号に記載された本来の実施形態における場合よりもさらに少ない空間で大きな辞書を格納することが可能である。さらに、これによってこれらの辞書をより簡単にまたすばやく探索することができる。
米国特許第５、２４３、３４１号において、Seroussi等は、２種類の辞書を使用するLempel-Zivの変形版を概略的に示している。第１の辞書は満杯となるまで使用され、次にこの辞書は待機辞書によって置き換えられ、この待機辞書は圧縮が続く前に最上の圧縮を与える、第１の辞書からのエントリによって満たされる。
本来のLempel-Ziv圧縮技術に対するその他の多くの修正版が、従来技術において示されている。
例えば、Welchは米国特許第４、５５８、３０２号において、Lempel-Ziv法の実行について記載している。この中では、符号化および複号化処理においてより簡単な計算しか必要とせず、そのためEastman等による特許第４、４６４、６５０号に記載された実行方法よりも早い。
Miller等は米国特許第４、８１４、７４６号においてLempel-Zivアルゴリズムに対する幾つかの修正版を示唆している。これらの修正版の第１は、圧縮を実際に始める前に辞書中に全ての可能なキャラクタを含ませる事である。その結果、次のデータがポインタよりもむしろキャラクタで有る事を示すフラッグを送出する必要が無い。さらにMiller等は、辞書が満杯になってきた場合、あまり最近では使用されないエントリの除去を容易にするために、タイムスタンプを各辞書エントリに結合している。これらの修正は、辞書を固定サイズに限定する事によって必要なメモリを減らし、辞書が圧縮するデータの現在の特性をより正確に反映する事を可能にする事によって、圧縮をより向上する事を目的としている。
Storerは、米国特許第４、８７６、５４１号において、従来のLempel-Ziv技術における困難さの幾つかを回避する圧縮技術について、記載している。特に、Miller等による米国特許第４、８１４、７４６号においてと同様に、圧縮辞書は最初アルファベット中の全てのキャラクタを含んでいるので、符号化されていないキャラクタを送出する必要がない。さらに、辞書があまり必要性のないエントリを追放する事が出来るように、最近においてほとんど使用されていないキューを維持する。Storerのシステムにおける辞書の符号化および複号化は、そのサイズが変化し、一度に数個のアクティブが存在しうる。各辞書の圧縮率がモニタされ、そして最良の圧縮を提示するものが使用される。
米国特許第４、９０６、９９１号において、Fiala等は置換スタイルのデータ圧縮技術について記載しており、これは幾分Lempel-Ziv圧縮に類似している。彼等の技術は固定キャラクタウインドウ（例えば４０９６キャラクタ）を探索する事によっており、このキャラクタは圧縮されるテキストがウインドウ内のある位置に対するポインタとして符号化されうるか否かを決定するために、すでに圧縮されている。圧縮されるテキストがこの方法で符号化されうるならば、スタート位置に対するポインタが、圧縮されるテキストとウインドウ内の位置間の重なりの長さと共に、生成される。もしこの方法で圧縮されるテキストが符号化できないならば、その長さのキャラクタ列後の長さとして符号化される。ＬＺ７８圧縮と同様に、ウインドウが圧縮を生じさせるために指摘されるはずの列をもたないので、この技術はドキュメントの初期においてデータを多く圧縮する事ができない。
O'Brienは、米国特許第４、９８８、９９８号において、キャラクタの繰り返しが長い列を含むデータ圧縮を強化することを可能とするLempel-Zivアルゴリズムの修正版について示唆している。Lempel-Zivアルゴリズムは、現存の辞書エントリに単一のキャラクタを添付する事によって、圧縮辞書にエントリを加えているので、このようなキャラクタ列が辞書中に発見される前に、多くの繰り返しキャラクタ列を必要とする。従ってO'Brienは、ランレングス（run-lengths）をテキスト中に挿入するランレングス符号化技術を用いて、データをプレ処理している。テキストと繰り返しキャラクタに対するランレングスとの組み合わせの結果は、次にLempel-Ziv技術を用いて圧縮される。
米国特許第５、０４９、８８１号において、Gibson等は、すでに処理されたキャラクタシーケンスから自身のポインタを生成し、データ速度と圧縮率の積を最大化することを強調する、データ圧縮システムについて記載している。このようにして、すでに入力したデータは辞書として使用され、さらに列一致テーブルを必要とすることなく、列一致のための候補を発見するために、ハッシングアルゴリズムと結合されている。
米国特許第５、０５８、１３７号において、Shahは、コードワードとデータを別々に格納するためのメモリを有するLempel-Zivデコーダについて記載している。コードワードを受信する事によって、このデコーダは、すでに受信したコードワードを格納し、新しく受信したコードワードをコードワードメモリに印加して、新しく受信したコードワードとさらにプレフィックスと関連した別のコードワードによって表現されるデータの一部である、最後のデータ要素の位置を獲得する。最新のコードワードの複号化を完了すると、複号されたワードの最初のデータ要素はその直前に受信したコードワードに添付され、その組み合わせが、すでに受信された最も高いコードワードのすぐ後のコードワードに等価なものとして、格納される。符号化および複号化の間において、少なくとも一個のメモリが共有される。
米国特許第５、０８７、９１３号において、Eastmanは、全ての先行する部分を伸長する必要なく、データの後半部分の伸長を可能とするために、探索ツリーデータベースを使用する、Lempel-Zivアルゴリズムについて記載している。探索ツリーデータベースは、予め決められた固定サイズに成長させられ、それ以降の成長は許可されない。圧縮探索ツリーデータベースが伸長に先立って形成されるという事実によって、データの先行する全体部分を伸長することなく、データの一部分を伸長する事が可能となる。
米国特許第５、１４０、３２１号において、Jungは、圧縮の減少を犠牲にして、圧縮速度を強化することを可能とした、Lempel-Ziv変形版の詳細を示している。データの圧縮部分全体において最適一致サブ列を見出すよりもむしろ、局所性原理を利用し、ファーストインファーストアウトバッファにおける最近の圧縮データを一致シーケンスを見出すために調査する。最近圧縮された列を格納するため、および一致列のすばやい検索を可能とするために、ハッシュテーブルを用いる。
米国特許第５、１７９、３７８号において、Ranganathan等は、データ記号の可変数から固定長コードワードを形成する事によって、処理能力を向上するために、プロセッサの短縮アレイを用いたLempel-Zivの実行方法について記載している。
米国特許第５、２６２、７７６号において、Kutkaは、通常の圧縮処理において必要とされる探索ステップを取り除くために、ツリーデータ構造を利用したLempel-Zivアルゴリズムの実行方法について記載している。プライマリシーケンスにおけるシーケンス要素は、エスケープシーケンスを用いて削減要素セットにおける要素に変換される。この技術は、画像の離散的コサイン変換の係数をあらわすデータを圧縮する場合に、特に適している。
特許文献に記載されているLempel-Ziv圧縮技術についての上述の変形例に加えて、その他の例が技術誌において見ることができる。
例えば、Rodeh他による「列の一致を介したデータ圧縮のための線形アルゴリズム」（“Linear Algorithm for Data Compression via String Matching”）には、ウインドウのサイズが固定されないＬＺ７７技術が記載されている。この技術によれば、データの圧縮部分における以前の列へのポインタは長さ方向に増大し、可変長コードにエンコードされる。
Bellによる「好適なＯＰＭ／Ｌテキスト圧縮」（“Better OPM/L Text Compression”）には、プレフィックスと拡張の組合せを使用して圧縮していないＬＺＳＳに言及したLempel-Zivの変形例が記載されている。一方、ポインタを送出するコストが１つのキャラクタ又は一連のキャラクタを単に送出するコストよりも高いならば、１つのキャラクタ又は一連のキャラクタが送出される。この場合、２進検索ツリーが最も長い列の一致を見出すために使用される。
Welshによる「高性能データ圧縮技術」（“A Technique for High-Performance Data Comression”）には、ポインタとキャラクタとの組合せよりもむしろ以前に圧縮されたデータへのポインタのみが使用されるＬＺ７８への修正版を開示している。列テーブルは入力されたキャラクタ列を固定長コードにマップするように構成される。テーブル上の各列に対して、そのプレフィックス列もまたテーブル上にに設けられる。列テーブルには、圧縮されたメッセージ内には以前に出現した列をも包含する。メッセージ内の列の実行サンプルで構成されるため利用可能な列はメッセージの統計を反映する。この技術はＬＺＷとして一般に呼ばれている。この技術では、入力列では一回の通過においてキャラクタが連続的に調査され、かつ最も長く認識された入力列は各時間ごとに除外される「グレーディパーシングアルゴリズム」（“greedy”parsing algorithm：貧欲分解アルゴリズム）を使用する。そして列テーブルに加えられた列はこの解析により決定される。
Miller及びWegmanによる“Variation on a Theme by Ziv and Lemple”には、ＬＺ７８の他の変形例が記載されている。このバージョンでは、辞書は長さ１（即ち、圧縮が生じるアルファベット上の全ての文字）の全ての列により前もって埋められており、この長さ１は縮小の一助にはなるが、有用なエントリが欠落した辞書としてスタートする問題を除去していない。又、辞書が満杯された時に圧縮をリセットするよりも、最も最近使用した辞書から列を除去することを提案している。しかしながら、ＬＺＭＷとして呼ばれているこのバージョンの最も大きな利点は、拡張が決して送出されないことである。むしろ、辞書は長さ１の全ての列でスタートするので、初期の辞書を使用して全てのデータをエンコードすることができる。しかしながら、これは結果的に圧縮されないことになる。一方、辞書は、以前の２つの一致の結び付きからなる辞書にエントリーを加えることにより増大する。
図３には、ＬＺＭＷ圧縮の例を示す。アルファベットは、図示のために３文字（Ａ，Ｂ，Ｃ）のみ含むものとする。図示のように、圧縮辞書は初期ではアルファベット文字を含む。圧縮が開始されるキャラクタへのポインタは、圧縮される一連のテキスト最初のキャラクタに置かれる。辞書内の最も長い一致が見い出されかつこのエントリへのポインタが送出される。一方、ポインタは圧縮アルゴリズムの適用に依存して部分的に格納される。ポインタは送出されるキャラクタ数により移動される。通常、辞書は、以前に送出された２つの辞書エントリの結び付きを含むように更新されるが、しかし、以前の送出がなかった場合にはこのステップはスキップされる。処理サイクルを経て第２の繰り返しにおいて、最も大きな一致が見い出され、その辞書エントリ番号が送出され、ポインタが適当なキャラクタ数により移動され、そして送出された２つの以前の辞書エントリの結び付きが新たなエントリとて辞書に加えられる。この処理は圧縮されるべきデータが無くなるまで繰り返される。
一般に使用される圧縮アルゴリズムはＬＺ７７及びＬＺ７８アルゴリズムの変形例に使用する。例えば、市場で入手可能な“ｚｉｐ”及び無償で入手できる“ｇｚｉｐ”に使用される圧縮アルゴリズムは、入力データにおいて写された列を見出すＬＺ７７の変形例である。“ｇｚｉｐ”では、２番目に出現する列はポインタにより対（距離、長さ）の形式で以前の列に置き換えられる。列が、指定された距離、例えば３２Kbytes、の範囲にて、それ以前のバイト数において何処にも出現しないときは、一連の文字バイトとして送出される。文字又は一致の長さは他のツリーと共に圧縮される。ツリーは各ブロックの開始時にコンパクトな形式で格納される。ブロックは、１つのブロックに対して圧縮されたデータが利用可能なメモリに合わねばならないことを除いて、如何なるサイズをも持つことができる。“ｇｚｉｐ”が、新たなツリーと共に他のブロックをもスタートさせるためにに有用であることを決めたときは、ブロックは送出される。写された列はハッシュテーブルを使用して見出される。長さ３の全ての列はハッシューテーブルに挿入され、ハッシュインデックスは次の３バイトに対して計算される。もしこのインデックスに対するハッシュチエン（hash chain）が空でないときは、チエンにおける全ての列は現在入力されている列と比較され、最も長い一致が選択される。ハッシュチエンは、最も最近の列のスタートと共に、最も短い距離に注目しかつハフマン（Huffman）コードの利点を得るために検索される。ハッシュチエンは単純にリンクされる。ハッシュチエンからの削除はない。アルゴリズムでは古すぎる一致は単純に放棄される。最悪の状況を回避するために、非常に長いハッシュチエンは、運用時間により任意に決定される所定の長さにおいて、任意に縮小される。その結果、“ｇｚｉｐ”は最も長く可能な一致を常に見出すことはないが、一般に、十分に長い一致を見出す。
残念ながら、従来技術における多くの数のLempel-Zivの変形版にも係わらず、いずれも適切に問題点を見出していない。ワードの完全に欠けている辞書と共にスタートすることは、小さなファイルが全く圧縮されることを仮想的に防ぎ、かつ大きなファイルがさらに圧縮されることを防ぐ。米国特許第４，８１４，７４６号及び４，８７６，５４１号において、Miller及びWegmanは、データが複号化された文字の組において全ての文字を含む辞書と共にスタートすることによりこの問題にアドレスすることを開始している。これは、どのような後続が辞書エントリ番号ではなくキャラクタであるかを示すために、エスケープコードを送出する上で必要な問題を解消する。
しかしながら、本願の発明者は、多くの文献、特に人間の自然言語又はコンピュータプログラミング言語、例えば、英語又はＣ言語、で書かれた文献は、統計的に極端に頻度が高く、かつ圧縮辞書の一部とすべき少ないワード数であることを観察することによって、さらなる圧縮が得られることを見出した。Ｚｉｐｆは、標題“Human Behavior and the Principles of least Effort”なる文献において、言語に対してこのことが真実であることを示した。事実、英語におけるワードの頻度は、Zipfian分布として知られるようになったことに従っている。即ち、ワードのランクとその頻度の積は近似的に一定である。従って、第２の最も共通なワードは最も多発するワードと同じ回数のおおよそ半分で現れる。これは、最も共通なワードは文献上の全てのワードの全出現において大きな端数を備えることを意味する。例えば、Marcus他による“Building a Large Annotated Corpus of English：The Penn Treebank, Computational Linguistics, Vol.19, No.2, pp.313-330(199#)”に記載されたツリーバンク（treebank）プロジェクトの一部として集められたウオールストリートジャナール（Wall Street Journal）のデータにおいて、“，”，“the”，“．”，“of”，“to”，“a”，“and”，“in”，“'s”，“is”及び“that”の最初の１０「ワード」は文献全体のワードの２５％より僅かに多い。１００個の最も多発するワードは文献全体のワードの４８．１％であり、さらに、５００個の最も多発するワードは６３．６％である。これは、残りの８０９０１ワードは文献全体のワードの残り３７．４％であることを意味する。従って、上から５００ワードに見られる平均ワードは上から５００ワードに見られない平均ワードより以上の頻度のおおよそ２７５倍である。
従って、従来技術にて記載されたLempel-Ziv圧縮技術を、この観察の利点をとり小さな文献の重要な圧縮と同様に、大きな文献のさらなる圧縮を可能にするように、モデファイすることが望まれている。
発明の概要
本発明は従来技術におけるLempel-Zivテキスト圧縮技術を拡張するものである。特に、本発明は圧縮辞書及び／又は圧縮ウインドウを提供する。圧縮ウインドウには統計的に重要な幾つかのワードを含み、もし圧縮ソフトウェアが、圧縮されるべき文献における極端に共通なワード、文字列及びフレーズのリストを再学習する必要があったならば、それより速く、その重要な幾つかのワードは、文献内においてほぼ確実に達成されるべき圧縮を可能にする。例えば、ＬＺ７８に基づく圧縮技術を使用するときに、単一のキャラクタにより以前のエントリを拡張することによりエントリが圧縮辞書に加えられ、本発明では、極端に多発するワードが圧縮辞書に入力される以前に、その極端に多発するワードの幾つかの繰り返しをとる必要を無くさせる。これはまた本発明に従って使用された圧縮辞書は、プリフィックスがそれ自身で多発でなければ初期に辞書に存在する長く、多発するワードのプリフィックスを必然的に含まない。稀なるプリフィックスは僅かに圧縮処理を助け、ＬＺ７８における主たる利点は長いワードを圧縮辞書に入力することを可能にし、本発明の技術を使用する際に不必要なステップでは、より長い多発ワードは最初から辞書内にある。辞書から稀なプリフィックスを除外することは、他のより有用なフレーズのためにスペースを残すことになる。
一方、最も極端に多発するワードは短く、本発明の発明者等は、圧縮されたテキストの形式の知識は、前もって満たされたプレフィル辞書から大きな利点を引き出すことを認識している。もし、例えば、科学的文献のテキストが圧縮されると、同様なテキストの例が、圧縮されたテキスト形式のプロフィールを得るために使用される。科学的文献のテキストにおいては、幾つかの長いフレーズが極端に共通化されている。これらのフレーズは圧縮ソフトウェアにより学習され、それらに対する最初の参照が圧縮されたデータにおいて作られた時に使用される。例えば、もし長さ１０のワード又はフレーズが共通であったならば、そのワードの最初の出現は１つの辞書参照を使用してエンコードされ、従来のＬＺ７８のもとでは、このようなエンコードはワードの第１１番目より後まで可能ではない。辞書は、頻度の高いワード又はフレーズの文脈の有用なもの以外のものであるとの理由で、このようなサブ列が圧縮過程の間に独立に加えられることがなければ、ＬＺ７８の場合であるとして頻度の高いワード又はフレーズのサブ列を含むことから防がれる。
コンピュータプログラミング言語でのテキストを圧縮するときは、本発明者は、圧縮の開始におけるゲインに潜在的に等しいかそれ以上であることを認識している。例えば、プログラミング言語である、Ｃ言語は言語の構成を示すワードの数が少ない。一方、ユーザは、変数及び関数を作成することにより多発するワードのリストに加えており、全てのＣプログラムはこのワードの基本的なセット中のサブセットを使用する。その結果、圧縮の開始に先立って辞書内にこれらのワードを持つことは、特に小さなファイルに対してより良い圧縮を結果的に生じる。
従って、人間の言語におけるワードの頻度分布及びデータの他の分類の利点を得るために、本発明者は、プレフィル辞書に統計的に重要なワード及び圧縮が生じる全てのアルファベットを併合するために、標準的なLempel-Ziv圧縮アルゴリズムのモデファイされたものを提案する。ところで、重要なワードで辞書を満たす処理は種々の方法のうちのいずれかで扱われる。１つの可能性は、頻繁に使用されるワードのリストを作成するために圧縮ソフトウェアのユーザに対してである。この処理は多くの環境において不満足なものであるから、自動処理が本発明に従って好適に使用される。しかしながら、付加的なプレフィル圧縮辞書は所望の圧縮ソフトウェアのユーザにより作成される。
一方、幾つかのプレフィル圧縮辞書が圧縮されるべき文書全体の小部分集合における圧縮過程の開始において自動的にテストされ、この部分集合における最も高い圧縮を達成する辞書が文書全体を圧縮するために選択される。勿論、ユーザは希望する特定の圧縮辞書を選択する。好ましくは圧縮のために使用されたプレフィル辞書の識別が圧縮データに格納され、その結果、伸長ソフトウェアはどのプレフィル辞書を伸長の間に使用するかを識別する。
同じプレフィル辞書は、圧縮時間における圧縮装置及び伸長時間における伸長装置の両方を利用しなければならない。１つの装置から他の装置にこのような辞書を通信ネットワーク上で送出することが可能であり、必要に応じて、適切な辞書を利用させることも可能である。例えば、複数のプレフィルデータ圧縮辞書は通信サーバ上に格納され、その結果、サーバ間で共有するテキストは本発明の技術を使用して圧縮／伸長される。また、プレフィルデータ圧縮辞書は好ましくはテキストデータの種々のジャンルについて作成されかつ階層的に格納され、その結果、最適なプレフィルデータ圧縮辞書が伝送されるべきデータについて選択される。記憶空間を節約するために、複数のプレフィルデータ圧縮辞書の間でのいずれか共通エントリが各サーバ上で一度だけ格納される必要がある。一方、特定の文献を圧縮するために使用されるプレフィルデータ圧縮辞書は、他の圧縮の間に構成されるデータ特定辞書である。この方法で、複数の文献の圧縮は反復的であり、単一のオリジナルプレフィルデータ圧縮辞書に基づくものである。
当業者にて明らかなように、本発明の技術はLempel-Ziv圧縮アルゴリズムの変形版に関連して使用される。
【図面の簡単な説明】
本発明の上述した及び他の目的と利点は、以下に記載しかつ添付図面に示す本発明の好適な例示的な実施形態でより明らかになる。
図１（Ａ）及び１（Ｂ）は、ともに従来技術としてのＬＺ７７テキスト圧縮の例として提供する。
図２は、従来技術としてのＬＺ７８テキスト圧縮の例である。
図３は、従来技術としてのＬＺＭＷテキスト圧縮の例である。
図４は、本発明によりモデファイされたLempel-Ziv圧縮技術を実現するサンプルハードウェア構成を例示する。
図５は、本発明により作成された圧縮データの使用のオプションを例示する。
図６は、本発明による辞書作成過程のフローチャートを例示し、辞書へのエントリについての選択されたシーケンスは圧縮を最大化するシーケンスである。
図７は、本発明の技術に従って、１つ又はそれ以上のプレフィル辞書を使用するＬＺ７８圧縮システムの好適な実施形態を例示する。
図８は、本発明によりモデファイされたＬＺ７８圧縮技術を例示するフローチャートである。
図９は、本発明の技術に従って、１つ又はそれ以上のプレフィル辞書を使用するＬＺ７８伸長システムの好適な実施形態を例示する。
図１０は、本発明によりモデファイされたＬＺ７８伸長技術を例示するフローチャートである。
図１１は、本発明のモデファイされたＬＺ７８を使用するテキスト圧縮の例である。
図１２は、本発明の混成ＬＺ７７／ＬＺ７８圧縮技術を例示するフローチャートである。
図１３は、本発明の混成ＬＺ７７／ＬＺ７８伸長技術を例示するフローチャートである。
図１４は、本発明による混成ＬＺ７７／ＬＺ７８技術の組み合わせを使用するテキスト圧縮の例である。
目下の好適な実施例の詳細な説明
本発明は、図４〜１４を参照して以下に詳細に説明されるであろう。当業者は、ここで与えられる記述は説明の目的だけであることを理解し、本発明の範囲を限定することを意図してはいない。従って、発明の範囲は、添付された請求項の範囲によってのみ限定される。
本発明によるLempel-Zivアルゴリズムの拡張は、テキスト圧縮文献だけでなく特許文献に記述されているLempel-Ziv圧縮技術の周知の変形版の全部と関連して使用され得る。しかしながら、目下の好適な実施例において、本発明は、LZ77またはLZ78圧縮技術の修正版、もしくは、それ自体LZ77またはLZ78技術の修正版または拡張版であるLempel-Ziv変形版の修正版として使用される。本発明によるLempel-Zivアルゴリズムの拡張版は、好適には、ソフトウエア圧縮パッケージの一部として、または、市販のワードプロセッシングパッケージのようなデータ圧縮から利益を得る既存のソフトウエアパッケージと関連して使用されるモジュールとして実行される。１例であるシステム構成は、図４に示されている。
本発明は、好適には、ユーザのコンピュータ１のプロセッサを制御するための命令を含むソフトウエアとして実行される。好適な実施例において、Lempel-Ziv圧縮アルゴリズムを実行するソフトウエアの実行形式は、コンピュータ１のプロセッサ（ＣＰＵ）３によって読み取り可能なハードディスク２のような固定されたプログラム格納装置上に格納され、それによって、Lempel-Ziv圧縮アルゴリズムを実行するためにその上に記憶される命令のプログラムは、所定のデータ圧縮を実行するためにプロセッサ３によって実行可能である。図４に示すように、ＣＰＵ３は、Lempel-Ziv圧縮アルゴリズムを実行している間データを格納するためのＲＡＭ４を含んでいる。好適な実施例において、圧縮されるべきデータは、フロッピーディスク５、光ディスク５’またはＣＤ ＲＯＭ５”のようなコンピュータが読み取り可能なメディア上のディジタル形式で提供されるか、あるいは、モデム６を介して受信され、ＲＡＭ４中に転送される。もちろん、データは、ＲＡＭ４中に転送される前にコンピュータのハードディスク２上に記憶されてもよく、ネットワーク接続を介して直接提供されてもよい。ユーザからコンピュータ１に入力されるデータはキーボード７および／またはマウスによって提供され、関連するグラフィック画像はコンピュータビデオディスプレイ９上に表示される。
本発明によれば、プレフィル圧縮辞書が、Lempel-Ziv圧縮アルゴリズムを実行するソフトウエアの実行形式とともにハードディスク２上に格納され、Lempel-Zivデータ圧縮アルゴリズムの実行中はＣＰＵ３のＲＡＭ４中に転送される。圧縮されるべきデータは、圧縮される前にハードディスク上のファイルとして格納され、局所的に再格納され、または圧縮後に送出されてもよい。換言すると、データ圧縮が局所的な格納空間を厳格に節約するために実行されるならば、圧縮処理の結果はハードディスク２または他のローカルメモリに記録される。代替例として、入力データおよびプレフィル圧縮辞書は、フロッピーディスク５、光ディスク５’またはＣＤ ＲＯＭ５”のようなコンピュータが読み取り可能なメディア上から提供され、モデム６を介して受信され、あるいは、ネットワーク接続を介して直接提供されてもよい。一方、データ圧縮が（例えば、モデム６を介した）ポイント・ポイント間接続を介する一層高速のデータ送出を許容するために実行されるならば、ＣＰＵ２はモデム６あるいは他の送出装置に接続され、圧縮されたデータはこの送出装置を介して送出される。さらに、圧縮されたデータは元のコンピュータが読み取り可能なメディア（例えば、フロッピーディスク５、光ディスク５’またはＣＤ ＲＯＭ５”）に戻されてもよい。
従って、本発明による圧縮アルゴリズムに実行中は、ＲＡＭ４は、典型的には実行可能なコード、１またはそれ以上のプレフィル圧縮辞書、および、ハードディスク２、フロッピーディスク５、光ディスク５’またはＣＤ ＲＯＭ５”のような他の記憶要素、もしくはモデム接続からの入力データを受信し、圧縮されたデータは、ハードディスク２上、もしくはフロッピーディスク５、光ディスク５’またはＣＤ ＲＯＭ５”のような他の記憶要素上に再格納され、格納および／または伸長のために他のコンピュータにモデム６を介して送出される。さらに、LZ78アルゴリズム変形版が使用されたときに、ＲＡＭ４はLZ78アルゴリズムおよびその変形版の動作中に従来開発された形式のデータ特定辞書のために空間を配分することが望ましい。
図５は、本発明によって生成された圧縮されたデータの使用に対するオプションを示す。図５に示すように、圧縮されるべき入力データはステップ１０で入力され、好適なLempel-Zivデータ圧縮アルゴリズム変形を使用してステップ１２で圧縮され、圧縮されたデータはステップ１４で一時的に格納される。ステップ１６で圧縮がハードディスク２、ＣＤ ＲＯＭ５”等上の局所的格納空間を節約するために実行されることが決定されたならば、圧縮されたデータファイルはステップ１８で局所的に格納され、このルーチンはステップ２０で終了される。しかしながら、入力データが他のコンピュータへの送出をスピードアップするために圧縮されるならば、ステップ２２で圧縮されたデータはモデム６のようなデータ送信装置に移され、ステップ２４で新しい場所に送出される。そして、送出された圧縮データはステップ２６で伸長され、ステップ２８で元の伸長された形式で格納される。そして、このルーチンはステップ２０で終了される。以下に記述されるように、圧縮されたデータを伸長するステップ２６の間に、同じプレフィル圧縮辞書が受け側において使用されるように、圧縮されたデータと共にプレフィル圧縮辞書を送出すること、または、少なくとも圧縮に使用された辞書を識別することが必要であってもよい。もちろん、受信された圧縮データは直ちに伸長される必要はないが、それが必要になるまで受信者で圧縮された形式で格納されてもよい。
Lempel-Zivアルゴリズムにとって重要なワードで圧縮辞書をプレフィルする処理は、本発明による複数の方法のいずれによっても処理される。１つの可能性は、圧縮ソフトウエアのユーザが、しばしば使用されるワードのリストを作成することである。この処理は多くの環境において望ましくはないので、本発明においては自動処理が使用されることが望ましい。特許4,386,416におけるように、このような自動処理に対する１つの可能性は、プレフィル圧縮辞書を、一般的にワードとして参照されるもの、即ち、空白、タブまたは句読点によって範囲が定められたキャラクタのシーケンスに制限することである。しかしながら、最も多発する種々の長さのキャラクタのシーケンスを決定するために、統計がテキストの代表的なサンプルから収集されることが望ましい。各長さの辞書エントリの数は、特定の長さのエントリの使用（即ち、辞書のエントリの長さによっては変わらず、むしろ、辞書の大きさから決定される固定量である辞書エントリに対するリファレンスを送出するために要求されるビット数より少ない特定長の列を復号するために元来要求されるビット数）から結果として生じる圧縮量および使用されるテキストのサンプルの中のそのシーケンスの発見される頻度の関数によって決定され得る。
例えば、圧縮を実行するときの辞書参照が１２ビット（即ち、辞書が高々２¹²または４０９６のエントリを含む）と仮定し、また、ＡＳＣＩＩキャラクタセットの７ビット符号化を仮定すると、１０キャラクタのシーケンスは圧縮なしで格納空間７０ビットが必要であり、９キャラクタのシーケンスは圧縮なしで格納空間６３ビットが必要である。頻度統計が導き出されるテキストの例の中で、特定長の１０シーケンスが６０回発生したと仮定すると、そのシーケンスが辞書の中にあれば、結果される節約は６０＊７０＝４２００（生データの送出コスト）以下の６０＊１２＝７２０（ポインタの送出コスト）であり、３４８０ビットの節約となる。長さ９の列がより頻繁に、６５回発生したと仮定すると、辞書中の長さ９のシーケンスの節約コストは（６５＊６３）−（６５＊１２）＝３３１５の節約となる。従って、長さ１０のシーケンスは長さ９のシーケンスよりも辞書のエントリとして望ましい。
プレフィル辞書の内容は、以下のように効率的に選択されてよい。プレフィル辞書がそれに基づいて学習される文献のすべてのテキストは、テキストのサブシーケンスのすべてが容易に識別されることを許容するデータ構造に中に転送されるべきである。一般的に、最大長は、計算コストがあまりに高くなることを防止するために辞書中の列に対して選択されることが必要である。１０または１５キャラクタの長さは多分充分であろうが、要すれば適当な最大長は経験的に決定されてもよい。しかしながら、本発明のアルゴリズムの設計において特定される適当な最大長は存在しないので、最大長の選択は辞書を構築するソフトウエアのユーザに任される。従って、選択された最大長は最適な圧縮をもたらさないかもしれない。これは圧縮とプレフィル辞書の生成コストの間にトレードオフが存在するからであり、辞書を構築するソフトウエアのユーザは、彼または彼女のコンピュータの合理的な時間内でプレフィル辞書が構築されることを許容する最大長を選択しなければならない。
各ノード（node）が１つのキャラクタ列およびカウントを含むツリーデータ構造は、頻繁に発生する列を識別するために使用される。このツリーのルート（root）は空列およびコーパス（corpus）中のキャラクタの合計数を含んでいる。各子ノード（daughter node）は、ツリーのルートからカレントノードに至る経路上のノードによって含まれるキャラクタのすべてを連結することによって生成される列をイクステンドするであろう。このように、特定長までのキャラクタシーケンスのすべては選択された最大長より深くないツリーの中に格納され得る。このツリーは、ツリーの深さの能力を上昇させるアルファベットの大きさを番号付けするツリーのリーフ（leaves）と共に非常に大きく成育し得る。しかしながら、データがまばらであるために、ツリーは実際上はより小であるべきである。当該分野の技術者にとって好ましいように、データは人間の言語の特性の結果としてまばらであり、従って、言語は可能な綴り（n-grams）のすべてを含まず、あるいは少なくとも頻繁には含まない。例えば、文字列“zqwxv”は経験的にごくまれであり、もしデータが英文の中にある場合にはデータ列中に出現しにくい。
一旦ツリーデータが満たされると、上に概説されたコスト節約公式を最大にするシーケンスが識別されるであろう。識別されたシーケンスのすべてのシーケンスは、データ構造中に辞書中に入れるために選択されたシーケンスの発生回数を減算することによって更新されるそれらのカウントを有していることが必要であるので、重複列は処理される。これは例によって図示されてもよい。データ中に１０回発生するシーケンス“ＡＢＣ”が辞書見出し語として選択されたとする。するとツリー中の“ＡＢ”のノードに関連するカウントは、“ＢＣ”に対するカウント、“Ａ”に対するカウント、“Ｂ”に対するカウント、および“Ｃ”に対するカウントと同様に１０減算されるであろう。シーケンス“ＡＢＣ”それ自体に関連するノードでさえも１０減算されるので、それは辞書からおよび辞書エントリとしての将来の考慮から削除される。
図６は本発明の望ましい実施例に従った辞書生成処理のフローチャートを例示するが、辞書へのエントリに対して選択されたシーケンスは圧縮を最大にするシーケンスである。図６に描かれているように、プレフィル圧縮辞書はステップ３０においてサンプル中の特定のキャラクタシーケンスの発生数（頻度統計）を算出することによってテキストから生成され、そして、ステップ３２において固定された辞書サイズ、従って、固定された辞書エントリポンタ長が与えられる各キャラクタシーケンスの圧縮を決定する。テキストサンプルは、圧縮されるべきテキストの一部、同等の文献、あるいは同一ジャンルの同等の文献の集積であるかもしれない。上の例のように、圧縮は、特定シーケンスの未符号化長と辞書のエントリポインタ長との差が乗算されたステップ３０で決定されたような特定シーケンスの発生数として算出される。従って、各キャラクタシーケンスに対する結果としての圧縮は、どのシーケンスが圧縮を最大とするかを決定するために使用される。ステップ３４において、圧縮を最大とするキャラクタシーケンスが選択され、圧縮辞書に加えられる。必要があるので、データツリー構造中のカウントは、上述のように更新される。そして、そのキャラクタシーケンス自身のキャラクタカウントも含んで、ステップ３４において圧縮辞書に加えられたばかりのキャラクタシーケンスの全サブ列に対するキャラクタカウントは、ステップ３６で修正される。列自体のキャラクタカウントをこのようにモデファイすることによって、後の同一列の圧縮辞書への包含が回避される。ステップ３８で圧縮辞書が満杯でないと判断されたならば、最大圧縮をもたらすこれらのシーケンスの選択処理は、ステップ３８において圧縮辞書が最大圧縮をもたらすこれらのシーケンスで満杯であると判断されるまで継続する。そして、ルーチンはステップ４０で終了する。もちろん、このようにして生成された圧縮辞書は、一般的に、本質的な圧縮をもたらすのに十分な頻度で発生するより長いシーケンスはもちろん極めて頻繁に発生する短いシーケンスも含んでいる。
辞書のためのアドレス空間は分割されることが望ましく、そして、どの辞書が使用されているかを示すフラグは表立って送付される必要はまったくない。アドレス空間は、プレフィル辞書と従来のデータ定義あるいはとにかく圧縮辞書の製作者によって適合していると見做される適応辞書との間で分割され得る。また、結合された圧縮辞書の全体のサイズは、圧縮辞書の製作者によって決定され得る。しかしながら、辞書エントリ番号それ自体はバイナリ表現で符号化されるので、サイズは２の偶数乗となるであろう。
当業者は、圧縮されていないテキストのより長い代表的なサンプルが、必然的にそれぞれがそれ自身の専門用語と統計的性質を有する異なるジャンルのテキストとなる文献を含むことを理解するであろう。従って、所定のジャンルの文献は、そのジャンルを特定するより小さいテキストサンプルを構成する。このようなそれぞれのサンプルは、そのジャンル向けの別個のプレフィル圧縮辞書を生成するために使用されるかもしれない。従って、圧縮辞書を生成するための上述の技術または他の技術のいかなる結合も、英語テキスト、仏語テキスト、Ｃで記述されたコンピュータプログラム、パスカルで記述されたコンピュータプログラム、データベースファイル、画像等のようなデータのいくついかの異なった形式あるいはジャンルに対して適用され得る。いったんデータの各形式に対して最も多発する“ワード”が決定されると、データの各形式に対する辞書が生成され得る。従って、初期の空辞書に対して、新しい“ワード”が追加されるであろうこの辞書は、従来の技術を使用してLempel-Ziv圧縮を実行するために使用されるであろう。例えば、英語新聞テキストが圧縮された場合は、辞書は新聞記事のサンプル中に見出される最も多発する英字シーケンス、ワード、および／またはフレーズによってプレフィルされるであろう。
特定のジャンルの文献を圧縮するために、圧縮コンピュータは、まず、自動手段（例えば、キーワードまたはクラスタ化法）によってこの文献がどのジャンルに最も近いかを識別し、そのジャンルに適したプレフィル圧縮辞書を選択する。従って、選択されたプレフィル圧縮辞書を識別する情報は、圧縮されたデータファイルに追加される。伸長時は、受信されたデータの伸長時にどのプレフィル辞書を使用するかを決定するために、伸長コンピュータは追加された情報を調べる。
この方法を望み通りに動作させるために、サンプル文献の集積は、最初に複数のジャンルに区分されなければならない。これは、いくつかの方法のどの１つによってなされてもよい。例えば、１人あるいは複数人が客観的あるいは主観的判断基準に基づいて相互に区分を決定してもよい。代わりに、コンピュータが、“スペイン語テキスド”あるいは“コンパイルされたコンピュータプログラム”のような特定のジャンル中の関係を示す語あるいは統計的なつづりの正しいパターンを自動的に走査してもよい。さらに、サンプル文献の集積に対して何も知られていない場合には、文学において公知のデータクラスタ化方法を使用して、集積は合理的なジャンル群に自動的に区分されてもよい。
このようにして、必要に応じて、付加的なプレフィル辞書は、圧縮ソフトウエアのユーザによって生成され得る。共にテキストのたの形式中には普通見出されない語の頻繁な使用を伴うコンピュータマニュアルあるいはビジネス文献のようなそれ自身の標準的な語彙を有するデータをユーザが定常的に圧縮する場合には、彼または彼女は、テキストのこの形式の大きい本体に対して辞書生成処理を適用し、文献のこの形式の使用に対する特注辞書を生成することが可能である。明らかに、可能であるべき伸長に対して、伸長を実行するソフトウエアもまたこの辞書にアクセスしなければならない。同様に、データが保存目的に対しては圧縮されないが、オンライン送出のために圧縮される場合には、圧縮されたデータの受け側はこの特注の辞書に対するアクセスを有しなければならない。従って、それが多数の辞書の配付および格納を要求し、圧縮目的に対するより適当な辞書の使用という付加的な利益を削除、または少なくとも低減するので、辞書生成処理は頻繁に実行されるべきではない。
圧縮処理の間に、最も高レベルの圧縮を達成するであろうプレフィル辞書は、圧縮されるべき全文献の小さいサブセットに対して圧縮を行うことによって決定され得る。換言すると、圧縮されるべきテキストのデータの最初のＮ文字（Ｎは任意の数であり、辞書の識別が異常に多大の時間を費やさないように最大値となるように事前に選択されても、文献長の割合として算出されてもよい。）は、推定プレフィル辞書のそれぞれを使用して圧縮される。各プレフィル辞書は使用した圧縮は計算され、全テキストを圧縮するために圧縮を最大とするプレフィル辞書が選択される。このように、最適の辞書が圧縮されるべき特定のテキストに対して使用され得る。さらに、彼または彼女が圧縮されるべき文献が特定のプレフィル辞書によって表される文献の種類の典型であることをおそれるならば、ユーザは手動で辞書を選択することも可能である。これはソフトウエアが種々の圧縮辞書を試すことを防止し、圧縮処理における時間の節約をもたらす。さらに、送り側が所有するプレフィル辞書の全部を所有していない他のユーザへの文献の送出を許容するために、また、遠隔サイトのソフトウエアのように使用可能な圧縮辞書の全部を認識していないソフトウエアによって後刻文献が伸長されてもよいように保存の目的の圧縮において、手動選択は必要である。
また、圧縮されるべきデータ中の文字のサブセットの圧縮過程において、完全な空データの圧縮辞書での開始が最もよい圧縮を許容すると判断された場合には、プレフィルデータ圧縮辞書はその特定データの符号化から除去されてもよい。
伸長処理の間に、圧縮の間に構築されたデータ特定辞書に対してなされたのと同一の修正が、データ特定辞書に対してなされる。このように、圧縮されたデータ中でのデータ特定辞書の参照は、データ伸長システムによって生成される再構築されたテキスト中に適当に拡張されてもよい。圧縮のために使用されたプレフィル辞書の識別子は、伸長モジュールが伸長の間で使用されるべきプレフィル辞書を識別できるように、圧縮されたデータ中に適当に記憶される。同様にデータ圧縮を実行するために使用されたLempel-Zivアルゴリズムの変形版の指示も圧縮されたデータはもちろん圧縮中に２つの辞書中のエントリを一度に流すためにどのような思想が使用されたかの指示とともに圧縮データ中に記憶される。さらに、圧縮中に含まれた辞書に対して辞書アドレス空間がどのように割り当てられたかの指示、即ち、データ特定辞書に対する開始および終了アドレスが何であるかだけでなく、圧縮で使用された１またはそれ以上のプレフィル辞書に対する開始および終了アドレスが何であるかも圧縮データとともに記憶されてもよい。また、圧縮されたデータが遠隔サイトに伝送される場合には、遠隔サイトにおける伸長を許容するために圧縮辞書を送ることが必要になるであろう。しかしながら、時間節約が辞書の伝送に必要とされる時間よりも大きくない限り、これは圧縮の目的を打ち負かしてしまうであろう。一方、時間節約が辞書伝送のコストを超えない場合でも、この辞書を使用して圧縮された他の文献が伝送されるならば、辞書の送出は賢明となるであろう。従って、圧縮されたデータが遠隔サイトに伝送されるときは、受信サイトにおいて使用可能なプレフィル辞書だけを使用することが一般的に望ましい。
しかしながら、送り側が最適のプレフィル辞書は辞書Ａであると判断したが、受け側が辞書Ａを有していないために代わりに辞書Ｂを使用して圧縮した場合は、送り側は受け側に対して、受け側は将来の使用のために辞書Ａを取得することを助言するメッセージを伝送することも可能である。いったん受け側がこのようなメッセージを取得すると、受け側はついには送り側または辞書Ａが使用可能な他のサーバから辞書Ａを得るであろう。そして、受け側はローカルの長期もしくは中期格納装置中に辞書Ａの記号複製を配置する。
別の考えでは、受け側が辞書Ａを有するかどうかを考慮せずに、送り側はプレフィル辞書Ａを使うデータファイルを備えてもよい。そのときは、受け側が最初にファイルを伸長するときはいつも、辞書Ａの記号複製が必要となるであろう。辞書Ａが受け側に現在格納されてない場合、受け側はネットワークを介して記号複製を獲得することができるであろう。そして受け側は、辞書Ａの記号複製を、ファイルを伸長するために使うのに加えて将来使うときのために、長期間又は中期間格納しておく。
一方で、例えば記録保管を目的として、一度にドキュメントの多くの集まりを圧縮したいようなことが起きるかもしれない。ドキュメントを別々に圧縮するよりはむしろ、各ドキュメント内の類似性あるいは予め選択されたコーパスに対する類似性ではない、様々なドキュメント間の類似性を利用することが望まれる。換言すれば、ドキュメントのいくつかが、ある手法において互いに関係する場合、それらの多くはさらなる圧縮に利用することができる同類の列を含むであろうということである。
例えば、ドキュメントＡが、普通の英語のワードを有するプレフィル辞書Ｄを使って、本発明により圧縮されたと仮定する。ドキュメントＡの圧縮終了時では、ドキュメントＡに現れる列だけではなくＤからのエントリを含む拡張された辞書Ｄ’が残る。別のドキュメントＢは、開始辞書として、プレフィル辞書Ｄ（あるいは辞書Ｄと辞書Ｄ’とのいくつかの中間物）の代わりに辞書Ｄ’を使って圧縮されてもよい。ドキュメントＢがドキュメントＡと全く同様である場合、この技術は優れた圧縮を提供するものであるということがわかる。
しかし、大量のドキュメントを圧縮することが望まれるような一般的な場合では、圧縮されたどのようなドキュメントＢでも、伸長時に使うために開始辞書を特定化すべきである。持ち合わせのプレフィル辞書の１つを特定化してもよいし、別の圧縮ドキュメントをドキュメントＡと命名し、そしてドキュメントＡの伸長の結果生じる最終辞書がドキュメントＢの伸長のために開始辞書として使われるということを特定化してもよい。
どのドキュメントが他のドキュメントの最終辞書に依存しているかを判定するためにクラスタ技術を使ってもよい。互いに非常に類似するようクラスタ化することによって判定されるドキュメントは互いに圧縮辞書を使って圧縮される。どのドキュメントが互いに依存するかに関する情報は、一旦依存するドキュメント全てがそれら自身伸長されるるとき伸長ソフトウェアがドキュメントを正確に伸長できるように圧縮されるとき、ドキュメントのヘッダに特定化される。
従って一般に、それぞれが高度に特定化されたタイプのテキストに対して適合されているような非常に多くの辞書を利用可能にすることによって、あるデータに対する圧縮率を改善することができる。しかし、非常に多くの辞書を格納する、そして時には送出するということに関しては費用がかかる。異なる辞書が多くの同じ列を符号化し、そうすることによって本質的な度合いで内容が重なることを認めることによってこの費用を最小化にすることができる。辞書符号化のこの特徴を利用することができるので、複数のジャンル特定テキストサンプルに対するプレフィル辞書は、ドキュメントの単一の大きなコーパスから同時に生成することができる。この例では、複数の辞書に対して特別に結合された表現は、異なるジャンル特定辞書の全てを個別に格納するのに必要であるときよりも少ない空間を占めるであろう。つまり、メモリ空間は、それぞれ各々の辞書にエントリを個別に格納するのとちがって、１度だけ複数の辞書にある列を格納することによって節約される。
当業者は、本発明が辞書の緊密さによって圧縮効率がもたらされることをある程度理解できるであろう。これを例示するために、圧縮効率及び辞書の緊密さの相対的な重要度を示すパラメータを定義することができる。パラメータが１に設定されるとき、最大圧縮効率が得られる。換言すれば、パラメータが１であるとき、専門化された辞書が各ジャンルに対して独立に作られ、各ジャンルに対する辞書は、上述のような複製の冗長な格納を取り除くために結合されるのみである。一方で、パラメータが多少減る場合は、ジャンル辞書は全部が独立して作られるわけではない。すなわち、これらはその重なりを改善するために故意に構成されるのである。パラメータが０まで幅広く減る場合、最大の重なりは、どのジャンルに対しても同じ辞書を使うことにより得られる。従ってパラメータを０に設定することにより最も小さい結合辞書を作り出すことができるが、しかしそれはジャンルに特定の特性には全く利用することができない。現在、本発明者は、多くの専門化されたジャンルが、サンプルドキュメントに対する「デューイ十進」分類法システムに対して、２つまたは３つを１度に階層的な「スーパージャンル」アナログにグループ分けされるときに、本発明の技術は最も良く稼動するであろうと考えている。このような階層的分類技術は、必要ならば、公知の自動クラスタ技術によって達成される。
本発明の好適な実施例は、ＬＺ７８の拡張として、図７〜１１を参照して説明する。好適な実施例のＬＺ７８アルゴリズムでは、図２で示されたように、圧縮処理の間拡大されるような圧縮辞書を使って、テキストは圧縮され、そうして圧縮辞書に対するリファレンスがオリジナルテキストの代わりに送出信される。しかし、従来のＬＺ７８と違って、本発明の使用される圧縮辞書が空の列からはスタートしない。その代わりに、空の列だけではなく、上記の手法の１つで生成される１つのプリフィル辞書あるいは数個のプリフィル辞書の内容をも得るために初期化される。プリフィル辞書はまた、圧縮が実行されるアルファベットの完全な内容を得ることができる。また、圧縮辞書は、共通アドレス空間を共有する２つの別個の辞書又は、単一のより大きな辞書のどちらとしてもみなすことができるが、それは本技術の実施例の詳細による。従って、本発明の使用される技術は、付加的なエントリが加えられる空の列のみを得る従来のデータ特定辞書はもちろん、１つのプリフィル辞書あるいは数個のプリフィル辞書からでもスタートされる。しかし、ＬＺＭＷにおけるように、アルファベットの全キャラクタがプリフィル辞書に加えられている場合は、データ特定辞書は空であるに違いない（なぜなら、そのイクステンションに続く空の列を送出する必要がないからである）。
プリフィル辞書空間は、同じアドレス空間を共有する２つの別個の辞書又は、圧縮開始前の１つのより大きなプリフィル辞書を形成するために連結されるあるいは連結されないような１つないしそれより多い独立のプリフィル辞書としてみなすことができる。圧縮されるべきキャラクタのシーケンスに遭遇するとき、１つ又は複数のプリフィル辞書内、あるいはデータ特定辞書内のどれにおいても最長一致（ＬＭ）は、ルックアップテーブル内において、又はツリーデータ構造を使って見つけることができる。この一致が一旦見つかると、辞書エントリ番号及びこのシーケンスに続くキャラクタが送出される。そして、まさに送出された辞書エントリ及び送出されたキャラクタの連なりは、データ特定辞書に加えられる。この処理は、圧縮されるべきデータが消滅するまで繰り返される。
ＬＺ７８については、プリフィル辞書は固定された大きさを有するが、その大きさは、圧縮をもたらすために送出される必要のある辞書エントリ番号の大きさを決定する。一旦プリフィル辞書が満杯になると、さらなるエントリは認められない。しかし、文学において概説（outlined）される辞書操作（dictionary handling）に対してあらゆる修正版を使うことができる。例えば、least recently usedアルゴリズムは、新しいエントリが加えられる必要のあるとき、辞書エントリを処分するのに使うことができる。代替的には、実績を監視することができ、圧縮比があるしきい値以下に落ちるか又は、圧縮されているデータの先行する部分に対して達成される圧縮比から逸脱するとき、データ特定辞書をリセットすることができる。
図７及び８は、本発明によるＬＺ７８データ圧縮を実行するための好適な実施例を例示する。図７に示されるように、圧縮されるべき入力データは、ＬＺ７８データ圧縮ソフトウェアモジュール42へ提供されるが、ＬＺ７８データ圧縮ソフトウェアモジュール42は、公知のＬＺ７８アルゴリズムの変形版のいずれを含んでもよい。上記で注目したように、辞書44は２つの個別の辞書、すなわち、従来のＬＺ７８データ特定辞書46及びプレフィル辞書48を含むものとみなすことができ、両者は同じ共通アドレスバス50を共有する。また、複数のプリフィル辞書52は、特定の入力データに対して最も圧縮するようなプリフィル辞書を見つけるためにも使うことができる。図７のアクティブな要素全ては、一般的には、動作中ＣＰＵ３（図４）によって処理するためにＲＡＭ４にもたらされる。
図８は、本発明によるＬＺ７８データ圧縮モジュール42におけるモデファイされたＬＺ７８圧縮技術を実現するためのソフトウェアのフローチャートである。図に示されるように、ルーチンはステップ56でスタートし、入力データストリームが空かどうかをステップ58で検査する。空である場合、全入力データは圧縮されており、ルーチンはステップ60へ進む。しかし、データストリームが空でない場合、このことから圧縮すべき入力データがより多く存在し、ステップ62において、現ポインタに続くデータシーケンスを有する最長一致（ＬＭ）がデータ特定辞書46から検索される。見つけられた最長一致は、ＤＳＬＭとしてＬＺ７８データ圧縮モジュール42に格納される。そしてステップ64において、現ポインタに続くデータシーケンスを有する最長一致（ＬＭ）がプリフィル辞書48及び／又はプリフィル辞書52から検索される。見つけられた最長一致は、ＰＦＬＭとしてＬＺ７８データ圧縮モジュール42に格納される。そして、ステップ66において、ＣＰＵ３は、データ特定辞書46で見つけられた最長一致の長さが、プリフィル辞書48（及び、１つより多くのものが使われている場合は他のプリフィル辞書52）で見つけられた最長一致の長さよりも長いかどうかを判定する。ＤＳＬＭの長さがＰＦＬＭの長さよりも大きい場合は、次にステップ68において最長一致がＤＳＬＭに設定され、そうでない場合は、ステップ70において最長一致がＰＦＬＭに設定される。（ＤＳＬＭとＰＦＬＭとの長さが等しい場合、フラグがトラックを維持する必要があるということを避けるために同じ長さであるとき辞書の一つを簡単に割り当てることを望むことができるにもかかわらず、あるいはどの辞書が最後に使われていようとも、前入力データシーケンスに対して使われた同じ辞書を使うことができる。）
ＬＭがステップ66〜70において一旦判定されると、ステップ72で、ＬＺ７８データ圧縮モジュール42において、入力データストリームにおいてＬＭに続くキャラクタが特定されイクステンション（Ｃ）として格納される。そしてステップ74において、ＬＭの辞書エントリ番号（及びどの辞書かについて）は所望の通りに送出／格納される。同様にステップ74において、イクステンション（Ｃ）は所望の通りに送出／格納される。そしてステップ76において、イクステンション（Ｃ）は、既に満杯となるまで、最長一致（ＬＭ）に連結されてデータ特定辞書46に格納される。もちろん、従来技術における更新技術（prior art updating techniques）もまた使うことができ、そうして、例えば最も以前にアクセスされたエントリの代わりに最新のエントリをデータ特定辞書46へ挿入することができる。そしてステップ78において、入力データに対する現ポインタを、（イクステンションに対して）最長一致プラス１の長さだけ移動させる。そして制御はステップ58に戻り、圧縮処理は、データストリームが消滅して圧縮処理が完了するまで入力データの次のシーケンスに対して繰り返される。
図８の方法を費用の節約を考慮に入れてモデファイしてもよいが、この費用の節約は、ＬＺ７８あるいはＬＺ７７におけるウィンドウ、を有するようなデータ特定辞書を使って、又はプリフィル辞書を参照してデータシーケンスを圧縮することに関係している。ＬＺ７８においては、各やり方に対する費用はおそらく同一であろうが、しかし、ＬＺ７７を本発明によるプリフィル辞書を有するよう拡張するとき、２つのやり方を使って圧縮する費用は異なり、両方の技術を使って圧縮が可能である場合には一方の方法よりももう一方の方法を選べるので有利である。
本発明によるＬＺ７８圧縮データシーケンスの伸長は、従来のＬＺ７８伸長技術と実質的に同じ方法で実行される。圧縮中になされる圧縮辞書に対する全修正版は、伸長の間にも同様になされる。このことは、ＬＺ７８の場合のように多少アルゴリズムの有益性を制限する。なぜならデータの一部を伸長するということは、先行する部分をそっくりそのまま伸長することを必要とするからである。伸長を実行するとき、辞書エントリ番号及びキャラクタの組のリストを、消滅するまで１度に１組処理する。一般的に、各辞書エントリは辞書内で調べられ、その辞書エントリの示すテキストが、その辞書エントリ及びキャラクタの組におけるキャラクタに従って表示される。このやり方によって、無損失の圧縮／伸長が達成される。
図９及び１０は、本発明によるＬＺ７８データ伸長を実行するための好適な実施例を例示する。図９に示されるように、圧縮データはＬＺ７８データ伸長ソフトウェアモジュール80へ提供され、このＬＺ７８データ伸長ソフトウェアモジュール80は公知のＬＺ７８アルゴリズムの変形版のいずれを含んでもよい。動作中、ＬＺ７８データ伸長モジュール80は辞書82内の入力圧縮デーダの辞書エントリを調べるが、この辞書82はプリフィル辞書84及び従来のデータ特定辞書86を有し、ＬＭを特定する辞書エントリ番号を使う。そして、結果生じた辞書エントリは、エントリＥとしてＬＺ７８データ伸長モジュール80に格納される。そして、入力圧縮データストリームにおける辞書エントリ番号に続くキャラクタは、ＣとしてＬＺ７８データ伸長モジュール80に格納される。そしてＣ及びＥは、ＣＰＵ３によって連結され、満杯になるまでデータ特定辞書86に挿入され、そして、再編成され伸長された（オリジナル）データとして出力する。連結されたデータは、圧縮中にデータ特定辞書48に挿入されたデータに対して同じ決まりを使ってデータ特定辞書86に挿入される。換言すれば、連結されたデータに割り当て又は再割り当てされた辞書コードは、割り当てられた辞書コードが圧縮中に判定されるのと同じ手法で判定される。
当業者は、辞書エントリ番号が、伸長の間、使われた圧縮の変形例に依存して異なるように割り当てられるということは理解できよう。従来のLempel-Ziv従来技術が使われる場合、割り当てられた辞書エントリ番号は、シーケンス（すなわち最初のものが０、次が１、その次が２などというように番号つけられる。）の次の１つに関連するものである。従来のLempel-Zivは辞書上であらゆる特別な機能を実行するための準備はなされていないので、辞書が満杯なとき辞書はリセットされて辞書番号が０に戻るか、あるいは辞書はさらには成長しないであろう。一方で、「least recentry used法」（ＬＲＵ法）のようにより複雑なスキームが辞書を管理するために使われる場合、辞書が満たされるまで、割り当てられた辞書エントリ番号は今説明したものと同じとなろう。ちょうどその時点でＬＲＵアルゴリズムは活動し始め、最も以前に使われた（least recently used）辞書エントリの辞書エントリ番号が割り当てられるであろう。辞書エントリ番号に以前関係していた辞書エントリは、辞書から取り除かれるであろう。
圧縮側上のプリフィル辞書48については、辞書82は、同じ共通アドレスバス88を共有する２つの個別の辞書としてみなすことができる。また、このような複数のプリフィル辞書が圧縮中に使われた場合、複数のプリフィル辞書90を、伸長の間にも使うことができる。図９のアクティブな要素全ては、一般的には、動作中ＣＰＵ３（図４）によって処理するためにＲＡＭ４にもたらされる。
図１０は、本発明によるモデファイされたＬＺ７８伸長技術を実現するためのソフトウェアのフローチャートである。図に示されるように、ルーチンはステップ94でスタートし、入力圧縮データストリームが空かどうかをステップ96で検査する。空である場合、全入力データは伸長されており、ルーチンはステップ98へ進む。しかし、圧縮データストリームが空でない場合、このことから伸長すべき入力データがより多く存在し、ステップ100において、現ポインタに対応する辞書エントリは辞書エントリ番号を使って調べられる。そして、そのようにして見つけられた対応する辞書エントリは、ＥとしてＬＺ７８データ伸長モジュール80に格納される。所望であれば、伸長されたデータはまたユーザに対して表示される。そしてステップ102において、現辞書エントリ番号に続く入力圧縮データストリームにおけるキャラクタは、ＣとしてＬＺ７８データ伸長モジュール80に格納される。所望であれば、そのキャラクタはまたユーザに対して表示される。ステップ104において、キャラクタＣ及び辞書エントリＥは連結され、ＡＤＤとしてＬＺ７８データ伸長モジュール80に格納される。所望であれば、もう１回、連結された結果はまたユーザに対して表示される。そしてステップ106において、連結「ＡＤＤ」は、既に満杯となるまでデータ特定辞書84へ挿入される。もちろん、従来技術における更新技術もまた使うことができ、そうして、例えば最も以前にもアクセスされた（least recently accessed）エントリの代わりに最新のエントリをデータ特定辞書80へ挿入することができる。そして最後に、ステップ108において、入力データに対する現ポインタは、入力圧縮データストリーム内の次の辞書エントリ番号のスタートへ進められる。そして制御はステップ96に戻り、伸長処理は、入力圧縮データストリームが消滅するまで入力データの次のシーケンスに対して繰り返される。そして伸長処理は完了する。
図１１は、図７〜１０を参照して説明された本発明のＬＺ７８の実施例を使ったテキスト圧縮の例である。図２の例のように、アルファベットは３つのキャラクタ（Ａ，Ｂ，Ｃ）だけを含むと仮定し、圧縮されるべきデータは、説明目的のために図２と同じである。図に示されるように、圧縮辞書は、初期において、多発シーケンス分（frequent sequences）のほかにアルファベットのキャラクタも含むが、ここで多発シーケンスは、テキストのサンプルから、以前格納された同様のテキストから、ユーザ入力から、あるいは当業者にとっては明らかであるような技術に統計的に基づく他のあらゆるものから決定されたものである。圧縮がスタートするキャラクタに対するポインタは、圧縮されているテキストのシーケンス内の最初のキャラクタに位置する。図２の例に示されるように、辞書内の最長一致が見つけられ、このエントリに対するポインタは、圧縮アルゴリズムの適用に応じて局所的に送出又は格納される。辞書内の最長一致は、プリフィル辞書に挿入されるべき列を特定するために上述のタイプのツリー構造と一致する辞書エントリ全てを含むようなツリー構造を作ることによって見つけられる。別の可能性としては、ルックアップテーブル又はハッシング機能を使う。そして、いずれにしても、ポインタは送出されるキャラクタの数によって移動させられる。
図１１に示されるように、辞書は以前送出された２つの辞書エントリの連結を含むように更新される。最初のステップでは、前の送出は存在せず、よって辞書には何も加えらされない。処理サイクルによる第２の反復では、最も大きい一致が見つけられ、その辞書エントリ番号は送出され、ポインタはキャラクタの適当な数によって移動させられ、送出された２つの前辞書エントリの連結されたものは、新しいエントリとして辞書に加えられる。この場合では「Ａ，Ｂ，Ｃ」が加えれる。そしてこの処理は第３のステップで繰り返され、新しいエントリ「ＡＢＢ」は、辞書に加えれる。この処理は圧縮されるべきデータが消滅するまで繰り返されるが、この例では、同じ入力シーケンスに対して、図２の従来技術のＬＺ７８技術において使われる６ステップに対して３つだけのステップですむ。それゆえ、本発明による多発して発生するシーケンスを含むプリフィル辞書は、従来のＬＺ７８圧縮アルゴリズムの符号化／複合化の効率を実質的に改善することができる。
もちろん、当業者によって理解されるように、プレフィル辞書も、また、ＬＺ７７データ圧縮変形版の圧縮性能を改良する。しかしながら、本発明のプレフィル辞書がＬＺ７７データ圧縮変形版とともにどのように使用されうるのかを理解するために、上記のＬＺ７７圧縮技術とＬＺ７８圧縮技術との違いを思い出さなければならない。図１について説明されたように、ＬＺ７７技術は、辞書を明瞭に構築するというよりむしろ、ＬＺ７８と同様に、ドキュメントの既に圧縮された部分の一部からなるテキストの「ウィンドウ」を保持する。各ステップにおいて、本システムは、圧縮されるべく残っているテキストのプレフィックスとして現れるウィンドウの最長のサブ列を識別する。本システムは、そのウィンドウへのポインタを送出することによってこのプレフィックスを符号化するが、そのポインタは、プレフィックスのコピーが始まるウィンドウ内位置又はプレフィックスのコピーが終わるウィンドウ内位置のいずれかをユーザの選択にて指定するものであり、次いで、本システムは、そのプレフィックスの長さとおそらくはイクステンションとを送出する。しかしながら、選択されたプレフィックスが空であれば、本システムは、エスケープコードとそれに続く圧縮されるべき次の文字キャラクタとを送出する。そのウィンドウは、新しく圧縮されたテキストを含むために更新され、圧縮は、そのプレフィックスの直後に続くドキュメントの部分について継続する。ＬＺ７７技術は、送出される各プレフィックスとともに文字キャラクタが送出されることを必要としない。結果として、ＬＺ７７技術の変形版は、ＬＺ７８技術よりも一般に効率的であり、ｇｚｉｐ及びＰＫＺＩＰのような多くの一般的な圧縮プログラムにおいて使用されている。
本発明によるプレフィル辞書は、数多くの方法のいずれにおけるＬＺ７７技術に組み込むことができる。まず、最も単純には、多くの共通の列を含む標準テキストを作成することができ、このテキストは、任意のドキュメントの圧縮を通してウィンドウにプリペンド（prepend）された状態に維持されることができる。そのプリペンドされたテキストが、実際に圧縮され送出されるのではなく、ウィンドウ内にあるため、圧縮ソフトウェアは、最近圧縮され送出されたテキストを参照するのと同じ方法でそれを参照することができる、ということに留意すべきである。かくして、圧縮処理の初めにおいては、ウィンドウとして働くべく利用可能なテキストが他にないときには、圧縮アルゴリズムは、共通列を含むテキストへのポインタを依然として送出することができる。このことは、特に、多くの文字キャラクタ又はウィンドウ内に十分なテキストがないことによる他の短い列をＬＺ７７技術が送出しなければならない、圧縮の始めにおいて、圧縮性能を改善する。圧縮が進むと、共通列を含むテキストは、随時、徐々に短くなって、ドキュメントからテキスト用ウィンドウ内の多くのルームが圧縮されるのを可能にする。圧縮されたテキストに対するプレフィル辞書テキストの最適比は、経験的に決定されることができ、一つのドキュメントジャンルから他のものへと一般に変化する。ＬＺ７７においては、固定サイズのウィンドウのテキストが、かかる圧縮のために一般に使用される。
他の、好適ではあるが、より複雑な技術は、圧縮アルゴリズムによって使用されるポインタのセットが、おそらく不規則に、２つのクラスに分割されるものとして扱うことを必要とする。第１のクラスのポインタは、ウィンドウ内の位置を指し、標準のＬＺ７７におけるように、ドキュメントの既に圧縮された部分の一部からなる。第２のクラスのポインタは、頻繁に発生する列を列記する辞書におけるエントリを指す。この混成の方法は、実質的には、ＬＺ７７及びＬＺ７８の性質のいくつかを結合する。各ステップにおいて、本システムは、２つの方法のうちの１つによって、ドキュメントの残り部分のプリフィックスを選択し、符号化し及び送出する。ＬＺ７７方法に続いて、ウィンドウ内のサブ列へのポインタ及びそれに続くこのサブ列の長さを送出してもよく、又は、必要なときには、エスケープコード及びそれに続く文字キャラクタを送出してもよい。あるいは、ＬＺ７８方法に続いて、圧縮されるべく残っているテキストのプリフィックスである最長辞書エントリへのポインタを送出してもよい。後者の方法は、かかる辞書エントリが存在する任意のステップにおいて、その方法が、ＬＺ７７方法がするよりもそのステップでより良好な圧縮（テキスト長に対する送出ビットの比によって測定される）を達成するならば、使用される。ＬＺ７７に対するこの混成方法の一つの利点は、送出される必要のある長さがなく、各辞書エントリは、辞書に永久的に格納される（又は記録される）固定長を有する。この混成の方法は、また、辞書エントリに文字キャラクタが伴わないということにおいて、ＬＺ７８よりも効率的である。
図１２は、かかる混成ＬＺ７７／ＬＺ７８圧縮技術を実現するソフトウェアのフローチャートである。現在好適な実施例においては、かかるシステムは、図７のＬＺ７８データ圧縮モジュールと、図９のＬＺ７８データ伸長モジュール８０とをそれぞれモデファイし、ＬＺ７７圧縮及び伸長ソフトウェアを含むようにすることにより、実現される。図示のように、結果としての混成ルーチンは、ステップ１１０でスタートし、入力データストリームが空かどうかをステップ１１２でチェックする。もしも空であれば、全ての入力データが圧縮され、当該ルーチンはステップ１１４で終了する。しかしながら、データストリームが空でなければ、従って圧縮すべき入力データがあれば、現ポインタに続くデータシーケンスを有する最長一致（ＬＭ）についてステップ１１６でプレフィル辞書が検索される。発見された最長一致（及び付加的にキャラクタイクステンションＥＸＴ）は、ＬＺ７７／ＬＺ７８データ圧縮モジュールにＰＤＬＭ（及びＥＸＴ）として格納される。現ポインタに続くデータシーケンスを有する最長一致（ＬＭ）を求めて、テキストの前のウィンドウが、次いで、検索される。発見された最長一致は、ＬＺ７７／ＬＺ７８データ圧縮モジュールにＷＬＭとして格納される。ステップ１２０では、ＣＰＵ３は、次いで、ステップ１１８にて一致が発見されたかどうかについて判定し、もしそうであれば、圧縮（ＥＸＴ）されるべきテキスト内の最長一致ＷＬＭに続くキャラクタが、ステップ１２２において（もしもイクステンションオプションが要望されているならば）識別される。他方、ＷＬＭにおいて一致が発見されなかったとステップ１２０にてＣＰＵ３が判定するならば、ステップ１２４では、現ポインタによって指定された一つのキャラクタ文字ＥＸＴを識別するためにポインタ及び長さの代わりにエスケープコードが使用される。
ステップ１２６では、辞書エントリ番号としてＰＤＬＭを送出することのコストが、ポインタ及び長さとしてＷＬＭを、並びに付加的に一つのキャラクタイクステンションＥＸＴを、あるいはリテラルとして送出することのコストと比較される。詳細には、ステップ１２６において、圧縮されていないデータを送出するのに比較してどの技術が最も節約するかが判定される。一般的には、これは、各技術に関して圧縮比を計算することによって達成される。次いで、ステップ１２６の結果に基づいて、ＰＤＬＭ及びＷＬＭの最も多くを節約する技術が、ステップ１２８において（ＥＸＴとともに又はＥＸＴなしに）要求されるように送出／格納される。最後に、ステップ１３０では、入力データへの現ポインタが、（イクステンションＥＸＴが使用されるならば）最長一致の長さ又は最長一致に１を加えた長さだけ移動せしめられる。次いで、制御は、ステップ１１２に戻り、現ポインタでの入力データの次のシーケンスのために圧縮が繰り返され、やがては、データストリームが使い果たされ、圧縮処理が完了する。
図１３は、本発明による混成ＬＺ７７／ＬＺ７８伸長技術を実現するソフトウェアのフローチャートである。図示のように、本ルーチンは、ステップ１３２でスタートし、ステップ１３４で入力圧縮データストリームが空かどうかをチェックする。もしも空であれば、全ての入力データが伸長せしめられ、本ルーチンはステップ１３６で終了する。しかしながら、圧縮データストリームが空でなく、従って伸長すべき入力データが存在するならば、それがＰＤＬＭであるか又はＷＬＭであるかを判定するために、現ポインタに対応するエントリがステップ１３８でチェックされる。例えば、リファレンスがＰＤＬＭリファレンスであるか又はＷＬＭリファレンスであるかは、アドレッシングされた空間がどのように分割されているかをチェックすることによって決定されうる。圧縮データストリーム内のエントリがＰＤＬＭであれば、図１０に関して説明されたＬＺ７８技術が続く。特に、現ポインタに対応するプレフィル辞書内の辞書エントリが、辞書エントリ番号を使用してステップ１４０において参照される。そのようにして発見された対応する辞書エントリは、次いで、ＥとしてＬＺ７７／ＬＺ７８伸長モジュールに格納される。所望ならば、伸長せしめられたデータは、また、ユーザに対して表示される。ステップ１４２では、付加的なイクステンションＥＸＴが（アルゴリズムを走行せしめるのに先立って決定されて）送られたならば、現辞書エントリ番号に続く入力圧縮データストリーム内のキャラクタが、次いで、ＬＺ７７／ＬＺ７８伸長モジュールにＣとして格納される。要求されるならば、そのキャラクタは、また、ユーザに対して表示される。ステップ１４４では、キャラクタＣ及び辞書エントリＥが、連結され、そしてＬＺ７７／ＬＺ７８データ伸長モジュールにＡＤＤとして格納される。所望ならば、もう一度、結果の連結もユーザに対して表示される。
他方、圧縮データストリームがＷＬＭであるとステップ１３８で判定されるならば、そのポインタでのエントリが、ステップ１４６で、そのエントリによって指定されるテキストの前のウィンドウにおけるエントリを参照するために使用される。その値は、ＬＺ７７／ＬＺ７８伸長モジュールにＥとして格納される。要求されるならば、伸長データも、また、ユーザに対して表示される。ステップ１４８では、付加的なイクステンションＥＸＴが（アルゴリズムを走行せしめるのに先立って決定されて）送られたならば、現エントリに続く入力圧縮データストリームが、次いで、ＬＺ７７／ＬＺ７８伸長モジュールにＣとして格納される。所望ならば、そのキャラクタも、また、ユーザに対して表示される。ステップ１５０では、キャラクタＣ及び辞書エントリＥが、連結され、ＬＺ７７／ＬＺ７８データ伸長モジュールにＡＤＤとして格納される。要求されるならば、もう一度、結果の連結もユーザに対して表示される。
ステップ１４４又はステップ１５０のいずれかが完了すると、入力データストリームへの現ポインタが、ステップ１５２において、データストリーム内の次のエントリの始めに進められる。次いで、制御は、ステップ１３４に戻り、伸長処理が入力データの次のシーケンスのために繰り返され、やがて入力圧縮データストリームが使い果たされる。そして、伸長処理は完了する。
図１４は、図１２及び図１３の混成技法を使用するテキスト圧縮の例である。この例においては、アルファベットは７個のキャラクタ（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ）を含み、圧縮されるべきデータは“ＡＢＣＢＤＥＦＧＡＢＣ”であると仮定される。図示のように、圧縮辞書は、初期において、多発シーケンス“ＡＢＣ”及び“ＤＥＦ”を含むが、これらの多発シーケンスは、上述の技術のいずれかを使用して、又は、当業者に明らかであるような、他の統計に基礎を置く技術から、決定されたものである。図１４は、圧縮が達成された方法を示しており、３つのオプション、すなわちプレフィル辞書、ＬＺ７７リファレンス、及びＬＺ７７文字がある。図１４の例では、何らのキャラクタイクステンションも使用されない。圧縮の間、次の情報が文字であるか、又は辞書リファレンス若しくはＬＺ７７リファレンスのいずれかであるかを示すために１ビットが使用される。後者の２つのオプションは、共通アドレス空間を共有するが、ＬＺ７７スタイルリファレンスが使用されるならば長さのみが使用される。
図１４に示されるように、圧縮の開始においては、圧縮が始まるキャラクタへのポインタは、圧縮されているテキストのシーケンスにおける最初のキャラクタに置かれる。ステップ０では、圧縮辞書において最長一致が発見され、このエントリ（Ｄ０）へのポインタが、送出され、圧縮アルゴリズムの応用に依存して局所的に格納される。次いで、そのポインタが、送出されたキャラクタの数によって移動せしめられる。ステップ１では、“Ｂ”も“ＢＤ”も圧縮辞書内にないため、ＬＺ７７リファレンスが送出される。そのフラグは、ＬＺ７７リファレンス（２，１）が送られることを示すが、ここで、“２”は現ウィンドウ内の第２のエントリへのポインタであり、“１”は長さである。次いで、そのポインタは、ステップ２に先立って１キャラクタだけ移動せしめられる。ステップ２では、圧縮辞書内で最長一致が発見され、このエントリ（Ｄ１）へのポインタが、送出され、圧縮アルゴリズムの応用に依存して局所的に格納される。次いで、そのポインタは、ステップ３に先立って、送出されたキャラクタの数だけ移動せしめられる。ステップ３では、圧縮ウィンドウ又は圧縮辞書の中にキャラクタ“Ｇ”がないため、ＬＺ７７文字が送られる。次いで、ステップ４に先立って、ポインタが１キャラクタ移動せしめられる。ステップ４では、圧縮辞書内で最長一致が発見され、このエントリ（Ｄ０）へのポインタが、圧縮アルゴリズムの応用に依存して送出又は格納される。次いで、送出されたキャラクタの数だけポインタが移動せしめられる。ステップ４では、ＬＺ７７ポインタリファレンスよりも安いと仮定されたため、ウィンドウエントリの代わりに辞書エントリが使用された。圧縮されるべきテキストの終わりにポインタがあるため、符号化処理は完了する。
送出される文字、長さ、及びアドレスへの圧縮のいくつかの形式を適用すること、送出される必要がある文字がないように辞書又はウィンドウをシード（seed）すること等、ＬＺ７７への標準的な改良のいずれもが、ＬＺ７７圧縮技術のイクステンションである上述の実施例のいずれにも等しく適用されることができる。また、上述のように、種々の辞書（又はウィンドウにプリペンドする種々のテキスト）が、送出されるデータの種々のジャンルに対して使用されることができる。各メッセージの始めに送られる初期のコード番号は、次いで、どの辞書又はブリペンドされたテキストが使用されているか（例えば、英語散文用、コンピュータソフトウェア用、又はビジネス業務用のもの）を示し、あるいは、辞書又はブリペンドされたテキストが先に送出されたテキストから特別に導かれたことを示す特殊なコードが送出されるであろう。
本発明の技術の実現例においては、プレフィルされたデータ圧縮辞書のセットが、定期的に圧縮ドキュメントをそれらの間で交換する数多くのサーバに分配される。上述のように、それらの辞書は、送出コストを節約するために分配の前に結合されてもよい。周期的に、プレフィル辞書の新しいセットが、プレフィル辞書の古いセットを補うために分配される。その新しいセットは、新しいジャンルに関する辞書、及び用語の変化を反映する古いジャンルに関する、より最新の辞書を含むであろう。理想的には、新しい辞書は、古い辞書と実質的に重なるように構築され、それによって、全ての新しい辞書及び古い辞書に関する結合された表現は、古い辞書のみに関する結合された表現とあまり異ならない。次いで、プレフィル辞書の２つの表現間の変化を列記するファイルが、分配される。このファイルを受信すると、サーバの各々は、新しい辞書を加えるために結合された辞書表現をモーデファイする。古い辞書は、もはや、古いファイルを伸長するために必要となるか否かに依存して、結合された表現に保存されてもよいし、それから削除されてもよい。かかる技術は、特に同じジャンルのファイルをしばしば交換する２つのサーバ間で、実質的にデータ送出及び記憶コストの減少につながる。
例えば、本発明のシミュレーションが、データの全部の半分を使用して行われた。比較のために、“ｇｚｉｐ”、“ｇｚｉｐ”のシミュレーション、及び本発明によるプレフィル辞書を有する“ｇｚｉｐ”のシミュレーションを使用して、当該データが圧縮された。本発明によるプレフィル辞書とともに使用されるように“ｇｚｉｐ”がモデファイされねばならないため、一つのシミュレーションが使用された。“ｇｚｉｐ”のシミュレーションがプレフィル辞書なしでテストされたが、これは、プレフィル辞書の追加の前に“ｇｚｉｐ”の性能をそのシミュレーションが概算したことを単に証明するためである。次の結果が得られた。
ｇｚｉｐによる圧縮パーセンテージ： ５０．６
シミュレーションによる圧縮パーセンテージ： ５０．７
辞書を使用するシミュレーションによる圧縮パーセンテージ：６２．８
当業者は、ファイルサイズにおける１２パーセンテージポイントの減少が相当なものであることを評価するであろう。この例では、このことは、ほぼ２５％のメモリ節約に達する。
本発明の多数の実施例及び本発明概念の多数の拡張が述べられてきたが、当業者は、本発明の新規な教え及び利益から実質的に逸脱することなく、当該例示的な実施例において多くの追加のモデファイが可能であることを容易に理解するであろう。
例えば、上記のように、本発明のプレフィル辞書は、任意の数多くの方法で形成されることができ、また、基本のＬｅｍｐｅｌ−Ｚｉｖ圧縮技術についての任意の数多くの変形版とともに使用されることができる。さらに、圧縮性能は、プレフィルデータ圧縮辞書及びデータ特定圧縮辞書の圧縮性能をモニタし追跡することによって最適化されることができる。例えば、プレフィルデータ圧縮辞書がデータ特定圧縮辞書よりも良好なデータ圧縮を提供していないならば、データ特定辞書が満杯になってリセットされる必要がある場合に、プレフィルデータ圧縮辞書はデータ特定辞書によって置き換えられ、データ特定辞書はリセットされる。他方、プレフィルデータ圧縮辞書が圧縮に関しより有用であるならば、それは保持され、データ特定圧縮辞書はリセットされる。どちらの辞書が他方の辞書よりも良好な圧縮を提供しているかを決定するために、各辞書に関連する節約が、圧縮の進行中に維持される。各辞書を使用して圧縮された各列の長さがまた保持されるが、それは、各辞書にもたらされた圧縮の部分から結果として生ずるデータの量である。データ特定辞書が更に成長するのを許容する方がベターであるほど、プレフィル辞書がほとんど改良を生み出さないといわれるよりも以下のしきい値が選択される。これは、（できるかぎり圧縮されたドキュメント全体について）包括的に、及び、これらのデータのいくつかの異なるセットを維持することによって局所的に、なされる。実際には、この処理によって、プレフィルデータ圧縮辞書及びデータ特定圧縮辞書にもたらされたアドレス空間全体が、プレフィル辞書が圧縮処理に改良を提供していないときにデータ特定辞書によって利用されることが可能となる。
さらに、米国特許第４８７６５４１号でＳｔｏｒｅｒが記載したタイプのｌｅａｓｔ ｒｅｃｅｎｔ ｕｓｅｄ（ＬＲＵ）法は、一番最近に使用されたエントリが、それがどの辞書から来たかにかかわらず、常に棄てられるため、２つの辞書を分離しておくのを不要にする。このコンテクストにおいて、「使用（used）」は、圧縮データストリームの一部としてコードをリードし又はライトすることを含むが、その列の最初の出現での辞書へのコードのエントリは、「使用」としてカウントされてもされなくてもよい。
加えて、データ特定辞書のサイズを減少せしめることを犠牲にして、多重のプレフィルデータ圧縮辞書が圧縮処理において使用されてもよい。極端なケースでは、データ特定辞書が完全に消去され、プレフィル辞書及びデータ特定辞書によって通常共有されるアドレス空間全体が、関連するプレフィル辞書によって共有される。もちろん、この場合には、圧縮されるべきテキスト内の全てのキャラクタシーケンス、ワード、及びフレーズが、１又はそれより多くのプレフィルデータ圧縮辞書内に存在する必要があるが、このことは、プレフィル辞書が、圧縮されるべきテキストにおいて発生しうるキャラクタの全ての組合せを含むのに十分なほど大きいときに、可能である。さらに、たとえプレフィルデータ圧縮辞書内でキャラクタの全ての組合せが発見されなくとも、発見されなかった組合せは圧縮されていないまま単に格納されうるか、及び／又は、プレフィル辞書はそのキャラクタ組合せを含むように圧縮中に更新されうるであろう。他方、プレフィル辞書が形成される元となるドキュメントの集合の頻度分析を行う、図６に関して説明されたソフトウェアによって作成されたプレフィルデータ圧縮辞書内にキャラクタセット全体が存在するかどうかを決定するために、一つのアルゴリズムが使用されうるであろう。キャラクタの全てが存在しない場合には、不在のキャラクタがプレフィルデータ圧縮辞書内に挿入される一方、最も発生しないコードワードが消去され、それによって、次のキャラクタが辞書にないことを示すのにエスケープキャラクタが必要でないことが保証される。
本発明の好適な実施例に対する別の修正版として、辞書エントリのコードワードアドレスが、Ｈｕｆｆｍａｎ符号化のような技術を使用して符号化され、より頻繁に使用されるアドレスがより少ないビットを使用して表されることができる。同様に、イクステンションキャラクタが、Ｈｕｆｆｍａｎ符号化のような可変長符号化を使用して符号化されることにより、性能が改善される。そのようなケースにおいては、データ特定辞書のサイズを制限する必要はなく、したがって、Ｌｅｍｐｅｌ−Ｚｉｖコードワードが正に整数であるため、データ特定辞書をさらに起動する必要はない。これらの整数は、次いで、可変長ビットシーケンスによって符号化される。さらに、これらの整数のコードワードの分配がドキュメントを通して変化することにより、その局所的エントロピーがその包括的エントロピーよりも下回るならば、適応Ｈｕｆｆｍａｎ符号化又は適応算術符号化のような、可変長符号化スキームの適応バージョンが使用されるべきである。
この技術によれば、コードワードに関する符号化を使用して送出されているコードの長さが知られ、また、辞書内のコードワードの数に基づくものとなる。最近使用されたコードワードのリストは保持されることができ、コードワードスキームの圧縮においてもたらされたコートワードの空間全体の小さなサブセットを、最近使用されたコードワードが形成するようなときにおいては、これらのコードワードの圧縮がリスタートされる。この新しい辞書は、最近使用されたコードワードが局所的に再びより使用されそうである一方、最近使用されていないものは再び使用されそうもない、という仮定で、最近使用されたコードワードから構成されることができる。
当業者は、また、特定のドキュメントの圧縮中に作成されるデータ特定圧縮辞書を、他の関連するドキュメントの圧縮に使用するプレフィルデータ圧縮辞書として、格納することを選択することができる。他方、データ特定辞書は、特定のエントリが他のプレフィルデータ圧縮辞書に含まれているかどうかを決定するために、使用されることができる。
したがって、全てのかかる修正は、次の請求の範囲に定義された、この発明の範囲に含まれるものである。

Claims (42)

1. キャラクタシーケンスを包含するテキストを圧縮するためのデータ圧縮方法であって、
   （ａ）異なるタイプおよび／またはジャンルのテキストに対して利用可能なプレフィルデータ圧縮辞書のうちのどの１つが前記キャラクタシーケンスに対して最大圧縮をもたらすかを判定し、前記テキストを圧縮するのに使われる１つのプレフィルデータ圧縮辞書選択するステップ、
   （ｂ）圧縮のため、前記キャラクタシーケンス中の最初のキャラクタにポインタを初期設定するステップ、
   （ｃ）前記ポインタからスタートするキャラクタと前記１つのプレフィルデータ圧縮辞書中に格納されたキャラクタシーケンスとを比較し、前記ポインタから始まるキャラクタと前記１つのプレフィルデータ圧縮辞書中に格納されたキャラクタシーケンスとの最長一致を決定するステップ、
   （ｄ）前記最長一致を呈する前記キャラクタの圧縮された表現として、前記最長一致への辞書ポインタを、メモリ中の前記１つのプレフィルデータ圧縮辞書中に格納するステップ、
   （ｅ）前記最長一致に続く前記キャラクタシーケンス中のキャラクタに前記ポインタを移動するステップ、及び
   （ｆ）圧縮されるべき前記キャラクタシーケンス中の全てのキャラクタについてステップｃ〜ｅを繰り返すステップ、
   を備えるデータ圧縮方法。
2. 請求項１に記載のデータ圧縮方法であって、
   少なくとも１つのキャラクタサンプルシーケンス中のキャラクタシーケンスの発生頻度を決定するために、圧縮されるべきキャラクタシーケンスの表現である前記少なくとも１つのサンプルキャラクタシーケンス中の前記キャラクタシーケンスを解析するステップ、及び
   前記所定の組合せとして、前記少なくとも１つのキャラクタサンプルシーケンス中に最も多発する、前記少なくとも１つのキャラクタサンプルシーケンス中のこれらのキャラクタシーケンスを選択するステップ、
   を実行することにより、前記１つのプレフィルデータ圧縮辞書を選択するステップの前に前記１つのプレフィルデータ圧縮辞書を生成するステップを更に備えるデータ圧縮方法。
3. 請求項２に記載のデータ圧縮方法であって、前記解析するステップは、前記少なくとも１つのキャラクタサンプルシーケンス中の前記キャラクタシーケンスの各々の発生数を決定するステップ、及び、各キャラクタシーケンスについて、前記各キャラクタシーケンスの発生数と、前記各キャラクタシーケンスのビット長と前記辞書ポインタのビット長の差との積を演算するステップを含むデータ圧縮方法。
4. 請求項３に記載のデータ圧縮方法であって、前記所定の組合せを選択するステップは、前記１つのプレフィルデータ圧縮辞書へ格納するために、前記積を演算するステップ中で決定された最大の積を有するこれらのデータシーケンスを選択するステップを含むデータ圧縮方法。
5. 請求項４に記載のデータ圧縮方法であって、更に、完全なキャラクタセットが前記１つのプレフィルデータ圧縮辞書中に存在するか否かを決定するステップ、及び、前記完全なキャラクタセット中の全てのキャラクタが、前記１つのプレフィルデータ圧縮辞書中に存在しないという場合において、新たな辞書エントリとして、前記１つのプレフィルデータ圧縮辞書に存在しない前記キャラクタセットのこれらのキャラクタを、前記積を演算するステップで決定された最小の積を有する辞書のエントリに代えて、前記１つのプレフィルデータ圧縮辞書中に挿入するステップを含むデータ圧縮方法。
6. 請求項１に記載のデータ圧縮方法であって、前記１つのプレフィルデータ圧縮辞書を選択するステップは、複数の異なるプレフィルデータ圧縮辞書の内のどの１つが前記キャラクタサブセットに対して最大の圧縮をもたらすかを決定するため、前記複数の異なるプレフィルデータ圧縮辞書に対して、圧縮されるべき前記データキャラクタシーケンスのサブセットキャラクタについてステップｂ〜ｅを実行するステップ、及び、前記キャラクタシーケンスの圧縮に使用するため、前記１つのプレフィルデータ圧縮辞書として、前記１つのプレフィルデータ圧縮辞書を選択するステップを含むデータ圧縮方法。
7. 請求項６に記載のデータ圧縮方法であって、前記１つのプレフィルデータ圧縮辞書を選択する前記のステップは、圧縮されるべき前記データキャラクタシーケンスの前記キャラクタサブセットについてステップｂ〜ｅを実行する間に、空のデータ圧縮辞書によるスタートが前記データキャラクタシーケンスの最大の圧縮を許可することが決定されるイベントにおいて、空のデータ圧縮辞書を選択するステップを含むデータ圧縮方法。
8. 請求項１に記載のデータ圧縮方法であって、更に、（ｇ）前記最長一致を呈する前記キャラクタの前記圧縮された表現として、受け側に前記辞書ポインタを送出するステップを含むデータ圧縮方法。
9. 請求項８に記載のデータ圧縮方法であって、前記１つのプレフィルデータ圧縮辞書を選択するステップは、前記プレフィルデータ圧縮辞書がステップｇの送出されたデータの受け側が利用可能であるか否かに基づいて、複数のプレフィルデータ圧縮辞書から１つのプレフィルデータ圧縮辞書を選択するステップを更に含むデータ圧縮方法。
10. 請求項１に記載のデータ圧縮方法であって、前記１つのプレフィルデータ圧縮辞書を選択するステップは、圧縮されるべき前記キャラクタシーケンスの圧縮の間に使用するための複合的なプレフィルデータ圧縮辞書を選択するステップを含むデータ圧縮方法。
11. 請求項１に記載のデータ圧縮方法であって、更に、前記辞書ポインタがより少ないアドレスビットを使用して表現されるように、前記辞書ポインタを符号化するステップを含むデータ圧縮方法。
12. 請求項１に記載のデータ圧縮方法であって、更に、前記最長一致を呈する前記キャラクタの圧縮された表現と共に、伸長処理の間に使用されるべきプレフィルデータ圧縮辞書へ、リファレンスを格納するステップを含むデータ圧縮方法。
13. 請求項１に記載のデータ圧縮方法であって、更に、テキストデータの異なるジャンルを包含する複数のプレフィルデータ圧縮辞書を格納するステップを含み、前記１つのプレフィルデータ圧縮辞書を選択するステップは、前記複数のプレフィルデータ圧縮辞書から前記１つのプレフィルデータ圧縮辞書を選択するステップを含み、それにより、選択されたプレフィルデータ圧縮辞書が、前記圧縮されるべき前記キャラクタシーケンスに最も類似するジャンルからデータを包含するデータ圧縮方法。
14. 請求項１３に記載のデータ圧縮方法であって、前記複数のプレフィルデータ圧縮辞書を格納する前記ステップは、対応するプレフィルデータ圧縮辞書内に包含されたテキストデータのジャンルにより、前記複数のプレフィルデータ圧縮辞書を階層的に配列するステップを含むデータ圧縮方法。
15. 請求項１３に記載のデータ圧縮方法であって、前記複数のプレフィルデータ圧縮辞書を格納するステップは、記憶メディア上に一度だけ前記複数のプレフィルデータ圧縮辞書の共通のエントリを格納するステップを含み、前記複数のプレフィルデータ圧縮辞書により、前記共通のエントリが割当てられるデータ圧縮方法。
16. キャラクタシーケンスの圧縮された表現を伸長する方法であって、前記圧縮された表現は、ポインタからスタートし、プレフィルデータ圧縮辞書中に格納されたキャラクタシーケンスにより前記キャラクタシーケンス中の特定のキャラクタまでのキャラクタシーケンスのそれぞれの最長一致に対する辞書ポインタを具備し、前記プレフィルデータ圧縮辞書は、前記キャラクタシーケンス中に多発しそうな所定のキャラクタの組合せを収納する方法において、
    利用可能なプレフィルデータ圧縮辞書のうちのどの１つが前記キャラクタシーケンスに対して最大圧縮をもたらすかを判定し、前記テキストを圧縮するのに使われる１つのプレフィルデータ圧縮辞書を選択することにより、圧縮の前に前記プレフィルデータ圧縮辞書が選択され、かつ、該方法は、
    （ａ）前記キャラクタの前記圧縮された表現中の第１の辞書ポインタへポインタを移動するステップ、
    （ｂ）前記ポインタにより示される前記辞書ポインタを使用して前記１つのプレフィルデータ圧縮辞書から辞書エントリを検索するステップ、
    （ｃ）前記最長一致を呈するキャラクタの伸長された表現として、前記辞書エントリを格納するステップ、
    （ｄ）前記キャラクタの前記圧縮された表現中の次の辞書ポインタに前記ポインタを移動するステップ、及び
    （ｅ）前記キャラクタシーケンス中の全ての圧縮されたキャラクタが伸長されるまで、前記キャラクタの前記圧縮された表現中の全ての辞書ポインタについてステップｂ〜ｄを繰り返すステップ、
    を備える方法。
17. 請求項１６に記載の方法であって、更に、前記キャラクタの前記圧縮された表現から、少なくとも、（１）伸長の間に使用するための前記１つのプレフィルデータ圧縮辞書の一致性、及び（２）前記キャラクタの前記圧縮された表現を伸長するために使用されるLempel-Zivアルゴリズム変形版の指示、を抽出するステップを備える方法。
18. キャラクタのシーケンスの圧縮された表現を伸長する方法であって、該圧縮された表現は、（１）ウィンドウポインタ及び前記キャラクタのシーケンス内での特定のキャラクタへのポインタでスタートするキャラクタのシーケンスの、所定のサイズのキャラクタウィンドウ内のキャラクタのシーケンスとのそれぞれの最長一致の長さ、及び（２）プレフィルデータ伸長辞書内の特定のキャラクタへの前記ポインタでスタートするキャラクタのシーケンスのそれぞれの最長一致の辞書エントリ番号をそなえ、前記プレフィルデータ圧縮辞書は前記キャラクタのシーケンス内で多発しそうなキャラクタの所定の組合せを包含しており、前記伸長方法は、
    （ａ）前記キャラクタの前記圧縮された表現内での第１のエントリへポインタを初期設定し、
    （ｂ）該ポインタによって指示された前記キャラクタの前記圧縮された表現内での現エントリが、（１）ウィンドウポインタ及び長さであるか（２）辞書エントリ番号であるかを決定し、
    （ｃ）前記現エントリがウィンドウポインタ及び長さであれば、前記ウィンドウポインタによって指示された現キャラクタウィンドウ内のキャラクタでスタートする前記長さによって決定されるキャラクタの数を検索し、
    （ｄ）前記現エントリが辞書エントリ番号であれば、該辞書エントリ番号によって特定された前記プレフィルデータ伸長辞書内の辞書エントリにおいてキャラクタを検索し、
    （ｅ）各ステップｃ又はｄにおいて検索されたキャラクタを、現エントリについての最長一致を呈するキャラクタの伸長された表現として格納し、
    （ｆ）前記ポインタを前記キャラクタの前記圧縮された表現内での次のエントリまで移動させ、
    （ｇ）前記キャラクタのシーケンス内でのすべての圧縮されたキャラクタが伸長されるまで、前記キャラクタの前記圧縮された表現内でのすべてのエントリについて各ステップｂ〜ｆを繰返す、
    各ステップをそなえている方法。
19. キャラクタのシーケンスを含むテキストを圧縮するためのデータ圧縮システムであって、
    前記キャラクタのシーケンス内で多発しそうなキャラクタの所定の組合せを包含する少なくとも１つのプレフィルデータ圧縮辞書、
    前記テキストが圧縮された後該テキストを格納するメモリ、及び
    （ａ）異なるタイプおよび／またはジャンルのテキストに対して利用可能なプレフィルデータ圧縮辞書のうちのどの１つが前記キャラクタシーケンスに対して最大圧縮をもたらすかを判定し、前記テキストを圧縮するのに使われる１つのプレフィルデータ圧縮辞書を選択し、（ｂ）圧縮のための前記キャラクタのシーケンス内での第１のキャラクタにポインタを初期設定し、（ｃ）前記ポインタでスタートするキャラクタを前記１つのプレフィルデータ圧縮辞書に格納されたキャラクタのシーケンスと比較して、前記ポインタでスタートする前記キャラクタの、前記１つのプレフィルデータ圧縮辞書に格納された前記キャラクタのシーケンスとの最長一致を決定し、（ｄ）前記１つのプレフィルデータ圧縮辞書内の前記最長一致への辞書ポインタを、前記最長一致を呈する前記キャラクタの圧縮された表現として前記メモリ内に格納し、（ｅ）前記最長一致に続く前記キャラクタのシーケンス内のキャラクタに前記ポインタを移動させ、（ｆ）圧縮されるべき前記キャラクタのシーケンス内のすべてのキャラクタについて各ステップｂ〜ｄを繰返す、各ステップを実行する圧縮手段、
    をそなえているデータ圧縮システム。
20. 前記１つのプレフィルデータ圧縮辞書を生成するプレフィルデータ圧縮辞書生成手段であって、前記１つのプレフィルデータ圧縮辞書は、該１つのプレフィルデータ圧縮辞書に、圧縮されるべきキャラクタのシーケンスを代表する少なくとも１つのキャラクタのサンプルシーケンス内で最も多発するキャラクタの組合せを挿入するプレフィルデータ圧縮辞書生成手段を更にそなえている、請求項１９に記載のシステム。
21. 前記プレフィルデータ圧縮辞書生成手段は、前記１つのプレフィルデータ圧縮辞書に、圧縮されるべきキャラクタのシーケンスを代表する少なくとも１つのキャラクタのサンプルシーケンス内でのキャラクタの組合せを挿入するものであり、該圧縮されるべきキャラクタのシーケンスは、（ａ）前記少なくとも１つのキャラクタのサンプルシーケンスにおけるキャクラタの前記組合せの各々の発生数と、（ｂ）各前記キャラクタの組合せのビット長及び前記辞書ポインタのビット長の差と、の最大の積を有する、請求項２０に記載のシステム。
22. 前記プレフィルデータ圧縮辞書生成手段は、圧縮されるべき前記キャラクタのシーケンスの全キャラクタの集合が前記１つのプレフィルデータ圧縮辞書内に存在するかどうかを決定し、前記全キャラクタの集合内でのすべてのキャラクタが圧縮されるべき前記キャラクタのシーケンス内に存在しない場合には、前記１つのプレフィルデータ圧縮辞書から欠けている前記キャラクタの集合内の各キャラクタを、前記１つのプレフィルデータ圧縮辞書内に、前記プレフィルデータ圧縮辞書生成手段によって決定される最小の積を有する辞書エントリの代りに新しい辞書エントリとして挿入する、請求項２１に記載のシステム。
23. 前記１つのプレフィルデータ圧縮辞書は多数のプレフィルデータ圧縮辞書の１つであり、該１つのプレフィルデータ圧縮辞書は、前記多数のプレフィルデータ圧縮辞書の残りの各々によって前記データキャラクタのシーケンスのうちの各キャラクタのサブセットに提供される圧縮より、圧縮されるべき前記データキャラクタのシーケンスのうちの各キャラクタのサブセットについてより多くの圧縮を提供する各キャラクタの組合せを包含する、請求項１９に記載のシステム。
24. 前記メモリは前記圧縮手段から離れた位置にあり、前記辞書ポインタを、前記最長一致を呈する前記キャラクタの前記圧縮された表現として、前記圧縮手段から前記メモリまで伝送する手段を更にそなえている、請求項１９に記載のシステム。
25. 前記１つのプレフィルデータ圧縮辞書は、前記離れた位置でも利用しうる多数のプレフィルデータ圧縮辞書のうちの１つである、請求項１９に記載のシステム。
26. 前記圧縮手段は、前記辞書ポインタがより少ないアドレスビットを用いて表現されうるように前記辞書ポインタを符号化する手段をそなえている、請求項１９に記載のシステム。
27. 前記圧縮手段は、前記最長一致を呈する前記キャラクタの前記圧縮された表現を用いて、前記メモリ内に、伸長処理中に使用されるべきプレフィルデータ圧縮辞書へのリファレンスを格納する、請求項１９に記載のシステム。
28. 前記メモリは、ハードディスク、ＲＡＭ，ＣＤ ＲＯＭ、フロッピーディスク（登録商標）、及び光ディスクのうちの少なくとも１つをそなえている、請求項１９に記載のシステム。
29. テキストデータの異なる形式を含む複数のプレフィルデータ圧縮辞書を格納する辞書メモリを更にそなえ、それによって前記テキストを圧縮するために使用されるプレフィルデータ圧縮辞書は、最も類似した形式から圧縮されるべき前記キャラクタのシーケンスまでのデータを包含する、請求項１９に記載のシステム。
30. 前記複数のプレフィルデータ圧縮辞書は、それぞれのプレフィルデータ圧縮辞書内に含まれるテキストデータの形式によって階層的に前記メモリ内に配列されている、請求項１９に記載のシステム。
31. 前記複数のプレフィルデータ圧縮辞書は、前記複数のプレフィルデータ圧縮辞書内の共通エントリが前記メモリ内に１度だけ格納されて前記複数のプレフィルデータ圧縮辞書によって共用されるように、前記メモリ内に格納されている、請求項１９に記載のシステム。
32. キャラクタのシーケンスを含むテキストを圧縮するためのデータ圧縮システムであって、
    前記キャラクタのシーケンスにおいて多発しそうなキャラクタの所定の組合せを含むプレフィルデータ圧縮辞書、
    データ特定用データ圧縮辞書、
    テキストが圧縮された後該テキストを格納するメモリ、及び
    （ａ）圧縮のための前記キャラクタのシーケンス内での第１のキャラクタにポインタを初期設定し、（ｂ）前記ポインタでスタートするキャラクタを前記プレフィルデータ圧縮辞書及び前記データ特定用データ圧縮辞書内に格納されたキャラクタのシーケンスと比較して、前記プレフィルデータ圧縮辞書及び前記データ特定用データ圧縮辞書内に格納された前記キャラクタのシーケンスとの、前記ポインタでスタートする前記キャラクタの最長一致の辞書エントリ番号を決定し、（ｃ）前記辞書エントリ番号及びイクステンションキャラクタを、前記最長一致を呈する前記キャラクタ及び前記イクステンションキャラクタの圧縮された表現として前記メモリ内に格納し、前記イクステンションキャラクタは前記ポインタでスタートする前記最長一致の後に発生する、圧縮されるべき前記キャラクタのシーケンス内でのキャラクタであり、（ｄ）前記最長一致を呈する前記キャラクタ及び前記イクステンションキャラクタを新しい辞書エントリとして前記データ特定用データ圧縮辞書内に選択的に格納し、（ｅ）前記イクステンションキャラクタに続く前記キャラクタのシーケンス内のキャラクタに前記ポインタを移動させ、（ｆ）圧縮されるべき前記キャラクタのシーケンス内のすべてのキャラクタについて各ステップｂ〜ｅを繰返す、各ステップを実行する圧縮手段、
    をそなえているデータ圧縮システム。
33. 前記圧縮手段は、前記キャラクタのシーケンスを圧縮する間前記プレフィルデータ圧縮辞書及び前記データ特定データ圧縮辞書の圧縮能力をモニタする手段、前記キャラクタのシーケンスを圧縮する間に前記データ特定データ圧縮辞書が満杯になった時前記モニタ手段によって決定されたデータ圧縮辞書をより小さいデータ圧縮能力を提供するようにリセットする手段、及び前記モニタ手段によって決定されたデータ圧縮辞書をより大きいデータ圧縮能力を提供するように、圧縮されるべき前記キャラクタのシーケンス内の後続するキャラクタの圧縮のための前記プレフィルデータ圧縮辞書に置き換える手段を更にそなえている、請求項３２に記載のシステム。
34. 前記プレフィルデータ圧縮辞書及び前記データ特定データ圧縮辞書は共通メモリを共有し、前記データ特定データ圧縮辞書は前記キャラクタのシーケンスを圧縮する間そこに格納された新しい辞書エントリとともに、異なるテキストの異なるキャラクタのシーケンスの圧縮に使用するためのプレフィルデータ圧縮辞書の少なくとも一部として前記共通メモリに格納される、請求項３２に記載のシステム。
35. テキストデータの異なる形式を含む複数のプレフィルデータ圧縮辞書を格納する辞書メモリを更にそなえ、それによって前記テキストを圧縮するために使用されるプレフィルデータ圧縮辞書が、最も類似した形式から圧縮されるべき前記キャラクタのシーケンスまでのデータを包含する、請求項３２に記載のシステム。
36. 前記圧縮手段が、前記テキストを圧縮する間に格納されたデータ特定データ圧縮辞書エントリを前記異なるテキストを圧縮するためのプレフィルデータ圧縮辞書として用いて、前記テキストと同じ形式とは異なるテキストについて各ステップｂ〜ｅを繰返す、請求項３５に記載のシステム。
37. キャラクタのシーケンスを含むテキストを圧縮するためのデータ圧縮システムであって、
    前記キャラクタのシーケンス内で多発しそうなキャラクタの所定の組合せを包含するプレフィルデータ圧縮辞書、
    所定数のキャラクタを含むキャラクタウィンドウ、
    テキストが圧縮された後該テキストを格納する圧縮されたデータメモリ、及び
    （ａ）圧縮のための前記キャラクタのシーケンス内の第１のキャラクタにポインタを初期設定し、（ｂ）前記ポインタでスタートするキャラクタを前記プレフィルデータ圧縮辞書及び前記キャラクタウィンドウ内のキャラクタのシーケンスと比較して、前記プレフィルデータ圧縮辞書内に格納された前記キャラクタのシーケンス及び前記キャラクタウィンドウ内のキャラクタのシーケンスとの、前記ポインタでスタートする前記キャラクタの最長一致を決定し、（ｃ）前記ポインタでスタートする前記キャラクタを前記プレフィルデータ圧縮辞書内に格納された前記キャラクタのシーケンスとの、前記ポインタでスタートする前記キャラクタの最長一致の辞書エントリ番号として表現することによって、又は前記キャラクタウィンドウ内の前記キャラクタのシーケンスとの、前記ポインタでスタートする前記キャラクタの最長一致の長さ及びウィンドウポインタとして前記ポインタでスタートする前記キャラクタを表現することによって、より大きい圧縮がえられるかどうかを決定し、（ｄ）ステップｃにおいてより大きい圧縮が、前記キャラクタウィンドウ内の前記キャラクタのシーケンスとの、前記ウィンドウポインタでスタートする前記キャラクタの前記最長一致の前記長さ及び前記ウィンドウポインタとして前記ポインタでスタートする前記キャラクタを表現することによってえられることが決定される時、前記最長一致を呈する前記キャラクタの圧縮された表現として前記圧縮されたデータメモリ内に前記最長一致の前記長さ及び前記ウィンドウポインタを格納し、さもなければ前記プレフィルデータ圧縮辞書内に格納された前記キャラクタのシーケンスとの、前記ポインタでスタートする前記キャラクタの前記最長一致の前記辞書エントリ番号を格納し、（ｅ）前記最長一致を呈するキャラクタを含ませるために前記キャラクタウィンドウを更新し、（ｆ）前記最長一致に続く前記キャラクタのシーケンス内のキャラクタまで前記ポインタを移動させ、（ｇ）圧縮されるべき前記キャラクタのシーケンス内のすべてのキャラクタについて各ステップｂ〜ｆを繰返す、各ステップを実行する圧縮手段、
    をそなえているデータ圧縮システム。
38. 前記圧縮されたデータメモリは前記圧縮手段から離れた位置にあり、前記キャラクタウィンドウ内の前記キャラクタのシーケンスとの、前記ウィンドウポインタでスタートする前記キャラクタの前記最長一致の前記長さ及び前記ウィンドウポインタとして前記ポインタでスタートする前記キャラクタを表現することによってより大きい圧縮がえられることがステップｃにおいて前記圧縮手段によって決定される時、前記最長一致の前記長さ及び前記ウィンドウポインタを前記圧縮されたデータメモリに伝送する手段を更にそなえ、さもなければ前記プレフィルデータ圧縮辞書内に格納された前記キャラクタのシーケンスとの、前記ポインタでスタートする前記キャラクタの前記最長一致の前記辞書エントリ番号を前記圧縮されたデータメモリに伝送する、請求項３７に記載のシステム。
39. キャラクタのシーケンスの圧縮された表現を伸長するデータ伸長システムであって、前記圧縮された表現はプレフィルデータ圧縮辞書内に格納されたキャラクタのシーケンスとの、前記キャラクタのシーケンス内での特定のキャラクタへのポインタでスタートするキャラクタのシーケンスのそれぞれの最長一致への辞書ポインタをそなえるデータ伸長システムにおいて、
    利用可能なプレフィルデータ圧縮辞書のうちのどの１つが前記キャラクタシーケンスに対して最大圧縮をもたらすかを判定し、前記テキストを圧縮するのに使われる１つのプレフィルデータ圧縮辞書を選択することにより、圧縮の前に前記プレフィルデータ圧縮辞書が選択され、かつ、該データ伸長システムは、
    前記キャラクタのシーケンスの前記圧縮された表現を格納する圧縮されたデータメモリ、
    伸長後前記キャラクタのシーケンスを格納する伸長されたデータメモリ、及び
    （ａ）前記圧縮されたデータメモリ内の前記キャラクタの前記圧縮された表現内の第１の辞書ポインタへポインタを初期設定し、（ｂ）前記ポインタによって指示された前記辞書ポインタを用いて前記１つのプレフィルデータ圧縮辞書から辞書エントリを検索し、（ｃ）前記辞書エントリを前記最長一致を呈するキャラクタの伸長された表現として前記伸長されたデータメモリ内に格納し、（ｄ）前記キャラクタの前記圧縮された表現内での次の辞書ポインタへ前記ポインタを移動させ、（ｅ）前記キャラクタのシーケンス内のすべての圧縮されたキャラクタが伸長されるまで前記圧縮されたデータメモリ内での前記キャラクタの前記圧縮された表現内のすべての辞書ポインタについて各ステップｂ〜ｄを繰返す、各ステップを実行する伸長手段、
    をそなえているデータ伸長システム。
40. 前記伸長手段は、前記圧縮されたデータメモリ内の前記キャラクタの前記圧縮された表現から、（１）前記伸長手段による伸長の間使用するための１つのプレフィルデータ圧縮辞書の一致性、及び（２）前記圧縮されたデータメモリ内の前記キャラクタの前記圧縮された表現を伸長するために使用されるべきＬｅｍｐｅｌ−Ｚｉｖアルゴリズム変形版の指示、のうちの少なくとも１つを抽出する手段をそなえている、請求項３９に記載のシステム。
41. キャラクタのシーケンスの圧縮された表現を伸長するデータ伸長システムであって、前記圧縮された表現は、プレフィルデータ圧縮辞書及びデータ特定データ圧縮辞書内に格納されたキャラクタのシーケンスとの、前記キャラクタのシーケンス内の特定のキャラクタへのポインタでスタートするキャラクタのシーケンスのそれぞれの最長一致の辞書エントリ番号及びイクステンションキャラクタをそなえ、前記イクステンションキャラクタは前記ポインタでスタートする最長一致の後に発生するキャラクタのシーケンス内のキャラクタであり、前記プレフィルデータ圧縮辞書は前記キャラクタのシーケンス内で多発しそうなキャラクタの所定の組合せを包含しており、前記データ伸長システムは、
    前記キャラクタのシーケンスの前記圧縮された表現を格納する圧縮されたデータメモリ、
    伸長後の前記キャラクタのシーケンスを格納する伸長されたデータメモリ、及び
    （ａ）データ特定データ伸長辞書を初期設定し、（ｂ）前記圧縮されたデータメモリ内での前記キャラクタの前記圧縮された表現内の第１の辞書エントリ番号へポインタを初期設定し、（ｃ）前記ポインタによって指示された辞書エントリ番号を用いて前記プレフィルデータ圧縮辞書及び前記データ特定データ伸長辞書のうちの１つから辞書エントリ及びイクステンションキャラクタを検索し、（ｄ）前記伸長されたデータメモリ内に前記辞書エントリを前記最長一致を呈するキャラクタの伸長された表現として格納し、（ｅ）前記最長一致を呈する前記キャラクタ及び前記イクステンションキャラクタを前記データ特定データ伸長辞書に選択的に格納し、（ｆ）前記圧縮されたデータメモリ内での前記キャラクタの前記圧縮された表現内の次の辞書エントリ番号へ前記ポインタを移動させ、（ｇ）前記キャラクタのシーケンス内のすべての圧縮されたキャラクタが伸長されるまで前記キャラクタの前記圧縮された表現内のすべての辞書エントリ番号及びイクステンションキャラクタについて各ステップｃ〜ｆを繰返す、各ステップを実行する伸長手段、
    をそなえているデータ伸長システム。
42. キャラクタのシーケンスの圧縮された表現を伸長するデータ伸長システムであって、前記圧縮された表現は、（１）所定のサイズのキャラクタウィンドウ内のキャラクタのシーケンスとの、前記キャラクタのシーケンス内の特定のキャラクタへのポインタでスタートするキャラクタのシーケンスのそれぞれの最長一致の長さ及びウィンドウポインタ、及び（２）プレフィルデータ伸長辞書内の特定のキャラクタへの前記ポインタでスタートするキャラクタのシーケンスのそれぞれの最長一致の辞書エントリ番号であって、前記プレフィルデータ圧縮辞書は前記キャラクタのシーケンス内で多発しそうなキャラクタの所定の組合せを包含しており、前記データ伸長システムは、
    前記キャラクタのシーケンスの前記圧縮された表現を格納するための圧縮されたデータメモリ、
    伸長後前記キャラクタのシーケンスを格納するための伸長されたデータメモリ、及び
    （ａ）前記圧縮されたデータメモリ内での前記キャラクタの前記圧縮された表現内の第１のエントリへポインタを初期設定し、（ｂ）前記ポインタによって指示された前記キャラクタの前記圧縮された表現内の現エントリが、（１）ウィンドウポインタ及び長さであるか、又は（２）辞書エントリ番号であるかを決定し、（ｃ）前記圧縮された表現内の前記現エントリがウィンドウポインタ及び長さであれば、前記ウィンドウポインタによって指示された現キャラクタウィンドウ内のキャラクタでスタートする前記長さによって決定される多数のキャラクタを検索し、（ｄ）前記圧縮された表現内の前記現エントリが辞書エントリ番号であれば、前記辞書エントリ番号によって特定される前記プレフィルデータ伸長辞書内の辞書エントリでキャラクタを検索し、（ｅ）現エントリについての最長一致を呈するキャラクタの伸長された表現として前記伸長されたデータメモリに各ステップｃ又はｄにおいて検索されたキャラクタを格納し、（ｆ）前記圧縮されたデータメモリ内での前記キャラクタの前記圧縮された表現内の次のエントリへ前記ポインタを移動させ、（ｇ）前記キャラクタのシーケンス内のすべての圧縮されたキャラクタが伸長されるまで前記キャラクタの前記圧縮された表現内のすべてのエントリについて各ステップｂ〜ｆを繰返す、各ステップを実行するための伸長手段、
    をそなえているデータ伸長システム。

Images