WO2014097359A1 - 圧縮プログラム、圧縮方法、圧縮装置およびシステム - Google Patents

Abstract

　一側面において、圧縮処理において動的に生成される圧縮辞書を用いつつ、部分的に伸張を実行可能な圧縮データを生成することを目的とする。　本開示の圧縮プログラムが、コンピュータに、圧縮対象のファイル内に含まれるデータのうち、複数回出現するデータに対して圧縮符号を割り当てることにより、圧縮辞書の生成を行ない、生成された前記圧縮辞書に基づいて前記ファイル内のデータに対して圧縮処理を実行する、処理を実行させる。

Description

圧縮プログラム、圧縮方法、圧縮装置およびシステム

　本発明は、データの圧縮技術または伸張技術の少なくとも一方に関する。

　ＬＺ７７と呼ばれる圧縮アルゴリズムがあり、ＺＩＰなどの圧縮ファイルフォーマットに採用されている。

　ＬＺ７７では、圧縮対象ファイルの先頭から順次圧縮処理が行なわれる。ＬＺ７７においては、データ参照領域（スライド窓などと呼ばれる）が設定され、圧縮対象ファイルのうち、圧縮処理が行なわれたデータは、順次スライド窓に格納される。スライド窓のサイズは予め設定されており、スライド窓内に格納されるデータがスライド窓のサイズを超えると、スライド窓内に先に格納されたデータを更新しつつデータが格納される。

　ＬＺ７７において順次行なわれる圧縮処理は、スライド窓内に含まれるデータのうち、圧縮対象ファイル内で圧縮処理の処理対象となるデータと最も長く一致するデータ列（最長一致データ列）に基づいて生成される圧縮符号が用いられる。圧縮符号は、スライド窓の最長一致データ列の一致長およびスライド窓内の位置を組み合わせた情報である。

　ＬＺ７７によれば、最長一致データ列の一致長が長いほど、多くのデータが１つの圧縮符号（一致長と位置との組み合わせ）により表現されるので、圧縮率が向上する。一致長の長い最長一致データ列が多く抽出されれば圧縮率が向上するので、スライド窓のサイズが大きくなれば圧縮率が向上する傾向にある。これは、より多くのデータから処理対象のデータと一致するデータを探し当てることになるため、一致長が長いデータ列を特定する確率が向上するためである。

　また、伸張処理においては、圧縮ファイルの先頭から順に読み出される圧縮符号毎に、スライド窓を参照して伸張されるとともに、伸張されたデータによりスライド窓内のデータが更新される。順次更新されるスライド窓内のデータに基づいて圧縮符号が伸張される。

特開平５－２４１７７７号公報

　しかしながら、ＬＺ７７によれば、動的に更新されるスライド窓を用いて圧縮データが生成されるので、伸張時には、圧縮ファイルの先頭から伸張することによりスライド窓に復元されたデータを利用することとなる。もし、その圧縮データのうち一部分のデータが必要な場合にも、部分的な伸張処理ではなく、圧縮データの始めから伸張処理を行なうことになり、伸張に多大な時間を費やすことになってしまう。

　本発明の一側面において、最長一致データ列に基づく圧縮符号を用いつつ、部分的に伸張できる圧縮データを生成することを目的とする。

　一態様によれば、圧縮プログラムは、コンピュータに、ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書の生成を行ない、前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう、処理を実行させる。

　一態様によれば、コンピュータに、ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書の生成を行ない、前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう、ことを実行させる圧縮方法が用いられる。

　一態様によれば、圧縮装置が、ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書を生成する生成部と、前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう処理部と、を含む。

　一態様によれば、圧縮装置と伸張装置とを含む圧縮伸張システムであって、前記圧縮装置が、ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書を生成する生成部と、前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう処理部と、前記圧縮処理により得られた圧縮データと前記圧縮辞書とを前記伸張装置に送信する送信部と、を含み、前記伸張装置が、前記圧縮装置から受信した圧縮データを、前記圧縮辞書に基づいて伸張する伸張部、を含む。

　一態様によれば、圧縮プログラムは、コンピュータに、ファイル内のデータに基づいて、静的な圧縮符号の割り当て対象を動的に生成し、生成された前記割り当て対象に圧縮符号を割り当てた圧縮辞書に基づいて、前記ファイルに対して圧縮処理を行なう、処理を実行させる。

　一側面によれば、最長一致データ列に基づく圧縮符号用いつつ、部分的に伸張できる圧縮データを生成できる。

図１は、圧縮処理の流れの一例を示す。 図２は、圧縮辞書の一例を示す。 図３は、圧縮ファイルのブロック構成例を示す。 図４は、伸張処理の流れの一例を示す。 図５は、部分伸張の例を示す。 図６は、機能構成例を示す。 図７は、圧縮処理の手順例を示す。 図８は、位置情報テーブルＴ１の例を示す。 図９は、記憶領域Ａ２の参照処理の手順例を示す。 図１０は、圧縮辞書の更新処理の手順例を示す。 図１１は、記憶領域Ａ２の更新処理の手順例を示す。 図１２は、圧縮辞書の参照処理の手順例を示す。 図１３は、圧縮辞書テーブルＴ２を示す。 図１４は、圧縮辞書テーブルＴ２の参照処理の手順例を示す。 図１５は、圧縮辞書テーブルＴ２の更新処理の手順例を示す。 図１６は、圧縮辞書Ｄ１を用いた処理の概要を示す。 図１７は、圧縮辞書Ｄ１の参照処理の手順例を示す。 図１８は、登録対象データの登録処理の手順例を示す。 図１９は、参照テーブルＴ３の参照処理の手順例を示す。 図２０は、登録対象データの登録処理の手順例を示す。 図２１は、コンピュータ１のハードウェア構成例を示す。 図２２は、コンピュータ１で動作するプログラムの構成例を示す。 図２３は、実施形態のシステムにおける装置の構成例を示す。

　下記に図面を参照しつつ、実施形態について説明する。

　図１は、圧縮処理の流れの一例を示す。圧縮処理のワークエリアとして、メモリに記憶領域Ａ１、記憶領域Ａ２、記憶領域Ａ３および記憶領域Ａ４が設けられる。圧縮対象のファイルＦ１が記憶領域Ａ１にロードされ、ロードされたデータが順次読み出され、読み出された処理対象のデータに基づいて、圧縮データの生成（図１中の「照合１」など）と記憶領域Ａ２の更新（図１中の「更新」など）とが行なわれる。生成された圧縮データは順次記憶領域Ａ４に格納され、記憶領域Ａ４に格納された圧縮データに基づき、圧縮ファイルＦ２が出力される。記憶領域Ａ３には圧縮辞書が格納されており、処理対象のデータに記憶領域Ａ２のデータと処理対象のデータとの照合（図１中の「照合２」など）の結果に応じて、圧縮辞書内にデータが登録される（図１中の「登録」）。例えば、照合２において得られる最長一致データ列が、所定の長さＬｍｉｎ以上の長さである場合に、最長一致データ列が圧縮辞書に登録される。記憶領域Ａ１、記憶領域Ａ２および記憶領域Ａ３は、それぞれ符号化部、参照部および辞書部などと呼ばれる。圧縮データとして、例えば、照合１の結果に応じて、本圧縮アルゴリズムの圧縮辞書に登録された圧縮符号か、または処理対象のデータをハフマン符号化して得られるハフマン符号が用いられる。また、ハフマン符号の代わりに、処理対象のデータそのものや、他の圧縮アルゴリズムにより生成される圧縮符号が用いられてもよい。

　図２は圧縮辞書の一例を示す。図２に示される圧縮辞書は、記憶領域Ａ３と参照テーブルＴ３により構成される。参照テーブルＴ３には、図１中の「登録」により記憶領域Ａ３内に最長一致データ列が順次格納される。また、最長一致データ列が登録されるごとに、参照テーブルＴ３に最長一致データ列の記憶領域Ａ３における格納位置と長さとが格納される。最長一致データ列の格納位置および長さが登録される参照テーブルＴ３内の位置を示す登録番号が、最長一致データ列に対応する圧縮符号として用いられる。図１中の「照合１」により、記憶領域Ａ３内のデータと処理対象のデータとの照合が行なわれ、照合の結果、合致するデータが得られた場合には、合致するデータの記憶領域Ａ３内での位置及びデータの長さと参照テーブルＴ３により対応づけられた圧縮符号が生成される。

　図１の例では、ファイルＦ１内に「・・・１ｓｔ　ｈｏｒｓｅ・・・２ｎｄ　ｈｏｒｓｅ・・・３ｒｄ　ｈｏｒｓｅ・・・」という文字列のデータが含まれる（「・・・」は不特定の文字列を示す）。ファイルＦ１は記憶領域Ａ１にロードされ、ロードされたデータは順に読み出される。以下に、図１に示す圧縮データｄ１～ｄ３それぞれの生成処理の流れを説明する。

