JP4314221B2

JP4314221B2 - 構造化文書記憶装置、構造化文書検索装置、構造化文書システム、方法およびプログラム

Info

Publication number: JP4314221B2
Application number: JP2005219165A
Authority: JP
Inventors: 拓也金輪
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2005-07-28
Filing date: 2005-07-28
Publication date: 2009-08-12
Anticipated expiration: 2025-07-28
Also published as: US20070027671A1; CN1904896A; JP2007034827A; US7613602B2

Description

本発明は、異なる文書構造の複数の構造化文書を、階層化された論理構造を持つ構造化文書データベースで管理する構造化文書記憶装置、構造化文書記憶装置から構造化文書を検索する構造化文書検索装置、これら構造化文書記憶装置と構造化文書検索装置を含む構造化文書システム、方法およびプログラムに関する。

ＸＭＬ（eXtensible Markup Language）などで記述された構造化文書データを記憶または検索するための構造化文書データベースが提案されている。構造化文書データベースを用いることによって、従来のテキストデータベースでは難しかった、構造を意識した検索が可能となる。この構造化文書データベースに対して検索を行なうためには、ＸＱｕｅｒｙに代表される構造化文書に対する問合せ言語を使用する。ＸＱｕｅｒｙは、Ｗ３Ｃ（World Wide Web Consortium）が標準化を進めている問合せ言語である。問合せ言語の特徴は、検索結果が単なるフィルタリングによるものではなく、複数の情報源である文書から、構造を持った新規の複合データを作成することが可能となることである。

一方、全文検索の分野では、構造の無い文書である文字列を管理するテキストデータベースが主流である。全文検索の重要な機能として、スコアリング、ワイルドカード、近傍検索、曖昧検索などがあり、これらを検索することがテキストデータベースには必要とされることが多い。
特に、スコアリングは全文検索においては必須機能である。スコアリングを導入することで、ユーザは、精度の高い情報（例えば、文書）を検索結果の上位として取得することが可能となり、必要な情報だけを素早く取得することが可能となる。

構造化文書データベースにおいても、問合せ時に、キーワードを指定した全文検索的な利用が可能ではあるが、せいぜい前方一致検索程度の機能程度であり、スコアリング等の機能は十分に考慮されているとはいえない。なぜなら、構造化文書は、構造を持つ、つまり、複数の要素から構成されているので、全文検索での場合と同じように、文書単位で求めることができないからである。

スコアの計算方法として有名なのは、ｔｆ−ｉｄｆ（term frequency − document frequency）法である。ｔｆは検索語がその文書内に発生した回数、ｉｄｆはその検索語が出現する文書数を示している。ｔｆは頻度が高い検索語ほど優先度を高くし、ｉｄｆはその検索語が特徴的であるかどうかの尺度を示す。これらを掛け合わせることで、ｔｆ−ｉｄｆ値としてスコアリングする。

構造化文書は複数の要素から構成されているので、どのレベルでスコアリングするかが重要になってくる。近年、構造化文書データベースの需要が広まっていることから、構造化文書データベースにおいても、スコアリングを高速に実現することが期待されている。

構造化文書データベースにおけるスコアリングを導入するためには、スコアリングの精度が重要となるとともに、これらを現実的な時間、リソースで求めることが重要になってくる。つまり、「精度」と「速度」の問題が重要になってくる。

例えば、特許文献１では、構造や語彙の曖昧性を加味した形でスコアリングを行なう構造化文書データベースが提案されている。この文献では、要素名や値など、類義語展開を意味ネットワークにより計算したり、階層関係における、「深さ情報」などを利用して、構造や語彙の類似度を計算しつつ、所望のデータを生成する。
特開２００２−２９７６０５公報

この発明は、上述した事情を考慮してなされたものであり、ＸＱｕｅｒｙのような加工型の問合せ言語を、スコアリングの精度を高く、かつ、高速に検索可能にするように情報を記憶する構造化文書記憶装置、スコアリングの精度を高く、かつ、高速に検索可能にする、構造化文書検索装置、構造化文書システム、方法およびプログラムを提供することを目的とする。

上述の課題を解決するため、本発明の構造化文書記憶装置は、１つの構造化文書を取得する取得手段と、前記構造化文書を解析する構造情報解析手段と、構造化文書の典型的な構造を示す構造雛型木を予め記憶している構造雛型木記憶手段と、前記構造雛型木を前記解析された構造化文書に合致するように更新する更新手段と、前記１つの構造化文書を複数の語彙に分割する分割手段と、前記１つの構造化文書内の要素ごとに該要素内に存在する全ての語彙に対して語彙ごとに該語彙が発生する頻度を示す発生頻度情報を算出する頻度情報算出手段と、前記語彙ごとに該語彙を含む範囲内で或る出現回数以上の他の語彙が存在するまで前記範囲を拡大する拡大手段と、前記拡大された範囲内で最も出現回数が多い語彙の語彙識別子を前記語彙の関連語彙識別子として付与する関連語彙識別子付与手段と、前記語彙ごとに前記関連語彙識別子を記憶している関連語彙識別子記憶手段と、前記構造雛型木の各ノードに構造雛型木識別子を付与する構造雛型木識別子付与手段と、或る語彙の関連語彙識別子が最も多く発生するノードの構造雛型木識別子を該或る語彙の関連構造雛型木識別子として付与する関連構造雛型木識別子付与手段と、前記語彙ごとに関連構造雛型木識別子を記憶している関連構造雛型木識別子記憶手段と、を具備することを特徴とする。

本発明の構造化文書検索装置は、上記に記載の構造化文書記憶装置を参照する構造化文書検索装置であって、複数の構造化文書の部分構造から構成される新たな複合文書を生成するための問合せ言語で記述された問合せデータを受け付ける受付手段と、前記問合せデータを構文解析する構文解析手段と、前記構文解析された問合せデータに含まれる、問合せの回答として要求される要求構造に類似する類似構造を持つ、構造雛型木に含まれるノードを前記構造化文書記憶装置から複数の候補として選択する選択手段と、語彙の間の類似度合いを示す類似度を複数の語彙について記憶している類似関係記憶手段と、前記類似度に基づいて、前記候補ごとに該候補が前記要求構造に類似している度合いを示す構造スコア値を算出する構造スコア値算出手段と、少なくとも、前記候補と前記構造雛型木とを照合することに基づいて、どの順番で各候補を処理するかを示す各候補の処理コストを算出する処理コスト算出手段と、少なくとも前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出し、該処理優先度の高い候補から順に、処理を行う選択候補として選択する処理優先度算出手段と、前記選択候補から処理を実行する処理実行手段と、複数の前記処理を実行した実行結果を検索結果として取得する結果取得手段と、を具備することを特徴とする。

本発明の構造化文書システムは、構造化文書記憶装置と構造化文書検索装置を具備した構造化文書システムであって、
前記構造化文書記憶装置は、１つの構造化文書を取得する取得手段と、前記構造化文書を解析する構造情報解析手段と、構造化文書の典型的な構造を示す構造雛型木を予め記憶している構造雛型木記憶手段と、前記構造雛型木を前記解析された構造化文書に合致するように更新する更新手段と、前記１つの構造化文書を複数の語彙に分割する分割手段と、前記１つの構造化文書内の要素ごとに該要素内に存在する全ての語彙に対して語彙ごとに該語彙が発生する頻度を示す発生頻度情報を算出する頻度情報算出手段と、前記語彙ごとに該語彙を含む範囲内で或る出現回数以上の他の語彙が存在するまで前記範囲を拡大する拡大手段と、前記拡大された範囲内で最も出現回数が多い語彙の語彙識別子を前記語彙の関連語彙識別子として付与する関連語彙識別子付与手段と、を具備し、
前記構造化文書検索装置は、複数の構造化文書の部分構造から構成される新たな複合文書を生成するための問合せ言語で記述された問合せデータを受け付ける受付手段と、前記問合せデータを構文解析する構文解析手段と、前記構文解析された問合せデータに含まれる、問合せの回答として要求される要求構造に類似する類似構造を持つ、構造雛型木に含まれるノードを前記構造化文書記憶装置から複数の候補として選択する選択手段と、語彙の間の類似度合いを示す類似度を複数の語彙について記憶している類似関係記憶手段と、前記類似度に基づいて、前記候補ごとに該候補が前記要求構造に類似している度合いを示す構造スコア値を算出する構造スコア値算出手段と、少なくとも、前記候補と前記構造雛型木とを照合することに基づいて、どの順番で各候補を処理するかを示す各候補の処理コストを算出する処理コスト算出手段と、少なくとも前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出し、該処理優先度の高い候補から順に、処理を行う選択候補として選択する処理優先度算出手段と、前記選択候補から処理を実行する処理実行手段と、複数の前記処理を実行した実行結果を検索結果として取得する結果取得手段と、を具備することを特徴とする。

本発明の構造化文書記憶装置、構造化文書検索装置、構造化文書システム、方法およびプログラムによれば、ＸＱｕｅｒｙのような加工型の問合せ言語を、スコアリングの精度を高く、かつ、高速に検索可能にする。

以下、図面を参照しながら本発明の実施形態に係る構造化文書記憶装置、構造化文書検索装置、構造化文書システム、方法およびプログラムについて詳細に説明する。
まず、実施形態の概要を説明する。本実施形態においては、特に、「複数の情報源（例えば、文書）から構造を持つ新規の複合データを生成および加工することができる言語」を考慮したスコアリングについて詳細に説明する。このような言語は加工型の問合せ言語と呼ばれ、例えば、ＸＱｕｅｒｙがそれに該当する。
構造化文書データベースにおける問合せ言語は、全文検索エンジンのようなキーワードレベルの検索と異なり、さらに構造情報を指定することが可能である等が示すように記述レベルが高く、複雑な表現をすることが可能である。特に、Ｗ３Ｃで標準化が成されているＸＱｕｅｒｙのような複数の情報源から構造を持つ複合データを生成および加工することができる言語は、その記述能力の高さとともに、問合せの最適化を如何に行なうかが問題であり、これら、問合せの最適化とスコアリングを融合して考えることが重要になってくる。

本実施形態では、問合せ処理を行なう際に、問合せに対する回答の各候補に対して一時的なスコア値と処理コストをもとに、処理優先度を決定する。構造化文書検索装置は、この処理優先度を利用することによって、精度よく、かつ、検索時間の高速化を行なうことを可能とする機能を持つことを特徴とする。

その他の本実施形態の特徴について以下に列挙する。
（１）構造化文書記憶装置は、構造化文書を登録する際に、構造情報（スキーマ）の特徴抽出を行い、データベース上に構造雛型木を作成または更新する。次に、構造化文書記憶装置は、文字列値を分割し、語彙索引の語彙索引情報として転置索引リストを作成する。この際に、各語彙索引情報として、構造雛型木上の識別子を付加しておく。これらは、構造化文書検索装置が行う検索時の構造制約条件であり、検索処理速度向上のために用いられる。

（２）構造化文書記憶装置は、語彙索引の各語彙索引情報として、その語彙と関連性が高い語彙として、その要素中で発生する全ての語彙に対する頻度情報を計算し、最大頻度を持つ語彙を関連語彙として語彙索引情報に残す。この際、最大頻度を持つ語彙の頻度が閾値以下である場合は、それぞれの語彙索引情報が発生する文字列を基点に、頻度情報を計算する範囲を広げていくことも可能とする。これにより、例えばＸＱｕｅｒｙにより、Ｒｅｔｕｒｎ節に並べられた別の変数に対するスコア（要素を超えたスコア）を求めることが可能となる。

（３）構造化文書検索装置が構造化文書を検索する際に、問合せ言語（ＸＱｕｅｒｙ）を解析し、問合せ言語の出力となる構造によって生成される仮想的な構造情報から、曖昧性を含んだ形で類似する構造を、構造化文書記憶装置が作成または加工した構造雛型木から検索する。このとき得られた類似度を構造スコア値とする。

