JP6575688B2 - インデックス付きデータ生成プログラム、インデックス付きデータ生成方法、インデックス付きデータ生成システム、検索プログラム、検索方法、および検索システム - Google Patents

Description

本発明は、インデックス付きデータ生成プログラム、インデックス付きデータ生成方法、インデックス付きデータ生成システム、検索プログラム、検索方法、および検索システムに関する。

従来、帳票を印刷する際には、目的の出力形式で出力されることを保証するために、例えばＰＤＦ（Portable Document Format）の形式が用いられる。印刷のために作成されたＰＤＦファイルは、単に印刷や保管の目的だけでなく、検索などに利用されることがある。しかしながら、印刷のために作成されたＰＤＦファイルは、ファイルサイズを小さくすることが求められるため、高度な検索などに利用することができない。高度な検索を行うために、例えば、タグを拡張することにより、ＰＤＦファイルに、文字列などの位置情報や属性情報などのメタデータを埋め込むことが知られている。また、高度な検索を行うために、例えば、帳票の項目とページ数とを特定のキーで関連付けたインデックスを生成することが知られている。

特開２０１３−０４５２０８号公報 特開２００１−０５６８３６号公報

しかしながら、例えば、タグを拡張する場合には、ファイルサイズが大きくなり、かつインデックスを有さないので、速やかに検索することができない。

また、例えば、従来の技術を用いて、単語や数値単位に、単語や数値とページの情報を関連付けたインデックスを作成した場合であっても、インデックスは、ページの情報しか有していないため、単語や数値の項目に対応した検索ができない。そのため、インデックスを参照した場合であっても、検索により検索候補を絞り込んだ後に、検索候補に対して個別に検索対象の項目に該当するか否かを確認する必要がある。

例えば、帳票で数値の検索を行う場合、「１００」という数値を検索しても、「単価」が「１００」、「数量」が「１００」、「金額」が「１００」である検索候補が表示されるため、目的とする項目に該当するか否かの確認が必要となる。また、単語の検索を行う場合も同様に、「鎌倉」を検索しても、「支店名」が「鎌倉」、「住所」が「鎌倉」、「氏名」が「鎌倉」である検索候補が表示される。

そのため、ＰＤＦファイルの検索候補とされたページのデータをそれぞれ参照して、個別に検索対象の項目に該当するか否かを確認する必要がある。

１つの側面では、検索対象の項目に該当するか否かを速やかに判別することを目的とする。

第１の案では、インデックス付きデータ生成プログラムは、コンピュータに、複数のカラムを有する帳票を含む帳票データから帳票出力形式データを生成する処理を実行させる。インデックス付きデータ生成プログラムは、コンピュータに、単語、文字、または数値に対するインデックス情報であって、複数のカラムそれぞれの属性と、帳票出力形式データに含まれる複数のカラムそれぞれに対応したデータ相互の帳票データにおける位置関係とを特定可能な位置情報を含むインデックス情報を生成する処理を実行させる。インデックス付きデータ生成プログラムは、コンピュータに、インデックス情報、および帳票出力形式データを含む出力ファイルを出力する処理を実行させる。

１つの態様によれば、検索対象の項目に該当するか否かを速やかに判別することができる。

図１は、実施例１に係る帳票ファイルの生成処理の流れの一例を示す図である。 図２は、実施例１のビットマップ型インデックスの一例を示す図である。 図３は、実施例１に係るハッシュ化インデックス生成処理の一例を示す図である。 図４は、符号化ファイルの構成例を示す図である。 図５は、検索対象を入力した画像の一例を示す図である。 図６は、実施例１に係る検索処理の一例を示す図である。 図７は、実施例１に係る文字列判別処理の一例を示す図である。 図８は、実施例１に係る検索条件判別処理の一例を示す図である。 図９は、実施例１に係るハッシュ化ビットマップの復元処理の一例を示す図である。 図１０は、実施例１に係る帳票出力装置の構成を示す機能ブロック図である。 図１１は、実施例１に係る帳票ファイル生成処理のフローチャートの一例を示す図である。 図１２は、実施例１に係る検索装置の構成を示す機能ブロック図である。 図１３は、実施例１に係る検索処理のフローチャートの一例を示す図である。 図１４は、実施例２に係る帳票出力形式データと、ビットマップ型インデックスとの一例を示す図である。 図１５は、検索対象を入力した画像の一例を示す図である。 図１６は、実施例２に係る検索処理の一例を示す図である。 図１７は、実施例３に係る帳票出力形式データと、ビットマップ型インデックスとの一例を示す図である。 図１８は、検索対象を入力した画像の一例を示す図である。 図１９は、実施例３に係る検索処理の一例を示す図である。 図２０は、コンピュータのハードウェア構成例を示す図である。 図２１は、コンピュータで動作するプログラムの構成例を示す図である。 図２２は、実施例のシステムにおける装置の構成例を示す図である。

以下に、本願の開示するインデックス付きデータ生成プログラム、インデックス付きデータ生成方法、インデックス付きデータ生成システム、検索プログラム、検索方法、および検索システムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの権利範囲が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。

［実施例１に係る帳票ファイル生成の一例］
図１は、実施例１に係る帳票ファイルの生成処理の流れの一例を示す図である。帳票出力装置は、入力された帳票データから帳票出力形式データを生成する。帳票出力装置は、生成した帳票出力形式データに基づいて、帳票の複数の項目（カラム）それぞれの属性（以下、「項目」と称する場合がある。）と、帳票出力形式データに含まれる複数の項目それぞれに対応したデータ相互の帳票データにおける位置関係とを特定可能な位置情報を含むビットマップ型インデックスを生成する。そして、帳票出力装置は、帳票出力形式データと、ビットマップ型インデックスとを含む帳票ファイルを生成する。帳票データは、複数の項目を有する帳票を含む。

帳票ファイルの生成処理の一例を、以下に説明する。例えば、帳票ファイル生成処理を実行する帳票出力装置は、帳票データを含むファイル３を読み出す。なお、ファイル３の「３」は、ファイルＩＤが「３」であることを示す。ファイル３は、帳票の項目として、「日付」、「商品コード」、「商品名」などを有している。例えば、「日付」の項目には「２０１５／７／１５」が含まれる。また、例えば、「商品コード」の項目には「１２３４５」が含まれる。また、例えば、「商品名」の項目には「ａ１ａ２ａ３」が含まれる。ここでは、「ａ１ａ２ａ３」を、日本語の漢字で表示される「冷蔵庫」として説明する。なお、帳票の項目は、これらに限定されるものではない。

帳票出力装置は、ファイル３に含まれる帳票データから帳票出力形式データを生成する。帳票出力形式データは、ＣＳＶ（Comma-Separated Values）形式のデータである。帳票出力形式データには、カンマにより区切られた複数の項目のデータからなるレコードが含まれる。なお、図１では、一例として１つのレコードを有した例を示しているが、帳票出力形式データには、複数のレコードが含まれる。

帳票出力装置は、ファイル３に対し、単語、文字などで構成される文字列や、数値で構成される数値列を含む帳票出力形式データを符号化し、符号化データと、符号化辞書とを生成する。なお、以降、文字列、および数値列を、単に「文字列」として説明する。帳票出力装置は、例えば、「日付」の項目の「２０１５／７／１５」を「Ａ０００ｈ」に符号化する。帳票出力装置は、例えば、「商品コード」の項目の「１２３４５」を「Ｂ０１０ｈ」に符号化する。帳票出力装置は、例えば、「商品名」の項目の「冷蔵庫」を「Ｃ０２１ｈ」に符号化する。また、帳票出力装置は、例えば、帳票出力形式データの文字列がアルファベットである場合、単語ごとに符号化する。例えば、「Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｔｅｌｅｖｉｓｉｏｎ」は、「Ｌｉｑｕｉｄ」、「Ｃｒｙｓｔａｌ」、および「Ｔｅｌｅｖｉｓｉｏｎ」に分けられ、それぞれ符号化される。帳票出力形式データの各データは、項目ごとに、符号化される。帳票出力装置は、帳票出力形式データを符号化し、符号化データを生成する。

また、帳票出力装置は、帳票出力形式データの文字列が日本語である場合、１文字ごとに符号化する。例えば、「冷蔵庫」は、「冷」、「蔵」、「庫」に分けられ、それぞれ符号化される。帳票出力装置は、例えば、「冷」を「Ｄ０００ｈ」に符号化する。帳票出力装置は、例えば、「蔵」を「Ｄ００１ｈ」に符号化する。帳票出力装置は、例えば、「庫」を「Ｄ００２ｈ」に符号化する。なお、帳票出力形式データの文字列が日本語である場合、符号化データに用いられる符号は、文字列ごとに、符号化された符号である。

以降、帳票出力形式データの各データなどが符号化された符号を「単語ＩＤ」という。

符号化辞書は、静的辞書と、動的辞書とを有する。静的辞書とは、一般的な英語辞典、国語辞典や教科書などを基にして、文書中に出現する単語の出現頻度を特定し、出現頻度のより高い単語に対して、より短い符号（単語ＩＤ）を割り当てた辞書のことをいう。静的辞書には、それぞれの単語に対応する符号である静的コードがあらかじめ登録されている。これに対して、動的辞書とは、静的辞書に登録されていない単語と、動的に付された動的コード（符号）とを対応付けた辞書である。静的辞書に登録されていない単語には、一例として、出現頻度の低い単語（低頻度単語）、文字、未知語、数値、時刻、タグなどがある。ここでいう未知語とは、静的辞書に登録されていない単語であり、符号化する文書の中で繰り返し出現する特長がある単語のことをいう。動的辞書には、静的辞書に登録されていない単語の出現順に、動的コードに対応付けられた単語が登録される。なお、符号化データを生成するための符号化辞書と、ビットマップ型インデックスを生成するための符号化辞書とを異なる辞書としても良い。

帳票出力装置は、ファイルＩＤに対する単語ＩＤについての情報を生成する。また、帳票出力装置は、ファイルＩＤに対し、単語ＩＤと、単語ＩＤが示す文字列の位置とについての情報を生成する。また、帳票出力装置は、ファイルＩＤに対し、帳票の項目と、帳票の項目の位置とについての情報を生成する。帳票出力装置は、生成された情報に基づき、ファイル３に対する、単語ＩＤが示す文字列の存否を２次元ビットマップ型インデックスＢＩ１に設定する。また、帳票出力装置は、生成された情報に基づき、ファイル３に対する、単語ＩＤ、および単語ＩＤが示す文字列の位置を第１の３次元ビットマップ型インデックスＢＩ２に設定する。また、帳票出力装置は、生成された情報に基づき、ファイル３に対する、帳票の項目、および帳票の項目が示す位置を第２の３次元ビットマップ型インデックスＢＩ３に設定する。

帳票出力形式データの文字列が日本語である場合、２次元ビットマップ型インデックスＢＩ１、第１の３次元ビットマップ型インデックスＢＩ２などでは、１文字ごとに符号化した単語ＩＤが用いられる。例えば、文字列が日本語の「冷蔵庫」である場合、「冷」、「蔵」、「庫」の対応する３つの単語ＩＤが用いられる。また、例えば、文字列がアルファベットの「Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｔｅｌｅｖｉｓｉｏｎ」である場合、「Ｌｉｑｕｉｄ」、「Ｃｒｙｓｔａｌ」、「Ｔｅｌｅｖｉｓｉｏｎ」に対応する３つの単語ＩＤが用いられる。

