図面 (/)

技術 複数の細分度のインデックス付けとクエリ—処理を効果的に用いてクエリ—の拡張を支援する方法、及び装置

出願人 日本電気株式会社
発明者 ウェンシャンリー
出願日 1999年5月20日 (22年0ヶ月経過) 出願番号 1999-140695
公開日 2000年5月16日 (21年0ヶ月経過) 公開番号 2000-137738
状態 特許登録済
技術分野 検索装置
主要キーワード 細分度 語空間 ランク付け処理 拡張クラス ブーリアン演算 追加ワード 上位概念語 検索メカニズム
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2000年5月16日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (13)

課題

サイズの小さいインデックスを用いてクエリーを効果的に拡張し、連続的にクエリーを処理するための方法、及び装置を提供する。

解決手段

クエリーは、元のクエリーでユーザにより指定されたワード意味的に類似するワード、及び構文的に関連するワードを用いて、概念的に拡張される。本発明は、効果的なクエリーの拡張を支援するために、複数の細分度を有する情報と、処理構造の概念を用い、インデックス付け、クエリー処理、及びランク付けの各処理を含む。

概要

背景

クエリーを適用することによって文書検索する従来の検索システムは、文書を分類する共通の原理方法論に基づいている。文書は通常、熟練者又は司書により、事前に指定され、調整された用語を用いて、手作業インデックス付けされる。文書はまた、その文書に含まれる語(ワード)に基づいてインデックス付けされることもある。ユーザは、指定可能な用語から選択したワードと、それらの間を適当なブーリアン演算子で連結して文書の検索を行う。このようなタイプのシステムでは、厳密なマッチング戦略が用いられる。このアプローチは、単純で高精度といった多くの利点を有するものの、ワード・ミスマッチの問題が生じる。

情報検索におけるワード・ミスマッチの問題は、作者がその文書で、ある概念を表すのに、あるワードを使用している場合に、ユーザが、それと同じ概念をクエリーにおいて指定する際、別のワードを使用してしまうことによって生じる。図1は、「car(乗用車)」及び「dealer(販売店)」に関連付けられた、ハイパーテキストマークアップ言語HTML)の文書において使用されるワードが、様々な文書の間で異なることがあることを示している。拡張可能なマークアップ言語(XML)や標準一般化マークアップ言語(SGML)のような、HTML以外の言語も用いられる。ユーザが、「automobile(自動車)」と「dealer(販売店)」というワードをクエリーに用いる場合、ワード・ミスマッチの問題で、対象となる文書を1つも検索できない結果になる。

尚、本明細書では、検索の対象が、主に英語を含むものと仮定しているため、検索に使用するクエリーの各要素は、英語で記述されている。しかし、これらは、ユーザの要求に応じて、どの国の言語で表現することも可能である。ここでは、前記英語で記述された要素に続いて(必要に応じ)括弧内に、その要素の日本語における意味を表すことにする。従って、当該括弧内の日本語は、単にクエリーの要素の意味を説明するためのものに過ぎず、クエリーの結果には影響を及ぼさない。

クエリーの拡張は、このような問題を解決する技法として示唆されている。このアプローチは、意味の類似したワード(例えば、類義語や他の関連する意味を有するワード)及び構文的に関連するワード(例えば、一定の頻度以上で同じ文書内に同時に現れるワード群は、構文的共起ワードである)をクエリー内のワードとして用いることによってクエリーを拡張するものである。こうしてクエリーが拡張されると、関連する文書内のワードにマッチする可能性が高まる。クエリーの拡張が使用されると、「car dealer(乗用車の販売店)」というワードを含むクエリーは、以下のように同様の意味の用語を含むように拡張される。

行1. [(「car(乗用車)」OR「automobile(自動車)」OR「auto(車)」OR「sedan(セダン)」)OR
行2. (「Ford(フォード車)」OR「Buick(ビュイック車)」)]AND
行3. (「dealer(販売店)」OR「Showroom(ショールーム)」OR「SalesOffice(販売所)」)。

上記例に含まれるクエリーの拡張には、2つのタイプがある。行1と行3のクエリーの拡張は、用語の意味において「car」と「dealer」に関連する追加ワードを追加するものである。即ち、意味的に類似するワードを追加するものである。「automobile」、「auto」、及び「sedan」は、「car」というワードに類似する意味を有するワードである。同様に、「Showroom」と「SalesOffice」は、「dealer」というワードに類似する意味を有するワードである。他のタイプのクエリーの拡張は、行2に示すものであり、これは例えば、構文的共起関係によるものである。ワールドワイドウエブ(単にウエブとも言う)で用いられる多くのワードは、実際には固有名詞であり、用語辞書には見つからない。例えば、固有名詞は、Ford、Buick、NBA、及びNFL(National Football League)といったものである。前述したように、構文的共起関係は、2つのワードが、同じ文書に同時に現れる頻度を分析することによって導出される。これは、2つのワードが頻繁に同じ文書内に現れる場合には、それらのワードが関連している可能性が高いという仮定に基づくものである。例えば、「Ford」と共に発生するワードとして、「dealer(販売店)」、「body shop(車体工場」、「Mustang(マスタング:フォード社製の車の名前)」、「Escort(エスコート:フォード社製の車の名前)」等が考えられる。

クエリーの拡張を支援するために、用語の意味によって関連付けられたワードのインデックスと、共起情報のような構文的関係が適切に維持されなければならない。用語の意味によってワードに関連付けられたインデックスは、階層構造意味ネットワーク、又は関連ワード階層クラスタとして構成される。前記階層構造については、1997年8月、ギリシャのアテネで行われた、the 23rd International Conference on Very Large Data Basesの予稿集ページ538-547、W. Li他の「Facilitating Multimedia Database Exploration through Visual Interfaces and Perpetual Query Reformulations」を参照されたい。また、前記意味ネットワークについては、1990年、International Journal of Lexicography 3(4)、ページ245-264における、G. A. Millerの「Nouns in WordNet: A Lexical Inheritance System」を参照のこと。また、関連ワードの階層クラスタについては、1983年、ニューヨーク、McGraw-Hill、ページ118-155の、G. Salton他による「TheSMARTand SIRE Experimental Retrieval Systems」を参照のこと。構文的共起関係のような構文的関係は、2項関係で表されるので、構文的関係のインデックスのサイズは非常に大きい。この問題を解決するため、いくつかの技法が提案されている。これらの技法については、1992年、デンマークにおけるthe Fifteenth annual InternationalACMSIGIR Conferenceの予稿集の、G. Grefenstetteによる「Use of syntactic context to produce term association lists for text retrieval」、1996年、スイスチューリッヒにおけるthe 19th Annual International ACM SIGIR Conferenceの予稿集の、J. Xu他による「Query Expantion Using Local and Global Document Analysis」、1997年、アメリカ合衆国ペンシルニアフィラデルフィアにおける、the20th Annual International ACM SIGIR Conferenceの予稿集の、C. Jacqueminによる「Guessing Morphology from Terms and Corpora」を参照のこと。こうした技法は、発生頻度の分析、及び形態素規則(例えば、全てのワードをその起源となる形態に変換する)や用語辞書の使用を含むものである。

ワード・ミスマッチの問題に関しては、情報検索(IR)の分野において、かなりの研究がされてきている。これについては、1983年、McGraw-Hill BookCompany発行の、G. Salton他による「Introduction to Modern Information Retrieval」、1989年、Addison-Wesley Publishing Company, Inc発行の、G.Saltonによる「Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer」、及び1997年、アメリカ合衆国カリフォルニアサンフランシスコ、Morgan Kaufmannの、K. Sparck Jones他による「Readings in Information Retrieval」を参照のこと。

しかし、この研究の殆どが、適合率再現率といった、検索の基準に関する点を指向したものである。クエリーの拡張を効果的に支援する方法(1993年、メリーランド州Gaithersburgで行われたthe 3rd Text Retrieval Conferenceの予稿集の、C. Buckley他による「Automatic Query Expansion UsingSMART」参照)やインデックス付けのメカニズムを示唆した研究がいくつか有るが、満足する解決法のない問題が依然として2つ残っている。第1の問題は、ある文書の集合(例えば、ウエブ)内の多くのワードが別個の固有名詞であり、各ワードが意味的に同じワード及び構文的に関連したワードを多く有するので、インデックスのサイズが極めて大きくなってしまうことである。第2の問題は、クエリーが追加ワードによって拡張されるので、クエリーの処理コストが高くなってしまうことである。

ウエブから収集された文書情報を取り扱う際には、文書の数が非常に多くなり、使用されているワードが極めて多様で、一貫性がなく、時には間違っている(例えば、タイプエラー)ため、これらの問題は、ますます顕著になる。ある研究では、ウエブに関する殆どのユーザ・クエリーは、通常、ワードを2つ有している。これについては、1995年、Digital Libraries(DL '95)の予稿集で、B.Croft他の「Providing Government Information on the Internet: Experienceswith THOMAS」を参照されたい。しかし、クエリー拡張を用いれば、クエリーの長さは実質的に長くなる。結果的に、ウエブ上の既存のサーチエンジンのほとんどは、クエリー拡張機能を提供できないことになる。

ここで、クエリー拡張の分野における既存の研究を概説する。クエリー拡張は、IRの分野において、かなりの注目を集めた。しかし、いままで注目されてきた部分は、クエリーの拡張によって、改善される検索の基準(即ち、適合率及び再現率)の程度を評価することであった。別の研究では、与えられたクエリーのワードに関して、1組の類似する用語を識別するために、辞書構築することに焦点があてられてきた。しかし、今までの研究は、クエリーが拡張された場合のクエリーの効率的な処理の問題や、クエリーの拡張及び処理を行うのに用いられるインデックスのサイズを小さくするといった点に取り組んでいない。更に、厳密なマッチング及び類似的なマッチングに基づいて文書をランク付けする問題は、困難なものとして残されたままである。

SMARTは、よく知られた先進情報検索システムの1つである。これに関しては、1971年、アメリカ合衆国ニュージャージー州Englewood CliffsのPrentice-Hallから発行されたGerard Salton編集のThe SMART Retrieval System -Experiments in Automatic Document Processing、第12章の、R. T. Dattolaによる「Experiments with a fast algorithm for automatic classification」、及び上記文献の、G. Salton他による「The SMART and SIRE Experimental Retrieval Systems」を参照のこと。SMARTでは、各文書が用語のベクトルで表される。ベクトルのそれぞれの位置は、文書内の対応する用語の重み(重要性)を表している。N個の異なる用語を有するM個の文書の集合は、M×Nの行列で表される。クエリーもまた用語のベクトルとして表される。文書の検索は、クエリー・ベクトルと各文書のベクトルとの余弦に対応する類似性の計算に基づく。他の、よく知られたシステムには、INQUERYがある。これについては、1995年、Information Processing and Managementの3:327-332で、J. Callan他による「Trec and tipster experiments with inquery」を参照のこと。

潜在的意味インデックス(LSI)は、辞書的なマッチングによる個別の用語検索の替わりに、統計的に導出された概念インデックスに依存する技法である。これについては、1990年、Journal of the America Society of Information Science、41:391-407の、R. Harshman他による「Indexing by latent semantic analysis」、及び1995年、the 1995ACMConference on Supercomputingの予稿集で、M. W. Berry他による「Computational Method for Intelligent Information Access」を参照されたい。LSIは、ワードの使用法に、いくつかの見えない構造、即ち潜在的な構造があることを仮定し、その構造は、文書におけるワードの発生を分析することによって外部化される必要がある。従って文書は、非常に大きな範囲の用語空間におけるベクトルとして考えられ、そのベクトルの個々の要素は与えられた文書における特定の用語の発生頻度を表している。全体及び局所的重み付けに基づく、より洗練された基準も使用されうる。短縮された特異値分解SVD)が、文書に亘るワード使用の構造を評価する。これについては、1989年、アメリカ合衆国メリーランド州ボルチモアのJohns-Hopkinsの、G. Golub他による「Matrix Computations」第2版を参照されたい。ここでは、検索が、特異値を有するデータベース、及び短縮されたSVDから得られたベクトルを使用して実行される。LSIの予備的評価では、この情報検索のアプローチは、個々の用語に基づくものより粗い基準とされている。

自動化されたクエリー拡張は、ワード・ミスマッチ問題を取り扱う技法として長い間示唆されてきた。これについては、1994年、アイルランド共和国ダブリンで行われたthe 17th Annual InternationalACMSIGIR Conferenceの予稿集で、E. Voorheesによる「Query Expansion Using Lexical-Semantic Relations」を参照されたい。あるアプローチでは、類語辞典を用いてクエリーを拡張し、関連する文書内でワードがマッチする可能性を高めている。研究では、単に一般的な類語辞典を用いるだけでは、改善に限界があることが分かっている。多くの革新的技法も提案されている。1994年、the 3rd International Conferenceon Information and Knowledge Managementの予稿集の、O. Kwon他による「Query Expansion Using Domain Adapted, Weighted Thesaurus in an Extended Boolean Model」、1993年、アメリカ合衆国ペンシルバニア州ピッツバーグで行われたthe 16th Annual International ACM SIGIR Conferenceの予稿集の、E. Voorheesによる「Concept Based Query Expansion」、同予稿集の、E. Voorheesによる「Query Expansion Using Lexical-Semantic Relations」、及び同予稿集の、M. W. Berry他による「Computational Methodsfor Intelligent Information Access」を参照されたい。実験の結果、自動化されたクエリー拡張では、平均で7%から25%の検索の効率化がはかられている。これについては、同予稿集の、C. Buckley他による「Automatic Query Expansion UsingSMART」を参照されたい。

クエリーの改良は、構文的に関連するワードを含めることによっても達成される。このアプローチは、ワードを、文書内での共起情報に基づいてクラスタ化し、これらのクラスタを用いてクエリーを拡張する。この共起情報は、2項関係であるため、こうしたインデックスのサイズは常に、極めて大きなものになる。また、あるグループは、ワードの変形に関する共起統計の集大成を用いてステマ(stemmer)を変更又は生成し、形態素規則のみを用いたアプローチに較べてどれだけ有利かを実証した。これについては、1994年、the Fourth Annual Symposiumの予稿集の、W. B. Croft他の「Corpus-Specific stemming Using Word Form Co-occurrence」を参照されたい。クエリーの用語を1組の意味的に関連する用語に拡張する上記各技法は、全体(global)分析と呼ばれる。クエリー拡張では、関連フィードバックからの用語もクエリーに追加され、検索の効率を改善する。1990年6月、Journal of the American Society for Information Scienceの41(4):288-297、G. Salton他の「Improving retrieval performance by relevance feedback」を参照のこと。これは、局所(local)分析と呼ばれる。これまでの研究では、ワードの前後関係及び語句の構造を用いた全体分析技法を文書の一部分の組に適用することによって、単純な局部的フィードバックより効果的でより確実な検索結果が得られることを示している。詳細については、上記文献の、J. Xu他による「Query Expansion Using Local and Global Document Analysis」を参照のこと。

しかし、前述したように、いままでの研究は、クエリーが拡張された場合のクエリーの効率的な処理の問題を解決したり、クエリー拡張とクエリー処理を実行するのに用いられるインデックスのサイズを小さくすることを目指すものではなかった。

概要

サイズの小さいインデックスを用いてクエリーを効果的に拡張し、連続的にクエリーを処理するための方法、及び装置を提供する。

クエリーは、元のクエリーでユーザにより指定されたワードに意味的に類似するワード、及び構文的に関連するワードを用いて、概念的に拡張される。本発明は、効果的なクエリーの拡張を支援するために、複数の細分度を有する情報と、処理構造の概念を用い、インデックス付け、クエリー処理、及びランク付けの各処理を含む。

目的

本発明の目的は、ワード・ミスマッチの問題と、結果的に生じるクエリー処理の非効率さを解決するために、小さなサイズのインデックスを使用して効率的なクエリー拡張を行い、連続的なクエリーの処理を行う方法及び装置を提供することである。より詳しくは、クエリー内に指定されたワードと意味的に類似し、構文的に関連のあるワードを用いて、そのクエリーを、物理的ではなく概念的に拡張し、結果的に関連する文書を逃すことを少なくする。

また、クエリーの拡張を支援するために、用語の意味について関連するワード、及び構文的共起関係にあるワードのインデックスが維持される必要があり、こうしたクエリー拡張の支援に関しては、以下の2つの問題が重要になる。1つ目はインデックス・テーブルのサイズの問題であり、2つ目はクエリー処理のオーバーヘッドの問題である。本発明は、これらの問題を解決することも目的とする。

効果

実績

技術文献被引用数
6件
牽制数
6件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

文書予備インデックス、文書内に含まれるワード、及び前記インデックスと前記ワードとの間の関係を含み、前記インデックス内のワードが元の細分度である、文書のデータベース検索する方法であって、前記方法が、a)小さなサイズの、より粗い細分度のインデックスを生成するために、前記予備的インデックスの中のワードを、対応する、より上位の概念に置き換えるステップと、b)元の細分度を有するクエリーのワードを、対応する、より上位の概念に置き換えることによって、文書のデータベースに適用される前記クエリーを論理的に拡張するステップと、c)より粗い細分度の前記インデックスを用いて、前記論理的に拡張されたクエリーを実行し、対応する、より上位の概念に関連する文書を検索するステップとを有することを特徴とする検索方法