（４）構造化文書検索装置は、プラン実行中の候補集合の候補それぞれに関して、構造スコアと語彙スコアと個別の処理コストを考慮して、逐次的に処理優先度を作成して、処理の可否を決定する。例えば、語彙索引により求めた候補値に対して、親子関係などの構造チェックが必要な場合、そのチェックがＸＭＬとして階層が深く、ディスクアクセスが多大に発生されることが予め予想されるならば、処理コストが高く設定され、これと、構造スコア値、語彙スコア値とを照らし合わせて、場合によってはこの候補をスキップすることで計算量を削減する。

（５）問合せ言語処理方式は、制約充足型方式に基づく（例えば、特開２００２−２９７６０５公報を参照）。

次に、本実施形態の構造化文書システム、すなわち、構造化文書記憶装置および構造化文書検索装置について図１を参照して説明する。
構造化文書記憶装置および構造化文書検索装置は、一般に図１に示すようにサーバであり、図１に示すようにクライアントからの問い合せに応じて動作する。クライアントは、入力部１０１，１０２、登録部１０３、検索部１０４を備えている。これらの装置部分は１つのクライアントに含まれる場合もあるし、第１のクライアントは入力部１０１と登録部１０３を備え、第２のクライアントは入力部１０２と検索部１０４を備えていてもよい。

入力部１０１は、ユーザから格納要求を受け付け、登録部１０３にこの格納要求を渡す。登録部１０３は、この格納要求を受けて、サーバである構造化文書システムに、格納しようとする格納データを送信する。この格納データは、ＸＭＬなどの構造化文書である。構造化文書は文字列からなる。

一方、入力部１０２は、ユーザからの検索要求を受け付け、検索部１０４にこの検索要求を渡す。検索部１０４は、この検索要求を受けて、サーバである構造化文書システムに、検索要求に対応する、ＸＱｕｅｒｙなどの問合せ言語からなる問合せデータを送信する。また、検索部１０４は、構造化文書システム内の構造化文書検索装置で求められた検索結果を受け取る。この検索結果は、例えば、ＸＭＬデータのデータ形式である。

構造化文書システムは、構造化文書記憶装置と構造化文書検索装置とからなる。構造化文書記憶装置は、要求処理部１０５、格納処理部１０６を備え、さらにデータベース１１７として、構造化文書データ記憶部１１８、語彙索引記憶部１１９、構造雛型木記憶部１２０、語彙統計情報記憶部１２１、意味ネットワーク記憶部１２２を備えている。
構造化文書検索装置は、要求処理部１０５、検索処理部１１１を備え、さらにデータベースとして、構造化文書データ記憶部１１８、語彙索引記憶部１１９、構造雛型木記憶部１２０、語彙統計情報記憶部１２１、意味ネットワーク記憶部１２２を備えている。

要求処理部１０５は、クライアントが送信するデータを受信し、受信したデータが格納要求に基づく格納データであるのか、検索要求に基づく問合せ言語からなる問合せデータであるのかを判定する。要求処理部１０５は、この判定結果に基づいて、格納データを受信した場合には格納データを格納処理部１０６に出力し、問合せデータを受信した場合には問合せデータを検索処理部１１１に出力する。さらに、要求処理部１０５は、検索処理部１１１が検索処理した処理結果をクライアントに転送する。

格納処理部１０６は、クライアントからの格納データを受けて、この格納データに含まれる構造化文書を解析し、検索に関する語彙索引情報を作成し、データベースの各記憶部に対応する語彙索引情報を記憶させる。

検索処理部１１１は、クライアントからの問合せデータを受けて、指定された問合せデータに基づいてデータベースに含まれる各記憶部を参照することによって、所望の構造化データを作成し、得られた構造化データをクライアントに転送する。

また、格納処理部１０６は、構造情報抽出部１０７、統計情報計算部１０８、索引情報格納部１０９、制御部１１０を備えている。
構造情報抽出部１０７は、クライアントからの格納データに含まれる構造化文書を解析し、解析した構造化文書と、構造雛型木記憶部１２０に格納されている構造雛型木とを照合し、構造雛型木を解析した構造化文書に合致するように更新し、更新された構造雛型木を構造雛型木記憶部１２０に記憶させる。また、構造情報抽出部１０７は、構造雛型木が構造雛型木記憶部１２０に無い場合には構造化文書に合致する構造雛型木を生成し、生成された構造雛型木を構造雛型木記憶部１２０に記憶させる。そして、構造情報抽出部１０７は、格納データに含まれる構造化文書の構造情報（文書中の各要素間の親子兄弟関係など）に関する情報を更新し、構造化文書データ記憶部１１８に記憶させる。また、構造情報抽出部１０７は、ＤＯＭ（Document Object Model）のようなオブジェクトツリー形式に展開し、構造雛型木の各ノードに構造雛型木識別子（以下、ＴＩＤと称する）を付与して、構造情報と共にＴＩＤも構造化文書データ記憶部１１８に記憶させる。ＴＩＤの一例は後に図５に示す。

統計情報計算部１０８は、検索のための索引付け及びスコアリングに関する情報を得るために行なわれる。統計情報計算部１０８は、文字列に対応する部分の語彙を分割し、分割した語彙に語彙識別子（以下、ＧＩＤと称する）を付与し、それぞれの語彙に対する索引を作成し、各語彙がどの語彙とどの程度関連しているかを計算する。また、統計情報計算部１０８は、ＧＩＤの他に、語彙が発生した文書ＩＤ、要素ＩＤ、発生位置、その要素に対応するＴＩＤ、関連度の高いＧＩＤ（関連ＧＩＤ）、そのＧＩＤが最も多く発生する構造のＴＩＤ（関連ＴＩＤ）を各語彙に付与する。統計情報計算部１０８は、これらの語彙識別子、計算結果を語彙索引情報として生成する。関連ＧＩＤ、関連ＴＩＤについては後に図３を参照して説明する。統計情報計算部１０８は、構造化文書の要素中で発生する全ての語彙に対する頻度情報を計算し、ＧＩＤと対応付けて頻度情報を語彙テーブルに含め、語彙統計情報記憶部１２１に記憶させる。また、統計情報計算部１０８は語彙テーブルと語彙索引情報とを関連付けて転置索引リストを作成する。

索引情報格納部１０９は、語彙テーブルと語彙索引情報とを関連付けた転置索引リストを語彙索引記憶部１１９に記憶させる。図７のようにデータを格納していく。転置索引リスト上に格納される、それぞれの語彙索引情報は、上述で求めた通りであり、これら情報が語彙索引記憶部１１９に記憶される。語彙テーブルの一例については後に図６を参照して説明する。また、語彙テーブルと語彙索引情報との関係については後に図７を参照して説明する。
制御部１１０は、格納処理部１０６の全体の動作を制御するためのものである。

構造化文書データ記憶部１１８は、構造情報抽出部１０７で抽出された、格納データに含まれる構造化文書の構造情報に関する情報を記憶する。構造化文書データ記憶部１１８は、オブジェクトツリーの各ノードに対して、対応するＴＩＤの情報を付加し、これらデータを格納する。構造化文書データ記憶部１１８は、文書をＵＮＩＸ（登録商標）のディレクトリ構造のように階層的にツリー構造状に格納している。
語彙索引記憶部１１９は、語彙テーブルと語彙索引情報とを関連付けた転置索引リストを記憶する。
構造雛型木記憶部１２０は、予め構造雛型木を格納している。また、構造情報抽出部１０７によって更新された構造雛型木も記憶する。
語彙統計情報記憶部１２１は、頻度情報を語彙統計情報として記憶する。

意味ネットワーク記憶部１２２は、それぞれ、単語と、それと関連する単語を類似度付きで関連付けた意味ネットワークを記憶している。意味ネットワークとは、語彙の間の類似関係をグラフで表現したものであり、類似関係のある語彙と語彙をアークで結び、その語彙間の類似度の値をアークに与えて、語彙間のネットワークを構成しているものである。

検索処理部１１１は、問合せ解析部１１２、問合せプラン作成部１１３、問合せ実行部１１４、結果生成部１１５、制御部１１６を備えている。

問合せ解析部１１２は、要求処理部１０５で受け付けられたユーザからの検索要求であるクエリを入力とし、入力したクエリを解析して、問合せグラフを生成する。問合せ解析部１１２は、問合せグラフに対して、データベース上の構造的な制約条件である構造制約条件を求める。さらに、問合せ解析部１１２は、クエリの問合せとして最終的に求めることが要求される結果である仮想的な構造情報を入力して、この構造と類似する構造が構造雛型木記憶部１２０に存在するかどうかを検索し、類似している構造を選択し、意味ネットワーク記憶部１２２を参照して、この類似している構造の類似度を求める。さらに、類似構造検索部４０３はこの構造に対応する類似度をスコアリングに反映させる。

問合せプラン作成部１１３は、クエリ条件グラフを入力として、クエリ中に発生する検索条件を考慮して、構造化文書データベース中に格納されている各種データの組み合わせを作成する。問合せプラン作成部１１３は、問合せ解析部１１２の情報を利用して、問合せ実行時の処理コストを見積もり、実際に実行するプランを作成する。問合せプラン作成部１１３は、問合せ言語構文解析部４０１で作成された問合せグラフに対して、構造制約条件作成部４０２と、類似構造検索部４０３の制約条件を加味して、如何に低処理コストで、処理を実行できるかを調査する。

問合せ実行部１１４は、プラン作成部４０５で作成したプラン情報を順次実行して、候補となる集合を作成する。問合せ実行部１１４は、各候補を処理する処理コストを事前に見積もる。問合せ実行部１１４は、最終的なスコア値が低くなることが予測され、かつ、処理コストが重い候補の処理を後に回すことを行なうための処理優先度を計算する。問合せ実行部１１４は、決定された処理の実行の可否に基づいて、処理優先度の高いものから処理を実行する。また、問合せ実行部１１４は、作成したプランに応じて、処理を繰り返し実行し、最後の処理を実行した後、結果件数をチェックする。

結果生成部１１５は、検索結果として構造化文書のＸＭＬデータを作成する。その際、結果生成部１１５は、検索された構造化文書の集合を類似度の高い順からソートしてＸＭＬ形式で出力する。結果生成部１１５は、検索結果として上位のものから順に結果として、取得件数分ＸＭＬデータを作成する。
制御部１１６は、検索処理部１１１の全体の動作を制御するためのものである。

次に、ＸＭＬで記述された構造化文書の一例について図２を参照して説明する。ＸＭＬは、構造化文書を記述するための代表的な言語である。図２は、ＸＭＬで記述された構造化文書の一例として、「特許」情報の例を示したものである。
ＸＭＬやＳＧＭＬは、文書の構造の表現にタグ（要素とも呼ばれる）が用いられる。タグには、開始タグと終了タグがあり、文書構造情報の構成要素を開始タグと終了タグで囲むことにより、文書中の文字列区切りと、その文字列が構造上どの構成要素に属するのかを明確に記述することができる。文字列はテキストと呼ばれることもある。

開始タグとは、要素名称を記号「＜」、「＞」で閉じたものであり、終了タグとは要素名称を記号「＜／」と「＞」で閉じたものである。タグに続く構成要素の内容が、文字列または子供の構成要素の繰り返しである。また、開始タグには「＜要素名称属性＝“属性値”＞」などのように属性情報を設定することができる。また、図２には記述されていないが、「＜特許ＤＢ＞＜／特許ＤＢ＞」のように文字列を含まない構成要素は、簡易記法として「＜特許ＤＢ／＞」のように表すこともできる。

