JPH09223161A - コンピュータ・ベースの文書検索システムにおいて問い合わせ応答を生成する方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】 本発明は、文書検索システムへの問い合わせ
に対する応答を生成する方法および装置を提供する。 【解決手段】 このシステムは、検索中の情報を含む可
能性があるテキストの部分を見つけランク付けすること
によって、情報を求める特定の要求に応答する。システ
ムは、テキストの小さな関連パッセージ（ヒット・パッ
セージと呼ぶ）を見つけ、そのようなパッセージが探索
中の情報に対応する程度の推定に応じてそのようなパッ
セージをランク付けする。所定の１組の規則に応じてそ
れぞれの異なる程度に問い合わせ句と異なる句を検索
し、この差異の程度に基づいて検索された句にペナルテ
ィを課し、優先順位構成問い合わせヒット・リストをユ
ーザに提供することによって、探索中の情報の記述と、
適当な答えを構成することができるテキスト・パッセー
ジの内容との間に出現するパラフレーズ変形例に適応す
るように緩和ランク付け構成が提供される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、文書検索システム
への問い合わせに対する応答を生成する方法および装置
に関する。大規模な文書本体（データベース）から関連
する用語（問い合わせ用語）を探索する際、テキストの
小さな関連パッセージ（「ヒット」または「ヒット・パ
ッセージ」と呼ばれる）を見つけ、それが探索中の情報
をどの程度提供するかの推定値に応じてランク付けする
ことが望ましい。

【０００２】

【従来の技術】文書データベースが非常に大規模なもの
である場合、生成されるヒット・パッセージの数が多す
ぎてユーザの助けとはならない。ユーザが、所望の情報
を見つけ、あるいは、探索中の情報はそのテキストの集
合にはないと合理的に結論できるまでに調べなければな
らないヒット・パッセージの数を最小限に抑える機構が
必要である。

【０００３】この種の特定の「精細」情報アクセスは、
オンライン情報システムにとってますます重要になりつ
つあり、従来型の文書検索技法ではうまく対処されてい
ない。より多くの数の検索される文書を生成する傾向が
ある（小数の語からなる）小規模な問い合わせを使用す
る場合には、この問題はさらに深刻になる。

【０００４】問い合わせと目標（ヒット）パッセージの
サイズが共に小規模であるとき、現行のシステムの１つ
の問題は、探索中の情報の記述と、適当な解答を構成す
るテキスト・パッセージの文脈との間で発生するパラフ
レーズ変形に有効に対処する問題である。リテラル探索
エンジンは、パラフレーズを返さず、したがって、重要
な関連情報を逃す可能性がある。パラフレーズを許容す
る探索エンジンでは、生成される応答が多すぎる可能性
があり、適切な階層ランキングがないことが多く、最小
限の有用性を有する問い合わせ応答がもたらされる。

【０００５】現在の所うまく対処されていない他の問題
は、結果として得られるヒット・パッセージの有効なラ
ンク付けである。効率的な情報アクセスを向上させるに
は、問い合わせに対する応答における合致する文書位置
の高品質なランク付けが必要である。

【０００６】従来型の情報検索（「文書検索」とも呼ば
れる）では、問い合わせが文書の集合と突き合わせて測
定され、１組の「検索された」文書が返される。有用な
変形例（「関連性ランク付け」と呼ばれる）は、通常、
文書中の問い合わせ用語の出現数と文書の集合全体中の
同じ用語の出現数とのある種の関数によって、検索した
文書を、問い合わせに対する推定関連性順にランク付け
するものである。

【０００７】しかし、文書検索技法は、所望の情報が見
つかる可能性が高い、検索中の文書内の特定の位置また
はパッセージを識別しようとはしない。したがって、検
索中の文書が十分に大規模なものであり、探索中の情報
が特定のものであるとき、情報シーカに対してかなりの
残余作業が残る。所望の情報が実際に文書に存在する場
合、依然として、検索中の文書を走査し探索中の情報が
どこにあるかを調べる必要がある。この欠点に対処する
機構が必要である。

【０００８】パッセージ検索に関する大部分の以前の情
報検索手順では、索引付け時にパッセージ粒度が選択さ
れ、このような単位が索引付けされ、次いで、小規模の
文書の場合と同様に検索され、あるいは個別の文の集合
が検索され組み合わされパッセージが生成される。Ｓａ
ｌｔｏｎ等著”Ａｐｐｒｏａｃｈｅｓ ｔｏ Ｐａｓｓ
ａｇｅ Ｒｅｔｒｉｅｖａｌ ｉｎ Ｆｕｌｌ Ｔｅｘ
ｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ”，Ｐｒ
ｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓｉｘｔｅｅｎｔ
ｈ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ ＡＣ
Ｍ ＳＩＧＩＲＣｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｅｓｅ
ａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ｉｎ Ｉ
ｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ （ＳＩＧ
ＩＲ９３）（引用によって本明細書に編入される）ＡＣ
Ｍ Ｐｒｅｓｓ，１９９３，ｐｐ４９−５８、Ｃａｌｌ
ａｎ，Ｊ．Ｐ．著”Ｐａｓｓａｇｅ−Ｌｅｖｅｌ Ｅｖ
ｉｄｅｎｃｅ ｉｎ Ｄｏｃｕｍｅｎｔ Ｒｅｔｒｉｅ
ｖａｌ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓ
ｅｖｅｎｔｅｅｎｔｈ Ａｎｎｕａｌ Ｉｎｔｅｒｎａ
ｔｉｏｎａｌ ＡＣＭ−ＳＩＧＩＲ Ｃｏｎｆｅｒｅｎ
ｃｅ ｏｎ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏ
ｐｍｅｎｔ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒ
ｉｅｖａｌ （ＳＩＧＩＲ９３）（やはり引用によって
本明細書に編入される），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌ
ａｇ，１９９４，ｐｐ３０２−３１０、Ｗｉｌｋｉｎｓ
ｏｎ，Ｒ．著”Ｅｆｆｅｃｔｉｖｅ Ｒｅｔｒｉｅｖａ
ｌｏｆ Ｓｔｒｕｃｔｕｒｅｄ Ｄｏｃｕｍｅｎｔｓ”
（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓｅｖｅｎ
ｔｅｅｎｔｈ， ｅｔｃ．，ｐｐ３１１−３１７にも記
載されている）を参照されたい。検索中のパッセージが
問い合わせ句に合致する程度に基づいて検索用のパッセ
ージを動的にサイズ付けするシステムを有すると有用で
ある。

【０００９】

【発明が解決しようとする課題】最近、隠れマルコフ連
鎖法に基づきパッセージを動的に選択することができる
異なる手法が提案されている。Ｍｉｔｔｅｎｄｏｒｆ等
著”Ｄｏｃｕｍｅｎｔａｎｄ Ｐａｓｓａｇｅ Ｒｅｔ
ｒｉｅｖａｌ Ｂａｓｅｄ ｏｎ Ｈｉｄｄｅｎ Ｍａ
ｒｋｏｖ Ｍｏｄｅｌｓ”（Ｐｒｏｃｅｅｄｉｎｇｓ
ｏｆ ｔｈｅＳｅｖｅｎｔｅｅｎｔｈ， ｅｔｃ．，ｐ
ｐ３１８−３２７）を参照されたい。しかし、この手法
は、テキスト材料の語彙全体には対処せず、索引付け時
に文書の記述をクラスタに低減させる必要がある。テキ
スト・ベース全体を包含すると共に、そのようなクラス
タ化を必要としないシステムを有することが好ましい。

【００１０】

【課題を解決するための手段】本発明は、テキスト内の
関連する特定の情報パッセージのより効率的で有用な位
置を用いて問い合わせに対する応答を生成する方法およ
び装置に関する。この方法は、問い合わせ中の用語にあ
る程度合致する（「（含意側）用語ヒット」）用語を含
むことなどによって、問い合わせに測定可能なある程度
に合致するテキスト内の小さな領域（「ヒット・パッセ
ージ」）を見つけ、それらの領域を、測定された合致度
によってランク付けする。このランク付け手順は、本明
細書では「緩和ランク付け」と呼ばれ、提示された問い
合わせと検索されるヒット・パッセージとの間の対応を
得るために問い合わせとの厳密な合致の要件を緩和しな
ければならない程度に基づいてヒット・パッセージをラ
ンク付けする。この緩和機構は、語順、語隣接、問い合
わせ用語の屈折形または派生形、見つかった用語の問い
合わせ用語からの意味上または推論上の距離を含め、事
前に定義された様々な「次元」（合致の密度の尺度）を
考慮する。

【００１１】本発明のシステムは、問い合わせ中の用語
に意味論的に類似しているテキスト（文書データベー
ス）中の用語（語または句）の出現を見つけて、すべて
または大部分の問い合わせ用語、あるいはそれに類似し
ている用語を含むテキストの小さな領域を識別する。こ
のような小さな領域は、コンパクトネス、見つかった句
の問い合わせ用語との意味論的類似、実際に見つかった
（すなわち、テキストから見つかったある用語に合致し
た）問い合わせ用語の数、対応する問い合わせ用語の順
序と比べた見つかった用語の出現の相対順序の組合せに
よってランク付けされる。

【００１２】識別された小さな領域を「ヒット・パッセ
ージ」と呼び、そのランクは、（問い合わせ中の対応す
る用語間の距離に対する）合致する用語を分離する分離
距離、ならびにヒット中の用語と問い合わせ中の対応す
る用語との間の「類似」距離に基づいてかなりの程度に
加重される。

【００１３】前述の基準は加重され、見つかったパッセ
ージは、所定の手順に従ってすべての加重を組み合わせ
ることによって生成されたスコアに基づいてランク付け
される。ユーザには、文書内の「ウィンドウ」（見つか
った「ヒット・パッセージ」の周りの可変サイズ領域）
が、結果として得られるランク付けに応じた順序で提示
される。

【００１４】緩和ランク付けの重要な利点は、従来型の
文書検索システムでは、検索演算子のそれぞれの異なる
組合せを使用する探索シーケンスによって見つける必要
があるヒットを、システムが自動的に生成し、ランク付
けすることである。したがって、情報シーカが結果に満
足せず、したがって、問い合わせを再形成する必要があ
る回数が大幅に減少され、問い合わせを形成するために
必要な作業量も著しく減少される。

【００１５】他の利点は、本システムによって生成され
るランク付けが主として文書の集合のサイズの影響も構
成の影響も受けず、いくつかの集合の群全体にわたって
意味をなし、そのため、それぞれの異なる集合を探索す
ることによって生成された用語ヒット・リストをマージ
することができ、それぞれの異なる集合から得たランク
付けスコアが同一基準のものとなることである。このた
め、索引付け・検索プロセスを並列化し、分散すること
ができる。

【００１６】また、本発明のシステムは、検索中の文書
内の関連する特定のパッセージを見つけるうえで従来型
のシステムよりも優れており、かつ緩和ランク付け手順
によって生成された情報と共にこのようなパッセージを
要約し表示し、その結果、ユーザは、そのパッセージが
なぜ検索されたかを知り、したがってヒット・パッセー
ジを調べるかどうかとどのように調べるかを判断するこ
とができる。

