(57)【要約】列方向に配列された現在の状態と行方向に配列された入力記号とに基づいて次の状態である遷移先を示す状態遷移表にて、隣接する列の遷移先の値が互いに最も近い値になるように列を列単位に並び替え（１００）、列が並び替えられた状態遷移表にて、各列の現在の状態が昇順に並ぶように状態名を付け替え（１０１）、列が並び替えられた状態遷移表における列の遷移先の値の変化点を表すビットマップ及び連続する同一の遷移先の値を１つにまとめた遷移先テーブルを行ごとに作成する（１０２）。固定長ブロックに分割されたビットマップの先頭のブロックと任意のブロックとの間に存在する変化点の数を当該ブロックごとに示すラベルを全ての入力記号について作成し（１０３〜１０４）、メモリに格納する（１０５）。
2008102474.tif 000002
【特許請求の範囲】
【請求項１】
有限オートマトンを用いるパターンマッチング方法であって、
列方向に現在の状態が配列され、また行方向に入力記号が配列され、前記現在の状態と前記入力記号とに基づいて次の状態である遷移先を示す状態遷移表にて、隣接する列の前記遷移先の値が互いに最も近い値になるように前記列を列単位に並び替える処理と、
前記列が並び替えられた状態遷移表にて、各列の現在の状態が昇順に並ぶように状態名を付け替える処理と、
前記列が並び替えられた状態遷移表における前記列の遷移先の値の変化点を表すビットマップ及び連続する同一の遷移先の値を１つにまとめた遷移先テーブルを行ごとに作成する処理とを有するパターンマッチング方法。
【請求項２】
請求項１に記載のパターンマッチング方法において、
前記ビットマップを予め設定された固定長のブロックに分割する処理と、
前記ビットマップの先頭のブロックと任意のブロックとの間に存在する前記変化点の数を当該ブロックごとに示すラベルを作成する処理と、
現在の前記状態に最も近い位置に存在する前記ラベルを基準となるラベルとし、前記ビットマップ上の前記基準となるラベルに対応するブロックと前記状態に対応するビットとの間に存在する前記変化点の数である差分を計算する処理と、
前記差分と前記基準となるラベルが示す前記変化点の数とに基づいて、前記遷移先テーブルのインデックスを算出する処理と、
前記算出されたインデックスが指し示す遷移先を次の状態とする処理とを有することを特徴とするパターンマッチング方法。
【請求項３】
有限オートマトンを用いてパターンマッチングを行うプログラムであって、
列方向に現在の状態が配列され、また行方向に入力記号が配列され、前記現在の状態と前記入力記号とに基づいて次の状態である遷移先を示す状態遷移表にて、隣接する列の前記遷移先の値が互いに最も近い値になるように前記列を列単位に並び替える手順と、
前記列が並び替えられた状態遷移表にて、各列の現在の状態が昇順に並ぶように状態名を付け替える手順と、
前記列が並び替えられた状態遷移表における前記列の遷移先の値の変化点を表すビットマップ及び連続する同一の遷移先の値を１つにまとめた遷移先テーブルを行ごとに作成する手順とをコンピュータに実行させるプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記ビットマップを予め設定された固定長のブロックに分割する手順と、
前記ビットマップの先頭のブロックと任意のブロックとの間に存在する前記変化点の数を当該ブロックごとに示すラベルを作成する手順と、
現在の前記状態に最も近い位置に存在する前記ラベルを基準となるラベルとし、前記ビットマップ上の前記基準となるラベルに対応するブロックと前記状態に対応するビットとの間に存在する前記変化点の数である差分を計算する手順と、
前記差分と前記基準となるラベルが示す前記変化点の数とに基づいて、前記遷移先テーブルのインデックスを算出する手順と、
前記算出されたインデックスが指し示す遷移先を次の状態とする手順とをコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力されたデータの中に特定のパターンが存在するか否かを判定するパターンマッチング方法及びプログラムに関する。
【背景技術】
【０００２】
入力されたデータの中に特定のパターンが存在するか否かを判定するパターンマッチングは、コンピュータを用いた情報処理分野における要素技術であり、その用途は多岐にわたる。例えば、ワードプロセッサでのテキスト検索、バイオテクノロジーにおけるＤＮＡ解析、電子メールなどに潜むコンピュータウィルスの検知等である。【０００３】
パターンマッチングの実現手段の１つとして、有限オートマトン（別名：有限状態機械、有限ステートマシン）を利用する方法がある。パターンマッチングのための有限オートマトンは、パターンあるいはパターンの集合から作成される。例として、３種類のパターン“ＡＢ＊Ｃ”、“Ａ［Ｂ｜Ｃ］”及び”ＣＡＢ”を受理するＮＦＡ（Non-deterministic  Finite  Automaton：非決定性有限オートマトン）及びＤＦＡ（Deterministic  Finite  Automaton：決定性有限オートマトン）について説明する。【０００４】
これらのパターンには正規表現が含まれる。正規表現とはパターンを簡潔に表現するための表現法である。【０００５】
第１のパターン“ＡＢ＊Ｃ”に含まれる“Ｂ＊”は０個以上のＢの連続を表す。従って、第１のパターンは、テキスト“ＡＣ”，“ＡＢＣ”，“ＡＢＢＣ”，…にマッチする。また、第２のパターン“Ａ［Ｂ｜Ｃ］”に含まれる“［Ｂ｜Ｃ］”はＢまたはＣを表す。従って、第２のパターンは、テキスト“ＡＢ”及び“ＡＣ”にマッチする。【０００６】
図１は、３種類のパターン“ＡＢ＊Ｃ”、“Ａ［Ｂ｜Ｃ］”及び”ＣＡＢ”を受理する従来のＮＦＡの一例を示す図である。また、図２は、３種類のパターン“ＡＢ＊Ｃ”、“Ａ［Ｂ｜Ｃ］”及び”ＣＡＢ”を受理する従来のＤＦＡの一例を示す図である。ＮＦＡとＤＦＡの違いについては後述する。【０００７】
パターンマッチングのための有限オートマトンは、初期状態から開始し、入力された文字に対応する枝を経由して次の状態へ遷移する。そして、パターンの最終文字に対応する状態（図１及び図２では二重円で囲まれた状態）に到達したら、そのパターンを検出したとみなす。【０００８】
上記の動作をテキストの先頭から末尾までの全ての文字について繰り返し実施する。【０００９】
有限オートマトンの表現形式として、ＮＦＡとＤＦＡの２種類が存在する。【００１０】
ＤＦＡは、決定性という単語が示すように、現在の状態と入力が決まると、次の状態が一意に定まる有限オートマトンである。【００１１】
一方、ＮＦＡは、次の状態が一意に定まらない有限オートマトンである。例えば、図１に示したＮＦＡの状態“０”に着目すると、入力された文字“Ａ”に対応する遷移先として、状態“０”、状態“４”及び状態“５”の３つの状態が存在する。【００１２】
逐次処理コンピュータ上でＮＦＡを動作させる場合、ある状態からの遷移先が複数存在するとき、その状態をスタックに積んでから、複数の遷移先のうち１つを選んで状態遷移する。そして、状態遷移できなくなるかテキストの末尾に達するまでＮＦＡを辿る。その後、スタックから状態を１つ取り出して、その状態へ復帰し、前回と異なる遷移先を選択して状態遷移する。上記の動作をスタックが空になるまで繰り返す。【００１３】
このように、逐次処理コンピュータ上でＮＦＡを動作させる場合、過去の状態に戻って状態遷移を再開する行為、すなわち、バックトラック（Backtracking）が発生する。このバックトラックの影響により、ＮＦＡに基づく検索の速度はＤＦＡよりも劣る。【００１４】
一方、ＤＦＡに含まれる状態数は、ＮＦＡよりも多くなる傾向がある。そのため、ＤＦＡを格納するためのメモリの量はＮＦＡの場合よりも多くなりやすい。パターンマッチングの速度を重視するアプリケーションの大部分は、ＮＦＡではなくＤＦＡを採用するが、メモリの必要量に関する課題を抱える事例は少なくない。【００１５】
一般的にはコンピュータ上のメモリには、ＤＦＡは状態遷移表の形式で格納される。【００１６】
図３は、コンピュータ上のメモリの格納される状態遷移表の一例を示す図である。【００１７】
図３に示した状態遷移表１０は、図２のＤＦＡから作成されたものであり、ＤＦＡと１対１に対応する。状態遷移表は、現在の状態と入力された記号に対応する遷移先とが列挙された表である。状態遷移表の中の要素数は、入力記号の種類の数と、状態数との積である。【００１８】
また、有限状態オートマトンの状態数の総和を、分割や合成により削減する技術が考えられている（例えば、特許公開２００２−２９７６８１号公報参照。）。【００１９】
パターンマッチングの分野においては、パターンの個数が多かったり、各パターンが複雑で長かったりする場合、ＤＦＡの状態数が数万に達することは珍しくない。言うまでもなく、このとき状態遷移表は巨大になり、その格納には大量のメモリが消費されてしまうという問題点がある。【００２０】
そこで、何らかの方法で状態遷移表の情報量を削減し、状態遷移表を収容するためのメモリの量を減らすことが望まれる。ただし、情報量の削減によって、状態遷移の仕方が変化してはならない。【００２１】
情報を劣化させずにサイズを小さくすることは可逆圧縮と呼ばれる。可逆圧縮には数々の公知のアルゴリズムや実装が存在する（ＬＺ法、ブロックソート法、ハフマン符号化、算術符号化など）。【００２２】
公知の可逆圧縮アルゴリズムを用いて状態遷移表を圧縮し、圧縮後の状態遷移表をメモリに格納してメモリ消費量を減らすことは可能である。しかし、公知の可逆圧縮アルゴリズムを用いて状態遷移表を圧縮した場合、状態遷移の速度に関する次のような問題が生じる。【００２３】
圧縮後の状態遷移表を用いて状態遷移する場合、現在の状態と入力に対応する遷移先を、圧縮後のデータの中から探し出して伸長する処理が必要になる。公知の可逆圧縮アルゴリズムは、圧縮前のデータをある程度の大きさのブロックに分割してブロック単位に圧縮する。すなわち、ブロック単位にしか伸長できないという問題点がある。状態遷移表の中の１つの遷移先のサイズは数バイト程度である。従って、たかだか数バイトの情報を得るためにブロック全体を伸長しなければならず、無駄な処理が発生して状態遷移が遅くなってしまう。また、圧縮率が低下してしまうため、ブロックのサイズを極端に小さくすることもできない。【００２４】
また、特許公開２００２−２９７６８１号公報に記載された技術においては、等価な部分有限状態オートマトンを１つの状態遷移に置き換えて分割するものであるため、等価な部分有限状態オートマトンを有さない有限状態オートマトンの状態遷移の情報量を削減するものについては記載されていない。
【発明の開示】
【００２５】
本発明は、上述した課題を解決するため、状態遷移の際の計算量をあまり増やさずに、状態遷移表の情報量を削減することができるパターンマッチング方法及びプログラムを提供することを目的とする。
【００２６】
上記目的を達成するために本発明は、
有限オートマトンを用いるパターンマッチング方法であって、
列方向に現在の状態が配列され、また行方向に入力記号が配列され、前記現在の状態と前記入力記号とに基づいて次の状態である遷移先を示す状態遷移表にて、隣接する列の前記遷移先の値が互いに最も近い値になるように前記列を列単位に並び替える処理と、
前記列が並び替えられた状態遷移表にて、各列の現在の状態が昇順に並ぶように状態名を付け替える処理と、
前記列が並び替えられた状態遷移表における前記列の遷移先の値の変化点を表すビットマップ及び連続する同一の遷移先の値を１つにまとめた遷移先テーブルを行ごとに作成する処理とを有する。
【００２７】
以上説明したように本発明においては、列方向に現在の状態が配列され、また行方向に入力記号が配列され、現在の状態と入力記号とに基づいて次の状態である遷移先を示す状態遷移表にて、隣接する列の遷移先の値が互いに最も近い値になるように列を列単位に並び替え、列が並び替えられた状態遷移表にて、各列の現在の状態が昇順に並ぶように状態名を付け替え、列が並び替えられた状態遷移表における列の遷移先の値の変化点を表すビットマップ及び連続する同一の遷移先の値を１つにまとめた遷移先テーブルを行ごとに作成する構成としたため、状態遷移の際の計算量をあまり増やさずに、状態遷移表の情報量を削減することができる。
【図面の簡単な説明】
【００２８】
【図１】３種類のパターン“ＡＢ＊Ｃ”、“Ａ［Ｂ｜Ｃ］”及び”ＣＡＢ”を受理する従来のＮＦＡの一例を示す図である。
【図２】３種類のパターン“ＡＢ＊Ｃ”、“Ａ［Ｂ｜Ｃ］”及び”ＣＡＢ”を受理する従来のＤＦＡの一例を示す図である。
【図３】コンピュータ上のメモリの格納される状態遷移表の一例を示す図である。
【図４】図３に示した状態遷移表を並び替えた後の状態遷移表を示す図である。
【図５】図３に示した状態遷移表の情報量を削減する手順を説明するためのフローチャートである。
【図６】図５に示したステップ１００の処理の詳細を説明するためのフローチャートである。
【図７】図５に示したステップ１００が実行された後のＲＥＰＬＡＣＥ（・）の内容を示す図である。
【図８】状態名付け替え後の状態遷移表の一例を示す図である。
【図９】図５に示したステップ１０２にて作成されるビットマップ及び遷移先テーブルの一例を示す図である。
【図１０】図９に示したビットマップから作成されるラベルテーブルの一例を示す図である。
【図１１】現在の状態と入力記号とが与えられている場合、次の状態（＝遷移先）を求める手順を説明するためのフローチャートである。
【図１２】基準となるラベルを現在の状態”ｓ”から決定する方法を模式化した図である。
【発明を実施するための最良の形態】
【００２９】
以下に、本発明の実施の形態について図面を参照して説明する。【００３０】
本発明は、パターンマッチングのための状態遷移図もしくは状態遷移表において、入力が等しければ複数の状態から同一の状態へ遷移することが多い、という性質を利用して、状態遷移表の情報量を削減する。【００３１】
図３に示した状態遷移表１０の一例を用いて、その性質を明らかにする。図３に示した状態遷移表１０は、背景技術の説明で使用されたものである。【００３２】
図３に示した状態遷移表１０について、隣接する列の遷移先の値が互いに最も近い値になるように列を並び替えると、その性質が顕在化する。【００３３】
図４は、図３に示した状態遷移表１０を並び替えた後の状態遷移表を示す図である。【００３４】
図４に示すように、並び替え後の状態遷移表１１は、水平方向に同一の値（遷移先）が連続している箇所が多いことが分かる。この性質に基づいて状態遷移表１０の情報量を削減する手順について説明する。【００３５】
図５は、図３に示した状態遷移表１０の情報量を削減する手順を説明するためのフローチャートである。【００３６】
まず、状態遷移表１０の隣接する列の遷移先の値が互いに最も近い値になるように、ステップ１００にて、状態遷移表１０を列単位に並び替える。なお、状態遷移表１０は、列方向に現在の状態、行方向に入力記号が配列された形式をとる。行と列が反転した状態遷移表を用いる場合は、それを転置（９０度回転）するか、もしくは、文中の「行」と「列」の単語を読み替える。本ステップの主な目的は、状態遷移表１０の各列が、並び替え後の状態遷移表１１のどの列に移動するかの対応関係を表すテーブルを作成することである。このテーブルをＲＥＰＬＡＣＥ（・）と呼ぶ。【００３７】
状態遷移表１０の、ある列の現在の状態を”ｓ”としたとき、ＲＥＰＬＡＣＥ（ｓ）は並び替え後の状態遷移表１１における、ｓに対応する列の位置を示す。列の位置は、並び替え後の状態遷移表１１の左から順に０、１、２、…、のように採番される。【００３８】
例えば、図３に示した状態遷移表１０の現在の状態”４”に対応する列が、並び替え後の状態遷移表１１の左から２番目の列に移動するとき、ＲＥＰＬＡＣＥ（４）＝１になる。【００３９】
なお、ＲＥＰＬＡＣＥ（・）はステップ１００と後述のステップ１０１とで用いられるテンポラリな配列であって、最終的にはメモリに格納されない。【００４０】
ここで、状態遷移を２次元配列ｇ（ｓ，ａ）で表す。ｇ（ｓ，ａ）は、現在の状態が”ｓ”であるときに入力”ａ”が与えられたときの遷移先（＝次の状態）である。【００４１】
また、並び替えの際の指標として、２つの列の間の類似度を定義する。状態”ｓ”と状態”ｔ”との間の類似度は、（式１）で算出される。【００４２】
【数１】
2008102474.tif 000003
類似度の値が大きいほど、それら２つの状態に対応する列の内容が互いに似通っていることになる。【００４３】
図６は、図５に示したステップ１００の処理の詳細を説明するためのフローチャートである。【００４４】
ステップ２００にて、状態遷移表１０における全状態の集合をＵ、初期状態をｓにそれぞれ代入し、列の位置”ｉ”を０に初期化する。【００４５】
ステップ２０１にて、状態”ｓ”の移動先の列の位置”ｉ”をＲＥＰＬＡＣＥ（ｓ）に記録したあと、ステップ２０２にて、列の位置”ｉ”をインクリメントして、Ｕから状態”ｓ”を取り除く。その後、ステップ２０３にて、Ｕが空集合であるか判定する。【００４６】
空集合であればステップ１００の処理は終了する。【００４７】
一方、空集合でなければ、ステップ２０４にて、状態”ｓ”と状態”ｔ”との間の類似度を最大化するような、ｔ∈Ｕを１つ求める。この類似度は、上述した（式１）に従って算出される。【００４８】
その後、ステップ２０５にて、ｔをｓに代入し、ステップ２０１へ戻る。【００４９】
図６のフローチャートから明らかなように、ＲＥＰＬＡＣＥ（初期状態）＝０である。すなわち、初期状態に対応する列は、並び替え後の状態遷移表１１の最左列に移動する。【００５０】
図３に示した状態遷移表１０の一例を、上述したステップの手順に従って並び替えると、図４に示した並び替え後の状態遷移表１１が得られる。【００５１】
図７は、図５に示したステップ１００が実行された後のＲＥＰＬＡＣＥ（・）の内容を示す図である。【００５２】
図７に示すように並び替え後の状態遷移表１１は、状態”ｓ”とＲＥＰＬＡＣＥ（ｓ）とが対応付けられているものである。【００５３】
その後、ステップ１０１にて、並び替え後の状態遷移表１１において、現在の状態が最左列から順に０、１、２、…、と昇順に並ぶように状態名を付け替える。【００５４】
図８は、状態名付け替え後の状態遷移表の一例を示す図である。【００５５】
図８に示すように状態名付け替え後の状態遷移表１２においては、並び替え後の状態遷移表１１にて、ある現在の状態”ｓ”が左から（Ｘ＋１）番目の列に配置されていたとき、その状態”ｓ”の新しい状態名をＸにする。状態”ｓ”の移動先の列の位置はＲＥＰＬＡＣＥ（ｓ）であるから、状態”ｓ”の新しい状態名はＲＥＰＬＡＣＥ（ｓ）に等しい。【００５６】
状態名付け替え後の状態遷移表１２が２次元配列ｇ’（ｓ、ａ）で表されるとすると、
ｇ’（ＲＥＰＬＡＣＥ（ｓ）、ａ）＝ｇ（ｓ、ａ）  ｆｏｒ  ∀ｓ∈全状態の集合、∀ａ∈Σ
の関係が成立する。なお、Σは、全ての入力記号（テキスト検索の場合は文字）の集合である。例えば、Σ＝｛Ａ、Ｂ、Ｃ｝などである。【００５７】
また、ＲＥＰＬＡＣＥ（初期状態）＝０であるから、初期状態の新しい状態名は０になる。その他の状態の新しい状態名は自然数である。【００５８】
その後、ステップ１０２にて、状態名付け替え後の状態遷移表１２において、入力記号ごとに、連続する同一の遷移先を１つにまとめた遷移先テーブルと、遷移先の変化点を表すビットマップを作成する。対象とする入力記号をａ（ａ∈Σ）とする。【００５９】
図９は、図５に示したステップ１０２にて作成されるビットマップ及び遷移先テーブルの一例を示す図である。ここで、図８に示した状態名付け替え後の状態遷移表１２の、入力記号”Ａ”に対応するビットマップ２０を例に挙げて示す。【００６０】
図９に示したビットマップ２０は、（状態数−１）ビット幅の１次元配列である。ビットマップ２０をＢＩＴＭＡＰ（ｘ）（０≦ｘ＜状態数−１）と表現すると、ｇ’（ｘ、ａ）とｇ’（ｘ＋１、ａ）とが等しい場合ＢＩＴＭＡＰ（ｘ）＝０であり、そうでない場合はＢＩＴＭＡＰ（ｘ）＝１である。【００６１】
また、図９に示した遷移先テーブル２２は、ｇ’（ｘ、ａ）（０≦∀ｘ＜状態数）の中から連続する同一の値を除去し、固有な値のみを残した配列であり、図８に示した状態名付け替え後の状態遷移表１２の、入力記号”Ａ”に対応する遷移先テーブル２２を例に挙げて示したものである。【００６２】
図９に示すように、連続する同一の遷移先の情報が除去されているため、状態遷移表の入力記号”Ａ”に関する情報量が減少していることが分かる。【００６３】
そして、ステップ１０３にて、入力記号ごとに、ビットマップ２０からラベルテーブルを作成する。【００６４】
図１０は、図９に示したビットマップ２０から作成されるラベルテーブルの一例を示す図である。【００６５】
図１０に示したラベルテーブル２１は、状態遷移を高速化するための補助情報として使用される。ラベルテーブル２１の使用方法は後述される。【００６６】
図１０に示すように、ビットマップ２０を予め設定された固定長のブロックに等分割し、ブロックごとにラベルを付与する。ブロックとラベルは１対１に対応する。ラベルの値は、そのラベルに対応するブロックよりも左にある全てのビットのうち、１になっているビットの個数である。各ブロックのサイズをＢビットとする。図１０ではＢ＝４である。【００６７】
ラベルの値は（式２）を用いて求められる。【００６８】
【数２】
2008102474.tif 000004
ここで、ビットマップ２０の左から（Ｘ＋１）番目のブロックに対応するラベルの値を、ＬＡＢＥＬ（Ｘ）で表す。ＬＡＢＥＬ（０）＝０である。ＬＡＢＥＬ（Ｘ）（０≦Ｘ≦（状態数−２＋Ｂ÷２）÷Ｂ（小数点以下切り捨て））を、ラベルテーブル２１と呼ぶ。【００６９】
その後、ステップ１０４にて、全ての入力記号について独立にステップ１０２およびステップ１０３を実行する。その結果、ビットマップ２０とラベルテーブル２１と遷移先テーブル２２とは、入力記号１つにつき１つずつ作られる。【００７０】
その後、ステップ１０４で得られた全てのビットマップ２０とラベルテーブル２１と遷移先テーブル２２とを、ステップ１０５にて、メモリに格納する。【００７１】
以上、状態遷移表１０が与えられたとき、その情報量を削減する方法について述べた。【００７２】
次に、ビットマップ２０とラベルテーブル２１と遷移先テーブル２２とを用いて状態遷移する方法について説明する。【００７３】
図１１は、現在の状態と入力記号とが与えられている場合、次の状態（＝遷移先）を求める手順を説明するためのフローチャートである。ｓを現在の状態とする。【００７４】
まず、ステップ３００にて、ｓを初期状態、すなわち、０に初期化する。【００７５】
初期化後、ステップ３０１にて、入力を待ち、ステップ３０２にて、入力記号に対応するビットマップ２０とラベルテーブル２１と遷移先テーブル２２とをメモリから取得する。【００７６】
そして、ステップ３０３にて、ビットマップ２０とラベルテーブル２１とを用いて、現在の状態”ｓ”に対応する遷移先テーブル２２のインデックスを求める。【００７７】
ここで、順を追って説明するため、はじめに、ラベルテーブル２１を用いずにビットマップ２０のみを参照して、遷移先テーブル２２のインデックスを求める方法を述べる。【００７８】
現在の状態”ｓ”に対応する遷移先テーブル２２のインデックスは、単純な計算式である（式３）で与えられる。【００７９】
【数３】
2008102474.tif 000005
ただし、（式３）には次のような問題がある。【００８０】
（式３）は、ビットマップ２０の一部分に含まれるビット”１”の個数を計数するものである。前述の通り、ビットマップ２０のサイズは、状態数から１を減じた数に等しいビット数である。従って、もし状態数が１００００であった場合、（式３）は平均して４９９９．５回の加算を必要とする。【００８１】
ゆえに、状態数が多い場合、（式３）は、計算速度の点で実用に耐えない。【００８２】
この問題を解決するため、ビットマップ２０とラベルテーブル２１とを併用して、ビット”１”の計数回数を大幅に減少させる。【００８３】
具体的には、ビットマップ２０の状態”０”に対応するビットから状態”ｓ−１”に対応するビットまでの全てのビット値を累計するのではなく、現在の状態”ｓ”に位置的に最も近いラベルからの差分を計算し、そのラベルの値と差分とを加算または減算して、遷移先テーブル２２のインデックスを求める。【００８４】
まず、基準となるラベルを現在の状態”ｓ”から決定する。基準となるラベルは、ｓから見て最も近い位置にあるラベルである。基準となるラベルがラベルテーブル２１の（ｎ＋１）番目の要素であるとする。このとき単純に、ｎ＝ｓ÷Ｂ（小数点以下切り捨て）にならないことに注意する。【００８５】
図１２は、基準となるラベルを現在の状態”ｓ”から決定する方法を模式化した図である。【００８６】
図１２に示すように、現在の状態”ｓ”がブロックの左半分に属している場合、そのブロックに対応するラベルが基準になる。【００８７】
一方、現在の状態”ｓ”がブロックの右半分に属している場合、そのブロックの１つ右のブロックに対応するラベルが基準になる。【００８８】
従って、ラベルテーブル２１のインデックス”ｎ”を現在の状態”ｓ”から求める式は、（式４）のようになる。【００８９】
【数４】
2008102474.tif 000006
次に、基準となるラベルからの差分をビットマップ２０から求める。【００９０】
現在の状態”ｓ”がブロックの左半分に属している場合、ＬＡＢＥＬ（ｎ）に不足分を加えた数値を遷移先テーブル２２のインデックスとする。不足分は、状態”ｓ”が属するブロックの左端のビットから、状態”ｓ−１”に対応するビットまでのうち、値が１であるビットの個数である。この不足分が、前述した「差分」である。【００９１】
一方、現在の状態”ｓ”がブロックの右半分に属している場合、ＬＡＢＥＬ（ｎ）から余剰分を引いた数値を遷移先テーブル２２のインデックスとする。余剰分は、状態”ｓ”が属するブロックの右端のビットから、状態”ｓ”  に対応するビットまでのうち、値が１であるビットの個数である。この余剰分が、前述した「差分」である。【００９２】
上述の、遷移先テーブル２２のインデックスを算出する過程を数式で表現すると、（式５）のようになる。【００９３】
【数５】
2008102474.tif 000007
ラベルテーブル２１を使用することによって、本ステップ内の加算回数の期待値は、（（状態数−１）÷２）回から（Ｂ÷４）回に減少する。【００９４】
その後、ステップ３０３で求まったインデックスが指し示す遷移先テーブル２２の内容をステップ３０４にてｓに代入する。ここでは、ｓが遷移先、すなわち、次の状態になる。【００９５】
例えば、図９に示した遷移先テーブル２２を例に挙げると、ステップ３０３で求まったインデックスが１であれば、次の状態は９になる。【００９６】
その後、ステップ３０１へ戻る。【００９７】
以上により、本発明によれば、パターンマッチングのための状態遷移図もしくは状態遷移表において、入力が等しければ複数の状態から同一の状態へ遷移することが多いという性質に着目し、列方向に現在の状態、行方向に入力記号が配列された状態遷移表の、隣接する列の遷移先の値が互いに最も近い値になるように状態遷移表を列単位に並び替えて水平方向に同一の値が連続しやすくし、各列の現在の状態が昇順に並ぶように状態名を付け替えたあと、値の不連続点を表すビットマップと、連続値を１つに集約した遷移先テーブルを行ごとに作成することによって、状態遷移表の情報量を削減することができる。【００９８】
また、本発明によれば、ビットマップの一定間隔ごとにビットマップの最初のビットからそこまでのビット値の累計が記録されたラベルをあらかじめ作成しておき、ビットマップと遷移先テーブルを用いて状態遷移する際、ビットマップの最初のビットから現在の状態に対応するビットまでのビット値を累計する代わりに、現在の状態に位置的に最も近いラベルとそのラベルからの差分を求め、そのラベルの値と差分とを加算または減算して、遷移先テーブルのインデックスを算出し、そのインデックスが指し示す遷移先を次の状態とする状態遷移方法を採ることにより、状態遷移表の情報量を削減したことによる状態遷移の速度低下を抑えることができる。【００９９】
なお、本発明においては、上述した機能を実現するためのプログラムをコンピュータにて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行するものであっても良い。コンピュータにて読取可能な記録媒体とは、フロッピーディスク（登録商標）、光磁気ディスク、ＤＶＤ、ＣＤなどの移設可能な記録媒体の他、コンピュータに内蔵されたＨＤＤ等を指す。この記録媒体に記録されたプログラムは、例えば、コンピュータが有する制御部（不図示）にて読み込まれ、制御部の制御によって、上述したものと同様の処理が行われる。【０１００】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１０１】
この出願は、２００７年２月２０日に出願された日本出願特願２００７−０３９２０９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2008102474.tif 000008
【図２】
2008102474.tif 000009
【図３】
2008102474.tif 000010
【図４】
2008102474.tif 000011
【図５】
2008102474.tif 000012
【図６】
2008102474.tif 000013
【図７】
2008102474.tif 000014
【図８】
2008102474.tif 000015
【図９】
2008102474.tif 000016
【図１０】
2008102474.tif 000017
【図１１】
2008102474.tif 000018
【図１２】
2008102474.tif 000019
【国際調査報告】
2008102474.tif 000020
2008102474.tif 000021