図２に示した文書は、「特許」タグから始まる要素を文書ルートとし、その子要素として「タイトル」タグ、「発明者リスト」タグ、「発明者」タグ、「効果」タグ、「キーワードリスト」タグ、「キーワード」タグから始まる要素集合が存在する。また、例えば、「タイトル」タグから始まる要素には「構造化文書検索装置」といった、１つの文字列が存在する。一般的に「文書」は複数のタグから構成されており、テキストデータベース等で扱う「文書」とは、これら複数のタグを無視した、文字列値だけの繋がりして扱う場合が多い。

次に、格納処理部１０６に含まれる、構造情報抽出部１０７、統計情報計算部１０８について図３を参照して説明する。
構造情報抽出部１０７は、構造化文書構文解析部３０１、構造雛型木照合部３０２、構造雛型木更新部３０３、構造化文書データ格納部３０４を備えている。
統計情報計算部１０８は、テキスト分割部３０５、語彙識別子特定部３０６、関連語彙計算部３０７を備えている。

構造化文書構文解析部３０１は、要求処理部１０５から渡されたテキスト形式である構造化文書を入力し、この構造化文書を構文解析して、ＤＯＭのようなオブジェクトツリー形式に展開する。構造化文書構文解析部３０１は、文書については文書ＩＤを付与し、オブジェクトツリーを構成する各要素に対してユニークな要素ＩＤを付加する。他に、発生位置、要素に対応するＴＩＤも付与する。発生位置は文字列の位置が何文字目であるかを示す。

構造雛型木照合部３０２は、オブジェクトツリーを走査して、特徴的な構造情報を抽出する。既にデータベース上の構造雛型木記憶部（１１６）に登録されている場合は、その構造雛型木と、オブジェクトツリーとを照合する。オブジェクトツリーと構造雛型木の一例については後に図５を参照して説明する。

構造雛型木更新部３０３は、あるタグが同列で重複しているような構造は一つに集約して特徴的な構造として抽出し、それら構造情報を構造雛型木として作成し、更新する。

構造化文書データ格納部３０４は、先にＤＯＭ形式に展開されたノードに対して、それぞれ構造雛型木に対応するＴＩＤを与え、ＴＩＤが構造化文書とともに構造化文書データ記憶部１１８に記憶させる。

テキスト分割部３０５は、語彙に対する索引を作成するために必要な情報を作成するために、文字列を、オブジェクトツリー上の、文字列に対応する部分の語彙に分割する。具体的には、文字列を入力として、例えば、形態素解析やＮ−ｇｒａｍ方式などで対象となる文字列を複数の語彙に分割する。後に、関連語彙計算部３０７が、分割した各語彙に対して語彙索引情報を作成する。
統計情報計算部１０８は、分割した語彙を文字列で管理するのではなく、分割した語彙にユニークなＧＩＤを対応付ける。ＧＩＤの項目は語彙テーブルに含まれる。語彙テーブルの一例については後に図６を参照して説明する。また、語彙テーブルと語彙索引情報の関係については後に図７を参照して説明する。

語彙識別子特定部３０６は、分割した各語彙に、各語彙に対応する識別子を特定し付与する。この識別子としては、その語彙が発生した文書ＩＤ、要素識別子（以下、要素ＩＤと称する）、発生位置、その要素に対応するＴＩＤ、関連ＧＩＤ、関連ＴＩＤがある。文書ＩＤや要素ＩＤは、構造化文書構文解析部３０１が自動的にこれらＩＤの振り分けを行なう。発生位置は分割した文字列位置が何文字目であるかを示す。発生位置、要素に対応するＴＩＤも構造化文書構文解析部３０１が求める。関連ＧＩＤ、関連ＴＩＤは、次の関連語彙計算部３０７が求める。

関連語彙計算部３０７は、分割した各語彙について、基本的には、ある文字列中で最も出現回数が多い語彙のＧＩＤを関連ＧＩＤとするが、文字列に含まれる文字数が少ない場合は、探索範囲を拡大して、この探索範囲で出現回数が多い語彙のＧＩＤを関連ＧＩＤとする。出現回数の閾値として、予め最低頻度を設定しておき、選択された文字列中で関連語彙を求める際に、最大頻度を持つ語彙の出現回数がその値よりも小さい場合は、その文字列だけで関連語彙を決定せずに、その文字列を基点として、属性値、兄弟要素の文字列、親要素の文字列の順に頻度が閾値を超えるまで、範囲を広げて同様の処理を行なう。なお、最低頻度の閾値は、固定値ではなく対象となる要素サイズに応じて適宜決定しても良い。関連ＧＩＤを決定する具体例について後に図８を参照して説明する。
また、関連語彙計算部３０７は、関連ＧＩＤを探索中の文字列の中で、最も多く発生した語彙に対するＴＩＤが関連ＴＩＤであるとして計算する。この場合に、ある語彙が、同一要素中に複数回発生する場合は、二つ目以降の語彙の関連ＧＩＤとしては、最大頻度を持つＧＩＤではなく、その次の頻度を持つＧＩＤを関連語彙として付加する。こうすることで、文字列中で発生頻度が高い語彙に関しては、複数の関連ＧＩＤを付加することができる。関連語彙計算部３０７は、このようにして、分割した各語彙に対して語彙索引情報を作成する。語彙索引情報の一例については後に図９を参照して説明する。

次に、検索処理部１１１に含まれる、問合せ解析部１１２、問合せプラン作成部１１３、問合せ実行部１１４について図４を参照して説明する。
問合せ解析部１１２は、問合せ言語構文解析部４０１、構造制約条件作成部４０２、類似構造検索部４０３を備えている。
問合せプラン作成部１１３は、クエリ処理コスト見積もり部４０４、プラン作成部４０５を備えている。
問合せ実行部１１４は、処理優先度計算部４０６、処理実行部４０７を備えている。

問合せ言語構文解析部４０１は、要求処理部１０５から渡された問合せデータ（例えば、クエリ）を構文解析し、解析結果として問合せグラフを作成し、構造化文書検索装置が処理できる形式に変換する。この問合せグラフは、プラン作成部４０５がクエリのプラン作成を行なう際に必要となる、問合せデータに含まれている要素間の制約関係を示す。構文解析はパージングとも呼ばれ、この解析結果として得られる問合せグラフはクエリグラフとも呼ばれる。問合せ言語構文解析部４０１が作成する問合せグラフについては後に図１０を参照して説明する。

構造制約条件作成部４０２は、問合せ言語構文解析部４０１で作成された問合せグラフに対して、データベース上の構造的な制約条件である構造制約条件を求める。構造制約条件は、問合せグラフのアークに対して付与されるものであり、親ノードと子ノードが対応する構造雛型木上のＴＩＤのペア［親ＴＩＤ制約、子ＴＩＤ制約］である。構造制約の親子関係を求めておくことで、構造制約によって、候補となる件数を早期に絞り込むことが可能となる。構造制約条件作成部４０２の動作の具体例については後に図１０を参照して説明する。

類似構造検索部４０３は、ＸＱｕｅｒｙの問合せとして最終的に求めることが要求される結果である、Ｒｅｔｕｒｎ節に記述された複合文書が構成する仮想的な構造情報を入力して、語彙統計情報記憶部１２１にある頻度情報を参照して、この構造と類似する構造が構造雛型木記憶部１２０に存在するかどうかを検索し、類似している構造を選択し、意味ネットワーク記憶部１２２を参照して、この類似している構造の類似度を求める。さらに、類似構造検索部４０３はこの構造に対応する類似度をスコアリングに反映させる。

ところで、ＸＱｕｅｒｙに代表される、加工型問合せ言語においては、Ｒｅｔｕｒｎ節には、データベース上には実際に存在しない、仮想的な要素、属性、文字列などを記述することが可能である。これらの仮想的な要素、属性、文字列などは、ユーザがクエリで自由に記述することができるものである。また、Ｒｅｔｕｒｎ節中の、＄ｘと＄ｙなどの仮想的な構造関係などもデータベース上にはないので、このままではスコアリングに反映されない。

しかしながら、これら複合文書によって最終的に作成されるデータ構造は、ユーザが欲しい情報に対する一つの意思表示であるので、スコアリングに反映させるべきである。例えば、＜ｔｉｔｌｅＬｉｓｔ＞で結果を纏め上げたとした場合は、その中身としては、＜ｔｉｔｌｅＬｉｓｔ＞に関連するような内容であることをユーザは期待している。これらの内容に類似するものを、スコア値として高く設定することによって、精度の高い情報を速く提示できるようになる。このスコア値を構造スコア値と定義する。

ただし、ユーザがクエリとして記述する場合は、タグ名に揺らぎがあったり、構造的に欠落する部分や、余剰な部分なども存在することが多い。なぜならば、ユーザは、データベース中にどういうタグ名がどういう構造で格納されている、などといった情報を一般的には知らないからである。したがって、これらタグ名や構造の揺らぎを吸収するべく、類似構造検索部４０３は、意味ネットワーク記憶部１２２を参照して、タグ名などの展開を行ない、厳密ではない構造に対しても類似度付きで検索を可能にする。意味ネットワーク記憶部１２２の内容の一例については後に図１２を参照して説明する。

類似構造検索部４０３が構造スコア値を求める際には、まず、Ｒｅｔｕｒｎ節の出力となる仮想的なデータ構造が実際のデータベース中で類似する部分を、構造雛型木記憶部１２０に記憶されている構造雛型木上から検索する。この際に、意味ネットワーク記憶部１２２の内容を用いて、多少のタグ名の揺らぎを吸収した形で検索を行なう。

類似構造検索部４０３が類似する構造情報を構造雛型木上から見つけた場合は、構造制約条件作成部４０２で求めた構造制約条件に対して、この時点までに意味ネットワーク上で展開した類似度をそれぞれのＴＩＤごとに付加して、その付加した値を構造スコア値とする。類似構造検索部４０３が構造スコア値を求める一例については後に図１３を参照して説明する。

なお、類似構造検索部４０３が、Ｒｅｔｕｒｎ節の出力構造の構成を事前に解析し、構造雛型木上から、曖昧度を含めて検索することに特徴があり、意味ネットワークの構築方法や精度、及び、構造雛型木上のマッチングアルゴリズムに関しては、既存の技術を用いても構わない。

問合せプラン作成部１１３は、問合せ言語構文解析部４０１で作成された問合せグラフに対して、構造制約条件作成部４０２と、類似構造検索部４０３の制約条件を加味して、如何に低処理コストで、処理を実行できるかを調査することが主な役目である。

クエリ処理コスト見積もり部４０４は、問合せ言語構文解析部４０１が作成した問合せグラフに関して、どの順番で処理を実行するかを決定するための処理コスト計算を行なう。クエリ処理コスト見積もり部４０４は、問合せグラフに関しては、一般的には語彙索引などの索引によって先に候補集合を絞り込んだ後に上流展開をする場合が多いが、ここでは、語彙統計情報記憶部１２１に格納された頻度情報から語彙の出現頻度を予め見積もった上で処理コストを決定する。クエリ処理コスト見積もり部４０４は、頻度情報の他にも、ＣＰＵ処理コストやディスクアクセス量、結合処理の少なさ、メモリ量制限、索引の有無など、様々な統計情報などを利用して、処理高速化を計る。

プラン作成部４０５は、クエリ処理コスト見積もり部４０４が見積もった処理コストを基に、問合せグラフの処理順序を決定する。一般的に、これらプランは複数候補が存在するが、この中でも、処理コストの低くなるものを一つ選んで実行する。プラン作成部４０５は、あくまで処理コストなどから事前に問合せグラフに対する処理順序を決定するだけで、実際に、そのプランに基づいて問合せ処理を実行するのが、問合せ実行部１１４である。

