(57)【要約】【課題】巨大な全文インデクス群を構築することなく、混合内容を含むＸＭＬ文書に対する、任意の構造を指定した全文検索を実現する。【解決手段】本発明は、ＸＭＬ文書群の各文書に対して文書ＩＤを付与し、該文書の全ノードにタグを跨ぐことを許す範囲ラベルを付与し、範囲ラベル記憶手段に格納し、ＸＭＬ文書のテキストから単語を切り出して、該単語の出現位置と文書ＩＤの組からなる出現位置情報を転置表記憶手段の転置表に格納する格納過程と、入力された検索クエリから、検索パスと検索キーワードを抽出し、範囲ラベル記憶手段から検索パスに該当する文書ＩＤ及び範囲ラベルを取得し、転置表記憶手段から検索キーワードに合致する出現位置情報を取得し、文書ＩＤと範囲ラベルから、検索キーワードの出現位置情報が存在するノード情報を選択する。【選択図】図１
2010108191.tif 000002
【特許請求の範囲】
【請求項１】
構造化データであるテキストとタグが混在するＸＭＬ文書群に対して全文検索を行う全文検索方法であって、
ＸＭＬの各ノード間の構造上の関係を管理するノード管理手段と、該ＸＭＬの文書内の単語にインデクスを構築する全文インデクス手段と、検索を実行する検索手段と、を有する装置において、
前記ノード管理手段が、入力されたＸＭＬ文書群の個々の文書に対して文書ＩＤを付与し、該文書の全てのノードにタグを跨ぐことを許す範囲ラベルを付与し、範囲ラベル記憶手段に格納する範囲ラベル付与ステップを行い、
前記全文インデクス手段が、前記ＸＭＬ文書のテキストから単語及びタグを跨いだ単語を切り出して、該ＸＭＬ文書における該単語の出現位置と文書ＩＤの組からなる出現位置情報を転置表記憶手段の転置表に格納する転置表格納ステップを行う、
からなる格納過程と、
前記検索手段が、入力された検索クエリから、検索パスと検索キーワードを抽出し、前記範囲ラベル記憶手段から検索パスに該当する文書ＩＤ及び範囲ラベルを取得する範囲ラベル取得ステップと、
前記転置表記憶手段から、前記検索キーワードに合致する出現位置情報を取得する出現位置情報取得ステップと、
前記範囲ラベル取得ステップで取得した前記文書ＩＤと前記範囲ラベルから、前記出現位置情報取得ステップで取得した前記検索キーワードの出現位置情報が存在するノード情報を選択するノード情報選択ステップと、
からなる検索過程と、
を行うことを特徴とする全文検索方法。
【請求項２】
前記格納過程の前記範囲ラベル付与ステップにおいて、
前記ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、記述内容を範囲ラベルとして前記範囲ラベル記憶手段に格納し、
前記格納過程の前記転置表格納ステップにおいて、
前記ＸＭＬ文書を一定の長さの文字列に分割し、該文字列を形態素解析することにより単語及びタグを跨いだ単語を切り出す形態素解析ステップと、
切り出した単語毎に、単語の最初の文字が出現したノードのpreorder値と、該単語の最後の文字が出現したノードのpostorder値を取得し、前記文書ＩＤ、該preorder値、該postorder値を前記出現位置情報として前記転置表記憶手段の転置表に格納する第1の範囲ラベル付与ステップと、
を行う請求項1記載の全文検索方法。
【請求項３】
前記検索過程の前記範囲ラベル取得ステップにおいて、
前記検索キーワードを形態素解析し、検索単語を取得し、
前記検索単語に基づいて前記転置表記憶手段の転置表から該検索単語の出現位置情報を取得する
請求項１記載の全文検索方法。
【請求項４】
前記格納過程の前記範囲ラベル付与ステップにおいて、
前記ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、全テキストノードを連結した際の開始文字オフセット、記述内容を範囲ラベルとして前記範囲ラベル記憶手段に格納し、
前記格納過程の前記転置表格納ステップにおいて、
前記ＸＭＬ文書の全テキストノードを連結し、一定の長さの文字列に分割し、N-gram方式により単語を切り出し、切り出した単語がテキストノードを跨っている場合は、該テキストノードの終端までのＭ文字（但し、Ｍは1以上の整数）も重複して切り出す単語切り出しステップと、
切り出した単語毎に、開始位置が含まれるノード識別子preorder値と、終了位置が含まれるノード識別子postorder値と、連結したテキスト中の開始位置を取得し、該preorder値、該postorder値、該開始位置、前記文書ＩＤを前記出現位置情報として前記転置表記憶手段の転置表に格納する第２の範囲ラベル付与ステップと、
を行う請求項１記載の全文検索方法。
【請求項５】
前記検索過程の前記範囲ラベル取得ステップにおいて、
前記検索キーワードをN-gram分解し、検索単語を取得し、
前記検索単語に基づいて前記転置表記憶手段の転置表から該検索単語の出現位置情報を取得し、
前記検索単語の出現位置情報の開始位置を付き合わせ、前記検索キーワードの出現位置情報を取得する
請求項１記載の全文検索方法。
【請求項６】
構造化データであるテキストとタグが混在するＸＭＬ文書群に対して全文検索を行う全文検索装置であって、
ＸＭＬの各ノード間の構造上の関係を管理するノード管理手段と、該ＸＭＬの文書内の単語にインデクスを構築する全文インデクス手段と、検索を実行する検索手段と、を有し、
前記ノード管理手段は、
入力されたＸＭＬ文書群の個々の文書に対して文書ＩＤを付与し、該文書の全てのノードにタグを跨ぐことを許す範囲ラベルを付与し、範囲ラベル記憶手段に格納する範囲ラベル付与手段を有し、
前記全文インデクス手段は、
前記ＸＭＬ文書のテキストから単語及びタグを跨いだ単語を切り出して、該ＸＭＬ文書における該単語の出現位置と文書ＩＤの組からなる出現位置情報を転置表記憶手段の転置表に格納する転置表格納手段を有し、
前記検索手段は、
入力された検索クエリから、検索パスと検索キーワードを抽出し、前記範囲ラベル記憶手段から検索パスに該当する文書ＩＤ及び範囲ラベルを取得する範囲ラベル取得手段と、
前記転置表記憶手段から、前記検索キーワードに合致する出現位置情報を取得し、出現位置情報取得手段と、
前記範囲ラベル取得手段で取得した前記文書ＩＤと前記範囲ラベルから、前記出現位置情報取得手段で取得した前記検索キーワードの出現位置情報が存在するノード情報を選択するノード情報選択手段と、を有する
ことを特徴とする全文検索装置。
【請求項７】
前記ノード管理手段の前記範囲ラベル付与手段は、
前記ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、記述内容を範囲ラベルとして前記範囲ラベル記憶手段に格納する手段を有し、
前記全文インデクス手段の前記転置表格納手段は、
前記ＸＭＬ文書を一定の長さの文字列に分割し、該文字列を形態素解析することにより単語及びタグを跨いだ単語を切り出す形態素解析手段と、
切り出した単語毎に、単語の最初の文字が出現したノードのpreorder値と、該単語の最後の文字が出現したノードのpostorder値を取得し、前記文書ＩＤ、該preorder値、該postorder値を前記出現位置情報として前記転置表記憶手段の転置表に格納する第1の範囲ラベル付与手段と、を含み、
前記検索手段の前記範囲ラベル取得手段は、
前記検索キーワードを形態素解析し、検索単語を取得し、該検索単語に基づいて前記転置表記憶手段の転置表から該検索単語の出現位置情報を取得する手段を含む
請求項６記載の全文検索装置。
【請求項８】
前記ノード管理手段の前記範囲ラベル付与手段は、
前記ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、全テキストノードを連結した際の開始文字オフセット、記述内容を範囲ラベルとして前記範囲ラベル記憶手段に格納する手段を有し、
前記全文インデクス手段の前記転置表格納手段は、
前記ＸＭＬ文書の全テキストノードを連結し、一定の長さの文字列に分割し、N-gram方式により単語を切り出し、切り出した単語がテキストノードを跨っている場合は、該テキストノードの終端までのＭ文字（但し、Ｍは1以上の整数）も重複して切り出す単語切り出し手段と、
切り出した単語毎に、開始位置が含まれるノード識別子preorder値と、終了位置が含まれるノード識別子postorder値と、連結したテキスト中の開始位置を取得し、該preorder値、該postorder値、該開始位置、前記文書ＩＤを前記出現位置情報として前記転置表記憶手段の転置表に格納する第２の範囲ラベル付与手段と、を含み、
前記検索手段の前記範囲ラベル取得手段は、
前記検索キーワードをN-gram分解し、検索単語を取得し、該検索単語に基づいて前記転置表記憶手段の転置表から該検索単語の出現位置情報を取得し、該検索単語の出現位置情報の開始位置を付き合わせ、前記検索キーワードの出現位置情報を取得する手段を含む
請求項６記載の全文検索装置。
【請求項９】
請求項６乃至８のいずれか１項に記載の全文検索装置を構成する各手段としてコンピュータを機能させるための全文検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全文検索方法及び装置及びプログラムに係り、特に、構造化データである多数のＸＭＬ及びＨＴＭＬ文書を蓄積・検索する分野で全文検索と呼ばれる、記述内容の部分一致を高速に行うためのＸＭＬデータのタグを跨いだ文字列に対する全文検索方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
蓄積された文書群から、検索キーワードが含まれている文書を高速に探し出す全文検索技術がある。これは平坦に記述されたテキスト（文字列）から、出現単語を切り出し、単語毎にどの文書に出現したかを索引（全文インデックス）しておくことで実現される。単語の切り出し方として、形態素解析を用いる方法や、N-gramと呼ばれる機械的に一定数の文字列を一文字ずつずらして重複しつつ取り出す方法が用いられる。
【０００３】
一方、ＸＭＬとはマークアップ言語の一つで、ＸＭＬで記述されたデータは構造化され、構造に意味を持ったデータである。図１２は、ＸＭＬ文書とその構造を示した図である。
ＸＭＬデータは木構造で表すことができ、各節を「ノード」と呼ぶ。特に、根のノードを「ルート要素」（"book"）、値（記述内容）を「テキストノード」("宇宙の不思議")、タグ中に記述されたものを「属性」（"no=１"）と呼ぶ。
【０００４】
ＸＭＬ文書（群）に対する全文検索では、文書全体を対象にすること以外にも、文書の特定の範囲を対象にすることもできる必要がある。すなわち、パスを指定することで大きな一つのＸＭＬ文書から、必要とする部分のみを検索対象にすることができる。この対象となる文書の一部を、ここでは「部分文書」と呼ぶ。図１３に部分文書の例を示す。同図（Ａ）が/book/chapterと指定された場合の部分文書で、同図（Ｂ）が/book/chapter/sectionと指定された場合の部分文書である。
【０００５】
このような部分文書に対する全文検索を高速に実現しようとした場合、部分文書の特定とその範囲の記述内容に検索キーワードが含まれているかどうか（さらには適合度の算出も）を効率的に行う必要がある（例えば、特許文献１参照）。
【特許文献１】特開２００８−１４６４２４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ＸＭＬ文書では「混合内容（Mixed Content）」と呼ばれるテキストとタグの混在を許す構造がある。その例を図１４に示す。例では、テキスト中に強調表示を行うために<b>タグが混在している。このように、意味的には連続した文字列であっても、タグにより分断され、別々のテキストノードになる場合がある。前述の特許文献１も含めた従来の手法では、テキストノード単位での処理となるため、例えば「水星」で全文検索した場合、全文インデクスには「水」「星」とバラバラに索引されており、検索できない。
【０００７】
これを解決するには、テキストノードを跨いだ単語に対しても索引する必要があるが、単純にテキストノードを連結してしまうと、構造が保持できなくなってしまう。最も単純な手法としては、全ての部分文書毎にテキストノードを連結した文字列を取り出し、それに対して全文インデックス群を構築する方法がある。しかしながら、この方法はテキストノードの重複によりインデクスサイズが巨大になりすぎ、現実的ではない。
【０００８】
本発明は、上記の点に鑑みなされたもので、巨大な全文インデクス群を構築することなく、混合内容を含むＸＭＬ文書に対する、任意の構造を指定した全文検索を実現することが可能な全文検索方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
図１は、本発明の原理を説明するための図である。
【００１０】
本発明（請求項１）は、構造化データであるテキストとタグが混在するＸＭＬ文書群に対して全文検索を行う全文検索方法であって、
ＸＭＬの各ノード間の構造上の関係を管理するノード管理手段と、該ＸＭＬの文書内の単語にインデクスを構築する全文インデクス手段と、検索を実行する検索手段と、を有する装置において、
ノード管理手段が、入力されたＸＭＬ文書群の個々の文書に対して文書ＩＤを付与し、該文書の全てのノードにタグを跨ぐことを許す範囲ラベルを付与し、範囲ラベル記憶手段に格納する範囲ラベル付与ステップ（ステップ１）と、
全文インデクス手段が、ＸＭＬ文書のテキストから単語及びタグを跨いだ単語を切り出して、該ＸＭＬ文書における該単語の出現位置と文書ＩＤの組からなる出現位置情報を転置表記憶手段の転置表に格納する転置表格納ステップ（ステップ２）と、
からなる格納過程と、
検索手段が、入力された検索クエリから、検索パスと検索キーワードを抽出し、範囲ラベル記憶手段から検索パスに該当する文書ＩＤ及び範囲ラベルを取得する範囲ラベル取得ステップ（ステップ３）と、
転置表記憶手段から、検索キーワードに合致する出現位置情報を取得する出現位置情報取得ステップ（ステップ４）と、
範囲ラベル取得ステップで取得した文書ＩＤと範囲ラベルから、出現位置情報取得ステップで取得した検索キーワードの出現位置情報が存在するノード情報を選択するノード情報選択ステップ（ステップ５）と、からなる検索過程と、を行う。
【００１１】
また、本発明（請求項２）は、格納過程の範囲ラベル付与ステップ（ステップ１）において、
ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、記述内容を範囲ラベルとして範囲ラベル記憶手段に格納し、
格納過程の転置表格納ステップ（ステップ２）において、
ＸＭＬ文書を一定の長さの文字列に分割し、該文字列を形態素解析することにより単語及びタグを跨いだ単語を切り出す形態素解析ステップと、
切り出した単語毎に、単語の最初の文字が出現したノードのpreorder値と、該単語の最後の文字が出現したノードのpostorder値を取得し、文書ＩＤ、該preorder値、該postorder値を出現位置情報として転置表記憶手段の転置表に格納する第1の範囲ラベル付与ステップと、を行う。
【００１２】
また、本発明（請求項３）は、検索過程の範囲ラベル取得ステップ（ステップ３）において、検索キーワードを形態素解析し、検索単語を取得し、検索単語に基づいて転置表記憶手段の転置表から該検索単語の出現位置情報を取得する。
【００１３】
また、本発明（請求項４）は、格納過程の範囲ラベル付与ステップ（ステップ１）において、
ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、全テキストノードを連結した際の開始文字オフセット、記述内容を範囲ラベルとして範囲ラベル記憶手段に格納し、
格納過程の転置表格納ステップ（ステップ２）において、
ＸＭＬ文書の全テキストノードを連結し、一定の長さの文字列に分割し、N-gram方式により単語を切り出し、切り出した単語がテキストノードを跨っている場合は、該テキストノードの終端までのＭ文字（但し、Ｍは1以上の整数）も重複して切り出す単語切り出しステップと、
切り出した単語毎に、開始位置が含まれるノード識別子preorder値と、終了位置が含まれるノード識別子postorder値と、連結したテキスト中の開始位置を取得し、該preorder値、該postorder値、該開始位置、文書ＩＤを出現位置情報として転置表記憶手段の転置表に格納する第２の範囲ラベル付与ステップと、を行う。
【００１４】
また、本発明（請求項５）は、検索過程の範囲ラベル取得ステップ（ステップ３）において、
検索キーワードをN-gram分解し、検索単語を取得し、
検索単語に基づいて転置表記憶手段の転置表から該検索単語の出現位置情報を取得し、
検索単語の出現位置情報の開始位置を付き合わせ、検索キーワードの出現位置情報を取得する。
【００１５】
図２は、本発明の原理構成図である。
【００１６】
本発明（請求項６）は、構造化データであるテキストとタグが混在するＸＭＬ文書群に対して全文検索を行う全文検索装置であって、
ＸＭＬの各ノード間の構造上の関係を管理するノード管理手段１２０と、該ＸＭＬの文書内の単語にインデクスを構築する全文インデクス手段１３０と、検索を実行する検索手段１４０と、を有し、
ノード管理手段１２０は、
入力されたＸＭＬ文書群の個々の文書に対して文書ＩＤを付与し、該文書の全てのノードにタグを跨ぐことを許す範囲ラベルを付与し、範囲ラベル記憶手段１２１に格納する範囲ラベル付与手段１２２を有し、
全文インデクス手段１３０は、
ＸＭＬ文書のテキストから単語及びタグを跨いだ単語を切り出して、該ＸＭＬ文書における該単語の出現位置と文書ＩＤの組からなる出現位置情報を転置表記憶手段１３１の転置表に格納する転置表格納手段１３２を有し、
検索手段１４０は、
入力された検索クエリから、検索パスと検索キーワードを抽出し、範囲ラベル記憶手段１２１から検索パスに該当する文書ＩＤ及び範囲ラベルを取得する範囲ラベル取得手段１４１と、
転置表記憶手段１３１から、検索キーワードに合致する出現位置情報を取得し、出現位置情報取得手段１４２と、
範囲ラベル取得手段１４１で取得した文書ＩＤと範囲ラベルから、出現位置情報取得手段１４２で取得した検索キーワードの出現位置情報が存在するノード情報を選択するノード情報選択手段１４３と、を有する。
【００１７】
また、本発明（請求項７）は、ノード管理手段１２０の範囲ラベル付与手段１２２において、
ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、記述内容を範囲ラベルとして範囲ラベル記憶手段に格納する手段を有し、
全文インデクス手段１３０の転置表格納手段１３２において、
ＸＭＬ文書を一定の長さの文字列に分割し、該文字列を形態素解析することにより単語及びタグを跨いだ単語を切り出す形態素解析手段と、
切り出した単語毎に、単語の最初の文字が出現したノードのpreorder値と、該単語の最後の文字が出現したノードのpostorder値を取得し、該preorder値、該postorder値、文書ＩＤを出現位置情報として転置表記憶手段１３１の転置表に格納する手段と、を含み、
検索手段１４０の範囲ラベル取得手段１４１において、
検索キーワードを形態素解析し、検索単語を取得し、該検索単語に基づいて転置表記憶手段の転置表から該検索単語の出現位置情報を取得する手段を含む。
【００１８】
また、本発明（請求項８）は、ノード管理手段１２０の範囲ラベル付与手段１２２において、
ＸＭＬ文書の文書ＩＤ、各ノードのpreorder値とpostorder値、タグ名、全テキストノードを連結した際の開始文字オフセット、記述内容を範囲ラベルとして範囲ラベル記憶手段に格納する手段を有し、
全文インデクス格納手段１３０の転置表格納手段１３２において、
ＸＭＬ文書の全テキストノードを連結し、一定の長さの文字列に分割し、N-gram方式により単語を切り出し、切り出した単語がテキストノードを跨っている場合は、該テキストノードの終端までのＭ文字（但し、Ｍは1以上の整数）も重複して切り出す単語切り出し手段と、
切り出した単語毎に、開始位置が含まれるノード識別子preorder値と、終了位置が含まれるノード識別子postorder値と、連結したテキスト中の開始位置を取得し、該preorder値、該postorder値、該開始位置、文書ＩＤを出現位置情報として転置表記憶手段１３１の転置表に格納する第２の範囲ラベル付与手段と、を含み、
検索手段１４０の範囲ラベル取得手段１４１において、
検索キーワードをN-gram分解し、検索単語を取得し、該検索単語に基づいて転置表記憶手段の転置表から該検索単語の出現位置情報を取得し、該検索単語の出現位置情報の開始位置を付き合わせ、検索キーワードの出現位置情報を取得する手段を含む。
【００１９】
本発明（請求項９）は、請求項６乃至８のいずれか１項に記載の全文検索装置を構成する各手段としてコンピュータを機能させるための全文検索プログラムである。
【発明の効果】
【００２０】
上記のように本発明によれば、テキストノードに付与される範囲値を拡張した転置表を作成することにより、タグを跨いだ（テキストノードを跨いだ）単語に対しても全文検索が可能であり、巨大な全文インデクス群を構築することなく、混合内容を含むＸＭＬ文書に対する任意の構造を指定した全文検索を実現することができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
図３は、本発明の一実施の形態における全文検索装置の構成図である。
【００２３】
同図に示す全文検索装置１００は、パスインデクス部１１０、ノード管理部１２０、全文インデクス部１３０、検索部１４０から構成される。
【００２４】
パスインデクス部１１０は、機能を実現するためには必須でないが、高速検索を実現するために通常用いられる。
【００２５】
ノード管理部１２０は、各ノードに出現した文書を識別し、各文書にＩＤを付与し、各ノード間の構造上の関係を管理する。本発明では、構造上の関係の管理に「範囲ラベル」を用いるものとし、各ノードに範囲ラベルを付与し、ノード表として範囲レベル記憶部１２１に格納する。範囲ラベルは、例えば、「S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, D. Drivastava, and Y. Wu: "Structural joins: A primitive for efficient XML query pattern matching," Proc. ICDE, p. 141, 2002」で示されるように、全てのノードにpreorder値とpostorder値の２値を付与し、子ノードのpreorder値とpostorder値は、親ノードのpreorder値とpostorder値に含まれるようにラベル付けされる。範囲ラベルの例を図４に示す。例えば、範囲ラベル（９，６０）の「desc」ノードは、範囲ラベル（６，６１）の「chapter」ノードの子供の関係にあり、範囲ラベルも（９，６０）は（６，６１）に含まれている。また、範囲ラベル（１２，１５）の「ｂ」ノードも（６，６１）に含まれており、直接親子だけでなく先祖子孫関係に対し、高速に判別することができる（この判別の組み合わせを選択することを「構造ジョイン」と呼ぶ）。図５に範囲レベル記憶部のノード表の格納例を示す。
【００２６】
全文インデクス部１３０は、ＸＭＬ文書の全テキストノードを連結したテキストから単語を切り出し、当該単語の出現位置を転置表記憶部１３１の転置表に記録する。単語の出現位置とは、単語の出現する文書の識別だけでなく、文書中の単語の出現する部分文書の構造上の位置、すなわち、上記説明した出現したノードの範囲ラベルも記録する。
【００２７】
検索部１４０は、検索クエリを受け取り、指定された検索パス及び検索キーワードにマッチするノードを、パスインデクス部１１０、ノード管理部１２０、全文インデクス部１３０から特定し、返却する。
【００２８】
以下に、ＸＭＬ文書の「格納フェイズ」、「検索フェイズ」からなるシステムの動作を説明する。
【００２９】
格納フェイズでは、与えられたＸＭＬ文書群から各種インデクスを作成する。
【００３０】
図６は、本発明の一実施の形態における格納フェイズの全体フローを示す。
【００３１】
以下では、ＸＭＬ文書群に対し、パスインデクス部１１０、ノード管理部１２０、全文インデクス部１３０のそれぞれが処理を行う。
【００３２】
ステップ１１０）  ノード管理部１２０は、ＸＭＬ文書をＸＭＬ文書記憶装置１０から取り出す。
【００３３】
ステップ１２０）  さらに、取り出した文書に文書ＩＤを付与してメモリ（図示せず）に格納する。
【００３４】
ステップ１３０）  詳細なノード管理部１２０の動作を図７に示す。
【００３５】
ノード管理部１２０は、メモリ（図示せず）からノードを取り出し（ステップ１３１）、パスを特定し、パスインデクス部１１０に伝える（ステップ１３２）。各ノードに範囲ラベルを付与し（ステップ１３３）、範囲ラベル記憶部１２１のノード表に、文書ＩＤ，範囲ラベル、開始文字オフセット等からなるノード情報を格納する（ステップ１３４）。上記の処理を取り出した全ノード分繰り返す（ステップ１３５）。
【００３６】
上記のように、ノード管理部１２０では、図４で示したＸＭＬ文書を、図５に示すように範囲レベル記憶部１２１のノード表に格納する。文書ＩＤ（docID）、範囲ラベル（pre,post）、タグ名（tag）、全テキストノードを連結した際の開始文字オフセット(offset)、記述内容(value)を格納する。但し、"offset"は形態素解析方式の場合は必須ではない。
【００３７】
ステップ１４０）  パスインデクス１１０は、パス毎にそのパスに対応するノード管理部１２０のノード情報（群）への関係を格納する。本発明では、具体的な手法は限定しないが、例えば、
（ａ）パスにＩＤを付与し、パスインデクス部１１０とノード管理部１２０で共通で保持する手法；
（ｂ）ノード管理部１２０で格納されているアドレス（ポインタ／オフセット）をパスインデクス部１１０で保持する方法；
などが考えられる。
【００３８】
ステップ１５０）  全文インデックス部１３０は、全てのテキストのノードを連結し、そのテキストから形態素解析方式、または、N-gram方式により単語を切り出し、出現位置を転置表を用いて転置表記憶部１３１に記録する。図８に全文インデクス部１３０の動作フローを示す。
【００３９】
ステップ１２０でメモリ（図示せず）に格納された全てのテキストノードを連結し（ステップ１５１）、形態素解析方式、またはN-gram方式を用いて単語を切り出す（ステップ１５２）。切り出された単語に基づいてノード管理部１２０に問い合わせ、当該単語の出現場所の位置情報を取得する（ステップ１５３）。当該単語が既出の単語でない場合は（ステップ１５４、Ｎｏ）、当該単語を転置表記憶部１３１の転置表に登録する（ステップ１５５）。転置表記憶部１３１の転置表に文書ＩＤ，範囲ラベル等の出現位置情報を追加格納する（ステップ１５６）。メモリ（図示せず）に格納された全ての単語分、ステップ１５３以降の処理を繰り返す（ステップ１５７）。
【００４０】
次に、検索フェイズについて説明する。
【００４１】
図９は、本発明の一実施の形態における検索フェイズのフローを示す。
【００４２】
ステップ２１０）  検索部１４０は、入力された検索クエリから、検索パスと検索キーワードを取り出す。
【００４３】
ステップ２２０）  パスインデクス部１１０から検索パスにマッチするノード情報（群）への関係を取得する。
【００４４】
ステップ２３０）  ノード管理部１２０から上記で該当するノード情報（群）の文書ＩＤ及び範囲ラベルを取得する。
【００４５】
ステップ２４０）  全文インデクス部１３０から、検索キーワードにマッチする出現位置情報（群）を取得する。
【００４６】
ステップ２５０）  ノード情報（群）の文書ＩＤと範囲ラベルと検索キーワードの出現位置情報（群）の文書ＩＤと範囲ラベルに対し、構造ジョインを行う（出現位置情報の存在するノード情報（群）を選択する）。
【００４７】
ステップ２６０）  必要ならば、ノード管理部１２０から、選択されたノード情報（群）に対応する部分文書を組み立て、返却する。
【００４８】
［第１の実施例］
＜格納フェイズ＞
本実施例では、格納フェイズにおいて、全文インデクス部１３０が単語の切り出しを行う際に、形態素解析方式を用いた例について説明する。
【００４９】
図８のステップ１５２において、全文インデクス部１３０は以下の処理を行う。
【００５０】
（１）テキストを一定の長さに分割（通常は文毎）し、順次以下の処理を行う。
【００５１】
ａ）形態素解析を行い、単語（群）を切り出す。単語毎に以下の処理を行う。
【００５２】
i.開始位置が含まれるノードのpreorder値を取得する。
【００５３】
ii.終了位置が含まれるノードのpostorder値を取得する。
【００５４】
ｂ）文書ＩＤ，preorder値、postorder値を転置表に記録する。
【００５５】
転置表の作成例を図１０に示す。転置表記億部１３１の転置表は、単語毎に出現位置（群）がまとめられた表である。同図の例において「水星」「金星」はタグを跨いでいるため、範囲ラベルもそれぞれ（１３，１７）（１９，２３）とタグを跨いだ格好になっている。
【００５６】
＜検索フェイズ＞
検索部１４０において、以下の手順で検索キーワードにマッチする出現位置情報（群）を取得する。
【００５７】
（１）検索キーワードを形態素解析し、検索単語を得る。
【００５８】
（２）検索単語に基づいて、全文インデクス部１３０の転置表記憶部１３１から当該検索単語の出現位置情報（群）を得る。
【００５９】
具体例として、図５のノード表及び図１１の転置表に対し、検索パス「/book/chapter」及び検索キーワード「水星・金星」が記された検索クエリの場合の処理を示す。
【００６０】
手順１：検索クエリから、検索パス「/book/chapter」、検索キーワード「水星・金星」を取り出す。
【００６１】
手順２：パスインデクス部１１０から、検索パス「/book/chapter」に対応するノード情報への関係を取得する。
【００６２】
手順３：ノード管理部１２０から該当するノード情報群として図６の２行目を含む複数行から、その文書ＩＤと範囲ラベルを取得する。
【００６３】
（001，6，61），…
手順４：全文インデクス部１３０から、検索キーワード「水星・金星」にマッチする出現位置情報（群）を以下の手順で取得する。
【００６４】
（ａ）「水星・金星」を形態素解析し、検索単語「水星」及び「金星」を得る。
【００６５】
（ｂ）図１０の転置表から、
「水星」の出現位置情報群："（001，13，17），…"
「金星」の出現位置情報群："（001，19，23），…"を得る。
【００６６】
手順５：手順３で得られた検索パス「/book/chapter」に対応する文書ＩＤ及び範囲ラベル群と、手順４で得られた検索キーワード「水星・金星」にマッチする出現位置情報群に対し、構造ジョインを行う。
【００６７】
この例では、少なくとも正しい組み合わせとして、
(001，6，61)と、（001，13，17）及び(001，19，23)
が選択される。
【００６８】
留意点として、この例のように検索単語が複数となった場合、全ての検索単語の出現位置情報と組み合わせとなるノード情報が正解となる。
【００６９】
手順６：検索結果として部分文書が必要とされる場合は、構造ジョインで選択されたノード情報から部分文書を組み立てる。
【００７０】
(001，6，61)の場合、ノード表（図５から文書ＩＤが001で、範囲ラベルが（6，61）に含まれる行（図５の２〜9行目及びそれ以降）を取り出し、部分文書を組み立てて返却結果とする。
【００７１】
同様に、検索パスを「/book/chapter/desc/b」とした場合、手順３で得られるノード情報は、
(001，12，15)，(001，18，21)，…
となり、手順４で得られた出現位置情報とどれも組み合わせとならない。このように検索キーワードに検索パスに一部かかっていたとしても、キーワード全てが含まれているような関係でないと結果に含まれないよう、正しく動作する。
【００７２】
［第２の実施例］
本実施例では、N-gram方式による単語の切り出しを行う場合を示す。なお、具体例としてはＮ＝２つまりBi-gramの場合について示す。
【００７３】
＜格納フェイズ＞
全文インデクス部１３０において、以下の処理を行う。
【００７４】
手順１：全テキストノードを連結する（ステップ１５２）。
【００７５】
手順２：一定の長さの文字列に分割（通常は文毎）し、順次以下の処理を行う。
【００７６】
（ａ）N-gram方式により、単語（群）を切り出す。但し、通常のN-gramの切り出しに加え、テキストノードの単位も考慮した切り出しを行う。つまり、
i.連結したテキストから機械的にＮ文字ずつ切り出す。
【００７７】
ii.切り出した単語がテキストノードを跨っていた場合、テキストノードの終端までのＭ文字も重複して切り出す。これは、Ｎ文字未満の検索単語に対しても、漏れなく対応するためである。
【００７８】
（ｂ）切り出した単語毎に、以下の処理を行う。
【００７９】
i.開始位置が含まれるノードのpreorder値を取得する。
【００８０】
ii.終了位置が含まれるノードのpostorder値を取得する。
【００８１】
iii.文書ＩＤ，preoder値、postorder値、開始位置を転置表に記録する。
【００８２】
転置表の作成例を図１１に示す。形態素解析方式の例と異なり、全テキストノードを連結した文字列での開始位置（position）も出現位置情報として格納されており「水星」「水」といったようにタグを跨いだ２文字の単語と、テキストノード終端までの一文字を重複して格納されている。
【００８３】
＜検索フェイズ＞
検索部１４０において、以下の手順で検索キーワードにマッチする出現位置情報（群）を取得する。
【００８４】
手順１：検索キーワードをN-gram分解し、検索単語（群）を得る。
【００８５】
手順２：転置表記億部131の転置表から検索単語毎に出現位置情報（群）を得る。
【００８６】
手順３：検索単語の出現開始位置を突き合わせ、検索キーワードの出現位置情報を得る。
【００８７】
具体例として、図５のノード管理部１２０の範囲ラベル記憶部１２１のノード表及び、図１１の転置表記憶部１３１の転置表に対して、検索パス「/book/chapter」及び検索キーワード「水星・金星」が記された検索クエリの場合の処理を示す。
【００８８】
手順１：（第1の実施例と同様）検索クエリから、検索パス「/book/chapter」、検索キーワード「水星・金星」を取り出す。
【００８９】
手順２：（第1の実施例と同様）パスインデクス部１１０から、検索パス「/book/chapter」に対応するノード情報への関係を取得する。
【００９０】
手順３：（第1の実施例と同様）ノード管理部１２０から該当するノード情報群として図５の２行目を含む複数行から、その文書ＩＤと範囲ラベルを取得する。
【００９１】
（001，6，61），…
手順４：全文インデクス部１３０から、検索キーワード「水星・金星」にマッチする出現位置情報（群）を以下の手順で取得する。
【００９２】
（ａ）「水星・金星」をBi-gram分解し、検索単語「水星」「・金」「金星」を得る。同時に、「水星」の開始位置をｋとした場合、「・金星」はｋ＋２、「金星」はｋ＋３の関係も得る。
【００９３】
（ｂ）図１１の転置表から、
「水星」の出現位置情報群："（001，13，17，9），…"
「・金」の出現位置情報群："（001，16，20，11），…"
「金星」の出現位置情報群："（001，19，23，12），…"を得る。
【００９４】
（ｃ）同じ文書ＩＤで開始位置（position）の関係を満たすものを、上記出現位置情報の組み合わせを見つける。この例では、各1列目が満たす。
【００９５】
（ｄ）上記の組み合わせから、検索キーワードの出現位置情報群を作成する。
【００９６】
（001，13，23），…
文書ＩＤは共通、preoder値は「水星」のもの、postorder値は「金星」のものを組み合わせ、検索キーワードの出現位置情報としている。
【００９７】
手順５：手順３で得られた検索パス「／book／chapter」に対応する文書ＩＤ及び範囲ラベル群と、手順４で得られた検索キーワード「水星・金星」にマッチする出現位置情報群に対し、構造ジョインを行う。
【００９８】
この例では、少なくとも正しい組み合わせとして、
(0061，6，61)と(001，13，23)
が選択される。
【００９９】
手順６：（第1の実施例と同様）検索結果として部分文書が必要とされる場合は、構造ジョインで選択されたノード情報から部分文書を組み立てる。
【０１００】
（001,6,61）の場合、ノード表（図５から文書ＩＤが001で、範囲ラベルが（6,61）に含まれる行（同図中の２〜９行目及びそれ以降）を取り出し、部分文書を組み立てて返却結果とする。
【０１０１】
同様に、検索パスを「/book/chapter/desc/b」とした場合、手順３で得られるノード情報は、
(001，12，15)，(001，18，21)，…
となり、手順４で得られた出現位置情報とどれも組み合わせとはならない。このように検索キーワードが検索パスに一部かかっていたとしても、キーワードがすべて含まれているような関係でないと結果に含まれないよう、正しく動作する。
【０１０２】
なお、上記の図３に記載された全文検索装置１００の構成要素の動作をプログラムとして構築し、全文検索装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【０１０３】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１０４】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１０５】
本発明は、構造化データ、特にＸＭＬの全文検索技術に適用可能である。
【図面の簡単な説明】
【０１０６】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における全文検索装置の構成図である。
【図４】本発明の一実施の形態における範囲ラベルの例である。
【図５】本発明の一実施の形態における範囲レベル記憶部のノード表の格納例である。
【図６】本発明の一実施の形態における格納フェイズの全体フローである。
【図７】本発明の一実施の形態におけるノード管理部のフロー（格納フェイズ）である。
【図８】本発明の一実施の形態における全文インデクス部の格納フェイズのフローである。
【図９】本発明の一実施の形態における検索フェイズのフローである。
【図１０】本発明の第１の実施例の転置表の作成例（形態素解析法式）である。
【図１１】本発明の第１の実施例の作成例（Bi-gram方式）である。
【図１２】ＸＭＬ文書とその構造を示す図である。
【図１３】パスが示す部分文書の例である。
【図１４】混合内容のＸＭＬ例である。
【符号の説明】
【０１０７】
１０  ＸＭＬ文書記憶装置
１００  全文検索装置
１１０  パスインデクス部１１０
１２０  ノード管理手段、ノード管理部
１２１  範囲ラベル記憶手段、範囲ラベル記憶部
１２２  範囲ラベル付与手段
１３０  全文インデクス手段、全文インデクス部
１３１  転置表記憶手段、転置表記億部
１３２  転置表格納手段
１４０  検索手段、検索部
１４１  範囲ラベル取得手段
１４２  出現位置情報取得手段
１４３  ノード情報選択手段
【図１】
2010108191.tif 000003
【図２】
2010108191.tif 000004
【図３】
2010108191.tif 000005
【図４】
2010108191.tif 000006
【図５】
2010108191.tif 000007
【図６】
2010108191.tif 000008
【図７】
2010108191.tif 000009
【図８】
2010108191.tif 000010
【図９】
2010108191.tif 000011
【図１０】
2010108191.tif 000012
【図１１】
2010108191.tif 000013
【図１２】
2010108191.tif 000014
【図１３】
2010108191.tif 000015
【図１４】
2010108191.tif 000016