(57)【要約】【課題】Ｘパスクエリーを処理するための簡単で効率的な方法を提供する。【解決手段】少なくとも１つの拡張マークアップ言語（ＸＭＬ）アプリケーションを解析し（１００）、該アプリケーションによって生成されるＸＭＬパス言語（Ｘパス）文字列のリストを生成する（１０２）。このＸパス文字列を処理し（１０４）、１つ以上の一意に定まらないＸパス（ＵＳＸＰ）文字列であって、各々が１つ以上の変数を含むＵＳＸＰ文字列を作成する（１０６）。ＵＳＸＰ文字列を用いてＸＭＬドキュメントに索引付けし（１０８）、オートマトンを生成する（１１０）。Ｘパスクエリーを受け取り（１１２）、オートマトンを介してＸパスクエリーを処理する（１１４）。【選択図】図１
2007026451.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの拡張マークアップ言語アプリケーションを解析し、該アプリケーションによって生成されるＸパス文字列のリストを生成することと、
前記Ｘパス文字列を処理し、１つ以上の一意に定まらないＸパス文字列であって、各々が１つ以上の変数を含む前記一意に定まらないＸパス文字列を作成することと、
前記一意に定まらないＸパス文字列を用いてＸＭＬドキュメントに索引付けし、オートマトンを生成することと、
Ｘパスクエリーを受け取ることと、
前記オートマトンを介して前記Ｘパスクエリーを処理することと、
を含むことを特徴とするＸパスクエリーの処理方法。
【請求項２】
少なくとも１つの拡張マークアップ言語文法規則を解析し、該文法規則によって生成されるＸパス文字列のリストを生成することと、
前記Ｘパス文字列を処理し、１つ以上の一意に定まらないＸパス文字列であって、各々が１つ以上の変数を含む前記一意に定まらないＸパス文字列を作成することと、
前記一意に定まらないＸパス文字列を用いてＸＭＬドキュメントに索引付けし、オートマトンを生成することと、
Ｘパスクエリーを受け取ることと、
前記オートマトンを介して前記Ｘパスクエリーを処理することと、
を含むことを特徴とするＸパスクエリーの処理方法。
【請求項３】
少なくとも１つの構文解析器を解析し、前記解析器によって生成される文字列のリストを生成することと、
前記文字列を処理し、１つ以上の一意に定まらない文字列であって、各々が１つ以上の変数を含む前記一意に定まらない文字列を作成することと、
前記一意に定まらない文字列を用いてドキュメントに索引付けし、オートマトンを生成することと、
クエリーを受け取ることと、
前記オートマトンを介して前記クエリーを処理することと、
を含むことを特徴とするクエリーの処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願の実施形態は、一般的に、ＸＭＬドキュメント等のドキュメント管理に関し、具体的には、Ｘパス文字列に対するクエリーの処理に関する。
【発明の開示】
【発明が解決しようとする課題】
【０００２】
本願は、Ｘパスクエリーを処理するための簡単で効率的な方法を提供することを目的とする。
【課題を解決するための手段】
【０００３】
本願の実施形態は、少なくとも１つの拡張マークアップ言語（ＸＭＬ）アプリケーションを解析し、そのアプリケーションによって生成されるＸＭＬパス言語（Ｘパス）文字列のリストを生成する。次に、これらのＸパス文字列を処理し、１つ以上の一意に定まらない（underspecified）Ｘパス（ＵＳＸＰ）文字列を作成する。このＵＳＸＰ文字列が「一意に定まらない」のは、各々が１つ以上の変数を含むからである。オートマトンを生成するために、このＵＳＸＰ文字列を用いて、ＸＭＬドキュメントに索引付けできる。次に、Ｘパスクエリーを受け取ると、本願の実施形態は、そのＸパスクエリーが上記オートマトンのＸパス文字列と一致するか否かを判定するために、このオートマトンを介してＸパスクエリーを処理できる。
【０００４】
このＸＭＬドキュメントの索引付けは、オートマトン内に索引を生成し、本願の実施形態は、このオートマトンの索引を参照して、Ｘパスクエリーに一致するオートマトン内の文字列に対応する、一致ＸＭＬドキュメントノードを明らかにする。この索引付けは、１つ以上のマーキングオブジェクトと、ＵＳＸＰ文字列内の各変数とを関連付ける。マーキングオブジェクトは、その変数が表すノードデータを含む。オートマトンを介したＸパスクエリーの処理は、その変数とマーキングオブジェクトとを置換する。これらの変数は、例えば、メタ変数を含むことができる。
【発明を実施するための最良の形態】
【０００５】
以下、添付の図面を参照し、本システム及び方法の様々な例示的な実施形態を詳細に説明する。
【０００６】
ＸＭＬドキュメントをクエリーするためのＸパスの使用は、今や、多くのアプリケーションにおける中心的課題である。Ｘパスは、例えば、いずれもＸＭＬドキュメントの管理に焦点をあてたＸＳＬＴ及びＸＱｕｅｒｙの中核にある。Ｘパスの使用の主な短所は、この形式（formalism）の大半のインプリメンテーションに固有の遅さである。構文解析及びＸパス実行のコストにより、しばしば速度が主要課題である産業的環境においては、対処が困難である。
【０００７】
図１に示されるように、本願の実施形態は、（ステップ１００において）少なくとも１つの文法規則（例えば、拡張マークアップ言語（ＸＭＬ）ソフトウェアアプリケーション）を解析し、ステップ１０２において、その文法規則又は解析器によって生成される文字列（例えば、そのアプリケーションによって生成されるＸＭＬパス言語（Ｘパス）文字列）のリストを生成する。次に、これらの文字列（例えば、Ｘパス文字列）が処理され（ステップ１０４）、一意に定まらないＸパス（ＵＳＸＰ）文字列等といった、１つ以上の一意に定まらない文字列が作成される（ステップ１０６）。これらの文字列が「一意に定まらない」のは、各々が１つ以上の変数を含むからである。換言すれば、これらの一意に定まらない文字列は、変数を含むので「暗示的」文字列であり、暗示的な一意に定まらない文字列に含まれる変数の代わりに値を含む「明示的」文字列と対比される。
【０００８】
一意に定まらない文字列を用いて、ドキュメント（例えば、ＸＭＬドキュメント）に索引付けし（ステップ１０８）、オートマトンを生成する（ステップ１１０）ことができる。後で論じる図３に示されるように、オートマトンは、一意に定まらない文字列における変数の代わりに値を含む、明示的文字列を含む。次に、ステップ１１２でクエリー（例えば、Ｘパスクエリー）を受け取ると、本願の実施形態は、オートマトンを介してそのクエリーを処理でき（ステップ１１４）、そのクエリーが、オートマトン内の明示的文字列の１つと一致するか否かを判定する（ステップ１１６）。
【０００９】
本願では、「オートマトン」を有限状態オートマトンと定義し、これは、複数の状態及びラベル付けされたアークで構成される有向グラフを用いて表され得るネットワークであると見なされてもよい。有限状態ネットワーク内の各状態は、何らかの目的地の状態へと導く０個以上のアークの原点として作用してもよい。初期状態から最終状態へと導く一続きのアークを「パス」と呼ぶ。オートマトンは、そのネットワーク内の一続きのアークが１つのパスに沿った入力文字列と一致する場合には、その入力文字列を受け入れる。有限状態技術の更なる背景は、以下の参照文献で説明されており、ここに参照することにより、本願に背景として組み込む。
ラウリ・カルツネン（Lauri Karttunen），「有限状態技術（Finite-State Technology）」，第１８章，オックスフォード・ハンドブック・オブ・コンピュテーショナル・リングイスティックス（The Oxford Handbook of Computational Linguistics），ルスラン・ミトコフ（Ruslan Mitkov）編，オックスフォード大学出版局（Oxford University Press），２００３年；
ケネス・アール・ビーズリー（Kenneth R. Beesley）及びラウリ・カルツネン（Lauri Karttunen），「有限状態形態論（Finite State Morphology）」，シー・エス・エル・アイ・パブリケーション（CSLI Publications），カリフォルニア州パロアルト，２００３年。
【００１０】
図２に示されるように、図１のドキュメントの索引付け（ステップ１０８）は、オートマトン内に索引を生成し（ステップ２００）、オートマトンの索引を参照して（ステップ２０２）、クエリーと一致するオートマトン内の明示的文字列に対応する一致ドキュメントノードを明らかにする（ステップ２０４）。図３に示されるように、索引付けは、１つ以上のマーキングオブジェクトと、一意に定まらない文字列内の各変数とを関連付ける（ステップ３００）。マーキングオブジェクトは、それらの変数が表すノードデータを含む。オートマトンを介したＸパスクエリーの処理（ステップ１１４）は、変数をマーキングオブジェクトと置換して、オートマトン内に明示的文字列を生成する（ステップ３０２）。これらの変数は、例えば、メタ変数を含むことができる。
【００１１】
一例では、ＸＭＬドキュメントにＵＳＸＰが適用される。これらのＵＳＸＰを適用すると、１つの完全なＸパスに各々が対応する１セットの文字列が生じる。次に、このＸパスのセットは、このＸパスがドキュメントに適用されると返されるＸＭＬノード位置と共に、オートマトン内に格納される。この例では、ＵＳＸＰは/Root/Node[@att=A]であり、ここで「A」は変数である。このＵＳＸＰが以下のＸＭＬドキュメントに適用されるとする。
【００１２】
<Root>
<Node att="1"/>
<Node att="2"/>
<Node att="3"/>
</Root>
/Root/Node[@att=A] → /Root/Node[@att="1"], /Root/Node[@att="2"],
/Root/Node[@att="3"]
【００１３】
これにより、以下の明示的文字列が生成される。
【００１４】
/Root/Node[@att="1"]
/Root/Node[@att="2"]
/Root/Node[@att="3"]
【００１５】
これらの文字列の各々は、上記ＸＭＬノードの１つに対応する１つの完全なＸパスである。これらの文字列は、これらが参照する実際のＸＭＬノードの索引と共に、オートマトン内に格納される。ＵＳＸＰの適用により、明示的文字列及び実際のノードの索引が生成される。
【００１６】
このように、本願の実施形態は、所与のドキュメント文法内で外部データを用いる方法を提供する。その課題は、あらゆる文法をその場で用いることができるように、また、あらゆるユーザがあらゆる種類の情報でその文法を拡充できるように、普遍的且つ多用途な構造を見出すことであった。ＸＭＬは、このニーズに対する良好な解決法として急速に現れた。この形式（formalism）は、人間によって（或る程度）可読であると共にコンピュータによっても管理可能なテキストフォーマットを提供する。本願で開示される方法は、ＸＭＬドキュメントからのあらゆる情報を、カテゴリー、特徴、又は見出し語として自在に解析できるように、この形式に手を加えたものである。換言すれば、ＸＭＬドキュメントをデータベースとして用いることができ、その各データを、本願の実施形態が解析する文の非常に文法的な構造に埋め込むことができる。
【００１７】
本願の実施形態は、この形式を新たな命令で拡充した。この新たな命令は、Ｘパスに基づきＸＭＬノードを読み出すために用いられるものである。このＸパスは、或る段階において、単語の見出し語や表層形式、所与の構文ノードのカテゴリーや特徴等といった、文法からの特定の情報を補助として用いて構築される。次に、特定の属性に制約される特定のマークアップタグを有する所与のＸＭＬノードが実在するか否かをチェックするために、このＸパスは、ＸＭＬファイルに対してテストされる（一度に２つ以上のファイルがチェックされてもよい）。本願の実施形態は、そのＸＭＬノードから或るデータを抽出するための、或る特定の命令を提供する。一例は、以下のＸＭＬデータベースに基づくものである。
【００１８】
2007026451.tif 000003
【００１９】
このＸＭＬデータベースの１つの目的は、所与のフランス語の動詞からの名詞の導出をエンコードすることである。これは、所与の文の全ての可能な候補の解釈が単一のセットの依存関係として正規化される、正規化手順のケースで特に有用である（ブランら（Brun & Al.）［１５］参照）。次のフランス語：Le train arrive en gare（列車が駅に到着する）を例とする。この文を、その文を名詞化したものと置き換えることができる：l'arrivee du train en gare（駅への列車の到着）。次に、このデータベースをクエリーして、その特定の動詞に対応する名詞を提供することができる。次に、このデータベースを、動詞arriverをシードとしてクエリーするＸパスを作成できる。例えば、次のＸパスを用いて、正しい値を返すことができる。
/normalization/entry[@verb="arriver"]/noun
【００２０】
本開示は、Ｘパスを介して直接マッピングされる特定の１セットの命令を提供する。例えば、ＸＭＬノードをテスト又は作成する命令であってもよく、何らかの特定の属性値を単に抽出する命令であってもよい。一度に２つ以上のデータベースを使用可能であってもよく、その場合、各データベースは、ロード時に関連付けられる簡単なエイリアスで識別される。特定の属性値を作成、テスト、又は抽出するために用いられる簡単な命令のリストを以下に示す。各ケースにおいて、@dbは、そのｄｂ（データベース）エイリアスを伴ってロードされたＸＭＬドキュメントを参照する。
【００２１】
@db(/root/name[@val=１])->Create()  そのＸパスに対応する新たなＸＭＬノードを作成する。
@db(/root/name[@val="1"])->Test()  このＸパスが、実在するＸＭＬノードに対応しているか否かをテストする。
@db(/root/name)->GetAttribute(value,"val")  このＸＭＬノードからvalという属性の値を取得する。
@db(/root/name)->SetAttribute("val",value)  このＸＭＬノードに対してvalという属性の値を設定する。
【００２２】
これらの命令は全て、他の文法的情報と自由に混ぜることができる。例えば、以下の命令は、その値を構文ノードから取得して、その存在をテストする。
2007026451.tif 000004
【００２３】
この命令は、文中の（変数#１と関連付けられた）各ＶＥＲＢ（動詞）について、こちらのデータベース内に、こちらの動詞と同じ見出し語（lemma）を有するＸＭＬノードが存在するか否かをテストすると書かれている（#1[lemma]は、こちらの構文ノードの見出し語を自動的に返す）。
【００２４】
このシステムの１つの長所は、ユーザが自分の特定の言語問題に適していると判断したＤＴＤを、何でも自由に定義できることである。この方法では、任意の言語的タスクに対して、あらゆる種類のデータを、それらの性質、内容、又は構成に対するいかなる制約もなく、使用可能にできる。
【００２５】
しかし、メモリ内でのこれらのファイルのサイズは、かなり大きくなり得る。Ｘパス評価の速度は、たとえ高速のコンピュータ上でも、非常に遅くなりがちである。ＸＭＬファイルが大きいほど、性能は悪くなる。サイズ問題が頻繁に生じる場合には、従来はコンピュータメモリを増設していたが、それはもはや本当の問題ではない。一方、速度こそが本当の問題である。本願の実施形態は、できるだけ高速でＸパスを実行するために専用に設計されたライブラリであるｌｉｂｘｍｌを用いるが、それにも関わらず、ＸＭＬドキュメントが大きい場合には、たとえ高速機上であっても、単一のＸパスを実行するのに、かなりの時間が必要となり得る（例えば、１〜１０ミリ秒）。これは、各文について、一度に２つ以上のＸパスを実行する場合には、非常に遅い。この固有の遅さを説明する主たる理由は、完全さが必要なことである。このシステムは、全てのＸＭＬノードが正しく評価されていることを確認するために、ファイル全体を完全にトラバースしなければならない。ファイルが非常に大きい場合には、必要な時間は計り知れないと言えよう。
【００２６】
Ｘパスは、今日のほとんどのＸＭＬシステムの中心的なコンポーネントであるので、この問題に対処するための多くの研究が行われていることは、驚くことではない。これらの解決法の幾つかは、Ｘパスを解析する最良の方法に焦点をあてたものであり、その他の解決法は、ファイル全体ではなく索引に対してＸパスを適用するために、ＸＭＬドキュメントに索引付けする何らかの方法を提案している。しかし、これらの解決法は複雑になりがちである。従って、本願の実施形態は、スクリプト命令内に存在するＸパスに基づく、ＸＭＬドキュメントに索引付けするための簡単で効率的な方法を提供する。
【００２７】
本願の実施形態では、所与のテキストに対して文法が実行される際に、現在の文法に対して何も規則が追加されないことが、その設計からすぐにわかるという意味において、文法は静的オブジェクトであると見なされる。この弱い前提からの演繹により、実行時には全てのＸパス命令がわかっているものとする。本願の実施形態は、全てのＸパス上のＸＭＬデータベースドキュメントに索引付けするのではなく、標準形のＸパス上のＸＭＬデータベースドキュメントのみに索引付けする。標準形Ｘパスとは、子（daughter）、親（parent）等といった特定の内部命令を何ら含まないものである。しかし、スクリプト言語では、これらのＸパスの一部は、何らかの特定のギャップを有することがあり、完全なＸパス表現ではないことがある。実際に、何らかの言語的データが完全であることを要する表現は、実行時のみにわかるものであり得る。例えば、以下のようなものである。
2007026451.tif 000005
【００２８】
この例では、/derivation/entry[@verb=#１[lemma]]というＸパスは、完全になるためには、構文ノード＃１の見出し語の形態を知る必要がある。
【００２９】
本願の実施形態は、Ｘパスを文字列であると見なす。本願の実施形態では、Ｘパス命令をキャッシュに格納し、遅くてコストのかかるＸパス評価の実行を回避するので、システムの速度が向上する。全てのＸパスが予めわかっているので、それらの文字列の形態は解析中に一貫して同じであると推論することができる。同じ動詞の見出し語が何度も見出される場合には、上述の規則によって生成されるＸパス文字列は、全てのケースにおいて同じである。
【００３０】
本願の実施形態は、規則の適用によって生成される文字列に索引を設ける。Ｘパスに基づく規則が適用されると、言語的な情報に基づきＸパス文字列が生成され、次に、この文字列が既に評価済であるか否かを確認するために、索引に対してテストされる。既に評価済である場合には、索引は、その文字列即ちそのＸパスに対応するＸＭＬノードを返す。
【００３１】
当然ながら、全てのＸパスが予め完全にわかっているわけではないという事実に関わらず、ＸＭＬドキュメントの索引付けには多くの方法がある。その１つは、１つの索引に、複数の異なるＸパスを直ちに格納することである。換言すれば、所与の文に対して計算される新たな各Ｘパスに対して、まず、その索引に対するテストが行われ、その索引がいかなる回答も返さない場合には、システムは、実際のＸパス評価に進む。しかし、このシステムは、既に評価済のＸパスに対しては非常に効率的であるが、新たなＸパスに対しては非常に非効率である。
【００３２】
他の可能性としては、まず、所与の文法における全ての有効なＸパス表現を取り出し、それらの文字列内の動的な部分、例えば言語的データに基づく部分を、メタ変数によって置き換えることがある。このように、本願の実施形態は、これらのメタ変数がエンジンによって検出され認識され得るように、ｌｉｂｘｍｌ Ｘパス評価モジュールを修正している。１つのメタ変数が評価される場合には、Ｘパスエンジンは、挙動が正則的であるそのノード又はその属性の値をテストしないが、現在のＸＭＬノードに、そのメタ変数の評価を含むオブジェクトを格納する。ＸＭＬドキュメント全体がトラバースされたら、本願の実施形態は、そのドキュメントに２回目のトラバースを行い、どのＸＭＬノードが評価済みであるかを検出する。次に、本願の実施形態は、そのＸＭＬノードに格納された特定のオブジェクトを読み出し、この情報を用いて、予め評価済のＸパス文字列のファミリーを生成する。次に、これらの文字列は、一致するＸＭＬノードへのポインタと共に、索引に格納される。
【００３３】
例えば、本願の実施形態に、/derivation/entry[@verb=#1[lemma]]というパスが入力された場合には、それらは、その表現の動的な部分である#1[lemma]を見つけ出し、それをメタ変数である#1と置き換えると、/derivation/entry[@verb=#1]となる。２つ以上の動的な部分が見つかった場合には、これらの各動的な部分は別のメタ変数と置き換えられる。
/derivation/entry[@verb=#1[lemma] and @number=#1[number]] →
/derivation/entry[@verb=#1 and @number=#2]
【００３４】
次に、ＸＭＬエンジンは、こちらのＸＭＬデータベースにこのＸパスを適用し、メタ変数#１及び#２が、ＸＭＬドキュメント内で見出された全ての実際の値と置き換えられた、全ての可能な候補の文字列を生成する。この方法を、先に例として与えられた短いＸＭＬドキュメントに適用した場合には、システムは、以下の文字列を、それらが一致するＸＭＬノードへのポインタと共に生成する。
2007026451.tif 000006
【００３５】
標準的なＸパス表現の評価中に、その標準的なＸパス表現は、索引に対してテストされる。この評価が失敗した場合には、単に、そのＸパス表現が、そのデータベースドキュメント内のどのＸＭＬノードとも一致しないことが意味される。その他の解析は必要ない。しかし、新たなＸＭＬノードが直ちに作成される場合（新たなＸＭＬノードは標準的表現でのみ作成可能）には、その作成に用いられた対応するＸパス文字列が、新たなＸＭＬノード上の対応するポインタと共に、索引に格納される。最後に、子（daughter）や親（parent）等の関数を含む複雑なＸパス表現は、依然として、正則Ｘパス表現として評価され、全体の処理速度が遅くなり得ることを留意されたい。
【００３６】
索引は、文字オートマトンとして実装される。これは、コンパクトな、文字列の索引手段である。このオートマトンは、Ｃ＋＋等の任意の形態のプログラミング言語で実装できる。オートマトンは、文字列が認識された際に読み出されるポインタを端末ノードが格納できるように設計されている。次に、本願の実施形態は、このオートマトンを用いて、Ｘパス表現を、それらのＸＭＬポインタのリストと共に格納する（１つのＸパスが、２つ以上のＸＭＬノードと一致してもよい）。以下のＸパス表現を格納するオートマトンの一例を、以下に示す。
/Dict/Verb/Entree[@lemma="use"] 
/Dict/Verb/Entree[@lemma="formulate"] 
/Dict/Verb/Entree[@lemma="eat"] 
/Dict/Noun/Entree[@lemma="system"]
/Dict/Noun/Entree[@lemma="information"] 
/Dict/Noun/Entree[@lemma="dog"]
【００３７】
以下のオートマトンは、６つの可能な候補のＸパスから、属性@lemmaを変数として、構築されたものである。
2007026451.tif 000007
【００３８】
このように、本願の実施形態は、計算効率の速度向上のための、Ｘパスクエリーを処理する新たな方法を提示する。この方法は、所与のドキュメントの新たな各インスタンスに対して、Ｘパスクエリーを格納するためのオートマトンを構築することを含む。次に、新たなＸパスは、ドキュメント自体に適用される前に、常に、まずこのオートマトンに対してテストされる。本願の実施形態は、Ｘパスコマンドが既知であり、前処理を受け得るケースについて考える。
【００３９】
本願の実施形態は、絶対Ｘパスのみを考慮する。従って、本願の実施形態は、実行時に計算される、ＸＭＬノードに対する相対Ｘパス表現は、キャッシュに格納しない。更に、本願の実施形態は、特定のＸパスエンジンに対する解決法の基礎をなすものではない。むしろ、本願の実施形態は、単に、ユーザのニーズに従って修正可能なＸパスエンジンの実装形態が存在すると想定しているに過ぎない。例えば、本願の実施形態は、ｌｉｂｘｍｌに基づいて実装されている。本願の実施形態は、一意に定まらないＸパス（UnderSpecified XPath：以下ＵＳＸＰと呼ぶ）を、特定の値（ＸＭＬマークアップタグの名称又は属性値）が変数と置き換えられた、任意のＸパス表現として参照する。また、本願の実施形態は、ＸＭＬドキュメントが、ドキュメント・オブジェクト・モデル、即ちＤＯＭを介して扱われるものと想定している。
【００４０】
より具体的には、一意に定まらないＸパスとは、動的な部分が変数によって置き換えられたＸパスである。本願の実施形態は、Ｘパスの動的な部分、即ち、これらのＸパスを処理するプログラムによって抽出された値によって実行時にインスタンス化されるＸパスの部分を参照する。
2007026451.tif 000008
【００４１】
この例では、ＸＭＬファイルは、所与の単語に関する特定の情報を見出すためにクエリーされ得る辞書をモデル化している。このＸＭＬファイルは、/Dict/Noun/Entree[@lemma="dog"]というＸパスによってクエリーされ得る。ここで、このＸＭＬファイルを用いるシステムは、実行時に@lemma属性が動的に生成されるＸパスを確実に操作する。この@lemmaは、本願の実施形態が、Ｘパス表現の変数部分として参照するものである。次に、本願の実施形態は、このＸパスに基づき、@lemma部分が特定の変数と関連付けられたＵＳＸＰを構築できる。
/Dict/Noun/Entree[@lemma="#1"]
【００４２】
本願の例では、これらの変数を示すために＃ｎを用いる。この表示は、本願明細書で単に一例として用いるものである。これらの変数は、ドキュメント・オブジェクト・モデル、即ちＤＯＭとして格納されているドキュメントの内部ツリー構造に従ってインスタンス化される。ＤＯＭは、ＸＭＬドキュメントのマークアップノードを、Ｃ＋＋やＪａｖａ（登録商標）等のプログラミング言語におけるオブジェクトとして扱う従来の方法である。ＤＯＭはツリー状構造であり、各ノード又は各属性がオブジェクトである。本願の実施形態は、特定のＸＭＬノード又は特定の属性が特定の一意に定まらないＸパスの部分として識別されたことをマークするために本願の実施形態が用いる特定のフィールドによって、これらのオブジェクトの構造が拡充されるものと想定する。
【００４３】
一例として、/Dict/Noun/Entree[lemma="#1"]というＵＳＸＰがドキュメントに適用される。次に、ＵＳＸＰの部分として識別されたシステム内の各ＤＯＭオブジェクトである/Dict/Noun/Entreeがマークされる。
2007026451.tif 000009
【００４４】
対応するＸパスの構築は、Ｘパスエンジンの簡単な修正を意味する。本願の実施形態は、処理自体には手を加えず、単に、Ｘパスエンジンによって変数として認識される特定の文字列をＸパス宣言に導入する。例えば、本願の実施形態は、特定の意味論を用いて、"#１"等の文字列を変数として定義できる。１つのノードが、変数が宣言されているＸパスの部分に対して一致する度に、本願の実施形態は、現在のノードに、それがＸパスエンジンによって受け入れられたノードに属することを示す特定のマークを追加する。このケースにおけるこのマークは、変数の索引を、ノードの名称や所与の属性の値に対応する文字列と共に記録する、特定のオブジェクトである。
【００４５】
ここで、本願の実施形態が、ＸパスエンジンにＵＳＸＰを入力として適用すると、システムは、そのＵＳＸＰと一致するＸＭＬノードのリストを生成する。本願の実施形態が必要とする、異なる値をリカバするために、本願の実施形態は、単に、得られた各ＸＭＬノードから開始して、ＤＯＭ階層を後方にトラバースする。上る途中の各ノードについて、本願の実施形態は、それが、変数に対する可能な候補のターゲットとしてマークされているか否かをチェックする。マークされている場合には、本願の実施形態は、そのノード（ＸＭＬノード又は属性ノードであり得る）の値を特定の構造で保持し、これは、本願の実施形態が、対応するＸパスを再生するために、後で用いる。
【００４６】
本願の実施形態は、各一致するノードに対して格納されるオブジェクトが、次の構造を有すると想定している：構造マーキング｛文字列値；整数索引；｝。値とは、本願の実施形態が対象とするノードの値である。索引は、そのノードをマークするために用いられた変数の索引である。ノードがマークされる度に、本願の実施形態は、本願の実施形態が対象とする文字列及び、そのノードと一致する変数の索引と共に、構造を記録する。
【００４７】
この再生のアルゴリズムの一例を、以下に疑似コードで示す。GenerateXPathにおいて、変数は以下の意味を有する。
a）"origin"（原点）は、ＵＸＳＰの処理によって生じるノードの１つである。
b）"node"（ノード）は、現在のＸＭＬノードである。これは、まず"origin"でインスタンス化される。
c）"usxp"は、ノードの初期リストの生成に用いられるＵＸＳＰである。Ｘパスにおいて、各変数は文字列"#index"であり、index（索引）は整数である。
d）"attributes"（属性）は、各変数に対する文字列が、それらの索引に従って格納されるベクトルである。
【００４８】
2007026451.tif 000010
【００４９】
一例として、本願の実施形態は、/Dict/Noun/Entree[lemma="#1"]というＵＳＸＰをドキュメントに適用するものとする。本願の実施形態は、各ＸＭＬノードに特定のマーキングオブジェクトを関連付ける。
2007026451.tif 000011
【００５０】
本願の実施形態が、上記ドキュメントにこのＸパスを適用した場合には、本願の実施形態は３つのノードのリストを生成する。これらの各ノードに対して、本願の実施形態はGenerateXPathを参照し、これにより以下のＸパス文字列が生じる。
/Dict/NOUN/Entree[lemma="information"]
/Dict/NOUN/Entree[lemma="system"]
/Dict/NOUN/Entree[lemma="dog"]
【００５１】
ＵＳＸＰにおいて、発生した"#１"の各々は、その値と置き換えられる。次に、本願の実施形態は、これらのＸパスを、得られたそれらのノードと共に、オートマトンに格納する。
【００５２】
このＸＭＬドキュメントに索引付けする際に、本願の実施形態は、この時点で、ＵＳＸＰに対応する全ての可能な候補のＸパスのリストを有する。これらの再生された各Ｘパスは、本願の実施形態がオートマトン又はデータベースに格納できる文字列である。次に、このオートマトンを用いて、まず、Ｘパスが有効なものであるか否かがチェックされる。このオートマトンの使用により、これらの文字列を格納するためのコンパクト且つ速い方法が可能になる。
【００５３】
実行時に、システムが、ＸＭＬドキュメントの索引付けに用いられたＸパスの適用を必要とする場合には、最初のステップで、このＸパスをオートマトンに対してテストする。このＸパスが認識されない場合には、クエリーは失敗し、認識された場合には、文字列と関連付けられたオートマトンに格納されたＸＭＬノードのリストが、値として返される。
【００５４】
以下のオートマトンは、６つの可能な候補のＸパスから、属性@lemmaを変数として構築されたものである。
2007026451.tif 000012
【００５５】
この例でわかるように、本願の実施形態は文字オートマトンを用いる。これは、異なるＸパスの文字列の記録のみを行い、それらの内部構造の解析を試みることはない。
【００５６】
本願の実施形態は、任意のテキスト（生テキスト又はＸＭＬ）を入力として、言語的単位に対して増分的に文法規則を適用する、構文解析器で良好に作用する。以下の例では構文解析器について論じるが、本発明は構文解析器に限定されず、任意の索引付け構成で有用であることを、当業者は理解しよう。例えば、言語的単位は、その文法自体によって定義される、文、段落、又はテキスト全体であってもよい。例えば、４段落で１００文のドキュメントは、以下のように処理することができる。
ａ）文法をドキュメント全体に適用する場合には１ステップ。
ｂ）文法を各段落に適用する場合には４ステップ。
ｃ）文法を各文に適用する場合には１００ステップ。
【００５７】
構文解析器は、ＸＭＬ出力、Ｃ＋＋オブジェクト構造（システムがライブラリとして用いられる場合）、又は、括弧で括られた構造としてのチャンクツリー及びそのチャンクツリーのノードに関する依存関係のリストを伴うより伝統的な出力等といった、様々な種類の出力を提供する。複数の規則が次々と適用され、規則が成功するか又は失敗するかが判定される。システムは、どの規則に対しても引き返すことはないので、本願の実施形態は、自らを組み合わせ的爆発に追い込むことはできない。
【００５８】
構文解析は、３つの異なる段階で行うことができる。
１）チャンキングと共に品詞のあいまい性を除去する。
２）正規表現に基づき、そのチャンクシーケンスにわたる単語間の依存関係を抽出する。
３）新たな依存関係の生成、又は既存の依存関係の修正や削除のために、これらの依存関係をブール演算子と組み合わせる。
【００５９】
以下に、本願の実施形態によって処理され、依存関係の幾つかがチャンクツリーの異なる部分から抽出された文の一例を示す。
The chunking rules define and produce a chunk tree.
（チャンキング規則はチャンクツリーを定義すると共に生成する。）
【００６０】
段階１
最初の段階では、文に対してチャンキング規則が適用され、以下のチャンクツリーが生成される。
2007026451.tif 000013
【００６１】
段階２
次のステップでは、そのツリー上の幾つかの基本的な依存関係を抽出する。これらの依存関係は、特定のサブツリー構成に生じたノードの接続のみを行う、幾つかの非常に基本的な規則を用いて抽出される。
SUBJ(define,rule)
VCOORD(define,procedure)
【００６２】
ＳＵＢＪは主語関係であり、ＶＣＯＯＲＤは２つの動詞間の同格関係である。主語１を抽出する典型的な規則は、次のものである。
| NP[?*, noun#1], FV[verb#2]| SUBJ(#2,#1)
【００６３】
ここで、#１及び#２は、互いに隣り合った名詞句（ＮＰ）及び定形動詞（ＦＶ）の語彙的サブノードと関連付けられた２つの変数である。“NP[...]”は、ノードＮＰの下にあるサブノードの探査を示す。
【００６４】
段階３
最後の段階では、これまでに抽出された依存関係に基づいて新たな依存関係を生成するために、簡単なブール表現が用いられる。
例えば、本願の実施形態は、以下の依存関係を生成する。
SUBJ(produce,rule)
【００６５】
以下の規則を用いる。
If (SUBJ(#2#VERB,#1#NOUN) & VCOORD(#2#VERB,#3#VERB)) SUBJ(#3,#1)
【００６６】
この規則には、次のことが書かれている。動詞（＃２）及び名詞（＃１）について主語が抽出され、この動詞（＃２）と他の動詞（＃３）との間に動詞の同格関係が見出された場合には、＃３は＃２と同じ主語を有する。
【００６７】
これらの典型的な文法規則と共に、本願の実施形態は、文法規則の出力と直接組まれる特殊化されたプログラミング言語を提供する。本願の実施形態は、文の言語データに迅速にアクセスするために、文から構築される内部言語データ構造を利用する。このプログラミング言語は、趣向の異なる変数（整数、浮遊、文字列、アレイ、構造）と、大量の演算から文字列操作までの様々な命令の大きなセットとを提供する。この言語は、豊富なＸＭＬ命令のセットも提供する。例えば、ＸＭＬファイルの構文解析中に、又は言語的な断片から直ちにＸＭＬファイルを作成するために、対象となっている現在のＸＭＬノードの性質をテストすることも可能である。更に、スクリプト命令は、文法規則と混ぜることが可能であり、これにより、文法学者（grammarian）が、自分たちの規則に、通常では処理が困難な何らかの特別な操作を導入できるようになる。例えば、テキスト内でそれまでに見出された全てのＮＰをアレイとして記録して、所与の前方照応代名詞の最も可能性が高い先行詞を見出すだめに、この情報を用いることができる。本願の実施形態は、次の節で、本願の実施形態が、ＸＭＬドキュメントをデータベースとして用いるために、このスクリプト言語をどのように利用するかを説明する。
【００６８】
構文解析器のゴールは、最終的に、チャンクツリーのノード間の、主語や直接目的語等といった構文的依存関係を計算することである。本願の実施形態は、言語的な単位を品詞のシーケンスに翻訳することから開始する。１回目のパスでは、このシーケンスのあいまい性が除去され、チャンキングされる。２回目のパスでは、前の結果が正規表現に翻訳され、チャンクツリーにおけるそれらの構成に従って、単語間の基本的な依存関係が抽出される。最後のパスでは、新たな依存関係の作成をトリガするために、それらの依存関係に演繹規則を適用する。これらの演繹規則は、既存の依存関係の修正又は削除を行うこともできる。
【００６９】
Ｘパスは、ほとんどのＸＭＬシステムの中核を成すものである。例えば、従来のシステムの１つは、Ｘパスを用いてドキュメントをクエリーする。最初のステップでは、ＸＭＬドキュメントが格納され、データベース内で索引付けされる。次に、これらのドキュメントから情報を読み出すために、ＸパスがＳＱＬクエリーに翻訳される。この処理は複雑であり、ＸＭＬドキュメントのストリーミングに用いることはできない。
【００７０】
別の従来の方法は、ボトムアップ・アルゴリズムを用いて、リーフから開始して最上部のノードまで上りながらＸパスを解析するものである。しかし、これらの方法は全て、実行時にＸパスを完全に解析し、次にその結果をＸＭＬドキュメントに対して直接テストする点で、又は、特定のノードを予めチェックする処理の速度を高めるための何らかの索引付け方法で改良されているという点で、共通している。
【００７１】
一方、本願の実施形態は、単一のパスで、一旦、全てのドキュメントに対して一意に定まらないＸパスを適用するので、単一の命令に対してＸパスの全ファミリーを適用する処理が減少する。本願の実施形態による文字オートマトンへの翻訳により、特定のＸパスを適用する速度が、システムを新たなＸパスドキュメントのトラバースに駆り立てないことが確実になるので、効率が高い。
【００７２】
ほとんどの研究チームは、処理速度の向上のために、多重索引付けによるツリーのトラバースの改善を試みているが、それらの索引付け機構は、多重索引を有する複雑なテーブルを含むので、かなり複雑で重くなりがちである。
【００７３】
ツリーオートマトンの使用は既に文献に記載されており、これらのオートマトンは、Ｘパス表現の構文解析をエンコードする手段として、又は、既に見出されているサブシーケンスをエンコードする手段として用いられている。しかし、ツリーオートマトンと文字列オートマトンとを混同すべきではない。ツリーオートマトンは、容易に実行可能な構造内の演算式等の複雑な表現を処理する方法であり、一方、文字オートマトンは、単に、多数の文字列を、これらの文字列のいかなる解釈も行うことなく、格納及び抽出する効率的な方法である。
【００７４】
本願の実施形態はＸパス表現のいかなる解読も行わず、Ｘパス表現は処理全体を通して文字列として保持される。これは、Ｘパス表現を処理するために、これらのオートマトンを、Ｘパス表現を理解する方法として用いる従来のシステムと比較した際の、多くの違いのうちの１つである。本願の実施形態は、このＸパス表現を処理せず、Ｘパス表現の表層的な文字列を文字オートマトンと比較する。本願の実施形態は、所与のＸパスに対する等価のＸパスを直ちに計算して、一意に定まらない文字列をオートマトンに格納し、Ｘパスのファミリーの自動処理のための下準備をすることもできる。本願の実施形態は、ドキュメント自体に対して適用される一意に定まらない表現の概念を導入している。本願におけるＸパスの概念は、変数で拡大されており、単一のＸパスではなくＸパスのファミリーを抽出する特定のタスクを有する。また、生成されたＸパス文字列をオートマトンにエンコードすることにより、そのＸパスに対する応答の存在をテストするための迅速且つ効率的な方法、並びに、オートマトンに格納されたノードの効率的な読み出しが確実になる。
【００７５】
本願の自然言語ツールのような実施形態の性能の大半は、そのようなシステムがアクセスし得る情報の豊富さに基づくものである。しかし、様々な情報ソースへのアクセスは、通常、この情報が格納される方法によって制限される。プログラマーは、彼らのシステムのアーキテクチャが極端に重くならないように簡潔にするために、彼らのソフトウェアが外部情報を取得する手段を、僅かな限られたブリッジのみに制限することを好む傾向がある。ＸＭＬの選択の理由は、これらの制限にある。ＸＭＬは、あらゆる種類の構造化データを、機械及び人間が可読なテキストファイルに格納するために使用可能な、汎用のコンテナである。もしＸＭＬが冗長で場所塞ぎであるとしても、簡単であるという長所を有する。今日、ほとんどのデータベースやワードプロセッサは、様々なデータソースをこのフォーマットで自動的にエクスポートする機構を提供している。しかし、情報を抽出するためのＸＭＬの使用は、Ｘパスが遅くて非効率的なので、容易ではない。本願の実施形態は、Ｘパスに基づく簡単なキャッシュ機構とオートマトンとを組み合わせて用いて、システムの性能を劇的に改善するものである。この機構は、自然言語ツールにおいてＸＭＬデータベースが容易に探査可能であることを証明すると共に、あらゆる状況において豊富且つ強力なデータソースを提供する。
【図面の簡単な説明】
【００７６】
【図１】本願の実施形態のフロー図である。
【図２】本願の実施形態のフロー図である。
【図３】本願の実施形態のフロー図である。
【図１】
2007026451.tif 000014
【図２】
2007026451.tif 000015
【図３】
2007026451.tif 000016