問合せ実行部１１４では、プラン作成部４０５で作成したプラン情報を順次実行して、候補となる集合を作成する。プランを構成する実際の各処理のことを、オペレータと定義する。オペレータは、例えば、語彙索引検索オペレータや構造照合オペレータなどがある。オペレータは、問合せグラフにおけるノードから別のノードに移動する際に、アークを制約条件としてフィルタリングを実施し、候補集合を作成していくことに対応する。探索途中に、候補集合をできるだけ増やさないように、また、できるだけ重い処理を実行しないようにすることが望ましい。プランとそのプランに含まれるオペレータの例について後に図１４を参照して説明する。

問合せ実行部１１４においては、処理優先度計算部４０６、処理実行部４０７の繰り返しでオペレータを逐次実行していく。プラン作成部４０５が作成したプランの処理が終了した後に結果件数チェック部４０８が結果件数をチェックする。

処理優先度計算部４０６は、各候補を処理する処理コストを事前に見積もる。処理優先度計算部４０６は、最終的なスコア値が低くなることが予測され、かつ、処理コストが重い候補の処理を後に回すことを行なうための処理優先度を計算する。
一般的に、処理コストが高くなる候補、というのは事前に分かる。その顕著な例が構造照合オペレータ内の処理である。この場合、処理優先度計算部４０６は、構造化文書データ記憶部１１８にアクセスし、そこに記憶されている構造情報（親子兄弟関係など）を調査する。先に述べた上流展開はこれら構造照合オペレータのことである。構造照合オペレータには他に後述する下流展開などがある。構造照合オペレータによって、階層が深かったり、巨大文書に対する構造照合を行なう場合の処理コストは高くなることが予想される。

これら重くなる処理を含むオペレータを如何に回避できるかが、問合せプラン作成部１１３において重要になってくるが、プランはあくまで見積もり処理コストを利用しているので、どうしても、全ての候補の処理コストまで見越したものにはならない。そのため、結局は、処理コストの高い処理を実行せざるを得ない場合がある。

本実施形態では、構造化文書に対するスコアリング方式を考えているので、ユーザが所望するのは、スコア値が高いものだけで、スコア値が低いものは、結局は利用されない場合も多い。これを利用して、処理コストが高い候補は処理的に後回しにするという方法が考えられる。
しかし、処理コストが高いことと、その候補がユーザにとって所望するデータであるかどうかは無関係であり、処理コストが高くても上位にスコアリングされて欲しい情報に関しては、先に処理する必要があり、ユーザが所望せず、かつ処理コストが高い候補集合だけを効率良く処理することが重要となってくる。

処理優先度計算部４０６は、各候補を処理する際に、それぞれに対して、処理優先度を計算する。処理優先度は、その処理を実際に実行するために必要と予測される処理コストの大きさに反比例して対応している処理コスト値と、構造スコア値と、語彙スコア値を掛け合わせたものとする。この処理優先度計算方式については、掛け算にこだわらす、「処理コスト値」、「構造スコア値」、「語彙スコア値」の３つをパラメータとして一意に決定される関数としても良い。処理優先度計算部４０６の動作の詳細は後に図１５を参照して説明する。

処理優先度計算部４０６は、語彙索引情報から構造スコア値と語彙スコア値と処理コストとにより逐次的に処理優先度を計算し、処理の途中（最終結果ではないプラン）の段階でその値に従って実行の可否を決定する。

処理実行部４０７は、処理優先度計算部４０６で決定された処理の実行の可否に基づいて、処理優先度の高いものから処理を実行する。
結果件数チェック部４０８は、プラン作成部４０５が作成したプランに応じて、処理優先度計算部４０６と処理実行部４０７を繰り返し実行し、最後のオペレータを実行した後、結果件数をチェックする。結果件数チェック部４０８は、問合せ処理の結果として、ユーザが所望する取得件数以下である場合は、処理していないオペレータから再び処理を再実行することで、結果的に取得所望件数になるまで処理を繰り返し行わせる。処理実行部４０７および結果件数チェック部４０８の具体的な動作については後に図１７を参照して説明する。

次に、オブジェクトツリーと構造雛型木の一例について図５を参照して説明する。
図５の上方に示したツリーがオブジェクトツリー５０１の一例であり、図５の下方に示したツリーが構造雛型木５０２の一例である。構造雛型木照合部３０２は、オブジェクトツリー５０１を走査して、構造情報を抽出する。図５の例では、例えば、オブジェクトツリー５０１には発明者タグが同列で重複する。構造雛型木更新部３０３は、このような重複する構造は一つに集約して特徴的な構造として抽出し、構造雛型木５０２に示すようにそれら構造情報を構造雛型木として作成し、逐次、情報を更新する。なお、構造雛型木５０２に示したＴＩＤ１、ＴＩＤ２、…、ＴＩＤ１０は、構造雛型木識別子の例である。

次に、語彙テーブルの一例について図６を参照して説明する。
語彙テーブルには、語彙索引情報として、ＧＩＤ、テキスト分割部３０５で分割された文字列（Ｇｒａｍ）、データベース中での総発生頻出情報、対応する転置索引リストの格納アドレス（転置索引リスト番号）などの情報を記録している。

次に、語彙テーブルと語彙索引情報の関係について図７を参照して説明する。
語彙テーブルに含まれるＧＩＤごとに、転置索引リストが存在する。転置索引リストは、ＧＩＤごとに総発生頻出情報に記述されている頻度の数だけ語彙索引情報が存在する。図７の例では、ＧＩＤ＝２にはリスト番号３７の転置索引リストが対応していて、この転置索引リストは、頻度６３に対応して６３個の語彙索引情報を含んでいる。

次に、関連語彙計算部３０７が関連ＧＩＤを決定する場合の例について図８を参照して説明する。
関連語彙計算部３０７が＜姓＞鈴木＜／姓＞の文字列ノードに対して索引付けを行なう場合において、最低頻度を仮に３と設定した場合の例を示す。＜姓＞鈴木＜／姓＞の範囲８０６では、テーブル８０１に示すように、「鈴木」の範囲内頻度が１であるので最低頻度３に到達しない。したがって、関連語彙計算部３０７は頻度計算を行う範囲を拡大する。拡大は、まず、「鈴木」の兄弟要素である、＜名＞の文字列をマージした「仮想文字列」を対象として頻度情報を再計算する。この拡大処理を属性、子、兄弟、親の順に繰り返す。図８の例では、関連語彙計算部３０７が頻度を算出する範囲を範囲８０５まで拡大した時点で、＜キーワード＞に含まれる「ＸＭＬ」の頻度をカウントすると、８０７，８０８，８０９の３箇所にＸＭＬが存在しているので、最低閾値である「３」になる。範囲が拡大したこの時点で、テーブル８０１はテーブル８０２のように更新される。この結果、この例の場合は、「鈴木」という語彙は、ＧＩＤ２である「ＸＭＬ」が関連語彙として語彙索引情報に格納されることになる。すなわち、「鈴木」の関連ＧＩＤはＧＩＤ２である。また、「鈴木」の関連ＴＩＤは、「ＸＭＬ」に対するＴＩＤであるので、図５の構造雛型木５０２により、ＴＩＤ５となる。また、例えば、他の文字列よりも先に「ＸＭＬ」が最低頻度に到達した場合に「ＸＭＬ」を「ＸＭＬ」の関連語彙とするのかどうかは設計事項であるので、どちらかに決めておけばよい。

次に、語彙索引情報の一例について図９を参照して説明する。図９は、＜概略＞タグの文字列を分割して得た語彙である「ＸＭＬ」に対する語彙索引情報として、最低頻度を２と設定した場合の例について説明したものである。
この場合は、＜概略＞タグ中には「ＸＭＬ」は２度発生することになる。関連語彙計算部３０７が、この「ＸＭＬ」に対する関連語彙を探す場合、範囲９０４では最低頻度に到達する文字列がないので、範囲を拡大する。関連語彙計算部３０７は、＜タイトル＞まで拡大すると、最低頻度に到達する文字列「文書」、「検索」の２つを探し出すことができる。すると、ＸＭＬの関連語彙は「文書」、「検索」の２つであり、それぞれのＧＩＤはテーブル９０１により「５１」、「８７」と求まる。そして、語彙索引情報は、図９のテーブル９０２に示したように、「文書」、「検索」に対応して２つあり、それぞれ文書ＩＤ、要素ＩＤ、自ＴＩＤ、オフセット、ＧＩＤ、関連ＴＩＤの情報を含んでいる。

次に、問合せ言語構文解析部４０１が作成する問合せグラフ（＝クエリグラフ）について図１０を参照して説明する。
クエリ１００１が検索部１０４から与えられると、問合せ言語構文解析部４０１はクエリ１００１をパージングし、問合せグラフ１００２を得る。図１０の問合せグラフ１００２におけるノードが候補集合、アークが制約条件に対応し、例えば、丸２と丸３は構造制約条件／タイトルという制約条件があり、丸３と丸４はｃｏｎｔａｉｎｓ（ｔｅｘｔ（），”構造化文書”）という語彙と構造に関する制約条件があることを示している。

このような問合せグラフ１００２を作成するクエリの最適化の手法によって、構造化文書検索装置がこれらノードを如何に効率良く探索することができるかが決まる。例えば、ｃｏｎｔａｉｎｓ（ｔｅｘｔ（），”構造化文書”）では、「構造化文書」を含む文字列集合は、予め格納時に索引付けされているので、この索引を先に利用すること、つまり、丸４から丸３へ辿るようにプランを作成することで処理の高速化が可能となる。逆に、丸３から丸４に辿る場合は、ＸＭＬ文書をルートから順に構造照合しながら検索することになり、構造化文書検索装置は処理コストが重い、と判断したりする。ここで、下流から上流へ辿って候補を絞り込むことを上流展開、上流から下流に辿って候補を絞り込むことを下流展開と定義する。例えば、丸４から丸３へ辿って候補を絞り込むことは上流展開であり、丸３から丸４に辿って候補を絞り込みことは下流展開である。

このように、問合せ言語構文解析部４０１は、問合せプラン作成部１１３がクエリのプラン作成を行なう際に必要となる、問合せデータに含まれている要素間の制約関係を作成する。

次に、構造制約条件作成部４０２の動作について図１０を参照して説明する。
丸２と丸３の構造制約は、図１０の構造雛型木１００３では、それぞれＴＩＤ４とＴＩＤ６に対応する。構造制約条件作成部４０２は、これらをペアとして、［ＴＩＤ４，ＴＩＤ６］をこの丸２と丸３の構造制約として保持しておく。このように、構造制約の親子関係を求めておくことで、構造制約によって、候補となる件数を早期に絞り込むことが可能となる。

なお、構造化文書検索装置が丸２から丸３へ探索を行なう場合（下流展開）、処理優先度計算部４０６が各候補に対して構造化文書データ記憶部１１８にアクセスして、それぞれの子要素を取得し、取得した要素のＴＩＤの値と、子ＴＩＤ制約であるＴＩＤ値を比較して、異なる場合は、その時点で候補から外すという処理を行なう。逆に、構造化文書検索装置が丸３から丸２へ探索を行なう場合（上流展開）は、処理優先度計算部４０６が各候補に対して親要素を取得し、親ＴＩＤ制約の値と比較するという処理を行なう。同様に、ＩＤ属性（／＠ｉｄと表記する）に対しては、［ＴＩＤ４，ＴＩＤ５］が事前に解析される。

次に、クエリの一例について図１１を参照して説明する。
ＸＱｕｅｒｙに代表される、加工型問合せ言語においては、Ｒｅｔｕｒｎ節には、データベース上には実際に存在しない、仮想的な要素、属性、文字列などを記述することが可能である。図１１のクエリでは、＜ｂｏｏｋＬｉｓｔ＞，＜著者＞，＜名前＞や／ｂｏｏｋＬｉｓｔ／著者／名前を持つ構造などは、ユーザがクエリで自由に記述したものであり、データベース上に存在しない仮想データである。また、Ｒｅｔｕｒｎ節中の、＄ｘと＄ｙなどの仮想的な構造関係などもデータベース上にはないため、＄ｘが最終的に出力する＜ｂｏｏｋ＞タグと、＄ｙが最終的に出力する＜ｐａｐｅｒ＞タグの関係もデータベース中には存在しない。

