JP5895545B2 - プログラム、圧縮ファイル生成方法、圧縮符号伸張方法、情報処理装置、および記録媒体 - Google Patents

Description

本発明は、スライド辞書法による符号化で得られた整数を符号化するプログラム、圧縮ファイル生成方法、圧縮符号伸張方法、情報処理装置、および記録媒体に関する。

データ圧縮技術には、ハフマン符号化、ＬＺ７７符号化、ＬＺ７８符号化などがある。ＬＺ７７符号化の改良技術としては、例えばＬＺＳＳ符号化がある。またＬＺＳＳで圧縮したデータをさらにハフマン符号化で圧縮する、ＺＩＰ形式やＬＺＨ形式の圧縮アルゴリズムもある。

ＬＺ７７符号化やＬＺＳＳ符号化では、スライド辞書法と呼ばれる方法で辞書を作成する。スライド辞書法では、スライド窓と呼ばれるバッファ領域が用いられる。スライド窓には、符号化対象の文字列が読み込まれた順に格納される。そしてスライド窓が文字列で満たされると、古い順に文字列が破棄される。

スライド窓内の領域は、参照部と符号化部とに分けられている。参照部に格納されている文字列を辞書として用い、符号化部に格納されている文字列が符号化される。符号化が終わった文字列は、参照部に格納される。符号化では、符号化部の先頭の文字列と最も長く一致する文字列（最長一致文字列）が、参照部の中から検索される。そして、符号化部内の文字列が、スライド窓の先頭から最長一致系列の先頭までの距離（アドレス）と、最長一致系列の長さとを示す数値に符号化される。このようにして、高い圧縮率が実現される。なお、最長一致文字列の長さが３文字未満の場合は、符号化部の先頭文字が２進数表記（例えばＡＳＣＩＩコード）で出力される。

また、ＺＩＰやＬＺＨでは、符号化された先頭アドレス、長さ、および文字の２進数表記が、さらにハフマン木を用いてハフマン圧縮される。これにより、圧縮率がさらに向上する。

なお、ハフマン圧縮については、ハフマン木を、無節点の木に変換することで、文字コードの圧縮効率の向上と圧縮処理や伸張処理の高速化を図る技術がある。

特開２０１０−９３４１４号公報

しかし、従来のスライド辞書法を用いた符号化で得られるアドレスや長さの整数は、その整数の符号化に用いられる符号化方式用に最適化された値ではない。そのためスライド辞書法による符号化で得られた整数を、例えばハフマン符号で符号化しても、十分な圧縮率が得られていない。

１つの側面では、本発明は、圧縮率を向上させることができるプログラム、圧縮ファイル生成方法、圧縮符号伸張方法、情報処理装置、および記録媒体を提供することを目的とする。

上記課題を解決するために、符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索し、符号化が終了した記号列の末尾から該最長一致記号列までの距離を示す整数を、該最長一致記号列のアドレスとし、該最長一致記号列に対応する、符号化が行われていない記号列の先頭の記号列を、該アドレスを示す整数と該最長一致記号列の長さを示す整数とに符号化し、出現頻度が高い整数ほど短い符号となるように、アドレスを示す整数と長さを示す整数を符号化する、処理をコンピュータに実行させるプログラムが提供される。

１態様によれば、圧縮率を向上させることができる。

第１の実施の形態に係るシステムの機能構成例を示す図である。 第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。 第２の実施の形態に係るコンピュータの圧縮・伸張機能を示すブロック図である。 元ファイル内の文字列の一例を示す図である。 スライド辞書法を説明する図である。 スライド辞書法による符号化の一例を示す図である。 スライド窓の先頭からのオフセットで最長一致文字列のアドレス修飾を行った場合の例を示す図である。 スライド窓の先頭からのオフセットで最長一致文字列のアドレス修飾を行った場合のアドレスの分布例を示す図である。 参照部の末尾からのオフセットで最長一致文字列のアドレス修飾を行った場合の例を示す図である。 参照部の末尾からのオフセットで最長一致文字列のアドレス修飾を行った場合のアドレスの分布例を示す図である。 アドレス（αｎ±β）におけるαの特性を示す図である。 アドレス（αｎ±β）におけるβの特性を示す図である。 最長一致文字列の圧縮状況を示す図である。 記憶部に格納された圧縮ファイルの一例を示す図である。 圧縮処理の手順の一例を示すフローチャートである。 最長一致文字列の符号化処理の手順の一例を示すフローチャートである。 アドレス要素値の算出処理の手順の一例を示すフローチャートである。 ハフマン木の生成処理の手順の一例を示すフローチャートである。 伸張処理の手順を示すフローチャートである。 スライド辞書法による復号処理の手順の一例を示すフローチャートである。 １パスによる圧縮処理の手順の一例を示すフローチャートである。 元ファイルの他の例を示す図である。 参照部の末尾からのオフセットで最長一致文字列のアドレス修飾を行った場合の他の例を示す図である。 アドレスを示す整数の特性を示す図である。 アドレスを示す整数の特性を示す図である。 スライド窓の移動例を示す図である。 スライド窓内の文字列の更新例を示す図である。 最長一致文字列の検索例を示す図である。 アドレスを示す整数の区分けの一例を示す図である。 高頻度整数と低頻度整数とのビット構成の一例を示す図である。 低頻度整数を区分けした場合の圧縮・伸張回数の一例を示す図である。 第４の実施の形態におけるハフマン木の生成処理の手順の一例を示す図である。 低頻度整数を区分けする他の例を示す図である。 整数の出現頻度と符号長との関係の一例を示す図である。 無節点の木の一例を示す図である。

以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
まず第１の実施の形態について説明する。第１の実施の形態は、スライド辞書法による符号化で得られる整数の出現頻度の偏りを増加させるものである。整数の出現頻度に偏りを持たせることで、出現頻度が高い記号ほど短い符号に符号化する符号化方式によって、より多くの整数を短い符号に符号化でき、圧縮率を向上させることができる。

図１は、第１の実施の形態に係るシステムの機能構成例を示す図である。図１には、情報処理装置１で生成した圧縮ファイル４ａを、他の情報処理装置２で伸張する場合の例を示している。

情報処理装置１は、元ファイル３内の記号列を圧縮するために、第１の符号化手段１ａと第２の符号化手段１ｂとを有する。
第１の符号化手段１ａは、符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索する。なお、符号化が終了した記号列の末尾から所定の範囲内の記号列は、例えばバッファ５に格納されている。バッファ５内の記号列は、新たな記号列の符号化が終了するごとに、第１の符号化手段１ａにより更新される。

例えば第１の符号化手段１ａは、スライド辞書法におけるスライド窓の参照部内の記号列を検索対象とし、符号部内の記号列の先頭の記号列に対しても最も長く一致する最長一致記号列を検索する。

次に第１の符号化手段１ａは、符号化が終了した記号列の末尾から該最長一致記号列までの距離（オフセット）を示す整数を、最長一致記号列のアドレスとする。そして第１の符号化手段１ａは、最長一致記号列に対応する、符号化が行われていない記号列の先頭の記号列を、アドレスを示す整数と最長一致記号列の長さを示す整数とに符号化する。例えば長さを示す整数とアドレスを示す整数との組からなる中間符号が生成される。第１の符号化手段１ａで生成された中間符号の列（中間符号列１ｃ）は、第２の符号化手段１ｂに送信される。

第２の符号化手段１ｂは、出現頻度が高い整数ほど短い符号となるように、アドレスを示す整数と長さを示す整数を符号化する。出現頻度が高い整数ほど短い符号となるように符号化する符号化方式としては、例えばハフマン符号化がある。例えば第２の符号化手段１ｂは、第１の符号化手段１ａから受信した中間符号列１ｃに示される整数の出現頻度を計算する。次に第２の符号化手段１ｂは、例えば各整数を、ハフマン木を生成するための葉に割り当てる。そして第２の符号化手段１ｂは、整数の出現頻度に基づいて、葉の上位の節点を生成し、ハフマン木を作成する。ハフマン木では、根から葉まで辿る経路に付与されたラベルの配列が、その葉に割り当てられた整数に対応する符号となる。第２の符号化手段１ｂは、長さを示す整数とアドレスを示す整数とを符号化し、圧縮ファイル４ａに格納する。そして第２の符号化手段１ｂは、圧縮ファイル４ａを、記録媒体４に格納する。なお、第２の符号化手段１ｂは、各整数の出現頻度を示す情報を記録媒体４に格納してもよい。

記録媒体４は、コンピュータ読み取り可能であり、例えば記録媒体４に格納された圧縮ファイル４ａは、情報処理装置２で読み出すことができる。記録媒体４に格納された圧縮ファイル４ａは、例えば以下のようなデータ構造を有する。

圧縮ファイル４ａには、出現頻度が高い整数ほど短い符号となるように、整数を符号化した圧縮符号が含まれている。圧縮符号の元となる整数には、符号化が終了した記号列の末尾から所定の範囲内の記号列のうち、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列のアドレスを示す整数と、最長一致記号列の長さを示す整数とが含まれる。最長一致記号列のアドレスを示す整数は、符号化が終了した記号列の末尾から所定の範囲内の記号列の末尾から最長一致記号列までの距離である。

情報処理装置２は、圧縮ファイル４ａを伸張するために、第１の復号手段２ａと第２の復号手段２ｂとを有する。
第１の復号手段２ａは、例えば圧縮ファイル４ａから符号列を取得する。取得した符号列には、アドレスを示す整数と長さを示す整数とを含む中間符号を、出現頻度が高い整数ほど短い符号に符号化することで得られた符号が含まれている。第１の復号手段２ａは、取得した符号列の先頭から順に、符号を中間符号列２ｃに復号する。例えば第１の復号手段２ａは、ハフマン木を用い、符号の値に応じ、ハフマン木の根から枝を辿り、行き着いた葉に割り当てられた整数に符号化する。なお、第１の復号手段２ａは、例えば記録媒体４から整数の出現頻度を示す情報を読み出し、読み出した情報に基づいて、符号化に用いられたものと同様のハフマン木を生成することができる。

第２の復号手段２ｂは、中間符号列２ｃに含まれるアドレスを示す整数と長さを示す整数とからなる中間符号を復号する。例えば第２の復号手段２ｂは、中間符号列２ｃ内の中間符号の復号により既に得られている記号列の末尾から、復号対象の中間符号におけるアドレスを示す整数に応じた距離にある記号を特定する。次に第２の復号手段２ｂは、特定した記号から、復号対象の中間符号における長さを示す整数分の記号列を取得する。そして第２の復号手段２ｂは、復号対象の中間符号を、取得した記号列に復号する。これにより、中間符号列２ｃが記号列に復号される。

