(57)【特許請求の範囲】
【請求項１】
インデクス蓄積部と、インデクス選択部と、インデクス登録部とを備える装置が、指定されたキーから値を検索するために、キーと値とを対応させたインデクスを作成する方法において、
前記インデクス蓄積部が、キーと値との組を登録するインデクスを複数のサブインデクスにより構成した二次元配列を記憶しており、
前記インデクス選択部が、登録する値とキーにそれぞれ所定の関数を適用し、
前記インデクス登録部が、前記登録する値に所定の関数を適用して決まる値とキーに所定の関数を適用して決まる値によって参照される前記二次元配列の位置にサブインデクスを格納することを特徴とするインデクス作成方法。
【請求項２】
請求項１に記載のインデクス作成方法において、
サブインデクスとしてＢ＋木構造を用いることを特徴とするインデクス作成方法。
【請求項３】
請求項１または請求項２に記載のインデクス作成方法において、
キーとして語を用い、値として当該語を含んでいる１つの文書を用いることを特徴とするインデクス作成方法。
【請求項４】
請求項３に記載のインデクス作成方法において、
文書と語に各々を一意に識別する文書識別番号と語識別番号を与え、
前記インデクス選択部が、文書に適用する関数として文書識別番号を前記二次元配列の一の方向の位置を示す値にマップするハッシュ関数と、語に適用する関数として語識別番号を前記二次元配列の他の方向の位置を示す値にマップするハッシュ関数とを用い、
前記インデクス登録部が、文書における語の出現をその文書識別番号およびその語識別番号の各々にハッシュ関数を適用して得られた値を用いて対応するサブインデクスに登録することを特徴とするインデクス作成方法。
【請求項５】
請求項４に記載のインデクス作成方法において、
前記装置は、文書ソート部を備え、
前記文書ソート部が、複数の文書における語の出現を一括して登録する場合に、それらの文書の文書識別番号にハッシュ関数を適用して決まる値が同じになるものを１つのグループにまとめ、
前記インデクス登録部が、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項６】
請求項１または請求項２に記載のインデクス作成方法において、
キーとして語を用い、値として当該語の文書における出現回数を用いて、語に一意に識別する語識別番号を与え、
前記インデクス選択部が、語の出現に適用する関数としてその語の文書における出現回数を前記二次元配列の一の方向の位置を示す値にマップするハッシュ関数を適用し、語に適用する関数として語識別番号を前記二次元配列の他の方向の位置を示す値にマップするハッシュ関数を適用し、
前記インデクス登録部が、或る文書における或る語の出現をその語の出現回数およびその語識別番号の各々にハッシュ関数を適用して得られた値を用いて対応するサブインデクスに登録することを特徴とするインデクス作成方法。
【請求項７】
請求項６に記載のインデクス作成方法において、
前記装置は、文書ソート部を備え、
前記文書ソート部が、複数の文書における語の出現を一括して登録する場合に、各語の出現回数にハッシュ関数を適用して決まる値が同じになるものを１つのグループにまとめ、
前記インデクス登録部が、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項８】
請求項１または請求項２に記載のインデクス作成方法において、
キーとして語を用い、値として当該語の文書における出現頻度を用いて、語に一意に識別する語識別番号を与え、
前記インデクス選択部が、語の出現に適用する関数としてその語の文書における出現頻度を前記二次元配列の一の方向の位置を示す値にマップするハッシュ関数を適用し、語に適用する関数として語識別番号を前記二次元配列の他の方向の位置を示す値にマップするハッシュ関数を適用し、
前記インデクス登録部が、或る文書における或る語の出現をその語の出現頻度およびその語識別番号の各々にハッシュ関数を適用して得られた値を用いて対応するサブインデクスに登録することを特徴とするインデクス作成方法。
【請求項９】
請求項８に記載のインデクス作成方法において、
前記装置は、文書ソート部を備え、
前記文書ソート部が、複数の文書における語の出現を一括して登録する場合に、各語の出現頻度にハッシュ関数を適用して決まる値が同じになるものを１つのグループにまとめ、
前記インデクス登録部が、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項１０】
請求項５または請求項７または請求項９に記載のインデクス作成方法において、
１つのグループにまとめられた文書におけるすべての語の出現を登録する場合に、各語の出現を語にハッシュ関数を適用して決まる値が同じになるものを一つのグループにまとめて、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項１１】
請求項１０に記載のインデクス作成方法において、
主記憶装置に用意した少なくとも１つのサブインデクスが格納できるページキャッシュを用いることを特徴とするインデクス作成方法。
【請求項１２】
文書名と当該文書に含まれる語とを対応させたインデクスを複数のサブインデクスにより構成し、文書名と語に各々を一意に識別する文書識別番号と語識別番号を与えて、文書識別番号と語識別番号とにハッシュ関数を適用して決まる値によって参照される二次元配列位置のサブインデクスに登録したインデクスを記憶したインデクス蓄積手段と、
前記インデクス蓄積手段から語をキーとして対応する文書名を得る検索実行手段と、を備えた装置により行う検索方法において、
前記検索実行手段が、複数の語による検索を行う場合に、各語の識別番号にハッシュ関数を適用して決まる値が同じになるものを１つのグループにまとめて、グループごとにサブインデクスに対する検索を実行することを特徴とするインデクス検索方法。
【請求項１３】
文書名と当該文書に含まれる語とを対応させたインデクスを複数のサブインデクスにより構成し、文書名と語に各々を一意に識別する文書識別番号と語識別番号を与えて、文書識別番号と語識別番号とにハッシュ関数を適用して決まる値によって参照される二次元配列位置のサブインデクスに登録したインデクスを記憶したインデクス蓄積手段と、
前記インデクス蓄積手段から語をキーとして対応する文書名を得る検索実行手段と、を備えた装置により行う検索方法において、
前記検索実行手段が、複数の語のＡＮＤまたはＯＲ条件による検索を行う場合に、文書識別番号にハッシュ関数を適用して決まる値が同じになる文書に対するサブインデクスに対して各語の出現を検索し、その検索結果についてＡＮＤまたはＯＲの演算を実施することを特徴とするインデクス検索方法。
【請求項１４】
指定されたキーから値を検索するために、キーと値とを対応させたインデクスを作成する装置において、
複数のサブインデクスから構成したインデクスを記憶するインデクス記憶手段と、
登録する値に所定の関数を適用することにより第１の値を算出する第１の関数適用手段と、
キーに所定の関数を適用することにより第２の値を算出する第２の関数適用手段と、
算出された前記第１の値と前記第２の値に応じて定まる二次元配列の位置にある前記インデクス記憶手段内のサブインデクスに前記キーと前記登録する値との組を格納する格納手段と、を備えたことを特徴とするインデクス作成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば文書に対する全文検索のためのインデクスを高速に生成し、また、当該インデクスを用いて高速な検索を実現する方法に関し、特に、当該インデクスの構成に関する。
【０００２】
【従来の技術】
大量の文書に対する全文検索の方法として、シグネチャ・ファイルと呼ばれるデータ構造を用いる方法がある。 特開平７-２４４６７１号公報に示されている方法では、文書における文字の出現をビットで表すインデクスを構成している。この方法では、格納されている文書数に影響されずに、比較的高速な検索が可能である。
しかしながら、いくつかの異なる語に対して１つのビットを割り当てているため、指定した以外の語が含まれている文書が検索される可能性があり、正確な検索が行えないという問題があった。また、生成や検索のアルゴリズムが複雑であり、既存のデータベース管理システムの上で実現することが困難であった。
【０００３】
このような問題に対して、文献「Compression and Fast Indexing for Multi-Gigabyte Text Databases」には、一般的なデータベース管理システムが提供しているハッシュ表やＢ＋木などのインデクス手法を用いて、高速な全文検索の機能を実現する方法が提案されている。この方法では、インデクスのキーとなる語と値となる文書に識別番号を割り付け、それらを圧縮して格納している。
これにより、検索に必要となるディスクの読み出しページ数を減らし、高速に検索が可能となる。また、異なる語に異なる識別番号を割り付けられるため、正確な検索が可能となる。なお、この文献は、この方法を用いて、約７０万件の文書に対する検索が高速に行えることを示している。
【０００４】
【発明が解決しようとする課題】
しかしながら、上記の文献で述べられている方法では、インデクスの新規作成や更新処理の性能が考慮されていないため、高い性能が得られないという問題があった。特に、更新時に或る語に対して同じ文書を重複して登録しないようにするための確認の処理は、文書識別番号の集まりに対する繰り返し処理により実現しなければならないため、効率よく実現することができない。
【０００５】
また、インタネットのＷＷＷページに対する全文検索を行う場合などのように、対象となる文書の数が数百万件となると、上記の文献で示したような方法であっても、Ｂ＋木の大きさが数十ＧＢとなるため、インデクスへの追加や検索の処理を効率よく行うことができない。
これは、Ｂ＋木に対する１個の語と文書の組の追加や検索処理が木の高さ＋１だけの回数のハードディスクに対するアクセスを必要とすること、Ｂ＋木が巨大になるとディスクのメモリ中へのキャッシュの効果が得られず、ハードディスクに対するほとんどすべてのアクセスが実際にハードディスクからデータを読み込む処理を必要とすることに起因する。
【０００６】
例えば、Ｂ＋木の全体の大きさが１０ＧＢであり、Ｂ＋木の各ノードの大きさが８ＫＢであり、各ノードの分岐の数が５００であるとすると、Ｂ＋木の高さｌｏｇ500（１０ＧＢ／８ＫＢ）−１＝２．１６で、１個の語と文書の組を追加、検索するために平均で２〜３回のディスク・アクセスが必要となる。ハードディスクを１回アクセスするために数十ミリ秒から数百ミリ秒かかるため、１個の語と文書の組の追加、検索には０．１秒から１秒の時間が必要となる。よって、１個の文書の中に１００個の異なる語が含まれているとすると、１個の文書を登録するために１０秒から１００秒の時間を必要とすることになる。
このようなことから、Ｂ＋木に格納するデータの数が多くなるにつれて、Ｂ＋木の高さが高くなってＢ＋木が大きくなり、アクセスするページ数が増え、結果として格納、検索に要する時間が長くなる。例えば、図１７に格納時間の変化の傾向を示すように、格納文書数の増加に応じて格納時間が大幅に増加してしまう。
【０００７】
本発明は、上記従来の事情に鑑みなされたもので、例えば膨大な数にのぼる文書に対する全文検索のためのインデクスを高速に作成する方法を提供することを目的とする。
また、本発明は、このように作成されたインデクスを用いて、高速な検索を実現する方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
具体的には、本発明は、Ｂ＋木インデクスのキーとして、語の識別番号の後ろに文書の識別番号つなげて配置したものを用いることで、或る文書における或る語の出現を、Ｂ＋木インデクスに対する１回の検索で実現できるようにした。
しかしながら、この場合に、これを単一のＢ＋木で管理しようとすると、大量の文書を格納した状態では、Ｂ＋木が巨大になり、１つの文書を追加しようとする際に、最悪の場合、その文書に含まれている異なる語の出現数と同じだけのページを更新しなければならなくなる。
【０００９】
これを避けるため、Ｂ＋木インデクスを、語の識別番号に或るハッシュ関数を適用して得られるハッシュ値と、文書識別番号に別のハッシュ関数を適用して得られるハッシュ値とによって複数のサブインデクスに分割し、これらサブインデクスを二次元の配列に配置する。そして、インデクスの新規生成時や更新時には、文書識別番号のハッシュ値が同じになるものをまとめて登録することで、書き込みページ数を少なくし、処理効率を高めた。
また、複数の語のＡＮＤやＯＲ検索を行う際には、語識別番号のハッシュ値が同じになるものをグループにまとめ、グループごとに文書識別番号のハッシュ値が同じになるＢ＋木に対する検索をまとめて処理することで、ページ読み出し時のページ・キャッシュのヒット率を高め、処理効率を高めた。
【００１０】
すなわち、本発明では、指定されたキーから値を検索するために、キー（例えば、語）と値（例えば、当該語を含んでいる１つの文書）とを対応させたインデクスを作成する方法において、キーと値との組を登録するインデクスを、例えばＢ＋木構造の複数のサブインデクスにより構成し、登録する値に所定の関数を適用して決まる値とキーに所定の関数を適用して決まる値によって参照される二次元配列位置にサブインデクスを格納している。
【００１１】
より具体的には、本発明では、文書と語に各々を一意に識別する文書識別番号と語識別番号を与え、文書に適用する関数として文書識別番号を二次元配列の一の方向の位置を示す値にマップするハッシュ関数と、語に適用する関数として語識別番号を二次元配列の他の方向の位置を示す値にマップするハッシュ関数とを用意し、文書における語の出現をその文書識別番号およびその語識別番号の各々にハッシュ関数を適用して得られた値を用いて対応するサブインデクスに登録する。
また、本発明では、語に一意に識別する語識別番号を与え、語の出現に適用する関数としてその語の文書における出現回数或いは出現頻度を二次元配列の一の方向の位置を示す値にマップするハッシュ関数と、語に適用する関数として語識別番号を二次元配列の他の方向の位置を示す値にマップするハッシュ関数を用意し、或る文書における或る語の出現をその語の出現回数およびその語識別番号の各々にハッシュ関数を適用して得られた値を用いて対応するサブインデクスに登録する。
【００１２】
また、上記の登録に際して、複数の文書における語の出現を一括して登録する場合には、それらの文書の文書識別番号（或いは、各語の出現回数または出現頻度）にハッシュ関数を適用して決まる値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録する。
さらには、上記の登録に際して、１つのグループにまとめられた文書におけるすべての語の出現を登録する場合には、各語の出現を語にハッシュ関数を適用して決まる値が同じになるものを一つのグループにまとめて、グループごとに語の出現を登録する。
なお、上記の登録に際しては、主記憶装置に用意した少なくとも１つのサブインデクスが格納できるページキャッシュを用いる。
【００１３】
また、本発明は、文書名と当該文書に含まれる語とを対応させたインデクスをもちいて、語をキーとして対応する文書名を得る検索方法において、文書名および語に各々を一意に識別する文書識別番号と語識別番号を与え、キーとして語識別番号に文書識別番号を結合した値を用いる。
より具体的には、文書名と当該文書に含まれる語とを対応させたインデクスを複数のサブインデクスにより構成し、文書名と語に各々を一意に識別する文書識別番号と語識別番号を与えて、文書識別番号と語識別番号とにハッシュ関数を適用して決まる値によって参照される二次元配列位置のサブインデクスに登録したインデクスをもちいて、語をキーとして対応する文書名を得る検索方法において、複数の語による検索を行う場合に、各語の識別番号にハッシュ関数を適用して決まる値が同じになるものを１つのグループにまとめて、グループごとにサブインデクスに対する検索を実行する。
【００１４】
また、文書名と当該文書に含まれる語とを対応させたインデクスを複数のサブインデクスにより構成し、文書名と語に各々を一意に識別する文書識別番号と語識別番号を与えて、文書識別番号と語識別番号とにハッシュ関数を適用して決まる値によって参照される二次元配列位置のサブインデクスに登録したインデクスをもちいて、語をキーとして対応する文書名を得る検索方法において、複数の語のＡＮＤまたはＯＲ条件による検索を行う場合に、文書識別番号にハッシュ関数を適用して決まる値が同じになる文書に対するサブインデクスに対して各語の出現を検索し、その検索結果についてＡＮＤまたはＯＲの演算を実施する。
【００１５】
【発明の実施の形態】
本発明の実施形態を図面を参照して説明する。
図１には、本発明に係る方法を実行する装置の構成例を示してある。なお、この装置はコンピュータハードウエア資源を用いて、本発明を実施するためのプログラムを実行することにより構成されている。
【００１６】
文書蓄積部１はハードディスク装置等の外部メモリにより構成されており、文書蓄積部１には登録や検索の対象となる文書がその文書名とともに格納される。文書ソート部２は、インデクスの登録の対象となる文書の文書名を、あらかじめ定義されたハッシュ関数を文書識別番号に適用して得られる値が同じになるものがまとまるようにソートする。
形態素解析部３は、指定された文書の全文を解析し、語の切り出しを行う。
インデクス登録部４は、与えられた文書名および語の識別番号を得て、インデクス選択部５の機能により選択されたＢ＋木構造に、語識別番号と文書識別番号をキーとして語の出現を登録する。
【００１７】
インデクス蓄積部６は、ハードディスク装置等の外部メモリにより構成されており、インデクス蓄積部６はあらかじめ定められた大きさの二次元の配列（ここではＤ×Ｗ、ただし、Ｄ，Ｗは１以上の整数）上にＢ＋木を記憶する。また、インデクス蓄積部６は文書名と文書識別番号、語と語識別番号の対応関係も記憶している。
インデクス選択部５は、与えられた文書識別番号と語識別番号に、それぞれあらかじめ定められたハッシュ関数を適用し、その結果得られた値を用いてインデクス蓄積部６に格納されているインデクス表から語の出現を登録するＢ＋木の識別番号を選択する。
【００１８】
ここで、文書ソート部２、インデクス選択部５で用いられる文書識別番号に適用されるハッシュ関数および語識別番号に適用されるハッシュ関数Ｈは、文書識別番号をｉd、語識別番号をｉwとしたとき、それぞれ、０≦Ｈd（ｉd）＜Ｄ、０≦Ｈw（ｉw）＜Ｗ、となる整数を値とするように定義される。
【００１９】
問い合わせ入力部７は、利用者からの検索要求を受け付け、語をＡＮＤまたはＯＲで結合した検索式を生成する。
検索実行部８は、与えられた検索式に含まれている語の識別番号から、インデクス選択部５の機能により検索の対象となるＢ＋木を得て検索処理を行う。
結果出力部９は、検索実行部８により得られた検索結果をディスプレイ表示等して利用者に提示する。
【００２０】
図２には、インデクス蓄積部６に格納されているＢ＋木のキーの構成例を示してある。
このＢ＋木のキーは、語識別番号の後ろに文書識別番号を結合した構造となっており、本例では、語識別番号として４バイト、文書識別番号として４バイトの領域を割り当てている。
これにより、或る語を含む文書を得る検索においては、その語の出現を含むすべてのＢ＋木について、その語の語識別番号の後ろに文書識別番号として最小のもの（ここでは０）を結合した値と、文書識別番号として最大のもの（ここではＦＦＦＦＦＦＦＦ（１６進））を結合した値の範囲で検索を行うことで、その語に対するすべての出現を、文書識別番号の昇順に得ることができる。
【００２１】
すなわち、この処理ではその手順を図３に示すように、図２のキーに対して、３２ビット左へシフトさせた値をｓｔａｒｔ点とし（ステップＳ１）、３２ビット左へシフトさせて０×ＦＦＦＦＦＦＦＦを加えた値をｅｎｄ点として（ステップＳ２）、ｓｔａｒｔ点からｅｎｄ点までの範囲で検索を行う（ステップＳ３）。
なお、図３において、＜＜はビットを左にシフトする演算を示している。
また、或る文書における或る語の出現を検索したいときには、その語の識別番号とその文書の識別番号を結合した値をキーとして、完全に一致するものを検索することで、該当する語の出現を得ることができる。
【００２２】
例えば、いくつかの文書に関する語の出現を登録した時点で、Ｂ＋木の一部の状態が図４に示されているようになっていたとする。この状態において、語識別番号が４５（１６進）であるような語を含む文書を検索する場合には、キーの値が４５００００００００（１６進）と４５ＦＦＦＦＦＦＦＦ（１６進）の範囲にあるものを検索することで目的とする語の出現（Ｏ4とＯ5）を得られる。また、語識別番号が４５（１６進）であるような語が文書識別番号が７であるような文書に含まれているか否かを確認する場合には、４５０００００００７（１６進）をキーとして、キーの値が一致するものを検索することで、語の出現（Ｏ5）を得ることができる。
【００２３】
図５には、インデクス蓄積部６におけるＢ＋木の格納構造を示してある。
このＢ＋木は、Ｄ×Ｗの二次元配列にＤ×Ｗ個のサブインデクスを格納した構造となっており、文書識別番号がｉdで且つ語識別番号がＩwである或る語の出現は、Ｂ＋木（Ｈw(ｉw)，Ｈd(ｉd)）のサブインデクスに対応してＢ＋木に登録されている。
よって、語識別番号がｉwである語の出現を検索する場合には、図６に示されている手順で選択されたＢ＋木について図３に示されている処理を実行する。
【００２４】
図６には、指定された或る一つの語が出現する文書を検索する処理手順を示してある。
まず、この処理では、与えられた語の語識別番号Ｉwをｉwに代入し、その値を引数としてハッシュ関数Ｈwを適用して得られる値をｗに代入している（ステップＳ１０）。そして、変数ｉおよびｒを０に初期化し（ステップＳ１１）、ｉを１つずつ増加させながら（ステップＳ１４）、ｉがＤとなるまで（ステップＳ１５）、Ｂ＋木（ｗ，ｉ）に対して語の検索を繰り返し行い（ステップＳ１２）、その結果を配列Ｒに追加している（ステップＳ１３）。
【００２５】
これにより、図５に示した二次元配列の或る一つの行に記憶されているＢ＋木の各サブインデクスに対する検索が行える。このようにすることにより、目的とする語の出現はそれ以外のＢ＋木には含まれていないので、これにより見つかった文書のみに目的とする語が含まれていることになる。
このような処理により、検索の対象となるＢ＋木が限定されかつ各Ｂ＋木を順序良く利用するため、検索対象のサブインデクスを保持するキャッシュのヒット率を高めることができ、効率よく検索が実行できる。なお、検索において、検索実行部８が使用する主記憶装置のキャッシュに、少なくとも１つのＢ＋木サブインデクスが保持されるようになっている。
【００２６】
図７には、複数の語のＡＮＤまたはＯＲ条件で検索を行う処理手順を示してある。
この処理は、複数の語とＡＮＤまたはＯＲの演算が与えられて呼び出され、まず、与えられた語の識別番号にハッシュ関数Ｈw（ｉw）を適用して得られる値の順にソートし、その結果を配列Ｘに格納している（ステップＳ２０）。これにより、以下の検索において同じＢ＋木サブインデクスに対する検索が連続して実行されるようになり、サブインデクスを保持するキャッシュのヒット率を高めることができる。
【００２７】
次に、図５に示した二次元配列の列を指定する変数ｄと確定した検索結果の数を示す変数Ｉの値を０に初期化し（ステップＳ２１）、Ｂ＋木（０，ｄ）に対して語識別番号Ｘ［０］の語の出現を検索する（ステップＳ２２）。この検索の処理は図３に示して手順で実施され、検索結果の数は変数ｒに代入され、検索結果は配列Ｒ［０．．．ｒ］に代入される（ステップＳ２３）。
続いて、変数ｗの値を１に初期化し（ステップＳ２４）、ｗを１つずつ増加させながら次のような処理を繰り返し行う。すなわち、二次元配列の縦方向にサブインデクスＢ＋木（Ｈw(X[0])，ｄ）を選択して、検索を実行しながらＡＮＤ，ＯＲの演算を実行する。
【００２８】
この処理は次の手順で実行され、サブインデクスＢ＋木（Ｈw(X[0])，ｄ）に対してＸ[w]の語の出現を図３の処理により検索し（ステップＳ２５）、その結果の数と結果を変数ｒ’とＲ’［０．．．ｒ’］に代入する（ステップＳ２６）。
続いて、ＡＮＤかＯＲかの演算を判断し（ステップＳ２７）、判断結果に従ってＲ［Ｉ．．．Ｉ＋ｒ］とＲ’［０．．．ｒ’］に対してＡＮＤまたはＯＲの演算を実施する（ステップＳ２８、Ｓ２９）。なお、ＡＮＤとＯＲの演算処理は、それぞれ図８、図９に基づいて後述する手順により実行される。
【００２９】
ＡＮＤ演算を行った場合には（ステップＳ２８）、演算の結果がｒ＝Ｉ（すなわち、演算の結果該当する語の出現がなかった）場合には（ステップＳ３０）、ｄを１つ増加させ（ステップＳ３１）、ｄがＤより小さい（すなわち、二次元配列の列がまだ残っている）場合には（ステップＳ３２）、次の列のＢ＋木サブインデクスの検索に進む（ステップＳ２４）。一方、ｒ＝Ｉでない場合には（ステップＳ３０）、ｗを１つだけ増加させ（ステップＳ３３）、次の語があることを確認して（ステップＳ３４）、次の語による検索演算に進む（ステップＳ２５）。
また、ＯＲ演算を行った場合には（ステップＳ２９）、演算の終了後にｗを１つだけ増加させ（ステップＳ３３）、次の語があることを確認して（ステップＳ３４）、次の語による検索演算に進む（ステップＳ２５）。
【００３０】
図８には、上記のＡＮＤ演算の処理（ステップＳ２８）の手順を示してある。この処理では、配列Ｒ［ｌ．．．ｌ＋ｒ］に含まれている語の出現で配列Ｒ’［０．．．ｒ’］に同じ文書の語の出現が含まれているもののみを配列Ｒに残す演算を行う。
両方に含まれているか否かの確認は、ｉを０からｒまで、ｉ’を０からｒ’まで増加させながら（ステップＳ４１、Ｓ４６〜Ｓ４８）、文書識別番号Ｒ［ｉ］．ｉｄと文書識別番号Ｒ’［ｉ’］．ｉｄを比較することで行う（ステップＳ４２）。
【００３１】
そして、Ｒ［ｉ］．ｉｄ＜Ｒ’［ｉ’］．ｉｄの場合には、配列Ｒ’にはＲ［ｉ］．ｉｄと同じ文書識別番号の文書に対する語の出現は含まれていないので、Ｒ［ｉ］を配列Ｒから削除する（ステップＳ４３）。また、Ｒ［ｉ］．ｉｄ＝Ｒ’［ｉ’］．ｉｄの場合には、配列Ｒ’［ｉ’］はＲ［ｉ］と同じ文書に対する語の出現であるので、Ｒ［ｉ］を配列Ｒに残し、ｉとｉ’とをそれぞれ１つずつ増加させて次の語の出現の処理に進む（ステップＳ４４）。また、Ｒ［ｉ］．ｉｄ＞Ｒ’［ｉ’］．ｉｄの場合には、Ｒ［ｉ］と同じ文書に対する語の出現がＲ’［ｉ’＋１．．．ｒ’］に含まれている可能性があるので、ｉ’を１つだけ増加させて再び比較の処理に戻る（ステップＳ４５）。
【００３２】
以上の処理は、ｉが配列Ｒの最後まで進むかｉ’が配列Ｒ’の最後に進むまで繰り返され、最後にｒにｉの値を代入することで（ステップＳ４９）、配列Ｒの後方にあって、Ｒ’［ｒ’−１］の語の出現に対する文書の文書識別番号よりも大きい文書識別番号の文書に対する語の出現をすべて削除して終了する。
なお、検索結果が０の場合には（ステップＳ４０、Ｓ５０）、そのまま処理を終了する。
【００３３】
図９には、上記のＯＲ演算の処理（ステップＳ２９）の手順を示してある。
この処理では、配列Ｒ’［０．．．ｒ’］に含まれている語の出現で配列Ｒ［ｌ．．．ｌ＋ｒ］に同じ文書の語の出現が含まれていないものを配列Ｒに追加することを行う。
この判断は、ｉを０からｒまで、ｉ’を０からｒ’まで増加させながら（ステップＳ６０、Ｓ６３〜Ｓ６７）、文書識別番号Ｒ［ｉ］．ｉｄと文書識別番号Ｒ’［ｉ’］．ｉｄを比較することで行う（ステップＳ６２）。
【００３４】
そして、Ｒ［ｉ］．ｉｄ＜Ｒ’［ｉ’］．ｉｄの場合には、配列Ｒ’にはＲ［ｉ］．ｉｄと同じ文書識別番号の文書に対する語の出現が含まれていないので、ｉを１つだけ増加させて次の比較の処理に進む（ステップＳ６３）。また、Ｒ［ｉ］．ｉｄ＝Ｒ’［ｉ’］．ｉｄの場合には、これらの語の出現は同じ文書に対するものであるので、ｉとｉ’とを共に１つだけ増加させて比較の処理に戻る（ステップＳ６４）。また、Ｒ［ｉ］．ｉｄ＞Ｒ’［ｉ’］．ｉｄの場合には、配列Ｒ［ｌ．．．ｌ＋ｒ］にはＲ’［ｉ’］．ｉｄと同じ文書識別番号の文書に対する語の出現は含まれていないので、語の出現Ｒ’［ｉ’］をＲ［ｉ］の直後に挿入し（ステップＳ６５）、ｉを２、ｉ’を１だけ増加させて次の比較の処理に進む（ステップＳ６６）。
なお、上記の比較の処理に先立って、ｉ＝ｒの確認を行い（ステップＳ６１）、それが真ならばＲ［ｌ．．．ｌ＋ｒ］のすべての要素に対する処理が終了したことになるので、配列Ｒ’で未処理の語の出現をすべて配列Ｒの最後尾に追加して処理を終了する（ステップＳ６８）。
【００３５】
図１０には、複数の文書の語の出現を一括して登録する処理の手順を示してある。
この処理では、まず、各文書を文書識別番号にハッシュ関数Ｈdを適用して得られる値によりグループ分けし、グループ分けされた文書をグループごとに配列Ｇに格納する（ステップＳ７０）。続いて、変数ｇを初期化し（ステップＳ７１）、配列Ｇに格納されている各グループについて、それに属しているすべての文書から語の出現（文書と語の組）を取り出し（ステップＳ７２）、それらを語の識別番号にハッシュ関数Ｈwを適用して得られる値によりグループ分けして、グループ分けされた語の出現をグループごとに配列Ｏに格納する（ステップＳ７３）。
そして、変数ｗを１つずつ増加させながら（ステップＳ７４、Ｓ７６、Ｓ７７）、配列Ｇに格納されている各グループについてそれに属している語の出現を登録する処理（図１１により後述する）を実施し（ステップＳ７５）、さらに、変数ｄを１つずつ増加させながら（ステップＳ７８、Ｓ７９）、上記の処理を繰り返し行う。
【００３６】
上記の処理により、語の出現は図５に示された配列の左上から下方向に並んだＢ＋木サブインデクスに順に格納され、一番下のＢ＋木サブインデクスまで格納が終わると、一つ右の列について上から下方向に並んだＢ＋木サブインデクスに順に格納されるため、複数のＢ＋木サブインデクスを交互に参照することがなくなり、ページ・キャッシュのヒット率を高めることができる。
さらに、主記憶上に一つのＢ＋木サブインデクスの内容を保持できるだけの領域があれば、格納処理をすべて主記憶中で実行できるため、きわめて高速に格納処理を実行できる。
【００３７】
図１１には、或る文書における或る語の出現を登録する処理の手順を示してある。
この処理では、語および文書に対してそれらの識別番号ｉw、ｉdを得て、それぞれにハッシュ関数Ｈw（ｉw）、Ｈd（ｉd）を適用して得られる値を変数ｗ、ｄに保持する（ステップＳ８０、Ｓ８１）。
そして、ｉwの値を左に３２ビットシフトした値にｉdの値を足したものを変数ｋに代入し（ステップＳ８２）、図５に示された配列のサブインデクスＢ＋木  （ｗ，ｄ）にｋをキーとして語の出現を登録する（ステップＳ８３）。
【００３８】
以上のように構成されたイデクスを用い、配列の分割数としてＤ＝６４、Ｗ＝６４を用いると、従来の一つのＢ＋木によるインデクスに比べて、木の深さを２／３程度に縮小できる。
これにより、文書の格納時の性能を、例えば、従来の図１７に示した状況から、図１６に実線で示されているように改善することができる。ここで、図１６で破線で示されているのは図１７で示されている従来技術による格納時間の推移である。なおまた、格納性能ばかりではなく、検索時の性能も約１．５倍に改善できる。
【００３９】
図１２には、本発明の第２実施例として、Ｂ＋木インデクスの縦方向の分割に、語の出現回数に或る関数を適用した値を用いる場合のキーの構成を示してある。  本実施例のキーは、語識別番号の後ろに出現回数を整数であらわした値を結合した構造であり、語識別番号として４バイト、出現回数として４バイトの領域を割り当てている。
【００４０】
図１３には、図１２に示されたキーの構成を用いて、語の出現をＢ＋木に登録した状態を示してある。
図に示されているように、同じ語に対する複数の異なる語の出現が、語の出現回数の多い順にならべられる。これにより、検索処理において、検索の結果を語の出現回数の多い順に取り出すことが容易となる。
【００４１】
なお、第２実施例における語の出現を検索する処理手順は、図６に示した第１実施例における語の出現を検索する処理と同じである。また、語の出現を登録する処理手順は、図１０に示した処理手順において文書識別番号を用いて文書をグループ分けしている処理（ステップＳ７０）を語の出現回数を用いて語の出現をグループ分けする処理に置き換え、また、図１１に示した処理手順において文書識別番号の値を用いてキーとなる値を生成している処理（ステップＳ８１、Ｓ８２）を語の出現回数の値を用いてキーとなる値を生成する処理に置き換えることで実現できる。
【００４２】
図１４には、本発明の第３実施例として、Ｂ＋木の縦方向の分割に語の出現頻度に或る関数を適用した値を用いる場合のキーの構成を示してある。
本実施例のキーは、語識別番号の後ろに出現頻度を整数であらわした値を結合した構造であり、語識別番号として４バイト、出現頻度として１バイトの領域を割り当てている。
なお、或る語の出現の出現頻度は、その語がその文書に現れた回数をその文書の総語数で割って１００を掛けた値であらわす。
【００４３】
図１５には、図１４に示されたキーの構成を用いて、語の出現をＢ＋木に登録した状態を示してある。
図に示されているように、同じ語に対する複数の異なる語の出現が語の出現頻度の高い順にならべられる。これにより、検索処理において、検索の結果を語の出現頻度の高い順に取り出すことが容易となる。
【００４４】
なお、第３実施例における語の出現を検索する処理手順は、図６に示した第１実施例における語の出現を検索する処理と同じである。また、語の出現を登録する処理手順は、図１０に示した処理手順において文書識別番号を用いて文書をグループ分けしている処理（ステップＳ７０）を語の出現頻度を用いて語の出現をグループ分けする処理に置き換え、また、図１１に示した処理手順において文書識別番号の値を用いてキーとなる値を生成している処理（ステップＳ８１、Ｓ８２）を語の出現頻度の値を用いてキーとなる値を生成する処理に置き換えることで実現できる。
【００４５】
【発明の効果】
以上説明したように、本発明によれば、
キーと値との組を登録するインデクスを複数のサブインデクスにより構成し、登録する値にハッシュ関数等の所定の関数を適用して決まる値とキーにハッシュ関数等の所定の関数を適用して決まる値によって参照される二次元配列位置にサブインデクスを格納するようにし、また、検索においては、キーとして、語の識別番号の後ろに文書の識別番号あるいは後の出現回数や出現頻度をつなげて配置したものを用いるようにしたため、大量の文書に対しても、文書の格納処理や検索処理に必要となる更新ページ数や読み出しページ数を削減でき、高速に処理を実行できる。
【図面の簡単な説明】
【図１】  本発明の一実施形態に係る装置構成を示す図である。
【図２】  第１実施例に係るキーの構成を示す図である。
【図３】  語の出現を検索する処理の手順を示すフローチャートである。
【図４】  Ｂ＋木の内容の一部を例示する図である。
【図５】  Ｂ＋木のインデクス配列の構成を示す図である。
【図６】  語の出現を検索する処理の手順を示すフローチャートである。
【図７】  複数の語による検索の処理手順を示すフローチャートである。
【図８】  ＡＮＤ演算の処理手順を示すフローチャートである。
【図９】  ＯＲ演算の処理手順を示すフローチャートである。
【図１０】  複数の文書を一括して登録する処理手順を示すフローチャートである。
【図１１】  或る１つの語の出現を登録する処理手順を示すフローチャートである。
【図１２】  第２実施例に係るキーの構成を示す図である。
【図１３】  第２実施例におけるＢ＋木の内容の一部を例示する図である。
【図１４】  第３実施例に係るキーの構成を示す図である。
【図１５】  第３実施例におけるＢ＋木の内容の一部を例示する図である。
【図１６】  本発明の第１実施例を用いた場合の登録文書数に対する新規文書登録に要する時間の推移を示したグラフである。
【図１７】  従来技術を用いた場合の登録文書数に対する新規文書登録に要する時間の推移を示したグラフである。
【符号の説明】
１・・・文書蓄積部、  ２・・・文書ソート部、  ４・・・インデクス登録部、
５・・・インデクス選択部、  ６・・・インデクス蓄積部、
８・・・検索実行部、
【図１】
0003849279.tif 000002
【図２】
0003849279.tif 000003
【図３】
0003849279.tif 000004
【図４】
0003849279.tif 000005
【図５】
0003849279.tif 000006
【図６】
0003849279.tif 000007
【図７】
0003849279.tif 000008
【図８】
0003849279.tif 000009
【図９】
0003849279.tif 000010
【図１０】
0003849279.tif 000011
【図１１】
0003849279.tif 000012
【図１２】
0003849279.tif 000013
【図１３】
0003849279.tif 000014
【図１４】
0003849279.tif 000015
【図１５】
0003849279.tif 000016
【図１６】
0003849279.tif 000017
【図１７】
0003849279.tif 000018