しかしながら、これら複合文書によって最終的に作成されるデータ構造は、ユーザが欲しい情報に対する一つの意思表示である。例えば、＜ｔｉｔｌｅＬｉｓｔ＞で結果を纏め上げたとした場合は、その中身としては、＜ｔｉｔｌｅＬｉｓｔ＞に関連するような内容であることをユーザは期待している。これら内容に類似するものを、スコア値として高く設定することによって、精度の高い情報を速く提示できるようになる。

次に、意味ネットワーク記憶部１２２の内容の一例について図１２を参照して説明する。
意味ネットワークは、単語と、この単語に関連する単語とを類似度付きで関連付けたものである。意味ネットワークは、語彙の間の類似関係をグラフで表現したものであり、類似関係のある語彙と語彙をアークで結び、その語彙間の類似度の値をアークに与えて、語彙間のネットワークを構成しているものである。図１２の例では、例えば、「構造化文書」は、「構造文書」、「ＸＭＬ」、「ＳＧＭＬ」とそれぞれ類似度０．５、類似度０．８、類似度０．８で関連づけられている。

次に、類似構造検索部４０３が構造スコア値を求める場合について図１３を参照して具体的に説明する。図１３の例では、構造化文書のＸＭＬデータ１３０１が既にデータベースに格納されている状況を考える。この場合、構造雛型木を図１３に示した第１構造雛型木１３０８とする。類似構造検索部４０３は、第１クエリ１３０４を処理する場合には、まず、Ｒｅｔｕｒｎ節に記述された＜ＴｉｔｌｅＬｉｓｔ＞タグと、＄ｘが最終的に出力する＜ｎａｍｅ＞タグで構成される複合文書の構造に類似する構造を構造雛型木上から検索する。この際に、類似構造検索部４０３は意味ネットワークを用いて、タグ名に対する揺らぎを吸収した形で検索を行なう。

この場合、類似構造検索部４０３は、意味ネットワーク１３０９上に、ＴｉｔｌｅＬｉｓｔとｔｉｔｌｅが類似度０．５の関係があるとすれば、＜ｔｉｔｌｅＬｉｓｔ＞＜ｎａｍｅ＞の関係と、＜ｔｉｔｌｅ＞＜ｎａｍｅ＞の関係（／ｔｉｔｌｅ／ｎａｍｅ）が類似度０．５であると見なす。ここで、／ｔｉｔｌｅ／ｎａｍｅの関係は第１構造雛型木１３０８上では、ＴＩＤ２，ＴＩＤ３に相当するので、類似構造検索部４０３はこれらのＴＩＤを持つ候補の構造スコア値を高く設定する。第１構造雛型木１３０８上で、＜ｎａｍｅ＞を表す構造として、ＴＩＤ６もあるが、こちらは、＜ａｕｔｈｏｒ＞タグの＜ｎａｍｅ＞（／ａｕｔｈｏｒｓ／ａｕｔｈｏｒ／ｎａｍｅ）でありので、類似構造検索部４０３はこちらの優先度を低くする。

この場合は、類似構造検索部４０３は、例えば、ＴＩＤ３に対しては構造スコア値＝０．５，ＴＩＤ６に対しては構造スコア値＝０．１とする。ここで、ＴＩＤ６のように、類似度がないと判定されたＴＩＤに対してスコア値を０としなかったのは、スコア計算を行なう際に、構造スコア値と掛け算をとる場合があるため、この値を０ではないできるだけ小さい値とした。

なお、構造制約計算時に、＄ｘの構造制約は、［ＴＩＤ１，ＴＩＤ３］及び、［ＴＩＤ１，ＴＩＤ６］である。この制約において、ＴＩＤ３の制約に合致する候補のスコア値を高く設定するので、出力結果としては、＄ｘの構造制約である、ＴＩＤ３＜ｎａｍｅ＞ＴａｎａｋａＴｈｅｏｒｙ＜／ｎａｍｅ＞のほうが先に表示される。

問合せ実行部１１４で実行されるプランとこのプランに含まれるオペレータの例について図１４を参照して説明する。
図１４の第１プラン１４０１は、語彙索引検索オペレータ、構造照合オペレータ、結果生成オペレータという３つのオペレータから構成されるプランの例である。なお、このプランは、一般的な検索パターンの基礎として最も実施されるプランである。プラン作成部４０５は第２プラン１４０２のような別のプランも作成するが、問合せ実行部１１４はこの中で最も処理コストが低いプランである第１プラン１４０１を選択して実行する。

次に、処理優先度計算部４０６の動作について図１５を参照して説明する。
まず、図４などを参照して上述したように、構造照合する場合の処理コストなどの処理コスト値を計算する（ステップＳ１５０１）。この処理コスト値として、［０：１］で正規化した値を用いて処理コストを計算する。例えば、照合のための階層が深い場合や、文書サイズが大きい場合などは、処理コストは高くなると予想され、処理コストが高いほど、処理コスト値は低くなるように処理コスト値を設定する。

構造コストの計算をする（ステップＳ１５０２）。具体的には構造スコア値を計算する。構造スコア値は、類似構造検索部４０３が求め、求め方の詳細は図１３を参照して上述した。

次に、複数の語彙索引検索オペレータが、既に処理した候補集合を得ているか否かを判定する（ステップＳ１５０３）。例えば、語彙索引検索オペレータなど、語彙索引情報を用いる場合は、入力となる候補集合が存在しない。この候補集合がある場合にはステップＳ１５０４に進み、この候補集合がない場合にはステップＳ１５０５に進む。

次に、複数の語彙索引検索オペレータを用いた結果をマージする処理（すなわち、結合処理）を行なう必要があるか否かを判定する（ステップＳ１５０４）。複数の語彙索引検索オペレータを用いた結果をマージする場合というのは、図１１に示した例のような、２つ以上のキーワード（この例では「ＸＭＬ」と「田中」）を条件にした検索をａｎｄで結合するような場合であり、一般的に良く使われるクエリの一つである。結合処理を行う必要がある場合にはステップＳ１５０６に進み、結合処理を行う必要がない場合にはステップＳ１５０５に進む。

ステップＳ１５０５では、語彙コストの計算をせずに、処理コストと構造コストの計算結果のみを処理優先度計算に使用することに決め、ステップＳ１５０７に進む。

ステップＳ１５０７では、処理コスト値と、構造スコア値と、語彙スコア値に基づいて、処理優先度を計算する。例えば、処理コスト値と、構造スコア値と、語彙スコア値を掛け合わせたものを処理優先度とする。語彙スコア値を計算しない場合は、処理コスト値と、構造スコア値とのみに基づいて、処理優先度を計算する。この場合は例えば、処理コスト値と、構造スコア値とを掛け合わせたものを処理優先度とする。

ステップＳ１５０６では、語彙コストを計算する。具体的には語彙スコア値を計算する。この場合は、図１５の条件を通過しているので、対象として必ず２つ以上の語彙索引検索オペレータを実行した候補集合が存在する。

本実施形態では、統計情報計算部１０８が語彙索引を作成する際に、関連度の高いＧＩＤ（関連ＧＩＤ）と、そのＧＩＤが最も多く発生する構造のＴＩＤ（関連ＴＩＤ）を算出し、索引情報格納部１０９が関連ＧＩＤと関連ＴＩＤを語彙索引記憶部１１９に記憶させてある。語彙スコア値を計算する際に、２つ以上の候補集合内で共通する関連ＧＩＤと関連ＴＩＤが存在するような候補が存在すれば、その候補に対してはスコア値を高く設定する。この際に、関連ＧＩＤや関連ＴＩＤなどは意味ネットワークを用いて展開して、類似度を含ませても良い。

次に、語彙スコア値を求める場合の具体的な例について図１６を参照して説明する。
図１６の例は、語彙索引検索オペレータに候補集合リストより生成された候補集合が２つあり、これらに対して語彙スコア値を求める場合である。第１候補集合リストにおける候補１６０１においては、関連ＧＩＤ＝５，関連ＴＩＤ＝７に関しては第２候補集合リストに完全に共通に存在するので、これらに対する語彙スコア値は高く設定する。この例では語彙スコア値は１．０に設定されている。

候補１６０２においては、ＧＩＤ＝５だけ一致するが、関連ＴＩＤ＝２であり、この部分は一致しない。よって、候補１６０１よりは語彙スコア値を低く設定する。この例では語彙スコア値は０．５に設定されている。候補１６０３においては、関連ＧＩＤすら一致しないので、さらに低い語彙スコア値を設定する。この例では語彙スコア値は０．１に設定されている。同様に、候補集合リスト２についても実施する。ここでは、候補１６０１の語彙スコアを１．０、候補１６０２の語彙スコアを０．５、候補１６０３の語彙スコア値を０．１と設定したが、これらの計算手法は、関連ＧＩＤ，関連ＴＩＤをパラメータとして算出することが重要であって、他の手法を用いても良い。

意味ネットワークを用いた場合は、関連ＧＩＤに対応する語彙を展開した語彙に関して同様に、２つの候補集合間で存在するならば、その類似度とともに、語彙スコア値に反映させても良い。以上で、処理優先度を求めるために必要な情報が揃ったことになる。これらを基に処理優先度を計算し（ステップＳ１５０７）、処理実行の有無を決定する。

次に、処理実行部４０７および結果件数チェック部４０８の具体的な動作について図１７を参照して説明する。
図１７は、処理の優先度に従った、処理手順を表したものである。この場合は、５つの候補集合に関して、処理優先度計算部４０６がそれぞれ処理優先度を求め、優先度が高い２つの候補を優先的に処理することで高速化を計っている。この例では、処理優先度計算部４０６が得るテーブル１７０３に示したように、第２候補１７０４と第５候補１７０５の優先度が高い。

図１７に示したように、プラン１７０２に応じて、処理優先度計算部４０６と処理実行部４０７を繰り返し実行し、最後のオペレータを実行した後、結果件数チェック部４０８において、結果件数をチェックする。結果件数チェック部４０８は、問合せ処理の結果として、ユーザが所望する取得件数以下であるかどうかを判定して、取得件数以下である場合は、処理実行部４０７が処理していないオペレータから再び処理を再実行することで、結果的に取得所望件数になるまで繰り返す。

次に、構造化文書記憶装置と構造化文書検索装置の具体例について説明する。

以下では、図１８に示すように、構造化文書記憶装置が３つの登録文書（第１文書１８０２，第２文書１８０３，第３文書１８０４）を記憶していて、構造化文書検索装置は、クエリとして、ＸＱｕｅｒｙ（クエリＡ１８０１）を入力するとする。

（構造化文書記憶装置の具体例）
まず、第１文書１８０２を登録する場合について説明する。
まず、構造情報抽出部１０７の処理から始まる。構造化文書構文解析部３０１が第１文書１８０２の文書構造を解析した後、構造雛型木照合部３０２が構造雛型木記憶部１２０を参照して構造雛型木を照合する。構造化文書構文解析部３０１は、解析を行なったオブジェクトツリーの各ノードに対して、対応するＴＩＤの情報を付加し、構造化文書データ記憶部１１８にこれらデータを格納する。この際に、文書ＩＤや要素ＩＤなどもシステムが発行されるが、ここでは文書ＩＤ＝３とする。構造雛型木記憶部１２０に既に図１９に示す構造雛型木１９０１があるとすると、構造雛型木照合部３０２がＴＩＤ３を基点して構造情報を重ね合わせると、全ての構造が重なりあう形になることがわかる。したがって、この例では、新たに構造雛型木におけるノードが増えることはないので、構造雛型木更新部３０３が構造雛型木を新たに更新する必要はない。