ここでいう２次元ビットマップ型インデックスＢＩ１とは、全文検索のためのインデックスであり、文字列を指定するポインタと、各ファイルにおける文字列の存否を示すビットとを連結したビット列である。すなわち、２次元ビットマップ型インデックスＢＩ１とは、ファイルに含まれる文字列について、ファイルごとの存否をインデックス化したビットマップのことをいう。検索処理時には、このビットマップを、検索対象である文字列を含むか否かを示すインデックスとして用いることができる。文字列を指定するポインタとしては、例えば、単語ＩＤが採用される。なお、文字列を指定するポインタは、例えば、文字列そのものを用いても良い。すなわち、２次元ビットマップ型インデックスＢＩ１は、文字列を指定するポインタで示される文字列ごとのビットマップを纏めたものである。図１に示すように、２次元ビットマップ型インデックスＢＩ１のＸ軸はファイルＩＤを表し、Ｙ軸は単語ＩＤを表す。つまり、２次元ビットマップ型インデックスＢＩ１は、単語ＩＤが示す文字列の、複数のファイルＩＤが示すファイルごとの存否を表す。

ここでいう第１の３次元ビットマップ型インデックスＢＩ２は、２次元ビットマップ型インデックスＢＩ１に対して、各ファイル内での、文字列の位置を追加したビットマップ型インデックスである。すなわち、第１の３次元ビットマップ型インデックスＢＩ２とは、ファイルに含まれる、文字列について、ファイルごとに存する位置をインデックス化したビットマップのことをいう。図１に示すように、第１の３次元ビットマップ型インデックスＢＩ２のＸ軸はＯｆｆｓｅｔ（位置）を表し、Ｙ軸は単語ＩＤを表し、Ｚ軸はファイルＩＤを表す。第１の３次元ビットマップ型インデックスＢＩ２は、単語ＩＤが示す文字列の、複数のファイルＩＤが示すファイルごとの位置を表す。すなわち、第１の３次元ビットマップ型インデックスＢＩ２は、文字列相互の帳票データにおける位置関係を特定可能な位置情報を含むインデックス情報である。

また、第２の３次元ビットマップ型インデックスＢＩ３は、各ファイルにおける、帳票の項目の位置をインデックス化したビットマップのことをいう。図１に示すように、第２の３次元ビットマップ型インデックスＢＩ３のＸ軸はＯｆｆｓｅｔ（位置）を表し、Ｙ軸は帳票の項目を表し、Ｚ軸はファイルＩＤを表す。すなわち、第２の３次元ビットマップ型インデックスＢＩ３は、帳票の項目の帳票データにおける位置関係を特定可能な位置情報を含むインデックス情報である。

ここで、帳票出力装置がファイル３に対して、各ビットマップ型インデックスを生成する場合の処理について説明する。

帳票出力装置は、ファイル３の帳票の項目に含まれる文字列を単語ＩＤに符号化する。なお、文字列が日本語である場合、帳票出力装置は、１文字ごとに、単語ＩＤに符号化する。例えば、「商品名」の「冷蔵庫」は、日本語なので、１文字ごとに、単語ＩＤに符号化される。ここでは、帳票の項目「商品名」の「冷」について各ビットマップ型インデックスを生成する場合の処理について説明する。「商品名」の「冷」の単語ＩＤは、「Ｄ０００ｈ」である。ファイル３における「冷」の位置は、「２」であるとする。

帳票出力装置は、生成された情報に基づいて、ファイル３に対する、単語ＩＤ「Ｄ０００ｈ」が示す文字の存否を２次元ビットマップ型インデックスＢＩ１に設定する。図１に示す２次元ビットマップ型インデックスＢＩ１には、ファイルＩＤが「３」のファイルに、「Ｄ０００ｈ」が存在することを意味するビット値「１」が、ファイルＩＤ「３」に対応するビットに設定される。なお、例えば、ファイルに「Ｄ０００ｈ」が存在しない場合には、そのファイルＩＤに対応するビットにビット値「０」が設定される。

帳票出力装置は、生成された情報に基づいて、ファイル３に対し、単語ＩＤ「Ｄ０００ｈ」が示す文字の位置「２」を第１の３次元ビットマップ型インデックスＢＩ２に設定する。図１に示す第１の３次元ビットマップ型インデックスＢＩ２には、ファイルＩＤが「３」のファイルの位置「２」に、「Ｄ０００ｈ」が存在することを意味するビット値「１」が、ファイルＩＤ「３」の位置「２」に対応するビットに設定される。なお、例えば、ファイルの所定の位置に「Ｄ０００ｈ」が存在しない場合には、そのファイルＩＤの所定の位置に対応するビットにビット値「０」が設定される。

また、帳票出力装置は、生成された情報に基づいて、ファイル３に対し、帳票の項目「商品名」の位置を第２の３次元ビットマップ型インデックスＢＩ３に設定する。図１に示す第２の３次元ビットマップ型インデックスＢＩ３には、帳票の項目「商品名」が、ファイル３の位置「２」から始まっていることを意味するビット値「１」が、ファイルＩＤ「３」の位置「２」に対応するビットに設定される。第２の３次元ビットマップ型インデックスＢＩ３では、帳票の項目が始まる位置に対応するビットにのみビット値「１」が設定される。例えば、ファイル３において帳票の項目「商品名」は、位置「２」から始まり、位置「４」で終わる。そのため、帳票の項目「商品名」の次の項目について、第２の３次元ビットマップ型インデックスＢＩ３では、位置「５」に対応するビットにビット値「１」が設定される。

このようにして、帳票出力装置は、ファイル３に対して、帳票の複数の項目、および帳票の各データを符号化した単語ＩＤ相互の帳票データにおける位置関係を特定可能な位置情報を含む各ビットマップ型インデックスＢＩ１〜ＢＩ３を生成する。帳票出力装置は、各ビットマップ型インデックスＢＩ１〜ＢＩ３から各ハッシュ化インデックスを生成する。そして、帳票出力装置は、各ハッシュ化インデックスのインデックス情報を有する符号化ファイル、および帳票出力形式データを含む帳票ファイルを、出力ファイルとして出力する。ハッシュ化インデックスについては後述する。

[ビットマップ型インデックスの一例]
次に、ビットマップ型インデックスについて、図２を用いて説明する。図２は、実施例１のビットマップ型インデックスの一例を示す図である。ここでは、ファイル３における、帳票の項目についてのビットマップ型インデックスを一例として説明する。また、ファイル３における、帳票の項目「日付」の「２０１５／７／１５」、および帳票の項目「冷蔵庫」に対応する単語ＩＤについてのビットマップ型インデックスを一例として説明する。

帳票の項目についてのビットマップ型インデックスでは、ファイル３の先頭のレコードから、項目順に、位置、および位置に対応するビットが割り当てられる。そして、項目の位置に対応するビットのビット値が「１」に設定される。或るレコードの最後の帳票の項目に位置、および位置に対応するビットが割り当てられると、次のレコードの最初の項目に次の位置、および位置に対応する次のビットが割り当てられる。

帳票の項目「日付」のビットマップは、「・・・１０００００１」となっている。これは、ファイル３の位置「０」である０ビット目に、先頭のレコードの帳票の項目「日付」に関するデータが格納されていることを表す。また、ファイル３の位置「６」である６ビット目に、次のレコードの帳票の項目「日付」に関するデータが格納されていることを表す。また、ここでは、位置「１２」、「２１」、「２９」、および「３７」に対応する各ビットに、帳票の項目「日付」に関するデータが格納されている。

また、帳票の項目「商品コード」のビットマップは、「・・・１０００００１０」となっている。これは、ファイル３の位置「１」である１ビット目に、先頭のレコードの帳票の項目の「商品コード」に関するデータが格納されていることを表す。また、ファイル３の位置「７」である７ビット目に、次のレコードの帳票の項目「商品コード」に関するデータが格納されていることを表す。また、ここでは、位置「１３」、「２２」、「３０」、および「３８」に対応する各ビットに、帳票の項目「商品コード」に関するデータが格納されている。

また、帳票の項目「商品名」のビットマップは、「・・・１０００００１００」となっており、帳票の項目「単価」のビットマップは、「・・・１０００００１０００００」となっている。これは、ファイル３の位置「２」〜「４」である２ビット目〜４ビット目に項目「商品名」に関するデータが格納されていることを表す。また、ファイル３の位置「８」〜「１０」である８ビット目〜１０ビット目に項目「商品名」に関するデータが格納されていることを表す。また、ここでは、位置「１４」〜「１９」、「２３」〜「２７」、「３１」〜「３５」、および「３９」〜「４２」に対応する各ビットに、帳票の項目「商品名」に関するデータが格納されている。

単語ＩＤについてのビットマップ型インデックスでは、ファイル３の先頭のレコードから、単語ＩＤ順に、位置、および位置に対応するビットが割り当てられる。そして、単語ＩＤの位置に対応するビットのビット値が「１」に設定される。或るレコードの最後の単語ＩＤに位置、および位置に対応するビットが割り当てられると、次のレコードの最初の単語ＩＤに次の位置、および位置に対応する次のビットが割り当てられる。

また、単語ＩＤ「Ａ０００ｈ」（数値「２０１５／７／１５））のビットマップは、「・・・０００１」となっている。これは、単語ＩＤ「Ａ０００ｈ」に対応する数値「２０１５／７／１５」が０ビット目に格納され、他のビットには格納されていないことを表す。また、単語ＩＤ「Ｄ０００ｈ」（文字「冷」）のビットマップは、「・・・０１００」となっている。これは、単語ＩＤ「Ｄ０００ｈ」に対応する文字「冷」が２ビット目に格納され、他のビットには格納されていないことを表す。また、単語ＩＤ「Ｄ００１ｈ」（文字「蔵」）のビットマップは、「・・・１０００」となっている。これは、単語ＩＤ「Ｄ００１ｈ」に対応する文字「蔵」が３ビット目に格納され、他のビットには格納されていないことを表す。また、単語ＩＤ「Ｄ００２ｈ」（文字「庫」）のビットマップは、「・・・１００００」となっている。これは、単語ＩＤ「Ｄ００２ｈ」に対応する文字「蔵」が４ビット目に格納され、他のビットには格納されていないことを表す。

このように、ビットマップ型インデックスは、例えば、帳票の項目や、帳票データにおける単語ＩＤの位置情報などを格納したビットマップ型転置インデックスである。

[実施例１に係るハッシュ化インデックス生成処理の一例]
次に、ビットマップ側インデックスのビットマップをハッシュ化する処理の一例を、図３を参照して説明する。図３は、実施例１に係るハッシュ化インデックス生成処理の一例を示す図である。図３は、Ｘ軸としてファイルＩＤ、Ｙ軸として単語ＩＤを表す２次元ビットマップ型インデックスＢＩ１のビットマップをハッシュ化する場合を一例として説明する。