　例えば、「１ｓｔ　ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである（記憶領域Ａ１からの読出し位置が「１ｓｔ　ｈｏｒｓｅ・・・」の「ｈ」の位置である）場合には、記憶領域Ａ３内で「ｈｏｒｓｅ・・・」の最長一致データ列が探索される。処理対象のデータが「１ｓｔ　ｈｏｒｓｅ・・・」の「ｈ」以降である場合には、図１に示す通り、記憶領域Ａ３にはデータが格納されていない状態なので、そもそも先頭のデータである「ｈ」と一致するデータが存在しない。そのため、所定の長さＬｍｉｎ以上の長さの最長一致データ列が得られないので、処理対象のデータと記憶領域Ａ２に格納されるデータとの照合処理である「照合２」が行なわれる。「照合２」では、記憶領域Ａ２に格納されたデータのそれぞれと処理対象のデータの先頭である「ｈ」との照合が行われる。しかしながら、記憶領域Ａ２内にもそもそも「ｈ」と一致するデータが存在しない。そのため、所定の長さＬｍｉｎ以上の長さの最長一致データ列が存在しないので、処理対象のデータの先頭データ「ｈ」のハフマン符号化が行なわれる。「１ｓｔ　ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータとなった場合の圧縮データｄ１は、ハフマン符号化により得られた圧縮符号と、ハフマン符号化により生成された圧縮符号であることを示す識別子（図１の例においては「０」）とを含む。上述した通り、圧縮データｄ１に含まれる圧縮符号の部分は、他の圧縮アルゴリズムに基づく圧縮符号でもよいし、処理対象のデータの先頭データ（「ｈ」）そのものでもよい。生成された圧縮データｄ１は記憶領域Ａ４に書き込まれる。さらに、処理対象のデータの先頭データ（「ｈ」）について処理が行なわれたので、記憶領域Ａ２に「ｈ」が格納される（図１中の「更新」）。

　例えば、「２ｎｄ　ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである（記憶領域Ａ１からの読出し位置が「２ｎｄ　ｈｏｒｓｅ・・・」の「ｈ」の位置である）場合には、記憶領域Ａ３内で「ｈｏｒｓｅ・・・」の最長一致データ列が探索される。図１に示す通り、記憶領域Ａ３にはデータが格納されていない状態なので、そもそも先頭のデータである「ｈ」と一致するデータが存在しない。すなわち、「照合１」により所定の長さＬｍｉｎ以上の長さの最長一致データ列が得られないので、さらに、記憶領域Ａ２内で「ｈｏｒｓｅ・・・」の最長一致データ列が探索される（照合２）。記憶領域Ａ２内には既に「・・・１ｓｔ　ｈｏｒｓｅ・・・」が格納されている。例えば、まず記憶領域Ａ２に対して「ｈ」の探索が行われ、探索により得られた記憶領域Ａ２内の「ｈ」の箇所から「ｏ」、「ｒ」、「ｓ」、「ｅ」・・・と連続しているか否か、順次照合される。図１の例では、処理対象のデータ「ｈｏｒｓｅ・・・」と記憶領域Ａ２内の「・・・１ｓｔ　ｈｏｒｓｅ・・・」の「ｈｏｒｓｅ」の部分が一致する。図１には、一致した「ｈｏｒｓｅ」が最長一致データ列であり、一致長が所定の長さＬｍｉｎ以上である場合が例示されている。図１のように、最長一致データ列「ｈｏｒｓｅ」が所定の長さＬｍｉｎ以上である場合には、「ｈｏｒｓｅ」が記憶領域Ａ３内に登録される。また、圧縮辞書への登録内容に基づいて圧縮符号が生成される。生成される圧縮符号は、圧縮辞書内での格納位置および登録された最長一致データ列のデータ長を示す。「２ｎｄ　ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである場合の圧縮データｄ２は、生成された圧縮符号と、圧縮符号が圧縮辞書に基づいて生成されたことを示す識別子（図１の例においては「１」）とを含む。生成された圧縮データｄ２は記憶領域Ａ４に格納される。さらに、「照合２」による最長一致データ列「ｈｏｒｓｅ」について処理が行なわれたので、記憶領域Ａ２に「ｈｏｒｓｅ」が格納される（図１中の「更新」）。

　「３ｒｄ　ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである場合には、記憶領域Ａ３内で「ｈｏｒｓｅ・・・」の最長一致データ列が探索される（「照合１」）。図１に示す通り、記憶領域Ａ３内には既に「ｈｏｒｓｅ」が格納されている。例えば、まず記憶領域Ａ３に対して「ｈ」の探索が行われ、探索により得られた記憶領域Ａ３内の「ｈ」の箇所から「ｏ」、「ｒ」、「ｓ」、「ｅ」・・・と連続しているか否か、順次照合される。図１の例では、照合１によりデータ列「ｈｏｒｓｅ」が一致する。図１には、一致した「ｈｏｒｓｅ」が最長一致データ列であり、一致長が所定の長さＬｍｉｎ以上である場合が例示されている。図１に示すように、最長一致データ列「ｈｏｒｓｅ」が所定の長さＬｍｉｎ以上である場合は、記憶領域Ａ３内での格納位置および一致長に対応する登録番号が参照テーブルＴ３から取得される。「３ｒｄ　ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである場合の圧縮データｄ３は、取得された登録番号を圧縮符号として含み、さらに、圧縮符号が圧縮辞書（記憶領域Ａ３および参照テーブルＴ３）に基づいて生成されたことを示す識別子（図１の例においては「１」）とを含む。さらに、「照合１」による最長一致データ列「ｈｏｒｓｅ」について処理が行なわれたので、記憶領域Ａ２に「ｈｏｒｓｅ」が格納される（図１中の「更新」）。

　図１の圧縮処理の変形例においては、例えば、圧縮データｄ２または圧縮データｄ３のように識別子「１」の圧縮データを生成した場合には図１中の「更新」が行なわれず、圧縮データｄ１のように識別子「０」の圧縮データを生成した場合にのみ「更新」が行なわれる。

　記憶領域Ａ１～Ａ４について圧縮処理でアクセスに用いられる位置の情報の管理も行なわれる。位置情報の管理については後述するが、例えば、記憶領域Ａ１からのデータ読み出しの位置、記憶領域Ａ２のデータ更新の位置やデータ参照の位置、記憶領域Ａ３の登録位置やデータ参照の位置、さらには、記憶領域Ａ４へのデータ書込みの位置が管理される。

　記憶領域Ａ２および記憶領域Ａ３は、例えば、それぞれデータサイズが定められた（例えば数キロバイト～数十キロバイト程度）記憶領域である。例えば、記憶領域Ａ２に定められたデータサイズ以上のデータが格納される場合には、記憶領域Ａ２の先頭に格納された古いデータの上から新しいデータが格納される。記憶領域Ａ２内に格納されるデータは、例えば、データの格納に応じて更新される書込み位置からの相対的なアドレスによりその位置が示される。また、例えば、書き込み位置からの相対的なアドレスにより記憶領域Ａ２に格納されたデータ同士での格納順序の先後が示される。記憶領域Ａ３は、例えば、入力ファイルの大きさに応じて、データサイズが定められた（例えば、数キロバイト～数十キロバイト程度）記憶領域である。例えば、定められたデータサイズ以上のデータが格納される場合には、新しいデータの格納は抑止される。図３は、圧縮ファイルのブロック構成例を示す。図３において、ファイルＦ１はｎ個のブロックに分割されている。ブロックは、ファイルＦ１を所定サイズのデータごとに分割して得られるものでもよいし、ファイルＦ１に含まれる区切り指定（例えば、ＨＴＭＬ文書におけるタグ（例えば＜ｈ１＞や＜ｐ＞など））に基づいて分割して得られるものでもよい。例えば、ファイルＦ１における各ブロックの開始位置を示すアドレス情報（Ｘ０～Ｘｎ－１）と、圧縮された状態の各ブロックの圧縮ファイルＦ２内での開始位置を示すアドレス情報（Ｙ０～Ｙｎ－１）とが、各ブロックのブロック番号に対応付けて管理テーブルＴ０に格納される。管理テーブルＴ０は、圧縮ファイルＦ２のトレーラ情報に含まれ、圧縮ファイルＦ２の部分伸張が行なわれる際に参照される。また、圧縮ファイルＦ２は、例えば圧縮ファイルＦ２の生成に用いられたハフマン符号化の符号化辞書Ｅ１をヘッダ情報に含み、圧縮辞書をトレーラ情報に含む。

　トレーラ情報に含まれる圧縮辞書は、圧縮処理が完了後（例えば、後述の図７のＳ１１１の時点）のものが格納される。ヘッダ情報は、例えば、圧縮ファイルＦ２の生成に用いられた圧縮アルゴリズムを識別する情報や、圧縮に用いられたパラメータなどの情報を含む。また、例えば、圧縮ファイルＦ２内に含まれるヘッダ情報、圧縮データおよびトレーラ情報の範囲を示す情報を含む。

　また、圧縮処理の変形例として、各ブロックについて圧縮辞書が生成されることとしてもよい。その場合には、管理テーブルＴ０に、各ブロックのブロック番号と対応付けて、各ブロックに対して生成された圧縮辞書の識別情報（図１中の辞書番号）が格納される。

　図１に示す圧縮処理によれば、最長一致データ列の探索により抽出された最長一致データ列が圧縮辞書に登録される。さらに、圧縮辞書に登録されたデータ列に対応する圧縮符号が変化しないので、圧縮符号をファイルＦ１内のどの位置においても共通して用いることができる。これにより、ＬＺ７７のスライド窓へのデータの復元の必要性から開放され、ブロックのアドレス情報と組み合わせることで、部分的な伸張が可能となる。また、参照テーブルＴ３を用いることにより、最長一致データ列の格納位置および長さという２種類の情報ではなく、登録番号という１種類情報により圧縮符号が構成されるため、圧縮効率の向上を図ることができる。

　上述のように、ファイル内のデータ列同士の照合によりデータ列と圧縮符号との対応関係を確定させる圧縮辞書を用いた圧縮により、長いデータ列が繰り返し出現するファイルを効率よく（圧縮率を維持しつつ）圧縮し、且つ部分伸張可能とすることができる。また、ファイルＦ１に対して１回のデータ読み出しで圧縮辞書の生成と圧縮処理とが行なわれる。そのため、圧縮辞書を生成してから圧縮辞書に基づいて圧縮処理を行なうよりも、メモリアクセスが抑制される。

