JP2009289196A - 情報検索プログラム、情報管理プログラム、情報検索装置、情報管理装置、情報検索方法、および情報管理方法 - Google Patents

Abstract

【課題】ファイルアクセス処理の高速化を図ることにより検索処理の効率化を実現する。
【解決手段】アーカイブ２００は、書庫領域２０１と管理領域２０２とデータ領域２０３とを有する。データ領域２０３には、圧縮ファイル群ｆ（圧縮ファイルｆ１〜ｆｎ）が記憶されている。アーカイブ２００はその記憶領域２３０に格納されており、一部の圧縮ファイル群ｆ´がキャッシュ領域２４０に格納される。ここで、キャッシュ領域２４０とは、アーカイブ２００の記憶領域２３０に対して相対的に決まる記憶領域２３０であり、アーカイブ２００の記憶領域２３０よりも高速アクセスできる領域である。たとえば、アーカイブ２００の記憶領域２３０が磁気ディスクである場合、キャッシュ領域２４０はメインメモリやキャッシュメモリとなる。
【選択図】図２

Description

この発明は、文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブに関する情報検索プログラム、情報管理プログラム、情報検索装置、情報管理装置、情報検索方法、および情報管理方法に関する。

従来、下記特許文献１により、検索対象ファイルを圧縮形式のまま、検索条件に該当する可能性のある圧縮ファイルを絞り込むことで、ファイルオープンの回数を低減化する技術が開示されている。また一般的にファイルの検索に関して、オープン処理の回数が多くなり、且つファイル管理がセクタ単位のため、格納領域の断片化（フラグメンテーション）が発生し、格納サイズが増大するという問題について、アーカイブの適用が有効とされている。

国際公開第２００６／１２３４４８号パンフレット

しかしながら、上述のアーカイブでは、各圧縮ファイルが異なる圧縮パラメータにより圧縮されているため、圧縮パラメータの演算が必要になり、総合的にオープン処理が長くなる問題があった。また、上述した特許文献およびアーカイブでは、検索対象ファイル数の増大にともない、オープン処理の比率が急増するという問題があった。特に、大規模な辞典ではオープン処理がファイル処理の全体の２０〜３０％を占め、全文検索の速度低下の要因となっているという問題があった。また、約５０００ファイルから、指定されたファイル名を特定するため、２分探索では１３回の照合が必要になるという問題があった。さらに、ファイル管理がセクタ単位のため、ディスク領域の断片化（フラグメンテーション）が発生し、格納サイズが増大するという問題があった。

一方、大容量の主記憶メモリを装備するシングルサーバのシステムにおける辞書検索では、多数のファイルに分割され、ディスク領域に分散されているため、キャッシュへの常駐化をするためには、オープンやリード処理に多大な時間を必要とし、且つキャッシュでは、格納領域の断片化（フラグメンテーション）が発生し、格納サイズが増大する問題があった。

また、グリッドコンピューティングを利用した多くの辞書検索では、あるグリッドコンピュータの検索処理が遅れると全体の検索処理に影響を及ぼし、検索効率を低下させる原因となっていた。

この発明は、上述した従来技術による問題点を解消するため、圧縮ファイルに対して圧縮形式のままで全文検索を実現する際に、ファイルアクセス処理の高速化を図ることにより検索処理の効率化を実現することができる情報検索プログラム、情報管理プログラム、情報検索装置、情報管理装置、情報検索方法および情報管理方法を提供することを目的とする。

上述した課題を解決し、目的を達成するため、第１のプログラム、装置および方法は、アーカイブの各圧縮ファイルが共通な圧縮パラメータで圧縮されており、且つ各圧縮ファイルの先頭アドレスが前記の特許文献１において対象ファイルの絞込みに利用される文字出現マップの各ビットの番号と、それに該当する圧縮ファイルの先頭アドレスが格納されたテーブルがアーカイブの管理領域に書き込まれることを要件とする。

第１のプログラム、装置および方法によれば、１回の圧縮パラメータの演算で多数のオープン処理が可能である。また文字出現マップにより絞り込まれたファイルのフラグの位置番号をもとに、該当する圧縮ファイルの先頭アドレスを得ることができ、高速なオープン処理を実現することができる。

また、第２のプログラム、装置および方法は、文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブにアクセス可能であり、前記各圧縮ファイルへのアクセス頻度の高い順に並び替える並び替え、前記圧縮ファイル群が記憶されている記憶領域に対するキャッシュ領域の記憶容量を超えないように、並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算し、積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込むことを要件とする。

第２のプログラム、装置および方法によれば、アクセス頻度が高い圧縮ファイルを優先的にキャッシュ領域に格納することができる。

また、第３のプログラム、装置および方法は、文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブを記憶する複数のスレーブサーバーにアクセス可能であり、前記各スレーブサーバーから前記アーカイブを受信し、受信されたアーカイブごとの前記検索対象ファイル群に記述されている各文字および当該各文字の出現頻度に関する圧縮パラメータに基づいて、前記出現頻度を前記文字ごとに集計することにより、前記各圧縮ファイル群に共通の圧縮パラメータを生成し、生成された共通の圧縮パラメータに基づいて、前記各圧縮ファイル群に共通のハフマン木を生成し、前記圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記圧縮ファイルを割り当て、前記各スレーブサーバーに割り当てられた圧縮ファイル群を含むあらたなアーカイブと前記共通のハフマン木とを、割当先となるスレーブサーバーに送信することを要件とする。

この第３のプログラム、装置および方法によれば、各スレーブサーバーに対し、アクセス頻度が平準化された圧縮ファイル群を含むアーカイブを配信することができ、グリッドコンピュータ全体の検索の効率化と高速化を図ることができる。

このプログラム、装置および方法によれば、圧縮ファイルに対して圧縮形式のままで全文検索を実現する際に、ファイルアクセス処理の高速化を図ることにより検索処理の効率化を実現することができるという効果を奏する。

以下に添付図面を参照して、このプログラム、装置および方法の好適な実施の形態を詳細に説明する。

＜実施の形態１＞
狭義のアーカイブとは、一般に、複数のフォルダとその配下の多くのファイルを１ファイル化する技術である。電子メールなどに添付し送受信され、データ交換などの目的に利用されており、圧縮技術との組合せが多いことから、広義では、圧縮の付属技術として紹介されることもある。インターネットの普及とともに、アーカイブ技術が進歩し、その操作性や圧縮方式と組合せ、多種・多様なツールが開発された。パソコンなどのハードウェアの進歩は目ざましく、特にＣＰＵの高速化、メモリやハードディスクや光ディスクなどの媒体の大容量化は顕著である。

ハードウェアの進歩に伴い、データの多様化や、分析・解析や調査・研究への業務適用などの変化も著しい。一方、個人情報の流出や粉飾決算などに関して、個人情報保護法などの法整備などに対応したセキリティ機能の強化が求められている。アーカイブ技術では、これまで、圧縮・伸長の性能が重視されてきたが、今後、検索やセキリティなどとの連携機能が重視される。

従来のアーカイブは、主にデータの保存や情報伝達・交換などの分野で発達した技術であり、圧縮と１ファイル化が特徴である。また、ファイルを利用する場合は、解凍（あるいは、一時的に伸長）が行われる。ＺＩＰなどのアーカイブには、全文検索の機能がない。ファイルが多くなればなるほど、検索は重要機能である。

実施の形態１では、圧縮ファイルに対して圧縮形式のままで全文検索を実現する際に、アクセス頻度の高いファイルをキャッシュメモリに常駐化することで、リードなどのファイルアクセス処理の時間の短縮化を実現する。

（コンピュータのハードウェア構成）
図１は、実施の形態１にかかる情報検索装置のハードウェア構成を示すブロック図である。図１において、情報検索装置は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ Ｍｅｍｏｒｙ）１０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１０３と、磁気ディスクドライブ１０４と、磁気ディスク１０５と、光ディスクドライブ１０６と、着脱可能な記録媒体の一例としての光ディスク１０７と、ディスプレイ１０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）１０９と、キーボード１１０と、マウス１１１と、スキャナ１１２と、プリンタ１１３と、を備えている。また、各構成部はバス１００によってそれぞれ接続されている。

ここで、ＣＰＵ１０１は、コンピュータの全体の制御を司る。ＲＯＭ１０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１０３は、ＣＰＵ１０１のワークエリアとして使用される。磁気ディスクドライブ１０４は、ＣＰＵ１０１の制御にしたがって磁気ディスク１０５に対するデータのリード／ライトを制御する。磁気ディスク１０５は、磁気ディスクドライブ１０４の制御で書き込まれたデータを記憶する。

光ディスクドライブ１０６は、ＣＰＵ１０１の制御にしたがって光ディスク１０７に対するデータのリード／ライトを制御する。光ディスク１０７は、光ディスクドライブ１０６の制御で書き込まれたデータを記憶したり、光ディスク１０７に記憶されたデータをコンピュータに読み取らせたりする。

ディスプレイ１０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。

インターフェース（以下、「Ｉ／Ｆ」と略する。）１０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク１１４に接続され、このネットワーク１１４を介して他の装置に接続される。そして、Ｉ／Ｆ１０９は、ネットワーク１１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。

キーボード１１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。

スキャナ１１２は、画像を光学的に読み取り、情報検索装置内に画像データを取り込む。なお、スキャナ１１２は、ＯＣＲ（Ｏｐｔｉｃａｌ Ｃｈａｒａｃｔｅｒ Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ１１３は、画像データや文書データを印刷する。プリンタ１１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。

（アーカイブの記憶内容）
図２は、アーカイブの記憶内容を示す説明図である。アーカイブは、図１に示したＲＡＭ１０３、磁気ディスク１０５などの記憶領域に記憶されている。アーカイブ２００は、書庫領域２０１と管理領域２０２とデータ領域２０３とを有する。書庫領域２０１には、文字出現マップ連携テーブル２１１とファイルパス連携テーブル２１２と仮想アーカイブ容量テーブル２１３とが記憶されている。管理領域２０２には、圧縮パラメータ２２１とファイルパステーブル２２２と文字出現マップＭ（単字出現マップＭ１および連字出現マップＭ２）とが記憶されている。データ領域２０３には、圧縮ファイル群ｆ（圧縮ファイルｆ１〜ｆｎ）が記憶されている。

アーカイブ２００はその記憶領域２３０に格納されており、先頭から圧縮ファイルｆ´までがキャッシュ領域２４０に格納される。ここで、キャッシュ領域２４０とは、アーカイブ２００の記憶領域２３０に対して相対的に決まる記憶領域２３０であり、アーカイブ２００の記憶領域２３０よりも高速アクセスできる領域である。たとえば、アーカイブ２００の記憶領域２３０が磁気ディスク１０５である場合、キャッシュ領域２４０はメインメモリヒープ領域などに設けられる。また、キャッシュ領域２４０には、一部または全部の文字出現マップやファイルパス、仮想アーカイブも記憶される。

図３は、圧縮ファイルｆｉと検索対象ファイルとの関係を示す説明図である。ｎ個の圧縮ファイルｆ１〜ｆｎは共通のハフマン木で圧縮されており、そのハフマン木を用いて伸長される。伸長された検索対象ファイル群は、たとえば、辞書や用語辞典など文字列が記述されたファイル群である。このファイルは、たとえば、ＨＴＭＬ（ＨｙｐｅｒＴｅｘｔ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）やＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）などコンピュータリーダブルな言語で記述されたファイルである。日本語の辞書の場合、１ファイルの文字数は４０００文字以上であり、ファイル数ｎは、ｎ＝４０００〜６０００程度の膨大なファイル数となる。