請求項2

請求項1において、d)関連性の順序に基づいて、検索された文書をランク付けするステップを、更に含むことを特徴とする検索方法。

請求項3

請求項2において、前記ランク付けステップで、検索された文書が、元の細分度を有するクエリーのワードを用いてランク付けされることを特徴とする検索方法。

請求項4

請求項3において、関連性の順序は、クエリーのワードと検索された文書に含まれるワードが、厳密にマッチする場合を始めとし、以降、意味的にマッチする場合、構文的にマッチする場合、マッチしない場合の順であることを特徴とする検索方法。

請求項5

請求項1において、前記置き換えステップで、より上位の概念が、より上位の意味的概念であることを特徴とする検索方法。

請求項6

請求項5において、より上位の意味的概念のそれぞれが、類義語を含むことを特徴とする検索方法。

請求項7

請求項1において、前記置き換えステップで、所定の基準を満たす予備的インデックス内のワードの一部だけが、より上位概念の対応するワードに置き換えられることを特徴とする検索方法。

請求項8

請求項7において、前記所定の基準は、前記ワードが用語辞書にあるかどうかに基づくことを特徴とする検索方法。

請求項9

請求項1において、前記置き換えステップで、より上位の前記概念が、より上位の構文的概念であることを特徴とする検索方法。

請求項10

請求項9において、より上位の前記構文的概念のそれぞれが、あるレベル頻度を越えて、文書内で共に発生するワードを含むことを特徴とする検索方法。

請求項11

請求項1において、論理的にクエリーを拡張する前記ステップが更に、b)(i)所定の基準を満たす、クエリーのワードのみを、より上位の意味的概念を有する、より上位の対応する概念に置き換えるステップを有することを特徴とする検索方法。

請求項12

請求項11において、論理的にクエリーを拡張する前記ステップが更に、b)(ii)対応する、より上位の前記概念のそれぞれに対して、構文的に関連するワードを付加することによって、前記クエリーを更に論理的に拡張するステップと、b)(iii)前記所定の基準を満たしていない、クエリー内のワードのそれぞれに対して、構文的に関連するワードを付加することによって、前記クエリーを更に論理的に拡張するステップとを有することを特徴とする検索方法。

請求項13

請求項12において、論理的にクエリーを拡張する前記ステップが更に、a)(iv)所定の基準を満たす、構文的に関連する前記ワードを、関連する、より上位の概念に置き換えるステップと、a)(v)構文的に関連する前記ワード及び、より上位の前記概念のうち冗長となる部分を拡張後のクエリーから除去するステップとを有することを特徴とする検索方法。

請求項14

請求項13において、前記所定の基準は、前記ワードが用語辞書にあるかどうかに基づくことを特徴とする検索方法。

請求項15

請求項1において、前記置き換えステップで、前記予備的インデックス内の、複数の意味を持つワードが、対応する、より上位の複数の概念によって置き換えられることを特徴とする検索方法。

請求項16

請求項12において、前記所定の基準を満たさないワードが固有名詞であることを特徴とする検索方法。

請求項17

請求項1において、対応する、より上位の概念に関連する文書が、所定の数だけ検索されるまで、前記実行ステップが、連続する段階において続けられることを特徴とする検索方法。

請求項18

請求項17において、前記各段階が、1つの拡張クラスを表すことを特徴とする検索方法。

請求項19

請求項17において、前記各段階が、1つの拡張クラス内の1スロットを表すことを特徴とする検索方法。

請求項20

請求項17において、各段階で、文書が、少なくともクエリー内の1つのワードに割り当てられた重要度のレベルを反映した順序で検索されることを特徴とする検索方法。

請求項21

サイズの小さい文書のインデックス、文書の含まれる元の細分度のワードに対応する、より上位の概念、及び前記インデックスと前記概念との間の関係を含む文書のデータベースを検索する方法であって、前記方法が、a)元の細分度のクエリーのワードを、対応する、より上位の概念に置き換えることによって、文書のデータベースに適用されるクエリーを論理的に拡張するステップと、b)論理的に拡張された前記クエリーを実行し、前記インデックスを用いて、対応する、より上位の概念に関連する文書を検索するステップとを有することを特徴とする検索方法。

請求項22

請求項21において、論理的にクエリーを拡張する前記ステップが更に、a)(i)所定の基準を満たす、クエリーのワードのみを、より上位の意味的概念を有する、より上位の対応する概念に置き換えるステップを有することを特徴とする検索方法。

請求項23

