JP4491480B2 - インデクス構築方法、文書検索装置及びインデクス構築プログラム - Google Patents

Description

本発明は、文書検索システムにおいて使用されるインデクスを構築する技術に関する。

大規模な文書データベースから指定された検索文字列が含まれる文書を高速に検索する方法として、インデクスを用いる方法が知られている。インデクスには、検索対象となる文書に含まれる複数のキーワードを示す索引項目と、索引項目を含む文書を識別する文書識別情報及び当該文書における索引項目の位置情報などを含む索引情報が記録されている。

このような文書の構築方法では、文書に関する索引項目は、トライ（trie）のような木構造によって管理される。索引情報は木構造の節（葉）に対応付けられる。トライとは、検索対象となる文字列すなわちキーワードの集合（以下、「キー集合」）における各キーワード（以下、「キー」）に共通な部分文字列（記号列）を、共通の節（以下、「節」又は「トライ節」）として括り出して作られる木構造である（特許文献１参照）。コンピュータは、検索文字列をキーに分解し、キーに基づいてトライを探索する。そして、コンピュータは、キーと合致する節に到着すると、当該節に設定されたポインタ情報を取得し、キーに対応する索引情報を読み出す。

また、組み込み機器などにおいては、トライをすべて主記憶装置（メモリ）に記憶させることによって検索性能を向上させるため、トライの複数の節を１つの節に統合（以下、「マージ節」）して、メモリに記憶されたトライの大きさを削減する方法がある。例えば、節「あ」、節「い」、節「う」を有するトライにおいて、これら３つの節を１つのマージ節「あ〜う」に統合する。

次に索引情報について説明する。索引情報は、文字列、文書番号及び出現位置を含む。また、索引情報を同一の文字列ごとに集約し、各要素間で差分を取得して索引情報を圧縮する技術が開示されている（特許文献２参照）。この場合、索引情報の圧縮は同一の文字列を有する索引情報のみとし、同一の文字列を持つ複数の索引情報を圧縮したものを１つの索引情報群（以下、「索引情報ブロック」）とする。
特開平８−１９４７１８号公報 特開２００１−３１２５１７号公報

コンピュータがマージ節を含むトライを利用して索引情報を管理する場合、マージ節は、複数の索引情報ブロックをまとめて管理するため、索引情報の更新を含む操作が複数回発生すると、局所的な索引情報ブロックの肥大化又は過疎化が生じる可能性がある。

索引情報ブロックの肥大化とは、特定のマージ節が管理している複数の索引情報ブロックに対して索引情報の追加が集中し、管理している複数の索引情報ブロックの情報量が大幅に増加する現象である。肥大化した索引情報ブロックよりも後方にある索引情報ブロックが検索対象となると、目的の索引情報を抽出するまでの時間が増加し、検索性能が劣化してしまう。

索引情報ブロックの過疎化とは、いくつかの節又はマージ節が管理している索引情報ブロックに索引情報の削除が集中し、それぞれの索引情報ブロックの情報量が大幅に減少する現象である。この場合、対象となった節又はマージ節が管理する索引情報量が非常に小さくなるため、トライのメモリ使用効率が悪化してしまう。

本発明は、このような問題点に鑑みてなされたものであり、索引情報の追加及び削除が繰り返された場合であっても、索引情報の検索を許容検索時間内で開始可能な状態を維持しつつ、トライのメモリ使用効率を維持させることを目的とする。

本発明の代表的な一形態によれば、文書を検索する文書検索装置において実行され、前記文書を所定の文字数で区切ることによって抽出される文字列を索引項目とする索引情報、及び、前記索引項目に含まれる部分文字列を節とするトライによって構成されるインデクスの構築方法であって、前記文書検索装置は、プロセッサ及び記憶部を備え、前記トライは、前記記憶部に生成され、前記索引情報は、前記索引項目が同じ索引情報によって構成される索引情報ブロックごとに管理され、前記トライの節は、一つ以上の前記索引情報ブロックが対応付けられることによって、前記索引情報が関連付けられ、前記インデクス構築方法は、前記プロセッサが、前記トライの節に複数の索引情報ブロックが対応する場合に、前記トライの節に関連付けられた索引情報の検索時間が所定の第１の閾値を超えると、前記対応する複数の索引情報ブロックに含まれる索引情報ブロックが途中で分割されないように、前記トライの節に関連付けられた索引情報を分割し、前記プロセッサが、前記検索対象の索引情報を含む索引情報ブロックに対応するトライの節の親の節に接続される新たな節を生成し、前記プロセッサが、前記新たに生成された節に前記分割された索引情報を関連付ける。

本発明の一形態によれば、長期間の運用などによって索引情報の追加が繰り返された場合であっても、索引情報の検索を所定の許容検索時間内で開始可能な状態を維持することができる。

以下、図を参照しながら、本発明の実施の形態を説明する。

（第１の実施の形態）
図１は、本発明の第１の実施の形態の文書登録検索システム１００の構成を示す図である。

第１の実施の形態では、肥大化した索引情報を分割することによって、検索開始時間を許容検索時間内に維持する方法について説明する。

本発明の第１の実施の形態の文書登録検索システム（トライ生成装置及び文書検索装置）１００は、出力装置１０１、入力装置１０２、ＣＰＵ（中央演算装置、Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１０３、主記憶装置１１１、及び二次記憶装置１０５を含む。出力装置１０１、入力装置１０２、ＣＰＵ１０３、主記憶装置１１１、及び二次記憶装置１０５は、バス１０４によって互いに接続される。なお、本発明の第１の実施の形態の文書登録検索システムでは、単一の計算機に機能が実装されているが、例えば、検索対象の文書本体は、別の計算機に格納されるなど、複数の計算機によって構成されていてもよい。

