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