日本語の辞書を例に挙げると、（Ａ）に示したように、ファイル番号ｉ＝２３の圧縮ファイルｆ２３を伸長すると、検索対象ファイルＦ２３が得られる。また、ファイル番号ｉ＝１５８の圧縮ファイルｆ１５８を伸長すると、（Ｂ）に示したように、検索対象ファイルＦ１５８が得られる。さらに、ファイル番号ｉ＝４９７１の圧縮ファイルｆ４９７１を伸長すると、（Ｃ）に示したように、検索対象ファイルＦ４９７１が得られる。なお、各検索対象ファイルＦ２３，Ｆ１５８，Ｆ４９７１中、墨付き括弧内の文字列は見出し語である。

図４は、単字出現マップＭ１を示す説明図である。単字出現マップＭ１では、文字ごとにビット列を有する。ビット列はビット番号順に並んでいる。ビット番号ｉは、圧縮ファイルのファイル番号ｉに対応する。ビット列中、“１”は、その文字が存在していることを示しており、“０”は存在しないことを示している。たとえば、かな文字「あ」のビット番号ｉ＝１のビットは“１”であるため、圧縮ファイルｆ１を伸長した検索対象ファイルにはかな文字「あ」が存在することとなる。一方、漢字文字「足」のビット番号ｉ＝１のビットは“０”であるため、圧縮ファイルｆ１を伸長した検索対象ファイルには漢字文字「足」が存在しないこととなる。

図５は、連字出現マップＭ２を示す説明図である。連字とは、連続する文字列である。ここでは、２連字について例示しているが、３連字以上でもよい。マップ形式は、図４に示した単字出現マップＭ１とおなじである。たとえば、数字連字「９９」のビット番号ｉ＝１のビットは“０”であるため、圧縮ファイルｆ１を伸長した検索対象ファイルには数字連字「９９」が存在しないこととなる。一方、数字連字「９９」のビット番号ｉ＝２のビットは“１”であるため、圧縮ファイルｆ２を伸長した検索対象ファイルには数字連字「９９」が存在することとなる。

図６は、圧縮パラメータ２２１を示す説明図である。圧縮パラメータ２２１とは、圧縮ファイル群ｆを伸長した検索対象ファイル群に記述されている文字／連字とその出現回数を対応付けたテーブルである。この圧縮パラメータ２２１にしたがって、検索対象ファイル群を圧縮ファイル群ｆに圧縮するためのハフマン木が生成される。

図７は、ファイルパステーブル２２２を示す説明図である。ファイルパステーブル２２２とは、圧縮ファイルｆｉへのパス（ファイルパス）が記述されたテーブルである。具体的には、たとえば、ファイルＩＤごとにその圧縮ファイルｆｉへのファイルパスとその圧縮ファイルｆｉを伸長した検索対象ファイルに記述されている見出し語とそのアドレスとサイズとを対応付けている。ファイルＩＤとは、圧縮ファイルｆｉを一意に特定する情報である。

ここでは、説明上、圧縮ファイルに割り当てられた符号をファイルＩＤとしている。たとえば、ファイルＩＤ：ｆ２３の圧縮ファイルｆ２３のファイルパスは、“ｈｏｎｍｏｎ￥ｆｉｌｅ２３．ｈｔｍｌ”であり、見出し語は「川端康成」である（図３を参照。）。なお、後述する常駐フラグが“１”に設定された場合、キャッシュ領域２４０へのファイルパス（たとえば、“ｃａｓｈ￥ｆｉｌｅ２３．ｈｔｍｌ”）が書き込まれ、“０”に戻った場合、キャッシュ領域２４０へのファイルパスは消去される。

図８は、文字出現マップ連携テーブル２１１を示す説明図である。文字出現マップ連携テーブル２１１は、文字出現マップＭの文字ごとのビット列を構成するビットごとに、アドレスとサイズとアクセス頻度と常駐フラグとが記憶されている。アドレスとは、文字出現マップＭの文字ごとのビット列を構成するビット番号に対応する圧縮ファイルが記憶されているアドレスである。サイズとは、圧縮ファイルｆｉのサイズである。たとえば、ビット番号ｉに対応する圧縮ファイルは圧縮ファイルｆｉである。この圧縮ファイルｆｉが記憶されているアドレスはａｄｒｉであり、圧縮ファイルｆｉのサイズはｓｉである。

また、アクセス頻度とは、そのビット番号ｉに対応する圧縮ファイルｆｉへのアクセスする度合いであり、ここでは、アクセス回数としている。アクセス頻度はアクセス回数のほか確率（圧縮ファイルｆｉへのアクセス回数／全圧縮ファイルへの総アクセス回数）であらわしてもよい。常駐フラグとは、そのビット番号ｉに対応する圧縮ファイルｆｉを、アーカイブ２００の記憶領域２３０から当該記憶領域２３０に対するキャッシュ領域２４０に移動してキャッシュ領域２４０に常駐されているか否かを示すフラグである。

キャッシュ領域２４０に常駐されている場合、常駐フラグは“１”である。一方、キャッシュ領域２４０に常駐されず、記憶領域２３０に格納されている場合、常駐フラグは“０”である。なお、常駐フラグが“１”に設定された場合、アドレスにはキャッシュ領域２４０のアドレスが書き込まれ、“０”に戻った場合、キャッシュ領域２４０のアドレスは消去される。

図９は、ファイルパス連携テーブル２１２を示す説明図である。ファイルパス連携テーブル２１２は、ファイルパスとビット番号ｉを連携するテーブルである。常駐フラグが“１”に設定された場合、キャッシュ領域２４０へのファイルパスが書き込まれ、“０”に戻った場合、キャッシュ領域２４０へのファイルパスは消去される。

図１０は、仮想アーカイブ容量テーブル２１３を示す説明図である。仮想アーカイブとは、記憶領域２３０に記憶されているアーカイブ２００のうちキャッシュ領域２４０に記憶された圧縮ファイル群ｆ´である。なお、書庫領域２０１や管理領域２０２内のテーブル等も仮想アーカイブに含めてもよい。

（情報検索装置の機能的構成）
図１１は、情報検索装置の機能的構成を示すブロック図である。情報検索装置１１００は、並び替え処理部１１０１と、積算部１１０２と、書込み部１１０３と、設定部１１０４と、入力部１１０５と、特定部１１０６と、読出し部１１０７と、伸長部１１０８と、検索部１１０９と、出力部１１１０と、更新部１１１１と、を含む構成である。

並び替え処理部１１０１〜入力部１１０５、更新部１１１１が仮想アーカイブ設定機能であり、入力部１１０５〜出力部１１１０が情報検索機能である。情報検索機能については、国際公開第ＷＯ２００６／１２３４４８号パンフレットに詳細に記載されているため、ここでは、本実施の形態の特徴部分に言及しつつ簡略化して説明する。

なお、並び替え処理部１１０１〜更新部１１１１は、具体的には、たとえば、図１に示したＲＯＭ、ＲＡＭ１０３、磁気ディスク１０５などの記憶領域２３０に記憶されたプログラムをＣＰＵ１０１に実行させることによって、または、Ｉ／Ｆ１０９によってその機能を実現する。

まず、並び替え処理部１１０１は、文字出現マップ連携テーブル２１１を、その各圧縮ファイルへのアクセス頻度の高い順（降順）に並び替える機能を有する。この並び替えは、常駐フラグの設定の前処理となる。

積算部１１０２は、並び替え処理部１１０１による並び替え後のアクセス頻度の高い順から圧縮ファイルｆｉのサイズを積算する機能を有する。具体的には、圧縮ファイル群ｆが記憶されている記憶領域２３０に対するキャッシュ領域２４０の記憶容量を超えないように積算する。たとえば、キャッシュ領域２４０の記憶容量を超えない最大の積算値となるように、並び替え処理部１１０１による並び替え後のアクセス頻度の高い順から圧縮ファイルのサイズを積算する。このように、最大の積算値を計算することで、キャッシュ領域２４０の記憶容量を最大限に活用することができる。

書込み部１１０３は、積算部１１０２によって積算された圧縮ファイル群を、当該ファイル群の検索に先立って、記憶領域２３０からキャッシュ領域２４０に書き込む機能を有する。書込み対象となる圧縮ファイル群ｆは、記憶領域２３０から消去されてもよく、また、記憶領域２３０に残存させておいてもよい。このように、キャッシュ領域２４０にアクセス頻度が高い圧縮ファイル群を書き込むことで、ファイルアクセスの高速化を図ることができる。

設定部１１０４は、書込み部１１０３によってキャッシュ領域２４０に書き込まれた圧縮ファイル群について常駐フラグを設定する機能を有する。具体的には、たとえば、キャッシュ領域２４０に書き込まれた圧縮ファイル群の文字出現マップ連携テーブル２１１における常駐フラグを、“０”から“１”に変更する。常駐フラグがすでに“１”の場合は、そのままである。なお、前回キャッシュ領域２４０に書き込まれていたが今回消去された圧縮ファイルについては、常駐フラグが“１”に設定されているため、“０”に変更する。これにより、アクセス頻度が高い圧縮ファイルがキャッシュ領域２４０に常駐されていることが特定できる。

入力部１１０５は、検索文字列の入力を受け付ける機能を有する。具体的には、図１に示したキーボードなどの入力装置を用いて入力された検索文字列を受け付ける。たとえば、「川端康成」といった検索文字列の入力を受け付ける。なお、検索文字列のほかに、前方一致、後方一致などの検索条件の入力を受け付けることとしてもよい。

特定部１１０６は、入力部１１０５によって入力された検索文字列を構成するすべての文字が存在する圧縮ファイルを特定する機能を有する。具体的には、文字出現マップＭを参照して、圧縮ファイル群を、検索文字列を構成するすべての文字が存在する圧縮ファイルに絞り込む。たとえば、検索文字列が「川端康成」の場合、「川」，「端」，「康」，「成」という単字に分解される。そして、単字出現マップＭ１から単字「川」，「端」，「康」，「成」のビット列を論理積演算し、論理積演算結果が“１”となったビット番号に対応する圧縮ファイルに絞り込まれる。

図１２は、文字出現マップＭを用いた圧縮ファイルｆｉの絞込み例を示す説明図である。図１２に示したように、各単字「川」，「端」，「康」，「成」のビット列を同一ビット番号で論理積（ＡＮＤ）演算をおこなう。論理積が“１”であるビット番号ｉ＝１，２３，１５８，４９７１に対応する圧縮ファイルｆ１，ｆ２３，ｆ１５８，ｆ４９７１の伸長後の検索対象ファイルに、単字「川」，「端」，「康」，「成」がすべて含まれていることがわかる。

ただし、この段階では、単字「川」，「端」，「康」，「成」がすべて含まれていることがわかるだけで、単字「川」，「端」，「康」，「成」がこの順で並ぶ文字列「川端康成」が含まれていることまでは特定できない。これにより、圧縮形式のまま、検索文字列を含んでいる可能性がある圧縮ファイルを特定することができる。

読出し部１１０７は、特定部１１０６によって特定された圧縮ファイルを、設定部１１０４によって設定された常駐フラグに基づく領域から読み出す機能を有する。具体的には、たとえば、特定部１１０６によって特定された圧縮ファイルについて、文字出現マップ連携テーブル２１１の常駐フラグを参照して、常駐フラグの値により、特定された圧縮ファイルが記憶されている領域を特定する。

常駐フラグが“０”である場合、圧縮ファイルはキャッシュ領域２４０に記憶されておらず、アーカイブ２００の記憶領域から読み出すこととなる。一般的なファイル名に基づくオープン処理では、ファイルパステーブル２２２が参照され、２分探索により一致したファイルＩＤの先頭アドレスとサイズにより該当の圧縮ファイルｆｉがオープンされる。多数の圧縮ファイルが格納されるアーカイブでは、オープン処理が長くなる。