出力装置１０１は、ＣＰＵ１０３によって実行された検索結果などを表示する。出力装置１０１は、例えば、ディスプレイである。入力装置１０２は、文書を登録したり、検索コマンド及び検索文字列の入力を受け付けたりする。入力装置１０２は、例えば、キーボードである。

主記憶装置１１１は、インデクス登録用の機能及びインデクス検索用の機能を実現するための各構成部、及び、各処理で入出力されるデータなどを一時的に記憶する。ＣＰＵ１０３は、主記憶装置１１１に記憶された各構成部を実行することによって、インデクスの登録処理及び検索文字列の検索処理を実行する。二次記憶装置１０５は、各データ及び各構成部を格納する。

また、二次記憶装置１０５には、ディスクキャッシュ（図示せず）を備える。ディスクキャッシュは、ＨＤＤなどのアクセスが低速な記憶装置に記録されているデータの一部が移され、データの読み出しを高速化する。ディスクキャッシュは、二次記憶装置１０５が備えるＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）等の半導体メモリによって構成される。また、主記憶装置１１１も、ＲＡＭ等により構成される。二次記憶装置１０５は、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）又はフラッシュメモリなどによって構成される。

二次記憶装置１０５には、文書登録検索システム１００全体を制御するシステム制御部１１３に加え、登録用の処理として文書制御部１１２及びインデクス作成部１１４、検索及び更新用の処理としてトライ検索部１１７及び索引情報分割部１１８が格納される。システム制御部１１３、文書制御部１１２、インデクス作成部１１４、トライ検索部１１７及び索引情報分割部１１８は、プログラムである。各構成部は、主記憶装置１１１上に読み出され、ＣＰＵ１０３によって実行される。図１では、各構成部が、主記憶装置１１１上に読み出された状態を示している。また、主記憶装置１１１には、各データを一時的に格納するワークエリア１２１及びトライ格納領域１２２が割り当てられている。

次に各構成部によって実行される処理の概要を説明する。

システム制御部１１３は、出力装置１０１を介して利用者に情報を提示し、入力装置１０２を介して利用者からの入力を受け付ける。さらに、他の構成部の実行を制御する。

文書制御部１１２は、インデクス作成部１１４、トライ検索部１１７及び索引情報分割部１１８を制御する。

インデクス作成部１１４は、トライ初期化部１１５及び索引情報作成部１１６を含む。トライ初期化部１１５は、トライを初期化する。索引情報作成部１１６は、索引情報を作成（生成）する。具体的には、検索対象となる文書を任意のグラム数（文字数）ごとに区切った文字列に分割し、文書番号１０９、出現位置１１０及び文字列１２３を含む複数の索引情報を作成（生成）する。さらに、同一の文字列を有する索引情報ごとにまとめ、文書番号に基づいて昇順に整列する。文書番号が同じ文書の場合には出現位置に基づいて整列する。最後に、整列された索引情報から重複情報を削除し、索引情報ブロックを生成する。

トライ検索部１１７は、トライを検索し、目的の索引情報を取得する。

索引情報分割部１１８は、索引情報変更部１１９とトライ節分割部１２０を含む。索引情報変更部１１９は、トライ検索部１１７によって検索された索引情報ブロックの更新又は切り離しを実行する。トライ節分割部１２０は、複数の節をまとめられていたトライの節を分割し、新たに生成されたトライの節を切り離された索引情報ブロックに対応させる。

二次記憶装置１０５は、テキスト１０６、トライ１０７及び複数の索引情報１０８を格納する。テキスト１０６は、文書データである。索引情報１０８は、テキスト１０６に対応し、文書番号１０９、出現位置１１０及び文字列１２３を含む。トライ１０７は、トライの構造に関する情報を格納する。

以上が、本発明の第１の実施の形態の構成である。以下、本発明の第１の実施の形態の索引情報分割処理について説明する。

＜索引情報分割＞
索引情報分割処理は、利用者によって入力されたキーワードを用いたインデクスの検索又は更新処理において、ＣＰＵ１０３が、システム制御部１１３を介して文書制御部１１２を処理することによって実行される。

図２は、本発明の第１の実施の形態の索引情報分割前の索引情報の一部が肥大化しているインデクスの状態を示す図である。

インデクス２０２は、トライ２００、索引情報２０１及びポインタ情報２０３を含む。例えば、インデクス２０２に対して、文字列「あき」を更新する場合について説明すると、ＣＰＵ１０３は、トライ検索部１１７を実行し、トライ２００の１グラム目の節「あ」、当該節に接続される２グラム目のマージ節「あ〜ん」の順に辿り、ポインタ情報２０３（ｐｔｒ１）が示す索引情報をワークエリア１２１に格納する。

さらに、ＣＰＵ１０３は、索引情報分割部１１８を実行し、ワークエリア１２１に格納された索引情報を「あき」が出現するまで先頭から検索する。このとき、図１に示すように、索引情報ブロック「ああ」の検索中に１回、索引情報ブロック「あか」の検索中に１回、許容検索時間２０４の超過が生じる。

図３は、本発明の第１の実施の形態の索引情報分割前のインデクス２０２の索引情報を検索するために必要な検索時間を示すグラフ３００である。

本発明の第１の実施の形態では、索引情報ブロックごとに索引情報を分割するため、分割可能範囲は、１つ又は複数の索引情報ブロックごとになる。また、索引情報の先頭から、索引情報ブロック「あき」が検索されるまでの間にある１つ又は複数の索引情報ブロックが分割対象３０５となる。