請求項22において、より上位の意味的概念のそれぞれが、類義語を含むことを特徴とする検索方法。

請求項24

請求項21において、より上位の前記概念が、より上位の構文的概念であることを特徴とする検索方法。

請求項25

請求項24において、より上位の前記構文的概念のそれぞれが、あるレベルの頻度を越えて、文書内で共に発生するワードを含むことを特徴とする検索方法。

請求項26

請求項22において、論理的にクエリーを拡張する前記ステップが更に、a)(ii)対応する、より上位の前記概念のそれぞれに対して、構文的に関連するワードを付加することによって、前記クエリーを更に論理的に拡張するステップと、a)(iii)前記所定の基準を満たしていない、クエリー内のワードのそれぞれに対して、構文的に関連するワードを付加することによって、前記クエリーを更に論理的に拡張するステップとを有することを特徴とする検索方法。

請求項27

請求項26において、論理的にクエリーを拡張する前記ステップが更に、a)(iv)所定の基準を満たす、構文的に関連する前記ワードを、関連する、より上位の概念に置き換えるステップと、a)(v)構文的に関連する前記ワード及び、より上位の前記概念のうち冗長となる部分を拡張後のクエリーから除去するステップとを有することを特徴とする検索方法。

請求項28

請求項27において、前記所定の基準は、前記ワードが用語辞書にあるかどうかに基づくことを特徴とする検索方法。

請求項29

請求項26において、前記所定の基準を満たさないワードが固有名詞であることを特徴とする検索方法。

請求項30

請求項26において、前記構文的概念のそれぞれが、あるレベルの頻度を越えて、文書内で共に発生するワードを含むことを特徴とする検索方法。

請求項31

請求項21において、c)関連性の順序に基づいて、検索された文書をランク付けするステップを、更に含むことを特徴とする検索方法。

請求項32

請求項31において、前記検索された文書が、元の細分度を有するクエリーのワードを用いてランク付けされることを特徴とする検索方法。

請求項33

請求項32において、関連性の順序は、クエリーのワードと検索された文書に含まれるワードが、厳密にマッチする場合を始めとし、以降、意味的にマッチする場合、構文的にマッチする場合、マッチしない場合の順であることを特徴とする検索方法。

請求項34

請求項21において、文書に含まれる元の細分度のワードが、複数の、より上位の概念に対応することを特徴とする検索方法。

請求項35

請求項21において、対応する、より上位の概念に関連する文書が、所定の数だけ検索されるまで、前記実行ステップが、連続する段階において続けられることを特徴とする検索方法。

請求項36

請求項35において、前記各段階は、1つの拡張クラスを表すことを特徴とする検索方法。

請求項37

請求項35において、前記各段階は、1つの拡張クラス内の1スロットを表すことを特徴とする検索方法。

請求項38

請求項35において、各段階で、文書が、少なくともクエリー内の1つのワードに割り当てられた重要度のレベルを反映した順序で検索されることを特徴とする検索方法。

請求項39

文書の予備的インデックス、文書内に含まれるワード、及び前記インデックスと前記ワードとの間の関係を含み、前記インデックス内のワードが元の細分度である、文書のデータベースを検索するシステムであって、前記システムが、a)より粗い細分度の小さなサイズのインデックスを生成するために、前記予備的インデックスの中のワードを、対応する、より上位の概念に置き換えるインデクサと、b)前記文書のデータベースに適用されるクエリーを提供するためのユーザ・インタフェースと、c)元の細分度を有する、クエリーのワードを、対応する、より上位の概念に置き換えることによって、前記クエリーを論理的に拡張し、論理的に拡張された前記クエリーを、より粗い細分度のインデックスを使用して実行し、対応する、より上位の概念に関連する文書を検索するプロセッサとを有することを特徴とする検索システム

請求項40

請求項39において、前記プロセッサが、関連性の順に、検索された文書をランク付けすることを特徴とする検索システム。

請求項41

請求項40において、前記プロセッサが、元の細分度を有する、クエリーのワードを使用して、検索された文書をランク付けすることを特徴とする検索システム。

請求項42

請求項41において、関連性の順序は、クエリーのワードと検索された文書に含まれるワードが、厳密にマッチする場合を始めとし、以降、意味的にマッチする場合、構文的にマッチする場合、マッチしない場合の順であることを特徴とする検索システム。

請求項43

請求項39において、より上位の前記概念は、より上位の意味的概念であることを特徴とする検索システム。

請求項44

請求項43において、より上位の前記意味的概念のそれぞれが、類義語を含むことを特徴とする検索システム。

請求項45

請求項39において、前記インデクサが、所定の基準を満たす予備的インデックス内のワードのみを、対応する、より上位の概念で置き換えることを特徴とする検索システム。

請求項46

請求項45において、前記所定の基準は、前記ワードが用語辞書にあるかどうかに基づいていることを特徴とする検索システム。

請求項47

請求項39において、より上位の前記概念が、より上位の構文的概念であることを特徴とする検索システム。

請求項48

請求項47において、より上位の前記構文的概念のそれぞれが、あるレベルの頻度を越えて文書内に共に発生するワードを含むことを特徴とする検索システム。

請求項49

請求項39において、前記プロセッサが更に、c)(i)所定の基準を満たす、クエリーのワードのみを、より上位の意味的概念である、対応する、より上位の概念に置き換えることによって、論理的にクエリーを拡張することを特徴とする検索システム。

請求項50

請求項49において、前記プロセッサが更に、c)(ii)対応する、より上位の前記概念のそれぞれに対して、構文的に関連するワードを付加し、c)(iii)前記所定の基準を満たしていない、クエリー内のワードのそれぞれに対して、構文的に関連するワードを付加することによって、前記クエリーを論理的に拡張することを特徴とする検索システム。

請求項51

請求項50において、前記プロセッサが更に、c)(iv)所定の基準を満たす、構文的に関連する前記ワードを、関連する、より上位の概念に置き換え、c)(v)構文的に関連する前記ワード及び、より上位の前記概念のうち冗長となる部分を拡張後のクエリーから除去することによって、前記クエリーを論理的に拡張することを特徴とする検索システム。

請求項52

請求項51において、前記所定の基準は、前記ワードが用語辞書にあるかどうかに基づいていることを特徴とする検索システム。

請求項53

請求項39において、複数の意味を有する、前記予備的インデックス内のワードが、対応する、より上位の複数の概念に置き換えられることを特徴とする検索システム。

請求項54

請求項50において、前記所定の基準を満たさないワードが固有名詞であることを特徴とする検索システム。

請求項55

請求項39において、対応する、より上位の概念に関連する文書が、所定の数だけ検索されるまで、前記クエリーの実行が、連続する段階において続けられることを特徴とする検索システム。

請求項56

請求項55において、前記各段階が、1つの拡張クラスを表していることを特徴とする検索システム。

請求項57

請求項55において、前記各段階は、1つの拡張クラス内の1スロットを表すことを特徴とする検索システム。

請求項58

請求項55において、各段階で、文書が、少なくともクエリー内の1つのワードに割り当てられた重要度のレベルを反映した順序で検索されることを特徴とする検索システム。

請求項59

サイズの小さい文書のインデックス、文書の含まれる元の細分度のワードに対応する、より上位の概念、及び前記インデックスと前記概念との間の関係を含む文書のデータベースを検索するシステムであって、前記システムが、a)前記文書のデータベースに適用されるクエリーを提供するためのユーザ・インタフェースと、b)元の細分度を有する、クエリーのワードを、対応する、より上位の概念に置き換えることによって、前記クエリーを論理的に拡張し、論理的に拡張された前記クエリーを、前記インデックスを使用して実行し、対応する、より上位の概念に関連する文書を検索するプロセッサとを有することを特徴とする検索システム。

請求項60

請求項59において、前記プロセッサが更に、b)(i)所定の基準を満たす、クエリーのワードのみを、より上位の意味的概念を有する、より上位の対応する概念に置き換えることによって、前記クエリーを論理的に拡張することを特徴とする検索システム。

請求項61

請求項60において、より上位の意味的概念のそれぞれが、類義語を含むことを特徴とする検索システム。

請求項62

請求項59において、より上位の前記概念が、より上位の構文的概念であることを特徴とする検索システム。

請求項63

請求項62において、より上位の前記構文的概念のそれぞれが、あるレベルの頻度を越えて、文書内で共に発生するワードを含むことを特徴とする検索システム。

請求項64

請求項60において、前記プロセッサが更に、b)(ii)対応する、より上位の前記概念のそれぞれに対して、構文的に関連するワードを付加し、b)(iii)前記所定の基準を満たしていない、クエリー内のワードのそれぞれに対して、構文的に関連するワードを付加することによって、前記クエリーを論理的に拡張することを特徴とする検索システム。

請求項65

請求項64において、前記プロセッサが更に、b)(iv)所定の基準を満たす、構文的に関連する前記ワードを、関連する、より上位の概念に置き換え、b)(v)構文的に関連する前記ワード及び、より上位の前記概念のうち冗長となる部分を拡張後のクエリーから除去することによって、前記クエリーを論理的に拡張することを特徴とする検索システム。

請求項66

請求項65において、前記所定の基準が、前記ワードが用語辞書にあるかどうかに基づくことを特徴とする検索システム。

請求項67

請求項64において、前記所定の基準を満たさないワードが固有名詞であることを特徴とする検索システム。

請求項68

請求項64において、前記構文的概念のそれぞれが、あるレベルの頻度を越えて、文書内で共に発生するワードを含むことを特徴とする検索システム。

請求項69

請求項59において、前記プロセッサが更に、関連性の順序に基づいて、検索された文書をランク付けすることを特徴とする検索システム。

請求項70

請求項69において、前記検索された文書が、元の細分度を有するクエリーのワードを用いてランク付けされることを特徴とする検索システム。

請求項71

請求項70において、関連性の順序は、クエリーのワードと検索された文書に含まれるワードが、厳密にマッチする場合を始めとし、以降、意味的にマッチする場合、構文的にマッチする場合、マッチしない場合の順であることを特徴とする検索システム。

請求項72

請求項59において、文書に含まれる元の細分度のワードが、複数の、より上位の概念に対応することを特徴とする検索システム。

請求項73

請求項59において、対応する、より上位の概念に関連する文書が、所定の数だけ検索されるまで、前記クエリーの実行が、連続する段階において続けられることを特徴とする検索システム。

請求項74

請求項73において、前記各段階は、1つの拡張クラスを表すことを特徴とする検索システム。

請求項75

請求項73において、前記各段階は、1つの拡張クラス内の1スロットを表すことを特徴とする検索システム。

請求項76

請求項73において、各段階で、文書が、少なくともクエリー内の1つのワードに割り当てられた重要度のレベルを反映した順序で検索されることを特徴とする検索システム。

技術分野

0001

本発明は、一般的に、データベース内の文書収集するのに適用されるインデックスクエリーの分野に関する。より詳しくは、クエリーの効果的な拡張と処理、クエリーの拡張を実施するのに使用されるインデックスのサイズの縮小、及び連続的なクエリーの処理に関する。