　図４は、伸張処理の流れの一例を示す。伸張処理のワークエリアとして、メモリに記憶領域Ｂ１、記憶領域Ｂ３および記憶領域Ｂ４が設けられる。記憶領域Ｂ１にロードされた圧縮ファイルＦ２のコンテンツ部分から順次圧縮データが読み出され、読み出された処理対象の圧縮データに基づいて伸張データの生成が行なわれる。この際、圧縮データに含まれる識別子に応じた生成処理が行なわれる。生成された伸張データは順次記憶領域Ｂ４に格納され、記憶領域Ｂ４に格納された伸張データに基づいて伸張ファイルＦ３が生成される。また、記憶領域Ｂ３には、圧縮ファイルＦ２に含まれる圧縮辞書がロードされる。記憶領域Ａ１および記憶領域Ａ３は、それぞれ符号化部および辞書部と呼ばれる。以下に、図４に示す圧縮データｄ１～ｄ３のそれぞれの例について伸張処理を説明する。

　処理対象の圧縮データが圧縮データｄ１である（記憶領域Ｂ１の読出し位置に圧縮データｄ１が存在する）場合に、まず圧縮データｄ１の識別子が判断される。圧縮データｄ１の識別子は、ハフマン符号化による圧縮を示す（「０」である）ので、圧縮データｄ１に対して、ハフマン符号化アルゴリズムに基づき、復号化が行なわれる。

　処理対象の圧縮データが圧縮データｄ２である（記憶領域Ｂ１の読出し位置に圧縮データｄ２が存在する）場合に、まず圧縮データｄ２の識別子が判断される。圧縮データｄ２の識別子は圧縮辞書による圧縮を示す（「１」である）ので、圧縮データｄ２内の圧縮符号に基づいて圧縮辞書の参照が行なわれる。具体的には、圧縮辞書に含まれる参照テーブルＴ３から圧縮符号に対応する記憶領域Ａ３内の位置および長さの指定が読み出され、記憶領域Ａ３から指定に応じたデータが読み出される。読み出されたデータが伸張データとなる。圧縮データｄ２内の圧縮符号は、圧縮辞書内の「ｈｏｒｓｅ」を示すので、伸張データとして「ｈｏｒｓｅ」が生成される。

　処理対象の圧縮データが圧縮データｄ３である（記憶領域Ｂ１の読出し位置に圧縮データｄ３が存在する）場合に、まず圧縮データｄ３の識別子が判断される。圧縮データｄ３の識別子は圧縮辞書による圧縮を示す（「１」である）ので、圧縮データｄ３内の圧縮符号に基づいて圧縮辞書の参照が行なわれる。具体的には、圧縮辞書に含まれる参照テーブルＴ３から圧縮符号に対応する記憶領域Ａ３内の位置および長さの指定が読み出され、記憶領域Ａ３から指定に応じたデータが読み出される。読み出されたデータが伸張データとなる。圧縮データｄ３内の圧縮符号は、圧縮辞書内の「ｈｏｒｓｅ」を示すので、伸張データとして「ｈｏｒｓｅ」が生成される。

　図５は、部分伸張の例を示す。圧縮ファイルＦ２を部分的に伸張する場合には、例えば、伸張データの範囲が指定される。例えば、ファイルの指定（ファイルＦ１）と、要求範囲の開始アドレスＸｉおよび終了アドレスＸｊの指定とを含む伸張要求により、伸張データの範囲が指定される。ファイルの指定に応じて部分伸張の対象ファイルが決定される。図５の例においては、圧縮ファイルＦ２の元となるファイルＦ１が指定されたことに基づいて、圧縮ファイルＦ２の部分伸張処理が行なわれる。

　伸張要求で指定された範囲に基づいて、伸張を行なうブロックが判断される。図５の例においては、開始アドレスＸｉがブロック番号２の開始アドレスＸ１よりも大きく、ブロック番号３の開始アドレスＸ２よりも小さい。また、終了アドレスＸｊがブロック番号３の開始アドレスＸ２よりも大きく、ブロック番号４の開始アドレスＸ３よりも小さい。すなわち、伸張要求で指定された範囲は、ブロック番号２およびブロック番号３に含まれる。そのため、ブロック２およびブロック番号３のみを圧縮ファイルＦ２からロードし、伸張が行なわれれば、伸張を要求された範囲のデータが生成される。

　またブロックごとに異なる圧縮辞書を用いて圧縮が行なわれている場合には、各ブロックの伸張処理において、管理テーブルＴ０の辞書番号を参照し、参照した辞書番号に対応する圧縮辞書に基づいて伸張が行なわれる。

　図６は、機能構成例を示す。本実施形態の処理を実行するコンピュータ１は、圧縮部１１、伸張部１２および記憶部１３を含む。圧縮部１１は圧縮処理を行ない、伸張部１２は伸張処理を行なう。記憶部１３は、圧縮対象のファイルＦ１や、圧縮処理により得られるファイルＦ２や、ファイルＦ２を伸張して得られるファイルＦ３などを格納する。また、記憶部１３は、圧縮部１１や伸張部１２のワークエリアとして用いられる。圧縮部１１は、制御部１１１、参照部１１２、更新部１１３、参照部１１４および更新部１１５を含む。

　制御部１１１は、圧縮処理を実行させるために参照部１１２、更新部１１３、参照部１１４および更新部１１５を制御し、各機能部の処理の実行制御を行なう。また、制御部１１１は、各機能部の処理に用いるデータを保持するため、記憶部１３に記憶領域（例えば、図１に示す記憶領域Ａ１および記憶領域Ａ２）を確保する。参照部１１２は、記憶領域Ａ１内の処理対象のデータに基づき、記憶領域Ａ２内のデータの参照処理を実行する。この参照処理は、例えば、記憶領域Ａ２内の各データと処理対象のデータとの照合により行なわれる。更新部１１３は、記憶領域Ａ１の処理対象のデータの読出しに応じて、記憶領域Ａ２内のデータを更新する。参照部１１４は、処理対象のデータに基づき圧縮辞書の参照処理を実行する。参照部１１４による圧縮辞書内の参照結果に応じて、制御部１１１は圧縮データを生成する。更新部１１５は、参照部１１２による記憶領域Ａ２の参照結果に応じて、圧縮辞書を更新する。続いて、各機能部による処理の実行手順について、後述する。

　図７は、圧縮処理の手順例を示す。まず、コンピュータ１内のオペレーティング・システムやアプリケーションプログラムの動作により圧縮機能が呼び出される（Ｓ１０１）と、制御部１１１は、前処理を実行する（Ｓ１０２）。Ｓ１０２の前処理は、例えば、図１に示す記憶領域Ａ１および記憶領域Ａ２の確保、圧縮済データを記憶する記憶領域Ａ４の確保、各記憶領域内の位置情報の設定、圧縮辞書の格納領域の確保などである。

　図８は、位置情報テーブルＴ１の例を示す。位置情報テーブルＴ１は、各記憶領域（記憶領域Ａ１、記憶領域Ａ２および記憶領域Ａ４など）へのアクセス位置の管理に用いられる。位置情報テーブルＴ１には、ファイルＦ１を展開する記憶領域Ａ１の記憶部１３における開始位置Ｐ１、終了位置Ｐ２および読出し位置Ｐ３が設定される。また、位置情報テーブルＴ１には、さらに、記憶領域Ａ２の記憶部１３における開始位置Ｐ４、終了位置Ｐ５、参照位置Ｐ６および更新位置Ｐ７が設定される。位置情報テーブルＴ１には、記憶領域Ａ４の記憶部１３における開始位置Ｐ８、終了位置Ｐ９、書込み位置Ｐ１０が設定される。位置情報テーブルＴ１に格納されるそれぞれの位置情報の初期値は、Ｓ１０２の前処理において制御部１１１により設定される。例えば、読み出し位置Ｐ３の初期値は開始位置Ｐ１と同じであり、参照位置Ｐ６および更新位置Ｐ７の初期値も開始位置Ｐ４と同じであり、書込み位置Ｐ１０の初期値も開始位置Ｐ８と同じである。

　Ｓ１０２の処理を終えると、次に、制御部１１１は、圧縮対象のファイルＦ１を記憶領域Ａ１に展開する（Ｓ１０３）。次に、制御部１１１は、参照部１１４に圧縮辞書の参照処理を実行させる（Ｓ１０４）。参照部１１４は、記憶領域Ａ１の読出し位置Ｐ３を始点とする処理対象のデータに基づいて、圧縮辞書の参照処理を実行する。Ｓ１０４の参照処理については、図１２に基づいて後述する。Ｓ１０４の参照処理により、参照部１１４は、圧縮辞書から処理対象のデータに対応する圧縮符号か、または、対応する圧縮符号が存在しない旨を示す情報を制御部１１１に返す。

　参照部１１４による参照結果が制御部１１１に返されると、制御部１１１は、参照部１１１に記憶領域Ａ２の参照処理を実行させる（Ｓ１０５）。参照部１１２は、処理対象のデータに基づいて記憶領域Ａ２を参照する。図９は、記憶領域Ａ２の参照処理の手順例を示す。参照部１１２は、制御部１１１により記憶領域Ａ２の参照を指示される（Ｓ２００）と、記憶領域Ａ２の参照位置Ｐ６、一致長Ｌａ、最長一致位置Ｐａをセット（例えばＰ６＝Ｐ１、Ｌａ＝０、Ｐａ＝Ｐ１などと設定）する（Ｓ２０１）。一致長Ｌａ、最長一致位置Ｐａは、記憶部１３内に記憶される。Ｓ２０１の処理を終えると、参照部１１２は、さらに、カウンタ値ｉのセットを行なう（Ｓ２０２）。カウンタ値ｉは、「０」にセットされる。