【００１７】本発明は、２語ないし６語など、短い問い
合わせを扱う際に特に有効であることが証明されてい
る。従って、本発明の検索システムは、１語問い合わせ
または６つよりも多くの用語の問い合わせに基づく探索
向けの従来型の用語探索機構を使用し、かつ２語ないし
６語の問い合わせに基づく探索向けの本発明のシステム
を使用して、それぞれの異なる問い合わせを異なるよう
に処理することができる。

【００１８】

【発明の実施の形態】使用される特定のタイプのランク
付けおよびペナルティ基準と、本発明を実施するのに適
したハードウェアおよびソフトウェアの構成を含め、全
体的な一般機能に関して本発明のシステムを説明する。
緩和ランク付け方法を実施する特定の方法、ならびに本
発明の実際の実施形態によって生成された探索結果の例
を提示する。

【００１９】第１節：本発明の装置 図１は、本発明を実施するコンピュータ・システム１０
を示す。システム１０は、プロセッサ２０と、オペレー
ティング・システム、アプリケーション、データ・ファ
イルを記憶するメモリ３０と、キーボードおよびマウス
４０と、ディスプレイおよびその他の出力装置（プリン
タなど）５０とを含む、従来型のパーソナル・コンピュ
ータまたはワークステーションでよい。厳密な構成は重
大ではない。たとえば、メモリ３０は、ネットワーク上
の分散メモリ、マルチプロセッサ中の共用メモリなどで
もよい。別法として同様に、出力装置５０は、大容量記
憶装置でもよく、あるいは、記憶、または表示、または
その他のタイプの出力のために、テキスト・フォーマッ
トであるか、それともグラフィカル・フォーマットであ
るか、それともその他のフォーマットであるかにかかわ
らず、探索問い合わせから得られた出力ファイルを受け
取ることができる任意の装置でもよい。この応用例で
は、「表示」は一般に、これらの可能性のどれかを包含
するために使用される。

【００２０】探索問い合わせなどシステムへの入力は、
キーボードおよびマウス４０を介して行われる。また、
探索問い合わせは、メモリ３０に記憶されプロセッサ２
０上で実行されるアプリケーションを実行する際に生成
することも、あるいは、ネットワークまたはその他の通
信チャネル上のリモート・ホストから受信することもで
きる。したがって、探索問い合わせの源は可変的なもの
であり、本発明は、探索の実行および結果の処理に関す
る。

【００２１】メモリ３０は、検索エンジン６０を含め、
本発明の方法を実行する命令を含むソフトウェアを記憶
する。このソフトウェアは一般に、本発明を実施するの
に必要なすべてのプログラム命令またはモジュールを含
む。下記の議論で理解されるように、本発明の教示が与
えられた場合、本発明を実施するプログラムまたはプロ
グラム・モジュールを生成することは簡単である。

【００２２】下記に詳しく説明するように、メモリ３０
は、探索を実行すべきすべての文書を含む文書本体７０
と、文書本体内のすべての用語、または指定されたある
サブセットの索引を備える用語出現索引８０も記憶す
る。また、生成装置ストア８５はメモリ３０の一部であ
り、プロセッサ２０は、結果をディスプレイ５０へ転送
できるように最終的に（プロセッサ２０に接続された）
出力バッファ９０に出力する前に、問い合わせ応答時に
生成された情報を一時的に生成装置ストア８５に記憶す
る。

【００２３】出力バッファ９０は、下記に詳しく論じる
ように、ユーザが定義し、あるいは事前に決定した最大
数のヒット・パッセージを記憶し、あるいは、問い合わ
せ応答によって生成されたヒットの総数がこの所定の最
大値を超えない場合はこの総数を記憶するように構成さ
れる。ヒット・パッセージ、すなわち、用語ヒットを含
む検索中のテキストの領域は、下記に説明する本発明の
方法によるランク順に記憶される（「用語ヒット」は、
本明細書では、何らかの点で問い合わせ用語に合致する
ものとして検索された個別の用語を指すために使用され
る）。

【００２４】近接バッファ９５もプロセッサ２０に接続
され、「ウィンドウ」、すなわち、入力された問い合わ
せ用語に合致する用語が現在プロセッサによって探索さ
れている動的可変サイズの文書中の領域の位置およびサ
イズを目標文書上に記憶するためにプロセッサによって
使用される。ウィンドウは、目標文書内の開始位置に、
その開始位置からその文書のうちのどれだけの量をヒッ
ト・パッセージに含めるべきかを決定するサイズを加え
た値として指定することができる。ヒット・パッセージ
とは、そのようなウィンドウによってカバーされる文書
の部分であり、ヒット用語、すなわち合致する用語自体
を含む。

【００２５】ヒット用語およびヒット・パッセージも近
接バッファ９５に記憶され、ウィンドウ情報に相関付け
られる。

【００２６】図２は、後に続く問い合わせ動作をサポー
トするために使用される用語出現索引８０および用語／
概念関係ネットワーク１１０を生成するために索引付け
すべきテキスト材料の文書本体７０に適用される索引付
け動作および分析動作を実行するにはプログラム・モジ
ュールをどのように構成すべきかを示す。

【００２７】用語索引付けモジュール９０は、用語出現
索引８０、すなわち、本体７０で出現するすべての用語
リストのレコードを、各用語が出現する文書とその用語
が出現する文書内の位置をリストするその用語用のレコ
ードと共に構成する。この動作は、情報検索における従
来型の動作である。

【００２８】用語分析モジュール１００は、本体７０中
の各用語を分析し、用語／概念関係ネットワーク１１
０、すなわち、本体７０内で出現する用語および概念、
または問い合わせ内で出現する関連用語および概念の本
体特有の意味ネットワークを、後で用語をテキスト中の
用語に接続するために使用できるこれらの用語および概
念間の様々な形態学、分類学、意味論上の含意関係と共
に構築する。

【００２９】用語／概念関係ネットワーク１１０を構築
する際には、一般的な英語または他の何らかの言語の
語、あるいはその両方に関する情報の汎用レキシコン１
９０と、本体７０の主ドメインに特有の用語に関する用
語および情報を含むドメイン特有専門レキシコン２００
とで構成されたレキシコン１８０が使用される。これら
のレキシコンは、用語間の形態学的関係に関する情報
と、レキシコン内では明白に出現しない用語間の形態学
的関係を導くために用語分析モジュール１００内の形態
学的分析ルーチンによって使用される語のシンタックス
部分などその他の情報とを含む。そのようなレキシコン
および形態学的分析の動作および使用法は、計算言用語
学における従来どおりのものである。

【００３０】用語／概念関係ネットワーク１１０を構築
する際には、英語または他の何らかの自然言語、あるい
はその両方の一般的な語と概念との間に成立する分類学
的包摂関係（すなわち、より一般的な用語とより特定的
な用語との間の関係）の汎用分類法１３０と、本体７０
の主ドメインに特有の包摂関係のドメイン特有の局限分
類法１４０も使用される。この動作は、英語または他の
何らかの自然言語、あるいはその両方の一般的な語と概
念との間に成立する意味論的含意関係（すなわち、ある
用語または概念と、その用語を含意または意味する他の
用語または概念との間の関係）の汎用含意データベース
１６０と、本体７０の主ドメインに特有の意味論的含意
関係のドメイン特有の含意データベース１７０とで構成
された意味論的含意関係１５０の意味ネットワークも使
用する。そのような意味論的分類法および意味ネットワ
ークの動作および使用法は、知識表現技術分野における
従来どおりのものである。Ｊｏｈｎ Ｓｏｗａ（ｅ
ｄ．）”Ｐｒｉｎｃｉｐｌｅｓｏｆ Ｓｅｍａｎｔｉｃ
Ｎｅｔｗｏｒｋｓ： Ｅｘｐｌｏｒａｔｉｏｎｓｉｎ
ｔｈｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ Ｋｎ
ｏｗｌｅｄｇｅ，”Ｓａｎ Ｍａｔｅｏ： Ｍｏｒｇａ
ｎ Ｋａｕｆｍａｎｎ， １９９１（引用によって本明
細書に組み込まれている）を参照されたい。

【００３１】これらのモジュールはそれぞれ、下記に説
明するように本発明の好ましい実施形態によって使用さ
れる。ただし、本発明を実施するためにそれぞれの異な
る等価構成を使用することができる。

【００３２】第２節：本発明の方法 図４は、本発明の方法の一般的な実施形態を示し、図５
および６は、本発明の好ましい実施形態に従って実行さ
れるステップを具体的に示す。

【００３３】２Ａ．基本モデル：ランク付けおよびペナ
ルティ手順 図４は、下記に論じる１２個のランク付けおよびペナル
ティ手順に対応する。ボックス４１０で、ユーザによっ
て入力され、あるいはプロセッサ２０上で実行中のプロ
セスによって要求された（１つないし多数の用語からな
る）探索問い合わせ句が入力される。ボックス４２０な
いし５５０は、文書本体から検索されたパッセージにペ
ナルティを課し、それをランク付けし、表示するために
実行されるステップを表し、下記にリストしたランク付
け手順１ないし１２に関係付けられる。図４の円中の数
値は、対応するように番号付けされたランク付け基準を
示す。

【００３４】この一般的な議論では、下記のリスト基準
／手順１ないし１２の順序および図４のボックス４３０
ないし５５０の順序は、ランク付けまたはペナルティ割
り当ての必要な順序を示すものではなく、多数の異なる
順序が可能である。

【００３５】下記に論じるペナルティおよびランク付け
基準（特に、手順１ないし７のペナルティおよびランク
付け基準）は、テキストの検索中のパッセージの融通性
のきくランク付けを可能にするので、本明細書では緩和
ランク付け基準と呼ばれる。

【００３６】手順１：近接ランク付けペナルティ（図４
のボックス４２０および４７０） ヒット・パッセージ
は、問い合わせ用語に関する１つまたは複数の合致を含
むテキストの小さな領域として識別され、合致する用語
どうしがどれだけ近く、あるいは離れて出現するかに応
じてペナルティを課される。すなわち、見つかった用語
どうしが、問い合わせ句中のそれらの用語の近接度と比
べて離れれば離れるほど、ペナルティが高くなる。

【００３７】１組の用語と、距離しきい値、すなわち合
致を数えられるようにこれらの用語の出現を見つける範
囲をユーザが指定する、「近接演算子」を使用する従来
型の情報検索技法と、本明細書の近接ペナルティが同じ
ものではないことに留意されたい。従来型の技法では、
結果として得られるヒットは、本発明とは異なり、用語
どうしがどれだけ近く出現するかではなく、いくつの用
語が出現するかによってランク付けされる。

【００３８】手順２：置換ペナルティ（図４のボックス
４８０） ヒット・パッセージは、問い合わせ用語の順
序とそれらの用語の対応する用語ヒットの順序との間の
置換距離の尺度を使用して、それに関連する句が、問い
合わせ句中の対応する用語とは異なる順序で出現する程
度によってペナルティを課される。

【００３９】手順３：形態学的変形ペナルティ（図４の
ボックス４３０） 問い合わせ用語は、目標テキスト中
の用語、すなわち問い合わせ用語の屈折形または派生形
と比較され、屈折変形または派生変形よりも正確な合致
が優先されるが、わずかしか優先されないように、小さ
なペナルティ因子によってランク付けされる。

【００４０】手順４：分類学的局限化ペナルティ（図４
のボックス４４０） 問い合わせ用語は、図２の分類法
１８０など、用語および概念間の分類法リスト汎用性関
係に従ってより特定的なテキスト中の用語と比較され
る。問い合わせ中の用語および概念よりも特定的なテキ
スト中の用語および概念は自動的に検索され、問い合わ
せに対する正確な合致ではないためにペナルティでラン
ク付けすることができる。