背景技術

0002

クエリーを適用することによって文書を検索する従来の検索システムは、文書を分類する共通の原理方法論に基づいている。文書は通常、熟練者又は司書により、事前に指定され、調整された用語を用いて、手作業インデックス付けされる。文書はまた、その文書に含まれる語(ワード)に基づいてインデックス付けされることもある。ユーザは、指定可能な用語から選択したワードと、それらの間を適当なブーリアン演算子で連結して文書の検索を行う。このようなタイプのシステムでは、厳密なマッチング戦略が用いられる。このアプローチは、単純で高精度といった多くの利点を有するものの、ワード・ミスマッチの問題が生じる。

0003

情報検索におけるワード・ミスマッチの問題は、作者がその文書で、ある概念を表すのに、あるワードを使用している場合に、ユーザが、それと同じ概念をクエリーにおいて指定する際、別のワードを使用してしまうことによって生じる。図1は、「car(乗用車)」及び「dealer(販売店)」に関連付けられた、ハイパーテキストマークアップ言語HTML)の文書において使用されるワードが、様々な文書の間で異なることがあることを示している。拡張可能なマークアップ言語(XML)や標準一般化マークアップ言語(SGML)のような、HTML以外の言語も用いられる。ユーザが、「automobile(自動車)」と「dealer(販売店)」というワードをクエリーに用いる場合、ワード・ミスマッチの問題で、対象となる文書を1つも検索できない結果になる。

0004

尚、本明細書では、検索の対象が、主に英語を含むものと仮定しているため、検索に使用するクエリーの各要素は、英語で記述されている。しかし、これらは、ユーザの要求に応じて、どの国の言語で表現することも可能である。ここでは、前記英語で記述された要素に続いて(必要に応じ)括弧内に、その要素の日本語における意味を表すことにする。従って、当該括弧内の日本語は、単にクエリーの要素の意味を説明するためのものに過ぎず、クエリーの結果には影響を及ぼさない。

0005

クエリーの拡張は、このような問題を解決する技法として示唆されている。このアプローチは、意味の類似したワード(例えば、類義語や他の関連する意味を有するワード)及び構文的に関連するワード(例えば、一定の頻度以上で同じ文書内に同時に現れるワード群は、構文的共起ワードである)をクエリー内のワードとして用いることによってクエリーを拡張するものである。こうしてクエリーが拡張されると、関連する文書内のワードにマッチする可能性が高まる。クエリーの拡張が使用されると、「car dealer(乗用車の販売店)」というワードを含むクエリーは、以下のように同様の意味の用語を含むように拡張される。

0006

行1. [(「car(乗用車)」OR「automobile(自動車)」OR「auto(車)」OR「sedan(セダン)」)OR
行2. (「Ford(フォード車)」OR「Buick(ビュイック車)」)]AND
行3. (「dealer(販売店)」OR「Showroom(ショールーム)」OR「SalesOffice(販売所)」)。

0007

上記例に含まれるクエリーの拡張には、2つのタイプがある。行1と行3のクエリーの拡張は、用語の意味において「car」と「dealer」に関連する追加ワードを追加するものである。即ち、意味的に類似するワードを追加するものである。「automobile」、「auto」、及び「sedan」は、「car」というワードに類似する意味を有するワードである。同様に、「Showroom」と「SalesOffice」は、「dealer」というワードに類似する意味を有するワードである。他のタイプのクエリーの拡張は、行2に示すものであり、これは例えば、構文的共起関係によるものである。ワールドワイドウエブ(単にウエブとも言う)で用いられる多くのワードは、実際には固有名詞であり、用語辞書には見つからない。例えば、固有名詞は、Ford、Buick、NBA、及びNFL(National Football League)といったものである。前述したように、構文的共起関係は、2つのワードが、同じ文書に同時に現れる頻度を分析することによって導出される。これは、2つのワードが頻繁に同じ文書内に現れる場合には、それらのワードが関連している可能性が高いという仮定に基づくものである。例えば、「Ford」と共に発生するワードとして、「dealer(販売店)」、「body shop(車体工場」、「Mustang(マスタング:フォード社製の車の名前)」、「Escort(エスコート:フォード社製の車の名前)」等が考えられる。

0008

クエリーの拡張を支援するために、用語の意味によって関連付けられたワードのインデックスと、共起情報のような構文的関係が適切に維持されなければならない。用語の意味によってワードに関連付けられたインデックスは、階層構造意味ネットワーク、又は関連ワード階層クラスタとして構成される。前記階層構造については、1997年8月、ギリシャのアテネで行われた、the 23rd International Conference on Very Large Data Basesの予稿集ページ538-547、W. Li他の「Facilitating Multimedia Database Exploration through Visual Interfaces and Perpetual Query Reformulations」を参照されたい。また、前記意味ネットワークについては、1990年、International Journal of Lexicography 3(4)、ページ245-264における、G. A. Millerの「Nouns in WordNet: A Lexical Inheritance System」を参照のこと。また、関連ワードの階層クラスタについては、1983年、ニューヨーク、McGraw-Hill、ページ118-155の、G. Salton他による「TheSMARTand SIRE Experimental Retrieval Systems」を参照のこと。構文的共起関係のような構文的関係は、2項関係で表されるので、構文的関係のインデックスのサイズは非常に大きい。この問題を解決するため、いくつかの技法が提案されている。これらの技法については、1992年、デンマークにおけるthe Fifteenth annual InternationalACMSIGIR Conferenceの予稿集の、G. Grefenstetteによる「Use of syntactic context to produce term association lists for text retrieval」、1996年、スイスチューリッヒにおけるthe 19th Annual International ACM SIGIR Conferenceの予稿集の、J. Xu他による「Query Expantion Using Local and Global Document Analysis」、1997年、アメリカ合衆国ペンシルニアフィラデルフィアにおける、the20th Annual International ACM SIGIR Conferenceの予稿集の、C. Jacqueminによる「Guessing Morphology from Terms and Corpora」を参照のこと。こうした技法は、発生頻度の分析、及び形態素規則(例えば、全てのワードをその起源となる形態に変換する)や用語辞書の使用を含むものである。

0009

ワード・ミスマッチの問題に関しては、情報検索(IR)の分野において、かなりの研究がされてきている。これについては、1983年、McGraw-Hill BookCompany発行の、G. Salton他による「Introduction to Modern Information Retrieval」、1989年、Addison-Wesley Publishing Company, Inc発行の、G.Saltonによる「Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer」、及び1997年、アメリカ合衆国カリフォルニアサンフランシスコ、Morgan Kaufmannの、K. Sparck Jones他による「Readings in Information Retrieval」を参照のこと。

0010

しかし、この研究の殆どが、適合率再現率といった、検索の基準に関する点を指向したものである。クエリーの拡張を効果的に支援する方法(1993年、メリーランド州Gaithersburgで行われたthe 3rd Text Retrieval Conferenceの予稿集の、C. Buckley他による「Automatic Query Expansion UsingSMART」参照)やインデックス付けのメカニズムを示唆した研究がいくつか有るが、満足する解決法のない問題が依然として2つ残っている。第1の問題は、ある文書の集合(例えば、ウエブ)内の多くのワードが別個の固有名詞であり、各ワードが意味的に同じワード及び構文的に関連したワードを多く有するので、インデックスのサイズが極めて大きくなってしまうことである。第2の問題は、クエリーが追加ワードによって拡張されるので、クエリーの処理コストが高くなってしまうことである。

0011

ウエブから収集された文書情報を取り扱う際には、文書の数が非常に多くなり、使用されているワードが極めて多様で、一貫性がなく、時には間違っている(例えば、タイプエラー)ため、これらの問題は、ますます顕著になる。ある研究では、ウエブに関する殆どのユーザ・クエリーは、通常、ワードを2つ有している。これについては、1995年、Digital Libraries(DL '95)の予稿集で、B.Croft他の「Providing Government Information on the Internet: Experienceswith THOMAS」を参照されたい。しかし、クエリー拡張を用いれば、クエリーの長さは実質的に長くなる。結果的に、ウエブ上の既存のサーチエンジンのほとんどは、クエリー拡張機能を提供できないことになる。

0012

ここで、クエリー拡張の分野における既存の研究を概説する。クエリー拡張は、IRの分野において、かなりの注目を集めた。しかし、いままで注目されてきた部分は、クエリーの拡張によって、改善される検索の基準(即ち、適合率及び再現率)の程度を評価することであった。別の研究では、与えられたクエリーのワードに関して、1組の類似する用語を識別するために、辞書構築することに焦点があてられてきた。しかし、今までの研究は、クエリーが拡張された場合のクエリーの効率的な処理の問題や、クエリーの拡張及び処理を行うのに用いられるインデックスのサイズを小さくするといった点に取り組んでいない。更に、厳密なマッチング及び類似的なマッチングに基づいて文書をランク付けする問題は、困難なものとして残されたままである。

0013

SMARTは、よく知られた先進情報検索システムの1つである。これに関しては、1971年、アメリカ合衆国ニュージャージー州Englewood CliffsのPrentice-Hallから発行されたGerard Salton編集のThe SMART Retrieval System -Experiments in Automatic Document Processing、第12章の、R. T. Dattolaによる「Experiments with a fast algorithm for automatic classification」、及び上記文献の、G. Salton他による「The SMART and SIRE Experimental Retrieval Systems」を参照のこと。SMARTでは、各文書が用語のベクトルで表される。ベクトルのそれぞれの位置は、文書内の対応する用語の重み(重要性)を表している。N個の異なる用語を有するM個の文書の集合は、M×Nの行列で表される。クエリーもまた用語のベクトルとして表される。文書の検索は、クエリー・ベクトルと各文書のベクトルとの余弦に対応する類似性の計算に基づく。他の、よく知られたシステムには、INQUERYがある。これについては、1995年、Information Processing and Managementの3:327-332で、J. Callan他による「Trec and tipster experiments with inquery」を参照のこと。

0014

潜在的意味インデックス(LSI)は、辞書的なマッチングによる個別の用語検索の替わりに、統計的に導出された概念インデックスに依存する技法である。これについては、1990年、Journal of the America Society of Information Science、41:391-407の、R. Harshman他による「Indexing by latent semantic analysis」、及び1995年、the 1995ACMConference on Supercomputingの予稿集で、M. W. Berry他による「Computational Method for Intelligent Information Access」を参照されたい。LSIは、ワードの使用法に、いくつかの見えない構造、即ち潜在的な構造があることを仮定し、その構造は、文書におけるワードの発生を分析することによって外部化される必要がある。従って文書は、非常に大きな範囲の用語空間におけるベクトルとして考えられ、そのベクトルの個々の要素は与えられた文書における特定の用語の発生頻度を表している。全体及び局所的重み付けに基づく、より洗練された基準も使用されうる。短縮された特異値分解SVD)が、文書に亘るワード使用の構造を評価する。これについては、1989年、アメリカ合衆国メリーランド州ボルチモアのJohns-Hopkinsの、G. Golub他による「Matrix Computations」第2版を参照されたい。ここでは、検索が、特異値を有するデータベース、及び短縮されたSVDから得られたベクトルを使用して実行される。LSIの予備的評価では、この情報検索のアプローチは、個々の用語に基づくものより粗い基準とされている。

0015

自動化されたクエリー拡張は、ワード・ミスマッチ問題を取り扱う技法として長い間示唆されてきた。これについては、1994年、アイルランド共和国ダブリンで行われたthe 17th Annual InternationalACMSIGIR Conferenceの予稿集で、E. Voorheesによる「Query Expansion Using Lexical-Semantic Relations」を参照されたい。あるアプローチでは、類語辞典を用いてクエリーを拡張し、関連する文書内でワードがマッチする可能性を高めている。研究では、単に一般的な類語辞典を用いるだけでは、改善に限界があることが分かっている。多くの革新的技法も提案されている。1994年、the 3rd International Conferenceon Information and Knowledge Managementの予稿集の、O. Kwon他による「Query Expansion Using Domain Adapted, Weighted Thesaurus in an Extended Boolean Model」、1993年、アメリカ合衆国ペンシルバニア州ピッツバーグで行われたthe 16th Annual International ACM SIGIR Conferenceの予稿集の、E. Voorheesによる「Concept Based Query Expansion」、同予稿集の、E. Voorheesによる「Query Expansion Using Lexical-Semantic Relations」、及び同予稿集の、M. W. Berry他による「Computational Methodsfor Intelligent Information Access」を参照されたい。実験の結果、自動化されたクエリー拡張では、平均で7%から25%の検索の効率化がはかられている。これについては、同予稿集の、C. Buckley他による「Automatic Query Expansion UsingSMART」を参照されたい。

0016

クエリーの改良は、構文的に関連するワードを含めることによっても達成される。このアプローチは、ワードを、文書内での共起情報に基づいてクラスタ化し、これらのクラスタを用いてクエリーを拡張する。この共起情報は、2項関係であるため、こうしたインデックスのサイズは常に、極めて大きなものになる。また、あるグループは、ワードの変形に関する共起統計の集大成を用いてステマ(stemmer)を変更又は生成し、形態素規則のみを用いたアプローチに較べてどれだけ有利かを実証した。これについては、1994年、the Fourth Annual Symposiumの予稿集の、W. B. Croft他の「Corpus-Specific stemming Using Word Form Co-occurrence」を参照されたい。クエリーの用語を1組の意味的に関連する用語に拡張する上記各技法は、全体(global)分析と呼ばれる。クエリー拡張では、関連フィードバックからの用語もクエリーに追加され、検索の効率を改善する。1990年6月、Journal of the American Society for Information Scienceの41(4):288-297、G. Salton他の「Improving retrieval performance by relevance feedback」を参照のこと。これは、局所(local)分析と呼ばれる。これまでの研究では、ワードの前後関係及び語句の構造を用いた全体分析技法を文書の一部分の組に適用することによって、単純な局部的フィードバックより効果的でより確実な検索結果が得られることを示している。詳細については、上記文献の、J. Xu他による「Query Expansion Using Local and Global Document Analysis」を参照のこと。

0017

しかし、前述したように、いままでの研究は、クエリーが拡張された場合のクエリーの効率的な処理の問題を解決したり、クエリー拡張とクエリー処理を実行するのに用いられるインデックスのサイズを小さくすることを目指すものではなかった。

発明が解決しようとする課題

0018

本発明の目的は、ワード・ミスマッチの問題と、結果的に生じるクエリー処理の非効率さを解決するために、小さなサイズのインデックスを使用して効率的なクエリー拡張を行い、連続的なクエリーの処理を行う方法及び装置を提供することである。より詳しくは、クエリー内に指定されたワードと意味的に類似し、構文的に関連のあるワードを用いて、そのクエリーを、物理的ではなく概念的に拡張し、結果的に関連する文書を逃すことを少なくする。

0019

また、クエリーの拡張を支援するために、用語の意味について関連するワード、及び構文的共起関係にあるワードのインデックスが維持される必要があり、こうしたクエリー拡張の支援に関しては、以下の2つの問題が重要になる。1つ目はインデックス・テーブルのサイズの問題であり、2つ目はクエリー処理のオーバーヘッドの問題である。本発明は、これらの問題を解決することも目的とする。

課題を解決するための手段

0020

本発明によれば、複数の細分度からなる情報の概念と処理構造が、クエリーの拡張を支援するために使用される。本発明は、インデックス付けフェーズ、クエリー処理フェーズ、及びランク付けフェーズを含む。インデックス付けフェーズでは、意味的に類似したワードが1つの概念としてグループ化され、こうして、より粗く細分化された意味概念のために、結果的に実際の1つのインデックス・サイズが小さくなる。クエリー処理の間、クエリー内のワードが、辞書と実際のデータの内容を使用して、対応する意味概念及び構文的拡張にマッピングされ、結果的に元のクエリーに対して論理的な拡張が行われる。更に、処理に関するオーバーヘッドが回避される。次に、最初のクエリーのワードは、検索結果として得られた文書を、厳密なマッチング、意味的なマッチング、及び構文的マッチングに基づいてランク付けするのに用いられ、連続的なクエリーの処理を実行するのにも用いられる。

発明を実施するための最良の形態

0021

本発明による、効率的にクエリーの拡張を行うための方法及び装置の好適実施形態が、添付図面と共に以下で詳細に説明される。以下の説明は、NECのPERICOオブジェクト指向データベース管理システム(OODBMS)に関してなされるが、本発明はこれに限られるものではないことに注意すべきである。本発明は、様々なデータベース・システム及び文書の集合体に適用されうる。

0022

本発明は、複数の細分度の概念を導入することによって、クエリーの拡張に関して、効果的なインデックス付けと処理支援を提供する。本発明のアプローチは、ワードのステミング(stemming)の後で、利用可能な技法を用いて、意味的に類似するワードと構文的に関連するワードについて、インデックスを設定する。前記技法については、1996年、スイス、チューリッヒでのthe 19th AnnualInternationalACMSIGIR Conferenceの予稿集の、J. Xu他の「Query ExpansionUsing Local and Global Document Analysis」、及び1997年、アメリカ合衆国ペンシルバニア州フィラデルフィアでのthe 20th Annual International ACM SIGIR Conferenceの予稿集の、C. Jacqueminの「Guessing Morphology from Terms and Corpora」を参照のこと。更に本発明のアプローチは、いくつかのエントリタプル)を、より高レベルの細分度で1つのエントリにマージすることにより、インデックスのサイズを小さくする。クエリー処理の間、より高いレベルの細分度での情報を有した、そのタプルが、関連文書を検索するのに用いられる。その後、クエリーの元のワードは、より細かい細分度で、厳密なマッチング、意味的に類似するマッチング、及び構文的に関連するマッチングに基づいてクエリー処理の間に結果として得られる文書をランク付けするために用いられる。複数の細分度を有するインデックスとクエリー処理技法を使用することによって、検索メカニズムにおける全体の精度を維持したまま、インデックスのサイズを小さくすることができ、かつ、より速いクエリー処理を実現できる。

