(57)【特許請求の範囲】
【請求項１】
階層化された論理構造を有する文書であって、前記論理構造の単位である構造要素に対応する実情報である要素を含む構造化文書と、前記構造化文書を一意に識別する文書ＩＤと、を対応づけて記憶する構造化文書記憶手段と、
前記構造要素を一意に識別する構造ＩＤと、前記要素の特徴を表す第１の特徴情報とを対応づけた構造情報を記憶する構造情報記憶手段と、
前記構造化文書の検索条件の入力を受付け、受付けた検索条件を解析し、前記構造化文書の前記構造要素に対応した構造の単位であるノードを階層化して有する階層構造の検索条件であって、検索対象となる前記構造ＩＤの候補と前記構造ＩＤの候補に対する検索キーとを対応づけた前記ノードを含む前記階層構造の検索条件を求める解析手段と、
前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補に対応づけられた前記第１の特徴情報を前記構造情報記憶手段から取得する取得手段と、
前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記検索キーの特徴を表す第２の特徴情報を算出する算出手段と、
前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補のうち、対応する前記検索キーについて前記算出手段が算出した前記第２の特徴情報が、前記取得手段が取得した前記第１の特徴情報に適合しない前記構造ＩＤの候補を削除する削除手段と、
前記削除手段が前記構造ＩＤの候補を削除した前記階層構造の検索条件に基づき、前記階層構造の検索条件を満たす前記構造ＩＤに対応する前記文書ＩＤを求め、前記求められた文書ＩＤに対応する前記構造化文書を前記構造化文書記憶手段から検索する検索手段と、
を備えたことを特徴とする構造化文書検索装置。
【請求項２】
階層化された論理構造を有する文書であって、前記論理構造の単位である構造要素に対応する実情報である要素を含む構造化文書と、前記構造化文書を一意に識別する文書ＩＤと、を対応づけて記憶する構造化文書記憶手段と、
前記構造要素を一意に識別する構造ＩＤと、前記要素の特徴を表す第１の特徴情報とを対応づけた構造情報を記憶する構造情報記憶手段と、
前記文書ＩＤと、前記要素を一意に識別する要素ＩＤと、前記要素に対応する前記構造要素の前記構造ＩＤとを対応づけた索引を記憶する索引記憶手段と、
前記構造化文書の検索条件の入力を受付け、受付けた検索条件を解析し、前記構造化文書の前記構造要素に対応した構造の単位であるノードを階層化して有する階層構造の検索条件であって、検索対象となる前記構造ＩＤの候補と前記構造ＩＤの候補に対する検索キーとを対応づけた前記ノードを含む前記階層構造の検索条件を求める解析手段と、
前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補に対応づけられた前記第１の特徴情報を前記構造情報記憶手段から取得する取得手段と、
前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記検索キーの特徴を表す第２の特徴情報を算出する算出手段と、
前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補のうち、対応する前記検索キーについて前記算出手段が算出した前記第２の特徴情報が、前記取得手段が取得した前記第１の特徴情報に適合しない前記構造ＩＤの候補を削除する削除手段と、
前記削除手段が前記構造ＩＤの候補を削除した前記階層構造の検索条件に基づき、前記階層構造の検索条件を満たす前記構造ＩＤに対応する前記文書ＩＤと前記要素ＩＤとを前記索引記憶手段から検索する索引検索手段と、
前記索引検索手段が検索した前記文書ＩＤに対応する前記構造化文書を前記構造化文書記憶手段から検索する検索手段と、
を備えたことを特徴とする構造化文書検索装置。
【請求項３】
前記索引記憶手段は、前記要素に含まれる文字列である語彙ごとに、前記語彙を一意に識別する語彙ＩＤと、前記語彙の前記構造化文書記憶手段のすべての構造化文書内での発生頻度とをさらに対応づけた前記索引を記憶し、
前記構造情報記憶手段は、前記要素に含まれる前記語彙に対応づけられた前記語彙ＩＤの最小値である最小語彙ＩＤおよび最大値である最大語彙ＩＤを前記第１の特徴情報として対応づけた前記構造情報を記憶し、
前記算出手段は、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードの前記検索キーに含まれる語彙の前記語彙ＩＤを前記第２の特徴情報として算出し、
前記削除手段は、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補のうち、対応する前記検索キーについて前記算出手段が算出した前記語彙ＩＤが、前記取得手段が取得した前記第１の特徴情報である前記最小語彙ＩＤと前記最大語彙ＩＤとの間に含まれない前記構造ＩＤの候補を削除することを特徴とする請求項２に記載の構造化文書検索装置。
【請求項４】
前記索引記憶手段は、前記要素に含まれるすべての連続する複数の文字である語彙ごとに、前記語彙を一意に識別する語彙ＩＤと、前記語彙の前記構造化文書記憶手段のすべての構造化文書内での発生頻度とをさらに対応づけた前記索引を記憶することを特徴とする請求項３に記載の構造化文書検索装置。
【請求項５】
前記索引記憶手段は、前記要素を形態素解析して得られる単語である語彙ごとに、前記語彙を一意に識別する語彙ＩＤと、前記語彙の前記構造化文書記憶手段のすべての構造化文書内での発生頻度とをさらに対応づけた前記索引を記憶することを特徴とする請求項３に記載の構造化文書検索装置。
【請求項６】
前記索引記憶手段は、前記文書ＩＤと、前記要素ＩＤと、前記要素に対応する前記構造要素の前記構造ＩＤと、前記要素の特徴を表す第３の特徴情報とを対応づけた索引を記憶し、
前記索引検索手段が検索した前記文書ＩＤと前記要素ＩＤとに対応づけられた前記第３の特徴情報を前記索引記憶手段から取得する第２の取得手段と、
前記索引検索手段が検索した前記文書ＩＤと前記要素ＩＤとから、検索する際に用いた前記階層構造の検索条件のノードに含まれる前記検索キーについて前記算出手段が算出した前記第２の特徴情報が、前記第２の取得手段が取得した前記第３の特徴情報に適合しない前記文書ＩＤと前記要素ＩＤとを削除する第２の削除手段と、をさらに備え、
前記検索手段は、前記第２の削除手段が削除した後の前記文書ＩＤに対応する前記構造化文書を前記構造化文書記憶手段から検索することを特徴とする請求項２に記載の構造化文書検索装置。
【請求項７】
前記索引記憶手段は、前記要素に含まれる文字列である語彙ごとに、前記語彙を一意に識別する語彙ＩＤと、前記語彙の前記構造化文書記憶手段のすべての構造化文書内での発生頻度と、前記文書ＩＤと、前記要素ＩＤと、前記要素に対応する前記構造要素の前記構造ＩＤと、前記要素に含まれる前記語彙に対応づけられた前記語彙ＩＤの最小値である最小語彙ＩＤおよび最大値である最大語彙ＩＤに基づいて算出した前記第３の特徴情報とを対応づけた前記索引を記憶し、
前記算出手段は、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードの前記検索キーに含まれる語彙の前記語彙ＩＤに基づいて前記第２の特徴情報を算出し、
前記第２の削除手段は、前記索引検索手段が検索した前記文書ＩＤと前記要素ＩＤとから、検索する際に用いた前記階層構造の検索条件のノードに含まれる前記検索キーについて前記算出手段が算出した前記語彙ＩＤが、前記第２の取得手段が取得した前記第３の特徴情報に適合しない前記文書ＩＤと前記要素ＩＤとを削除することを特徴とする請求項６に記載の構造化文書検索装置。
【請求項８】
前記索引記憶手段は、前記文書ＩＤと、前記要素ＩＤと、前記要素に対応する前記構造要素の前記構造ＩＤと、前記要素に含まれる前記語彙の出現位置と、前記出現位置ごとの前記要素の特徴を表す第３の特徴情報とを対応づけた索引を記憶することを特徴とする請求項７に記載の構造化文書検索装置。
【請求項９】
前記構造情報記憶手段は、前記第１の特徴情報に基づいて前記構造要素を分割する条件をさらに対応づけた前記構造情報を記憶し、
前記構造化文書の入力を受付ける受付手段と、
前記受付手段が受付けた前記構造化文書から少なくとも１つの前記構造要素を含む階層構造を抽出する抽出手段と、
前記抽出手段が抽出した前記階層構造に含まれる前記構造要素ごとに対応する前記構造ＩＤを決定する構造情報決定手段と、
前記抽出手段が抽出した前記階層構造に含まれる前記構造要素に対応する前記要素の前記第１の特徴情報が、前記構造情報決定手段が決定した前記構造ＩＤに対応する前記条件を満たすか否かを判定する判定手段と、
前記判定手段が前記条件を満たすと判定した場合に、前記構造情報決定手段が決定した前記構造ＩＤに対応する前記構造要素を分割して新たな前記構造情報を作成し、前記構造情報記憶手段に登録する構造情報分割手段と、をさらに備えたことを特徴とする請求項２に記載の構造化文書検索装置。
【請求項１０】
前記構造情報記憶手段は、前記構造要素に対応する前記要素の文字列長の最大値である最大文字列長を前記第１の特徴情報とし、前記最大文字列長が予め定められた閾値を超えた場合に前記構造要素を分割する条件をさらに対応づけた前記構造情報を記憶することを特徴とする請求項９に記載の構造化文書検索装置。
【請求項１１】
前記構造情報記憶手段は、前記構造要素に対応する前記要素内の前記語彙の個数の最大値である最大語彙数を前記第１の特徴情報とし、前記最大語彙数が予め定められた閾値を超えた場合に前記構造要素を分割する条件をさらに対応づけた前記構造情報を記憶することを特徴とする請求項９に記載の構造化文書検索装置。
【請求項１２】
前記構造情報記憶手段は、前記構造要素に対応する前記要素の文字列長が予め定められた第１の閾値を超えた回数を前記第１の特徴情報とし、前記回数が予め定められた第２の閾値を超えた場合に前記構造要素を分割する条件をさらに対応づけた前記構造情報を記憶することを特徴とする請求項９に記載の構造化文書検索装置。
【請求項１３】
前記索引記憶手段は、前記要素に含まれる文字列である語彙ごとに、前記語彙を一意に識別する語彙ＩＤと、前記語彙の前記構造化文書記憶手段のすべての構造化文書内での発生頻度とをさらに対応づけた前記索引を記憶し、
前記構造情報記憶手段は、前記索引記憶手段に記憶された前記語彙のうち、前記出現頻度が予め定められた第１の閾値より大きい前記語彙が、前記構造要素に対応する前記要素内に出現する回数が予め定められた第２の閾値を超えた場合に前記構造要素を分割する条件をさらに対応づけた前記構造情報を記憶することを特徴とする請求項９に記載の構造化文書検索装置。
【請求項１４】
構造化文書検索装置が、
階層化された論理構造を有する文書であって、前記論理構造の単位である構造要素に対応する実情報である要素を含む構造化文書の検索条件の入力を受付け、受付けた検索条件を解析し、前記構造化文書の前記構造要素に対応した構造の単位であるノードを階層化して有する階層構造の検索条件であって、検索対象となる前記構造化文書の前記構造要素を一意に識別する構造ＩＤの候補と前記構造ＩＤの候補に対する検索キーとを対応づけた前記ノードを含む前記階層構造の検索条件を求める解析ステップと、
前記構造ＩＤと、前記要素の特徴を表す第１の特徴情報とを対応づけた構造情報を記憶する構造情報記憶手段から、前記解析ステップが求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補に対応づけられた前記第１の特徴情報を取得する取得ステップと、
前記解析ステップが求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記検索キーの特徴を表す第２の特徴情報を算出する算出ステップと、
前記解析ステップが求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補のうち、対応する前記検索キーについて前記算出ステップが算出した前記第２の特徴情報が、前記取得ステップが取得した前記第１の特徴情報に適合しない前記構造ＩＤの候補を削除する削除ステップと、
構造化文書と前記構造化文書を一意に識別する文書ＩＤと、前記要素を一意に識別する要素ＩＤと、前記要素に対応する前記構造要素の前記構造ＩＤとを対応づけた索引を記憶する索引記憶手段から、前記削除ステップが前記構造ＩＤの候補を削除した前記階層構造の検索条件に基づき、前記階層構造の検索条件を満たす前記構造ＩＤに対応する前記文書ＩＤと前記要素ＩＤとを検索する索引検索ステップと、
前記索引検索ステップが検索した前記文書ＩＤに対応する前記構造化文書を、前記構造化文書と前記文書ＩＤとを対応づけて記憶する構造化文書記憶手段から検索する検索ステップと、
を実行することを特徴とする構造化文書検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、階層化された論理構造を持つ構造化文書データベースで管理された異なる文書構造の複数の構造化文書を検索する構造化文書検索装置および構造化文書検索方法に関するものである。
【背景技術】
【０００２】
近年、ＸＭＬ（eXtensible Markup Language）などで記述された構造化文書データを記憶・検索する構造化文書データベースが開発されている。構造化文書データベースに対する問合せ（検索）は、一般に、Ｗ３Ｃ（World Wide Web Consortium）が標準化を進めているＸＱｕｅｒｙ（XML Query）という問合せ言語によって行われる。
【０００３】
ＸＱｕｅｒｙは、条件式の指定によるフィルタリングだけでなく、検索結果を返す部分であるＲｅｔｕｒｎ節に仮想的な構造化文書を埋め込むこと、条件式を複雑な入れ子構造とすること、条件式に関数式を定義することなどが可能であり、多様な機能を有する非常に問合せ能力が高度な言語である。
【０００４】
ＸＱｕｅｒｙでは、要素や属性などのＤＯＭ（Document Object Model）におけるノードレベルの情報を検索対象とする。例えば、特許文献１では、以下の方法により、構造化文書のノードレベルの情報の検索を行う技術が提案されている。
【０００５】
まず、構造化文書をデータベースに格納する際に、対象となる文書のデータ構造を解析し、その構造（ノード）に対する解析情報を語彙索引情報などに埋め込んで索引を作成する。なお、この場合の構造の解析情報は、ＸＰａｔｈ（XML Path Language）で表現できるパスレベルを同一の構造情報（構造テンプレート）と見なした情報である。
【０００６】
次に、検索時に検索クエリを解析して問合せグラフを作成し、コスト計算をした上でクエリ実行のプランを作成する。この際、索引処理時にクエリを解析し、それぞれの変数が満たさなければならない構造に対する制約を予め求めることにより、各索引に対する探索範囲を限定した上で索引の検索を行い、中間の候補件数の削減を実現している。
【０００７】
一方、全文検索の分野では、キーワードの論理条件（ＡＮＤ／ＯＲなど）を指定して合致する文書を検索する機能や、文字の出現位置を条件に指定して検索する機能が実現されている。出現位置を条件とする検索条件の一例として、「<title>タグに、“web”と“title”が５文字以内に存在する情報を検索せよ」のような近傍検索が挙げられる。
【０００８】
近傍検索を実現するためには、ＡＮＤ条件の処理を行う際にテキストの位置情報を残しておく必要がある。しかし、ＸＱｕｅｒｙは検索対象がノード単位のモデルであるため、ＡＮＤ条件の処理時に出現位置に関する情報が失われ、近傍検索を実現することができなかった。
【０００９】
このように、ＸＱｕｅｒｙは、全文検索機能を実現するという観点からは十分な表現能力を有するとは言えなかった。これを解消するため、ＸＱｕｅｒｙを拡張し、全文検索機能を融合したＸＱＦＴ（XQuery-Full-Text）という言語規格がＷ３Ｃによって提案されている。
【００１０】
ＸＱＦＴは検索対象のノードに対して、テキストの出現位置の条件を含む複数の条件を記述可能である。例えば、上記の近傍検索の例は、「./title ftcontains "web" && "site" distance at most 5」と記述することができる。ＸＱＦＴでは、検索対象の情報がＸＱｕｅｒｙの「ノード」レベルではなく、「テキストの出現位置」レベルであるため、これを考慮した処理方法を実現しなければならない。
【００１１】
【特許文献１】特開２００１−１４７９３３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、ＸＱＦＴでは、テキストの出現位置レベルまで考慮した検索結果の候補を取得するため、結合処理等を行う場合に中間候補数が膨大になり、検索処理速度の低下や、メモリ量の爆発等を招く可能性があるという問題があった。
【００１３】
例えば、ある要素内に“web”が１００回、“site”が２００回出現する場合、各要素に対する候補を単純に結合すると、中間候補数は２００００（１００×２００）個存在する。ＸＱＦＴによりテキストの出現位置レベルまで考慮すると、各要素に対する候補数が増大するため、それらの候補を結合して得られる中間候補数の個数はさらに増大する。
【００１４】
本発明は、上記に鑑みてなされたものであって、構造化文書に対する高速な全文検索機能を実現することができる構造化文書検索装置および構造化文書検索方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するために、本発明は、階層化された論理構造を有する文書であって、前記論理構造の単位である構造要素に対応する実情報である要素を含む構造化文書と、前記構造化文書を一意に識別する文書ＩＤと、を対応づけて記憶する構造化文書記憶手段と、前記構造要素を一意に識別する構造ＩＤと、前記要素の特徴を表す第１の特徴情報とを対応づけた構造情報を記憶する構造情報記憶手段と、前記構造化文書の検索条件の入力を受付け、受付けた検索条件を解析し、前記構造化文書の前記構造要素に対応した構造の単位であるノードを階層化して有する階層構造の検索条件であって、検索対象となる前記構造ＩＤの候補と前記構造ＩＤの候補に対する検索キーとを対応づけた前記ノードを含む前記階層構造の検索条件を求める解析手段と、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補に対応づけられた前記第１の特徴情報を前記構造情報記憶手段から取得する取得手段と、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記検索キーの特徴を表す第２の特徴情報を算出する算出手段と、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補のうち、対応する前記検索キーについて前記算出手段が算出した前記第２の特徴情報が、前記取得手段が取得した前記第１の特徴情報に適合しない前記構造ＩＤの候補を削除する削除手段と、前記削除手段が前記構造ＩＤの候補を削除した前記階層構造の検索条件に基づき、前記階層構造の検索条件を満たす前記構造ＩＤに対応する前記文書ＩＤを求め、前記求められた文書ＩＤに対応する前記構造化文書を前記構造化文書記憶手段から検索する検索手段と、を備えたことを特徴とする。
【００１６】
また、本発明は、階層化された論理構造を有する文書であって、前記論理構造の単位である構造要素に対応する実情報である要素を含む構造化文書と、前記構造化文書を一意に識別する文書ＩＤと、を対応づけて記憶する構造化文書記憶手段と、前記構造要素を一意に識別する構造ＩＤと、前記要素の特徴を表す第１の特徴情報とを対応づけた構造情報を記憶する構造情報記憶手段と、前記文書ＩＤと、前記要素を一意に識別する要素ＩＤと、前記要素に対応する前記構造要素の前記構造ＩＤとを対応づけた索引を記憶する索引記憶手段と、前記構造化文書の検索条件の入力を受付け、受付けた検索条件を解析し、前記構造化文書の前記構造要素に対応した構造の単位であるノードを階層化して有する階層構造の検索条件であって、検索対象となる前記構造ＩＤの候補と前記構造ＩＤの候補に対する検索キーとを対応づけた前記ノードを含む前記階層構造の検索条件を求める解析手段と、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補に対応づけられた前記第１の特徴情報を前記構造情報記憶手段から取得する取得手段と、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記検索キーの特徴を表す第２の特徴情報を算出する算出手段と、前記解析手段が求めた前記階層構造の検索条件の各ノードについて、各ノードに含まれる前記構造ＩＤの候補のうち、対応する前記検索キーについて前記算出手段が算出した前記第２の特徴情報が、前記取得手段が取得した前記第１の特徴情報に適合しない前記構造ＩＤの候補を削除する削除手段と、前記削除手段が前記構造ＩＤの候補を削除した前記階層構造の検索条件に基づき、前記階層構造の検索条件を満たす前記構造ＩＤに対応する前記文書ＩＤと前記要素ＩＤとを前記索引記憶手段から検索する索引検索手段と、前記索引検索手段が検索した前記文書ＩＤに対応する前記構造化文書を前記構造化文書記憶手段から検索する検索手段と、を備えたことを特徴とする。
【００１７】
また、本発明は、上記装置を実行することができる構造化文書検索方法である。
【発明の効果】
【００１８】
本発明によれば、構造化文書の構造要素ごとに対応する要素の特徴を表す特徴情報を格納し、検索時に当該特徴情報を参照して中間候補数を絞り込むことができる。このため、構造化文書に対する高速な全文検索機能を実現することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１９】
以下に添付図面を参照して、この発明にかかる構造化文書検索装置および構造化文書検索方法の最良な実施の形態を詳細に説明する。
【００２０】
（第１の実施の形態）
第１の実施の形態にかかる構造化文書検索装置は、構造化文書の構造要素ごとに対応する要素の特徴を表す特徴情報を格納し、検索時に当該特徴情報を参照して中間候補数を絞り込むことにより、ＸＱＦＴのような構造化文書の全文検索機能を高速に実現可能とするものである。
【００２１】
図１は、第１の実施の形態にかかる構造化文書検索装置１００の構成を示すブロック図である。同図に示すように、構造化文書検索装置１００は、ネットワーク２００を介してクライアント３００と接続されており、通信部１０１と、格納処理部１１０と、検索処理部１２０と、構造化文書記憶部１３１と、構造テンプレート記憶部１３２と、索引記憶部１３３とを備えている。
【００２２】
クライアント３００は、登録する構造化文書（ＸＭＬ文書）や、登録済みの構造化文書を対象とする検索クエリを構造化文書検索装置１００に送信し、検索結果を受信するものである。
【００２３】
ネットワーク２００は、クライアント３００と構造化文書検索装置１００とを接続するもので、例えば、インターネット、有線ＬＡＮ（Local Area Network）、無線ＬＡＮなどのあらゆるネットワーク構成を適用することができる。
【００２４】
通信部１０１は、ネットワーク２００を介して、クライアント３００から構造化文書、検索クエリを受信し、検索結果をクライアント３００に送信するものである。
【００２５】
構造化文書記憶部１３１は、ＸＭＬで記述された構造化文書を記憶する記憶部である。ここで、構造化文書の記述形式について説明する。図２は、ＸＭＬで記述された構造化文書の一例を示す説明図である。
【００２６】
同図では、特許に関する情報をＸＭＬ形式で記述した構造化文書の例が示されている。ＸＭＬでは、文書の構造の表現にタグが用いられる。タグには、開始タグと終了タグが存在し、構造化文書の構成要素を開始タグと終了タグで囲むことにより、文書中の文字列（テキスト）の区切りと、そのテキストが構造上いずれの構成要素に属するのかを明確に記述することができる。
【００２７】
なお、ＸＭＬでは、タグを使って定義したデータの単位を要素という。例えば、＜特許＞タグと＜／特許＞タグとを含み、両タグで囲まれたデータが１つの要素を構成する。
【００２８】
また、要素には、省略可能か、繰り返しが可能かなどの付加的な情報を追加するための属性を指定することができる。属性は、開始タグに「＜要素名称 属性＝"属性値"＞」のような書式で設定する。同図では、“特許”要素の属性として“ＩＤ”属性が指定された例が示されている。
【００２９】
また、開始タグとは要素名称を記号「＜」、「＞」で閉じた書式で記載され、終了タグとは要素名称を記号「＜／」と「＞」で閉じた書式で記載される。開始タグと終了タグとの間には、構造化文書の実情報を表すテキスト、または他の要素（子要素）が設定される。「＜特許ＤＢ＞＜／特許ＤＢ＞」のようにテキストを含まない構成要素は、簡易記法として「＜特許ＤＢ／＞」のように表すこともできる。
【００３０】
同図に示した文書は、「特許」タグから始まる要素を文書ルート（根）とし、その子要素として「タイトル」、「発明者一覧」、「効果」、「キーワードリスト」タグから始まる要素を有する。また、例えば、「タイトル」タグから始まる要素には「構造化文書検索装置」といった、１つのテキスト（文字列）が存在する。
【００３１】
なお、このようなＸＭＬ形式の構造化文書から、各タグの名称や階層関係、繰り返しの個数などを抽出した情報を構造情報という。また、構造化文書の構造情報を構成する論理的な構造の単位を構造要素という。第１の実施の形態では、上述の要素、属性、テキストが構造要素となる。
【００３２】
次に、構造化文書記憶部１３１に格納された構造化文書のデータ構造について説明する。図３は、構造化文書記憶部１３１に格納された構造化文書のデータ構造の一例を示す説明図である。
【００３３】
同図は、図２に示す構造化文書を木構造のデータ構造で表した例を示している。図３では、楕円のノードはフォルダを表すノード、六角形のノードは文書を表すノード、一重線の四角形はタグを表すノード、二重線の四角形は属性を表すノード、角の丸い四角形はテキストを表すノードを意味する。
【００３４】
例えば、“発明者一覧”タグを表すノード以下の部分木は、“発明者一覧”要素以下の２つの“発明者”要素を含んでいることを表している。
【００３５】
構造化文書記憶部１３１は、このような木構造のデータ構造を表形式で格納する。図４は、表形式で表した構造化文書のデータ構造の一例を示す説明図である。
【００３６】
同図に示すように、構造化文書記憶部１３１の構造化文書は、文書ＩＤと、要素ＩＤと、木構造の親子兄弟関係を長男次弟方式で表したときの次弟と長男とを対応づけて格納している。文書ＩＤは、構造化文書を一意に識別するための識別子である。要素ＩＤは、文書ＩＤで識別される構造化文書の木構造の要素（ノード）を一意に識別するための識別子である。
【００３７】
例えば、同図の要素ＩＤ＝３のノードは、図２の“タイトル”タグのノードに対応しており、次弟として図２の“発明者一覧”タグのノード（要素ＩＤ＝４）、および長男として図２の“テキスト”ノード（要素ＩＤ＝５）を有することを示している。
【００３８】
構造テンプレート記憶部１３２は、上述のようなＸＭＬ形式の構造化文書から抽出された構造情報を格納するものである。構造テンプレート記憶部１３２は、構造化文書記憶部１３１に格納する構造化文書の構造を、構造情報と照合して解析する際に参照される。
【００３９】
図５は、第１の実施の形態における構造テンプレート記憶部１３２に格納された構造情報のデータ構造の一例を示す説明図である。同図は、構造情報を木構造で表した例を示している。
【００４０】
同図に示すように、構造情報の木構造は、構造化文書の木構造と同様に、フォルダを表す楕円のノード、文書を表す六角形のノード、タグを表す一重線の四角形のノード、属性を表す二重線の四角形のノード、テキストを表す角の丸い四角形のノードを含んでいる。
【００４１】
また、構造情報には、構造情報の各ノードである構造要素を一意に識別するための識別子であるテンプレートＩＤ（ＴＩＤ）が付与されている。構造情報は、複数の構造化文書から、構造を表す情報のみを抽出した情報である。したがって、例えば、“発明者”タグのノードのように、構造化文書内では複数設定されうる情報であっても、構造情報上では１つに集約される。
【００４２】
構造テンプレート記憶部１３２は、このような木構造の構造情報を表形式で格納する。図６は、表形式で表した構造テンプレート記憶部１３２のデータ構造の一例を示す説明図である。
【００４３】
同図に示すように、構造テンプレート記憶部１３２の構造情報は、ＴＩＤと、次弟と、長男と、最小語彙ＩＤと、最大語彙ＩＤと、最大テキストサイズとを対応づけて格納している。
【００４４】
最小語彙ＩＤおよび最大語彙ＩＤには、ＴＩＤで識別される構造要素に対応するテキスト要素内に出現する語彙のうち、それぞれ語彙ＩＤが最小および最大の語彙を設定する。語彙ＩＤとは、索引記憶部１３３内に格納されている語彙に対し、語彙の出現順に付与された一意に識別するための識別子をいう。索引記憶部１３３の詳細については後述する。
【００４５】
最大テキストサイズとは、ＴＩＤで識別される構造要素に対応するテキスト要素のうち、文字列長が最大のテキスト要素の文字列長の値をいう。
【００４６】
このように、構造要素の親子兄弟関係を表す情報（次弟、長男）だけでなく、構造要素に対応するテキスト要素の特徴を表す情報（特徴情報）として最小語彙ＩＤと最大語彙ＩＤと最大テキストサイズとを対応づけて格納することにより、検索時に当該情報を参照して中間候補数を絞り込むことが可能となる。
【００４７】
索引記憶部１３３は、構造化文書の検索で用いる索引を記憶するものであり、統計情報記憶部１３３ａと、転置ファイル記憶部１３３ｂとを備えている。
【００４８】
統計情報記憶部１３３ａは、構造化文書記憶部１３１に格納された各構造化文書内に発生する語彙の統計情報を格納する記憶部である。語彙とは、構造化文書の実情報を表すテキストに含まれる語句を言う。第１の実施の形態では、テキストをＮグラム分割した語句を語彙とする。Ｎグラム分割とは、文字列に含まれるすべての連続するＮ個の文字を語彙として分割する方法をいう。
【００４９】
例えば、文字列“ＸＭＬデータベース”をＮ＝３でＮグラム分割すると、“ＸＭＬ”、“ＭＬデ”、“Ｌデー”、“データ”、“ータベ”、“タベー”、“ベース”、“ース”、“ス”の９個の語彙に分割される。
【００５０】
なお、テキストからの語彙の分割方法はこれに限られるものではなく、テキストに含まれる語句を抽出するものであれば、形態素解析で得られる単語を語彙とする方法などのあらゆる方法を適用することができる。
【００５１】
図７は、統計情報記憶部１３３ａに格納された統計情報のデータ構造の一例を示す説明図である。同図に示すように、統計情報記憶部１３３ａは、分割された各語彙について、発生順に昇順に付与された識別子である語彙ＩＤと、語彙の全構造化文書内での発生頻度と、転置ファイル番号とを対応づけた統計情報を格納している。
【００５２】
なお、一般的に出現頻度が高い語彙はいずれの文書内にも存在する可能性が高いことから、語彙ＩＤの値は小さくなる傾向があり、逆に稀少語彙に関しては語彙ＩＤの値は大きくなる傾向がある。
【００５３】
また、転置ファイル番号とは、後述する転置ファイル記憶部１３３ｂに記憶された転置ファイルを一意に識別するための番号をいう。なお、統計情報記憶部１３３ａに格納された語彙の統計情報と、転置ファイルとにより構造化文書の検索を高速化するための索引が構成される。
【００５４】
転置ファイル記憶部１３３ｂは、構造化文書の検索処理を高速化するための索引の一部を構成する転置ファイルを格納する記憶部である。図８は、転置ファイル記憶部１３３ｂに格納された転置ファイルのデータ構造の一例を示す説明図である。
【００５５】
同図は、統計情報記憶部１３３ａに格納された、ある語彙に対応する１つの転置ファイルのデータ構造を表している。実際には、語彙ごとに同図のような構造の転置ファイルが作成され、転置ファイル記憶部１３３ｂに格納される。
【００５６】
同図に示すように、転置ファイル記憶部１３３ｂの転置ファイルは、ＴＩＤと、文書ＩＤと、要素ＩＤと、発生位置とを対応づけた語彙索引情報を格納している。
【００５７】
発生位置とは、当該転置ファイルに対応する語彙が、文書ＩＤと要素ＩＤとで識別される構造化文書の要素内で出現する位置を表す情報である。
【００５８】
格納処理部１１０は、クライアント３００から受信した構造化文書を構造化文書記憶部１３１に格納する処理を実行するもので、構造情報抽出部１１１と、構造テンプレート決定部１１２と、索引登録部１１３と、統計情報更新部１１４と、文書登録部１１５とを備えている。
【００５９】
構造情報抽出部１１１は、通信部１０１がクライアント３００から受信した構造化文書から構造情報を抽出するものである。具体的には、構造情報抽出部１１１は、受信した構造化文書を構文解析してＤＯＭのような木構造の形式に展開し、木構造の各ノードを構造情報として抽出する。展開した木構造の各ノードは、後述する文書登録部１１５により構造化文書記憶部１３１に記憶される。なお、文書ＩＤ、要素ＩＤは、構造情報抽出部１１１が構造情報を抽出した際に付与される。
【００６０】
構造テンプレート決定部１１２は、構造情報抽出部１１１が抽出した構造情報を参照し、構造テンプレート記憶部１３２に記憶された構造情報と照合することにより、展開した木構造の構造化文書の各ノードに対応するＴＩＤを決定するものである。また、構造テンプレート決定部１１２は、構造テンプレート記憶部１３２に既に記憶されている構造情報に含まれない新規の構造情報を構造情報抽出部１１１が抽出した場合は、当該新規構造情報を構造テンプレート記憶部１３２に格納する。
【００６１】
索引登録部１１３は、クライアント３００から受信した構造化文書に含まれるテキスト要素に対する語彙索引情報を作成し、転置ファイル記憶部１３３ｂに登録するものである。
【００６２】
具体的には、索引登録部１１３は、テキスト要素の文字列をＮグラム分割して得られた語彙に対応する転置ファイル内に、構造テンプレート決定部１１２で決定または算出されたＴＩＤ、文書ＩＤ、要素ＩＤ、および発生位置を対応づけた語彙索引情報を新たに転置ファイルに追加する。
【００６３】
統計情報更新部１１４は、クライアント３００から受信した構造化文書に含まれるテキスト要素から抽出した語彙の統計情報を統計情報記憶部１３３ａに登録するものである。
【００６４】
具体的には、統計情報更新部１１４は、テキスト要素の文字列をＮグラム分割して得られた語彙に対応する統計情報記憶部１３３ａ内の統計情報を更新する。なお、新規の語彙が抽出された場合は、当該新規の語彙を統計情報記憶部１３３ａの統計情報に追加する。
【００６５】
また、統計情報更新部１１４は、構造テンプレート記憶部１３２内の最小語彙ＩＤ、最大語彙ＩＤ、最大テキストサイズの更新が必要な場合に、それらの値を更新する処理を行う。例えば、図６のような構造情報が構造テンプレート記憶部１３２に登録されている場合に、ＴＩＤ＝４の構造要素に対応するテキスト要素として最大語彙ＩＤ＝５２２の語彙が出現した場合、最大語彙ＩＤを５２２に更新する。
【００６６】
文書登録部１１５は、構造情報抽出部１１１が木構造に展開した各ノードに対して、親子兄弟関係を付加し、構造化文書記憶部１３１に格納するものである。
【００６７】
検索処理部１２０は、クライアント３００から受信した検索クエリに従い、構造化文書記憶部１３１から構造化文書を検索する処理を実行するもので、クエリ解析部１２１と、制約付加部１２２と、クエリプランニング部１２３と、クエリ実行部１２４とを備えている。
【００６８】
検索処理部１２０の処理は、原則として特許文献１の方法により実行される。以下では、検索処理のうち、語彙索引の処理に関する部分について詳細に説明するが、実際の処理では、語彙索引の処理以外にもさまざまな処理が実行される。
【００６９】
なお、特許文献１の方法では、制約従属型のプラン作成方法に準じ、問合せ言語を解析した内部形式から、階層構造の検索条件であるクエリグラフを作成する。そして、作成したクエリグラフに含まれる全ての変数の具体化を目標として、テーブルと呼ばれる変数集合の取り得る値（候補集合）の組み合わせを表すデータを順次生成する。ここで、１つのテーブルを生成する処理単位をオペレータと呼ぶ。各オペレータの結果は、候補集合として記憶部に保存される。
【００７０】
クエリ解析部１２１は、通信部１０１がクライアント３００から受信した検索クエリを構文解析し、解析結果としてクエリグラフを作成するものである。クエリグラフの作成は、特許文献１に記載の方法など従来から用いられているあらゆる方法を適用することができる。
【００７１】
図９は、検索クエリの一例を示す説明図である。同図に示すクエリは、「タイトル要素に“構造化文書”および“XML”を含み、ＩＤ＝３である“特許”文書を取得し、“＜検索結果＞”タグで囲った検索結果データを出力する検索条件を表している。
【００７２】
図１０は、クエリグラフの一例を示す説明図である。同図のクエリグラフは、図９の検索クエリをクエリ解析部１２１が解析して作成したクエリグラフである。
【００７３】
図１０に示すように、クエリグラフは構造情報の各構造要素に対応したノードを含む木構造で表される。例えば、図１０のクエリグラフのノード２は、「特許」文書の構造要素が対応することを示している。また、例えば、ノード３はタイトルタグが、ノード４はタイトルタグ下のテキスト要素が対応することを示している。
【００７４】
構造要素に対する検索条件（以下、検索キー）が存在する場合は、当該検索キーを、検索キーの検索対象となる構造要素に対応するノードに対応づける。例えば、図１０では、ノード４に対応するタイトルタグ下のテキスト要素に対して検索キーとして「ftcontains “構造化文書” && “XML”」が対応づけられている。
【００７５】
制約付加部１２２は、クエリ解析部１２１が作成したクエリグラフにおけるノード間の制約関係を求め、当該制約を満たす構造要素の候補を取得してクエリグラフに付加するものである。なお、このような構造要素の候補が中間候補の１つに相当する。
【００７６】
制約としては、候補となる構造要素が相互に満たさなければならない構造に関する制約（以下、構造制約という。）、語彙に関する制約（以下、語彙制約という。）が存在する。
【００７７】
構造制約とは、テキスト全体が対応するノードレベルの情報により設定される制約をいう。例えば、クエリグラフのノード４はタイトルタグ下のテキスト要素でなければならないといった制約が構造制約に該当する。この場合、ノード４には、対応する構造要素の候補として、ＴＩＤ＝７の構造要素が取得される。なお、構造情報は、図５、図６に示すような内容が格納されていることを前提とする。同様に、ノード２に対してはＴＩＤ＝４の構造要素が、ノード６に対してはＴＩＤ＝５の構造要素が候補として取得される。
【００７８】
この他、制約付加部１２２は、ある２つの構造要素は同一文書内に存在するといった制約（以下、同一文書制約という。）を構造制約とすることもできる。
【００７９】
語彙制約とは、テキストの語彙レベルの情報により設定される制約をいう。例えば、ＴＩＤ＝７のノードに対応する語彙は、語彙ＩＤが最小語彙ＩＤ＝２１から最大語彙ＩＤ＝１０４５の間に存在しなければならないといった制約が語彙制約に該当する。なお、最小語彙ＩＤ、最大語彙ＩＤは、図６に示すようなノードごとの特徴情報を含む構造テンプレート記憶部１３２から取得できる。
【００８０】
また、制約付加部１２２は、近傍検索などの語彙の出現位置を条件とした制約を語彙制約とすることもできる。
【００８１】
制約付加部１２２は、図１に示すように、特徴情報取得部１２２ａと、特徴情報算出部１２２ｂと、ＴＩＤ候補削除部１２２ｃとを備えている。
【００８２】
特徴情報取得部１２２ａは、クエリグラフの各ノードに含まれるＴＩＤの候補に対応づけられた特徴情報である最小語彙ＩＤおよび最大語彙ＩＤを構造テンプレート記憶部１３２から取得するものである。
【００８３】
特徴情報算出部１２２ｂは、クエリグラフの各ノードに含まれる検索キーの特徴を表す特徴情報を算出するものである。具体的には、特徴情報算出部１２２ｂは、検索キーをＮグラム分割した結果の語彙を検索キーの特徴情報として算出する。
【００８４】
ＴＩＤ候補削除部１２２ｃは、クエリグラフの各ノードに含まれるＴＩＤの候補から、特徴情報算出部１２２ｂが算出した特徴情報である検索キーを分割した語彙の語彙ＩＤが、特徴情報取得部１２２ａが取得した最小語彙ＩＤおよび最大語彙ＩＤの範囲外となる候補を削除するものである。  
【００８５】
クエリプランニング部１２３は、クエリ解析部１２１で求めたクエリグラフと、制約付加部１２２で付加した制約関係を満たす構造要素の候補の情報とを参照し、処理コストが最小になるようなプラン（処理順序）を作成するものである。プランの作成方法としては、特許文献１に記載の方法など従来から用いられているあらゆる方法を適用することができる。なお、Ｎグラム方式では、グラムレベルでその処理順序を決定するために、グラムごとのコストと、検索語彙全体のコストとが分けて計算される。
【００８６】
図１１、図１２は、処理コスト計算で用いられる語彙の頻度情報の一例を示した説明図である。図１１、図１２は、単純に語彙の頻度によって処理コストを計算する場合の例を示している。
【００８７】
検索結果の候補を早期に絞り込むため、クエリプランニング部１２３は、原則として頻度が小さい語彙から検索を実行するようなプランを作成する。例えば、テキスト“構造化文書”から抽出された語彙の頻度が、図１１に示すような値であった場合、最も頻度の小さい（３０）語彙である“造化”から検索を実行するプランが作成される。
【００８８】
なお、同一テキスト内の語彙を連続して検索する必要はない。例えば、図１２に示すようなテキスト“ＸＭＬ”から抽出された語彙の頻度と、図１１に示すような語彙の頻度とから、“造化”、“化文”、“Ｌ”の順に処理するようなプランを作成してもよい。
【００８９】
また、あるオペレータを実行することで新たに制約が付加される場合もあるが、Ｎグラム方式で分割して得た索引の場合は、１つでも条件を満たさない語彙が存在する場合は、その時点で以後の処理が中断される。
【００９０】
クエリ実行部１２４は、クエリプランニング部１２３が作成したプランに従ってクエリを実行するものであり、索引検索部１２４ａと、検索部１２４ｂとを備えている。
【００９１】
索引検索部１２４ａは、語彙索引の処理を行う語彙索引処理オペレータを実行するものである。
【００９２】
検索部１２４ｂは、残りのオペレータを実行することにより、検索条件を満たす構造化文書を検索するものである。
【００９３】
次に、このように構成された第１の実施の形態にかかる構造化文書検索装置１００による構造化文書格納処理について説明する。図１３は、第１の実施の形態における構造化文書格納処理の全体の流れを示すフローチャートである。
【００９４】
まず、通信部１０１が、クライアント３００から入力データであるＸＭＬ文書を受信する（ステップＳ１３０１）
【００９５】
次に、構造情報抽出部１１１が、入力データを構文解析して木構造の形式に展開し、展開した木構造から構造要素を抽出する（ステップＳ１３０２）。
【００９６】
次に、構造テンプレート決定部１１２が、木構造と構造テンプレート記憶部１３２に格納された構造情報とを参照して、木構造の各ノードに対応する構造要素のＩＤ（ＴＩＤ）を決定する構造テンプレート決定処理を実行する（ステップＳ１３０３）。構造テンプレート決定処理の詳細については後述する。
【００９７】
次に、索引登録部１１３が、語彙索引情報を生成し、転置ファイル記憶部１３３ｂに登録する（ステップＳ１３０４）。転置ファイルに登録する語彙索引情報に必要なＴＩＤ、文書ＩＤ、要素ＩＤ、および発生位置の情報は、構造テンプレート決定処理で取得または算出される。
【００９８】
次に、統計情報更新部１１４が、統計情報記憶部１３３ａの統計情報を更新する（ステップＳ１３０５）。具体的には、統計情報更新部１１４は、テキスト要素の文字列をＮグラム分割して得られた語彙について、統計情報記憶部１３３ａの統計情報の頻度の値を、テキスト要素内での出現回数分加算した値に更新する。
【００９９】
また、統計情報更新部１１４は、構造テンプレート決定処理内で算出されたＴＩＤごとの最小語彙ＩＤ、最大語彙ＩＤ、最大テキストサイズに変更がある場合は、変更後の値で構造テンプレート記憶部１３２の特徴情報（最小語彙ＩＤ、最大語彙ＩＤ）を更新する。
【０１００】
次に、文書登録部１１５が、木構造の各ノードに対して、親子兄弟関係を付加し、表形式で表した構造化文書を構造化文書記憶部１３１に登録する（ステップＳ１３０６）。例えば、図２のようなＸＭＬ文書を入力し、構造情報抽出部１１１により図３に示すような木構造が得られた場合、図４のような情報により木構造を表形式で表した構造化文書が登録される。
【０１０１】
以上が、構造化文書格納処理の全体の流れである。次に、ステップＳ１３０３の構造テンプレート決定処理について説明する。図１４は、第１の実施の形態における構造テンプレート決定処理の全体の流れを示すフローチャートである。
【０１０２】
まず、構造テンプレート決定部１１２は、構造情報抽出部１１１が抽出した構造要素のうち、テキスト要素に対応する構造要素について、当該テキスト要素に対する語彙分割を実行する（ステップＳ１４０１）。語彙分割方法としては、Ｎグラム方式の分割方法を採用する。
【０１０３】
次に、構造テンプレート決定部１１２は、分割した語彙から重複した語彙を削除し、新規の語彙に対しては語彙ＩＤを付加する（ステップＳ１４０２）。なお、既存の語彙の場合は、統計情報記憶部１３３ａから語彙ＩＤを取得する。また、語彙の発生回数は、後に統計情報記憶部１３３ａの頻度を更新する際に利用するのでＲＡＭ（Random Access Memory）などの記憶部（図示せず）に記憶しておく。
【０１０４】
次に、構造テンプレート決定部１１２は、構造テンプレート記憶部１３２に記憶するＴＩＤごとの特徴情報（最大語彙ＩＤ、最小語彙ＩＤ、最大テキストサイズ）を算出する（ステップＳ１４０３）。具体的には、構造テンプレート決定部１１２は、ステップＳ１４０２で付加または取得した語彙ＩＤのうち、最大値を最大語彙ＩＤとし、最小値を最小語彙ＩＤとして算出する。また、対応するテキスト要素の文字列長を最大テキストサイズとして算出する。
【０１０５】
次に、構造テンプレート決定部１１２は、構造テンプレート記憶部１３２を参照し、展開した木構造の構造要素から１つの構造要素を取得し、木構造の構造制約に合致する構造要素を取得する（ステップＳ１４０４）。
【０１０６】
次に、構造テンプレート決定部１１２は、合致する構造要素が取得されたか否かを判断し（ステップＳ１４０５）、取得されなかった場合は（ステップＳ１４０５：ＮＯ）、新規に構造要素を作成する（ステップＳ１４０６）。
【０１０７】
次に、構造テンプレート決定部１１２は、作成した構造要素のＴＩＤを、現在処理している木構造の構造要素に該当するＴＩＤとして設定する（ステップＳ１４０７）。
【０１０８】
ステップＳ１４０５で、合致する構造要素が取得された場合は（ステップＳ１４０５：ＹＥＳ）、構造テンプレート決定部１１２は、取得した構造要素のＴＩＤを、現在処理している木構造の構造要素に該当するＴＩＤとして設定する（ステップＳ１４０８）。
【０１０９】
次に、構造テンプレート決定部１１２は、すべての木構造の構造要素を処理したか否かを判断し（ステップＳ１４０９）、すべての構造要素を処理していない場合は（ステップＳ１４０９：ＮＯ）、次の構造要素について処理を繰り返す（ステップＳ１４０４）。
【０１１０】
すべての構造要素を処理した場合は（ステップＳ１４０９：ＹＥＳ）、構造テンプレート決定処理を終了する。
【０１１１】
次に、このように構成された第１の実施の形態にかかる構造化文書検索装置１００による構造化文書検索処理について説明する。図１５は、第１の実施の形態における構造化文書検索処理の全体の流れを示すフローチャートである。
【０１１２】
まず、通信部１０１が、クライアント３００から検索クエリを受信する（ステップＳ１５０１）。次に、クエリ解析部１２１が、受信した検索クエリを解析し、クエリグラフを作成する（ステップＳ１５０２）。
【０１１３】
次に、制約付加部１２２が、クエリ解析部１２１が作成したクエリグラフに対して制約を付加する制約付加処理を実行する（ステップＳ１５０３）。制約付加処理の詳細については後述する。
【０１１４】
次に、クエリプランニング部１２３が、制約付加部１２２により制約が付加されたクエリグラフを参照し、処理コストが最小になる検索実行のプランを作成する（ステップＳ１５０４）。
【０１１５】
次に、索引検索部１２４ａが、検索処理のうち、語彙索引に関する処理である転置ファイルスキャン処理を実行する（ステップＳ１５０５）。転置ファイルスキャン処理では、付加された制約に従い、検索対象となる索引の候補を絞り込む処理が実行される。転置ファイルスキャン処理の詳細については後述する。
【０１１６】
次に、検索部１２４ｂが、検索処理のうち、転置ファイルスキャン処理以外の残りのプランに該当する処理を実行し、検索条件を満たす構造化文書を検索する（ステップＳ１５０６）。
【０１１７】
次に、通信部１０１が、検索結果である構造化文書をクライアント３００に送信し（ステップＳ１５０７）、構造化文書検索処理を終了する。
【０１１８】
次に、ステップＳ１５０３の制約付加処理の詳細について説明する。図１６は、第１の実施の形態における制約付加処理の全体の流れを示すフローチャートである。
【０１１９】
まず、制約付加部１２２は、クエリグラフの各ノードの構造制約を満たすＴＩＤの候補の集合（以下、ＴＩＤ候補集合という。）を取得する（ステップＳ１６０１）。例えば、図１０に示すようなクエリグラフのノード４に対しては、タイトルタグの下のテキスト要素であることから、図５に示すような構造情報のＴＩＤ７が候補として取得できる。
【０１２０】
なお、ステップＳ１６０１の処理により、構造制約を満たすＴＩＤの候補が取得できる。以下のステップＳ１６０２からステップＳ１６１０では、ＴＩＤの候補から語彙制約を満たさない候補を削除する処理を行う。
【０１２１】
次に、制約付加部１２２は、未処理のノードに対するＴＩＤ候補集合Ｐｉを取得する（ステップＳ１６０２）。この際、特徴情報取得部１２２ａが、各ＴＩＤの候補に対応づけられた最小語彙ＩＤおよび最大語彙ＩＤを構造テンプレート記憶部１３２から取得しておく。
【０１２２】
次に、特徴情報算出部１２２ｂは、Ｐｉに対応する検索キーの語彙を分割する（ステップＳ１６０３）。例えば、図１０のクエリグラフのノード４に対しては、「ftcontains “構造化文書” && “XML”」という検索キーが対応づけられている。このため、制約付加部１２２は、“構造化文書”および“XML”をそれぞれ語彙分割する。語彙分割は、上述のようなＮグラム分割による方法で行う。
【０１２３】
次に、制約付加部１２２は、Ｐｉに対応する論理条件を取得する（ステップＳ１６０４）。例えば、図１０のクエリグラフのノード４の場合は、ＡＮＤ条件（“＆＆”）が取得される。
【０１２４】
次に、制約付加部１２２は、取得した論理条件がＡＮＤ条件のみか否かを判断する（ステップＳ１６０５）。ＡＮＤ条件のみの場合は（ステップＳ１６０５：ＹＥＳ）、Ｐｉの各ＴＩＤ候補のうち、検索キーから分割した語彙の語彙ＩＤのいずれかが、ＴＩＤに対応する最小語彙ＩＤと最大語彙ＩＤとの間の範囲外となるＴＩＤ候補を取得する（ステップＳ１６０６）。
【０１２５】
例えば、検索キーが“構造化文書”の場合、図１１に示すように検索キーから分割した語彙の語彙ＩＤは、２２から２３５の間の値を取る。このため、例えば、図６に示すような構造情報が設定されていた場合を前提とすると、語彙ＩＤの値は、ＴＩＤ７の最小語彙ＩＤ（＝２１）と最大語彙ＩＤ（＝１０４５）との範囲内に収まる。したがって、ＴＩＤ７は本ステップでは取得されない。一方、ＴＩＤ６については、最小語彙ＩＤ（＝２５）と最大語彙ＩＤ（＝１０３）との範囲外となる語彙ＩＤが存在する（語彙ＩＤ＝２２，１７８，２３５）。このため、本ステップではＴＩＤ６が該当するＴＩＤ候補として取得される。
【０１２６】
ステップＳ１６０５で、ＡＮＤ条件のみでないと判断した場合は（ステップＳ１６０５：ＮＯ）、制約付加部１２２は、取得した論理条件がＯＲ条件のみか否かを判断する（ステップＳ１６０７）。ＯＲ条件のみの場合は（ステップＳ１６０７：ＹＥＳ）、Ｐｉの各ＴＩＤ候補のうち、検索キーから分割した語彙の語彙ＩＤのすべてが、ＴＩＤに対応する最小語彙ＩＤと最大語彙ＩＤとの間の範囲外となるＴＩＤ候補を取得する（ステップＳ１６０８）。
【０１２７】
次に、制約付加部１２２は、ステップＳ１６０６またはステップＳ１６０８で、該当するＴＩＤ候補が取得されたか否かを判断する（ステップＳ１６０９）。該当するＴＩＤ候補が取得された場合は（ステップＳ１６０９：ＹＥＳ）、ＴＩＤ候補削除部１２２ｃは、Ｐｉから該当するＴＩＤ候補を削除する（ステップＳ１６１０）。
【０１２８】
このようにして、論理条件がＡＮＤ条件かＯＲ条件かに応じて、ＴＩＤの候補を適切に絞り込むことが可能となる。
【０１２９】
ステップＳ１６０７で、ＯＲ条件のみでないと判断した場合は（ステップＳ１６０７：ＮＯ）、ＴＩＤ候補の削除処理を行わずにステップＳ１６１１以降の位置条件の判定処理を実行する。
【０１３０】
ステップＳ１６１０でＴＩＤ候補を削除した後、または、ステップＳ１６０７でＯＲ条件のみでないと判断した場合は、制約付加部１２２は、Ｐｉに対応する検索キーから、近傍検索などの位置に関する条件指定（位置条件）を取得する（ステップＳ１６１１）。
【０１３１】
次に、制約付加部１２２は、各ＴＩＤ候補が、取得した位置条件を満たすか否かを判断し（ステップＳ１６１２）、満たさない場合は（ステップＳ１６１２：ＮＯ）、該当するＴＩＤ候補をＰｉから削除する（ステップＳ１６１３）。
【０１３２】
例えば、「"XML"&&"データベース" distance at most 5」という位置条件が指定されていた場合、少なくとも１４（＝条件中の文字列の長さ＋間隔の値＝９＋５）文字が、テキスト要素内に存在しなければならない。これに対し、例えば、当該テキスト要素に対応する構造要素のＴＩＤに対応づけられた最大テキストサイズが１４未満であれば、位置条件を満たさないとしてＰｉから削除することができる。
【０１３３】
なお、最大テキストサイズは、構造テンプレート記憶部１３２から取得することができる。このようにして、語彙の位置条件に応じてＴＩＤの候補を絞り込むことが可能となる。
【０１３４】
次に、制約付加部１２２は、すべてのノードを処理したか否かを判断し（ステップＳ１６１４）、すべてのノードを処理していない場合は（ステップＳ１６１４：ＮＯ）、次にノードに対して処理を繰り返す（ステップＳ１６０２）。
【０１３５】
すべてのノードを処理した場合は（ステップＳ１６１４：ＹＥＳ）、制約付加部１２２は、すべてのＴＩＤ候補集合内のＴＩＤに対して、同一文書内に存在しなければならないＴＩＤ間の関係を取得し、同一文書制約として付加する（ステップＳ１６１５）。
【０１３６】
例えば、図１０のようなクエリグラフの場合、ノード４およびノード６に対応するＴＩＤ＝７およびＴＩＤ＝５は、それぞれ「特許」文書（ＴＩＤ＝４）内に存在しなければならないため、同一文書制約が付加される。なお、以下では、同一文書制約を「ＴＩＤ７＜−＞ＴＩＤ５」のような形式で記述する。
【０１３７】
このように、制約付加処理では、構造制約だけでなく、構造化文書の登録時に格納されたテキスト要素の語彙の特徴を表す特徴情報で表される語彙制約により、中間候補であるＴＩＤの候補数を絞り込むことができる。このため、構造化文書に対する高速な全文検索機能を実現することができる。
【０１３８】
次に、ステップＳ１５０５の転置ファイルスキャン処理の詳細について説明する。図１７は、第１の実施の形態における転置ファイルスキャン処理の全体の流れを示すフローチャートである。
【０１３９】
まず、索引検索部１２４ａは、制約付加部１２２により付加された構造制約Ｔと、検索キーから分割した語彙（以下、検索語彙という。）の語彙ＩＤの集合Ｇとを取得する（ステップＳ１７０１）。
【０１４０】
次に、索引検索部１２４ａは、クエリプランニング部１２３が作成したプランに従い、クエリを実行するノードを取得する（ステップＳ１７０２）。例えば、最初の処理では、頻度が最も小さい検索語彙に対応するノードを取得する。
【０１４１】
次に、索引検索部１２４ａは、検索語彙に対応する転置ファイルを、転置ファイル記憶部１３３ｂから取得する（ステップＳ１７０３）。具体的には、検索語彙の語彙ＩＤに対応する転置ファイル番号を統計情報記憶部１３３ａから取得し、取得した転置ファイル番号で識別される転置ファイルを、転置ファイル記憶部１３３ｂから取得する。
【０１４２】
次に、索引検索部１２４ａは、転置ファイルから語彙索引情報を取り出す（ステップＳ１７０４）。次に、索引検索部１２４ａは、語彙索引情報のＴＩＤが、構造制約Ｔに含まれるか否かを判断する（ステップＳ１７０５）。
【０１４３】
構造制約Ｔに含まれる場合は（ステップＳ１７０５：ＹＥＳ）、索引検索部１２４ａは、現在の語彙索引情報を索引の候補集合に追加する（ステップＳ１７０６）。
【０１４４】
ステップＳ１７０６で候補集合に追加した後、または、ステップＳ１７０５で、語彙索引情報のＴＩＤが構造制約Ｔに含まれないと判断した場合は（ステップＳ１７０５：ＮＯ）、索引検索部１２４ａは、すべての語彙索引情報を処理したか否かを判断する（ステップＳ１７０７）。
【０１４５】
すべての語彙索引情報を処理していない場合は（ステップＳ１７０７：ＮＯ）、転置ファイルから次の語彙索引情報を取得して処理を繰り返す（ステップＳ１７０４）。
【０１４６】
すべての語彙索引情報を処理した場合は（ステップＳ１７０７：ＹＥＳ）、索引検索部１２４ａは、すべての検索語彙を処理したか否かを判断する（ステップＳ１７０８）。すべての検索語彙を処理していない場合は（ステップＳ１７０８：ＮＯ）、次の検索語彙に対して処理を繰り返す（ステップＳ１７０３）。
【０１４７】
すべての検索語彙を処理した場合は（ステップＳ１７０８：ＹＥＳ）、索引検索部１２４ａは、すべてのノードを処理したか否かを判断する（ステップＳ１７０９）。すべてのノードを処理していない場合は（ステップＳ１７０９：ＮＯ）、次のノードを取得して処理を繰り返す（ステップＳ１７０２）。
【０１４８】
すべてのノードを処理した場合は（ステップＳ１７０９：ＹＥＳ）、転置ファイルスキャン処理を終了する。
【０１４９】
なお、上述のような処理で得られた索引の候補集合に含まれるＴＩＤから、重複を排除してＴＩＤ集合が作成され、作成されたＴＩＤ集合は次のオペレータ処理を実行する際の新たな制約条件として利用される。
【０１５０】
次に、第１の実施の形態にかかる構造化文書検索装置１００による構造化文書検索処理の具体例について説明する。図１８は、構造テンプレート記憶部１３２に記憶されている構造情報の一例を示す説明図である。また、図１９は、入力された検索クエリの一例を示す説明図である。
【０１５１】
以下では、図６および図１８に示すような構造情報が構造テンプレート記憶部１３２に記憶されており、図１９に示すような検索クエリが入力された場合の構造化文書検索処理について説明する。
【０１５２】
図１９に示す検索クエリは、ＸＱＦＴの言語規格に従い記述されたクエリである。また、本クエリは、“「タイトル」要素の候補として、「構造化文書」かつ「XML」を含み、かつ両者が２文字以内の距離に存在するという制約を満たし、さらに「発明者」要素に「田中」を含む特許文書を検索せよ”、という検索条件を意味する。
【０１５３】
図２０は、検索クエリを解析した結果であるクエリグラフの一例を示す説明図である。同図は、図１９の検索クエリを解析した結果のクエリグラフを表す。構造制約としては、以下に示すような４つの制約（Ａ１〜Ａ４）が付加される。
Ａ１：ノード６（ＴＩＤ１１、ＴＩＤ１９）→田中
Ａ２：ノード４（ＴＩＤ６、ＴＩＤ７、ＴＩＤ１５）→ＸＭＬ
Ａ３：ノード４（ＴＩＤ６、ＴＩＤ７、ＴＩＤ１５）→構造化文書
Ａ４：ノード４とノード６は同一文書制約を満たす
【０１５４】
なお、例えば、“ノード６（ＴＩＤ１１、ＴＩＤ１９）→田中”とは、ノード６は構造要素の候補がＴＩＤ１１またはＴＩＤ１９でなければならないこと、および、対応するテキストの検索キーとして「田中」が設定されていることを表している。
【０１５５】
また、Ａ４は同一文書制約の構造制約を表し、例えば、ノード４がＴＩＤ６のときは、ノード６にはＴＩＤ１１が存在しなければならない制約である。したがって、Ａ４の同一文書制約は、「｛ＴＩＤ６、ＴＩＤ７｝＜−＞｛ＴＩＤ１１｝」および「｛ＴＩＤ１５｝＜−＞｛ＴＩＤ１９｝」と表すこともできる。
【０１５６】
また、語彙制約としては以下に示すような２つの制約（Ｂ１、Ｂ２）が付加される。
Ｂ１：ノード４には、「構造」、「造化」、「化文」、「文書」、「書」、「ＸＭＬ」、「ＭＬ」、「Ｌ」に対応する語彙ＩＤをすべて含む
Ｂ１：ノード６には、「田中」、「中」に対応する語彙ＩＤを含む
【０１５７】
なお、ftcontainsなど部分一致検索の場合は、Ｎグラム以下の文字列長の語彙に関しては条件に加えないが、ここでは説明の都合上付加している。
【０１５８】
例えば、検索キー「構造化文書」に対する検索語彙は図１１に示すように分割されるため、語彙ＩＤの分布は｛２２，３２，５５，１７８，２３５｝となる。
【０１５９】
ＴＩＤ６の最小語彙ＩＤは図６より２５であり、２５より小さい語彙ＩＤ（２２）が存在するためＴＩＤ６は候補から削除される（ステップＳ１６０９：ＹＥＳ、ステップＳ１６１０）。ＴＩＤ７およびＴＩＤ１５は制約を満たすため（ステップＳ１６０９：ＮＯ）、候補から削除されない。
【０１６０】
同様に、検索キー「ＸＭＬ」に対する検索語彙の語彙ＩＤの分布は｛４３，５８，１２３｝であり、ＴＩＤ７、ＴＩＤ１５は制約を満たすため候補から削除されない。
【０１６１】
ノード６に対しても同様に検索語彙である「田中」および「中」の語彙ＩＤと、ＴＩＤ１１およびＴＩＤ１９に対応する最小語彙ＩＤおよび最大語彙ＩＤとが比較される。ここでは、両者ともに候補として残されたことを前提とする。
【０１６２】
また、位置条件による制約として、以下のような制約（Ｃ１）が付加される。
Ｃ１：ノード４は、「構造化文書」と「ＸＭＬ」とが２文字以上離れた距離に存在する
【０１６３】
この場合、ノード４に対応するテキストのテキストサイズとして少なくとも１０（＝「構造化文書」のサイズ＋「ＸＭＬ」のサイズ＋２＝５＋３＋２）文字が必要となるため、例えば、対応する最大テキストサイズが１０未満であるＴＩＤ候補が存在すれば、この段階で除外することができる（ステップＳ１６１３）。
【０１６４】
図２１は、このような処理により候補が絞り込まれた状態における、クエリグラフの一例を示す説明図である。図２０と比較して、図２１では、ノード４に対するＴＩＤ候補が、ＴＩＤ７、ＴＩＤ１５に絞り込まれていることが示されている。
【０１６５】
このようにして制約付加部１２２で制約を求めた後、クエリプランニング部１２３によるクエリプランニング処理が実行される。クエリプランニング部１２３は、頻度が低い検索語彙を優先的に処理するようなプランを作成する。
【０１６６】
図２２は、検索語彙ごと頻度を示した説明図である。同図に示すように、語彙「田中」に対する頻度が最も低い（２０）ので、当該語彙に対応するノードから転置ファイルスキャン処理を実行する（ステップＳ１７０２）。
【０１６７】
このように、第１の実施の形態にかかる構造化文書検索装置では、構造化文書の構造要素ごとに対応する要素の特徴を表す特徴情報を格納し、当該特徴情報を参照して転置ファイルスキャン時に不要な語彙索引情報の読み出し数を早い段階で削減することが可能となる。その結果、語彙の出現位置レベルまで考慮した検索条件による検索時に必要となる候補の結合処理コストを削減することを可能とする。このため、ＸＱＦＴのような位置情報を指定と構造制約と組み合わせたクエリによる構造化文書の全文検索機能を高速に実行することができる。
【０１６８】
（第２の実施の形態）
第２の実施の形態にかかる構造化文書検索装置は、語彙索引情報内に、対応するテキスト要素に含まれる語彙の特徴を表す特徴値を格納し、転置ファイルスキャン処理時に参照して候補数を絞り込むことにより、さらに高速な検索を可能とするものである。
【０１６９】
第２の実施の形態では、転置ファイル記憶部１３３ｂに、テキスト要素に含まれる語彙から算出された特徴値を対応づけた語彙索引情報を含む転置ファイルを格納する点が、第１の実施の形態と異なっている。特徴値は、構造テンプレート決定部１１２により、構造テンプレート決定処理内で算出される。
【０１７０】
また、第２の実施の形態では、転置ファイルスキャン処理時に、索引検索部１２４ａが、特徴値を参照して索引の候補を絞り込む点が、第１の実施の形態と異なっている。
【０１７１】
図２３は、第２の実施の形態における転置ファイル記憶部１３３ｂに格納された転置ファイルのデータ構造の一例を示す説明図である。
【０１７２】
同図に示すように、転置ファイル記憶部１３３ｂの転置ファイルは、ＴＩＤと、特徴値と、文書ＩＤと、要素ＩＤと、発生位置とを対応づけた語彙索引情報を格納している。
【０１７３】
特徴値とは、文書ＩＤと要素ＩＤとで識別される構造化文書の要素の特徴を表す情報であり、構造テンプレート決定部１１２により算出される。
【０１７４】
第２の実施の形態における構造テンプレート決定部１１２は、構造化文書のテキスト要素に対する特徴値を算出する処理を行う。特徴値は、テキストに含まれる語彙の語彙ＩＤの最小値および最大値である最小語彙ＩＤおよび最大語彙ＩＤから算出する。具体的には、最小語彙ＩＤと最大語彙ＩＤとを変換係数α（例えば、１０）で除算した値を特徴値として算出する。
【０１７５】
例えば、テキストに含まれる語彙の最小語彙ＩＤが２２、最大語彙ＩＤが３０１であった場合、それらをそれぞれα＝１０で除算した結果である（２、３０）が、当該テキストの特徴値として算出される。
【０１７６】
なお、特徴値の算出方法はこれに限られるものではなく、テキストの特徴を表す情報であればあらゆる方法により算出することができる。例えば、英数字や記号などの文字コード値を利用する方法、予め文字列パターンを複数用意しておき、いずれのパターンに含まれるかをパターン番号によって指定する方法を適用可能である。
【０１７７】
第２の実施の形態における索引検索部１２４ａは、語彙索引の処理時、特徴値を参照して索引の候補を絞り込む処理を行う。具体的には、索引検索部１２４ａは、検索キーに含まれる語彙の語彙ＩＤに、特徴値算出時と同様の変換処理を行い、候補である語彙索引情報の特徴値の範囲内に変換後の語彙ＩＤの値が含まれない場合に、当該語彙索引情報を索引の候補から除外する。なお、特徴値の範囲とは、例えば特徴値が（２、３０）の場合、２以上３０以下の範囲をいう。
【０１７８】
次に、このように構成された第２の実施の形態にかかる構造化文書検索装置による構造テンプレート決定処理について説明する。図２４は、第２の実施の形態における構造テンプレート決定処理の全体の流れを示すフローチャートである。
【０１７９】
第２の実施の形態では、テキスト要素の特徴値を算出する処理がステップＳ２４０４に挿入された点が、第１の実施の形態と異なっている。その他の処理は、第１の実施の形態と同様の処理なので、その説明を省略する。
【０１８０】
ステップＳ２４０４では、構造テンプレート決定部１１２が、ステップＳ２４０３で算出した最大語彙ＩＤ、最小語彙ＩＤからテキストの特徴値を算出する（ステップＳ２４０４）。
【０１８１】
図２５は、算出された特徴値を説明するための説明図である。同図は、“ＸＭＬデータベース”というテキストについて算出された特徴値を表す図である。
【０１８２】
なお、同図は説明のために、統計情報記憶部１３３ａの情報の一部（語彙、語彙ＩＤ）と、転置ファイル記憶部１３３ｂの情報（発生位置、特徴値、文書ＩＤ、要素ＩＤ、ＴＩＤ）とを対応づけた情報を表している。
【０１８３】
同図に示す例では、語彙“データ”の語彙ＩＤ＝１２が最小語彙ＩＤであり、語彙“タベー”の語彙ＩＤ＝１４７が最大語彙ＩＤである。したがって、最小語彙ＩＤおよび最大語彙ＩＤを変換係数α＝１０で除算して並べた値（１，１４）が特徴値として算出されている。
【０１８４】
このようにして算出された特徴値は、最終的に転置ファイル記憶部１３３ｂの転置ファイル内に格納される。上記例では、文書ＩＤ、要素ＩＤ、ＴＩＤ、および特徴値が同一で、発生位置が異なる９個の語彙索引情報が、新たに転置ファイルに格納される。
【０１８５】
なお、同一テキスト要素内に複数回数発生する語彙に関しては、語彙ＩＤの分布を複数の区間に分割して特徴値を算出するように構成してもよい。図２６は、このような構成で算出された特徴値を説明するための説明図である。同図は、“文書と文書の関係”というテキストについて算出された特徴値を表す図である。
【０１８６】
この例では、“文書”という語彙が同一テキスト中に２回発生するので、語彙ＩＤ分布（２２，２２，２６，５５，１０３，１７８，２３５，３０１）を２区間（２２，２２，２６，５５）および（１０３，１７８，２３５，３０１）に分割する。そして、分割した区間それぞれで算出した特徴値（２，５）および（１０，３０）を、それぞれ語彙“文書”に対応づけて格納している。
【０１８７】
この場合は、図２５と異なり、語彙“文書”に対しては特徴値が（２，５）または（１０，３０）、その他の語彙に対しては特徴値が（２，３０）である８つの語彙索引情報が転置ファイルに格納される。
【０１８８】
このように、発生頻度が高く、処理コストが高くなるような語彙に関しては、より詳細な特徴値を付与できるため、特徴値による絞込みの精度が向上するという効果が得られる。
【０１８９】
次に、このように構成された第２の実施の形態にかかる構造化文書検索装置による転置ファイルスキャン処理について説明する。図２７は、第２の実施の形態における転置ファイルスキャン処理の全体の流れを示すフローチャートである。
【０１９０】
ステップＳ２７０１からステップＳ２７０５までの、ノード取得処理、転置ファイル取得処理、語彙索引情報取得処理は、第２の実施の形態にかかる構造化文書検索装置におけるステップＳ１７０１からステップＳ１７０５までと同様の処理なので、その説明を省略する。
【０１９１】
ステップＳ２７０５で、語彙索引情報のＴＩＤが構造制約Ｔに含まれると判断した場合は（ステップＳ２７０５：ＹＥＳ）、索引検索部１２４ａは、語彙索引情報内の特徴値の範囲と比較するため、集合Ｇ内の語彙ＩＤの値を変換する（ステップＳ２７０６）。具体的には、特徴値を算出する際に用いる変換係数αで、検索語彙の語彙ＩＤの値を除算する。例えば、検索語彙の語彙ＩＤが１００であったとすると、変換係数α＝１０で除算することにより、語彙ＩＤの値が１０に変換される。
【０１９２】
次に、索引検索部１２４ａは、語彙索引情報内の特徴値の範囲内に、変換した語彙ＩＤの値が含まれるか否かを判断する（ステップＳ２７０７）。例えば、特徴値が（２，５）であり、変換した語彙ＩＤの値が１０であった場合は、範囲内（２から５の間）に含まれないと判断する。
【０１９３】
語彙索引情報内の特徴値の範囲内に、変換した語彙ＩＤの値が含まれると判断した場合は（ステップＳ２７０７：ＹＥＳ）、索引検索部１２４ａは、現在の語彙索引情報を索引の候補集合に追加する（ステップＳ２７０８）。
【０１９４】
なお、変換処理のコスト、候補件数の関係などを考慮した処理コストに応じて特徴値による判定の可否を決定するように構成してもよいし、特徴値のうちのある１つの値（最小値または最大値）だけを利用するように構成してもよい。
【０１９５】
ステップＳ２７０９からステップＳ２７１１までの、終了判定処理は、第２の実施の形態にかかる構造化文書検索装置におけるステップＳ１７０７からステップＳ１７０９までと同様の処理なので、その説明を省略する。
【０１９６】
このように、転置ファイルスキャン処理では、索引作成時に転置ファイルに登録されたテキストの特徴値を参照し、検索条件に含まれる語彙から算出した特徴値に相当する値が、索引の特徴値に適合しない場合に、当該索引を候補から除外することができる。このため、語彙索引処理時の候補数をさらに絞り込むことができ、構造化文書に対する高速な全文検索機能を実現することができる。
【０１９７】
ここで、転置ファイルスキャン処理で処理されるデータの具体例について説明する。図２８は、転置ファイルスキャン処理で処理される候補の一例を示す説明図である。同図は、構造制約Ｔとして｛ＴＩＤ７、ＴＩＤ１１｝（ＴＩＤ７とＴＩＤ１１が構造制約を満たす構造要素のＴＩＤであることを表す）が取得され、語彙ＩＤ集合Ｇとして｛１３５、２９２、３５６｝が取得された場合を前提としている（ステップＳ２７０１）。
【０１９８】
なお、検索キーとしては“ＸＭＬ”が指定されたことを前提とする。したがって、語彙ＩＤ集合Ｇは、それぞれ語彙“ＸＭＬ”、語彙“ＭＬ”、語彙“Ｌ”に対応する語彙ＩＤを含んでいる。
【０１９９】
さらに、同図では、語彙“ＸＭＬ”に対応する転置ファイルとして５つのＴＩＤの語彙索引情報を含む転置ファイルが転置ファイル記憶部１３３ｂに記憶されていることを前提とする。なお、同図では、語彙索引情報のうち、要素ＩＤと発生位置とは省略している。
【０２００】
上記のような前提では、構造制約条件により、転置ファイルのＴＩＤは３件に絞り込まれる（ステップＳ２７０４）。また、集合Ｇ内の語彙ＩＤの変換値は、それぞれ１３，２９，３５となるため（ステップＳ２７０５）、これらの変換値が特徴値の範囲外となる文書ＩＤ＝２００の語彙索引情報が除外される（ステップＳ２７０７）。
【０２０１】
このように、構造制約のみによれば候補はＴＩＤ７とＴＩＤ１１であるが、特徴値を参照することにより、ＴＩＤ７に対応する索引のみに候補を絞り込むことができる。
【０２０２】
次に、処理を繰り返すことにより制約がさらに絞り込まれる例について説明する。図２９、図３０は、転置ファイルスキャン処理で処理される候補の別の一例を示す説明図である。
【０２０３】
この例では、図１８のような構造情報が構造テンプレート記憶部１３２に記憶されていることを前提とする。
【０２０４】
この状態で、転置ファイル１のスキャンによりＴＩＤ７、ＴＩＤ１５の候補が、ＴＩＤ１５の候補のみに絞り込まれ（図２９）、次に構造制約｛ＴＩＤ１１、ＴＩＤ１９｝を処理すると仮定する（図３０）。
【０２０５】
この場合、ＴＩＤ１１とＴＩＤ１９とのうち、図１８に示すような構造情報でＴＩＤ１５と同一文書制約を満たすＴＩＤはＴＩＤ１９のみであるので、ＴＩＤ１１に関する索引情報は読み出す必要がない（ステップＳ２７０５：ＮＯ）。したがって、転置ファイル２ではＴＩＤ１９を持つ文書ＩＤ＝６２の語彙索引情報だけを候補とすればよい。
【０２０６】
次に、第２の実施の形態にかかる構造化文書検索装置による構造化文書検索処理の具体例について説明する。
【０２０７】
ここでは、第１の実施の形態で図１８から図２２を用いて説明した構造化文書検索処理の具体例を前提として説明する。すなわち、図１８から図２２で説明した処理により、図２１のようなクエリグラフが生成され、当該クエリグラフ内の検索語彙の頻度が図２２のような値を取っていることを前提とする。
【０２０８】
図３１は、このときの転置ファイルスキャン処理で処理される候補の一例を示す説明図である。索引検索部１２４ａで、[ＴＩＤ１１,ＴＩＤ１９]を構造制約として転置ファイルスキャン処理を行なった結果、候補集合としてＴＩＤ１１のみが残されたとする。
【０２０９】
ＴＩＤ１１の候補は３つ存在するが、文書ＩＤ＝２００の候補については、特徴値の比較により候補から削除される。「田中」の語彙ＩＤが１３６であるとすると、変換した語彙ＩＤの値は１３となり（ステップＳ１７０６）、特徴値である８０から９０の範囲内に含まれないためである。
【０２１０】
また、構造制約からＴＩＤ１９が除外されていることから、同一文書制約「｛ＴＩＤ１５｝＜−＞｛ＴＩＤ１９｝」に従い、ＴＩＤ１５も候補から除外される。したがって、この後に処理されるノード４では、ＴＩＤ１５を除いたＴＩＤ７のみを構造制約として候補を抽出すればよい。
【０２１１】
図３２は、このときの転置ファイルスキャン処理で処理される候補の一例を示す説明図である。
【０２１２】
ノード４では、最も頻度が低い語彙「造化」に対する処理を実行する。この場合も、特徴値による絞込みにより、結果的に文書ＩＤ＝４３に対応する１件の候補だけが抽出される。「造化」は、「構造化文書」を構成する語彙の１つであるので、この場合は索引から位置情報まで含めた形で残しておき、次の処理に利用する。
【０２１３】
このように、第２の実施の形態にかかる構造化文書検索装置では、語彙索引情報内にテキスト要素に含まれる語彙の特徴を表す特徴値を格納し、転置ファイルスキャン処理時に参照して候補数を絞り込むことができる。このため、ＸＱＦＴのような位置情報を指定と構造制約と組み合わせたクエリによる構造化文書の全文検索機能をさらに高速に実行することができる。
【０２１４】
（第３の実施の形態）
第３の実施の形態にかかる構造化文書検索装置は、構造要素ごとに特徴情報に基づく分割ルールを定め、構造要素に対応する要素の値の特徴情報が分割ルールに適合する場合に、当該構造要素を分割して新たな構造要素を作成して構造テンプレート記憶部１３２を更新するものである。
【０２１５】
第３の実施の形態では、構造テンプレート記憶部１３２に構造要素ごとの分割ルールを設定する点が、第２の実施の形態と異なっている。また、構造化文書登録処理時に、構造テンプレート決定部１１２が、当該分割ルールを参照して構造テンプレート記憶部１３２に格納されている構造要素を分割して新たな構造要素を作成する点が、第２の実施の形態と異なっている。
【０２１６】
図３３は、第３の実施の形態における構造テンプレート記憶部１３２に格納された構造情報のデータ構造の一例を示す説明図である。同図は、構造情報を表形式で表した例を示している。
【０２１７】
同図に示すように、第３の実施の形態では、構造情報に、要素内最大発生語彙数と、テキストサイズの閾値を超えた回数と、基準情報と、分割方法とをさらに対応づけて格納している。基準情報と、分割方法とにより分割ルールが指定される。
【０２１８】
要素内最大発生語彙数とは、対応するテキスト要素内に発生する各語彙の出現数のうち最大値をいう。テキストサイズの閾値を超えた回数とは、予め定められたテキストサイズの閾値（例えば、１００文字）を超えた回数をいう。
【０２１９】
基準情報には、分割の判断に適用する情報を設定する。例えば、構造要素ごとの特徴情報である最小語彙ＩＤ、最大語彙ＩＤ、最大テキストサイズ、要素内最大発生語彙数、およびテキストサイズの閾値を超えた回数などを設定することができる。また、これ以外に、頻出語彙などを判断基準とすることも可能である。同図では、語彙ＩＤ＝２２または４００の頻出語彙を抽出し、基準情報として設定された例が示されている。
【０２２０】
また、分割条件には、基準情報に設定された情報が満たす条件を設定する。基準情報に設定された情報が分割条件を満たした場合に、対応する構造要素を分割する。同図では、頻出語彙として定められた語彙ＩＤ＝２２または４００の語彙の出現回数が予め定められた閾値である３０を超えたことが分割条件として設定された例が示されている。
【０２２１】
なお、基準情報は、処理負荷を低減するため、計算量が小さい特徴情報を用いるのが望ましい。また、初期段階では基準情報や分割条件を設定しないように構成してもよいし、デフォルトの値を設定するように構成してもよい。
【０２２２】
この他、例えば、テキストサイズの閾値（１００）を超えた回数を基準情報とし、当該回数が１０を超えたことを分割条件として構造要素を分割するように構成してもよい。この場合、分割の方法としては、例えば、テキストサイズが１００以上のテキスト要素と、テキストサイズが９９以下のテキスト要素とを分離するように２つの構造要素に分割する方法を適用する。
【０２２３】
このように、例えば、ある語彙が同一テキスト要素内で発生する回数が多い場合は、クエリ処理で性能劣化を招く可能性があると判断して、登録時に事前に構造テンプレートの構造要素を分割することができる。このため、転置ファイルスキャン処理の段階で候補を早期に絞り込むことが可能となる。
【０２２４】
第３の実施の形態における構造テンプレート決定部１１２は、ＴＩＤの決定および特徴値の算出機能に加え、ＴＩＤが分割条件を満たすか否かを判断して分割条件を満たす場合にＴＩＤを分割し、分割したＴＩＤを該当するＴＩＤとして決定する処理を行うものである。
【０２２５】
すなわち、構造テンプレート決定部１１２は、構造情報のみによってＴＩＤを決定するのではなく、対応するテキストの特徴情報に応じて構造要素を分割する場合がある。そして、構造テンプレート決定部１１２は、分割することにより新規に作成した構造要素を構造化文書の木構造のノードに対応する構造要素として決定する。
【０２２６】
次に、このように構成された第３の実施の形態にかかる構造化文書検索装置によるテンプレート決定処理について説明する。図３４は、第３の実施の形態におけるテンプレート決定処理の全体の流れを示すフローチャートである。
【０２２７】
ステップＳ３４０１からステップＳ３４０２までの、語彙分割処理、語彙ＩＤ付加処理は、第２の実施の形態にかかる構造化文書検索装置におけるステップＳ２４０１からステップＳ２４０２までと同様の処理なので、その説明を省略する。
【０２２８】
語彙ＩＤを付加した後、構造テンプレート決定部１１２は、構造テンプレート記憶部１３２に記憶するＴＩＤごとの特徴情報（最大語彙ＩＤ、最小語彙ＩＤ、最大テキストサイズ、要素内最大発生語彙数、テキストサイズの閾値を超えた回数）を算出する（ステップＳ３４０３）。例えば、テキスト要素内の語彙のうち、出現回数が最も多い語彙の出現関数を要素内最大発生語彙数として算出する。
【０２２９】
ステップＳ３４０４からステップＳ３４０６までの特徴値算出処理、構造要素取得処理は、第２の実施の形態にかかる構造化文書検索装置におけるステップＳ２４０４からステップＳ２４０６までと同様の処理なので、その説明を省略する。
【０２３０】
ステップＳ３４０６で、構造要素が取得されなかった場合は（ステップＳ３４０６：ＮＯ）、構造テンプレート決定部１１２は、新規に構造要素を作成し、デフォルトの基準情報と分割条件とを設定して構造テンプレート記憶部１３２に登録する（ステップＳ３４０７）。
【０２３１】
次に、構造テンプレート決定部１１２は、作成した構造要素のＴＩＤを、現在処理している木構造の構造要素に該当するＴＩＤとして設定する（ステップＳ３４０８）。
【０２３２】
ステップＳ３４０６で、構造要素が取得された場合は（ステップＳ３４０６：ＹＥＳ）、構造テンプレート決定部１１２は、構造要素に対応する特徴情報に従い最も適合する構造要素を選択する（ステップＳ３４０９）。なお、この処理は、構造要素が複数取得された場合に、いずれかの構造要素を選択するために実行する処理であるため、構造要素が１つのみ取得された場合には実行しない。
【０２３３】
例えば、図１８および図３３に示すような構造情報が構造テンプレート記憶部１３２に記憶されており、タイトルタグ下のテキスト要素に対応する構造要素としてＴＩＤ６およびＴＩＤ７が取得されたとする。この場合、例えば、テキスト要素に“文書”が含まれるならば、“文書”の語彙ＩＤが２２であるため、当該語彙ＩＤを最小語彙ＩＤと最大語彙ＩＤとの間に含むＴＩＤ７が最も適合する構造要素として選択される。
【０２３４】
次に、構造テンプレート決定部１１２は、構造テンプレート記憶部１３２を参照し、選択した構造要素に対応する基準情報と分割条件を取得する（ステップＳ３４１０）。
【０２３５】
次に、構造テンプレート決定部１１２は、取得した基準情報と分割条件、および、ステップＳ３４０３で算出した特徴情報を参照し、構造要素が分割条件を満たすか否かを判断する（ステップＳ３４１１）。
【０２３６】
分割条件を満たさない場合は（ステップＳ３４１１：ＮＯ）、ステップＳ３４０９で選択した構造要素のＴＩＤを、現在処理している木構造の構造要素に該当するＴＩＤとして設定する（ステップＳ３４１２）。
【０２３７】
分割条件を満たす場合は（ステップＳ３４１１：ＹＥＳ）、構造テンプレート決定部１１２は、新規に構造要素を作成し、デフォルトの基準情報と分割条件とを設定して構造テンプレート記憶部１３２に登録する（ステップＳ３４０７）。
【０２３８】
ステップＳ３４１３の終了確認処理は、第２の実施の形態にかかる構造化文書検索装置におけるステップＳ２４１０と同様の処理なので、その説明を省略する。
【０２３９】
次に、第３の実施の形態にかかる構造化文書検索装置による構造化文書登録処理の具体例について説明する。
【０２４０】
図３５は、構造テンプレート記憶部１３２に格納された構造情報の一例を示す説明図である。また、図３６および図３７は、登録する構造化文書の一例を示す説明図である。
【０２４１】
ここでは、図３３および図３５に示すような構造情報が構造テンプレート記憶部１３２に格納されている状態を前提とし、図３６および図３７で示すような構造化文書を登録する例について説明する。なお、以下ではタイトル要素に対する処理に着目して説明する。
【０２４２】
タイトル要素については、図３５のような構造情報から、２つの構造要素の候補が取得される（ステップＳ３４０５、ステップＳ３４０６：ＹＥＳ）。そこで、構造テンプレート決定部１１２は、構造要素に対応する特徴情報に従い最も適合する構造要素を選択する（ステップＳ３４０９）。
【０２４３】
この例では、テキスト要素内に語彙“文書”（語彙ＩＤ＝２２）を含むため、当該語彙ＩＤを最小語彙ＩＤと最大語彙ＩＤとの間に含むＴＩＤ７が最も適合する構造要素として選択される。
【０２４４】
次に、構造テンプレート決定部１１２は、構造要素の分割条件を満たすか否かを判断する（ステップＳ３４１１）。ここでは、テキスト要素に頻出語彙である語彙ＩＤ＝２２の語彙“文書”を２つ含むため、出現回数３０以上であるという分割条件を満たしたと仮定する（ステップＳ３４１１：ＹＥＳ）。
【０２４５】
この場合は、構造テンプレート決定部１１２は、ＴＩＤ７を分割し、新規に構造要素を作成する（ステップＳ３４０７）。分割は、タイトルタグ下のテキスト要素に対応する構造要素のみを分割してもよいし、親要素も含めて新たな構造要素を作成して分割してもよい。
【０２４６】
図３８は、分割後の構造テンプレート記憶部１３２に格納された構造情報の一例を示す説明図である。同図は、親要素である特許文書を含めて構造要素を分割した例を示している。
【０２４７】
このように、第３の実施の形態にかかる構造化文書検索装置では、構造要素ごとに特徴情報に基づく分割ルールを定め、構造要素に対応する要素の値の特徴情報が分割ルールに適合する場合に、当該構造要素を分割して新たな構造要素を作成して構造テンプレート記憶部を更新することができる。これにより、処理候補数が増大し、検索処理のボトルネックとなりうる部分を予め検出して構造要素を分割することができる。このため、転置ファイルスキャン処理の段階で候補を早期に絞り込むことが可能となる。
【産業上の利用可能性】
【０２４８】
以上のように、本発明にかかる構造化文書検索装置および構造化文書検索方法は、異なる文書構造の複数の構造化文書を、階層化された論理構造を持つ構造化文書データベースで管理し、かつ全文検索処理のような位置情報を条件に指定した検索を行う構造化文書検索装置および構造化文書検索方法に適している。
【図面の簡単な説明】
【０２４９】
【図１】第１の実施の形態にかかる構造化文書検索装置の構成を示すブロック図である。
【図２】ＸＭＬで記述された構造化文書の一例を示す説明図である。
【図３】構造化文書記憶部に格納された構造化文書のデータ構造の一例を示す説明図である。
【図４】表形式で表した構造化文書のデータ構造の一例を示す説明図である。
【図５】第１の実施の形態における構造テンプレート記憶部に格納された構造情報のデータ構造の一例を示す説明図である。
【図６】表形式で表した構造テンプレート記憶部のデータ構造の一例を示す説明図である。
【図７】統計情報記憶部に格納された統計情報のデータ構造の一例を示す説明図である。
【図８】転置ファイル記憶部に格納された転置ファイルのデータ構造の一例を示す説明図である。
【図９】検索クエリの一例を示す説明図である。
【図１０】クエリグラフの一例を示す説明図である。
【図１１】処理コスト計算で用いられる語彙の頻度情報の一例を示した説明図である。
【図１２】処理コスト計算で用いられる語彙の頻度情報の一例を示した説明図である。
【図１３】第１の実施の形態における構造化文書格納処理の全体の流れを示すフローチャートである。
【図１４】第１の実施の形態における構造テンプレート決定処理の全体の流れを示すフローチャートである。
【図１５】第１の実施の形態における構造化文書検索処理の全体の流れを示すフローチャートである。
【図１６】第１の実施の形態における制約付加処理の全体の流れを示すフローチャートである。
【図１７】第１の実施の形態における転置ファイルスキャン処理の全体の流れを示すフローチャートである。
【図１８】構造テンプレート記憶部に記憶されている構造情報の一例を示す説明図である。
【図１９】入力された検索クエリの一例を示す説明図である。
【図２０】検索クエリを解析した結果であるクエリグラフの一例を示す説明図である。
【図２１】クエリグラフの一例を示す説明図である。
【図２２】検索語彙ごと頻度を示した説明図である。
【図２３】第２の実施の形態における転置ファイル記憶部に格納された転置ファイルのデータ構造の一例を示す説明図である。
【図２４】第２の実施の形態における構造テンプレート決定処理の全体の流れを示すフローチャートである。
【図２５】算出された特徴値を説明するための説明図である。
【図２６】特徴値を説明するための説明図である。
【図２７】第２の実施の形態における転置ファイルスキャン処理の全体の流れを示すフローチャートである。
【図２８】転置ファイルスキャン処理で処理される候補の一例を示す説明図である。
【図２９】転置ファイルスキャン処理で処理される候補の別の一例を示す説明図である。
【図３０】転置ファイルスキャン処理で処理される候補の別の一例を示す説明図である。
【図３１】転置ファイルスキャン処理で処理される候補の一例を示す説明図である。
【図３２】転置ファイルスキャン処理で処理される候補の一例を示す説明図である。
【図３３】第３の実施の形態における構造テンプレート記憶部に格納された構造情報のデータ構造の一例を示す説明図である。
【図３４】第３の実施の形態におけるテンプレート決定処理の全体の流れを示すフローチャートである。
【図３５】構造テンプレート記憶部に格納された構造情報の一例を示す説明図である。
【図３６】登録する構造化文書の一例を示す説明図である。
【図３７】登録する構造化文書の一例を示す説明図である。
【図３８】分割後の構造テンプレート記憶部に格納された構造情報の一例を示す説明図である。
【符号の説明】
【０２５０】
１００  構造化文書検索装置
１０１  通信部
１１０  格納処理部
１１１  構造情報抽出部
１１２  構造テンプレート決定部
１１３  索引登録部
１１４  統計情報更新部
１１５  文書登録部
１２０  検索処理部
１２１  クエリ解析部
１２２  制約付加部
１２２ａ  特徴情報取得部
１２２ｂ  特徴情報算出部
１２２ｃ  ＴＩＤ候補削除部
１２３  クエリプランニング部
１２４  クエリ実行部
１２４ａ  索引検索部
１２４ｂ  検索部
１３１  構造化文書記憶部
１３２  構造テンプレート記憶部
１３３  索引記憶部
１３３ａ  統計情報記憶部
１３３ｂ  転置ファイル記憶部
２００  ネットワーク
３００  クライアント
【図１】
0004490930.tif 000002
【図２】
0004490930.tif 000003
【図３】
0004490930.tif 000004
【図４】
0004490930.tif 000005
【図５】
0004490930.tif 000006
【図６】
0004490930.tif 000007
【図７】
0004490930.tif 000008
【図８】
0004490930.tif 000009
【図９】
0004490930.tif 000010
【図１０】
0004490930.tif 000011
【図１１】
0004490930.tif 000012
【図１２】
0004490930.tif 000013
【図１３】
0004490930.tif 000014
【図１４】
0004490930.tif 000015
【図１５】
0004490930.tif 000016
【図１６】
0004490930.tif 000017
【図１７】
0004490930.tif 000018
【図１８】
0004490930.tif 000019
【図１９】
0004490930.tif 000020
【図２０】
0004490930.tif 000021
【図２１】
0004490930.tif 000022
【図２２】
0004490930.tif 000023
【図２３】
0004490930.tif 000024
【図２４】
0004490930.tif 000025
【図２５】
0004490930.tif 000026
【図２６】
0004490930.tif 000027
【図２７】
0004490930.tif 000028
【図２８】
0004490930.tif 000029
【図２９】
0004490930.tif 000030
【図３０】
0004490930.tif 000031
【図３１】
0004490930.tif 000032
【図３２】
0004490930.tif 000033
【図３３】
0004490930.tif 000034
【図３４】
0004490930.tif 000035
【図３５】
0004490930.tif 000036
【図３６】
0004490930.tif 000037
【図３７】
0004490930.tif 000038
【図３８】
0004490930.tif 000039