本発明の第１の実施の形態では、文字列「あき」が検索されるまでに、まず、索引情報ブロック「ああ」で許容検索時間３０１を超過する。このとき、索引情報分割部１１８は、索引情報ブロック「ああ」には分割が必要と判断する。分割可能範囲３０２は、索引情報ブロック「ああ」となるため、次の許容検索時間３０３の計測開始は、索引情報ブロック「あい」からとなる。

引き続き、文字列「あき」を検索すると、索引情報ブロック「あか」を検索中に再び許容検索時間３０３を超過する。このとき、索引情報分割部１１８は、索引情報ブロック「あか」の分割が必要であると判断する。分割可能範囲３０４は、索引情報ブロック「あい」から索引情報ブロック「あか」となり、次の許容検索時間の計測開始は、索引情報ブロック「あき」からとなる。

索引情報ブロック「あき」は、検索対象の索引情報を含む索引情報ブロックであるため、ＣＰＵ１０３は、索引情報分割部１１８を実行し、索引情報ブロック「あき」を検索する。なお、「あき」以降の索引情報ブロックは、分割対象外３０６となる。例えば、別の機会に、索引情報ブロック「あわ」を検索した場合に、許容検索時間を超過すると索引情報分割部１１８を実行して索引情報を分割する。

図４は、本発明の第１の実施の形態の索引情報分割後のインデクス４０２を示す図である。

インデクス４０２は、トライ４００、索引情報４０１及びポインタ情報４０３を含む。前述したように、図２に示したインデクス２０２における、ポインタ情報２０３（ｐｔｒ１）によって示される索引情報が３つの索引情報に分割されている。具体的には、トライ２００では、節「あ」にマージ節「あ〜ん」の１つの節が接続されていたが、索引情報が分割されたトライ４００では、節「あ」に節「あ」、マージ節「い〜か」及びマージ節「き〜ん」の３つの節が接続される。そして、ポインタ情報４０３には新たにｐｔｒ８及びｐｔｒ９が追加され、ｐｔｒ８には索引情報ブロック「あい」から索引情報ブロック「あか」を含む索引情報を示すポインタ情報、ｐｔｒ９には索引情報ブロック「あき」から索引情報ブロック「あん」を含む索引情報を示すポインタ情報が格納される。また、ポインタ情報４０３のｐｔｒ１は、索引情報ブロック「ああ」のみを示すように変更される。

このように、許容検索時間を閾値として、マージ節「あ〜ん」を、節「あ」、マージ節「あ〜か」、及びマージ節「き〜ん」の３つの節又はマージ節に分割することによって、許容検索時間内に「あき」の検索を開始することができる。また、「あい」から「あか」までの文字列を索引項目とする索引情報についても許容検索時間内に検索を開始することができるようになる。

図５は、本発明の第１の実施の形態の索引情報分割後のインデクス４０２の索引情報を検索するために必要な検索時間を示すグラフ５００である。

グラフ５００は、１グラム目の節「あ」以下の節「あ」、マージ節「い〜か」、マージ節「き〜ん」における検索時間を示している。図３に示した分割対象３０５にあたる索引情報ブロック「ああ」から索引情報ブロック「あか」に関して、許容検索時間を基準とし、索引情報を分割した結果、分割対象３０５となったすべての索引情報ブロックの検索開始時間を許容検索時間５０１内に収めることができる。

また、前述のように、索引情報ブロック「あき」から索引情報ブロック「あん」を含む索引情報は、文字列「あき」を検索対象とした場合には、分割対象外である。この場合には、例えば、文字列「あん」について検索が実行された場合に、索引情報分割の対象となる。そして、索引情報分割部１１８によって索引情報の分割が必要と判定された場合には、索引情報ブロック「あき」から索引情報ブロック「あん」によって構成される索引情報は分割される。

＜索引情報分割部＞
図６は、本発明の第１の実施の形態の索引情報分割部１１８の処理手順を示すＰＡＤ（Ｐｒｏｇｒａｍ Ａｎａｌｙｓｉｓ Ｄｉａｇｒａｍ）である。

ＣＰＵ１０３は、まず、索引情報分割部１１８を実行し、トライ検索部１１７によって検索された節が有するポインタ情報が示す索引情報を取得する。そして、取得された索引情報をワークエリア１２１に格納し、格納先のアドレスを変数ＩＤＸに登録する。さらに、次の検索又は更新する索引情報へのアドレスを示す変数ＮＥＸＴにはＮＵＬＬ値（無効値）を登録する。また、索引情報の分割が必要か否かを判定するための変数ＣＨＧに‘Ｙ’（分割必要）を登録する（Ｓ６００）。

次に、ＣＰＵ１０３は、索引情報変更部１１９を実行し、索引情報を検索又は更新する。索引情報変更部１１９を実行した結果、索引情報を分割する必要がある場合には、変数ＣＨＧに‘Ｙ’が登録され、分割後に検索及び更新対象となる索引情報が格納されたワークエリア１２１に格納されたアドレスが変数ＮＥＸＴに格納される。分割する必要がない場合には、既に索引情報の検索又は更新が完了しているため、変数ＣＨＧに‘Ｎ’（分割不要）が登録される（Ｓ６０２）。

ＣＰＵ１０３は、索引情報変更部１１９の実行結果が‘Ｙ’であった場合、すなわち、索引情報の分割が必要と判定された場合には（Ｓ６０３）、トライ節分割部１２０を実行する。トライ節分割部１２０が実行されると、現在検索対象となっている索引情報に対応する節は、変数ＮＥＸＴが示す索引情報の一つ前の索引情報ブロックまでを管理する節と、変数ＮＥＸＴが示す索引情報を有する索引情報ブロックを管理する節に分割される。その後、変数ＮＥＸＴが示す索引情報ブロックを管理する節に対して、変数ＮＥＸＴが示す索引情報を示すポインタを登録する（Ｓ６０４）。