帳票出力装置は、単語ＩＤに対応するビットマップそれぞれについてハッシュ関数を適用した複数のハッシュ化ビットマップを生成する。ここでは、帳票出力装置は、４３ビットレジスタを想定し、一例として２９と３１のハッシュ値（底）を基に、２次元ビットマップ型インデックスＢＩ１のビットマップをハッシュ化する。具体的には、帳票出力装置は、１つの底のハッシュ化ビットマップについて、単語ＩＤに対応するビットマップの各ビットの位置を底で割った余りの位置に、ビットマップの各ビットの値を設定する。ビットマップの各ビットの位置は、それぞれのファイルＩＤに対応する。一例として、帳票出力装置は、底２９のハッシュ化ビットマップｈ１１について、ビットマップの各ビットの位置を底２９で割った余りの位置に、ビットマップの各ビットの値を設定する。ビットマップの３５ビット目の位置のビット値「１」は、ハッシュ化ビットマップｈ１１の６ビット目に設定される。ビットマップの４２ビット目の位置のビット値「１」は、ハッシュ化ビットマップｈ１１の１３ビット目に設定される。帳票出力装置は、底３１のハッシュ化ビットマップｈ１２について、ビットマップの各ビットの位置を底３１で割った余りの位置に、ビットマップの各ビットの値を設定する。ビットマップの３５ビット目の位置のビット値「１」は、ハッシュ化ビットマップｈ１２の４ビット目に設定される。ビットマップの４２ビット目の位置のビット値「１」は、ハッシュ化ビットマップｈ１２の１１ビット目に設定される。すなわち、帳票出力装置は、ビットマップの０ビット目からの各ビットを順番にハッシュ化ビットマップの０ビット目から設定し、（底−１）ビット目まで設定する。そして、帳票出力装置は、再度折り返してビットマップの０ビット目から既にハッシュ化ビットマップに設定された値とＯＲ演算した値を設定する。この結果、帳票出力装置は、ビットマップについて、ハッシュ化ビットマップｈ１１、ｈ１２を生成する。このようにして、帳票出力装置は、単語ＩＤにおける２次元ビットマップ型インデックスＢＩ１のビットマップについて、それぞれハッシュ化ビットマップｈ１１、ｈ１２を生成する。帳票出力装置は、生成されたハッシュ化ビットマップｈ１１、ｈ１２を纏めた２次元ハッシュ化インデックスＨＩ１を生成する。

帳票出力装置は、第１の３次元ビットマップ型インデックスＢＩ２のビットマップから、２次元ビットマップ型インデックスＢＩ１のビットマップの場合と同様に、ハッシュ関数を適用した複数のハッシュ化ビットマップを生成する。そして、帳票出力装置は、それぞれ生成されたハッシュ化ビットマップを纏めた第１の３次元ハッシュ化インデックスＨＩ２を生成する。また、帳票出力装置は、第２の３次元ビットマップ型インデックスＢＩ３から、同様に、第２の３次元ハッシュ化インデックスＨＩ３を生成する。以降、ハッシュ値（底）は、一例として、２９と３１であるとして説明する。

［符号化ファイルの構成例］
図４は、符号化ファイルの構成例を示す図である。図４に示すように、符号化ファイルは、ヘッダ部と、符号化データと、トレーラ部とを有する。符号化データは、複数のファイルそれぞれの符号化された単語ＩＤ群を記憶する。トレーラ部は、各ファイルのアドレス、動的辞書（共通／個別）の情報、ハッシュ化インデックス（２次元／３次元）などを記憶する。各ファイルのアドレスは、複数のファイルが符号化された各符号化データの格納先のアドレスを示す。各ファイルのアドレスは、一例として、符号化データの先頭からの相対アドレスである。個別の動的辞書の情報は、複数のファイルそれぞれに対する、動的辞書の情報に対応する。共通の動的辞書の情報は、複数のファイル全体に対する、動的辞書の情報に対応する。ヘッダ部には、トレーラ部に格納された各ファイルのアドレスへのポインタ、動的辞書へのポインタやハッシュ化インデックス（２次元／３次元）へのポインタが格納される。帳票出力装置は、複数のファイルをそれぞれ符号化すると、符号化されたそれぞれの結果を示す符号化データを符号化ファイルに格納し、格納した各アドレスを各ファイルのアドレスに格納する。復号化処理では、ヘッダ部の各ファイルのアドレスへのポインタを利用して、トレーラ部の各ファイルのアドレスから復号化対象のファイルのアドレスを参照する。復号化処理は、ヘッダ部の動的辞書へのポインタを利用し、動的辞書を参照する。検索処理では、ヘッダ部の各ハッシュ化インデックスのアドレスへのポインタを利用して、トレーラ部の各ハッシュ化インデックスのアドレスから検索対象のハッシュ化インデックスのアドレスを参照する。

［実施例１に係る検索処理の一例］
図５は、検索対象を入力した画像の一例を示す図である。図５に示すように、検索装置では、検索条件の有効範囲として、「帳票」、「ページ」、「レコード」とを選択可能となっている。検索条件の有効範囲は、検索を行う単位を表している。例えば、「帳票」が選択されている場合には、帳票単位で検索が行われる。また、例えば、「ページ」が選択されている場合には、ページ単位で検索が行われる。例えば、「すべて」が選択されている場合には、検索を行う単位を指定せずに、検索が行われる。検索装置では、項目条件として、例えば、３つの検索条件で検索可能となっている。ここでは、検索条件の有効範囲として、「すべて」が選択され、検索条件として「商品名」が設定され、検索対象として「冷蔵庫」が入力された場合について説明する。なお、検索条件は、直接入力可能であってもよい。検索対象として日本語が入力された場合には、検索対象の文字列は、１文字ごとに分けられ、検索が行われる。

図６は、実施例１の検索処理の一例を示す図である。図６に示すように、検索処理を実行する検索装置は、入力された検索対象の「冷蔵庫」をもとに、２次元ハッシュ化インデックスＨＩ１を参照する。検索装置は、「冷」、「蔵」、「庫」に対応する各単語ＩＤが存在するファイルＩＤを取得する。そして、検索装置は、第１の３次元ハッシュ化インデックスＨＩ２に、単語ＩＤとファイルＩＤとを指定して、単語ＩＤの位置情報を特定する。また、検索装置は、第２の３次元ハッシュ化インデックスＨＩ３に、検索条件の「商品名」とファイルＩＤとを指定して、帳票の項目「商品名」の位置情報を特定する。

検索処理の一例を、以下で詳しく説明する。検索装置は、検索対象の文字列の入力を受け付けると、２次元ハッシュ化インデックスＨＩ１を参照し、受け付けた検索対象が示す単語ＩＤに対するハッシュ化ビットマップを抽出する。検索装置は、検索対象として受け付けられた「冷蔵庫」を「冷」、「蔵」、「庫」に分けて、各文字に対応する単語ＩＤを読み出す。検索装置は、「冷」に対応する単語ＩＤ「Ｄ０００ｈ」を読み出す。検索装置は、「蔵」に対応する単語ＩＤ「Ｄ００１ｈ」を読み出す。検索装置は、「庫」に対応する単語ＩＤ「Ｄ００２ｈ」を読み出す。そして、検索装置は、単語ＩＤ「Ｄ０００ｈ」に対するハッシュ化ビットマップｈ４を２次元ハッシュ化インデックスＨＩ１から抽出する。ハッシュ化ビットマップｈ４には、底２９のハッシュ化ビットマップｈ４１と底３１のハッシュ化ビットマップｈ４２とが含まれる。検索装置は、単語ＩＤ「Ｄ００１ｈ」に対するハッシュ化ビットマップｈ５を２次元ハッシュ化インデックスＨＩ１から抽出する。ハッシュ化ビットマップｈ５には、底２９のハッシュ化ビットマップｈ５１と底３１のハッシュ化ビットマップｈ５２とが含まれる。検索装置は、単語ＩＤ「Ｄ００２ｈ」に対するハッシュ化ビットマップｈ６を２次元ハッシュ化インデックスＨＩ１から抽出する。ハッシュ化ビットマップｈ６には、底２９のハッシュ化ビットマップｈ６１と底３１のハッシュ化ビットマップｈ６２とが含まれる。

検索装置は、抽出された各単語ＩＤに対するハッシュ化ビットマップを復元する。なお、ハッシュ化ビットマップの復元処理は、後述する。復元結果は、単語ＩＤに対応するビットマップで表わされる。ここでは、検索装置は、単語ＩＤ「Ｄ０００ｈ」に対するハッシュ化ビットマップｈ４を復元し、ビットマップｂ４を復元結果として出力する。検索装置は、単語ＩＤ「Ｄ００１ｈ」に対するハッシュ化ビットマップｈ５を復元し、ビットマップｂ５を復元結果として出力する。検索装置は、単語ＩＤ「Ｄ００２ｈ」に対するハッシュ化ビットマップｈ６を復元し、ビットマップｂ６を復元結果として出力する。

また、検索装置は、単語ＩＤ「Ｄ０００ｈ」のビットマップｂ４と、単語ＩＤ「Ｄ００１ｈ」のビットマップｂ５と、単語ＩＤ「Ｄ００２ｈ」のビットマップとのＡＮＤ演算を行う。検索装置は、ＡＮＤ結果のビットがＯＮ（「１」）であるファイルＩＤを出力する。すなわち、検索装置は、単語ＩＤ「Ｄ０００ｈ」が示す「冷」と、単語ＩＤ「Ｄ００１ｈ」が示す「蔵」と、単語ＩＤ「Ｄ００２ｈ」が示す「庫」と、を含むファイルのファイルＩＤを絞り込む。ここでは、ファイルＩＤとして「３」が出力される。

また、検索装置は、ファイルＩＤを絞り込んだ後、第１の３次元ハッシュ化インデックスＨＩ２を参照し、単語ＩＤ、およびファイルＩＤに対するハッシュ化ビットマップを抽出する。ここでは、検索装置は、単語ＩＤ「Ｄ０００ｈ」、およびファイルＩＤ「３」に対するハッシュ化ビットマップｈ７を第１の３次元ハッシュ化インデックスＨＩ２から抽出する。ハッシュ化ビットマップｈ７には、底２９のハッシュ化ビットマップｈ７１と底３１のハッシュ化ビットマップｈ７２とが含まれる。また、検索装置は、単語ＩＤ「Ｄ００１ｈ」、およびファイルＩＤ「３」に対するハッシュ化ビットマップｈ８を第１の３次元ハッシュ化インデックスＨＩ２から抽出する。ハッシュ化ビットマップｈ８には、底２９のハッシュ化ビットマップｈ８１と底３１のハッシュ化ビットマップｈ８２とが含まれる。また、検索装置は、単語ＩＤ「Ｄ００２ｈ」、およびファイルＩＤ「３」に対するハッシュ化ビットマップｈ９を第１の３次元ハッシュ化インデックスＨＩ２から抽出する。ハッシュ化ビットマップｈ９には、底２９のハッシュ化ビットマップｈ９１と底３１のハッシュ化ビットマップｈ９２とが含まれる。

また、検索装置は、抽出されたハッシュ化ビットマップｈ７〜ｈ９を復元する。復元結果は、単語ＩＤ、およびファイルＩＤに対応するビットマップで表わされる。ここでは、検索装置は、単語ＩＤ「Ｄ０００ｈ」、およびファイルＩＤ「３」に対するハッシュ化ビットマップｈ７を復元し、ビットマップｂ７を復元結果として出力する。検索装置は、単語ＩＤ「Ｄ００１ｈ」、およびファイルＩＤ「３」に対するハッシュ化ビットマップｈ８を復元し、ビットマップｂ８を復元結果として出力する。検索装置は、単語ＩＤ「Ｄ００２ｈ」、およびファイルＩＤ「３」に対するハッシュ化ビットマップｈ９を復元し、ビットマップｂ９を復元結果として出力する。