0023

最初に、複数の細分度の表記と、それが、どのように、ほとんどのIRシステムによって使用されている従来のインデックス付けに関連して適応されるのかについて説明する。次に、所定の文書の集合に関して、複数の細分度を有するインデックス付けを行う場合の、記憶域に対するオーバーヘッドについての見積りを行う。

0024

従来のIRシステムは、文書リストから所与のワードを容易に検索するために、インデックスを保持し、同時に、得られた文書に関連付けられたワードの組を抽出する。この場合、「文書」という用語は、テキストイメージ、又はテキストとイメージの組み合わせに関連することに注意すべきである。

0025

図2は、インデックスの例を示している。図2の(b)に示すテーブルは、図2の(a)に示すテーブルを転置したインデックスである。図2では、説明を容易にするため、これらのインデックスがテーブルの形で示されている。しかし、実際の環境では、例えばNECのPERCIO OODBMSの上位層クラスが用いられる。1つのクエリーの例をとると、ユーザが最初に、ワード「car(乗用車)」かつ「dealer(販売店)」を用いてクエリーを作成すると、IRシステムは、図2の(b)のテーブルの対応する行から文書リストを取り出す。この場合、クエリーの解答は、2つの行から得られた文書リストの共通部分となる。このIRに対するアプローチは、明らかに、厳密なマッチングのみを支援するものであり、「automobile dealer(自動車の販売店)」、「car showroom(乗用車のショールーム)」、又は「automobile showroom(自動車のショールーム)」といった類似の意味を有する用語を含む関連文書を得ることができない。クエリー拡張は、クエリーを「car」かつ「dealer」という記述から、(「car」又は「automobile」)かつ(「dealer」又は「showroom」)という記述に拡張する特別のユーティリティと関連して使用される。このアプローチは実現可能ではあるが、クエリー処理にかなりのオーバーヘッドを招くことになる。特に、図2の(b)のインデックス・テーブルについての2回のルックアップの代わりに、元のクエリー内のワードと意味的に類似するワードのそれぞれについて、何回かのルックアップが必要になる。また、オンライン辞書のような類語辞書的ツールが、クエリーの用語を、それらと意味的に類似する用語に拡張するのに必要である。これらの観察から、本発明は、文書の集合を検索する際に、クエリーの拡張を支援する、より効果的な方法を提供する。

0026

先に述べたように、ユーザの語彙と作者の語彙とのミスマッチを避けるために、意味の類似するワード、及び構文的関係を有するワードを用いてクエリーを拡張する方法に基づいたクエリーの拡張が必要とされる。

0027

図3は、従来のIRシステムにおいて、クエリーの拡張を容易にするのに追加が必要となるデータ構造を示している。特に、図3は、各ワードが意味的に類似する概念にグループ化される、用語の意味を含むオンライン辞書から導出されたテーブルを示している。なお、図3に示されたテーブルは、説明のため簡略化されている。例えば、類似する用語の組「car(乗用車)」、「auto(車)」、「automobile(自動車)」、及び「sedan(セダン)」は、1つの象徴エンティティ、sem1として表されている。辞書や類語辞書に基づく意味的な類似とは違って、IRにおける構文的関係は、文書の収集そのものによって決定される。特に、ワードの共起情報は、2つのワードを構文的に関連付けるのに使用される。図3(b)は、この情報を表したインデックスを例示している。図3補助インデックスと共に、図2の従来のIRインデックスを用いることによって、基本的なクエリー拡張技法が、IRシステムにおいて支援される。基本的には、ユーザのクエリーが与えられると、クエリーのワード・リストが、意味的に類似するワード及び構文的に関連するワードを含むように拡張される。

0028