ＣＰＵ１０３は、変数ＩＤＸの内容に変数ＮＥＸＴの内容を登録し、再び索引情報変更部１１９を実行する（Ｓ６０５）。これらの一連の処理は、索引情報変更部１１９によって節の分割が不要と判定されるまで繰り返される（Ｓ６０１）。

＜索引情報変更部＞
図７は、本発明の第１の実施の形態の索引情報変更部１１９の処理手順を示すＰＡＤである。

ＣＰＵ１０３は、まず、検索開始時間として、変数ＴＩＭＥに現在時刻を格納する（Ｓ７００）。さらに、変数ＮＥＸＴに検索対象の索引情報が格納されたワークエリア１２１上のアドレスを格納する（Ｓ７０１）。

ＣＰＵ１０３は、変数ＮＥＸＴが示すワークエリア１２１上に読み出し可能な索引情報が１件以上残っている場合には（Ｓ７０２）、索引情報を１件読み出す（Ｓ７０３）。ワークエリア１２１に読み出し可能な索引情報が存在しない場合には、検索対象が索引情報に含まれていなかったことを示す検索・更新対象なしフラグ（‘Ｕ’）を呼び出し元に送信する（Ｓ７１９）。

ＣＰＵ１０３は、読み出された索引情報の索引項目が検索キーと一致する場合には（Ｓ７０４）、さらに、更新対象となっているか否かを判定する（Ｓ７０５）。そして、読み出された索引情報が更新対象であった場合には、当該索引情報又は当該索引情報の前後の位置にある索引情報を更新する（Ｓ７０６）。なお、索引情報を更新するか否かを判定する更新フラグは、索引情報分割部１１８を実行する呼出し元の処理で設定される。検索又は更新対象となる索引情報を取得した後は、以降の索引情報を検索又は更新する必要がないため、本処理を終了し、分割不要フラグ（‘Ｎ’）を呼び出し元に送信する（Ｓ７０７）。

一方、ＣＰＵ１０３は、読み出された索引情報の索引項目が検索キーと一致せず、検索時間が許容検索時間を超過した場合には（Ｓ７０８）、現在検索している索引情報ブロックの走査が終了するまで（Ｓ７０９）、順番に１件ずつ索引情報を読み出す（Ｓ７１０）。そして、読み出された索引情報の索引項目が検索キーと一致するか否かを確認し（Ｓ７１１）、更新対象である場合には（Ｓ７１２）、索引情報を更新する（Ｓ７１３）。検索又は更新対象となる索引情報が読み出された場合には、読み出された位置を検索又は更新処理の終点とし、分割不要フラグ（‘Ｎ’）を呼び出し元に送信する（Ｓ７１４）。

ＣＰＵ１０３は、検索時間が許容検索時間を超過し、検索中の索引情報ブロックの走査が終了すると、次の検索する対象の索引情報ブロックが存在するか否かを判定する（Ｓ７１５）。次の索引情報ブロックが存在する場合には、変数ＮＥＸＴに次の索引情報ブロックが格納されているワークエリアのアドレスを格納し（Ｓ７１６）、分割必要フラグ（‘Ｙ’）を呼び出し元に送信する（Ｓ７１７）。次の索引情報ブロックが存在しなかった場合には、検索対象が索引情報に含まれていなかったことを示す検索・更新対象なしフラグ（‘Ｕ’）を呼び出し元に送信する（Ｓ７１８）。

＜トライ節分割部＞
図８は、本発明の第１の実施の形態のトライ節分割部１２０の処理手順を示すＰＡＤである。

ＣＰＵ１０３は、まず、分割された索引情報を管理するための新たな節をトライ格納領域１２２に作成（生成）する（Ｓ８００）。そして、現在検索対象となっている節の親の節を取得し（Ｓ８０１）、新たに作成された節を取得された親の節に接続する（Ｓ８０２）。

ＣＰＵ１０３は、新たに生成された節の文字管理範囲を分割対象となった索引情報ブロックを示す文字から、分割前の節が管理していた最終文字までに変更する（Ｓ８０３）。また、分割された索引情報を示すポインタを新たに生成した節に登録する（Ｓ８０４）。そして、現在の検索対象となっている節には、文字管理範囲の最終文字を分割対象となった索引情報ブロックを示す文字の一つ前の文字を設定する（Ｓ８０５）。

本発明の第１の実施の形態によれば、索引情報ブロックが肥大化することによって検索性能が劣化することを防ぐことができる。

また、本発明の第１の実施の形態における索引情報分割処理は、索引情報の更新処理又は検索処理を実行する場合にあわせて実行される。したがって、利用者が通常の操作を実行しながら、意識せずに肥大化した索引情報を分割することができる。なお、利用者が文書登録検索システム１００の索引情報をメンテナンスするために、利用者の指示によって索引情報分割処理をするようにしてもよいし、定期的に索引情報分割処理が実行されるようにしてもよい。

（第２の実施の形態）
本発明の第１の実施の形態では、索引情報ブロックが肥大化した場合に索引情報ブロックを分割して検索性能を向上させる方法について説明したが、第２の実施の形態では、索引情報ブロックが過疎化した場合の処理について説明する。

前述したように、索引情報ブロックが過疎化すると、節又はマージ節が管理する索引情報量が非常に小さくなるため、トライのメモリ使用効率が悪化してしまう。本発明の第２の実施の形態では、過疎化した索引情報を統合し、トライのメモリ使用効率を向上する方法について説明する。

なお、本発明の第２の実施の形態において、本発明の第１の実施の形態と共通する内容については適宜説明を省略する。

図９は、本発明の第２の実施の形態の文書登録検索システム１００の構成を示す図である。

