(57)【要約】  有限状態機械における状態遷移表を少ない情報量で記憶し検索する手法を提供する。複数の遷移先を複数の状態と複数の入力に対応させて表示する状態遷移表において、同一遷移先を有しかつ値が連続している入力を１つの集合として纏めることにより複数の入力を複数の集合とし、同一遷移先を共有する集合が互いに隣接するように複数の集合を整列させ、整列後の各集合に含まれる入力の下限値または上限値と重複のない遷移先を整列順にメモリに格納して状態遷移表の情報量を削減し、前記複数の状態と複数の入力のうち１つの状態と１つの入力が与えられたとき前記メモリを参照し該状態に対応する１つ以上の集合の下限値又は上限値と１つの遷移先を取得し、取得した下限値または上限値を入力の値と比較し比較結果に基づき前記与えられた入力が属する集合を特定し、特定された集合から遷移先を求め、遷移先を次の状態とする状態遷移表の情報記憶検索手法。
2008053762.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）複数の遷移先を複数の状態と複数の入力に対応させて表示する状態遷移表において、同一遷移先を有しかつ値が連続している入力を１つの集合として纏めることにより該複数の入力を複数の集合として構成し、
（ｂ）同一遷移先を共有する集合が互いに隣接するように前記複数の集合を整列させ、
（ｃ）整列後の各集合に含まれる入力の下限値または上限値と、重複のない遷移先を整列順にメモリに格納することにより前記状態遷移表の情報量を削減し、
（ｄ）前記複数の状態と複数の入力のうち１つの状態と１つの入力が与えられたとき前記メモリを参照し該状態に対応する１つ以上の集合の下限値または上限値と１つの遷移先を取得し、取得した下限値または上限値を入力の値と比較し該比較結果に基づき前記与えられた入力が属する集合を特定し、
（ｅ）該特定された集合から遷移先を求め、該遷移先を次の状態とすることを特徴とする状態遷移表の情報記憶検索方法。
【請求項２】
請求項１に記載の状態遷移表の情報記憶検索方法において、
前記（ａ）は前記状態遷移表の各入力について同一遷移先を有しかつ値が連続している複数の入力値を格納する複数のセルと該複数の入力値に対応する遷移先を格納する複数のセルからなる入力−遷移テーブルを生成し、
前記（ｂ）で前記入力−遷移テーブルから全てのセルを抽出し、これらのセルを入力の下限値または上限値別および遷移先別に配列させ集合−遷移先テーブルを生成し、さらに該集合−遷移先テーブル内で同一遷移先を共有する複数の行が互いに隣接するように整列させ整列後集合−遷移先テーブルを生成し、
前記（ｃ）は前記重複のない遷移先を該整列後集合−遷移先テーブルから求めることを特徴とする状態遷移表の情報記憶検索方法。
【請求項３】
請求項１に記載の状態遷移表の情報記憶検索方法において、前記（ｃ）で前記入力の下限値が前記メモリに格納された場合、前記（ｄ）は前記入力の値が前記取得した１つ以上の下限値の最小値と同等または大きい場合、該入力の値以下の１つ以上の下限値を選択し、該選択した下限値のうち最大の値を持つ集合を前記入力が属する集合として特定し、
前記入力の値が前記取得した１つ以上の下限値の最小値未満の場合、前記整列後集合−遷移先テーブル内で下限値が最小である集合を前記入力が属する集合として特定することを特徴とする状態遷移表の情報記憶検索方法。
【請求項４】
請求項１に記載の状態遷移表の情報記憶検索方法において、前記（ｃ）で前記入力の上限値が前記メモリに格納された場合、前記（ｄ）は前記入力の値が前記取得した１つ以上の上限値の最大値と同等または小さい場合、該入力の値以下の１つ以上の上限値を選択し、該選択した上限値のうち最小の値を持つ集合を前記入力が属する集合として特定し、
前記入力の値が前記取得した１つ以上の上限値の最大値より大きい場合、前記整列後集合−遷移先テーブル内で上限値が最大である集合を前記入力が属する集合として特定することを特徴とする状態遷移表の情報記憶検索方法。
【請求項５】
複数の遷移先を複数の状態と複数の入力に対応させて表示する状態遷移表において、同一遷移先を有しかつ値が連続している入力を１つの集合として纏めることにより該複数の入力を複数の集合として構成する構成手段と、
同一遷移先を共有する集合が互いに隣接するように前記複数の集合を整列させる整列手段と、
整列後の各集合に含まれる入力の下限値または上限値と重複のない遷移先を整列順にメモリに格納する格納手段と、
前記複数の状態と複数の入力のうち１つの状態と１つの入力が与えられたとき前記メモリを参照し該状態に対応する１つ以上の集合の下限値または上限値と１つの遷移先を取得し、取得した下限値または上限値を入力の値と比較し該比較結果に基づき前記与えられた入力が属する集合を特定する特定手段と、
該特定された集合から遷移先を次の状態とする遷移先決定手段とを具備することを特徴とする状態遷移表情報記憶検索装置。
【請求項６】
請求項５に記載の状態遷移表情報記憶検索装置において、
前記構成手段は前記状態遷移表の各入力について同一遷移先を有しかつ値が連続している複数の入力値を格納する複数のセルと該複数の入力値に対応する遷移先を格納する複数のセルからなる入力−遷移テーブルを生成し、
前記整列手段は前記入力−遷移テーブルから全てのセルを抽出し、これらのセルを入力の下限値または上限値別および遷移先別に配列させ集合−遷移先テーブルを生成し、さらに該集合−遷移先テーブル内で同一遷移先を共有する複数の行が互いに隣接するように整列させ整列後集合−遷移先テーブルを生成し、
前記格納手段は前記重複のない遷移先を該整列後集合−遷移先テーブルから求めることを特徴とする状態遷移表情報記憶検索装置。
【請求項７】
請求項５に記載の状態遷移表情報記憶検索装置において、前記格納手段が前記入力の下限値を前記メモリに格納した場合、前記特定手段は、前記入力の値が前記取得した１つ以上の下限値の最小値と同等または大きい場合、該入力の値以下の１つ以上の下限値を選択し、該選択した下限値のうち最大の値を持つ集合を前記入力が属する集合として特定し、
前記入力の値が前記取得した１つ以上の下限値の最小値未満の場合、前記整列後集合−遷移先テーブル内で下限値が最小である集合を前記入力が属する集合として特定することを特徴とする状態遷移表情報記憶検索装置。
【請求項８】
請求項６において、前記格納手段が前記入力の上限値を前記メモリに格納した場合、前記特定手段は、前記入力の値が前記取得した１つ以上の上限値の最大値と同等または小さい場合、該入力の値以下の１つ以上の上限値を選択し、該選択した上限値のうち最小の値を持つ集合を前記入力が属する集合として特定し、前記入力の値が前記取得した１つ以上の上限値の最大値より大きい場合、前記整列後集合−遷移先テーブル内で上限値が最大である集合を前記入力が属する集合として特定することを特徴とする。
【請求項９】
請求項１ないし４のいずれかの状態遷移表の情報記憶検索方法を実施するためのプログラム。
【請求項１０】
複数の遷移先を複数の状態と複数の入力に対応させて表示する状態遷移表を取り扱うコンピュータに実行させるプログラムであって、
（ａ）前記状態遷移表において、同一遷移先を有しかつ値が連続している入力を１つの集合として纏めることにより該複数の入力を複数の集合として構成し、
（ｂ）同一遷移先を共有する集合が互いに隣接するように前記複数の集合を整列し、
（ｃ）整列後の各集合に含まれる入力の下限値または上限値と、重複のない遷移先を整列順にメモリに格納することにより前記状態遷移表の情報量を削減し、
（ｄ）前記複数の状態と複数の入力のうち１つの状態と１つの入力が与えられたとき前記メモリを参照し該状態に対応する１つ以上の集合の下限値または上限値と１つの遷移先を取得し、取得した下限値または上限値を入力の値と比較し該比較結果に基づき前記与えられた入力が属する集合を特定し、
（ｅ）該特定された集合から遷移先を求め、該遷移先を次の状態とする、
状態遷移表の情報記憶検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）本願は、先の日本特許出願２００６−２９８０８８号（２００６年１１月１日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は有限状態機械に関し、特に状態遷移表の情報記憶検索方法と装置及びプログラムに関する。
【背景技術】
【０００２】
有限状態機械（Finite State Machine、別名：有限ステートマシン、有限オートマトン）は、機械制御や電子回路における順序回路だけでなく、コンピュータにおける計算モデル、情報検索、テキスト編集などの極めて広い分野で応用されている。有限状態機械を一般化して表現すると、図１のようになる。有限状態機械１の外界から供給される入力２と状態１４が定まっているとき、状態遷移メモリ１１に格納されている状態遷移表を参照し、次の状態として遷移先１２を求める。次に、出力表１３を参照し該遷移先に対応する出力３を得る。該出力は外界に作用し、その結果、新たな入力が有限状態機械１に与えられ、状態１４の内容が次の遷移先１２となる。【０００３】
図２は最も単純な表現形式の状態遷移表を示す。この状態遷移表は複数の入力（ａ，ｂ，ｃ，ｄ，ｅ，．．）と複数の状態（Ａ，Ｂ，Ｃ，Ｄ，．．）全ての組み合わせについて遷移先（Ａ−ａ，，，，Ｄ−ｅ，．．）を記述したものである。状態遷移表の情報量は入力が取り得る値の数と状態の数との積に正比例する。従って、入力が取り得る値の範囲が広かったり、状態数が多い場合は、状態遷移メモリ１１が大容量となりコストや消費電力、実装面積などの点で効率が低くなる。そこで、状態遷移表を少ない情報量で表現する方法に関して多くの研究がなされてきた。そのような従来の技術の１つとしてダブル配列法（非特許文献１）と呼ばれるダブル配列を用いて状態遷移表を表現する方法がある。【０００４】
図１１（ａ）、（ｂ）に示すようにダブル配列法は、例えば３つのパターン「ＡＢＣ」、「ＣＡ」,「ＣＣ」を一致判定する状態遷移図、前記状態遷移表、ＢＡＳＥおよびＣＨＥＣＫと呼ばれる２つの１次元配列の内容を示す配列表を使用する。ダブル配列法は図１１の（ｃ）の状態遷移表の中に遷移先１２が定義されていない要素が多く存在するという性質を利用して図１１の（ｃ）の状態遷移表の行を横方向にずらして重ね合わせることで、遷移先１２が定義されていない要素の数を減らすことができる。図１１の（ｃ）の状態遷移表に状態（ｓ）と入力（ｉ）が与えられたとき遷移先（ｔ）を決定するアルゴリズムは下記の通りである：
遷移先（ｔ）＝ＢＡＳＥ（状態（ｓ））＋入力（ｉ）
ただし、ＣＨＥＣＫ（ＢＡＳＥ（状態（ｓ））＋入力（ｉ））が状態（ｓ）と等しいとき状態遷移は成功し遷移先（ｔ）が定義され、等しくないとき状態遷移は失敗し遷移先（ｔ）は定義されない。【０００５】
具体的なＢＡＳＥ配列とＣＨＥＣＫ配列を用いて入力されたテキスト「ＡＢＣ」が受理される様子を示す。なお、文字Ａ，Ｂ，Ｃの内部表現値（数値）をそれぞれ１、２、３とする。【０００６】
先ず、状態（ｓ）の初期値は１であり、
（１）テキストの１番目の文字はＡであるから入力（ｉ）＝Ａ＝１、
（２）図１１（ｂ）の配列表からＢＡＳＥ（１）＝１、
（３）従って、遷移先（ｔ）＝ＢＡＳＥ（１）＋１＝２、
（４）また、図１１（ｂ）の配列表からＣＨＥＣＫ（２）＝１で状態（ｓ）＝１となるのでこの遷移は成功である。状態遷移図は状態１から遷移ラベルＡで状態２に遷移することを示している。【０００７】
次に、上記遷移の結果状態（ｓ）＝２のとき、
（１）テキストの２番目の文字はＢであるから入力（ｉ）＝Ｂ＝２、
（２）図１１（ｂ）の配列表からＢＡＳＥ（２）＝４
（３）従って、遷移先（ｔ）＝ＢＡＳＥ（２）＋２＝６、
（４）また、図１１（ｂ）の配列表からＣＨＥＣＫ（６）＝２＝状態（ｓ）であるからこの遷移は成功である。図１１（ａ）の状態遷移図は状態２から遷移ラベルＢで状態６に遷移することを示している。【０００８】
最後に、状態（ｓ）＝６において、
（１）テキストの３番目の文字はＣであるから入力（ｉ）＝Ｃ＝３、
（２）図１１（ｂ）の配列表からＢＡＳＥ（６）＝４、
（３）従って、遷移先（ｔ）＝ＢＡＳＥ（６）＋３＝７、
（４）また、図１１（ｂ）の配列表からＣＨＥＣＫ（７）＝６＝状態（ｓ）であるからこの遷移も成功である。状態遷移図は状態６から遷移ラベルＣで状態７に遷移することを示している。入力されたテキストの全ての文字について処理を完了し最後に得られた状態７は状態遷移図において末端であるからテキストＡＢＣは受理されたことになる。【０００９】
【非特許文献１】著者：青江 順一。題目：ダブル配列による有限状態機械の効率的インプリメンテーション。出典：電子情報通信学会論文誌Ｄ  Ｖｏｌ．Ｊ７０−Ｄ  Ｎｏ．４  ｐｐ．６５３−６６２  １９８７年４月
【発明の開示】
【発明が解決しようとする課題】
【００１０】
以下の分析は本発明により与えられる。
なお、上記非特許文献１の全開示内容はその引用をもって本書に繰込み記載する。
従来のダブル配列法は状態遷移表がスパース（sparse：疎）でないときは次の理由により状態遷移表の情報量を効率良く減少させることができない。即ち、ダブル配列法は状態遷移表に遷移先が定義されていない要素が多く存在するという性質を利用して情報量を削減する。言い換えれば状態遷移表が十分にスパースでなければ情報量をあまり減らすことができない。状態遷移表がスパースになりにくいアプリケーションとして、正規表現を含むパターンを探すテキスト検索が挙げられる。そのようなテキスト検索においては、アルファベット全て（Ａ〜Ｚ）や数字全て（０〜９）を一括して扱うことがある。この場合、状態遷移表は十分にスパースにならない。この現象を顕著に表す例を図１２（ａ）、（ｂ）に示す。【００１１】
図１２（ａ）は正規表現を含むパターン「Ａ〔Ａ−Ｚａ−ｚ０−９〕〔Ａ−Ｆ０−９〕」を一致判定する状態遷移図と状態遷移表を示す。ここで、〔Ａ−Ｚａ−ｚ０−９〕と〔Ａ−Ｆ０−９〕は文字クラス（Character class）と呼ばれる正規表現の一種である。〔Ａ−Ｚａ−ｚ０−９〕はアルファベットの大文字・小文字か数字のいずれか１文字を意味し、〔Ａ−Ｆ０−９〕は１６進数の１桁を意味する。従って、図１２（ｂ）に示す状態遷移表はテキストＡｚＣやＡ９０などを受理する。しかし、状態遷移表は現在状態Ｓ１とＳ２において複数の入力に対して遷移先が定義されているため、明らかにスパースではない。そのため、状態遷移表にダブル配列法を適用しても情報量の削減効果は小さい。【００１２】
本発明は、上述の問題点に鑑みてなされたものであり、その目的とするところは、有限状態機械における状態遷移表の大部分もしくは全ての要素で遷移先が定義されている場合であっても状態遷移表の情報量を削減する冗長性除去手段と、冗長性が除去された情報を用いて状態遷移を行う状態遷移手段を提供することである。
【課題を解決するための手段】
【００１３】
上記の目的を達成するため、第一の観点に基づく本発明の状態遷移表の情報記憶検索方法は（ａ）複数の遷移先を複数の状態と複数の入力に対応させて表示する状態遷移表において、同一遷移先を有しかつ値が連続している入力を１つの集合として纏めることにより該複数の入力を複数の集合として構成し、（ｂ）同一遷移先を共有する集合が互いに隣接するように前記複数の集合を整列させ、（ｃ）整列後の各集合に含まれる入力の下限値または上限値と、重複のない遷移先を整列順にメモリに格納することにより前記状態遷移表の情報量を削減し、（ｄ）前記複数の状態と複数の入力のうち１つの状態と１つの入力が与えられたとき前記メモリを参照し該状態に対応する１つ以上の集合の下限値または上限値と１つの遷移先を取得し、取得した下限値または上限値を入力の値と比較し該比較結果に基づき前記与えられた入力が属する集合を特定し、（ｅ）該特定された集合から遷移先を求め、該遷移先を次の状態とする状態遷移表の情報記憶検索方法及び該方法をコンピュータに実行させるためのプログラムが提供される。【００１４】
第二の観点に基づく本発明の状態遷移表情報記憶検索装置は複数の遷移先を複数の状態と複数の入力に対応させて表示する状態遷移表において、同一遷移先を有しかつ値が連続している入力を１つの集合として纏めることにより該複数の入力を複数の集合として構成する構成手段、同一遷移先を共有する集合が互いに隣接するように前記複数の集合を整列させる整列手段、整列後の各集合に含まれる入力の下限値または上限値と、重複のない遷移先を整列順にメモリに格納する格納手段を具備することにより前記状態遷移表の情報量を削減し、前記複数の状態と複数の入力のうち１つの状態と１つの入力が与えられたとき前記メモリを参照し該状態に対応する１つ以上の集合の下限値または上限値と１つの遷移先を取得し、取得した下限値または上限値を入力の値と比較し該比較結果に基づき前記与えられた入力が属する集合を特定する特定手段と、該特定された集合から遷移先を次の状態とする遷移先決定手段と、を具備する状態遷移表情報記憶検索装置が提供される。
【発明の効果】
【００１５】
本発明によれば、状態遷移表の中の状態それぞれについて、入力に対応する遷移先が共通であって、かつ値が連続している入力の集合を１つ以上構成し、各集合に含まれる入力の最小値または最大値のいずれかを集合の位置を示す情報としてメモリに記録するため、状態遷移表が疎でなくても状態遷移表の情報量を減少させ、状態遷移表を格納するためのメモリの量を削減することができる。【００１６】
また、本発明によれば、状態遷移表の中の状態それぞれについて、入力に対応する遷移先が共通であって、かつ値が連続している入力の集合を１つ以上構成し、同一遷移先を共有する集合の遷移先をキーとしてこれらの集合が隣接するように整列させることにより重複のない遷移先をメモリに記録するため、入力は異なるが遷移先が同一である要素が状態遷移表の中に存在している場合に、状態遷移表の情報量を減少させ、状態遷移表を格納するためのメモリの量を削減することができる。
【図面の簡単な説明】
【００１７】
【図１】一般化された有限状態機械を示す図。
【図２】最も単純に表現された状態遷移表を示す図。
【図３】入力−遷移先テーブルの情報量を削減する手順を示すフローチャート。
【図４】図３のフローチャートをプログラム的に表現したアルゴリズムを示す図。
【図５】状態遷移表の中の状態の１つについて入力と遷移先との関係を記した入力−遷移先テーブルを示す図。
【図６】入力−遷移先テーブルに存在する１つ以上の区間とその区間の遷移先との対応関係を示す区間−遷移先テーブルを示す図。
【図７】整列後の区間−遷移先テーブル、重複のない遷移先セル、区切りフラグのセルを示す図。
【図８】区間の個数セル、整列後の区間下限値セル、区切りフラグのセル、重複のない遷移先セルが状態遷移メモリに収められる過程を表す図。
【図９】状態遷移メモリに収められている情報を用いて入力に対応する遷移先を求める手順を示すフローチャート。
【図１０】図９のフローチャートをプログラム的に表現したアルゴリズムを示す図。
【図１１】従来技術のダブル配列法を説明する図。
【図１２】従来技術のダブル配列法の問題点を顕著に示す図。
【符号の説明】
【００１８】
１…有限状態機械
２…入力
３…出力
１０…状態遷移表
１１…状態遷移メモリ
１２…遷移先
１３…出力表
１４…状態
１００…入力−遷移先テーブル
１０１…区間−遷移先テーブル
１０２…整列後の区間−遷移先テーブル
１０５…区間の個数セル
１１０…区間下限値セル
１１１…区間上限値セル
１１２…区間遷移先セル
１２０…整列後の区間下限値セル
１２１…整列後の区間上限値セル
１２２…整列後の区間の遷移先セル
１３０…区切りフラグのセル
１３１…重複のない遷移先セル
【発明を実施するための最良の形態】
【００１９】
以下に、本発明の種々の展開可能形態を示す。
（形態１）
本発明の第１の視点によれば、
（ａ）複数の遷移先を複数の状態と複数の入力に対応させて表示する状態遷移表において、同一遷移先を有しかつ値が連続している入力を１つの集合として纏めることにより該複数の入力を複数の集合として構成し、
（ｂ）同一遷移先を共有する集合が互いに隣接するように前記複数の集合を整列させ、
（ｃ）整列後の各集合に含まれる入力の下限値または上限値と、重複のない遷移先を整列順にメモリに格納することにより前記状態遷移表の情報量を削減し、
（ｄ）前記複数の状態と複数の入力のうち１つの状態と１つの入力が与えられたとき前記メモリを参照し該状態に対応する１つ以上の集合の下限値または上限値と１つの遷移先を取得し、取得した下限値または上限値を入力の値と比較し該比較結果に基づき前記与えられた入力が属する集合を特定し、
（ｅ）該特定された集合から遷移先を求め、該遷移先を次の状態とすることを特徴とする状態遷移表の情報記憶検索方法を実施することができる。
（形態２）
前記（ａ）は前記状態遷移表の各入力について同一遷移先を有しかつ値が連続している複数の入力値を格納する複数のセルと該複数の入力値に対応する遷移先を格納する複数のセルからなる入力−遷移テーブルを生成し、
前記（ｂ）で前記入力−遷移テーブルから全てのセルを抽出し、これらのセルを入力の下限値または上限値別および遷移先別に配列させ集合−遷移先テーブルを生成し、さらに該集合−遷移先テーブル内で同一遷移先を共有する複数の行が互いに隣接するように整列させ整列後集合−遷移先テーブルを生成し、
前記（ｃ）は前記重複のない遷移先を該整列後集合−遷移先テーブルから求めるものとすることができる。
（形態３）
また、前記（ｃ）で前記入力の下限値が前記メモリに格納された場合、前記（ｄ）は前記入力の値が前記取得した１つ以上の下限値の最小値と同等または大きい場合、該入力の値以下の１つ以上の下限値を選択し、該選択した下限値のうち最大の値を持つ集合を前記入力が属する集合として特定し、
前記入力の値が前記取得した１つ以上の下限値の最小値未満の場合、前記整列後集合−遷移先テーブル内で下限値が最小である集合を前記入力が属する集合として特定するものとすることができる。
（形態４）
更には、前記（ｃ）で前記入力の上限値が前記メモリに格納された場合、前記（ｄ）は前記入力の値が前記取得した１つ以上の上限値の最大値と同等または小さい場合、該入力の値以下の１つ以上の上限値を選択し、該選択した上限値のうち最小の値を持つ集合を前記入力が属する集合として特定し、
前記入力の値が前記取得した１つ以上の上限値の最大値より大きい場合、前記整列後集合−遷移先テーブル内で上限値が最大である集合を前記入力が属する集合として特定するものとすることができる。
（その他の形態）
また、本発明に係る状態遷移表情報記憶検索装置及びプログラムにおいても、上記した各状態遷移表の情報記憶検索方法の形態と同様の展開を行うことが可能である。
本発明の実施の形態について図面を参照して詳細に説明する。状態遷移表の情報量を削減する方法と削減後の情報を使って状態遷移を行う方法に図３のフローチャートを参照する。先ず、ステップ２１で状態遷移表から入力（ｉ）に関する入力−遷移テーブル１００を図５に示すように作成する。図５（ａ）はその一般的方法を、図５（ｂ）は具体例を示す。図５において入力−遷移先テーブル１００は図１２の状態遷移表が示す１つの状態について入力（ｉ）とその遷移先との関係を記した表であり、状態遷移表（図１２）の一部分である。記号ＭＩＮ＿ＩＮＰＵＴは入力が取り得る値の最小値であり、ＭＡＸ＿ＩＮＰＵＴは最大値である。また、記号ｇ（Ｘ）は入力Ｘに対応する遷移先を表す。【００２０】
図４は図３の主なステップに対応しプログラムとして表現したアルゴリズムを示す。入力−遷移先テーブル１００の情報量を削減する手順は、図４のステップＡ２２〜Ａ２４からなる。【００２１】
次に、図３のステップ２２で入力−遷移先テーブル１００から各列を左から順に抽出し、区間下限値、区間上限値、区間遷移先別に上から順に配列し図６に示す区間−遷移先テーブル１０１を生成する。区間とは入力−遷移先テーブル１００において同一の遷移先を持ち、かつ、連続番号になっている入力の集合である。【００２２】
以下、区間の定義を示す：
（１）入力−遷移先テーブル１００において少なくとも１つの入力の集合である、
（２）１つの区間に属する全ての入力は同一の遷移先を共有する、
（３）１つの区間に属する全ての入力が連続番号である、
（４）上記を満たす入力集合のうち大きさが最大のものを区間とする、
各区間はその性質によりその区間に属する入力の下限値と上限値によって一意に識別される。区間−遷移先テーブル１０１は入力−遷移先テーブル１００に存在する１つ以上の区間とその区間の遷移先との対応関係を示す。この区間−遷移先テーブル１０１において区間に属する入力の最小値を区間の下限値ＬＯＷＥＲ（０）〜ＬＯＷＥＲ（Ｎ−１）とし、ある区間に属する入力の最大値をその区間の上限値ＵＰＰＥＲ（０）〜ＵＰＰＥＲ（Ｎ−１）とする。さらに、ある区間の遷移先をその区間遷移先ＮＥＸＴ（０）〜ＮＥＸＴ（Ｎ−１）とする。ここでＮは、図５の入力−遷移先テーブル１００に存在する区間の数である。なお、１番目の区間の下限値ＬＯＷＥＲ（０）はＭＩＮ＿ＩＮＰＵＴに等しく、Ｎ番目の区間の上限値ＵＰＰＥＲ（Ｎ−１）はＭＡＸ＿ＩＮＰＵＴに等しい。【００２３】
このステップ２２に対応する図４のアルゴリズムＡ２２で使われている変数は以下の定義に従う：
（Ａ）ＬＯＷＥＲ（Ｘ）＝テーブル１０１の区間下限値セル１１０−（Ｘ＋１）、
（Ｂ）ＵＰＰＥＲ（Ｘ）＝テーブル１０１の区間上限値セル１１１−（Ｘ＋１）、
ＮＥＸＴ（Ｘ）＝テーブル１０１の区間遷移先セル１１２−（Ｘ＋１）。【００２４】
次に、ステップ２３において区間−遷移先テーブル１０１内で区間遷移先セルの内容をキーとして同一遷移先を共有する複数の行が互いに隣接するよう整列させる。図７は整列後の区間−遷移先テーブル１０２を示す。【００２５】
後述のステップ２５で区間下限値を状態遷移メモリ１１に格納する場合、ステップ２３において下記の変数の定義に基づき整列条件１と２が成立するようにする：
（変数の定義）
（１）ＬＯＷＥＲ＊（Ｘ）＝区間下限値セル１２０−（Ｘ＋１）、
（２）ＵＰＰＥＲ＊（Ｘ）＝区間上限値セル１２１−（Ｘ＋１）、
（３）ＮＥＸＴ＊（Ｘ）＝区間遷移先セル１２２−（Ｘ＋１）。
（整列条件１）
ＬＯＷＥＲ＊（０）＝ＬＯＷＥＲ（０）、
ＵＰＰＥＲ＊（０）＝ＵＰＰＥＲ（０）、
ＮＥＸＴ＊（０）＝ＮＥＸＴ（０）。
（整列条件２）
ＮＥＸＴ＊（Ｘ）＝ＮＥＸＴ＊（Ｙ）を満たす全てのＸ、Ｙ（０≦Ｘ＜Ｙ＜Ｎ）の組み合わせについてＮＥＸＴ＊（Ｚ）＝ＮＥＸＴ＊（Ｘ）、Ｘ＜∀Ｚ＜Ｙ。【００２６】
換言すると、整列条件１は「整列の前後で区間−遷移先テーブル１０１の１行目の内容は不変でなければならない」ということであり、整列条件２は「整列後のテーブル１０２の区間遷移先セル１２２−１〜１２２−Ｎにおいて等しい値同士が隣接しなければならない」ということである。【００２７】
公知の整列アルゴリズム（バブルソート法、ヒープソート法、クイックソート法、マージソート法など）をそのまま適用した場合上記の整列条件２は満たされるが整列条件１は満たされない。そこで、公知の整列アルゴリズムを利用可能にするため、整列条件１が成立するように区間遷移先セル１１２−１〜１１２−Ｎに対して、整列前に以下の変更を加える：「０≦Ｘ＜Ｎについて、ＮＥＸＴ（Ｘ）とＮＥＸＴ（０）が等しければ、ＮＥＸＴ（Ｘ）←マイナス∞」。この変更を行った後に公知の整列アルゴリズムを用いて、区間遷移先セル１１２−１〜１１２−Ｎの遷移先をキーとして、同一遷移先を共有する複数の行が隣接するように整列させる。上記の変更によってマイナス∞に書き換えられた区間の遷移先セル１１２−１が属する行は他の行に移動しない。従って整列条件１が満たされる。【００２８】
一方、後述のステップ２５で区間上限値を状態遷移メモリ１１に格納する場合、ステップ２３における変数は下記の整列条件１と２が成立するようにするように定義される：
（整列条件１）
ＬＯＷＥＲ＊（Ｎ−１）＝ＬＯＷＥＲ（Ｎ−１）、
ＵＰＰＥＲ＊（Ｎ−１）＝ＵＰＰＥＲ（Ｎ−１）、
ＮＥＸＴ＊（Ｎ−１）＝ＮＥＸＴ（Ｎ−１）
（整列条件２）
ＮＥＸＴ＊（Ｘ）＝ＮＥＸＴ＊（Ｙ）を満たす全てのＸ、Ｙ（０≦Ｘ＜Ｙ＜Ｎ）の組み合わせについてＮＥＸＴ＊（Ｚ）＝ＮＥＸＴ＊（Ｘ）、Ｘ＜∀Ｚ＜Ｙ。【００２９】
換言すると、整列条件１は「整列の前後で区間−遷移先テーブル１０１の最終行目の内容は不変でなければならない」ということであり、整列条件２は「整列後のテーブル１０２の区間遷移先セル１２２−１〜１２２−Ｎにおいて等しい値同士が隣接しなければならない」ということである。【００３０】
公知の整列アルゴリズム（バブルソート法、ヒープソート法、クイックソート法、マージソート法など）をそのまま適用した場合上記の整列条件２は満たされるが整列条件１は満たされない。そこで、公知の整列アルゴリズムを利用可能にするため、整列条件１が成立するように区間遷移先セル１１２−１〜１１２−Ｎに対して、整列前に以下の変更を加える：「０≦Ｘ＜Ｎについて、ＮＥＸＴ（Ｘ）とＮＥＸＴ（Ｎ−１）が等しければ、ＮＥＸＴ（Ｘ）←プラス∞」。この変更を行った後に公知の整列アルゴリズムを用いて、 同一遷移先を共有する行が隣接するように整列させる。上記の変更によってプラス∞に書き換えられた区間の遷移先セル１１２−Ｎが属する行は他の行に移動しない。従って整列条件１が満たされる。【００３１】
次に、ステップ２４で整列後の区間−遷移先テーブル１０２から重複のない遷移先セル１３１−１〜１３１−Ｍと、区切り(separator)フラグのセル１３０−１〜１３０−Ｎを求める。ここでＭは整列後の区間の遷移先セル１２２−１〜１２２−Ｎに含まれる固有な値の個数である。例えば、図７（ｂ）の整列後の区間−遷移先テーブル１０２で、整列後の区間の遷移先セル１２２−１〜１２２−５はそれぞれＳ２、Ｓ２、Ｓ１、Ｓ１、Ｓ３であるが、このうちＳ１とＳ２は複数回出現しているから固有な値はＳ２、Ｓ１、Ｓ３の３つであり、Ｍ＝３となる。重複のない遷移先セル１３１−１〜１３１−Ｍは、整列後の区間の遷移先セル１２２−１〜１２２−Ｎから重複している値が取り除かれ、空いた要素が上詰めされた配列である。区切りフラグのセル１３０−１〜１３０−Ｎは０か１のいずれかの値をとり、整列後の区間の遷移先セル１２２−１〜１２２−Ｎにおける値の変化点を表す。具体的には、整列後の区間の遷移先セル１２２−Ｘと整列後の区間遷移先セル１２２−（Ｘ−１）が異なるとき、区切りフラグのセル１３０−Ｘ（２≦Ｘ＜Ｎ）は１をとり、等しければ値０をとる。区切りフラグのセル１３０−１は０に固定である。【００３２】
次に、ステップ２５で区間の個数セル１０５（値＝Ｎ）、整列後の区間の下限値セル１２０−２〜１２０−Ｎ（または区間上限値セル１２１−１〜１２１−（Ｎ−１））、区切りフラグのセル１３０−２〜１３０−Ｎ、重複のない遷移先セル１３１−１〜１３１−Ｍを図８に示すように状態遷移メモリ１１に格納する。ただし、区間下限値を格納した場合、整列後の区間上限値のセル１２１−１〜１２１−Ｎは整列後の区間下限値セル１２０−１〜１２０−Ｎから１を減じた値かＭＡＸ＿ＩＮＰＵＴに等しいため冗長な情報であり、そのため、状態遷移メモリ１１に格納されない。同様に、区間上限値を格納した場合、整列後の区間下限値のセル１２０−１〜１２０−Ｎは整列後の区間上限値セル１２１−１〜１２１−Ｎに１を加えた値かＭＩＮ＿ＩＮＰＵＴに等しいため冗長な情報であり、そのため、状態遷移メモリ１１に格納されない。【００３３】
また、ステップ２５で区間下限値をメモリ１１に格納した場合は、図８に示すように整列後の区間下限値セル１２０−１は必ずＭＩＮ＿ＩＮＰＵＴに等しく、区切りフラグのセル１３０−１は０に固定であるため、これらの情報を状態遷移メモリ１１に格納する必要はない。同様に、区間上限値をメモリ１１に格納した場合は、括弧内の値が示すように整列後の区間上限値セル１２１−Ｎは必ずＭＡＸ＿ＩＮＰＵＴに等しく、区切りフラグのセル１３０−１は０に固定であるため、これらの情報を状態遷移メモリ１１に格納する必要はない。【００３４】
以上、図５の入力−遷移先テーブル１００の情報量を１つの入力に関し削減する方法について述べた。この入力−遷移先テーブル１００は状態遷移表の１つの状態についてその入力と遷移先との関係を記しているので、ステップ２６において全入力に関し入力−遷移先テーブル１００が作成されたか否かを判定し、作成されていれば終了し、作成されていなければステップ２７で入力ポインター（ｉ）を１つインクリメントしステップ２１に戻り上述の過程を繰り返す。これにより状態遷移表全体の情報量が削減できる。【００３５】
次に、図９（ａ）、（ｂ）はある入力が状態遷移表に与えられたときその入力に対応する遷移先を図８の状態遷移メモリ１１を用いて求める方法を示す。なお、図９（ａ）は図３のステップ２５で区間下限値をメモリ１１に格納した場合、図９（ｂ）は区間上限値を格納した場合を示す。【００３６】
先ず、図９（ａ）において、ステップ３１−１で現在の状態に対応する区間の個数セル１０５の値Ｎと、整列後の区間下限値セル１２０−２〜１２０−Ｎと、区切りフラグのセル１３０−２〜１３０−Ｎと、重複のない遷移先セル１３１−１〜１３１−Ｍとを図８の状態遷移メモリ１１から読み出す。【００３７】
次に、ステップ３２−１で前記入力が属する区間（集合）を特定する。「入力値≧整列後のセル１２０−Ｘの区間下限値」を満たす全てのＸ（２≦∀Ｘ≦Ｎ）について、整列後のセル１２０−Ｘから区間下限値の最大値を求める。整列後のセル１２０−Ｙ（２≦∃Ｙ≦Ｎ）の区間下限値が最大値に等しいとき、前記入力は整列後の区間下限値セル１２０−Ｙを含む区間に属する。「入力値≧整列後のセル１２０−Ｘの区間下限値」を満たすＸ（２≦Ｘ≦Ｎ）が存在しないとき、前記入力は整列後の区間の下限値セル１２０−１を含む区間に属する。【００３８】
例えば、区間下限値セル１２０−Ｘ（２≦Ｘ≦５）の値はＸの値に対応し５、３、８、６の順に配列されており、入力値を７とすると、これらのうち７以下のものは５、３、６の３つである。５、３、６の最大値は６である。従って、前記入力値７に対し整列後の区間下限値セル１２０−５を含む区間が特定されたことになる。図５の入力−遷移先テーブル１００を参照すると入力値７は６以上７以下の区間に属することが分かる。なお、ステップ３２−１乃至３５−１に対応するアルゴリズムＡ３１−１を図１０に示す。ただし、このアルゴリズムが使用する変数ＳＥＣＴＩＯＮは入力が整列後の区間下限値セル１２０−（ＳＥＣＴＩＯＮ＋１）を含む区間に属することを意味する。【００３９】
即ち、ステップ３２−１で入力値が整列後区間下限値セル１２０−２乃至１２０−Ｎの最小値と同等または大きいと判断された場合、ステップ３３−１に進み入力値以下の整列後の区間下限値セル１２０の値を選択し、ステップ３４−１で選択した下限値のうち最大の値を持つ整列後の区間下限値セル１２０を前記入力が属する区間として特定する。【００４０】
また、ステップ３２−１で入力値が整列後区間下限値セル１２０−２乃至１２０−Ｎの下限値の最小値未満と判断された場合、ステップ３５−１に進み整列後区間下限値セル１２０−１を前記入力が属する区間として特定する。【００４１】
次に、ステップ３６に進み、ステップ３４−１または３５−１で特定された区間下限値セルを含む区間に対応し、かつ重複のない遷移先セル１３１−１〜１３１−Ｍのインデックス（＝対応する区切りフラグの総和）を求め、そのインデックスが示す内容を遷移先とする。即ち、区切りフラグのセル１３０−２〜１３０−（ＳＥＣＴＩＯＮ＋１）の和を求め、その和をＩＮＤＥＸと表記する。このとき、前記入力が属する区間の遷移先は重複のない遷移先セル１３１−（ＩＮＤＥＸ＋１）である。即ち、入力値が７の場合、前記特定された区間は区間下限値セル１２０−５であるためＳＥＣＴＩＯＮ（区間番号）＝４である。そこで、区切りフラグのセル１３０−２〜１３０−（４＋１）の値の和を求めると、０＋１＋０＋１＝２＝ＩＮＤＥＸが得られる。従って、前記入力が属する区間の遷移先は重複のない遷移先セル１３１−（２＋１）、すなわちＳ３であることが分かる。図５の入力―状態テーブル１００を参照すると、入力値７に対応する遷移先はＳ３である。なお、ステップ３６に対応するアルゴリズムＡ３２を図１０に示す。【００４２】
次に、図９（ｂ）の場合、ステップ３１−２で現在の状態に対応する区間の個数セル１０５の値Ｎと、整列後の区間上限値セル１２１−１〜１２１−（Ｎ−１）と、区切りフラグのセル１３０−２〜１３０−Ｎと、重複のない遷移先セル１３１−１〜１３１−Ｍとを図８の状態遷移メモリ１１から読み出す。【００４３】
次に、ステップ３２−２で前記入力が属する区間（集合）を特定する。「入力値≦整列後のセル１２１−Ｘの区間上限値」を満たす全てのＸ（１≦∀Ｘ＜Ｎ）について、整列後のセル１２１−Ｘから区間上限値の最小値を求める。整列後のセル１２１−Ｙ（１≦∃Ｙ＜Ｎ）の区間上限値が最小値に等しいとき、前記入力は整列後の区間上限値セル１２１−Ｙを含む区間に属する。「入力値≦整列後のセル１２１−Ｘの区間上限値」を満たすＸ（１≦Ｘ＜Ｎ）が存在しないとき、前記入力は整列後の区間の上限値セル１２１−Ｎを含む区間に属する。【００４４】
例えば、区間上限値セル１２１−Ｘ（１≦Ｘ＜５）の値はＸの値に対応し２、５、７、４、の順に配列されており、入力値を３とすると、これらのうち３以上のものは５、７、４の３つである。５、７、４の最小値は４である。従って、前記入力値３に対し整列後の区間上限値セル１２１−４を含む区間が特定されたことになる。図５の入力−遷移先テーブル１００を参照すると入力値３は３以上４以下の区間に属することが分かる。なお、ステップ３２−２乃至３５−２に対応するアルゴリズムＡ３１−２を図１０に示す。ただし、このアルゴリズムが使用する変数ＳＥＣＴＩＯＮは入力が整列後の区間上限値セル１２１−（ＳＥＣＴＩＯＮ＋１）を含む区間に属することを意味する。【００４５】
即ち、ステップ３２−２で入力値が整列後区間上限値セル１２１−１乃至１２１−（Ｎ−１）の最大値と同等または小さいと判断された場合、ステップ３３−２に進み入力値以上の整列後の区間上限値セル１２１の値を選択し、ステップ３４−２で選択した上限値のうち最小の値を持つ整列後の区間上限値セル１２１を前記入力が属する区間として特定する。【００４６】
ステップ３２−２で入力値が整列後区間上限値セル１２１−１乃至１２１−（Ｎ−１）の最大値より大きいと判断された場合、ステップ３５−２に進み整列後区間上限値セル１２１−Ｎを前記入力が属する区間として特定する。
次に、ステップ３６に進み、ステップ３４−２または３５−２で特定された区間上限値セルを含む区間に対応し、かつ重複のない遷移先セル１３１−１〜１３１−Ｍのインデックス（＝対応する区切りフラグの総和）を求め、そのインデックスが示す内容を遷移先とする。即ち、区切りフラグのセル１３０−２〜１３０−（ＳＥＣＴＩＯＮ＋１）の和を求め、その和をＩＮＤＥＸと表記する。このとき、前記入力が属する区間の遷移先は重複のない遷移先セル１３１−（ＩＮＤＥＸ＋１）である。即ち、入力値が３の場合、前記特定された区間は区間上限値セル１２１−４であるためＳＥＣＴＩＯＮ（区間番号）＝３である。そこで、区切りフラグのセル１３０−２〜１３０−（３＋１）の値の和を求めると、０＋１＋１＝２＝ＩＮＤＥＸが得られる。従って、前記入力が属する区間の遷移先は重複のない遷移先セル１３１−（２＋１）、すなわちＳ１であることが分かる。図５の入力−遷移先テーブル１００を参照すると、入力値３に対応する遷移先はＳ１である。なお、ステップ３６に対応するアルゴリズムＡ３２を図１０に示す。【００４７】
次に、本実施例に記載されている方法によって状態遷移表（図１１の（ｃ）参照）の情報量が削減されることを定量的に示す。【００４８】
具体的には、状態遷移表の情報量と、削減された後の情報量を比較する。ただし、比較を容易にするため状態遷移表に存在する状態のうちの１つに着目する。【００４９】
始めに、それぞれの情報量を定式化する。
（削減される前の情報量）
状態遷移表の１つの状態の情報量＝入力−遷移先テーブル１００の情報量＝入力の種類の数×ｌｏｇ２（全状態数）ビットここで、入力の種類の数＝ＭＡＸ＿ＩＮＰＵＴ−ＭＩＮ＿ＩＮＰＵＴ＋１、である。
（削減された後の情報量）
・区間の個数１０５セルの値Ｎの情報量＝ｌｏｇ２（Ｎ）ビット
・整列後の区間の下限値セル１２０−２〜１２０−Ｎの情報量＝Ｎ×ｌｏｇ２（入力の種類の数）ビット
・区切りフラグのセル１３０−２〜１３０−Ｎの情報量＝Ｎ−１ビット
・重複のない遷移先セル１３１−１〜１３１−Ｍの情報量＝Ｍ×ｌｏｇ２（全状態数）ビットであるから、これらを合計するとｌｏｇ２（Ｎ）＋Ｎ×ｌｏｇ２（入力の種類の数）＋Ｎ−１＋Ｍ×ｌｏｇ２（全状態数）である。【００５０】
変数が多いため、全状態数と入力の種類の数を固定する。入力の種類の数を２５６に固定し、全状態数を６４にしたときと６５５３６にしたときの２通りについて、それぞれ比較する。【００５１】
まず、全状態数＝６４、入力の種類の数＝２５６とする。また、計算を容易にするため、Ｍ＝全状態数＝６４とする。【００５２】
このとき、区間の個数セル１０５の値Ｎが１２７以下であれば、入力−遷移先テーブル１００の情報量よりも、本実施例の方法によって削減された後の情報量の方が少ない（理由：上記の条件から不等式「１５３６＞ｌｏｇ２（Ｎ）＋Ｎ×９＋３８３」が導かれ、これを解くとＮ≦１２７が得られる）。【００５３】
一般的な状態遷移表において１つの状態からの平均遷移数が１２７を超える場合は極めて稀であるから、状態遷移表の情報量を削減するという点で、本実施例の方法は十分に効果的である。【００５４】
次に、全状態数＝６５５３６、入力の種類の数＝２５６とする。また、計算を容易にするため、区間の個数セル１０５の値ＮをＭとする。【００５５】
このとき、区間の個数１０５（Ｎ）が１６３以下であれば、入力−遷移先テーブル１００の情報量よりも、本実施例の方法によって削減された後の情報量の方が少ない（理由：上記の条件から不等式「４０９６＞ｌｏｇ２（Ｎ）＋Ｎ×２５−１」が導かれ、これを解くと、Ｎ≦１６３が得られる）。【００５６】
一般的な状態遷移表において１つの状態からの平均遷移数が１６３を超える場合は極めて稀であるから、状態遷移表の情報量を削減するという点で、本実施例の方法は十分に効果的である。
以上本発明の好適な実施形態について説明したが、本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。
【図１】
2008053762.tif 000003
【図２】
2008053762.tif 000004
【図３】
2008053762.tif 000005
【図４】
2008053762.tif 000006
【図５】
2008053762.tif 000007
【図６】
2008053762.tif 000008
【図７】
2008053762.tif 000009
【図８】
2008053762.tif 000010
【図９】
2008053762.tif 000011
【図１０】
2008053762.tif 000012
【図１１】
2008053762.tif 000013
【図１２】
2008053762.tif 000014
【国際調査報告】
2008053762.tif 000015
2008053762.tif 000016