【００４１】手順５：意味論的含意ペナルティ（図４の
ボックス４５０） 問い合わせ用語に対する高度の「意
味論的」類似を有する用語を含み、あるいは、問い合わ
せ用語を論理的に伴うヒット・パッセージは、意味論的
類似がより低く、あるいは含意強度がより低いヒット・
パッセージよりも低いペナルティを課される。

【００４２】手順６：欠落用語ペナルティ（図４のボッ
クス４６０） すべてではなく、いくつかの問い合わせ
用語に関する合致を含むヒット・パッセージを含み、ヒ
ット・パッセージから欠落している問い合わせ用語の数
に応じてそれらのヒット・パッセージにペナルティを課
す。このようにして、完全な合致が出現しないときには
自動的に、見つかったうちで最良の合致に関する情報が
ユーザに提示される。ヒット・パッセージはまた、欠落
している用語の重要性の判定に応じてランク付けされ
る。

【００４３】手順７：重なり抑制（図４のボックス５０
０） より良いランクを有する他のヒット・パッセージ
に重なる（すなわち、そのようなヒット・パッセージと
同じ、目標文書上の「ウィンドウ」の少なくとも一部を
占める）ヒット・パッセージは抑制され、すなわち破棄
される。他の重なるヒット・パッセージと同じランクを
有するヒット・パッセージは、見つかった文書の全体的
なランクに何も追加しないので、同様に抑制される。

【００４４】手順８：位置順序付け（図４のボックス５
１０） 等しい他のすべての因子、すなわち等しいラン
ク付けスコアを有するヒットは、一次的には、デフォル
トの好ましい文書順に順序付けされ、二次的には、所与
のヒット・パッセージが文書内で出現する位置に応じて
順序付けされる。

【００４５】手順９：動的パッセージ・サイズ付けおよ
び内部境界ペナルティ（図４のボックス５２０） ヒッ
ト・パッセージは、ヒット領域を含む文の最小シーケン
スからなるテキストのパッセージによって識別され、あ
るいは、ヒット領域が文構造を有さないテキストの部分
（たとえば、図表）内にある場合は、ヒット領域を含む
最小コヒーレント領域によって識別される。ヒット・パ
ッセージを判定する際に特定的に使用された現問い合わ
せパッセージ内の用語は、可能なら、そのような識別が
表示されるときに強調表示される。所与のヒット・パッ
セージ内で文の終わり（ピリオドなど）またはパラグラ
フの境界が出現する場合、そのパッセージにはペナルテ
ィが課される。

【００４６】手順１０：合致の要約（図４のボックス５
３０） ヒット・パッセージは、そのような各ヒット・
パッセージ中の合致しない問い合わせ用語の特定の識別
を含む、問い合わせ中の対応する用語に合致するヒット
・パッセージ中の用語のリストによって要約される。

【００４７】手順１１：リストのランク付け（図４のボ
ックス５４０） 問い合わせを処理する際、それぞれ、
合致の質を報告するランク付けスコア（全体的なペナル
ティ合計が低いほど、より高い質を示す）を有する、見
つかった用語ヒットのランク付きリストがユーザに提示
される。したがって、各ヒット・パッセージは、合致要
約と、ヒットを構成するテキストのパッセージの表示に
よって識別される。用語ヒットは、前述のランク付け因
子を組み合わせることによって決定される順序でリスト
され、普通ならランクが等しいヒット・パッセージは、
本体およびテキスト中のそれらの位置に応じて順序付け
される。すなわち、好ましい文書中のヒット・パッセー
ジが最初に提示され、文書内の前の方にあるヒット・パ
ッセージの方が、後の方にあるヒット・パッセージより
も前に提示される。

【００４８】手順１２：対話パッセージ・アクセス（図
４のボックス５５０） 結果リスト中の各用語ヒット
は、文書中の対応するヒット・パッセージの周りの文脈
内にこのヒット・パッセージを表示するために選択でき
る少なくとも１つのアクティブ・ボタンまたはハイパー
リンクを含む。ヒット・パッセージは、それが出現する
文脈内に表示されたときには強調表示され、合致をもた
らしたヒット・パッセージ中の用語はマーク付けされ
る。その場合、ユーザは文書内を自由に動き回り、強調
表示されたヒット・パッセージに自由に戻ることができ
る。

【００４９】手順４００は、ステップ４２０ないし５５
０を実行した後、図４のボックス５６０に示したよう
に、他の問い合わせの処理を開始する準備が完了し、そ
れ以外の場合は、ボックス５７０のように停止する。

【００５０】２Ｂ．基本方法：物理的近接および類似に
よるランク付け 本発明の基本方法は、すべての問い合わせ用語が密に出
現し、あるいは大部分の問い合わせ用語（または大部分
の問い合わせ用語に類似している用語）が密に出現する
索引付きテキストの領域を見つけることである。このよ
うなヒット・パッセージは、緩和ランク付け基準によっ
てグレード付けされ、このランク順にユーザに提供され
る。

【００５１】たとえば、ユーザが（テキスト・エディタ
・アプリケーション用のオンライン・ユーザのマニュア
ルなどの）文書本体中の句”ｊｕｍｐ ｔｏ ｅｎｄ
ｏｆｆｉｌｅ”（ファイルの終わりにジャンプする）を
見つけるための問い合わせを行った場合、検索エンジン
によって返されるヒット・パッセージは、”ｍｏｖｅ
ｔｈｅ ｃｕｒｓｏｒ ｔｏ ｔｈｅ ｅｎｄ ｏｆ
ｔｈｅ ｉｎｐｕｔｂｕｆｆｅｒ”（カーソルを入力バ
ッファの終わりへ移動する）となる可能性がある。この
場合、検索中の用語”ｊｕｍｐ”（ジャンプ）は、密な
意味論的距離を有する語としての問い合わせ用語”ｍｏ
ｖｅ”（移動する）に対応し、介在する句”ｔｈｅ ｃ
ｕｒｓｏｒ”（カーソル）は、検索中のパッセージのコ
ンパクトネスを最初の問い合わせ句に対して比較する基
準に基づいて小さなペナルティをもたらす。介在する語
を含まない他の検索中のパッセージはこのペナルティを
受けない。

【００５２】この例では、句”ｉｎｐｕｔ ｂｕｆｆｅ
ｒ”（入力バッファ）は、ある種の測定可能な含意関係
によって問い合わせ用語”ｆｉｌｅ”（ファイル）に対
応する。上記で指摘したように、含意は、問い合わせ用
語がある程度、検索中の語を意味することを示す。この
場合、”ｉｎｐｕｔ ｂｕｆｆｅｒ”は、用語”ｆｉｌ
ｅ”の仮想存在を含意するとみなすことができる。ある
用語は、それが別の用語によって意味される場合、その
別の用語を含意する。一般に、含意する側の用語は、含
意される側の用語よりも狭く、かつ特定的であるが、ほ
ぼ同義であることもある（したがって、”ｂｉｒｄ”
（鳥）は”ａｎｉｍａｌ”（動物）に含意し、”ｐｌｕ
ｍａｇｅ”（羽衣）は”ｂｉｒｄ”に含意する）。

【００５３】ヒット・パッージ”ｊｕｍｐ ｔｏ ｅｎ
ｄ ｏｆ ｆｉｌｅ”には、ヒットの全長、欠落してい
る用語（もしあれば）の数、問い合わせの整列する語と
対応するヒット・パッセージとの間の意味論的類似また
は含意の強度に基づいて量的ランクが割り当てられる。

【００５４】この方法は、問い合わせの各用語に関する
下記の情報を与えることができる用語出現索引（その生
成については上記の第１節で論じる）を使用する。 １．その用語を含む本体中の１組のすべての文書の列挙 ２．所与の文書に関して、用語が出現する文書内の（た
とえば、バイト・オフセットとしての）位置 ３．集合内で用語が出現する回数、その用語が出現する
文書の数、各文書内でその用語が出現する回数、集合中
の文書および語トークンの総数などの統計的情報 そのような索引の構築は、情報検索における従来型の動
作である。

【００５５】この方法はさらに、用語のステムまたは形
態学的変体、意味論的に関係する語、より特定的な用
語、ある用語を含意する用語を得る機構（上記の第１節
でも論じる）を使用する。この類似距離は、問い合わせ
語を検索中の用語に突き合わせる際に割り当てるべき関
連するペナルティとして使用される。

【００５６】たとえば、問い合わせ用語”ｃｈａｎｇ
ｅ”（変化）の場合、形態学的変体には”ｃｈａｎｇｅ
ｄ”、”ｃｈａｎｇｉｎｇ”、”ｉｎｔｅｒｃｈａｎｇ
ｅ”が含まれる。意味論的に関係する語は”ｉｎｆｌｕ
ｅｎｃｅ”（影響する）であってよい。より特定的な語
には”ａｌｔｅｒ”（修正する）および”ｄａｍａｇ
ｅ”（損傷する）が含まれる。含意側の語は”ｍｏｖ
ｅ”であってよい（何かを移動することは位置の変化を
伴うため）。下記の説明では、これらの関係する用語は
一般に、「類似用語」または「含意側用語」と呼ばれ、
数値ペナルティは、問い合わせ用語と含意側用語との間
の関連性の種類と、２つの用語間の類似距離に基づい
て、それぞれの類似用語または含意側用語に関連付けら
れる。

【００５７】問い合わせ中の各用語ごとに「生成プログ
ラム」が構築される。生成プログラムとは、問い合わせ
用語またはそれに類似する用語が出現する文書中の位置
を列挙するメモリに記憶されているデータ構造またはデ
ータベースである。問い合わせ用語またはそれに類似す
る用語のこのような出現をその用語に関する「（含意
側）用語ヒット」と呼ぶ。

【００５８】集合中の文書には、それらの文書が索引付
けされた順序や、より頻繁に使用され、あるいはより豊
富な情報を与え、あるいはより有用な文書が、それほど
有用ではない文書よりも先に来る順序付けなど、任意の
順序が割り当てられる。各問い合わせ用語ごとの生成プ
ログラムは、その用語に関する用語ヒットが出現する集
合中の第１の文書中のその問い合わせ用語に関する用語
ヒットの第１の出現を生成するように初期設定される。

【００５９】基本的には、この方法は、問い合わせの用
語に関する用語ヒットを含む各文書内をウィンドウを移
動させ、ウィンドウが問い合わせ全体の合致を含むかど
うかを判定し、そのウィンドウからヒット・パッセージ
を抽出すべきかどうかを選択し、そうである場合、選択
したパッセージをランク付けすることによって進行す
る。

【００６０】問い合わせウィンドウのサイズは、（一時
的に）固定された位置パラメータに、所定の因子に問い
合わせの長さを乗じた積として求められたウィンドウ・
サイズ・パラメータを加えた値によって求められる。こ
の２つのパラメータは、情報シーカまたは実行中のプロ
セスによって処理することも、あるいは所定の有用な値
に設定することもできる。

【００６１】文書３０５上のウィンドウ３００が図３に
示されており、ウィンドウ３００は、ｎ個の用語３２
０．１ないし３２０．ｎ（ｔ１，ｔ２，．．．，ｔｎ）
を含むヒット・パッセージ３２０を含むテキスト３１
０．１ないし３１０．１１の行を含む。ヒット・パッセ
ージ３２０は、開始位置３３０によってマーク付けされ
た始めと、終了位置３４０によってマーク付けされた終
わりとを有する。