次に、統計情報計算部１０８の処理に移る。テキスト分割部３０５が各ノードの文字列を分割して索引付けを行なう。ここの例として、＜姓＞の文字列「田中」について索引付けを行なう場合について図２０を参照して説明する。

テキスト分割部３０５が、文字列を、オブジェクトツリー上の、文字列に対応する部分の語彙に分割し、語彙識別子特定部３０６が、語彙識別子としては、その語彙が発生した文書ＩＤ、要素ＩＤ、発生位置である位置情報、その要素に対応するＴＩＤ（自ＴＩＤ）を求め、関連語彙計算部３０７が関連ＧＩＤを求める。ここでは、最低発生頻度として４が予め設定されていると仮定して話を進める。＜姓＞の文字列値には、「田中」という文字しか存在しないので、基点となる＜姓＞の部分の兄弟要素である、次郎に対する頻度情報も併せて考える。この段階でも最大頻度を持つ語彙が、最低発生頻度の４に到達していないことから、探索範囲を親要素まで拡大し、＜発明者＞に対しても同様の処理を行なう。これを繰り返し、／タイトル／名，／概略，キーワードリスト／キーワードと要素内の文字列を順に頻度をカウントしていく。

キーワードリスト／キーワードの時点で、図２０のテーブル２００１のＸＭＬの項目２００２に示したように、「ＸＭＬ」という語彙の頻度が４回に到達するので、これを「田中」という語彙に対する関連ＧＩＤとする。関連ＴＩＤは、このＧＩＤが最も発生する要素、この例では、＜概略＞タグに対応するＴＩＤ１５とする。このようにして、統計情報計算部１０８は、図２０の語彙索引情報２００３を得る。同様に、＜概略＞文字列における、「ＸＭＬ」に対する索引付けの例も図２０に示してある。この場合は、語彙索引情報は語彙索引情報２００６と語彙索引情報２００７の２つになる。

この段階で語彙索引情報を全て求めたので、これらを語彙索引情報として、語彙索引記憶部１１９に格納する。なお、新規に発生した語彙であるならば、改めて転置索引リストを作成することになる。

同様の手順で、論文一式（ＴＩＤ１８）の下に、第３文書１８０４を登録した場合の、構造情報を図２１に示す。すなわち、構造化文書構文解析部３０１が第３文書１８０４の文書構造を解析した後、構造雛型木照合部３０２が構造雛型木記憶部１２０を参照して構造雛型木を照合する。構造化文書構文解析部３０１は、解析を行なったオブジェクトツリーの各ノードに対して、対応するＴＩＤの情報を付加し、構造化文書データ記憶部１１８にこれらデータを格納する。構造雛型木記憶部１２０に図２１の右側に示す構造雛型木（ＴＩＤ１９の＜論文＞以下の構造雛型木）がないとすると、新たに構造情報が発生したと見なせるので、構造雛型木更新部３０３は＜詳細情報＞以下の構造を改めて構造雛型木を更新する。

（構造化文書検索装置の具体例）
検索する問合せ言語（クエリ）は、図１８に示したクエリＡである。まず、問合せ解析部１１２の処理から始まる。問合せ言語構文解析部４０１が問合せ構文解析を行い、クエリを構文解析し、問合せグラフを作成する。この例では、問合せ言語構文解析部４０１は図２２に示す問合せグラフ２２０１を作成する。

次に、構造制約条件作成部４０２が構造制約条件を求める。この例では、＄ｘに関しては／／名／ｔｅｘｔ（）の制約が付加されているので、これを構造雛型木から合致する構造情報を検索する。図１９の構造雛型木１９０１を参照すれば、［ＴＩＤ６，ＴＩＤ７］と［ＴＩＤ１２，ＴＩＤ１３］の２つがこれらの制約にあたることがわかる。

次に、類似構造検索部４０３が構造スコア値を計算する。まず出力となる、Ｒｅｔｕｒｎ節に着目する。図１８のクエリＡ１８０１を参照する。「著者リスト」はデータベース上に実データとして存在しないタグ名であるが、この例では、類似構造検索部４０３が意味ネットワーク記憶部１２２を検索して、図２３のように、「著者リスト」は「発明者」と類似度０．８と合致することが分かる。つまり、＄ｘに着目すると、／特許／発明者リスト／発明者／名という構造が、「著者リスト」に関与する構造と高い類似度を持つ。よって、構造雛型木上で、／特許／発明者リスト／発明者／名に類似する構造を検索した場合、ＴＩＤ１３が相当するために、これを類似構造として、この類似度０．８をＴＩＤ１３の構造スコア値の基準値とする。

先ほど求めた構造制約条件として、［ＴＩＤ１２，ＴＩＤ１３］と［ＴＩＤ６，ＴＩＤ７］とを求めたが、最初のほうのＴＩＤ１３がこの場合に合致するので、［ＴＩＤ１２，ＴＩＤ１３］に関しては先ほど求めた類似度０．８を構造スコア値とする。類似構造検索部４０３は、［ＴＩＤ６，ＴＩＤ７］に関しては類似度からは判別できないので、この場合は構造スコア値を低く設定する。ここでは、構造スコア値は０．５としておく。構造スコア値は、一致しない場合でも０としないのは、今回は処理優先度を「処理コスト値×構造スコア値×語彙スコア値」という風に掛け算で設定したからで、例えば、語彙スコアなどの値を有効するためにも０でない値を設定しておく。以上より、この場合、ＴＩＤ１３の構造スコア値は０．８，ＴＩＤ７の構造スコア値は０．５となる。

次に、クエリ処理コスト見積もり部４０４において、処理コスト値計算を行い、プラン作成部４０５が最適なプランを作成する。ここでは、プラン作成部４０５が作成した検索プランを図２４に示す。このプランでは、図２４に示したオペレータ番号２４０１〜２４０６までをこの順にオペレータ処理を実行していく。＄ｘ（田中）、＄ｙ（一郎）ごとに語彙索引検索オペレータを実行し（２４０１、２４０２）、その後、それぞれ上流展開オペレータにより構造照合を行なった上（２４０３、２４０４）で、それぞれの結果を結合する結果結合オペレータを実施し（２４０５）、最終的な結果を生成する結果生成オペレータを行う（２４０６）、というのがプランの一連の流れである。ここまでで問合せプラン作成部１１３がプランまで作成したので、このプランに従って、問合せ実行部１１４が実際の処理（オペレータ）を実行する。

以下、処理実行部４０７が行う各オペレータの処理について説明する。まず、「田中」を含む語彙索引検索オペレータについて説明する。語彙索引検索オペレータは、「田中」などの語彙をキーとして、合致する語彙索引情報を転置索引リスト上から検索する、という手順を行う。この際に、予め構造制約として付加したＴＩＤ情報と、問合せ解析部１１２で求めた構造制約から得た構造制約情報とを比較して、ＴＩＤが合致しない候補集合を省く、といった処理を行なう。

上述したように構造制約条件作成部４０２が求めた構造制約条件により、＄ｘの制約に関しては、ＴＩＤの集合として、［ＴＩＤ６，ＴＩＤ７］と［ＴＩＤ１２，ＴＩＤ１３］がある。後に上流展開を行なうので、必要な構造制約は、ペアの後者のほうであり、この場合は、｛ＴＩＤ７，ＴＩＤ１３｝である。

図２５に示した例では、第１候補２５０１はクエリから得た構造制約情報に一致するものがないので、この段階で候補から省く（フィルタリングと呼ぶ）が、第２候補２５０２に関してはＴＩＤ７が構造制約条件として一致するので、この値は候補として残す。他に残る候補は、ＴＩＤ１３を語彙索引情報として有する第３候補２５０３だけである。すなわち、「田中」の語彙索引として、５件の語彙索引情報がリスト上に存在するが、このうち、｛ＴＩＤ７，ＴＩＤ１３｝に合致する、第２候補及び第３候補だけが候補として残る。

最初に行う語彙索引検索オペレータでは、図１５のフローチャートにしたがうとステップＳ１５０３で「ＮＯ」となるので語彙スコア値は考慮する必要はない。語彙スコア値を計算する必要があるオペレータは、上流展開オペレータや、下流展開オペレータなど、既に候補集合がある場合に、次の候補集合に移る場合にのみに計算する必要がある場合がある。

＄ｙの語彙索引検索オペレータについても同様である。この場合の構造制約は、上述した＄ｘの場合と同様に計算すると、図２１の２１０２、２１０３に対応して｛ＴＩＤ２６，ＴＩＤ３７｝となる。図２６に示すように、この場合は、転置索引リスト上には５つの候補が存在するが、全ての候補が、構造制約を満たすので、全ての候補を候補として残す。

次に、上流展開オペレータの処理について説明する。上流展開オペレータは、前候補集合が存在するので、各候補に対して語彙スコア値を計算した上で、処理優先度の計算を行い、優先度の高い所定数の候補を優先的に処理する。

図２５では、第２候補と第３候補の２件の候補が残っているが、この２件に対して、上流展開を実施するかどうかを決定する。処理優先度を求めるために既に類似構造検索部４０３で得られている構造スコア値を参照する。構造スコア値は、図２５の例では、２番目の候補はＴＩＤ７であり、この候補に対する構造スコア値は０．５（デフォルト値）である。３番目の候補はＴＩＤ１３であり、この候補に対する構造スコア値は０．８である。

図２４に示した上流展開オペレータ２４０４についての構造スコア値を説明の都合上先に行なう。この場合は、構造制約として、｛ＴＩＤ２６，ＴＩＤ３７｝が得られるが、いずれも、類似構造検索部４０３で求めたＴＩＤと合致しないので、デフォルト値である０．５を構造スコア値とする。

次に、個別の処理コスト値を求める。処理コスト値の求め方は、オペレータごとに様々な計算方法があっても良い。ここでは、各候補に対して、２番目のオペレータである上流展開の処理コスト値を考慮して計算する。この場合に、候補が持っているＴＩＤと構造雛型木上のＴＩＤを比較して、構造化文書データ記憶部１１８に実際にアクセスして構造情報を照合しなくても、構造雛型木記憶部１２０に記憶されている構造雛型木と照合して、おおよそにかかる処理時間を見積もることができる。構造照合オペレータの場合は、処理コスト値＝１／（構造照合を行なう段数）で見積もる。

図２５の候補集合より、１番目の候補の構造情報はＴＩＤ７であり、この構造制約は、［ＴＩＤ６，ＴＩＤ７］である。つまり、ＴＩＤ７から上流展開して、ＴＩＤ６に合致するような構造照合処理を行なう、ということである。構造雛型木上で、これらＴＩＤ６とＴＩＤ７の段数は１段であるので、この場合の処理コスト値は１／１＝１となる。２番目の候補（構造情報がＴＩＤ１３）も同様に処理コスト値は１となる。

図２４の上流展開オペレータ２４０４の場合は、構造制約が｛ＴＩＤ２６，ＴＩＤ３７｝であるので、これらに対応する構造雛型木上のノードから、｛ＴＩＤ２５，ＴＩＤ３５｝に到達するまでの処理コスト値を構造雛型木上で計算する。この場合、図２７に示したように、ＴＩＤ２６に関しては１段、ＴＩＤ３５に関しては２段必要なので、ＴＩＤ２６に対する処理コスト値として１／１＝１を、ＴＩＤ３５に対する処理コスト値としては、１／２＝０．５として計算する。