クエリーの拡張を用いたクエリーの処理には、上述の方法が使用されるが、このアプローチでは、処理に関するオーバーヘッドが高くなってしまう。本発明によれば、クエリーをより効率的に処理することができる追加のインデックス構造が使用される。本発明のアプローチの基本的発想は、図2及び図3のインデックスを、クエリーが概念的に拡張されるように変換するものである。即ち、意味的に類似するワード及び構文的に関連するワードをリスト内に含ませることによって、クエリーのワードのリストを物理的に拡張するのではなく、クエリーのワードを、その関連する、より上位レベルの意味概念と構文的関係(例えば、共起関係)のワードと入れ替えることによって、クエリーを概念的に拡張する。このことは、追加のインデックス構造による容量オーバーヘッドの追加をもたらす。しかし、ユーザのクエリーがより効率的に処理されるので、全体としては節約を達成できる。

0029

前述したように拡張されたクエリーを処理するために、図4に示すように、インデックス・テーブルが変更される。特に、図4の(a)に示すインデックス・テーブルは、各ワード(固有名称でない)を、より上位レベルの意味概念のワードに置き換えることによって、図2の(a)から導出される。図4の(b)に示すインデックス・テーブルは、図2の(b)に示されたワードを、それらが対応する、より上位レベルの意味概念のワードと組み合わせ、それぞれの文書リストのエントリをマージすることによって得られる。従って、「car」、「auto」、「automobile」、及び「sedan」に対応する行エントリは、図4の(b)では単一のエントリSem1として表されている。同様に、図2(b)の、「dealer」、「showroom」、及び「SalesOffice」に対応する行は、Sem2というラベルの1行に纏められている。

0030

構文的に関連するワードに対するインデックスは通常、いくつかの理由から、意味的に関連するワードに対するインデックスよりかなり大きい。ウエブ上の多くのワードは、固有の名称であり、辞書には見つからない。実験では、2,904の文書を分析した場合、キーワードの42%だけがWordNetで見つかった。WordNetは60,000以上のワードを有するオンライン辞書である。これについては、1990年、International Journal of Lexicography 3(4)、ページ245-264の、G. A. Millerによる「Nouns in WordNet: A Lexical Inheritance System」を参照されたい。残りの58%のワードは固有名詞やタイプエラーを含んでおり、これがインデックスのサイズを肥大化させる元となっている。従来のIRシステムにおいては、構文的な関連付けは、通常、共起関係によって把握されていた。同じ文書内でのワードの共起関係は、1対1関係であるため、n個のワードが識別された場合、インデックスのサイズは、最悪のケースでは、(n×(n−1))/2となる。巨大な記憶域とインデックス付けのオーバーヘッドのために、3個以上のワードの共起関係をインデックス付けするのは、非常にコストがかかる。

0031

辞書に見つかったワード(意味的に意義のあるもの)をSとし、他の全てのワード(固有名詞)をPとする。辞書にあるワードと辞書にないワードという、上記分類に基づいて、ワードの間の共起関係が3つの異なるカテゴリに分類される。

0032

・P−P型:例えば(Toyota(トヨタ)、Avalon(トヨタ車の名前))、(Acura(アキュラ)、Legend(アキュラ車の名前))、(Nissan(日産)、Maxima(日産車の名前))。

0033

・S−P型、又はP−S型:例えば(Buick(フォード車の名前)、car(乗用車))、Buick、dealer(販売店))、(car、Ford(フォード社))、(Ford、auto(車))、(Ford、dealer)。

0034

・S−S型:例えば(car、garage(ガレージ))、(auto、garage)。

0035

通常、図3の(b)に示す、より粗い細分度に変換できないP−P型のエントリを変換することは困難である。しかし、他の全てのエントリは、対応する、より高いレベルの意味概念に置換できるSワードを有する。これによって、共起インデックスのサイズが減少し、クエリー処理のスピードアップが実現される。インデックスのサイズの減少は、以下のように生じる。S−P型(wi、X)の各エントリに対し、wiが意味概念Semiに対応するように、図3の(b)に示された全ての(wi、X)のエントリを、図4の(c)の(Semi、X)に置換する。ここで、対応する文書のリストもマージされる。同様の手順がP−S型のエントリにも適用される。図4の(c)に示すように、エントリ(Ford、car)と(Ford、auto)は、(Ford、Sem1)に置換される。同様に、エントリ(Ford、dealer)と(Ford、showroom)は、(Ford、Sem2)に置換される。こうしたマージ・メカニズムについて、図5の(a)(b)を用いて説明する。

0036

S−S型のエントリは、以下の2つの方法でマージされる。

0037

・単一マージ:図5の(a)(b)に示すような、1対多/多対1のタイプのマージ。例えば、エントリ(car、dealer)、(automobile、dealer)、及び(auto、dealer)は、(Sem1、dealer)に置換される。ここで使用されるアルゴリズムは、S−P型及びP−S型で使用されるものと同じである。

0038

複合マージ:図5の(c)に示すような、多対多のタイプのマージ。例えば、エントリ(car、dealer)、(automobile、showroom)、及び(auto、SalesOffice)は、(Sem1、Sem2)に置換される。このタイプのマージのアルゴリズムは、以下のようなものである。

0039

1.S−S型の各エントリ(wi、X)に対して、wiが、意味概念Semiに対応するように、図3の(b)の(wi、X)のエントリ全てを、図4の(c)に示すような(Semi、X)に置換する。

0040

2.(Semi、wj)のタイプの各エントリに対して、wjが、意味概念Semjに対応するように、こうした全ての(Semi、wj)を、(Semi、Semj)に置換する。

0041

上記ステップ2は、上記ステップ1の前に実行することもできることに注意すべきである。更に、このアルゴリズムのステップ1とステップ2は、マージするものがなくなるまで繰り返し行われうる。

0042

複数のエントリがマージされると、それに応じて、各エントリの構文的ワードリストも、合併(UNION)演算によってマージされる。

0043

複数の細分度を有するインデックス付け技法は、OODBMSの上位層に実装されうる。こうした実装では、図2の(a)、図3の(a)、及び図4の(c)に示すテーブルは、内容を有するクラスである。他のテーブルは、ポインタのみを有するクラスである。インデックスに対する更新、削除、及び挿入操作は、自動監視維持やクラスの間で伝達を行うプログラムを介して、OODBMSによって実行される。複数の細分度を有するインデックスの維持は累積的に行われ、再編成は必要とされない。

0044

次に、従来のワードに基づくインデックスの他に、意味概念に基づくインデックス・テーブルを支援するのに必要なために追加される記憶域のオーバーヘッドを考慮に入れて、本発明による実施例の見積りを計算する。前述したように、図4に示すテーブルが、効率的なクエリー処理のために導入される。最初に、従来のIRシステムで使用されるインデックス、即ち、図2に示すテーブルに関する記憶域の見積りに関する計算を行う。所定の集合体における文書の数はDであるとする。更に、その所定の文書の集合体における、辞書にあるワード数(ワード・ステミングを用いて、ストップ・ワードとグルーピング・ワードを取り除いた後の数)はWであり、辞書にないワードの数はVとする。また、文書毎の、辞書にあるワード数の平均をwとし、辞書にないワード数の平均をvとし、ワード毎の文書数の平均をdとする。エントリ数(即ち、行数)とテーブルの全体のサイズ(即ち、ポインタの数)に基づいて、インデックスのサイズが計算される。テーブルの各エントリが、ポインタ・データとして表されることに注意すべきである。これらのパラメータが与えられると、図2の(a)に示されたテーブルのサイズは、以下の式(2)で表される。

0045

行数[2(a)] =D ...(1)
全体サイズ[2(a)] =(1+v+w)D ...(2)。

0046

各行において、文書の識別のために1つのポインタが必要とされ、ワードのリストの中で辞書にないワードを表すのに、平均でv個のポインタが必要とされ、更にワードのリストの中で辞書にあるワードを表すのに、平均でw個のポインタが必要とされるので、(1+v+w)の項が生じていることに注意すべきである。同様に、図2の(b)に示すテーブルのサイズは、以下の式(4)で表される。

0047

行数[2(b)] =W+V ...(3)
全体サイズ[2(b)] =(1+d)・(W+V) ...(4)。

0048

このテーブルの各行は、平均で、文書リスト内で文書の識別子となるd個のポインタと、ワードそのものを指す1つのポインタを必要とする。

0049

次に、基本的なクエリー拡張を支援するのに必要な、オンライン辞書と構文的共起テーブルの記憶域オーバーヘッドを見積る。fを、辞書にあるワードを意味概念にグループ化することによって得られる圧縮要素とする。従って、fは、1つの概念にグループ化されたワードの数の平均と見ることができる。図3の(a)に示すテーブルのサイズは、以下の式(6)のように表すことができる。

0050

行数[3(a)] =W/f ...(5)
全体サイズ[3(a)] =W+W/f ...(6)。

0051

式(5)は、辞書にあるワードの記憶域が、圧縮要素fに基づいて圧縮されるので、このように表される。式(6)は、W個のポインタが、ワードのリスト内のワードを表すのに必要で、W/f個のポインタが意味的な識別子を表すのに必要であることを示している。図3の(b)で示されるテーブルのサイズは、最悪の場合、以下の式(8)で表される。

0052

行数[3(b)] =V(V−1)/2+VW+W(W−1)/2 ...(
7)
全体サイズ[3(b)]=(1+2+q)・(V(V−1)/2+VW+W(W−1
)/2) ...(8)。

0053

式(7)では、第1項がP−P型のワードの共起関係に対応し、第2項がS−P型又はP−S型に対応し、最後の項はS−S型の共起関係に対応する。qは、共起関係を表す項毎の、文書リスト内のエントリの平均数を表している。更に、構文的用語識別子を表すために3つのポインタが必要とされ、2つのワードが各行の共起関係に含まれる。

0054

次に、意味的に類似する用語の組を1つのユニークな意味概念にグループ化する、本発明による複数の細分度を有するインデックス付けに関する記憶域オーバーヘッドについて見積りを行う。前述したように、図4に示すインデックス・テーブルのサイズを計算するために、意味概念毎の平均文書数と、文書毎の意味概念の平均数を見積る必要がある。複数の用語が1つの意味概念に縮減されるので、意味概念毎の文書の平均数は、dより大きくなり、この拡張は、f・dにはならないことを示すことができる。他方、文書毎の概念の平均数は、wを越えることはない。実際に、この数がwと似たものになることを示すことができる。これらのパラメータに基づいて、複数の細分度を有するインデックス付けの追加の記憶域オーバーヘッドを計算することができる。図4の(a)に示すテーブルに関する計算は以下の通りである。

0055

行数[4(a)] =D ...(9)
全体サイズ[4(a)] =(1+v+w)D ...(10)。

0056

即ち、サイズは図2の(a)に示すテーブルと同じである。一方、図4の(b)に示すテーブルのサイズは、以下の通りである。

0057

行数[4(b)] =W/f ...(11)
全体サイズ[4(b)] =(1+df)・W/f ...(12)。

0058

