(57)【要約】  単一オートマトン（５００）は、階層検索オートマトン（５０１）とキーワード検索オートマトン（５０２）とから構成される。階層検索オートマトン（５０１）とキーワード検索オートマトン（５０２）とは状態遷移するように連結されている。たとえば、ヒット階層ノード（Ｎ６）に状態遷移している場合にヒットキーワード「ブルー」の先頭文字『ブ』が与えられると、キーワード検索オートマトン（５０２）内の先頭文字『ブ』をあらわすノードに状態遷移する。また、先頭文字『ブ』をあらわすノードに状態遷移している場合に遷移先のノードをあらわす文字『ル』以外のヒットミスする文字が走査位置に出現すると、ヒット階層ノード（Ｎ６）に状態遷移する。
2008117454.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
検索対象となる階層構造を有する電子文書を取得する取得部、
前記取得部によって取得された電子文書に関するパススキーマを生成するパススキーマ生成部、
任意の検索キーワード、当該検索キーワードの検索条件、及び前記検索キーワードの検索範囲を特定する検索式の入力を受け付ける入力部、
前記パススキーマ生成部によって生成されたパススキーマの階層を検索する階層検索オートマトンと、前記入力部によって入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成するオートマトン生成部、
前記オートマトン生成部によって生成された単一オートマトンを用いて、前記電子文書の中から、前記検索範囲内の前記ヒットキーワードを検索する検索部、および
前記検索部によって検索された検索結果を出力する出力部、
として機能させることを特徴とする情報検索プログラム。
【請求項２】
前記階層検索オートマトンは、
遷移元となる上位の階層ノードとその遷移先となる下位の階層ノードとの間に開始タグの開始記号をあらわすノードを有し、前記上位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することを特徴とする請求項１に記載の情報検索プログラム。
【請求項３】
前記階層検索オートマトンは、
前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することを特徴とする請求項２に記載の情報検索プログラム。
【請求項４】
前記コンピュータを、
前記パススキーマを構成する各階層ノードの階層名を固有の文字列に変換する変換手段として機能させ、
前記オートマトン生成部は、
前記階層検索オートマトンを前記変換手段によって変換された固有の文字列を用いて構成することにより、前記単一オートマトンを生成し、
前記階層検索オートマトンは、
前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名から変換された固有の文字列をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することを特徴とする請求項２に記載の情報検索プログラム。
【請求項５】
前記階層検索オートマトンは、
ヒットミスする文字が出現した場合、前記上位の階層ノードに状態遷移することを特徴とする請求項３または４に記載の情報検索プログラム。
【請求項６】
前記階層検索オートマトンは、
前記一連のノード群の中の末尾ノードに状態遷移している場合に前記開始タグの終了記号が与えられると、前記下位の階層ノードに状態遷移することを特徴とする請求項３または４に記載の情報検索プログラム。
【請求項７】
前記階層検索オートマトンは、
遷移元となる下位の階層ノードとその遷移先となる上位の階層ノードとの間に終了タグの開始記号をあらわすノードを有し、前記下位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することを特徴とする請求項１に記載の情報検索プログラム。
【請求項８】
前記階層検索オートマトンは、
前記開始記号をあらわすノードと上位の階層ノードとの間に前記下位の階層ノードの階層名をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することを特徴とする請求項６に記載の情報検索プログラム。
【請求項９】
前記コンピュータを、
前記電子文書内の階層名を固有の文字列に変換する変換手段として機能させ、
前記オートマトン生成手段は、
前記階層検索オートマトンを前記変換手段によって変換された固有の文字列を用いて構成することにより、前記単一オートマトンを生成し、
前記階層検索オートマトンは、
前記開始記号をあらわすノードと上位の階層ノードとの間に前記下位の階層ノードの階層名から変換された固有の文字列をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することを特徴とする請求項７に記載の情報検索プログラム。
【請求項１０】
前記固有の文字列は、前記階層名よりも文字数が少ない固有の文字列であることを特徴とする請求項４〜６、９のいずれか１項に記載の情報検索プログラム。
【請求項１１】
前記階層検索オートマトンは、
ヒットミスする文字が出現した場合、前記下位の階層ノードに状態遷移することを特徴とする請求項８〜１０のいずれか１項に記載の情報検索プログラム。
【請求項１２】
前記階層検索オートマトンは、
前記一連のノード群の中の末尾ノードに状態遷移している場合に前記開始タグの終了記号が与えられると、前記上位の階層ノードに状態遷移することを特徴とする請求項８〜１０のいずれか１項に記載の情報検索プログラム。
【請求項１３】
前記単一オートマトンは、
前記階層検索オートマトン内のヒット階層ノードに状態遷移している場合に前記ヒットキーワードの先頭文字が与えられると、前記キーワード検索オートマトン内の前記先頭文字に対応するノードに状態遷移することを特徴とする請求項１に記載の情報検索プログラム。
【請求項１４】
前記単一オートマトンは、
前記キーワード検索オートマトン内のいずれかのノードに状態遷移している場合にヒットミスする文字が与えられると、前記ヒット階層ノードに状態遷移することを特徴とする請求項１に記載の情報検索プログラム。
【請求項１５】
前記コンピュータを、
前記パススキーマの中から、前記入力手段によって入力された検索式により特定される検索範囲に関する部分パススキーマを抽出する抽出手段として機能させ、
前記オートマトン生成手段は、
前記抽出手段によって抽出された部分パススキーマの階層を検索する階層検索オートマトンと、前記ヒットキーワードを検索するキーワード検索オートマトンとからなり、前記単一オートマトンを生成することを特徴とする請求項１に記載の情報検索プログラム。
【請求項１６】
前記コンピュータを、
前記電子文書の各階層をあらわす開始タグを、階層開始指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる開始タグに変換するとともに、前記電子文書の各階層をあらわす終了タグを、階層終了指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる終了タグに変換する変換手段として機能させ、
前記パススキーマ生成手段は、
前記変換手段による変換後の電子文書に関するパススキーマを生成することを特徴とする請求項１に記載の情報検索プログラム。
【請求項１７】
前記コンピュータを、
前記電子文書の各階層をあらわす開始タグを、階層開始指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる開始タグに変換するとともに、前記電子文書の各階層をあらわす終了タグを、前記階層開始指示子と当該終了タグに対応する開始タグの階層名により特定される階層ノードの親ノードを末端とするパスに割り振られた固有の識別子とからなる開始タグに変換する変換手段として機能させ、
前記パススキーマ生成手段は、
前記変換手段による変換後の電子文書に関するパススキーマを生成することを特徴とする請求項１に記載の情報検索プログラム。
【請求項１８】
請求項１〜１７のいずれか一項に記載の情報検索プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【請求項１９】
検索対象となる階層構造を有する電子文書を取得する取得部と、
前記取得部によって取得された電子文書に関するパススキーマを生成するパススキーマ生成部と、
任意の検索キーワードと当該検索キーワードの検索式との入力を受け付けする入力部と、
前記パススキーマ生成部によって生成されたパススキーマの階層を検索する階層検索オートマトンと、前記入力部によって入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成するオートマトン生成部、
前記オートマトン生成部によって生成された単一オートマトンを用いて、前記電子文書の前記検索式の中から、前記ヒットキーワードを検索する検索部と、
前記検索部によって検索された検索結果を出力する出力部と、
を備えることを特徴とする情報検索装置。
【請求項２０】
検索対象となる階層構造を有する電子文書を取得し、
取得された前記電子文書に関するパススキーマを生成し、
任意の検索キーワードと当該検索キーワードの検索式との入力を受け付けし、
生成されたパススキーマの階層を検索する階層検索オートマトンと、入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成し、
生成された前記単一オートマトンを用いて、前記電子文書の前記検索式の中から、前記ヒットキーワードを検索し、
検索された前記検索結果を出力することを特徴とする情報検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬ文書など階層構造を有する電子文書を検索する情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法に関するものである。
【背景技術】
【０００２】
近年、さまざまな分野で情報量が爆発的に増加している。ある分野においてはギガバイトオーダーからテラバイトオーダーになりつつあり、その莫大なデータから所望のデータを取り出すことが困難になりつつある。データは通常、管理のしやすさから階層構造を持たせて保存される。【０００３】
たとえば、図書館で本を管理するには本という階層の下にタイトル、著者、出版社、出版日、貸し出し情報などといった階層を持たせることにより、ある本に対して、管理情報ごとに情報を引き出すことが可能となる。【０００４】
階層構造を持つ膨大な電子文書から高速に所望のデータを取り出す場合、従来から、階層検索とキーワード検索とを別々のオートマトンを用いて実行している（たとえば、下記特許文献１を参照。）。【０００５】
具体的には、階層検索オートマトンにおいて階層条件にヒットした場合にキーワード検索を実行するキーワード検索オートマトンで検索を実行し、逆にキーワード検索オートマトン実行中に階層をあらわす記号が出現した場合、再び階層検索オートマトンで階層条件を検索するという処理を繰り返し実行している。【０００６】
【特許文献１】特開２００５−０７０９１１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では、ＸＭＬ文書など階層をあらわす記号の出現頻度が高い電子文書を検索する場合、階層検索オートマトンを用いた検索処理とキーワード検索オートマトンを用いた検索処理との切り替え頻度が高くなり、オーバーヘッドが生じることとなる。したがって、全体として検索速度が低下してしまうという問題があった。【０００８】
また、検索範囲を特定する複数の検索式を与えて同時に検索する場合に、すべての検索式を１つのオートマトンの中に生成するため、キーワードがヒットしたときに、現在の階層がそのヒットしたキーワードに対応する階層条件を満たしているかを判断する必要があった。したがって、高頻度でキーワードがヒットしてしまう場合、検索速度が低下してしまうという問題があった。【０００９】
本発明は、上記に鑑みてなされたものであって、階層検索オートマトンとキーワード検索オートマトンとの間のオーバーヘッドの低減を図ることにより、検索速度の向上を図ることができる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、この発明の情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法は、検索対象となる階層構造を有する電子文書を取得し、取得された電子文書に関するパススキーマを生成し、任意の検索キーワードと当該検索キーワードの検索条件と前記検索キーワードの検索範囲を特定する検索式との入力を受け付け、生成されたパススキーマの階層を検索する階層検索オートマトンと、入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成し、生成された単一オートマトンを用いて、前記電子文書の中から、前記検索範囲内の前記ヒットキーワードを検索し、検索された検索結果を出力することを特徴とする。【００１１】
また、上記発明において、前記階層検索オートマトンは、遷移元となる上位の階層ノードとその遷移先となる下位の階層ノードとの間に開始タグの開始記号をあらわすノードを有し、前記上位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することとしてもよい。【００１２】
また、上記発明において、前記階層検索オートマトンは、前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。【００１３】
また、上記発明において、前記パススキーマを構成する各階層ノードの階層名を固有の文字列に変換し、前記階層検索オートマトンを前記変換手段によって変換された固有の文字列を用いて構成することにより、前記単一オートマトンを生成し、前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名から変換された固有の文字列をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。【００１４】
また、上記発明において、前記階層検索オートマトンは、ヒットミスする文字が出現した場合、前記上位の階層ノードに状態遷移することとしてもよい。【００１５】
また、上記発明において、前記階層検索オートマトンは、前記一連のノード群の中の末尾ノードに状態遷移している場合に前記開始タグの終了記号が与えられると、前記下位の階層ノードに状態遷移することとしてもよい。【００１６】
また、上記発明において、前記階層検索オートマトンは、遷移元となる下位の階層ノードとその遷移先となる上位の階層ノードとの間に終了タグの開始記号をあらわすノードを有し、前記下位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することとしてもよい。【００１７】
また、上記発明において、前記階層検索オートマトンは、前記開始記号をあらわすノードと上位の階層ノードとの間に前記下位の階層ノードの階層名をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。【００１８】
また、上記発明において、前記電子文書内の階層名を固有の文字列に変換し、前記階層検索オートマトンを前記変換手段によって変換された固有の文字列を用いて構成することにより、前記単一オートマトンを生成し、前記階層検索オートマトンは、前記開始記号をあらわすノードと上位の階層ノードとの間に前記下位の階層ノードの階層名から変換された固有の文字列をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。【００１９】
また、上記発明において、前記階層検索オートマトンは、ヒットミスする文字が出現した場合、前記下位の階層ノードに状態遷移することとしてもよい。【００２０】
また、上記発明において、前記階層検索オートマトンは、前記一連のノード群の中の末尾ノードに状態遷移している場合に前記開始タグの終了記号が与えられると、前記上位の階層ノードに状態遷移することとしてもよい。【００２１】
また、上記発明において、前記単一オートマトンは、前記階層検索オートマトン内のヒット階層ノードに状態遷移している場合に前記ヒットキーワードの先頭文字が与えられると、前記キーワード検索オートマトン内の前記先頭文字に対応するノードに状態遷移することとしてもよい。【００２２】
また、上記発明において、前記単一オートマトンは、前記キーワード検索オートマトン内のいずれかのノードに状態遷移している場合にヒットミスする文字が与えられると、前記ヒット階層ノードに状態遷移することとしてもよい。【００２３】
また、上記発明において、前記パススキーマの中から、前記入力手段によって入力された検索式により特定される検索範囲に関する部分パススキーマを抽出し、抽出された部分パススキーマの階層を検索する階層検索オートマトンと、前記ヒットキーワードを検索するキーワード検索オートマトンとからなり、前記単一オートマトンを生成することとしてもよい。【００２４】
また、上記発明において、前記検索式により特定されるパスが前記パススキーマ内に複数通り存在するか否かを判断し、判断された判断結果に基づいて、前記部分パススキーマを抽出することとしてもよい。【００２５】
また、上記発明において、複数通り存在しないと判断された場合、前記パススキーマからルートノードと前記ヒット階層ノードとその子階層ノードとからなる部分パススキーマを抽出することとしてもよい。【００２６】
また、上記発明において、複数通り存在すると判断された場合、さらに、前記複数通りのパスがどの配列パターンに該当するかを判断し、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する配列パターンと判断された場合、ルートノードと、前記他の階層ノードと前記ヒット階層ノードとの間にのみ存在する中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００２７】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する配列パターンと判断された場合、ルートノードと、前記他の階層ノードと前記ヒット階層ノードとの間に存在する中間階層ノードと、前記ルートノードと前記他の階層ノードとの間に存在する前記中間階層ノードと同一階層名の他の中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００２８】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも下位階層に存在する配列パターンと判断された場合、ルートノードと、前記ヒット階層ノードと、当該ヒット階層ノードと前記他の階層ノードとの間に存在する子階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００２９】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記ヒット階層ノードとの間にのみ存在する中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３０】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在しかつ前記分岐元の階層ノードと前記他の階層ノードとの間に存在しない中間階層ノードと、前記ルートノードと前記分岐元の階層ノードとの間に存在する前記中間階層ノードと同一階層名の他の中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３１】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記ヒット階層ノードと、前記分岐元の階層ノードと前記他の階層ノードとの間にのみ存在する分岐先の階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３２】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記他の階層ノードとの間に存在しかつ前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在しない中間階層ノードと、前記ルートノードと前記分岐元の階層ノードとの間に存在する前記中間階層ノードと同一階層名の他の中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３３】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在すると判断された場合、ルートノードと、当該ルートノードと前記分岐元の階層ノードとの間に存在せずかつ前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在する第１の中間階層ノードと、前記ルートノードと前記第１の中間階層ノードとの間に存在せずかつ前記分岐元の階層ノードと前記第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３４】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在する第１の中間階層ノードと、前記分岐元の階層ノードと前記第１の中間階層ノードとの間に存在せずかつ前記分岐元の階層ノードと前記第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３５】
また、上記発明において、前記検索式に、前記ヒット階層ノードおよびその下位のすべての階層ノードを指定するワイルドカードが用いられている場合、ルートノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３６】
また、上記発明において、前記検索式に、任意の階層名を有するすべての階層ノードを指定するワイルドカードが用いられている場合、ルートノードと、前記階層名を有する階層ノードと、当該階層ノードの子階層ノードと、からなる部分パススキーマを抽出することとしてもよい。【００３７】
また、上記発明において、ワイルドカードが用いられている検索式が複数存在する場合、前記検索式ごとに特定されるヒット階層ノードの論理和を取ることにより、部分パススキーマを抽出することとしてもよい。【００３８】
また、上記発明において、前記部分パススキーマ内に階層名が同一のヒット階層ノードが共通の階層ノードから分岐されている場合、子階層ノードを有するヒット階層ノードに縮退させることにより、縮退済みの部分パススキーマを抽出することとしてもよい。【００３９】
また、上記発明において、前記電子文書の各階層をあらわす開始タグを、階層開始指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる開始タグに変換するとともに、前記電子文書の各階層をあらわす終了タグを、階層終了指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる終了タグに変換し、変換後の電子文書に関するパススキーマを生成することとしてもよい。【００４０】
また、上記発明において、生成された前記変換後の電子文書に関するパススキーマの中から、ルートノードと前記検索式により指定されたヒット階層ノードとからなる部分パススキーマを抽出し、前記階層検索オートマトンを前記部分パススキーマおよび当該部分パススキーマに用いられる前記階層指示子および前記固有の識別子を用いて構成することにより、前記単一オートマトンを生成することとしてもよい。【００４１】
また、上記発明において、前記階層検索オートマトンは、前記ルートノードと前記ヒット階層ノードとの間に、前記階層開始指示子をあらわすノードを有し、当該階層開始指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードに関する固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記ヒット階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。【００４２】
また、上記発明において、前記階層検索オートマトンは、前記ルートノードと前記ヒット階層ノードとの間に、前記階層終了指示子をあらわすノードを有し、当該階層終了指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードの子階層ノードに関する固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記子階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。【００４３】
また、上記発明において、前記部分パススキーマが前記ルートノードから複数のヒット階層ノードへ分岐している場合、前記各ヒット階層ノードの固有の識別子をまとめることにより、前記ルートノードと前記固有の識別子がまとめられた単一のヒット階層ノードとからなる縮退済み部分パススキーマを抽出し、前記階層検索オートマトンを前記縮退済み部分パススキーマおよび当該縮退済み部分パススキーマに用いられる前記階層指示子および前記固有の識別子を用いて構成することにより、前記単一オートマトンを生成し、前記階層検索オートマトンは、前記ルートノードと前記ヒット階層ノードとの間に、前記階層開始指示子をあらわすノードを有し、当該階層開始指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードに関するいずれかの固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記ヒット階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。【００４４】
また、上記発明において、前記検索式が複数存在する場合、前記パススキーマ生成手段によって生成された変換後の電子文書に関するパススキーマの中から、ルートノードと前記検索式により指定されたヒット階層ノードの論理和とからなる部分パススキーマを抽出し、前記階層検索オートマトンを、前記部分パススキーマのうち前記検索式により指定されたヒット階層ノードの中から選ばれた前記検索式ごとの代表ノードと、前記各検索式の論理積により指定されたヒット階層ノードの中から選ばれた代表ノードと、前記部分パススキーマに用いられる前記階層指示子および前記固有の識別子と、を用いて構成することにより、前記単一オートマトンを生成することとしてもよい。【００４５】
また、上記発明において、前記電子文書の各階層をあらわす開始タグを、階層開始指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる開始タグに変換するとともに、前記電子文書の各階層をあらわす終了タグを、前記階層開始指示子と当該終了タグに対応する開始タグの階層名により特定される階層ノードの親ノードを末端とするパスに割り振られた固有の識別子とからなる開始タグに変換し、変換後の電子文書に関するパススキーマを生成することとしてもよい。【００４６】
また、上記発明において、生成された前記変換後の電子文書に関するパススキーマの中から、ルートノードと前記検索式により指定されたヒット階層ノードとからなる部分パススキーマを抽出し、前記階層検索オートマトンを前記部分パススキーマおよび当該部分パススキーマに用いられる前記階層指示子および前記固有の識別子を用いて構成することにより、前記単一オートマトンを生成することとしてもよい。【００４７】
また、上記発明において、前記階層検索オートマトンは、ルートノードと前記ヒット階層ノードとの間に、前記階層開始指示子をあらわすノードを有し、当該階層開始指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードに関する固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記ヒット階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。【００４８】
また、上記発明において、前記階層検索オートマトンは、前記ヒット階層ノードに状態遷移している場合に前記階層開始指示子が与えられると、当該階層開始指示子をあらわすノードに状態遷移し、前記階層開始指示子以外のデータが与えられると、前記ヒット階層ノードに状態遷移することとしてもよい。【００４９】
これらの発明によれば、階層検索オートマトンのノード数を削減することができる。また、階層検索オートマトンとキーワード検索オートマトン間の切り替え回数の低減化を図ることができる。
【発明の効果】
【００５０】
本発明にかかる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法は、階層検索用オートマトンとキーワード検索用オートマトンとの間のオーバーヘッドの低減を図ることにより、検索速度の向上を図ることができるという効果を奏する。
【図面の簡単な説明】
【００５１】
【図１】図１は、この発明の実施の形態１にかかる情報検索装置のハードウェア構成を示す説明図である。
【図２】図２は、この発明の実施の形態１にかかる検索対象となる電子文書を示す説明図である。
【図３】図３は、この発明の実施の形態１にかかるパススキーマを示す説明図である。
【図４】図４は、図１に示した情報検索装置の機能的構成を示すブロック図である。
【図５】図５は、この発明の実施の形態１にかかる単一オートマトンを示す説明図である。
【図６】図６は、変換テーブルを示す説明図である。
【図７】図７は、変換後のＸＭＬ文書を示す説明図である。
【図８】図８は、変換済み単一オートマトンを示す説明図である。
【図９】図９は、この発明の実施の形態にかかる情報検索処理手順を示すフローチャートである。
【図１０】図１０は、この発明の実施の形態２にかかる検索対象となる電子文書の一例を示す説明図である。
【図１１】図１１は、この発明の実施の形態２にかかるパススキーマを示す説明図である。
【図１２】図１２は、部分パススキーマの抽出例（その１）を示す説明図である。
【図１３】図１３は、図１２に示した部分パススキーマにより階層検索オートマトンを構成した場合の単一オートマトンを示す説明図である。
【図１４】図１４は、部分パススキーマの抽出例（その２）を示す説明図である。
【図１５】図１５は、図１４に示した部分パススキーマにより階層検索オートマトンを構成した場合の単一オートマトンを示す説明図である。
【図１６】図１６は、この発明の実施の形態２にかかる情報検索装置の機能的構成を示すブロック図である。
【図１７】図１７は、配列パターンＡを示す説明図である。
【図１８】図１８は、配列パターンＢを示す説明図である。
【図１９】図１９は、配列パターンＣが適用されるパススキーマを示す説明図である。
【図２０】図２０は、抽出パターンＣ−１により抽出された部分パススキーマを示す説明図である。
【図２１】図２１は、抽出パターンＣ−２により抽出された部分パススキーマを示す説明図である。
【図２２】図２２は、抽出パターンＣ−３により抽出された部分パススキーマを示す説明図である。
【図２３】図２３は、抽出パターンＣ−４により抽出された部分パススキーマを示す説明図である。
【図２４】図２４は、抽出パターンＣ−５により抽出された部分パススキーマを示す説明図である。
【図２５】図２５は、抽出パターンＣ−６により抽出された部分パススキーマを示す説明図である。
【図２６】図２６は、この発明の実施の形態２にかかる情報検索処理手順を示すフローチャートである。
【図２７】図２７は、抽出処理（ステップＳ２６０１，Ｓ２６０２）の詳細な処理手順を示すフローチャートである。
【図２８】図２８は、部分パススキーマの抽出例（その３）を示す説明図である。
【図２９】図２９は、部分パススキーマの抽出例（その４）を示す説明図である。
【図３０】図３０は、部分パススキーマの抽出例（その５）を示す説明図である。
【図３１】図３１は、パスＩＤテーブルを示す説明図である。
【図３２】図３２は、パスＩＤへの変換例（その１）を示す説明図である。
【図３３】図３３は、変換済みパススキーマを示す説明図である。
【図３４】図３４は、部分パススキーマの抽出例（その６）を示す説明図である。
【図３５】図３５は、変換済み部分パススキーマから得られる階層検索オートマトンを示す説明図である。
【図３６】図３６は、部分パススキーマの抽出例（その７）を示す説明図である。
【図３７】図３７は、変換済み部分パススキーマから得られる階層検索オートマトンを示す説明図である。
【図３８】図３８は、複数検索式の変換例を示す説明図である。
【図３９】図３９は、部分パススキーマの抽出例（その８）を示す説明図である。
【図４０】図４０は、変換済み部分パススキーマから得られる階層検索オートマトンを示す説明図である。
【図４１】図４１は、パスＩＤへの変換例（その２）を示す説明図である。
【図４２】図４２は、第４の例の階層検索オートマトンを示す説明図である。
【図４３】図４３は、この発明の実施の形態３にかかる情報検索処理手順を示すフローチャートである。
【符号の説明】
【００５２】
１００  情報検索装置
４０１  取得部
４０２  パススキーマ生成部
４０３  入力部
４０４  オートマトン生成部
４０５  検索部
４０６  出力部
４０７  変換部
１６０１  抽出部
１６０２  判断部
【発明を実施するための最良の形態】
【００５３】
以下に添付図面を参照して、この発明にかかる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法の好適な実施の形態を詳細に説明する。【００５４】
＜実施の形態１＞
（情報検索装置のハードウェア構成）
まず、この発明の実施の形態１にかかる情報検索装置のハードウェア構成について説明する。図１は、この発明の実施の形態１にかかる情報検索装置のハードウェア構成を示す説明図である。【００５５】
図１において、情報検索装置１００は、コンピュータ本体１１０と、入力装置１２０と、出力装置１３０と、から構成されており、不図示のルータやモデムを介してＬＡＮ，ＷＡＮやインターネットなどのネットワーク１４０に接続可能である。【００５６】
コンピュータ本体１１０は、ＣＰＵ，メモリ，インターフェースを有する。ＣＰＵは、情報検索装置１００の全体の制御を司る。メモリは、ＲＯＭ，ＲＡＭ，ＨＤ，光ディスク１１１，フラッシュメモリから構成される。メモリはＣＰＵのワークエリアとして使用される。【００５７】
また、メモリには各種プログラムが格納されており、ＣＰＵからの命令に応じてロードされる。ＨＤおよび光ディスク１１１はディスクドライブによりデータのリード／ライトが制御される。また、光ディスク１１１およびフラッシュメモリはコンピュータ本体１１０に対し着脱自在である。インターフェースは、入力装置１２０からの入力、出力装置１３０への出力、ネットワーク１４０に対する送受信の制御をおこなう。【００５８】
また、入力装置１２０としては、キーボード１２１、マウス１２２、スキャナ１２３などがある。キーボード１２１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式であってもよい。マウス１２２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。スキャナ１２３は、画像を光学的に読み取る。読み取られた画像は画像データとして取り込まれ、コンピュータ本体１１０内のメモリに格納される。なお、スキャナ１２３にＯＣＲ機能を持たせてもよい。【００５９】
また、出力装置１３０としては、ディスプレイ１３１、プリンタ１３２、スピーカ１３３などがある。ディスプレイ１３１は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。また、プリンタ１３２は、画像データや文書データを印刷する。またスピーカ１３３は、効果音や読み上げ音などの音声を出力する。【００６０】
（電子文書の一例）
つぎに、この発明の実施の形態１にかかる検索対象となる電子文書について説明する。図２は、この発明の実施の形態１にかかる検索対象となる電子文書を示す説明図である。【００６１】
階層構造を有する電子文書としてＸＭＬ文書２００がある。ＸＭＬ文書２００には、タグが埋め込まれており、このタグにより階層を表現する。タグは、開始タグと終了タグの２種類のタグがある。【００６２】
本明細書では、タグを構成する記号をタグ記号と呼び、特に、『<』を開始タグのタグ開始記号、『</』を終了タグのタグ開始記号、『>』を開始タグおよび終了タグのタグ終了記号と呼ぶ。また、タグ開始記号とタグ終了記号との間に括られている文字列を階層名と呼ぶ。【００６３】
（パススキーマの一例）
つぎに、この発明の実施の形態１にかかるパススキーマについて説明する。パススキーマとは、検索対象となるＸＭＬ文書２００中に存在するルートノードからのすべてのパスを抽出し、重複するパスを１本にまとめたパスツリーである。パスツリーのノードはＸＭＬ文書２００の階層をあらわしている。以降、パスツリーのノードを階層ノードと呼ぶ。【００６４】
図３は、この発明の実施の形態１にかかるパススキーマを示す説明図である。図３に示したパススキーマ３００は、図２に示したＸＭＬ文書２００に関するパススキーマである。図３において、階層ノードＮ０はルートノードである。階層ノードＮ１はsyainをあらわすノードである。階層ノードＮ２はACTをあらわすノードである。階層ノードＮ３はcharaをあらわすノードである。階層ノードＮ６はnameをあらわすノードである。【００６５】
（情報検索装置の機能的構成）
つぎに、図１に示した情報検索装置１００の機能的構成について説明する。図４は、図１に示した情報検索装置１００の機能的構成を示すブロック図である。図４において、情報検索装置１００は、取得部４０１と、パススキーマ生成部４０２と、入力部４０３と、オートマトン生成部４０４と、検索部４０５と、出力部４０６と、変換部４０７と、を備えている。【００６６】
なお、これら各機能４０１〜４０７は、情報検索装置１００内のメモリに格納された当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。【００６７】
また、各機能からの出力データはメモリに保持される。また、図４中矢印で示した接続先の機能は、接続元の機能からの出力データをメモリから読み込んで、当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させる。【００６８】
まず、取得部４０１は、検索対象となる階層構造を有する電子文書を取得する機能を有する。具体的には、たとえば、ＸＭＬ文書２００を読み込んだり、キーボード１２１を操作することで作成されたＸＭＬ文書２００を取り込む。【００６９】
また、パススキーマ生成部４０２は、取得部４０１によって取得された電子文書に関するパススキーマを生成する機能を有する。具体的には、たとえば、ＸＭＬ文書２００を取得した場合、ＸＭＬパーサを用いてＸＭＬ文書２００の構造を解析する。ＸＭＬパーサとしては、たとえば、ＤＯＭやＳＡＸ、または下記文献（１）に示されているＸＭＬ走査器を用いることができる。これにより、図３に示したようなパススキーマを生成する。【００７０】
石野明、武田正幸 著、「パスプルーニングによる決定性有限オートマトンを用いたＸＱｕｅｒｙ処理の提案」、
DBSJ Letters,Vol.4,No.4,pp.17-20,2006.
http://www.dbsj.org/Japanese/DBSJLetters/vol4/no4/ishino.pdf【００７１】
また、入力部４０３は、任意の検索キーワードと当該検索キーワードの検索条件と検索式との入力を受け付ける機能を有する。検索キーワードとは、ユーザが電子文書の中からユーザが拾いたいキーワードであり、文字や数字などの文字列により構成される。【００７２】
検索条件とは、検索キーワードに対して与えられる条件である。単なるキーワード検索である場合、完全一致、前方一致、部分一致、後方一致、類似語などが検索条件となる。一方、数値範囲検索である場合、入力された数値の数値範囲（以上、以下など）が検索条件となる。【００７３】
また、検索式とは、検索キーワードの検索範囲を特定する質問式である。検索キーワードは電子文書の中の検索範囲から検索されることとなる。また、検索範囲は、パススキーマ内のパスにより特定される。ここでは、検索範囲は、階層をあらわす要素名を記号「/」を介して羅列した検索式により表現することとする。【００７４】
ここで、検索式の一例を示す。
/syain/ACT/chara/name = “ブルー”・・・（１）【００７５】
上記検索式（１）の左辺は、階層ノードＮ０を始点として、syainをあらわす階層ノードＮ１、ACTをあらわす階層ノードＮ２、およびcharaをあらわす階層ノードＮ３を経由し、nameをあらわす階層ノードＮ６に到達するパスを表現している。この階層ノードＮ３を親ノードとする階層ノードＮ６の階層が検索範囲となる。一方、右辺は検索キーワードをあらわしている。【００７６】
したがって、左辺で示された検索範囲の中から右辺で示された検索キーワードを検索することとなる。なお、検索範囲の階層ノードを「ヒット階層ノード」と称す。たとえば、上記検索式（１）の例では、階層ノードＮ３を親ノードとする階層ノードＮ６がヒット階層ノードとなる。また、検索範囲内において検索条件を満たすことにより検索キーワードに一致または関連することとなったキーワードを、「ヒットキーワード」と称す。上記検索式（１）の例では、「ブルー」がヒットキーワードとなる。【００７７】
また、図４において、オートマトン生成部４０４は、階層検索オートマトンとキーワード検索オートマトンとを連結した単一オートマトンを生成する機能を有する。階層検索オートマトンとは、パススキーマ３００の階層を検索するオートマトンであり、パススキーマ３００を構成する階層ノードをそのままノードとして構成している。すなわち、階層検索オートマトンは、ＸＭＬ文書２００の走査位置がパススキーマ３００内のどの階層ノードに遷移しているかを判定するオートマトンである。【００７８】
また、キーワード検索オートマトンは、検索条件を満たすヒットキーワードを検索するオートマトンである。具体的には、たとえば、ヒットキーワードの文字順に遷移する文字ごとのノードにより構成されている。すなわち、階層検索オートマトンは、ＸＭＬ文書２００の走査位置がヒットキーワードのどの文字のノードに遷移しているかを判定するオートマトンである。【００７９】
本実施の形態１では、階層検索オートマトンとキーワード検索オートマトンとを別々に扱うのではなく、階層検索オートマトンのヒット階層ノードとキーワード検索オートマトンのヒットキーワードのノード集合との間で状態遷移するように、ヒット階層ノードとヒットキーワードのノード集合とを遷移枝で連結することで、単一オートマトンを構成している。したがって、ＸＭＬ文書２００の走査位置が階層検索オートマトンのヒット階層ノードに状態遷移したときに限り、キーワード検索オートマトンによる状態遷移をおこなう。【００８０】
図５は、この発明の実施の形態１にかかる単一オートマトンを示す説明図である。この単一オートマトン５００は、上記検索式（１）が与えられた場合のオートマトンである。図５において、階層ノードＮ０は初期状態をあらわす。階層検索オートマトン５０１の上半部は、上位の階層ノードから下位の階層ノードへの状態遷移をあらわしており、下半部は、下位の階層ノードから上位の階層ノードへの状態遷移をあらわしている。【００８１】
まず、上半部の状態遷移について説明する。階層検索オートマトン５０１は、遷移元となる上位の階層ノードとその遷移先となる下位の階層ノードとの間に開始タグのタグ開始記号『<』をあらわすノードを有する。【００８２】
たとえば、上位の階層ノードＮ０とその下位の階層ノードＮ１との間、上位の階層ノードＮ１とその下位の階層ノードＮ２との間、上位の階層ノードＮ２とその下位の階層ノードＮ３との間、上位の階層ノードＮ３とその下位の階層ノードＮ６との間に、開始タグのタグ開始記号『<』をあらわすノードを有する。そして、上位の階層ノードに状態遷移している場合にタグ開始記号『<』が与えられると、タグ開始記号『<』をあらわすノードに状態遷移する。【００８３】
また、上位の階層ノードに状態遷移している場合にタグ開始記号『<』以外の文字が与えられると、当該上位の階層ノードに状態遷移する。たとえば、階層ノードＮ０に状態遷移している場合にタグ開始記号『<』以外の文字が与えられると、当該上位の階層ノードＮ０に状態遷移する。【００８４】
また、タグ開始記号『<』をあらわすノードと下位の階層ノードとの間に、下位の階層ノードの階層名をあらわす一連のノード群を有する。たとえば、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ１との間には、階層名の文字『s』、『y』、『a』、『i』、『n』をあらわす一連のノード群を有する。【００８５】
また、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ２との間には、階層名の文字『A』、『C』、『T』をあらわす一連のノード群を有する。また、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ３との間には、階層名の文字『c』、『h』、『a』、『r』、『a』をあらわす一連のノード群を有する。【００８６】
また、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ６との間には、階層名の文字『n』、『a』、『m』、『e』をあらわす一連のノード群を有する。そして、タグ開始記号『<』をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで一連のノード群に対し状態遷移する。【００８７】
たとえば、階層ノードＮ０からタグ開始記号『<』をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が文字「s」であるとすると、タグ開始記号『<』をあらわすノードから文字『s』をあらわすノードに状態遷移する。つぎの走査位置が文字「y」であるとすると、文字『s』をあらわすノードから文字『y』をあらわすノードに状態遷移する。このあとも、ヒットミスする文字が走査位置に出現するまで状態遷移を続ける。【００８８】
そして、階層名の末尾文字をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字をあらわすノードの末尾文字をあらわすノードから下位の階層ノードに状態遷移する。【００８９】
たとえば、上位の階層ノードＮ０から階層名syainの末尾文字『n』に状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字『n』をあらわすノードの末尾文字をあらわすノードから下位の階層ノードＮ１に状態遷移する。他の末尾文字『T』、『a』、『e』についても、それぞれ下位の階層ノードＮ２、Ｎ３、Ｎ６に状態遷移する。【００９０】
また、上位の階層ノードと下位の階層ノードとの間のノードに状態遷移している場合、ヒットミスする文字が走査位置に出現すると、上位の階層ノードに状態遷移する。たとえば、上位の階層ノードＮ０と下位の階層ノードＮ１との間の文字『s』をあらわすノードに状態遷移している場合、文字『y』以外のヒットミスする文字が走査位置に出現すると、上位の階層ノードＮ１に状態遷移する。【００９１】
つぎに、下半部の状態遷移について説明する。階層検索オートマトン５０１は、遷移元となる下位の階層ノードとその遷移先となる上位の階層ノードとの間に終了タグのタグ開始記号『</』をあらわすノードを有する。【００９２】
たとえば、下位の階層ノードＮ６とその上位の階層ノードＮ３との間、下位の階層ノードＮ３とその上位の階層ノードＮ２との間、下位の階層ノードＮ２とその上位の階層ノードＮ１との間、下位の階層ノードＮ１とその上位の階層ノードＮ０との間に、終了タグのタグ開始記号『</』をあらわすノードを有する。そして、下位の階層ノードに状態遷移している場合にタグ開始記号『</』が与えられると、タグ開始記号『</』をあらわすノードに状態遷移する。【００９３】
また、下位の階層ノードに状態遷移している場合にタグ開始記号『</』以外の文字が与えられると、当該下位の階層ノードに状態遷移する。たとえば、階層ノードＮ６に状態遷移している場合にタグ開始記号『</』以外の文字が与えられると、当該上位の階層ノードＮ６に状態遷移する。【００９４】
また、タグ開始記号『</』をあらわすノードと上位の階層ノードとの間に、下位の階層ノードの階層名をあらわす一連のノード群を有する。たとえば、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ３との間には、階層名の文字『n』、『a』、『m』、『e』をあらわす一連のノード群を有する。【００９５】
また、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ２との間には、階層名の文字『c』、『h』、『a』、『r』、『a』をあらわす一連のノード群を有する。また、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ１との間には、階層名の文字『A』、『C』、『T』をあらわす一連のノード群を有する。【００９６】
また、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ０との間には、階層名の文字『s』、『y』、『a』、『i』、『n』をあらわす一連のノード群を有する。そして、タグ開始記号『</』をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで一連のノード群に対し状態遷移する。【００９７】
たとえば、階層ノードＮ６からタグ開始記号『</』をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が文字『n』であるとすると、タグ開始記号『</』をあらわすノードから文字『n』をあらわすノードに状態遷移する。つぎの走査位置が文字『a』であるとすると、文字『n』をあらわすノードから文字『a』をあらわすノードに状態遷移する。このあとも、ヒットミスする文字が走査位置に出現するまで状態遷移を続ける。【００９８】
そして、階層名の末尾文字をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字をあらわすノードの末尾文字をあらわすノードから下位の階層ノードに状態遷移する。【００９９】
たとえば、上位の階層ノードＮ６から階層名nameの末尾文字『n』に状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字『n』をあらわすノードの末尾文字をあらわすノードから下位の階層ノードＮ３に状態遷移する。他の末尾文字『a』、『T』、『n』についても、それぞれ下位の階層ノードＮ２、Ｎ１、Ｎ０に状態遷移する。【０１００】
また、下位の階層ノードと上位の階層ノードとの間のノードに状態遷移している場合、ヒットミスする文字が走査位置に出現すると、下位の階層ノードに状態遷移する。たとえば、下位の階層ノードＮ６と上位の階層ノードＮ３との間の文字『n』をあらわすノードに状態遷移している場合、文字『n』以外のヒットミスする文字が走査位置に出現すると、上位の階層ノードＮ６に状態遷移する。【０１０１】
つぎに、キーワード検索オートマトン５０２について説明する。キーワード検索オートマトン５０２は、ヒットキーワードを文字順に状態遷移する一連のノード群である。図５に示したように、ヒットキーワードが、検索キーワードと同一の「ブルー」である場合、『ブ』、『ル』、『ー』をあらわすノード群がその文字順に状態遷移するように連結されている。【０１０２】
階層検索オートマトン５０１とキーワード検索オートマトン５０２とは状態遷移するように連結されている。具体的には、階層検索オートマトン５０１内のヒット階層ノードに状態遷移している場合にヒットキーワードの先頭文字が与えられると、キーワード検索オートマトン５０２内の先頭文字をあらわすノードに状態遷移する。たとえば、ヒット階層ノードＮ６に状態遷移している場合にヒットキーワード「ブルー」の先頭文字『ブ』が与えられると、キーワード検索オートマトン５０２内の先頭文字『ブ』をあらわすノードに状態遷移する。【０１０３】
また、キーワード検索オートマトン５０２内のいずれかのノードに状態遷移している場合にヒットミスする文字が与えられると、ヒット階層ノードに状態遷移する。たとえば、先頭文字『ブ』をあらわすノードに状態遷移している場合に遷移先のノードをあらわす文字『ル』以外のヒットミスする文字が走査位置に出現すると、ヒット階層ノードＮ６に状態遷移する。【０１０４】
また、ヒットキーワードにヒットした場合もヒット階層ノードに状態遷移することで、ＸＭＬ文書２００の走査を継続することができる。たとえば、文字『ー』をあらわすノードに状態遷移すると、ヒットキーワードにマッチすることになるが、このとき、ヒット階層ノードＮ６に状態遷移する。【０１０５】
このように、ＸＭＬ文書２００の走査位置が階層検索オートマトン５０１のヒット階層ノードに状態遷移したときに限り、キーワード検索オートマトン５０２に状態遷移するため、階層検索オートマトン５０１とキーワード検索オートマトン５０２との間の処理の切り替え頻度の低減化を図ることができる。【０１０６】
同様に、ヒットキーワードにマッチしないと、ただちにヒット階層ノードに状態遷移するため、ヒット階層ノードにより特定される検査範囲内の文字列のみを集中的に検索することができる。【０１０７】
また、図４において、検索部４０５は、単一オートマトン５００を用いて、電子文書の中から、検索範囲内のヒットキーワードを検索する機能を有する。具体的には、ＸＭＬ文書２００を走査し、その走査位置がどの階層であるかを階層検索オートマトン５０１により判定する。そして、ヒット階層ノードに状態遷移した場合、ＸＭＬ文書２００の走査位置がヒットキーワードのどの文字であるかをキーワード検索オートマトン５０２により判定する。【０１０８】
出力部４０６は、キーワード検索オートマトン５０２においてヒットキーワードにマッチした場合、そのマッチした文字列を検索結果として出力する機能を有する。この出力処理には、ディスプレイ１３１による画面表示やプリンタ１３２による印刷出力、音声による読み上げ、半導体メモリやＨＤへの格納、他のコンピュータ装置への送信などがある。【０１０９】
また、変換部４０７は、パススキーマ３００を構成する各階層ノードの階層名を文字数の少ない固有の文字列に変換する機能を有する。具体的には、取得部４０１により取得された電子文書内の階層名を固有の文字列に変換しておくことで、パススキーマ生成部４０２により生成されるパススキーマも固有の文字列を用いたパスツリーとなる。【０１１０】
ここで、固有の文字列とは、階層名よりも文字数が少なければよく、１文字にするのが最適である。ここでは、階層名ごとに１文字分の固有数字を割り当てることにより、変換処理を実現する。【０１１１】
図６は、変換テーブルを示す説明図である。この変換テーブル６００を用いることにより、階層名を個有数字に変換することができる。図７は、変換後のＸＭＬ文書を示す説明図である。図７のＸＭＬ文書７００は、図２に示したＸＭＬ文書２００を変換テーブル６００を用いて変換したＸＭＬ文書である。【０１１２】
図８は、変換済み単一オートマトンを示す説明図である。図８の変換済み単一オートマトン８００は、図５と同様、上記検索式（１）が与えられた場合のオートマトンであるが、階層名が固有数字に置き換えられた階層検索オートマトン８０１となっている。すなわち、遷移元の階層ノードと遷移先の階層ノードとの間のノードがタグ開始記号をあらわすノードと固有数字をあらわすノードのみとなっているため、状態遷移回数の低減化を図ることができ、検索速度の高速化を図ることができる。【０１１３】
（情報検索処理手順）
つぎに、この発明の実施の形態にかかる情報検索処理手順について説明する。図９は、この発明の実施の形態にかかる情報検索処理手順を示すフローチャートである。図９において、まず、取得部４０１により階層構造を有する電子文書（ＸＭＬ文書２００）を取得する（ステップＳ９０１）。【０１１４】
そして、変換部４０７による変換処理をおこなうか否かを判断する（ステップＳ９０２）。変換しないと判断された場合（ステップＳ９０２：Ｎｏ）、パススキーマ生成部４０２によりパススキーマ３００を生成する（ステップＳ９０３）。つぎに、検索キーワードとその検索条件と検索式とが入力されるのを待ち受ける（ステップＳ９０４：Ｎｏ）。【０１１５】
検索キーワードとその検索条件と検索式とが入力された場合（ステップＳ９０４：Ｙｅｓ）、オートマトン生成部４０４により単一オートマトン５００を生成し（ステップＳ９０５）、この単一オートマトン５００を用いて検索をおこなう（ステップＳ９０６）。このあと、ステップＳ９１２に移行する。【０１１６】
一方、ステップＳ９０２において、変換すると判断された場合（ステップＳ９０２：Ｙｅｓ）、電子文書（ＸＭＬ文書２００）内の階層名を変換テーブル６００にしたがって変換する（ステップＳ９０７）。そして、パススキーマ生成部４０２により変換済みパススキーマを生成する（ステップＳ９０８）。つぎに、検索キーワードとその検索条件と検索式とが入力されるのを待ち受ける（ステップＳ９０９：Ｎｏ）。【０１１７】
検索キーワードとその検索条件と検索式とが入力された場合（ステップＳ９０９：Ｙｅｓ）、オートマトン生成部４０４により変換済み単一オートマトン８００を生成し（ステップＳ９１０）、この変換済み単一オートマトン８００を用いて検索をおこなう（ステップＳ９１１）。このあと、ステップＳ９１２に移行する。最後に、出力部４０６により検索結果を出力する（ステップＳ９１２）ことにより、一連の処理を終了する。【０１１８】
このように、実施の形態１によれば、階層検索オートマトン５０１（８０１）とキーワード検索オートマトン５０２との間の処理の切り替え頻度の低減化を図ることができる。また、ヒットキーワードにマッチしないと、ただちにヒット階層ノードに状態遷移するため、ヒット階層ノードにより特定される検査範囲内の文字列のみを集中的に検索することができる。またこれにより、ハードウェア化が容易となる。【０１１９】
＜実施の形態２＞
つぎに、実施の形態２について説明する。実施の形態１では、パススキーマから得られるパスをすべてオートマトンで表現しているが、実施の形態２は、ルートノードからヒット階層ノードに一意に到達することができるパスツリーとなる部分パススキーマをパススキーマから抽出する。これにより、生成される単一オートマトン内の階層検索オートマトンのサイズを縮小することができる。【０１２０】
なお、実施の形態１で示した構成と同一構成については同一符号を付し、その説明を省略する。また、説明を簡略化するため、特に断りがない限り、変換テーブル６００を用いた場合と用いない場合とを区別せずに説明する。【０１２１】
（電子文書の一例）
つぎに、この発明の実施の形態２にかかる検索対象となる電子文書について説明する。図１０は、この発明の実施の形態２にかかる検索対象となる電子文書の一例を示す説明図である。ＸＭＬ文書１０００は、検索対象となる電子文書である。【０１２２】
（パススキーマの一例）
つぎに、この発明の実施の形態２にかかるパススキーマについて説明する。図１１は、この発明の実施の形態２にかかるパススキーマを示す説明図である。図１１に示したパススキーマ１１００は、図１０に示したＸＭＬ文書１０００に関するパススキーマである。【０１２３】
図１１のパススキーマ１１００において、階層ノードＮ０はルートノードである。階層ノードＮ１は階層名syainをあらわすノードである。階層ノードＮ２は階層名ACTをあらわすノードである。階層ノードＮ３は階層名charaをあらわすノードである。階層ノードＮ４は階層名nickをあらわすノードである。階層ノードＮ５は階層名castをあらわすノードである。階層ノードＮ７は階層名IDをあらわすノードである。【０１２４】
なお、階層名nameをあらわす同一の階層ノードＮ６は３つあるが、説明上それぞれを区別するために、階層ノードＮ４の子階層ノードを階層ノードＮ６ａ、階層ノードＮ３の子階層ノードを階層ノードＮ６ｂ、階層ノードＮ５の子階層ノードを階層ノードＮ６ｃとする。つぎに、部分パススキーマの抽出例について説明する。【０１２５】
（部分パススキーマの抽出例）
図１２は、部分パススキーマの抽出例（その１）を示す説明図である。図１２において、下記検索式（２）が与えられた場合、syain，ACT，castを通るパスＰ１を部分パススキーマ１２００として抽出する。このパスＰ１はユニークなパスであるため、階層ノードＮ０とcastをあらわす階層ノードＮ５とその子ノードであるnameをあらわす階層ノードＮ６ｃとからなるパスツリーが部分パススキーマとして抽出される。一方、途中のsyain，ACTをあらわす階層ノードは削除される。また、パスＰ１から外れた階層ノードも当然削除される。【０１２６】
/syain/ACT/cast = ブルー・・・（２）【０１２７】
図１３は、図１２に示した部分パススキーマ１２００により階層検索オートマトンを構成した場合の単一オートマトンを示す説明図である。この単一オートマトン１３００において、階層検索オートマトン１３０１には、部分パススキーマ１２００を構成していない階層ノードＮ１〜Ｎ４，Ｎ７が含まれていないため、階層検索オートマトン１３０１のサイズ縮小化を図ることができる。これにより、状態遷移回数を削減することができるため、検索速度の向上を図ることができる。【０１２８】
図１４は、部分パススキーマの抽出例（その２）を示す説明図である。図１４において、下記検索式（３）が与えられた場合、syain,ACT,cast,chara,nameを通るパスを部分パススキーマ１４００として抽出する。パスＰ１，Ｐ２は、階層ノードＮ２まで共通するため、階層ノードＮ１，Ｎ２は削除される。【０１２９】
また、階層ノードＮ６ａはヒット階層ノードではないので、削除される。階層ノードＮ４は階層ノードＮ３からの分岐先を特定するために残しておく。階層ノードＮ６ｂはヒット階層ノードであるため残しておく。階層ノードＮ７は階層ノードＮ６ｂの子階層ノードであるため残しておく。階層ノードＮ５，Ｎ６ｃはパスＰ２，Ｐ３外なので削除される。【０１３０】
/syain/ACT/cast/chara/name =ブルー・・・（３）【０１３１】
図１５は、図１４に示した部分パススキーマ１４００により階層検索オートマトンを構成した場合の単一オートマトン１５００を示す説明図である。階層検索オートマトン１５０１には、部分パススキーマ１４００を構成していない階層ノードＮ１，Ｎ２，Ｎ５が含まれていないため、階層検索オートマトン１５０１のサイズ縮小化を図ることができる。これにより、状態遷移回数を削減することができるため、検索速度の向上を図ることができる。【０１３２】
（情報検索装置１００の機能的構成）
図１６は、この発明の実施の形態２にかかる情報検索装置１００の機能的構成を示すブロック図である。図１６において、図４の示した機能４０１〜４０７のほかに、抽出部１６０１と判断部１６０２とを備える。【０１３３】
なお、これら各機能１６０１，１６０２は、情報検索装置１００内のメモリに格納された当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。【０１３４】
また、各機能１６０１，１６０２からの出力データはメモリに保持される。また、図１６中矢印で示した接続先の機能は、接続元の機能からの出力データをメモリから読み込んで、当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させる。【０１３５】
図１６において、抽出部１６０１は、パススキーマの中から、検索式により特定される検索範囲に関する部分パススキーマを抽出する。具体的には、検索式により特定されるパスが１通り、すなわちユニークパスである場合、パススキーマからルートノードとヒット階層ノードとその子階層ノードとからなるパスツリーを部分パススキーマとして抽出する。たとえば、図１２に示したように、部分パススキーマ１２００を抽出する。【０１３６】
一方、検索式により特定されるパスが複数通りある場合、その複数通りのパスの配列パターンに応じて部分パススキーマを抽出する。具体的な抽出例については、判断部１６０２の説明で述べる。【０１３７】
いずれにしても、オートマトン生成部４０４では、図１３および図１５に示したように、部分パススキーマ１２００，１４００の階層を検索する階層検索オートマトン１３０１，１５０１と、ヒットキーワードを検索するキーワード検索オートマトン５０２とからなる単一オートマトン１３００，１５００を生成する。【０１３８】
また、判断部１６０２は、検索式により特定されるパスがパススキーマ１１００内に複数通り存在するか否かを判断する。具体的には、検索式の末尾の階層名をあらわすノードが複数あるか否かにより、パスが複数通りあるか否かを判断することができる。たとえば、図１２に示したように、パススキーマ１１００から検索式（２）により特定されるパスはパスＰ１のみであると判断され、パスＰ１はユニークパスとなる。一方、図１４に示したように、パススキーマ１１００から検索式（３）により特定されるパスはパスＰ２，Ｐ３の２通りであると判断される。【０１３９】
また、判断部１６０２は、複数通りあると判断された場合、その複数通りのパスの配列パターンがどの配列パターンに該当するか否かを判断する。以下、配列パターン例について説明する。【０１４０】
図１７は、配列パターンＡを示す説明図である。配列パターンＡは、ヒット階層ノードと同一階層名となる類似ノードがヒット階層ノードよりも上位階層に存在する配列パターンである。図１７において、たとえば、検索式が「/a/b/name」である場合、パススキーマ１７００の階層ノードＮ０〜Ｎ４までのパスと階層ノードＮ０〜Ｎ８までのパスが特定される。ここで、階層ノードＮ４，Ｎ８のうち階層ノードＮ８をヒット階層ノードとすると、階層ノードＮ４は類似ノードとなる。【０１４１】
配列パターンＡの場合、抽出パターンＡ−１，Ａ−２がある。抽出パターンＡ−１では、ルートノードＮ０と、類似ノードとヒット階層ノードとの間にのみ存在する中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。【０１４２】
この抽出パターンＡ−１にしたがうと、ルートノードＮ０と、集合Ｙにのみ存在する中間階層ノードＮ５と、ヒット階層ノードＮ８と、からなる部分パススキーマ１７０１を抽出することができる。同様に、ルートノードＮ０と、中間階層ノードＮ７と、ヒット階層ノードＮ８と、からなる部分パススキーマ１７０２を抽出することができる。【０１４３】
一方、抽出パターンＡ−２では、ルートノードＮ０と、類似ノードとヒット階層ノードとの間に存在する中間階層ノードと、ルートノードＮ０と類似ノードとの間に存在し中間階層ノードと同一階層名である他の中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。【０１４４】
この抽出パターンＡ−２にしたがうと、ルートノードＮ０と、集合Ｙに存在する中間階層ノードＮ６と、集合Ｘに存在する他の中間階層ノードＮ２と、ヒット階層ノードＮ８と、からなる部分パススキーマ１７０３を抽出することができる。【０１４５】
なお、中間階層ノードとしてルートノードＮ０から階層の深いノードを選んでおくと、他の類似ノードに対する中間階層ノードとしても利用することができ、ノード数の削減を図ることができる。【０１４６】
図１８は、配列パターンＢを示す説明図である。配列パターンＢは、ヒット階層ノードと同一階層名となる他の階層ノードがヒット階層ノードよりも下位階層に存在する配列パターンである。図１８において、たとえば、検索式が「/a/b/name」である場合、パススキーマ１７００の階層ノードＮ０〜Ｎ４までのパスと階層ノードＮ０〜Ｎ８までのパスが特定される。ここで、階層ノードＮ４，Ｎ８のうち階層ノードＮ４をヒット階層ノードとすると、階層ノードＮ８は類似ノードとなる。【０１４７】
配列パターンＢの場合、抽出パターンＢ−１がある。抽出パターンＢ−１では、ルートノードＮ０と、ヒット階層ノードと、当該ヒット階層ノードと類似ノードとの間に存在する子階層ノードと、からなる部分パススキーマを抽出する。【０１４８】
この抽出パターンＢ−１にしたがうと、ルートノードＮ０と、ヒット階層ノードＮ４と、集合Ｙ（当該ヒット階層ノードＮ４と類似ノードＮ８との間）に存在する子階層ノードＮ５，Ｎ６またはＮ７と、からなる部分パススキーマ１８０１〜１８０３を抽出することができる。【０１４９】
図１９は、配列パターンＣが適用されるパススキーマを示す説明図である。配列パターンＣは、類似ノードがヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンである。図１９において、たとえば、検索式が「/a/b/name」である場合、パススキーマ１９００の階層ノードＮ０〜Ｎ７までのパスと階層ノードＮ０〜Ｎ３，Ｎ８〜Ｎ１５までのパスが特定される。ここで、階層ノードＮ７，Ｎ１５のうち階層ノードＮ７をヒット階層ノードとすると、階層ノードＮ１５は類似ノードとなる。【０１５０】
配列パターンＣの場合、抽出パターンＣ−１〜Ｃ−６がある。抽出パターンＣ−１では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間にのみ存在する中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。【０１５１】
図２０は、抽出パターンＣ−１により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−１では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間にのみ存在する中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。【０１５２】
この抽出パターンＣ−１にしたがうと、ルートノードＮ０と、集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）にのみ存在する中間階層ノードＮ４と、ヒット階層ノードＮ７と、からなる部分パススキーマ２０００を抽出することができる。【０１５３】
なお、図１９に示した集合Ｙにおいて、階層ノードＮ５は、同一階層名ｂの階層ノードＮ２が集合Ｘに存在し、また、同一階層名ｂの階層ノードＮ１０が集合Ｚに存在するため、選ばれない。同様に、階層ノードＮ６は、同一階層名ｂの階層ノードＮ１２，Ｎ１３が集合Ｚに存在するため選ばれない。【０１５４】
図２１は、抽出パターンＣ−２により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−２では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間に存在しかつ分岐元の階層ノードと類似ノードとの間に存在しない中間階層ノードと、ルートノードと分岐元の階層ノードとの間に存在する中間階層ノードと同一階層名の他の中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。【０１５５】
この抽出パターンＣ−２にしたがうと、ルートノードＮ０と、集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在しかつ集合Ｚ（分岐元の階層ノードＮ３と類似ノードＮ１５との間）に存在しない中間階層ノードＮ５と、集合Ｘ（ルートノードＮ０と分岐元の階層ノードＮ３との間）に存在する中間階層ノードＮ５と同一階層名の他の中間階層ノードＮ２と、ヒット階層ノードＮ７と、からなる部分パススキーマ２１００を抽出することができる。【０１５６】
図２２は、抽出パターンＣ−３により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−３では、ルートノードＮ０と、ヒット階層ノードと、分岐元の階層ノードと類似ノードとの間にのみ存在する分岐先の階層ノードと、からなる部分パススキーマを抽出する。【０１５７】
この抽出パターンＣ−３にしたがうと、ルートノードＮ０と、ヒット階層ノードＮ７と、集合Ｚ（分岐元の階層ノードＮ３と類似ノードＮ１５との間）にのみ存在する分岐先の階層ノードＮ８，Ｎ９またはＮ１１と、からなる部分パススキーマ２２０１〜２２０３を抽出することができる。【０１５８】
図２３は、抽出パターンＣ−４により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−４では、ルートノードＮ０と、分岐元の階層ノードと類似ノードとの間に存在しかつ分岐元の階層ノードとヒット階層ノードとの間に存在しない中間階層ノードと、ルートノードＮ０と分岐元の階層ノードとの間に存在する中間階層ノードと同一階層名の他の中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。【０１５９】
この抽出パターンＣ−４にしたがうと、ルートノードＮ０と、集合Ｚ（分岐元の階層ノードＮ３と類似ノードＮ１５との間）に存在しかつ集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在しない中間階層ノードＮ１４と、集合Ｘ（ルートノードＮ０と分岐元の階層ノードＮ３との間）に存在する中間階層ノードＮ１４と同一階層名の他の中間階層ノードＮ１と、ヒット階層ノードＮ７と、からなる部分パススキーマ２３００を抽出することができる。【０１６０】
図２４は、抽出パターンＣ−５により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−５では、ルートノードＮ０と、当該ルートノードＮ０と分岐元の階層ノードとの間に存在せずかつ分岐元の階層ノードとヒット階層ノードとの間に存在する第１の中間階層ノードと、ルートノードＮ０と第１の中間階層ノードとの間に存在せずかつ第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードと分岐元の階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出する。【０１６１】
この抽出パターンＣ−５にしたがうと、ルートノードＮ０と、当該ルートノードＮ０と集合Ｘ（分岐元の階層ノードＮ３との間）に存在せずかつ集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在する第１の中間階層ノードＮ６と、ルートノードＮ０と第１の中間階層ノードＮ６との間に存在せずかつ第１の中間階層ノードＮ６と同一階層名の第２の中間階層ノードＮ１３，Ｎ１４のうち最上位の中間階層ノードＮ１３と分岐元の階層ノードＮ３との間の第３の中間階層ノードＮ８，Ｎ９またはＮ１１と、からなる部分パススキーマ２４０１〜２４０３を抽出することができる。【０１６２】
図２５は、抽出パターンＣ−６により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−６では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間に存在する第１の中間階層ノードと、分岐元の階層ノードと第１の中間階層ノードとの間に存在せずかつ第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードと分岐元の階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出する。【０１６３】
この抽出パターンＣ−６にしたがうと、ルートノードＮ０と、集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在する第１の中間階層ノードＮ５と、分岐元の階層ノードＮ３と第１の中間階層ノードＮ５との間に存在せずかつ第１の中間階層ノードＮ５と同一階層名の第２の中間階層ノードＮ１０のうち最上位の中間階層ノードＮ１０と分岐元の階層ノードＮ３との間の第３の中間階層ノードＮ８またはＮ９と、からなる部分パススキーマ２５０１〜２５０３を抽出することができる。【０１６４】
（情報検索処理手順）
つぎに、この発明の実施の形態２にかかる情報検索処理手順について説明する。図２６は、この発明の実施の形態２にかかる情報検索処理手順を示すフローチャートである。図２６において、図９に示したステップと同一処理内容については同一ステップ番号を付し、その説明を省略する。【０１６５】
図２６において、ステップＳ９０４とステップＳ９０５との間において、抽出処理を実行する（ステップＳ２６０１）。この抽出処理（ステップＳ２６０１）は、上述した判断部１６０２および抽出部１６０１により実行される。このため、ステップＳ９０５の単一オートマトン生成では、抽出処理（ステップＳ２６０１）により抽出された部分パススキーマを用いて構成された階層検索オートマトンとキーワード検索オートマトン５０２とからなる単一オートマトンを生成することとなる。【０１６６】
同様に、ステップＳ９０９とステップＳ９１０との間においても、抽出処理を実行する（ステップＳ２６０２）。この抽出処理（ステップＳ２６０２）も、上述した判断部１６０２および抽出部１６０１により実行される。このため、ステップＳ９１０の変換済み単一オートマトン生成では、抽出処理（ステップＳ２６０２）により抽出された変換済み部分パススキーマを用いて構成された変換済み階層検索オートマトンとキーワード検索オートマトン５０２とからなる変換済み単一オートマトンを生成することとなる。【０１６７】
つぎに、上述した抽出処理（ステップＳ２６０１，Ｓ２６０２）の詳細な処理手順について説明する。図２７は、抽出処理（ステップＳ２６０１，Ｓ２６０２）の詳細な処理手順を示すフローチャートである。図２７において、まず、検索式からルートノードおよびヒット階層ノードを特定し（ステップＳ２７０１）、検索式により特定されるパスが複数通りあるか否かを判断する（ステップＳ２７０２）。【０１６８】
複数通りない場合（ステップＳ２７０２：Ｎｏ）、図１２に示したように、そのパスにより特定される部分パススキーマ（または変換済み部分パススキーマ）をパススキーマ（変換済みパススキーマ）から抽出する（ステップＳ２７０３）。これにより、ステップＳ９０５（Ｓ９１０）に移行する。【０１６９】
一方、複数通りある場合（ステップＳ２７０２：Ｙｅｓ）、該当する配列パターンを特定し（ステップＳ２７０４）、抽出パターンを選択する（ステップＳ２７０５）。抽出パターンの選択はランダムにおこなってもよく、また優先順位をつけて選択してもよい。【０１７０】
このあと、選択された抽出パターンにしたがって部分パススキーマ（または変換済み部分パススキーマ）をパススキーマ（変換済みパススキーマ）から抽出して（ステップＳ２７０６）、ステップＳ９０５（Ｓ９１０）に移行する。これにより、一連の処理を終了する。【０１７１】
（ワイルドカード検索）
つぎに、ワイルドカード検索について説明する。ワイルドカードとは、検索する際にどんなパターンにもマッチする特殊文字であり、検索式の組み方により、２通りの検索範囲が特定される。ここでは、検索式中において、ワイルドカードを『//』で表記する。【０１７２】
まず、Ｘ//のように、ワイルドカードが末尾に記述されている検索式の場合、ヒット階層ノードとしてＸを階層名とする階層ノードのみを選択する。図２８は、部分パススキーマの抽出例（その３）を示す説明図である。図１１に示したパススキーマ１１００を例にあげると、下記検索式（４）が与えられた場合、ルートノードＮ０とヒット階層ノードＮ３とからなる部分パススキーマ２８００を抽出することができ、サイズの縮小を図ることができる。なお、フラグが立っている階層ノードは検索対象となる階層ノードである。【０１７３】
/syain/ACT/chara//・・・（４）【０１７４】
また、//Ｘのように、ワイルドカードが末尾に記述されていない検索式の場合、ヒット階層ノードとして、上記文献（１）に示したパスプルーニング手法により導き出される階層ノードとその子階層ノードを選択する。図２９は、部分パススキーマの抽出例（その４）を示す説明図である。図１１に示したパススキーマ１１００を例にあげると、下記検索式（５）が与えられた場合、ルートノードＮ０とヒット階層ノードＮ６（Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃ）とからなる部分パススキーマ２９００を抽出することができる。なお、フラグが立っている階層ノードは検索対象となる階層ノードである。【０１７５】
//name・・・（５）【０１７６】
また、検索式が複数与えられる場合もある。この場合、すべての検索式から得られるノードを網羅するように、ヒット階層ノードやその子階層ノードを特定する。具体的には、各検索式の論理和を取ることにより、部分パススキーマを抽出する。【０１７７】
図３０は、部分パススキーマの抽出例（その５）を示す説明図である。図３０に示した抽出例は、上述した検索式（４）,（５）が与えられた場合の抽出例である。この場合、ルートノードＮ０とヒット階層ノードＮ３，Ｎ６（Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃ）とからなる部分パススキーマ３０００を抽出することができ、サイズの縮小を図ることができる。なお、フラグが立っている階層ノードは検索対象となる階層ノードである。【０１７８】
また、ヒット階層ノードＮ６ａ，Ｎ６ｂは階層ノードＮ３からの分岐先ノードであるため、この２本のパスを１本にまとめることができる。具体的には、子階層ノードを有するヒット階層ノードＮ６ｂに縮退させる。部分パススキーマ３００１は、縮退済み部分パススキーマである。これにより、さらにサイズの縮小を図ることができる。【０１７９】
このように、実施の形態２によれば、ルートノードからヒット階層ノードに一意に到達することができるパスツリーとなる部分パススキーマをパススキーマから抽出するため、階層検索オートマトンの生成元を、ノード数が削減された部分パススキーマに絞り込むことができる。したがって、生成される単一オートマトン内の階層検索オートマトンのサイズを縮小することができる。【０１８０】
階層検索オートマトンのサイズが縮小されると、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。【０１８１】
＜実施の形態３＞
つぎに、実施の形態３について説明する。実施の形態１では、図６に示した変換テーブル６００により、電子文書内の階層名ごとに固有の文字列に変換することで階層検索オートマトンのノード数を削減しているが、実施の形態３では、パススキーマ内のパスごとにタグ記号および固有の識別子を割り当てることにより、階層検索オートマトンのノード数を削減する。【０１８２】
たとえば、図１１に示したパススキーマ１１００の場合、階層名nameをあらわす階層ノードをヒット階層ノードとするパスは３本存在するが、パスごとに異なる識別子を割り当てることにより、電子文書読み出し時にその識別子を検出するだけでパスを判別することができる。なお、実施の形態１，２で示した構成と同一構成については同一符号を付し、その説明を省略する。【０１８３】
（第１の例）
（パスＩＤテーブル）
図３１は、パスＩＤテーブル３１００を示す説明図である。図３１において、パスＩＤテーブル３１００はパスごとにパスＩＤが割り振られている。このパスＩＤテーブル３１００は、電子文書を読み込んだときに作成される。【０１８４】
具体的には、パスＩＤテーブル３１００にパスＩＤが割り振られていないパスが検出された場合、その検出されたパスに対して固有のパスＩＤを割り振る。一方、パスＩＤが割り振られているパスが検出された場合には、電子文書のタグを変換する。【０１８５】
なお、検索対象がＸＭＬ文書である場合、開始タグのタグ記号を『<…>』から『［…』に変換する。また、終了タグのタグ記号を『</…>』から『/…』に変換する。この変換処理は、図４に示した変換部４０７が実行する。また、タグ記号『[』を階層開始指示子と称し、タグ記号『/』を階層終了指示子と称す。【０１８６】
（パスＩＤへの変換例）
つぎに、パスＩＤへの変換例（その１）について説明する。図３２は、パスＩＤへの変換例（その１）を示す説明図である。図３２において、符号３２０１は変換前のＸＭＬ文書であり、符号３２０２は変換済みＸＭＬ文書である。【０１８７】
（変換済みパススキーマの生成例）
図３３は、変換済みパススキーマを示す説明図である。この変換済みパススキーマ３３００は、図３２に示した変換済みＸＭＬ文書３２０２から生成されたパススキーマである。ここでは、各階層ノードの符号として「ｎ＃」を付している。＃はパスＩＤである。したがって、図１１に示した階層ノードＮ６（Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃ）のように、同一階層名nameのノードが複数存在することはなく、図３３では、ｎ４，ｎ６，ｎ９のように、同一階層名nameであっても区別がつくように表現される。【０１８８】
（部分パススキーマの抽出例）
図３４は、部分パススキーマの抽出例（その６）を示す説明図である。図３４において、下記検索式（６）が与えられると、変換済み部分パススキーマ３４００を変換済みパススキーマ３３００から抽出することができる。同一検索式が与えられた図１４の抽出例と比較するとノード数が削減されていることがわかる。【０１８９】
/syain/ACT/chara/name/・・・（６）【０１９０】
図３５は、変換済み部分パススキーマ３４００から得られる階層検索オートマトンを示す説明図である。図３５において、階層検索オートマトン３５００は、変換済み部分パススキーマ３４００を構成する階層ノードｎ０，ｎ４と、階層開始指示子『[』をあらわすノードと、階層終了指示子『/』をあらわすノードとから構成される。階層検索オートマトン３５００は、図１５に示した階層検索オートマトン１５０１と比べると、ノード数が削減されている。【０１９１】
階層検索オートマトン３５００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。【０１９２】
また、階層検索オートマトン３５００では、ヒット階層ノードｎ４に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ４自身に状態遷移する。【０１９３】
また、階層検索オートマトン３５００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』が与えられると、ヒット階層ノードｎ４に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。【０１９４】
また、ヒット階層ノードｎ４６９には、ヒット階層ノードｎ４の子階層ノードｎ７の識別子『７』も埋め込まれているため、階層検索オートマトン３５００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『７』が与えられると、ヒット階層ノードｎ４に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。【０１９５】
したがって、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。【０１９６】
（第２の例）
（ワイルドカード検索）
第２の例は、ワイルドカード検索に関する検索例である。ワイルドカード検索の場合、複数通りのパスが選択される場合がある。図３６は、部分パススキーマの抽出例（その７）を示す説明図である。図３６において、たとえば、下記検索式（７）が与えられた場合、変換済みパススキーマ３３００から、ルートノードｎ０とヒット階層ノードｎ４、ｎ６、ｎ９とからなる変換済み部分パススキーマ３６０１を抽出することができる。【０１９７】
また、これらのヒット階層ノードｎ４、ｎ６、ｎ９は同一階層名であるため、縮退させることにより変換済み部分パススキーマ３６０２を得ることができる。縮退されたヒット階層ノードｎ４６９は、ヒット階層ノードｎ４、ｎ６、ｎ９の識別子『４』，『６』，『９』とヒット階層ノードｎ４の子階層ノードｎ７の識別子『７』が埋め込まれたノードである。【０１９８】
図３７は、変換済み部分パススキーマ３６０２から得られる階層検索オートマトンを示す説明図である。図３７において、階層検索オートマトン３７００は、変換済み部分パススキーマ３６０２を構成する階層ノードｎ０，ｎ４６９と、階層開始指示子『[』をあらわすノードと、階層終了指示子『/』をあらわすノードとから構成される。階層検索オートマトン３７００は、図１５に示した階層検索オートマトン１５０１と比べると、ノード数が削減されている。【０１９９】
階層検索オートマトン３７００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。【０２００】
また、階層検索オートマトン３７００では、ヒット階層ノードｎ４６９に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ４６９自身に状態遷移する。【０２０１】
また、ヒット階層ノードｎ４６９には、ヒット階層ノードｎ４、ｎ６、ｎ９の識別子『４』，『６』，『９』が埋め込まれているため、階層検索オートマトン３７００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』，『６』または『９』が与えられると、ヒット階層ノードｎ４６９に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。【０２０２】
また、ヒット階層ノードｎ４６９には、ヒット階層ノードｎ４の子階層ノードｎ７の識別子『７』も埋め込まれているため、階層検索オートマトン３７００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『７』が与えられると、ヒット階層ノードｎ４６９に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。【０２０３】
したがって、この第２の例では、単一オートマトンの生成に先立って、パススキーマを縮退させることができるため、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。【０２０４】
（第３の例）
第３の例は、複数検索式の場合の検索例である。検索式が複数与えられた場合、すべての検索式から得られるノードを網羅するように、ヒット階層ノードやその子階層ノードを特定する。具体的には、各検索式の論理和を取ることにより、変換済み部分パススキーマを抽出する。【０２０５】
図３８は、複数検索式の変換例を示す説明図である。検索式Ｋ１＝/syain/ACT/chara//と検索式Ｋ２＝//nameとが与えられた場合、検索式Ｋ１および検索式Ｋ２を検索式Ｑ１およびＱ２に変換する。検索式Ｑ１およびＱ２は、検索式Ｋ１およびＫ２内の階層名を、それぞれ階層開始指示子『[』と固有の識別子とからなる記号列に変換し、これらを論理和（図中、「ｏｒ」で表記）でつなげることにより表現される。【０２０６】
また、検索式Ｑ１およびＱ２から、これらの論理積（図中、「＆」で表記）ととった検索式Ｑ２＆Ｑ１を生成する。この場合、検索式Ｑ１およびＱ２から、検索式Ｑ２＆Ｑ１に含まれる記号列（[４，[６）を削除する。このように、３つの検索式Ｑ１，Ｑ２，Ｑ２＆Ｑ１からそれぞれ１つずつ記号列を選択することにより、変換済み部分パススキーマを抽出する。【０２０７】
図３９は、部分パススキーマの抽出例（その８）を示す説明図である。図３９において、３つの検索式Ｑ１，Ｑ２，Ｑ２＆Ｑ１から、それぞれ記号列[３，[４，[９が選ばれたとすると、変換済み部分パススキーマ３９００が抽出される。【０２０８】
なお、選ばれなかった記号列は、検索式Ｑ１，Ｑ２，Ｑ２＆Ｑ１においてそれぞれ選ばれた記号列の階層ノードに埋め込まれることとなる。たとえば、ヒット階層ノードｎ３には、階層開始指示子『[』をあらわすノードからの遷移先を特定するため、記号列[３，[５，[７が埋め込まれることとなる。【０２０９】
また、子階層ノードｎ４，ｎ５を有するため、記号列[４，[５も階層終了指示子『/』をあらわすノードからの遷移先として埋め込まれることとなる。さらに、子階層ノードｎ５はヒット階層ノードではないため、その子階層ノードであるヒット階層ノードｎ６の記号列[６も階層終了指示子『/』をあらわすノードからの遷移先として埋め込まれる。【０２１０】
また、ヒット階層ノードｎ９には、階層開始指示子『[』をあらわすノードからの遷移先を特定するため、記号列[９が埋め込まれることとなる。また、ヒット階層ノードｎ４には、階層開始指示子『[』をあらわすノードからの遷移先を特定するため、記号列[４，[６が埋め込まれることとなる。また、ヒット階層ノードｎ４は子階層ノードｎ７を有するため、記号列[７も階層終了指示子『/』をあらわすノードからの遷移先として埋め込まれることとなる。【０２１１】
図４０は、変換済み部分パススキーマ３９００から得られる階層検索オートマトンを示す説明図である。図４０において、階層検索オートマトン４０００は、変換済み部分パススキーマ３９００を構成する階層ノードｎ０，ｎ３，ｎ４，ｎ９と、階層開始指示子『[』をあらわすノードと、階層終了指示子『/』をあらわすノードとから構成される。【０２１２】
階層検索オートマトン４０００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。【０２１３】
また、階層検索オートマトン４０００では、ヒット階層ノードｎ４に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ４自身に状態遷移する。【０２１４】
また、階層検索オートマトン４０００では、ヒット階層ノードｎ９に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ９自身に状態遷移する。【０２１５】
また、階層検索オートマトン４０００では、ヒット階層ノードｎ３に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ３自身に状態遷移する。【０２１６】
また、ヒット階層ノードｎ４には、ヒット階層ノードｎ６の識別子『６』が埋め込まれているため、階層検索オートマトン４０００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』または『６』が与えられると、ヒット階層ノードｎ４に状態遷移する。【０２１７】
また、ヒット階層ノードｎ３には、ヒット階層ノードｎ３，ｎ５およびｎ７の識別子『３』，『５』および『７』が埋め込まれているため、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『３』，『５』または『７』が与えられると、ヒット階層ノードｎ３に状態遷移する。【０２１８】
同様に、ヒット階層ノードｎ９には、ヒット階層ノードｎ９の識別子『９』が埋め込まれているため、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『９』が与えられると、ヒット階層ノードｎ９に状態遷移する。【０２１９】
一方、階層開始指示子『[』をあらわすノードに状態遷移している場合、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。【０２２０】
また、ヒット階層ノードｎ４には、子階層ノードｎ７の識別子『７』が埋め込まれているため、階層検索オートマトン４０００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『７』が与えられると、ヒット階層ノードｎ４に状態遷移する。【０２２１】
また、ヒット階層ノードｎ４には、階層ノードｎ４，ｎ５，ｎ６の識別子『４』，『５』および『６』が埋め込まれているため、階層検索オートマトン４０００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『４』，『５』または『６』が与えられると、ヒット階層ノードｎ３に状態遷移する。【０２２２】
一方、階層終了指示子『/』をあらわすノードに状態遷移している場合、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。【０２２３】
したがって、この第３の例では、単一オートマトンの生成に先立って、パススキーマを縮退させることができるため、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。【０２２４】
（第４の例）
第４の例は、階層指示子を開始タグと終了タグとで区別せず、同一記号を用いる場合の例である。具体的には、たとえば、階層終了指示子『/』を、階層開始指示子『[』に変え、識別子をタグ間文字列の識別子の親となる識別子を用いる。【０２２５】
図４１は、パスＩＤへの変換例（その２）を示す説明図である。図４１において、符号３２０１は変換前のＸＭＬ文書であり、符号４１００は変換済みＸＭＬ文書である。たとえば、ＸＭＬ文書４１００の４行目に着目すると、変換後の終了タグは、階層開始指示子『[』と、開始タグに埋め込まれている識別子『４』の親となる識別子『３』と、からなる記号列『[３』となる。他の変換後のタグも同様に変換される。なお、この場合の変換済み部分パススキーマは、図３４に示した場合と同様である。【０２２６】
図４２は、第４の例の階層検索オートマトンを示す説明図である。図４２において、階層検索オートマトン４２００は、ルートノードｎ０とヒット階層ノードｎ４と階層開始指示子『[』をあらわすノードから構成される。図３５に示した階層検索オートマトン３５００と比べると、階層終了指示子『/』をあらわすノードが削除されている分、オートマトンサイズが縮小される。【０２２７】
階層検索オートマトン４２００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層開始指示子『[』以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。【０２２８】
また、階層検索オートマトン４２００では、ヒット階層ノードｎ４に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層開始指示子『[』以外の文字が与えられると、ヒット階層ノードｎ４自身に状態遷移する。【０２２９】
また、階層検索オートマトン４２００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』が与えられると、ヒット階層ノードｎ４に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。【０２３０】
したがって、この第４の例では、単一オートマトンの生成に先立って、パススキーマを縮退させることができるため、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。【０２３１】
（情報検索処理手順）
つぎに、この発明の実施の形態３にかかる情報検索処理手順について説明する。図４３は、この発明の実施の形態３にかかる情報検索処理手順を示すフローチャートである。図４３において、図９に示したステップと同一処理内容については同一ステップ番号を付し、その説明を省略する。【０２３２】
図４３において、ステップＳ９０２：Ｙｅｓのあと、変換部４０７により、パスＩＤテーブル３１００を用いて、タグ開始記号および階層名を変換する（ステップＳ４３０１）。したがって、図３２または図４１に示したような変換済みＸＭＬ文書３２０２，４１００が得られ、図３３に示したような変換済みパススキーマ３３００が生成されることとなる（ステップＳ９０８）。【０２３３】
また、ステップＳ９０９のあと、変換済みパススキーマ３３００から変換済み部分パススキーマを抽出する（ステップＳ４３０２）。この場合、図３４、図３６または図３９に示したように、変換済み部分パススキーマ３４００，３６０２，３９００が抽出されることとなる。【０２３４】
したがって、ステップＳ９１０において、図３５，図３７，図４０または図４２に示したように、変換済みの階層検索オートマトン３５００，３７００，４０００，４２００を有する変換済み単一オートマトンが生成されることとなる（ステップＳ９１０）。【０２３５】
このように、実施の形態３では、パススキーマ内のパスごとにタグ記号および固有の識別子を割り当てることにより、階層検索オートマトンのノード数を削減することができる。【０２３６】
したがって、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。【０２３７】
以上説明したように、本実施の形態によれば、階層検索用オートマトンとキーワード検索用オートマトンとの間のオーバーヘッドの低減を図ることにより、検索速度の向上を図ることができる。【０２３８】
なお、本実施の形態で説明した情報検索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。【０２３９】
また、本実施の形態で説明した情報検索装置１００は、スタンダードセルやストラクチャードＡＳＩＣ(Application  Specific  Integrated  Circuit)などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ(Programmable Logic Device)によっても実現することができる。具体的には、たとえば、上述した情報検索装置１００の機能的構成（機能ブロックの各符号を入れる）をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、情報検索装置１００を製造することができる。
【産業上の利用可能性】
【０２４０】
以上のように、本発明にかかる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法は、階層構造を有する電子文書の検索に有用であり、特に、ＸＭＬ文書やＨＴＭＬ文書などに適している。
【図１】
2008117454.tif 000003
【図２】
2008117454.tif 000004
【図３】
2008117454.tif 000005
【図４】
2008117454.tif 000006
【図５】
2008117454.tif 000007
【図６】
2008117454.tif 000008
【図７】
2008117454.tif 000009
【図８】
2008117454.tif 000010
【図９】
2008117454.tif 000011
【図１０】
2008117454.tif 000012
【図１１】
2008117454.tif 000013
【図１２】
2008117454.tif 000014
【図１３】
2008117454.tif 000015
【図１４】
2008117454.tif 000016
【図１５】
2008117454.tif 000017
【図１６】
2008117454.tif 000018
【図１７】
2008117454.tif 000019
【図１８】
2008117454.tif 000020
【図１９】
2008117454.tif 000021
【図２０】
2008117454.tif 000022
【図２１】
2008117454.tif 000023
【図２２】
2008117454.tif 000024
【図２３】
2008117454.tif 000025
【図２４】
2008117454.tif 000026
【図２５】
2008117454.tif 000027
【図２６】
2008117454.tif 000028
【図２７】
2008117454.tif 000029
【図２８】
2008117454.tif 000030
【図２９】
2008117454.tif 000031
【図３０】
2008117454.tif 000032
【図３１】
2008117454.tif 000033
【図３２】
2008117454.tif 000034
【図３３】
2008117454.tif 000035
【図３４】
2008117454.tif 000036
【図３５】
2008117454.tif 000037
【図３６】
2008117454.tif 000038
【図３７】
2008117454.tif 000039
【図３８】
2008117454.tif 000040
【図３９】
2008117454.tif 000041
【図４０】
2008117454.tif 000042
【図４１】
2008117454.tif 000043
【図４２】
2008117454.tif 000044
【図４３】
2008117454.tif 000045
【手続補正書】
【提出日】平成21年5月22日(2009.5.22)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬ文書など階層構造を有する電子文書を検索する情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法に関するものである。
【背景技術】
【０００２】
近年、さまざまな分野で情報量が爆発的に増加している。ある分野においてはギガバイトオーダーからテラバイトオーダーになりつつあり、その莫大なデータから所望のデータを取り出すことが困難になりつつある。データは通常、管理のしやすさから階層構造を持たせて保存される。
【０００３】
たとえば、図書館で本を管理するには本という階層の下にタイトル、著者、出版社、出版日、貸し出し情報などといった階層を持たせることにより、ある本に対して、管理情報ごとに情報を引き出すことが可能となる。
【０００４】
階層構造を持つ膨大な電子文書から高速に所望のデータを取り出す場合、従来から、階層検索とキーワード検索とを別々のオートマトンを用いて実行している（たとえば、下記特許文献１を参照。）。
【０００５】
具体的には、階層検索オートマトンにおいて階層条件にヒットした場合にキーワード検索を実行するキーワード検索オートマトンで検索を実行し、逆にキーワード検索オートマトン実行中に階層をあらわす記号が出現した場合、再び階層検索オートマトンで階層条件を検索するという処理を繰り返し実行している。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−０７０９１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では、ＸＭＬ文書など階層をあらわす記号の出現頻度が高い電子文書を検索する場合、階層検索オートマトンを用いた検索処理とキーワード検索オートマトンを用いた検索処理との切り替え頻度が高くなり、オーバーヘッドが生じることとなる。したがって、全体として検索速度が低下してしまうという問題があった。
【０００８】
また、検索範囲を特定する複数の検索式を与えて同時に検索する場合に、すべての検索式を１つのオートマトンの中に生成するため、キーワードがヒットしたときに、現在の階層がそのヒットしたキーワードに対応する階層条件を満たしているかを判断する必要があった。したがって、高頻度でキーワードがヒットしてしまう場合、検索速度が低下してしまうという問題があった。
【０００９】
本発明は、上記に鑑みてなされたものであって、階層検索オートマトンとキーワード検索オートマトンとの間のオーバーヘッドの低減を図ることにより、検索速度の向上を図ることができる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、この発明の情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法は、検索対象となる階層構造を有する電子文書を取得し、取得された電子文書に関するパススキーマを生成し、任意の検索キーワードと当該検索キーワードの検索条件と前記検索キーワードの検索範囲を特定する検索式との入力を受け付け、生成されたパススキーマの階層を検索する階層検索オートマトンと、入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成し、生成された単一オートマトンを用いて、前記電子文書の中から、前記検索範囲内の前記ヒットキーワードを検索し、検索された検索結果を出力することを特徴とする。
【００１１】
また、上記発明において、前記階層検索オートマトンは、遷移元となる上位の階層ノードとその遷移先となる下位の階層ノードとの間に開始タグの開始記号をあらわすノードを有し、前記上位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することとしてもよい。
【００１２】
また、上記発明において、前記階層検索オートマトンは、前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。
【００１３】
また、上記発明において、前記パススキーマを構成する各階層ノードの階層名を固有の文字列に変換し、前記階層検索オートマトンを前記変換手段によって変換された固有の文字列を用いて構成することにより、前記単一オートマトンを生成し、前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名から変換された固有の文字列をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。
【００１４】
また、上記発明において、前記階層検索オートマトンは、ヒットミスする文字が出現した場合、前記上位の階層ノードに状態遷移することとしてもよい。
【００１５】
また、上記発明において、前記階層検索オートマトンは、前記一連のノード群の中の末尾ノードに状態遷移している場合に前記開始タグの終了記号が与えられると、前記下位の階層ノードに状態遷移することとしてもよい。
【００１６】
また、上記発明において、前記階層検索オートマトンは、遷移元となる下位の階層ノードとその遷移先となる上位の階層ノードとの間に終了タグの開始記号をあらわすノードを有し、前記下位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することとしてもよい。
【００１７】
また、上記発明において、前記階層検索オートマトンは、前記開始記号をあらわすノードと上位の階層ノードとの間に前記下位の階層ノードの階層名をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。
【００１８】
また、上記発明において、前記電子文書内の階層名を固有の文字列に変換し、前記階層検索オートマトンを前記変換手段によって変換された固有の文字列を用いて構成することにより、前記単一オートマトンを生成し、前記階層検索オートマトンは、前記開始記号をあらわすノードと上位の階層ノードとの間に前記下位の階層ノードの階層名から変換された固有の文字列をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することとしてもよい。
【００１９】
また、上記発明において、前記階層検索オートマトンは、ヒットミスする文字が出現した場合、前記下位の階層ノードに状態遷移することとしてもよい。
【００２０】
また、上記発明において、前記階層検索オートマトンは、前記一連のノード群の中の末尾ノードに状態遷移している場合に前記開始タグの終了記号が与えられると、前記上位の階層ノードに状態遷移することとしてもよい。
【００２１】
また、上記発明において、前記単一オートマトンは、前記階層検索オートマトン内のヒット階層ノードに状態遷移している場合に前記ヒットキーワードの先頭文字が与えられると、前記キーワード検索オートマトン内の前記先頭文字に対応するノードに状態遷移することとしてもよい。
【００２２】
また、上記発明において、前記単一オートマトンは、前記キーワード検索オートマトン内のいずれかのノードに状態遷移している場合にヒットミスする文字が与えられると、前記ヒット階層ノードに状態遷移することとしてもよい。
【００２３】
また、上記発明において、前記パススキーマの中から、前記入力手段によって入力された検索式により特定される検索範囲に関する部分パススキーマを抽出し、抽出された部分パススキーマの階層を検索する階層検索オートマトンと、前記ヒットキーワードを検索するキーワード検索オートマトンとからなり、前記単一オートマトンを生成することとしてもよい。
【００２４】
また、上記発明において、前記検索式により特定されるパスが前記パススキーマ内に複数通り存在するか否かを判断し、判断された判断結果に基づいて、前記部分パススキーマを抽出することとしてもよい。
【００２５】
また、上記発明において、複数通り存在しないと判断された場合、前記パススキーマからルートノードと前記ヒット階層ノードとその子階層ノードとからなる部分パススキーマを抽出することとしてもよい。
【００２６】
また、上記発明において、複数通り存在すると判断された場合、さらに、前記複数通りのパスがどの配列パターンに該当するかを判断し、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する配列パターンと判断された場合、ルートノードと、前記他の階層ノードと前記ヒット階層ノードとの間にのみ存在する中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００２７】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する配列パターンと判断された場合、ルートノードと、前記他の階層ノードと前記ヒット階層ノードとの間に存在する中間階層ノードと、前記ルートノードと前記他の階層ノードとの間に存在する前記中間階層ノードと同一階層名の他の中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００２８】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも下位階層に存在する配列パターンと判断された場合、ルートノードと、前記ヒット階層ノードと、当該ヒット階層ノードと前記他の階層ノードとの間に存在する子階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００２９】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記ヒット階層ノードとの間にのみ存在する中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３０】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在しかつ前記分岐元の階層ノードと前記他の階層ノードとの間に存在しない中間階層ノードと、前記ルートノードと前記分岐元の階層ノードとの間に存在する前記中間階層ノードと同一階層名の他の中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３１】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記ヒット階層ノードと、前記分岐元の階層ノードと前記他の階層ノードとの間にのみ存在する分岐先の階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３２】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記他の階層ノードとの間に存在しかつ前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在しない中間階層ノードと、前記ルートノードと前記分岐元の階層ノードとの間に存在する前記中間階層ノードと同一階層名の他の中間階層ノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３３】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在すると判断された場合、ルートノードと、当該ルートノードと前記分岐元の階層ノードとの間に存在せずかつ前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在する第１の中間階層ノードと、前記ルートノードと前記第１の中間階層ノードとの間に存在せずかつ前記分岐元の階層ノードと前記第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３４】
また、上記発明において、前記ヒット階層ノードと同一階層名となる他の階層ノードが前記ヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンと判断された場合、ルートノードと、前記分岐元の階層ノードと前記ヒット階層ノードとの間に存在する第１の中間階層ノードと、前記分岐元の階層ノードと前記第１の中間階層ノードとの間に存在せずかつ前記分岐元の階層ノードと前記第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３５】
また、上記発明において、前記検索式に、前記ヒット階層ノードおよびその下位のすべての階層ノードを指定するワイルドカードが用いられている場合、ルートノードと、前記ヒット階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３６】
また、上記発明において、前記検索式に、任意の階層名を有するすべての階層ノードを指定するワイルドカードが用いられている場合、ルートノードと、前記階層名を有する階層ノードと、当該階層ノードの子階層ノードと、からなる部分パススキーマを抽出することとしてもよい。
【００３７】
また、上記発明において、ワイルドカードが用いられている検索式が複数存在する場合、前記検索式ごとに特定されるヒット階層ノードの論理和を取ることにより、部分パススキーマを抽出することとしてもよい。
【００３８】
また、上記発明において、前記部分パススキーマ内に階層名が同一のヒット階層ノードが共通の階層ノードから分岐されている場合、子階層ノードを有するヒット階層ノードに縮退させることにより、縮退済みの部分パススキーマを抽出することとしてもよい。
【００３９】
また、上記発明において、前記電子文書の各階層をあらわす開始タグを、階層開始指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる開始タグに変換するとともに、前記電子文書の各階層をあらわす終了タグを、階層終了指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる終了タグに変換し、変換後の電子文書に関するパススキーマを生成することとしてもよい。
【００４０】
また、上記発明において、生成された前記変換後の電子文書に関するパススキーマの中から、ルートノードと前記検索式により指定されたヒット階層ノードとからなる部分パススキーマを抽出し、前記階層検索オートマトンを前記部分パススキーマおよび当該部分パススキーマに用いられる前記階層指示子および前記固有の識別子を用いて構成することにより、前記単一オートマトンを生成することとしてもよい。
【００４１】
また、上記発明において、前記階層検索オートマトンは、前記ルートノードと前記ヒット階層ノードとの間に、前記階層開始指示子をあらわすノードを有し、当該階層開始指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードに関する固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記ヒット階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。
【００４２】
また、上記発明において、前記階層検索オートマトンは、前記ルートノードと前記ヒット階層ノードとの間に、前記階層終了指示子をあらわすノードを有し、当該階層終了指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードの子階層ノードに関する固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記子階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。
【００４３】
また、上記発明において、前記部分パススキーマが前記ルートノードから複数のヒット階層ノードへ分岐している場合、前記各ヒット階層ノードの固有の識別子をまとめることにより、前記ルートノードと前記固有の識別子がまとめられた単一のヒット階層ノードとからなる縮退済み部分パススキーマを抽出し、前記階層検索オートマトンを前記縮退済み部分パススキーマおよび当該縮退済み部分パススキーマに用いられる前記階層指示子および前記固有の識別子を用いて構成することにより、前記単一オートマトンを生成し、前記階層検索オートマトンは、前記ルートノードと前記ヒット階層ノードとの間に、前記階層開始指示子をあらわすノードを有し、当該階層開始指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードに関するいずれかの固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記ヒット階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。
【００４４】
また、上記発明において、前記検索式が複数存在する場合、前記パススキーマ生成手段によって生成された変換後の電子文書に関するパススキーマの中から、ルートノードと前記検索式により指定されたヒット階層ノードの論理和とからなる部分パススキーマを抽出し、前記階層検索オートマトンを、前記部分パススキーマのうち前記検索式により指定されたヒット階層ノードの中から選ばれた前記検索式ごとの代表ノードと、前記各検索式の論理積により指定されたヒット階層ノードの中から選ばれた代表ノードと、前記部分パススキーマに用いられる前記階層指示子および前記固有の識別子と、を用いて構成することにより、前記単一オートマトンを生成することとしてもよい。
【００４５】
また、上記発明において、前記電子文書の各階層をあらわす開始タグを、階層開始指示子と前記パススキーマを構成するパスごとに割り振られた固有の識別子とからなる開始タグに変換するとともに、前記電子文書の各階層をあらわす終了タグを、前記階層開始指示子と当該終了タグに対応する開始タグの階層名により特定される階層ノードの親ノードを末端とするパスに割り振られた固有の識別子とからなる開始タグに変換し、変換後の電子文書に関するパススキーマを生成することとしてもよい。
【００４６】
また、上記発明において、生成された前記変換後の電子文書に関するパススキーマの中から、ルートノードと前記検索式により指定されたヒット階層ノードとからなる部分パススキーマを抽出し、前記階層検索オートマトンを前記部分パススキーマおよび当該部分パススキーマに用いられる前記階層指示子および前記固有の識別子を用いて構成することにより、前記単一オートマトンを生成することとしてもよい。
【００４７】
また、上記発明において、前記階層検索オートマトンは、ルートノードと前記ヒット階層ノードとの間に、前記階層開始指示子をあらわすノードを有し、当該階層開始指示子をあらわすノードに状態遷移している場合に前記ヒット階層ノードに関する固有の識別子が与えられると、前記ヒット階層ノードに状態遷移し、前記ヒット階層ノード以外の他の階層ノードに関する固有の識別子が与えられると、前記ルートノードに状態遷移することとしてもよい。
【００４８】
また、上記発明において、前記階層検索オートマトンは、前記ヒット階層ノードに状態遷移している場合に前記階層開始指示子が与えられると、当該階層開始指示子をあらわすノードに状態遷移し、前記階層開始指示子以外のデータが与えられると、前記ヒット階層ノードに状態遷移することとしてもよい。
【００４９】
これらの発明によれば、階層検索オートマトンのノード数を削減することができる。また、階層検索オートマトンとキーワード検索オートマトン間の切り替え回数の低減化を図ることができる。
【発明の効果】
【００５０】
本発明にかかる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法は、階層検索用オートマトンとキーワード検索用オートマトンとの間のオーバーヘッドの低減を図ることにより、検索速度の向上を図ることができるという効果を奏する。
【図面の簡単な説明】
【００５１】
【図１】この発明の実施の形態１にかかる情報検索装置のハードウェア構成を示す説明図である。
【図２】この発明の実施の形態１にかかる検索対象となる電子文書を示す説明図である。
【図３】この発明の実施の形態１にかかるパススキーマを示す説明図である。
【図４】図１に示した情報検索装置の機能的構成を示すブロック図である。
【図５】この発明の実施の形態１にかかる単一オートマトンを示す説明図である。
【図６】変換テーブルを示す説明図である。
【図７】変換後のＸＭＬ文書を示す説明図である。
【図８】変換済み単一オートマトンを示す説明図である。
【図９】この発明の実施の形態にかかる情報検索処理手順を示すフローチャートである。
【図１０】この発明の実施の形態２にかかる検索対象となる電子文書の一例を示す説明図である。
【図１１】この発明の実施の形態２にかかるパススキーマを示す説明図である。
【図１２】部分パススキーマの抽出例（その１）を示す説明図である。
【図１３】図１２に示した部分パススキーマにより階層検索オートマトンを構成した場合の単一オートマトンを示す説明図である。
【図１４】部分パススキーマの抽出例（その２）を示す説明図である。
【図１５】図１４に示した部分パススキーマにより階層検索オートマトンを構成した場合の単一オートマトンを示す説明図である。
【図１６】この発明の実施の形態２にかかる情報検索装置の機能的構成を示すブロック図である。
【図１７】配列パターンＡを示す説明図である。
【図１８】配列パターンＢを示す説明図である。
【図１９】配列パターンＣが適用されるパススキーマを示す説明図である。
【図２０】抽出パターンＣ−１により抽出された部分パススキーマを示す説明図である。
【図２１】抽出パターンＣ−２により抽出された部分パススキーマを示す説明図である。
【図２２】抽出パターンＣ−３により抽出された部分パススキーマを示す説明図である。
【図２３】抽出パターンＣ−４により抽出された部分パススキーマを示す説明図である。
【図２４】抽出パターンＣ−５により抽出された部分パススキーマを示す説明図である。
【図２５】抽出パターンＣ−６により抽出された部分パススキーマを示す説明図である。
【図２６】この発明の実施の形態２にかかる情報検索処理手順を示すフローチャートである。
【図２７】抽出処理（ステップＳ２６０１，Ｓ２６０２）の詳細な処理手順を示すフローチャートである。
【図２８】部分パススキーマの抽出例（その３）を示す説明図である。
【図２９】部分パススキーマの抽出例（その４）を示す説明図である。
【図３０】部分パススキーマの抽出例（その５）を示す説明図である。
【図３１】パスＩＤテーブルを示す説明図である。
【図３２】パスＩＤへの変換例（その１）を示す説明図である。
【図３３】変換済みパススキーマを示す説明図である。
【図３４】部分パススキーマの抽出例（その６）を示す説明図である。
【図３５】変換済み部分パススキーマから得られる階層検索オートマトンを示す説明図である。
【図３６】部分パススキーマの抽出例（その７）を示す説明図である。
【図３７】変換済み部分パススキーマから得られる階層検索オートマトンを示す説明図である。
【図３８】複数検索式の変換例を示す説明図である。
【図３９】部分パススキーマの抽出例（その８）を示す説明図である。
【図４０】変換済み部分パススキーマから得られる階層検索オートマトンを示す説明図である。
【図４１】パスＩＤへの変換例（その２）を示す説明図である。
【図４２】第４の例の階層検索オートマトンを示す説明図である。
【図４３】この発明の実施の形態３にかかる情報検索処理手順を示すフローチャートである。
【発明を実施するための形態】
【００５２】
以下に添付図面を参照して、この発明にかかる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法の好適な実施の形態を詳細に説明する。
【００５３】
＜実施の形態１＞
（情報検索装置のハードウェア構成）
まず、この発明の実施の形態１にかかる情報検索装置のハードウェア構成について説明する。図１は、この発明の実施の形態１にかかる情報検索装置のハードウェア構成を示す説明図である。
【００５４】
図１において、情報検索装置１００は、コンピュータ本体１１０と、入力装置１２０と、出力装置１３０と、から構成されており、不図示のルータやモデムを介してＬＡＮ，ＷＡＮやインターネットなどのネットワーク１４０に接続可能である。
【００５５】
コンピュータ本体１１０は、ＣＰＵ，メモリ，インターフェースを有する。ＣＰＵは、情報検索装置１００の全体の制御を司る。メモリは、ＲＯＭ，ＲＡＭ，ＨＤ，光ディスク１１１，フラッシュメモリから構成される。メモリはＣＰＵのワークエリアとして使用される。
【００５６】
また、メモリには各種プログラムが格納されており、ＣＰＵからの命令に応じてロードされる。ＨＤおよび光ディスク１１１はディスクドライブによりデータのリード／ライトが制御される。また、光ディスク１１１およびフラッシュメモリはコンピュータ本体１１０に対し着脱自在である。インターフェースは、入力装置１２０からの入力、出力装置１３０への出力、ネットワーク１４０に対する送受信の制御をおこなう。
【００５７】
また、入力装置１２０としては、キーボード１２１、マウス１２２、スキャナ１２３などがある。キーボード１２１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式であってもよい。マウス１２２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。スキャナ１２３は、画像を光学的に読み取る。読み取られた画像は画像データとして取り込まれ、コンピュータ本体１１０内のメモリに格納される。なお、スキャナ１２３にＯＣＲ機能を持たせてもよい。
【００５８】
また、出力装置１３０としては、ディスプレイ１３１、プリンタ１３２、スピーカ１３３などがある。ディスプレイ１３１は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。また、プリンタ１３２は、画像データや文書データを印刷する。またスピーカ１３３は、効果音や読み上げ音などの音声を出力する。
【００５９】
（電子文書の一例）
つぎに、この発明の実施の形態１にかかる検索対象となる電子文書について説明する。図２は、この発明の実施の形態１にかかる検索対象となる電子文書を示す説明図である。
【００６０】
階層構造を有する電子文書としてＸＭＬ文書２００がある。ＸＭＬ文書２００には、タグが埋め込まれており、このタグにより階層を表現する。タグは、開始タグと終了タグの２種類のタグがある。
【００６１】
本明細書では、タグを構成する記号をタグ記号と呼び、特に、『<』を開始タグのタグ開始記号、『</』を終了タグのタグ開始記号、『>』を開始タグおよび終了タグのタグ終了記号と呼ぶ。また、タグ開始記号とタグ終了記号との間に括られている文字列を階層名と呼ぶ。
【００６２】
（パススキーマの一例）
つぎに、この発明の実施の形態１にかかるパススキーマについて説明する。パススキーマとは、検索対象となるＸＭＬ文書２００中に存在するルートノードからのすべてのパスを抽出し、重複するパスを１本にまとめたパスツリーである。パスツリーのノードはＸＭＬ文書２００の階層をあらわしている。以降、パスツリーのノードを階層ノードと呼ぶ。
【００６３】
図３は、この発明の実施の形態１にかかるパススキーマを示す説明図である。図３に示したパススキーマ３００は、図２に示したＸＭＬ文書２００に関するパススキーマである。図３において、階層ノードＮ０はルートノードである。階層ノードＮ１はsyainをあらわすノードである。階層ノードＮ２はACTをあらわすノードである。階層ノードＮ３はcharaをあらわすノードである。階層ノードＮ６はnameをあらわすノードである。
【００６４】
（情報検索装置の機能的構成）
つぎに、図１に示した情報検索装置１００の機能的構成について説明する。図４は、図１に示した情報検索装置１００の機能的構成を示すブロック図である。図４において、情報検索装置１００は、取得部４０１と、パススキーマ生成部４０２と、入力部４０３と、オートマトン生成部４０４と、検索部４０５と、出力部４０６と、変換部４０７と、を備えている。
【００６５】
なお、これら各機能４０１〜４０７は、情報検索装置１００内のメモリに格納された当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。
【００６６】
また、各機能からの出力データはメモリに保持される。また、図４中矢印で示した接続先の機能は、接続元の機能からの出力データをメモリから読み込んで、当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させる。
【００６７】
まず、取得部４０１は、検索対象となる階層構造を有する電子文書を取得する機能を有する。具体的には、たとえば、ＸＭＬ文書２００を読み込んだり、キーボード１２１を操作することで作成されたＸＭＬ文書２００を取り込む。
【００６８】
また、パススキーマ生成部４０２は、取得部４０１によって取得された電子文書に関するパススキーマを生成する機能を有する。具体的には、たとえば、ＸＭＬ文書２００を取得した場合、ＸＭＬパーサを用いてＸＭＬ文書２００の構造を解析する。ＸＭＬパーサとしては、たとえば、ＤＯＭやＳＡＸ、または下記文献（１）に示されているＸＭＬ走査器を用いることができる。これにより、図３に示したようなパススキーマを生成する。
【００６９】
石野明、武田正幸  著、「パスプルーニングによる決定性有限オートマトンを用いたＸＱｕｅｒｙ処理の提案」、DBSJ Letters,Vol. 4, No. 4, pp. 17-20,2006.
http://www.dbsj.org/Japanese/DBSJLetters/vol4/no4/ishino.pdf
【００７０】
また、入力部４０３は、任意の検索キーワードと当該検索キーワードの検索条件と検索式との入力を受け付ける機能を有する。検索キーワードとは、ユーザが電子文書の中からユーザが拾いたいキーワードであり、文字や数字などの文字列により構成される。
【００７１】
検索条件とは、検索キーワードに対して与えられる条件である。単なるキーワード検索である場合、完全一致、前方一致、部分一致、後方一致、類似語などが検索条件となる。一方、数値範囲検索である場合、入力された数値の数値範囲（以上、以下など）が検索条件となる。
【００７２】
また、検索式とは、検索キーワードの検索範囲を特定する質問式である。検索キーワードは電子文書の中の検索範囲から検索されることとなる。また、検索範囲は、パススキーマ内のパスにより特定される。ここでは、検索範囲は、階層をあらわす要素名を記号「/」を介して羅列した検索式により表現することとする。
【００７３】
ここで、検索式の一例を示す。
/syain/ACT/chara/name = “ブルー”・・・（１）
【００７４】
上記検索式（１）の左辺は、階層ノードＮ０を始点として、syainをあらわす階層ノードＮ１、ACTをあらわす階層ノードＮ２、およびcharaをあらわす階層ノードＮ３を経由し、nameをあらわす階層ノードＮ６に到達するパスを表現している。この階層ノードＮ３を親ノードとする階層ノードＮ６の階層が検索範囲となる。一方、右辺は検索キーワードをあらわしている。
【００７５】
したがって、左辺で示された検索範囲の中から右辺で示された検索キーワードを検索することとなる。なお、検索範囲の階層ノードを「ヒット階層ノード」と称す。たとえば、上記検索式（１）の例では、階層ノードＮ３を親ノードとする階層ノードＮ６がヒット階層ノードとなる。また、検索範囲内において検索条件を満たすことにより検索キーワードに一致または関連することとなったキーワードを、「ヒットキーワード」と称す。上記検索式（１）の例では、「ブルー」がヒットキーワードとなる。
【００７６】
また、図４において、オートマトン生成部４０４は、階層検索オートマトンとキーワード検索オートマトンとを連結した単一オートマトンを生成する機能を有する。階層検索オートマトンとは、パススキーマ３００の階層を検索するオートマトンであり、パススキーマ３００を構成する階層ノードをそのままノードとして構成している。すなわち、階層検索オートマトンは、ＸＭＬ文書２００の走査位置がパススキーマ３００内のどの階層ノードに遷移しているかを判定するオートマトンである。
【００７７】
また、キーワード検索オートマトンは、検索条件を満たすヒットキーワードを検索するオートマトンである。具体的には、たとえば、ヒットキーワードの文字順に遷移する文字ごとのノードにより構成されている。すなわち、階層検索オートマトンは、ＸＭＬ文書２００の走査位置がヒットキーワードのどの文字のノードに遷移しているかを判定するオートマトンである。
【００７８】
本実施の形態１では、階層検索オートマトンとキーワード検索オートマトンとを別々に扱うのではなく、階層検索オートマトンのヒット階層ノードとキーワード検索オートマトンのヒットキーワードのノード集合との間で状態遷移するように、ヒット階層ノードとヒットキーワードのノード集合とを遷移枝で連結することで、単一オートマトンを構成している。したがって、ＸＭＬ文書２００の走査位置が階層検索オートマトンのヒット階層ノードに状態遷移したときに限り、キーワード検索オートマトンによる状態遷移をおこなう。
【００７９】
図５は、この発明の実施の形態１にかかる単一オートマトンを示す説明図である。この単一オートマトン５００は、上記検索式（１）が与えられた場合のオートマトンである。図５において、階層ノードＮ０は初期状態をあらわす。階層検索オートマトン５０１の上半部は、上位の階層ノードから下位の階層ノードへの状態遷移をあらわしており、下半部は、下位の階層ノードから上位の階層ノードへの状態遷移をあらわしている。
【００８０】
まず、上半部の状態遷移について説明する。階層検索オートマトン５０１は、遷移元となる上位の階層ノードとその遷移先となる下位の階層ノードとの間に開始タグのタグ開始記号『<』をあらわすノードを有する。
【００８１】
たとえば、上位の階層ノードＮ０とその下位の階層ノードＮ１との間、上位の階層ノードＮ１とその下位の階層ノードＮ２との間、上位の階層ノードＮ２とその下位の階層ノードＮ３との間、上位の階層ノードＮ３とその下位の階層ノードＮ６との間に、開始タグのタグ開始記号『<』をあらわすノードを有する。そして、上位の階層ノードに状態遷移している場合にタグ開始記号『<』が与えられると、タグ開始記号『<』をあらわすノードに状態遷移する。
【００８２】
また、上位の階層ノードに状態遷移している場合にタグ開始記号『<』以外の文字が与えられると、当該上位の階層ノードに状態遷移する。たとえば、階層ノードＮ０に状態遷移している場合にタグ開始記号『<』以外の文字が与えられると、当該上位の階層ノードＮ０に状態遷移する。
【００８３】
また、タグ開始記号『<』をあらわすノードと下位の階層ノードとの間に、下位の階層ノードの階層名をあらわす一連のノード群を有する。たとえば、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ１との間には、階層名の文字『s』、『y』、『a』、『i』、『n』をあらわす一連のノード群を有する。
【００８４】
また、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ２との間には、階層名の文字『A』、『C』、『T』をあらわす一連のノード群を有する。また、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ３との間には、階層名の文字『c』、『h』、『a』、『r』、『a』をあらわす一連のノード群を有する。
【００８５】
また、タグ開始記号『<』をあらわすノードと下位の階層ノードＮ６との間には、階層名の文字『n』、『a』、『m』、『e』をあらわす一連のノード群を有する。そして、タグ開始記号『<』をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで一連のノード群に対し状態遷移する。
【００８６】
たとえば、階層ノードＮ０からタグ開始記号『<』をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が文字「s」であるとすると、タグ開始記号『<』をあらわすノードから文字『s』をあらわすノードに状態遷移する。つぎの走査位置が文字「y」であるとすると、文字『s』をあらわすノードから文字『y』をあらわすノードに状態遷移する。このあとも、ヒットミスする文字が走査位置に出現するまで状態遷移を続ける。
【００８７】
そして、階層名の末尾文字をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字をあらわすノードの末尾文字をあらわすノードから下位の階層ノードに状態遷移する。
【００８８】
たとえば、上位の階層ノードＮ０から階層名syainの末尾文字『n』に状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字『n』をあらわすノードの末尾文字をあらわすノードから下位の階層ノードＮ１に状態遷移する。他の末尾文字『T』、『a』、『e』についても、それぞれ下位の階層ノードＮ２、Ｎ３、Ｎ６に状態遷移する。
【００８９】
また、上位の階層ノードと下位の階層ノードとの間のノードに状態遷移している場合、ヒットミスする文字が走査位置に出現すると、上位の階層ノードに状態遷移する。たとえば、上位の階層ノードＮ０と下位の階層ノードＮ１との間の文字『s』をあらわすノードに状態遷移している場合、文字『y』以外のヒットミスする文字が走査位置に出現すると、上位の階層ノードＮ１に状態遷移する。
【００９０】
つぎに、下半部の状態遷移について説明する。階層検索オートマトン５０１は、遷移元となる下位の階層ノードとその遷移先となる上位の階層ノードとの間に終了タグのタグ開始記号『</』をあらわすノードを有する。
【００９１】
たとえば、下位の階層ノードＮ６とその上位の階層ノードＮ３との間、下位の階層ノードＮ３とその上位の階層ノードＮ２との間、下位の階層ノードＮ２とその上位の階層ノードＮ１との間、下位の階層ノードＮ１とその上位の階層ノードＮ０との間に、終了タグのタグ開始記号『</』をあらわすノードを有する。そして、下位の階層ノードに状態遷移している場合にタグ開始記号『</』が与えられると、タグ開始記号『</』をあらわすノードに状態遷移する。
【００９２】
また、下位の階層ノードに状態遷移している場合にタグ開始記号『</』以外の文字が与えられると、当該下位の階層ノードに状態遷移する。たとえば、階層ノードＮ６に状態遷移している場合にタグ開始記号『</』以外の文字が与えられると、当該上位の階層ノードＮ６に状態遷移する。
【００９３】
また、タグ開始記号『</』をあらわすノードと上位の階層ノードとの間に、下位の階層ノードの階層名をあらわす一連のノード群を有する。たとえば、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ３との間には、階層名の文字『n』、『a』、『m』、『e』をあらわす一連のノード群を有する。
【００９４】
また、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ２との間には、階層名の文字『c』、『h』、『a』、『r』、『a』をあらわす一連のノード群を有する。また、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ１との間には、階層名の文字『A』、『C』、『T』をあらわす一連のノード群を有する。
【００９５】
また、タグ開始記号『</』をあらわすノードと下位の階層ノードＮ０との間には、階層名の文字『s』、『y』、『a』、『i』、『n』をあらわす一連のノード群を有する。そして、タグ開始記号『</』をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで一連のノード群に対し状態遷移する。
【００９６】
たとえば、階層ノードＮ６からタグ開始記号『</』をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が文字『n』であるとすると、タグ開始記号『</』をあらわすノードから文字『n』をあらわすノードに状態遷移する。つぎの走査位置が文字『a』であるとすると、文字『n』をあらわすノードから文字『a』をあらわすノードに状態遷移する。このあとも、ヒットミスする文字が走査位置に出現するまで状態遷移を続ける。
【００９７】
そして、階層名の末尾文字をあらわすノードに状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字をあらわすノードの末尾文字をあらわすノードから下位の階層ノードに状態遷移する。
【００９８】
たとえば、上位の階層ノードＮ６から階層名nameの末尾文字『n』に状態遷移している場合、ＸＭＬ文書２００の走査位置が記号『>』であるとすると、階層名の末尾文字『n』をあらわすノードの末尾文字をあらわすノードから下位の階層ノードＮ３に状態遷移する。他の末尾文字『a』、『T』、『n』についても、それぞれ下位の階層ノードＮ２、Ｎ１、Ｎ０に状態遷移する。
【００９９】
また、下位の階層ノードと上位の階層ノードとの間のノードに状態遷移している場合、ヒットミスする文字が走査位置に出現すると、下位の階層ノードに状態遷移する。たとえば、下位の階層ノードＮ６と上位の階層ノードＮ３との間の文字『n』をあらわすノードに状態遷移している場合、文字『n』以外のヒットミスする文字が走査位置に出現すると、上位の階層ノードＮ６に状態遷移する。
【０１００】
つぎに、キーワード検索オートマトン５０２について説明する。キーワード検索オートマトン５０２は、ヒットキーワードを文字順に状態遷移する一連のノード群である。図５に示したように、ヒットキーワードが、検索キーワードと同一の「ブルー」である場合、『ブ』、『ル』、『ー』をあらわすノード群がその文字順に状態遷移するように連結されている。
【０１０１】
階層検索オートマトン５０１とキーワード検索オートマトン５０２とは状態遷移するように連結されている。具体的には、階層検索オートマトン５０１内のヒット階層ノードに状態遷移している場合にヒットキーワードの先頭文字が与えられると、キーワード検索オートマトン５０２内の先頭文字をあらわすノードに状態遷移する。たとえば、ヒット階層ノードＮ６に状態遷移している場合にヒットキーワード「ブルー」の先頭文字『ブ』が与えられると、キーワード検索オートマトン５０２内の先頭文字『ブ』をあらわすノードに状態遷移する。
【０１０２】
また、キーワード検索オートマトン５０２内のいずれかのノードに状態遷移している場合にヒットミスする文字が与えられると、ヒット階層ノードに状態遷移する。たとえば、先頭文字『ブ』をあらわすノードに状態遷移している場合に遷移先のノードをあらわす文字『ル』以外のヒットミスする文字が走査位置に出現すると、ヒット階層ノードＮ６に状態遷移する。
【０１０３】
また、ヒットキーワードにヒットした場合もヒット階層ノードに状態遷移することで、ＸＭＬ文書２００の走査を継続することができる。たとえば、文字『ー』をあらわすノードに状態遷移すると、ヒットキーワードにマッチすることになるが、このとき、ヒット階層ノードＮ６に状態遷移する。
【０１０４】
このように、ＸＭＬ文書２００の走査位置が階層検索オートマトン５０１のヒット階層ノードに状態遷移したときに限り、キーワード検索オートマトン５０２に状態遷移するため、階層検索オートマトン５０１とキーワード検索オートマトン５０２との間の処理の切り替え頻度の低減化を図ることができる。
【０１０５】
同様に、ヒットキーワードにマッチしないと、ただちにヒット階層ノードに状態遷移するため、ヒット階層ノードにより特定される検査範囲内の文字列のみを集中的に検索することができる。
【０１０６】
また、図４において、検索部４０５は、単一オートマトン５００を用いて、電子文書の中から、検索範囲内のヒットキーワードを検索する機能を有する。具体的には、ＸＭＬ文書２００を走査し、その走査位置がどの階層であるかを階層検索オートマトン５０１により判定する。そして、ヒット階層ノードに状態遷移した場合、ＸＭＬ文書２００の走査位置がヒットキーワードのどの文字であるかをキーワード検索オートマトン５０２により判定する。
【０１０７】
出力部４０６は、キーワード検索オートマトン５０２においてヒットキーワードにマッチした場合、そのマッチした文字列を検索結果として出力する機能を有する。この出力処理には、ディスプレイ１３１による画面表示やプリンタ１３２による印刷出力、音声による読み上げ、半導体メモリやＨＤへの格納、他のコンピュータ装置への送信などがある。
【０１０８】
また、変換部４０７は、パススキーマ３００を構成する各階層ノードの階層名を文字数の少ない固有の文字列に変換する機能を有する。具体的には、取得部４０１により取得された電子文書内の階層名を固有の文字列に変換しておくことで、パススキーマ生成部４０２により生成されるパススキーマも固有の文字列を用いたパスツリーとなる。
【０１０９】
ここで、固有の文字列とは、階層名よりも文字数が少なければよく、１文字にするのが最適である。ここでは、階層名ごとに１文字分の固有数字を割り当てることにより、変換処理を実現する。
【０１１０】
図６は、変換テーブルを示す説明図である。この変換テーブル６００を用いることにより、階層名を個有数字に変換することができる。図７は、変換後のＸＭＬ文書を示す説明図である。図７のＸＭＬ文書７００は、図２に示したＸＭＬ文書２００を変換テーブル６００を用いて変換したＸＭＬ文書である。
【０１１１】
図８は、変換済み単一オートマトンを示す説明図である。図８の変換済み単一オートマトン８００は、図５と同様、上記検索式（１）が与えられた場合のオートマトンであるが、階層名が固有数字に置き換えられた階層検索オートマトン８０１となっている。すなわち、遷移元の階層ノードと遷移先の階層ノードとの間のノードがタグ開始記号をあらわすノードと固有数字をあらわすノードのみとなっているため、状態遷移回数の低減化を図ることができ、検索速度の高速化を図ることができる。
【０１１２】
（情報検索処理手順）
つぎに、この発明の実施の形態にかかる情報検索処理手順について説明する。図９は、この発明の実施の形態にかかる情報検索処理手順を示すフローチャートである。図９において、まず、取得部４０１により階層構造を有する電子文書（ＸＭＬ文書２００）を取得する（ステップＳ９０１）。
【０１１３】
そして、変換部４０７による変換処理をおこなうか否かを判断する（ステップＳ９０２）。変換しないと判断された場合（ステップＳ９０２：Ｎｏ）、パススキーマ生成部４０２によりパススキーマ３００を生成する（ステップＳ９０３）。つぎに、検索キーワードとその検索条件と検索式とが入力されるのを待ち受ける（ステップＳ９０４：Ｎｏ）。
【０１１４】
検索キーワードとその検索条件と検索式とが入力された場合（ステップＳ９０４：Ｙｅｓ）、オートマトン生成部４０４により単一オートマトン５００を生成し（ステップＳ９０５）、この単一オートマトン５００を用いて検索をおこなう（ステップＳ９０６）。このあと、ステップＳ９１２に移行する。
【０１１５】
一方、ステップＳ９０２において、変換すると判断された場合（ステップＳ９０２：Ｙｅｓ）、電子文書（ＸＭＬ文書２００）内の階層名を変換テーブル６００にしたがって変換する（ステップＳ９０７）。そして、パススキーマ生成部４０２により変換済みパススキーマを生成する（ステップＳ９０８）。つぎに、検索キーワードとその検索条件と検索式とが入力されるのを待ち受ける（ステップＳ９０９：Ｎｏ）。
【０１１６】
検索キーワードとその検索条件と検索式とが入力された場合（ステップＳ９０９：Ｙｅｓ）、オートマトン生成部４０４により変換済み単一オートマトン８００を生成し（ステップＳ９１０）、この変換済み単一オートマトン８００を用いて検索をおこなう（ステップＳ９１１）。このあと、ステップＳ９１２に移行する。最後に、出力部４０６により検索結果を出力する（ステップＳ９１２）ことにより、一連の処理を終了する。
【０１１７】
このように、実施の形態１によれば、階層検索オートマトン５０１（８０１）とキーワード検索オートマトン５０２との間の処理の切り替え頻度の低減化を図ることができる。また、ヒットキーワードにマッチしないと、ただちにヒット階層ノードに状態遷移するため、ヒット階層ノードにより特定される検査範囲内の文字列のみを集中的に検索することができる。またこれにより、ハードウェア化が容易となる。
【０１１８】
＜実施の形態２＞
つぎに、実施の形態２について説明する。実施の形態１では、パススキーマから得られるパスをすべてオートマトンで表現しているが、実施の形態２は、ルートノードからヒット階層ノードに一意に到達することができるパスツリーとなる部分パススキーマをパススキーマから抽出する。これにより、生成される単一オートマトン内の階層検索オートマトンのサイズを縮小することができる。
【０１１９】
なお、実施の形態１で示した構成と同一構成については同一符号を付し、その説明を省略する。また、説明を簡略化するため、特に断りがない限り、変換テーブル６００を用いた場合と用いない場合とを区別せずに説明する。
【０１２０】
（電子文書の一例）
つぎに、この発明の実施の形態２にかかる検索対象となる電子文書について説明する。図１０は、この発明の実施の形態２にかかる検索対象となる電子文書の一例を示す説明図である。ＸＭＬ文書１０００は、検索対象となる電子文書である。
【０１２１】
（パススキーマの一例）
つぎに、この発明の実施の形態２にかかるパススキーマについて説明する。図１１は、この発明の実施の形態２にかかるパススキーマを示す説明図である。図１１に示したパススキーマ１１００は、図１０に示したＸＭＬ文書１０００に関するパススキーマである。
【０１２２】
図１１のパススキーマ１１００において、階層ノードＮ０はルートノードである。階層ノードＮ１は階層名syainをあらわすノードである。階層ノードＮ２は階層名ACTをあらわすノードである。階層ノードＮ３は階層名charaをあらわすノードである。階層ノードＮ４は階層名nickをあらわすノードである。階層ノードＮ５は階層名castをあらわすノードである。階層ノードＮ７は階層名IDをあらわすノードである。
【０１２３】
なお、階層名nameをあらわす同一の階層ノードＮ６は３つあるが、説明上それぞれを区別するために、階層ノードＮ４の子階層ノードを階層ノードＮ６ａ、階層ノードＮ３の子階層ノードを階層ノードＮ６ｂ、階層ノードＮ５の子階層ノードを階層ノードＮ６ｃとする。つぎに、部分パススキーマの抽出例について説明する。
【０１２４】
（部分パススキーマの抽出例）
図１２は、部分パススキーマの抽出例（その１）を示す説明図である。図１２において、下記検索式（２）が与えられた場合、syain，ACT，castを通るパスＰ１を部分パススキーマ１２００として抽出する。このパスＰ１はユニークなパスであるため、階層ノードＮ０とcastをあらわす階層ノードＮ５とその子ノードであるnameをあらわす階層ノードＮ６ｃとからなるパスツリーが部分パススキーマとして抽出される。一方、途中のsyain，ACTをあらわす階層ノードは削除される。また、パスＰ１から外れた階層ノードも当然削除される。
【０１２５】
/syain/ACT/cast = ブルー・・・（２）
【０１２６】
図１３は、図１２に示した部分パススキーマ１２００により階層検索オートマトンを構成した場合の単一オートマトンを示す説明図である。この単一オートマトン１３００において、階層検索オートマトン１３０１には、部分パススキーマ１２００を構成していない階層ノードＮ１〜Ｎ４，Ｎ７が含まれていないため、階層検索オートマトン１３０１のサイズ縮小化を図ることができる。これにより、状態遷移回数を削減することができるため、検索速度の向上を図ることができる。
【０１２７】
図１４は、部分パススキーマの抽出例（その２）を示す説明図である。図１４において、下記検索式（３）が与えられた場合、syain,ACT,cast,chara,nameを通るパスを部分パススキーマ１４００として抽出する。パスＰ１，Ｐ２は、階層ノードＮ２まで共通するため、階層ノードＮ１，Ｎ２は削除される。
【０１２８】
また、階層ノードＮ６ａはヒット階層ノードではないので、削除される。階層ノードＮ４は階層ノードＮ３からの分岐先を特定するために残しておく。階層ノードＮ６ｂはヒット階層ノードであるため残しておく。階層ノードＮ７は階層ノードＮ６ｂの子階層ノードであるため残しておく。階層ノードＮ５，Ｎ６ｃはパスＰ２，Ｐ３外なので削除される。
【０１２９】
/syain/ACT/cast/chara/name = ブルー・・・（３）
【０１３０】
図１５は、図１４に示した部分パススキーマ１４００により階層検索オートマトンを構成した場合の単一オートマトン１５００を示す説明図である。階層検索オートマトン１５０１には、部分パススキーマ１４００を構成していない階層ノードＮ１，Ｎ２，Ｎ５が含まれていないため、階層検索オートマトン１５０１のサイズ縮小化を図ることができる。これにより、状態遷移回数を削減することができるため、検索速度の向上を図ることができる。
【０１３１】
（情報検索装置１００の機能的構成）
図１６は、この発明の実施の形態２にかかる情報検索装置１００の機能的構成を示すブロック図である。図１６において、図４の示した機能４０１〜４０７のほかに、抽出部１６０１と判断部１６０２とを備える。
【０１３２】
なお、これら各機能１６０１，１６０２は、情報検索装置１００内のメモリに格納された当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。
【０１３３】
また、各機能１６０１，１６０２からの出力データはメモリに保持される。また、図１６中矢印で示した接続先の機能は、接続元の機能からの出力データをメモリから読み込んで、当該機能に関するプログラムを情報検索装置１００内のプロセッサに実行させる。
【０１３４】
図１６において、抽出部１６０１は、パススキーマの中から、検索式により特定される検索範囲に関する部分パススキーマを抽出する。具体的には、検索式により特定されるパスが１通り、すなわちユニークパスである場合、パススキーマからルートノードとヒット階層ノードとその子階層ノードとからなるパスツリーを部分パススキーマとして抽出する。たとえば、図１２に示したように、部分パススキーマ１２００を抽出する。
【０１３５】
一方、検索式により特定されるパスが複数通りある場合、その複数通りのパスの配列パターンに応じて部分パススキーマを抽出する。具体的な抽出例については、判断部１６０２の説明で述べる。
【０１３６】
いずれにしても、オートマトン生成部４０４では、図１３および図１５に示したように、部分パススキーマ１２００，１４００の階層を検索する階層検索オートマトン１３０１，１５０１と、ヒットキーワードを検索するキーワード検索オートマトン５０２とからなる単一オートマトン１３００，１５００を生成する。
【０１３７】
また、判断部１６０２は、検索式により特定されるパスがパススキーマ１１００内に複数通り存在するか否かを判断する。具体的には、検索式の末尾の階層名をあらわすノードが複数あるか否かにより、パスが複数通りあるか否かを判断することができる。たとえば、図１２に示したように、パススキーマ１１００から検索式（２）により特定されるパスはパスＰ１のみであると判断され、パスＰ１はユニークパスとなる。一方、図１４に示したように、パススキーマ１１００から検索式（３）により特定されるパスはパスＰ２，Ｐ３の２通りであると判断される。
【０１３８】
また、判断部１６０２は、複数通りあると判断された場合、その複数通りのパスの配列パターンがどの配列パターンに該当するか否かを判断する。以下、配列パターン例について説明する。
【０１３９】
図１７は、配列パターンＡを示す説明図である。配列パターンＡは、ヒット階層ノードと同一階層名となる類似ノードがヒット階層ノードよりも上位階層に存在する配列パターンである。図１７において、たとえば、検索式が「/a/b/name」である場合、パススキーマ１７００の階層ノードＮ０〜Ｎ４までのパスと階層ノードＮ０〜Ｎ８までのパスが特定される。ここで、階層ノードＮ４，Ｎ８のうち階層ノードＮ８をヒット階層ノードとすると、階層ノードＮ４は類似ノードとなる。
【０１４０】
配列パターンＡの場合、抽出パターンＡ−１，Ａ−２がある。抽出パターンＡ−１では、ルートノードＮ０と、類似ノードとヒット階層ノードとの間にのみ存在する中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。
【０１４１】
この抽出パターンＡ−１にしたがうと、ルートノードＮ０と、集合Ｙにのみ存在する中間階層ノードＮ５と、ヒット階層ノードＮ８と、からなる部分パススキーマ１７０１を抽出することができる。同様に、ルートノードＮ０と、中間階層ノードＮ７と、ヒット階層ノードＮ８と、からなる部分パススキーマ１７０２を抽出することができる。
【０１４２】
一方、抽出パターンＡ−２では、ルートノードＮ０と、類似ノードとヒット階層ノードとの間に存在する中間階層ノードと、ルートノードＮ０と類似ノードとの間に存在し中間階層ノードと同一階層名である他の中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。
【０１４３】
この抽出パターンＡ−２にしたがうと、ルートノードＮ０と、集合Ｙに存在する中間階層ノードＮ６と、集合Ｘに存在する他の中間階層ノードＮ２と、ヒット階層ノードＮ８と、からなる部分パススキーマ１７０３を抽出することができる。
【０１４４】
なお、中間階層ノードとしてルートノードＮ０から階層の深いノードを選んでおくと、他の類似ノードに対する中間階層ノードとしても利用することができ、ノード数の削減を図ることができる。
【０１４５】
図１８は、配列パターンＢを示す説明図である。配列パターンＢは、ヒット階層ノードと同一階層名となる他の階層ノードがヒット階層ノードよりも下位階層に存在する配列パターンである。図１８において、たとえば、検索式が「/a/b/name」である場合、パススキーマ１７００の階層ノードＮ０〜Ｎ４までのパスと階層ノードＮ０〜Ｎ８までのパスが特定される。ここで、階層ノードＮ４，Ｎ８のうち階層ノードＮ４をヒット階層ノードとすると、階層ノードＮ８は類似ノードとなる。
【０１４６】
配列パターンＢの場合、抽出パターンＢ−１がある。抽出パターンＢ−１では、ルートノードＮ０と、ヒット階層ノードと、当該ヒット階層ノードと類似ノードとの間に存在する子階層ノードと、からなる部分パススキーマを抽出する。
【０１４７】
この抽出パターンＢ−１にしたがうと、ルートノードＮ０と、ヒット階層ノードＮ４と、集合Ｙ（当該ヒット階層ノードＮ４と類似ノードＮ８との間）に存在する子階層ノードＮ５，Ｎ６またはＮ７と、からなる部分パススキーマ１８０１〜１８０３を抽出することができる。
【０１４８】
図１９は、配列パターンＣが適用されるパススキーマを示す説明図である。配列パターンＣは、類似ノードがヒット階層ノードよりも上位階層に存在する分岐元の階層ノードから分岐されたパスに存在する配列パターンである。図１９において、たとえば、検索式が「/a/b/name」である場合、パススキーマ１９００の階層ノードＮ０〜Ｎ７までのパスと階層ノードＮ０〜Ｎ３，Ｎ８〜Ｎ１５までのパスが特定される。ここで、階層ノードＮ７，Ｎ１５のうち階層ノードＮ７をヒット階層ノードとすると、階層ノードＮ１５は類似ノードとなる。
【０１４９】
配列パターンＣの場合、抽出パターンＣ−１〜Ｃ−６がある。抽出パターンＣ−１では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間にのみ存在する中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。
【０１５０】
図２０は、抽出パターンＣ−１により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−１では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間にのみ存在する中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。
【０１５１】
この抽出パターンＣ−１にしたがうと、ルートノードＮ０と、集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）にのみ存在する中間階層ノードＮ４と、ヒット階層ノードＮ７と、からなる部分パススキーマ２０００を抽出することができる。
【０１５２】
なお、図１９に示した集合Ｙにおいて、階層ノードＮ５は、同一階層名ｂの階層ノードＮ２が集合Ｘに存在し、また、同一階層名ｂの階層ノードＮ１０が集合Ｚに存在するため、選ばれない。同様に、階層ノードＮ６は、同一階層名ｂの階層ノードＮ１２，Ｎ１３が集合Ｚに存在するため選ばれない。
【０１５３】
図２１は、抽出パターンＣ−２により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−２では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間に存在しかつ分岐元の階層ノードと類似ノードとの間に存在しない中間階層ノードと、ルートノードと分岐元の階層ノードとの間に存在する中間階層ノードと同一階層名の他の中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。
【０１５４】
この抽出パターンＣ−２にしたがうと、ルートノードＮ０と、集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在しかつ集合Ｚ（分岐元の階層ノードＮ３と類似ノードＮ１５との間）に存在しない中間階層ノードＮ５と、集合Ｘ（ルートノードＮ０と分岐元の階層ノードＮ３との間）に存在する中間階層ノードＮ５と同一階層名の他の中間階層ノードＮ２と、ヒット階層ノードＮ７と、からなる部分パススキーマ２１００を抽出することができる。
【０１５５】
図２２は、抽出パターンＣ−３により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−３では、ルートノードＮ０と、ヒット階層ノードと、分岐元の階層ノードと類似ノードとの間にのみ存在する分岐先の階層ノードと、からなる部分パススキーマを抽出する。
【０１５６】
この抽出パターンＣ−３にしたがうと、ルートノードＮ０と、ヒット階層ノードＮ７と、集合Ｚ（分岐元の階層ノードＮ３と類似ノードＮ１５との間）にのみ存在する分岐先の階層ノードＮ８，Ｎ９またはＮ１１と、からなる部分パススキーマ２２０１〜２２０３を抽出することができる。
【０１５７】
図２３は、抽出パターンＣ−４により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−４では、ルートノードＮ０と、分岐元の階層ノードと類似ノードとの間に存在しかつ分岐元の階層ノードとヒット階層ノードとの間に存在しない中間階層ノードと、ルートノードＮ０と分岐元の階層ノードとの間に存在する中間階層ノードと同一階層名の他の中間階層ノードと、ヒット階層ノードと、からなる部分パススキーマを抽出する。
【０１５８】
この抽出パターンＣ−４にしたがうと、ルートノードＮ０と、集合Ｚ（分岐元の階層ノードＮ３と類似ノードＮ１５との間）に存在しかつ集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在しない中間階層ノードＮ１４と、集合Ｘ（ルートノードＮ０と分岐元の階層ノードＮ３との間）に存在する中間階層ノードＮ１４と同一階層名の他の中間階層ノードＮ１と、ヒット階層ノードＮ７と、からなる部分パススキーマ２３００を抽出することができる。
【０１５９】
図２４は、抽出パターンＣ−５により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−５では、ルートノードＮ０と、当該ルートノードＮ０と分岐元の階層ノードとの間に存在せずかつ分岐元の階層ノードとヒット階層ノードとの間に存在する第１の中間階層ノードと、ルートノードＮ０と第１の中間階層ノードとの間に存在せずかつ第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードと分岐元の階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出する。
【０１６０】
この抽出パターンＣ−５にしたがうと、ルートノードＮ０と、当該ルートノードＮ０と集合Ｘ（分岐元の階層ノードＮ３との間）に存在せずかつ集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在する第１の中間階層ノードＮ６と、ルートノードＮ０と第１の中間階層ノードＮ６との間に存在せずかつ第１の中間階層ノードＮ６と同一階層名の第２の中間階層ノードＮ１３，Ｎ１４のうち最上位の中間階層ノードＮ１３と分岐元の階層ノードＮ３との間の第３の中間階層ノードＮ８，Ｎ９またはＮ１１と、からなる部分パススキーマ２４０１〜２４０３を抽出することができる。
【０１６１】
図２５は、抽出パターンＣ−６により抽出された部分パススキーマを示す説明図である。この抽出パターンＣ−６では、ルートノードＮ０と、分岐元の階層ノードとヒット階層ノードとの間に存在する第１の中間階層ノードと、分岐元の階層ノードと第１の中間階層ノードとの間に存在せずかつ第１の中間階層ノードと同一階層名の第２の中間階層ノードのうち最上位の中間階層ノードと分岐元の階層ノードとの間の第３の中間階層ノードと、からなる部分パススキーマを抽出する。
【０１６２】
この抽出パターンＣ−６にしたがうと、ルートノードＮ０と、集合Ｙ（分岐元の階層ノードＮ３とヒット階層ノードＮ７との間）に存在する第１の中間階層ノードＮ５と、分岐元の階層ノードＮ３と第１の中間階層ノードＮ５との間に存在せずかつ第１の中間階層ノードＮ５と同一階層名の第２の中間階層ノードＮ１０のうち最上位の中間階層ノードＮ１０と分岐元の階層ノードＮ３との間の第３の中間階層ノードＮ８またはＮ９と、からなる部分パススキーマ２５０１〜２５０３を抽出することができる。
【０１６３】
（情報検索処理手順）
つぎに、この発明の実施の形態２にかかる情報検索処理手順について説明する。図２６は、この発明の実施の形態２にかかる情報検索処理手順を示すフローチャートである。図２６において、図９に示したステップと同一処理内容については同一ステップ番号を付し、その説明を省略する。
【０１６４】
図２６において、ステップＳ９０４とステップＳ９０５との間において、抽出処理を実行する（ステップＳ２６０１）。この抽出処理（ステップＳ２６０１）は、上述した判断部１６０２および抽出部１６０１により実行される。このため、ステップＳ９０５の単一オートマトン生成では、抽出処理（ステップＳ２６０１）により抽出された部分パススキーマを用いて構成された階層検索オートマトンとキーワード検索オートマトン５０２とからなる単一オートマトンを生成することとなる。
【０１６５】
同様に、ステップＳ９０９とステップＳ９１０との間においても、抽出処理を実行する（ステップＳ２６０２）。この抽出処理（ステップＳ２６０２）も、上述した判断部１６０２および抽出部１６０１により実行される。このため、ステップＳ９１０の変換済み単一オートマトン生成では、抽出処理（ステップＳ２６０２）により抽出された変換済み部分パススキーマを用いて構成された変換済み階層検索オートマトンとキーワード検索オートマトン５０２とからなる変換済み単一オートマトンを生成することとなる。
【０１６６】
つぎに、上述した抽出処理（ステップＳ２６０１，Ｓ２６０２）の詳細な処理手順について説明する。図２７は、抽出処理（ステップＳ２６０１，Ｓ２６０２）の詳細な処理手順を示すフローチャートである。図２７において、まず、検索式からルートノードおよびヒット階層ノードを特定し（ステップＳ２７０１）、検索式により特定されるパスが複数通りあるか否かを判断する（ステップＳ２７０２）。
【０１６７】
複数通りない場合（ステップＳ２７０２：Ｎｏ）、図１２に示したように、そのパスにより特定される部分パススキーマ（または変換済み部分パススキーマ）をパススキーマ（変換済みパススキーマ）から抽出する（ステップＳ２７０３）。これにより、ステップＳ９０５（Ｓ９１０）に移行する。
【０１６８】
一方、複数通りある場合（ステップＳ２７０２：Ｙｅｓ）、該当する配列パターンを特定し（ステップＳ２７０４）、抽出パターンを選択する（ステップＳ２７０５）。抽出パターンの選択はランダムにおこなってもよく、また優先順位をつけて選択してもよい。
【０１６９】
このあと、選択された抽出パターンにしたがって部分パススキーマ（または変換済み部分パススキーマ）をパススキーマ（変換済みパススキーマ）から抽出して（ステップＳ２７０６）、ステップＳ９０５（Ｓ９１０）に移行する。これにより、一連の処理を終了する。
【０１７０】
（ワイルドカード検索）
つぎに、ワイルドカード検索について説明する。ワイルドカードとは、検索する際にどんなパターンにもマッチする特殊文字であり、検索式の組み方により、２通りの検索範囲が特定される。ここでは、検索式中において、ワイルドカードを『//』で表記する。
【０１７１】
まず、Ｘ//のように、ワイルドカードが末尾に記述されている検索式の場合、ヒット階層ノードとしてＸを階層名とする階層ノードのみを選択する。図２８は、部分パススキーマの抽出例（その３）を示す説明図である。図１１に示したパススキーマ１１００を例にあげると、下記検索式（４）が与えられた場合、ルートノードＮ０とヒット階層ノードＮ３とからなる部分パススキーマ２８００を抽出することができ、サイズの縮小を図ることができる。なお、フラグが立っている階層ノードは検索対象となる階層ノードである。
【０１７２】
/syain/ACT/chara//・・・（４）
【０１７３】
また、//Ｘのように、ワイルドカードが末尾に記述されていない検索式の場合、ヒット階層ノードとして、上記文献（１）に示したパスプルーニング手法により導き出される階層ノードとその子階層ノードを選択する。図２９は、部分パススキーマの抽出例（その４）を示す説明図である。図１１に示したパススキーマ１１００を例にあげると、下記検索式（５）が与えられた場合、ルートノードＮ０とヒット階層ノードＮ６（Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃ）とからなる部分パススキーマ２９００を抽出することができる。なお、フラグが立っている階層ノードは検索対象となる階層ノードである。
【０１７４】
//name・・・（５）
【０１７５】
また、検索式が複数与えられる場合もある。この場合、すべての検索式から得られるノードを網羅するように、ヒット階層ノードやその子階層ノードを特定する。具体的には、各検索式の論理和を取ることにより、部分パススキーマを抽出する。
【０１７６】
図３０は、部分パススキーマの抽出例（その５）を示す説明図である。図３０に示した抽出例は、上述した検索式（４）,（５）が与えられた場合の抽出例である。この場合、ルートノードＮ０とヒット階層ノードＮ３，Ｎ６（Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃ）とからなる部分パススキーマ３０００を抽出することができ、サイズの縮小を図ることができる。なお、フラグが立っている階層ノードは検索対象となる階層ノードである。
【０１７７】
また、ヒット階層ノードＮ６ａ，Ｎ６ｂは階層ノードＮ３からの分岐先ノードであるため、この２本のパスを１本にまとめることができる。具体的には、子階層ノードを有するヒット階層ノードＮ６ｂに縮退させる。部分パススキーマ３００１は、縮退済み部分パススキーマである。これにより、さらにサイズの縮小を図ることができる。
【０１７８】
このように、実施の形態２によれば、ルートノードからヒット階層ノードに一意に到達することができるパスツリーとなる部分パススキーマをパススキーマから抽出するため、階層検索オートマトンの生成元を、ノード数が削減された部分パススキーマに絞り込むことができる。したがって、生成される単一オートマトン内の階層検索オートマトンのサイズを縮小することができる。
【０１７９】
階層検索オートマトンのサイズが縮小されると、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。
【０１８０】
＜実施の形態３＞
つぎに、実施の形態３について説明する。実施の形態１では、図６に示した変換テーブル６００により、電子文書内の階層名ごとに固有の文字列に変換することで階層検索オートマトンのノード数を削減しているが、実施の形態３では、パススキーマ内のパスごとにタグ記号および固有の識別子を割り当てることにより、階層検索オートマトンのノード数を削減する。
【０１８１】
たとえば、図１１に示したパススキーマ１１００の場合、階層名nameをあらわす階層ノードをヒット階層ノードとするパスは３本存在するが、パスごとに異なる識別子を割り当てることにより、電子文書読み出し時にその識別子を検出するだけでパスを判別することができる。なお、実施の形態１，２で示した構成と同一構成については同一符号を付し、その説明を省略する。
【０１８２】
（第１の例）
（パスＩＤテーブル）
図３１は、パスＩＤテーブル３１００を示す説明図である。図３１において、パスＩＤテーブル３１００はパスごとにパスＩＤが割り振られている。このパスＩＤテーブル３１００は、電子文書を読み込んだときに作成される。
【０１８３】
具体的には、パスＩＤテーブル３１００にパスＩＤが割り振られていないパスが検出された場合、その検出されたパスに対して固有のパスＩＤを割り振る。一方、パスＩＤが割り振られているパスが検出された場合には、電子文書のタグを変換する。
【０１８４】
なお、検索対象がＸＭＬ文書である場合、開始タグのタグ記号を『<…>』から『［…』に変換する。また、終了タグのタグ記号を『</…>』から『/…』に変換する。この変換処理は、図４に示した変換部４０７が実行する。また、タグ記号『[』を階層開始指示子と称し、タグ記号『/』を階層終了指示子と称す。
【０１８５】
（パスＩＤへの変換例）
つぎに、パスＩＤへの変換例（その１）について説明する。図３２は、パスＩＤへの変換例（その１）を示す説明図である。図３２において、符号３２０１は変換前のＸＭＬ文書であり、符号３２０２は変換済みＸＭＬ文書である。
【０１８６】
（変換済みパススキーマの生成例）
図３３は、変換済みパススキーマを示す説明図である。この変換済みパススキーマ３３００は、図３２に示した変換済みＸＭＬ文書３２０２から生成されたパススキーマである。ここでは、各階層ノードの符号として「ｎ＃」を付している。＃はパスＩＤである。したがって、図１１に示した階層ノードＮ６（Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃ）のように、同一階層名nameのノードが複数存在することはなく、図３３では、ｎ４，ｎ６，ｎ９のように、同一階層名nameであっても区別がつくように表現される。
【０１８７】
（部分パススキーマの抽出例）
図３４は、部分パススキーマの抽出例（その６）を示す説明図である。図３４において、下記検索式（６）が与えられると、変換済み部分パススキーマ３４００を変換済みパススキーマ３３００から抽出することができる。同一検索式が与えられた図１４の抽出例と比較するとノード数が削減されていることがわかる。
【０１８８】
/syain/ACT/chara/name/・・・（６）
【０１８９】
図３５は、変換済み部分パススキーマ３４００から得られる階層検索オートマトンを示す説明図である。図３５において、階層検索オートマトン３５００は、変換済み部分パススキーマ３４００を構成する階層ノードｎ０，ｎ４と、階層開始指示子『[』をあらわすノードと、階層終了指示子『/』をあらわすノードとから構成される。階層検索オートマトン３５００は、図１５に示した階層検索オートマトン１５０１と比べると、ノード数が削減されている。
【０１９０】
階層検索オートマトン３５００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。
【０１９１】
また、階層検索オートマトン３５００では、ヒット階層ノードｎ４に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ４自身に状態遷移する。
【０１９２】
また、階層検索オートマトン３５００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』が与えられると、ヒット階層ノードｎ４に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。
【０１９３】
また、ヒット階層ノードｎ４６９には、ヒット階層ノードｎ４の子階層ノードｎ７の識別子『７』も埋め込まれているため、階層検索オートマトン３５００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『７』が与えられると、ヒット階層ノードｎ４に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。
【０１９４】
したがって、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。
【０１９５】
（第２の例）
（ワイルドカード検索）
第２の例は、ワイルドカード検索に関する検索例である。ワイルドカード検索の場合、複数通りのパスが選択される場合がある。図３６は、部分パススキーマの抽出例（その７）を示す説明図である。図３６において、たとえば、下記検索式（７）が与えられた場合、変換済みパススキーマ３３００から、ルートノードｎ０とヒット階層ノードｎ４、ｎ６、ｎ９とからなる変換済み部分パススキーマ３６０１を抽出することができる。
【０１９６】
また、これらのヒット階層ノードｎ４、ｎ６、ｎ９は同一階層名であるため、縮退させることにより変換済み部分パススキーマ３６０２を得ることができる。縮退されたヒット階層ノードｎ４６９は、ヒット階層ノードｎ４、ｎ６、ｎ９の識別子『４』，『６』，『９』とヒット階層ノードｎ４の子階層ノードｎ７の識別子『７』が埋め込まれたノードである。
【０１９７】
図３７は、変換済み部分パススキーマ３６０２から得られる階層検索オートマトンを示す説明図である。図３７において、階層検索オートマトン３７００は、変換済み部分パススキーマ３６０２を構成する階層ノードｎ０，ｎ４６９と、階層開始指示子『[』をあらわすノードと、階層終了指示子『/』をあらわすノードとから構成される。階層検索オートマトン３７００は、図１５に示した階層検索オートマトン１５０１と比べると、ノード数が削減されている。
【０１９８】
階層検索オートマトン３７００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。
【０１９９】
また、階層検索オートマトン３７００では、ヒット階層ノードｎ４６９に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ４６９自身に状態遷移する。
【０２００】
また、ヒット階層ノードｎ４６９には、ヒット階層ノードｎ４、ｎ６、ｎ９の識別子『４』，『６』，『９』が埋め込まれているため、階層検索オートマトン３７００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』，『６』または『９』が与えられると、ヒット階層ノードｎ４６９に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。
【０２０１】
また、ヒット階層ノードｎ４６９には、ヒット階層ノードｎ４の子階層ノードｎ７の識別子『７』も埋め込まれているため、階層検索オートマトン３７００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『７』が与えられると、ヒット階層ノードｎ４６９に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。
【０２０２】
したがって、この第２の例では、単一オートマトンの生成に先立って、パススキーマを縮退させることができるため、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。
【０２０３】
（第３の例）
第３の例は、複数検索式の場合の検索例である。検索式が複数与えられた場合、すべての検索式から得られるノードを網羅するように、ヒット階層ノードやその子階層ノードを特定する。具体的には、各検索式の論理和を取ることにより、変換済み部分パススキーマを抽出する。
【０２０４】
図３８は、複数検索式の変換例を示す説明図である。検索式Ｋ１＝/syain/ACT/chara//と検索式Ｋ２＝//nameとが与えられた場合、検索式Ｋ１および検索式Ｋ２を検索式Ｑ１およびＱ２に変換する。検索式Ｑ１およびＱ２は、検索式Ｋ１およびＫ２内の階層名を、それぞれ階層開始指示子『[』と固有の識別子とからなる記号列に変換し、これらを論理和（図中、「ｏｒ」で表記）でつなげることにより表現される。
【０２０５】
また、検索式Ｑ１およびＱ２から、これらの論理積（図中、「＆」で表記）ととった検索式Ｑ２＆Ｑ１を生成する。この場合、検索式Ｑ１およびＱ２から、検索式Ｑ２＆Ｑ１に含まれる記号列（[４，[６）を削除する。このように、３つの検索式Ｑ１，Ｑ２，Ｑ２＆Ｑ１からそれぞれ１つずつ記号列を選択することにより、変換済み部分パススキーマを抽出する。
【０２０６】
図３９は、部分パススキーマの抽出例（その８）を示す説明図である。図３９において、３つの検索式Ｑ１，Ｑ２，Ｑ２＆Ｑ１から、それぞれ記号列[３，[４，[９が選ばれたとすると、変換済み部分パススキーマ３９００が抽出される。
【０２０７】
なお、選ばれなかった記号列は、検索式Ｑ１，Ｑ２，Ｑ２＆Ｑ１においてそれぞれ選ばれた記号列の階層ノードに埋め込まれることとなる。たとえば、ヒット階層ノードｎ３には、階層開始指示子『[』をあらわすノードからの遷移先を特定するため、記号列[３，[５，[７が埋め込まれることとなる。
【０２０８】
また、子階層ノードｎ４，ｎ５を有するため、記号列[４，[５も階層終了指示子『/』をあらわすノードからの遷移先として埋め込まれることとなる。さらに、子階層ノードｎ５はヒット階層ノードではないため、その子階層ノードであるヒット階層ノードｎ６の記号列[６も階層終了指示子『/』をあらわすノードからの遷移先として埋め込まれる。
【０２０９】
また、ヒット階層ノードｎ９には、階層開始指示子『[』をあらわすノードからの遷移先を特定するため、記号列[９が埋め込まれることとなる。また、ヒット階層ノードｎ４には、階層開始指示子『[』をあらわすノードからの遷移先を特定するため、記号列[４，[６が埋め込まれることとなる。また、ヒット階層ノードｎ４は子階層ノードｎ７を有するため、記号列[７も階層終了指示子『/』をあらわすノードからの遷移先として埋め込まれることとなる。
【０２１０】
図４０は、変換済み部分パススキーマ３９００から得られる階層検索オートマトンを示す説明図である。図４０において、階層検索オートマトン４０００は、変換済み部分パススキーマ３９００を構成する階層ノードｎ０，ｎ３，ｎ４，ｎ９と、階層開始指示子『[』をあらわすノードと、階層終了指示子『/』をあらわすノードとから構成される。
【０２１１】
階層検索オートマトン４０００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。
【０２１２】
また、階層検索オートマトン４０００では、ヒット階層ノードｎ４に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ４自身に状態遷移する。
【０２１３】
また、階層検索オートマトン４０００では、ヒット階層ノードｎ９に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ９自身に状態遷移する。
【０２１４】
また、階層検索オートマトン４０００では、ヒット階層ノードｎ３に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層終了指示子『/』が与えられると、そのノードに状態遷移する。なお、タグ記号以外の文字が与えられると、ヒット階層ノードｎ３自身に状態遷移する。
【０２１５】
また、ヒット階層ノードｎ４には、ヒット階層ノードｎ６の識別子『６』が埋め込まれているため、階層検索オートマトン４０００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』または『６』が与えられると、ヒット階層ノードｎ４に状態遷移する。
【０２１６】
また、ヒット階層ノードｎ３には、ヒット階層ノードｎ３，ｎ５およびｎ７の識別子『３』，『５』および『７』が埋め込まれているため、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『３』，『５』または『７』が与えられると、ヒット階層ノードｎ３に状態遷移する。
【０２１７】
同様に、ヒット階層ノードｎ９には、ヒット階層ノードｎ９の識別子『９』が埋め込まれているため、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『９』が与えられると、ヒット階層ノードｎ９に状態遷移する。
【０２１８】
一方、階層開始指示子『[』をあらわすノードに状態遷移している場合、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。
【０２１９】
また、ヒット階層ノードｎ４には、子階層ノードｎ７の識別子『７』が埋め込まれているため、階層検索オートマトン４０００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『７』が与えられると、ヒット階層ノードｎ４に状態遷移する。
【０２２０】
また、ヒット階層ノードｎ４には、階層ノードｎ４，ｎ５，ｎ６の識別子『４』，『５』および『６』が埋め込まれているため、階層検索オートマトン４０００では、階層終了指示子『/』をあらわすノードに状態遷移している場合、識別子『４』，『５』または『６』が与えられると、ヒット階層ノードｎ３に状態遷移する。
【０２２１】
一方、階層終了指示子『/』をあらわすノードに状態遷移している場合、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。
【０２２２】
したがって、この第３の例では、単一オートマトンの生成に先立って、パススキーマを縮退させることができるため、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。
【０２２３】
（第４の例）
第４の例は、階層指示子を開始タグと終了タグとで区別せず、同一記号を用いる場合の例である。具体的には、たとえば、階層終了指示子『/』を、階層開始指示子『[』に変え、識別子をタグ間文字列の識別子の親となる識別子を用いる。
【０２２４】
図４１は、パスＩＤへの変換例（その２）を示す説明図である。図４１において、符号３２０１は変換前のＸＭＬ文書であり、符号４１００は変換済みＸＭＬ文書である。たとえば、ＸＭＬ文書４１００の４行目に着目すると、変換後の終了タグは、階層開始指示子『[』と、開始タグに埋め込まれている識別子『４』の親となる識別子『３』と、からなる記号列『[３』となる。他の変換後のタグも同様に変換される。なお、この場合の変換済み部分パススキーマは、図３４に示した場合と同様である。
【０２２５】
図４２は、第４の例の階層検索オートマトンを示す説明図である。図４２において、階層検索オートマトン４２００は、ルートノードｎ０とヒット階層ノードｎ４と階層開始指示子『[』をあらわすノードから構成される。図３５に示した階層検索オートマトン３５００と比べると、階層終了指示子『/』をあらわすノードが削除されている分、オートマトンサイズが縮小される。
【０２２６】
階層検索オートマトン４２００では、ルートノードｎ０に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層開始指示子『[』以外の文字が与えられると、ルートノードｎ０自身に状態遷移する。
【０２２７】
また、階層検索オートマトン４２００では、ヒット階層ノードｎ４に状態遷移している場合、階層開始指示子『[』が与えられると、そのノードに状態遷移する。一方、階層開始指示子『[』以外の文字が与えられると、ヒット階層ノードｎ４自身に状態遷移する。
【０２２８】
また、階層検索オートマトン４２００では、階層開始指示子『[』をあらわすノードに状態遷移している場合、識別子『４』が与えられると、ヒット階層ノードｎ４に状態遷移する。一方、それ以外の識別子（図中「？」で表記）が与えられると、ルートノードｎ０に状態遷移する。
【０２２９】
したがって、この第４の例では、単一オートマトンの生成に先立って、パススキーマを縮退させることができるため、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。
【０２３０】
（情報検索処理手順）
つぎに、この発明の実施の形態３にかかる情報検索処理手順について説明する。図４３は、この発明の実施の形態３にかかる情報検索処理手順を示すフローチャートである。図４３において、図９に示したステップと同一処理内容については同一ステップ番号を付し、その説明を省略する。
【０２３１】
図４３において、ステップＳ９０２：Ｙｅｓのあと、変換部４０７により、パスＩＤテーブル３１００を用いて、タグ開始記号および階層名を変換する（ステップＳ４３０１）。したがって、図３２または図４１に示したような変換済みＸＭＬ文書３２０２，４１００が得られ、図３３に示したような変換済みパススキーマ３３００が生成されることとなる（ステップＳ９０８）。
【０２３２】
また、ステップＳ９０９のあと、変換済みパススキーマ３３００から変換済み部分パススキーマを抽出する（ステップＳ４３０２）。この場合、図３４、図３６または図３９に示したように、変換済み部分パススキーマ３４００，３６０２，３９００が抽出されることとなる。
【０２３３】
したがって、ステップＳ９１０において、図３５，図３７，図４０または図４２に示したように、変換済みの階層検索オートマトン３５００，３７００，４０００，４２００を有する変換済み単一オートマトンが生成されることとなる（ステップＳ９１０）。
【０２３４】
このように、実施の形態３では、パススキーマ内のパスごとにタグ記号および固有の識別子を割り当てることにより、階層検索オートマトンのノード数を削減することができる。
【０２３５】
したがって、単一オートマトンを保持するメモリ容量を削減することができる。またこれにより、プロセッサで処理を実行する場合、メモリサイズの削減を図ることができ、キャッシュミス率の低下が見込め、検索速度の高速化を実現することができる。また、階層検索オートマトンのサイズの縮小により、状態遷移回数が低減する。これにより、キャッシュミス率も低下するため、検索速度の高速化を実現することができる。
【０２３６】
以上説明したように、本実施の形態によれば、階層検索用オートマトンとキーワード検索用オートマトンとの間のオーバーヘッドの低減を図ることにより、検索速度の向上を図ることができる。
【０２３７】
なお、本実施の形態で説明した情報検索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。
【０２３８】
また、本実施の形態で説明した情報検索装置１００は、スタンダードセルやストラクチャードＡＳＩＣ(Application Specific Integrated Circuit)などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ(Programmable Logic Device)によっても実現することができる。具体的には、たとえば、上述した情報検索装置１００の機能的構成（機能ブロックの各符号を入れる）をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、情報検索装置１００を製造することができる。
【産業上の利用可能性】
【０２３９】
以上のように、本発明にかかる情報検索プログラム、該プログラムを記録した記録媒体、情報検索装置、および情報検索方法は、階層構造を有する電子文書の検索に有用であり、特に、ＸＭＬ文書やＨＴＭＬ文書などに適している。
【符号の説明】
【０２４０】
１００  情報検索装置
４０１  取得部
４０２  パススキーマ生成部
４０３  入力部
４０４  オートマトン生成部
４０５  検索部
４０６  出力部
４０７  変換部
１６０１  抽出部
１６０２  判断部
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータを、
検索対象となる階層構造を有する電子文書を取得する取得部、
前記取得部によって取得された電子文書に関するパススキーマを生成するパススキーマ生成部、
任意の検索キーワード、当該検索キーワードの検索条件、及び前記検索キーワードの検索範囲を特定する検索式の入力を受け付ける入力部、
前記パススキーマ生成部によって生成されたパススキーマの階層を検索する階層検索オートマトンと、前記入力部によって入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成するオートマトン生成部、
前記オートマトン生成部によって生成された単一オートマトンを用いて、前記電子文書の中から、前記検索範囲内の前記ヒットキーワードを検索する検索部、および
前記検索部によって検索された検索結果を出力する出力部、
として機能させることを特徴とする情報検索プログラム。
【請求項２】
前記階層検索オートマトンは、
遷移元となる上位の階層ノードとその遷移先となる下位の階層ノードとの間に開始タグの開始記号をあらわすノードを有し、前記上位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することを特徴とする請求項１に記載の情報検索プログラム。
【請求項３】
前記階層検索オートマトンは、
前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することを特徴とする請求項２に記載の情報検索プログラム。
【請求項４】
前記コンピュータを、
前記パススキーマを構成する各階層ノードの階層名を固有の文字列に変換する変換手段として機能させ、
前記オートマトン生成部は、
前記階層検索オートマトンを前記変換手段によって変換された固有の文字列を用いて構成することにより、前記単一オートマトンを生成し、
前記階層検索オートマトンは、
前記開始記号をあらわすノードと下位の階層ノードとの間に、前記下位の階層ノードの階層名から変換された固有の文字列をあらわす一連のノード群を有し、前記開始記号をあらわすノードに状態遷移している場合に任意の文字列が与えられると、ヒットミスする文字が出現するまで前記一連のノード群に対し状態遷移することを特徴とする請求項２に記載の情報検索プログラム。
【請求項５】
前記階層検索オートマトンは、
ヒットミスする文字が出現した場合、前記上位の階層ノードに状態遷移することを特徴とする請求項３または４に記載の情報検索プログラム。
【請求項６】
前記階層検索オートマトンは、
前記一連のノード群の中の末尾ノードに状態遷移している場合に前記開始タグの終了記号が与えられると、前記下位の階層ノードに状態遷移することを特徴とする請求項３または４に記載の情報検索プログラム。
【請求項７】
前記階層検索オートマトンは、
遷移元となる下位の階層ノードとその遷移先となる上位の階層ノードとの間に終了タグの開始記号をあらわすノードを有し、前記下位の階層ノードに状態遷移している場合に前記開始記号が与えられると、前記開始記号をあらわすノードに状態遷移することを特徴とする請求項１に記載の情報検索プログラム。
【請求項８】
請求項１〜７のいずれか一項に記載の情報検索プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【請求項９】
検索対象となる階層構造を有する電子文書を取得する取得部と、
前記取得部によって取得された電子文書に関するパススキーマを生成するパススキーマ生成部と、
任意の検索キーワードと当該検索キーワードの検索式との入力を受け付けする入力部と、
前記パススキーマ生成部によって生成されたパススキーマの階層を検索する階層検索オートマトンと、前記入力部によって入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成するオートマトン生成部、
前記オートマトン生成部によって生成された単一オートマトンを用いて、前記電子文書の前記検索式の中から、前記ヒットキーワードを検索する検索部と、
前記検索部によって検索された検索結果を出力する出力部と、
を備えることを特徴とする情報検索装置。
【請求項１０】
コンピュータが、
検索対象となる階層構造を有する電子文書を取得し、
取得された前記電子文書に関するパススキーマを生成し、
任意の検索キーワードと当該検索キーワードの検索式との入力を受け付けし、
生成されたパススキーマの階層を検索する階層検索オートマトンと、入力された検索キーワードの前記検索条件を満たすヒットキーワードを検索するキーワード検索オートマトンとからなり、前記階層検索オートマトンの中の前記ヒットキーワードが存在するヒット階層ノードと前記ヒットキーワードをあらわすノード集合との間で状態遷移する単一オートマトンを生成し、
生成された前記単一オートマトンを用いて、前記電子文書の前記検索式の中から、前記ヒットキーワードを検索し、
検索された前記検索結果を出力することを特徴とする情報検索方法。                                                                    
【国際調査報告】
2008117454.tif 000046
2008117454.tif 000047