(57)【要約】  本発明の候補パステーブル構築装置は、パスの深さごとに、当該パスの全ての部分パスの各々について、当該部分パスの仮パスＩＤと、当該部分パスが包含している部分パスの仮パスＩＤのリストと、を組としたテンプレートを予め格納するテンプレート格納部（４０）と、パスＩＤを登録し管理するパスＩＤ管理部（３０）と、解析対象パスの全ての部分パスを抽出し、抽出した部分パスの実パスＩＤをパスＩＤ管理部（３０）から取得する処理を行うパス抽出部（２０）と、解析対象パスの深さのテンプレートをテンプレート格納部（４０）から取得し、取得したテンプレート中の仮パスＩＤを、パス抽出部（２０）で取得された、当該仮パスＩＤに対応する部分パスの実パスＩＤに置換し、置換したテンプレートを候補パステーブルとする処理を行うテンプレート適用部（５０）と、を有する。
2009057382.tif 000002
【特許請求の範囲】
【請求項１】
ＸＭＬデータ中のパスを解析対象パスとし、当該解析対象パスの部分パス間の包含関係を表す候補パステーブルを構築する候補パステーブル構築装置であって、
パスの深さごとに、当該パスの全ての部分パスの各々について、当該部分パスの仮パスＩＤと、当該部分パスが包含している部分パスの仮パスＩＤのリストと、を組としたテンプレートを予め格納するテンプレート格納部と、
パスＩＤを登録し管理するパスＩＤ管理部と、
前記解析対象パスの全ての部分パスを抽出し、抽出した部分パスの実パスＩＤを前記パスＩＤ管理部から取得する処理を行うパス抽出部と、
前記解析対象パスの深さのテンプレートを前記テンプレート格納部から取得し、取得したテンプレート中の仮パスＩＤを、前記パス抽出部で取得された、当該仮パスＩＤに対応する部分パスの実パスＩＤに置換し、置換したテンプレートを前記候補パステーブルとする処理を行うテンプレート適用部と、を有する候補パステーブル構築装置。
【請求項２】
ＸＭＬデータ中の、根要素から、子要素を含まない葉要素までのパスを、前記解析対象パスとして検出するパース部をさらに有し、
前記パス抽出部および前記テンプレート適用部は、前記パース部にて検出された解析対象パスに対して前記処理を行う、請求項１に記載の候補パステーブル構築装置。
【請求項３】
前記パス抽出部および前記テンプレート適用部は、前記解析対象パスのパスＩＤが前記パスＩＤ管理部に登録されていない場合にのみ、前記処理を行う、請求項１に記載の候補パステーブル構築装置。
【請求項４】
ＸＭＬデータ中のパスを解析対象パスとし、当該解析対象パスの部分パス間の包含関係を表す候補パステーブルを構築する候補パステーブル構築装置による候補パステーブル構築方法であって、
パスの深さごとに、当該パスの全ての部分パスの各々について、当該部分パスの仮パスＩＤと、当該部分パスが包含している部分パスの仮パスＩＤのリストと、を組としたテンプレートを予め格納するテンプレート格納ステップと、
前記解析対象パスの全ての部分パスを抽出し、抽出した部分パスの実パスＩＤを取得する処理を行うパス抽出ステップと、
前記解析対象パスの深さのテンプレート中の仮パスＩＤを、当該仮パスＩＤに対応する部分パスの実パスＩＤに置換し、置換したテンプレートを前記候補パステーブルとする処理を行うテンプレート適用ステップと、を有する候補パステーブル構築方法。
【請求項５】
ＸＭＬデータ中の、根要素から、子要素を含まない葉要素までのパスを、前記解析対象パスとして検出するステップをさらに有し、
前記パス抽出ステップおよび前記テンプレート適用ステップでは、前記検出された解析対象パスに対して前記処理を行う、請求項４に記載の候補パステーブル構築方法。
【請求項６】
前記解析対象パスのパスＩＤが登録されているか確認するステップをさらに有し、
前記パス抽出ステップおよび前記テンプレート適用ステップでは、前記解析対象パスのパスＩＤが登録されていない場合にのみ、前記処理を行う、請求項４に記載の候補パステーブル構築方法。
【請求項７】
ＸＭＬデータ中のパスを解析対象パスとし、当該解析対象パスの部分パス間の包含関係を表す候補パステーブルを構築するコンピュータに、
パスの深さごとに、当該パスの全ての部分パスの各々について、当該部分パスの仮パスＩＤと、当該部分パスが包含している部分パスの仮パスＩＤのリストと、を組としたテンプレートを予め格納するテンプレート格納手順と、
前記解析対象パスの全ての部分パスを抽出し、抽出した部分パスの実パスＩＤを取得する処理を行うパス抽出手順と、
前記解析対象パスの深さのテンプレート中の仮パスＩＤを、当該仮パスＩＤに対応する部分パスの実パスＩＤに置換し、置換したテンプレートを前記候補パステーブルとする処理を行うテンプレート適用手順と、を実行させるための候補パステーブル構築プログラム。
【請求項８】
ＸＭＬデータ中の、根要素から、子要素を含まない葉要素までのパスを、前記解析対象パスとして検出する手順をさらに有し、
前記パス抽出手順および前記テンプレート適用手順では、前記検出された解析対象パスに対して前記処理を行う、請求項７に記載の候補パステーブル構築プログラム。
【請求項９】
前記解析対象パスのパスＩＤが登録されているか確認する手順をさらに有し、
前記パス抽出手順および前記テンプレート適用手順では、前記解析対象パスのパスＩＤが登録されていない場合にのみ、前記処理を行う、請求項７に記載の候補パステーブル構築プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、候補パステーブル構築装置、候補パステーブル構築方法、候補パステーブル構築プログラムに関する。
【背景技術】
【０００２】
ＸＭＬ(eXtensible  Markup  Language)は、１９９８年に、Ｗ３Ｃ（World  Wide  Web  Consortium）によって勧告されて以来、広く普及してきており、標準的な計算機間のデータ交換フォーマットになっている。また、２００７年１月には、Ｗ３ＣによってＸＱｕｅｒｙが勧告されるなど、ＸＭＬの周辺環境も整ってきている。【０００３】
ＸＭＬデータ（ＸＭＬ文書）は、例えば、図１に示すように、ＸＭＬに準拠して、要素などにより階層的な木構造が構成されるように記述される。【０００４】
要素とは、ＸＭＬデータの基本単位であり、開始タグ、コンテンツ、および終了タグから構成される。例えば、図１において、“<price>100</price>”は要素である。このうち、“<price>”は開始タグ、“100”はコンテンツ、“</price>”は終了タグである。【０００５】
また、要素は、他の要素を含むことができる。例えば、図１において、要素“book”は、要素“price”を含んでいる。このように、各要素は親子関係に見立てることができる。この場合、要素“book”は親要素、要素“price”は子要素となる。また、最上位の親要素（図１では、要素“books”）は、特に、根要素と称される。【０００６】
ＸＭＬデータでは、ＸＭＬデータ中の特定の部分を指し示すために、上述のように各要素を親子関係に見立て、“/a/b/c”のようなパス表記を用いる。例えば、図１において、パスは、一例として、“/books/book/price”と表記される。【０００７】
このようなパス表記を用いてＸＭＬデータの特定の部分を示す言語構文としては、ＸＰａｔｈが挙げられる。ＸＰａｔｈは、ＸＱｕｅｒｙ（ＸＭＬデータを検索するための規格）や、ＸＳＬＴ（XML  Stylesheet  Language  Transformations；ＸＭＬデータ間でデータの変換作業を行うための規格）において重要な役割を担っている。【０００８】
ＸＰａｔｈでは、ＸＰａｔｈの仕様に従って作られたＸＰａｔｈ式が入力されると、そのＸＰａｔｈ式により指定されたＸＭＬデータ中の特定の部分を検索し抽出する。例えば、図１のＸＭＬデータに対するＸＰａｔｈ式は、“//books//book”や“//books/book”などとなる。ＸＰａｔｈ式において、“//”は“子孫”を表し、“/”は“子”を表す。【０００９】
ＸＰａｔｈ式を高速に処理するためには、ＸＭＬデータ中のパスの包含関係を予め判定しておき、ＸＭＬデータの構造索引を生成しておくことが有効である。【００１０】
ここで、パスの包含関係の定義の例として、次の２つが考えられる。【００１１】
（定義１）
・あるパスＡは、パスＡ中の全ての部分パスによって包含されている。【００１２】
（定義２）
・ある根要素から始まるパスＡは、パスＡ中の全ての部分パスによって包含される。【００１３】
なお、パスＡの部分パスとは、パスＡ中の任意のタグから開始され任意のタグで終了するパスであるものとする。【００１４】
例えば、非特許文献１では、ＸＭＬデータベースのキャッシュにおいて、ＸＭＬデータのビットレートを落とさずに利用率を高める目的で、パスの包含関係を利用している。【００１５】
ところで、ＸＭＬデータ中のパスの包含関係を判定する方法としては、以下の２つが考えられる。【００１６】
１）ＸＭＬデータ中の２つのパスの包含関係を必要に応じて判定する方法
２）ＸＭＬデータ中の任意のパスの包含関係を表す表を予め保持しておく方法
ＸＭＬデータ中のパスの包含関係をより高速に判定するためには、２)の方法がよいと考えられる。【００１７】
以下、ＸＭＬデータ中のパスについて、そのパスの部分パス間の包含関係を表す表を候補パステーブル（Candidate  Path  Table）と表記する。【００１８】
また、候補パステーブルにおいて、部分パスの各々には識別子としてユニークなパスＩＤがつけられているものとする。【００１９】
また、候補パステーブルは、パスＩＤと、そのパスＩＤのパスが包含している候補パスのパスＩＤのリストと、を組としたテーブルであるものとする。【００２０】
しかしながら、候補パステーブルの構築は、高速に行うことが困難であるという課題がある。以下にその理由を述べる。【００２１】
候補パステーブルを構築するためには、ＸＭＬデータ中のパスに対して、そのパスの全ての部分パスを抽出する必要がある。【００２２】
例えば、パス“/a/b/c/d/e”には、図２に示すような部分パスが存在する。【００２３】
また、パスの包含関係を上記の定義１として定義した場合、図２に示した部分パス間の包含関係を基にして、パス“/a/b/c/d/e”の候補パステーブルとして、図３に示すような候補パステーブルが構築される。【００２４】
ＸＭＬデータの解析には、標準ＡＰＩ（Application  Program  Interface）であるＳＡＸ（Simple  API  for  XML）やＤＯＭ（Document  Object  Model）が用いられる。【００２５】
ＳＡＸは、ＸＭＬデータを先頭から読み込み、要素が出現する毎に処理手順を呼び出す方式である。【００２６】
一方、ＤＯＭは、ＸＭＬデータをメモリ上に読み込んでツリー構造として保持する方式である。【００２７】
しかしながら、ＤＯＭは、ＸＭＬデータの全てを読み込むため処理に時間がかかり、また、大規模なＸＭＬデータを扱う場合には多くのメモリを消費する。【００２８】
そのため、候補パステーブルの構築には、ＳＡＸが適している。【００２９】
以下、ＳＡＸを用いた候補パステーブル構築方法について説明する。【００３０】
まず、ＸＭＬデータを先頭から読み込み、要素が出現する毎に、これまでに出現した要素との組み合わせを基に部分パスを抽出する。このときに抽出された部分パスをパスＡとすると、パスＡに対して以下の２つの作業を行う。【００３１】
１）パスＡを包含している部分パスを探し、候補パステーブルには、探した部分パスの候補パスとして、パスＡのパスＩＤを登録する。【００３２】
２）パスＡが包含している部分パスを探し、候補パステーブルには、パスＡの候補パスとして、探した部分パスのパスＩＤを登録する。【００３３】
ところで、上述したＳＡＸを用いた候補パステーブルの構築方法においては、最上位の親要素からn番目の深さの要素が出現した場合には、(n){(n+1)/2}個の部分パスが存在することになり、各部分パスを抽出し、上記の手順を実行することになる。【００３４】
しかしながら、特に、上述した１)、２)の処理は、これまでに出現した全ての部分パスに対して現在の部分パスとの包含関係を判定する必要があるため、候補パステーブルの構築に時間が掛かってしまうという課題がある。
【非特許文献１】朴大一、遠山元道、「ＸＭＬデータベースにおけるキャッシュ管理手法の提案」、第１６回データ工学ワークショップ（ＤＥＷＳ２００５）、２００５年３月
【発明の開示】
【００３５】
そこで、本発明の目的は、上述した課題を解決する候補パステーブル構築装置、候補パステーブル構築方法、候補パステーブル構築プログラムを提供することにある。
【００３６】
上記目的を達成するために本発明の候補パステーブル構築装置は、
ＸＭＬデータ中のパスを解析対象パスとし、当該解析対象パスの部分パス間の包含関係を表す候補パステーブルを構築する候補パステーブル構築装置であって、
パスの深さごとに、当該パスの全ての部分パスの各々について、当該部分パスの仮パスＩＤと、当該部分パスが包含している部分パスの仮パスＩＤのリストと、を組としたテンプレートを予め格納するテンプレート格納部と、
パスＩＤを登録し管理するパスＩＤ管理部と、
前記解析対象パスの全ての部分パスを抽出し、抽出した部分パスの実パスＩＤを前記パスＩＤ管理部から取得する処理を行うパス抽出部と、
前記解析対象パスの深さのテンプレートを前記テンプレート格納部から取得し、取得したテンプレート中の仮パスＩＤを、前記パス抽出部で取得された、当該仮パスＩＤに対応する部分パスの実パスＩＤに置換し、置換したテンプレートを前記候補パステーブルとする処理を行うテンプレート適用部と、を有する。
【００３７】
上記目的を達成するために本発明の候補パステーブル構築方法は、
ＸＭＬデータ中のパスを解析対象パスとし、当該解析対象パスの部分パス間の包含関係を表す候補パステーブルを構築する候補パステーブル構築装置による候補パステーブル構築方法であって、
パスの深さごとに、当該パスの全ての部分パスの各々について、当該部分パスの仮パスＩＤと、当該部分パスが包含している部分パスの仮パスＩＤのリストと、を組としたテンプレートを予め格納するテンプレート格納ステップと、
前記解析対象パスの全ての部分パスを抽出し、抽出した部分パスの実パスＩＤを取得する処理を行うパス抽出ステップと、
前記解析対象パスの深さのテンプレート中の仮パスＩＤを、当該仮パスＩＤに対応する部分パスの実パスＩＤに置換し、置換したテンプレートを前記候補パステーブルとする処理を行うテンプレート適用ステップと、を有することを特徴とする。
【００３８】
上記目的を達成するために本発明の候補パステーブル構築プログラムは、
ＸＭＬデータ中のパスを解析対象パスとし、当該解析対象パスの部分パス間の包含関係を表す候補パステーブルを構築するコンピュータに、
パスの深さごとに、当該パスの全ての部分パスの各々について、当該部分パスの仮パスＩＤと、当該部分パスが包含している部分パスの仮パスＩＤのリストと、を組としたテンプレートを予め格納するテンプレート格納手順と、
前記解析対象パスの全ての部分パスを抽出し、抽出した部分パスの実パスＩＤを取得する処理を行うパス抽出手順と、
前記解析対象パスの深さのテンプレート中の仮パスＩＤを、当該仮パスＩＤに対応する部分パスの実パスＩＤに置換し、置換したテンプレートを前記候補パステーブルとする処理を行うテンプレート適用手順と、を実行させることを特徴とする。
【００３９】
本発明の候補パステーブル構築装置は、パスの深さごとに、そのパスの部分パス間の包含関係を、部分パスの仮パスＩＤで表したテンプレートを予め格納しておく。そして、解析対象パスの部分パスを抽出して実パスＩＤを取得し、解析対象パスの深さに応じたテンプレート中の仮パスＩＤを実パスＩＤに置換するだけで候補パステーブルを構築する。
【００４０】
そのため、候補パステーブルの構築に際して、解析対象パスごとに、その解析対象パスの部分パス間の包含関係を判定する必要がないため、候補パステーブルを高速に構築することができるという効果が得られる。
【図面の簡単な説明】
【００４１】
【図１】ＸＭＬデータの例を示す図である。
【図２】あるパスの部分パスとその部分パスのパスＩＤの例を示す図である。
【図３】図２に示した部分パス間の包含関係を基に構築された候補パステーブルの例を示す図である。
【図４】本発明の一実施形態の候補パステーブル構築装置の構成を示すブロック図である。
【図５】図４に示したパス抽出部により解析対象パスから抽出された部分パスとその部分パスのパスＩＤの例を示す図である。
【図６】図４に示した候補パステーブル構築装置による候補パステーブル構築方法を説明するフローチャートである。
【図７】図４に示したパス抽出部により解析対象パスから抽出された部分パスとその部分パスのパスＩＤの例を示す図である。
【図８】図４に示したテンプレート格納部に格納されたテンプレートの例を示す図である。
【図９】図４に示したテンプレート適用部により構築された候補パステーブルの例を示す図である。
【図１０】図４に示したテンプレート格納部に格納されたテンプレートの他の例を示す図である。
【図１１】図４に示したテンプレート適用部により構築された候補パステーブルの他の例を示す図である。
【発明を実施するための最良の形態】
【００４２】
以下に、本発明を実施するための最良の形態について図面を参照して説明する。【００４３】
図４は、本発明の一実施形態の候補パステーブル構築装置の構成を示す図である。【００４４】
図４に示すように、本実施形態の候補パステーブル構築装置は、ＳＡＸパース部（SAX  Parser）１０と、パス抽出部２０と、パスＩＤ管理部３０と、テンプレート（template）格納部４０と、テンプレート適用部５０と、を有している。【００４５】
ＳＡＸパース部１０は、ＸＭＬデータが入力されると、入力されたＸＭＬデータ中の「根要素から葉要素までのパス」を解析対象パスとして検出し、検出した解析対象パスをパス抽出部２０へ渡す。【００４６】
ここで、「葉要素」とは、子要素を含まない要素を指す。【００４７】
例えば、パス“/a/b/c/d/e”の場合、途中に検出されるパス“/a/b”やパス“/a/b/c”などは、子要素を含むため、「根要素から葉要素までのパス」ではない。【００４８】
パス抽出部２０は、ＳＡＸパース部１０から渡された解析対象パスの全ての部分パスを抽出する。ここでは、部分パスの抽出方法として、まず、解析対象パスの最上位の親要素（根要素）を先頭とする部分パスを順に抽出していき、以降、先頭の親要素を１つずつずらしながら、部分パスを抽出していく方法を用いる。深さが５であるパス“/#1/#2/#3/#4/#5”から部分パスを抽出する順序の例を図５に示す。【００４９】
また、パス抽出部２０は、抽出した部分パスをキーにしてパスＩＤ管理部３０への問い合わせを行い、その部分パスのパスＩＤを実パスＩＤとして取得する。【００５０】
パスＩＤ管理部３０は、パスとパスＩＤとの組を登録し管理する。【００５１】
例えば、パスＩＤ管理部３０は、パス抽出部２０からパスの問い合わせを受けた場合、そのパスのパスＩＤが登録済みであれば、登録済みのパスＩＤを返し、また、そのパスがパスＩＤの登録されていない新たなパスであれば、新たなパスＩＤを生成して返す。【００５２】
また、パスＩＤ管理部３０は、パス抽出部２０からパスの問い合わせを受けた場合、そのパスのパスＩＤがすでに登録されているかどうかを返すことも行う。【００５３】
テンプレート格納部４０は、パスの深さごとに、ある深さのパスの全ての部分パスの各々について、その部分パスのパスＩＤと、その部分パスが包含している部分パスのパスＩＤのリストと、を組としたテンプレートを予め格納している。なお、テンプレート中のパスＩＤは、実パスＩＤと区別するため、以降、仮パスＩＤと称す。【００５４】
また、テンプレート格納部４０は、テンプレート適用部５０から深さｎのテンプレートの問い合わせを受けた場合、ｎに対応するテンプレートを返す。【００５５】
テンプレート適用部５０は、解析対象パスの深さがｎである場合、テンプレート格納部４０への問い合わせを行って、深さｎのテンプレートを取得する。【００５６】
また、テンプレート適用部５０は、テンプレート格納部４０から取得したテンプレート中の仮パスＩＤを、その仮パスＩＤに対応する部分パスの実パスＩＤであって、パス抽出部２０で取得された実パスＩＤに置換する。【００５７】
さらに、テンプレート適用部５０は、実パスＩＤで置換したテンプレートを、解析対象パスの候補パステーブルとして更新する。【００５８】
以下、図４に示した本実施形態の候補パステーブル構築装置による候補パステーブル構築方法について、図６〜図９を参照して説明する。ここでは、パスの包含関係を上記の定義１として定義するものとして説明する。【００５９】
図６に示すように、ステップ１０１において、ＸＭＬデータが入力されると、ステップ１０２において、ＳＡＸパース部１０は、ＸＭＬデータ中の「根要素から葉要素までのパス」を解析対象パスとして検出する。【００６０】
ここでは、根要素から葉要素までの深さが５であるパス“/f/g/h/i/j”が解析対象パスとして検出され、パス抽出部２０へ渡されたものとする。【００６１】
次に、ステップ１０３において、パス抽出部２０は、解析対象パス“/f/g/h/i/j”のパスＩＤがすでに登録されているかパスＩＤ管理部３０に問い合わせる。【００６２】
もし、解析対象パス“/f/g/h/i/j”のパスＩＤが登録されている場合は、すでに解析対象パス“/f/g/h/i/j”の候補パステーブルは構築済みである。そのため、パス抽出部２０は、処理を終了し、ＳＡＸパース部１０で次の解析対象パスが検出されるまで待機する。【００６３】
一方、解析対象パス“/f/g/h/i/j”のパスＩＤが登録されていない場合、ステップ１０４において、パス抽出部２０は、解析対象パス“/f/g/h/i/j中の全ての部分パスを抽出する。【００６４】
ここでは、部分パスの抽出方法として、まず、解析対象パスの最上位の親要素（根要素）を先頭とする部分パスを順に抽出していき、以降、先頭の親要素を１つずつずらしながら、部分パスを抽出していく方法を用いるものとする。【００６５】
次に、ステップ１０４において、パス抽出部２０は、解析対象パス“/f/g/h/i/jから抽出した部分パスをキーにして、パスＩＤ管理部３０に問い合わせを行って、その部分パスの実パスＩＤを取得する。【００６６】
解析対象パス“/f/g/h/i/jから抽出した部分パスとその部分パスの実パスＩＤのリストの例を図７に示す。【００６７】
次に、ステップ１０６において、パス抽出部２０は、図７に示した解析対象パス“/f/g/h/i/jの部分パスの実パスＩＤのリストと解析対象パス“/f/g/h/i/jの深さが５である旨の情報とをテンプレート適用部５０へ渡し、テンプレート適用部５０は、テンプレート格納部４０に問い合わせを行って、深さ５のテンプレートを取得する。【００６８】
深さ５のテンプレートの例を図８に示す。図８において、テンプレート中の部分パスの順序は、パス抽出部２０による部分パスの抽出順序と同じになっている。【００６９】
次に、ステップ１０７において、テンプレート適用部５０は、テンプレート中の仮パスＩＤを、その仮パスＩＤに対応する部分パスの実パスＩＤであって、ステップ１０５でパス抽出部２０により取得された実パスＩＤに置換する。【００７０】
置換の基準としては、部分パスの抽出順序を用いる。テンプレート中の仮パスＩＤを実パスＩＤに置換した結果の例を図９に示す。【００７１】
その後、ステップ１０８において、テンプレート適用部５０は、テンプレート中の仮パスＩＤを実パスＩＤに置換した結果を既存の候補パステーブルにマージし、候補パステーブルを更新する。【００７２】
なお、本実施形態においては、パスの包含関係を上記の定義１として定義するものとして説明したが、上記の定義２として定義する場合、テンプレート格納部４０に格納される深さ５のテンプレートは、図１０のようになり、また、テンプレート適用部５０により構築される候補パステーブルは、図１１のようになる。【００７３】
上述したように本実施形態においては、ある深さのパスに関して、そのパスと他のパスの包含関係は自明であることを利用して、候補パステーブルを構築する。【００７４】
すなわち、本実施形態においては、パスの深さごとに、そのパスの部分パス間の包含関係を、部分パスの仮パスＩＤで表したテンプレートを予め格納しておく。そして、解析対象パスの部分パスを抽出して実パスＩＤを取得し、解析対象パスの深さに応じたテンプレート中の仮パスＩＤを実パスＩＤに置換するだけで候補パステーブルを構築する。【００７５】
そのため、候補パステーブルの構築に際して、解析対象パスごとに、その解析対象パスの部分パス間の包含関係を判定する必要がないため、候補パステーブルを高速に構築することができるという効果が得られる。【００７６】
また、本実施形態においては、解析対象パスを、「根要素から葉要素までのパス」とするため、候補パステーブル構築のさらなる高速化を図れる。【００７７】
また、本実施形態においては、解析対象パスのパスＩＤが登録済みである場合は、解析対象パスの候補パステーブルは構築済みとして、処理を終了するため、候補パステーブル構築の高効率化およびさらなる高速化を図れる。【００７８】
また、本発明の候補パステーブル構築装置は、上述のように専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行するものであってもよい。コンピュータ読み取り可能な記録媒体とは、フロッピーディスク、光磁気ディスク、ＣＤ−ＲＯＭ等の記録媒体、コンピュータに内蔵されるハードディスク装置等の記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットを介してプログラムを送信する場合のように、短時間の間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合のサーバとなるコンピュータ内部の揮発性メモリのように、一定時間プログラムを保持しているものも含む。【００７９】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解し得る様々な変更をすることができる。【００８０】
本出願は、２００７年１０月３１日に出願された日本出願特願２００７−２８３４４４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2009057382.tif 000003
【図２】
2009057382.tif 000004
【図３】
2009057382.tif 000005
【図４】
2009057382.tif 000006
【図５】
2009057382.tif 000007
【図６】
2009057382.tif 000008
【図７】
2009057382.tif 000009
【図８】
2009057382.tif 000010
【図９】
2009057382.tif 000011
【図１０】
2009057382.tif 000012
【図１１】
2009057382.tif 000013
【国際調査報告】
2009057382.tif 000014
2009057382.tif 000015
2009057382.tif 000016
2009057382.tif 000017