JP5389715B2 - 複合語に対する文書数予測装置及び方法及びプログラム - Google Patents

Description

本発明は、複合語に対する文書数予測装置及び方法及びプログラムに係り、特に、ユーザから入力された複合語のクエリに対し、複合語を含む文書数が未知の場合に、文書数を予測して文書検索の計算量と検索結果の応答速度を向上させるために、一部の文書群に対して複合語を含む文書の偏りに着目した複合語に対する文書数予測装置及び方法及びプログラムに関する。

近年、インターネット上で検索サービスが広く普及し、ユーザが欲しい文書へのクエリを用いて文書を効率良く文書が検索できるようになった。ここで、この検索を実現するために、文書に関するインデックスを作成し、ユーザから入力されたクエリに該当するインデックスから文書を検索結果として提供している。

文書群に対するインデックスとして、一般に転置インデックスが用いられる（例えば、非特許文献１参照）。この転置インデックスとは、ある単語に対して単語を含む文書をリスト化したものである。図９の転置インデックスの例を用いて説明する。同図には「太陽」に関する転置インデックスを示している。転置インデックス内の１つ目の四角は「太陽」を含む文書に関する情報を示している。ここでは、文書として「Doc1」に関する情報が入っている。このDoc1に関する情報はいくつかの情報から構成されており、同図では、「Doc1」の情報として以下の３つの情報が入っている。

１．文書ID
２．単語（「太陽」）の出現回数
３．単語（「太陽」）の出現位置
また、この転置インデックスは予め作成するため、単語を含む文書数の情報も保持している。図９では、「太陽」を含む文書は１５文書存在する。

前述のように単語に対する転置インデックスを検索対象となる文書群から抽出した単語に対して作成しておくが、ユーザから入力されるクエリには転置インデックスが用意されていない単語の場合がある。転置インデックスが用意されていないクエリに対しては、クエリを構成する単語群や関連する単語の転置インデックスから該当する文書を求める必要がある。

ここではクエリが複合語（複数の単語から構成される語）の場合について取り上げ、複合語に対する転置インデックスが用意されていない時の文書のリストを求める方法について説明する。複合語のクエリとして「太陽エネルギー」の場合について説明する。図９のように「太陽」、「エネルギー」の転置インデックスが用意されている場合、「太陽エネルギー」を含む文書をこれら転置インデックスから求める必要がある。まずは、「太陽」を含む文書「Doc１」に着目し、「エネルギー」を含む文書を探索する。ここでは、「エネルギー」の転置インデックスから「Doc1」に「エネルギー」が含まれていることがわかる。

次に、「Doc１」の「太陽」の出現位置の次に、「エネルギー」の出現位置が連続する箇所を探索する。図９からは「太陽」の出現位置が"１"に対し、「エネルギー」の出現位置が"２"のため「Doc１」に「太陽エネルギー」が含まれることを検出する。同様の処理を、「太陽」の転置インデックスに存在するすべての文書に対して処理し、「太陽エネルギー」を含む文書のリストを作成する。

Justin Zobel, Alistair Moffat and Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453 - 490.

しかしながら、前述の従来技術では、ユーザからクエリが入力された際に、複合語を構成する複数の転置インデックスから複合語を含む文書を検出する必要があり、転置インデックス全体から逐次処理した場合は計算量が多く、応答時間が長くなる問題がある。

また、対象とする文書群から予め複合語に対する転置インデックスを作成して応答時間を短縮する場合は、用意する転置インデックスの数が膨大になりコストが大きくなる問題がある。

その一方で、複合語を構成する一部の文書数を基に、文書群全体の複合語を構成する文書数を予測する場合には、複合語を構成する一部の文書群の存在状況により予測値が大きく異なる問題がある。ここでの文書群の存在状況とは、文書に対象とする複合語が含まれていた文書数と含まれていなかった文書数の割合のことを示す。

本発明は、上記の点に鑑みなされたもので、少ないコストで文書数を予測でき、また、一部の文書群から検出した複合語を含む文書数を基に、文書数を予測する場合に、一般的な手段での予測文書数よりも精度良く予測可能な複合語に対する文書数予測装置及び方法及びプログラムを提供することを目的とする。

図１は、本発明の原理構成図である。

