(57)【特許請求の範囲】
【請求項１】
逐次入力されるデータを処理するストリームデータ処理装置であって，
データの変化に対応した処理を実行する規則として，状態情報とパターン情報とを記憶する情報記憶部と，
データの状態を変数条件で記述する状態情報と，前記状態の並びであるパターンと該パターンの場合に実行する処理との対応関係を示すパターン情報とを取得して前記情報記憶部に格納する情報取得部と，
前記パターン情報のパターンに含まれる状態について，該状態を記述する変数条件を排他的な変数条件に分割し，該分割した各変数条件で記述される状態を細分状態とする状態細分化部と，
前記細分状態が，前記パターンに示された状態を記述する変数条件を満たすかを検査する細分状態検査部と，
前記パターンに示された状態を記述する変数条件を満たす細分状態を用いて，該パターンに示された状態を置き換え，前記パターンの状態の並びに対応する細分状態の並びを示す細分パターンを生成する細分パターン生成部とを，備える
ことを特徴とするストリームデータ処理装置。
【請求項２】
前記細分パターン情報を前記パターン情報と対応付けて記憶する細分パターン情報記憶部と，
逐次入力されるデータを取得するデータ取得部と，
前記データの照合処理で使用されるパターン情報に対応する細分パターン情報を取得して，前記取得した細分パターン情報にもとづくＡＣマシンを生成する照合器生成部と，
前記取得したデータを，逐次，対応する細分状態に変換して前記ＡＣマシンに代入し，照合結果として該ＡＣマシンの処理結果を取得する細分パターン照合部と，
前記照合結果にもとづいて，前記細分パターン情報に対応するパターン情報に記述された処理の実行処理を出力する処理実行支持部とを，備える
ことを特徴とする請求項１に記載のストリームデータ処理装置。
【請求項３】
逐次入力されるデータを処理するストリームデータ処理方法であって，
コンピュータが，
データの変化に対応した処理を実行する規則として，状態情報とパターン情報とを記憶する情報記憶部を備えて，
データの状態を変数条件で記述する状態情報と，前記状態の並びであるパターンと該パターンの場合に実行する処理との対応関係を示すパターン情報とを取得して前記情報記憶部に格納する処理過程と，
前記パターン情報のパターンに含まれる状態について，該状態を記述する変数条件を排他的な変数条件に分割し，該分割した各変数条件で記述される状態を細分状態とする処理過程と，
前記細分状態が，前記パターンに示された状態を記述する変数条件を満たすかを検査する処理過程と，
前記パターンに示された状態を記述する変数条件を満たす細分状態を用いて，該パターンに示された状態を置き換え，前記パターンの状態の並びに対応する細分状態の並びを示す細分パターンを生成する処理過程とを，実行する
ことを特徴とするストリームデータ処理方法。
【請求項４】
コンピュータに，逐次入力されるデータを処理するストリームデータ処理を実行させるためのストリームデータ処理プログラムであって，
データの変化に対応した処理を実行する規則として，状態情報とパターン情報とを記憶する情報記憶部を備える前記コンピュータに，
データの状態を変数条件で記述する状態情報と，前記状態の並びであるパターンと該パターンの場合に実行する処理との対応関係を示すパターン情報とを取得して前記情報記憶部に格納する処理と，
前記パターン情報のパターンに含まれる状態について，該状態を記述する変数条件を排他的な変数条件に分割し，該分割した各変数条件で記述される状態を細分状態とする処理と，
前記細分状態が，前記パターンに示された状態を記述する変数条件を満たすかを検査する処理と，
前記パターンに示された状態を記述する変数条件を満たす細分状態を用いて，該パターンに示された状態を置き換え，前記パターンの状態の並びに対応する細分状態の並びを示す細分パターンを生成する処理とを，実行させる
ためのストリームデータ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，逐次入力されてくる複数データによる状態列にもとづいて所定の処理を実行するストリームデータ処理技術に関する。
【背景技術】
【０００２】
ストリームデータ処理では，コンピュータに入力されてくるデータに応じて，変数の値が変化して次々に書き換えられる。そして，変数の値の領域の変化が，所定の規則に合致する場合に，対応する所定の処理を実行する。
【０００３】
ストリームデータ処理の一例として，感染症の伝播に応じて学校閉鎖を決定する処理に適用した場合を説明する。
【０００４】
図１４は，ある地域に感染症が発生した場合に，感染症の伝播を予防するために，病院での患者数と所在する複数の学校での欠席者数に応じて学校を閉鎖する処理例である。図１４に示すように，病院Ｈを中心に，３つの学校Ｓｃ１〜Ｓｃ３があり，学校Ｓｃ２は，学校Ｓｃ１に近接して所在し，学校Ｓｃ３は，より離れて所在していると仮定する。
【０００５】
ここで，学校Ｓｃ１の欠席者が少ない段階で，予防的に学校を閉鎖したいとする。すなわち，学校Ｓｃ１の学校閉鎖を決定する条件（規則）として，「遠地の学校Ｓｃ３の欠席者に続き，近隣の学校Ｓｃ２の欠席者が増加し，しかも，病院の陽性患者数が多数であること」を定めて，この規則が満たされた場合に，処理「学校閉鎖」を行うものとする。
【０００６】
したがって，入力される変数は，病院Ｈの陽性患者数Ｘ０，学校Ｓｃ１の欠席者数Ｘ１，学校Ｓｃ２の欠席者数Ｘ２，学校Ｓｃ３の欠席者数Ｘ３であり，入力されてくる変数の値の領域の変化によって，上記の規則が満たされるか否かが判断される。
【０００７】
図１５は，図１４に示す処理例を，コンピュータを用いて実行する場合の各処理を示す図である。
【０００８】
上記の「学校の閉鎖」を実行するアプリケーション・プログラム（ストリームデータ処理）を実行するために，以下の手順により，上記の「遠地の学校Ｓｃ３の欠席者に続き，近隣の学校Ｓｃ２の欠席者が増加し，しかも，病院の陽性患者数が多数であること」という規則を，状態の変化として記述する。
【０００９】
まず，アプリケーション・プログラムの開発段階として，手順１〜２が実行される。
【００１０】
手順１：状態−変数条件定義
まず，変数｛Ｘｎ｝に関する条件式を用いて，ある時点における系の状態を複数定義する。状態とは，変数｛Ｘｎ｝で張られる空間に占める領域であり，変数条件で定められる。｛Ｃｎ｝は，定数である。以下は，状態の定義例である。
【００１１】
状態Ｓａ：Ｘ１＜Ｃ１，Ｘ３≧Ｃ３
（学校Ｓｃ１では欠席数が小（少ない），遠地の学校Ｓｃ３の欠席数が大（多い））
状態Ｓｂ：Ｘ０≧Ｃ０，Ｘ１＜Ｃ１，Ｘ２≧Ｃ２
（学校Ｓｃ１では欠席数が小，近隣の学校Ｓｃ２の欠席数が大，病院の患者数が大）
手順２：パターン定義
次に，上記手順１で定めた状態に関するパターンを定義する。パターンとは，状態の並びであり，状態がその順序で出現することを意味する。以下は，パターンの定義例である。
【００１２】
パターン：ＳａＳｂ→「学校Ｓｃ１を閉鎖」
（状態Ｓａに続いて状態Ｓｂとなったとき，学校Ｓｃ１を閉鎖する）。
【００１３】
上記の状態およびパターンが保持されて，アプリケーション・プログラムの実行段階として，手順３〜５が実行される。
【００１４】
手順３：変数−状態変換
変数Ｘ０〜Ｘ３として逐次入力されてくる値により，変数領域の値が書き換えられると，上記手順１で定められた状態の定義にもとづいて，変数領域に応じた状態を出力する。
【００１５】
手順４：パターン照合
上記手順３で出力された状態列を，上記手順２で定められたパターンと照合する。
【００１６】
手順５：処理実行
上記手順４で，状態列がパターンとマッチした場合に，そのマッチしたパターンに対応した処理を実行する。
【００１７】
また，ユーザによって定義される状態によっては，入力された変数領域が，複数の状態を同時に満たすような場合がある。ユーザは規則を適切に表すための状態を定義するが，状態同士の範囲を厳密に検証することは煩雑となるからである。例えば，上記の状態Ｓａ，Ｓｂの定義の場合に，入力された変数の値が，（Ｘ０，Ｘ１，Ｘ２，Ｘ３）＝（ｚ０，ｚ１，ｚ２，ｚ３）であるとき，条件が（ｚ０≧Ｃ０）＆（ｚ１＜Ｃ１）＆（ｚ２≧Ｃ２）＆（ｚ３≧Ｃ３）であるならば，状態Ｓａ，Ｓｂの定義条件を同時に満たすことになる。このような状態を「Ｓａ∧（合接）Ｓｂ」と表す。
【００１８】
上記の「パターン照合」の処理として，いくつかの手法が知られている。
【００１９】
（１）第１の照合手法
「Ｓａ∧Ｓｂ」のような状態を扱うことができる照合手法として，状態列の履歴を保持してパターン照合する手法が知られている。
【００２０】
パターンＰの長さと同一サイズのバッファを用意し，直近の状態の履歴を保持する。そして，状態が変わるたびに，直近と現在の状態の組がパターンとマッチするかを調べる。
【００２１】
入力される値の並びに応じた状態Ｓの変化（遷移）を状態列Ｓｔとして表し，状態列Ｓｔ＝ＳａＳｃＳｂ（Ｓａ∧Ｓｂ）Ｓｂであるとする。
【００２２】
図１６（Ａ）に示すように，パターン長と同じ長さの状態数分の行を持つバッファを用意する。バッファ内の「１つ前」は，直近に入力された変数，「現在」は今回入力された変数を示し，その領域が状態に該当する場合に“１”が，その領域が状態に該当しない場合に“０”が，それぞれ設定される。
【００２３】
図１６（Ａ）の例は，状態列Ｓｔ＝ＳａＳｃＳｂ（Ｓａ∧（合接）Ｓｂ）Ｓｂのうち，「ＳａＳｃ」まで読み込んだ時点のバッファの状態である。すなわち，現在入力された変数に対する状態Ｓｃの直近の状態はＳａであるから，バッファの「１つ前」ではＳａ＝１，Ｓｂ＝０が，「現在」のＳａ＝０，Ｓｂ＝０が，それぞれ設定される。そのため，パターン「ＳａＳｂ」に該当しないことが分かる。
【００２４】
図１６（Ｂ）の例は，次の入力により，変数の値による状態がＳｂとなった場合を示す。図１６（Ｂ）の例で，直近と現在の状態は，ＳｃＳｂとなるので，バッファの「１つ前」では，Ｓａに０が，Ｓｂに０が，「現在」では，Ｓａに０が，Ｓｂに１が設定される。
【００２５】
図１６（Ｃ）の例は，さらに，同様に，次の入力により，変数の値による状態がＳａ∧Ｓｂとなった場合を示す。図１６（Ｃ）の例で，直近と現在の状態は，Ｓｂ（Ｓａ∧Ｓｂ）となるので，バッファの「１つ前」では，Ｓａに０が，Ｓｂに１が，「現在」では，Ｓａに１が，Ｓｂに１が，設定される。
【００２６】
図１６（Ｄ）の例は，さらに，次の入力により，変数の値による状態がＳｂとなった場合を示す。図１６（Ｄ）の例で，直近と現在の状態は，（Ｓａ∧Ｓｂ）Ｓｂとなるので，バッファの「１つ前」では，Ｓａに１が，Ｓｂに１が，「現在」では，Ｓａに０が，Ｓｂに１が設定される。これにより，Ｓａが１，Ｓｂが１となり，パターンを満たす状態遷移を照合できたことになる。
【００２７】
（２）第２の照合手法
複数のパターンに対する照合を同時に扱うことができる手法として，ＡＣ（Ａｈｏ−Ｃｏｒａｓｉｃｋ）マシンを利用した手法がある。
【００２８】
パターンを表す複数の文字列を入力して，図１７に示すような，オートマトンを作成しておく。オートマトンは，ノード（節点）と，状態を示すラベル付きアーク（枝）で構成され，値が入力される初期ノードが１つと，複数の終了ノードを持つ。アークは，遷移先を表す。
【００２９】
図１７に示すオートマトン例は，状態列のパターンＳａＳｂ，ＳｃＳａを同時に照合するものである。初期ノードおよび中間ノードを数字付きの丸形で，結果を示す終了ノードを数字付きの矩形で，アークは矢印付きの弧で表す。
【００３０】
図１７のオートマトンでは，初期ノード０から開始され，状態の入力を受けるたびに，現在のノードから，該当するアークを辿って次のノードに遷移する。終了ノードのノード３，４に遷移したとき，ノードに対応するパターン，例えばノード３に到達した場合にはパターンＳａＳｂとマッチしたことを意味し，ノード４に到達した場合にはパターンＳｃＳａとマッチしたことを意味する。
【００３１】
さらに，状態遷移の規則を生成する場合に，規則中に表れるある状態の遷移が他の状態の遷移と同一である場合に，同一となった２つの状態について後の状態を削除して先の状態に変更することで，状態遷移の規則を圧縮し，遷移規則表のサイズを小さくする手法がある。
【先行技術文献】
【特許文献】
【００３２】
【特許文献１】特開平５−２３３３１２号公報
【発明の概要】
【発明が解決しようとする課題】
【００３３】
しかし，上述の第１の照合手法の場合には，文字列やパターンの長さに応じて計算量が多くなるという問題があり効率が悪い。計算効率を高めるために，文字列Ｔの各文字を１回のみ比較対象とし，一旦照合した部分の次の文字列からパターンＰと比較する処理を行うと，照合漏れを生じるおそれがある。例えば，図１６（Ｂ）に示すように，文字列Ｔの先頭から３文字分の部分文字列の先頭（ｂ）がパターンＰの先頭（ａ）と一致しなければ，１文字分ずらした部分文字列ａａａとパターンＰとを照合する。ここで，部分文字列ａａａがパターンＰに一致しない場合に，処理効率のために，文字列Ｔの未照合の部分ｂｂへ処理位置を進めてパターンＰと照合すると，文字列Ｔの「ａａｂ」が照合漏れになってしまう。
【００３４】
また，ユーザによって定義される状態によっては，入力された変数領域が，複数の状態を同時に満たすような場合があるが，このような状態（Ｓａ∧Ｓｂ）を含むパターン照合を扱うことができないという問題があった。
【００３５】
また，上述の第１の照合手法では，状態がＳａ∧Ｓｂとなった場合を含む状態列を照合できる。しかし，状態が変化するたびに，「パターン数×パターン長」の回数のフラグ比較が必要となり，計算コストが高くなるという問題があった。特に，パターンが複数になると，この照合手法では処理コストが非常に高くなるという問題があった。
【００３６】
また，上述の第２の照合手法は，複数のパターンに対する照合を同時に扱うことができるが，状態が変わるたびに１回のノード遷移の処理のみを行うだけであり，状態「Ｓａ∧Ｓｂ」を含むパターン照合を扱うことができないという問題があった。
【００３７】
ストリームデータの処理において，状態を定義する条件が複雑であったり，状態の数が多くなったりすると，ある状態を示す条件として入力された条件式が，他の状態をも示すような場合が生じる。ユーザが，全ての条件式を完全に排他的なものであるように，すなわち，変数領域の値の組によっては，複数の変数条件が同時には真とはならないように，設定することは，非常に困難である。
【００３８】
本発明は，同時に複数の状態を占めるような状態（Ｓａ∧Ｓｂ）を含むパターンのパターン照合処理を，処理コストを増大させることなく実行できるストリームデータ処理技術を提供することである。
【課題を解決するための手段】
【００３９】
本願において発明の一態様として開示されるストリームデータ処理装置は，逐次入力されるデータを処理する装置であって，１）データの変化に対応した処理を実行する規則として，状態情報とパターン情報とを記憶する情報記憶部と，２）データの状態を変数条件で記述する状態情報と，前記状態の並びであるパターンと該パターンの場合に実行する処理との対応関係を示すパターン情報とを取得して前記情報記憶部に格納する情報取得部と，３）前記パターン情報のパターンに含まれる状態について，該状態を記述する変数条件を排他的な変数条件に分割し，該分割した各変数条件で記述される状態を細分状態とする状態細分化部と，４）前記細分状態が，前記パターンに示された状態を記述する変数条件を満たすかを検査する細分状態検査部と，５）前記パターンに示された状態を記述する変数条件を満たす細分状態を用いて，該パターンに示された状態を置き換え，前記パターンの状態の並びに対応する細分状態の並びを示す細分パターンを生成する細分パターン生成部とを有する。
【００４０】
また，本発明の別の態様として開示されるストリームデータ処理方法は，データの変化に対応した処理を実行する規則として，状態情報とパターン情報とを記憶する情報記憶部を備えたコンピュータが，１）データの状態を変数条件で記述する状態情報と，前記状態の並びであるパターンと該パターンの場合に実行する処理との対応関係を示すパターン情報とを取得して前記情報記憶部に格納する処理過程と，２）前記パターン情報のパターンに含まれる状態について，該状態を記述する変数条件を排他的な変数条件に分割し，該分割した各変数条件で記述される状態を細分状態とする処理過程と，３）前記細分状態が，前記パターンに示された状態を記述する変数条件を満たすかを検査する処理過程と，４）前記パターンに示された状態を記述する変数条件を満たす細分状態を用いて，該パターンに示された状態を置き換え，前記パターンの状態の並びに対応する細分状態の並びを示す細分パターンを生成する処理過程とを実行するものである。
【００４１】
さらに，本発明の別の態様として開示されるストリームデータ処理プログラムは，コンピュータに，上記の処理方法により実現される処理を実行させるためのものである。
【発明の効果】
【００４２】
上記開示したストリームデータ処理装置によれば，ＡＣマシンによる判定処理を可能にするパターン情報を提供することができる。よって，ストリームデータの変数の領域が同時に複数の状態を占めるような状態を含む場合のストリームデータ処理を小さなコストで実行する判定処理を実現することができる。
【図面の簡単な説明】
【００４３】
【図１】本発明の一態様として開示するストリームデータ処理装置の構成例を示す図である。
【図２】本発明の実施の一形態において，ストリームデータ処理装置を，２つの装置として実施する場合の構成例を示す図（その１）である。
【図３】本発明の実施の一形態において，ストリームデータ処理装置を，２つの装置として実施する場合の構成例を示す図（その２）である。
【図４】本発明の実施の一形態における状態情報およびパターン情報の構成例を示す図である。
【図５】状態を定義する変数条件の変数の領域と細分される領域との対応関係を模式的に示す図である。
【図６】本発明の実施の一形態における細分パターン情報の構成例を示す図である。
【図７】本発明の実施の一形態におけるストリームデータ処理装置の処理フロー例を示す図である。
【図８】パターン展開処理（ステップＳ５）のより詳細な処理フロー例を示す図である。
【図９】状態Ｓの分割処理（ステップＳ５１，Ｓ５６）のより詳細な処理フロー例を示す図である。
【図１０】本発明の実施の一形態における細分状態における変数条件の例を示す図である。
【図１１】細分状態の検査処理（ステップＳ５１３）の処理フロー例を示す図である。
【図１２】アプリケーション実行段階における，ストリームデータの判定処理の処理フロー例を示す図である。
【図１３】細分状態への変換処理（ステップＳ１３）のより詳細な処理フロー例を示す図である。
【図１４】ストリームデータ処理を適用するアプリケーション処理の一例を説明するための図である。
【図１５】図１４に示す処理例を，コンピュータを用いて実行する場合の各処理を示す図である。
【図１６】従来手法のうち第１の照合手法を説明するための図である。
【図１７】従来手法のうち第２の照合手法を説明するための図である。
【発明を実施するための形態】
【００４４】
図１は，本発明の一態様として開示するストリームデータ処理装置１の構成例を示す図である。
【００４５】
ストリームデータ処理装置１は，逐次入力されるデータ（ストリームデータ）２１を取得して，取得したストリームデータ２１の変化に応じて所定の処理を行う装置である。ストリームデータ処理装置１は，ＣＰＵおよびメモリ等を有するハードウェアとソフトウェアプログラムとを備えるコンピュータ・システム，または専用ハードウェアによって実現される。
【００４６】
ストリームデータ処理装置１は，情報取得部１０，情報記憶部１１，状態細分化部１２，細分状態検査部１３，細分パターン生成部１４，細分パターン情報記憶部１５，照合器生成部１６，パターン照合部１７，および処理実行指示部１８を有する。
【００４７】
情報取得部１０は，ストリームデータ２１の変化に対応した処理を実行する規則としてユーザによって用意された状態情報２２およびパターン情報２３の入力を受け付けて，取得する。
【００４８】
状態情報２２は，後述するパターン情報に設定されているストリームデータ２１の状態を，所定の変数の値がとる領域を示す変数条件で記述する定義情報である。
【００４９】
パターン情報２３は，データの状態の並びであるパターンと，そのパターンの場合に実行する処理との対応関係を記述する定義情報である。
【００５０】
情報記憶部１１は，情報取得部１０が取得した状態情報２２とパターン情報２３とを記憶する。
【００５１】
状態細分化部１２は，パターン情報２３のパターンについて，状態情報２２の状態を記述する変数条件をもとに，その状態に対応する変数の値がとる領域を，排他的な変数条件の変数の値がとる領域に分割し，分割した領域を細分状態とする。
【００５２】
細分状態検査部１３は，状態細分化部１２によって生成された各細分状態が，状態を記述する変数条件を満たすかを検査する。
【００５３】
細分パターン生成部１４は，細分状態検査部１３の結果をもとに，状態を記述する変数条件を満たす細分状態を用いて状態を置き換え，状態の並びに対応する細分状態の並びを示す細分パターンを生成する。
【００５４】
細分パターン情報記憶部１５は，細分パターン情報（細分パターン）２４を記憶する。
【００５５】
照合器生成部１６は，細分パターン情報２４をもとにＡＣマシンを生成する。
【００５６】
パターン照合部１７は，入力されたストリームデータ２１を取得し，ストリームデータ２１の変数に対応する状態をＡＣマシンに代入し，ＡＣマシンが出力する照合結果を取得する。
【００５７】
処理実行指示部１８は，照合結果にもとづいて，細分パターン情報２４に対応するパターン情報２３に記述された所定の処理の実行指示（指示）２５を出力する。
【００５８】
ストリームデータ処理装置１の情報取得部１０，情報記憶部１１，状態細分化部１２，細分状態検査部１３，細分パターン生成部１４，および細分パターン情報記憶部１５は，ストリームデータ２１を処理するアプリケーション・プログラムの開発段階で使用される処理部である。
【００５９】
ストリームデータ処理装置１の照合器生成部１６，パターン照合部１７，および処理実行指示部１８は，上記のアプリケーション・プログラムの実行段階で，ストリームデータの規則判定処理において使用される処理部である。
【００６０】
したがって，ストリームデータ処理装置１は，アプリケーション・プログラムの開発段階で使用される処理部と実行段階で使用される処理部とを，独立する別個の装置として実施してもよい。
【００６１】
図２および図３は，ストリームデータ処理装置１を，２つの装置として実施する場合の構成例を示す図である。
【００６２】
図２に示すストリームデータ処理装置１ａは，アプリケーション・プログラムの開発段階で使用される装置であって，状態情報２２とパターン情報２３とを取得して，細分パターン情報２４を生成し，出力する。
【００６３】
ストリームデータ処理装置１ａは，情報取得部１０，情報記憶部１１，状態細分化部１２，細分状態検査部１３，細分パターン生成部１４，および出力部１９を有する。
【００６４】
ストリームデータ処理装置１ａの情報取得部１０，情報記憶部１１，状態細分化部１２，細分状態検査部１３，および細分パターン生成部１４は，図１に示すストリームデータ処理装置１の同番号の処理部に相当する。
【００６５】
出力部１９は，細分パターン生成部１４で生成された細分パターン情報２４を出力する。
【００６６】
図３に示すストリームデータ処理装置１ｂは，アプリケーション・プログラムの実行段階で使用される装置であって，ストリームデータ処理装置１ａで生成された細分パターン情報２４を入力して，ストリームデータ２１が，処理実行の規則を満たすかを判定し，規則を満たす場合に，処理実行の指示２５を出力する。
【００６７】
ストリームデータ処理装置１ｂは，細分パターン情報記憶部１５，照合器生成部１６，パターン照合部１７，処理実行指示部１８，および細分パターン取得部１１０を有する。
【００６８】
ストリームデータ処理装置１ｂの細分パターン情報記憶部１５，照合器生成部１６，パターン照合部１７，処理実行指示部１８は，図１に示すストリームデータ処理装置１の同番号の処理部に相当する。
【００６９】
細分パターン取得部１１０は，パターン情報２３に対応する細分パターン情報２４の入力を受け付け，細分パターン情報記憶部１５に格納する。
【００７０】
細分パターン取得部１１０は，複数のパターン情報２３に対応する細分パターン情報２４の入力を受け付ける場合に，ストリームデータ２１の判定に用いられるパターン情報２３を示す識別情報２６を受け付けて，識別情報２６が示すパターン情報２３に対応する細分パターン情報２４を特定して照合器生成部１６へ渡す。
【００７１】
以下に，図１に示すストリームデータ処理装置１の処理動作を，具体例を用いて説明する。
【００７２】
具体例において，ストリームデータ処理装置１は，図１４で説明した状況において，「学校閉鎖」や「学校閉鎖の解除」の決定を，条件（規則）にもとづいて判定するものとする。
【００７３】
ストリームデータ処理装置１に入力されるストリームデータ２１は，病院Ｈの陽性患者数Ｘ０，学校Ｓｃ１の欠席者数Ｘ１，学校Ｓｃ２の欠席者数Ｘ２，学校Ｓｃ３の欠席者数Ｘ３の各変数の値である。
【００７４】
また，状態とパターンについては，以下のように設定されるとする。
【００７５】
状態Ｓａ：Ｘ１＜Ｃ１，Ｘ３≧Ｃ３
状態Ｓｂ：Ｘ０≧Ｃ０，Ｘ１＜Ｃ１，Ｘ２≧Ｃ２
状態Ｓｃ：Ｘ１≧Ｃ１，Ｘ３＜Ｃ３
パターン：ＳａＳｂ→処理Ｄ「学校Ｓｃ１を閉鎖」
パターン：ＳｃＳａ→処理Ｅ「学校Ｓｃ１の閉鎖を解除」
ストリームデータ処理装置１の状態取得部１０は，上記の状態およびパターンをそれぞれ定義する状態情報２２，パターン情報２３を取得して，情報記憶部１１に格納する。
【００７６】
図４（Ａ）は，状態情報２２の構成例および図４（Ｂ）はパターン情報２３の構成例を示す図である。
【００７７】
図４（Ａ）に示すように，状態情報２２は，状態と，対応する変数条件（変数の条件式）とが設定された状態−変数条件対応表として実施される。また，図４（Ｂ）に示すように，パターン情報２３は，パターンと，対応する処理とが設定されたパターン−処理対応表として実施される。
【００７８】
次に，ストリームデータ処理装置１の状態細分化部１２は，パターン情報２３の各パターンについて，そのパターンに含まれる各状態を記述する変数条件（条件式）を，排他的となるように分割し，分割した変数条件に対応する状態を細分状態とする。
【００７９】
図５は，状態を定義する変数条件の変数の領域と細分領域との対応関係を模式的に示す図である。図５は，説明を簡便にするため，状態に対応する変数の領域を二次元の領域として表している。
【００８０】
状態細分化部１２は， 状態Ｓａ，Ｓｂ，Ｓｃそれぞれを定義する変数条件（条件式）の変数が示す領域を特定する。
【００８１】
状態細分化部１２は，状態Ｓａ，Ｓｂ，Ｓｃの各々に対応する領域を示す条件式から，排他的な領域を示す条件式を生成する。この変数が排他的な領域を示す条件式によって，状態Ｓａ，Ｓｂに対応する領域は細分化される。細分化された各領域に対応する状態を細分状態ｔｋとする。
【００８２】
例えば，図５に示すように，状態Ｓａの条件式は，状態Ｓａの条件式のみに対応する細分状態ｔ１と，状態Ｓａと状態Ｓｂの条件式の両方に対応する細分状態ｔ２とに分割され，状態Ｓｂの条件式は，状態Ｓｂの条件式のみに対応する細分状態ｔ３と，状態Ｓａと状態Ｓｂの条件式の両方に対応する細分状態ｔ２とに分割されることになる。
【００８３】
すなわち，状態細分化部１２は，細分状態ｔ１，ｔ２，ｔ３を定義する条件式を生成する。
【００８４】
状態細分化部１２は，状態Ｓｃを定義する条件式が既に排他的である場合には，状態Ｓｃを示す条件式を，そのまま細分状態ｔ４の条件式とする。
【００８５】
次に，細分状態検査部１３は，細分状態ｔ１，ｔ２，ｔ３，ｔ４の条件式について，状態を記述する条件式を満たすかを検査する。
【００８６】
例えば，細分状態検査部１３は，状態Ｓａを記述する条件式を満たすものが，細分状態ｔ１，ｔ２の条件式であると特定する。同様に，状態Ｓｂを記述する条件式を満たすものが，細分状態ｔ２，ｔ３の条件式であると特定する。
【００８７】
次に，細分パターン生成部１４は，検査結果をもとに，パターン情報２３の各パターンの状態Ｓａ，Ｓｂ，Ｓｃそれぞれを，対応する細分状態に置き換えた細分パターンを生成する。例えば，状態Ｓａは細分状態ｔ１，ｔ２に，状態Ｓｂは細分状態ｔ２，ｔ３に，状態Ｓｃは細分状態ｔ４に，それぞれ置き換えられ，各パターンについて細分状態を用いた細分パターンが生成される。パターンＳａＳｂに対応する細分パターンｔ１ｔ２，ｔ１ｔ３，ｔ２ｔ２，ｔ２ｔ３が，パターンの状態ＳｃＳａに対応する細分パターンｔ４ｔ１，ｔ４ｔ２が，それぞれ生成される。
【００８８】
生成された細分パターンである細分パターン情報２４は，細分パターン情報記憶部１５に記憶される。
【００８９】
図６は，細分パターン情報２４の構成例を示す図である。
【００９０】
細分パターン情報２４は，細分状態で記述された細分パターンと，対応する処理とが設定された細分パターン−処理対応表として実施される。
【００９１】
図６に示す細分パターン情報２４では，細分パターンｔ８ｔ５〜ｔ１３ｔ１３がパターンＳａＳｂに相当し，細分パターンｔ８ｔ５…がパターンＳｃＳａに相当することを示す。
【００９２】
次に，照合器生成部１６は，照合器として，細分パターン情報２４の細分パターンにもとづくオートマトンを備えるＡＣマシンを生成する。
【００９３】
その後，ストリームデータ処理装置１にストリームデータ２１が入力されると，パターン照合部１７は，入力されたストリームデータ２１を取得し，ストリームデータ２１の各変数Ｘ０，Ｘ１，Ｘ２，Ｘ３の値を，逐次，状態Ｓａ，Ｓｂ，Ｓｃに変換し，変換した状態Ｓａ，Ｓｂ，ＳｃをＡＣマシン（照合器）に代入してその処理結果を取得する。
【００９４】
ＡＣマシンから処理結果（例えば，細分パターンｔ８ｔ５＝パターンＳａＳｂに一致）が得られると，処理実行指示部１８は，その処理結果に対応する処理Ｄ実行の指示２５を出力する。
【００９５】
図７は，ストリームデータ処理装置１の処理フロー例を示す図である。
【００９６】
図７の処理フローは，アプリケーション開発段階において実行されるものとし，情報取得部１０により，状態情報２２およびパターン情報２３が情報記憶部１１に格納されているとする。
【００９７】
情報取得部１０は，状態情報２２の変数条件を入力して，各状態を定義する（ステップＳ１）。次に，情報取得部１０は，パターン情報２３のうち，定義した状態に関連するパターンと処理のペアとを複数入力する（ステップＳ２）。
【００９８】
そして，状態細分化部１２は，入力したパターンを１つ取り出し（ステップＳ３），未処理のパターンがあって，パターンを取り出した場合には（ステップＳ４のＹ），パターン展開処理を行う（ステップＳ５）。このパターン展開処理により，パターンに相当する細分パターン集合Ｐが得られる。状態細分化部１２は，得られた細分パターン集合Ｐを，細分パターン情報（細分パターン−処理対応表）２４に登録する（ステップＳ６）。
【００９９】
一方，状態細分化部１２は，パターンを取り出せなかった場合には（ステップＳ４のＮ），処理を終了する。
【０１００】
図８は，パターン展開処理（ステップＳ５）のより詳細な処理フロー例を示す図である。
【０１０１】
状態細分化部１２は，パターンの先頭から状態Ｓａを１つ取り出して状態Ｓ（Ｓ＝Ｓａ）として（ステップＳ５０），状態Ｓの分割処理を行う（ステップＳ５１）。状態Ｓの分割処理により，状態Ｓａが分割された細分状態の集合は結果Ｐとして出力されて保持される。ここで，結果Ｐ＝｛ｔ８，ｔ９，ｔ１２，ｔ１３｝とする。
【０１０２】
次に，状態細分化部１２は，出力された結果Ｐを結果Ｑに待避して（ステップＳ５２），パターンの先頭から未処理の状態を１つ取り出して状態Ｓとする（ステップＳ５３）。パターンに未処理の状態Ｓｂがあって，取り出した場合には（ステップＳ５４のＹ），ステップＳ５５の処理へ進み，パターンに未処理の状態がなく取り出さなかった場合には（ステップＳ５４のＮ），結果Ｐを出力して，処理を終了する。
【０１０３】
状態細分化部１２は，ステップＳ５５の処理として，結果Ｐをクリアして，状態Ｓ（Ｓ＝Ｓｂ）の分割処理を行ない，結果Ｒを出力する（ステップＳ５６）。状態Ｓの分割処理により，状態Ｓｂが分割された細分状態の集合は結果Ｒとして出力されて保持される。ここで，結果Ｒ＝｛ｔ５，ｔ１３｝とする。
【０１０４】
次に，状態細分化部１２は，結果Ｒから要素を１つ取り出して細分状態ｔ（ｔ＝ｔ５）とし（ステップＳ５７），結果Ｒから未処理の要素（細分状態）が全て取り出されていなければ（ステップＳ５８のＮ），結果Ｑの各要素に，取り出した細分状態ｔを追加したものを生成して，結果Ｐに追加し，ステップＳ５７の処理へ戻る（ステップＳ５９）。
【０１０５】
例えば，結果Ｑ＝｛ｔ８，ｔ９，ｔ１２，ｔ１３｝である場合に，各要素にｔ５が追加されて「ｔ８ｔ５，ｔ９ｔ５，ｔ１２ｔ５，ｔ１３ｔ５」が生成され，これらの要素が結果Ｐに追加される。よって，結果Ｐ＝｛ｔ８ｔ５，ｔ９ｔ５，ｔ１２ｔ５，ｔ１３ｔ５｝となる。
【０１０６】
さらに，ステップＳ５７の処理が実行され，結果Ｒから次のｔ（ｔ＝ｔ１３）が取り出されるので（ステップＳ５８のＮ），ステップＳ５９の処理において，結果Ｑ＝｛ｔ８，ｔ９，ｔ１２，ｔ１３｝の各要素にｔ１３が追加されて「ｔ８ｔ１３，ｔ９ｔ１３，ｔ１２ｔ１３，ｔ１３ｔ１３」が生成され，これらの要素が結果Ｐに追加される。よって，結果Ｐ＝｛ｔ８ｔ５，ｔ９ｔ５，ｔ１２ｔ５，ｔ１３ｔ５，ｔ８ｔ１３，ｔ９ｔ１３，ｔ１２ｔ１３，ｔ１３ｔ１３｝となる。
【０１０７】
状態細分化部１２は，ステップＳ５７〜Ｓ５９の処理の繰り返し（内ループ）により，結果Ｒから未処理の要素（細分状態）を全て取り出していれば（ステップＳ５８のＹ），ステップＳ５２の処理へ戻り，ステップＳ５２以降の処理を繰り返す（外ループ）。
【０１０８】
以上の処理によって，ＳａＳｂのパターンに対応する細分パターンの集合Ｐが生成され出力される。
【０１０９】
図９は，状態Ｓの分割処理（ステップＳ５１，Ｓ５６）のより詳細な処理フロー例を示す図である。
【０１１０】
状態細分化部１２は，状態Ｓの変数条件を取得して（ステップＳ５１０），状態Ｓの細分状態を保持するための変数Ｔとループ変数ｋをそれぞれ初期化して，Ｔ＝｛｝，ｋ＝０とする（ステップＳ５１１）。
【０１１１】
状態細分化部１２は，処理する変数の数Ｎから，ループ変数ｋが２Ｎ以上であるかを判定して，ループ処理終了を判定する。ｋ≧２Ｎでなければ（ステップＳ５１２のＮ），ステップＳ５１３へ進み，ｋ≧２Ｎであれば（ステップＳ５１２のＹ），変数Ｔを出力して，処理を終了する。
【０１１２】
ステップＳ５１３において，細分状態検査部１３は，細分状態ｔｋの検査処理を行う。
【０１１３】
検査の結果，細分状態ｔｋが状態Ｓに含まれる場合には（ステップＳ５１４の“１”），細分状態検査部１３は，変数Ｔに細分状態ｔｋを追加して，変数Ｔ＝｛ｔｋ｝∪Ｔとし（ステップＳ５１５），ステップＳ５１６へ進む。検査の結果，細分状態ｔｋが状態Ｓに含まれない場合には（ステップＳ５１４の“０”），細分状態検査部１３は，変数Ｔへの細分状態の追加を行わずに，ステップＳ５１６へ進む。ループ変数ｋを１加算し，さらに，ステップＳ５１２の処理へ戻る（ステップＳ５１６）。
【０１１４】
細分状態検査部１３が実行する細分状態の検査処理（ステップＳ５１３）の一例を説明する。
【０１１５】
状態細分化部１２は，状態Ｓの分割処理において，状態Ｓで記述されている変数条件に含まれるＮ個の変数について変数が占める領域の組み合わせを細分状態ｔ０，ｔ１，…として列挙している。
【０１１６】
細分状態検査部１３は，列挙された各細分状態ｔｋが状態Ｓに含まれるか，すなわち，細分状態ｔｋで全ての変数が状態Ｓの変数条件を満たしているかを検査し，状態Ｓに含まれる全ての細分状態ｔｋを取得している。例えば，状態情報２２の変数条件から，変数Ｘ０，Ｘ１，Ｘ２，Ｘ３の場合（Ｎ＝４）に，１６の細分領状態ｔ０〜ｔ１５が得られる。
【０１１７】
図１０は，細分状態における変数条件の例を示す図である。
【０１１８】
図１０に示す細分条件の変数条件表では，細分状態ｔ０の場合に，変数条件は「Ｘ３＜Ｃ３，Ｘ２＜Ｃ２，Ｘ１＜Ｃ１，Ｘ０＜Ｃ０」であり，細分状態ｔ１の場合に，変数条件は「Ｘ３＜Ｃ３（図中，「＜」と示す），Ｘ２＜Ｃ２（図中，「＜」と示す），Ｘ１＜Ｃ１（図中，「＜」と示す），Ｘ０≧Ｃ０（図中，「≧」と示す）」であることを示す。
【０１１９】
細分状態検査部１３は，図１０に示す変数条件表を保持する代わりに，各細分状態の変数の組に対応するビット列（ここでは，［Ｘ３Ｘ２Ｘ１Ｘ０］Ｂ）を作成する。例えば，細分状態ｔ０の変数条件は［００００］Ｂ，細分状態ｔ１の変数条件は［０００１］Ｂと表されることになる。
【０１２０】
具体的には，細分状態検査部１３は，細分状態ｔｋの添字ｋから，Ｘｎ（ｎは０からＮ−１）に関する条件式の不等号を調べ，変数ｎが条件式で与えられた定数の範囲内に含まれる場合を示す“＜”を“１”で，変数ｎが条件式で与えられた定数の範囲内に含まれない場合を示す“≧”を“０”でそれぞれ表してビット列に設定する。
【０１２１】
なお，“Ｘｎ＜Ｃｎ”と“Ｘｎ≧Ｃｎ”とを用いるケースに限らず，“Ｘｎ＝Ｃｎ”と“Ｘｎ≠Ｃｎ”とを用いるようにしてもよい。
【０１２２】
細分状態検査部１３は，図１０に示す細分状態の場合に，状態Ｓａの変数条件，すなわち，各変数の条件式の論理積（（Ｘ１＜Ｃ１）＆（Ｘ３≧Ｃ３））について，状態Ｓａに含まれる細分状態ｔｋを検査するときは，その変数条件に含まれる変数Ｘ１，Ｘ３にのみ着目する。そして，細分状態検査部１３は，状態Ｓの条件式の論理積を同時に満たす領域，例えば細分状態ｔ８，ｔ９，ｔ１２，ｔ１３を特定する。
【０１２３】
図１１は，細分状態の検査処理（ステップＳ５１３）の処理フロー例を示す図である。
【０１２４】
ここでは，状態Ｓａの変数条件（（Ｘ１＜Ｃ１）＆（Ｘ３≧Ｃ３））の場合に，細分状態ｔ０を検査するときを例として説明する。
【０１２５】
細分状態検査部１３は，ループ変数ｎを初期化（ｎ＝０）して（ステップＳ３００），処理する変数の数Ｎから，ループ変数ｎがＮ以上であるかを判定して，ループ処理終了を判定する（ステップＳ３０１）。ｎ≧Ｎでなければ（ステップＳ３０１のＮ），ステップＳ３０２へ進み，ｎ≧Ｎであれば（ステップＳ３０１のＹ），“１”を出力して，処理を終了する。
【０１２６】
ステップＳ３０２の処理で，細分状態検査部１３は，変数条件が変数Ｘｎを含むかを調べ，変数Ｘｎが含まれない場合には（Ｓ３０２のＮ），ステップＳ３０３の処理へ進み，変数Ｘｎが含まれる場合には（Ｓ３０２のＹ），ステップＳ３０４の処理へ進む。
【０１２７】
例えば，ループ変数ｎ＝０の場合に，変数Ｘ０が状態Ｓａの変数条件（（Ｘ１＜Ｃ１）＆（Ｘ３≧Ｃ３））に含まれるかが調べられ，変数Ｘ０が変数条件に含まれないので，ステップＳ３０３へ進む。
【０１２８】
ステップＳ３０３の処理では，細分状態検査部１３は，ループ変数ｎを１加算して更新し，ステップＳ３０１の処理へ戻る。
【０１２９】
ステップＳ３０４の処理では，細分状態検査部１３は，変数Ｘｎの条件式の不等号を調べる。変数Ｘｎの条件式の不等号が“＜”であれば（ステップＳ３０４の“＜”），細分状態検査部１３は，細分状態ｔｋの添え字ｋのｎビット目の値を調べる（ステップＳ３０５）。
【０１３０】
細分状態ｔｋの添え字ｋのｎビット目が“０”であれば（ステップＳ３０５の“０”），条件式の不等号“＜（０）”と一致するので，細分状態検査部１３は，ステップＳ３０３の処理へ進む。細分状態ｔｋの添え字ｋのｎビット目が“１”であれば（ステップＳ３０５の“１”），不等号“＜（０）”と一致しないので，細分状態検査部１３は，その状態に含まれないことを示す“Ｅｘ（０）”を出力して，処理を終了する。
【０１３１】
一方，変数Ｘｎの条件式の不等号が“≧”であれば（ステップＳ３０４の“≧”），細分状態検査部１３は，細分状態ｔｋの添え字ｋのｎビット目の値を調べ，細分状態ｔｋの添え字ｋのｎビット目が“１”であれば，条件式の不等号“≧（１）”と一致するので，細分状態検査部１３は，ステップＳ３０３の処理へ進む。細分状態ｔｋの添え字ｋのｎビット目が“０”であれば（ステップＳ３０６の“０”），不等号“≧（１）”と一致しないので，細分状態検査部１３は，その状態に含まれないことを示す“Ｅｘ（０）”を出力して，処理を終了する。
【０１３２】
細分状態検査部１３は，以上の処理をループ変数が終了に至るまで繰り返し，ループ処理終了の判定において，ループ変数がｎ≧Ｎであれば（ステップＳ３０１のＹ），全ての変数Ｘ０〜Ｘｎについて値が条件式を満たすことがチェックできたことになるので，その状態に含まれることを示す“Ｉｎ（１）”を出力して，処理を終了する。
【０１３３】
以上の処理により，状態Ｓａの場合に，細分状態ｔ８，ｔ９，ｔ１２，ｔ１３について，“Ｉｎ（１）”が出力され，それ以外の細分状態について“Ｅｘ（０）”が出力される。
【０１３４】
そして，細分パターン生成部１４は，状態Ｓａに対応する細分状態ｔ８，ｔ９，ｔ１２，ｔ１３を用いて，パターンＳａＳｂに相当する細分パターンを生成して，細分パターン情報記憶部１５に格納する。
【０１３５】
図１２は，アプリケーション実行段階における，ストリームデータの判定処理の処理フロー例を示す図である。
【０１３６】
照合器生成部１６は，細分パターン情報記憶部１５に格納された細分パターン情報を取得し，細分パターン情報にもとづくオートマトンを用いるＡＣマシンを生成して照合器とする（ステップＳ１１）。ＡＣマシンを生成する手法は，既知の処理手法のいずれを用いてもよい。一例として，“Flexible Pattern Matching in String”（G. Navarro, M. Raffinot，Cambridge Press，２００２年，ｐｐ．４９−５４）の手法がある。
【０１３７】
パターン照合部１７は，ストリームデータ２１を受け取り（ステップＳ１２），ストリームデータ２１内の各変数Ｘｎの値を細分状態ｔＢに変換する処理を行う（ステップＳ１３）。入力されたストリームデータ２１の変数Ｘｎの値の組と，細分状態ｔＢとの形式を合わせるためである。変換処理により，ストリームデータ２１のＮ個の変数Ｘｎの値の組に対応する細分状態ｔＢが得られる。
【０１３８】
次に，パターン照合部１７は，細分状態ｔＢを，ＡＣマシン（照合器）に入力し，一致した細分パターンに対応する処理を得る（ステップＳ１４）。
【０１３９】
パターン照合部１７は，細分パターンのいずれかに一致していれば（ステップＳ１５のＹ），処理実行指示部１８は，一致した細分パターンに対応する「処理」の処理実行の指示２５を出力し（ステップＳ１６），パターン照合部１７は，ステップＳ１２の処理へ戻る。細分パターンのいずれにも一致していなければ（ステップＳ１５のＮ），パターン照合部１７は，そのままステップＳ１２の処理へ戻る。
【０１４０】
図１３は，細分状態ｔへの変換処理（ステップＳ１３）の処理フロー例を示す図である。ここでは，ストリームデータ２１の各変数Ｘｎの値を細分状態ｔに変換する場合を例とする。
【０１４１】
パターン照合部１７は，入力されたストリームデータ２１から，変更された変数とその値との組を１つ取り出して，Ｘｎ＝ｚｎとする（ステップＳ１３０）。
【０１４２】
パターン照合部１７は，ストリームデータ２１から取り出す変数とその値があって，取り出すことができたら（ステップＳ１３１のＹ），取り出した変数の値ｚｎが，状態情報２２の変数Ｘｎに対応する変数条件の定数Ｃｎについて，ｚｎ＜Ｃｎであるかを調べる（ステップＳ１３２）。変数の値ｚｎがｚｎ＜Ｃｎであれば（ステップＳ１３２のＹ），パターン照合部１７は，０または１を表す＊がＮ個並んでいるビット列［＊＊…＊］Ｂのｎビット目を“０（＜を示す）”にして，ステップＳ１３０の処理へ戻る。変数の値ｚｎがｚｎ＜Ｃｎでなければ（ステップＳ１３２のＮ），ｚｎ≧Ｃｎであるので，パターン照合部１７は，ビット列［＊＊…＊］Ｂのｎビット目を“１（≧を示す）”にして（ステップＳ１３４），ステップＳ１３０の処理へ戻る。
【０１４３】
パターン照合部１７は，ストリームデータ２１から取り出す変数とその値がなくなったら（ステップＳ１３１のＮ），“ｔＢ”を出力して，処理を終了する。
【０１４４】
具体的には，変数条件の定数を，Ｃ０＝２０，Ｃ１＝Ｃ２＝Ｃ３＝１０とする場合に，ストリームデータ２１として，ｚ０＝５，ｚ１＝３，ｚ２＝２，ｚ３＝１２が入力されたとする。
【０１４５】
１回目のループ処理により，ｚ０＝５が取り出され，ｚ０＜Ｃ０が成立するので，ビット列［］Ｂのｎ＝０番目が“０”になる（［＊＊＊０］Ｂ）。次のループ処理で，ｚ１＝３が取り出され，ｚ１＜Ｃ１が成立するので，ビット列［］Ｂのｎ＝１番目が“０”になる（［＊＊００］Ｂ）。
【０１４６】
３回目，４回目のループ処理では，ｚ２＝２，ｚ３＝１２がそれぞれ順に取り出され，同様に処理される。ｚ２＝２について，ｚ２＜Ｃ２が成立するので，ビット列［］Ｂのｎ＝２番目が“０”になり（［＊０００］Ｂ），ｚ３＝１２については，ｚ３＜Ｃ３が成立しないので，ビット列［］Ｂのｎ＝３番目が“１”になり，最終的にビット列［１０００］Ｂに変換される。
【０１４７】
そして，このビット列［１０００］Ｂは，細分状態ｔ８に一致するため（図１０参照），ｔＢとして“ｔ８”が出力される。
【０１４８】
次に入力されたストリームデータ２１の変数のうち，ｚ０＝１５，ｚ２＝１５と変化しているとする。
【０１４９】
１回目のループ処理で，ｚ０＝１５が取り出され，ｚ０＜Ｃ０が成立するので，ビット列［］Ｂのｎ＝０番目が“０”になる。次のループ処理で，ｚ２＝１５が取り出され，ｚ１＜Ｃ１が成立しないので，ビット列［］Ｂのｎ＝２番目が“１”になり，ビット列［１１００］Ｂとなる。このビット列［１１００］Ｂは，細分状態ｔ１２に一致するため（図１０参照），ｔＢとして“ｔ１２”が出力される。
【０１５０】
その後，パターン照合部１７によって，得られた細分状態ｔＢを照合器に代入されることにより，ストリームデータ２１の変数の値のパターン照合が行われる。
【０１５１】
上記の説明で示すストリームデータ処理装置１，１ａ，１ｂは，演算装置（ＣＰＵ），一時記憶装置（ＤＲＡＭ，フラッシュメモリ等）および永続性記憶装置（ＨＤＤ，フラッシュメモリ等）を有し，外部とデータの入出力をするコンピュータによって実施することができる。
【０１５２】
また，ストリームデータ処理装置１，１ａ，１ｂは，このコンピュータが実行可能なプログラムによっても実施することができる。この場合に，ストリームデータ処理装置１，１ａ，１ｂが，それぞれ有すべき機能の処理内容を記述したプログラムが提供される。提供されたプログラムを上記コンピュータが実行することによって，上記説明したストリームデータ処理装置１，１ａ，１ｂのそれぞれの処理機能がコンピュータで実現される。なお，上記コンピュータは，可搬型記録媒体から直接プログラムを読み取り，そのプログラムに従った処理を実行することもできる。さらに，上記プログラムは，コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【０１５３】
以上説明したように，ストリームデータを状態列に変換して，正規表現パターンと照合する処理において，同時に複数の状態を示すような変数条件式が与えられていた場合には，従来手法では処理ができないか，処理できたとしても処理コストが大きいという問題があった。
【０１５４】
開示したストリームデータ処理装置１によれば，状態定義として，変数の値の領域が複数の状態を占めるような変数条件が与えられた場合でも，状態の定義として記述された変数条件を，排他的な変数の領域となるような変数条件で示す細分状態に分けて，照合のために与えられたパターンを細分状態による細分パターンに変換することにより，ＡＣマシンを用いた正規表現パターン照合を行うことが可能となる。
【０１５５】
本発明と従来技術との効果を比較するため，理論的な処理コストを検討する。
【０１５６】
従来の手法として，ストリームデータの状態履歴を保持して照合する第１の照合手法を採用する。検討するケースとして，照合するパターン長Ｈ＝１０，パターン数Ｍ＝１０，入力されるストリームデータの変数の数＝Ｎとし，１命令に１μｓ（マイクロ秒）を要すると仮定する。
【０１５７】
さらに，パターン照合処理では，ストリームデータを逐次リアルタイムで処理する必要から，応答時間以内で処理できる問題の大きさ（Ｍ）の上限を比較する。具体的には，１命令の所要時間×処理コスト≦応答時間（応答時間＝１０ｍｓ，Ｈ＝１０，Ｍ＝Ｎ）として，問題の大きさ（Ｍ）を求める。
【０１５８】
従来手法では，処理コストは，Ｈ×Ｍ（＝Ｎ）回の算術比較処理となり，問題の大きさ（Ｍ）は，約１，０００（＝１０−３×１０×Ｍ≦１０（ｍｓ））回が上限となる。一方，本発明では，処理コストは，Ｎ回の算術比較処理となり，約１００，０００（＝１０−３×（Ｍ／１０）≦１０（ｍｓ））回が上限となる。
【０１５９】
さらに，パターン照合処理前の初期化処理では，従来手法のパターン照合処理での問題の大きさの限界に対する初期化処理時間を比較する。具体的には，従来手法の問題の大きさの上限（Ｍ＝１，０００）の場合に，１命令の処方時間×処理コストとして，初期化処理時間を求めるとする。
【０１６０】
従来手法では，Ｈに変数Ｎを代入する算術処理となるため，約１（＝１０−３×１０×１００）ｍｓ（ミリ秒）である。一方，本発明では，Ｈ×Ｍに比例した処理回数となり，約１０（＝１０−３×１０×１００）ｍｓとなる。
【０１６１】
したがって，本発明は，初期化処理段階では，従来手法に比べて，１０倍程度処理時間が長くなるが，１０ｍｓ程度であれば許容範囲であると考えられ，照合処理段階では，およそ１００倍の大きさの問題を扱うことができることが分かる。
【０１６２】
さらに，パターン数Ｍが多く，パターン長Ｈが長い場合ほど，本発明は，従来手法の処理に比べて効率のよい処理を実現することができることが分かる。
【符号の説明】
【０１６３】
１，１ａ，１ｂ  ストリームデータ処理装置
１０  情報取得部
１１  情報記憶部
１２  状態細分化部
１３  細分状態検査部
１４  細分パターン生成部
１５  細分パターン情報記憶部
１６  照合器生成部
１７  パターン照合部
１８  処理実行指示部
１９  出力部
１１０  細分パターン取得部
２１  ストリームデータ
２２  状態情報
２３  パターン情報
２４  細分パターン情報
２５  指示
２６  識別情報
【図１】
0005505206.tif 000002
【図２】
0005505206.tif 000003
【図３】
0005505206.tif 000004
【図４】
0005505206.tif 000005
【図５】
0005505206.tif 000006
【図６】
0005505206.tif 000007
【図７】
0005505206.tif 000008
【図８】
0005505206.tif 000009
【図９】
0005505206.tif 000010
【図１０】
0005505206.tif 000011
【図１１】
0005505206.tif 000012
【図１２】
0005505206.tif 000013
【図１３】
0005505206.tif 000014
【図１４】
0005505206.tif 000015
【図１５】
0005505206.tif 000016
【図１６】
0005505206.tif 000017
【図１７】
0005505206.tif 000018