(57)【特許請求の範囲】
【請求項１】
データストリーム中ですでに観察済みの文字列をコード値に置き換えることによって直列データストリームを圧縮するための方法であって、前記データストリームからの新しい拡張文字を、ストリングディクショナリ内ですでに探索され、かつ、見出されている文字列に付加することによって、連続する、より長いデータ文字列が作成され、前記付加された次の拡張文字が前記ディクショナリ（１１）に未だストアされていない新しいストリングを作り出したときに最長整合ストリングが決定され、その後、前記新しいストリングが、前記ディクショナリ（１１）内の次の逐次利用可能アドレスにおけるディクショナリ中にストアされ、前記最長整合ストリングが予めストアされているアドレスのためのコード（＠３３）が、前記新しいストリングを作り出した前記拡張文字と共に記憶装置またはデコーダに出力され、
前記データストリーム中ですでに観察済みの文字列と置き換えられた数値ストリングコードを含むディクショナリ（１１）の１ステップ探索（図３）を実行するステップと、
前記データストリーム（１２）中でストリングに最初に遭遇したとき、前記ディクショナリに文字列をストアする代わりに、ストリングコード（９３）を新しいデータストリングを表す前記ディクショナリ中にストアするステップと、
前記ディクショナリを探索すべき文字列（１２）を、前記ストリングコードに付加された前記データストリームからの次の拡張文字（７１）と共に、前記ディクショナリ（１１）から探索するポインタアドレスにおいて読み出されるストリングコード（６９）からなる固有ポインタアドレスに変換して、前記ディクショナリを１ステップで探索すべき新しいポインタアドレス（７２）を作成するステップと、
前記ディクショナリの前記新しいポインタアドレス（７３）からストリングコードが見出されなくなるまで、前記ディクショナリから前記新しいポインタアドレスにおいてストリングコードを読み出すステップと、
次の逐次ストリングコード（９３）を、前記ディクショナリの前記新しいポインタアドレス中にストアするステップと、
前記ディクショナリの最新のポインタアドレスの前のポインタアドレスから読み出された最新ストリングコード（９２）を出力するステップと
を備えることを特徴とする方法。
【請求項２】
前記ディクショナリ（１１）から読み出された前記最新ストリングコード（９２）を出力した後、新しい探索（図５）を開始するステップをさらに含み、前記新しい探索を開始するステップは、
前記データストリームから読み出される最後の拡張文字および前記データストリームから読み出される次の拡張文字を、新しいポインタアドレス（９６）に変換して、前記ディクショナリの新しい探索を開始するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
１ステップ探索を実行する前記ステップは、前記ディクショナリ（１１）のポインタアドレス（１９）から読み出される（＠２１）ストリングコード内容から、探索されるストリングが新しいストリングであること、および、新しいストリングおよび新しい探索のために、新しいポインタアドレス（３４）を作成する必要があることを同時に決定するステップ（＠２２）を備えることを特徴とする請求項１に記載の方法。
【請求項４】
次の固有逐次ストリングコードを前記ディクショナリ（１１）中にストアする前記ステップ（＠９３）は、次の固有逐次ストリングコードを提供するために、コードカウンタ（５９）をインクリメントするステップを備えることを特徴とする請求項１に記載の方法。
【請求項５】
前記ディクショナリから読み出された前記ストリングコードが、前記ディクショナリが満杯であることを示すために使用すべき最高の番号が振られたストリングコードであるか否かを決定するステップ（＠５４）をさらに含むことを特徴とする請求項３に記載の方法。
【請求項６】
前記ディクショナリ（図２）において、前記ディクショナリ（１１）の各アドレスにおける内容に関連するテーブルレベルメモリ（１１Ａ）を提供するステップと、
新しい固有ストリングコードが前記ディクショナリ（１１）中にストアされる毎に、前記テーブルレベルメモリ（１１Ａ）にレベル値を設定するステップ（＠６１）と、
前記ディクショナリが満杯であることが決定された場合（＠５４）に、前記テーブルレベルメモリ（１１Ａ）に、より高いレベル値を設定するステップとをさらに含み、
前記ディクショナリから読み出された内容から決定する前記ステップ（＠５４）は、前記固有ポインタアドレスにおけるテーブルレベル値が、探索されるストリングのためのコードが前記ディクショナリ中に存在することを示す所定のテーブルレベル値に対応することを決定するステップをさらに備えることを特徴とする請求項５に記載の方法。
【請求項７】
前記ディクショナリから前記ポインタアドレスにおいて読み出される（＠２２）ストリングコードは、すでに発生済みのストリングを表すコードであり、
新しいポインタアドレス（＠５６）の生成を継続するステップ（＠７６）と、
前記ディクショナリ（１１）から前記新しいポインタアドレス（＠１９）において、すでにストアされているストリングコードの読出しを継続するステップ（＠８６）と、
先行するストリングが見出される毎に、前記アドレスポインタによって表されるストリングの長さを拡張するステップと
を備えることを特徴とする請求項１に記載の方法。
【請求項８】
前記新しいポインタアドレスにおいて読み出される（＠２２）コードは、未発生のストリング（図５）を表すコードであり、
すでにストアされているストリングから得られる最後の文字（＠１８）のためのコード、およびそれに付加された、前記入力データストリームからの次の文字（＠１７）からなる、新しいポインタアドレス（＠５６、９６）を生成するステップを含むことを特徴とする請求項１に記載の方法。
【請求項９】
最新の整合ストリングコード（＠３３、９２）をレシーバまたはデコーダに伝送するステップと、
新しい固有ストリングコード値を、前記ディクショナリの前記ポインタアドレス中にストアするステップとをさらに含み、
前記新しい固有ストリングコード値（９３）は、コード生成器（５９）によって生成された逐次値からなることを特徴とする請求項８に記載の方法。
【請求項１０】
データストリーム中ですでに観察済みの文字列をコード値に置き換えることによって直列データストリームを圧縮するためのデータ圧縮システム（図１、図２）であって、探索するストリングがストリングディクショナリ（１１）内で見出されたとき、前記データストリームからの新しい拡張文字（１７）を付加することにより、連続する、より長い文字列が作成され、前記ディクショナリは、観察済みの古いストリングをストアするメモリと、前記ディクショナリ内の新しいストリングを探索するための手段であって、前記ディクショナリ中にストアされている古いストリングと新しいストリングとを比較するための手段を含み、前記ディクショナリ内に見出されない新しいストリングは、整合するストリングを見出すことができるメモリロケーションの探索後、メモリ内の次の逐次オープンアドレスにストアされる探索するための手段とを備え、前記データ圧縮システムは、
前記直列データストリーム中で観察される各可能列のための１つメモリアドレスからなるストリングコードディクショナリ（１１）であって、該ディクショナリ（１１）内の前記データストリーム（１２）中に最初に観察されたときに文字列のためのストリングコード値をストアするための手段を備えたストリングコードディクショナリ（１１）と、
前記ディクショナリ（１１）内を探索すべき文字列を、固有ポインタアドレス（＠１９）に変換するためのポインタアドレス手段（１７、１８）であって、前記ポインタアドレスは、既知のストリング部分（１８）と次の文字部分（１７）とを備え、該次の文字部分は、前記入力データストリーム（＠１４）から取り出されかつ前記ディクショナリから読み出された前記ストリング部分（１８）に付加されて、固有ポインタアドレス（＠１９）を形成するポインタアドレス手段（１７、１８）と、
前記ディクショナリ（１１）を探索するストリングを表す前記固有ポインタアドレスにおいて前記ディクショナリ（１１）の内容を読み出す（＠１９、２１）ための手段と、
単一の読出し探索で前記ストリングコードディクショナリから読み出された内容から、読み出すストリングが前記ディクショナリ内における最長整合ストリングであるか否か、または、新しい、より長いストリングポインタアドレスを作成するために、拡張文字を追加するか否かを決定するための手段（２２）と
を備え、前記ポインタアドレス手段は、前記ディクショナリの最後のポインタアドレスから読み出される（＠３０）コード値（＠２２）、および前記入力データストリーム（１２）中の次の文字（１４）からなる新しい固有ポインタアドレス（＠３１、３４）を作成するための手段をさらに備えることを特徴とするデータ圧縮システム。
【請求項１１】
前記決定手段（２２）は、前記ディクショナリ（１１）から読み出された、前記入力データストリーム（１２）中ですでに発生済みの複数の文字列を示すストリングコード値を受け取り、かつ、ストアするためのバッファレジスタ手段と、
前記入力データストリーム中に見出された最長整合文字列に対するストリングコードをレシーバに伝送するための手段（２３）と
を備えることを特徴とする請求項１０に記載のデータ圧縮システム（図１、２）。
【請求項１２】
前記決定手段（２２）は、前記ディクショナリから読み出された、前記ストリングコードディクショナリ（１１）の前記ポインタアドレスにおいてストリングコードが存在しないことを示す値を受け取るためのバッファレジスタ手段と、
前記ポインタアドレスによって示される、前記入力データストリーム中の前記文字列と置き換えるべき固有ストリングコード値を、前記ディクショナリに書き込むためのストリングコード生成手段（５９）と
を備えることを特徴とする請求項１０に記載のデータ圧縮システム。
【請求項１３】
前記ポインタアドレス手段は、「ｎ」を２０〜２３として、２ｎビットに等しい長さを有するポインタアドレスをストアするためのレジスタを備えることを特徴とする請求項１２に記載のデータ圧縮システム。
【請求項１４】
前記ストリングコードディクショナリは、「ｎ」を２０〜２３として、最小の２nポインタアドレスを有するメモリを備えることを特徴とする請求項１２に記載のデータ圧縮システム。
【請求項１５】
前記ストリングコード生成手段は、可能ポインタアドレスの数がコード値の数を超える、異なるポインタアドレスにおいて可変幅固有ストリングコード値（＠５９）を生成するための手段を備えることを特徴とする請求項１４に記載のデータ圧縮システム。
【請求項１６】
前記ストリングコードディクショナリ（１１）は、幅が可変の前記ストリングコード値の数より多いメモリアドレスロケーションを備えることを特徴とする請求項１０に記載のデータ圧縮システム。
【請求項１７】
前記メモリロケーション（１１Ａにおける）の一部は、未使用ビット中にテーブル値をストアするためのテーブルを備えることを特徴とする請求項１０に記載のデータ圧縮システム。
【請求項１８】
前記ストリングコードディクショナリ（１１）は、関連するテーブルレベル値メモリ（１１Ａ）と、
前記ディクショナリがより下位のテーブルレベルのストリングコード値で満杯のとき、前記テーブルレベル値（６１）をより高いテーブルレベルにリセットするための手段とをさらに含むことを特徴とする請求項１０に記載のデータ圧縮システム。
【発明の詳細な説明】
【０００１】
（発明の背景）
１．発明の分野
本発明は、データ圧縮システムに関する。より詳細には、本発明は、無損失データ圧縮、およびストリングコード（ｓｔｒｉｎｇ  ｃｏｄｅ）をストアするためのディクショナリを使用したシステムにおいてデータのストリームを圧縮する速度を速めるための方法および手段に関する。
【０００２】
２．従来技術の説明
従来、無損失データ圧縮アルゴリズムが知られていた。最も良く知られているデータ圧縮システムおよび方法の中には、Ｌｅｍｐｅｌ  Ｚｉｖ  Ｏｎｅ（ＬＺ−１）、Ｌｅｍｐｅｌ  Ｚｉｖ  Ｔｗｏ（ＬＺ−２）、およびＬｅｍｐｅｌ  Ｚｉｖ  Ｗｅｌｃｈ（ＬＺＷ）と呼ばれているものがある。これらの適応無損失データ圧縮システムはすべて、入力データストリーム中で遭遇するデータストリング、記号ストリングまたは文字列を表すストリングコードをストアするためのディクショナリを使用している。一旦ストリングが識別されると、識別されたデータストリングよりビット数の少ないコードとしてストアされ、それにより、データストリーム中に同一のストリングが続いて発生した場合に、すでにストアされているストリングコードと置き換えられる。上に挙げた３つのデータ圧縮システムはすべて、調査中のストリングに対して、ストリングコードがすでにストアされているか否かを決定するために、ディクショナリ中の複数のロケーションを探索しなければならない。そのためには、入力データ文字列と、ディクショナリロケーション中にすでにコード化されている同一文字列とを突き合せなければならない。
【０００３】
ディクショナリ中の複数のロケーションの探索に要する時間を最短にするために、ハッシングアルゴリズムを使用して上記マッチング機能を実行することが提案されている。ハッシュ探索は、探索するデータに基づいてテーブル中の索引を計算する。ハッシュ表探索の効率は、テーブルの構成および複数の項目を、矛盾することなくテーブルの同一領域にハッシュすることができるか否かによって決まる。ハッシングシステムは実施費用が高く、計算が複雑であり、そのため、オーバヘッドが性能を低下させる。あるＬＺＷハッシング法が、米国特許第４，５５８，３０２号に記載されている。
【０００４】
また、メモリおよびメモリの一部を分割し、整合または整合がないことが見出されるまで逐次探索する二分探索法の使用も提案されている。定義によれば二分探索法では、ディクショナリ内を複数回探索しなければならず、また、テーブルを並べ換える必要もあるが、ハッシングに関連する複雑な計算が負うべきオーバヘッドが低減されるという利点を有している。
【０００５】
連想ストア装置（ＣＡＭ）すなわち連想メモリを使用することにより、ディクショナリ中に位置付けされている複数のストリングの内容を比較する回数を少なくすることが提案されている。このシステムは効率的ではあるが、複雑であり、極めて費用のかかるシステムである。この方法の一例が、米国特許第５，８３８，２６４号に記載されている。
「Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ：Ｔｈｅ  Ｃｏｍｐｌｅｔｅ  Ｒｅｆｅｒｅｎｃｅ」という名称の印刷刊行物（Ｄ．Ｓａｌｏｍｏｎ著、１９９８年、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ）によれば、ディクショナリ方式が解析され、また、それらの方式が、静的または動的（適応的）方式として分類されている。この参考文献によれば、ＳｔｏｒｅｒおよびＳｚｙｍｅｎｓｋｉを、ＬＺ７７を改良するＬＺＳＳ（同じくＳｔｏｒｅｒ、１９８２年）の開発者と見做している。上記ディクショナリ方式は、二分探索ツリー中に探索バッファ（ディクショナリ）を保持し、出力として「２つのフィールドを有するトークン」を作成する。二分探索ツリーの２つの形態が、わずか１４のノードを用いて考察されている。Ｓａｌｏｍｏｎは、ディクショナリ用として平衡ツリー構造を用いる場合、１４のノードの任意のノードを最大４ステップで見出すことができるが、スキュードツリーを使用する場合、最大１４のステップが必要であると結論している。したがって、それぞれのツリーにおけるエレメント数「ｎ」の高さが、二分探索ツリーを使用するディクショナリの探索を実行するために必要な最大ステップ数を決定している。
ＬＺ７８（およびＺＩＶ７８）は、ＬＺＳＳを改良したものであり、探索バッファおよび／またはルックアヘッドバッファは使用していない。その代わりに、それまでに遭遇したすべてのストリングを、個々の文字としてストアするディクショナリがあり、そのサイズは、急速に増加し、直ぐに満杯になる、ディクショナリ専用のメモリサイズすなわちメモリ量によって制限されている。符号器（エンコーダ）は、２つのフィールドトークンを出力する。トークンの第１のフィールドは、最長整合ストリングの探索後に見出される最長整合に割り当てられる、ディクショナリ内のアドレスロケーション（ポインタ）である。コード器は、このポインタを使用して、そのディクショナリを探索するが、このポインタは、デコーダにおいてのみ使用される。第２のフィールドは、不整合の原因となり、ディクショナリ内における次の逐次利用可能ディクショナリアドレス中にストアされる新しいストリングをもたらすデータストリームからの拡張文字である。
Ｓａｌｏｍｏｎは、使用時にＬＺ７８ディクショナリのサイズを決定することができることを正しく観察しているが、大型のディクショナリは、より多くのストリングを含むことができ、また、より長い整合を可能にする代わりに、その分ポインタがより長くなり、また、ディクショナリの探索速度がより遅い。Ｓａｌｏｍｏｎは、ルートとしてナルストリングから開始されるツリー構造の使用を提案している。ナルストリングツリーは、二分探索ツリーに必要なレベル数「ｎ」を減少させるが、整合を確認し、あるいは整合が存在しないことを結論付けるためには、すべてのレベルにおいて複数の探索が必要である。それにより、先行レベルにおいて見出された整合が、探索するストリングに対する最長整合であったことになる。
Ｓａｌｏｍｏｎは、Ｌｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ（ＬＺＷ）がＬＺ７８を改良したものであることを正しく観察しており、ＬＺ７８と類似のツリー構造を好ましく使用している。ＬＺ７８に対するＬＺＷの利点は、二重になっていることであり、フィールドトークンが１つしか出力されず、また、好ましいことには、ディクショナリのための「ツリー」構造のサイズが制限されない。ＬＺ７８ディクショナリと同様、ナルストリングツリーと等価である場合、ＬＺＷディクショナリにおいても複数の探索が必要である。
Ｓａｌｏｍｏｎは、開発者であるＲｏｓｓ  Ｗｉｌｌｉａｍｓの名に因んで「Ｗｉｌｌｉａｍｓ  ９１」またはＬＺＲＷ１と呼ばれるＬＺ７７を、簡易高速変形態様と簡潔に説明している。この方式は、全利用可能メモリをＬＺ７７バッファとして使用し、「ブロック」中の入力ストリームをコード化する。説明によれば、１ステップで整合が見出される可能性があることが提案されているが、ＬＺ７７においては、その１ステップには、わずか１ブロックのデータストリームをコード化するために、長さ４キロバイトの探索バッファ上を１６バイトのルックアヘッドバッファを移動させるステップを備えている。上記探索バッファが、ブロックにおけるＬＺ７７探索を複数にしており、そのため、１ステップ探索では有り得ない。この方式は、「見出される整合が必ずしも最長ではないため、決して有効ではない」と言うことができる。
Ｄ．Ｓａｌｏｍｏｎの上記ディクショナリ方式については、最長整合ストリングを見出すための探索ツリー（またはいくつかの等価物）を特に必要とし、そのため、複数の探索を必要とする方式、として要約することが唯一公正であろう。ＬＺ７７ブロックバッファメモリ内の探索を高速化するために、いくつかの形態のハッシングを使用する非ディクショナリ試行は、すべての利用可能なメモリを消費するが、複数の探索の後、最長の整合ストリングが見出されることを依然として保証していない。
【０００６】
ストリングディクショナリを使用したデータ圧縮システムにおいて、複数探索を完全に回避する方法および装置が提供されることは望ましいことであろう。また、既存の圧縮解除器／デコーダが、いかなる変更もなく、圧縮データを受け取り、かつ、復号化することができるように、新しいデータ圧縮システムからの出力を、ＬＺＷなどの既存のデータ圧縮システムと互換性を持たせるべくフォーマット可能にすることができることがさらに望ましい。
【０００７】
（発明の概要）
本発明の本質的な目的は、ストリングディクショナリを使用して実施されるデータ圧縮の速度を最適化することである。
【０００８】
本発明の他の本質的な目的は、データ圧縮器のストリングディクショナリ内の複数アドレスロケーションを探索する必要性を除去することである。
【０００９】
本発明の他の本質的な目的は、ディクショナリ内の探索を不要にするために、可能なすべての新規ストリングコードのための唯一の固有アドレスを有するルックアップテーブルとして配列されたＬＺＷストリングディクショナリを提供することである。
【００１０】
本発明の他の本質的な目的は、効率的にフォーマット化し、それにより、ストリングディクショナリ内を広範囲に渡って探索するペナルティを課すことなく、漢字、日本語、およびその他の複雑な文字コードを圧縮することができる新規データ圧縮システムを提供することである。
【００１１】
本発明の他の本質的な目的は、計算機システムに負担をかけることなく、低コストのランダムアクセスメモリ（ＲＡＭ）を使用して実施することができるデータ圧縮システムを提供することである。
【００１２】
本発明の他の本質的な目的は、これまでに可能であった速度より速い速度でＬＺＷデータ圧縮を実行する新規方法を提供し、それにより、標準化されている、あるいはＬＺＷなどのストリングデータ圧縮を使用している高速ネットワークのための実時間スループットを増加させることである。
【００１３】
本発明の他の目的は、データストリームを圧縮するプロセスを高速化する、新しい改良型ＬＺＷデータ圧縮実行方法を提供し、かつ、既存の回線およびリンク上での伝送速度をより速くするための手段を提供することである。
【００１４】
本発明の本質的な目的は、圧縮すべきデータストリーム中で遭遇するデータストリングのための新規拡張ポインタアドレスコードを提供することである。
【００１５】
本発明の本質的な目的は、アクセス可能アドレスの数が、全ディクショナリ内に使用されている最大ストリングコード数より多い、新規ストリングディクショナリを提供することである。
【００１６】
本発明の本質的な目的は、ビット数の少ない固有単一のストリングコード値を、ビット数の多い固有ポインタアドレスコード中に含まれている文字列を表すディクショナリ中にストアすることである。
【００１７】
本発明の本質的な目的は、ストリングディクショナリ内の複数のアドレスロケーションの探索を必要とすることなく、ＬＺＷフォーマットで圧縮データストリームを生成することである。
【００１８】
本発明の本質的な目的は、ストリングコードを有する拡張文字をＬＺＷディクショナリ中にストアする必要を無くすことである。
【００１９】
本発明の一般的な目的は、ディクショナリが満杯の場合に、停止し、かつ、内容をクリアする必要なく、同一ＬＺＷストリングディクショナリを複数回使用することである。
【００２０】
本発明の一般的な目的は、すべてのメモリロケーションの内容にわたって読み出すことなく、ストリングディクショナリのすべてまたは選択部分を、パージすなわちクリアすることである。
【００２１】
本発明の一般的な目的は、コードデータがストアされているアドレスロケーションのみを重ね書きすることによってクリアすることができるように、ストリングコードのアドレスロケーションを補助ルックアップテーブル中にストアすることである。
【００２２】
本発明の一般的な目的は、ディクショナリが満杯の場合に、停止し、かつ、内容を消去する必要なく、同一ＬＺＷストリングディクショナリを複数回使用することである。
本発明の一般的な目的は、すべてのメモリロケーションの内容にわたって読み出すことなく、ストリングディクショナリのすべてまたは選択部分を、パージすなわち消去することである。
本発明の一般的な目的は、コードデータがストアされているアドレスロケーションのみを重ね書きすることによって消去することができるように、ストリングコードのアドレスロケーションを補助ルックアップテーブル中にストアすることである。
本発明のこれらおよびその他目的によれば、入力データストリーム中に観察される各可能ストリングのためのメモリロケーションを有するストリングコードディクショナリを提供することを特徴とする、入力データストリーム中で遭遇するデータ文字列をコードに置き換えるためのデータ圧縮システムおよび方法が提供される。入力データストリームがシステムに入力されると、探索すべき新しい文字列が、既知のストリング部分および次の文字部分からなる固有ポインタアドレスに変換される。生成されるすべての可能ポインタアドレスは、対応するメモリロケーションをストリングコードディクショナリ内に有している。上記ポインタアドレスを用いて、新規ストリングコードディクショナリの内容が読み出される。ディクショナリの内容がストリングコードを含んでいる場合、そのストリングコードは、探索するストリングのためのストリングコードであり、ディクショナリの１ステップ探索が完了する。より長いストリングのための次の探索は、ディクショナリから読み出された最新整合ストリングコードに次の（拡張）文字を付加し、新しい固有ポインタアドレスを提供することによって開始される。これらの１ステップ読出し探索は、ディクショナリのポインタアドレスから読み出される内容が無くなるまで継続される。
上記ポインタアドレスが保持され、ストリングコード生成器によって、次の利用可能ストリングコードがディクショナリのポインタアドレスに書き込まれる。この書込みにより、１ステップ読出し探索が完了し、「ミス」が発生する。ポインタアドレスのストリングコード部分が、先行する「ミス」ストリングからの最後の文字およびデータストリームからの次の拡張文字からなる、探索すべき新しいストリングが作成される。
ミスが発生した場合は必ず、すでに整合している最新のストリングのためのコードが、ストア装置またはレシーバデコーダに出力される。この方法によれば、ミスが発生するまで、データストリームからの拡張文字が常に付加され、あるいは既知のストリングに連結され、探索すべき、より長いストリングが常に作成される。また、探索すべきストリングのための新しい２つの文字列およびポインタアドレスが作成され、１ステップストリング探索が、ストリングそのものではなく、ストリングのためのコードを含む新規ディクショナリ内で実行される。
【００２３】
（好ましい実施形態の詳細な説明）
図１および好ましい実施形態のデータ圧縮システムを参照する前に、ほとんどのデータ圧縮システムに合った単一の形式は存在しないことを理解されたい。したがって、コンプレッサ／トランスミッタとレシーバ／デコーダはともに、１）使用する文字セット、２）最大コード値または最大コードフィールドを定義するのに使用する最大ビット数、３）停止、リセット、コードクリアなどの特別コード、および４）使用するコード化データパッキング−分離スキームを知る必要がある。データコンプレッサおよびデコーダが、使用するプロトコルを既に確立しており、かつ前述した項目が分かっている場合、データ圧縮を開始する前にプリアンブル内またはヘッダ内でそのような情報を送信する必要はない。トランスミッタおよびレシーバがプロトコル項目を知っている本発明の好ましい実施形態では、文字セットを使用する初期化なしに新規のストリングディクショナリ１１を含む圧縮システム１０を開始することが可能である。ただし、従来のＬＺＷデータ圧縮で使用されるとおりディクショナリを文字セットで初期化することも可能である。データ圧縮システム１０は、入力データストリームのための入力ライン１２を含み、この入力データストリームは、データストリームバッファ１３内に入れられ、このデータストリームバッファ１３には、次の文字を取り出し、それをライン１５上に出力する抽出器１４が付加され、このライン１５上で、この次の文字は、ポインタアドレスレジスタ１６の拡張文字コード部分１７内に入れられる。ポインタアドレスレジスタ１６内には、ＬＺＷストリングコード部分１８内のＬＺＷストリングコードが既に存在しており、このＬＺＷストリングコード部分は、ライン１２上のデータストリーム内で見られる最後の一致したストリングに対するコードを含む。説明のため、ＬＺＷコード部分は１２ビットを含み、また拡張文字部分１７は８ビットを含み、したがって、ライン１９上のディクショナリポインタアドレスは２０ビットを含むことになるものと想定する。新規ディクショナリ１１は、少なくとも２２０の固有メモリロケーションまたはメモリアドレスを備え、したがって、可能なすべてのディクショナリポインタアドレスが、メモリロケーションを有することになる。ディクショナリが初期化されるとき、例外なくすべての文字列には、それと一致するものが見つかることになり、これにより、２つの文字列の圧縮が開始される。
【００２４】
ライン１９上のディクショナリポインタアドレスは、ディクショナリ１１内で読取り動作を生じさせ、また、そのポインタアドレスにある内容がライン２１上に現れて、ＨＩＴ／ＮＯ  ＨＩＴバッファ２２内にストアされる。ストリングコードがそのポインタアドレスに存在しており、このことは、現在、検査されているストリングが以前に見られたものであり、そのストリングがディクショナリ１１内でコードで置き換えられていることをバッファ２２内の論理に認識させるものと想定する。したがって、ＨＩＴがライン２３上で観察され、このことは、ＨＩＴ論理２４に論理２５内で次のポインタアドレスを生成させる。
【００２５】
ポインタ論理２５により、バッファ２２は、ポインタアドレスレジスタ１６のストリングコード部分１８内に書き込まれた最後のＨＩＴコードをライン２７上に生成することができる。同時に、このポインタ論理は、イネーブル信号をライン２９上に生成し、この信号は、ポインタアドレスレジスタ１６の拡張文字部分１７内に書き込まれるライン１５上の次の文字コードを文字抽出器１４に生成させる。この時点で、ポインタアドレスレジスタ１６は、ディクショナリ１１から読み取られた最後のＨＩＴコード、およびデータストリームから取り出された拡張文字または次の文字を含む。ライン１９上の新しいポインタアドレスが、その新しいポインタアドレスにあるディクショナリの内容を再び読み取り、読み取った内容をＨＩＴ／ＮＯ  ＨＩＴバッファレジスタ２２内に入れる。このプロセスは、ディクショナリ１１から読み取られるＨＩＴコードが存在しなくなり、バッファレジスタ２２内の論理が、ＮＯ  ＨＩＴ論理３１へのライン２８上に信号を生成するまで続く。ＮＯ  ＨＩＴ論理３１は、ライン３０を介して、ライン３２上およびトランスミッタ内またはレシーバ３３内に、バッファレジスタ２２からの最後に一致したコードを読み込む。これは、ブロック３３によって示されているが、遠隔のレシーバに対して送信するためのラインであることも可能である。ＮＯ  ＨＩＴ論理３１は、ライン６２を介して、ＮＯ  ＨＩＴポインタアドレスでレジスタ１１内に次の逐次コードをコードジェネレータ５９が書き込むようにさせる。また、ＮＯ  ＨＩＴ論理３１は、論理ブロック３４で、ライン２９を介してシステム１０に新しいポインタアドレスを生成するように信号を送る。新しいポインタを生成するため、論理３４は、２つの逐次動作を行う。ブロック３５で示す第１の動作は、レジスタ１６のブロック１７内の拡張文字を、部分１７に接続されたライン３６で示されるとおり、レジスタ１６のブロック１８内に移動させることである。次の逐次動作は、ライン１５を介して、データストリーム内の次の文字を拡張文字部分１７内にロードすることである。ブロック３７で示すとおり、この論理は、ライン３８上にイネーブル信号を生成する。最後の文字が読み取られたことを文字抽出ブロック１４が感知した場合には、ブロック１４が、ブロック１４で最後の文字が読み取られていることをコンピュータコントローラ論理にブロック３９で知らせ、これにより、探索論理の終りが完了する。
【００２６】
図１のデータ圧縮システム１０の動作を要約すると、抽出器１４からの入力データストリーム内の次の文字または最後の文字が、ブロック２２で読み取られた最後の一致からのストリングコード部分１８上に、常に付加されることが認められよう。アドレスポインタは、ライン１９上の２つの部分１７および１８によって生成され、このことは、その固有ポインタアドレスでディクショナリ１１の内容をシステムが読み取るようにさせる。この実施形態においてアドレスポインタ位置に内容が存在する場合、その位置は、アドレスポインタによって示されるストリングに関する一致に対するコードを含む。ストリングが前の一致を有する場合には、そのストリングを１つの文字によって拡張しなければならず、より長い一致を見つける試行をしなければならない。これを行うため、ディクショナリ１１から読み取られたばかりのコードがバッファ２２を通り、コード部分１８内にロードされ、データストリームからの次の文字コードまたは拡張文字が部分１７にロードされ、新しいポインタが生成される。この一連の動作は、ディクショナリ１１から読み取られるコードが全く存在しなくなるまで続く。コードが全く存在しなくなることは、ＭＩＳＳまたはＮＯ  ＨＩＴで示される。これが生じたとき、ＭＩＳＳに対する新しいコードがポインタアドレスにおいてディクショナリ１１内にストアされ、新しいストリングは、この時点で部分１７内にある最後の文字から開始しなければならない。新しいストリングを開始する前に、前の一致コードまたは最後の一致コードを、論理ブロック３３として示すとおり、レシーバに送信しなければならない。次に、ＮＯ  ＨＩＴ論理３１が、ポインタ論理３４に２つのことを行わせる。第１に、拡張文字部分１７内の最後の文字をコード部分１８内に移動し、次の文字を抽出器１４から取り出し、拡張文字部分１４内にロードし、これにより、２つの１文字列を有する新しいストリングを開始する。これら２つの新しい１文字列は、既に観察された複数文字列を構成することも、しないことも可能であるポインタアドレスを含むが、これは、ディクショナリの内容をポインタアドレスに読み取らせ、前述したとおり、ＨＩＴまたはＮＯ  ＨＩＴが起きたかどうかを判定することによって判定することになる。
【００２７】
ディクショナリ１１を使用する文字コードセットで初期化するとき、複数文字列の圧縮を開始するには、データストリーム内の最初の２文字を部分１８および１７にロードするだけでよい。単一文字に対するポインタアドレスを使用する必要はなく、また単一文字のためのコードは、好ましくは、特殊制御文字に続くより下位のアドレス内に配置する。２５６文字ＡＳＣＩＩコードセットを使用する場合、２文字列に対するコードは、３つの特殊コードコードを使用し、かつゼロアドレスを全く使用しない場合には、２５９で開始することになる。
【００２８】
ディクショナリ１１を初期化せず、レシーバが文字コードセットおよびプロトコルを知っているとき、コードセット内の単一文字コードのためのアドレスは、前述したとおり、より下位のアドレスとして予約することができる。ただし、単一文字コードの内容は、レジスタ１６によってアドレス指定可能ではないため、２文字アドレスがＭＩＳＳまたはＮＯ  ＨＩＴを生じさせたとき、レジスタ２２内に最後の一致コードが全く存在しないことになる。これが起きた場合、単一文字コードは、ストリングコード部分１８内で入手可能であり、コントローラ３９によって読み取られることが可能である。ＭＩＳＳが生じたときに単一文字コードを生成する別の仕方は、レジスタ１８内の単一文字コードが、コントローラ３９内で以前に見られたかどうかを判定することであり、見られていない場合、それがＭＩＳＳが生じたときの最後の一致であることになる。
【００２９】
次に、テーブルレベル機能がそこで使用される、図１のデータ圧縮システムを変形した実施形態の概略ブロック図を示す図２を参照する。データ圧縮システム５０は、同様のまたは拡張したディクショナリ１１、および以下に説明するとおり、ディクショナリの一部分であることが可能な、１１Ａで示したテーブルレベルを使用する。この説明では、ライン１２上、バッファ１３内、および抽出器１４内のデータストリームは、本明細書で前に説明したのと同じであると想定する。したがって、次の文字は、拡張文字部分１７にとって、必要なときにはいつでもライン１５上で手に入る。同様に、バッファ２２内の最後の一致コードは、ポインタアドレスレジスタ１６Ａのコード部分１８にとって、ライン２７上で手に入る。変形した実施形態では、ポインタアドレスレジスタ１６Ａは、テーブルカウンタ５２によって索引付けされているテーブルレベルブロック５１を含むものとして示され、このカウンタは、リセット入力およびセット入力、ならびにオーバーフロー出力４０を有するものとして示されている。ライン１９上のポインタアドレスでディクショナリ１１にアクセスすることに加え、ディクショナリポインタアドレスと同じポインタアドレスで、テーブル１１Ａ内にテーブルレベル値も提供されている。例えば、１１Ａ内のテーブルレベルが、ディクショナリ１１の内容と同時に読み取られ、テーブルレベルブロック５３内にストアされる場合、このレベルは、論理ブロック５４で、ブロック５１内の現行のテーブルレベルと比較することができる。それらのテーブルレベルを比較する場合、ＨＩＴが存在し、そうでない場合、ＭＩＳＳまたはＮＯ  ＨＩＴが存在する。ＨＩＴが生じたとき、ライン５５上の信号が、ブロック５６でＨＩＴ論理を開始し、システム５０に新しいポインタアドレスを生成させる。新しいポインタアドレスの生成は、図１に関連して説明したのと同じであり、バッファ２２内の最後の一致コードが、ポインタアドレスレジスタ１６Ａのストリングコード部分１８内に入れられ、入力ストリーム内の拡張文字または次の文字が、抽出器１４からポインタアドレスレジスタ１６Ａの次の文字の部分１７または拡張文字部分１７に供給される。
【００３０】
ただし、対応が存在している可能性があっても、つまりディクショナリ１１内にコードが存在している可能性があっても、テーブルレベル論理内でＭＩＳＳが生じた場合、ＭＩＳＳが存在し、システム５０は、ライン５７によって示されるとおり、ＭＩＳＳ論理を実行する。ＭＩＳＳ論理５８は、次のストリングコードをコードジェネレータ５９が書き込むようにさせ、ブロック５１で現行のテーブルレベルをポインタアドレスでディクショナリ１１内およびテーブルレベル１１Ａ内にテーブル論理６１が書き込むようにさせる。
【００３１】
ディクショナリ１１内に書き込まれる新しいストリングコードは、論理ブロック５９によってステップされ、コードは、アドレスポインタ位置で書き込まれるようにディクショナリ１１にとって入手可能である。同様に、テーブル論理６１は、ブロック５１と同様の現行のテーブルレベルを提供し、ライン６２上の書込みイネーブル信号によってそのテーブルレベルで同じロケーションに書き込まれる。
【００３２】
この場合、ポインタアドレスでディクショナリ１１内にデータが存在してはいても、テーブルレベル１１Ａが、ブロック５１内の現行のテーブルレベルと符合し、それに等しくなるまで、一致またはＨＩＴは存在しないことが理解されよう。ディクショナリ１１を拡張することの目的は、割り当てられたストリングコードのすべてが使用されるまで、ストリングコードでディクショナリを完全に埋めるのを可能にすることである。ストリングコードのすべてが使用されてはいても、ディクショナリ１１内のすべてのアドレス位置は使用されてない。例えば、ディクショナリが２２０のアクセス可能なアドレス位置を有する場合、およそ１００万の可能なアドレスが存在する。ただし、ＬＺＷコードが、２１２ビットを使用してコードを生成するだけである場合には、コードジェネレータ５９によって生成されるコードの数は、およそ４０９６のコードを有し、ディクショナリは、４０９６のコードが使い果たされたとき、満杯になっている。ディクショナリ１１にテーブルレベル追加を加えることにより、ディクショナリが満杯のとき、テーブルレベルを変更し、４０９６のストリングコードがその中に書き込まれているディクショナリのアドレスを除去またはクリアする必要なしに、コードジェネレータ５９が生成する完全に新しいシーケンスの同じストリングコードを開始することができる。言い換えれば、最大数のストリングコードでディクショナリ１１が満杯になるたびに毎回、テーブルレベル１１Ａを実施し、テーブルレベル５１がポインタアドレスのテーブルレベルに対応しない限り、ＨＩＴが生じないようにする。ＨＩＴが生じたとき、図１に関連して説明したのと同じ仕方で新しいポインタアドレスを生成し、ライン２７上の最後の一致コードをレジスタ１６Ａのストリングコード部分１８内に入れ、データストリームからの次の文字をレジスタ１６Ａの次の文字部分１７内に入れる。ディクショナリ１１が満杯になったとき、コードジェネレータ５９をリセットし、再び、同じシーケンスのストリングコードを開始するが、これらのコードは、この時点では、異なるテーブルレベルと関連している。というのは、テーブルレベル論理が、テーブルカウンタ５２および現行のテーブルレベルブロック５１により、次の高いレベルに設定しているからである。使用するメモリチップによっては、数百ものテーブルレベルを利用することができ、ディクショナリ１１をリセットする必要がない。
【００３３】
次に、データ圧縮ディクショナリ１１内の単一アドレス位置にディクショナリ探索を制限するのに使用する一連の動作の簡略図を示す図３を参照する。ブロック６６が、ブロック６７で以下により詳細に説明するディクショナリの初期化および／またはディクショナリのクリアで始まる開始動作を示す。次の動作は、ブロック６８で示すとおり、ポインタアドレスおよびシステム１０のその他の部分を初期化および／またはクリアすることである。これらの動作はブロック６９で始まり、そこで、「Ｘ」ビットストリングコードが、ポインタアドレスレジスタ１６のストリングコード部分１８内に設定される。ただし、第１の文字がデータストリームから読み取られるとき、ストリングコードは全く存在しない。ブロック７１で、「Ｙ」ビット文字コードが拡張文字部分１７内に設定される。このコードは、開始時のデータストリーム内の第２の文字、または第２の読取り動作に関するデータストリーム内の第２の文字を含む。ポインタアドレスレジスタ内の２つのコードセットを使用する固有ポインタアドレスを使用してブロック７２に示す２ｘ＋ｙビットを有する固有ポインタアドレスが生成される。ブロック７３で、ディクショナリ１１の内容が、そのポインタアドレスで読み取られる。ブロック７４で、ディクショナリ１１のストリングコード内容が、ブロック７４に示すとおり、出力バッファ２２内に読み込まれる。ただし、内容が全く存在しない場合には、まず、内容不在コードと等価のものが、バッファ２２内に読み込まれる。ブロック７５で、ディクショナリから読み取られたストリングコードが、以前にストアされたコードであるか否か、または情報の不在であるか否かの論理判定が行われる。ストリングコードが読み取られた場合には、ＨＩＴが存在し、ブロック７６に示すとおり、ＨＩＴ論理に進む。ＨＩＴが生じない場合、ブロック７７に示されるとおり、ＭＩＳＳ論理に進む。
【００３４】
図３に関する説明は、図１上におよび図２上に直接に読まれる。ディクショナリ１１を開始することを所望しない場合、図３Ａに示すとおり、準備ステップが行われるという条件で、やはり同じ一連の動作を使用することが可能である。
【００３５】
同じ開始ブロック６６を示す図３Ａを参照する。ブロック６７Ａは、ディクショナリ１１およびシステムがクリアされ、したがって、ディクショナリ１１内に以前に記録されているコード情報が全く存在しないことを示している。ただし、圧縮システム１０とデコーディングシステムの両方によって知られている数字によって文字セットに対するコード値が予約されている。
【００３６】
ブロック７８で、システム１０を開始するため、データストリーム内の第１の文字が、レジスタ１６のストリングコード部分１８内にロードされる。
【００３７】
ブロック７９で、データストリーム内の第２の文字または次の文字が、レジスタ１６の拡張文字コード部分１７内にロードされる。
【００３８】
ブロック８０で、ストリングコード部分１８内の文字が、単一文字列であり、かつデータストリーム内で以前に生じていないかどうかが判定される。生じていない場合、部分１８内の文字は、最後に一致したコードとしてバッファレジスタ２２内にロードされる。この手続きは、ディクショナリ１１を初期化せずにデータ圧縮システム１０を開始する唯一の仕方であるだけでなく、ブロック８０で判定が行われた後、ブロック７２ないし７７に関連して説明したとおり初期化されたときと同様に動作するシステム１０を提供する。単一文字コードは、ディクショナリ１１内に記録されていることが可能であるが、ライン１９上のアドレスポインタは、それらのコードにアクセスしないことになる。
【００３９】
ブロック７８で、最初、図１に示すシステムを介して、データストリーム内の第１の文字が、レジスタ２２内にロードされ、またアドレスレジスタ１６のストリングコード部分１８内にもロードされる。次に、データストリーム内の拡張文字または第２の文字が、ブロック７９で示されるとおり、アドレスレジスタの文字コード部分１７内に設定される。システムがこのように開始のために始められると、２つの別個の独立した文字が、ポインタアドレスレジスタ１６内に設定され、またデータストリーム内の第１の文字を示す最後の一致文字が、バッファ２２内に設定されることが理解されよう。図３のこの変形形態は、本明細書で前述したものと同一であるその他のブロック７２〜７７を使用するので、さらなる説明を必要としない。
【００４０】
次に、アクセスされる単一のディクショナリアドレスが、ＨＩＴをもたらすストリングコードを含むときに使用される一連の動作を有する簡略化した流れ図を示す図４を参照する。ブロック８１は、ディクショナリ１１から読み取られたストリングコードがＨＩＴを示すことを示す。ブロック８２は、より長いストリングのための新しいポインタを生成するのが望ましいことを示す。ブロック８３は、ディクショナリ１１から読み取られたストリングコードが、部分１８でアドレスレジスタ１６内にストアされることを示し、またブロック８４は、入力データストリーム内の次の文字に対するコードが、ポインタアドレスレジスタ１６の拡張文字部分１７内にストアされることを示す。ブロック８５は、ポインタアドレスレジスタ１６内の２つのコードを使用して新しいポインタアドレスが生成されることを示す。ブロック８６は、そのポインタアドレスでディクショナリ１１の新しいストリングコード内容が読み取られることを示す。ブロック８７は、ディクショナリのコード内容がバッファレジスタ２２内にストアされることを示す。ブロック８８は、ディクショナリ１１から読み取られた情報コードが以前にストアされたコードを含むかどうかについての論理判定を示す。ディクショナリからコードが読み取られる場合、ライン８９上でＨＩＴが存在し、ブロック８２ないし８８に示す一連の動作が繰り返される。ＨＩＴが存在しない場合、ＭＩＳＳが存在し、一連の動作は、次に、ブロック９１に示すとおり、ＭＩＳＳ論理に進む。
【００４１】
アクセスされる単一のディクショナリアドレスが、ブロック９１Ａに示すとおり、ストリングコードを全く含まずＭＩＳＳをもたらすときに使用される、簡略化した流れ図および一連の動作を示す図５を参照する。図５のブロック９１Ａは、ＭＩＳＳが生じたとき、この論理に従う。情報として、ＭＩＳＳが生じるとき、文字列は、ストリングに追加された最後の追加文字によって新しいストリングがあまりにも長くなったため、それがディクショナリ内でもはや見られないところまで拡張されていることを想起されたい。これが起きたとき、前のＨＩＴが、ディクショナリ内で見られる最長の一致である。ブロック９２は、この最後に一致したＨＩＴコードが、レシーバまたはデコーダに送信されることを示す。最後の一致はレジスタ２２内に保持され、それをライン３２上でレシーバまたはデコーダ３３に出力することができる。ブロック９３は、ポインタアドレスでディクショナリ１１内に、コードジェネレータ５９によって生成された次の逐次コードを書き込むまたはストアする動作を示す。レジスタ１８内の同じコードと最後に一致したバッファ２２内のコードは、同一であることを留意されたい。ただし、これは、ポインタアドレスでディクショナリ内に書き込まれているコードではない。ブロック９３は、次の逐次コードがディクショナリ１１内に書き込まれることを示す。ブロック９４および９５に示し、説明する論理を使用して新しいポインタアドレスを生成することが必要であり、この論理では、アドレスレジスタ部分１７内に最後に入力された拡張文字コードのためのコードが、ポインタアドレスレジスタ１６のストリングコード部分１８内に移動または転送される。新しい文字または次の拡張文字が、ブロック９４および９５によってそれぞれ示されるとおり、レジスタ部分１７内にストアされる。ブロック９６は、次に、レジスタ１６内の情報が使用され、ブロック９４および９５に示されるとおり、レジスタ１６内にロードされた２つのコード部分を使用して新しいポインタアドレスが生成されることを示す。ブロック９７は、ディクショナリ１１のストリングコード内容が、その新しいポインタアドレスでディクショナリから読み取られることを示し、またブロック９８は、ディクショナリ１１のストリングコード内容が出力コードバッファ２２内にストアされることを示す。ブロック９９は、ディクショナリ１１から読み取られた情報が以前にストアされたコードを含むかどうかについての論理判定を示し、ストアされている場合、この論理は、論理ＨＩＴを示すブロック１０１に行き、またストアされていない場合、この論理は、論理ＭＩＳＳを示すブロック１０２に進む。ＨＩＴ論理およびＭＩＳＳ論理は、図４および５にそれぞれ示し、またブロック１０１および１０２にそれぞれ示している。
【００４２】
次に、ディクショナリ１１として使用することができるメモリブロックまたはメモリモジュールの概略を示す図６を参照する。メモリのモジュール１０３は、深さ２２０行、幅１６ビットのであるものとして示している。１６ビットは、１２データ圧縮コードビット、およびディクショナリ１１内に組み込まれるテーブルレベルのために予約した最後の４ビットとして使用することができる。したがって、およそ深さ１００万のビットまたは行、幅１６ビットを有する２つの標準のメモリブロックは、実際には、およそ２．００ドルで購入することができる２メガバイトのモジュールを含む。これは、モジュールが８ビットバイトの形態をとり、共に接続されたとき、１つの幅１６ビットのアドレス指定可能な行を構成することを想定している。以下に説明するとおり、この２メガバイトのモジュールは、変更することなく、本発明におけるディクショナリとして使用すること、あるいはテーブルを広げるため、さらなる４ビットバイトまたは８ビットバイトを追加することによって変更することが可能である。ＬＺＷデータ圧縮を行うとき、ＬＺＷコード内で９ビットないし１２ビットを使用することが通常である。１３ビットを超えてコードビットを拡張する正当な理由はめったにないが、正当な理由がある場合、ディクショナリを拡大することによってより多くのコードビットをディクショナリ内に収容することができる。
【００４３】
次に、深さ２２１ビットで幅は８ビットだけ、つまり幅１バイトであるブロックまたはモジュールとしての同じ量のメモリを示す図７を参照する。この構成では、図６に示すとおり、２つの８ビットバイトが直接に接続され、等価のメモリストレージをもたらす形で２つの行を使用することが可能である。各メモリモジュールは、異なる仕方で接続されてはいるものの、２メガバイトを備え、その費用は同じである。
【００４４】
次に、それぞれ２メガバイトのメモリを備え、それらが図６に示したのと同じタイプであることを示すために１０３Ａ、１０３Ｂ、１０３Ｃと番号を付けた、図６および７に示した型の３つのメモリブロックまたはメモリモジュールの概略を示す図８を参照する。３つの同じモジュール１０３Ａないし１０３Ｃを使用してディクショナリを構成するとき、使用中（ビジー）モジュールである１つのモジュール内で動作を行い、フラッシュまたはリセットした１つの完全に空のモジュールを有し、許容される最大数のストリングコードまでちょうど満たし、まだフラッシュしていない別のモジュールを有することが可能である。
【００４５】
図６〜８の説明では、圧縮コードのために使用するビット数は、１２ビットとして示した。１２ビットを使用すると、４０９６の固有ストリングコードを生成することだけが可能である。図１および２に関連して説明したとおり、およそ１００万のアドレスが存在してはいるものの、４０９６の固有圧縮コードが割り当てられると、ディクショナリは満杯になる。ディクショナリをリセットするテーブルレベル１１Ａシステムを回避するとき、圧縮コードのために、最高でモジュールの１６ビットすべてを使用することが可能である。例えば、図６では、図２の番号１１Ａを参照して説明したテーブルレベル動作のために、１６ビットのうち４ビットが予約されている。したがって、圧縮コードを形成するのに１２ビットだけしか残されていない。しかし、テーブルレベル１１Ａを完全に無くすと、１６ビットすべてを圧縮コードのために利用することができ、この場合、およそ６５０００の別々の圧縮コードを生成することが可能であり、これにより、システムは、それが所望される場合、より長いストリングを生成することができる。可能な２２４のアドレスのうち６５０００だけが埋まっているので、この場合、図８に示す型のディクショナリを構成し、９から１６の間にコード圧縮ビット数を最適化することが可能である。一旦選択したコードビット数によって許容される最大数のコードでディクショナリが埋まると、データ圧縮システムは、リセットコードをデコーダまたはレシーバに送信し、圧縮コードで埋められたモジュールをリフレッシュまたはフラッシュするのを待つ必要なしに、即時に、次のモジュール１０３Ｂ内で先行して新しいコードを生成し、新しいストリングを送信する。この動作を代替の仕方で行い、２つのモジュールだけを使用することも可能であろうが、３つのモジュールが提供された場合、アクティブなモジュールが満杯になる前に、第３のモジュール内でリフレッシュ動作またはフラッシュ動作を前に完了できることが分かっていれば、あるモジュールが使用中のとき、別のモジュールが常に空であることが保証される。
【００４６】
本適用例に記載する型のディクショナリ１１を実現するために、市販のメモリを配置することの簡略化したバージョンを説明したので、３２メガバイトのメモリの費用が、およそ２０．００ドルで購入することができ、本明細書に記載する型のメモリは、コンピュータ動作時間を短縮することにより、非常に短い期間で元が取れることが理解されよう。これは、大きなコンピュータまたはメインフレームコンピュータでは、特にそうである。
【００４７】
次に、図８に示したものと同様の多数のセクション、ブロック、またはモジュールを有する概略図を示す図９を参照する。単一のモジュールをリフレッシュまたはフラッシュすることが所望されるとき、ブロック１０５に示すとおり、２メガバイトのアドレス生成容量を有するクリアアドレスカウンタを使用することができる。これらのアドレスのそれぞれ、および番号１０６で示すモジュールＳ１ないしＳ１６のそれぞれに、すべてゼロを書き込むことが好ましい。他のセクションを除いてクリアされるべきセクション内のアドレスをポイントするための手段として、選択入力１０８を有するマルチプレクサ１０７を使用することができる。したがって、ディクショナリの他のセクションがデータ圧縮システムのために使用されている最中に、セクションを１つずつ選択し、アドレス位置のそれぞれにゼロを書き込むことができる。
【００４８】
次に、ディクショナリ１１の概略、およびディクショナリ内の可能なすべてのアドレスに上書きすることを必要としない、ディクショナリの内容をクリアするための関連する構造を示す図１０を参照する。ライン１９上のアドレスポインタが、ディクショナリ１１内のアドレスにアクセスするとき、補助メモリ１１０内に同じアドレスを書き込むことが可能である。ＡＮＤゲートまたはそれに類するデバイス１１１が、ブロッキングデバイスとして動作しているものとして示している。というのは、ＭＩＳＳが生じたときにだけ、そのアドレスを記録すればよいからである。したがって、ＭＩＳＳが生じるたびに毎回、アドレスカウンタ１１２のカウントが、メモリ１１０内でステップされ、データ圧縮動作中に情報がその中にストアされる４０９６のアドレスが、結果として、なんらかの順序でメモリ１１０内にストアされることになる。この場合、これらのアドレスを使用し、クリアアドレスカウンタとともにアドレスポインタを生成し、情報がそこにストアされていることが分かっているアドレスだけをクリアするように、すべてゼロを生成することが可能である。
【００４９】
この場合、４０９６のアドレスのためのコードストーレッジを実装するのに必要なメモリをディクショナリ１１として使用するのと同じメモリモジュールで実現してもよいことが認められよう。
【００５０】
ディクショナリを探索する必要なしに、データ圧縮を行うことの基本原理を説明したので、このシステムを実施する多くの仕方が存在することが理解されよう。例えば、メモリは、現在、とても安価で、さらに安価になっているので、ほとんどの適用例において専用メモリが見合うものとなる可能性があり、さらなる速度が必要とされる場合、示したステップおよび動作のいくつかは、図１〜５に示すアルゴリズムおよびステップを実現する安価な専用ハードウェア実装形態によって実行することができる。
【００５１】
安価なメモリで置き換えることにより、テーブルまたはテーブルレベル１１Ａを無しで済ますのが可能なことを説明したので、システム全体がソフトウェアで実行されるとき、テーブルレベル実装形態を使用するのが望ましい可能性がある。
【００５２】
マルチプロセッシングシステムを使用して大きいファイルに対するデータ圧縮を行うことが望ましい場合、本発明を使用し、またそのメモリが満杯になるまで、複数のプロセッサの１つを使用してデータ圧縮を行い、次に、そのデータ圧縮システム内の第２のプロセッサにそのデータストリームを切り替え、データ圧縮を行いつづけ、その一方で第１のプロセッサはそのディクショナリをフラッシュして、データ圧縮の速度を最適化することが可能である。
【００５３】
中央プロセッシングシステムに売上げおよび在庫を送信する大手の製造業者は、自らのデータをリアルタイムで圧縮し、十分な帯域幅を有するリンクを介してそのデータをより高速に送信することができる。通信リンクが、データ圧縮システムよりも遅い場合、圧縮データは、バッファシステム内に迅速にストアし、データ圧縮を行うコンピュータシステムを不利にすることなく、リンクが提供する最大限の速度で送信することができる。
【００５４】
探索するストリングに対してディクショナリ内にコードまたは値がストアされているか否かを単一回の読取り動作で判定するための、好ましい実施形態としてのディクショナリおよびアドレスポインタを説明したので、本発明をコンピュータ内のソフトウェアで実行するのが可能である、またはハードウェアおよびソフトウェアを使用して実施するのが可能であることが理解されよう。文字のコードセットを使用してディクショナリを初期化することの利点、およびトランスミッタおよびレシーバがともに使用されているコードセットを知っているとき、ディクショナリを初期化しないことの利点が存在する。少しでも疑念がある場合、圧縮データに先立ってコードセットおよびプロトコルを送信することができる。ディクショナリをコードセットで初期化しない場合、コンプレッサが初期にその欠如を補い、単一文字コードをディクショナリ内にストアさせる。ただし、ディクショナリ内に複数文字列コードがストアされていると、新規のアドレスポインタは、同じ新規のＨＩＴ結果またはＭＩＳＳ結果を生成することになる。テーブルレベルの変形実施形態では、異なるテーブルレベル内の異なるアドレスに同じ複数ストリングコードを書き込むことが可能である。ディクショナリ内に新しいシーケンスのストリングコード値が書き込まれるデータ圧縮動作中、１つのテーブルレベルだけが有効であるので、ＨＩＴが生じたとき、正しい最後に一致したコードがわかり、レジスタ１８内に書き込むためにその正しい最後に一致したコードがバッファ２２に読み込まれる限り、競合は存在しない。言い換えれば、ＨＩＴまたはＭＩＳＳが生じたかを判定するのに、そのポインタアドレスのテーブルレベルだけを使用することができる。すべてのＨＩＴに続き、次のポインタアドレスを構成するために最後に一致したコードを利用することができる。ＭＩＳＳに続き、次のポインタアドレスは、ディクショナリの外で利用可能な２つの単一文字コードを含み、したがって、ＨＩＴが生じたとき、テーブルレベルを使用してＨＩＴまたはＭＩＳＳを判定するのに、最後に一致したコードを有するだけでよい。
【図面の簡単な説明】
【図１】データストリーム中に見出される英数字または記号のストリングを表すコードを生成するためのデータ圧縮システムの好ましい実施形態の概略ブロック図である。
【図２】ディクショナリ上またはディクショナリ中に付加されるテーブルレベル機能を示す、図１に示すデータ圧縮システムの変形実施形態の概略構成図である。
【図３】ディクショナリ探索を、データ圧縮システムにおける単一のディクショナリポインタアドレスに制限するために使用される動作シーケンスを示す簡易流れ図である。
【図３Ａ】ディクショナリが初期化されない場合における、図３に示す流れ図を変形した動作シーケンスの簡易流れ図である。
【図４】アクセスされる単一のディクショナリポインタアドレスが、ＨＩＴの結果をもたらすストリングコードを含む場合に使用される動作シーケンスを示す簡易流れ図である。
【図５】アクセスされる単一のディクショナリポインタアドレスが、ＭＩＳＳの結果をもたらすストリングコードを含まない場合に使用される動作シーケンスを示す簡易流れ図である。
【図６】本発明におけるディクショナリのために使用されるメモリのブロックすなわちモジュールの概略図である。
【図７】図６に示す構成とは異なるメモリの他のブロックすなわちモジュールの概略図である。
【図８】図６および７に示すタイプのメモリの３つのブロックすなわちモジュールの概略図である。
【図９】メモリが満杯になり、動作不能の場合にブロックをクリアするための構造を示す、複数のブロックすなわちモジュールを有し、常時そのうちの１つしか動作することができない大型ディクショナリの概略図である。
【図１０】ディクショナリと、ディクショナリを直ちにリセットすることが望ましい場合に、ディクショナリの内容をフラッシングすなわちクリアするための構造を示す概略図である。
【図１】
0003611319.tif 000002
【図２】
0003611319.tif 000003
【図３】
0003611319.tif 000004
【図３Ａ】
0003611319.tif 000005
【図４】
0003611319.tif 000006
【図５】
0003611319.tif 000007
【図６】
0003611319.tif 000008
【図７】
0003611319.tif 000009
【図８】
0003611319.tif 000010
【図９】
0003611319.tif 000011
【図１０】
0003611319.tif 000012