(57)【特許請求の範囲】
【請求項１】
指定された語から決定されるキーを用いて検索対象値を検索するために、キーと検索対象値とを対応させたインデクスをインデクス作成装置が作成するインデクス作成方法において、
前記インデクス作成装置の登録手段が、語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録する一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を当該文字列に代えて含ませたキー文字列と検索対象値との組からなるキーを記憶手段に登録することを特徴とするインデクス作成方法。
【請求項２】
請求項１に記載のインデクス作成方法において、
前記インデクス作成装置の登録手段は、前記閾値を越える長さの語と当該語を一意に特定するための登録番号とを対応させて登録テーブルに登録し、当該語から決定されるキー文字列に前記登録番号を付加することを特徴とするインデクス作成方法。
【請求項３】
請求項１又は請求項２に記載のインデクス作成方法において、
前記インデクス作成装置の登録手段は、前記閾値以下の長さの語から決定されるキー文字列と前記閾値を越える長さの語から決定されるキー文字列に各々を区別するフラグを付加することを特徴とするインデクス作成方法。
【請求項４】
請求項１乃至請求項３のいずれか１項に記載のインデクス作成方法において、
キー文字列と検索対象値との組からなるキーを登録するインデクスを複数のサブインデクスにより構成し、
登録するキーに対応する検索対象値に所定の関数を適用して決まる関数値と登録するキーに対応する語に所定の関数を適用して決まる関数値によって参照される二次元配列位置にサブインデクスを格納することを特徴とするインデクス作成方法。
【請求項５】
請求項４に記載のインデクス作成方法において、
キーを決定する語を含んでいる１つの文書の文書識別情報を検索対象値として用いることを特徴とするインデクス作成方法。
【請求項６】
請求項５に記載のインデクス作成方法において、
文書に一意に識別する文書識別番号を与え、
当該文書識別番号を文書識別情報として用いて、
文書識別情報に適用する関数として文書識別番号を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数とを用意し、
前記インデクス作成装置の登録手段は、文書における語の出現をその文書識別番号およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録することを特徴とするインデクス作成方法。
【請求項７】
請求項６に記載のインデクス作成方法において、
前記インデクス作成装置の登録手段は、複数の文書における語の出現を一括して登録する場合に、それらの文書の文書識別番号にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項８】
請求項５に記載のインデクス作成方法において、
語の文書における出現回数を文書識別情報として用いて、
文書識別情報に適用する関数として語の文書における出現回数を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、
語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数を用意し、
前記インデクス作成装置の登録手段は、或る文書における或る語の出現をその語の出現回数およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録することを特徴とするインデクス作成方法。
【請求項９】
請求項８に記載のインデクス作成方法において、
前記インデクス作成装置の登録手段は、複数の文書における語の出現を一括して登録する場合に、各語の出現回数にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項１０】
請求項５に記載のインデクス作成方法において、
語の文書における出現頻度を文書識別情報として用いて、
文書識別情報に適用する関数として語の文書における出現頻度を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、
語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数を用意し、
前記インデクス作成装置の登録手段は、或る文書における或る語の出現をその語の出現頻度およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録することを特徴とするインデクス作成方法。
【請求項１１】
請求項１０に記載のインデクス作成方法において、
前記インデクス作成装置の登録手段は、複数の文書における語の出現を一括して登録する場合に、各語の出現頻度にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項１２】
請求項７又は請求項９又は請求項１１に記載のインデクス作成方法において、
前記インデクス作成装置の登録手段は、１つのグループにまとめられた文書におけるすべての語の出現を登録する場合に、各語の出現を語にハッシュ関数を適用して決まるハッシュ値が同じになるものを一つのグループにまとめて、グループごとに語の出現を登録することを特徴とするインデクス作成方法。
【請求項１３】
請求項１２に記載のインデクス作成方法において、
主記憶装置に用意した少なくとも１つのサブインデクスが格納できるページキャッシュを用いることを特徴とするインデクス作成方法。
【請求項１４】
請求項５乃至請求項１３のいずれか１項に記載のインデクス作成方法において、
サブインデクスとしてＢ＋木構造を用いたことを特徴とするインデクス作成方法。
【請求項１５】
文書名と当該文書に含まれる語から決定されるキーとを対応させたインデクスをＢ＋木構造により構成して、指定された語から決定されるキーを用いて対応する文書名をインデクス検索装置が得るインデクス検索方法において、
文書名に一意に識別する文書識別情報を与え、
前記インデクス検索装置の記憶手段には、語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列と文書識別情報との組からなるキーが登録されている一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と文書識別情報との組からなるキーが登録されており、
前記インデクス検索装置の検索手段が、指定された語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列に検索範囲を指定する文書識別情報を結合したものをキーとして用いて記憶手段から当該キーと一致するキーに対応する文書識別情報を検索する一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列に前記文書識別情報を結合したものをキーとして用いて記憶手段から当該キーと一致するキーに対応する文書識別情報を検索することを特徴としたインデクス検索方法。
【請求項１６】
請求項１５に記載のインデクス検索方法において、
前記閾値を越える長さの語から決定されるキー文字列には当該語を一意に特定するための登録番号が付加されているとともに、当該登録番号が当該語と対応して前記インデクス検索装置の登録テーブルに登録されており、
前記インデクス検索装置の検索手段は、前記閾値を越える長さの語から決定されるキー文字列に検索範囲を指定する登録番号を付加したキーを用いて検索を行った後に、更に当該キーのキー文字列に付加された登録番号と対応して登録されている語を登録テーブルに基づいて特定し、特定した語と検索対象の語との対応に基づいて、検索された文書名集合から該当する文書名を特定することを特徴とするインデクス検索方法。
【請求項１７】
指定された語から決定されるキーを用いて検索対象値を検索するために、キーと検索対象値とを対応させたインデクスを作成するインデクス作成装置において、
インデクスを記憶する記憶手段と、
語の長さが設定された閾値以下であることに応じて当該語の文字列を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録する一方、語の長さが前記閾値を越えることに応じて当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録する登録手段と、
を備えたことを特徴とするインデクス作成装置。
【請求項１８】
指定された語から決定されるキーを用いて検索対象値を検索するために、キーと検索対象値とを対応させたインデクスの作成処理を、コンピュータに実行させるプログラムを当該コンピュータに読み取り可能に記憶した記憶媒体において、
前記プログラムは、語の長さが設定された閾値以下であることに応じて当該語の文字列を含むキー文字列と検索対象値との組からなるキーをインデクスメモリに登録する一方、語の長さが前記閾値を越えることに応じて当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と検索対象値との組からなるキーをインデクスメモリに登録する処理を、前記コンピュータに実行させることを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば文書に対する全文検索のためのインデクスを高速に生成し、また、当該インデクスを用いて高速な検索を実現する方法に関し、特に、検索等に用いるキーの構成に関する。
【０００２】
【従来の技術】
大量の文書に対する全文検索の方法として、シグネチャ・ファイルと呼ばれるデータ構造を用いる方法がある。特開平７-２４４６７１号公報に示されている方法では、文書における文字の出現をビットで表すインデクスを構成している。この方法では、格納されている文書数に影響されずに、比較的高速な検索が可能である。
しかしながら、いくつかの異なる語に対して１つのビットを割り当てているため、指定した以外の語が含まれている文書が検索される可能性があり、正確な検索が行えないという問題があった。また、生成や検索のアルゴリズムが複雑であり、既存のデータベース管理システムの上で実現することが困難であった。
【０００３】
このような問題に対して、文献「Compression and Fast Indexing for Multi-Gigabyte Text Databases」には、一般的なデータベース管理システムが提供しているハッシュ表やＢ＋木などのインデクス手法を用いて、高速な全文検索の機能を実現する方法が提案されている。この方法では、インデクスのキーとなる語と値となる文書に識別番号を割り付け、それらを圧縮して格納している。
これにより、検索に必要となるディスクの読み出しページ数を減らし、高速に検索が可能となる。また、異なる語に異なる識別番号を割り付けられるため、正確な検索が可能となる。なお、この文献は、この方法を用いて、約７０万件の文書に対する検索が高速に行えることを示している。
【０００４】
しかしながら、上記の文献で述べられている方法では、インデクスの新規作成や更新処理の性能が考慮されていないため、高い性能が得られないという問題があった。特に、更新時に或る語に対して同じ文書を重複して登録しないようにするための確認の処理は、文書識別番号の集まりに対する繰り返し処理により実現しなければならないため、効率よく実現することができない。
【０００５】
このような問題に対して、本出願人は特願平１０−２６６９１号に処理の効率化を図ることができるインデクス作成方法および検索方法を提案している。この方法では、Ｂ＋木のキーとして語の識別番号の後ろに文書の識別番号をつなげて配置したものを用いて、Ｂ＋木を、語の識別番号に或るハッシュ関数を適用して得られるハッシュ値と文書識別番号に別のハッシュ関数を適用して得られるハッシュ値などによって分割して二次元の配列に配置することにより、新規生成時や更新時には、文書識別番号のハッシュ値などが同じになるものをまとめて登録することで、書き込みページ数を少なくし、処理効率を高めている。
【０００６】
また、上記の文献で述べられている方法では、語の識別番号を必要とする。異なる語に異なる識別番号を与えるには、何らかの方法で語を管理する必要がある。１つの語の管理（追加、検索）に要する時間をＴｗとし、１個の文書の中に１００個の異なる語が含まれているとすると、例えば語の管理では、検索時には１Ｔｗ、登録時には１００Ｔｗの時間を要する。語の数が増加するに伴い、Ｔｗは増加し、その結果、インデクスの新規作成や更新処理の性能は大きく低下することとなる。
【０００７】
具体例として、インターネットのＷＷＷページに対する全文検索を行う場合などは、対象となる文書の数が数百万件となり、その文書中に出現する異なる語の数は数千万件となる。インターネットの場合には、固有名詞の豊富さや、スペル・ミスや、多言語での記述などの特性により、異なる語の数は文書数に比例して増加する傾向がある。数千万件の異なる語をＢ＋木で管理する場合、１つの語の追加や検索に要する時間Ｔｗとしては、０．１秒から１秒の時間が必要となる。これは、Ｂ＋木に対する１個の語の追加や検索処理が木の高さ＋１だけの回数のハードディスクに対するアクセスを必要とすることや、Ｂ＋木が巨大になるとディスクのメモリ中へのキャッシュの効果が得られず、ハードディスクに対するほとんどすべてのアクセスが実際にハードディスクを読み込む処理を必要とすることに起因する。
【０００８】
例えば、１千万件の異なる語をＢ＋木で管理する場合に、各ノードの分岐の数が５００であるとするとＢ＋木の高さはｌｏｇ500（１０，０００，０００）−１＝１．５９となり、１個の語と文書の組を追加、検索するために平均で約２．６回のディスク・アクセスが必要となる。ハードディスクを１回アクセスするために数十ミリ秒から数百ミリ秒かかるため、１個の語と文書の組の追加や検索には０．１秒から１秒の時間が必要となる。よって、１個の文書の中に１００個の異なる語が含まれているとすると、１個の文書を登録するために１００Ｔｗ、すなわち、１０秒から１００秒の時間を必要とすることになる。
【０００９】
【発明が解決しようとする課題】
ところで、上記従来例では語の識別番号の後ろに文書の識別番号をつなげて配置したものをＢ＋木のキーとして用いて検索等を行う構成を示したが、このように語に識別番号を与える代わりに、例えば語の文字列を用いてキーを作成することも考えられる。このように語の文字列を用いてキーを作成すれば、語と識別番号との対応関係を管理等する必要がなくなるため、例えば異なる語の数が多くなっても、語の管理に要する負担を少なくすることができると考えられる。
【００１０】
しかしながら、Ｂ＋木のキーの長さは一般に固定長であるため、例えば文書中で用いられる種々な長さの語のすべてに対応するためには、これらすべての語を含めることが可能なようにキーの長さを十分に長く取る必要がある。ところが、キーの長さが大きくなるとデータベースのサイズが大きくなってしまうため、ハードディスクを読み込む回数が多くなると同時にメモリ中のキャッシュのヒット率が低下し、全体的な性能が低下するといった不具合が生じてしまう。
また、例えばキーの長さを可変長にしたとしても、この場合には、処理が複雑になると同時にディスクのフラグメントが生じてしまうため、アクセス効率等が悪くなって、全体的な性能が低下するといった不具合が生じてしまう。
【００１１】
本発明は、このような従来の事情に鑑みなされたもので、語の文字列からキーを決定する仕方を工夫して、例えば大量の異なる語を含む大量の文書に対する全文検索のためのインデクスを高速に作成する方法を提供することを目的とする。また、本発明は、このように作成されたインデクスを用いて、高速な検索を実現する方法を提供することを目的とする。
また、本発明は、上記のような方法を実行するための装置や、また、プログラムを記憶した記憶媒体を提供することを目的とする。
【００１２】
【課題を解決するための手段】
上記目的を達成するため、本発明に係るインデクス作成方法では、指定された語から決定されるキーを用いて検索対象値を検索するために、キーと検索対象値とを対応させたインデクスをインデクス作成装置が作成するに際して、前記インデクス作成装置の登録手段が、語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録する一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を当該文字列に代えて含ませたキー文字列と検索対象値との組からなるキーを記憶手段に登録する。
このように、本発明では、前記閾値より長い語については当該文字列のハッシュ値を用いてキーを構成するため、例えばキーの長さを短い固定長に制限することができ、これにより、データベースサイズの増加を防ぎ、処理効率を高めることができる。
【００１３】
また、本発明では、前記インデクス作成装置の登録手段は、前記閾値を越える長さの語と当該語を一意に特定するための登録番号とを対応させて登録テーブルに登録し、当該語から決定されるキー文字列に前記登録番号を付加することで、前記閾値を越える長さの語の間でハッシュ値が重なってしまった場合でも、各語を区別できる構成とした。
また、本発明では、前記インデクス作成装置の登録手段は、前記閾値以下の長さの語から決定されるキー文字列と前記閾値を越える長さの語から決定されるキー文字列に各々を区別するフラグを付加することで、これらのキー文字列を区別できる構成とした。
【００１４】
また、本発明に係るインデクス作成方法では、上記のように語の長さに閾値を設定してインデクスを作成するに際して、キー文字列と検索対象値との組からなるキーを登録するインデクスを複数のサブインデクスにより構成し、登録するキーに対応する検索対象値に所定の関数を適用して決まる関数値と登録するキーに対応する語に所定の関数を適用して決まる関数値によって参照される二次元配列位置にサブインデクスを格納する。
ここで、本発明では、上記したキーと対応させる検索対象値として、例えば当該キーを決定する語を含んでいる１つの文書の文書識別情報を用いる。
【００１５】
上記したサブインデクスを構成する一例として、本発明では、文書に一意に識別する文書識別番号を与え、当該文書識別番号を文書識別情報として用いて、文書識別情報に適用する関数として文書識別番号を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数とを用意し、前記インデクス作成装置の登録手段は、文書における語の出現をその文書識別番号およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録する。
【００１６】
また、本発明では、このようなサブインデクスの構成を実施するに際して、前記インデクス作成装置の登録手段は、複数の文書における語の出現を一括して登録する場合に、それらの文書の文書識別番号にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録する。
このように、本発明では、例えばインデクスの新規生成時や更新時に、文書識別番号のハッシュ値が同じになるものをまとめて登録することができるため、書き込みページ数を少なくし、処理効率を高めることができる。
【００１７】
また、本発明では、前記インデクス作成装置の登録手段は、上記のようにして１つのグループにまとめられた文書におけるすべての語の出現を登録する場合に、各語の出現を語にハッシュ関数を適用して決まるハッシュ値が同じになるものを一つのグループにまとめて、グループごとに語の出現を登録することで、処理効率を更に高めることもできる。
【００１８】
また、上記したサブインデクスを構成する他の例として、本発明では、語の文書における出現回数を文書識別情報として用いて、文書識別情報に適用する関数として語の文書における出現回数を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数を用意し、前記インデクス作成装置の登録手段は、或る文書における或る語の出現をその語の出現回数およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録する。
【００１９】
この構成においても、上記と同様に、前記インデクス作成装置の登録手段は、複数の文書における語の出現を一括して登録する場合に、各語の出現回数にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録することで、処理効率を高めることができる。また、上記と同様に、前記インデクス作成装置の登録手段は、１つのグループにまとめられた文書におけるすべての語の出現を登録する場合に、各語の出現を語にハッシュ関数を適用して決まるハッシュ値が同じになるものを一つのグループにまとめて、グループごとに語の出現を登録することで、処理効率を更に高めることができる。
【００２０】
また、上記したサブインデクスを構成する他の例として、本発明では、語の文書における出現頻度を文書識別情報として用いて、文書識別情報に適用する関数として語の文書における出現頻度を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数を用意し、前記インデクス作成装置の登録手段は、或る文書における或る語の出現をその語の出現頻度およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録する。
【００２１】
この構成においても、上記と同様に、前記インデクス作成装置の登録手段は、複数の文書における語の出現を一括して登録する場合に、各語の出現頻度にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録することで、処理効率を高めることができる。また、上記と同様に、前記インデクス作成装置の登録手段は、１つのグループにまとめられた文書におけるすべての語の出現を登録する場合に、各語の出現を語にハッシュ関数を適用して決まるハッシュ値が同じになるものを一つのグループにまとめて、グループごとに語の出現を登録することで、処理効率を更に高めることができる。
また、本発明では、以上の登録に際して、例えば主記憶装置に用意した少なくとも１つのサブインデクスが格納できるページキャッシュを用いることで、処理の高速化を図った。
【００２２】
また、本発明では、以上に示したサブインデクスとしてＢ＋木構造を用いた。本発明では、文書識別情報をキーに付加することで、例えば異なる文書中の同じ語から決定されるキーを文書毎に区別することを可能にし、これにより、例えば異なる文書中の同じ語から決定されるキーが重なってしまってＢ＋木構造中で衝突してしまう（例えば両者の区別ができずに一方が他方に上書きされてしまう）ことを防ぐことができる。
なお、文書の一意な文書識別情報としては、例えば上記した文書識別番号や語の出現回数や語の出現頻度といった情報を用いることができる。
【００２３】
また、本発明に係るインデクス検索方法では、文書名と当該文書に含まれる語から決定されるキーとを対応させたインデクスをＢ＋木構造により構成して、指定された語から決定されるキーを用いて対応する文書名をインデクス検索装置が得る検索を行うに際して、文書名に一意に識別する文書識別情報を与え、  前記インデクス検索装置の記憶手段には、語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列と文書識別情報との組からなるキーが登録されている一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と文書識別情報との組からなるキーが登録されており、前記インデクス検索装置の検索手段が、指定された語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列に検索範囲を指定する文書識別情報を結合したものをキーとして用いて記憶手段から当該キーと一致するキーに対応する文書識別情報を検索する一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列に前記文書識別情報を結合したものをキーとして用いて記憶手段から当該キーと一致するキーに対応する文書識別情報を検索する。
【００２４】
このように、本発明では、例えば語の文字列或いは文字列のハッシュ値を含むキー文字列の後ろに検索範囲を指定する文書識別情報を結合したものをキーとして用いるため、或る文書における或る語の出現をＢ＋木インデクスに対する１回の検索で見つけることを実現することができる。
なお、文書識別情報としては、上記と同様に、例えば文書識別番号や語の出現回数や語の出現頻度といった情報を用いることができる。
【００２５】
また、本発明では、上記のインデクス検索方法において、前記閾値を越える長さの語から決定されるキー文字列に当該語を一意に特定するための登録番号を付加するとともに、当該登録番号と当該語とを対応させて前記インデクス検索装置の登録テーブルに登録しておき、上記検索に際して、前記インデクス検索装置の検索手段は、前記閾値を越える長さの語から決定されるキー文字列に検索範囲を指定する登録番号を付加したキーを用いて検索を行った後に、更に当該キーのキー文字列に付加された登録番号と対応して登録されている語を登録テーブルに基づいて特定し、特定した語と検索対象の語との対応に基づいて、検索された文書名集合から該当する文書名を特定する。
【００２６】
このように、本発明では、前記閾値を越える長さの語から決定されるキーを用いて検索を行うに際して、例えば同一の文書中の異なる語の間でキーを構成するハッシュ値が重なってしまった場合であっても、まず、登録番号以外のハッシュ値や文書識別情報から文書名集合を検索した後に、更に、検索した文書名集合から登録番号を用いて該当する文書名を特定するようにしたため、検索対象と一致する語を一意に特定することができる。
【００２７】
また、本発明は、以上に示した方法を実行する装置や、以上に示した方法を実行するためのプログラムを記憶した記憶媒体として構成することもできる。
例えば、本発明に係るインデクス作成装置では、指定された語から決定されるキーを用いて検索対象値を検索するために、キーと検索対象値とを対応させたインデクスを作成するに際して、記憶手段がインデクスを記憶し、登録手段が語の長さが設定された閾値以下であることに応じて当該語の文字列を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録する一方、語の長さが前記閾値を越えることに応じて当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録する。
【００２８】
また、本発明に係る記憶媒体では、指定された語から決定されるキーを用いて検索対象値を検索するために、キーと検索対象値とを対応させたインデクスの作成処理を、コンピュータに実行させるプログラムを当該コンピュータに読み取り可能に記憶した構成において、前記プログラムは、語の長さが設定された閾値以下であることに応じて当該語の文字列を含むキー文字列と検索対象値との組からなるキーをインデクスメモリに登録する一方、語の長さが前記閾値を越えることに応じて当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と検索対象値との組からなるキーをインデクスメモリに登録する処理を、前記コンピュータに実行させる。
【００２９】
【発明の実施の形態】
本発明に係る第１実施例を図面を参照して説明する。
図１には、本発明に係る方法を実行する装置の構成例を示してある。なお、この装置はコンピュータハードウエア資源を用いて、本発明を実施するためのプログラムを実行することにより構成されている。
【００３０】
文書蓄積部１はハードディスク装置等の外部メモリにより構成されており、この文書蓄積部１には、登録や検索の対象となる文書がその文書名や文書識別番号と対応付けられて格納されて管理される。なお、文書識別番号は文書を一意に識別する情報であり、例えば各文書毎に異なる番号が与えられている。
文書ソート部２は、インデクスの登録の対象となる文書の文書名を、あらかじめ定義されたハッシュ関数を文書識別番号に適用して得られるハッシュ値が同じになるものがまとまるようにソートする。
【００３１】
形態素解析部３は、指定された文書の全文を解析し、語の切り出しを行う。
キー文字列作成部４は、与えられた語に基づいてキー文字列を作成する。
ロングワード管理部５は、あらかじめ定められた閾値よりも長い語の一覧を保持するロングワードテーブルを管理する。本例では、ロングワードテーブルは、文書毎に用意される。また、文書毎のロングワードテーブルが保持する語には、一意な登録番号が付与される。
なお、上記したキー文字列や登録番号の具体例については後述する。
【００３２】
インデクス登録部６は、与えられた文書名の文書識別番号および語を得て、後述するインデクス選択部８の機能により選択されたＢ＋木構造に、キー文字列と文書識別番号とを結合した値をキーとして、文書内の語の出現を登録する。
インデクス蓄積部７はハードディスク装置等の外部メモリにより構成されており、このインデクス蓄積部７は、あらかじめ定められた大きさの二次元の配列（本例ではＤ×Ｗ、但し、Ｄ、Ｗは１以上の整数）上にＢ＋木を記憶する。また、インデクス蓄積部７は文書名と文書識別番号との対応関係も記憶している。
【００３３】
インデクス選択部８は、与えられた文書識別番号と語の文字列（例えば文字コード）に、それぞれあらかじめ定められたハッシュ関数を適用し、その結果得られたハッシュ値を用いてインデクス蓄積部７に格納されているインデクス表から語の出現を登録するＢ＋木の識別番号を選択する。
ここで、上記した文書ソート部２およびインデクス選択部８で用いられる文書識別番号に適用されるハッシュ関数Ｈｄや、語の文字列に適用されるハッシュ関数Ｈｗは、文書識別番号をｉd、語の文字列をｓとしたとき、それぞれ、０≦Ｈd（ｉd）＜Ｄ、０≦Ｈw（ｓ）＜Ｗ、となる整数をハッシュ値とするように定義される。
【００３４】
問い合わせ入力部９は、利用者からの検索要求を受け付け、例えば語をＡＮＤまたはＯＲで結合した検索式を生成する。
検索実行部１０は、与えられた検索式に含まれている語の文字列から、インデクス選択部８の機能により検索の対象となるＢ＋木を得て検索処理を行う。
結果出力部１１は、検索実行部１０により得られた検索結果をディスプレイ表示等して利用者に提示する。
【００３５】
図２には、インデクス蓄積部７に格納されているＢ＋木のキーの構成例を示してある。
同図に示されるように、このＢ＋木のキーは、キー文字列の後ろに文書識別番号を結合した構造となっており、本例では、キー文字列として９バイト、文書識別番号として４バイトの領域を割り当てている。
【００３６】
図３には、キー文字列の構成例を示してある。
同図に示されるように、キー文字列は、対象とする語の長さがあらかじめ定められた閾値より短いか或いは長いかによって、２通りの構造を成す。本例では、語の長さの閾値を８バイトに設定してあり、対象とする語の長さが８バイト以下（すなわち、閾値以下）の場合には、語の文字列をそのままキー文字列に含めて用いる一方、対象とする語の長さが８バイトを越える（すなわち、閾値を越える）場合には、語の文字列ｓにハッシュ関数Ｈｌを適用して得られるハッシュ値Ｈｌ（ｓ）をキー文字列に含めて用いる。
【００３７】
ここで、上記したハッシュ関数Ｈｌは、語の文字列をｓ、閾値をｎとしたとき、０≦Ｈｌ（ｓ）＜２8(n-1)、となる整数をハッシュ値とするように定義される。すなわち、ハッシュ関数Ｈｌの返す値（すなわち、ハッシュ値）のデータサイズは、閾値より１バイト少ないハッシュ値（本例の場合は７バイト）となる。
【００３８】
また、例えば語の長さが８バイトを越える場合に、異なる語の間でハッシュ値が重複する可能性があるので、本例では、ハッシュ値とロングワードテーブルにおけるその語の登録番号（本例では、後述するように１５ビットの登録番号を含んだ２バイトから成る登録番号部として図３に示してある）を結合したものをキー文字列とする。これにより、同じ文書中に現れる長い語の間でハッシュ値が重複しても、キー文字列が重複することが無くなる。また、実際のＢ＋木中では、上記図２に示したようにキー文字列に文書識別番号を結合したものをキーとするので、異なる文書に含まれる語の間でキー文字列が重複しても、Ｂ＋木のキーが重複することは無い。
【００３９】
また、長さが８バイト以下の語の文字列と長さが８バイトを越える語のハッシュ値との間で値が重なる可能性がある。そこで、本例では、語の長さが８バイト以下の場合には、語の文字列の８バイト目の値をキー文字列中の９バイト目にずらし、キー文字列中の８バイト目の値を０にする。例えば、対象とする語が’ｉｎｔｅｒｎｅｔ’である場合、キー文字列は、６９６Ｅ７４６５７２６Ｅ６５００７４（１６進）となる。
【００４０】
一方、長さが８バイトを越える語については、登録番号の最大値を３２７６７（すなわち、２15−１）とし、登録番号を格納する領域（登録番号部）の最上位ビットを常に１にする。これにより、語の長さが８バイト以下の場合にはキー文字列の先頭から８バイト目のデータの最上位ビットが必ず０になる一方、語の長さが８バイトを越える場合にはキー文字列の先頭から８バイト目のデータの最上位ビットが必ず１になるので、長さが閾値以下の語の文字列と長さが閾値を越える語のハッシュ値との間で値が重なっても、キー文字列が重複することが無くなる。
【００４１】
図４には、キー文字列を作成する処理の手順の一例を示してある。
すなわち、例えば与えられた語の長さが８バイト以下の場合には（ステップＳ１）、まず、キー文字列ｉｗに語の文字列ｓの先頭から７バイトの値をコピーし（ステップＳ２）、次に、キー文字列ｉｗの８バイト目に０をセットし（ステップＳ３）、次いで、キー文字列ｉｗの９バイト目に前記文字列ｓの８バイト目の値をコピーすることにより（ステップＳ４）、キー文字列ｉｗを作成する。
【００４２】
一方、与えられた語の長さが８バイトを越える場合には（ステップＳ１）、まず、キー文字列ｉｗに語の文字列ｓのハッシュ値Ｈｌ（ｓ）をコピーし（ステップＳ５）、次に、与えられた登録番号と１０００００００００００００００（２進）との論理和を取った値をキー文字列ｉｗの８バイト目以降にコピーすることにより（ステップＳ６）、キー文字列ｉｗを作成する。
なお、図４において、＜＜はビットを左にシフトする演算を示している。
【００４３】
このように、本例のインデクス作成方法では、語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列と値（本例では、当該キー文字列を決定する語を含んでいる１つの文書の文書識別情報）との組を登録することとする一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を当該文字列に代えて含ませたキー文字列と値（本例では、当該キー文字列を決定する語を含んでいる１つの文書の文書識別情報）との組を登録するようにしたため、例えばキーの長さを短い固定長に制限することができ、これにより、データベースサイズの増加を防ぎ、処理効率を高めることができる。
【００４４】
なお、語の長さの閾値としては、どのような値が設定されてもよいが、例えば長さが閾値以下の語の出現率や長さが閾値を越える語の出現率を考慮して、インデクスのサイズを小さくすることや、データの登録処理や検索処理にかかる時間を短くすることができるような値に設定されるのが好ましい。
【００４５】
また、上記のように本例では、設定された閾値を越える長さの語と当該語を一意に特定するための登録番号とを対応させて登録テーブル（本例では、ロングワードテーブル）に登録し、登録した登録番号を当該語から決定されるキー文字列に付加することにより、前記閾値を越える長さの語の間でハッシュ値が重なってしまった場合でも、各語を区別できる構成としている。
また、本例では、設定された閾値以下の長さの語から決定されるキー文字列と当該閾値を越える長さの語から決定されるキー文字列に各々を区別するフラグを付加することで、これらのキー文字列を区別できる構成としてある。なお、本例では、好ましい態様として、キー文字列中のハッシュ値と登録番号との境目となる先頭から８バイト目のデータの最上位ビットをフラグとして用いたが、フラグの構成としては特に限定はない。
【００４６】
図５には、Ｂ＋木から語の出現を検索する処理の手順の一例を示してある。
すなわち、或る語を含む文書を得る検索においては、まず、当該語からキー文字列ｉｗを作成し（ステップＳ１１）、その語の出現を含む全てのＢ＋木について、当該キー文字列ｉｗに検索範囲を指定する文書識別番号の最小値（ここでは０（３２ビット））を結合した値をｓｔａｒｔ点として設定する一方（ステップＳ１２）、検索範囲を指定する文書識別番号の最大値（ここではＦＦＦＦＦＦＦＦ（１６進））を結合した値をｅｎｄ点として設定する（ステップＳ１４）。
【００４７】
ここで、与えられた語の長さが閾値を越える場合には、語のハッシュ値に登録番号を付加した値がキー文字列ｉｗとして用いられるため、この登録番号についても、上記した文書識別番号の場合と同様に検索範囲を設定する。すなわち、本例では、検索範囲の最小値に対応するキー文字列ｉｗを作成する際に、語の検索範囲を指定する登録番号の最小値（ここでは０）を与える一方（ステップＳ１１）、検索範囲の最大値に対応するキー文字列ｉｗを作成する際に、語の検索範囲を指定する登録番号の最大値（ここでは７ＦＦＦ（１６進））を与え（ステップＳ１３）、これにより、キー文字列ｉｗに与えた登録番号の最小値から最大値までの範囲で検索が行われるようにしている。
【００４８】
そして、上記したｓｔａｒｔ点からｅｎｄ点までの間で検索を行うことにより（ステップＳ１５）、例えば与えられた語の長さが閾値（本例では８バイト）以下である場合には（ステップＳ１６）、その語に対するすべての出現を、文書識別番号の昇順に得ることができる（ステップＳ１７）。
一方、与えられた語の長さが閾値を越えている場合には（ステップＳ１６）、キー文字列ｉｗに与えた登録番号の検索範囲において該当する語の出現がすべて検索されるため、検索された語の出現の中から本当に検索対象に該当するものを特定することを行う。
【００４９】
具体的には、本例では、得られた検索結果から語の登録番号と文書識別番号を取り出して、当該文書識別番号と対応するロングワードテーブルを参照することで（ステップＳ１８）、当該登録番号と対応した語を特定し、例えば特定した語と検索対象の語とを比較することにより、検索対象の語が検索された文書に本当に含まれているかどうかを検証する（ステップＳ１９）。この結果、検索対象の語が文書に含まれていればその語の出現を返し（ステップＳ１７）、含まれていなければ例えばＮＵＬＬを返す（ステップＳ２０）。
なお、上記と同様に、図５において、＜＜はビットを左にシフトする演算を示している。
【００５０】
一例として、いくつかの文書に関する語の出現を登録した時点で、Ｂ＋木の一部の状態が図６に示されているようになっていたとする。この状態において、キー文字列が７４６５７３７４００００００００００（１６進）であるような語を含む文書を検索する場合には、キーの値が７４６５７３７４００００００００００００００００００（１６進）と７４６５７３７４００００００００００ＦＦＦＦＦＦＦＦ（１６進）の範囲にあるものを検索することにより、目的とする語の出現（Ｏ４、Ｏ５）を得られる。
【００５１】
また、キー文字列が７４６５７３７４００００００００００（１６進）である語が文書識別番号が７である文書に含まれているか否かを確認する場合には、７４６５７３７４０００００００００００００００００７（１６進）をキーとして、キーの値が一致するものを検索することで、語の出現（Ｏ５）を得ることができる。なお、本例では、語の出現には、例えば当該語がどの文書中のどのページやどの行にあるかといった情報や、当該語の出現回数や出現頻度等といった情報が含まれている。
【００５２】
このように、本例のインデクス検索方法では、例えば文書名と当該文書に含まれる語から決定されるキーとを対応させたインデクスをＢ＋木構造により構成して、語から決定されるキーを用いて対応する文書名を得る検索を行うに際して、文書名に一意に識別する文書識別情報（本例では文書識別番号）を与え、語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列に検索範囲を指定する文書識別情報を結合した値をキーとして用いる一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列に前記文書識別情報を結合した値をキーとして用いることにより、或る文書における或る語の出現をＢ＋木インデクスに対する１回の検索で見つけることを実現している。
【００５３】
また、本例では、前記閾値を越える長さの語から決定されるキー文字列には当該語を一意に特定するための登録番号が付加されているとともに、当該登録番号と当該語とが対応してロングワードテーブルに登録されており、上記検索では、前記閾値を越える長さの語から決定されるキー文字列に検索範囲を指定する登録番号を付加した値を用いて検索を行った後に、更に当該キー文字列に付加された登録番号と対応して登録されている語を特定し、特定した語と検索対象の語との対応に基づいて、検索された文書名集合から該当する文書名を特定しており、これにより、上記したように検索対象と一致する語を一意に特定することができる。
【００５４】
図７には、インデクス蓄積部７におけるＢ＋木の格納構造を示してある。
同図に示されるように、本例では、Ｄ×Ｗの二次元配列によりＤ×Ｗ個のサブインデクスが設けられており、各サブインデクスとしてＢ＋木構造が用いられている。例えば、文書識別番号がｉｄで且つ語の文字列がｓである或る語の出現は、Ｂ＋木（Ｈｗ（ｓ），Ｈｄ（ｉｄ））のサブインデクスに対応したＢ＋木に登録されている。
よって、文字列がｓである語の出現を検索する場合には、後述する図８に示されている手順で選択されたＢ＋木について上記図５に示した処理を実行する。
【００５５】
ここで、図８には、指定された或る一つの語が出現する文書を検索する処理の手順の一例を示してある。
すなわち、この処理では、まず、与えられた語の文字列ｓにハッシュ関数Ｈｗを適用して得られるハッシュ値Ｈｗ（ｓ）をｗに代入する（ステップＳ３１）。そして、変数ｉおよび変数ｒを０に初期化し（ステップＳ３２）、ｉを１つずつ増加させながら（ステップＳ３５）、ｉがＤとなるまで（ステップＳ３６）、Ｂ＋木（ｗ，ｉ）に対して語の検索を繰り返し行い（ステップＳ３３）、その結果を配列Ｒ［ｒ，ｒ＋ｒ’］に追加している（ステップＳ３４）。なお、ｒ’には検索結果数が代入され、ｉを１つ増加させる度毎にｒがｒ＋ｒ’に置き換えられる。
【００５６】
これにより、上記図７に示した二次元配列の或る一つの行のサブインデクスに記憶されているＢ＋木群に対する検索を行うことができる。このように検索を行う範囲を一つの行に限っても、目的とする語の出現はそれ以外のＢ＋木には含まれていないので、これにより見つかった文書のみに目的とする語が含まれていることになる。このように、本例の検索処理では、検索の対象となるＢ＋木が限定され、且つ各Ｂ＋木を順序良く利用するため、検索対象のサブインデクスを保持するキャッシュのヒット率を高めることができ、効率よく検索が実行できる。なお、本例の検索では、検索実行部１０が使用する主記憶装置のキャッシュに、少なくとも１つのＢ＋木サブインデクスが保持されるようになっている。
【００５７】
図９には、複数の文書の語の出現を一括して登録する処理の手順の一例を示してある。
すなわち、この処理では、まず、各文書を文書識別番号ｉｄにハッシュ関数Ｈｄを適用して得られるハッシュ値Ｈｄ（ｉｄ）によりＤ個のグループに分け、グループ分けされた文書をグループごとに各配列Ｇ（０）〜Ｇ（Ｄ−１）に格納する（ステップＳ４１）。続いて、変数ｄを０に初期化し（ステップＳ４２）、変数ｄを１つずつ増加させながら（ステップＳ４９）、変数ｄがＤとなるまで（ステップＳ５０）、各配列Ｇ（ｄ）について以下の登録処理を行う。
【００５８】
すなわち、この登録処理では、上記した各配列Ｇ（ｄ）について、その配列Ｇ（ｄ）に格納されている全ての文書から語の出現（文書と語の組）を取り出して（ステップＳ４３）、取り出した語の出現を各語の文字列ｓにハッシュ関数Ｈｗを適用して得られるハッシュ値Ｈｗ（ｓ）によりＷ個のグループに分け、グループ分けされた語の出現をグループごとに各配列Ｏ（０）〜Ｏ（Ｗ−１）に格納する（ステップＳ４４）。そして、変数ｗを０に初期化し（ステップＳ４５）、変数ｗを１つずつ増加させながら（ステップＳ４７）、変数ｗがＷとなるまで（ステップＳ４８）、配列Ｇ（ｄ）に格納されている各グループＯ（ｗ）について、そのグループＯ（ｗ）に属している語の出現を登録する処理を実施する（ステップＳ４６）。なお、語の出現を登録する処理の手順については、後述する図１０に示す。
【００５９】
上記の処理により、語の出現は上記図７に示された配列の左上から下方向に並んだＢ＋木サブインデクスに順に格納され、一番下のＢ＋木サブインデクスまで格納が終わると、一つ右の列について上から下方向に並んだＢ＋木サブインデクスに順に格納されるため、複数のＢ＋木サブインデクスを交互に参照することがなくなり、ページ・キャッシュのヒット率を高めることができる。
さらに、主記憶上に一つのＢ＋木サブインデクスの内容を保持できるだけの領域があれば、一つのＢ＋木サブインデクスに対する格納処理をすべて主記憶中で実行できるため、極めて高速に格納処理を実行できる。
【００６０】
図１０には、或る文書における或る語の出現を登録する処理の手順の一例を示してある。
すなわち、この処理では、例えば文書中の語の文字列ｓおよび当該文書の文書識別番号ｉｄを得て、それぞれにハッシュ関数Ｈｗ、Ｈｄを適用して得られるハッシュ値Ｈｗ（ｓ）、Ｈｄ（ｉｄ）をそれぞれの変数ｗ、ｄに保持する（ステップＳ６１、Ｓ６２）。
【００６１】
続いて、対象とする語に基づいてキー文字列ｉｗを作成する。ここで、語の長さが設定された閾値（本例では８バイト）以下の場合には（ステップＳ６３）、当該語の文字列を含んだキー文字列ｉｗを作成する一方（ステップＳ６４）、語の長さが前記閾値を越える場合には（ステップＳ６３）、当該語を文書に対応するロングワードテーブルに登録して登録番号を取得し（ステップＳ６７）、取得した登録番号と語に基づいてキー文字列ｉｗを作成する（ステップＳ６８）。
【００６２】
次いで、作成したキー文字列ｉｗの値を左に３２ビットシフトした値に、文書識別番号ｉｄの値を足したものを変数ｋに代入する（ステップＳ６５）。そして、上記図７に示された配列のサブインデクスＢ＋木（ｗ，ｄ）に、前記ｋをキーとして語の出現を登録する（ステップＳ６６）。
なお、上記と同様に、図１０において、＜＜はビットを左にシフトする演算を示している。
【００６３】
このように、本例では、指定された語から決定されるキー文字列を含むキーを用いて値（本例では、当該キー文字列を決定する語を含んでいる１つの文書の文書識別情報）を検索するためにキーと値（本例では、キー文字列を決定する語を含んでいる１つの文書の文書識別情報）とを対応させたインデクスを作成するに際して、キー文字列と値（本例では、当該キー文字列を決定する語を含んでいる１つの文書の文書識別情報）との組を登録するインデクスを複数のサブインデクスにより構成し、登録する値（本例では、キー文字列を決定する語を含んでいる１つの文書の文書識別情報）に所定の関数を適用して決まる関数値と語（本例では語の文字列）に所定の関数を適用して決まる関数値によって参照される二次元配列位置にサブインデクスを格納する構成を用い、また、サブインデクスとしてＢ＋木構造を用いることで、処理の効率化を図っている。
【００６４】
なお、具体的には、本例では上記したように、文書に適用する関数として文書識別番号を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数とを用意し、文書における語の出現をその文書識別番号およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録するようにした。
【００６５】
そして、本例では、このようなサブインデクスの構成を用いて、複数の文書における語の出現を一括して登録する場合に、それらの文書の文書識別番号にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて、グループごとに語の出現を登録することにより、インデクスの新規生成時や更新時における書き込みページ数を少なくし、処理効率を高めた。
更に、本例では、上記のようにして１つのグループにまとめられた文書におけるすべての語の出現を登録する場合に、各語の出現を語にハッシュ関数を適用して決まるハッシュ値が同じになるものを一つのグループにまとめて、グループごとに語の出現を登録することにより、処理効率を更に高めた。
【００６６】
また、本例では、サブインデクスとしてＢ＋木構造を用いるに際して、キーに当該キーと対応する文書の一意な識別情報（本例では文書識別情報）を付加することにより、例えば異なる文書中の同じ語から決定されるキー文字列が重なってしまった場合であっても、これらのキー文字列を文書識別情報により区別可能な構成とすることで、両者がＢ＋木構造中で衝突してしまうことを防いだ。
また、本例では、上記したように、主記憶装置に用意した少なくとも１つのサブインデクスが格納できるページキャッシュを用いているため、処理の高速化を図ることができる。
【００６７】
以上のように、本例のインデクス作成方法やインデクス検索方法では、例えば大量の異なる語を含む大量の文書に対する全文検索のためのインデクスを作成する処理や、作成したインデクスを用いて検索を行う処理を実行するに際して、語の文字列或いは当該文字列のハッシュ値を用いてキーを作成するようにしたため、異なる語の数によって受ける影響を小さくすることができ、例えば数百万件の文書に対する全文検索のためのインデクスを高速に生成、更新、検索することができる。
【００６８】
また、本例の方法では、例えば各語と識別番号との対応関係を管理するといったことを行わずとも、設定された閾値を越える長さの語に適用するハッシュ関数や登録番号を記憶等しておけば、語とキーとの対応が付けられるため、例えば異なる語の数が多くなっても語の管理に要する負担を少なくすることができ、これにより、１つの語の管理（追加、検索）に要する時間Ｔｗをゼロに近づけることができる。
【００６９】
また、本例の方法では、上記したサブインデクスの構成やＢ＋木の構造を採用しているため、文書の格納処理や検索処理に必要となる更新ページ数や読み出しページ数を削減することができ、登録処理や検索処理を高速に実行することができる。なお、本例では、サブインデクスとしてＢ＋木を用いることで、例えば木のルートからの検索を短いパスで実現することや、新たな語の出現を容易に追加等することができる。
【００７０】
図１１には、本発明の第２実施例として、Ｂ＋木インデクスの縦方向の分割に、語の出現回数に或る関数を適用した関数値を用いる場合のキーの構成例を示してある。  同図に示されるように、本例のキーは、キー文字列の後ろに語の出現回数を整数であらわした値を結合した構造であり、キー文字列として９バイト、出現回数として４バイトの領域を割り当てている。
【００７１】
図１２には、上記図１１に示したキーの構成を用いて、語の出現をＢ＋木に登録した状態の一例を示してある。
上記図１２に示されているように、同じ語に対する複数の異なる語の出現が、例えば語の出現回数の多い順にならべられる。これにより、検索処理において、検索の結果を語の出現回数の多い順に取り出すことが容易となる。
【００７２】
なお、本第２実施例における語の出現を検索する処理手順は、上記図８に示した第１実施例における語の出現を検索する処理と同じである。また、語の出現を登録する処理手順は、上記図９に示した処理手順において文書識別番号を用いて文書をグループ分けしている処理（ステップＳ４１）を語の出現回数を用いて語の出現をグループ分けする処理に置き換え、また、上記図１０に示した処理手順において文書識別番号の値を用いてキーとなる値を生成している処理（ステップＳ６２、Ｓ６５）を語の出現回数の値を用いてキーとなる値を生成する処理に置き換えること等で実現できる。
【００７３】
このように、本発明では、文書中の語の出現に適用する関数としてその語の文書における出現回数を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数を用意し、或る文書における或る語の出現をその語の出現回数およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録するといった構成を用いることもできる。
【００７４】
この構成においても、上記第１実施例の場合と同様に、複数の文書における語の出現を一括して登録する場合に、各語の出現回数にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめてグループごとに語の出現を登録することや、更に、各語の出現を語にハッシュ関数を適用して決まるハッシュ値が同じになるものを一つのグループにまとめてグループごとに語の出現を登録することにより、処理効率を高めることができる。
【００７５】
図１３には、本発明の第３実施例として、Ｂ＋木の縦方向の分割に語の出現頻度に或る関数を適用した関数値を用いる場合のキーの構成例を示してある。
同図に示されるように、本例のキーは、キー文字列の後ろに語の出現頻度を整数であらわした値を結合した構造であり、キー文字列として９バイト、出現頻度として１バイトの領域を割り当てている。
なお、本例では、或る語の出現の出現頻度は、その語がその文書に現れた回数をその文書の総語数で割って１００を掛けた値であらわす。
【００７６】
図１４には、上記図１３に示したキーの構成を用いて、語の出現をＢ＋木に登録した状態の一例を示してある。
上記図１４に示されているように、同じ語に対する複数の異なる語の出現が、例えば語の出現頻度の高い順にならべられる。これにより、検索処理において、検索の結果を語の出現頻度の高い順に取り出すことが容易となる。
【００７７】
なお、本第３実施例における語の出現を検索する処理手順は、上記図８に示した第１実施例における語の出現を検索する処理と同じである。また、語の出現を登録する処理手順は、上記図９に示した処理手順において文書識別番号を用いて文書をグループ分けしている処理（ステップＳ４１）を語の出現頻度を用いて語の出現をグループ分けする処理に置き換え、また、上記図１０に示した処理手順において文書識別番号の値を用いてキーとなる値を生成している処理（ステップＳ６２、Ｓ６５）を語の出現頻度の値を用いてキーとなる値を生成する処理に置き換えること等で実現できる。
【００７８】
このように、本発明では、文書中の語の出現に適用する関数としてその語の文書における出現頻度を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語に適用する関数として語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数を用意し、或る文書における或る語の出現をその語の出現頻度およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録するといった構成を用いることもできる。
【００７９】
この構成においても、上記第１実施例や第２実施例の場合と同様に、複数の文書における語の出現を一括して登録する場合に、各語の出現頻度にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめてグループごとに語の出現を登録することや、更に、各語の出現を語にハッシュ関数を適用して決まるハッシュ値が同じになるものを一つのグループにまとめてグループごとに語の出現を登録することにより、処理効率を高めることができる。
【００８０】
ここで、本発明は、以上に示した方法を実行する装置として把握することもできる。
一例として、本発明に係るインデクス作成装置では、指定された語から決定されるキーを用いて検索対象値を検索するためにキーと検索対象値とを対応させたインデクスを作成するに際して、ハードディスク等から成る記憶手段がインデクスを記憶し、登録手段が語の長さが設定された閾値以下であることに応じて当該語の文字列を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録する一方、語の長さが前記閾値を越えることに応じて当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と検索対象値との組からなるキーを記憶手段に登録することにより、処理の効率化を図ることができる。
【００８１】
また、上記したように以上では、上記図１に示した装置に備えられた各機能手段により行われる処理は、例えばプロセッサやメモリ等を備えたハードウエア資源においてプロセッサが制御プログラムを実行することにより構成されるが、本発明では、これらの各機能手段を独立したハードウエア回路として構成してもよい。
また、本発明は上記の制御プログラムを格納したフロッピーディスクやＣＤ−ＲＯＭ等のコンピュータにより読み取り可能な記憶媒体として把握することもでき、当該制御プログラムを記憶媒体からコンピュータに入力してプロセッサに実行させることにより、本発明に係る処理を遂行させることができる。
【００８２】
一例として、本発明に係る記憶媒体では、指定された語から決定されるキーを用いて検索対象値を検索するためにキーと検索対象値とを対応させたインデクスの作成処理を、コンピュータに実行させるプログラムを当該コンピュータに読み取り可能に記憶した構成において、前記プログラムが、語の長さが設定された閾値以下であることに応じて当該語の文字列を含むキー文字列と検索対象値との組からなるキーをインデクスメモリに登録する一方、語の長さが前記閾値を越えることに応じて当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を含むキー文字列と検索対象値との組からなるキーをインデクスメモリに登録する処理を前記コンピュータに実行させることにより、処理の効率化を図ることができる。
【００８３】
なお、上記したインデクスメモリとしては、例えば上記プログラムを格納した記憶媒体とは別個なハードディスク装置等として設けることができるばかりでなく、例えば当該記憶媒体の中に設けられてもよい。また、インデクスメモリを記憶媒体中に設ける場合には、例えばキーと検索対象値とを対応させたインデクスを上記プログラム中に記憶してもよく、また、このようなインデクスを上記プログラムとは別に記憶していてもよい。
【００８４】
【発明の効果】
以上説明したように、本発明によると、指定された語から決定されるキーを用いて検索対象値を検索するためにキーと検索対象値とを対応させたインデクスを作成するに際して、語の長さが設定された閾値以下の場合には当該語の文字列を含むキー文字列と検索対象値との組からなるキーを登録する一方、語の長さが前記閾値を越える場合には当該語の文字列に所定のハッシュ関数を適用して決まるハッシュ値を当該文字列に代えて含ませたキー文字列と検索対象値との組からなるキーを登録するようにしたため、例えば異なる語の数が多い場合でも、キーの長さを短い固定長に制限することができ、これにより、データベースサイズの増加を防ぎ、処理効率を高めることができる。
【００８５】
また、本発明では、前記閾値を越える長さの語を一意に特定するための登録番号を当該語から決定されるキー文字列に付加することや、前記閾値以下の長さの語から決定されるキー文字列と前記閾値を越える長さの語から決定されるキー文字列に各々を区別するフラグを付加することを行うようにしたため、登録時や検索時において異なる語から決定されるキーを確実に区別することができる。
【００８６】
また、本発明では、キーと検索対象値との組を登録するインデクスを複数のサブインデクスにより構成し、例えば文書を特定する文書識別番号や語の出現回数や語の出現頻度を二次元配列の一の方向の位置を示すハッシュ値にマップするハッシュ関数と、語を二次元配列の他の方向の位置を示すハッシュ値にマップするハッシュ関数とを用意して、文書における語の出現をその文書識別番号等およびその語の各々にハッシュ関数を適用して得られたハッシュ値を用いて対応するサブインデクスに登録するようにしたため、例えば文書識別番号等や語にハッシュ関数を適用して決まるハッシュ値が同じになるものを１つのグループにまとめて処理することで、複数の文書における語の出現を一括して登録する処理等の効率を高めることができる。
【００８７】
また、本発明では、例えば主記憶装置に用意した少なくとも１つのサブインデクスが格納できるページキャッシュを用いることで、処理の高速化を実現した。
また、本発明では、サブインデクスとしてＢ＋木構造を用いることで、インデクス更新処理や検索処理の高速化を図るとともに、キーに当該キーと対応する文書の一意な文書識別情報を付加することで、或る文書における或る語の出現をＢ＋木インデクスに対する１回の検索で見つけること等を実現した。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る装置の構成例を示す図である。
【図２】本発明の第１実施例に係るキーの構成例を示す図である。
【図３】キー文字列の構成例を示す図である。
【図４】キー文字列を作成する処理の手順の一例を示すフローチャートである。
【図５】語の出現を検索する処理の手順の一例を示すフローチャートである。
【図６】Ｂ＋木の内容の一部を例示する図である。
【図７】Ｂ＋木のインデクス配列の構成例を示す図である。
【図８】語の出現を検索する処理の手順の一例を示すフローチャートである。
【図９】複数の文書の語の出現を一括して登録する処理の手順の一例を示すフローチャートである。
【図１０】或る一つの語の出現を登録する処理の手順の一例を示す図である。
【図１１】本発明の第２実施例に係るキーの構成例を示す図である。
【図１２】本発明の第２実施例におけるＢ＋木の内容の一部を例示する図である。
【図１３】本発明の第３実施例に係るキーの構成例を示す図である。
【図１４】本発明の第３実施例におけるＢ＋木の内容の一部を例示する図である。
【符号の説明】
１・・文書蓄積部、  ２・・文書ソート部、  ３・・形態素解析部、
４・・キー文字列作成部、  ５・・ロングワード管理部、
６・・インデクス登録部、  ７・・インデクス蓄積部、
８・・インデクス選択部、  ９・・問い合わせ入力部、
１０・・検索実行部、  １１・・結果出力部、
【図１】
0003859044.tif 000002
【図２】
0003859044.tif 000003
【図３】
0003859044.tif 000004
【図４】
0003859044.tif 000005
【図５】
0003859044.tif 000006
【図６】
0003859044.tif 000007
【図７】
0003859044.tif 000008
【図８】
0003859044.tif 000009
【図９】
0003859044.tif 000010
【図１０】
0003859044.tif 000011
【図１１】
0003859044.tif 000012
【図１２】
0003859044.tif 000013
【図１３】
0003859044.tif 000014
【図１４】
0003859044.tif 000015