記号列検索方法、プログラムおよび装置ならびにそのトライの生成方法、プログラムおよび装置
【課題】メモリ容量が少ない機器であっても、トライによる高速な文書検索を実現する。
【解決手段】コンピュータが、トライにおける節を共通化したインデクス階層化節を作成し、この節を境目とし、第１のトライ９００と第２のトライ９０４とに階層化する。このうち、第１のトライ９００は主記憶装置の上位部分文字列格納領域に格納する。また、第２のトライ９０４は二次記憶装置の上位部分文字列格納領域に格納する。そして、このコンピュータは、検索タームの入力を受け付けると、この第１のトライ９００および第２のトライ９０４上における、前記検索タームを構成する文字列の文字を辿って、当該文字列に対応する索引情報に到達する。そして、その索引情報を読み出して、その検索タームを含む文書およびその文書における位置を検索する。
【解決手段】コンピュータが、トライにおける節を共通化したインデクス階層化節を作成し、この節を境目とし、第１のトライ９００と第２のトライ９０４とに階層化する。このうち、第１のトライ９００は主記憶装置の上位部分文字列格納領域に格納する。また、第２のトライ９０４は二次記憶装置の上位部分文字列格納領域に格納する。そして、このコンピュータは、検索タームの入力を受け付けると、この第１のトライ９００および第２のトライ９０４上における、前記検索タームを構成する文字列の文字を辿って、当該文字列に対応する索引情報に到達する。そして、その索引情報を読み出して、その検索タームを含む文書およびその文書における位置を検索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書検索システムに使用する検索インデクス作成技術に関する。
【背景技術】
【０００２】
従来、コンピュータが、大規模な文書データベースから、指定された検索文字列が含まれる文書を高速に検索する技術として、インデクスを用いるものが知られている(以下、方式１と呼ぶ)。このインデクスは、（１）検索される文書に含まれるキーワードを示した索引項目と、（２）その索引項目を含む文書を識別する文書識別情報や、当該文書における索引項目の文書位置等を示した索引情報と、が記録されたものである。また、方式１のようなインデクスを用いた文書検索方法において、文書に対する索引項目はトライ（trie）のような木構造により管理される。
【０００３】
このトライとは、検索対象となる文字列すなわちキーワードの集合（以下、キー集合と呼ぶ）における各キーワード（以下、キーと呼ぶ）に共通な部分文字列を、共通の節として括り出して作られる木構造である。このトライは、インデクスの検索の際に用いられ、コンピュータは、検索ターム中の文字列をキーに分解し、このキーで節を辿りトライ上を探索する。そして、コンピュータは、トライの末端の節に到達すると、その末端の節に設定されたポインタ情報を読み取り、検索タームに対応する索引情報を読み出すことができる。
【０００４】
このトライの概要を、図１を用いて説明する。図１は、比較例のインデクスを例示した図である。前記したとおり、インデクス１０５は、索引項目を木構造で構成したトライ１００と、その索引項目に対応する索引情報１０１とを含んで構成される。なお、このトライ１００の末端の文字列の節には、索引情報１０１を読み出すためのポインタ情報１０２が設定される。
【０００５】
図１に例示したトライ１００は３グラム（キーの文字数が３個）のトライであり、一例として、「あ」から始まる文字列のトライを示している。例えば、このようなトライにおいて、１グラム目の「あ」の節に続く２グラム目の節として「あ」、「い」、「う」、…、「ん」の節が設定され、そのさらに次に３グラム目の節として、「あ」、…、「ん」の節が設定される。そして、末端の節（つまり、図１の３グラム目の節）には、索引情報１０１を読み出すためのポインタ情報１０２が設定されている。
【０００６】
ここで、コンピュータが、このトライ１００を辿って「あいち」という文字列を含む文書の文書番号およびその文書における文字位置を検索する場合には、以下のようになる。
【０００７】
まず、コンピュータは、１グラム目の「あ」の節、この節に繋がる２グラム目の「い」の節、この節に繋がる３グラム目の「ち」の節、というように節を辿る。そして、コンピュータは、末端の節である「ち」の節に設定されたポインタ情報１０２（「ｐｔｒ６１」）により、記憶装置の所定領域から「あいち」に関する索引情報１０１を読み出す。つまり、「あいち」を含む文書の文書番号（文書識別情報）１０３である「００１」と、その文書における「あいち」の文字位置１０４である「２１」とを読み出す。
【特許文献１】特開平１１−１４３９０１号公報
【特許文献２】特開昭５９−１４８９２２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ここで、コンピュータが、前記したトライを用いてインデクスを管理する場合において、文書の索引情報の検索を高速にするには、個々の索引情報の容量を小さくしてトライにおけるグラム数（キーに共通な部分文字列（記号列）の文字数）を大きくすることが考えられる。しかし、このようにグラム数の大きいトライは、メモリに格納しきれないことがある。このような問題は、特に、携帯電話機やＤＶＤ（Digital Versatile Disk）プレイヤ等、メモリ容量の少ない機器に文書検索システムを実装する場合に大きな問題となる。
【０００９】
そこで、本発明は、前記した問題を解決し、メモリ容量が少ない機器であっても、トライによる高速な文書検索を実現する手段を提供することを目的とする。
【課題を解決するための手段】
【００１０】
前記した課題を解決するため、本発明は、主記憶装置および二次記憶装置を備えるコンピュータ（記号列検索装置）が、まず、トライを作成（生成）する。次に、このトライにより検索される索引情報の必要検索時間を参照して、この生成したトライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算する。そして、この計算した節ごとの必要検索時間が、所定の閾値以下か否かを判断する。ここで、必要検索時間が、所定の閾値以下である節のうち、同じ節を親とする節同士を共通化したインデクス階層化節を生成する。つまり、複数の節を共通化し、まとめた節を生成する。そして、この共通化の対象である節およびこの節から先に繋がる節を、インデクス階層化節に置き換えた第１のトライを生成する。生成した第１のトライは、主記憶装置の所定領域に格納する。なお、共通化の対象である節およびこの節から先に繋がる節については、第２のトライとして二次記憶装置の所定領域に移動する。そして、第１のトライにおけるインデクス階層化節には、この第２のトライの格納領域を示すポインタ情報を設定する。これにより、コンピュータが検索タームに含まれる記号列（文字列を含む）により索引情報の検索を行うとき、主記憶装置に格納される第１のトライを辿った後、二次記憶装置に格納される第２のトライにアクセスして、この記号列（文字列を含む）に対応する索引情報に辿りつくことができる。なお、記号列とは、１バイト文字や２バイト文字の文字コードを、２ビットや４ビットに分割した記号コードの記号を繋げたものである。
【００１１】
このように、本発明の記号列検索装置は、トライを第１のトライと第２のトライとに階層化し、それぞれを主記憶装置と二次記憶装置とに格納する。従って、主記憶装置（メモリ）の容量が少ない機器（コンピュータ）であっても、大きな容量のトライを実装することができる。つまり、記号列検索装置は、トライによる高速な文書検索を行うことができる。また、記号列検索装置は、第１のトライを作成するとき、この第１のトライにおける節を共通化するので、主記憶装置に格納される第１のトライの節の数を低減することができる。つまり、第１のトライの容量を低減するので、主記憶装置（メモリ）の容量が少ないコンピュータであっても、より一層トライを搭載しやすくなる。さらに、この第１のトライにおいて、共通化するのは、その節から先に繋がる索引情報の必要検索時間の合計が所定の閾値以下の節を対象とした。つまり、必要検索時間の合計が所定の閾値を超える節については、第２のトライを経由せず、すぐに索引情報に到達するようにした。これにより、トライを用いた索引情報の検索効率を向上させることができる。
【発明の効果】
【００１２】
本発明によれば、メモリ容量が少ない機器であっても、トライによる高速な文書検索を行うことができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照しながら、本発明を実施するための最良の形態（以下、実施の形態という）を、説明する。
【００１４】
＜第１の実施の形態＞
図２は、本発明の実施の形態である文書登録検索システムの構成例を示した図である。
【００１５】
本発明の実施の形態である文書登録検索システム（トライ生成装置および記号列検索装置）２００は、図２に示すように、ディスプレイ２０１、キーボード２０２、ＣＰＵ（中央演算装置、Central Processing Unit)２０３、主記憶装置２０９、二次記憶装置２０５およびこれらを接続するバス２０４を含んで構成される。
【００１６】
ディスプレイ（出力装置）２０１は、ＣＰＵ２０３による検索結果を表示する。キーボード２０２（入力装置）は、テキスト２０６の登録および検索のコマンドや、検索タームを入力する。ＣＰＵ２０３は、後記する各プログラムを実行することで、インデクスの登録処理および検索キーワードの検索処理を実行する。主記憶装置２０９は、インデクス登録用および検索用プログラム、ならびに入出力されるデータ等を一時的に格納する。二次記憶装置（二次記憶装置）２０５は、各データおよび各プログラムを格納する。
【００１７】
また、この二次記憶装置２０５には、ディスクキャッシュ（図示せず）を備える。このディスクキャッシュは、ＨＤＤ等、アクセスが低速な記憶装置に記録されているデータの一部を写し、データの読み出しを高速化する手段である。このディスクキャッシュは、二次記憶装置２０５が備えるＲＡＭ（Random Access Memory）等の半導体メモリにより構成される。また、主記憶装置２０９も、ＲＡＭ等により構成され、二次記憶装置２０５は、ＨＤＤ（Hard Disk Drive）やフラッシュメモリ等により構成される。
【００１８】
二次記憶装置２０５には、文書登録検索システム２００全体の制御を司るシステム制御プログラム２１２に加え、登録用のプログラムとして文書登録制御プログラム２１０およびインデクス作成登録プログラム２１３、検索用のプログラムとして検索制御プログラム２１１およびインデクス検索プログラム２２１が格納される。これらのプログラムは、ＣＰＵ２０３により、主記憶装置２０９上に読み出され、実行される。図２は、これらのプログラムが、主記憶装置２０９上に読み出された状態を示している。また、この主記憶装置２０９には、各データを一時的に格納するワークエリア２２５、上位部分文字列格納領域２２４およびトライ格納領域２２６が確保されている。
【００１９】
ここで各プログラムの概略を説明する。
【００２０】
システム制御プログラム２１２は、ディスプレイ２０１およびキーボード２０２を用いたユーザ入出力の制御を行い、その他の各プログラムの実行を制御するプログラムである。
【００２１】
文書登録制御プログラム２１０は、インデクス作成登録プログラム２１３を制御するプログラムである。
【００２２】
インデクス作成登録プログラム２１３は、トライ初期化プログラム２１４と、索引情報作成プログラム２１５と、インデクス階層化プログラム２１６とを含んで構成される。トライ初期化プログラム２１４はトライの初期化を行うプログラムである。なお、ＣＰＵ２０３がこのトライ初期化プログラム２１４を実行することで、請求項におけるトライ初期化部の機能を実現する。索引情報作成プログラム２１５は、索引情報２０７（後記）を作成するプログラムである。インデクス階層化プログラム２１６は、インデクスの階層化を行う、つまり、トライを２つの階層に分けるプログラムである。
【００２３】
このインデクス階層化プログラム２１６は、インデクス階層化節作成プログラム２１７と、インデクス検索時間比較プログラム２１８と、隣接部分文字列検索プログラム２１９と、インデクス階層化節分割プログラム２２０とを含んで構成される。
【００２４】
インデクス階層化節作成プログラム２１７は、インデクス階層化節（詳細は後記）を作成するプログラムである。なお、ＣＰＵ２０３がインデクス階層化節作成プログラム２１７を実行することで請求項におけるインデクス階層化節生成部の機能を実現する。
【００２５】
インデクス検索時間比較プログラム２１８は、索引情報２０７の必要検索時間と目標検索時間（詳細は後記）とを比較するプログラムである。なお、ＣＰＵ２０３がインデクス検索時間比較プログラム２１８を実行することで請求項におけるインデクス検索時間比較部の機能を実現する。
【００２６】
隣接部分文字列検索プログラム２１９は、トライにおいて同じ節を親とする節（つまり兄弟関係にある節）を探索するプログラムである。なお、ＣＰＵ２０３が隣接部分文字列検索プログラム２１９を実行することで、請求項における隣接部分記号列検索部の機能を実現する。
【００２７】
インデクス階層化節分割プログラム２２０は、階層化されたトライのうち、下位のトライ（第２のトライ）の容量が所定の閾値を超えたときインデクス階層化節を分割するプログラムである。
【００２８】
さらに、インデクス検索プログラム２２１は、上位部分文字列検索プログラム２２２と、下位部分文字列検索プログラム２２３とを含んで構成される。上位部分文字列検索プログラム２２２は、階層化されたトライのうち上位のトライ（第１のトライ）を検索するプログラムである。下位部分文字列検索プログラム２２３は、階層化されたトライのうち、下位のトライ（第２のトライ）を検索するプログラムである。なお、ＣＰＵ２０３がインデクス検索プログラム２２１を実行することで、請求項におけるインデクス検索部の機能を実現する。
【００２９】
なお、二次記憶装置２０５は、文書データであるテキスト２０６と、そのテキスト２０６の索引情報２０７とを記憶する。さらに、この二次記憶装置２０５には、前記した第２のトライを格納する下位部分文字列格納領域２０８が確保されている。
【００３０】
また、前記したプログラムの詳細は、本実施の形態における登録処理および検索処理の説明の項において詳細に述べる。
【００３１】
＜登録処理＞
ユーザが入力した文書データ（テキスト２０６）の登録処理は、ＣＰＵ２０３が、システム制御プログラム２１２経由で、文書登録制御プログラム２１０を実行することで行われる。
【００３２】
＜インデクス作成登録プログラム＞
次に、インデクス作成登録プログラム２１３について、図２を参照しつつ、図３のＰＡＤ（Program Analysis Diagram）を用いて説明する。図３は、図２のインデクス作成登録プログラムの処理手順を示した図である。
【００３３】
まず、図２のＣＰＵ２０３は、トライ初期化プログラム２１４を起動し、トライ格納領域２２６の初期設定を行う（Ｓ３００）。このときのトライ初期化プログラム２１４による初期設定の詳細については、図４を用いて後記する。
【００３４】
次に、ＣＰＵ２０３は、索引情報作成プログラム２１５を起動し、索引情報２０７を作成し、二次記憶装置２０５へ格納する（Ｓ３０１）。つまり、ＣＰＵ２０３は、二次記憶装置２０５に格納されているテキスト２０６から、所定の部分文字列と、テキスト２０６における文書番号（文書識別情報）２２７と、その文字位置（出現位置情報）２２８とを抽出し、索引情報２０７を作成し、二次記憶装置２０５へ格納する。
【００３５】
例えば、ＣＰＵ２０３は、索引情報作成プログラム２１５により、文書番号「００１」の「・・・あいち・・・」というテキスト２０６から、この「あいち」という文字列が文書番号「００１」の文書に含まれ、その文書における「あいち」という文字列の先頭の文字「あ」の文字位置は「２１」であることを示す索引情報２０７を作成する。そして、この作成した索引情報２０７を二次記憶装置２０５へ格納する。なお、ＣＰＵ２０３は、この索引情報２０７それぞれに対し、この索引情報２０７を検索するのに要する検索時間（必要検索時間）を計測し、索引情報２０７に付加する。
【００３６】
次に、ＣＰＵ２０３は、インデクス階層化プログラム２１６を起動する。そして、ＣＰＵ２０３は、索引情報作成プログラム２１５によって作成された索引情報２０７をもとにインデクス階層化処理を行う（Ｓ３０２）。このときのインデクス階層化処理の詳細は、図６を用いて後記する。
【００３７】
＜トライ初期化プログラム＞
次に、トライ初期化プログラム２１４について、図２を参照しつつ、図４のＰＡＤを用いて詳細に説明する。図４は、図２のトライ初期化プログラムの処理手順を示した図である。
【００３８】
まず、図２のＣＰＵ２０３は、既にトライが作成され、主記憶装置２０９にトライ格納領域２２６が設定されているか否かを判定する（Ｓ４００）。ここで、未だトライが作成されておらず、トライ格納領域２２６が設定されていないとき（Ｓ４００のＮｏ）、ＣＰＵ２０３は、テキスト２０６で用いられるすべての文字をグラム数分（例えば、３グラム分）の文字列に分割する。例えば、テキスト２０６において「あいちはく」という文字列が含まれていたとき、ＣＰＵ２０３は、この文字列を３グラム分の文字列「あいち」と、「はく＿」とに分割する。なお、「＿」は空白を表す。そして、ＣＰＵ２０３は、この分割した文字列の１文字をキー（節）として、トライを作成し、トライ格納領域２２６を設定する（Ｓ４０１）。例えば、ＣＰＵ２０３は、１グラム目の節に「あ」、２グラム目の節に「い」、３グラム目の節に「ち」を設定したトライを作成し、トライ格納領域２２６に設定する。このとき、ＣＰＵ２０３が作成するトライの具体例は、図５を用いて後記する。
【００３９】
そして、ＣＰＵ２０３は、トライの末端の節それぞれに、その文字列に対応する索引情報２０７のポインタ情報を設定する（Ｓ４０２）。
【００４０】
ここで、ＣＰＵ２０３が、トライ初期化プログラム２１４により作成するトライを、図５を用いて説明する。図５は、図２のＣＰＵが、トライ初期化プログラムにより作成するトライを含むインデクスを例示した図である。
【００４１】
図５に例示するように、インデクス５００は、索引項目を木構造で構成したトライ５０１と、その索引項目に対応する索引情報５０２とを含んで構成される。なお、このトライ５０１の末端の文字列の節には、索引情報を読み出すためのポインタ情報５０３が設定される。なお、図５において、「あ」から始まる文字列のトライのみを示しているが、この他にも「い」から始まる文字列のトライ、「う」から始まる文字列のトライ等も存在する。
【００４２】
例えば、図５に例示したトライ５０１において、１グラム目の「あ」の節に続く２グラム目の節として「あ」、「い」、「う」、…、「ん」の節が設定され、そのさらに次に３グラム目の節として、「あ」、…、「ん」の節が設定される。そして、末端の節（つまり、図５の３グラム目の節）には、索引情報５０２を読み出すためのポインタ情報５０３が設定されている。例えば、「あいち」に関する索引情報２０７のポインタ情報５０３は「ｐｒｔ６１」であり、この索引情報２０７の必要検索時間は「１.１２７」であることを示す。
【００４３】
なお、図５において説明を省略しているが、ＣＰＵ２０３は、トライの初期設定を行うとき、トライを構成する節それぞれに、その節から繋がる索引情報２０７の必要検索時間を設定しておく。
【００４４】
このとき、ＣＰＵ２０３は、トライ５０１の末端の節（例えば、図５に例示したトライ５０１の３グラム目の節）には、その節に繋がる索引情報２０７の必要検索時間を設定し、トライ５０１の末端の節以外の節（例えば、図５に例示したトライ５０１の１グラム目および２グラム目の節）には、この節に繋がる節に設定された必要検索時間の合計値を設定する。
【００４５】
例えば、図５に例示したトライ５０１の２グラム目の「あ」の節の次に、３グラム目の節として、「あ」〜「ん」の節が繋がっている場合、ＣＰＵ２０３は、この２グラム目の「あ」の節の必要検索時間として、３グラム目の「あ」〜「ん」それぞれの節の必要検索時間を合計した値を設定する。また、ＣＰＵ２０３は、この１グラム目の「あ」の節の必要検索時間を設定する場合も同様に、２グラム目の「あ」〜「ん」それぞれに設定された必要検索時間を合計した値を設定する。このように、ＣＰＵ２０３は、トライ５０１の末端の節から順に、その１グラム目の節まで、索引情報２０７の必要検索時間の合計値を計算し、この計算した値を各節に設定する。このようにして節それぞれに設定された必要検索時間は、ＣＰＵ２０３がトライの各節を共通化し、階層化するときに参照される。このときの各節の共通化および階層化の処理の詳細については、図６および図７を用いて後記する。
【００４６】
なお、図５において１グラム目「あ」の節から始まるトライ５０１を例示しているが、これ以外にもトライの１グラム目の「い」〜「わ」の節から始まるトライもトライ格納領域２２６に格納される。また、図示を省略しているが、これら１グラム目の節の親となる節として、０グラム目の節が設定されているものとする。これにより、ＣＰＵ２０３により、この１グラム目「あ」の節に隣接する節が検索されると、１グラム目の「い」〜「わ」の節が検索されることになる。
【００４７】
＜インデクス階層化プログラムおよびインデクス検索時間比較プログラム＞
次に、インデクス階層化プログラム２１６およびインデクス検索時間比較プログラム２１８について、図２を参照しつつ、図６および図７のＰＡＤを用いて詳細に説明する。図６および図７は、図２のインデクス階層化プログラムの処理手順を示した図である。
【００４８】
まず、ＣＰＵ２０３は、主記憶装置２０９のトライ格納領域２２６から、トライ初期化プログラム２１４により作成されたトライを読み出すと、このインデクス階層化プログラム２１６の実行処理に用いる変数（ｔｏｔａｌ,Ｍ,Ｎ,Ｌ,Ｐ）の初期値を設定する。ここで、ＣＰＵ２０３は、初期値として、ｔｏｔａｌ=０、Ｍ＝１、Ｎ＝１、Ｌ＝１、Ｐ＝１を設定する（Ｓ６００）。
【００４９】
なお、この変数ｔｏｔａｌは、トライの各節に設定された必要検索時間の合計値を計算するために用いる変数である。変数Ｍは、目標検索時間以上の節の数をカウントするために用いる変数である。変数Ｎは、隣接する節のうち、処理を実行した節の数をカウントするために用いる変数である。変数Ｌは、目標検索時間未満の節のうち、処理を実行した節の数をカウントするために用いる変数である。変数Ｐは、変数ｔｏｔａｌが、目標検索時間未満の節の数をカウントするために用いる変数である。なお、この目標検索時間とは、ＣＰＵ２０３が、当該節を、共通化するか否かを判断するために用いる閾値であり、主記憶装置２０９の所定領域に格納される。
【００５０】
次に、ＣＰＵ２０３は、隣接部分文字列検索プログラム２１９を起動し、隣接する節を探索し、その節の数をカウントする（Ｓ６０１）。ここでは、まず、ＣＰＵ２０３は、トライの１グラム目の節の数をカウントする。つまり、ＣＰＵ２０３は、トライの０グラム目の節（図示せず）を親とし、兄弟関係にある節の数をカウントする。例えば、図５に例示したトライの１グラム目「あ」の節と、トライの１グラム目の「い」〜「わ」の節まで（図５において図示省略）の数をカウントする。
【００５１】
次に、ＣＰＵ２０３は、変数Ｎの値が、Ｓ６０１でカウントした数以下であるか否かを判断する（Ｓ６０２）。ここで、変数Ｎの値が、Ｓ６０１でカウントした数以下であるとき判断したとき、Ｓ６０３へ進む。
【００５２】
そして、ＣＰＵ２０３は、隣接する節のうち、まだ処理を行っていない節を１つ選択する（Ｓ６０３）。例えば、トライの１グラム目の「あ」〜「わ」の節から、まだ処理を行っていない、「あ」の節を選択する。
【００５３】
一方、Ｓ６０２において、変数ＮがＳ６０１でカウントした数を超える数のとき、Ｓ６０７へ進む。つまり、ＣＰＵ２０３が、隣接する節のうち、その節における必要検索時間が目標検索時間未満の節（目標検索時間非超過部分文字列の節）すべてについて、階層化が終了すると、Ｓ６０７へ進む。
【００５４】
ＣＰＵ２０３は、Ｓ６０３で節を選択した後、この選択した節に設定されている必要検索時間を読み出す（Ｓ６０４）。例えば、図５に例示するトライ５０１の１グラム目の「あ」の節に設定されている必要検索時間を読み出す。そして、ＣＰＵ２０３は、この読み出した必要検索時間に基づき、節の共通化処理を実行する（Ｓ６０５）。この後、ＣＰＵ２０３は、変数Ｎの値をインクリメントし（Ｓ６０６）、Ｓ６０７へ進む。このＳ６０５における節の共通化処理について、図７を用いて説明する。
【００５５】
まず、ＣＰＵ２０３は、図６のＳ６０３で選択した節における必要検索時間が、目標検索時間以上か否かを判断する（図７のＳ７００）。例えば、図５に例示したトライ５０１の１グラム目の「あ」の節に設定された必要検索時間が「５．０」のとき、この値が、目標検索時間以上か否かを判断する。なお、このときの判断は、前記したインデクス検索時間比較プログラム２１８により行う。
【００５６】
ここで、Ｓ６０３で選択した節における必要検索時間が、目標検索時間以上であるとき（図７のＳ７００のＹｅｓ）、ＣＰＵ２０３は、変数Ｍの値をインクリメントする（Ｓ７０１）。このようにして、ＣＰＵ２０３は、必要検索時間が、目標検索時間以上である節（目標検索時間超過部分文字列の節）の数をカウントする。また、ＣＰＵ２０３は、この目標検索時間超過部分文字列と判断した節を、共通化する節の対象として主記憶装置２０９の所定領域に記憶しておく。例えば、図５に例示する１グラム目の「あ」の節に設定された必要検索時間が、目標検索時間以上だったとき、この１グラム目の「あ」の節の情報を、共通化する節の対象として主記憶装置２０９の所定領域に記憶しておく。
【００５７】
この後、ＣＰＵ２０３は、変数Ｐの値を「０」、変数ｔｏｔａｌの値も「０」にして（Ｓ７０２）、図６のＳ６０６へ進む。つまり、ＣＰＵ２０３は、必要検索時間が目標検索時間以上である節（目標検索時間超過部分文字列の節）については、共通化処理を行わないと判断し、隣接する別の節の処理に移る。例えば、図５に例示するトライの１グラム目の「あ」の節に設定された必要検索時間が、目標検索時間以上だったとき、１グラム目の別の節（「い」の節等）の処理に移る。
【００５８】
一方、Ｓ７００において、Ｓ６０３（図６参照）で選択した節における必要検索時間が、目標検索時間未満のとき（Ｓ７００のＮｏ）、ＣＰＵ２０３は、変数ｔｏｔａｌに、Ｓ６０３で選択した節における必要検索時間を加算する（Ｓ７０３）。例えば、図５に例示するトライの１グラム目の「あ」の節に設定された必要検索時間「５．０」であり、この必要検索時間が目標検索時間未満のとき、変数ｔｏｔａｌに、この必要検索時間「５．０」を加算する。また、ＣＰＵ２０３は、目標検索時間非超過部分文字列の節を、主記憶装置２０９の所定領域に記憶しておく。
【００５９】
そして、ＣＰＵ２０３は、インデクス検索時間比較プログラム２１８により、この必要検索時間を加算した変数ｔｏｔａｌが、目標検索時間以上となったか判断する（Ｓ７０４）。ここで、必要検索時間を加算した変数ｔｏｔａｌが、目標検索時間以上となった場合（Ｓ７０４のＹｅｓ）、変数Ｐの値が１を超えるか否かを判断する（Ｓ７０５）。ここで、変数Ｐが１を超えるとき（Ｓ７０５のＹｅｓ）、つまり、隣接する節のうち、他にも目標検索時間非超過部分文字列の節があるとき、Ｓ７０６へ進む。例えば、ＣＰＵ２０３が、１グラム目の「い」の節に設定された必要検索時間「１．０」を、変数ｔｏｔａｌに加算したところ、この加算した値が、目標検索時間以上となった場合において、他にも目標検索時間非超過部分文字列の節（例えば、１グラム目の「あ」の節）があったとき、Ｓ７０６へ進む。一方、変数Ｐが１以下であるとき（Ｓ７０５のＮｏ）、図６のＳ６０６へ進む。
【００６０】
なお、必要検索時間を加算した変数ｔｏｔａｌがまだ目標検索時間未満であるとき（Ｓ７０４のＮｏ）、ＣＰＵ２０３は、変数Ｐの値をインクリメントして（Ｓ７０９）、図６のＳ６０５へ進む。
【００６１】
Ｓ７０６では、ＣＰＵ２０３は、インデクス階層化節作成プログラム２１７を起動する。そして、ＣＰＵ２０３は、目標検索時間非超過部分文字列の節を共通化し、この共通化した節によりトライを階層化する。このインデクス階層化節作成プログラム２１７に基づく、節の共通化およびトライの階層化の詳細は、図８を用いて後記するが、例えば、前記した例でいうと、図５に例示するトライ５０１の１グラム目の「い」の節と、１グラム目の「あ」の節とを共通化した節を作成する。そして、この共通化した節を節目としてトライを階層化する。
【００６２】
次に、ＣＰＵ２０３は、インデクス階層化節分割プログラム２２０を起動する（Ｓ７０７）。そして、ＣＰＵ２０３は、共通化した節および階層化したトライの分割を行う。この共通化した節および階層化したトライの分割の詳細は、図９を用いて後記する。
【００６３】
そして、ＣＰＵ２０３は、変数Ｐの値を「０」にし、変数ｔｏｔａｌの値を「０」にする（Ｓ７０８）。そして、図６のＳ６０６へ進む。
【００６４】
図６に戻ってＳ６０６以降の説明を続ける。ＣＰＵ２０３は、変数Ｎの値をインクリメントして（Ｓ６０６）、Ｓ６０２へ戻る。そして、ＣＰＵ２０３は、変数Ｎの値が、Ｓ６０１でカウントした数（隣接する節の数）になるまで、Ｓ６０３〜Ｓ６０６の処理を実行する。つまり、隣接するすべての節に、Ｓ６０３〜Ｓ６０６の処理を実行する。そして、ＣＰＵ２０３は、変数Ｎの値がＳ６０１でカウントした数（隣接する節の数）を超えたとき、Ｓ６０７へ進む。つまり、ＣＰＵ２０３は、隣接する節のうち、目標検索時間未満の節（目標検索時間非超過部分文字列の節）の処理をすべて終了すると、目標検索時間以上の節（目標検索時間超過部分文字列の節）の処理にとりかかる。
【００６５】
まず、ＣＰＵ２０３は、変数Ｌが、変数Ｍ（目標検索時間超過部分文字列の節の数＋１）以下か否かを判断する（Ｓ６０７）。ここで、変数Ｌが、変数Ｍ以下であるとき、ＣＰＵ２０３は、主記憶装置２０９に記憶された目標検索時間超過部分文字列の節の中から、まだ処理を行っていない節を１つ選択する（Ｓ６０８）。例えば、図５に例示するトライ５０１において１グラム目の「い」の節が、目標検索時間超過部分文字列の節であるとき、ＣＰＵ２０３は、この１グラム目の「い」の節を選択する。
【００６６】
そして、ＣＰＵ２０３は、変数Ｌの値をインクリメントし（Ｓ６０９）、Ｓ６０８で選択した節の次に続く節を探索する（Ｓ６１０）。例えば、ＣＰＵ２０３は、図５に例示するトライ５０１において、１グラム目の「う」の節の次に続く、２グラム目の節を探索する。ここで、次に続く節が存在するか否かを判断し（Ｓ６１１）、次に続く節が存在する場合、ＣＰＵ２０３は、この節を階層化する（Ｓ６１２）。つまり、ＣＰＵ２０３は、トライにおける次のグラムの節について、Ｓ６００以降の処理を実行する。例えば、図５に例示するトライ５０１において、１グラム目の「い」の節の次に続く、２グラム目の節があったとき、つまり、１グラム目の「い」の節の子の節があったとき、この２グラム目の節について、Ｓ６００以降の処理と同様の処理を行う。そして、１グラム目の「い」の節の子の節の処理を終了すると、１グラム目の別の節（１グラム目の「う」の節等）の処理に移る。
【００６７】
一方、次に続く節が存在しない場合、Ｓ６０８へ戻り、まだ処理を行っていない節の処理に移る。つまり、図５に例示するトライ５０１において、１グラム目の「い」の節の子の節がなかったとき、１グラム目の兄弟関係にある別の節（例えば、１グラム目の「う」の節等）の処理に移る。そして、ＣＰＵ２０３は、このような処理を、変数Ｌが、変数Ｍと同じ値になるまで実行する。つまり、隣接する節のうち、すべての目標検索時間超過部分文字列の節について、処理が完了するまで続ける。すなわち、前記した例でいうと、１グラム目の節のうち、目標検索時間超過部分文字列の節すべてについて、前記した処理を実行する。
【００６８】
＜インデクス階層化節作成プログラム＞
次に、インデクス階層化節作成プログラム２１７について、図２、図５および図９を参照しつつ、図８のＰＡＤを用いて詳細に説明する。図８は、図２のインデクス階層化ノード作成プログラムの処理手順を示した図である。図９は、図５のトライをもとに作成されたトライを例示した図である。
【００６９】
ＣＰＵ２０３は、主記憶装置２０９に記憶された共通化の対象である節（目標検索時間非超過部分文字列）を読み出し、この節を共通化したインデクス階層化節を作成する（Ｓ８００）。
【００７０】
例えば、図５に例示するトライ５０１における２グラム目の「あ」、「い」の以外のすべての節（つまり、２グラム目の「う」〜「ん」の節）が、共通化の対象の節として主記憶装置２０９に記憶されているとき、ＣＰＵ２０３は、この２グラム目の「う」〜「ん」の節を読み出し、これらの節をまとめたインデクス階層化節（符号９０２参照）を作成する。なお、このときのインデクス階層化節のラベルは、図９の符号９０２に示すように、例えば、「あ、い以外」等とする。
【００７１】
また、ＣＰＵ２０３は、この共通化の対象の節およびこの節に繋がる節を、ワークエリア２２５にコピーする。そして、ＣＰＵ２０３は、トライから、この共通化の対象の節およびこの節に繋がる節を削除し、この共通化の対象の節のあった場所に、インデクス階層化節を設置する。つまり、この共通化の対象の節およびこの節に繋がる節を、インデクス階層化節に置き換える。そして、ＣＰＵ２０３は、このようにして節を削除し、インデクス階層化節を設置したトライを第１のトライとして、上位部分文字列格納領域２２４に格納する（Ｓ８０１）。
【００７２】
例えば、ＣＰＵ２０３は、図５に例示するトライ５０１において、２グラム目の「う」〜「ん」の節およびその節に繋がる節をすべてワークエリア２２５にコピーする。そして、トライ５０１からこれらの節を削除し、２グラム目の「う」〜「ん」の節のかわりに、インデクス階層化節９０２を設置する。そして、ＣＰＵ２０３はこのようにして共通化の対象となる節を削除し、かわりにインデクス階層化節を設置したトライを、第１のトライ（図９の符号９００参照）として、図２の上位部分文字列格納領域２２４に格納する。
【００７３】
このようにすることで、ＣＰＵ２０３は、節の数が少なく、容量の少ない第１のトライを作成することができる。従って、文書登録検索システム２００は、主記憶装置２０９の記憶容量が少ない場合であっても、トライを実装することができる。
【００７４】
また、ＣＰＵ２０３は、必要検索時間が短い索引情報２０７に繋がる節については、階層化するが、必要検索時間が長い索引情報２０７に繋がる節については、階層化を行わない。これにより、必要検索時間が短い索引情報２０７を検索する際は、二次記憶装置２０５の第２のトライを経由するが、必要検索時間が長い索引情報２０７を検索する際は、主記憶装置２０９の第１のトライから直に索引情報２０７へ辿りつくことになるので、システム全体として索引情報２０７の検索効率を向上させることができる。
【００７５】
次に、ＣＰＵ２０３は、Ｓ８００で作成したインデクス階層化節から繋がる第２のトライを作成し、図２の下位部分文字列格納領域２０８に格納する（Ｓ８０２）。すなわち、ＣＰＵ２０３は、まずワークエリア２２５に格納されている共通化の対象の節およびこの節に繋がる節を読み出す。そして、この読み出した共通化の対象の節に、この節の親となる節（図９の第２のトライの根９０３参照）を設置する。そして、ＣＰＵ２０３は、この第２のトライの根９０３を頂点とするトライを、インデクス階層化節から繋がる第２のトライ９０４として、図２の下位部分文字列格納領域２０８に格納する。
【００７６】
なお、このようにして第２のトライの格納領域が決まると、ＣＰＵ２０３は、この第２のトライの接続元となるインデクス階層化節に、この第２のトライの格納領域を示すポインタ情報を設定する。
【００７７】
例えば、Ｓ８０２において、ＣＰＵ２０３は、まず、図５に例示するトライの２グラム目の「う」〜「ん」の節およびその節に繋がる節を、ワークエリア２２５から読み出す。そして、ＣＰＵ２０３は読み出したこれらの節の親となる節（図９の第２のトライの根９０３参照）を設置する。そして、ＣＰＵ２０３は、この第２のトライの根９０３を頂点とするトライを、インデクス階層化節９０２から繋がる第２のトライ９０４として、図２の二次記憶装置２０５の下位部分文字列格納領域２０８に格納する。次に、ＣＰＵ２０３は、第１のトライ９００の２グラム目のインデクス階層化節９０２（「あ、い以外」）に、この第２のトライ９０４の格納領域を示すポインタ情報９０５（「ｐｔｒ３３２」）を設定する。
【００７８】
このようにすることで、ＣＰＵ２０３が、索引情報９０６の検索を行う場合、第１のトライ９００のインデクス階層化節から、この節に続く第２のトライ（あるいは第２のトライの根）へジャンプして、索引情報９０６へ辿りつくことができる。
【００７９】
このような処理の後、ＣＰＵ２０３は、インデクス階層化節分割プログラム２２０を起動し、前記した第２のトライの容量に応じて、インデクス階層化節を分割する。
【００８０】
＜インデクス階層化節分割プログラム＞
次に、インデクス階層化節分割プログラム２２０について、図２を参照しつつ、図１０のＰＡＤを用いて詳細に説明する。図１０は、図２のインデクス階層化節分割プログラムの処理手順を示した図である。
【００８１】
まず、図２のＣＰＵ２０３は、インデクス階層化節から指す第２のトライ、つまりインデクス階層化節から続く第２のトライの容量を計測し、その容量が二次記憶装置２０５のディスクキャッシュに格納できる容量より大きいか否かを判断する（Ｓ１０００）。
【００８２】
ここで、この第２のトライの容量が二次記憶装置２０５のディスクキャッシュに格納できる容量以下の場合（Ｓ１０００のＮｏ）、ＣＰＵ２０３は、インデクス階層化節の分割は行わないが、この第２のトライの容量が二次記憶装置２０５のディスクキャッシュに格納できる容量より大きい場合（Ｓ１０００のＹｅｓ）、上位部分文字列格納領域２２４に格納されている、インデクス階層化節をワークエリア２２５上に読み出し、このインデクス階層化節を分割する（Ｓ１００１）。Ｓ１００１で、分割したインデクス階層化節は、図２の上位部分文字列格納領域２２４に戻す。なお、このときの分割は、その分割したインデクス階層化節の先にある第２のトライの容量が、ディスクキャッシュに格納できる容量以下となるように行う。このようにすることで、ＣＰＵ２０３が、二次記憶装置２０５に格納される第２のトライを検索する際、高速に検索できる。
【００８３】
なお、Ｓ１００１における、分割の個数は、分割後のインデクス階層化節の先にある第２のトライの容量が、ディスクキャッシュに格納できる容量以下となる範囲で、できるだけ少ない方がよい。つまり、Ｓ１００１の分割は、分割後の第２のトライの容量が、ディスクキャッシュの容量以下となり、かつ、分割してできる新たな第２のトライの数が最小になるのが好ましい。これは、分割により第２のトライの数が増えると、これに伴い第１のトライにおけるインデクス階層化節の数も増え、第１のトライの容量が大きくなってしまうからである。
【００８４】
そして、ＣＰＵ２０３は、下位部分文字列格納領域２０８に格納された第２のトライを、ワークエリア２２５上に読み出し、Ｓ１００１のインデクス階層化節の分割に従って、第２のトライを分割する（Ｓ１００２）。次に、ＣＰＵ２０３は、分割した第２のトライそれぞれに第２のトライの根を設置し、下位部分文字列格納領域２０８に格納する。
【００８５】
また、ＣＰＵ２０３は、分割した第２のトライの格納領域が決まると、Ｓ１００１において分割したインデクス階層化節に、この第２のトライの格納領域へのポインタ情報を設定する（Ｓ１００３）。
【００８６】
ここで、図１１、図１２および図１３を用いて、前記したインデクス階層化節の分割処理を具体的に説明する。図１１および図１２は、本実施の形態のインデクス階層化節の分割手順を概念的に説明した図である。図１３は、図１１および図１２を説明するために引用した図である。以下の説明において、二次記憶装置２０５のディスクキャッシュに格納できる容量は、６ｋであるものとして説明する。
【００８７】
例えば、図１１に例示する第１のトライ１１００において、インデクス階層化節１１０１（「ち、つ以外」）の先にある第２のトライ１１０２の容量は７ｋである。そして、この第２のトライ１１０２の容量は、二次記憶装置２０５のディスクキャッシュに格納できる容量を超えている。
【００８８】
従って、ＣＰＵ２０３は、この第２のトライ１１０２の容量が、６ｋ以下となるように第２のトライ１１０２を分割し、それに伴いインデクス階層化節１１０１も分割する。
【００８９】
例えば、ＣＰＵ２０３は、図１１における３グラム目のインデクス階層化節１１０１（「ち、つ以外」）を、図１２に例示するように、インデクス階層化節１２００（「あ〜む」）およびインデクス階層化節１２０１（「め〜ん」）の２つのインデクス階層化節に分割する。このとき、インデクス階層化節１２００（「あ〜む」）の先に続く第２のトライの容量は３．８ｋ、インデクス階層化節１２０１（「め〜ん」）の先に続く第２のトライの容量は３．２ｋというように、それぞれの容量が、ディスクキャッシュに格納できる容量以下となるように分割する。そして、ＣＰＵ２０３は、分割後の第２のトライそれぞれに、第２のトライの根１２０２,１２０３を設置する。また、ＣＰＵ２０３は、インデクス階層化節１２００,１２０１それぞれに、この分割後の第２のトライの格納領域を示すポインタ情報１２０４,１２０５を設定する。
【００９０】
つまり、図１３のグラフに示すように、図１１のインデクス階層化節１１０１の分割前は、「あ−い−あ」〜「あ−い−た」および「あ−い−て」〜「あ−い−ん」のインデクス階層化節の第２のトライの容量は、ディスクキャッシュに格納できる容量（６ｋ）を超えていたところ、図１２の「あ−い−あ」〜「あ−い−む」のインデクス階層化節１２００および「あ−い−め」〜「あ−い−ん」のインデクス階層化節１２０１に分割することで、それぞれの第２のトライの容量は、ディスクキャッシュに格納できる容量（６ｋ）以下とする。
【００９１】
ＣＰＵ２０３が、このようなインデクス階層化節の分割を行うことで、第２のトライの容量を、二次記憶装置２０５のディスクキャッシュに格納できる容量以下とすることができる。これにより、ＣＰＵ２０３は、ディスクキャッシュを用いて索引情報２０７の検索を高速に行うことができる。
【００９２】
＜検索処理＞
次に、前記した処理により作成されたインデクスにより、ＣＰＵ２０３が索引情報の検索を行う手順について説明する。ユーザが入力した検索タームに関する索引情報２０７の検索は、ＣＰＵ２０３が、システム制御プログラム２１２から検索制御プログラム２１１を実行することで行われる。検索制御プログラム２１１は、インデクス検索プログラム２２１を実行することで行われる。
【００９３】
＜インデクス検索プログラム＞
インデクス検索プログラム２２１について、図１４のＰＡＤを用いて詳細に説明する。図１４は、図２のインデクス検索プログラムの処理手順を示した図である。ここでは、ＣＰＵ２０３が、図９に例示する第１のトライ９００および第２のトライ９０４の節を辿って、索引情報２０７を検索する場合について説明する。
【００９４】
ＣＰＵ２０３は、まず入力された検索タームを、連続するグラム数分の文字列に分割する（Ｓ１４００）。ここで、分割する文字列の文字数は、インデクスのグラム数（所定長）以下の文字数とする。例えば、検索タームが「あいぬじん」である場合において、図９に例示したインデクスは３グラムなので、ＣＰＵ２０３は、「あいぬ」、「じん＿」といった３文字以下の文字列に分割する。
【００９５】
次に、ＣＰＵ２０３は、検索タームを分割した文字列の個数分、以下のＳ１４０２〜Ｓ１４０４の処理を繰り返す（Ｓ１４０１）。例えば、検索タームである「あいぬじん」を、「あいぬ」、「じん＿」という２個の文字列に分割した場合、Ｓ１４０２〜Ｓ１４０４の処理を２回実行する。
【００９６】
次に、ＣＰＵ２０３は、上位部分文字列検索プログラム２２２を起動する。そして、ＣＰＵ２０３は、分割した文字列について、前記した第１のトライを辿り、末端の節に設定された第２のトライのポインタ情報を読み出す（Ｓ１４０２）。このようにして、ＣＰＵ２０３は、分割した文字列のうち、第１のトライに含まれる文字列（上位部分文字列）の検索を行い、この上位部分文字列に続く下位部分文字列（第２のトライに含まれる文字列）のポインタ情報を読み出す。
【００９７】
例えば、ＣＰＵ２０３が、図９に例示する第１のトライ９００において、１グラム目の「あ」の節、２グラム目の「い」の節、３グラム目の「ち、つ以外」の節というように、節を辿る。そして、末端の節である３グラム目の「ち、つ以外」の節（インデクス階層化節）に設定された第２のトライのポインタ情報（「ｐｔｒ３３１」）を読み出す。
【００９８】
次に、ＣＰＵ２０３は、下位部分文字列検索プログラム２２３を起動する。続いて、Ｓ１４０２で読み出した第２のトライのポインタ情報をもとに、第２のトライにアクセスする。そして、ＣＰＵ２０３は、この第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報（索引情報のポインタ情報）が示す索引情報２０７をワークエリア２２５へ読み込む（Ｓ１４０３）。
【００９９】
例えば、ＣＰＵ２０３は、図９に例示する第１のトライ９００の３グラム目の「ち、つ以外」の節に設定された第２のトライのポインタ情報「ｐｔｒ３３１」をもとに、この「ち、つ以外」の節の次に続く、第２のトライ９０４にアクセスする。そして、この第２のトライの「ぬ」の節に設定されたポインタ情報「ｐｔｒ１９９」が示す索引情報２０７をワークエリア２２５へ読み込む。つまり、ＣＰＵ２０３は、「あいぬ」を検索項目とする索引情報２０７をワークエリア２２５へ読み込む。
【０１００】
次に、ＣＰＵ２０３は、読み込んだ索引情報２０７から当該文字列を含む文書番号２２７および文字位置（位置情報）２２８を抽出し、ワークエリア２２５に格納する（Ｓ１４０４）。
【０１０１】
例えば、ＣＰＵ２０３は、図９の符号９０７に示す「あいぬ」の索引情報に格納されている、「あいぬ」を含む文書番号「００１」と、文字位置「２１」を抽出し、ワークエリア２２５に格納する。つまり、「あいぬ」という文字列は、文書番号「００１」の文書の文字位置「２１」の位置にあるという情報を抽出する。
【０１０２】
ＣＰＵ２０３は、以上の処理を、検索タームを分割した文字列の個数分実行する。つまり、ＣＰＵ２０３は「あいぬ」の処理を終了すると、「じん＿」についても、同様の処理を実行し、この「じん＿」を含む文書番号と文字位置（位置情報）を抽出し、ワークエリア２２５に格納する。
【０１０３】
そして、ＣＰＵ２０３は、すべての文字列の位置情報の抽出を完了すると、ワークエリア２２５に格納された文字列ごとの位置情報のうち、同じ位置関係にある位置情報を抽出する（Ｓ１４０５）。つまり、ＣＰＵ２０３は、文字列同士が検索タームの並びと同じ位置関係にある位置情報を検索し、この位置情報を出力する。
【０１０４】
例えば、ＣＰＵ２０３は、「あいぬ」の位置情報として、文書番号「００１」および文字位置「２１」という情報を抽出する。また、図示していないが、「じん＿」の位置情報として、文書番号「００１」および文字位置「２４」という情報を抽出したとする。この場合、両者とも、文書番号が同じであり、かつ、文字位置についても「あいぬ」（先頭の文字「あ」は２１番目）のすぐ次に「じん＿」（先頭の文字「じ」は２４番目）が続く位置関係にあり、文字列同士が検索タームの並びと同じ位置関係にある。従って、「あいぬじん」は、文書番号「００１」の文書において、文字位置「２１」から始まる位置にある文字列であるという情報を検索することができる。
【０１０５】
このようにして、ＣＰＵ２０３は、文書における検索タームの位置情報を得ることができる。
【０１０６】
＜第２の実施の形態＞
第２の実施の形態の文書登録検索システムは、索引情報２０７の必要検索時間に代えて、索引情報２０７の容量（索引情報の容量の合計値）をもとに当該節を共通化するか否かを判断することを特徴とする。図１５は、本発明の第２の実施の形態における文書登録検索システムの構成例を示した図である。
【０１０７】
図１５に示すように、第２の実施の形態の文書登録検索システム２００Ａは、図２のトライ初期化プログラム２１４に代えて、トライ初期化プログラム２１４Ａを備え、また、図２のインデクス階層化プログラム２１６に代えて、インデクス階層化プログラム２１６Ａを備えることを特徴とする。このインデクス階層化プログラム２１６Ａは、図１５に示すように、図２のインデクス検索時間比較プログラム２１８に代えて、索引情報容量比較プログラム２１８Ａを備えることを特徴とする。前記した第１の実施の形態と同様の構成要素は同じ符号を付して、説明を省略する。なお、ＣＰＵ２０３が索引情報容量比較プログラム２１８Ａを実行することで、請求項における索引情報容量比較部の機能を実現する。
【０１０８】
トライ初期化プログラム２１４Ａは、トライの初期化を行う際、トライの各節に、この節を辿った先にある索引情報２０７の容量（索引情報の容量の合計値）の情報を付加するプログラムである。
【０１０９】
また、このインデクス階層化プログラム２１６Ａは、索引情報容量比較プログラムにより、各節の索引情報の容量の値（索引情報の容量の合計値）の比較を行い、この節をインデクス階層化節とするか否かを判断するプログラムである。
【０１１０】
このインデクス階層化プログラム２１６Ａの処理手順を、図１６および図１７を用いて説明する。図１６および図１７は、図１５のインデクス階層化プログラムの処理手順を示した図である。図１６のＳ１６００〜Ｓ１６０３までの処理は、図６のＳ６００〜Ｓ６０３までの処理と同様なので説明を省略し、Ｓ１６０４から説明する。なお、本フローにおける変数ｔｏｔａｌは、節に設定されている索引情報の容量の合計値を計算するために用いる変数である。
【０１１１】
ＣＰＵ２０３は、Ｓ１６０３で節を選択した後、この選択した節に設定されている索引情報の容量の情報を読み出す（Ｓ１６０４）。例えば、図５に例示するトライ５０１の１グラム目の「あ」の節に設定されている索引情報２０７の容量の情報を読み出す。そして、ＣＰＵ２０３は、この読み出した索引情報２０７の容量の情報に基づき、節の共通化処理を実行する（Ｓ１６０５）。なお、Ｓ１６０６は、図６のＳ６０６と同様なので説明を省略する。このＳ１６０５における節の共通化処理について、図１７を用いて説明する。
【０１１２】
まず、ＣＰＵ２０３は、Ｓ１６０３で選択した節における索引情報２０７の容量の値が、所定の閾値（索引情報の容量の閾値）以上か否かを判断する（図１７のＳ１７００）。このときの判断は、前記した索引情報容量比較プログラム２１８Ａにより行われる。
【０１１３】
ここで、Ｓ１６０３で選択した節における索引情報の容量が、所定の閾値（索引情報の容量の閾値）以上であるとき（Ｓ１７００のＹｅｓ）、Ｓ１７０１およびＳ１７０２の処理を実行する。Ｓ１７０１およびＳ１７０２の処理は、図７のＳ７０１およびＳ７０２の処理と同様なので説明を省略する。
【０１１４】
一方、Ｓ１７００において、Ｓ１６０３で選択した節における索引情報の容量が、前記した閾値未満のとき（Ｓ１７００のＮｏ）、ＣＰＵ２０３は、変数ｔｏｔａｌに、Ｓ１６０３で選択した節における索引情報の容量の値を加算する（Ｓ１７０３）。
【０１１５】
そして、ＣＰＵ２０３は、索引情報容量比較プログラム２１８Ａにより、この索引情報の容量を加算した変数ｔｏｔａｌが、前記した所定の閾値以上か否かを判断する（Ｓ１７０４）。ここで、この索引情報の容量を加算した変数ｔｏｔａｌが、前記した所定の閾値（索引情報の容量の閾値）以上であるとき（Ｓ１７０４のＹｅｓ）、変数Ｐの値が１以上であるか否かを判断する（Ｓ１７０５）。ここで、変数Ｐが１を超えるとき（Ｓ１７０５のＹｅｓ）、つまり、隣接する節のうち、他にも容量非超過部分文字列の節があるとき、Ｓ１７０６へ進む。一方、変数Ｐが１以下であるとき（Ｓ１７０５のＮｏ）、図１６のＳ１６０６へ進む。
【０１１６】
なお、索引情報の容量を加算した変数ｔｏｔａｌが前記した所定の閾値（索引情報の容量の閾値）未満であるとき（Ｓ１７０４のＮｏ）、ＣＰＵ２０３は、変数Ｐの値をインクリメントして（Ｓ１７０９）、図１６のＳ１６０６へ進む。
【０１１７】
Ｓ１７０６において、ＣＰＵ２０３は、インデクス階層化節作成プログラム２１７を起動する。そして、ＣＰＵ２０３は、容量非超過部分文字列の節を共通化し、この共通化した節によりトライを階層化する（Ｓ１７０６）。この後の、Ｓ１７０７およびＳ１７０８の処理は、図７のＳ７０７およびＳ７０８の処理と同様なので、説明を省略する。
【０１１８】
また、図１６のＳ１６０７の処理は、図６のＳ６０７と同様なので、説明を省略し、Ｓ１６０８から説明する。Ｓ１６０７において、変数Ｌが、変数Ｍ以下であるとき、ＣＰＵ２０３は、主記憶装置２０９に記憶された容量超過部分文字列の節の中から、まだ処理を行っていない節を１つ選択する（Ｓ１６０８）。そして、このすべての容量超過部分文字列について処理を実行するまで、Ｓ１６０９〜Ｓ１６１２の処理を実行する。このＳ１６０９〜Ｓ１６１２の処理は、図６のＳ６０９〜Ｓ６１２の処理と同様であるので、説明を省略する。
【０１１９】
このように、ＣＰＵ２０３は、索引情報２０７の容量（索引情報の容量の合計値）を用いることでも検索効率のよいトライを作成することができる。
【０１２０】
＜その他の実施の形態＞
なお、前記した実施の形態において、トライの節はひらがなを用いる場合を例に説明したが、カタカナや漢字を用いるようにしてももちろんよい。また、テキスト２０６が日本語以外の言語を含むものであれば、その言語の文字をトライの節に用いるようにすればよい。図１８は、本実施の形態のインデクスを例示した図である。図１９は、図１８のインデクスを階層化したものを例示した図である。
【０１２１】
例えば、テキスト２０６が、英語の文書であるとき、文書登録検索システム２００,２００Ａが、トライ初期化プログラム２１４,２１４Ａにより作成したトライは、図１８に例示するように、アルファベットの文字１つ１つをトライの節としたものになる。例えば、図１８に例示するように「ａ」の節、「ｉ」の節、「ｒ」の節を辿り、「ｒ」の節に設定されたポインタ情報１８０２が示す先に「ａｉｒ」という文字列の索引情報１８０１が置かれる。また、文書登録検索システム２００,２００Ａが、図１８に例示するようなアルファベットのトライ１８００を階層化して、図１９に例示するような第１のトライ１９００および第２のトライ１９０１を作成する場合も、トライの節はアルファベットの文字１つ１つを単位としたものになる。
【０１２２】
さらに、前記した実施の形態において、索引情報２０７は、テキスト２０６に含まれる文字列の索引情報としたが、画像データや映像データの索引情報であってもよい。
【０１２３】
また、文書登録検索システム２００,２００Ａにおいて、インデクス階層化節分割プログラム２２０を含まない構成としてもよい。すなわち、文書登録検索システム２００,２００Ａにおいて、インデクス階層化節を作成した後、このインデクス階層化節の分割を行わないようにしてもよい。
【０１２４】
さらに、文書登録検索システム２００,２００Ａは、インデクス作成登録プログラム２１３と、インデクス検索プログラム２２１との両方のプログラムを含む構成としたが、これらを別個の構成としてもよい。すなわち、インデクス作成登録プログラム２１３によりインデクス作成を行うコンピュータとは別に、インデクス検索プログラム２２１によりインデクス検索を行うコンピュータを設けるようにしてもよい。
【０１２５】
また、文書登録検索システム２００,２００Ａの二次記憶装置２０５は、この文書登録検索システム２００,２００Ａの外部に設置するようにしてもよい。
【０１２６】
また、前記した実施の形態において、１つの文字コードを１グラムとしてもよい。例えば、２バイト文字コードであれば２バイト（１６ビット）を１グラムとし、１バイト文字コードであれば１バイト（８ビット）を１グラムとしてもよい。また、グラムは、文字コードに制限されることなく、任意のビット長を１グラムとしてもよい。このようにすることで、例えば、４ビットまたは２ビットの記号コードを１グラムとしてトライを生成し、記号列の登録および検索を実現することができる。
【０１２７】
また、前記した実施の形態において、文書登録検索システム２００,２００Ａは共通化節の下に繋がるトライをトライ形式で二次記憶装置２０５の下位部分文字列格納領域２０８に格納することとしたが、これに限定されない。例えば、二次記憶装置２０５において、ＣＰＵ２０３がアクセスしやすいよう、Ｂ木（B tree）形式で格納するようにしてもよい。さらに、二次記憶装置２０５において、ディスク容量を削減するために、トライの圧縮を行い、格納するようにしてもよい。
【０１２８】
本実施の形態に係る各プログラムはコンピュータによる読み取り可能な記憶媒体（ＣＤ−ＲＯＭ等）に記憶して提供することが可能である。また、そのプログラムを、インターネット等のネットワークを通して提供することも可能である。
【図面の簡単な説明】
【０１２９】
【図１】比較例のインデクスを例示した図である。
【図２】本発明の第１の実施の形態における文書登録検索システムの構成例を示した図である。
【図３】図２のインデクス作成登録プログラムの処理手順を示した図である。
【図４】図２のトライ初期化プログラムの処理手順を示した図である。
【図５】図２のＣＰＵが、トライ初期化プログラムにより作成するトライを含むインデクスを例示した図である。
【図６】図２のインデクス階層化プログラムの処理手順を示した図である。
【図７】図２のインデクス階層化プログラムの処理手順を示した図である。
【図８】図２のインデクス階層化ノード作成プログラムの処理手順を示した図である。
【図９】図５のトライをもとに作成されたトライを例示した図である。
【図１０】図２のインデクス階層化節分割プログラムの処理手順を示した図である。
【図１１】本実施の形態のインデクス階層化節の分割手順を概念的に説明した図である。
【図１２】本実施の形態のインデクス階層化節の分割手順を概念的に説明した図である。
【図１３】図１１および図１２を説明するために引用した図である。
【図１４】図２のインデクス検索プログラムの処理手順を示した図である。
【図１５】本発明の第２の実施の形態における文書登録検索システムの構成例を示した図である。
【図１６】図１５のインデクス階層化プログラムの処理手順を示した図である。
【図１７】図１５のインデクス階層化プログラムの処理手順を示した図である。
【図１８】本実施の形態のインデクスを例示した図である。
【図１９】図１８のインデクスを階層化したものを例示した図である。
【符号の説明】
【０１３０】
１００,５０１ トライ
１０１,２０７,５０２,９０６,１８０１ 索引情報
１０２,５０３,９０５,１２０４,１２０５,１８０２ ポインタ情報
１０３,２２７ 文書番号
１０４,２２８ 文字位置
１０５,５００ インデクス
２００,２００Ａ 文書登録検索システム
２０１ ディスプレイ
２０２ キーボード
２０３ ＣＰＵ
２０４ バス
２０５ 二次記憶装置
２０６ テキスト
２０８ 下位部分文字列格納領域
２０９ 主記憶装置
２１０ 文書登録制御プログラム
２１１ 検索制御プログラム
２１２ システム制御プログラム
２１３ インデクス作成登録プログラム
２１４,２１４Ａ トライ初期化プログラム
２１５ 索引情報作成プログラム
２１６,２１６Ａ インデクス階層化プログラム
２１７ インデクス階層化節作成プログラム（インデクス階層化節生成部）
２１８ インデクス検索時間比較プログラム
２１８Ａ 索引情報容量比較プログラム
２１９ 隣接部分文字列検索プログラム
２２０ インデクス階層化節分割プログラム
２２１ インデクス検索プログラム
２２２ 上位部分文字列検索プログラム
２２３ 下位部分文字列検索プログラム
２２４ 上位部分文字列格納領域
２２５ ワークエリア
２２６ トライ格納領域
９００,１１００,１９００ 第１のトライ
９０２,１１０１,１２００,１２０１ インデクス階層化節
９０３,１２０２,１２０３ 第２のトライの根
９０４,１１０２,１９０１ 第２のトライ
【技術分野】
【０００１】
本発明は、文書検索システムに使用する検索インデクス作成技術に関する。
【背景技術】
【０００２】
従来、コンピュータが、大規模な文書データベースから、指定された検索文字列が含まれる文書を高速に検索する技術として、インデクスを用いるものが知られている(以下、方式１と呼ぶ)。このインデクスは、（１）検索される文書に含まれるキーワードを示した索引項目と、（２）その索引項目を含む文書を識別する文書識別情報や、当該文書における索引項目の文書位置等を示した索引情報と、が記録されたものである。また、方式１のようなインデクスを用いた文書検索方法において、文書に対する索引項目はトライ（trie）のような木構造により管理される。
【０００３】
このトライとは、検索対象となる文字列すなわちキーワードの集合（以下、キー集合と呼ぶ）における各キーワード（以下、キーと呼ぶ）に共通な部分文字列を、共通の節として括り出して作られる木構造である。このトライは、インデクスの検索の際に用いられ、コンピュータは、検索ターム中の文字列をキーに分解し、このキーで節を辿りトライ上を探索する。そして、コンピュータは、トライの末端の節に到達すると、その末端の節に設定されたポインタ情報を読み取り、検索タームに対応する索引情報を読み出すことができる。
【０００４】
このトライの概要を、図１を用いて説明する。図１は、比較例のインデクスを例示した図である。前記したとおり、インデクス１０５は、索引項目を木構造で構成したトライ１００と、その索引項目に対応する索引情報１０１とを含んで構成される。なお、このトライ１００の末端の文字列の節には、索引情報１０１を読み出すためのポインタ情報１０２が設定される。
【０００５】
図１に例示したトライ１００は３グラム（キーの文字数が３個）のトライであり、一例として、「あ」から始まる文字列のトライを示している。例えば、このようなトライにおいて、１グラム目の「あ」の節に続く２グラム目の節として「あ」、「い」、「う」、…、「ん」の節が設定され、そのさらに次に３グラム目の節として、「あ」、…、「ん」の節が設定される。そして、末端の節（つまり、図１の３グラム目の節）には、索引情報１０１を読み出すためのポインタ情報１０２が設定されている。
【０００６】
ここで、コンピュータが、このトライ１００を辿って「あいち」という文字列を含む文書の文書番号およびその文書における文字位置を検索する場合には、以下のようになる。
【０００７】
まず、コンピュータは、１グラム目の「あ」の節、この節に繋がる２グラム目の「い」の節、この節に繋がる３グラム目の「ち」の節、というように節を辿る。そして、コンピュータは、末端の節である「ち」の節に設定されたポインタ情報１０２（「ｐｔｒ６１」）により、記憶装置の所定領域から「あいち」に関する索引情報１０１を読み出す。つまり、「あいち」を含む文書の文書番号（文書識別情報）１０３である「００１」と、その文書における「あいち」の文字位置１０４である「２１」とを読み出す。
【特許文献１】特開平１１−１４３９０１号公報
【特許文献２】特開昭５９−１４８９２２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ここで、コンピュータが、前記したトライを用いてインデクスを管理する場合において、文書の索引情報の検索を高速にするには、個々の索引情報の容量を小さくしてトライにおけるグラム数（キーに共通な部分文字列（記号列）の文字数）を大きくすることが考えられる。しかし、このようにグラム数の大きいトライは、メモリに格納しきれないことがある。このような問題は、特に、携帯電話機やＤＶＤ（Digital Versatile Disk）プレイヤ等、メモリ容量の少ない機器に文書検索システムを実装する場合に大きな問題となる。
【０００９】
そこで、本発明は、前記した問題を解決し、メモリ容量が少ない機器であっても、トライによる高速な文書検索を実現する手段を提供することを目的とする。
【課題を解決するための手段】
【００１０】
前記した課題を解決するため、本発明は、主記憶装置および二次記憶装置を備えるコンピュータ（記号列検索装置）が、まず、トライを作成（生成）する。次に、このトライにより検索される索引情報の必要検索時間を参照して、この生成したトライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算する。そして、この計算した節ごとの必要検索時間が、所定の閾値以下か否かを判断する。ここで、必要検索時間が、所定の閾値以下である節のうち、同じ節を親とする節同士を共通化したインデクス階層化節を生成する。つまり、複数の節を共通化し、まとめた節を生成する。そして、この共通化の対象である節およびこの節から先に繋がる節を、インデクス階層化節に置き換えた第１のトライを生成する。生成した第１のトライは、主記憶装置の所定領域に格納する。なお、共通化の対象である節およびこの節から先に繋がる節については、第２のトライとして二次記憶装置の所定領域に移動する。そして、第１のトライにおけるインデクス階層化節には、この第２のトライの格納領域を示すポインタ情報を設定する。これにより、コンピュータが検索タームに含まれる記号列（文字列を含む）により索引情報の検索を行うとき、主記憶装置に格納される第１のトライを辿った後、二次記憶装置に格納される第２のトライにアクセスして、この記号列（文字列を含む）に対応する索引情報に辿りつくことができる。なお、記号列とは、１バイト文字や２バイト文字の文字コードを、２ビットや４ビットに分割した記号コードの記号を繋げたものである。
【００１１】
このように、本発明の記号列検索装置は、トライを第１のトライと第２のトライとに階層化し、それぞれを主記憶装置と二次記憶装置とに格納する。従って、主記憶装置（メモリ）の容量が少ない機器（コンピュータ）であっても、大きな容量のトライを実装することができる。つまり、記号列検索装置は、トライによる高速な文書検索を行うことができる。また、記号列検索装置は、第１のトライを作成するとき、この第１のトライにおける節を共通化するので、主記憶装置に格納される第１のトライの節の数を低減することができる。つまり、第１のトライの容量を低減するので、主記憶装置（メモリ）の容量が少ないコンピュータであっても、より一層トライを搭載しやすくなる。さらに、この第１のトライにおいて、共通化するのは、その節から先に繋がる索引情報の必要検索時間の合計が所定の閾値以下の節を対象とした。つまり、必要検索時間の合計が所定の閾値を超える節については、第２のトライを経由せず、すぐに索引情報に到達するようにした。これにより、トライを用いた索引情報の検索効率を向上させることができる。
【発明の効果】
【００１２】
本発明によれば、メモリ容量が少ない機器であっても、トライによる高速な文書検索を行うことができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照しながら、本発明を実施するための最良の形態（以下、実施の形態という）を、説明する。
【００１４】
＜第１の実施の形態＞
図２は、本発明の実施の形態である文書登録検索システムの構成例を示した図である。
【００１５】
本発明の実施の形態である文書登録検索システム（トライ生成装置および記号列検索装置）２００は、図２に示すように、ディスプレイ２０１、キーボード２０２、ＣＰＵ（中央演算装置、Central Processing Unit)２０３、主記憶装置２０９、二次記憶装置２０５およびこれらを接続するバス２０４を含んで構成される。
【００１６】
ディスプレイ（出力装置）２０１は、ＣＰＵ２０３による検索結果を表示する。キーボード２０２（入力装置）は、テキスト２０６の登録および検索のコマンドや、検索タームを入力する。ＣＰＵ２０３は、後記する各プログラムを実行することで、インデクスの登録処理および検索キーワードの検索処理を実行する。主記憶装置２０９は、インデクス登録用および検索用プログラム、ならびに入出力されるデータ等を一時的に格納する。二次記憶装置（二次記憶装置）２０５は、各データおよび各プログラムを格納する。
【００１７】
また、この二次記憶装置２０５には、ディスクキャッシュ（図示せず）を備える。このディスクキャッシュは、ＨＤＤ等、アクセスが低速な記憶装置に記録されているデータの一部を写し、データの読み出しを高速化する手段である。このディスクキャッシュは、二次記憶装置２０５が備えるＲＡＭ（Random Access Memory）等の半導体メモリにより構成される。また、主記憶装置２０９も、ＲＡＭ等により構成され、二次記憶装置２０５は、ＨＤＤ（Hard Disk Drive）やフラッシュメモリ等により構成される。
【００１８】
二次記憶装置２０５には、文書登録検索システム２００全体の制御を司るシステム制御プログラム２１２に加え、登録用のプログラムとして文書登録制御プログラム２１０およびインデクス作成登録プログラム２１３、検索用のプログラムとして検索制御プログラム２１１およびインデクス検索プログラム２２１が格納される。これらのプログラムは、ＣＰＵ２０３により、主記憶装置２０９上に読み出され、実行される。図２は、これらのプログラムが、主記憶装置２０９上に読み出された状態を示している。また、この主記憶装置２０９には、各データを一時的に格納するワークエリア２２５、上位部分文字列格納領域２２４およびトライ格納領域２２６が確保されている。
【００１９】
ここで各プログラムの概略を説明する。
【００２０】
システム制御プログラム２１２は、ディスプレイ２０１およびキーボード２０２を用いたユーザ入出力の制御を行い、その他の各プログラムの実行を制御するプログラムである。
【００２１】
文書登録制御プログラム２１０は、インデクス作成登録プログラム２１３を制御するプログラムである。
【００２２】
インデクス作成登録プログラム２１３は、トライ初期化プログラム２１４と、索引情報作成プログラム２１５と、インデクス階層化プログラム２１６とを含んで構成される。トライ初期化プログラム２１４はトライの初期化を行うプログラムである。なお、ＣＰＵ２０３がこのトライ初期化プログラム２１４を実行することで、請求項におけるトライ初期化部の機能を実現する。索引情報作成プログラム２１５は、索引情報２０７（後記）を作成するプログラムである。インデクス階層化プログラム２１６は、インデクスの階層化を行う、つまり、トライを２つの階層に分けるプログラムである。
【００２３】
このインデクス階層化プログラム２１６は、インデクス階層化節作成プログラム２１７と、インデクス検索時間比較プログラム２１８と、隣接部分文字列検索プログラム２１９と、インデクス階層化節分割プログラム２２０とを含んで構成される。
【００２４】
インデクス階層化節作成プログラム２１７は、インデクス階層化節（詳細は後記）を作成するプログラムである。なお、ＣＰＵ２０３がインデクス階層化節作成プログラム２１７を実行することで請求項におけるインデクス階層化節生成部の機能を実現する。
【００２５】
インデクス検索時間比較プログラム２１８は、索引情報２０７の必要検索時間と目標検索時間（詳細は後記）とを比較するプログラムである。なお、ＣＰＵ２０３がインデクス検索時間比較プログラム２１８を実行することで請求項におけるインデクス検索時間比較部の機能を実現する。
【００２６】
隣接部分文字列検索プログラム２１９は、トライにおいて同じ節を親とする節（つまり兄弟関係にある節）を探索するプログラムである。なお、ＣＰＵ２０３が隣接部分文字列検索プログラム２１９を実行することで、請求項における隣接部分記号列検索部の機能を実現する。
【００２７】
インデクス階層化節分割プログラム２２０は、階層化されたトライのうち、下位のトライ（第２のトライ）の容量が所定の閾値を超えたときインデクス階層化節を分割するプログラムである。
【００２８】
さらに、インデクス検索プログラム２２１は、上位部分文字列検索プログラム２２２と、下位部分文字列検索プログラム２２３とを含んで構成される。上位部分文字列検索プログラム２２２は、階層化されたトライのうち上位のトライ（第１のトライ）を検索するプログラムである。下位部分文字列検索プログラム２２３は、階層化されたトライのうち、下位のトライ（第２のトライ）を検索するプログラムである。なお、ＣＰＵ２０３がインデクス検索プログラム２２１を実行することで、請求項におけるインデクス検索部の機能を実現する。
【００２９】
なお、二次記憶装置２０５は、文書データであるテキスト２０６と、そのテキスト２０６の索引情報２０７とを記憶する。さらに、この二次記憶装置２０５には、前記した第２のトライを格納する下位部分文字列格納領域２０８が確保されている。
【００３０】
また、前記したプログラムの詳細は、本実施の形態における登録処理および検索処理の説明の項において詳細に述べる。
【００３１】
＜登録処理＞
ユーザが入力した文書データ（テキスト２０６）の登録処理は、ＣＰＵ２０３が、システム制御プログラム２１２経由で、文書登録制御プログラム２１０を実行することで行われる。
【００３２】
＜インデクス作成登録プログラム＞
次に、インデクス作成登録プログラム２１３について、図２を参照しつつ、図３のＰＡＤ（Program Analysis Diagram）を用いて説明する。図３は、図２のインデクス作成登録プログラムの処理手順を示した図である。
【００３３】
まず、図２のＣＰＵ２０３は、トライ初期化プログラム２１４を起動し、トライ格納領域２２６の初期設定を行う（Ｓ３００）。このときのトライ初期化プログラム２１４による初期設定の詳細については、図４を用いて後記する。
【００３４】
次に、ＣＰＵ２０３は、索引情報作成プログラム２１５を起動し、索引情報２０７を作成し、二次記憶装置２０５へ格納する（Ｓ３０１）。つまり、ＣＰＵ２０３は、二次記憶装置２０５に格納されているテキスト２０６から、所定の部分文字列と、テキスト２０６における文書番号（文書識別情報）２２７と、その文字位置（出現位置情報）２２８とを抽出し、索引情報２０７を作成し、二次記憶装置２０５へ格納する。
【００３５】
例えば、ＣＰＵ２０３は、索引情報作成プログラム２１５により、文書番号「００１」の「・・・あいち・・・」というテキスト２０６から、この「あいち」という文字列が文書番号「００１」の文書に含まれ、その文書における「あいち」という文字列の先頭の文字「あ」の文字位置は「２１」であることを示す索引情報２０７を作成する。そして、この作成した索引情報２０７を二次記憶装置２０５へ格納する。なお、ＣＰＵ２０３は、この索引情報２０７それぞれに対し、この索引情報２０７を検索するのに要する検索時間（必要検索時間）を計測し、索引情報２０７に付加する。
【００３６】
次に、ＣＰＵ２０３は、インデクス階層化プログラム２１６を起動する。そして、ＣＰＵ２０３は、索引情報作成プログラム２１５によって作成された索引情報２０７をもとにインデクス階層化処理を行う（Ｓ３０２）。このときのインデクス階層化処理の詳細は、図６を用いて後記する。
【００３７】
＜トライ初期化プログラム＞
次に、トライ初期化プログラム２１４について、図２を参照しつつ、図４のＰＡＤを用いて詳細に説明する。図４は、図２のトライ初期化プログラムの処理手順を示した図である。
【００３８】
まず、図２のＣＰＵ２０３は、既にトライが作成され、主記憶装置２０９にトライ格納領域２２６が設定されているか否かを判定する（Ｓ４００）。ここで、未だトライが作成されておらず、トライ格納領域２２６が設定されていないとき（Ｓ４００のＮｏ）、ＣＰＵ２０３は、テキスト２０６で用いられるすべての文字をグラム数分（例えば、３グラム分）の文字列に分割する。例えば、テキスト２０６において「あいちはく」という文字列が含まれていたとき、ＣＰＵ２０３は、この文字列を３グラム分の文字列「あいち」と、「はく＿」とに分割する。なお、「＿」は空白を表す。そして、ＣＰＵ２０３は、この分割した文字列の１文字をキー（節）として、トライを作成し、トライ格納領域２２６を設定する（Ｓ４０１）。例えば、ＣＰＵ２０３は、１グラム目の節に「あ」、２グラム目の節に「い」、３グラム目の節に「ち」を設定したトライを作成し、トライ格納領域２２６に設定する。このとき、ＣＰＵ２０３が作成するトライの具体例は、図５を用いて後記する。
【００３９】
そして、ＣＰＵ２０３は、トライの末端の節それぞれに、その文字列に対応する索引情報２０７のポインタ情報を設定する（Ｓ４０２）。
【００４０】
ここで、ＣＰＵ２０３が、トライ初期化プログラム２１４により作成するトライを、図５を用いて説明する。図５は、図２のＣＰＵが、トライ初期化プログラムにより作成するトライを含むインデクスを例示した図である。
【００４１】
図５に例示するように、インデクス５００は、索引項目を木構造で構成したトライ５０１と、その索引項目に対応する索引情報５０２とを含んで構成される。なお、このトライ５０１の末端の文字列の節には、索引情報を読み出すためのポインタ情報５０３が設定される。なお、図５において、「あ」から始まる文字列のトライのみを示しているが、この他にも「い」から始まる文字列のトライ、「う」から始まる文字列のトライ等も存在する。
【００４２】
例えば、図５に例示したトライ５０１において、１グラム目の「あ」の節に続く２グラム目の節として「あ」、「い」、「う」、…、「ん」の節が設定され、そのさらに次に３グラム目の節として、「あ」、…、「ん」の節が設定される。そして、末端の節（つまり、図５の３グラム目の節）には、索引情報５０２を読み出すためのポインタ情報５０３が設定されている。例えば、「あいち」に関する索引情報２０７のポインタ情報５０３は「ｐｒｔ６１」であり、この索引情報２０７の必要検索時間は「１.１２７」であることを示す。
【００４３】
なお、図５において説明を省略しているが、ＣＰＵ２０３は、トライの初期設定を行うとき、トライを構成する節それぞれに、その節から繋がる索引情報２０７の必要検索時間を設定しておく。
【００４４】
このとき、ＣＰＵ２０３は、トライ５０１の末端の節（例えば、図５に例示したトライ５０１の３グラム目の節）には、その節に繋がる索引情報２０７の必要検索時間を設定し、トライ５０１の末端の節以外の節（例えば、図５に例示したトライ５０１の１グラム目および２グラム目の節）には、この節に繋がる節に設定された必要検索時間の合計値を設定する。
【００４５】
例えば、図５に例示したトライ５０１の２グラム目の「あ」の節の次に、３グラム目の節として、「あ」〜「ん」の節が繋がっている場合、ＣＰＵ２０３は、この２グラム目の「あ」の節の必要検索時間として、３グラム目の「あ」〜「ん」それぞれの節の必要検索時間を合計した値を設定する。また、ＣＰＵ２０３は、この１グラム目の「あ」の節の必要検索時間を設定する場合も同様に、２グラム目の「あ」〜「ん」それぞれに設定された必要検索時間を合計した値を設定する。このように、ＣＰＵ２０３は、トライ５０１の末端の節から順に、その１グラム目の節まで、索引情報２０７の必要検索時間の合計値を計算し、この計算した値を各節に設定する。このようにして節それぞれに設定された必要検索時間は、ＣＰＵ２０３がトライの各節を共通化し、階層化するときに参照される。このときの各節の共通化および階層化の処理の詳細については、図６および図７を用いて後記する。
【００４６】
なお、図５において１グラム目「あ」の節から始まるトライ５０１を例示しているが、これ以外にもトライの１グラム目の「い」〜「わ」の節から始まるトライもトライ格納領域２２６に格納される。また、図示を省略しているが、これら１グラム目の節の親となる節として、０グラム目の節が設定されているものとする。これにより、ＣＰＵ２０３により、この１グラム目「あ」の節に隣接する節が検索されると、１グラム目の「い」〜「わ」の節が検索されることになる。
【００４７】
＜インデクス階層化プログラムおよびインデクス検索時間比較プログラム＞
次に、インデクス階層化プログラム２１６およびインデクス検索時間比較プログラム２１８について、図２を参照しつつ、図６および図７のＰＡＤを用いて詳細に説明する。図６および図７は、図２のインデクス階層化プログラムの処理手順を示した図である。
【００４８】
まず、ＣＰＵ２０３は、主記憶装置２０９のトライ格納領域２２６から、トライ初期化プログラム２１４により作成されたトライを読み出すと、このインデクス階層化プログラム２１６の実行処理に用いる変数（ｔｏｔａｌ,Ｍ,Ｎ,Ｌ,Ｐ）の初期値を設定する。ここで、ＣＰＵ２０３は、初期値として、ｔｏｔａｌ=０、Ｍ＝１、Ｎ＝１、Ｌ＝１、Ｐ＝１を設定する（Ｓ６００）。
【００４９】
なお、この変数ｔｏｔａｌは、トライの各節に設定された必要検索時間の合計値を計算するために用いる変数である。変数Ｍは、目標検索時間以上の節の数をカウントするために用いる変数である。変数Ｎは、隣接する節のうち、処理を実行した節の数をカウントするために用いる変数である。変数Ｌは、目標検索時間未満の節のうち、処理を実行した節の数をカウントするために用いる変数である。変数Ｐは、変数ｔｏｔａｌが、目標検索時間未満の節の数をカウントするために用いる変数である。なお、この目標検索時間とは、ＣＰＵ２０３が、当該節を、共通化するか否かを判断するために用いる閾値であり、主記憶装置２０９の所定領域に格納される。
【００５０】
次に、ＣＰＵ２０３は、隣接部分文字列検索プログラム２１９を起動し、隣接する節を探索し、その節の数をカウントする（Ｓ６０１）。ここでは、まず、ＣＰＵ２０３は、トライの１グラム目の節の数をカウントする。つまり、ＣＰＵ２０３は、トライの０グラム目の節（図示せず）を親とし、兄弟関係にある節の数をカウントする。例えば、図５に例示したトライの１グラム目「あ」の節と、トライの１グラム目の「い」〜「わ」の節まで（図５において図示省略）の数をカウントする。
【００５１】
次に、ＣＰＵ２０３は、変数Ｎの値が、Ｓ６０１でカウントした数以下であるか否かを判断する（Ｓ６０２）。ここで、変数Ｎの値が、Ｓ６０１でカウントした数以下であるとき判断したとき、Ｓ６０３へ進む。
【００５２】
そして、ＣＰＵ２０３は、隣接する節のうち、まだ処理を行っていない節を１つ選択する（Ｓ６０３）。例えば、トライの１グラム目の「あ」〜「わ」の節から、まだ処理を行っていない、「あ」の節を選択する。
【００５３】
一方、Ｓ６０２において、変数ＮがＳ６０１でカウントした数を超える数のとき、Ｓ６０７へ進む。つまり、ＣＰＵ２０３が、隣接する節のうち、その節における必要検索時間が目標検索時間未満の節（目標検索時間非超過部分文字列の節）すべてについて、階層化が終了すると、Ｓ６０７へ進む。
【００５４】
ＣＰＵ２０３は、Ｓ６０３で節を選択した後、この選択した節に設定されている必要検索時間を読み出す（Ｓ６０４）。例えば、図５に例示するトライ５０１の１グラム目の「あ」の節に設定されている必要検索時間を読み出す。そして、ＣＰＵ２０３は、この読み出した必要検索時間に基づき、節の共通化処理を実行する（Ｓ６０５）。この後、ＣＰＵ２０３は、変数Ｎの値をインクリメントし（Ｓ６０６）、Ｓ６０７へ進む。このＳ６０５における節の共通化処理について、図７を用いて説明する。
【００５５】
まず、ＣＰＵ２０３は、図６のＳ６０３で選択した節における必要検索時間が、目標検索時間以上か否かを判断する（図７のＳ７００）。例えば、図５に例示したトライ５０１の１グラム目の「あ」の節に設定された必要検索時間が「５．０」のとき、この値が、目標検索時間以上か否かを判断する。なお、このときの判断は、前記したインデクス検索時間比較プログラム２１８により行う。
【００５６】
ここで、Ｓ６０３で選択した節における必要検索時間が、目標検索時間以上であるとき（図７のＳ７００のＹｅｓ）、ＣＰＵ２０３は、変数Ｍの値をインクリメントする（Ｓ７０１）。このようにして、ＣＰＵ２０３は、必要検索時間が、目標検索時間以上である節（目標検索時間超過部分文字列の節）の数をカウントする。また、ＣＰＵ２０３は、この目標検索時間超過部分文字列と判断した節を、共通化する節の対象として主記憶装置２０９の所定領域に記憶しておく。例えば、図５に例示する１グラム目の「あ」の節に設定された必要検索時間が、目標検索時間以上だったとき、この１グラム目の「あ」の節の情報を、共通化する節の対象として主記憶装置２０９の所定領域に記憶しておく。
【００５７】
この後、ＣＰＵ２０３は、変数Ｐの値を「０」、変数ｔｏｔａｌの値も「０」にして（Ｓ７０２）、図６のＳ６０６へ進む。つまり、ＣＰＵ２０３は、必要検索時間が目標検索時間以上である節（目標検索時間超過部分文字列の節）については、共通化処理を行わないと判断し、隣接する別の節の処理に移る。例えば、図５に例示するトライの１グラム目の「あ」の節に設定された必要検索時間が、目標検索時間以上だったとき、１グラム目の別の節（「い」の節等）の処理に移る。
【００５８】
一方、Ｓ７００において、Ｓ６０３（図６参照）で選択した節における必要検索時間が、目標検索時間未満のとき（Ｓ７００のＮｏ）、ＣＰＵ２０３は、変数ｔｏｔａｌに、Ｓ６０３で選択した節における必要検索時間を加算する（Ｓ７０３）。例えば、図５に例示するトライの１グラム目の「あ」の節に設定された必要検索時間「５．０」であり、この必要検索時間が目標検索時間未満のとき、変数ｔｏｔａｌに、この必要検索時間「５．０」を加算する。また、ＣＰＵ２０３は、目標検索時間非超過部分文字列の節を、主記憶装置２０９の所定領域に記憶しておく。
【００５９】
そして、ＣＰＵ２０３は、インデクス検索時間比較プログラム２１８により、この必要検索時間を加算した変数ｔｏｔａｌが、目標検索時間以上となったか判断する（Ｓ７０４）。ここで、必要検索時間を加算した変数ｔｏｔａｌが、目標検索時間以上となった場合（Ｓ７０４のＹｅｓ）、変数Ｐの値が１を超えるか否かを判断する（Ｓ７０５）。ここで、変数Ｐが１を超えるとき（Ｓ７０５のＹｅｓ）、つまり、隣接する節のうち、他にも目標検索時間非超過部分文字列の節があるとき、Ｓ７０６へ進む。例えば、ＣＰＵ２０３が、１グラム目の「い」の節に設定された必要検索時間「１．０」を、変数ｔｏｔａｌに加算したところ、この加算した値が、目標検索時間以上となった場合において、他にも目標検索時間非超過部分文字列の節（例えば、１グラム目の「あ」の節）があったとき、Ｓ７０６へ進む。一方、変数Ｐが１以下であるとき（Ｓ７０５のＮｏ）、図６のＳ６０６へ進む。
【００６０】
なお、必要検索時間を加算した変数ｔｏｔａｌがまだ目標検索時間未満であるとき（Ｓ７０４のＮｏ）、ＣＰＵ２０３は、変数Ｐの値をインクリメントして（Ｓ７０９）、図６のＳ６０５へ進む。
【００６１】
Ｓ７０６では、ＣＰＵ２０３は、インデクス階層化節作成プログラム２１７を起動する。そして、ＣＰＵ２０３は、目標検索時間非超過部分文字列の節を共通化し、この共通化した節によりトライを階層化する。このインデクス階層化節作成プログラム２１７に基づく、節の共通化およびトライの階層化の詳細は、図８を用いて後記するが、例えば、前記した例でいうと、図５に例示するトライ５０１の１グラム目の「い」の節と、１グラム目の「あ」の節とを共通化した節を作成する。そして、この共通化した節を節目としてトライを階層化する。
【００６２】
次に、ＣＰＵ２０３は、インデクス階層化節分割プログラム２２０を起動する（Ｓ７０７）。そして、ＣＰＵ２０３は、共通化した節および階層化したトライの分割を行う。この共通化した節および階層化したトライの分割の詳細は、図９を用いて後記する。
【００６３】
そして、ＣＰＵ２０３は、変数Ｐの値を「０」にし、変数ｔｏｔａｌの値を「０」にする（Ｓ７０８）。そして、図６のＳ６０６へ進む。
【００６４】
図６に戻ってＳ６０６以降の説明を続ける。ＣＰＵ２０３は、変数Ｎの値をインクリメントして（Ｓ６０６）、Ｓ６０２へ戻る。そして、ＣＰＵ２０３は、変数Ｎの値が、Ｓ６０１でカウントした数（隣接する節の数）になるまで、Ｓ６０３〜Ｓ６０６の処理を実行する。つまり、隣接するすべての節に、Ｓ６０３〜Ｓ６０６の処理を実行する。そして、ＣＰＵ２０３は、変数Ｎの値がＳ６０１でカウントした数（隣接する節の数）を超えたとき、Ｓ６０７へ進む。つまり、ＣＰＵ２０３は、隣接する節のうち、目標検索時間未満の節（目標検索時間非超過部分文字列の節）の処理をすべて終了すると、目標検索時間以上の節（目標検索時間超過部分文字列の節）の処理にとりかかる。
【００６５】
まず、ＣＰＵ２０３は、変数Ｌが、変数Ｍ（目標検索時間超過部分文字列の節の数＋１）以下か否かを判断する（Ｓ６０７）。ここで、変数Ｌが、変数Ｍ以下であるとき、ＣＰＵ２０３は、主記憶装置２０９に記憶された目標検索時間超過部分文字列の節の中から、まだ処理を行っていない節を１つ選択する（Ｓ６０８）。例えば、図５に例示するトライ５０１において１グラム目の「い」の節が、目標検索時間超過部分文字列の節であるとき、ＣＰＵ２０３は、この１グラム目の「い」の節を選択する。
【００６６】
そして、ＣＰＵ２０３は、変数Ｌの値をインクリメントし（Ｓ６０９）、Ｓ６０８で選択した節の次に続く節を探索する（Ｓ６１０）。例えば、ＣＰＵ２０３は、図５に例示するトライ５０１において、１グラム目の「う」の節の次に続く、２グラム目の節を探索する。ここで、次に続く節が存在するか否かを判断し（Ｓ６１１）、次に続く節が存在する場合、ＣＰＵ２０３は、この節を階層化する（Ｓ６１２）。つまり、ＣＰＵ２０３は、トライにおける次のグラムの節について、Ｓ６００以降の処理を実行する。例えば、図５に例示するトライ５０１において、１グラム目の「い」の節の次に続く、２グラム目の節があったとき、つまり、１グラム目の「い」の節の子の節があったとき、この２グラム目の節について、Ｓ６００以降の処理と同様の処理を行う。そして、１グラム目の「い」の節の子の節の処理を終了すると、１グラム目の別の節（１グラム目の「う」の節等）の処理に移る。
【００６７】
一方、次に続く節が存在しない場合、Ｓ６０８へ戻り、まだ処理を行っていない節の処理に移る。つまり、図５に例示するトライ５０１において、１グラム目の「い」の節の子の節がなかったとき、１グラム目の兄弟関係にある別の節（例えば、１グラム目の「う」の節等）の処理に移る。そして、ＣＰＵ２０３は、このような処理を、変数Ｌが、変数Ｍと同じ値になるまで実行する。つまり、隣接する節のうち、すべての目標検索時間超過部分文字列の節について、処理が完了するまで続ける。すなわち、前記した例でいうと、１グラム目の節のうち、目標検索時間超過部分文字列の節すべてについて、前記した処理を実行する。
【００６８】
＜インデクス階層化節作成プログラム＞
次に、インデクス階層化節作成プログラム２１７について、図２、図５および図９を参照しつつ、図８のＰＡＤを用いて詳細に説明する。図８は、図２のインデクス階層化ノード作成プログラムの処理手順を示した図である。図９は、図５のトライをもとに作成されたトライを例示した図である。
【００６９】
ＣＰＵ２０３は、主記憶装置２０９に記憶された共通化の対象である節（目標検索時間非超過部分文字列）を読み出し、この節を共通化したインデクス階層化節を作成する（Ｓ８００）。
【００７０】
例えば、図５に例示するトライ５０１における２グラム目の「あ」、「い」の以外のすべての節（つまり、２グラム目の「う」〜「ん」の節）が、共通化の対象の節として主記憶装置２０９に記憶されているとき、ＣＰＵ２０３は、この２グラム目の「う」〜「ん」の節を読み出し、これらの節をまとめたインデクス階層化節（符号９０２参照）を作成する。なお、このときのインデクス階層化節のラベルは、図９の符号９０２に示すように、例えば、「あ、い以外」等とする。
【００７１】
また、ＣＰＵ２０３は、この共通化の対象の節およびこの節に繋がる節を、ワークエリア２２５にコピーする。そして、ＣＰＵ２０３は、トライから、この共通化の対象の節およびこの節に繋がる節を削除し、この共通化の対象の節のあった場所に、インデクス階層化節を設置する。つまり、この共通化の対象の節およびこの節に繋がる節を、インデクス階層化節に置き換える。そして、ＣＰＵ２０３は、このようにして節を削除し、インデクス階層化節を設置したトライを第１のトライとして、上位部分文字列格納領域２２４に格納する（Ｓ８０１）。
【００７２】
例えば、ＣＰＵ２０３は、図５に例示するトライ５０１において、２グラム目の「う」〜「ん」の節およびその節に繋がる節をすべてワークエリア２２５にコピーする。そして、トライ５０１からこれらの節を削除し、２グラム目の「う」〜「ん」の節のかわりに、インデクス階層化節９０２を設置する。そして、ＣＰＵ２０３はこのようにして共通化の対象となる節を削除し、かわりにインデクス階層化節を設置したトライを、第１のトライ（図９の符号９００参照）として、図２の上位部分文字列格納領域２２４に格納する。
【００７３】
このようにすることで、ＣＰＵ２０３は、節の数が少なく、容量の少ない第１のトライを作成することができる。従って、文書登録検索システム２００は、主記憶装置２０９の記憶容量が少ない場合であっても、トライを実装することができる。
【００７４】
また、ＣＰＵ２０３は、必要検索時間が短い索引情報２０７に繋がる節については、階層化するが、必要検索時間が長い索引情報２０７に繋がる節については、階層化を行わない。これにより、必要検索時間が短い索引情報２０７を検索する際は、二次記憶装置２０５の第２のトライを経由するが、必要検索時間が長い索引情報２０７を検索する際は、主記憶装置２０９の第１のトライから直に索引情報２０７へ辿りつくことになるので、システム全体として索引情報２０７の検索効率を向上させることができる。
【００７５】
次に、ＣＰＵ２０３は、Ｓ８００で作成したインデクス階層化節から繋がる第２のトライを作成し、図２の下位部分文字列格納領域２０８に格納する（Ｓ８０２）。すなわち、ＣＰＵ２０３は、まずワークエリア２２５に格納されている共通化の対象の節およびこの節に繋がる節を読み出す。そして、この読み出した共通化の対象の節に、この節の親となる節（図９の第２のトライの根９０３参照）を設置する。そして、ＣＰＵ２０３は、この第２のトライの根９０３を頂点とするトライを、インデクス階層化節から繋がる第２のトライ９０４として、図２の下位部分文字列格納領域２０８に格納する。
【００７６】
なお、このようにして第２のトライの格納領域が決まると、ＣＰＵ２０３は、この第２のトライの接続元となるインデクス階層化節に、この第２のトライの格納領域を示すポインタ情報を設定する。
【００７７】
例えば、Ｓ８０２において、ＣＰＵ２０３は、まず、図５に例示するトライの２グラム目の「う」〜「ん」の節およびその節に繋がる節を、ワークエリア２２５から読み出す。そして、ＣＰＵ２０３は読み出したこれらの節の親となる節（図９の第２のトライの根９０３参照）を設置する。そして、ＣＰＵ２０３は、この第２のトライの根９０３を頂点とするトライを、インデクス階層化節９０２から繋がる第２のトライ９０４として、図２の二次記憶装置２０５の下位部分文字列格納領域２０８に格納する。次に、ＣＰＵ２０３は、第１のトライ９００の２グラム目のインデクス階層化節９０２（「あ、い以外」）に、この第２のトライ９０４の格納領域を示すポインタ情報９０５（「ｐｔｒ３３２」）を設定する。
【００７８】
このようにすることで、ＣＰＵ２０３が、索引情報９０６の検索を行う場合、第１のトライ９００のインデクス階層化節から、この節に続く第２のトライ（あるいは第２のトライの根）へジャンプして、索引情報９０６へ辿りつくことができる。
【００７９】
このような処理の後、ＣＰＵ２０３は、インデクス階層化節分割プログラム２２０を起動し、前記した第２のトライの容量に応じて、インデクス階層化節を分割する。
【００８０】
＜インデクス階層化節分割プログラム＞
次に、インデクス階層化節分割プログラム２２０について、図２を参照しつつ、図１０のＰＡＤを用いて詳細に説明する。図１０は、図２のインデクス階層化節分割プログラムの処理手順を示した図である。
【００８１】
まず、図２のＣＰＵ２０３は、インデクス階層化節から指す第２のトライ、つまりインデクス階層化節から続く第２のトライの容量を計測し、その容量が二次記憶装置２０５のディスクキャッシュに格納できる容量より大きいか否かを判断する（Ｓ１０００）。
【００８２】
ここで、この第２のトライの容量が二次記憶装置２０５のディスクキャッシュに格納できる容量以下の場合（Ｓ１０００のＮｏ）、ＣＰＵ２０３は、インデクス階層化節の分割は行わないが、この第２のトライの容量が二次記憶装置２０５のディスクキャッシュに格納できる容量より大きい場合（Ｓ１０００のＹｅｓ）、上位部分文字列格納領域２２４に格納されている、インデクス階層化節をワークエリア２２５上に読み出し、このインデクス階層化節を分割する（Ｓ１００１）。Ｓ１００１で、分割したインデクス階層化節は、図２の上位部分文字列格納領域２２４に戻す。なお、このときの分割は、その分割したインデクス階層化節の先にある第２のトライの容量が、ディスクキャッシュに格納できる容量以下となるように行う。このようにすることで、ＣＰＵ２０３が、二次記憶装置２０５に格納される第２のトライを検索する際、高速に検索できる。
【００８３】
なお、Ｓ１００１における、分割の個数は、分割後のインデクス階層化節の先にある第２のトライの容量が、ディスクキャッシュに格納できる容量以下となる範囲で、できるだけ少ない方がよい。つまり、Ｓ１００１の分割は、分割後の第２のトライの容量が、ディスクキャッシュの容量以下となり、かつ、分割してできる新たな第２のトライの数が最小になるのが好ましい。これは、分割により第２のトライの数が増えると、これに伴い第１のトライにおけるインデクス階層化節の数も増え、第１のトライの容量が大きくなってしまうからである。
【００８４】
そして、ＣＰＵ２０３は、下位部分文字列格納領域２０８に格納された第２のトライを、ワークエリア２２５上に読み出し、Ｓ１００１のインデクス階層化節の分割に従って、第２のトライを分割する（Ｓ１００２）。次に、ＣＰＵ２０３は、分割した第２のトライそれぞれに第２のトライの根を設置し、下位部分文字列格納領域２０８に格納する。
【００８５】
また、ＣＰＵ２０３は、分割した第２のトライの格納領域が決まると、Ｓ１００１において分割したインデクス階層化節に、この第２のトライの格納領域へのポインタ情報を設定する（Ｓ１００３）。
【００８６】
ここで、図１１、図１２および図１３を用いて、前記したインデクス階層化節の分割処理を具体的に説明する。図１１および図１２は、本実施の形態のインデクス階層化節の分割手順を概念的に説明した図である。図１３は、図１１および図１２を説明するために引用した図である。以下の説明において、二次記憶装置２０５のディスクキャッシュに格納できる容量は、６ｋであるものとして説明する。
【００８７】
例えば、図１１に例示する第１のトライ１１００において、インデクス階層化節１１０１（「ち、つ以外」）の先にある第２のトライ１１０２の容量は７ｋである。そして、この第２のトライ１１０２の容量は、二次記憶装置２０５のディスクキャッシュに格納できる容量を超えている。
【００８８】
従って、ＣＰＵ２０３は、この第２のトライ１１０２の容量が、６ｋ以下となるように第２のトライ１１０２を分割し、それに伴いインデクス階層化節１１０１も分割する。
【００８９】
例えば、ＣＰＵ２０３は、図１１における３グラム目のインデクス階層化節１１０１（「ち、つ以外」）を、図１２に例示するように、インデクス階層化節１２００（「あ〜む」）およびインデクス階層化節１２０１（「め〜ん」）の２つのインデクス階層化節に分割する。このとき、インデクス階層化節１２００（「あ〜む」）の先に続く第２のトライの容量は３．８ｋ、インデクス階層化節１２０１（「め〜ん」）の先に続く第２のトライの容量は３．２ｋというように、それぞれの容量が、ディスクキャッシュに格納できる容量以下となるように分割する。そして、ＣＰＵ２０３は、分割後の第２のトライそれぞれに、第２のトライの根１２０２,１２０３を設置する。また、ＣＰＵ２０３は、インデクス階層化節１２００,１２０１それぞれに、この分割後の第２のトライの格納領域を示すポインタ情報１２０４,１２０５を設定する。
【００９０】
つまり、図１３のグラフに示すように、図１１のインデクス階層化節１１０１の分割前は、「あ−い−あ」〜「あ−い−た」および「あ−い−て」〜「あ−い−ん」のインデクス階層化節の第２のトライの容量は、ディスクキャッシュに格納できる容量（６ｋ）を超えていたところ、図１２の「あ−い−あ」〜「あ−い−む」のインデクス階層化節１２００および「あ−い−め」〜「あ−い−ん」のインデクス階層化節１２０１に分割することで、それぞれの第２のトライの容量は、ディスクキャッシュに格納できる容量（６ｋ）以下とする。
【００９１】
ＣＰＵ２０３が、このようなインデクス階層化節の分割を行うことで、第２のトライの容量を、二次記憶装置２０５のディスクキャッシュに格納できる容量以下とすることができる。これにより、ＣＰＵ２０３は、ディスクキャッシュを用いて索引情報２０７の検索を高速に行うことができる。
【００９２】
＜検索処理＞
次に、前記した処理により作成されたインデクスにより、ＣＰＵ２０３が索引情報の検索を行う手順について説明する。ユーザが入力した検索タームに関する索引情報２０７の検索は、ＣＰＵ２０３が、システム制御プログラム２１２から検索制御プログラム２１１を実行することで行われる。検索制御プログラム２１１は、インデクス検索プログラム２２１を実行することで行われる。
【００９３】
＜インデクス検索プログラム＞
インデクス検索プログラム２２１について、図１４のＰＡＤを用いて詳細に説明する。図１４は、図２のインデクス検索プログラムの処理手順を示した図である。ここでは、ＣＰＵ２０３が、図９に例示する第１のトライ９００および第２のトライ９０４の節を辿って、索引情報２０７を検索する場合について説明する。
【００９４】
ＣＰＵ２０３は、まず入力された検索タームを、連続するグラム数分の文字列に分割する（Ｓ１４００）。ここで、分割する文字列の文字数は、インデクスのグラム数（所定長）以下の文字数とする。例えば、検索タームが「あいぬじん」である場合において、図９に例示したインデクスは３グラムなので、ＣＰＵ２０３は、「あいぬ」、「じん＿」といった３文字以下の文字列に分割する。
【００９５】
次に、ＣＰＵ２０３は、検索タームを分割した文字列の個数分、以下のＳ１４０２〜Ｓ１４０４の処理を繰り返す（Ｓ１４０１）。例えば、検索タームである「あいぬじん」を、「あいぬ」、「じん＿」という２個の文字列に分割した場合、Ｓ１４０２〜Ｓ１４０４の処理を２回実行する。
【００９６】
次に、ＣＰＵ２０３は、上位部分文字列検索プログラム２２２を起動する。そして、ＣＰＵ２０３は、分割した文字列について、前記した第１のトライを辿り、末端の節に設定された第２のトライのポインタ情報を読み出す（Ｓ１４０２）。このようにして、ＣＰＵ２０３は、分割した文字列のうち、第１のトライに含まれる文字列（上位部分文字列）の検索を行い、この上位部分文字列に続く下位部分文字列（第２のトライに含まれる文字列）のポインタ情報を読み出す。
【００９７】
例えば、ＣＰＵ２０３が、図９に例示する第１のトライ９００において、１グラム目の「あ」の節、２グラム目の「い」の節、３グラム目の「ち、つ以外」の節というように、節を辿る。そして、末端の節である３グラム目の「ち、つ以外」の節（インデクス階層化節）に設定された第２のトライのポインタ情報（「ｐｔｒ３３１」）を読み出す。
【００９８】
次に、ＣＰＵ２０３は、下位部分文字列検索プログラム２２３を起動する。続いて、Ｓ１４０２で読み出した第２のトライのポインタ情報をもとに、第２のトライにアクセスする。そして、ＣＰＵ２０３は、この第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報（索引情報のポインタ情報）が示す索引情報２０７をワークエリア２２５へ読み込む（Ｓ１４０３）。
【００９９】
例えば、ＣＰＵ２０３は、図９に例示する第１のトライ９００の３グラム目の「ち、つ以外」の節に設定された第２のトライのポインタ情報「ｐｔｒ３３１」をもとに、この「ち、つ以外」の節の次に続く、第２のトライ９０４にアクセスする。そして、この第２のトライの「ぬ」の節に設定されたポインタ情報「ｐｔｒ１９９」が示す索引情報２０７をワークエリア２２５へ読み込む。つまり、ＣＰＵ２０３は、「あいぬ」を検索項目とする索引情報２０７をワークエリア２２５へ読み込む。
【０１００】
次に、ＣＰＵ２０３は、読み込んだ索引情報２０７から当該文字列を含む文書番号２２７および文字位置（位置情報）２２８を抽出し、ワークエリア２２５に格納する（Ｓ１４０４）。
【０１０１】
例えば、ＣＰＵ２０３は、図９の符号９０７に示す「あいぬ」の索引情報に格納されている、「あいぬ」を含む文書番号「００１」と、文字位置「２１」を抽出し、ワークエリア２２５に格納する。つまり、「あいぬ」という文字列は、文書番号「００１」の文書の文字位置「２１」の位置にあるという情報を抽出する。
【０１０２】
ＣＰＵ２０３は、以上の処理を、検索タームを分割した文字列の個数分実行する。つまり、ＣＰＵ２０３は「あいぬ」の処理を終了すると、「じん＿」についても、同様の処理を実行し、この「じん＿」を含む文書番号と文字位置（位置情報）を抽出し、ワークエリア２２５に格納する。
【０１０３】
そして、ＣＰＵ２０３は、すべての文字列の位置情報の抽出を完了すると、ワークエリア２２５に格納された文字列ごとの位置情報のうち、同じ位置関係にある位置情報を抽出する（Ｓ１４０５）。つまり、ＣＰＵ２０３は、文字列同士が検索タームの並びと同じ位置関係にある位置情報を検索し、この位置情報を出力する。
【０１０４】
例えば、ＣＰＵ２０３は、「あいぬ」の位置情報として、文書番号「００１」および文字位置「２１」という情報を抽出する。また、図示していないが、「じん＿」の位置情報として、文書番号「００１」および文字位置「２４」という情報を抽出したとする。この場合、両者とも、文書番号が同じであり、かつ、文字位置についても「あいぬ」（先頭の文字「あ」は２１番目）のすぐ次に「じん＿」（先頭の文字「じ」は２４番目）が続く位置関係にあり、文字列同士が検索タームの並びと同じ位置関係にある。従って、「あいぬじん」は、文書番号「００１」の文書において、文字位置「２１」から始まる位置にある文字列であるという情報を検索することができる。
【０１０５】
このようにして、ＣＰＵ２０３は、文書における検索タームの位置情報を得ることができる。
【０１０６】
＜第２の実施の形態＞
第２の実施の形態の文書登録検索システムは、索引情報２０７の必要検索時間に代えて、索引情報２０７の容量（索引情報の容量の合計値）をもとに当該節を共通化するか否かを判断することを特徴とする。図１５は、本発明の第２の実施の形態における文書登録検索システムの構成例を示した図である。
【０１０７】
図１５に示すように、第２の実施の形態の文書登録検索システム２００Ａは、図２のトライ初期化プログラム２１４に代えて、トライ初期化プログラム２１４Ａを備え、また、図２のインデクス階層化プログラム２１６に代えて、インデクス階層化プログラム２１６Ａを備えることを特徴とする。このインデクス階層化プログラム２１６Ａは、図１５に示すように、図２のインデクス検索時間比較プログラム２１８に代えて、索引情報容量比較プログラム２１８Ａを備えることを特徴とする。前記した第１の実施の形態と同様の構成要素は同じ符号を付して、説明を省略する。なお、ＣＰＵ２０３が索引情報容量比較プログラム２１８Ａを実行することで、請求項における索引情報容量比較部の機能を実現する。
【０１０８】
トライ初期化プログラム２１４Ａは、トライの初期化を行う際、トライの各節に、この節を辿った先にある索引情報２０７の容量（索引情報の容量の合計値）の情報を付加するプログラムである。
【０１０９】
また、このインデクス階層化プログラム２１６Ａは、索引情報容量比較プログラムにより、各節の索引情報の容量の値（索引情報の容量の合計値）の比較を行い、この節をインデクス階層化節とするか否かを判断するプログラムである。
【０１１０】
このインデクス階層化プログラム２１６Ａの処理手順を、図１６および図１７を用いて説明する。図１６および図１７は、図１５のインデクス階層化プログラムの処理手順を示した図である。図１６のＳ１６００〜Ｓ１６０３までの処理は、図６のＳ６００〜Ｓ６０３までの処理と同様なので説明を省略し、Ｓ１６０４から説明する。なお、本フローにおける変数ｔｏｔａｌは、節に設定されている索引情報の容量の合計値を計算するために用いる変数である。
【０１１１】
ＣＰＵ２０３は、Ｓ１６０３で節を選択した後、この選択した節に設定されている索引情報の容量の情報を読み出す（Ｓ１６０４）。例えば、図５に例示するトライ５０１の１グラム目の「あ」の節に設定されている索引情報２０７の容量の情報を読み出す。そして、ＣＰＵ２０３は、この読み出した索引情報２０７の容量の情報に基づき、節の共通化処理を実行する（Ｓ１６０５）。なお、Ｓ１６０６は、図６のＳ６０６と同様なので説明を省略する。このＳ１６０５における節の共通化処理について、図１７を用いて説明する。
【０１１２】
まず、ＣＰＵ２０３は、Ｓ１６０３で選択した節における索引情報２０７の容量の値が、所定の閾値（索引情報の容量の閾値）以上か否かを判断する（図１７のＳ１７００）。このときの判断は、前記した索引情報容量比較プログラム２１８Ａにより行われる。
【０１１３】
ここで、Ｓ１６０３で選択した節における索引情報の容量が、所定の閾値（索引情報の容量の閾値）以上であるとき（Ｓ１７００のＹｅｓ）、Ｓ１７０１およびＳ１７０２の処理を実行する。Ｓ１７０１およびＳ１７０２の処理は、図７のＳ７０１およびＳ７０２の処理と同様なので説明を省略する。
【０１１４】
一方、Ｓ１７００において、Ｓ１６０３で選択した節における索引情報の容量が、前記した閾値未満のとき（Ｓ１７００のＮｏ）、ＣＰＵ２０３は、変数ｔｏｔａｌに、Ｓ１６０３で選択した節における索引情報の容量の値を加算する（Ｓ１７０３）。
【０１１５】
そして、ＣＰＵ２０３は、索引情報容量比較プログラム２１８Ａにより、この索引情報の容量を加算した変数ｔｏｔａｌが、前記した所定の閾値以上か否かを判断する（Ｓ１７０４）。ここで、この索引情報の容量を加算した変数ｔｏｔａｌが、前記した所定の閾値（索引情報の容量の閾値）以上であるとき（Ｓ１７０４のＹｅｓ）、変数Ｐの値が１以上であるか否かを判断する（Ｓ１７０５）。ここで、変数Ｐが１を超えるとき（Ｓ１７０５のＹｅｓ）、つまり、隣接する節のうち、他にも容量非超過部分文字列の節があるとき、Ｓ１７０６へ進む。一方、変数Ｐが１以下であるとき（Ｓ１７０５のＮｏ）、図１６のＳ１６０６へ進む。
【０１１６】
なお、索引情報の容量を加算した変数ｔｏｔａｌが前記した所定の閾値（索引情報の容量の閾値）未満であるとき（Ｓ１７０４のＮｏ）、ＣＰＵ２０３は、変数Ｐの値をインクリメントして（Ｓ１７０９）、図１６のＳ１６０６へ進む。
【０１１７】
Ｓ１７０６において、ＣＰＵ２０３は、インデクス階層化節作成プログラム２１７を起動する。そして、ＣＰＵ２０３は、容量非超過部分文字列の節を共通化し、この共通化した節によりトライを階層化する（Ｓ１７０６）。この後の、Ｓ１７０７およびＳ１７０８の処理は、図７のＳ７０７およびＳ７０８の処理と同様なので、説明を省略する。
【０１１８】
また、図１６のＳ１６０７の処理は、図６のＳ６０７と同様なので、説明を省略し、Ｓ１６０８から説明する。Ｓ１６０７において、変数Ｌが、変数Ｍ以下であるとき、ＣＰＵ２０３は、主記憶装置２０９に記憶された容量超過部分文字列の節の中から、まだ処理を行っていない節を１つ選択する（Ｓ１６０８）。そして、このすべての容量超過部分文字列について処理を実行するまで、Ｓ１６０９〜Ｓ１６１２の処理を実行する。このＳ１６０９〜Ｓ１６１２の処理は、図６のＳ６０９〜Ｓ６１２の処理と同様であるので、説明を省略する。
【０１１９】
このように、ＣＰＵ２０３は、索引情報２０７の容量（索引情報の容量の合計値）を用いることでも検索効率のよいトライを作成することができる。
【０１２０】
＜その他の実施の形態＞
なお、前記した実施の形態において、トライの節はひらがなを用いる場合を例に説明したが、カタカナや漢字を用いるようにしてももちろんよい。また、テキスト２０６が日本語以外の言語を含むものであれば、その言語の文字をトライの節に用いるようにすればよい。図１８は、本実施の形態のインデクスを例示した図である。図１９は、図１８のインデクスを階層化したものを例示した図である。
【０１２１】
例えば、テキスト２０６が、英語の文書であるとき、文書登録検索システム２００,２００Ａが、トライ初期化プログラム２１４,２１４Ａにより作成したトライは、図１８に例示するように、アルファベットの文字１つ１つをトライの節としたものになる。例えば、図１８に例示するように「ａ」の節、「ｉ」の節、「ｒ」の節を辿り、「ｒ」の節に設定されたポインタ情報１８０２が示す先に「ａｉｒ」という文字列の索引情報１８０１が置かれる。また、文書登録検索システム２００,２００Ａが、図１８に例示するようなアルファベットのトライ１８００を階層化して、図１９に例示するような第１のトライ１９００および第２のトライ１９０１を作成する場合も、トライの節はアルファベットの文字１つ１つを単位としたものになる。
【０１２２】
さらに、前記した実施の形態において、索引情報２０７は、テキスト２０６に含まれる文字列の索引情報としたが、画像データや映像データの索引情報であってもよい。
【０１２３】
また、文書登録検索システム２００,２００Ａにおいて、インデクス階層化節分割プログラム２２０を含まない構成としてもよい。すなわち、文書登録検索システム２００,２００Ａにおいて、インデクス階層化節を作成した後、このインデクス階層化節の分割を行わないようにしてもよい。
【０１２４】
さらに、文書登録検索システム２００,２００Ａは、インデクス作成登録プログラム２１３と、インデクス検索プログラム２２１との両方のプログラムを含む構成としたが、これらを別個の構成としてもよい。すなわち、インデクス作成登録プログラム２１３によりインデクス作成を行うコンピュータとは別に、インデクス検索プログラム２２１によりインデクス検索を行うコンピュータを設けるようにしてもよい。
【０１２５】
また、文書登録検索システム２００,２００Ａの二次記憶装置２０５は、この文書登録検索システム２００,２００Ａの外部に設置するようにしてもよい。
【０１２６】
また、前記した実施の形態において、１つの文字コードを１グラムとしてもよい。例えば、２バイト文字コードであれば２バイト（１６ビット）を１グラムとし、１バイト文字コードであれば１バイト（８ビット）を１グラムとしてもよい。また、グラムは、文字コードに制限されることなく、任意のビット長を１グラムとしてもよい。このようにすることで、例えば、４ビットまたは２ビットの記号コードを１グラムとしてトライを生成し、記号列の登録および検索を実現することができる。
【０１２７】
また、前記した実施の形態において、文書登録検索システム２００,２００Ａは共通化節の下に繋がるトライをトライ形式で二次記憶装置２０５の下位部分文字列格納領域２０８に格納することとしたが、これに限定されない。例えば、二次記憶装置２０５において、ＣＰＵ２０３がアクセスしやすいよう、Ｂ木（B tree）形式で格納するようにしてもよい。さらに、二次記憶装置２０５において、ディスク容量を削減するために、トライの圧縮を行い、格納するようにしてもよい。
【０１２８】
本実施の形態に係る各プログラムはコンピュータによる読み取り可能な記憶媒体（ＣＤ−ＲＯＭ等）に記憶して提供することが可能である。また、そのプログラムを、インターネット等のネットワークを通して提供することも可能である。
【図面の簡単な説明】
【０１２９】
【図１】比較例のインデクスを例示した図である。
【図２】本発明の第１の実施の形態における文書登録検索システムの構成例を示した図である。
【図３】図２のインデクス作成登録プログラムの処理手順を示した図である。
【図４】図２のトライ初期化プログラムの処理手順を示した図である。
【図５】図２のＣＰＵが、トライ初期化プログラムにより作成するトライを含むインデクスを例示した図である。
【図６】図２のインデクス階層化プログラムの処理手順を示した図である。
【図７】図２のインデクス階層化プログラムの処理手順を示した図である。
【図８】図２のインデクス階層化ノード作成プログラムの処理手順を示した図である。
【図９】図５のトライをもとに作成されたトライを例示した図である。
【図１０】図２のインデクス階層化節分割プログラムの処理手順を示した図である。
【図１１】本実施の形態のインデクス階層化節の分割手順を概念的に説明した図である。
【図１２】本実施の形態のインデクス階層化節の分割手順を概念的に説明した図である。
【図１３】図１１および図１２を説明するために引用した図である。
【図１４】図２のインデクス検索プログラムの処理手順を示した図である。
【図１５】本発明の第２の実施の形態における文書登録検索システムの構成例を示した図である。
【図１６】図１５のインデクス階層化プログラムの処理手順を示した図である。
【図１７】図１５のインデクス階層化プログラムの処理手順を示した図である。
【図１８】本実施の形態のインデクスを例示した図である。
【図１９】図１８のインデクスを階層化したものを例示した図である。
【符号の説明】
【０１３０】
１００,５０１ トライ
１０１,２０７,５０２,９０６,１８０１ 索引情報
１０２,５０３,９０５,１２０４,１２０５,１８０２ ポインタ情報
１０３,２２７ 文書番号
１０４,２２８ 文字位置
１０５,５００ インデクス
２００,２００Ａ 文書登録検索システム
２０１ ディスプレイ
２０２ キーボード
２０３ ＣＰＵ
２０４ バス
２０５ 二次記憶装置
２０６ テキスト
２０８ 下位部分文字列格納領域
２０９ 主記憶装置
２１０ 文書登録制御プログラム
２１１ 検索制御プログラム
２１２ システム制御プログラム
２１３ インデクス作成登録プログラム
２１４,２１４Ａ トライ初期化プログラム
２１５ 索引情報作成プログラム
２１６,２１６Ａ インデクス階層化プログラム
２１７ インデクス階層化節作成プログラム（インデクス階層化節生成部）
２１８ インデクス検索時間比較プログラム
２１８Ａ 索引情報容量比較プログラム
２１９ 隣接部分文字列検索プログラム
２２０ インデクス階層化節分割プログラム
２２１ インデクス検索プログラム
２２２ 上位部分文字列検索プログラム
２２３ 下位部分文字列検索プログラム
２２４ 上位部分文字列格納領域
２２５ ワークエリア
２２６ トライ格納領域
９００,１１００,１９００ 第１のトライ
９０２,１１０１,１２００,１２０１ インデクス階層化節
９０３,１２０２,１２０３ 第２のトライの根
９０４,１１０２,１９０１ 第２のトライ
【特許請求の範囲】
【請求項１】
索引情報の索引項目の記号列を、記号の節からなる木構造で構成したトライの生成方法であって、
主記憶装置および二次記憶装置を備える記号列検索装置が、
前記トライを生成し、
前記生成したトライを前記主記憶装置に記憶し、
前記索引情報の必要検索時間を参照して、前記生成したトライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算し、前記計算した節ごとの必要検索時間を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記必要検索時間が、所定の閾値以下か否かを判断し、
前記必要検索時間が、前記所定の閾値以下である節のうち、その節の親が同じである節同士を共通化したインデクス階層化節を生成し、
前記共通化の対象である節およびこの節から先に繋がる節を、前記生成したインデクス階層化節に置き換えた第１のトライを生成し、
前記生成した第１のトライを前記主記憶装置の所定領域に格納し、
前記共通化の対象である節およびこの節から先に繋がる節を含む第２のトライを前記二次記憶装置の所定領域に格納し、
前記第１のトライにおける前記インデクス階層化節に、前記第２のトライの格納領域を示すポインタ情報を設定すること
を特徴とするトライの生成方法。
【請求項２】
前記記号列検索装置が、
前記二次記憶装置に格納された索引情報の容量を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の容量の合計を計算し、前記計算した節ごとの索引情報の容量を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記索引情報の容量が、所定の閾値以下か否かを判断し、
前記索引情報の容量が、前記所定の閾値以下である節のうち、同じ節を親とする節同士を共通化したインデクス階層化節を生成すること
を特徴とする請求項１に記載のトライの生成方法。
【請求項３】
前記生成した第２のトライの容量が、前記二次記憶装置が備えるディスクキャッシュの容量を超えるとき、
前記記号列検索装置が、
前記第２のトライの容量が前記ディスクキャッシュの容量以下となるよう、前記第２のトライを分割し、
前記分割した第２のトライに繋がる前記インデクス階層化節を分割し、
前記分割したインデクス階層化節に、前記分割した第２のトライの格納領域を示すポインタ情報を設定すること
を特徴とする請求項１または請求項２に記載のトライの生成方法。
【請求項４】
前記記号列検索装置が、
前記第２のトライを分割するとき、
前記第２のトライの容量が前記ディスクキャッシュの容量以下となり、かつ、前記第２のトライの分割数が最小となるよう分割すること
を特徴する請求項３に記載のトライの生成方法。
【請求項５】
請求項１ないし請求項４のいずれか１項に記載のトライ生成方法により生成された前記第１のトライおよび前記第２のトライを用いて、前記索引情報の検索を行う検索方法であって、
記号列の検索を行う記号列検索装置が、
検索対象の記号列である検索タームの入力を受け付け、
前記入力された検索タームを所定長以下の記号列に分割し、
その分割した記号列それぞれについて、前記主記憶装置に格納される第１のトライを辿り、この第１のトライの末端の節に設定されたポインタ情報を読み出し、
前記読み出したポインタ情報をもとに、前記二次記憶装置に格納される前記第２のトライにアクセスし、
前記アクセスした第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報が示す索引情報を読み出し、
前記読み出した索引情報から、前記分割した記号列それぞれについて、当該記号列を含む文書およびその文書における当該記号列の記号位置を含む位置情報を読み出し、
前記読み出した位置情報から、当該記号列同士が前記検索タームの並びと同じ位置関係にある位置情報を検索し、
前記検索した位置情報を出力すること
を特徴とする記号列検索方法。
【請求項６】
索引情報の索引項目の記号列を、記号の節からなる木構造で構成したトライを生成するトライ生成プログラムであって、
前記トライを生成し、前記生成したトライを主記憶装置に記憶し、前記索引情報の必要検索時間を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算し、前記計算した節ごとの必要検索時間を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記必要検索時間が、所定の閾値以下か否かを判断し、
前記必要検索時間が、前記所定の閾値以下である節のうち、同じ節を親とする節を検索し、
前記検索した節を共通化したインデクス階層化節を生成し、前記共通化の対象である節およびこの節から先に繋がる節を、前記生成したインデクス階層化節に置き換えた第１のトライを生成し、前記生成した第１のトライを主記憶装置の所定領域に格納し、前記共通化の対象である節およびこの節から先に繋がる節を含む第２のトライを二次記憶装置の所定領域に格納し、前記第１のトライにおける前記インデクス階層化節に、前記第２のトライの格納領域を示すポインタ情報を設定する
処理を記号列検索装置であるコンピュータに実行させることを特徴とするトライ生成プログラム。
【請求項７】
前記二次記憶装置に格納された索引情報の容量を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の容量の合計を計算し、前記計算した節ごとの索引情報の容量を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記索引情報の容量が、所定の閾値以下か否かを判断し、
前記索引情報の容量が、前記所定の閾値以下である節のうち、同じ節を親とする節同士を共通化したインデクス階層化節を生成する
処理をコンピュータに実行させることを特徴とする請求項６に記載のトライ生成プログラム。
【請求項８】
請求項６または請求項７に記載のトライ生成プログラムにより生成された前記第１のトライおよび前記第２のトライを用いて、前記索引情報の検索を行う検索プログラムであって、
検索タームの入力を受け付け、前記入力された検索タームを所定長以下の記号列に分割し、その分割した記号列それぞれについて、前記主記憶装置に格納される第１のトライを辿り、この第１のトライの末端の節に設定されたポインタ情報を読み出し、前記読み出したポインタ情報をもとに、前記二次記憶装置に格納される前記第２のトライにアクセスし、前記アクセスした第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報が示す索引情報を読み出し、前記読み出した索引情報から、前記分割した記号列それぞれについて、当該記号列を含む文書およびその文書における当該記号列の記号位置を含む位置情報を読み出し、前記読み出した位置情報から、当該記号列同士が前記検索タームの並びと同じ位置関係にある位置情報を検索し、
前記検索した位置情報を出力する
処理をコンピュータに実行させることを特徴とする記号列検索プログラム。
【請求項９】
索引情報の索引項目の記号列を、記号の節からなる木構造で構成したトライを生成するトライ生成装置であって、
前記トライを生成し、前記生成したトライを主記憶装置に記憶し、前記索引情報の必要検索時間を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算し、前記計算した節ごとの必要検索時間を、前記主記憶装置に記憶するトライ初期化部と、
前記トライを構成する節ごとに、その節における前記必要検索時間が、所定の閾値以下か否かを判断するインデクス検索時間比較部と、
前記必要検索時間が、前記所定の閾値以下である節のうち、その節の親が同じである節を検索する隣接部分記号列検索部と、
前記検索した節を共通化したインデクス階層化節を生成し、前記共通化の対象である節およびこの節から先に繋がる節を、前記生成したインデクス階層化節に置き換えた第１のトライを生成し、前記生成した第１のトライを主記憶装置の所定領域に格納し、前記共通化の対象である節およびこの節から先に繋がる節を含む第２のトライを二次記憶装置の所定領域に格納し、前記第１のトライにおける前記インデクス階層化節に、前記第２のトライの格納領域を示すポインタ情報を設定するインデクス階層化節生成部と、
を備えることを特徴とするトライ生成装置。
【請求項１０】
前記トライを構成する節ごとに、その節における前記索引情報の容量が、所定の閾値以下か否かを判断する索引情報容量比較部をさらに備え、
前記トライ初期化部は、
前記トライを生成し、前記生成したトライを主記憶装置に記憶し、前記索引情報の容量を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の容量の合計を計算し、前記計算した節ごとの索引情報の容量を、前記主記憶装置に記憶し、
前記隣接部分記号列検索部は、
前記必要検索時間が、前記所定の閾値以下である節のうち、その節の親が同じである節を検索すること
を特徴とする請求項９に記載のトライ生成装置。
【請求項１１】
請求項９または請求項１０に記載のトライ生成装置により生成された前記第１のトライおよび前記第２のトライを用いて、前記索引情報の検索を行う検索装置であって、
検索タームの入力を受け付ける入力装置と、
前記入力された検索タームを所定長以下の記号列に分割し、その分割した記号列それぞれについて、前記主記憶装置に格納される第１のトライを辿り、この第１のトライの末端の節に設定されたポインタ情報を読み出し、前記読み出したポインタ情報をもとに、前記二次記憶装置に格納される前記第２のトライにアクセスし、前記アクセスした第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報が示す索引情報を読み出し、前記読み出した索引情報から、前記分割した記号列それぞれについて、当該記号列を含む文書およびその文書における当該記号列の記号位置を含む位置情報を読み出し、前記読み出した位置情報から、当該記号列同士が前記検索タームの並びと同じ位置関係にある位置情報を検索するインデクス検索部と、
前記検索した位置情報を出力する出力装置と、
を備えることを特徴とする記号列検索装置。
【請求項１】
索引情報の索引項目の記号列を、記号の節からなる木構造で構成したトライの生成方法であって、
主記憶装置および二次記憶装置を備える記号列検索装置が、
前記トライを生成し、
前記生成したトライを前記主記憶装置に記憶し、
前記索引情報の必要検索時間を参照して、前記生成したトライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算し、前記計算した節ごとの必要検索時間を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記必要検索時間が、所定の閾値以下か否かを判断し、
前記必要検索時間が、前記所定の閾値以下である節のうち、その節の親が同じである節同士を共通化したインデクス階層化節を生成し、
前記共通化の対象である節およびこの節から先に繋がる節を、前記生成したインデクス階層化節に置き換えた第１のトライを生成し、
前記生成した第１のトライを前記主記憶装置の所定領域に格納し、
前記共通化の対象である節およびこの節から先に繋がる節を含む第２のトライを前記二次記憶装置の所定領域に格納し、
前記第１のトライにおける前記インデクス階層化節に、前記第２のトライの格納領域を示すポインタ情報を設定すること
を特徴とするトライの生成方法。
【請求項２】
前記記号列検索装置が、
前記二次記憶装置に格納された索引情報の容量を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の容量の合計を計算し、前記計算した節ごとの索引情報の容量を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記索引情報の容量が、所定の閾値以下か否かを判断し、
前記索引情報の容量が、前記所定の閾値以下である節のうち、同じ節を親とする節同士を共通化したインデクス階層化節を生成すること
を特徴とする請求項１に記載のトライの生成方法。
【請求項３】
前記生成した第２のトライの容量が、前記二次記憶装置が備えるディスクキャッシュの容量を超えるとき、
前記記号列検索装置が、
前記第２のトライの容量が前記ディスクキャッシュの容量以下となるよう、前記第２のトライを分割し、
前記分割した第２のトライに繋がる前記インデクス階層化節を分割し、
前記分割したインデクス階層化節に、前記分割した第２のトライの格納領域を示すポインタ情報を設定すること
を特徴とする請求項１または請求項２に記載のトライの生成方法。
【請求項４】
前記記号列検索装置が、
前記第２のトライを分割するとき、
前記第２のトライの容量が前記ディスクキャッシュの容量以下となり、かつ、前記第２のトライの分割数が最小となるよう分割すること
を特徴する請求項３に記載のトライの生成方法。
【請求項５】
請求項１ないし請求項４のいずれか１項に記載のトライ生成方法により生成された前記第１のトライおよび前記第２のトライを用いて、前記索引情報の検索を行う検索方法であって、
記号列の検索を行う記号列検索装置が、
検索対象の記号列である検索タームの入力を受け付け、
前記入力された検索タームを所定長以下の記号列に分割し、
その分割した記号列それぞれについて、前記主記憶装置に格納される第１のトライを辿り、この第１のトライの末端の節に設定されたポインタ情報を読み出し、
前記読み出したポインタ情報をもとに、前記二次記憶装置に格納される前記第２のトライにアクセスし、
前記アクセスした第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報が示す索引情報を読み出し、
前記読み出した索引情報から、前記分割した記号列それぞれについて、当該記号列を含む文書およびその文書における当該記号列の記号位置を含む位置情報を読み出し、
前記読み出した位置情報から、当該記号列同士が前記検索タームの並びと同じ位置関係にある位置情報を検索し、
前記検索した位置情報を出力すること
を特徴とする記号列検索方法。
【請求項６】
索引情報の索引項目の記号列を、記号の節からなる木構造で構成したトライを生成するトライ生成プログラムであって、
前記トライを生成し、前記生成したトライを主記憶装置に記憶し、前記索引情報の必要検索時間を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算し、前記計算した節ごとの必要検索時間を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記必要検索時間が、所定の閾値以下か否かを判断し、
前記必要検索時間が、前記所定の閾値以下である節のうち、同じ節を親とする節を検索し、
前記検索した節を共通化したインデクス階層化節を生成し、前記共通化の対象である節およびこの節から先に繋がる節を、前記生成したインデクス階層化節に置き換えた第１のトライを生成し、前記生成した第１のトライを主記憶装置の所定領域に格納し、前記共通化の対象である節およびこの節から先に繋がる節を含む第２のトライを二次記憶装置の所定領域に格納し、前記第１のトライにおける前記インデクス階層化節に、前記第２のトライの格納領域を示すポインタ情報を設定する
処理を記号列検索装置であるコンピュータに実行させることを特徴とするトライ生成プログラム。
【請求項７】
前記二次記憶装置に格納された索引情報の容量を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の容量の合計を計算し、前記計算した節ごとの索引情報の容量を、前記主記憶装置に記憶し、
前記トライを構成する節ごとに、その節における前記索引情報の容量が、所定の閾値以下か否かを判断し、
前記索引情報の容量が、前記所定の閾値以下である節のうち、同じ節を親とする節同士を共通化したインデクス階層化節を生成する
処理をコンピュータに実行させることを特徴とする請求項６に記載のトライ生成プログラム。
【請求項８】
請求項６または請求項７に記載のトライ生成プログラムにより生成された前記第１のトライおよび前記第２のトライを用いて、前記索引情報の検索を行う検索プログラムであって、
検索タームの入力を受け付け、前記入力された検索タームを所定長以下の記号列に分割し、その分割した記号列それぞれについて、前記主記憶装置に格納される第１のトライを辿り、この第１のトライの末端の節に設定されたポインタ情報を読み出し、前記読み出したポインタ情報をもとに、前記二次記憶装置に格納される前記第２のトライにアクセスし、前記アクセスした第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報が示す索引情報を読み出し、前記読み出した索引情報から、前記分割した記号列それぞれについて、当該記号列を含む文書およびその文書における当該記号列の記号位置を含む位置情報を読み出し、前記読み出した位置情報から、当該記号列同士が前記検索タームの並びと同じ位置関係にある位置情報を検索し、
前記検索した位置情報を出力する
処理をコンピュータに実行させることを特徴とする記号列検索プログラム。
【請求項９】
索引情報の索引項目の記号列を、記号の節からなる木構造で構成したトライを生成するトライ生成装置であって、
前記トライを生成し、前記生成したトライを主記憶装置に記憶し、前記索引情報の必要検索時間を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の必要検索時間の合計を計算し、前記計算した節ごとの必要検索時間を、前記主記憶装置に記憶するトライ初期化部と、
前記トライを構成する節ごとに、その節における前記必要検索時間が、所定の閾値以下か否かを判断するインデクス検索時間比較部と、
前記必要検索時間が、前記所定の閾値以下である節のうち、その節の親が同じである節を検索する隣接部分記号列検索部と、
前記検索した節を共通化したインデクス階層化節を生成し、前記共通化の対象である節およびこの節から先に繋がる節を、前記生成したインデクス階層化節に置き換えた第１のトライを生成し、前記生成した第１のトライを主記憶装置の所定領域に格納し、前記共通化の対象である節およびこの節から先に繋がる節を含む第２のトライを二次記憶装置の所定領域に格納し、前記第１のトライにおける前記インデクス階層化節に、前記第２のトライの格納領域を示すポインタ情報を設定するインデクス階層化節生成部と、
を備えることを特徴とするトライ生成装置。
【請求項１０】
前記トライを構成する節ごとに、その節における前記索引情報の容量が、所定の閾値以下か否かを判断する索引情報容量比較部をさらに備え、
前記トライ初期化部は、
前記トライを生成し、前記生成したトライを主記憶装置に記憶し、前記索引情報の容量を参照して、前記トライを構成する節それぞれについて、その節から先に繋がる索引情報の容量の合計を計算し、前記計算した節ごとの索引情報の容量を、前記主記憶装置に記憶し、
前記隣接部分記号列検索部は、
前記必要検索時間が、前記所定の閾値以下である節のうち、その節の親が同じである節を検索すること
を特徴とする請求項９に記載のトライ生成装置。
【請求項１１】
請求項９または請求項１０に記載のトライ生成装置により生成された前記第１のトライおよび前記第２のトライを用いて、前記索引情報の検索を行う検索装置であって、
検索タームの入力を受け付ける入力装置と、
前記入力された検索タームを所定長以下の記号列に分割し、その分割した記号列それぞれについて、前記主記憶装置に格納される第１のトライを辿り、この第１のトライの末端の節に設定されたポインタ情報を読み出し、前記読み出したポインタ情報をもとに、前記二次記憶装置に格納される前記第２のトライにアクセスし、前記アクセスした第２のトライの節を辿り、この第２のトライの末端に設定されたポインタ情報が示す索引情報を読み出し、前記読み出した索引情報から、前記分割した記号列それぞれについて、当該記号列を含む文書およびその文書における当該記号列の記号位置を含む位置情報を読み出し、前記読み出した位置情報から、当該記号列同士が前記検索タームの並びと同じ位置関係にある位置情報を検索するインデクス検索部と、
前記検索した位置情報を出力する出力装置と、
を備えることを特徴とする記号列検索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２００８−１３４６８８（Ｐ２００８−１３４６８８Ａ）
【公開日】平成２０年６月１２日（２００８．６．１２）
【国際特許分類】
【出願番号】特願２００６−３１８４６０（Ｐ２００６−３１８４６０）
【出願日】平成１８年１１月２７日（２００６．１１．２７）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２０年６月１２日（２００８．６．１２）
【国際特許分類】
【出願日】平成１８年１１月２７日（２００６．１１．２７）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]