本発明（請求項１）は、文書検索における複合語に対する文書数予測装置であって、
単語名毎に、該単語を含んでいる文書ＩＤ、単語の出現回数、単語の出現位置を含む転置インデックスを格納した転置インデックス記憶手段６０と、
ユーザから入力されたクエリが複合語の場合に複合語を単一の単語に分割する単語分割手段１０と、
分割された単語に基づいて転置インデックス記憶手段６０を参照して、分割した単語それぞれに対する転置インデックスを抽出する転置インデックス取得手段２１と、
予め設定した文書数を対象として、抽出された転置インデックスから抽出した複合語を含む文書数を算出する文書数算出手段２２と、
検出した複合語を含む文書数と転置インデックス取得手段２１で取得した各単語を含む文書数に基づいて、文書数予測ルールを用いて全文書に対する複合語を含む文書数の予測値を算出する予測値算出手段１００と、を有する。

また、本発明（請求項２）は、請求項１の文書数予測ルールにおいて、
複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも大きい場合は、単独文書数比を用いて予測する文書数を小さく補正するルールを含む。

また、本発明（請求項３）は、請求項１の文書数予測ルールにおいて、
複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも小さい場合は、単独文書数比を用いて予測する文書数を大きく補正するルールを含む。

図２は、本発明の原理を説明するための図である。

本発明（請求項４）は、文書検索における複合語に対する文書数予測方法であって、
単語名毎に、該単語を含んでいる文書ＩＤ、単語の出現回数、単語の出現位置を含む転置インデックスを格納した転置インデックス記憶手段と、
文書数予測ルールを格納したルール記憶手段と、を有する装置が、
ユーザから入力されたクエリが複合語の場合に複合語を単一の単語に分割する単語分割ステップ（ステップ１）と、
分割された単語に基づいて転置インデックス記憶手段を参照して、分割した単語それぞれに対する転置インデックスを抽出する転置インデックス取得ステップ（ステップ２）と、
予め設定した文書数を対象として、抽出された転置インデックスから抽出した複合語を含む文書数を算出する文書数算出ステップ（ステップ３）と、
検出した複合語を含む文書数と転置インデックス取得ステップ（ステップ２）で取得した各単語を含む文書数に基づいて、文書数予測ルールを用いて全文書に対する複合語を含む文書数の予測値を算出する予測値算出ステップ（ステップ４）と、を行う。

また、本発明（請求項５）は、請求項４の予測値算出ステップにおいて、
複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも大きい場合は、単独文書数比を用いて予測する文書数を小さく補正する文書数予測ルールを用いる。

また、本発明（請求項６）は、請求項４の予測値算出ステップにおいて、
複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも小さい場合は、単独文書数比を用いて予測する文書数を大きく補正する文書数予測ルールを用いる。

本発明（請求項７）は、請求項１乃至３のいずれか１項に記載の文書数予測装置を構成する各手段としてコンピュータを機能させるための文書数予測プログラムである。

上記のように本発明によれば、従来の複合語に対する文書数の計算において、複合語を構成する単語の転置インデックスを逐次スキャンして複合語を含む文書数を計算するより、少ない計算量で文書数を予測できる。また、一部の文書群から検出した複合語を含む文書数を基に文書数を予測する場合に、一般的な手段での予測文書数よりも精度よく予測できる。

本発明の原理構成図である。 本発明の原理を説明するための図である。 本発明の一実施の形態における文書数予測装置の構成図である。 本発明の一実施の形態における文書数予測装置の動作のフローチャートである。 本発明の一実施例の「太陽エネルギー」を持つ文書の検出状況である。 本発明の一実施例の複合語「太陽エネルギー」に対する文書数の計算例１である。 本発明の一実施例の複合語「太陽エネルギー」に対する文書数の計算例２である。 本発明の一実施例の複合語「太陽エネルギー」に対する文書数の計算例３である。 転置インデックスの例である。

以下、図面と共に、本発明の実施の形態を説明する。

図３は、本発明の一実施の形態における文書数予測装置の構成を示す。

同図に示す文書数予測装置は、クエリ入力部１０、文書数予測部２０、予測式１計算部３０、予測式２計算部４０、予測式３計算部５０、転置インデックス記憶部６０、予測ルール記憶部７０から構成される。このうち、転置インデクス記憶部６０、予測ルール記憶部７０は、ハードディスクやメモリ等の記憶媒体である。

クエリ入力部１０は、入力されたクエリが複合語である場合は、当該複合語を単一の単語に分割する。