このようなシステムによれば、元ファイル３内の記号列は、まず第１の符号化手段１ａにより中間符号列１ｃに符号化される。例えば、既に符号化された記号列として、「・・・caaad」という記号列がバッファ５に格納されており、符号化の対象として、「aaababababb・・」という記号列が続いている場合を考える。なお記号列内の各記号は、すべて１バイトで表されているものとする。この場合、「aaa」という記号列が最長一致記号列として検出される。バッファ５内の「aaa」という最長一致記号列の先頭は、バッファ５内に記号列の末尾から、４バイトの距離にある。また最長一致記号列「aaa」の長さは３バイトである。すると符号化対象の「aaababababb・・」という記号列の先頭の「aaa」が、例えば｛３，４｝という中間符号に符号化される。この中間符号は、右側の整数が最長一致記号列の長さを示し、左側の整数が最長一致記号列の先頭のアドレスを示す。

なお、元ファイル３内の先頭の所定数の記号については、例えば、その記号を表す２進数表記が、そのまま中間符号となる。また、最長一致記号列が見つからないか、あるいは検出された最長一致文字列の長さが所定値未満の場合、符号化がされていない記号列の先頭の記号は、例えば、その記号を表す２進数表記がそのまま中間符号となる。

第１の符号化手段１ａで生成された中間符号列１ｃは、第２の符号化手段１ｂに送信される。第２の符号化手段１ｂでは、最長一致文字列のアドレスや長さを示す整数の出現頻度が求められる。元ファイル３の記号列が、複数のレコードの集合のであり、レコードが何らかの項目値によってソートされている場合、ソートされた項目の記号列が同じレコードは、近傍に配置されている。この場合、最長一致記号列のアドレスは、小さな値となる。その結果、整数の出現頻度を算出すると、整数の値が０に近いほど、出現頻度が高くなるような特性が見られる。すなわち、整数の値が０近傍に偏在している。

そこで第２の符号化手段１ｂは、出現頻度が高い整数ほど短い符号に符号化する。例えば整数「１」の出現頻度が「０．１３７」であれば、３ビットの符号「０００」に符号化され、整数「２」の出現頻度が「０．０７４」であれば、４ビットの符号「００１０」に符号化される。すると、整数の値が０近傍に偏在していることで、短い符号に符号化される記号列が多くなる。その結果、生成される符号列が短くなる。すなわち圧縮率が向上する。

このような圧縮で生成された符号列は、圧縮ファイル４ａとして記録媒体４に格納できる。例えば記録媒体４が可搬型の光ディスクであれば、その光ディスクを情報処理装置２に挿入して、情報処理装置２に圧縮ファイル４ａを読み取らせることができる。なお、ネットワークを介して、圧縮ファイル４ａを情報処理装置１から情報処理装置２に送信することもできる。

情報処理装置２では、第１の復号手段２ａにより、圧縮ファイル４ａ内の符号列が、中間符号に復号される。中間符号には、例えばアドレスを示す整数と長さを示す整数とが含まれる。複数の中間符号による中間符号列２ｃは、第２の復号手段２ｂに送信される。すると第２の復号手段２ｂにより、中間符号列２ｃの先頭から順に、中間符号が記号列に復号される。例えば中間符号列２ｃの先頭の所定数の中間符号は、記号の２進数表記であり、そのまま復号後の記号となる。その後、アドレスを示す整数と長さを示す整数とを含む中間符号があれば、既に復号されている記号列の末尾から、アドレスを示す整数に応じた距離の記号が特定される。次に、特定された記号から、長さを示す整数に応じた長さの記号列が取得される。そして中間符号が、取得した記号列に復号される。中間符号列２ｃ内の中間符号が復号されると、元ファイル３内の記号列と同様の記号列が得られる。

このようにして、スライド辞書法におけるアドレスを、既に符号化された記号列の末尾からの距離で表すことで、アドレスを示す整数を、０近傍の整数に偏在させることができる。すなわち、整数の出現頻度の偏りが大きくなる。このような整数を出現頻度が大きいほど短い符号に符号化する手法で整数を符号化することで、圧縮率が向上する。

なお、第１の符号化手段１ａ、第２の符号化手段１ｂは、情報処理装置１が有するＣＰＵ（Central Processing Unit）により実現することができる。第１の復号手段２ａと第２の復号手段２ｂとは、情報処理装置２が有するＣＰＵにより実現することができる。また、記録媒体４は、光ディスクのような可搬型の記録媒体、ＲＡＭ（Random Access Memory）やハードディスクドライブ（ＨＤＤ:Hard Disk Drive）などにより実現することができる。

また、図１に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、最長一致文字列のアドレスを示す整数が０近傍に偏るように、様々な工夫を施したものである。なお、以下の説明では圧縮対象を文字列とするが、圧縮対象の文字列には記号も含むものとする。

図２は、第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。コンピュータ１００は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ１０２と複数の周辺機器が接続されている。なおコンピュータ１００が有するＣＰＵ数は１つに限定されず、複数であってもよい。コンピュータ１００が複数のＣＰＵを有する場合、複数のＣＰＵが連係動作し、装置全体を制御する。

ＲＡＭ１０２は、コンピュータ１００の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。

バス１０８に接続されている周辺機器としては、ＨＤＤ１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７がある。

ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、コンピュータ１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。

グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。

入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。

光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。

通信インタフェース１０７は、ネットワーク１０に接続されている。通信インタフェース１０７は、ネットワーク１０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。

以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお、第１の実施の形態に示した装置も、図２に示したコンピュータと同様のハードウェアにより実現することができる。

図３は、第２の実施の形態に係るコンピュータの圧縮・伸張機能を示すブロック図である。コンピュータ１００は、圧縮部１１０、記憶部１２０、および伸張部１３０を有する。

圧縮部１１０は、元ファイル２１内に記述されている文字列のデータ圧縮を行う。圧縮部１１０は、元ファイル２１のデータを高圧縮率で圧縮するために、第１の符号化処理部１１１と第２の符号化処理部１１２とを有する。

第１の符号化処理部１１１は、スライド辞書法で、元ファイル２１内の文字列を符号化する。第１の符号化処理部１１１で生成された符号は、中間符号ファイル２２に書き込まれる。中間符号ファイル２２は、例えばＲＡＭ１０２に一時的に格納される。

第２の符号化処理部１１２は、中間符号ファイル２２に含まれている所定の情報を、例えばハフマン符号に符号化する。第２の符号化処理部１１２は、生成した符号を圧縮ファイル１２１に書き込む。そして第２の符号化処理部１１２は、圧縮ファイル１２１を記憶部１２０に格納する。

記憶部１２０は、圧縮ファイル１２１を記憶する。圧縮ファイル１２１は、例えばヘッダ部１２１ａと符号部１２１ｂを有する。ヘッダ部１２１ａには、例えばスライド辞書法による符号化の際のアドレスの指定方法（修飾方法）や、ハフマン符号化の際に用いられた、符号化対象の整数の相対頻度が書き込まれている。符号部１２１ｂには、元ファイル２１内の文字列を圧縮して得られた符号が書き込まれている。

伸張部１３０は、圧縮ファイル１２１の符号部１２１ｂに書き込まれた符号を伸張し、元ファイル２１と同じ内容の伸張ファイル２４を出力する。伸張部１３０は、符号を伸張するために、第１の復号処理部１３１と第２の復号処理部１３２とを有する。

第１の復号処理部１３１は、ハフマン符号を伸張する。例えば第１の復号処理部１３１は、ヘッダ部１２１ａに示されている、整数の相対頻度の情報を用いて、ハフマン符号の復号を行う。第１の復号処理部１３１は、伸張して得られた値（中間符号）を中間符号ファイル２３に書き込む。中間符号ファイル２３は、例えばＲＡＭ１０２に一時的に格納される。

第２の復号処理部１３２は、中間符号ファイル２３に格納された中間符号を、スライド辞書法で復号する。例えば第２の復号処理部１３２は、ヘッダ部１２１ａに格納されている、修飾方法の情報を用いて、中間符号を復号する。第２の復号処理部１３２は、伸張して得られた値（平文）を伸張ファイル２４に書き込む。伸張ファイル２４は、例えばＲＡＭ１０２に一時的に格納される。

なお、圧縮部１１０と伸張部１３０とは、例えばコンピュータ１００のＣＰＵ１０１が、ＲＡＭ１０２に格納されたプログラムを実行することにより実現される。また記憶部１２０は、例えばＨＤＤ１０３または光ディスク１４の記憶領域の一部である。

また、図３に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
図３に示したような機能を有するコンピュータ１００により、元ファイル２１内の文字列がデータ圧縮され、圧縮ファイル１２１が生成される。そして圧縮ファイル１２１は、記憶部１２０に格納される。またコンピュータ１００により、圧縮ファイル１２１内の符号が伸張され、伸張ファイル２４が生成される。以下、圧縮処理と伸張処理とについて、具体的に説明する。

＜圧縮処理＞
まず、元ファイル２１内の文字列の圧縮処理について説明する。元ファイル２１内の文字列は、例えば複数のレコードの配列である。元ファイル２１内のレコードは、所定の基準によってソートされているものとする。

図４は、元ファイル内の文字列の一例を示す図である。図４に示す元ファイル２１には、タグによって構造化された名簿が格納されている。このような名簿には、各人の氏名や住所などの情報が登録されている。例えば一人の人に関する情報が、１つのレコードを構成する。

第１の符号化処理部１１１は、このような文字列を、ＺＩＰなどに利用されているスライド辞書法によって符号化する。スライド辞書法は、スライド窓と呼ばれるバッファ領域を用いて、文字列を符号化するデータ圧縮方法である。

図５は、スライド辞書法を説明する図である。スライド辞書法で用いられるスライド窓３０には、圧縮対象の文字列が、図中右側から入力され、左に向かって順次シフトする。そして、スライド窓３０内が文字列で満たされると、左端の文字から順に破棄される。このようなスライド窓３０への文字列の入力動作は、文字列上のスライド窓３０の移動と言い換えることもできる。圧縮対処の文字列のうち、スライド窓３０に囲まれた領域内の文字列が、バッファであるスライド窓３０に格納される。スライド窓３０は、圧縮対象の文字列の先頭から最後尾に向かって移動する。図５の例では、右に向かって移動する。

スライド窓３０内の領域は、参照部３１と符号化部３２とに分けられる。参照部３１に格納されている文字列が、符号化部３２に格納されている文字列の符号化用の辞書として利用される。すなわち、圧縮対象の文字列の先頭から順に符号化の対象となり、符号化の対象となった文字列は、直前の所定の範囲の文字列を辞書として用い、符号化される。

図６は、スライド辞書法による符号化の一例を示す図である。第１の符号化処理部１１１は、例えばスライド窓３０の符号化部３２の先頭からの文字列と、最も長く一致する文字列を、参照部３１から検索する。一致した文字列を、最長一致文字列４１，４２と呼ぶ。なお、最長一致文字列４１，４２は、最長一致系列とも呼ばれる。

図６の例では、符号化部３２の先頭からの３文字「ABC」と一致する文字列が、参照部３１から検出されている。符号化部３２の４文字目は「D」であるのに対し、参照部３１内の「ABC」に続く文字は「X」である。すなわち３文字の文字列は一致するが、４文字目が相違する。この場合、「ABC」の文字列が、最長一致文字列４１，４２となる。