次に、語彙スコア値を求める。図１５より、語彙スコア値を求めるためには、ステップＳ１５０４の語彙索引検索オペレータ同士の結合処理が行なわれること、が条件となる。図２４の例では、結果結合オペレータ２４０５がそれにあたるので、この段階で語彙スコア値を計算する。この際に、格納時に索引に付加しておいた、関連語彙ＧＩＤと関連ＴＩＤを用いる。
図２８は、上流展開オペレータを行なう際の候補集合である。上述したように、図２４の語彙索引検索オペレータ２４０１から２つの候補が、語彙索引検索オペレータ２４０２から５つの候補が発生しており、これらをまとめて語彙索引情報および処理コスト値、構造スコア値、以下で求める語彙スコア値、これらの値から求まる処理優先度を示したものが図２８である。なお、これまでの説明において、処理コスト値及び構造スコア値は既に求まっており、現時点は語彙スコア値を計算する段階である。

ここでは、２つのリスト間で＜関連ＧＩＤ，関連ＴＩＤ＞が共通するものがあるかどうかを照合する。共通するものがあった場合は、語彙スコア値を高く、そうでなければ語彙スコア値を低く設定する。この際に、関連ＧＩＤや関連ＴＩＤなどに対しても、意味ネットワークによりＮ段展開しておく（類義語展開と呼ぶ）ことで、厳密ではなく、曖昧性を残した形で検索することが可能となる。ここでは、Ｎ＝１とした１段展開までを行なうことにする。

語彙スコア値はここでは以下のルールに従って設定することにする。
Ａ．関連ＧＩＤ，関連ＴＩＤが共に一致するようであれば語彙スコア値を１に設定
Ｂ．関連ＧＩＤ，関連ＴＩＤがどちらも一致しないようであれば語彙スコア値を０．５に設定
Ｃ．関連ＧＩＤだけ一致し、関連ＴＩＤが異なるものがあれば、語彙スコア値を０．６に設定
Ｄ．関連ＧＩＤ，関連ＴＩＤがそれぞれ類義語展開によって展開された値によって一致した場合は、その類似度を語彙スコア値とする。ただし、この場合の語彙スコア値は、Ｃ．の語彙スコア値０．６を下回った場合は０．５を下限値とする。

語彙スコア値を求める一例として図２８の第４候補２６０２について考察する。この場合は、関連ＧＩＤ＝２、関連ＴＩＤ＝２９である。関連ＧＩＤ＝２，関連ＴＩＤ＝２９に完全に合致するものは＄ｘの候補集合中には存在しないが、図２１を参照するとこの関連ＴＩＤは「概要」というタグ名に対応することがわかる。図２９の意味ネットワークを参照すれば、「概要」は「概略」という名称と類似度０．８で合致する。よって、ここでは、類似度展開は０．８となり、これを語彙スコア値とする。

次に、第５候補２６０３の場合を考える。この場合は、関連ＧＩＤ＝２，関連ＴＩＤ＝１２である。関連ＴＩＤに関しては１段だけ意味ネットワークを展開しても合致するものがないので、類義語展開によって語彙スコア値は決定されない。関連ＧＩＤだけが一致するので、この場合は、０．６という語彙スコア値を与える。
また、第６候補の場合は、関連ＧＩＤ及び関連ＴＩＤともに合致するものが無いので、０．５を語彙スコアとして設定する。
以上のような語彙スコア値の求め方は、語彙スコア値に依存してこれら候補の優劣を付けることができればよく、その値をどう設定するかは様々な方法がある。

このように、処理優先度計算部４０６が候補集合となる両者のリストの関連ＧＩＤ，関連ＴＩＤを比較しつつ、各候補に対して語彙スコア値を設定していく。処理コスト、構造スコア値、語彙スコア値が求まれば、処理優先度計算部４０６はそれらを掛け合わせて、最終的な処理優先度を計算する。これらも図２８に示した。ここで、件数として、上位２件ずつ選択した場合は、処理優先度計算部４０６は＄ｘに関する候補集合からは第１候補及び第２候補を、＄ｙに関しては第４候補及び第６候補を候補として選択する。そして、処理実行部４０７がこれらの選択された候補を先に処理する。

処理優先度を求めた後、選択された候補に対してだけ実際の上流展開処理を行なう。この場合は、＄ｘに関する候補集合からは、第１候補及び第２候補を、＄ｙに関しては、第４候補及び第６候補が処理優先度として高いので、これら候補に対して先に構造照合処理を実行する。最後に結果結合オペレータにおいて、｛第１候補，第２候補｝の候補集合と、｛第４候補，第５候補｝の候補集合について結合処理を行なう。先ほどまでの処理でスコア値が低くなると予想される候補を除いているので結合処理コストも従来に比べて削減できる。

以上のオペレータの実行処理によって得られる検索結果の例について図３０を参照して説明する。図３０の例では、検索結果３００１として３件を表示している。このように、＜Ｒｅｔｕｒｎ＞節の中に複数の変数を記述し、複合文書を作成する場合にも適切なスコアリングが行なうことが可能となり、かつ、スコア値が低く処理コストが高い候補の処理を後回しにすることで、高速性も維持することができる。

また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の構造化文書記憶装置、構造化文書検索装置、および構造化文書システムによる効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、又はこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の構造化文書記憶装置、構造化文書検索装置、および構造化文書システムと同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合又は読み込む場合はネットワークを通じて取得又は読み込んでもよい。
また、記憶媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーションシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
さらに、本願発明における記憶媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
また、記憶媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記憶媒体に含まれ、媒体の構成は何れの構成であってもよい。

なお、本願発明におけるコンピュータまたは組み込みシステムは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。

なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。

本発明の実施形態に係る構造化文書記憶装置および構造化文書検索装置のブロック図。構造化文書データの一例を示した図。図１の格納処理部のブロック図。図１の検索処理部のブロック図。オブジェクトツリーと構造雛型木の一例を示す図。語彙テーブルを示す図。語彙テーブル、転置索引リスト、語彙索引情報の関係を示した図図３の関連語彙計算部が関連ＧＩＤと関連ＴＩＤを求めることを説明するための図語彙索引情報の一例を示す図。図４の問合せ言語構文解析部が作成する問合せグラフを説明するための図。図１の検索処理部が受け付ける、複数文書から構成されるＸＱｕｅｒｙの一例を示す図。図１の意味ネットワーク記憶部の内容を示す図。図４の類似構造検索部が構造スコア値を求める手法を示す図。図１の問合せ実行部が実行する問合せ処理プランの一例を示す図。図４の処理優先度計算部の動作の一例を示すフローチャート。図４の処理優先度計算部が求める語彙スコア値を求める手法を説明するための図。図４の処理実行部および結果件数チェック部の動作の一例を説明するための図。図１の構造化文書記憶装置が記憶している文書の一例と、図１の構造化文書検索装置が受け付けるＸＱｕｅｒｙの一例を示す図。図１８の例に対する構造雛型木を示す図。索引付けの具体的な手法の一例を説明するための図。図１９の構造雛型木に新たな構造雛型木を追加する場合を示す図。図１８のＸＱｕｅｒｙに対する問合せグラフを示す図。図１８の例に対して設定されている意味ネットワークを示す図。図１８のＸＱｕｅｒｙに対するプランの概要を示す図。＄ｘに関する転置索引リスト集合に含まれる複数の候補を示す図。＄ｙに関する転置索引リスト集合に含まれる複数の候補を示す図。構造照合における処理コスト見積もりを説明するための一例を示す図。処理優先度を説明するための図＄ｘ，＄ｙの語彙スコア値に対する処理方法を説明するための図。スコアリングを考慮した検索結果を示す図。

符号の説明

１０１，１０２…入力部、１０３…登録部、１０４…検索部、１０５…要求処理部、１０６…格納処理部、１０７…構造情報抽出部、１０８…統計情報計算部、１０９…索引情報格納部、１１０…制御部、１１１…検索処理部、１１２…問合せ解析部、１１３…問合せプラン作成部、１１４…問合せ実行部、１１５…結果生成部、１１６…制御部、１１７…データベース、１１８…構造化文書データ記憶部、１１９…語彙索引記憶部、１２０…構造雛型木記憶部、１２１…語彙統計情報記憶部、１２２…意味ネットワーク記憶部、３０１…構造化文書構文解析部、３０２…構造雛型木照合部、３０３…構造雛型木更新部、３０４…構造化文書データ格納部、３０５…テキスト分割部、０６…語彙識別子特定部、３０７…関連語彙計算部、４０１…問合せ言語構文解析部、４０２…構造制約条件作成部、４０３…類似構造検索部、４０４…クエリ処理コスト見積もり部、４０５…プラン作成部、４０６…処理優先度計算部、４０７…処理実行部、４０８…結果件数チェック部、５０１…オブジェクトツリー、５０２、１００３、１３０８、１９０１…構造雛型木、１００１…クエリ、１００２…問合せグラフ、１３０１…ＸＭＬデータ、１３０４…第１クエリ、１３０９…意味ネットワーク、１４０１…第１プラン、１４０２…第２プラン、２００３、２００６、２００７…語彙索引情報、２４０１、２４０２…語彙索引検索オペレータ、２４０４…上流展開オペレータ、２４０５…結果結合オペレータ

Claims