また、検索装置は、復元結果として出力されたビットマップｂ７〜ｂ９のビットがＯＮ（「１」）を示すＯｆｆｓｅｔ（位置）を特定する。例えば、検索装置は、ファイルＩＤ「３」、および単語ＩＤ「Ｄ０００ｈ」のビットマップｂ７において、ビット値が「１」のＯｆｆｓｅｔ（位置）を特定する。ここでは、Ｏｆｆｓｅｔ（位置）「２」が特定される。また、検索装置は、ファイルＩＤ「３」、および単語ＩＤ「Ｄ００１ｈ」のビットマップｂ８において、ビット値が「１」のＯｆｆｓｅｔ（位置）を特定する。ここでは、Ｏｆｆｓｅｔ（位置）「３」が特定される。また、検索装置は、ファイルＩＤ「３」、および単語ＩＤ「Ｄ００２ｈ」のビットマップｂ９において、ビット値が「１」のＯｆｆｓｅｔ（位置）を特定する。ここでは、Ｏｆｆｓｅｔ（位置）「４」が特定される。

検索装置は、特定したＯｆｆｓｅｔ（位置）に基づいて、検索対象の文字列がファイルに含まれるか否か判別する。図７は、実施例１に係る文字列判別処理の一例を示す図である。

検索装置は、例えば、図７に示すように、単語ＩＤ「Ｄ０００ｈ」、「Ｄ００１ｈ」、「Ｄ００２ｈ」について、Ｏｆｆｓｅｔ（位置）が特定されると、検索対象の文字列に応じて、単語ＩＤのビットマップｂ７〜ｂ９を配置する。ここでは、検索対象の文字列が「冷蔵庫」なので、検索装置は、ビットマップｂ７、ビットマップｂ８、ビットマップｂ９の順に配置する。そして、検索装置は、検索対象の文字列の最初の文字である「冷」のビットマップｂ７でビット値が「１」であるビットを１つ左にシフトする。これにより、「冷」のビットマップｂ７では、３ビット目のビットが「１」となる。検索装置は、シフトさせた「冷」のビットマップｂ７と、次の文字である「蔵」のビットマップｂ８とのＡＮＤ演算を行う。検索装置は、ＡＮＤ演算の結果が「１」である場合、ＡＮＤ結果のビットマップでビット値が「１」であるビットを１つ左にシフトする。これにより、ＡＮＤ結果のビットマップでは、４ビット目のビットが「１」となる。検索装置は、シフトさせたＡＮＤ結果のビットマップと、さらに次の文字である「庫」のビットマップｂ９とのＡＮＤ演算を行う。検索装置は、ＡＮＤ演算の結果が「１」である場合、検索対象がファイルに含まれていると判別する。なお、検索装置は、ＡＮＤ演算のいずれかの結果が「０」である場合には、検索対象がファイルに含まれていないと判別する。

このように検索装置は、ＡＮＤ演算と、ビットのシフトとを組み合わせることで、検索対象がファイルに含まれているか否か判別する。

図６に戻り、検索装置は、ファイルＩＤを絞り込んだ後、第２の３次元ハッシュ化インデックスＨＩ３を参照し、ファイルＩＤに含まれる帳票の項目に対するハッシュ化ビットマップを抽出する。ここでは、検索装置は、ファイルＩＤ「３」に含まれる帳票の項目に対するハッシュ化ビットマップを第２の３次元ハッシュ化インデックスＨＩ３から抽出する。検索装置は、ファイル３に含まれる帳票の項目「日付」、「商品コード」、「商品名」、「単価」などに対応する、ハッシュ化ビットマップｈ１０〜ｈ１３を第２の３次元ハッシュ化インデックスＨＩ３から抽出する。ハッシュ化ビットマップｈ１０には、底２９のハッシュ化ビットマップｈ１０１と底３１のハッシュ化ビットマップｈ１０２とが含まれる。ハッシュ化ビットマップｈ１１には、底２９のハッシュ化ビットマップｈ１１１と底３１のハッシュ化ビットマップｈ１１２とが含まれる。ハッシュ化ビットマップｈ１２には、底２９のハッシュ化ビットマップｈ１２１と底３１のハッシュ化ビットマップｈ１２２とが含まれる。ハッシュ化ビットマップｈ１３には、底２９のハッシュ化ビットマップｈ１３１と底３１のハッシュ化ビットマップｈ１３２とが含まれる。

また、検索装置は、抽出されたハッシュ化ビットマップｈ１０〜ｈ１３を復元する。復元結果は、ファイルＩＤ、および帳票の項目に対応するビットマップで表される。ここでは、検索装置は、ハッシュ化ビットマップｈ１０〜ｈ１３を復元し、ビットマップｂ１０〜ｂ１３を復元結果として出力する。

また、検索装置は、復元結果として出力されたビットマップｂ１０〜ｂ１３のビットがＯＮ（「１」）を示すＯｆｆｓｅｔ（位置）を特定する。例えば、検索装置は、ファイルＩＤ「３」、および帳票の項目「日付」のビットマップｂ１０において、ビットマップｂ１０のビット値が「１」のＯｆｆｓｅｔ（位置）を特定する。ここでは、例えば、Ｏｆｆｓｅｔ（位置）「０」が特定される。検索装置は、同様に、帳票の各項目について、ビットマップｂ１１〜ｂ１３のビット値が「１」のＯｆｆｓｅｔ（位置）を特定する。

検索装置は、特定したＯｆｆｓｅｔ（位置）に基づいて、検索対象の文字列が検索条件の項目に含まれるか否か判別する。図８は、実施例１に係る検索条件判別処理の一例を示す図である。

ここでは、検索装置は、特定された帳票の項目のＯｆｆｓｅｔ（位置）と、図７を用いて説明した「冷蔵庫」についてのＡＮＤ演算の結果とに基づいて、検索条件判別処理を行う。検索装置は、図７において最終的なＡＮＤ結果のビットマップにおいて、ビット値が「１」となるＯｆｆｓｅｔ（位置）が、検索条件として選択された「商品名」の項目に含まれるか否か判別する。最終的なＡＮＤ結果のビットマップでは、４ビット目のビット値が「１」となる。「商品名」の項目のビットマップでは、２ビット目が「１」となり、「単価」の項目のビットマップでは、５ビット目が「１」となる。そのため、「商品名」の項目に含まれる文字がビットマップにおいて２ビット目〜４ビット目に格納されていることがわかる。最終的なＡＮＤ結果のビットマップでは、４ビット目が「１」である。これにより、検索装置は、ファイル３において、検索対象の文字列「冷蔵庫」が、「商品名」の項目に存在すると判別する。なお、例えば、最終的なＡＮＤ結果のビットマップでビット値が「１」となる位置が、１ビット目や、５ビット目である場合には、検索装置は、検索対象の文字列「冷蔵庫」が、「商品名」の項目に存在しないと判別する。

検索装置は、例えば、帳票の項目「商品名」に文字列「冷蔵庫」を含むファイル名を出力する。なお、検索装置は、例えば、帳票の項目「商品名」に文字列「冷蔵庫」を含むファイル名、および「冷蔵庫」を含む前後の文字列を表示してもよい。このように、検索装置は、ハッシュ化インデックス（ビットマップ型インデックス）を用いて、検索条件を満たす検索対象の文字列について検索を行い、検索結果を出力する。これにより、検索装置は、検索対象の文字列に対する検索結果を速やかに出力することができる。

［実施例１に係るハッシュ化ビットマップ復元処理の一例］
次に、ハッシュ化ビットマップを復元する処理の一例を、図９を参照して説明する。図９は、実施例１に係るハッシュ化ビットマップの復元処理の一例を示す図である。ここでは、ハッシュ化ビットマップｈ４を復元する場合を一例として説明する。

検索装置は、ハッシュ化ビットマップｈ４に含まれる、ハッシュ化ビットマップｈ４１、ｈ４２をそれぞれビットマップに展開する（復元１）。ここでは、検索装置は、１つの底のハッシュ化ビットマップの復元先のビットマップについて、底に整数（０〜）を乗算して得られた値にハッシュ化ビットマップの各ビットの位置を加算した位置に、ハッシュ化ビットマップの各ビットの値を設定する。一例として、検索装置は、底２９のハッシュ化ビットマップｈ４１の復元先のビットマップｂ４１について、底２９に「０」を乗算した値にハッシュ化ビットマップｈ４１の各ビットの位置を加算した位置に、ハッシュ化ビットマップｈ４１の各ビットの値を設定する。検索装置は、底２９のハッシュ化ビットマップｈ４１の復元先のビットマップｂ４１について、底２９に「１」を乗算した値にハッシュ化ビットマップｈ４１の各ビットの位置を加算した位置に、ハッシュ化ビットマップｈ４１の各ビットの値を設定する。検索装置は、復元先の底２９のビットマップｂ４１の最大ビットの位置のビットの値が設定されるまで繰り返す。同様に、検索装置は、底３１のハッシュ化ビットマップｈ４２の復元先のビットマップｂ４２について、底３１に「０」を乗算した値にハッシュ化ビットマップｈ４２の各ビットの位置を加算した位置に、ハッシュ化ビットマップｈ４２の各ビットの値を設定する。検索装置は、底３１のハッシュ化ビットマップｈ４２の復元先のビットマップｂ４２について、底３１に「１」を乗算した値にハッシュ化ビットマップｈ４２の各ビットの位置を加算した位置に、ハッシュ化ビットマップｈ４２の各ビットの値を設定する。検索装置は、復元先のビットマップｂ４２の最大ビットの位置のビットの値が設定されるまで繰り返す。

検索装置は、復元された各ビットマップの対応する位置のビットをＡＮＤ演算する（復元２）。ここでは、検索装置は、底２９のハッシュ化ビットマップｈ４１から復元されたビットマップｂ４１と、底３１のハッシュ化ビットマップｈ４２から復元されたビットマップｂ４２とをＡＮＤ演算する。検索装置は、ＡＮＤ結果のビットマップｂ４を復元結果として出力する。

なお、検索装置は、第１の３次元ハッシュ化インデックスＨＩ２のハッシュ化ビットマップも、２次元ハッシュ化インデックスＨＩ１のハッシュ化ビットマップの場合と同様に、復元する。また、検索装置は、第２の３次元ハッシュ化インデックスＨＩ３のハッシュ化ビットマップも、２次元ハッシュ化インデックスＨＩ１のハッシュ化ビットマップの場合と同様に、復元する。

[実施例１に係る帳票出力装置の構成]
次に、図１０を参照して、実施例１に係る帳票出力装置１００の構成について説明する。図１０は、実施例１に係る帳票出力装置１００の構成を示す機能ブロック図である。図１０に示すように、帳票出力装置１００は、制御部１１０と、記憶部１２０とを有する。

制御部１１０は、図１に示したインデックス生成処理を実行する処理部である。制御部１１０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。そして、制御部１１０は、例えば、ＡＳＩＣやＦＰＧＡなどの集積回路の電子回路に対応する。または、制御部１１０は、ＣＰＵやＭＰＵなどの電子回路に対応する。また、制御部１１０は、帳票出力形式データ生成部１１１、符号化処理部１１２、埋込部１１３、および出力部１１４を有する。

記憶部１２０は、例えばフラッシュメモリやＦＲＡＭ（登録商標）などの不揮発性の半導体メモリ素子などの記憶装置に対応する。記憶部１２０は、符号化辞書１２１と、２次元ハッシュ化インデックス１２２と、第１の３次元ハッシュ化インデックス１２３と、第２の３次元ハッシュ化インデックス１２４と、符号化データ１２５とを有する。