【００６２】ウィンドウ３００は、文書３０５の本体の
それぞれの異なる部分を含むように本体上を移動するこ
とができる。たとえば、ウィンドウは、図のテキストに
対して下向きに移動する際、行３１０．１を省き、行３
１０．１２（この行が、３１０．１１の下方の次の行に
なる）を含み、次いで行３１０．２を省き、行３１０．
１３を含み、以下同様である。ウィンドウ構築の使用法
を下記に詳しく提示する。

【００６３】他のパラメータ（ユーザまたはプロセスに
よって事前に決定され、あるいは設定される）は、緩和
のそれぞれの異なる次元（たとえば、近接、置換、形
態、分類、含意、削除）の加重を決定し、２つのパラメ
ータは、ヒット・パッセージが文境界またはパラグラフ
境界を含む場合に割り当てるべきペナルティを指定す
る。各パラメータは、情報シーカが処理できるようにす
ることも、あるいは所定の有用な値に設定することもで
きる。パッセージのランク付けは、正味ペナルティ、す
なわち、様々なソースからそのパッセージに割り当てら
れたペナルティの和によって決定される。

【００６４】２Ｃ．ヒット・パッセージを所望のランク
順に生成する一般的な方法 下記の方法は、ヒット・パッセージを生成し、探索問い
合わせを最もうまく反映するランク付けでそれらのパッ
セージを順序付ける一般的な手順を与える。

【００６５】それぞれ、語または句である、用語ｑ１，
ｑ２，．．．，ｑｍの文を問い合わせｑとし、語ｘ１，
ｘ２，．．．，ｘｎのシーケンスを含むテキスト文書を
ｘとする。順序付けされた用語対（ｐ，ｐ’）に距離尺
度ｄ＝ｄ（ｐ，ｐ’）を割り当てる用語類似距離関係が
使用され（ ｐおよびｐ’は用語である）、ｄは用語間
の類似距離である。

【００６６】類似距離零は、用語の同一または完全な同
義、あるいは問い合わせ用語ｐとテキスト用語ｐ’との
合致にペナルティが割り当てられない何らかの他の環境
を表す。より大きな類似距離は、例えば、一方が他方よ
りも一般的であり、あるいは他方によって含意され、あ
るいは一方のある意味が部分的に、他方のある意味と同
義であり、あるいは用語が何らかの他の点で意味論的に
類似しているため、部分的にのみ同義であり、あるいは
その他の点で関係付けられた用語に対応する。

【００６７】問い合わせｑが与えられており、（１）問
い合わせの用語とテキストの用語とからなる各対が小さ
な類似距離を有し、（２）問い合わせ中の用語に整列す
るテキスト中の用語がテキスト内で互いに近接して出現
し、（３）テキスト中の用語ヒットが、それに対応する
問い合わせ用語が問い合わせ内で出現する順に出現する
場合に、そのような整列をより高くランク付けするよう
に、問い合わせ中の用語とテキスト中の用語の整列ａ＝
（ｑ１，ｘｉ１），（ｑ２，ｘｉ２），．．．，（ｑ
ｍ，ｘｉｍ）を求めたい。

【００６８】問い合わせ用語のあるサブセットのみに関
するテキスト対応を有する整列も、検討され、欠落して
いる用語の種類、またはその用語が問い合わせで果たす
役割、あるいはその両方によって決定されたペナルティ
を与えることによって、より多くの問い合わせ用語を含
む整列よりも悪くランク付けされる（より高いペナルテ
ィを課される）。

【００６９】問い合わせ用語ｑｉ（単一の語と、語のシ
ーケンスを含む句のどちらか）が与えられた場合、用語
距離対（ｔ１，ｄ１），（ｔ２，ｄ２），．．．，（ｔ
ｊ，ｄｊ）のリストを距離値ｄｊ、すなわち問い合わせ
用語ｑｉと潜在的なテキスト用語ｔｊとの間の類似距離
の増加する順に返す関数呼び出しが行われるように類似
距離関数が構成される。この関数を「類似語」と呼ぶ。

【００７０】テキスト・シーケンスｘ１，ｘ
２，．．．，ｘｎは、所与の用語ｔｊに関する関数呼び
出し”ｔｅｒｍ−ｉｎｄｅｘ”が、（１）その用語が出
現するすべての文書、（２）テキスト内で用語ｔｊに関
する合致が出現するすべての位置ｉを見つけるように、
事前に索引付けされる。ｔｊが語ｗ１，ｗ２，．．．，
ｗｐのシーケンスである場合、ｘｉ＝ｗ１，ｘｉ＋１＝
ｗ２，．．．およびｘｉ＋ｐ−１＝ｗｐである場合には
位置ｉでｔｊに関する合致が出現する。

【００７１】問い合わせｑ中の各用語ｑｉに関して、そ
の用語およびそれに類似する（含意側）用語に関する用
語−索引用語リストを組み合わせることによって、用語
ｑｉに関する用語ヒット（厳密な合致または含意側の
「密なヒット」）のシーケンスが構築される。これらの
ヒットはそれぞれ、問い合わせ用語とそれに合致するテ
キスト用語との間の類似距離に対応する加重またはペナ
ルティ（あるいは用語の厳密な合致の場合は零）を有す
る。

【００７２】一般に、所与の問い合わせｑに関するヒッ
ト・パッセージを生成し返す方法は下記のとおりであ
る。

【００７３】１．問い合わせ中の各有意用語に関する用
語ヒットの生成プログラムをセットアップする（”ｏ
ｆ”や”ｔｈｅ”などある種の関数語は無意味であると
判断され、無視される）。このような生成プログラム
は、文書中の用語ヒットを生成し、その場合、用語ヒッ
トは、集合中の文書の順に出現し、文書内では、文書内
のその用語ヒットの位置の順に出現する。

【００７４】２．問い合わせｑに関する全体的なヒット
・パッセージは、問い合わせの用語によって生成される
第１の類似用語（ｔ）の位置から開始することによって
順次、生成される。この用語ヒットを「語根」と呼ぶこ
とができる。したがって、第１のヒット・パッセージ
は、集合中の最初の文書中の最初の語、すなわち、問い
合わせ中の１つの用語に関する用語ヒットである。次い
で、この方法は、同じ文書中、および語根用語ｔの位置
からのしきい値近接距離（近接ホライズン）によって決
定されるウィンドウ内にある問い合わせ中の他の用語に
よって生成されるすべての用語を検査する。このウィン
ドウ内で出現する他の（非語根）生成プログラムから得
た用語ヒットの各組み合わせごとに、個別の用語ヒット
間の距離、各用語ヒットで使用された類似距離または合
致ペナルティ、ヒット・パッセージの領域に関するシン
タックス情報（ヒット・パッセージに含まれる文または
パラグラフの境界があるかどうかなど）、ウィンドウ内
に対応するヒットを有さない問い合わせ中の用語に対応
する適当なペナルティ（このペナルティは、欠落してい
る語の種類、あるいは問い合わせその語の役割または集
合中の頻度、あるいはその両方に依存する）から、この
組み合わせに関する正味ペナルティ・スコアが算出され
る。このようなヒット・パッセージには、文境界ペナル
ティおよびパラグラフ境界ペナルティに関するパラメー
タ設定に応じて、文境界またはパラグラフ境界を横切っ
たことに対するペナルティも割り当てられる。そのよう
な最良の組み合わせが選択され、その問い合わせに関す
るヒット・パッセージとして生成される。

【００７５】３．語根用語（ｔ）に関する生成プログラ
ムは、ヒット・パッセージを生成した後、その用語に関
する次の用語ヒットへ進み、問い合わせ中のすべての他
の用語に関する生成プログラムが、前の語根用語が最初
に選択されたときの値に復元される。次に、新しい語根
が選択され（現在生成されている用語ヒットのうちの最
初の用語ヒット）、プロセスが繰り返される。

【００７６】４．問い合わせに関するヒット・パッセー
ジを生成するこのプロセスは、十分な数の零ペナルティ
・ヒット・パッセージが生成され（指定された限界によ
って決定される）、あるいは生成すべき用語ヒットがも
はやなくなるまで繰り返され、その後、見つかったすべ
てのヒット・パッセージがその全体的な正味ペナルティ
によってソートされる。より良いヒット・パッセージま
たは同じスコアを有する前にヒット・パッセージ内に含
まれ、あるいはそれに重なるヒット・パッセージは抑圧
され、最良の残留ヒット・パッセージ（指定された限
界）は、その全体的なペナルティ・スコアの順（最小の
ペナルティが最初）に情報シーカに提示される。別法と
して、ヒット・パッセージが生成されたときにそれを表
示ウィンドウに提供することができ、新しい各ヒット
は、それが見つかったときにディスプレイ内の適当なラ
ンク位置に挿入される。重なっている表示中のヒット・
パッセージを、新しくより良いヒット・パッセージで置
き換えることを回避するには、探索ウィンドウが重なり
の点を越えるまでヒット・パッセージをディスプレイへ
送るのを遅延させることができる。

【００７７】５．提示される問い合わせヒット・リスト
中の各ヒット・パッセージは、そのペナルティ・スコ
ア、合致基準の要約（各問い合わせ用語ごとの対応する
用語ヒットのリストを含む）、ソース文書内のパッセー
ジの位置の識別（文書ＩＤやパッセージの始めおよび終
わりのバイト・オフセットなど）、検索されたパッセー
ジのテキスト文字列と共に表示される。検索されたパッ
セージは、この合致中の最初の用語ヒットよりも前に位
置するソース文書中の最後の文境界またはセグメント境
界から開始し、最後の用語ヒットの後に続く最初の文境
界またはセグメント境界で終了することによって決定さ
れる。

【００７８】６．表示された用語ヒット・リストを使用
して、検索されたパッセージが出現する文脈内のそれら
のパッセージのディスプレイにアクセスすることができ
る。これを行うには、パッセージが出現する文書上で表
示ウィンドウを開き、検索されたパッセージが表示ウィ
ンドウ内に見えるように表示ウィンドウ内にテキストを
位置決めし、可能なら、そのパッセージに位置調整され
た用語ヒットがユーザに見えるようにその用語ヒットに
マーク付けする。

【００７９】従来型の文書検索とは異なり、本発明のシ
ステムは、単に文書自体を見つけるのではなく、文書内
の特有の情報パッセージを見つける。これは、情報検索
において「パッセージ検索」と呼ばれていたものに類似
しているが、本発明では、パッセージは、用語および位
置の汎用全テキスト索引を使用して問い合わせに応答し
て動的に構築され、パッセージのサイズおよび粒度は合
致において見つけられるものに応じて可変である。

【００８０】２Ｄ．問い合わせおよび結果の例 下記の例は、周知のＥｍａｃｓテキスト・エディタ用の
チュトリアル文書に索引付けする、出願人が使用したこ
の方法の実際の実施態様によって生成された簡略用語ヒ
ット・リストの一部である。このリストで、各ヒット用
語リストは、シーケンス番号と、ペナルティ・スコア
と、合致する用語のリストと、ヒットが出現した文書
と、下記のフォーマットの文書内のヒットの位置とを含
むデータ構造を備える。 ++++++++++++++++++++<hit sequence number> (hit <penalty score> <list of matching terms><file
where hit was found> <beginning position><end pos
ition>) <retrieved text passage>