一方、文字出現マップのビット番号に基づくオープン処理では、文字出現マップ２１１が参照され、ビット番号に対応した先頭アドレスとサイズを直接得ることができ、該当する圧縮ファイルｆｉを高速にアクセスすることができる。常駐フラグが“１”である場合、キャッシュ領域２４０に記憶されていることがわかる。この場合、キャッシュ領域２４０から圧縮ファイルｆｉをアクセスすることができ、さらに高速化を図ることができる。

伸長部１１０８は、読出し部１１０７によって読み出された圧縮ファイルを伸長する機能を有する。具体的には、たとえば、圧縮パラメータ２２１に基づいて生成されたハフマン木により、読み出された圧縮ファイルｆｉを伸長する。これにより、読み出された圧縮ファイルｆｉのみ伸長すればよいため、ファイルアクセスの高速化を図ることができる。

検索部１１０９は、伸長部１１０８によって伸長された検索対象ファイルの中から検索文字列に一致または関連する文字列を検索する機能を有する。具体的には、たとえば、伸長された検索対象ファイル群の中から検索文字列と一致する文字列が存在する検索対象ファイルを抽出する。検索文字列と前方一致または後方一致する文字列が存在する検索対象ファイルを、関連する検索対象ファイルとして抽出する。その他、検索文字列に共起する文字列が設定されている場合には、共起する文字列が存在する検索対象ファイルを、関連する検索対象ファイルとして抽出する。

出力部１１１０は、伸長部１１０８によって伸長された検索対象ファイルを出力する機能を有する。出力部１１１０の出力形式は、具体的には、たとえば、ディスプレイへの表示やプリンタへの印刷出力、他のコンピュータへの送信、情報検索装置１１００内の記憶領域２３０への格納などがある。ディスプレイに表示する場合、伸長された検索対象ファイルをそのまま表示することとしてもよい。また、伸長された検索対象ファイル名を一覧表示して、ユーザが検索対象ファイル名をポイントすることで、リンク先となる検索対象ファイルを読み出して画面表示することとしてもよい。

また、検索部１１０９により検索された場合、検索された検索対象ファイルをそのまま表示することとしてもよい。また、検索された検索対象ファイル名を一覧表示して、ユーザが検索対象ファイル名をポイントすることで、リンク先となる検索対象ファイルを読み出して画面表示することとしてもよい。

更新部１１１１は、伸長部１１０８によって圧縮ファイルが伸長された場合、当該圧縮ファイルへのアクセス頻度を更新する機能を有する。具体的には、たとえば、アクセス頻度がアクセス回数で表されている場合、伸長された圧縮ファイルｆｉのアクセス回数を１加算する。また、アクセス頻度が確率で表されている場合、伸長された圧縮ファイルに対しては、アクセス回数を１加算するとともに全圧縮ファイルｆ１〜ｆｎへの総アクセス回数も１加算する。

一方、伸長されなかった圧縮ファイルｆｉに対しては全圧縮ファイルｆ１〜ｆｎへの総アクセス回数のみ１加算する。したがって、並び替え処理部１１０１は、更新後の圧縮ファイル群ｆのアクセス頻度にしたがってソート処理を実行することとなる。これにより、文字出現マップＭにより絞り込まれやすい圧縮ファイルｆｉのアクセス頻度が高くなるため、次回以降の伸長速度の高速化を実現することができる。

また、更新部１１１１は、伸長された圧縮ファイルｆｉではなく、検索部１１０９によって検索された検索対象ファイルの圧縮ファイルｆｉについて、当該圧縮ファイルｆｉへのアクセス頻度を更新することとしてもよい。具体的には、たとえば、アクセス頻度がアクセス回数で表されている場合、検索された検索対象ファイルの圧縮ファイルｆｉへのアクセス回数を１加算する。また、アクセス頻度が確率で表されている場合、検索された検索対象ファイルの圧縮ファイルｆｉに対しては、アクセス回数を１加算するとともに全圧縮ファイルｆ１〜ｆｎへの総アクセス回数も１加算する。

一方、検索されなかった検索対象ファイルの圧縮ファイルｆｉに対しては全圧縮ファイルｆ１〜ｆｎへの総アクセス回数のみ１加算する。したがって、並び替え処理部１１０１は、更新後の圧縮ファイル群のアクセス頻度にしたがってソート処理を実行することとなる。これにより、実際に検索された圧縮ファイルｆｉのアクセス頻度が高くなるため、次回以降の検索速度の高速化を実現することができる。

（仮想アーカイブ設定処理手順）
図１３は、情報検索装置１１００の仮想アーカイブ設定機能が実行する仮想アーカイブ設定処理手順を示すフローチャートである。まず、並び替え処理部１１０１により、文字出現マップ連携テーブル２１１を、アクセス頻度の降順にソートする（ステップＳ１３０１）。ここで、並び替え後の順位ｋをｋ＝１とし（ステップＳ１３０２）、積算部１１０２により、順位１〜ｋ＋１までの圧縮ファイルの合計サイズを計算する（ステップＳ１３０３）。そして、合計サイズｓ（１＿ｋ＋１）が、ｓ（１＿ｋ＋１）＞Ｔｓであるか否かを判断する（ステップＳ１３０４）。ここで、Ｔｓはキャッシュ領域２４０に記憶可能な最大の記憶容量である。

ｓ（１＿ｋ＋１）＞Ｔｓでない場合（ステップＳ１３０４：Ｎｏ）、ｋをインクリメントして（ステップＳ１３０５）、ステップＳ１３０３に戻る。一方、ｓ（１＿ｋ＋１）＞Ｔｓである場合（ステップＳ１３０４：Ｙｅｓ）、キャッシュ領域２４０にはこれ以上圧縮ファイルを格納できないため、順位１〜ｋ＋１までの圧縮ファイルのビット番号、アクセス頻度およびサイズとなるように仮想アーカイブ容量テーブル２１３を更新する（ステップＳ１３０６）。

そして、書込み部１１０３により、順位１〜ｋまでの圧縮ファイルをキャッシュ領域２４０に書き込む（ステップＳ１３０７）。この場合、順位ｋ＋１以降の圧縮ファイルはキャッシュ領域２４０から消去される。このあと、設定部１１０４により、文字出現マップ連携テーブル２１１における順位１〜ｋまでの圧縮ファイルの常駐フラグをＯＮ（“０”→“１”）にする（ステップＳ１３０８）。

なお、順位ｋ＋１以降の圧縮ファイルについては、常駐フラグをＯＦＦ（“１”→“０”）にする。これにより一連の処理が終了する。この仮想アーカイブ設定処理手順によれば、検索に先立って、アクセス頻度が高い圧縮ファイルを優先的に仮想アーカイブとして設定することができるため、ファイルアクセスの高速化を実現することができる。

（情報検索処理手順）
図１４は、情報検索装置１１００の情報検索機能が実行する情報検索処理手順を示すフローチャートである。入力部１１０５により、検索文字列の入力を受け付ける（ステップＳ１４０１）。そして、検索文字列を単字または連字（以下、単に「文字」）に分解する（ステップＳ１４０２）。つぎに、分解された文字ごとのビット列を文字出現マップＭから抽出して（ステップＳ１４０３）、抽出されたビット列を同一ビット番号で論理積演算する（ステップＳ１４０４）。

この論理積演算が“１”である圧縮ファイルｆｉを、分解された文字を含む圧縮ファイルとして特定する（ステップＳ１４０５）。このあと、特定された圧縮ファイルｆｉのうち未処理の圧縮ファイルｆｉがあるか否かを判断する（ステップＳ１４０６）。未処理の圧縮ファイルｆｉがある場合（ステップＳ１４０６：Ｙｅｓ）、特定された未処理の圧縮ファイルｆｉを１つ選択し（ステップＳ１４０７）、その選択された圧縮ファイルｆｉに対して常駐フラグがＯＮであるか否かを判断する（ステップＳ１４０８）。

ＯＮである場合（ステップＳ１４０８：Ｙｅｓ）、読出し部１１０７により、キャッシュ領域２４０から直接ＣＰＵ１０１のレジスタに転送して（ステップＳ１４０９）、ステップＳ１４１１に移行する。一方、ＯＦＦである場合（ステップＳ１４０８：Ｎｏ）、読出し部１１０７により、アーカイブ２００の記憶領域２３０からキャッシュ領域２４０にリードして、ＣＰＵ１０１に読み込ませて、ステップＳ１４１１に移行する（ステップＳ１４１０）。ステップＳ１４１１では、伸長部１１０８により、圧縮パラメータ２２１に基づくハフマン木を用いて伸長処理を実行して（ステップＳ１４１１）、ステップＳ１４０６に戻る。

ステップＳ１４０６において、未処理の圧縮ファイルｆｉがない場合（ステップＳ１４０６：Ｎｏ）、検索部１１０９により、伸長された検索対象ファイルを検索文字列により検索する（ステップＳ１４１２）。そして、出力部１１１０により、検索結果を出力する（ステップＳ１４１３）。このあと、更新部１１１１により、文字出現マップ連携テーブル２１１の該当する圧縮ファイルｆｉのアクセス頻度を１加算する（ステップＳ１４１４）。これにより、一連の処理を終了する。

この情報検索処理手順によれば、常駐フラグがＯＮ（“１”）に設定されている圧縮ファイルｆｉをキャッシュ領域２４０から読み出して伸長処理をおこなうため、ファイルアクセスの高速化を実現することができる。また、検索する都度、圧縮ファイルｆｉへのアクセス頻度が更新されるため、キャッシュ領域２４０に書き込まれる圧縮ファイルｆｉを逐次更新することができる。したがって、次回以降のファイルアクセスの高速化も実現することができる。

このように、実施の形態１によれば、アーカイブの圧縮ファイルｆｉのアクセスにおいて、文字出現マップのビット番号をもとに文字出現マップ連携テーブル２１１を利用することで高速化を図ることができる。さらに、アクセス頻度の高いファイルをキャッシュメモリに常駐化することで、ファイルのアクセス処理の時間の短縮化を図ることができる。したがって、伸長するまでの時間が大幅に短縮化され、検索速度の高速化を図ることができる。また、キャッシュ領域を有効活用することで、省メモリ化を図ることができる。なお、この実施の形態１の情報検索装置１１００は、パーソナル・コンピュータや検索サーバーのほか、携帯電話機、携帯型ゲーム機、電子辞書などの携帯型端末に適用することができる。

＜実施の形態２＞
つぎに、実施の形態２について説明する。インターネットでのサイト検索などは、定期的に各サイトの更新を監視し、形態素解析を行った要約データをもとに、大規模なインデックスを作成し、全文検索が行われている。サイトのデータ量の増大に対し、従来では、各サイトの監視の処理の高速化とスループットの増加、複数のコンピュータによる検索のスケーラビリティが課題となっている。

これらの課題に対し、実施の形態２では、アーカイブ２００の追加やマージ、削除などの高速化を実現する。また、グリッドコンピュータなどに関するスケーラビリティに対して、スレーブサーバーに検索を分割し並行処理したり、各スレーブサーバーの稼働率を平準化することで、検索速度の効率化を実現する。

図１５は、実施の形態２にかかる検索システムのシステム構成図である。検索システム１５００は、マスターサーバー１５０１と複数のスレーブサーバー１５０２−１〜１５０２−Ｎを含む構成である。マスターサーバー１５０１と複数のスレーブサーバー１５０２−１〜１５０２−Ｎ、または、スレーブサーバー１５０２−１〜１５０２−Ｎどうしは、ネットワーク１１４を介して相互に通信可能である。マスターサーバー１５０１は、スレーブサーバー１５０２−１〜１５０２−Ｎを統括管理する。各スレーブサーバー１５０２−Ｉは、上述した実施の形態１の情報検索装置１１００に相当し、上述した仮想アーカイブ設定機能と情報検索機能を有する。