帳票出力形式データ生成部１１１は、符号化対象のファイルを記憶領域に読み出す。帳票出力形式データ生成部１１１は、読み出したファイルに含まれる帳票データから帳票出力形式データを生成する。帳票出力形式データ生成部１１１は、生成した帳票出力形式データを符号化処理部１１２に出力する。なお、帳票出力形式データ生成部１１１は、帳票データから帳票データのページ情報を抽出する。例えば、帳票出力形式データ生成部１１１は、帳票出力形式データを生成する前に、定義ファイルを検索し、ページ情報を抽出する。また、例えば、帳票出力形式データ生成部１１１は、帳票出力形式データを生成する過程で、ページ情報を抽出しても良い。なお、例えば、帳票出力形式データ生成部１１１は、ページ情報を、帳票出力形式データに追記する。また、例えば、帳票出力形式データ生成部１１１は、帳票出力形式データとは別に、ページ情報として出力しても良い。

符号化処理部１１２は、符号化部１１２ａと、インデックス生成部１１２ｂとを有する。符号化部１１２ａは、符号化辞書１２１に基づいて、帳票出力形式データに含まれる文字列を符号化し、符号化データ１２５を生成する。符号化部１１２ａは、帳票出力形式データに含まれる文字列が静的辞書に登録されているか否かを判定する。一例として、符号化部１１２ａは、文字列が静的辞書のビットフィルタにヒットするか否かを判定する。符号化部１１２ａは、文字列が静的辞書に登録されている場合には、文字列を静的辞書に基づいて符号化する。一例として、符号化部１１２ａは、静的辞書に基づいて、文字列を、文字列に対応する静的コード（単語ＩＤ）に符号化する。符号化部１１２ａは、符号化された単語ＩＤをインデックス生成部１１２ｂに出力する。

符号化部１１２ａは、文字列が静的辞書に登録されていない場合には、文字列を動的辞書に基づいて符号化する。一例として、符号化部１１２ａは、文字列が動的辞書のバッファ部に格納されているか否かを判定する。符号化部１１２ａは、文字列が動的辞書のバッファ部に格納されていない場合には、文字列をバッファ部に格納するとともに、文字列を格納した格納位置、および格納したデータ長をアドレステーブルに格納する。符号化部１１２ａは、文字列を、文字列に対応付けられた、アドレステーブルの動的コード（単語ＩＤ）に符号化する。また、符号化部１１２ａは、文字列が、動的辞書のバッファ部に格納されている場合には、文字列を、文字列に対応する動的コード（単語ＩＤ）に符号化する。符号化部１１２ａは、符号化された単語ＩＤ、および単語ＩＤが示す文字列の位置を含む情報をインデックス生成部１１２ｂに出力する。

インデックス生成部１１２ｂは、ファイルのファイルＩＤ、および符号化された単語ＩＤに基づいて、２次元ハッシュ化インデックス１２２を生成する。例えば、インデックス生成部１１２ｂは、符号化部１１２ａから出力された情報を受け取る。インデックス生成部１１２ｂは、受け取った情報に基づいて、単語ＩＤが存在するファイルのファイルＩＤに対応するビットマップを生成する。インデックス生成部１１２ｂは、生成したビットマップについて、底α、底βをそれぞれ用いてハッシュ化ビットマップを生成する。すなわち、インデックス生成部１１２ｂは、ファイルに対する、単語ＩＤが示す文字列の存否を２次元ハッシュ化インデックス１２２に設定する。

一例として、インデックス生成部１１２ｂは、単語ＩＤに対応するビットマップそれぞれについて、２つのハッシュ値（底）に基づいたハッシュ化ビットマップを生成する。すなわち、インデックス生成部１１２ｂは、ビットマップの０ビット目からの各ビットを順番にハッシュ化ビットマップの０ビット目から設定し、（底−１）ビット目まで設定する。そして、インデックス生成部１１２ｂは、再度折り返してハッシュ化ビットマップの０ビット目から既にハッシュ化ビットマップに設定された値とＯＲ演算した値を設定する。そして、インデックス生成部１１２ｂは、全ての単語ＩＤに対応するビットマップに対してハッシュ化ビットマップを生成すると、生成されたハッシュ化ビットマップを纏めた２次元ハッシュ化インデックス１２２を記憶部１２０に格納する。

また、インデックス生成部１１２ｂは、ファイルのファイルＩＤ、符号化された単語ＩＤ、および単語ＩＤが示す文字列の位置に基づいて、第１の３次元ハッシュ化インデックス１２３を生成する。例えば、インデックス生成部１１２ｂは、受け取った情報に基づいて、単語ＩＤが存在するファイルのファイルＩＤ、およびファイル内の単語ＩＤの位置に対応するビットマップを生成する。インデックス生成部１１２ｂは、生成したビットマップについて、底α、底βをそれぞれ用いてハッシュ化ビットマップを生成する。すなわち、インデックス生成部１１２ｂは、ファイル（帳票データ）に対する、単語ＩＤ、および単語ＩＤが示す文字列の位置を第１の３次元ハッシュ化インデックス１２３に設定する。

またインデックス生成部１１２ｂは、ファイルのファイルＩＤ、帳票の項目、および帳票の項目の位置に基づいて、第２の３次元ハッシュ化インデックス１２４を生成する。例えば、インデックス生成部１１２ｂは、受け取った情報に基づいて、単語ＩＤが存在するファイルのファイルＩＤ、および帳票の項目の位置に対応するビットマップを生成する。インデックス生成部１１２ｂは、生成したビットマップについて、底α、底βをそれぞれ用いてハッシュ化ビットマップを生成する。すなわち、インデックス生成部１１２ｂは、ファイル（帳票データ）に対する、帳票の項目、および帳票データにおける帳票の項目の位置を第２の３次元ハッシュ化インデックス１２４に設定する。

なお、第１の３次元ハッシュ化インデックス１２３、および第２の３次元ハッシュ化インデックス１２４の生成方法は、２次元ハッシュ化インデックス１２２の説明と同様であるので、その説明を省略する。インデックス生成部１１２ｂは、生成した、第１の３次元ハッシュ化インデックス１２３、および第２の３次元ハッシュ化インデックス１２４を記憶部１２０に格納する。

埋込部１１３は、符号化辞書１２１の動的辞書と、符号化データ１２５と、各ハッシュ化インデックス１２２〜１２４のインデックス情報とを有する符号化ファイルを、帳票ファイルに埋め込み、出力ファイルを生成する。これにより、インデックス付きの帳票ファイルが生成される。例えば、帳票ファイルがＰＤＦファイルである場合には、埋込部１１３は、ＰＤＦファイルの拡張領域に、符号化ファイルを埋め込む。また、例えば、帳票ファイルが、帳票製品の独自圧縮ファイルである場合には、埋込部１１３は、符号化ファイルを帳票定義体などと一緒に圧縮し、出力ファイルを生成する。

出力部１１４は、出力ファイルを、例えば、検索装置２００（図１２参照）へ転送する。

[実施例１に係る帳票ファイル生成処理の処理手順]
次に、実施例１に係る帳票ファイル生成処理の処理手順について、図１１を参照して説明する。図１１は、実施例１に係る帳票ファイル生成処理のフローチャートの一例を示す図である。帳票ファイルは、インデックス付きの帳票ファイルである。

帳票出力形式データ生成部１１１は、符号化対象のファイルを記憶領域に読み出す（Ｓ１０）。帳票出力形式データ生成部１１１は、読み出したファイルに含まれる帳票データから帳票出力形式データを生成する（Ｓ１１）。

符号化部１１２ａは、符号化辞書１２１に基づいて、帳票出力形式データの文字列を単語ＩＤに符号化する（Ｓ１２）。なお、符号化部１１２ａは、符号化辞書１２１（静的辞書、および動的辞書）に文字列が格納されていない場合には、新たに文字列を符号化し、動的辞書に格納する。

インデックス生成部１１２ｂは、ファイルのファイルＩＤ、および単語ＩＤに基づいて、２次元ハッシュ化インデックス１２２を生成する（Ｓ１３）。インデックス生成部１１２ｂは、ファイルのファイルＩＤ、単語ＩＤ、およびファイル内における単語ＩＤの位置に基づいて、第１の３次元ハッシュ化インデックス１２３を生成する（Ｓ１４）。インデックス生成部１１２ｂは、ファイルのファイルＩＤ、帳票の項目、およびファイル内における帳票の項目の位置に基づいて、第２の３次元ハッシュ化インデックス１２４を生成する（Ｓ１５）。

埋込部１１３は、符号化辞書１２１の動的辞書と、各ハッシュ化インデックス１２２〜１２４とを有する符号化ファイルを帳票ファイルに埋め込み、出力ファイルを生成する（Ｓ１６）。

出力部１１４は、生成された出力ファイルを、例えば、検索装置２００（図１２参照）に出力する（Ｓ１７）。

[実施例１に係る検索装置の構成]
次に図１２を参照して、実施例１に係る検索処理を実行する検索装置２００の構成について説明する。図１２は、実施例１に係る検索装置２００の構成を示す機能ブロック図である。図１２に示すように、検索装置２００は、制御部２１０と記憶部２２０とを有する。

制御部２１０は、図６〜図８に示した検索処理を実行する処理部である。制御部２１０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。そして、制御部２１０は、例えば、ＡＳＩＣやＦＰＧＡなどの集積回路の電子回路に対応する。または、制御部２１０は、ＣＰＵやＭＰＵなどの電子回路に対応する。また、制御部２１０は、検索対象受付部２１１と、第１の復元部２１２と、第２の復元部２１３と、検索処理部２１４と、検索結果出力部２１５とを有する。

記憶部２２０は、例えばフラッシュメモリやＦＲＡＭ（登録商標）などの不揮発性の半導体メモリ素子などの記憶装置に対応する。記憶部２２０は、符号化辞書２２１、２次元ハッシュ化インデックス２２２、第１の３次元ハッシュ化インデックス２２３、第２の３次元ハッシュ化インデックス２２４、第１の復元ビットマップ２２５、第２の復元ビットマップ２２６、第３の復元ビットマップ２２７、絞込みビットマップ２２８、および符号化データ２２９を有する。第１の復元ビットマップ２２５は、２次元ハッシュ化インデックス２２２を展開したビットマップである。第２の復元ビットマップ２２６は、第１の３次元ハッシュ化インデックス２２３を展開したビットマップである。第３の復元ビットマップ２２７は、第２の３次元ハッシュ化インデックス２２４を展開したビットマップである。絞込みビットマップ２２８は、検索対象が複数の単語ＩＤで表される文字列である場合に、第２の復元ビットマップ２２６をＡＮＤ演算したＡＮＤ結果のビットマップである。ＡＮＤのビットマップは、例えば、図７において、ＡＮＤ結果の「冷蔵庫」を示すビットマップが対応する。

検索対象受付部２１１は、検索対象を受け付ける。例えば、検索対象受付部２１１は、図５に示すような入力画像を表示し、検索条件や、検索対象の文字列を受け付ける。

第１の復元部２１２は、検索対象の文字列が示す単語ＩＤに対応する２次元ハッシュ化インデックス２２２からハッシュ化ビットマップを抽出する。第１の復元部２１２は、抽出したハッシュ化ビットマップを展開し、展開した第１の復元ビットマップ２２５を記憶部２２０に格納する。検索対象が複数の単語ＩＤで表される文字列で構成される場合には、第１の復元部２１２は、各単語ＩＤに対応した複数の２次元ハッシュ化インデックス２２２からハッシュ化ビットマップを複数抽出する。そして、第１の復元部２１２は、各ハッシュ化ビットマップを展開し、展開した複数のビットマップを第１の復元ビットマップ２２５として、記憶部２２０に格納する。