　Ｓ２０２の処理を終えると、参照部１１２は、処理対象のデータと記憶領域Ａ２内のデータとの照合を行なう。この照合において、参照部１１２は、記憶領域Ａ１の読出し位置Ｐ３からカウンタ値ｉずれた位置（Ｐ３＋ｉ）のデータと、記憶領域Ａ２の参照位置Ｐ６からカウンタ値ｉずれた位置（Ｐ６＋ｉ）のデータとが一致するか否かの判定（Ｓ２０３）を行なう。

　参照部１１２がＳ２０３の判定においてデータ同士が一致すると判定した場合（Ｓ２０３：ＹＥＳ）には、参照部１１２はカウンタ値ｉをインクリメントする（Ｓ２０４）。参照部１１２は、続いて、Ｓ２０４でインクリメントされたカウンタ値ｉが設定値Ｌｍａｘ以上であるか否か判定する（Ｓ２０５）。カウンタ値ｉが設定値Ｌｍａｘよりも小さい場合（Ｓ２０５：ＮＯ）には、Ｓ２０３の判定が再度行なわれる。上記のＳ２０３～Ｓ２０５の処理により、読み出し位置Ｐ３からのデータ（処理対象のデータ）と参照位置Ｐ６からのデータ列とについて、１つずつ合致しているか否かの判定が行なわれる。カウンタ値ｉは処理対象のデータと一致するデータの長さを示す。設定値Ｌｍａｘは予め設定された値であり、最長一致の上限値を示す。

　Ｓ２０５の判定でカウンタ値ｉが設定値Ｌｍａｘ以上である場合（Ｓ２０５：ＹＥＳ）には、参照部１１２は、一致長Ｌａをカウンタ値ｉに更新し（Ｓ２０６）、最長一致位置Ｐａを参照位置Ｐ６に更新する（Ｓ２０７）。図９のＳ２０６とＳ２０７とに示す「＝」は代入演算子である。Ｓ２０６とＳ２０７との処理順序は逆でもよい。Ｓ２０６およびＳ２０７で値を更新すると、参照部１１２は、値が代入された一致長Ｌａおよび最長一致位置Ｐａを制御部１１１に返す（Ｓ２１３）。

　Ｓ２０３の判定でデータ同士が一致しないと判定された場合（Ｓ２０３：ＮＯ）には、参照部１１２は、カウンタ値ｉが一致長Ｌａよりも大きいか否か判定する（Ｓ２０８）。カウンタ値ｉが一致長Ｌａよりも大きい場合には（Ｓ２０８：ＹＥＳ）、参照部１１２は、一致長Ｌａをカウンタ値ｉに更新し（Ｓ２０９）、最長一致位置Ｐａを参照位置Ｐ６に更新する（Ｓ２１０）。図９のＳ２０９とＳ２１０とに示す「＝」は代入演算子である。Ｓ２０９とＳ２１０との処理順序は逆でもよい。カウンタ値ｉが一致長Ｌａ以下である場合（Ｓ２０８：ＮＯ）か、Ｓ２０６およびＳ２０７の処理が行なわれた場合には、参照部１１２は、参照位置Ｐ６のインクリメントを行なう（Ｓ２１１）。参照部１１２は、さらに、参照位置Ｐ６が記憶領域Ａ２の終了位置Ｐ５に達しているか否かを判定する（Ｓ２１２）。参照位置Ｐ６が終了位置Ｐ５に達していない場合（Ｓ２１２：ＮＯ）には、参照部１１２は、再度Ｓ２０２の処理によりカウンタ値ｉをリセットし、Ｓ２１１でインクリメントされた参照位置Ｐ６に基づいてＳ２０３の判定を行なう。Ｓ２１２の判定において、参照位置Ｐ６が終了位置Ｐ５に達したと判定される場合（Ｓ２１２：ＹＥＳ）には、参照部１１２は、一致長Ｌａおよび最長一致位置Ｐａを制御部１１１に返して、記憶領域Ａ２への参照処理を終了する（Ｓ２１３）。

　次に、制御部１１１は、Ｓ１０５の記憶領域Ａ２への参照処理の結果（一致長Ｌａおよび最長一致位置Ｐａ）に基づいて、更新部１１５に圧縮辞書の更新処理を実行させる（Ｓ１０６）。更新部１１５は図１０のフローに従って圧縮辞書の更新処理を行なう。

　図１０は、圧縮辞書の更新処理の手順例を示す。制御部１１１により更新処理が指示される（Ｓ３００）と、更新部１１５は、制御部１１１により指定される一致長Ｌａおよび最長一致位置Ｐａに基づいて記憶領域Ａ２からデータを読み出す（Ｓ３０１）。すなわち、更新部１１５は、記憶領域Ａ２における最長一致位置Ｐａから一致長Ｌａの長さのデータを読み出す。Ｓ３０１で読みだしたデータは、圧縮辞書に登録させる対象のデータ（登録対象データ）である。

　更新部１１５は、参照部１１４に、登録対象データに基づいて圧縮辞書内を参照させる（Ｓ３０２）。更新部１１５は、Ｓ３０２の参照処理に基づいて、圧縮辞書内に登録対象データと重複するデータが含まれているか否かを判定する（Ｓ３０３）。圧縮辞書内に登録対象データと重複するデータが存在する場合（Ｓ３０３：Ｙｅｓ）には、更新部１１５は、登録対象データが圧縮辞書内の重複データよりも一致長が長いか否かを判定する（Ｓ３０４）。例えば、重複データを部分的に含むデータが圧縮辞書内に登録されている場合には、登録対象データよりも長いデータが登録されていることとなり、Ｓ３０４の判定でＮＯと判定される。

　Ｓ３０３で重複するデータが含まれない場合（Ｓ３０３：ＮＯ）か、Ｓ３０４で登録対象データが重複データよりも一致長が長い場合（Ｓ３０４：ＹＥＳ）には、更新部１１５は、一致長Ｌａが設定値Ｌｍｉｎよりも大きいか否かを判定する（Ｓ３０５）。Ｓ３０５で一致長が設定値Ｌｍｉｎよりも大きいと判定された場合（Ｓ３０５：ＹＥＳ）には、更新部１１５は、登録対象データを圧縮辞書に登録する処理を行ない（Ｓ３０６）、処理を終了する（Ｓ３０７）。Ｓ３０６の圧縮辞書への登録処理は、圧縮辞書の形式によって手順が異なるので、圧縮辞書の形式に応じて後述する。

　Ｓ３０４で、登録対象データが重複データよりも一致長が長い場合（Ｓ３０４：ＹＥＳ）か、一致長Ｌａが設定値Ｌｍｉｎ以下である場合（Ｓ３０４：ＮＯ）には、更新部１１５は、Ｓ３０６を行なわずに処理を終了する（Ｓ３０７）。

　図１０において、Ｓ３０３およびＳ３０４は付加的な構成であり、登録対象データが圧縮辞書に登録済みのデータと完全一致でなければ、更新部１１５は、Ｓ３０５の処理を行なうこととしてもよい。また、Ｓ３０５の処理についても付加的な構成であり、更新部１１５は、Ｓ３０５の判定を行なわずに、Ｓ３０６の処理を行なってもよい。

　更新部１１５が図１０の手順を終えると、制御部１１１は、更新部１１３に記憶領域Ａ２を更新させる（Ｓ１０７）。更新部１１３は、制御部１１１の指示に応じて記憶領域Ａ２の更新処理を行なう。

　図１１は、記憶領域Ａ２の更新処理の手順例を示す。制御部１１１から記憶領域Ａ２の更新処理の指示を受ける（Ｓ４００）と、更新部１１３は、記憶領域Ａ１内の読出し位置Ｐ３から一致長Ｌａのデータを読み出す（Ｓ４０１）。さらに、更新部１１３は、Ｓ４０１で読み出したデータを記憶領域Ａ２の更新位置Ｐ７に書き込む（Ｓ４０２）。Ｓ４０２の書き込みにおいて、記憶領域Ａ２の終了位置Ｐ５を超えてしまうデータについては、記憶領域Ａ２の開始位置Ｐ４から書き込む。

　次に、更新部１１３は、更新位置Ｐ７の更新を行なう（Ｓ４０３）。更新位置Ｐ７の初期値は記憶領域Ａ２のＳ４０２の書き込みにおいて一致長Ｌａのデータの書き込みを行なったので、更新位置Ｐ７は、Ｐ７＋Ｌａに更新される。図１１のＳ４０３における「＝」は、代入演算子である。さらに、更新部１１３は、更新位置Ｐ７が終了位置Ｐ５よりも大きいか否か判定し（Ｓ４０４）、更新位置Ｐ７が終了位置Ｐ５よりも大きい場合（Ｓ４０４：ＹＥＳ）には、更新位置Ｐ７をＰ７＝Ｐ７－Ｐ５＋Ｐ４と修正する（Ｓ４０５）。このＳ４０５における「＝」は、代入演算子である。Ｓ４０５の処理を行なうか、更新位置Ｐ７が終了位置よりも大きくない場合（Ｓ４０４：ＮＯ）には、更新部１１３は処理を終了する（Ｓ４０６）。