本発明の第１の実施の形態の文書検索システムとの相違点は、索引情報分割部１１８の代わりに索引情報統合部１２８が含まれている点である。その他の構成は、第１の実施の形態と同じである。

索引情報統合部１２８は、索引情報変更部１１９及びトライ節統合部１２９を含む。索引情報変更部１１９による処理は、第１の実施の形態と同じである。トライ節統合部１２９は、複数のトライ節を結合する。索引情報統合部１２８及びトライ節統合部１２９による処理の詳細は後述する。

以下、本発明の第２の実施の形態の索引情報統合処理について説明する。

＜索引情報統合＞
索引情報統合処理は、利用者が入力したキーワードを用いたインデクスの検索又は更新処理において、ＣＰＵ１０３が、システム制御部１１３を介して文書制御部１１２を処理することによって実行される。

図１０は、本発明の第２の実施の形態の索引情報統合前の索引情報の一部が過疎化しているインデクスの状態を示す図である。

インデクス１００２は、トライ１０００、索引情報１００１及びポインタ情報１００３を含む。図上部には、インデクス１００２の全体図を示し、図下部には、文字列「い」に対応するインデクス１００２の拡大図を示す。

インデクス１００２において、文字列「い」を検索する場合には、トライ検索部１１７を実行することによって、トライ１０００の１グラム目の節「い」に接続されるすべての節又はマージ節が管理する索引情報を検索する。検索対象となるトライ１０００の１グラム目の節「い」以下には、トライ１００４、索引情報１００６及びポインタ情報１００５が接続される。具体的には、節「い」には、節「あ」、マージ節「い〜た」、マージ節「ち〜を」、及び節「ん」が接続され、それぞれ小さな１つ又は複数の索引情報ブロックが管理されている。

図１１Ａ及び図１１Ｂは、本発明の第２の実施の形態の索引情報統合前の索引情報を検索するために必要な検索時間の例を示すグラフである。

グラフ１１００及びグラフ１１０２は、図１０に示したトライ１０００の１グラム目の節「い」に接続される節「あ」、マージ節「い〜た」、マージ節「ち〜を」、及び節「ん」に対応する索引情報を検索するために必要な検索時間を表している。

グラフ１１００及びグラフ１１０２について、いずれの節又はマージ節が示す索引情報ブロックを検索しても、許容検索時間１１０１及び許容検索時間１１０３を大幅に下回るにもかかわらず、トライ１０００において節又はマージ節を記憶するメモリが４つの節の分だけ消費されてしまう。

図１２Ａ及び図１２Ｂは、本発明の第２の実施の形態の索引情報統合後のインデクスの例を示す図である。

インデクス１２０２及びインデクス１２０６は、図１０に示したインデクス１００２に対し、索引情報統合処理を実行した例である。

インデクス１２０２は、図１１Ａに示した索引情報に対応している。インデクス１２０２は、トライ１２００、索引情報１２０１及びポインタ情報１２０３によって構成される。図１０と相違する点は、図１０に示したトライ１０００の１グラム目の節「い」に接続される節「あ」、マージ節「い〜た」、マージ節「ち〜を」、及び節「ん」の４つの節が１つのマージ節「あ〜ん」に統合されている点である。そして、ポインタ情報１２０３からｐｔｒ３、ｐｔｒ４、ｐｔｒ５が削除され、ｐｔｒ２は、索引情報ブロック「いあ」から索引情報ブロック「いん」を含む索引情報を示すポインタ情報を管理する。

また、インデクス１２０６は、図１１Ｂに示した索引情報に対応している。インデクス１２０６は、トライ１２０４、索引情報１２０５及びポインタ情報１２０７によって構成される。インデクス１２０６では、図１０に示したトライ１０００の１グラム目の節「い」に接続される節「あ」及びマージ節「い〜た」を１つのマージ節「あ〜た」に統合し、マージ節「ち〜を」及び節「ん」を１つのマージ節「ち〜ん」に統合している。ポインタ情報１２０７からはｐｔｒ３、ｐｔｒ５が削除される。ｐｔｒ２は、索引情報ブロック「いあ」から索引情報ブロック「いた」を含む索引情報を示すポインタ情報を管理し、ｐｔｒ４は索引情報ブロック「いち」から索引情報ブロック「いん」を含む索引情報を示すポインタ情報を管理する。

図１３Ａ及び図１３Ｂは、本発明の第２の実施の形態の索引情報統合後の索引情報を検索するために必要な検索時間の例を示すグラフである。

図１３Ａに示すグラフ１３００は、索引情報統合後のインデクス１２０２の検索時間を示すグラフである。グラフ１３００を参照すると、許容検索時間１３０１を基準として索引情報を統合した場合、１つに統合した索引情報ブロックの検索開始時間が許容検索時間１３０１に収まることがわかる。

また、図１３Ｂに示すグラフ１３０２は、索引情報統合後のインデクス１２０６の検索時間を示すグラフである。グラフ１３０２を参照すると、許容検索時間１３０３を基準として索引情報を統合した場合、統合したそれぞれの索引情報ブロックの検索開始時間が許容検索時間１３０３に収まることがわかる。

以上のように索引情報の統合することによって、節又はマージ節を生成するために消費されるメモリ量を低減することができ、メモリの使用効率を向上させることができる。

＜索引情報統合部＞
図１４は、本発明の第２の実施の形態の索引情報統合部１２８の処理手順を示すＰＡＤである。

ＣＰＵ１０３は、索引情報統合部１２８を起動し、検索中の節の番号を表す変数Ｉ、経過時間を計測する変数ＴＩＭＥ及び統合の対象となる節の数を格納する変数ＣＮＴに０を登録する。また、索引情報の統合が可能か否かを判断するために用いる変数ＣＨＧに‘Ｕ’（検索終了）を登録する（Ｓ１４００）。

