(57)【特許請求の範囲】
【請求項１】
有限状態オートマトン又は当該有限状態オートマトンを拡張したオートマトンに関し、非決定性オートマトンの決定化を行うオートマトン決定化装置で実行されるオートマトンの決定化方法であって、
前記オートマトン決定化装置は記憶手段を備え、
部分決定化手段によって、前記非決定性オートマトンに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化工程と、
名称変更手段によって、前記決定化により前記記憶手段に記憶された前記非決定性オートマトンに含まれた何れかの状態の組み合わせからなる決定化済み状態の名称を、互いに異なる単一の名称に付け替える名称変更工程と、
繰り返し手段によって、前記非決定性オートマトンに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し実行させる繰り返し工程と、
を含み、
前記部分決定化工程は、前記繰り返し工程による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とするオートマトンの決定化方法。
【請求項２】
前記非決定性オートマトンに含まれた遷移に係る入力記号のうち、一部の入力記号を抽出した部分集合を、前記繰り返し回数に応じて順次生成する部分集合生成工程を更に含み、
前記部分決定化工程は、前記部分集合に含まれた入力記号に基づいて、当該入力記号に係る遷移を決定化対象とすることを特徴とする請求項１に記載のオートマトンの決定化方法。
【請求項３】
前記部分決定化工程は、
前記非決定性オートマトンに含まれた遷移のうち、決定化対象以外の遷移に係る入力記号を互いに異なる記号に置き換える置換工程と、
前記置換工程後の非決定性オートマトンを決定化し、決定性オートマトンを生成する決定化工程と、
前記決定性オートマトンに含まれる遷移のうち、前記置換工程で置き換えた入力記号を元の記号に戻す復元工程と、
を含み、
前記繰り返し工程は、前記非決定性オートマトンに含まれた全ての遷移について決定化が行われるまで、前記決定性オートマトンを非決定性オートマトンとして前記部分決定化工程に処理させることを特徴とする請求項１又は２に記載のオートマトンの決定化方法。
【請求項４】
前記部分決定化工程は、
前記非決定性オートマトンに含まれた遷移にかかる入力記号から、一の入力記号を処理対象として順次選択する入力記号選択工程と、
前記非決定性オートマトンに含まれた遷移のうち、前記処理対象の入力記号に係る遷移を抽出した遷移集合を生成する遷移集合抽出手段と、
前記遷移集合に含まれる遷移から、前記決定化対象とする遷移を選択する選択手段と、
を含むことを特徴とする請求項１又は２に記載のオートマトンの決定化方法。
【請求項５】
前記部分集合生成工程は、前記非決定性オートマトンに含まれた遷移に係る入力記号の種別に応じて、抽出する入力記号を選択することを特徴とする請求項２に記載のオートマトンの決定化方法。
【請求項６】
前記部分集合生成工程は、前記非決定性オートマトンに含まれた遷移に係る入力記号のうち、各入力記号に係る遷移の個数に応じて、抽出する入力記号を選択することを特徴とする請求項２又は５に記載のオートマトンの決定化方法。
【請求項７】
前記部分集合生成工程は、前記非決定性オートマトンに含まれた遷移に係る入力記号毎に、当該入力記号に係る遷移の個数と前記非決定性オートマトンに含まれた状態の数との和を、当該入力記号に係る遷移の遷移元の状態の数と前記非決定性オートマトンに含まれた状態の数との和で除算した値を夫々算出し、この算出した値に応じて、抽出する入力記号を選択することを特徴とする請求項６に記載のオートマトンの決定化方法。
【請求項８】
音声認識装置で用いられる重み付き有限状態トランスデューサに関し、非決定性有限状態トランスデューサの決定化を行うオートマトン決定化装置で実行される重み付き有限状態トランスデューサの決定化方法であって、
前記オートマトン決定化装置は記憶手段を備え、
部分決定化手段によって、前記非決定性有限状態トランスデューサに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化工程と、
名称変更手段によって、前記決定化により前記記憶手段に記憶された前記非決定性有限状態トランスデューサに含まれた何れかの状態又はそれを含む組の組み合わせからなる決定化済み状態の名称を、互いに異なる単一の名称に付け替える名称変更工程と、
繰り返し手段によって、前記非決定性有限状態トランスデューサに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し実行させる繰り返し工程と、
を含み、
前記部分決定化工程は、前記繰り返し工程による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とする有限状態トランスデューサの決定化方法。
【請求項９】
有限状態オートマトン又は当該有限状態オートマトンを拡張したオートマトンに関し、非決定性オートマトンを決定化するオートマトン決定化装置であって、
前記非決定性オートマトンに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化手段と、
前記決定化により生成された、前記非決定性オートマトンに含まれた何れかの状態の組み合わせからなる決定化済み状態を記憶する記憶手段と、
前記決定化済み状態の名称を互いに異なる単一の名称に付け替える名称変更手段と、
前記非決定性オートマトンに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し実行させる繰り返し手段と、
を備え、
前記部分決定化手段は、前記繰り返し工程による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とするオートマトン決定化装置。
【請求項１０】
有限状態オートマトン又は当該有限状態オートマトンを拡張したオートマトンに関し、非決定性オートマトンを決定化し、この決定化の際の作業エリアとして機能する記憶手段を備えたコンピュータに、
前記非決定性オートマトンに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化機能と、
前記決定化により前記記憶手段に記憶された前記非決定性オートマトンに含まれた何れかの状態の組み合わせからなる決定化済み状態の名称を、互いに異なる単一の名称に付け替える名称変更工程と、
前記非決定性オートマトンに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し行う繰り返し機能と、
を実現させ、
前記部分決定化機能は、前記繰り返し機能による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とするオートマトンの決定化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限状態オートマトン（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ａｕｔｏｍａｔｏｎ：ＦＳＡ）又はＦＳＡを拡張したオートマトン（有限状態トランスデューサ、重み付き有限状態オートマトン、重み付き有限状態トランスデューサ等）の決定化に関する。
【背景技術】
【０００２】
現在の状態からある入力によって遷移するときに、遷移先の状態が複数存在するようなＦＳＡは非決定性ＦＳＡと呼ばれている。また、現在の状態からある入力によって遷移するときに、遷移先の状態が１つのみであるようなＦＳＡは決定性ＦＳＡと呼ばれている。非決定性ＦＳＡを決定性ＦＳＡに変換することは「決定化」と呼ばれており、この決定化はサブセット構成法と呼ばれる方法によって実現できることが知られている（例えば、非特許文献１参照）。また、重み付き有限状態オートマトンや有限状態トランスデューサ、有限状態トランスデューサ等の有限状態オートマトンを拡張したオートマトンについても、非決定状態にあるオートマトン（非決定性オートマトン）から決定化する方法が提案されている（例えば、非特許文献２参照）。
【０００３】
【非特許文献１】Ｊ．ホップクロフト／Ｊ．ウルマン共著、「オートマトン言語理論  計算論Ｉ（第２版）」、サイエンス社
【非特許文献２】Finite-state  transducers  in  language  and  speech  processing,  Mehryar  Mohri,  Computational  Linguistics,  Volume  23,  Issue  2(June  1997)  Pages.269-311
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、決定化したい非決定性ＦＳＡや上述した非決定性オートマトンの規模が大きく複雑になると、従来の決定化の方法では、決定化の処理中に記憶しておかなければならない要素数が増加するため、決定化を実行するためのメモリ量が多量に必要となるという問題がある。
【０００５】
本発明は上記に鑑みてなされたものであって、決定化の実行時に要するメモリ量を減少させることが可能なオートマトンの決定化方法、有限状態トランスデューサの決定化方法、オートマトン決定化装置及びオートマトンの決定化プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明は、有限状態オートマトン又は当該有限状態オートマトンを拡張したオートマトンに関し、非決定性オートマトンの決定化を行うオートマトン決定化装置で実行されるオートマトンの決定化方法であって、前記オートマトン決定化装置は記憶手段を備え、部分決定化手段によって、前記非決定性オートマトンに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化工程と、名称変更手段によって、前記決定化により前記記憶手段に記憶された前記非決定性オートマトンに含まれた何れかの状態の組み合わせからなる決定化済み状態の名称を、互いに異なる単一の名称に付け替える名称変更工程と、繰り返し手段によって、前記非決定性オートマトンに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し実行させる繰り返し工程と、を含み、前記部分決定化工程は、前記繰り返し工程による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とする。
【０００７】
また、本発明は、音声認識装置で用いられる重み付き有限状態トランスデューサに関し、非決定性有限状態トランスデューサの決定化を行うオートマトン決定化装置で実行される重み付き有限状態トランスデューサの決定化方法であって、前記オートマトン決定化装置は記憶手段を備え、部分決定化手段によって、前記非決定性有限状態トランスデューサに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化工程と、名称変更手段によって、前記決定化により前記記憶手段に記憶された前記非決定性有限状態トランスデューサに含まれた何れかの状態又はそれを含む組の組み合わせからなる決定化済み状態の名称を、互いに異なる単一の名称に付け替える名称変更工程と、繰り返し手段によって、前記非決定性有限状態トランスデューサに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し実行させる繰り返し工程と、を含み、前記部分決定化工程は、前記繰り返し工程による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とする。
【０００８】
また、本発明は、有限状態オートマトン又は当該有限状態オートマトンを拡張したオートマトンに関し、非決定性オートマトンを決定化するオートマトン決定化装置であって、前記非決定性オートマトンに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化手段と、前記決定化により生成された、前記非決定性オートマトンに含まれた何れかの状態の組み合わせからなる決定化済み状態を記憶する記憶手段と、前記決定化済み状態の名称を互いに異なる単一の名称に付け替える名称変更手段と、前記非決定性オートマトンに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し実行させる繰り返し手段と、を備え、前記部分決定化手段は、前記繰り返し工程による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とする。
【０００９】
また、本発明は、有限状態オートマトン又は当該有限状態オートマトンを拡張したオートマトンに関し、非決定性オートマトンを決定化し、この決定化の際の作業エリアとして機能する記憶手段を備えたコンピュータで動作するプログラムであって、前記非決定性オートマトンに含まれた遷移のうち、決定化対象として選択した一部の遷移について決定化を行う部分決定化機能と、前記決定化により前記記憶手段に記憶された前記非決定性オートマトンに含まれた何れかの状態の組み合わせからなる決定化済み状態の名称を、互いに異なる単一の名称に付け替える名称変更工程と、前記非決定性オートマトンに含まれた全ての遷移について決定化が行われるまで、前記部分決定化工程を繰り返し行う繰り返し機能と、を実現させ、前記部分決定化機能は、前記繰り返し機能による繰り返し毎に、前記決定化対象として選択する遷移又は遷移の組みを異ならしめることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、非決定性オートマトンに含まれた遷移から、決定化の対象とする遷移を一部選び、この決定化対象とする遷移を毎回変えながら繰り返し決定化を行うことで、一回の決定化で記憶する決定化済み状態の名称のうち、それを構成する非決定性オートマトンに含まれた状態の延べ数を減少させることができるため、決定化の実行時に要するメモリ量を減少させることができる。
【発明を実施するための最良の形態】
【００１１】
以下に添付図面を参照して、オートマトン決定化装置、決定化方法及び決定化プログラムの最良な実施形態を詳細に説明する。
【００１２】
［第１の実施形態］
図１は、本実施形態に係るオートマトン決定化装置１００のハードウェア構成を示したブロック図である。図１に示したように、オートマトン決定化装置１００は、ＣＰＵ（Central  Processing  Unit）１、操作部２、表示部３、ＲＯＭ（Read  Only  Memory）４、ＲＡＭ（Random  Access  Memory）５、記憶部６等を備え、各部はバス７により接続されている。なお、後述するオートマトン決定化装置２００、３００及び４００においても、オートマトン決定化装置１００と同様のハードウェア構成を有するものとする。
【００１３】
ＣＰＵ１は、ＲＡＭ５の所定領域を作業領域として、ＲＯＭ４又は記憶部６に予め記憶された各種制御プログラムとの協働により各種処理を実行し、オートマトン決定化装置１００を構成する各部の動作を統括的に制御する。また、ＣＰＵ１は、ＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により、後述する各機能部の機能を実現させる。
【００１４】
操作部２は、マウスやキーボード等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をＣＰＵ１に出力する。
【００１５】
表示部３は、ＬＣＤ（Liquid  Crystal  Display）等の表示装置により構成され、ＣＰＵ１からの表示信号に基づいて、各種情報を表示する。
【００１６】
ＲＯＭ４は、オートマトン決定化装置１００の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。
【００１７】
ＲＡＭ５は、ＳＤＲＡＭ等の揮発性の記憶媒体であって、ＣＰＵ１の作業エリアとして機能し、具体的には、後述する逐次決定化処理時において生成される各種変数やパラメータの値等を一時記憶するバッファ等の役割を果たす。
【００１８】
記憶部６は、磁気的又は光学的に記録可能な記憶媒体を有し、オートマトン決定化装置１００の制御にかかるプログラムや各種設定情報等を書き換え可能に記憶する。また、記憶部６は、後述する逐次決定化処理で処理の対象となる非決定性ＦＳＡや後述する非決定性ＷＦＳＴ等のオートマトンに係る各種の情報を予め記憶する。
【００１９】
図２は、ＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される、オートマトン決定化装置１００の機能的構成を示した図である。同図に示したように、オートマトン決定化装置１００は決定化処理部１１、部分集合生成部１２、部分決定化部１３、繰り返し処理部１４を備えている。
【００２０】
決定化処理部１１は、非決定性ＦＳＡをサブセット構成法とよばれる公知の方法により決定化する機能部である。以下、決定化処理部１１が行う決定化の方法を、従来の決定化方法という。
【００２１】
ここで、決定化処理部１１が行う従来の決定化方法について説明する。図３は、非決定性ＦＳＡであるＡ1＝（Ｑ1，Σ，Ｅ1，Ｉ1，Ｆ1）の一例を示した図である。Ｑ1は状態の集合を、Σは入力記号の集合を、Ｅ1は遷移の集合でＥ1⊆Ｑ1×Σ×Ｑ1を、Ｉ1は初期状態の集合を、Ｆ1は受理状態の集合を夫々意味している。また、遷移の集合Ｅ1の各要素である遷移をδとして、prev(δ)を遷移元の状態、next(δ)を遷移先の状態、input(δ)を遷移の入力記号であるとする。なお、prev(δ)∈Ｑ1、next(δ)∈Ｑ1、input(δ)∈Σである。
【００２２】
図３の場合、Ｑ1＝｛０，１，２，３｝、Σ＝｛ａ，ｂ，ｃ｝、Ｉ1＝｛０｝、Ｆ1＝｛０｝となる。なお、ＦＳＡの状態名は整数値で表現されているものとしている。この例の場合、遷移の集合Ｅ1は図４で示した遷移表のように表すことができる。ここで、図４は、図３に示した非決定性ＦＳＡの遷移表を示した図である。同図に示したように、遷移の種別を表す「遷移」と、遷移元の状態を表す「遷移元状態」と、遷移先の状態を表す「遷移先状態」と、この遷移に付与された「入力記号」と、が対応付けられている。この遷移表において、例えば行Ｒ１は、入力記号ａによる状態０から状態１への遷移δ0を表している。
【００２３】
なお、図３で示したＦＳＡが非決定性ＦＳＡであるということは、一の入力記号に対応する遷移先の状態数を数えることで判別することができる。例えば、現在の状態が初期状態である状態０であるとき、入力記号ａがこのＦＳＡに入力された場合を参照すると、遷移先の状態は状態１か状態２となり、遷移先の状態は１つに定まらない。このことから、図３のＦＳＡが非決定性ＦＳＡであることがわかる。
【００２４】
決定化処理部１１は、図３で示した非決定性ＦＳＡをサブセット構成法によって決定化するため、図５で示した決定化処理を実行する。以下、決定化処理部１１が行う決定化処理について説明する。なお、本処理の前提として、非決定性ＦＳＡであるＡ1＝（Ｑ1，Σ，Ｅ1，Ｉ1，Ｆ1）を決定化した決定性ＦＳＡを、Ａ2＝（Ｑ2，Σ，Ｅ2，ｉ2，Ｆ2）とする。ここでｉ2は初期状態であり、この処理によって決定化を実行する前、つまりステップＳ１１が実行される前のＦ2やＥ2やＱ2は空集合であるものとする。また、決定化処理の実行時に生成される、後述するｑsub、ｑ'sub、ｘ、δ’等の各種変数は作業エリアとして機能するＲＡＭ５に一時記憶されるものとする。なお、図中の「φ」は空集合を表す。
【００２５】
まず、決定化処理部１１は、Ａ2の初期状態ｉ2にＩ1を代入し（ステップＳ１１）、このＡ2の初期状態であるｉ2をキューＳに１つの要素として追加する（ステップＳ１２）。
【００２６】
次いで、決定化処理部１１は、Ｓが空集合か否かを判定する（ステップＳ１３）。ここで、Ｓを空集合でないと判定した場合には（Ｓ１３；Ｙｅｓ）、決定化処理部１１は、Ｓから要素を一つ取り出しｑsubに代入した後（ステップＳ１４）、現在のｑsubに関してΣに含まれた要素（入力記号）全てに対してステップＳ１６〜２３の処理を行ったか否かを判定する（ステップＳ１５）。
【００２７】
ステップＳ１５において、Σの要素全てに対して処理を行ったと判定した場合には（ステップＳ１５；Ｙｅｓ）、ステップＳ１３の処理へと再び戻る。また、ステップＳ１５において、Σの要素全てに対して処理を行っていないと判定した場合には（ステップＳ１５；Ｎｏ）、決定化処理部１１は、まだ処理していない入力記号をｘに代入する（ステップＳ１６）。
【００２８】
続いて、決定化処理部１１は、ｑsubに含まれる状態のうち入力記号ｘを伴う遷移の遷移先の状態の集合をｑ'subに代入する（ステップＳ１７）。次に決定化処理部１１は、入力記号ｘによりｑsubからｑ'subに遷移することのできる遷移δ’をＥ2に追加する（ステップＳ１８）。
【００２９】
次いで、決定化処理部１１は、ｑ'subが既にＱ2に存在しているか否かを判定する。ここで、存在すると判定した場合（ステップＳ１９；Ｙｅｓ）、ステップＳ１５の処理へと再び戻る。
【００３０】
一方、ｑ'subがＱ2に存在していないと判定した場合（ステップＳ１９；Ｎｏ）、決定化処理部１１は、ｑ'subをＱ2に追加する（ステップＳ２０）。続いて決定化処理部１１は、ｑ'subの要素がＦ1に含まれているか否かを判定する（ステップＳ２１）。ここで、ｑ'subの要素がＦ1に含まれていないと判定した場合には（ステップＳ２１；Ｎｏ）、ステップＳ２３の処理へと直ちに移行する。
【００３１】
また、ステップＳ２１において、ｑ'subの要素がＦ1に含まれていると判定した場合には（ステップＳ２１；Ｙｅｓ）、決定化処理部１１は、ｑ'subを受理状態の集合Ｆ2に追加し（ステップＳ２２）、ステップＳ２３の処理へと移行する。
【００３２】
続くステップＳ２３では、決定化処理部１１がＳにｑ'subを追加した後（ステップＳ２３）、ステップＳ１５の処理へと再び戻る。
【００３３】
一方、ステップＳ１３において、Ｓを空集合と判定した場合には（ステップＳ１３；Ｎｏ）、ステップＳ２４へと移行し、Ｑ2に追加された状態の名前を付け替えた後（ステップＳ２４）、本処理を終了する。この名前の付け替えについては後述する。
【００３４】
なお、受理状態に到達できない経路にある状態や遷移は除去することとしてもよい。また、Ｓはキューである必要はなく、例えばスタック等、要素を１つずつ追加、取り出しでき、空であるかどうかを確認できるものであればその態様は問わないものとする。
【００３５】
図６は、上記した決定化処理により図３の非決定性ＦＳＡ  Ａ1を決定化した決定性ＦＳＡ  Ａ2を示した図である。また、図６での遷移の集合Ｅ2は、図７に示した遷移表で表される。なお、図６では、名前の付け替えの処理（ステップＳ２４）前の状態を示している。
【００３６】
図６において、各状態の「｛｝」で囲まれた中の数字はＱ１の要素であり、「｛｝」で囲まれた全体の集合は上述したステップＳ２０で追加された各ｑ'subに対応するものである。具体的に、状態Ｂ１１は｛０｝、状態Ｂ１２は｛１，２｝、状態Ｂ１３は｛０，３｝のように、集合Ｑ1の部分集合として表現されている。以下、この部分集合が名前として割り当てられた状態のこと、すなわち、名前の付け替え前のＱ2に含まれている状態のことを「決定化済み状態」という。
【００３７】
上述したステップＳ２４で行う名前の付け替えの処理は、決定化済み状態の名前、つまり、状態の集合Ｑ1の部分集合として表現された名前を、単一の名前に置き換える処理のことを意味している。例えば、図６の場合、名前の付け替え前のＱ2の要素、つまり決定化済み状態の名前は整数値の集合で表されている。このように状態の名前を集合として保持するのは効率が悪いので、それぞれの集合に互いに異なる整数値を割り当てる。つまり、状態Ｂ１１の｛０｝を０に、状態Ｂ１２の｛１，２｝を１に、状態Ｂ１３の｛０，３｝を２に名前を付け替える。図８は、この図６の状態の名前を付け替えた結果の一例を示した図である。同様に図６の遷移表である図７での「遷移元状態」と「遷移先状態」との名前も付け替えることができる。
【００３８】
このように名前の付け替えを行うことで、状態の名前をＱ1の部分集合として保持する必要がなくなり、決定化後のＦＳＡを記憶しておくために必要な記憶域を削減できる。さらに具体的には、整数が４バイトで表現されていた場合、名前の付け替え前は状態名を記憶するために状態名とその数を記憶しておく必要があるため、状態名の記憶に２０バイト、状態名の数を記憶するために１２バイトで計３２バイト必要であるが、名前の付け替え後は１２バイトで済むようになる。
【００３９】
しかしながら、決定化処理部１１の決定化処理のみでは状態数や遷移数が増えるに伴い、Ｑ1の部分集合として表現される名前の長さも増加するため、決定化済み状態を記憶しておくために大きなメモリ量が必要となる。そのため、本実施形態では、部分集合生成部１２、部分決定化部１３、繰り返し処理部１４により、後述する逐次決定化処理を実行し非決定性ＦＳＡの決定化を行うことで、決定化済み状態ｑ'subに含まれている状態の数を減らし、決定化済み状態を記憶しておくためにメモリ量を削減する。
【００４０】
以下、本実施形態で行う逐次決定化処理の概要について説明する。ｑ'subに含まれる状態がどのように作成されるのかは、上述した図５のステップＳ１７で説明したとおりである。Ｑ2に含まれている決定化済み状態ｑsubから入力記号ａにより遷移した先の状態がｑ'subであるとすると、ｑsubに含まれる各状態から入力記号ａをとって遷移した先の状態は全てｑ'subに含まれることになる。ここで、ａは入力記号の集合Σに含まれる入力記号である。したがって、Ｅ1に含まれる遷移のうち、遷移元の状態がｑsubに含まれており、且つ、その入力記号がａであるような遷移の数がｑ'subに含まれる状態数の上限値となる。
【００４１】
さて、ｑsubに含まれた状態が遷移元であり、入力記号がａであり、ｑ'subに含まれている状態が遷移先であるようなＥ1に含まれる遷移の集合をδsubとすると、決定化の操作はδsubに含まれている遷移を１つの遷移にまとめているとみなすことで処理することができる。実際、決定化後のＦＳＡ  Ａ２において、ｑsubから入力記号ａをとってｑ'subへと遷移する遷移はただ１つである。δsubに含まれる遷移の数がｑ'subに含まれる状態数の上限値であるから、δsubをいくつかの集合に分割することができればｑ'subに含まれる状態数の上限値を減らすことができる。つまり、決定化済み状態を記憶するための記憶域を削減するためにはδsubを分割すればよいということがわかる。
【００４２】
ところが、δsubに含まれた全ての遷移を分割しても、それらの遷移については決定化したことにはならない場合がある。例えば、δsubに含まれる入力記号ａに係る２つの遷移（δ0、δ1）を分割したとすると、ｑsubから入力記号ａをとって遷移する遷移先の状態は２つになる。これはつまり決定化できていないということである。そこで、本実施形態では、δsubに含まれた全ての遷移について分割を行うのでなく、δsubに含まれた遷移のうち一部の遷移を分割し、残りの遷移については分割しないようにする。以下、δsubのうち分割を行わない遷移のことを「決定化対象とする遷移」という。また、δsubに含まれた遷移のうち一部の遷移を分割して決定化すること、つまり非決定性ＦＳＡの遷移の一部を決定化することを「部分決定化」という。ただし、全ての遷移について決定化することも、この部分決定化の概念に含めるものとする。
【００４３】
また、部分決定化によって決定化済み状態を記憶するための記憶域を削減することができるが、部分決定化を１回行っただけでは非決定性ＦＳＡは決定化できない。そこで、繰り返し処理部１４は、全ての遷移が決定化されるまで決定化対象とする遷移を変えながら、部分決定化部１３により部分決定化を繰り返し実行させる。部分決定化では、図５で説明した処理のステップＳ２４と同様に、実行されるたびに状態の名前を付け替えるため、決定化済み状態を記憶するための記憶域は部分決定化が終了するたびに不要となる。
【００４４】
つまり、この部分決定化を繰り返して実行する方法で必要となる決定化済み状態を記憶するためのメモリ量は、各回の部分決定化が必要となった決定化済み状態を記憶するためのメモリ量のうちで最も多いものと同値となる。すなわち、図５で説明した従来の決定化の方法よりも、決定化済み状態を記憶するためのメモリ量を削減することが可能となる。
【００４５】
以下、部分集合生成部１２、部分決定化部１３、繰り返し処理部１４について説明する。
【００４６】
部分集合生成部１２は、決定化対象とする遷移の入力記号の部分集合Σi（ｉは１以上の整数）を、後述する決定化処理の繰り返し回数に応じて生成する機能部である。
【００４７】
具体的に、部分集合生成部１２は、所定の規則に基づいて処理の対象となる非決定性ＦＳＡの集合Σに含まれた入力記号を配列し、配列後の入力記号のうち、一部の入力記号を抽出した部分集合Σiを、後述する部分決定化処理の繰り返し回数に応じて順次生成する。
【００４８】
ここで、入力記号の配列決定時の基準となる所定の規則は、特に問わないものとする。なお、本実施形態では、下記式（１）で表した関数ｖ（ｘ）で得られる値が大きいほど、上位の順位となるよう定めた関係式ｒ（ｖ（ｘ））を所定の規則として用いるものとする。
【００４９】
【数１】
0004956334.tif 000002
【００５０】
ここで、「ｘ」は処理対象となる非決定性ＦＳＡの集合Σに含まれた何れかの入力記号であって、当該ｘを入力記号とする遷移の集合をＥxとしている。ただし、ＥxはＥ1に含まれているものとする。ＱxはＥxに属する遷移の遷移元となる状態の集合である。さらに、Ｅxの要素数をＮ（Ｅx）、Ｑxの要素数をＮ（Ｑx）、Ｑ1の要素数をＮ（Ｑ1）としている。
【００５１】
ここで、上記式（１）の計算結果に基づき、当該計算結果の値が大きいほど上位の順位となるよう各入力記号を配列することは、各入力記号に係る遷移の個数が多いものから配列することと同義である。なお、上記式（１）においてＮ(Ｑ1)の部分を所定の定数値としてもよい。また、配列決定時の指標となる所定の規則は、上記例に限定されないものとする。
【００５２】
また、部分集合生成部１２により生成される部分集合Σiは、下記式（２）の条件を満たすものとする。ここで、「ｎ」は後述する部分決定化処理を繰り返す総数（繰り返し総数）を表しており、Σn＝Σである。
【００５３】
【数２】
0004956334.tif 000003
【００５４】
集合Σの分割方法は、上記式（２）の条件を満たす限り特に問わないものとするが、本実施形態では、ｉの増加とともに、決定化の対象となる遷移の入力記号の数を略等間隔で増加させる態様を採用する。
【００５５】
以下、図９を参照して、部分集合生成部１２で実行される部分集合生成処理の動作を説明する。まず、部分集合生成部１２は、上述した所定の規則に基づいて、非決定性ＦＳＡの集合Σに含まれた各入力記号を配列する（ステップＳ３１）。
【００５６】
次いで、部分集合生成部１２は、Ｎ（Σ）を入力記号の総数として、ΣiにＮ(Σ)×i／n個だけ並べた順に入力記号を代入し、これをn回繰り返すことで繰り返しの回数ｉ毎のΣiを順次生成する（ステップＳ３２）。言い換えると、入力記号を引数に取り、順位(１以上の整数)を返す関数ｒとし、入力記号をｘとしたときｒ(ｘ)≦Ｎ(Σ)×i／nを満たす入力記号の集合をｉの値毎にΣiに代入する。
【００５７】
上述した部分集合生成処理の動作を、図３に示した非決定性ＦＳＡを用いて説明する。まず、部分集合生成部１２は、式（１）で示した関数ｖ（ｘ）を用いて、その値を入力記号毎に計算すると、ｖ（ａ）＝（２＋４）／（１＋４）＝１．２、ｖ（ｂ）＝（２＋４）／（２＋４）＝１．０、ｖ（ｃ）＝（１＋４）／（１＋４）＝１．０が得られる。ここで、関数ｖ（ｘ）の返す値が同じとなる場合には、入力記号が文字であれば割り当てられた文字コード等の値を基準に順序を決める等すればよいし、整数値であればその値自体を基準に順序を決めるなどすればよい。次いで、部分集合生成部１２は、ｖ（ｘ）の大きに応じて上位の順位となるよう定めた関係式ｒ（ｘ）を用いることで、ｒ（ｖ（ａ））＝１、ｒ（ｖ（ｂ））＝２、ｒ（ｖ（ｃ））＝３を導出する。
【００５８】
ここで、繰り返し総数ｎ＝３が設定されたものとすると、部分集合生成部１２は、部分集合Σiとして繰り返し回数ｉ（ｉ＝１〜３）毎に、Σ1＝{ａ}、Σ2＝{ａ,ｂ}、Σ3＝{ａ,ｂ,ｃ}を生成する。
【００５９】
図２に戻り、部分決定化部１３は、部分集合生成部１２により生成されたΣiに基づいて、決定化の対象とする遷移を選択するとともに、決定化の対象とならない遷移に係る入力記号を異なる入力記号に置き換え、図５で説明した従来の決定化方法を利用することで、決定化の対象とする遷移についての決定化（部分決定化）を行う。
【００６０】
また、繰り返し処理部１４は、部分決定化部１３を制御し、繰り返し総数ｎに応じた回数だけ部分決定化処理を繰り返し実行させる。
【００６１】
以下、図１０、１１を参照して、部分決定化部１３及び繰り返し処理部１４により実行される逐次決定化処理について説明する。なお、本処理の前提として、部分集合生成部１２により部分集合Σiが予め生成されているものとする。また、逐次決定化処理の実行時に生成される、後述するＥr、Ｅd、ｘnew等の各種変数は作業エリアとして機能するＲＡＭ５に一時記憶されるものとする。
【００６２】
図１０は、本実施形態における逐次決定化処理の手順を示したフローチャートである。まず、繰り返し処理部１４は、繰り返し回数を計数するための変数ｉを１に設定すると（ステップＳ４１）、このｉの値に応じた部分決定化処理（ステップＳ４２）を部分決定化部１３に実行させる。以下、図１１を参照して、ステップＳ４２の部分決定化処理について説明する。
【００６３】
図１１は、ステップＳ４２の部分決定化処理の手順を示したフローチャートである。まず、部分決定化部１３は、決定化の対象となる遷移、つまり遷移の入力記号がΣiに含まれている遷移の集合をＥrに代入する（ステップＳ５１）。次いで、部分決定化部１３は、決定化の対象とならない遷移、つまり遷移の入力記号がΣiに含まれていない遷移の集合をＥdに代入する（ステップＳ５２）。なお、Σiのｉは、ステップＳ４１又は後述するステップＳ４５で設定されたｉの値に対応する。
【００６４】
続いて、部分決定化部１３は、Ｅdに属する全ての遷移δdについて、後述するステップＳ５４、５５の処理を施したか否かを判定する（ステップＳ５３）。ここで、未処理の遷移δdが存在すると判定した場合（ステップＳ５３；Ｎｏ）、部分決定化部１３は、下記式（３）を満たすｘnew、即ち、Ｅdの遷移の入力記号が互いに異なる入力記号となり、且つ、Σiとも異なる入力記号となるような入力記号ｘnewを生成する（ステップＳ５４）。
【００６５】
【数３】
0004956334.tif 000004
【００６６】
次いで、部分決定化部１３は、この生成したｘnewを遷移δdにかかる入力記号と置き換え（ステップＳ５５）、ステップＳ５３の処理へと再び戻る。
【００６７】
一方、ステップＳ５３において、Ｅdに属する全ての遷移δdについて、ステップＳ５４、５５の処理を施したと判定した場合には（ステップＳ５３；Ｙｅｓ）、ステップＳ５６の処理へと移行する。
【００６８】
次に、部分決定化部１３は、Ｅdに属した遷移δdをＥrへと追加した後（ステップＳ５６）、このＥrを含む非決定性ＦＳＡ  Ａr＝（Ｑ1，Σr，Ｅr，Ｉ1，Ｆ1）の決定化処理を決定化処理部１１に実行させ、その結果をＡ'r（Ａ'r＝（Ｑ2，Σr，Ｅ'r，ｉ2，Ｆ2））に代入する（ステップＳ５７）。ここで、Σrは入力記号を置き換えた後の入力記号の集合である。なお、ステップＳ５７で行われる決定化処理の手順は、図５で説明したものと同様であるため、説明を省略する。
【００６９】
続いて、部分決定化部１３は、Ａ'rの入力記号ΣrをステップＳ５５で置き換える前の元の入力記号に戻した後、このＡ'rをＡ2＝（Ｑ2，Σ，Ｅ2，ｉ2，Ｆ2）に代入し（ステップＳ５８）、ステップＳ４３の処理へと移行する。ここでＡ2は、Ａ1のうちΣiに属する入力記号を持つ遷移のみを決定化したＦＳＡとなっている。
【００７０】
図１０に戻り、繰り返し処理部１４は、ｉの値が繰り返し回数の最大値であるｎを下回るか否かを判定する（ステップＳ４３）。ここで、ｉの値がｎを下回ると判定した場合には（ステップＳ４３；Ｙｅｓ）、繰り返し処理部１４は、ステップＳ４２で決定化されたＦＳＡ  Ａ2をＦＳＡ  Ａ1とし（ステップＳ４４）、ｉの値を１増やした後（ステップＳ４５）、ステップＳ４２の処理へと再び戻る。
【００７１】
また、ステップＳ４３において、ｉの値がｎ以上と判定した場合には（ステップＳ４３；Ｎｏ）、本処理を終了する。ここで、最終的に得られたＦＳＡ  Ａ2は処理対象となった非決定性ＦＳＡ  Ａ1を決定化したものとなっている。
【００７２】
上述した逐次決定化処理の動作を、図３で示した非決定性ＦＳＡ  Ａ1を基に、図１２〜１７を用いて説明する。なお、繰り返し総数ｎは３とし、部分集合生成部１２により生成された部分集合Σiが、Σ1＝｛ａ｝、Σ2＝｛ａ,ｂ｝、Σ3＝｛ａ,ｂ,ｃ｝であるものとする。
【００７３】
まず、１回目（ｉ＝１）の決定化に関して、入力記号の名前を付け替えた時点（図１１のステップＳ５７の時点）でのＦＳＡ  Ａrを図１２に示す。この例では、状態１から状態０へ遷移する遷移の入力記号ｂをＢと置き換え、状態２から状態３へ遷移する遷移の入力記号ｂをＣと置き換え、状態３から状態０へ遷移する遷移の入力記号ｃをＤと付け替えている。
【００７４】
部分決定化部１３は、このＦＳＡ  Ａrを図５で説明した決定化の方法によって決定化する。状態名の名前の付け替え前、つまり図５でのステップＳ２４を実行する直前のＦＳＡを図１３に示す。そして、決定化処理部１１が状態番号を振りなおし、部分決定化部１３が、入力記号を元に戻して１回目の決定化が完了する。この状態が図１４である。
【００７５】
同様に２回目（ｉ＝２）の決定化処理中において、図１４で示した状態２から状態０へ遷移する遷移の入力記号ｃをＣに置き換えて決定化した後、状態名を付け替える直前の結果を図１５に示している。さらに状態番号を振りなおし、入力記号を元に戻したものが図１６である。
【００７６】
既に決定化された状態ではあるが、部分決定化部１３は、繰り返し処理部１４の制御に応じて３回目（ｉ＝３）の決定化を行う。ここで、図１７は、状態名を付け替える直前の結果を示した図である。置き換えた入力記号はないので、入力記号については元に戻す処理は何も行わず、状態名のみ付け替えた最終結果は上述した図８と同様となる。
【００７７】
ところで、図５で説明した従来の決定化の方法のみを用いた場合での、決定化済み状態に含まれた要素の合計数は、図６に示したように５個である。一方、図１０で説明した決定化の方法による１回目の決定化の結果において、決定化済み状態に含まれた要素の合計数は図１３から分かるように４個である。また、同様に２回目は図１５より４個、３回目は図１７より３個となる。
【００７８】
したがって、繰り返し決定化処理を行った中での最大の合計要素数は４個となり、決定化処理のみを用いた従来の決定化による方法よりも合計要素数の最大値を減らすことができる。つまり、決定化済み状態の記憶に必要なメモリ量を減らすことができる。
【００７９】
以上のように、本実施形態によれば、非決定性ＦＳＡに含まれた遷移から、決定化の対象とする遷移を一部選び、この決定化対象とする遷移を毎回変えながら繰り返し決定化を行うことで、一回の決定化で記憶する決定化済み状態の名称のうち、それを構成する非決定性オートマトンに含まれた状態の延べ数を減少させることができるため、決定化の実行時に要するメモリ量を減少させることができる。
【００８０】
なお、先に述べたオートマトン決定化装置１００における各処理を実行するプログラムを、インストール可能な形式又は実行可能な形式でＣＤ−ＲＯＭ、フロッピー（Ｒ）ディスク（ＦＤ）、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録して提供する態様としてもよい。 
【００８１】
また、オートマトン決定化装置１００における各処理を実行するプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。 
【００８２】
この場合には、プログラムは、オートマトン決定化装置１００において上記記録媒体から読み出して実行することによりＲＡＭ５上にロードされ、上記ソフトウェア構成で説明した各部がＲＡＭ５上に生成される。
【００８３】
［第２の実施形態］
上述した第１の実施形態では、部分決定化処理を行う毎に入力記号の置き換えを行う態様を説明した。本実施形態では入力記号の置き換えを行うことなく、非決定性ＦＳＡの決定化を実現し、当該決定化に必要となるメモリ量を削減することが可能なオートマトン決定化装置２００について説明する。なお、上述した第１の実施形態と同様の構成については、同一の符号を付与しその説明を省略する。
【００８４】
図１８は、図１に示したＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される、本実施形態のオートマトン決定化装置２００の機能的構成を示した図である。同図に示したように、オートマトン決定化装置２００は部分集合生成部１２、部分決定化部２１、繰り返し処理部１４を有している。
【００８５】
ここで、部分決定化部２１は、処理対象の非決定性ＦＳＡに含まれた遷移にかかる入力記号から、一の入力記号を処理対象として順次選択し、この処理対象の入力記号に係る遷移を抽出した遷移の集合Ｅdを生成する。また、部分決定化部２１は、Ｅdに含まれる遷移から、決定化対象とする遷移を選択し、この選択した遷移について決定化を行う。ここで、Ｅdの生成に係る抽出方法は、特に問わないものとするが、本実施形態では、第１の実施形態で説明した、部分集合Σiに基づいて行うものとする。
【００８６】
以下、図１９〜２１を参照して、部分決定化部２１及び繰り返し処理部１４により実行される、本実施形態の逐次決定化処理について説明する。なお、本処理の前提として、部分集合生成部１２により部分集合Σiが予め生成されているものとする。また、逐次決定化処理の実行時に生成される、後述する各種変数は作業エリアとして機能するＲＡＭ５に一時記憶されるものとする。
【００８７】
図１９は、本実施形態における逐次決定化処理の手順を示したフローチャートである。まず、繰り返し処理部１４は、繰り返し回数を計数するための変数ｉを１に設定すると（ステップＳ６１）、このｉの値に応じた部分決定化処理（ステップＳ６２）を部分決定化部２１に実行させる。以下、図２０を参照して、ステップＳ６２の部分決定化処理について説明する。
【００８８】
図２０は、ステップＳ６２の部分決定化処理の手順を示したフローチャートである。まず、部分決定化部２１は、Ａ2の初期状態ｉ2にＩ1を代入し（ステップＳ７１）、このｉ2をキューＳに追加する（ステップＳ７２）。この時点でＳにはｉ2のみが記憶されている。
【００８９】
次いで、部分決定化部２１は、Ｓが空集合か否かを判定し、空集合でないと判定した場合には（Ｓ７３；Ｙｅｓ）、Ｓから要素を一つ取り出しｑsubに代入した後（ステップＳ７４）、現在のｑsubに関してΣに含まれた要素（入力記号）全てに対して処理を行ったか否かを判定する（ステップＳ７５）。ここで、Σの要素全てに対して処理を行ったと判定した場合には（ステップＳ７５；Ｙｅｓ）、ステップＳ７３の処理へと再び戻る。
【００９０】
一方、ステップＳ７５において、Σの要素全てに対して処理を行っていないと判定した場合には（ステップＳ７５；Ｎｏ）、部分決定化部２１は、まだ処理していない入力記号のうちの１つをｘに代入する（ステップＳ７６）。
【００９１】
続いて、部分決定化部２１は、入力記号ｘを伴うｑsubに含まれる状態からの遷移の集合をＥdに代入した後（ステップＳ７７）、このＥdが空集合か否かを判定する（ステップＳ７８）。ここで、Ｅdを空集合と判定した場合（ステップＳ７８；Ｎｏ）、ステップＳ７５の処理へと再び戻る。
【００９２】
一方、ステップＳ７８において、Ｅdを空集合でないと判定した場合（ステップＳ７８；Ｙｅｓ）、部分決定化部２１は、Ｅdから遷移を選択する遷移選択処理（ステップＳ７９）を実行する。以下、図２１を参照して、ステップＳ７９の遷移選択処理について説明する。
【００９３】
まず、部分決定化部２１は、ステップＳ７６で代入した入力記号ｘが、部分集合Σiに含まれているか否かを判定する（ステップＳ７９１）。なお、Σiのｉは、ステップＳ６１又は後述するステップＳ６５で設定されたｉの値に対応する。
【００９４】
ここで、入力記号ｘが部分集合Σiに含まれていると判定した場合には（ステップＳ７９１；Ｙｅｓ）、遷移の集合ＥtにＥdを代入し（ステップＳ７９２）、図２０のステップＳ８０の処理へと移行する。
【００９５】
一方、ステップＳ７９１において、入力記号ｘが部分集合Σiに含まれないと判定した場合には（ステップＳ７９１；Ｎｏ）、Ｅdから任意の遷移を一つ取り出し、遷移の集合Ｅtに代入した後（ステップＳ７９３）、図２０のステップＳ８０の処理へと移行する。
【００９６】
図２０に戻り、部分決定化部２１は、ステップＳ７９で選択した遷移の集合Ｅtに属する遷移をＥdから除去する（ステップＳ８０）。続いて、部分決定化部２１は、Ｅtに含まれる遷移をδとしたとき、遷移δの遷移先の状態の集合ｑsをｑ'subに代入する（ステップＳ８１）。
【００９７】
次いで、部分決定化部２１は、δ'の遷移元の状態がｑsubであり、δ'の遷移先の状態がｑ'subであり、δ'の入力記号がｘであるδ'を、Ｅ2に追加した後（ステップＳ８２）、ｑ'subがＱ2に存在しているか否かを判定する（ステップＳ８３）。ここで、ｑ'subが既にＱ2に存在していると判定した場合には（ステップＳ８３；Ｙｅｓ）、ステップＳ７８の処理へと再び戻る。
【００９８】
一方、ステップＳ８３において、ｑ'subがＱ2に存在しないと判定した場合、つまりｑ'subが新たな状態であると判定した場合には（ステップＳ８３；Ｎｏ）、部分決定化部２１は、Ｑ2にｑ'subを追加する（ステップＳ８４）。続いて部分決定化部２１は、ｑ'subの要素がＦ1に含まれているか否かを判定する（ステップＳ８５）。ここで、ｑ'subの要素がＦ1に含まれていないと判定した場合には（ステップＳ８５；Ｎｏ）、ステップＳ８７の処理へと直ちに移行する。
【００９９】
また、ステップＳ８５において、ｑ'subの要素がＦ1に含まれていると判定した場合には（ステップＳ８５；Ｙｅｓ）、部分決定化部２１は、ｑ'subを受理状態の集合Ｆ2に追加した後（ステップＳ８６）、ステップＳ８７の処理へと移行する。
【０１００】
続くステップＳ８７では、部分決定化部２１がＳにｑ'subを追加した後（ステップＳ８７）、ステップＳ７８の処理へと再び戻る。
【０１０１】
一方、ステップＳ７３において、Ｓを空集合と判定した場合には（ステップＳ７３；Ｎｏ）、ステップＳ８８へと移行し、Ｑ2に追加された状態の名前を付け替えた後（ステップＳ８８）、図１９のステップＳ６３へと移行する。
【０１０２】
図１９に戻り、繰り返し処理部１４は、ｉの値が繰り返し回数の最大値であるｎを下回るか否かを判定する（ステップＳ６３）。ここで、ｉの値がｎを下回ると判定した場合には（ステップＳ６３；Ｙｅｓ）、繰り返し処理部１４は、ステップＳ６２で導出されたＦＳＡ  Ａ2をＦＳＡ  Ａ1とし（ステップＳ６４）、ｉの値を１増やした後（ステップＳ６５）、ステップＳ６２の処理に再び移行する。
【０１０３】
また、ステップＳ６３において、ｉの値がｎ以上と判定した場合には（ステップＳ６３；Ｎｏ）、本処理を終了する。ここで、最終的に得られたＦＳＡ  Ａ2は処理対象となった非決定性ＦＳＡ  Ａ1を決定化したものとなっている。
【０１０４】
以上のように、本実施形態によれば、非決定性ＦＳＡに含まれた遷移から、決定化の対象とする遷移を一部選び、この決定化対象とする遷移を毎回変えながら繰り返し決定化を行うことで、一回の決定化で記憶する決定化済み状態の名称のうち、それを構成する非決定性オートマトンに含まれた状態の延べ数を減少させることができるため、決定化の実行時に要するメモリ量を減少させることができる。
【０１０５】
また、本実施形態によれば、決定化の対象とする遷移を直接指定することができるため、入力記号による遷移の選択以外の方法でも決定化の対象となる遷移を選択することができる。
【０１０６】
［第３の実施形態］
第１の実施形態で説明した方法は、ＦＳＡだけでなくＦＳＡを拡張したオートマトンの決定化に対しても同様に適用することが可能である。本実施形態では、ＦＳＡを拡張したオートマトンの決定化を行うオートマトン決定化装置３００について説明する。なお、上述した第１の実施形態と同様の構成については、同一の符号を付与しその説明を省略する。
【０１０７】
図２２は、ＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される、オートマトン決定化装置３００の機能的構成を示した図である。同図に示したように、オートマトン決定化装置３００は決定化処理部３１、部分集合生成部１２、部分決定化部３２、繰り返し処理部３３を備えている。
【０１０８】
決定化処理部３１は、遷移先の状態が複数存在する重み付き有限状態オートマトン（Weighted  Finite  State  Automaton；ＷＦＳＡ）、有限状態トランスデューサ（Finite  State  Transducer；ＦＳＴ）、重み付き有限状態トランスデューサ（Weighted  Finite  State  Transducer；ＷＦＳＴ）等の非決定性ＦＳＡを拡張した非決定性状態にあるオートマトン（非決定性オートマトン）の決定化を行う。
【０１０９】
ここで、ＷＦＳＡとは、ＦＳＡの遷移に重みを加えたものである。したがって、ＷＦＳＡの遷移には、入力記号と重みとが割り当てられていることになる。なお、ここで「重み」とは、何らかの確率値やスコア、ペナルティ等であり、入力記号を受理する経路に沿って所定の規則（足し算、かけ算、最小値、最大値等）によって演算されるものである。
【０１１０】
また、ＦＳＴはＦＳＡの遷移の入力記号に出力記号を加えたものであり、入力記号からなる記号列を入力として与えると、出力記号からなる記号列を出力する。このＦＳＴは、例えば記号列の変換に利用されている。
【０１１１】
また、ＷＦＳＴは、ＷＦＳＡの遷移に割り当てられた入力記号、重みに加え、出力記号も付与するようにしたモデルである。つまり、ＷＦＳＴでは、遷移に対して入力記号、出力記号及び重みの３つの要素が割り当てられていることになる。このＷＦＳＴは、例えば音声認識におけるモデルを表現するものとして利用されている。
【０１１２】
これらＦＳＡの拡張モデル（特に、ＷＦＳＡやＦＳＴ）を決定化するための方法は、Finite-state  transducers  in  language  and  speech  processing,  Mehryar  Mohri,  Computational  Linguistics,  Volume  23,  Issue  2(June  1997)  Pages.269-311等に記載されている。なお、決定化処理部３１は、これら公知の方法を利用した決定化処理を行う機能部である。以下、決定化処理部３１が行う決定化の方法を、従来の決定化方法という。
【０１１３】
以下、決定化処理部３１が行う従来の決定化方法について説明する。なお、ここでは、ＷＦＳＴを処理の対象とし、決定化の対象となる非決定性ＷＦＳＴをＴ1＝（Ｑ1,Σ,Δ,Ｅ1,Ｉ1,Ｆ1,λ1,ρ1）とし、決定化後のＴ1を決定性ＷＦＳＴ  Ｔ2=（Ｑ2,Σ,Δ,Ｅ2,ｉ2,Ｆ2,λ2,ρ2）とする。
【０１１４】
上記した非決定性ＷＦＳＴ  Ｔ1において、Ｑ1は状態の集合、Σは入力記号の集合、Δは出力記号の集合、Ｅ1は遷移の集合でＥ1⊆Ｑ1×Σ×Δ×Ｋ×Ｑ1、Ｉ1は初期状態の集合、Ｆ1は受理状態の集合である。また、λ1は初期重み関数であって、初期状態を引数にとり当該引数に渡した初期状態に割り当てられた初期重みを返す関数である。ρ1は終了重み関数であって、受理状態を引数にとり当該引数に渡した受理状態に割り当てられた終了重みを返す関数である。なお、Ｔ2に関するＱ2、Ｅ2、Ｆ2、ρ2に関しても同様である。ただし、ｉ2は初期状態、λ2は初期重みである。Ｋは重みを表す集合であって、例えば整数全体や正の整数全体、実数全体であったりする。
【０１１５】
図２３は、決定化処理部３１が行う決定化処理の手順を示したフローチャートである。まず、決定化処理部３１は、Ｆ2を空集合とした後（ステップＳ９１）、全ての初期状態の初期重みのうち、最も小さい値をλ2に代入する（ステップＳ９２）。
【０１１６】
次いで、決定化処理部３１は、Ｔ1の状態名（ｑ）、文字列、重みの３つ組を要素とする集合を生成し、Ｔ2の初期状態名としてｉ2に代入する（ステップＳ９３）。この３つ組のうち、文字列を「余りの文字列」と呼ぶこととし、ステップＳ９３では空文字列であるεを設定する。一方、３つ組のうちの重みを「余りの重み」と呼ぶこととし、ステップＳ９３ではλ1(ｑ)−λ2を代入する。
【０１１７】
続いて、決定化処理部３１は、キューＳにｉ2を追加した後（ステップＳ９４）、Ｓが空集合か否かを判定する（ステップＳ９５）。ここで、Ｓが空でないと判定した場合には（ステップＳ９５；Ｙｅｓ）、決定化処理部３１は、Ｓに含まれた要素を１つ取り出し、取り出した要素をｑ2に代入する（ステップＳ９６）。
【０１１８】
次に、決定化処理部３１は、ｑ2に含まれた状態名、余りの文字列、余りの重みの３つ組の集合（ｑ，ｌ，ｗ）のうち、ｑがＴ1の受理状態の集合Ｆ1に含まれているか否かを判定する（ステップＳ９７）。ここで、ｑがＴ1の受理状態の集合Ｆ1に含まれていないと判定した場合には（ステップＳ９７；Ｎｏ）、ステップＳ１００の処理へと直ちに移行する。
【０１１９】
また、ステップＳ９７において、ｑがＴ1の受理状態の集合Ｆ1に含まれていると判定した場合には（ステップＳ９７；Ｙｅｓ）、決定化処理部３１は、ｑ2をＴ2の受理状態の集合Ｆ2に追加する（ステップＳ９８）。
【０１２０】
次いで、決定化処理部３１は、ｑ2に属する３つ組（ｑ，ｌ，ｗ）のｑのうち、受理状態の集合Ｆ1に含まれた全てのｑについてｗ＋ρ1(ｑ)を計算し、その最小値をｑ2の終了重みとしてρ2(ｑ2)に代入する（ステップＳ９９）。
【０１２１】
続いて、決定化処理部３１は、Σに含まれた全ての要素（入力記号）について、後述するステップＳ１０１からステップＳ１０９の処理を実行したか否かを判定する（ステップＳ１００）。ここで、Σのすべての要素について処理を実行したと判定した場合には（ステップＳ１００；Ｙｅｓ）、ステップＳ９５の処理へと再び戻る。
【０１２２】
一方、ステップＳ１００において、未処理の要素が存在すると判定した場合には（ステップＳ１００；Ｎｏ）、決定化処理部３１は、まだ処理していない入力記号のうちの１つをｘに代入した後（ステップＳ１０１）、Γ(ｑ2,ｘ)が空か否かを判定する（ステップＳ１０２）。ここで、Γ(ｑ2,ｘ)は、Γ(ｑ2,ｘ)＝{(ｑ,ｌ，ｗ)∈ｑ2|δ∈Ｅ1,prev(δ)=ｑ,input(δ)=ｘ}である。つまり、ｑ2に含まれている３つ組（ｑ，ｌ，ｗ）のうち、入力記号がｘであり遷移元がｑである遷移δがＥ1に存在するという条件をみたす３つ組（ｑ，ｌ，ｗ）の集合を示している。
【０１２３】
ステップＳ１０２において、Γ(ｑ2,ｘ)を空と判定した場合には（ステップＳ１０２；Ｎｏ）、ステップＳ１００の処理へと再び戻る。また、ステップＳ１０２において、Γ(ｑ2,ｘ)を空でないと判定した場合には（ステップＳ１０２；Ｙｅｓ）、決定化処理部３１は、遷移元がｑ2で入力記号がｘである遷移の重みを算出し、この算出結果をｗ2に代入する（ステップＳ１０３）。ここで代入されるｗ2の値は、Γ(ｑ2,ｘ)に属する３つ組（ｑ，ｌ，ｗ）の全てに対する次の値のうち最も小さい値となる。その値とは、Ｅ1に属する遷移のうち、遷移元がｑ且つ入力記号がｘであるような遷移δの重みのうちで最も小さい値にｗを足した値である。なお、ｗｅｉｇｈｔ（δ）は遷移δの重みを表す。
【０１２４】
続いて、決定化処理部３１は、遷移元がｑ2で入力記号がｘである遷移の出力記号を算出し、この算出結果をｌ2に代入する（ステップＳ１０４）。ここで代入されるｌ2の値は、Γ(ｑ2,ｘ)に属する３つ組（ｑ，ｌ，ｗ）の全てに対する次の文字列のうち、前方最長一致をとったものとなる。その文字列とはＥ1に属する遷移のうち、遷移元がｑかつ入力記号がｘであるような遷移δの出力記号の前方最長一致をとった文字列の前方に文字列ｌをつなげたものである。例えば、Γ(ｑ2,ｘ)に属する３つ組（ｑ，ｌ，ｗ）が１つだけで且つ条件を満たすδが２つあるとし、その出力記号output(δ)がＡＢとＡＣであり、文字列ｌがＰであるとすると、ｌ2に代入される文字列はＰＡとなる。
【０１２５】
次いで、決定化処理部３１は、ｑ2から入力記号ｘによって遷移する遷移先の状態ｑ'2を生成する（ステップＳ１０５）。ここで、ｑ'2を生成するには、Ｔ1の状態名と余りの文字列と余りの重みとで構成される３つ組の集合を生成しなければならない。そのうち、状態はν(ｑ2,ｘ)に属しているもので、その要素をｑ'とするものである。なお、ν(ｑ2,ｘ)＝{ｑ'|(ｑ,ｌ,ｗ)∈ｑ2,δ∈Ｅ1,prev(δ)=ｑ,input(δ)＝ｘ,next(δ)＝ｑ'}である。つまり、ｑ2に属する３つ組（ｑ，ｌ，ｗ）に関して、Ｅ1に属する遷移δのうち、遷移元の状態がｑであり、入力記号がｘであるような遷移の遷移先の状態をｑ'としたとき、この条件を満たすｑ'の集合が、ν(ｑ2,ｘ)の返す値である。
【０１２６】
３つ組の２番目の値である余りの文字列は、ｑ'に対して次のような文字列になる。その文字列とは、集合γ(ｑ2,ｘ)に属する４つ組（ｑ，ｌ，ｗ，δ）の夫々に対し、ｌの後ろにδの出力文字列を加えた文字列の前方からｌ2の文字列を除去した文字列を算出し、それらの文字列の前方最長一致をとったものとなる。ここで、γ(ｑ2,ｘ)＝{(ｑ，ｌ，ｗ，δ)∈ｑ2×Ｅ1|prev(δ)＝ｑ,input(δ)＝ｘ}である。つまり、ｑ2に含まれている３つ組（ｑ，ｌ，ｗ）のうち、入力記号がｘであり且つ遷移元がｑであるようなＥ1に属する遷移を含めた４つ組（ｑ,ｌ,ｗ,δ）の集合が、γ(ｑ2,ｘ)の返す値である。
【０１２７】
３つ組の３番目の値である余りの重みは、ｑ'に対して次のような重みとなる。その重みの値は、集合γ(ｑ2,ｘ)に属する４つ組（ｑ，ｌ，ｗ，δ）の夫々に対して、ｗにδの重みを加えｗ2を引いた値のうち、最も小さい値となる。以上の計算により生成される３つ組の集合がｑ'2となる。
【０１２８】
続くステップＳ１０６において、決定化処理部３１は、ｑ2からｑ'2への遷移をＥ2に追加する（ステップＳ１０６）。ここで追加した遷移の入力記号はｘであり、出力記号はｌ2であり、重みはｗ2である。
【０１２９】
次いで、決定化処理部３１は、ステップＳ１０５で生成したｑ'2がＱ2に含まれているか否かを判定し、含まれていると判定した場合には（ステップＳ１０７；Ｎｏ）、ステップＳ１００の処理へと再び戻る。
【０１３０】
また、ステップＳ１０５において、ｑ'2がＱ2に含まれていないと判定した場合には（ステップＳ１０７；Ｙｅｓ）、決定化処理部３１は、ｑ'2をＱ2に追加し（ステップＳ１０８）、Ｓにｑ'2を追加した後（ステップＳ１０９）、ステップＳ１００の処理へと再び戻る。
【０１３１】
一方、ステップＳ９５において、Ｓが空であると判定した場合には（ステップＳ９５；Ｎｏ）、決定化処理部３１は、Ｔ1を決定化したＴ2の状態の集合Ｑ2に属している状態の名前を付け替え（ステップＳ１１０）、本処理を終了する。
【０１３２】
つまり、名前の付け替え前はＱ2に属する状態の名前はＱ1に属する状態名と余りの出力記号と余りの重みの３つ組の集合で表現されていたが、決定化処理が完了すれば不要であるため、それを新しい名前に付け替える。新しい名前は例えば、０から順に各状態に番号を振るなどとすればよく、この処理によって記憶域を削減できる。なお，ＷＦＳＴのようにＦＳＡを拡張したモデルにおいても、名前の付け替え前のＱ2に含まれる状態のことをＦＳＡの場合と同様に「決定化済み状態」という。
【０１３３】
以上で説明した決定化処理によりＷＦＳＴを決定化した場合の一例を、図２４〜２６を用いて説明する。図２４は、決定化前の非決定性ＷＦＳＴ  Ｔ1を示した図である。同図において、「０／０」と書かれている状態が初期状態であり、「／」の左側が状態番号を、右側が初期重みを表している。また、２重丸で描かれている状態「１／０」と「２／２」はそれぞれ受理状態であり、「／」の左側が状態番号を、右側が終了重みを表している。つまり、状態１の終了重みは０で、状態２の終了重みは２であることを示している。また、各遷移に書かれている文字は「入力記号：出力記号／重み」という意味で，例えば状態０から状態１への遷移の場合、入力記号がａで出力記号がＡで重みが１であることを示している。
【０１３４】
図２５は、決定化処理のステップＳ１１０により名前の付け替えを行う直前のＷＦＳＴを示した図である。ここで、Ｂ２１で示した状態は初期状態であって、３つ組の集合は（０，ε,０）であり、初期重みは０である。つまり、このＢ２１に対応する決定化前の状態は、状態０であり、余りの出力記号は空文字列であり、余りの重みは０であることを示している。
【０１３５】
Ｂ２２で示した状態は受理状態であり、終了重みは１である。また、この状態Ｂ２２に対応する決定化前の状態１，２のうち、状態１に関する３つ組では余りの文字列が空文字列であり、余りの重みは１である。また、状態２に関する３つ組では余りの文字列が空文字列であり、余りの重みは０である。なお、他の状態Ｂ２３〜Ｂ２５についても同様である。
【０１３６】
図２６は、決定化処理のステップＳ１１０により名前の付け替えを行った後のＷＦＳＴ、つまり決定化後のＷＦＳＴを示した図である。この図２６と図２５とに含まれた状態名を比較することで、名前の付け替えにより状態名を記憶するために必要なメモリ量が減少することがわかる。例えば、図２５においてＢ２４で示した状態は「｛（０,ε,２）,（１,Ａ,１）,（２,Ａ,０）｝／１」であり、３つ組を３つ含む集合と終了重みを記憶している。一方、図２６において、Ｂ２４に対応するＢ３１で示した状態では、「３／１」となり、状態番号と終了重みを記憶するだけとなっている。
【０１３７】
しかしながら、上記した決定化処理部３１による決定化の方法のみでは、ＷＦＳＴの状態数や遷移数が増えるに伴い、決定化済み状態を記憶しておくために大きなメモリ量が必要となる。そのため、本実施形態では、部分集合生成部１２、部分決定化部３２、繰り返し処理部３３を備えることで、決定化済み状態を記憶するためのメモリ量の削減を行う。以下、部分決定化部３２、繰り返し処理部３３について説明する。
【０１３８】
部分決定化部３２は、繰り返し回数ｉに対応した入力記号の部分集合Σiに基づいて、決定化の対象とする遷移を選択するとともに、決定化の対象とならない遷移に係る入力記号を異なる入力記号に置き換え、図２３で説明した従来の決定化方法を利用することで、決定化の対象とする遷移についての決定化（部分決定化）を行う。
【０１３９】
繰り返し処理部３３は、部分決定化部３２を制御し、繰り返し総数ｎに応じた回数だけ部分決定化処理を繰り返し実行させる。
【０１４０】
次に、図２７、２８を用いて、部分決定化部３２及び繰り返し処理部３３により実行される逐次決定化処理について説明する。なお、本処理の前提として、部分集合生成部１２により部分集合Σiが予め生成されているものとする。また、逐次決定化処理の実行時に生成される、後述する各種変数は作業エリアとして機能するＲＡＭ５に一時記憶されるものとする。
【０１４１】
図２７は、本実施形態における逐次決定化処理の手順を示したフローチャートである。まず、繰り返し処理部３３は、繰り返し回数を計数するための変数ｉを１に設定すると（ステップＳ１２１）、このｉの値に応じた部分決定化処理（ステップＳ１２２）を部分決定化部３２に実行させる。以下、図２８を参照して、ステップＳ１２２の部分決定化処理について説明する。
【０１４２】
図２８は、ステップＳ１２２の部分決定化処理の手順を示したフローチャートである。まず、部分決定化部３２は、決定化の対象となる遷移、つまり遷移の入力記号がΣiに含まれている遷移の集合をＥrに代入する（ステップＳ１３１）。次いで、部分決定化部３２は、決定化の対象とならない遷移、つまり遷移の入力記号がΣiに含まれていない遷移の集合をＥdに代入する（ステップＳ１３２）。なお、Σiのｉは、ステップＳ１２１又は後述するステップＳ１２５で設定されたｉの値に対応する。
【０１４３】
続いて、部分決定化部３２は、Ｅdに属する全ての遷移δdについて、後述するステップＳ１３４、１３５の処理を施したか否かを判定する（ステップＳ１３３）。ここで、未処理の遷移δdが存在すると判定した場合（ステップＳ１３３；Ｎｏ）、部分決定化部３２は、上記した式（３）を満たすｘnew、即ち、Ｅdの遷移の入力記号が互いに異なる入力記号となり、且つ、Σiとも異なる入力記号となるような入力記号ｘnewを生成する（ステップＳ１３４）。そして、部分決定化部３２は、この生成したｘnewを遷移δdにかかる入力記号と置き換え（ステップＳ１３５）、ステップＳ１３３の処理へと再び戻る。
【０１４４】
一方、ステップＳ１３３において、Ｅdに属する全ての遷移δdについて、ステップＳ１３４、１３５の処理を施したと判定した場合には（ステップＳ１３３；Ｙｅｓ）、ステップＳ１３６の処理へと移行する。
【０１４５】
次に、部分決定化部３２は、Ｅdに属した遷移δdをＥrに追加した後（ステップＳ１３６）、このＥrを含む非決定性ＷＦＳＴ  Ｔr＝（Ｑ1，Σr，Δ,Ｅr，Ｉ1，Ｆ1,λ1,ρ1）の決定化処理を決定化処理部３１に実行させ、その結果をＴ'r（Ｔ'r＝（Ｑ2，Σr，Δ,Ｅ'r，ｉ2，Ｆ2,λ2,ρ2））に代入する（ステップＳ１３７）。ここで、Σrは入力記号を置き換えた後の入力記号の集合である。なお、ステップＳ１３７で行われる決定化処理の手順は、図２３で説明したものと同様であるため、説明を省略する。
【０１４６】
続いて、部分決定化部３２は、Ｔ'rの入力記号ΣrをステップＳ１３５で置き換える前の元の入力記号に戻した後、このＴ'rをＴ2＝（Ｑ2，Σ，Δ,Ｅ2，ｉ2，Ｆ2,λ2,ρ2）に代入し（ステップＳ１３８）、図２７のステップＳ１２３の処理へと移行する。ここでＴ2は、Ｔ1のうちΣiに属する入力記号を持つ遷移のみを決定化したＷＦＳＴとなっている。
【０１４７】
図２７に戻り、繰り返し処理部３３は、ｉの値が繰り返し回数の最大値であるｎを下回るか否かを判定する（ステップＳ１２３）。ここで、ｉの値がｎを下回ると判定した場合には（ステップＳ１２３；Ｙｅｓ）、繰り返し処理部３３は、ステップＳ１２２で決定化されたＷＦＳＴ  Ｔ2をＷＦＳＴ  Ｔ1とし（ステップＳ１２４）、ｉの値を１増やした後（ステップＳ１２５）、ステップＳ１２２の処理へと再び戻る。
【０１４８】
また、ステップＳ１２３において、ｉの値がｎ以上と判定した場合には（ステップＳ１２３；Ｎｏ）、本処理を終了する。ここで、最終的に得られたＷＦＳＴ  Ｔ2は処理対象となった非決定性ＷＦＳＴ  Ｔ1を決定化したものとなっている。
【０１４９】
上述した逐次決定化処理の動作を、図２４で示した非決定性ＷＦＳＴ  Ｔ1を基に、図２９〜３１を用いて説明する。なお、繰り返し総数ｎは２とし、部分集合生成部１２により生成された部分集合Σiが、Σ1＝｛ａ｝、Σ2＝｛ａ,ｂ｝であるものとする。
【０１５０】
まず、１回目（ｉ＝１）の決定化に関して、決定化を行い且つ状態名を置き換える前（ステップＳ１１０を実行する直前）のＷＦＳＴを図２９に示す。この図から、入力記号はａの遷移については決定化できていることが分かる。また、入力記号ｂについては、ｂ1、ｂ2という記号に置き換えられており、元に戻すとどちらもｂとなるので、入力記号ｂに係る遷移についてはまだ決定化されていないことが分かる。なお、続くステップＳ１１０の処理により状態名を付け替え、さらに続くステップＳ１３８の処理により、図２９の入力記号を元の入力記号に戻した結果のＷＦＳＴは、図３０のようになる。
【０１５１】
次に２回目（ｉ＝２）の決定化を実行する。つまり、図３０のＷＦＳＴを決定化する。この決定化の結果、図３０のＷＦＳＴは図３１のようになる。なお、図３１では状態名の付け替え前のＷＦＳＴを示している。状態名を付け替えると図２６のようになる。
【０１５２】
ところで、図２３で説明した決定化処理（従来の決定化方法）のみを用いて図２４のＷＦＳＴを決定化すると、状態名の付け替え前では図２５のように表されることは上述したとおりである。このとき、記憶しなければならない３つ組（状態名、余りの文字列、余りの重み）の数を数えると、状態Ｂ２１には｛（０，ε，０）｝で１個、状態Ｂ２２には｛（１，ε，１），（２，ε，０）｝で２個、状態Ｂ２３には｛（０，ε，０），（３，ε，１）｝で２個、状態Ｂ２４には｛（０，ε，２），（１，Ａ，１），（２，Ａ，０）｝で３個、状態Ｂ２５には｛（０，ε，０），（１，ε，１），（２，ε，０）｝で３個となり、合計１１個である。
【０１５３】
一方、図２７、２８で説明した逐次決定化処理により図２４のＷＦＳＴを決定化すると、１回目の決定化では図２９のようになり、状態Ｂ４１には｛（０，ε，０）｝で１個、状態Ｂ４２には｛（１，ε，１），（２，ε，０）｝で２個、状態Ｂ４３には｛（３，ε，０）｝で１個となり、合計４個である。また、２回目の決定化では図３１のようになり、同様に数えると合計８個となる。
【０１５４】
したがって、逐次決定化処理による決定化の方法では、決定化の際に状態名として記憶しなければならない３つ組の数は最大８個となり、決定化処理のみを用いた決定化の方法よりも合計要素数の最大値を減らすことができる。つまり、決定化済み状態の記憶に必要なメモリ量を減らすことができる。
【０１５５】
次に本実施形態にかかるオートマトン決定化装置３００の変形例として、本実施形態にかかる決定化の方法（逐次決定化処理）を音声認識装置に適用した態様について説明する。
【０１５６】
図３２は、音声認識装置５００の構成を模式的に示した図である。図３２に示したように、音声認識装置５００は、図示しないマイク等を介して入力される音声信号から音声認識に必要となる特徴量を抽出する特徴量抽出部５０１と、後述するＷＦＳＴの合成と最適化を行う合成最適化部５０２と、合成最適化部５０２で最適化されたＷＦＳＴに基づいて、抽出された特徴量を文字列へと変換するデコーダ５０３と、を備えている。
【０１５７】
また、音声認識装置５００は、図示しない記憶手段に、音響モデル５０４、単語辞書５０５、言語モデル５０６を予め夫々記憶している。ここで、音響モデル５０４にはどの音素が入力された音声信号に最も近いかを判断するための情報が保持されている。また、単語辞書５０５には各単語がどういった音素列で構成されているかが保持されている。また、言語モデル５０６には認識対象の言語においてどの単語の並びが尤もらしいかどうかを判断するための情報（スコア）が保持されている。
【０１５８】
なお、音声認識装置５００では、これら音響モデル５０４、単語辞書５０５及び言語モデル５０６は、上述したＷＦＳＴで表現されているものとする。このような音声認識装置で用いられるＷＦＳＴの作成方法の例は、Mehryar Mohri,  Michael  Riley著,  Integrated  Context-Dependent  Networks  in  Very  Large  Vocabulary  Speech  Recognition,  EUROSPEECH  '99,  Volume  2,  Page  811-814に記載されている。
【０１５９】
具体的に、音響モデル５０４には一般にＨＭＭ（Ｈｉｄｄｅｎ  Ｍａｒｋｏｖ  ｍｏｄｅｌ）が用いられるが、この場合、入力記号を遷移確率と出力確率を計算する関数の番号に、出力記号を音素にすることでＷＦＳＴとして表現できる。ただし、このＷＦＳＴの重みは入力記号で指定された番号の関数を使って動的に、つまりデコーダ５０３が特徴量を受け取ったときに計算されることになる。
【０１６０】
また、単語辞書５０５では、音素を入力記号とし、単語を出力記号としたＷＦＳＴで表現することができる。また、言語モデルでは、単語を入力記号と出力記号とし、重みとして言語モデルのスコアを用いることで表現できる。
【０１６１】
合成最適化部５０２は、複数のＷＦＳＴを１つに合成する公知の手法により、音響モデル５０４を表すＷＦＳＴ、単語辞書５０５を表すＷＦＳＴ、言語モデル５０６を表すＷＦＳＴの何れか又は全てを１つのＷＦＳＴに合成する。
【０１６２】
また、合成最適化部５０２は、合成したＷＦＳＴを含む夫々のＷＦＳＴに対して、デコーダ５０３の処理量が少なくなるように、また、デコーダ５０３で処理しやすいように最適化を行う。この最適化を行なう処理の一つに本実施形態にかかる逐次決定化処理が含まれているものとする。即ち、合成最適化部５０２には、上述した本実施形態の逐次決定化処理を実行するオートマトン決定化装置３００が含まれている。
【０１６３】
デコーダ５０３は、合成最適化部５０２で合成・最適化されたＷＦＳＴを用いて、特徴量抽出部５０１により抽出された音声信号の特徴量を文字列へと変換し、これを認識結果として出力する。文字列への変換には例えばビタビ探索を用いることができる。
【０１６４】
図３３は、合成最適化部５０２により単語辞書５０５を表すＷＦＳＴと、言語モデル５０６を表すＷＦＳＴとを合成したＷＦＳＴに対して、上述した逐次決定化処理を行なう際に必要となる記憶域の変化を示した図である。ここで、実線で示したグラフは、本実施形態の決定化の方法（逐次決定化処理）により決定化を行った結果を示している。また、比較のため、従来の決定化の方法により決定化を行った結果を破線により示している。
【０１６５】
横軸は図２３のステップＳ９５からステップＳ１０９までの処理を繰り返した回数を表しており、そのオーダーは「×１０００」となっている。言い換えると、キューＳに投入された決定化後の状態に関し、いくつの状態まで処理したかを示している。縦軸はＱ2に含まれている決定化済み状態に含まれている３つ組（状態名，余りの文字列，余りの重み）の総数を表しており、そのオーダーは「×１００００００」となっている。また、決定化を行なう前の状態数は１８６８８個であり、遷移数は２３０９３０個である。また、入力記号の数は６０個である。
【０１６６】
図３３において、従来の決定化の方法により決定化を行った結果を点線で示している。図から明らかなように、従来の決定化の方法では、処理した状態数が増えるに伴い、決定化済み状態に含まれている３つ組の総数は急激に増加し、Ｃ１１で示した点で処理が完了している。
【０１６７】
一方、本実施形態の決定化の方法（逐次決定化処理）により決定化を行った結果を実線で示している。この例では６回繰り返しており、１回の部分決定化で決定化される遷移の入力記号の数を、繰り返しのたびに１０個ずつ増やしている。決定化済み状態に含まれている３つ組の総数は単調増加せず、図２７におけるステップＳ１２２の部分決定化処理が完了するたびに、０個になる。これは決定化後、名前の置き換え処理が行なわれるためである。
【０１６８】
図３３において、Ｃ２１は一連の処理の中で１回目の部分決定化が完了した点を示しており、Ｃ２２は２回目の部分決定化が完了した点を示している。以後同様にＣ２３〜２５は、３回目〜５回目の部分決定化が完了した点を示しており、Ｃ２６は６回目の決定化が完了した点（逐次決定化処理が完了した点）を示している。
【０１６９】
この図３３から明らかなように、本実施形態にかかる決定化の方法（逐次決定化処理）では、従来の決定化の方法に比べ繰り返す回数は増えるものの、決定化済み状態を記憶しておくための記憶域を減らすことが可能である。
【０１７０】
以上のように、本実施形態によれば、非決定性ＷＦＳＴに含まれた遷移から、決定化の対象とする遷移を一部選び、この決定化対象とする遷移を毎回変えながら繰り返し決定化を行うことで、一回の決定化で記憶する決定化済み状態のうち、それを構成する３つ組の個数を減少させることができるため、決定化の実行時に要するメモリ量を減少させることができる。
【０１７１】
なお、本実施形態では、非決定性ＷＦＳＴの決定化について説明したが、これに限らず、ＷＦＳＡやＦＳＴ等のＦＳＡを拡張したオートマトンについても、本実施形態の決定化の方法を適用することが可能である。
【０１７２】
［第４の実施形態］
上述した第３の実施形態では、部分決定化処理を行う毎に入力記号の置き換えを行う態様を説明した。本実施形態では入力記号の置き換えを行うことなく、非決定性ＷＦＳＴの決定化を実現し、当該決定化に必要となるメモリ量を削減することが可能なオートマトン決定化装置４００について説明する。なお、上述した第３の実施形態と同様の構成については、同一の符号を付与しその説明を省略する。
【０１７３】
図３４は、図１に示したＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される、オートマトン決定化装置４００の機能的構成を示した図である。同図に示したように、オートマトン決定化装置４００は、部分集合生成部１２、部分決定化部４１及び繰り返し処理部３３を備えている。
【０１７４】
ここで、部分決定化部４１は、上述した決定化処理時において、決定化済み状態に含まれた非決定性ＷＦＳＴの状態が遷移元であるような遷移のうち、入力記号が同じ遷移から決定化する遷移を所定の遷移選択方法によって選択し、この選択した遷移から決定化済み状態を生成する。ここで、所定の遷移選択方法は、特に問わないものとするが、本実施形態では、第１の実施形態で説明した、部分集合Σiに基づいて行うものとする。
【０１７５】
以下、図３５〜３７を参照して、部分決定化部４１及び繰り返し処理部３３により実行される、本実施形態の逐次決定化処理について説明する。なお、本処理の前提として、部分集合生成部１２により部分集合Σiが予め生成されているものとする。
【０１７６】
図３５は、本実施形態における逐次決定化処理の手順を示したフローチャートである。まず、繰り返し処理部３３は、繰り返し回数を計数するための変数ｉを１に設定すると（ステップＳ１４１）、このｉの値に応じた部分決定化処理（ステップＳ１４２）を部分決定化部４１に実行させる。以下、図３６を参照して、ステップＳ１４２の部分決定化処理について説明する。
【０１７７】
図３６は、ステップＳ１４２の部分決定化処理の手順を示したフローチャートである。まず、部分決定化部４１は、Ｆ2を空集合とした後（ステップＳ１５１）、全ての初期状態の初期重みのうち、最も小さい値をλ2に代入する（ステップＳ１５２）。
【０１７８】
次いで、部分決定化部４１は、Ｔ1の状態名（ｑ）、文字列、重みの３つ組を要素とする集合を生成し、Ｔ2の初期状態名としてｉ2に代入する（ステップＳ１５３）。この３つ組のうち、文字列を「余りの文字列」と呼ぶこととし、ステップＳ１５３では空文字列であるεを設定する。一方、３つ組のうちの重みを「余りの重み」と呼ぶこととし、このステップではλ1(ｑ)−λ2を代入する。
【０１７９】
続いて、部分決定化部４１は、キューＳにｉ2を追加した後（ステップＳ１５４）、Ｓが空集合か否かを判定する（ステップＳ１５５）。ここで、Ｓが空でないと判定した場合には（ステップＳ１５５；Ｙｅｓ）、部分決定化部４１は、Ｓに含まれた要素を１つ取り出し、取り出した要素をｑ2に代入する（ステップＳ１５６）。
【０１８０】
次に、部分決定化部４１は、ｑ2に含まれた状態名、余りの文字列、余りの重みの３つ組の集合（ｑ，ｌ，ｗ）のうち、ｑがＴ1の受理状態の集合Ｆ1に含まれているか否かを判定する（ステップＳ１５７）。ここで、ｑがＴ1の受理状態の集合Ｆ1に含まれていないと判定した場合には（ステップＳ１５７；Ｎｏ）、ステップＳ１６０の処理へと直ちに移行する。
【０１８１】
また、ステップＳ１５７において、ｑがＴ1の受理状態の集合Ｆ1に含まれていると判定した場合には（ステップＳ１５７；Ｙｅｓ）、部分決定化部４１は、ｑ2をＴ2の受理状態の集合Ｆ2に追加する（ステップＳ１５８）。
【０１８２】
次いで、部分決定化部４１は、ｑ2に属する３つ組（ｑ，ｌ，ｗ）のｑのうち、受理状態の集合Ｆ1に含まれた全てのｑについてｗ＋ρ1(ｑ)を計算し、その最小値をｑ2の終了重みとしてρ2(ｑ2)に代入する（ステップＳ１５９）。
【０１８３】
続いて、部分決定化部４１は、集合Σに含まれたすべての要素（入力記号）について、後述するステップＳ１６１からステップＳ１７２の処理を実行したか否かを判定する（ステップＳ１６０）。ここで、Σに含まれた全ての要素（入力記号）について処理を実行したと判定した場合には（ステップＳ１６０；Ｙｅｓ）、ステップＳ１５５の処理へと再び戻る。
【０１８４】
一方、ステップＳ１６０において、未処理の要素が存在すると判定した場合には（ステップＳ１６０；Ｎｏ）、部分決定化部４１は、まだ処理していない入力記号のうちの１つをｘに代入する（ステップＳ１６１）。
【０１８５】
次に、部分決定化部４１は、ｑ2に属する３つ組（ｑ，ｌ，ｗ）の集合において、Ｅ1に属する遷移δのうち、遷移元がｑであり且つ入力記号にｘをとる遷移の集合をＥdに代入した後（ステップＳ１６２）、このＥdが空集合か否かを判定する（ステップＳ１６３）。ここで、Ｅdを空集合と判定した場合には（ステップＳ１６３；Ｎｏ）、ステップＳ１６０の処理に再び戻る。
【０１８６】
一方、ステップＳ１６３において、Ｅdが空集合でないと判定した場合（ステップＳ１６３；Ｙｅｓ）、部分決定化部４１は、Ｅdから遷移を選択する遷移選択処理（ステップＳ１６４）を実行する。以下、図３７を参照して、ステップＳ１６４の遷移選択処理について説明する。
【０１８７】
図３７は、ステップＳ１６４の遷移選択処理の手順を示したフローチャートである。まず、部分決定化部４１は、ステップＳ１６１で代入した入力記号ｘが、部分集合Σiに含まれているか否かを判定する（ステップＳ１６４１）。なお、Σiのｉは、ステップＳ１４１又は後述するステップＳ１４５で設定されたｉの値に対応する。
【０１８８】
ここで、入力記号ｘが部分集合Σiに含まれていると判定した場合には（ステップＳ１６４１；Ｙｅｓ）、遷移の集合ＥtにＥdを代入し（ステップＳ１６４２）、図３６のステップＳ１６５の処理へと移行する。
【０１８９】
一方、ステップＳ１６４１において、入力記号ｘが部分集合Σiに含まれないと判定した場合には（ステップＳ１６４１；Ｎｏ）、Ｅdから任意の遷移を一つ取り出し、遷移の集合Ｅtに代入した後（ステップＳ１６４３）、図３６のステップＳ１６５の処理へと移行する。
【０１９０】
図３６に戻り、部分決定化部４１は、ステップＳ１６４で選択した遷移の集合Ｅtに属する遷移をＥdから除去する（ステップＳ１６５）。
【０１９１】
続いて、部分決定化部４１は、遷移元がｑ2で入力記号がｘである遷移の重みを算出し、この算出結果をｗ2に代入する（ステップＳ１６６）。ここで代入されるｗ2の値は、Γ'(ｑ2,ｘ)に属する３つ組（ｑ，ｌ，ｗ）の全てに対する次の値のうち最も小さい値となる。その値とは、Ｅtに属する遷移のうち、遷移元がｑ且つ入力記号がｘであるような遷移δの重みのうちで最も小さい値にｗを足した値である。なお、Γ'(ｑ2,ｘ)＝{(ｑ，ｌ，ｗ)∈ｑ2｜δ∈Ｅt,prev(δ)＝ｑ,input(δ)＝ｘ}である。
【０１９２】
次に、部分決定化部４１は、遷移元がｑ2で入力記号がｘである遷移の出力記号を算出し、この算出結果をｌ2に代入する（ステップＳ１６７）。ここで代入されるｌ2の値は、Γ'(ｑ2,ｘ)に属する３つ組（ｑ，ｌ，ｗ）の全てに対する次の文字列のうち、前方最長一致をとったものとなる。その文字列とはＥtに属する遷移のうち、遷移元がｑかつ入力記号がｘであるような遷移δの出力記号の前方最長一致をとった文字列の前方に文字列ｌをつなげたものである。例えば、Γ'(ｑ2,ｘ)に属する３つ組（ｑ，ｌ，ｗ）が１つだけで且つ条件を満たすδが２つあるとし、その出力記号output(δ)がＡＢとＡＣであり、文字列ｌがＰであるとすると、ｌ2に代入される文字列はＰＡとなる。
【０１９３】
次いで、部分決定化部４１は、ｑ2から入力記号ｘによって遷移する遷移先の状態ｑ'2を生成する（ステップＳ１６８）。ここで、ｑ'2を生成するには、Ｔ1の状態名と余りの文字列と余りの重みとで構成される３つ組の集合を生成しなければならない。そのうち、状態はν'(ｑ2,ｘ)に属しているもので、その要素をｑ'とするものである。なお、ν'(ｑ2,ｘ)＝{ｑ'|(ｑ,ｌ,ｗ)∈ｑ2,δ∈Ｅt,prev(δ)=ｑ,input(δ)＝ｘ,next(δ)＝ｑ'}である。つまり、ｑ2に属する３つ組（ｑ，ｌ，ｗ）に関して、Ｅtに属する遷移δのうち、遷移元の状態がｑであり、入力記号がｘであるような遷移の遷移先の状態をｑ'としたとき、この条件を満たすｑ'の集合が、ν'(ｑ2,ｘ)の返す値である。
【０１９４】
３つ組の２番目の値である余りの文字列は、ｑ'に対して次のような文字列になる。その文字列とは、集合γ'(ｑ2,ｘ)に属する４つ組（ｑ，ｌ，ｗ，δ）の夫々に対し、ｌの後ろにδの出力文字列を加えた文字列の前方からｌ2の文字列を除去した文字列を算出し、それらの文字列の前方最長一致をとったものとなる。ここで、γ'(ｑ2,ｘ)＝{(ｑ，ｌ，ｗ，δ)∈ｑ2×Ｅt|prev(δ)＝ｑ,input(δ)＝ｘ}である。つまり、ｑ2に含まれている３つ組（ｑ，ｌ，ｗ）のうち、入力記号がｘであり且つ遷移元がｑであるようなＥtに属する遷移を含めた４つ組（ｑ,ｌ,ｗ,δ）の集合が、γ'(ｑ2,ｘ)の返す値である。
【０１９５】
３つ組の３番目の値である余りの重みは、ｑ'に対して次のような重みとなる。その重みの値は、集合γ'(ｑ2,ｘ)に属する４つ組（ｑ，ｌ，ｗ，δ）の夫々に対して、ｗにδの重みを加えｗ2を引いた値のうち、最も小さい値となる。以上の計算により生成される３つ組の集合がｑ'2となる。
【０１９６】
続くステップＳ１６９において、部分決定化部４１は、ｑ2からｑ'2への遷移をＥ2に追加する（ステップＳ１６９）。ここで追加した遷移の入力記号はｘであり、出力記号はｌ2であり、重みはｗ2である。
【０１９７】
次いで、部分決定化部４１は、ステップＳ１６８で生成したｑ'2がＱ2に含まれているか否かを判定し、含まれていると判定した場合には（ステップＳ１７０；Ｎｏ）、ステップＳ１６３の処理へと再び戻る。
【０１９８】
また、ステップＳ１７０において、ｑ'2がＱ2に含まれていないと判定した場合には（ステップＳ１７０；Ｙｅｓ）、部分決定化部４１は、ｑ'2をＱ2に追加し（ステップＳ１７１）、Ｓにｑ'2を追加した後（ステップＳ１７２）、ステップＳ１６３の処理へと再び戻る。
【０１９９】
一方、ステップＳ１５５において、Ｓを空集合と判定した場合には（ステップＳ１５５；Ｎｏ）、部分決定化部４１は、Ｔ1を決定化したＴ2の状態の集合Ｑ2に属している状態の名前を付け替え（ステップＳ１７３）、図３５のステップＳ１４３の処理へと移行する。
【０２００】
図３５に戻り、繰り返し処理部３３は、ｉの値が繰り返し回数の最大値であるｎを下回るか否かを判定する（ステップＳ１４３）。ここで、ｉの値がｎを下回ると判定した場合には（ステップＳ１４３；Ｙｅｓ）、繰り返し処理部３３は、ステップＳ１４２で決定化されたＷＦＳＴ  Ｔ2をＷＦＳＴ  Ｔ1とし（ステップＳ１４４）、ｉの値を１増やした後（ステップＳ１４５）、ステップＳ１４２の処理へと再び戻る。
【０２０１】
また、ステップＳ１４３において、ｉの値がｎ以上と判定した場合には（ステップＳ１４３；Ｎｏ）、本処理を終了する。ここで、最終的に得られたＷＦＳＴ  Ｔ2は処理対象となった非決定性ＷＦＳＴ  Ｔ1を決定化したものとなっている。
【０２０２】
以上のように、本実施形態によれば、非決定性ＷＦＳＴに含まれた遷移から、決定化の対象とする遷移を一部選び、この決定化対象とする遷移を毎回変えながら繰り返し決定化を行うことで、一回の決定化で記憶する決定化済み状態のうち、それを構成する３つ組の個数を減少させることができるため、決定化の実行時に要するメモリ量を減少させることができる。
【０２０３】
また、本実施形態によれば、決定化の対象とする遷移を直接指定することができるため、入力記号による遷移の選択以外の方法でも決定化の対象となる遷移を選択することができる。
【０２０４】
なお、本実施形態では、非決定性ＷＦＳＴの決定化について説明したが、これに限らず、ＷＦＳＡやＦＳＴ等のＦＳＡを拡張したオートマトンについても、本実施形態の決定化の方法を適用することが可能である。
【０２０５】
以上、発明の実施の形態について説明したが、本発明はこれに限定されるものではなく、本発明の主旨を逸脱しない範囲での種々の変更、置換、追加などが可能である。
【図面の簡単な説明】
【０２０６】
【図１】オートマトン決定化装置のハードウェア構成を示した図である。
【図２】オートマトン決定化装置の機能的構成の一例を示した図である。
【図３】有限オートマトンの一例を示した図である。
【図４】有限オートマトンの遷移表の一例を示した図である。
【図５】決定化処理の手順の一例を示したフローチャートである。
【図６】有限オートマトンの一例を示した図である。
【図７】有限オートマトンの遷移表の一例を示した図である。
【図８】有限オートマトンの一例を示した図である。
【図９】部分集合生成処理の手順の一例を示したフローチャートである。
【図１０】逐次決定化処理の手順の一例を示したフローチャートである。
【図１１】部分決定化処理の手順の一例を示したフローチャートである。
【図１２】逐次決定化処理の動作を説明するための図である。
【図１３】逐次決定化処理の動作を説明するための図である。
【図１４】逐次決定化処理の動作を説明するための図である。
【図１５】逐次決定化処理の動作を説明するための図である。
【図１６】逐次決定化処理の動作を説明するための図である。
【図１７】逐次決定化処理の動作を説明するための図である。
【図１８】オートマトン決定化装置の機能的構成の一例を示した図である。
【図１９】逐次決定化処理の手順の一例を示したフローチャートである。
【図２０】部分決定化処理の手順の一例を示したフローチャートである。
【図２１】遷移選択処理の手順の一例を示したフローチャートである。
【図２２】オートマトン決定化装置の機能的構成の一例を示した図である。
【図２３】決定化処理の手順の一例を示したフローチャートである。
【図２４】重み付き有限状態トランスデューサの一例を示した図である。
【図２５】重み付き有限状態トランスデューサの一例を示した図である。
【図２６】重み付き有限状態トランスデューサの一例を示した図である。
【図２７】逐次決定化処理の手順の一例を示したフローチャートである。
【図２８】部分決定化処理の手順の一例を示したフローチャートである。
【図２９】逐次決定化処理の動作を説明するための図である。
【図３０】逐次決定化処理の動作を説明するための図である。
【図３１】逐次決定化処理の動作を説明するための図である。
【図３２】音声認識装置の構成を模式的に示した図である。
【図３３】逐次決定化処理時に必要となる記憶域の変化を示した図である。
【図３４】オートマトン決定化装置の機能的構成の一例を示した図である。
【図３５】逐次決定化処理の手順の一例を示したフローチャートである。
【図３６】部分決定化処理の手順の一例を示したフローチャートである。
【図３７】遷移選択処理の手順の一例を示したフローチャートである。
【符号の説明】
【０２０７】
１００  オートマトン決定化装置
２００  オートマトン決定化装置
３００  オートマトン決定化装置
４００  オートマトン決定化装置
１  ＣＰＵ
２  操作部
３  表示部
４  ＲＯＭ
５  ＲＡＭ
６  記憶部
７  バス
１１  決定化処理部
１２  部分集合生成部
１３  部分決定化部
１４  繰り返し処理部
２１  部分決定化部
３１  決定化処理部
３２  部分決定化部
３３  繰り返し処理部
４１  部分決定化部
５００  音声認識装置
５０１  特徴量抽出部
５０２  合成最適化部
５０３  デコーダ
５０４  音響モデル
５０５  単語辞書
５０６  言語モデル
【図１】
0004956334.tif 000005
【図２】
0004956334.tif 000006
【図３】
0004956334.tif 000007
【図４】
0004956334.tif 000008
【図５】
0004956334.tif 000009
【図６】
0004956334.tif 000010
【図７】
0004956334.tif 000011
【図８】
0004956334.tif 000012
【図９】
0004956334.tif 000013
【図１０】
0004956334.tif 000014
【図１１】
0004956334.tif 000015
【図１２】
0004956334.tif 000016
【図１３】
0004956334.tif 000017
【図１４】
0004956334.tif 000018
【図１５】
0004956334.tif 000019
【図１６】
0004956334.tif 000020
【図１７】
0004956334.tif 000021
【図１８】
0004956334.tif 000022
【図１９】
0004956334.tif 000023
【図２０】
0004956334.tif 000024
【図２１】
0004956334.tif 000025
【図２２】
0004956334.tif 000026
【図２３】
0004956334.tif 000027
【図２４】
0004956334.tif 000028
【図２５】
0004956334.tif 000029
【図２６】
0004956334.tif 000030
【図２７】
0004956334.tif 000031
【図２８】
0004956334.tif 000032
【図２９】
0004956334.tif 000033
【図３０】
0004956334.tif 000034
【図３１】
0004956334.tif 000035
【図３２】
0004956334.tif 000036
【図３３】
0004956334.tif 000037
【図３４】
0004956334.tif 000038
【図３５】
0004956334.tif 000039
【図３６】
0004956334.tif 000040
【図３７】
0004956334.tif 000041