第１の符号化処理部１１１は、符号化部３２内の最長一致文字列４１を、符号化する。その際、第１の符号化処理部１１１は、最長一致文字列４１の長さが３バイト未満の場合、文字列を符号化せずに、文字の２進数表記のまま中間符号ファイル２２に出力する。この際、第１の符号化処理部１１１は、符号化されていないことを示すフラグ「０」を、文字の先頭に付与する。

最長一致文字列４１の長さが３バイト以上あれば、第１の符号化処理部１１１は、参照部３１側の最長一致文字列４２の長さと、その最長一致文字列のアドレスとを中間符号ファイル２２に出力する。この際、第１の符号化処理部１１１は、符号化されていることを示すフラグ「１」を、文字の先頭に付与する。最長一致文字列の長さは、最長一致文字列４２のデータ長であり、例えばバイト数（整数）で表される。図６のように最長一致文字列４２が、１バイト文字で３文字分であれば、最長一致文字列の長さは「３」となる。

最長一致文字列のアドレスは、参照部３１内での最長一致文字列４２の位置を示す情報である。例えば、参照部３１内での最長一致文字列４２の先頭の文字の位置を、最長一致文字列のアドレスとすることができる。この場合、最長一致文字列のアドレスから、最長一致文字列の長さで示されるデータ長の領域に存在する文字列が、最長一致文字列４２である。

最長一致文字列のアドレスは、第２の符号化処理部１１２によってハフマン符号に符号化される。ここで、最長一致文字列のアドレスをハフマン符号に符号化する場合、アドレスを示す整数に偏りがあるほど、圧縮の効率がよくなる。すなわちハフマン符号化では、出現頻度の高いデータほど短い符号に符号化される。そのため、アドレスを示す整数の出現頻度の偏りが大きいほど、ハフマン符号化したときに、短い符号に符号化される割合が高くなり、圧縮率が向上する。

そこで、最長一致文字列のアドレス修飾方法による、アドレスを示す整数の偏り度合いの違いについて説明する。
まず、比較例として、ＺＩＰなどの既存のＬＺ７７系圧縮におけるアドレス修飾方法について説明する。既存のＬＺ７７系圧縮では、スライド窓３０の先頭からのオフセットによって、最長一致文字列のアドレスが指定される。

図７は、スライド窓の先頭からのオフセットで最長一致文字列のアドレス修飾を行った場合の例を示す図である。図７の上段は符号化部３２の先頭が人名となった場合の例であり、下段は符号化部３２の先頭が地名となった場合の例である。

例えば、符号化部３２の先頭の文字列が、タグ付きの人名「<name>片岡正光</name>・・・」となった場合、この文字列に基づいて、参照部３１から最長一致文字列が検索される。すると符号化部３２内の「<name>片岡正」が、符号化部３２の最長一致文字列４３となり、その文字列と同じ参照部３１内の同じ文字列が、参照部３１の最長一致文字列４４となる。この場合、参照部３１の先頭から最長一致文字列４４の先頭の文字までのオフセットγａが、最長一致文字列４４のアドレスとなる。

また、上段の例の場合と各レコードのデータ長が異なっていれば、参照部３１の先頭の文字列が上段の例と同じでも、符号化部３２の先頭が地名となる場合も考えられる。符号化部３２の先頭の文字列が、タグ付きの地名「<addr>神奈川県川崎市多摩区・・・」となった場合、この文字列に基づいて、参照部３１から最長一致文字列が検索される。すると符号化部３２内の「<addr>神奈川県」が、符号化部３２の最長一致文字列４５となり、その文字列と同じ参照部３１内の同じ文字列が、参照部３１の最長一致文字列４６となる。この場合、参照部３１の先頭から最長一致文字列４６の先頭の文字までのオフセットγｂが、最長一致文字列４４のアドレスとなる。

この場合、アドレスを示す整数の出現頻度の分布は、オフセットγａ，γｂの影響を受ける。
図８は、スライド窓の先頭からのオフセットで最長一致文字列のアドレス修飾を行った場合のアドレスの分布例を示す図である。図８の横軸は、最長一致文字列のアドレスを示す整数であり、縦軸は整数の出現頻度である。図８に示すように、スライド窓の先頭からのオフセットで最長一致文字列のアドレス修飾を行うと、人名や地名は、氏名までのオフセットγａ，γｂに影響される。すると、レコードを構成する文字列の種別（例えば人名や地名）ごとにはアドレスの偏りがあっても、異なる種別の文字列間ではアドレスが分散する。その結果、全体としてはアドレスを示す整数の偏りはあまり大きくない。

次に、参照部３１の末尾（図５中の右端）から最長一致文字列４２の先頭の文字までのオフセットを、最長一致文字列４２のアドレスとした場合について説明する。
図９は、参照部の末尾からのオフセットで最長一致文字列のアドレス修飾を行った場合の例を示す図である。図９に示すように、参照部３１内の最長一致文字列４４，４６は、参照部３１の末尾からのオフセットにより指定することができる。

このようなアドレスを採用すると、図４に示す名簿のような定型化された文字列の場合、最長一致文字列のアドレスを示す整数の出現頻度が高くなる値は、レコード長を１周期とする周期性を採る傾向がある。例えばアドレスをαｎ＋β（またはαｎ−β）で表すことができる。なお「αｎ」は、α×ｎの乗算を示している。

ここでｎは、最長一致文字列のアドレスを示す整数の出現頻度が高くなる周期である。この周期は、１レコード当たりのレコード長に近似するものと想定できる。なお周期ｎは、１以上の整数である。レコードが固定長であれば、固定長のバイト数が、周期ｎとなる。レコードが可変長であれば、例えば、レコードのデータ長の平均値の小数点以下を四捨五入した値が、周期ｎとなる。

αは、符号部１２１ｂ内の最長一致文字列４１が属するレコードと、参照部３１内の最長一致文字列４２が属するレコードとの間の識別番号（レコード番号）の差分である。なお図４に示した文字列では、<number>タグで囲まれた数値が、各レコードのレコード番号である。αは、１以上の整数である。

βは、可変長の場合における、周期ｎの倍数とアドレスとの誤差である。βは、０以上の整数である。レコードが固定長の場合、βの値は「０」である。
次に、アドレスを「αｎ±β」と表すことの合理性について説明する。

図１０は、参照部の末尾からのオフセットで最長一致文字列のアドレス修飾を行った場合のアドレスの分布例を示す図である。図１０の横軸は、最長一致文字列のアドレスを示す整数であり、縦軸は整数の出現頻度である。図１０に示すように、アドレスを示す出現頻度が高い整数の値には、レコード長を１周期とする周期性が確認できる。そしてアドレスを示す整数は、レコード長の整数倍「αｎ」の位置近傍に偏在していることが分かる。すなわち、最長一致文字列のアドレスにおける出現頻度が高くなる値は、レコード長に応じた周期ｎを１サイクルとする周期性を有している。

このようにアドレスが、レコード長による周期性を有している場合、アドレスを「αｎ±β」と表すことで、αとβとの整数を、０近傍に偏らせることができる。
図１１は、アドレス（αｎ±β）におけるαの特性を示す図である。図１１では、横軸にαの値（整数）を採り、縦軸にαの値が出現する頻度を示している。図１１に示すように、αの値が大きくなるほど、その整数が出現する頻度は小さくなっている。すなわちαの値は、０近傍に偏在している。なお図１１では、スライド窓３０の参照部３１のサイズが無限大（∞）であるものとしてグラフを作成しているが、実際には参照部３１のサイズは有限である。そのためスライド窓３０の参照部３１に格納可能なレコード数がαの最大値となり、αが最大値となったときの頻度が、頻度の最小値となる。

図１２は、アドレス（αｎ±β）におけるβの特性を示す図である。図１２では、横軸にβの値（整数）を採り、縦軸にβの値が出現する頻度を示している。図１２に示すように、βの値が大きくなるほど、その整数が出現する頻度は小さくなっている。すなわちβの値は、０近傍に偏在している。なお図１２では、レコード長に応じた周期ｎの倍数（αｎ）とアドレスとの誤差が無限大（∞）まであり得るものとしてグラフを作成しているが、誤差は、最大でも周期ｎの半分の値である。そのため誤差の最大値がβの最大値となり、βが最大値となったときの頻度が、頻度の最小値となる。

図１０〜図１２に示したような、レコード長によるアドレスの周期性は、図４に示した名簿のような文字列を圧縮対象とした場合に顕著に表れる。すなわち、図４のような名簿の文字列は、レコード内の項目の値の出現位置について、レコード長による周期性がある。例えば氏名、所属、住所などの項目に登録されている人名や地名などの文字列が、概ねレコード長周期で出現する。

このような文字列をスライド辞書法で符号化する際に、スライド窓３０の先頭からのオフセットをアドレスとすると、オフセットの基準となる位置の文字（参照部３１の先頭の文字列）と、最長一致文字列との関連がない（図８参照）。そのため、レコード長による文字列出現頻度の周期性が、アドレスに反映されない。

他方、参照部３１の末尾からのオフセットをアドレスとすると、符号化部３２内の最長一致文字列の前の文字からのオフセットとなる。符号化部３２内の最長一致文字列と、参照部３１内の最長一致文字列とは、複数の項目（氏名や地名）を含むレコードにおける同じ項目の文字列であることが多い。そのため参照部３１の末尾からのオフセットをアドレスとすれば、レコード内の項目の出現周期（レコード長）がアドレスに反映される。そこで、第２の実施の形態では、参照部３１の末尾からのオフセットをアドレスとしている。

また第２の実施の形態では、例えば、参照部３１内に最長一致文字列が複数検出された場合、参照部３１の末尾に近い最長一致文字列の位置を、符号化時のアドレスとする。これにより、αの値の０近傍への偏りを高めることができる。

元ファイル２１内のすべての文字列がスライド辞書法で符号化されると、中間符号ファイル２２に基づいて、第２の符号化処理部１１２によってハフマン符号への符号化が行われる。例えば、第２の符号化処理部１１２は、最長一致文字列の長さと、最長一致文字列のアドレスを、ハフマン符号に符号化する。このとき第２の符号化処理部１１２は、「αｎ±β」の形式表された最長一致文字列のアドレスについては、「α」と「β」とを個別に符号化する。

図１３は、最長一致文字列の圧縮状況を示す図である。最長一致文字列のアドレスは、「αｎ＋β」の場合と、「αｎ−β」の場合とがある。「αｎ＋β」の場合には、ハフマン圧縮によりαとβとが個別に符号化され、「＋」の符号が「０」に変換される。「αｎ−β」の場合には、ハフマン圧縮によりαとβとが個別に符号化され、「−」の符号が「１」に変換される。なおαとβとのハフマン圧縮には、例えば共通のハフマン木を使用することができる。なお、ハフマン木は、符号化に用いる符号の木の一例である。符号の木としては、第５の実施の形態に示す無節点の木（図３５）を用いることもできる。

図１１、図１２に示したように、αとβとの値は、０近傍に偏在している。そのため、最長一致文字列のアドレスを「αｎ＋β」の形式で表し、αとβとを個別にハフマン圧縮することで、圧縮率を高めることができる。しかもアドレスを「αｎ＋β」の形式で表すことで、圧縮符号長を短縮することができ、圧縮率がさらに向上する。