なお、各スレーブサーバー１５０２−Ｉ（Ｉ＝１〜Ｎ）が備えるアーカイブ２００の種類は異なる。たとえば、あるスレーブサーバー１５０２−Ｉが保持するアーカイブ２００−Ｉは国語辞典のアーカイブであり、他のスレーブサーバー１５０２−Ｊ（Ｊ≠Ｉ）が保持するアーカイブ２００−Ｊは用語辞典のアーカイブであり、別のスレーブサーバー１５０２−Ｋ（Ｋ≠Ｉ，Ｊ）が保持するアーカイブ２００−Ｋは英和辞典のアーカイブであるなど、それぞれ種類や出版社が異なるアーカイブである。

なお、各スレーブサーバー１５０２−Ｉはそれぞれ異なるアーカイブ２００−Ｉを有するが、各アーカイブ２００−Ｉ内の圧縮パラメータ２２１−Ｉも異なる。したがって、各スレーブサーバー１５０２−Ｉが保持するハフマン木ｈ−Ｉも異なる構造となる。

このようなスレーブサーバー群１５０２に対して、共通の検索キーワードをマスターサーバー１５０１から与えることで、串刺し検索と呼ばれる多書籍検索を実行する。各スレーブサーバー１５０２−Ｉは、検索結果をマスターサーバー１５０１に返すことで、マスターサーバー１５０１は複数辞書の検索結果を得ることができる。以降、説明の簡略化のため、スレーブサーバー１５０２−Ｉの数を２台（Ｎ＝２）として説明する。

図１６は、アーカイブの共通化を示す説明図である。マスターサーバー１５０１は、各スレーブサーバー１５０２−１，１５０２−２における検索処理の平準化のため、スレーブサーバー１５０２−１，１５０２−２のアーカイブ２００−１，２００−２とハフマン木ｈ−１，ｈ−２をネットワーク１１４経由で収集する。そして、各アーカイブ２００−１，２００−２を集約した統合アーカイブＡと、各アーカイブ２００−１，２００−２のハフマン木ｈ−１，ｈ−２を共通化した共通ハフマン木Ｈを生成する。

図１７は、新アーカイブの分配処理を示す説明図である。マスターサーバー１５０１は、スレーブサーバー１５０２−１，１５０２−２の検索処理が平準化するように統合アーカイブＡを分割し、各スレーブサーバー１５０２−１，１５０２−２に固有な新アーカイブＡ１，Ａ２としてスレーブサーバー１５０２−１，１５０２−２に配信する。また、新共通ハフマン木Ｈ１、Ｈ２も各スレーブサーバー１５０２−１，１５０２−２に配信される。本例では、一台のスレーブサーバーに対して１つのアーカイブが割り当てられているため、各スレーブサーバー１５０２−１，１５０２−２に対して共通ハフマン木Ｈを配信しているが、スレーブサーバーごとに複数のアーカイブとそのハフマン木がある場合、スレーブサーバーごとに固有の共通ハフマン木を配信することとなる。たとえば、スレーブサーバー１５０１−１にアーカイブ２００−１，２００−２とハフマン木ｈ−１，ｈ−２がある場合、スレーブサーバー１５０２−１に共通ハフマン木Ｈを配信することとなる。

（ハフマン木の再構成）
図１８は、アーカイブ２００−１の圧縮符号テーブルおよび圧縮パラメータ２２１を示す説明図である。ここでは、説明を単純化するため、アーカイブ２００−１に含まれる圧縮された検索対象ファイル群には、文字ａ〜ｆが記述されているものとする。図１８中、（Ａ）はアーカイブ２００−１の圧縮符号テーブル１８００であり、（Ｂ）はアーカイブ２００−１の圧縮パラメータＰ１である。圧縮符号テーブル１８００において、出現回数が高い文字ほど短い圧縮符号が割り当てられている。

図１９は、アーカイブ２００−１の圧縮符号テーブル１８００から生成されるハフマン木ｈ−１である。図１９中、丸図形（○）が節点である。特に、最上位の節点を根Ｒ、それ以外の節点を内部節点と呼ぶ。また、四角図形（□）が葉、節点間、または、節点と葉とを結ぶ線分が枝である。葉の中に示した文字は伸長後の文字であり、葉の下に示した文字列は、当該葉となる伸長後の文字に割り当てられた圧縮符号である。

図２０は、アーカイブ２００−２の圧縮符号テーブルおよび圧縮パラメータ２２１を示す説明図である。ここでは、説明を単純化するため、アーカイブ２００−２に含まれる圧縮された検索対象ファイル群には、文字ａ〜ｆが記述されているものとする。図２０中、（Ａ）はアーカイブ２００−２の圧縮符号テーブル２０００であり、（Ｂ）はアーカイブ２００−２の圧縮パラメータＰ２である。圧縮符号テーブル２０００において、出現回数が高い文字ほど短い圧縮符号が割り当てられている。図２１は、アーカイブ２００−２の圧縮符号テーブル２０００から生成されるハフマン木ｈ−２を示す説明図である。

図２２は、統合アーカイブＡの圧縮符号テーブルおよび圧縮パラメータ２２１を示す説明図である。統合アーカイブＡは、アーカイブ２００−１，２００−２を統合しているため、統合アーカイブＡに含まれている圧縮された検索対象ファイルには、文字ａ〜ｆが記述されていることとなる。したがって、（Ｂ）に示した共通圧縮パラメータＰの出現回数は、アーカイブ２００−１の圧縮パラメータＰ１とアーカイブ２００−２の圧縮パラメータＰ２の出現回数を同一文字で集計した値となる。図２３は、統合アーカイブＡの圧縮符号テーブルから生成される共通ハフマン木Ｈを示す説明図である。

（アーカイブの再構成）
つぎに、実施の形態２におけるアーカイブの再構成について説明する。ここでは、上述したアーカイブ２００−１とアーカイブ２００−２とを統合して、統合アーカイブＡを生成する。まず、アーカイブ２００−１の記憶内容について説明する。

図２４は、アーカイブ２００−１の記憶内容を示す説明図である。アーカイブ２００−１は、図１に示したＲＡＭ１０３、磁気ディスク１０５などの記憶領域２３０に記憶されている。アーカイブ２００−１は、書庫領域２０１と管理領域２０２とデータ領域２０３とを有する。書庫領域２０１には、文字出現マップ連携テーブル２１１ａとファイルパス連携テーブル２１２ａと仮想アーカイブ容量テーブル２１３ａとが記憶されている。管理領域２０２には、圧縮パラメータＰ１とファイルパステーブル２２２ａと文字出現マップＭａ（単字出現マップＭａ１および連字出現マップＭａ２）とが記憶されている。データ領域２０３には、図３に示したような圧縮ファイル群ｆａ（圧縮ファイルｆａ＿１〜ｆａ＿ｎ）が記憶されている。なお、これらは実施の形態１で説明した内容に準じている。

図２５は、アーカイブ２００−１の単字出現マップＭａ１を示す説明図である。図２６は、アーカイブ２００−１の連字出現マップＭａ２を示す説明図である。アーカイブ２００−１の文字出現マップＭａでは、アーカイブ２００−２と区別するため、便宜上、ビット番号をａ＿１〜ａ＿ｎとする。図２７は、アーカイブ２００−１の圧縮パラメータＰ１を示す説明図である。図２８は、アーカイブ２００−１のファイルパステーブル２２２ａを示す説明図である。図２９は、アーカイブ２００−１の文字出現マップ連携テーブル２１１ａを示す説明図である。図３０は、アーカイブ２００−１のファイルパス連携テーブル２１２ａを示す説明図である。

つぎに、アーカイブ２００−２の記憶内容について説明する。図３１は、アーカイブ２００−２の記憶内容を示す説明図である。アーカイブ２００−２は、図１に示したＲＡＭ１０３、磁気ディスク１０５などの記憶領域２３０に記憶されている。アーカイブ２００−２は、書庫領域２０１と管理領域２０２とデータ領域２０３とを有する。書庫領域２０１には、文字出現マップ連携テーブル２１１ｂとファイルパス連携テーブル２１２ｂと仮想アーカイブ容量テーブル２１３ｂとが記憶されている。管理領域２０２には、圧縮パラメータＰ２とファイルパステーブル２２２ｂと文字出現マップＭｂ（単字出現マップＭｂ１および連字出現マップＭｂ２）とが記憶されている。データ領域２０３には、図３に示したような圧縮ファイル群ｆｂ（圧縮ファイルｆｂ＿１〜ｆｂ＿ｍ）が記憶されている。なお、これらは実施の形態１で説明した内容に準じている。

図３２は、アーカイブ２００−２の単字出現マップＭｂ１を示す説明図である。図３３は、アーカイブ２００−２の連字出現マップＭｂ２を示す説明図である。アーカイブ２００−２の文字出現マップＭｂでは、アーカイブ２００−１と区別するため、便宜上、ビット番号をｂ＿１〜ｂ＿ｍとする。図３４は、アーカイブ２００−２の圧縮パラメータＰ２を示す説明図である。図３５は、アーカイブ２００−２のファイルパステーブル２２２ｂを示す説明図である。図３６は、アーカイブ２００−２の文字出現マップ連携テーブル２１１ｂを示す説明図である。図３７は、アーカイブ２００−２のファイルパス連携テーブル２１２ｂを示す説明図である。

まず、圧縮パラメータＰ１，Ｐ２の再構成について説明する。図３８は、共通パラメータの生成例を示す説明図である。アーカイブ２００−１の圧縮パラメータＰ１とアーカイブ２００−２の圧縮パラメータＰ２を、同一文字（単字／連字）で出現頻度を集計することで、共通圧縮パラメータＰが生成される。

つぎに、文字出現マップ連携テーブル２１１ａ，２１１ｂの再構成について説明する。図３９は、文字出現マップ連携テーブル２１１ａ，２１１ｂの再構成を示す説明図である。アーカイブ２００−１の文字出現マップ連携テーブル２１１ａとアーカイブ２００−２の文字出現マップ連携テーブル２１１ｂとを統合して、アクセス頻度の高い順にソートする。統合後の文字出現マップ連携テーブル３９００は、合計でｎ＋ｍ個のビット番号のアクセス頻度を有することとなる。このあと、アクセス頻度が各スレーブサーバー１５０２−１，１５０２−２において平準化するように、スレーブサーバー１５０２−１，１５０２−２ごとに割り当てる。

ここでは、アクセス頻度が高い順の順位が奇数番目となるビット番号について、スレーブサーバー１５０２−１に割り当てる新たな文字出現マップ連携テーブル３９００ａとする。一方、偶数番目となるビット番号について、スレーブサーバー１５０２−２に割り当てる新たな文字出現マップ連携テーブル３９００ｂとする。割当方法としては、ここでは例として奇数番目と偶数番目としたが、一方のスレーブサーバー１５０２−１に対しては、１位，４位，５位，８位，９位…とし、他方のスレーブサーバー１５０２−２に対しては、２位，３位，６位，７位，１０位…としてもよい。その他、割り当てた順位（またはアクセス頻度）の合計が均等になるように分配すればどのような割り当て方法でもよい。

図４０は、ファイルパス連携テーブル２１２ａ，２１２ｂの再構成を示す説明図である。まず、アーカイブ２００−１のファイルパス連携テーブル２１２ａとアーカイブ２００−２のファイルパス連携テーブル２１２ｂとを統合する。統合後のファイルパス連携テーブル４０００は、合計でｎ＋ｍ個のビット番号のファイルパスを有することとなる。このあと、上述した文字出現マップ連携テーブル３９００で採用された割当方法により、ビット番号を割り当てる。

これにより、一方のスレーブサーバー１５０２−１には、そのスレーブサーバー１５０２−１に割り当てられた文字出現マップ連携テーブル３９００ａのビット番号と同一ビット番号のファイルパス連携テーブル４０００ａが得られる。同様に、他方のスレーブサーバー１５０２−２には、そのスレーブサーバー１５０２−２に割り当てられた文字出現マップ連携テーブル３９００ｂのビット番号と同一ビット番号のファイルパス連携テーブル４０００ｂが得られる。

