(57)【要約】【課題】ＸＭＬタグによる構造情報とアノテーションタグによる構造情報の双方を組み合わせた構造検索を可能とする。【解決手段】本発明は、プログラムを実行するプロセッサと、プログラムを格納する第１の記憶領域と、木構造条件を満たす構造化文書及び当該文書に付されたアノテーションデータを記憶する第２の記憶領域と、構造化文書のタグの包含関係とアノテーションデータのタグの包含関係から個別に得られるＤＯＭ（Document Object Model）木のルート要素を共通化した構造に対し、構造化文書のテキストを割り当ててテキスト共有ＤＯＭ木を生成する文書構造リスト構築部と、検索クエリに合致する要素を、テキスト共有ＤＯＭ木から検索する検索処理部とを有する。【選択図】図１−１
2013246522.tif 000002
【特許請求の範囲】
【請求項１】
プログラムを実行するプロセッサと、
プログラムを格納する第１の記憶領域と、
木構造条件を満たす構造化文書及び当該文書に付されたアノテーションデータを記憶する第２の記憶領域と、
前記構造化文書のタグの包含関係と前記アノテーションデータのタグの包含関係から個別に得られるＤＯＭ（Document Object Model）木のルート要素を共通化した構造に対し、構造化文書のテキストを割り当ててテキスト共有ＤＯＭ木を生成する文書構造リスト構築部と、
検索クエリを入力する入力装置と、
前記検索クエリとして与えられたロケーションパスに合致する要素を、前記テキスト共有ＤＯＭ木から検索するロケーションパス検索部と
を有する構造化文書検索装置。
【請求項２】
プログラムを実行するプロセッサと、
プログラムを格納する第１の記憶領域と、
木構造条件を満たす構造化文書及び当該文書に付されたアノテーションデータを記憶する第２の記憶領域と、
前記構造化文書のタグの包含関係と前記アノテーションデータのタグの包含関係から個別に得られるＤＯＭ（Document Object Model）木のルート要素を共通化した構造に対し、異なるＤＯＭ木のタグ間における包含関係を組み入れ、さらに当該組み入れ後の構造に対して構造化文書のテキストを割り当ててＤＯＭ  ＤＡＧ（Directed Acyclic Graph）を生成する文書構造リスト構築部と、
検索クエリを入力する入力装置と、
前記検索クエリとして与えられたロケーションパスに合致する要素を、前記ＤＯＭ  ＤＡＧから検索するロケーションパス検索部と
を有する構造化文書検索装置。
【請求項３】
請求項２に記載の構造化文書検索装置において、
複数の前記ＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧを生成するパスＤＡＧ要素生成・登録部と、
前記パスＤＡＧの要素のＩＤであるパスＤＡＧ  ＩＤと、対応関係にある１つ又は複数の前記ＤＯＭ  ＤＡＧの要素の位置情報とで構成される転置インデクスを構築する転置インデクス構築部とを有し、
前記ロケーションパス検索部は、前記パスＤＡＧと前記転置インデクスとに基づいて、検索クエリであるロケーションパスに合致する要素が出現する箇所を計算する
ことを特徴とする構造化文書検索装置。
【請求項４】
請求項２に記載の構造化文書検索装置において、
複数の前記ＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧを生成するパスＤＡＧ要素生成・登録部と、
前記パスＤＡＧと、ビット列と、前記ＤＯＭ  ＤＡＧの各要素に対応するロケーションパスの種類を記憶する数列データとを保持する検索インデクスを構築する検索インデクス構築部とを有し、
前記ロケーションパス検索部は、検索クエリであるロケーションパスに対応するパスＤＡＧ  ＩＤを前記パスＤＡＧから計算し、計算により求められた前記パスＤＡＧ  ＩＤで特定される要素が出現する箇所を前記ビット列と前記数列データの走査により計算する
ことを特徴とする構造化文書検索装置。
【請求項５】
請求項２に記載の構造化文書検索装置において、
複数の前記ＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧを生成するパスＤＡＧ要素生成・登録部と、
前記パスＤＡＧと、ビット列と、前記ＤＯＭ  ＤＡＧの各要素に対応するロケーションパスの種類を記憶する数列データとを保持する検索インデクスを構築する検索インデクス構築部と、
前記検索インデクスが保持する前記ビット列及び前記数列データに基づいて、簡潔ビットベクトル及びウェーブレット木を生成する簡潔ビットベクトル・ウェーブレット木生成部とを有し、
前記ロケーションパス検索部は、検索クエリであるロケーションパスに対応するパスＤＡＧ  ＩＤを前記パスＤＡＧから計算し、計算により求められた前記パスＤＡＧ  ＩＤで特定される要素が出現する箇所を前記簡潔ビットベクトル又は前記ウェーブレット木に対するｒａｎｋ演算及びｓｅｌｅｃｔ演算により計算する
ことを特徴とする構造化文書検索装置。
【請求項６】
請求項５に記載の構造化文書検索装置において、
アノテーションデータの追加により、前記ウェーブレット木に登録されている数列の一部の数字が他の数列へ置き換えられた場合に、前記ウェーブレット木を、当該ウェーブレット木に対する変更情報を含む拡張ウェーブレット木に変換する拡張ウェーブレット木構築部を有し、
前記ロケーションパス検索部は、前記ｒａｎｋ演算及びｓｅｌｅｃｔ演算に前記拡張ウェーブレット木を使用する
ことを特徴とする構造化文書検索装置。
【請求項７】
木構造条件を満たす構造化文書のタグの包含関係と当該文書に付されたアノテーションデータのタグの包含関係から個別に得られるＤＯＭ（Document Object Model）木のルート要素を共通化した構造に対し、構造化文書のテキストを割り当ててテキスト共有ＤＯＭ木を生成する第１の処理と、
検索クエリとして与えられたロケーションパスに合致する要素を、前記テキスト共有ＤＯＭ木から検索する第２の処理と
をコンピュータに実行させるプログラム。
【請求項８】
木構造条件を満たす構造化文書のタグの包含関係と当該文書に付されたアノテーションデータのタグの包含関係から個別に得られるＤＯＭ（Document Object Model）木のルート要素を共通化した構造に対し、異なるＤＯＭ木のタグ間における包含関係を組み入れ、さらに当該組み入れ後の構造に構造化文書のテキストを割り当ててＤＯＭ  ＤＡＧ（Directed Acyclic Graph）を生成する第１の処理と、
検索クエリとして与えられたロケーションパスに合致する要素を、前記ＤＯＭ  ＤＡＧから検索する第２の処理と
をコンピュータに実行させるプログラム。
【請求項９】
請求項８に記載のプログラムは、コンピュータに実行させる処理として、
複数の前記ＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧを生成する第３の処理と、
前記パスＤＡＧの要素のＩＤであるパスＤＡＧ  ＩＤと、対応関係にある１つ又は複数の前記ＤＯＭ  ＤＡＧの要素の位置情報とで構成される転置インデクスを構築する第４の処理とを更に有し、
前記第２の処理は、前記パスＤＡＧと前記転置インデクスとに基づいて、検索クエリであるロケーションパスに合致する要素が出現する箇所を計算する
ことを特徴とするプログラム。
【請求項１０】
請求項８に記載のプログラムは、コンピュータに実行させる処理として、
複数の前記ＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧを生成する第３の処理と、
前記パスＤＡＧと、ビット列と、前記ＤＯＭ  ＤＡＧの各要素に対応するロケーションパスの種類を記憶する数列データとを保持する検索インデクスを構築する第５の処理とを更に有し、
前記第２の処理は、検索クエリであるロケーションパスに対応するパスＤＡＧ  ＩＤを前記パスＤＡＧから計算し、計算により求められた前記パスＤＡＧ  ＩＤで特定される要素が出現する箇所を前記ビット列と前記数列データの走査により計算する
ことを特徴とするプログラム。
【請求項１１】
請求項８に記載のプログラムは、コンピュータに実行させる処理として、
複数の前記ＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧを生成する第３の処理と、
前記パスＤＡＧと、ビット列と、前記ＤＯＭ  ＤＡＧの各要素に対応するロケーションパスの種類を記憶する数列データとを保持する検索インデクスを構築する第５の処理と、
前記検索インデクスが保持する前記ビット列及び前記数列データに基づいて、簡潔ビットベクトル及びウェーブレット木を生成する第６の処理とを更に有し、
前記第２の処理は、検索クエリであるロケーションパスに対応するパスＤＡＧ  ＩＤを前記パスＤＡＧから計算し、計算により求められた前記パスＤＡＧ  ＩＤで特定される要素が出現する箇所を前記簡潔ビットベクトル又は前記ウェーブレット木に対するｒａｎｋ演算及びｓｅｌｅｃｔ演算により計算する
ことを特徴とするプログラム。
【請求項１２】
請求項１１に記載のプログラムは、コンピュータに実行させる処理として、
アノテーションデータの追加により、前記ウェーブレット木に登録されている数列の一部の数字が他の数列へ置き換えられた場合に、前記ウェーブレット木を、当該ウェーブレット木に対する変更情報を含む拡張ウェーブレット木に変換する第７の処理を有し、
前記第２の処理は、前記ｒａｎｋ演算及びｓｅｌｅｃｔ演算に前記拡張ウェーブレット木を使用する
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構造化言語で記述された文書（以下、「構造化文書」という。）および任意の形式でアノテーションデータが付与された構造化文書を、タグの構造及び／又は文字列データに基づいて検索する構造化文書検索装置及びその機能をコンピュータを通じて実現するプログラムに関する。
【背景技術】
【０００２】
ＸＭＬ（Extensible Markup Language）は、テキストに対して構造情報の記述を可能とするデータフォーマットであり、タグと呼ばれる「＜」、「＞」で囲まれた文字列により、テキスト内への構造情報の記述を可能にする。ＸＭＬは、タグを入れ子状に記述することにより階層状の木構造を表現でき、タグの追加・削除により階層状の木構造を変更することができる。このため、ＸＭＬは、財務情報の記録、特許明細書の記録、電子商取引におけるデータ交換、ソフトウェアのファイル形式のフォーマットとして広く使用されている。以下、ＸＭＬを用いて記述した文書をＸＭＬ文書という。ＸＭＬ文書では、構造とテキストの双方を検索条件に用いる検索が可能である。ＸＭＬ文書の検索クエリ方式には、Ｗ３Ｃ勧告のＸＰａｔｈ等がある。
【０００３】
一方、一般的なテキストデータに対し、アノテーションを付与するための技術の一つに、ＵＩＭＡ（Unstructured Information Management Architecture）がある。ＵＩＭＡは、構造化されていない文書等のデータを管理するために用いられる技術であり、文書へのアノテーションタグの付与を可能とするプラットフォームを提供する。ＵＩＭＡは、ＸＭＬとは異なり、木構造条件を満たす形式でタグを付ける必要がない。このため、ＵＩＭＡは、計算機により得られた文法構造の解析結果、文書中の技術的に重要な部分などへのマーキングのように、必ずしも構造間に木構造関係を満たす必要がない文書構造情報の保存に利用されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願公開第２００４／０２４３５６０号明細書
【非特許文献】
【０００５】
【非特許文献１】清水敏之、鬼塚真、江田毅晴、吉川正俊、ＸＭＬデータの管理とストリーム処理に関する技術、電子情報通信学会論文誌Ｄ  Ｊ９０−Ｄ（２）：１５９−１８４、２００７
【非特許文献２】G.Navarro and V.Makinen、Compressed full-text indexes、 ACM Computing Surveys 39（1）、2007.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、構造間に木構造関係を満たす保証のない文書構造情報は、今後ますます増加すると予想される。このため、木構造関係に縛られることなく、構造条件とテキスト条件による検索を可能とする技術が求められている。
【０００７】
しかし、計算機による自動抽出により得られる結果（例えば文法構造の解析結果、テキストの意味情報（例えば重要技術・効果など）に基づく文書構造の解析結果）や人手によるマーキングの結果は、その構造情報が木構造条件を満たすとは限らない。このため、木構造条件を満たさない構造情報を含む文書に対しては、既存のＸＭＬ検索手法を利用することができなかった。
【０００８】
以上の理由により、構造上の制約がないタグ情報の検索には、ＵＩＭＡにより用意される検索機能が用いられている（特許文献１）。しかし、この検索方式では、タグの包含関係による階層的構造が考えられていない。従って、ＵＩＭＡの用意する検索機能では、検索クエリとして指定されたテキストが、各タグに含まれるか否かを検証するブーリアン検索しか実行されていない。
【０００９】
結局、ＸＭＬ文書について用意された既存の検索機能やＵＩＭＡにより用意された既存の検索機能では、アノテーション付きのＸＭＬ文書について、ＸＭＬによる構造条件とアノテーションによる構造条件の双方を考慮した検索を実行することができなかった。
【００１０】
本発明は、前述した問題点を考慮し、タグの構造が木構造条件を満たす構造化文書と、当該文書に対応付けられた任意のアノテーションの構造情報とで形成される構造が木構造条件を満たさない場合でも、構造条件とテキストの双方を考慮した検索を可能にする。
【課題を解決するための手段】
【００１１】
本明細書は、上記課題を解決する発明を複数含んでいる。その一例である発明は、プログラムを実行するプロセッサと、プログラムを格納する第１の記憶領域と、木構造条件を満たす構造化文書及び当該文書に付されたアノテーションデータを記憶する第２の記憶領域と、構造化文書のタグの包含関係とアノテーションデータのタグの包含関係から個別に得られるＤＯＭ（Document Object Model）木のルート要素を共通化した構造に対し、構造化文書のテキストを割り当ててテキスト共有ＤＯＭ木を生成する文書構造リスト構築部と、検索クエリとして与えられたロケーションパスに合致する要素を、テキスト共有ＤＯＭ木から検索する検索処理部とを有する。
【発明の効果】
【００１２】
本発明によれば、任意の形式で付与されたアノテーションを含む構造情報とテキストの双方による検索を実現することができる。前述した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００１３】
【図１−１】構造化文書検索装置の構成例を示す図（第１の実施例）。
【図１−２】主記憶装置に記憶するプログラム及びデータの一例を示す図（第１の実施例）。
【図２】アノテーショングループの一例を説明する図（各実施例共通）。
【図３】テキスト共有ＤＯＭ木の一例を示す図（各実施例共通）。
【図４】構造化文書検索装置の前処理の流れを説明する図（第１の実施例）。
【図５】ＤＯＭ木構築部の処理例を示すフローチャート（第１の実施例）。
【図６】文書構造リスト構築部の処理例を示すフローチャート（第１の実施例）。
【図７】親子関係解析・登録部の処理例を示すフローチャート（第１の実施例）。
【図８】構造化文書検索装置による検索処理の流れを説明する図（第１の実施例）。
【図９】ＤＯＭ  ＤＡＧの一例を示す図（第２の実施例）。
【図１０】２つのＤＯＭ  ＤＡＧを統合したパスＤＡＧと転置インデクスの一例を説明する図（第２の実施例）。
【図１１】転置インデクス構築部の処理例を示すフローチャート（第３の実施例）。
【図１２】深さ割当部の処理例を示すフローチャート（第３の実施例）。
【図１３】パスＤＡＧ  ＩＤ取得部の処理例を示すフローチャート（第３の実施例）。
【図１４】パスＤＡＧ要素生成・登録部を示すフローチャート（第３の実施例）。
【図１５】転置インデクス登録部の処理例を示すフローチャート（第３の実施例）。
【図１６】ＤＯＭ  ＤＡＧの記録例を説明する図（第４の実施例）。
【図１７】検索インデクスの概要を示す図（第４の実施例）。
【図１８】検索インデクス構築部の処理例を示すフローチャート（第４の実施例）。
【図１９】検索インデクス登録部の処理例を示すフローチャート（第４の実施例）。
【図２０】パスＤＡＧ  ＩＤ登録部の処理例を示すフローチャート（第４の実施例）。
【図２１】ロケーションパス検索部の処理例を示すフローチャート（第４の実施例）。
【図２２】ＸＭＬ要素検索部の処理例を示すフローチャート（第４の実施例）。
【図２３】アノテーション要素検索部の処理例を示すフローチャート（第４の実施例）。
【図２４】拡張ウェーブレット木の概要を示す図（第６の実施例）。
【図２５】拡張ウェーブレット木構築部の処理例を示すフローチャート（第６の実施例）。
【図２６】ｒａｎｋ計算部の処理例を示すフローチャート（第６の実施例）。
【図２７】ｓｅｌｅｃｔ計算部の処理例を示すフローチャート（第６の実施例）。
【発明を実施するための形態】
【００１４】
以下、添付図面に基づいて、本発明の実施例を説明する。なお、本発明は、後述する実施例に限定されるものではなく、その技術思想の範囲において、種々の変形が可能である。
【００１５】
［第１の実施例］
［概要］
本実施例では、ＸＭＬ文書の集合とアノテーションデータの集合を前処理して検索用データを予め作成し、この検索用データと検索クエリとの照合により、検索クエリに合致する要素を探索結果として出力する構造化文書検索装置について説明する。本実施例では、検索用データとして、ＸＭＬタグとアノテーションタグの構造情報を統合したテキスト共有ＤＯＭ木を使用する。
【００１６】
［装置構成］
図１−１は、構造化文書検索装置４００の構成例を示す。構造化文書検索装置４００は、ＣＰＵ（Central Processing Unit）４０１、主記憶装置（メモリ）４０２、補助記憶装置４０３Ａ、ユーザインタフェース部４０６を有する計算機として構成される。この構造化文書検索装置４００は、ＬＡＮ（Local Area Network）等のネットワーク４０５を介して外部のネットワーク装置に接続されている。
【００１７】
ＣＰＵ４０１は、主記憶装置４０２に格納されたプログラムを実行する中央演算装置である。図１−２に、主記憶装置４０２に格納されるプログラムを通じて実現される機能部とデータの一例を示す。なお、図１−２には、実施例１で使用するプログラムを通じて実現される機能部だけでなく、他の実施例で使用するプログラムにより実現される機能部や、各実施例で使用するデータについても表している。例えば、ＣＰＵ４０１は、プログラムの実行により、ＸＭＬ文書からＤＯＭ木を構築するＤＯＭ木構築部４０９、アノテーションデータからＤＯＭ木を構築するＤＯＭ木構築部４１０、文書構造リスト構築部４１１、テキスト共有ＤＯＭ木構築部４１５、テキストデータ・テキスト要素リスト構築部４１７、テキスト割当部４１８、親子関係解析・登録部４１９、ロケーションパス検索部４２０、ＤＯＭ  ＤＡＧ構築部４２２、転置インデクス構築部４２４、深さ割当部４２７、パスＤＡＧ  ＩＤ取得部４２８、パスＤＡＧ要素生成・登録部４２９、パスＤＡＧ  ＩＤ登録部４３９、検索インデクス登録部４４０、ＸＭＬ要素検索部４４３、アノテーション要素検索部４４４、拡張ウェーブレット木構築部４５１、検索インデクス構築部４５４、簡易ビットベクトル・ウェーブレット木構築部４５５として機能する。
【００１８】
主記憶装置４０２は、ＲＡＭ（Random Access Memory）等の記憶装置である。主記憶装置４０２は、前述したプログラム及びプログラムの実行に用いるパスＤＡＧ４２３等を記憶する。また、主記憶装置４０２は、必要があれば、ＸＭＬ文書集合４０７、アノテーションデータ集合４０８、文書構造リスト４１２も一時的に記憶する。
【００１９】
補助記憶装置４０３Ａは、ＸＭＬ文書、アノテーションデータ、前述したプログラム等を格納するＨＤＤ等の記憶装置又は記憶媒体である。
【００２０】
リムーバブルメディア４０４は、ＸＭＬ文書やアノテーションデータ等を記録したＣＤ−ＲＯＭ、ＤＶＤ等の記録媒体である。補助記憶装置４０３Ａ及びリムーバブルメディア４０４に記録された各データは、構造化文書検索装置４００の起動時に、必要に応じ、主記憶装置４０２に読み出される。
【００２１】
ユーザインタフェース部４０６は、ユーザインタフェースを提供する入出力装置（例えば、キーボード、マウス、ディスプレイ）である。
【００２２】
ＣＰＵ４０１は、主記憶装置４０２、補助記憶装置４０３Ａ、リムーバブルメディア４０４、又は、ネットワーク４０５を介して接続された外部記憶装置４０３Ｂから、必要に応じ、ＸＭＬ文書と当該文書に付されたアノテーションデータを取得する。ここで、外部記憶装置４０３Ｂは、ＨＤＤ等の記憶装置又は記憶媒体である。また、ネットワーク４０５は、ローカルエリアネットワークでも、インターネットでもよい。また、ネットワーク４０５は有線ネットワークでも無線ネットワークでもよい。ＣＰＵ４０１は、これらの記憶装置から取得したＸＭＬ文書とアノテーションデータに基づいて、検索インデクス４３０を作成する。作成された検索インデクス４３０は、主記憶装置４０２に記憶される。
【００２３】
前述の説明においては、ＸＭＬ文書とアノテーションデータは、主記憶装置４０２、補助記憶装置４０３Ａ、リムーバブルメディア４０４、ネットワーク４０５上の外部記憶装置４０３Ｂにいずれかに格納される例を示したが、ＣＰＵ４０１が読み書き可能な記憶装置上に格納されていればよい。例えばＸＭＬ文書は補助記憶装置４０３Ａに格納し、アノテーションデータは主記憶装置４０２に格納しても良い。
【００２４】
ＣＰＵ４０１は、前述した各機能部に対応するプログラムを実行し、所定の機能を実現する機能部として動作する。例えばＣＰＵ４０１は、文書構造構築プログラムに従って動作することにより、テキスト共有ＤＯＭ木構築部４１５として機能する。他のプログラムについても同様である。例えばＣＰＵ４０１は、ロケーションパス検索プログラムに従って動作することにより、ロケーションパス検索部４２０として機能する。また、ＣＰＵ４０１は、検索インデクス構築プログラムに従って動作することにより、検索インデクス構築部４５４として機能する。
【００２５】
ロケーションパス検索部４２０、ＤＯＭ  ＤＡＧ構築部４２２及び検索インデクス構築部４５４の各機能を実現するプログラム、テーブル等の情報は、補助記憶装置４０３Ａ、リムーバブルメディア４０４、不揮発性半導体メモリ、ハードディスクドライブ、ＳＳＤ（Solid State Drive）等の記憶デバイス、又は、ＩＣカード、ＳＤカード、ＤＶＤ等の計算機読み取り可能な非一時的データ記憶媒体に格納することができる。
【００２６】
［アノテーションデータ］
続いて、アノテーションデータについて説明する。アノテーションは、ＸＭＬ文書内のテキスト領域に対して、タグを付与することで与えられる。アノテーションにより付与されるタグをアノテーションタグと呼ぶ。アノテーションタグは、互いに包含関係による構造が、木構造となるグループに事前に分けられていることを想定する。アノテーションタグのグループをアノテーショングループと呼び、各アノテーショングループには整数によるＩＤが割り振られる。異なるアノテーショングループに属するアノテーションタグ同士は、木構造条件を満たす必要はない。
【００２７】
図２は、ＸＭＬ文書に付与されたアノテーションとアノテーショングループの例を示す。「アノテーショングループ１」においては、文書中のテキスト「耐久性を向上」に「効果」というアノテーションタグが付与されており、テキスト「ナイフに関する」に「内容」というアノテーションタグが付与されている。これらのタグは、お互い重なることなく木構造条件を満たしている。また、「アノテーショングループ２」においては、文書中のテキスト「医療用」に「対象」というアノテーションタグが付与されており、テキスト「医療用ナイフ」に「道具」というアノテーションタグが付与されている。これらのアノテーションタグ同士は、入れ子の関係になっているので木構造条件を満たす。
【００２８】
一方、「アノテーショングループ１」に属するアノテーションタグである「内容」と、「アノテーショングループ２」に属するアノテーションタグである「道具」とは、タグ同士が入れ子の関係になっておらず、木構造条件を満たしていない。しかし、「内容」と「道具」は異なるアノテーショングループに属するタグ同士であるため、アノテーションデータとして問題ないものである。
【００２９】
アノテーションタグは、「タグ名、アノテーショングループＩＤ、テキスト領域の開始位置、テキスト領域の終了位置」で与えられる４つの情報の組により構成される。アノテーションデータは、各アノテーションタグについて４つの情報の組が記述されたデータの集合である。アノテーションデータの一例には、各行に、各アノテーションタグのデータであるタグ名、アノテーショングループＩＤ、テキスト領域の開始位置、テキスト領域の終了位置をタブ区切りで記述したテキストデータを考えることができる。
【００３０】
［ＸＭＬ要素、アノテーション要素、テキスト要素］
ＸＭＬ要素は、各ＸＭＬタグの開始タグ、終了タグにより表された要素であり、タグ名、テキスト領域における開始タグ、終了タグの位置を持つ。アノテーション要素は、タグ名、アノテーショングループＩＤ、各アノテーションタグの開始タグ、終了タグの位置を持つ要素である。テキスト要素は、テキスト領域を表す要素であり、テキスト領域の開始位置、終了位置、テキスト領域に含まれるテキストから構成される。
【００３１】
［ＤＯＭ木の要素］
ＤＯＭ木を構成する要素は、タグ名、アノテーショングループＩＤ、テキスト領域開始位置、テキスト領域終了位置、深さを持つ。通常のＸＭＬタグによる要素の場合、アノテーショングループＩＤを“０”とする。テキスト要素の場合、アノテーショングループＩＤを“−１”とし、タグ名の部分にテキストを保持する。
【００３２】
[前処理の概要］
ここでは、構造化文書検索装置４００が検索前に実行する前処理の概要について説明する。前処理は、文書構造リスト構築部４１１として機能するＣＰＵ４０１が実行する。ＣＰＵ４０１は、前処理として、テキスト共有ＤＯＭ木４１６を作成する。
【００３３】
まず、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８の中から、未処理のＸＭＬ文書と対応するアノテーションデータを取得する。次に、ＣＰＵ４０１は、ＤＯＭ木構築プログラムを実行し、ＸＭＬ文書からＤＯＭ木を構築するＤＯＭ木構築部４０９と、アノテーションデータからＤＯＭ木を構築するＤＯＭ木構築部４１０として動作する。ＤＯＭ木構築部４０９及び４１０として機能するＣＰＵ４０１は、ＸＭＬ文書のＤＯＭ木とアノテーションデータの各アノテーショングループに属する要素のＤＯＭ木を作成する。
【００３４】
次に、ＣＰＵ４０１は、テキスト共有ＤＯＭ木構築プログラムを実行し、テキスト共有ＤＯＭ木構築部４１５として機能する。ここで、ＣＰＵ４０１は、同じテキストに対して形成された２つのＤＯＭ木のルート要素を共通化した構造にテキストを割り当て、テキスト共有ＤＯＭ木４１６を作成する。各ＸＭＬ文書とアノテーションデータに対して構築されたテキスト共有ＤＯＭ木４１６は、検索に用いるデータ構造として、文書構造リスト構築部４１１に保持される。
【００３５】
［テキスト共有ＤＯＭ木］
続いて、テキスト共有ＤＯＭ木４１６を説明する。テキスト共有ＤＯＭ木４１６は、ＸＭＬタグに基づいて構築されたＤＯＭ木と、各アノテーショングループに属するタグに基づいて構成された１つ又は複数のＤＯＭ木から構築されるデータ構造であり、各ＤＯＭ木のルート要素を共通化したデータ構造を有している。ここで、ＸＭＬタグに基づくＤＯＭ木は、ＤＯＭ木構築部４０９として機能するＣＰＵ４０１が構築する。また、アノテーションタグに基づくＤＯＭ木は、ＤＯＭ木構築部４１０として機能するＣＰＵ４０１が構築する。以下の説明において、単にＤＯＭ木というときは、ＸＭＬタグに基づいて構築されたＤＯＭ木又はアノテーションタグに基づいて構築されたＤＯＭ木をいう。
【００３６】
ＸＭＬ文書を構成するテキストは、ＸＭＬタグ及びアノテーションタグで区切られており、区切られたテキスト領域ごとにテキスト要素が構成される。各ＤＯＭ木において、テキスト要素は、包含される要素のうち、ルート要素から最も深い位置の要素に割り当てられる。各テキスト領域は、単一のＤＯＭ木でなく、複数のＤＯＭ木に割り当てられる可能性がある。
【００３７】
図３は、ＸＭＬタグ＜ｐ＞、＜ｍｔｄ＞、＜ｆｘ＞、＜ｖａｌ＞、＜ａｔｔｒ＞と、同一のアノテーションＩＤに属するタグ［Ａ］と［Ｔ］でタグ付けした下記の文章から作成したテキスト共有ＤＯＭ木の例を示している。
（タグ付け前の文章）
「本発明では、粉末コークスを用いることで、粗鋼を生産し、２倍の効率化を達成した。」
（タグ付け後の文章）
「＜ｐ＞本発明では、［Ａ］＜ｍｔｄ＞粉末コークスを用いる＜／ｍｔｄ＞ことで、＜ｆｘ＞［Ｔ］＜ｏｂｊ＞粗鋼＜／ｏｂｊ＞を生産［／Ｔ］［／Ａ］し、＜ｖａｌ＞２倍＜／ｖａｌ＞の＜ａｔｒ＞効率化＜／ａｔｔｒ＞を達成＜／ｆｘ＞した。＜／ｐ＞」
図３に示すように、テキスト共有ＤＯＭ木のルート要素には、ＸＭＬタグの＜ｐ＞とアノテーションタグの［Ａ］にエッジが接続されている。すなわち、テキスト共有ＤＯＭ木は、ＸＭＬタグによるＤＯＭ木と、同一のアノテーショングループに属するアノテーションタグによるＤＯＭ木のルート要素を共通化した構造を有している。また、テキストは、ＸＭＬタグ、アノテーションタグに関わらず分割され、ＸＭＬタグ、アノテーションタグの場合に分け、テキスト領域の包含関係に基づいて、包含関係がある最も深い位置の要素に割り当てられる。例えば図３の例の場合、テキスト「粗鋼」は、ＸＭＬタグ＜ｏｂｊ＞とアノテーションタグ［Ｔ］の両方に割り当てられている。
【００３８】
［前処理の詳細処理］
図４に、前処理に関連して実行されるデータの流れを示す。前処理の開始は、ユーザインタフェース４０６を通じ、ＣＰＵ４０１に与えられる（ステップＳ３０１）。また、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８を補助記憶装置４０３Ａから入力する（ステップＳ３０２）。なお、入力されたＸＭＬ文書集合４０７とアノテーションデータ集合４０８は、作業領域としての主記憶装置４０２に格納される。
【００３９】
この段階で、ＣＰＵ４０１は、テキスト共有ＤＯＭ木構築部４１５としての分析処理を実行し、文書構造リスト４１２を構築する（ステップＳ３０３）。
【００４０】
ＣＰＵ４０１（テキスト共有ＤＯＭ木構築部４１５）は、ＸＭＬ文書集合４０７の要素としてのＸＭＬ文書と、ＸＭＬ文書に対応したアノテーションデータ集合４０８の要素としてのアノテーションデータ４０８とに基づいてテキスト共有ＤＯＭ木４１６を生成する。ＣＰＵ４０１（テキスト共有ＤＯＭ木構築部４１５）が実行する前処理の詳細については後述する。前処理が終了すると、ＣＰＵ４０１は、生成されたテキスト共有ＤＯＭ木４１６を文書構造リスト４１２として、補助記憶装置４０３Ａに出力する（ステップＳ３０４）。
【００４１】
［アノテーションデータ用のＤＯＭ木構築部４１０］
図５は、アノテーションデータからＤＯＭ木を構築するＤＯＭ木構築部４１０として機能するＣＰＵ４０１の処理動作例を示すフローチャートである。
【００４２】
ＣＰＵ４０１（ＤＯＭ木構築部４１０）は、入力されたアノテーションデータのファイルを読み込み、「タグ名、アノテーショングループＩＤ、テキスト領域開始位置、テキスト領域終了位置」の４組データの集合ＡＳを用意する（ステップＳ４０１）。ＣＰＵ４０１は、集合ＡＳのうち最大のアノテーショングループＩＤを“ｇ”にセットする（ステップＳ４０２）。次に、ＣＰＵ４０１は、変数ｉに“１”をセットする（ステップＳ４０３）。次に、ＣＰＵ４０１は、変数ｉが“ｇ”以下か判定し、変数ｉが“ｇ”より大きくなるまで、後述するステップＳ４０５〜Ｓ４１３を繰り返す（ステップＳ４０４）。
【００４３】
ステップＳ４０４で肯定結果が得られた場合、ＣＰＵ４０１は、集合ＡＳよりアノテーショングループＩＤが変数ｉとなる要素のリストをＡＬに設定する（ステップＳ４０５）。次に、ＣＰＵ４０１は、リストＡＬの要素をテキスト領域開始位置の昇順にソートし、テキスト領域開始位置が同じものについては、テキスト領域の終了位置の降順にソートする（ステップＳ４０６）。
【００４４】
続いて、ＣＰＵ４０１は、ルート要素のみからなるＤＯＭ木ＡＴを用意し、ルート要素をｖとする（ステップＳ４０７）。ここで、ＣＰＵ４０１は、変数ｊに１をセットする（ステップＳ４０８）。次に、ＣＰＵ４０１は、変数ｊがリストＡＬの長さ（要素数）を越えるまで、後述するステップＳ４１０〜Ｓ４１２を繰り返し（ステップＳ４０９）、繰り返し終了後、変数ｉに“１”を加算してステップＳ４０４に戻る（ステップＳ４１３）。
【００４５】
先のステップＳ４０９で肯定結果が得られた場合、ＣＰＵ４０１は、リストＡＬのｊ番目の要素のテキスト領域（テキスト領域開始位置とテキスト領域終了位置で与えられる領域）が、ルート要素ｖにあるテキスト領域（テキスト領域開始位置とテキスト領域終了位置で与えられる領域）に含まれるまで、ルート要素ｖの親要素をｖにセットする処理を繰り返す（ステップＳ４１０）。
【００４６】
この後、ＣＰＵ４０１は、リストＡＬのｊ番目の要素のタグ名、アノテーショングループＩＤ、テキスト領域開始位置、テキスト領域終了位置を有するＤＯＭ木の要素を作成し、ルート要素ｖの子要素としてＤＯＭ木ＡＴに加える（ステップＳ４１１）。この後、ＣＰＵ４０１は、変数ｊに“１”を加算し、ステップＳ４０９に戻る（ステップＳ４１２）。
【００４７】
ＣＰＵ４０１は、各アノテーショングループについて、テキスト領域の開始位置と終了位置に基づいて要素を事前にソートし、その後、前述した方法を適用することにより、アノテーションデータのＤＯＭ木を構築する。また、ＤＯＭ木は順序木となっているが、前述した方法で要素を加えることにより、兄弟要素同士は、テキスト領域の開始位置で昇順にソートされた状態となる。
【００４８】
［ＸＭＬ文書用のＤＯＭ木構築部４０９］
前述したように、ＣＰＵ４０１は、ＸＭＬ文書からＤＯＭ木を構築するＤＯＭ木構築部４０９としても機能する。ＤＯＭ木構築部４０９としてのＣＰＵ４０１は、入力されたＸＭＬ文書に付与されたタグの包含関係を分析し、ＤＯＭ木を構築する。ＸＭＬ文書のＤＯＭ木は、非特許文献１に記載の方法により構築することができる。構築されたＤＯＭ木は、各タグに対応するテキスト領域の開始位置、終了位置の情報は含まない。
【００４９】
本実施例では、ＣＰＵ４０１が、ＸＭＬ文書について構築されたＤＯＭ木に割り当てられたテキスト要素について、テキスト領域における開始位置及び終了位置を計算する。次に、ＣＰＵ４０１は、計算された位置情報を各要素に付与しながらテキスト要素を削除し、テキスト要素が保持する文字列をつなげたテキストを作成する。
【００５０】
ここでは、“ｔ”を空のテキストとする。ＣＰＵ４０１は、構築されたＤＯＭ木をルート要素から走査しながら、テキスト要素に対応するテキストの長さを記録し、前順に開始位置、後順に終了位置を記録する。各テキスト要素を走査した後、ＣＰＵ４０１は、テキスト要素を削除し、テキスト“ｔ”に対し、削除されたテキスト要素が保持する文字列を加える。最後に、ＣＰＵ４０１は、構築されたＤＯＭ木とテキストｔを出力し、一連の処理を終了する。
【００５１】
［文書構造リスト構築部４１１］
図６は、文書構造リスト構築部４１１として機能するＣＰＵ４０１により実行される処理の一例を示すフローチャートである。
【００５２】
まず、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８を入力とする（ステップＳ５０１）。次に、ＣＰＵ４０１は、文書構造リスト４１２を空のリストに初期化する（ステップＳ５０２）。その後、ＣＰＵ４０１は、変数ｉに“１”をセットする（ステップＳ５０３）。次に、ＣＰＵ４０１は、テキストデータリストを空に初期化する（ステップＳ５０４）。
【００５３】
この後、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８に含まれる、ＸＭＬ文書とアノテーションデータの全てのペアを処理したか否かを判定する(ステップＳ５０５)。この判定処理で肯定結果が得られるまで、ＣＰＵ４０１は、後述するステップＳ５０６〜Ｓ５１０の処理を繰り返し実行する。
【００５４】
ステップＳ５０５で否定結果が得られた場合、ＣＰＵ４０１は、未処理のＸＭＬ文書とアノテーションデータのペアを読み込む（ステップＳ５０６）。次に、ＣＰＵ４０１は、ＸＭＬ文書用のＤＯＭ木構築部４０９とアノテーションデータ用のＤＯＭ木構築部４１０として機能し、それぞれ対応するＤＯＭ木を作成する（ステップＳ５０７）。
【００５５】
この後、ＣＰＵ４０１は、ＸＭＬ文書から得られたＤＯＭ木と各アノテーショングループに属するタグから得られたＤＯＭ木を入力すると、後述するテキスト共有ＤＯＭ木構築部４１５として機能してテキスト共有ＤＯＭ木４１６を作成し、作成されたテキスト共有ＤＯＭ木４１６を構成する要素のリストＮを得る（ステップＳ５０８）。次に、ＣＰＵ４０１は、リストＮを、文書構造リスト（テキスト共有ＤＯＭ木リスト）４１２に追加する（ステップＳ５０９）。
【００５６】
次に、ＣＰＵ４０１は、読み込んだＸＭＬ文書及びアノテーションデータを処理済としてステップＳ５０５に戻る（ステップＳ５１０）。
【００５７】
［テキスト共有ＤＯＭ木構築部４１５］
テキスト共有ＤＯＭ木構築部４１５として機能するＣＰＵ４０１は、ＸＭＬ要素によるＤＯＭ木と、ＸＭＬ文書内のテキスト及び各アノテーショングループの要素からなるＤＯＭ木を入力する。ここで、ＣＰＵ４０１は、各ＤＯＭ木のルート要素以外の要素のリストＮを用意する。
【００５８】
ＣＰＵ４０１は、リストＮとＸＭＬ文書内のテキストを、テキストデータ・テキスト要素リスト構築部４１７に入力し、テキストデータリスト４１４とテキスト要素リスト４１３を更新する。
【００５９】
この後、ＣＰＵ４０１は、テキスト要素リスト４１３と、ＸＭＬ要素と、各アノテーショングループの要素からなるＤＯＭ木を入力する。テキスト割当部４１８として機能するＣＰＵ４０１は、テキスト要素を子要素として各要素に割り当てる。ＣＰＵ４０１は、テキスト要素リスト４１３の各要素をリストＮに加える。また、ＣＰＵ４０１は、各ＤＯＭ木のルート要素を１つに共通化し、共通化したルート要素をリストＮの先頭に加える。最後に、ＣＰＵ４０１は、リストＮを出力し、テキスト共有ＤＯＭ木の作成処理を終了する。
【００６０】
［テキストデータ・テキスト要素リスト構築部４１７］
テキストデータ・テキスト要素リスト構築部４１７として機能するＣＰＵ４０１は、リストＮとテキストｔとを入力する。ＣＰＵ４０１は、リストＮ内の各要素のテキスト領域の開始位置、終了位置を取り出し、昇順にソートした数値からなるリストをＳとする。ＣＰＵ４０１は、リストＳ内で数値が重複している部分を除去する。リストＳの先頭の値が０でない場合、ＣＰＵ４０１は、先頭に０を追加する。また、リストＳの最後尾の値がテキストｔと同じ場合、ＣＰＵ４０１は、最後尾の値を削除する。ＣＰＵ４０１は、テキストｔとリストＳをテキストデータとして、テキストデータリスト４１４の最後尾に追加する。
【００６１】
ＣＰＵ４０１は、テキスト要素リスト４１３を空に初期化する。リストＳの各値は、テキスト領域の開始位置、終了位置を与えている。従って、ＣＰＵ４０１は、リストＳの先頭の要素から順番に、テキスト領域の開始位置を現在見ている要素の値、終了位置を次の要素の値、タグ名を＃として、ＤＯＭ  ＤＡＧ４２１の要素を作成し、テキスト要素リスト４１３の最後尾に順次追加する。なお、リストＳの最後の要素の場合、次の要素が存在しない。このため、ＣＰＵ４０１は、テキストｔの長さをテキスト領域の終了位置にセットする。
【００６２】
［テキスト割当部４１８］
テキスト要素リスト４１３の各要素は、互いのテキスト領域が重ならないため包含関係を有していない。このため、テキスト割当部４１８として機能するＣＰＵ４０１は、テキスト要素リスト４１３の各要素とルート要素とに基づいて、テキスト要素同士が兄弟となるＤＯＭ木を作成することができる。作成されるＤＯＭ木をＴｔとする。ＣＰＵ４０１は、ＤＯＭ木Ｔｔに対して、各アノテーショングループのＤＯＭ木から、後述する親子関係解析・登録部４１９としての機能を通じ、アノテーショングループ外の親を登録する。
【００６３】
［要素間の包含関係］
本実施例では、ＸＭＬ要素又はアノテーション要素とテキスト要素間の包含関係は、以下のルールに従うものとする。ＸＭＬ要素又はアノテーション要素のテキスト領域がテキスト要素のテキスト領域を包含する、又は同じである場合、ＸＭＬ要素又はアノテーション要素は、テキスト要素を包含するとする。これ以外の場合は、包含関係はないものとする。
【００６４】
［親子関係解析・登録部４１９］
図７は、親子関係解析・登録部４１９として機能するＣＰＵ４０１により実行される処理の一例を示すフローチャートである。
【００６５】
まず、ＣＰＵ４０１は、ＤＯＭ木ＴとＤＯＭ木Ｕを入力とする（ステップＳ６０１）
次に、ＣＰＵ４０１は、ＤＯＭ木Ｕの要素の集合をＶとし（ステップＳ６０２）、Ｖが空であるかを判定する（ステップＳ６０３）。Ｖが空になるまで、後述のステップＳ６０４〜Ｓ６０８を繰り返す。
【００６６】
要素ｖをＶから取り出し、Ｖから削除する（ステップＳ６０４）。ＣＰＵ４０１は、ＤＯＭ木Ｔの要素の中で、ｖを包含する要素のうち、ルートからの深さが最も深いものを要素ｕとする（ステップＳ６０５）。ｕがＤＯＭ木Ｔのルート要素であるかを判定し（ステップＳ６０６）、ルート要素でないならば、ＣＰＵ４０１は、ｕをｖのアノテーショングループ外の親要素として登録し、ステップＳ６０３に戻る（ステップＳ６０７）。
【００６７】
［検索動作の概要］          
続いて、構造化文書検索装置４００において実行される検索処理の概要を説明する。検索処理は、後述するロケーションパス検索部４２０として機能するＣＰＵ４０１により実行される。ロケーションパス検索部４２０として機能するＣＰＵ４０１は、各ＸＭＬ文書とアノテーションデータとから構築されたテキスト共有ＤＯＭ木をロケーションパスに沿って辿り、検索クエリに合致した要素を検索結果として取得する。
【００６８】
図３では、テキスト共有ＤＯＭ木について、ロケーションパス「/p/fx/obj」とロケーションパス「/A/T」とが共通する要素を検索する場合について表している。図３の例の場合、ロケーションパス「/p/fx/obj」は、ルート要素の下のタグ＜ｐ＞の下のタグ＜ｆｘ＞の下のタグ＜ｏｂｊ＞の下に割り当てられた要素を表しており、ロケーションパス「/A/T」は、ルート要素の下のタグ［Ａ］の下のタグ［Ｔ］の下に割り当てられた要素を表している。図３では、これら２つのロケーションパスを点線の矢印により表している。この結果、共通する要素は、テキスト要素である「粗鋼」となる。
【００６９】
［検索動作の詳細］
図８に、構造化文書検索装置４００において検索処理が実行される際のデータの流れを示す。なお、ＣＰＵ４０１は、検索に使用する文書構造リスト４１２（本実施例の場合、テキスト共有ＤＯＭ木４１６）を、補助記憶装置４０３Ａから主記憶装置４０２に事前に読み出しているものとする（ステップＳ４０１）。
【００７０】
この状態で、ユーザがユーザインタフェース４０６を通じ、検索クエリとしてのロケーションパスを構造化文書検索装置４００（具体的には、ＣＰＵ４０１）に投入する（ステップＳ４０２）。
【００７１】
すると、ロケーションパス検索部４２０として機能するＣＰＵ４０２は、文書構造リスト４１２にあるテキスト共有ＤＯＭ木４１６にアクセスし、検索クエリとして指定されたロケーションパスに合致した要素の箇所を計算する（ステップＳ４０３）。この後、ＣＰＵ４０１は、検索クエリに合致した要素の集合をユーザインタフェース４０６に出力する（ステップＳ４０５）。
【００７２】
［ロケーションパス検索部４２０］
最後に、ロケーションパス検索部４２０として機能するＣＰＵ４０１の動作を説明する。文書構造リスト４１２を構成する各要素のリストの先頭は、テキスト共有ＤＯＭ木のルート要素となっている。従って、ＣＰＵ４０１は、各テキスト共有ＤＯＭ木のルート要素からテキスト共有ＤＯＭ木をロケーションパスに沿って辿ることにより、検索クエリに合致するテキスト共有ＤＯＭ木の要素を得る。
【００７３】
［実施例の効果］
本実施例に係る構造化文書検索装置４００は、前処理として、ＸＭＬタグに基づいて構築されたＤＯＭ木と、アノテーショングループに属するタグに基づいて構築されたＤＯＭ木の間でルート要素を共通化したテキスト共有ＤＯＭ木４１６を生成する。テキスト共有ＤＯＭ木４１６には、共通するルート要素を起点として各ＤＯＭ木の構造が含まれている。従って、任意の形式でアノテーションがＸＭＬ文書に付与されている場合にも、ＸＭＬによる階層構造とアノテーションによる階層構造の双方を考慮した検索を可能とすることができる。
【００７４】
［第２の実施例］
本実施例においては、ＸＭＬ要素とアノテーション要素、又は、異なるアノテーショングループに属するアノテーション要素同士といった異なる種類の要素間における包含関係を定義する。このために、本実施例では、第１の実施例におけるテキスト共有ＤＯＭ木の構造を拡張したＤＯＭ  ＤＡＧ（Directed Acyclic Graph：非循環有向グラフ）を使用する。なお、本実施例に係る構造化文書検索装置４００の基本構成は、実施例１と同様である。すなわち、図１−１及び図１−２に示す構成を基本構成とする。ただし、本実施例では、テキスト共有ＤＯＭ木構築部４１５に代えて、ＤＯＭ  ＤＡＧ構築部４２２を使用する。
【００７５】
［前処理の概要］
前述したように、本実施例においては、ＸＭＬ要素とアノテーション要素間、及び、異なるアノテーショングループ間に属する要素間におけるテキスト領域の包含関係についても親子関係として考慮したＤＯＭ  ＤＡＧを使用した構造検索について説明する。ＤＯＭ  ＤＡＧの導入により、異なる種類の要素間の包含関係を考慮した検索を実行可能な構造化文書検索装置が実現される。
【００７６】
［ＤＯＭ  ＤＡＧ］
ここでは、本実施例で使用するＤＯＭ  ＤＡＧについて説明する。ＤＯＭ  ＤＡＧは、テキスト共有ＤＯＭ木において、ＸＭＬタグや異なるアノテーショングループに属するタグなど、異なる種類の要素間の包含関係も記述したデータ構造である。すなわち、ルート要素で共通化された各ＤＯＭ木の間において、包含関係による親子関係が記述されたデータ構造である。
【００７７】
ＤＯＭ  ＤＡＧでは、例えばＤＯＭ木Ｔ２の要素を包含するＤＯＭ木Ｔ１の要素のうち、ＤＯＭ木Ｔ１のルート要素から最も深い位置にある要素との間に親子関係があるものとして扱い、ＤＯＭ木Ｔ１とＤＯＭ木Ｔ２の間にリンクを張る。これにより、ＤＯＭ木Ｔ１の要素からＤＯＭ木Ｔ２の要素への包含関係を表現する。
【００７８】
図９に、図３に示したテキスト共有ＤＯＭ木４１６に基づいて構築されたＤＯＭ  ＤＡＧの例を示す。図９の場合、ＸＭＬタグであるタグ＜ｆｘ＞からアノテーションタグであるタグ［Ｔ］へのリンク、アノテーションタグであるタグ［Ｔ］からＸＭＬタグであるタグ＜ｏｂｊ＞へのリンクのように、異なる種類のタグ間でも親子関係が考えられている。
【００７９】
［ＤＯＭ  ＤＡＧ内の要素の包含関係］
ＤＯＭ木又はＤＯＭ  ＤＡＧ内の要素の包含関係は、次のルールに従うものとする。
（１）ルート要素は、ルート要素以外のどの要素も包含する。
（２）ＸＭＬ要素とアノテーション要素のテキスト領域開始位置と終了位置が同じ場合、ＸＭＬ要素がアノテーション要素を包含する。
（３）アノテーション要素同士のテキスト領域開始位置と終了位置が同じ場合、アノテーショングループＩＤが小さい要素がアノテーショングループＩＤが大きい要素を包含する。
（４）テキスト要素とテキスト要素以外の他の要素について、テキスト領域開始位置と終了位置が同じ場合、後者が前者を包含する。
（５）（１）〜（４）によって包含関係が決定しない場合、要素にあるテキスト領域の包含関係から要素の包含関係を決定する。ただし、テキスト要素のテキスト領域が他の要素のテキスト領域を包含する場合、要素の包含関係はないものとする。
（６）（１）〜（５）によって包含関係が決定しない場合、互いに包含関係がないものとする。
【００８０】
［ＤＯＭ  ＤＡＧ構築部４２２］
ＤＯＭ  ＤＡＧ構築部４２２として機能するＣＰＵ４０１は、ＸＭＬ要素から構築したＤＯＭ木、ＸＭＬ文書内のテキスト、各アノテーショングループの要素から構築したＤＯＭ木を入力とする。
【００８１】
親子関係解析・登録部４１９として機能するＣＰＵ４０１は、ＸＭＬ要素を含むアノテーショングループの全てのＤＯＭ木の組に対し、アノテーショングループ外の親を割り当てる。ここで、ＣＰＵ４０１は、各ＤＯＭ木について、ルート要素以外の要素のリストＮを用意する。ＣＰＵ４０１は、リストＮとＸＭＬ文書内のテキストを、テキストデータ・テキスト要素リスト構築部４１７に入力し、テキストデータリスト４１４とテキスト要素リスト４１３を更新する。
【００８２】
テキスト割当部４１８として機能するＣＰＵ４０１は、テキスト要素リスト４１３と、ＸＭＬ要素と、各アノテーショングループの要素からなるＤＯＭ木を入力すると、テキスト要素を子要素としてＤＯＭ木の各要素に割り当てる。ＣＰＵ４０１は、テキスト要素リスト４１３の各要素をリストＮに加えると共に、深さの情報を各要素に割り当てる。ＣＰＵ４０１は、ＤＯＭ木の各要素が持つアノテーショングループ外の親要素リストの要素に対し、親子関係のリンクを張る。また、ＣＰＵ４０１は、各ＤＯＭ木のルート要素を１つに共通化し、共通化したルート要素をリストＮの先頭に加える。この後、ＣＰＵ４０１は、リストＮを出力し、ＤＯＭ  ＤＡＧの作成処理を終了する。
【００８３】
［実施例の効果］
本実施例に係る構造化文書検索装置４００は、前処理として、実施例１で説明したテキスト共有ＤＯＭ木４１６を構成する異なるＤＯＭ木の要素間についても包含関係を規定したＤＯＭ  ＤＡＧを作成する。従って、本実施例に係る構造化文書検索装置４００を用いれば、実施例１の効果に加え、異なる種類の要素間における包含関係（親子関係）も考慮した検索を可能とすることができる。
【００８４】
［第３の実施例］
前述したように、ＤＯＭ  ＤＡＧを用いれば、異種タグ間の構造関係を利用した検索が可能となる。しかし、ロケーションパスの検索時、構築した全てのＤＯＭ  ＤＡＧをルート要素から辿るのでは非効率的である。
【００８５】
そこで、本実施例では、複数のＤＯＭ  ＤＡＧの構造を集約したデータ構造であるパスＤＡＧを定義する。さらに、パスＤＡＧ内の要素をエントリとして、ＤＯＭ  ＤＡＧ内の要素を値とした転置インデクスによる検索を可能とすることにより、ロケーションパスを検索クエリとした効率的な探索を可能にする。
【００８６】
本実施例の場合も、構造化文書検索装置４００の基本構成は、実施例１と同様である。すなわち、図１−１及び図１−２に示す構成を基本構成とする。ただし、本実施例の場合、ＤＯＭ  ＤＡＧ構築部４２２とロケーションパス検索部４２０の機能が拡張されている。
【００８７】
［前処理の概要］
本実施例の場合、転置インデクス構築部４２４が前処理を実行する。転置インデクス構築部４２４として機能するＣＰＵ４０１は、パスＤＡＧ４２３をルート要素のみからなるデータ構造に初期化すると共に、各ＸＭＬ文書と対応したアノテーションデータに基づいてＤＯＭ  ＤＡＧを構築する。
【００８８】
パスＤＡＧ  ＩＤ取得部４２８として機能するＣＰＵ４０１は、ＤＯＭ  ＤＡＧを構成する各要素のタグ名と親要素に基づいて、パスＤＡＧ内に既に登録されている構造か否かを判定する。判定対象である構造がパスＤＡＧ内に既に登録されている場合、ＣＰＵ４０１は、当該構造に対し、対応するパスＤＡＧ内の要素のＩＤであるパスＤＡＧ  ＩＤを与える。これに対し、判定対象とする構造が登録されていない場合、ＣＰＵ４０１は、パスＤＡＧ要素生成・登録部４２９として機能し、パスＤＡＧ４２３に対して新しく要素を生成すると共に、生成された要素に対してパスＤＡＧ  ＩＤを得える。パスＤＡＧ  ＩＤの取得後、ＣＰＵ４０１は、転置インデクス４２５の取得したパスＤＡＧ  ＩＤに対応したエントリに各要素を追加する。
【００８９】
図１０は、２つのＤＯＭ  ＤＡＧの登録後に生成される、パスＤＡＧと転置インデクス４２５の例を示す。図１０に示すように、パスＤＡＧ４２３は、ＸＭＬ文書１から構築されたＤＯＭ  ＤＡＧとＸＭＬ文書２から構築されたＤＯＭ  ＤＡＧについて、親ノードの集合が同じである要素を共通化させるように構築される。図中、白抜きで示す要素は、ＸＭＬ要素、黒の塗りつぶしで示す要素は、アノテーション要素を示す。
【００９０】
ただし、要素ｃのように、２つの文書間で親の集合の関係が異なる要素の場合には、パスＤＡＧ４２３上では、異なる要素として登録される。図１０では、「ｃ：１」と「ｃ：２」として区別して登録されている。
【００９１】
また、要素ｄは、親要素がどちらも要素ｃだけであり、親の集合が共通しているように見える。しかし、パスＤＡＧ上における要素ｃは、前述したように異なる要素として登録されている。このため、要素ｄも、パスＤＡＧ上異なる要素として登録される。ＤＯＭ  ＤＡＧの各要素には、文書の順番、文書内でのタグの出現順を組にした番号が振られている。各要素の番号は、転置インデクス４２５内で対応するパスＤＡＧ要素のパスＤＡＧ  ＩＤのエントリに記録される。
【００９２】
なお、図１０には、パスＤＡＧ４２３に対応する転置インデクス４２５の構造もＩＤとタグ番号の関係として記載されている。この転置インデクスの生成方法については、次項において説明する。
【００９３】
［転置インデクス構築部４２４］
図１１は、転置インデクス構築部４２４として機能するＣＰＵ４０１の処理動作を示すフローチャートである。
【００９４】
まず、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８を入力する（ステップＳ１００１）。次に、ＣＰＵ４０１は、ＤＯＭ  ＤＡＧリストを空のリストに初期化する（ステップＳ１００２）。続いて、ＣＰＵ４０１は、転置インデクス４２５を空のテーブルに初期化する（ステップＳ１００３）。また、ＣＰＵ４０１は、変数ｉを“１”にセットする（ステップＳ１００４）。次に、ＣＰＵ４０１は、テキストデータリストを空に初期化する（ステップＳ１００５）。
【００９５】
この後、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８に含まれる、ＸＭＬ文書とアノテーションデータの全てのペアを処理したか否かを判定する（ステップＳ１００６）。この判定処理において肯定結果が得られるまで、ＣＰＵ４０１は、後述するステップＳ１００７〜Ｓ１０１３の処理を繰り返す。
【００９６】
ＤＯＭ  ＤＡＧ構築部４２２として機能するＣＰＵ４０１は、未処理のＸＭＬ文書とアノテーションデータのペアを読み込む（ステップＳ１００７）。ここで、ＣＰＵ４０１は、ＸＭＬ文書用のＤＯＭ木構築部４０９及びアノテーションデータ用のＤＯＭ木構築部４１０として機能し、ＸＭＬ文書とアノテーションデータのそれぞれからＤＯＭ木を作成する（ステップＳ１００８）。
【００９７】
次に、ＣＰＵ４０１は、後述するＤＯＭ  ＤＡＧ構築部４２２として機能し、ＸＭＬ文書から得られたＤＯＭ木と各アノテーショングループに属するタグから得られたＤＯＭ木からＤＯＭ  ＤＡＧ４２１を作成し、ＤＯＭ  ＤＡＧ４２１を構成する要素のリストＮを得る（ステップＳ１００９）。
【００９８】
続いて、ＣＰＵ４０１は、リストＮを後述するＤＯＭ  ＤＡＧ要素リストソート部４２６に入力し、ソートする（ステップＳ１０１０）。さらに、ＣＰＵ４０１は、リストＮと変数ｉを転置インデクス登録部４４０に入力し、転置インデクス４２５に各要素を登録する（ステップＳ１０１１）。この後、ＣＰＵ４０１は、リストＮをＤＯＭ  ＤＡＧリストに追加する（ステップＳ１０１２）。また、ＣＰＵ４０１は、読み込んだＸＭＬ文書、アノテーションデータを処理済とし、ステップＳ１００６に戻る（ステップＳ１０１３）。
【００９９】
［ＤＯＭ  ＤＡＧ要素リストソート部４２６］
ここでは、ステップＳ１０１０の処理を実行するＤＯＭ  ＤＡＧ要素リストソート部４２６の処理動作を説明する。勿論、ＤＯＭ  ＤＡＧ要素リストソート部４２６としての機能は、ＣＰＵ４０１によるプログラムの実行を通じて実現する。ＤＯＭ  ＤＡＧ要素リストソート部４２６として機能するＣＰＵ４０１は、ＤＯＭ  ＤＡＧ要素のリストＮを入力とする。次に、ＣＰＵ４０１は、リストＮ内の要素を、テキスト領域開始位置と包含関係に基づいて文書内の出現順に並び替える。事前に、ＸＭＬ要素を、各アノテーショングループ毎に対応するＤＯＭ木について前順で並び換え、並び替えた要素同士をマージソートの要領でマージすると、リストＮ内の要素を効率的にソートすることができる。要素の並びは、次のルールに従うものとする。
（１）ルート要素は他のどの要素より前に来る。
（２）テキスト領域開始位置が前の要素の前に来る又はテキスト領域開始位置が同じ場合、包含する要素が前に来る。
【０１００】
［深さ割当部４２７］
ここでは、深さ割当部４２７として機能するＣＰＵ４０１の機能を説明する。図１２は、深さ割当部４２７の処理例を示すフローチャートである。
【０１０１】
まず、ＣＰＵ４０１は、ＤＯＭ  ＤＡＧ４２１の要素からなるリストＮを入力とする（ステップＳ１１０１）。次に、ＣＰＵ４０１は、ＸＭＬ文書の中で最も深い位置にある要素の深さをＤとし、長さＤの配列をＥとする（ステップＳ１１０２）。次に、ＣＰＵ４０１は、変数ｉを１とし、変数ｄを０とする（ステップＳ１１０３）。この後、ＣＰＵ４０１は、変数ｉがＮの長さ以下か否かを判定する（ステップＳ１１０４）。変数ｉがＮの長さより大きいと判定されるまで、ＣＰＵ４０１は、後述するステップＳ１１０５〜Ｓ１１１３を繰り返す。
【０１０２】
ステップＳ１１０４で肯定結果が得られた場合、ＣＰＵ４０１は、リストＮのｉ番目の要素をｖとする（ステップＳ１１０５）。次に、ＣＰＵ４０１は、ｖがＸＭＬ要素またはテキスト要素かを判定する（ステップＳ１１０６）。ここで、ｖがＸＭＬ要素またはテキスト要素であった場合、ＣＰＵ４０１は、ＤＯＭ  ＤＡＧ４２１のルート要素からの深さをｄにセットする（ステップＳ１１０７）。さらに、ＣＰＵ４０１は、Ｅのｄ番目の要素にｖのテキスト領域終了位置をセットし、ステップＳ１１０４へ戻る（ステップＳ１１０８）。
【０１０３】
一方、ステップＳ１１０６の判定処理において、ｖがＸＭＬ要素でもテキスト要素でもないと判定された場合、ＣＰＵ４０１は、ｖがアノテーションタグの開始要素か否か判定する（ステップＳ１１０９）。ここで、ｖがアノテーションタグの開始要素であると判定された場合、ＣＰＵ４０１は、ｖのテキスト領域開始位置を変数ｅにセットする（ステップＳ１１１０）。これに対し、ステップＳ１１０９の判定処理において、ｖがアノテーションタグの開始要素でないと判定された場合、ＣＰＵ４０１は、ｖのテキスト領域の終了位置を変数ｅにセットする（ステップＳ１１１１）。
【０１０４】
ｖがテキスト領域開始位置とテキスト領域終了位置のいずれであった場合でも、ＣＰＵ４０１は、変数ｄが１になるか、Ｅのｄ−１番目の要素が変数ｅより大きくなるまで、変数ｄから１を引く（ステップＳ１１１２）。この後、ＣＰＵ４０１は、ｖの深さをｄとする一方、変数ｉに１を加算し、ステップＳ１１０４に戻る（ステップＳ１１１３）。
【０１０５】
［パスＤＡＧ  ＩＤ取得部４２８］
ここでは、ＤＯＭ  ＤＡＧからパスＤＡＧを取得するパスＤＡＧ  ＩＤ取得部４２８の処理機能を説明する。図１３は、パスＤＡＧ  ＩＤ取得部４２８として機能するＣＰＵ４０１の処理例を示すフローチャートである。
【０１０６】
まず、ＣＰＵ４０１は、ＤＯＭ  ＤＡＧ４２１の要素のリストＮを入力とする（ステップＳ１２０１）。次に、ＣＰＵ４０１は、変数ｉを１にセットする（ステップＳ１２０２）。この後、ＣＰＵ４０１は、変数ｉがＮの長さ以下か否かを判定し、変数ｉがＮの長さより大きいと判定されるまで、後述するステップＳ１２０４〜Ｓ１２１３を繰り返す（ステップＳ１２０３）。
【０１０７】
変数ｉがリストＮの長さ以下であった場合、ＣＰＵ４０１は、リストＮのｉ番目の要素をｖとする（ステップＳ１２０４）。次に、ＣＰＵ４０１は、要素ｖがアノテーションの終了タグ要素か否かを判定する（ステップＳ１２０５）。この判定結果として肯定結果が得られた場合、ＣＰＵ４０１は変数ｉに１を加算し、ステップＳ１２０３に戻る（ステップＳ１２０６）。これに対し、ステップＳ１２０５の判定処理で否定結果が得られた場合、ＣＰＵ４０１は、ＤＯＭ  ＤＡＧ４２１における要素ｖの親要素の集合をＶとする（ステップＳ１２０７）。さらに、ＣＰＵ４０１は、集合Ｖの各要素に相当するパスＤＡＧ４２３の要素の集合をＰとする（ステップＳ１２０８）。さらに、ＣＰＵ４０１は、集合Ｐに属するパスＤＡＧ４２３の要素のうち共通する子要素の中で、要素ｖと同じタグ名を持つパスＤＡＧ４２３の要素の集合をＩとする（ステップＳ１２０９）。
【０１０８】
ここで、ＣＰＵ４０１は、集合Ｉの中で親要素の集合が集合Ｐと同一となる要素が存在するか否かを判定する（ステップＳ１２１０）。この判定処理において肯定結果が得られた場合、ＣＰＵ４０１は、その要素が持つパスＤＡＧ  ＩＤを要素ｖに登録し、ステップＳ１２０３に戻る（ステップＳ１２１１）。これに対し、ステップＳ１２１０の判定処理において否定結果が得られた場合、ＣＰＵ４０１は、後述するパスＤＡＧ要素生成・登録部４２９に要素ｖと集合Ｐを入力する（ステップＳ１２１２）。その後、ＣＰＵ４０１は、変数ｉに１を加算し、ステップＳ１２０３に戻る（ステップＳ１２１３）。
【０１０９】
［パスＤＡＧ要素生成・登録部４２９］
ここでは、ステップＳ１２１２で使用されるパスＤＡＧ要素生成・登録部４２９としてのＣＰＵ４０１の処理機能を説明する。図１４は、パスＤＡＧ要素生成・登録部４２９として機能するＣＰＵ４０１の処理例を示すフローチャートである。
【０１１０】
ＣＰＵ４０１は、ＤＯＭ  ＤＡＧ４２１の要素ｖとパスＤＡＧ４２３の要素Ｐを入力とする（ステップＳ１３０１）。ここで、ＣＰＵ４０１は、要素ｖが保持する深さをｄとする（ステップＳ１３０２）。
【０１１１】
次に、ＣＰＵ４０１は、要素ｖがアノテーション要素か否か判定する（ステップＳ１３０３）。要素ｖがアノテーション要素であった場合、ＣＰＵ４０１は、（２，ｄ，ＡＩ）をパスＤＡＧ  ＩＤとして要素ｖに与え、ＡＩに１を加算する（ステップＳ１３０４）。その後、ＣＰＵ４０１は、要素ｖが保持するパスＤＡＧ  ＩＤを持つパスＤＡＧ要素を作成し、集合Ｐの各要素の子要素とする（ステップＳ１３０５）。
【０１１２】
これに対し、ステップＳ１３０３で否定結果が得られた場合（すなわち、要素ｖがＸＭＬ要素であった場合）、ＣＰＵ４０１は、要素ｖのタグ名が“＃”か否か判定する（ステップＳ１３０６）。
【０１１３】
要素ｖのタグ名が＃の場合、ＣＰＵ４０１は、（１，ｄ，ＸＩ［ｄ］）をパスＤＡＧ  ＩＤとして要素ｖに与える（ステップＳ１３０７）。これに対し、要素ｖのタグ名が＃でない場合、ＣＰＵ４０１は、（０，ｄ，ＸＩ［ｄ］）をパスＤＡＧ  ＩＤとして要素ｖに与える（ステップＳ１３０８）。いずれかのパスＤＡＧ  ＩＤが要素ｖに与えられた後、ＣＰＵ４０１は、ＸＩ［ｄ］に１を加算する（ステップＳ１３０９）。
【０１１４】
［転置インデクス登録部４４２］
次に、転置インデクス登録部４４２の処理動作を説明する。図１５は、転置インデクス登録部４４２として機能するＣＰＵ４０１の処理を示すフローチャートである。
【０１１５】
まず、ＣＰＵ４０１は、ＤＯＭ  ＤＡＧ要素のリストＮと文書番号ｎを入力とする（ステップＳ１４０１）。次に、ＣＰＵ４０１は、変数ｉに１をセットする（ステップＳ１４０２）。続いて、ＣＰＵ４０１は、変数ｉがリストＮの長さ以下か否かを判定する（ステップＳ１４０３）。ＣＰＵ４０１は、変数ｉがリストＮの長さを越えると判定されるまで、後述するステップＳ１４０４〜Ｓ１４０９を繰り返す。
【０１１６】
変数ｉがリストＮの長さを越えない場合、ＣＰＵ４０１は、要素ｖがルート要素か否か判定する（ステップＳ１４０４）。要素ｖがルート要素である場合、ＣＰＵ４０１は、変数ｉに１を加算してステップＳ１４０３に戻る（ステップＳ１４０９）。これに対し、要素ｖがルート要素でなかった場合、ＣＰＵ４０１は、後述するパスＤＡＧ  ＩＤ取得部４２８に対して変数ｖを入力し、変数ｖが保持するパスＤＡＧ  ＩＤｊを取得する（ステップＳ１４０５）。
【０１１７】
この後、ＣＰＵ４０１は、転置インデクス４２５において、変数ｊに対応したエントリが存在しないか否か判定する（ステップＳ１４０６）。対応するエントリが存在しない場合、ＣＰＵ４０１は、変数ｊに対応したエントリを作成する（ステップＳ１４０８）。この後、ＣＰＵ４０１は、変数ｊ対応したエントリに対し、（ｎ、ｉ）のタプル（tuple）を追加する（ステップＳ１４０７）。その後、ＣＰＵ４０１は、変数ｉに１を加算し、ステップＳ１４０３へ戻る（ステップＳ１４０９）。
【０１１８】
［検索動作の概要］
本実施例による検索動作は以下のように進行する。本実施例の場合、ロケーションパスによる検索は、ロケーションパス検索部４２０としてのＣＰＵ４０１が、転置インデクス４２５に基づいて実行する。ロケーションパス検索部４２０としてのＣＰＵ４０１は、ロケーションパスに沿ってパスＤＡＧを辿り、ロケーションパスの構造に合致したパスＤＡＧ要素のパスＤＡＧ  ＩＤを取得する。
【０１１９】
ＣＰＵ４０１は、取得したパスＤＡＧ  ＩＤに基づいて転置インデクス４２５を検索し、ロケーションパスに合致するＤＯＭ  ＤＡＧ要素のタグ番号をＤＯＭ  ＤＡＧリストから得る。次に、ＣＰＵ４０１は、このタグ番号で特定されるＤＯＭ  ＤＡＧ要素を検索結果として取得する。
【０１２０】
以上の処理動作を具体例により説明する。ここでは、図１０を参照する。図１０は、パスＤＡＧ４２３と転置インデクス４２５を使用し、ロケーションパス「/a/b/＃」に合致する要素の検索が実行される要素を表している。この場合、ＣＰＵ４０１は、パスＤＡＧ（左下に示す構造図）上でロケーションパスを辿り、（１，３，１）をパスＤＡＧ  ＩＤとして得る。次に、ＣＰＵ４０１は、転置インデクス４２５（右下に示すテーブル）から（１，３，１）に対応するエントリを検索する。図１０の例では、破線矢印で示すように、ＤＯＭ  ＤＡＧ要素のタグ番号である（１，５）と（２，４）が得られる。次に、ＣＰＵ４０１は、このタグ番号に対応する要素を、文書１のＤＯＭ  ＤＡＧと文書２のＤＯＭ  ＤＡＧから取得する。
【０１２１】
［ロケーションパス検索部４２０］
ここでは、ロケーションパス検索部４２０として機能するＣＰＵ４０１の処理を説明する。ＣＰＵ４０１は、ロケーションパスに沿ってパスＤＡＧ４２３を辿り、到達した要素に対応するパスＤＡＧ  ＩＤを変数ｉとする。次に、ＣＰＵ４０１は、転置インデクス４２５の中からパスＤＡＧ  ＩＤｉに対応するエントリＥを取得する。エントリＥ内の各要素は、ＤＯＭ  ＤＡＧリストにあるＤＯＭ  ＤＡＧの要素のリストの場所と、ＤＯＭ  ＤＡＧリスト内の要素の場所の組になっている。ロケーションパス検索部４２０は、これら対応するＤＯＭ  ＤＡＧの要素を転置インデクス４２５から全て取得し、出力する。
【０１２２】
［実施例の効果］
本実施例に係る構造化文書検索装置４００では、複数のＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧを定義することにより、前述した実施例に比して検索効率を高めることができる。
【０１２３】
［第４の実施例］
ここでは、ＤＯＭ  ＤＡＧ４２１の計算機上での保持形態について考える。Ｃ言語等では、構造情報をポインタとして表現する。このため、ＤＯＭ  ＤＡＧ４２１の構造が複雑である場合、多数のポインタが要素間に張られることになり、元のＸＭＬ文書とアノテーションデータよりも多くのメモリが必要となる。そこで、本実施例では、パスＤＡＧと数列データにより、ＤＯＭ  ＤＡＧの構造を表現する手法を説明する。
【０１２４】
なお、本実施例に係る構造化文書検索装置４００は、ＸＭＬ文書の開始タグとアノテーションデータに出現する開始要素と終了要素について出現順に割り当てられた要素番号に基づいて、検索クエリに合致するタグの開始場所と終了場所に該当する要素を検索する。
【０１２５】
［前処理の概要］
本実施例に係る前処理は、検索インデクス構築部４２４として機能するＣＰＵ４０１が実行する。前述の実施例で説明したように、検索インデクス４３０は、パスＤＡＧと数列データにより、ＤＯＭ  ＤＡＧ４２１の構造を記述する。このため、各ＸＭＬ文書と対応するアノテーションデータについてのＤＯＭ  ＤＡＧ４２１を、主記憶装置４０２に保持する必要はない。
【０１２６】
まず、ＣＰＵ４０１は、各ＸＭＬ文書と対応するアノテーションデータについてＤＯＭ  ＤＡＧ４２１を構築する。次に、ＣＰＵ４０１は、パスＤＡＧ  ＩＤ取得部４２８として機能し、構築したＤＯＭ  ＤＡＧ４２１の各要素のパスＤＡＧ  ＩＤを取得する。この後、ＣＰＵ４０１は、取得されたパスＤＡＧ  ＩＤを順番に数列データに登録する。
【０１２７】
図１６は、図１０に示すＤＯＭ  ＤＡＧを数列データとして記録する様子を示している。左上段に示すように、ＤＯＭ  ＤＡＧ４２１の各要素には、出現順に通し番号が振られている。図１６の場合、文書１のＤＯＭ  ＤＡＧの各要素には、その出現順に“１”から“７”の通し番号が付されており、文書２のＤＯＭ  ＤＡＧの各要素には、その出現順に“８”から“１５”の通し番号が付されている。また、右上段に示すように、２つのＤＯＭ  ＤＡＧ４２１を集約したパスＤＡＧ４２３の各要素には、パスＤＡＧ  ＩＤが各階層の出現順に数列データが記録されている。
【０１２８】
［検索インデクス４３０］
図１７は、検索インデクス４３０の概要を示す。検索インデクス４３０は、複数のＤＯＭ  ＤＡＧの構造を集約したパスＤＡＧ４２３と、パスＤＡＧ４２３の各要素に振られたＩＤをＤＯＭ  ＤＡＧの各要素に割り当て、要素の出現順に登録した数列データ群と、ビット列のデータ群と、テキストデータリスト４１４とから構成される。
【０１２９】
数列データ群は、アノテーション要素判別ビット列４３１、テキスト要素判別ビット列４３２、ＸＭＬ要素の深さ数列４３３、深さ別ＩＤ列リスト４３４、アノテーション終了タグ判別ビット列４３５、アノテーション開始タグＩＤ列４３６、アノテーション終了タグＩＤ列４３７、アノテーション要素の深さ数列４３８とから構成される。テキストデータリスト４１４は、各ＸＭＬ文書内の全文字列を出現順につなげたテキストと、ＸＭＬタグとアノテーションタグにより切り分けられたテキスト分割位置のリストとから構成される。
【０１３０】
［検索インデクス構築部４５４］
図１８は、検索インデクス構築部４５４として機能するＣＰＵ４０１の処理例を示すフローチャートである。
【０１３１】
まず、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８を入力とする（ステップＳ１７０１）。次に、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１、テキスト要素判別ビット列４３２、ＸＭＬ要素の深さ数列４３３、アノテーション終了タグ判別ビット列４３５、アノテーション開始タグＩＤ列４３６、アノテーション終了タグＩＤ列４３７、アノテーション要素の深さ数列４３８を空の数列に初期化する（ステップＳ１７０２）。
【０１３２】
次に、ＣＰＵ４０１は、ＸＭＬ文書集合４０７に含まれるＸＭＬ文書の中で最も深い位置にある要素の深さをＤとする時、深さ別ＩＤ列リスト４３４に空の数列をＤ本セットする（ステップＳ１７０３）。
【０１３３】
この後、ＣＰＵ４０１は、パスＤＡＧ４２３をルート要素のみを持つグラフに初期化し、ルート要素にパスＤＡＧ  ＩＤとして（０，０，１）を与える（ステップＳ１７０４）。また、ＣＰＵ４０１は、数字ＸＤ、長さＤの数列ＸＩの各要素、数字ＡＩを０に初期化する（ステップＳ１７０４）。
【０１３４】
さらに、ＣＰＵ４０１は、テキストデータリストを空に初期化する（ステップＳ１７０５）。
【０１３５】
この後、ＣＰＵ４０１は、ＸＭＬ文書集合４０７とアノテーションデータ集合４０８に含まれる、ＸＭＬ文書とアノテーションデータの全ペアを処理したか否かを判定する（ステップＳ１７０６）。この判定処理で肯定結果が得られるまで、ＣＰＵ４０１は、後述するステップＳ１７０７〜Ｓ１７１３の処理を繰り返し実行する。
【０１３６】
ステップＳ１７０６で否定の結果が得られた場合、ＣＰＵ４０１は、未処理のＸＭＬ文書とアノテーションデータのペアを読み込む（ステップＳ１７０７）。ＸＭＬ文書から、ＸＭＬ文書からのＤＯＭ木構築部４０９により、アノテーションデータから、アノテーションデータからのＤＯＭ木構築部４１０により、ＤＯＭ木を作成する（ステップＳ１７０８）。
【０１３７】
次に、ＣＰＵ４０１は、ＸＭＬ文書から得られたＤＯＭ木と各アノテーショングループに属するタグから得られたＤＯＭ木を入力すると、後述するＤＯＭ  ＤＡＧ構築部４２２としての機能を通じてＤＯＭ  ＤＡＧ４２１を作成し、要素のリストＮを得る（ステップＳ１７０９）。
【０１３８】
この後、ＣＰＵ４０１は、リストＮをＤＯＭ  ＤＡＧ要素リストソート部４２６に入力し、ソートする（ステップＳ１７１０）。さらに、ＣＰＵ４０１は、リストＮを後述するアノテーション終了タグ挿入部４４１に入力する（ステップＳ１７１１）。次に、ＣＰＵ４０１は、リストＮを後述する検索インデクス登録部４４０に入力する（ステップＳ１７１２）。そして、ＣＰＵ４０１は、読み込んだＸＭＬ文書とアノテーションデータを処理済とし、ステップＳ１７０６に戻る（ステップＳ１７１３）。
【０１３９】
［アノテーション終了タグ要素］
アノテーション終了タグ要素とは、アノテーションの終了タグを示す要素であり、対応するアノテーション要素、深さ、パスＤＡＧ  ＩＤを保持する。アノテーション終了タグ要素は、ＤＯＭ  ＤＡＧ４２１の要素をソートしたリスト内におけるアノテーションタグの終了位置を示すために用いる。
【０１４０】
［アノテーション終了タグ挿入部４４１］
アノテーション終了タグ挿入部４４１として機能するＣＰＵ４０１は、ＤＯＭ  ＤＡＧ４２１の要素のリストＮを入力とする。ここで、ＣＰＵ４０１は、空のアノテーション要素のリストＬを用意する。
【０１４１】
ＣＰＵ４０１は、リストＮの要素を先頭から順番に走査する。リストＮの要素がアノテーション要素の場合、アノテーションタグの終了要素を作成し、該当するアノテーション要素を記録した後、リストＬの最後尾に追加する。ＣＰＵ４０１は、リストＮを走査した後、リストＬ内の要素をマージソートの要領でリストＮに挿入し、リストＬをリストＮにマージする。ソート時の順序は次のルールに従うものとする。
【０１４２】
ＤＯＭ木の要素のソート時は次のルールに従い、降順にソートする。
（１）ルート要素は他のどの要素より前に来る。
（２）リストＮ内の要素とアノテーション終了タグ要素の比較において、前者のテキスト領域開始位置が後者のテキスト領域終了位置と同じ場合、後者に保持するアノテーション要素が前者に含まれるならば、前者が前に来る。そうでない場合、後者が前にくる。
（３）リストＮ内の要素とアノテーション終了タグ要素の比較において、前者のテキスト領域終了位置が後者のテキスト領域終了位置と同じ場合、後者に対応したアノテーション要素が前者を含むならば、前者が前に来る。そうでない場合、後者が前にくる。
【０１４３】
［検索インデクス登録部４４０］
図１９は、検索インデクス登録部４４０として機能するＣＰＵ４０１の処理例を示すフローチャートである。
【０１４４】
ＣＰＵ４０１は、ＤＯＭ  ＤＡＧ４２１の要素からなるリストＮを入力とする（ステップＳ１８０１）。次に、ＣＰＵ４０１は、変数ｉに１をセットする（ステップＳ１８０２）。その後、ＣＰＵ４０１は、変数ｉがリストＮの長さ以下か判定する（ステップＳ１８０３）。ＣＰＵ４０１は、変数ｉがリストＮの長さを越えるまで、後述するステップＳ１８０４〜Ｓ１８１１を繰り返す。
【０１４５】
変数ｉがリストＮの長さ以下の場合、ＣＰＵ４０１は、リストＮのｉ番目の要素をｖとする（ステップＳ１８０４）。ここで、ＣＰＵ４０１は、要素ｖがアノテーションタグの終了要素か否か判定する（ステップＳ１８０５）。肯定結果が得られた場合、ＣＰＵ４０１は、要素ｖに対応した開始要素のパスＤＡＧ  ＩＤｊを取得し、ＩＤｊの１番目の要素に３をセットする（ステップＳ１８０６）。一方、ステップＳ１８０５で否定結果が得られた場合、ＣＰＵ４０１は、後述するパスＤＡＧ  ＩＤ取得部４２８に要素ｖを入力し、要素ｖが保持するパスＤＡＧ  ＩＤｊを取得する（ステップＳ１８０７、Ｓ１８０８）。
【０１４６】
以上の処理の後、ＣＰＵ４０１は、ＩＤｊをパスＤＡＧ  ＩＤとしてＤＮに登録する（ステップＳ１８０９）。さらに、ＣＰＵ４０１は、ＩＤｊをパスＤＡＧ  ＩＤ登録部４３９に入力する（ステップＳ１８１０）。この後、ＣＰＵ４０１は、変数ｉに１を加算し、ステップＳ１８０３に戻る（ステップＳ１８１１）。
【０１４７】
［パスＤＡＧ  ＩＤ登録部４３９］
前述のステップＳ１８１０で使用されるパスＤＡＧ  ＩＤ登録部４３９の処理内容を説明する。図２０は、パスＤＡＧ  ＩＤ登録部４３９として機能するＣＰＵ４０１の処理内容を示すフローチャートである。
【０１４８】
まず、ＣＰＵ４０１は、パスＤＡＧ  ＩＤｉを入力とする（ステップＳ１９０１）。次に、ＣＰＵ４０１は、ＩＤｉのｊ番目の要素をｉ［ｊ］とする（ステップＳ１９０２）。
ここで、ＣＰＵ４０１は、ｉ［１］が０または１であるか判定する（ステップＳ１９０３）。ｉ［１］が０または１の時、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１の最後尾に０を追加し（ステップＳ１９０４）、ＸＭＬ要素の深さ数列４３３の最後尾にｉ［２］を加え（ステップＳ１９０５）、テキスト要素判別ビット列４３２の最後尾にｉ［１］を加える（ステップＳ１９０６）。
【０１４９】
さらに、ＣＰＵ４０１は、ｉ［２］が０か否かを判定する（ステップＳ１９０７）。ｉ［２］が０であれば、ＣＰＵ４０１は、この時点で登録処理を終了する。これに対し、ｉ［２］が０以外の場合、ＣＰＵ４０１は、深さ別ＩＤ列リスト４３４にあるｉ［２］番目の数列の最後尾にｉ［３］を加え、登録処理を終了する（ステップＳ１９０８）。
【０１５０】
一方、ステップＳ１９０３で否定結果の場合、すなわちｉ［１］が２また３の時、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１の最後尾に１を追加する（ステップＳ１９１０）。さらに、ＣＰＵ４０１は、アノテーション要素の深さ数列４３８の最後尾にｉ［２］を加える（ステップＳ１９１１）。
【０１５１】
この後、ＣＰＵ４０１は、ｉ［１］が２であるか否かを判定する（ステップＳ１９１２）。ｉ［１］が２の場合、ＣＰＵ４０１は、アノテーション終了タグ判別ビット列４３５の最後尾に０を加えると共に、アノテーション開始タグＩＤ列４３６の最後尾にｉ［３］を加え、登録処理を終了する（ステップＳ１９１３、Ｓ１９１４）。
【０１５２】
これに対し、ステップＳ１９１２で否定結果が得られた場合、すなわちｉ［１］が３の場合、ＣＰＵ４０１は、アノテーション終了タグ判別ビット列４３５の最後尾に１を加えると共に、アノテーション終了タグＩＤ列４３７の最後尾にｉ［３］を加え、登録処理を終了する（ステップＳ１９１５、Ｓ１９１６）。
【０１５３】
［検索動作の概要］
ここで、本実施例に係る検索動作を説明する。本実施例における検索動作は、ロケーションパス検索部４２０として機能するＣＰＵ４０１により実行される。ＣＰＵ４０１は、検索クエリで与えられたロケーションパスに沿ってパスＤＡＧを辿り、ロケーションパスの構造に合致したパスＤＡＧ要素のパスＤＡＧ  ＩＤを取得する。
【０１５４】
ＣＰＵ４０１は、取得したパスＤＡＧ  ＩＤから、検索結果となる要素がＸＭＬ要素かアノテーション要素か判定する。検索結果となる要素がＸＭＬ要素の場合、ＣＰＵ４０１は、ＸＭＬ要素検索部４４３として機能し、検索クエリに合致した数列データにおける要素の箇所を計算する。一方、検索結果となる要素がアノテーション要素の場合、ＣＰＵ４０１は、アノテーション要素検索部４４４として機能し、検索クエリに合致した数列データにおける要素の箇所を計算する。
【０１５５】
ここで、ＸＭＬ要素検索部４４３とアノテーション要素検索部４４４は、数列に対して次のｒａｎｋと、ｓｅｌｅｃｔと、ｎｅａｒｅｓｔと呼ばれる演算を実行する。
（１）ｒａｎｋ（ｃ，ｐ）：数列において、ｐ番目の位置の要素にあるｃの数
（２）ｓｅｌｅｃｔ（ｃ，ｎ）：数列において、ｎ回目に出現するｃの位置
（３）ｎｅａｒｅｓｔ（ｐ，ｄ）：数列において、ｐ番目より後ろの要素でｄ以下の値を持つ、ｐに最も近い要素の位置
【０１５６】
ここでは、図１６を参照して、一連の処理動作を説明する。図１６は、パスＤＡＧ４２３と数列データを使用して、ロケーションパス「/e/c/d」に合致する要素を検索する例を示す。
【０１５７】
まず、ＣＰＵ４０１は、ロケーションパスに沿ってパスＤＡＧを辿ることで、パスＤＡＧ  ＩＤである（０，３，３）を得る。図１６では、該当するパスＤＡＧ  ＩＤを破線で囲んで示している。ここで、パスＤＡＧ  ＩＤの１番目の要素が“０”の時はＸＭＬ要素を示し、２番目の要素である“３”は深さを示している。
【０１５８】
従って、ＣＰＵ４０１は、深さ別ＩＤ列リスト４３４の３番目の数列（深さが“３”の位置の数列）において、パスＤＡＧ  ＩＤの３番目の要素である“３”を含む位置を探す。図１６の場合、“３”は、深さ“３”の数列内の４番目にある。この要素も、図１６では、破線で囲んで示している。
【０１５９】
次に、ＣＰＵ４０１は、ＸＭＬ要素の深さ数列４３３について、ｓｅｌｅｃｔ（３，４）を計算し、“３”が４回目に出現する位置である“１４”を得る。次に、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１に対して、ｓｅｌｅｃｔ（０，１４）を計算する。アノテーション要素判別ビット列４３１では、ＸＭＬ要素の位置には０が登録されているためである。従って、この演算は、アノテーション要素判別ビット列４３１で、１４回目に出現するＸＭＬ要素の位置を求めることを意味する。ここでは、演算結果として“１５”を得る。
【０１６０】
図１６の左上段に示すように、“１５”に対応するＤＯＭ  ＤＡＧの要素は、ＸＭＬ文書２のＤＯＭ  ＤＡＧの“ｄ”である。なお、“１５”は、要素における開始タグの位置を示している。要素の終了タグの位置についても同様の方法で取得できる。
【０１６１】
［ロケーションパス検索部４２０］
図２１は、ロケーションパス検索部４２０として機能するＣＰＵ４０１の処理を示すフローチャートである。
【０１６２】
ＣＰＵ４０１は、ロケーションパスに沿ってパスＤＡＧ４２３を辿り、到達した要素に対応するパスＤＡＧ  ＩＤをｉとする（ステップ２００１）。次に、ＣＰＵ４０１は、ＩＤｉの１番目の要素をｓ、２番目の要素をｄとする（ステップＳ２００２）。また、ＣＰＵ４０１は、変数ｊに１をセットする（ステップＳ２００３）。さらに、ＣＰＵ４０１は、Ｌを、検索対象のタグの開始位置と終了位置のペアを保持するための空のリストとする（ステップＳ２００４）。
【０１６３】
ここで、ＣＰＵ４０１は、要素ｓが０または１か判定する（ステップＳ２００５）。要素ｓが０または１であれば、ＣＰＵ４０１は、ＸＭＬ要素検索部４４３に対してｉとｊを入力し、得られたタグの開始位置、終了位置のタプルｔを得る（ステップＳ２００６）。
【０１６４】
次に、ＣＰＵ４０１は、タプルｔが（−１，−１）であるか否か判定する（ステップＳ２００７）。タプルｔが（−１，−１）でない場合、ＣＰＵ４０１は、タプルｔをリストＬの最後尾に加え、ｊを１増やす（ステップＳ２００８、Ｓ２００９）。タプルｔが（−１、−１）となるまでステップＳ２００６〜Ｓ２００９を繰り返す（ステップＳ２００７）。なお、ＣＰＵ４０１は、タプルｔが（−１、−１）となるまで、ＣＰＵ４０１は、ステップＳ２００６〜Ｓ２００９を繰り返す。そして、タプルｔが（−１，−１）となると、ＣＰＵ４０１は、リストＬを出力し、検索処理を終了する（ステップＳ２０１４）。
【０１６５】
これに対し、ステップＳ２００５で否定結果が得られた場合（この場合は、要素ｓが０と１のどちらでもない場合）、ＣＰＵ４０１は、アノテーション要素検索部４４４に対してｉとｊを入力し、得られたタグの開始位置と終了位置のタプルをｔとする（ステップＳ２０１０）。
【０１６６】
ここで、ＣＰＵ４０１は、タプルｔが（−１，−１）であるか否か判定する（ステップＳ２０１１）。この場合も、タプルｔが（−１，−１）でない場合、ＣＰＵ４０１は、タプルｔをリストＬの最後尾に加え、変数ｊに１を加算する（ステップＳ２０１２、Ｓ２０１３）。そして、タプルｔが（−１、−１）となるまで、ＣＰＵ４０１は、ステップＳ２０１０〜Ｓ２０１３を繰り返す。そして、タプルｔが（−１，−１）となると、ＣＰＵ４０１は、リストＬを出力し、検索処理を終了する（ステップＳ２０１４）。
【０１６７】
［ＸＭＬ要素検索部４４３］
図２２は、ＸＭＬ要素検索部４４３として機能するＣＰＵ４０１の処理を示すフローチャートである。
【０１６８】
まず、ＣＰＵ４０１は、入力されたパスＤＡＧ  ＩＤをｉ、検索番号をｎとする（ステップＳ２１０１）。次に、ＣＰＵ２０１は、パスＤＡＧ  ＩＤｉの２番目の要素をｄ、３番目の要素をｊとする（ステップＳ２１０２）。さらに、ＣＰＵ４０１は、深さ別ＩＤ列リスト４３４のｄ番目の数列にｊが含まれる数をｍとする（ステップＳ２１０３）。
【０１６９】
ここで、ＣＰＵ４０１は、ｍがｎより小さいか判定する（ステップＳ２１０４）。ｍがｎより少ない場合、ＣＰＵ４０１は、２つの要素からなるタプル（−１，−１）を出力して探索処理を終了する（ステップＳ２１０５）。
【０１７０】
これに対し、ｍがｎ以上であった場合、ＣＰＵ４０１は、深さ別ＩＤ列リスト４３４のｄ番目の数列に対して、ｓｅｌｅｃｔ（ｊ，ｎ）を計算し、結果をｎにセットする（ステップＳ２１０６）。
【０１７１】
次に、ＣＰＵ４０１は、ＸＭＬ要素の深さ数列４３３に対して、ｓｅｌｅｃｔ（ｄ，ｎ）を計算し、その結果をｎにセットする（ステップＳ２１０７）。
【０１７２】
さらに、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１に対して、ｓｅｌｅｃｔ（０，ｎ）を計算し、変数ｓにセットする（ステップＳ２１０８）。
【０１７３】
次に、ＣＰＵ４０１は、ＸＭＬ要素の深さ数列４３３に対して、ｎｅａｒｅｓｔ（ｎ，ｄ）を計算し、結果を変数ｐにセットする（ステップＳ２１０９）。
【０１７４】
その後、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１に対して、ｓｅｌｅｃｔ（０，ｐ）を計算し、結果をｐにセットする（ステップＳ２１１０）。
【０１７５】
次に、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１に対して、ｒａｎｋ（１，ｎ）を計算し、結果を変数ｒにセットする（ステップＳ２１１１）。
【０１７６】
さらに、ＣＰＵ４０１は、アノテーション要素の深さ数列４３８に対して、ｎｅａｒｅｓｔ（ｒ，ｄ）を計算し、結果をｒにセットする（ステップＳ２１１２）。
【０１７７】
また、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１に対して、ｓｅｌｅｃｔ（１，ｑ）を計算し、変数ｑにセットする（ステップＳ２１１３）。
【０１７８】
また、ＣＰＵ４０１は、変数ｅにｐとｑで小さい方をセットする（ステップＳ２１１４）。
【０１７９】
そして、ＣＰＵ４０１は、ｓとｅのペアのタプル（ｓ，ｅ）を出力する（ステップＳ２１１５）。
【０１８０】
［アノテーション要素検索部４４４］
図２３は、アノテーション要素検索部４４４として機能するＣＰＵ４０１の処理を示すフローチャートである。
【０１８１】
まず、ＣＰＵ４０１は、入力されたパスＤＡＧ  ＩＤをｉ、検索番号をｎとする（ステップＳ２２０１）。次に、ＣＰＵ４０１は、ｉの３番目の要素をｊとする（ステップＳ２２０２）。また、ＣＰＵ４０１は、アノテーション開始タグＩＤ列４３６にｊが含まれる数をｍとする（ステップＳ２２０３）。
【０１８２】
ここで、ＣＰＵ４０１は、ｍがｎより小さいか否か判定する（ステップＳ２２０４）。ｍがｎより小さい場合、ＣＰＵ４０１は、２つの要素からなるタプル（−１，−１）を出力して検索処理を終了する（ステップＳ２２０５）。
【０１８３】
一方、ｍがｎ以上であった場合、ＣＰＵ４０１は、アノテーション開始タグＩＤ列４３６に対して、ｓｅｌｅｃｔ（ｊ，ｎ）を計算し、結果をｍにセットする（ステップＳ２２０６）。
【０１８４】
次に、ＣＰＵ４０１は、アノテーション終了タグ判別ビット列４３５に対して、ｓｅｌｅｃｔ（０，ｍ）を計算し、結果をｍにセットする（ステップＳ２２０７）。
【０１８５】
さらに、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１に対して、ｓｅｌｅｃｔ（１，ｍ）を計算し、変数ｓにセットする（ステップＳ２２０８）。
【０１８６】
また、ＣＰＵ４０１は、アノテーション終了タグＩＤ列４３７に対して、ｓｅｌｅｃｔ（ｊ，ｎ）を計算し、結果をｍにセットする（ステップＳ２２０９）。
【０１８７】
その後、ＣＰＵ４０１は、アノテーション終了タグ判別ビット列４３５に対して、ｓｅｌｅｃｔ（１，ｍ）を計算し、結果をｍにセットする（ステップＳ２２１０）。
【０１８８】
また、ＣＰＵ４０１は、アノテーション要素判別ビット列４３１に対して、ｓｅｌｅｃｔ（１，ｍ）を計算し、変数ｅにセットする（ステップＳ２２１１）。
【０１８９】
さらに、ＣＰＵ４０１は、ｓとｅのペアのタプル（ｓ，ｅ）を出力する（ステップＳ２２１２）。
【０１９０】
［実施例の効果］
本実施例に係る構造化文書検索装置４００では、パスＤＡＧと数列データによりＤＯＭ  ＤＡＧの構造を記述する手法を採用する。この場合、構造化文書検索装置４００は、各ＸＭＬ文書と対応するアノテーションデータから作成されたＤＯＭ  ＤＡＧを保持する必要がなく、前述した実施例に比してメモリ容量の消費量を大幅に低減することができる。
【０１９１】
［第５の実施例］
定数オーダの計算量により、ビット列に対してｒａｎｋやｓｅｌｅｃｔを計算することができるデータ構造として、簡潔ビットベクトルが知られている。また、数列データをデータ圧縮した状態で保持し、圧縮した状態のままｒａｎｋやｓｅｌｅｃｔを効率良く計算することができるデータ構造として、ウェーブレット木が知られている。
【０１９２】
ウェーブレット木は、簡潔ビットベクトルを発展させたデータ構造であり、どちらも事前に計算のための辞書データが必要となる。辞書データの構築法、データ構造を用いたｒａｎｋやｓｅｌｅｃｔの計算方法は、非特許文献２に記載された手法等を用いれば良い。
【０１９３】
本実施例では、検索インデクス構築部４５４としての処理機能の実行後、簡易ビットベクトル・ウェーブレット木構築部４５５が、前述した公知の方法により、アノテーション終了タグ判別ビット列４３５、テキスト要素判別ビット列４３２、アノテーション要素判別ビット列４３１に対して簡潔ビットベクトルを生成すると共に、ＸＭＬ要素の深さ数列４３３、深さ別ＩＤ列リスト４３４、アノテーション開始タグＩＤ列４３６、アノテーション終了タグＩＤ列４３７、アノテーション要素の深さ数列４３８に対してウェーブレット木を生成する。
【０１９４】
［実施例の効果］
本実施例に係る構造化文書検索装置４００は、用意した簡潔ビットベクトル、ウェーブレット木を用いることにより、ＸＭＬ要素検索部４４３とアノテーション要素検索部４４４におけるｒａｎｋ演算及びｓｅｌｅｃｔ演算を効率化することができる。
【０１９５】
［第６の実施例］
実運用面では、同じＸＭＬ文書に対して、異なるアノテーションデータを追加し又は削除できることが望まれる。本実施例では、与えられたＸＭＬ文書に対して既にインデクスが構築された状態において、インデクスの構成を大きく変更することなく、アノテーション要素群を追加する手法について説明する。
【０１９６】
アノテーション要素が追加されると、各要素の親の集合が変更される。このため、これまでパスＤＡＧ上で同一と考えられていた要素を別の要素として扱わなければならない。また、アノテーションを追加すると、テキスト領域が分割されるため、パスＤＡＧ  ＩＤの変更だけでなく、テキスト領域を表す要素の数も増える問題がある。また、アノテーションを追加すると、パスＤＡＧの構造を変更するだけでなく、数列データにある数字ｃの一部を、これまで数列になかった数字とｃからなる数列に置換する必要が発生する。
【０１９７】
以下では、ウェーブレット木４４６に登録されている数列にある数字ｃの一部が、これまで数列になかった数字からなる数列Ｎに変更となった場合に、既存のウェーブレット木４４６にデータ構造を追加することで、変更時におけるｒａｎｋ、ｓｅｌｅｃｔ、ｌｏｏｋｕｐを可能とする拡張ウェーブレット木４４５について説明する。
【０１９８】
［拡張ウェーブレット木４４５］
図２４は、拡張ウェーブレット木４４５の概要を示す図である。拡張ウェーブレット木４４５は、元の数列から構成されたウェーブレット木４４６、変更となった数字ｘが元の数列に登録されたどの数字になるかを示す数字変更表４４７、数列全体において、どの部分の数字が追加されたかを示す追加フラグ４４８、元の数列の各数字に対して、どの位置に追加されたかを示す数字別追加フラグ４４９、元の数列を構成する数字において、変更に関連した数字に対応した変更ウェーブレット４５０から構成される。
【０１９９】
［拡張ウェーブレット木構築部４５１］
図２５は、拡張ウェーブレット木構築部４４５として機能するＣＰＵ４０１の処理を示すフローチャートである。ＣＰＵ４０１は、ウェーブレット木４４６に登録されている数列のｐ番目にある数字ｃが数列Ｎに変更された場合、以下の手順により、ウェーブレット木４４６を拡張する。
【０２００】
まず、ＣＰＵ４０１は、ウェーブレット木４４６に登録されている数列と同じ長さで全ての値が０で初期化された数列Ｂを用意する（ステップＳ２４０１）。次に、ＣＰＵ４０１は、リストＮの長さを｜Ｎ｜とし、数列Ｂのｐ番目以降に｜Ｎ｜−１個の“１”を追加する（ステップＳ２４０２）。
【０２０１】
この後、ＣＰＵ４０１は、数列Ｂの簡潔ビットベクトルを作成し、これを追加フラグ４４８とする（ステップＳ２４０３）。次に、ＣＰＵ４０１は、追加フラグ４４８のｒａｎｋ（ｐ，ｃ）を計算し、計算結果をｑとする（ステップＳ２４０４）。
【０２０２】
ここで、ＣＰＵ４０１は、ウェーブレット木４４６に登録されている数字ｃの個数をｍとする（ステップＳ２４０５）。さらに、ＣＰＵ４０１は、全ての値が０で初期化された長さｍの数列Ｖを用意し、ｑ番目以降に｜Ｎ｜−１個の“１”を追加する（ステップＳ２４０６）。
【０２０３】
この後、ＣＰＵ４０１は、数列Ｖの簡潔ビットベクトルを作成し、これを数字ｃに対応した数字別追加フラグ４４９とする（ステップＳ２４０７）。さらに、ＣＰＵ４０１は、数列Ｎを保持するウェーブレット木を作成し、これを数字ｃに対応した変更ウェーブレット４５０とする（ステップＳ２４０８）。その後、ＣＰＵ４０１は、変更された数列を構成する各数字が、元の数列を構成していたどの数字に対応するかを記述した数字変更表４４７を作成する（ステップＳ２４０９）。
【０２０４】
［拡張ウェーブレット木におけるｒａｎｋ計算部４５２］
図２６は、拡張ウェーブレット木４４５についてｒａｎｋ計算を実行するｒａｎｋ計算部４５２として機能するＣＰＵ４０１の処理を示すフローチャートである。
【０２０５】
まず、ＣＰＵ４０１は、追加フラグ４４８に対してｒａｎｋ（０，ｐ）を計算し、ｑとする（ステップＳ２５０１）。次に、ＣＰＵ４０１は、数字変更表４４７から、ｃの元の数列における数字を取得し、これをｄとする（ステップＳ２５０２）。次に、ＣＰＵ４０１は、元のウェーブレット木４４６に対して、ｒａｎｋ（ｃ，ｑ）を計算し、計算結果をｒとする（ステップＳ２５０３）。
【０２０６】
ここで、ＣＰＵ４０１は、ｃとｄが同じか否か判定する（ステップＳ２５０４）。ｃとｄが同じでない場合、ＣＰＵ４０１はｒを出力し、演算処理を終了する（ステップＳ２５０８）。
【０２０７】
これに対し、ｃとｄが同じ場合、ＣＰＵ４０１は、追加フラグ４４８に対して、ｓｅｌｅｃｔ（０，ｑ）を計算し、計算結果をｓとする（ステップＳ２５０５）。次に、ＣＰＵ４０１は、ｄに対応した数字別追加フラグ４４９に対して、ｓｅｌｅｃｔ（０，ｒ）を計算し、計算結果をｔとする（ステップＳ２５０６）。また、ＣＰＵ４０１は、ｄに対応した数字別追加フラグ４４９に対して、ｒａｎｋ（ｃ，ｔ＋ｐ−ｓ）を計算し、計算結果を出力し、演算処理を終了する（ステップＳ２５０７）。
【０２０８】
［拡張ウェーブレット木におけるｓｅｌｅｃｔ計算部４５３］
図２７は、拡張ウェーブレット木４４５についてｓｅｌｅｃｔ計算を実行するｓｅｌｅｃｔ計算部４５３として機能するＣＰＵ４０１の処理を示すフローチャートである。
【０２０９】
まず、ＣＰＵ４０１は、数字変更表４４７から、ｃの元の数列における数字を取得し、これをｄとする（ステップＳ２６０１）。
【０２１０】
ここで、ＣＰＵ４０１は、ｃとｄが異なるか否か判定する（ステップＳ２６０２）。ｃがｄと異なる場合（肯定結果）、ＣＰＵ４０１は、ｄに該当する追加ウェーブレット木に対して、ｓｅｌｅｃｔ（ｃ,ｎ）を計算し、計算結果をｓとする（ステップＳ２６０３）。さらに、ＣＰＵ４０１は、ｄに対応した数字別追加フラグ４４９に対して、ｒａｎｋ（０，ｓ）を計算し、計算結果をｎとする（ステップＳ２６０４）。
【０２１１】
このステップＳ２６０４の後、又はステップＳ２６０２で否定結果を得た後、ＣＰＵ４０１は、ｄに対応した数字別追加フラグ４４９に対して、ｓｅｌｅｃｔ（０，ｎ）を計算し、計算結果をｔとする（ステップＳ２６０６）。
【０２１２】
次に、ＣＰＵ４０１は、元のウェーブレット木４４６に対して、ｓｅｌｅｃｔ（ｄ，ｎ）を計算し、計算結果をｍとする（ステップＳ２６０７）。また、ＣＰＵ４０１は、追加フラグ４４８に対して、ｓｅｌｅｃｔ（０，ｍ）を計算し、計算結果をｕとする（ステップＳ２６０８）。
【０２１３】
ここで、ＣＰＵ４０１は、ｃとｄが同じか否か判定する（ステップＳ２６０９）。ｃとｄが同じ場合、ＣＰＵ４０１は、ｕを出力して計算処理を終了する（ステップＳ２６１０）。一方、ｃとｄが異なる場合、ＣＰＵ４０１は、ｓ−ｔ＋ｕを計算結果として出力し、計算処理を終了する（ステップＳ２６１１）。
【０２１４】
［実施例の効果］
本実施例に係る構造化文書検索装置４００によれば、同じＸＭＬ文書に対して、異なるアノテーションデータを追加し又は削除することが可能になる。
【０２１５】
[他の実施例]
本発明は、上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば上述した実施例は、本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備える場合に限定されるものではない。
【０２１６】
また、ある実施例の構成の一部を他の実施例の構成に置き換えることが可能である。また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成を追加し、削除し、又は置換することもできる。
【０２１７】
また、上述した各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上述した各構成、機能等は、ＣＰＵがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。
【０２１８】
各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Solid State Drive）等の記録装置、または、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。
【０２１９】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。実際には殆ど全ての構成が相互に接続されていると考えてもよい。
【符号の説明】
【０２２０】
４００  構造化文書検索装置
４０１  ＣＰＵ（中央演算装置）
４０２  主記憶装置
４０３Ａ  補助記憶装置
４０３Ｂ  外部記憶装置
４０４  リムーバブルメディア
４０５  ネットワーク
４０６  インターフェース部
４０７  ＸＭＬ文書集合
４０８  アノテーションデータ集合
４０９  ＤＯＭ木構築部（ＸＭＬ文書用）
４１０  ＤＯＭ木構築部（アノテーションデータ用）
４１１  文書構造リスト構築部
４１２  文書構造リスト
４１３  テキスト要素リスト
４１４  テキストデータリスト
４１５  テキスト共有ＤＯＭ木構築部
４１６  テキスト共有ＤＯＭ木
４１７  テキストデータ・テキスト要素リスト構築部
４１８  テキスト割当部
４１９  親子関係解析・登録部
４２０  ロケーションパス検索部
４２１  ＤＯＭ  ＤＡＧ
４２２  ＤＯＭ  ＤＡＧ構築部
４２３  パスＤＡＧ
４２４  転置インデクス構築部
４２５  転置インデクス
４２６  ＤＯＭ  ＤＡＧ要素リストソート部
４２７  深さ割当部
４２８  パスＤＡＧ  ＩＤ取得部
４２９  パスＤＡＧ要素生成・登録部
４３０  検索インデクス
４３１  アノテーション要素判別ビット列
４３２  テキスト要素判別ビット列
４３３  ＸＭＬ要素の深さ数列
４３４  深さ別ＩＤ列リスト
４３５  アノテーション終了タグ判別ビット列
４３６  アノテーション開始タグＩＤ列
４３７  アノテーション終了タグＩＤ列
４３８  アノテーション要素の深さ数列
４３９  パスＤＡＧ  ＩＤ登録部
４４０  検索インデクス登録部
４４１  アノテーション終了タグ挿入部
４４２  転置インデクス登録部
４４３  ＸＭＬ要素検索部
４４４  アノテーション要素検索部
４４５  拡張ウェーブレット木
４４６  元の数列から構成されたウェーブレット木
４４７  数字変更表
４４８  追加フラグ
４４９  数字別追加フラグ
４５０  変更ウェーブレット木
４５１  拡張ウェーブレット木構築部
４５２  拡張ウェーブレット木におけるｒａｎｋ計算部
４５３  拡張ウェーブレット木におけるｓｅｌｅｃｔ計算部
４５４  検索インデクス構築部
４５５  簡易ビットベクトル・ウェーブレット木構築部
【図１−１】
2013246522.tif 000003
【図１−２】
2013246522.tif 000004
【図２】
2013246522.tif 000005
【図３】
2013246522.tif 000006
【図４】
2013246522.tif 000007
【図５】
2013246522.tif 000008
【図６】
2013246522.tif 000009
【図７】
2013246522.tif 000010
【図８】
2013246522.tif 000011
【図９】
2013246522.tif 000012
【図１０】
2013246522.tif 000013
【図１１】
2013246522.tif 000014
【図１２】
2013246522.tif 000015
【図１３】
2013246522.tif 000016
【図１４】
2013246522.tif 000017
【図１５】
2013246522.tif 000018
【図１６】
2013246522.tif 000019
【図１７】
2013246522.tif 000020
【図１８】
2013246522.tif 000021
【図１９】
2013246522.tif 000022
【図２０】
2013246522.tif 000023
【図２１】
2013246522.tif 000024
【図２２】
2013246522.tif 000025
【図２３】
2013246522.tif 000026
【図２４】
2013246522.tif 000027
【図２５】
2013246522.tif 000028
【図２６】
2013246522.tif 000029
【図２７】
2013246522.tif 000030