【００８１】これは、問い合わせ句”ｍｏｖｅ ｔｏ
ｅｎｄ ｏｆ ｆｉｌｅ”、すなわち、所定の文書本体
内でのこの句の探索に関して生成された結果である。こ
の例の文書本体は、前述のようにＥｍａｃｓテキスト・
エディタ文書の一部である。

【００８２】結果として得られるヒット・リストの最初
の３用語リストを下記に示す。 ++++++++++++++++++++１ （hit 0.115("GO""TO""END""FILE")"/home/emacs-tutor
ial"5881 5898) M-> Go to end of file（ファイルの終わりへ進む） ++++++++++++++++++++２ (hit 0.115("MOVES""TO""END""FILE")"/home/emacs-tut
orial"4984 5012)which moves to the end of file .（ファイルの終わり
へ移動する） ++++++++++++++++++++3 (hit 2.849("DASHES"(MISSING TO)"ENDS""FILE")"/home
/emacs-tutorial"15624 15753)begins and ends with dashes, and contains the stri
ng "Emacs: TUTORIAL".Your copy of the Emacs tutori
al is called "TUTORIAL". Whatever file youfind, th
at file's name will appear in that precise spot.
（ダッシュで始まりダッシュで終わり、文字列”Ｅｍａ
ｃｓ：ＴＵＴＯＲＩＡＬ”を含む。Ｅｍａｃｓのコピー
を”ＴＵＴＯＲＩＡＬ”と呼ぶ。どんなファイルが見つ
かっても、そのファイルの名前はその厳密なスポットに
表示される）

【００８３】上記のアンダーラインの部分は、入力問い
合わせ句”ｍｏｖｅ ｔｏ ｅｎｄｏｆ ｆｉｌｅ”に
関する合致として見つかった実際に検索されたヒット・
パッセージである）。

【００８４】上記の結果の関連するテキストの下記の抜
粋部分は、文脈中のそれぞれのヒット・パッセージの表
示を示す。ヒット領域（パッセージ）には下線が施さ
れ、見つかった用語ヒットはボールド体で表示されてい
る。

【００８５】Ｎｏ．１．For hit 0.115("GO""TO""END""
FILE") M-a Move back to beginning of sentence（文の始めへ
戻る） M-e Move forward to end of sentence（文の終わりへ
進む） M-< Go to beginning of file（ファイルの始めへ進
む） M-> Go to end of file（ファイルの終わりへ進む） >> Try all of these commands now a few times for p
ractice. Since the last two will take you away fro
m this screen, you can come back here with M-v's a
nd C-v's. These are the most often used commands.
（次に、練習のためにすべてのこれらのコマンドを試し
てみる。最後の２つがこの画面を終了させるので、Ｍ−
ｖおよびＣ−ｖによってこの画面に戻ることができる。
これらは、最も頻繁に使用されるコマンドである。

【００８６】Ｎｏ．２．For hit 0.155("MOVES""TO""EN
D""FILE") Two other simple cursor motion commands are: M-<(M
eta Less-Than), which moves to the beginning of th
e file, and M->(Meta Greater-than), whichmoves to
the end of the file. You probably don't need to tr
y them, sincefinding this spot again will be borin
g. On most terminals the "<" is above the comma an
d you must use the shift key to type it. On these
terminals you must use the shift key to type M-< a
lso; without the shift key,you would be typing M-c
omma.（２つの他の簡単なカーソル移動コマンドは、フ
ァイルの始めへ移送するM-<(Meta Less-than)とファイ
ルの終わりへ移動するM->(Meta Greater-than) であ
る。このスポットを再び見つけることは退屈なので、お
そらくこれらを試す必要はない。大部分の端末では、”
＜”はコンマの上にあり、これを入力するにはシフト・
キーを使用しなければならない。このような端末では、
Ｍ−＜を入力するときにもシフト・キーを使用しなけれ
ばならない。シフト・キーがない場合は、Ｍ−コンマを
入力する）

【００８７】Ｎｏ．３．For hit 2.849("DASHES"(MISSI
NG TO)"ENDS""FILE") If you look near the bottom of the screen you will
see a line that begins and ends with dashes, and
contains the string "Emacs: TUTORIAL". Your copy o
f the Emacs tutorial is called "TUTORIAL". Whateve
r file you find, that file's name will appear in t
hat precise spot. （画面の１番下の近くを見る場合、
ダッシュで始まりダッシュで終わり、文字列”Ｅｍａｃ
ｓ：ＴＵＴＯＲＩＡＬ”を含む行が表示される。Ｅｍａ
ｃｓチュトリアルのコピーを”ＴＵＴＯＲＩＡＬ”と呼
ぶ。どんなファイルが見つかっても、そのファイルの名
前はその厳密なスポットに表示される）

【００８８】合致の低さの程度を示す適当なペナルティ
・スコアを用いて、良好な合致から連続的に可能性の低
くなる合致へ次第に緩和していく。この例では、２より
も大きなペナルティ・スコアは、合致が有用でない可能
性が高いことを示す。文脈がどのように語の意味を決定
するかの影響をシステムが受けず、したがって、この文
脈では、”ｄａｓｈｅｓ”が明らかに動詞ではなく複数
名詞である場合でも、システムが”ｄａｓｈｅｓ”を”
ｍｏｖｅ”が局限化したものとして受け入れることに留
意されたい。これに対して、第１のヒットでは、ｍｏｖ
ｅはより特定的な用語”ｇｏ”には正しく合致し、それ
に対して第２のヒットでは屈折形”ｍｏｖｅｓ”に正し
く合致する。

【００８９】したがって、本発明の方法は、特定の情報
要求に対する答えを含むテキスト内のパッセージを見つ
け、探索中の情報を含むと推定される程度によってその
パッセージをランク付けする。

【００９０】２Ｅ．ヒット・パッセージを所望のランク
順に生成する特定の方法 図５は、本発明の方法の上位フローチャートである。ボ
ックス５１０で、探索問い合わせが入力され、ボックス
５２０で、方法は問い合わせ（探索）用語に関する合致
を含む本体中の目標領域を識別する。これは下記の第２
Ｆ節で詳しく説明する手順に従って、図２に示した用語
索引付けモジュール９０および１００の出力を使用して
行われる。

【００９１】ボックス５３０で、プロセッサ２０は、図
６および下記の第２Ｆ節で詳しく説明する手順で問い合
わせヒットのソート済みリストを出力バッファに充填す
る。次いで、ランク付きヒット・リストがディスプレイ
５０上に表示され、あるいは将来使用できるように大容
量記憶域中のファイルとして記憶することもできる。

【００９２】ボックス５５０で、実際のヒットが、それ
に割り当てられたランクに従って表示され、あるいは記
憶される。ヒット用語が強調表示され、目標テキスト、
すなわちヒット・パッセージが見つかった文書にハイパ
ーリンクが提供される。

【００９３】これによって所与の問い合わせの処理が完
了し、他の問い合わせがある場合、方法はボックス５６
０からボックス５１０へ進み、そうでない場合はボック
ス５７０で終了する。

【００９４】２Ｆ．目標領域を識別し問い合わせヒット
をソートする方法 本節では、図５のステップ５２０を実行する本発明の方
法を論じる。これを行うために下記の６つのステップが
実行される。問い合わせが行われると、前述のように、
索引モジュール９０および１００の結果を使用すること
によって文書が見つけられ、したがって、問い合わせ用
語に関する合致が見つかるはずである一連の文書がプロ
セッサに提供される。問い合わせ用語が出現するそのよ
うな各文書内で、プロセッサによって下記のステップ０
ないし６が実行される。この動作は、次の図６の議論で
より明らかになる。

【００９５】０．最初、この文書に関する含意用語生成
プログラムによって生成された第１の含意側用語が近接
バッファにシードされ、動作パラメータ・ペナルティし
きい値が*maximum-penalty-threshold* 、すなわち問い
合わせヒットに関して受け入れられる最大ペナルティに
設定される（好ましい実施形態では、このパラメータは
５０に設定される。このパラメータが、変更でき、かつ
ユーザによって制御できることは自明である）。

【００９６】前述のように、近接バッファは、この方法
では、文書内を有効に移動して用語ヒットが見つかる文
書の領域を画定する「ウィンドウ」に対応する。近接バ
ッファは、所与のウィンドウ内のあらゆるもの、ならび
にウィンドウのサイズおよび文書中のウィンドウの位置
を識別する情報を記憶する。ウィンドウのサイズは、文
書中のウィンドウの開始位置と、近接ホライズン、すな
わち文書中のウィンドウの終わり、すなわち下記で論じ
る可変位置によって定義することができる。

【００９７】１．近接ホライズンは、この問い合わせに
関して決定された近接ウィンドウ・サイズを加えること
によって近接バッファ中の第１のヒットの位置に基づい
て設定される。次いで、次のヒットが近接ホライズンを
越え、あるいは含意側用語ヒットがもはやなくなるまで
含意側用語ヒット生成プログラムを進行させることによ
って、すべての妥当な含意側用語ヒット、すなわち近接
ホライズン内で出現するすべての含意側用語ヒットの出
現で近接バッファが充填される。近接ホライズンを越え
る含意側用語ヒットが生成される場合には、後で生成で
きるように生成プログラム・ストアに残される。このよ
うな含意側用語ヒットは、下記の第２Ｈ節で説明する方
法によって生成される。

【００９８】好ましい実施形態では、（ａ）パラメータ
＊ｐｒｏｐｏｒｉｏｎａｌ−ｐｒｏｘｉｍｉｔｙ＊（た
とえば、１００）が（ユーザまたはアプリケーションに
よって）設定された場合にはそのパラメータに問い合わ
せ中の用語の数を乗じた値に等しく、あるいは（ｂ）ｐ
ｒｏｐｏｒｔｉｏｎａｌ−ｐｒｏｘｉｍｉｔｙパラメー
タを設定しない場合には、バッファ中の第１のヒットの
位置から＊ｐｒｏｘｉｍｉｔｙ−ｔｈｒｅｓｈｏｌｄ＊
（たとえば、３００）個の文字に等しい数の文字内の含
意側ヒットを選択するように設定される。これらのパラ
メータは、変更し、あるいは他の点で問い合わせに依存
させることができ、かつユーザと、実行中のアプリケー
ションまたはプロセスのどちらか、あるいはその両方に
よって制御することができる。

【００９９】２．近接バッファの現内容から得ることが
でき、かつペナルティがペナルティしきい値よりも小さ
な、最良スコア問い合わせヒットが、下記の第２Ｇ節で
説明する方法によって見つけられる。そのような合致が
得られない場合は、ステップ６へ進む。

【０１００】３．この問い合わせヒットのスコアが出力
バッファ中の最悪ヒットよりも低く、出力バッファがす
でに満杯である場合、このヒットは破棄され、方法は下
記のステップ６へ進む。この問い合わせヒットが、すで
に出力バッファにある他の問い合わせヒットに重なる場
合、前者のヒットがより良いスコアを有する場合には、
前者のヒットが後者のヒットで置き換えられ、あるいは
前者のヒットのスコアが後者のヒットのスコア以下であ
る場合には前者のヒットは破棄される。その他の場合、
この問い合わせヒットは、そのペナルティ・スコアに従
って出力バッファの適当なランクに挿入され、バッファ
がすでに満杯である場合はバッファ中の最悪バッファが
破棄される。出力バッファがまだ現在、満杯である場
合、パラメータｐｅｎａｌｔｙ−ｔｈｒｅｓｈｏｌｄが
出力バッファ中の最悪問い合わせペナルティに設定され
る。

【０１０１】４．出力バッファが満杯であり、最後のヒ
ットが零ペナルティを有する場合、方法は停止し、ヒッ
トを生成し、出力バッファの内容を返す。

【０１０２】５．生成すべき含意側ヒットがもはやない
場合、方法は停止し、出力バッファの内容を返す。

【０１０３】６．その他の場合、近接バッファ中の第１
の用語ヒットが近接バッファから削除され、方法はステ
ップ１へ進む。

【０１０４】問い合わせヒットを識別しソートする方法
の前述の要約は、図６のフローチャートによって分類さ
れる。一般に、方法６００は、問い合わせサイズに応じ
た固定サイズを有するウィンドウを文書上で移動し、
（第１の含意用語ヒットから）ウィンドウを文書上のあ
る点に固定するステップを含む。各ウィンドウ位置ごと
に、方法は問い合わせ語に関する合致を含むパッセージ
を探索する。そのような最良の合致は、所定の最大数の
完全合致が見つかり、あるいはすべての文書の探索が終
了するまで出力バッファに入れられる。

【０１０５】図６のボックス６１０で、方法は問い合わ
せ用語に関する合致を含む目標領域の識別を開始する。

【０１０６】ボックス６２０で、現文書に関する第１の
含意側用語ヒットが近接バッファにシードされ、ボック
ス６３０で、ペナルティしきい値が所定の最大値に設定
される。「含意側用語ヒット」は下記のように定義する
ことができる。問い合わせの各用語ごとに、用語／概念
関係ネットワークに、その問い合わせ用語を含意するこ
とができるある１組の用語がある。所与の問い合わせ用
語に関する合致は、その問い合わせ用語を厳密に含むこ
とも、あるいは、その問い合わせ用語を含意する何らか
の他の用語を含むこともできる。したがって、本明細書
では、どちらかのタイプの合致を含意側用語ヒットと呼
び、そのようなすべての問い合わせ用語に対する１組の
そのようなすべての含意側用語ヒットを「全体的な含意
側セット」と呼ぶことができる。

【０１０７】ボックス６４０で、前述のように、近接ホ
ライズンが設定され、すなわち、現目標パッセージに関
する次の含意側用語ヒットにウィンドウが位置決めされ
る（このボックスの第１のパスで、「次の」含意側用語
ヒットは第１の含意側用語ヒットである）。次いでボッ
クス６５０で、前述のステップ１で定義したすべての妥
当な含意側用語ヒットが近接バッファに充填される。

【０１０８】ボックス６６０で、方法は、現ペナルティ
しきい値よりも良い（すなわち、低い）ペナルティを有
する近接バッファ中の用語ヒットで構成できる問い合わ
せヒットがあるかどうかを判定する。第１のパスでは、
これは所定の最大ペナルティしきい値との比較である。
近接バッファ内の用語ヒットで構成できるそのような問
い合わせヒットがない場合、ボックス７４０で、近接バ
ッファ中の第１のヒットが削除され、ボックス６４０
で、近接ホライズンが、ウィンドウの始めを用いて近接
バッファ中の（新しい）第１の用語にリセットされる。

【０１０９】ボックス６５０で、近接バッファに再び、
（前述のステップ１で定義した）妥当な含意側用語ヒッ
トが充填され、この例では、近接ウィンドウが実際上、
ステップ６５０の前の反復に対して１含意側用語ヒット
だけ下向きに移動する。ボックス６６０で、現ペナルテ
ィしきい値よりも低いペナルティを有する近接バッファ
の（新しい）内容で構成できる問い合わせヒットがある
かどうかが再び判定され、プロセスが継続する。

【０１１０】この試験を満たす問い合わせヒットが見つ
かった場合、方法はボックス６７０へ進み、近接バッフ
ァ中の最良の問い合わせヒット（すなわち、最低ペナル
ティを有する問い合わせヒット）が「現」問い合わせヒ
ットとして指定される。近接バッファ中の最良スコア問
い合わせヒットは、前述の第２Ａないし２Ｃ節で一般的
に説明したように決定され、好ましい実施形態によって
これを行う詳細な手順を下記の第２Ｇ節に記載する。

【０１１１】ボックス６８０で、現問い合わせヒットの
ペナルティが出力バッファ中の最悪ヒットよりも良い
（低い）かどうかが判定される（最良問い合わせヒット
は、ディスプレイに出力できるように記憶され、あるい
は探索手順の完了時にファイルに記憶される）。そうで
ない場合、ボックス７３０で、現問い合わせヒットが破
棄され、ボックス７４０で、近接バッファから第１の問
い合わせヒットが削除され、方法は前述のように、ボッ
クス６４０に戻り、より良い問い合わせヒットでもう１
度試せるようにウィンドウを再位置決めする。

【０１１２】ボックス６８０で、現問い合わせヒットが
出力バッファ中の最悪ヒットよりも良い場合、ボックス
６９０で、より低いスコアの重なりが抑圧される。これ
は、目標パッセージが現問い合わせヒットの目標パッセ
ージに重なる問い合わせヒットが現問い合わせヒットと
比較され、より低いスコア（より高いペナルティ）を有
する問い合わせヒットが破棄される。この２つの問い合
わせヒットが同じペナルティ・スコアを有する場合、第
１の問い合わせヒットが保持される。

【０１１３】ボックス７００で、出力バッファが満杯で
ある場合、ボックス７１０で、プロセッサは出力バッフ
ァ中の最低スコア用語リストを破棄する。方法は次い
で、ステップ７２０へ進み、現問い合わせヒットが出力
バッファに挿入される。これは挿入ソートによって行わ
れ、すなわち、現問い合わせヒットのペナルティが出力
バッファ中の第１のヒットと比較され、そのペナルティ
の方が低い場合には、第１のヒットの上に挿入され、す
べての他のヒットは下向きに移動される。そうでない場
合、現ヒットのペナルティよりも低いペナルティが見つ
かるまで、現ヒット・ペナルティが出力バッファ中の次
のヒットのペナルティと比較され、見つかった時点で、
現ヒットが挿入され、他のヒットは下向きに移動され
る。これによって、出力バッファは常に、現ヒットの挿
入時にソートされる。

【０１１４】出力バッファ中の最低スコア・ヒットと比
較し上向きに移動する（実際には、対向する端部から移
動する）ことによる挿入や、探索が完了した後にソート
を行うことなど、他の変形例も可能である。他のソート
（ツリー・ソートなど）も適当である。しかし、挿入ソ
ートは、新しい現ヒット・ペナルティと、すでに記憶さ
れているペナルティを比較し、出力バッファを満杯にし
同時にソートする従来型の１つの方法である。

【０１１５】ボックス７５０で、最新の現問い合わせヒ
ットが追加された場合、方法は出力バッファが現在、満
杯であるかどうかを判定する。満杯である場合、ペナル
ティしきい値が出力バッファ中の最悪問い合わせのペナ
ルティしきい値に設定され（ボックス７６０）、いずれ
の場合も、ボックス７７０へ進む。この場合、出力バッ
ファ中の最後の問い合わせヒットが零ペナルティを有し
ていたかどうかが判定される。そうである場合、これ
は、出力バッファに零ペナルティ・ヒットが充填されて
いることを示し、それに続く探索点はなく、したがっ
て、ボックス７９０へ進み、出力バッファの内容が返さ
れる。ステップ５４０に戻り、前述のようにヒットの表
示、記憶などが行われる。出力バッファのサイズをユー
ザによって選択することも、あるいは実行中のプロセス
によって設定することもでき、したがって一般的に、こ
のサイズが可変であることに留意されたい。

【０１１６】ボックス７７０で、出力バッファ中の最後
の問い合わせヒットが零ペナルティを有さない場合、ボ
ックス７８０で、生成すべき含意側用語ヒットがもはや
ないかどうか、すなわち、索引からのすべての含意側用
語ヒットが終了したかどうかを判定する。生成すべきヒ
ットがもはやない場合、ボックス７９０へ進む。そうで
ない場合、ボックス７４０へ進み、近接バッファから第
１の含意側用語ヒットが削除され、近接ウィンドウが次
の含意側用語ヒットに再位置決めされる。次いで、再び
ボックス６４０へ進む。

【０１１７】図５の方法６００が完了した後、出力バッ
ファに最良（最低ペナルティ）から最悪までのランク順
に問い合わせヒットが充填される。

【０１１８】２Ｇ．最良スコア問い合わせヒットを判定
する方法 下記は、最良のスコアを有する問い合わせヒット、すな
わち、最低の集計ペナルティまたは組合せペナルティを
形成するために、現近接バッファのどの含意側用語ヒッ
トどうしを使用できるかを判定する適切な方法である。
したがって、この方法は、文書上のウィンドウ内に位置
する用語ヒットを実際にスコア付けする手順を提供す
る。

【０１１９】Ａ．問い合わせｑの連続問い合わせ用語を
ｑ１，ｑ２，．．．，ｑｍとし、現近接バッファ中の
（すなわち、近接バッファ中の第１の含意側用語ヒット
の近接ホライズン内）含意側用語ヒットのシーケンスを
ｘ１，ｘ２，．．．，ｘｎとする。近接バッファ中の第
１の用語ｘ１が１つの問い合わせ用語に整列し、各問い
合わせ用語が、それを含意する近接バッファ中の１つの
ｘｉｊと、それが欠落していることを示すマーカのどち
らかと対になるように、問い合わせ中の用語と近接バッ
ファ中の含意側用語とのすべての可能な整列ａ＝（ｑ
１，ｘｉｌ），（ｑ２，ｘｉ２），．．．，（ｑｍ，ｘ
ｉｍ）を探索する。このような整列は、そのような最良
ランクのヒット、すなわち、下記のランク付けアルゴリ
ズムによって割り当てられた最低ペナルティ・スコアを
有するヒットを見つけるために探索される。

【０１２０】Ｂ．各対（ｑｊ，ｘｉｊ）ごとに下記のペ
ナルティの和を求める。

【０１２１】１．形態学的変形例ペナルティ−−ｑｊと
ｘｉｊが同じ形態学的語根を有するが、同じ屈折形でも
同じ派生形でもない（すなわち、共に語根形であるとは
限らず、共に単数形であるとは限らず、共に三人称単数
形動詞であるとは限らない）場合、この２つのうちで語
根形ではないものに、関与する形態学的関係が屈折であ
るか、それとも派生であるかに応じてパラメータ＊ｉｎ
ｆｌｅｃｔｉｏｎ−ｐｅｎａｌｔｙ＊または＊ｄｅｒｉ
ｖａｔｉｏｎ−ｐｅｎａｌｔｙ＊によって決定される量
だけペナルティを課す。好ましい実施形態では、これら
のペナルティはそれぞれ、０．０８および０．１であ
る。このランク付けペナルティ成分が、それぞれの異な
るペナルティを使用するように修正することも、あるい
はそれぞれの異なる種類の屈折関係または派生関係に対
するそれぞれの異なるペナルティを組み込むように修正
することもできることは自明である。

【０１２２】２．分類学的局限化ペナルティ−−包摂分
類法によればｑｊ（の語根）がｘｉｊ（の語根）よりも
一般的な用語である場合、整列に、パラメータ＊ｄｅｓ
ｃｅｎｄａｎｔｓ−ｐｅｎａｌｔｙ＊によって決定され
る量だけペナルティを課す（好ましい実施形態では、こ
のパラメータは０．１である。このランク付けペナルテ
ィ成分が、それぞれの異なるペナルティを使用するよう
に修正することも、あるいはより一般的な用語とより特
定的な用語との間の意味論的距離の次元を組み込むよう
に修正することもできることは自明である）。

【０１２３】３．意味論的含意ペナルティ−−既知の含
意関係によればｑｊ（の語根）がｘｉｊ（の語根）によ
って意味論的に含意される場合、整列に、パラメータ＊
ｅｎｔａｉｌｍｅｎｔｓ−ｐｅｎａｌｔｙ＊によって決
定される量だけペナルティを課す（好ましい実施形態で
は、このパラメータは０．１である。このランク付けペ
ナルティ成分が、異なるペナルティを使用するように修
正することも、あるいは問い合わせ用語と含意側用語と
の間の含意強度の次元を組み込むように修正することも
できることは自明である）。

【０１２４】４．欠落用語ペナルティ−−ｑｊ（の語
根）が前述の関係（同じ形態論的語根、または語根間の
分類学的局限化関係、または語根間の意味論的含意関
係）では近接バッファ中のどのｘｉｊ用語にも整列でき
ず、したがって、欠落しているとマーク付けされた場
合、その用語に、下記のように決定されるペナルティを
課す。その用語が下記の統語論的語クラスのうちの１つ
に存在する場合、（副詞、助詞、接続詞、頭文字、間投
詞、法助動詞、名前接頭辞、機能語、進行形、前置詞、
代名詞、句読点、タイトル）＊ｍｉｓｓｉｎｇ−ｑｕａ
ｌｉｆｉｅｒ−ｐｅｎａｌｔｙ＊によってペナルティを
課す。その用語が動詞であり、あるいは動詞である可能
性がある場合は、＊ｍｉｓｓｉｎｇ−ｖｅｒｂ−ｐｅｎ
ａｌｔｙ＊によってペナルティを課す。その用語が下記
の統語論的語クラスのうちの１つに存在する場合には、
（形容詞、決定詞）＊ｍｉｓｓｉｎｇ−ａｄｊｅｃｔｉ
ｖｅ−ｐｅｎａｌｔｙ＊によってペナルティを課す。そ
の他の場合は、＊ｍｉｓｓｉｎｇ−ｔｅｒｍ−ｐｅｎａ
ｌｔｙ＊によってペナルティを課す。

【０１２５】好ましい実施形態では、ｍｉｓｓｉｎｇ−
ｑｕａｌｉｆｉｅｒ−ｐｅｎａｌｔｙは２であり、ｍｉ
ｓｓｉｎｇ−ｖｅｒｂ−ｐｅｎａｌｔｙは５であり、ｍ
ｉｓｓｉｎｇ−ａｄｊｅｃｔｉｖｅ−ｐｅｎａｌｔｙは
７．５であり、ｍｉｓｓｉｎｇ−ｔｅｒｍ−ｐｅｎａｌ
ｔｙは１０である。このランク付けペナルティ成分は、
それぞれの異なるペナルティまたはそれぞれの異なるペ
ナルティ範疇を使用するように修正することも、あるい
は、欠落している用語に対するペナルティを決定するた
めの用語頻度または語重要性あるいは統語論的役割の次
元を組み込むように修正することができる。

【０１２６】Ｃ．累算された前述のペナルティに、整列
全体に関して求められた下記のペナルティを加える。

【０１２７】５．近接ランク付けペナルティ−−テキス
ト中の連続含意側用語対の出現順の整列中のこの各連続
含意側用語対ごとに、単一の文字よりも大きな含意側用
語間のギャップに、含意側用語間の文字数よりも１だけ
少ない数にパラメータ＊ｇａｐ−ｐｅｎａｌｔｙ−ｆａ
ｃｔｏｒ＊を乗じた値に等しい量だけペナルティを課
す。好ましい実施形態では、このパラメータは０．００
５である。このランク付けペナルティ成分が、異なるペ
ナルティ因子を使用するように修正することも、あるい
は、語カウントまたは文字カウント以外の他の近接尺度
を使用して語間のギャップを測定するように修正するこ
ともできることは自明である。

【０１２８】６．置換ペナルティ−−各連続問い合わせ
用語対ごとに、整列中の対応する含意側用語がテキスト
において同じ順序でない場合、このヒットに、パラメー
タ＊ｏｕｔ−ｏｆ−ｏｒｄｅｒ−ｐｅｎａｌｔｙ＊に等
しい量だけペナルティを課す（好ましい実施形態では、
このパラメータは０．２５である。このランク付けペナ
ルティ成分が、異なるペナルティ因子を使用するように
修正することも、あるいは、ヒット中の用語の順序が問
い合わせ中の用語の順序と異なる程度の様々な他の尺度
を使用するように修正することもできることは自明であ
る）。

【０１２９】７．内部境界ペナルティ−−整列の最初の
含意側ヒットから整列の最後の含意側ヒットまでの領域
によってカバーされるテキストの部分を、テキストのそ
の部分に含まれる各文境界またはパラグラフ境界に関し
て走査し、境界が文境界であるか、それともパラグラフ
境界であるかに応じて＊ｃｒｏｓｓ−ｓｅｎｔｅｎｃｅ
−ｐｅｎａｌｔｙ＊または＊ｃｒｏｓｓ−ｐａｒａｇｒ
ａｐｈ−ｐｅｎａｌｔｙ＊に等しいペナルティを加え
る。好ましい実施形態では、これらのパラメータはそれ
ぞれ、０．１および５０である。このランク付けペナル
ティ成分がそれぞれの異なるペナルティを使用するよう
に修正できることは自明である。

【０１３０】任意の点で、部分的に生成された整列のペ
ナルティ・スコアがすでに、生成できる何らかの他の整
列のスコアよりも悪く、あるいは、指定されたペナルテ
ィしきい値よりも悪いことを判定することができる場
合、悪い方の部分的整列をその点で破棄し、その後は検
討しないようにすることができる。そのような探索を実
行する多数の従来型の技法が、コンピュータ科学探索に
関する文献に記載されている。

【０１３１】Ｄ．ペナルティしきい値よりも良いペナル
ティがある場合には、最良（最小）総ペナルティを選択
する。これによって、用語のペナルティ・スコア付けが
完了し、したがって、最良スコア問い合わせヒットの現
近接バッファからの検索が完了する。

【０１３２】２Ｈ．含意側用語ヒットを生成する方法 この方法は、用語／概念関係ネットワーク１１０を使用
する。用語／概念関係ネットワーク１１０は、オフライ
ンで手動で構築することも、あるいは、手動で構築した
関係および形態学的規則の知識ベースを使用して、第１
節で説明し、さらに下記の第２Ｉ節で詳しく説明する方
法によって、索引付けプロセス中に自動的に構築するこ
ともできる。このネットワークでは、索引付けされた材
料の本体で出現し、あるいは問い合わせ用語で出現する
可能性がある所与の用語が表現され、この用語を、それ
が示すことができる１つまたは複数の概念に関連付ける
ことができる。これらの語および概念は、下記の形態学
的関係、分類学的関係、意味論的含意関係によって互い
に関係付けることができる。

【０１３３】１．用語ｘは、屈折用語または派生用語ｙ
の語根形である。

【０１３４】２．用語または概念ｘは、用語または概念
ｙを分類学的に包摂する（すなわち、用語または概念ｘ
は用語または概念ｙよりも一般的な用語または概念であ
る）。

【０１３５】３．用語または概念ｘは、用語または概念
ｙによって含意することができる。

【０１３６】一般に、これらの関係は、データ入力によ
ってオフラインで構築されたそのような関係（１２０、
１５０、１８０）の知識ベースで探さなければならな
い。しかし、ある種の形態学的関係は、テキスト内で出
会った語の屈折形および派生形に形態学的規則を適用す
ることによって自動的に導くことができる。そのような
形態学的規則は一般に、計算言語学における従来型のシ
ステムの一部である。

【０１３７】問い合わせｑ＝ｑ１，ｑ２，．．．，ｑｍ
に関する含意側用語（「全体的な含意側セット」は、ｑ
中の用語ｑｉを含意する本体内で出現する１組のすべて
の用語である。この場合、下記のどれかが成立する場合
には、用語ｘは用語ｑｉを含意する。

【０１３８】１．ｘまたはｘの語根は、ｑｉまたはｑｉ
の語根に等しい。

【０１３９】２．ｘまたはｘの語根は、ｑｉまたはｑｉ
の語根、あるいはｘが示す概念を分類学的に包摂し、あ
るいは、ｘの語根は、ｑｉまたはｑｉの語根、あるいは
ｑｉまたはｑｉの語根が示す概念を分類学的に包摂す
る。

【０１４０】３．ｘまたはｘの語根は、ｑｉまたはｑｉ
の語根、あるいはｘが示す概念によって意味論的に含意
され、あるいは、ｘの語根は、ｑｉまたはｑｉの語根、
あるいはｑｉまたはｑｉの語根が示す概念によって意味
論的に含意される。

【０１４１】問い合わせｑ＝ｑ１，ｑ２，．．．，ｑｍ
に関する含意側用語ヒットは、ｑ中の用語ｑｉまたはｑ
中の用語ｑｉが示す概念を含意する本体中のすべての用
語出現のシーケンスである。これらの含意側用語ヒット
は、それぞれ、（最初は、本体のすべての文書のデフォ
ルト順序によって決定され、次に文書内の用語出現の位
置によって決定される）本体中の含意側用語ヒットの出
現順に各含意側用語の出現を生成する、各含意側用語ご
との生成プログラムの集合を作成することによって本体
中のこれらの含意側用語ヒットの出現順に生成される。
任意の生成ステップで、生成に利用できる最初のヒット
を有する含意側用語生成プログラムを選択し、その用語
ヒットを生成することによって、次に生成される含意側
用語ヒットが生成される。次の生成ステップでは、異な
る含意側用語生成プログラムが、生成するために利用で
きる最初のヒットを有することができる。この含意側用
語ヒット生成プログラムを繰り返し呼び出して、あるフ
ァイル中のある用語出現から始まり、その語根用語出現
を越えたある近接ホライズンに達するまで継続する、本
体のウィンドウ内で出現するすべての含意側用語ヒット
を見つけることができる。

【０１４２】２Ｉ．用語／概念関係ネットワークの生成 索引付けされた材料中の各語または句に出会う、上記の
第１節で説明した索引付け時に（あるいは、別々のパス
中に）、本体が分析される際に構築される語および概念
ならびに語および概念間の関係の成長する用語／概念関
係ネットワーク１１０でその語または句が検索される。
その語又は句がまだ、この用語／概念関係ネットワーク
１１０に存在しない場合には、このネットワークに追加
される。

【０１４３】そのような各語または句に初めて出会う際
に、その語または句は、語および概念の関係（１２０、
１５０、１８０）からなる手動で構築された外部知識ベ
ースでも検索され、このような外部ネットワークで見つ
かった場合、この語または句によって含意されることが
知られており、あるいはこの語または句の派生形または
屈折形である外部ネットワーク中のすべての語および概
念が、それらの語および概念間の既知の関係と共に、成
長する用語／概念関係１１０ネットワークに追加され
る。そのような語または句が外部ネットワークで見つか
らない場合、その語または句は、形態学的規則によって
分析され、外部知識ベース（１２０、１５０、１８０）
において知られている語の屈折形または派生形であるか
どうかが判定され、そうである場合、その語根との形態
学的関係が用語／概念関係ネットワークに記録され、そ
の語根形は、本体で出現した場合と同様に扱われる（す
なわち、その語根形が外部ネットワークで検索され、す
べてのその含意、屈折、派生、関係が追加される）。

【０１４４】このプロセスの終わりには、本体で出現す
るすべての用語と、それらの用語によって含意され、あ
るいはそれらの用語に形態学的に関係するすべての概念
を、それらの用語および概念間のすべての既知の形態学
的関係、分類学的関係、含意関係と共に含む用語／概念
関係ネットワークが構築されている。

【０１４５】２Ｊ．問い合わせサイズ手順適応 一般に、短い問い合わせをうまく処理することができな
い従来型の検査方法に対して、本発明の方法は、トライ
アル・ランにおいて、２つまたは３つの語、あるいはお
そらく最大約６つの語からなる短い問い合わせを特に効
果的に処理することが証明されている。したがって、１
つまたはある数Ｎよりも多くの語を探索する際に従来型
の語探索技法を使用することによって本発明をさらに機
能強化することができる。数Ｎは、事前に設定し、ある
いは探索結果が成功したことに応答してユーザまたはプ
ロセスによって選択することができ、生成された結果に
応じて３ないし６以上でよい。そのようなシステムは、
従来型の技法と本発明の両方を最もうまく使用し、した
がって、その動作は、小数の語しか有さない問い合わせ
の特に困難な領域に制限される。

【０１４６】一般に、短い問い合わせをうまく処理する
ことができない従来型の検査方法に対して、本発明の方
法は、トライアル・ランにおいて、２つまたは３つの
語、あるいはおそらく最大約６つの語からなる短い問い
合わせを特に効果的に処理することが証明されている。
したがって、１つまたはある数Ｎよりも多くの語を探索
する際に従来型の語探索技法を使用することによって本
発明をさらに機能強化することができる。数Ｎは、事前
に設定し、あるいは探索結果が成功したことに応答して
ユーザまたはプロセスによって選択することができ、生
成された結果に応じて３ないし６以上でよい。そのよう
なシステムは、従来型の技法と本発明の両方を最もうま
く使用し、したがって、その動作は、小数の語しか有さ
ない問い合わせの特に困難な領域に制限される。

【０１４７】２Ｊ．文書検索応用例 このパッセージ検索技法を従来型の文書検索問題に応用
し、各文書が含む最良のパッセージ・スコアを各文書に
与えることによって文書を検索しランク付けすることが
できる。

【図面の簡単な説明】

【図１】 本発明のシステムのブロック図である。

【図２】 本発明の索引付け・分析システムの対話モジ
ュールの図である。

【図３】 本発明のシステムによって生成された例示的
な探索結果を示す図である。

【図４】 本発明による一般的な問い合わせ処理方法の
フローチャートである。

【図５】 本発明の方法のさらに詳しい好ましい実施形
態を示すフローチャートである。

【図６】 本発明の方法のさらに詳しい好ましい実施形
態を示すフローチャートである。

【符号の説明】

１０ コンピュータ・システム ２０ プロセッサ ３０ メモリ ４０ キーボードおよびマウス ５０ 出力装置 ６０ 検索エンジン ７０ 文書本体 ８０ 用語出現索引 ８５ 生成プログラム・スコア ９０ 出力バッファ ９５ 近接バッファ １００ 語分析モジュール １１０ 用語／概念関係ネットワーク １３０ 汎用分類法 １４０ 局限分類法 １５０ 意味論的含意関係 １６０ 汎用含意データベース １７０ ドメイン特有含意データベース １８０ レキシコン １９０ 汎用レキシコン ２００ ドメイン特有局限レキシコン

Claims (9)

【特許請求の範囲】
1. 【請求項１】 プロセッサに結合されたメモリに記憶さ
   れているデータベース中の文書の情報を見つける方法で
   あって、この方法が、前記プロセッサによって実行され
   るプログラム・ステップによって実施され、 （１）少なくとも１つの問い合わせ用語を含む探索問い
   合わせを受け取るステップと、 （２）前記少なくとも１つの問い合わせ用語に対応する
   少なくとも１つのヒット用語を含む少なくとも１つのヒ
   ット・パッセージを前記文書から生成するステップと、 （３）それぞれ、少なくとも第１の問い合わせ用語およ
   び第２の問い合わせ用語に対応する、少なくとも第１の
   ヒット用語および第２のヒット用語に関して、前記第１
   のヒット用語と第２のヒット用語との間の第１の距離お
   よび前記第１の問い合わせ用語と第２の問い合わせ用語
   との間の第２の距離を求めるステップと、 （４）前記第１の距離と前記第２の距離との比較に基づ
   く大きさを有する因子を生成するステップと、 （５）前記因子の大きさを組み込んだ前記ヒット・パッ
   セージに関するスコアを生成するステップとを含む方
   法。
2. 【請求項２】 プロセッサに結合されたメモリに記憶さ
   れているデータベース中の文書の情報を見つける方法で
   あって、この方法が、前記プロセッサによって実行され
   るプログラム・ステップによって実施され、 （１）少なくとも第１の問い合わせ用語と第２の問い合
   わせ用語を第１の順序で含む探索問い合わせを受け取る
   ステップと、 （２）少なくとも、前記第１の問い合わせ用語に対応す
   る第１のヒット用語と、前記第２の問い合わせ用語に対
   応する第２のヒット用語とを含む、少なくとも１つのヒ
   ット・パッセージを前記文書から生成し、前記第１のヒ
   ット用語および第２のヒット用語が第２の順序であるス
   テップと、 （３）前記第１の距離と前記第２の距離との比較に基づ
   く大きさを有する因子を生成するステップと、 （４）前記因子の大きさを組み込んだ前記ヒット・パッ
   セージに関するスコアを生成するステップとを含む方
   法。
3. 【請求項３】 さらに、 ステップ４の後に、最良スコアの前記ヒット・パッセー
   ジを判定するステップと、 少なくとも前記最良スコア・ヒット・パッセージを受け
   取るステップとを含む請求項２に記載の方法。
4. 【請求項４】 さらに、 ステップ４の後に、最良スコアの前記ヒット・パッセー
   ジを判定するステップと、 少なくとも、前記最良スコアのヒット・パッセージを含
   む文書を受け取るステップとを含む請求項２に記載の方
   法。
5. 【請求項５】 コンピュータ・システムのプロセッサに
   結合されたメモリに記憶されているデータベース中の文
   書の情報を見つける方法であって、コンピュータ・シス
   テムがさらに、前記プロセッサに結合された近接バッフ
   ァと出力バッファとを含み、この方法が、前記プロセッ
   サによって実行されるプログラム・ステップによって実
   施され、 （１）少なくとも１つの問い合わせ用語を含む探索問い
   合わせを受け取るステップと、 （２）前記データベース中の少なくとも１つの前記文書
   の少なくとも１つの目標領域を判定するステップと、 （３）ペナルティ式を所定の最大値に設定するステップ
   と、 （４）前記目標領域内の前記問い合わせ用語に対応する
   問い合わせヒットを判定し、前記各問い合わせヒットが
   それに対応する問い合わせ用語にどれだけ密に対応する
   かを反映するスコアを前記問い合わせヒットに関連付け
   るステップと、 （５）前記近接バッファに前記問い合わせヒットを記憶
   するステップと、 （６）前記近接バッファの最良スコアの問い合わせヒッ
   トを現問い合わせヒットとして指定するステップと、 （７）前記出力バッファが満杯である場合、最低スコア
   の問い合わせヒットを破棄するステップと、 （８）前記現問い合わせヒットを前記出力バッファに挿
   入するステップと、 （９）出力バッファが現在、満杯である場合、前記ペナ
   ルティしきい値を出力バッファ中の最低スコアの問い合
   わせヒットのスコアに設定するステップと、 （１０）所定の基準が満たされた場合、ステップ１３へ
   進み、そうでない場合は、ステップ１１へ進むステップ
   と、 （１１）生成すべき含意側用語がまだある場合、ステッ
   プ１２へ進み、その他の場合は、ステップ１３へ進むス
   テップと、 （１２）前記文書に対して目標領域を再位置決めし、ス
   テップ４へ進むステップと、 （１３）出力バッファの内容を返すステップとを含む方
   法。
6. 【請求項６】 前記コンピュータ・システムのプロセッ
   サに結合されたメモリに記憶されているデータベース中
   の文書の情報を見つけるコンピュータ・システムにおい
   て、 複数の問い合わせ用語を含む探索問い合わせを受け取る
   ように構成された問い合わせモジュールと、 それぞれ、少なくとも１つの前記問い合わせ用語に対応
   する少なくとも１つのヒット用語を含む、パッセージを
   前記文書から検索するように構成された検索モジュール
   と、 前記問い合わせ用語の出現順と、前記パッセージに現れ
   前記問い合わせ用語に対応するヒット用語の出現順との
   比較に基づいて前記パッセージに関するスコアを生成す
   るように構成されたスコア付けモジュールとを含むコン
   ピュータ・システム。
7. 【請求項７】 データベース中の文書のパッセージを検
   索しランク付けする探索システムであって、 少なくとも１つの問い合わせ用語を含む探索問い合わせ
   に応答して、それぞれ、少なくとも１つの前記問い合わ
   せ用語に対応する少なくとも１つのヒット用語を含む、
   パッセージを前記文書から検索するように構成された検
   索モジュールと、 前記問い合わせ用語の出現順と、前記パッセージに現れ
   前記問い合わせ用語に対応するヒット用語の出現順との
   比較に基づいて前記パッセージに関するスコアを生成す
   るように構成されたスコア付けモジュールとを含むコン
   ピュータ・システム。
8. 【請求項８】 前記コンピュータ・システムのプロセッ
   サに結合されたメモリに記憶されているデータベース中
   の文書の情報を見つけるコンピュータ・システムにおい
   て、 複数の問い合わせ用語を含む探索問い合わせを受け取る
   ように構成された問い合わせモジュールと、 少なくとも２つの前記問い合わせ用語に対応する少なく
   とも２つの前記ヒット用語を含む少なくとも１つのパッ
   セージを前記文書から検索するように構成された検索モ
   ジュールと、 前記少なくとも２つの前記ヒット用語間の距離を組み込
   んだ大きさを有する因子に基づいて前記パッセージに関
   するスコアを生成するように構成されたスコア付けモジ
   ュールとを含むコンピュータ・システム。
9. 【請求項９】 複数の問い合わせ用語を含む探索問い合
   わせに応答して、少なくとも２つの前記問い合わせ用語
   に対応する少なくとも２つの前記ヒット用語を含む少な
   くとも前記第１のパッセージを検索するように構成され
   た検索モジュールと、 前記少なくとも２つの前記ヒット用語間の距離を組み込
   んだ大きさを有する因子に基づいて前記パッセージに関
   するスコアを生成するように構成されたスコア付けモジ
   ュールとを含むコンピュータ・システム。