　更新部１１３が図１１の手順を終了すると、制御部１１１は、Ｓ１０４における圧縮辞書の参照処理の処理結果に応じて生成された圧縮符号もしく記憶領域Ａ１の読出し位置Ｐ３のデータを、書き込み位置Ｐ１０に書き込む（Ｓ１０８）。Ｐ１０８において、制御部１１１は、さらに、書き込んだデータ（圧縮符号または読出し位置Ｐ３のデータ）の長さに応じて書き込み位置Ｐ１０を更新する。Ｓ１０８が終わると、制御部１１１は読出し位置Ｐ３を更新する（Ｓ１０９）。さらに、制御部１１１は読出し位置Ｐ３がファイルＦ１の終点（終了位置Ｐ２）であるか否かを判断する（Ｓ１１０）。読出し位置Ｐ３が、まだ終了位置Ｐ２に到達していない場合（Ｓ１１０：ＮＯ）には、制御部１１１は、再度Ｓ１０４の処理を行なう。また、読出し位置Ｐ３が終了位置Ｐ２に到達した場合（Ｓ１１０：ＹＥＳ）には、制御部１１１は、記憶領域Ａ４に書き込まれたデータおよび圧縮辞書を含む圧縮ファイルを生成し、ファイルクローズ処理を行なう（Ｓ１１１）。Ｓ１１１で圧縮ファイルを生成すると、制御部１１１は、圧縮機能の呼び出し元に圧縮処理の完了通知を行ない、処理を終了する。

　次に、図７に示すＳ１０４の参照処理について説明する。図１２は、圧縮辞書の参照処理の手順例を示す。参照部１１４は、制御部１１１に参照処理を指示される（Ｓ５００）と、読出し位置Ｐ３を始点とするデータ（処理対象のデータ）に基づき圧縮辞書内を探索する（Ｓ５０１）。Ｓ５０１については、圧縮辞書の形式と併せて後述する。次に、参照部１１４は、Ｓ５０１の圧縮辞書内の探索の結果に基づいて、処理対象のデータと合致するデータ（合致データ）が圧縮辞書に存在するか否かを判断する（Ｓ５０２）。圧縮辞書内に合致データが存在する場合（Ｓ５０２：ＹＥＳ）には、参照部１１４は、合致データに対応する圧縮符号を生成する（Ｓ５０３）。

　圧縮辞書内に合致データが存在しない場合（Ｓ５０２：ＮＯ）には、参照部１１４は、記憶領域Ａ１の読出し位置Ｐ３から、データを読み出す（Ｓ５０４）。Ｓ５０４で読み出すデータは、例えば文字などの単位の情報である。この単位は、図９において用いられたカウンタ値ｉや参照位置Ｐ６などに用いられる単位であり、Ｓ２０４やＳ２１１のインクリメントによる増分と同じデータ量である。

　さらに、参照部１１４は、Ｓ５０３やＳ５０４の処理において、識別子を付与する。識別子は、圧縮符号であるか否かを示し、さらには圧縮符号の種類などを示す。識別子の詳細については、圧縮辞書の具体例をとともに後述する。

　Ｓ５０３またはＳ５０４の処理を終えると、参照部１１４は、Ｓ５０３で生成された圧縮符号、または、Ｓ５０４で読み出されたデータを制御部１１１に返し、処理を終了する（Ｓ５０５）。

　続いて、圧縮辞書の例ごとに圧縮処理の説明を行なう。

　図１３は、圧縮辞書テーブルＴ２を示す。圧縮辞書テーブルＴ２は、圧縮辞書の例である。圧縮辞書テーブルＴ２は、データ（文字情報）のカラムを含む。また、データ（文字情報）に固定長のデータ領域（例えばｍビット）が確保され、圧縮辞書テーブルＴ２の何番目のデータであるかを示す番号を圧縮符号に用いられる。例えば、「ｈｏｒｓｅ」はｍ×１の位置に存在するので、「０００００００１」などの固定長の符号（登録番号）を圧縮符号とする。変形例として、圧縮符号のカラムを設け、登録番号を圧縮符号のカラムに格納することとしてもよい。また、他の変形例として、所定のアルゴリズムにより生成された可変長の圧縮符号が圧縮符号のカラムに格納されることとしてもよい。

　図１０に示すＳ３０６の処理により、データと圧縮符号のセットを含むレコードが登録される。登録されるデータは、図７のＳ１０５の参照処理により定められる最長一致のデータである。図１３には単語、熟語およびタグなどが例示されているが、単語の一部分である文字情報なども圧縮辞書テーブルＴ２に登録される。また、圧縮辞書テーブルＴ２に登録されるデータとして文字情報が例示されるが、文字情報に限定されるものではない。

　図１３に示す圧縮辞書テーブルＴ２は、図１０に示すＳ３０２の処理やＳ３０６の処理、さらには、図１２に示すＳ５０１の処理によりアクセスされる。圧縮辞書テーブルＴ２へのアクセスには、記憶部１３における位置情報が用いられる。圧縮辞書テーブルＴ２の位置情報は、開始位置Ｐ１１、終了位置Ｐ１２、参照位置Ｐ１３および更新位置Ｐ１４である。

　図１４は、圧縮辞書テーブルＴ２の参照処理の手順例を示す。圧縮辞書テーブルＴ２の参照処理は、例えば、図１０に示すＳ３０２の処理や、図１２に示すＳ５０１の処理で行なわれる。参照部１１４は、参照処理を指示される（Ｓ６００）と、まず参照位置Ｐ１３を開始位置Ｐ１１にセットする（Ｓ６０１）。次に、参照部１１４は、対象のデータと、参照位置Ｐ１３に示されるレコード内のデータとを照合する（Ｓ６０２）。対象のデータとは、図１０に示すＳ３０２の処理では登録対象データであり、図１２に示すＳ５０１の処理では、読出し位置Ｐ３から読み出されるデータ列である。参照部１１４は、Ｓ６０２の照合の結果、合致したか否かを判断する（Ｓ６０３）。

　Ｓ６０２の照合の結果、合致しない場合（Ｓ６０３：ＮＯ）は、参照部１１４は、参照位置Ｐ１３を更新する（Ｓ６０４）。例えば、更新後の参照位置Ｐ１３は、更新前の参照位置Ｐ１３が示すレコードの次のレコードを示す。さらに、参照部１１４は、参照位置Ｐ１３が終了位置Ｐ１２に到達したか否かを判断する（Ｓ６０５）。参照位置Ｐ１３が終了位置Ｐ１２に到達していない場合（Ｓ６０５：ＮＯ）には、参照部１１４は、Ｓ６０２の照合処理を再度行なう。参照位置Ｐ１３が終了位置Ｐ１２に到達した場合（Ｓ６０５：ＹＥＳ）には、参照部１１４は、対象のデータと合致するデータが圧縮辞書テーブルＴ２に存在しない旨を制御部１１１に返す（Ｓ６０６）。

　Ｓ６０２の照合の結果、合致する場合（Ｓ６０３：ＹＥＳ）には、参照部１１４は、参照位置Ｐ１３を制御部１１１に返す（Ｓ６０７）。参照部１１４は、Ｓ６０７またはＳ６０６の処理を行なうと、参照処理を終了する（Ｓ６０８）。

　参照部１１４は、図１４の参照処理の結果に応じた識別子を生成する。Ｓ６０６の処理で合致しない旨を返した場合には、参照部１１４は、例えば識別子「０」を図１２に示すＳ５０４の処理における単位データに付与する。また、Ｓ６０７で参照位置Ｐ１３を返した場合には、参照部１１４は、例えば識別子「１」を図１２に示すＳ５０３の処理における圧縮符号に付与する。伸張する際には、識別子に基づいて圧縮辞書テーブルＴ２の参照を行なうか否かが判断される。

　図１５は、圧縮辞書テーブルＴ２の更新処理の手順例を示す。圧縮辞書テーブルＴ２の更新処理は、例えば、図１０に示すＳ３０６の処理で行なわれる。更新処理を指示される（Ｓ７００）と、更新部１１５は、登録対象データを更新位置Ｐ１４のレコードに書き込む（Ｓ７０１）。登録対象データは、図１０のＳ３０１で読み出されるデータである。

　Ｓ７０１でデータが更新位置Ｐ１４のレコードに登録されると、更新部１１５は、圧縮符号を生成する（Ｓ７０２）。先に説明したように、各データに対応する圧縮符号は、例えば、各データが何番目の位置に登録されたかを示す登録番号である。更新部１１５は、さらに、Ｓ７０２で生成された圧縮符号を更新位置Ｐ１４のレコードに書き込む（Ｓ７０３）。Ｓ７０３の処理は、圧縮辞書テーブルＴ２に圧縮符号のカラムが設けられる場合に行なわれる処理であり、レコードの位置を圧縮符号として用いる場合には行なわれない。さらに、更新部１１５は、更新位置Ｐ１４を更新して（Ｓ７０４）、更新処理を終了する（Ｓ７０５）。更新位置Ｐ１４の更新は、参照位置の更新と同様に行なわれる。すなわち、更新後の更新位置Ｐ１４が示すレコードは、更新前の更新位置Ｐ１４が示すレコードの次のレコードである。

　上述の例の圧縮辞書（圧縮辞書テーブルＴ２）では、圧縮辞書がテーブル構造であるため、伸張時には、圧縮符号に基づきテーブル内の探索が行なわれる。圧縮辞書テーブルＴ２内の位置を示す情報を圧縮符号とすると、圧縮辞書テーブルＴ２から必要な情報のみを読み出すことができるので、圧縮辞書テーブルＴ２の探索が高速化される。

　図１６は、圧縮辞書Ｄ１を用いた処理の概要を示す。図１に例示した圧縮辞書Ｄ１について説明する。

　図１０に示すＳ３０６の処理において、登録対象データは、記憶領域Ａ３に順次記憶される。例えば、記憶領域Ａ２の参照により、順に登録対象データ「ａｂｏｕｔ」、「ｈｏｒｓｅ」、「ｒａｃｅ」が得られたとすると、格納位置「０」～「４」に「ａｂｏｕｔ」が格納され、さらに、格納位置「４」の次の「５」から「ｈｏｒｓｅ」が格納される。

