以下に、本発明の実施の形態について図� ��を参照して説明する。

 本発明は、パターンマッチングのための� ��態遷移図もしくは状態遷移表において、入� ��が等しければ複数の状態から同一の状態へ� ��移することが多い、という性質を利用して� ��状態遷移表の情報量を削減する。

 図3に示した状態遷移表10の一例を用いて� ��その性質を明らかにする。図3に示した状態 遷移表10は、背景技術の説明で使用されたも� ��である。

 図3に示した状態遷移表10について、隣接� ��る列の遷移先の値が互いに最も近い値にな� ��ように列を並び替えると、その性質が顕在� ��する。

 図4は、図3に示した状態遷移表10を並び替 えた後の状態遷移表を示す図である。

 図4に示すように、並び替え後の状態遷移 表11は、水平方向に同一の値(遷移先)が連続� �ている箇所が多いことが分かる。この性質� �基づいて状態遷移表10の情報量を削減する手 順について説明する。

 図5は、図3に示した状態遷移表10の情報量 を削減する手順を説明するためのフローチャ ートである。

 まず、状態遷移表10の隣接する列の遷移� �の値が互いに最も近い値になるように、ス� �ップ100にて、状態遷移表10を列単位に並び替 える。なお、状態遷移表10は、列方向に現在� ��状態、行方向に入力記号が配列された形式� ��とる。行と列が反転した状態遷移表を用い� ��場合は、それを転置(90度回転)するか、もし くは、文中の「行」と「列」の単語を読み替 える。本ステップの主な目的は、状態遷移表 10の各列が、並び替え後の状態遷移表11のど� �列に移動するかの対応関係を表すテーブル� �作成することである。このテーブルをREPLACE( ・)と呼ぶ。

 状態遷移表10の、ある列の現在の状態を� �s”としたとき、REPLACE(s)は並び替え後の状態 遷移表11における、sに対応する列の位置を示 す。列の位置は、並び替え後の状態遷移表11� ��左から順に0、1、2、…、のように採番され� ��。

 例えば、図3に示した状態遷移表10の現在� ��状態”4”に対応する列が、並び替え後の状 態遷移表11の左から2番目の列に移動するとき 、REPLACE(4)=1になる。

 なお、REPLACE(・)はステップ100と後述のス� ��ップ101とで用いられるテンポラリな配列で� ��って、最終的にはメモリに格納されない。

 ここで、状態遷移を2次元配列g(s,a)で表す 。g(s,a)は、現在の状態が”s”であるときに� �力”a”が与えられたときの遷移先(=次の状� �)である。

 また、並び替えの際の指標として、2つの 列の間の類似度を定義する。状態”s”と状� �”t”との間の類似度は、(式1)で算出される� ��

 類似度の値が大きいほど、それら2つの状態 に対応する列の内容が互いに似通っているこ とになる。

 図6は、図5に示したステップ100の処理の� �細を説明するためのフローチャートである� �

 ステップ200にて、状態遷移表10における� �状態の集合をU、初期状態をsにそれぞれ代入 し、列の位置”i”を0に初期化する。

 ステップ201にて、状態”s”の移動先の列 の位置”i”をREPLACE(s)に記録したあと、ステ� ��プ202にて、列の位置”i”をインクリメント して、Uから状態”s”を取り除く。その後、� ��テップ203にて、Uが空集合であるか判定する 。

 空集合であればステップ100の処理は終了� ��る。

 一方、空集合でなければ、ステップ204に� ��、状態”s”と状態”t”との間の類似度を� �大化するような、t∈Uを1つ求める。この類� �度は、上述した(式1)に従って算出される。

 その後、ステップ205にて、tをsに代入し� �ステップ201へ戻る。

 図6のフローチャートから明らかなように 、REPLACE(初期状態)=0である。すなわち、初期� ��態に対応する列は、並び替え後の状態遷移� ��11の最左列に移動する。

 図3に示した状態遷移表10の一例を、上述� ��たステップの手順に従って並び替えると、� ��4に示した並び替え後の状態遷移表11が得ら� ��る。

 図7は、図5に示したステップ100が実行さ� �た後のREPLACE(・)の内容を示す図である。

 図7に示すように並び替え後の状態遷移表 11は、状態”s”とREPLACE(s)とが対応付けられ� �いるものである。

 その後、ステップ101にて、並び替え後の� ��態遷移表11において、現在の状態が最左列� �ら順に0、1、2、…、と昇順に並ぶように状� �名を付け替える。

 図8は、状態名付け替え後の状態遷移表の 一例を示す図である。

 図8に示すように状態名付け替え後の状態 遷移表12においては、並び替え後の状態遷移� ��11にて、ある現在の状態”s”が左から(X+1)� �目の列に配置されていたとき、その状態”s� ��の新しい状態名をXにする。状態”s”の移� �先の列の位置はREPLACE(s)であるから、状態”s ”の新しい状態名はREPLACE(s)に等しい。

 状態名付け替え後の状態遷移表12が2次元配� ��g’(s、a)で表されるとすると、
