(57)【特許請求の範囲】
【請求項１】
検索対象文書を複数のグループに分割するグループ分割部と、
前記分割された複数のグループのそれぞれについて、当該グループと、当該グループに含まれる検索対象文書に出現するキーワードと、当該キーワードが出現する検索対象文書の数と、の情報を対応付けて記憶する索引部と、
検索要求の入力を受け付ける入力受付部と、
前記分割された複数のグループのそれぞれについて、前記入力を受け付けられた検索要求に出現するキーワードの数、もしくは、当該キーワードの数に重み付けをしたものを要素とするベクトルと、前記索引部に記憶された当該グループにおいて当該キーワードが出現する検索対象の文書の数を要素とするベクトルと、の余弦を計算し、当該計算された余弦の値をグループスコアとするグループスコア計算部と、
前記計算されたグループスコアにより、前記複数のグループからいずれか１つ以上のグループを選択するグループ選択部と、
前記選択された１つ以上のグループのそれぞれについて、前記入力を受け付けられた検索要求により、並列に検索を行う検索部と、
前記選択された１つ以上のグループのそれぞれについて検索された結果を併合して、これを前記入力を受け付けられた検索要求に対する検索結果として出力する併合部と、
を備え、
前記検索部は、前記選択された１つ以上のグループのそれぞれについて、当該グループに含まれる文書に対して前記入力を受け付けられた検索要求に出現するキーワードの数を要素とするベクトルと、当該文書に当該キーワードが出現する回数を要素とするベクトルと、の余弦を計算し、当該計算された余弦の値を文書スコアとし、
前記併合部は、前記計算されたグループスコアと、前記計算された文書スコアと、の線形和を計算して、これを総合スコアとし、前記入力を受け付けられた検索要求に対する検索結果を、当該総合スコアの順に出力する
ことを特徴とする検索装置。
【請求項２】
請求項１に記載の検索装置であって、
当該検索対象文書には、それぞれＵＲＬ（Universal Resource Locator）が対応付けられ、
前記グループ分割部は、前記検索対象文書を、各グループに含まれる検索対象文書の数が
（ａ）所望の範囲の数を超える場合は、これに対応付けられたＵＲＬの木構造をある深さの断面で切断することによりグループを再分割し、
（ｂ）所望の範囲の数未満である場合は、当該グループと他のグループとを、併合後のグループに含まれる検索対象文書の数が所望の範囲の数以下となるように、併合する
ことを特徴とする検索装置。
【請求項３】
請求項１または２に記載の検索装置であって、
前記索引部は、前記分割された複数のグループのそれぞれについて、グループと、当該グループに含まれる検索対象文書が含む全単語数と、の情報を対応付けてさらに記憶する
ことを特徴とする検索装置。
【請求項４】
請求項１から３のいずれか１項に記載の検索装置であって、
前記索引部は、前記分割された複数のグループのそれぞれについて、グループと、当該グループに含まれる検索対象文書が含む全キーワードについて、当該キーワードと、当該グループと、当該グループ内での当該キーワードの出現文書数と、の情報を対応付けてさらに記憶する
ことを特徴とする検索装置。
【請求項５】
請求項１から４のいずれか１項に記載の検索装置であって、
前記グループ分割部は、当該検索対象文書のそれぞれについて、これに出現する複数の単語の頻度からなるベクトルと、所定の複数のベクトルとの余弦を計算し、当該検索対象文書を、当該所定の複数のベクトルのうち、その余弦が最大のベクトルに対応付けられるグループに、当該検索対象文書を分類する
ことを特徴とする検索装置。
【請求項６】
請求項１から４のいずれか１項に記載の検索装置であって、
前記グループ分割部は、当該検索対象文書のそれぞれに対して、所定の検索要求により文書スコアを計算し、当該計算結果によって当該検索対象文書を分類する
ことを特徴とする検索装置。
【請求項７】
検索対象文書を複数のグループに分割するグループ分割工程と、
前記分割された複数のグループのそれぞれについて、当該グループと、当該グループに含まれる検索対象文書に出現するキーワードと、当該キーワードが出現する検索対象文書の数と、の情報を対応付けて記憶する索引工程と、
検索要求の入力を受け付ける入力受付工程と、
前記分割された複数のグループのそれぞれについて、前記入力を受け付けられた検索要求に出現するキーワードの数、もしくは、当該キーワードの数に重み付けをしたものを要素とするベクトルと、前記索引工程にて記憶された当該グループにおいて当該キーワードが出現する検索対象の文書の数を要素とするベクトルと、の余弦を計算し、当該計算された余弦の値をグループスコアとするグループスコア計算工程と、
前記計算されたグループスコアにより、前記複数のグループからいずれか１つ以上のグループを選択するグループ選択工程と、
前記選択された１つ以上のグループのそれぞれについて、前記入力を受け付けられた検索要求により、並列に検索を行う検索工程と、
前記選択された１つ以上のグループのそれぞれについて検索された結果を併合して、これを前記入力を受け付けられた検索要求に対する検索結果として出力する併合工程と、
を備え、
前記検索工程では、前記選択された１つ以上のグループのそれぞれについて、当該グループに含まれる文書に対して前記入力を受け付けられた検索要求に出現するキーワードの数を要素とするベクトルと、当該文書に当該キーワードが出現する回数を要素とするベクトルと、の余弦を計算し、当該計算された余弦の値を文書スコアとし、
前記併合工程では、前記計算されたグループスコアと、前記計算された文書スコアと、の線形和を計算して、これを総合スコアとし、前記入力を受け付けられた検索要求に対する検索結果を、当該総合スコアの順に出力する
ことを特徴とする検索方法。
【請求項８】
コンピュータを、請求項１から６のいずれか１項に記載の検索装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高速な検索を行うのに好適な検索装置、検索方法、ならびに、これらをコンピュータに実現させるためのプログラムに関する。
【０００２】
【従来の技術】
従来から、検索対象文書をデータベースに登録し、当該データベースに対して検索要求を与えると、当該検索要求に適合した文書を検索結果として出力する検索システムが提案されている。
【０００３】
近年普及が目覚ましいインターネット技術の分野においても、世界中のウェブサイトの情報を収集し、これをデータベース化して、ユーザからの検索要求に対してこれに適合するようなウェブサイトのＵＲＬ（Universal Resource Locator）を提示するインターネット検索エンジンも、各社から提供されている。
【０００４】
【発明が解決しようとする課題】
しかしながら、大規模な検索を可能とするためには、データベースの規模や数を増やす必要があるが、このような場合にはデータベースとの間の入出力や通信量、データベースそのものの処理量が増大して、検索に要する時間（待ち時間）が長くなってしまう、とともに、各データベースシステムへの負荷が大きくなってしまうおそれがあるという問題が生ずる。
【０００５】
特開平１１−３９３２４号公報においては、複数の検索サブシステムを用意し、利用者が発する検索要求の傾向をあらかじめ分析して、いずれかの検索サブシステムを選択して負荷分散を図る検索技術が開示されているが、状況によってはこの技術による効果が得られないこともある。したがって、各種の状況に対応するため、さまざまな負荷分散の技術に対する要望は大きい。
【０００６】
本発明は、上記の課題を解決するもので、高速な検索を行うのに好適な検索装置、検索方法、ならびに、これらをコンピュータに実現させるためのプログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
上記の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００８】
本発明の第１の観点に係る検索装置は、グループ分割部と、索引部と、入力受付部と、グループスコア計算部と、グループ選択部と、検索部と、併合部と、を備え、以下のように構成する。
【０００９】
すなわち、グループ分割部は、検索対象文書を複数のグループに分割する。
【００１０】
一方、索引部は、前記分割された複数のグループのそれぞれについて、当該グループと、当該グループに含まれる検索対象文書に出現するキーワードと、当該キーワードが出現する検索対象文書の数と、の情報を対応付けて記憶する。
【００１１】
さらに、入力受付部は、検索要求の入力を受け付ける。
【００１２】
そして、グループスコア計算部は、分割された複数のグループのそれぞれについて、索引部に記憶された情報を参照して入力を受け付けられた検索要求に対するグループスコアを計算する。
【００１３】
一方、グループ選択部は、計算されたグループスコアにより、複数のグループからいずれか１つ以上のグループを選択する。
【００１４】
さらに、検索部は、選択された１つ以上のグループのそれぞれについて、入力を受け付けられた検索要求により、並列に検索を行う。
【００１５】
そして、併合部は、選択された１つ以上のグループのそれぞれについて検索された結果を併合して、これを入力を受け付けられた検索要求に対する検索結果として出力する。
【００１６】
本発明により、あらかじめ所定の基準により検索対象文書をグループに分類するとともに、検索要求から当該基準に対応するグループスコアを計算し、これによって検索すべきグループを選択して、負荷分散を図るとともに、ユーザは短い待ち時間で検索結果を得ることができるようになる。
【００１７】
また、本発明の検索装置において、索引部は、分割された複数のグループのそれぞれについて、グループと、当該グループに含まれる検索対象文書が含む全単語数と、の情報を対応付けてさらに記憶するように構成することができる。
【００１８】
また、本発明の検索装置において、索引部は、分割された複数のグループのそれぞれについて、グループと、当該グループに含まれる検索対象文書が含む全キーワードについて、当該キーワードと、当該グループと、当該グループ内での当該キーワードの出現文書数と、の情報を対応付けてさらに記憶するように構成することができる。
【００１９】
これらの発明は、上記発明の好適実施形態の一つであり、グループスコアの計算に、「グループに含まれる検索対象文書が含む全単語数」「グループに含まれるキーワードの出現文書数」などの情報を用いることができるようになる。
【００２０】
また、本発明の検索装置は、以下のように構成することができる。
【００２１】
すなわち、検索部は、選択された１つ以上のグループのそれぞれについて、当該グループに含まれる文書に対して入力を受け付けられた検索要求により、文書スコアを計算する。
【００２２】
一方、併合部は、計算されたグループスコアと、計算された文書スコアと、を参照して、総合スコアを計算し、入力を受け付けられた検索要求に対する検索結果を、当該総合スコアの順に出力する。
【００２３】
本発明により、総合スコアを用いて検索結果をユーザに提示する順番を適切に決定し、ユーザが望む要望に応じた順序で検索結果を提示できるようになる。
【００２４】
また、本発明の検索装置において、併合部は、選択された１つ以上のグループのそれぞれについて検索された結果を当該結果に含まれる検索対象文書が得られた順に併合して、その順に出力するように構成することができる。
【００２５】
本発明により、複数のデータベースシステムにおいて検索処理が行われた場合には、検索対象文書が得られた順にユーザにこれを提示して、待ち時間を減らすことができるようになる。
【００２６】
また、本発明の検索装置は、以下のように構成することができる。
【００２７】
すなわち、当該検索対象文書には、それぞれＵＲＬが対応付けられる。
【００２８】
一方、グループ分割部は、検索対象文書を、各グループに含まれる検索対象文書の数が所望の範囲の数を超える場合は、これに対応付けられたＵＲＬの木構造を広さ方向に分割してグループを再分割する。
【００２９】
さらに、所望の範囲の数未満である場合は、当該グループと他のグループとを、併合後のグループに含まれる検索対象文書の数が所望の範囲の数以下となるように、併合する。
【００３０】
本発明により、ＵＲＬの木構造に基づいて適切な数にグループを構成することができる。
【００３１】
また、本発明の検索装置において、グループ分割部は、当該検索対象文書のそれぞれについて、これに出現する複数の単語の頻度からなるベクトルと、所定のベクトルとの余弦を計算し、当該計算結果によって当該検索対象文書を分類するように構成することができる。
【００３２】
本発明により、文書の特徴をベクトルであらわし、これが所定のベクトルとの間に張る角に相当する情報を有する余弦（cosine）を計算して、所定のベクトルとの「類似度」（どれだけ張る角が小さいか）により文書をグループに分割することができるようになる。
【００３３】
また、本発明の検索装置において、グループスコア計算部は、入力を受け付けられた検索要求と当該所定のベクトルとに対して所定の類似度計算（両者の余弦の計算を含む。）を行って、これをグループスコアとするように構成することができる。
【００３４】
本発明により、検索要求の特徴をベクトルであらわし、これと、文書の分類の際に用いた「所定のベクトル」と、の間の「類似度」により検索要求をいずれか１つ以上のグループに振り分けることができるようになる。
【００３５】
また、本発明の検索装置において、グループ分割部は、当該検索対象文書のそれぞれに対して、所定の検索要求により文書スコアを計算し、当該計算結果によって当該検索対象文書を分類するように構成することができる。
【００３６】
本発明により、文書を並べる順序を決めるのに用いる文書スコアを、グループ化の際にも利用できるようになる。
【００３７】
本発明の他の観点に係る検索方法は、グループ分割工程と、索引工程と、入力受付工程と、グループスコア計算工程と、グループ選択工程と、検索工程と、併合工程と、を備え、以下のように構成する。
【００３８】
すなわち、グループ分割工程では、検索対象文書を複数のグループに分割する。
【００３９】
一方、索引工程では、分割された複数のグループのそれぞれについて、当該グループと、当該グループに含まれる検索対象文書に出現するキーワードと、当該キーワードが出現する検索対象文書の数と、の情報を対応付けて記憶する。
【００４０】
さらに、入力受付工程では、検索要求の入力を受け付ける。
【００４１】
そして、グループスコア計算工程では、分割された複数のグループのそれぞれについて、記憶された情報を参照して入力を受け付けられた検索要求に対するグループスコアを計算する。
【００４２】
一方、グループ選択工程では、計算されたグループスコアにより、複数のグループからいずれか１つ以上のグループを選択する。
【００４３】
さらに、検索工程では、選択された１つ以上のグループのそれぞれについて、入力を受け付けられた検索要求により、並列に検索を行う。
【００４４】
そして、併合工程では、選択された１つ以上のグループのそれぞれについて検索された結果を併合して、これを入力を受け付けられた検索要求に対する検索結果として出力する。
【００４５】
本発明の他の観点に係るプログラムは、コンピュータを、上記の検索装置として機能させ、あるいは、コンピュータに、上記の登録方法を実行させるように構成する。
【００４６】
上記のプログラムは、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＦＤ（Flexible Disk；フレキシブルディスク）などの各種の記録媒体に記録することができるほか、インターネットなどのコンピュータ通信網を介して配布することができる。
【００４７】
【発明の実施の形態】
以下、添付図面を参照して、本発明の実施の形態について説明する。
【００４８】
（情報処理装置の概要構成）
図１は、本発明のデータ構造が記録された記録媒体を処理して、本発明の検索装置を構成するサブ装置として機能しうる典型的な情報処理装置の概要構成を示す模式図である。以下、図１を参照して説明する。
【００４９】
情報処理装置１０１は、ＣＰＵ（Central Processing Unit；中央処理ユニット）１０２によって制御される。情報処理装置１０１に電源を投入すると、ＣＰＵ１０２は、ＲＯＭ１０３に記憶されたＩＰＬ（Initial Program Loader；初期プログラムローダ）を実行する。
【００５０】
ＩＰＬは、ハードディスク１０４、ＦＤドライブ１１０に装着されたＦＤ、ＣＤ−ＲＯＭドライブ１１１に装着されたＣＤ−ＲＯＭなどの記録媒体に記憶されたＯＳ（Operating System；オペレーティング・システム）プログラムを読み出して実行するプログラムである。
【００５１】
ＯＳを起動した後、ＣＰＵ１０２は、キーボード１０５やマウス１０６などにより入力されたユーザの指示にしたがって、あるいは、ハードディスクなどにあらかじめ記述された設定ファイルの内容にしたがって、ハードディスクなどに記憶されたアプリケーションプログラムを実行する。
【００５２】
当該アプリケーションプログラムを実行することにより、情報処理装置１０１は、サブ装置として機能することとなる。
【００５３】
これにより、サブ装置の管理情報を入力することができるほか、ユーザとの対話を担うサブ装置では、ユーザからの検索要求の入力を受け付けることができる。
【００５４】
ＣＰＵ１０２は、これらのプログラムの実行の際に、ＲＡＭ１０７を一時的な作業用記憶領域として用いる。このほか、一時的な作業用記憶領域として、ＣＰＵ１０２内に設けられたレジスタやキャッシュ（図示せず）が使われる。
【００５５】
プログラムの実行に伴ない、ユーザに結果を報告したり、途中経過を見せたり、管理情報を提示したりするため、ＣＰＵ１０２は、液晶ディスプレイやＣＲＴ（Cathode Ray Tube）などの表示装置１０８に当該情報を表示することができる。マウス１０６による指示操作では、マウス１０６を移動することにより、画面に表示されたカーソルが移動し、マウス１０６をクリックすることにより、カーソルが指すメニュー項目を選択することができる。
【００５６】
情報処理装置１０１は、ＮＩＣ（Network Interface Card）やモデムなどのインターフェース１０９を介してサブ装置同士の通信が行われるほか、インターネットなどのコンピュータ通信網と通信を行うことができる。また、インターフェース１０９を介して受信したプログラムを実行したり、などができる。
【００５７】
（本発明の実施形態）
以下の説明では、理解を容易にするため、インターネット検索エンジンに本発明を適用した場合を例にあげて、本発明の一本実施形態を説明する。図２は、本実施形態に係る検索装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【００５８】
本実施形態の検索装置２０１は、グループ分割部２０２と、索引部２０３と、入力受付部２０４と、グループスコア計算部２０５と、グループ選択部２０６と、検索部２０７と、併合部２０８と、を備える。
【００５９】
図３は、本実施形態に係る検索装置において実行させる索引作成処理の流れを示すフローチャートである。
【００６０】
グループ分割部２０２は、検索対象文書を複数のグループに分割する（ステップＳ３０１）。本実施形態で検索対象文書は、インターネット内の各ウェブサイトに存在するＨＴＭＬ（Hyper Text Markup Language）文書となる。これを、以下のような手法により、複数のグループに分割する。
【００６１】
グループ分割部２０２は、当該検索対象文書のそれぞれについて、これに出現する複数の単語の頻度からなるベクトルと、所定のベクトルとの余弦を計算し、当該計算結果によって当該検索対象文書を分類するものである。
【００６２】
検索に用いられることが多いと予想されるキーワードをあらかじめｍ個選択し、当該キーワードのそれぞれが当該検索対象文書に出現する頻度を各要素とするベクトルを考える。
【００６３】
たとえば、ｎ個のグループに分割するのであれば、「所定のベクトル」として、互いに異なる単位ベクトルを適宜ｎ個用意する。
【００６４】
そして、各単位ベクトルと検索対象文書のベクトルとの余弦を計算することにより、当該単位ベクトルと検索対象文書のベクトルとが張る角が最も小さいものを選ぶことができる。そして、選ばれた単位ベクトルに対応付けられたグループに当該検索対象文書を分類すればよい。
【００６５】
これ以外の分類手法については、その他の実施形態として後述する。
【００６６】
一方、索引部２０３は、分割された複数のグループのそれぞれについて、当該グループと、当該グループに含まれる検索対象文書に出現するキーワードと、当該キーワードが出現する検索対象文書の数と、の情報を対応付けて記憶する（ステップＳ３０２）。このキーワードとしては、上記グループの分類の際に用いたものと同じものを採用することができる。
【００６７】
索引部２０３は、必要な文書の各種の情報を転置索引表を用いることにより高速にグループスコアを計算することができるようにする。転置索引表は、検索要求に含まれるキーワード（やこれに対応するＩＤ）を与えると、当該キーワードが出現する位置ならびに統計情報が得られるものである。転置索引表は、キーワード等をキーとするハッシュやＢ木、トライ構造などの公知の技術によって構成することができる。
【００６８】
なお、検索部２０７には、各グループに対応付けられたデータベース（ＤＢ）が用意されており、このデータベースには、各グループにまた、検索対象文書のＵＲＬ等と合わせて、属する検索対象文書そのものやこれを前処理したものを記録しておく。
【００６９】
これ以外に記憶されることが望ましい情報については、その他の実施形態として後述する。
【００７０】
図４は、本実施形態に係る検索装置において実行させる検索応答処理の流れを示すフローチャートである。
【００７１】
入力受付部２０４は、検索要求の入力を受け付ける（ステップＳ４０１）。受け付ける検索要求は、適切なキーワードにより表現されるように正規化されたものであることが望ましい。また、キーワードに適宜重み付けをしてもよい。正規化には、データベース検索の種々の技法を用いることができる。
【００７２】
そして、グループスコア計算部２０５は、分割された複数のグループのそれぞれについて、索引部２０３に記憶された情報を参照して入力を受け付けられた検索要求に対するグループスコアを計算する（ステップＳ４０２）。
【００７３】
本実施形態では、グループスコアの計算にも、ベクトルの余弦を用いる。すなわち、ｎ個のグループのそれぞれについて、当該キーワードが出現する検索対象文書の数を要素とするベクトルと同じ向きの単位ベクトルを考える。一方、検索要求に対しても、その検索要求に出現するキーワードの数（に重み付けをしたもの）を要素とするベクトルを求める。そして、その各単位ベクトルと、求めた検索要求のベクトルとの余弦を計算し、これをグループスコアとする。本手法による場合、グループスコアの値は、０以上１以下となり、大きければ大きいほど、２つのベクトルが張る角は小さいことになる。
【００７４】
一方、グループ選択部２０６は、計算されたグループスコアにより、複数のグループからいずれか１つ以上のグループを選択する（ステップＳ４０３）。
【００７５】
本実施形態では、グループスコアが大きいものからいずれかあらかじめ定めた数だけグループを選択する。
【００７６】
さらに、検索部２０７は、選択された１つ以上のグループのそれぞれについて、入力を受け付けられた検索要求により、並列に検索を行う（ステップＳ４０４）。
【００７７】
検索部２０７において各グループにはＤＢがそれぞれ割り当てられているが、そのそれぞれ専用の検索を行うシステム（Ｑ）が割り当てられている。したがって、各Ｑが各ＤＢに対する検索を並列に実行することができる。
【００７８】
ユーザが求める検索対象文書が属するグループは、２つのベクトルが張る角が小さいものである可能性が極めて高いと考えられるため、これらについてのみデータベース検索処理を行えば、必要な情報はほぼ得られることとなる。一方で、不必要なデータベース検索処理は行わないため、適切に負荷分散を図ることができる。また、データベース検索処理を並列に行うため、待ち時間の短かい検索が可能となる。
【００７９】
そして、併合部２０８は、選択された１つ以上のグループのそれぞれについて検索された結果を併合して、これを入力を受け付けられた検索要求に対する検索結果として出力する（ステップＳ４０５）。
【００８０】
併合の手法については、以下のようなものが考えられる。
【００８１】
もっとも単純には、選択された１つ以上のグループのそれぞれについて検索された結果を当該結果に含まれる検索対象文書が得られた順に併合して、その順に出力する。
【００８２】
これらの各部のそれぞれに対して、上記のサブ装置を１つもしくは複数割り当ててもよいし、これらの各部の任意の組み合わせに対して上記のサブ装置を１つもしくは複数割り当ててもよい。ただし、検索部２０７には、グループの数と同じサブ装置を割り当て、それぞれのグループにおける検索が独立に並列に検索ができるようにすることが望ましい。
【００８３】
この手法では、複数のデータベースシステムにおいて検索処理が行われた場合には、検索対象文書が得られた順にユーザにこれを提示して、待ち時間を減らすことができるようになる。
【００８４】
このほか、検索部２０７に、選択された１つ以上のグループのそれぞれについて、当該グループに含まれる文書に対して入力を受け付けられた検索要求により、文書スコアを計算させ、計算されたグループスコアと、計算された文書スコアと、を参照して、総合スコアを計算し、入力を受け付けられた検索要求に対する検索結果を、当該総合スコアの順に出力するようにしてもよい。
【００８５】
文書スコアは、たとえば、当該検索対象文書が含むキーワードのベクトルと入力要求のベクトルとの余弦を計算することにより得ることができる。総合スコアは、グループスコアと文書スコアの線形和とする等の手法が考えられる。
【００８６】
この手法では、総合スコアを用いて検索結果をユーザに提示する順番を適切に決定し、ユーザが望む要望に応じた順序で検索結果を提示できるようになる。
【００８７】
このように、本実施形態では、あらかじめ所定の基準により検索対象文書をグループに分類するとともに、検索要求から当該基準に対応するグループスコアを計算し、これによって検索すべきグループを選択して、負荷分散を図るとともに、ユーザは短い待ち時間で検索結果を得ることができるようになる。
【００８８】
また、索引作成処理と検索応答処理とは独立に実行することができる。たとえば、所定の期間おきに、あるいは、検索応答処理を実行していない状態（ユーザからの検索要求の入力待ちのアイドル状態）が一定時間以上継続した時に、索引作成処理を行うなどの態様が考えられる。
【００８９】
（グループ化の実施形態）
以下では、種々の検索対象文書のグループ化の実施形態について詳細に説明する。まず、文書の内容に依存した分類の手法である。
【００９０】
第１の手法は、分類カテゴリを示すラベルが１つ以上付与された事例文書をあらかじめＮ個用意して、これとの類似度により各分類カテゴリへ分類を行うものである。ラベルの種類はｎ種類である。
【００９１】
文書同士の類似度（スコア）の計算には、種々の手法があり、上記のようにキーワードの出現頻度のベクトルを用いてその間の余弦（内積）を類似度とするものなどが考えられる。
【００９２】
ある検索対象文書と、事例文書のそれぞれと、の類似度を計算し、これをスコアとして、スコアの上位Ｍ個（Ｍ≦Ｎ）の事例文書を選ぶ。
【００９３】
そして、各スコアをその事例文書に付与されたラベルに対する得点に加算する。同じラベルが異なる事例文書に付与されていることがあるため、ラベルの得点は、複数の事例文書のスコアを加算したものとなることがある。
【００９４】
そして、得点が一位のラベルにより表現される分類カテゴリに当該検索対象文書を分類する。
【００９５】
第２の手法は、やはり類似検索を利用したものである。本手法では、分類の際に適当な検索要求を用意する。
【００９６】
そして、類似検索を用いて、この検索要求に対する各検索対象文書のスコアを計算し、上位１個の検索対象文書を得る。
【００９７】
次に、上位１位の文書を次の検索要求として、残りの各検索対象文書のスコアを計算する。この検索対象文書のスコアを第１次スコアと呼ぶ。そして、第１次スコアの上位M1個（M1≦N）を選択し、これを１番目のグループとする。
【００９８】
以下同様に、次に、第１次スコアが２位以下の文書で、かつ、１番目のグループに属しない文書を次の検索要求として、それ以外の各検索対象文書のスコアを計算し、第２次スコアを得て、第２次スコアの上位M2個（M2≦N）を選択し、これを２番目のグループとする。
【００９９】
そして、１番目と２番目のグループの共通要素は、そのスコアが高い方のグループに分類し直す。
【０１００】
さらに、１番目と２番目のグループのいずれにも属しない検索対象文書を選択して、同様の処理を繰り返して、文書を分類する。
【０１０１】
このように文書の内容に依存するような各種の文書分類の手法を本発明に適用することができる。
【０１０２】
以下では、文書の内容に依存しない分類方法について詳細に説明する。これは、文書の内容ではなく、文書の外見的な特徴に注目するものである。すなわち、以下のような情報に基づいて分類を行う。
・文書の作成日時、更新日時。
・文書の作成者。
・文書の管理番号。
・文書に含まれる何らかの明示的な記述子。たとえば、ＨＴＭＬ文書におけるMETAタグ内のキーワードの記述等。
・文書の配置された場所。ＵＲＬやファイルシステム上の絶対パス等。
【０１０３】
木構造をなすＵＲＬにより分類する場合について説明する。この木構造を任意の深さの断面で切断することにより、複数のグループに分割することができる。そして、そのそれぞれのグループに属する検索対象文書の数を調べ、これが所定の数よりも大きい場合は、さらに深い断面で再分割する。一方、所定の数よりも小さい場合は、いずれか他のグループと併合する。各グループに含まれる検索対象文書の数が所望の範囲になるまでこれを繰り返す。
【０１０４】
このように、これらの情報を用いて分類する場合には、容易に大量の文書を分類することができる。
【０１０５】
（グループスコアの計算の実施形態）
以下では、グループスコアの計算の実施形態について詳細に説明する。
【０１０６】
グループスコアを計算する前に、まず準備として、入力された検索要求に含まれるタームの集合を構成する。適宜これらのタームをシソーラスを使って拡張したり、正規化をしておくことが望ましい。また、得られた検索結果の文書から特徴語を抽出して、当該ターム集合に追加してもよい。
【０１０７】
n個のグループがある場合、各タームtに対するグループcのグループスコアscore(t,c)の計算手法には、たとえば、以下のようなものがある。
【０１０８】
（１）DF×ICF1と呼ばれるもの。以下のような計算式を用いる。
score(t,c) = DF×ICF
ただし
DF = dfc/(dfc + K)；
ICF = log((n+0.5)/CF)/log(n+1.0)；
Kはempiricall yにより定められる定数；
dfcはタームtが出現する文書のグループc内における割合；
CFはタームtが現れる文書を含むグループの数
【０１０９】
（２）DF×ICF2と呼ばれるもの。以下のような計算式を用いる。
score(t,c) = DF×ICF
ただし
DF = dt + (1-dt)×dfc/maxc(dfc)；
ICF = log(n/CF)；
dtは０以上１以下の定数、典型的には０.５；
dfcはタームtが出現する文書のグループc内における割合；
maxc(dfc)は各グループのdfcの最大の値；
CFはタームtが現れる文書を含むグループの数
【０１１０】
（３）DF×AVG-IDFと呼ばれるもの。以下のような計算式を用いる。
score(t,c) = DF×AVGICF
ただし
DF = dt + (1-dt)×dfc/maxc(dfc)；
AVGICF = (1/n)Σclog(n/dfc) + 1；
dtは０以上１以下の定数、典型的には０.５；
dfcはタームtが出現する文書のグループc内における割合；
maxc(dfc)は各グループのdfcの最大の値
【０１１１】
このような計算式により、各タームtに対するグループcのスコアが得られる。そこで、検索要求に含まれるタームのスコアの総和を、当該グループcのグループスコアとする。
【０１１２】
これらの計算を行うためには、索引部２０３は、「グループに含まれる検索対象文書が含む全単語数」「グループに含まれるタームの出現文書数」「タームが出現する文書を含むグループの数」などの情報を記憶しておく必要がある。
【０１１３】
このほか、以下のような処理を行ってもよい。
【０１１４】
DF×ICF1においてKの値を小さくしたり、DF×ICF2やDF×AVGICFにおいてdtの値を小さくしたりすると、サイズが大きい（グループ内に含まれる文書の数が多い）グループのスコアが大きくなる傾向にある。したがって、再現率を重視するか、初期精度を重視するか、によって、これらの値をグループスコア計算時にユーザの指示によって調整することとする。
【０１１５】
また、得られるスコアの総和sを、以下のような計算式により調整して、これをグループスコアとしてもよい。
s×(log(n)+k)
パラメータkを調整することにより、グループスコアを望ましい値とすることができる。
【０１１６】
また、検索要求に含まれるターム数が多い場合は、CFが大きいタームについては、計算を行わずにscore(t,c) = 0としてしまう手法も考えられる。また、このようなタームをストップワードとして、索引部２０３には登録しないこととするのも効果的である。
【０１１７】
さらに、各グループごとに優先タームを割り当て、優先タームが検索要求に含まれる場合は、そのグループを優先的に選択する（最も高いスコアとする）ような態様も考えられる。
【０１１８】
【発明の効果】
以上説明したように、本発明によれば、高速な検索を行うのに好適な検索装置、検索方法、ならびに、これらをコンピュータに実現させるためのプログラムを提供することができる。
【図面の簡単な説明】
【図１】  本発明の検索装置を構成するサブ装置を実現する典型的な情報処理装置の概要構成を示す模式図である。
【図２】  本実施形態に係る検索装置の概要構成を示す模式図である。
【図３】  本実施形態に係る索引作成処理の制御の流れを示すフローチャートである。
【図４】  本実施形態に係る検索応答処理の制御の流れを示すフローチャートである。
【符号の説明】
１０１  情報処理装置
１０２  ＣＰＵ
１０３  ＲＯＭ
１０４  ＨＤ
１０５  キーボード
１０６  マウス
１０７  ＲＡＭ
１０８  表示装置
１０９  インターフェース
１１０  ＦＤドライブ
１１１  ＣＤ−ＲＯＭドライブ
２０１  検索装置
２０２  グループ分割部
２０３  索引部
２０４  入力受付部
２０５  グループスコア計算部
２０６  グループ選択部
２０７  検索部
２０８  併合部
【図１】
0004230710.tif 000002
【図２】
0004230710.tif 000003
【図３】
0004230710.tif 000004
【図４】
0004230710.tif 000005