図４１は、ファイルパステーブル２２２ａ，２２２ｂの再構成を示す説明図である。まず、アーカイブ２００−１のファイルパステーブル２２２ａとアーカイブ２００−２のファイルパステーブル２２２ｂとを統合する。統合後のファイルパステーブル４１００は、合計でｎ＋ｍ個のファイルＩＤのファイルパスを有することとなる。このあと、上述した文字出現マップ連携テーブル３９００で採用された割当方法により、ビット番号に対応するファイルＩＤを割り当てる。

これにより、一方のスレーブサーバー１５０２−１には、そのスレーブサーバー１５０２−１に割り当てられた文字出現マップ連携テーブル３９００ａのビット番号と同一ビット番号に対応するファイルＩＤのファイルパステーブル４１００ａが得られる。同様に、他方のスレーブサーバー１５０２−２には、そのスレーブサーバー１５０２−２に割り当てられた文字出現マップ連携テーブル３９００ｂのビット番号と同一ビット番号に対応するファイルＩＤのファイルパステーブル４１００ｂが得られる。

図４２は、単字出現マップＭａ１，Ｍｂ１の再構成を示す説明図である。まず、アーカイブ２００−１の単字出現マップＭａ１とアーカイブ２００−２の単字出現マップＭｂ１とを統合する。統合後の単字出現マップＭａｂ１は、文字ごとに合計でｎ＋ｍ個のビットからなるビット列を有することとなる。このあと、上述した文字出現マップ連携テーブル３９００で採用された割当方法により、ビット番号を割り当てる。

これにより、一方のスレーブサーバー１５０２−１には、そのスレーブサーバー１５０２−１に割り当てられた文字出現マップ連携テーブル３９００ａのビット番号と同一ビット番号となる単字出現マップＭＡ１が得られる。同様に、他方のスレーブサーバー１５０２−２には、そのスレーブサーバー１５０２−２に割り当てられた文字出現マップ連携テーブル３９００ｂのビット番号と同一ビット番号となる単字出現マップＭＢ１が得られる。

図４３は、連字出現マップＭａ２，Ｍｂ２の再構成を示す説明図である。まず、アーカイブ２００−１の連字出現マップＭａ２とアーカイブ２００−２の連字出現マップＭｂ２とを統合する。統合後の連字出現マップＭａｂ２は、文字ごとに合計でｎ＋ｍ個のビットからなるビット列を有することとなる。このあと、上述した文字出現マップ連携テーブル３９００で採用された割当方法により、ビット番号を割り当てる。

これにより、一方のスレーブサーバー１５０２−１には、そのスレーブサーバー１５０２−１に割り当てられた文字出現マップ連携テーブル３９００ａのビット番号と同一ビット番号となる連字出現マップＭＢ１が得られる。同様に、他方のスレーブサーバー１５０２−２には、そのスレーブサーバー１５０２−２に割り当てられた文字出現マップ連携テーブル３９００ｂのビット番号と同一ビット番号となる連字出現マップＭＢ２が得られる。

図４４は、圧縮ファイル群ｆａ，ｆｂの再構成を示す説明図である。まず、アーカイブ２００−１の圧縮ファイル群ｆａをそのハフマン木ｈ−１を用いて伸長する。これにより、検索対象ファイル群Ｆａが得られる。同様に、アーカイブ２００−２の圧縮ファイル群ｆｂをそのハフマン木ｈ−２を用いて伸長する。これにより、検索対象ファイル群Ｆｂが得られる。

つぎに、検索対象ファイル群Ｆａを、共通ハフマン木Ｈを用いて再圧縮する。これにより、圧縮ファイル群ｇａが得られる。同様に、検索対象ファイル群Ｆｂを、共通ハフマン木Ｈを用いて再圧縮する。これにより、圧縮ファイル群ｇｂが得られる。

このあと、再圧縮された圧縮ファイル群ｇａおよび圧縮ファイル群ｇｂを統合する。そして、上述した文字出現マップ連携テーブル３９００で採用された割当方法により、アクセス頻度の高い順に並び替える。これにより、アクセス頻度順の統合圧縮ファイル群ｇが得られる。

これにより、一方のスレーブサーバー１５０２−１には、そのスレーブサーバー１５０２−１に割り当てられた文字出現マップ連携テーブル３９００ａのビット番号と同一ビット番号の圧縮ファイル群ｇ１が割り当てられる。同様に、他方のスレーブサーバー１５０２−２には、そのスレーブサーバー１５０２−２に割り当てられた文字出現マップ連携テーブル３９００ｂのビット番号と同一ビット番号の圧縮ファイル群ｇ２が割り当てられる。

図４５は、新アーカイブＡ１の記憶内容を示す説明図である。新アーカイブＡ１は、スレーブサーバー１５０２−１に配信される。新アーカイブＡ１には、図３８に示した共通圧縮パラメータＰ、図３９に示した再構成後の文字出現マップ連携テーブル３９００ａ、図４０に示した再構成後のファイルパス連携テーブル４０００ａ、図４１に示した再構成後のファイルパステーブル４１００ａ、図４２に示した再構成後の単字出現マップＭＡ１、図４３に示した再構成後の連字出現マップＭ２、図４４に示した再構成後の圧縮ファイル群ｇ１が格納される。

図４６は、新アーカイブＡ２の記憶内容を示す説明図である。新アーカイブＡ２は、スレーブサーバー１５０２−２に配信される。新アーカイブＡ２には、図３８に示した共通圧縮パラメータＰ、図３９に示した再構成後の文字出現マップ連携テーブル３９００ｂ、図４０に示した再構成後のファイルパス連携テーブル４０００ｂ、図４１に示した再構成後のファイルパステーブル４１００ｂ、図４２に示した再構成後の単字出現マップＭＢ１、図４３に示した再構成後の連字出現マップＭＢ２、図４４に示した再構成後の圧縮ファイル群ｇ２が格納される。

（マスターサーバー１５０１の機能的構成）
図４７は、マスターサーバー１５０１（情報管理装置）の機能的構成を示すブロック図である。マスターサーバー１５０１は、受信部４７０１と、共通圧縮パラメータ生成部４７０２と、共通ハフマン木生成部４７０３と、伸長部４７０４と、圧縮部４７０５と、再構成部４７０６と、送信部４７０７と、を含む構成である。受信部４７０１〜送信部４７０７は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、磁気ディスク１０５などの記憶領域に記憶されたプログラムをＣＰＵ１０１に実行させることによって、または、Ｉ／Ｆ１０９によってその機能を実現する。

まず、受信部４７０１は、スレーブサーバー１５０２−Ｉから送信されてくるデータを受信する機能を有する。具体的には、たとえば、各スレーブサーバー１５０２−１〜１５０２−Ｎからアーカイブ２００−１〜２００−Ｎやハフマン木ｈ−１〜ｈ−Ｎを受信する。

共通圧縮パラメータ生成部４７０２は、全アーカイブ２００−１〜２００−Ｎに対する共通圧縮パラメータＰを生成する機能を有する。具体的には、たとえば、図３８に示したように、各スレーブサーバー１５０２−１，１５０２−２から受信されたアーカイブ２００−１，２００−２に含まれている圧縮パラメータＰ１，Ｐ２を抽出する。そして、抽出された各圧縮パラメータＰ１，Ｐ２の出現回数を同一文字ごとに集計することで、共通圧縮パラメータＰを生成する。生成された共通圧縮パラメータＰは、共通ハフマン木生成部４７０３とアーカイブ生成部４７１３に送られる。

共通ハフマン木生成部４７０３は、全アーカイブ２００−１〜２００−Ｎに対する共通ハフマン木Ｈを生成する機能を有する。具体的には、たとえば、共通圧縮パラメータＰの出現回数の高い文字から２分探索で“０”と“１”を割り当てることにより、共通ハフマン木Ｈを生成する（図２２、図２３を参照。）。生成された共通ハフマン木は、伸長部４７０４とアーカイブ生成部４７１３に送られる。

伸長部４７０４は、アーカイブ２００−Ｉごとに、アーカイブ２００−Ｉに含まれている圧縮ファイル群ｆを伸長する機能を有する。伸長処理に用いられるハフマン木は、アーカイブ２００−Ｉとともに送信されてきたハフマン木ｈ−Ｉである。たとえば、図４４に示したように、圧縮ファイル群ｆａをその圧縮に用いられたハフマン木ｈ−１で伸長することで、検索対象ファイル群Ｆａを得る。同様に、圧縮ファイル群ｆｂをその圧縮に用いられたハフマン木ｈ−２で伸長することで、検索対象ファイル群Ｆｂを得る。

圧縮部４７０５は、伸長部４７０４で伸長された検索対象ファイル群を再圧縮する機能を有する。再圧縮に用いられるハフマン木は共通ハフマン木Ｈである。たとえば、図４４に示したように、検索対象ファイル群Ｆａを共通ハフマン木Ｈで再圧縮することで、圧縮ファイル群ｇａを得る。同様に、検索対象ファイル群Ｆｂをその圧縮に用いられたハフマン木Ｈで再圧縮することで、圧縮ファイル群ｇｂを得る。圧縮ファイル群ｇａ，ｇｂは、統合部４７１１で統合される。

再構成部４７０６は、受信された各アーカイブ２００−Ｉと各ハフマン木ｈ−Ｉを再構成する機能を有する。再構成部４７０６は、統合部４７１１と、割当部４７１２と、アーカイブ生成部４７１３と、を有する。統合部４７１１は、アーカイブ２００−Ｉ内のデータをそれぞれ統合する機能を有する。

具体的には、たとえば、図３９〜図４３に示したように、各アーカイブ２００−１，２００−２の文字出現マップ連携テーブル２１１ａ，２１１ｂ、各ファイルパス連携テーブル２１２ａ，２１２ｂ、各ファイルパステーブル２２２ａ，２２２ｂ、各単字出現マップＭａ１，Ｍｂ１、各連字出現マップＭａ２，Ｍｂ２をそれぞれ統合して、統合後の文字出現マップ連携テーブル３９００、統合後のファイルパス連携テーブル４０００、統合後のファイルパステーブル４１００、統合後の単字出現マップＭａｂ１、統合後の連字出現マップＭａｂ２を得る。

また、統合部４７１１は、図４４に示したように、圧縮部４７０５によってアーカイブ２００−１，２００−２ごとに再圧縮された圧縮ファイル群ｇａ，ｇｂを統合して、統合後の圧縮ファイル群ｇを得る。

割当部４７１２は、統合されたデータをアーカイブ別に、各スレーブサーバー１５０２−Ｉにおいて割当後のアクセス頻度が均等になるように、統合部４７１１によって統合されたデータをスレーブサーバー１５０２−Ｉごとに割り当てる機能を有する。

具体的には、たとえば、図３９に示したように、統合後の文字出現マップ連携テーブル３９００のレコードを、アクセス頻度またはその順位が均等になるように割り当てて、スレーブサーバー１５０２−１，１５０２−２ごとに再構成された文字出現マップ連携テーブル３９００ａ，３９００ｂを得る。

また、図４０〜図４３に示した統合後のファイルパス連携テーブル４０００、統合後のファイルパステーブル４１００、統合後の単字出現マップＭａｂ１、統合後の連字出現マップＭａｂ２についても同様である。また、割当部４７１２は、図４４に示したように、統合後の圧縮ファイル群ｇについても、アクセス頻度またはその順位が均等になるように割り当てて、スレーブサーバー１５０２−１，１５０２−２ごとに再構成された圧縮ファイル群ｇ１，ｇ２を得る。

