(57)【要約】      （修正有）【課題】  ＸＭＬストリームデータを評価するためのオートマトンを差分更新するとともに、そのオートマトンがＸＭＬストリームデータを迅速に処理できるようにすること。【解決手段】  ＸＭＬデータを処理するために入力された更新前ＸＰａｔｈ式を示す更新前ＤＦＡを、入力された更新後ＸＰａｔｈ式を示す更新後ＤＦＡに更新するフィルタエンジン１０であって、更新前ＸＰａｔｈ式と、その更新前ＸＰａｔｈ式から導出した更新前ＮＦＡと、その更新前ＮＦＡから導出した更新前ＤＦＡを管理するオートマトン管理部１５と、更新前ＸＰａｔｈ式と更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式から導出した差分ＮＦＡを管理する更新オートマトン管理部１８と、差分ＮＦＡを用いて、更新前ＮＦＡを更新後ＮＦＡに、更新前ＤＦＡを更新後ＤＦＡに、それぞれ差分更新するＤＦＡ更新モジュール１７と、を有する。【選択図】      図２
2007011998.tif 000002
【特許請求の範囲】
【請求項１】
ＸＭＬデータを処理するために入力された更新前ＸＰａｔｈ式を示す更新前ＤＦＡを、入力された更新後ＸＰａｔｈ式を示す更新後ＤＦＡに更新するＸＰａｔｈ式処理方法であって、
コンピュータが、
前記更新前ＸＰａｔｈ式と、当該更新前ＸＰａｔｈ式から導出した更新前ＮＦＡと、当該更新前ＮＦＡから導出した前記更新前ＤＦＡとを記憶手段に管理するオートマトン管理ステップと、
前記更新前ＸＰａｔｈ式と前記更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式から導出した差分ＮＦＡを記憶手段に管理する更新オートマトン管理ステップと、
前記差分ＮＦＡを用いて、前記更新前ＮＦＡを更新後ＮＦＡに、前記更新前ＤＦＡを前記更新後ＤＦＡに、それぞれ差分更新するＤＦＡ更新ステップと、
を実行することを特徴とするＸＰａｔｈ式処理方法。
【請求項２】
前記ＤＦＡ更新ステップは、前記更新前ＮＦＡに対して、推移に従って状態を順に辿る処理を実行し、当該実行過程において前記更新前ＮＦＡにおける各推移に適合する前記更新前ＤＦＡの推移を特定して、前記更新前ＤＦＡの各状態が保持するＮＦＡ状態群および推移群を確認し、当該ＮＦＡ状態群および推移群と差分ＮＦＡとの差分を更新することを特徴とする請求項１に記載のＸＰａｔｈ式処理方法。
【請求項３】
前記差分ＸＰａｔｈ式は、前記更新前ＸＰａｔｈ式から前記更新後ＸＰａｔｈ式に追加されたＸＰａｔｈ式の集合として構成され、前記ＤＦＡ更新ステップは、前記更新前ＮＦＡおよび前記更新前ＤＦＡに、前記差分ＮＦＡを、それぞれ差分追加することを特徴とする請求項１または請求項２に記載のＸＰａｔｈ式処理方法。
【請求項４】
前記差分ＸＰａｔｈ式は、前記更新前ＸＰａｔｈ式から削除されたＸＰａｔｈ式の集合として構成され、前記ＤＦＡ更新ステップは、前記更新前ＮＦＡおよび前記更新前ＤＦＡから、前記差分ＮＦＡを、それぞれ差分削除することを特徴とする請求項１または請求項２に記載のＸＰａｔｈ式処理方法。
【請求項５】
コンピュータが、前記更新後ＤＦＡをもとにＸＭＬデータをフィルタ処理するデータ抽出ステップを実行することを特徴とする請求項１ないし請求項４のいずれか１項に記載のＸＰａｔｈ式処理方法。
【請求項６】
ＸＭＬデータを処理するために入力された更新前ＸＰａｔｈ式を示す更新前ＤＦＡを、入力された更新後ＸＰａｔｈ式を示す更新後ＤＦＡに更新するＸＰａｔｈ式処理装置であって、
前記更新前ＸＰａｔｈ式と、当該更新前ＸＰａｔｈ式から導出した更新前ＮＦＡと、当該更新前ＮＦＡから導出した前記更新前ＤＦＡとを管理するオートマトン管理部と、
前記更新前ＸＰａｔｈ式と前記更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式から導出した差分ＮＦＡを管理する更新オートマトン管理部と、
前記差分ＮＦＡを用いて、前記更新前ＮＦＡを更新後ＮＦＡに、前記更新前ＤＦＡを前記更新後ＤＦＡに、それぞれ差分更新するＤＦＡ更新モジュールと、
を有することを特徴とするＸＰａｔｈ式処理装置。
【請求項７】
請求項１ないし請求項５のいずれか１項に記載のＸＰａｔｈ式処理方法をコンピュータに実行させるためのＸＰａｔｈ式処理プログラム。
【請求項８】
請求項７に記載のＸＰａｔｈ式処理プログラムを格納したコンピュータが読み取り可能な記憶媒体。
【請求項９】
ＸＭＬデータを処理するために入力された更新前ＸＰａｔｈ式を示す更新前ＤＦＡから生成される、入力された更新後ＸＰａｔｈ式を示すオートマトンであって、
コンピュータが、
前記更新前ＸＰａｔｈ式と、当該更新前ＸＰａｔｈ式から導出した更新前ＮＦＡと、当該更新前ＮＦＡから導出した前記更新前ＤＦＡとを記憶手段に管理するオートマトン管理ステップと、
前記更新前ＸＰａｔｈ式と前記更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式から導出した差分ＮＦＡを記憶手段に管理する更新オートマトン管理ステップと、
前記差分ＮＦＡを用いて、前記更新前ＤＦＡを差分更新してオートマトンを生成するＤＦＡ更新ステップと、
を実行することにより生成されることを特徴とするオートマトン。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オートマトンを用いたＸＰａｔｈ式の処理に関し、殊にＸＰａｔｈ式の差分追加を行う、ＸＰａｔｈ式処理方法、ＸＰａｔｈ式処理装置、ＸＰａｔｈ式処理プログラムおよびそのプログラムを記憶した記憶媒体、ならびに、オートマトンに関する。
【背景技術】
【０００２】
例えば、ＸＭＬ（Extensible Markup Language）をベースにした新しいニュース配信フォーマットにＮｅｗｓＭＬ（ニューズエムエル）がある。ＮｅｗｓＭＬは、ニュース記事、画像、動画、音声等のニュース素材を自由に組み合わせ、ウェブサイトや携帯電話、テレビ（テレビのデータ放送）等、さまざまな機器を対象に情報を送ることができる。ＮｅｗｓＭＬの受け側（ユーザ）は、フィルタエンジンに検索条件を登録しておくことで、必要な情報を得ることができる。検索条件はＸＭＬ問い合わせ言語で記述されるため、フィルタエンジンは個々のＸＰａｔｈ式を処理すると共に、ＸＰａｔｈ（XML Path Language）式の追加を処理することになる。
【０００３】
ＸＰａｔｈ式を用いて入力されたＸＭＬデータ（ストリームデータなど）をフィルタ処理する際には、ＸＰａｔｈ式から導出されたオートマトン（Automaton）を用いることが有効である。ちなみに、オートマトンとは、コンピュータ等の計算機構を数学的に表すモデルの総称であり、入力、出力、状態をもつ。このうち、決定性有限オートマトン（ＤＦＡ：Deterministic Finite Automaton）は、入力に対する推移先（遷移先）が１つに決まるオートマトンである。一方、非決定性有限オートマトン（ＮＦＡ：Nondeterministic Finite Automaton）は、ある状態において入力に対する推移先（遷移先）が複数存在するオートマトンである。
【０００４】
既に入力されたＸＰａｔｈ式に対して追加を行う従来技術では、ＸＰａｔｈ式を処理するためのＤＦＡが、ＸＰａｔｈ式の追加の度に別途生成されていたため、ＸＰａｔｈ式の追加の度にＤＦＡが増えてしまうとの問題があった。そこで特許文献１に開示された技術は、各ユーザの希望条件をＸＰａｔｈ式を用いることで、ＸＭＬデータから複数のユーザの希望する部分ＸＭＬデータを抽出して配信するシステムにおいて、ユーザによるＸＰａｔｈ式の追加に応じてＸＰａｔｈ式から導出されたＤＦＡを追加前と追加後との差分で更新することを可能とするものである。
【特許文献１】特開２００３−３２３４２９号公報（請求項１）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ＤＦＡの差分更新（差分追加）に関する従来技術（特許文献１など）では、ＸＰａｔｈ式の差分追加のときに、ＸＭＬデータを必要としていた。そのため、ＸＭＬデータのデータ変換処理などの評価時に、ＸＰａｔｈ式の追加・削除をオートマトンに反映するオートマトンの更新処理がオーバーヘッドとなり、ＸＭＬデータの評価時の性能が劣化してしまう。その結果、最新のＸＭＬデータをユーザが取得するまでに時間がかかってしまうという問題があった。特に、ＸＭＬデータが交通情報などの即時性のあるニュースデータのときには、ユーザにとって取得するまでに時間がかからないことが重要となる。
【０００６】
そこで、本発明は、前記した問題を解決し、ＸＭＬデータを評価するためのオートマトンを差分更新するとともに、そのオートマトンがＸＭＬデータを迅速に処理できるようにすることを主な目的とする。
【課題を解決するための手段】
【０００７】
前記課題を解決するために、本発明は、ＸＭＬデータを処理するために入力された更新前ＸＰａｔｈ式を示す更新前ＤＦＡを、入力された更新後ＸＰａｔｈ式を示す更新後ＤＦＡに更新するＸＰａｔｈ式処理方法であって、コンピュータが、前記更新前ＸＰａｔｈ式と、当該更新前ＸＰａｔｈ式から導出した更新前ＮＦＡと、当該更新前ＮＦＡから導出した前記更新前ＤＦＡとを記憶手段に管理するオートマトン管理ステップと、前記更新前ＸＰａｔｈ式と前記更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式から導出した差分ＮＦＡを記憶手段に管理する更新オートマトン管理ステップと、前記差分ＮＦＡを用いて、前記更新前ＮＦＡを更新後ＮＦＡに、前記更新前ＤＦＡを前記更新後ＤＦＡに、それぞれ差分更新するＤＦＡ更新ステップと、を実行することを特徴とする。
【０００８】
これにより、これまでに生成されているＤＦＡ（既存のＤＦＡ）に更新対象のＸＰａｔｈ式の情報を差分更新するだけなので、新たなＤＦＡを別に生成する必要がない。このため、メモリ空間の有効活用を図ることができる。また、差分更新にＸＭＬデータを必要としないため、迅速にＸＰａｔｈ式の情報を差分更新できる。
【０００９】
本発明は、前記ＤＦＡ更新ステップが、前記更新前ＮＦＡに対して、推移に従って状態を順に辿る処理（深さ優先や幅優先など）を実行し、当該実行過程において前記更新前ＮＦＡにおける各推移に適合する前記更新前ＤＦＡの推移を特定して、前記更新前ＤＦＡの各状態が保持するＮＦＡ状態群および推移群を確認し、当該ＮＦＡ状態群および推移群と差分ＮＦＡとの差分を更新することを特徴とする。
【００１０】
これにより、確実にＤＦＡに対するＸＰａｔｈ式の情報の差分更新を行え、また、さらに効率的にメモリ空間を使用することができる。
【００１１】
本発明は、前記差分ＸＰａｔｈ式が、前記更新前ＸＰａｔｈ式から前記更新後ＸＰａｔｈ式に追加されたＸＰａｔｈ式の集合として構成され、前記ＤＦＡ更新ステップが、前記更新前ＮＦＡおよび前記更新前ＤＦＡに、前記差分ＮＦＡを、それぞれ差分追加することを特徴とする。
【００１２】
これにより、メモリ空間の有効活用を図りつつ、迅速にＤＦＡを差分追加できる。
【００１３】
本発明は、前記差分ＸＰａｔｈ式が、前記更新前ＸＰａｔｈ式から削除されたＸＰａｔｈ式の集合として構成され、前記ＤＦＡ更新ステップが、前記更新前ＮＦＡおよび前記更新前ＤＦＡから、前記差分ＮＦＡを、それぞれ差分削除することを特徴とする。
【００１４】
これにより、メモリ空間の有効活用を図りつつ、迅速にＤＦＡを差分削除できる。
【００１５】
本発明は、コンピュータが、前記更新後ＤＦＡをもとにＸＭＬデータをフィルタ処理するデータ抽出ステップを実行することを特徴とする。
【００１６】
これにより、効率的に差分更新されたＤＦＡを有効に活用することができる。
【００１７】
本発明は、ＸＭＬデータを処理するために入力された更新前ＸＰａｔｈ式を示す更新前ＤＦＡを、入力された更新後ＸＰａｔｈ式を示す更新後ＤＦＡに更新するＸＰａｔｈ式処理装置であって、前記更新前ＸＰａｔｈ式と、当該更新前ＸＰａｔｈ式から導出した更新前ＮＦＡと、当該更新前ＮＦＡから導出した前記更新前ＤＦＡとを管理するオートマトン管理部と、前記更新前ＸＰａｔｈ式と前記更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式から導出した差分ＮＦＡを管理する更新オートマトン管理部と、前記差分ＮＦＡを用いて、前記更新前ＮＦＡを更新後ＮＦＡに、前記更新前ＤＦＡを前記更新後ＤＦＡに、それぞれ差分更新するＤＦＡ更新モジュールと、を有することを特徴とする。
【００１８】
これにより、これまでに生成されているＤＦＡ（既存のＤＦＡ）に追加対象のＸＰａｔｈ式の情報を差分更新するだけなので、新たなＤＦＡを別に生成する必要がない。このため、メモリ空間の有効活用を図るＸＰａｔｈ式処理装置（後記するフィルタエンジン）を提供することができる。また、差分更新にＸＭＬデータを必要としないため、迅速にＸＰａｔｈ式の情報を差分更新できる。
【００１９】
本発明は、請求項１ないし請求項５のいずれか１項に記載のＸＰａｔｈ式処理方法をコンピュータに実行させるためのＸＰａｔｈ式処理プログラムである。
【００２０】
これにより、このプログラムをインストールされたコンピュータに、プログラムに基づいた各ステップを実行させ、ＸＰａｔｈ式の処理（ＤＦＡの差分更新）を行う。
【００２１】
本発明は、請求項７に記載のＸＰａｔｈ式処理プログラムを格納したコンピュータが読み取り可能な記憶媒体である。
【００２２】
このＸＰａｔｈ式処理プログラムは、例えばＣＤ−ＲＯＭ等の記録媒体に複写・記録されて市場を流通されたり、例えばネットワーク上を伝送されたりする。そして、このプログラムをインストールされたコンピュータにＸＰａｔｈ式の処理（ＤＦＡの差分更新）を実行させる。
【００２３】
本発明は、ＸＭＬデータを処理するために入力された更新前ＸＰａｔｈ式を示す更新前ＤＦＡから生成される、入力された更新後ＸＰａｔｈ式を示すオートマトンであって、コンピュータが、前記更新前ＸＰａｔｈ式と、当該更新前ＸＰａｔｈ式から導出した更新前ＮＦＡと、当該更新前ＮＦＡから導出した前記更新前ＤＦＡとを記憶手段に管理するオートマトン管理ステップと、前記更新前ＸＰａｔｈ式と前記更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式から導出した差分ＮＦＡを記憶手段に管理する更新オートマトン管理ステップと、前記差分ＮＦＡを用いて、前記更新前ＤＦＡを差分更新してオートマトンを生成するＤＦＡ更新ステップと、を実行することにより生成されることを特徴とする。
【００２４】
これにより、これまでに生成されているＤＦＡ（既存のＤＦＡ）に更新対象のＸＰａｔｈ式の情報を差分更新するだけなので、新たなＤＦＡを別に生成する必要がない。このため、メモリ空間の有効活用を図ることができる。また、差分更新にＸＭＬデータを必要としないため、迅速にＸＰａｔｈ式の情報を差分更新できる。
【発明の効果】
【００２５】
本発明によれば、これまでに生成されているＤＦＡに追加・削除対象のＸＰａｔｈ式を即時で差分更新するため、ＸＭＬデータの評価時にはＤＦＡの差分更新操作が発生しない。このようにＸＰａｔｈ式の追加・削除時に決定性オートマトンを更新するため、ＸＭＬデータの評価時にはＸＰａｔｈ式の追加・削除操作の影響による性能劣化が生じない。
【発明を実施するための最良の形態】
【００２６】
以下、本発明のＸＰａｔｈ式処理方法の実施形態を、図面を参照して詳細に説明する。なお、以下説明するＸＰａｔｈ式処理方法は、ＸＰａｔｈ式処理装置、ＸＰａｔｈ式処理プログラムを具現化したものでもある。第１実施形態では既存のＸＰａｔｈ式に新たなＸＰａｔｈ式を追加する差分更新を、第２実施形態では既存のＸＰａｔｈ式の一部を削除する差分更新を、それぞれ述べる。以下、第１実施形態を説明する。
【００２７】
図１は、ＸＰａｔｈ式処理方法が適用されるフィルタエンジンの概要を示す図である。図示しないデータ提供者によりＸＭＬ形式にしたがって生成されたＸＭＬデータが、ＸＰａｔｈ式処理方法を実行するフィルタエンジン１０にイントラネット等のネットワークを経由して送信される。フィルタエンジン１０には、ＸＭＬデータを受け取る個々のユーザが、自分の欲しいデータの条件（個人プロファイル）を、従来例のように、ＸＭＬ問い合わせという形式でフィルタエンジン１０に予め登録している。
【００２８】
フィルタエンジン１０は、登録されている個人プロファイルに応じて送られてくるニュースソース等のＸＭＬデータをフィルタ・変換して個々のユーザにＸＭＬデータとして配信する。ニュースソース等のＸＭＬデータの具体例としては、ＮｅｗｓＭＬがある。ＮｅｗｓＭＬは前記のとおり、ＸＭＬをベースにした新しいニュース配信フォーマットであり、ニュース記事、画像、動画、音声等のニュース素材を自由に組み合わせ、ウェブサイトや携帯電話等さまざまな機器を対象に情報を送ることができる。また、ニュース記事、画像、動画、音声等のさまざまなニュース素材を構造化して一元管理するのに適する。
【００２９】
なお、フィルタエンジン１０は、請求項のＸＰａｔｈ式処理装置およびＸＰａｔｈ式処理プログラムを内包するものでもある。ちなみに、ＸＭＬは、インターネットの標準としてＷ３Ｃ（World Wide Web Consortium）により勧告されたメタ言語である。メタ言語は、言語を作る言語という意味である。ＸＭＬデータ（ＸＭＬ文書：XMLDocumentともいう）は、ＸＭＬによって作られた言語を用いて作成された文書やデータである。
【００３０】
そして、フィルタエンジン１０は、ＸＭＬデータから、ユーザの希望条件であるＸＰａｔｈ式に適合するＸＭＬデータを抽出する。ここで、フィルタエンジン１０は、後記において詳細に説明するように、ＸＰａｔｈ式から導出されたＤＦＡヘ即時に、かつ、全てＸＰａｔｈ式の追加・削除を反映させることを特徴とする。これにより、ＸＭＬデータの処理時にはＸＰａｔｈ式の更新に関わる操作が一切発生しないため処理が高速化されるという効果を奏する。
【００３１】
図２は、図１のフィルタエンジン１０の内部構成を示すブロック図である。この図２に示すように、フィルタエンジン１０は、ＸＭＬパースモジュール１１、問い合わせパースモジュール１２、データ抽出モジュール１３、ＤＦＡ作成モジュール１３Ｂ、オートマトン管理部１５、データ変換モジュール１６、ＤＦＡ更新モジュール１７、および、更新オートマトン管理部１８を含んで構成される。フィルタエンジン１０は、ＣＰＵおよびＲＡＭから構成される主制御装置、ハードディスク等から構成される外部記憶装置、通信を行うためのＮＩＣ（Network Interface Card）を有するコンピュータと、ルータ（Router）とを含んで構成される。オートマトン管理部１５および更新オートマトン管理部１８は、例えば、外部記憶装置に格納される。
【００３２】
ＸＭＬパースモジュール（ＸＭＬパーサ）１１は、入力されるＸＭＬデータをパースして内部形式ＸＭＬデータ（ＳＡＸ（Simple API for XML）イベント）に変換し、データ抽出モジュール１３ヘ出力する。なお、パースとは、テキスト形式で記述されたＸＭＬデータを読み込んで、ＸＭＬのタグで指定された文書要素や属性等を解析する解析処理である（本実施形態においてはパースの手順等は特に限定するものではない）。ちなみに、ＸＭＬパースモジュール１１を通してＸＭＬデータを操作するためのＡＰＩ（Application Programming Interface）には、ＤＯＭ（Document Object Mode）とＳＡＸという２種類の標準インターフェースがある。本実施形態では、ＸＭＬパースモジュール１１は、後者のＳＡＸに対応している。
【００３３】
なお、ＳＡＸに対応したＸＭＬパースモジュール１１は、ＸＭＬデータを順次シーケンシャルに読み込みつつ、ＸＭＬのタグ（開始タグ、終了タグ、空要素タグ）を検出するごとにアドインされた各種ハンドラを起動する。ここでハンドラとは、ＳＡＸインターフェースに基づいてＸＭＬデータの各要素を処理するためのメソッドを定義したプログラムである。また、タグとは、ＸＭＬデータにおいて、要素の位置を明示し、属性を収納するために記述される文字列である。
【００３４】
問い合わせパースモジュール１２は、ＸＰａｔｈ式を生成する。具体的には、問い合わせパースモジュール１２は、追加される個人プロファイル（ＸＭＬ問い合わせ言語で記述される検索条件）をパース（解析処理）し、「データ変換操作」とデータ抽出操作である「個々のＸＰａｔｈ式」とに分離する。ＸＰａｔｈ式は、ＤＦＡ作成モジュール１３Ｂによってオートマトンに変換されてからデータ抽出モジュール１３ヘ出力され、データ変換操作はデータ変換モジュール１６ヘ出力される。なお、ＸＰａｔｈ式は、ＸＭＬデータの特定の部分を指し示す言語である。ＸＰａｔｈ式を利用すれば、ＸＭＬデータ中にアンカ等が埋め込まれていなくとも、データ中の任意の位置を指し示すことができる。
【００３５】
ＤＦＡ作成モジュール１３Ｂは、問い合わせパースモジュール１２から入力される個々のＸＰａｔｈ式をＮＦＡに変換（ＮＦＡを生成）し、そのＮＦＡを結合ＮＦＡに結合し、その結合ＮＦＡからＤＦＡを生成してオートマトン管理部１５に登録（追加）する。
【００３６】
データ抽出モジュール１３は、オートマトン管理部１５に格納されたＤＦＡを用いて、ＸＭＬパースモジュール１１に入力されたＸＭＬデータから抽出された部分ＸＭＬを内部形式ＸＭＬデータ（フィルタされた後の内部形式ＸＭＬデータ）としてデータ変換モジュール１６ヘ出力する。
【００３７】
データ変換モジュール１６は、データ変換操作と抽出された内部形式のＸＭＬデータとから所定の変換を実行し、その結果をフィルタされたＸＭＬデータ（変換後ＸＭＬデータ）として出力する。なお、所定の変換は本発明においては特に限定するものではない。
【００３８】
次に、オートマトン管理部１５を詳細に説明する。図３は、図２におけるオートマトン管理部１５のメモリ上でのデータ構成を示した図である。なお、ＤＦＡの詳細は図５に示す。
【００３９】
図３に示すように、個々のＸＰａｔｈ式ごとにＮＦＡが生成される。こうして生成された複数のＮＦＡは１つのノードにより結合され、そのルートからイプシロンエッジにより個々のＮＦＡに接続される（結合ＮＦＡ）。なお、イプシロンエッジとは、例えばオートマトンにおいて通常定義される”空文字列”のことである。ＤＦＡは、結合ＮＦＡを用いて順次生成および更新される。または、ＤＦＡは、結合ＮＦＡとＸＭＬデータの入力に応じて、必要な状態が順次生成および更新される。
【００４０】
図４は、図３の具体的なプログラム上でのデータ構造を示す図である。この図４において、Ｖａｒｉａｂｌｅクラス（class Variable）は、個々のＸＰａｔｈ式ごとにインスタンス（Instance）を生成するクラスであり、次のような属性を有する。なお、インスタンスとは、例えばオブジェクト指向プログラミングにおいて、あるクラスの定義をひな型として実際に作られたオブジェクトのことをいう。
＊そのインスタンスごとに異なる内部識別子である”ｉｄ”
＊個々のＸＰａｔｈ式表現である”ＸＰａｔｈ式”
＊Ｖａｒｉａｂｌｅをユーザが区別するための名称である”ｖａｒＮａｍｅ”
【００４１】
Ｓｔａｔｅクラス（class State）は、ＮＦＡの状態を表現するクラスであり、次のような属性を有する。
＊自身の状態から他の状態への推移を表現するエッジの集合”ｅｄｇｅｓ”
＊自身の状態が終端か非終端かを示す”ｔｙｐｅ”（なお、ＸＰａｔｈ式の表現をＮＦＡに変換した場合、最後尾の状態は終端であり、それ以外の状態は非終端であるとする。）
＊自身の状態がどのＶａｒｉａｂｌｅインスタンスから（つまりそのＸＰａｔｈ式から）生成されたかを示す”ｖａｒ”
【００４２】
ＤＦＡＳｔａｔｅクラス（class DFAState）はＤＦＡの状態を表現し、Ｓｔａｔｅクラスをオブジェクト指向的な継承を用いて定義され、次のような属性を有する。
＊ＮＦＡを用いてＤＦＡを生成する際に必要になる、ＮＦＡの状態群を表現する”ｓｔａｔｅｓ”
なお、ｅｄｇｅｓはＳｔａｔｅクラスのものを継承しているが、処理の高速化を図るため、ｌｉｓｔではなくｈａｓｈやｍａｐ構造を用いて再定義することも可能である。
【００４３】
Ｅｄｇｅクラス（class Edge）はＮＦＡの状態Ｓｔａｔｅ間のエッジ、もしくはＤＦＡの状態間のエッジを表現し、次のような属性を有する。
＊自身のエッジのエッジ先である状態”ｔｏ”
＊自身のエッジのエッジ元である状態”ｆｒｏｍ”
【００４４】
図５は、図４のＤＦＡのメモリ上でのデータ構造を図示した図である。ただし、この図５では図４と異なり、”ｅｄｇｅｓ”を実現するためにｌｉｓｔではなくｍａｐ構造を利用している。
【００４５】
この図５の左に位置するＤＦＡＳｔａｔｅはＤＦＡＳｔａｔｅクラスのインスタンスであり、ＤＦＡの１状態を表現している。この図５の状態ではその属性値であるｓｔａｔｅｓ，ｅｄｇｅｓ，ｔｙｐｅ，ｖａｒ，ｖａｒＩｄの値がそれぞれ設定されている。ここで、ｓｔａｔｅｓはＮＦＡの状態群を表す。ｅｄｇｅｓはエッジのラベルとエッジインスタンスヘの参照の組を表現している。ｔｙｐｅは非終端であるので”ｎｏｎ−ｔｅｒｍｉｎａｌ”になっている。ｖａｒはＶａｒｉａｂｌｅインスタンスヘの参照である。この例では、ｖａｒＩｄは３であり、３番目のＶａｒｉａｂｌｅ（ＸＰａｔｈ式）までの状態をこのＤＦＡＳｔａｔｅが反映していることを意味している。
【００４６】
図５の中間（左中間）に位置するのがＥｄｇｅのインスタンス群である。また、図５の右中間に位置するのがＥｄｇｅの推移先に相当するＤＦＡＳｔａｔｅインスタンス群である。なお、図５に示すように、Ｅｄｇｅの推移先はＮｕｌｌ（ＤＦＡＳｔａｔｅが未生成）であることも許されている。
【００４７】
ＤＦＡ更新モジュール１７は、オートマトン管理部１５が管理する構築済みのＤＦＡから更新後のオートマトンが許容する状態に対応する更新前のオートマトン状態を特定し、特定した個々の状態を差分で更新する。
【００４８】
つまり、差分で更新する処理とは、更新後ＸＰａｔｈ式を全て使用する代わりに、更新前ＸＰａｔｈ式と更新後ＸＰａｔｈ式との差分となる差分ＸＰａｔｈ式を用いて、更新前ＤＦＡから更新後ＤＦＡに更新する処理である。まず、オートマトン管理部１５が、更新前ＸＰａｔｈ式と、その更新前ＸＰａｔｈ式から導出した更新前ＮＦＡ（図３の中段のＮＦＡ）と、その更新前ＮＦＡから導出した更新前ＤＦＡ（図３下段のＤＦＡ）を管理する。次に、更新オートマトン管理部１８は、差分ＸＰａｔｈ式から導出する差分ＮＦＡを管理する。
【００４９】
そして、ＤＦＡ更新モジュール１７は、差分ＮＦＡを用いて更新前ＤＦＡから更新後ＤＦＡへ部分更新する。つまり、ＤＦＡ更新モジュール１７は、差分ＸＰａｔｈ式を差分ＮＦＡに変換し、更新前ＮＦＡおよび更新前ＤＦＡに対して差分ＮＦＡを追加することにより、差分ＸＰａｔｈ式の情報を差分追加する。
【００５０】
次に、図６に示す更新前のデータの一例、および、図７に示す更新後のデータの一例について説明する。
【００５１】
図６は、オートマトン管理部１５が管理するデータの一例を示す図である。ＤＦＡ作成モジュール１３Ｂは、３つのＸＰａｔｈ式（更新前ＸＰａｔｈ式：図６（ａ）参照）から、各式に相当するＮＦＡを導出し、それらのＮＦＡを統合ＮＦＡ（更新前ＮＦＡ：図６（ｂ）参照）にし、それからＤＦＡ（更新前ＤＦＡ：図６（ｃ）参照）を導出している。
【００５２】
例えば、図６（ａ）に示す「／ａ／／ｂ」は、Ｓ１、Ｓ２、Ｓ３の状態と、ａ、＊、ｂの推移から構成される。なお／／ｌａｂｅｌは、入力ＸＭＬデータの任意の深さの要素の名称がｌａｂｅｌであるものにマッチするため、ＮＦＡではワイルドカード（＊）による自己推移に対応付けられる。「／ｄ／／ｂ」は、Ｓ４、Ｓ５、Ｓ６の状態と、ｄ、＊、ｂの推移から構成され、「／ａ／ｃ／ｂ」は、Ｓ７、Ｓ８、Ｓ９、Ｓ１０の状態と、ａ、ｃ、ｂの推移から構成される。
【００５３】
次に、ＤＦＡ作成モジュール１３Ｂは、これらの３つのＮＦＡを、Ｓ０の状態と、イプシロンの推移により、各ＮＦＡの開始状態を、Ｓ０の状態で統合させる（図６（ｂ）に示す統合ＮＦＡの作成）。
【００５４】
さらに、ＤＦＡ作成モジュール１３Ｂは、この統合ＮＦＡと同等なＤＦＡを生成する（図６（ｃ））。ＤＦＡは、例えばサブセットコンストラクションにより作成されるが、ここの例では特に特許文献１で示されるような遅延評価ＤＦＡの例を用いており、部分的に状態がＮＵＬＬとなっている。ＤＦＡの各状態は推移群と対応するＮＦＡ状態を表すＮＦＡ状態群からなる。表記を簡略化するため、ＮＦＡの状態群の表記において、ＮＦＡ状態を表すプレフィックスＳを省略し番号のみを記載している。よって例えば、図６（ｂ）の状態Ｓ０は、図６（ｃ）の状態｛０，１，４，７｝の「０」に対応する。
【００５５】
図７は、記憶装置に格納されるデータの一例を示す図である。更新オートマトン管理部１８は、追加するＸＰａｔｈ式（差分ＸＰａｔｈ式：図７（ａ）参照）、そのＸＰａｔｈ式から導出されたＮＦＡ（差分ＮＦＡ：図７（ｂ）参照）を管理する。オートマトン管理部１５は、差分ＮＦＡが更新前ＮＦＡ（図６（ｂ））に追加されたＮＦＡ（更新後ＮＦＡ：図７（ｃ）参照）を管理する。
【００５６】
図８、図９は、ＤＦＡ更新モジュール１７が、図６（ｃ）に示された更新前ＤＦＡに対して、図７（ｂ）の差分ＮＦＡを追加した結果である更新後ＤＦＡを示している。ハッチングされた状態は更新された状態を表している。
【００５７】
以下、ＤＦＡ更新モジュール１７の処理の詳細について、フローチャートを参照して説明する。ＤＦＡ更新モジュール１７は、図１０〜図１２に示すフローチャートに沿ってＤＦＡの差分更新を行う。
【００５８】
図１０はＤＦＡの更新フローを示す。Ｓ２００において、複数のＸＰａｔｈ式（更新前ＸＰａｔｈ式）を処理するために導出されたＤＦＡ（更新前ＤＦＡ）を読み込み、その開始状態を状態ｄｓとして保持する。Ｓ２１０において、追加対象のＸＰａｔｈ式（差分ＸＰａｔｈ式）を読み込み、それからＮＦＡ（差分ＮＦＡ）を導出し、その開始状態を状態ｎｓとして保持する。これらの状態ｄｓ、状態ｎｓを引数として、Ｓ２２０に示すサブルーチンＤＦＡ（更新前ＤＦＡ）状態の更新を行う。なお、ＤＦＡの更新フロー（図１０）の任意のタイミングにおいて、ＤＦＡ更新モジュール１７は、図６（ｂ）の更新前ＮＦＡに図７（ｂ）の差分ＮＦＡを反映して、図７（ｃ）の更新後ＮＦＡとする。
【００５９】
図１１はサブルーチンであるＤＦＡ状態の更新のフローの詳細を示す。ここでは特にＸＰａｔｈ式の追加操作に対するフローを示している。本サブルーチンでは正規のＤＦＡに加えて、特許文献１に記述されている遅延評価型のＤＦＡにも対応するため、Ｓ３１０において状態ｄｓがＮＵＬＬ（未評価）であるか否かを判定する。ＮＵＬＬである場合は（Ｓ３１０、Ｙｅｓ）、更新対象の状態が未評価であるため、本サブルーチンを終了（ｒｅｔｕｒｎ）する。状態ｄｓが存在する場合は（Ｓ３１０、Ｎｏ）、Ｓ３２０において状態ｄｓが保持するＮＦＡ状態群に対して、追加対象のＸＰａｔｈ式のＮＦＡ状態ｎｓを追加する。
【００６０】
続いてＮＦＡ状態ｎｓからの推移を用いてＤＦＡを更新するため、Ｓ３３０において状態ｎｓからの推移群を取得する。Ｓ３４０において取得した推移群でＳ３５０、Ｓ３６０の処理が未処理である推移があるか否かを判定する。未処理の推移がない場合は、全ての推移に対するＤＦＡの更新が終了（ｒｅｔｕｒｎ）である。未処理の推移がある場合は、Ｓ３５０において未処理の推移を１つ選択し、推移ｎｅとして保持する。そして、状態ｄｓと推移ｎｅを引数として、Ｓ３６０に示すサブルーチン「推移によるＤＦＡ状態更新」を行う。
【００６１】
図１２はサブルーチンである推移によるＤＦＡ状態更新フローの詳細を示す。Ｓ４００において、ＤＦＡ状態ｄｓが保持する推移群において、ＮＦＡ側の推移ｎｅに適合する推移を特定する。Ｓ４１０において、適合する推移の有無を判定する。適合する推移がない場合は、Ｓ４５０へ進み、状態ｄｓの推移群に新たに推移ｎｅを追加して、本サブルーチンを終了（ｒｅｔｕｒｎ）する。適合する推移がある場合は、Ｓ４２０へ進み、未処理である推移の有無を判定する。
【００６２】
未処理である推移がない場合は、推移ｎｅによるＤＦＡ更新が終了であるため、本サブルーチンを終了（ｒｅｔｕｒｎ）する。未処理である推移がある場合は、Ｓ４３０において未処理である推移を１つ選択し推移ｄｅとして保持する。Ｓ４４０において、推移ｄｅの推移先のＤＦＡ状態を状態ｄｓ１として保持し、推移ｎｅの推移先のＮＦＡ状態を状態ｎｓ１として保持する。これらの状態ｄｓ１、状態ｎｓ１を引数として、Ｓ２２０に示すサブルーチン「ＤＦＡ状態の更新」を行う。
【００６３】
図１０〜図１２で示したように、本発明は更新ＸＰａｔｈ式から導出されたＮＦＡに対して、推移に従って状態を順に辿る処理を実行し、当該実行過程においてＮＦＡにおける各推移に適合するＤＦＡの推移を特定して、ＤＦＡの各状態が保持するＮＦＡ状態群および推移群を確認し、当該ＮＦＡ状態群および推移群と差分ＮＦＡとの差分を更新することを特徴とする。
【００６４】
以上説明した図１０〜図１２の処理を具体的に説明するため、図６〜図９に示した一例を適用して、ＤＦＡ更新モジュール１７が行うＤＦＡの差分更新の方法を説明する。
【００６５】
図１０のＳ２００において、状態ｄｓは｛０，１，４，７｝で構成される状態を保持する。Ｓ２１０で、状態ｎｓは図７のＳ１１の状態を保持する、Ｓ２２０で、これらの状態ｄｓと状態ｎｓからＤＦＡ状態更新を行う。
【００６６】
図１１のＳ３１０において状態ｄｓ｛０，１，４，７｝はＮＵＬＬでないため、Ｓ３２０で状態ｎｓのＳ１１という状態を状態ｄｓに加え、その結果、状態ｄｓが保持するＮＦＡ状態群は｛０，１，４，７，１１｝となる。次にＳ３３０で、状態ｎｓからの推移としてａを取得する。Ｓ３４０において未処理である推移ａがあるため、Ｓ３５０でａを推移ｎｅに保持する。
【００６７】
次に、状態ｄｓと推移ｎｅでＳ３６０の「推移によるＤＦＡ状態更新」を行う。
【００６８】
図１２のＳ４００において、状態ｄｓ（｛０，１，４，７，１１｝）の推移群ａ、ｄのうち、推移ｎｅ（ａ）に適合する推移であるａを特定する。Ｓ４１０において適合する推移があったため、Ｓ４２０に進み、未処理である推移ａがあるため、Ｓ４３０に進む。Ｓ４３０では適合する推移ａを取り出し、推移ｄｅに保持する。Ｓ４４０では推移ｄｅ（ａ）の推移先のＤＦＡ状態｛２、８｝を状態ｄｓ１として保持し、推移ｎｅ（ａ）の推移先のＮＦＡ状態Ｓ１２を状態ｎｓ１として保持し、これらを引数としてＳ２２０のサブルーチンＤＦＡ状態更新を行う。
【００６９】
ＤＦＡ状態更新サブルーチンの最初の再帰について説明する。
【００７０】
図１１のＳ３１０において状態ｄｓ｛２，８｝はＮＵＬＬでないため、Ｓ３２０で状態ｎｓのＳ１２という状態を状態ｄｓに加え、その結果状態ｄｓが保持するＮＦＡ状態群は｛２，８，１２｝となる。次にＳ３３０で、状態ｎｓからの推移としてｄ、＊を取得する、Ｓ３４０において未処理である推移ｄがあるため、Ｓ３５０でｄを推移ｎｅに保持する。
【００７１】
次に、状態ｄｓと推移ｎｅでＳ３６０の「推移によるＤＦＡ状態更新」を行う。図１２のＳ４００において、状態ｄｓ（｛２，８，１２｝）の推移群ｂ、ｃ、ｏｔｈｅｒのうち、推移ｎｅ（ｄ）に適合する推移であるｏｔｈｅｒを特定する。Ｓ４１０において適合する推移があったため、Ｓ４２０に進み、未処理である推移ｄがあるため、Ｓ４３０に進む。
【００７２】
Ｓ４３０では適合する推移ｄを取り出し、推移ｄｅに保持する。このとき、推移ｄが適合したＤＦＡの推移がｏｔｈｅｒであったため、ｏｔｈｅｒによる推移をｏｔｈｅｒとｄとに分割し、推移先の構造をコピーする。Ｓ４４０では推移ｄｅ（ｄ）の推移先のＤＦＡ状態｛２｝を状態ｄｓ１として保持し、推移ｎｅ（ｄ）の推移先のＮＦＡ状態Ｓ１３を状態ｎｓ１として保持し、これらを引数としてＳ２２０のサブルーチンＤＦＡ状態更新を行う。
【００７３】
ＤＦＡ状態更新サブルーチンの二度目の再帰について説明する。
【００７４】
図１１のＳ３１０において状態ｄｓ｛２｝はＮＵＬＬでないため、Ｓ３２０で状態ｎｓのＳ１３という状態を状態ｄｓに加え、その結果状態ｄｓが保持するＮＦＡ状態群は｛２，１３｝となる。次にＳ３３０で、状態ｎｓからの推移を取得するが推移はない。Ｓ３４０において未処理である推移がないため、本サブルーチンの処理を終了（ｒｅｔｕｒｎ）する。図８はこの時点のＤＦＡを示している。
【００７５】
図１２のＳ２２０の処理が完了したため、Ｓ４２０に進む。Ｓ４２０では未処理である推移がないため、本サブルーチンの処理を終了（ｒｅｔｕｒｎ）する。
【００７６】
図１１のＳ３６０の処理が完了したため、Ｓ３４０に進む。Ｓ３４０において未処理である推移＊があるため、Ｓ３５０で＊を推移ｎｅに保持する。次に、状態ｄｓと推移ｎｅでＳ３６０の「推移によるＤＦＡ状態更新」を行う。図１２のＳ４００において、状態ｄｓ（｛２，８，１２｝）の推移群ｄ、ｂ、ｃ、ｏｔｈｅｒのうち、推移ｎｅ（＊）に適合する推移であるｄ、ｂ、ｃ、ｏｔｈｅｒを特定する。Ｓ４１０において適合する推移があったため、Ｓ４２０に進み、未処理である推移ｄがあるため、Ｓ４３０に進む。Ｓ４３０では適合する推移ｄを取り出し、推移ｄｅに保持する。
【００７７】
Ｓ４４０では推移ｄｅ（ｄ）の推移先のＤＦＡ状態｛２，１３｝を状態ｄｓ１として保持し、推移ｎｅ（＊）の推移先のＮＦＡ状態Ｓ１２を状態ｎｓ１として保持し、これらを引数としてＳ２２０のサブルーチンＤＦＡ状態更新を行う。
【００７８】
前記の処理を再帰的に繰り返すことにより、図６のＤＦＡが更新されて最終的に図９に示すＤＦＡになる。
【００７９】
以上、第１実施形態（差分追加）を説明した。次に第２実施形態（差分削除）を説明する。なお、第２実施形態におけるフィルタエンジン１０の構成は、第１実施形態と同じであるため、説明を省略する。
【００８０】
図１３は、図６に示す更新前のデータに対する削除するデータの一例を示している。図１４〜図１６は、図６に示されたＤＦＡに対して、図１３（ｂ）のＮＦＡを削除した結果のＤＦＡを示している。ハッチングされた状態は更新された状態を表している。
【００８１】
ＤＦＡ更新モジュール１７は、図１７〜図１９に示すフローに沿ってＤＦＡの差分更新（差分削除）を行う。
【００８２】
図１７はＤＦＡの削除フローを示す。Ｓ５００において、複数のＸＰａｔｈ式を処理するために導出されたＤＦＡを読み込み、その開始状態を状態ｄｓとして保持する。Ｓ５１０において、削除対象に相当するＮＦＡを読み込み、その開始状態を状態ｎｓとして保持する。これらの状態ｄｓ、状態ｎｓを引数として、Ｓ５２０に示すサブルーチンＤＦＡ状態の削除を行う。このＤＦＡ状態の削除後に、Ｓ５３０で削除対象に相当するＮＦＡを削除する。
【００８３】
図１８はサブルーチンであるＤＦＡ状態の削除のフローの詳細を示す。ここでは特にＸＰａｔｈ式の削除操作に対するフローを示している。本サブルーチンでは差分追加と同様に、Ｓ６１０において、状態ｄｓがＮＵＬＬ（未評価）であるか否かを判定する。ＮＵＬＬである場合は（Ｓ６１０，Ｙｅｓ）、追加対象の状態が未評価であるため、本サブルーチンを終了（ｒｅｔｕｒｎ）する。
【００８４】
状態ｄｓが存在する場合は、Ｓ６２０において状態ｄｓが保持するＮＦＡ状態群に対して、削除対象のＸＰａｔｈ式のＮＦＡ状態ｎｓを削除する。この時、状態ｄｓが保持するＮＦＡ状態群をＳ６３０にて確認し、ＮＦＡ状態群がない場合、この状態ｄｓ配下をＳ６４０にて削除する。ＮＦＡ状態群がある場合、ＮＦＡ状態ｎｓからの推移を用いてＤＦＡを削除するため、Ｓ６５０において状態ｎｓからの推移群を取得する。
【００８５】
Ｓ６５０において取得した推移群でＳ６７０、Ｓ６８０の処理が未処理である推移があるか否かを判定する。未処理の推移がない場合は（Ｓ６６０，無）、全ての推移に対するＤＦＡの削除が終了である。未処理の推移がある場合（Ｓ６６０，有）は、Ｓ６７０において未処理の推移を一つ選択し、推移ｎｅとして保持する。そして、状態ｄｓと推移ｎｅとを引数として、Ｓ６８０に示すサブルーチン推移によるＤＦＡ状態削除を行い、Ｓ６６０に戻る。
【００８６】
図１９はサブルーチンである推移によるＤＦＡ状態削除フローの詳細を示す。Ｓ７００において、ＤＦＡ状態ｄｓが保持する推移群において、ＮＦＡ側の推移ｎｅに適合する推移を特定する。Ｓ７１０において、適合する推移の有無を判定する。適合する推移がない場合は、本サブルーチンを終了（ｒｅｔｕｒｎ）する。適合する推移がある場合は、Ｓ７２０へ進み。未処理である推移の有無を判定する。未処理である推移がない場合は、推移ｎｅによるＤＦＡ削除が終了であるため、本サブルーチンを終了（ｒｅｔｕｒｎ）する。
【００８７】
未処理である推移がある場合は、Ｓ７３０において未処理である推移を一つ選択し推移ｄｅとして保持する。Ｓ７４０において、推移ｄｅの推移先のＤＦＡ状態を状態ｄｓ１として保持し、推移ｎｅの推移先のＮＦＡ状態を状態ｎｓ１として保持する。これらの状態ｄｓ１、状態ｎｓ１を引数として、Ｓ５２０に示すサブルーチン「ＤＦＡ状態の削除」を行う。
【００８８】
以上説明した図１７〜図１９の処理を具体的に説明するため、図６、図１３〜図１６に示した一例を適用して、ＤＦＡ更新モジュール１７が行うＤＦＡの差分更新の方法を説明する。
【００８９】
図１７のＳ５００において、状態ｄｓは、｛０，１，４，７｝で構成される状態を保持する。Ｓ５１０で、状態ｎｓは図１３のＳ１の状態を保持する。Ｓ５２０で、これらの状態ｄｓと状態ｎｓからＤＦＡ状態削除を行う。
【００９０】
図１８のＳ６１０において、状態ｄｓ｛０，１，４，７｝はＮＵＬＬでないため、Ｓ６２０で状態ｎｓのＳ１という状態を状態ｄｓから削除し、その結果状態ｄｓが保持するＮＦＡ状態群は、｛０，４，７｝となる。Ｓ６３０で状態ｄｓ｛０，４，７｝はＮＦＡ状態群を保持しているため、Ｓ６５０で、状態ｎｓからの推移としてａを取得する。Ｓ６６０において未処理である推移ａがあるため、Ｓ６７０でａを推移ｎｅに保持する。次に、状態ｄｓと推移ｎｅとでＳ６８０の「推移によるＤＦＡ状態削除」を行う。
【００９１】
図１９のＳ７００において、状態ｄｓ｛０，４，７｝の推移群ａ，ｄのうち、推移ｎｅ（ａ）に適合する推移であるａを特定する。Ｓ７１０において適合する推移があったため、Ｓ７２０に進み、未処理である推移ａがあるため、Ｓ７３０に進む。Ｓ７３０では適合する推移ａを取り出し、推移ｄｅに保持する。Ｓ７４０では推移ｄｅ（ａ）の推移先のＤＦＡ状態｛２，８｝を状態ｄｓ１として保持し、推移ｎｅ（ａ）の推移先のＮＦＡ状態Ｓ２を状態ｎｓ１として保持し、これらを引数としてＳ５２０のサブルーチンＤＦＡ状態削除を行う。
【００９２】
ＤＦＡ状態削除サブルーチンの最初の再帰について説明する。
【００９３】
図１８のＳ６１０において、状態ｄｓ｛２、８｝はＮＵＬＬでないため、Ｓ６２０で状態ｎｓのＳ２という状態を状態ｄｓから削除し、その結果状態ｄｓが保持するＮＦＡ状態群は｛８｝となる。Ｓ６３０で状態ｄｓ｛８｝はＮＦＡ状態を保持しているため、Ｓ６５０で、状態ｎｓからの推移としてｂ、＊を取得する。Ｓ６６０において未処理である推移ｂがあるため、Ｓ６７０でｂを推移ｎｅに保持する。次に、状態ｄｓと推移ｎｅでＳ６８０の「推移によるＤＦＡ状態削除」を行う。
【００９４】
図１９のＳ７００において、状態ｄｓ｛８｝の推移群ｂ，ｃ，ｏｔｈｅｒのうち、推移ｎｅ（ｂ）に適合する推移であるｂ，ｏｔｈｅｒを特定する。Ｓ７１０において適合する推移があったため、Ｓ７２０に進み、未処理である推移ｂがあるため、Ｓ７３０に進む。Ｓ７３０では適合する推移ｂを取り出し、推移ｄｅに保持する。Ｓ７４０では推移ｄｅ（ｂ）の推移先のＤＦＡ状態｛２，３｝を状態ｄｓ１として保持し、推移ｎｅ（ｂ）の推移先のＮＦＡ状態Ｓ３を状態ｎｓ１として保持し。これらを引数としてＳ５２０のサブルーチンＤＦＡ状態削除を行う。
【００９５】
ＤＦＡ状態削除サブルーチンの二度目の再帰について説明する。
【００９６】
図１８のＳ６１０において、状態ｄｓ｛２，３｝はＮＵＬＬではないため、Ｓ６２０で状態ｎｓのＳ３という状態を状態ｄｓから削除し、その結果状態ｄｓが保持するＮＦＡ状態群は｛２｝となる。Ｓ６３０で状態ｄｓ｛２｝はＮＦＡ状態を保持しているため、Ｓ６５０で、状態ｎｓからの推移を取得する。次に、Ｓ６６０で未処理である推移がないため、本サブルーチンの処理を終了（ｒｅｔｕｒｎ）する。図１４はこの時点のＤＦＡを示している。
【００９７】
図１９のＳ５２０の処理が完了したため、Ｓ７２０に進む。Ｓ７２０では未処理である推移ｏｔｈｅｒがあるため、Ｓ７３０に進む。Ｓ７３０では適合する推移ｏｔｈｅｒを取り出し、推移ｄｅに保持する。Ｓ７４０では推移ｄｅ（ｏｔｈｅｒ）の推移先のＤＦＡ状態｛２｝を状態ｄｓ１として保持し、推移ｎｅ（ｏｔｈｅｒ）の推移先のＮＦＡ状態Ｓ２を状態ｎｓ１として保持し、これらを引数としてＳ５２０のサブルーチンＤＦＡ状態削除を行う。
【００９８】
ＤＦＡ状態削除サブルーチンの三度目の再帰について説明する。
【００９９】
図１８のＳ６１０において、状態ｄｓ｛２｝はＮＵＬＬでないため、Ｓ６２０で状態ｎｓのＳ２という状態を状態ｄｓから削除し、その結果状態ｄｓが保持するＮＦＡ状態群はＮＵＬＬとなる。Ｓ６３０で状態ｄｓはＮＦＡ状態を保持していないため、Ｓ６４０で、ｄ８を削除し、本サブルーチンの処理を終了（ｒｅｔｕｒｎ）する。
【０１００】
図１９のＳ５２０の処理が完了したため、Ｓ７２０に進む。Ｓ７２０では未処理である推移がないため、本サブルーチンの処理を終了（ｒｅｔｕｒｎ）する。図１５はこの時点のＤＦＡを示している。
【０１０１】
図１８のＳ６８０の処理が完了したため、Ｓ６６０に進む。Ｓ６６０において未処理である推移＊があるため、Ｓ６７０で＊を推移ｎｅに保持する。次に、状態ｄｓと推移ｎｅでＳ３６０の「推移によるＤＦＡ状態削除」を行う。
【０１０２】
図１９のＳ７００において、状態ｄｓ｛８｝の状態群ｂ，ｃ，ｏｔｈｅｒのうち、推移ｎｅ（＊）に適合する推移であるｂ，ｃ，ｏｔｈｅｒを特定する。Ｓ７１０において適合する推移があったため、Ｓ７２０に進み、未処理である推移ｃがあるため、Ｓ７３０に進む。Ｓ７３０では適合する推移ｃを取り出し、推移ｄｅに保持する。Ｓ７４０では推移ｄｅ（ｃ）の推移先のＤＦＡ状態｛２，９｝を状態ｄｓ１として保持し、推移ｎｅ（＊）の推移先のＮＦＡ状態Ｓ２を状態ｎｓ１として保持し、これらを引数としてＳ５２０のサブルーチンＤＦＡ状態削除を行う。
【０１０３】
前記の処理を繰り返すことにより、図６のＤＦＡが更新されて最終的に図１６に示すＤＦＡになる。これにより、図１７のＳ５２０で、ＤＦＡ状態更新が終了した後、Ｓ５３０で図６のＮＦＡから削除するＸＰａｔｈ式に相当するＮＦＡを削除し、図１６のＮＦＡになる。
【０１０４】
以上、第２実施形態（差分削除）を説明した。第１実施形態（図１０〜図１２）および第２実施形態（図１７〜図１９）で示したように、本発明は更新前ＸＰａｔｈ式から導出された更新前ＮＦＡに対して、推移に従って状態を順に辿る処理（深さ優先や幅優先など）を実行し、その実行過程において更新前ＮＦＡにおける各推移に適合する更新前ＤＦＡの推移を特定して、更新前ＤＦＡの各状態が保持するＮＦＡ状態群と推移群を確認し、当該ＮＦＡ状態群および推移群と差分ＮＦＡとの差分を更新することを特徴とする。
【０１０５】
なお、本発明は前記した実施形態に限定されることなく、幅広く変形実施することができる。例えば、ＮｅｗｓＭＬは一例でありＸＭＬデータがＮｅｗｓＭＬに限定されることはない。例えば、ＸＭＬデータがＮＩＴＦ（News Industry Text Format）データ等でもよい。また、フィルタエンジン１０は、例えばＡＳＰ（Application Service Provider）が企業や個人ユーザのために設置したり、企業や団体等が自社の社員や構成員等のために設置したりする。また、前記実施形態で示したＤＦＡに対するＸＰａｔｈ式の情報の差分追加の手段・手法は一例であり、本発明が前記実施形態で示した差分追加の手段・手法に限定されることはない。また、前記したフローなどは、ＸＰａｔｈ式処理プログラムとしてネットワーク上を伝送されたり、ＣＤ−ＲＯＭ等の記憶媒体に記憶されて流通されたりする。
【０１０６】
また、フィルタエンジン１０を構成する装置は、１台に限定されることはなく、複数の装置に機能を分散配置してもよい。例えば、フィルタ処理を実行する装置（ＸＭＬパースモジュール１１、データ抽出モジュール１３、および、データ変換モジュール１６）と、フィルタ処理のためのオートマトンを作成する装置（問い合わせパースモジュール１１、ＤＦＡ作成モジュール１３Ｂ、オートマトン管理部１５、ＤＦＡ更新モジュール１７、更新オートマトン管理部１８）とを、別々の装置として構成してもよい。これにより、各装置への負荷が分散され、高速な処理が実現可能となる。
【図面の簡単な説明】
【０１０７】
【図１】本発明の一実施形態に関するＸＰａｔｈ式処理方法を実行するフィルタエンジンの概要を示す構成図である。
【図２】本発明の一実施形態に関する図１のフィルタエンジンの内部構成を示す構成図である。
【図３】本発明の一実施形態に関する図２におけるオートマトン管理部のメモリ上でのデータ構成を示す説明図である。
【図４】本発明の一実施形態に関する図３の具体的なプログラム上でのデータ構造を示す説明図である。
【図５】本発明の一実施形態に関する図４のＤＦＡのメモリ上でのデータ構成を示す説明図である。
【図６】本発明の一実施形態に関する更新前のデータの例を示す状態遷移図である。
【図７】本発明の第１実施形態に関する追加するデータの例を示す状態遷移図である。
【図８】本発明の第１実施形態に関するＤＦＡ追加の例（途中の状態）を示す状態遷移図である。
【図９】本発明の第１実施形態に関するＤＦＡ追加の例（最終状態）を示す状態遷移図である。
【図１０】本発明の第１実施形態に関するＤＦＡ追加処理を示すフローチャートである。
【図１１】本発明の第１実施形態に関するＤＦＡ状態更新サブルーチンを示すフローチャートである。
【図１２】本発明の第１実施形態に関する推移によるＤＦＡ状態更新サブルーチンを示すフローチャートである。
【図１３】本発明の第２実施形態に関する削除するＸＰａｔｈ式とそのＮＦＡを示す状態遷移図である。
【図１４】本発明の第２実施形態に関するＤＦＡ削除の例（途中の状態）を示す状態遷移図である。
【図１５】本発明の第２実施形態に関するＤＦＡ削除の例（途中の状態）を示す状態遷移図である。
【図１６】本発明の第２実施形態に関するＤＦＡ削除の例（最終状態）を示す状態遷移図である。
【図１７】本発明の第２実施形態に関するＤＦＡ削除処理を示すフローチャートである。
【図１８】本発明の第２実施形態に関するＤＦＡ状態削除サブルーチンを示すフローチャートである。
【図１９】本発明の第２実施形態に関する推移によるＤＦＡ状態削除サブルーチンを示すフローチャートである。
【符号の説明】
【０１０８】
１０    フィルタエンジン
１１    ＸＭＬパースモジュール
１２    問い合わせパースモジュール
１３    データ抽出モジュール
１３Ｂ  ＤＦＡ作成モジュール
１５    オートマトン管理部
１６    データ変換モジュール
１７    ＤＦＡ更新モジュール
１８    更新オートマトン管理部
【図１】
2007011998.tif 000003
【図２】
2007011998.tif 000004
【図３】
2007011998.tif 000005
【図４】
2007011998.tif 000006
【図５】
2007011998.tif 000007
【図６】
2007011998.tif 000008
【図７】
2007011998.tif 000009
【図８】
2007011998.tif 000010
【図９】
2007011998.tif 000011
【図１０】
2007011998.tif 000012
【図１１】
2007011998.tif 000013
【図１２】
2007011998.tif 000014
【図１３】
2007011998.tif 000015
【図１４】
2007011998.tif 000016
【図１５】
2007011998.tif 000017
【図１６】
2007011998.tif 000018
【図１７】
2007011998.tif 000019
【図１８】
2007011998.tif 000020
【図１９】
2007011998.tif 000021