(57)【特許請求の範囲】
【請求項１】
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースと、
前記複数のフィールドのうちの特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ列が前記特定のフィールドに登録された前記データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部と、
検索に用いられる前記データ列を示す検索データ列を受け付ける受付部と、
前記検索データ列のハッシュ値を算出する算出部と、
前記検索データ列の一部と一致する前記部分データ列が前記索引記憶部に存在するか否かを判定する第１判定部と、
前記第１判定部により、前記検索データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定された場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第２判定部と、
前記第２判定部により、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定された場合は、当該部分データ列に対応する前記位置情報を取得する取得部と、を備える、
ことを特徴とする検索装置。
【請求項２】
前記索引情報の登録を行う前記データ情報の特定のフィールドに登録された前記データ列を示す登録データ列の一部と、前記索引記憶部に登録済みの前記部分データ列との競合度合いに応じて、前記登録データ列の前記部分データ列のデータ長を可変に設定する設定部をさらに備える、
ことを特徴とする請求項１に記載の検索装置。
【請求項３】
前記受付部は、前記索引情報の登録を行う前記データ情報を受け付け、
前記受付部が、前記データ情報を受け付けた場合、前記登録データ列と、当該データ情報の前記位置情報を特定する特定部と、
前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在するか否かを判定する第３判定部と、
前記第３判定部により、前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定された場合は、当該部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致するか否かを判定する第４判定部と、
前記第３判定部により前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在しないと判定された場合、または、前記第４判定部により前記部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致しないと判定された場合は、所定の規則に従って、前記索引情報の登録場所を決定する決定部と、
前記決定部により決定された登録場所に前記索引情報を登録する登録部と、を備え、
前記設定部は、前記第４判定部により前記部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致しないと判定された場合は、前記登録データ列の前記部分データ列のデータ長を、前記登録データ列の一部と一致する前記部分データ列のデータ長よりも大きい値に設定する、
ことを特徴とする請求項２に記載の検索装置。
【請求項４】
前記複数のデータ情報の各々は、文書を示す情報である、
ことを特徴とする請求項１に記載の検索装置。
【請求項５】
前記データベースは、前記複数のデータ情報が並列に配置されるテーブルデータを記憶する、
ことを特徴とする請求項１に記載の検索装置。
【請求項６】
前記位置情報は、前記データ情報における前記特定フィールドの位置も特定する、
ことを特徴とする請求項１に記載の検索装置。
【請求項７】
コンピュータが、検索に用いられるデータ列を示す検索データ列を受け付ける第１ステップと、
コンピュータが、前記検索データ列のハッシュ値を算出する第２ステップと、
コンピュータが、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検索データ列の一部と一致する前記部分データ列が存在するか否かを判定する第３ステップと、
コンピュータが、前記第３ステップで、前記検索データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第４ステップと、
コンピュータが、前記第４ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第５ステップと、を備える、
ことを特徴とする検索方法。
【請求項８】
検索に用いられるデータ列を示す検索データ列を受け付ける第１ステップと、
前記検索データ列のハッシュ値を算出する第２ステップと、
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検索データ列の一部と一致する前記部分データ列が存在するか否かを判定する第３ステップと、
前記第３ステップで、前記検索データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第４ステップと、
前記第４ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第５ステップと、をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法およびプログラムに関する。
【背景技術】
【０００２】
従来、例えばＢ木などのデータ構造からなる索引（インデックス）が格納された索引記憶部を備え、索引記憶部から読み出した索引を用いて、所望のデータをデータベースから検索する検索装置が知られている。索引記憶部が保持するデータ量が少ないほど、検索時の読み出し量が少なくなるので、検索速度を高速化することが可能になる。このため、索引記憶部が保持するデータ量は少ないことが望まれる。
【０００３】
例えば、データベースに格納されたテーブルの特定のフィールドの各行に登録されたデータ（キー）と、当該キーの登録場所を示す情報（バリュー）とが格納されるＢ木のリーフノードにおけるキーの格納領域を減らす技術が知られている。この技術では、リーフノードは２層化され、第１層目のデータ構造体には、キーと、当該キーに対応する第２層目のデータ構造体の位置を示す情報（ポインタ）とが格納される。そして、第２層目のデータ構造体には、当該キーに対応する全てのバリューが格納される。例えば、テーブルの特定のフィールドの第２行目および第５行目の各々に当該キーが登録されている場合は、第２行目を示すバリューと第５行目を示すバリューとが、当該キーに対応する第２層目の構造体に格納される。一方、第１層目のデータ構造体に格納される当該キーの数は１つで済むので、結果として、リーフノードにおけるキーの格納領域が低減されるという具合である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−７２８２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した技術では、同値のキーが殆ど存在しない場合には、索引記憶部は全てのキーを保持する必要があるので、索引記憶部が保持するデータ量を低減することはできないという問題がある。本発明が解決しようとする課題は、索引記憶部が保持するデータ量を低減可能な検索装置、検索方法およびプログラムを提供することである。
【課題を解決するための手段】
【０００６】
実施形態の検索装置は、データベースと、索引記憶部と、受付部と、算出部と、第１判定部と、第２判定部と、取得部とを備える。データベースは、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶する。索引記憶部は、複数のフィールドのうちの特定のフィールドに登録されたデータ列の一部である部分データ列と、データ列のハッシュ値と、当該データ列が特定のフィールドに登録されたデータ情報のデータベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する。受付部は、検索データ列を受け付ける。算出部は、検索データ列のハッシュ値を算出する。第１判定部により、検索データ列の一部と一致する部分データ列が索引記憶部に存在すると判定され、第２判定部により、当該部分データ列に対応するハッシュ値と、検索データ列のハッシュ値とが一致すると判定された場合は、取得部は、当該部分データ列に対応する位置情報を取得する。
【０００７】
また、実施形態の検索方法は、検索に用いられるデータ列を示す検索データ列を受け付ける第１ステップと、前記検索データ列のハッシュ値を算出する第２ステップと、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検索データ列の一部と一致する前記部分データ列が存在するか否かを判定する第３ステップと、前記第３ステップで、前記検索データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第４ステップと、前記第４ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第５ステップと、を備えることを特徴とする。
【０００８】
さらに、実施形態のプログラムは、検索に用いられるデータ列を示す検索データ列を受け付ける第１ステップと、前記検索データ列のハッシュ値を算出する第２ステップと、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検索データ列の一部と一致する前記部分データ列が存在するか否かを判定する第３ステップと、前記第３ステップで、前記検索データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第４ステップと、前記第４ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第５ステップと、をコンピュータに実行させるためのプログラムである。
【図面の簡単な説明】
【０００９】
【図１】第１実施形態の検索装置の一例を示すブロック図。
【図２】データベース部の一例を示す図。
【図３】データ情報の一例を示す図。
【図４】索引記憶部の一例を示す図。
【図５】検索処理の一例を示すフローチャート
【図６】登録処理の一例を示すフローチャート。
【図７】削除処理の一例を示すフローチャート。
【図８】第２実施形態の索引記憶部の一例を示す図。
【図９】第２実施形態の検索装置の一例を示すブロック図。
【図１０】登録処理の一例を示す図。
【図１１】変形例を説明するための図。
【発明を実施するための形態】
【００１０】
（第１実施形態）
図１は、第１実施形態の検索装置１００の概略構成の一例を示すブロック図である。図１に示すように、検索装置１００は、操作表示部１０と、記憶部２０と、制御部３０とを備える。操作表示部１０は、各種画面や検索装置１００に関する情報（例えば検索結果等）を表示するとともに、ユーザーが各種の操作入力を行うための手段である。詳細な図示は省略するが、操作表示部１０は、各種画面や検索装置１００に関する情報を表示するとともにユーザーからのタッチ入力を受け付ける表示パネルと、例えば各種ボタンやマウスなどの操作デバイスとを備える。
【００１１】
記憶部２０は、データベース部２２と索引記憶部２４とを含む。データベース部２２は、複数のフィールドを各々が有する複数のデータ情報を記憶する。図２に示すように、データベース部２２は、複数のデータ情報ＤＱを記憶する。ここでは、データ情報ＤＱは文書を示す情報であり、一例として、ＸＭＬ（Extensible Markup Language）で記述された半構造化データがデータ情報ＤＱとして採用されている。
【００１２】
図３は、データ情報ＤＱの一例を示す図である。図３に示すように、データ情報ＤＱは、それぞれにデータ列が登録される複数のフィールドＦを有している。本実施形態では、各データ情報ＤＱが有する複数のフィールドＦのうちの特定のフィールドＦｘに対してのみ索引が作成される。詳細な内容については後述する。ここでは、各データ情報ＤＱの特定のフィールドＦｘは、アプリケーション名（application-title）を構成する文字列（データ列）が登録されるフィールドである。
【００１３】
図１に戻って説明を続ける。索引記憶部２４は、索引（インデックス）を記憶する。索引は、例えばＢ木などのデータ構造である。本実施形態では、索引としてＢ木が用いられるが、これに限らず、索引の種類は任意である。例えばビットマップインデックスや関数インデックスなどを採用することもできる。図４に示すように、索引記憶部２４は、最上位層のルートノード２５と、中間層のブランチノード２６と、最下層のリーフノード２７とを含む。リーフノード２７は、アプリケーション名を構成する文字列の一部である部分文字列と、当該アプリケーション名を構成する文字列のハッシュ値と、当該アプリケーション名が特定のフィールドＦｘに登録されたデータ情報ＤＱのデータベース部２２における位置を示すＩＤ（位置情報）とが対応付けられた索引情報を行ごとに記憶する。本実施形態のＩＤ（位置情報）は、データベース部２２におけるデータ情報ＤＱの位置だけでなく、当該データ情報ＤＱにおける特定のフィールドＦｘの位置も特定する情報である。また、本実施形態では、部分文字列のデータ長は固定長である。ここでは、一例として１０文字分のデータ長に設定されるが、これに限定されるものではない。
【００１４】
図１に示す制御部３０は、検索装置１００の各部を制御する手段であり、ＣＰＵ（Central Processing Unit）、ＲＯＭ（Read  Only  Memory）、および、ＲＡＭ(Random  Access  Memory)などを含む制御装置で構成される。制御部３０が有する機能としては、
受付部３１、リーフノード特定部３２、算出部３３、第１判定部３４、第２判定部３５、取得部３６、特定部３７、第３判定部３８、第４判定部３９、登録部４０、決定部４１、削除対象特定部４２、削除部４３がある。以上の機能（３１、３２、３３、３４、３５、３６、３７、３８、３９、４０、４１、４２、４３）は、ＣＰＵが、ＲＯＭに格納された制御プログラムをＲＡＭ上に読み出して実行することにより実現される。なお、これに限らず、以上の機能（３１、３２、３３、３４、３５、３６、３７、３８、３９、４０、４１、４２、４３）のうちの少なくとも一部がハードウェア回路で実現されてもよい。
【００１５】
受付部３１は、操作表示部１０からの各種入力を受け付ける。例えば、受付部３１は、検索に用いられるアプリケーション名を構成する文字列（検索文字列と呼ぶ）の入力を受け付けることもできるし、索引情報の登録を行うデータ情報ＤＱの入力を受け付けることもできる。また、削除を行うデータ情報ＤＱの入力を受け付けることもできる。リーフノード特定部３２は、入力された文字列に対応するリーフノード２７を特定する。算出部３３は、入力された文字列のハッシュ値を算出する。
【００１６】
第１判定部３４は、検索文字列の一部と一致する部分文字列が索引記憶部２４（リーフノード２７）に存在するか否かを判定する。第２判定部３５は、第１判定部３４により、検索文字列の一部と一致する部分文字列が索引記憶部２４に存在すると判定された場合は、当該部分文字列に対応するハッシュ値と、検索文字列のハッシュ値とが一致するか否かを判定する。取得部３６は、第２判定部３５により、部分文字列に対応するハッシュ値と、検索文字列のハッシュ値とが一致すると判定された場合は、当該部分文字列に対応するＩＤを索引記憶部２４（リーフノード２７）から取得する。また、取得部３６は、当該ＩＤで特定されるデータ情報ＤＱをデータベース部２２から取得することもできる。
【００１７】
上述の受付部３１、リーフノード特定部３２、算出部３３、第１判定部３４、第２判定部３５、取得部３６は、後述の検索処理を実行する検索処理部であると捉えることもできる。検索処理の詳細な内容については後述する。
【００１８】
特定部３７は、索引情報の登録を行うデータ情報ＤＱの入力を受付部３１で受け付けた場合、当該データ情報ＤＱの特定のフィールドＦｘに登録されたアプリケーション名を構成する文字列（登録文字列と呼ぶ）と、当該データ情報ＤＱのＩＤ（位置情報）とを特定する。第３判定部３８は、登録文字列の一部と一致する部分文字列が索引記憶部２４（リーフノード２７）に存在するか否かを判定する。第４判定部３９は、第３判定部３８により、登録文字列の一部と一致する部分文字列が索引記憶部２４に存在すると判定された場合は、当該部分文字列に対応するハッシュ値と、登録文字列のハッシュ値とが一致するか否かを判定する。
【００１９】
登録部４０は、登録文字列の部分文字列と、当該登録文字列のハッシュ値と、特定部３７で特定されたＩＤとを対応付けた索引情報を、索引記憶部２４（リーフノード２７）に登録する。
【００２０】
決定部４１は、第３判定部３８により登録文字列の一部と一致する部分文字列が索引記憶部２４に存在しないと判定された場合、または、第４判定部３９により部分文字列に対応するハッシュ値と、登録文字列のハッシュ値とが一致しないと判定された場合は、所定の規則に従って、索引情報の登録場所を決定する。
【００２１】
上述の受付部３１、リーフノード特定部３２、算出部３３、取得部３６、特定部３７、第３判定部３８、第４判定部３９、登録部４０、決定部４１は、後述の登録処理を実行する登録処理部であると捉えることもできる。登録処理の詳細な内容については後述する。
【００２２】
削除対象特定部４２は、索引記憶部２４に記憶された索引情報のうち、削除対象の索引情報を特定する。削除部４３は、削除対象特定部４２で特定された索引情報を索引記憶部２４から削除する。
【００２３】
上述の受付部３１、リーフノード特定部３２、算出部３３、削除対象特定部４２、削除部４３は、後述の削除処理を実行する削除処理部であると捉えることもできる。削除処理の詳細な内容については後述する。
【００２４】
次に、制御部３０が実行する検索処理について説明する。図５は、検索処理の一例を示すフローチャートである。図５に示すように、まず、検索文字列の入力を受付部３１で受け付けると（ステップＳ５１１）、リーフノード特定部３２は、検索文字列に対応するリーフノード２７を特定する（ステップＳ５１２）。本実施形態では、リーフノード特定部３２は、Ｂ木をたどって、対応するリーフノード２７を特定する。より具体的には以下のとおりである。いま、図４に示すように、「データベース管理システム」という文字列を検索文字列として受け付けた場合を想定する。まずルートノード２５では、「データベース管理システム」に対応するブランチノード２６が特定される。ここでは、５０音の各行（あ行、か行、・・・、わ行）ごとに、ブランチノード２６が割り当てられており、検索文字列の先頭の文字が、５０音の各行のうちの何れに属するかに応じて、対応するブランチノード２６が特定される。「データベース管理システム」は、先頭の文字が「デ」であり、「た行」に属するとみなされるので、「データベース管理システム」に対応するブランチノード２６として、「た行」に対応するブランチノード２６が特定される。
【００２５】
図４に示すように、ブランチノード２６には、当該ブランチノード２６に割り当てられた複数の文字列（ここでは一例として２文字分の文字列）ごとに、当該文字列に対応するリーフノード２７の位置を示すポインタが格納される。「データベース管理システム」の先頭から数えて２文字分の文字列は「デー」であるので、「デー」に対応するポインタ「ｅｅｅ」で示されるリーフノード２７が、「データベース管理システム」に対応するリーフノード２７となる。以上のようにして、「データベース管理システム」に対応するリーフノード２７が特定される。なお、上述の例に限らず、検索文字列に対応するリーフノード２７の特定方法は任意である。
【００２６】
次に、第１判定部３４は、検索文字列の一部と一致する部分文字列がリーフノード２７に存在するか否かを判定する（ステップＳ５１３）。例えば、検索文字列が「データベース管理システム」の場合、図４のリーフノード２７の第６行目の索引情報および第７行目の索引情報の各々の部分文字列（「データベース管理シス」）が、「データベース管理システム」の一部と一致するので、ステップＳ５１３の結果は肯定となる。検索文字列の一部と一致する部分文字列がリーフノード２７に存在すると判定された場合、算出部３３は、検索文字列のハッシュ値を算出する（ステップＳ５１４）。一方、検索文字列の一部と一致する部分文字列がリーフノード２７に存在しないと判定された場合、検索処理は終了する。
【００２７】
上述のステップＳ５１４の後、第２判定部３５は、検索文字列のハッシュ値と、検索文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、検索文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する（ステップＳ５１５）。例えば検索文字列が「データベース管理システム」の場合、図４のリーフノード２７の第６行目の索引情報のハッシュ値（Ｈ（データベース管理システム））は、検索文字列（「データベース管理システム」）のハッシュ値と一致する一方、第７行目の索引情報のハッシュ値（Ｈ（データベース管理システムの実行情報を取得する手段を有する記憶装置））は、検索文字列（「データベース管理システム」）のハッシュ値と一致しない。
【００２８】
上述のステップＳ５１５において、検索文字列のハッシュ値と一致するハッシュ値を含む索引情報があると判定された場合、取得部３６は、当該索引情報のＩＤを取得する（ステップＳ５１６）。次に、取得部３６は、データベース部２２から、その取得したＩＤで特定されるデータ情報ＤＱを取得して操作表示部１０に表示する（ステップＳ５１７）。一方、上述のステップＳ５１５において、検索文字列のハッシュ値と一致する索引情報は存在しないと判定された場合、検索処理は終了する。
【００２９】
次に、制御部３０が実行する登録処理について説明する。図６は、登録処理の一例を示すフローチャートである。図６に示すように、まず、索引情報の登録を行うデータ情報ＤＱの入力を受付部３１で受け付けると（ステップＳ６１１）、特定部３７は、その受け付けたデータ情報ＤＱの特定のフィールドＦｘに登録されたアプリケーション名を構成する文字列（登録文字列と呼ぶ）と、当該データ情報ＤＱのＩＤ（位置情報）を特定する（ステップＳ６１２）。次に、リーフノード特定部３２は、登録文字列に対応するリーフノード２７を特定する（ステップＳ６１３）。この特定方法は、検索文字列に対応するリーフノード２７の特定方法と同様であるので、詳細な説明は省略する。
【００３０】
次に、第３判定部３８は、登録文字列の一部と一致する部分文字列がリーフノード２７に存在するか否かを判定する（ステップＳ６１４）。ステップＳ６１４において、登録文字列の一部と一致する部分文字列がリーフノード２７に存在しないと判定された場合、決定部４１は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定し（ステップＳ６１５）、処理は後述のステップＳ６２０に移行する。いま、登録文字列が「データ抽出装置、抽出方法およびプログラム」であって、登録文字列の５０音順に挿入場所が決定される場合を想定する。図４の例では、登録文字列「データ抽出装置、抽出方法およびプログラム」は、第３行目の索引情報と第４行目の索引情報との間に挿入されることが決定される。なお、これに限らず、所定の規則は任意に設定可能である。
【００３１】
一方、上述のステップＳ６１４において、登録文字列の一部と一致する部分文字列がリーフノード２７に存在すると判定された場合、算出部３３は、登録文字列のハッシュ値を算出する（ステップＳ６１６）。次に、第４判定部３９は、登録文字列のハッシュ値と、登録文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する（ステップＳ６１７）。
【００３２】
上述のステップＳ６１７において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、取得部３６は、登録文字列の一部と一致する部分文字列に対応するＩＤで特定されるデータ情報ＤＱをデータベース部２２から取得し、当該データ情報ＤＱの特定のフィールドＦｘに登録されたアプリケーション名を構成する文字列を取得する（ステップＳ６１８）。例えば、図４の例において、登録文字列が「データベース管理システムおよびプログラム」の場合を想定する。この場合、第６行目の索引情報および第７行目の索引情報の各々の部分文字列（「データベース管理シス」）が、登録文字列の一部と一致するものの、ハッシュ値は一致しない。したがって、取得部３６は、第６行目の索引情報および第７行目の索引情報に含まれるＩＤで特定されるデータ情報ＤＱをそれぞれ取得するとともに、当該各データ情報ＤＱにおける特定のフィールドＦｘに登録されたアプリケーション名を構成する文字列を取得する。
【００３３】
次に、決定部４１は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定し（ステップＳ６１９）、処理は後述のステップＳ６２０に移行する。いま、登録文字列が「データベース管理システムおよびプログラム」であって、登録文字列の５０音順に挿入場所が決定される場合を想定する。図４の例では、登録文字列「データベース管理システムおよびプログラム」は、第６行目の索引情報と第７行目の索引情報との間に挿入されることが決定される。なお、これに限らず、所定の規則は任意に設定可能である。
【００３４】
ステップＳ６２０では、登録部４０は、決定部４１により決定された挿入場所に、登録文字列の部分文字列と、当該登録文字列のハッシュ値と、特定部３７で特定されたＩＤとを対応付けた索引情報を登録する。例えば登録文字列が「データベース管理システムおよびプログラム」である場合、先頭から１０文字分のデータ長の「データベース管理シス」と、「データベース管理システムおよびプログラム」のハッシュ値と、「データベース管理システムおよびプログラム」が特定のフィールドＦｘに登録されたデータ情報ＤＱのＩＤ（特定部３７で特定されたＩＤ）とが対応付けられた索引情報が、決定部４１により決定された挿入場所に登録される。
【００３５】
一方、上述のステップＳ６１７において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在すると判定された場合、登録部４０は、リーフノード２７（索引記憶部２４）のうち、当該索引情報が記憶される行の直後の行または直前の行に、登録文字列の部分文字列と、登録文字列のハッシュ値と、特定部３７で特定されたＩＤとを対応付けた索引情報を登録する（ステップＳ６２０）。
【００３６】
次に、制御部３０が実行する削除処理について説明する。図７は、削除処理の一例を示すフローチャートである。図７に示すように、まず、削除を行うデータ情報ＤＱの入力を受付部３１で受け付けると（ステップＳ７１１）、特定部３７は、その受け付けたデータ情報ＤＱの特定のフィールドＦｘに登録されたアプリケーション名を構成する文字列（削除文字列と呼ぶ）と、当該データ情報ＤＱのＩＤ（位置情報）を特定する（ステップＳ７１２）。次に、リーフノード特定部３２は、削除文字列に対応するリーフノード２７を特定する（ステップＳ７１３）。
【００３７】
次に、削除対象特定部４２は、リーフノード２７に記憶された索引情報のうち削除対象となる索引情報を特定する（ステップＳ７１４）。より具体的には、削除対象特定部４２は、削除文字列のハッシュ値と一致するハッシュ値を含む索引情報を、削除対象の索引情報として特定する。次に、削除部４３は、削除対象特定部４２で特定された索引情報をリーフノード２７から削除する（ステップＳ７１５）。
【００３８】
以上に説明したように、本実施形態では、データ情報ＤＱの特定のフィールドＦｘに登録されたアプリケーション名を構成する文字列（データ列）を、そのまま索引記憶部２４に登録することはせずに、アプリケーション名を構成する文字列の一部の部分文字列と、当該文字列のハッシュ値と、ＩＤ（位置情報）とを対応付けて索引記憶部２４に記憶するので、索引記憶部２４が保持するデータ量を低減できる。したがって、本実施形態によれば、検索時の読み出し量が少なくなるので、検索速度を高速化することが可能になるという有利な効果を奏する。
【００３９】
（第２実施形態）
次に第２実施形態について説明する。第２実施形態では、図８に示すように、索引記憶部２４（リーフノード２７）に記憶される部分文字列のデータ長は可変に設定される点で上述の第１実施形態と相違する。その他は、第１実施形態と同じであるので、重複する部分については説明を省略する。
【００４０】
図９は、第２実施形態の検索装置１００の概略構成の一例を示すブロック図である。図９に示すように、制御部３０が有する機能の中に設定部４４が含まれる点で第１実施形態と相違する。設定部４４は、索引記憶部２４（リーフノード２７）に登録する部分文字列のデータ長を可変に設定するとともに、登録する部分文字列を設定する。
【００４１】
図１０は、第２実施形態における登録処理の一例を示すフローチャートである。なお、検索処理および削除処理は、上述の第１実施形態と同じであるので、ここでは説明を省略する。図１０のステップＳ９１１〜ステップＳ９１４の内容は、図６のステップＳ６１１〜ステップＳ６１４の内容と同じであるので、詳細な説明は省略する。
【００４２】
図１０のステップＳ９１４において、登録文字列の一部と一致する部分文字列がリーフノード２７に存在しないと判定された場合、決定部４１は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定する（ステップＳ９１５）。ステップＳ９１５の内容は図６のステップＳ６１５の内容と同じであるので、詳細な説明は省略する。ステップＳ９１５の後、設定部４４は、登録文字列のデータ長を１文字分のデータ長に設定する。そして、登録文字列の先頭の文字を部分文字列として設定する（ステップＳ９１６）。例えば登録文字列が「データ抽出装置、抽出方法およびプログラム」の場合、先頭の文字である「デ」が部分文字列として設定される。なお、これに限らず、部分文字列の設定方法は任意であり、例えば先頭の文字から２文字分のデータ列を部分文字列として設定することもできる。ステップＳ９１６の後、処理はステップＳ９２２に移行する。ステップＳ９２２の内容は、図６のステップＳ６２０の内容と同じであるので、詳細な説明は省略する。
【００４３】
上述のステップＳ９１４において、登録文字列の一部と一致する部分文字列がリーフノード２７に存在すると判定された場合、算出部３３は、登録文字列のハッシュ値を算出する（ステップＳ９１７）。次に、第４判定部３９は、登録文字列のハッシュ値と、登録文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する（ステップＳ９１８）。
【００４４】
上述のステップＳ９１８において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、設定部４４は、データ長を拡張して、登録する部分文字列を設定する（ステップＳ９１９）。より具体的には、設定部４４は、登録する部分文字列のデータ長を、登録文字列の一部と一致する部分文字列のデータ長よりも大きい値に設定する。
【００４５】
例えば、図８の例において、登録文字列が「データベース管理システムおよびプログラム」の場合を想定する。この場合、第３行目、第５行目、第６行目および第７行目の各々の索引情報の部分文字列（「データ」、「デ」、「データベ」、「デー」）が、登録文字列の一部と一致するものの、ハッシュ値は一致しない。したがって、設定部４４は、登録する文字列のデータ長を、登録文字列の一部と一致する部分文字列のうちデータ長が最大のものよりも１文字分だけ長い値に設定する。この場合、登録する部分文字列のデータ長は５文字分の長さとなり、設定部４４は、先頭の文字から数えて５文字分のデータ長の「データベー」を、登録する部分文字列として設定する。なお、これは一例であり、登録する部分文字列の設定方法は任意である。要するに、登録する部分文字列として、登録文字列の一部と一致する部分文字列のデータ長よりも長いデータ長の文字列を設定するものであればよい。
【００４６】
ステップＳ９１９の後、処理はステップＳ９２０に移行する。ステップＳ９２０〜ステップＳ９２２の内容は、図６のステップＳ６１８〜ステップＳ６２０の内容と同じであるので、詳細な説明は省略する。
【００４７】
また、上述のステップＳ９１８において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、処理はステップＳ９２２に移行する。図９のステップＳ９２２の内容は、図６のステップＳ６２０の内容と同じであるので、詳細な説明は省略する。
【００４８】
以上に説明したように、本実施形態では、登録文字列の一部と一致する部分文字列がリーフノード２７に存在するものの、当該登録文字列のハッシュ値と一致するハッシュ値を含む索引情報がリーフノード２７に存在しないと判定された場合は、登録する部分文字列のデータ長は拡張される一方、登録文字列の一部と一致する部分文字列がリーフノード２７に存在しないと判定された場合は、登録する部分文字列のデータ長は抑制される（一例として、本実施形態では１文字分のデータ長に抑制される）。すなわち、必要な部分は登録する部分文字列のデータ長を伸ばしつつ、必要の無い部分で登録する部分文字列のデータ長を抑えることにより、索引記憶部２４（リーフノード２７）の容量を削減できるという利点がある。
【００４９】
（変形例）
以上、本発明の実施形態を説明したが、上述の各実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【００５０】
例えば上述の各実施形態では、データベース部２２に記憶されるデータ情報の一例として、文書を示す情報（ドキュメント情報）を挙げて説明したが、これに限らず、データ情報の種類は任意である。例えば図１１に示すように、データ情報は、テーブルデータ２００の各ラインを構成するデータ群Ｇであってもよい。各データ群Ｇ（データ情報）は、それぞれにデータ列が登録される複数のフィールドＦを有する。そして、複数のフィールドＦのうち、特定のフィールドＦｘに対して、上述したような索引を作成することができる。
【００５１】
また、上述の各実施形態では、データ情報ＤＱが有する複数のフィールドＦのうちの特定のフィールドＦｘに対してのみ索引が作成されているが、これに限らず、他のフィールドに対しても、上述の各実施形態と同様の索引を作成することもできる。
【符号の説明】
【００５２】
１０  操作表示部
２０  記憶部
２２  データベース部
２４  索引記憶部
２５  ルートノード
２６  ブランチノード
２７  リーフノード
３０  制御部
３１  受付部
３２  リーフノード特定部
３３  算出部
３４  第１判定部
３５  第２判定部
３６  取得部
３７  特定部
３８  第３判定部
３９  第４判定部
４０  登録部
４１  決定部
４２  削除対象特定部
４３  削除部
４４  設定部
１００  検索装置
２００  テーブルデータ
【図１】
0005462215.tif 000002
【図２】
0005462215.tif 000003
【図３】
0005462215.tif 000004
【図４】
0005462215.tif 000005
【図５】
0005462215.tif 000006
【図６】
0005462215.tif 000007
【図７】
0005462215.tif 000008
【図８】
0005462215.tif 000009
【図９】
0005462215.tif 000010
【図１０】
0005462215.tif 000011
【図１１】
0005462215.tif 000012