１つの構造化文書を取得する取得手段と、
前記構造化文書を解析する構造情報解析手段と、
構造化文書の典型的な構造を示す構造雛型木を予め記憶している構造雛型木記憶手段と、
前記構造雛型木を前記解析された構造化文書に合致するように更新する更新手段と、
前記１つの構造化文書を複数の語彙に分割する分割手段と、
前記１つの構造化文書内の要素ごとに該要素内に存在する全ての語彙に対して語彙ごとに該語彙が発生する頻度を示す発生頻度情報を算出する頻度情報算出手段と、
前記語彙ごとに該語彙を含む範囲内で或る出現回数以上の他の語彙が存在するまで前記範囲を拡大する拡大手段と、
前記拡大された範囲内で最も出現回数が多い語彙の語彙識別子を前記語彙の関連語彙識別子として付与する関連語彙識別子付与手段と、
前記語彙ごとに前記関連語彙識別子を記憶している関連語彙識別子記憶手段と、
前記構造雛型木の各ノードに構造雛型木識別子を付与する構造雛型木識別子付与手段と、
或る語彙の関連語彙識別子が最も多く発生するノードの構造雛型木識別子を該或る語彙の関連構造雛型木識別子として付与する関連構造雛型木識別子付与手段と、
前記語彙ごとに関連構造雛型木識別子を記憶している関連構造雛型木識別子記憶手段と、を具備することを特徴とする構造化文書記憶装置。
前記解析された構造化文書に基づいて、該構造化文書の構造を抽出する抽出する抽出手段と、
前記抽出された構造を構造雛型木として前記構造雛型木記憶部に記憶させる記憶手段と、をさらに具備することを特徴とする請求項１に記載の構造化文書記憶装置。
前記拡大手段は、前記語彙の位置を基点として属性、子要素、兄弟要素、親要素の順に、前記範囲を拡大することを特徴とする請求項１または請求項２に記載の構造化文書記憶装置。
請求項１に記載の構造化文書記憶装置を参照する構造化文書検索装置であって、
複数の構造化文書の部分構造から構成される新たな複合文書を生成するための問合せ言語で記述された問合せデータを受け付ける受付手段と、
前記問合せデータを構文解析する構文解析手段と、
前記構文解析された問合せデータに含まれる、問合せの回答として要求される要求構造に類似する類似構造を持つ、構造雛型木に含まれるノードを前記構造化文書記憶装置から複数の候補として選択する選択手段と、
語彙の間の類似度合いを示す類似度を複数の語彙について記憶している類似関係記憶手段と、
前記類似度に基づいて、前記候補ごとに該候補が前記要求構造に類似している度合いを示す構造スコア値を算出する構造スコア値算出手段と、
少なくとも、前記候補と前記構造雛型木とを照合することに基づいて、どの順番で各候補を処理するかを示す各候補の処理コストを算出する処理コスト算出手段と、
少なくとも前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出し、該処理優先度の高い候補から順に、処理を行う選択候補として選択する処理優先度算出手段と、
前記選択候補から処理を実行する処理実行手段と、
複数の前記処理を実行した実行結果を検索結果として取得する結果取得手段と、を具備することを特徴とする構造化文書検索装置。
前記構文解析手段は、前記問合せデータの構造情報を作成し、
前記選択手段は、前記構造情報にもとづいて前記複数の候補を前記構造化文書記憶装置から選択することを特徴とする請求項４に記載の構造化文書検索装置。
前記処理優先度算出手段は、前記処理コストの大きさに反比例して対応している処理コスト値と、前記構造スコア値とを掛け合わせた数値に基づいて、各候補の処理の処理優先度を算出することを特徴とする請求項４または請求項５に記載の構造化文書検索装置。
前記構造化文書記憶装置は、さらに、語彙ごとに関連語彙識別子を記憶していて、構造雛型木の各ノードに構造雛型木識別子を付与していて、或る語彙の関連語彙識別子が最も多く発生するノードの構造雛型木識別子を該或る語彙の関連構造雛型木識別子として付与し、
前記関連語彙識別子および前記関連構造雛型木識別子にもとづいて、同一の関連語彙識別子を有する語彙と、同一の関連構造雛型木識別子を有する語彙とが一致している数が多いほど値が高くなるように複数の語彙間で正規化した値を語彙スコア値として各語彙に付与する語彙スコア値付与手段をさらに具備し、
前記処理優先度算出手段は、問合せ言語が複数のキーワードから構成される検索を実行した場合、かつ、検索処理途中において、各索引情報の結合処理を行なう場合に、前記語彙スコア値と前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出することを特徴とする請求項４または請求項５に記載の構造化文書検索装置。
構造化文書記憶装置と構造化文書検索装置を具備した構造化文書システムであって、
前記構造化文書記憶装置は、
１つの構造化文書を取得する取得手段と、
前記構造化文書を解析する構造情報解析手段と、
構造化文書の典型的な構造を示す構造雛型木を予め記憶している構造雛型木記憶手段と、
前記構造雛型木を前記解析された構造化文書に合致するように更新する更新手段と、
前記１つの構造化文書を複数の語彙に分割する分割手段と、
前記１つの構造化文書内の要素ごとに該要素内に存在する全ての語彙に対して語彙ごとに該語彙が発生する頻度を示す発生頻度情報を算出する頻度情報算出手段と、
前記語彙ごとに該語彙を含む範囲内で或る出現回数以上の他の語彙が存在するまで前記範囲を拡大する拡大手段と、
前記拡大された範囲内で最も出現回数が多い語彙の語彙識別子を前記語彙の関連語彙識別子として付与する関連語彙識別子付与手段と、を具備し、
前記構造化文書検索装置は、
複数の構造化文書の部分構造から構成される新たな複合文書を生成するための問合せ言語で記述された問合せデータを受け付ける受付手段と、
前記問合せデータを構文解析する構文解析手段と、
前記構文解析された問合せデータに含まれる、問合せの回答として要求される要求構造に類似する類似構造を持つ、構造雛型木に含まれるノードを前記構造化文書記憶装置から複数の候補として選択する選択手段と、
語彙の間の類似度合いを示す類似度を複数の語彙について記憶している類似関係記憶手段と、
前記類似度に基づいて、前記候補ごとに該候補が前記要求構造に類似している度合いを示す構造スコア値を算出する構造スコア値算出手段と、
少なくとも、前記候補と前記構造雛型木とを照合することに基づいて、どの順番で各候補を処理するかを示す各候補の処理コストを算出する処理コスト算出手段と、
少なくとも前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出し、該処理優先度の高い候補から順に、処理を行う選択候補として選択する処理優先度算出手段と、
前記選択候補から処理を実行する処理実行手段と、
複数の前記処理を実行した実行結果を検索結果として取得する結果取得手段と、
を具備することを特徴とする構造化文書システム。
前記構造化文書記憶装置は、
前記語彙ごとに前記関連語彙識別子を記憶している関連語彙識別子記憶手段と、
前記構造雛型木の各ノードに構造雛型木識別子を付与する構造雛型木識別子付与手段と、
或る語彙の関連語彙識別子が最も多く発生するノードの構造雛型木識別子を該或る語彙の関連構造雛型木識別子として付与する関連構造雛型木識別子付与手段と、
前記語彙ごとに関連構造雛型木識別子を記憶している関連構造雛型木識別子記憶手段と、をさらに具備することを特徴とする請求項８に記載の構造化文書システム。
前記構造化文書検索装置は、
前記関連語彙識別子および前記関連構造雛型木識別子にもとづいて、同一の関連語彙識別子を有する語彙と、同一の関連構造雛型木識別子を有する語彙とが一致している数が多いほど値が高くなるように複数の語彙間で正規化した値を語彙スコア値として各語彙に付与する語彙スコア値付与手段をさらに具備し、
前記処理優先度算出手段は、問合せ言語が複数のキーワードから構成される検索を実行した場合、かつ、検索処理途中において、各索引情報の結合処理を行なう場合に、前記語彙スコア値と前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出することを特徴とする請求項９に記載の構造化文書システム。
コンピュータを使用して行う構造化文書方法であって、
第１取得手段が、１つの構造化文書を取得し、
第１解析手段が、前記構造化文書を解析し、
構造雛型木記憶手段が、構造化文書の典型的な構造を示す構造雛型木を予め記憶し、
更新手段が、前記構造雛型木を前記解析された構造化文書に合致するように更新し、
分割手段が、前記１つの構造化文書を複数の語彙に分割し、
第１算出手段が、前記１つの構造化文書内の要素ごとに該要素内に存在する全ての語彙に対して語彙ごとに該語彙が発生する頻度を示す発生頻度情報を算出し、
拡大手段が、前記語彙ごとに該語彙を含む範囲内で或る出現回数以上の他の該語彙が存在するまで前記範囲を拡大し、
第１付与手段が、前記拡大された範囲内で最も出現回数が多い語彙の語彙識別子を前記語彙の関連語彙識別子として付与し、
受付手段が、複数の構造化文書の部分構造から構成される新たな複合文書を生成するための問合せ言語で記述された問合せデータを受け付け、
第２解析手段が、前記問合せデータを構文解析し、
選択手段が、前記構文解析された問合せデータに含まれる、問合せの回答として要求される要求構造に類似する類似構造を持つ、構造雛型木に含まれるノードを前記構造雛型木記憶手段から複数の候補として選択し、
類似関係記憶手段が、語彙の間の類似度合いを示す類似度を複数の語彙について記憶し、
第２算出手段が、前記類似度に基づいて、前記候補ごとに該候補が前記要求構造に類似している度合いを示す構造スコア値を算出し、
第３算出手段が、少なくとも、前記候補と前記構造雛型木とを照合することに基づいて、どの順番で各候補を処理するかを示す各候補の処理コストを算出し、
第４算出手段が、少なくとも前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出し、該処理優先度の高い候補から順に、処理を行う選択候補として選択し、
実行手段が、前記選択候補から処理を実行し、
第２取得手段が、複数の前記処理を実行した実行結果を検索結果として取得する、ことを特徴とする構造化文書方法。
さらに、
関連語彙識別子記憶手段が、前記語彙ごとに前記関連語彙識別子を記憶し、
第２付与手段が、前記構造雛型木の各ノードに構造雛型木識別子を付与し、
第３付与手段が、或る語彙の関連語彙識別子が最も多く発生するノードの構造雛型木識別子を該或る語彙の関連構造雛型木識別子として付与し、
関連構造雛型木識別子記憶手段が、前記語彙ごとに関連構造雛型木識別子を記憶することを特徴とする請求項１１に記載の構造化文書方法。
さらに、
第４付与手段が、前記関連語彙識別子および前記関連構造雛型木識別子にもとづいて、同一の関連語彙識別子を有する語彙と、同一の関連構造雛型木識別子を有する語彙とが一致している数が多いほど値が高くなるように複数の語彙間で正規化した値を語彙スコア値として各語彙に付与することをさらに具備し、
前記処理優先度を算出することは、問合せ言語が複数のキーワードから構成される検索を実行した場合、かつ、検索処理途中において、各索引情報の結合処理を行なう場合に、前記語彙スコア値と前記処理コストと前記構造スコア値とに基づいて、前記プランを構成する各処理の処理優先度を算出することを特徴とする請求項１２に記載の構造化文書方法。
コンピュータを、
１つの構造化文書を取得する取得手段と、
前記構造化文書を解析する構造情報解析手段と、
構造化文書の典型的な構造を示す構造雛型木を予め記憶している構造雛型木記憶手段と、
前記構造雛型木を前記解析された構造化文書に合致するように更新する更新手段と、
前記１つの構造化文書を複数の語彙に分割する分割手段と、
前記１つの構造化文書内の要素ごとに該要素内に存在する全ての語彙に対して語彙ごとに該語彙が発生する頻度を示す発生頻度情報を算出する頻度情報算出手段と、
前記語彙ごとに該語彙を含む範囲内で或る出現回数以上の他の語彙が存在するまで前記範囲を拡大する拡大手段と、
前記拡大された範囲内で最も出現回数が多い語彙の語彙識別子を前記語彙の関連語彙識別子として付与する関連語彙識別子付与手段と、
複数の構造化文書の部分構造から構成される新たな複合文書を生成するための問合せ言語で記述された問合せデータを受け付ける受付手段と、
前記問合せデータを構文解析する構文解析手段と、
前記構文解析された問合せデータに含まれる、問合せの回答として要求される要求構造に類似する類似構造を持つ、構造雛型木に含まれるノードを前記構造雛型木記憶手段から複数の候補として選択する選択手段と、
語彙の間の類似度合いを示す類似度を複数の語彙について記憶している類似関係記憶手段と、
前記類似度に基づいて、前記候補ごとに該候補が前記要求構造に類似している度合いを示す構造スコア値を算出する構造スコア値算出手段と、
少なくとも、前記候補と前記構造雛型木とを照合することに基づいて、どの順番で各候補を処理するかを示す各候補の処理コストを算出する処理コスト算出手段と、
少なくとも前記処理コストと前記構造スコア値とに基づいて、各候補の処理の処理優先度を算出し、該処理優先度の高い候補から順に、処理を行う選択候補として選択する処理優先度算出手段と、
前記選択候補から処理を実行する処理実行手段と、
複数の前記処理を実行した実行結果を検索結果として取得する結果取得手段として機能させるための構造化文書プログラム。
前記語彙ごとに前記関連語彙識別子を記憶している関連語彙識別子記憶手段と、
前記構造雛型木の各ノードに構造雛型木識別子を付与する構造雛型木識別子付与手段と、
或る語彙の関連語彙識別子が最も多く発生するノードの構造雛型木識別子を該或る語彙の関連構造雛型木識別子として付与する関連構造雛型木識別子付与手段と、
前記語彙ごとに関連構造雛型木識別子を記憶している関連構造雛型木識別子記憶手段と、をさらに具備することを特徴とする請求項１４に記載の構造化文書プログラム。
前記関連語彙識別子および前記関連構造雛型木識別子にもとづいて、同一の関連語彙識別子を有する語彙と、同一の関連構造雛型木識別子を有する語彙とが一致している数が多いほど値が高くなるように複数の語彙間で正規化した値を語彙スコア値として各語彙に付与する語彙スコア値付与手段をさらに具備し、
前記処理優先度算出手段は、問合せ言語が複数のキーワードから構成される検索を実行した場合、かつ、検索処理途中において、各索引情報の結合処理を行なう場合に、前記語彙スコア値と前記処理コストと前記構造スコア値とに基づいて、前記プランを構成する各処理の処理優先度を算出することを特徴とする請求項１５に記載の構造化文書プログラム。