(57)【特許請求の範囲】
【請求項１】
有限状態オートマトンに含まれる第１状態から出て行く遷移であって、第１記号が割り当てられている第１遷移が２以上存在する場合に、新たな第２状態を生成する状態生成ステップと、
前記第１状態から前記第２状態への遷移であって、前記第１記号が割り当てられた第２遷移を生成する第１遷移生成ステップと、
前記第１遷移それぞれに対して、前記第１遷移の次の状態から出て行く遷移である第３遷移の前の状態を前記第２状態に置き換えた第４遷移を生成する第２遷移生成ステップと、
前記第２状態が生成されるごとに、前記第１遷移の次の状態であって、前記第１遷移以外に入ってくる遷移が存在しないという条件を判定し、前記条件が満たされる場合に、当該第１遷移の次の状態を削除するとともに削除した状態から出て行く遷移を削除し、さらに前記第２状態が生成されるごとに、前記第１遷移を削除する、第１削除ステップと、
を含むことを特徴とするオートマトン決定化方法。
【請求項２】
前記第１削除ステップは、前記条件を判定する処理、および、前記条件が満たされる場合に、当該第１遷移の次の状態を削除するとともに削除した状態から出て行く遷移を削除する処理を、前記第１遷移の次の状態すべてについて実行すること、
を特徴とする請求項１に記載のオートマトン決定化方法。
【請求項３】
前記第３遷移と前記第４遷移とを関連づける第１関連づけステップと、
前記第１遷移生成ステップにより前記第２遷移を生成するときに、前記第１遷移に他の遷移が関連づけられている場合に、生成された前記第２遷移と前記他の遷移とを関連づける第２関連づけステップと、
前記有限状態オートマトンに含まれる２つの状態が、前記状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、２つの前記状態が等価であると判定する判定ステップと、
等価であると判定された２つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、
を特徴とする請求項１に記載のオートマトン決定化方法。
【請求項４】
前記基準は、前記一方の状態から出て行く遷移に関連づけられているすべての遷移と、前記他方の状態から出て行く遷移に関連づけられているすべての遷移と、が一致することを定める基準であること、
を特徴とする請求項３に記載のオートマトン決定化方法。
【請求項５】
前記第１遷移の次の状態と前記第２状態とを関連づける第３関連づけステップと、
前記状態生成ステップにより前記第２状態を生成するときに、前記第１遷移の次の状態に他の状態が関連づけられている場合に、生成された前記第２状態と前記他の状態とを関連づける第４関連づけステップと、
前記有限状態オートマトンに含まれる２つの状態が、前記状態に関連づけられた状態についての予め定められた基準を満たす場合に、２つの前記状態が等価であると判定する判定ステップと、
等価であると判定された２つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、
を特徴とする請求項１に記載のオートマトン決定化方法。
【請求項６】
前記基準は、前記一方の状態に関連づけられているすべての状態と、前記他方の状態に関連づけられているすべての状態と、が一致することを定める基準であること、
を特徴とする請求項５に記載のオートマトン決定化方法。
【請求項７】
前記有限状態オートマトンは、重み付き有限状態オートマトンであり、
前記第１遷移それぞれの重みから予め定められた演算により算出される重みの最良値である、前記第２遷移の重みを算出する重み算出ステップをさらに含むこと、
を特徴とする請求項１に記載のオートマトン決定化方法。
【請求項８】
前記第３遷移と前記第４遷移とを関連づけるとともに、前記第４遷移の重みを関連づけに割り当てる第５関連づけステップと、
前記第１遷移生成ステップにより前記第２遷移を生成するときに、前記第１遷移に他の遷移が関連づけられている場合に、生成された前記第２遷移と前記他の遷移とを関連づける第６関連づけステップと、
前記重み付き有限状態オートマトンに含まれる２つの状態が、前記状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、２つの前記状態が等価であると判定する判定ステップと、
等価であると判定された２つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、
を特徴とする請求項７に記載のオートマトン決定化方法。
【請求項９】
前記基準は、前記一方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの重みと、前記他方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの重みと、が一致することを定める基準であること、
を特徴とする請求項８に記載のオートマトン決定化方法。
【請求項１０】
前記有限状態オートマトンは、有限状態トランスデューサであり、
前記第１遷移それぞれの出力記号列の最長前方一致の記号列である、前記第２遷移の出力記号列を算出する記号列算出ステップをさらに含むこと、
を特徴とする請求項１に記載のオートマトン決定化方法。
【請求項１１】
前記第３遷移と前記第４遷移とを関連づけるとともに、前記第４遷移の出力記号列を関連づけに割り当てる第７関連づけステップと、
前記第１遷移生成ステップにより前記第２遷移を生成するときに、前記第１遷移に他の遷移が関連づけられている場合に、生成された前記第２遷移と前記他の遷移とを関連づける第８関連づけステップと、
前記有限状態トランスデューサに含まれる２つの状態が、前記状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、２つの前記状態が等価であると判定する判定ステップと、
等価であると判定された２つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、
を特徴とする請求項１０に記載のオートマトン決定化方法。
【請求項１２】
前記基準は、前記一方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの出力記号列と、前記他方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの出力記号列と、が一致することを定める基準であること、
を特徴とする請求項１１に記載のオートマトン決定化方法。
【請求項１３】
初期状態から到達できない状態と遷移とを、予め定められた頻度で削除する第２削除ステップをさらに含むこと、
を特徴とする請求項１に記載のオートマトン決定化方法。
【請求項１４】
前記第２削除ステップは、１つの前記第１状態について、前記状態生成ステップ、前記第１遷移生成ステップ、前記第２遷移生成ステップ、および、前記第１削除ステップのうちいずれかが完了するごとに、初期状態から到達できない状態と遷移とを削除すること、
を特徴とする請求項１３に記載のオートマトン決定化方法。
【請求項１５】
有限状態オートマトンに含まれる第１状態から出て行く遷移であって、第１記号が割り当てられている第１遷移が２以上存在する場合に、新たな第２状態を生成する状態生成部と、
前記第１状態から前記第２状態への遷移であって、前記第１記号が割り当てられた第２遷移を生成する第１遷移生成部と、
前記第１遷移それぞれに対して、前記第１遷移の次の状態から出て行く遷移である第３遷移の前の状態を前記第２状態に置き換えた第４遷移を生成する第２遷移生成部と、
前記第２状態が生成されるごとに、前記第１遷移の次の状態であって、前記第１遷移以外に入ってくる遷移が存在しないという条件を判定し、前記条件が満たされる場合に、当該第１遷移の次の状態を削除するとともに削除した状態から出て行く遷移を削除し、さらに前記第２状態が生成されるごとに、前記第１遷移を削除する、削除部と、
を備えることを特徴とするオートマトン決定化装置。
【請求項１６】
コンピュータに、
有限状態オートマトンに含まれる第１状態から出て行く遷移であって、第１記号が割り当てられている第１遷移が２以上存在する場合に、新たな第２状態を生成する状態生成ステップと、
前記第１状態から前記第２状態への遷移であって、前記第１記号が割り当てられた第２遷移を生成する第１遷移生成ステップと、
前記第１遷移それぞれに対して、前記第１遷移の次の状態から出て行く遷移である第３遷移の前の状態を前記第２状態に置き換えた第４遷移を生成する第２遷移生成ステップと、
前記第２状態が生成されるごとに、前記第１遷移の次の状態であって、前記第１遷移以外に入ってくる遷移が存在しないという条件を判定し、前記条件が満たされる場合に、当該第１遷移の次の状態を削除するとともに削除した状態から出て行く遷移を削除し、さらに前記第２状態が生成されるごとに、前記第１遷移を削除する、第１削除ステップと、
を実行させるためのオートマトン決定化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、オートマトン決定化方法、オートマトン決定化装置およびオートマトン決定化プログラムに関する。
【背景技術】
【０００２】
有限状態オートマトン（Finite  State  Automaton、ＦＳＡ）は自然言語処理や音声認識等さまざまな分野で利用されている。例えば、文章中に表れる特定の文字列や文字列のパターンを検索するなどの用途がある。ＦＳＡは有限オートマトン（Finite  Automaton、ＦＡ）や有限状態機械（Finite  State  Machine、ＦＳＭ）と呼ばれることもある。
【０００３】
ＦＳＡにはいくつか種類が存在する。例えば、ＦＳＡには、有限状態アクセプタ（Finite  State  Acceptor）、有限状態トランスデューサ（Finite  State  Transducer、ＦＳＴ）、重み付き有限状態アクセプタ（Weighted  Finite  State  Acceptor、ＷＦＳＡ）、および、重み付き有限状態トランスデューサ（Weighted  Finite  State  Transducer、  ＷＦＳＴ）が存在する。有限状態アクセプタは、入力された記号列を受け付けるか否かのみを出力することができる。有限状態トランスデューサは、入力された記号列に応じた記号列を出力する。重み付き有限状態アクセプタは、入力された記号列に応じた重みを出力する。重み付き有限状態トランスデューサは、入力された記号列に応じた重みと記号列を出力する。
【０００４】
ここで、重みは確率や距離などであっても良い。有限状態アクセプタについてはこれ以降、単にアクセプタと呼ぶこととする。また、一般に有限状態アクセプタを有限状態オートマトン（ＦＳＡ）と呼ぶことがある。以下ではＦＳＡを、アクセプタ、ＦＳＴ、ＷＦＳＴ、および、ＷＦＳＡなどの総称として用いることとする。
【０００５】
ＦＳＴは、例えば音声認識における単語辞書に用いられることがある。そのような単語辞書は、発音を入力するとそれに対応する単語を出力するＦＳＴとして構成される。ＷＦＳＡやＷＦＳＴは、音声認識における言語モデルなどの音声認識に必要な辞書やモデルを表現するためのモデルとして用いられることや、統計的機械翻訳で用いられることがある。
【０００６】
以上で説明したように、ＦＳＡを実際にそれぞれの応用で用いるとき、必要な情報をＦＳＡに変換する必要がある。通常このような変換は、簡単な変換手順で実施され、それによって得られたＦＳＡはその後の処理に適した構造でないことが多い。そのため、必要に応じてＦＳＡを変換することがある。そのような変換の一つが次に述べる決定化である。
【０００７】
決定性有限状態オートマトン（Deterministic  Finite  State  Automaton、ＤＦＳＡ）とは、ある入力記号が入力されたときにいずれの状態においても次の状態が一意に決まるＦＳＡのことを言う。非決定性有限状態オートマトン（Nondeterministic  Finite  State  Automaton、ＮＦＳＡ）とは、ＤＦＳＡでないＦＳＡである。すなわち、ＮＦＳＡは、ある入力記号に対する次の状態が複数存在するような状態を含むＦＳＡである。決定化（determinization）とはＮＦＳＡをＤＦＳＡへ変換することをいう。アクセプタの決定化には例えばサブセット構成法（Subset  Construction）が用いられる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許第６、２４３、６７９号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、従来技術では、ＮＦＳＡを記憶領域に保ったまま、ＤＦＳＡを新たに生成する方法が用いられている。このような方法では、状態や遷移を多量に含んでいるＮＦＳＡを決定化しようとした場合に多くの記憶領域が必要になるという問題があった。
【課題を解決するための手段】
【００１０】
実施形態のオートマトン決定化方法は、状態生成ステップと、第１遷移生成ステップと、第２遷移生成ステップと、第１削除ステップと、を含む。状態生成ステップは、有限状態オートマトンに含まれる第１状態から出て行く遷移であって、第１記号が割り当てられている第１遷移が２以上存在する場合に、新たな第２状態を生成する。第１遷移生成ステップは、第１状態から第２状態への遷移であって、第１記号が割り当てられた第２遷移を生成する。第２遷移生成ステップは、第１遷移それぞれに対して、第１遷移の次の状態から出て行く遷移である第３遷移の前の状態を第２状態に置き換えた第４遷移を生成する。第１削除ステップは、第４遷移を生成した第１遷移の次の状態であって、第１遷移以外に入ってくる遷移が存在しない状態を削除し、削除した状態から出て行く遷移を削除し、第４遷移を生成した第１遷移を削除する。
【図面の簡単な説明】
【００１１】
【図１】音声認識装置のブロック図。
【図２】決定化部のブロック図。
【図３】決定化処理のフローチャート。
【図４】ＷＦＳＡの決定化処理の擬似コードの一例を示す図。
【図５】関数ｍｅｒｇｅＩｎｉｔｉａｌｓの擬似コードの一例を示す図。
【図６】関数ｍｅｒｇｅＴｒａｎｓｉｔｉｏｎｓの擬似コードの一例を示す図。
【図７】関数ｍｅｒｇｅＷｅｉｇｈｔの擬似コードの一例を示す図。
【図８】第１の実施形態の関数ｒｅｃｏｎｎｅｃｔの擬似コードの一例を示す図。
【図９】決定化する非決定性ＷＦＳＡの一例を示す図。
【図１０】決定化処理途中のＷＦＳＡの一例を示す図。
【図１１】決定化処理途中のＷＦＳＡの一例を示す図。
【図１２】決定化処理途中のＷＦＳＡの一例を示す図。
【図１３】決定化処理途中のＷＦＳＡの一例を示す図。
【図１４】決定化処理途中のＷＦＳＡの一例を示す図。
【図１５】決定化処理途中のＷＦＳＡの一例を示す図。
【図１６】決定化処理途中のＷＦＳＡの一例を示す図。
【図１７】決定化処理途中のＷＦＳＡの一例を示す図。
【図１８】音声認識装置のハードウェア構成図。
【図１９】第２の実施形態の関数ｒｅｃｏｎｎｅｃｔの擬似コードの一例を示す図。
【図２０】第３の実施形態の関数ｒｅｃｏｎｎｅｃｔの擬似コードの一例を示す図。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、この発明にかかるオートマトン決定化装置の好適な実施形態を詳細に説明する。
（第１の実施形態）
第１の実施形態にかかるオートマトン決定化装置は、ＮＦＳＡを変形することにより決定化を行う。同じ記憶領域でより多くの状態や遷移を含んだＮＦＳＡを決定化するために、ＮＦＳＡに含まれる状態や遷移のうち、決定化にとって不要となった状態や遷移を記憶領域から逐次削除することによって決定化に必要となる記憶領域を減らす。これにより、より少ない記憶領域で有限状態オートマトンの決定化を行うことができる。特に、ある入力記号に対する次の状態が複数存在するような状態、すなわち、非決定性の状態の全体に占める割合が少ないＮＦＳＡを決定化するときの記憶領域の削減に効果的である。
【００１３】
（準備）
ＷＦＳＡは、状態の集合Ｑと遷移の集合Ｅ、入力記号の集合Σ、重みの集合Ｋ、初期状態の集合Ｉ、終了状態の集合Ｆ、初期重み関数λ、終了重み関数ρを含む８つ組（Ｑ，Ｅ，Σ，Ｋ，Ｉ，Ｆ，λ，ρ）から構成される。遷移は４つ組（前状態，入力記号，重み，次状態）で構成される。集合Ｋは、整数全体からなる集合、実数全体からなる集合、複素数全体からなる集合、行列、ブーリアン（０と１のみ）から成る集合、および、文字列から成る集合など様々な集合に対応させることができる。集合Ｋは、正でない実数からなる集合や負でない実数からなる集合などに対応させることもできる。初期状態ｑｉ∈Ｉに対応する初期重みはλ（ｑｉ）となる。同様に終了状態ｑｆ∈Ｆに対応する終了重みはρ（ｑｆ）となる。終了状態でない状態ｑがρの引数に与えられた場合は、集合Ｋに含まれない値を返し、その値は終了状態でないすべての状態に対して同じ値であるとする。これら８つの集合は本実施形態での決定化の対象となるＷＦＳＡを構成する情報としてすべての方法（擬似コード）から常に参照することができるものとする。
【００１４】
ＷＦＳＡの決定化を行うには集合Ｋに対し２つの２項演算（＋）と（×）、さらに定数０＃と１＃を定義できる必要がある。ここではこのような演算と定数を伴う集合Ｋが、半環（semiring）と呼ばれる条件を満たしているものとする。さらに、ａ（＋）ｂ≠０＃を満たす任意のａ，ｂ∈Ｋに対して、ｃ＝（ａ（＋）ｂ）−１（×）ａとなるようなｃが存在する必要がある。なお、ｘの逆元をｘ−１と書く。すなわち、ｘ−１（×）ｘ＝１＃である。集合Ｋが半環であるとは次の（１）〜（４）の４つの条件を満たすことを意味する。
（１）Ｋが演算（＋）に対して可換モノイドであり、その単位元が０＃である。
（２）Ｋが演算（×）に対してモノイドであり、その単位元が１＃である。
（３）任意のｘ，ｙ，ｚ∈Ｋに対して分配法則が成り立つ。すなわち、
ｘ（×）（ｙ（＋）ｚ）＝（ｘ（×）ｙ）（＋）（ｘ（×）ｚ）と、
（ｙ（＋）ｚ）（×）ｘ＝（ｙ（×）ｘ）（＋）（ｚ（×）ｘ）と、を満たす。
（４）任意のｘ∈Ｋに対して、０＃（×）ｘ＝ｘ（×）０＃＝０＃が成り立つ。
【００１５】
上記のような条件を満たす半環には、例えばトロピカル半環（tropical  semiring、または、min-plus  semiring）と呼ばれるものが存在する。トロピカル半環は、集合Ｋが０以上の実数Ｒ＋に無限大（∞）を加えた集合である。トロピカル半環は、（＋）がｍｉｎ、（×）が＋、０＃が∞、１＃が０であるような演算と定数を伴う。集合Ｋが０以上の整数Ｎ＋に∞を加えた集合も同様にトロピカル半環と呼ばれる。
【００１６】
集合Ｋが０以下の実数Ｒ−に−∞を加えた集合で（＋）がｍａｘ、（×）が＋、０＃が−∞、１＃が０であるような半環や、トロピカル半環の（＋）の計算をｘ（＋）ｙ＝−ｌｏｇ（ｅ−ｘ＋ｅ−ｙ）に置き換えた対数半環（log  semiring）も条件を満たす。集合Ｋが文字列で、（＋）が前方最長一致（longest  common  prefix）、（×）が連結、１＃が空文字列（εと書く）、０＃がτであるような文字列半環（string  semiring）も条件を満たす。ここでτは、任意の文字列ｘに対してｘ（＋）τ＝τ（＋）ｘ＝ｘとなるような文字列であり、εはε（×）ｘ＝ｘ（×）ε＝ｘとなるような文字列であるとする。逆元も定義でき、任意の文字列ｘ、ｙに対して、ｘ−１（×）（ｘ（×）ｙ）＝ｙとなる。文字列半環を用いることで、ＦＳＴをＷＦＳＡと同様に扱うことができる。他にも様々な半環が知られている。
【００１７】
ＷＦＳＴの場合はＦＳＴに重みが加わっているが、上記条件を満たす半環と文字列半環とを組み合わせた半環を用いることでＷＦＳＡと同様に扱うことができる。例えば、重みにトロピカル半環、出力文字列に文字列半環を用いる場合には、集合Ｋを重みの集合（Ｒ＋∪｛∞｝）と文字列の集合Σ＊との組み合わせとする。そして、任意の重みａ，ｂ∈（Ｒ＋∪｛∞｝）と文字列ｘ，ｙ∈Σ＊に対して（＋）を（ａ，ｘ）（＋）（ｂ，ｙ）＝（ａ（＋）ｂ，ｘ（＋）ｙ）、（×）を（ａ，ｘ）（×）（ｂ，ｙ）＝（ａ（×）ｂ，ｘ（×）ｙ）、０＃＝（∞，τ）、１＃＝（０，ε）のように定義することで、ＷＦＳＴをＷＦＳＡの場合と同様に扱うことができる。
【００１８】
遷移ｅの前状態はｐ（ｅ）、次状態はｎ（ｅ）、入力記号はｉｎ（ｅ）、重みはｗ（ｅ）で表す。遷移の集合Ｅに含まれる遷移の次状態から成る集合をｎ（Ｅ）で表す。
【００１９】
空集合はφまたは｛｝と書く。集合Ｂの要素の数は｜Ｂ｜と書く。差集合は＼で表す。例えば｛１、２｝＼｛２｝＝｛１｝である。集合Ｗの各要素について演算（＋）を行うことを以下の数１で表す。
【数１】
0005554304.tif 000002
【００２０】
各要素をｗ１，ｗ２，ｗ３，・・・，ｗ｜Ｗ｜とするとき、ｗ１（＋）ｗ２（＋）ｗ３（＋）・・・（＋）ｗ｜Ｗ｜と書くことと同じである。
【００２１】
重みの最良値とは、対象となる重みの各要素について演算（＋）を行った結果である。対象となる重みが同じであっても使用する半環が異なると重みの最良値が異なる値になることがある。例えば重みの集合｛１，２，３｝に対して（＋）がｍｉｎであるような半環を用いている場合は、重みの最良値は１になる。（＋）がｍａｘであるような半環を用いている場合は重みの最良値は３になる。
【００２２】
（方法の概要）
以下では、オートマトン決定化装置を音声認識装置に適用した例を説明するが、適用可能な装置はこれに限られるものではない。また、以下では、ＷＦＳＡを対象とした決定化方法を例に説明するが、他のＦＳＡについても同様の手順を適用できる。図１は、音声認識装置１００の構成例を示すブロック図である。図１に示すように、音声認識装置１００は、モデル生成部１１０と、音声認識部１３０と、音響モデル１２１と、単語辞書１２２と、言語モデル１２３と、を備えている。
【００２３】
音声認識部１３０は、入力された音声を認識し、音声認識結果を出力する。音声認識部１３０は、音声取得部１３１と、特徴抽出部１３２と、デコード部１３３と、ラティス処理部１３４と、出力部１３５と、を備えている。音声取得部１３１は、各種記憶装置（図示せず）に記録された音声、マイクからの入力音声、および、通信回線から入力される音声などを取り込み、特徴抽出部１３２に取り込んだ音声を渡す。特徴抽出部１３２は、受け取った音声から音声の特徴量を抽出してデコード部１３３に渡す。デコード部１３３は、モデル生成部１１０が生成したモデルを用いて、受け取った特徴量をデコードし、デコードの結果をラティス（単語ラティスや音素ラティスなど）としてラティス処理部１３４に渡す。
【００２４】
ラティス処理部１３４は、決定化部１１３を備えている。ラティスはＦＳＡの一種であるので、ラティス処理部１３４は必要に応じて決定化部１１３を用いて決定化を行う。ラティス処理部１３４は、例えばラティス中で認識結果として最も尤もらしい系列を求め、それを認識結果として出力部１３５に渡す。出力部１３５は、受け取った認識結果を、画面等を用いてユーザに出力（提示）する。
【００２５】
音響モデル１２１は、特徴抽出部１３２が抽出する特徴量に対応する音素を見つけるための情報を記録する。単語辞書１２２は、音素列と単語との対応付けを記録する。言語モデル１２３は、単語列の尤もらしい並びを見つけるための情報を記録する。認識できる単語の並びを表す文法を言語モデル１２３の代わりに用いるように構成しても良い。
【００２６】
モデル生成部１１０は、デコード部１３３で用いるためのＷＦＳＴで表現されたモデルを生成する。モデル生成部１１０は、音響モデル１２１、単語辞書１２２、および、言語モデル１２３を入力とし、入力されたモデルをＷＦＳＴに変換したモデルを生成する。単語辞書から変換されたＷＦＳＴの入力記号には音素、出力記号には単語、重みには例えば０が割り当てられる。言語モデルから変換されたＷＦＳＴの入力記号と出力記号には単語が、重みには単語列の尤もらしい並びを見つけるための値が割り当てられる。
【００２７】
モデル生成部１１０は、モデル変換部１１１と、合成部１１２と、決定化部１１３と、最小化部１１４と、を備えている。
【００２８】
モデル変換部１１１は、入力されたモデル（音響モデル１２１、単語辞書１２２、言語モデル１２３）をＷＦＳＴへと変換する。合成部１１２は、変換された複数のＷＦＳＴを合成する。例えば単語辞書１２２から生成されたＷＦＳＴと言語モデル１２３から生成されたＷＦＳＴを合成すると、入力記号が音素で出力記号が単語、重みが単語列の尤もらしい並びを見つけるための値に対応するＷＦＳＴが生成される。決定化部１１３は、合成前や合成後のＷＦＳＴを必要に応じて決定化する。最小化部１１４は、決定化されたＷＦＳＴの状態や遷移ができる限り少なくなるようにＷＦＳＴを変形する。
【００２９】
このように、本実施形態では、音声認識におけるモデル作成時（モデル生成部１１０の決定化部１１３）、および、デコード時に生成されるラティスを処理する際（ラティス処理部１３４の決定化部１１３）の少なくとも一方で決定化処理が実行される。既に述べたように決定化に関してＷＦＳＴとＷＦＳＡは同様に扱うことができるため、以下で述べる説明ではＷＦＳＡを用いる。
【００３０】
図２は、決定化部１１３の詳細な構成例を示すブロック図である。決定化部１１３は、併合部１５０と、判定部１６１と、削除部１６２と、つなぎ替え部１６３と、を含む。併合部１５０は、決定化のために遷移を併合し、必要に応じて状態を生成する。併合部１５０は、状態生成部１５１と、遷移生成部１５２と、関連づけ部１５３と、重み算出部１５４と、を備えている。
【００３１】
状態生成部１５１は、決定化の際に必要な状態を生成する。例えば、状態生成部１５１は、決定化するＷＦＳＡに含まれる各状態（第１状態）について、当該状態から出て行く遷移であって、同一の記号が割り当てられている遷移（第１遷移）が２以上存在する場合に、新たな状態（第２状態）を生成する。
【００３２】
遷移生成部１５２は、決定化の際に必要な遷移を生成する。例えば、遷移生成部１５２は、第１状態から第２状態への遷移（第２遷移）を生成する。また、遷移生成部１５２は、第１遷移の次の状態から出て行く遷移（第３遷移）の前の状態を第２状態に置き換えた遷移（第４遷移）を生成する。
【００３３】
関連づけ部１５３は、遷移生成部１５２により生成される遷移と、既にＷＦＳＡに含まれる遷移であって遷移生成の根拠となる遷移とを関連づける。例えば、関連づけ部１５３は、第３遷移と第４遷移とを関連づける。
【００３４】
重み算出部１５４は、生成される遷移の重みを算出する。例えば、重み算出部１５４は、複数の第１遷移それぞれの重みから予め定められた演算により算出される重みの最良値を、第２遷移の重みとして算出する。
【００３５】
判定部１６１は、決定化するＷＦＳＡに含まれる２つの状態が等価であるか否かを判定する。例えば、判定部１６１は、２つの状態が、状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、２つの状態が等価であると判定する。判定部１６１は、例えば、一方の状態から出て行く遷移に関連づけられているすべての遷移と、他方の状態から出て行く遷移に関連づけられているすべての遷移と、が一致することを基準として利用する。
【００３６】
削除部１６２は、併合部１５０の処理によって不要になった状態や遷移を記憶領域から削除する。判定部１６１により、ある状態が別の状態と等価であると判定された場合は、削除部１６２は、一方の状態を削除する。環状経路が存在しないＦＳＡを決定化する場合には、判定部１６１が存在しなくても決定化そのものは実行できる。ただし、決定化後のＦＳＡの状態や遷移は、判定部１６１が存在する場合に比べ多くなることがある。
【００３７】
つなぎ替え部１６３は、必要に応じて、遷移の接続先の状態を変更する。すなわち、つなぎ替え部１６３は、遷移のつなぎ替えを行う。例えば、つなぎ替え部１６３は、等価であると判定された２つ状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替える。
【００３８】
次に、このように構成された第１の実施形態にかかる音声認識装置１００による決定化処理について図３を用いて説明する。図３は、第１の実施形態における決定化処理の全体の流れを示すフローチャートである。なお、図３のフローチャートは、第１の実施形態のみでなく、以下に説明するすべての実施形態における決定化処理の流れの概要を表す。
【００３９】
決定化部１１３は、処理開始時に、決定化するＮＦＳＡ（本実施形態では非決定性ＷＦＳＡ）をＲＡＭなどの記憶装置の記憶領域に読み込む（ステップＳ１０１）。決定化部１１３は、すべての状態について決定化が完了するまでステップＳ１０２からステップＳ１０３を繰り返し処理する。ステップＳ１０２では、決定化部１１３の併合部１５０は、まだ決定化が終わっていない状態を初期状態の側から順に決定化する。ステップＳ１０３では、決定化部１１３の削除部１６２が、ステップＳ１０２の決定化により不要になった状態や遷移を記憶領域から削除する。
【００４０】
決定化部１１３はすべての状態を決定化したか否かを判断し（ステップＳ１０４）、決定化していない場合は（ステップＳ１０４：Ｎｏ）、ステップＳ１０２に戻り処理を繰り返す。すべての状態を決定化した場合（ステップＳ１０４：Ｙｅｓ）、決定化処理を終了する。
【００４１】
以下に、決定化処理の詳細な例を説明する。図４は、本実施形態におけるＷＦＳＡの決定化処理の擬似コードの一例を示す図である。決定化を行う非決定性ＷＦＳＡ  Ａ＝（Ｑ，Ｅ，Σ，Ｋ，Ｉ，Ｆ，λ，ρ）は、最初に記憶領域に記憶されているものとする。本実施形態では、この記憶領域に記録されているＱ、Ｅ、Ｉ、Ｆ、λ、ρを順次変更することによって決定化を行う。
【００４２】
１行目では後述する３つ組からなる集合Ｍを空集合に初期化する。なお、Ｍは、いずれの擬似コードからでも参照できるものとする。
【００４３】
２行目では関数ｍｅｒｇｅＩｎｉｔｉａｌｓによって初期状態を１つの状態に併合する。ｍｅｒｇｅＩｎｉｔｉａｌｓについては後で述べる。
【００４４】
３行目では集合ＳにＩを代入する。さらに処理済か否かを判断するための集合Ｑ’にＩを代入する。ここで、集合Ｓはスタックでもキューでも何でも良い。
【００４５】
４行目ではＳが空集合か否かを判定する。空集合でなければ５行目から２４行目までの処理を行う。
【００４６】
５行目ではＳから１つ状態を取り出し、ｑに代入する。
【００４７】
６行目ではｑから出て行く遷移（ｏｕｔｇｏｉｎｇ  ｔｒａｎｓｉｔｉｏｎ）を集合Ｅｏｕｔに代入する。
【００４８】
７行目ではＥｏｕｔに含まれる遷移の入力記号をΣｏｕｔに代入する。
【００４９】
８行目はΣｏｕｔに含まれる各入力記号σについて９行目から２４行目までの処理を行うことを表す。
【００５０】
９行目では入力記号がσであるようなＥｏｕｔに含まれる遷移をＥσに代入する。
【００５１】
１０行目ではＥσに含まれる遷移の次状態の数が１か否かを判定し、１なら１１行目から１３行目を、そうでなければ１５行目から２４行目を処理する。
【００５２】
１１行目は関数ｍｅｒｇｅＷｅｉｇｈｔを呼び出す。引数としてＥσを渡し、戻り値として得られる状態をｑｎに代入する。関数ｍｅｒｇｅＷｅｉｇｈｔは、Ｅσが複数の遷移を含んでいるときに遷移を１つに併合する処理を行う。詳細は後述する。
【００５３】
１２行目ではｑｎがＱ’に含まれているかを判定し、含まれていなければ１３行目を処理する。
【００５４】
１３行目ではＳとＱ’にｑｎを追加する。
【００５５】
１５行目では関数ｍｅｒｇｅＴｒａｎｓｉｔｉｏｎｓを呼び出す。この関数は遷移の併合を行い、それに必要な新しい状態を生成し、その状態を戻り値として返す。その状態をｑｎｅｗとする。関数ｍｅｒｇｅＴｒａｎｓｉｔｉｏｎｓが、例えば状態生成部１５１、遷移生成部１５２および関連づけ部１５３の機能に相当する。
【００５６】
１６行目ではｑｎｅｗを引数として関数ｒｅｃｏｎｎｅｃｔを呼び出す。この関数は、状態ｑｎｅｗと等価な状態が存在するか否かを判断し、存在する場合はｔｒｕｅを、存在しない場合がｆａｌｓｅを返す。また、等価な状態が存在すれば、状態ｑへ入ってくる遷移（ｉｎｃｏｍｉｎｇ  ｔｒａｎｓｉｔｉｏｎ）の次状態を、その状態へと変更する処理（つなぎ替え）を行う。ここで等価な状態とは、本明細書においては、一方を他方の状態であるとしてもＷＦＳＡが受理する言語や出力する重みに影響を及ぼさないことをいう。アクセプタの場合は、重みが存在しないが、その場合は受理する言語に影響を及ぼさないことをいう。この関数の詳細は後述する。戻り値がｆａｌｓｅであれば１７行目でＳにｑｎｅｗを追加する。関数ｒｅｃｏｎｎｅｃｔが、例えばつなぎ替え部１６３の機能に相当する。
【００５７】
１８行目はＥσに含まれる遷移の次状態から成る集合に含まれる各状態ｑｎについて１９行目から２３行目を処理することを示す。
【００５８】
１９行目ではｑｎに入ってくる遷移がすべてＥσに含まれているか否かを判定し、そうであれば２０行目から２３行目を処理する。
【００５９】
２０行目では集合Ｅｒにｑｎから出て行く遷移を代入する。
【００６０】
２１行目では集合Ｅｓに遷移を代入する。その遷移は、集合Ｍに含まれる３つ組（連結元の遷移，連結先の遷移，重み）のうち、連結先の遷移ｅｄがＥｒに含まれているような連結元の遷移ｅｓである。
【００６１】
２２行目では集合Ｍに含まれる３つ組のうち、連結元の遷移ｅｓがＥｓに含まれているような３つ組を集合Ｍから削除する。遷移ｅｓの前状態から出て行く遷移を連結元の遷移とするような集合Ｍに含まれる３つ組を集合Ｍから削除することで、決定化に必要な記憶領域をさらに削減することもできる。
【００６２】
２３行目では遷移の集合ＥからＥｒに含まれる遷移を削除する。また、状態の集合Ｑから状態ｑｎを削除する。
【００６３】
２４行目では遷移の集合ＥからＥσを削除する。
【００６４】
２５行目では２４行目までの処理で削除できなかった状態と遷移を削除する。削除する状態は、初期状態から到達できない状態である。また、削除する遷移は、初期状態から到達できない状態が前状態か次状態であるような遷移である。言い換えると、初期状態から辿って通過することができない遷移である。２５行目の削除処理は、４行目による５行目から２４行目までの繰り返し処理が一定回数完了するたびに実施するよう構成することもできるし、１５行目から２４行目までの処理が一定回数完了するたびに実施するよう構成することもできる。すなわち、任意の予め定められた頻度で、初期状態から到達できない状態と遷移とを削除するように構成することができる。
【００６５】
図５は、関数ｍｅｒｇｅＩｎｉｔｉａｌｓの詳細な擬似コードの一例を示す図である。
【００６６】
１行目では初期状態が１つだけか否かを判定する。１つだけなら何もせず、２行目でこの関数での処理を終え、３行目以降の処理が行われることはない。
【００６７】
３行目では新たな初期状態を作成するためＱに含まれない新しい状態ｑｎｅｗを生成する。
【００６８】
４行目では初期状態の集合Ｉに含まれる各状態に対応する初期重みを演算（＋）によって計算し、その結果をｑｎｅｗの初期重みとしてλ（ｑｎｅｗ）に記録する。
【００６９】
５行目は各初期状態について６行目から１０行目を処理することを示す。
【００７０】
６行目はｑから出て行く各遷移ｅについて７行目から１０行目を処理することを示す。
【００７１】
７行目では新しい遷移ｅｎｅｗを生成する。ここで遷移ｅｎｅｗは、前状態をｑｎｅｗ、次状態を遷移ｅの次状態、入力記号を遷移ｅの入力記号、重みをλ（ｑｎｅｗ）の（×）に対する逆元とλ（ｑ）と遷移ｅの重みを（×）で演算した結果とする。
【００７２】
８行目ではｅｎｅｗを集合Ｅに追加する。
【００７３】
９行目はＩに含まれるすべての初期状態が、入ってくる遷移を持っている場合、１０行目を処理することを表す。入ってくる遷移が１つも存在しない初期状態が１つでも存在する場合、ｑｎｅｗと等価な状態がこれ以降の処理で現れることがない。このため、等価な状態の判定のために使う集合Ｍに３つ組を追加する必要がなく、１０行目を処理する必要がない。
【００７４】
１０行目では３つ組（ｅｎｅｗ，ｅ，ｗ（ｅｎｅｗ））をＭに追加する。
【００７５】
１１行目は初期状態であり、かつ、終了状態でもあるような状態が存在するか否かを判定する。初期状態かつ終了状態である状態が存在すれば１２行目の処理を行う。
【００７６】
１２行目ではｑｎｅｗを終了状態の集合Ｆに追加する。さらに、終了重みρ（ｑｎｅｗ）を設定する。終了重みに設定される値は、終了状態でもある各初期状態ｑに対して、ｑｎｅｗの初期重みの逆元とｑの初期重みとｑの終了重みを（×）で演算し、各状態に対して得られたすべての値を（＋）で演算した結果とする。
【００７７】
１３行目ではＩをｑｎｅｗのみから成る集合にし、ｑｎｅｗをＱに追加する。入ってくる遷移を持つ初期状態以外の状態をＱから削除する。さらに削除した状態から出て行く遷移を削除する。
【００７８】
図６は、関数ｍｅｒｇｅＴｒａｎｓｉｔｉｏｎｓの詳細な擬似コードの一例を示す図である。
【００７９】
１行目ではＱに含まれない新しい状態ｑｎｅｗを生成する。
【００８０】
２行目では集合Ｅσに含まれる遷移の重みを（＋）で演算した結果をｗｐに代入する。すなわち、ｗｐには集合Ｅσに含まれる遷移の重みの最良値が代入される。
【００８１】
３行目ではＥσに含まれる遷移の次状態に終了状態が含まれている場合、４行目の処理を行う。
【００８２】
４行目では終了状態の集合Ｆにｑｎｅｗを追加する。さらに、Ｅσに含まれる遷移の次状態が終了状態であるような遷移の重みｗと次状態ｑｎに対して次のような重みの計算を行い、ρ（ｑｎｅｗ）に代入する。その重みとは、ｗｐの逆元とｗとｑｎの終了重みρ（ｑｎ）を（×）で演算した結果である。
【００８３】
５行目では前状態がｑ、次状態がｑｎｅｗ、入力記号がσ、重みがｗｐであるような遷移をｅｄｅｔとする。
【００８４】
６行目ではＥにｅｄｅｔを、Ｑにｑｎｅｗを追加する。
【００８５】
７行目ではＭに含まれる３つ組（ｅｓ，ｅｄ，ｗ）のうち、ｅｓがＥσに含まれるような３つ組のみを集合Ｍｓに代入する。同様に、Ｍに含まれる３つ組（ｅｓ，ｅｄ，ｗ）のうち、ｅｄがＥσに含まれるような３つ組のみを集合Ｍｄに代入する。
【００８６】
８行目ではＭｓに含まれる各３つ組（ｅｓ，ｅｄ，ｗ）のｅｓをｅｄｅｔに変えた３つ組から成る集合をＭに追加し、ＭｓをＭから削除する。さらに、Ｍｄに含まれる各３つ組（ｅｓ，ｅｄ，ｗ）のｅｄをｅｄｅｔに変えた３つ組から成る集合をＭに追加し、ＭｄをＭから削除する。
【００８７】
９行目はＥσに含まれる遷移の次状態の集合に含まれる各状態ｑｎについて１０行目から１３行目を処理することを表す。
【００８８】
１０行目はＥσに含まれる遷移のうち、次状態がｑｎであるような遷移の重みをすべて（＋）で演算し、その結果をｗｂに代入する。
【００８９】
１１行目はｑｎから出て行く各遷移ｅｎについて１２行目から１３行目を処理することを表す。
【００９０】
１２行目では前状態がｑｎｅｗ、次状態がｎ（ｅｎ）、入力記号がｅｎの入力記号、重みがｗｐの逆元とｗ（ｅσ）とｗ（ｅｎ）を（×）で演算した結果である遷移をｅｎｅｗとする。
【００９１】
１３行目ではｅｎｅｗを集合Ｅに追加する。さらに、Ｍに３つ組（ｅｎｅｗ，ｅｎ，ｗ（ｅｎｅｗ））を追加する。ｅｎおよびｅｎｅｗを含む３つ組をＭに追加することが、例えば、生成される遷移（ｅｎｅｗ）と遷移生成の根拠となる遷移ｅｎとを関連づける関連づけ部１５３の機能に相当する。
【００９２】
１４行目ではｑｎｅｗを戻り値として返す。
【００９３】
図７は、関数ｍｅｒｇｅＷｅｉｇｈｔの詳細な擬似コードの一例を示す図である。Ｅσに含まれる遷移の前状態と次状態、入力記号はすべて同じであることを前提としている。また、Ｅσには１個以上の遷移が含まれているものとしている。
【００９４】
１行目は遷移ｅがＥσに含まれる遷移であることを示している。
【００９５】
２行目ではＥσに含まれる遷移の数が１か否かを判定しており、１なら８行目へ進み、それ以外であれば、すなわち遷移の数が２以上であれば３行目から７行目を処理することを示している。
【００９６】
３行目ではＥσに含まれる遷移の重みをすべて（＋）によって演算し、その結果をｗｐに代入する。
【００９７】
４行目では遷移ｅの重みをｗｐに変更した遷移をｅｄｅｔに代入する。
【００９８】
５行目では集合Ｍに含まれる３つ組（連結元の遷移，連結先の遷移，重み）のうち、連結先の遷移ｅｄがＥσに含まれるような３つ組から成る集合をＭｄに代入する。
【００９９】
６行目ではＭｄに含まれる３つ組を集合Ｍから削除し、Ｍｄに含まれる３つ組の連結先の遷移をｅｄｅｔに変更した３つ組を集合Ｍに追加する。
【０１００】
７行目では遷移の集合ＥからＥσに含まれる遷移を削除し、その後、Ｅにｅｄｅｔを追加する。
【０１０１】
８行目はこの関数の戻り値として遷移ｅの次状態を返すことを示している。
【０１０２】
図８は、関数ｒｅｃｏｎｎｅｃｔの詳細な擬似コードの一例を示す図である。
【０１０３】
１行目では状態ｑから出て行く遷移をＥｏｕｔに代入する。
【０１０４】
２行目ではＭに含まれている３つ組（ｅｓ，ｅｄ，ｗ）のｅｓから成る遷移の集合にＥｏｕｔに含まれている遷移がすべて含まれているか否かを判定し、すべて含まれていれば３行目から１３行目を処理することを示している。そうでない場合はｑと等価な状態は存在しないため、１４行目へ処理を移す。
【０１０５】
３行目ではＭに含まれる３つ組（ｅｓ，ｅｄ，ｗ）のうち、ｅｓがＥｏｕｔに含まれる３つ組に関して２つ組（ｅｄ，ｗ）を生成し、その集合を集合Ｄに代入する。
【０１０６】
４行目ではＤに含まれる２つ組の１つ目の値ｅｄがＭに含まれる３つ組の２つ目の値と一致する３つ組に関して、その３つ組の１つ目の値である遷移ｅｓから成る集合からＥｏｕｔを取り除いた集合をＥｍに代入する。
【０１０７】
５行目ではＥｍに含まれる遷移の前状態から構成される集合をＱｍに代入する。
【０１０８】
６行目はＱｍに含まれる各状態ｑｍについて７行目から１３行目まで処理することを表している。
【０１０９】
７行目ではｑｍから出て行く遷移をＥｍ’に代入する。
【０１１０】
８行目ではＭに含まれている３つ組（ｅｓ，ｅｄ，ｗ）のｅｓから成る遷移の集合にＥｍ’に含まれている遷移がすべて含まれているか否かを判定し、含まれていれば９行目から１３行目を処理することを示している。
【０１１１】
９行目ではＭに含まれる３つ組のうち、１つ目の値ｅｓがＥｍ’に含まれる３つ組の２つ目の値ｅｄと３つ目の値ｗを、それぞれ１つ目と２つ目の値とする２つ組から成る集合をＤｍに代入する。
【０１１２】
１０行目ではＤとＤｍが等しいか否かを判定し、さらに、ｑとｑｍに対応する終了重みが等しいか否かを判定する。両方とも等しければ状態ｑと状態ｑｍとは等価な状態である。その場合、１１行目から１３行目までを処理する。ｑまたはｑｍがいずれも終了状態でない場合、最初に述べた終了重み関数ρの定義により同じ値が得られρ（ｑ）＝ρ（ｑｍ）となる。一方が終了状態である場合、終了状態に対する終了重み関数ρで得られる値は重みの集合Ｋに含まれ、終了状態でない状態に対するρの値は集合Ｋに含まれないので、常にρ（ｑ）≠ρ（ｑｍ）である。両方ともが終了状態のときは、終了重みの値に応じてρ（ｑ）とρ（ｑｍ）が等しいか否かが決まる。
【０１１３】
１１行目ではｑへ入ってくる遷移をＥｉｎに代入する。
【０１１４】
１２行目ではＥｉｎとＥｏｕｔに含まれる遷移を集合Ｅから取り除く。また、Ｅｉｎに含まれる遷移の次状態をｑｍに変更した遷移をＥに追加する。さらに状態ｑを状態の集合Ｑから取り除く。擬似コードには記載していないが、集合Ｍに含まれる３つ組の１番目の要素がＥｏｕｔに含まれている３つ組を集合Ｍから取り除いても良い。すなわち、｛（ｅｓ，ｅｄ，ｗ）∈Ｍ｜ｅｓ∈Ｅｏｕｔ｝をＭから取り除いても良い。
【０１１５】
１３行目ではｔｒｕｅを戻り値として返し、この関数の処理を終える。
【０１１６】
Ｑｍに含まれるすべての状態に対して７行目から１３行目を処理してもｑと等価な状態が存在しなければ１４行目でｆａｌｓｅを戻り値として返す。
【０１１７】
以上のように、決定化を行いながら不要になった状態や遷移を逐次削除することで従来より少ない記憶領域で決定化処理を実行することができる。
【０１１８】
これまでに説明した決定化処理の具体例を以下に説明する。図９は、決定化する非決定性ＷＦＳＡの一例を示す図である。
【０１１９】
図９の例では重みの半環がトロピカル半環であるものとする。丸が状態、太線の丸が初期状態、二重丸が終了状態、矢印が遷移、矢印付近の文字のうち／の左側が入力記号、右側が重みである。丸の中の数字は状態の番号である。
【０１２０】
図４の１行目から処理を始める。１行目では後に使用する３つ組の集合Ｍを空集合で初期化する。２行目では初期状態を１つに併合するが、初期状態は１つなので何も起きない。３行目を処理すると、Ｓ＝｛１｝、Ｑ’＝｛１｝となる。Ｓは空集合ではないので、５行目に進む。Ｓから１つ要素を取り出すと、ｑ＝１、Ｓ＝｛｝となる。
【０１２１】
６行目と７行目の処理を終えると、Ｅｏｕｔ＝｛（１，ａ，１，２），（１，ｂ，３，２），（１，ａ，３，３），（１，ｂ，５，３）｝、Σｏｕｔ＝｛ａ，ｂ｝となる。９行目から２４行目について、まずσ＝ａの場合から処理を行う（ｂから処理しても良い）。９行目を処理するとＥσ＝｛（１，ａ，１，２），（１，ａ，３，３）｝となる。Ｅσに含まれる遷移の次状態の集合は｛２，３｝であるため、｜ｎ（Ｅσ）｜＝２となり、１０行目の条件を満たさない。従って１５行目に進む。
【０１２２】
関数ｍｅｒｇｅＴｒａｎｓｉｔｉｏｎｓに進む。引数の値は、ｑ＝１、σ＝ａ、Ｅσ＝｛（１，ａ，１，２），（１，ａ，３，３）｝である。
【０１２３】
図６の１行目で新しい状態を生成する。これをｑｎｅｗ＝７とする。２行目の計算は次のようになる。この例ではトロピカル半環を用いるので（＋）は最小値（ｍｉｎ）の計算になり、ｗｐ＝１（＋）３＝ｍｉｎ（１，３）＝１となる。Ｅσの次状態の集合ｎ（Ｅσ）＝｛２，３｝とＦ＝｛６｝との積集合は空集合なので３行目の条件は満たさず、５行目へと進む。５行目では、ｅｄｅｔ＝（１，ａ，１，７）となる。
【０１２４】
６行目ではｅｄｅｔとｑｎｅｗをそれぞれＥとＱに追加する。この結果、ＷＦＳＡは、図１０のようになる。
【０１２５】
Ｍ＝φなので７行目によりＭｓ＝φ、Ｍｄ＝φとなる。従って、８行目の処理後もＭ＝φである。
【０１２６】
９行目ではまずｑｎ＝２について１０行目から１３行目の処理を行う。なお、ｑｎ＝３の場合を先に処理してもかまわない。
【０１２７】
１０行目では次状態が２であるＥσに含まれる遷移は（１，ａ，１，２）のみであるので、その重み１がｗｂの値となる。
【０１２８】
次にｐ（ｅｎ）＝２であるような遷移について１２行目と１３行目を処理する。ここではｅｎ＝（２，ｃ，１，４）のみを処理すれば良い。
【０１２９】
１２行目で新しい遷移ｅｎｅｗ＝（７，ｃ，１，４）を生成する。重みはｗｐ−１＝−１、ｗｂ＝１、ｗ（ｅｎ）＝１なので、−１＋１＋１＝１と計算される。１３行目でＥにｅｎｅｗを追加し、Ｍに３つ組（ｅｎｅｗ，ｅｎ，１）を追加する。遷移は４つ組として記録することもできるし、Ｅに含まれる要素への参照として記録することもできる。
【０１３０】
ｑｎ＝３についても同様に１０行目から１３行目を処理する。１０行目でｗｂ＝３となる。１２行目と１３行目はｅｎ＝（３，ｃ，２，５）について処理すれば良い。１２行目で新しい遷移ｅｎｅｗ＝（７，ｃ，４，５）を生成する。重みはｗｐ−１＝−１、ｗｂ＝３、ｗ（ｅｎ）＝２なので、−１＋３＋２＝４と計算される。１３行目でＥにｅｎｅｗを、Ｍに３つ組（ｅｎｅｗ，ｅｎ，４）を追加する。
【０１３１】
最後に１４行目でｑｎｅｗを戻り値としてこの関数での処理を終了する。
【０１３２】
この時点でＭ＝｛（（７，ｃ，１，４），（２，ｃ，１，４），１）、（（７，ｃ，４，５），（３，ｃ，２，５），４）｝であり、ＷＦＳＡは図１１のようになる。点線矢印は、Ｍに記録している３つ組に対応する。矢印の元が３つ組の１つ目の値、矢印の先が３つ組の２つ目の値、矢印の付近の値が３つ組の３つ目の値と一致している。すなわち、点線矢印の元の遷移と点線矢印の先の遷移とが、相互に関連づけられていることを表している。
【０１３３】
図４の１５行目に戻る。ｑｎｅｗ＝７となる。１６行目で関数ｒｅｃｏｎｎｅｃｔに進む。図８の１行目でＥｏｕｔ＝｛（７，ｃ，１，４），（７，ｃ，４，５）｝となる。今、Ｍに含まれる３つ組の１番目の値にはＥｏｕｔに含まれる値がすべて含まれているので２行目の条件を満たす。３行目でＤ＝｛（（２，ｃ，１，４），１），（（３，ｃ，２，５），４）｝となる。
【０１３４】
４行目でＥｍ＝φとなる。Ｍに含まれる３つ組の２番目の値がＤに含まれる２つ組の１番目の値であるような３つ組の１番目の値の集合はＥｏｕｔと等しく、Ｅｏｕｔとの差集合をとると空集合になるためである。Ｅｍ＝φであるので５行目ではＱｍ＝φとなる。これは、状態７と等価な状態である可能性がある状態が存在しないことを意味している。その結果、７行目から１３行目の処理は行われない。そして１４行目でｆａｌｓｅを戻り値としてこの関数の処理を終え、図４の１６行目に戻る。
【０１３５】
１６行目の結果はｆａｌｓｅであるので、１７行目でＳに状態７を追加すると、Ｓ＝｛７｝となる。
【０１３６】
今、Ｅσ＝｛（１，ａ，１，２），（１，ａ，３，３）｝である。ｎ（Ｅσ）＝｛２，３｝なので、この２つの状態について１９行目から２３行目を処理する。まずｑｎ＝２について処理する。状態２へ入ってくる遷移は（１，ａ，１，２）と（１，ｂ，３，２）が存在する。（１，ａ，１，２）はＥσに含まれているが、（１，ｂ，３，２）は含まれていないので、１９行目の条件を満たさない。また、ｑｎ＝３についても１９行目の条件を満たさない。従って２４行目に進み、ＥσをＥから取り除くと、図１２のようになる。
【０１３７】
８行目に戻り、σ＝ｂで９行目から２４行目までを先ほどと同じように処理する。１０行目の条件は満たさないので、１５行目を処理すると図１３のようになる。このときｑｎｅｗ＝８、Ｍ＝｛（（７，ｃ，１，４），（２，ｃ，１，４），１），（（７，ｃ，４，５），（３，ｃ，２，５），４），（（８，ｃ，１，４），（２，ｃ，１，４），１），（（８，ｃ，４，５），（３，ｃ，２，５），４）｝である。
【０１３８】
１６行目の関数ｒｅｃｏｎｎｅｃｔを引数ｑｎｅｗ＝８で処理する。図８の１行目でＥｏｕｔ＝｛（８，ｃ，１，４），（８，ｃ，４，５）｝となるので、２行目の条件を満たす。３行目でＤ＝｛（（２，ｃ，１，４），１），（（３，ｃ，２，５），４）｝となる。Ｄに含まれる２つ組の１番目の要素は（２，ｃ，１，４）と（３，ｃ，２，５）である。これらのうちいずれかを２番目の要素とするＭに含まれる３つ組の１番目の要素は（７，ｃ，１，４）、（７，ｃ，４，５）、（８，ｃ，１，４）、（８，ｃ，４，５）である。ここからＥｏｕｔに含まれる遷移を取り除くと、Ｅｍ＝｛（７，ｃ，１，４），（７，ｃ，４，５）｝となる。これが４行目の結果である。５行目でＱｍ＝｛７｝となる。
【０１３９】
Ｑｍの要素の数は１なので、ｑｍ＝７についてのみ７行目から１３行目を処理すれば良い。７行目でＥｍ’にｑｍから出て行く遷移を代入し、Ｅｍ’＝｛（７，ｃ，１，４），（７，ｃ，４，５）｝となる。８行目の条件は満たすので、９行目以降に進む。９行目でＤｍ＝｛（（２，ｃ，１，４），１），（（３，ｃ，２，５），４）｝となる。ＤとＤｍは等しく、状態７、８は共に終了状態ではないので１０行目の条件を満たし、１１行目以降に進む。１０行目の条件を満たすということは状態ｑ＝８と状態ｑｍ＝７が等価であるということである。一方が不要なので、１１行目と１２行目で状態８と、状態８から出て行く遷移をすべて削除する。状態８へ入ってくる遷移は、そのすべてについて次状態を状態７に変更する。１３行目で戻り値をｔｒｕｅとして図４の１６行目へ戻る。
【０１４０】
１６行目の処理が完了すると、図１４のようになる。ｔｒｕｅが戻ってくるので１７行目は処理されずＳ＝｛７｝のままである。
【０１４１】
１８行目の条件を満たす状態は状態２と３である。これらの状態について１９行目から２３行目を処理する。まず、ｑｎ＝２の場合について処理する。状態２に入ってくる遷移は（１，ｂ，３，２）のみであり、これはＥσ＝｛（１，ｂ，３，２），（１，ｂ，５，３）｝に含まれている。従って、１９行目の条件を満たすので、２０行目以降の処理を行う。その処理では、状態２と関連する遷移とそれら遷移に関連する集合Ｍの要素を削除する。まず２０行目で状態２から出て行く遷移をＥｒに代入する。Ｅｒ＝｛（２，ｃ，１，４）｝となる。
【０１４２】
この時点ではＭ＝｛（（７，ｃ，１，４），（２，ｃ，１，４），１），（（７，ｃ，４，５），（３，ｃ，２，５），４），（（８，ｃ，１，４），（２，ｃ，１，４），１），（（８，ｃ，４，５），（３，ｃ，２，５），４）｝である。図８の１２行目の処理時に、そこで削除された状態８から出て行く遷移を３つ組の１番目の要素に持つ３つ組をＭから取り除いていれば、Ｍ＝｛（（７，ｃ，１，４），（２，ｃ，１，４），１），（（７，ｃ，４，５），（３，ｃ，２，５），４）｝である。前者の場合、２１行目でＥｓ＝｛（７，ｃ，１，４），（８，ｃ，１，４）｝となり、後者の場合、Ｅｓ＝｛（７，ｃ，１，４）｝となる。図１４は後者の場合を表している。
【０１４３】
Ｍに含まれる３つ組の１番目の要素がＥｓに含まれている３つ組をＭから削除する。そのような３つ組は前者の場合は｛（（７，ｃ，１，４），（２，ｃ，１，４），１），（（８，ｃ，１，４），（２，ｃ，１，４），１）｝である。後者の場合は（（７，ｃ，１，４），（２，ｃ，１，４），１）のみである。２２行目ではそれらをＭから削除する。２３行目ではＥｒを遷移の集合Ｅから取り除き、状態２も状態の集合Ｑから取り除く。
【０１４４】
１９行目から２３行目を状態３についても同様に処理すると、この場合は図８の１２行目の処理がいずれであってもＭ＝｛｝となる。２４行目でＥσをＥから削除すると、図１５のようになる。
【０１４５】
次にＳ＝｛７｝なのでｑ＝７として５行目から２４行目を処理する。１７行目まで処理すると、図１６のようになる。Ｓ＝｛９｝、Ｍ＝｛（（９，ａ，３），（４，ａ，３），３），（（９，ｄ，４），（５，ｄ，１），４）｝である。ここでは分かりやすくするため新しく作成する状態の番号を１つずつ増やしているが、削除した状態の番号を再利用することで使用する記憶領域を削減しても良い。
【０１４６】
状態４と５について１９行目から２３行目を処理することになり、いずれの場合も１９行目の条件を満たすので、状態４と５とそれらから出て行く遷移が削除され、２２行目に従ってＭの要素が取り除かれる。さらに２４行目でＥσに含まれる遷移を削除すると、図１７のようになる。
【０１４７】
次にＳ＝｛９｝なのでＳから９を取り出し、ｑ＝９として６行目から２４行目の処理を行う。Σｏｕｔ＝｛ａ，ｄ｝であるが、それぞれの入力記号につき遷移が１本しか存在しないので、いずれの場合も１０行目の条件を満たし、１１行目以降を処理する。１１行目ではいずれの場合でもｑｎ＝６となる。いずれか一方の処理時に１３行目に進み、Ｓに状態６が加えられ、Ｓ＝｛６｝となる。４行目に戻るがＳが空集合ではないので５行目に進み、ｑ＝６として６行目以降を処理する。状態６から出て行く遷移は存在しないので、８行目以降は処理されない。４行目に戻り、Ｓ＝｛｝であるので、最後に２５行目を処理する。しかしながらすべての状態と遷移が初期状態から到達することができるので、何も起きない。以上で決定化が完了する。
【０１４８】
以上の決定化処理過程で発生する状態数の最大値は８個となり、遷移数の最大値は１２本となる。従来の方法で決定化を行うと、発生する状態数の最大値は決定化前の状態数と決定化後の状態数を足した値である１０個となり、同様に遷移数は１３本となる。従って、本実施形態の方法によれば、処理途中で発生する状態数と遷移数が従来法よりも少なくなり、その結果、従来法よりも使用する記憶領域が少なくなる。
【０１４９】
本実施形態ではＷＦＳＡを対象として説明したが、重みの処理をなくすことでアクセプタの決定化が同様に可能である。また、重みを出力記号列であるとし、演算（＋）を前方最長一致とし、（×）を連結演算とすることでＦＳＴの決定化も可能である。先に述べたように、２つ組（重み、出力記号列）を重みとみなせばＷＦＳＴについても決定化が同様に可能である。
【０１５０】
ＦＳＴの決定化の場合、例えば重み算出部１５４が、複数の第１遷移それぞれの出力記号列の最長前方一致の記号列を、第２遷移の出力記号列として算出する。また、重み算出部１５４が、複数の第１遷移それぞれの出力記号列の最長前方一致の記号列を、第１遷移の出力記号列の前方から取り除いた記号列を、第４遷移の出力記号列の前方に連結する。
【０１５１】
図１８は、本実施形態の音声認識装置１００のハードウェア構成の一例を示したブロック図である。図１８に示されるように、音声認識装置１００は、ＣＰＵ（Central  Processing  Unit）１、操作部２、表示部３、ＲＯＭ（Read  Only  Memory）４、ＲＡＭ（Random  Access  Memory）５、記憶部６、バス７等を備えている。各部はバス７により接続されている。本装置構成における記憶領域とはＲＯＭ４、ＲＡＭ５、記憶部６のいずれにかかわらずＦＳＡを記憶するために用いられる装置内の記憶領域を指す。
【０１５２】
ＣＰＵ１は、ＲＡＭ５の所定領域を作業領域として、ＲＯＭ４または記憶部６に予め記憶された各種制御プログラムとの協働により各種処理を実行し、音声認識装置１００を構成する各部の動作を統括的に制御する。またＣＰＵ１は、ＲＯＭ４または記憶部６に予め記憶された所定のプログラムとの協働により後述する各機能部の機能を実現させる。
【０１５３】
操作部２は、マウスやキーボード、マイク等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をＣＰＵ１に出力する。
【０１５４】
表示部３は、ＬＣＤ（Liquid  Crystal  Display）等の表示装置により構成され、ＣＰＵ１からの表示信号に基づいて、各種情報を表示する。
【０１５５】
ＲＯＭ４は、音声認識装置１００の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。
【０１５６】
ＲＡＭ５は、ＳＤＲＡＭ等の揮発性の記憶媒体であって、ＣＰＵ１の作業エリアとして機能する。具体的には、決定化処理時に生成される各種変数やパラメータの値等を一時記憶するバッファ等の役割を果たす。
【０１５７】
記憶部６は、フラッシュメモリ等の半導体による記憶媒体や、磁気的または光学的に記録可能な記憶媒体を有し、音声認識装置１００の制御にかかるプログラムや各種設定情報等を書き換え可能に記憶する。また記憶部６は、ＦＳＡに係る各種の情報を予め記憶したり、決定化処理の処理結果であるＦＳＡを記録したりする。
【０１５８】
このように、第１の実施形態にかかるオートマトン決定化装置では、従来の方法に比べ、決定化処理の途中に保持しなければならない状態数や遷移数が少なくなるので、従来の方法より少ない記憶領域で決定化を行うことができる。
【０１５９】
（第２の実施形態）
第１の実施形態では遷移を用いて等価な状態の判定を行うように構成した。第２の実施形態にかかるオートマトン決定化装置は、従来のサブセット構成法のように、状態を用いて等価な状態の判定を行うように構成する。
【０１６０】
状態を用いて状態の等価を判定する場合、第１の実施形態で用いた集合Ｍの要素である３つ組（連結元の遷移、連結先の遷移、重み）の１番目と２番目を変更し、（連結元の状態、連結先の状態、重み）のようにする。また、擬似コードを以下に述べるように書き換える。
【０１６１】
図４の２１行目と２２行目をそれぞれ、Ｑｓ←｛ｑｓ｜（ｑｓ，ｑｄ，ｗ）∈Ｍ，ｑｄ＝ｑｎ｝、および、Ｍ←Ｍ＼｛（ｑｓ，ｑｄ，ｗ）∈Ｍ｜ｑｓ∈Ｑｓ｝に変更する。
【０１６２】
図５の１０行目をＭ←Ｍ∪｛（ｑｎｅｗ，ｑ，λ（ｑｎｅｗ）−１（×）λ（ｑ））｝に変更する。
【０１６３】
図６の７行目と８行目を削除する。１０行目と１１行目の間に次の処理を追加する。Ｍに含まれる３つ組の１番目の要素にｑｎが存在するときは処理（ａ）を、そうでないときは処理（ｂ）を行う。処理（ａ）では、Ｍに含まれる３つ組の１番目の要素がｑｎであるような全ての３つ組についてＭ←Ｍ∪｛（ｑｎｅｗ，ｑｄ，ｗｐ−１（×）ｗｂ（×）ｗｄ）｝を処理する。ここで、当該３つ組の２番目の要素をｑｄ、３番目の要素をｗｄとしている。処理（ｂ）はＭ←Ｍ∪｛（ｑｎｅｗ，ｑｎ，ｗｐ−１（×）ｗｂ）｝である。等価な状態が一部発見できないことがあるが、処理を簡単にするために処理（ｂ）だけを行うようにすることも可能である。１３行目をＥ←Ｅ∪｛ｅｎｅｗ｝のみに変更する。
【０１６４】
図７の５行目と６行目を削除する。
【０１６５】
図８を図１９のように変更する。１行目ではＭに含まれる３つ組の１番目の要素からなる集合にｑが含まれているか否かを判定し、含まれていれば２行目から９行目を処理する。
【０１６６】
２行目ではＭに含まれる３つ組の１番目の要素ｑｓがｑであるような２番目の要素ｑｄと３番目の要素ｗから成る２つ組の集合をＤに代入する。
【０１６７】
３行目ではＤに含まれる２つ組の１番目の要素ｑｄが２番目の要素となるＭに含まれる３つ組の１番目の要素をＱｍとする。Ｑｍに含まれる状態はｑと等価な状態の候補であり、それらの状態がｑと等価であるか否かを５行目以降で判定する。
【０１６８】
４行目は５行目から９行目をＱｍに含まれる各状態ｑｍについて処理することを表している。
【０１６９】
５行目ではＭに含まれる３つ組の１番目の要素ｑｓがｑｍであるような２番目の要素ｑｄと３番目の要素ｗから成る２つ組の集合をＤｍに代入する。
【０１７０】
６行目でＤとＤｍが同じであるかを判定し、同じであればｑとｑｍが等価な状態であるので、状態ｑと関連する遷移を削除または変更するため、７行目から９行目を処理する。
【０１７１】
７行目ではｑに入ってくる遷移をＥｉｎに、ｑから出て行く遷移をＥｏｕｔに代入する。
【０１７２】
８行目ではＥｏｕｔを集合Ｅから削除し、Ｅｉｎの次状態をｑｍに変更し、Ｑからｑを削除する。
【０１７３】
等価な状態が見つかりｑを削除したので戻り値をｔｒｕｅとして９行目でこの関数での処理が完了する。
【０１７４】
１０行目はｑと等価な状態が見つからなかった場合に実行される。この場合、戻り値をｆａｌｓｅとしてこの関数での処理が完了する。
【０１７５】
以上で示した方法により、サブセット構成法をベースとする場合でも処理途中で発生する状態や遷移の数を従来法より少なくすることができる。すなわち、従来法よりも使用する記憶領域が少なくなる。第１の実施形態と同様に、本実施形態においても、アクセプタ、ＦＳＴ、および、ＷＦＳＴの決定化が可能である。アクセプタの場合は重みに関する処理を取り除けば良い。ＦＳＴやＷＦＳＴの場合は第１の実施形態で述べたように重みの半環をそれぞれ対応する半環へと変更するだけである。
【０１７６】
（第３の実施形態）
第１の実施形態で重みの処理を省くとアクセプタに対しても第１の実施形態の方法を用いることができることを述べた。第３の実施形態ではアクセプタの決定化処理の例を示す。
【０１７７】
アクセプタは状態の集合Ｑ、遷移の集合Ｅ、入力記号の集合Σ、初期状態の集合Ｉ、および、終了状態の集合Ｆから成る５つ組（Ｑ，Ｅ，Σ，Ｉ，Ｆ）から構成される。遷移は３つ組（前状態，入力記号，次状態）で構成される。第１の実施形態で用いた集合Ｍの要素は３つ組であったが、ここでは２つ組（連結元の遷移，連結先の遷移）で構成される。
【０１７８】
第３の実施形態では、擬似コードを以下に述べるように書き換える。図４は２１行目および２２行目をそれぞれ、Ｅｓ←｛ｅｓ｜（ｅｓ，ｅｄ）∈Ｍ，ｅｄ∈Ｅｒ｝およびＭ←Ｍ＼｛（ｅｓ，ｅｄ）∈Ｍ｜ｅｓ∈Ｅｓ｝に変更する。
【０１７９】
図５は４行目を削除する。７行目をｅｎｅｗ←（ｑｎｅｗ，ｉｎ（ｅ），ｎ（ｅ））に変更する。１０行目をＭ←Ｍ∪｛（ｅｎｅｗ，ｅ）｝に変更する。１２行目をＦ←Ｆ∪｛ｑｎｅｗ｝に変更する。
【０１８０】
図６は２行目と１０行目を削除する。４行目および５行目をそれぞれ、Ｆ←Ｆ∪｛ｑｎｅｗ｝，および、ｅｄｅｔ←（ｑ，σ，ｑｎｅｗ）に変更する。７行目および８行目をそれぞれ、Ｍｓ←｛（ｅｓ，ｅｄ）∈Ｍ｜ｅｓ∈Ｅσ｝、Ｍｄ←｛（ｅｓ，ｅｄ）∈Ｍ｜ｅｄ∈Ｅσ｝、および、Ｍ←Ｍ∪｛（ｅｄｅｔ，ｅｄ）｜（ｅｓ，ｅｄ）∈Ｍｓ｝＼Ｍｓ∪｛（ｅｓ，ｅｄｅｔ）｜（ｅｓ，ｅｄ）∈Ｍｄ｝＼Ｍｄに変更する。１２行目および１３行目をそれぞれ、ｅｎｅｗ←（ｑｎｅｗ，ｉｎ（ｅｎ），ｎ（ｅｎ））、および、Ｅ←Ｅ∪｛ｅｎｅｗ｝，Ｍ←Ｍ∪｛（ｅｎｅｗ，ｅｎ）｝に変更する。
【０１８１】
図７は３行目を削除する。４行目から６行目を順に、ｅｄｅｔ←（ｐ（ｅ），ｉｎ（ｅ），ｎ（ｅ））、Ｍｄ←｛（ｅｓ，ｅｄ）∈Ｍ｜ｅｄ∈Ｅσ｝、および、Ｍ←（Ｍ＼Ｍｄ）∪｛（ｅｓ，ｅｄｅｔ）｜（ｅｓ，ｅｄ）∈Ｍｄ｝に変更する。
【０１８２】
重みに関する処理を取り除くため、図８を図２０のように変更する。重み関数ρが存在しないため、１０行目の重み関数を使った判定が終了状態か否かの判定に置き換わっている。状態ｑと状態ｑｍがいずれも終了状態である場合、または、いずれも終了状態でない場合は（ｑ∈Ｆ）＝（ｑｍ∈Ｆ）は真となる。一方が終了状態で他方が終了状態でない場合は偽となる。
【０１８３】
以上で示した方法により、アクセプタの場合でも処理途中で発生する状態や遷移の数を従来法より少なくすることができるので、従来法よりも使用する記憶領域が少なくできる。
【０１８４】
以上説明したとおり、第１から第３の実施形態によれば、決定化処理の途中で発生する状態や遷移の数を従来法より少なくし、使用する記憶領域を少なくすることができる。
【０１８５】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１８６】
１００  音声認識装置
１１０  モデル生成部
１１１  モデル変換部
１１２  合成部
１１３  決定化部
１１４  最小化部
１２１  音響モデル
１２２  単語辞書
１２３  言語モデル
１３０  音声認識部
１３１  音声取得部
１３２  特徴抽出部
１３３  デコード部
１３４  ラティス処理部
１３５  出力部
１５０  併合部
１５１  状態生成部
１５２  遷移生成部
１５３  関連づけ部
１５４  重み算出部
１６１  判定部
１６２  削除部
１６３  つなぎ替え部
【図１】
0005554304.tif 000003
【図２】
0005554304.tif 000004
【図３】
0005554304.tif 000005
【図４】
0005554304.tif 000006
【図５】
0005554304.tif 000007
【図６】
0005554304.tif 000008
【図７】
0005554304.tif 000009
【図８】
0005554304.tif 000010
【図９】
0005554304.tif 000011
【図１０】
0005554304.tif 000012
【図１１】
0005554304.tif 000013
【図１２】
0005554304.tif 000014
【図１３】
0005554304.tif 000015
【図１４】
0005554304.tif 000016
【図１５】
0005554304.tif 000017
【図１６】
0005554304.tif 000018
【図１７】
0005554304.tif 000019
【図１８】
0005554304.tif 000020
【図１９】
0005554304.tif 000021
【図２０】
0005554304.tif 000022