(57)【要約】【課題】蓄積されたＸＭＬ文書に対して、パスと検索単語を入力して適合度の算出を行う場合に、処理を高速に行うこと。【解決手段】本発明は、ＸＭＬ文書を複数蓄積し、それらのＸＭＬ文書に対してパスと検索単語によってランキングを行う情報処理装置において、記憶部が、パス情報、ノード情報および単語情報を記憶している。また、パス情報は、パス単位の情報として、それぞれのパスの配下の部分文書の集合に関する統計情報であるパス統計情報を記憶している。  そして、処理部は、パスと検索単語が入力される前に、パス統計情報を含むパス情報を更新しておくので、適合度の算出時はパス統計情報を算出する必要がなく、検索を高速に処理することができる。【選択図】図１
2008146424.tif 000002
【特許請求の範囲】
【請求項１】
複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、前記ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、前記複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、
前記複数のＸＭＬ文書に関してパス単位の情報を前記パス情報に格納するパスインデックス部と、
それぞれの前記ＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報を前記ノード情報に格納するノード管理部と、
前記複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤ（IDentification）を含む出現位置情報と関連付けて前記単語情報に格納するテキストインデックス部と、
パスと検索単語が入力されたときに、前記複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、
を備える情報処理装置が、構造化データであるＸＭＬ文書を複数蓄積し、その複数のＸＭＬ文書に関して、前記入力されたパスの配下の部分文書における前記検索単語の適合度を算出する、ＸＭＬ文書の適合度の算出方法であって、
前記パス情報は、パス単位の情報として、それぞれのパスの配下の部分文書の集合に関する統計情報であるパス統計情報を記憶しており、
前記パスインデックス部は、前記パスと検索単語が入力される前に、蓄積された前記複数のＸＭＬ文書に関して、前記パス統計情報を含むパス情報を更新し、
前記ランキング部は、前記パスと検索単語が入力された後に、前記パス統計情報を含むパス情報、前記ノード情報、および、前記単語情報を参照し、当該パスと検索単語に基づいて、前記複数のＸＭＬ文書に関する適合度の算出を行う
ことを特徴とするＸＭＬ文書の適合度の算出方法。
【請求項２】
複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、前記ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、前記複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、
前記複数のＸＭＬ文書に関してパス単位の情報を前記パス情報に格納するパスインデックス部と、
それぞれの前記ＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報を前記ノード情報に格納するノード管理部と、
前記複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤ（IDentification）を含む出現位置情報と関連付けて前記単語情報に格納するテキストインデックス部と、
パスと検索単語が入力されたときに、前記複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、
を備える情報処理装置が、構造化データであるＸＭＬ文書を複数蓄積し、その複数のＸＭＬ文書に関して、前記入力されたパスの配下の部分文書における前記検索単語の適合度を算出する、ＸＭＬ文書の適合度の算出方法であって、
前記ノード情報は、各ノードごとの情報として、それぞれのノードの配下の部分文書に関する統計情報であるノード統計情報を記憶しており、
前記ノード管理部は、前記パスと検索単語が入力される前に、前記ノード統計情報を含む前記ノード情報を更新し、
前記ランキング部は、前記パスと検索単語が入力された後に、前記パス情報、前記ノード統計情報を含むノード情報、および、前記単語情報を参照し、当該パスと検索単語に基づいて、前記複数のＸＭＬ文書に関する適合度の算出を行う
ことを特徴とするＸＭＬ文書の適合度の算出方法。
【請求項３】
複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、前記ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、前記複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、
前記複数のＸＭＬ文書に関してパス単位の情報を前記パス情報に格納するパスインデックス部と、
それぞれの前記ＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報を前記ノード情報に格納するノード管理部と、
前記複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤ（IDentification）を含む出現位置情報と関連付けて前記単語情報に格納するテキストインデックス部と、
パスと検索単語が入力されたときに、前記複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、
を備える情報処理装置が、構造化データであるＸＭＬ文書を複数蓄積し、その複数のＸＭＬ文書に関して、前記入力されたパスの配下の部分文書における前記検索単語の適合度を算出する、ＸＭＬ文書の適合度の算出方法であって、
前記単語情報は、前記出現位置情報として、前記ＸＭＬ文書の文書ＩＤとともに、その単語が出現するノード位置情報を記憶しており、
前記テキストインデックス部は、前記パスと検索単語が入力される前に、前記ノード位置情報を含む前記単語情報を更新し、
前記ランキング部は、前記パスと検索単語が入力された後に、前記パス情報、前記ノード情報、および、前記ノード位置情報を含む単語情報を参照し、当該パスと検索単語に基づいて、前記複数のＸＭＬ文書に関する適合度の算出を行う
ことを特徴とするＸＭＬ文書の適合度の算出方法。
【請求項４】
前記ノード管理部は、ノード間の関係情報として、各ノードに、開始ラベル値と終了ラベル値を、親ノードの開始ラベル値は子ノードの開始ラベル値よりも小さく、親ノードの終了ラベル値は子ノードの終了ラベル値よりも大きい、という関係を満たすように付与して前記ノード情報に格納し、
前記テキストインデックス部は、各単語情報のノード位置情報として、前記ノード情報における開始ラベル値と終了ラベル値を付与し、
前記ランキング部は、前記パスと検索単語が入力されたときに、前記ノード情報における各ノードの開始ラベル値と終了ラベル値に基づいてそのパスに対応する部分文書の範囲を決定し、その部分文書に関して当該検索単語の適合度を算出する
ことを特徴とする請求項３に記載のＸＭＬ文書の適合度の算出方法。
【請求項５】
前記記憶部は、さらに、前記ＸＭＬ文書においてテキストデータを有するノードのテキストデータをそのテキストデータの識別情報と関連付けて格納するテキスト情報を記憶し、
前記ノード管理部は、前記ノード情報において、ノードごとに、その配下のテキストデータの識別情報を関連付け、
前記ランキング部は、前記パスと検索単語が入力されたときに、前記ノード情報におけるテキストデータの識別情報に基づいてそのパスに対応する部分文書の範囲を決定し、その部分文書に関して当該検索単語の適合度を算出する
ことを特徴とする請求項３に記載のＸＭＬ文書の適合度の算出方法。
【請求項６】
複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、前記ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、前記複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、
前記複数のＸＭＬ文書に関してパス単位の情報を前記パス情報に格納するパスインデックス部と、
それぞれの前記ＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報を前記ノード情報に格納するノード管理部と、
前記複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤ（IDentification）を含む出現位置情報と関連付けて前記単語情報に格納するテキストインデックス部と、
パスと検索単語が入力されたときに、前記複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、
を備え、構造化データであるＸＭＬ文書を複数蓄積し、その複数のＸＭＬ文書に関して、前記入力されたパスの配下の部分文書における前記検索単語の適合度を算出する情報処理装置であって、
前記パス情報は、パス単位の情報として、それぞれのパスの配下の部分文書の集合に関する統計情報であるパス統計情報を記憶しており、
前記パスインデックス部は、前記パスと検索単語が入力される前に、蓄積された前記複数のＸＭＬ文書に関して、前記パス統計情報を含むパス情報を更新し、
前記ランキング部は、前記パスと検索単語が入力された後に、前記パス統計情報を含むパス情報、前記ノード情報、および、前記単語情報を参照し、当該パスと検索単語に基づいて、前記複数のＸＭＬ文書に関する適合度の算出を行う
ことを特徴とする情報処理装置。
【請求項７】
複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、前記ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、前記複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、
前記複数のＸＭＬ文書に関してパス単位の情報を前記パス情報に格納するパスインデックス部と、
それぞれの前記ＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報を前記ノード情報に格納するノード管理部と、
前記複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤ（IDentification）を含む出現位置情報と関連付けて前記単語情報に格納するテキストインデックス部と、
パスと検索単語が入力されたときに、前記複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、
を備え、構造化データであるＸＭＬ文書を複数蓄積し、その複数のＸＭＬ文書に関して、前記入力されたパスの配下の部分文書における前記検索単語の適合度を算出する情報処理装置であって、
前記ノード情報は、各ノードごとの情報として、それぞれのノードの配下の部分文書に関する統計情報であるノード統計情報を記憶しており、
前記ノード管理部は、前記パスと検索単語が入力される前に、前記ノード統計情報を含む前記ノード情報を更新し、
前記ランキング部は、前記パスと検索単語が入力された後に、前記パス情報、前記ノード統計情報を含むノード情報、および、前記単語情報を参照し、当該パスと検索単語に基づいて、前記複数のＸＭＬ文書に関する適合度の算出を行う
ことを特徴とする情報処理装置。
【請求項８】
複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、前記ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、前記複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、
前記複数のＸＭＬ文書に関してパス単位の情報を前記パス情報に格納するパスインデックス部と、
それぞれの前記ＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報を前記ノード情報に格納するノード管理部と、
前記複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤ（IDentification）を含む出現位置情報と関連付けて前記単語情報に格納するテキストインデックス部と、
パスと検索単語が入力されたときに、前記複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、
を備え、構造化データであるＸＭＬ文書を複数蓄積し、その複数のＸＭＬ文書に関して、前記入力されたパスの配下の部分文書における前記検索単語の適合度を算出する情報処理装置であって、
前記単語情報は、前記出現位置情報として、前記ＸＭＬ文書の文書ＩＤとともに、その単語が出現するノード位置情報を記憶しており、
前記テキストインデックス部は、前記パスと検索単語が入力される前に、前記ノード位置情報を含む前記単語情報を更新し、
前記ランキング部は、前記パスと検索単語が入力された後に、前記パス情報、前記ノード情報、および、前記ノード位置情報を含む単語情報を参照し、当該パスと検索単語に基づいて、前記複数のＸＭＬ文書に関する適合度の算出を行う
ことを特徴とする情報処理装置。
【請求項９】
前記ノード管理部は、ノード間の関係情報として、各ノードに、開始ラベル値と終了ラベル値を、親ノードの開始ラベル値は子ノードの開始ラベル値よりも小さく、親ノードの終了ラベル値は子ノードの終了ラベル値よりも大きい、という関係を満たすように付与して前記ノード情報に格納し、
前記テキストインデックス部は、各単語情報のノード位置情報として、前記ノード情報における開始ラベル値と終了ラベル値を付与し、
前記ランキング部は、前記パスと検索単語が入力されたときに、前記ノード情報における各ノードの開始ラベル値と終了ラベル値に基づいてそのパスに対応する部分文書の範囲を決定し、その部分文書に関して当該検索単語の適合度を算出する
ことを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
請求項１から請求項５までのいずれか１項に記載のＸＭＬ文書の適合度の算出方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、蓄積した複数のＸＭＬ（eXtensible Markup Language）文書に関して、パスと検索単語を有する検索クエリ（問合せ）に対する適合度の算出を行う技術に関する。
【背景技術】
【０００２】
近年、コンピュータ装置で文書を作成する場合、マークアップ言語の１つであるＸＭＬを使用することが多い。ＸＭＬにより作成された文書であるＸＭＬ文書（以下、単に「文書」ともいう。）は、多く利点を有するからである。
たとえば、ＸＭＬ文書は、文書の構造を表現および管理するためのタグの内容を使用者が定義できるため使いやすく、また、階層構造となっているのでデータ整理に適している。さらに、ＸＭＬ文書は、データがバイナリデータでなくテキストデータであるので使用者がデータの内容を容易に確認でき、また、世界標準として認定されているので他の多くのアプリケーションと互換性がある。
【０００３】
そして、ＸＭＬ文書の増加にともなって、蓄積された複数のＸＭＬ文書に対する検索の精度や速度の向上の必要性も高くなってきている。なお、以下、検索クエリに対する文書の適合性によって行われる順位付けのことをランキングという。また、検索時は、文書中の検索単語の出現に関する何らかの統計量を利用してスコアを算出し、そのスコアの大小関係によってランキングが行われる。
【０００４】
蓄積された文書に対するランキングの手法としては、文書の記述内容を統計的に分析する手法が多く用いられている（たとえば非特許文献１参照）。
なお、スコアの算出に利用される統計量として、一般に、「文書集合全体の統計量（全文書の長さの平均（以下、「平均長さ」という。）など）」、「文書ごとの統計量（各文書の長さなど）」、「検索単語に対する統計量（各文書における検索単語の出現頻度など）」が用いられる。
【０００５】
また、ＸＭＬ文書に対して効率的な検索を実現しようとする場合、構造化データであるＸＭＬ文書からその検索に必要な記述内容を高速に取り出すことが可能でなければならない。そこで、一般的には、ＸＭＬ文書の構造と記述内容を記録したインデックス（構造インデックス）をあらかじめ構築しておく。そして、構造インデックスの構築には様々な方法が存在するが、多くの場合、ＸＭＬ文書の持つ全てのパス（データの所在を示す文字列。たとえば「/book/chapter/section」など）とそのパスに対応する記述内容を関連付けるパスインデックスが構築される（たとえば特許文献１参照）。
【０００６】
そして、ＸＭＬ文書はその構造に意味を持っているため、ＸＭＬ文書に対するランキングは、ＸＭＬ文書の構造を利用して行うことが望ましい。そうすることで、精度の高い検索結果が期待できるからである。つまり、ＸＭＬ文書のランキングでは、従来のランキング時に行っていたように文書単位でスコアを算出するのではなく、部分文書（ＸＭＬ文書の一部）単位でスコアを算出することが好ましい。
【０００７】
すなわち、ＸＭＬ文書のランキングに関するスコアの算出に利用される統計量として、「文書集合全体の統計量」ではなく「部分文書集合全体の統計量」、また、「文書ごとの統計量」ではなく「部分文書ごとの統計量」を使用することが望ましい。また、「検索単語に対する統計量」に関しても、たとえば、その出現位置を文書単位ではなくもっと詳細に識別するなどしたほうがよい。
【非特許文献１】岸田和明、外２名、「検索実験の方法と実際：ＮＴＣＩＲワークショップでの試み」、Pre-meeting Lecture at the NTCIR-3 Workshop、2002年10月8日、p.9-10
【特許文献１】特開２００６−２２８１５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、前記した「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」は、検索クエリの内容に依存して変化する。これは、検索クエリにおけるパスの内容によって、該当する部分文書の範囲が変わるためである。
したがって、前記した非特許文献１や特許文献１を含む従来技術では、検索（ランキング）の都度、それらの統計量を算出しなければならず、蓄積されたＸＭＬ文書が大量になると算出コストが膨大になり、その結果、処理が遅くなってしまうという問題があった（詳細は「発明を実施するための最良の形態」の冒頭に記載）。
【０００９】
そこで、本発明は、前記問題点に鑑みてなされたものであり、蓄積されたＸＭＬ文書に対して、パスと検索単語を指定して適合度の算出を行う場合に、処理を高速に行うことを目的とする。
【課題を解決するための手段】
【００１０】
前記課題を解決するために、請求項１および請求項６に係る発明は、情報処理装置が、複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、複数のＸＭＬ文書に関してパス単位の情報をパス情報に格納するパスインデックス部と、それぞれのＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報をノード情報に格納するノード管理部と、複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤを含む出現位置情報と関連付けて単語情報に格納するテキストインデックス部と、パスと検索単語が入力されたときに、複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、を備える。
そして、パス情報は、パス単位の情報として、それぞれのパスの配下の部分文書の集合に関する統計情報であるパス統計情報を記憶しており、パスインデックス部は、パスと検索単語が入力される前に、蓄積された複数のＸＭＬ文書に関して、パス統計情報を含むパス情報を更新し、ランキング部は、パスと検索単語が入力された後に、パス統計情報を含むパス情報、ノード情報、および、単語情報を参照し、当該パスと検索単語に基づいて、複数のＸＭＬ文書に関する適合度の算出を行う。
【００１１】
かかる発明によれば、部分文書集合全体の統計量であるパス統計情報を、パスと検索単語の入力前に算出および格納しておくことができ、そのパス統計情報を使うことでＸＭＬ文書に関する適合度の算出処理を高速に行うことができる。
【００１２】
請求項２および請求項７に係る発明は、情報処理装置が、複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、複数のＸＭＬ文書に関してパス単位の情報をパス情報に格納するパスインデックス部と、それぞれのＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報をノード情報に格納するノード管理部と、複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤを含む出現位置情報と関連付けて単語情報に格納するテキストインデックス部と、パスと検索単語が入力されたときに、複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、を備える。
そして、ノード情報は、各ノードごとの情報として、それぞれのノードの配下の部分文書に関する統計情報であるノード統計情報を記憶しており、ノード管理部は、パスと検索単語が入力される前に、ノード統計情報を含むノード情報を更新し、ランキング部は、パスと検索単語が入力された後に、パス情報、ノード統計情報を含むノード情報、および、単語情報を参照し、当該パスと検索単語に基づいて、複数のＸＭＬ文書に関する適合度の算出を行う。
【００１３】
かかる発明によれば、部分文書ごとの統計量であるノード統計情報を、パスと検索単語の入力前に算出および格納しておくことができ、そのノード統計情報を使うことでＸＭＬ文書に関する適合度の算出処理を高速に行うことができる。
【００１４】
請求項３および請求項８に係る発明は、情報処理装置が、複数のＸＭＬ文書に関するパス単位の情報を格納するパス情報、ＸＭＬ文書ごとの各ＸＭＬ文書におけるノード間の関係情報を格納するノード情報、および、複数のＸＭＬ文書で使用されている各単語の出現位置情報を格納する単語情報、を記憶する記憶部と、複数のＸＭＬ文書に関してパス単位の情報をパス情報に格納するパスインデックス部と、それぞれのＸＭＬ文書におけるノード間の親子関係を含む関係を分析しその関係情報をノード情報に格納するノード管理部と、複数のＸＭＬ文書のいずれかで使用されている単語を、その単語が使用されているＸＭＬ文書の文書ＩＤを含む出現位置情報と関連付けて単語情報に格納するテキストインデックス部と、パスと検索単語が入力されたときに、複数のＸＭＬ文書に関して、その入力されたパスの配下の文書である部分文書における当該検索単語の適合度を算出するランキング部と、を備える。
そして、単語情報は、出現位置情報として、ＸＭＬ文書の文書ＩＤとともに、その単語が出現するノード位置情報を記憶しており、テキストインデックス部は、パスと検索単語が入力される前に、ノード位置情報を含む単語情報を更新し、ランキング部は、パスと検索単語が入力された後に、パス情報、ノード情報、および、ノード位置情報を含む単語情報を参照し、当該パスと検索単語に基づいて、複数のＸＭＬ文書に関する適合度の算出を行う。
【００１５】
かかる発明によれば、検索単語に対する統計量である出現位置情報を、パスと検索単語の入力前に算出および格納しておくことができ、その出現位置情報を使うことでＸＭＬ文書に関する適合度の算出処理を高速に行うことができる。
【００１６】
請求項４および請求項９に係る発明は、情報処理装置において、ノード管理部が、ノード間の関係情報として、各ノードに、開始ラベル値と終了ラベル値を、親ノードの開始ラベル値は子ノードの開始ラベル値よりも小さく、親ノードの終了ラベル値は子ノードの終了ラベル値よりも大きい、という関係を満たすように付与してノード情報に格納し、テキストインデックス部が、各単語情報のノード位置情報として、ノード情報における開始ラベル値と終了ラベル値を付与し、ランキング部は、パスと検索単語が入力されたときに、ノード情報における各ノードの開始ラベル値と終了ラベル値に基づいてそのパスに対応する部分文書の範囲を決定し、その部分文書に関して当該検索単語の適合度を算出する。
【００１７】
かかる発明によれば、ノード情報および単語情報における開始ラベル値と終了ラベル値によって部分文書の範囲を決定することができる。
【００１８】
請求項５に係る発明は、情報処理装置において、記憶部が、さらに、ＸＭＬ文書においてテキストデータを有するノードのテキストデータをそのテキストデータの識別情報と関連付けて格納するテキスト情報を記憶し、ノード管理部は、ノード情報において、ノードごとに、その配下のテキストデータの識別情報を関連付け、ランキング部は、パスと検索単語が入力されたときに、ノード情報におけるテキストデータの識別情報に基づいてそのパスに対応する部分文書の範囲を決定し、その部分文書に関して当該検索単語の適合度を算出する。
【００１９】
かかる発明によれば、テキストデータの識別情報によって部分文書の範囲を決定することができる。
【００２０】
請求項１０に係る発明は、請求項１から請求項５までのいずれか１項に記載のＸＭＬ文書の適合度の算出方法をコンピュータに実行させることを特徴とするプログラムである。
【００２１】
かかる発明によれば、ＸＭＬ文書の適合度の算出方法をコンピュータに実行させることができる。
【発明の効果】
【００２２】
本発明によれば、蓄積されたＸＭＬ文書に対して、パスと検索単語を指定して適合度の算出を行う場合に、処理を高速に行うことができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明に係る情報処理装置、ＸＭＬ文書の適合度の算出方法およびそのプログラムを実施するための最良の形態（以下、実施形態という。）について、適宜図面を参照しながら説明する。なお、参照図以外の図も適宜参照する。
その前に、理解を容易にするため、図２１〜図２４を参照しながら、比較例（従来技術）および用語について説明する。
【００２４】
図２１は、比較例の統計情報を用いたランキング例を示したものであり、（ａ）が文書例、（ｂ）が適合度（ランキング）の計算例１、（ｃ）が適合度の計算例２の説明図である。
図２１（ａ）に示すように、ここでは、３つの文書（文書０１〜０３）に対して、単語「特許」で検索を行う場合について説明する。なお、ここでの文書は、ＸＭＬ文書であってもなくても、いずれでもよい。また、３つの文書における検索単語の出現回数と文書のテキスト長は、図示した通りである。
【００２５】
図２１（ｂ）は、検索単語の出現回数でランキングを行った結果を示している。また、図２１（ｃ）は、検索単語の出現頻度（出現回数／テキスト長）でランキングを行った結果を示している。
そして、比較例では、一般に、前記したような統計量（検索単語の出現回数や出現頻度）と単語の出現位置（出現文書の識別子）を記録したインデックス（テキストインデックス）を構築しておく。そして、検索時には、構築してあるテキストインデックスを用いることで、検索単語の出現位置を特定し、高速なスコア算出を行うことができる。
なお、検索文字列に複数の単語が含まれている場合は、各単語に関してスコア算出を行い、所定の計算式によりそれらのスコアを統合するなどすればよい。
【００２６】
次に、図２２を参照しながら、構造化データであるＸＭＬ文書の構造について説明する。図２２において、（ａ）はＸＭＬ文書のソースコードの例の簡略図、（ｂ）はＸＭＬ文書の構造（木構造）を示した図である。
図２２（ａ）に例示しているように、ＸＭＬ文書００１のソースコードにおいて、ＸＭＬ文書の構成要素を識別するために使われるマーク（「＜book＞」など）をタグという。
【００２７】
また、ＸＭＬ文書は、図２２（ｂ）に示すように、ディレクトリ構造のような木構造を有しており、各要素（ノード）はパス（「/book/chapter」など。以下、同様に記載）で表現される。なお、各ノードには、ノード「ｎ１」の子ノードには「ｎ１１」〜「ｎ１３」、ノード「ｎ１２」の子ノードには「ｎ１２１」〜「ｎ１２４」、・・・、と、階層的に符号を付してある（他図も同様）。
【００２８】
このように、ＸＭＬ文書は、記述内容とは別に、タグによってそれぞれの記述内容の意味（属性）を付与されているため、単語とともにパスを指定して検索することで、大きな１つのＸＭＬ文書から必要とする部分を取り出すことができる。そして、前記したように、１つのＸＭＬ文書から取り出される文書の一部を部分文書という。
図２２の例では、ＸＭＬ文書００１は本のデータを表しており、この本のタイトルの記述内容だけを取り出したい場合、パスを「/book/title」と指定することで、タイトルの記述内容だけを取り出すことができる。
【００２９】
また、図２２（ｂ）に示すように、ＸＭＬ文書００１は、「/book」の配下に本の記述内容が章（chapter）別に格納されている。ＸＭＬ文書００１の中から特に単語「地球」について詳しく書かれている部分文書を取り出したい場合に、たとえば、章ごとに調査したいときは、「/book/chapter」の配下の「text」に対して単語「地球」で検索を行えばよい。また、章よりもさらに詳しい節（section）ごとに調査したいときは、「/book/chapter/section」の配下の「text」に対して単語「地球」で検索を行えばよい。いずれの場合も、スコアの高い部分文書がランキング上位の部分文書になる。
【００３０】
続いて、図２３を参照しながら、パス指定（パスの内容）の違いによる部分文書の違いについて説明する。図２３の（ａ）と（ｂ）は、図２２（ｂ）の構造の例について、それぞれのパスによる部分文書の範囲を示した図である。
図２３（ａ）に示すように、パスを「/book/chapter」と指定すれば、それぞれの「chapter」（ｎ１２，ｎ１３など）以下のノードが部分文書となる。一方、図２３（ｂ）に示すように、パスを「/book/chapter/section」と指定すれば、それぞれの「section」（ｎ１２４など）以下のノードが部分文書となる。このように、パスの内容によって、部分文書の範囲は異なるのである。
【００３１】
次に、図２４を参照しながら、パス指定の違いによる部分文書の違いの別の例について説明する。図２４の（ａ）と（ｂ）は、図２２（ｂ）の例について、それぞれのパスによる部分文書の範囲を示した図である。
図２４（ａ）に示すように、パスを「/book/title」と指定すれば、破線で図示した１箇所だけが該当する部分文書となる。一方、図２４（ｂ）に示すように、パスを「任意のtitle」と指定すれば、破線で図示した３箇所（以上）が該当する部分文書となる。
【００３２】
このように、検索クエリにおけるパスの内容によって、該当する部分文書が変化するので、パスの内容が変化するたびに、「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」も変化することになる。そのため、比較例においては、検索の都度、それらの統計量を算出しなくてはならなかった。そして、特に、蓄積されたＸＭＬ文書の数が増加すればするほど、それらの統計量の算出コストが大きくなってしまっていた。
【００３３】
続いて、図１〜図２０を参照しながら、本発明の各実施形態の情報処理装置、ＸＭＬ文書の適合度の算出方法およびそのプログラムについて説明する。
まず、本実施形態のランキング手法で用いるスコア計算式であるＢＭ２５（非特許文献１の「3.3.1  Okapi」参照）について説明する。このＢＭ２５を用いた場合、文書ｋにおける単語ｉのスコアＳｑｋｉの計算式は、次の式（１）により与えられる。
【００３４】
【数１】
2008146424.tif 000003
ここで、各記号の意味は次の通りである。
Ｌ：（部分）文書集合全体の平均長さ（部分文書集合全体の統計量。パス統計情報）
Ｎ：（部分）文書の総数（部分文書集合全体の統計量。パス統計情報）
ｌｋ：（部分）文書ｋの長さ（部分文書の統計量。ノード統計情報）
ｔｆｋｉ：（部分）文書ｋ中の単語ｉの出現回数（単語の統計量）
ｎｉ：該当する単語ｉを含む（部分）文書数（単語の統計量）
ｌｑ：検索文字列ｑの長さ
ｔｆｑｉ：検索文字列ｑ中の検索単語ｉの出現回数
【００３５】
（第１実施形態）
図１は、本発明の第１実施形態における情報処理装置の構成図である。図１に示すように、第１実施形態の情報処理装置１は、コンピュータ装置であり、入力部２、出力部３、メモリ４、記憶部５および処理部６を備えている。
【００３６】
入力部２は、データ入力を行うものであり、たとえば、キーボード、マウス、通信インターフェースなどである。情報処理装置１の使用者（以下、単に「使用者」という。）は、入力部２を使って、ＸＭＬ文書や検索クエリ（パスと検索文字列）を入力することができる。なお、本実施形態では、使用者がＸＭＬ文書の構造や記述内容をある程度把握しており、検索クエリとして、文字列だけではなく、パスも指定するものとする。
【００３７】
出力部３は、データを出力するものであり、たとえば、ディスプレイやスピーカである。出力部３は、ＸＭＬ文書の検索によるランキング結果などを出力する。
メモリ４は、処理部６の作業領域であり、たとえば、ＲＡＭ（Random Access Memory）である。
【００３８】
記憶部５は、データを記憶するものであり、たとえば、ハードディスクである。記憶部５は、たとえば、１件のデータを複数の項目(フィールド)の集合として表現して、データの集合を表（テーブル）で表す、いわゆるリレーショナルデータベースである。記憶部５は、入力部２から入力されたＸＭＬ文書を格納するＸＭＬ文書群５１、パステーブルＰＴ（Path Table。パス情報。詳細は図４（ｂ）で後記）、ノードテーブルＮＴ（Node Table。ノード情報。詳細は図４（ａ）で後記）および転置表ＩＴ（Inverted Table。単語情報。詳細は図５で後記）を記憶している。
また、記憶部５は、図示を省略しているが、後記するＸＭＬ文書の適合度の算出方法を記述したプログラムを記憶している。
【００３９】
処理部６は、各種演算処理を行うものであり、たとえば、ＣＰＵ（Central Processing Unit）である。処理部６は、その機能として、データ格納部６１、パスインデックス部６２、範囲ラベル部６３（ノード管理部）、テキストインデックス部６４およびランキング部６５を備えている。なお、以下において、処理部６がこれらの機能以外の機能を果たす場合は、動作主体を処理部６として記載する。
【００４０】
データ格納部６１は、入力部２から入力されたＸＭＬ文書をＸＭＬ文書群５１に格納する。
パスインデックス部６２は、入力部２から入力されたＸＭＬ文書の情報に基づき、パステーブルＰＴ（図４（ｂ）参照）において、各パスの統計量（部分文書集合全体の平均長さ（Ｌ）、部分文書数（Ｎ））を更新する。
【００４１】
範囲ラベル部６３は、各ノードに範囲ラベル（開始ラベル（値）「pre」と終了ラベル（値）「post」の２値のＩＤ（IDentification）。関係情報。出現位置情報。ノード位置情報）を付与し、ノードテーブルＮＴ（図４（ａ）参照）に記録する。各ノードに対して、子ノードの範囲ラベルが親ノードの範囲ラベルの「pre」と「post」の間の値になるようにラベル付けすることで、各ノード間の上下（親子）関係がわかる（特許文献１参照）。
【００４２】
ここで、図２および図３を参照しながら、範囲ラベルについて説明する。図２は、ＸＭＬ文書のソースコードの例を示した図であり、（ａ）が図２２と同様のＸＭＬ文書００１に関する図であり、（ｂ）がその他の例としてのＸＭＬ文書００２に関する図である。図２の（ａ）と（ｂ）に示すように、いずれのＸＭＬ文書も本（book）に関するデータである。
【００４３】
図３は、（ａ）がＸＭＬ文書００１に対して範囲ラベルを付与した状態を示す図であり、（ｂ）がＸＭＬ文書００２に対して範囲ラベルを付与した状態を示す図である。
図３（ａ）に示すように、ＸＭＬ文書００１において、ノードｎ１（book）は範囲ラベルが（１，９９）（開始ラベル「pre」が「１」で、終了ラベル「post」が「９９」。以下同様）で、範囲ラベルが（２，５）のノードｎ１１の親であることがわかる。また、ノードｎ１１は範囲ラベルが（２，５）で、範囲ラベルが（６，４７）のノードｎ１２とは上下（親子）関係にないことがわかる。図３（ｂ）に示したＸＭＬ文書００２についても、同様に、各ノードに対して範囲ラベルが付与されている。
【００４４】
図１に戻って、テキストインデックス部６４は、入力部２から入力されたＸＭＬ文書に出現する全ての単語の出現位置（文書ＩＤと範囲ラベル）を、転置表ＩＴに記録する。
ランキング部６５は、検索時に、パステーブルＰＴ、ノードテーブルＮＴおよび転置表ＩＴから統計情報などを取り出し、各部分文書ごとのスコアを算出する。
【００４５】
次に、図４を参照しながら、ノードテーブルとパステーブルについて説明する。図４は、（ａ）がノードテーブル、（ｂ）がパステーブルを例示した図である。
図４（ａ）において、（ａ１）はＸＭＬ文書００１に関するノードテーブル００１ＮＴであり、（ａ２）はＸＭＬ文書００２に関するノードテーブル００２ＮＴである。いずれのノードテーブルＮＴも、左から順に、ＸＭＬ文書の識別子を表す文書ＩＤ（docid）、範囲ラベル（「pre」と「post」）、各ノードに与えられているタグ（tag）、パスの識別子を表すパスＩＤ（pathid）、そのノードがパス指定されたときの部分文書の長さを表すｌｋ（ｌｋ）、および、そのノードのテキストデータであるテキスト（text）のカラムから構成されている。
【００４６】
図４（ｂ）に示すように、パステーブルＰＴは、左から順に、パスＩＤ（pathid）、パス（pathexp）、Ｌ（部分文書集合全体の平均長さ）、Ｎ（部分文書の総数）のカラムから構成されている。
【００４７】
続いて、図５を参照しながら、転置表について説明する。図５は、転置表の例を示した図である。
図５に示すように、転置表ＩＴは、単語（term）と出現位置（position）のカラムから構成されている。出現位置の()内は、左から順に、文書ＩＤ（docid）、開始ラベル（pre）、終了ラベル（post）を意味している。たとえば、転置表ＩＴにおいて、単語「宇宙」に対応する出現位置が（００１，３，４）であれば、文書ＩＤ（docid）が「００１」であるＸＭＬ文書００１における開始ラベル（pre）が「３」で終了ラベル（post）が「４」のノード、つまり、図３（ａ）におけるノードｎ１１１に単語「宇宙」が存在していることがわかる。
【００４８】
次に、図６を参照しながら、構造インデックス（パステーブルＰＴおよびノードテーブルＮＴ）の構築処理について説明する。図６は、構造インデックスの構築処理を示すフローチャートである。
まず、使用者が、入力部２を介して、新たに蓄積したいＸＭＬ文書を情報処理装置１に投入する。そうすると、処理部６のデータ格納部６１が記憶部５のＸＭＬ文書群５１にそのＸＭＬ文書を格納し、また、そのとき、パスインデックス部６２と範囲ラベル部６３が以下の処理により、構造インデックスを構築する。
【００４９】
投入されたＸＭＬ文書に関して、パスインデックス部６２は、１つのパスを取り出す（ステップＳ６０１）。パスインデックス部６２は、パステーブルＰＴを参照し、そのパスがすでにパステーブルＰＴに含まれている（存在している）か否かを判断する（ステップＳ６０２）。
【００５０】
パスがパステーブルＰＴに含まれていない場合（ステップＳ６０２でＮｏ）、パスインデックス部６２は、新しいパスＩＤを発行し、新たにそのパスをパステーブルＰＴに加え（ステップＳ６０３）、さらに、そのパスに関するＬとＮの値（部分文書集合の統計量）を計算する、すなわち、そのパスの配下の連結テキスト長をＬの値とし、Ｎの値を「１」として、それぞれ、パステーブルＰＴの該当箇所に格納する（ステップＳ６０４）。
【００５１】
パスがすでにパステーブルＰＴに含まれている場合（ステップＳ６０２でＹｅｓ）、パスインデックス部６２は、そのパスに関するＬとＮの値（部分文書集合の統計量）を計算する、すなわち、そのパスの配下の連結テキスト長の平均をＬの値とし、Ｎの値をインクリメント（１つ増加）して、それぞれ、パステーブルＰＴの該当箇所に格納する（ステップＳ６０４）。
【００５２】
その後、パスインデックス部６２は、そのＸＭＬ文書に関する全てのパス分の処理を終了したか否かを判断し（ステップＳ６０５）、終了していなければ（Ｎｏ）ステップＳ６０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ６０６に進む。
【００５３】
このようにして、ステップＳ６０１〜Ｓ６０５の処理により、検索に必要な３つの統計量（「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」）のうち、「部分文書集合全体の統計量」（パステーブルＰＴの「Ｌ」と「Ｎ」）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができる。そして、これにより、検索（適合度の算出）時に「部分文書集合全体の統計量」を算出する必要がなくなり、検索処理を高速化することができるようになる。
【００５４】
続いて、投入されたＸＭＬ文書に関し、範囲ラベル部６３は、１つのノードを取り出す（ステップＳ６０６）。
その後、範囲ラベル部６３は、パステーブルＰＴを参照し、そのノードに対応するパスＩＤを取り出し（ステップＳ６０７）、前記した規則性にしたがって範囲ラベルを付与し（ステップＳ６０８）、ノードテーブルＮＴに各値（カラムの情報）を格納する（ステップＳ６０９）。
【００５５】
つまり、ステップＳ６０９において、範囲ラベル部６３は、文書ＩＤ（docid）、範囲ラベル（「pre」と「post」）、タグ（tag）およびパスＩＤ（pathid）だけでなく、そのノード配下の部分文書の長さを表すｌｋと、そのノードのテキストデータであるテキスト（text）に関する情報もノードテーブルＮＴに格納する。
【００５６】
その後、範囲ラベル部６３は、そのＸＭＬ文書に関する全てのノード分の処理を終了したか否かを判断し（ステップＳ６１０）、終了していなければ（Ｎｏ）ステップＳ６０６に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ６１１に進む。
【００５７】
このようにして、ステップＳ６０６〜Ｓ６１０の処理により、検索に必要な３つの統計量（「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」）のうち、「部分文書ごとの統計量」（ノードテーブルＮＴの「ｌｋ」）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができる。そして、これにより、検索（適合度の算出）時に「部分文書ごとの統計量」を算出する必要がなくなり、検索処理を高速化することができる。
【００５８】
処理部６は、投入した全てのＸＭＬ文書分の処理を終了したか否かを判断し（ステップＳ６１１）、終了していなければ（Ｎｏ）ステップＳ６０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
このようにして、図６のフローチャートの処理によれば、投入した全てのＸＭＬ文書に関して、その投入直後に、「部分文書集合全体の統計量」および「部分文書ごとの統計量」を算出および格納することができる。
【００５９】
なお、図６のフローチャートでは、説明を簡単にするため、パスインデックス部６２による処理と範囲ラベル部６３による処理を分離したが、それらの処理を並列的に行うようにしてもよい。
【００６０】
続いて、図７を参照しながら、テキストインデックス（転置表ＩＴ）の構築処理について説明する。図７は、テキストインデックスの構築処理を示すフローチャートである。
図６に示したフローチャートの処理によって、投入されたＸＭＬ文書に関して、パステーブルＰＴとノードテーブルＮＴが更新された後、処理部６のテキストインデックス部６４は、ノードテーブルＮＴから１レコード（１ノード分のデータ）を取り出す（ステップＳ７０１）。
【００６１】
続いて、テキストインデックス部６４は、取り出したレコードにおける記述内容（図４（ａ）のノードテーブルＮＴの「text」のカラムのデータ）に関して、形態素解析（計算機を用いた自然言語処理の基礎技術の１つ）の手法を用いて単語に分ける（ステップＳ７０２）。
【００６２】
その後、テキストインデックス部６４は、分けられたうちの１つの単語が転置表ＩＴに含まれているか否かを判断する（ステップＳ７０３）。
その単語が転置表ＩＴに含まれていなかった場合（ステップＳ７０３でＮｏ）、テキストインデックス部６４は、その単語を新たに転置表ＩＴに登録し（ステップＳ７０４）、ステップＳ７０５に進む。その単語が転置表ＩＴに含まれていた場合（ステップＳ７０３でＹｅｓ）、テキストインデックス部６４は、そのままステップＳ７０５に進む。
【００６３】
ステップＳ７０５において、テキストインデックス部６４は、その単語の出現位置である文書ＩＤ（docid）と範囲ラベル（「pre」と「post」）を転置表ＩＴに格納する。たとえば、単語「宇宙」がＸＭＬ文書００１のノードｎ１１１に存在していれば（図３（ａ）参照）、ＸＭＬ文書００１の文書ＩＤ「００１」、ノードｎ１１１の開始ラベル（pre）「３」および終了ラベル（post）「４」を表す（００１，３，４）を、転置表ＩＴの「宇宙」に対応する「position」のカラムに格納する。
【００６４】
その後、テキストインデックス部６４は、そのレコードに関する全ての単語分の処理を終了したか否かを判断し（ステップＳ７０６）、終了していなければ（Ｎｏ）ステップＳ７０３に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ７０７に進む。
また、テキストインデックス部６４は、そのＸＭＬ文書に関する全てのレコード分の処理を終了したか否かを判断し（ステップＳ７０７）、終了していなければ（Ｎｏ）ステップＳ７０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
【００６５】
このようにして、図７に示したフローチャートの処理により、検索に必要な３つの統計量（「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」）のうち、「検索単語に対する統計量」（転置表ＩＴの「position」）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができる。そして、これにより、検索（適合度の算出）時に「検索単語に対する統計量」を算出する必要がなくなり、検索処理を高速化することができる。
【００６６】
次に、図８を参照しながら、ランキング処理について説明する。図８は、ランキング処理を示すフローチャートである。
記憶部５のＸＭＬ文書群５１に蓄積された複数のＸＭＬ文書に関して、検索によるランキングを行う場合、まず、使用者が入力部２を用いて検索クエリ（パスと検索文字列）を入力する。
【００６７】
そうすると、処理部６のランキング部６５は、検索クエリからパス、検索単語（検索文字列から抽出）、ｌｑ（検索文字列ｑの長さ）、および、ｔｆｑｉ（検索文字列ｑ中の検索単語ｉの出現回数）を取り出す（算出する）（ステップＳ８０１）。
続いて、ランキング部６５は、パステーブルＰＴを参照し、検索クエリ中のパスに対応するレコードにおける「Ｌ」、「Ｎ」およびパスＩＤ（pathid）の値を取り出す（ステップＳ８０２）。
【００６８】
ランキング部６５は、ノードテーブルＮＴを参照し、ステップＳ８０２で取り出したパスＩＤ（pathid）に対応するレコードにおける部分文書の位置（文書ＩＤ（docid）と範囲ラベル（「pre」と「post」））および「ｌｋ」の値を取り出す（ステップＳ８０３）。なお、取り出した部分文書の集まりを部分文書群と呼ぶ。
【００６９】
ランキング部６５は、転置表ＩＴから、検索単語の出現位置（文書ＩＤ（docid）、範囲ラベル（「pre」と「post」））の値を取り出す（ステップＳ８０４）。なお、ここで取り出された出現位置のノードの集まりを単語出現文書群と呼ぶ。
【００７０】
続いて、ランキング部６５は、転置表ＩＴから取り出した出現位置の値を用いて検索単語の出現する部分文書を絞り、ｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）とｎｉ（該当する単語ｉを含む部分文書数）を算出する（ステップＳ８０５）。すなわち、ランキング部６５は、部分文書群と単語出現文書群の位置情報を用いて、部分文書群から検索単語の含まれる部分文書を選別し、各部分文書における単語の統計量であるｔｆｋｉとｎｉを算出する。ここで、ステップＳ８０５の具体例について、図９を参照しながら説明する。
【００７１】
図９は、ステップＳ８０５の具体例、すなわち、部分文書の選別と単語の統計量の算出の例を示した図である。なお、この図９における例は、図２〜図５の具体例とは関係ない独立した例である。
図９（ａ）に示した部分文書群と図９（ｂ）に示した単語出現文書群に基づき、たとえば、まず、部分文書群のおける部分文書（００１，１０，２０）（図示した４つのうち最上位の部分文書）に含まれる単語出現文書が単語出現文書群にあるか探す。つまり、単語出現文書群において、文書ＩＤが「００１」で、範囲ラベルが「１０」〜「２０」の間に含まれている単語出現文書を探せばよい。ここでは、単語出現文書として、（００１，１２，１３）と（００１，１５，１６）が該当する。
【００７２】
以下、同様にして、図９（ｃ）に示すように、部分文書が３つに絞られ（文書ＩＤが「００３」の文書は検索単語を１つも含まないため、はずれている）、統計量のｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）は上から「２」、「１」および「１」であり、そして、ｎｉ（該当する単語ｉを含む部分文書数）は「３」であると算出することができる。
【００７３】
図８に戻って、ランキング部６５は、各統計量と前記した式（１）を用いて、該当する部分文書のスコアを算出する（ステップＳ８０６）。
そして、ランキング部６５は、ステップＳ８０６で算出したスコアの高い順に部分文書をソートすることで、ランキングを行う（ステップＳ８０７）。
【００７４】
このように、情報処理装置１は、予め算出および格納してある３つの統計量（「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」）を用いて検索（適合度の算出、ランキング）を行うことにより、検索を高速に処理することができる。
【００７５】
（検索例）
次に、図２〜図５の具体例に対して、図８のフローチャートによる検索（ランキング）を行った場合の例について説明する。ここでは、検索クエリのうち、パスが「/book/chapter/text/text()」であり、検索文字列が「地球」であるものとする。
まず、ｌｑ（検索文字列ｑの長さ）は「２」であり、ｔｆｑｉ（検索文字列ｑ中の単語ｉ（地球）の出現回数）は「１」であると算出できる（図８のステップＳ８０１。以下、「図８の」を省略）。
【００７６】
また、パステーブルＰＴ（図４参照）におけるパスが「/book/chapter/text/text()」のレコード（「pathid」が「０９」のレコード）から、「Ｌ」は「２３７９」であり、「Ｎ」は「１３」であることがわかる（ステップＳ８０２）。
さらに、ノードテーブル００１ＮＴ（図４（ａ１）参照）における「pathid」が「０９」のレコードから、その部分文書の出現位置が（００１，１４，１５）であり、ｌｋ（部分文書ｋの長さ）が「３１９」であることがわかる（ステップＳ８０３）。
【００７７】
また、転置表ＩＴ（図５参照）における「term」が「地球」のレコードから、単語「地球」の出現する全ての位置が、（００１，１４，１５）および（００１，１９，２０）であるとわかる（ステップＳ８０４）。
しかし、部分文書（００１，１９，２０）は、ステップＳ８０３で取り出した部分文書（００１，１４，１５）に含まれないため、部分文書（００１，１４，１５）だけが該当する部分文書として絞り込まれる（ステップＳ８０５）。つまり、部分文書（００１，１９，２０）は、使用者によって検索クエリで指定されたパスに対応する部分文書に含まれないため、検索の対象外となる。
【００７８】
また、この部分文書（００１，１４，１５）に関して、ｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）は「１」であり、ｎｉ（該当する単語ｉを含む部分文書数）も「１」であると算出できる（ステップＳ８０５）。
【００７９】
以上の７つの値を前記した式（１）に代入してスコアを算出した式を、次の式（２）に示す。
【数２】
2008146424.tif 000004
このようにして、検索クエリに該当した部分文書に関するスコアを算出することができる。
【００８０】
なお、ステップＳ８０２において、検索クエリのパスの内容によっては、「Ｌ」と「Ｎ」の値が複数存在する場合もありえる。その場合の「Ｌ」と「Ｎ」の値の扱いについて、図１０を参照しながら説明する。図１０は、「Ｌ」と「Ｎ」の値が複数存在する場合における「Ｌ」と「Ｎ」の値の算出の説明図であり、（ａ）が図４（ｂ）と同様のパステーブルＰＴなど、（ｂ）が「Ｌ」と「Ｎ」の値の算出式、をそれぞれ表している。
【００８１】
たとえば、検索クエリのパスが「任意の位置にあるtitle（//title）」である場合、図１０（ａ）に示すように、複数のパスが該当する（パスＩＤ（pathid）が「０２」と「０７」のパス）。この場合、たとえば、図１０（ｂ）の算出式に示すように、「Ｎ」の値は複数の「Ｎ（Ｎ１，Ｎ２，・・・）」の値を足したもの、「Ｌ」の値は複数の「Ｌ（Ｌ１，Ｌ２，・・・）」のそれぞれに関して、対応する「Ｎ」の値による加重平均をとったもの、として計算すればよい。具体的な算出例は、図１０（ａ）の下半分に示した通りである。
このようにして、「Ｌ」と「Ｎ」の値が複数存在する場合でも、支障なく適合度の算出やランキングを行うことができる。
【００８２】
（第２実施形態）
次に、図１１Ａ〜図２０を参照しながら、本発明の第２実施形態について説明する。図１１Ａは、第２実施形態の情報処理装置の構成図である。なお、図１の情報処理装置１と同様の構成については同じ符号を付し、説明を適宜省略する。図１１Ａの情報処理装置１ａは、図１の情報処理装置１と比べて、記憶部５ａと処理部６ａの構成が変更されている。
【００８３】
図１１Ａに示すように、情報処理装置１ａの処理部６ａは、図１の範囲ラベル部６３の代わりにタグインデックス部６６（ノード管理部）を備えている。タグインデックス部６６は、ノードテーブルＮＴａにおいてノードＩＤを使用して各ノードに関する情報を管理する。
また、記憶部５ａにおいて、ノードテーブルＮＴａと転置表ＩＴａは、図１の情報処理装置１において相当するそれぞれの構成と比べて、構成要素が一部変更されている（詳細は図１２と図１４で後記）。さらに、記憶部５ａは、図１の記憶部５と比べて、新たにテキストテーブルＴＴ（テキスト情報）を有している（詳細は図１３で後記）。
【００８４】
ここで、図１１Ｂを参照しながら、ＸＭＬ文書にノードＩＤを付与した状態について説明する。図１１Ｂは、（ａ）が図２（ａ）のＸＭＬ文書００１に対してノードＩＤを付与した状態を示す図であり、（ｂ）が図２（ｂ）のＸＭＬ文書００２に対してノードＩＤを付与した状態を示す図である。
図１１Ｂ（ａ）に示すように、ＸＭＬ文書００１において、ノードｎ１（book）はノードＩＤが「００１」で、ノードＩＤが「００２」のノードｎ１１の親である。同様に、全てのノードに識別子として異なるノードＩＤを付与する。図１１Ｂ（ｂ）についても同様である。
【００８５】
次に、図１２を参照しながら、ノードテーブルＮＴａについて説明する。図１２（ａ）は、（ａ１）がＸＭＬ文書００１に関するノードテーブル００１ＮＴａであり、（ａ２）がＸＭＬ文書００２に関するノードテーブル００２ＮＴａを示す図である。いずれのノードテーブルＮＴａも、左から順に、ノードＩＤ（nodeid）、直近の親ノードのノードＩＤを表す親ノードＩＤ（parent）、各ノードに与えられているタグ（tag）、パスの識別子を表すパスＩＤ（pathid）、そのノードがパス指定されたときの部分文書の長さを表すｌｋ、および、そのノードがパス指定されたときの部分文書に含まれるテキストデータの識別子であるテキストＩＤ（textid）（関係情報。ノード位置情報）のカラムから構成されている。
図１２（ｂ）のパステーブルＰＴは、図４（ｂ）のものと同様である。
【００８６】
続いて、図１３を参照しながら、テキストテーブルについて説明する。図１３は、（ａ）が図１２（ａ）と同様のノードテーブルＮＴａであり、（ｂ）がテキストテーブルＴＴの構成図である。
図１３（ｂ）に示すように、テキストテーブルＴＴには、各テキストノードのテキストデータ（text）がテキストＩＤ（textid）と関連付けられて格納されている。
【００８７】
次に、図１４を参照しながら、転置表ＩＴａについて説明する。図１４は、転置表ＩＴａの構成図である。
図１４に示すように、転置表ＩＴａは、単語（term）とテキストＩＤ（textid）のカラムから構成されている。テキストＩＤ（textid）は、図１３（ｂ）のテキストテーブルＴＴにおけるテキストＩＤ（textid）と対応している。
【００８８】
続いて、図１５を参照しながら、構造インデックス（パステーブルＰＴおよびノードテーブルＮＴａ）の構築処理について説明する。図１５は、構造インデックスの構築処理の概要を示すフローチャートである。
まず、使用者が、入力部２を介して、新たに蓄積したいＸＭＬ文書を情報処理装置１に投入する。そうすると、処理部６のデータ格納部６１が記憶部５のＸＭＬ文書群５１にそのＸＭＬ文書を格納する。それとき、投入された全てのＸＭＬ文書に関して（ステップＳ１５０３でＹｅｓが選択されるまで）、パスインデックス部６２がパスインデックスの構築（パステーブルＰＴの更新）を行い（ステップＳ１５０１。詳細は図１６）、タグインデックス部６６がタグインデックスの構築（ノードテーブルＮＴａとテキストテーブルＴＴの更新）を行うことにより（ステップＳ１５０２。詳細は図１７）、構造インデックスを構築する。
【００８９】
図１６は、パスインデックス部６２によるパスインデックスの構築処理のフローチャートであるが、ステップＳ１６０１〜Ｓ１６０５の処理は、図６のステップＳ６０１〜Ｓ６０５の処理と同様であるので、説明を省略する。
【００９０】
図１７は、タグインデックス（ノードテーブルＮＴａとテキストテーブルＴＴ）の構築処理のフローチャートであり、図１６のフローチャートの処理の後に行われる。
まず、投入されたＸＭＬ文書から、タグインデックス部６６は、１つのノードを取り出す（ステップＳ１７０１）。
次に、タグインデックス部６６は、パステーブルＰＴを参照し、そのノードに対応するパスＩＤを取り出す（ステップＳ１７０２）。
タグインデックス部６６は、そのノードがテキストノード（テキストデータを有するノード）である場合は、テキストデータをテキストテーブルＴＴに格納し（ステップＳ１７０３）、テキストテーブルＴＴから該当するテキストＩＤ（textid）の値を取り出す（ステップＳ１７０４）。そのノードがテキストノードでない場合、タグインデックス部６６はステップＳ１７０３とステップＳ１７０４の処理を行わずにスルーする。
【００９１】
続いて、タグインデックス部６６は、そのノードがルートノード（最上位のノード）か否かを判断し（ステップＳ１７０５）、ルートノードの場合（Ｙｅｓ）、ノードテーブルＮＴａのそのノードの「parent」に「０」を格納し（ステップＳ１７１０）、ステップＳ１７１１に進む。
そのノードがルートノードでない場合（ステップＳ１７０５でＮｏ）、タグインデックス部６６は、ノードテーブルＮＴａのそのノードの「parent」に直近の親ノードのノードＩＤを格納する（親ノードのノードＩＤをparent値とする）（ステップＳ１７０６）。
【００９２】
ステップＳ１７０６の後、タグインデックス部６６は、ルートノードに移動するまで（レコードのparent値が０になるまで。すなわち、ステップＳ１７０９でＹｅｓになるまで）、parent値をたどって１つ上の親ノードのノードテーブルＮＴａの行（レコード）に移動し（ステップＳ１７０７）、そのレコードのテキストＩＤ（textid）に、ステップＳ１７０４で取り出したテキストＩＤの値を加える（ステップＳ１７０８）。
【００９３】
つまり、ステップＳ１７０７〜Ｓ１７０９の処理により、ノードテーブルＮＴａにおいて、それぞれのノードにその配下のテキストデータのテキストＩＤ（textid）が全て集まることになる。たとえば、図１２（ａ１）において、ルートノード（ノードＩＤ（nodeid）が「００１」のノード）には、ＸＭＬ文書００１のすべてのテキストデータのテキストＩＤ（textid）が集まる。
なお、ステップＳ１７０１で取り出したノードがテキストノードでない場合、タグインデックス部６６は、ステップＳ１７０６〜Ｓ１７０９の処理を行わずにスルーする。
【００９４】
次に、タグインデックス部６６は、ノードテーブルＮＴａの末尾に、そのノード自身のレコードを加える（ステップＳ１７１１）。このとき、タグインデックス部６６は、ノードテーブルＮＴに、「ｌｋ」を含む各値（カラムの情報）を格納する。
タグインデックス部６６は、全てのノード分の処理を終了したか否かを判断し（ステップＳ１７１２）、終了していなければ（Ｎｏ）ステップＳ１７０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
【００９５】
このようにして、図１７のフローチャートの処理により、図６のステップＳ６０６〜Ｓ６１０の場合と同様、ノードテーブルＮＴａを更新するときに、「部分文書ごとの統計量」（ノードテーブルＮＴａの「ｌｋ」）を算出および格納することができる。そして、これにより、検索（適合度の算出）時に「部分文書ごとの統計量」を算出する必要がなくなり、検索処理を高速化することができる。
【００９６】
続いて、図１８を参照しながら、テキストインデックス（転置表ＩＴａ）の構築処理について説明する。図１８は、テキストインデックスの構築処理を示すフローチャートである。
図１５〜図１７に示したフローチャートの処理によって、投入されたＸＭＬ文書に関して、パステーブルＰＴとノードテーブルＮＴａが更新された後、テキストインデックス部６４は、ノードテーブルＮＴａから１レコードを取り出す（ステップＳ１８０１）。
【００９７】
続いて、テキストインデックス部６４は、取り出したレコードにおける記述内容（図１３（ａ）のノードテーブルＮＴａの「textid」に対応する図１３（ｂ）のテキストテーブルＴＴにおける「text」のカラムのデータ）に関して、形態素解析の手法を用いて単語に分ける（ステップＳ１８０２）。
【００９８】
その後、テキストインデックス部６４は、分けられたうちの１つの単語が転置表ＩＴａに含まれているか否かを判断する（ステップＳ１８０３）。
その単語が転置表ＩＴａに含まれていなかった場合（ステップＳ１８０３でＮｏ）、テキストインデックス部６４は、その単語を新たに転置表ＩＴａに登録する（ステップＳ１８０４）。
【００９９】
ステップＳ１８０３でＹｅｓの場合、およびステップＳ１８０４に続き、ステップＳ１８０５において、テキストインデックス部６４は、その単語の「textid」を転置表ＩＴａに格納する。たとえば、単語「宇宙」がＸＭＬ文書００１のノードｎ１１１に存在していれば（図１１Ｂ（ａ）参照）、ノードｎ１１１のテキストデータに該当する「textid」である「０１」（図１３（ｂ）参照）を、転置表ＩＴａ（図１４参照）の「宇宙」に対応する「textid」のカラムに格納する。
【０１００】
その後、テキストインデックス部６４は、そのレコードに関する全ての単語分の処理を終了したか否かを判断し（ステップＳ１８０６）、終了していなければ（Ｎｏ）ステップＳ１８０３に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ１８０７に進む。
また、テキストインデックス部６４は、そのＸＭＬ文書に関する全てのレコード分の処理を終了したか否かを判断し（ステップＳ１８０７）、終了していなければ（Ｎｏ）ステップＳ１８０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
【０１０１】
このようにして、図１８に示したフローチャートの処理により、検索に必要な３つの統計量（「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」）のうち、「検索単語に対する統計量」（転置表ＩＴａの情報）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができるので、検索（適合度の算出）時に「検索単語に対する統計量」を算出する必要がなくなり、検索処理を高速化することができる。
【０１０２】
次に、図１９を参照しながら、ランキング処理について説明する。図１９は、ランキング処理を示すフローチャートである。
記憶部５ａのＸＭＬ文書群５１に蓄積された複数のＸＭＬ文書に関して、検索によるランキングを行う場合、まず、使用者が入力部２を用いて検索クエリ（パスと検索文字列）を入力する。
【０１０３】
そうすると、処理部６のランキング部６５は、検索クエリからパス、検索単語（検索文字列から抽出）、ｌｑ（検索文字列ｑの長さ）、および、ｔｆｑｉ（検索文字列ｑ中の検索単語ｉの出現回数）を取り出す（算出する）（ステップＳ１９０１）。
続いて、ランキング部６５は、パステーブルＰＴを参照し、検索クエリ中のパスに対応するレコードにおける「Ｌ」、「Ｎ」およびパスＩＤ（pathid）の値を取り出す（ステップＳ１９０２）。
【０１０４】
ランキング部６５は、ノードテーブルＮＴａを参照し、ステップＳ１９０２で取り出したパスＩＤ（pathid）に対応するレコードにおけるテキストＩＤ（textid）と「ｌｋ」の値を取り出す（ステップＳ１９０３）。
ランキング部６５は、転置表ＩＴａから、検索単語の出現位置（textid）の値を取り出す（ステップＳ１９０４）。
【０１０５】
続いて、ランキング部６５は、転置表ＩＴａから取り出したテキストＩＤ（textid）の値を用いて検索単語の出現する部分文書を絞り、ｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）とｎｉ（該当する単語ｉを含む部分文書数）を算出する（ステップＳ１９０５）。ここで、ステップＳ１９０５の具体例について、図２０を参照しながら説明する。
【０１０６】
図２０は、ステップＳ１９０５の具体例、すなわち、部分文書の選別と単語の統計量の算出の例を示した図である。なお、この図２０における例は、図２〜図５などの具体例とは関係ない独立した例である。
図２０（ａ）に示した部分文書群と図２０（ｂ）に示した単語出現文書群に基づき、たとえば、まず、部分文書群（ａ）における最上位に記載された部分文書（ノードＩＤ「００４」、テキストＩＤ「０２，０３，０４，０５，０６，０７」）におけるテキストＩＤが単語出現文書群（ｂ）に存在するか探す。ここでは、（ｂ）の単語出現文書群において、テキストＩＤの「０３」と「０７」が該当する。
【０１０７】
以下、同様にして、図２０（ｃ）に示すように、部分文書が３つに絞られ、統計量のｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）は上から「２」、「１」および「１」であり、そして、ｎｉ（該当する単語ｉを含む部分文書数）は「３」であると算出することができる。
【０１０８】
図１９に戻って、ランキング部６５は、各統計量と前記した式（１）を用いて、該当する部分文書のスコアを算出する（ステップＳ１９０６）。
そして、ランキング部６５は、ステップＳ１９０６で算出したスコアの高い順に部分文書をソートすることで、ランキングを行う（ステップＳ１９０７）。
なお、ステップＳ１９０６とステップＳ１９０７の処理は、図８のステップＳ８０６とステップＳ８０７の処理と同様であるので、詳細な説明を省略する。
【０１０９】
このように、情報処理装置１ａは、予め算出および格納してある３つの統計量（「部分文書集合全体の統計量」、「部分文書ごとの統計量」および「検索単語に対する統計量」）を用いて検索（適合度の算出、ランキング）を行うことにより、検索を高速に処理することができる。
【０１１０】
また、各実施形態のＸＭＬ文書の適合度の算出方法は、前記した各フローチャートを実行するプログラムを作成することで、コンピュータ（装置）において実現することができる。さらに、それらのプログラムは、ハードディスク、フラッシュメモリ、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、ＤＶＤ（Digital Versatile Disk）などの記録媒体に保存することが可能である。
【０１１１】
以上で実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。
たとえば、本実施形態では、文字列から単語を抽出する手法として、形態素解析を用いたが、Ｎ-ｇｒａｍなどの別の手法を用いてもよい。
その他、具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図面の簡単な説明】
【０１１２】
【図１】第１実施形態の情報処理装置の構成図である。
【図２】ＸＭＬ文書のソースコードの例を示した図であり、（ａ）が図２２と同様のＸＭＬ文書００１に関する図であり、（ｂ）がその他の例としてのＸＭＬ文書００２に関する図である。
【図３】（ａ）がＸＭＬ文書００１に対して範囲ラベルを付与した状態を示す図であり、（ｂ）がＸＭＬ文書００２に対して範囲ラベルを付与した状態を示す図である。
【図４】（ａ）がノードテーブル、（ｂ）がパステーブルを例示した図である。
【図５】転置表の例を示した図である。
【図６】構造インデックスの構築処理を示すフローチャートである。
【図７】テキストインデックスの構築処理を示すフローチャートである。
【図８】ランキング処理を示すフローチャートである。
【図９】部分文書の選別と単語の統計量の算出の例を示した図である。
【図１０】「Ｌ」と「Ｎ」の値が複数存在する場合における「Ｌ」と「Ｎ」の値の算出の説明図であり、（ａ）が図４（ｂ）と同様のパステーブルＰＴなど、（ｂ）が「Ｌ」と「Ｎ」の値の算出式、をそれぞれ表している。
【図１１Ａ】第２実施形態の情報処理装置の構成図である。
【図１１Ｂ】（ａ）が図２（ａ）のＸＭＬ文書００１に対してノードＩＤを付与した状態を示す図であり、（ｂ）が図２（ｂ）のＸＭＬ文書００２に対してノードＩＤを付与した状態を示す図である。
【図１２】（ａ）がノードテーブル、（ｂ）がパステーブルを例示した図である。
【図１３】（ａ）が図１２（ａ）と同様のノードテーブルＮＴであり、（ｂ）がテキストテーブルＴＴの構成図である。
【図１４】転置表ＩＴａの例を示した図である。
【図１５】構造インデックスの構築処理の概要を示すフローチャートである。
【図１６】パスインデックス部６２によるパスインデックスの構築処理のフローチャートである。
【図１７】タグインデックスの構築処理のフローチャートである。
【図１８】テキストインデックスの構築処理を示すフローチャートである。
【図１９】ランキング処理を示すフローチャートである。
【図２０】部分文書の選別と単語の統計量の算出の例を示した図である。
【図２１】比較例の統計情報を用いたランキング例を示したものであり、（ａ）が文書例、（ｂ）が適合度（ランキング）の計算例１、（ｃ）が適合度の計算例２の説明図である。
【図２２】（ａ）はＸＭＬ文書のソースコードの例の簡略図、（ｂ）はＸＭＬ文書の木構造を示した図である。
【図２３】（ａ）と（ｂ）は、図２（ｂ）の例について、それぞれのパスによる部分文書の範囲を示した図である。
【図２４】（ａ）と（ｂ）は、図２（ｂ）の例について、それぞれのパスによる部分文書の範囲を示した図である。
【符号の説明】
【０１１３】
１，１ａ  情報処理装置
２      入力部
３      出力部
４      メモリ
５，５ａ  記憶部
６，６ａ      処理部
５１    ＸＭＬ文書群
６１    データ格納部
６２    パスインデックス部
６３    範囲ラベル部
６４    テキストインデックス部
６５    ランキング部
６６    タグインデックス部
ＩＴ，ＩＴａ  転置表
ＮＴ，ＮＴａ  ノードテーブル
ＰＴ，ＰＴａ  パステーブル
ＴＴ    テキストテーブル
【図１】
2008146424.tif 000005
【図２】
2008146424.tif 000006
【図３】
2008146424.tif 000007
【図４】
2008146424.tif 000008
【図５】
2008146424.tif 000009
【図６】
2008146424.tif 000010
【図７】
2008146424.tif 000011
【図８】
2008146424.tif 000012
【図９】
2008146424.tif 000013
【図１０】
2008146424.tif 000014
【図１１Ａ】
2008146424.tif 000015
【図１１Ｂ】
2008146424.tif 000016
【図１２】
2008146424.tif 000017
【図１３】
2008146424.tif 000018
【図１４】
2008146424.tif 000019
【図１５】
2008146424.tif 000020
【図１６】
2008146424.tif 000021
【図１７】
2008146424.tif 000022
【図１８】
2008146424.tif 000023
【図１９】
2008146424.tif 000024
【図２０】
2008146424.tif 000025
【図２１】
2008146424.tif 000026
【図２２】
2008146424.tif 000027
【図２３】
2008146424.tif 000028
【図２４】
2008146424.tif 000029