第１の復元部２１２は、第１の復元ビットマップ２２５から、検索対象の文字列を全て含むファイルＩＤを抽出する。例えば、第１の復元部２１２は、第１の復元ビットマップ２２５が複数ある場合には、図６に示すように、第１の復元ビットマップ２２５のＡＮＤ演算を行う。第１の復元部２１２は、ＡＮＤ結果のビット値が「１」であるファイルＩＤを抽出する。第１の復元部２１２は、抽出したファイルＩＤを第２の復元部２１３に出力する。

第２の復元部２１３は、ファイルＩＤ、および検索対象の文字列が示す単語ＩＤに対応する第１の３次元ハッシュ化インデックス２２３からハッシュ化ビットマップを抽出する。第２の復元部２１３は、抽出したハッシュ化ビットマップを展開し、展開した第２の復元ビットマップ２２６を記憶部２２０に格納する。検索対象が複数の単語ＩＤで表される文字列で構成される場合には、第２の復元部２１３は、各単語ＩＤに対応した複数の第１の３次元ハッシュ化インデックス２２３からハッシュ化ビットマップを複数抽出する。そして、第２の復元部２１３は、各ハッシュ化ビットマップを展開し、展開した複数のビットマップを第２の復元ビットマップ２２６として、記憶部２２０に格納する。

また、第２の復元部２１３は、ファイルＩＤ、および帳票の項目に対応する第２の３次元ハッシュ化インデックス２２４からハッシュ化ビットマップを抽出する。第２の復元部２１３は、抽出したハッシュ化ビットマップを展開し、展開した第３の復元ビットマップ２２７を記憶部２２０に格納する。

検索処理部２１４は、検索対象の文字列を含むファイル、および検索対象の文字列の位置を検索する。例えば、検索処理部２１４は、第２の復元ビットマップ２２６に基づいて、ビット値が「１」を示すＯｆｆｓｅｔ（位置）を抽出する。検索処理部２１４は、検索対象が複数の単語ＩＤで表される文字列で構成される場合には、ビット値が「１」を示すＯｆｆｓｅｔ（位置）を、第２の復元ビットマップ２２６ごとに、抽出する。そして、検索処理部２１４は、単語ＩＤの並び、すなわち文字列の並びと、ビット値が「１」を示すＯｆｆｓｅｔ（位置）の並びとを比較する。すなわち、検索処理部２１４は、検索対象における文字列の位置関係と、ビット値が「１」となる単語ＩＤの位置関係とが一致するか否か判別する。例えば、検索処理部２１４は、第２の復元ビットマップ２２６において、図７に示すように、ＡＮＤ演算とビットのシフトとを組み合わせて、検索対象の文字列の位置関係と、単語ＩＤの位置関係とが一致するか否か判別する。検索処理部２１４は、検索対象の文字列の位置関係と、単語ＩＤの位置関係とが一致する場合に、最終的なＡＮＤ結果のビットマップを、絞込みビットマップ２２８として記憶部２２０に格納する。

また、検索処理部２１４は、検索条件を満たす検索対象を検索する。例えば、検索処理部２１４は、図５の項目条件において、検索条件が選択されている場合には、第３の復元ビットマップ２２７、および絞込みビットマップ２２８に基づいて、検索条件を満たす検索対象を検索する。例えば、検索処理部２１４は、絞込みビットマップ２２８においてビット値が「１」となるＯｆｆｓｅｔ（位置）が、第３の復元ビットマップ２２７において検索条件の項目を示すＯｆｆｓｅｔ（位置）に含まれる場合に、検索条件を満たすと判別する。このようにして、検索処理部２１４は、検索条件を満たす検索対象を検索する。

検索結果出力部２１５は、検索処理部２１４の検索結果を出力する。検索結果出力部２１５は、検索条件を満たし、検索対象の文字列を含むファイルについて、例えば、ファイル名を出力する。

[実施例１に係る検索処理の処理手順]
次に、実施例１に係る検索処理の処理手順について、図１３を参照して説明する。図１３は、実施例１に係る検索処理のフローチャートの一例を示す図である。

検索対象受付部２１１は、検索対象を受け付ける（Ｓ２０）。

第１の復元部２１２は、検索対象の文字列を表す単語ＩＤに対応する２次元ハッシュ化インデックス２２２を読み出す（Ｓ２１）。第１の復元部２１２は、読み出した２次元ハッシュ化インデックス２２２からハッシュ化ビットマップを抽出し、第１の復元ビットマップ２２５に展開する（Ｓ２２）。第１の復元部２１２は、第１の復元ビットマップ２２５に基づいて、検索対象の文字列を表す単語ＩＤを全て含むファイルＩＤを抽出する（Ｓ２３）。

第２の復元部２１３は、ファイルＩＤ、および単語ＩＤに基づいて第１の３次元ハッシュ化インデックス２２３を読み出す（Ｓ２４）。第２の復元部２１３は、第１の３次元ハッシュ化インデックス２２３からハッシュ化ビットマップを抽出し、第２の復元ビットマップ２２６に展開する（Ｓ２５）。第２の復元部２１３は、ファイルＩＤ、および検索条件として選択された帳票の項目に基づいて第２の３次元ハッシュ化インデックス２２４を読み出す（Ｓ２６）。第２の復元部２１３は、第２の３次元ハッシュ化インデックス２２４からハッシュ化ビットマップを抽出し、第３の復元ビットマップ２２７に展開する（Ｓ２７）。なお、検索条件が選択されていない場合には、第２の復元部２１３は、例えば、第２の３次元ハッシュ化インデックス２２４からハッシュ化ビットマップを抽出せずに、処理を進める。

検索処理部２１４は、第２の復元ビットマップ２２６に検索対象の文字列が全て含まれるか否か判別する（Ｓ２８）。第２の復元ビットマップ２２６に検索対象の文字列が全て含まれている場合（Ｓ２８肯定）、検索処理部２１４は、検索条件を満たすか否か判別する（Ｓ２９）。なお、検索条件が選択されていない場合には、検索処理部２１４は、例えば、検索条件を満たすか否か判別せずに、処理を進める。

検索条件を満たす場合（Ｓ２９肯定）、検索結果出力部２１５は、検索条件を満たし、検索対象の文字列を含むファイルについて、例えば、ファイル名を出力する（Ｓ３０）。一方、第２の復元ビットマップ２２６に検索対象の文字列の何れかが含まれていない場合（Ｓ２８否定）、検索結果出力部２１５は、検索対象の文字列を含むファイルがない旨を検索結果として出力する（Ｓ３１）。また、検索条件を満たさない場合（Ｓ２９否定）、検索結果出力部２１５は、検索条件を満たすファイルがない旨を検索結果として出力する（Ｓ３２）。

[実施例の効果]
帳票出力装置１００は、帳票データから帳票出力形式データを生成する。帳票出力装置１００は、文字列に対するインデックス情報であって、帳票の項目と、帳票出力形式データに含まれる帳票の項目それぞれに対応したデータ相互の帳票データにおける位置関係とを特定可能な位置情報を含むインデックス情報を生成する。帳票出力装置１００は、インデックス情報、および帳票出力形式データを含む出力ファイルを出力する。これにより、例えば、検索装置２００は、インデックス情報を参照することで、検索対象の有無を速やかに判別することができる。

インデックス情報は、帳票の項目と、帳票出力形式データに含まれるデータ相互の位置関係とを特定可能な位置情報を含んでいる。これにより、例えば、検索装置２００は、インデックス情報を参照することで、例えば、検索対象の項目に該当するか否かを速やかに判別することができる。

出力ファイルは、拡張領域に、帳票出力形式データが符号化された符号化データ、およびインデックス情報を含む。例えば、出力ファイルがＰＤＦファイルである場合、ＰＤＦの拡張領域に、符号化データ、およびインデックス情報が含まれる。これにより、例えば、検索装置２００は、帳票出力形式データが符号化された状態で、検索を行うことができ、検索対象の項目に該当するか否かを速やかに判別することができる。

なお、例えば、ＰＤＦファイルに属性情報や、文字列などの位置情報などをメタデータとして埋め込むことも考えられる。しかし、この場合、ファイルサイズが大きくなる。また、ＰＤＦファイルを生成する時間が長くなる。これに対し、帳票出力装置１００は、例えば、ＰＤＦファイルの拡張領域に、帳票出力形式データが符号化された符号化データ、およびインデックス情報を埋め込む。これにより、帳票出力装置１００は、出力ファイルのファイルサイズを小さくすることができる。また、帳票出力装置１００は、例えば、ＰＤＦファイルを生成する時間を短くすることができる。

また、ファイルサイズを小さくするために、例えば、帳票データをＺｉｐ形式で圧縮することも考えられる。しかし、Ｚｉｐ形式で圧縮すると、圧縮された帳票データを使用する場合に、圧縮ファイルを全て伸張する必要がある。そのため、全ての伸張が終了するまで検索ができず、検索時間が長くなる。これに対し、帳票出力装置１００は、符号化データとは別に、インデックス情報を有する。これにより、例えば、検索装置２００は、インデックス情報を参照することで、検索対象の項目に該当するか否かを速やかに判別することができる。そのため、検索時間を短くすることができる。

符号化データは、帳票出力形式データが帳票の項目ごとに、符号化されたデータである。これにより、帳票出力装置１００は、高い圧縮率で圧縮した出力ファイルを作成することができ、出力ファイルのサイズを小さくすることができる。また、例えば、検索装置２００は、符号化データを帳票の項目ごとに、伸張することができ、必要な部分のみの参照、または取り出しを行うことができる。

インデックス情報である第１の３次元ハッシュ化インデックス１２３、２２３は、ファイルＩＤと、単語ＩＤと、単語ＩＤの位置情報とを軸とするビットマップ型転置インデックス情報である。これにより、帳票出力装置１００は、例えば、ＰＤＦファイルに属性情報や、文字列などの位置情報などをメタデータとして埋め込む場合と比較して、出力ファイルのサイズを小さくすることができる。また、例えば、検索装置２００は、精度の良い検索を速やかに行うことができる。

次に、実施例２について説明する。実施例２では、異なる項目の中に同じ文字列が含まれる場合について説明する。

[実施例２に係る帳票出力形式データとビットマップ型インデックスの一例]
図１４は、実施例２に係る帳票出力形式データと、ビットマップ型インデックスとを示す図である。図１４の帳票出力形式データは、帳票の項目として、「支店名」、「住所」、「性別」などを有している。また、例えば、「支店名」の項目には、「鎌倉支店」が含まれる。また、例えば、「住所」の項目には、「鎌倉市」が含まれる。また、例えば、「性別」の項目には、「男」が含まれる。なお、実施例２における符号化の手順、ハッシュ化の手順などは、実施例１と同じであり、実施例２での説明は省略する。また、以降、各文字列については、単語ＩＤに符号化する前の各文字列を用いて説明する。

帳票出力装置が生成したビットマップ型インデックスには、異なる帳票の項目、例えば、「支店名」、および「住所」に、文字列「鎌」、および「倉」が含まれる。そのため、「鎌」におけるビットマップでは、０ビット目、および４ビット目のビット値が「１」に設定される。また、「倉」におけるビットマップでは、１ビット目、および５ビット目のビット値が「１」に設定される。