　図１に示す照合１の処理（例えば、図１２の５０１の処理）を行なう場合には、参照部１１４は、記憶領域Ａ１の読出し位置Ｐ３からのデータと記憶領域Ａ３内に登録された各データとの照合を行なう。照合部１１４は、照合１により記憶領域Ａ３内で最長一致であるデータを抽出し、そのデータの記憶領域Ａ３内での格納位置（最長一致位置Ｐｂ）と一致長Ｌｂとを圧縮符号として用いる。図１６の例においては、記憶領域Ａ１の読出し位置Ｐ３からのデータ列が「ｈｏｒｓｅ・・・」となっている。その場合に、記憶領域Ａ３の格納位置「５」～「９」が最長一致であれば、例えば、圧縮符号は、最長一致位置Ｐｂ「０００００００００１０１（２進数表現）」と一致長Ｌｂ「０１０１（２進数表現）」で示される。さらに、圧縮符号であることを示す識別子「１」が付与される。圧縮符号でなく、読出し位置Ｐ３のデータをそのまま用いる場合には、識別子「０」が付与される。図１６に示す例においては、圧縮符号は１７ビットである。文字情報「ｈｏｒｓｅ」に使用される文字コード系が８ビットのものであったとすると４０ビット必要となるので、この例においては、データ量が半分以下に低減されたこととなる。

　例えば、記憶領域Ａ３内のアドレスのデータ長は、予め定められる。また、記憶領域Ａ３もアドレスのデータ長に対応したデータサイズとなる。上述の例では、アドレスが１２ビットで表現され、１バイトで表現される文字コードが用いられているので、記憶領域Ａ３のデータサイズは４ＫＢ程度である。

　図１７は、圧縮辞書Ｄ１の参照処理の手順例を示す。図１２に示すＳ５０１の処理が開始される（Ｓ８００）と、参照部１１４は、参照位置Ｐ１３、一致長Ｌｂ、最長一致位置Ｐｂの初期値をセットする（Ｓ８０１）。例えば、参照位置Ｐ１３の初期値は、記憶領域Ａ３の開始位置Ｐ１１にセットされる。例えば、一致長Ｌｂの初期値は、０にセットされる。また、例えば、最長一致位置Ｐｂの初期値は、Ｐ１１よりも１少ない位置（Ｐ１１－１）にセットされる。さらに、参照部１１４は、カウンタ値ｊをセット（ｊ＝０）する（Ｓ８０２）。

　参照部１１４は、記憶領域Ａ１の読出し位置Ｐ３からカウンタ値ｊずれた位置（Ｐ３＋ｊ）のデータと、記憶領域Ａ３の参照位置Ｐ１３からカウンタ値ｊずれた位置（Ｐ６＋ｊ）のデータとが一致するか否かの判定（Ｓ８０３）を行なう。

　参照部１１４がＳ８０３の判定においてデータ同士が一致すると判定した場合（Ｓ８０３：ＹＥＳ）には、参照部１１４はカウンタ値ｊをインクリメントする（Ｓ８０４）。参照部１１４は、続いて、Ｓ８０４でインクリメントされたカウンタ値ｊが設定値Ｌｍａｘ以上であるか否か判定する（Ｓ８０５）。カウンタ値ｊが設定値Ｌｍａｘよりも小さい場合（Ｓ８０５：ＮＯ）には、Ｓ８０３の判定が再度行なわれる。上記のＳ８０３～Ｓ８０５の処理により、読み出し位置Ｐ３からのデータ列Ｒ１と参照位置Ｐ１３からのデータ列とについて、１つずつ合致しているか否かの判定が繰り返し行なわれる。カウンタ値ｊはデータ列Ｒ１との一致が確認されたデータの長さを示す。設定値Ｌｍａｘは予め設定された値であり、最長一致の上限値を示す。

　Ｓ８０５の判定でカウンタ値ｊが設定値Ｌｍａｘ以上である場合（Ｓ８０５：ＹＥＳ）には、参照部１１２は、一致長Ｌｂをカウンタ値ｊに更新し（Ｓ８０６）、最長一致位置Ｐｂを参照位置Ｐ１３に更新する（Ｓ８０７）。図１７のＳ８０６とＳ８０７とに示す「＝」は代入演算子である。また、Ｓ８０６とＳ８０７との処理順序は逆でもよい。Ｓ８０６およびＳ８０７で値を更新すると、参照部１１４は、値が代入された一致長Ｌｂおよび最長一致位置Ｐｂを制御部１１１に返す（Ｓ８１３）。

　Ｓ８０３の判定でデータ同士が一致しないと判定された場合（Ｓ８０３：ＮＯ）には、参照部１１４は、カウンタ値ｊが一致長Ｌｂよりも大きいか否か判定する（Ｓ８０８）。カウンタ値ｊが一致長Ｌｂよりも大きい場合には（Ｓ８０８：ＹＥＳ）、参照部１１４は、一致長Ｌｂをカウンタ値ｊに更新し（Ｓ８０９）、最長一致位置Ｐｂを参照位置Ｐ１３に更新する（Ｓ８１０）。図１７のＳ８０９とＳ８１０とに示す「＝」は代入演算子である。また、Ｓ８０９とＳ８１０との処理順序は逆でもよい。

　カウンタ値ｊが一致長Ｌｂ以下である場合（Ｓ８０８：ＮＯ）か、Ｓ８０６およびＳ８０７の処理が行なわれた場合には、参照部１１４は、参照位置Ｐ１３を更新する（Ｓ８１１）。Ｓ８１１において、更新後の参照位置Ｐ１３は、更新前の参照位置が示すデータの次のデータを示す。参照部１１４は、さらに、参照位置Ｐ１３が記憶領域Ａ３の終了位置Ｐ２に達しているか否かを判定する（Ｓ８１２）。図１７のＳ８１２における「＝」は等号を示す。参照位置Ｐ１３が終了位置Ｐ１２に達していない場合（Ｓ８１２：ＮＯ）には、参照部１１４は、再度Ｓ８０２の処理によりカウンタ値ｊをリセットし、Ｓ８１１でインクリメントされた参照位置Ｐ１３に基づいてＳ８０３の判定を行なう。Ｓ８１２の判定において、参照位置Ｐ１３が終了位置Ｐ１２に達したと判定される場合（Ｓ８１２：ＹＥＳ）には、参照部１１４は、一致長Ｌｂおよび最長一致位置Ｐｂを制御部１１１に返して、圧縮辞書Ｄ１への参照処理を終了する（Ｓ８１２）。

　図１２のＳ５０２に示す通り、参照部１１４は、図１７に示す参照処理の結果に応じて圧縮辞書Ｄ１内に合致するデータが存在したか否かを判断する。この判断は、最長一致位置Ｐｂおよび一致長Ｌｂに応じて判断される。例えば、一致長Ｌｂが所定値（例えば、２バイトや３バイト）よりも小さい場合には、圧縮辞書Ｄ１内に合致するデータが存在しなかったものとしてもよい。また、所定値を１に設定した場合にも、参照位置Ｐ１３が初期値のまま（例えば、開始位置Ｐ１１－１などが初期値に用いられる）である場合は、圧縮辞書Ｄ１内に合致するデータが存在しなかったものとしてもよい。

　また、圧縮辞書Ｄ１は、図１０に示すＳ３０２の処理においても、登録対象データを重複するデータが存在するか否かを判断するために参照される。この参照処理は、図１２に示すＳ５０１の処理と異なり参照すべきデータの長さが定まっている。そのため、更新部１１５は、図１７の手順例ではなく、図１４の手順例に従って圧縮辞書Ｄ１の参照処理を行なう。以下に図１４に沿って、更新部１１５による圧縮辞書Ｄ１の参照処理を説明する。

　更新部１５は、登録対象データに基づく圧縮辞書Ｄ１の参照処理を指示される（Ｓ６００）と、圧縮辞書Ｄ１内の参照位置Ｐ１３をセットする（Ｓ６０１）。Ｓ６０１において、更新部１１５は、参照位置Ｐ１３を例えば圧縮辞書Ｄ１（記憶領域Ａ３）の開始位置Ｐ１１にセットする。

　次に、更新部１１５は、記憶領域Ａ３の参照位置Ｐ１３に存在するデータと登録対象データとを照合する（Ｓ６０２）。更新部１１５は、さらに、Ｓ６０２の照合で登録対象データと合致したか否かを判断する（Ｓ６０３）。Ｓ６０３で合致しないと判断した場合（Ｓ６０３：ＮＯ）には、更新部１１５は、参照位置Ｐ１３の更新を行なう（Ｓ６０４）。更新後の参照位置Ｐ１３は、更新前の参照位置Ｐ１３が示すデータの次のデータを示す。さらに、更新部１１５は、参照位置Ｐ１３が記憶領域Ａ３の終了位置Ｐ１２に到達したか否かを判断する（Ｓ６０５）。Ｓ６０５の判断の結果、参照位置Ｐ１３が終了位置Ｐ１２に到達していない場合（Ｓ６０５：ＮＯ）には、更新部１１５は、再度Ｓ６０２の処理を行なう。一方、Ｓ６０５で参照位置Ｐ１３が終了位置Ｐ１２に到達した場合（Ｓ６０５：ＹＥＳ）には、更新部１１５は、登録対象データと合致するデータが圧縮辞書Ｄ１に存在しない旨を制御部１１１に返す（Ｓ６０６）。

　一方、Ｓ６０３で合致したと判断した場合（Ｓ６０３：ＹＥＳ）には、更新部１１５は、参照位置Ｐ１３を制御部１１１に返す（Ｓ６０７）。Ｓ６０６またはＳ６０７を行なうと、更新部１１５は処理を終了する（Ｓ６０８）。