辞書にあるワードのエントリの数は、ワードが意味概念に統合されるために、要素fに基づいて減少する。しかし、意味概念毎の文書の数は、その要素とほぼ同じ分だけ増加する。結果的に、このテーブルのサイズは、図2の(b)に示すテーブルと同じようなものになる。より高いレベルの細分度においては、図4の(a)と(b)に示すテーブルは、それぞれ図2の(a)と(b)に示すテーブルであることに注意すべきである。最後に、図4の(c)に示すテーブルの記憶域の見積りは、以下の式(13)、(14)のように計算される。

0059

行数[3(b)] =V(V−1)/2+V・(W/f)+(W(W−1)/2f2
) ...(13)
全体サイズ[3(b)] =(1+2+q)・V(V−1)/2+(1+2+qf)
・V・(W/f)+(1+2+qf)(W(W−1)/2f2) ...(14)

0060

基本的に、S−S型、S−P型、又はP−S型の共起用語の全ては、要素fに基づいて圧縮され、図3の(b)に示すテーブルと較べて実質的に小さな容量になる。

0061

最終的に、本発明によれば、図3の(b)に示すテーブル以外が必要とされる。一方、基本的なクエリー拡張技法は、図2及び図3に示すテーブルを全て必要とする。従って、本発明の方法を採用した場合の記憶域に関するコストは、図4の(a)と(b)に示すテーブルの記憶域の増加分だけ大きくなるが、図4の(c)に示すテーブルのサイズが小さくなるので、前記コストの増加分は部分的に埋め合わせられる。節約の正確な数値は、前述した種々のパラメータの値に依存する。最悪の場合でも、追加の記憶域は、基本的なクエリー拡張技法を使用した場合の記憶域の2倍よりかなり小さい。

0062

前述のインデックス付け技法は、ワードが単一の意味のみを有することを仮定して議論されている。しかし、ワードは、通常複数の意味を有している。例えば、「bank」というワードは、金融機関銀行)、または川岸として解釈される。複数の意味を有するワードについて考慮するため、意味的ワードリストのワード(図3で示されている)が、図4の(a)に示す複数の概念番号に属するものとする。例えば、「bank」は、Sem10とSem20に関連付けられるものとする。こうした複数の意味を考慮して、クエリーの拡張を実行するために、クエリーが、複数の異なる概念番号に属する1つのワードを含む場合、その異なる概念番号のそれぞれが、クエリーの処理の際に考慮されるべきである。

0063

上記説明においては、インデックス技法は、NECのOODBMSの上位層に実装されており、意味的ワードリスト内のワードが、ポインタによって概念番号に関連付けられている。また、冗長なデータは記憶されておらず、ポインタに関する記憶域のコストも非常に低いものである。WordNetは、あるワードに対する類義語を様々な意味の解釈で提供し、その意味が使用される頻度に応じてランク付けする。例えば、「bank」は、川岸よりも金融機関として、より多く解釈される。最も一般的な意味解釈が、現在の実行に用いられる。しかし、データ構造を拡張することもできる。

0064

前で述べられた以外の、意味のグループ化を考慮に入れることができる。図4では、類義語によるクエリーの拡張だけが考慮されている。ISA、IS_PART_OF等の、他の型の意味の緩和を考慮することもできる。図4の(a)に示す形態のテーブルを、様々な意味のグループ化(例えば、1つはISAに関して、1つはIS_PART_OFに関して)に関して複数生成することができる。また、1つのテーブルを様々な意味のグループ化に関して使用することもできる。類義語及び上位概念語の両方によってクエリーの拡張を行う場合、複数のテーブルに対してルックアップが行われる。

0065

ワード・ミスマッチの問題に対処するため、クエリー処理技法は、関連ワードを用いてクエリーのワードを拡張する必要がある。結果的に、元のクエリーのワードに対する関連性によって文書をランク付けする、追加タスクが実行されうる。次に、拡張されたクエリーの処理が、本発明による3つのタスク、即ち、クエリーの拡張、クエリーの処理、及び結果のランク付けとして提供される。

0066

まず、クエリーの拡張について説明する。図6は、従来のクエリー拡張技法の元でのクエリーの拡張の例を示している。「carとdealerというワードを含む文書を検索する」というクエリーが修正され、carとdealerに関連するワードが追加されている。意味的に類似する関連ワードと、構文的な共起関係を有する関連ワードは、図3に示すテーブルを用いて決定される。本発明による、複数の細分度を有するクエリー拡張技法の元でのクエリー拡張の例は、図7に示されている。複数の細分度を有するクエリーの拡張技法は、carとdealerというワードを、図3の(a)に示すテーブルを用いて概念Sem1とSem2に変換する。ワードを、そのワードに対応する、より上位レベルの意味概念に変換した後、図4の(c)に示すテーブルを用いて、その意味概念が、構文的関係を含むように拡張され、元のクエリーにある固有名詞が、共起テーブルからの関連ワードを含むように拡張される。

0067

辞書にあるワードと辞書にないワードの両方を含むクエリーQが与えられた場合、Qは、以下の式(15)で表現される。

0068

Q=(s1∧...∧sm)∧(p1∧...∧pn) ...(15)
式(15)では、siは辞書にあるワードを表し、pjは辞書にないワードを表す。更に、クエリーQには、辞書にあるワードがm個あり、辞書にないワードがn個ある。こうしたクエリーが与えられると、複数の細分度を有するクエリー拡張技法が、以下のように実行される。

0069

1.Qにある各si(i=1,...、m)を、図3の(a)に示すテーブルから得られた、そのsiに対応する、より上位レベルの意味概念に置換する。このように置き換えられた概念のそれぞれをCiと表記する。

0070

2.ステップ1で得られた各Ci(i=1,...、m)に対して構文的関連を有するワードを、図4の(c)に示すテーブルを用いて求め、追加することによってQを拡張する。S−S型のエントリは、概念の追加に寄与し、S−P型のエントリは、固有名詞に寄与する。

0071

3.各pj(j=1,...,n)と共に生じる、構文的関連を有するワードを、図4の(c)に示すテーブルを用いて求め、追加することによってQを拡張する。P−S型のエントリは、概念の追加に寄与し、P−P型のエントリは、固有名詞に寄与する。

0072

4.冗長なクエリーのワード又は概念をQから除去する。

0073

本発明によって拡張されたクエリーは、従来の技法によって拡張されたクエリーと較べて、よりコンパクトで、チェックすべき項目が少ない。それは、クエリーのワードが、より粗い細分度におけるエンティティに変換されているからである。結果的に、本発明により拡張されたクエリーのクエリー処理のコストは、一層小さいものになる。次に、従来の技術のクエリー拡張、及び本発明の、複数の細分度を有するクエリー拡張において導入されるエンティティ(ワード又は概念)の数が見積られる。前述のように、より上位レベルの意味概念の元でグループ化された、辞書にあるワードの平均数は、fで表される。ここで、ワードに意味的に関連付けられた、より上位レベルの概念の平均数をgとし、ワードに関連付けられた、構文的関連を有する固有名詞の平均数をhとする。そこで、基本的なクエリーの拡張(BQ)の元でのQにおけるワードの数は、以下の式(16)に示すように、ステップ1、2、及び3で発生する拡張の合計である。

0074

ワード数[BQ]=(mf)+m(g+h)+n(g+h) ...(16)
ここで、第1項は、辞書にあるm個のワードのそれぞれが意味的に類似するf個のワードに置換されるために生じる。第2項は、辞書にあるm個のワードのそれぞれに対し、辞書にある共起ワード、及び辞書にない共起ワードが(g+h)個追加されるために生じる。第3項は、(g+h)個の共起ワードを追加したn個の固有名詞のそれぞれに対応する。同様に、複数の細分度を有するクエリー拡張(MGQ)の元でのQにおけるワードと概念の数は、以下の式(17)で表される。

0075

ワード数[MGQ]=m+m(g/f+h)+n(g/f+h) ...(
17)
ここでは、使用されている類似のワードの組に関して、より上位レベルの意味表現を用いているので、圧縮要素fが現れることが、実質的に大きく異なる点である。従って、複数の細分度を有するクエリー拡張技法によって、クエリーに含まれるワード/概念の数は、基本的なクエリー拡張技法によるものよりも厳密な意味で少なくなっている。図4の(c)のテーブルにおいて、ワード毎の固有名詞の数が小さければ、本発明の技法によるクエリーの複雑さは、要素fに基づいて軽減される。

0076

今度は、クエリー処理について説明する。従来の厳密なマッチングに基づくクエリー処理では、クエリーに関連する検索の述語に関する条件を満たさないことが分かるとすぐに、検索処理を終了する。検索は類似性に基づいているので、実際のIRにおいては、そうではない。特にユーザは、ユーザの検索基準に、部分的にでもマッチした結果を見ようとするものである。従って、N個のワードを有するクエリーに対して、N回のルックアップが必要であり、これは、検索の述語におけるブール条件には依存しない。更に、部分的なマッチングが支援されているので、クエリー処理の後に、ランク付け処理を追加する必要がある。ランク付け技法は、文書の内のどのワードがクエリーにマッチするかということと、そのワードの文書内での頻度に関する情報を必要とする。

0077

ここで、2つの技法において、クエリーを処理する際のルックアップのコストについて分析する。2つの要因のために、処理コストには基本的な違いがある。この2つの要因は、以下に示すものである。

0078

・基本的なクエリー拡張におけるワード数が、複数の細分度を有するクエリー拡張におけるワード数より多いこと。

0079

・ルックアップが行われる、それぞれのテーブルのエントリ数が2つの技法で異なること。

0080

ここで、前述したクエリーQのルックアップ・コストの見積りを行う。テーブルは、平衡探索構造で組織化されており、テーブルのルックアップ操作は、テーブルの行数に応じて対数的に変化するものと仮定する。従って、前述の見積り式を用いた、基本的なクエリー拡張においてQを実行する際のルックアップ・コストは、以下の式(18)、(19)のようになる。

0081