ＣＰＵ１０３は、トライ検索部１１７によって検索された節に対応するポインタ情報が示す複数の索引情報をワークエリア１２１に格納し、格納先のアドレスを配列変数ＳＲＣＨに登録する（Ｓ１４０１）。また、配列の個数を変数ＳＲＣＨＣＮＴに登録する（Ｓ１４０２）。

具体的には、図１０に示すインデクス１００２では、トライ１０００の１グラム目の節「い」に接続される節「あ」、マージ節「い〜た」、マージ節「ち〜を」、及び節「ん」に対応する索引情報を示すポインタが配列変数ＳＲＣＨに格納される。すなわち、ｐｔｒ２、ｐｔｒ３、ｐｔｒ４、ｐｔｒ５が配列変数ＳＲＣＨに格納される。また、配列の個数ＳＲＣＨＣＮＴは４となる。

ＣＰＵ１０３は、変数ＳＴＡＲＴに検索開始時間を登録する（Ｓ１４０３）。

次に、ＣＰＵ１０３は、索引情報の検索処理を検索対象となる節が存在しなくなるまで繰り返し実行する（Ｓ１４０４）。

ＣＰＵ１０３は、まず、索引情報変更部１１９を実行し、索引情報を検索及び更新する。索引情報変更部１１９を実行した結果、検索継続の場合には変数ＣＨＧに‘Ｎ’、現在検索対象となっている節が管理する索引情報ブロックの検索を終了した場合には変数ＣＨＧに‘Ｕ’が登録される（Ｓ１４０５）。なお、索引情報変更部１１９の処理は、本発明の第１の実施の形態の図７にて説明した処理と同じである。なお、第２の実施の形態では、索引情報変更部１１９から返却されるフラグが‘Ｙ’の場合には「分割必要」の意味となるが、分割が必要な索引情報は統合する必要がないため、無視される。また、‘Ｎ’の場合には「分割不要」の意味となるが、検索対象の索引情報の検索時間が許容検索時間を超えずに統合対象になりうるため、検索を継続することになる。さらに、‘Ｕ’は、すべての検索対象の索引情報の検索が終了したことを示すことになる。

ＣＰＵ１０３は、変数ＣＨＧの値が‘Ｎ’の場合には、次の索引情報の検索を実行する（Ｓ１４１２）。また、変数ＣＨＧの値が‘Ｕ’の場合には（Ｓ１４０６）、統合対象になりうる索引情報ブロックのアドレスを格納する配列変数ＭＥＲＧＥのＣＮＴ番目に、現在検索していた索引情報ブロックのアドレスを登録し（Ｓ１４０７）、変数ＣＮＴの値に１を加算する（Ｓ１４０８）。さらに、検索による経過時間を計測し、変数ＴＩＭＥに設定する（Ｓ１４０９）。そして、次の検索対象へ移行するために、変数Ｉの値に１を加算し（Ｓ１４１０）、配列変数ＳＲＣＨのＩ番目に格納されている索引情報ブロックのアドレスを変数ＮＥＸＴに設定する（Ｓ１４１１）。

ＣＰＵ１０３は、この時点で許容検索時間を超過していた場合には（Ｓ１４１３）、変数ＣＮＴの値が１よりも大きいか否かを判定する。変数ＣＮＴの値が１より大きい場合には（Ｓ１４１４）、統合対象となる節と索引情報ブロックが存在するため、トライ節統合部１２９を実行することによって、節と索引情報ブロックを統合する（Ｓ１４１５）。そして、統合の有無に関わらず、変数ＴＩＭＥ及び変数ＣＮＴの値を０に設定し（Ｓ１４１６、Ｓ１４１７）、変数ＳＴＡＲＴに現在時刻を指定する（Ｓ１４１８）。

最後に、ＣＰＵ１０３は、すべての索引情報の検索が終了すると、変数ＣＮＴの値が１よりも大きいか否かを判定し（Ｓ１４１９）、変数ＣＮＴの値が１よりも大きい場合には、統合可能な節が存在するため、トライ節統合部１２９を実行し、節と索引情報ブロックを統合する（Ｓ１４２０）。

＜トライ節統合部＞
図１５は、本発明の第２の実施の形態のトライ節統合部１２９の処理手順を示すＰＡＤである。

ＣＰＵ１０３は、条件変数である変数Ｊに１を設定する（Ｓ１５００）。そして、統合対象となる節の親の節を取得し（Ｓ１５０１）、ＭＥＲＧＥ［１］からＭＥＲＧＥ［ＣＮＴ−１］に対応する節を削除する（Ｓ１５０２、Ｓ１５０３、Ｓ１５０４）。

ＣＰＵ１０３は、再び条件変数Ｊを１に設定し（Ｓ１５０５）、配列変数ＭＥＲＧＥの０番目から（ＣＮＴ−１）番目に対応する索引情報を連結することによって、ＭＥＲＧＥ［０］に対応する節に登録する（Ｓ１５０６、Ｓ１５０７、Ｓ１５０８）。

最後に、ＣＰＵ１０３は、索引情報の統合が完了すると、節に対応する文字管理範囲を、統合した索引情報を管理する文字管理範囲に書き換える（Ｓ１５０９）。

本発明の第２の実施の形態によれば、索引情報ブロックが過疎化することによってメモリ消費量が増大することを防ぎ、メモリの使用効率を向上させることができる。

