(57)【要約】【課題】  パッセージの長さに制限を設けることなく、与えられた検索語が集中的に出現するパッセージを効率良く検索するパッセージ検出装置を提供することを目的とする。【解決手段】  パッセージ検索装置は、文書を検索するための前処理を行う索引作成手段１０と、パッセージ検索を行う文書を選択する文書検索手段２０と、選択した文書に対して、検索語の出現分布を考慮した評価を行う文書精査手段３０と、検索の対象となる文書を格納する文書DB４０と、索引作成手段１０が生成した各リストを格納するリストDB５０と、文書検索手段２０が選択した上位文書を格納する上位文書DB６０と、文書精査手段３０が行ったパッセージの評価結果を格納するパッセージ評価DB７０と、検索作成手段１０が選択した文書を格納する選択文書DB８０とから構成される。【選択図】      図１
2005301444.tif 000002
【特許請求の範囲】
【請求項１】
複数の文書の中から与えられた検索語をより集中的に含むパッセージを検索するパッセージ検索方法であって、
文書を検索するための前処理を行う索引作成手段が、複数の文書の中から所定の条件を満たす文書を選択し、選択した文書の中に出現した単語ごとに、その単語が出現した文書を記載した出現文書リストと、前記選択した文書の中で前記単語が出現した位置を記載した出現位置リストと、前記単語が出現した文書の数を記載したDF値リストとを作成する手順と、
検索を行う文書の数を制限する文書検索手段が、所定の方法を用いて前記選択した文書の評価を行い、評価結果の上位から所定の数の文書を選択し、上位文書とする手順と、
前記検索語を文書中で出現した順に並べる併合整列手段が、前記上位文書に記載された前記検索語のうち、同義語であると指定された複数の検索語のうちの一つの検索語に同義語である他の検索語を変更し、同義語である他の検索語の出現位置リストを前記一つの検索語の出現位置リストに統合した後、前記出現位置リストに記載された前記上位文書の中で前記検索語が出現した位置にもとづいて、前記上位文章に記載されたすべての検索語を出現した順に並べて全出現位置リストとする手順と、
前記全出現位置リストの中で評価を行うパッセージを切り出す窓を作成する窓作成手段が、前記全出現位置リストの中で、前記検索語が出現した順に少なくとも一回出現する最初で最小の範囲であって、最初に出現した検索語の位置を左端とし、最後に出現した他の検索語の位置を右端とする窓を作成する手順と、
対象とする検索語を減らさずに窓を移動する窓移動手段が、前記全出現位置リストの中の前記窓の左端より右側の範囲について、前記窓の左端に存在する検索語と同じ検索語が、前記窓の範囲内に他にも存在する場合には、前記窓の左端を右に一語分だけ動かして前記窓の左端に存在する検索語を範囲外とする新しい窓を作成し、前記窓の左端に存在する検索語と同じ検索語が、前記窓の範囲内にはないが範囲外にある場合には、前記窓の左端を右に一語分だけ動かして前記窓の左端に存在する検索語を前記窓の範囲外にすると共に、前記窓の右端を前記窓の範囲外にある検索語の位置まで動かした新しい窓を作成する手順と、
前記窓が切り出したパッセージを評価するパッセージ評価手段が、前記全出現位置リストから前記新しい窓を用いてパッセージを切りだし、切り出したパッセージを評価する手順と
を実行することを特徴とするパッセージ検索方法。
【請求項２】
前記文書検索手段による前記選択した文書の評価は、
選択した文書に出現する各検索語について、全文書数を前記検索語が出現した文書の数で割った値の１０を底とする対数の値を求め、求めた各検索語の値をすべて加算した値にもとづいて行われること
を特徴とする請求項１に記載のパッセージ検索方法。
【請求項３】
前記パッセージ評価手段による前記窓を用いて切り出したパッセージの評価は、
前記窓が切り出したパッセージの右端の検索語と同じ検索語が、前記パッセージの中に他にも存在するか否かを判断し、存在する場合、前記パッセージの右端の検索語を削除し、存在しない場合、前記パッセージの右端の検索語の重みを各検索語の重みの和に加え、前記各検索語の重みの和から前記窓が切り出したパッセージの評価を計算し、計算した評価と先に計算した評価とを比較して、前記計算した評価が前記先に計算した評価より大きい場合、前記先に計算した評価に代えて前記計算した評価を新しい先に計算した評価とし、パッセージの右端の検索語を削除し、パッセージの検索語の数を１だけ減らし、削除後のパッセージの中に他の検索語が存在するか否かを判断し、他の検索語がない場合、前記新しい先に計算した評価を前記窓が切りだしたパッセージの評価結果とすること
を特徴とする請求項１に記載のパッセージ検索方法。
【請求項４】
複数の文書の中から与えられた検索語をより集中的に含むパッセージを検索するパッセージ検索装置であって、
複数の文書の中から所定の条件を満たす文書を選択し、選択した文書の中に出現した単語ごとに、その単語が出現した文書を記載した出現文書リストと、前記選択した文書の中で前記単語が出現した位置を記載した出現位置リストと、前記単語が出現した文書の数を記載したDF値リストとを作成する索引作成手段と、
所定の方法を用いて前記選択した文書の評価を行い、評価結果の上位から所定の数の文書を選択し、上位文書とする文書検索手段と、
前記上位文書に記載された前記検索語のうち、同義語であると指定された複数の検索語のうちの一つの検索語に同義語である他の検索語を変更し、同義語である他の検索語の出現位置リストを前記一つの検索語の出現位置リストに統合し、前記出現位置リストに記載された前記上位文書の中で前記検索語が出現した位置にもとづいて、前記上位文章に記載されたすべての検索語を出現した順に並べて全出現位置リストとする併合整列手段と、
前記全出現位置リストの中で、前記検索語が出現した順に少なくとも一回出現する最初で最小の範囲であって、最初に出現した検索語の位置を左端とし、最後に出現した他の検索語の位置を右端とする窓を作成する窓作成手段と、
前記全出現位置リストの中の前記窓の左端より右側の範囲について、前記窓の左端に存在する検索語と同じ検索語が、前記窓の範囲内に他にも存在する場合には、前記窓の左端を右に一語分だけ動かして前記窓の左端に存在する検索語を範囲外とする新しい窓を作成し、前記窓の左端に存在する検索語と同じ検索語が、前記窓の範囲内にはないが範囲外にある場合には、前記窓の左端を右に一語分だけ動かして前記窓の左端に存在する検索語を前記窓の範囲外にすると共に、前記窓の右端を前記窓の範囲外にある検索語の位置まで動かした新しい窓を作成する窓移動手段と、
前記全出現位置リストから前記新しい窓を用いてパッセージを切りだし、切り出したパッセージを評価するパッセージ評価手段と
を備えたことを特徴とするパッセージ検索装置。
【請求項５】
請求項１に記載のパッセージ検索方法をコンピュータに実行させることを特徴とするパッセージ検索プログラム。
【請求項６】
請求項１に記載のパッセージ検索方法をコンピュータに実行させるプログラムを記録したコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は与えられた検索語にしたがって文書を検索する文書検索方法、装置、プログラムおよび記録媒体に関する。特に、与えられた検索語が集中的に出現するパッセージ（文断片）を検索するパッセージ検索方法、パッセージ検索装置、パッセージ検索プログラムおよびパッセージ検索プログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
通常の文書検索では、ある検索語の出現頻度の高い文書は、その検索語について詳しく述べているとみなされ、検索するに際して高い評価を得る。しかし、例えば、質問応答においては、一つの文中に検索語が何度も出現しても、答えが近くに存在するとの指標にはならない。文中に検索語が一度出現すれば、答えを得るには充分だからである。
【０００３】
そこで、検索語の出現回数は考えず、多くの異なる検索語がなるべく集中的に出現するパッセージがふさわしいと考え、そのパッセージを検索するパッセージ検索が実現されている。
【０００４】
例えば、パッセージ検索は、オープンドメイン質問回答システムにおいて、利用者が与えた質問の回答を含む可能性の高い文書の中の、特に回答が現れそうな部分を特定する際に利用されている（特許文献１を参照）。
【０００５】
パッセージ検索は以下のように行われる。文書を、例えば、３文づつあるいは３００語づつに区切り、その区間を幅とする「窓」を考える。ここで、「窓」とは文書の任意の区間を切り出す機能を備えるものである。次に、その窓が切り出した区間に含まれる単語列をパッセージとし、窓を少しづつ(例えば、１文づつ、あるいは、１０語づつなど）移動させながら、切り出したパッセージを一つづつ評価していく。
【０００６】
評価には、以下に示す代表的な２つの方法がある。いずれもパッセージに点数を付与して評価を行っている。
【０００７】
第１の方法は、TF-IDFなどの検索語の出現頻度にもとづく文書検索の方法である。この方法は、パッセージ中の検索語の出現分布を考慮していないので、パッセージの長さを必要以上に長くすると、普通の文書検索の方法と同等な方法となってしまうという問題がある。その結果、パッセージ検索の特徴である単語の出現分布を反映した検索結果を得ることはできない。
【０００８】
第２の方法は、パッセージ中に出現する検索語の分布（例えば、検索語間の距離など）を考慮した関数を利用して文書検索を行う方法である。この方法は、パッセージが広範囲になるにしたがい、パッセージ中に含まれる検索語の数が増加するため、処理に時間を要すとの問題があり、逆に、パッセージの範囲を狭くすると、検索語の多くがパッセージの範囲外に出てしまうとの問題がある。このため、パッセージの適切な長さを経験的に決める必要がある。
【０００９】
これらの方法に対して、文書を特定の長さの区間に区切るのではなく、検索語がすべて含まれる最小の区間を見つけ出してパッセージとし、そのパッセージの評価を行う方法が考えられる。しかし、この方法は、通常、効率が非常に悪い。例えば、１０００文から構成される一つの文書があり、その中の最後の１文だけに検索語が出現している場合を考える。この文書に対して、先頭から1文づつ取り出し、窓を移動させながら窓の中のパッセージを評価して点数を付与していくと、最後の１文に至る直前まで点数はゼロである。
【００１０】
この問題を解決するために、予め文書の中の単語の出現分布を調べておき、検索語の出現頻度の高い文だけを選び出し、その文の中で窓を移動させて評価を行うことにより、窓の無駄な移動と必要のない評価をなくす方法が提案されている（非特許文献１を参照）。この方法は、文書を特定の長さで区切る方法ではなく、文書全体を対象とした方法なので、パッセージの長さに制限がなく、しかも、検索語の出現分布が高い部分を短時間で見つけ出すことができる。
【特許文献１】特開２００２−１３２８１１号公報（段落００４４）
【非特許文献１】K.Sadakane and H.Imai、“Fast Algorithms for k-word Proximity Search”、IEICE Transactions on Communications Electronics Information and Systems、Vol.E84-A、No.9、pp.312-319、2001年
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、前記した方法には、すべての検索語を含まない文書は対象外となってしまうという問題がある。この方法を質問応答システムに応用し、利用者が入力する質問に含まれる単語をすべて検索語として採用した場合、条件が強すぎて、回答を含む文を検索で得られない可能性がきわめて強くなる。
【００１２】
また、例えば、８つの検索語が与えられており、そのうちの７つの検索語が長い文書の始めの文に集中して出現しており、残りの１つの検索語が文書の最後の文に出現している場合、前記した方法では、文書全体がパッセージとして切り出されてしまい、その結果、検索語が集中的に現れる部分がわからなくなってしまうという問題がある。
【００１３】
本発明は、このような問題に鑑みなされたものであり、パッセージの長さに制限を設けることなく、与えられた検索語が集中的に出現するパッセージを効率良く検索するパッセージ検出方法とパッセージ検出装置とパッセージ検出プログラムおよびパッセージ検出プログラムを記録した記録媒体とを提供することを目的とする。
【００１４】
なお、「集中的」とは、与えられたすべての検索語が、より短いパッセージに出現する状態を示している。
【課題を解決するための手段】
【００１５】
前記した課題を解決するため、本発明では、以下のような方法、装置、プログラム及びプログラムを記録した記録媒体を用いることとした。
【００１６】
請求項１に記載の発明では、パッセージ検索方法の文書を検索するための前処理を行う索引作成手段が、複数の文書の中から所定の条件を満たす文書を選択し、選択した文書の中に出現した単語ごとに、その単語が出現した文書を記載した出現文書リストと、選択した文書の中で単語が出現した位置を記載した出現位置リストと、単語が出現した文書の数を記載したDF値リストとを作成し、検索を行う文書の数を制限する文書検索手段が、所定の方法を用いて選択した文書の評価を行い、評価結果の上位から所定の数の文書を選択して上位文書とし、検索語を文書中で出現した順に並べる併合整列手段が、上位文書に記載された検索語のうち、同義語であると指定された複数の検索語のうちの一つの検索語に同義語である他の検索語を変更し、同義語である他の検索語の出現位置リストを一つの検索語の出現位置リストに統合した後、出現位置リストに記載された上位文書の中で検索語が出現した位置にもとづいて、上位文章に記載されたすべての検索語を出現した順に並べて全出現位置リストとし、全出現位置リストの中で評価を行うパッセージを切り出す窓を作成する窓作成手段が、全出現位置リストの中で、検索語が出現した順に少なくとも一回出現する最初で最小の範囲であって、最初に出現した検索語の位置を左端とし、最後に出現した他の検索語の位置を右端とする窓を作成し、対象とする検索語を減らさずに窓を移動する窓移動手段が、全出現位置リストの中の窓の左端より右側の範囲について、窓の左端に存在する検索語と同じ検索語が、窓の範囲内に他にも存在する場合には、窓の左端を右に一語分だけ動かして窓の左端に存在する検索語を範囲外とする新しい窓を作成し、窓の左端に存在する検索語と同じ検索語が、窓の範囲内にはないが範囲外にある場合には、窓の左端を右に一語分だけ動かして窓の左端に存在する検索語を窓の範囲外にすると共に、窓の右端を窓の範囲外にある検索語の位置まで動かした新しい窓を作成し、窓が切り出したパッセージを評価するパッセージ評価手段が、全出現位置リストから新しい窓を用いてパッセージを切りだし、切り出したパッセージを評価することとした。
【００１７】
請求項１に記載の発明は、パッセージを検索するアルゴリズムをより少ない計算量で効率良く実現するものである。そのために、計算結果が同じになることが明白な場合については計算を行わないようにしている。また、パッセージを切り出す範囲に制限を加えていないため、すべての検索語を含むパッセージを柔軟に見つけ出し、それを評価することによって、より評価結果の高いパッセージを検出できる。
【００１８】
請求項２に記載の発明では、文書検索手段による選択した文書の評価は、選択した文書に出現する各検索語について、全文書数を検索語が出現した文書の数で割った値の１０を底とする対数の値を求め、求めた各検索語の値をすべて加算した値にもとづいて行われることとした。
【００１９】
前記した選択した文書を評価する方法は一例であり、他の方法を用いることも可能である。
【００２０】
請求項３に記載の発明では、パッセージ評価手段による窓を用いて切り出したパッセージの評価は、窓が切り出したパッセージの右端の検索語と同じ検索語が、パッセージの中に他にも存在するか否かを判断し、存在する場合、パッセージの右端の検索語を削除し、存在しない場合、パッセージの右端の検索語の重みを各検索語の重みの和に加え、各検索語の重みの和から窓が切り出したパッセージの評価を計算し、計算した評価と先に計算した評価とを比較して、計算した評価が先に計算した評価より大きい場合、先に計算した評価に代えて計算した評価を新しい先に計算した評価とし、パッセージの右端の検索語を削除し、パッセージの検索語の数を１だけ減らし、削除後のパッセージの中に他の検索語が存在するか否かを判断し、他の検索語がない場合、新しい先に計算した評価を窓が切りだしたパッセージの評価結果とすることとした。
【００２１】
前記した窓が切り出したパッセージを評価する方法は一例であり、また、評価を効率良く実現する方法を示している。
【００２２】
請求項４に記載の発明では、パッセージ検索装置が、複数の文書の中から所定の条件を満たす文書を選択し、選択した文書の中に出現した単語ごとに、その単語が出現した文書を記載した出現文書リストと、選択した文書の中で単語が出現した位置を記載した出現位置リストと、単語が出現した文書の数を記載したDF値リストとを作成する索引作成手段と、所定の方法を用いて選択した文書の評価を行い、評価結果の上位から所定の数の文書を選択し、上位文書とする文書検索手段と、上位文書に記載された検索語のうち、同義語であると指定された複数の検索語のうちの一つの検索語に同義語である他の検索語を変更し、同義語である他の検索語の出現位置リストを一つの検索語の出現位置リストに統合し、出現位置リストに記載された上位文書の中で検索語が出現した位置にもとづいて、上位文章に記載されたすべての検索語を出現した順に並べて全出現位置リストとする併合整列手段と、全出現位置リストの中で、検索語が出現した順に少なくとも一回出現する最初で最小の範囲であって、最初に出現した検索語の位置を左端とし、最後に出現した他の検索語の位置を右端とする窓を作成する窓作成手段と、全出現位置リストの中の窓の左端より右側の範囲について、窓の左端に存在する検索語と同じ検索語が、窓の範囲内に他にも存在する場合には、窓の左端を右に一語分だけ動かして窓の左端に存在する検索語を範囲外とする新しい窓を作成し、窓の左端に存在する検索語と同じ検索語が、窓の範囲内にはないが範囲外にある場合には、窓の左端を右に一語分だけ動かして窓の左端に存在する検索語を窓の範囲外にすると共に、窓の右端を窓の範囲外にある検索語の位置まで動かした新しい窓を作成する窓移動手段と、全出現位置リストから新しい窓を用いてパッセージを切りだし、切り出したパッセージを評価するパッセージ評価手段とを備えることとした。
【００２３】
パッセージ検索方法を装置で実現している。
【発明の効果】
【００２４】
請求項１と請求項４に記載の発明によれば、複数の文書の中から与えられた検索語が集中的に出現するパッセージを、パッセージの長さに制限を設けることなく、より少ない計算量で効率良く検索することが可能となる。
【００２５】
請求項２に記載の発明によれば、検索の対象となる文書の選択を、数式で示される客観的な基準にもとづいて行うことが可能となる。
【００２６】
請求項３に記載の発明によれば、パッセージ検索方法で評価しなくてはならないパッセージの数は、従来は全出現位置リストの要素数の２乗のオーダーであったものを、より少ない全出現位置リストの要素数と検索語数との積とすることができ、これによりパッセージ検索方法の計算量を大幅に削減することが可能となる。
【００２７】
請求項５に記載の発明によれば、パッセージ検索方法をプログラムで記述することにより、パッセージ検索方法をコンピュータで実現することが可能となる。
【００２８】
請求項６に記載の発明によれば、パッセージ検索プログラムを記録媒体に記録して、それをコンピュータに読み込ませることにより、特定のコンピュータに限定されることなく、パッセージ検索方法を実現することが可能となる。
【発明を実施するための最良の形態】
【００２９】
本発明の実施形態について、適宜、図面を参照しながら詳細に説明する。
図１は、本発明の実施形態に係るパッセージ検索装置の構成を示す図である。パッセージ検索装置は、高速に文書を検索するための前処理を行う索引作成手段１０と、すべての文書の中から、パッセージ検索を行う文書を選択する文書検索手段２０と、文書検索手段２０が選択した文書に対して、検索語の出現分布を考慮した評価を行う文書精査手段３０と、検索の対象となる文書を格納する文書データベース（DB）４０と、索引作成手段１０が生成した各リストを格納するリストデータベース（DB）５０と、文書検索手段２０が選択した上位文書を格納する上位文書データベース（DB）６０と、文書精査手段３０が行ったパッセージの評価結果を格納するパッセージ評価データベース（DB）７０と、検索作成手段１０が文書DB４０から選択した文書を格納する選択文書データベース（DB）８０とから構成される。
【００３０】
索引作成手段１０は、文書DB４０に格納されている文書の中から所定の条件を満たす文書を選択して選択文書DB８０に格納した後、選択した文書の中に出現した単語ごとに、単語が出現した文書を記載したリスト（以後、「出現文書リスト」と略称する）と、選択した文書の中で単語が出現した位置を記載したリスト（以後、「出現位置リスト」と略称する）を作成する。これは従来から行われている方法と同じである。また、その単語が出現した文書の数（DF値）のリスト（以後、「DF値リスト」と略称する）を作成する。さらに、必要であれば、文書に各単語が出現した数（TF値）のリスト（以後、「TF値リスト」と略称する）を作成する。
【００３１】
文書検索手段２０は、所定の方法を用いて前記した選択した文書の評価を行い、評価結果の上位から所定の数の文書をさらに選択する。評価は、例えば、DF値を利用した評価関数：各検索語のidf（=log（全文書数／DF値））の和  を用いて選択した文書に点数を付与することにより行われる。その評価結果の上位から予め定められた件数（例えば、１０００件）だけ文書を選択する。
【００３２】
文書精査手段３０は、文書検索手段２０が選択した文書について評価を行う。次に、文書精査手段３０について詳しく説明する。
【００３３】
図２は、本発明の実施形態に係る文書精査手段３０の構成を示す図である。文書精査手段３０は、与えられた検索語を文書の中での出現順に並べた全出現位置リストを作成する併合整列手段３１と、作成した全出現位置リストの中で評価を行う区間を切り出す窓を生成する窓作成手段３２と、対象とする検索語を減らさずに効率良く窓を移動する窓移動手段３３と、窓に切り出されたパッセージを評価するパッセージ評価手段３４とから構成される。
【００３４】
併合整列手段３１は、各検索語の出現位置リストから、各検索語を文書中で出現した順に並べた「全出現位置リスト」を作成する。ここでは全出現位置リストを検索語が出現した順に左から右へ表示するものとする。
【００３５】
窓作成手段３２は、併合整列手段３１が作成した全出現位置リストの中で、与えられたすべての検索語が出現した順に少なくとも一回出現する最初の最小の区間を、パッセージを切り出す最初の窓とする。また、全出現位置リストの中で検索語が出現した順に、窓を左から右に表示することとすると、最も早く出現した検索語の位置を窓の「左端」と呼び、最も遅く出現した検索語の位置を窓の「右端」と呼ぶことができる。
【００３６】
窓を全出現位置リスト上で左から右に移動させる場合、左端にある検索語と同じ検索語が窓内に他にも存在する場合、窓の左端を右に一語分だけ移動させ、窓の左端の検索語を窓の範囲外としても、窓の範囲内のある検索語の数は変わらない。この場合に検索語の密集度を考えると、左端にあった検索語を窓の範囲外とする前の密集度よりも、左端にあった検索語を窓の範囲外とした後の密集度の方が高い。本発明の目的は、与えられた検索語が集中的に出現するパッセージを効率良く検索することであるから、より高い密集度のパッセージが存在するならば、密集度が低いパッセージを考慮する必要はない。このことから、検索語が窓の範囲内の左端のみに存在し、他には存在しない場合だけ、評価を行えばよいこととなる。窓移動手段３３は、前記した考え方にしたがい、対象とする検索語の数を減らさずに効率良く窓を全出現位置リスト上で移動する。
【００３７】
パッセージ評価手段３４は、全出現位置リスト上を移動した窓が切り出したパッセージを、検索語の密度を示す指標を用いて評価する。
【００３８】
パッセージ評価手段３４は、評価方法として様々な方法を用いることができるが、以下の条件を満足する必要がある。
「検索語の出現する位置で左端と右端を指定されたパッセージpが、パッセージqに真に含まれており（p⊂q）、しかも、pとqを含む検索語の集合k(p)とk(q)が同じである（k(p)=k(q)）とき、パッセージの評価結果であるscoreは、score(p)＞score(q)となる。」
【００３９】
つまり、「パッセージpがパッセージqの一部分であり、パッセージpとパッセージqとは同じ検索語の集合に含まれているときには、パッセージの評価は、パッセージpの方がパッセージqよりも大きくなる」という条件を満足しなくてはならない。
【００４０】
この条件を満たす評価方法には、例えば、（１）式で示されるようなパッセージpに含まれる各検索語wの重みW(w)の和をパッセージpの長さで減衰させた関数を用いた方法ある。
【００４１】
【数１】
2005301444.tif 000003
【００４２】
ここで、cはパッセージpの長さによる減衰係数であり、k(p)はパッセージpに含まれる検索語の集合である。また、length(p)はパッセージpの長さであり、パッセージに出現する全単語の数を用いることができる。同じ検索語wがパッセージｐに複数回出現しても、重みW(w)は一度しか加えない。W(w)には、例えば、前記したidfを利用することができるが、検索語wの品詞や文脈などから定めた別の関数を利用してもよいし、これ以外にも様々な関数を利用することができる。ただし、前記した評価方法の性質についての条件を満足する必要がある。
【００４３】
次に、パッセージ評価手段３４での評価に必要な計算量について説明する。パッセージ評価手段３４が、生成されるすべてのパッセージについて評価を行うには、通常、全出現位置リストに記載されている検索語の数（複数回記載されている場合は、それぞれ数える）の２乗オーダーの計算量が必要となる。これは、全出現位置リストに記載されている検索語に対して、単純にすべてのパターンのパッセージを作成することを考えると、一つの検索語を左端として、それより右に存在する各検索語を右端とするパッセージを作成できることから容易に理解できる。
【００４４】
しかし、実際には、全出現位置リストには同じ検索語が複数回出現することが多い。これを考慮すると、評価する必要があるパッセージの数を全出現位置リストに出現する検索語の数（複数回出現する場合でも、一回と数えることができる）に減少させることができ、その結果、評価に必要な計算量を減らすことが可能となる。その原理を以下に説明する。
【００４５】
全出現位置リストのうち、窓が切り出した検索語列を「親パッセージ」と呼び、この親パッセージに含まれる検索語を、右端から順に一語づつ取り除いて生成される検索語列を「プレフィックスパッセージ」と呼ぶ。
【００４６】
親パッセージから生成されたプレフィックスパッセージの右端の検索語が、右端以外にもプレフィックスパッセージ内に存在している場合、プレフィックスパッセージから右端の検索語を削除しても、プレフィックスパッセージに含まれる検索語の数は変わらない。この場合、プレフィックスパッセージの右端が検索語である場合よりも、プレフィックスパッセージから右端の検索語を除いた場合の方が、検索語の密集度は高い。そうであるならば、検索語の密集度が低くなる右端が検索語が存在するプレフィックスパッセージの評価を行う必要はないことになる。このことは、右端の検索語が他には出現しないプレフィックスパッセージだけ評価を行えばよいことを意味する。また、親パッセージは検索語のみから構成されている。以上より、評価すべきプレフィックスパッセージの数は、検索語の数と同じになる。
【００４７】
また、親パッセージは全出現位置リストを移動する窓と対応しているので、その数は最大でも全出現位置リストに含まれる要素数と同じである。
【００４８】
以上より、全出現位置リストにおいて評価しなければならないプレフィックスパッセージの数は、最大でも  全出現位置リストに出現する要素数×検索語数  となり、計算量は前記した  全出現位置リストに記載されている検索語の数の２乗オーダー  より少なくすることができる。特に、同じ検索語が複数回出現する文書において、大幅に計算量を減少させることが可能となる。
【００４９】
パッセージ検索装置の動作を、図３から図６に示すフローチャートを用いて説明する。なお、パッセージ検索に用いる検索語は、事前に与えられているものとする。
【００５０】
索引作成手段１０は、文書DB４０から所定の条件を満たす文書を選択して読み出し、選択文書DB８０に記録する（ステップＳ１００）。また、索引作成手段１０は、選択した文書に含まれる単語ごとに、単語が出現した文書を記載した出現文書リストと、選択した文書の中で単語が出現した位置を出現順に記載した出現位置リストと、その単語が出現した文書の数（DF値）を記載したDF値リストとを作成し、リストDB５０に記録する。さらに必要な場合には、索引作成手段１０は、選択した文書ごとに、その文書に含まれるそれぞれの単語が出現した回数を記載した出現回数リストを作成し、リストDB５０に記録する（ステップＳ１０１）。
【００５１】
文書検索手段２０は、リストDB５０内のDF値リストから与えられた検索語のDF値を読み出し、検索語ごとにidf（=log（全文書数／DF値））を算出する（ステップＳ１０２）。次に、文書検索手段２０は、選択文書DB８０から、選択した文書を読み出し、読み出した選択した文書の中から検索語を抽出し、抽出した検索語のidfの合計を算出して、選択した文書の評価点とする（ステップＳ１０３）。
【００５２】
文書検索手段２０は、選択文書DB８０内の残りの選択した文書の有無を判断し（ステップＳ１０４）、有る場合（ステップＳ１０４のＹｅｓの場合）、ステップＳ１０３へ戻る。無い場合（ステップＳ１０４のＮｏの場合）、文書検索手段２０は、評価点が高い方から順に選択された文書を並べ、上位から所定の数の選択された文書を上位文書DB６０に記録し、他は廃棄する（ステップＳ１０５）。
【００５３】
以上により、検索語の出現頻度が高い文書が、所定の数だけ得られたこととなる。ただし、この段階では、選択された文書には、すべての検索語が含まれているわけではなく、また、検索語の出現分布も考慮されていない。また、「文書の先頭に出現する単語ほど重要である」との経験則にもとづき、検索語の最初の出現位置により評価点を増減するなどの単純な工夫は行ってもよいが、文書内での複数の検索語の具体的な出現分布までは考慮しない。
【００５４】
文書精査手段３０の併合整列手段３１は、上位文書DB６０から上位文書を任意に選び出し、選び出した上位文書に記載された各検索語の出現位置リストをリストDB５０から読み出す（ステップＳ１０６）。「アメリカ」と「米国」などのように、予め同義語と指定されている複数の検索語が、選び出した上位文書中に記載されている場合、それら同義語については区別する必要がないことから、一つの検索語に統一した上で、それらの出現位置リストを一つに統合する（ステップＳ１０７）。選び出した上位文書中に同義語が無い場合には、ステップＳ１０７は省略できる。
【００５５】
次に、統合した同義語の出現位置リストも含め、選び出した上位文書に含まれる各検索語の出現位置リストを用いて、各検索語を、選び出した文書で記載されている順に並べた一つの全出現位置リストを作成する（ステップＳ１０８）。
【００５６】
文書精査手段３０の窓作成手段３２は、併合整列手段３１が作成した全出現位置リストの中で、与えられたすべての検索語が出現した順に少なくとも一回出現する最初で最小の区間をパッセージを切り出す最初の窓とする（ステップＳ１０９）。
【００５７】
文書精査手段３０のパッセージ評価手段３４は、窓作成手段３２が作成した最初の窓または窓移動手段３３が移動した窓を用いて全出現位置リストからパッセージを切り出し（ステップＳ１１０）、切り出したパッセージについて、前記した評価方法を用いて評価を行い、評価結果をパッセージと対にしてパッセージ評価DB７０に記録する（ステップＳ１１１）。
【００５８】
窓移動手段３３は、窓の右端が全出現位置リストの最後尾要素（最も右の要素）の位置に到達しているか否かを判断する（ステップＳ１１２）。到達している場合（ステップＳ１１２のＹｅｓの場合）、ステップＳ１１７へ進む。
【００５９】
到達していない場合（ステップＳ１１２のＮｏの場合）、窓移動手段３３は、窓の左端に存在する検索語と同じ検索語が、全出現位置リストの中で、窓の左端より右（窓の左端は含まない）にも存在するか否かを判断し（ステップＳ１１３）、存在しないと判断した場合（ステップＳ１１３のＮｏの場合）、ステップＳ１１７へ進む。
【００６０】
存在すると判断した場合（ステップＳ１１３のＹｅｓの場合）、窓移動手段３３は、その検索語が、全出現位置リストの中で、窓の右端より左（窓の右端を含む）、つまり窓の範囲内に存在するか否かを判断し（ステップＳ１１４）、存在すると判断した場合（ステップＳ１１４のＹｅｓの場合）、窓の左端を一語分だけ右へ移動して、作成された窓を移動した窓とし（ステップＳ１１５）、ステップＳ１１０へ戻る。
【００６１】
存在しないと判断した場合（ステップＳ１１４のＮｏの場合）、検索語は窓の右端より右（窓の右端は含まない）、つまり窓の範囲外に存在することになるので、窓移動手段３３は、窓の右端をその検索語の位置まで移動し、窓の左端を一語分だけ右へ移動して、作成された窓を移動した窓とし（ステップＳ１１６）、ステップＳ１１０へ戻る。
【００６２】
窓移動手段３３による、全出現位置リストでの窓の移動の具体例を図８に示す。
全出現位置リストを[a c a d b a d e c a d b c b]とし、各アルファベットが検索語を示すものとする。図８の中で、“（  ）”は窓を示しており、“（  ）”内の区間が、窓で切り出されたパッセージとなる。窓の最も左に存在する検索語（アルファベット）が、窓の「左端」となり、窓の最も右に存在する検索語（アルファベット）が、窓の「右端」となる。
【００６３】
ステップ０では、窓の左端に存在する検索語“a”と同じ検索語が、窓の左端より右（窓の左端は含まない）にも存在するか否かを判断し、存在するので、次に、窓の右端より左（窓の右端を含む）に存在するか否かを判断し、存在するので、窓の左端を一語分だけ右へ移動して、作成された窓を移動した窓とし、移動した窓で切り出した次のパッセージの評価に移る。
【００６４】
ステップ１では、窓の左端に存在する検索語“c”と同じ検索語が、窓の左端より右（窓の左端は含まない）にも存在するか否かを判断し、存在するので、次に、窓の右端より左（窓の右端を含む）に存在するか否かを判断し、存在しないので、窓の右端をその検索語に位置まで移動し、窓の左端を一語分だけ右へ移動して、作成された窓を移動した窓とし、移動した窓で切り出した次のパッセージの評価に移る。
【００６５】
ステップ２では、窓の左端に存在する検索語“a”についてステップ０と同じ処理を行う。ステップ３では、窓の左端に存在する検索語“d”についてステップ０と同じ処理を行う。ステップ４では、窓の左端に存在する検索語“b”についてステップ１と同じ処理を行う。ステップ５では、窓の左端に存在する検索語“a”についてステップ０と同じ処理を行う。ステップ６では、窓の左端に存在する検索語“d”についてステップ０と同じ処理を行う。ステップ７では、窓の左端に存在する検索語“e”についてステップ１と同じ処理を行う。
【００６６】
併合整列手段３１は、上位文書DB６０に記録されたすべての文書について評価が完了したか否かを判断する（ステップＳ１１７）。完了していないと判断した場合（ステップＳ１１７のＮｏの場合）、ステップＳ１０６へ戻る。完了したと判断した場合（ステップＳ１１７のＹｅｓの場合）、パッセージ評価手段３４は、すべての評価結果をパッセージ評価DB７０から読み出し、最も評価結果が高いパッセージを与えられた検索語に対する検索結果として出力し（ステップＳ１１８）、処理を終了する。
【００６７】
次に、パッセージ評価手段３４における評価の動作を、図７に示すフローチャートを用いて説明する。評価関数には前記した（１）式を用い、また、前記した計算量を削減する方法も用いる。なお、図７に示すパッセージ評価手段３４の動作は、ステップＳ１１１の処理内容をより詳細に説明したものである。
【００６８】
評価は、全出現位置リストから窓が切り出したパッセージ（親パッセージ）とそれから生成される各プレフィックスパッセージに対して行われ、それらの評価結果の中で、最も大きな評価結果を得た親パッセージまたはプレフィックスパッセージを、窓が切り出したパッセージの最終的な評価結果とする。なお、各検索語には重みW(w)が予め設定されている。
【００６９】
パッセージ評価手段３４は、まず、パッセージの評価結果DSと、各検索語の重みW(w)の和WSを０に設定する（ステップＳ２００）。また、親パッセージに出現する検索語の数length(p)を数える（ステップＳ２０１）。その際、同じ検索語が複数回出現した場合、それぞれ別の語として数えるものとする。なお、ステップＳ２００とステップＳ２０１は、順序が前後してもよい。
【００７０】
以降の処理では、親パッセージとプレフィックスパッセージを合わせて、単にパッセージpと呼ぶことにする。
【００７１】
パッセージ評価手段３４は、パッセージpの右端の検索語がパッセージpの中に他にも存在するか否かを判断する（ステップＳ２０２）。存在する場合（ステップＳ２０２のＹｅｓの場合）、パッセージ評価手段３４はパッセージpの右端の検索語を削除し、length(p)の値を１だけ減らして（ステップＳ２０３）、ステップＳ２０２へ戻る。存在しない場合（ステップＳ２０２のＮｏの場合）、パッセージ評価手段３４は、パッセージpの右端の検索語の重みW(w)を各検索語の重みの和WSに加え（ステップＳ２０４）、（１）式を計算して得られた値をパッセージpの評価結果Sとする（ステップＳ２０５）。
【００７２】
パッセージ評価手段３４は、得られたパッセージpの評価結果Sと評価結果DSとを比較し、DS＜Sならば、Sを新しいDSとする（ステップＳ２０６）。パッセージ評価手段３４は、パッセージpの右端の検索語を削除し、length(p)の値を１だけ減らす（ステップＳ２０７）。
【００７３】
パッセージ評価手段３４は、削除後のパッセージpの中に、まだ検索語が存在するか否かを判断する（ステップＳ２０８）。まだ、検索語がある場合（ステップＳ２０８のＹｅｓの場合）、ステップＳ２０２へ戻る。もう、検索語がない場合（ステップＳ２０８のＮｏの場合）、最終的に得られたDSを窓が切りだしたパッセージ（親パッセージ）の評価結果とし（ステップＳ２０９）、窓が切りだしたパッセージ（親パッセージ）の評価を終了する。
【００７４】
パッセージ評価手段３４によるパッセージ評価の具体例を図９に示す。
親パッセージを[a c a d b a d e]とし、各アルファベットが検索語を示すものとする。
【００７５】
ステップ０では、親パッセージの右端の検索語“e”がパッセージの中に他にも存在するか否かを判断し、存在しないので、このパッセージは評価する必要があることから、パッセージの右端の検索語の重みW(w)を各検索語の重みの和WSに加え、（１）式を計算して得られた値をパッセージの評価結果Sとし、得られたパッセージの評価結果Sと評価結果DSとを比較し、DS＜Sならば、Sを新しいDSとする。そして、パッセージの右端の検索語を削除し、length(p)の値を１だけ減らし、削除後のパッセージの中に、まだ検索語が存在するか否かを判断し、まだ、検索語があるので、ステップ１へ移る。
【００７６】
ステップ１では、パッセージの右端の検索語“d”がパッセージの中に他にも存在するか否かを判断し、存在するので、このパッセージを評価する必要はないことから、パッセージの右端の検索語を削除し、length(p)の値を１だけ減らし、削除後のパッセージの中に、まだ検索語が存在するか否かを判断し、まだ、検索語があるのでステップ２へ移る。
【００７７】
ステップ２では、パッセージの右端の検索語“a”についてステップ１と同じことを行いステップ３へ移る。ステップ３では、パッセージの右端の検索語“b”についてステップ０と同じことを行いステップ４へ移る。ステップ４では、パッセージの右端の検索語“d”についてステップ０と同じことを行いステップ５へ移る。ステップ５では、パッセージの右端の検索語“a”についてステップ１と同じことを行いステップ６へ移る。ステップ６では、パッセージの右端の検索語“c”についてステップ０と同じことを行いステップ７へ移る。
【００７８】
ステップ７では、パッセージの右端の検索語“a”がパッセージの中に他にも存在するか否かを判断し、存在しないので、このパッセージは評価する必要があることから、パッセージの右端の検索語の重みW(w)を各検索語の重みの和WSに加え、（１）式を計算して得られた値をパッセージの評価結果Sとし、得られたパッセージの評価結果Sと評価結果DSとを比較し、DS＜Sならば、Sを新しいDSとする。そして、パッセージの右端の検索語を削除し、length(p)の値を１だけ減らし、削除後のパッセージの中に、まだ検索語が存在するか否かを判断し、もう、検索語はないので、この親パッセージ[a c a d b a d e]の評価を終了する。
【００７９】
以上により、パッセージ選択装置は、文書から上位文書を選択し、選択した各上位文書の中で、与えられた検索語を出現順に並べた全出現位置リストを作成し、また、全出現位置リストの中で、与えられた検索語が出現順に一度だけ出現する最初で最小の窓を生成し、窓を用いて全出現位置リストからパッセージを切りだし、切り出した各パッセージに対して計算量を削減できる評価方法を適用してその評価を行い、選択した各上位文書の中で、最も評価結果が高いパッセージを与えられた検索語に対する検索結果として得ることができた。
【００８０】
また、パッセージ検索装置時で実現している機能をパッセージ検索方法として実現し、それをプログラムで記述することにより、パッセージ検索方法をコンピュータで実現することが可能となる。さらに、パッセージ検索プログラムを記録媒体に記録して、それをコンピュータに読み込ませることにより、特定のコンピュータに限定されることなく、パッセージ検索方法を実現することが可能となる。
【図面の簡単な説明】
【００８１】
【図１】本発明の実施形態に係るパッセージ検索装置の構成を示す図である。
【図２】本発明の実施形態に係る文書精査手段３０の構成を示す図である。
【図３】パッセージ検索装置の動作を説明するためのフローチャートである。
【図４】パッセージ検索装置の動作を説明するためのフローチャートである。
【図５】パッセージ検索装置の動作を説明するためのフローチャートである。
【図６】パッセージ検索装置の動作を説明するためのフローチャートである。
【図７】パッセージ評価手段の動作を説明するためのフローチャートである。
【図８】全出現位置リスト上での窓の移動の具体例を説明するための図である。
【図９】パッセージ評価手段３４によるパッセージ評価の具体例を説明するための図である。
【符号の説明】
【００８２】
１０    索引作成手段
２０    文書検索手段
３０    文書精査手段
３１    併合整列手段
３２    窓作成手段
３３    窓移動手段
３４    パッセージ評価手段
４０    文書データベース（DB）
５０    リストデータベース（DB）
６０    上位文書データベース（DB）
７０    パッセージ評価データベース（DB）
８０    選択文書データベース（DB）
【図１】
2005301444.tif 000004
【図２】
2005301444.tif 000005
【図３】
2005301444.tif 000006
【図４】
2005301444.tif 000007
【図５】
2005301444.tif 000008
【図６】
2005301444.tif 000009
【図７】
2005301444.tif 000010
【図８】
2005301444.tif 000011
【図９】
2005301444.tif 000012