g’(REPLACE(s)、a)=g(s、a) for ∀s∈全状態の集� �、∀a∈σ
の関係が成立する。なお、σは、全ての入力� ��号(テキスト検索の場合は文字)の集合であ� �。例えば、σ={A、B、C}などである。

 また、REPLACE(初期状態)=0であるから、初� �状態の新しい状態名は0になる。その他の状� ��の新しい状態名は自然数である。

 その後、ステップ102にて、状態名付け替� ��後の状態遷移表12において、入力記号ごと� �、連続する同一の遷移先を1つにまとめた遷� ��先テーブルと、遷移先の変化点を表すビッ� ��マップを作成する。対象とする入力記号をa (a∈σ)とする。

 図9は、図5に示したステップ102にて作成� �れるビットマップ及び遷移先テーブルの一� �を示す図である。ここで、図8に示した状態� ��付け替え後の状態遷移表12の、入力記号”A� ��に対応するビットマップ20を例に挙げて示� �。

 図9に示したビットマップ20は、(状態数-1) ビット幅の1次元配列である。ビットマップ20 をBITMAP(x)(0≦x<状態数-1)と表現すると、g’( x、a)とg’(x+1、a)とが等しい場合BITMAP(x)=0であ り、そうでない場合はBITMAP(x)=1である。

 また、図9に示した遷移先テーブル22は、g ’(x、a)(0≦∀x<状態数)の中から連続する同 一の値を除去し、固有な値のみを残した配列 であり、図8に示した状態名付け替え後の状� �遷移表12の、入力記号”A”に対応する遷移� �テーブル22を例に挙げて示したものである。

 図9に示すように、連続する同一の遷移先 の情報が除去されているため、状態遷移表の 入力記号”A”に関する情報量が減少してい� �ことが分かる。

 そして、ステップ103にて、入力記号ごと� ��、ビットマップ20からラベルテーブルを作� �する。

 図10は、図9に示したビットマップ20から� �成されるラベルテーブルの一例を示す図で� �る。

 図10に示したラベルテーブル21は、状態遷 移を高速化するための補助情報として使用さ れる。ラベルテーブル21の使用方法は後述さ� ��る。

 図10に示すように、ビットマップ20を予め 設定された固定長のブロックに等分割し、ブ ロックごとにラベルを付与する。ブロックと ラベルは1対1に対応する。ラベルの値は、そ� ��ラベルに対応するブロックよりも左にある� ��てのビットのうち、1になっているビットの 個数である。各ブロックのサイズをBビット� �する。図10ではB=4である。

 ラベルの値は(式2)を用いて求められる。

 ここで、ビットマップ20の左から(X+1)番目の ブロックに対応するラベルの値を、LABEL(X)で� ��す。LABEL(0)=0である。LABEL(X)(0≦X≦(状態数-2+ Bí2)íB(小数点以下切り捨て))を、ラベルテー� ��ル21と呼ぶ。

 その後、ステップ104にて、全ての入力記� ��について独立にステップ102およびステップ1 03を実行する。その結果、ビットマップ20と� �ベルテーブル21と遷移先テーブル22とは、入� ��記号1つにつき1つずつ作られる。

 その後、ステップ104で得られた全てのビ� ��トマップ20とラベルテーブル21と遷移先テー ブル22とを、ステップ105にて、メモリに格納� ��る。

 以上、状態遷移表10が与えられたとき、� �の情報量を削減する方法について述べた。

 次に、ビットマップ20とラベルテーブル21 と遷移先テーブル22とを用いて状態遷移する� ��法について説明する。

 図11は、現在の状態と入力記号とが与え� �れている場合、次の状態(=遷移先)を求める� �順を説明するためのフローチャートである� �sを現在の状態とする。

 まず、ステップ300にて、sを初期状態、す なわち、0に初期化する。

 初期化後、ステップ301にて、入力を待ち� ��ステップ302にて、入力記号に対応するビッ� ��マップ20とラベルテーブル21と遷移先テーブ ル22とをメモリから取得する。

 そして、ステップ303にて、ビットマップ2 0とラベルテーブル21とを用いて、現在の状態 ”s”に対応する遷移先テーブル22のインデッ クスを求める。

 ここで、順を追って説明するため、はじ� ��に、ラベルテーブル21を用いずにビットマ� �プ20のみを参照して、遷移先テーブル22のイ� ��デックスを求める方法を述べる。

 現在の状態”s”に対応する遷移先テーブ ル22のインデックスは、単純な計算式である( 式3)で与えられる。

 ただし、(式3)には次のような問題がある。

 (式3)は、ビットマップ20の一部分に含ま� �るビット”1”の個数を計数するものである� ��前述の通り、ビットマップ20のサイズは、� �態数から1を減じた数に等しいビット数であ� ��。従って、もし状態数が10000であった場合� �(式3)は平均して4999.5回の加算を必要とする� �

 ゆえに、状態数が多い場合、(式3)は、計� ��速度の点で実用に耐えない。

 この問題を解決するため、ビットマップ2 0とラベルテーブル21とを併用して、ビット” 1”の計数回数を大幅に減少させる。

 具体的には、ビットマップ20の状態”0”� ��対応するビットから状態”s-1”に対応する� ��ットまでの全てのビット値を累計するので� ��なく、現在の状態”s”に位置的に最も近い ラベルからの差分を計算し、そのラベルの値 と差分とを加算または減算して、遷移先テー ブル22のインデックスを求める。

 まず、基準となるラベルを現在の状態”s ”から決定する。基準となるラベルは、sか� �見て最も近い位置にあるラベルである。基� �となるラベルがラベルテーブル21の(n+1)番目� ��要素であるとする。このとき単純に、n=síB( 小数点以下切り捨て)にならないことに注意� �る。

 図12は、基準となるラベルを現在の状態� �s”から決定する方法を模式化した図である� ��

 図12に示すように、現在の状態”s”がブ� ��ックの左半分に属している場合、そのブロ� ��クに対応するラベルが基準になる。

 一方、現在の状態”s”がブロックの右半 分に属している場合、そのブロックの1つ右� �ブロックに対応するラベルが基準になる。

 従って、ラベルテーブル21のインデック� �”n”を現在の状態”s”から求める式は、(� �4)のようになる。

 次に、基準となるラベルからの差分をビッ� ��マップ20から求める。

 現在の状態”s”がブロックの左半分に属 している場合、LABEL(n)に不足分を加えた数値� ��遷移先テーブル22のインデックスとする。� �足分は、状態”s”が属するブロックの左端� ��ビットから、状態”s-1”に対応するビット� ��でのうち、値が1であるビットの個数である 。この不足分が、前述した「差分」である。

 一方、現在の状態”s”がブロックの右半 分に属している場合、LABEL(n)から余剰分を引� ��た数値を遷移先テーブル22のインデックス� �する。余剰分は、状態”s”が属するブロッ� ��の右端のビットから、状態”s” に対応す� ��ビットまでのうち、値が1であるビットの個 数である。この余剰分が、前述した「差分」 である。

 上述の、遷移先テーブル22のインデック� �を算出する過程を数式で表現すると、(式5)� �ようになる。

 ラベルテーブル21を使用することによって� �本ステップ内の加算回数の期待値は、((状態 数-1)í2)回から(Bí4)回に減少する。

 その後、ステップ303で求まったインデッ� ��スが指し示す遷移先テーブル22の内容をス� �ップ304にてsに代入する。ここでは、sが遷移 先、すなわち、次の状態になる。

 例えば、図9に示した遷移先テーブル22を� ��に挙げると、ステップ303で求まったインデ� ��クスが1であれば、次の状態は9になる。

 その後、ステップ301へ戻る。

 以上により、本発明によれば、パターン� ��ッチングのための状態遷移図もしくは状態� ��移表において、入力が等しければ複数の状� ��から同一の状態へ遷移することが多いとい� ��性質に着目し、列方向に現在の状態、行方� ��に入力記号が配列された状態遷移表の、隣� ��する列の遷移先の値が互いに最も近い値に� ��るように状態遷移表を列単位に並び替えて� ��平方向に同一の値が連続しやすくし、各列� ��現在の状態が昇順に並ぶように状態名を付� ��替えたあと、値の不連続点を表すビットマ� ��プと、連続値を1つに集約した遷移先テーブ ルを行ごとに作成することによって、状態遷 移表の情報量を削減することができる。

 また、本発明によれば、ビットマップの� ��定間隔ごとにビットマップの最初のビット� ��らそこまでのビット値の累計が記録された� ��ベルをあらかじめ作成しておき、ビットマ� ��プと遷移先テーブルを用いて状態遷移する� ��、ビットマップの最初のビットから現在の� ��態に対応するビットまでのビット値を累計� ��る代わりに、現在の状態に位置的に最も近� ��ラベルとそのラベルからの差分を求め、そ� ��ラベルの値と差分とを加算または減算して� ��遷移先テーブルのインデックスを算出し、� ��のインデックスが指し示す遷移先を次の状� ��とする状態遷移方法を採ることにより、状� ��遷移表の情報量を削減したことによる状態� ��移の速度低下を抑えることができる。

 なお、本発明においては、上述した機能� ��実現するためのプログラムをコンピュータ� ��て読取可能な記録媒体に記録し、この記録� ��体に記録されたプログラムをコンピュータ� ��読み込ませ、実行するものであっても良い� ��コンピュータにて読取可能な記録媒体とは� ��フロッピーディスク(登録商標)、光磁気デ� �スク、DVD、CDなどの移設可能な記録媒体の他 、コンピュータに内蔵されたHDD等を指す。こ の記録媒体に記録されたプログラムは、例え ば、コンピュータが有する制御部(不図示)に� ��読み込まれ、制御部の制御によって、上述� ��たものと同様の処理が行われる。

 以上、実施の形態を参照して本願発明を� ��明したが、本願発明は上記実施の形態に限� ��されるものではない。本願発明の構成や詳� ��には、本願発明のスコープ内で当業者が理� ��し得る様々な変更をすることができる。

 この出願は、2007年2月20日に出願された日 本出願特願2007-039209を基礎とする優先権を主� ��し、その開示の全てをここに取り込む。