(57)【特許請求の範囲】
【請求項１】
記憶手段をもつコンピュータの処理によって、個々の文書にキーワードが関連付けられた、複数の文書からなるデータベースのインデックスを作成する方法であって、
前記データベースを、複数の部分文書集合に分割するステップと、
前記データベースに含まれるキーワードのハッシュ値を特定の数で割った余りの数（以下、キーワード・グループ番号と呼ぶ）を計算する処理を用いるステップであって、前記個々の部分文書集合毎に、該部分文書集合に含まれる個々の文書を順次読み込んで、該個々の文書に関連付けられたキーワードについて、該計算されたキーワード・グループ番号毎に個別の第１の部分インデックス・ファイルを作成し、前記記憶手段に書き出すステップと、
前記第１の部分インデックス・ファイルを前記記憶手段から読み込んで、同一のキーワード・グループ番号をもつもの同士でマージすることにより、複数の第２の部分インデックス・ファイルを作成し、前記記憶手段に書き込むステップと、
前記複数の第２の部分インデックス・ファイルを前記記憶手段から読み込んで、マージすることにより、前記データベースに対応するインデックスを作成し、前記記憶手段に書き出すステップとを有する、
方法。
【請求項２】
前記データベースの個々の文書及び前記キーワードにはそれぞれ、前記データベースを通して一意的な文書ｉｄ及びキーワードｉｄが付与される、請求項１に記載の方法。
【請求項３】
前記第１の部分インデックス・ファイルが、キーワードｉｄから文書ｉｄへのポインタを含むＫ２Ｄインデックスを有する、請求項２に記載の方法。
【請求項４】
前記第１の部分インデックス・ファイルが、文書ｉｄからキーワードｉｄへのポインタを含むＤ２Ｋインデックスを有する、請求項２に記載の方法。
【請求項５】
前記キーワードと前記キーワードｉｄの対応を示すＫＷインデックスを作成し、前記記憶手段に書き出すステップをさらに有する、請求項２に記載の方法。
【請求項６】
前記ＫＷインデックスは、前記部分文書集合の個々の文書を順次読み出して、前記キーワード・グループ番号毎に、前記データベースに対応する単一のインデックス・ファイルとして順次書き出される、請求項５に記載の方法。
【請求項７】
記憶手段をもつコンピュータの処理によって、個々の文書にキーワードが関連付けられた、複数の文書からなるデータベースのインデックスを作成するために、
前記コンピュータをして、
前記データベースを、複数の部分文書集合に分割するステップと、
前記データベースに含まれるキーワードのハッシュ値を特定の数で割った余りの数（以下、キーワード・グループ番号と呼ぶ）を計算する処理を用いるステップであって、前記個々の部分文書集合毎に、該部分文書集合に含まれる個々の文書を順次読み込んで、該個々の文書に関連付けられたキーワードについて、該計算されたキーワード・グループ番号毎に個別の第１の部分インデックス・ファイルを作成し、前記記憶手段に書き出すステップと、
前記第１の部分インデックス・ファイルを前記記憶手段から読み込み、同一のキーワード・グループ番号をもつもの同士でマージすることにより、複数の第２の部分インデックス・ファイルを作成し、前記記憶手段に書き出すステップと、
前記複数の第２の部分インデックス・ファイルを前記記憶手段から読み込み、マージすることにより、前記データベースに対応するインデックスを作成し、前記記憶手段に書き出すステップとを実行させる、
プログラム。
【請求項８】
前記データベースの個々の文書及び前記キーワードにはそれぞれ、前記データベースを通して一意的な文書ｉｄ及びキーワードｉｄが付与される、請求項７に記載のプログラム。
【請求項９】
前記第１の部分インデックス・ファイルが、キーワードｉｄから文書ｉｄへのポインタを含むＫ２Ｄインデックスを有する、請求項８に記載のプログラム。
【請求項１０】
前記第１の部分インデックス・ファイルが、文書ｉｄからキーワードｉｄへのポインタを含むＤ２Ｋインデックスを有する、請求項８に記載のプログラム。
【請求項１１】
前記キーワードと前記キーワードｉｄの対応を示すＫＷインデックスを作成し、前記記憶手段に書き出すステップをさらに有する、請求項８に記載のプログラム。
【請求項１２】
前記ＫＷインデックスは、前記部分文書集合の個々の文書を順次読み込んで、前記キーワード・グループ番号毎に、前記データベースに対応する単一のインデックス・ファイルとして順次書き出される、請求項１１に記載のプログラム。
【請求項１３】
個々の文書にキーワードが関連付けられた、複数の文書からなるデータベースのインデックスを作成するためのシステムであって、
記憶手段と、
主記憶と、
前記データベースを、複数の部分文書集合に分割する手段と、
前記データベースに含まれるキーワードのハッシュ値を特定の数で割った余りの数（以下、キーワード・グループ番号と呼ぶ）を計算する処理を用いる手段であって、前記個々の部分文書集合毎に、該部分文書集合に含まれる個々の文書を順次読み込んで、該個々の文書に関連付けられたキーワードについて、該計算されたキーワード・グループ番号毎に個別の第１の部分インデックス・ファイルを作成し、前記記憶手段に書き出す手段と、
前記第１の部分インデックス・ファイルを前記記憶手段から前記主記憶に読み込み、同一のキーワード・グループ番号をもつもの同士でマージすることにより、複数の第２の部分インデックス・ファイルを作成し、前記記憶手段に書き出す手段と、
前記複数の第２の部分インデックス・ファイルを前記記憶手段から前記主記憶に読み込みマージすることにより、前記データベースに対応するインデックスを作成し、前記記憶手段に書き出す手段とを有する、
システム。
【請求項１４】
前記データベースの個々の文書及び前記キーワードにはそれぞれ、前記データベースを通して一意的な文書ｉｄ及びキーワードｉｄが付与される、請求項１３に記載のシステム。
【請求項１５】
前記第１の部分インデックス・ファイルが、キーワードｉｄから文書ｉｄへのポインタを含むＫ２Ｄインデックスを有する、請求項１４に記載のシステム。
【請求項１６】
前記第１の部分インデックス・ファイルが、文書ｉｄからキーワードｉｄへのポインタを含むＤ２Ｋインデックスを有する、請求項１４に記載のシステム。
【請求項１７】
前記キーワードと前記キーワードｉｄの対応を示すＫＷインデックスを作成し、前記記憶手段に書き出すステップをさらに有する、請求項１４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、テキストマイニング等に使用されるデータベースに関し、特に、データベースのインデックス作成システム、方法及びプログラムに関するものである。
【背景技術】
【０００２】
テキストマイニングの典型的な応用例では、テキストマイニングのシステムに対話的に検索条件を与え、その検索条件に相関の高いキーワードを見出す、ということが必要になる。
【０００３】
例えば、ＰＣコールセンターのコールログを対象とした分析をする際、特に、ある特定の製品に頻出する問題を見つけたいとする。この場合、その製品番号を絞込条件として検索を行い、ヒットした文書中のキーワードを数え上げることにより、その製品と一緒に言及されることの多いキーワードを見つけることになる。
【０００４】
また、テキストマイニング・システムでは、キーワードにカテゴリを予め付与することもできる。例えば、「発熱する」というキーワードに対して、「問題表現」というカテゴリを付与しておく。すると、キーワードの数え上げを、このカテゴリに属するキーワードのみに対して行うことによって、問題を効率よく見つけることが可能となる。
【０００５】
このように、対話的に検索条件を与えて、その結果を確認するようなテキストマイニングの応用例では、動的に与えられた文書集合中のキーワードの数え上げが必須である。数え上げ計算を高速に行うためのインデックス構造として、リレーショナル・データベースを利用することもできるが、検索条件とキーワードの出現頻度の相関分析を行う目的には、十分なパフォーマンスを提供するものではない。
【０００６】
そこで、このような目的に適合する、高速にマイニングを実行するためのインデックス構造及びアルゴリズムとして、本出願人に係る、特願２００５−３４９７１７号明細書に記載の技術がある。しかし、特願２００５−３４９７１７号明細書に記載されている技術だと、大規模データに対して、そこに記載されている索引構造を構築することが難しい。その主要な理由は、キーワードと、テキストマイニング・データベースに含まれる文書との関係を行列構造にマップする場合、データの規模が大きくなってその結果、データベースに含まれる文書の数が増えてくると、主記憶に全ての情報を保持することが出来なくなるからである。
【０００７】
すなわち、より具体的に述べると、高速にインデックスを構築するためには、キーワード文字列と、数値ＩＤとの対応を保持するマップが、主記憶上になくてはならない。また、キーワードから、対応する文書のポスティング・リスト(posting list、すなわち、文書ＩＤの配列）を検索する構造を、キーワードに対して何らかの順序（例えば、頻度順）で整列する必要があるが、この場合も、キーワード集合を保持するハッシュ構造を主記憶上に保持できないと、文書単位で分割されたインデックスのマージが困難になる。このことから、インデックス作成に必要なキーワードが全て主記憶上に保持できるような主記憶のサイズであることが本質的である。すると、主記憶のサイズは、いくら大きくても限界がある訳だから、主記憶のサイズにより、文書の集合に対してインデックス構造を作成できる、文書の数の限界が決まってくる。
【０００８】
ところで、米国特許第６５５３３８５号及び、http://uima-framework.sourceforge.net/ には、文書集合の各文書に自然言語処理などの技術を適用して情報を抽出し、所定のデータ構造にストアする、というフレームワークが記載されている。しかし、この開示技術も、一文書を処理して得られた情報を逐次的に処理する大規模データに関して、効率的にストアする技法については、示唆するものではない。
【０００９】
特開平９−２１２５２８号公報は、データベースを複数のデータ・セグメントに分割するステップを備える。これにおいて、各データ・セグメントは、データベース内の選定されたフィールドにて互いに異なるバリューを有するレンジに対応し、種々の記憶装置内にデータ・セグメントの各々を記憶するステップと、対応する各データ・セグメントを識別するためのセグメント・インデックスを記憶するステップと、選定されたフィールドの複数のレンジに対応するエントリを有するレンジ・インデックスを記憶するステップとを備え、レンジ・インデックス内の各エントリは、複数のデータ・セグメントに対し、当該レンジに対応するセグメント・インデックスを識別する。
【００１０】
特開２００３−２７１６４８号公報は、検索対象文書を複数のグループに分割し、グループのそれぞれについて、当該グループと、これに含まれる検索対象文書に出現するキーワードと、当該キーワードが出現する検索対象文書の数と、の情報を対応付けて記憶することを開示する。
【００１１】
このように、特開平９−２１２５２８号公報及び、特開２００３−２７１６４８号公報は、大規模な検索に対応するために、データベースを複数に分割して負荷分散することによって、検索を高速化することを教示する。しかし、ここに教示されている方法は、データベース検索に係るものであって、大規模テキストマイニング・データベースのインデックス作成に適用することはできない。
【特許文献１】特願２００５−３４９７１７号明細書
【特許文献２】米国特許第６５５３３８５号
【特許文献３】特開平９−２１２５２８号公報
【特許文献４】特開２００３−２７１６４８号公報
【非特許文献１】http://uima-framework.sourceforge.net/
【発明の開示】
【発明が解決しようとする課題】
【００１２】
この発明の目的は、コンピュータの主記憶の容量などの物理的制約に拘わらず、テキストマイニング・システムなどに使用される大規模データベースの文書に含まれるキーワードのインデックス作成を高速に処理することを可能ならしめるシステム、方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１３】
上記目的は、本発明に従い、データベースの文書を複数に分割し、その分割した各々の文書の集合に対して、インデックス作成処理を行って、部分インデックス・ファイルを作成し、そうして作成したインデックス・ファイルを、分割前のもとのデータベース全体のインデックスとなるようにマージすることによって達成される。
【００１４】
なお、本発明の文脈で、キーワードとは、単語やフレーズ等の抽出情報を表現する一般の文字列を示し、文書とは、その各々がいくつかのキーワードを含むある集計単位であり、テキストマイニング・システムなどに使用される大規模データベースは、そのような文書の有限集合を含む。そのような文書の単位の例として、コールセンターにおける一回の電話のログ、メールデータへースの１つのメール、Ｗｅｂデータにおける１つのＨＴＭＬファイル、ブログにおける１つの記事、などが挙げられる。
【００１５】
さて、本発明によれば、先ず、文書集合の全体は、互いに共通部分のない部分集合の和に分解される。
次に、上記で分割された各部分集合に対して、その部分集合内で出現するキーワードの集合を、キーワードのハッシュ値をある固定の整数値で割った余りでグルーピングし、これにより、各グループに対するインデックス・ファイルが作成される。この固定の整数値をグループ数と呼び、キーワードのハッシュ値を、そのグループ数で割った余りをグループ番号と呼ぶ。なお、グループ数は、文書集合の全体を分けた部分集合の数とは独立に、事前に決めておく。
次に、そのようにして文書の各部分集合毎に用意されたインデックス・ファイルについて、同じグループ番号をもつものどおしが、マージされる。これによって、個々のグループ番号に対応する統合されたインデックス・ファイルが生成される。しかし、そのようなインデックス・ファイルは、グループ番号の個数だけ存在し、まだ、文書集合の全体に対応するインデックスになっていない。そこで次に、そのようなグループ番号の個数だけあるインデックス・ファイルをさらにマージして、文書集合の全体に対応するインデックス・ファイルが生成される。
【発明の効果】
【００１６】
この発明によれば、文書集合の全体を分割し、その分割された部分集合において、キーワードに基づくグループ数の概念によりさらに処理を細分し、その細分化された単位で部分的なインデックスを生成するようにすることによって、限られた主記憶容量の範囲内でも、インデックス作成のためのキーワード・データをすべて主記憶容量にロードして高速処理することが可能となる。さらに、その後の統合したインデックス・ファイルを作成する処理は、大量の主記憶容量を要する訳ではないので、限られた主記憶容量のコンピュータ・システムでも、大規模なテキストマイニング・システムのデータベースのインデックスを高速に作成することが可能ならしめられる、という顕著な効果が得られる。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【００１８】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＰｅｎｔｉｕｍ（商標）  ４、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量をもつものである。ハードディスク・ドライブ１０８は、テキストマイニング用大規模データベースとそのインデックス・ファイルを格納するために、２００ＧＢ以上の容量をもつものであることが望ましい。
【００１９】
ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システム及びテキストマイニング用大規模データベースのデータが、予め格納されている。オペレーティング・システムは、Ｌｉｎｕｘ（商標）、マイクロソフト社のＷｉｎｄｏｗｓ  ＸＰ（商標）、Ｗｉｎｄｏｗｓ（商標）２０００、アップルコンピュータのＭａｃ  ＯＳ（商標）などの、ＣＰＵ１０４に適合する任意のものでよい。
【００２０】
ハードディスク・ドライブ１０８にはまた、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などの任意のプログラム言語処理系も格納されている。このプログラム言語処理系は、以下で説明する、テキストマイニング用データベースのインデックス作成のためのツールを作成し、維持するために使用される。使用するプログラム言語としては、ハッシュ・テーブルをサポートするものであことが望ましい。特にＪａｖａは、java.util.Hashtableなどのハッシュ・テーブルの機能を、ライブラリで提供する。Ｃ、Ｃ＋＋、Ｃ＃などの処理系でも同様の機能が提供されるが、もし所望の機能がない場合は、この分野の熟練した当業者なら、独自に作成することができるはずである。
【００２１】
ハードディスク・ドライブ１０８にはさらに、プログラム言語処理系でコンパイルするためのソースコードを書くためのテキスト・エディタ、及び、Ｅｃｌｉｐｓｅ（商標）などの開発環境を含んでいてもよい。
【００２２】
キーボード１１０及びマウス１１２は、オペレーティング・システムまたは、ハードディスク・ドライブ１０８から主記憶１０６にロードされ、ディスプレイ１１４に表示されたプログラム（図示しない）を起動したり、、文字を打ち込んだりするために使用される。
【００２３】
ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。ディスプレイ１１４は、図示しないが、本発明に係るデータベース・インデックス作成ツールの操作画面を表示するために使用される。この画面に、キーボード１１０で所定のパラメータやファイル名を入力し、表示されている所定のボタンをマウス１１２でクリックすることにより、キーワード作成処理が開始される。
【００２４】
次に、図２を参照して、テキストマイニング用データベースの一般的な構造を説明する。図２に示すように、テキストマイニング用データベース２０２は、文書id = 1, 2, 3 ・・・を付与された複数の文書をもつ。そのような文書の単位の例として、コールセンターにおける一回の電話のログ、メールデータへースの１つのメール、Ｗｅｂデータにおける１つのＨＴＭＬファイル、ブログにおける１つの記事、などがある。文書の数は、多くの場合、１０万のオーダーであり、場合により、１００万以上のオーダーの文書をもつデータベースであることもある。
【００２５】
各文書には、テキストマイニングの分野で周知の技法により、当該文書から抽出された、１つまたはそれ以上のキーワードが関連付けられている。各文書からキーワードを抽出する技法は、特開２００１−８４２５０、特開２００２−２５１４０２、及び特開２００５−２４６４４０等に記述されている技法が知られているが、本発明の主題ではないので、ここでは詳述しない。図２の例では、id=1の文書から、phone, internet, mailが抽出されてid=1の文書に関連づけられ、id=2の文書から、mail, networkが抽出されてid=2の文書に関連づけられている。ここで、単一の文書内では、単一のキーワードは重複カウントされないことに留意されたい。
【００２６】
尚、図２では、キーワードの例として、英単語が示されているが、日本語その他の任意の言語で、構文解析によりキーワードを抽出する技術は確立しているので、本発明の適用範囲は、言語に限定されないことを理解されたい。
【００２７】
しかし、このままのデータ構造では、例えば、internetを含む文書のidを列挙することも、非常に時間がかかる。そこで、このような参照を高速化するために、図３以下で説明する、いくつかのインデックスが必要となる。
【００２８】
図３を参照すると、先ず、キーワード文字列からIDをひくためのインデックスKW2IDと、KW2IDへのポインタでIDからキーワード文字列をひくためのインデックスID2KW とが示されている。データ構造自体としては、プログラミング言語でJava(商標)を使用する場合、例えば、java.util.Hashtableを利用することができる。
【００２９】
各キーワード文字列は、KW2IDテーブルの keyword_i (i=1, 2, ..., k) に、ID(id_i)と一緒に格納される。key_len_i は、keyword_i の文字列長を格納する。例えば "CPU" なら key_len_iの値は3である。
【００３０】
キーワード文字列 wからIDをひくときは、wのハッシュ値iに対し、pointer_iの値が指し示す keyword_i を調べる。これが wと一致する場合は id_iが求めるIDになる。一致しない場合は、next_pointer_i が指し示す別のキーワードを調べ、 wと一致するかどうか調べる。これを wが見つかるまで繰り返す。next_pointer_i の値が、次のキーワードが存在しないことを示す値（例えば -1にしておく）の場合は、wはインデックスに登録されていないことになる。
【００３１】
IDからキーワード文字列をひくときは、ID2KW の pointer_iを読み（各pointer_iは8バイト固定長なので、IDがわかれば ID2KW 内の pointer_i の位置に直接とべる）、その pointer_iの値が指し示す KW2ID 内のキーワード文字列 keyword_iを読む。
【００３２】
次に、図４を参照して、キーワードから文書へのポインタを与えるインデックスである、K2Dについて説明する。図４において、ランク・テーブル４０２は、各々のキーワードと、そのキーワードの全文書中での出現頻度との対応を示す表である。ランク・テーブル４０２において、キーワードは実際は、internetのような具体的な文字列ではなく、図３でkeyword_iで示されている、キーワードのid値として格納されている。例えば、internetというキーワードは、図４によると、全文書中で、105672回現れる。ランク・テーブル４０２では、キーワードの欄は、その頻度で、降順にソートされている。
【００３３】
文書分布テーブル４０４は、各キーワード毎に、そのキーワードが現れる文書idの集合を配列している。例えば、文書分布テーブル４０４の１行目は、ランク・テーブル４０２の最初のキーワードinternetが現れる文書の文書idを配列している。なお、好適な実施例では、文書idは、４バイトからなる。通常文書idは非負整数で表すことが多いが、4バイトで整数を2の補数表現した場合には 0 から 2147483647 までの値を表現できる。したがって多くの場合4バイトで表現できる。むろん、必要に応じてより大きなバイト数を確保する実施方法もあり得る。
【００３４】
さて、ランク・テーブル４０２の出現頻度の欄は、対応する文書分布テーブル４０４の行に対するポインタの役目も果たす。例えば、internetというキーワードに対する出現頻度の欄は、文書分布テーブル４０４の対応する行である、{0,1,3,4,7...}をポインタ４１０で、指し示す。なお、{0,1,3,4,7...}は、文書idの並びで、文書分布テーブル４０４では、升目に入った数字であらわされているものである。同様に、windowsというキーワードに対する出現頻度の欄は、文書分布テーブル４０４の対応する行である、{1,2,5,7,8...}をポインタ４１２で、指し示す。
【００３５】
次に、図５を参照して、文書からキーワードへのポインタを与えるインデックスである、D2Kについて説明する。図５において、ポインタ・テーブル５０２は、単に、文書idを1から始まって最後の文書idまで、リストするものである。キーワード分布テーブル５０４は、各文書毎に、その文書から抽出されたキーワードのidの集合を配列するものである。例えば、図５では、文書idが1の文書から、100,102,270,564,1008, ...というキーワードidをもつキーワードが抽出されたことが示されている。同様に、文書idが2の文書から抽出されたキーワードのキーワードidは、7,64,195,197,700である。ポインタ・テーブル５０２の文書idの欄は、対応するキーワード分布テーブル５０４の対応する行を指し示す。例えば、文書idが1の欄は、キーワード分布テーブル５０４の、{100,102,270,564,1008...}という行を、ポインタ５１０で指し示す。同様に、文書idが2の欄は、キーワード分布テーブル５０４の、{7,64,195,197,700}という行を、ポインタ５１２で指し示す。なおここで、{100,102,270,564,1008...}などは、キーワードidの並びで、キーワード分布テーブル５０４では、升目に入った数字であらわされている。好適な実施例では、キーワードidも、４バイトからなる。
【００３６】
ここまでの説明で、これらのインデックス構造自体は、従来から知られており、この発明の特徴ではないことを理解されたい。ここから、従来技術では知られていない、本発明の説明を行うことにする。
【００３７】
先ず、本発明において、キーワード・グループ数Gという固定の整数値が選ばれる。この数Gは、次のように使用される。すなわち、任意のキーワードwに対して、あるハッシュ関数hashを作用させる。その結果をGで割った余りhを、キーワードのグループ番号と呼ぶことにする。
数式で書くと、h = hash(w) mod G となる。
Javaの記法では、h = hash(w) % G; である。
ここで使用するhash関数は、定義域が想定されるキーワードw全体に亘り、値が整数であるような任意のものでよい。例えば、これに限定されるものではないが、Javaで用意されている、HashCode()という関数を使用することができる。これは、下記のようなアルゴリズムで、長さnの文字列のハッシュ値を返す。
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
ここで、s[i] は文字列の i 番目の文字、n は文字列の長さ、^ はべき乗を示す。
【００３８】
次に、文書数による、データベースの文書の分割について説明する。本発明によれば、データベースの文書全体の集合 Dが
、D = D1∪D2∪...∪Dk  のように、分割される。
このとき、任意のi≠jにつき、Di∩Dj = Φである。
数学的に言うと、集合 Dが、D1,D2,...,Dkに、直和分割される、ということになる。
例えば、データベースが、1000000個の文書からなる、
すなわち、D = {1,2,...,1000000} とすると、これを20分割して、
D1 = {1,2,...,50000}
D2 = {50001,50002,...,100000}
D3 = {100001,100002,...,150000}
.......
D20 = {950001,950002,...,1000000}  となる。この例では、１つの部分集合が50000の文書を含むように分割されるが、コンピュータの主記憶の容量や、上記キーワード・グループの個数Gに応じて、別の値を選ぶこともできる。また、この例では、等しい文書数の部分集合に分割しているが、等しくない文書数の部分集合に直和分割してもよい。
【００３９】
次に上記のように分割された、１つの文書部分集合におけるインデックス作成処理について、図６のフローチャートを参照して説明する。これは、h番目のキーワード・グループについての処理である。上述したように、hというのは、キーワードのハッシュ値を、キーワード・グループの数Gで割った余りであるから、h = 0, 1, ..., G-1である。よって、図６のフローチャートは、１つの文書部分集合につき、hの値を変えながら、G回繰り返すことになる。なお、以下のフローチャートでは、説明の都合上、キーワード・グループを、キーワードのハッシュ値を、キーワード・グループの数Gで割った余りに1を加えた数として説明する。すると、h = 1, ..., Gである。というのは、ＣやＪａｖａでは、配列のインデックスは0から始まるので、h = 0, 1, ..., G-1の方がこれらのコンピュータ言語に馴染むが、説明の便宜上、少し直感的でなくなるためである。実装的には、h = 0, 1, ..., G-1でも、h = 1, ..., Gでも、どちらでもよいことに留意されたい。h = 1, ..., Gとした場合は、キーワード・グループの数Gで割った余りが0である場合を、キーワード・グループ1とする。
【００４０】
さて、図６において、先ず、当該の文書部分集合において、ステップ６０２で、まだ読み出されていない文書があるかどうかが、判断される。もしその判断が否定的であれば、全ての文書を読み出した、ということなので、図６のフローチャートは、終了する。まだまだ読み出されていない文書があると、ステップ６０４で、次の文書が、当該の文書部分集合から読み出される。
【００４１】
こうして１つの文書が読み出されると、ステップ６０６では、その文書のキーワードに関して、ハッシュが計算され、さらにそのハッシュ値についてGによる整数割り算が行われる。その余りの値がhであると、そのキーワードが、主記憶１０６（図１）中の所定のバッファメモリに保持され、その余りの値がh以外だと、単に無視される。図２に示されているように、１つの文書には通常、複数のキーワードが関連付けられているので、ステップ６０６では、ステップ６０４で読み出された１つの文書に関連付けられた全ての複数のキーワードにつき、ハッシュ値とそのGによる余りが計算される。なお、ステップ６０６では、折角１つの文書に関連付けられた、すべてのキーワードを処理するので、後の処理のため、そのハッシュ値のGによる整数割り算の余り値とともに、バッファメモリに保持しておけばよいように思われるかもしれない。しかし、通常、１つの文書部分集合に関連する全てのキーワードを保持するには、主記憶１０６の使用可能な容量は十分ではない。そこで、本発明によれば、１つのキーワード・グループhに属するキーワードのみが、主記憶１０６に保持される。
【００４２】
ステップ６０８では、このようにして、バッファメモリに保持された、キーワード・グループhのキーワードについて、インデックスの構築が行われる。ステップ６０８は、実際は、サブルーチンとしてあらわされるような詳細な処理を含むので、後で詳しく説明する。
【００４３】
ステップ６０８の処理が終わると、ステップ６０２の判断ステップに戻り、まだ読み出していない文書がある限り、ステップ６０４、６０６及び６０８を繰り返す。こうして全ての文書が読み出されると、ステップ６０２での判断が否定的になるので、そこで処理は終わる。キーワード・グループhに属するキーワード群について、インデックスの作成が完了すると、キーワード・グループhに属するキーワード群を保持していた主記憶１０６の領域が開放され、hが１つ増分され、図６のフローチャートの処理が、ステップ６０２から、文書部分集合の最初の文書から開始される。
【００４４】
こうして結局、図６のフローチャートの処理は、k個の文書部分集合毎に、G回実行されるので、結果的に、k × G回実行されることになる。
【００４５】
次に、図７を参照して、図６のステップ６０８のインデックス作成処理を詳細に説明する。図７において、ステップ７０２で、初期化、すなわち、設定ファイルから設定情報を主記憶１０６に読み込んだり、文書が格納されているファイルをオープンしたりする処理を行う。設定情報には、インデックスのファイルを書き出すためのディレクトリ名などの情報を含む。なお、図７のフローチャートが対象とするのは、１つの文書部分集合と、その文書部分集合の文書に関連付けられた、１つのキーワード・グループhに属するキーワード群であることに留意されたい。
【００４６】
より詳細に具体的に説明すると、初期化ステップ７０２では、ＫＷプラグイン、Ｋ２Ｄプラグイン及びＤ２Ｋプラグイン、という３つのプログインが初期化される。ここでプラグインという言い方をしたが、単に、個別の処理プロセスくらいの意味で理解してよい。ＫＷプラグインは、図３に示すインデックス構造を作成するためのものであり、Ｋ２Ｄプラグインは、図４に示すインデックス構造を作成するためのものであり、Ｄ２Ｋプラグインは、図５に示すインデックス構造を作成するためのものである。これらのプラグインは、好適な実施例では、Ｊａｖａ（商標）で書かれているが、Ｃ、Ｃ＋＋、Ｃ＃など、その他の任意の適当なプログラミング言語で作成することもできる。
【００４７】
ステップ７０４では、文書が残っているかどうか、すなわち、１つの文書部分集合において、まだ読み込む文書が残っているかどうかが判断される。まだ文書が残っているなら、processDocumentと名付けられたステップ７０６に進む。そうでなく、文書部分集合の全ての文書が読み出されたなら、Serializeと名付けられたステップ７０８に進む。
【００４８】
processDocumentと名付けられたステップ７０６について説明する。processDocumentは、１つの文書を引数とする。ステップ７０６において、読み出された、引数として与えられた文書に関して、ＫＷプラグインは、その文書に関連するキーワードに、文書部分集合でなく、文書集合全体に亘って一意的なＩＤを付与する。このとき、図６のステップ６０６で、１つのキーワード・グループhに属するキーワード群の情報が、主記憶１０６に、java.util.Hashtableなどのハッシュ構造でロードされているので、ＫＷプラグインは、そのキーワードで、規定されたメソッドを用いて、そのハッシュ構造に問い合わせする。
【００４９】
このとき、もし既にキーワードがそのハッシュ構造に既に存在していれば、そのキーワードのＩＤが返される。もし存在していなければ、キーワードに既に付与されている最後のＩＤに１を加えた値が、そのキーワードに付与され、そのキーワードとＩＤは、そのハッシュ構造に、規定されたメソッドを用いて登録される。また、その付与されたＩＤは、キーワードに既に付与されているＩＤとして、主記憶の所定位置に参照可能に上書き保持される。
【００５０】
このとき、問いあわせするのは、キーワード・グループhに属するキーワード群だけなのであるが、その問い合わせするもととなるキーワード自体が、ハッシュ関数とGによる割り算の計算でキーワード・グループhに属する、と分かっているので、上記キーワード・グループhに関するハッシュ構造にそのキーワードがないことが分かると直ちに、部分集合でない、文書集合全体を通して、そのキーワードが、今までなかったことがわかる。
【００５１】
これにより、キーワードをキーワード・グループに分けることの効果が明らかである。すなわち、もしこのようなキーワード・グループに分けないと、上記のような問い合わせを行うために、今まで出会ったキーワード全体を主記憶１０６にすべてロードしなくてはならないが、それは、データベースの文書数や主記憶のサイズを考慮すると、多くの場合、困難である。すると、そのようなキーワードとＩＤのハッシュ配列情報は、一旦ハードディスク１０８に配置して、部分的に読み出す必要があり、どうしても処理速度が著しく低下してしまう。本発明によれば、キーワードを、キーワード・グループに分けることにより、今まで出会ったキーワード全体を主記憶１０６にすべてロードすることが可能となり、キーワードＩＤの照会と付与の処理が高速化される。
【００５２】
さて、ＫＷプラグインは、この時点で、ハードディスク１０８上にオープンされているＫＷインデックス・ファイルに、キーワードとＩＤの対応を書き出す。ＫＷインデックス・ファイルのデータ構造は、図３に関連して既に説明したものである。なお、Ｋ２Ｄインデックス・ファイル（図４）、及びＤ２Ｋインデックス・ファイル（図５）とは異なり、ＫＷインデックス・ファイルは、全体の文書集合を通して、キーワード・グループ毎に１つ作成される。
【００５３】
Ｄ２Ｋプラグインは、processDocumentに引数として与えられた文書から、（文書ＩＤ、キーワードＩＤ）の組を、主記憶１０６に保管する。ここで、キーワードＩＤは、直前にＫＷプラグインが付与したものを使う。こうして、全ての文書を処理した後、当該部分文書のキーワード・グループhに関する、図５に示すような文書キーワード行列が、主記憶１０６上に構築されることになる。
【００５４】
processDocumentでは、Ｋ２Ｄプラグインは、何もしない。こうして処理は、ステップ７０４の判断に戻る。
【００５５】
次に、図７のフローチャートで、ステップ７０４で判断が否定的、すなわち、文書部分集合の全ての文書を読み出したと判断されると、serializeと書かれたステップ７０８で、Ｄ２Ｋプラグインは、主記憶１０６に保管されている文書キーワード行列を、Ｄ２Ｋインデックス・ファイル（図５）として、ハードディスク１０８に書き出す。Serializeステップ７０８では、ＫＷプラグインも、Ｋ２Ｄプラグインも、何もしない。
【００５６】
図７のフローチャートで、serializeステップ７０８の次に、postProcessと書かれたステップ７１０が実行される。postProcessステップ７１０では、Ｋ２Ｄプラグインが、Ｄ２Ｋプラグインを介して、Ｄ２Ｋが構築した文書キーワード行列を受け取り、転置行列構造（図４に示す、キーワード文書行列）であるＫ２Ｄインデックス・ファイルとして、ハードディスク１０８に書き出す。
【００５７】
分割されたインデックス・ファイルの作成処理は、これで完了であるが、Ｄ２Ｋから、転置行列構造としてのＫ２Ｄインデックスを作成する処理は、もう少し詳しく説明した方がよいと思われるので、図８と図９のフローチャートを参照して説明する。
【００５８】
図８を参照すると、ステップ８０２では、Ｋ２Ｄプラグインによって、key2docという空のテーブルが作成される。次にステップ８０４では、主記憶１０６上にＤ２Ｋプラグインによって構築された文書キーワード行列（ここでは、doc2keyと呼ぶ）文書ｉｄがリストされる。すなわち、ここでは、文書キーワード行列doc2keyが主記憶上に存在することが前提とされる。
【００５９】
なお、doc2key自体は、メモリ上に保持されている、好適にはＪａｖａで作成されたハッシュ・テーブルで、文書ｉｄをキーにして、キーワードｉｄの配列を返す。key2docも好適にはＪａｖａで作成されたハッシュ・テーブルであり、キーワードｉｄをキーにして、対応する文書ｉｄを返す。
【００６０】
ステップ８０６では、読み出していない文書ｉｄはまだあるかどうかが判断される。その判断が肯定的、すなわち、読み出していない文書ｉｄがまだあるなら、ステップ８０８で、次の文書ｉｄが読まれる。ステップ８１０で、doc2keyから、読み出した文書ｉｄに対応するキーワードのリスト（配列ともいう）Lが取得される。そうして、ステップ８１２では、リストL中のすべてのキーワードｉｄについて、すべての対（キーワードｉｄ,文書ｉｄ）をkey2docに入れる処理が行われる。こうして、ステップ８０６の判断に戻る。
【００６１】
ステップ８０６での判断が否定的、すなわち、すべての文書ｉｄが読み出されたなら、WriteIndexFilesという名前のサブルーチン８１４の処理が行われる。
【００６２】
図９は、WriteIndexFilesサブルーチンの詳細を示すフローチャートである。図９のステップ９０２では、key2docテーブルに登録されているキーワードｉｄがリストされる。ステップ９０４では、そのリスト中で、キーワードｉｄが、昇順にソートされる。
【００６３】
ステップ９０６では、読み出していないキーワードｉｄがまだ残っているかどうかが判断される。そして、読み出していないキーワードｉｄがまだ残っているなら、ステップ９０８で、次のキーワードｉｄが読まれる。
【００６４】
ステップ９１０では、key2docから、読み出したキーワードｉｄに対応する文書ｉｄのリストLが取得される。ステップ９１２では、（キーワードｉｄ,L.Length）の対が、ランク・テーブル・インデックスに書き出される。なお、L.Lengthというのは、リストLの長さをあらわす。ランク・テーブル・インデックスは、図４に、例示されているようなものである。
【００６５】
ステップ９１４では、リストLが、文書分布テーブル・インデックスに書き出される。文書分布テーブル・インデックスも、図４に例示されているようなものである。
【００６６】
こうしてステップ９０６の判断ステップに戻り、読み出していないキーワードｉｄがまだ残っている限り、ステップ９０８、９１０、９１２及び９１４が繰り返され、ステップ９０６の判断が否定的、すなわち、全てのキーワードｉｄが読み出されたと判断されると、処理は終了となる。
【００６７】
以上で、部分文書集合毎のキーワード・グループ別のＤ２Ｋインデックス・ファイル（図５）、及びＫ２Ｄインデックス・ファイル（図４）を作成する処理の説明が完了したので、次に、これらの個別のインデックスを統合して、文書集合全体に対応するインデックスを作成する処理について説明する。なお、図７のフローチャートに示す処理では、ＫＷインデックス・ファイルも作成されるが、この発明の好適な実施例では、ＫＷインデックスはもともと、文書集合全体に対応する単一のものとして作成されるので、マージする必要はないことを理解されたい。
【００６８】
次に、図１０を参照して、キーワード・グループh（h = 1...G）における、部分文書集合毎のＤ２Ｋインデックスのマージ処理について説明する。図１０のステップ１００２では、中間doc2keyインデックス・ファイルDh[1], Dh[2],..., Dh[k]がオープンされる。kは、部分文書集合の個数である。Dh[i]というのは例えば、部分文書集合Diの、キーワード・グループhにおけるＤ２Ｋインデックス・ファイルであり、その作成処理は、図７のフローチャートに関連して説明済みである。
【００６９】
次に、ステップ１００４では、空のインデックス・ファイルFMD[h]が作成される。次のステップ１００６では、変数i = 1とセットされ、ステップ１００８では、iがkに達したかどうかが判断される。iがkにまだ達してなければ、ステップ１０１０で、まだ読んでいない文書idが、Dh[i]に残っているかどうかが、判断される。
【００７０】
もしその判断が肯定的であるなら、ステップ１０１２で、Dh[i]から次の文書idが読まれる。そうして、ステップ１０１４で、Dh[i]から、読まれた文書idに対するキーワードidのリストLが取得される。次に、ステップ１０１６では、リストL中のすべてのキーワードidにつき、対(キーワードid,文書id)がFMD[h]に書き出される。その後処理は、判断ステップ１０１０に戻る。
【００７１】
ステップ１０１０で、Dh[i]の全ての文書idが読まれた、と判断されたら、ステップ１０１８で、iが1だけ増分されて、判断ステップ１００８に戻る。ここで、iがkを超えれば、処理は完了であり、iがkを超えていなければ、判断ステップ１０１０に進む。
【００７２】
図１０のフローチャートは、単一のキーワード・グループhに対する、中間的なＤ２Ｋインデックス・ファイルFMD[h]を作成する処理であった。従って、実際は、キーワード・グループ1からキーワード・グループGまでについてのG回の処理を、各々図１０のフローチャートで行うことにより、FMD[i](i = 1,2, ...,G)というG個の中間的なＤ２Ｋインデックス・ファイルが作成される。
【００７３】
次に、図１１のフローチャートを参照して、最終的なＤ２Ｋインデックス・ファイルを作成する処理について説明する。図５に示すように、Ｄ２Ｋインデックス・ファイルは、実質的には、ポインタ・テーブル(PT)と、キーワード分布テーブル(DT)とからなることに改めて留意されたい。
【００７４】
図１１を参照すると、ステップ１１０２では、中間doc2keyインデックス・ファイルFMD[1], FMD[2],...,FMD[G]がオープンされる。これは、図１０のフローチャートで説明した処理で作成したものである。
【００７５】
ステップ１１０６では、各FMD[i](i = 1,2, ...,G)から、文書idが小さい順に１つ文書idを読み、それをバッファにストアする、という処理が行われる。このバッファとは、主記憶１０６に確保された所定の領域である。
【００７６】
次にステップ１１０８では、バッファにまだ、読み出していない文書idがあるかどうかが判断され、もしあるなら、ステップ１１１０に進む。ステップ１１１０では、バッファに格納されている最小の文書idが選ばれ、それが仮にDIDとされる。例えば、DIDという変数に、最小の文書idを代入する。
【００７７】
ステップ１１１２では、DIDに対応するキーワード・リストが、FMD[i](i = 1,2, ...,G)のうちの、DIDを含むFMD[i]（複数ありえる）から取得され、それぞれ、単一のリストLにマージされる。そうして作成されたリストLは、DTに書き出される。
【００７８】
ステップ１１１４では、バッファから、DIDを除去する。より正確に言うと、DIDの値をもつ、文書idのエントリを除去する。そうして、さきほどのDIDを含んでいた、FMD[i]（複数ありえる）から、次の文書idを、やはり文書idが小さい順に読み、バッファにストアする、という処理が行われる。
【００７９】
このようにして、バッファにストアされた文書idのエントリがなくなるまで、ステップ１１１０、１１１２、及び１１１４が行われ、バッファにストアされた文書idのエントリがなくなって、判断ステップ１１０８での判断が否定的になると、処理は、ステップ１１１６に行く。
【００８０】
ステップ１１１６では、DTが上から順に読まれ、文書idを見つけた場所を単に記録するという処理で、PTが作成される。
【００８１】
次に、図１２を参照して、キーワード・グループh（h = 1...G）における、部分文書集合毎のＫ２Ｄインデックスのマージ処理について説明する。先ず、ステップ１２０２では、中間key2docインデックス・ファイルRh[1], Dh[1], ..., Rh[k], Dh[k]がオープンされる。kは、部分文書集合の個数である。Dh[i]というのは、部分文書集合Diの、キーワード・グループhにおける文書分布テーブル（図４）であり、また、Rh[i]というのは、部分文書集合Diの、キーワード・グループhにおけるランク・テーブル（図４）であり、それらの作成処理は、図７のフローチャートに関連して説明済みである。なお、図１０でも、Dh[i]という記号が使われており、そこでは、Dh[i]は、キーワード・グループhにおける、部分文書集合毎の中間doc2keyをあらわしていたが、Dh[i]という記号は、図１０及び図１２の各々で、仮変数ファイル名として使われているので、混乱はないものと思量する。
【００８２】
さて、ステップ１２０４では、空のインデックス・ファイルFMR[h],FMD[h]が作成される。ステップ１２０６では、各Rh[i]からキーワードidが１つ読まれ、それらが、バッファにストアされる。このバッファとは、主記憶１０６に確保された所定の領域である。ステップ１２０８では、バッファにキーワードidが残っているかどうかが判断される。もしまだ残っていれば、ステップ１２１０に進む。
【００８３】
ステップ１２１０では、バッファにストアされているキーワードidのうち、最小のキーワードidを選び、それをKIDとする処理が行われる。実際上、KIDという変数に、最小のキーワードidの値が代入される。
【００８４】
ステップ１２１２では、KIDを含むRh[i]中のKIDの出現頻度が合計される。このようなRh[i]は、複数あり得る。そうして、KIDとその合計頻度が、FMR[h]に書き出される。
【００８５】
ステップ１２１４では、KIDに対応する、Dh[i]中の文書idのリストが単一のリストLにマージされ、そのリストLが、FMD[h]に書き出される。
【００８６】
ステップ１２１６では、バッファからKIDが除去され、KIDを含んでいた全てのRh[i]から、次のキーワードidが読み出され、それらが、バッファにストアされる。こうして処理は、判断ステップ１２０８に戻り、バッファにキーワードidが残っている限り、ステップ１２１２、１２１４及び１２１６が繰り返される。
【００８７】
バッファに残っているキーワードidがなくなり、判断ステップ１２０８での判断が否定的になると、処理は完了である。このマージ処理によって作成されるインデックスFMR[h],FMD[h]は、入力のインデックスと全く同じフォーマットである。この時点では、キーワードはidの昇順に並び、頻度の降順には並んでいない。頻度順のソートは次の処理（図１３のフローチャートで示す処理）で行う。
【００８８】
図１２のフローチャートは、単一のキーワード・グループhに対する、中間的なＫ２Ｄインデックス・ファイルFMR[h],FMD[h]を作成する処理であった。従って、実際は、キーワード・グループ1からキーワード・グループGまでについてのG回の処理を、各々図１２のフローチャートで行うことにより、FMR[i], FMD[i](i = 1,2, ...,G)という、それぞれG個の中間的なＫ２Ｄインデックス・ファイルが作成される。
【００８９】
図１３は、図１２のフローチャートの処理で作成された、中間的なＫ２Ｄインデックス・ファイルFMR[i], FMD[i](i = 1,2, ...,G)から、文書集合全体に対応する最終的なＫ２Ｄインデックス・ファイルを作成する処理を示すフローチャートである。FMR[i]は、図４に示すランク・テーブルに相当し、FMD[i]は、図４に示す文書分布テーブル４０４に相当する。
【００９０】
図１３において、ステップ１３０２では、中間key2docインデックス・ファイルFMR[1], FMD[1],FMR[2], FMD[2],...,FMR[G], FMD[G]がオープンされる。
【００９１】
ステップ１３０４では、FMR[i]から、キーワードidが頻度でソートされたインデックス・ファイルFMRs[i]が作成される。このことは、i = 1, 2, ..., Gにつき、行われる。本発明によれば、FMR[i]は、単一のキーワード・グループiのみに対応するように作成されたものなので、それ単独だと、その全体を主記憶１０６に収めることができる程度の大きさである。従って、このソート処理は、主記憶上で、高速に行うことができる。ソートのアルゴリズムは、quick sort, Shell sortなど、既知の任意のソート・アルゴリズムを用いることができる。
【００９２】
ステップ１３０６では、変数iに1が代入される。判断ステップ１３０８では、変数iが、キーワード・グループの個数Gを超えていないかどうかが判断され、超えていないなら、CreateTempDTと名付けられたサブルーチン１３１０が実行され、ステップでiが1だけ増分されて、ステップ１３０８での判断が行われる。
【００９３】
ステップ１３０８で、iがGを超えた、と判断されると、CreateFinalIndexと名付けられたサブルーチン１３１４が実行されて、最終的なＫ２Ｄインデックス・ファイルの作成処理が完了する。
【００９４】
ここまでの説明では、最終的なインデックス作成の説明としては、完結していないので、次にステップ１３１０で示したサブルーチンCreateTempDTと、ステップ１３１４で示したサブルーチンCreateFinalIndexを順次、詳述する。
【００９５】
図１４は、サブルーチンCreateTempDTの処理を示すフローチャートである。図１４のステップ１４０２では、所与のiにつき、FMR[i], FMRs[i], FMD[i]がオープンされる。この所与のiとは、図１３のフローチャートで、ステップ１３０６で与えられ、ステップ１３１２で増分されているものである。また、FMR[i], FMRs[i], FMD[i]は、図１３のフローチャートで与えられているものと同じものである。
【００９６】
ステップ１４０４では、上記所与のiにつき、空のインデックス・ファイルFMDs[i]が作成される。そして、ステップ１４０６では、FMRs[i]に、まだ読み出されていないキーワードidがあるかどうかが、判断される。
【００９７】
そして、もしFMRs[i]に、まだ読み出されていないキーワードidがあるなら、処理は、ステップ１４０８に進み、ステップ１４０８では、FMRs[i]を読んで、次のキーワードid KID[1], KID[2], ..., KID[m]と、その頻度が取得される。
【００９８】
ステップ１４１０では、FMR[i]を読んで、KID[j] (j = 1,2,...,m)のポインタが取得される。次にステップ１４１２では、FMD[i]を読んで、KID[j] (j = 1,2,...,m)に対応する文書idのリストDLIST[j] が取得される。
【００９９】
ステップ１４１４では、DLIST[j] (j = 1,2,...,m)をFMDs[i]に書き出す処理が行われる。こうして処理は、判断ステップ１４０６に戻り、FMRs[i]に、まだ読み出されていないキーワードidがある限り、ステップ１４０８、１４１０、１４１２及び１４１４が行われ、判断ステップ１４０６で、FMRs[i]から全てのキーワードidが読まれた、と判断されたなら、サブルーチンCreateTempDTが完了する。
【０１００】
以上説明したように、所与のiにつき、サブルーチンCreateTempDTは、FMDs[i]を書き出すので、図１３で、i = 1,2,..,Gまでステップ１３１２すなわち、サブルーチンCreateTempDTの処理が完了し、ステップ１３１４、すなわちサブルーチンCreateFinalIndexが呼ばれる直前では、FMDs[i] (i = 1,2,...,G)が揃っていることになる。
【０１０１】
図１５は、サブルーチンCreateFinalIndexの処理を示すフローチャートである。図１５のステップ１５０２では、中間key2docインデックス・ファイルFMRs[i], FMDs[i]  (i = 1,2,...,G)がオープンされる。ステップ１５０４では、空のインデックス・ファイルRT及びDTが作成される。
【０１０２】
ステップ１５０６では、各FMRs[i]  (i = 1,2,...,G)から１つキーワードidが読み出され、バッファにストアされる。そうしてステップ１５０８では、バッファにキーワードidがまだあるかどうかが判断される。
【０１０３】
バッファにまだキーワードidがあるなら、処理はステップ１５１０に進み、そこでは、バッファ中で最大の頻度をもつキーワードidが選択される。そのようなキーワードidの値を、KIDという変数値に代入し、KIDの所属するキーワード・グループpを確認する。そのようなキーワード・グループpは、KIDを値をもつキーワードidが取り出されたFMRs[i]のiの値を調べることによって、確認される。
【０１０４】
ステップ１５１２では、KIDとその頻度が、RTに書き出される。次のステップ１５１４では、FMDs[p]において、KIDに対応する文書idのリストが読み取られ、そのリストがDTに書き出される。
【０１０５】
次のステップ１５１６では、バッファからKIDの値をもつキーワードidが除去され、FMRs[p]から次のキーワードidが読み出され、バッファにストアされる。そうして処理は、判断ステップ１５０８に戻る。
【０１０６】
ステップ１５０８で、バッファにキーワードidが残っている限り、ステップ１５１０、１５１２、１５１４及び１５１６が繰り返され、バッファにキーワードidが最早なくなると、図１５のフローチャートは、終わる。こうして、全体の文書集合に対応する最終的なインデックス・ファイルRTとDT（図４では、それぞれ、ランク・テーブル４０２と、文書分布テーブル４０４と示されている）が、ハードディスク１０８に書き出されたことになる。
【０１０７】
以上、本発明を、一実施例に基づき説明したが、本発明の１つのキーポイントは、キーワードを、複数のキーワード・グループに分けることにより、インデックス作成処理の間、キーワード・グループ毎のKWインデックスの全体を、主記憶に保持することで、インデックス作成処理を高速化することができる。
【０１０８】
逆に言うと、データベースに関連づけられたキーワードの数が多い場合、キーワード・グループの数を増やすことで、キーワード・グループ毎のKWインデックスのサイズを減らし、その全体が主記憶に収まるようになされる。
【０１０９】
このような、部分インデックス・サイズのスリム化は、インデックス・ファイルのマージ処理においても、主記憶への効果的なロードを可能ならしめ、Ｄ２Ｋ及びＫ２Ｄマージ処理も容易にする。
【０１１０】
Ｄ２Ｋ及びＫ２Ｄ以外の、適当な部分インデックス・ファイルのサイズを小さくしようとすると、部分文書集合のサイズを小さくすることが有効であることがある。こうして、部分文書集合のサイズと、キーワード・グループの数、という２つの調整パラメータを備えたことで、インデックス・ファイル作成の自由度が高まったのである。
【０１１１】
なお、上記の実施例は、１つの文書からキーワードが構文解析などの手法で抽出され関連づけられている、テキストマイニング・データベースに関連して説明したが、１つの文書に、キーワードが関連付けられているタイプのデータベースであるなら、任意のデータベースに、本発明のインデックス作成技術を適用することができることを理解されたい。
【図面の簡単な説明】
【０１１２】
【図１】本発明を実施するためのハードウェアのブロック図である。
【図２】データベースの各文書とキーワードの関係を示す図である。
【図３】データベースのＫＷインデックスの構造を示す図である。
【図４】データベースのＫ２Ｄインデックスの構造を示す図である。
【図５】データベースのＤ２Ｋインデックスの構造を示す図である。
【図６】部分文書集合の特定のキーワード・グループにおいて、部分インデックスを作成するためのフローチャートを示す図である。
【図７】図６のフローチャートにおける、メモリ上にストアされたキーワードからインデックスを作成するためのサブルーチンの処理のフローチャートの図である。
【図８】転置行列構造としてのＫ２Ｄインデックスを作成する処理のフローチャートを示す図である。
【図９】図８のフローチャートにおける、WriteIndexFilesサブルーチンの処理のフローチャートの図である。
【図１０】部分文書集合毎のＤ２Ｋインデックスのマージ処理のフローチャートを示す図である。
【図１１】最終的なＤ２Ｋインデックス・ファイルを作成する処理のフローチャートを示す図である。
【図１２】部分文書集合毎のＫ２Ｄインデックスのマージ処理のフローチャートを示す図である。
【図１３】文書集合全体に対応する最終的なＫ２Ｄインデックス・ファイルを作成する処理のフローチャートを示す図である。
【図１４】図１３における、サブルーチンCreateTempDTの処理のフローチャートを示す図である。
【図１５】図１４における、サブルーチンCreateFinalIndexの処理のフローチャートを示す図である。
【図１】
0004848317.tif 000002
【図２】
0004848317.tif 000003
【図３】
0004848317.tif 000004
【図４】
0004848317.tif 000005
【図５】
0004848317.tif 000006
【図６】
0004848317.tif 000007
【図７】
0004848317.tif 000008
【図８】
0004848317.tif 000009
【図９】
0004848317.tif 000010
【図１０】
0004848317.tif 000011
【図１１】
0004848317.tif 000012
【図１２】
0004848317.tif 000013
【図１３】
0004848317.tif 000014
【図１４】
0004848317.tif 000015
【図１５】
0004848317.tif 000016