[実施例２の検索処理の一例]
図１５は、検索対象を入力した画像の一例を示す図である。ここでは、検索条件として「住所」が選択され、検索対象として「鎌倉」が入力されている。

検索装置は、検索対象の入力を受け付けると、図１６に示すように、検索条件である「住所」の項目のビットマップにマスクビットを設定する。図１６は、実施例２に係る検索処理の一例を示す図である。帳票の項目「住所」のビットマップにマスクビットが設定されると、４ビット目〜６ビット目のビット値が「１」に設定されたビットマップが生成される。

検索装置は、マスクビットのビットマップと、「鎌倉」の検索結果のビットマップ（絞込みビットマップ２２８）とをＡＮＤ演算する。なお、「鎌倉」の検索処理は、例えば、図７を用いて説明した検索処理と同じであり説明は省略する。「鎌倉」は、帳票の項目「支店名」と、帳票の項目「住所」とに存在するため、「鎌倉」の検索結果のビットマップでは、１ビット目、および５ビット目のビット値が「１」に設定されている。しかし、マスクビットのビットマップでは、１ビット目は、帳票の項目「住所」に該当しないため、ビット値が「０」に設定されている。従って、ＡＮＤ演算を行うと、ＡＮＤ結果のビットマップでは、１ビット目のビット値は「０」であり、５ビット目のビット値のみが「１」となる。このように、検索装置は、ＡＮＤ演算を行うことで、検索条件を満たす検索対象を絞り込む。つまり、帳票の複数の項目に同じ文字列が含まれる場合でも、検索装置は、検索条件に応じて検索対象の位置を絞り込むことができる。

次に、実施例３について説明する。実施例３では、異なる項目の中に同じ文字列が含まれ、レコード単位で検索を行う場合について説明する。

[実施例３に係る帳票出力形式データとビットマップ型インデックスの一例]
図１７は、実施例３に係る帳票出力形式データと、ビットマップ型インデックスとを示す図である。図１７の帳票出力形式データは、帳票の項目として、「支店名」、「住所」、「性別」を有している。なお、帳票出力形式データは、他の項目を有しても良い。また、図１７の帳票出力形式データには、複数のレコードが含まれ、例えば、レコード１、およびレコード２には、「性別」の項目のみが異なるデータが含まれる。なお、実施例３における符号化の手順、ハッシュ化の手順などは、実施例１と同じであり、実施例３での説明は省略する。また、以降、各文字列については、単語ＩＤに符号化する前の各文字列を用いて説明する。

帳票出力装置が生成したビットマップ型インデックスには、異なる帳票の項目、および異なるレコードに、文字列「鎌」、および「倉」が含まれる。そのため、「鎌」におけるビットマップでは、０ビット目、４ビット目、８ビット目、および１２ビット目のビット値が「１」に設定される。また、「倉」におけるビットマップでは、１ビット目、５ビット目、９ビット目、および１３ビット目のビット値が「１」に設定される。また、レコードの区切りを示すビットマップでは、０ビット目、８ビット目、および１６ビット目に「１」が設定される。なお、レコードの区切りを示すビットマップでは、レコードの最初の文字列に対応するビットのビット値が「１」に設定される。レコードの区切りを示すビットマップは、例えば、帳票の項目についてのビットマップと同様に、３次元ビットマップ型インデックスとして生成される。その手順についての説明は省略する。

[実施例３の検索処理の一例]
図１８は、検索対象を入力した画像の一例を示す図である。ここでは、レコード単位で検索が選択されている。また、検索条件１として「住所」が設定され、検索対象として「鎌倉」が入力されている。さらに検索条件２として「すべて」が設定され、検索対象として「女」が入力されている。

検索装置は、検索対象を受け付けると、図１９に示すように、検索条件である「住所」の項目のビットマップにマスクビットを設定する。図１９は、実施例３に係る検索処理の一例を示す図である。帳票の項目「住所」のビットマップにマスクビットが設定されると、４〜６ビット目、および１２〜１４ビット目のビット値が「１」に設定されたビットマップが生成される。

検索装置は、マスクビットのビットマップと、「鎌倉」の検索結果のビットマップ（絞込みビットマップ２２８）とをＡＮＤ演算する。ＡＮＤ演算を行うと、ＡＮＤ結果のビットマップでは、５ビット目、および１３ビット目のビット値が「１」となる。これは、レコード１の帳票の項目「住所」と、レコード２の帳票の項目「住所」とに「鎌倉」が含まれることを表している。

検索装置は、検索条件が「すべて」である場合には、例えば、マスクビットを設定せずに、検索対象の「女」の検索結果のビットマップをそのまま、ＡＮＤ結果のビットマップとして出力する。検索対象の「女」のＡＮＤ結果のビットマップでは、１５ビット目のビット値が「１」に設定されている。なお、検索装置は、検索条件が「すべて」である場合には、帳票の項目の全てのビットマップにマスクビットを設定して、ＡＮＤ演算を行ってもよい。

検索装置は、ＡＮＤ結果のビットマップと、検索対象の「女」のＡＮＤ結果のビットマップと、レコードの区切り位置を示すビットマップとに基づいて、検索条件を満たすレコードを判別する。検索装置は、レコードの区切り位置を示すビットマップにおいて、レコード１を示す０ビット目〜７ビット目に、ＡＮＤ結果のビットマップ、および検索対象の「女」のＡＮＤ結果のビットマップでビット値が「１」に設定されているか否か判別する。また、検索装置は、レコードの区切り位置を示すビットマップにおいて、レコード２を示す８ビット目〜１５ビット目に、ＡＮＤ結果のビットマップ、および検索対象の「女」のＡＮＤ結果のビットマップでビット値が「１」に設定されているか否か判別する。ここでは、０ビット目〜７ビット目には、検索対象の「女」のＡＮＤ結果のビットマップでビット値が「１」に設定されていない。そのため、検索装置は、レコード１は、検索条件を満たさないと判別する。また、８ビット目〜１５ビット目には、検索対象の「女」のＡＮＤ結果のビットマップでビット値が「１」に設定されており、ＡＮＤ結果のビットマップのビット値が「１」に設定されている。そのため、検索装置は、レコード２は検索条件を満たすと判別する。検索装置は、検索条件を満たし、検索対象の「鎌倉」、および「女」を含むレコード２を絞り込み出力する。つまり、複数のレコード、および帳票の複数の項目に同じ文字列が含まれる場合でも、検索装置は、検索条件に応じてレコード単位で検索対象を絞り込むことができる。

さて、これまで開示の装置に関する実施例について説明したが、開示の技術は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。

実施例に係る検索装置２００は、検索対象を含むファイルなどが複数存在する場合には、例えば、ファイルごとに、検索対象の数をカウントし、検索対象を多く含むほどファイルを優先的に出力しても良い。例えば、検索装置２００は、ファイルを、検索対象を多く含む順に出力する。これにより、検索対象を多く含むファイルなどを速やかに発見することができる。

また、実施例に係る帳票出力装置１００は、３２ビットレジスタを想定し、２９と３１のハッシュ値（底）を基に、各ビットマップをハッシュ化するとして説明した。実施例では、１つのビットマップを４４ビットとして説明した。しかしながら、２９および３１のハッシュ値（底）は、一例であって、これに限定されない。ビットマップのビット数も、一例であって、これに限定されない。２つのハッシュ値（底）は、複数のファイル内のそれぞれの文字列の数に応じて決定されれば良い。例えば、文字列の数が１００００であるとすると、一方の底で割った余りと他方の底で割った余りとから表わされる２次元の行列が約１００００となるように、２つの底が選択される。２つの底は、隣接した素数であれば良い。選択される２つの素数は、行列の数が１００００の場合、一例として、９７と１０１である。つまり、最小公倍数が約１００００となる２次元のマトリックス空間の中で、ある文字列について一方のハッシュおよび他方のハッシュで求められる余りの組は、他の文字列について求められる余りの組と衝突しない（重複しない）であろうという推測に基づくものである。

また、実施例では、帳票出力装置１００が、単語ＩＤに対応するビットマップおよび単語ＩＤおよびファイルＩＤに対応するビットマップそれぞれについて、２つのハッシュ値（底）に基づいたそれぞれのハッシュ化ビットマップを生成すると説明した。帳票出力装置１００は、ハッシュ化ビットマップを生成する際、ハッシュの衝突（ハッシュノイズ）を検知する場合がある。例えば、超高頻度の文字列は、複数のファイルに存在するため、超高頻度の文字列に対応するビットマップの複数位置のビット値が「１」に設定される。すると、ビットマップがハッシュ化されると、ハッシュ化ビットマップの同じ位置に「１」が重複して設定されることがある。超高頻度の文字列の一例として、「ｔｈｅ」や「ｏｎ」が挙げられる。そこで、帳票出力装置１００は、ハッシュノイズに対して、ハッシュの衝突監視を行い、０／１比率の測定やビットマップの分割により、ハッシュノイズの低減化を行えば良い。例えば、帳票出力装置１００は、ハッシュ化ビットマップのいずれか１つで連続して衝突が発生した場合に、衝突が発生したハッシュ化ビットマップに対応するビットマップの存否情報を用いて存否（１／０）の比率を集計する。帳票出力装置１００は、「１」の比率が閾値より大きい場合には、衝突が発生したハッシュ化ビットマップに対応するビットマップを分割する。一例として、帳票出力装置１００は、衝突が発生したハッシュ化ビットマップに対応するビットマップの偶数番目の位置のビットを抽出し、新たにビットマップを生成する。加えて、帳票出力装置１００は、衝突が発生したハッシュ化ビットマップに対応するビットマップの奇数番目の位置のビットを抽出し、新たにビットマップを生成する。そして、帳票出力装置１００は、分割した新たなビットマップを、分割先として例えば低頻度単語の領域に格納する。帳票出力装置１００は、２つのハッシュ化ビットマップのいずれか１つに対し分割先を設定する。そして、帳票出力装置１００は、ビットマップを分割後に、分割先の各ビットマップに対して、２つのハッシュ値（底）に基づいたそれぞれのハッシュ化ビットマップを生成する。これにより、帳票出力装置１００は、ハッシュ化ビットマップのデータが衝突する場合であっても、ハッシュ化前のビットマップの偶数番目のデータと奇数番目のデータとを分割してそれぞれハッシュ化することで、データの衝突を回避することが可能となる。

また、実施例に係る帳票出力装置１００は、隣接した複数のハッシュ値（底）を基に、例えば、２次元（単語ＩＤの軸とファイルＩＤの軸）、および３次元（単語ＩＤの軸とファイルＩＤの軸と文字列の位置の軸、帳票の項目の軸とファイルＩＤと帳票の項目の位置の軸）にハッシュ化を適用したハッシュ化インデックスを生成すると説明した。しかしながら、帳票出力装置１００は、ファイルの軸に代えてブロックの軸としても良い。すなわち、単語ＩＤの存否情報は、ブロック単位であるとしても良い。

また、実施例に係る帳票出力装置１００は、検索対象の文字列が日本語である場合、１文字ごとに、単語ＩＤを設定し、ビットマップ型インデックスを生成した。しかしながら、帳票出力装置１００は、単語ごとに、単語ＩＤを設定し、ビットマップ型インデックスを生成しても良い。

また、実施例に示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。

