(57)【特許請求の範囲】
【請求項１】
コンピュータに、
複数のファイルにおける単語の頻度情報に基づき、出現頻度が所定順位の単語の出現頻度よりも大きい高頻度単語について出現頻度が高いほど短い所定符号長以下の可変長の圧縮符号を割り当て、高頻度単語と可変長の圧縮符号とを対応付けて登録した辞書を生成し、
符号化の対象となる対象ファイルから単語を抽出し、
抽出した単語が前記辞書に登録された高頻度単語である場合、当該高頻度単語に対応する圧縮符号で当該単語を符号化し、抽出した単語が前記辞書に登録された高頻度単語ではない場合、抽出された単語に対して当該単語が前記対象ファイルから最初に抽出された際の順に前記所定符号長の圧縮符号を動的に割り当てて当該単語を符号化する
処理を実行させることを特徴とする符号化プログラム。
【請求項２】
請求項１に記載の符号化プログラムであって、出現頻度が、前記所定順位の単語の出現頻度よりも小さい単語のうち、出現頻度が第２の所定順位の単語の出現頻度よりも大きい単語に前記所定符号長の圧縮符号を割り当て、出現頻度が前記第２の所定順位の単語の出現頻度より小さい単語に、前記所定符号長と異なる第２の符号長の圧縮符号を割り当てて符号化することを特徴とする符号化プログラム。  
【請求項３】
コンピュータが、
複数のファイルにおける単語の頻度情報に基づき、出現頻度が所定順位の単語の出現頻度よりも大きい高頻度単語について出現頻度が高いほど短い所定符号長以下の可変長の圧縮符号を割り当て、高頻度単語と可変長の圧縮符号とを対応付けて登録した辞書を生成し、
符号化の対象となる対象ファイルから単語を抽出し、
抽出した単語が前記辞書に登録された高頻度単語である場合、当該高頻度単語に対応する圧縮符号で当該単語を符号化し、抽出した単語が前記辞書に登録された高頻度単語ではない場合、抽出された単語に対して当該単語が前記対象ファイルから最初に抽出された際の順に前記所定符号長の圧縮符号を動的に割り当てて当該単語を符号化する
処理を実行することを特徴とする符号化方法。  
【請求項４】
複数のファイルにおける単語の頻度情報に基づき、出現頻度が所定順位の単語の出現頻度よりも大きい高頻度単語について出現頻度が高いほど短い所定符号長以下の可変長の圧縮符号を割り当て、高頻度単語と可変長の圧縮符号とを対応付けて登録した辞書を生成する生成部と、
符号化の対象となる対象ファイルから単語を抽出する抽出部と、
前記抽出部により抽出した単語が前記辞書に登録された高頻度単語である場合、当該高頻度単語に対応する圧縮符号で当該単語を符号化し、抽出した単語が前記辞書に登録された高頻度単語ではない場合、抽出された単語に対して当該単語が前記対象ファイルから最初に抽出された際の順に前記所定符号長の圧縮符号を動的に割り当てて当該単語を符号化する符号化部と、
を有する符号化装置。 
【請求項５】
コンピュータが、
第１のファイルを符号化する際に、複数のファイルにおける単語の頻度情報に基づき、出現頻度が所定順位の単語の出現頻度よりも大きい高頻度単語については、出現頻度が高いほど短い所定符号長以下の可変長の圧縮符号で符号化し、前記頻度情報における出現頻度が前記所定順位の単語の出現頻度よりも小さい低頻度単語については、前記第１のファイルに出現した順に、前記所定符号長の圧縮符号を所定規則で動的に割り当てて符号化し、
前記第１のファイルに出現した順に前記低頻度単語を並べた辞書を、前記第１のファイルを符号化した符号化ファイルに格納する
処理を実行することを特徴とする符号化方法。 
【請求項６】
コンピュータが、
第１のファイルを符号化した符号化ファイルであって、複数のファイルにおける単語の頻度情報に基づき、出現頻度が所定順位の単語の出現頻度よりも大きい高頻度単語については、出現頻度が高いほど短い所定符号長以下の可変長の圧縮符号で符号化され、前記頻度情報における出現頻度が前記所定順位の単語の出現頻度よりも小さい低頻度単語については、前記第１のファイルに出現した順に、前記所定符号長の圧縮符号を所定規則で動的に割り当てて符号化され、前記第１のファイルに出現した順に前記低頻度単語を並べた辞書が格納された前記符号化ファイルを伸長する際、前記符号化ファイルの前記辞書に並んだ前記低頻度単語に対して並んだ順に前記所定符号長の圧縮符号を前記所定規則で動的に割り当て、
割り当てた圧縮符号を用いて前記符号化ファイルから前記低頻度単語を伸長する
処理を実行することを特徴とする伸長方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化プログラム、符号化方法および符号化装置に関する。
【背景技術】
【０００２】
静的辞書を用いて圧縮対象のテキストを単語ごとに圧縮する技術が存在する。静的辞書は、各々の単語に圧縮符号を対応付けた辞書である。かかる技術では、テキスト群から抽出された単語ごとに出現頻度が集計される。そして、出現頻度に応じた符号長の圧縮符号が各単語に対応付けられて静的辞書に登録される。静的辞書では、出現頻度の高い単語に対して短い符号長が割り当てられ、出現頻度の低い単語に対して長い符号長が割り当てられる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開昭６２−０１７８７２号公報
【特許文献２】特開平１１−２１５００７号公報
【特許文献３】特開２０００−２６９８２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、母集団の出現頻度に基づいて符号長を割り当てると、出現頻度の低い単語に割り当てられる符号長が長くなるため、圧縮率が低下する。
【０００５】
一つの側面では、圧縮処理時に単語に割り当てる符号長を改善させる符号化プログラム、符号化方法および符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
第１の案では、符号化プログラムは、コンピュータに、複数のファイルにおける単語の頻度情報より生成された符号割当て規則に基づき、前記複数のファイルに含まれる第１のファイルを符号化する際に、前記頻度情報における出現頻度が、所定順位の単語の出現頻度よりも大きい各単語に対し、前記符号割当て規則に応じて符号化し、前記頻度情報における出現頻度が、前記所定順位の単語の出現頻度よりも小さい単語の少なくとも一部に対し、前記符号割当て規則による符号と異なる符号割当て規則で、かつ、第１の符号長で符号化する処理を実行させる。
【発明の効果】
【０００７】
本発明の１実施態様によれば、圧縮処理時に単語に割り当てる符号長を改善できるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】図１は、参考例１の辞書を説明するための図である。
【図２】図２は、参考例１の圧縮を説明するための図である。
【図３】図３は、実施例１の辞書を説明するための第１の図である。
【図４】図４は、実施例１の圧縮を説明するための図である。
【図５】図５は、情報処理装置の各処理部と記憶部との関係を説明するための図である。
【図６】図６は、実施例１の圧縮処理に係るシステム構成の一例を示す図である。
【図７】図７は、圧縮辞書の作成を説明するための第１の図である。
【図８】図８は、圧縮辞書の作成を説明するための第２の図である。
【図９】図９は、圧縮辞書を作成を説明するための第３の図である。
【図１０】図１０は、圧縮辞書の文字・記号部を説明するための図である。
【図１１】図１１は、実施例１の圧縮を説明するための第２の図である。
【図１２】図１２は、圧縮処理の全体の流れを説明するためのフロー図である。
【図１３】図１３は、標本化処理の流れの例を示すフロー図である。
【図１４】図１４は、１パス圧縮処理の流れの例を示すフロー図である。
【図１５】図１５は、実施例１の伸長処理に係るシステム構成の一例を示す図である。
【図１６】図１６は、伸長辞書を説明するための図である。
【図１７】図１７は、実施例１の伸長を説明するための図である。
【図１８】図１８は、圧縮符号を伸長する処理の流れの例を示すフロー図である。
【図１９】図１９は、低頻度領域の拡張を説明するための図である。
【図２０】図２０は、実施例１の情報処理装置のハードウェア構成を示す図である。
【図２１】図２１は、コンピュータで動作するプログラムの構成例を示す図である。
【図２２】図２２は、実施形態のシステムにおける装置の構成例を示す図である。
【発明を実施するための形態】
【０００９】
以下に、本願の開示する符号化プログラムの実施例、符号化方法および符号化装置を図面に基づいて詳細に説明する。なお、この実施例によりこの権利範囲が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１０】
（参考例１の辞書）
図１を用いて、参考例１の辞書について説明する。図１は、参考例１の辞書を説明するための図である。参考例１に係る辞書は、ファイルＡ、ファイルＢ、ファイルＣ等を含む母集団２１のファイルから収集した単語を有する。例えば、辞書は、様々の文書や一般的な辞典を母集団２１として登録された約１９万語の単語を有する。図１には、辞書に登録された単語の分布を分布表１０ａが示されている。ここで、母集団とは、辞書に登録する単語を収集するために用いられる複数のテキストファイルである。分布表１０ａの縦軸は、単語数を示す。分布表１０ａでは、母集団２１において出現頻度が高い単語ほど単語数が小さく、出現頻度が低い単語ほど単語数が大きい。すなわち、単語数は、母集団における単語の出現順位を表す。例えば、母集団２１において比較的出現頻度が高い「the」は、単語数「10語」に位置し、比較的出現頻度が低い「zymosis」は、単語数「189,000語」に位置する。なお、母集団２１において最も出現頻度の低い単語は、「190,000語」に位置する。
【００１１】
分布表１０ａの横軸は、符号長を示す。参考例１の辞書に含まれる各単語には、母集団２１における出現頻度に応じた符号長が割当てられる。母集団２１において出現頻度の高い単語に対して短い符号長が割り当てられ、出現頻度の低い単語に対して長い符号長が割り当てられる。例えば、分布表１０のように、出現頻度が高い「the」よりも出現頻度が低い「zymosis」に対して長い符号長が割当てられる。以下、母集団において出現頻度の順位が１〜８０００位までの単語を高頻度単語と呼び、出現頻度の順位が８００１位以下の単語を低頻度単語と呼ぶ。なお、高頻度単語と低頻度単語を分ける境界となっている出現順位８０００位は、あくまで一例であり、他の出現順位を境界としてもよい。
【００１２】
分布表１０ａの横縞は、母集団２１に出現した単語に対応する単語数の位置を表す。横縞の密度が高い部分は、出現する単語が多く、分布密度が高いことを表す。一方、横縞の密度が低い部分は、出現する単語が少なく、分布密度が低いことを表す。参考例１に係る辞書には、母集団から収集した１９万語の単語が全て登録される。このため、分布表１０ａには、単語数１〜１９００００語の高頻度単語から低頻度単語までの領域にわたって横縞の密度が高く、一様に示されている。
【００１３】
このように、分布表１０ａによれば、母集団における単語の出現頻度に応じて高頻度単語および低頻度単語に符号長が割当てられている。しかし、分布表１０ａに見られるように低頻度単語に割当てられる符号長が長くなるという問題があった。例えば、低頻度単語である「zymosis」は、出現順位が１８９０００位であり、低頻度単語の中でも出現順位が低いので、割り当てられる符号長が長い。
【００１４】
一方、圧縮ファイル２３は、圧縮対象のファイルを符号化し、圧縮したファイルである。圧縮ファイル２３は、辞書に登録されている１９万語の単語のうちの３２０００語程度の単語を有するものとする。図１には、辞書に含まれる単語のうち、圧縮ファイル２３にも含まれる単語の分布表１０ｂが示されている。分布表１０ｂは、分布表１０ａと同様に、縦軸が単語数で、横軸が符号長を示す。単語数１〜８０００語の高頻度単語は、圧縮ファイル２３に大部分出現する。このため、分布表１０ｂでは、単語数１〜８０００語の高頻度単語の領域において横縞が、一様に、密度が高く示されている。一方、単語数８００１〜１９００００語の低頻度単語は、圧縮ファイル２３に一部しか出現しない。このため、分布表１０ｂでは、単語数８００１〜１９００００語の低頻度単語の領域において横縞が、まばらに、密度が低く示されている。
【００１５】
ここで、例えば、圧縮ファイル２３の各単語に、母集団２１における出現頻度に応じた符号長を割り当てた場合、圧縮ファイル２３では、低頻度単語の符号長の変化が大きく、単語数の少ない低頻度単語に対して長い符号長が割り当てられる。例えば、「zymosis」のように分布表２０ｂの底辺付近に位置する低頻度単語は、長い符号長が割り当てられる。このため、各単語の圧縮に割り当てられた符号長の圧縮符号を用いて圧縮した場合、圧縮ファイル２３は、出現順位が低い低頻度単語に割り当てる可変長符号が冗長になるため、圧縮率が低下する。
【００１６】
参考例１の圧縮の流れをより具体的に説明する。図２は、参考例１の圧縮を説明するための図である。符号化木２２は、母集団２１から抽出された約１９万語の単語に対し、それぞれに圧縮符号を割当てることで生成される辞書である。母集団２１は、ファイルＡ、ファイルＢ、ファイルＣ等を含む複数のテキストファイルである。母集団２１から「the」「zymosis」等の単語が抽出される。抽出された各単語には、母集団における出現頻度に応じた符号長の可変長符号が割当てられる。ここで、可変長符号とは、符号長が可変の圧縮符号である。例えば、高頻度単語の「the」に対して６ビットの可変長符号が割当てられる。また、低頻度単語の「zymosis」に対して２４ビットの可変長符号が割当てられる。各単語に割当てられた可変長符号は、符号化木２２に登録される。このようにして、符号化木２２が生成される。
【００１７】
圧縮ファイル２３は、対象ファイル２０から抽出した各単語に対し、符号化木２２に登録されている可変長符号を割当てることで作成される。対象ファイルとは、圧縮処理の対象となるファイルである。例えば、対象ファイル２０から「the」「zymosis」が抽出される。対象ファイル２０から抽出された高頻度単語「the」に対して、符号化木２２に登録された６ビットの可変長符号「000001」が割当てられ、圧縮ファイル２３に出力される。また、対象ファイル２０から抽出された低頻度単語「zymosis」に対して、符号化木２２に登録された２４ビットの可変長符号「110011001111001010110011」が割当てられ、圧縮ファイル２３に出力される。
【００１８】
このように、出現順位が低い低頻度単語に割当てる可変長符号が冗長になるため、対象ファイル２０から圧縮ファイル２３を生成したときの圧縮率が低下するという問題があった。
【００１９】
（実施例１の辞書）
次に、図３を用いて、実施例１の辞書について説明する。図３は、実施例１の辞書を説明するための第１の図である。図３の例に示される分布表１１ａ，１１ｂは、図１と同様に、縦軸が単語数で、横軸が符号長を示す。
【００２０】
実施例１に係る情報処理装置１００は、ファイルＡ、ファイルＢ、ファイルＣ等を含む母集団５１に基づいて辞書を生成する。母集団２１は、符号化するファイルを含んでもよい。ここで、生成された辞書には約１９万語の単語が登録されているものとし、圧縮ファイル２３には、辞書に登録されている１９万語の単語のうちの３２０００語の単語が含まれるものとする。辞書に含まれる１９万語の単語のうち、圧縮ファイル２３にも共通して含まれる３２０００語の単語の分布を分布表１１ａに示す。なお、分布表１１ａは、図１の参考例１に係る分布表１０ｂと同じである。
【００２１】
分布表１１ａ内の横縞は、圧縮ファイル２３に出現した単語に対応する単語数の位置を表す。横縞の密度が高い部分は、出現する単語が多く、分布密度が高いことを表す。一方、横縞の密度が低い部分は、出現する単語が少なく、分布密度が低いことを表す。分布表１１ａによると、単語数が１〜８０００語の領域では、横縞の密度が高く、出現する単語の分布密度が高い。一方、単語数が８００１〜１９００００語の領域では、横縞の密度が低く、出現する単語の分布密度が低い。
【００２２】
例えば、辞書において出現順位が１〜８０００位までの「the」「a」「of」等の高頻度単語は、大部分が圧縮ファイル５３に共通して含まれる。このため、分布表１１ａにおいて単語数が１〜８０００語の領域は、単語の分布密度が高い。一方、辞書において出現順位が８００１位以下の「zymosis」等の低頻度単語は、圧縮ファイル５３に共通して含まれる単語が少ない。このため、単語数が８００１〜１９００００語の領域は、出現する単語の分布密度が低い。
【００２３】
情報処理装置１００は、全ての高頻度単語に可変長符号を割当てる。また、情報処理装置１００は、圧縮ファイル２３に含まれる低頻度単語に固定長符号を割当てる。そして、情報処理装置１００は、各単語に割当てた可変長符号および固定長符号を辞書に登録する。なお、情報処理装置１００は、辞書に含まれるが圧縮ファイル２３に含まれない低頻度単語に対して圧縮符号を割当てなくてもよい。
【００２４】
例えば、図３の１１ｂに示す例によると、情報処理装置１００は、圧縮ファイルに含まれる単語のうち、出現順位が１〜８０００位の高頻度単語に対して１〜１６ビットの可変長符号を割当てる。また、情報処理装置１００は、出現順位が８００１〜３２０００位の低頻度単語に対して１６ビットの固定長符号を割当てる。すなわち、情報処理装置１００は、全ての高頻度単語に対して「0000h」〜「9FFFh」までの可変長符号を割当て、圧縮ファイル２３に含まれる低頻度単語に対して「A000h」〜「FFFFh」までの固定長符号を割当てる。辞書における圧縮ファイル５３に含まれる単語の分布を分布表１１ｂに示す。分布表１１ｂによると、全体的に横縞の密度が高く、全体的に単語の分布密度が高いことが分かる。
【００２５】
情報処理装置１００は、分布表１１ｂに示されように、高頻度単語に対して可変長符号を割当て、低頻度単語に対して固定長符号を割当てた辞書を用いて圧縮ファイル２３を生成する。これにより、情報処理装置１００は、圧縮ファイル２３に含まれる低頻度単語の符号長を短くすることができる。例えば、図３の例に示されるように、分布表１１ａの「zymosis」の符号長よりも、分布表１１ｂの「zymosis」の符号長の方が短い。このように、情報処理装置１００は、参考例１に係る辞書を用いた場合よりも、実施例１に係る辞書を用いた場合の方が、低頻度単語に割当てる圧縮符号の符号長を短くできる。
【００２６】
次に、図４を用いて、実施例１の情報処理装置１００が対象ファイル５０に含まれる単語を符号化して圧縮する圧縮処理を説明する。図４は、実施例１の圧縮を説明するための図である。まず、情報処理装置１００は、ケヤキ木５２に、母集団５１に含まれる単語を登録する。例えば、情報処理装置１００は、ケヤキ木５２に、様々の文書や一般的な辞典に登録された約１９万語の単語を登録する。ここで、ケヤキ木５２は、実施例１に係る辞書である。母集団５１には、対象ファイル５０が含まれてもよい。情報処理装置１００は、ケヤキ木５２に登録されている単語のうち、対象ファイル５０に含まれる「the」「zymosis」等の単語に対して可変長符号または固定長符号を割当てる。
【００２７】
情報処理装置１００は、母集団５１から抽出された各単語に関し、対象ファイル５０における出現頻度を集計する。情報処理装置１００は、母集団５１から抽出された単語のうち、対象ファイル５０における出現順位が１〜８０００位の高頻度単語に１〜１６ビットまでの可変長符号を割当て、可変長符号をケヤキ木５２に登録する。例えば、情報処理装置１００は、高頻度単語である「the」に６ビットの可変長符号「000001」を割当て、可変長符号「000001」をケヤキ木５２に登録する。
【００２８】
次に、情報処理装置１００は、ケヤキ木５２に基づいて対象ファイル５０を圧縮し、圧縮ファイル５３を生成する処理を実行する。まず、情報処理装置１００は、対象ファイル５０を読込み、対象ファイル５０から高頻度単語「the」を抽出する。情報処理装置１００は、抽出された「the」に対して、ケヤキ木５２に登録された６ビットの可変長符号「000001」を割当て、可変長符号「000001」を圧縮ファイル５３に出力する。
【００２９】
次に、情報処理装置１００は、対象ファイル５０を読込み、対象ファイル５０から低頻度単語「zymosis」を抽出する。情報処理装置１００は、低頻度単語「zymosis」に対して１６ビットの固定長符号「1010010011010010」を割当て、低頻度単語「zymosis」に対応付けて固定長符号「1010010011010010」をケヤキ木５２に登録する。さらに、情報処理装置１００は、ケヤキ木５２に登録した固定長符号「1010010011010010」を圧縮ファイル５３に出力する。なお、情報処理装置１００は、次回対象ファイル５０から低頻度単語「zymosis」を抽出した場合、「zymosis」は既にケヤキ木５２に登録されているので、ケヤキ木５２から固定長符号「1010010011010010」を取得し、圧縮ファイル５３に出力する。
【００３０】
このように、情報処理装置１００は、対象ファイル５０から抽出した低頻度単語に固定長符号を割当て、低頻度単語に割当てた固定長符号をケヤキ木５２に登録するとともに、ケヤキ木５２に登録された固定長符号を圧縮ファイル５３に出力することで、１パスでファイルを圧縮することができる。
【００３１】
（実施例１の圧縮処理に関する処理部の構成）
図５を用いて、情報処理装置１００の各処理部と記憶部との関係について説明する。なお、情報処理装置１００は、符号化装置の一例である。図５は、情報処理装置の各処理部と記憶部との関係を説明するための図である。図５の例に示すように、情報処理装置１００の記憶部１２０は、圧縮部１１０と伸張部１５０とに接続される。圧縮部１１０は、対象ファイルを圧縮する。伸長部１５０は、圧縮ファイルを伸長する。記憶部１２０は例えば、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリなどの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。
【００３２】
また、情報処理装置１００は、圧縮部１１０と、伸張部１５０とを有する。圧縮部１１０および伸張部１５０の機能は例えば、ＣＰＵ（Central  Processing  Unit）が所定のプログラムを実行することで実現することができる。また、圧縮部１１０および伸張部１５０の機能は例えば、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路により実現することができる。
【００３３】
図６を用いて、実施例１の圧縮処理に係るシステム構成について説明する。図６は、実施例１の圧縮処理に係るシステム構成の一例を示す図である。図６の例に示されるように、情報処理装置１００は、圧縮部１１０と、記憶部１２０とを有する。圧縮部１１０は、標本化部１１１、第一ファイルリード部１１２、辞書生成部１１３、第二ファイルリード部１１４、判定部１１５、単語符号化部１１６、文字符号化部１１７およびファイルライト部１１８を有する。記憶部１２０は、圧縮辞書１２１および圧縮ファイル１２５を有する。圧縮ファイル１２５は、圧縮データ１２６、頻度表１２７および動的辞書１２８を有する。
【００３４】
圧縮部１１０は、対象ファイルにおける出現頻度が所定順位以上の各単語に、所定符号長以下の可変長の圧縮符号を割り当て、出現頻度が所定順位未満の各単語に、所定符号長の圧縮符号を割り当てる。さらに、圧縮部１１０は、各単語に割り当てられた圧縮符号によって対象ファイルを圧縮する。例えば圧縮部１１０は、１以上のファイルを有する母集団から複数の単語を取得し、母集団から取得された複数の単語のうち、対象ファイルに含まれる各単語に圧縮符号を割り当てる。以下、圧縮部１１０の各処理部について詳細に説明する。
【００３５】
（圧縮部１１０の各処理部について）
圧縮部１１０は、標本化部１１１、第一ファイルリード部１１２、辞書生成部１１３、第二ファイルリード部１１４、判定部１１５、単語符号化部１１６、文字符号化部１１７およびファイルライト部１１８を有する。以下、圧縮部１１０の各処理部について説明する。
【００３６】
標本化部１１１は、母集団から収集した単語を圧縮辞書１２１ａに登録する処理部である。標本化部１１１は、母集団に含まれる各テキストファイルから約１９万語の単語を収集し、収集した各単語を基礎単語として登録する。標本化部１１１は、圧縮辞書１２１ａにおいて基礎単語がアルファベット順に格納されるように、登録した基礎単語を並び替える。標本化部１１１は、圧縮辞書１２１ａにおいて、基礎単語と、２グラムおよびビットマップとを基礎単語へのポインタによって対応付ける。
【００３７】
標本化部１１１は、登録された各基礎単語に対して３バイトの静的コードを割り当てる。静的コードとは、母集団から収集された各単語に一意に割当てられる３バイトの単語コードである。例えば、標本化部１１１は、基礎単語「able」に対して静的コード「A0007Bh」を割当てる。また、標本化部１１１は、基礎単語「about」に対して静的コード「A00091h」を割当てる。
【００３８】
基礎単語に静的コードを割当てた段階の圧縮辞書１２１ａについて説明する。図７は、圧縮辞書の作成を説明するための第１の図である。図７の例に示されるように、圧縮辞書１２１ａは、２グラムと、ビットマップと、基礎単語と、静的コードと、動的コードと、出現回数と、符号長と、圧縮符号とを対応付ける。「２グラム」は、各単語に含まれる連字である。例えば、「able」は、「ab」「bl」「le」に対応する２グラムを含む。
【００３９】
「ビットマップ」は、２グラムが含まれる基礎単語の位置を表す。例えば、２グラム「ab」のビットマップが「１＿０＿０＿０＿０」の場合、ビットマップは基礎単語の先頭２文字が「ab」であることを表す。各ビットマップは、基礎単語へのポインタによってそれぞれ基礎単語に対応付けられる。例えば、２グラム「ab」のビットマップ「１＿０＿０＿０＿０」は、「able」および「about」に対応付けられる。
【００４０】
「基礎単語」は、圧縮辞書１２１ａに登録された単語である。例えば、標本化部１１１は、母集団から抽出した約１９万語の各単語を、それぞれ基礎単語として圧縮辞書１２１ａに登録する。「静的コード」は、各基礎単語に一意に割当てられる３バイトの単語コードである。「動的コード」は、対象ファイルに出現する各低頻度単語に割当てられる１６ビット（２バイト）の単語コードである。「出現回数」は、母集団中に基礎単語が出現した回数である。「符号長」は、各基礎単語に割り当てる圧縮符号の長さである。「圧縮符号」は、符号長に対応する圧縮符号である。例えば、「圧縮符号」には、基礎単語の符号長が「6」の場合、６ビットの圧縮符号が格納される。出現回数の集計および符号長の算出に関する詳細は、後述する。なお、図７の例では、各項目のデータがレコードとして関連づけられて記憶されている例を示したが、上記説明において互いに関連づけられた項目どうしの関係が保たれれば、データは他の記憶のされ方をしても構わない。後述する図８〜１０、図１６に関しても同様である。
【００４１】
第一ファイルリード部１１２は、母集団に含まれる各テキストファイルを読込み、母集団における各基礎単語の出現回数を集計する処理部である。まず、第一ファイルリード部１１２は、母集団に含まれるテキストファイルを先頭から順に読み込み、母集団に含まれる各単語を抽出し、抽出した単語と圧縮辞書１２１ａの基礎単語とを比較する。第一ファイルリード部１１２は、母集団から抽出した単語と圧縮辞書１２１ａの基礎単語と比較する際に、２グラムおよびビットマップと基礎単語とを対応付ける基礎単語へのポインタを用いる。第一ファイルリード部１１２は、母集団から単語を抽出する度に、圧縮辞書１２１ａにおいて、母集団から抽出された単語に対応する基礎単語の出現回数をインクリメントすることで、各基礎単語の出現回数を集計する。
【００４２】
次いで、第一ファイルリード部１１２は、集計した各単語の出現回数を基に各々の単語の出現頻度をそれぞれ算出して辞書生成部１１３に出力する。例えば、第一ファイルリード部１１２は、各単語の出現回数を、全単語の出現回数の合計値でそれぞれ除算し、各々の単語の出現頻度を算出する。
【００４３】
なお、第一ファイルリード部１１２は、対象ファイルから圧縮辞書１２１ａに登録されていない単語を抽出した場合、文字・記号部１２１ｄにおいて、抽出した単語に含まれる各文字の出現頻度をインクリメントする。例えば、辞書生成部１１３は、圧縮辞書１２１ａに登録されていない「repertoire」を抽出した場合に「r」「e」「p」「e」「r」「t」「o」「i」「r」「e」の各英文字の出現回数を文字・記号部１２１ｄにおいてそれぞれインクリメントする。なお、文字・記号部１２１ｄに関する詳細は、後述する。
【００４４】
辞書生成部１１３は、出現頻度に応じた圧縮符号を各高頻度単語に対応付けて登録することで圧縮辞書１２１ｂを生成する処理部である。辞書生成部１１３は、圧縮辞書１２１ａに登録されている各単語のうち、出現頻度の順位が１〜８０００位の高頻度単語に関し、符号長を算出する。例えば、辞書生成部１１３は、高頻度単語の符号長ｎを、式（１）に母集団における基礎単語の出現頻度ｘを代入することにより算出する。次いで、辞書生成部１１３は、算出した符号長ｎに対応する可変長符号を基礎単語に割り当てる。辞書生成部１１３は、割当てた可変長符号を基礎単語に対応付けて圧縮辞書１２１ａに登録する。なお、辞書生成部１１３は、式（１）を用いる以外の方法で符号長ｎを特定してもよい。
【００４５】
ｎ＝ｌｏｇ２（１／ｘ）  ・・・（１）
【００４６】
可変長符号を割り当てた段階の圧縮辞書１２１ｂについて説明する。図８は、圧縮辞書の作成を説明するための第２の図である。図８の例に示されるように、圧縮辞書１２１ｂは、２グラムと、ビットマップと、基礎単語と、静的コードと、動的コードと、出現回数と、符号長と、圧縮符号とを対応付ける。圧縮辞書１２１ｂの各要素は、圧縮辞書１２１ａと同一であるので説明を省略する。
【００４７】
辞書生成部１１３は、例えば、高頻度単語「able」「about」「act」に対して式（１）を用いて符号長を割当てる。例えば、辞書生成部１１３は、高頻度単語「able」の出現回数「7」に基づいて符号長「9」を算出する。辞書生成部１１３は、符号長「9」に対応する可変長符号「0101110…」を「able」に割当てる。また、辞書生成部１１３は、高頻度単語「about」の出現回数「5」に基づいて符号長「10」を算出する。辞書生成部１１３は、符号長「10」に対応する可変長符号「1000001…」を「about」に割当てる。また、辞書生成部１１３は、高頻度単語「act」の出現回数「3」に基づいて符号長を「15」算出する。辞書生成部１１３は、符号長「15」に対応する可変長符号「1000010…」を「act」に割当てる。
【００４８】
なお、辞書生成部１１３は、高頻度単語に１６ビットよりも大きい符号長が割り当てられた場合、高頻度単語の符号長を補正してもよい。例えば、辞書生成部１１３は、高頻度単語に１８ビットの符号長が割り当てられた場合、符号長を１〜１６ビットに補正してもよい。
【００４９】
第二ファイルリード部１１４は、対象ファイルを読込む処理部である。第二ファイルリード部１１４は、対象ファイルを読込み、単語を抽出する。第二ファイルリード部１１４は、抽出した各単語を判定部１１５に出力する。
【００５０】
判定部１１５は、第二ファイルリード部１１４によって抽出された単語が基礎単語として圧縮辞書１２１ｂに登録されている場合に、抽出された単語に対応する圧縮符号が圧縮辞書に登録されているか否かを判定する。判定部１１５は、第二ファイルリード部１１４によって抽出された単語が基礎単語として圧縮辞書１２１ｂに登録されているか否かを判定する。判定部１１５は、抽出された単語が基礎単語として圧縮辞書１２１ｂに登録されている場合に、以下の処理を実行する。
【００５１】
さらに、判定部１１５は、対象ファイルから抽出された単語と基礎単語とを比較し、抽出された単語に対応する圧縮符号が圧縮辞書１２１ｂに登録されているか否かを判定する。判定部１１５は、抽出された単語の圧縮符号が圧縮辞書１２１ｂに登録されている場合、抽出された単語に対応する圧縮符号を圧縮辞書１２１ｂから取得する。判定部１１５は、取得した圧縮符号をファイルライト部１１８に出力する。
【００５２】
一方、判定部１１５は、対象ファイルから抽出された単語が圧縮辞書１２１ｂに登録されているが、抽出された単語に対応する圧縮符号が圧縮辞書１２１ｂに登録されていない場合、抽出された単語を単語符号化部１１６に出力する。単語符号化部１１６は、出力された単語に動的コードを割当てる。動的コードは、圧縮辞書１２１への登録順に割当てられる１６ビット（２バイト）の固定長符号である。例えば、単語符号化部１１６は、それぞれの単語に対し、動的コードとして「A000h」「A001h」「A002h」「A003h」…を動的コードとして割り当てる。単語符号化部１１６は、割当てられた動的コードを基礎単語に対応づけて圧縮辞書１２１ｂに登録する。さらに、単語符号化部１１６は、圧縮辞書１２１ｂに登録した動的コードを圧縮ファイルに出力する。
【００５３】
このように、圧縮部１１０は、対象ファイルから抽出した各低頻度単語に１６ビットの動的コードを割当てて圧縮辞書１２１ｂに登録すると共に、登録された動的コードを圧縮ファイルに出力することで、１パスで圧縮処理をおこなう。すなわち、圧縮部１１０は、動的コードの登録処理とファイルの圧縮処理を並行して行う。なお、以下では、圧縮部１１０が低頻度単語に動的コードを割り当てて圧縮辞書１２１に登録し、割当てられた動的コードを圧縮ファイル１２５に出力する処理を１パス圧縮処理と呼ぶ場合がある。
【００５４】
次に、各々の低頻度単語に動的コードを割当てた段階の圧縮辞書１２１ｃについて説明する。図９は、圧縮辞書の作成を説明するための第３の図である。図９の例に示されるように、圧縮辞書１２１ｃは、２グラムと、ビットマップと、基礎単語と、静的コードと、動的コードと、出現回数と、符号長と、圧縮符号とを対応付ける。圧縮辞書１２１ｃの各要素は、圧縮辞書１２１ａと同一であるので説明を省略する。
【００５５】
例えば、単語符号化部１１６は、対象ファイルから抽出された低頻度単語「administrator」に対して動的コード「C0FEh」を割当てて圧縮辞書１２１ｃに登録する。さらに、単語符号化部１１６は、圧縮辞書１２１ｃに登録した動的コード「C0FEh」をファイルライト部１１８に出力する。また、単語符号化部１１６は、対象ファイルから抽出された低頻度単語「adjust」に対して動的コード「A0EFh」を割当てて圧縮辞書１２１ｃに登録する。さらに、単語符号化部１１６は、圧縮辞書１２１ｃに登録した動的コード「A0EFh」をファイルライト部１１８に出力する。
【００５６】
判定部１１５は、第二ファイルリード部１１４によって対象ファイルから抽出された単語が基礎単語として圧縮辞書１２１ｂに登録されていない場合に、以下の処理を実行する。判定部１１５は、対象ファイルから抽出した単語を文字符号化部１１７に出力する。文字符号化部１１７は、抽出した単語に含まれる各文字または各記号の出現回数をインクリメントする。ここで、文字・記号部１２１ｄは、圧縮辞書１２１内に確保された、文字および記号に対応する圧縮符号を格納する領域である。文字符号化部１１７は、単語符号化部１１６が単語に符号長を割当てる場合と同様に、文字および記号の出現回数に基づいて各文字および各記号に符号長を割り当てる。次いで、文字符号化部１１７は、文字符号化部１１７によって割当てられた符号長に基づいて文字および記号に可変長符号または固定長符号を割り当てる。そして、文字符号化部１１７は、文字および記号に割当てた可変長符号または固定長符号を、文字および記号に対応付けて文字・記号部１２１ｄに登録する。
【００５７】
次に、文字・記号部１２１ｄの例について説明する。図１０は、圧縮辞書の文字・記号部を説明するための図である。図１０の例に示されるように、圧縮辞書の文字・記号部１２１ｄは、文字・記号、出現回数、符号長および圧縮符号を対応付ける。「文字・記号」は、対象ファイルに含まれる英字、数字、特殊記号、制御文字等の文字コードである。図１０の例では、アスキーコードが格納されているが他の文字コードが格納されてもよい。「出現回数」は、対象ファイルにおいて文字または記号が出現した回数である。「符号長」は、文字または記号に割り当てた圧縮符号の長さである。「符号長」は、例えば、「出現回数」を式（１）に当てはめることで算出される。「圧縮符号」は、文字または記号に割り当てた圧縮符号である。「圧縮符号」は、「符号長」に対応する。
【００５８】
ファイルライト部１１８は、圧縮ファイル１２５を生成する処理部である。ファイルライト部１１８は、単語符号化部１１６および文字符号化部１１７から出力された圧縮符号を基にして圧縮データ１２６を生成する。ファイルライト部１１８は、生成した圧縮データ１２６を圧縮ファイル１２５に格納する。
【００５９】
また、ファイルライト部１１８は、圧縮辞書１２１ｃから各高頻度単語と、出現回数とを取得する。次いで、ファイルライト部１１８は、取得した各高頻度単語と、出現回数とを対応付けて頻度表１２７に登録する。このようにして、ファイルライト部１１８は、各高頻度単語と、出現回数とを対応付けた頻度表１２７を生成する。ファイルライト部１１８は、生成した頻度表を圧縮ファイル１２５に格納する。なお、ファイルライト部１１８は、頻度表１２７に高頻度単語を格納する代わりに高頻度単語に対応する静的コードを格納してもよい。
【００６０】
一方、ファイルライト部１１８は、圧縮辞書１２１ｃに登録されている低頻度単語をそれぞれ取得する。ファイルライト部１１８は、各低頻度単語が圧縮辞書１２１ｃに登録された順にオフセットが大きくなるように、各々の低頻度単語を動的辞書１２８に登録する。例えば、圧縮辞書１２１ｃに「average」「visitor」「atmosphere」の順に低頻度単語が登録されているものとする。かかる場合において、ファイルライト部１１８は、「average」「visitor」「atmosphere」の順にオフセットが大きくなるように動的辞書１２８に各低頻度単語を登録していき、動的辞書１２８を生成する。そして、ファイルライト部１１８は、生成した動的辞書１２８を圧縮ファイル１２５に格納する。なお、ファイルライト部１１８は、動的辞書１２８に低頻度単語を格納する代わりに低頻度単語に対応する静的コードを格納してもよい。
【００６１】
図１１を用いてファイルライト部１１８の処理について説明する。図１１は、実施例１の圧縮を説明するための第２の図である。ファイルライト部１１８は、圧縮辞書（ケヤキ木）１２１から各高頻度単語と出現回数とをそれぞれ取得する。ファイルライト部１１８は、取得した各高頻度単語と出現回数とを対応付けて頻度表１２７に登録していき、頻度表１２７を生成する。ファイルライト部１１８は、生成した頻度表１２７を圧縮ファイル１２５のヘッダ部１２５ａに格納する。
【００６２】
一方、ファイルライト部１１８は、圧縮辞書（ケヤキ木）１２１に登録されている低頻度単語をそれぞれ取得する。ファイルライト部１１８は、各低頻度単語が圧縮辞書１２１ｃに登録された順にオフセットが大きくなるように、各々の低頻度単語を動的辞書１２８に登録していき、動的辞書１２８を生成する。ファイルライト部１１８は、生成した動的辞書１２８を圧縮ファイル１２５のトレーラー部１２５ｃに格納する。
【００６３】
なお、ファイルライト部１１８は、圧縮データを圧縮ファイル１２５の符号化部１２５ｂに出力する。
【００６４】
（圧縮処理の全体のフロー図）
次に、圧縮処理の全体の流れを表すフロー図について説明する。図１２は、圧縮処理の全体の流れを説明するためのフロー図である。図１２の例のように圧縮部１１０は、前処理を実行する（ステップＳ１０）。例えば、圧縮部１１０は、前処理において圧縮辞書１２１ａを格納するための記憶領域と、圧縮ファイル１２５を格納するための記憶領域とを確保する。圧縮部１１０は、母集団から１９万語の単語を抽出し、抽出した１９万語の単語のうち、出現順位が１〜８０００位の高頻度単語に対して圧縮符号を割当てる標本化処理をおこなう（ステップＳ１１）。
【００６５】
圧縮部１１０は、対象ファイルから抽出した低頻度単語に圧縮符号を割当てると共に、圧縮ファイル１２５を生成する１パス圧縮処理をおこなう（ステップＳ１２）。圧縮部１１０は、圧縮辞書１２１に基づいて頻度表１２７を生成し、圧縮ファイル１２５のヘッダ部１２５ａに頻度表１２７を格納する（ステップＳ１３）。頻度表１２７には、高頻度単語と出現回数とが含まれる。圧縮部１１０は、圧縮辞書１２１に基づいて動的辞書１２８を生成し、圧縮ファイル１２５のトレーラー部１２５ｃに動的辞書１２８を格納する（ステップＳ１４）。動的辞書１２８には、各低頻度単語が圧縮辞書１２１ｃに登録された順にオフセットが大きくなるように登録される。なお、ステップＳ１１およびステップＳ１２の詳細なフローに関しては後述する。
【００６６】
（標本化処理のフロー図）
次に、ステップＳ１１の処理フローについて詳細に説明する。図１３は、標本化処理の流れの例を示すフロー図である。図１３の例のように圧縮部１１０は、前処理を実行する（ステップＳ２０）。例えば、圧縮部１１０は、前処理において圧縮辞書１２１ｂを生成するための作業領域を確保する。標本化部１１１は、母集団から単語を抽出する（ステップＳ２１）。標本化部１１１は、母集団から抽出した各単語をアルファベット順に並び替え、基礎単語として圧縮辞書１２１に登録する（ステップＳ２２）。標本化部１１１は、登録された各基礎単語に静的コードを割当てる（ステップＳ２３）。
【００６７】
第一ファイルリード部１１２は、母集団のテキストファイルを読込み、母集団における各基礎単語の出現頻度を集計する（ステップＳ２４）。辞書生成部１１３は、各高頻度単語の出現頻度に基づいて、各高頻度単語に１〜１６ビットまでの符号長を割当てる（ステップＳ２５）。辞書生成部１１３は、高頻度単語に割当てられた符号長に基づいて高頻度単語に圧縮符号（可変長符号）を割当てる（ステップＳ２６）。
【００６８】
（１パス圧縮処理のフロー図）
次に、ステップＳ１２の処理フローについて詳細に説明する。図１４は、１パス圧縮処理の流れの例を示すフロー図である。図１４の例のように、圧縮部１１０は、前処理を実行する（ステップＳ３０）。例えば、圧縮部１１０は、前処理において、１パス圧縮処理をおこなうための作業領域を確保する。第二ファイルリード部１１４は、対象ファイルから単語を抽出する（ステップＳ３１）。
【００６９】
判定部１１５は、第二ファイルリード部１１４によって対象ファイルから抽出された単語を圧縮辞書１２１と照合する（ステップＳ３２）。判定部１１５は、対象ファイルから抽出された単語が圧縮辞書１２１に登録済みか否かを判定する（ステップＳ３３）。ファイルライト部１１８は、対象ファイルから抽出された単語が圧縮辞書１２１に登録済みの場合（ステップＳ３３Yes）、圧縮辞書１２１から単語に対応する１〜１６ビットまでの圧縮符号を取得し、圧縮符号を圧縮ファイル１２５に出力する（ステップＳ３７）。そして、圧縮部１１０は、ステップＳ３６の処理に移行する。
【００７０】
一方、単語符号化部１１６は、抽出された単語が圧縮辞書１２１に登録されていない場合（ステップＳ３３No）、１６ビットの固定長符号（動的コード）を基礎単語に対応づけて低頻度単語として圧縮辞書１２１に登録する（ステップＳ３４）。例えば、単語符号化部１１６は、単語が抽出された順にA000h,  A001h,  A002h…のように昇順に１６ビットの固定長符号を割当てる。ファイルライト部１１８は、圧縮辞書１２１に登録した１６ビットの固定長符号（動的コード）を圧縮ファイル１２５に出力する（ステップＳ３５）。そして、圧縮部１１０は、ステップＳ３６の処理に移行する。
【００７１】
次いで、圧縮部１１０は、ステップＳ３６において、対象ファイルの終端に至ったか否かを判定する（ステップＳ３６）。圧縮部１１０は、対象ファイルの終端に至った場合（ステップＳ３６Yes）、処理を終了する。一方、圧縮部１１０は、対象ファイルの終端に至っていない場合（ステップＳ３６No）、ステップＳ３１の処理に戻る。
【００７２】
このように、実施例１によれば、低頻度単語に割り当てる符号長が２バイト以上に長くなるのを防止することができるので、低頻度単語に割り当てる符号長が改善する。
【００７３】
（実施例１の伸長処理に関する処理部の構成）
図１５を用いて、実施例１の伸長処理に係るシステム構成について説明する。図１５は、実施例１の伸長処理に係るシステム構成の一例を示す図である。図１５の例に示されるように、情報処理装置１００は、伸長部１５０および記憶部１２０を有する。伸長部１５０は、伸長辞書生成部１５１、ファイルリード部１５２、伸長処理部１５３およびファイルライト部１５４を有する。記憶部１２０は、圧縮ファイル１２５および伸長辞書１２９を有する。圧縮ファイル１２５は、圧縮データ１２６、頻度表１２７および動的辞書１２８を有する。以下、伸長部１５０の各処理部について詳細に説明する。
【００７４】
伸長辞書生成部１５１は、頻度表１２７および動的辞書１２８に基づいて伸長辞書１２９を生成する処理部である。まず、高頻度単語を伸長辞書１２９に登録する手順について説明する。伸長辞書生成部１５１は、頻度表１２７から各高頻度単語の出現回数を取得する。伸長辞書生成部１５１は、取得した各高頻度単語の出現回数に基づいて各々の高頻度単語の符号長を算出する。伸長辞書生成部１５１は、算出した符号長に対応する圧縮符号を各高頻度単語に割り当て、伸長辞書１２９に登録する。
【００７５】
次に、低頻度単語を伸長辞書１２９に登録する手順について説明する。ここで、動的辞書１２８には、各低頻度単語が圧縮辞書１２１に登録された順にオフセットが大きくなるように、各々の低頻度単語が登録されているものとする。伸長辞書生成部１５１は、圧縮辞書１２１に登録されている低頻度単語のうち、オフセットが小さい順に低頻度単語に動的コード「A000h」「A001h」「A002h」…を割当てる。
【００７６】
例えば、圧縮辞書１２１にオフセットが小さい順に低頻度単語として「average」「visitor」「atmosphere」…が登録されているものとする。伸長辞書生成部１５１は、「average」に対して「A000h」を割当て、「visitor」に対して「A001h」を割当て、「atmosphere」に対して「A002h」を割当てる。
【００７７】
伸長辞書生成部１５１は、各低頻度単語に割り当てた動的コードを伸長辞書１２９に登録する。このようにして伸長辞書１２９が生成される。
【００７８】
伸長辞書１２９の一例について説明する。図１６は、伸長辞書を説明するための図である。図１６の例に示されるように伸長辞書１２９は、２グラムと、ビットマップと、基礎単語と、静的コードと、動的コードと、出現回数と、符号長と、圧縮符号とを対応付ける。「基礎単語」は、伸長辞書１２９に登録された単語である。「静的コード」は、頻度表１２７または動的辞書１２８に基づいて各基礎単語に割当てられる。「動的コード」は、動的辞書１２８を基に各低頻度単語に割当てられる。「出現回数」は、頻度表１２７から取得されたデータである。「符号長」は、伸長辞書生成部１５１によって出現回数を基に算出される。「圧縮符号」は、伸長辞書生成部１５１によって符号長を基にして割り当てられる。
【００７９】
ファイルリード部１５２は、圧縮データ１２６から所定長の圧縮符号を取得する処理部である。例えば、ファイルリード部１５２は、圧縮データ１２６から１６ビット分の圧縮符号を取得して伸長処理部１５３に出力する。
【００８０】
伸長処理部１５３は、ファイルリード部１５２から出力された圧縮符号を伸長する処理部である。伸長処理部１５３は、伸長辞書１２９において、ファイルリード部１５２によって出力された１６ビットの圧縮符号を検索し、圧縮符号に対応する基礎単語を特定する。さらに、伸長処理部１５３は、基礎単語に対応する符号長を特定する。例えば、図１６の例によれば、伸長処理部１５３は、圧縮符号が「1000001…」であった場合、伸長辞書１２９において、圧縮符号「1000001…」に対応する基礎単語「about」を特定し、さらに符号長「10」を特定する。
【００８１】
符号長が「10」であった場合、ファイルリード部１５２によって取得された１６ビット分の圧縮符号のうち、１ビット目から１０ビット目までが、基礎単語「about」に対応する圧縮符号である。なお、ファイルリード部１５２によって取得された１６ビット分の圧縮符号のうち、１１ビット目から１６ビット目までは、次に伸長する基礎単語に対応する圧縮符号である。
【００８２】
ファイルライト部１５４は、伸長処理部１５３によって特定された基礎単語を伸長ファイルに書き込む処理部である。
【００８３】
また、ファイルライト部１５４は、伸長処理部１５３によって特定された符号長をファイルリード部１５２に出力する。ファイルリード部１５２は、出力された符号長によって、圧縮データ１２６において次回圧縮符号を取得する位置を特定する。例えば、ファイルリード部１５２は、ファイルライト部１５４によって出力された符号長が「10」であった場合、前回圧縮符号を取得した位置よりも１０ビット後方の位置から１６ビット分の圧縮符号を取得する。
【００８４】
なお、文字・記号を伸長する処理に関しては、単語を伸長する処理と同様であるので説明を省略する。
【００８５】
（伸長ファイルを作成する処理の流れ）
次に、図１７を用いて伸長ファイルを生成する処理の流れについて説明する。図１７は、実施例１の伸長を説明するための図である。伸長部１５０は、伸長辞書１２９を生成する処理を実行し、生成した伸長辞書１２９に基づいて圧縮ファイルを伸長する処理を実行する。
【００８６】
まず、伸長辞書を生成する処理について説明する。伸長辞書生成部１５１は、圧縮ファイル１２５のヘッダ部１２５ａに格納されている頻度表１２７から各高頻度単語の出現回数を取得する。伸長辞書生成部１５１は、取得した各高頻度単語の出現回数に基づいて、各々の高頻度単語の符号長を算出する。次いで、伸長辞書生成部１５１は、算出した符号長を伸長辞書１２９に登録する。そして、伸長辞書生成部１５１は、登録された符号長に基づいて高頻度単語に可変長符号を割り当て、可変長符号および符号長を伸長辞書１２９に登録する。
【００８７】
例えば、伸長辞書生成部１５１は、高頻度単語「the」の出現回数を基にして符号長「6」を算出する。伸長辞書生成部１５１は、符号長「6」に対応する可変長符号「000001」を高頻度単語「the」に割り当て、可変長符号「000001」および符号長「6」を伸長辞書１２９に登録する。
【００８８】
伸長辞書生成部１５１は、圧縮ファイル１２５のトレーラー部１２５ｃに格納されている動的辞書１２８から、動的辞書１２８への登録順に低頻度単語を取得する。伸長辞書生成部１５１は、各低頻度単語に１６ビットの動的コードを割り当て、動的コードおよび符号長を伸長辞書１２９に登録する。このようにして、伸長辞書生成部１５１は、伸長辞書１２９を生成する。
【００８９】
例えば、伸長辞書生成部１５１は、動的辞書１２８から「zymosis」を取得し、動的辞書における「zymosis」の登録順番に基づいて動的コード「1010110001100010」および符号長「16」を伸長辞書１２９に登録する。以上のようにして、伸長部１５０は伸長辞書１２９を生成する処理を実行する。
【００９０】
次に、伸長辞書１２９に基づいて圧縮ファイルを伸長する処理について説明する。ファイルリード部１５２は、圧縮データ１２６から１６ビットの圧縮符号を取得して伸長処理部１５３に出力する。例えば、ファイルリード部１５２は、圧縮データ１２６から「1010110001100010」を取得して伸長処理部１５３に出力する。
【００９１】
伸長処理部１５３は、出力された１６ビットの圧縮符号を、伸長辞書（ケヤキ木）１２９と照合し、圧縮符号に対応する基礎単語と符号長を特定する。例えば、伸長処理部１５３は、出力された「1010110001100010」に対応する基礎単語「zymosis」と符号長「16」とを特定する。
【００９２】
伸長処理部１５３は、特定された基礎単語をファイルライト部１５４に出力する。ファイルライト部１５４は、出力された基礎単語を伸長ファイル１６０に出力する。
【００９３】
さらに、伸長処理部１５３は、特定された符号長をファイルリード部１５２に出力する。ファイルリード部１５２は、出力された符号長を基に次回圧縮データ１２６を読み出す位置を特定する。例えば、ファイルリード部１５２は、伸長処理部１５３から出力された符号長が「16」の場合、次回読み出す位置を、前回読み出した位置から１６ビット後方の位置に特定する。
【００９４】
（伸長処理のフロー図）
次に、伸長処理の流れを表すフロー図について説明する。図１８は、圧縮符号を伸長する処理の流れを示すフロー図である。図１８の例のように、伸長部１５０は、前処理を実行する（ステップＳ４０）。例えば、伸長部１５０は、伸長辞書１２９を格納するための記憶領域および伸長辞書１２９を作成するための作業領域を確保する。伸長辞書生成部１５１は、頻度表１２７を基に各高頻度単語に可変長符号および符号長を割当てる（ステップＳ４１）。伸長辞書生成部１５１は、各可変長符号および符号長を伸長辞書１２９に登録する（ステップＳ４２）。伸長辞書生成部１５１は、動的辞書１２８を基に各低頻度単語に動的コードおよび符号長を割当てる（ステップＳ４３）。伸長辞書生成部１５１は、各動的コードおよび符号長を伸長辞書１２９に登録する（ステップＳ４４）。伸長処理部１５３およびファイルライト部１５４は、生成された伸長辞書１２９を用いて対象ファイルに対して伸長処理を実行し、伸長ファイルを生成する（ステップＳ４５）。
【００９５】
（低頻度領域の拡張）
圧縮部１１０は、対象ファイルに３２０００語以上の単語が含まれる場合、低頻度単語を格納する領域を拡張してもよい。以下では低頻度単語を格納する領域を低頻度領域と呼ぶ。
【００９６】
図１９は、低頻度領域の拡張を説明するための図である。グラフ６０は、低頻度領域を拡張した場合に各基礎単語に割り当てる符号長を表す。グラフ６０の縦軸は単語数を示し、母集団において出現頻度が高い単語ほど単語数が小さく、出現頻度が低い単語ほど単語数が大きい。すなわち、単語数は、母集団における単語の出現順位を表す。高頻度単語はグラフ６０の縦軸１〜８０００語に位置する。低頻度単語のうち出現頻度の順位が８０００〜２８０００位の低頻度単語は、グラフ６０の縦軸８０００〜２８０００語に位置する。また、低頻度単語のうち出現頻度の順位が２８０００〜９２０００位の低頻度単語は、グラフ６０の縦軸２８０００〜９２０００語に位置する。
【００９７】
一方、横軸は各単語に割り当てられる符号長を示す。例えば、高頻度単語に対しては、１〜１６ビットまでの可変長符号が割り当てられる。出現頻度の順位が８０００〜２８０００位の低頻度単語に対しては、１６ビットの固定長符号が割当てられる。また、出現頻度の順位が２８０００〜９２０００位の低頻度単語に対しては、２４ビットの固定長符号が割当てられる。
【００９８】
各単語に割り当てられる圧縮符号の領域に関して説明する。高頻度単語には、００００ｈ〜９ＦＦＦｈまでの領域が割り当てられる。出現頻度の順位が８０００〜２８０００位の低頻度単語には、Ａ００００〜ＥＦＦＦＦｈまでの領域が割り当てられる。さらに、出現頻度の順位が２８０００〜９２０００位の低頻度単語には、Ｆ０００００〜ＦＦＦＦＦＦｈまでの領域が割り当てられる。このように、圧縮部１１０は、低頻度領域を拡張することで低頻度単語として新たに約６００００語の単語を圧縮辞書に登録することができる。これにより、圧縮部１１０は、対象ファイルの容量が大きい場合においても、各単語に圧縮符号を割当てることができる。
【００９９】
（効果）
以上説明したように、圧縮部１１０は、複数のファイルにおける単語の頻度情報より生成された符号割当て規則に基づき、複数のファイルに含まれる第１のファイルを符号化する際に、頻度情報における出現頻度が、所定順位の単語の出現頻度よりも大きい各単語に対し、符号割当て規則に応じて符号化し、頻度情報における出現頻度が、所定順位の単語の出現頻度よりも小さい単語の少なくとも一部に対し、前記符号割当て規則による符号と異なる符号割当て規則で、かつ、第１の符号長で符号化する。これにより、圧縮処理時に単語に割り当てる符号長を短くでき、圧縮率を向上できる。
【０１００】
また、第１の符号長は、符号割当て規則に応じて符号化される単語の最大符号化長以上とする。これにより、圧縮辞書において出現頻度の低い単語を格納する領域を拡張することができる。
【０１０１】
また、圧縮部１１０は、出現頻度が、所定順位の単語の出現頻度よりも小さい単語のうち、出現頻度が第２の所定順位の単語の出現頻度よりも大きい単語に所定符号長の圧縮符号を割り当て、出現頻度が第２の所定順位の単語の出現頻度より小さい単語に、所定符号長と異なる第２の符号長で符号化する。これにより、符号化する対象ファイルの容量が大きい場合においても、各単語に圧縮符号を割当てることができる。
【０１０２】
また、圧縮部１１０は、対象ファイルにおける出現頻度が所定順位以上の各単語に、該出現頻度に応じて所定符号長以下の可変長の圧縮符号を割り当て、出現頻度が所定順位未満の各単語に、所定符号長の圧縮符号を割り当てる。さらに、圧縮部１１０は、各単語に割り当てられた圧縮符号によって対象ファイルを圧縮する。これにより、圧縮処理時に単語に割り当てる符号長を短くでき、圧縮率を向上できる。
【０１０３】
また、圧縮部１１０は、１以上のファイルを有する母集団から複数の単語を取得する処理をさらにコンピュータに実行させ、母集団から取得された複数の単語のうち、対象ファイルに含まれる各単語に圧縮符号を割り当てる。これにより、圧縮処理に費やす時間を短縮できる。
【０１０４】
また、圧縮部１１０は、圧縮符号を割り当てる単語が所定数以上ある場合に、出現頻度が所定順位以下の単語のうち、出現頻度が他の所定順位以上の各単語に所定符号長の圧縮符号を割り当て、出現頻度が他の所定順位未満の各単語に他の所定符号長の圧縮符号を割り当てる。これにより、圧縮辞書において出現頻度の低い単語を格納する領域を拡張することができる。
【０１０５】
また、伸長部１５０は、圧縮ファイルに含まれる各単語と、各単語の出現頻度に基づいて各単語に割り当てられる可変長または固定長の圧縮符号とを対応付けた辞書を生成し、辞書を用いて圧縮ファイルに含まれる各圧縮符号を単語に伸長する処理を実行する。これにより、可変長符号および固定長符号を含む圧縮ファイルを伸長することができる。
【０１０６】
（実施例１に関連する他の態様）
以下、上述の実施形態における変形例の一部を説明する。下記の変形例のみでなく、本発明の本旨を逸脱しない範囲の設計変更は適宜行われうる。
【０１０７】
実施例１において、標本化部１１１は、複数のテキストファイルを含む母集団から基礎単語を収集したが、これに限定されない。標本化部１１１は、一つのテキストファイルから基礎単語を収集してもよい。
【０１０８】
実施例１において、辞書生成部１１３は、低頻度単語に対して１６ビットの固定長の圧縮符号を割り当てる旨を説明したが、これに限定されない。辞書生成部１１３は、低頻度単語に対して１６ビット以外のビット数を割り当ててもよい。
【０１０９】
実施例１において、辞書生成部１１３は、出現順位が８０００位以上の単語に可変長符号を割り当て、出現順位が８０００位以下の単語に固定長符号を割り当てたが、これに限定されない。辞書生成部１１３は、出現順位が８０００位以外の順位を境界にして可変長符号または固定長符号を単語に割り当ててもよい。
【０１１０】
また、圧縮処理の対象は、ファイル内のデータ以外にも、システムから出力される監視メッセージなどでもよい。例えば、バッファに順次格納される監視メッセージを上述の圧縮処理により圧縮し、ログファイルとして格納するなどの処理が行なわれる。また、例えば、データベース内のページ単位に圧縮が行なわれてもよいし、複数のページをまとめた単位で圧縮が行なわれてもよい。
【０１１１】
また、実施例１に示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１１２】
（情報処理装置のハードウェア構成）
図２０は、実施例１の情報処理装置のハードウェア構成を示す図である。図２０の例が示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０１と、ユーザからのデータ入力を受け付ける入力装置２０２と、モニタ２０３とを有する。また、コンピュータ２００は、記憶媒体からプログラム等を読み取る媒体読取装置２０４と、他の装置と接続するためのインターフェース装置２０５と、他の装置と無線により接続するための無線通信装置２０６とを有する。また、コンピュータ２００は、各種情報を一時記憶するＲＡＭ（Random  Access  Memory）２０７と、ハードディスク装置２０８とを有する。また、各装置２０１〜２０８は、バス２０９に接続される。
【０１１３】
ハードディスク装置２０８には、標本化部１１１、第一ファイルリード部１１２、辞書生成部１１３、第二ファイルリード部１１４、判定部１１５、単語符号化部１１６、文字符号化部１１７およびファイルライト部１１８の各処理部と同様の機能を有するプログラムが記憶される。また、ハードディスク装置２０８には、プログラムを実現するための各種データが記憶される。
【０１１４】
ＣＰＵ２０１は、ハードディスク装置２０８に記憶された各プログラムを読み出して、ＲＡＭ２０７に展開して実行することで各種の処理を行う。これらのプログラムは、コンピュータ２００を、例えば図６に示した標本化部１１１、第一ファイルリード部１１２、辞書生成部１１３および第二ファイルリード部１１４として機能させることができる。さらに、これらのプログラムは、コンピュータ２００を、判定部１１５、単語符号化部１１６、文字符号化部１１７およびファイルライト部１１８として機能させることができる。
【０１１５】
なお、プログラムは、必ずしもハードディスク装置２０８に記憶されている必要はない。例えば、コンピュータ２００が読み取り可能な記憶媒体に記憶されたプログラムを、コンピュータ２００が読み出して実行するようにしてもよい。コンピュータ２００が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal  Serial  Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ（Local  Area  Network）等に接続された装置にこのプログラムを記憶させておき、コンピュータ２００がこれらからプログラムを読み出して実行するようにしてもよい。
【０１１６】
図２１は、コンピュータで動作するプログラムの構成例を示す図である。コンピュータ２００において、図２０に示すハードウェア群２６（２０１〜２０９）の制御を行なうＯＳ（オペレーティング・システム）２７が動作する。ＯＳ２７に従った手順でＣＰＵ２０１が動作して、ハードウェア群２６の制御・管理が行なわれることにより、アプリケーションプログラム２９やミドルウェア２８に従った処理がハードウェア群２６で実行される。さらに、コンピュータ２００において、ミドルウェア２８またはアプリケーションプログラム２９が、ＲＡＭ２０７に読み出されてＣＰＵ２０１により実行される。
【０１１７】
ＣＰＵ２０１によって圧縮機能が呼び出された場合に、ミドルウェア２８またはアプリケーションプログラム２９の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２７に基づいてハードウェア群２６を制御して）圧縮部１１０の機能が実現される。圧縮機能は、それぞれアプリケーションプログラム２９自体に含まれてもよいし、アプリケーションプログラム２９に従って呼び出されることで実行されるミドルウェア２８の一部であってもよい。
【０１１８】
アプリケーションプログラム２９（またはミドルウェア２８）の圧縮機能により得られる圧縮ファイルは、部分的に伸張することも可能である。圧縮ファイルの途中を伸張する場合には、伸張対象の部分までの圧縮データの伸張処理が抑制されるため、ＣＰＵ２０１の負荷が抑制される。また、伸張対象の圧縮データを部分的にＲＡＭ２０７上に展開するので、ワークエリアも削減される。
【０１１９】
図２２は、実施形態のシステムにおける装置の構成例を示す図である。図２２のシステムは、コンピュータ２００ａ、コンピュータ２００ｂ、基地局３０およびネットワーク４０を含む。コンピュータ２００ａは、無線または有線の少なくとも一方により、コンピュータ２００ｂと接続されたネットワーク４０に接続している。
【符号の説明】
【０１２０】
１００              情報処理装置
１１０              圧縮部
１１１              標本化部
１１２              第一ファイルリード部
１１３              辞書生成部
１１４              第二ファイルリード部
１１５              判定部
１１６              単語符号化部
１１７              文字符号化部
１１８              ファイルライト部
１２０              記憶部
１２１              圧縮辞書
１２５              圧縮ファイル
１２６              圧縮データ
１２７              頻度表
１２８              動的辞書
【図１】
0006645013.tif 000002
【図２】
0006645013.tif 000003
【図３】
0006645013.tif 000004
【図４】
0006645013.tif 000005
【図５】
0006645013.tif 000006
【図６】
0006645013.tif 000007
【図７】
0006645013.tif 000008
【図８】
0006645013.tif 000009
【図９】
0006645013.tif 000010
【図１０】
0006645013.tif 000011
【図１１】
0006645013.tif 000012
【図１２】
0006645013.tif 000013
【図１３】
0006645013.tif 000014
【図１４】
0006645013.tif 000015
【図１５】
0006645013.tif 000016
【図１６】
0006645013.tif 000017
【図１７】
0006645013.tif 000018
【図１８】
0006645013.tif 000019
【図１９】
0006645013.tif 000020
【図２０】
0006645013.tif 000021
【図２１】
0006645013.tif 000022
【図２２】
0006645013.tif 000023