また、本発明の第２の実施の形態における索引情報統合処理は、索引情報の更新処理又は検索処理を実行する場合にあわせて実行される。したがって、利用者が通常の操作を実行しながら、意識せずに過疎化した索引情報を統合することができる。なお、利用者が文書登録検索システム１００の索引情報をメンテナンスするために、利用者の指示によって索引情報統合処理をするようにしてもよいし、定期的に索引情報統合処理が実行されるようにしてもよい。また、第１の実施の形態の索引情報分割処理と、第２の実施の形態の索引情報統合処理とをそれぞれ定期的に実行することによって、索引情報の追加及び削除が繰り返された場合であっても、索引情報の検索を許容検索時間内で開始可能な状態を維持しつつ、トライのメモリ使用効率を維持させることができる。

（その他の実施の形態）
前述した第１の実施の形態及び第２の実施の形態では、節及び索引情報にひらがなを用いる場合を例として説明したが、カタカナ又は漢字を用いることも可能である。また、テキスト１０６が日本語以外の言語を含むものであれば、当該言語の文字を節及び索引情報に用いるようにすればよい。さらに、１バイト文字又は２バイト文字の文字コードを、２ビット又は４ビットに分割した記号コードの記号を繋げた記号列であってもよい。

また、前述した第１の実施の形態及び第２の実施の形態における許容検索時間は、索引情報分割と索引情報統合で同一の時間であっても異なる時間であってもよい。

本発明の第１の実施の形態の文書登録検索システムの構成を示す図である。 本発明の第１の実施の形態の索引情報分割前の索引情報の一部が肥大化しているインデクスの状態を示す図である。 本発明の第１の実施の形態の索引情報分割前のインデクスの索引情報を検索するために必要な検索時間を示すグラフである。 本発明の第１の実施の形態の索引情報分割後のインデクスを示す図である。 本発明の第１の実施の形態の索引情報分割後のインデクスの索引情報を検索するために必要な検索時間を示すグラフである。 本発明の第１の実施の形態の索引情報分割部の処理手順を示すＰＡＤである。 本発明の第１の実施の形態の索引情報変更部の処理手順を示すＰＡＤである。 本発明の第１の実施の形態のトライ節分割部の処理手順を示すＰＡＤである。 本発明の第２の実施の形態の文書登録検索システムの構成を示す図である。 本発明の第２の実施の形態の索引情報統合前の索引情報の一部が過疎化しているインデクスの状態を示す図である。 本発明の第２の実施の形態の索引情報統合前の索引情報を検索するために必要な検索時間の一例を示すグラフである。 本発明の第２の実施の形態の索引情報統合前の索引情報を検索するために必要な検索時間の別の例を示すグラフである。 本発明の第２の実施の形態の索引情報統合後のインデクスの一例を示す図である。 本発明の第２の実施の形態の索引情報統合後のインデクスの別の例を示す図である。 本発明の第２の実施の形態の索引情報統合後の索引情報を検索するために必要な検索時間の一例を示すグラフである。 本発明の第２の実施の形態の索引情報統合後の索引情報を検索するために必要な検索時間の別の例を示すグラフである。 本発明の第２の実施の形態の索引情報統合部の処理手順を示すＰＡＤである。 本発明の第２の実施の形態のトライ節統合部の処理手順を示すＰＡＤである。

符号の説明

１００ 文書登録検索システム
１０１ 出力装置
１０２ 入力装置
１０３ ＣＰＵ
１０４ バス
１０５ 二次記憶装置
１０６ テキスト
１０８ 索引情報
１０９ 文書番号
１１０ 出現位置
１１１ 主記憶装置
１１２ 文書制御部
１１３ システム制御部
１１４ インデクス作成部
１１５ トライ初期化部
１１６ 索引情報作成部
１１７ トライ検索部
１１８ 索引情報分割部
１１９ 索引情報変更部
１２０ トライ節分割部
１２１ ワークエリア
１２２ トライ格納領域
１２３ 文字列
１２８ 索引情報統合部
１２９ トライ節統合部
２００、４００、１０００、１００４、１２００、１２０４ トライ
２０１、４０１、１００１、１００６、１２０１、１２０５ 索引情報
２０２、４０２、１００２、１２０２、１２０６ インデクス
２０３、４０３、１００３、１００５、１２０３、１２０７ ポインタ情報
２０４、３０１、３０３、５０１、１１０１、１１０３、１３０１、１３０３ 許容検索時間
３００、５００、１１００、１１０２、１３００、１３０２ グラフ
３０２、３０４ 分割可能範囲
３０５ 分割対象
３０６ 分割対象外

Claims (10)

1. 文書を検索する文書検索装置において実行され、前記文書を所定の文字数で区切ることによって抽出される文字列を索引項目とする索引情報、及び、前記索引項目に含まれる部分文字列を節とするトライによって構成されるインデクスの構築方法であって、
   前記文書検索装置は、プロセッサ及び記憶部を備え、
   前記トライは、前記記憶部に生成され、
   前記索引情報は、前記索引項目が同じ索引情報によって構成される索引情報ブロックごとに管理され、
   前記トライの節は、一つ以上の前記索引情報ブロックが対応付けられることによって、前記索引情報が関連付けられ、
   前記インデクス構築方法は、
   前記プロセッサが、前記トライの節に複数の索引情報ブロックが対応する場合に、前記トライの節に関連付けられた索引情報の検索時間が所定の第１の閾値を超えると、前記対応する複数の索引情報ブロックに含まれる索引情報ブロックが途中で分割されないように、前記トライの節に関連付けられた索引情報を分割し、
   前記プロセッサが、前記検索対象の索引情報を含む索引情報ブロックに対応するトライの節の親の節の下位に接続される新たな節を生成し、
   前記プロセッサが、前記新たに生成された節に、前記分割された索引情報を関連付けることを特徴とするインデクス構築方法。
