(57)【要約】【課題】蓄積されたＸＭＬ文書に対して、検索パスと検索単語を入力して適合度の算出を行う場合に、処理を高速化することを目的とする。【解決手段】本発明の情報処理装置において、処理部は、検索単語に対応する単語出現ノード情報として、この検索単語を含むＸＭＬ文書の識別情報、ノードの識別情報、および、パスの識別情報、を記憶部から取り出し、そのパスの識別情報と検索パスを比較することで、必要な単語出現ノード情報を抽出する、つまり、不要な単語出現ノード情報を削除することができる。これにより、検索単語に関する統計情報を算出するときに、その算出に使用する単語出現ノード情報の数を減少させ、部分文書に関する当該検索単語の適合度の算出に要する処理を高速化することができる。【選択図】図１
2008305124.tif 000002
【特許請求の範囲】
【請求項１】
ＸＭＬ（eXtensible Markup Language）文書群と、
前記ＸＭＬ文書群に含まれるパスごとに、当該パスの識別情報と、当該パスの配下の文書である部分文書の集合全体に関する統計情報とが関連付けられたパス情報と、
前記ＸＭＬ文書を構成するノードごとに、当該ノードを含むＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該ノードの識別情報、当該ノードに対応する前記パスの識別情報、および、当該パスの配下の部分文書に関する統計情報、が関連付けられたノード情報と、
前記ＸＭＬ文書群に用いられる単語ごとに、当該単語を含むＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該単語を含むノードの識別情報、および、当該ノードに対応する前記パスの識別情報、が単語出現ノード情報として関連付けられた単語情報と、
前記部分文書に関して、当該部分文書の集合全体に関する統計情報、当該部分文書に関する統計情報、および、検索単語に関する統計情報、に基づいて、前記部分文書に関する当該検索単語の適合度を算出する算出式と、
を記憶する記憶部と、処理部と、を備える情報処理装置によるＸＭＬ文書の適合度の算出方法であって、
前記処理部は、
検索単語、および、当該検索単語の前記ＸＭＬ文書群における検索領域を示す検索パス、の入力を受け付けるステップと、
前記パス情報から、前記検索パスに対応する、パスの識別情報、および、部分文書の集合全体に関する統計情報、を取り出すステップと、
前記単語情報から、当該検索単語に対応する単語出現ノード情報として、ＸＭＬ文書の識別情報、ノードの識別情報、および、パスの識別情報、を取り出すステップと、
前記取り出した単語出現ノード情報におけるパスの識別情報、および、前記入力された検索パスを比較して、前記入力された検索パスに対応する検索領域に含まれる単語出現ノード情報を抽出するステップと、
前記ノード情報から、前記取り出したパスの識別情報に示されるパスの配下の部分文書の位置情報として、ＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該ノードの識別情報、および、部分文書に関する統計情報、を取り出すステップと、
前記抽出した単語出現ノード情報、および、前記取り出した部分文書の位置情報から、前記検索単語に関する統計情報を算出するステップと、
前記取り出した部分文書の集合全体に関する統計情報、前記取り出した部分文書に関する統計情報、前記算出した検索単語に関する統計情報、および、前記算出式、に基づいて、前記部分文書に関する当該検索単語の適合度を算出するステップと、
を実行することを特徴とするＸＭＬ文書の適合度の算出方法。
【請求項２】
前記処理部は、
前記記憶部のＸＭＬ文書群に新たなＸＭＬ文書が追加された場合、当該追加されたＸＭＬ文書に用いられる単語ごとの、当該単語を含むＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該単語を含むノードの識別情報、および、当該ノードの識別情報に対応する前記パスの識別情報、を単語出現ノード情報として前記単語情報に追加することで、前記単語情報を更新する
ことを特徴とする請求項１に記載のＸＭＬ文書の適合度の算出方法。
【請求項３】
前記処理部は、
前記ノードの識別情報として、開始ラベル値および終了ラベル値を用い、前記開始ラベル値は当該ノードの親ノードの開始ラベル値より大きく、かつ、前記終了ラベル値は当該ノードの親ノードの終了ラベル値より小さくなるように付与して使用し、
前記抽出した単語出現ノード情報、および、前記取り出した部分文書の位置情報から、前記検索単語に関する統計情報を算出するステップにおいて、
当該単語出現ノード情報が当該部分文書の位置情報の示す範囲に含まれるか否かを、それらの情報における前記開始ラベル値および終了ラベル値の大小関係によって判断する
ことを特徴とする請求項１または請求項２に記載のＸＭＬ文書の適合度の算出方法。
【請求項４】
ＸＭＬ（eXtensible Markup Language）文書群と、
前記ＸＭＬ文書群に含まれるパスごとに、当該パスの識別情報と、当該パスの配下の文書である部分文書の集合全体に関する統計情報とが関連付けられたパス情報と、
前記ＸＭＬ文書群に含まれるテキストデータごとに、当該テキストデータの識別情報が関連付けられたテキスト情報と、
前記ＸＭＬ文書を構成するノードごとに、当該ノードの識別情報、当該ノードに対応する前記パスの識別情報、当該パスの識別情報に対応する部分文書に関する統計情報、および、当該部分文書に含まれる１以上の前記テキストデータの識別情報、が関連付けられたノード情報と、
前記ＸＭＬ文書群に用いられる単語ごとに、当該単語を含むテキストデータの識別情報、および、当該テキストデータに対応する前記パスの識別情報、が単語出現ノード情報として関連付けられた単語情報と、
前記部分文書に関して、当該部分文書の集合全体に関する統計情報、当該部分文書に関する統計情報、および、検索単語に関する統計情報、に基づいて、前記部分文書に関する当該検索単語の適合度を算出する算出式と、
を記憶する記憶部と、処理部と、を備える情報処理装置によるＸＭＬ文書の適合度の算出方法であって、
前記処理部は、
検索単語、および、当該検索単語の前記ＸＭＬ文書群における検索領域を示す検索パス、の入力を受け付けるステップと、
前記パス情報から、前記検索パスに対応する、パスの識別情報、および、部分文書の集合全体に関する統計情報、を取り出すステップと、
前記単語情報から、当該検索単語に対応する単語出現ノード情報として、テキストデータの識別情報、および、パスの識別情報、を取り出すステップと、
前記取り出した単語出現ノード情報におけるパスの識別情報、および、前記入力された検索パスを比較して、前記入力された検索パスに対応する検索領域に含まれる単語出現ノード情報を抽出するステップと、
前記ノード情報から、前記取り出したパスの識別情報に示されるパスの配下の部分文書の位置情報として、ノードの識別情報、１以上のテキストデータの識別情報、および、部分文書に関する統計情報、を取り出すステップと、
前記抽出した単語出現ノード情報、および、前記取り出した部分文書の位置情報から、前記検索単語に関する統計情報を算出するステップと、
前記取り出した部分文書の集合全体に関する統計情報、前記取り出した部分文書に関する統計情報、前記算出した検索単語に関する統計情報、および、前記算出式、に基づいて、前記部分文書に関する当該検索単語の適合度を算出するステップと、
を実行することを特徴とするＸＭＬ文書の適合度の算出方法。
【請求項５】
前記処理部は、
前記記憶部のＸＭＬ文書群に新たなＸＭＬ文書が追加された場合、当該追加されたＸＭＬ文書に用いられる単語ごとの、当該単語を含むテキストデータの識別情報、および、当該テキストデータに対応する前記パスの識別情報、を単語出現ノード情報として前記単語情報に追加することで、前記単語情報を更新する
ことを特徴とする請求項４に記載のＸＭＬ文書の適合度の算出方法。
【請求項６】
ＸＭＬ（eXtensible Markup Language）文書群、
前記ＸＭＬ文書群に含まれるパスごとに、当該パスの識別情報と、当該パスの配下の文書である部分文書の集合全体に関する統計情報とが関連付けられたパス情報、
前記ＸＭＬ文書を構成するノードごとに、当該ノードを含むＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該ノードの識別情報、当該ノードに対応する前記パスの識別情報、および、当該パスの配下の部分文書に関する統計情報、が関連付けられたノード情報、
前記ＸＭＬ文書群に用いられる単語ごとに、当該単語を含むＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該単語を含むノードの識別情報、および、当該ノードに対応する前記パスの識別情報、が単語出現ノード情報として関連付けられた単語情報、および、
前記部分文書に関して、当該部分文書の集合全体に関する統計情報、当該部分文書に関する統計情報、および、検索単語に関する統計情報、に基づいて、前記部分文書に関する当該検索単語の適合度を算出する算出式、
を記憶する記憶部と、
検索単語、および、当該検索単語の前記ＸＭＬ文書群における検索領域を示す検索パス、の入力を受け付け、
前記パス情報から、前記検索パスに対応する、パスの識別情報、および、部分文書の集合全体に関する統計情報、を取り出し、
前記単語情報から、当該検索単語に対応する単語出現ノード情報として、ＸＭＬ文書の識別情報、ノードの識別情報、および、パスの識別情報、を取り出し、
前記取り出した単語出現ノード情報におけるパスの識別情報、および、前記入力された検索パスを比較して、前記入力された検索パスに対応する検索領域に含まれる単語出現ノード情報を抽出し、
前記ノード情報から、前記取り出したパスの識別情報に示されるパスの配下の部分文書の位置情報として、ＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該ノードの識別情報、および、部分文書に関する統計情報、を取り出し、
前記抽出した単語出現ノード情報、および、前記取り出した部分文書の位置情報から、前記検索単語に関する統計情報を算出し、
前記取り出した部分文書の集合全体に関する統計情報、前記取り出した部分文書に関する統計情報、前記算出した検索単語に関する統計情報、および、前記算出式、に基づいて、前記部分文書に関する当該検索単語の適合度を算出する処理部と、
を備えることを特徴とする情報処理装置。
【請求項７】
前記処理部は、
前記記憶部のＸＭＬ文書群に新たなＸＭＬ文書が追加された場合、当該追加されたＸＭＬ文書に用いられる単語ごとの、当該単語を含むＸＭＬ文書の識別情報、当該ＸＭＬ文書における当該単語を含むノードの識別情報、および、当該ノードの識別情報に対応する前記パスの識別情報、を単語出現ノード情報として前記単語情報に追加することで、前記単語情報を更新する
ことを特徴とする請求項６に記載の情報処理装置。
【請求項８】
ＸＭＬ（eXtensible Markup Language）文書群、
前記ＸＭＬ文書群に含まれるパスごとに、当該パスの識別情報と、当該パスの配下の文書である部分文書の集合全体に関する統計情報とが関連付けられたパス情報、
前記ＸＭＬ文書群に含まれるテキストデータごとに、当該テキストデータの識別情報が関連付けられたテキスト情報、
前記ＸＭＬ文書を構成するノードごとに、当該ノードの識別情報、当該ノードに対応する前記パスの識別情報、当該パスの識別情報に対応する部分文書に関する統計情報、および、当該部分文書に含まれる１以上の前記テキストデータの識別情報、が関連付けられたノード情報、
前記ＸＭＬ文書群に用いられる単語ごとに、当該単語を含むテキストデータの識別情報、および、当該テキストデータに対応する前記パスの識別情報、が単語出現ノード情報として関連付けられた単語情報、および
前記部分文書に関して、当該部分文書の集合全体に関する統計情報、当該部分文書に関する統計情報、および、検索単語に関する統計情報、に基づいて、前記部分文書に関する当該検索単語の適合度を算出する算出式、
を記憶する記憶部と、
検索単語、および、当該検索単語の前記ＸＭＬ文書群における検索領域を示す検索パス、の入力を受け付け、
前記パス情報から、前記検索パスに対応する、パスの識別情報、および、部分文書の集合全体に関する統計情報、を取り出し、
前記単語情報から、当該検索単語に対応する単語出現ノード情報として、テキストデータの識別情報、および、パスの識別情報、を取り出し、
前記取り出した単語出現ノード情報におけるパスの識別情報、および、前記入力された検索パスを比較して、前記入力された検索パスに対応する検索領域に含まれる単語出現ノード情報を抽出し、
前記ノード情報から、前記取り出したパスの識別情報に示されるパスの配下の部分文書の位置情報として、ノードの識別情報、１以上のテキストデータの識別情報、および、部分文書に関する統計情報、を取り出し、
前記抽出した単語出現ノード情報、および、前記取り出した部分文書の位置情報から、前記検索単語に関する統計情報を算出し、
前記取り出した部分文書の集合全体に関する統計情報、前記取り出した部分文書に関する統計情報、前記算出した検索単語に関する統計情報、および、前記算出式、に基づいて、前記部分文書に関する当該検索単語の適合度を算出する処理部と、
を備えることを特徴とする情報処理装置。
【請求項９】
前記処理部は、
前記記憶部のＸＭＬ文書群に新たなＸＭＬ文書が追加された場合、当該追加されたＸＭＬ文書に用いられる単語ごとの、当該単語を含むテキストデータの識別情報、および、当該テキストデータに対応する前記パスの識別情報、を単語出現ノード情報として前記単語情報に追加することで、前記単語情報を更新する
ことを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
請求項１から請求項５までのいずれか１項に記載のＸＭＬ文書の適合度の算出方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、蓄積した複数のＸＭＬ（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」参照）について説明する。このＢＭ２５を用いた場合、文書ｋにおける単語ｉのスコアＳｑｋｉの計算式は、次の式（１）により与えられる。
【００３４】
【数１】
2008305124.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）、パスＩＤ（pathid）、開始ラベル（pre）、終了ラベル（post）を意味しており、それらの組み合わせの１つ１つを単語出現ノード（情報）という。たとえば、転置表ＩＴにおいて、単語「宇宙」に対応する出現位置が（００１，０３，３，４）であれば、文書ＩＤ（docid）が「００１」であるＸＭＬ文書００１における開始ラベル（pre）が「３」で終了ラベル（post）が「４」のノード、つまり、図３（ａ）におけるノードｎ１１１に単語「宇宙」が存在していることがわかる。また、そのノードにおけるパスＩＤが「０３」であることもわかる。
【００４８】
この転置表ＩＴにおける単語のそれぞれの出現位置にパスＩＤが含まれていることで、検索単語に関する各単語出現ノード（情報）が、検索パスによって特定される前記ＸＭＬ文書群における検索領域内のものか否かがわかり、不要な単語出現ノード（情報）を予め削除することができる。これにより、検索単語に関する統計情報を算出するときに、その算出に使用する単語出現ノード（情報）の数を減少させ、ＸＭＬ文書の適合度の算出に要する処理を高速化することができる（詳細は図８で後記）。
【００４９】
次に、図６を参照しながら、構造インデックス（パステーブルＰＴおよびノードテーブルＮＴ）の構築処理について説明する。図６は、構造インデックスの構築処理を示すフローチャートである。
まず、使用者が、入力部２を介して、新たに蓄積したいＸＭＬ文書を情報処理装置１に投入する。そうすると、処理部６のデータ格納部６１が記憶部５のＸＭＬ文書群５１にそのＸＭＬ文書を格納し、また、そのとき、パスインデックス部６２と範囲ラベル部６３が以下の処理により、構造インデックスを構築する。
【００５０】
投入されたＸＭＬ文書に関して、パスインデックス部６２は、１つのパスを取り出す（ステップＳ６０１）。パスインデックス部６２は、パステーブルＰＴを参照し、そのパスがすでにパステーブルＰＴに含まれている（存在している）か否かを判断する（ステップＳ６０２）。
【００５１】
パスがパステーブルＰＴに含まれていない場合（ステップＳ６０２でＮｏ）、パスインデックス部６２は、新しいパスＩＤを発行し、新たにそのパスをパステーブルＰＴに加え（ステップＳ６０３）、さらに、そのパスに関するＬとＮの値（部分文書の集合全体に関する統計情報）を計算する、すなわち、そのパスの配下の連結テキスト長をＬの値とし、Ｎの値を「１」として、それぞれ、パステーブルＰＴの該当箇所に格納する（ステップＳ６０４）。
【００５２】
パスがすでにパステーブルＰＴに含まれている場合（ステップＳ６０２でＹｅｓ）、パスインデックス部６２は、そのパスに関するＬとＮの値（部分文書の集合全体に関する統計情報）を計算する、すなわち、そのパスの配下の連結テキスト長の平均をＬの値とし、Ｎの値をインクリメント（１つ増加）して、それぞれ、パステーブルＰＴの該当箇所に格納する（ステップＳ６０４）。
【００５３】
その後、パスインデックス部６２は、そのＸＭＬ文書に関する全てのパス分の処理を終了したか否かを判断し（ステップＳ６０５）、終了していなければ（Ｎｏ）ステップＳ６０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ６０６に進む。
【００５４】
このようにして、ステップＳ６０１〜Ｓ６０５の処理により、検索に必要な３つの統計情報（「部分文書の集合全体に関する統計情報」、「部分文書（ごと）に関する統計情報」および「検索単語に関する統計情報」）のうち、「部分文書の集合全体に関する統計情報」（パステーブルＰＴの「Ｌ」と「Ｎ」）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができる。そして、これにより、検索（適合度の算出）時に「部分文書の集合全体に関する統計情報」を算出する必要がなくなり、検索処理を高速化することができるようになる。
【００５５】
続いて、投入されたＸＭＬ文書に関し、範囲ラベル部６３は、１つのノードを取り出す（ステップＳ６０６）。
その後、範囲ラベル部６３は、パステーブルＰＴを参照し、そのノードに対応するパスＩＤを取り出し（ステップＳ６０７）、前記した規則性にしたがって範囲ラベルを付与し（ステップＳ６０８）、ノードテーブルＮＴに各値（カラムの情報）を格納する（ステップＳ６０９）。
【００５６】
つまり、ステップＳ６０９において、範囲ラベル部６３は、文書ＩＤ（docid）、範囲ラベル（「pre」と「post」）、タグ（tag）およびパスＩＤ（pathid）だけでなく、そのノード配下の部分文書の長さを表すｌｋと、そのノードのテキストデータであるテキスト（text）に関する情報もノードテーブルＮＴに格納する。
【００５７】
その後、範囲ラベル部６３は、そのＸＭＬ文書に関する全てのノード分の処理を終了したか否かを判断し（ステップＳ６１０）、終了していなければ（Ｎｏ）ステップＳ６０６に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ６１１に進む。
【００５８】
このようにして、ステップＳ６０６〜Ｓ６１０の処理により、検索に必要な３つの統計情報（「部分文書の集合全体に関する統計情報」、「部分文書（ごと）に関する統計情報」および「検索単語に関する統計情報」）のうち、「部分文書（ごと）に関する統計情報」（ノードテーブルＮＴの「ｌｋ」）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができる。そして、これにより、検索（適合度の算出）時に「部分文書（ごと）に関する統計情報」を算出する必要がなくなり、検索処理を高速化することができる。
【００５９】
処理部６は、投入した全てのＸＭＬ文書分の処理を終了したか否かを判断し（ステップＳ６１１）、終了していなければ（Ｎｏ）ステップＳ６０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
このようにして、図６のフローチャートの処理によれば、投入した全てのＸＭＬ文書に関して、その投入直後に、「部分文書の集合全体に関する統計情報」および「部分文書（ごと）に関する統計情報」を算出および格納することができる。
【００６０】
なお、図６のフローチャートでは、説明を簡単にするため、パスインデックス部６２による処理と範囲ラベル部６３による処理を分離したが、それらの処理を並列的に行うようにしてもよい。
【００６１】
続いて、図７を参照しながら、テキストインデックス（転置表ＩＴ）の構築処理について説明する。図７は、テキストインデックスの構築処理を示すフローチャートである。
図６に示したフローチャートの処理によって、投入されたＸＭＬ文書に関して、パステーブルＰＴとノードテーブルＮＴが更新された後、処理部６のテキストインデックス部６４は、ノードテーブルＮＴから１レコード（１ノード分のデータ）を取り出す（ステップＳ７０１）。
【００６２】
続いて、テキストインデックス部６４は、取り出したレコードにおける記述内容（図４（ａ）のノードテーブルＮＴの「text」のカラムのデータ）に関して、形態素解析（計算機を用いた自然言語処理の基礎技術の１つ）の手法を用いて単語に分ける（ステップＳ７０２）。
【００６３】
その後、テキストインデックス部６４は、分けられたうちの１つの単語が転置表ＩＴに含まれているか否かを判断する（ステップＳ７０３）。
その単語が転置表ＩＴに含まれていなかった場合（ステップＳ７０３でＮｏ）、テキストインデックス部６４は、その単語を新たに転置表ＩＴに登録し（ステップＳ７０４）、ステップＳ７０５に進む。その単語が転置表ＩＴに含まれていた場合（ステップＳ７０３でＹｅｓ）、テキストインデックス部６４は、そのままステップＳ７０５に進む。
【００６４】
ステップＳ７０５において、テキストインデックス部６４は、その単語の出現位置である文書ＩＤ（docid）、パスＩＤ（pathid）および範囲ラベル（「pre」「post」）を転置表ＩＴに格納する。たとえば、単語「宇宙」がＸＭＬ文書００１のノードｎ１１１に存在していれば（図３（ａ）参照）、ＸＭＬ文書００１の文書ＩＤ「００１」、ノードｎ１１１の開始ラベル（pre）「３」および終了ラベル（post）「４」、そのノードｎ１１１のパスＩＤ「０３」（ノードテーブルＮＴ参照により）を表す（００１，０３，３，４）を、転置表ＩＴの「宇宙」に対応する「position」のカラムに格納する。
【００６５】
その後、テキストインデックス部６４は、そのレコードに関する全ての単語分の処理を終了したか否かを判断し（ステップＳ７０６）、終了していなければ（Ｎｏ）ステップＳ７０３に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ７０７に進む。
また、テキストインデックス部６４は、そのＸＭＬ文書に関する全てのレコード分の処理を終了したか否かを判断し（ステップＳ７０７）、終了していなければ（Ｎｏ）ステップＳ７０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
【００６６】
このようにして、図７に示したフローチャートの処理により、検索に必要な３つの統計情報（「部分文書の集合全体に関する統計情報」、「部分文書（ごと）に関する統計情報」および「検索単語に関する統計情報」）のうち、「検索単語に関する統計情報」（転置表ＩＴの「position」）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができる。そして、これにより、検索（適合度の算出）時に「検索単語に関する統計情報」を算出する必要がなくなり、検索処理を高速化することができる。
【００６７】
次に、図８を参照しながら、ランキング処理について説明する。図８は、ランキング処理を示すフローチャートである。
記憶部５のＸＭＬ文書群５１に蓄積された複数のＸＭＬ文書に関して、検索によるランキングを行う場合、まず、使用者が入力部２を用いて検索クエリ（検索パスと検索文字列）を入力する。
【００６８】
そうすると、処理部６のランキング部６５は、検索クエリから検索パス、検索単語（検索文字列から抽出）、ｌｑ（検索文字列ｑの長さ）、および、ｔｆｑｉ（検索文字列ｑ中の検索単語ｉの出現回数）を取り出す（算出する）（ステップＳ８０１）。
続いて、ランキング部６５は、パステーブルＰＴを参照し、検索クエリ中のパスに対応するレコードにおける「Ｌ」、「Ｎ」およびパスＩＤ（pathid）の値を取り出す（ステップＳ８０２）。
【００６９】
ランキング部６５は、転置表ＩＴから、検索単語の出現位置（文書ＩＤ（docid）、パスＩＤ（pathid）、範囲ラベル（「pre」と「post」））の値を取り出す（ステップＳ８０３）。取り出された出現位置は検索単語を含むテキストノードを示し、前記したようにその１つ１つを単語出現ノード（情報）といい、その集合を単語出現ノード群という。
【００７０】
ランキング部６５は、検索パスと、ステップＳ８０３で取り出した単語出現ノード群のパス（パスＩＤからパスに戻したもの）から、検索範囲の単語出現ノードだけを絞り込む（抽出する）（ステップＳ８０４）。
【００７１】
ランキング部６５は、ノードテーブルＮＴを参照し、ステップＳ８０２で取り出したパスＩＤ（pathid）に対応するレコードにおける部分文書の位置（文書ＩＤ（docid）と範囲ラベル（「pre」と「post」））および「ｌｋ」の値を取り出す（ステップＳ８０５）。なお、取り出した部分文書の集まりを部分文書群と呼ぶ。また、ステップＳ８０５では、パスＩＤに加えて、単語出現ノード群に含まれる文書ＩＤも用いることで、部分文書を絞り込むことも可能である。
【００７２】
続いて、ランキング部６５は、ステップＳ８０４で検索範囲に絞った単語出現ノード群と、ステップＳ８０５で取り出した部分文書群から、ｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）とｎｉ（該当する単語ｉを含む部分文書数）を算出する（ステップＳ８０５１）。ここで、ステップＳ８０４〜Ｓ８０５１の具体例について、図９を参照しながら説明する。
【００７３】
図９は、ステップＳ８０４〜Ｓ８０５１の具体例、すなわち、部分文書の選別と単語に関する統計情報の算出の例を示した図である。検索パスは「/book/chapter」であるものとする。そして、ステップＳ８０３で取り出した出現位置の集合が単語出現ノード群ＷＤ０１として示されている。
【００７４】
この単語出現ノード群ＷＤ０１に対してステップＳ８０４の絞り込みを行うことで、単語出現ノード群ＷＤ０２とすることができる。たとえば、単語出現ノード群ＷＤ０１における単語出現ノード（００１，０９，１４，１５）は、パスＩＤが「０９」でそのパスは「/book/chapter/text/text()」（図４（ｂ）のパステーブルＰＴ参照）なので、検索パスの検索範囲に含まれているので、残される。
【００７５】
一方、単語出現ノード群ＷＤ０１における単語出現ノード（００１，１６，７７，７８）は、パスＩＤが「１６」でそのパスは「/book/column/text()」（図４（ｂ）のパステーブルＰＴには不図示）なので、検索パスの検索範囲に含まれていないので、削除される。
【００７６】
その後、ステップＳ８０５で取り出された部分文書群ＰＤ０１と、単語出現ノード群ＷＤ０２とをマージ（統合）して、部分文書群ＰＤ０２とし、単語に関する統計情報であるｔｆｋｉとｎｉを算出する。ここでは、たとえば、部分文書群ＰＤ０１に含まれる単語出現ノードが、単語出現ノード群ＷＤ０２にあるか探す。つまり、単語出現ノード群ＷＤ０２において、文書ＩＤが「００１」で、範囲ラベルが「６」〜「４７」の間に含まれている単語出現ノードを探せばよい。ここでは、単語出現ノードとして、（００１，０９，１４，１５）と（００１，１４，２３，２４）が該当する。
【００７７】
以下、同様にして、部分文書群ＰＤ０２に示すように、部分文書が３つに絞られ（文書ＩＤが「００３」の部分文書（範囲ラベルが「６」〜「２７」）は単語出現ノード群ＷＤ０２中の単語出現ノードを１つも含まないため、削除されている）、単語に関する統計情報であるｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）は上から「２」、「１」および「１」であり、ｎｉ（該当する単語ｉを含む部分文書数）は「３」であると算出することができる。
【００７８】
このようにして、単語出現ノード群ＷＤ０１を予め絞り込んで単語出現ノード群ＷＤ０２とし、その単語出現ノード群ＷＤ０２と部分文書群ＰＤ０１をマージすることで、単語出現ノード群ＷＤ０１と部分文書群ＰＤ０１をマージする場合に比べて、処理を高速化することができる。
【００７９】
図８に戻って、ランキング部６５は、各統計情報と前記した式（１）を用いて、該当する部分文書のスコア（適合度）を算出する（ステップＳ８０６）。
そして、ランキング部６５は、ステップＳ８０６で算出したスコアの高い順に部分文書をソートすることで、ランキングを行う（ステップＳ８０７）。
【００８０】
このように、情報処理装置１は、予め算出および格納してある３つの統計情報（「部分文書の集合全体に関する統計情報」、「部分文書（ごと）に関する統計情報」および「検索単語に関する統計情報」）を用いて検索（適合度の算出、ランキング）を行うことにより、検索を高速に処理することができる。また、前記したように、単語出現ノード群を予め必要なものだけに絞り込んでおくことで、さらに、処理を高速化することができる。
【００８１】
（検索例）
次に、図２〜図５の具体例に対して、図８のフローチャートによる検索（ランキング）を行った場合の例について説明する。ここでは、検索クエリのうち、検索パスが「/book/chapter/text/text()」であり、検索文字列が「地球」であるものとする。
まず、ｌｑ（検索文字列ｑの長さ）は「２」であり、ｔｆｑｉ（検索文字列ｑ中の単語ｉ（地球）の出現回数）は「１」であると算出できる（図８のステップＳ８０１。以下、「図８の」を省略）。
【００８２】
また、パステーブルＰＴ（図４参照）におけるパスが「/book/chapter/text/text()」のレコード（「pathid」が「０９」のレコード）から、「Ｌ」は「２３７９」であり、「Ｎ」は「１３」であることがわかる（ステップＳ８０２）。
さらに、転置表ＩＴ（図５参照）における「term」が「地球」のレコードから、単語「地球」の出現する全ての位置が、（００１，０９，１４，１５）および（００１，１２，１９，２０）であるとわかる（ステップＳ８０４）。
【００８３】
また、検索パス「/book/chapter/text/text()」と、（００１，０９，１４，１５）および（００１，１２，１９，２０）のそれぞれのパス「/book/chapter/text/text()」および「/book/column」から、検索範囲の単語出現ノードを絞り込む、つまり、（００１，０９，１４，１５）を抽出する（ステップＳ８０４）。
【００８４】
さらに、ノードテーブル００１ＮＴ（図４（ａ１））を参照し、ステップＳ８０２で取り出したパスＩＤ「０９」に対応するレコードにおける部分文書の位置（文書ＩＤ「００１」と範囲ラベル（「１４」と「１５」））および「ｌｋ」（部分文書ｋの長さ）の値「３１９」を取り出す（ステップＳ８０５）。
【００８５】
また、ステップＳ８０４で検索範囲に絞った単語出現ノード（００１，０９，１４，１５）と、ステップＳ８０５で取り出した部分文書から、ｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）「１」とｎｉ（該当する単語ｉを含む部分文書数）「１」を算出する（ステップＳ８０５１）。
【００８６】
以上の７つの値を前記した式（１）に代入してスコアを算出した式を、次の式（２）に示す。
【数２】
2008305124.tif 000004
このようにして、検索クエリに該当した部分文書に関するスコアを算出することができる。
【００８７】
なお、ステップＳ８０２において、検索クエリのパスの内容によっては、「Ｌ」と「Ｎ」の値が複数存在する場合もありえる。その場合の「Ｌ」と「Ｎ」の値の扱いについて、図１０を参照しながら説明する。図１０は、「Ｌ」と「Ｎ」の値が複数存在する場合における「Ｌ」と「Ｎ」の値の算出の説明図であり、（ａ）が図４（ｂ）と同様のパステーブルＰＴなど、（ｂ）が「Ｌ」と「Ｎ」の値の算出式、をそれぞれ表している。
【００８８】
たとえば、検索クエリのパスが「任意の位置にあるtitle（//title）」である場合、図１０（ａ）に示すように、複数のパスが該当する（パスＩＤ（pathid）が「０２」と「０６」のパス）。この場合、たとえば、図１０（ｂ）の算出式に示すように、「Ｎ」の値は複数の「Ｎ（Ｎ１，Ｎ２，・・・）」の値を足したもの、「Ｌ」の値は複数の「Ｌ（Ｌ１，Ｌ２，・・・）」のそれぞれに関して、対応する「Ｎ」の値による加重平均をとったもの、として計算すればよい。具体的な算出例は、図１０（ａ）の下半分に示した通りである。
このようにして、「Ｌ」と「Ｎ」の値が複数存在する場合でも、支障なく適合度の算出やランキングを行うことができる。
【００８９】
（第２実施形態）
次に、図１１Ａ〜図２０を参照しながら、本発明の第２実施形態について説明する。図１１Ａは、第２実施形態の情報処理装置の構成図である。なお、図１の情報処理装置１と同様の構成については同じ符号を付し、説明を適宜省略する。図１１Ａの情報処理装置１ａは、図１の情報処理装置１と比べて、記憶部５ａと処理部６ａの構成が異なっている。
【００９０】
図１１Ａに示すように、情報処理装置１ａの処理部６ａは、図１の範囲ラベル部６３の代わりにタグインデックス部６６を備えている。タグインデックス部６６は、ノードテーブルＮＴａにおいてノードＩＤを使用して各ノードに関する情報を管理する。
また、記憶部５ａにおいて、ノードテーブルＮＴａと転置表ＩＴａは、図１の情報処理装置１において相当するそれぞれの構成と比べて、構成要素が一部変更されている（詳細は図１２と図１４で後記）。さらに、記憶部５ａは、図１の記憶部５と比べて、新たにテキストテーブルＴＴ（テキスト情報）を有している（詳細は図１３で後記）。
【００９１】
ここで、図１１Ｂを参照しながら、ＸＭＬ文書にノードＩＤを付与した状態について説明する。図１１Ｂは、（ａ）が図２（ａ）のＸＭＬ文書００１に対してノードＩＤを付与した状態を示す図であり、（ｂ）が図２（ｂ）のＸＭＬ文書００２に対してノードＩＤを付与した状態を示す図である。
図１１Ｂ（ａ）に示すように、ＸＭＬ文書００１において、ノードｎ１（book）はノードＩＤが「００１」で、ノードＩＤが「００２」のノードｎ１１の親である。同様に、全てのノードに識別子として異なるノードＩＤを付与する。図１１Ｂ（ｂ）についても同様である。
【００９２】
次に、図１２を参照しながら、ノードテーブルＮＴａについて説明する。図１２（ａ）は、（ａ１）がＸＭＬ文書００１に関するノードテーブル００１ＮＴａであり、（ａ２）がＸＭＬ文書００２に関するノードテーブル００２ＮＴａを示す図である。いずれのノードテーブルＮＴａも、左から順に、ノードＩＤ（nodeid）、直近の親ノードのノードＩＤを表す親ノードＩＤ（parent）、各ノードに与えられているタグ（tag）、パスの識別子を表すパスＩＤ（pathid）、そのノードがパス指定されたときの部分文書の長さを表すｌｋ、および、そのノードがパス指定されたときの部分文書に含まれるテキストデータの識別子であるテキストＩＤ（textid）（テキストの識別情報）のカラムから構成されている。
図１２（ｂ）のパステーブルＰＴは、図４（ｂ）のものと同様である。
【００９３】
続いて、図１３を参照しながら、テキストテーブルについて説明する。図１３は、（ａ）が図１２（ａ）と同様のノードテーブルＮＴａであり、（ｂ）がテキストテーブルＴＴの構成図である。
図１３（ｂ）に示すように、テキストテーブルＴＴには、各テキストノードのテキストデータ（text）がテキストＩＤ（textid）と関連付けられて格納されている。
【００９４】
次に、図１４を参照しながら、転置表ＩＴａについて説明する。図１４は、転置表ＩＴａの構成図である。
図１４に示すように、転置表ＩＴａは、term（単語）とposition(テキストＩＤ（textid）、パスＩＤ（pathid））のカラムから構成されている。テキストＩＤ（textid）は、図１３（ｂ）のテキストテーブルＴＴにおけるテキストＩＤ（textid）と対応している。パスＩＤ（pathid）は、図１３（ａ）におけるパスＩＤ（pathid）と対応している。この転置表ＩＴａを用いることで、検索パスによって指定される部分文書に含まれる単語出現ノードを高速で検索、抽出することができる（詳細は図１９のステップＳ１９０４などで後記）。
【００９５】
続いて、図１５を参照しながら、構造インデックス（パステーブルＰＴおよびノードテーブルＮＴａ）の構築処理について説明する。図１５は、構造インデックスの構築処理の概要を示すフローチャートである。
まず、使用者が、入力部２を介して、新たに蓄積したいＸＭＬ文書を情報処理装置１に投入する。そうすると、処理部６のデータ格納部６１が記憶部５のＸＭＬ文書群５１にそのＸＭＬ文書を格納する。それとき、投入された全てのＸＭＬ文書に関して（ステップＳ１５０３でＹｅｓが選択されるまで）、パスインデックス部６２がパスインデックスの構築（パステーブルＰＴの更新）を行い（ステップＳ１５０１。詳細は図１６）、タグインデックス部６６がタグインデックスの構築（ノードテーブルＮＴａとテキストテーブルＴＴの更新）を行うことにより（ステップＳ１５０２。詳細は図１７）、構造インデックスを構築する。
【００９６】
図１６は、パスインデックス部６２によるパスインデックスの構築処理のフローチャートであるが、ステップＳ１６０１〜Ｓ１６０５の処理は、図６のステップＳ６０１〜Ｓ６０５の処理と同様であるので、説明を省略する。
【００９７】
図１７は、タグインデックス（ノードテーブルＮＴａとテキストテーブルＴＴ）の構築処理のフローチャートであり、図１６のフローチャートの処理の後に行われる。
まず、投入されたＸＭＬ文書から、タグインデックス部６６は、１つのノードを取り出す（ステップＳ１７０１）。
次に、タグインデックス部６６は、パステーブルＰＴを参照し、そのノードに対応するパスＩＤを取り出す（ステップＳ１７０２）。
タグインデックス部６６は、そのノードがテキストノード（テキストデータを有するノード）である場合は、テキストデータをテキストテーブルＴＴに格納し（ステップＳ１７０３）、テキストテーブルＴＴから該当するテキストＩＤ（textid）の値を取り出す（ステップＳ１７０４）。そのノードがテキストノードでない場合、タグインデックス部６６はステップＳ１７０３とステップＳ１７０４の処理を行わずにスルーする。
【００９８】
続いて、タグインデックス部６６は、そのノードがルートノード（最上位のノード）か否かを判断し（ステップＳ１７０５）、ルートノードの場合（Ｙｅｓ）、ノードテーブルＮＴａのそのノードの「parent」に「０」を格納し（ステップＳ１７１０）、ステップＳ１７１１に進む。
そのノードがルートノードでない場合（ステップＳ１７０５でＮｏ）、タグインデックス部６６は、ノードテーブルＮＴａのそのノードの「parent」に直近の親ノードのノードＩＤを格納する（親ノードのノードＩＤをparent値とする）（ステップＳ１７０６）。
【００９９】
ステップＳ１７０６の後、タグインデックス部６６は、ルートノードに移動するまで（レコードのparent値が０になるまで。すなわち、ステップＳ１７０９でＹｅｓになるまで）、parent値をたどって１つ上の親ノードのノードテーブルＮＴａの行（レコード）に移動し（ステップＳ１７０７）、そのレコードのテキストＩＤ（textid）に、ステップＳ１７０４で取り出したテキストＩＤの値を加える（ステップＳ１７０８）。
【０１００】
つまり、ステップＳ１７０７〜Ｓ１７０９の処理により、ノードテーブルＮＴａにおいて、それぞれのノードにその配下のテキストデータのテキストＩＤ（textid）が全て集まることになる。たとえば、図１２（ａ１）において、ルートノード（ノードＩＤ（nodeid）が「００１」のノード）には、ＸＭＬ文書００１のすべてのテキストデータのテキストＩＤ（textid）が集まる。
なお、ステップＳ１７０１で取り出したノードがテキストノードでない場合、タグインデックス部６６は、ステップＳ１７０６〜Ｓ１７０９の処理を行わずにスルーする。
【０１０１】
次に、タグインデックス部６６は、ノードテーブルＮＴａの末尾に、そのノード自身のレコードを加える（ステップＳ１７１１）。このとき、タグインデックス部６６は、ノードテーブルＮＴに、「ｌｋ」を含む各値（カラムの情報）を格納する。
タグインデックス部６６は、全てのノード分の処理を終了したか否かを判断し（ステップＳ１７１２）、終了していなければ（Ｎｏ）ステップＳ１７０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
【０１０２】
このようにして、図１７のフローチャートの処理により、図６のステップＳ６０６〜Ｓ６１０の場合と同様、ノードテーブルＮＴａを更新するときに、「部分文書（ごと）に関する統計情報」（ノードテーブルＮＴａの「ｌｋ」）を算出および格納することができる。そして、これにより、検索（適合度の算出）時に「部分文書（ごと）に関する統計情報」を算出する必要がなくなり、検索処理を高速化することができる。
【０１０３】
続いて、図１８を参照しながら、テキストインデックス（転置表ＩＴａ）の構築処理について説明する。図１８は、テキストインデックスの構築処理を示すフローチャートである。
図１５〜図１７に示したフローチャートの処理によって、投入されたＸＭＬ文書に関して、パステーブルＰＴとノードテーブルＮＴａが更新された後、テキストインデックス部６４は、ノードテーブルＮＴａから１レコードを取り出す（ステップＳ１８０１）。
【０１０４】
続いて、テキストインデックス部６４は、取り出したレコードにおける記述内容（図１３（ａ）のノードテーブルＮＴａの「textid」に対応する図１３（ｂ）のテキストテーブルＴＴにおける「text」のカラムのデータ）に関して、形態素解析の手法を用いて単語に分ける（ステップＳ１８０２）。
【０１０５】
その後、テキストインデックス部６４は、分けられたうちの１つの単語が転置表ＩＴａに含まれているか否かを判断する（ステップＳ１８０３）。
その単語が転置表ＩＴａに含まれていなかった場合（ステップＳ１８０３でＮｏ）、テキストインデックス部６４は、その単語を新たに転置表ＩＴａに登録する（ステップＳ１８０４）。
【０１０６】
ステップＳ１８０３でＹｅｓの場合、およびステップＳ１８０４に続き、ステップＳ１８０５において、テキストインデックス部６４は、その単語の「textid」および「pathid」を転置表ＩＴａに格納する。たとえば、単語「宇宙」がＸＭＬ文書００１のノードｎ１１１に存在していれば（図１１Ｂ（ａ）参照）、ノードｎ１１１のテキストデータに該当する「textid」である「０１」（図１３（ｂ）参照）、および、ノードｎ１１１に対応する「pathid」である「０３」を、転置表ＩＴａ（図１４参照）の「宇宙」に対応する「position」のカラムに格納する。
【０１０７】
その後、テキストインデックス部６４は、そのレコードに関する全ての単語分の処理を終了したか否かを判断し（ステップＳ１８０６）、終了していなければ（Ｎｏ）ステップＳ１８０３に戻って処理を繰り返し、終了していれば（Ｙｅｓ）ステップＳ１８０７に進む。
また、テキストインデックス部６４は、そのＸＭＬ文書に関する全てのレコード分の処理を終了したか否かを判断し（ステップＳ１８０７）、終了していなければ（Ｎｏ）ステップＳ１８０１に戻って処理を繰り返し、終了していれば（Ｙｅｓ）処理を終了する。
【０１０８】
このようにして、図１８に示したフローチャートの処理により、検索に必要な３つの統計情報（「部分文書の集合全体に関する統計情報」、「部分文書（ごと）に関する統計情報」および「検索単語に関する統計情報」）のうち、「検索単語に関する統計情報」（転置表ＩＴａの情報）をＸＭＬ文書の投入直後（検索クエリの入力前）に算出および格納することができるので、検索（適合度の算出）時に「検索単語に関する統計情報」を算出する必要がなくなり、検索処理を高速化することができる。
【０１０９】
次に、図１９を参照しながら、ランキング処理について説明する。図１９は、ランキング処理を示すフローチャートである。
記憶部５ａのＸＭＬ文書群５１に蓄積された複数のＸＭＬ文書に関して、検索によるランキングを行う場合、まず、使用者が入力部２を用いて検索クエリ（検索パスと検索文字列）を入力する。
【０１１０】
そうすると、処理部６のランキング部６５は、検索クエリから検索パス、検索単語（検索文字列から抽出）、ｌｑ（検索文字列ｑの長さ）、および、ｔｆｑｉ（検索文字列ｑ中の検索単語ｉの出現回数）を取り出す（算出する）（ステップＳ１９０１）。
続いて、ランキング部６５は、パステーブルＰＴを参照し、検索クエリ中のパスに対応するレコードにおける「Ｌ」、「Ｎ」およびパスＩＤ（pathid）の値を取り出す（ステップＳ１９０２）。
【０１１１】
ランキング部６５は、転置表ＩＴａから、検索単語の出現位置（テキストＩＤ（textid）、パスＩＤ（pathid））の値を取り出す（ステップＳ１９０３）。取り出された出現位置は検索単語を含むテキストノードを示し、前記したようにその１つ１つを単語出現ノード（情報）といい、その集合を単語出現ノード群という。
【０１１２】
ランキング部６５は、検索パスと、ステップＳ１９０３で取り出した単語出現ノード群のパス（パスＩＤからパスに戻したもの）から、検索範囲の単語出現ノードだけを絞り込む（抽出する）（ステップＳ１９０４）。
【０１１３】
ランキング部６５は、ノードテーブルＮＴａを参照し、ステップＳ１９０２で取り出したパスＩＤ（pathid）に対応するレコードにおける部分文書の位置（ノードＩＤ（nodeid）、テキストＩＤ（textid））および「ｌｋ」の値を取り出す（ステップＳ１９０５）。なお、取り出した部分文書の集まりを部分文書群と呼ぶ。
【０１１４】
続いて、ランキング部６５は、検索単語の出現する部分文書を絞りｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）とｎｉ（該当する単語ｉを含む部分文書数）を算出する（ステップＳ１９０５１）。つまり、ステップＳ１９０４で検索範囲に絞った単語出現ノード群と、ステップＳ１９０５で取り出した部分文書群から、ｔｆｋｉとｎｉを算出する。ここで、ステップＳ１９０４〜Ｓ１９０５１の具体例について、図２０を参照しながら説明する。
【０１１５】
図２０は、ステップＳ１９０４〜Ｓ１９０５１の具体例、すなわち、部分文書の選別と単語に関する統計情報の算出の例を示した図である。検索パスは「/book/chapter」であるものとする。そして、ステップＳ１９０３で取り出した出現位置の集合が単語出現ノード群ＷＤ１１として示されている。
【０１１６】
この単語出現ノード群ＷＤ１１に対してステップＳ１９０４の絞り込みを行うことで、単語出現ノード群ＷＤ１２とすることができる。たとえば、単語出現ノード群ＷＤ１１における単語出現ノード（０３，０９）は、パスＩＤが「０９」でそのパスは「/book/chapter/text/text()」（図１２（ｂ）のパステーブルＰＴ参照）なので、検索パスの検索範囲に含まれているので、残される。
【０１１７】
一方、単語出現ノード群ＷＤ１１における単語出現ノード（１９，１６）は、パスＩＤが「１６」でそのパスは「/book/column/text()」なので、検索パスの検索範囲に含まれていないので、削除される。
【０１１８】
その後、ステップＳ１９０５で取り出された部分文書群ＰＤ１１と、単語出現ノード群ＷＤ１２とをマージ（統合）して、部分文書群ＰＤ１２とし、単語に関する統計情報であるｔｆｋｉとｎｉを算出する。たとえば、部分文書群ＰＤ１１に含まれる単語出現ノードが、単語出現ノード群ＷＤ１２にあるか探す。つまり、部分文書群ＰＤ１１において、ノードＩＤが「００４」の部分文書はテキストＩＤ「０２，０３，０４，０５，０６，０７」を有しているので、単語出現ノード群ＷＤ１２の中でそのテキストＩＤを持つ単語出現ノードを探せばよい。ここでは、単語出現ノードとして、（０３，０９）と（０５，１４）が該当する。
【０１１９】
以下、同様にして、部分文書群ＰＤ１２に示すように、部分文書が３つに絞られ（ノードＩＤが「２３４」の部分文書は単語出現ノード群ＷＤ１２中の単語出現ノードを１つも含まないため、削除されている）、単語に関する統計情報であるｔｆｋｉ（部分文書ｋ中の単語ｉの出現回数）は上から「２」、「１」および「１」であり、ｎｉ（該当する単語ｉを含む部分文書数）は「３」であると算出することができる。
【０１２０】
このようにして、単語出現ノード群ＷＤ１１を予め絞り込んで単語出現ノード群ＷＤ１２とし、その単語出現ノード群ＷＤ１２と部分文書群ＰＤ１１をマージすることで、単語出現ノード群ＷＤ１１と部分文書群ＰＤ１１をマージする場合に比べて、処理を高速化することができる。
【０１２１】
図１９に戻って、ランキング部６５は、各統計情報と前記した式（１）を用いて、該当する部分文書のスコアを算出する（ステップＳ１９０６）。
そして、ランキング部６５は、ステップＳ１９０６で算出したスコアの高い順に部分文書をソートすることで、ランキングを行う（ステップＳ１９０７）。
なお、ステップＳ１９０６とステップＳ１９０７の処理は、図８のステップＳ８０６とステップＳ８０７の処理と同様であるので、詳細な説明を省略する。
【０１２２】
このように、情報処理装置１ａは、予め算出および格納してある３つの統計情報（「部分文書の集合全体に関する統計情報」、「部分文書（ごと）に関する統計情報」および「検索単語に関する統計情報」）を用いて検索（適合度の算出、ランキング）を行うことにより、検索を高速に処理することができる。また、前記したように、単語出現ノード群を予め必要なものだけに絞り込んでおくことで、さらに、処理を高速化することができる。
【０１２３】
なお、各実施形態のＸＭＬ文書の適合度の算出方法は、前記した各フローチャートを実行するプログラムを作成することで、コンピュータ（装置）において実現することができる。さらに、それらのプログラムは、ハードディスク、フラッシュメモリ、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、ＤＶＤ（Digital Versatile Disk）などの記録媒体に保存することが可能である。
【０１２４】
以上で実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。
たとえば、本実施形態では、文字列から単語を抽出する手法として、形態素解析を用いたが、Ｎ-ｇｒａｍなどの別の手法を用いてもよい。
その他、具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図面の簡単な説明】
【０１２５】
【図１】第１実施形態の情報処理装置の構成図である。
【図２】ＸＭＬ文書のソースコードの例を示した図であり、（ａ）が図２２と同様のＸＭＬ文書００１に関する図であり、（ｂ）がその他の例としてのＸＭＬ文書００２に関する図である。
【図３】（ａ）がＸＭＬ文書００１に対して範囲ラベルを付与した状態を示す図であり、（ｂ）がＸＭＬ文書００２に対して範囲ラベルを付与した状態を示す図である。
【図４】（ａ）がノードテーブル、（ｂ）がパステーブルを例示した図である。
【図５】転置表の例を示した図である。
【図６】構造インデックスの構築処理を示すフローチャートである。
【図７】テキストインデックスの構築処理を示すフローチャートである。
【図８】ランキング処理を示すフローチャートである。
【図９】部分文書の選別と単語に関する統計情報の算出の例を示した図である。
【図１０】「Ｌ」と「Ｎ」の値が複数存在する場合における「Ｌ」と「Ｎ」の値の算出の説明図であり、（ａ）が図４（ｂ）と同様のパステーブルＰＴなど、（ｂ）が「Ｌ」と「Ｎ」の値の算出式、をそれぞれ表している。
【図１１Ａ】第２実施形態の情報処理装置の構成図である。
【図１１Ｂ】（ａ）が図２（ａ）のＸＭＬ文書００１に対してノードＩＤを付与した状態を示す図であり、（ｂ）が図２（ｂ）のＸＭＬ文書００２に対してノードＩＤを付与した状態を示す図である。
【図１２】（ａ）がノードテーブル、（ｂ）がパステーブルを例示した図である。
【図１３】（ａ）が図１２（ａ）と同様のノードテーブルＮＴａであり、（ｂ）がテキストテーブルＴＴの構成図である。
【図１４】転置表ＩＴａの例を示した図である。
【図１５】構造インデックスの構築処理の概要を示すフローチャートである。
【図１６】パスインデックス部６２によるパスインデックスの構築処理のフローチャートである。
【図１７】タグインデックスの構築処理のフローチャートである。
【図１８】テキストインデックスの構築処理を示すフローチャートである。
【図１９】ランキング処理を示すフローチャートである。
【図２０】部分文書の選別と単語に関する統計情報の算出の例を示した図である。
【図２１】比較例の統計情報を用いたランキング例を示したものであり、（ａ）が文書例、（ｂ）が適合度（ランキング）の計算例１、（ｃ）が適合度の計算例２の説明図である。
【図２２】（ａ）はＸＭＬ文書のソースコードの例の簡略図、（ｂ）はＸＭＬ文書の木構造を示した図である。
【図２３】（ａ）と（ｂ）は、図２（ｂ）の例について、それぞれのパスによる部分文書の範囲を示した図である。
【図２４】（ａ）と（ｂ）は、図２（ｂ）の例について、それぞれのパスによる部分文書の範囲を示した図である。
【符号の説明】
【０１２６】
１，１ａ  情報処理装置
２      入力部
３      出力部
４      メモリ
５，５ａ  記憶部
６，６ａ      処理部
５１    ＸＭＬ文書群
６１    データ格納部
６２    パスインデックス部
６３    範囲ラベル部
６４    テキストインデックス部
６５    ランキング部
６６    タグインデックス部
ＩＴ，ＩＴａ  転置表
ＮＴ，ＮＴａ  ノードテーブル
ＰＴ，ＰＴａ  パステーブル
ＴＴ    テキストテーブル
【図１】
2008305124.tif 000005
【図２】
2008305124.tif 000006
【図３】
2008305124.tif 000007
【図４】
2008305124.tif 000008
【図５】
2008305124.tif 000009
【図６】
2008305124.tif 000010
【図７】
2008305124.tif 000011
【図８】
2008305124.tif 000012
【図９】
2008305124.tif 000013
【図１０】
2008305124.tif 000014
【図１１Ａ】
2008305124.tif 000015
【図１１Ｂ】
2008305124.tif 000016
【図１２】
2008305124.tif 000017
【図１３】
2008305124.tif 000018
【図１４】
2008305124.tif 000019
【図１５】
2008305124.tif 000020
【図１６】
2008305124.tif 000021
【図１７】
2008305124.tif 000022
【図１８】
2008305124.tif 000023
【図１９】
2008305124.tif 000024
【図２０】
2008305124.tif 000025
【図２１】
2008305124.tif 000026
【図２２】
2008305124.tif 000027
【図２３】
2008305124.tif 000028
【図２４】
2008305124.tif 000029