アーカイブ生成部４７１３は、スレーブサーバー１５０２−Ｉごとに再構成された新アーカイブを生成する機能を有する。具体的には、たとえば、スレーブサーバー１５０２−１，１５０２−２ごとに割り当てられたデータを、スレーブサーバー１５０２−１，１５０２−２ごとにまとめて、図４５および図４６に示したような新アーカイブＡ１，Ａ２とする。

送信部４７０７は、各スレーブサーバー１５０２−Ｉにデータを配信する機能を有する。具体的には、たとえば、アーカイブ２００−１〜２００−Ｎやハフマン木ｈ−１〜ｈ−Ｎの収集リクエストを配信する。また、再構成部４７０６によって再構成された新アーカイブＡ１（Ａ２）と共通ハフマン木Ｈとを組み合わせて、割当先となるスレーブサーバー１５０２−１（１５０２−２）にそれぞれ配信する。

（再構成処理手順）
つぎに、マスターサーバー１５０１によるアーカイブ再構成処理手順について説明する。図４８および図４９は、マスターサーバー１５０１によるアーカイブ再構成処理手順を示すフローチャートである。図４８において、まず、受信部４７０１により、各スレーブサーバー１５０２−１〜１５０２−Ｎのアーカイブ２００−１〜２００−Ｎとハフマン木ｈ−１〜ｈ−Ｎとを収集する（ステップＳ４８０１）。

つぎに、統合部４７１１により、アーカイブ２００−１，２００−２内の文字出現マップ連携テーブル２１１ａ，２１１ｂを抽出して統合する（ステップＳ４８０２）。そして、割当部４７１２により、統合後の文字出現マップ連携テーブル３９００をアクセス頻度の高い順（降順）にソートして（ステップＳ４８０３）、スレーブサーバー１５０２−１，１５０２−２ごとに文字出現マップ連携テーブル３９００ａ，３９００ｂを割り当てる（ステップＳ４８０４）。

つぎに、各ファイルパステーブル２２２ａ，２２２ｂ、各ファイルパス連携テーブル２１２ａ，２１２ｂ、および各文字出現マップＭａ，Ｍｂを統合し、アクセス頻度の高いビット番号（または対応するファイルＩＤ）にしたがって、スレーブサーバー１５０２−１，１５０２−２ごとに割り当てることで再構成する（ステップＳ４８０５）。

そして、共通圧縮パラメータ生成部４７０２により、共通圧縮パラメータＰを生成し（ステップＳ４８０６）、この共通圧縮パラメータＰを用いて、共通ハフマン木生成部４７０３により、共通ハフマン木Ｈを生成する（ステップＳ４８０７）。

つぎに、図４９において、伸長部４７０４により、アーカイブ２００−１，２００−２ごとの圧縮ファイル群ｆａ，ｆｂをその圧縮に用いたハフマン木ｈ−１，ｈ−２で伸長する（ステップＳ４９０１）。そして、圧縮部４７０５により、アーカイブ２００−１，２００−２ごとに伸長された検索対象ファイル群Ｆａ，Ｆｂを共通ハフマン木Ｈで再圧縮する（ステップＳ４９０２）。つぎに、統合部４７１１により、再圧縮された各圧縮ファイル群ｇａ，ｇｂを統合して（ステップＳ４９０３）、アクセス頻度の高いビット番号順（降順）にソートする（ステップＳ４９０４）。

このあと、割当部４７１２により、アクセス頻度またはその順位の合計が均等になるように、各スレーブサーバー１５０２−１，１５０２−２に割り当てる（ステップＳ４９０５）。そして、アーカイブ生成部４７１３により、スレーブサーバー１５０２−１，１５０２−２ごとの新アーカイブＡ１，Ａ２を生成して（ステップＳ４９０６）、新アーカイブＡ１（Ａ２）および共通ハフマン木Ｈを各新アーカイブＡ１（Ａ２）の割当先となるスレーブサーバー１５０２−１（１５０２−２）に配信する（ステップＳ４９０７）。これにより、一連の処理を終了する。

このように、実施の形態２によれば、各スレーブサーバー１５０２−１，１５０２−２のアーカイブ２００−１，２００−２を再構成することで、スレーブサーバー１５０２−１，１５０２−２の検索速度の均一化を図ることができる。したがって、同一の検索文字列を各スレーブサーバー１５０２−１，１５０２−２に与えた場合、ほぼ同時に検索結果が各スレーブサーバー１５０２−１，１５０２−２から返ってくる。すなわち、最後の検索結果が返ってくるまでの待ち時間が短縮化されるため、検索速度の向上を図ることができる。

＜実施の形態３＞
つぎに、実施の形態３について説明する。実施の形態３は、実施の形態２の一部を改良した構成である。実施の形態２では、各アーカイブ２００−Ｉの圧縮ファイル群を、その圧縮に用いられたハフマン木ｈ−Ｉでそれぞれ伸長する工程と、伸長された検索対象ファイル群を共通ハフマン木Ｈで再圧縮する工程とを実行する。この伸長および再圧縮という２パス処理をおこなっておくことにより、各スレーブサーバー１５０２−Ｉにおいて、共通ハフマン木Ｈを用いて圧縮／伸長することができる構成としている。

これに対し、実施の形態３では、ハフマン木の伸長処理を利用して、スレーブサーバー１５０２−Ｉごとのハフマン木の葉に埋め込まれている伸長文字と同一文字の葉を、共通ハフマン木Ｈから特定する。そして、共通ハフマン木Ｈの特定された葉に割り当てられた圧縮符号を、特定元となるハフマン木ｈ−Ｉの葉の伸長文字のかわりに設定する。設定後のハフマン木を変換用ハフマン木と称す。

そして、変換用ハフマン木を用いて、設定前のハフマン木ｈ−Ｉで圧縮した圧縮ファイル群の伸長処理を施すことにより、圧縮ファイル群が、共通ハフマン木Ｈの圧縮符号に対応する圧縮ファイル群に変換される。このように、１回の変換処理という１パス処理により、圧縮形式のまま共通ハフマン木Ｈの圧縮符号に対応する圧縮ファイル群をスレーブサーバー１５０２−Ｉごとに得ることができる。したがって、マスターサーバー１５０１における再構成処理の高速化を実現することができる。

なお、上述した実施の形態１，２と同一構成には同一符号を付し、その説明を省略する。また、実施の形態３においても、説明の簡略化のため、マスターサーバー１５０２−Ｉの数を２台（Ｎ＝２）として説明する。

図５０は、変換用ハフマン木の生成例（その１）を示す説明図である。図５０では、アーカイブ２００−１のハフマン木ｈ−１と共通ハフマン木Ｈとを用いた生成例を示している。ここで、ハフマン木ｈ−１の文字「ｂ」が設定されている葉に注目する。まず、この注目葉の文字「ｂ」と同一文字が設定されている共通ハフマン木の葉を特定する（ステップＳ５００１）。つぎに、特定された共通ハフマン木の葉の文字「ｂ」に割り当てられている圧縮符号「１１０」およびその圧縮符号長（この例では３）を読み出す（ステップＳ５００２）。そして、注目葉に設定されている文字「ｂ」に代えて、読み出された圧縮符号およびその圧縮符号長「１１０（３）」を書き込む（ステップＳ５００３）。他の文字ａ，ｃ〜ｆについても同様に変換する。

図５１は、変換用ハフマン木の生成例（その２）を示す説明図である。図５１では、アーカイブ２００−２のハフマン木ｈ−２と共通ハフマン木Ｈとを用いた生成例を示している。ここで、ハフマン木ｈ−２の文字「ｆ」が設定されている葉に注目する。まず、この注目葉の文字「ｆ」と同一文字が設定されている共通ハフマン木の葉を特定する（ステップＳ５１０１）。つぎに、特定された共通ハフマン木の葉の文字「ｆ」に割り当てられている圧縮符号「１１１０」およびその圧縮符号長（この例では４）を読み出す（ステップＳ５１０２）。そして、注目葉に設定されている文字「ｆ」に代えて、読み出された圧縮符号およびその圧縮符号長「１１１０（４）」を書き込む（ステップＳ５１０３）。他の文字ａ〜ｅについても同様に変換する。

図５２は、変換用ハフマン木を示す説明図（その１）である。この変換用ハフマン木Ｈ１は、図５０に示したアーカイブ２００−１のハフマン木ｈ−１と共通ハフマン木Ｈとを用いた生成処理により生成されたハフマン木である。この変換用ハフマン木Ｈ１を用いて、たとえば、圧縮符号「１１１０」が割り当てられた伸長文字に伸長しようとすると、図５０に示した文字「ｂ」に伸長されるのではなく、文字「ｂ」の代わりに設定された圧縮符号「１１０」に変換される。したがって、圧縮ファイルの伸長および再圧縮という２パス処理が不要となり、圧縮形式のまま１パス処理により、共通ハフマン木Ｈで圧縮／伸長可能な圧縮ファイルを得ることができる。

図５３は、変換用ハフマン木を示す説明図（その２）である。この変換用ハフマン木Ｈ２は、図５１に示したアーカイブ２００−２のハフマン木ｈ−２と共通ハフマン木Ｈとを用いた生成処理により生成されたハフマン木である。この変換用ハフマン木Ｈ２を用いて、たとえば、圧縮符号「１１１１」が割り当てられた伸長文字に伸長しようとすると、図５１に示した文字「ｆ」に伸長されるのではなく、文字「ｆ」の代わりに設定された圧縮符号「１１１０」に変換される。したがって、圧縮ファイルの伸長および再圧縮という２パス処理が不要となり、圧縮形式のまま１パス処理により、共通ハフマン木Ｈで圧縮／伸長可能な圧縮ファイルを得ることができる。

（マスターサーバー１５０１の機能的構成）
図５４は、実施の形態３にかかるマスターサーバー１５０１（情報管理装置）の機能的構成を示すブロック図である。マスターサーバー１５０１は、実施の形態２で説明した構成のほか、選択部５４０１と、特定部５４０２と、設定部５４０３と、変換部５４０４と、を含む構成である。選択部５４０１〜変換部５４０４は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、磁気ディスク１０５などの記憶領域に記憶されたプログラムをＣＰＵ１０１に実行させることによって、または、Ｉ／Ｆ１０９によってその機能を実現する。

選択部５４０１は、アーカイブ２００−Ｉごとに、当該アーカイブ２００−Ｉ内の圧縮ファイル群の圧縮に用いられたハフマン木ｈ−Ｉから任意の葉を順次選択する機能を有する。具体的には、たとえば、図５０および図５１に示したハフマン木ｈ−Ｉの葉を順次選択する。

特定部５４０２は、選択部５４０１によって順次選択された葉で伸長される文字と同一文字の葉を、共通ハフマン木Ｈから特定する機能を有する。具体的には、図５０および図５１で示したように、同一文字が設定されている共通ハフマン木Ｈの葉を特定する。

設定部５４０３は、ハフマン木ｈ−Ｉにおいて選択された葉に、当該選択された葉で伸長される文字に代えて、特定部５４０２によって特定された葉に割り当てられた圧縮符号を設定する機能を有する。具体的には、選択された葉の構造体中、伸長文字が書き込まれている領域に、共通ハフマン木Ｈから特定された圧縮符号を上書きする。また、その他の空き領域に圧縮符号長を書き込んでおく。なお、この設定対象となる葉の構造体では、上位節点へのポインタはそのままであるため、その選択された葉に割り当てられた圧縮符号を指定することで、葉の構造体に書き込まれた圧縮符号に変換される。

変換部５４０４は、変換用ハフマン木Ｈ１，Ｈ２を用いて、その変換前のハフマン木ｈ−１，ｈ−２で圧縮された圧縮ファイルを圧縮形式のまま変換する機能を有する。これにより、共通ハフマン木Ｈで圧縮／伸長可能な圧縮ファイル群ｇａ，ｇｂとなる。なお、変換後の圧縮ファイル群ｇａ，ｇｂは、実施の形態２と同様、統合部４７１１により統合され、割当部４７１２によりアクセス頻度またはその順位の合計が均等になるように、スレーブサーバー１５０２−１，１５０２−２ごとに割り当てられる。