図１４は、記憶部に格納された圧縮ファイルの一例を示す図である。記憶部１２０に格納された圧縮ファイル１２１のヘッダ部１２１ａには、例えば圧縮方式として、スライド辞書法におけるアドレスが、参照部３１の末尾からのオフセットであることが示されている。またヘッダ部１２１ａには、アドレス形式が「αｎ±β」の形式であることが示されている。またヘッダ部１２１ａには、レコード長に応じた周期ｎの値が示されている。さらにヘッダ部１２１ａには、文字の２進数表示の出現頻度や、整数の出現頻度が設定されている。

符号部１２１ｂには、例えば文字の２進数表示の圧縮符号１２１ｃや長さとアドレスとの圧縮符号１２１ｄが設定されている。アドレスの圧縮符号は、例えばαの圧縮符号、正負を示すフラグ、およびβの圧縮符号で構成されている。

このような圧縮ファイル１２１は、例えば光ディスク１４などの可搬型の記録媒体に格納することもできる。この場合、図３と同様の機能を有する他のコンピュータに、可搬型の記録媒体内の圧縮ファイル１２１を読み取らせ、元ファイル２１に伸張させることができる。

次に、以上のような技術を用いた圧縮処理の手順について説明する。
図１５は、圧縮処理の手順の一例を示すフローチャートである。以下、図１５に示す処理をステップ番号に沿って説明する。なお図１５に示す圧縮処理は、元ファイル２１内のすべての文字列をスライド辞書法で符号化した後に、ハフマン符号に符号化する方式（２パス方式）である。２パス方式以外の圧縮方式について後述する（第３の実施の形態）。

［ステップＳ１０１］第１の符号化処理部１１１は、元ファイル２１内の文字列を先頭から順に読み出し、スライド窓３０に格納する。例えば第１の符号化処理部１１１は、スライド窓３０の符号化部３２に、文字列を格納する。

［ステップＳ１０２］第１の符号化処理部１１１は、スライド窓３０の参照部３１に格納された文字列を辞書として用い、符号化部３２内の最長一致文字列を符号化する。この処理の詳細は後述する（図１６参照）。

［ステップＳ１０３］第１の符号化処理部１１１は、スライド窓３０のデータを更新する。例えば第１の符号化処理部１１１は、参照部３１内に符号化された文字列分の空き領域があれば、符号化された文字列を参照部３１内の文字列の末尾の後ろに書き込む。また第１の符号化処理部１１１は、参照部３１内に符号化された文字列分の空き領域がなければ、参照部３１内の文字列の先頭から順に文字を削除し、符号化された文字列分の空き領域を設け、参照部３１内の文字列を前方にシフトする。そして第１の符号化処理部１１１は、符号化された文字列を参照部３１内の文字列の末尾の後ろに書き込む。

また第１の符号化処理部１１１は、符号化された文字列を符号化部３２から削除し、符号化部３２内の文字列を前方にシフトする。そして第１の符号化処理部１１１は、元ファイル２１内に未処理の文字列があれば、先頭から順に読み出し、スライド窓の符号化部３２の空き領域に格納する。

［ステップＳ１０４］第１の符号化処理部１１１は、スライド窓３０の符号化部３２が空になったか否かを判断する。スライド窓３０の符号化部３２が空になった場合、第１の符号化処理部１１１は、処理をステップＳ１０５に進める。またスライド窓３０の符号化部３２に、符号化が未処理の文字列が残っていれば、第１の符号化処理部１１１は、処理をステップＳ１０２に進める。

［ステップＳ１０５］第２の符号化処理部１１１は、最長一致文字列のアドレスの要素値（ｎ、α、β）を算出する。この処理の詳細は後述する（図１７参照）。
［ステップＳ１０６］第２の符号化処理部１１２は、ハフマン木を生成する。

［ステップＳ１０７］第２の符号化処理部１１２は、中間符号ファイル２２内の符号列（アドレス、長さ、文字の２進数表示）を、ハフマン符号に符号化する。なお図１３に示すように、アドレスについて「αｎ＋β」の形式で記載されている場合、αとβとを個別に符号化する。また第２の符号化処理部１１２は、例えば、α・β・長さおよび文字の２進数表記を、それぞれ個別のハフマン木を用いて符号化する。なおαとβとの頻度特性が類似していれば、共通のハフマン木を用いて得符号化することもできる。

［ステップＳ１０８］第２の符号化処理部１１２は、圧縮ファイル１２１を出力する。例えば、第２の符号化処理部１１２は、ステップＳ１０６で生成した符号を、圧縮ファイル１２１の符号部１２１ｂに書き込む。また第２の符号化処理部１１２は、圧縮ファイル１２１のヘッダ部１２１ａに、アドレス修飾の方法を示す情報や、アドレスや長さの整数の出現確率を書き込む。アドレス修飾の方法を示す情報には、例えば、参照部３１の末尾から最長一致文字列の先頭までのオフセットをアドレスとしたこと、「αｎ＋β」の形式のアドレスの「α」と「β」とを個別に符号化したこと、ｎ（レコード長）の値などが示される。またヘッダ部１２１ａには、例えば、α・β・長さ・文字の２進数表記を、それぞれ個別のハフマン木で符号化したのか、あるいはαとβについては共通のハフマン木で符号化したのかを示す情報が含まれる。そして第２の符号化処理部１１２は、例えば生成した圧縮ファイル１２１を記憶部１２０に格納する。

このようにして、元ファイル２１内の文字列が圧縮され、圧縮ファイル１２１が生成される。
次に最長一致文字列の符号化処理（ステップＳ１０２）について詳細に説明する。

図１６は、最長一致文字列の符号化処理の手順の一例を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。
［ステップＳ１１１］第１の符号化処理部１１１は、スライド窓３０の符号化部３２の先頭の文字列に対応する最長一致文字列を、参照部３１から検索する。最長一致文字列が複数検出された場合、第１の符号化処理部１１１は、参照部３１の末尾に近い方の最長一致文字列を、検索結果とする。

［ステップＳ１１２］第１の符号化処理部１１１は、検索結果として得られた最長一致文字列のアドレスと長さを取得する。最長一致文字列のアドレスは、例えば参照部３１の末尾から最長一致文字列の先頭の文字までのオフセット（バイト数）である。長さは、最長一致文字列のバイト数である。

［ステップＳ１１３］第１の符号化処理部１１１は、最長一致文字列の長さが３バイト以上か否かを判断する。第１の符号化処理部１１１は、最長一致文字列の長さが３バイト以上であれば、処理をステップＳ１１４に進める。また第１の符号化処理部１１１は、最長一致文字列の長さが３バイト未満であれば、処理をステップＳ１１５に進める。

［ステップＳ１１４］第１の符号化処理部１１１は、アドレスと長さを示す符号を中間符号ファイル２２に出力する。例えばアドレスは、図６に示したようなデータ形式で出力される。その後、最長一致文字列の符号化処理が終了する。

［ステップＳ１１５］第１の符号化処理部１１１は、最長一致文字列の長さが３バイト未満の場合、最長一致文字列の２進数表記を、符号として中間符号ファイル２２に出力する。その後、最長一致文字列の符号化処理が終了する。

このようにして、最長一致文字列が符号化される。このような符号化が、元ファイル２１内のすべての文字列に対して行われる。
次に、アドレス要素値の算出処理（ステップＳ１０５）について詳細に説明する。

図１７は、アドレス要素値の算出処理の手順の一例を示すフローチャートである。以下、図１７に示す処理をステップ番号に沿って説明する。
［ステップＳ１２１］第２の符号化処理部１１２は、アドレスの各整数をＲＡＭ１０２に記録する。

［ステップＳ１２２］第２の符号化処理部１１２は、記録した整数をグループ化する。例えば図１０のように、アドレスを示す整数とその整数の出現頻度とを求める。そして出現頻度が１以上で連続する整数を、１つのグループとする。また出現頻度が１以上で連続する整数において、出現頻度の増減が繰り返される場合、例えば、出現頻度が減少から増加に転じる整数の値を境界として、その境界の前後で異なるグループとなるようにグループを分けをする。これにより、例えば図１０に示すような出現頻度の整数を、「α＝１」のときのαｎ近傍の整数のグループ、「α＝２」のときのαｎ近傍の整数のグループというように、アドレスを示す整数が複数のグループに分けられる。

［ステップＳ１２３］第２の符号化処理部１１２は、グループごとのαを決定する。例えば第２の符号化処理部１１２は、グループごとに、そのグループに属する整数の平均値を求める。次に第２の符号化処理部１１２は、平均値を昇順に並べる。そして第２の符号化処理部１１２は、平均値が小さいグループから順に、１から昇順の整数をαとして割り当てる。各グループに割り当てられたαの値が、そのグループに属する整数におけるαの値となる。

［ステップＳ１２４］第２の符号化処理部１１２は、グループ化された整数に基づいて、出現頻度が高くなる整数の周期性を調査し、レコード長に応じた周期ｎを判断する。例えば第２の符号化処理部１１２は、複数のグループを、割り当てられたαの値が小さい順に並べる。次に第２の符号化処理部１１２は、グループごとに、グループ内での整数の平均値を計算する。さらに第２の符号化処理部１１２は、隣接するグループ間での平均値の差分を求め、グループ間距離とする。そして第２の符号化処理部１１２は、グループ間距離の平均値を周期ｎとする。

なお、第２の符号化処理部１１２は、グループ内での整数の平均値に代えて、グループ内で出現頻度が最大値となる整数を求めてもよい。この場合、第２の符号化処理部１１２は、隣接するグループ間での出現頻度が最大値となる整数の差分を、グループ間距離とする。

［ステップＳ１２５］第２の符号化処理部１１２は、各整数のβの値を求める。例えば第２の符号化処理部１１２は、アドレスを示す整数が属するグループに割り当てられてαの値と、ステップＳ１２４で求めた周期ｎとにより、「α×ｎ」を計算する。そしてアドレスを示す整数と「α×ｎ」との差分をβとする。このときアドレスを示す整数が「α×ｎ」以上であれば、βの符号は「＋」となる。またアドレスを示す整数が「α×ｎ」より小さければ、βの符号は「−」となる。

このようにして、最長一致文字列のアドレスを「αｎ±β」の形式で表すことができる。
次に、ハフマン木の生成処理（ステップＳ１０６）について説明する。

図１８は、ハフマン木の生成処理の手順の一例を示すフローチャートである。以下、図１８に示す処理をステップ番号に沿って説明する。
［ステップＳ１３１］第２の符号化処理部１１２は、αを示す整数の出現頻度の出現頻度を求める。αを示す整数の出現頻度は、例えばすべてのアドレスのαの総出現回数のうち、その整数が出現した回数である。そして第２の符号化処理部１１２は、αを示す整数の出現頻度に基づいて、ハフマン木を生成する。

［ステップＳ１３２］第２の符号化処理部１１２は、βを示す整数の出現頻度の出現頻度を求める。βを示す整数の出現頻度は、例えばすべてのアドレスのβの総出現回数のうち、その整数が出現した回数である。そして第２の符号化処理部１１２は、βを示す整数の出現頻度に基づいて、ハフマン木を生成する。