文書数予測部２０は、クエリ入力部１０で分割された単語に基づいて、転置インデックス６０を検索し、各単語に対応する文書ID、出現回数、出現位置を含む転置インデックスを抽出し、当該単語に対する転置リストを生成する。当該転置インデックスから複合語を含む文書数を検出する。

予測式１計算部３０、予測式計算部４０、予測式３計算部５０は、予め設定された条件に対応する予測ルールに基づいて、検出した複合語を含む文書数と当該複合語中の各単語を含む文書数を基に文書数を予測する。

転置インデックス記憶部６０は、単語名毎に転置インデックスが格納されている。ここで、転置インデックスは、単語を含んでいる文書の文書ＩＤ，単語の出現回数、単語の出現位置を含む。

予測ルール記憶部７０は、予測式１計算部３０、予測式計算部４０、予測式３計算部５０で用いる文書数予測のためのルールを格納する。

上記の構成における動作を説明する。

図４は、本発明の一実施の形態における文書数予測装置の動作のフローチャートである。

ステップ１０１） 予め、処理する転置インデックスの割合を文書数予測装置のメモリ（図示せず）に設定する。

ステップ１０２） クエリ入力部１０は、入力された複合語を形態素解析し、単一の単語に分割する。

ステップ１０３） 文書数予測部２０は、分割されたそれぞれの単語に対する転置インデックスを転置インデックス記憶部６０から読み出す。

ステップ１０４） 文書数予測部２０は、ステップ１０３で読み出した転置インデックスにより各単語に対する文書数ｄｆを計数し、当該文書数において、最も文書数の小さい単語を選出し、ここでは単語ａとする。反対に、文書数の小さい単語を単語ｂとする。また、単語ａの文書数ｄｆ１、単語ｂの文書数をｄｆ２とする。

ステップ１０５） ステップ１０４で選出した単語ａの転置インデックスに対して、ステップ１０１でメモリ（図示せず）に格納されている割合に基づいて、サーチする文書数を決定する。ここで決定した文書数をＮとする。

ステップ１０６） ステップ１０４で選出した単語ａの転置リストから、ステップ１０５で決定したＮ個分の、単語ａの転置インデックスの先頭からの単語の出現位置を基に入力されたクエリの複合語を含む文書数を探索する。このとき検出した複合語を含む文書数をＤ、単語ａでサーチしたインデックス数をｓ１、単語ｂでサーチしたインデックス数をｓ２とする。

ステップ１０７） 文書数予測部２０は、ｓ１／ｓ２が、"１．０"よりも大きい場合は、ステップ１０８に移行し、そうでなければステップ１０９に移行する。

ステップ１０８） 予測式１計算部３０は、条件（ｓ１／ｓ２＞１．０）に基づいて予測ルール記憶部７０から以下の予測式１を取得し、複合語の文書数を予測し、出力する。

予測式１＝Ｄ／（ｓ２／（ｄｆ１−ｓ１＋ｓ２））
ステップ１０９） ｓ１／ｓ２とｄｆ１／ｄｆ２を比較し、ｓ１／ｓ２＜ｄｆ１／ｄｆ２である場合は、ステップ１１０に移行し、ｓ１／ｓ２≧ｄｆ１／ｄｆ２である場合はステップ１１１に移行する。

ステップ１１０） 予測式２計算部４０は、条件（ｓ１／ｓ２＞１．０かつ、ｓ１／ｓ２＜ｄｆ１／ｄｆ２）に基づいて予測ルール記憶部７０から以下の予測式２を取得し、複合語の文書数を予測し出力する。

予測式２＝Ｄ／（ａ１／ｄｆ１）×（１．０−（（ｓ１／ｓ２）／（ｄｆ１／ｄｆ２）））
ステップ１１１） 予測式３計算部５０は、条件（ｓ１／ｓ２＞１．０、かつ、１／ｓ２≧ｄｆ１／ｄｆ２）に基づいて予測ルール記憶部７０から以下の予測式３を取得し、複合語の文書数を予測し出力する。

予測式３＝Ｄ／（ｓ１／ｄｆ１）

以下に、上記の実施の形態で述べた文書数予測装置の具体的な動作を図４のフローチャートに沿って説明する。

以下の実施例では、転置インデックス記憶部６０には、単語名として「太陽」、「エネルギー」に関する転置インデックス情報が格納されているものとして説明する。