（再構成処理手順）
つぎに、実施の形態３におけるマスターサーバー１５０１によるアーカイブ再構成処理手順について説明する。図５５は、マスターサーバー１５０１によるアーカイブ再構成処理手順（後半）を示すフローチャートである。なお、再構成処理手順（前半）は、図４８と同一であるため、説明を省略する。

まず、ハフマン木ｈ−１，ｈ−２への圧縮符号設定処理を実行する（ステップＳ５５０１）。つぎに、変換部５４０４により、１パス変換処理を実行する（ステップＳ５５０２）。１パス変換処理は、アーカイブ２００−１，２００−２ごとに得られた変換用ハフマン木Ｈ１，Ｈ２を用いて、アーカイブ２００−１，２００−２内の圧縮ファイル群ｇａ，ｇｂごとに実行する。

そして、統合部４７１１により、変換後の圧縮ファイル群ｇａ，ｇｂを統合し（ステップＳ５５０３）、アクセス頻度の高い順（降順）にソートする（ステップＳ５５０４）。このあと、割当部４７１２により、アクセス頻度またはその順位の合計が均等になるように、各スレーブサーバー１５０２−１，１５０２−２に割り当てる（ステップＳ５５０５）。

そして、アーカイブ生成部４７１３により、スレーブサーバー１５０２−１，１５０２−２ごとの新アーカイブＡ１，Ａ２を生成して（ステップＳ５５０６）、新アーカイブＡ１（Ａ２）および共通ハフマン木Ｈを各新アーカイブＡ１（Ａ２）の割当先となるスレーブサーバー１５０２−１（１５０２−２）に配信する（ステップＳ５５０７）。これにより、一連の処理を終了する。

図５６は、ハフマン木への圧縮符号設定処理の詳細な処理手順を示すフローチャートである。まず、選択部５４０１により、各アーカイブ２００−１，２００−２のハフマン木ｈ−１，ｈ−２の中から、未処理のハフマン木があるか否かを判断する（ステップＳ５６０１）。未処理のハフマン木がある場合（ステップＳ５６０１：Ｙｅｓ）、未処理のハフマン木を１つ選択する（ステップＳ５６０２）。そして、選択ハフマン木の中に未処理の葉があるか否かを判断する（ステップＳ５６０３）。

未処理の葉がある場合（ステップＳ５６０３：Ｙｅｓ）、未処理の葉を１つ選択する（ステップＳ５６０４）。そして、特定部５４０２により、共通ハフマン木Ｈから選択葉に設定されている文字と同一文字が設定されている葉を特定する（ステップＳ５６０５）。このあと、設定部５４０３により、特定された葉に割り当てられた圧縮符号とその圧縮符号長を、選択葉の構造体に設定して（ステップＳ５６０６）、ステップＳ５６０３に戻る。

ステップＳ５６０３において、未処理の葉がない場合（ステップＳ５６０３：Ｎｏ）、ステップＳ５６０１に戻る。ステップＳ５６０１において、未処理のハフマン木がない場合（ステップＳ５６０１：Ｎｏ）、１パス変換処理（ステップＳ５５０２）に移行する。

このように、実施の形態３によれば、ハフマン木の伸長処理という既存の処理を利用することで、１回の変換処理という１パス処理により、圧縮形式のまま共通ハフマン木の圧縮符号に対応する圧縮ファイル群をスレーブサーバー１５０２−１，１５０２−２ごとに得ることができる。したがって、共通ハフマン木Ｈに適用させるためのファイルオープン処理（伸長処理）が不要となり、マスターサーバー１５０１におけるアーカイブ再構成処理の高速化を実現することができる。また、ハフマン木の伸長処理という既存の処理を応用しているため、あらたなアルゴリズムを構築することなく、シンプルな構成でアーカイブ２００再構成処理を実現することができる。

以上のことから、上述した実施の形態１〜３によれば、圧縮ファイルに対して圧縮形式のままで全文検索を実現する際に、ファイルアクセス処理の高速化を図ることにより検索処理の効率化を実現することができる。また、キャッシュ領域による常駐メモリ化や各サーバー資源の効率化により、全文検索の高速化を実現することができる。

なお、本実施の形態で説明した方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な媒体であってもよい。

上述した実施の形態に関し、さらに以下の付記を開示する。

（付記１）文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブにアクセス可能なコンピュータを、
前記各圧縮ファイルへのアクセス頻度の高い順に並び替える並び替え手段、
前記圧縮ファイル群が記憶されている記憶領域に対するキャッシュ領域の記憶容量を超えないように、前記並び替え手段による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算する積算手段、
前記積算手段によって積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み手段、
として機能させることを特徴とする情報検索プログラム。

（付記２）前記積算手段は、
前記キャッシュ領域の記憶容量を超えない最大の積算値となるように、前記並び替え手段による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算し、
前記書込み手段は、
前記最大の積算値として積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み手段、
として機能させることを特徴とする情報検索プログラム。

（付記３）前記コンピュータを、
前記書込み手段によって前記キャッシュ領域に書き込まれた圧縮ファイル群について常駐フラグを設定する設定手段、
検索文字列の入力を受け付ける入力手段、
前記圧縮ファイルごとの文字の存否を特定する文字出現マップを参照することにより、前記入力手段によって入力された検索文字列を構成するすべての文字が存在する圧縮ファイルを特定する特定手段、
前記特定手段によって特定された圧縮ファイルを、前記設定手段によって設定された常駐フラグに基づく領域から読み出す読出し手段、
前記読出し手段によって読み出された圧縮ファイルを伸長する伸長手段、
前記伸長手段によって伸長された検索対象ファイルを出力する出力手段、
として機能させることを特徴とする付記１または２に記載の情報検索プログラム。

（付記４）前記コンピュータを、
前記伸長手段によって伸長された検索対象ファイルの中から前記検索文字列に一致または関連する文字列を検索する検索手段として機能させ、
前記出力手段は、
前記検索手段によって検索された検索結果を出力することを特徴とする付記３に記載の情報検索プログラム。

（付記５）前記コンピュータを、
前記伸長手段によって前記圧縮ファイルが伸長された場合、当該圧縮ファイルへのアクセス頻度を更新する更新手段として機能させ、
前記並び替え手段は、
前記更新手段によって更新された更新後のアクセス頻度に基づいて、前記各圧縮ファイルへのアクセス頻度の高い順に並び替えることを特徴とする付記３または４に記載の情報検索プログラム。

（付記６）前記コンピュータを、
前記検索手段によって検索対象ファイルが検索された場合、当該検索対象ファイルが圧縮された圧縮ファイルへのアクセス頻度を更新する更新手段として機能させ、
前記並び替え手段は、
前記更新手段によって更新された更新後のアクセス頻度に基づいて、前記各圧縮ファイルへのアクセス頻度の高い順に並び替えることを特徴とする付記４に記載の情報検索プログラム。

（付記７）文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブを記憶する複数のスレーブサーバーにアクセス可能なマスターサーバーを、
前記各スレーブサーバーから前記アーカイブを受信する受信手段、
前記受信手段によって受信されたアーカイブごとの前記検索対象ファイル群に記述されている各文字および当該各文字の出現頻度に関する圧縮パラメータに基づいて、前記出現頻度を前記文字ごとに集計することにより、前記各圧縮ファイル群に共通の圧縮パラメータを生成する圧縮パラメータ生成手段、
前記圧縮パラメータ生成手段によって生成された共通の圧縮パラメータに基づいて、前記各圧縮ファイル群に共通のハフマン木を生成する共通ハフマン木生成手段、
前記圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記圧縮ファイルを割り当てる割当手段、
前記割当手段によって前記各スレーブサーバーに割り当てられた圧縮ファイル群を含むあらたなアーカイブと前記共通ハフマン木生成手段によって生成された共通のハフマン木とを、割当先となるスレーブサーバーに送信する送信手段、
として機能させることを特徴とする情報管理プログラム。

（付記８）前記マスターサーバーを、
前記アーカイブごとに、当該アーカイブに含まれている圧縮ファイル群を、当該圧縮ファイル群の圧縮に用いられた圧縮パラメータに基づくハフマン木により伸長する伸長手段、
前記伸長手段によって伸長された検索対象ファイル群を、前記共通のハフマン木により圧縮する圧縮手段として機能させ、
前記割当手段は、
前記圧縮手段によって圧縮された再圧縮ファイルの元となる圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記再圧縮ファイルを割り当て、
前記送信手段は、
前記再圧縮ファイル群を含むあらたなアーカイブと前記共通のハフマン木とを、前記割当先となるスレーブサーバーに送信することを特徴とする付記７に記載の情報管理プログラム。

（付記９）前記マスターサーバーを、
前記アーカイブごとに、当該アーカイブ内の圧縮ファイル群の圧縮に用いられたハフマン木から任意の葉を順次選択する選択手段、
前記選択手段によって順次選択された葉で伸長される文字と同一文字の葉を、前記共通のハフマン木から特定する特定手段、
前記ハフマン木における前記選択された葉に、当該選択された葉で伸長される文字に代えて、前記特定手段によって特定された葉に割り当てられた圧縮符号を設定する設定手段、
前記設定手段による設定後のハフマン木を用いて、前記アーカイブ内の圧縮ファイル群を、前記設定手段によって設定された圧縮符号で圧縮された圧縮ファイル群に変換する変換手段として機能させ、
前記割当手段は、
前記変換手段によって変換された変換後の圧縮ファイルの変換元となる圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記変換後の圧縮ファイルを割り当て、
前記送信手段は、
前記変換手段による変換後の圧縮ファイル群を含むアーカイブと前記共通のハフマン木とを、前記割当先となるスレーブサーバーに送信することを特徴とする付記７に記載の情報管理プログラム。

（付記１０）前記割当手段は、
前記アクセス頻度の順位の合計が互いに近似するように割り当てることを特徴とする付記７〜９のいずれか一つに記載の情報管理プログラム。

（付記１１）文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブにアクセス可能な情報検索装置であって、
前記各圧縮ファイルへのアクセス頻度の高い順に並び替える並び替え手段と、
前記圧縮ファイル群が記憶されている記憶領域に対するキャッシュ領域の記憶容量を超えないように、前記並び替え手段による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算する積算手段と、
前記積算手段によって積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み手段と、
を備えることを特徴とする情報検索装置。

（付記１２）文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブを記憶する複数のスレーブサーバーにアクセス可能な情報管理装置であって、
前記各スレーブサーバーから前記アーカイブを受信する受信手段と、
前記受信手段によって受信されたアーカイブごとの前記検索対象ファイル群に記述されている各文字および当該各文字の出現頻度に関する圧縮パラメータに基づいて、前記出現頻度を前記文字ごとに集計することにより、前記各圧縮ファイル群に共通の圧縮パラメータを生成する圧縮パラメータ生成手段と、
前記圧縮パラメータ生成手段によって生成された共通の圧縮パラメータに基づいて、前記各圧縮ファイル群に共通のハフマン木を生成する共通ハフマン木生成手段と、
前記圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記圧縮ファイルを割り当てる割当手段と、
前記割当手段によって前記各スレーブサーバーに割り当てられた圧縮ファイル群を含むあらたなアーカイブと前記共通ハフマン木生成手段によって生成された共通のハフマン木とを、割当先となるスレーブサーバーに送信する送信手段と、
を備えることを特徴とする情報管理装置。

（付記１３）文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブにアクセス可能な情報検索装置が、
前記各圧縮ファイルへのアクセス頻度の高い順に並び替える並び替え工程と、
前記圧縮ファイル群が記憶されている記憶領域に対するキャッシュ領域の記憶容量を超えないように、前記並び替え工程による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算する積算工程と、
前記積算工程によって積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み工程と、
を実行することを特徴とする情報検索方法。