ルックアップ・コスト(Q,BQ) = mf・log(行数[2(b)]+(m+n)・(g+h)・log(行数[3(
b)]) ...(18)
= mf・log(W+V)+(m+n)・(g+h)・log(V(V-1)/2+VW+W
(W-1)/2) ...(19)。

0082

同様に、複数の細分度を有するクエリー拡張においてQを実行する際のルックアップ・コストは、以下の式(20)、(21)のようになる。

0083

ルックアップ・コスト(Q,MGQ) = m・log(行数[4(b)]+(m+n)・(g/f+h)・log(行数[
4(c)]) ...(20)
= m・log(W/f+V)+(m+n)・(g/f+h)・log(V(V-1)/2+
V・W/f+(W(W-1))/2f2) ...(21)。

0084

辞書に有るワードのルックアップの回数が、MGQ内の要素fによって少なくなり、ルックアップの実行対象となる2つのテーブルのサイズが小さくなるので、MGQにおけるクエリー処理のコストがBQにおけるコストより小さくなるのは明らかである。

0085

次に、本発明のランク付け方法について説明する。クエリー処理段階において、より粗い細分度でのワードの表現が、関係のない文書を除去するのに用いられる。しかし、候補となる文書は、それらが2つの条件、即ち、より粗い細分度レベルにおいて「car」と「dealer」を含むという条件を満たすので、同じランクを有する。これは、クエリー処理の結果として好ましいものではない。従って、ランク付けの段階では、候補となる文書内にある元のワードがアクセスされ、それがランク付けに使われる。

0086

図8では、以下の条件を満たすキーワードを有する、4つの、候補となる文書が示されている。

0087

条件:(Sem1 ∨ Ford ∨ Buick)∧(Sem2 ∨ Ford ∨ BUICK)。

0088

最初のマッチング・キーワードがランク付けのために検索される。従って、(「car」、「dealer」)、(「auto」、「dealer」)、(「auto」、「sales office」)、及び(「Ford」、「showroom」)が、関連性の程度をランク付けするのに用いられる。

0089

候補となる文書は、クエリー内のワードを有する文書内においてマッチしたワードについての緩和の程度に基づいてランク付けされる。

0090

例えば、緩和の程度は、E<Se<Sy<X(即ち、厳密なマッチング<意味的緩和<構文的緩和<マッチングなし)の順で定義される。ここで、クエリーのワードに関し、より高いレベルで緩和がされたワードを用いたクエリーの結果は、ユーザに対して、より関連のないものを含むことになる。しかし、緩和の程度の順と定義は、アプリケーション要件によって任意である。候補となる文書を探すのに、より小さな緩和が用いられるほど、候補となる文書のランクは、より高くなる。図8の下部に、「car」と「dealer」というワードを有する文書に最も高いランクが与えられている。これは、候補のワードがクエリーのワードに厳密にマッチしたからである。「auto」と「dealer」というワードを有する文書は2番目に高いランクが与えられている。これは、クエリーのワード「car」とマッチさせるため、1つのワードのみに、意味的な緩和(即ち、クエリーの用語を、意味的に関連する用語と入れ替える)が必要とされるからである。他のランク付けに関しては、図8に示すように行われる。

0091

ランク付け技法は、以下の2つの基準に基づいて行われる。

0092

・与えられたクエリーQのキーワードに関して、Qと文書Doc1にあるキーワードWord1、Doc2にあるWord2、Doc3にあるWord3、Doc4にあるWord4との間の関係がそれぞれ、厳密なマッチング、意味的なクエリー緩和によるマッチング、構文的なクエリー緩和によるマッチング、及びマッチングなしである場合、文書は、Doc1>Doc2>Doc3>Doc4の順にランク付けされる。

0093

・M個の文書、Doci(i=1,...,M)と、文書Dociにそれぞれ対応する、クエリーにマッチするキーワード数、Matchi(i=1,...,M)に関するランク付け(スコア)は、Match1>Match2>Match3...MatchM-1>MatchMである場合、Doc1>Doc2>Doc3...DocM-1>DocM0となる。

0094

2つのキーワードを備えたクエリーを使用する、前述したランク付け技法に基づけば、図9に示すような、2つのワードを有するクエリーで文書を検索する場合の2次元ランク付けグラフが生成される。クエリーの拡張をしないと、スロット(E,E)内の文書だけが検索される。クエリーの意味的拡張と構文的拡張の両方を用いると、文書がスロット(X,X)にない限り、関連する全ての文書が検索される。

0095

このランク付けグラフは、行列として表されている。N個の用語を有するクエリーに関して、ランク付けグラフは、N×4の行列、M(i,j)(i=0...N、j=0...3)によって表される。例えば、図9のランク付けグラフは、行列M(i,j)(i=0...2、j=0...3)として表されている。例えば、スロット(E,E)、(Se,E)、(Se,Sy)、及び(X,X)は、行列内で、それぞれスロット(3,3)、(2,3)、(2,1)、及び(0,0)として表されている。この表現によれば、各文書は以下のように簡単にランク付けできる。

0096

・スロット(n,m)内の文書に対して、mが0から3の間である場合、これらの文書のランクは、スロット(i,j)(i=0...n、j=0...3)内の文書より高いスコアになる。

0097

・スロット(n1,m1)内の文書のランクのスコアは、n1≧n2かつm1≧m2である場合、スロット(n2,m2)内の文書のスコア以上になる。

0098

このランク付けグラフの表現は、市販の視覚化ツールによって実現される。例えば、Cone Treesと呼ばれる視覚化方法は、3次元のランク付け表現に関する奥行きを追加することによって変更されうる。詳細については、1993年4月、Communications of theACM, Vol. 36, No. 4,ページ57-71の、G. G. Robertson他による「Information Visualization Using 3D Interactive Animation」を参照のこと。

0099

このランク付け技法に基づけば、図9の上部のスロット内の結果は、下部における結果よりも高いスコアでランク付けされる。しかし、図9において同じクラスに属するスロットの結果をランク付けするのは困難である。図10は、そのようなランク付けがどのように行われるかを示している。結果的に示されたスロットは、更にクラスに分類され、そこで、同じクラスのスロットが同じランクを有するようにされる。

0100

本発明によるクエリー処理は、図10に示すクラス構造を用いて、クラス毎に連続して行われる。ユーザが2つのキーワードを持つクエリーを発行し、上位50個の結果が検索されるように要求した場合について考える。図10を参照すると、クエリー・プロセッサは最初に、クラス0に検索結果を生成する可能性がある。検索結果が50より多い場合、クエリー・プロセッサは、クエリー拡張タスクを実行することなく処理を終了することができる。クラス0における検索結果の数が50に満たない場合、クエリー・プロセッサはクラス1(例えば、スロット(2,3)及び(3,2))にその結果を生成することができる。検索結果(例えば、クラス0及びクラス1における)の総数が50より多い場合、クエリー・プロセッサは、更にクエリー処理をすることなく、処理を終了する。クエリー・プロセッサは、スロット(2,3)及び(3,2)内の結果も連続的に生成することができることに注意すべきである。つまり、クエリー・プロセッサは、スロット(2,3)の結果を最初に生成することができる。検索結果の総数が50を越える場合、クエリー・プロセッサは、スロット(3,2)内に結果を生成することなく、処理を終了することができる。クエリー・プロセッサは、検索結果の総数が50を越えるまで、又は最後のクラスに達するまで、前述のように、残りのスロット及びクラスから、更なる結果の生成を続けることができる。

0101

上記の例が、1つのキーワードが他のキーワードより重要であるとして、ユーザによって変更される場合、クエリー・プロセッサが検索結果のスロットを検索する順序は、その変更に応じて修正される。例えば、ユーザが、キーワード1はキーワード2より重要であると指定した場合、クラス内の水平的なクエリー処理の順序は、図11に示すように導出される。即ち、この例では、クエリー・プロセッサが、最初にスロット(3,2)に検索結果を生成する。次に、検索結果の総数が50に満たない場合、クエリー・プロセッサはその後、スロット(2,3)に結果を生成する。

0102

図12は、本発明が実行されるシステムの物理的構成を示している。こうしたシステムは、文書の集合体を記憶するデータベース1206を含んでいる。このデータベースは、概念(例えば、意味的又は構文的概念)及び、文書の集合体に対するそれらの関係を記憶するためのインデックス1208を含んでいる。システムは更に、インデックス1208を生成し、より上位の細分度を有する概念と文書の集合体に対するそれらの関係を含むインデックス1208を生成するためのインデクサ1210を含む。プロセッサ1204は、ユーザ・インタフェース1202を介してユーザから指定されたクエリーを受信するのに使用される。プロセッサ1204は、次に、クエリーを処理し、ランク付け機能を実行する。クエリーの結果とランク付け機能は、ユーザ・インタフェース1202を介して再びユーザに表示される。

0103

業者は、本発明の実施が、図12で例示された実施例に限られるものではないことを理解することができる。実際、当業者は、本発明の範囲から逸脱することなく、他の代替ハードウエア環境を使用して同様の効果を得ることができる。例えば、上述の、様々な機能が別個の要素によって実行され(例えば、クエリー処理とランク付け機能が、別の構成要素で行われる)、又は単一の要素によって行われる(例えば、単一のプロセッサが、インデックス付け、クエリー処理、及びランク付け機能を実行する)。

0104

要するに、本発明は、入力された文書に関するキーワードの組の元の有効性(適合率、及び再現率)、用語の意味を含む辞書、及びクエリーを保持したまま、効果的に複数の細分度に亘るインデックス付け(インデックス領域の節約)と、クエリー処理(処理時間の節約)を用いてクエリーの拡張を支援するための新しい技法を提供する。

0105

本発明による複数の細分度に亘るインデックス付け技法とクエリー処理技法によって、クエリーが単純化されるため、ワードの関連を示すインデックスのサイズがより小さくなり、クエリーの処理時間が短くなる。また、本発明のランク付け技法が、文書内に最初からあるワードに基づくため、ランク付けの結果に一貫性が保たれる。

0106

ここまでの開示及び教示から、当業者が、本発明に対して様々な、他の変更及び修正をすることができることは明らかである。従って、本明細書では本発明のいくつかの実施例についてのみ述べているが、本発明の意図及び範囲を逸脱することなく、本発明に対して様々な変更を考えることができる。

発明の効果

0107

本発明によれば、ワード・ミスマッチの問題と、結果的に生じるクエリー処理の非効率さを解決するために、小さなサイズのインデックスを使用して、効率的なクエリー拡張が行われる。具体的には、クエリー内に指定されたワードと意味的に類似し、構文的に関連のあるワードを用いて、そのクエリーを、物理的ではなく概念的に拡張し、結果的に、関連する文書を逃すことを少なくすることができる。

図面の簡単な説明

0108

図1情報検索に関するワード・ミスマッチの問題を示す図である。
図2厳密なマッチングの情報検索システムで、従来より使用されているインデックスの例を示す図である。
図3従来の情報検索システムで使用するために、ワードを意味的に類似した概念、及び構文的に関連する拡張にグループ化することによって得られたインデックスの例を示す図である。
図4本発明において、より効率的にクエリー処理を行うために必要なインデックス構造を示す図である。
図5共起ワードのインデックスのエントリをマージする処理を示す図である。
図6従来の情報検索システムにおけるクエリー拡張処理を示す図である。
図7本発明による、複数の細分度を有するクエリー拡張技法を用いたクエリー拡張処理を示す図である。
図8本発明による、ランク付け処理を示す図である。
図92つのワードを有するクエリーのランク付けを表す2次元グラフである。
図10連続的なクエリー処理の順序を示す図である。
図11キーワードがあるレベルの重要度割り当てられている場合の、連続的なクエリー処理の順序を示す図である。
図12本発明が実施可能な一実施形態の物理的構成を示す図である。

--

0109

1202 ユーザ・インタフェース
1204プロセッサ
1206データベース
1208インデックス
1210 インデクサ

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