　図１８は、圧縮辞書Ｄ１への登録対象データの登録処理の手順例を示す。図１０に示すＳ３０６の処理で登録処理が開始される（Ｓ９００）と、更新部１１５は、圧縮辞書Ｄ１（記憶領域Ａ３）の更新位置Ｐ１４から登録対象データを書き込む（Ｓ９０１）。次に、更新部１１５は、更新位置Ｐ１４を更新する（Ｓ９０２）。更新位置Ｐ１４は、登録対象データの長さ（一致長Ｌａ）だけ移動する。更新１１５は、Ｓ９０２を終えると登録処理を終了する（Ｓ９０３）。例えば、更新位置Ｐ１４の初期値はＰ１１であり、図１８の登録処理が行なわれるたびに更新位置Ｐ１４は更新される。

　上述の圧縮辞書Ｄ１を用いた場合には、圧縮辞書Ｄ１内に圧縮符号そのものは含まれない。そのため、圧縮辞書Ｄ１自体のデータサイズが抑制される。

　参照テーブルＴ３を用いた処理の概要は、前述の通り、図２に示される。図２に示す記憶領域Ａ３および参照テーブルＴ３が圧縮辞書Ｄ２として用いられる。

　参照テーブルＴ３は複数のレコードを含み、それぞれのレコードは記憶領域Ａ３内の格納位置とデータ長との組を含む。例えば、参照テーブルＴ３のそれぞれのレコードは、記憶領域Ａ３内に登録される登録対象データそれぞれの格納位置とデータ長との組を含む。また、例えば、参照テーブルＴ３の記憶部１３内での位置（開始位置Ｐ１５、終了位置Ｐ１６、参照位置Ｐ１７および書込み位置Ｐ１８）などを示す情報が、図８に示す位置情報テーブルＴ１と同様のテーブルにより記憶部１３内で管理される。

　図１６に示す圧縮辞書Ｄ１においては、最長一致位置Ｐｂおよび一致長Ｌｂが得られた場合に、最長一致位置Ｐｂと一致長Ｌｂとにより圧縮符号が生成された。圧縮辞書Ｄ２では、図１７に示す参照処理により得られる最長一致位置Ｐｂと一致長Ｌｂとに基づいて参照テーブルＴ３が探索され、対応する格納位置およびデータ長を含むレコードを示す登録番号（ポインタ）を圧縮符号に用いる。この場合、図２に示すように、記憶領域Ａ３の参照により得られた圧縮符号であることを示す識別子「１」が用いられる。

　また、図１７に示す参照処理により最長一致位置Ｐｂおよび一致長Ｌｂが得られたにも関わらず、対応する格納位置およびデータ長のレコードが存在しないこともあり得る。その場合には、処理対象のデータに対して例えばハフマン符号化が行なわれ、生成されたハフマン符号に識別子「０」が付与される。

　上述の通り、図２に示す圧縮辞書Ｄ２を用いる場合にも、図１７に示す参照処理が行なわれる。図１７に示す参照処理により得られる最長一致位置Ｐｂおよび一致長Ｌｂに基づいて、参照部１１４は、参照テーブルＴ３の参照処理を行なう。これにより、参照部１１４は、参照テーブルＴ３内のポインタを取得する。

　図１９は、参照テーブルＴ３の参照処理の手順例を示す。図１７の参照処理でＳ８１３の処理が実行される（Ｓ１０００）と、参照部１１４は、参照位置Ｐ１７の初期値をセットする（Ｓ１００１）。参照位置Ｐ１７の初期値は、例えば参照テーブルＴ３の開始位置Ｐ１５である。次に、参照部１１４は、最長一致位置Ｐｂおよび一致長Ｌｂと、参照テーブルＴ３内の参照位置Ｐ１７のレコードとの照合処理を行なう（Ｓ１００２）。

　参照部１１４は、Ｓ１００２の照合処理の結果、参照位置Ｐ１７のレコードに記憶される格納位置と最長一致位置Ｐｂとが合致したか否かを判断する（Ｓ１００３）。さらに、参照位置Ｐ１７のレコードに記憶される格納位置と最長一致位置Ｐｂとが合致した場合（Ｓ１００３：ＹＥＳ）には、参照部１１４は、さらに、参照位置Ｐ１７のレコードに記憶されるデータ長と一致長Ｌｂが合致したか否か判断する（Ｓ１００４）。参照位置Ｐ１７のレコードに記憶されるデータ長と一致長Ｌｂが合致した場合（Ｓ１００４：ＹＥＳ）に、参照部１１４は、参照位置Ｐ１７を制御部１１１に返す（Ｓ１００５）。この場合の圧縮符号は、参照位置Ｐ１７（図２に示す登録番号）に基づいて生成される。

　参照位置Ｐ１７のレコードに記憶される格納位置およびデータ長のいずれかが合致しない場合（Ｓ１００３，Ｓ１００４：ＮＯ）には、更新部１１４は、参照位置Ｐ１７を更新する（Ｓ１００６）。更新部１１４は、参照位置Ｐ１７を示す値をインクリメントし、次のレコードを示す値にする。さらに、参照部１１４は、参照位置Ｐ１７が参照テーブルＴ３の終了位置Ｐ１６に到達したか否かを判断する（Ｓ１００７）。Ｓ１００７における「＝」は等号である。

　参照位置Ｐ１７が終了位置Ｐ１６に到達しない場合（Ｓ１００７：ＮＯ）には、参照部１１４は、Ｓ１００２の処理を行なう。一方、参照位置Ｐ１７が終了位置Ｐ１６に到達した場合（Ｓ１００７：ＹＥＳ）には、参照部１１４は、合致するレコードが存在しない旨を制御部１１１に返す（Ｓ１００８）。

　参照部１１４は、Ｓ１００５もしくはＳ１００８を実行すると、参照テーブルＴ３の参照処理を終了し、図１２に示すフローに戻る。

　図２０は、登録対象データの登録処理の手順例を示す。圧縮辞書Ｄ１を用いる場合と圧縮辞書Ｄ２を用いる場合とで、登録処理は一部同じ手順含む。図１０に示すＳ３０６の処理で登録処理が開始される（Ｓ１１００）と、更新部１１５は、記憶領域Ａ３の更新位置Ｐ１４から登録対象データを書き込む（Ｓ１１０１）。次に、更新部１１５は、参照テーブルＴ３の書込み位置Ｐ１８のレコードに、更新位置Ｐ１４および一致長Ｌａを書き込む（Ｓ１１０２）。更新部１１５は、書込み位置Ｐ１８のレコードの格納位置に更新位置Ｐ１４を書き込み、データ長に一致長Ｌａを書き込む。次に、更新部１１５は、書込み位置Ｐ１８を更新する（Ｓ１１０３）。更新後の書込み位置Ｐ１８は、更新前の書込み位置Ｐ１８が示すレコードの次のレコードを示す。書込み位置Ｐ１８の初期値は、例えば、開始位置Ｐ１５であり、図２０の登録処理が行なわれるたびに書込み位置Ｐ１８は更新される。

　次に、更新部１１５は、更新位置Ｐ１４を更新する（Ｓ１１０４）。更新位置Ｐ１４は、登録対象データの長さ（一致長Ｌａ）だけ移動する。更新部１１５は、Ｓ１１０４を終えると登録処理を終了する（Ｓ１１０５）。例えば、更新位置Ｐ１４の初期値はＰ１１であり、図２０の登録処理が行なわれるたびに更新位置Ｐ１４は更新される。

　上述の圧縮辞書Ｄ２を用いた場合には、圧縮符号が登録番号に集約されるため、最長一致位置Ｐｂおよび一致長Ｌｂによる圧縮符号を用いるよりも圧縮率の向上が見込まれる。一方で、圧縮符号により最長一致位置Ｐｂおよび一致長Ｌｂの位置が示され、最長一致位置Ｐｂおよび一致長Ｌｂにより伸張用データの位置が示されるので、圧縮辞書Ｄ１内のデータとの照合による探索を含まない。そのため、伸張速度は劣化しにくい。

　下記に、本実施形態に用いられるハードウェア及びソフトウェアについて説明する。

　図２２は、コンピュータ１のハードウェア構成例を示す。コンピュータ１は、例えば、プロセッサ３０１、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）３０２、ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）３０３、ドライブ装置３０４、記憶媒体３０５、入力インターフェース（Ｉ／Ｆ）３０６、入力デバイス３０７、出力インターフェース（Ｉ／Ｆ）３０８、出力デバイス３０９、通信インターフェース（Ｉ／Ｆ）３１０、ＳＡＮ（Ｓｔｏｒａｇｅ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）インターフェース（Ｉ／Ｆ）３１１およびバス３１２などを含む。それぞれのハードウェアはバス３１２を介して接続されている。

　ＲＡＭ３０２は読み書き可能なメモリ装置であって、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ　ＲＡＭ）やＤＲＡＭ（Ｄｙｎａｍｉｃ　ＲＡＭ）などの半導体メモリ、またはＲＡＭでなくてもフラッシュメモリなどが用いられる。ＲＯＭ３０３は、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ　ＲＯＭ）なども含む。ドライブ装置３０４は、記憶媒体３０５に記録された情報の読み出しか書き込みかの少なくともいずれか一方を行なう装置である。記憶媒体３０５は、ドライブ装置３０４によって書き込まれた情報を記憶する。記憶媒体３０５は、例えば、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ　Ｓｔａｔｅ　Ｄｒｉｖｅ）などのフラッシュメモリ、ＣＤ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｃ）、ブルーレイディスクなどの記憶媒体である。また、例えば、コンピュータ１は、複数種類の記憶媒体それぞれについて、ドライブ装置３０４及び記憶媒体３０５を設ける。