［ステップＳ１３３］第２の符号化処理部１１２は、αとβとの頻度特性の類似性を判定する。第２の符号化処理部１１２は、例えば整数の値ごとに、αの出現頻度とβの出現頻度との差分を計算する。第２の符号化処理部１１２は、整数の値ごとに得られた差分を合計し、合計値が所定値以下であれば、類似していると判断する。

［ステップＳ１３４］第２の符号化処理部１１２は、αとβとの頻度特性の類似が類似している場合、処理をステップＳ１３５に進める。また第２の符号化処理部１１２は、αとβとの頻度特性が類似していない場合、処理をステップＳ１３６に進める。

［ステップＳ１３５］第２の符号化処理部１１２は、αとβとに共通のハフマン木を生成する。例えば第２の符号化処理部１１２は、αまたはβを示す整数の出現頻度の出現頻度を求める。この場合の整数の出現頻度は、例えばすべてのアドレスのαの総出現回数とβの総出現回数との和のうち、その整数が出現した回数である。そして第２の符号化処理部１１２は、αまたはβを示す整数の出現頻度に基づいて、ハフマン木を生成する。

［ステップＳ１３６］第２の符号化処理部１１２は、長さを示す整数の出現頻度の出現頻度を求める。長さを示す整数の出現頻度は、例えばすべての長さを示す整数の総出現回数のうち、その整数が出現した回数である。そして第２の符号化処理部１１２は、長さを示す整数の出現頻度に基づいて、ハフマン木を生成する。

［ステップＳ１３７］第２の符号化処理部１１２は、文字の２進数表記の出現頻度の出現頻度を求める。文字の２進数表記の出現頻度は、例えば文字の２進数表記の総出現回数のうち、その文字の２進数表記が出現した回数である。そして第２の符号化処理部１１２は、文字の２進数表記の出現頻度に基づいて、ハフマン木を生成する。

このようにして、圧縮辞書として用いるハフマン木が生成される。生成されたハフマン木を用いて、スライド辞書法によって生成されたアドレスや長さなどの整数や、文字の２進数表示が、ハフマン符号に符号化される。なお、αとβとの出現頻度の特性が類似している場合、ハフマン木を共通化することで、圧縮・伸張時に使用するメモリなどの資源が少なくて済む。

次に圧縮ファイル１２１に含まれている符号の伸張処理について説明する。
図１９は、伸張処理の手順を示すフローチャートである。以下、図１９に示す処理をステップ番号に沿って説明する。

［ステップＳ１４１］第１の復号処理部１３１は、圧縮ファイル１２１のヘッダ部１２１ａから、整数および文字の２進数表示の出現頻度を読み出す。
［ステップＳ１４２］第１の復号処理部１３１は、ハフマン木を生成する。例えば第１の復号処理部１３１は、整数の出現頻度に基づいて、アドレス（α・β）と長さを示すハフマン符号を伸張するためのハフマン木を生成する。また第１の復号処理部１３１は、文字の２進数表示の出現頻度に基づいて、文字の進数表示のハフマン符号を伸張するためのハフマン木を生成する。なおハフマン木の生成方法は、データ圧縮時のハフマン木の生成方法と同じである。

［ステップＳ１４３］第１の復号処理部１３１は、圧縮ファイル１２１の符号部１２１ｂ内の最長一致文字列のハフマン符号を、先頭から順に復号する。例えば第１の復号処理部１３１は、最長一致文字列がアドレスと長さで表されていれば、アドレス（α・β）と長さを示すハフマン符号を、共通のハフマン木に基づいて復号する。また第１の復号処理部１３１は、最長一致文字列が文字の２進数表示で表されていれば、文字の２進数表示を示すハフマン符号を、文字の２進数表示用のハフマン木に基づいて復号する。伸張されたデータ（中間符号）は、中間符号ファイル２３に格納される。

［ステップＳ１４４］第２の復号処理部１３２は、スライド辞書法により、中間符号ファイル２３内の中間符号を復号する。この処理の詳細は後述する（図２０参照）。
［ステップＳ１４５］第１の復号処理部１３１は、圧縮ファイル１２１の符号部１２１ｂ内の符号をすべて復号したか否かを判断する。第１の復号処理部１３１は、すべての符号の復号が完了した場合、処理を終了する。また第１の復号処理部１３１は、復号していない符号があれば、処理をステップＳ１４３に進める。

このようにして、符号部１２１ｂ内の符号が復号される。
次にスライド辞書法による復号処理の手順について説明する。
図２０は、スライド辞書法による復号処理の手順の一例を示すフローチャートである。以下、図２０に示す処理をステップ番号に沿って説明する。なお初期状態では、スライド窓の内容は空であるものとする。

［ステップＳ１５１］第２の復号処理部１３２は、中間符号ファイル２３から、第１の復号処理部１３１で復号された、１つの最長一致文字列分の符号（中間符号）を取得する。

［ステップＳ１５２］第２の復号処理部１３２は、取得した中間符号が、アドレス＋長さの形式の符号か、あるいは文字の２進数表示かを判断する。例えば第２の復号処理部１３２は、中間符号の先頭のフラグが「０」であれば、文字の２進数表記であると判断する。また第２の復号処理部１３２は、中間符号の先頭のフラグが「１」であれば、アドレス＋長さの形式であると判断する。第２の復号処理部１３２は、文字の２進数表記であれば、処理をステップＳ１５３に進める。また第２の復号処理部１３２は、アドレス＋長さの形式であれば、処理をステップＳ１５４に進める。

［ステップＳ１５３］第２の復号処理部１３２は、中間符号が文字の２進数表記であれば、文字の進数表現を伸張ファイル２４に出力する。その後、第２の復号処理部１３２は、処理をステップＳ１５７に進める。

［ステップＳ１５４］第２の復号処理部１３２は、中間符号がアドレス＋長さの形式であれば、「αｎ＋β」の形式で記述されているアドレスを、アドレスを示す整数に変換する。例えば第２の復号処理部１３２は、圧縮ファイル１２１のヘッダ部１２１ａから、レコード長に応じた周期ｎを取得する。そして第２の復号処理部１３２は「αｎ＋β」を計算し、アドレスを示す整数を得る。

［ステップＳ１５５］第２の復号処理部１３２は、アドレスを示す整数と、長さを示す整数とを、文字列に復号する。例えば第２の復号処理部１３２は、アドレスに示す整数を、スライド窓内の復号されている文字列の末尾からのオフセットとして、そのオフセットの位置の文字を検出する。そして第２の復号処理部１３２は、検出した文字から長さで示されたデータ長分の文字列を取得し、復号後の文字列とする。

［ステップＳ１５６］第２の復号処理部１３２は、復号された文字列を伸張ファイル２４に出力する。
［ステップＳ１５７］第２の復号処理部１３２は、スライド窓のデータを更新する。例えば第２の復号処理部１３２は、復号された文字数分だけ、スライド窓内の先頭の文字列を破棄する。次に第２の復号処理部１３２は、復号された文字数分だけ、スライド窓内の文字列を前方にシフトする。そして第２の復号処理部１３２は、スライド窓内の末尾に復号された文字列を格納する。

このようにして、最長一致文字列に対応する符号を、元の最長一致文字列に復号することができる。
以上説明したように、第２の実施の形態では、スライド辞書法による符号化の際に、参照部３１の末尾からのオフセットをアドレスとし、アドレスを「αｎ＋β」の形式で表している。これにより、αやβを０近傍の整数に偏らせることができる。ハフマン符号は、出現頻度の高い整数ほど、短い符号に符号化される。そのため、０近傍に偏った整数をハフマン符号に符号化することが、圧縮効率が向上する。

〔第３の実施の形態〕
次に第３の実施の形態について説明する。第３の実施の形態は、１パスによるデータ圧縮を行うものである。なお第３の実施の形態を実現するための機能構成は、図３に示した第２の実施の形態の機能構成と同じである。そこで図３に示した各要素の符号を用いて、第３の実施の形態の処理を説明する。

図２１は、１パスによる圧縮処理の手順の一例を示すフローチャートである。以下、図２１に示す処理をステップ番号に沿って説明する。
［ステップＳ２０１］第１の符号化処理部１１１は、元ファイル２１内の文字列を先頭から順に読み出し、スライド窓３０に格納する。例えば第１の符号化処理部１１１は、スライド窓３０の符号化部３２に、文字列を格納する。

［ステップＳ２０２］第１の符号化処理部１１１は、スライド窓３０の参照部３１に格納された文字列を辞書として用い、符号化部３２内の最長一致文字列を符号化する。この処理の詳細は、第２の実施の形態における最長一致文字列の符号化処理（図１６参照）と同様である。

［ステップＳ２０３］第１の符号化処理部１１１は、スライド窓３０のデータを更新する。この処理の詳細は、図１５のステップＳ１０３の処理と同様である。
［ステップＳ２０４］第１の符号化処理部１１１は、スライド窓３０が文字列で満杯になったか否かを判断する。スライド窓３０が文字列で満杯になった場合、第１の符号化処理部１１１は、処理をステップＳ２０５に進める。またスライド窓３０が文字列で満杯になっていなければ、第１の符号化処理部１１１は、処理をステップＳ２０２に進める。

［ステップＳ２０５］第２の符号化処理部１１１は、最長一致文字列のアドレスの要素値（ｎ、α、β）を算出する。この処理の詳細は、図１７に示した第２の実施の形態の処理と同様である。

［ステップＳ２０６］第２の符号化処理部１１２は、ハフマン木を生成する。ハフマン木は、例えばアドレス「αｎ＋β」のαとβとのそれぞれに応じて生成される。またαとβとの出現頻度の特性が類似していれば、αとβとの整数の出現頻度に応じて、１つのハフマン木を生成することもできる。ハフマン木の生成処理の詳細は、図１８に示した第２の実施の形態の処理と同様である。

［ステップＳ２０７］第１の符号化処理部１１１は、最長一致文字列の符号化処理を再度実行する。例えば第１の符号化処理部１１１は、ステップＳ２０２で符号化された文字列の次の文字から符号化を再開する。

［ステップＳ２０８］第１の符号化処理部１１１は、ステップＳ２０３の処理と同様に、スライド窓３０のデータを更新する。
［ステップＳ２０９］第１の符号化処理部１１１は、スライド窓３０の符号化部３２が空になったか否かを判断する。スライド窓３０の符号化部３２が空になった場合、第１の符号化処理部１１１は、処理をステップＳ２１０に進める。またスライド窓３０の符号化部３２に、符号化が未処理の文字列が残っていれば、第１の符号化処理部１１１は、処理をステップＳ２０７に進める。

［ステップＳ２１０］第２の符号化処理部１１２は、中間符号ファイル２２内の符号列（アドレス、長さ、文字の２進数表示）を、ハフマン符号に符号化する。なお図１３に示すように、アドレスについて「αｎ＋β」の形式で記載されている場合、αとβとを個別に符号化する。また第２の符号化処理部１１２は、例えば、α・β・長さおよび文字の２進数表記を、それぞれ個別のハフマン木を用いて符号化する。なおαとβとの頻度特性が類似していれば、共通のハフマン木を用いて得符号化することもできる。