（付記１４）文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブを記憶する複数のスレーブサーバーにアクセス可能なマスターサーバーが、
前記各スレーブサーバーから前記アーカイブを受信する受信工程と、
前記受信工程によって受信されたアーカイブごとの前記検索対象ファイル群に記述されている各文字および当該各文字の出現頻度に関する圧縮パラメータに基づいて、前記出現頻度を前記文字ごとに集計することにより、前記各圧縮ファイル群に共通の圧縮パラメータを生成する圧縮パラメータ生成工程と、
前記圧縮パラメータ生成工程によって生成された共通の圧縮パラメータに基づいて、前記各圧縮ファイル群に共通のハフマン木を生成する共通ハフマン木生成工程と、
前記圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記圧縮ファイルを割り当てる割当工程と、
前記割当工程によって前記各スレーブサーバーに割り当てられた圧縮ファイル群を含むあらたなアーカイブと前記共通ハフマン木生成工程によって生成された共通のハフマン木とを、割当先となるスレーブサーバーに送信する送信工程と、
を実行することを特徴とする情報管理方法。

実施の形態１にかかる情報検索装置のハードウェア構成を示すブロック図である。 アーカイブの記憶内容を示す説明図である。 圧縮ファイルと検索対象ファイルとの関係を示す説明図である。 単字出現マップを示す説明図である。 連字出現マップを示す説明図である。 圧縮パラメータを示す説明図である。 ファイルパステーブルを示す説明図である。 文字出現マップ連携テーブルを示す説明図である。 ファイルパス連携テーブルを示す説明図である。 仮想アーカイブ容量テーブルを示す説明図である。 情報検索装置の機能的構成を示すブロック図である。 文字出現マップを用いた圧縮ファイルの絞込み例を示す説明図である。 情報検索装置の仮想アーカイブ設定機能が実行する仮想アーカイブ設定処理手順を示すフローチャートである。 情報検索装置の情報検索機能が実行する情報検索処理手順を示すフローチャートである。 実施の形態２にかかる検索システムのシステム構成図である。 アーカイブの共通化を示す説明図である。 新アーカイブの分配処理を示す説明図である。 アーカイブ２００−１の圧縮符号テーブルおよび圧縮パラメータを示す説明図である。 アーカイブ２００−１の圧縮符号テーブルから生成されるハフマン木である。 アーカイブ２００−２の圧縮符号テーブルおよび圧縮パラメータを示す説明図である。 アーカイブ２００−２の圧縮符号テーブルから生成されるハフマン木を示す説明図である。 統合アーカイブの圧縮符号テーブルおよび圧縮パラメータを示す説明図である。 統合アーカイブの圧縮符号テーブルから生成される共通ハフマン木を示す説明図である。 アーカイブ２００−１の記憶内容を示す説明図である。 アーカイブ２００−１の単字出現マップを示す説明図である。 アーカイブ２００−１の連字出現マップを示す説明図である。 アーカイブ２００−１の圧縮パラメータを示す説明図である。 アーカイブ２００−１のファイルパステーブルを示す説明図である。 アーカイブ２００−１の文字出現マップ連携テーブルを示す説明図である。 アーカイブ２００−１のファイルパス連携テーブルを示す説明図である。 アーカイブ２００−２の記憶内容を示す説明図である。 アーカイブ２００−２の単字出現マップＭｂ１を示す説明図である。 アーカイブ２００−２の連字出現マップＭｂ２を示す説明図である。 アーカイブ２００−２の圧縮パラメータＰ２を示す説明図である。 アーカイブ２００−２のファイルパステーブル２２２ｂを示す説明図である。 アーカイブ２００−２の文字出現マップ連携テーブルを示す説明図である。 アーカイブ２００−２のファイルパス連携テーブルを示す説明図である。 共通パラメータの生成例を示す説明図である。 文字出現マップ連携テーブルの再構成を示す説明図である。 ファイルパス連携テーブルの再構成を示す説明図である。 ファイルパステーブルの再構成を示す説明図である。 単字出現マップの再構成を示す説明図である。 連字出現マップの再構成を示す説明図である。 圧縮ファイル群の再構成を示す説明図である。 新アーカイブＡ１の記憶内容を示す説明図である。 新アーカイブＡ２の記憶内容を示す説明図である。 マスターサーバー（情報管理装置）の機能的構成を示すブロック図である。 マスターサーバーによるアーカイブ再構成処理手順（前半）を示すフローチャートである。 マスターサーバーによるアーカイブ再構成処理手順（後半）を示すフローチャートである。 変換用ハフマン木の生成例（その１）を示す説明図である。 変換用ハフマン木の生成例（その２）を示す説明図である。 変換用ハフマン木を示す説明図（その１）である。 変換用ハフマン木を示す説明図（その２）である。 実施の形態３にかかるマスターサーバー１５０１（情報管理装置）の機能的構成を示すブロック図である。 実施の形態３におけるマスターサーバーによるアーカイブ再構成処理手順（後半）を示すフローチャートである。 ハフマン木への圧縮符号設定処理の詳細な処理手順を示すフローチャートである。

符号の説明

１１００ 情報検索装置
１１０１ 並び替え処理部
１１０２ 積算部
１１０３ 書込み部
１１０４ 設定部
１１０５ 入力部
１１０６ 特定部
１１０７ 読出し部
１１０８ 伸長部
１１０９ 検索部
１１１０ 出力部
１１１１ 更新部
１５００ 検索システム
１５０１ マスターサーバー
１５０２ スレーブサーバー群
４７０１ 受信部
４７０２ 共通圧縮パラメータ生成部
４７０３ 共通ハフマン木生成部
４７０４ 伸長部
４７０５ 圧縮部
４７０６ 再構成部
４７０７ 送信部
４７１１ 統合部
４７１２ 割当部
４７１３ アーカイブ生成部
５４０１ 選択部
５４０２ 特定部
５４０３ 設定部
５４０４ 変換部

Claims (8)

1. 文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブにアクセス可能なコンピュータを、
   前記各圧縮ファイルへのアクセス頻度の高い順に並び替える並び替え手段、
   前記圧縮ファイル群が記憶されている記憶領域に対するキャッシュ領域の記憶容量を超えないように、前記並び替え手段による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算する積算手段、
   前記積算手段によって積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み手段、
   として機能させることを特徴とする情報検索プログラム。
2. 前記積算手段は、
   前記キャッシュ領域の記憶容量を超えない最大の積算値となるように、前記並び替え手段による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算し、
   前記書込み手段は、
   前記最大の積算値として積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み手段、
   として機能させることを特徴とする情報検索プログラム。
3. 前記コンピュータを、
   前記書込み手段によって前記キャッシュ領域に書き込まれた圧縮ファイル群について常駐フラグを設定する設定手段、
   検索文字列の入力を受け付ける入力手段、
   前記圧縮ファイルごとの文字の存否を特定する文字出現マップを参照することにより、前記入力手段によって入力された検索文字列を構成するすべての文字が存在する圧縮ファイルを特定する特定手段、
   前記特定手段によって特定された圧縮ファイルを、前記設定手段によって設定された常駐フラグに基づく領域から読み出す読出し手段、
   前記読出し手段によって読み出された圧縮ファイルを伸長する伸長手段、
   前記伸長手段によって伸長された検索対象ファイルを出力する出力手段、
   として機能させることを特徴とする請求項１または２に記載の情報検索プログラム。
4. 文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブを記憶する複数のスレーブサーバーにアクセス可能なマスターサーバーを、
   前記各スレーブサーバーから前記アーカイブを受信する受信手段、
   前記受信手段によって受信されたアーカイブごとの前記検索対象ファイル群に記述されている各文字および当該各文字の出現頻度に関する圧縮パラメータに基づいて、前記出現頻度を前記文字ごとに集計することにより、前記各圧縮ファイル群に共通の圧縮パラメータを生成する圧縮パラメータ生成手段、
   前記圧縮パラメータ生成手段によって生成された共通の圧縮パラメータに基づいて、前記各圧縮ファイル群に共通のハフマン木を生成する共通ハフマン木生成手段、
   前記圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記圧縮ファイルを割り当てる割当手段、
   前記割当手段によって前記各スレーブサーバーに割り当てられた圧縮ファイル群を含むあらたなアーカイブと前記共通ハフマン木生成手段によって生成された共通のハフマン木とを、割当先となるスレーブサーバーに送信する送信手段、
   として機能させることを特徴とする情報管理プログラム。
5. 文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブにアクセス可能な情報検索装置であって、
   前記各圧縮ファイルへのアクセス頻度の高い順に並び替える並び替え手段と、
   前記圧縮ファイル群が記憶されている記憶領域に対するキャッシュ領域の記憶容量を超えないように、前記並び替え手段による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算する積算手段と、
   前記積算手段によって積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み手段と、
   を備えることを特徴とする情報検索装置。
6. 文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブを記憶する複数のスレーブサーバーにアクセス可能な情報管理装置であって、
   前記各スレーブサーバーから前記アーカイブを受信する受信手段と、
   前記受信手段によって受信されたアーカイブごとの前記検索対象ファイル群に記述されている各文字および当該各文字の出現頻度に関する圧縮パラメータに基づいて、前記出現頻度を前記文字ごとに集計することにより、前記各圧縮ファイル群に共通の圧縮パラメータを生成する圧縮パラメータ生成手段と、
   前記圧縮パラメータ生成手段によって生成された共通の圧縮パラメータに基づいて、前記各圧縮ファイル群に共通のハフマン木を生成する共通ハフマン木生成手段と、
   前記圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記圧縮ファイルを割り当てる割当手段と、
   前記割当手段によって前記各スレーブサーバーに割り当てられた圧縮ファイル群を含むあらたなアーカイブと前記共通ハフマン木生成手段によって生成された共通のハフマン木とを、割当先となるスレーブサーバーに送信する送信手段と、
   を備えることを特徴とする情報管理装置。
7. 文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブにアクセス可能な情報検索装置が、
   前記各圧縮ファイルへのアクセス頻度の高い順に並び替える並び替え工程と、
   前記圧縮ファイル群が記憶されている記憶領域に対するキャッシュ領域の記憶容量を超えないように、前記並び替え工程による並び替え後のアクセス頻度の高い順から前記圧縮ファイルのサイズを積算する積算工程と、
   前記積算工程によって積算された圧縮ファイル群を、当該ファイル群の検索に先立って、前記記憶領域からキャッシュ領域に書き込む書込み工程と、
   を実行することを特徴とする情報検索方法。
8. 文字列が記述された検索対象ファイルが圧縮された圧縮ファイル群を含むアーカイブを記憶する複数のスレーブサーバーにアクセス可能なマスターサーバーが、
   前記各スレーブサーバーから前記アーカイブを受信する受信工程と、
   前記受信工程によって受信されたアーカイブごとの前記検索対象ファイル群に記述されている各文字および当該各文字の出現頻度に関する圧縮パラメータに基づいて、前記出現頻度を前記文字ごとに集計することにより、前記各圧縮ファイル群に共通の圧縮パラメータを生成する圧縮パラメータ生成工程と、
   前記圧縮パラメータ生成工程によって生成された共通の圧縮パラメータに基づいて、前記各圧縮ファイル群に共通のハフマン木を生成する共通ハフマン木生成工程と、
   前記圧縮ファイルへのアクセス頻度の合計が互いに近似するように、前記各スレーブサーバーに前記圧縮ファイルを割り当てる割当工程と、
   前記割当工程によって前記各スレーブサーバーに割り当てられた圧縮ファイル群を含むあらたなアーカイブと前記共通ハフマン木生成工程によって生成された共通のハフマン木とを、割当先となるスレーブサーバーに送信する送信工程と、
   を実行することを特徴とする情報管理方法。

Images