クエリ入力部１０にクエリとして、複合語「太陽エネルギー」が入力されると、「太陽エネルギー」を形態素解析し、「太陽」、「エネルギー」の２つの単語に分割する。次に、「太陽」、「エネルギー」を文書数予測部２０に転送する（ステップ１０１）。

文書数予測部２０は、「太陽」、「エネルギー」の単語を取得すると、「太陽」、「エネルギー」の２つの単語に関する転置インデックス情報を転置インデックス記憶部６０から読み出す（ステップ１０２）。ここで、読み出した転置インデックス情報の例を図９に示す。同図では、文書内に「太陽」、「エネルギー」の単語を含んでいる文書に関する転置インデックスとして、各文書に対する文書ＩＤ、出現回数、出現位置が格納されている。

次に、文書数予測部２０は、「太陽」、「エネルギー」の各転置インデックスに対し、文書ＩＤ毎に「太陽エネルギー」の単語を含む文書を探索する（ステップ１０３）。まず、始めに、文書ＩＤが「Doc1」の文書に対して「太陽エネルギー」の複合語が文書に含まれるかを探索するために、「太陽」の転置インデックスから「太陽」の単語の出現位置を抽出する。ここでは、図９より「１」を取り出す。次に、「エネルギー」の転置インデックスから「１」よりも大きく、かつ、最小の出現位置を抽出する。ここでは、「２」が取り出される。「太陽」の出現位置「１」、「エネルギー」の出現位置「２」が連続しているため、「太陽エネルギー」が当該文書（文書ＩＤ「Doc1」）内に出現することを検知する。文書ＩＤ「Doc1」で「太陽エネルギー」が検出されたため、次の文書に対して同様の処理を行う。

本実施例での「太陽エネルギー」を含む文書群の検出状況を図５に示す。図５では、１つの長方形が文書の転置インデックスを表しており、「○」が付いているのは文書内に「太陽エネルギー」を含む文書であることを示す（ステップ１０４）。

本実施例では、文書数の小さい「太陽」の転置インデックスの先頭から４件サーチする。本実施例では、図６の例のように「太陽」の文書数（ｄｆ１）が１０とすると、転置インデックスの先頭の４文書をサーチする。このとき、４文書中１文書（Ｄ＝１）見つかったものとする（図６の○の付いている文書）。

この例では、「太陽」をサーチした文書数ｓ１が"４"、「エネルギー」をサーチした文書数ｓ２が"２"となり（ステップ１０５，１０６）、２つの転置インデックスをサーチした文書数の比（４／２）が１．０以上のため（ステップ１０７）、予測式１計算部３０において下記の予測式により文書数を予測する（ステップ１０８）。

予測文書数＝Ｄ／（ｓ２／（ｄｆ１−ｓ１＋ｓ２））
＝１／（２／（１０−４＋２））
＝４
上記を「太陽エネルギー」の予測文書数とする。

次に、図７の例のように、複合語「太陽エネルギー」に関する文書の文書数を予測する場合について説明する。同図の例では、「太陽」の文書数が"１０"、「エネルギー」の文書数が"１１"であり（ステップ１０３）、文書数小さい「太陽」の転置インデックスに対して（ステップ１０４）、先頭の２文書をサーチし（ステップ１０５，１０６）、「太陽エネルギー」を含む文書が１つ（Ｄ＝１）見つかったものとする。

図７の例では、「太陽」をサーチした文書数ｓ１が"２"、「エネルギー」でサーチした文書数ｓ２が"７"となり、２つの転置インデックスをサーチした文書の比が２／７で１．０未満であり（ステップ１０７）、さらに、２つの単語のＤＦ比（１０／１１）が２つの転置インデックスをサーチした文書の比（２／７）よりも大きいため（ステップ１０９）、予測式２計算部４０において下記の予測式により文書数を予測する（ステップ１１０）。

予測文書数＝Ｄ／（ｓ１／ｄｆ１）×（１．０−（（ｓ１／ｓ２）／（ｄｆ１／ｄｆ２）））
＝１／（２／１０）×（１．０−（（２／７）／（１０／１１）））
＝１／（１／５）×（１．０−０．３１４３）
＝１／（１／５）×０．６８５７
＝３．４２８５
上記を「太陽エネルギー」の予測文書数とする。

次に、図８の例のように複合語「太陽エネルギー」に関する文書の文書数を予測する場合について説明する。同図の例では、「太陽」の文書数が"６"、「エネルギー」の文書数が"１６"であり、文書数の小さい「太陽」の転置インデックスに対して、先頭の２文書をサーチし、「太陽エネルギー」を含む文書が１つ見つかったものとする（ステップ１０３〜１０４）。

