検索装置、検索方法およびプログラム
【課題】索引記憶部が保持するデータ量を低減可能な検索装置、検索方法およびプログラムを提供する。
【解決手段】実施形態の検索装置は、データベースと、索引記憶部と、受付部と、算出部と、第1判定部と、第2判定部と、取得部とを備える。データベースは、複数のフィールドをそれぞれが有する複数のデータ情報を記憶する。索引記憶部は、特定のフィールドに登録されたデータ列の一部である部分データ列と、データ列のハッシュ値と、当該データ列が特定のフィールドに登録されたデータ情報の位置を示す位置情報とが対応付けられた索引情報を記憶する。第1判定部により、検察データ列の一部と一致する部分データ列が索引記憶部に存在すると判定され、第2判定部により、当該部分データ列に対応するハッシュ値と、検索データ列のハッシュ値とが一致すると判定された場合は、取得部は、当該部分データ列に対応する位置情報を取得する。
【解決手段】実施形態の検索装置は、データベースと、索引記憶部と、受付部と、算出部と、第1判定部と、第2判定部と、取得部とを備える。データベースは、複数のフィールドをそれぞれが有する複数のデータ情報を記憶する。索引記憶部は、特定のフィールドに登録されたデータ列の一部である部分データ列と、データ列のハッシュ値と、当該データ列が特定のフィールドに登録されたデータ情報の位置を示す位置情報とが対応付けられた索引情報を記憶する。第1判定部により、検察データ列の一部と一致する部分データ列が索引記憶部に存在すると判定され、第2判定部により、当該部分データ列に対応するハッシュ値と、検索データ列のハッシュ値とが一致すると判定された場合は、取得部は、当該部分データ列に対応する位置情報を取得する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、検索装置、検索方法およびプログラムに関する。
【背景技術】
【0002】
従来、例えばB木などのデータ構造からなる索引(インデックス)が格納された索引記憶部を備え、索引記憶部から読み出した索引を用いて、所望のデータをデータベースから検索する検索装置が知られている。索引記憶部が保持するデータ量が少ないほど、検索時の読み出し量が少なくなるので、検索速度を高速化することが可能になる。このため、索引記憶部が保持するデータ量は少ないことが望まれる。
【0003】
例えば、データベースに格納されたテーブルの特定のフィールドの各行に登録されたデータ(キー)と、当該キーの登録場所を示す情報(バリュー)とが格納されるB木のリーフノードにおけるキーの格納領域を減らす技術が知られている。この技術では、リーフノードは2層化され、第1層目のデータ構造体には、キーと、当該キーに対応する第2層目のデータ構造体の位置を示す情報(ポインタ)とが格納される。そして、第2層目のデータ構造体には、当該キーに対応する全てのバリューが格納される。例えば、テーブルの特定のフィールドの第2行目および第5行目の各々に当該キーが登録されている場合は、第2行目を示すバリューと第5行目を示すバリューとが、当該キーに対応する第2層目の構造体に格納される。一方、第1層目のデータ構造体に格納される当該キーの数は1つで済むので、結果として、リーフノードにおけるキーの格納領域が低減されるという具合である。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2010−72823号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、上述した技術では、同値のキーが殆ど存在しない場合には、索引記憶部は全てのキーを保持する必要があるので、索引記憶部が保持するデータ量を低減することはできないという問題がある。本発明が解決しようとする課題は、索引記憶部が保持するデータ量を低減可能な検索装置、検索方法およびプログラムを提供することである。
【課題を解決するための手段】
【0006】
実施形態の検索装置は、データベースと、索引記憶部と、受付部と、算出部と、第1判定部と、第2判定部と、取得部とを備える。データベースは、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶する。索引記憶部は、複数のフィールドのうちの特定のフィールドに登録されたデータ列の一部である部分データ列と、データ列のハッシュ値と、当該データ列が特定のフィールドに登録されたデータ情報のデータベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する。受付部は、検索データ列を受け付ける。算出部は、検索データ列のハッシュ値を算出する。第1判定部により、検察データ列の一部と一致する部分データ列が索引記憶部に存在すると判定され、第2判定部により、当該部分データ列に対応するハッシュ値と、検索データ列のハッシュ値とが一致すると判定された場合は、取得部は、当該部分データ列に対応する位置情報を取得する。
【0007】
また、実施形態の検索方法は、検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、前記検索データ列のハッシュ値を算出する第2ステップと、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、を備えることを特徴とする。
【0008】
さらに、実施形態のプログラムは、検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、前記検索データ列のハッシュ値を算出する第2ステップと、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、をコンピュータに実行させるためのプログラムである。
【図面の簡単な説明】
【0009】
【図1】第1実施形態の検索装置の一例を示すブロック図。
【図2】データベース部の一例を示す図。
【図3】データ情報の一例を示す図。
【図4】索引記憶部の一例を示す図。
【図5】検索処理の一例を示すフローチャート
【図6】登録処理の一例を示すフローチャート。
【図7】削除処理の一例を示すフローチャート。
【図8】第2実施形態の索引記憶部の一例を示す図。
【図9】第2実施形態の検索装置の一例を示すブロック図。
【図10】登録処理の一例を示す図。
【図11】変形例を説明するための図。
【発明を実施するための形態】
【0010】
(第1実施形態)
図1は、第1実施形態の検索装置100の概略構成の一例を示すブロック図である。図1に示すように、検索装置100は、操作表示部10と、記憶部20と、制御部30とを備える。操作表示部10は、各種画面や検索装置100に関する情報(例えば検索結果等)を表示するとともに、ユーザーが各種の操作入力を行うための手段である。詳細な図示は省略するが、操作表示部10は、各種画面や検索装置100に関する情報を表示するとともにユーザーからのタッチ入力を受け付ける表示パネルと、例えば各種ボタンやマウスなどの操作デバイスとを備える。
【0011】
記憶部20は、データベース部22と索引記憶部24とを含む。データベース部22は、複数のフィールドを各々が有する複数のデータ情報を記憶する。図2に示すように、データベース部22は、複数のデータ情報DQを記憶する。ここでは、データ情報DQは文書を示す情報であり、一例として、XML(Extensible Markup Language)で記述された半構造化データがデータ情報DQとして採用されている。
【0012】
図3は、データ情報DQの一例を示す図である。図3に示すように、データ情報DQは、それぞれにデータ列が登録される複数のフィールドFを有している。本実施形態では、各データ情報DQが有する複数のフィールドFのうちの特定のフィールドFxに対してのみ索引が作成される。詳細な内容については後述する。ここでは、各データ情報DQの特定のフィールドFxは、アプリケーション名(application-title)を構成する文字列(データ列)が登録されるフィールドである。
【0013】
図1に戻って説明を続ける。索引記憶部24は、索引(インデックス)を記憶する。索引は、例えばB木などのデータ構造である。本実施形態では、索引としてB木が用いられるが、これに限らず、索引の種類は任意である。例えばビットマップインデックスや関数インデックスなどを採用することもできる。図4に示すように、索引記憶部24は、最上位層のルートノード25と、中間層のブランチノード26と、最下層のリーフノード27とを含む。リーフノード27は、アプリケーション名を構成する文字列の一部である部分文字列と、当該アプリケーション名を構成する文字列のハッシュ値と、当該アプリケーション名が特定のフィールドFxに登録されたデータ情報DQのデータベース部22における位置を示すID(位置情報)とが対応付けられた索引情報を行ごとに記憶する。本実施形態のID(位置情報)は、データベース部22におけるデータ情報DQの位置だけでなく、当該データ情報DQにおける特定のフィールドFxの位置も特定する情報である。また、本実施形態では、部分文字列のデータ長は固定長である。ここでは、一例として10文字分のデータ長に設定されるが、これに限定されるものではない。
【0014】
図1に示す制御部30は、検索装置100の各部を制御する手段であり、CPU(Central Processing Unit)、ROM(Read Only Memory)、および、RAM(Random Access Memory)などを含む制御装置で構成される。制御部30が有する機能としては、
受付部31、リーフノード特定部32、算出部33、第1判定部34、第2判定部35、取得部36、特定部37、第3判定部38、第4判定部39、登録部40、決定部41、削除対象特定部42、削除部43がある。以上の機能(31、32、33、34、35、36、37、38、39、40、41、42、43)は、CPUが、ROMに格納された制御プログラムをRAM上に読み出して実行することにより実現される。なお、これに限らず、以上の機能(31、32、33、34、35、36、37、38、39、40、41、42、43)のうちの少なくとも一部がハードウェア回路で実現されてもよい。
【0015】
受付部31は、操作表示部10からの各種入力を受け付ける。例えば、受付部31は、検索に用いられるアプリケーション名を構成する文字列(検索文字列と呼ぶ)の入力を受け付けることもできるし、索引情報の登録を行うデータ情報DQの入力を受け付けることもできる。また、削除を行うデータ情報DQの入力を受け付けることもできる。リーフノード特定部32は、入力された文字列に対応するリーフノード27を特定する。算出部33は、入力された文字列のハッシュ値を算出する。
【0016】
第1判定部34は、検索文字列の一部と一致する部分文字列が索引記憶部24(リーフノード27)に存在するか否かを判定する。第2判定部35は、第1判定部34により、検索文字列の一部と一致する部分文字列が索引記憶部24に存在すると判定された場合は、当該部分文字列に対応するハッシュ値と、検索文字列のハッシュ値とが一致するか否かを判定する。取得部36は、第2判定部35により、部分文字列に対応するハッシュ値と、検索文字列のハッシュ値とが一致すると判定された場合は、当該部分文字列に対応するIDを索引記憶部24(リーフノード27)から取得する。また、取得部36は、当該IDで特定されるデータ情報DQをデータベース部22から取得することもできる。
【0017】
上述の受付部31、リーフノード特定部32、算出部33、第1判定部34、第2判定部35、取得部36は、後述の検索処理を実行する検索処理部であると捉えることもできる。検索処理の詳細な内容については後述する。
【0018】
特定部37は、索引情報の登録を行うデータ情報DQの入力を受付部31で受け付けた場合、当該データ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(登録文字列と呼ぶ)と、当該データ情報DQのID(位置情報)とを特定する。第3判定部38は、登録文字列の一部と一致する部分文字列が索引記憶部24(リーフノード27)に存在するか否かを判定する。第4判定部39は、第3判定部38により、登録文字列の一部と一致する部分文字列が索引記憶部24に存在すると判定された場合は、当該部分文字列に対応するハッシュ値と、登録文字列のハッシュ値とが一致するか否かを判定する。
【0019】
登録部40は、登録文字列の部分文字列と、当該登録文字列のハッシュ値と、特定部37で特定されたIDとを対応付けた索引情報を、索引記憶部24(リーフノード27)に登録する。
【0020】
決定部41は、第3判定部38により登録文字列の一部と一致する部分文字列が索引記憶部24に存在しないと判定された場合、または、第4判定部39により部分文字列に対応するハッシュ値と、登録文字列のハッシュ値とが一致しないと判定された場合は、所定の規則に従って、索引情報の登録場所を決定する。
【0021】
上述の受付部31、リーフノード特定部32、算出部33、取得部36、特定部37、第3判定部38、第4判定部39、登録部40、決定部41は、後述の登録処理を実行する登録処理部であると捉えることもできる。登録処理の詳細な内容については後述する。
【0022】
削除対象特定部42は、索引記憶部24に記憶された索引情報のうち、削除対象の索引情報を特定する。削除部43は、削除対象特定部42で特定された索引情報を索引記憶部24から削除する。
【0023】
上述の受付部31、リーフノード特定部32、算出部33、削除対象特定部42、削除部43は、後述の削除処理を実行する削除処理部であると捉えることもできる。削除処理の詳細な内容については後述する。
【0024】
次に、制御部30が実行する検索処理について説明する。図5は、検索処理の一例を示すフローチャートである。図5に示すように、まず、検索文字列の入力を受付部31で受け付けると(ステップS511)、リーフノード特定部32は、検索文字列に対応するリーフノード27を特定する(ステップS512)。本実施形態では、リーフノード特定部32は、B木をたどって、対応するリーフノード27を特定する。より具体的には以下のとおりである。いま、図4に示すように、「データベース管理システム」という文字列を検索文字列として受け付けた場合を想定する。まずルートノード25では、「データベース管理システム」に対応するブランチノード26が特定される。ここでは、50音の各行(あ行、か行、・・・、わ行)ごとに、ブランチノード26が割り当てられており、検索文字列の先頭の文字が、50音の各行のうちの何れに属するかに応じて、対応するブランチノード26が特定される。「データベース管理システム」は、先頭の文字が「デ」であり、「た行」に属するとみなされるので、「データベース管理システム」に対応するブランチノード26として、「た行」に対応するブランチノード26が特定される。
【0025】
図4に示すように、ブランチノード26には、当該ブランチノード26に割り当てられた複数の文字列(ここでは一例として2文字分の文字列)ごとに、当該文字列に対応するリーフノード27の位置を示すポインタが格納される。「データベース管理システム」の先頭から数えて2文字分の文字列は「デー」であるので、「デー」に対応するポインタ「eee」で示されるリーフノード27が、「データベース管理システム」に対応するリーフノード27となる。以上のようにして、「データベース管理システム」に対応するリーフノード27が特定される。なお、上述の例に限らず、検索文字列に対応するリーフノード27の特定方法は任意である。
【0026】
次に、第1判定部34は、検索文字列の一部と一致する部分文字列がリーフノード27に存在するか否かを判定する(ステップS513)。例えば、検索文字列が「データベース管理システム」の場合、図4のリーフノード27の第6行目の索引情報および第7行目の索引情報の各々の部分文字列(「データベース管理シス」)が、「データベース管理システム」の一部と一致するので、ステップS513の結果は肯定となる。検索文字列の一部と一致する部分文字列がリーフノード27に存在すると判定された場合、算出部33は、検索文字列のハッシュ値を算出する(ステップS514)。一方、検索文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合、検索処理は終了する。
【0027】
上述のステップS514の後、第2判定部35は、検索文字列のハッシュ値と、検索文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、検索文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する(ステップS515)。例えば検索文字列が「データベース管理システム」の場合、図4のリーフノード27の第6行目の索引情報のハッシュ値(H(データベース管理システム))は、検索文字列(「データベース管理システム」)のハッシュ値と一致する一方、第7行目の索引情報のハッシュ値(H(データベース管理システムの実行情報を取得する手段を有する記憶装置))は、検索文字列(「データベース管理システム」)のハッシュ値と一致しない。
【0028】
上述のステップS515において、検索文字列のハッシュ値と一致するハッシュ値を含む索引情報があると判定された場合、取得部36は、当該索引情報のIDを取得する(ステップS516)。次に、取得部36は、データベース部22から、その取得したIDで特定されるデータ情報DQを取得して操作表示部10に表示する(ステップS517)。一方、上述のステップS515において、検索文字列のハッシュ値と一致する索引情報は存在しないと判定された場合、検索処理は終了する。
【0029】
次に、制御部30が実行する登録処理について説明する。図6は、登録処理の一例を示すフローチャートである。図6に示すように、まず、索引情報の登録を行うデータ情報DQの入力を受付部31で受け付けると(ステップS611)、特定部37は、その受け付けたデータ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(登録文字列と呼ぶ)と、当該データ情報DQのID(位置情報)を特定する(ステップS612)。次に、リーフノード特定部32は、登録文字列に対応するリーフノード27を特定する(ステップS613)。この特定方法は、検索文字列に対応するリーフノード27の特定方法と同様であるので、詳細な説明は省略する。
【0030】
次に、第3判定部38は、登録文字列の一部と一致する部分文字列がリーフノード27に存在するか否かを判定する(ステップS614)。ステップS614において、登録文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合、決定部41は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定し(ステップS615)、処理は後述のステップS620に移行する。いま、登録文字列が「データ抽出装置、抽出方法およびプログラム」であって、登録文字列の50音順に挿入場所が決定される場合を想定する。図4の例では、登録文字列「データ抽出装置、抽出方法およびプログラム」は、第3行目の索引情報と第4行目の索引情報との間に挿入されることが決定される。なお、これに限らず、所定の規則は任意に設定可能である。
【0031】
一方、上述のステップS614において、登録文字列の一部と一致する部分文字列がリーフノード27に存在すると判定された場合、算出部33は、登録文字列のハッシュ値を算出する(ステップS616)。次に、第4判定部39は、登録文字列のハッシュ値と、登録文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する(ステップS617)。
【0032】
上述のステップS617において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、取得部36は、登録文字列の一部と一致する部分文字列に対応するIDで特定されるデータ情報DQをデータベース部22から取得し、当該データ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列を取得する(ステップS618)。例えば、図4の例において、登録文字列が「データベース管理システムおよびプログラム」の場合を想定する。この場合、第6行目の索引情報および第7行目の索引情報の各々の部分文字列(「データベース管理シス」)が、登録文字列の一部と一致するものの、ハッシュ値は一致しない。したがって、取得部36は、第6行目の索引情報および第7行目の索引情報に含まれるIDで特定されるデータ情報DQをそれぞれ取得するとともに、当該各データ情報DQにおける特定のフィールドFxに登録されたアプリケーション名を構成する文字列を取得する。
【0033】
次に、決定部41は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定し(ステップS619)、処理は後述のステップS620に移行する。いま、登録文字列が「データベース管理システムおよびプログラム」であって、登録文字列の50音順に挿入場所が決定される場合を想定する。図4の例では、登録文字列「データベース管理システムおよびプログラム」は、第6行目の索引情報と第7行目の索引情報との間に挿入されることが決定される。なお、これに限らず、所定の規則は任意に設定可能である。
【0034】
ステップS620では、登録部40は、決定部41により決定された挿入場所に、登録文字列の部分文字列と、当該登録文字列のハッシュ値と、特定部37で特定されたIDとを対応付けた索引情報を登録する。例えば登録文字列が「データベース管理システムおよびプログラム」である場合、先頭から10文字分のデータ長の「データベース管理シス」と、「データベース管理システムおよびプログラム」のハッシュ値と、「データベース管理システムおよびプログラム」が特定のフィールドFxに登録されたデータ情報DQのID(特定部37で特定されたID)とが対応付けられた索引情報が、決定部41により決定された挿入場所に登録される。
【0035】
一方、上述のステップS617において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在すると判定された場合、登録部40は、リーフノード27(索引記憶部24)のうち、当該索引情報が記憶される行の直後の行または直前の行に、登録文字列の部分文字列と、登録文字列のハッシュ値と、特定部37で特定されたIDとを対応付けた索引情報を登録する(ステップS620)。
【0036】
次に、制御部30が実行する削除処理について説明する。図7は、削除処理の一例を示すフローチャートである。図7に示すように、まず、削除を行うデータ情報DQの入力を受付部31で受け付けると(ステップS711)、特定部37は、その受け付けたデータ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(削除文字列と呼ぶ)と、当該データ情報DQのID(位置情報)を特定する(ステップS712)。次に、リーフノード特定部32は、削除文字列に対応するリーフノード27を特定する(ステップS713)。
【0037】
次に、削除対象特定部42は、リーフノード27に記憶された索引情報のうち削除対象となる索引情報を特定する(ステップS714)。より具体的には、削除対象特定部42は、削除文字列のハッシュ値と一致するハッシュ値を含む索引情報を、削除対象の索引情報として特定する。次に、削除部43は、削除対象特定部42で特定された索引情報をリーフノード27から削除する(ステップS715)。
【0038】
以上に説明したように、本実施形態では、データ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(データ列)を、そのまま索引記憶部24に登録することはせずに、アプリケーション名を構成する文字列の一部の部分文字列と、当該文字列のハッシュ値と、ID(位置情報)とを対応付けて索引記憶部24に記憶するので、索引記憶部24が保持するデータ量を低減できる。したがって、本実施形態によれば、検索時の読み出し量が少なくなるので、検索速度を高速化することが可能になるという有利な効果を奏する。
【0039】
(第2実施形態)
次に第2実施形態について説明する。第2実施形態では、図8に示すように、索引記憶部24(リーフノード27)に記憶される部分文字列のデータ長は可変に設定される点で上述の第1実施形態と相違する。その他は、第1実施形態と同じであるので、重複する部分については説明を省略する。
【0040】
図9は、第2実施形態の検索装置100の概略構成の一例を示すブロック図である。図9に示すように、制御部30が有する機能の中に設定部44が含まれる点で第1実施形態と相違する。設定部44は、索引記憶部24(リーフノード27)に登録する部分文字列のデータ長を可変に設定するとともに、登録する部分文字列を設定する。
【0041】
図10は、第2実施形態における登録処理の一例を示すフローチャートである。なお、検索処理および削除処理は、上述の第1実施形態と同じであるので、ここでは説明を省略する。図10のステップS911〜ステップS914の内容は、図6のステップS611〜ステップS614の内容と同じであるので、詳細な説明は省略する。
【0042】
図10のステップS914において、登録文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合、決定部41は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定する(ステップS915)。ステップS915の内容は図6のステップS615の内容と同じであるので、詳細な説明は省略する。ステップS915の後、設定部44は、登録文字列のデータ長を1文字分のデータ長に設定する。そして、登録文字列の先頭の文字を部分文字列として設定する(ステップS916)。例えば登録文字列が「データ抽出装置、抽出方法およびプログラム」の場合、先頭の文字である「デ」が部分文字列として設定される。なお、これに限らず、部分文字列の設定方法は任意であり、例えば先頭の文字から2文字分のデータ列を部分文字列として設定することもできる。ステップS916の後、処理はステップS922に移行する。ステップS922の内容は、図6のステップS620の内容と同じであるので、詳細な説明は省略する。
【0043】
上述のステップS914において、登録文字列の一部と一致する部分文字列がリーフノード27に存在すると判定された場合、算出部33は、登録文字列のハッシュ値を算出する(ステップS917)。次に、第4判定部39は、登録文字列のハッシュ値と、登録文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する(ステップS918)。
【0044】
上述のステップS918において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、設定部44は、データ長を拡張して、登録する部分文字列を設定する(ステップS919)。より具体的には、設定部44は、登録する部分文字列のデータ長を、登録文字列の一部と一致する部分文字列のデータ長よりも大きい値に設定する。
【0045】
例えば、図8の例において、登録文字列が「データベース管理システムおよびプログラム」の場合を想定する。この場合、第3行目、第5行目、第6行目および第7行目の各々の索引情報の部分文字列(「データ」、「デ」、「データベ」、「デー」)が、登録文字列の一部と一致するものの、ハッシュ値は一致しない。したがって、設定部44は、登録する文字列のデータ長を、登録文字列の一部と一致する部分文字列のうちデータ長が最大のものよりも1文字分だけ長い値に設定する。この場合、登録する部分文字列のデータ長は5文字分の長さとなり、設定部44は、先頭の文字から数えて5文字分のデータ長の「データベー」を、登録する部分文字列として設定する。なお、これは一例であり、登録する部分文字列の設定方法は任意である。要するに、登録する部分文字列として、登録文字列の一部と一致する部分文字列のデータ長よりも長いデータ長の文字列を設定するものであればよい。
【0046】
ステップS919の後、処理はステップS920に移行する。ステップS920〜ステップS922の内容は、図6のステップS618〜ステップS620の内容と同じであるので、詳細な説明は省略する。
【0047】
また、上述のステップS918において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、処理はステップS922に移行する。図9のステップS922の内容は、図6のステップS620の内容と同じであるので、詳細な説明は省略する。
【0048】
以上に説明したように、本実施形態では、登録文字列の一部と一致する部分文字列がリーフノード27に存在するものの、当該登録文字列のハッシュ値と一致するハッシュ値を含む索引情報がリーフノード27に存在しないと判定された場合は、登録する部分文字列のデータ長は拡張される一方、登録文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合は、登録する部分文字列のデータ長は抑制される(一例として、本実施形態では1文字分のデータ長に抑制される)。すなわち、必要な部分は登録する部分文字列のデータ長を伸ばしつつ、必要の無い部分で登録する部分文字列のデータ長を抑えることにより、索引記憶部24(リーフノード27)の容量を削減できるという利点がある。
【0049】
(変形例)
以上、本発明の実施形態を説明したが、上述の各実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【0050】
例えば上述の各実施形態では、データベース部22に記憶されるデータ情報の一例として、文書を示す情報(ドキュメント情報)を挙げて説明したが、これに限らず、データ情報の種類は任意である。例えば図11に示すように、データ情報は、テーブルデータ200の各ラインを構成するデータ群Gであってもよい。各データ群G(データ情報)は、それぞれにデータ列が登録される複数のフィールドFを有する。そして、複数のフィールドFのうち、特定のフィールドFxに対して、上述したような索引を作成することができる。
【0051】
また、上述の各実施形態では、データ情報DQが有する複数のフィールドFのうちの特定のフィールドFxに対してのみ索引が作成されているが、これに限らず、他のフィールドに対しても、上述の各実施形態と同様の索引を作成することもできる。
【符号の説明】
【0052】
10 操作表示部
20 記憶部
22 データベース部
24 索引記憶部
25 ルートノード
26 ブランチノード
27 リーフノード
30 制御部
31 受付部
32 リーフノード特定部
33 算出部
34 第1判定部
35 第2判定部
36 取得部
37 特定部
38 第3判定部
39 第4判定部
40 登録部
41 決定部
42 削除対象特定部
43 削除部
44 設定部
100 検索装置
200 テーブルデータ
【技術分野】
【0001】
本発明は、検索装置、検索方法およびプログラムに関する。
【背景技術】
【0002】
従来、例えばB木などのデータ構造からなる索引(インデックス)が格納された索引記憶部を備え、索引記憶部から読み出した索引を用いて、所望のデータをデータベースから検索する検索装置が知られている。索引記憶部が保持するデータ量が少ないほど、検索時の読み出し量が少なくなるので、検索速度を高速化することが可能になる。このため、索引記憶部が保持するデータ量は少ないことが望まれる。
【0003】
例えば、データベースに格納されたテーブルの特定のフィールドの各行に登録されたデータ(キー)と、当該キーの登録場所を示す情報(バリュー)とが格納されるB木のリーフノードにおけるキーの格納領域を減らす技術が知られている。この技術では、リーフノードは2層化され、第1層目のデータ構造体には、キーと、当該キーに対応する第2層目のデータ構造体の位置を示す情報(ポインタ)とが格納される。そして、第2層目のデータ構造体には、当該キーに対応する全てのバリューが格納される。例えば、テーブルの特定のフィールドの第2行目および第5行目の各々に当該キーが登録されている場合は、第2行目を示すバリューと第5行目を示すバリューとが、当該キーに対応する第2層目の構造体に格納される。一方、第1層目のデータ構造体に格納される当該キーの数は1つで済むので、結果として、リーフノードにおけるキーの格納領域が低減されるという具合である。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2010−72823号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、上述した技術では、同値のキーが殆ど存在しない場合には、索引記憶部は全てのキーを保持する必要があるので、索引記憶部が保持するデータ量を低減することはできないという問題がある。本発明が解決しようとする課題は、索引記憶部が保持するデータ量を低減可能な検索装置、検索方法およびプログラムを提供することである。
【課題を解決するための手段】
【0006】
実施形態の検索装置は、データベースと、索引記憶部と、受付部と、算出部と、第1判定部と、第2判定部と、取得部とを備える。データベースは、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶する。索引記憶部は、複数のフィールドのうちの特定のフィールドに登録されたデータ列の一部である部分データ列と、データ列のハッシュ値と、当該データ列が特定のフィールドに登録されたデータ情報のデータベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する。受付部は、検索データ列を受け付ける。算出部は、検索データ列のハッシュ値を算出する。第1判定部により、検察データ列の一部と一致する部分データ列が索引記憶部に存在すると判定され、第2判定部により、当該部分データ列に対応するハッシュ値と、検索データ列のハッシュ値とが一致すると判定された場合は、取得部は、当該部分データ列に対応する位置情報を取得する。
【0007】
また、実施形態の検索方法は、検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、前記検索データ列のハッシュ値を算出する第2ステップと、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、を備えることを特徴とする。
【0008】
さらに、実施形態のプログラムは、検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、前記検索データ列のハッシュ値を算出する第2ステップと、それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、をコンピュータに実行させるためのプログラムである。
【図面の簡単な説明】
【0009】
【図1】第1実施形態の検索装置の一例を示すブロック図。
【図2】データベース部の一例を示す図。
【図3】データ情報の一例を示す図。
【図4】索引記憶部の一例を示す図。
【図5】検索処理の一例を示すフローチャート
【図6】登録処理の一例を示すフローチャート。
【図7】削除処理の一例を示すフローチャート。
【図8】第2実施形態の索引記憶部の一例を示す図。
【図9】第2実施形態の検索装置の一例を示すブロック図。
【図10】登録処理の一例を示す図。
【図11】変形例を説明するための図。
【発明を実施するための形態】
【0010】
(第1実施形態)
図1は、第1実施形態の検索装置100の概略構成の一例を示すブロック図である。図1に示すように、検索装置100は、操作表示部10と、記憶部20と、制御部30とを備える。操作表示部10は、各種画面や検索装置100に関する情報(例えば検索結果等)を表示するとともに、ユーザーが各種の操作入力を行うための手段である。詳細な図示は省略するが、操作表示部10は、各種画面や検索装置100に関する情報を表示するとともにユーザーからのタッチ入力を受け付ける表示パネルと、例えば各種ボタンやマウスなどの操作デバイスとを備える。
【0011】
記憶部20は、データベース部22と索引記憶部24とを含む。データベース部22は、複数のフィールドを各々が有する複数のデータ情報を記憶する。図2に示すように、データベース部22は、複数のデータ情報DQを記憶する。ここでは、データ情報DQは文書を示す情報であり、一例として、XML(Extensible Markup Language)で記述された半構造化データがデータ情報DQとして採用されている。
【0012】
図3は、データ情報DQの一例を示す図である。図3に示すように、データ情報DQは、それぞれにデータ列が登録される複数のフィールドFを有している。本実施形態では、各データ情報DQが有する複数のフィールドFのうちの特定のフィールドFxに対してのみ索引が作成される。詳細な内容については後述する。ここでは、各データ情報DQの特定のフィールドFxは、アプリケーション名(application-title)を構成する文字列(データ列)が登録されるフィールドである。
【0013】
図1に戻って説明を続ける。索引記憶部24は、索引(インデックス)を記憶する。索引は、例えばB木などのデータ構造である。本実施形態では、索引としてB木が用いられるが、これに限らず、索引の種類は任意である。例えばビットマップインデックスや関数インデックスなどを採用することもできる。図4に示すように、索引記憶部24は、最上位層のルートノード25と、中間層のブランチノード26と、最下層のリーフノード27とを含む。リーフノード27は、アプリケーション名を構成する文字列の一部である部分文字列と、当該アプリケーション名を構成する文字列のハッシュ値と、当該アプリケーション名が特定のフィールドFxに登録されたデータ情報DQのデータベース部22における位置を示すID(位置情報)とが対応付けられた索引情報を行ごとに記憶する。本実施形態のID(位置情報)は、データベース部22におけるデータ情報DQの位置だけでなく、当該データ情報DQにおける特定のフィールドFxの位置も特定する情報である。また、本実施形態では、部分文字列のデータ長は固定長である。ここでは、一例として10文字分のデータ長に設定されるが、これに限定されるものではない。
【0014】
図1に示す制御部30は、検索装置100の各部を制御する手段であり、CPU(Central Processing Unit)、ROM(Read Only Memory)、および、RAM(Random Access Memory)などを含む制御装置で構成される。制御部30が有する機能としては、
受付部31、リーフノード特定部32、算出部33、第1判定部34、第2判定部35、取得部36、特定部37、第3判定部38、第4判定部39、登録部40、決定部41、削除対象特定部42、削除部43がある。以上の機能(31、32、33、34、35、36、37、38、39、40、41、42、43)は、CPUが、ROMに格納された制御プログラムをRAM上に読み出して実行することにより実現される。なお、これに限らず、以上の機能(31、32、33、34、35、36、37、38、39、40、41、42、43)のうちの少なくとも一部がハードウェア回路で実現されてもよい。
【0015】
受付部31は、操作表示部10からの各種入力を受け付ける。例えば、受付部31は、検索に用いられるアプリケーション名を構成する文字列(検索文字列と呼ぶ)の入力を受け付けることもできるし、索引情報の登録を行うデータ情報DQの入力を受け付けることもできる。また、削除を行うデータ情報DQの入力を受け付けることもできる。リーフノード特定部32は、入力された文字列に対応するリーフノード27を特定する。算出部33は、入力された文字列のハッシュ値を算出する。
【0016】
第1判定部34は、検索文字列の一部と一致する部分文字列が索引記憶部24(リーフノード27)に存在するか否かを判定する。第2判定部35は、第1判定部34により、検索文字列の一部と一致する部分文字列が索引記憶部24に存在すると判定された場合は、当該部分文字列に対応するハッシュ値と、検索文字列のハッシュ値とが一致するか否かを判定する。取得部36は、第2判定部35により、部分文字列に対応するハッシュ値と、検索文字列のハッシュ値とが一致すると判定された場合は、当該部分文字列に対応するIDを索引記憶部24(リーフノード27)から取得する。また、取得部36は、当該IDで特定されるデータ情報DQをデータベース部22から取得することもできる。
【0017】
上述の受付部31、リーフノード特定部32、算出部33、第1判定部34、第2判定部35、取得部36は、後述の検索処理を実行する検索処理部であると捉えることもできる。検索処理の詳細な内容については後述する。
【0018】
特定部37は、索引情報の登録を行うデータ情報DQの入力を受付部31で受け付けた場合、当該データ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(登録文字列と呼ぶ)と、当該データ情報DQのID(位置情報)とを特定する。第3判定部38は、登録文字列の一部と一致する部分文字列が索引記憶部24(リーフノード27)に存在するか否かを判定する。第4判定部39は、第3判定部38により、登録文字列の一部と一致する部分文字列が索引記憶部24に存在すると判定された場合は、当該部分文字列に対応するハッシュ値と、登録文字列のハッシュ値とが一致するか否かを判定する。
【0019】
登録部40は、登録文字列の部分文字列と、当該登録文字列のハッシュ値と、特定部37で特定されたIDとを対応付けた索引情報を、索引記憶部24(リーフノード27)に登録する。
【0020】
決定部41は、第3判定部38により登録文字列の一部と一致する部分文字列が索引記憶部24に存在しないと判定された場合、または、第4判定部39により部分文字列に対応するハッシュ値と、登録文字列のハッシュ値とが一致しないと判定された場合は、所定の規則に従って、索引情報の登録場所を決定する。
【0021】
上述の受付部31、リーフノード特定部32、算出部33、取得部36、特定部37、第3判定部38、第4判定部39、登録部40、決定部41は、後述の登録処理を実行する登録処理部であると捉えることもできる。登録処理の詳細な内容については後述する。
【0022】
削除対象特定部42は、索引記憶部24に記憶された索引情報のうち、削除対象の索引情報を特定する。削除部43は、削除対象特定部42で特定された索引情報を索引記憶部24から削除する。
【0023】
上述の受付部31、リーフノード特定部32、算出部33、削除対象特定部42、削除部43は、後述の削除処理を実行する削除処理部であると捉えることもできる。削除処理の詳細な内容については後述する。
【0024】
次に、制御部30が実行する検索処理について説明する。図5は、検索処理の一例を示すフローチャートである。図5に示すように、まず、検索文字列の入力を受付部31で受け付けると(ステップS511)、リーフノード特定部32は、検索文字列に対応するリーフノード27を特定する(ステップS512)。本実施形態では、リーフノード特定部32は、B木をたどって、対応するリーフノード27を特定する。より具体的には以下のとおりである。いま、図4に示すように、「データベース管理システム」という文字列を検索文字列として受け付けた場合を想定する。まずルートノード25では、「データベース管理システム」に対応するブランチノード26が特定される。ここでは、50音の各行(あ行、か行、・・・、わ行)ごとに、ブランチノード26が割り当てられており、検索文字列の先頭の文字が、50音の各行のうちの何れに属するかに応じて、対応するブランチノード26が特定される。「データベース管理システム」は、先頭の文字が「デ」であり、「た行」に属するとみなされるので、「データベース管理システム」に対応するブランチノード26として、「た行」に対応するブランチノード26が特定される。
【0025】
図4に示すように、ブランチノード26には、当該ブランチノード26に割り当てられた複数の文字列(ここでは一例として2文字分の文字列)ごとに、当該文字列に対応するリーフノード27の位置を示すポインタが格納される。「データベース管理システム」の先頭から数えて2文字分の文字列は「デー」であるので、「デー」に対応するポインタ「eee」で示されるリーフノード27が、「データベース管理システム」に対応するリーフノード27となる。以上のようにして、「データベース管理システム」に対応するリーフノード27が特定される。なお、上述の例に限らず、検索文字列に対応するリーフノード27の特定方法は任意である。
【0026】
次に、第1判定部34は、検索文字列の一部と一致する部分文字列がリーフノード27に存在するか否かを判定する(ステップS513)。例えば、検索文字列が「データベース管理システム」の場合、図4のリーフノード27の第6行目の索引情報および第7行目の索引情報の各々の部分文字列(「データベース管理シス」)が、「データベース管理システム」の一部と一致するので、ステップS513の結果は肯定となる。検索文字列の一部と一致する部分文字列がリーフノード27に存在すると判定された場合、算出部33は、検索文字列のハッシュ値を算出する(ステップS514)。一方、検索文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合、検索処理は終了する。
【0027】
上述のステップS514の後、第2判定部35は、検索文字列のハッシュ値と、検索文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、検索文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する(ステップS515)。例えば検索文字列が「データベース管理システム」の場合、図4のリーフノード27の第6行目の索引情報のハッシュ値(H(データベース管理システム))は、検索文字列(「データベース管理システム」)のハッシュ値と一致する一方、第7行目の索引情報のハッシュ値(H(データベース管理システムの実行情報を取得する手段を有する記憶装置))は、検索文字列(「データベース管理システム」)のハッシュ値と一致しない。
【0028】
上述のステップS515において、検索文字列のハッシュ値と一致するハッシュ値を含む索引情報があると判定された場合、取得部36は、当該索引情報のIDを取得する(ステップS516)。次に、取得部36は、データベース部22から、その取得したIDで特定されるデータ情報DQを取得して操作表示部10に表示する(ステップS517)。一方、上述のステップS515において、検索文字列のハッシュ値と一致する索引情報は存在しないと判定された場合、検索処理は終了する。
【0029】
次に、制御部30が実行する登録処理について説明する。図6は、登録処理の一例を示すフローチャートである。図6に示すように、まず、索引情報の登録を行うデータ情報DQの入力を受付部31で受け付けると(ステップS611)、特定部37は、その受け付けたデータ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(登録文字列と呼ぶ)と、当該データ情報DQのID(位置情報)を特定する(ステップS612)。次に、リーフノード特定部32は、登録文字列に対応するリーフノード27を特定する(ステップS613)。この特定方法は、検索文字列に対応するリーフノード27の特定方法と同様であるので、詳細な説明は省略する。
【0030】
次に、第3判定部38は、登録文字列の一部と一致する部分文字列がリーフノード27に存在するか否かを判定する(ステップS614)。ステップS614において、登録文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合、決定部41は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定し(ステップS615)、処理は後述のステップS620に移行する。いま、登録文字列が「データ抽出装置、抽出方法およびプログラム」であって、登録文字列の50音順に挿入場所が決定される場合を想定する。図4の例では、登録文字列「データ抽出装置、抽出方法およびプログラム」は、第3行目の索引情報と第4行目の索引情報との間に挿入されることが決定される。なお、これに限らず、所定の規則は任意に設定可能である。
【0031】
一方、上述のステップS614において、登録文字列の一部と一致する部分文字列がリーフノード27に存在すると判定された場合、算出部33は、登録文字列のハッシュ値を算出する(ステップS616)。次に、第4判定部39は、登録文字列のハッシュ値と、登録文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する(ステップS617)。
【0032】
上述のステップS617において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、取得部36は、登録文字列の一部と一致する部分文字列に対応するIDで特定されるデータ情報DQをデータベース部22から取得し、当該データ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列を取得する(ステップS618)。例えば、図4の例において、登録文字列が「データベース管理システムおよびプログラム」の場合を想定する。この場合、第6行目の索引情報および第7行目の索引情報の各々の部分文字列(「データベース管理シス」)が、登録文字列の一部と一致するものの、ハッシュ値は一致しない。したがって、取得部36は、第6行目の索引情報および第7行目の索引情報に含まれるIDで特定されるデータ情報DQをそれぞれ取得するとともに、当該各データ情報DQにおける特定のフィールドFxに登録されたアプリケーション名を構成する文字列を取得する。
【0033】
次に、決定部41は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定し(ステップS619)、処理は後述のステップS620に移行する。いま、登録文字列が「データベース管理システムおよびプログラム」であって、登録文字列の50音順に挿入場所が決定される場合を想定する。図4の例では、登録文字列「データベース管理システムおよびプログラム」は、第6行目の索引情報と第7行目の索引情報との間に挿入されることが決定される。なお、これに限らず、所定の規則は任意に設定可能である。
【0034】
ステップS620では、登録部40は、決定部41により決定された挿入場所に、登録文字列の部分文字列と、当該登録文字列のハッシュ値と、特定部37で特定されたIDとを対応付けた索引情報を登録する。例えば登録文字列が「データベース管理システムおよびプログラム」である場合、先頭から10文字分のデータ長の「データベース管理シス」と、「データベース管理システムおよびプログラム」のハッシュ値と、「データベース管理システムおよびプログラム」が特定のフィールドFxに登録されたデータ情報DQのID(特定部37で特定されたID)とが対応付けられた索引情報が、決定部41により決定された挿入場所に登録される。
【0035】
一方、上述のステップS617において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在すると判定された場合、登録部40は、リーフノード27(索引記憶部24)のうち、当該索引情報が記憶される行の直後の行または直前の行に、登録文字列の部分文字列と、登録文字列のハッシュ値と、特定部37で特定されたIDとを対応付けた索引情報を登録する(ステップS620)。
【0036】
次に、制御部30が実行する削除処理について説明する。図7は、削除処理の一例を示すフローチャートである。図7に示すように、まず、削除を行うデータ情報DQの入力を受付部31で受け付けると(ステップS711)、特定部37は、その受け付けたデータ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(削除文字列と呼ぶ)と、当該データ情報DQのID(位置情報)を特定する(ステップS712)。次に、リーフノード特定部32は、削除文字列に対応するリーフノード27を特定する(ステップS713)。
【0037】
次に、削除対象特定部42は、リーフノード27に記憶された索引情報のうち削除対象となる索引情報を特定する(ステップS714)。より具体的には、削除対象特定部42は、削除文字列のハッシュ値と一致するハッシュ値を含む索引情報を、削除対象の索引情報として特定する。次に、削除部43は、削除対象特定部42で特定された索引情報をリーフノード27から削除する(ステップS715)。
【0038】
以上に説明したように、本実施形態では、データ情報DQの特定のフィールドFxに登録されたアプリケーション名を構成する文字列(データ列)を、そのまま索引記憶部24に登録することはせずに、アプリケーション名を構成する文字列の一部の部分文字列と、当該文字列のハッシュ値と、ID(位置情報)とを対応付けて索引記憶部24に記憶するので、索引記憶部24が保持するデータ量を低減できる。したがって、本実施形態によれば、検索時の読み出し量が少なくなるので、検索速度を高速化することが可能になるという有利な効果を奏する。
【0039】
(第2実施形態)
次に第2実施形態について説明する。第2実施形態では、図8に示すように、索引記憶部24(リーフノード27)に記憶される部分文字列のデータ長は可変に設定される点で上述の第1実施形態と相違する。その他は、第1実施形態と同じであるので、重複する部分については説明を省略する。
【0040】
図9は、第2実施形態の検索装置100の概略構成の一例を示すブロック図である。図9に示すように、制御部30が有する機能の中に設定部44が含まれる点で第1実施形態と相違する。設定部44は、索引記憶部24(リーフノード27)に登録する部分文字列のデータ長を可変に設定するとともに、登録する部分文字列を設定する。
【0041】
図10は、第2実施形態における登録処理の一例を示すフローチャートである。なお、検索処理および削除処理は、上述の第1実施形態と同じであるので、ここでは説明を省略する。図10のステップS911〜ステップS914の内容は、図6のステップS611〜ステップS614の内容と同じであるので、詳細な説明は省略する。
【0042】
図10のステップS914において、登録文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合、決定部41は、所定の規則に従って、登録文字列の索引情報の挿入場所を決定する(ステップS915)。ステップS915の内容は図6のステップS615の内容と同じであるので、詳細な説明は省略する。ステップS915の後、設定部44は、登録文字列のデータ長を1文字分のデータ長に設定する。そして、登録文字列の先頭の文字を部分文字列として設定する(ステップS916)。例えば登録文字列が「データ抽出装置、抽出方法およびプログラム」の場合、先頭の文字である「デ」が部分文字列として設定される。なお、これに限らず、部分文字列の設定方法は任意であり、例えば先頭の文字から2文字分のデータ列を部分文字列として設定することもできる。ステップS916の後、処理はステップS922に移行する。ステップS922の内容は、図6のステップS620の内容と同じであるので、詳細な説明は省略する。
【0043】
上述のステップS914において、登録文字列の一部と一致する部分文字列がリーフノード27に存在すると判定された場合、算出部33は、登録文字列のハッシュ値を算出する(ステップS917)。次に、第4判定部39は、登録文字列のハッシュ値と、登録文字列の一部と一致する部分文字列に対応するハッシュ値とを比較し、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報があるか否かを判定する(ステップS918)。
【0044】
上述のステップS918において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、設定部44は、データ長を拡張して、登録する部分文字列を設定する(ステップS919)。より具体的には、設定部44は、登録する部分文字列のデータ長を、登録文字列の一部と一致する部分文字列のデータ長よりも大きい値に設定する。
【0045】
例えば、図8の例において、登録文字列が「データベース管理システムおよびプログラム」の場合を想定する。この場合、第3行目、第5行目、第6行目および第7行目の各々の索引情報の部分文字列(「データ」、「デ」、「データベ」、「デー」)が、登録文字列の一部と一致するものの、ハッシュ値は一致しない。したがって、設定部44は、登録する文字列のデータ長を、登録文字列の一部と一致する部分文字列のうちデータ長が最大のものよりも1文字分だけ長い値に設定する。この場合、登録する部分文字列のデータ長は5文字分の長さとなり、設定部44は、先頭の文字から数えて5文字分のデータ長の「データベー」を、登録する部分文字列として設定する。なお、これは一例であり、登録する部分文字列の設定方法は任意である。要するに、登録する部分文字列として、登録文字列の一部と一致する部分文字列のデータ長よりも長いデータ長の文字列を設定するものであればよい。
【0046】
ステップS919の後、処理はステップS920に移行する。ステップS920〜ステップS922の内容は、図6のステップS618〜ステップS620の内容と同じであるので、詳細な説明は省略する。
【0047】
また、上述のステップS918において、登録文字列のハッシュ値と一致するハッシュ値を含む索引情報が存在しないと判定された場合、処理はステップS922に移行する。図9のステップS922の内容は、図6のステップS620の内容と同じであるので、詳細な説明は省略する。
【0048】
以上に説明したように、本実施形態では、登録文字列の一部と一致する部分文字列がリーフノード27に存在するものの、当該登録文字列のハッシュ値と一致するハッシュ値を含む索引情報がリーフノード27に存在しないと判定された場合は、登録する部分文字列のデータ長は拡張される一方、登録文字列の一部と一致する部分文字列がリーフノード27に存在しないと判定された場合は、登録する部分文字列のデータ長は抑制される(一例として、本実施形態では1文字分のデータ長に抑制される)。すなわち、必要な部分は登録する部分文字列のデータ長を伸ばしつつ、必要の無い部分で登録する部分文字列のデータ長を抑えることにより、索引記憶部24(リーフノード27)の容量を削減できるという利点がある。
【0049】
(変形例)
以上、本発明の実施形態を説明したが、上述の各実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【0050】
例えば上述の各実施形態では、データベース部22に記憶されるデータ情報の一例として、文書を示す情報(ドキュメント情報)を挙げて説明したが、これに限らず、データ情報の種類は任意である。例えば図11に示すように、データ情報は、テーブルデータ200の各ラインを構成するデータ群Gであってもよい。各データ群G(データ情報)は、それぞれにデータ列が登録される複数のフィールドFを有する。そして、複数のフィールドFのうち、特定のフィールドFxに対して、上述したような索引を作成することができる。
【0051】
また、上述の各実施形態では、データ情報DQが有する複数のフィールドFのうちの特定のフィールドFxに対してのみ索引が作成されているが、これに限らず、他のフィールドに対しても、上述の各実施形態と同様の索引を作成することもできる。
【符号の説明】
【0052】
10 操作表示部
20 記憶部
22 データベース部
24 索引記憶部
25 ルートノード
26 ブランチノード
27 リーフノード
30 制御部
31 受付部
32 リーフノード特定部
33 算出部
34 第1判定部
35 第2判定部
36 取得部
37 特定部
38 第3判定部
39 第4判定部
40 登録部
41 決定部
42 削除対象特定部
43 削除部
44 設定部
100 検索装置
200 テーブルデータ
【特許請求の範囲】
【請求項1】
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースと、
前記複数のフィールドのうちの特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ列が前記特定のフィールドに登録された前記データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部と、
検索に用いられる前記データ列を示す検索データ列を受け付ける受付部と、
前記検索データ列のハッシュ値を算出する算出部と、
前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在するか否かを判定する第1判定部と、
前記第1判定部により、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定された場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第2判定部と、
前記第2判定部により、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定された場合は、当該部分データ列に対応する前記位置情報を取得する取得部と、を備える、
ことを特徴とする検索装置。
【請求項2】
前記受付部は、前記索引情報の登録を行う前記データ情報を受け付け、
前記受付部が、前記データ情報を受け付けた場合、当該データ情報の前記特定のフィールドに登録された前記データ列を示す登録データ列と、当該データ情報の前記位置情報を特定する特定部と、
前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在するか否かを判定する第3判定部と、
前記第3判定部により、前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定された場合は、当該部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致するか否かを判定する第4判定部と、
前記第3判定部により前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在しないと判定された場合、または、前記第4判定部により前記部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致しないと判定された場合は、所定の規則に従って、前記索引情報の登録場所を決定する決定部と、
前記決定部により決定された登録場所に前記索引情報を登録する登録部と、を備える、
ことを特徴とする請求項1に記載の検索装置。
【請求項3】
前記第4判定部により前記部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致しないと判定された場合は、前記登録データ列の前記部分データ列のデータ長を、前記登録データ列の一部と一致する前記部分データ列のデータ長よりも大きい値に設定する設定部をさらに備える、
ことを特徴とする請求項2に記載の検索装置。
【請求項4】
前記複数のデータ情報の各々は、文書を示す情報である、
ことを特徴とする請求項1に記載の検索装置。
【請求項5】
前記データベースは、前記複数のデータ情報が並列に配置されるテーブルデータを記憶する、
ことを特徴とする請求項1に記載の検索装置。
【請求項6】
前記位置情報は、前記データ情報における前記特定フィールドの位置も特定する、
ことを特徴とする請求項1に記載の検索装置。
【請求項7】
検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、
前記検索データ列のハッシュ値を算出する第2ステップと、
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、
前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、
前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、を備える、
ことを特徴とする検索方法。
【請求項8】
検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、
前記検索データ列のハッシュ値を算出する第2ステップと、
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、
前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、
前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、をコンピュータに実行させるためのプログラム。
【請求項1】
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースと、
前記複数のフィールドのうちの特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ列が前記特定のフィールドに登録された前記データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部と、
検索に用いられる前記データ列を示す検索データ列を受け付ける受付部と、
前記検索データ列のハッシュ値を算出する算出部と、
前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在するか否かを判定する第1判定部と、
前記第1判定部により、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定された場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第2判定部と、
前記第2判定部により、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定された場合は、当該部分データ列に対応する前記位置情報を取得する取得部と、を備える、
ことを特徴とする検索装置。
【請求項2】
前記受付部は、前記索引情報の登録を行う前記データ情報を受け付け、
前記受付部が、前記データ情報を受け付けた場合、当該データ情報の前記特定のフィールドに登録された前記データ列を示す登録データ列と、当該データ情報の前記位置情報を特定する特定部と、
前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在するか否かを判定する第3判定部と、
前記第3判定部により、前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定された場合は、当該部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致するか否かを判定する第4判定部と、
前記第3判定部により前記登録データ列の一部と一致する前記部分データ列が前記索引記憶部に存在しないと判定された場合、または、前記第4判定部により前記部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致しないと判定された場合は、所定の規則に従って、前記索引情報の登録場所を決定する決定部と、
前記決定部により決定された登録場所に前記索引情報を登録する登録部と、を備える、
ことを特徴とする請求項1に記載の検索装置。
【請求項3】
前記第4判定部により前記部分データ列に対応する前記ハッシュ値と、前記登録データ列の前記ハッシュ値とが一致しないと判定された場合は、前記登録データ列の前記部分データ列のデータ長を、前記登録データ列の一部と一致する前記部分データ列のデータ長よりも大きい値に設定する設定部をさらに備える、
ことを特徴とする請求項2に記載の検索装置。
【請求項4】
前記複数のデータ情報の各々は、文書を示す情報である、
ことを特徴とする請求項1に記載の検索装置。
【請求項5】
前記データベースは、前記複数のデータ情報が並列に配置されるテーブルデータを記憶する、
ことを特徴とする請求項1に記載の検索装置。
【請求項6】
前記位置情報は、前記データ情報における前記特定フィールドの位置も特定する、
ことを特徴とする請求項1に記載の検索装置。
【請求項7】
検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、
前記検索データ列のハッシュ値を算出する第2ステップと、
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、
前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、
前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、を備える、
ことを特徴とする検索方法。
【請求項8】
検索に用いられるデータ列を示す検索データ列を受け付ける第1ステップと、
前記検索データ列のハッシュ値を算出する第2ステップと、
それぞれがデータ列を含む複数のフィールドをそれぞれが有する複数のデータ情報を記憶するデータベースに存在する複数の前記データ情報のうちの何れかの前記データ情報の特定のフィールドに登録された前記データ列の一部である部分データ列と、当該データ列のハッシュ値と、当該データ情報の前記データベースにおける位置を示す位置情報とが対応付けられた索引情報を記憶する索引記憶部に、前記検察データ列の一部と一致する前記部分データ列が存在するか否かを判定する第3ステップと、
前記第3ステップで、前記検察データ列の一部と一致する前記部分データ列が前記索引記憶部に存在すると判定した場合は、当該部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致するか否かを判定する第4ステップと、
前記第4ステップで、前記部分データ列に対応する前記ハッシュ値と、前記検索データ列の前記ハッシュ値とが一致すると判定した場合は、当該部分データ列に対応する前記位置情報を取得する第5ステップと、をコンピュータに実行させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2012−230493(P2012−230493A)
【公開日】平成24年11月22日(2012.11.22)
【国際特許分類】
【出願番号】特願2011−97366(P2011−97366)
【出願日】平成23年4月25日(2011.4.25)
【出願人】(000003078)株式会社東芝 (54,554)
【出願人】(301063496)東芝ソリューション株式会社 (1,478)
【公開日】平成24年11月22日(2012.11.22)
【国際特許分類】
【出願日】平成23年4月25日(2011.4.25)
【出願人】(000003078)株式会社東芝 (54,554)
【出願人】(301063496)東芝ソリューション株式会社 (1,478)
[ Back to top ]