［ステップＳ２１１］第２の符号化処理部１１２は、圧縮ファイル１２１を出力する。
このように、中間符号の一部を用いてハフマン木を生成することで、ハフマン木の生成処理が容易となる。その結果、圧縮処理の高速化が図れる。

〔第４の実施の形態〕
次に第４の実施の形態について説明する。第４の実施の形態は、文字列の出現頻度が、レコード長による周期性を有していない場合に適したデータ圧縮処理である。以下、第４の実施の形態における第２の実施の形態との相違点について説明する。

図４〜図１３には、名簿のデータベースのようなデータベース系のファイルを圧縮する場合の、スライド辞書法による符号化について説明した。データベース系のファイルでは、各レコードに共通の項目が含まれており、各項目の文字列が、レコード長による周期性を持って出現する。他方、名簿のようなデータベースほどレコード長による周期性を有していないデータもある。例えば、国語辞書などの辞書の文字列は、名簿ほどのレコード長による周期性は期待できない。

そこで、第４の実施の形態では、第２の実施の形態で示した最長一致文字列のアドレスと長さを、以下のように補正し、０の近傍に近づける。
・補正後のアドレス＝参照部の末尾から最長一致文字列の先頭までのオフセット−最長一致文字列の長さ
・補正後の長さ＝最長一致文字列の長さ−３
補正後のアドレスは、参照部の末尾から最長一致文字列の末尾までのオフセットを示している。

補正後の長さは、長さを示す整数の開始値を「０」にシフトしたものである。すなわち、最長一致文字列が「０」ということはないため、補正前の長さを示す整数として「０」は使用されない。また最長一致文字列の長さが２バイト以下の場合、第２の実施の形態と同様に、文字列の２進数表記が中間符号として出力される。そのため、補正前の長さを示す整数として「１〜２」も使用されない。このように補正前の長さを示す整数では「０〜２」は使われない。そこで第４の実施の形態では、「３，４，５，・・・」という配列の整数が、「０」から開始される「０，１，２，・・・」という配列の整数に補正される。これにより、長さを示す整数を「０」近傍に偏らせることができる。なお、伸張時には、復号して得られた長さを示す整数に「３」を加えた値が、最長一致文字列の長さとなる。

図２２は、元ファイルの他の例を示す図である。図２２に示す元ファイル２１ａには、電子辞書に用いる辞書データが、圧縮対象の文字列として格納されている。図２２に示すように、電子辞書や電子書籍の本文（例えばＸＨＴＭＬ（Extensible HyperText Markup Language）ファイルは、見出しと解説で構成されている。すると、見出し語などに、関連した用語や基礎単語などの文字列が繰り返し表記される。例えば、図２２の例では、”『相合”という文字列が繰り返し出現する。このような電子辞書などの辞書データに関しては、最長一致文字列のアドレスとして、例えば参照部３１の末尾から最長一致文字列の末尾の文字までのオフセットを使用する。

図２３は、参照部の末尾からのオフセットで最長一致文字列のアドレス修飾を行った場合の他の例を示す図である。図２３の例では、辞書データの”『相合牛」・・・”という文字列が符号化部３２の先頭にあるものとする。そして符号化部３２の”『相合”の３文字を最長一致文字列４７とし、参照部３１からは、２つの最長一致文字列４８，４９が検出されている。この場合、参照部３１の末尾に近い方の最長一致文字列４９を用いて、符号化部３２の最長一致文字列４７が符号化される。

符号化の際に、最長一致文字列４９のアドレスと長さが決定される。このとき、参照部３１の末尾から最長一致文字列４９の末尾の文字までのオフセットを、アドレスとする。このようにして決定したアドレスおよび長さは、以下のような特性を有する。

図２４は、アドレスを示す整数の特性を示す図である。図２４では、横軸にアドレスを示す整数の値を示し、縦軸にアドレスを示す整数の値が出現する頻度を示している。図２４に示すように、アドレスを示す整数の値が大きくなるほど、その整数が出現する頻度は小さくなっている。すなわちアドレスを示す整数の値は、０近傍に偏在している。なお図２４では、スライド窓３０の参照部３１のサイズが無限大（∞）であるものとしてグラフを作成しているが、実際には参照部３１のサイズは有限である。そのためスライド窓３０の参照部３１のデータ長がアドレスを示す整数の最大値となり、アドレスを示す整数が最大値となったときの頻度が、頻度の最小値となる。

図２５は、アドレスを示す整数の特性を示す図である。図２５では、横軸に長さを示す整数の値を示し、縦軸にアドレスを示す整数の値が出現する頻度を示している。図２５に示すように、長さを示す整数の値が大きくなるほど、その整数が出現する頻度は小さくなっている。すなわち長さを示す整数の値は、０近傍に偏在している。なお図２５では、スライド窓３０の参照部３１のサイズが無限大（∞）であるものとしてグラフを作成しているが、実際には参照部３１のサイズは有限である。そのためスライド窓３０の参照部３１のデータ長が、長さを示す整数の最大値となり、長さを示す整数が最大値となったときの頻度が、頻度の最小値となる。

このようにして、電子辞書などのデータをスライド辞書法で符号化したときの符号を、０の近傍に偏らせることができる。特に、アドレスについては、参照部３１の末尾から最長一致文字列の末尾の文字をまでのオフセットをアドレスとしたことで、アドレスを示す整数の値が、「０」近傍への偏り度合いが高くなる。

次に、スライド窓の制御およびアドレスの計算方法について詳細に説明する。
スライド窓３０はＦＩＦＯ（First-In First-Out）型のバッファである。スライド窓３０には、符号化対象の文字列が順次入力され、スライド窓３０内が文字列で満杯になると、古い文字列から順に破棄される。このような動作を、文字列上でのスライド窓の移動と捉えると、図２６のように表せる。

図２６は、スライド窓の移動例を示す図である。図２６では、スライド窓３０のうちの参照部３１の論理的な移動を示している。図２６には、「→うし」という文字列の符号化が完了した後の、スライド窓３０の移動状況が示されている。「→うし」という３文字列が符号化されたことで、参照部３１が、文字列上を右方向に３文字分移動している。その結果、参照部３１の先頭からは「あい−」の３文字が押し出され、参照部３１の末尾に「→うし」という３文字が追加されている。なお符号化部３２も、参照部３１と同様に移動する。

図２６にはスライド窓３０の移動を論理的処理として示したが、スライド窓３０はバッファであり、実際には、バッファへの文字列の書き込みによりスライド窓３０内のデータが更新される。

図２７は、スライド窓内の文字列の更新例を示す図である。第１の符号化処理部１１１は、符号化カウンタ３３を有する。符号化カウンタ３３は、符号化された文字列の量を示すカウンタである。例えば、符号化された文字列の量がバイト数で符号化カウンタ３３に示される。符号化カウンタ３３の値を、参照部３１の長さ（データ量）で除算したときの余りの値が、参照部３１の物理領域の先頭から、参照部３１の論理的な末尾の文字の次の領域までのオフセットとなる。参照部３１の論理的な末尾の文字の次の領域は、参照部３１に次に格納する文字列の書き込み位置である。

文字列が符号化されると、符号化された文字列が、書き込み位置を先頭として、参照部３１に書き込まれる。なお書き込み位置以降に既に文字列が書き込まれている場合、符号化された文字列が上書きで書き込まれる。また符号化カウンタ３３の値は、文字列の符号化が完了するごとに、符号化された文字列分（例えばバイト数）カウントアップされる。

例えば参照部３１の長さを、８１９２バイトとする。この場合、８１９２バイト分の文字列が符号化されると、参照部３１内が文字列で満杯になる。この時点での符号化カウンタ３３の値は「８１９２」である。

この状況で、文字列「→うし」の符号化が完了したものとする。この場合、文字列「→うし」が、参照部３１の先頭に書き込まれる。また「→うし」は２バイト文字で３文字であるため、６バイト分の文字列が符号化されたこととなる。そこで符号化カウンタ３３の値は、６だけカウントアップされる。その結果、符号化カウンタ３３の値が「８１９２」から「８１９８」に更新される。

なお符号化部３２の文字列の更新も参照部３１と同様に、符号化カウンタ３３の値を用いて更新できる。
このようにして、スライド窓３０のバッファへの物理的な書き込みをサイクリックに行うことができる。その結果、スライド窓３０内の文字列の更新時の書き込みデータ量が少なくて済み、圧縮処理の高速化が図れる。また伸張時にも同様のスライド窓の制御を行うことで、伸張処理の高速化が図れる。なお第２の実施の形態においても、図２７に示した方法でスライド窓３０の文字列を更新し、圧縮・伸張処理の高速化が可能である。

図２７に示したような物理領域を有する参照部３１から最長一致文字列を検索する場合、参照部３１の論理的な先頭の文字から後方に向かって、最長一致文字列の照合が行われる。

図２８は、最長一致文字列の検索例を示す図である。なお図２８は、電子辞書のデータをスライド辞書法で符号化する場合の例であり、最長一致文字列の末端までのオフセットをアドレスとする。

図２８の例では、”『相合牛』・・・」”の文字列に対する最長一致文字列が検索され、”『相合”の３文字と一致する文字列が、２箇所検出されている。この場合、参照部３１の後方（末尾により近い方）の文字列が、最長一致文字列として検出される。

最長一致文字列を検出すると、検出された最長一文字列の末尾の文字の位置が、参照部３１の物理的な先頭からのオフセットで表される。第１の符号化処理部１１１は、最長一文字列の末尾の文字の位置の、参照部３１の物理的な先頭からのオフセットを、検出位置ポインタ３４に設定する。そして第１の符号化処理部１１１は、以下の式により、最長一致文字列のアドレスを算出する。
最長一致文字列のアドレス＝符号化カウンタの値−検出位置ポインタの値−参照部のデータ長×ｍ ・・・（１）
ここで、ｍは０以上の整数である。第１の符号化処理部１１１は、例えば「参照部のデータ長×ｍ」の値が「符号化カウンタの値−検出位置ポインタの値」より小さくなるようなｍのうちの最大値を求め、そのｍの最大値を用いて上記式（１）を計算する。

なお最長一致文字列のアドレスは、「符号化カウンタの値−検出位置ポインタの値」を「参照部のデータ長」で除算することで求めることもできる。この場合、除算したときの余りが、最長一致文字列のアドレスとなる。

例えば図２８の例では、参照部３１の論理的な先頭は、物理領域の先頭から７バイト目の文字である。そして、参照部３１の論理的な先頭の文字から８０００バイト目の”『相合”の文字が、最長一致文字列として検出されている。検出された最長一致文字列は、参照部３１の物理的な領域の末尾から１８６バイトの位置にある。また参照部３１の物理領域上では、論理的な先頭の文字の前に６バイト分の文字が存在する。すると参照部３１の論理的な末尾から最長一致文字列の末尾の文字までのオフセットは「１９２」となる。