この例では、「太陽」をサーチした文書数ｓ１が"２"、「エネルギー」をサーチした文書数ｓ２が"３"となり（ステップ１０５）、２つの転置インデックスをサーチした文書の比（２／３）が１．０未満であり（ステップ１０７）、さらに、２つの単語のＤＦ比（６／１６）が２つの転置インデックスをサーチした文書の比（２／３）よりも小さいため（ステップ１０９）、予測式３計算部５０において下記の予測式により文書数を予測する（ステップ１１１）。

予測文書数＝Ｄ／（ｓ１／ｄｆ１）
＝１／（２／６）
＝３
上記を「太陽エネルギー」の予測ＤＦとする。

なお、上記の図３に示す文書数予測装置の構成要素の動作をプログラムとして構築し、文書数予測装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。

本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更、応用が可能である。

１０ 単語分割手段、クエリ入力部
２０ 文書数予測部
２１ 転置インデックス取得手段
２２ 文書数算出手段
３０ 予測式１計算部
４０ 予測式２計算部
５０ 予測式３計算部
６０ 転置インデックス記憶手段、転置インデックス記憶部
７０ 予測ルール記憶部
１００ 予測値算出手段

Claims (7)

1. 文書検索における複合語に対する文書数予測装置であって、
   単語名毎に、該単語を含んでいる文書ＩＤ、単語の出現回数、単語の出現位置を含む転置インデックスを格納した転置インデックス記憶手段と、
   ユーザから入力されたクエリが複合語の場合に複合語を単一の単語に分割する単語分割手段と、
   分割された単語に基づいて前記転置インデックス記憶手段を参照して、分割した単語それぞれに対する転置インデックスを抽出する転置インデックス取得手段と、
   予め設定した文書数を対象として、抽出された前記転置インデックスから抽出した複合語を含む文書数を算出する文書数算出手段と、
   検出した複合語を含む文書数と前記転置インデックス取得手段で取得した各単語を含む文書数に基づいて、文書数予測ルールを用いて全文書に対する複合語を含む文書数の予測値を算出する予測値算出手段と、
   を有することを特徴とする文書数予測装置。
2. 前記文書数予測ルールは、
   複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも大きい場合は、単独文書数比を用いて予測する文書数を小さく補正するルールを含む
   請求項１記載の文書数予測装置。
3. 前記文書数予測ルールは、
   複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも小さい場合は、単独文書数比を用いて予測する文書数を大きく補正するルールを含む
   請求項１記載の文書数予測装置。
4. 文書検索における複合語に対する文書数予測方法であって、
   単語名毎に、該単語を含んでいる文書ＩＤ、単語の出現回数、単語の出現位置を含む転置インデックスを格納した転置インデックス記憶手段と、
   文書数予測ルールを格納したルール記憶手段と、を有する装置が、
   ユーザから入力されたクエリが複合語の場合に複合語を単一の単語に分割する単語分割ステップと、
   分割された単語に基づいて前記転置インデックス記憶手段を参照して、分割した単語それぞれに対する転置インデックスを抽出する転置インデックス取得ステップと、
   予め設定した文書数を対象として、抽出された前記転置インデックスから抽出した複合語を含む文書数を算出する文書数算出ステップと、
   検出した複合語を含む文書数と前記転置インデックス取得ステップで取得した各単語を含む文書数に基づいて、文書数予測ルールを用いて全文書に対する複合語を含む文書数の予測値を算出する予測値算出ステップと、
   を行うことを特徴とする文書数予測方法。
5. 前記予測値算出ステップにおいて、
   複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも大きい場合は、単独文書数比を用いて予測する文書数を小さく補正する前記文書数予測ルールを用いる
   請求項４記載の文書数予測方法。
6. 前記予測値算出ステップにおいて、
   複合語を含む文書を検出する際に、各単語の転置インデックスを探索した文書数比が単独の単語の文書数比よりも小さい場合は、単独文書数比を用いて予測する文書数を大きく補正する前記文書数予測ルールを用いる
   請求項４記載の文書数予測方法。
7. 請求項１乃至３のいずれか１項に記載の文書数予測装置を構成する各手段としてコンピュータを機能させるための文書数予測プログラム。

Images