［ハードウェア構成］
下記に、上述の実施形態に用いられるハードウェア、およびソフトウェアについて説明する。図２０は、コンピュータ１のハードウェア構成例を示す図である。コンピュータ１は、例えば、プロセッサ３０１、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）３０２、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）３０３、ドライブ装置３０４、記憶媒体３０５、入力インターフェース（Ｉ／Ｆ）３０６、入力デバイス３０７、出力インターフェース（Ｉ／Ｆ）３０８、出力デバイス３０９、通信インターフェース（Ｉ／Ｆ）３１０、ＳＡＮ（Ｓｔｏｒａｇｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）インターフェース（Ｉ／Ｆ）３１１、およびバス３１２などを含む。それぞれのハードウェアはバス３１２を介して接続されている。

ＲＡＭ３０２は読み書き可能なメモリ装置であって、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ ＲＡＭ）やＤＲＡＭ（Ｄｙｎａｍｉｃ ＲＡＭ）などの半導体メモリ、またはＲＡＭでなくてもフラッシュメモリなどが用いられる。ＲＯＭ３０３は、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ ＲＯＭ）なども含む。ドライブ装置３０４は、記憶媒体３０５に記録された情報の読み出しか書き込みかの少なくともいずれか一方を行なう装置である。記憶媒体３０５は、ドライブ装置３０４によって書き込まれた情報を記憶する。記憶媒体３０５は、例えば、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｒｉｖｅ）などのフラッシュメモリ、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）、ブルーレイディスクなどの記憶媒体である。また、例えば、コンピュータ１は、複数種類の記憶媒体それぞれについて、ドライブ装置３０４、および記憶媒体３０５を設ける。

入力インターフェース３０６は、入力デバイス３０７と接続されており、入力デバイス３０７から受信した入力信号をプロセッサ３０１に伝達する回路である。出力インターフェース３０８は、出力デバイス３０９と接続されており、出力デバイス３０９に、プロセッサ３０１の指示に応じた出力を実行させる回路である。通信インターフェース３１０はネットワーク３を介した通信の制御を行なう回路である。通信インターフェース３１０は、例えばネットワークインターフェースカード（ＮＩＣ）などである。ＳＡＮインターフェース３１１は、ストレージエリアネットワークによりコンピュータ１と接続された記憶装置との通信の制御を行なう回路である。ＳＡＮインターフェース３１１は、例えばホストバスアダプタ（ＨＢＡ）などである。

入力デバイス３０７は、操作に応じて入力信号を送信する装置である。入力信号は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力デバイス３０９は、コンピュータ１の制御に応じて情報を出力する装置である。出力デバイス３０９は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力デバイス３０７、および出力デバイス３０９として用いられる。また、入力デバイス３０７、および出力デバイス３０９は、コンピュータ１と一体になっていても良いし、コンピュータ１に含まれず、例えば、コンピュータ１に外部から接続する装置であっても良い。

例えば、プロセッサ３０１は、ＲＯＭ３０３や記憶媒体３０５に記憶されたプログラムをＲＡＭ３０２に読み出し、読み出されたプログラムの手順に従って制御部１１０、２１０の処理を行なう。その際にＲＡＭ３０２はプロセッサ３０１のワークエリアとして用いられる。記憶部１２０、２２０の機能は、ＲＯＭ３０３および記憶媒体３０５がプログラムファイル（後述のアプリケーションプログラムＡＰ２４、ミドルウェアＭＷ２３およびＯＳ２２など）やデータファイル（例えば、符号化辞書１２１、２２１、２次元ハッシュ化インデックス１２２、２２２、第１の３次元ハッシュ化インデックス１２３、２２３など）を記憶し、ＲＡＭ３０２がプロセッサ３０１のワークエリアとして用いられることによって実現される。プロセッサ３０１が読み出すプログラムについては、図２１を用いて説明する。

図２１は、コンピュータで動作するプログラムの構成例を示す図である。コンピュータ１において、図２１に示すハードウェア群ＨＷ２１（３０１〜３１２）の制御を行なうＯＳ（オペレーティング・システム）２２が動作する。ＯＳ２２に従った手順でプロセッサ３０１が動作して、ハードウェア群ＨＷ２１の制御・管理が行なわれることにより、アプリケーションプログラムＡＰ２４やミドルウェアＭＷ２３に従った処理がハードウェア群ＨＷ２１で実行される。さらに、コンピュータ１において、ミドルウェアＭＷ２３またはアプリケーションプログラムＡＰ２４が、ＲＡＭ３０２に読み出されてプロセッサ３０１により実行される。

プロセッサ３０１が、帳票生成機能が呼び出された場合に、ミドルウェアＭＷ２３またはアプリケーションプログラムＡＰ２４の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェアＨＷ群２１を制御して）制御部１１０の機能が実現される。プロセッサ３０１が、検索機能が呼び出された場合に、ミドルウェアＭＷ２３またはアプリケーションプログラムＡＰ２４の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェアＨＷ群２１を制御して）制御部２１０の機能が実現される。符号化機能および検索機能は、アプリケーションプログラムＡＰ２４自体に含まれても良いし、アプリケーションプログラムＡＰ２４に従って呼び出されることで実行されるミドルウェアＭＷ２３の一部であっても良い。

図２２は、実施例のシステムにおける装置の構成例を示す図である。図２２のシステムは、コンピュータ１ａ、コンピュータ１ｂ、基地局２およびネットワーク３を含む。コンピュータ１ａは、無線または有線の少なくとも一方により、コンピュータ１ｂと接続されたネットワーク３に接続している。

帳票出力装置１００と検索装置２００とは、図２２に示すコンピュータ１ａとコンピュータ１ｂとのいずれに含まれても良い。コンピュータ１ｂが帳票出力装置１００の機能を含み、コンピュータ１ａが検索装置２００の機能を含んでも良いし、コンピュータ１ａが帳票出力装置１００の機能を含み、コンピュータ１ｂが検索装置２００の機能を含んでも良い。また、コンピュータ１ａとコンピュータ１ｂとの双方が、帳票出力装置１００の機能および検索装置２００の機能を備えても良い。

１００ 帳票出力装置
１１０ 制御部
１１１ 帳票出力形式データ生成部
１１２ 符号化処理部
１１２ａ 符号化部
１１２ｂ インデックス生成部
１１３ 埋込部
１１４ 出力部
１２０ 記憶部
１２１ 符号化辞書
１２２ ２次元ハッシュ化インデックス
１２３ 第１の３次元ハッシュ化インデックス
１２４ 第２の３次元ハッシュ化インデックス
２００ 検索装置
２１１ 検索対象受付部
２１２ 第１の復元部
２１３ 第２の復元部
２１４ 検索処理部
２１５ 検索結果出力部
２２０ 記憶部
２２１ 符号化辞書
２２２ ２次元ハッシュ化インデックス
２２３ 第１の３次元ハッシュ化インデックス
２２４ 第２の３次元ハッシュ化インデックス
２２５ 第１の復元ビットマップ
２２６ 第２の復元ビットマップ
２２７ 第３の復元ビットマップ
２２８ 絞込みビットマップ

Claims (9)

1. コンピュータに、
   複数のカラムを有する帳票を含む帳票データから帳票出力形式データを生成し、
   単語、文字、または数値に対するインデックス情報であって、前記複数のカラムそれぞれの属性と、前記帳票出力形式データに含まれる前記複数のカラムそれぞれに対応したデータ相互の前記帳票データにおける位置関係とを特定可能な位置情報を含む前記インデックス情報を生成し、
   前記インデックス情報、および前記帳票出力形式データを含む出力ファイルを出力する
   処理を実行させることを特徴とするインデックス付きデータ生成プログラム。
2. 前記出力ファイルは、前記出力ファイルの拡張領域に、前記帳票出力形式データが符号化された符号化データ、および前記インデックス情報を含む
   ことを特徴とする請求項１に記載のインデックス付きデータ生成プログラム。
3. 前記符号化データは、前記帳票出力形式データが、前記帳票の属性ごとに、符号化されたデータである
   ことを特徴とする請求項２に記載のインデックス付きデータ生成プログラム。
4. 前記インデックス情報は、前記単語、前記文字、または前記数値と、前記帳票のファイル情報と、前記位置情報とを軸とするビットマップ型転置インデックス情報である
   ことを特徴とする請求項１〜３の何れか１つに記載のインデックス付きデータ生成プログラム。
5. コンピュータが、
   複数のカラムを有する帳票を含む帳票データから帳票出力形式データを生成し、
   単語、文字、または数値に対するインデックス情報であって、前記複数のカラムそれぞれの属性と、前記帳票出力形式データに含まれる前記複数のカラムそれぞれに対応したデータ相互の前記帳票データにおける位置関係とを特定可能な位置情報を含む前記インデックス情報を生成し、
   前記インデックス情報、および前記帳票出力形式データを含む出力ファイルを出力する
   処理を実行させることを特徴とするインデックス付きデータ生成方法。
6. 複数のカラムを有する帳票を含む帳票データから帳票出力形式データを生成する第１生成部と、
   単語、文字、または数値に対するインデックス情報であって、前記複数のカラムそれぞれの属性と、前記帳票出力形式データに含まれる前記複数のカラムそれぞれに対応したデータ相互の前記帳票データにおける位置関係とを特定可能な位置情報を含む前記インデックス情報を生成する第２生成部と、
   前記インデックス情報、および前記帳票出力形式データを含む出力ファイルを出力する出力部と
   を有することを特徴とするインデックス付きデータ生成システム。
7. コンピュータに、
   単語、文字、数値を組み合わせた検索対象の文字列を受け付け、
   単語、文字、または数値に対するインデックス情報であって、複数のカラムそれぞれの属性と、前記複数のカラムを有する帳票を含む帳票データから生成された帳票出力形式データに含まれる前記複数のカラムそれぞれに対応したデータ相互の前記帳票データにおける位置関係とを特定可能な位置情報を含む前記インデックス情報を参照して、前記検索対象の文字列に含まれる前記単語、前記文字、前記数値が前記帳票出力形式データに含まれ、かつ、位置関係が前記検索対象の文字列と一致するかを判別する
   処理を実行させることを特徴とする検索プログラム。
8. コンピュータが、
   単語、文字、数値を組み合わせた検索対象の文字列を受け付け、
   単語、文字、または数値に対するインデックス情報であって、複数のカラムそれぞれの属性と、前記複数のカラムを有する帳票を含む帳票データから生成された帳票出力形式データに含まれる複数のカラムそれぞれに対応したデータ相互の前記帳票データにおける位置関係とを特定可能な位置情報を含む前記インデックス情報を参照して、前記検索対象の文字列に含まれる前記単語、前記文字、前記数値が前記帳票出力形式データに含まれ、かつ、位置関係が前記検索対象の文字列と一致するかを判別する
   処理を実行させることを特徴とする検索方法。
9. 単語、文字、数値を組み合わせた検索対象の文字列を受け付ける受付部、
   単語、文字、または数値に対するインデックス情報であって、複数のカラムそれぞれの属性と、前記複数のカラムを有する帳票を含む帳票データから生成された帳票出力形式データに含まれる複数のカラムそれぞれに対応したデータ相互の前記帳票データにおける位置関係とを特定可能な位置情報を含む前記インデックス情報を参照して、前記検索対象の文字列に含まれる前記単語、前記文字、前記数値が前記帳票出力形式データに含まれ、かつ、位置関係が前記検索対象の文字列と一致するかを判別する判別部と
   を有することを特徴とする検索システム。

Images