ここで、図２８の例に示す数値を、式（１）に当てはめてみる。符号化カウンタ３３の値が「８１９８」であり、検出位置ポインタ３４の値は「８００６」である。すると「符号化カウンタの値−検出位置ポインタの値」は「１９２」となる。また参照部のデータ長は「８１９２」である。そこで「ｍ＝０」として式（１）を計算すると、最長一致文字列のアドレスが「１９２」となり、正しい結果が得られていることが分かる。

なお第２の実施の形態のように最長一致文字列の先頭までのオフセットをアドレスとする場合、最長一文字列の先頭の文字の位置を示すオフセットの値を、検出位置ポインタ３４に設定すればよい。

次に、最長一致文字列のアドレスを分解し、０近傍の複数の整数で表す手法について説明する。電子辞書のようなデータでは、第２の実施の形態のようにアドレスを「αｎ＋β」という形式にすることが難しい。そこで第４の実施の形態では、アドレスを示す整数を、整数を２進数表記したときの桁数が所定の閾値以下の下位整数と、その閾値より大きな上位整数とに区分けする。図２４、図２５に示したように、アドレスや長さの整数が、値が大きくなるほど出現頻度が低下する特性を有する場合、下位整数は上位整数よりも出現頻度が高い。そこで以下の説明では、下位整数を高頻度整数と呼び、上位整数を低頻度整数と呼ぶこととする。

図２９は、アドレスを示す整数の区分けの一例を示す図である。図２９では、横軸にアドレスを示す整数の値を示し、縦軸にアドレスを示す整数の値が出現する頻度を示している。図２９の例は、スライド窓３０の参照部３１のデータ長が８ｋ（８１９２）バイトの例である。

アドレスを示す整数の出現頻度は、整数の値が大きくなるほど低下する。参照部３１のデータ長が８ｋバイトであれば、アドレスを示す整数の最大値は８ｋ（８１９２）である。また最長一致記号列の長さについて、そこで、例えば整数「１２８」を高頻度整数の境界値とし、境界値以下の整数を高頻度整数、境界値より大きな整数を低頻度整数とする。この境界値は、アドレスの桁数の閾値の一例である。境界値「１２８」は、２進数表記における桁数の境界値「７」に等しい。

このように１〜８１９２までの整数を区分けすると、高頻度整数（１〜１２８）については７ビットで表現できる。低頻度整数（１２９〜８１９２）については、例えば上位３ビット、中位３ビット、下位７ビットの合成とみなし、３分割することができる。

図３０は、高頻度整数と低頻度整数とのビット構成の一例を示す図である。
図３０に示すように、高頻度整数は、全７ビットで表現される。低頻度整数は、１３ビットで表現される。なお、７ビットすべてが「０」の場合、アドレスを示す整数「１」を表しているものとする。すなわち７ビットで表される数値に１を加算した値を、アドレスを示す整数とする。

低頻度整数は、上位３ビット、中位３ビット、下位７ビットに分割される。このように分割した場合、以下のような特性が統計的に推定できる。
・低頻度整数の下位７ビットは、高頻度整数の全７ビットと相似した特性を持つ。
・低頻度整数の上位３ビットは、中位３ビットと相似した特性を持つ。

そこで第４の実施の形態では、第２の符号化処理部１１２は、低頻度整数の下位７ビットについては、高頻度整数と共通の符号に符号化する。また第２の符号化処理部１１２は、低頻度整数の上位３ビットについては、低頻度整数の中位３ビットと共通の符号に符号化する。このような符号化を行うことで、ハフマン木の葉の数を８１９２から１３６（１２８＋８）に減少させることができる。その結果、ハフマン木のサイズが縮小し、圧縮・伸張処理の効率化を図ることができる。

図３１は、低頻度整数を区分けした場合の圧縮・伸張回数の一例を示す図である。１２８を高頻度整数の境界値とした場合、１〜１２８の高頻度整数に関しては、高頻度整数を表す「１〜７」ビットが圧縮・伸張の対象となる。高頻度整数を表す「１〜７」ビットは、１回で圧縮・伸張が行われる。

低頻度整数のうちの「１２９〜１０２４」を表す中位３ビットおよび下位７ビットのうち、下位７ビットに関しては、高頻度整数とみなして圧縮・伸張が行われる。そこで中位３ビットに関して、個別に圧縮・伸張が行われる。従って、低頻度整数のうちの「１２９〜１０２４」については、中位３ビット・上位３ビットそれぞれの圧縮・伸張が行われ、圧縮また伸張回数は２回となる。

低頻度整数のうちの「１０２５〜８１９２」を表す全１３ビットのうち、下位７ビットに関しては、高頻度整数とみなして圧縮・伸張が行われる。そこで中位３ビット、上位３ビットに関しては、それぞれ低頻度整数のうちの「１２９〜１０２４」を表す中位３ビットとみなして個別に圧縮・伸張が行われる。従って、低頻度整数のうちの「１０２５〜８１９２」については、下位７ビット・中位３ビット・上位３ビットそれぞれの圧縮・伸張が行われ、圧縮また伸張回数は３回となる。

次に、低頻度整数を複数に区分けする場合のハフマン木の生成処理の手順について説明する。
図３２は、第４の実施の形態におけるハフマン木の生成処理の手順の一例を示す図である。以下、図３２に示す処理をステップ番号に沿って説明する。

［ステップＳ３０１］第２の符号化処理部１１２は、アドレスを示す整数と、長さを示す整数とを合わせ、各整数の出現頻度を計算する。
［ステップＳ３０２］第２の符号化処理部１１２は、低頻度整数を上位３ビット、中位３ビット、下位７ビットに分割する。

［ステップＳ３０３］第２の符号化処理部１１２は、高頻度整数の７ビットで表される１２８個の整数と、低頻度整数の中位３ビットで表される８個の整数それぞれに対応する葉を生成する。葉の構造体には、割り当てられた整数と、その整数の出現頻度が設定される。

［ステップＳ３０４］第２の符号化処理部１１２は、アドレスを示す整数と長さを示す整数とに共通のハフマン木を生成する。例えば第２の符号化処理部１１２は、高出現頻度の整数の出現頻度と、低頻度整数の中位３ビットで表される整数の出現頻度とを用いて、ハフマン木を生成する。このようになお、アドレスを示す整数と長さを示す整数とのハフマン木を共通化することで、圧縮・伸張時に使用するメモリなどの資源が少なくて済む。

［ステップＳ３０５］第２の符号化処理部１１２は、文字の２進数表記それぞれの出現頻度に基づいてハフマン木を生成する。
このようにして、アドレスと長さを符号化するためのハフマン木と、文字の２進数表記を符号化するためのハフマン木とが生成される。

第４の実施の形態では、アドレスと長さを符号化するためのハフマン木について、低頻度整数を複数に分割して、下位７ビットを高頻度整数と同様に扱う。また低頻度整数の上位３ビットは、中位３ビットと同様に扱う。これにより、葉の数を減少させ、ハフマン木の構造を簡略化することができる。ハフマン木の構造化簡略化されることで、圧縮・伸張の速度も高速化する。

またアドレスと長さとのそれぞれを示す整数のうちの低頻度整数を複数に分割したことで、ハフマン符号化を行うアドレスまたは長さを示す整数のデータ長に制限がある場合であっても、その制限が緩和される。例えばＬＺ７７符号（スライド辞書法を使用）とハフマン符号化を組み合わせた圧縮形式の１つであるＬＨＡでは、最長一致記号列の長さについて、２５６（８ビット）に制限が設けられている。上記の例では、アドレスと長さを示す整数は、分割前は１３ビットであるが、分割によって８ビット以下に抑えられている。その結果、ＬＨＡにおけるハフマン符号の際の長さの制限にかからずに済む。

なお上記の例では、低頻度整数を３つに区分けしているが、例えば低頻度整数を２つに区分けするだけでも、ハフマン木の葉の数を削減できる。
図３３は、低頻度整数を区分けする他の例を示す図である。図３３の例では、高頻度整数境界値を「２５６」としている。この場合、「１〜２５６」が高頻度整数となる。高頻度整数は全８ビットで表される。そして、８ビットで表される整数それぞれが割り当てられた２５６個の葉が生成される。

全１３ビットで表される低頻度整数は、上位５ビットと下位８ビットとに区分けされる。この場合、下位８ビットは、高頻度整数とみなして符号化できる。そこで上位５ビットの表される３２個の整数それぞれが割り当てられた３２個の葉が生成される。

以上より、生成されるハフマン木の葉の数は、「２８８」（２５６＋３２）となり、ハフマン木の葉の数が削減できることが分かる。
〔第５の実施の形態〕
次に、第５の実施の形態について説明する。第５の実施の形態は、圧縮・伸張の際にハフマン木に代えて、無節点の木を生成するものである。

無節点の木は、ハフマン木と同様に、出現頻度が高い記号（例えば文字や整数）ほど、短い符号に符号化するものである。ただし、ハフマン木は、根（ルート）の下位に複数の節点が設けられるのに対して、無節点の木では、根の下位に節点は設けられず、すべての葉が根の下位に直接接続される。このような構造の無節点の木を用いると、圧縮符号を１ビット毎ではなく、数ビットの符号単位で伸張することが可能となり、伸張速度が向上する。

無節点の木を生成する際には、例えば各整数の出現頻度に応じて、符号化時の符号長が決定される。
図３４は、整数の出現頻度と符号長との関係の一例を示す図である。図３４には、整数に関し、出現回数、出現頻度、補正確率、符号長、および圧縮符号が示されている。

例えば第２の符号化処理部１１２は、各整数の出現回数を計数し、出現頻度を求める。出現頻度は、例えばすべての整数の出現回数に対する、対応する整数の出現回数の割合である。

第２の符号化処理部１１２は、出現頻度に基づいて補正確率を求める。補正確率は、例えば、「１／２」のべき乗のうち、出現頻度以下の最も大きな数である。例えば、出現頻度「０．１３７」の場合、「１／４（０．２５）」より小さく、「１／８（０．１２５）」より大きい。そこで出現頻度「０．１３７」の補正確率は「１／８」となる。

次に第２の符号化処理部１１２は、補正確率に基づいて、符号長を求める。符号長は、符号のビット数である。例えば補正確率を「１／２」のべき乗で表したときの指数（何乗か）が、符号長とされる。補正確率「１／８」であれば、「１／２」の３乗であることから、符号長は「３」となる。

第２の符号化処理部１１２は、各整数の圧縮符号を、その整数の出現頻度に応じて決定した符号長の符号に決定する。例えば符号長が「３」であれば、圧縮符号は「０００」、符号長が「４」であれば、圧縮符号は「００１０」となる。第２の符号化処理部１１２は、アドレスや長さを示す整数を、図３４に示すような圧縮符号に符号化する。

このような整数と圧縮符号との対応関係に基づいて、無節点の木を生成することができる。例えば図３０に示すように低頻度整数を区分けした場合、葉の数は１３６個となる。すると８ビットで表すことができる。そこで符号の最大ビット数が８の場合の無節点の木の例を、図３５を参照して説明する。

