(57)【特許請求の範囲】
【請求項１】
コンピュータに、
あるデータに対して最長一致文字列検索をおこない、検索された最長一致文字列のうち所定長未満となる第１データそれぞれの出現頻度と、最長一致文字列のうち前記所定長以上となる第２データの位置情報それぞれの出現頻度とを基にして、圧縮符号、第１識別情報および前記第１データをそれぞれ対応付けた情報と、前記圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を生成し、
圧縮対象のデータに対して最長一致文字列検索をおこない、最長一致文字列が前記所定長未満の場合には、前記頻度情報に含まれる第１データのうち、前記最長一致文字列の第１データに対応付けられた圧縮符号を出力し、
前記最長一致文字列が前記所定長以上の場合には、前記頻度情報に含まれる第２データの位置情報のうち、前記最長一致文字列の位置情報と一致する位置情報に対応付けられた圧縮符号、および、前記頻度情報に含まれる第１データのうち最長一致文字列の長さの情報に対応付けられた圧縮符号を出力する
各処理を実行させることを特徴とする圧縮プログラム。
【請求項２】
前記頻度情報を生成する処理は、前記第１データおよび該第１データの出現頻度と、スライド窓の先頭から前記第２データまでの位置情報を縮約した情報および前記位置情報の出現頻度とを含むハフマン木を生成することを特徴とする請求項１に記載の圧縮プログラム。
【請求項３】
前記頻度情報を生成する処理は、前記スライド窓の先頭から前記第２データが出現するまでの位置をｎビット固定長で表現した場合における先頭ビットから１または０が連続する数を示す連続数を、前記縮約した情報として前記ハフマン木の葉に格納することを特徴とする請求項２に記載の圧縮プログラム。
【請求項４】
前記圧縮対象のデータから出力される圧縮ファイルの一部に、前記ハフマン木に対応した出現頻度情報を含むことを特徴とする請求項２に記載の圧縮プログラム。
【請求項５】
コンピュータが実行する圧縮方法であって、
あるデータに対して最長一致文字列検索をおこない、検索された最長一致文字列のうち所定長未満となる第１データそれぞれの出現頻度と、最長一致文字列のうち前記所定長以上となる第２データの位置情報それぞれの出現頻度とを基にして、圧縮符号、第１識別情報および前記第１データをそれぞれ対応付けた情報と、前記圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を生成し、
圧縮対象のデータに対して最長一致文字列検索をおこない、最長一致文字列が前記所定長未満の場合には、前記頻度情報に含まれる第１データのうち、前記最長一致文字列の第１データに対応付けられた圧縮符号を出力し、
前記最長一致文字列が前記所定長以上の場合には、前記頻度情報に含まれる第２データの位置情報のうち、前記最長一致文字列の位置情報と一致する位置情報に対応付けられた圧縮符号、および、前記頻度情報に含まれる第１データのうち、最長一致文字列の長さの情報に対応付けられた圧縮符号を出力する
各処理を実行することを特徴とする圧縮方法。
【請求項６】
あるデータに対して最長一致文字列検索をおこない、検索された最長一致文字列のうち所定長未満となる第１データそれぞれの出現頻度と、最長一致文字列のうち前記所定長以上となる第２データの位置情報それぞれの出現頻度とを基にして、圧縮符号、第１識別情報および前記第１データをそれぞれ対応付けた情報と、前記圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を生成する生成部と、
圧縮対象のデータに対して最長一致文字列検索をおこない、最長一致文字列が前記所定長未満の場合には、前記頻度情報に含まれる第１データのうち、前記最長一致文字列の第１データに対応付けられた圧縮符号を出力し、前記最長一致文字列が前記所定長以上の場合には、前記頻度情報に含まれる第２データの位置情報のうち、前記最長一致文字列の位置情報と一致する位置情報に対応付けられた圧縮符号、および、前記頻度情報に含まれる第１データのうち、最長一致文字列の長さの情報に対応付けられた圧縮符号を出力する符号化部と
を有することを特徴とする圧縮装置。
【請求項７】
コンピュータに、
入力した圧縮ファイルの一部から、所定長未満となる第１データの出現頻度と、各最長一致文字列のうち前記所定長以上となる第２データの位置情報の出現頻度とを基にして生成された、圧縮符号、第１識別情報および前記第１データを対応付けた情報と、前記圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を取得し、
前記圧縮ファイルからデータを読み出し、読み出したデータと前記頻度情報とを基にして、伸長データを生成する、
処理を実行させることを特徴とする伸長プログラム。
【請求項８】
前記第１データおよび出現頻度と、前記位置情報の出現頻度とを構造に反映した、前記第１データまたは前記位置情報を葉に含むハフマン木を、前記頻度情報より生成可能であり、
前記ハフマン木の前記第１データを含む葉には第１識別子が格納され、前記位置情報を含む葉には第２識別子が格納されており、
前記伸長データを生成する処理は、伸長対象のデータを読み出して前記ハフマン木を辿り、データに対応する前記ハフマン木の葉を特定し、特定したハフマン木の葉に第１識別情報が含まれているか第２識別情報が含まれているかを判定し、
第１識別子が含まれている場合には、葉に含まれるデータを出力し
第２識別子が含まれている場合には、葉に含まれる位置情報に基づいてデータを出力することを特徴とする請求項７に記載の伸長プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、圧縮プログラム等に関する。
【背景技術】
【０００２】
データに対して最長一致文字列検索をおこない、データの出現頻度に応じて、データを圧縮する技術がある。例えば、ＺＩＰは、１段目にＬＺ７７系圧縮行い、２段目にハフマン圧縮を行う圧縮技術である。
【０００３】
１段目のＬＺ７７系圧縮では、変換データに対してスライド窓を設け、スライド窓で最長一致文字列探索を行う。そして、ＬＺ７７系圧縮は、最長一致文字列検索の結果に応じて、圧縮符号に文字、または、文字列に対する識別ビットを設け、圧縮符号化を行う。以下の説明では、最長一致文字列検索によって得られるデータを、最長一致データと表記する。
【０００４】
例えば、スライド窓で最長一致文字列検索を行った結果、最長一致データが３バイト未満の場合には、識別ビット「０」と、１バイトの文字コードとを対応付けたものを、圧縮符号として出力する。これに対して、最長一致データが３バイト以上の場合には、識別ビット「１」と、最長一致データのスライド窓の位置と長さとを対応付けたものを、圧縮符号として出力する。
【０００５】
２段目のハフマン圧縮では、文字の出現頻度に応じたハフマン木を生成し、識別ビット「０」の１バイトの文字コードにハフマン符号を割り当てる。また、識別ビット「１」に対して最長一致文字列の長さを圧縮符号として割り当てる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００４−５１４３６６号公報
【特許文献２】特開平８−２８８８６１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では、圧縮符号に識別ビットが含まれるため、圧縮率が低下するという問題がある。
【０００８】
１つの側面では、圧縮率が低下することを防止することができる圧縮プログラム、圧縮方法、圧縮装置および伸長プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
第１の案では、コンピュータに下記の処理を実行させる。コンピュータに、圧縮対象のデータに対して最長一致文字列検索をおこなわせる。コンピュータに、検索された最長一致文字列の第１データそれぞれの出現頻度と、最長一致文字列のうち所定長以上となる第２データそれぞれの位置情報の出現頻度とを基にして、圧縮符号、第１識別情報および前記第１データをそれぞれ対応付けた情報と、圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を生成させる。コンピュータに、圧縮対象のデータに対して最長一致文字検索をおこなわせる。コンピュータに、最長一致文字列が所定長未満の場合には、頻度情報に含まれる第１データのうち、最長一致文字列の第１データに対応付けられた圧縮符号を出力させる。コンピュータに、最長一致文字列が所定長以上の場合には、頻度情報に含まれる第２データの位置情報のうち、最長一致文字列の位置情報に対応付けられた圧縮符号、および、頻度情報に含まれる第１データのうち、最長一致文字列の長さ情報に対応付けられた圧縮符号を出力させる。
【発明の効果】
【００１０】
本発明の１実施態様によれば、圧縮率が低下することを防止することができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、ハフマン木の参考例を示す図である。
【図２】図２は、ＬＺ７７を利用した圧縮処理の参考例を説明する図である。
【図３】図３は、ＬＺ７７を利用した伸長処理の参考例を説明する図である。
【図４】図４は、情報処理装置の構成の参考例を示す機能ブロック図である。
【図５】図５は、圧縮部の構成の参考例を示す機能ブロック図である。
【図６】図６は、頻度表のデータ構造の参考例を示す図である。
【図７】図７は、伸長部の構成の参考例を示す機能ブロック図である。
【図８】図８は、参考例の問題を説明するための図である。
【図９】図９は、拡張ハフマン木の一例を示す図である。
【図１０】図１０は、本実施例１に係る圧縮処理を説明する図である。
【図１１】図１１は、本実施例１に係る伸長処理を説明する図である。
【図１２】図１２は、本実施例１に係る情報処理装置の構成を示す図である。
【図１３】図１３は、本実施例１に係る圧縮部の構成を示す機能ブロック図である。
【図１４】図１４は、拡張した頻度表のデータ構造の一例を示す図である。
【図１５】図１５は、圧縮部の第２符号化部の処理を説明するための図である。
【図１６】図１６は、本実施例に係る伸長部の構成を示す機能ブロック図である。
【図１７】図１７は、第２伸長部の処理を説明するための図である。
【図１８】図１８は、本実施例１に係る圧縮部の処理手順を示すフローチャートである。
【図１９】図１９は、頻度表および拡張ハフマン木を生成する処理手順を示すフローチャートである。
【図２０】図２０は、圧縮データを生成する処理手順を示すフローチャートである。
【図２１】図２１は、本実施例１に係る伸長部の処理手順を示すフローチャートである。
【図２２】図２２は、葉に含まれる０の連続数を基に、最長一致文字列の位置および長さを特定する処理手順を示すフローチャートである。
【図２３】図２３は、拡張ハフマン木の一例を示す図（２）である。
【図２４】図２４は、本実施例２に係る圧縮処理を説明する図である。
【図２５】図２５は、本実施例２に係る伸長処理を説明する図である。
【図２６】図２６は、本実施例２に係る情報処理装置の構成を示す図である。
【図２７】図２７は、本実施例２に係る圧縮部の構成を示す機能ブロック図である。
【図２８】図２８は、拡張した頻度表のデータ構造の一例を示す図（２）である。
【図２９】図２９は、圧縮部の第２符号化部の処理を説明するための図（２）である。
【図３０】図３０は、本実施例２に係る伸長部の構成を示す機能ブロック図である。
【図３１】図３１は、第２伸長部の処理を説明するための図（２）である。
【図３２】図３２は、頻度表および拡張ハフマン木を生成する処理手順を示すフローチャート（２）である。
【図３３】図３３は、圧縮データを生成する処理手順を示すフロートチャート（２）である。
【図３４】図３４は、本実施例２に係る伸長部の処理手順を示すフローチャートである。
【図３５】図３５は、コンピュータのハードウェア構成例を示す図である。
【図３６】図３６は、コンピュータで動作するプログラムの構成例を示す図である。
【図３７】図３７は、実施形態のシステムにおける装置の構成例を示す図である。
【発明を実施するための形態】
【００１２】
以下に、本願の開示する圧縮プログラム、圧縮方法、圧縮装置および伸長プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００１３】
本願発明の実施例１を説明する前に、ＬＺ７７を利用した圧縮技術および伸長技術の参考例について説明する。
【００１４】
ＬＺ７７を利用した圧縮技術の参考例について説明する。まず、参考例では、圧縮対象となるファイルＦ１を参照し、データの出現頻度を集計する。参考例では、データの出現頻度の集計結果を基にしてハフマン木を生成する。なお、以下の参考例・本実施例では、説明の便宜上、文字列を圧縮する場合について説明しているが、圧縮対象となるものは「データ」であり、文字列に限られるものではない。すなわち、圧縮対象のデータが文字列のように文字の区切りを有していないデータ、例えば、０または１が並んだデータに対しても圧縮・伸長を行うことが出来る。
【００１５】
図１は、ハフマン木の参考例を示す図である。図１に示すハフマン木１０は、最上位に根ノード１１を有し、各節点１２−１〜が枝によって接続され、各最下位に葉１０−１〜１０−２５６を有する。各節点のデータ構造は、１０ａに示すものとなる。基本的に、上位の節点と下位の左と右の節点への３種のポインタが格納される。下位の枝と節点が無い場合は、葉のデータが格納される。また、各葉のデータ構造は、１０ｂに示すものとなる。例えば、葉には、葉の識別子と、予備情報と、文字コードまたは最長一致文字列の長さとが格納される。各葉は、葉に格納された文字コードの出現頻度の順に並んでおり、出現頻度の高い文字コードに対して、短い圧縮データが割り当てられる。参考例のハフマン木は２５６個の葉を有する。なお、参考例・実施例では、説明の便宜上、圧縮対象と文字列としているため、葉には、葉の識別子と、予備情報と、文字コードまたは最長一致文字列の長さとが格納されているが、圧縮対象が「データ」である場合には、文字コードの代わりに、伸長後のデータが格納される。
【００１６】
図２は、ＬＺ７７を利用した圧縮処理の参考例を説明する図である。図１に示したハフマン木を生成した後に、図２に示す圧縮処理を実行する。まず、記憶領域Ａ１、記憶領域Ａ２および記憶領域Ａ３が例えばメモリ内に確保される。図２に示すファイルＦ１内のコンテンツ部分のデータは、記憶領域Ａ１にリードされる。記憶領域Ａ１は、例えば符号化部などと呼ばれる。ファイルＦ１は、「ｈｅ・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ  ｈｏｒｓｅ・・・３ｒｄ  ｈｏｒｓｅ・・・」というデータが含まれる（「・・・」は不特定な文字列である）。なお、図２の「ｈｏｒｓｅ」に示す三角、マル、四角の記号は、説明の便宜上、視覚的に各「ｈｏｒｓｅ」を区別するためのものであり、実際のファイルＦ１には含まれない。
【００１７】
記憶領域Ａ１にリードされたデータに基づいて、圧縮データの生成処理が行なわれる。また、圧縮データの生成処理が行なわれたデータは、記憶領域Ａ１から記憶領域Ａ２にコピーされる。記憶領域Ａ２は、例えば参照部と呼ばれる。圧縮データは、記憶領域Ａ１にリードされたデータと記憶領域Ａ２内のデータとの照合処理の結果に応じて生成される。生成された圧縮データは順次記憶領域Ａ３に格納され、記憶領域Ａ３に格納された圧縮データに基づいて圧縮ファイルＦ２が生成される。また、図２において、記憶領域Ａ１およびＡ２内のデータは模式的に示されている。
【００１８】
図２に示される「１ｓｔ  ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである場合を例に圧縮データｄ１の生成を説明する。まず、記憶領域Ａ２内で「ｈｏｒｓｅ・・・」の最長一致データが探索される（図２に示す「照合」）。図１の例では「ｈｅ・・・１ｓｔ」が存在するので、「ｈ」が記憶領域Ａ２内で処理対象データと最も長く一致するデータの部分（最長一致文字列）となる。参考例では、最長一致文字列のデータ量が３バイト未満の場合には、１バイト毎の文字と、ハフマン木１０とを比較して、それぞれの文字のハフマン符号を特定し、圧縮データｄ１が生成される。圧縮データｄ１には、ハフマン符号に加えて、文字をハフマン符号化したことを示す識別子「０」が含まれる。
【００１９】
図２に示される「２ｎｄ  ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである場合を例に圧縮データｄ２の生成を説明する。まず、記憶領域Ａ２内で「ｈｏｒｓｅ・・・」の最長一致データが探索される（図１に示す「照合」）。図１の例では、「１ｓｔ  ｈｏｒｓｅ・・・」が記憶領域Ａ２に存在するので、例えば、処理対象のデータの「ｈｏｒｓｅ」と記憶領域Ａ２内の「１ｓｔ  ｈｏｒｓｅ・・・」の「ｈｏｒｓｅ」とが一致する。例えば、記憶領域Ａ２内の一致データ「ｈｏｒｓｅ」が、最長一致文字列となる。最長一致文字列のデータ量が３バイト以上の場合には、最長一致文字列の記憶領域Ａ２内での位置と、最長一致文字列のデータ長に基づき圧縮データｄ２が生成される。例えば、「ｈｏｒｓｅ」の位置と、「ｈｏｒｓｅ」の長さとが、圧縮データｄ２に格納される。なお、「ｈｏｒｓｅ」の長さの情報は、ハフマン木１０に基づき圧縮される。圧縮データｄ２には、最長一致文字列の位置および長さに基づく圧縮データである旨を示す識別子「１」が含まれる。
【００２０】
図２に示される「３ｒｄ  ｈｏｒｓｅ・・・」の「ｈ」以降が処理対象のデータである場合を例に圧縮データｄ３の生成を説明する。まず、記憶領域Ａ２内で「ｈｏｒｓｅ・・・」の最長一致データが探索される（図１に示す「照合」）。図２の例では、「１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ  ｈｏｒｓｅ」が記憶領域Ａ２に存在するので、例えば、処理対象のデータの「ｈｏｒｓｅ」と記憶領域Ａ２内の「１ｓｔ  ｈｏｒｓｅ」および「２ｎｄ  ｈｏｒｓｅ」の「ｈｏｒｓｅ」とが一致する。例えば、記憶領域Ａ２内の「１ｓｔ  ｈｏｒｓｅ」または「２ｎｄ  ｈｏｒｓｅ」のいずれか「ｈｏｒｓｅ」が最長一致文字列となる。最長一致文字列のデータ量が３バイト以上の場合には、最長一致文字列の記憶領域Ａ２内での位置と、最長一致文字列のデータ長に基づき圧縮データｄ３が生成される。例えば、「ｈｏｒｓｅ」の位置と、「ｈｏｒｓｅ」の長さとが、圧縮データｄ３格納される。なお、「ｈｏｒｓｅ」の長さの情報は、ハフマン木１０に基づき圧縮される。圧縮データｄ３には、最長一致文字列に基づく圧縮データである旨を示す識別子「１」が含まれる。
【００２１】
図３は、ＬＺ７７を利用した伸長処理の参考例を説明する図である。伸張処理においては、圧縮ファイルＦ２内の圧縮データをメモリ（記憶領域Ｂ１）にロードし、ロードされた圧縮データの識別子に応じて伸長データの生成処理を行なう。図３の「＊」は圧縮されたデータであることを示す。記憶領域Ｂ１は、例えば符号化部などと呼ばれる。最長一致文字列に基づく圧縮データでない旨を示す識別子「０」を含む圧縮データ（図２における圧縮データｄ１）を読み出した場合には、圧縮データのハフマン符号とハフマン木１０とを比較し、圧縮データに対応するハフマン木１０の葉を特定し、特定した葉に格納された文字コードを、伸長データして生成する。生成された伸長データは、記憶領域Ｂ２および記憶領域Ｂ３の双方に格納される。記憶領域Ｂ２は、例えば参照部などと呼ばれる。
【００２２】
一方、最長一致文字列に基づく圧縮データである旨を示す識別子「１」を含む圧縮データ（図２における圧縮データｄ２および圧縮データｄ３など）を読み出した場合には、圧縮データに示される記憶領域Ｂ２内のデータが伸長データとなる。圧縮データには、伸長データの位置と、伸長データの長さが格納されている。また、伸長データの長さは、ハフマン木１０に基づいてハフマン符号化されている。このため、圧縮データに格納されたハフマン符号と、ハフマン木とを比較して、対応するハフマン木１０の葉を特定し、伸長データの長さを得る。
【００２３】
例えば、圧縮データｄ２には、識別子「１」と、「ｈｏｒｓｅ」の位置と、「ｈｏｒｓｅ」の長さが格納されているが、このうち、「ｈｏｒｓｅ」の長さの情報は、ハフマン木１０によってハフマン符号化されている。このため、圧縮された「ｈｏｒｓｅ」の長さのハフマン符号とハフマン木１０とを比較して、葉を特定する。特定した葉には、復号後の「ｈｏｒｓｅ」の長さの情報が格納されている。そして、記憶領域Ｂ２の先頭位置からの位置および長さに対応する記憶領域Ｂ２内のデータ「ｈｏｒｓｅ」を伸長データとして生成する。生成された伸長データは、記憶領域Ｂ２および記憶領域Ｂ３の双方に格納される。
【００２４】
なお、上記の例では、説明の便宜上、文字列を用いて最長一致文字列検索を行う場合について説明したが、圧縮対象が「データ」の場合には、記憶領域Ｂ１に格納されたデータと、記憶領域Ｂ２に格納されたデータとの間で、最長一致文字列の検索が行われる。そして、一致するデータのうち、最長のデータが最長一致文字列として検出される。この最長一致文字列は、０または１が連続するデータとなる。
【００２５】
図４は、情報処理装置の構成の参考を示す機能ブロック図である。図４に示すように、この情報処理装置１００は、圧縮部１００ａと、伸長部１００ｂと、記憶部１００ｃとを有する。圧縮部１００ａは、図２に示した圧縮処理を実行する処理部である。伸長部１００ｂは、図３に示した伸長処理を実行する処理部である。記憶部１００ｃは、圧縮対象のファイルＦ１、圧縮処理により得られる圧縮ファイルＦ２、ファイルＦ２を伸長して得られるファイルＦ３などを媒介する。
【００２６】
図５は、圧縮部の構成の参考例を示す機能ブロック図である。図５に示すように、圧縮部１００ａは、第１段階処理部１２０ａと第２段階処理部１２０ｂとを有する。第１段階処理部１２０ａは、参照部文字リード部１０１、文字頻度集計部１０２、頻度表生成部１０３、ハフマン木生成部１０４を有する。第２段階処理部１２０ｂは、ファイルリード部１０５、最長一致文字列検索部１０６、第１符号化部１０７、第２符号化部１０８、識別ビット生成部１０９、参照部更新部１１０、ファイルライト部１１１を有する。
【００２７】
第１段階処理部１１０ａは、文字コードの出現頻度を集計し、ハフマン木を作成する処理部である。第１段階処理部１１０ａに含まれる各部について説明する。
【００２８】
参照部文字リード部１０１は、所定の記憶領域に圧縮対象となるファイルＦ１のコンテンツ部分を読み出す処理部である。ここでは、所定の記憶領域を記憶領域Ａ４とする。例えば、記憶領域Ａ４は、記憶部１００ｃに存在するものとする。参照部文字リード部１０１は、記憶領域Ａ４に読み出したファイルＦ１に対する集計処理が完了する度に、新たなファイルＦ１のコンテンツ部分を読み出して、記憶領域の情報を更新する。
【００２９】
文字頻度集計部１０２は、参照部文字リード部１０１によって記憶領域Ａ４に読み出されたコンテンツを参照し、データの出現頻度を集計する処理部である。文字頻度集計部１０２は、集計結果を頻度表生成部１０３に出力する。文字頻度集計部１０２は、記憶領域Ａ４の情報が更新される度に、データの出現回数を計数する。例えば、文字頻度集計部１０２は、全てのデータの出現回数と、各データの出現回数とを基にして、データの出現頻度を集計する。ここでは説明の便宜上、文字コードを用いて説明する。
【００３０】
頻度表生成部１０３は、文字頻度集計部１０２から取得する各データの出現頻度の集計結果を基にして、頻度表を生成する処理部である。図６は、頻度表のデータ構造の参考例を示す図である。図６に示すように、この頻度表２０は、文字コード、または、最長一致データの長さに関する識別番号と、その出現頻度とを対応付ける。頻度表２０は、２５６のレコードを有する。頻度表生成部１０３は、頻度表２０の情報を、ハフマン木生成部１０４に出力する。
【００３１】
ハフマン木生成部１０４は、頻度表２０を基にしてハフマン木を生成する処理部である。ハフマン木生成部１０４は、２５６個の葉の構造体を作成し、各葉の構造体に「文字コード（データ）」と、該文字コード（データ）の「出現頻度」を割り当てる。なお、ハフマン木生成部１０４は、識別番号と、データとの対応関係を示すテーブルを保持しているものとする。
【００３２】
ハフマン木生成部１０４は、葉の構造体をその文字コードの出現頻度の順にソートし、出現頻度に応じて、２分木の「枝」をくみ上げ、上位に向かって、２分木の枝をくみ上げていくことで、ハフマン木を生成する。例えば、ハフマン木は、図１に示したハフマン木１０に対応する。ハフマン木生成部１０４は、ハフマン木１０の各葉に、葉の識別子と、文字コード（データ）または最長一致文字列の長さをそれぞれ格納する。また、上位へのポインタ、下位の左と右へのポインタに対応する節点のアドレスを格納する。
【００３３】
第２段階処理部１２０ｂは、図２で説明したように、ファイルＦ１を圧縮する処理部である。第２段階処理部１２０ｂに含まれる各部の処理について説明する。
【００３４】
ファイルリード部１０５は、ファイルＦ１内のコンテンツ部分のデータを、符号化部に対応する記憶領域Ａ１に読み出す処理部である。ファイルリード部１０５は、記憶領域Ａ１に格納されたデータに対する処理が終了し、記憶領域Ａ１のデータが参照部である記憶領域Ａ２に移行し、圧縮符号が格納された記憶領域Ａ３のデータを圧縮ファイルＦ２へ書き込んだ後に、新たなデータをファイルＦ１から読み出し、記憶領域Ａ１に格納されたデータを更新する。
【００３５】
最長一致文字検索部１０６は、参照部となる記憶領域Ａ２に格納されたデータと、記憶領域Ａ１に格納されたデータとを比較して、最長一致文字列を検索する処理部である。最長一致文字列を検索する処理は、図２に示した処理と同様である。最長一致文字探索部１０６は、最長一致文字列の情報を、第１符号部１０７、第２符号部１０８、識別ビット生成部１０９に出力する。
【００３６】
第１符号化部１０７は、最長一致文字列のデータ量が３バイト未満の場合に処理を行う。第１符号化部１０７は、最長一致文字列のデータ量が３バイト未満の場合に、それぞれ、１バイトの文字コード、または、データの２進数表現と、ハフマン木１０とを比較して、ハフマン符号を特定する。第１符号化部１０７は、ハフマン符号と、識別ビット生成部１０９から取得する識別ビットとを合わせた圧縮データを、記憶領域Ａ３に格納し、ファイルライト部１１１に出力する。
【００３７】
第２符号化部１０８は、最長一致文字列のデータ量が３バイト以上の場合に処理を行う。第２符号化部１０８は、最長一致文字列のデータ量が３バイト以上の場合に、最長一致文字列の記憶領域Ａ２での先頭からの位置と、最長一致文字列の一致長を特定する。第２符号化部１０８は、最長一致文字列の一致長とハフマン木１０とを比較して、一致長のハフマン符号を特定する。第２符号化部１０８は、最長一致文字列の位置と、一致長のハフマン符号と、識別ビットとを合わせた圧縮データを、記憶領域Ａ３に格納し、ファイルライト部１１１に出力する。
【００３８】
識別ビット生成部１０９は、最長一致文字列のデータ量に基づいて、識別ビット「０」または識別ビット「１」を出力する処理部である。具体的に、識別ビット生成部１０９は、最長一致文字列のデータ量が３バイト未満である場合には、識別ビット「０」を出力する。これに対して、識別ビット生成部１０９は、最長一致文字列のデータ量が３バイト以上である場合には、識別ビット「１」を出力する。
【００３９】
参照部更新部１１０は、記憶領域Ａ１と記憶領域Ａ２との照合が完了した場合に、記憶領域Ａ１に格納されたデータを、記憶領域Ａ２に格納する処理部である。
【００４０】
ファイルライト部１１１は、最長一致文字列のデータ量が３バイト未満の場合に、識別ビット「０」と、第１符号化部１０７から出力されるハフマン符号とを合わせた圧縮データを、記憶領域Ａ３に書き込む。また、ファイルライト部１１１は、最長一致データのデータ量が３バイト以上の場合に、識別ビット「１」と、第２符号化部１０８から出力される最長一致データの位置およびデータ長とを合わせた圧縮データを、記憶領域Ａ３に書き込む。
【００４１】
また、ファイルライト部１１１は、記憶領域Ａ１に対する処理が終了すると、記憶領域Ａ３のデータを圧縮ファイルＦ２に書き込む。なお、頻度表の作成が完了後に、ファイルライト部１１１は、頻度表生成部１０３から頻度表の情報を取得し、取得した頻度表の情報を、ヘッダ情報として、圧縮ファイルＦ２に付加する。
【００４２】
次に伸長部１００ｂの構成の一例について説明する。図７は、伸長部の構成の参考例を示す機能ブロック図である。図７に示すように、伸長部１００ｂは、第１段階処理部１３０ａと第２段階処理部１３０ｂとを有する。第１段階処理部１３０ａは、頻度表リード部１２１と、ハフマン木生成部１２２とを有する。第２段階処理部１３０ｂは、ファイルリード部１２３と、圧縮符号識別部１２４と、第１伸長部１２５と、第２伸長部１２６と、参照部更新部１２７と、ファイルライト部１２８とを有する。
【００４３】
第１段階処理部１３０ａは、圧縮ファイルＦ２のヘッダ情報に含まれる頻度表を基にして、ハフマン木を生成する処理部である。第１段階処理部１３０ａに含まれる各処理部について説明する。
【００４４】
頻度表リード部１２１は、頻度表の情報を読み出して、ハフマン木生成部１２２に出力する処理部である。例えば、頻度表リード部１２１が読み出す頻度表の情報は、図５の頻度表生成部１０３によって生成された頻度表の情報を取得する。
【００４５】
ハフマン木生成部１２２は、頻度表を基にしてハフマン木を生成する処理部である。ハフマン木生成部１２２がハフマン木を生成する処理は、図４のハフマン木生成部１０４と同様である。
【００４６】
第２段階処理部１３０ｂは、図３で説明したように、圧縮ファイルＦ２を伸長する処理部である。第２段階処理部１３０ｂに含まれる各部の処理について説明する。
【００４７】
ファイルリード部１２３は、圧縮ファイルＦ２内の圧縮データを記憶領域Ｂ１に読み出す処理部である。ファイルリード部１２３は、記憶領域Ｂ１に格納された圧縮データに対する処理が終了した場合に、新たな圧縮データを圧縮ファイルＦ２から読み出し、記憶領域Ｂ１に格納された圧縮データを更新する。
【００４８】
圧縮符号識別部１２４は、記憶領域Ｂ１の圧縮データから、識別子を読み出し、識別子が「０」であるのか「１」であるのかを判定する処理部である。圧縮符号識別１２４は、判定結果を、第１伸長部１２５および第２伸長部１２６に出力する。
【００４９】
第１伸長部１２５は、圧縮データの識別子が「０」である場合に処理を行う。第１伸長部１２５は、識別子が「０」である場合に、圧縮データの識別子以降のデータ列と、ハフマン木１０とを比較して、ハフマン木１０を辿り、到達した葉に含まれるデータを、伸長データとして復号する処理部である。第１伸長部１２５は、伸長データを、参照部である記憶領域Ｂ２、および記憶領域Ｂ３に格納し、参照部更新部１２７およびファイルライト部１２８に出力する。
【００５０】
第２伸長部１２６は、圧縮データの識別子が「１」である場合に処理を行う。第２伸長部１２６は、識別子が「１」である場合には、伸長データは、参照部である記憶領域Ｂ２内のデータが伸長データとなるため、記憶領域Ｂ２から伸長データを取り出す。
【００５１】
第２伸長部１２６は、伸長データを取り出すべく、最長一致文字列の格納された記憶領域Ｂ２の先頭からの位置と、最長一致文字列の長さを特定する。位置の情報は、圧縮データの識別子「１」以降の固定長（１６ｂｉｔ）の情報に対応する。また、長さの情報は、位置の情報以降の固定長（８ｂｉｔ）の情報に対応する。また、長さの情報は、ハフマン符号化されているため、第２伸長部１２６は、長さのハフマン符号と、ハフマン木１０とを比較して、ハフマン木１０を辿り、到達した葉に含まれる長さの情報を得る。
【００５２】
第２伸長部１２６は、位置と長さに対応するデータを参照部である記憶領域Ｂ２から取り出し、取り出したデータを伸長データとする。第２伸長部１２５は、伸長データを、参照部である記憶領域Ｂ２、および記憶領域Ｂ３に格納し、参照部更新部１２７およびファイルライト部１２８に出力する。
【００５３】
参照部更新部１２７は、第１伸長部１２５または第２伸長部１２６から伸長データを取得した場合に、伸長データによって、記憶領域Ｂ２を更新する処理部である。
【００５４】
ファイルライト部１２８は、第１伸長部１２５または第２伸長部１２６から伸長データを取得した場合に、伸長データを、記憶領域Ｂ３に格納し、ファイルＦ３に書き込む処理部である。
【００５５】
次に、参考例の問題について説明する。図８は、参考例の問題を説明するための図である。図８の縦軸は、出現頻度を示し、横軸は、データに割り当てられる圧縮符号の符号長を示す。参考例では、出現頻度の大きいデータに関しては、短い圧縮符号が割り当てられ、反対に、出現頻度の小さいデータに関しては、長い圧縮符号が割り当てられるが、出現頻度に限らず、伸長方法を区別するための１ビットの識別子が付与される。例えば、５ｂに含まれるような出現頻度の少ないデータに関しては、圧縮データ長に占める識別子の割合が「ａ２／Ａ２」と小さいため、圧縮率に余り影響を与えない。しかし、５ａに含まれるような出現頻度の大きい文字に関しては、圧縮データ長に占める識別子の割合「ａ１／Ａ１」が大きく、また、出現頻度が大きいため、合計すると圧縮データ長が長くなってしまい、圧縮率の低下を招く。
【００５６】
次に、本実施例に係る情報処理装置の圧縮処理について説明する。まず、第１段階処理として、情報処理装置は、圧縮対象となるファイルＦ１をリードし、データの出現頻度を集計し、拡張ハフマン木を生成する。そして、第２段階処理として、ファイルＦ１をリードし、最長一致文字列検索を行い、その結果に応じて符号化を行い、圧縮ファイルＦ２をライトする。なお、第１段階処理において、情報処理装置は、図２に示した最長一致文字列検索部１０６と同様の処理を行って、ファイルＦ１に対して最長一致文字列検索を実行し、各最長一致文字列の位置を特定する。そして、情報処理装置は、位置を０の連続数に変換し、０の連続数の出現頻度を集計する。また、１バイト単位に文字、またはデータの出現頻度を集計する。
【００５７】
位置を０の連続数に変換する処理の一例について説明する。情報処理装置は、位置を１６ビット長の２進数に変換し、先頭ビットから０の連続する数を計数したものを、０の連続数とする。例えば、位置が「２６（１０）」を、１６ビットの２進数で表すと「０００００００００００１１０１０」となる。このため、位置「２６」に対する０の連続数は「１１」となる。
【００５８】
情報処理装置は、データの出現頻度と、０の連続数の出現頻度を基にして、拡張ハフマン木３０を生成する。図９は、拡張ハフマン木の一例を示す図である。拡張ハフマン木３０は、ハフマン木１０と比較して、葉の構造体が異なり、葉の数も１６個多い２７２個となる。
【００５９】
図９に示す拡張ハフマン木３０は、最上位に根ノード３１を有し、各節点３２−１〜が枝によって接続され、各最下位に葉３０−１〜３０−２７２を有する。各節点のデータ構造は、３０ａに示すものとなる。基本的に、上位の節点と下位の左と右の節点への３種のポインタが格納される。下位の枝と節点が無い場合には、葉のデータが格納される。また、各葉のデータ構造は、３０ｂに示すものとなる。葉には、葉の識別子と、予備情報と、識別情報と、識別情報に応じた情報とが格納される。例えば、識別情報が「０」の場合には、識別情報に応じた情報は、文字コード（データ）または最長一致文字列の長さの情報となる。識別情報が「１」の場合には、識別情報に応じた情報は「０の連続数」となる。
【００６０】
図１０は、本実施例１に係る圧縮処理を説明する図である。図９に示した拡張ハフマン木を生成した後に、図１０に示す圧縮処理を実行する。情報処理装置は、記憶領域Ａ１、記憶領域Ａ２および記憶領域Ａ３を記憶部に確保する。記憶領域Ａ１は、例えば符号化部などと呼ばれる。例えば、ファイルＦ１は、「ｈｅ・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ  ｈｏｒｓｅ・・・３ｒｄ  ｈｏｒｓｅ・・・」というデータが含まれる。
【００６１】
情報処理装置は、記憶領域Ａ１にデータをリードし、圧縮データを生成する。情報処理装置は、圧縮データの生成処理を行ったデータを、記憶領域Ａ１から記憶領域Ａ２にコピーする。記憶領域Ａ２は、例えば参照部などと呼ばれる。圧縮データは、記憶領域Ａ１にリードされたデータと記憶領域Ａ２内のデータとの照合処理の結果に応じて生成される。情報処理装置は、圧縮データを順次記憶領域Ａ３に格納し、記憶領域Ａ３に格納された圧縮データに基づいて圧縮ファイルＦ２が生成される。特に、本実施例に係る圧縮部２００ａは、圧縮部１００ａと異なり、各圧縮データに識別子「０」または「１」を付与しないことを特徴とする。
【００６２】
図１０において、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「ｈｅ・・・１ｓｔ」に格納されている場合の処理の一例について説明する。情報処理装置は、記憶領域Ａ１のデータと記憶領域Ａ２のデータとを比較して、最長一致文字列を検索する。例えば、「ｈ」が、記憶領域Ａ２内で処理対象のデータと最も長く一致する文字、またはデータであるとすると、情報処理装置は、「ｈ」を１バイトの文字、またはデータとして特定する。
【００６３】
情報処理装置は、例えば「ｈ」のように最長一致文字列が３バイト未満の場合には、下記の処理を実行する。図１０に示すように、情報処理装置は、１バイトの文字「ｈ」と、拡張ハフマン木３０とを比較して、文字「ｈ」のデータのハフマン符号を特定し、圧縮データｄ１を生成し、記憶領域Ａ３に格納する。なお、圧縮データｄ１には、識別子は含まれない。
【００６４】
図１０において、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ」に格納されている場合の処理の一例について説明する。情報処理装置は、記憶領域Ａ１のデータと記憶領域Ａ２のデータとを比較して、最長一致文字列を検索する。例えば、「ｈｏｒｓｅ」が、記憶領域Ａ２内で処理対象のデータと最も長く一致するデータであるとすると、情報処理装置は、「ｈｏｒｓｅ」を最長一致文字列として特定する。
【００６５】
情報処理装置は、例えば「ｈｏｒｓｅ」のように最長一致文字列が３バイト以上である場合には、下記の処理を実行する。図１０に示すように、情報処理装置は、最長一致文字列の記憶領域Ａ２内での位置と、最長一致文字列のデータ長を特定する。情報処理装置は、最長一致文字列の位置に対応する０の連続数と、拡張ハフマン木３０とを比較して、０の連続数をハフマン符号化する。また、情報処理装置は、最長一致文字列の長さと、拡張ハフマン木３０とを比較して、長さをハフマン符号化する。情報処理装置は、０の連続数のハフマン符号と、長さのハフマン符号とを合わせて圧縮データｄ２を生成し、記憶領域Ａ３に格納する。なお、圧縮データｄ２には、識別子は含まれない。
【００６６】
図１０において、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ  ｈｏｒｓｅ・・・３ｒｄ」に格納されている場合の処理の一例について説明する。情報処理装置は、記憶領域Ａ１のデータと記憶領域Ａ２のデータとを比較して、最長一致文字列を検索する。例えば、「ｈｏｒｓｅ」が、記憶領域Ａ２内で処理対象のデータと最も長く一致するデータであるとすると、情報処理装置は、「ｈｏｒｓｅ」を最長一致文字列として特定する。
【００６７】
情報処理装置は、例えば「ｈｏｒｓｅ」のように最長一致文字列が３バイト以上である場合には、下記の処理を実行する。図１０に示すように、情報処理装置は、最長一致文字列の記憶領域Ａ２内での位置と、最長一致文字列のデータ長を特定する。情報処理装置は、最長一致文字列の位置に対応する０の連続数と、拡張ハフマン木３０とを比較して、０の連続数をハフマン符号化する。また、情報処理装置は、最長一致文字列の長さと、拡張ハフマン木３０とを比較して、長さをハフマン符号化する。情報処理装置は、０の連続数のハフマン符号と、長さのハフマン符号とを合わせて圧縮データｄ３を生成し、記憶領域Ａ３に格納する。なお、圧縮データｄ３には、識別子は含まれない。
【００６８】
図１１は、本実施例１に係る伸長処理を説明する図である。まず、情報処理装置は、記憶領域Ｂ１、記憶領域Ｂ２および記憶領域Ｂ３を記憶部に確保する。情報処理装置は、圧縮ファイルＦ２内の圧縮データを記憶領域Ｂ１にロードする。また、伸長部２００ｂは、圧縮データと拡張ハフマン木３０とを比較して、葉を特定し、特定した葉に含まれる識別情報が「０」であるか「１」であるかを判定する。
【００６９】
情報処理装置は、識別情報が「０」である場合には、特定した葉に含まれるデータを、圧縮データに対応する伸長データとして特定する。例えば、識別情報が「０」であり、葉に「ｈ」が含まれている場合には、圧縮データに対応する伸長データが「ｈ」となる。情報処理装置は、伸長データ「ｈ」を、記憶領域Ｂ２および記憶領域Ｂ３の双方に格納する。
【００７０】
情報処理装置は、識別情報が「１」である場合には、特定した葉に含まれる０の連続を基にして、最長一致文字列の位置を特定する。情報処理装置は、最長一致文字の位置を特定した後に、圧縮データの続きと、拡張ハフマン木３０とを比較して、葉を特定し、特定した葉に含まれる最長一致文字の長さを特定する。情報処理装置は、記憶領域Ｂ２を参照し、最長一致文字列の位置および長さに対応するデータ「ｈｏｒｓｅ」を記憶領域Ｂ２から取得する。この取得したデータ「ｈｏｒｓｅ」が、圧縮データに対応する伸長データとなる。情報処理装置は、伸長データ「ｈｏｒｓｅ」を、記憶領域Ｂ２および記憶領域Ｂ３の双方に媒介する。
【００７１】
図１２は、本実施例１に係る情報処理装置の構成を示す図である。図１２に示すように、この情報処理装置２００は、圧縮部２００ａと伸長部２００ｂと、記憶部２００ｃとを有する。圧縮部２００ａは、図１０に示した圧縮処理を実行する処理部である。伸長部２００ｂは、図１１に示した伸長処理を実行する処理部である。記憶部２００ｃは、圧縮対象のファイルＦ１、圧縮処理により得られる圧縮ファイルＦ２、ファイルＦ２を伸長して得られるファイルＦ３などを格納する。
【００７２】
図１３は、本実施例１に係る圧縮部の構成を示す機能ブロック図である。図１３に示すように、圧縮部２００ａは、第１段階処理部２２０ａと、第２段階処理部２２０ｂとを有する。第１段階処理部２２０ａは、参照部文字リード部２０１、文字頻度集計部２０２と、最長一致文字列検索部２０３と、頻度表生成部２０４と、拡張ハフマン木生成部２０５を有する。第２段階処理部２２０ｂは、ファイルリード部２０６と、最長一致文字列検索部２０７と、第１符号化部２０８と、第２符号化部２０９と、参照部更新部２１０と、ファイルライト部２１１とを有する。
【００７３】
参照部文字リード部２０１は、所定の記憶領域に圧縮対象となるファイルＦ１のコンテンツ部分を読み出す処理部である。例えば、参照部文字リード部２０１は、記憶領域Ａ１に圧縮対象となるファイルＦ１のコンテンツ部分を読み出す。そして、参照部文字リード部２０１は、後述の最長一致文字列検索部２０３による最長一致データの検索が完了した後に、記憶領域Ａ１に格納されたデータを記憶領域Ａ２にコピーし、新たなデータをファイルＦ１から読み出して、記憶領域Ａ１に格納する。
【００７４】
また、参照部文字リード部２０１は、例えば、記憶領域Ａ４に、圧縮対象となるファイルＦ１のコンテンツ部分を読み出す。そして、参照部文字リード部２０１は、後述の文字頻度集計部２０２の文字集計が完了した後に、ファイルＦ１の続きのコンテンツ部分を記憶領域Ａ４に格納する。
【００７５】
文字頻度集計部２０２は、例えば、記憶領域Ａ４に格納されたデータを参照し、各データの出現頻度を集計する処理部である。文字頻度集計部２０２は、各データの出現頻度の情報を頻度表生成部２０４に出力する。文字頻度集計部２０２は、記憶領域Ａ４のデータが更新される度に、データの出現回数を計数する。例えば、文字頻度集計部２０２は、全てのデータの出現回数と、各データの出現回数とを基にして、データの出現頻度を集計する。
【００７６】
最長一致文字列検索部２０３は、参照部となる記憶領域Ａ２に格納されたデータと、符号化部となる記憶領域Ａ１に格納されたデータとを比較して、最長一致文字列を検索する処理部である。最長一致文字列を検索する処理は、図５に示した最長一致文字列検索部１０６と同様である。
【００７７】
また、最長一致文字列検索部２０３は、最長一致文字列の位置を、０の連続数に変換する。具体的には、最長一致文字列検索部２０３は、位置を１６ビット長の２進数に変換し、先頭から０が連続する数を計数したものを、０の連続するとして算出する。例えば、位置が「２６（１０）」を、１６ビットの２進数で表すと「０００００００００００１１０１０」となる。このため、位置「２６」に対する０の連続数は「１１」となる。
【００７８】
最長一致文字列検索部２０３は、記憶領域Ａ１のデータが更新される度に、最長一致文字列の位置の０の連続数を算出し、各０の連続数の出現頻度を算出する。最長一致文字列検索部２０３は、各０の連続数の出現頻度の情報を頻度表生成部２０４に出力する。
【００７９】
頻度表生成部２０４は、各データの出現頻度と、０の連続数の出現頻度とを基にして、拡張した頻度表を生成する処理部である。頻度表生成部２０４は、拡張した頻度表の情報を、拡張ハフマン木生成部２０５に出力する。図１４は、拡張した頻度表のデータ構造の一例を示す図である。図１４に示すように、この拡張した頻度表４０は、文字コード（データ）／長さと出現頻度とを対応付ける。また、０の連続数と出現頻度とを対応付ける。文字コード（データ）／長さと出現頻度とを対応付けたレコードの数は、２５６である。０の連続数と出現頻度とを対応付けたレコードの数は１６である。文字コード（データ）／長さの番号は、所定の文字コードに対応する番号あるいは長さに対応する。
【００８０】
頻度表生成部２０４は、頻度表４０の１段目〜２５６段目までのレコードについては、文字頻度集計部２０２から取得する各データの出現頻度の情報を格納する。頻度表生成部２０４は、２５７段目〜２７２段目までのレコードについては、最長一致文字列検索部２０３から取得する０の連続数の出現頻度の情報を格納する。
【００８１】
拡張ハフマン木生成部２０５は、拡張した頻度表４０を基にして、拡張したハフマン木３０を生成する処理部である。拡張ハフマン木生成部２０５のデータ構造は、図９に示した拡張ハフマン木３０に対応する。
【００８２】
拡張ハフマン木生成部２０５は、葉の識別子と、予備情報と、識別情報「０」と、文字または最長一致文字列の長さとを対応付けた葉の構造体を２５６個生成する。また、拡張ハフマン木生成部２０５は、葉の識別子と、予備情報と、識別情報「１」と、０の連続数とを対応付けた葉の構造体を１６個生成する。また、拡張ハフマン木生成部２０５は、葉の構造体に含まれる文字コード（データ）または０の連続数と、頻度表４０とを比較して、各葉の構造体の出現頻度を特定する。
【００８３】
拡張ハフマン木生成部２０５は、葉の構造体を文字コード、または、０の連続数の出現頻度の順にソートし、出現頻度に応じて、２分木の「枝」をくみ上げ、上位に向かって、２分木の枝をくみ上げていくことで、ハフマン木を生成する。
【００８４】
第２段階処理部２２０ｂは、図１０で説明したように、ファイルＦ１を圧縮する処理部である。第２段階処理部２２０ｂに含まれる各部の処理について説明する。
【００８５】
ファイルリード部２０６は、ファイルＦ１内のコンテンツ部分のデータを、符号化部に対応する記憶領域Ａ１に読み出す処理部である。ファイルリード部２０６は、記憶領域Ａ１に格納されたデータに対する処理が終了し、記憶領域Ａ１のデータが参照部Ａ２に移行し、圧縮符号が格納された記憶領域Ａ３のデータをＦ２へ書き込んだ後に、新たなデータをファイルＦ１から読み出し、記憶領域Ａ１に格納されたデータを更新する。
【００８６】
最長一致文字検索部２０７は、参照部となる記憶領域Ａ２に格納された圧縮データと、記憶領域Ａ１に格納されたデータとを比較して、最長一致文字列を検索する処理部である。最長一致文字列を検索する処理は、図１０に示した処理と同様である。最長一致文字探索部２０７は、最長一致文字列の情報を、第１符号部２０８、第２符号部２０９に出力する。
【００８７】
第１符号化部２０８は、最長一致文字列のデータ量が３バイト未満の場合に処理を行う。第１符号化部２０８は、最長一致文字列のデータ量が３バイト未満の場合に、それぞれの１バイトの文字コード、またはデータの２進数表現と、拡張ハフマン木３０とを比較して、ハフマン符号を特定する。第１符号化部２０８は、ハフマン符号を記憶領域Ａ３に格納し、ファイルライト部２１１に出力する。このハフマン符号そのものが、圧縮データとなる。
【００８８】
図１５は、圧縮部の第２符号化部の処理を説明するための図（１）である。第２符号化部２０９は、最長一致文字列のデータ量が３バイト以上の場合に処理を行う。図１５に示すように、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ」が格納されており、最長一致文字列を「ｈｏｒｓｅ」とする。
【００８９】
第２符号化部３０８は、最長一致文字列のデータ量が３バイト以上の場合に、最長一致文字列の記憶領域Ａ２での先頭からの位置と、最長一致文字列の一致長を特定する。図１５に示す例では、最長一致文字列の位置は「Ｘ１」となり、最長一致文字列の長さは「Ｙ１」となる。
【００９０】
第２符号化部２０９は、最長一致文字列の位置「Ｘ１」を１６ビット長の２進数で表した場合における「０の連続数」と、「１以降のビット列」とを特定する。第２符号化部２０９は、「０の連続数」と、拡張ハフマン木３０とを比較して、「０の連続数」のハフマン符号を求める。また、第２符号化部２０９は、最長一致文字列の長さ「Ｙ１」と、拡張ハフマン木３０とを比較して、最長一致文字列の長さ「Ｙ１」のハフマン符号を求める。
【００９１】
第２符号化部２０９は、最長一致文字列の位置の「０の連続数」のハフマン符号と、最長一致文字列の位置の「１以降のビット列」と、最長一致文字列の「長さ」のハフマン符号を組み合わせて、圧縮データｄ２を生成する。第２符号化処理部２０９は、圧縮データｄ２を、記憶領域Ａ３に格納し、ファイルライト部２１１に出力する。
【００９２】
参照部更新部２１０は、記憶領域Ａ１と記憶領域Ａ２との照合が完了した場合に、記憶領域Ａ１に格納されたデータを、記憶領域Ａ２に格納する処理部である。
【００９３】
ファイルライト部２１１は、最長一致文字列のデータ量が３バイト未満の場合に、第１符号化部２０８から出力される圧縮データを、記憶領域Ａ３に書き込む。また、ファイルライト部２１１は、最長一致データのデータ量が３バイト以上の場合に、第２符号化部１０９から出力される圧縮データを、記憶領域Ａ３に書き込む。
【００９４】
また、ファイルライト部２１１は、記憶領域Ａ１に対する処理が終了すると、記憶領域Ａ３のデータを圧縮ファイルＦ２に書き込む。なお、ファイルライト部２１１は、第１段階処理において、頻度表の作成の完了後に、頻度表生成部２０４から頻度表の情報を取得し、取得した頻度表の情報を、ヘッダ情報として、圧縮ファイルＦ２に付加する。
【００９５】
図１６は、本実施例に係る伸長部の構成を示す機能ブロック図である。図１６に示すように、この伸長部２００ｂは、第１処理部２３０ａと、第２段階処理部２３０ｂとを有する。第１段階処理部２３０ａは、頻度表リード部２２１と、拡張ハフマン木生成部２２２とを有する。
【００９６】
第１段階処理部２３０ａは、圧縮ファイルＦ２のヘッダ情報に含まれる拡張された頻度表４０の情報を基にして、拡張ハフマン木３０を生成する処理部である。第１段階処理部２３０ａに含まれる各処理部について説明する。
【００９７】
頻度表リード部２２１は、拡張された頻度表４０の情報を読み出して、拡張ハフマン木生成部２２２に出力する処理部である。例えば、頻度表リード部２２１が読み出す拡張された頻度表の情報は、図１３の頻度表生成部２０４によって生成された拡張された頻度表の情報を取得する。
【００９８】
拡張ハフマン木生成部２２２は、拡張された頻度表４０を基にして拡張ハフマン木３０を生成する処理部である。拡張ハフマン木生成部２２２が拡張ハフマン木３０を生成する処理は、図１３の拡張ハフマン木生成部２０５が拡張ハフマン木３０を生成する処理と同じである。
【００９９】
第２段階処理部２３０ｂは、図１１で説明したように、圧縮ファイルＦ２を伸長する処理部である。第２段階処理部２３０ｂに含まれる各部の処理について説明する。
【０１００】
ファイルリード部２２３は、圧縮ファイルＦ２内の圧縮データを記憶領域Ｂ１に読み出す処理部である。ファイルリード部２２３は、記憶領域Ｂ１に格納された圧縮データに対する処理が終了した場合に、新たな圧縮データを圧縮ファイルＦ２から読み出し、記憶領域Ｂ１に格納された圧縮データを更新する。
【０１０１】
葉識別部２２４は、記憶領域Ｂ１に格納された圧縮データと、拡張ハフマン木３０とを比較して、拡張ハフマン木３０を辿り、葉を特定する情報である。葉識別部２２４は、特定した葉の情報を、第１伸長部２２５および第２伸長部２２６に出力する。
【０１０２】
第１伸長部２２５は、葉に含まれる識別情報が「０」の場合に処理を行う。図９で説明したように、識別情報が「０」の場合には、葉には文字コード（データ）の情報が含まれる。第１伸長部２２５は、葉に含まれる文字コード（データ）の情報を抽出する。第１伸長部２２５は、抽出した文字コード（データ）の情報を、伸長データとして、参照部である記憶領域Ｂ２、および記憶領域Ｂ３に格納し、ファイルライト部２２８に出力する。
【０１０３】
第２伸長部２２６は、葉に含まれる識別情報が「１」の場合に処理を行う。図９で説明したように、識別情報が「１」の場合には、葉には「０の連続数」が含まれる。第２伸長部２２６は、「０の連続数」を基にして、最長一致文字列の位置を復元する。
【０１０４】
図１７は、第２伸長部の処理を説明するための図（１）である。図１７において、記憶領域Ｂ１に含まれる圧縮データと、拡張ハフマン木３０との比較がなされ、記憶領域Ｂ１のｘ１の位置まで、ポインタが移動したものとする。また、「０の連続数」を「１１」とすると、最長一致文字列の位置は、１６ビット長で２進数に変換されているため、１以降のビット長は、「５ビット」となる。このため、第２伸長部２２６は、位置Ｘ１の次から５ビット進めた位置Ｘ２までのビット列「１０１０１」を、最長一致文字列の位置として復元する。
【０１０５】
また、第２伸長部２２６は、位置Ｘ２以降のビットと拡張ハフマン木３０とを比較して、拡張ハフマン木３０の葉を特定し、特定した葉に含まれる最長一致文字列の長さを特定する。上記の処理を実行することで、第２伸長部２２６は、最長一致文字列の位置と長さを特定する。第２伸長部２２６は、位置と長さに対応するデータを記憶領域Ｂ２から取り出し、取り出したデータを伸長データとする。第２伸長部２２６は、伸長データを、参照部である記憶領域Ｂ２、およびＢ３に格納し、参照部更新部２２７およびファイルライト部２２８に出力する。
【０１０６】
参照部更新部２２７は、第１伸長部２２５または第２伸長部２２６から伸長データを取得した場合に、伸長データによって、記憶領域Ｂ２を更新する処理部である。
【０１０７】
ファイルライト部２２８は、第１伸長部２２５または第２伸長部２２６から伸長データを取得した場合に、伸長データを記憶領域Ｂ３に格納し、ファイルＦ３に書き込む処理部である。
【０１０８】
図１８は、本実施例１に係る圧縮部の処理手順を示すフローチャートである。図１８に示すように、圧縮部２００ａは、前処理を実行する（ステップＳ１０１）。ステップＳ１０１の前処理において、圧縮部２００ａは、記憶領域Ａ１、記憶領域Ａ２および記憶領域Ａ３を記憶部２００ｃに確保する。
【０１０９】
圧縮部２００ａは、ファイルＦ１とＦ２をオープンし（ステップＳ１０２）、ファイルＦ１をリードし、文字の出現頻度を集計し、頻度表の情報を生成する（ステップＳ１０３）。圧縮部２００ａは、圧縮ファイルＦ２のヘッダに頻度表４０の情報を格納する（ステップＳ１０４）。圧縮部２００ａは、頻度表４０の情報を基にして、拡張ハフマン木３０を生成する（ステップＳ１０５）。
【０１１０】
圧縮部２００ａは、最長一致文字列を検索し（ステップＳ１０６）、最長一致文字列のデータ量に応じて、圧縮データの生成・書き込みを行う（ステップＳ１０７）。圧縮部２００ａは、記憶領域Ａ２を更新し（ステップＳ１０８）、記憶領域Ａ４を更新する（ステップＳ１０９）。
【０１１１】
圧縮部２００ａは、ファイルＦ１の終点であるか否かを判定する（ステップＳ１１０）。圧縮部２００ａは、ファイルＦ１の終点では無い場合には（ステップＳ１１０，Ｎｏ）、ステップＳ１０６に移行する。
【０１１２】
一方、圧縮部２００ａは、ファイルＦ１の終点である場合には（ステップＳ１１０，Ｙｅｓ）、圧縮ファイルＦ１とＦ２をクローズする（ステップＳ１１１）。
【０１１３】
次に、図１８のステップＳ１０３およびステップＳ１０４で示した、頻度表４０を生成する処理および拡張ハフマン木３０を生成する処理手順について具体的に説明する。
【０１１４】
図１９は、頻度表および拡張ハフマン木を生成する処理手順を示すフローチャート（１）である。図１９に示すように、圧縮部２００ａは、ファイルＦ１に含まれるデータの出現頻度を計算する（ステップＳ１５１）。圧縮部２００ａは、ファイルＦ１に含まれる最長一致文字列を検出し、最長一致文字列の０の連続数の出現頻度を計算する（ステップＳ１５２）。
【０１１５】
圧縮部２００ａは、文字コード（データ）または最長一致文字列の長さおよび識別情報「０」を対応付けた葉と、０の連続数および識別情報「１」を対応付けた葉を生成する（ステップＳ１５３）。圧縮部２００ａは、葉を出現頻度の順にソートする（ステップＳ１５４）。
【０１１６】
圧縮部２００ａは、出現頻度を基にして、２分木の枝をくみあげて拡張ハフマン木３０を生成する（ステップＳ１５５）。
【０１１７】
次に、図１８のステップＳ１０６で示した圧縮データを生成する処理手順について具体的に説明する。
【０１１８】
図２０は、圧縮データを生成する処理手順を示すフロートチャート（１）である。図２０に示すように、圧縮部２００ａは、最長一致文字列のデータ量が３バイト以上であるか否かを判定する（ステップＳ１６１）。
【０１１９】
圧縮部２００ａは、３バイト以上である場合には（ステップＳ１６２，Ｙｅｓ）、最長一致文字列の０の連続数と拡張ハフマン木３０とを比較して、０の連続数をハフマン符号化する（ステップＳ１６３）。
【０１２０】
圧縮部２００ａは、最長一致文字列の長さと拡張ハフマン木３０とを比較して、長さをハフマン符号化する（ステップＳ１６４）。圧縮部２００ａは、ハフマン符号化した０の連続数と、１以降のビット列と、ハフマン符号化した長さを圧縮データとして出力する（ステップＳ１６５）。
【０１２１】
一方、圧縮部２００ａは、最長一致文字列のデータ量が３バイト未満の場合には（ステップＳ１６２，Ｎｏ）、文字コード（データ）と拡張ハフマン木３０とを比較して、文字コード（データ）をハフマン符号化したものを圧縮データとして出力する（ステップＳ１６６）。
【０１２２】
図２１は、本実施例１に係る伸長部の処理手順を示すフローチャートである。図２１に示すように、伸長部２００ｂは、前処理を実行する（ステップＳ２０１）。ステップＳ２０１の前処理において、伸長部２００ｂは、記憶領域Ｂ１、記憶領域Ｂ２および記憶領域Ｂ３を記憶部２００ｃに確保する。
【０１２３】
伸長部２００ｂは、ファイルＦ２とＦ３をオープンし（ステップＳ２０２）、圧縮ファイルＦ２のヘッダから頻度表４０を読み出す（ステップＳ２０３）。伸長部２００ｂは、拡張ハフマン木３０を生成する（ステップＳ２０４）。
【０１２４】
伸長部２００ｂは、圧縮データと拡張ハフマン木３０とを比較し（ステップＳ２０５）、拡張ハフマン木３０の葉の識別情報が「０」であるか否かを判定する（ステップＳ２０６）。
【０１２５】
伸長部２００ｂは、識別情報が「０」である場合には（ステップＳ２０６，Ｙｅｓ）、葉に含まれる文字コード（データ）を記憶領域Ｂ２に格納し（ステップＳ２０７）、伸長データの書き込みを行う（ステップＳ２０８）。
【０１２６】
一方、伸長部２００ｂは、識別情報が「１」である場合には（ステップＳ２０６，Ｎｏ）、葉に含まれる０の連続数を基に、最長一致文字列の位置および長さを特定する（ステップＳ２０９）。伸長部２００ｂは、最長一致文字列の位置および長さに対応する文字列を記憶領域Ｂ２から取得する（ステップＳ２１０）。
【０１２７】
伸長部２００ｂは、データを記憶領域Ｂ２に格納し（ステップＳ２１１）、ステップＳ２０８に移行する。伸長部２００ｂは、圧縮ファイルＦ２の終点であるか否かを判定する（ステップＳ２１２）。
【０１２８】
伸長部２００ｂは、圧縮ファイルＦ２の終点でない場合には（ステップＳ２１２，Ｎｏ）、ステップＳ２０５に移行する。一方、伸長部２００ｂは、圧縮ファイルＦ２の終点である場合には（ステップＳ２１２，Ｙｅｓ）、ファイルＦ２とＦ３をクローズする（ステップＳ２１３）。
【０１２９】
次に、図２１のステップＳ２０９に示した葉に含まれる０の連続数を基に、最長一致文字列の位置および長さを特定する処理について説明する。図２２は、葉に含まれる０の連続数を基に、最長一致文字列の位置および長さを特定する処理手順を示すフローチャートである。
【０１３０】
図２２に示すように、伸長部２００ｂは、葉に含まれる０の連続数を基にして、圧縮データに含まれる１以降のビット列のビット長を特定する（ステップＳ２５１）。伸長部２００ｂは、圧縮データから１以降のビット列を取得し、最長一致文字列の位置を特定する（ステップＳ２５２）。
【０１３１】
伸長部２００ｂは、圧縮データの続きと、拡張ハフマン木３０とを比較して、最長一致文字列の長さを特定する（ステップＳ２５３）。
【０１３２】
次に、本実施例にかかる情報処理装置２００の効果について説明する。情報処置装置２００の圧縮部２００は、準備段階で、圧縮対象のファイルＦ１に対して最長一致検索をおこない、データの出現頻度と、所定長以上となる最長一致文字列の位置の出現頻度を特定する。そして、圧縮段階において、圧縮部２００ａは、圧縮対象のファイルＦ１に対して最長一致文字列検索をおこなう。圧縮部２００ａは、最長一致文字列が所定長未満の場合には、出現頻度の情報を基にして、最長一致文字列を符号化し、圧縮データを生成する。圧縮部２００ａは、最長一致文字列が所定長以上の場合には、出現頻度の情報を基にして、最長一致文字列の位置の符号化し、最長一致文字列の圧縮データを生成する。これによって、圧縮データに識別情報が付加されないため、圧縮率の低下を防止することができる。
【０１３３】
本実施例１に係る情報処理装置１００では、データの出現頻度と、０の連続数の出現頻度とをまとめ、さらに識別情報を葉に追加した拡張ハフマン木３０を用いて圧縮し、この拡張ハフマン木３０を用いて伸長を行うこととなる。情報処理装置１００が、伸長処理を行う場合に、拡張ハフマン木３０をたどり、拡張ハフマン木３０の葉の識別情報を参照すれば、０の連続数で圧縮されているか否かを識別可能であるため、圧縮処理の際に、圧縮データそのものに識別情報を付与しなくても伸長を実行可能となる。
【０１３４】
また、情報処理装置２００は、伸長部２００が、準備段階で、圧縮対象のファイルＦ１に対して最長一致検索をおこない、データの出現頻度と、所定長以上となる最長一致文字列の位置の出現頻度を取得する。そして、伸長段階において、圧縮ファイルＦ２と出現頻度の情報とを比較して、圧縮ファイルＦ２を伸長する。このため、圧縮ファイルＦ２に識別情報が付加されていなくても、適切に伸長することができる。
【実施例２】
【０１３５】
次に、本実施例２に係る情報処理装置の圧縮処理について説明する。まず、情報処理装置は、圧縮対象となるファイルＦ１を参照し、データの出現頻度を集計する。また、情報処理装置は、実施例１に図２に示した最長一致文字列検索部１０６と同様の処理を行って、ファイル１に対して最長一致文字列検索を実行し、各最長一致文字列の位置を特定する。情報処理装置は、位置を１６ビットの２進数で表した場合に、先頭ビットが０の場合には、位置を０の連続数に変換し、０の連続数の出現頻度を集計する。位置を０の連続数に変換する処理は、実施例１と同様である。
【０１３６】
これに対して、位置を１６ビットの２進数で表した場合に、先頭ビットが１の場合には、位置を１の連続数に変換し、１の連続数の出現頻度を集計する。
【０１３７】
位置を１の連続数に変換する処理の一例について説明する。情報処理装置は、位置を１６ビット長の２進数に変換し、先頭ビットから１の連続する数を計数したものを、１の連続数とする。例えば、位置が「６４６８２（１０）」を、１６ビットの２進数で表すと「１１１１１１００１０１０１０１０」となる。このため、位置「６４６８２」に対する１の連続数は「６」となる。
【０１３８】
情報処理装置は、データの出現頻度と、０の連続数の出現頻度と、１の連続数の出現頻度を基にして、拡張ハフマン木３０を生成する。図２３は、拡張ハフマン木の一例を示す図（２）である。拡張ハフマン木５０は、ハフマン木１０と比較して、葉の構造体が異なり、葉の数も３２個多い２８８個となる。
【０１３９】
図２３に示す拡張ハフマン木５０は、最上位に根ノード５１を有し、各節点５２−１〜が枝によって接続され、各最下位に葉５０−１〜５０−２８８を有する。各節点のデータ構造は、５０ａに示すものとなる。基本的に、上位の節点と下位の左と右への３種のポインタが格納される。下位の枝と節点が無い場合には、葉のデータが格納される。また、各葉のデータ構造は、５０ｂに示すものとなる。葉には、葉の識別子と、予備情報と、識別情報と、識別情報に応じた情報とが格納される。例えば、識別情報が「０」の場合には、識別情報に応じた情報は、文字または最長一致文字列の長さの情報となる。識別情報が「１０」の場合には、識別情報に応じた情報は「０の連続数」となる。識別情報が「１１」の場合には、識別情報に応じた情報は「１の連続数」となる。図２３に示した拡張ハフマン木を生成した後に、下記に示す圧縮処理を実行する。
【０１４０】
図２４は、本実施例２に係る圧縮処理を説明する図である。情報処理装置は、記憶領域Ａ１、記憶領域Ａ２および記憶領域Ａ３を記憶部に確保する。記憶領域Ａ１は、例えば符号化部などと呼ばれる。例えば、ファイルＦ１は、「ｈｅ・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ  ｈｏｒｓｅ・・・３ｒｄ  ｈｏｒｓｅ・・・」というデータが含まれる。
【０１４１】
情報処理装置は、記憶領域Ａ１にデータをリードし、圧縮データを生成する。情報処理装置は、圧縮データの生成処理を行ったデータを、記憶領域Ａ１から記憶領域Ａ２にコピーする。記憶領域Ａ２は、例えば参照部などと呼ばれる。圧縮データは、記憶領域Ａ１にリードされたデータと記憶領域Ａ２内のデータとの照合処理の結果に応じて生成される。情報処理装置は、圧縮データを順次記憶領域Ａ３に格納し、記憶領域Ａ３に格納された圧縮データに基づいて圧縮ファイルＦ２が生成される。
【０１４２】
図２４において、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「ｈｅ・・・１ｓｔ」に格納されている場合の処理の一例について説明する。情報処理装置は、記憶領域Ａ１のデータと記憶領域Ａ２のデータとを比較して、最長一致文字列を検索する。例えば、「ｈ」が、記憶領域Ａ２内で処理対象のデータと最も長く一致する文字、またはデータであるとすると、情報処理装置は、「ｈ」を１バイトの文字、またはデータとして特定する。
【０１４３】
情報処理装置は、例えば「ｈ」のように最長一致文字列が３バイト未満の場合には、下記の処理を実行する。図２４に示すように、情報処理装置は、１バイトの文字「ｈ」と、拡張ハフマン木５０とを比較して、文字「ｈ」またはデータのハフマン符号を特定し、圧縮データｄ１を生成し、記憶領域Ａ３に格納する。なお、圧縮データｄ１には、識別子は含まれない。
【０１４４】
図２４において、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ」に格納されている場合の処理の一例について説明する。情報処理装置は、記憶領域Ａ１のデータと記憶領域Ａ２のデータとを比較して、最長一致文字列を検索する。例えば、「ｈｏｒｓｅ」が、記憶領域Ａ２内で処理対象のデータと最も長く一致するデータであるとすると、情報処理装置は、「ｈｏｒｓｅ」を最長一致文字列として特定する。
【０１４５】
情報処理装置は、例えば「ｈｏｒｓｅ」のように最長一致文字列が３バイト以上であり、かつ、最長一致文字列の位置の先頭ビットが「０」の場合には、下記の処理を実行する。図２４に示すように、情報処理装置は、最長一致文字列の記憶領域Ａ２内での位置と、最長一致文字列のデータ長を特定する。情報処理装置は、最長一致文字列の位置に対応する０の連続数と、拡張ハフマン木５０とを比較して、０の連続数をハフマン符号化する。また、情報処理装置は、最長一致文字列の長さと、拡張ハフマン木５０とを比較して、長さをハフマン符号化する。情報処理装置は、０の連続数のハフマン符号と、長さのハフマン符号とを合わせて圧縮データｄ２を生成し、記憶領域Ａ３に格納する。なお、圧縮データｄ２には、識別子は含まれない。
【０１４６】
図２４において、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「・・・２ｎｄ  ｈｏｒｓｅ・・・３ｒｄ」に格納されている場合の処理の一例について説明する。情報処理装置は、記憶領域Ａ１のデータと記憶領域Ａ２のデータとを比較して、最長一致文字列を検索する。例えば、「ｈｏｒｓｅ」が、記憶領域Ａ２内で処理対象のデータと最も長く一致するデータであるとすると、情報処理装置は、「ｈｏｒｓｅ」を最長一致文字列として特定する。
【０１４７】
情報処理装置は、例えば「ｈｏｒｓｅ」のように最長一致文字列が３バイト以上であり、かつ、最長一致文字列の位置の先頭ビットが「１」の場合には、下記の処理を実行する。図２４に示すように、情報処理装置は、最長一致文字列の記憶領域Ａ２内での位置と、最長一致文字列のデータ長を特定する。情報処理装置は、最長一致文字列の位置に対応する１の連続数と、拡張ハフマン木５０とを比較して、１の連続数をハフマン符号化する。また、情報処理装置は、最長一致文字列の長さと、拡張ハフマン木５０とを比較して、長さをハフマン符号化する。情報処理装置は、１の連続数のハフマン符号と、長さのハフマン符号とを合わせて圧縮データｄ３を生成し、記憶領域Ａ３に格納する。なお、圧縮データｄ３には、識別子は含まれない。
【０１４８】
図２５は、本実施例２に係る伸長処理を説明する図である。まず、情報処理装置は、記憶領域Ｂ１、記憶領域Ｂ２および記憶領域Ｂ３を記憶部に確保する。情報処理装置は、圧縮ファイルＦ２内の圧縮データを記憶領域Ｂ１にロードする。また、伸長部２００ｂは、圧縮データと拡張ハフマン木３０とを比較して、葉を特定し、特定した葉に含まれる識別情報が「０」であるか「１０」であるか「１１」であるかを判定する。
【０１４９】
情報処理装置は、識別情報が「０」である場合には、特定した葉に含まれるデータを、圧縮データに対応する伸長データとして特定する。例えば、識別情報が「０」であり、葉に「ｈ」が含まれている場合には、圧縮データに対応する伸長データが「ｈ」となる。情報処理装置は、伸長データ「ｈ」を、記憶領域Ｂ２および記憶領域Ｂ３の双方に格納する。
【０１５０】
情報処理装置は、識別情報が「１０」である場合には、特定した葉に含まれる０の連続を基にして、最長一致文字列の位置を特定する。情報処理装置は、最長一致文字の位置を特定した後に、圧縮データの続きと、拡張ハフマン木５０とを比較して、葉を特定し、特定した葉に含まれる最長一致文字の長さを特定する。情報処理装置は、記憶領域Ｂ２を参照し、最長一致文字列の位置および長さに対応するデータ「ｈｏｒｓｅ」を記憶領域Ｂ２から取得する。この取得したデータ「ｈｏｒｓｅ」が、圧縮データに対応する伸長データとなる。情報処理装置は、伸長データ「ｈｏｒｓｅ」を、記憶領域Ｂ２および記憶領域Ｂ３の双方に格納する。
【０１５１】
情報処理装置は、識別情報が「１１」である場合には、特定した葉に含まれる１の連続を基にして、最長一致文字列の位置を特定する。情報処理装置は、最長一致文字の位置を特定した後に、圧縮データの続きと、拡張ハフマン木５０とを比較して、葉を特定し、特定した葉に含まれる最長一致文字の長さを特定する。情報処理装置は、記憶領域Ｂ２を参照し、最長一致文字列の位置および長さに対応するデータ「ｈｏｒｓｅ」を記憶領域Ｂ２から取得する。この取得したデータ「ｈｏｒｓｅ」が、圧縮データに対応する伸長データとなる。情報処理装置は、伸長データ「ｈｏｒｓｅ」を、記憶領域Ｂ２および記憶領域Ｂ３の双方に格納する。
【０１５２】
図２６は、本実施例２に係る情報処理装置の構成を示す図である。図２６に示すように、この情報処理装置３００は、圧縮部３００ａと伸長部３００ｂと、記憶部３００ｃとを有する。圧縮部３００ａは、図２４に示した圧縮処理を実行する処理部である。伸長部３００ｂは、図２５に示した伸長処理を実行する処理部である。記憶部３００ｃは、圧縮対象のファイルＦ１、圧縮処理により得られる圧縮ファイルＦ２、ファイルＦ２を伸長して得られるファイルＦ３などを媒介する。
【０１５３】
図２７は、本実施例２に係る圧縮部の構成を示す機能ブロック図である。図２７に示すように、圧縮部３００ａは、第１段階処理部３２０ａと、第２段階処理部３２０ｂとを有する。第１段階処理部３２０ａは、参照部文字リード部３０１、文字頻度集計部３０２と、最長一致文字列検索部３０３と、頻度表生成部３０４と、拡張ハフマン木生成部３０５を有する。第２段階処理部３２０ｂは、ファイルリード部３０６と、最長一致文字列検索部３０７と、第１符号化部３０８と、第２符号化部３０９と、参照部更新部３１０と、ファイルライト部３１１とを有する。このうち、参照部文字リード部３０１、文字頻度集計部３０２に関する説明は、実施例１に示した参照部文字リード部２０１および文字頻度集計部２０２と同様である。
【０１５４】
最長一致文字列検索部３０３は、参照部となる記憶領域Ａ２に格納されたデータと、符号化部となる記憶領域Ａ１に格納されたデータとを比較して、最長一致文字列を検索する処理部である。最長一致文字列を検索する処理は、図５に示した最長一致文字列検索部１０６と同様である。
【０１５５】
また、最長一致文字列検索部３０３は、最長一致文字列の位置の先頭ビットが「０」の場合には、位置を０の連続数に変換する。具体的には、最長一致文字列検索部３０３は、位置を１６ビット長の２進数に変換し、先頭から０が連続する数を計数したものを、０の連続するとして算出する。例えば、位置が「２６（１０）」を、１６ビットの２進数で表すと「０００００００００００１１０１０」となる。このため、位置「２６」に対する０の連続数は「１１」となる。
【０１５６】
最長一致文字列検索部３０３は、記憶領域Ａ１のデータが更新される度に、最長一致文字列の位置の０の連続数を算出し、各０の連続数の出現頻度を算出する。最長一致文字列検索部３０３は、各０の連続数の出現頻度の情報を頻度表生成部３０４に出力する。
【０１５７】
一方、最長一致文字列検索部３０３は、最長一致文字列の位置の先頭ビットが「１」の場合には、位置を１の連続数に変換する。具体的には、最長一致文字列検索部３０３は、位置を１６ビット長の２進数に変換し、先頭から１が連続する数を計数したものを、１の連続するとして算出する。例えば、位置が「６４６８２（１０）」を、１６ビットの２進数で表すと「１１１１１１００１０１０１０１０」となる。このため、位置「６４６８２（１０）」に対応する１の連続数は「６」となる。
【０１５８】
最長一致文字列検索部３０３は、記憶領域Ａ１のデータが更新される度に、最長一致文字列の位置の１の連続数を算出し、各１の連続数の出現頻度を算出する。最長一致文字列検索部３０３は、各１の連続数の出現頻度の情報を頻度表生成部３０４に出力する。
【０１５９】
頻度表生成部３０４は、各データの出現頻度、０の連続数の出現頻度、１の連続数の出現頻度を基にして、拡張した頻度表を生成する処理部である。頻度表生成部３０４は、拡張した頻度表の情報を、拡張ハフマン木生成部３０５に出力する。図２８は、拡張した頻度表のデータ構造の一例を示す図（２）である。図２８に示すように、この拡張した頻度表６０は、文字コード（データ）／長さと出現頻度とを対応付ける。また、０の連続数と出現頻度とを対応付ける。また、１の連続数と出現頻度とを対応付ける。文字コード（データ）／長さと出現頻度とを対応付けたレコードの数は、２５６である。０の連続数と出現頻度とを対応付けたレコードの数は１６である。１の連続数と出現頻度とを対応付けたレコードの数は１６である。文字コード（データ）／長さの番号は、所定の文字に対応する番号あるいは長さに対応する。
【０１６０】
拡張ハフマン木生成部３０５は、拡張した頻度表６０を基にして、拡張したハフマン木５０を生成する処理部である。拡張ハフマン木生成部３０５のデータ構造は、図２３に示した拡張ハフマン木５０に対応する。
【０１６１】
拡張ハフマン木生成部３０５は、葉の識別子と、予備情報と、識別情報「０」と、文字コード（データ）または最長一致文字列の長さとを対応付けた葉の構造体を２５６個生成する。拡張ハフマン木生成部３０５は、葉の識別子と、予備情報と、識別情報「１０」と、０の連続数とを対応付けた葉の構造体を１６個生成する。拡張ハフマン木生成部３０５は、葉の識別子と、予備情報と、識別情報「１１」と、１の連続数とを対応付けた葉の構造体を１６個生成する。拡張ハフマン木生成部３０５は、葉の構造体に含まれる文字コード、０の連続数、１の連続数と、頻度表６０とを比較して、各葉の構造体の出現頻度を特定する。
【０１６２】
拡張ハフマン木生成部３０５は、葉の構造体を文字コード、０の連続数、または１の連続数の出現頻度の順にソートし、出現頻度に応じて、２分木の「枝」をくみ上げ、上位に向かって、２分木の枝をくみ上げていくことで、ハフマン木を生成する。
【０１６３】
第２段階処理部３２０ｂは、図２４で説明したように、ファイルＦ１を圧縮する処理部である。第２段階処理部３２０ｂに含まれる各部の処理について説明する。
【０１６４】
ファイルリード部３０６は、ファイルＦ１内のコンテンツ部分のデータを、符号化部に対応する記憶領域Ａ１に読み出す処理部である。ファイルリード部３０６は、記憶領域Ａ１に格納されたデータに対する処理が終了し、記憶領域Ａ１のデータを参照部である記憶領域Ａ２に移行し、圧縮符号が格納された記憶領域Ａ３のデータを圧縮ファイルＦ２に書き込んだ後に、新たなデータをファイルＦ１から読み出し、記憶領域Ａ１に格納されたデータを更新する。
【０１６５】
最長一致文字検索部３０７は、参照部となる記憶領域Ａ２に格納されたデータと、記憶領域Ａ１に格納されたデータとを比較して、最長一致文字列を検索する処理部である。最長一致文字列を検索する処理は、図２４に示した処理と同様である。最長一致文字探索部３０７は、最長一致文字列の情報を、第１符号部３０８、第２符号部３０９に出力する。
【０１６６】
第１符号化部３０８は、最長一致文字列のデータ量が３バイト未満の場合に処理を行う。第１符号化部３０８は、最長一致文字列のデータ量が３バイト未満の場合に、それぞれの１バイトの文字コード、またはデータの２進数表現と、拡張ハフマン木５０とを比較して、ハフマン符号を特定する。第１符号化部３０８は、ハフマン符号を記憶領域Ａ３に格納し、ファイルライト部３１１に出力する。このハフマン符号そのものが、圧縮データとなる。
【０１６７】
図２９は、圧縮部の第２符号化部の処理を説明するための図（２）である。第２符号化部３０９は、最長一致文字列のデータ量が３バイト以上であり、かつ最長一致文字列の位置の先頭ビットが「０」の場合に、図２９の上段の処理を行う。図２９の上段に示すように、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「・・・１ｓｔ  ｈｏｒｓｅ・・・２ｎｄ」が格納されており、最長位置文字列を「ｈｏｒｓｅ」とする。
【０１６８】
第２符号化部３０８は、最長一致文字列のデータ量が３バイト以上の場合に、最長一致文字列の記憶領域Ａ２での先頭からの位置と、最長一致文字列の一致長を特定する。図２９に示す例では、最長一致文字列の位置は「Ｘ１」となり、最長一致文字列の長さは「Ｙ１」となる。ここで、Ｘ１の位置を「０００００００００００１１０１０」とすると、先頭ビットは「０」となる。
【０１６９】
第２符号化部３０９は、最長一致文字列の位置「Ｘ１」を１６ビット長の２進数で表した場合における「０の連続数」と、「１以降のビット列」とを特定する。第２符号化部３０９は、「０の連続数」と、拡張ハフマン木５０とを比較して、「０の連続数」のハフマン符号を求める。また、第２符号化部３０９は、最長一致文字列の長さ「Ｙ１」と、拡張ハフマン木５０とを比較して、最長一致文字列の長さ「Ｙ１」のハフマン符号を求める。
【０１７０】
第２符号化部３０９は、最長一致文字列の位置の「０の連続数」のハフマン符号と、最長一致文字列の位置の「１以降のビット列」と、最長一致文字列の「長さ」のハフマン符号を組み合わせて、圧縮データｄ２を生成する。第２符号化処理部３０９は、圧縮データｄ２を、記憶領域Ａ３に格納し、ファイルライト部３１１に出力する。
【０１７１】
これに対して、第２符号化部３０９は、最長一致文字列のデータ量が３バイト以上であり、かつ最長一致文字列の位置の先頭ビットが「１」の場合に、図２９の下段の処理を行う。図２９の下段に示すように、記憶領域Ａ１に「ｈｏｒｓｅ・・・」が格納され、記憶領域Ａ２に「・・・２ｎｄ  ｈｏｒｓｅ・・・３ｒｄ」が格納されており、最長位置文字列を「ｈｏｒｓｅ」とする。
【０１７２】
第２符号化部３０８は、最長一致文字列のデータ量が３バイト以上の場合に、最長一致文字列の記憶領域Ａ２での先頭からの位置と、最長一致文字列の一致長を特定する。図２９に示す例では、最長一致文字列の位置は「Ｘ２」となり、最長一致文字列の長さは「Ｙ２」となる。ここで、Ｘ２の位置を「１１１１１１００１０１０１０１０」とすると、先頭ビットは「１」となる。
【０１７３】
第２符号化部３０９は、最長一致文字列の位置「Ｘ２」を１６ビット長の２進数で表した場合における「１の連続数」と、「０以降のビット列」とを特定する。第２符号化部３０９は、「１の連続数」と、拡張ハフマン木５０とを比較して、「１の連続数」のハフマン符号を求める。また、第２符号化部３０９は、最長一致文字列の長さ「Ｙ２」と、拡張ハフマン木５０とを比較して、最長一致文字列の長さ「Ｙ２」のハフマン符号を求める。
【０１７４】
第２符号化部３０９は、最長一致文字列の位置の「１の連続数」のハフマン符号と、最長一致文字列の位置の「０以降のビット列」と、最長一致文字列の「長さ」のハフマン符号を組み合わせて、圧縮データｄ３を生成する。第２符号化処理部３０９は、圧縮データｄ３を、記憶領域Ａ３に格納し、ファイルライト部３１１に出力する。
【０１７５】
参照部変更部３１０、ファイルライト部３１１に関する説明は、実施例１に示した参照部更新部３１０およびファイルライト部３１１に関する説明と同様である。
【０１７６】
図３０は、本実施例２に係る伸長部の構成を示す機能ブロック図である。図３０に示すように、この伸長部３００ｂは、第１処理部３３０ａと、第２段階処理部３３０ｂとを有する。第１段階処理部３３０ａは、頻度表リード部３２１と、拡張ハフマン木生成部３２２とを有する。
【０１７７】
第１段階処理部３３０ａは、圧縮ファイルＦ２のヘッダ情報に含まれる拡張された頻度表６０の情報を基にして、拡張ハフマン木５０を生成する処理部である。第１段階処理部３３０ａに含まれる各処理部について説明する。
【０１７８】
頻度表リード部３２１は、拡張された頻度表６０の情報を読み出して、拡張ハフマン木生成部３２２に出力する処理部である。例えば、頻度表リード部３２１が読み出す拡張された頻度表の情報は、図２７の頻度表生成部３０４によって生成された拡張された頻度表の情報を取得する。
【０１７９】
拡張ハフマン木生成部３２２は、拡張された頻度表６０を基にして拡張ハフマン木５０を生成する処理部である。拡張ハフマン木生成部３２２が拡張ハフマン木５０を生成する処理は、図２７の拡張ハフマン木生成部３０５が拡張ハフマン木５０を生成する処理と同じである。
【０１８０】
第２段階処理部３３０ｂは、図２５で説明したように、圧縮ファイルＦ２を伸長する処理部である。第２段階処理部３３０ｂに含まれる各部の処理について説明する。
【０１８１】
ファイルリード部３２３は、圧縮ファイルＦ２内の圧縮データを記憶領域Ｂ１に読み出す処理部である。ファイルリード部３２３は、記憶領域Ｂ１に格納された圧縮データに対する処理が終了した場合に、新たな圧縮データを圧縮ファイルＦ２から読み出し、記憶領域Ｂ１に格納された圧縮データを更新する。
【０１８２】
葉識別部３２４は、記憶領域Ｂ１に格納された圧縮データと、拡張ハフマン木５０とを比較して、拡張ハフマン木５０を辿り、葉を特定する情報である。葉識別部３２４は、特定した葉の情報を、第１伸長部３２５および第２伸長部３２６に出力する。
【０１８３】
第１伸長部３２５は、葉に含まれる識別情報が「０」の場合に処理を行う。図２３で説明したように、識別情報が「０」の場合には、葉には文字コードの情報が含まれる。第１伸長部３２５は、葉に含まれる文字コードの情報を抽出する。第１伸長部３２５は、抽出した文字の情報を、伸長データとして、参照部である記憶領域Ｂ２、および記憶領域Ｂ３に格納し、ファイルライト部３２８に出力する。
【０１８４】
第２伸長部３２６は、葉に含まれる識別情報が「１０」または「１１」の場合に処理を行う。図２３で説明したように、識別情報が「１０」の場合には、葉には「０の連続数」が含まれる。第２伸長部２２６は、識別情報が「１０」の場合に伸長データを生成する処理は、実施例１の第２伸長部２２６と同様である。
【０１８５】
図３１は、第２伸長部の処理を説明するための図（２）である。図３１において、記憶領域Ｂ１に含まれる圧縮データと、拡張ハフマン木５０との比較がなされ、記憶領域Ｂ１のｘ１の位置まで、ポインタが移動したものとする。また、「１の連続数」を「６」とすると、最長一致文字列の位置は、１６ビット長で２進数に変換されているため、１以降のビット長は、「１０ビット」となる。このため、第２伸長部２２６は、位置Ｘ１の次から１０ビット進めた位置Ｘ２までのビット列「０１０１０１０１０」の前に「１１１１１１」を加えた「１１１１１１０１０１０１０１０」を、最長一致文字列の位置として復元する。
【０１８６】
また、第２伸長部２２６は、位置Ｘ２以降のビットと拡張ハフマン木３０とを比較して、拡張ハフマン木３０の葉を特定し、特定した葉に含まれる最長一致文字列の長さを特定する。上記の処理を実行することで、第２伸長部２２６は、最長一致文字列の位置と長さを特定する。第２伸長部２２６は、位置と長さに対応する文字列を参照部である記憶領域Ｂ２から取り出し、取り出した文字列を伸長データとする。第２伸長部２２６は、伸長データを、参照部である記憶領域Ｂ２、および、記憶領域Ｂ３に格納し、参照部更新部２２７およびファイルライト部２２８に出力する。
【０１８７】
また、第２伸長部３２６は、位置Ｘ２以降のビットと拡張ハフマン木５０とを比較して、拡張ハフマン木５０の葉を特定し、特定した葉に含まれる最長一致文字列の長さを特定する。上記の処理を実行することで、第２伸長部３２６は、最長一致文字列の位置と長さを特定する。第２伸長部３２６は、位置と長さに対応する文字列を記憶領域Ｂ２から取り出し、取り出した文字列を伸長データとする。第２伸長部３２６は、伸長データを、参照部である記憶領域Ｂ２、および、記憶領域Ｂ３に格納し、参照部更新部３２７およびファイルライト部３２８に出力する。
【０１８８】
参照部更新部３２７およびファイルライト部３２８に関する説明は、実施例１の参照部更新部３２７とファイルライト部３２８と同様である。
【０１８９】
続いて、本実施例２に係る圧縮部３００の全体の処理手順は、図１８と同様である。詳細の処理手順として、頻度表６０を生成する処理および拡張ハフマン木５０を生成する処理手順について具体的に説明する。
【０１９０】
図３２は、頻度表および拡張ハフマン木を生成する処理手順を示すフローチャート（２）である。図３２に示すように、圧縮部３００ａは、ファイルＦ１に含まれるデータの出現頻度を計算する（ステップＳ３０１）。圧縮部３００ａは、ファイルＦ１に含まれる最長一致文字列を検出し、最長一致文字列の０の連続数および１の連続数の出現頻度を計算する（ステップＳ３０２）。
【０１９１】
圧縮部３００ａは、文字コードまたは最長一致文字列の長さおよび識別情報「０」を対応付けた葉を生成する（ステップＳ３０３）。圧縮部３００ａは、０の連続数および識別情報「１０」を対応付けた葉を生成する（ステップＳ３０４）。圧縮部３００ｂは、１の連続数および識別情報「１１」を対応付けた葉を生成する（ステップＳ３０５）。
【０１９２】
圧縮部３００ａは、葉を出現頻度の順にソートする（ステップＳ３０６）。圧縮部３００ａは、出現頻度を基にして、２分木の枝をくみあげて拡張ハフマン木５０を生成する（ステップＳ３０７）。
【０１９３】
続いて、本実施例２に係る圧縮部３００ａが、圧縮データを生成する処理手順について具体的に説明する。
【０１９４】
図３３は、圧縮データを生成する処理手順を示すフロートチャート（２）である。図３３に示すように、圧縮部３００ａは、最長一致文字列のデータ量が３バイト以上であるか否かを判定する（ステップＳ３１０）。
【０１９５】
圧縮部３００ａは、３バイト以上である場合には（ステップＳ３１１，Ｙｅｓ）、最長一致文字列の位置は「０」から始まるか否かを判定する（ステップＳ３１２）。圧縮部３００ａは、最長一致文字列の位置が「０」から始まる場合には（ステップＳ３１３，Ｙｅｓ）、最長一致文字列の０の連続数と拡張ハフマン木５０とを比較して、０の連続数をハフマン符号化する（ステップＳ３１４）。
【０１９６】
圧縮部３００ａは、最長一致文字列の長さと拡張ハフマン木５０とを比較して、長さをハフマン符号化する（ステップＳ３１５）。圧縮部３００ａは、ハフマン符号化した０の連続数と、１以降のビット列と、ハフマン符号化した長さを圧縮データとして出力する（ステップＳ３１６）。
【０１９７】
一方、圧縮部３００ａは、最長一致文字列の位置が「０」から始まらない場合には（ステップＳ３１３，Ｎｏ）、最長一致文字列の１の連続数と拡張ハフマン木５０とを比較して、１の連続数をハフマン符号化する（ステップＳ３１７）。
【０１９８】
圧縮部３００ａは、最長一致文字列の長さと拡張ハフマン木５０とを比較して、長さをハフマン符号化する（ステップＳ３１８）。圧縮部３００ａは、ハフマン符号化した１の連続数と、０以降のビット列と、ハフマン符号化した長さを圧縮データとして出力する（ステップＳ３１９）。
【０１９９】
ところで、圧縮部３００ａは、最長一致文字列のデータ量が３バイト未満の場合には（ステップＳ３１１，Ｎｏ）、文字コードと拡張ハフマン木５０とを比較して、文字コードをハフマン符号化したものを圧縮データとして出力する（ステップＳ３２０）。
【０２００】
図３４は、本実施例２に係る伸長部の処理手順を示すフローチャートである。図３４に示すように、図３４に示すように、伸長部３００ｂは、前処理を実行する（ステップＳ４０１）。ステップＳ４０１の前処理において、伸長部３００ｂは、記憶領域Ｂ１、記憶領域Ｂ２および記憶領域Ｂ３を記憶部３００ｃに確保する。
【０２０１】
伸長部３００ｂは、ファイルＦ２とＦ３をオープンし（ステップＳ４０２）、圧縮ファイルＦ２のヘッダから頻度表６０を読み出す（ステップＳ４０３）。伸長部３００ｂは、拡張ハフマン木５０を生成する（ステップＳ４０４）。
【０２０２】
伸長部３００ｂは、圧縮データと拡張ハフマン木５０とを比較し（ステップＳ４０５）、拡張ハフマン木５０の葉の識別情報が「０」であるか否かを判定する（ステップＳ４０６）。
【０２０３】
伸長部３００ｂは、識別情報が「０」である場合には（ステップＳ４０６，Ｙｅｓ）、葉に含まれる文字コードを記憶領域Ｂ２に格納し（ステップＳ４０７）、伸長データの書き込みを行う（ステップＳ４０８）。
【０２０４】
伸長部３００ｂは、圧縮ファイルＦ２の終点でない場合には（ステップＳ４０９，Ｎｏ）、ステップＳ４０５に移行する。一方、伸長部３００ｂは、圧縮ファイルＦ２の終点である場合には（ステップＳ４０９，Ｙｅｓ）、ファイルＦ２とＦ３をクローズする。
【０２０５】
一方、伸長部３００ｂは、識別情報が「０」でない場合には（ステップＳ４０６，Ｎｏ）、識別情報が「１０」であるか否かを判定する（ステップＳ４１１）。伸長部３００ｂは、識別情報が「１０」である場合には（ステップＳ４１１，Ｙｅｓ）、葉に含まれる０の連続数を基に、最長一致文字列の位置および長さを特定する（ステップＳ４１２）。伸長部３００ｂは、最長一致文字列の位置および長さに対応するデータを記憶領域Ｂ２から取得する（ステップＳ４１３）。伸長部３００ｂは、データを記憶領域Ｂ２に格納し（ステップＳ４１４）、ステップＳ４０９に移行する。
【０２０６】
一方、伸長部３００ｂは、識別情報が「１１」である場合には（ステップＳ４１１，Ｎｏ）、葉に含まれる１の連続数を基に、最長一致文字列の位置および長さを特定する（ステップＳ４１５）。伸長部３００ｂは、最長一致文字列の位置および長さに対応する文字列を記憶領域Ｂ２から取得する（ステップＳ４１６）。伸長部３００ｂは、データを記憶領域Ｂ２に格納し（ステップＳ４１７）、ステップＳ４０９に移行する。
【０２０７】
次に、本実施例２にかかる情報処理装置３００の効果について説明する。情報処置装置３００の圧縮部３００ａは、最長一致文字列検索部１０６と同様の処理を行って、ファイル１に対して最長一致文字列検索を実行し、各最長一致文字列の位置を特定する。情報処理装置は、位置を１６ビットの２進数で表した場合に、先頭ビットが０の場合には、位置を０の連続数に変換し、０の連続数の出現頻度を集計する。また、圧縮部３００ａは、先頭ビットが１の場合には、一を１の連続数に変換し、１の連続数の出現頻度を集計する。圧縮部３００ａは、データの出現頻度、０の連続数の出現頻度、１の連続数の出現頻度をまとめた拡張ハフマン木を生成し、この拡張ハフマン木を用いて、圧縮処理を行う。圧縮部３００ａが利用する、この拡張ハフマン木は１種類あり、拡張ハフマン木の葉に識別情報が含まれているため、圧縮データに識別情報が付加されなくても伸長可能であり、圧縮率の低下を防止することができる。
【０２０８】
下記に、本実施形態に用いられるハードウェア及びソフトウェアについて説明する。図３５は、コンピュータ１のハードウェア構成例を示す。コンピュータ１は、例えば、プロセッサ３０１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０２、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０３、ドライブ装置３０４、記憶媒体３０５、入力インターフェース（Ｉ／Ｆ）３０６、入力デバイス３０７、出力インターフェース（Ｉ／Ｆ）３０８、出力デバイス３０９、通信インターフェース（Ｉ／Ｆ）３１０、ＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）インターフェース（Ｉ／Ｆ）３１１およびバス３１２などを含む。それぞれのハードウェアはバス３１２を介して接続されている。
【０２０９】
ＲＡＭ３０２は読み書き可能なメモリ装置であって、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ  ＲＡＭ）やＤＲＡＭ（Ｄｙｎａｍｉｃ  ＲＡＭ）などの半導体メモリ、またはＲＡＭでなくてもフラッシュメモリなどが用いられる。ＲＯＭ３０３は、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）なども含む。ドライブ装置３０４は、記憶媒体３０５に記録された情報の読み出しか書き込みかの少なくともいずれか一方を行なう装置である。記憶媒体３０５は、ドライブ装置３０４によって書き込まれた情報を記憶する。記憶媒体３０５は、例えば、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）などのフラッシュメモリ、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ブルーレイディスクなどの記憶媒体である。また、例えば、コンピュータ１は、複数種類の記憶媒体それぞれについて、ドライブ装置３０４及び記憶媒体３０５を設ける。
【０２１０】
入力インターフェース３０６は、入力デバイス３０７と接続されており、入力デバイス３０７から受信した入力信号をプロセッサ３０１に伝達する回路である。出力インターフェース３０８は、出力デバイス３０９と接続されており、出力デバイス３０９に、プロセッサ３０１の指示に応じた出力を実行させる回路である。通信インターフェース３１０はネットワーク３を介した通信の制御を行なう回路である。通信インターフェース３１０は、例えばネットワークインターフェースカード（ＮＩＣ）などである。ＳＡＮインターフェース３１１は、ストレージエリアネットワークによりコンピュータ１と接続された記憶装置との通信の制御を行なう回路である。ＳＡＮインターフェース３１１は、例えばホストバスアダプタ（ＨＢＡ）などである。
【０２１１】
入力デバイス３０７は、操作に応じて入力信号を送信する装置である。入力信号は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力デバイス３０９は、コンピュータ１の制御に応じて情報を出力する装置である。出力デバイス３０９は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力デバイス３０７及び出力デバイス３０９として用いられる。また、入力デバイス３０７及び出力デバイス３０９は、コンピュータ１と一体になっていてもよいし、コンピュータ１に含まれず、例えば、コンピュータ１に外部から接続する装置であってもよい。
【０２１２】
例えば、プロセッサ３０１は、ＲＯＭ３０３や記憶媒体３０５に記憶されたプログラムをＲＡＭ３０２に読み出し、読み出されたプログラムの手順に従って圧縮部２００ａの処理または伸張部２００ｂの処理を行なう。その際にＲＡＭ３０２はプロセッサ３０１のワークエリアとして用いられる。記憶部２００ｃの機能は、ＲＯＭ３０３および記憶媒体３０５がプログラムファイル（後述のアプリケーションプログラム２４、ミドルウェア２３およびＯＳ２２など）やデータファイル（圧縮対象のファイルＦ１、圧縮されたファイルＦ２など）を記憶し、ＲＡＭ３０２がプロセッサ３０１のワークエリアとして用いられることによって実現される。プロセッサ３０１が読み出すプログラムについては、図３６を用いて説明する。
【０２１３】
図３６は、コンピュータ１で動作するプログラムの構成例を示す。コンピュータ１において、図３５に示すハードウェア群２１（３０１〜３１２）の制御を行なうＯＳ（オペレーティング・システム）２２が動作する。ＯＳ２２に従った手順でプロセッサ３０１が動作して、ハードウェア群２１の制御・管理が行なわれることにより、アプリケーションプログラム２４やミドルウェア２３に従った処理がハードウェア群２１で実行される。さらに、コンピュータ１において、ミドルウェア２３またはアプリケーションプログラム２４が、ＲＡＭ３０２に読み出されてプロセッサ３０１により実行される。
【０２１４】
プロセッサ３０１が、圧縮機能が呼び出された場合に、ミドルウェア２３またはアプリケーションプログラム２４の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア群２１を制御して）圧縮部２００ａの機能が実現される。また、プロセッサ３０１が、伸張機能が呼び出された場合に、ミドルウェア２３またはアプリケーションプログラム２４の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア群２１を制御して）伸張部２００ｂの機能が実現される。圧縮機能および伸張機能は、それぞれアプリケーションプログラム２４自体に含まれてもよいし、アプリケーションプログラム２４に従って呼び出されることで実行されるミドルウェア２３の一部であってもよい。
【０２１５】
アプリケーションプログラム２４（またはミドルウェア２３）の圧縮機能により得られる圧縮ファイルＦ２は、圧縮ファイルＦ２内の圧縮辞書Ｄ１に基づいて部分的に伸張可能である。圧縮ファイルＦ２の途中を伸張する場合には、伸張対象の部分までの圧縮データの伸張処理が抑制されるため、プロセッサ３０１の負荷が抑制される。また、伸張対象の圧縮データを部分的にＲＡＭ３０２上に展開するので、ワークエリアも削減される。
【０２１６】
図３７は、実施形態のシステムにおける装置の構成例を示す。図３７のシステムは、コンピュータ１ａ、コンピュータ１ｂ、基地局２およびネットワーク３を含む。コンピュータ１ａは、無線または有線の少なくとも一方により、コンピュータ１ｂと接続されたネットワーク３に接続している。
【０２１７】
図１２に示す圧縮部２００ａと伸張部２００ｂとは、図３７に示すコンピュータ１ａとコンピュータ１ｂとのいずれに含まれてもよい。コンピュータ１ｂが圧縮部２００ａを含み、コンピュータ１ａが伸張部２００ｂを含んでもよいし、コンピュータ１ｂが圧縮部２００ａを含み、コンピュータ１ａが伸張部２００ｂを含んでもよい。また、コンピュータ１ａとコンピュータ１ｂとの双方が、圧縮部２００ａおよび伸張部２００ｂを備えてもよい。
【０２１８】
以下、上述の実施形態における変形例の一部を説明する。下記の変形例のみでなく、本発明の本旨を逸脱しない範囲の設計変更は適宜行われうる。圧縮処理の対象は、ファイル内のデータ以外にも、システムから出力される監視メッセージなどでもよい。例えば、バッファに順次格納される監視メッセージを上述の圧縮処理により圧縮し、ログファイルとして格納するなどの処理が行なわれる。また、例えば、データベース内のページ単位に圧縮が行なわれてもよいし、複数のページをまとめた単位で圧縮が行なわれてもよい。
【０２１９】
また、上述の圧縮処理の対象となるデータは、上述の通り、文字情報に限定されるものでない。数値のみの情報であってもよいし、画像・音声などのデータに対して上述の圧縮処理を用いてもよい。例えば、音声合成により得られるデータを多量に含むファイルなどは、データ内に繰り返しを多く含むため動的辞書により圧縮率が向上することが見込まれる。当然その一部のみが利用される場合には、部分伸張により余分な伸張処理が抑制される。また、固定カメラにより撮影された動画像についても各フレームの画像が似たものになることから繰り返しが多く含まれる。そのため、上述の圧縮処理を適用することにより、文書データや音声データと同様の効果を得ることができる。
【０２２０】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２２１】
（付記１）コンピュータに、
あるデータに対して最長一致文字列検索をおこない、検索された最長一致文字列のうち所定長未満となる第１データそれぞれの出現頻度と、最長一致文字列のうち所定長以上となる第２データの位置情報それぞれの出現頻度とを基にして、圧縮符号、第１識別情報および前記第１データをそれぞれ対応付けた情報と、圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を生成し、
圧縮対象のデータに対して最長一致文字列検索をおこない、最長一致文字列が所定長未満の場合には、前記頻度情報に含まれる第１データのうち、前記最長一致文字列の第１データに対応付けられた圧縮符号を出力し、
前記最長一致文字列が所定長以上の場合には、前記頻度情報に含まれる第２データの位置情報のうち、前記最長一致文字列の位置情報と一致する位置情報に対応付けられた圧縮符号、および、前記頻度情報に含まれる第１データのうち最長一致文字列の長さの情報に対応付けられた圧縮符号を出力する
各処理を実行させることを特徴とする圧縮プログラム。
【０２２２】
（付記２）前記頻度情報を生成する処理は、前記第１データおよび該第１データの出現頻度と、スライド窓の先頭から前記第２データまでの位置情報を縮約した情報および前記位置情報の出現頻度とを含むハフマン木を生成することを特徴とする付記１に記載の圧縮プログラム。
【０２２３】
（付記３）前記頻度情報を生成する処理は、前記スライド窓の先頭から前記第２データが出現するまでの位置をｎビット固定長で表現した場合における先頭ビットから１または０が連続する数を示す連続数を、前記縮約した情報として前記ハフマン木の葉に格納することを特徴とする付記２に記載の圧縮プログラム。
【０２２４】
（付記４）前記圧縮対象のデータから出力される圧縮ファイルの一部に、前記ハフマン木に対応した出現頻度情報を含むことを特徴とする付記２に記載の圧縮プログラム。
【０２２５】
（付記５）コンピュータに、
入力した圧縮ファイルの一部から、所定長未満となる第１データの出現頻度と、各最長一致文字列のうち所定長以上となる第２データの位置情報の出現頻度とを基にして生成された、圧縮符号、第１識別情報および前記第１データを対応付けた情報と、圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を取得し、
前記圧縮ファイルからデータを読み出し、読み出したデータと前記頻度情報とを基にして、伸長データを生成する、
処理を実行させることを特徴とする伸長プログラム。
【０２２６】
（付記６）前記第１データおよび出現頻度と、前記位置情報の出現頻度とを構造に反映した、前記１データまたは前記位置情報を葉に含むハフマン木を、前記頻度情報より生成可能であり、
前記ハフマン木の前記第１データを含む葉には第１識別子が格納され、前記位置情報を含む葉には第２識別子が格納されており、
前記伸長する処理は、伸長対象のデータを読み出して前記ハフマン木を辿り、データに対応する前記ハフマン木の葉を特定し、特定したハフマン木の葉に第１識別情報が含まれているか第２識別情報が含まれているかを判定し、
第１識別子が含まれている場合には、葉に含まれるデータを出力し
第２識別子が含まれている場合には、葉に含まれる位置情報に基づいてデータを出力することを特徴とする付記５に記載の伸長プログラム。
【０２２７】
（付記７）コンピュータが実行する圧縮方法であって、
あるデータに対して最長一致文字列検索をおこない、検索された最長一致文字列のうち所定長未満となる第１データそれぞれの出現頻度と、最長一致文字列のうち所定長以上となる第２データの位置情報それぞれの出現頻度とを基にして、圧縮符号、第１識別情報および前記第１データをそれぞれ対応付けた情報と、圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を生成し、
圧縮対象のデータに対して最長一致文字列検索をおこない、最長一致文字列が所定長未満の場合には、前記頻度情報に含まれる第１データのうち、前記最長一致文字列の第１データに対応付けられた圧縮符号を出力し、
前記最長一致文字列が所定長以上の場合には、前記頻度情報に含まれる第２データの位置情報のうち、前記最長一致文字列の位置情報と一致する位置情報に対応付けられた圧縮符号、および、前記頻度情報に含まれる第１データのうち最長一致文字列の長さの情報に対応付けられた圧縮符号を出力する
各処理を実行させることを特徴とする圧縮方法。
【０２２８】
（付記８）前記頻度情報を生成する処理は、前記第１データおよび該第１データの出現頻度と、スライド窓の先頭から前記第２データまでの位置情報を縮約した情報および前記位置情報の出現頻度とを含むハフマン木を生成することを特徴とする付記７に記載の圧縮方法。
【０２２９】
（付記９）前記頻度情報を生成する処理は、前記スライド窓の先頭から前記第２データが出現するまでの位置をｎビット固定長で表現した場合における先頭ビットから１または０が連続する数を示す連続数を、前記縮約した情報として前記ハフマン木の葉に格納することを特徴とする付記７に記載の圧縮方法。
【０２３０】
（付記１０）前記圧縮対象のデータから出力される圧縮ファイルの一部に、前記ハフマン木に対応した出現頻度情報を含むことを特徴とする付記８に記載の圧縮方法。
【０２３１】
（付記１１）コンピュータが実行する伸長方法であって、
入力した圧縮ファイルの一部から、所定長未満となる第１データの出現頻度と、各最長一致文字列のうち所定長以上となる第２データの位置情報の出現頻度とを基にして生成された、圧縮符号、第１識別情報および前記第１データを対応付けた情報と、圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を取得し、
前記圧縮ファイルからデータを読み出し、読み出したデータと前記頻度情報とを基にして、伸長データを生成する、
各処理を実行することを特徴とする伸長方法。
【０２３２】
（付記１２）前記第１データおよび出現頻度と、前記位置情報の出現頻度とを構造に反映した、前記１データまたは前記位置情報を葉に含むハフマン木を、前記頻度情報より生成可能であり、
前記ハフマン木の前記第１データを含む葉には第１識別子が格納され、前記位置情報を含む葉には第２識別子が格納されており、
前記伸長する処理は、伸長対象のデータを読み出して前記ハフマン木を辿り、データに対応する前記ハフマン木の葉を特定し、特定したハフマン木の葉に第１識別情報が含まれているか第２識別情報が含まれているかを判定し、
第１識別子が含まれている場合には、葉に含まれるデータを出力し
第２識別子が含まれている場合には、葉に含まれる位置情報に基づいてデータを出力することを特徴とする付記１１に記載の伸長方法。
【０２３３】
（付記１３）あるデータに対して最長一致文字列検索をおこない、検索された最長一致文字列のうち所定長未満となる第１データそれぞれの出現頻度と、最長一致文字列のうち所定長以上となる第２データの位置情報それぞれの出現頻度とを基にして、圧縮符号、第１識別情報および前記第１データをそれぞれ対応付けた情報と、圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を生成する生成部と、
圧縮対象のデータに対して最長一致文字列検索をおこない、最長一致文字列が所定長未満の場合には、前記頻度情報に含まれる第１データのうち、前記最長一致文字列の第１データに対応付けられた圧縮符号を出力し、前記最長一致文字列が所定長以上の場合には、前記頻度情報に含まれる第２データの位置情報のうち、前記最長一致文字列の位置情報と一致する位置情報に対応付けられた圧縮符号、および、前記頻度情報に含まれる第１データのうち、最長一致文字列の長さの情報に対応付けられた圧縮符号を出力する符号化部と
を有することを特徴とする圧縮装置。
【０２３４】
（付記１４）前記生成部は、前記第１データおよび該第１データの出現頻度と、スライド窓の先頭から前記第２データまでの位置情報を縮約した情報および前記位置情報の出現頻度とを含むハフマン木を生成することを特徴とする付記１３に記載の圧縮装置。
【０２３５】
（付記１５）符号化部は、前記スライド窓の先頭から前記第２データが出現するまでの位置をｎビット固定長で表現した場合における先頭ビットから１または０が連続する数を示す連続数を、前記縮約した情報として前記ハフマン木の葉に格納することを特徴とする付記１２に記載の圧縮装置。
【０２３６】
（付記１６）前記圧縮対象のデータから出力される圧縮ファイルの一部に、前記ハフマン木に対応した出現頻度情報を含むことを特徴とする付記１４に記載の圧縮装置。
【０２３７】
（付記１７）入力した圧縮ファイルの一部から、所定長未満となる第１データの出現頻度と、各最長一致文字列のうち所定長以上となる第２データの位置情報の出現頻度とを基にして生成された、圧縮符号、第１識別情報および前記第１データを対応付けた情報と、圧縮符号、第２識別情報および前記位置情報を対応付けた情報とを含む頻度情報を取得し、前記圧縮ファイルからデータを読み出し、読み出したデータと前記頻度情報とを基にして、伸長データを生成する伸長部
を有することを特長とする伸長装置。
【０２３８】
（付記１８）前記第１データおよび出現頻度と、前記位置情報の出現頻度とを構造に反映した、前記１データまたは前記位置情報を葉に含むハフマン木を、前記頻度情報より生成可能であり、前記ハフマン木の前記第１データを含む葉には第１識別子が格納され、前記位置情報を含む葉には第２識別子が格納されており、
前記伸長部は、伸長対象のデータを読み出して前記ハフマン木を辿り、データに対応する前記ハフマン木の葉を特定し、特定したハフマン木の葉に第１識別情報が含まれているか第２識別情報が含まれているかを判定し、
第１識別子が含まれている場合には、葉に含まれるデータを出力し
第２識別子が含まれている場合には、葉に含まれる位置情報に基づいてデータを出力することを特徴とする付記１７に記載の伸長装置。
【符号の説明】
【０２３９】
２００    情報処理装置
２００ａ  圧縮部
２００ｂ  伸長部
【図１】
0006511836.tif 000002
【図２】
0006511836.tif 000003
【図３】
0006511836.tif 000004
【図４】
0006511836.tif 000005
【図５】
0006511836.tif 000006
【図６】
0006511836.tif 000007
【図７】
0006511836.tif 000008
【図８】
0006511836.tif 000009
【図９】
0006511836.tif 000010
【図１０】
0006511836.tif 000011
【図１１】
0006511836.tif 000012
【図１２】
0006511836.tif 000013
【図１３】
0006511836.tif 000014
【図１４】
0006511836.tif 000015
【図１５】
0006511836.tif 000016
【図１６】
0006511836.tif 000017
【図１７】
0006511836.tif 000018
【図１８】
0006511836.tif 000019
【図１９】
0006511836.tif 000020
【図２０】
0006511836.tif 000021
【図２１】
0006511836.tif 000022
【図２２】
0006511836.tif 000023
【図２３】
0006511836.tif 000024
【図２４】
0006511836.tif 000025
【図２５】
0006511836.tif 000026
【図２６】
0006511836.tif 000027
【図２７】
0006511836.tif 000028
【図２８】
0006511836.tif 000029
【図２９】
0006511836.tif 000030
【図３０】
0006511836.tif 000031
【図３１】
0006511836.tif 000032
【図３２】
0006511836.tif 000033
【図３３】
0006511836.tif 000034
【図３４】
0006511836.tif 000035
【図３５】
0006511836.tif 000036
【図３６】
0006511836.tif 000037
【図３７】
0006511836.tif 000038