2. 前記インデクス構築方法は、
   前記プロセッサが、前記トライの節に関連付けられた索引情報の検索時間が所定の第２の閾値を超えない場合には、前記トライの節以外の節に対応する索引情報を前記所定の第２の閾値を超えるまでさらに検索し、
   前記プロセッサが、検索時間が前記所定の第２の閾値を超えた時点で、検索が完了した節の数が２以上の場合には、前記検索が完了した他の節に対応する索引情報を、前記トライの節に対応する索引情報に統合し、
   前記プロセッサが、前記検索が完了した他の節を前記トライから削除することを特徴とする請求項１に記載のインデクス構築方法。
3. 前記インデクス構築方法は、前記文書を検索するために索引情報を検索する場合に、前記トライの節に関連付けられた索引情報を分割する処理が実行されることを特徴とする請求項１に記載のインデクス構築方法。
4. 前記インデクス構築方法は、前記インデクスを再構築する要求を受け付けた場合に、前記トライに含まれるすべての節に対応する索引情報の検索を開始し、前記トライに含まれるすべての節において、前記トライの節に関連付けられた索引情報を分割する処理が実行されることを特徴とする請求項１に記載のインデクス構築方法。
5. 文書を検索する文書検索装置において実行され、前記文書を所定の文字数で区切ることによって抽出される文字列を索引項目とする索引情報、及び、前記索引項目に含まれる部分文字列を節とするトライによって構成されるインデクスの構築方法であって、
   前記文書検索装置は、プロセッサ及び記憶部を備え、
   前記トライは、前記記憶部に生成され、
   前記索引情報は、前記索引項目が同じ索引情報によって構成される索引情報ブロックごとに管理され、
   前記トライの節は、一つ以上の前記索引情報ブロックが対応付けられることによって、前記索引情報が関連付けられ、
   前記インデクス構築方法は、
   前記プロセッサが、前記トライの節に関連付けられた索引情報の検索時間が所定の第１の閾値を超えない場合には、前記トライの節以外の節に対応する索引情報を前記所定の第１の閾値を超えるまでさらに検索し、
   前記プロセッサが、検索時間が前記所定の第１の閾値を超えた時点で、検索が完了した節の数が２以上の場合には、前記検索が完了した他の節に対応する索引情報を、前記トライの節に対応する索引情報に統合し、
   前記プロセッサが、前記検索が完了した他の節を前記トライから削除することを特徴とするインデクス構築方法。
6. 前記インデクス構築方法は、
   前記プロセッサが、前記トライの節に複数の索引情報ブロックが対応する場合に、前記トライの節に関連付けられた索引情報の検索時間が所定の第２の閾値を超えると、前記対応する複数の索引情報ブロックに含まれる索引情報ブロックが分割されないように、前記トライの節に関連付けられた索引情報を分割し、
   前記プロセッサが、前記検索対象の索引情報を含む索引情報ブロックに対応するトライの節の親の節の下位に接続される新たに節を生成し、
   前記プロセッサが、前記新たに生成された節に、前記分割された索引情報を関連付けることを特徴とする請求項５に記載のインデクス構築方法。
7. 前記インデクス構築方法は、前記文書を検索するために索引情報を検索する場合に、前記トライの節に関連付けられた索引情報を統合する処理が実行されることを特徴とする請求項５に記載のインデクス構築方法。
8. 前記インデクス構築方法は、前記インデクスを再構築する要求を受け付けた場合に、前記トライに含まれるすべての節に対応する索引情報の検索を開始し、前記トライに含まれるすべての節において、前記トライの節に関連付けられた索引情報を統合する処理が実行されることを特徴とする請求項５に記載のインデクス構築方法。
9. プロセッサ及び記憶部を備え、インデクスを利用して文書を検索する文書検索装置であって、
   前記インデクスは、前記文書を所定の文字数で区切ることによって抽出される文字列を索引項目とする索引情報、及び、前記索引項目に含まれる部分文字列を節とするトライによって構成され、
   前記トライは、前記記憶部に生成され、
   前記索引情報は、前記索引項目が同じ索引情報によって構成される索引情報ブロックごとに管理され、
   前記トライの節は、一つ以上の前記索引情報ブロックが対応付けられることによって、前記索引情報が関連付けられ、
   前記プロセッサは、
   前記トライの節に複数の索引情報ブロックが対応する場合に、前記トライの節に関連付けられた索引情報の検索時間が所定の閾値を超えると、前記対応する複数の索引情報ブロックに含まれる索引情報ブロックが途中で分割されないように、前記トライの節に関連付けられた索引情報を分割し、
   前記検索対象の索引情報を含む索引情報ブロックに対応するトライの節の親の節の下位に接続される新たな節を生成し、
   前記新たに生成された節に、前記分割された索引情報を関連付けることを特徴とする文書検索装置。
10. 文書を所定の文字数で区切ることによって抽出される文字列を索引項目とする索引情報、及び、前記索引項目に含まれる部分文字列を節とするトライによって構成されるインデクスを構築する処理を文書検索装置に実行させるプログラムであって、
    前記トライを生成する手順と、
    前記索引項目が同じ索引情報を索引情報ブロックとして管理する手順と、
    前記トライの節に、一つ以上の前記索引情報ブロックを対応させることによって、前記索引情報を関連付ける手順と、
    前記トライの節に複数の索引情報ブロックが対応する場合に、前記トライの節に関連付けられた索引情報の検索時間が所定の閾値を超えると、前記対応する複数の索引情報ブロックに含まれる索引情報ブロックが途中で分割されないように、前記トライの節に関連付けられた索引情報を分割する手順と、
    前記検索対象の索引情報を含む索引情報ブロックに対応するトライの節の親の節の下位に接続される新たな節を生成する手順と、
    前記新たに生成された節に、前記分割された索引情報を関連付ける手順と、を前記文書検索装置に実行させることを特徴とするインデクス構築プログラム。

Images