(57)【要約】  セグメント（ｓｇ２（１））について、文字情報「人」の圧縮符号（Ｐ（人））の集約出現マップと、文字情報「形」の圧縮符号（Ｐ（形））の集約出現マップと、集約削除マップと、のＡＮＤ演算をおこなう。ＡＮＤ結果は「１１００」となり、セグメント（ｓｇ１（１）），（ｓｇ１（２））に、文字情報「人」および「形」が存在する可能性があることがわかる。このＡＮＤ結果からセグメント（ｓｇ１（１）），（ｓｇ１（２））が指定されたため、ＡＮＤ演算を実行する。これにより、セグメント（ｓｇ０（１））、セグメント（ｓｇ０（５））が指定され、ＡＮＤ演算を実行する。これにより、セグメント（ｓｇ０（１））からはファイル番号３が指定され、セグメント（ｓｇ０（５））からはファイル番号１９が指定される。したがって、圧縮ファイル（ｆ３），（ｆ１９）に、文字情報「人」および「形」の両方が存在することがわかる。
2013038527.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
複数のファイルのそれぞれについて所定の文字情報を含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す第２の情報と、を記憶手段に記憶し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出方法。
【請求項２】
前記コンピュータに、さらに、
前記検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルが前記所定の文字情報を含まないと判定する、
ことを実行させることを特徴とする請求項１に記載の抽出方法。
【請求項３】
前記第１の情報は、前記複数のファイルのそれぞれについて前記所定の文字情報を含むか否かを示すビットによるビット列であり、
前記第２の情報は、前記ビット列に含まれる各ビットを演算して得られるビットである、
ことを特徴とする請求項１又は２に記載の抽出方法。
【請求項４】
前記コンピュータに、
前記記憶手段に、さらに、前記複数のファイルのそれぞれについて検索対象とするか否かを示す第３の情報を記憶し、
前記検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報及び前記第３の情報に基づいて、検索対象であり、且つ前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする請求項１〜３のいずれか１項に記載の抽出方法。
【請求項５】
前記コンピュータに、
前記記憶手段に、さらに、前記複数のファイルの少なくともいずれかが検索対象であるか否かを示す第４の情報を記憶し、
前記検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示し、且つ前記第４の情報が前記複数のファイルの少なくともいずれかが検索対象である旨を示すことを検出すると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする請求項１〜３のいずれか１項に記載の抽出方法。
【請求項６】
コンピュータに、
複数のファイルのそれぞれについて所定の文字情報を含むか否かを示す第１の情報と、前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す第２の情報と、を記憶手段に記憶し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記複数のファイルから前記所定の文字情報を含むファイルを抽出し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルのうちの前記一部のファイルに含まれないファイルから、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出方法。
【請求項７】
コンピュータに、
複数のファイルのそれぞれについて所定の文字情報を含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す第２の情報と、を記憶手段に記憶し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出プログラム。
【請求項８】
コンピュータに、
複数のファイルのそれぞれについて所定の文字情報を含むか否かを示す第１の情報と、前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す第２の情報と、を記憶手段に記憶し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記複数のファイルから前記所定の文字情報を含むファイルを抽出し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルのうちの前記一部のファイルに含まれないファイルから、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出プログラム。
【請求項９】
複数のファイルのそれぞれについて所定の文字情報を含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す第２の情報と、を記憶する記憶手段と、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する抽出手段と、
を備えることを特徴とする抽出装置。
【請求項１０】
複数のファイルのそれぞれについて所定の文字情報を含むか否かを示す第１の情報と、前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す第２の情報と、を記憶する記憶手段と、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記複数のファイルから前記所定の文字情報を含むファイルを抽出し、前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルのうちの前記一部のファイルに含まれないファイルから、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する抽出手段と、
を備えることを特徴とする抽出装置。
【請求項１１】
複数のコンピュータと、割当装置と、を含む抽出システムであって、
前記割当装置が、
複数のファイルを分割して得られる複数のファイル群のそれぞれについて、それぞれのファイル群に含まれる少なくとも１つのファイルが所定の文字情報を含むかを示す情報を保持する保持手段と、
前記所定の文字情報についての検索要求を受けた場合に、前記保持手段に保持された情報に前記所定の文字情報を含むファイルを少なくとも１つ旨を示されるファイル群の数に応じて、前記複数のファイル群を前記複数のコンピュータのそれぞれに割り当てる割当手段と、を含み、
前記複数のコンピュータのそれぞれが、
前記複数のファイル群のそれぞれについて、それぞれのファイル群に含まれるいずれのファイルが所定の文字情報を含むかを示すインデックス情報を記憶する記憶手段と、
前記記憶手段に記憶された前記複数のファイル群それぞれについてのインデックス情報のうち、前記割当装置に割り当てられたファイル群についての前記インデックス情報に基づいて前記所定の文字情報を含むファイルを抽出する抽出手段と、を含む、
ことを特徴とする抽出システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報を抽出する抽出方法、抽出プログラム、抽出装置、および抽出システムに関する。
【背景技術】
【０００２】
従来、所定の文字情報を含む検索文字列が入力された場合に、検索対象の複数のファイルのいずれが所定の文字情報を含むかを示すインデックス情報を参照して、検索対象のファイルのうちの所定の文字情報を含むファイルを絞り込む技術がある。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第２９８６８６５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、検索対象のファイル数が増大すると、それに合わせてインデックス情報のサイズも増大する。インデックス情報のサイズ増大により、インデックス情報を参照する処理に要する時間が増大するため、結果として検索処理の時間が増大するという問題があった。  【０００５】
本発明は、上述した従来技術による問題点を解消するため、ファイル数増大に応じた検索処理時間の増大を抑制することができる抽出方法、抽出プログラム、抽出装置、および抽出システムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するため、本発明の一側面によれば、複数のファイルのそれぞれについて所定の文字情報を含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す第２の情報と、を記憶手段に記憶し、前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する抽出方法、抽出プログラム、抽出装置、および抽出システムが提案される。
【発明の効果】
【０００７】
本発明の一側面によれば、ファイル数増大に応じた検索処理時間の増大を抑制することができるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】図１は、本実施の形態にかかる圧縮符号マップの分散化を示す説明図である。
【図２】図２は、セグメント群を記憶したサーバを示す説明図である。
【図３】図３は、対象ファイルが追加された場合の圧縮符号マップの追加例を示す説明図である。
【図４】図４は、出現マップの階層化を示す説明図である。
【図５】図５は、削除マップの階層化を示す説明図である。
【図６】図６は、階層化されたセグメント群の詳細を示す説明図である。
【図７】図７は、図６に示した階層構造セグメント群を実装したコンピュータシステムの構成例を示す説明図である。
【図８】図８は、階層構造セグメント群を用いた圧縮ファイルの絞込み例を示す説明図である。
【図９】図９は、実施の形態にかかるコンピュータのハードウェア構成例を示すブロック図である。
【図１０】図１０は、本実施の形態にかかるシステム構成例を示す説明図である。
【図１１】図１１は、本実施の形態にかかるコンピュータまたはコンピュータシステムの機能的構成例１を示すブロック図である。
【図１２】図１２は、図１１に示したコンピュータの集計部〜第２圧縮部までの処理の流れを示す説明図である。
【図１３】図１３は、集計部による集計および作成部による圧縮符号マップＭｓの作成例を示す説明図である。
【図１４】図１４は、（１）出現回数の集計の詳細を示す説明図である。
【図１５】図１５は、図１３の（２）圧縮符号長算出の詳細（Ｎ＝１１）を示す説明図である。
【図１６】図１６は、図１３の（３）葉数特定〜（５）葉の構造体生成の詳細（Ｎ＝１１）を示す説明図である。
【図１７】図１７は、文字情報ごとの補正結果を示す説明図である。
【図１８】図１８は、図１３の（６）葉へのポインタ生成の詳細（Ｎ＝１１）を示す説明図である。
【図１９】図１９は、図１３の（７）２N分枝無節点ハフマン木Ｈの構築の詳細（Ｎ＝１１）を示す説明図である。
【図２０】図２０は、葉の構造体を示す説明図である。
【図２１】図２１は、特定単一文字の構造体を示す説明図である。
【図２２】図２２は、分割文字コードの構造体を示す説明図である。
【図２３】図２３は、基礎単語の構造体を示す説明図である。
【図２４】図２４は、圧縮符号マップの生成例を示す説明図である。
【図２５】図２５は、作成部による圧縮符号マップ作成処理手順例を示すフローチャートである。
【図２６】図２６は、図２５に示した集計処理（ステップＳ２５０１）の詳細な処理手順例を示すフローチャートである。
【図２７】図２７は、図２６に示した対象ファイルの集計処理（ステップＳ２６０３）の詳細な処理手順例を示すフローチャートである。
【図２８】図２８は、文字出現頻度集計テーブルを示す説明図である。
【図２９】図２９は、図２７に示した基礎単語集計処理（ステップＳ２７０２）の詳細な処理手順例を示すフローチャートである。
【図３０】図３０は、基礎単語出現頻度集計テーブルを示す説明図である。
【図３１】図３１は、図２９に示した最長一致検索処理（ステップＳ２９０１）の詳細な処理手順を示すフローチャートである。
【図３２】図３２は、図２５に示したマップ割当数決定処理（ステップＳ２５０２）の詳細な処理手順例を示すフローチャートである。
【図３３】図３３は、図２５に示した再集計処理（ステップＳ２５０３）の詳細な処理手順例を示すフローチャートである。
【図３４】図３４は、対象ファイルの再集計処理（ステップＳ３３０３）の詳細な処理手順例を示すフローチャートである。
【図３５】図３５は、上位分割文字コード出現頻度集計テーブルを示す説明図である。
【図３６】図３６は、下位分割文字コード出現頻度集計テーブルを示す説明図である。
【図３７】図３７は、図３４で示した２グラム文字列特定処理（ステップＳ３４０６）の詳細な処理手順を示すフローチャートである。
【図３８】図３８は、２グラム文字列出現頻度集計テーブルを示す説明図である。
【図３９】図３９は、図２５に示したハフマン木生成処理（ステップＳ２５０４）の詳細な処理手順例を示すフローチャートである。
【図４０】図４０は、図３９に示した枝数特定処理（ステップＳ３９０４）の詳細な処理手順例を示すフローチャートである。
【図４１】図４１は、図３９に示した構築処理（ステップＳ３９０５）の詳細な処理手順を示すフローチャートである。
【図４２】図４２は、図４１に示した葉へのポインタ生成処理（ステップＳ４１０３）の詳細な処理手順を示すフローチャートである。
【図４３】図４３は、図２５に示したマップ作成処理（ステップＳ２５０５）の詳細な処理手順例を示すフローチャートである。
【図４４】図４４は、図４３に示した対象ファイルのマップ作成処理（ステップＳ４３０３）の詳細な処理手順を示すフローチャートである。
【図４５】図４５は、図４４で示した基礎単語出現マップ作成処理（ステップＳ４４０２）の詳細な処理手順例を示すフローチャートである。
【図４６】図４６は、図４４で示した特定単一文字出現マップ作成処理（ステップＳ４４０３）の詳細な処理手順例を示すフローチャートである。
【図４７】図４７は、図４６で示した分割文字コード出現マップ作成処理（ステップＳ４６０３）の詳細な処理手順例を示すフローチャートである。
【図４８】図４８は、図４４に示した２グラム文字列マップ作成処理（ステップＳ４４０４）の詳細な処理手順例を示すフローチャートである。
【図４９】図４９は、２グラム文字列出現マップ生成処理（ステップＳ４８０３）の詳細な処理手順例を示すフローチャートである。
【図５０】図５０は、２N分枝無節点ハフマン木Ｈを用いた圧縮処理の具体例を示す説明図である。
【図５１】図５１は、第１圧縮部による２N分枝無節点ハフマン木Ｈを用いた対象ファイル群の圧縮処理手順例を示すフローチャートである。
【図５２】図５２は、図５１に示した圧縮処理（ステップＳ５１０３）の詳細な処理手順を示すフローチャート（その１）である。
【図５３】図５３は、図５１に示した圧縮処理（ステップＳ５１０３）の詳細な処理手順を示すフローチャート（その２）である。
【図５４】図５４は、図５１に示した圧縮処理（ステップＳ５１０３）の詳細な処理手順を示すフローチャート（その３）である。
【図５５】図５５は、出現率と出現率領域との関係を示す説明図である。
【図５６】図５６は、出現率領域別の圧縮パターンを有する圧縮パターンテーブルを示す説明図である。
【図５７】図５７は、Ｂ領域およびＢ´領域の場合の圧縮パターンを示す説明図である。
【図５８】図５８は、Ｃ領域およびＣ´領域の場合の圧縮パターンを示す説明図である。
【図５９】図５９は、Ｄ領域およびＤ´領域の場合の圧縮パターンを示す説明図である。
【図６０】図６０は、Ｅ領域およびＥ´領域の場合の圧縮パターンを示す説明図である。
【図６１】図６１は、圧縮符号マップ圧縮処理手順を示すフローチャートである。
【図６２】図６２は、本実施の形態にかかるコンピュータまたはコンピュータシステムの機能的構成例２を示すブロック図である。
【図６３】図６３は、ファイル伸長例を示す説明図である。
【図６４】図６４は、図６３での伸長処理の具体例を示す説明図（その１）である。
【図６５】図６５は、図６３での伸長処理の具体例を示す説明図（その２）である。
【図６６】図６６は、ファイル追加処理の具体例を示す説明図である。
【図６７】図６７は、セグメント追加処理の詳細な処理手順を示すフローチャートである。
【図６８】図６８は、図６７に示した追加ファイルによるマップ更新処理（ステップＳ６７０９）の詳細な処理手順を示すフローチャート（前半）である。
【図６９】図６９は、図６７に示した追加ファイルによるマップ更新処理（ステップＳ６７０９）の詳細な処理手順を示すフローチャート（後半）である。
【図７０】図７０は、セグメント階層化処理の詳細な処理手順を示すフローチャートである。
【図７１】図７１は、図７０に示した選択出現マップ集約処理（ステップＳ７００４）の詳細な処理手順を示すフローチャートである。
【図７２】図７２は、図７０に示した削除マップ集約処理（ステップＳ７００５）の詳細な処理手順を示すフローチャートである。
【図７３】図７３は、本実施の形態にかかる検索処理手順を示すフローチャートである。
【図７４】図７４は、図７３に示したポインタ特定処理（ステップＳ７３０２）の詳細な処理手順を示すフローチャート（その１）である。
【図７５】図７５は、図７３に示したポインタ特定処理（ステップＳ７３０２）の詳細な処理手順を示すフローチャート（その２）である。
【図７６】図７６は、図７３に示したファイル絞込み処理（ステップＳ７３０３）の詳細な処理手順を示すフローチャートである。
【図７７】図７７は、図７３に示した２N分枝無節点ハフマン木Ｈを用いた伸長処理（ステップＳ７３０４）の詳細な処理手順例を示すフローチャート（その１）である。
【図７８】図７８は、図７３に示した２N分枝無節点ハフマン木Ｈを用いた伸長処理（ステップＳ７３０４）の詳細な処理手順例を示すフローチャート（その２）である。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、本発明の実施の形態を詳細に説明する。なお、本明細書において、「文字情報」とは、テキストデータを構成する、単一文字、基礎単語、分割文字コードなどである。対象ファイル群は、たとえば、文書ファイル、Ｗｅｂページ、電子メールなどの電子データであり、たとえば、テキスト形式、ＨＴＭＬ（ＨｙｐｅｒＴｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）形式、ＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）形式の電子データである。
【００１０】
また、「単一文字」とは、１つの文字コードで表現される文字である。単一文字の文字コード長は、文字コード種により異なる。
【００１１】
たとえば、ＵＴＦ（Ｕｎｉｃｏｄｅ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｆｏｒｍａｔ）１６の場合は１６ビットコード、ＡＳＣＩＩ（Ａｍｅｒｉｃａｎ  Ｓｔａｎｄａｒｄ  Ｃｏｄｅ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｉｎｔｅｒｃｈａｎｇｅ）コードの場合は８ビットコード、シフトＪＩＳ（Ｊａｐａｎｅｓｅ  Ｉｎｄｕｓｔｒｉａｌ  Ｓｔａｎｄａｒｄ）コードの場合は８ビットコードである。シフトＪＩＳコードで日本語の文字を表現する場合は、２個の８ビットコードを組み合わせることとなる。
【００１２】
また、「基礎単語」とは、小・中学校で学習する基本的な単語や、特定の文字列で表現される予約語をいう。「Ｔｈｉｓ  ｉｓ  ａ・・・．」の英文を例にすると「Ｔｈｉｓ」、「ｉｓ」、「ａ」などの単語であり、千語レベル、２千語レベル、数千語レベルに分類され、英和辞典には、「＊＊＊」、「＊＊」、「＊」マークが付与されている。また、予約語とは、あらかじめ決められた文字列であり、たとえば、ＨＴＭＬのタグ（たとえば、＜ｂｒ＞）が挙げられる。
【００１３】
また、「分割文字コード」とは、単一文字を、上位のコードと下位のコードに分割した各々のコードである。本実施の形態では、後述するように、単一文字を、上位のコードと下位のコードに分割する場合がある。たとえば、「芝」という単一文字の文字コードは、ＵＴＦ１６の場合、「９Ｄ８２」で表現されるが、上位分割文字コード「０ｘ９Ｄ」と下位分割文字コード「０ｘ８２」に分割される。
【００１４】
また、「グラム」とは、文字単位である。たとえば、単一文字については、その１文字分が１グラムとなる。分割文字コードについては、分割文字コード単独で１グラムとなる。したがって、単一文字「芝」は２グラムとなる。なお、本実施の形態では、文字コードとしてＵＴＦ１６を例に挙げて説明する。
【００１５】
また、本明細書では、「ビットをＯＮ」とした場合は、そのビットの値を“１”にし、「ビットをＯＦＦ」とした場合は、そのビットの値を“０”として説明する。なお、「ビットをＯＮ」とした場合は、そのビットの値を“０”にし、「ビットをＯＦＦ」とした場合は、そのビットの値を“１”にしてもよい。
【００１６】
「出現マップ」とは、全文検索のためのインデックスであり、文字情報を指定するポインタと文字情報の各対象ファイルでの存否を示すビット列を連結したビット列である。検索処理時には、このビット列を、ビットのＯＮ・ＯＦＦに応じて検索対象の文字情報を含むか否かを示すインデックスとして用いることができる。文字情報を指定するポインタとしては、たとえば、文字情報の圧縮符号が採用される。文字情報を指定するポインタは、たとえば、文字情報そのものを用いても良い。「圧縮符号マップ」とは、圧縮符号のポインタで示される文字情報ごとの出現マップをまとめたビットマップである。２グラム文字列の圧縮符号マップについては、第１グラムの圧縮符号と第２グラムの圧縮符号を組み合わせた圧縮符号列となる。
【００１７】
「２グラム文字列」とは、１グラムの文字コードが連接する文字列である。たとえば、「人形芝居」という文字列には、２連接文字「人形」、「形芝」、「芝居」が含まれている。２連接文字「人形」の「人」、「形」はそれぞれ分割されない単一文字であるため、２連接文字「人形」はそのまま２グラム文字列となる。
【００１８】
「芝」は上述したように分割されるため、単一文字「形」と「芝」の上位分割文字コード「０ｘ９Ｄ」の組み合わせが２グラム文字列となる。また、上位分割文字コード「０ｘ９Ｄ」と下位分割文字コード「０ｘ８２」の組み合わせも２グラム文字列となる。さらに、下位分割文字コード「０ｘ８２」と分割されない単一文字「居」の組み合わせも２グラム文字列となる。
【００１９】
基礎単語により、対象ファイル群が圧縮されている場合、圧縮符号マップの生成時や検索時に１パスでアクセスすることが可能である。なお、対象ファイル群を圧縮しない場合は、文字情報を指定するポインタとしては、文字情報の文字コードをそのまま採用してもよい。
【００２０】
また、「削除マップ」とは、対象ファイルの存在または削除をビット列で示したインデックスである。なお、削除マップにおいてＯＮ（＝１）に該当するビットに対応するファイル番号の対象ファイルは、存在していることを意味する。一方、ＯＦＦ（＝０）になると、当該対象ファイルは削除されたことを意味する。これにより、圧縮符号マップを用いて検索を行う場合に、対象ファイルそのものを削除しなくても、対象ファイルに対応する削除マップをＯＦＦにすることで、対象ファイルを検索対象から除くことができる。
【００２１】
図１は、本実施の形態にかかる圧縮符号マップの分散化を示す説明図である。圧縮符号マップは、所定のファイル数ｎ単位（たとえば、ｎ＝２５６）で分割されている。分割された各々を、セグメントと称す。
【００２２】
セグメントｓｇ０（１）は、圧縮ファイルｆ１〜ｆｎまでの圧縮符号マップを有するセグメントであり、セグメントｓｇ０（２）は、圧縮ファイルｆ（ｎ＋１）〜ｆ（２ｎ）までの圧縮符号マップを有するセグメントであり、セグメントｓｇ０（３）は、圧縮ファイルｆ（２ｎ＋１）〜ｆ（３ｎ）までの圧縮符号マップを有するセグメントである。
【００２３】
セグメントは初期状態では、セグメントｓｇ０（１）のみが存在し、ファイル追加によりファイル数がｎを超えると、セグメントｓｇ０（２）が生成され、ファイル数が２ｎを超えると、セグメントｓｇ０（３）が生成される。このように、ファイル数増加により、最後尾のセグメントｓｇ０（Ｋ）は、圧縮ファイルｆ（（Ｋ−１）ｎ＋１）〜ｆ（Ｋｎ）までの圧縮符号マップを有するセグメントとなる（ただし、Ｋは現在のセグメント数を示す。Ｋは１以上の整数である。）。
【００２４】
各セグメントは、管理領域Ａ１〜ＡＫ（管理領域群Ａｓ）を有する。管理領域Ａ１〜ＡＫには、先行セグメントへのポインタ、後続セグメントへのポインタ、自セグメント内の圧縮符号マップを構成する各出現マップへのポインタ、自セグメント内の削除マップへのポインタ、自セグメント内の各圧縮ファイルへのポインタが格納されている。
【００２５】
先頭のセグメントｓｇ０（１）については、先行セグメントがないため、先行セグメントへのポインタとして、たとえば、「００００００００ｈ」が格納される。アドレス「００００００００ｈ」は、先頭のセグメントｓｇ０（１）を指定する論理アドレスである。同様に、最後尾のセグメントｓｇ０（Ｋ）については、後続セグメントがないため、後続セグメントへのポインタとして、たとえば、「０ＦＦＦＦＦＦＦｈ」が格納される。還元すれば、後続セグメントへのポインタとして「０ＦＦＦＦＦＦＦｈ」が格納されているセグメントが最後尾のセグメントである。
【００２６】
Ｋ＝１の場合、すなわち、セグメントｓｇ０（１）しか存在しない場合、セグメントｓｇ０（１）の先行セグメントへのポインタは「００００００００ｈ」であり、後続セグメントへのポインタは「０ＦＦＦＦＦＦＦｈ」である。ファイル追加によりＫ＝２になると、セグメントｓｇ０（１）の後続セグメントへのポインタは、「０ＦＦＦＦＦＦＦｈ」から「セグメントｓｇ０（２）へのポインタ」に変更される。
【００２７】
また、セグメントｓｇ０（２）の先行セグメントへのポインタには、「セグメントｓｇ０（１）へのポインタ（セグメントｓｇ０（１）のアドレス「００００００００ｈ」）」が格納される。また、セグメントｓｇ０（２）の後続セグメントへのポインタには、「０ＦＦＦＦＦＦＦｈ」が格納される。このように、セグメントごとに先行セグメントおよび後続セグメントとの関連付けをしておくことで、セグメント単位での検索を連携しておこなうことができる。
【００２８】
各セグメントの圧縮符号マップＭ１〜ＭＫ（圧縮符号マップＭｓ）は、文字情報が同じである出現マップを有するが、担当するファイル番号が異なる。各セグメントの圧縮符号マップＭ１〜ＭＫにおいて担当するファイル番号は、自セグメントが保持する圧縮ファイルのファイル番号となる。たとえば、セグメントｓｇ０（Ｋ）の圧縮符号マップＭＫでは、各文字情報の出現マップについてファイル番号（Ｋ−１）ｎ〜Ｋｎの存否を示すビット列を有することとなる。
【００２９】
各セグメントの削除マップＤ１〜ＤＫ（削除マップＤｓ）についても圧縮符号マップ群Ｍｓと同様、担当するファイル番号が異なる。各削除マップＤ１〜ＤＫにおいて担当するファイル番号は、自セグメントが保持する圧縮ファイルのファイル番号となる。たとえば、セグメントｓｇ０（Ｋ）の削除マップＤＫでは、各文字情報の出現マップについてファイル番号（Ｋ−１）ｎ〜Ｋｎについての存在または削除を示すビット列を有することとなる。
【００３０】
図２は、セグメント群を記憶したサーバを示す説明図である。サーバ２００は、データベース２０１を有する。データベース２０１には、アーカイブファイル２０２が格納されている。アーカイブファイル２０２は、バッチ部２１１と、追加部２１２と、を有する。バッチ部２１１には、ｃ個のセグメントｓｇ０（１）〜ｓｇ０（ｃ）がデフォルトで格納されている。追加部２１２には、追加されたセグメントｓｇ０（ｃ＋１）〜ｓｇ０（Ｋ）が格納されている。なお、追加部２１２に空き領域がなくなった場合は、サーバ２００とネットワークを介して通信可能な他のサーバに格納させるものとする。
【００３１】
図３は、対象ファイルが追加された場合の圧縮符号マップの追加例を示す説明図である。（Ａ）では、セグメントｓｇ０（１），ｓｇ０（２）が登録済みであり、文字情報ＬＴ１〜ＬＴｚの圧縮符号Ｐ（ＬＴ１）〜Ｐ（ＬＴｚ）についての出現マップにおいて、ファイル番号１〜２ｎまでのインデックス情報が格納されている。
【００３２】
（Ｂ）は、（Ａ）の状態から出現マップ群を圧縮した状態を示している。圧縮手法については後述するが、圧縮するタイミングとしては、たとえば、１セグメントのファイル数ｎの倍数になった場合に圧縮するものとする。この場合、ファイル数がｎの倍数２ｎであるため、出現マップごとにインデックス情報であるビット列を圧縮する。また、文字情報ＬＴ１〜ＬＴｚの存否を確認する場合には、伸長されるものとする。伸長手法についても後述する。このように、通常は圧縮して保存しておき、必要なときにだけ伸長することで、省メモリ化を図ることができる。
【００３３】
（Ｃ）は、（Ｂ）の状態からあらたな圧縮ファイルｆ（２ｎ＋１）が追加された状態を示している。（Ｂ）での最後尾のセグメントであるセグメントｓｇ０（２）では圧縮ファイルｆ（２ｎ＋１）を格納できないため、あらたにセグメントｓｇ０（３）が設定され、圧縮ファイルｆ（２ｎ＋１）が保存されることになる。また、セグメントｓｇ０（３）の圧縮符号マップには、圧縮符号ごとに圧縮ファイルｆ（２ｎ＋１）についてのビットが設定される。（Ｃ）の例では、文字情報ＬＴ１，ＬＴ２については「１」、ＬＴｚについては「０」が設定されている。
【００３４】
（Ｄ）は、（Ｃ）の状態からセグメントｓｇ０（３）においてｎ個の圧縮ファイルｆ（２ｎ＋１）〜ｆ（３ｎ）が追加された状態を示している。
【００３５】
（Ｅ）は、（Ｄ）の状態においてセグメントｓｇ０（３）でｎ個の圧縮ファイルｆ（２ｎ＋１）〜ｆ（３ｎ）が追加されたため、圧縮符号ごとにセグメントｓｇ０（１）〜ｓｇ０（３）のインデックス情報を圧縮した状態を示している。このように、セグメント単位で圧縮ファイルがｎ個たまると、出現マップの圧縮がおこなわれる。
【００３６】
図４は、出現マップの階層化を示す説明図である。セグメント数が増加すると、圧縮符号ごとにインデックス情報となるビット列が冗長化する。冗長化した場合、圧縮符号ごと、すなわち、文字情報ごとに、全ファイル数について存否を示すビットのＯＮ／ＯＦＦを確認する必要があるが、存在しない箇所について確認作業をするのは無駄であり、検索時間の増大の原因となる。そこで、圧縮符号ごと、すなわち、文字情報ごとに、セグメントがｍ＋１個生成されたら、ｍ個単位でインデックス情報を集約することにする。
【００３７】
図４では、例として文字情報ＬＴｘの圧縮符号Ｐ（ＬＴｘ）のインデックス情報を上位階層に集約する場合を例に挙げて説明する。なお、「ｓｇＸ（Ｙ）」のＸは、階層番号を示しており、Ｙはセグメント番号を示している。したがって、ｓｇＸ（Ｙ）の場合は、第Ｘ階層のＹ番目のセグメントとなる。また、これまで説明してきたセグメントｓｇ０（１）〜ｓｇ０（Ｋ）は、第０階層のセグメントとなる。
【００３８】
まず、基本階層である第０階層から上位階層である第１階層への集約例について説明する。集約のルールとしては、対象階層のセグメントのインデックス情報であるビット列がオール０、すなわち、文字情報ＬＴｘがそのセグメント内の対象ファイル群に存在しない場合、上位階層のインデックスとして「０」に集約する。一方、対象階層のセグメントのインデックス情報であるビット列１個でも「１」がある場合、すなわち、文字情報ＬＴｘがそのセグメント内の対象ファイル群の少なくともいずれか１つに存在する場合、上位階層のインデックスとして「１」に集約する。
【００３９】
たとえば、セグメントｓｇ０（１）については、「１」が存在するため、上位階層のセグメントｓｇ１（１）には、「１」が設定される。同様に、セグメントｓｇ０（ｍ）については、オール０であるため、上位階層のセグメントｓｇ１（１）には、「０」が設定される。この上位階層のセグメントｓｇ１（１）のビット位置は、下位のセグメントｓｇ０（１）〜ｓｇ０（ｍ）の位置を示している。このように、上位階層のセグメントのビットの値により下位のセグメントのインデックス情報の状態を特定することができる。
【００４０】
また、このような集約は第０階層と第１階層との間だけではなく、最上位階層のセグメント数がｍ個になると、あらたに上位階層のセグメントが生成されることとなる。たとえば、第１階層でセグメントがセグメントｓｇ１（ｍ）まで出来上がると、上述したように第２階層のセグメントｓｇ２（１）が生成されることとなる。なお、図４では、第２階層までの例を示したが、追加される圧縮ファイル数が増加するにしたがって、第３階層以上の階層に集約されることになる。
【００４１】
図５は、削除マップの階層化を示す説明図である。削除マップについても、図４と同様セグメント単位で上位階層に集約されることになる。
【００４２】
図６は、階層化されたセグメント群の詳細を示す説明図である。図６の階層構造セグメント群では、第０階層に図１に示したようなｍ2個のセグメントｓｇ０（１）〜ｓｇ０（ｍ2）が生成されている。また、上位階層についても同様なデータ構造のセグメントｓｇ１（１）〜ｓｇ１（ｍ）が生成されている。たとえば、第１階層のセグメントｓｇ１（１）〜ｓｇ１（ｍ）では、第０階層で集約された出現マップ（集約出現マップ）が圧縮符号ごとに格納されている。同様に、第０階層で集約された削除マップ（集約削除マップ）が圧縮符号ごとに格納されている。
【００４３】
また、第０階層と同様、それぞれの管理領域に、先行セグメントへのポインタや後続セグメントへのポインタが設定されている。また、自セグメント内の集約出現マップへのポインタや集約削除マップへのポインタも格納される。また、管理領域には、下位階層のセグメント（下位セグメント）へのポインタがそれぞれ格納されている。たとえば、セグメントｓｇ１（１）では、下位階層のセグメントｓｇ０（１）へのポインタ〜セグメントｓｇ０（ｍ）へのポインタが格納されており、セグメントｓｇ０（１）〜セグメントｓｇ０（ｍ）を指定することができる。なお、第１階層以上のセグメントには、圧縮ファイルは格納されない。
【００４４】
図７は、図６に示した階層構造セグメント群ＳＧを実装したコンピュータシステムの構成例を示す説明図である。図７の階層構造セグメント群ＳＧでは、ｍ個のセグメントを１アーカイブファイルとする。なお、「ＡＸ（Ｙ）」はアーカイブファイルの符号であり、Ｘは、階層番号を示しており、Ｙはアーカイブ番号を示している。したがって、ＡＸ（Ｙ）の場合は、第Ｘ階層のＹ番目のアーカイブファイルとなる。たとえば、アーカイブファイルＡ０（１）は、第０階層のセグメントｓｇ０（１）〜ｓｇ０（ｍ）の集合である。
【００４５】
図７の例では、マスタサーバＭＳは、第１階層以上のアーカイブファイルを格納している。また、スレーブサーバＳ１，Ｓ２，…，Ｓ（２ｍ＋１），…は、マスタサーバＭＳにより割り当てられた１個のアーカイブファイルを格納している。図７のアーカイブファイルの割り当ては１例であり、マスタサーバＭＳが第１階層以上のアーカイブファイルをすべて担当する必要はなく、他のサーバに分散させてもよい。また、スレーブサーバＳ１，Ｓ２，…，Ｓ（２ｍ＋１），…についても１アーカイブファイルだけではなく、複数のアーカイブファイルを担当することとしてもよい。
【００４６】
図８は、階層構造セグメント群ＳＧを用いた圧縮ファイルの絞込み例を示す説明図である。図８では、説明を単純化するため、第０階層のセグメントのファイル数ｎをｎ＝４とし、ｍ＝４とする。したがって、第０階層セグメントｓｇ０（１）〜ｓｇ０（１６）まで存在することになるが、図示されていないセグメントについては説明を省略する。また、図８では、最上位階層を第２階層として説明する。また、図８において、実線矢印はＡＮＤ結果にしたがって下位階層のセグメントを指定していることを示しており、点線矢印は実際には指定されないが、指定されたセグメントと対比するために図示している。また、図８では、検索文字列として「人形」が入力された場合を示す。
【００４７】
（Ａ）において、最上位階層である第２階層のセグメントｓｇ２（１）について、文字情報「人」の圧縮符号Ｐ（人）の集約出現マップと、文字情報「形」の圧縮符号Ｐ（形）の集約出現マップと、集約削除マップと、のＡＮＤ演算をおこなう。ＡＮＤ結果は「１１００」となり、下位階層である第１階層のセグメントｓｇ１（１），ｓｇ１（２）に、文字情報「人」および「形」が存在する可能性があることがわかる。
【００４８】
また、下位セグメント番号３，４についてはＡＮＤ結果が「０」である。したがって、セグメントｓｇ１（３），ｓｇ１（４）の各ＡＮＤ演算をおこなうまでもなく、セグメントｓｇ１（３），ｓｇ１（４）の各ＡＮＤ結果がオール０になることがわかる。
【００４９】
（Ｂ）では、第２階層のＡＮＤ結果から第１階層のセグメントｓｇ１（１），ｓｇ１（２）が指定されたため、セグメントｓｇ１（１），ｓｇ１（２）について、（Ａ）と同様ＡＮＤ演算を実行する。これにより、セグメントｓｇ１（１）からはセグメントｓｇ０（１）が指定され、セグメントｓｇ１（２）からはセグメントｓｇ０（５）が指定されることになる。セグメントｓｇ１（２）に着目すると、下位セグメント番号６〜８についてはＡＮＤ結果が「０」である。したがって、セグメントｓｇ０（６）〜ｓｇ０（８）の各ＡＮＤ演算をおこなうまでもなく、セグメントｓｇ０（６）〜ｓｇ０（８）の各ＡＮＤ結果がオール０になることがわかる。
【００５０】
（Ｃ）では、第１階層のＡＮＤ結果から第０階層のセグメントｓｇ０（１），ｓｇ０（５）が指定されたため、ｓｇ０（１），ｓｇ０（５）について、（Ａ），（Ｂ）と同様ＡＮＤ演算を実行する。これにより、セグメントｓｇ０（１）からはファイル番号３が指定され、セグメントｓｇ０（５）からはファイル番号１９が指定されることになる。したがって、圧縮ファイルｆ３，ｆ１９に、文字情報「人」および「形」の両方が存在することがわかる。
【００５１】
＜コンピュータのハードウェア構成例＞
図９は、実施の形態にかかるコンピュータのハードウェア構成例を示すブロック図である。図９において、コンピュータは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）９０１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９０３と、磁気ディスクドライブ９０４と、磁気ディスク９０５と、光ディスクドライブ９０６と、光ディスク９０７と、ディスプレイ９０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）９０９と、キーボード９１０と、マウス９１１と、スキャナ９１２と、プリンタ９１３と、を備えている。また、各構成部はバス９００によってそれぞれ接続されている。
【００５２】
ここで、ＣＰＵ９０１は、コンピュータの全体の制御を司る。ＲＯＭ９０２は、ブートプログラムなどのプログラムを記憶している。また、ＲＯＭ９０２は、圧縮符号マップＭｓを生成・管理するプログラム、圧縮符号マップＭｓを用いて検索を行うプログラムを記憶している。ＲＡＭ９０３は、ＣＰＵ９０１のワークエリアとして使用され、ＣＰＵ９０１は、ＲＯＭ９０２に記憶されたプログラムをＲＡＭ９０３に読み出して実行することができる。磁気ディスクドライブ９０４は、ＣＰＵ９０１の制御にしたがって磁気ディスク９０５に対するデータのリード／ライトを制御する。磁気ディスク９０５は、磁気ディスクドライブ９０４の制御で書き込まれたデータを記憶する。
【００５３】
光ディスクドライブ９０６は、ＣＰＵ９０１の制御にしたがって光ディスク９０７に対するデータのリード／ライトを制御する。光ディスク９０７は、光ディスクドライブ９０６の制御で書き込まれたデータを記憶したり、光ディスク９０７に記憶されたデータを情報処理装置に読み取らせたりする。
【００５４】
ディスプレイ９０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ９０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００５５】
インターフェース（以下、「Ｉ／Ｆ」と略する。）９０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク９１４に接続され、このネットワーク９１４を介して他の装置に接続される。そして、Ｉ／Ｆ９０９は、ネットワーク９１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ９０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００５６】
キーボード９１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス９１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００５７】
スキャナ９１２は、画像を光学的に読み取り、コンピュータ内に画像データを取り込む。なお、スキャナ９１２は、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ９１３は、画像データや文書データを印刷する。プリンタ９１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００５８】
また、コンピュータは、上述した各種サーバや据置き型のパーソナル・コンピュータのほか、携帯電話機、スマートフォン、電子書籍端末、ノート型パソコンなどの携帯型端末であってもよい。また、本実施の形態は、複数のコンピュータに応じて実施されてもよい。
【００５９】
図１０は、本実施の形態にかかるシステム構成例を示す説明図である。図１０において、システムは、図９に示す各ハードウェアを含みうるコンピュータ１００１〜１００３、ネットワーク１００４、スイッチ１００５、無線基地局１００７を含む。情報処理装置１００３に含まれるＩ／Ｆは、無線通信機能を備える。
【００６０】
たとえば、複数のファイルを含むコンテンツについての圧縮符号マップを生成する処理をコンピュータ１００１で実行し、コンピュータ１００２，１００３に配信し、コンピュータ１００２，１００３のそれぞれで配信されたコンテンツについての検索処理を実行してもよい。
【００６１】
また、複数のファイルを含むコンテンツについての圧縮符号マップを生成する処理をコンピュータ１００１で実行し、コンピュータ１００２またはコンピュータ１００３からコンテンツについての検索依頼をコンピュータ１００１が受け付けて、検索処理を実行し、実行した検索処理の結果をコンピュータ１００２、コンピュータ１００３のそれぞれに返すように構成してもよい。図２と同様に、コンピュータ１００１〜１００３のそれぞれは、上述した各種サーバや据置き型のパーソナル・コンピュータのほか、携帯電話機、スマートフォン、電子書籍端末、ノート型パソコンなどの携帯型端末であってもよい。
【００６２】
＜機能的構成例１＞
図１１は、本実施の形態にかかるコンピュータまたはコンピュータシステムの機能的構成例１を示すブロック図であり、図１２は、図１１に示したコンピュータまたはコンピュータシステムの集計部〜第２圧縮部までの処理の流れを示す説明図である。図１１において、コンピュータまたはコンピュータシステム（以下、「コンピュータ１１００」）は、集計部１１０１と、第１生成部１１０２と、第１圧縮部１１０３と、作成部１１０４と、第２生成部１１０５と、第２圧縮部１１０６と、を備える。
【００６３】
集計部１１０１〜第２圧縮部１１０６は、具体的には、たとえば、図９に示したＲＯＭ９０２、ＲＡＭ９０３、磁気ディスク９０５などの記憶装置に記憶されたプログラムをＣＰＵ９０１に実行させることによりその機能を抽出装置として実現する。なお、集計部１１０１〜第２圧縮部１１０６は、それぞれ実行結果を記憶装置に書き込んだり、他の部の実行結果を読み出したりして、それぞれ演算を実行する。以下、集計部１１０１〜第２圧縮部１１０６について簡単に説明する。
【００６４】
集計部１１０１は、対象ファイル群内の文字情報の出現回数を集計する。具体的には、たとえば、集計部１１０１は、図１２の（Ａ）に示したように、対象ファイル群Ｆｓ内の文字情報の出現回数を集計する。集計部１１０１では、特定単一文字、上位分割文字コード、下位分割文字コード、２グラム文字、基礎単語別に出現回数を計数する。集計部１１０１の詳細な処理内容については後述する。
【００６５】
第１生成部１１０２は、集計部１１０１の集計結果に基づいて２N分枝無節点ハフマン木Ｈを生成する（図１２（Ｂ））。２N分枝無節点ハフマン木Ｈとは、根から分岐する枝が２N本あり、１または複数本の枝で葉を直接ポイントするハフマン木である。節点（内部節点）はない。節点がなく直接葉にヒットするため、節点を有する通常のハフマン木に比べて、伸長速度の高速化を図ることができる。葉は、該当する文字情報とその圧縮符号を含む構造体である。葉の構造体とも呼ぶ。葉に割り当てられる枝数は、割当先の葉に存在する圧縮符号の圧縮符号長に依存する。第１生成部１１０２の詳細な処理内容については後述する。
【００６６】
第１圧縮部１１０３は、２N分枝無節点ハフマン木Ｈを用いて対象ファイル群Ｆｓの各対象ファイルを圧縮して圧縮ファイル群ｆｓにする（図１２（Ｃ））。第１圧縮部１１０３の詳細な処理内容については後述する。
【００６７】
作成部１１０４は、集計部１１０１の集計結果と２N分枝無節点ハフマン木Ｈにおいて文字情報ごとに割り当てられた圧縮符号に基づいて、圧縮符号マップＭｓを作成する。作成部１１０４は、圧縮符号マップＭｓについても、特定単一文字、上位分割文字コード、下位分割文字コード、２グラム文字、基礎単語別に作成する。作成部１１０４は、圧縮符号マップＭｓにおいて該当する文字情報が１個の対象ファイルに１回でも出現したらそのファイル番号のビットをＯＮにする（図１２（Ｄ））。また、初期状態では、削除マップＤｓは各対象ファイルですべてＯＮにする。作成部１１０４の詳細な処理内容については後述する。
【００６８】
第２生成部１１０５は、文字情報の出現確率に基づいて出現マップを圧縮する無節点ハフマン木ｈを生成する（図１２（Ｅ））。第２生成部１１０５の詳細な処理内容については後述する。また、図７に示したコンピュータシステムの場合、マスタサーバＭＳの第２生成部１１０５で生成された無節点ハフマン木は、スレーブサーバＳ１，Ｓ２，…に送信される。
【００６９】
第２圧縮部１１０６は、第２生成部１１０５で生成された無節点ハフマン木を用いて各出現マップを圧縮する（図１２（Ｆ））。第２圧縮部１１０６の詳細な処理内容については後述する。また、図７に示したコンピュータシステムの場合、スレーブサーバＳ１，Ｓ２，…は、マスタサーバＭＳの第２生成部１１０５で生成され送信されてきたハフマン木を用いて、第２圧縮部１１０６により、スレーブサーバＳ１，Ｓ２，…内の出現マップを圧縮することとなる。
【００７０】
＜集計および圧縮符号マップＭｓの作成の詳細＞
つぎに、集計部１１０１による集計および作成部１１０４による圧縮符号マップＭｓの作成の詳細について説明する。圧縮符号マップＭｓを作成する場合、作成に先立って、集計部１１０１により、対象ファイル群Ｆｓから文字情報の出現回数を集計し、第１生成部１１０２により、２N分枝無節点ハフマン木Ｈを生成しておく必要がある。
【００７１】
図１３は、集計部１１０１による集計および作成部１１０４による圧縮符号マップＭｓの作成例を示す説明図である。
【００７２】
（１）出現回数の集計
まず、コンピュータ１１００は、対象ファイル群Ｆｓに存在する文字情報の出現回数を計数する。集計結果は、出現回数の降順にソートされ、出現回数の大きい方から昇順の順位がつけられる。なお、ここでは、文字情報の総種類数は、例として１３０５個（＜２０４８（＝２11））とする。（１）出現回数の集計の詳細は図７で説明する。
【００７３】
（２）圧縮符号長算出
つぎに、（１）で得られた集計結果を基にして、コンピュータ１１００は、文字情報ごとの圧縮符号長を算出する。具体的には、コンピュータ１１００は、文字情報ごとに、出現率を算出する。出現率は、文字情報の出現回数を全文字情報の総出現回数で割ることで得られる。そして、コンピュータ１１００は、出現率に対応する生起確率を求め、生起確率から圧縮符号長を導き出す。
【００７４】
生起確率は、１／２xで表現される。ｘはべき数である。圧縮符号長は、生起確率のべき数ｘとなる。具体的には、出現率が生起確率の以下のどの範囲であるかで圧縮符号長が決定される。ＡＲは出現率である。
１／２0＞ＡＲ≧１／２1・・・圧縮符号長は１ビット。
１／２1＞ＡＲ≧１／２2・・・圧縮符号長は２ビット。
１／２2＞ＡＲ≧１／２3・・・圧縮符号長は３ビット。
１／２3＞ＡＲ≧１／２4・・・圧縮符号長は４ビット。
・
・
・
１／２N-1＞ＡＲ≧１／２N・・・圧縮符号長はＮビット。
【００７５】
（２）圧縮符号長算出の詳細は図１５で説明する。
【００７６】
（３）葉数特定
つぎに、コンピュータ１１００は、圧縮符号長ごとに葉数を集計することで圧縮符号長ごとの葉数を特定する。ここでは、最大圧縮符号長は１７ビットとする。また、葉数とは、文字情報の種類数である。したがって、圧縮符号長５ビットの葉数が２である場合、５ビットの圧縮符号が割り当てられる文字情報が２つ存在することを示している。
【００７７】
（４）葉数補正
つぎに、コンピュータ１１００は、葉数を補正する。具体的には、コンピュータ１１００は、枝数の上限２Nのべき数Ｎが最大圧縮符号長となるように補正する。たとえば、べき数Ｎ＝１１の場合、圧縮符号長１１ビット〜１７ビットまでの葉数の総和を、補正後の圧縮符号長１１ビットの葉数にする。そして、コンピュータ１１００は、圧縮符号長ごとに葉当たりの枝数を割り当てる。具体的には、補正後の圧縮符号長に対し、その降順に、２0、２1、２2、２3、２4、２5、２6として葉当たりの枝数を決定する。
【００７８】
たとえば、図１３では、圧縮符号長１１ビットの圧縮符号が割り当てられる文字情報の総数（葉数）は１２１５個であるが、その葉当たりの枝数は１である。圧縮符号長１１ビットの圧縮符号が割り当てられる文字情報については、それぞれ１本の枝しか割り当てられないこととなる。一方、圧縮符号長６ビットの圧縮符号が割り当てられる文字情報の総数（葉数）は６個であるが、その葉当たりの枝数は３２である。圧縮符号長６ビットの圧縮符号が割り当てられる文字情報については、それぞれ３２本の枝が割り当てられることとなる。（４）葉数補正は、必要な場合に実行すればよく、実行しなくてもよい。
【００７９】
（５）葉の構造体生成
つぎに、コンピュータ１１００は、葉の構造体を生成する。葉の構造体とは、文字情報とその圧縮符号長とその圧縮符号長での圧縮符号が対応付けられたデータ構造体である。たとえば、出現順位が１位である文字「０」の圧縮符号長は６ビットであり、圧縮符号は「００００００」となる。図１３の例では、文字情報の種類数（葉数）は１３０５個であるため、葉Ｌ１の構造体〜葉Ｌ１３０５の構造体が生成されることとなる。（３）葉数特定〜（５）葉の構造体生成の詳細（Ｎ＝１１）は、図１６で説明する。
【００８０】
（６）葉へのポインタ生成
つぎに、コンピュータ１１００は、葉の構造体ごとに葉へのポインタを生成する。葉へのポインタは、そのポイント先となる葉の構造体内の圧縮符号に、その葉当たりの枝数分の番号に相当するビット列を連結したビット列である。たとえば、葉Ｌ１である文字「０」に割り当てられた圧縮符号「００００００」の圧縮符号長は６ビットであるため、葉Ｌ１当たりの枝数は３２本である。
【００８１】
したがって、葉Ｌ１へのポインタの先頭６ビットは、圧縮符号「００００００」となる。後続ビット列は、葉Ｌ１当たりの枝数で表現される３２（＝２5）種のビット列となる。すなわち、３２種の５ビットのビット列が圧縮符号「００００００」の後続ビット列となる。したがって、葉Ｌ１へのポインタは、先頭６ビットが「００００００」で固定された３２種の１１ビットのビット列となる。なお、葉当たりの枝数が１本の場合は、葉へのポインタは１個であり、圧縮符号とその葉へのポインタは同一ビット列となる。（６）葉へのポインタ生成の詳細は、図１８で説明する。
【００８２】
（７）２N分枝無節点ハフマン木Ｈの構築
最後に、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈを構築する。具体的には、葉のポインタを根とすることで、葉の構造体を直接指定する２N分枝無節点ハフマン木Ｈが構築される。圧縮符号列が、先頭６ビットが「００００００」の１１ビットのビット列である場合、後続の５ビットが３２種のいずれのビット列であっても、２N分枝無節点ハフマン木Ｈにより文字「０」の葉Ｌ１の構造体をポイントすることができる。（７）２N分枝無節点ハフマン木Ｈの構築の詳細は、図１９で説明する。
【００８３】
図１４は、（１）出現回数の集計の詳細を示す説明図である。図１４において、コンピュータ１１００は、（Ａ）対象ファイル群Ｆｓからの集計、（Ｂ）出現頻度の降順でのソート、（Ｃ）目標出現率の順位までの抽出という３つのフェーズを実行する。以下、基礎単語と単一文字に分けて説明する。
【００８４】
（Ａ１）まず、コンピュータ１１００は、対象ファイル群Ｆｓを読み込んで、基礎単語の出現頻度（出現回数）を計数する。コンピュータ１１００は、基礎単語の構造体を参照して、基礎単語の構造体内の基礎単語に一致する文字列が対象ファイルに存在する場合に、当該基礎単語の出現頻度（初期値は０）を１加算する。基礎単語の構造体とは、基礎単語が記述されたデータ構造体である。
【００８５】
（Ｂ１）対象ファイル群Ｆｓにおいて基礎単語の集計が終了すると、コンピュータ１１００は、基礎単語出現頻度集計テーブルを、出現頻度の降順にソートする。すなわち、出現頻度の高い順に並べ替え、出現頻度が最も高い基礎単語から順位付けをおこなう。
【００８６】
（Ａ２）、また、コンピュータ１１００は、対象ファイル群Ｆｓを読み込んで、単一文字の出現頻度を計数する。具体的には、コンピュータ１１００は、単一文字の出現頻度（初期値は０）を１加算する。
【００８７】
（Ｂ２）対象ファイル群Ｆｓにおいて単一文字の集計が終了すると、コンピュータ１１００は、単一文字出現頻度集計テーブルを、出現頻度の降順にソートする。すなわち、出現頻度の高い順に並べ替え、出現頻度が最も高い単一文字から順位付けをおこなう。
【００８８】
（Ｃ１）つぎに、コンピュータ１１００は、（Ｂ１）ソート後の基礎単語出現頻度集計テーブルを参照して、目標出現率Ｐｗまでの順位の基礎単語を抽出する。具体的には、コンピュータ１１００は、全基礎単語の出現頻度の総和（総出現頻度）を分母とし、順位が１位の基礎単語から降順に出現頻度を累計して分子とし、各順位までの目標出現率Ｐｗを算出する。
【００８９】
たとえば、総出現頻度が４００００、１位からｙ位までの基礎単語群の累計出現頻度が３００００とすると、ｙ位までの出現頻度は、（４００００／３００００）×１００＝７５［％］となる。ここで、目標出現率Ｐｗが７５［％］である場合は、上位ｙ位までの基礎単語を抽出することとなる。
【００９０】
（Ｃ２１）つぎに、コンピュータ１１００は、（Ｂ２）ソート後の単一文字出現頻度集計テーブルを参照して、目標出現率Ｐｃまでの順位の単一文字を抽出する。具体的には、コンピュータ１１００は、全単一文字の出現頻度の総和（総出現頻度）を分母とし、順位が１位の単一文字から降順に出現頻度を累計して分子とし、各順位までの出現率を算出する。
【００９１】
たとえば、総出現頻度が５００００、１位からｙ位までの単一文字群の累計出現頻度が４００００とすると、ｙ位までの出現頻度は、（５００００／４００００）×１００＝８０［％］となる。ここで、目標出現率Ｐｃが８０［％］である場合は、上位ｙ位までの単一文字を抽出することとなる。なお、（Ｃ２１）で抽出された単一文字を、元の単一文字群と区別するために、「特定単一文字（群）」と称す。
【００９２】
（Ｃ２２）また、単一文字群のうち特定単一文字群から外された単一文字（以下、「非特定単一文字（群）」）は、出現頻度が各特定単一文字よりも低いため、その文字コードを分割する。具体的には、非特定単一文字の文字コードを、上位ビットの文字コードと、下位ビットの文字コードに分割する。
【００９３】
たとえば、単一文字がＵＴＦ１６ビット文字コードで表現されている場合は、上位８ビットの文字コードと下位８ビットの文字コードに分割する。この場合、分割されたいずれの文字コードも、０ｘ００〜０ｘＦＦのコードで表現される。このように、上位ビットの文字コードが上位分割文字コードであり、下位ビットの文字コードが下位分割文字コードである。
【００９４】
図１５は、図１３の（２）圧縮符号長算出の詳細（Ｎ＝１１）を示す説明図である。図１５の文字情報テーブルは、図１３の（１）での集計結果を反映したテーブルであり、文字情報ごとに順位項目、伸長種別項目、コード項目、文字項目、出現回数項目、総回数項目、出現率項目、補正前での生起確率項目および圧縮符号長項目が設定されている。このうち、順位項目〜総回数項目までが再ソート結果で得られた情報である。
【００９５】
ここで、順位項目には、文字情報の出現回数の降順に順位（昇順）が書き込まれている。文字情報項目のうち伸長種別項目には、文字情報の種別が書き込まれる。「１６」は１６ビットコード（の単一文字）を示している。「８」は８ビットの分割文字コードを示している。「基」は基礎単語を示している。
【００９６】
文字情報項目のうちコード項目には、特定単一文字または分割文字コードが書き込まれている。基礎単語の場合は空欄とする。文字情報項目のうち文字項目には、文字や基礎単語が書き込まれている。分割文字コードの場合は空欄とする。出現回数項目には、対象ファイル群Ｆｓでの文字情報の出現回数が書き込まれている。総回数項目には、全文字情報の総出現回数が書き込まれている。
【００９７】
出現率項目には、出現回数を総回数で割り算した値が出現率として書き込まれている。補正前項目の生起確率項目には、出現率に対応する生起確率が書き込まれている。圧縮符号長項目には、生起確率に応じた圧縮符号長、すなわち、生起確率１／２yのべき数ｙが圧縮符号長として書き込まれている。
【００９８】
図１６は、図１３の（３）葉数特定〜（５）葉の構造体生成の詳細（Ｎ＝１１）を示す説明図である。図１５の文字情報テーブルを圧縮符号長単位で葉数（文字情報の総種類数）を集計した結果が、図１５における補正前の葉数となる。ここで、補正Ａとは、圧縮符号長の上限長Ｎ（すなわち、２N分枝無節点ハフマン木Ｈの最大枝数２Nのべき数Ｎ）以上の圧縮符号長に割り当てられた葉数を、圧縮符号長の上限長Ｎに集約する補正である。この場合、補正前での最大圧縮符号長は１７ビットであるが、文字情報の総種類数が１３０５種であるため、圧縮符号長の上限長Ｎは、Ｎ＝１１となる。したがって、補正Ａでは、圧縮符号長１１ビットの葉数が、圧縮符号長が１１ビット〜１７ビットの葉数の総和（１１９０個）となる。
【００９９】
そして、コンピュータ１１００は、生起確率総和を求める。圧縮符号長ごとの生起確率は決められているため（５ビットなら１／２5）、圧縮符号長ごとに生起確率を葉数で乗じることで、圧縮符号長ごとの乗算結果が得られる。たとえば、補正Ａにおける圧縮符号長５ビットの葉数は２である。圧縮符号長５ビットの生起確率は、１／２5である。したがって、補正Ａにおける圧縮符号長５ビットの生起確率は、２×（１／２5）＝１／２4となる。圧縮符号長６ビット以降も同様に補正Ａにおける圧縮符号長生起確率を求める。そして、補正Ａ後における各圧縮符号長の生起確率を合計することで、補正Ａでの生起確率総和が得られる。
【０１００】
そして、コンピュータ１１００は、生起確率総和が１以下であるか否かを判断する。しきい値ｔは０＜ｔ≦１である。しきい値ｔを設けたくない場合は、ｔ＝１とすればよい。しきい値ｔ未満であれば、補正Ｂに移行する。しきい値ｔ以上１以下である場合は、補正Ｂに移行せず、この時点での圧縮符号長ごとの葉数で確定する。
【０１０１】
補正Ｂは、補正Ａでの圧縮符号長群（５ビット〜１２ビット）は変えずに、葉数を更新する補正である。具体的には、補正Ａでの生起確率総和が、しきい値ｔ以上１以下でない場合におこなわれる補正である。より具体的には、補正Ｂは２種類ある。
【０１０２】
１つ目は、生起確率総和がしきい値ｔ未満である場合、生起確率総和が１以下の最大値が得られるまで、たとえば、最大漸近値に収束するまで、生起確率総和を増加させる補正（以下、補正Ｂ+）である。もう１つは、生起確率総和が１より大きい場合、生起確率総和が１以下に割り込んでから１以下の最大値が得られるまで、たとえば、最大漸近値に収束するまで、生起確率総和を減少させる補正（以下、補正Ｂ-）である。
【０１０３】
図１６に示した例では、補正Ａでの生起確率総和が「１．１４６」であるため、補正Ｂ-をおこなうこととなる。なお、補正Ｂ+および補正Ｂ-のいずれの補正Ｂであっても、葉数を生起確率総和で割るという同じ補正をおこなう。
【０１０４】
まず、補正Ｂ-の１回目（補正Ｂ-１）では、圧縮符号長ごとの補正Ａでの葉数を、前回の補正（この場合は補正Ａ）の生起確率の総和（１．１４６）で割ることで、葉数を更新する。なお、小数点以下は切り捨てでも、四捨五入でもよい。なお、補正Ａでの圧縮符号長の上限長Ｎ（Ｎ＝１１ビット）については、前回の補正（この場合は補正Ａ）の生起確率総和（１．１４６）で割ることはせず、葉の総数（１３０５個）から、補正Ｂ-１での圧縮符号長ごとの葉の総数（圧縮符号長の上限長Ｎの葉数除く）を引くことで、圧縮符号長の上限長Ｎの葉数を求める。この場合は、１２０８個である。
【０１０５】
このあと、コンピュータ１１００は、補正Ａの場合と同様の計算処理により、補正Ｂ-１での生起確率総和を求める。そして、コンピュータ１１００は、補正Ｂ-１での生起確率総和が１以下の最大漸近値に収束したか否かを判断する。補正Ｂ-１での生起確率総和が１以下の最大漸近値に収束していなければ、補正Ｂ-の２回目（補正Ｂ-２）に移行する。最大漸近値に収束した場合は、補正Ｂ-２に移行せず、この時点での圧縮符号長ごとの葉数で確定する。補正Ｂ-１で更新された生起確率総和「１．０４２」は１より大きいため、最大漸近値に収束しておらず、補正Ｂ-２に移行する。
【０１０６】
補正Ｂ-２では、圧縮符号長ごとの補正Ｂ-１での葉数を、前回の補正（この場合は補正Ｂ-１）の生起確率総和（１．０４２）で割ることで、葉数を更新する。なお、小数点以下は切り捨てでも、四捨五入でもよい。なお、補正Ｂ-１での圧縮符号長の上限長Ｎ（Ｎ＝１１ビット）については、前回の補正（この場合は補正Ｂ-１）の生起確率総和（１．０４２）で割ることはせず、葉の総数（１３０５個）から、補正Ｂ-２での圧縮符号長ごとの葉の総数（圧縮符号長の上限長Ｎの葉数除く）を引くことで、圧縮符号長の上限長Ｎの葉数を求める。この場合は、１２１５個である。
【０１０７】
このあと、コンピュータ１１００は、補正Ｂ-１の場合と同様の計算処理により、補正Ｂ-２での生起確率総和を求める。そして、コンピュータ１１００は、補正Ｂ-２での生起確率総和が１以下の最大漸近値に収束したか否かを判断する。補正Ｂ-２での生起確率総和が１以下の最大漸近値に収束していなければ、補正Ｂ-の３回目（補正Ｂ-３）に移行する。最大漸近値に収束した場合は、補正Ｂ-３に移行せず、この時点での圧縮符号長ごとの葉数で確定する。補正Ｂ-２で更新された生起確率総和「０．９８２」は１以下であるが、最大漸近値に収束しているかが不明であるため、補正Ｂ-３に移行する。
【０１０８】
補正Ｂ-３では、圧縮符号長ごとの補正Ｂ-２での葉数を、前回の補正（この場合は補正Ｂ-２）の生起確率総和（０．９８２）で割ることで、葉数を更新する。なお、小数点以下は切り捨てでも、四捨五入でもよい。なお、補正Ｂ-２での圧縮符号長の上限長Ｎ（Ｎ＝１１ビット）については、前回の補正（この場合は補正Ｂ-２）の生起確率総和（０．９８２）で割ることはせず、葉の総数（１３０５個）から、補正Ｂ-３での圧縮符号長ごとの葉の総数（圧縮符号長の上限長Ｎの葉数除く）を引くことで、圧縮符号長の上限長Ｎの葉数を求める。この場合は、１２１５個である。
【０１０９】
このあと、コンピュータ１１００は、補正Ｂ-２の場合と同様の計算処理により、補正Ｂ-３での生起確率総和を求める。そして、コンピュータ１１００は、補正Ｂ-３での生起確率総和が１以下の最大漸近値に収束したか否かを判断する。補正Ｂ-３での生起確率総和が１以下の最大漸近値に収束していなければ、補正Ｂ-の４回目（補正Ｂ-４）に移行する。最大漸近値に収束した場合は、補正Ｂ-４に移行せず、この時点での圧縮符号長ごとの葉数で確定する。
【０１１０】
補正Ｂ-３で更新された生起確率総和「０．９８２」は、補正Ｂ-２で更新された生起確率総和「０．９８２」と同じ値である。すなわち、補正Ｂ-３での各圧縮符号長の葉数と補正Ｂ-２での各圧縮符号長の葉数とは同じである。この場合、コンピュータ１１００は、生起確率総和が最大漸近値に収束したと判断し、葉数が確定する。
【０１１１】
このようにして、葉数が確定するまで補正Ｂ-を継続することとなる。図１６の例では、補正Ｂ-３で圧縮符号長ごとの葉数が確定したこととなる。このあと、コンピュータ１１００は、圧縮符号長ごとに、葉当たりの枝数を算出することとなる。葉当たりの枝数の算出は、上述したように、圧縮符号長の上限長Ｎ（この場合はＮ＝１１ビット）から降順に、２0、２1、２2、２3、２4、２5、２6として葉当たりの枝数を割り当てることとなる。なお、枝数の小計は、圧縮符号長ごとに、葉当たりの枝数に確定した葉数を乗じた乗算結果である。
【０１１２】
図１７は、文字情報ごとの補正結果を示す説明図である。図１７において、文字情報テーブルには、補正Ａ、補正Ｂ-１〜補正Ｂ-２までの補正結果が追加されている。図１７に示したように、補正により圧縮符号長別の葉数が更新されるため、順位項目の１位の文字情報から短い圧縮符号長が割り当てられることとなる。
【０１１３】
たとえば、補正Ｂ-２で確定した場合、圧縮符号長６ビットでは葉数が６、圧縮符号長７ビットでは葉数が１８、…、圧縮符号長１１ビットでは葉数が１２１５となっている。したがって、順位が１位から６位までの文字情報（葉数６個分）については６ビットの圧縮符号長、順位が７位から２４位までの文字情報（葉数１８個分）については７ビットの圧縮符号長、…、順位が９１位から１３０５位までの文字情報（葉数１２１５個分）については１１ビットの圧縮符号長が割り当てられる。
【０１１４】
そして、コンピュータ１１００は、文字情報と文字情報に割り当てられた圧縮符号長と圧縮符号長ごとの葉数とに基づいて、文字情報ごとに圧縮符号を割り当て、葉の構造体を生成することとなる。たとえば、出現率１位の単一文字「０」は５ビットの圧縮符号長が割り当てられているため、圧縮符号が「００００００」となる。したがって、圧縮符号「００００００」、圧縮符号長「６」、文字情報「０」を含む葉Ｌ１の構造体が生成されることとなる。
【０１１５】
なお、上述した補正処理では、圧縮符号長が５ビット〜１１ビットとしたが、２グラム文字列の圧縮符号マップＭを分割する場合もあるため、圧縮符号長は偶数ビットとなるように、補正してもよい。具体的には、たとえば、圧縮符号長５ビットおよび７ビットの文字情報については６ビット、９ビットの文字情報については８ビット、１１ビットの文字情報については１０ビットとする。
【０１１６】
図１８は、図１３の（６）葉へのポインタ生成の詳細（Ｎ＝１１）を示す説明図である。図１８は、圧縮符号長の上限Ｎが１１ビットの場合の葉へのポインタを示している。図１８において、圧縮符号長が６ビットの葉数は６個であるため、圧縮符号は「００００００」〜「０００１０１」が割り当てられる。また、圧縮符号長が６ビットの葉当たりの枝数は、３２本である。したがって、圧縮符号長が６ビットの圧縮符号についての葉へのポインタは、３２（＝２5）個生成される。具体的には、葉へのポインタの先頭６ビットが圧縮符号で後続５ビットが３２種のビット列となる。したがって、圧縮符号長が６ビットの圧縮符号の各々について、３２種の葉へのポインタが生成されることとなる。
【０１１７】
なお、図示はしないが、圧縮符号長が７ビットの葉数は１８個であるため、圧縮符号「０００１１００」〜「００１１１１１」が割り当てられる。また、圧縮符号長が７ビットの葉当たりの枝数は、１６本である。したがって、圧縮符号長が７ビットの圧縮符号についての葉へのポインタは、１６（＝２4）個生成される。具体的には、葉へのポインタの先頭７ビットが圧縮符号で後続４ビットが１６種のビット列となる。したがって、圧縮符号長が７ビットの圧縮符号の各々について、１６種の葉へのポインタが生成されることとなる。
【０１１８】
同様に、圧縮符号長が８ビットの葉数は２３個であるため、圧縮符号「０１００００００」〜「０１０１０１１０」が割り当てられる。また、圧縮符号長が８ビットの葉当たりの枝数は、８本である。したがって、圧縮符号長が８ビットの圧縮符号についての葉へのポインタは、８（＝２3）個生成される。具体的には、葉へのポインタの先頭８ビットが圧縮符号で後続３ビットが８種のビット列となる。したがって、圧縮符号長が８ビットの圧縮符号の各々について、８種の葉へのポインタが生成されることとなる。
【０１１９】
同様に、圧縮符号長が９ビットの葉数は２３個であるため、圧縮符号「０１０１０１１１０」〜「０１１０００１００」が割り当てられる。また、圧縮符号長が９ビットの葉当たりの枝数は、４本である。したがって、圧縮符号長が９ビットの圧縮符号についての葉へのポインタは、４（＝２2）個生成される。具体的には、葉へのポインタの先頭９ビットが圧縮符号で後続２ビットが４種のビット列となる。したがって、圧縮符号長が９ビットの圧縮符号の各々について、４種の葉へのポインタが生成されることとなる。
【０１２０】
同様に、圧縮符号長が１０ビットの葉数は２０個であるため、圧縮符号「０１１００００１１０」〜「０１１００１１１０１」が割り当てられる。また、圧縮符号長が１０ビットの葉当たりの枝数は、２本である。したがって、圧縮符号長が１０ビットの圧縮符号についての葉へのポインタは、２（＝２1）個生成される。具体的には、葉へのポインタの先頭１０ビットが圧縮符号で後続１ビットが２種のビット列となる。したがって、圧縮符号長が１０ビットの圧縮符号の各々について、２種の葉へのポインタが生成されることとなる。
【０１２１】
同様に、圧縮符号長が１１ビットの葉数は１２１５個であるため、圧縮符号「０１１００１１１１００」〜「１１１１１１１１０１０」が割り当てられる。また、圧縮符号長が１１ビットの葉当たりの枝数は、１本である。したがって、圧縮符号長が１１ビットの圧縮符号についての葉へのポインタは、１（＝２0）個生成される。具体的には、圧縮符号がそのまま葉へのポインタとなる。したがって、圧縮符号長が１１ビットの圧縮符号の各々について、１種の葉へのポインタが生成されることとなる。
【０１２２】
図１９は、図１３の（７）２N分枝無節点ハフマン木Ｈの構築の詳細（Ｎ＝１１）を示す説明図である。図１９では、Ｎ＝１１とした場合の２０４８（＝２11）分枝無節点ハフマン木Ｈを示している。根の構造体には、葉へのポインタが格納されている。葉へのポインタはポイント先の葉の構造体を指定することができる。
【０１２３】
具体的には、圧縮符号長が６ビットの圧縮符号が格納される葉の構造体についての葉へのポインタは、図１８に示したように３２個生成される。したがって、葉Ｌ１の構造体については、根の構造体に３２個の葉Ｌ１へのポインタＬ１Ｐ（１）〜Ｌ１Ｐ（３２）が格納される。葉Ｌ２の構造体〜葉Ｌ６の構造体についても同様である。葉Ｌ７以降の構造体については、図１９のとおりである。
【０１２４】
図２０は、葉の構造体を示す説明図である。葉の構造体は、第１領域〜第４領域を有するデータ構造体である。葉の構造体は、第１領域には、圧縮符号およびその圧縮符号長が格納される。第２領域には、葉の標識と伸長種別（図１５参照）、出現率（図１５参照）が格納される。第３領域には、伸長種別に応じて特定単一文字である１６ビットの文字コード、非特定単一文字の文字コードが分割された８ビットの分割文字コード、または基礎単語へのポインタが格納される。基礎単語へのポインタにより基礎単語の構造体内の基礎単語が指定される。また、照合フラグも格納されている。照合フラグはデフォルトでは「０」である。「０」の場合は、伸長する文字をそのまま伸長バッファに書き出し、「１」の場合は、＜ｃｏｌｏｒ＞タグと＜／ｃｏｌｏｒ＞タグで挟み込んで伸長バッファに書き出す。
【０１２５】
第４領域には、格納されている文字情報の出現率と出現マップの出現率領域が格納される。出現率とは、図１５に示した文字情報の出現率である。出現マップの出現率領域については図５５および図５６で説明する。なお、第３領域には、そのほか、符号種別と符号区分が格納される。符号種別とは、文字コードが数字、英字、特殊記号、カタカナ、ひらがな、漢字のいずれに該当するか、または基礎単語へのポインタであるかを識別する情報である。符号区分とは、文字コードが１６ビットであるか８ビットであるかを識別する情報である。１６ビットの文字コードである場合または予約語である場合、符号区分として“１”を割り当て、８ビットの分割文字コードの場合、符号区分として“０”を割り当てる。
【０１２６】
なお、第１領域〜第４領域内の情報は、後述する構築処理（ステップＳ３９０５）において格納されることとなる。
【０１２７】
図２１は、特定単一文字の構造体を示す説明図である。特定単一文字の構造体２１００は、特定単一文字コードｅ♯とその葉Ｌ♯へのポインタを格納するデータ構造体である。具体的には、たとえば、コンピュータ１１００は、対象ファイル群Ｆｓからの集計結果が得られたときに、コンピュータ１１００が、特定単一文字の構造体２１００に特定単一文字コードｅ♯を格納する。そして、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈが構築されると、２N分枝無節点ハフマン木Ｈにおける各葉の構造体に格納された圧縮符号に対応する、特定単一文字の構造体２１００における特定文字コードｅ♯へのポインタを格納する。
【０１２８】
また、特定単一文字コードｅ♯へのポインタが対応する葉の構造体に格納されると、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈにおける各特定単一文字コードｅ♯に対応する葉へのポインタを、特定単一文字の構造体２１００内の対応する特定単一文字コードｅ♯に関連付けて格納する。これにより、特定単一文字の構造体２１００が生成される。
【０１２９】
図２２は、分割文字コードの構造体を示す説明図である。分割文字コードの構造体２２００は、分割文字コードとその葉Ｌ♯へのポインタを格納する。具体的には、たとえば、コンピュータ１１００は、対象ファイル群Ｆｓからの集計結果が得られたときに、コンピュータ１１００が、分割文字コードの構造体２２００に分割文字コードを格納する。そして、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈが構築されると、２N分枝無節点ハフマン木Ｈにおける各葉の構造体に格納された圧縮符号に対応する、分割文字コードの構造体２２００における分割文字コードへのポインタを格納する。
【０１３０】
また、分割文字コードへのポインタが対応する葉の構造体に格納されると、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈにおける各分割文字コードに対応する葉へのポインタを、分割文字コードの構造体２２００内の対応する分割文字コードに関連付けて格納する。これにより、分割文字コードの構造体２２００が生成される。
【０１３１】
図２３は、基礎単語の構造体を示す説明図である。基礎単語の構造体２３００は、基礎単語とその葉Ｌ♯へのポインタを格納するデータ構造体である。基礎単語の構造体２３００には、あらかじめ基礎単語が格納されている。コンピュータ１１００は、２N分枝無節点ハフマン木Ｈが構築されると、２N分枝無節点ハフマン木Ｈにおける各葉の構造体に格納された圧縮符号に対応する、基礎単語の構造体２３００における基礎単語へのポインタを格納する。
【０１３２】
また、基礎単語へのポインタが対応する葉の構造体に格納されると、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈにおける各基礎単語に対応する葉へのポインタを、基礎単語の構造体２３００内の対応する基礎に関連付けて格納することとなる。
【０１３３】
＜圧縮符号マップＭｓの作成例＞
第１生成部１１０２により２N分枝無節点ハフマン木Ｈが生成されると、作成部１１０４は、単一文字の圧縮符号マップＭｓ、上位分割文字コードの圧縮符号マップＭｓ、下位分割文字コードの圧縮符号マップＭｓ、単語の圧縮符号マップＭｓ、２グラム文字列の圧縮符号マップＭｓを作成する。以下、単一文字の圧縮符号マップＭｓ、上位分割文字コードの圧縮符号マップＭｓ、下位分割文字コードの圧縮符号マップＭｓ、２グラム文字列の圧縮符号マップＭｓの詳細な作成例について説明する。なお、基礎単語の圧縮符号マップＭｓは、単一文字の圧縮符号マップＭｓと同様に行われるため省略する。
【０１３４】
図２４は、圧縮符号マップＭｓの生成例を示す説明図である。図２４では、対象ファイルＦｉ内に『竜馬は脱藩した』という文字列が記述されているものとする。
【０１３５】
（Ａ）まず、先頭文字「竜」が対象文字である。対象文字「竜」は特定単一文字であるため、２N分枝無節点ハフマン木Ｈにアクセスして特定単一文字「竜」の圧縮符号を取得し、特定単一文字「竜」の出現マップを特定する。未生成の場合は、特定単一文字「竜」の圧縮符号をポインタとし、かつ、対象ファイルの存否を示すビット列をオール０にした特定単一文字「竜」の出現マップを生成する。そして、特定単一文字「竜」の出現マップについて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。
【０１３６】
（Ｂ）つぎに、対象文字を１グラムシフトして、対象文字を「馬」にする。対象文字「馬」は特定単一文字であるため、２N分枝無節点ハフマン木Ｈにアクセスして特定単一文字「馬」の圧縮符号を取得し、特定単一文字「馬」の出現マップを特定する。未生成の場合は、特定単一文字「馬」の圧縮符号をポインタとし、かつ、対象ファイルの存否を示すビット列をオール０にした特定単一文字「馬」の出現マップを生成する。そして、特定単一文字「馬」の出現マップについて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。
【０１３７】
また、対象文字が「馬」にシフトされた場合、「竜馬」という２グラム文字列が得られるため、「竜」の圧縮符号と「馬」の圧縮符号を結合した「竜馬」の圧縮符号列により、２グラム文字列「竜馬」の出現マップを特定する。未生成の場合は、「竜馬」の圧縮符号列をポインタとし、かつ、対象ファイルの存否を示すビット列をオール０にした２グラム文字列「竜馬」の出現マップを生成する。そして、２グラム文字列「竜馬」の出現マップにおいて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。
【０１３８】
（Ｃ）つぎに、対象文字を１グラムシフトして、対象文字を「は」にする。対象文字「は」についても（Ｂ）と同様に処理することで、特定単一文字「は」の出現マップについて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。同様に、２グラム文字列「馬は」の出現マップにおいて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。
【０１３９】
（Ｄ）つぎに、対象文字を１グラムシフトして、対象文字を「脱」にする。対象文字「脱」は特定単一文字ではないため、対象文字「脱」の文字コード「０ｘ８１３１」を、上位分割文字コード「０ｘ８１」と下位分割文字コード「０ｘ３１」に分割する。そして、対象文字を上位分割文字コード「０ｘ８１」にする。上位分割文字コード「０ｘ８１」についても、特定単一文字と同様に処理することで、上位分割文字コード「０ｘ８１」の出現マップについて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。同様に、２グラム文字列「は  ０ｘ８１」の出現マップにおいて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。
【０１４０】
（Ｅ）つぎに、対象文字を１グラムシフトして、文字「脱」の下位分割文字コード「０ｘ３１」を、対象文字にする。下位分割文字コード「０ｘ３１」についても、同様に処理することで、下位分割文字コード「０ｘ３１」の出現マップについて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。同様に、２グラム文字列「０ｘ８１  ０ｘ３１」の出現マップにおいて対象ファイルＦｉのビットをＯＮ（“０”→“１”）にする。
【０１４１】
（Ｆ）〜（Ｉ）についても同様の処理をおこない、最後の対象ファイルＦｎについても処理を完了することで、単一文字、上位分割文字コード、下位分割文字コード、２グラム文字列のそれぞれについて、圧縮符号マップＭｓが生成される。
【０１４２】
＜圧縮符号マップ生成処理手順＞
つぎに、作成部１１０４による圧縮符号マップ作成処理手順例について説明する。
【０１４３】
図２５は、作成部１１０４による圧縮符号マップ作成処理手順例を示すフローチャートである。コンピュータ１１００は、集計処理（ステップＳ２５０１）、マップ割当数決定処理（ステップＳ２５０２）、再集計処理（ステップＳ２５０３）、ハフマン木生成処理（ステップＳ２５０４）、マップ作成処理（ステップＳ２５０５）を実行する。コンピュータ１１００は、集計部１１０１により集計処理（ステップＳ２５０１）〜再集計処理（ステップＳ２５０３）を実行する。また、第１生成部１１０２によりハフマン木生成処理（ステップＳ２５０４）を実行し、作成部１１０４によりマップ作成処理（ステップＳ２５０５）を実行する。
【０１４４】
集計処理（ステップＳ２５０１）とは、対象ファイル群Ｆｓ内の単一文字や基礎単語の出現回数（出現頻度ともいう）を計数する処理である。マップ割当数決定処理（ステップＳ２５０２）とは、集計処理（ステップＳ２５０１）で集計された単一文字および基礎単語についてのマップ割当数を決定する処理である。マップ割当数に対応する出現順位の単一文字および基礎単語が、それぞれ特定単一文字および基礎単語となる。
【０１４５】
再集計処理（ステップＳ２５０３）とは、単一文字のうち特定単一文字以外の非特定単一文字を分割して、上位分割文字コードおよび下位分割文字コードとし、それぞれの出現回数を集計する処理である。また、再集計処理（ステップＳ２５０３）では、２グラム文字列の出現回数も集計する。
【０１４６】
ハフマン木生成処理（ステップＳ２５０４）とは、図１５〜図２０に示したように、２N分枝無節点ハフマン木Ｈを生成する処理である。マップ作成処理（ステップＳ２５０５）とは、特定単一文字、基礎単語、上位分割文字コード、下位分割文字コード、２グラム文字列についての圧縮符号マップＭを生成する処理である。
【０１４７】
（集計処理（ステップＳ２５０１））
図２６は、図２５に示した集計処理（ステップＳ２５０１）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、ファイル番号ｉをｉ＝１に設定し（ステップＳ２６０１）、対象ファイルＦｉを読み込む（ステップＳ２６０２）。そして、コンピュータ１１００は、対象ファイルＦｉの集計処理を実行する（ステップＳ２６０３）。対象ファイルＦｉの集計処理（ステップＳ２６０３）の詳細については、図２７で説明する。このあと、コンピュータ１１００は、ファイル番号ｉがｉ＞ｎ（ｎは対象ファイルＦ１〜Ｆｎの総数）であるか否かを判断する（ステップＳ２６０４）。
【０１４８】
ｉ＞ｎでない場合（ステップＳ２６０４：Ｎｏ）、コンピュータ１１００は、ｉをインクリメントし（ステップＳ２６０５）、ステップＳ２６０２に戻る。一方、ｉ＞ｎである場合（ステップＳ２６０４：Ｙｅｓ）、コンピュータ１１００は、図２５に示したマップ割当数決定処理（ステップＳ２５０２）に移行して、集計処理（ステップＳ２５０１）を終了する。この集計処理（ステップＳ２５０１）によれば、対象ファイルＦｉごとに対象ファイルＦｉの集計処理（ステップＳ２６０３）を実行することができる。
【０１４９】
（対象ファイルＦｉの集計処理（ステップＳ２６０３））
図２７は、図２６に示した対象ファイルＦｉの集計処理（ステップＳ２６０３）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、対象文字を対象ファイルＦｉの先頭文字とし（ステップＳ２７０１）、基礎単語集計処理を実行する（ステップＳ２７０２）。基礎単語集計処理（ステップＳ２７０２）の詳細については図２９で説明する。このあと、コンピュータ１１００は、文字出現頻度集計テーブルにおいて対象文字の出現回数を１増加する（ステップＳ２７０３）。
【０１５０】
図２８は、文字出現頻度集計テーブルを示す説明図である。文字出現頻度集計テーブル２８００は、ＲＡＭ９０３や磁気ディスク９０５などの記憶装置に記憶されており、該当する文字が出現する都度出現回数を１ずつ増加させる。
【０１５１】
図２７に戻り、コンピュータ１１００は、対象文字が対象ファイルＦｉの末尾文字であるか否かを判断する（ステップＳ２７０４）。対象文字が対象ファイルＦｉの末尾文字でない場合（ステップＳ２７０４：Ｎｏ）、コンピュータ１１００は、対象文字を末尾方向へ１文字シフトし（ステップＳ２７０５）、ステップＳ２７０２に戻る。
【０１５２】
一方、対象文字が対象ファイルＦｉの末尾文字である場合（ステップＳ２７０４：Ｙｅｓ）、コンピュータ１１００は、ステップＳ２６０４に移行して、対象ファイルＦｉの集計処理（ステップＳ２６０３）を終了する。この対象ファイルＦｉの集計処理（ステップＳ２６０３）によれば、対象ファイル群Ｆｓに存在する基礎単語および単一文字の出現頻度を集計することができる。
【０１５３】
（基礎単語集計処理（ステップＳ２７０２））
図２９は、図２７に示した基礎単語集計処理（ステップＳ２７０２）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、最長一致検索処理を実行し（ステップＳ２９０１）、最長一致した基礎単語があったか否かを判断する（ステップＳ２９０２）。最長一致検索処理（ステップＳ２９０１）の詳細については図３１で説明する。最長一致した基礎単語があった場合（ステップＳ２９０２：Ｙｅｓ）、コンピュータ１１００は、基礎単語出現頻度集計テーブルにおいて最長一致した基礎単語の出現回数を１増加し（ステップＳ２９０３）、ステップＳ２７０３に移行する。
【０１５４】
図３０は、基礎単語出現頻度集計テーブルを示す説明図である。基礎単語出現頻度集計テーブル３０００は、ＲＡＭ９０３や磁気ディスク９０５などの記憶装置に記憶されており、該当する基礎単語が出現する都度出現回数を１ずつ増加させる。
【０１５５】
図２９に戻り、最長一致した基礎単語がなかった場合（ステップＳ２９０２：Ｎｏ）、ステップＳ２７０３に移行する。これにより、基礎単語集計処理（ステップＳ２７０２）を終了する。この基礎単語集計処理（ステップＳ２７０２）によれば、最長一致検索処理（ステップＳ２９０１）により基礎単語を計数することができるため、文字列が長い基礎単語を優先的に計数することができる。
【０１５６】
（最長一致検索処理（ステップＳ２９０１））
図３１は、図２９に示した最長一致検索処理（ステップＳ２９０１）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、ｃ＝１とする（ステップＳ３１０１）。ｃは対象文字からの文字数（対象文字含む）である。ｃ＝１の場合は、対象文字だけである。つぎに、コンピュータ１１００は、対象文字からｃ文字目までの対象文字列と前方一致する基礎単語を２分探索する（ステップＳ３１０２）。そして、コンピュータ１１００は、検索により基礎単語があるか否かを判断する（ステップＳ３１０３）。２分探索により基礎単語がヒットしなかった場合（ステップＳ３１０３：Ｎｏ）、ステップＳ３１０６に移行する。
【０１５７】
一方、２分探索により基礎単語がヒットした場合（ステップＳ３１０３：Ｙｅｓ）、コンピュータ１１００は、ヒットした基礎単語と対象文字列とが完全一致するか否かを判断する（ステップＳ３１０４）。そして、完全一致しない場合（ステップＳ３１０４：Ｎｏ）、ステップＳ３１０６に移行する。一方、完全一致する場合（ステップＳ３１０４：Ｙｅｓ）、コンピュータ１１００は、最長一致候補として記憶装置に保持し（ステップＳ３１０５）、ステップＳ３１０６に移行する。
【０１５８】
ステップＳ３１０６では、コンピュータ１１００は、対象文字列について２分探索が終了したか否かを判断する（ステップＳ３１０６）。具体的には、コンピュータ１１００は、末尾の基礎単語まで２分探索したか否かを判断する。２分探索が終了していない場合（ステップＳ３１０６：Ｎｏ）、コンピュータ１１００は、ステップＳ３１０２に移行して、２分探索が終了するまで継続する。
【０１５９】
一方、対象文字列について２分探索が終了した場合（ステップＳ３１０６：Ｙｅｓ）、コンピュータ１１００は、ｃ文字目の文字が対象ファイルＦｉの末尾文字であるか否かを判断する（ステップＳ３１０７）。ｃ文字目の文字が対象ファイルＦｉの末尾文字である場合（ステップＳ３１０７：Ｙｅｓ）、ステップＳ３１１０に移行する。一方、ｃ文字目の文字が対象ファイルＦｉの末尾文字でない場合（ステップＳ３１０７：Ｎｏ）、コンピュータ１１００は、ｃ＞ｃｍａｘであるか否かを判断する（ステップＳ３１０８）。ｃｍａｘはあらかじめ設定された値であり、これにより対象文字列の上限文字数が設定される。
【０１６０】
ｃ＞ｃｍａｘでない場合（ステップＳ３１０８：Ｎｏ）、コンピュータ１１００は、ｃをインクリメントして（ステップＳ３１０９）、ステップＳ３１０２に戻る。一方、ｃ＞ｃｍａｘである場合（ステップＳ３１０８：Ｙｅｓ）、コンピュータ１１００は、最長一致候補があるか否かを判断する（ステップＳ３１１０）。具体的には、コンピュータ１１００は、ステップＳ３１０５において１つでも最長一致候補がメモリに保持されているか否かを判断する。
【０１６１】
最長一致候補がある場合（ステップＳ３１１０：Ｙｅｓ）、コンピュータ１１００は、最長一致候補のうち最長文字列を、最長一致した基礎単語に決定する（ステップＳ３１１１）。そして、ステップＳ２９０２に移行する。一方、ステップＳ３１１０において、最長一致候補が１つもない場合（ステップＳ３１１０：Ｎｏ）、ステップＳ２９０２に移行する。これにより、最長一致検索処理（ステップＳ２９０１）を終了する。この最長一致検索処理（ステップＳ２９０１）によれば、基礎単語の構造体にある基礎単語の中から、完全一致した文字列の中でかつ最長の文字列を基礎単語として検索することができる。
【０１６２】
（マップ割当数決定処理（ステップＳ２５０２））
図３２は、図２５に示したマップ割当数決定処理（ステップＳ２５０２）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、集計処理（ステップＳ２５０１）による基礎単語ごとの出現頻度を示す基礎単語出現頻度集計テーブル３０００と単一文字ごとの出現頻度を示す文字出現頻度集計テーブル２８００を出現頻度の高い順にソートする（ステップＳ３２０１）。そして、コンピュータ１１００は、ソート後の基礎単語出現頻度集計テーブル３０００を参照して、基礎単語の出現順位ＲｗをＲｗ＝１とし（ステップＳ３２０２）、出現順位Ｒｗまでの累積出現回数Ａｒｗを計数する（ステップＳ３２０３）。そして、コンピュータ１１００は、下記式（１）を満たすか否かを判断する（ステップＳ３２０４）。
【０１６３】
Ａｒｗ＞Ｐｗ×Ａｗ・・・（１）
Ａｗは集計された基礎単語の総出現回数である。
【０１６４】
上記（１）式を満たさない場合（ステップＳ３２０４：Ｎｏ）、コンピュータ１１００は、出現順位Ｒｗをインクリメントして（ステップＳ３２０５）、ステップＳ３２０３に戻る。すなわち、上記式（１）を満たすまで出現順位Ｒｗを下げ続ける。
【０１６５】
そして、上記式（１）を満たした場合（ステップＳ３２０４：Ｙｅｓ）、コンピュータ１１００は、基礎単語のマップ割当数ＮｗをＮｗ＝Ｒｗ−１とする（ステップＳ３２０６）。ここで、マップ割当数Ｎｗとは、マップ作成処理（ステップＳ３２０５）で生成される基礎単語出現マップに割り当てられる基礎単語数であり、基礎単語出現マップのレコード数（行数）を意味する。
【０１６６】
また、コンピュータ１１００は、単一文字の出現順位ＲｃをＲｃ＝１とし（ステップＳ３２０７）、出現順位Ｒｃまでの累積出現回数Ａｒｃを計数する（ステップＳ３２０８）。そして、コンピュータ１１００は、下記式（２）を満たすか否かを判断する（ステップＳ３２０９）。
【０１６７】
Ａｒｃ＞Ｐｃ×Ａｃ・・・（２）
Ａｃは集計された単一文字の総出現回数である。
【０１６８】
上記（２）式を満たさない場合（ステップＳ３２０９：Ｎｏ）、コンピュータ１１００は、出現順位Ｒｃをインクリメントして（ステップＳ３２１０）、ステップＳ３２０８に戻る。すなわち、上記式（２）を満たすまで出現順位Ｒｃを下げ続ける。
【０１６９】
そして、上記式（２）を満たした場合（ステップＳ３２０９：Ｙｅｓ）、コンピュータ１１００は、単一文字のマップ割当数ＮｃをＮｃ＝Ｒｃ−１とする（ステップＳ３２１１）。ここで、マップ割当数Ｎｃとは、マップ作成処理（ステップＳ２５０５）で生成される特定単一文字出現マップに割り当てられる特定単一文字数であり、特定単一文字出現マップのレコード数（行数）を意味する。この後、再集計処理（ステップＳ２５０３）に移行して、マップ割当数決定処理（ステップＳ２５０２）を終了する。
【０１７０】
このマップ割当数決定処理（ステップＳ２５０２）によれば、マップ作成処理（ステップＳ２５０５）において目標出現率Ｐｗに応じた数の基礎単語分について基礎単語出現マップを生成することができる。したがって、すべての基礎単語についてマップ割当をおこなう必要はなく、目標出現率Ｐｗにしたがって決められるため、マップサイズの最適化を図ることができる。
【０１７１】
また、単一文字についても、マップ作成処理（ステップＳ２５０５）において目標出現率Ｐｃに応じた数の単一文字分について特定単一文字の圧縮符号マップＭを生成することができる。したがって、すべての単一文字についてマップ割当をおこなう必要はなく、目標出現率Ｐｃにしたがって決められるため、マップサイズの最適化を図ることができる。
【０１７２】
（再集計処理（ステップＳ２５０３））
図３３は、図２５に示した再集計処理（ステップＳ２５０３）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、ファイル番号ｉをｉ＝１に設定し（ステップＳ３３０１）、対象ファイルＦｉを読み込む（ステップＳ３３０２）。そして、コンピュータ１１００は、対象ファイルＦｉの再集計処理を実行する（ステップＳ３３０３）。対象ファイルＦｉの再集計処理（ステップＳ３３０３）の詳細については、図３３で説明する。このあと、コンピュータ１１００は、ファイル番号ｉがｉ＞ｎ（ｎは対象ファイルＦ１〜Ｆｎの総数）であるか否かを判断する（ステップＳ３３０４）。
【０１７３】
ｉ＞ｎでない場合（ステップＳ３３０４：Ｎｏ）、コンピュータ１１００は、ｉをインクリメントし（ステップＳ３３０５）、ステップＳ３３０２に戻る。一方、ｉ＞ｎである場合（ステップＳ３３０４：Ｙｅｓ）、コンピュータ１１００は、図２５に示したハフマン木生成処理（ステップＳ３２０４）に移行して、再集計処理（ステップＳ３２０３）を終了する。この再集計処理（ステップＳ３２０３）によれば、対象ファイルＦｉごとに対象ファイルＦｉの再集計処理（ステップＳ３３０３）を実行することができる。
【０１７４】
（対象ファイルＦｉの再集計処理（ステップＳ３３０３））
図３４は、対象ファイルＦｉの再集計処理（ステップＳ３３０３）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、対象文字を対象ファイルＦｉの先頭文字とし（ステップＳ３４０１）、対象文字が特定単一文字であるか否かを判断する（ステップＳ３４０２）。特定単一文字である場合（ステップＳ３４０２：Ｙｅｓ）、分割せずにステップＳ３４０４に移行する。
【０１７５】
一方、特定単一文字でない場合（ステップＳ３４０２：Ｎｏ）、コンピュータ１１００は、対象文字の文字コードを上位分割文字コードと下位分割文字コードとに分割する（ステップＳ３４０３）。そして、ステップＳ３４０４に移行する。
【０１７６】
ステップＳ３４０４では、コンピュータ１１００は、上位分割文字コード出現頻度集計テーブルに対し、ステップＳ３４０３で得られた上位分割文字コードと同一分割文字コードの出現回数を１加算する（ステップＳ３４０４）。
【０１７７】
図３５は、上位分割文字コード出現頻度集計テーブルを示す説明図である。上位分割文字コード出現頻度集計テーブル３５００は、ＲＡＭ９０３や磁気ディスク９０５などの記憶装置に記憶されており、該当する上位分割文字コードが出現する都度出現回数を１ずつ増加させる。
【０１７８】
また、図３４において、コンピュータ１１００は、下位分割文字コード出現頻度集計テーブルに対し、ステップＳ３４０３で得られた下位分割文字コードと同一分割文字コードの出現回数を１加算する（ステップＳ３４０５）。
【０１７９】
図３６は、下位分割文字コード出現頻度集計テーブルを示す説明図である。下位分割文字コード出現頻度集計テーブル３６００は、ＲＡＭ９０３や磁気ディスク９０５などの記憶装置に記憶されており、該当する下位分割文字コードが出現する都度出現回数を１ずつ増加させる。
【０１８０】
また、図３４において、コンピュータ１１００は、２グラム文字列特定処理を実行する（ステップＳ３４０６）。２グラム文字列特定処理（ステップＳ３４０６）では、対象文字を基点とする２グラム文字列を特定する。２グラム文字列特定処理（ステップＳ３４０６）の詳細は図３７で説明する。
【０１８１】
コンピュータ１１００は、２グラム文字列出現頻度集計テーブルに対し、２グラム文字列特定処理（ステップＳ３４０６）で特定された２グラム文字列の出現回数を１加算する（ステップＳ３４０７）。
【０１８２】
図３７は、図３４で示した２グラム文字列特定処理（ステップＳ３４０６）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、対象文字に対し、対象文字は分割されたか否かを判断する（ステップＳ３７０１）。すなわち、コンピュータ１１００は、対象文字が分割文字コードか否かを判断する。分割されていない場合（ステップＳ３７０１：Ｎｏ）、すなわち、単一文字の場合、コンピュータ１１００は、１つ前の文字があるか否かを判断する（ステップＳ３７０２）。
【０１８３】
１つ前の文字がある場合（ステップＳ３７０２：Ｙｅｓ）、コンピュータ１１００は、１つ前の文字は分割されたか否かを判断する（ステップＳ３７０３）。すなわち、コンピュータ１１００は、１つ前の文字が分割文字コードか否かを判断する。分割されていない場合（ステップＳ３７０３：Ｎｏ）、すなわち、単一文字の場合、コンピュータ１１００は、対象文字の１つ前の単一文字と対象文字（単一文字）からなる文字列を、２グラム文字列に決定する（ステップＳ３７０４）。そして、ステップＳ３４０７に移行する。
【０１８４】
一方、ステップＳ３７０３において、１つ前の文字が分割された場合（ステップＳ３７０３：Ｙｅｓ）、すなわち、分割文字コードである場合、その１つ前の文字である分割文字コードは、下位分割文字コードとなる。したがって、コンピュータ１１００は、１つ前の文字である下位分割文字コードと対象文字からなる文字列を、２グラム文字列に決定する（ステップＳ３７０５）。そして、ステップＳ３４０７に移行する。
【０１８５】
また、ステップＳ３７０２において、１つ前の文字がない場合（ステップＳ３７０２：Ｎｏ）、対象文字だけとなるため、２グラム文字列を決定せずに、ステップＳ３４０７に移行する。
【０１８６】
また、ステップＳ３７０１において、対象文字が分割された場合（ステップＳ３７０１：Ｙｅｓ）、すなわち、分割文字コードである場合、コンピュータ１１００は、その分割文字コードが上位分割文字コードか下位分割文字コードであるかを判断する（ステップＳ３７０６）。
【０１８７】
上位分割文字コードである場合（ステップＳ３７０６：上位）、コンピュータ１１００は、１つ前の文字は分割されたか否かを判断する（ステップＳ３７０７）。すなわち、１つ前の文字が分割文字コードか否かを判断する。分割されていない場合（ステップＳ３７０７：Ｎｏ）、すなわち、単一文字の場合、コンピュータ１１００は、対象文字の１つ前の単一文字と対象文字から分割された上位分割文字コードからなる文字列を、２グラム文字列に決定する（ステップＳ３７０８）。そして、ステップＳ３４０７に移行する。
【０１８８】
一方、ステップＳ３７０７において、１つ前の文字が分割された場合（ステップＳ３７０７：Ｙｅｓ）、すなわち、分割文字コードである場合、その１つ前の文字である分割文字コードは、下位分割文字コードとなる。したがって、コンピュータ１１００は、１つ前の文字である下位分割文字コードと対象文字から分割された上位分割文字コードからなる文字列を、２グラム文字列に決定する（ステップＳ３７０９）。そして、ステップＳ３４０７に移行する。
【０１８９】
また、ステップＳ３７０６において、下位分割文字コードである場合（ステップＳ３７０６：下位）、コンピュータ１１００は、対象文字から分割された上位分割文字コードおよび下位分割文字コードからなる文字列を、２グラム文字列に決定する（ステップＳ３７１０）。そして、ステップＳ３４０７に移行する。
【０１９０】
この２グラム文字列特定処理（ステップＳ３４０６）によれば、対象文字が分割された場合であっても２グラム文字列を特定することができる。また、１文字シフトにしたがって２グラム文字列を特定するため、基礎単語の圧縮符号マップＭおよび特定単一文字の圧縮符号マップＭと同時並行で生成することができる。
【０１９１】
このように、上述した情報生成によれば、目標出現率Ｐｗ，Ｐｃにより、マップ作成される基礎単語数および単一文字数が制限されるため、無駄なマップ作成がなくなり、マップ作成の高速化およびマップサイズの最適化を同時に実現することができる。また、１文字シフトにより複数種類のマップ作成を同時並行で実行することができ、高精度な検索に用いる複数種類のマップ作成の効率化を図ることができる。
【０１９２】
図３８は、２グラム文字列出現頻度集計テーブルを示す説明図である。２グラム文字列出現頻度集計テーブル３８００は、ＲＡＭ９０３や磁気ディスク９０５などの記憶装置に記憶されており、該当する２グラム文字列が出現する都度出現回数を１ずつ増加させる。
【０１９３】
このあと、コンピュータ１１００は、対象文字の後続文字が対象ファイルＦｉ内にあるか否かを判断し（ステップＳ３４０８）、後続文字がある場合（ステップＳ３４０８：Ｙｅｓ）、後続文字を対象文字に設定し（ステップＳ３４０９）、ステップＳ３４０２に戻る。一方、後続文字がない場合（ステップＳ３４０８：Ｎｏ）、対象ファイルＦｉの再集計処理（ステップＳ３３０３）を終了して、ステップＳ３３０４に移行する。
【０１９４】
これにより、対象ファイルＦｉごとに、対象ファイルＦｉ内に存在する上位分割文字コード、下位分割文字コード、および２グラム文字列の出現回数を集計することができる。
【０１９５】
（ハフマン木生成処理（ステップＳ２５０４））
図３９は、図２５に示したハフマン木生成処理（ステップＳ２５０４）の詳細な処理手順例を示すフローチャートである。図３９において、コンピュータ１１００は、圧縮符号長の上限長Ｎを決定する（ステップＳ３９０１）。つぎに、コンピュータ１１００は、補正処理を実行する（ステップＳ３９０２）。ここで、補正処理とは、図１５〜図１７で説明したように、文字情報ごとの生起確率および圧縮符号長を、圧縮符号長の上限長Ｎを用いて補正する処理である。
【０１９６】
つぎに、コンピュータ１１００は、文字情報ごとに葉の構造体を生成する（ステップＳ３９０３）。そして、コンピュータ１１００は、枝数特定処理を実行する（ステップＳ３９０４）。枝数特定処理（ステップＳ３９０４）では、圧縮符号長ごとの葉当たりの枝数を特定する。枝数特定処理（ステップＳ３９０４）の詳細は図４０で説明する。
【０１９７】
そして、コンピュータ１１００は、構築処理を実行する（ステップＳ３９０５）。枝数特定処理（ステップＳ３９０４）により葉の構造体ごとの枝数が特定されるため、まず、コンピュータ１１００は、葉の構造体ごとに、枝数分の葉へのポインタ群を生成する。そして、生成された各葉の構造体についての葉へのポインタ群を集約して根の構造体とする。これにより、２N分枝無節点ハフマン木Ｈが生成されることとなる。なお、生成された２N分枝無節点ハフマン木Ｈは、コンピュータ１１００内の記憶装置（ＲＡＭ９０３や磁気ディスク９０５など）に格納される。このあと、図２５のマップ作成処理（ステップＳ２５０５）に移行する。
【０１９８】
図４０は、図３９に示した枝数特定処理（ステップＳ３９０４）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、最大圧縮符号長ＣＬｍａｘ（＝Ｎ）と最小圧縮符号長ＣＬｍｉｎ（＝Ｍ）との差分Ｄ（＝Ｎ−Ｍ）を算出する（ステップＳ４００１）。たとえば、Ｎ＝１１の場合、図２６を参照すると、Ｍ＝６である。したがって、Ｄ＝５である。
【０１９９】
つぎに、コンピュータ１１００は、２のべき数の変数ｊをｊ＝０とし、圧縮符号長の変数ＣＬをＣＬ＝Ｎとする（ステップＳ４００２）。そして、コンピュータ１１００は、ｊ＞Ｄであるか否かを判断する（ステップＳ４００３）。ｊ＞Ｄでない場合（ステップＳ４００３：Ｎｏ）、コンピュータ１１００は、圧縮符号長ＣＬの葉当たりの枝数ｂ（ＣＬ）を算出する（ステップＳ４００４）。圧縮符号長ＣＬの葉当たりの枝数ｂ（ＣＬ）は、ｂ（ＣＬ）＝２jで算出される。たとえば、ｊ＝０のとき、圧縮符号長ＣＬ＝Ｎ＝１１であるため、圧縮符号長１１ビットでの葉当たりの枝数ｂ（１１）は、ｂ（１１）＝２j＝２0＝１となる。
【０２００】
つぎに、コンピュータ１１００は、圧縮符号長ＣＬの総枝数Ｂ（Ｌ）を算出する（ステップＳ４００５）。圧縮符号長ＣＬの総枝数Ｂ（Ｌ）は、Ｂ（Ｌ）＝Ｌ（ＣＬ）×ｂ（ＣＬ）で算出される。Ｌ（ＣＬ）は、圧縮符号長ＣＬでの葉数（文字情報の種類数）である。たとえば、ｊ＝０のとき、圧縮符号長ＣＬ＝Ｎ＝１１であるため、圧縮符号長１１ビットでの総枝数Ｂ（Ｌ）は、１２１６×２0＝１２１６となる。
【０２０１】
このあと、コンピュータ１１００は、ｊをインクリメントし、圧縮符号長ＣＬをデクリメントして（ステップＳ４００６）、ステップＳ４００３に戻り、インクリメント後のｊがｊ＞Ｄであるか否かが判断される。なお、Ｎ＝１１の場合は、ｊ＝Ｄになるとｊ＝Ｄ＝５となり、ＣＬ＝Ｍ＝６となる。したがって、ステップＳ４００４では、圧縮符号長ＣＬ（５ビット）の葉当たりの枝数ｂ（６）は、ｂ（６）＝２6＝６４となる。同様に、総枝数Ｂ（Ｌ）は、Ｂ（６）＝０×２6＝０となる。そして、ｊ＞Ｄである場合（ステップＳ４００３：Ｙｅｓ）、構築処理（ステップＳ３９０５）に移行する。
【０２０２】
図４１は、図３９に示した構築処理（ステップＳ３９０５）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、圧縮符号長ＣＬをＣＬ＝ＣＬｍｉｎ＝Ｍとする（ステップＳ４１０１）。つぎに、コンピュータ１１００は、圧縮符号長ＣＬでの未選択の葉があるか否かを判断する（ステップＳ４１０２）。未選択の葉がある場合（ステップＳ４１０２：Ｙｅｓ）、コンピュータ１１００は、葉へのポインタ生成処理（ステップＳ４１０３）を実行して、ステップＳ４１０２に戻る。葉へのポインタ生成処理（ステップＳ４１０３）では、葉の構造体ごとに、圧縮符号長ＣＬに応じた枝数分の葉へのポインタ群を生成する。なお、葉へのポインタ生成処理（ステップＳ４１０３）の詳細は図４２で説明する。
【０２０３】
一方、ステップＳ４１０２において、未選択の葉がない場合（ステップＳ４１０２：Ｎｏ）、コンピュータ１１００は、ＣＬ＞Ｎであるか否かを判断する（ステップＳ４１０４）。ＣＬ＞Ｎでない場合（ステップＳ４１０４：Ｎｏ）、コンピュータ１１００は、ＣＬをインクリメントして（ステップＳ４１０５）、ステップＳ４１０２に戻る。一方、ＣＬ＞Ｎである場合（ステップＳ４１０４：Ｙｅｓ）、２N分枝無節点ハフマン木Ｈが構築されたこととなり、ステップＳ２５０５に移行することとなる。なお、第１領域〜第５領域内の情報は、この構築処理（ステップＳ３９０５）において格納されることとなる。
【０２０４】
図４２は、図４１に示した葉へのポインタ生成処理（ステップＳ４１０３）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、未選択の葉Ｌを選択し（ステップＳ４２０１）、選択葉へのポインタ数ｋをｋ＝１に設定する（ステップＳ４２０２）。そして、コンピュータ１１００は、選択葉へのポインタＰＬ（ｋ）の先行ビット列を、選択葉の圧縮符号に設定する（ステップＳ４２０３）。たとえば、上限長Ｎ＝１１については、選択葉が、文字情報「０」の葉の構造体である場合、圧縮符号は「００００００」である。したがって、選択葉へのポインタＰＬ（ｋ）の先行ビット列も、「００００００」となる。
【０２０５】
つぎに、コンピュータ１１００は、選択葉へのポインタＰＬ（ｋ）の後続ビット列のビット長を、最大圧縮符号長Ｎから選択葉の圧縮符号長ＣＬを引いた差分とし、後続ビット列の初期値をオール０に設定する（ステップＳ４２０４）。たとえば、選択葉が、文字情報「０」の葉の構造体である場合、圧縮符号長ＣＬは６ビットであるため、後続ビット列のビット長は５ビット（＝１１−６）となる。ｋ＝１の場合は、後続ビット列はオール０となるため、後続ビット列は、５ビットの「０００００」となる。
【０２０６】
そして、コンピュータ１１００は、選択葉へのポインタＰＬ（ｋ）を根の構造体に格納する（ステップＳ４２０５）。このあと、コンピュータ１１００は、ｋ＞ｂ（ＣＬ）であるか否かを判断する（ステップＳ４２０６）。ｂ（ＣＬ）は、選択葉の圧縮符号長ＣＬの葉当たりの枝数である。ｋ＞ｂ（ＣＬ）でない場合（ステップＳ４２０６：Ｎｏ）、選択葉に割り当てられたすべての枝について葉へのポインタが生成されていないため、コンピュータ１１００は、ｋをインクリメントする（ステップＳ４２０７）。
【０２０７】
そして、コンピュータ１１００は、現在の後続ビット列をインクリメントして、インクリメント後の後続ビット列を先行ビット列の末端に連結することで、あらたに、選択葉へのポインタＰＬ（ｋ）を生成する（ステップＳ４２０８）。そして、コンピュータ１１００は、選択葉へのポインタＰＬ（ｋ）を根の構造体に格納し（ステップＳ４２０９）、ステップＳ４２０６に戻る。ステップＳ４２０６〜ステップＳ４２０９を繰り返すことで、葉当たりの枝数分の葉へのポインタ群が生成されることとなる。そして、ステップＳ４２０６において、ｋ＞ｂ（ＣＬ）である場合（ステップＳ４２０６：Ｙｅｓ）、ステップＳ４１０２に移行する。
【０２０８】
このように、対象ファイル群Ｆｓに出現する文字情報の種類数に応じて、２N分枝無節点ハフマン木Ｈの最大枝数２Nを最適な本数に設定することができるため、２N分枝無節点ハフマン木Ｈのサイズの適正化を図ることができる。また、本実施の形態によれば、上限長Ｎが２〜４の整数倍でない場合（たとえば、上限長Ｎ＝１１，１３）であっても、圧縮効率のよい２N分枝無節点ハフマン木Ｈを生成することができる。
【０２０９】
このあと、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈの各葉の構造体と、基礎単語の構造体，特定文字コードの構造体，分割文字コードの構造体とを、図１７の文字情報テーブルを参照して、相互に関連付ける。具体的には、上述したように、葉の構造体には、当該葉に格納されている圧縮符号に対応する特定文字、分割文字コードおよび葉へのポインタや基礎単語へのポインタを格納する。
【０２１０】
また、コンピュータ１１００は、基礎単語の構造体の基礎単語ごとに、対応する圧縮符号を格納する葉へのポインタを格納する。また、コンピュータ１１００は、特定文字コードの構造体の特定文字ごとに、対応する圧縮符号を格納する葉へのポインタを格納する。また、コンピュータ１１００は、分割文字コードの構造体の分割文字コードごとに、対応する圧縮符号を格納する葉へのポインタを格納する。
【０２１１】
（マップ作成処理（ステップＳ２５０５））
図４３は、図２５に示したマップ作成処理（ステップＳ２５０５）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、ファイル番号ｉをｉ＝１に設定し（ステップＳ４３０１）、対象ファイルＦｉを読み込む（ステップＳ４３０２）。そして、コンピュータ１１００は、対象ファイルＦｉのマップ作成処理を実行する（ステップＳ４３０３）。対象ファイルＦｉのマップ作成処理（ステップＳ４３０３）の詳細は、図４４で説明する。このあと、コンピュータ１１００は、ファイル番号ｉがｉ＞α（αは対象ファイルＦｓのファイル総数）であるか否かを判断する（ステップＳ４３０４）。
【０２１２】
ｉ＞αでない場合（ステップＳ４３０４：Ｎｏ）、コンピュータ１１００は、ｉをインクリメントし（ステップＳ４３０５）、ステップＳ４３０２に戻る。一方、ｉ＞αである場合（ステップＳ４３０４：Ｙｅｓ）、マップ作成処理（ステップＳ２５０５）が終了する。このマップ作成処理（ステップＳ２５０５）によれば、対象ファイルＦｉごとに対象ファイルＦｉのマップ作成処理（ステップＳ４３０３）を実行することができる。
【０２１３】
図４４は、図４３に示した対象ファイルＦｉのマップ作成処理（ステップＳ４３０３）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、対象文字を対象ファイルＦｉの先頭文字とし（ステップＳ４４０１）、基礎単語出現マップ作成処理（ステップＳ４４０２）、特定単一文字出現マップ作成処理（ステップＳ４４０３）、２グラム文字列出現マップ作成処理（ステップＳ４４０４）を実行する。
【０２１４】
基礎単語出現マップ作成処理（ステップＳ４４０２）の詳細は図４５で説明する。また、特定単一文字出現マップ作成処理（ステップＳ４４０３）の詳細は図４６で説明する。さらに、２グラム文字列出現マップ作成処理（ステップＳ４４０４）の詳細は図４８で説明する。
【０２１５】
このあと、コンピュータ１１００は、対象文字が対象ファイルＦｉの末尾文字であるか否かを判断する（ステップＳ４４０５）。対象文字が対象ファイルＦｉの末尾文字でない場合（ステップＳ４４０５：Ｎｏ）、コンピュータ１１００は、対象文字を末尾方向へ１文字シフトし（ステップＳ４４０６）、ステップＳ４４０２に戻る。一方、対象文字が対象ファイルＦｉの末尾文字である場合（ステップＳ４４０５：Ｙｅｓ）、ステップＳ４３０４に移行して、対象ファイルＦｉのマップ作成処理（ステップＳ４３０３）を終了する。
【０２１６】
この対象ファイルＦｉのマップ作成処理（ステップＳ４３０３）によれば、基礎単語出現マップ、特定単一文字出現マップおよび２グラム文字列出現マップを、対象文字を１文字ずつシフトしながら、同時並行で生成することができる。
【０２１７】
図４５は、図４４で示した基礎単語出現マップ作成処理（ステップＳ４４０２）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、対象文字について最長一致検索処理を実行する（ステップＳ４５０１）。最長一致検索処理（ステップＳ４５０１）の詳細な処理手順は、図３１に示した最長一致検索処理（ステップＳ２９０１）と同一処理内容であるため説明を省略する。
【０２１８】
そして、コンピュータ１１００は、最長一致した基礎単語、すなわち、基礎単語があるか否かを判断する（ステップＳ４５０２）。最長一致した基礎単語がない場合（ステップＳ４５０２：Ｎｏ）、特定単一文字出現マップ作成処理（ステップＳ４４０３）に移行する。一方、最長一致した基礎単語がある場合（ステップＳ４５０２：Ｙｅｓ）、コンピュータ１１００は、その最長一致した基礎単語について、基礎単語出現マップが設定済みであるか否かを判断する（ステップＳ４５０３）。
【０２１９】
設定済みである場合（ステップＳ４５０３：Ｙｅｓ）、ステップＳ４５０６に移行する。一方、設定済みでない場合（ステップＳ４５０３：Ｎｏ）、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈにおける最長一致した基礎単語の葉にアクセスして、その圧縮符号を取得する（ステップＳ４５０４）。そして、コンピュータ１１００は、取得した圧縮符号を、最長一致した基礎単語についての基礎単語出現マップへのポインタに設定して（ステップＳ４５０５）、ステップＳ４５０６に移行する。このあと、ステップＳ４５０６では、コンピュータ１１００は、最長一致した基礎単語についての基礎単語出現マップの対象ファイルＦｉのビットをＯＮにする（ステップＳ４５０６）。
【０２２０】
これにより、基礎単語出現マップ作成処理（ステップＳ４４０２）を終了し、特定単一文字出現マップ作成処理（ステップＳ４４０３）に移行する。この基礎単語出現マップ作成処理（ステップＳ４４０２）によれば、対象文字ごとに最長一致した基礎単語を基礎単語としてマップ作成することができる。
【０２２１】
図４６は、図４４で示した特定単一文字出現マップ作成処理（ステップＳ４４０３）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、特定単一文字の構造体に対して対象文字の２分探索をおこない（ステップＳ４６０１）、一致したか否かを判断する（ステップＳ４６０２）。一致する単一文字がなかった場合（ステップＳ４６０２：Ｎｏ）、コンピュータ１１００は、分割文字コード出現マップ作成処理を実行して（ステップＳ４６０３）、２グラム文字列出現マップ作成処理（ステップＳ４４０４）に移行する。分割文字コード出現マップ作成処理（ステップＳ４６０３）の詳細は図４７で説明する。
【０２２２】
一方、ステップＳ４６０２において、２分探索により対象文字と一致する単一文字があった場合（ステップＳ４６０２：Ｙｅｓ）、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈにおける２分探索された単一文字の葉にアクセスして、その圧縮符号を取得する（ステップＳ４６０４）。そして、コンピュータ１１００は、その取得された圧縮符号について、特定単一文字出現マップが設定済みであるか否かを判断する（ステップＳ４６０５）。設定済みである場合（ステップＳ４６０５：Ｙｅｓ）、ステップＳ４６０７に移行する。
【０２２３】
一方、設定済みでない場合（ステップＳ４６０５：Ｎｏ）、コンピュータ１１００は、取得した圧縮符号を、２分探索された単一文字についての特定単一文字出現マップへのポインタに設定して（ステップＳ４６０６）、ステップＳ４６０７に移行する。このあと、ステップＳ４６０７では、２分探索された単一文字についての特定単一文字出現マップの対象ファイルＦｉのビットをＯＮにする（ステップＳ４６０７）。
【０２２４】
これにより、特定単一文字出現マップ作成処理（ステップＳ４４０３）を終了し、２グラム文字列出現マップ作成処理（ステップＳ４４０４）に移行する。この特定単一文字出現マップ作成処理（ステップＳ４４０３）によれば、２分探索された対象文字を特定単一文字としてマップ作成することができる。
【０２２５】
図４７は、図４６で示した分割文字コード出現マップ作成処理（ステップＳ４６０３）の詳細な処理手順例を示すフローチャートである。まず、コンピュータ１１００は、対象文字を分割し（ステップＳ４７０１）、２N分枝無節点ハフマン木Ｈにおける上位分割文字コードの葉にアクセスして、圧縮符号を取得する（ステップＳ４７０２）。そして、コンピュータ１１００は、その取得された圧縮符号について、上位分割文字コード出現マップが設定済みであるか否かを判断する（ステップＳ４７０３）。
【０２２６】
設定済みである場合（ステップＳ４７０３：Ｙｅｓ）、ステップＳ４７０５に移行する。一方、設定済みでない場合（ステップＳ４７０３：Ｎｏ）、コンピュータ１１００は、取得した圧縮符号を、上位分割文字コードの出現マップへのポインタに設定して（ステップＳ４７０４）、ステップＳ４７０５に移行する。このあと、ステップＳ４７０５では、コンピュータ１１００は、対象文字から分割された上位分割文字コードの出現マップの対象ファイルＦｉのビットをＯＮにする（ステップＳ４７０５）。
【０２２７】
また、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈにおける下位分割文字コードの葉にアクセスして、圧縮符号を取得する（ステップＳ４７０６）。そして、コンピュータ１１００は、その取得された圧縮符号について、下位分割文字コードの出現マップが設定済みであるか否かを判断する（ステップＳ４７０７）。設定済みである場合（ステップＳ４７０７：Ｙｅｓ）、ステップＳ４７０９に移行する。
【０２２８】
一方、設定済みでない場合（ステップＳ４７０７：Ｎｏ）、コンピュータ１１００は、取得した圧縮符号を、下位分割文字コードの出現マップへのポインタに設定して（ステップＳ４７０８）、ステップＳ４７０９に移行する。このあと、ステップＳ４７０９では、コンピュータ１１００は、対象文字から分割された下位分割文字コードの出現マップの対象ファイルＦｉのビットをＯＮにする（ステップＳ４７０９）。
【０２２９】
これにより、分割文字コード出現マップ作成処理（ステップＳ４６０３）を終了し、２グラム文字列出現マップ作成処理（ステップＳ４４０４）に移行する。この分割文字コード出現マップ作成処理（ステップＳ４６０３）によれば、目標出現率Ｐｃに応じた順位よりも下位の単一文字については、出現頻度が低いため、ＯＦＦのビットが多数出現することとなる。
【０２３０】
しかしながら、目標出現率Ｐｃに応じた順位よりも下位の単一文字については特定単一文字の出現マップの生成対象外とすることで、特定単一文字の圧縮符号マップＭｓのマップサイズの最適化を図ることができる。また、分割することで、目標出現率Ｐｃに応じた順位よりも下位の単一文字については、上位分割文字コードの圧縮符号マップＭｓおよび下位分割文字コードの圧縮符号マップＭｓといったマップサイズが固定化されたマップに設定される。したがって、目標出現率Ｐｃをどのような出現率に設定しても、マップサイズの増大化を防止でき、省メモリ化を図ることができる。
【０２３１】
図４８は、図４４に示した２グラム文字列マップ作成処理（ステップＳ４４０４）の詳細な処理手順例を示すフローチャートである。図４８において、まず、コンピュータ１１００は、２グラム文字列特定処理を実行する（ステップＳ４８０１）。２グラム文字列特定処理（ステップＳ４８０１）の詳細な処理手順は、図３７に示した２グラム文字列特定処理（ステップＳ４８０６）と同一処理内容であるため説明を省略する。
【０２３２】
つぎに、コンピュータ１１００は、２グラム文字列特定処理（ステップＳ４８０１）により２グラム文字列が特定されたか否かを判断する（ステップＳ４８０２）。特定されなかった場合（ステップＳ４８０２：Ｎｏ）、図４４のステップＳ４４０５に移行する。
【０２３３】
一方、特定された場合（ステップＳ４８０２：Ｙｅｓ）、コンピュータ１１００は、２グラム文字列出現マップ生成処理を実行して（ステップＳ４８０３）、ステップＳ４４０５に移行する。
【０２３４】
図４９は、２グラム文字列出現マップ生成処理（ステップＳ４８０３）の詳細な処理手順例を示すフローチャートである。図４９において、まず、コンピュータ１１００は、図４８の２グラム文字列特定処理（ステップＳ４８０１）で特定された２グラム文字列の第１グラム（特定単一文字または分割文字コード）について、２N分枝無節点ハフマン木Ｈの葉にアクセスして、圧縮符号を取得する（ステップＳ４９０１）。同様に、コンピュータ１１００は、第２グラム（特定単一文字または分割文字コード）について、２N分枝無節点ハフマン木Ｈの葉にアクセスして、圧縮符号を取得する（ステップＳ４９０２）。
【０２３５】
そして、コンピュータ１１００は、第１グラムの圧縮符号と第２グラムの圧縮符号を連結する（ステップＳ４９０３）。そして、コンピュータ１１００は、連結圧縮符号をポインタとする出現マップが設定済みであるか否かを判断する（ステップＳ４９０４）。設定済みである場合（ステップＳ４９０４：Ｙｅｓ）、ステップＳ４９０６に移行する。
【０２３６】
一方、設定済みでない場合（ステップＳ４９０４：Ｎｏ）、コンピュータ１１００は、連結圧縮符号を、特定された２グラム文字列の出現マップへのポインタに設定する（ステップＳ４９０５）。このあと、ステップＳ４９０６では、コンピュータ１１００は、特定された２グラム文字列の出現マップの対象ファイルＦｉのビットをＯＮにする（ステップＳ４９０６）。
【０２３７】
これにより、２グラム文字列出現マップ生成処理（ステップＳ４８０３）を終了し、ステップＳ４４０５に移行する。この２グラム文字列出現マップ生成処理（ステップＳ４８０３）によれば、２グラム文字列の連結圧縮符号により、２グラム文字列の出現マップを直接指定することができる。
【０２３８】
＜圧縮処理の具体例＞
つぎに、対象ファイルＦｉの圧縮処理の具体例について説明する。上述のように、圧縮符号マップＭｓを生成した場合は、検索文字列を圧縮した圧縮符号列により圧縮符号マップＭｓ内の出現マップをポイントすることが可能となる。以下、圧縮処理の具体例について説明する。
【０２３９】
図５０は、２N分枝無節点ハフマン木Ｈを用いた圧縮処理の具体例を示す説明図である。まず、コンピュータ１１００は、対象ファイル群Ｆｓから１文字目の圧縮対象文字コードを取得し、対象ファイルＦｉ上の位置を保持しておく。そして、コンピュータ１１００は、基礎単語の構造体２３００に対して２分木探索をおこなう。基礎単語は２文字以上の文字コード列であるため、１文字目の圧縮対象文字コードがヒットした場合、２文字目の文字コードを圧縮対象文字コードとして取得する。
【０２４０】
そして、２文字目の文字コードは、１文字目の圧縮対象文字コードがヒットした位置から探索する。３文字目以降も、不一致の圧縮対象文字コードが出現するまで繰り返し２分木探索をおこなう。一致する基礎単語ｒａ（ａは葉の番号）が探索された場合、基礎単語の構造体２３００において対応付けされている葉Ｌａへのポインタにより葉Ｌａの構造体にアクセスする。そして、コンピュータ１１００は、アクセス先の葉Ｌａの構造体に格納されている基礎単語ｒａの圧縮符号を探索して、圧縮バッファ５０００に格納する。
【０２４１】
一方、不一致の圧縮文字コードが出現した場合、基礎単語の構造体２３００に対する２分木探索を終了する（ＥＯＴ（Ｅｎｄ  Ｏｆ  Ｔｒａｎｓｍｉｓｓｉｏｎ）まで進む）。そして、コンピュータ１１００は、１文字目の圧縮対象文字コードを再度レジスタにセットして、特定単一文字の構造体２１００に対する２分木探索をおこなう。
【０２４２】
一致する文字コードｅｂ（ｂは葉の番号）が探索された場合、コンピュータ１１００は、その葉Ｌｂへのポインタにより葉Ｌｂの構造体にアクセスする。そして、コンピュータ１１００は、アクセス先の葉Ｌｂの構造体に格納されている文字コードｅｂの圧縮符号を探索して、圧縮バッファ５０００に格納する。
【０２４３】
一方、一致する文字コードが出現せず２分木探索を終了した場合、圧縮対象文字コードは特定単一文字コードではないため、コンピュータ１１００は、上位８ビットと下位８ビットに分割する。そして、コンピュータ１１００は、上位８ビットの分割文字コードについて、分割文字コードの構造体２２００に対する２分木探索をおこなう。一致する分割文字コードＤｃ１（ｃ１は葉の番号）が探索された場合、コンピュータ１１００は、その葉Ｌｃ１へのポインタにより葉Ｌｃ１の構造体にアクセスする。そして、コンピュータ１１００は、アクセス先の葉Ｌｃ１の構造体に格納されている分割文字コードＤｃ１の圧縮符号を探索して、圧縮バッファ５０００に格納する。
【０２４４】
引き続き、コンピュータ１１００は、下位８ビットの分割文字コードについて、分割文字コードの構造体に対する２分木探索をおこなう。一致する分割文字コードＤｃ２（ｃ２は葉の番号）が探索された場合、コンピュータ１１００は、その葉Ｌｃ２へのポインタにより葉Ｌｃ２の構造体にアクセスする。そして、コンピュータ１１００は、アクセス先の葉Ｌｃ２の構造体に格納されている分割文字コードＤｃ２の圧縮符号を探索して、圧縮バッファ５０００に格納する。これにより、対象ファイルＦｉが圧縮されることとなる。
【０２４５】
＜対象ファイル群Ｆｓの圧縮処理＞
つぎに、第１圧縮部１１０３による対象ファイル群Ｆｓの圧縮処理の処理手順について説明する。
【０２４６】
図５１は、第１圧縮部１１０３による２N分枝無節点ハフマン木Ｈを用いた対象ファイル群Ｆｓの圧縮処理手順例を示すフローチャートである。まず、コンピュータ１１００は、ファイル番号：ｐをｐ＝１とし（ステップＳ５１０１）、対象ファイルＦｐを読み込む（ステップＳ５１０２）。つぎに、コンピュータ１１００は、圧縮処理を実行して（ステップＳ５１０３）、ファイル番号：ｐをインクリメントする（ステップＳ５１０４）。圧縮処理（ステップＳ５１０３）の詳細は図５２で説明する。
【０２４７】
そして、コンピュータ１１００は、ｐ＞αであるか否かを判断する（ステップＳ５１０５）。αは対象ファイル群Ｆｓのファイル総数である。ｐ＞αでない場合（ステップＳ５１０５：Ｎｏ）、ステップＳ５１０２に戻る。一方、ｐ＞αである場合（ステップＳ５１０５：Ｙｅｓ）、対象ファイル群Ｆｓの圧縮処理を終了する。
【０２４８】
図５２は、図５１に示した圧縮処理（ステップＳ５１０３）の詳細な処理手順を示すフローチャート（その１）である。図５２において、まず、コンピュータ１１００は、対象ファイル群Ｆｓに圧縮対象文字コードがあるか否かを判断する（ステップＳ５２０１）。ある場合（ステップＳ５２０１：Ｙｅｓ）、コンピュータ１１００は、圧縮対象文字コードを取得してレジスタにセットする（ステップＳ５２０２）。そして、コンピュータ１１００は、先頭の圧縮対象文字コードか否かを判断する（ステップＳ５２０３）。
【０２４９】
ここで、先頭の圧縮対象文字コードとは、未圧縮の１文字目の文字コードをいう。先頭である場合（ステップＳ５２０３：Ｙｅｓ）、コンピュータ１１００は、その圧縮対象文字コードの対象ファイル群Ｆｓ上の位置（先頭位置）となるポインタを取得し（ステップＳ５２０４）、ステップＳ５２０５に移行する。一方、先頭でない場合（ステップＳ５２０３：Ｎｏ）、先頭位置を取得せずにステップＳ５２０５に移行する。
【０２５０】
そして、コンピュータ１１００は、基礎単語の構造体２３００に対して２分木探索をおこなう（ステップＳ５２０５）。圧縮対象文字コードが一致した場合（ステップＳ５２０６：Ｙｅｓ）、コンピュータ１１００は、連続して一致した文字コード列が基礎単語（の文字コード列）に該当するか否かを判断する（ステップＳ５２０７）。該当しない場合（ステップＳ５２０７：Ｎｏ）、コンピュータ１１００は、ステップＳ５２０２に戻って後続の文字コードを圧縮対象文字コードとして取得する。この場合、後続の文字コードは先頭ではないため、先頭位置は取得しないこととなる。
【０２５１】
一方、ステップＳ５２０７において、基礎単語に該当する場合（ステップＳ５２０７：Ｙｅｓ）、コンピュータ１１００は、該当する基礎単語の葉Ｌ♯へのポインタにより葉Ｌ♯の構造体にアクセスする（ステップＳ５２０８）。そして、コンピュータ１１００は、ポイントされた葉Ｌ♯の構造体に格納されている基礎単語の圧縮符号を抽出する（ステップＳ５２０９）。
【０２５２】
この後、コンピュータ１１００は、抽出された圧縮符号を圧縮バッファ５０００に格納して（ステップＳ５２１０）、ステップＳ５２０１に戻る。このループが基礎単語の圧縮処理の流れとなる。ステップＳ５２０１において、圧縮対象文字コードがない場合（ステップＳ５２０１：Ｎｏ）、コンピュータ１１００は、対象ファイルＦｐから圧縮された圧縮ファイルｆｐを圧縮バッファ５０００からファイル出力して保存する（ステップＳ５２１１）。そして、ステップＳ５１０４に移行する。一方、ステップＳ５２０６において不一致となった場合（ステップＳ５２０６：Ｎｏ）、１６ビットの文字コードの圧縮処理のループに入る。
【０２５３】
図５３は、図５１に示した圧縮処理（ステップＳ５１０３）の詳細な処理手順を示すフローチャート（その２）である。図５３において、コンピュータ１１００は、ステップＳ５２０４で取得された先頭位置のポインタを参照して、対象ファイル群Ｆｓから圧縮対象文字コードを取得してレジスタにセットする（ステップＳ５３０１）。
【０２５４】
つぎに、コンピュータ１１００は、圧縮対象文字コードについて、特定単一文字の構造体２１００に対して２分木探索をおこなう（ステップＳ５３０２）。一致した場合（ステップＳ５３０３：Ｙｅｓ）、コンピュータ１１００は、該当する文字の葉Ｌ♯へのポインタにより葉Ｌ♯の構造体にアクセスする（ステップＳ５３０４）。そして、コンピュータ１１００は、ポイントされた葉Ｌ♯の構造体に格納されている圧縮対象文字コードの圧縮符号を抽出する（ステップＳ５３０５）。
【０２５５】
この後、コンピュータ１１００は、探索された圧縮符号を圧縮バッファ５０００に格納して（ステップＳ５３０６）、ステップＳ５２０１に戻る。このループが１６ビットの文字コードの圧縮処理の流れとなる。一方、ステップＳ５３０３において一致する文字コードが存在しなかった場合（ステップＳ５３０３：Ｎｏ）、分割文字コードの圧縮処理のループに入る。
【０２５６】
図５４は、図５１に示した圧縮処理（ステップＳ５１０３）の詳細な処理手順を示すフローチャート（その３）である。図５４において、まず、コンピュータ１１００は、圧縮対象文字コードを上位８ビットと下位８ビットとに分割し（ステップＳ５４０１）、上位８ビットの分割文字コードを抽出する（ステップＳ５４０２）。そして、コンピュータ１１００は、分割文字コードの構造体２２００に対して２分木探索をおこなう（ステップＳ５４０３）。
【０２５７】
そして、コンピュータ１１００は、探索された分割文字コードの葉Ｌ♯へのポインタにより葉Ｌ♯の構造体にアクセスする（ステップＳ５４０４）。そして、コンピュータ１１００は、ポイントされた葉Ｌ♯の構造体に格納されている分割文字コードの圧縮符号を抽出する（ステップＳ５４０５）。この後、コンピュータ１１００は、探索された圧縮符号を圧縮バッファ５０００に格納する（ステップＳ５４０６）。
【０２５８】
つぎに、コンピュータ１１００は、下位８ビットが探索済みか否かを判断し（ステップＳ５４０７）、探索済みでない場合（ステップＳ５４０７：Ｎｏ）、コンピュータ１１００は、下位８ビットの分割文字コードを抽出して（ステップＳ５４０８）、ステップＳ５４０３〜Ｓ５４０６を実行する。一方、下位８ビットが探索済みである場合（ステップＳ５４０７：Ｙｅｓ）、ステップＳ５３０１に戻り、基礎単語の圧縮処理のループに入る。
【０２５９】
このように、２N分枝無節点ハフマン木Ｈを用いた圧縮処理では、内部節点がないため根に向かって探索する必要はなく、ポイントされた葉Ｌ♯の構造体に格納されている文字情報を抽出して、圧縮バッファ５０００に書き込むだけでよい。したがって、圧縮処理の高速化を図ることができる。
【０２６０】
また、圧縮対象文字コードが格納されている葉Ｌ♯の構造体を、基礎単語の構造体、特定単一文字コードの構造体および分割文字コードの構造体により即座に特定することができる。したがって、２N分枝無節点ハフマン木Ｈの葉を探索する必要がなく、圧縮処理の高速化を図ることができる。また、低位文字コードを上位ビットコードと下位ビットコードに分割することで、非特定単一文字を２５６種の分割文字コードの圧縮符号に圧縮することができる。したがって、圧縮率の向上を図ることができる。
【０２６１】
＜マップ圧縮の具体例＞
つぎに、第２圧縮部１１０６による圧縮符号マップＭｓ内の各出現マップのマップ圧縮の具体例について説明する。第２圧縮部１１０６は、圧縮領域内の出現マップを圧縮し、非圧縮領域の出現マップは圧縮しない。圧縮領域とは、ファイル番号１〜αまで採番されている場合に、ｎ×（α／ｎの商）となるファイル番号までの出現マップのビット列である。たとえば、ｎ＝２５６ビットであり、現在の対象ファイル数α＝６００である場合、α／ｎの商は２となるため、ファイル番号１〜２ｎまでの出現マップのビット列が圧縮領域となる。そして、ファイル番号（２ｎ＋１）〜αまでのビット列は非圧縮領域となり圧縮されない。
【０２６２】
また、出現マップのビット列は、ファイル総数αが増大することで、ビット列内の“０”が連続する箇所も多くなる。また、出現頻度が高い文字情報については、これとは逆に“１”が連続する箇所が多くなる。したがって、文字の出現率に応じた出現率領域を設定する。出現率領域とは、出現率の範囲である。出現率領域に応じて、出現マップ圧縮用のハフマン木ｈを割り当てることとする。
【０２６３】
図５５は、出現率と出現率領域との関係を示す説明図である。出現率が０〜１００％の範囲とすると、図５５に示したように、Ａ〜Ｅ領域およびＡ´〜Ｅ´領域に領域分割することができる。したがって、Ａ〜Ｅ領域およびＡ´〜Ｅ´領域で特定された出現率領域に応じて、出現マップ圧縮用のハフマン木ｈを圧縮パターンとして割り当てる。
【０２６４】
図５６は、出現率領域別の圧縮パターンを有する圧縮パターンテーブルを示す説明図である。出現率は、図２０に示したように、葉Ｌ＃の構造体の第５領域に格納されているため、葉Ｌ＃の構造体が指定されることで、圧縮パターンテーブル５６００を参照して、圧縮パターンが特定されることとなる。なお、Ａ領域およびＡ´領域は、非圧縮のため、圧縮パターンとなるハフマン木は存在しない。
【０２６５】
図５７は、Ｂ領域およびＢ´領域の場合の圧縮パターンを示す説明図である。圧縮パターン５７００は、葉が１６種のハフマン木ｈとなる。
【０２６６】
図５８は、Ｃ領域およびＣ´領域の場合の圧縮パターンを示す説明図である。圧縮パターン５８００は、葉が１６種＋１種のハフマン木ｈとなる。圧縮パターン５８００では、Ｂ領域およびＢ´領域に比べて、“０”が連続する箇所または“１”が連続する箇所が確率的に多くなる。したがって、１６ビット連続して値が“０”であるビット列に、符号語“００”が割り当てられている。
【０２６７】
図５９は、Ｄ領域およびＤ´領域の場合の圧縮パターンを示す説明図である。圧縮パターン５９００は、葉が１６種＋１種のハフマン木となる。圧縮パターン５９００では、Ｃ領域およびＣ´領域に比べて、“０”が連続する箇所または“１”が連続する箇所が確率的に多くなる。したがって、３２ビット連続して値が“０”であるビット列に、符号語“００”が割り当てられている。
【０２６８】
図６０は、Ｅ領域およびＥ´領域の場合の圧縮パターンを示す説明図である。圧縮パターン６０００は、葉が１６種＋１種のハフマン木となる。圧縮パターン６０００では、Ｄ領域およびＤ´領域に比べて、“０”が連続する箇所または“１”が連続する箇所が確率的に多くなる。したがって、６４ビット連続して値が“０”であるビット列に、符号語“００”が割り当てられている。このように、出現率領域に応じて、文字コードが存在しないことを意味する“０”の連続数が増加するため、文字コードの出現率に応じて圧縮符号マップＭｓの圧縮効率の向上を図ることができる。
【０２６９】
（圧縮符号マップ圧縮処理手順）
つぎに、圧縮符号マップ圧縮処理について説明する。圧縮符号マップ圧縮処理は、圧縮領域のビット列を圧縮する処理である。具体的には、図５６に示した圧縮パターンテーブル５６００と図５７〜図６０に示した圧縮パターン５７００〜６０００（ハフマン木ｈ）を用いて、圧縮符号マップＭｓの圧縮領域のビット列を圧縮する。以下、圧縮符号マップ圧縮処理手順について説明する。
【０２７０】
図６１は、圧縮符号マップ圧縮処理手順を示すフローチャートである。図６１において、まず、コンピュータ１１００は、圧縮符号マップＭｓにおいて、未選択の出現マップへのポインタがあるか否かを判断する（ステップＳ６１０１）。未選択のアドレスがある場合（ステップＳ６１０１：Ｙｅｓ）、コンピュータ１１００は、未選択のアドレスを選択して葉Ｌ＃の構造体にアクセスし（ステップＳ６１０２）、葉Ｌ＃の構造体の第１領域の中から文字コードを取得する（ステップＳ６１０３）。そして、コンピュータ１１００は、アクセス先の葉Ｌ＃の構造体の第５領域から出現率領域を取得することで、取得された文字コードの出現率領域を特定する（ステップＳ６１０４）。
【０２７１】
このあと、コンピュータ１１００は、図５９の圧縮パターンテーブル５９００を参照して、特定された出現率領域が非圧縮領域（たとえば、出現率領域Ａ、Ａ´）であるか否かを判断する（ステップＳ６１０５）。非圧縮領域である場合（ステップＳ６１０５：Ｙｅｓ）、ステップＳ６１０１に戻り、つぎのアドレスを選択する。
【０２７２】
一方、非圧縮領域でない場合（ステップＳ６１０５：Ｎｏ）、コンピュータ１１００は、特定された出現率領域により、図５７〜図６０に示した圧縮パターン５７００〜６０００（ハフマン木ｈ）の中から該当する圧縮パターン（ハフマン木ｈ）を選択する（ステップＳ６１０６）。また、コンピュータ１１００は、圧縮対象となる取得文字コードの出現マップにおける圧縮領域のビット列を抽出する（ステップＳ６１０７）。
【０２７３】
そして、コンピュータ１１００は、取得文字コードの出現率が５０％以上であるか否かを判断する（ステップＳ６１０８）。出現率とは、上述したように、対象ファイル群Ｆｓ内の全ファイル数を母集団（分母）とし、当該文字情報が存在するファイル数を分子とした値である。出現率領域は、出現率に応じて決められているため（図５５を参照）、出現率領域がＡ〜Ｅである場合、取得文字コードの出現率が５０％以上でないと判断する。一方、出現率領域がＡ´〜Ｅ´である場合、コンピュータ１１００は、取得文字コードの出現率が５０％以上であると判断する。
【０２７４】
そして、出現率が５０％以上である場合（ステップＳ６１０８：Ｙｅｓ）、コンピュータ１１００は、圧縮効率を上げるために、ステップＳ６１０７で抽出されたビット列を反転する（ステップＳ６１０９）。たとえば、抽出されたビット列が“１１１０”である場合、“０００１”にして、“０”の個数を増やす。そして、コンピュータ１１００は、反転後のビット列を、ステップＳ６１０６で選択したハフマン木を用いて圧縮して、記憶装置（たとえば、フラッシュメモリや磁気ディスク２０５）に格納する（ステップＳ６１１０）。そして、ステップＳ６１０１に戻る。このように、ビット列反転をおこなうことで、出現率領域Ａ´〜Ｅ´のハフマン木ｈを用意する必要がないため、省メモリ化を図ることができる。
【０２７５】
一方、ステップＳ６１０８において、出現率が５０％以上でない場合（ステップＳ６１０８：Ｎｏ）、コンピュータ１１００は、ビット列反転（ステップＳ６１０９）をおこなうことなく、ステップＳ６１０７で抽出されたビット列を、ステップＳ６１０６で選択したハフマン木を用いて圧縮して（ステップＳ６１１０）、ステップＳ６１０１に戻る。また、ステップＳ６１０１において、未選択のアドレスがない場合（ステップＳ６１０１：Ｎｏ）、圧縮符号マップ圧縮処理を終了する。
【０２７６】
このような圧縮符号マップ圧縮処理手順により、図３に示したように、文字情報ごとに圧縮領域内のビット列が、出現率に応じて圧縮される。このように、出現率領域に応じて、文字情報が存在しないことを意味する“０”の連続数が増加するため、文字情報の出現率に応じて圧縮符号マップＭｓの圧縮効率の向上を図ることができる。
【０２７７】
また、対象ファイルが後から追加されると、追加された対象ファイルを圧縮する際、圧縮符号マップＭｓにも文字の存否を示すビット列を追加する必要がある。圧縮前の圧縮符号マップＭｓでは、ファイル番号：１〜αの出現マップのビット列については、圧縮パターン５７００〜６０００により圧縮されてレコードごとに符号長が異なる。すなわち、可変長であるため圧縮領域となる。
【０２７８】
したがって、図３に示したように、圧縮符号列の先頭（ファイル番号ｋ側）は整列するが末尾（ファイル番号１側）が整列しない。仮に、ビット列の並びを、ファイル番号：１〜αの順に、圧縮符号マップＭｓへのポインタ（文字情報の圧縮符号）側から割り当てると、追加ファイルのビット列は、圧縮符号列の末尾側に挿入することとなり、圧縮符号列と追加ファイルのビット列とが非連続となってしまう。したがって、あらかじめ、圧縮符号マップＭｓの圧縮領域のビット列を、先頭位置から末尾位置にかけて対象ファイル群Ｆｓのファイル番号ｐの降順に配列しておく。そして、圧縮符号マップＭｓにおいて、出現マップへのポインタ（文字情報の圧縮符号）と圧縮領域との間に非圧縮領域を設定する。
【０２７９】
図３を例に挙げると、ファイル番号：１〜２ｎ＋１のうち圧縮符号列が整列する側にファイル番号：２ｎ＋１のビットを割り当てる。これにより、ファイル番号；１〜２ｎのビット列を圧縮した場合でも、非圧縮のファイル番号：２ｎ＋１〜３ｎのビット列を挿入しても、ファイル番号順にビット列を連続させることができる。これにより、ファイル番号；１〜２ｎのビット列が圧縮されても、追加ファイルのファイル番号とそのビットとのずれがなく、対象ファイルの絞込みを正確に実行することができる。
【０２８０】
＜機能的構成例２＞
図６２は、本実施の形態にかかるコンピュータまたはコンピュータシステムの機能的構成例２を示すブロック図である。図６２において、コンピュータ１１００は、指定部６２０１と、第１伸長部６２０２と、第１圧縮部１１０３と、入力部６２０３と、抽出部６２０４と、第２伸長部６２０５と、特定部６２０６と、セグメント生成部６２０７と、を備える。指定部６２０１〜セグメント生成部６２０７は、具体的には、たとえば、図９に示したＲＯＭ９０２、ＲＡＭ９０３、磁気ディスク９０５などの記憶装置に記憶されたプログラムをＣＰＵ９０１に実行させることによりその機能を実現する。なお、指定部６２０１〜セグメント生成部６２０７は、それぞれ実行結果を記憶装置に書き込んだり、他の部の実行結果を読み出したりして、それぞれ演算を実行する。以下、指定部６２０１〜セグメント生成部６２０７について簡単に説明する。
【０２８１】
指定部６２０１は、対象ファイル群Ｆｓ内のいずれかの対象ファイルのオープン指定を受け付ける。具体的には、キーボード、マウス、タッチパネルをユーザが操作することで、指定部６２０１は、対象ファイルＦｉのオープン指定を受け付ける。当該オープン指定が受け付けられると、圧縮符号マップＭｓにおいて、オープン指定された対象ファイルＦｉのファイル番号ｉに関連付けられている圧縮ファイルｆｉへのポインタが指定される。これにより、ポイント先となるアドレスに格納されている、オープン指定された対象ファイルＦｉの圧縮ファイルｆｉが読み出される。
【０２８２】
指定部６２０１による指定がマスタサーバにより実行された場合、指定された対象ファイルＦｉのファイル番号ｉを第０階層のセグメント数Ｋで割ったときの商に一致するセグメント番号のセグメントを特定する。これにより、特定されたセグメントから圧縮ファイルｆｉを指定することができる。
【０２８３】
また、指定部６２０１は、対象ファイルＦｉの追加指定を受け付ける。具体的には、キーボード、マウス、タッチパネルをユーザが操作することで、指定部６２０１は、対象ファイルＦｉの追加指定を受け付ける。当該追加指定が受け付けられると、追加指定された対象ファイルＦｉが第１圧縮部１１０３により２N分枝無節点ハフマン木Ｈで圧縮され、圧縮ファイルｆｉとして、第０階層の最後尾のセグメントに保存される。
【０２８４】
また、指定部６２０１は、セグメントの集約指定を受け付ける。具体的には、キーボード、マウス、タッチパネルをユーザが操作することで、指定部６２０１は、セグメントの集約指定を受け付ける。また、セグメントの集約指定は、タイマにより所定時刻または所定時間単位で受け付けてもよい。
【０２８５】
第１伸長部６２０２は、対象ファイルＦｉの圧縮ファイルｆｉを、２N分枝無節点ハフマン木Ｈで伸長する。具体的には、たとえば、第１伸長部６２０２は、指定部６２０１によってオープン指定された対象ファイルＦｉの圧縮ファイルｆｉを、２N分枝無節点ハフマン木Ｈで伸長する。また、後述する特定部６２０６で特定された対象ファイルＦｉについても２N分枝無節点ハフマン木Ｈで伸長する。伸長の具体例については後述する。
【０２８６】
入力部６２０３は、検索文字列の入力を受け付ける。具体的には、キーボード、マウス、タッチパネルをユーザが操作することで、入力部６２０３は、検索文字列の入力を受け付ける。また、入力部６２０３は、ネットワークを介してクライアント装置から検索文字列を受信することで、検索文字列の入力を受け付ける。
【０２８７】
抽出部６２０４は、入力部６２０３によって入力された検索文字列内の文字情報の圧縮符号を２N分枝無節点ハフマン木Ｈから抽出する。具体的には、たとえば、抽出部６２０４は、検索文字列から、特定単一文字、上位分割文字コード、下位分割文字コード、２グラム文字列、および基礎単語のうち該当する文字情報を抽出する。
【０２８８】
たとえば、検索文字列が「人形」である場合、特定単一文字「人」、「形」と、２グラム文字列「人形」が抽出される。これにより、抽出部６２０４は、抽出された文字情報の圧縮符号を２N分枝無節点ハフマン木Ｈで特定し、圧縮符号マップＭｓの該当する出現マップをポイントすることができる。たとえば、特定単一文字「人」の圧縮済みの出現マップと、「形」の圧縮済みの出現マップと、２グラム文字列「人形」の圧縮済みの出現マップとをポイントすることができる。
【０２８９】
図７に示したコンピュータシステムでは、マスタサーバＭＳが抽出部６２０４による文字情報の抽出をおこない、２N分枝無節点ハフマン木Ｈで抽出文字情報の圧縮符号を取得する。取得された圧縮符号は、出現マップへのポインタとなるため、スレーブサーバＳ１，Ｓ２，…に送信される。
【０２９０】
第２伸長部６２０５は、抽出部６２０４によって抽出された圧縮済みの出現マップを伸長する。具体的には、文字情報の出現率から出現率領域が特定できるため、第２伸長部６２０５は、特定された出現率領域に応じたマップ用のハフマン木により、圧縮済みの出現マップの圧縮領域を伸長する。たとえば、上記の例では、すべてのアーカイブファイル（図７を参照）において、特定単一文字「人」の圧縮済みの出現マップと、「形」の圧縮済みの出現マップと、２グラム文字列「人形」の圧縮済みの出現マップとが、伸長される。
【０２９１】
図７に示したコンピュータシステムでは、マスタサーバＭＳおよびスレーブサーバＳ１，Ｓ２，…の各々で、第２伸長部６２０５による伸長処理が実行されることになる。
【０２９２】
特定部６２０６は、第２伸長部６２０５による伸長後の出現マップ群および削除マップＤのＡＮＤ演算を実行することで、検索文字列内の文字情報を含む対象ファイルの圧縮ファイルを圧縮ファイル群から特定する。上記の例では、特定部６２０６は、特定単一文字「人」の圧縮済みの出現マップと、「形」の圧縮済みの出現マップと、２グラム文字列「人形」の圧縮済みの出現マップと、削除マップと、をＡＮＤ演算する。
【０２９３】
このＡＮＤ演算は、図８に示したように、最上位階層のセグメントから実行され、最終的に第０階層のセグメントに絞り込まれ、絞り込まれた第０階層のセグメントでＡＮＤ演算が実行される。なお、図８では簡略化のため、２グラム文字列「人形」の圧縮済みの出現マップは省略されている。
【０２９４】
図７に示したコンピュータシステムでは、マスタサーバＭＳは、最上位階層から第１階層のセグメントについて特定部６２０６による絞込みをおこない、検索文字列を含む対象ファイルのファイル番号を、当該ファイル番号を管理するスレーブサーバに送信する。ファイル番号を受信したスレーブサーバは、特定部６２０６による特定処理により、出現マップおよび削除マップでＡＮＤ演算することで、圧縮ファイルを絞り込むことになる。
【０２９５】
これにより、図８に示したように、ファイル番号３，１９（の圧縮ファイルｆ３，ｆ１９）が特定される。第１伸長部６２０２では、特定部６２０６によって特定された圧縮ファイル（上記の例では圧縮ファイルｆ３，ｆ１９）を２N分枝無節点ハフマン木Ｈで伸長することとなる。
【０２９６】
このあと、スレーブサーバで絞り込まれた圧縮ファイルは、マスタサーバＭＳに送信される。マスタサーバＭＳは、スレーブサーバからの圧縮ファイルを、第１伸長部６２０２により２N分枝無節点ハフマン木Ｈで伸長する。伸長された対象ファイル（上記の例ではＦ３、Ｆ１９）は、ディスプレイなどの表示装置に表示される。また、検索文字列がクライアント装置から受け付けられている場合は、マスタサーバＭＳがクライアント装置に、検索結果として伸長された対象ファイル（上記の例ではＦ３、Ｆ１９）を送信することになる。また、特定部６２０６において圧縮ファイルが特定されなかった場合は、その旨の検索結果を返すことになる。
【０２９７】
セグメント生成部６２０７は、対象ファイルの追加指定が受け付けられると、現在のファイル総数αが１セグメントあたりのファイル数ｎの倍数であるか否かを判断する。ｎの倍数である場合は、最後尾のセグメントには追加指定された対象ファイルの圧縮ファイルを保存できる空き領域がないため、あらたに第０階層のセグメントを生成する。セグメントがあらたに生成されると、図１や図６に示したように、管理領域間での関連付けをおこなう。そして、あらたなセグメントに対し追加される圧縮ファイルが順次格納されることになる。
【０２９８】
セグメント生成部６２０７を実行するコンピュータがマスタサーバＭＳの場合は、最後尾のセグメントを有するスレーブサーバに対し、第０階層のあらたなセグメントの生成指示を送信する。また、最後尾のセグメントを保持するスレーブサーバに、あらたなセグメントを保持する空き領域がない場合は、他のスレーブサーバに第０階層のあらたなセグメントの生成指示を送信する。そして、あらたなセグメントが生成されると、マスタサーバＭＳは、追加された圧縮ファイルを順次送信することとなる。これにより、あらたなセグメントに、追加された圧縮ファイルが順次格納されることになる。
【０２９９】
また、セグメント生成部６２０７は、出現マップや削除マップの集約をおこなう。具体的には、たとえば、セグメント生成部６２０７は、図４に示したように、出現マップごとに、上位階層への集約をおこなう。そして、セグメント生成部６２０７は、図４に示したように、集約先の上位階層のセグメント（たとえば、セグメントｓｇ１（１））の管理領域と、集約元の上位階層のセグメント群（たとえば、セグメントｓｇ０（１）〜ｓｇ０（ｍ））の各管理領域との間での関連付けをおこなう。この集約処理は削除マップについても同様に実行される。
【０３００】
＜ファイル伸長例＞
図６３は、ファイル伸長例を示す説明図である。ファイル伸長例で示す処理は、入力部６２０３、抽出部６２０４、第２伸長部６２０５、特定部６２０６、第１伸長部６２０２により実行される。（Ｇ１）まず、入力部６２０３により検索文字列「人形」が入力された場合、検索文字列「人形」を構成する文字「人」、「形」について特定単一文字の構造体２１００に対し２分探索することで、特定単一文字「人」、「形」が検索される。特定単一文字の構造体２１００には、２N分枝無節点ハフマン木Ｈの葉（特定単一文字）へのポインタが関連付けられている。したがって、特定単一文字の構造体でヒットすると、２N分枝無節点ハフマン木Ｈの葉を直接指定することができる。
【０３０１】
（Ｇ２）２N分枝無節点ハフマン木Ｈの葉を直接指定すると、当該葉の構造体内の照合フラグがＯＮに設定され、圧縮符号が抽出される。圧縮符号は特定単一文字の出現マップへのポインタとなるため、直接指定することができる。本例の場合、特定単一文字「人」、「形」の圧縮符号が抽出されるため、「人」の出現マップと「形」の出現マップとが抽出される。また、「人」の圧縮符号および「形」の圧縮符号を連結した連結圧縮符号も２グラム文字列の出現マップへのポインタとなるため、直接指定することができる。したがって、２グラム文字列「人形」の出現マップも抽出される。
【０３０２】
（Ｇ３）抽出された３個の出現マップは、マップ用ハフマン木により伸長される。このあと、図８に示したように、特定部６２０６が、最上位階層のセグメントから絞込みを行って、セグメントｓｇ０（１）において、伸長された出現マップと削除マップとによりＡＮＤ演算を実行して、ＡＮＤ結果が得られる。
【０３０３】
（Ｇ４）セグメントｓｇ０（１）のＡＮＤ結果においてファイル番号３がＯＮになっているため、検索文字列「人形」が対象ファイルＦ３に存在することが判明する。したがって、圧縮ファイル群ｆｓから圧縮ファイルｆ３が抽出される。これにより伸長すべき圧縮ファイルが絞り込まれることになり、無駄な伸長処理を低減することができる。
【０３０４】
（Ｇ５）最後に、抽出された圧縮ファイルｆ３を圧縮状態のまま、照合、伸長することで、伸長後の対象ファイルＦ３がオープンされる。なお、「人」、「形」の葉の構造体では照合フラグがＯＮになっているため、「人」、「形」の伸長の際、強調表示となるように文字列置換されて伸長される。たとえば、照合フラグがＯＮである「人」、「形」については、＜Ｂ＞＜／Ｂ＞タグではさんで伸長することで、太字で表示される。照合フラグがＯＦＦの文字については＜Ｂ＞＜／Ｂ＞タグではさむことなくそのまま伸長する。
【０３０５】
＜伸長処理の具体例＞
つぎに、図６３での伸長処理の具体例について説明する。ここでは、検索文字列「人形」の圧縮符号列を用いて圧縮ファイルｆｉについて照合しながら伸張する例について説明する。なお、例として、特定単一文字「人」の圧縮符号を「１１０００１００１１」（１０ビット）とし、特定単一文字「形」の圧縮符号を「０１０００１００１０」（１０ビット）とする。
【０３０６】
また、伸長処理では、レジスタに圧縮符号列をセットし、マスクパターンにより圧縮符号を抽出する。抽出した圧縮符号を、１パス（１枝分のアクセス）で２N分枝無節点ハフマン木Ｈの根から探索する。そして、アクセスした葉Ｌ♯の構造体に格納されている文字コードを読み出して伸長バッファに格納する。
【０３０７】
また、圧縮符号を抽出するため、マスクパターンのマスク位置をオフセットする。また、マスクパターンの初期値を“０ｘＦＦＦ０００００”とする。このマスクパターンは先頭１２ビットが“１”であり、後続の２０ビットが“０”のビット列である。
【０３０８】
図６４および図６５は、図６３での伸長処理の具体例を示す説明図である。図６４では、特定単一文字「人」についての伸張例（Ａ）を示している。図６４において、まず、ＣＰＵは、ビットアドレスａｂｉとバイトオフセットｂｙｏｓとビットオフセットｂｉｏｓとを算出する。ビットアドレスａｂｉは、抽出された圧縮符号のビット位置を示す値であり、今回のビットアドレスａｂｉは、前回のビットアドレスａｂｉに前回抽出された圧縮符号の圧縮符号長ｌｅｇを加算した値となる。なお、初期状態では、ビットアドレスａｂｉはａｂｉ＝０とする。
【０３０９】
バイトオフセットｂｙｏｓは、メモリに保持されている圧縮符号列のバイト境界を示す値であり、ビットアドレスａｂｉ／８の商で求められる。たとえば、バイトオフセットｂｙｏｓ＝０のときは、メモリに記憶されている先頭からの圧縮符号列をレジスタにセットし、バイトオフセットｂｙｏｓ＝１のときは、メモリに記憶されている先頭１バイト目からの圧縮符号列をレジスタにセットする。
【０３１０】
また、ビットオフセットｂｉｏｓは、マスクパターンのマスク位置（“ＦＦＦ”）をオフセットする値であり、ビットアドレスａｂｉ／８の余りである。たとえば、ビットオフセットｂｉｏｓ＝０のときは、マスク位置はシフトされないこととなり、マスクパターンは、“０ｘＦＦＦ０００００”となる。一方、ビットオフセットｂｉｏｓ＝４のときは、マスク位置は末尾方向に４ビットシフトすることとなり、マスクパターンは、“０ｘ０ＦＦＦ００００”となる。
【０３１１】
レジスタシフト数ｒｓは、マスクパターンとのＡＮＤ演算後のレジスタ内の圧縮符号列を末尾方向にシフトするビット数であり、ｒｓ＝３２−１２−ｂｉｏｓで求められる。このシフトにより、シフト後のレジスタの末尾ｍビットのビット列を対象ビット列として抽出する。対象ビット列の抽出後はレジスタをクリアする。
【０３１２】
なお、メモリ内のブロックは１バイトのビット列を示しており、内部の数字は、バイト境界となるバイト位置を示している。図６４では、ビットアドレスａｂｉ＝０により、バイトオフセットｂｙｏｓ＝０、ビットオフセットｂｉｏｓ＝０となる。バイトオフセットｂｙｏｓ＝０により、メモリに保持されている圧縮符号列のうち先頭から４バイト分（図中、網掛け）の圧縮符号列をレジスタにセットする。
【０３１３】
また、ビットオフセットｂｉｏｓ＝０により、マスクパターンは、“０ｘＦＦＦ０００００”である。したがって、レジスタにセットされた圧縮符号列とマスクパターン“０ｘＦＦＦ０００００”を論理積（ＡＮＤ）演算することにより、ＡＮＤ結果が得られる。
【０３１４】
また、ビットオフセットｂｉｏｓ＝０により、レジスタシフト数ｒｓは、ｒｓ＝３２−ｍ―ｂｉｏｓ＝３２−１２−０＝２０となる。したがって、レジスタ内のＡＮＤ結果を末尾方向に２０ビット分シフトする。このシフトによりレジスタには、“１１０００１００１１００”が残されるため、末尾１２ビットを対象ビット列として抽出する。この場合は、“１１０００１００１１００”が対象ビット列として抽出される。抽出後、レジスタはクリアされる。
【０３１５】
２N分枝無節点ハフマン木Ｈの根の構造体には、抽出された対象ビット列“１１０００１００１１００”があるため、この対象ビット列と一致する葉Ｌ♯へのポインタ（枝番号）を探索する。この場合、葉Ｌ９７へのポインタ群の中の１つと一致するため、該当する葉Ｌ９７へのポインタを読み出して、葉Ｌ９７の構造体にアクセスする。
【０３１６】
葉Ｌ９７の構造体には、文字コード“０ｘＢＡ４Ｅ”が格納されているため、当該文字コード“０ｘＢＡ４Ｅ”を抽出して伸長バッファに格納する。この場合、照合フラグがＯＮであるため、文字コード“０ｘＢＡ４Ｅ”を＜Ｂ＞＜／Ｂ＞タグで挟み込んで格納する。
【０３１７】
また、葉Ｌ９７の構造体には、文字コード“０ｘＢＡ４Ｅ”の圧縮符号長ｌｅｇ（＝１０ビット）も格納されているため、文字コード“０ｘＢＡ４Ｅ”の圧縮符号長ｌｅｇも抽出する。この抽出された圧縮符号長ｌｅｇによりビットアドレスａｂｉを更新する。この場合、更新後のビットアドレスａｂｉはａｂｉ＝０＋１０＝１０となる。
【０３１８】
図６５では、特定単一文字「形」について伸張する例（Ｂ）を示している。具体的には、図６４の状態（Ａ）からレジスタをバイトオフセットｂｉｏｓ分シフトした場合、前回である（Ａ）のビットアドレスａｂｉはａｂｉ＝０、圧縮符号長ｌｅｇは１０ビットであるため、（Ｂ）のビットアドレスａｂｉはａｂｉ＝１０ビットとなる。
【０３１９】
また、このビットアドレスａｂｉ＝１０により、バイトオフセットｂｙｏｓ＝１、ビットオフセットｂｉｏｓ＝２となる。バイトオフセットｂｙｏｓ＝１により、メモリに保持されている圧縮符号列のうち先頭１バイト目から４バイト分（図中、網掛け）の圧縮符号列をレジスタにセットする。
【０３２０】
また、ビットオフセットｂｉｏｓ＝２により、マスクパターンは、“０ｘ３ＦＦＣ００００”である。したがって、レジスタにセットされた圧縮符号列とマスクパターン“０ｘ３ＦＦＣ００００”を論理積（ＡＮＤ）演算することにより、ＡＮＤ結果が得られる。
【０３２１】
また、ビットオフセットｂｉｏｓ＝２により、レジスタシフト数ｒｓは、ｒｓ＝３２−ｍ−ｂｉｏｓ＝３２−１２−２＝１８となる。したがって、レジスタ内のＡＮＤ結果を末尾方向に１８ビット分シフトする。このシフトによりレジスタには、“０００００１０００１００１０”が残されるため、末尾１０ビットを対象ビット列として抽出する。この場合は、“０１０００１００１０”が対象ビット列として抽出される。抽出後、レジスタはクリアされる。
【０３２２】
２N分枝無節点ハフマン木Ｈの根の構造体には、抽出された対象ビット列“０１０００１００１０”があるため、このビット列と一致する葉Ｌ♯へのポインタ（枝番号）を探索する。この場合、対象ビット列“０１０００１００１０”が葉Ｌ１０５へのポインタ群の中の１つと一致するため、該当する葉Ｌ１０５へのポインタを読み出して、葉Ｌ２４の構造体にアクセスする。
【０３２３】
葉Ｌ１０５の構造体には、文字コード“０ｘ６２５Ｆ”が格納されているため、当該文字コード“０ｘ６２５Ｆ”を抽出して伸長バッファに格納する。ファイル伸長例（Ｇ１）の場合は、そのまま伸長バッファに格納するが、ファイル伸長例（Ｇ２）の場合は、照合フラグがＯＮであるため、文字コード“０ｘ６２５Ｆ”を＜Ｂ＞＜／Ｂ＞タグで挟み込んで格納する。また、葉Ｌ１０５の構造体には、文字コード“０ｘ６２５Ｆ”の圧縮符号長ｌｅｇ（＝８ビット）も格納されているため、文字コード“０ｘ６２５Ｆ”の圧縮符号長ｌｅｇも抽出する。この抽出された圧縮符号長ｌｅｇによりビットアドレスａｂｉを更新する。この場合、更新後のビットアドレスａｂｉはａｂｉ＝１０＋８＝１８となる。このようにして伸長することで、対象ファイルがオープンされることとなる。
【０３２４】
＜ファイル追加処理の具体例＞
つぎに、ファイル追加処理の具体例について説明する。ここでは、圧縮済みの圧縮符号マップＭｓを伸長することなく、セグメント生成部６２０７が、追加対象となる対象ファイルＦ（ｎ＋１）の追加と、圧縮符号マップＭｓの更新とを実行する。
【０３２５】
図６６は、ファイル追加処理の具体例を示す説明図である。図６６では、対象ファイルＦ（ｎ＋１）を追加する場合を例に挙げて説明する。まず、図６３のファイル伸長例により、圧縮ファイル群ｆｓから圧縮ファイルｆ３が伸長され、伸長後の対象ファイルＦ３がメインメモリ（たとえば、ＲＡＭ９０３）上に書き出されたとする。ここで、対象ファイルＦ（ｎ＋１）に変更し、新規保存指示を与えたとする。この場合、メインメモリ上の対象ファイルＦ（ｎ＋１）にはあたらしく採番されたファイル番号ｎ＋１が割り与えられる。すなわち、セグメントｓｇ０（１）には空き領域がないため、セグメントｓｇ０（２）が設定され、セグメントｓｇ０（１）との間で関連付けがおこなわれる。
【０３２６】
（Ｉ）そして、対象ファイルＦ（ｎ＋１）を２N分枝無節点ハフマン木Ｈで圧縮して圧縮ファイルｆ（ｎ＋１）とし、セグメントｓｇ０（２）に保存する。（Ｊ）また、メインメモリ上の対象ファイルＦ（ｎ＋１）の文字情報を集計部１１０１により集計することで、文字情報の存否を検出することができる。したがって、新たに採番されたファイル番号ｎ＋１のビットを、各文字情報の出現マップに追加（デフォルトはＯＦＦ）し、文字情報が出現したビットについてＯＮにする。また、ファイル番号ｎ＋１のビットを削除マップＤにも追加（デフォルトはＯＮ）する。
【０３２７】
（Ｋ）また、圧縮ファイルｆ（ｎ＋１）については、セグメントｓｇ０（２）の管理領域においてポインタが関連付けされる。これにより、以降において、セグメントｓｇ０（２）においてファイル番号（ｎ＋１）が指定されると、圧縮ファイルｆ（ｎ＋１）を伸長して対象ファイルＦ（ｎ＋１）をオープンすることができる。
【０３２８】
また、図７に示したコンピュータシステムにおいて、ファイル総数がαであるとすると、α＝ファイル番号ｍ×ｎの場合、スレーブサーバＳ１にのみアーカイブファイルＡ０（１）が格納されている。そして、あらたに対象ファイルＦ（ｍ×ｎ＋１）が追加される場合、マスタサーバＭＳは、対象ファイルＦ（ｍ×ｎ＋１）の圧縮ファイルｆ（ｍ×ｎ＋１）を、割当先となるスレーブサーバＳ２に送信する。割当先をどのスレーブサーバにするかはあらかじめ決めておくものとする。スレーブサーバＳ２は、スレーブサーバＳ１のセグメントｓｇ０（ｍ）の後続セグメントとしてセグメントｓｇ０（ｍ＋１）を生成して、マスタサーバＭＳからの圧縮ｆ（ｍ×ｎ＋１）を保存することになる。
【０３２９】
図６７は、セグメント追加処理の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、指定部６２０１によりファイル追加が指定されるのを待ち受ける（ステップＳ６７０１：Ｎｏ）。ファイル追加の指定がされた場合（ステップＳ６７０１：Ｙｅｓ）、コンピュータ１１００は、保存対象セグメントｓｇ０（Ｋ）を特定する（ステップＳ６７０２）。具体的には、ファイル数ｉを１セグメントあたりのファイル数ｎで除算した商と同じ番号のセグメントを保存対象セグメントｓｇ０（Ｋ）とする。
【０３３０】
そして、コンピュータ１１００は、ファイル数ｉをインクリメントして（ステップＳ６７０３）、ｉ＞Ｋｎであるか否かを判断する（ステップＳ６７０４）。ｉ＞Ｋｎでない場合（ステップＳ６７０４：Ｎｏ）、現セグメントｓｇ０（Ｋ）にはまだ圧縮ファイルを保存できるため、コンピュータ１１００は、追加ファイルによるマップ更新処理を実行する（ステップＳ６７０９）。追加ファイルによるマップ更新処理（ステップＳ６７０９）の詳細については後述する。
【０３３１】
このあと、コンピュータ１１００は、追加ファイルを２N分枝無節点ハフマン木Ｈで圧縮して（ステップＳ６７１０）、圧縮追加ファイルを保存対象セグメントｓｇ０（Ｋ）に保存する（ステップＳ６７１１）。そして、コンピュータ１１００は、保存対象セグメントｓｇ０（Ｋ）の管理領域ＡＫに、圧縮追加ファイルへのポインタを関連付ける（ステップＳ６７１２）。これにより、セグメント追加処理を終了する。
【０３３２】
また、ステップＳ６７０４において、ｉ＞Ｋｎである場合（ステップＳ６７０４：Ｙｅｓ）、現セグメントｓｇ０（Ｋ）では圧縮追加ファイルを保存できないため、コンピュータ１１００は、現セグメントｓｇ０（Ｋ）の圧縮符号マップをマップ用ハフマン木で圧縮する（ステップＳ６７０５）。そして、コンピュータ１１００は、新セグメントの領域を確保して（ステップＳ６７０６）、セグメント番号Ｋをインクリメントする（ステップＳ６７０７）。このあと、コンピュータ１１００は、インクリメント後のセグメントｓｇ０（Ｋ）とその先行セグメントとのポインタの連携処理を実行する（ステップＳ６７０８）。これにより、図１に示したように、先行セグメントと関連付けされることとなる。このあと、ステップＳ６７０９に移行する。
【０３３３】
図６８は、図６７に示した追加ファイルによるマップ更新処理（ステップＳ６７０９）の詳細な処理手順を示すフローチャート（前半）である。まず、コンピュータ１１００は、圧縮符号マップＭｓおよび削除マップＤｓにおいて、追加ファイルのファイル番号のビットを設定する（ステップＳ６８０１）。具体的には、出現マップについてはＯＦＦのビットを追加ファイルのファイル番号に対して設定し、削除マップＤについてはＯＮのビットを追加ファイルのファイル番号に対して設定する。
【０３３４】
つぎに、コンピュータ１１００は、追加ファイル内の先頭文字を対象文字に設定し（ステップＳ６８０２）、対象文字について最長一致検索処理を実行する（ステップＳ６８０３）。最長一致検索処理（ステップＳ６８０３）は、図３１に示した処理と同一処理であるため説明を省略する。
【０３３５】
このあと、コンピュータ１１００は、最長一致した基礎単語が基礎単語の構造体２３００にあるか否かを判断する（ステップＳ６８０４）。ない場合（ステップＳ６８０４：Ｎｏ）、図６９のステップＳ６９０１に移行する。一方、ある場合（ステップＳ６８０４：Ｙｅｓ）、コンピュータ１１００は、最長一致した基礎単語の圧縮符号を２N分枝無節点ハフマン木Ｈから特定して、当該圧縮符号により、最長一致した基礎単語の出現マップを指定する（ステップＳ６８０５）。そして、コンピュータ１１００は、指定された出現マップにおいて追加ファイルのファイル番号に対応するビットをＯＮにする（ステップＳ６８０６）。このあと、図６９のステップＳ６９０１に移行する。
【０３３６】
図６９は、図６７に示した追加ファイルによるマップ更新処理（ステップＳ６７０９）の詳細な処理手順を示すフローチャート（後半）である。まず、コンピュータ１１００は、対象文字が特定単一文字であるか否かを判断する（ステップＳ６９０１）。具体的には、たとえば、コンピュータ１１００は、対象文字が特定単一文字の構造体でヒットしたか否かを判断する。
【０３３７】
対象文字が特定単一文字である場合（ステップＳ６９０１：Ｙｅｓ）、コンピュータ１１００は、ヒットした特定単一文字の圧縮符号を２N分枝無節点ハフマン木Ｈから特定して、当該圧縮符号により、ヒットした特定単一文字の出現マップを指定する（ステップＳ６９０２）。そして、コンピュータ１１００は、指定された出現マップにおいて追加ファイルのファイル番号に対応するビットをＯＮにする（ステップＳ６９０３）。このあと、ステップＳ６９０９に移行する。
【０３３８】
一方、対象文字が特定単一文字でない場合（ステップＳ６９０１：Ｎｏ）、コンピュータ１１００は、対象文字を上位分割文字コードと下位分割文字コードとに分割する（ステップＳ６９０４）。そして、コンピュータ１１００は、分割文字コードの構造体でヒットした上位分割文字コードの圧縮符号を２N分枝無節点ハフマン木Ｈから特定して、当該圧縮符号により、ヒットした上位分割文字コードの出現マップを指定する（ステップＳ６９０５）。そして、コンピュータ１１００は、指定された出現マップにおいて追加ファイルのファイル番号に対応するビットをＯＮにする（ステップＳ６９０６）。
【０３３９】
同様に、コンピュータ１１００は、分割文字コードの構造体でヒットした下位分割文字コードの圧縮符号を２N分枝無節点ハフマン木Ｈから特定して、当該圧縮符号により、ヒットした下位分割文字コードの出現マップを指定する（ステップＳ６９０７）。そして、コンピュータ１１００は、指定された出現マップにおいて追加ファイルのファイル番号に対応するビットをＯＮにする（ステップＳ６９０８）。このあと、ステップＳ６９０９に移行する。
【０３４０】
また、ステップＳ６９０９において、コンピュータ１１００は、２グラム文字列特定処理を実行する（ステップＳ６９０９）。２グラム文字列特定処理（ステップＳ６９０９）は、図３７に示した処理と同一処理であるため説明を省略する。
【０３４１】
このあと、コンピュータ１１００は、２グラム文字列（たとえば「人形」）のうち先頭グラム文字（たとえば、「人」）の圧縮符号と末尾グラム文字（たとえば、「形」）の圧縮符号とを連結する（ステップＳ６９１０）。つぎに、コンピュータ１１００は、連結圧縮符号により、２グラム文字列の出現マップを指定する（ステップＳ６９１１）。そして、コンピュータ１１００は、指定された出現マップにおいて追加ファイルのファイル番号に対応するビットをＯＮにして（ステップＳ６９１２）、一連の処理を終了する。
【０３４２】
＜セグメント階層化処理＞
つぎに、セグメント階層化処理について説明する。セグメント階層化処理とは、図４および図５に示したように、下位階層のセグメント群のインデックス情報群を上位階層のインデックス情報に集約していく処理である。セグメント階層化処理は、セグメント生成部６２０７が実行する。
【０３４３】
図７０は、セグメント階層化処理の詳細な処理手順を示すフローチャートである。図７０において、コンピュータ１１００は、指定部により、セグメントの集約指定を待ち受ける（ステップＳ７００１：Ｎｏ）。集約指定が受け付けられた場合（ステップＳ７００１：Ｙｅｓ）、コンピュータ１１００は、出現マップを指定するポインタである圧縮符号を順次選択する（ステップＳ７００２）。具体的には、未選択の圧縮符号がある場合（ステップＳ７００２：Ｙｅｓ）、コンピュータ１１００は、未選択の圧縮符号を１つ選択し（ステップＳ７００３）、選択出現マップ集約処理を実行する（ステップＳ７００４）。選択出現マップ集約処理（ステップＳ７００４）の詳細については後述する。
【０３４４】
選択出現マップ集約処理（ステップＳ７００４）のあと、ステップＳ７００２に戻る。そして、未選択の圧縮符号がない場合（ステップＳ７００２：Ｎｏ）、コンピュータ１１００は、削除マップ集約処理を実行する（ステップＳ７００５）。削除マップ集約処理（ステップＳ７００５）の詳細については後述する。これにより、セグメント階層化処理を終了する。
【０３４５】
図７１は、図７０に示した選択出現マップ集約処理（ステップＳ７００４）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、ｆ＝０、ｈ＝ｆ＋１、ｊ＝１に設定する（ステップＳ７１０１）。ここで、ｆは対象となる階層番号であり、ｈは対象階層の上位階層の階層番号である。ｊはセグメント番号である。つぎに、コンピュータ１１００は、対象階層である第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）で圧縮ファイルの空き領域があるか否かを判断する（ステップＳ７１０２）。ｍは、集約可能なセグメント数である。
【０３４６】
空き領域がない場合（ステップＳ７１０２：Ｎｏ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）の各々には圧縮ファイルが最大限格納されているため、コンピュータ１１００は、上位階層である第ｈ階層のセグメントｓｇｈ（ｊ）に集約済みであるか否かを判断する（ステップＳ７１０３）。具体的には、たとえば、コンピュータ１１００は、第ｈ階層のセグメントｓｇｈ（ｊ）が存在するか否かを判断する。
【０３４７】
集約済みでない場合（ステップＳ７１０３：Ｎｏ）、コンピュータ１１００は、上位セグメントｓｇｈ（ｊ）を設定し、上位セグメントｓｇｈ（ｊ）内に選択圧縮符号のインデックス領域を確保する（ステップＳ７１０４）。そして、ａ＝ｊに設定する（ステップＳ７１０５）。ここで、ａは対象セグメントｓｇｈ（ｊ）を特定する変数である。
【０３４８】
そして、コンピュータ１１００は、ａ＝ｊ＋ｍか否かを判断する（ステップＳ７１０６）。ａ＝ｊ＋ｍでない場合（ステップＳ７１０６：Ｎｏ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）のすべてについて集約処理が完了していない。したがって、コンピュータ１１００は、選択圧縮符号についてセグメントｓｇｆ（ａ）のインデックス情報を抽出する（ステップＳ７１０７）。
【０３４９】
そして、コンピュータ１１００は、抽出されたセグメントｓｇｆ（ａ）のインデックス情報であるビット列がオール０、すなわち、選択圧縮符号についての文字情報がセグメントｓｇｆ（ａ）内の圧縮ファイル群のいずれにも存在していないか否かを判断する（ステップＳ７１０８）。
【０３５０】
オール０の場合（ステップＳ７１０８：Ｙｅｓ）、コンピュータ１１００は、上位セグメントｓｇｈ（ａ）に集約結果として「０」を書き込み（ステップＳ７１０９）、ステップＳ７１１１に移行する。一方、オール０でない場合（ステップＳ７１０８：Ｎｏ）、上位セグメントｓｇｈ（ａ）に集約結果として「１」を書き込み（ステップＳ７１１０）、ステップＳ７１１１に移行する。ステップＳ７１１１では、ａをインクリメントし（ステップＳ７１１１）、ステップＳ７１０６に戻る。
【０３５１】
また、ステップＳ７１０６において、ａ＝ｊ＋ｍになった場合（ステップＳ７１０６：Ｙｅｓ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）のすべてについて集約処理が完了したことになる。したがって、コンピュータ１１００は、上位セグメントｓｇｈ（ｊ）と第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）との間でポインタによる関連付けをおこなう（ステップＳ７１１２）。このあと、ｊ＝ｊ＋ｍにしてｊをセグメントｍ個分シフトして（ステップＳ７１１３）、ステップＳ７１０２に戻る。
【０３５２】
また、ステップＳ７１０２において、空き領域がある場合（ステップＳ７１０２：Ｙｅｓ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）の集約処理を実行できないため、ｆ＝ｆ＋１，ｊ＝１とする（ステップＳ７１１４）。そして、コンピュータ１１００は、セグメントｓｇｆ（ｊ）が存在するか否かを判断する（ステップＳ７１１５）。存在する場合（ステップＳ７１１５：Ｙｅｓ）、ステップＳ７１０２に戻る。これにより、段階的に階層を上げて集約することができる。一方、存在しない場合（ステップＳ７１１５：Ｎｏ）、ステップＳ７００２に戻る。
【０３５３】
図７２は、図７０に示した削除マップ集約処理（ステップＳ７００５）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、ｆ＝０、ｈ＝ｆ＋１、ｊ＝１に設定する（ステップＳ７２０１）。ここで、ｆは対象となる階層番号であり、ｈは対象階層の上位階層の階層番号である。ｊはセグメント番号である。つぎに、コンピュータ１１００は、対象階層である第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）で圧縮ファイルの空き領域があるか否かを判断する（ステップＳ７２０２）。ｍは、集約可能なセグメント数である。
【０３５４】
空き領域がない場合（ステップＳ７２０２：Ｎｏ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）の各々には圧縮ファイルが最大限格納されているため、コンピュータ１１００は、上位階層である第ｈ階層のセグメントｓｇｈ（ｊ）に集約済みであるか否かを判断する（ステップＳ７２０３）。具体的には、たとえば、コンピュータ１１００は、第ｈ階層のセグメントｓｇｈ（ｊ）が存在するか否かを判断する。
【０３５５】
集約済みでない場合（ステップＳ７２０３：Ｎｏ）、コンピュータ１１００は、上位セグメントｓｇｈ（ｊ）内に削除マップのインデックス領域を確保する（ステップＳ７２０４）。そして、ａ＝ｊに設定する（ステップＳ７２０５）。ここで、ａは対象セグメントｓｇｈ（ｊ）を特定する変数である。
【０３５６】
そして、コンピュータ１１００は、ａ＝ｊ＋ｍか否かを判断する（ステップＳ７２０６）。ａ＝ｊ＋ｍでない場合（ステップＳ７２０６：Ｎｏ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）のすべてについて集約処理が完了していない。したがって、コンピュータ１１００は、削除マップについてセグメントｓｇｆ（ａ）のインデックス情報を抽出する（ステップＳ７２０７）。
【０３５７】
そして、コンピュータ１１００は、抽出されたセグメントｓｇｆ（ａ）のインデックス情報であるビット列がオール０、すなわち、セグメントｓｇｆ（ａ）内の圧縮ファイル群が削除された否かを判断する（ステップＳ７２０８）。
【０３５８】
オール０の場合（ステップＳ７２０８：Ｙｅｓ）、コンピュータ１１００は、上位セグメントｓｇｈ（ａ）に集約結果として「０」を書き込み（ステップＳ７２０９）、ステップＳ７２１１に移行する。一方、オール０でない場合（ステップＳ７２０８：Ｎｏ）、コンピュータ１１００は、上位セグメントｓｇｈ（ａ）に集約結果として「１」を書き込み（ステップＳ７２１０）、ステップＳ７２１１に移行する。ステップＳ７２１１では、ａをインクリメントし（ステップＳ７２１１）、ステップＳ７２０６に戻る。
【０３５９】
また、ステップＳ７２０６において、ａ＝ｊ＋ｍになった場合（ステップＳ７２０６：Ｙｅｓ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）のすべてについて集約処理が完了したことになる。したがって、コンピュータ１１００は、上位セグメントｓｇｈ（ｊ）と第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）との間でポインタによる関連付けをおこなう（ステップＳ７２１２）。このあと、ｊ＝ｊ＋ｍにしてｊをセグメントｍ個分シフトして（ステップＳ７２１３）、ステップＳ７２０２に戻る。
【０３６０】
また、ステップＳ７２０２において、空き領域がある場合（ステップＳ７２０２：Ｙｅｓ）、第ｆ階層のセグメントｓｇｆ（ｊ）〜ｓｇｆ（ｊ＋ｍ−１）について集約処理を実行できないため、ｆ＝ｆ＋１，ｊ＝１とする（ステップＳ７２１４）。そして、コンピュータ１１００は、セグメントｓｇｆ（ｊ）が存在するか否かを判断する（ステップＳ７２１５）。存在する場合（ステップＳ７２１５：Ｙｅｓ）、ステップＳ７２０２に戻る。これにより、段階的に階層を上げて集約することができる。一方、存在しない場合（ステップＳ７２１５：Ｎｏ）、ステップＳ７００２に戻る。
【０３６１】
このように、セグメント階層化処理を実行することで、図４および図５に示したようにセグメントの階層化が実現される。したがって、図７に示したようなアーカイブファイルの階層構造を構築することができる。
【０３６２】
＜検索処理手順＞
つぎに、本実施の形態にかかる検索処理手順について説明する。具体的には、たとえば、図６３に示したファイル伸長例についての処理手順となる。
【０３６３】
図７３は、本実施の形態にかかる検索処理手順を示すフローチャートである。まず、コンピュータ１１００は、検索文字列の入力を待ち受け（ステップＳ７３０１：Ｎｏ）、検索文字列が入力された場合（ステップＳ７３０１：Ｙｅｓ）、ポインタ特定処理（ステップＳ７３０２）、ファイル絞込み処理（ステップＳ７３０３）、伸長処理（ステップＳ７３０４）を実行する。ポインタ特定処理（ステップＳ７３０２）は、検索文字列から出現マップを指定するポインタとなる圧縮符号を特定する。ポインタ特定処理（ステップＳ７３０２）の詳細は、図７４および図７５で説明する。
【０３６４】
ファイル絞込み処理（ステップＳ７３０３）は、図８に示したように、階層構造セグメント群から検索文字列を構成する文字情報が存在する対象ファイルＦｉの圧縮ファイルｆｉを絞り込む。ファイル絞込み処理（ステップＳ７３０３）の詳細は、図７６で説明する。
【０３６５】
伸長処理（ステップＳ７３０４）は、ファイル絞込み処理（ステップＳ７３０３）で絞り込まれた圧縮ファイルｆｉを伸長する過程で、伸長対象となる圧縮符号列と検索文字列の圧縮文字列とを照合する。伸長処理（ステップＳ７３０４）の詳細は、図７７および図７８で説明する。
【０３６６】
図７４は、図７３に示したポインタ特定処理（ステップＳ７３０２）の詳細な処理手順を示すフローチャート（その１）である。まず、コンピュータ１１００は、検索文字列を対象文字列に設定し（ステップＳ７４０１）、最長一致検索処理を実行する（ステップＳ７４０２）。最長一致検索処理（ステップＳ７４０２）は、図３１に示した最長一致検索処理（ステップＳ２９０１）と同一処理であるため説明を省略する。
【０３６７】
そして、コンピュータ１１００は、基礎単語の構造体において、最長一致検索処理（ステップＳ７４０２）で得られた最長一致検索結果を２分探索する（ステップＳ７４０３）。最長一致検索結果が、基礎単語の構造体で探索された場合（ステップＳ７４０３：Ｙｅｓ）、探索された基礎単語の圧縮符号を２N分枝無節点ハフマン木Ｈから取得して検索バッファに保存する（ステップＳ７４０４）。
【０３６８】
そして、コンピュータ１１００は、対象文字列に後続があるか否かを判断する（ステップＳ７４０５）。後続がある場合（ステップＳ７４０５：Ｙｅｓ）、コンピュータ１１００は、後続文字列を対象文字列に設定して（ステップＳ７４０６）、最長一致検索処理（ステップＳ７４０２）に戻る。一方、後続がない場合（ステップＳ７４０５：Ｎｏ）、ポインタ特定処理（ステップＳ７３０２）は終了し、ファイル絞込み処理（ステップＳ７３０３）に移行する。
【０３６９】
また、ステップＳ７４０３において、最長一致検索結果が、基礎単語の構造体で探索されなかった場合（ステップＳ７４０３：Ｎｏ）、図７５のステップＳ７５０１に移行する。具体的には、最長一致検索結果が基礎単語の構造体に登録されていない場合、または、最長一致検索で最長一致候補がなかった場合（ステップＳ７４０３：Ｎｏ）に、図７５のステップＳ７５０１に移行する。
【０３７０】
図７５は、図７３に示したポインタ特定処理（ステップＳ７３０２）の詳細な処理手順を示すフローチャート（その２）である。まず、コンピュータ１１００は、対象文字列の先頭文字を対象文字に設定する（ステップＳ７５０１）。つぎに、コンピュータ１１００は、特定単一文字の構造体において対象文字を２分探索する（ステップＳ７５０２）。対象文字が探索された場合（ステップＳ７５０３：Ｙｅｓ）、コンピュータ１１００は、特定単一文字の圧縮符号を２N分枝無節点ハフマン木Ｈから取得して検索バッファに保存する（ステップＳ７５０４）。
【０３７１】
一方、ステップＳ７５０３において、探索されなかった場合（ステップＳ７５０３：Ｎｏ）、コンピュータ１１００は、対象文字を上位８ビットと下位８ビットに分割する（ステップＳ７５０５）。そして、コンピュータ１１００は、上位分割文字コードの圧縮符号を２N分枝無節点ハフマン木Ｈから取得して検索バッファに保存する（ステップＳ７５０６）。
【０３７２】
また、コンピュータ１１００は、下位分割文字コードの圧縮符号を２N分枝無節点ハフマン木Ｈから取得して検索バッファに保存する（ステップＳ７５０７）。また、コンピュータ１１００は、対象文字やステップＳ７５０５で分割された分割文字コードについて、２N分枝無節点ハフマン木Ｈの葉にアクセスし、照合フラグをＯＮにする（ステップＳ７５０８）。このあと、コンピュータ１１００は、２グラム文字列特定処理を実行する（ステップＳ７５０９）。２グラム文字列特定処理（ステップＳ７５０９）は、図３７に示した２グラム文字列特定処理（ステップＳ３４０６）と同一処理であるため説明を省略する。
【０３７３】
そして、コンピュータ１１００は、２グラム文字列特定処理（ステップＳ７５０９）で２グラム文字列が特定されなかった場合（ステップＳ７５１０：Ｎｏ）、図７４のステップＳ７４０５に戻る。一方、２グラム文字列が特定された場合（ステップＳ７５１０：Ｙｅｓ）、コンピュータ１１００は、２グラム文字列の圧縮符号を２N分枝無節点ハフマン木Ｈから取得して検索バッファに保存する（ステップＳ７５１１）。具体的には、たとえば、コンピュータ１１００は、第１グラムの圧縮符号および第２グラムの圧縮符号を２N分枝無節点ハフマン木Ｈにアクセスすることで取得、連結し、２グラム文字列の圧縮符号マップＭから連結圧縮符号で指定された出現マップを取得する。そして、図７４のステップＳ７４０５に戻る。
【０３７４】
図７６は、図７３に示したファイル絞込み処理（ステップＳ７３０３）の詳細な処理手順を示すフローチャートである。まず、コンピュータ１１００は、階層番号ｈを現時点での最上位階層の階層番号Ｈとし（ステップＳ７６０１）、セグメント番号ｊをｊ＝１に設定する（ステップＳ７６０２）。
【０３７５】
つぎに、コンピュータ１１００は、セグメントｓｇＨ（ｊ）が存在するか否かを判断する（ステップＳ７６０３）。セグメントｓｇＨ（ｊ）が存在する場合（ステップＳ７６０３：Ｙｅｓ）、コンピュータ１１００は、検索バッファ内の圧縮符号ごとに、出現マップおよび削除マップを指定する（ステップＳ７６０４）。そして、コンピュータ１１００は、指定された出現マップおよび削除マップから対象セグメントｓｇＨ（ｊ）のインデックス情報を抽出する（ステップＳ７６０５）。
【０３７６】
そして、コンピュータ１１００は、抽出されたインデックス情報群をＡＮＤ演算する（ステップＳ７６０６）。このあと、コンピュータ１１００は、現在の階層番号ｈがｈ＝０であるか否かを判断する（ステップＳ７６０７）。ｈ≠０の場合（ステップＳ７６０７：Ｎｏ）、ＡＮＤ結果で得られる「１」の位置は下位セグメントの番号となるため、当該番号を検索バッファに保存して、ステップＳ７６１０に移行する（ステップＳ７６０８）。
【０３７７】
一方、ｈ＝０の場合（ステップＳ７６０７：Ｙｅｓ）、ＡＮＤ結果で得られる「１」の位置はファイル番号となるため、当該番号の圧縮ファイルを検索バッファに保存して、ステップＳ７６１０に移行する（ステップＳ７６０９）。
【０３７８】
ステップＳ７６１０では、セグメント番号ｊをインクリメントして（ステップＳ７６１０）、ステップＳ７６０３に戻る。この際、後続セグメントとはポインタで関連付けされているため、セグメント番号のインクリメントにより後続セグメントを特定できることとなる。
【０３７９】
また、ステップＳ７６０３において、対象セグメントｓｇＨ（ｊ）が存在しない場合（ステップＳ７６０３：Ｎｏ）、コンピュータ１１００は、階層番号ｈをデクリメントし（ステップＳ７６１１）、ｈ＜０であるか否かを判断する（ステップＳ７６１２）。ｈ＜０でない場合（ステップＳ７６１２：Ｎｏ）、ステップＳ７６０２に戻る。一方、ｈ＜０である場合（ステップＳ７６１２：Ｙｅｓ）、ステップＳ７６０９により伸長対象の圧縮ファイルが特定できているため、伸長処理（ステップＳ７３０４）に移行する。
【０３８０】
図７７は、図７３に示した２N分枝無節点ハフマン木Ｈを用いた伸長処理（ステップＳ７３０４）の詳細な処理手順例を示すフローチャート（その１）である。図７７において、まず、コンピュータ１１００は、ビットアドレスａｂｉをａｂｉ＝０とし（ステップＳ７７０１）、バイトオフセットｂｙｏｓを算出し（ステップＳ７７０２）、ビットオフセットｂｉｏｓを算出する（ステップＳ７７０３）。そして、コンピュータ１１００は、バイトオフセットｂｙｏｓの位置からの圧縮符号列をレジスタｒ１にセットする（ステップＳ７７０４）。
【０３８１】
つぎに、コンピュータ１１００は、レジスタｒ２にセットされたマスクパターンをビットオフセットｂｉｏｓ分、末尾方向にシフトして（ステップＳ７７０５）、レジスタｒ１にセットされた圧縮符号列とのＡＮＤ演算をおこなう（ステップＳ７７０６）。このあと、コンピュータ１１００は、レジスタシフト数ｒｓを算出して（ステップＳ７７０７）、ＡＮＤ演算後のレジスタｒ２をレジスタシフト数ｒｓ分、末尾にシフトする（ステップＳ７７０８）。
【０３８２】
図７８は、図７３に示した２N分枝無節点ハフマン木Ｈを用いた伸長処理（ステップＳ７３０４）の詳細な処理手順例を示すフローチャート（その２）である。ステップＳ７７０８のあと、図７８において、コンピュータ１１００は、シフト後のレジスタｒ２から末尾Ｎビットを対象ビット列として抽出する（ステップＳ７８０１）。つぎに、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈの根の構造体から葉Ｌ♯へのポインタを特定し（ステップＳ７８０２）、ポイント先となる葉Ｌ♯の構造体に１パスでアクセスする（ステップＳ７８０３）。このあと、コンピュータ１１００は、アクセス先の葉Ｌ♯の構造体の照合フラグがＯＮであるか否かを判断する（ステップＳ７８０４）。
【０３８３】
照合フラグがＯＮである場合（ステップＳ７８０４：Ｙｅｓ）、コンピュータ１１００は、アクセス先の葉Ｌ♯の構造体内の文字情報について置換文字を伸長バッファに書き出して（ステップＳ７８０５）、ステップＳ７８０７に移行する。一方、照合フラグがＯＦＦの場合（ステップＳ７８０４：Ｎｏ）、コンピュータ１１００は、アクセス先の葉Ｌ♯の構造体内の文字情報（伸長文字）を伸長バッファに書き出して（ステップＳ７８０６）、ステップＳ７８０７に移行する。
【０３８４】
ステップＳ７８０７では、コンピュータ１１００は、アクセス先の葉Ｌ♯の構造体から圧縮符号長ｌｅｇを抽出し（ステップＳ７８０７）、ビットアドレスａｂｉを更新する（ステップＳ７８０８）。このあと、コンピュータ１１００は、メモリに圧縮符号列があるか否か、具体的には、マスクパターンによるマスク処理が施されていない圧縮符号列があるか否かを判断する（ステップＳ７８０９）。たとえば、バイトオフセットｂｙｏｓに該当するバイト位置があるか否かにより判断する。圧縮符号列がある場合（ステップＳ７８０９：Ｙｅｓ）、図７７のステップＳ７７０２に戻る。一方、圧縮符号列がない場合（ステップＳ７８０９：Ｎｏ）、伸長処理（ステップＳ７３０４）を終了する。
【０３８５】
このような伸長処理（ステップＳ７３０４）により、圧縮状態のまま照合・伸長をおこなうことができ、伸長速度の高速化を図ることができる。
【０３８６】
以上説明したように、本実施の形態によれば、検索対象ファイル群を複数のセグメントに分割して保存しているため、セグメント単位のインデックス情報で検索をおこなうことができる。したがって、検索対象ファイルのファイル数の増大にともなってインデックス情報のサイズが増大しても、検索処理時間の増大を抑制することができる。
【０３８７】
また、同一階層のセグメント群を集約して上位階層のセグメントを生成して階層構造セグメント群ＳＧを構築している。したがって、階層構造セグメント群ＳＧの最上位階層のセグメントのインデックス情報から順次絞込みをおこなうことで、検索文字列が存在しないセグメントおよび当該セグメントの下位に存在する圧縮ファイルを絞り込み対象から除外することができる。このように、無駄な絞り込みをしなくて済むため、検索速度の向上を図ることができる。
【０３８８】
また、上述した実施の形態では、マスタサーバが第１階層までの絞込みをおこない、絞り込まれたファイル番号を、当該ファイル番号を所有するスレーブサーバに送信する。したがって、送信されなかったスレーブサーバでは絞込み処理を実行しなくて済むため、無駄な検索を抑制することができ、検索効率の向上を図ることができる。
【０３８９】
なお、上述した実施の形態では、マスタサーバＭＳが圧縮ファイルｆｉの伸長をおこなう例について説明したが、マスタサーバＭＳが２N分枝無節点ハフマン木Ｈを各スレーブサーバにあらかじめ送信しておくことで、各スレーブサーバにおいて圧縮ファイルｆｉの伸長処理を実行することとしてもよい。この場合、マスタサーバＭＳからファイル番号ｉを受けたスレーブサーバは、当該ファイル番号ｉの圧縮ファイルＦｉを伸長し、伸長した対象ファイルＦｉをマスタサーバＭＳに返すことになる。このように、スレーブサーバに伸長処理を実行させることで、マスタサーバＭＳへの負荷集中を抑制して負荷分散を図ることができる。
【０３９０】
また、上述した実施の形態では、圧縮ファイルｆｉを絞り込む例について説明したが絞込み対象は、非圧縮の対象ファイルＦｉでもよい。この場合、上述した圧縮処理や伸長処理は不要となる。また、出現マップへのポインタは圧縮符号ではなく、文字情報を特定するポインタであればよい。
【０３９１】
また、あらかじめ、圧縮符号マップＭｓの圧縮領域のビット列を、先頭位置から末尾位置にかけて対象ファイル群Ｆｓのファイル番号ｐの降順に配列しておく。これにより、ファイル番号；１〜ｎのビット列が圧縮されても、追加ファイルのファイル番号とそのビットとのずれがなく、対象ファイルＦｉの絞込みを正確に実行することができる。
【０３９２】
また、圧縮符号マップＭｓの圧縮領域を所定数の最大倍数（たとえば、所定ファイル数ｎ＝２５６の最大倍数）のビット列にすることで、対象ファイルが追加される都度、圧縮符号マップＭｓの圧縮をおこなう必要がない。これにより、コンピュータの演算負荷を低減することができる。また、追加後のファイル総数が初期のファイル数の最大倍数に達した場合に、圧縮符号マップＭｓのファイル番号に対応する全ビットが圧縮領域となるため、圧縮符号マップＭｓがハフマン木ｈにより圧縮される。これにより、省メモリ化を図ることができる。このように、所定ファイル数ｎ（たとえば２５６個）単位で圧縮がおこなわれるため、演算負荷低減と省メモリ化を同時に実現することができる。
【０３９３】
なお、本実施の形態で説明した情報処理方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータ１１００で実行することにより実現することができる。本情報処理プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータ１１００で読み取り可能な記録媒体に記録され、コンピュータ１１００によって記録媒体から読み出されることによって実行される。また本情報処理プログラムは、インターネット等のネットワークを介して配布してもよい。
【符号の説明】
【０３９４】
６２０１  指定部
６２０２  第１伸長部
６２０３  入力部
６２０４  抽出部
６２０５  第２伸長部
６２０６  特定部
６２０７  セグメント生成部
【図１】
2013038527.tif 000003
【図２】
2013038527.tif 000004
【図３】
2013038527.tif 000005
【図４】
2013038527.tif 000006
【図５】
2013038527.tif 000007
【図６】
2013038527.tif 000008
【図７】
2013038527.tif 000009
【図８】
2013038527.tif 000010
【図９】
2013038527.tif 000011
【図１０】
2013038527.tif 000012
【図１１】
2013038527.tif 000013
【図１２】
2013038527.tif 000014
【図１３】
2013038527.tif 000015
【図１４】
2013038527.tif 000016
【図１５】
2013038527.tif 000017
【図１６】
2013038527.tif 000018
【図１７】
2013038527.tif 000019
【図１８】
2013038527.tif 000020
【図１９】
2013038527.tif 000021
【図２０】
2013038527.tif 000022
【図２１】
2013038527.tif 000023
【図２２】
2013038527.tif 000024
【図２３】
2013038527.tif 000025
【図２４】
2013038527.tif 000026
【図２５】
2013038527.tif 000027
【図２６】
2013038527.tif 000028
【図２７】
2013038527.tif 000029
【図２８】
2013038527.tif 000030
【図２９】
2013038527.tif 000031
【図３０】
2013038527.tif 000032
【図３１】
2013038527.tif 000033
【図３２】
2013038527.tif 000034
【図３３】
2013038527.tif 000035
【図３４】
2013038527.tif 000036
【図３５】
2013038527.tif 000037
【図３６】
2013038527.tif 000038
【図３７】
2013038527.tif 000039
【図３８】
2013038527.tif 000040
【図３９】
2013038527.tif 000041
【図４０】
2013038527.tif 000042
【図４１】
2013038527.tif 000043
【図４２】
2013038527.tif 000044
【図４３】
2013038527.tif 000045
【図４４】
2013038527.tif 000046
【図４５】
2013038527.tif 000047
【図４６】
2013038527.tif 000048
【図４７】
2013038527.tif 000049
【図４８】
2013038527.tif 000050
【図４９】
2013038527.tif 000051
【図５０】
2013038527.tif 000052
【図５１】
2013038527.tif 000053
【図５２】
2013038527.tif 000054
【図５３】
2013038527.tif 000055
【図５４】
2013038527.tif 000056
【図５５】
2013038527.tif 000057
【図５６】
2013038527.tif 000058
【図５７】
2013038527.tif 000059
【図５８】
2013038527.tif 000060
【図５９】
2013038527.tif 000061
【図６０】
2013038527.tif 000062
【図６１】
2013038527.tif 000063
【図６２】
2013038527.tif 000064
【図６３】
2013038527.tif 000065
【図６４】
2013038527.tif 000066
【図６５】
2013038527.tif 000067
【図６６】
2013038527.tif 000068
【図６７】
2013038527.tif 000069
【図６８】
2013038527.tif 000070
【図６９】
2013038527.tif 000071
【図７０】
2013038527.tif 000072
【図７１】
2013038527.tif 000073
【図７２】
2013038527.tif 000074
【図７３】
2013038527.tif 000075
【図７４】
2013038527.tif 000076
【図７５】
2013038527.tif 000077
【図７６】
2013038527.tif 000078
【図７７】
2013038527.tif 000079
【図７８】
2013038527.tif 000080
【手続補正書】
【提出日】平成26年3月14日(2014.3.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータに、
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、を記憶手段に記憶し、
追加ファイルの前記複数のファイルへの追加に応じて、前記第１の情報を、前記追加ファイルが前記複数の所定の文字情報をそれぞれ含むか否かを示す追加存否情報を追加して更新し、かつ、前記第２の情報を、前記追加存否情報を用いて、前記追加ファイルが追加された前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す情報に更新し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出方法。
【請求項２】
前記コンピュータに、さらに、
前記検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルが前記所定の文字情報を含まないと判定する、
ことを実行させることを特徴とする請求項１に記載の抽出方法。
【請求項３】
前記第１の情報は、前記複数のファイルのそれぞれについて前記複数の所定の文字情報をそれぞれ含むか否かを示すビットによるビット列であり、
前記第２の情報は、前記ビット列に含まれる各ビットを演算して得られるビットである、
ことを特徴とする請求項１又は２に記載の抽出方法。
【請求項４】
前記コンピュータに、
前記記憶手段に、さらに、前記複数のファイルのそれぞれについて検索対象とするか否かを示す第３の情報を記憶し、
前記複数のファイルのすべてが検索対象から除外された際に、前記第３の情報のうちの除外されたファイルについて検索対象とする旨を示す情報を、検索対象とする旨を示さない情報に更新し、
前記検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報及び前記第３の情報に基づいて、検索対象であり、且つ前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする請求項１〜３のいずれか１項に記載の抽出方法。
【請求項５】
前記コンピュータに、
前記記憶手段に、さらに、前記複数のファイルの少なくともいずれかが検索対象であるか否かを示す第４の情報を記憶し、
前記複数のファイルのそれぞれが検索対象から除外された際に、前記第４の情報を、前記複数のファイルの少なくともいずれかが検索対象である旨を示さない情報に更新し、
前記検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示し、且つ前記第４の情報が前記複数のファイルの少なくともいずれかが検索対象である旨を示すことを検出すると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする請求項１〜３のいずれか１項に記載の抽出方法。
【請求項６】
コンピュータに、
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、前記複数のファイルのそれぞれについて検索対象とするか否かを示す第３の情報を記憶し、
前記複数のファイルのいずれかが検索対象から除外された際に、前記第３の情報のうちの除外されたファイルについて検索対象とする旨を示す情報を、検索対象とする旨を示さない情報に更新し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報及び前記第３の情報に基づいて、検索対象であり、かつ前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出方法。
【請求項７】
コンピュータに、
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、を記憶手段に記憶し、
追加ファイルの前記複数のファイルへの追加に応じて、前記第１の情報を、前記追加ファイルが前記複数の所定の文字情報をそれぞれ含むか否かを示す追加存否情報を追加して更新し、かつ、前記第２の情報を、前記追加存否情報を用いて、前記追加ファイルが追加された前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す情報に更新し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記複数のファイルから前記所定の文字情報を含むファイルを抽出し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルのうちの前記一部のファイルに含まれないファイルから、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出方法。
【請求項８】
コンピュータに、
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、を記憶手段に記憶し、
追加ファイルの前記複数のファイルへの追加に応じて、前記第１の情報を、前記追加ファイルが前記複数の所定の文字情報をそれぞれ含むか否かを示す追加存否情報を追加して更新し、かつ、前記第２の情報を、前記追加存否情報を用いて、前記追加ファイルが追加された前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す情報に更新し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出プログラム。
【請求項９】
コンピュータに、
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、を記憶手段に記憶し、
追加ファイルの前記複数のファイルへの追加に応じて、前記第１の情報を、前記追加ファイルが前記複数の所定の文字情報をそれぞれ含むか否かを示す追加存否情報を追加して更新し、かつ、前記第２の情報を、前記追加存否情報を用いて、前記追加ファイルが追加された前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す情報に更新し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記複数のファイルから前記所定の文字情報を含むファイルを抽出し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルのうちの前記一部のファイルに含まれないファイルから、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出プログラム。
【請求項１０】
コンピュータに、
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、前記複数のファイルのそれぞれについて検索対象とするか否かを示す第３の情報を記憶し、
前記複数のファイルのいずれかが検索対象から除外された際に、前記第３の情報のうちの除外されたファイルについて検索対象とする旨を示す情報を、検索対象とする旨を示さない情報に更新し、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報及び前記第３の情報に基づいて、検索対象であり、かつ前記所定の文字情報を含むファイルを抽出する、
ことを実行させることを特徴とする抽出プログラム。
【請求項１１】
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、を記憶する記憶手段と、
追加ファイルの前記複数のファイルへの追加に応じて、前記第１の情報を、前記追加ファイルが前記複数の所定の文字情報をそれぞれ含むか否かを示す追加存否情報を追加して更新し、かつ、前記第２の情報を、前記追加存否情報を用いて、前記追加ファイルが追加された前記複数のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す情報に更新する更新手段と、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する抽出手段と、
を備えることを特徴とする抽出装置。
【請求項１２】
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、を記憶する記憶手段と、
追加ファイルの前記複数のファイルへの追加に応じて、前記第１の情報を、前記追加ファイルが前記複数の所定の文字情報をそれぞれ含むか否かを示す追加存否情報を追加して更新し、かつ、前記第２の情報を、前記追加存否情報を用いて、前記追加ファイルが追加された前記複数のファイルのうちの一部のファイルについて、前記一部のファイルの少なくともいずれかが前記所定の文字情報を含むか否かを示す情報に更新する更新手段と、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報に基づいて前記複数のファイルから前記所定の文字情報を含むファイルを抽出し、前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示さないことが検出されると、前記複数のファイルのうちの前記一部のファイルに含まれないファイルから、前記第１の情報に基づいて前記所定の文字情報を含むファイルを抽出する抽出手段と、
を備えることを特徴とする抽出装置。
【請求項１３】
複数のファイルのそれぞれについて複数の所定の文字情報をそれぞれ含むか否かを示す第１の情報と、前記複数のファイルの少なくともいずれかが前記複数の所定の文字情報をそれぞれ含むか否かを示す第２の情報と、前記複数のファイルのそれぞれについて検索対象とするか否かを示す第３の情報を記憶する記憶手段と、
前記複数のファイルのいずれかが検索対象から除外された際に、前記第３の情報のうちの除外されたファイルについて検索対象とする旨を示す情報を、検索対象とする旨を示さない情報に更新する更新手段と、
前記所定の文字情報についての検索要求を受けた際に、前記第２の情報が前記所定の文字情報を含む旨を示すことが検出されると、前記第１の情報及び前記第３の情報に基づいて、検索対象であり、かつ前記所定の文字情報を含むファイルを抽出する抽出手段と、
を備えることを特徴とする抽出装置。
【請求項１４】
複数のコンピュータと、割当装置と、を含む抽出システムであって、
前記割当装置が、
複数のファイルを分割して得られる複数のファイル群のそれぞれについて、それぞれのファイル群に含まれる少なくとも１つのファイルが複数の所定の文字情報をそれぞれ含むか否かを示す情報を保持する保持手段と、
追加ファイルの前記複数のファイル群のいずれかへの追加に応じて、前記保持手段に保持された情報を、前記追加ファイルが追加されたファイル群に含まれる少なくとも一つのファイルが前記所定の文字情報を含むか否かを示す情報に更新する更新手段と、
前記所定の文字情報についての検索要求を受けた場合に、前記保持手段に保持された情報に前記所定の文字情報を含むファイルを少なくとも１つ含む旨を示されるファイル群の数に応じて、前記複数のファイル群を前記複数のコンピュータのそれぞれに割り当てる割当手段と、を含み、
前記複数のコンピュータのそれぞれが、
前記複数のファイル群のそれぞれについて、それぞれのファイル群に含まれるいずれのファイルが複数の所定の文字情報をそれぞれ含むか否かを示すインデックス情報を記憶する記憶手段と、
前記追加ファイルの前記複数のファイル群のいずれかへの追加に応じて、前記記憶手段に記憶されたインデックス情報を、前記追加ファイルが追加されたファイル群に含まれるいずれかのファイルが前記所定の文字情報を含むか否かを示す情報に更新する更新手段と、
前記記憶手段に記憶された前記複数のファイル群それぞれについてのインデックス情報のうち、前記割当装置に割り当てられたファイル群についての前記インデックス情報に基づいて前記所定の文字情報を含むファイルを抽出する抽出手段と、を含む、
ことを特徴とする抽出システム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
たとえば、総出現頻度が４００００、１位からｙ位までの基礎単語群の累計出現頻度が３００００とすると、ｙ位までの出現頻度は、（３００００／４００００）×１００＝７５［％］となる。ここで、目標出現率Ｐｗが７５［％］である場合は、上位ｙ位までの基礎単語を抽出することとなる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００９１
【補正方法】変更
【補正の内容】
【００９１】
たとえば、総出現頻度が５００００、１位からｙ位までの単一文字群の累計出現頻度が４００００とすると、ｙ位までの出現頻度は、（４００００／５００００）×１００＝８０［％］となる。ここで、目標出現率Ｐｃが８０［％］である場合は、上位ｙ位までの単一文字を抽出することとなる。なお、（Ｃ２１）で抽出された単一文字を、元の単一文字群と区別するために、「特定単一文字（群）」と称す。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１３２
【補正方法】変更
【補正の内容】
【０１３２】
また、基礎単語へのポインタが対応する葉の構造体に格納されると、コンピュータ１１００は、２N分枝無節点ハフマン木Ｈにおける各基礎単語に対応する葉へのポインタを、基礎単語の構造体２３００内の対応する基礎単語に関連付けて格納することとなる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０３１８
【補正方法】変更
【補正の内容】
【０３１８】
図６５では、特定単一文字「形」について伸張する例（Ｂ）を示している。具体的には、図６４の状態（Ａ）からレジスタをビットオフセットｂｉｏｓ分シフトした場合、前回である（Ａ）のビットアドレスａｂｉはａｂｉ＝０、圧縮符号長ｌｅｇは１０ビットであるため、（Ｂ）のビットアドレスａｂｉはａｂｉ＝１０ビットとなる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０３８９
【補正方法】変更
【補正の内容】
【０３８９】
なお、上述した実施の形態では、マスタサーバＭＳが圧縮ファイルｆｉの伸長をおこなう例について説明したが、マスタサーバＭＳが２N分枝無節点ハフマン木Ｈを各スレーブサーバにあらかじめ送信しておくことで、各スレーブサーバにおいて圧縮ファイルｆｉの伸長処理を実行することとしてもよい。この場合、マスタサーバＭＳからファイル番号ｉを受けたスレーブサーバは、当該ファイル番号ｉの圧縮ファイルｆｉを伸長し、伸長した対象ファイルＦｉをマスタサーバＭＳに返すことになる。このように、スレーブサーバに伸長処理を実行させることで、マスタサーバＭＳへの負荷集中を抑制して負荷分散を図ることができる。
【国際調査報告】
2013038527.tif 000081
2013038527.tif 000082
2013038527.tif 000083
2013038527.tif 000084