　入力インターフェース３０６は、入力デバイス３０７と接続されており、入力デバイス３０７から受信した入力信号をプロセッサ３０１に伝達する回路である。出力インターフェース３０８は、出力デバイス３０９と接続されており、出力デバイス３０９に、プロセッサ３０１の指示に応じた出力を実行させる回路である。通信インターフェース３１０はネットワーク３を介した通信の制御を行なう回路である。通信インターフェース３１０は、例えばネットワークインターフェースカード（ＮＩＣ）などである。ＳＡＮインターフェース３１１は、ストレージエリアネットワークによりコンピュータ１と接続された記憶装置との通信の制御を行なう回路である。ＳＡＮインターフェース３１１は、例えばホストバスアダプタ（ＨＢＡ）などである。

　入力デバイス３０７は、操作に応じて入力信号を送信する装置である。入力信号は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力デバイス３０９は、コンピュータ１の制御に応じて情報を出力する装置である。出力デバイス３０９は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力デバイス３０７及び出力デバイス３０９として用いられる。また、入力デバイス３０７及び出力デバイス３０９は、コンピュータ１と一体になっていてもよいし、コンピュータ１に含まれず、例えば、コンピュータ１に外部から接続する装置であってもよい。

　例えば、プロセッサ３０１は、ＲＯＭ３０３や記憶媒体３０５に記憶されたプログラムをＲＡＭ３０２に読み出し、読み出されたプログラムの手順に従って圧縮部１１の処理または伸張部１２の処理を行なう。その際にＲＡＭ３０２はプロセッサ３０１のワークエリアとして用いられる。記憶部１３の機能は、ＲＯＭ３０３および記憶媒体３０５がプログラムファイル（後述のアプリケーションプログラム２４、ミドルウェア２３およびＯＳ２２など）やデータファイル（圧縮対象のファイルＦ１、圧縮されたファイルＦ２など）を記憶し、ＲＡＭ３０２がプロセッサ３０１のワークエリアとして用いられることによって実現される。プロセッサ３０１が読み出すプログラムについては、図２２を用いて説明する。

　図２２は、コンピュータ１で動作するプログラムの構成例を示す。コンピュータ１において、図２２に示すハードウェア群２１（３０１～３１２）の制御を行なうＯＳ（オペレーティング・システム）２２が動作する。ＯＳ２２に従った手順でプロセッサ３０１が動作して、ハードウェア群２１の制御・管理が行なわれることにより、アプリケーションプログラム２４やミドルウェア２３に従った処理がハードウェア群２１で実行される。さらに、コンピュータ１において、ミドルウェア２３またはアプリケーションプログラム２４が、ＲＡＭ３０２に読み出されてプロセッサ３０１により実行される。

　プロセッサ３０１が、圧縮機能が呼び出された場合に、ミドルウェア２３またはアプリケーションプログラム２４の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア群２１を制御して）圧縮部１１の機能が実現される。また、プロセッサ３０１が、伸張機能が呼び出された場合に、ミドルウェア２３またはアプリケーションプログラム２４の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア群２１を制御して）伸張部１２の機能が実現される。圧縮機能および伸張機能は、それぞれアプリケーションプログラム２４自体に含まれてもよいし、アプリケーションプログラム２４に従って呼び出されることで実行されるミドルウェア２３の一部であってもよい。

　アプリケーションプログラム２４（またはミドルウェア２３）の圧縮機能により得られる圧縮ファイルＦ２は、圧縮ファイルＦ２内の圧縮辞書Ｄ１に基づいて部分的に伸張可能である。圧縮ファイルＦ２の途中を伸張する場合には、伸張対象の部分までの圧縮データの伸張処理が抑制されるため、プロセッサ３０１の負荷が抑制される。また、伸張対象の圧縮データを部分的にＲＡＭ３０２上に展開するので、ワークエリアも削減される。

　図２３は、実施形態のシステムにおける装置の構成例を示す。図２３のシステムは、コンピュータ１ａ、コンピュータ１ｂ、基地局２およびネットワーク３を含む。コンピュータ１ａは、無線または有線の少なくとも一方により、コンピュータ１ｂと接続されたネットワーク３に接続している。

　図６に示す圧縮部１１と伸張部１２とは、図２３に示すコンピュータ１ａとコンピュータ１ｂとのいずれに含まれてもよい。コンピュータ１ｂが圧縮部１１を含み、コンピュータ１ａが伸張部１２を含んでもよいし、コンピュータ１ｂが圧縮部１１を含み、コンピュータ１ａが伸張部１２を含んでもよい。また、コンピュータ１ａとコンピュータ１ｂとの双方が、圧縮部１１および伸張部１２を備えてもよい。

　以下、上述の実施形態における変形例の一部を説明する。下記の変形例のみでなく、本発明の本旨を逸脱しない範囲の設計変更は適宜行われうる。

　圧縮処理の対象は、ファイル内のデータ以外にも、システムから出力される監視メッセージなどでもよい。例えば、バッファに順次格納される監視メッセージを上述の圧縮処理により圧縮し、ログファイルとして格納するなどの処理が行なわれる。また、例えば、データベース内のページ単位に圧縮が行なわれてもよいし、複数のページをまとめた単位で圧縮が行なわれてもよい。

　また、上述の圧縮処理の対象となるデータは、上述の通り、文字情報に限定されるものでない。数値のみの情報であってもよいし、画像・音声などのデータに対して上述の圧縮処理を用いてもよい。例えば、音声合成により得られるデータを多量に含むファイルなどは、データ内に繰り返しを多く含むため動的辞書により圧縮率が向上することが見込まれる。当然その一部のみが利用される場合には、部分伸張により余分な伸張処理が抑制される。また、固定カメラにより撮影された動画像についても各フレームの画像が似たものになることから繰り返しが多く含まれる。そのため、上述の圧縮処理を適用することにより、文書データや音声データと同様の効果を得ることができる。

　１　　　　コンピュータ
　１ａ　　　コンピュータ
　１ｂ　　　コンピュータ
　２　　　　基地局
　１１　　　圧縮部
　１２　　　伸張部
　１３　　　記憶部
　１１１　　制御部
　１１２　　参照部
　１１３　　更新部
　１１４　　参照部
　１１５　　更新部

Claims (14)

1. 　コンピュータに、
   　ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書の生成を行ない、
   　前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう、
   　処理を実行させることを特徴とする圧縮プログラム。
2. 　前記コンピュータに、さらに、
   　前記圧縮処理により得られる圧縮データと、前記圧縮辞書とを含む圧縮ファイルを生成する、
   処理を実行させることを特徴とする請求項１に記載の圧縮プログラム。
3. 　前記圧縮データは、前記圧縮辞書を用いた伸張処理により伸張される、
   　ことを特徴とする請求項２に記載の圧縮プログラム。
4. 　前記圧縮辞書は、データと圧縮符号との組み合わせを複数含み、
   　前記圧縮辞書に、前記ファイルから読み出されるデータに基づいた組み合わせが順次追加され、
   　前記ファイルの圧縮処理は、順次組み合わせが追加される圧縮辞書に基づいて行われる、
   　ことを特徴とする請求項１～３のいずれか１項に記載の圧縮プログラム。
5. 　前記ファイル内に複数回出現するデータは、前記ファイル内のデータ同士の照合により抽出される、
   　ことを特徴とする請求項１～４のいずれか１項に記載の圧縮プログラム。
6. 　前記ファイル内に複数回出現するデータは、前記ファイル内のデータを変換アルゴリズムにより変換して得られた変換データ同士の照合により抽出される、
   　ことを特徴とする請求項１～４のいずれか１項に記載の圧縮プログラム。
7. 　前記複数回出現するデータは、２以上の文字情報を含むデータ列である、
   　ことを特徴とする請求項１～６のいずれか１項に記載の圧縮プログラム。
8. 　前記圧縮辞書は、前記複数回出現するデータを含み、
   　前記圧縮符号は、前記圧縮辞書における前記複数回出現するデータの格納位置およびデータ長を含む、
   　ことを特徴とする請求項１～７のいずれか１項に記載の圧縮プログラム。
9. 　前記圧縮辞書は、前記複数回出現するデータと前記圧縮符号とを関連付けた情報を含む、
   　ことを特徴とする請求項１～７のいずれか１項に記載の圧縮プログラム。
10. 　前記圧縮辞書は、前記複数回出現するデータを含み、
    　前記圧縮符号は、前記圧縮辞書における前記複数回出現するデータの格納位置およびデータ長を格納する位置を示す、
    　ことを特徴とする請求項１～７のいずれか１項に記載の圧縮プログラム。
11. 　コンピュータに、
    　ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書の生成を行ない、
    　前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう、
    　ことを実行させることを特徴とする圧縮方法。
12. 　ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書を生成する生成部と、
    　前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう処理部と、
    　を含むことを特徴とする圧縮装置。
13. 　圧縮装置と伸張装置とを含むシステムであって、
    　前記圧縮装置が、
    　　ファイル内に複数回出現するデータに対し圧縮符号を割り当てた圧縮辞書を生成する生成部と、
    　　前記圧縮辞書に基づいて前記ファイルの圧縮処理を行なう処理部と、
    　　前記圧縮処理により得られた圧縮データと前記圧縮辞書とを前記伸張装置に送信する送信部と、を含み、
    　前記伸張装置が、
    　　前記圧縮装置から受信した圧縮データを、前記圧縮辞書に基づいて伸張する伸張部、
    　を含むことを特徴とするシステム。
14. 　コンピュータに、
    　ファイル内のデータに基づいて、静的な圧縮符号の割り当て対象を動的に生成し、
    　生成された前記割り当て対象に圧縮符号を割り当てた圧縮辞書に基づいて、前記ファイルに対して圧縮処理を行なう、
    　処理を実行させることを特徴とする圧縮プログラム。

Images