(57)【特許請求の範囲】
【請求項１】
タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得し、
前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成し、
生成された前記パスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定し、
一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する、
処理をコンピュータに実行させることを特徴とする更新プログラム。
【請求項２】
前記パスを生成する処理は、
前記開始タグが読み込まれると前記パスの末尾に前記開始タグのタグ内文字列を追加することにより前記パスを更新することを特徴とする請求項１に記載の更新プログラム。
【請求項３】
前記入力ストリームから終了タグが読み込まれると、前記条件に一致すると判定されたパスが、前記開始タグまでの経路を示すパスに包含される上位パスであるか否かを判断し、
前記上位パスであると判断された場合、前記終了状態において前記開始タグ内の文字列が走査された場合の前記終了状態から前記パス照合状態への遷移を生成することにより、更新後のオートマトンを更新する、
処理をコンピュータに実行させることを特徴とする請求項１または２に記載の更新プログラム。
【請求項４】
前記パスを生成する処理は、
前記終了タグが読み込まれると前記パスの末尾から前記終了タグのタグ内文字列を削除することにより前記パスを更新することを特徴とする請求項３に記載の更新プログラム。
【請求項５】
前記パスと当該パス内の末尾のタグ内文字列を示す終了タグが読込済みか否かを示す情報とを登録し、
登録された前記パス内の末尾の終了タグが前記入力ストリームから最初に読み込まれたか否かを判断する、
処理を前記コンピュータに実行させ、
前記上位パスであるか否かを判断する処理は、
前記末尾の終了タグが前記入力ストリームから最初に読み込まれたと判断された場合、
前記条件に一致すると判定されたパスが、前記開始タグまでの経路を示すパスに包含され
る上位パスであるか否かを判断することを特徴とする請求項３または４に記載の更新プログラム。
【請求項６】
前記入力ストリームから前記タグ以外の文字が読み込まれると、前記オートマトンにしたがって前記オートマトンの現在の走査位置となる状態から前記文字に対応する状態に遷移させる処理を前記コンピュータに実行させることを特徴とする請求項１〜５のいずれか一つに記載の更新プログラム。
【請求項７】
コンピュータが、
タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得し、
前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成し、
生成された前記パスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定し、
一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する、
処理を実行することを特徴とする更新方法。
【請求項８】
タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得する取得部と、
前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成する生成部と、
前記生成部によって生成されたパスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定する判定部と、
前記判定部によって一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する更新部と、
を有することを特徴とする更新装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、更新プログラム、更新方法、および更新装置に関する。
【背景技術】
【０００２】
従来、入力ＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）データのタグをパススキーマ内のパスを特定するパスＩＤに置き換えて、パス・キーワード照合オートマトンを作成する従来技術１が開示されている。また、入力ＸＭＬデータからＳＡＸ（Ｓｉｍｐｌｅ  ＡＰＩ  ｆｏｒ  ＸＭＬ）イベントを生成して、生成したＳＡＸイベントに応じてパス照合オートマトンを更新する従来技術２が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開第２００８／１１７４５４号
【特許文献２】特開２００３−３２３４２９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述した従来技術１では、入力ＸＭＬデータのパススキーマをあらかじめ認識しておく必要がある。したがって、パススキーマが不明なＸＭＬデータを受信した場合、ＸＭＬデータ全体のパススキーマを認識する処理を実行しなければならず、オートマトンによる照合に遅延が生じることになる。また、上述した従来技術２では、単に新規のＸＰａｔｈとの差分をすべて追加してオートマトンを構築するため、その間オートマトンの走査を実行できなくなる。
【０００５】
本発明は、オートマトンの照合処理の高速化を図ることを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一側面によれば、タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得し、前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成し、生成された前記パスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定し、一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する更新プログラム、更新方法、および更新装置が提案される。
【発明の効果】
【０００７】
本発明の一側面によれば、オートマトンの照合処理の遅延を抑制することができるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】図１は、本実施の形態にかかるオートマトン更新例を示す説明図である。
【図２】図２は、入力ストリームＳとクエリＱとの照合例を示す説明図である。
【図３】図３は、入力ストリームＳの変換例を示す説明図である。
【図４】図４は、入力ストリームＳのパスを示す説明図である。
【図５】図５は、パスＩＤ管理テーブルの一例を示す説明図である。
【図６】図６は、初期オートマトンＡ０の構築例を示す説明図である。
【図７】図７は、ノード構造体の一例を示す説明図である。
【図８】図８は、初期オートマトンＡ０における各状態のノード構造体Ｎの一例を示す説明図である。
【図９】図９は、オートマトンＡの動作例（その１）を示す説明図である。
【図１０】図１０は、オートマトンＡの動作例（その２）を示す説明図である。
【図１１】図１１は、オートマトンＡの動作例（その３）を示す説明図である。
【図１２】図１２は、オートマトンＡの動作例（その４）を示す説明図である。
【図１３】図１３は、オートマトンＡの動作例（その５）を示す説明図である。
【図１４】図１４は、オートマトンＡの動作例（その６）を示す説明図である。
【図１５】図１５は、パス照合状態Ｎ３のノード構造体Ｎの一例を示す説明図である。
【図１６】図１６は、キーワード照合途中状態およびキーワード照合完了状態のノード構造体Ｎの一例を示す説明図である。
【図１７】図１７は、開始状態Ｎ１の更新例を示す説明図である。
【図１８】図１８は、オートマトンＡの動作例（その７）を示す説明図である。
【図１９】図１９は、オートマトンＡの動作例（その８）を示す説明図である。
【図２０】図２０は、オートマトンＡの動作例（その９）を示す説明図である。
【図２１】図２１は、終了状態Ｎ２の更新例を示す説明図である。
【図２２】図２２は、オートマトンＡの動作例（その１０）を示す説明図である。
【図２３】図２３は、オートマトンＡの動作例（その１１）を示す説明図である。
【図２４】図２４は、オートマトンＡの動作例（その１２）を示す説明図である。
【図２５】図２５は、オートマトンＡの動作例（その１３）を示す説明図である。
【図２６】図２６は、更新装置１００のハードウェア構成例を示すブロック図である。
【図２７】図２７は、更新装置１００の機能的構成例を示すブロック図である。
【図２８】図２８は、更新装置１００による更新処理手順例を示すフローチャートである。
【図２９】図２９は、図２８に示した初期オートマトン構築処理（ステップＳ２８０３）の詳細な処理手順例を示すフローチャートである。
【図３０】図３０は、図２８に示した第１の走査処理（ステップＳ２８０９）の詳細な処理手順例を示すフローチャートである。
【図３１】図３１は、図３０に示した第１の更新処理（ステップＳ３００６）の詳細な処理手順例を示すフローチャートである。
【図３２】図３２は、図２８に示した第２の走査処理（ステップＳ２８１０）の詳細な処理手順例を示すフローチャートである。
【図３３】図３３は、図２８に示した第３の走査処理（ステップＳ２８１１）の詳細な処理手順例を示すフローチャートである。
【図３４】図３４は、図３３に示した第２の更新処理（ステップＳ３３０５）の詳細な処理手順例を示すフローチャートである。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、本発明にかかる更新プログラム、更新装置、および更新方法の実施の形態を詳細に説明する。なお、本実施の形態では、オートマトンを総称する符号として「Ａ」を用いるが、更新の状態を特定するために、「Ａ０」，「Ａ１」，「Ａ２」の符号を付すことがある。「Ａ０」は初期のオートマトンを示す符号であり、「Ａ１」は１回目の更新後のオートマトンを示す符号であり、「Ａ２」は２回目の更新後のオートマトンを示す符号である。
【００１０】
＜オートマトン更新例＞
図１は、本実施の形態にかかるオートマトン更新例を示す説明図である。本実施の形態では、図１に示すように、更新装置１００が、オートマトンＡを、初期のオートマトン（以下、初期オートマトンＡ０）から、照合に必要な部分ごとに段階的に更新することで、現段階で不要な部分の更新にかかる時間をオートマトンＡの走査に当てることができる。したがって、オートマトンＡによる照合処理の遅延を抑制することができる。以下、具体的に説明する。
【００１１】
上述したオートマトンＡの更新は、更新装置１００により実行される。更新装置１００は、クエリＤＢ（Ｄａｔａ  Ｂａｓｅ）１０２とオートマトンＡとを記憶する。クエリＤＢ１０２は、クエリＱを記憶するデータベースである。クエリＱとは、データ照合の条件と、当該条件に一致した場合に出力されるキーワードと、を有する。更新装置１００は、タグにより階層化された入力ストリームＳの発生源Ｇとなるコンピュータから、ネットワーク１０１を介して入力ストリームＳを受信する。入力ストリームＳとしては、たとえば、ＸＭＬデータやＨＴＭＬ（ＨｙｐｅｒＴｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）データが挙げられるが、本例ではＸＭＬデータを例に挙げて説明する。
【００１２】
入力ストリームＳは、タグにより階層化されている。図１の入力ストリームＳでは、＜タップ＞および＜／タップ＞が最上位である第１階層のタグである。また、＜タップＩＤ＞および＜／タップＩＤ＞が第２階層のタグである。また、＜ソケット＞および＜／ソケット＞も第２階層のタグである。また、＜電力＞および＜／電力＞が最下位の第３階層のタグである。
【００１３】
更新装置１００は、入力ストリームＳの先頭から読み込み、オートマトンＡを走査しながら、キーワードの照合をおこなう。本実施の形態では、最上位階層のタグ内文字列から現在読み込まれたタグ内文字列に至るまでの経路を「パス」と称す。たとえば、開始タグ＜タップＩＤ＞が読み込まれた場合、第１階層の＜タップ＞の「タップ」から第２階層の＜タップＩＤ＞の「タップＩＤ」までの経路が、開始タグ＜タップＩＤ＞のパスとなる。また、開始タグ＜電力＞が読み込まれた場合、第１階層の＜タップ＞の「タップ」⇒第２階層の＜ソケット＞の「ソケット」⇒第３階層の＜電力＞の「電力」までの経路が、開始タグ＜電力＞のパスとなる。
【００１４】
更新装置１００は、現在読み込まれたタグのパスが、クエリＱの条件に一致するか否かを判断する。図１のクエリＱの条件は、「／タップ／／ソケット」である。これは、第１階層の＜タップ＞の「タップ」から任意の階層の＜ソケット＞の「ソケット」までのパスを意味する。現在読み込まれたタグのパスがクエリＱの条件に一致する場合、更新装置１００は、オートマトンＡを更新する。「／／」は、任意の数の階層をまたいでよいことを表す。
【００１５】
初期オートマトンＡ０は、初期状態と、開始状態と、終了状態と、を有する。開始状態とは、開始タグの開始タグ記号である「＜＞」に相当する状態である。本例では、開始タグ記号「＜＞」は「［」に変換される。終了状態とは、終了タグの終了タグ記号である「＜／＞」に相当する状態である。本例では、終了タグ記号「＜／＞」は「］」に変換される。初期オートマトンＡ０は、さらに、初期状態と開始状態との間の遷移、初期状態と終了状態との間の遷移、初期状態でループする遷移を有する。
【００１６】
１回目のオートマトンＡの更新においては、更新装置１００は、クエリＱの条件と一致したパスに対応する新しい状態を生成する。生成する新状態を、「パス照合状態」と称す。パス照合状態には、クエリＱの条件と一致したパスに固有なパスＩＤが割当てられる。図１の例では、「３」が割当てられる。
【００１７】
また、１回目のオートマトンＡの更新においては、更新装置１００は、開始状態からの遷移先の変更をおこなう。具体的には、更新装置１００は、開始状態からパス照合状態への遷移、パス照合状態から開始状態や終了状態への遷移、パス照合状態からクエリＱ内のキーワードへの遷移、その遷移先状態を生成する。本例では、クエリＱのキーワードとして「ＥＲＲ」が登録されている。
【００１８】
更新装置１００は、入力ストリームＳの走査位置がパス照合状態のときに「ＥＲＲ」を読み込んだ場合に、クエリＱのキーワードと照合できるよう、パス照合状態からの第１遷移「Ｅ」とその第１遷移先状態、第１遷移先状態からの第２遷移「Ｒ」とその第２遷移先状態、第２遷移先状態から第３遷移「Ｒ」とその第３遷移先状態を生成する。これにより、１回目のオートマトンＡの更新が終了する。
【００１９】
１回目のオートマトンＡの更新では、終了状態からパス照合状態への遷移が生成されていない。オートマトンＡによる走査は、終了状態からパス照合状態への遷移がない状態でも当該遷移による走査が必要になるまでは可能である。したがって、終了状態からパス照合状態への遷移の生成のために、走査を停止する必要がないため、照合処理の遅延を抑制することができる。
【００２０】
１回目のオートマトンＡの更新のあと、終了状態からパス照合状態への遷移が走査に必要になった場合に、更新装置１００は、終了状態からの遷移先の変更をおこなう。具体的には、終了状態からパス照合状態への遷移を生成することで、２回目のオートマトンＡの更新を実行する。２回目のオートマトンＡの更新では、走査位置が終了状態に位置する場合、更新装置１００は、クエリＱと一致したパスが、終了タグのタグ内文字列に至るまでのパスの親パスであるか否かを判断する。具体的には、終了タグのタグ内文字列に至るまでのパスから、終了タグのタグ内文字列を削除したパスが、クエリＱと一致したパスと同一パスであれば、クエリＱと一致したパスは親パスとなる。親パスである場合、終了状態からの遷移先がパス照合状態となる。したがって、親パスが検出されてから、終了状態からの遷移先の変更が実行される。
【００２１】
このように、更新装置１００は、３種類のオートマトン更新処理である「新しい状態の生成」、「開始状態からの遷移先の変更」、「終了状態からの遷移先の変更」のうち、「終了状態からの遷移先の変更」の処理を終了タグ検出のタイミングまで実行しない。したがって、オートマトン更新処理の負荷を分散し、処理の遅延時間を抑制することができる。
【００２２】
＜入力ストリームＳとクエリＱとの照合例＞
図２は、入力ストリームＳとクエリＱとの照合例を示す説明図である。クエリＱは、入力ストリームＳにおいて第１階層が「タップ」であるレコードに存在する「ソケット」に文字列「ＥＲＲ」が含まれる場合に、文字列「ＥＲＲ」が照合結果として更新装置１００から出力される。
【００２３】
図３は、入力ストリームＳの変換例を示す説明図である。更新装置１００は、入力ストリームＳを先頭の＜タップ＞から末尾の＜／タップ＞まで順次読み込む。更新装置１００は、タグについて変換をおこなう。これにより、タグが圧縮されるため、オートマトンＡの縮小化を図ることができる。図３の例では、開始タグ記号「＜＞」は「［」に変換される。また、終了タグ記号「＜／＞」は「］」に変換される。また、タグ内文字列は、各々固有な番号に変換される。本例では、読み込み順に、「１」、「２」、…に変換される。たとえば、「タップ」が「１」に、「タップＩＤ」が「２」に、「ソケット」が「３」に、「電力」が「４」に変換される。なお、変換された入力ストリームＳを、「変換ストリームｓ」と称す。
【００２４】
図４は、入力ストリームＳのパスを示す説明図である。パスとは、入力ストリームＳの階層に従って入力ストリームＳ内の各タグに到達するまでの経路を示す情報である。本例では、理解の容易のため、便宜上、入力ストリームＳについてのパススキーマを用いてパスを説明するが、入力ストリームＳがどのように構成されているかは、入力ストリームＳを読み込んで自ら解析するまで更新装置１００は認識していない。
【００２５】
パススキーマは、第０階層を示すルートから入力ストリームＳの階層構造を示すツリー構造体である。本例の入力ストリームＳでは、「タップ」が第１階層、「タップＩＤ」および「ソケット」が第２階層、「電力」が第３階層となる。ルートから第１階層の「タップ」に至るまでの経路がパスｐ１、ルートから「タップＩＤ」に至るまでの経路がパスｐ２、ルートから「ソケット」に至るまでの経路がパスｐ３、ルートから「電力」に至るまでの経路がパスｐ４である。
【００２６】
各パスｐ１〜ｐ４に割当てた数字は、図３で変換した固有な番号に対応する。具体的には、パスｐ＃（＃は数字）は、＃に変換されたタグ文字列に到達するパスである。たとえば、パスｐ２は、「２」に変換されたタグ内文字列「タップＩＤ」に到達するパスである。また、パスｐ４は、「４」に変換されたタグ内文字列「電力」に到達するパスである。＃は、後述するパスＩＤとなる。更新装置１００は、入力ストリームＳの読み込み中に、現在読み込んでいるタグを末尾とするパスを検出することになる。
【００２７】
図５は、パスＩＤ管理テーブルの一例を示す説明図である。パスＩＤ管理テーブルＴは、パスＩＤを管理するテーブルである。パスＩＤ管理テーブルＴは、パスＩＤ項目と、パス項目と、フラグ項目と、を有し、パスごとに、各項目の値がレコードとして格納される。デフォルトではレコードはない空の状態である。パスＩＤ項目には、パスＩＤが格納される。パスＩＤとは、パスを一意に特定する識別情報であり、上述した＃となる。パス項目には、パスが格納される。たとえば、パスＩＤ：４のパスｐ４の場合、「／タップ／ソケット／電力」が格納される。
【００２８】
フラグ項目には、フラグが格納される。フラグの値は「１」または「０」である。デフォルトは「０」である。フラグとは、そのパスにより到達したタグが終了タグとして一度でも入力ストリームＳに出現したか否かを示す識別子である。未出現の場合が「０」であり、一度でも出現すれば「１」に設定される。たとえば、入力ストリームＳの読み込み中に開始タグ＜タップＩＤ＞が出現すると、更新装置１００は、パスｐ２を検出して、パスＩＤ管理テーブルＴの新規レコードに、パスＩＤ：２と、パスｐ２（／タップ／タップＩＤ）を登録する。その後、終了タグ＜／タップＩＤ＞が出現すると、更新装置１００は、パスｐ２のフラグを「０」から「１」に変更する。
【００２９】
このようにして、パスＩＤ管理テーブルＴには、パスが検出される都度レコードが追加され、その終了タグが検出されると、フラグが変更される。これにより、終了タグの直後に読み込まれた開始タグは、その終了タグのパスよりも１階層上の階層から辿ることにより、パスを検出できることになる。たとえば、パスｐ２の終了タグ＜／タップＩＤ＞のあとに開始タグ＜ソケット＞が出現するが、１つ上の階層の＜タップ＞に戻ってから＜ソケット＞に辿ることにより、パスｐ３を検出することができる。
【００３０】
図６は、初期オートマトンＡ０の構築例を示す説明図である。図１に示したように、更新装置１００は、初期オートマトンＡ０を記憶する。初期オートマトンＡ０は、どの入力ストリームＳにも適用可能であるため、或るタイミングで構築して更新装置１００内に保存しておけばよい。初期オートマトンＡ０が未構築の場合、更新装置１００は、（Ａ）において、初期状態Ｎ０と、開始タグ記号「＜＞」から変換された開始タグ記号「［」を示す開始状態Ｎ１と、終了タグ記号「＜／＞」から変換された終了タグ記号「］」を示す終了状態Ｎ２と、を生成する。そして、更新装置１００は、初期状態Ｎ０自身のループとなる遷移ｔ００と、開始状態Ｎ１から初期状態Ｎ０への遷移ｔ１０と、終了状態Ｎ２から初期状態Ｎ０への遷移ｔ２０を生成する。「Σ」は、すべての記号を示す。なお、以下の図面中の遷移の符号ｔｘｙにおいて、ｘは遷移元の状態の状態ＩＤを示し、ｙは遷移先の状態の状態ＩＤを示す。
【００３１】
更新装置１００は、（Ｂ）において、初期状態Ｎ０自身のループとなる遷移ｔ００から「［」および「］」を削除し、初期状態Ｎ０から開始状態Ｎ１への遷移ｔ０１と、初期状態Ｎ０から終了状態Ｎ２への遷移ｔ０２を生成する。これにより、初期オートマトンＡ０が構築される。構築された初期オートマトンＡ０は、更新装置１００内の記憶領域に格納され、入力ストリームＳの受信が開始される都度、読み出される。
【００３２】
図７は、ノード構造体の一例を示す説明図である。ノード構造体Ｎとは、オートマトンＡの状態の特徴を記憶するデータ構造体である。具体的には、ノード構造体Ｎは、状態ごとに、状態ＩＤと、状態の種類と、リストＬとを記憶する。状態ＩＤとは、状態を一意に特定する識別状態である。各状態には、状態ＩＤとして固有の識別情報が割当てられる。状態の種類とは、その状態が、どのような種類なのかを特定する属性情報である。たとえば、上述した「初期状態」、「開始状態」、「終了状態」がある。このほか、「パス照合状態」、「キーワード照合途中状態」、「キーワード照合完了状態」がある。「パス照合状態」、「キーワード照合途中状態」、「キーワード照合完了状態」については、後述する。
【００３３】
リストＬとは、状態の遷移先状態を特定する遷移を保持するデータ構造である。具体的には、リストＬには、記号ごとに領域が用意されており、その領域に遷移先状態の状態ＩＤが格納される。以下、図８に、初期オートマトンＡ０を構成する状態のノード構造体Ｎを示す。
【００３４】
図８は、初期オートマトンＡ０における各状態のノード構造体Ｎの一例を示す説明図である。図８において、（Ａ）に初期状態Ｎ０のノード構造体Ｎ、（Ｂ）に開始状態Ｎ１のノード構造体Ｎ、（Ｃ）に終了状態Ｎ２のノード構造体Ｎを示す。
【００３５】
（Ａ）において、初期状態Ｎ０の状態ＩＤは「０」である。また、初期状態Ｎ０であるため、状態の種類は「初期」である。また、初期状態Ｎ０において、「［」が出現すると開始状態Ｎ１に遷移することになるため、リストＬの記号「［」の領域には、開始状態Ｎ１の状態ＩＤ：１が格納される。同様に、初期状態Ｎ０において、「］」が出現すると終了状態Ｎ２に遷移することになるため、リストＬの記号「］」の領域には、終了状態Ｎ２の状態ＩＤ：２が格納される。また、全記号Σのうち「［」および「］」を除いた「Σ＼｛［，］｝」の各々については、初期状態Ｎ０自身にループするため、「Σ＼｛［，］｝」の各記号の領域には、初期状態Ｎ０の状態ＩＤ：０が格納される。
【００３６】
（Ｂ）において、開始状態Ｎ１の状態ＩＤは「１」である。また、開始状態Ｎ１であるため、状態の種類は「開始」である。また、開始状態Ｎ１において、全記号Σのいずれの記号が出現しても初期状態Ｎ０に遷移することになるため、リストＬの各記号の領域には、初期状態Ｎ０の状態ＩＤ：０が格納される。
【００３７】
（Ｃ）において、終了状態Ｎ２の状態ＩＤは「２」である。また、終了状態Ｎ２であるため、状態の種類は「終了」である。また、終了状態Ｎ２において、全記号Σのいずれの記号が出現しても初期状態Ｎ０に遷移することになるため、リストＬの各記号の領域には、初期状態Ｎ０の状態ＩＤ：０が格納される。
【００３８】
＜オートマトンＡの動作例＞
つぎに、オートマトンＡの動作例について具体的に説明する。以下の図において、図中、旗印は、オートマトンＡの現在位置を示し、太矢印は走査を示す。
【００３９】
図９は、オートマトンＡの動作例（その１）を示す説明図である。図９は、初期オートマトンＡ０の走査開始前の状態を示している。図９では、クエリＱと初期オートマトンＡ０が用意されている。また、入力ストリームＳの各入力データが格納される第１バッファｂ１および入力データから変換された変換入力データが格納される第２バッファｂ２は、空である。また、第３バッファｂ３には現在のパスが登録される。図９は走査前であるため、第３バッファｂ３も空である。また、パスＩＤ管理テーブルＴにもレコードは存在しない。
【００４０】
図１０は、オートマトンＡの動作例（その２）を示す説明図である。図１０は、図９の状態から入力ストリームＳの先頭データである開始タグ＜タップ＞が受信された場合の処理を示している。入力ストリームＳの先頭データである開始タグ＜タップ＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜タップ＞を読み出して「［１」に変換し、第２バッファｂ２に書き込む。また、開始タグ＜タップ＞が受信されたため、更新装置１００は、現在のパスｐとして、「／タップ」を検出して第３バッファｂ３に書き込む。そして、更新装置１００は、パスＩＤ管理テーブルＴに、パスＩＤ：１、第３バッファｂ３内のパス「／タップ」、フラグ：０のレコードを登録する。第３バッファｂ３のパスｐ１はクエリＱの条件に一致しないため、更新装置１００は、第２バッファｂ２の「［」により、走査位置である初期状態Ｎ０から開始状態Ｎ１に走査し、第２バッファｂ２の「１」により、開始状態Ｎ１から初期状態Ｎ０に走査する。
【００４１】
図１１は、オートマトンＡの動作例（その３）を示す説明図である。図１１は、図１０の状態から入力ストリームＳの開始タグ＜タップＩＤ＞が受信された場合の処理を示している。入力ストリームＳの開始タグ＜タップＩＤ＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜タップＩＤ＞を読み出して「［２」に変換し、第２バッファｂ２に書き込む。また、開始タグ＜タップＩＤ＞が受信されたため、更新装置１００は、第３バッファｂ３の「／タップ」の末尾に「／タップＩＤ」を書き込む。そして、更新装置１００は、パスＩＤ管理テーブルＴに、パスＩＤ：２、第３バッファｂ３内のパス「／タップ／タップＩＤ」、フラグ：０のレコードを登録する。また、第３バッファｂ３のパスｐ２はクエリＱの条件に一致しないため、更新装置１００は、第２バッファｂ２の「［」により、走査位置である初期状態Ｎ０から開始状態Ｎ１に走査し、第２バッファｂ２の「２」により、開始状態Ｎ１から初期状態Ｎ０に走査する。
【００４２】
図１２は、オートマトンＡの動作例（その４）を示す説明図である。図１２は、図１１の状態から入力ストリームＳの文字「１」が受信された場合の処理を示している。入力ストリームＳの文字「１」が第１バッファｂ１に書き込まれると、更新装置１００は、文字「１」を読み出して変換せずに第２バッファｂ２に書き込む。また、文字が受信された場合、パスＩＤ管理テーブルＴへの登録は実行されない。更新装置１００は、第２バッファｂ２の「１」により、走査位置である初期状態Ｎ０から初期状態Ｎ０に走査する。
【００４３】
図１３は、オートマトンＡの動作例（その５）を示す説明図である。図１３は、図１２の状態から入力ストリームＳの終了タグ＜／タップＩＤ＞が受信された場合の処理を示している。入力ストリームＳの終了タグ＜／タップＩＤ＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜／タップＩＤ＞を読み出して「］２」に変換し、第２バッファｂ２に書き込む。また、終了タグ＜／タップＩＤ＞が受信されたため、更新装置１００は、パスＩＤ管理テーブルＴにおいて、終了タグ＜／タップＩＤ＞のタグ内文字列「タップＩＤ」を末尾とするパスｐ２のフラグを「１」に設定する。
【００４４】
フラグを「１」に設定した場合、更新装置１００は、パス照合状態がオートマトンＡに存在するか否かを判断する。この時点では、パス照合状態が存在しないため、更新装置１００は、第２バッファｂ２の「］２」の「］」により、走査位置である初期状態Ｎ０から終了状態Ｎ２に走査し、第２バッファｂ２の「］２」の「２」により、終了状態Ｎ２から初期状態Ｎ０に走査する。そして、更新装置１００は、第３バッファｂ３のパスｐ２：「／タップ／タップＩＤ」から「／」および終了タグ＜／タップＩＤ＞のタグ内文字列「タップＩＤ」を削除して、パスｐ１：「／タップ」に戻す。
【００４５】
図１４は、オートマトンＡの動作例（その６）を示す説明図である。図１４は、図１３の状態から入力ストリームＳの開始タグ＜ソケット＞が受信された場合の処理を示している。入力ストリームＳの開始タグ＜ソケット＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜ソケット＞を読み出して「［３」に変換し、第２バッファｂ２に書き込む。また、開始タグ＜ソケット＞が受信されたため、更新装置１００は、第３バッファｂ３の「／タップ」の末尾に「／」およびタグ内文字列「ソケット」を書き込む。そして、更新装置１００は、パスＩＤ管理テーブルＴに、パスＩＤ：３、第３バッファｂ３内のパス「／タップ／ソケット」、フラグ：０のレコードを登録する。
【００４６】
ここで、第３バッファｂ３のパスｐ３はクエリＱの条件に一致する。このため、更新装置１００は、オートマトンＡの１回目の更新を実行する。具体的には、更新装置１００は、まず、新規状態を生成する。新規状態は、パスＩＤ：３を示す状態である。この状態は、クエリＱと一致したパスｐ３を特定する状態であるため、パス照合状態と称す。また、第２バッファｂ２には、「［３」が書き込まれたため、パス照合状態Ｎ３は、開始状態Ｎ１からの遷移先状態となる。したがって、記号ΣのうちパスＩＤ：３を除いた記号「Σ＼｛３｝」で遷移される場合は、開始状態Ｎ１の遷移先は初期状態Ｎ０となる。一方、パスＩＤ：３で遷移される場合は、開始状態Ｎ１の遷移先はパス照合状態Ｎ３となる。
【００４７】
また、パス照合状態Ｎ３が生成されると、更新装置１００は、クエリＱのキーワードを構成する文字によりパス照合状態Ｎ３から順次遷移される遷移先状態を生成する。キーワードを構成する文字により遷移される遷移先状態のうち、末尾文字以外の文字により遷移される遷移先状態は、キーワード照合途中状態となり、末尾文字により遷移される遷移先状態は、キーワード照合完了状態となる。本例の場合、先頭文字「Ｅ」および２番目の文字「Ｒ」により遷移される遷移先状態は、キーワード照合途中状態Ｎ４，Ｎ５となり、末尾文字「Ｒ」により遷移される遷移先状態は、キーワード照合完了状態Ｎ６となる。
【００４８】
また、更新装置１００は、パス照合状態Ｎ３から開始状態Ｎ１への遷移と終了状態Ｎ２への遷移を生成する。また、更新装置１００は、パス照合状態Ｎ３が自身にループする遷移も生成する。この遷移は、全記号Σから開始タグ記号「［」、終了タグ記号「］」およびキーワードの先頭文字「Ｅ」を除いた記号「Σ＼｛［，］，Ｅ｝」となる。これにより、１回目のオートマトンＡの更新が完了する。ここで、１回目のオートマトンＡの更新後の各状態のノード構造体Ｎについて説明する。
【００４９】
図１５は、パス照合状態Ｎ３のノード構造体Ｎの一例を示す説明図である。図１５において、状態ＩＤは、０〜２まで割当済みであるため、パス照合状態Ｎ３の状態ＩＤを未割り当ての「３」とする。また、パス照合状態Ｎ３であるため、状態の種類は「パス照合」である。また、パス照合状態Ｎ３において、「［」が出現すると開始状態Ｎ１に遷移することになるため、リストＬの記号「［」の領域には、開始状態Ｎ１の状態ＩＤ：１が格納される。同様に、パス照合状態Ｎ３において、「］」が出現すると終了状態Ｎ２に遷移することになるため、リストＬの記号「］」の領域には、終了状態Ｎ２の状態ＩＤ：２が格納される。
【００５０】
同様に、パス照合状態Ｎ３において、文字「Ｅ」が出現すると、状態ＩＤ：４が割当てられたキーワード照合途中状態に遷移することになるため、リストＬの記号「４」の領域には、キーワード照合途中状態の状態ＩＤ：４が格納される。また、全記号Σのうち「［」、「］」および「４」を除いた「Σ＼｛［，］，４｝」の各々については、パス照合状態Ｎ３自身にループするため、「Σ＼｛［，］，４｝」の各記号の領域には、パス照合状態Ｎ３の状態ＩＤ：３が格納される。
【００５１】
図１６は、キーワード照合途中状態およびキーワード照合完了状態のノード構造体Ｎの一例を示す説明図である。図１６において、（Ａ）が先頭文字「Ｅ」で遷移されるキーワード照合途中状態Ｎ４、（Ｂ）が２番目の文字「Ｒ」で遷移されるキーワード照合途中状態Ｎ５、（Ｃ）が末尾文字「Ｒ」で遷移されるキーワード照完了状態Ｎ６を示す。
【００５２】
（Ａ）において、状態ＩＤは、「４」である。また、キーワード照合途中状態であるため、状態の種類は「キーワード照合途中」である。また、キーワード照合途中状態Ｎ４において、文字「Ｒ」が出現すると次のキーワード照合途中状態Ｎ５に遷移することになるため、リストＬの記号「Ｒ」の領域には、次のキーワード照合途中状態Ｎ５の状態ＩＤ：５が格納される。同様に、「［」が出現すると開始状態Ｎ１に遷移することになるため、リストＬの記号「［」の領域には、開始状態Ｎ１の状態ＩＤ：１が格納される。また、「］」が出現すると終了状態Ｎ２に遷移することになるため、リストＬの記号「］」の領域には、終了状態Ｎ２の状態ＩＤ：２が格納される。また、全記号Σのうち「［」、「］」および「５」を除いた「Σ＼｛［，］，５｝」の各々については、パス照合状態Ｎ３に遷移するため、「Σ＼｛［，］，５｝」の各記号の領域には、パス照合状態Ｎ３の状態ＩＤ：３が格納される。
【００５３】
（Ｂ）において、状態ＩＤは、「５」である。また、キーワード照合途中状態であるため、状態の種類は「キーワード照合途中」である。また、キーワード照合途中状態Ｎ５において、文字「Ｒ」が出現するとキーワード照合完了状態Ｎ６に遷移することになるため、リストＬの記号「Ｒ」の領域には、キーワード照合完了状態Ｎ６の状態ＩＤ：６が格納される。同様に、「［」が出現すると開始状態Ｎ１に遷移することになるため、リストＬの記号「［」の領域には、開始状態Ｎ１の状態ＩＤ：１が格納される。また、「］」が出現すると終了状態Ｎ２に遷移することになるため、リストＬの記号「］」の領域には、終了状態Ｎ２の状態ＩＤ：２が格納される。また、全記号Σのうち「［」、「］」および「５」を除いた「Σ＼｛［，］，５｝」の各々については、パス照合状態Ｎ３に遷移するため、「Σ＼｛［，］，５｝」の各記号の領域には、パス照合状態Ｎ３の状態ＩＤ：３が格納される。
【００５４】
（Ｃ）において、状態ＩＤは、「６」である。また、キーワード照合完了状態であるため、状態の種類は「キーワード照合完了」である。また、キーワード照合完了状態Ｎ６において、「［」が出現すると開始状態Ｎ１に遷移することになるため、リストＬの記号「［」の領域には、開始状態Ｎ１の状態ＩＤ：１が格納される。また、「］」が出現すると終了状態Ｎ２に遷移することになるため、リストＬの記号「］」の領域には、終了状態Ｎ２の状態ＩＤ：２が格納される。また、全記号Σのうち「［」および「］」を除いた「Σ＼｛［，］｝」の各々については、パス照合状態Ｎ３に遷移するため、「Σ＼｛［，｝」の各記号の領域には、パス照合状態Ｎ３の状態ＩＤ：３が格納される。
【００５５】
図１７は、開始状態Ｎ１の更新例を示す説明図である。開始状態Ｎ１のリストＬのうち、記号「３」の領域に、パス照合状態Ｎ３の状態ＩＤ：３が格納される。これにより、走査位置が開始状態Ｎ１である場合に、「３」が出現すると、パス照合状態Ｎ３に遷移し、「３」以外の記号が出現すると、初期状態Ｎ０に遷移することになる。つぎに、図１４に戻り、更新後のオートマトンＡによる走査の開始について説明する。
【００５６】
図１４において、更新装置１００は、更新後のオートマトンＡにより走査を開始する。更新装置１００は、第２バッファｂ２の「［３」の「［」により、走査位置である初期状態Ｎ０から開始状態Ｎ１に走査し、第２バッファｂ２の「３」により、開始状態Ｎ１からパス照合状態Ｎ３に走査する。走査位置は、パス照合状態Ｎ３となる。
【００５７】
図１８は、オートマトンＡの動作例（その７）を示す説明図である。図１８は、図１４の状態から入力ストリームＳの開始タグ＜電力＞が受信された場合の処理を示している。入力ストリームＳの開始タグ＜電力＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜電力＞を読み出して「［４」に変換し、第２バッファｂ２に書き込む。また、開始タグ＜電力＞が受信されたため、更新装置１００は、第３バッファｂ３の「／タップ／ソケット」の末尾に「／」およびタグ内文字列「電力」を書き込む。そして、更新装置１００は、パスＩＤ管理テーブルＴに、パスＩＤ：４、第３バッファｂ３内のパス「／タップ／ソケット／電力」、フラグ：０のレコードを登録する。また、第３バッファｂ３のパスｐ４はクエリＱの条件に一致しないため、更新装置１００は、第２バッファｂ２の「［４」のうち「［」により、走査位置であるパス照合状態Ｎ３から開始状態Ｎ１に走査し、第２バッファｂ２の「４」により、開始状態Ｎ１から初期状態Ｎ０に走査する。
【００５８】
図１９は、オートマトンＡの動作例（その８）を示す説明図である。図１９は、図１８の状態から入力ストリームＳの文字列「１０」が受信された場合の処理を示している。入力ストリームＳの文字列「１０」が第１バッファｂ１に書き込まれると、更新装置１００は、文字列「１０」を読み出して、変換せずに第２バッファｂ２に書き込む。また、文字列「１０」が受信された場合、パスＩＤ管理テーブルＴへの登録は実行されない。また、更新装置１００は、第２バッファｂ２の「１」により、走査位置である初期状態Ｎ０から初期状態Ｎ０に走査し、第２バッファｂ２の「０」により、走査位置である初期状態Ｎ０から初期状態Ｎ０に走査する。
【００５９】
図２０は、オートマトンＡの動作例（その９）を示す説明図である。図２０は、図１９の状態から入力ストリームＳの終了タグ＜／電力＞が受信された場合の処理を示している。入力ストリームＳの終了タグ＜／電力＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜／電力＞を読み出して「］４」に変換し、第２バッファｂ２に書き込む。また、終了タグ＜／電力＞が受信されたため、更新装置１００は、パスＩＤ管理テーブルＴにおいて、終了タグ＜／電力＞のタグ内文字列「電力」を末尾とするパスｐ４のフラグを「１」に設定する。
【００６０】
フラグを「１」に設定した場合、更新装置１００は、現在のパスｐ４の親パスを設定する。親パスとは、階層が１つ上のパスである。すなわち、現在のパスの末尾を削除することにより、親パスが生成される。図２０の場合、現在のパスｐ４の末尾「電力」を削除することにより、親パスｐ３が得られる。更新装置１００は、親パスｐ３に対応するパス照合状態がオートマトンＡに存在するか否かを判断する。この場合、親パスｐ３に対応するパス照合状態Ｎ３が存在することになる。
【００６１】
パス照合状態Ｎ３に対応する親パスｐ３はクエリＱの条件に一致するため、更新装置１００は、オートマトンＡの２回目の更新を実行する。具体的には、更新装置１００は、終了状態Ｎ２からパス照合状態Ｎ３への遷移を生成する。この遷移は、タグ内文字列「電力」から変換された記号「４」となる。また、更新装置１００は、終了状態Ｎ２から初期状態Ｎ０への遷移を、全記号Σから記号「４」を除いた「Σ＼｛４｝」に変更する。
【００６２】
そして、更新装置１００は、第２バッファｂ２の「］４」のうち「］」により、走査位置である初期状態Ｎ０から終了状態Ｎ２に走査し、第２バッファｂ２の「］４」のうち「４」により、終了状態Ｎ２からパス照合状態Ｎ３に走査する。このあと、更新装置１００は、第３バッファｂ３のパスｐ４：「／タップ／ソケット／電力」から「／」および終了タグ＜／電力＞のタグ内文字列「電力」を削除して、パスｐ３：「／タップ／ソケット」に戻す。すなわち、図２０で終了状態Ｎ２からパス照合状態Ｎ３への遷移が生成されるため、更新装置１００は、親パスがクエリＱの条件に一致するまでの走査を、終了状態Ｎ２からパス照合状態Ｎ３への遷移の生成を待たずに実行することができる。したがって、処理遅延の抑制を図ることができる。
【００６３】
図２１は、終了状態Ｎ２の更新例を示す説明図である。終了状態Ｎ２のリストＬのうち、記号「４」の領域に、パス照合状態Ｎ３の状態ＩＤ：３が格納される。これにより、走査位置が終了状態Ｎ２である場合に、「４」が出現すると、パス照合状態Ｎ３に遷移し、「４」以外の記号が出現すると、初期状態Ｎ０に遷移することになる。
【００６４】
図２２は、オートマトンＡの動作例（その１０）を示す説明図である。図２２は、図２０の状態から入力ストリームＳの終了タグ＜／ソケット＞が受信された場合の処理を示している。入力ストリームＳの終了タグ＜／ソケット＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜／ソケット＞を読み出して「］３」に変換し、第２バッファｂ２に書き込む。また、終了タグ＜／ソケット＞が受信されたため、更新装置１００は、パスＩＤ管理テーブルＴにおいて、終了タグ＜／ソケット＞のタグ内文字列「ソケット」を末尾とするパスｐ３のフラグを「１」に設定する。
【００６５】
フラグを「１」に設定した場合、更新装置１００は、現在のパスｐ３の親パスを設定する。図２２の場合、現在のパスｐ３の末尾「ソケット」を削除することにより、親パスｐ１が得られる。更新装置１００は、親パスｐ１に対応するパス照合状態がオートマトンＡに存在するか否かを判断する。この場合、親パスｐ１に対応するパス照合状態は存在しない。すなわち、親パスｐ１については２回目のオートマトンＡの更新はできない。
【００６６】
したがって、更新装置１００は、第２バッファｂ２の「］３」のうち「］」により、走査位置であるパス照合状態Ｎ３から終了状態Ｎ２に走査し、第２バッファｂ２の「］３」のうち「３」により、終了状態Ｎ２から初期状態Ｎ０に走査する。そして、更新装置１００は、第３バッファｂ３のパスｐ２：「／タップ／タップＩＤ」から「／」および終了タグ＜／タップＩＤ＞のタグ内文字列「タップＩＤ」を削除して、パスｐ１：「／タップ」に戻す。
【００６７】
図２３は、オートマトンＡの動作例（その１１）を示す説明図である。図２３は、図２２の状態から入力ストリームＳの開始タグ＜ソケット＞が受信された場合の処理を示している。入力ストリームＳの開始タグ＜ソケット＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜ソケット＞を読み出して「［３」に変換し、第２バッファｂ２に書き込む。また、開始タグ＜ソケット＞が受信されたため、更新装置１００は、第３バッファｂ３の「／タップ」の末尾に「／」およびタグ内文字列「ソケット」を書き込む。
【００６８】
そして、更新装置１００は、第３バッファｂ３内のパス「／タップ／ソケット」であるパスｐ３は、パスＩＤ管理テーブルＴに登録済みであるため、パスＩＤ管理テーブルＴへの登録は実行されない。そして、更新装置１００は、第２バッファｂ２の「［３」のうち「［」により、走査位置である初期状態Ｎ０から開始状態Ｎ１に走査し、第２バッファｂ２の「［３」のうち「３」により、開始状態Ｎ１からパス照合状態Ｎ３に走査する。
【００６９】
図２４は、オートマトンＡの動作例（その１２）を示す説明図である。図２４は、図２３の状態から入力ストリームＳの文字列「ＥＲＲ」が受信された場合の処理を示している。入力ストリームＳの文字列「ＥＲＲ」が第１バッファｂ１に書き込まれると、更新装置１００は、文字「ＥＲＲ」を読み出して変換せずに第２バッファｂ２に書き込む。また、文字列が受信された場合、パスＩＤ管理テーブルＴへの登録は実行されない。
【００７０】
そして、更新装置１００は、第２バッファｂ２の文字列「ＥＲＲ」のうち先頭文字「Ｅ」により、走査位置であるパス照合状態Ｎ３からキーワード照合途中状態Ｎ４に走査する。つぎに、更新装置１００は、文字列「ＥＲＲ」のうち２番目の文字「Ｒ」により、走査位置であるキーワード照合途中状態Ｎ４から次のキーワード照合途中状態Ｎ５に走査し、文字列「ＥＲＲ」のうち末尾文字「Ｒ」により、キーワード照合完了状態Ｎ６に走査する。キーワード照合完了状態Ｎ６に遷移したため、更新装置１００は、クエリＱのキーワード「ＥＲＲ」を出力する。
【００７１】
図２５は、オートマトンＡの動作例（その１３）を示す説明図である。図２５は、図２４の状態から入力ストリームＳの開始タグ＜電力＞が受信された場合の処理を示している。入力ストリームＳの開始タグ＜電力＞が第１バッファｂ１に書き込まれると、更新装置１００は、＜電力＞を読み出して「［４」に変換し、第２バッファｂ２に書き込む。また、開始タグ＜電力＞が受信されたため、更新装置１００は、第３バッファｂ３の「／タップ／ソケット」の末尾に「／」およびタグ内文字列「電力」を書き込む。
【００７２】
そして、更新装置１００は、第３バッファｂ３内のパス「／タップ／ソケット／電力」であるパスｐ４は、パスＩＤ管理テーブルＴに登録済みであるため、パスＩＤ管理テーブルＴへの登録は実行されない。また、走査位置がキーワード照合完了状態Ｎ６である場合、どの記号が出現しても、走査が完了しているため、遷移に失敗することになる。開始タグ記号「［」の場合、走査位置は開始状態Ｎ１に遷移し、終了タグ記号「］」の場合、走査位置は終了状態Ｎ２に遷移し、それ以外の記号の場合、走査位置はパス照合状態Ｎ３に遷移する。図２５の場合は、第２バッファｂ２の「［４」のうち「［」により、更新装置１００は、キーワード照合完了状態Ｎ６から開始状態Ｎ１に走査し、「［４」のうち記号「４」により、開始状態Ｎ１から初期状態Ｎ０に走査する。このあと、これまで説明した動作にしたがって、オートマトンＡが走査されることになる。
【００７３】
＜更新装置１００のハードウェア構成例＞
図２６は、更新装置１００のハードウェア構成例を示すブロック図である。図２６において、更新装置１００は、プロセッサ２６０１、記憶装置２６０２、入力装置２６０３、出力装置２６０４、および通信装置２６０５が、バス２６０６に接続されて構成されるコンピュータである。
【００７４】
プロセッサ２６０１は、コンピュータの全体の制御を司る。また、プロセッサ２６０１は、記憶装置２６０２に記憶されている各種プログラム（ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）や本実施の形態の更新プログラム）を実行することで、記憶装置２６０２内のデータを読み出したり、実行結果となるデータを記憶装置２６０２に書き込んだりする。
【００７５】
記憶装置２６０２は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、フラッシュメモリ、磁気ディスクドライブなどで構成され、プロセッサ２６０１のワークエリアになったり、各種プログラム（ＯＳや本実施の形態の更新プログラム）や各種データ（各プログラムの実行により得られたデータを含む）を記憶したりする。
【００７６】
入力装置２６０３は、キーボード、マウス、タッチパネルなどユーザの操作により、各種データの入力をおこなうインターフェースである。出力装置２６０４は、プロセッサ２６０１の指示により、データを出力するインターフェースである。出力装置２６０４には、ディスプレイやプリンタが挙げられる。通信装置２６０５は、ネットワーク１０１を介して外部からデータを受信したり、外部にデータを送信したりするインターフェースである。
【００７７】
（更新装置１００の機能的構成例）
図２７は、更新装置１００の機能的構成例を示すブロック図である。更新装置１００は、取得部２７０１と、生成部２７０２と、判定部２７０３と、第１の更新部２７０４と、パス判断部２７０５と、第２の更新部２７０６と、登録部２７０７と、タグ判断部２７０８と、走査部２７０９と、を有する。取得部２７０１、生成部２７０２、判定部２７０３、第１の更新部２７０４、パス判断部２７０５、第２の更新部２７０６、登録部２７０７、タグ判断部２７０８、および走査部２７０９は、具体的には、たとえば、図２６に示した記憶装置２６０２に記憶されたプログラムをプロセッサ２６０１に実行させることにより、その機能を実現する。
【００７８】
取得部２７０１は、初期オートマトンＡ０を取得する。具体的には、たとえば、初期オートマトンＡ０が未構築の場合は、取得部２７０１は、図６に示したように、初期オートマトンＡ０を構築することにより初期オートマトンＡ０を取得する。取得部２７０１は、構築された初期オートマトンＡ０を記憶装置２６０２に記憶する。また、初期オートマトンＡ０が構築済みの場合は初期オートマトンＡ０が記憶装置２６０２に記憶されているため、取得部２７０１は、記憶装置２６０２から初期オートマトンＡ０を読み込むことにより取得する。
【００７９】
生成部２７０２は、入力ストリームＳから開始タグが読み込まれると入力ストリームＳ内の階層に基づく開始タグの位置を特定するパスを生成する。生成部２７０２は、たとえば、パスが未生成の場合、最初に開始タグ＜タップ＞が読み込まれると、パスとして「／タップ」を生成する。「／」は階層を区切るための記号である。そのあと、開始タグ＜タップＩＤ＞が読み込まれると、生成部２７０２は、開始タグ＜タップＩＤ＞内のタグ内文字列「タップＩＤ」をパスの末尾に追加して、パス「／タップ」をパス「／タップ／タップＩＤ」に更新する。
【００８０】
これにより、ＸＭＬファイルが入力ストリームＳとして読み込まれる場合、更新装置１００は、ＸＭＬファイルのパススキーマを把握していなくても、どのタグがどの階層のタグであるかを特定することができる。したがって、パススキーマがない状態で入力ストリームＳを読み込んでも、オートマトンＡを更新することが可能となる。
【００８１】
また、生成部２７０２は、終了タグが読み込まれるとパスの末尾から終了タグのタグ内文字列を削除することによりパスを更新する。たとえば、パスが「／タップ／ソケット／電力」の場合に、終了タグ＜／電力＞が読み込まれた場合、生成部２７０２は、パス「／タップ／ソケット／電力」から終了タグ＜／電力＞のタグ内文字列「電力」を削除したパス「／タップ／ソケット」に更新する。終了タグが読み込まれると、パスがこれ以上、下位の階層に伸びることがないため、注目するパスを１つ上の階層のパスに戻すことになる。
【００８２】
これにより、ＸＭＬファイルが入力ストリームＳとして読み込まれる場合、更新装置１００は、ＸＭＬファイルのパススキーマを把握していなくても、どのタグがどの階層のタグであるかを特定することができる。したがって、パススキーマがない状態で入力ストリームＳを読み込んでも、オートマトンＡを更新することが可能となる。
【００８３】
判定部２７０３は、生成部２７０２によって生成されたパスがクエリＱ内のキーワードに対応する条件に一致するか否かを判定する。クエリＱには、条件と、当該条件に合致した場合に出力されるキーワードと、が記述されている。条件とは、出力対象となるキーワードが存在しうる階層のタグ内文字列を特定するパスである。条件については、ＸＰａｔｈ表記の場合、キーワードが存在しうる階層のタグ内文字列に至る経路のうち途中経路は、図１に示したように、省略して記述可能である。図１の場合、条件は、「／タップ／／ソケット」であり、「タップ」から「ソケット」に至るまでのパスとなる。本例の場合、図４に示したパスｐ３が条件「／タップ／／ソケット」にマッチするパスとなる。
【００８４】
第１の更新部２７０４は、判定部２７０３によって一致すると判定された場合、初期オートマトンＡ０から１回目の更新を実行する。これにより、図１４に示したように、初期オートマトンＡ０がオートマトンＡ１に更新される。すなわち、新たな開始タグを受信したタイミングで実施していた３種類のオートマトン更新処理「新しい状態の生成」、「開始状態Ｎ１からの遷移先の変更」および「終了状態Ｎ２からの遷移先の変更」のうち、「新しい状態の生成」、「開始状態Ｎ１からの遷移先の変更」が実行される。この時点では、「終了状態Ｎ２からの遷移先の変更」は実行されないため、当該更新処理が実行されるまでの間、オートマトンＡの走査を実行することができ、処理遅延の抑制を図ることができる。
【００８５】
パス判断部２７０５は、入力ストリームＳから終了タグが読み込まれると、条件に一致すると判定されたパスが、開始タグまでの経路を示すパスに包含される上位パスであるか否かを判断する。上位パスとは、図２０や図２２で説明した親パスである。条件に一致したパスが親パスに該当する場合、オートマトンＡにパス照合状態が存在することになる。したがって、２回目のオートマトンＡの更新が実行されることになる。条件に一致したパスが親パスに該当しない場合、まだ、２回目のオートマトンＡの更新を実行する必要がない。
【００８６】
第２の更新部２７０６は、パス判断部２７０５によって上位パスであると判断された場合、終了状態において開始タグ内の文字列が走査された場合の終了状態からパス照合状態への遷移を生成することにより、第１の更新部２７０４による更新後のオートマトンＡを更新する。すなわち、第２の更新部２７０６は、２回目のオートマトンの更新を実行する。更新装置１００は、３種類のオートマトン更新処理である「新しい状態の生成」、「開始状態Ｎ１からの遷移先の変更」および「終了状態Ｎ２からの遷移先の変更」のうち、「終了状態Ｎ２からの遷移先の更新」の処理を、対応する終了タグ受信のタイミングで実行することになる。これにより、オートマトン更新処理の負荷を分散し、処理遅延を抑制することができる。
【００８７】
登録部２７０７は、パスと当該パス内の末尾のタグ内文字列を示す終了タグが読込済みか否かを示す情報とを登録する。具体的には、たとえば、図１０、図１１、図１４、図１８に示したように、登録部２７０７は、パスＩＤ管理テーブルＴに、パスと当該パスを特定するＩＤとフラグとを登録する。末尾のタグ内文字列を示す終了タグが読込済みか否かを示す情報の一例がフラグである。これにより、更新装置１００は、終了タグが読込済みであるか否かを監視することができる。
【００８８】
タグ判断部２７０８は、登録部２７０７によって登録されたパス内の末尾の終了タグが入力ストリームＳから最初に読み込まれたか否かを判断する。最初に読み込まれたと判断された場合、今後、終了状態からパス照合状態への遷移が、オートマトンＡの走査で必要になる。したがって、このタイミングで、第２の更新部２７０６による２回目のオートマトンＡの更新が実行されることになる。
【００８９】
具体的には、タグ判断部２７０８により組み合わせ内の開始タグに対応する終了タグが入力ストリームＳから最初に読み込まれたと判断された場合、パス判断部２７０５が、条件に一致すると判定されたパスが、上位パスであるか否かを判断することになる。上位パスと判断された場合、第２の更新部２７０６による２回目のオートマトンＡの更新が実行されることになる。このように、入力ストリームＳからのタグを監視することにより、２回目のオートマトンＡの更新時期を検出することができるため、２回目のオートマトンＡの更新を自動的に開始することができる。したがって、オートマトンＡの更新の効率化を図ることができる。
【００９０】
走査部２７０９は、入力ストリームＳからタグ以外の文字が読み込まれると、オートマトンＡにしたがってオートマトンＡの現在の走査位置となる状態から文字に対応する状態に遷移させる。これにより、オートマトンＡを更新しながら、入力ストリームＳでオートマトンＡを走査することができ、処理時間の短縮化を図ることができる。また、走査部２７０９において、キーワード照合完了状態Ｎ６に遷移した場合、入力ストリームＳ内のあるタグに挟まれた文字列が、クエリＱのキーワードに一致したことになる。この場合、走査部２７０９は、一致したキーワードを、更新装置１００の出力装置や通信装置、記憶装置に出力する。
【００９１】
出力装置２６０４がディスプレイの場合は、一致したキーワードがディスプレイに表示され、プリンタの場合は印刷出力される。また、通信装置２６０５に出力する場合、通信装置２６０５から外部装置に一致したキーワードが送信されることになる。また、走査部２７０９は、一致したキーワードを記憶装置２６０２に記憶することとしてもよい。
【００９２】
＜更新装置１００の更新処理手順＞
図２８は、更新装置１００による更新処理手順例を示すフローチャートである。まず、更新装置１００は、初期オートマトンＡ０があるか否かを判断する（ステップＳ２８０１）。初期オートマトンＡ０がない場合（ステップＳ２８０１：Ｎｏ）、更新装置１００は、初期化を実行する（ステップＳ２８０２）。初期化では、更新装置１００は、記憶装置内のパスＩＤ管理テーブルＴを空にする。
【００９３】
つぎに、更新装置１００は、初期オートマトン構築処理を実行して（ステップＳ２８０３）、ステップＳ２８０５に移行する。初期オートマトン構築処理（ステップＳ２８０３）では、初期オートマトンＡ０が構築される。初期オートマトン構築処理（ステップＳ２８０３）の詳細な処理については後述する。一方、初期オートマトンＡ０がある場合（ステップＳ２８０１：Ｙｅｓ）、記憶装置から初期オートマトンＡ０を取得して（ステップＳ２８０４）、ステップＳ２８０５に移行する。ステップＳ２８０５において、更新装置１００は、初期オートマトンＡ０を走査対象のオートマトンＡに決定する（ステップＳ２８０５）。
【００９４】
このあと、更新装置１００は、入力ストリームＳを待ち受ける（ステップＳ２８０６：Ｎｏ）。入力ストリームＳが受信された場合（ステップＳ２８０６：Ｙｅｓ）、入力ストリームＳの先頭位置を現在の読込位置Ｓｃｕｒに設定する（ステップＳ２８０７）。そして、更新装置１００は、現在の読込位置Ｓｃｕｒのデータが、開始タグか文字か終了タグかを判断する（ステップＳ２８０８）。開始タグである場合（ステップＳ２８０８：開始タグ）、更新装置１００は、第１の走査処理を実行して（ステップＳ２８０９）ステップＳ２８０８に戻る。
【００９５】
文字である場合（ステップＳ２８０８：文字）、更新装置１００は、第２の走査処理を実行して（ステップＳ２８１０）ステップＳ２８０８に戻る。終了タグである場合（ステップＳ２８０８：終了タグ）、更新装置１００は、第３の走査処理を実行して（ステップＳ２８１１）ステップＳ２８０８に戻る。第１の走査処理（ステップＳ２８０９）、第２の走査処理（ステップＳ２８１０）、第３の走査処理（ステップＳ２８１１）の詳細については後述する。
【００９６】
一方、ステップＳ２８０８において、現在の読込位置Ｓｃｕｒがない場合（ステップＳ２８０８：なし）、更新装置１００は、現在の読込位置がない状態から一定時間が経過したか否かを判断する（ステップＳ２８１２）。一定時間経過していない場合（ステップＳ２８１２：Ｎｏ）、ステップＳ２８０８に戻る。これにより、入力ストリームＳのデータ受信を待ち受けることになる。一方、一定時間経過した場合（ステップＳ２８１２：Ｙｅｓ）、更新装置１００は、更新処理を終了する。
【００９７】
図２９は、図２８に示した初期オートマトン構築処理（ステップＳ２８０３）の詳細な処理手順例を示すフローチャートである。更新装置１００は、初期状態Ｎ０、開始状態Ｎ１および終了状態Ｎ２を作成し（ステップＳ２９０１）、作成した各状態の遷移先の初期値を初期状態Ｎ０に設定する（ステップＳ２９０２）。これにより、図６に示したように、初期オートマトンＡ０が構築される。構築された初期オートマトンＡ０は、記憶装置に記憶される。
【００９８】
図３０は、図２８に示した第１の走査処理（ステップＳ２８０９）の詳細な処理手順例を示すフローチャートである。更新装置１００は、読み込まれた開始タグをバイナリ変換する（ステップＳ３００１）。たとえば、図３に示したように、開始タグ＜タップ＞が読み込まれた場合、「［１」に変換する。
【００９９】
更新装置１００は、現在のパスｐに、「／ｔ」を追加する（ステップＳ３００２）。「／」は階層の境界を示す記号である。ｔはタグ内文字列である。たとえば、開始タグ＜タップ＞が読み込まれた場合、ｐは、ｐ＝／タップとなる。また、現在のパスが「／タップ／ソケット」である場合に、開始タグ＜／電力＞が読み込まれた場合、ｐは、ｐ＝／タップ／ソケット／電力となる。そして、更新装置１００は、パスＩＤ管理テーブルＴを参照して、パスＩＤ管理テーブルＴに、現在のパスｐが存在するか否かを判断する（ステップＳ３００３）。パスＩＤ管理テーブルＴに現在のパスｐがある場合（ステップＳ３００３：Ｙｅｓ）、第１の更新処理（ステップＳ３００６）が完了しているため、ステップＳ３００７に移行する。
【０１００】
一方、パスＩＤ管理テーブルＴに現在のパスｐがない場合（ステップＳ３００３：Ｎｏ）、更新装置１００は、パスＩＤ管理テーブルＴに現在のパスｐを追加して、新たなパスＩＤを割当てる（ステップＳ３００４）。たとえば、パスＩＤ管理テーブルＴが空の状態で開始タグ＜タップ＞が読み込まれた場合、パスＩＤ：１、パスｐ＝／タップを追加する。
【０１０１】
そして、更新装置１００は、現在のパスｐがクエリＱの条件にマッチするか否かを判断する（ステップＳ３００５）。マッチする場合（ステップＳ３００５：Ｙｅｓ）、更新装置１００は、第１の更新処理を実行して（ステップＳ３００６）、ステップＳ３００７に移行する。一方、マッチしない場合（ステップＳ３００５：Ｎｏ）、ステップＳ３００７に移行する。第１の更新処理（ステップＳ３００６）の詳細については後述する。
【０１０２】
つぎに、更新装置１００は、走査対象のオートマトンＡの現在の読込位置Ａｃｕｒから「［ｉ」について遷移させ、遷移先を新たな読込位置Ａｃｕｒにする（ステップＳ３００７）。ｉは、ｐに対応するパスＩＤである。そして、更新装置１００は、入力ストリームＳの現在の読込位置Ｓｃｕｒを開始タグの文字列長分加算して現在の読込位置Ｓｃｕｒを更新し（ステップＳ３００８）、第１の走査処理を終了する。
【０１０３】
図３１は、図３０に示した第１の更新処理（ステップＳ３００６）の詳細な処理手順例を示すフローチャートである。更新装置１００は、パスＩＤ：ｉに対応するパス照合状態ｖを作成する（ステップＳ３１０１）。つぎに、更新装置１００は、“［”に関する遷移先を開始状態Ｎ１に設定し、“］”に関する遷移先を終了状態Ｎ２に設定する。そして、更新装置１００は、それ以外の遷移先として、自分自身を設定する（ステップＳ３１０２）。そして、更新装置１００は、開始状態Ｎ１のパスＩＤ：ｉに関する遷移先を初期状態Ｎ０からパス照合状態ｖに変更する（ステップＳ３１０３）。また、更新装置１００は、クエリＱ内のキーワードｋに関するキーワード状態を作成し、遷移を設定する（ステップＳ３１０４）。キーワード状態とは、キーワードの各文字を遷移とした場合の遷移先状態であり、本例では、キーワード照合途中状態Ｎ４，Ｎ５およびキーワード照合完了状態Ｎ６である。
【０１０４】
更新装置１００は、パス照合状態ｖからキーワードｋの先頭文字に対応する状態への遷移を設定する（ステップＳ３１０５）。そして更新装置１００は、キーワードｋの末尾文字に対応する状態を、キーワード照合完了状態Ｎ６として設定する（ステップＳ３１０６）。これにより、図１４に示したように、初期オートマトンＡ０がオートマトンＡ１に更新される。
【０１０５】
図３２は、図２８に示した第２の走査処理（ステップＳ２８１０）の詳細な処理手順例を示すフローチャートである。更新装置１００は、オートマトンＡの現在の読込位置Ａｃｕｒから、今回読み込まれた文字（以下、文字ｃとする）について遷移させ、遷移先を新たなＡｃｕｒにする（ステップＳ３２０１）。そして、更新装置１００は、現在の読込位置Ａｃｕｒが示す状態がキーワード照合完了状態Ｎ６であるか否かを判断する（ステップＳ３２０２）。
【０１０６】
キーワード照合完了状態Ｎ６である場合（ステップＳ３２０２：Ｙｅｓ）、更新装置１００は、クエリ照合結果ＡｎｓとなるクエリＱのキーワードｋを出力して（ステップＳ３２０３）、ステップＳ３２０４に移行する。一方、キーワード照合完了状態Ｎ６でない場合（ステップＳ３２０２：Ｎｏ）、ステップＳ３２０４に移行する。ステップＳ３２０４において、更新装置１００は、入力ストリームＳの現在の読込位置ＳｃｕｒをＳｃｕｒ＝Ｓｃｕｒ＋１に更新する（ステップＳ３２０４）。すなわち、更新装置１００は、１文字分読込位置Ｓｃｕｒを進める。これにより、第２の走査処理（ステップＳ２８１０）を終了する。
【０１０７】
図３３は、図２８に示した第３の走査処理（ステップＳ２８１１）の詳細な処理手順例を示すフローチャートである。更新装置１００は、読み込まれた終了タグをバイナリ変換する（ステップＳ３３０１）。たとえば、図３に示したように、終了タグ＜／タップ＞が読み込まれた場合、「］１」に変換する。
【０１０８】
更新装置１００は、パスＩＤ管理テーブルＴ中の現在のパスｐのフラグが「０」であるか否かを判断する（ステップＳ３３０２）。「０」でない場合（ステップＳ３３０２：Ｎｏ）、第２の更新処理（ステップＳ３３０５）が完了しているため、ステップＳ３３０６に移行する。一方、「０」である場合（ステップＳ３３０２：Ｙｅｓ）、更新装置１００は、パスＩＤ管理テーブルＴの現在のパスｐのフラグを「１」に設定する（ステップＳ３３０３）。そして、更新装置１００は、現在のパスｐの親パスに対応するパス照合状態Ｎ３がオートマトンＡにあるか否かを判断する（ステップＳ３３０４）。
【０１０９】
現在のパスｐの親パスに対応するパス照合状態Ｎ３がオートマトンＡにある場合（ステップＳ３３０４：Ｙｅｓ）、親パスがクエリＱの条件に一致するときは、更新装置１００は、第２の更新処理を実行して（ステップＳ３３０５）、ステップＳ３３０６に移行する。第２の更新処理（ステップＳ３３０５）の詳細については後述する。一方、現在のパスｐの親パスに対応するパス照合状態Ｎ３がオートマトンＡにない場合（ステップＳ３３０４：Ｎｏ）、ステップＳ３３０６に移行する。現在のパスｐの親パスに対応するパス照合状態Ｎ３がオートマトンＡにあっても、親パスがクエリＱの条件に一致しないときもステップＳ３３０６に移行する。
【０１１０】
ステップＳ３３０６において、更新装置１００は、オートマトンＡの現在の読込位置Ａｃｕｒから「］ｉ」について遷移させ、遷移先を新たな読込位置Ａｃｕｒにする（ステップＳ３３０６）。ｉはｐに対応するパスＩＤである。そして、更新装置１００は、入力ストリームＳの現在の読込位置Ｓｃｕｒを終了タグの文字列長分加算して現在の読込位置Ｓｃｕｒを更新する（ステップＳ３３０７）。このあと、更新装置１００は、現在のパスｐの末尾から「／ｔ」を削除したものを新たなパスｐとし（ステップＳ３３０８）、第３の走査処理を終了する。
【０１１１】
図３４は、図３３に示した第２の更新処理（ステップＳ３３０５）の詳細な処理手順例を示すフローチャートである。更新装置１００は、現在のパスｐから末尾のタグである「／ｔ」を取り除いて得られるパスをパスｐａｒとし、パスｐａｒに対応するパスＩＤをｊとする（ステップＳ３４０１）。つぎに、更新装置１００は、パスＩＤ：ｊに対応するパス照合状態Ｎ３をｗとし（ステップＳ３４０２）、終了状態Ｎ２のｉに関する遷移先を、初期状態Ｎ０からパス照合状態ｗに変更する（ステップＳ３４０３）。これにより、図２０に示したように、オートマトンＡがオートマトンＡ１からオートマトンＡ２に更新される。
【０１１２】
このように、本実施の形態によれば、新たな開始タグを受信したタイミングで実施していた３種類のオートマトン更新処理「新しい状態の生成」、「開始状態Ｎ１からの遷移先の変更」および「終了状態Ｎ２からの遷移先の変更」のうち、「終了状態Ｎ２からの遷移先の変更」の処理を、対応する終了タグ受信のタイミングまで実施しない。これにより、オートマトン更新処理の負荷を分散し、照合処理の遅延の抑制を図ることができる。
【０１１３】
すなわち、本実施の形態では、入力ストリームＳから受信されたデータは、１文字単位（または１タグ単位）で読み込まれる。そして、文字の場合はそのままオートマトンに与えられ、タグ名の場合は対応するパスＩＤに変換してからパスＩＤとしてオートマトンに与えられて、クエリ照合が実行される。オートマトンを用いたクエリ照合においては、常に、現在のデータの読み込み位置と、オートマトン読み込み状態が保存され、オートマトンの変更が発生した後も、その位置から照合が再開される。
【０１１４】
このように、受信データを１文字（または１タグ）ずつ読みながら逐次的に照合が実行されるため、新たなパスが存在しない限りにおいては、遅延なく照合結果が出力される。また、新たなパスが存在した場合も、その直前の位置までは照合が完了している。したがって、クエリチェックとオートマトン更新が完了すると、即座にその位置から照合を開始でき、遅延を最小限に抑制することができる。さらに、１文字（または１タグ）ずつの処理であるため、入力ストリームＳ全体を保管する必要がなく、計算領域の抑制を図ることができる。
【０１１５】
また、パスの末尾に対しタグ内文字列の追加または削除をおこなうことにより、入力ストリームＳとして読み込まれる場合、更新装置１００は、パススキーマを把握していなくても、どのタグがどの階層のタグであるかを特定することができる。したがって、パススキーマがない状態で入力ストリームＳを読み込んでも、オートマトンＡを更新することができる。
【０１１６】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１１７】
（付記１）タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得し、
前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成し、
生成された前記パスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定し、
一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する、
処理をコンピュータに実行させることを特徴とする更新プログラム。
【０１１８】
（付記２）前記生成する処理は、
前記開始タグが読み込まれると前記パスの末尾に前記開始タグのタグ内文字列を追加することにより前記パスを更新することを特徴とする付記１に記載の更新プログラム。
【０１１９】
（付記３）前記入力ストリームから終了タグが読み込まれると、前記条件に一致すると判定されたパスが、前記開始タグまでの経路を示すパスに包含される上位パスであるか否かを判断し、
前記上位パスであると判断された場合、前記終了状態において前記開始タグ内の文字列が走査された場合の前記終了状態から前記パス照合状態への遷移を生成することにより、更新後のオートマトンを更新する、
処理をコンピュータに実行させることを特徴とする付記１または２に記載の更新プログラム。
【０１２０】
（付記４）前記生成する処理は、
前記終了タグが読み込まれると前記パスの末尾から前記終了タグのタグ内文字列を削除することにより前記パスを更新することを特徴とする付記３に記載の更新プログラム。
【０１２１】
（付記５）前記パスと当該パス内の末尾のタグ内文字列を示す終了タグが読込済みか否かを示す情報とを登録し、
登録された前記パス内の末尾の終了タグが前記入力ストリームから最初に読み込まれたか否かを判断する、
処理を前記コンピュータに実行させ、
前記上位パスであるか否かを判断する処理は、
前記末尾の終了タグが前記入力ストリームから最初に読み込まれたと判断された場合、前記条件に一致すると判定されたパスが、前記開始タグまでの経路を示すパスに包含される上位パスであるか否かを判断することを特徴とする付記３または４に記載の更新プログラム。
【０１２２】
（付記６）前記入力ストリームから前記タグ以外の文字が読み込まれると、前記オートマトンにしたがって前記オートマトンの現在の走査位置となる状態から前記文字に対応する状態に遷移させる処理を前記コンピュータに実行させることを特徴とする付記１〜５のいずれか一つに記載の更新プログラム。
【０１２３】
（付記７）タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得し、
前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成し、
生成された前記パスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定し、
一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する、
処理をコンピュータに実行させる更新プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２４】
（付記８）前記生成する処理は、
前記開始タグが読み込まれると前記パスの末尾に前記開始タグのタグ内文字列を追加することにより前記パスを更新する付記７に記載の更新プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２５】
（付記９）前記入力ストリームから終了タグが読み込まれると、前記条件に一致すると判定されたパスが、前記開始タグまでの経路を示すパスに包含される上位パスであるか否かを判断し、
前記上位パスであると判断された場合、前記終了状態において前記開始タグ内の文字列が走査された場合の前記終了状態から前記パス照合状態への遷移を生成することにより、更新後のオートマトンを更新する、
処理をコンピュータに実行させる付記７または８に記載の更新プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２６】
（付記１０）前記生成する処理は、
前記終了タグが読み込まれると前記パスの末尾から前記終了タグのタグ内文字列を削除することにより前記パスを更新する付記９に記載の更新プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２７】
（付記１１）前記パスと当該パス内の末尾のタグ内文字列を示す終了タグが読込済みか否かを示す情報とを登録し、
登録された前記パス内の末尾の終了タグが前記入力ストリームから最初に読み込まれたか否かを判断する、
処理を前記コンピュータに実行させ、
前記上位パスであるか否かを判断する処理は、
前記末尾の終了タグが前記入力ストリームから最初に読み込まれたと判断された場合、前記条件に一致すると判定されたパスが、前記開始タグまでの経路を示すパスに包含される上位パスであるか否かを判断することを特徴とする付記９または１０に記載の更新プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２８】
（付記１２）前記入力ストリームから前記タグ以外の文字が読み込まれると、前記オートマトンにしたがって前記オートマトンの現在の走査位置となる状態から前記文字に対応する状態に遷移させる処理を前記コンピュータに実行させる付記７〜１１のいずれか一つに記載の更新プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２９】
（付記１３）コンピュータが、
タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得し、
前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成し、
生成された前記パスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定し、
一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する、
処理を実行することを特徴とする更新方法。
【０１３０】
（付記１４）タグにより階層化された入力ストリーム内のデータとクエリ内のキーワードとの照合をおこなうオートマトンであって、初期状態、開始タグ記号を示す開始状態、終了タグ記号を示す終了状態、前記初期状態と前記開始状態との間の遷移、前記初期状態と前記終了状態との間の遷移、および前記初期状態から前記初期状態への遷移が規定されたオートマトンを取得する取得部と、
前記入力ストリームから開始タグが読み込まれると前記入力ストリーム内の階層に基づく前記開始タグの位置を特定するパスを生成する生成部と、
前記生成部によって生成されたパスが前記クエリ内の前記キーワードに対応する条件に一致するか否かを判定する判定部と、
前記判定部によって一致すると判定された場合、前記パスが前記条件に一致したことを示すパス照合状態と、前記開始状態において前記開始タグ内の文字列が走査された場合の前記開始状態から前記パス照合状態への遷移と、前記パス照合状態において前記キーワードが走査された場合の前記パス照合状態からの遷移と、当該遷移による遷移先状態と、前記パス照合状態において前記開始タグ記号が走査された場合の前記パス照合状態から前記開始状態への遷移と、前記パス照合状態において前記終了タグ記号が走査された場合の前記パス照合状態から前記終了状態への遷移と、を生成することにより、前記オートマトンを更新する更新部と、
を有することを特徴とする更新装置。
【符号の説明】
【０１３１】
１００  更新装置
２７０１  取得部
２７０２  生成部
２７０３  判定部
２７０４  第１の更新部
２７０５  パス判断部
２７０６  第２の更新部
２７０７  登録部
２７０８  タグ判断部
２７０９  走査部
Ａ  オートマトン
Ｔ  パスＩＤ管理テーブル
【図１】
0005958088.tif 000002
【図２】
0005958088.tif 000003
【図３】
0005958088.tif 000004
【図４】
0005958088.tif 000005
【図５】
0005958088.tif 000006
【図６】
0005958088.tif 000007
【図７】
0005958088.tif 000008
【図８】
0005958088.tif 000009
【図９】
0005958088.tif 000010
【図１０】
0005958088.tif 000011
【図１１】
0005958088.tif 000012
【図１２】
0005958088.tif 000013
【図１３】
0005958088.tif 000014
【図１４】
0005958088.tif 000015
【図１５】
0005958088.tif 000016
【図１６】
0005958088.tif 000017
【図１７】
0005958088.tif 000018
【図１８】
0005958088.tif 000019
【図１９】
0005958088.tif 000020
【図２０】
0005958088.tif 000021
【図２１】
0005958088.tif 000022
【図２２】
0005958088.tif 000023
【図２３】
0005958088.tif 000024
【図２４】
0005958088.tif 000025
【図２５】
0005958088.tif 000026
【図２６】
0005958088.tif 000027
【図２７】
0005958088.tif 000028
【図２８】
0005958088.tif 000029
【図２９】
0005958088.tif 000030
【図３０】
0005958088.tif 000031
【図３１】
0005958088.tif 000032
【図３２】
0005958088.tif 000033
【図３３】
0005958088.tif 000034
【図３４】
0005958088.tif 000035