図３５は、無節点の木の一例を示す図である。無節点の木５０には、根５１と複数の葉５２ａ，５２ｂ，５２ｃ，・・・５２ｍ，５２ｎが設けられている。根５１の直下に葉５２ａ，５２ｂ，５２ｃ，・・・５２ｍ，５２ｎが設けられており、ハフマン木にあるような節は存在しない。ここで葉５２ａ，５２ｂ，５２ｃ，・・・５２ｍ，５２ｎそれぞれの識別番号を、左から順に１，２，３，・・・とする。

根の構造体６１には、８ビットで表せるアドレスに対応する各領域に、葉５２ａ，５２ｂ，５２ｃ，・・・５２ｍ，５２ｎへのポインタが設定されている。葉の構造体６２には、例えば対応する葉５２ａの識別番号、圧縮符号長、圧縮符号、整数（圧縮される記号）などが設定されている。

ここで根の構造体６１においては、圧縮符号長が少ない葉ほど、多くのポインタが設定される。例えば葉５２ａの圧縮符号長は「３」、圧縮符号は「０００」である。この場合、根の構造体の葉５２ａに対しては、「００００００００」〜「０００１１１１１」のアドレス範囲のすべての領域に、葉５２ａへのポインタが設定される。

このような無節点の木５０によれば、復号を符号単位で行うことができる。例えば第１の復号処理部１３１は、復号対象の符号列の先頭の８ビットの値を取得し、根の構造体６１の先頭から、取得した値をオフセットとした領域に格納されているポインタを参照する。次に第１の復号処理部１３１は、参照したポインタで示されている葉の構造体を参照する。そして第１の復号処理部１３１は、取得した８ビットのうち、参照した葉の構造体に示されている圧縮符号長で示されるビット数の先頭のビットを、参照した葉の構造体に示されている整数に復号する。その後、第１の復号処理部１３１は、復号していない符号列の先頭８ビットを再度取得し、同様に復号する。

例えば、取得した８ビットの値が「０００００１１１」であれば、対応するオフセットの領域が参照される。その領域には、葉５２ａに対応する葉の構造体６２へのポインタが設定されている。葉の構造体６２には、圧縮符号長が「３」であること、整数「１」に復号することが示されている。そこで、第１の復号処理部１３１は、８ビットの値「０００００１１１」のうちの先頭の３ビット「０００」を整数「１」に復号する。

このように、無節点の木５０を用いて復号することで、ハフマン木を用いた復号のように、根からの節点を辿るための複数の判断が不要となり、根５１から１パスで目的の葉を検出し、復号することができる。すなわち無節点の木５０により、圧縮データを１ビットごとでなく、８ビットをまとめた１回の判定で、葉の構造体を獲得するができる。これにより、圧縮された符号を高速に伸長することができる。

〔その他の実施の形態〕
上記の各実施の形態に示した処理機能をコンピュータ１００によって実現するために、各実施の形態に示した処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。なおプログラムを記録する記録媒体には、一時的な伝搬信号自体は含まれない。

プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。

プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。

また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。

以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。

１，２ 情報処理装置
１ａ 第１の符号化手段
１ｂ 第２の符号化手段
１ｃ 中間符号列
２ａ 第１の復号手段
２ｂ 第２の復号手段
２ｃ 中間符号列
３ 元ファイル
４ 記録媒体
４ａ 圧縮ファイル
５ バッファ

Claims (14)

1. 符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索し、
   符号化が終了した記号列の末尾から該最長一致記号列の末尾までの距離を示す整数を、該最長一致記号列のアドレスとし、該最長一致記号列に対応する、符号化が行われていない記号列の先頭の記号列を、該アドレスを示す整数と該最長一致記号列の長さを示す整数とに符号化し、
   該最長一致記号列のアドレスを示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）を求め、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式に変換し、αとβとの値および長さを示す整数を、出現頻度が高いほど短い符号となるように符号化する、
   処理をコンピュータに実行させるプログラム。
2. 最長一致記号列の検索では、検索対象の記号列をバッファに格納し、記号列の符号化が終了するごとに、符号化が終了した記号列を、該バッファ内の最先に符号化された記号列の位置に上書きで書き込む、
   処理をコンピュータに実行させる請求項１記載のプログラム。
3. 最長一致記号列の検索では、符号化された記号数を示すカウンタの値から、前記バッファの先頭から最長一致記号列の位置までのオフセットと、前記バッファの記憶容量の整数倍とを減算した結果を、該最長一致記号列のアドレスとする、
   処理をコンピュータに実行させる請求項２記載のプログラム。
4. 符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索し、
   符号化が終了した記号列の末尾から該最長一致記号列までの距離を示す整数を、該最長一致記号列のアドレスとし、該最長一致記号列に対応する、符号化が行われていない記号列の先頭の記号列を、該アドレスを示す整数と該最長一致記号列の長さを示す整数とに符号化し、
   該最長一致記号列のアドレスを示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）を求め、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式に変換し、αとβとの値および長さを示す整数を、出現頻度が高いほど短い符号となるように符号化する、
   処理をコンピュータに実行させるプログラム。
5. 符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索し、
   符号化が終了した記号列の末尾から該最長一致記号列までの距離を示す整数を、該最長一致記号列のアドレスとし、該最長一致記号列に対応する、符号化が行われていない記号列の先頭の記号列を、該アドレスを示す整数と該最長一致記号列の長さを示す整数とに符号化し、
   該最長一致記号列のアドレスを示す整数を、桁数が閾値以下の値の下位整数と、前記閾値より大きい値の上位整数とに分け、上位整数を前記閾値以下の桁で表される整数と前記閾値より上の桁で表される整数とに分離し、符号化に用いる符号の木の葉として、前記閾値以下の桁で表される整数それぞれに対応する葉と、上位整数の前記閾値より上の桁で表される整数それぞれに対応する葉とを生成し、生成された葉それぞれに対応する整数の出現頻度に応じて符号の木を生成し、該符号の木を用い、出現頻度が高い整数ほど短い符号となるように、アドレスを示す整数と長さを示す整数を符号化する、
   処理をコンピュータに実行させるプログラム。
6. 整数の符号化では、最長一致記号列のアドレスを示す整数と、最長一致記号列の長さを示す整数とに共通の符号の木を生成し、該符号の木を用いて整数を符号化する、
   処理をコンピュータに実行させる請求項１乃至５のいずれかに記載のプログラム。
7. 符号化が終了した記号列の書き込みでは、符号化された記号数を示すカウンタの値を前記バッファに格納可能な記号数で除算し、前記バッファの先頭から該除算の余りで示された距離の位置に、符号化が終了した記号列を上書きで書き込み、該記号列の記号数分だけ該カウンタの値をカウントアップする、
   処理をコンピュータに実行させる請求項２または３記載のプログラム。
8. 符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索したときに、該最長一致記号列のアドレスを示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）に基づいて、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式で表したときのαとβとの値、および長さを示す整数を含む中間符号を、出現頻度が高い整数ほど短い符号に符号化することで得られた符号が、符号列に含まれており、該符号列の先頭から順に、符号を中間符号に復号し、
   以前に得られた中間符号の復号により既に得られている記号列の末尾から、新たに得られた中間符号のアドレスを示す整数に応じた距離にある記号を特定し、該記号を末尾とする記号列であり、該中間符号の長さを示す整数分の長さの該記号列を取得し、該中間符号を該取得した記号列に復号する、
   処理をコンピュータに実行させるプログラム。
9. 符号の復号では、復号に用いる符号の木として、根の直下にすべての葉が接続された無節点の木を用いる、
   処理をコンピュータに実行させる請求項８記載のプログラム。
10. コンピュータが、
    符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索し、
    符号化が終了した記号列の末尾から該最長一致記号列の末尾までの距離を示す整数を、該最長一致記号列のアドレスとして、該最長一致記号列に対応する、符号化が行われていない記号列の先頭の記号列を、該アドレスを示す整数と該最長一致記号列の長さを示す整数とに符号化し、
    該最長一致記号列のアドレスを示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）を求め、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式に変換し、αとβとの値および長さを示す整数を、出現頻度が高いほど短い符号となるように符号化し、
    整数の符号化によって得られた符号を含む圧縮ファイルを生成する、
    ことを特徴とする圧縮ファイル生成方法。
11. コンピュータが、
    符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索したときに、該最長一致記号列のアドレスを示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）に基づいて、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式で表したときのαとβとの値、および長さを示す整数を含む中間符号を、出現頻度が高い整数ほど短い符号に符号化することで得られた符号が、符号列に含まれており、該符号列の先頭から順に、符号を中間符号に復号し、
    以前に得られた中間符号の復号により既に得られている記号列の末尾から、新たに得られた中間符号のアドレスを示す整数に応じた距離にある記号を特定し、該記号を末尾とする記号列であり、該中間符号の長さを示す整数分の長さの該記号列を取得し、該中間符号を該取得した記号列に復号する、
    ことを特徴とする圧縮符号伸張方法。
12. 符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索し、符号化が終了した記号列の末尾から該最長一致記号列の末尾までの距離を示す整数を、該最長一致記号列のアドレスとして、該最長一致記号列に対応する、符号化が行われていない記号列の先頭の記号列を、該アドレスを示す整数と該最長一致記号列の長さを示す整数とに符号化する第１の符号化手段と、
    該最長一致記号列のアドレスを示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）を求め、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式に変換し、αとβとの値および長さを示す整数を、出現頻度が高いほど短い符号となるように符号化する第２の符号化手段と、
    を有することを特徴とする情報処理装置。
13. 符号化が終了した記号列の末尾から所定の範囲内の記号列を検索対象として、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列を検索したときに、該最長一致記号列のアドレスを示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）に基づいて、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式で表したときのαとβとの値、および長さを示す整数を含む中間符号を、出現頻度が高い整数ほど短い符号に符号化することで得られた符号が、符号列に含まれており、該符号列の先頭から順に、符号を中間符号に復号する第１の復号手段と、
    以前に得られた中間符号の復号により既に得られている記号列の末尾から、新たに得られた中間符号のアドレスを示す整数に応じた距離にある記号を特定し、該記号を末尾とする記号列であり、該中間符号の長さを示す整数分の長さの該記号列を取得し、該中間符号を該取得した記号列に復号する第２の復号手段と、
    を有することを特徴とする情報処理装置。
14. 圧縮ファイルを記憶するコンピュータ読み取り可能な記録媒体において、
    前記圧縮ファイルには、出現頻度が高い整数ほど短い符号となるように、整数を符号化した圧縮符号が含まれており、
    前記圧縮ファイルに含まれる圧縮符号の元となる整数には、符号化が終了した記号列の末尾から所定の範囲内の記号列のうち、符号化が行われていない記号列の先頭の記号列に対して最も長く一致する最長一致記号列の末尾のアドレスを示す整数と、該最長一致記号列の長さを示す整数とが含まれており、
    最長一致記号列のアドレスを示す整数は、符号化が終了した記号列の末尾から所定の範囲内の記号列の末尾から該最長一致記号列までの距離を示す整数の出現頻度が高くなる周期ｎ（ｎは１以上の整数）に基づいて、最長一致記号列のアドレスをαｎ±β（αは１以上の整数、βは０以上の整数）の形式で表したときのαとβとの値である、
    ことを特徴とする記録媒体。
    

Images