(57)【要約】【課題】縦続接続不可能な仮説生成規則を従属可能にする記号列変換方法を提供する。【解決手段】入力信号選択部が、入出力記号列配置記憶部を参照して前段の仮説生成部へ入力する入力記号列と前段及びそれより前の各仮説生成部の出力する出力記号列の何れかの中から１つを選択してｍ段目（ｍは１〜Ｍまでの整数）の仮説生成部の入力記号列とし、ｍ段目の仮説生成部が補助仮説ｆｍを生成する補助仮説生成過程を、ｍをインクリメントしながらＭ段目まで繰り返す補助仮説生成過程と、仮説補正部が、補助仮説ｆｍの累積重みで前段の補助仮説ｆｍ−１の重みを補正し、仮説ｆ１の累積重みを補助仮説の累積重みで補正するまでｍをデクリメントしながら繰り返す仮説補正過程と、仮説絞込み部が、補正された累積重みが特異値を呈する仮説或いは補助仮説を抽出し、抽出した仮説或いは補助仮説を次段の仮説絞込み部の入力記号列とする仮説絞込み過程と、を備える【選択図】図１
2014081516.tif 000002
【特許請求の範囲】
【請求項１】
Ｍ個（Ｍ≧２）の縦続接続される仮説生成部と、上記仮説生成部のそれぞれに付随するＭ個の仮説補正部と、上記仮説補正部のそれぞれに付随するＭ個の仮説絞込み部と、上記縦続接続される仮説生成部の間に設けられ１段目の仮説生成部の入力記号列と上記前段及びそれより前の各仮説生成部の出力する出力記号列とを入力として次段の仮説生成部の入力記号列を選択する入力記号列選択部と、上記入力記号列選択部の選択する入力記号列選択情報と上記仮説絞込み部の抽出した仮説を出力とするか否かの出力選択情報とを記憶した入出力記号列配置記憶部とを備えた記号列変換装置を構成し、
1段目の上記仮説生成部が、入力される入力記号列に対して状態遷移が可能な状態遷移過程である仮説ｆ１を仮説生成規則に従って生成する仮説生成処理過程と、
上記入力信号選択部が、上記した入出力記号列配置記憶部を参照して１段目の仮説生成部へ入力する入力記号列と前段及びそれより前の各仮説生成部の出力する出力記号列の何れかの中から１つを選択してｍ段目（ｍは１〜Ｍまでの整数）の仮説生成部の入力記号列とし、上記ｍ段の仮説生成部が補助仮説ｆｍを生成する補助仮説生成過程を、上記ｍをインクリメントしながら上記Ｍ段目まで繰り返す補助仮説生成過程と、
上記仮説補正部が、上記補助仮説ｆｍの累積重みで前段の補助仮説ｆｍ−１の重みを補正し、上記仮説ｆ１の累積重みを補助仮説の累積重みで補正するまで上記ｍをデクリメントしながら繰り返す仮説補正過程と、
上記仮説絞込み部が、補正された累積重みが特異値を呈する仮説或いは補助仮説を抽出し、抽出した仮説或いは補助仮説を次段の仮説絞込み部の入力記号列とする仮説絞込み過程と、
を備えることを特徴とする記号列変換方法。
【請求項２】
請求項１に記載した記号列変換方法において、
上記仮説絞込み過程は、
各仮説絞込み部が、上記した入出力記号列配置記憶部を参照して当該抽出した仮説ｆ１或いは補助仮説ｆｍを外部に出力するか否かを選択する処理も行う仮説絞込み過程であることを特徴とする記号列変換方法。
【請求項３】
音声信号を入力として音声の短時間音響パターンの時系列から音響特徴記号列を抽出する音声特徴記号列抽出過程を備え、
上記音響特徴記号列変換過程で変換された音響特徴を表す記号列を請求項１又は２に記載した記号列変換方法により上記音声信号に対応する記号列に変換し、
初段の仮説生成部は、上記音声特徴記号列抽出部で抽出した音響特徴を表す記号列を入力とし、音声固定単位の標準的特徴を備えた音響モデル用仮説生成規則と、種々の単語の発音を上記音声固定単位の系列に対応させる単語発音辞書用仮説生成用規則とを参照して、単語系の記号列を出力記号列とする仮説を生成することを特徴とする音声認識方法。
【請求項４】
Ｍ個（Ｍ≧２）の縦続接続される仮説生成部と、上記仮説生成部のそれぞれに付随するＭ個の仮説補正部と、上記仮説補正部のそれぞれに付随するＭ個の仮説絞込み部と、上記縦続接続される仮説生成部の間に設けられ１段目の仮説生成部の入力記号列と上記前段及びそれより前の各仮説生成部の出力する出力記号列とを入力として次段の仮説生成部の入力記号列を選択する入力記号列選択部と、上記入力記号列選択部の選択する入力記号列選択情報と上記仮説絞込み部の抽出した仮説を出力とするか否かの出力選択情報とを記憶した入出力記号列配置記憶部とを備えた記号列変換装置であって、
1段目の上記仮説生成部が、入力される入力記号列に対して状態遷移が可能な状態遷移過程である仮説ｆ１を仮説生成規則に従って生成し、
上記入力信号選択部が、上記した入出力記号列配置記憶部を参照して１段目の仮説生成部へ入力する入力記号列と前段及びそれより前の各仮説生成部の出力する出力記号列の何れかの中から１つを選択してｍ段目（ｍは１〜Ｍまでの整数）の仮説生成部の入力記号列とし、上記ｍ段の仮説生成部が補助仮説ｆｍを生成する補助仮説生成過程を、上記ｍをインクリメントしながら上記Ｍ段目まで繰り返し、
上記仮説補正部が、上記補助仮説ｆｍの累積重みで前段の補助仮説ｆｍ−１の重みを補正し、上記仮説ｆ１の累積重みを補助仮説の累積重みで補正するまで上記ｍをデクリメントしながら繰り返し、
上記仮説絞込み部が、補正された累積重みが特異値を呈する仮説或いは補助仮説を抽出し、抽出した仮説或いは補助仮説を次段の仮説絞込み部の入力記号列とする、
ことを特徴とする記号列変換装置。
【請求項５】
請求項４に記載した記号列変換装置において、
上記各仮説絞込み部は、上記した入出力記号列配置記憶部を参照して当該抽出した仮説ｆ１或いは補助仮説ｆｍを外部に出力するか否かを選択する処理も行うことを特徴とする記号列変換装置。
【請求項６】
音声信号を入力として音声の短時間音響パターンの時系列から音響特徴記号列を抽出する音声特徴記号列抽出部を具備し、
上記音響特徴記号列変換部で変換された音響特徴を表す記号列を請求項１又は２に記載した記号列変換方法により上記音声信号に対応する記号列に変換し、
初段の仮説生成部は、上記音声特徴記号列抽出部で抽出した音響特徴を表す記号列を入力とし、音声固定単位の標準的特徴を備えた音響モデル用仮説生成規則と、種々の単語の発音を上記音声固定単位の系列に対応させる単語発音辞書用仮説生成用規則とを参照して、単語系の記号列を出力記号列とする仮説を生成することを特徴とする音声認識装置。
【請求項７】
請求項４又は５に記載した記号列変換装置、又は請求項６に記載した音声認識装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項７に記載した何れかのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重み付き有限状態変換器（ＷＦＳＴ：Weighted Finite-State Transducer）によって表現された記号列変換規則によって、入力された記号列に対して生成可能な数多くの出力記号列から、適用される変換規則の重みの累積値が最小または最大の特異値を呈する出力記号列を効率的に見つけることを可能とする記号列変換方法、及びそれを用いた音声認識方法と、それらの装置とプログラムと記録媒体に関する。
【背景技術】
【０００２】
異なる２つの重み付き有限状態変換器において、ある仮説生成規則の出力記号列がもう一方の仮説生成規則の入力記号列とできる場合、これら２つの仮説生成規則を合成し、１つの仮説生成規則を作成することができる。例えば、音声認識ではこのような特徴を活用し、音響モデルによる仮説生成規則、トライフォン（音素の３つ組み）を音素に変換する仮説生成規則、発音辞書による仮説生成規則、言語モデルによる仮説生成規則を合成することで、音声認識結果である単語列に変換する仕組みを実現している。
【０００３】
一方で、仮説生成規則を合成すると、仮説生成規則の状態数や状態遷移数が非常に大きくなってしまうため実行時のメモリが増大する問題がある。この問題を解決するため、例えば特許文献１に開示されている記号列変換装置９００が考えられている。図１４に、記号列変換装置９００の機能構成を示してその動作を説明する。
【０００４】
記号列変換装置９００は、Ｍ段に縦続接続された仮説生成部２０１−１〜２０１−Ｍと、これらＭ個の各仮説生成部２０１−２からＭ段目の仮説生成部２０１−Ｍのそれぞれに付随して設けられたＭ個の仮説生成規則格納部１０１−１〜１０１−Ｍと、仮説補正部３０１−１〜３０１−Ｍと、各仮説補正部３０１−１〜３０１−Ｍのそれぞれに付随して設けたＭ個の仮説絞込み部４０１−１〜４０１−Ｍとによって構成される。
【０００５】
各仮説補正部３０１−１〜３０１−Ｍは、重み補正手段３０１Ａと、繰返し制御手段３０１Ｂと、を備える。重み補正手段３０１Ａは、後段の仮説生成部が生成した仮説の中の累積重みが最大又は最小となる特異値の値で、前段の仮説生成部が生成した仮説の累積重みを補正する。繰返し制御手段３０１Ｂは、その累積重みを補正する動作をＭ−１段目から１段目の仮説補正部まで繰返し実行させる。
【０００６】
仮説絞込み部４０１−１〜４０１−Ｍは、仮説抽出手段４０１Ａと、入力処理部４０１Ｂと、を備える。仮説抽出手段４０１Ａは、記号列が全て読み込まれた時点で、各仮説生成部２０１−１〜２０１−Ｍが生成した各仮説の補正された仮説中から累積重みが例えば最小となる仮説を抽出し、その仮説を次段の仮説絞り込み部に入力する処理を実行する。入力処理手段４０１Ｂは、仮説抽出手段４０１Ａが抽出した仮説を、次段の入力とする。
【０００７】
１段目の仮説生成部２０１−１は、入力される記号列の１個の記号入力に対して１段目の仮説生成規則格納部１０１−１に格納された仮説生成規則に基づいて仮説を生成する。仮説とは、ある記号列が順に入力され、現時点までに読み込まれた入力記号列に対して、仮説生成規則において所期状態からその入力記号列によって状態遷移を繰り返した場合の可能性のある一つの状態遷移過程を表すものである。
【０００８】
２段目以降の仮説生成部２０１−２〜２０１−Ｍには前段の仮説生成部が生成した仮説（候補記号列）が入力される。以降、１段目の仮説生成部２０１−１の出力する仮説と、２段目以降の仮説生成部２０１−２〜２０１−Ｍが出力する仮説とを区別する目的で、２段目以降の仮説生成部２０１−２〜２０１−Ｍが生成する仮説をｍ段目補助仮説或いは単に補助仮説と称する。
【０００９】
各仮説生成部２０１−１〜２０１−Ｍで生成される仮説は、各仮説生成規則格納部１０１−１〜１０１−Ｍに格納されている重み付き有限状態遷移過程を経て生成され、遷移過程の可能性に基づいて複数の仮説が生成される。各仮説には、重み付き有限状態遷移過程に付された条件に従って重みが付与される。重みは1段目の仮説生成部２０１−１から終段の仮説生成部２０１−Ｍまでの状態遷移に従って累積される。
【００１０】
終段の仮説生成部２０１−Ｍに仮説が生成されると、仮説補正部３０１−１〜３０１−Ｍが動作を開始する。仮説補正部３０１−Ｍは、仮説生成部２０１−Ｍが生成した仮説の中から、例えば累積重みが最小値を呈する仮説を抽出し、その仮説の累積重みを用いて前段のＭ−１段目の仮説生成部２０１−（Ｍ−１）が生成する仮説の累積重みを補正する。この補正は、終段で抽出した最小の累積重みを前段の仮説生成部２０１−（Ｍ−１）が生成した仮説の全ての累積重みに加算することで行われる。この補正は、初段の仮説生成部２０１−１が出力する仮説を補正するまで繰り返される。
【００１１】
全ての記号列が読み込まれ、仮説を補正する処理が終了すると、仮説絞り込み部４０１−１〜４０１−Ｍは、各仮説生成部２０１−１〜２０１−Ｍが生成した全ての仮説の中から累積重みの特異値を示す（もっともらしい）仮説を選択し、仮説を絞り込む。その絞り込み動作は以下の如くして行われえる。
【００１２】
初段の仮説絞込み部４０１−１は、初段の仮説生成部２０１−１が生成した仮説の中から累積重みが例えば最も小さい仮説を抽出し、その仮説を２段目の仮説生成部２０１−２に入力記号列として与え、２段目の仮説生成部２０１−２でこの入力記号列で可能な有限状態遷移過程に従って補助仮説を生成する。
【００１３】
２段目の仮説絞込み部３０１−２は、２段目仮説生成部２０１−２が生成した補助仮説の中から累積重みが例えば最も小さい仮説を抽出し、その補助仮説を３段目の仮説生成部２０１−３の入力記号列とする手順を終段の仮説生成部２０１−Ｍが出力する補助仮説まで繰り返す。終段の仮説絞込み部４０１−Ｍが終段の仮説生成部２０１−Ｍが生成した補助仮説の中から抽出した補助仮説が記号列出力部１０６に出力され、記号列の変換が終了する。
【００１４】
このように仮説生成部を多段縦続接続し、終段の仮説生成部が生成した仮説の中から累積重みが特異値を示す仮説を変換結果（音声認識結果）として出力することで、メモリの増大を回避している。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特許第４４７８０８８号
【発明の概要】
【発明が解決しようとする課題】
【００１６】
従来の記号列変換装置９００で変換できる記号列は、直前に位置する仮説生成規則の出力記号列が、後に位置する仮説生成規則の入力記号列にできる場合に限られる。例えば、クラス言語モデルによる音声認識においては、音響モデルによる仮説生成規則、トライフォンを音素に変換する仮説生成規則、単語発音辞書による仮説生成規則に加えて単語列をクラス列に変換する仮説生成規則、クラス言語モデルによる仮説生成規則を合成、或いはその仮説生成部を多段縦続接続することで音声認識を実施する。この音声認識処理の後に、例えば、言い換え処理を追加する場合、上記したクラス言語モデルによる仮説生成規則の出力はクラス列であるために、単語列を入力とする言い換え用の仮説生成規則を縦続接続することができない。
【００１７】
このように従来の記号列変換装置９００は、仮説生成規則の入力記号列が適合するものしか接続できない課題があり、汎用性に欠ける課題があった。
【００１８】
本発明は、この課題に鑑みてなされたものであり、仮説生成部の縦続接続の関係を任意の組み合わせに変更可能にすることで、従来は縦続接続不可能な仮説生成規則を従属可能にする記号列変換方法とそれを用いた音声認識方法と、それらの装置とプログラムとその記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明の記号列変換方法は、Ｍ個（Ｍ≧２）の縦続接続される仮説生成部と、仮説生成部のそれぞれに付随するＭ個の仮説補正部と、仮説補正部のそれぞれに付随するＭ個の仮説絞込み部と、縦続接続される仮説生成部の間に設けられ１段目の仮説生成部の入力記号列と前段及びそれより前の各仮説生成部の出力する出力記号列とを入力として次段の仮説生成部の入力記号列を選択する入力記号列選択部と、入力記号列選択部の選択する入力記号列選択情報と仮説絞込み部の抽出した仮説を出力とするか否かの出力選択情報とを記憶した入出力記号列配置記憶部とを備えた記号列変換装置を構成する。そして、1段目の仮説生成部が、入力される入力記号列に対して状態遷移が可能な状態遷移過程である仮説ｆ１を仮説生成規則に従って生成する仮説生成処理過程と、入力信号選択部が、入出力記号列配置記憶部を参照して１段目の仮説生成部へ入力する入力記号列と前段及びそれより前の各仮説生成部の出力する出力記号列の何れかの中から１つを選択してｍ段目（ｍは１〜Ｍまでの整数）の仮説生成部の入力記号列とし、ｍ段の仮説生成部が補助仮説ｆｍを生成する補助仮説生成過程を、ｍをインクリメントしながらＭ段目まで繰り返す補助仮説生成過程と、仮説補正部が、補助仮説ｆｍの累積重みで前段の補助仮説ｆｍ−１の重みを補正し、仮説ｆ１の累積重みを補助仮説の累積重みで補正するまでｍをデクリメントしながら繰り返す仮説補正過程と、仮説絞込み部が、補正された累積重みが特異値を呈する仮説或いは補助仮説を抽出し、抽出した仮説或いは補助仮説を次段の仮説絞込み部の入力記号列とする。
【００２０】
また、本願発明の音声認識方法は、上記した記号列変換方法に加えて、音声特徴記号列抽出過程を備える。音声特徴記号列抽出過程は、音声信号を入力として音声の短時間音響パターンの時系列から音響特徴記号列を抽出する。そして、初段の仮説生成部は、音声特徴記号列抽出部で抽出した音響特徴を表す記号列を入力とし、音声固定単位の標準的特徴を備えた音響モデル用仮説生成規則と、種々の単語の発音を上記音声固定単位の系列に対応させる単語発音辞書用仮説生成用規則とを参照して、単語系の記号列を出力記号列とする仮説を生成する。
【発明の効果】
【００２１】
本発明の記号列変換方法によれば、入出力記号列配置記憶部に記憶した情報に基づいて入力記号列が適合する仮説生成部を任意に組み合わせることが出来るので、例えばクラス言語モデル用の仮説生成規則の後に、単語列を入力とする仮説生成規則を縦続接続することが可能になり、記号列変換方法の汎用性を高めることができる。また、この発明の記号列変換方法を用いた音声認識方法によれば、例えばクラス言語モデルを用いた場合でも、言い換え処理などの処理の追加を容易に行うことが可能になる。
【図面の簡単な説明】
【００２２】
【図１】この発明の記号列変換装置１００の機能構成例を示す図。
【図２】記号列変換装置１００の概略的な動作フローを示す図。
【図３】この発明の記号列変換装置２００の機能構成例を示す図。
【図４】アルファベット−ひらがな変換規則格納部２１０１に記憶されている仮説生成規則Ｔ１を示す図。
【図５】ひらがな−漢字変換規則格納部２１０２に記憶されている仮説生成規則Ｔ２を示す図。
【図６】ひらがな−カタカナ変換規則格納部２１０３に記憶されている仮説生成規則Ｔ３を示す図。
【図７】入出力記号列配置記憶部１５に記憶された情報の例を示す図。
【図８】この発明の記号列変換装置２００の動作フローを示す図。
【図９】この発明の記号列変換装置２００の動作フローを示す図。
【図１０】この発明の記号列変換装置２００の動作フローを示す図。
【図１１】この発明の記号列変換装置２００の動作フローを示す図。
【図１２】この発明の音声認識装置３００の機能構成例を示す図。
【図１３】音声認識装置３００の入出力記号列配置記憶部１５′に記憶された情報の例を示す図。
【図１４】従来の記号列変換装置９００の機能構成を示す図。
【発明を実施するための形態】
【００２３】
以下、この発明の実施の形態を図面を参照して説明する。複数の図面中同一のものには同じ参照符号を付し、説明は繰り返さない。
【実施例１】
【００２４】
図１に、この発明の記号列変換装置１００の機能構成例を示す。記号列変換装置１００は、Ｍ個（Ｍ≧２）の縦続接続される仮説生成部１０１〜１０Ｍと、各仮説生成部１０１〜１０Ｍのそれぞれに付随するＭ個の仮説補正部１２１〜１２Ｍと、各仮説補正部１２１〜１２Ｍに付随するＭ個の仮説絞込み部１３１〜１３Ｍと、縦続接続される仮説生成部１０１〜１０Ｍの間に設けられ１段目の仮説生成部の入力記号列と前段より前の仮説生成部の出力する記号列とを入力として次段の仮説生成部の入力記号列を選択する入力記号列選択部１４１〜１４Ｍ−１と、入力記号列選択部１４１〜１４Ｍ−１の選択する入力記号列選択情報と仮説絞込み部１３１〜１３Ｍの抽出した仮説を出力とするか否かの出力選択情報とを記憶した入力記号列配置記憶部１５と、各部の時系列的な動作を制御する制御部１６と、を具備する。記号列変換装置１００は、例えばＲＯＭ、ＲＡＭ、ＣＰＵ等で構成されるコンピュータに所定のプログラムが読み込まれて、ＣＰＵがそのプログラムを実行することで実現されるものである。
【００２５】
図２に、記号列変換装置１００の概略的な動作フローを示してその動作を説明する。１段目の仮説生成部１１１は、入力される入力記号列に対して状態遷移が可能な状態遷移過程である仮説ｆ１を仮説生成規則に従って生成する（ステップＳ１１ａ，１１ｂ）。各ステップの中の（・）は、後述する詳細な動作フローチャートで対応する動作ステップを表す。
【００２６】
入力記号選択部１４ｍが、入出力記号列配置記憶部１５を参照して１段目の仮説生成部１１１へ入力する入力記号列と前段及びそれより前の各仮説生成部１１１〜１１ｍ−１の出力する出力記号列の何れかを選択してｍ段目（ｍは１〜Ｍまでの整数）の仮説生成部１１ｍの入力記号列とし、ｍ段目の仮説生成部１１ｍが補助仮説ｆｍを生成する過程を、ｍをインクリメントしながらＭ段目まで繰り返す（ステップＳ１２ａ，１２ｂ，１２ｃ）。１段目の入力記号選択部１４１は、入力記号列と仮説生成部１１１の出力する出力記号列の何れか一方を、入出力記号列配置記憶部１５を参照し選択して仮説生成部１１２に出力する。最終段の入力記号選択部１４Ｍ−１は、１段目の仮説生成部１１１へ入力する入力記号列と前段及びそれより前の各仮説生成部１１１〜１１Ｍ−１の複数の出力記号列の中から１個の記号列を、入出力記号列配置記憶部１５を参照し選択して仮説生成部１１Ｍに出力する。
【００２７】
各仮説補正部１２ｍが、補助仮説ｆｍの累積重みで前段の補助仮説ｆｍ−１の重みを補正し、仮説ｆ１の累積重みを補助仮説の累積重みで補正するまでｍをデクリメントしながら繰り返す（ステップＳ１２ｄ，１２ｃ）。ここで補正とは、前段の仮説生成部１１ｍ−１の一つの状態遷移過程を表す仮説に対する累積重みを、その仮説を補助仮説とする、入出力記号列配置記憶部１５を参照して選択される仮説生成部１１１〜１１ｍ−１の何れかの仮説或いは補助仮説の出力記号列を後段の仮説生成部１１ｍの入力記号列としたときの後段の仮説生成部１１ｍにおいて可能な状態遷移過程の中で累積重みが最小となる状態遷移を求め、その累積重みを仮説の累積重みに加算することである。
【００２８】
仮説絞込み部１３ｍが、補正された累積重みが特異値を呈する仮説或いは補助仮説を抽出し、抽出した仮説或いは補助仮説を次段の仮説絞込み部１３ｍ＋１の入力とし、最終段の仮設絞込み部１３Ｍの抽出した補助仮説を外部に出力する（ステップＳ１３ａ）。仮説絞込み部１３ｍは、入出力記号列配置記憶部１５を参照して抽出した仮説或いは補助仮説を、直接外部に出力するようにしても良い（ステップＳ１３ｂ）。
【００２９】
以上説明したように記号列変換装置１００によれば、入出力記号列配置記憶部１５に記憶した情報に基づいて入力記号選択部１４ｍが次段の仮説生成部１１ｍの入力記号列を選択するので、例えば、ひらがな−漢字変換の仮説生成規則を用いて仮説生成した後に、ひらがな−カタカナ変換の仮説生成規則を用いる仮説生成部を設けることが可能である。よって、記号列変換方法の汎用性を高めることが出来る。
【００３０】
図３に、記号列変換装置２００の機能構成例を示してより具体的にこの発明を説明する。記号列変換装置２００は、１段目の仮説生成部２１１１の仮説生成規則がアルファベット−ひらがな変換規則（Ｔ１：図４）、２段目の仮説生成部２１１２の仮説生成規則がひらがな−漢字変換規則（Ｔ２：図５）、３段目の最終段の仮説生成部２１１３の仮説生成規則がひらがな−カタカナ変換規則（Ｔ３：図６）、としたものである。各変換規則Ｔ１〜Ｔ３はそれぞれ、アルファベット−ひらがな変換規則格納部２１０１とひらがな−漢字変換規則格納部２１０２とひらがな−カタカナ変換規則格納部２１０３に記憶されている。図７に、入出力記号列配置記憶部２１５に記憶された情報を示す。その情報の１列目は仮説生成部２１１１〜２１１３の段番号、２列目は各仮説生成部の入力記号列になる仮説生成部の出力記号列の段番号、３列目は仮説絞込み部が補助仮説を出力するか否かを表す値、である。
【００３１】
この記号列変換装置２００に、入力記号列として「ａ，ｍ，ｅ，ｄ，ａ，ｍ，ａ」を入力した場合を例にその動作を説明する。その動作フローを図８〜図１１に示す。仮説生成規則Ｔ１の現状状態番号をｓ１、出力記号列をＯ、累積重みをＷ、補助仮説リストをＬとして（ｓ１，Ｏ，Ｗ，Ｌ）のように表す。ｍ段目の補助仮説は同様に（ｓｍ，Ｏ，Ｗ，Ｌｍ）のように表す。また、ｍ段目補助仮説リストは{（ｓｍ，Ｏ，Ｗ，Ｌｍ），（ｓｍ′，Ｏ′，Ｗ′，Ｌｍ′），…}のように表す。
【００３２】
記号列変換装置２００が動作を開始する（ステップＳ４０１）と、制御部２１６は、記号列変換装置２００を構成するコンピュータの記憶手段である例えばＲＡＭに、空の仮説リストＨとＨ′を作成する（ステップＳ４０２）。そして仮説リストＨの中に仮説ｈ＝（０，φ，０，{（０，φ，０，φ）}）を挿入する（ステップＳ４０３）。
【００３３】
〔“ａ”の処理〕
仮説生成部２１１１は、入力記号列の記号“ａ”を読み込む（ステップＳ４０４）。そして、仮説リストＨから仮説（０，φ，０，{（０，φ，０，φ）}）を取り出し、アルファベット−ひらがな変換規則の現状態０から入力記号が“ａ”の状態遷移〈０→０，ａ：あ／０〉を含むリストＥ１を作成する（ステップＳ４０５）。このときｍ＝１に設定する。
【００３４】
仮説生成部２１１１は、リストＥ１＝φ（内容が無い）ではないのでリストＥ１から状態遷移〈０→０，ａ：あ／０〉を取り出し（ステップＳ４０７）、新たな仮説ｆ１＝（０，あ，０，{（０，φ，０，{（０，φ，０，φ）}）}を生成する（ステップＳ４０８）。
【００３５】
仮説ｆ１が生成されると、２段目の仮説生成部２１１２が動作を開始する（ステップＳ４０９）。このときｍ＝２に設定する。入力記号選択部２１４１は、入出力記号列配置記憶部２１５を参照してｍ＝２の入力記号段番号ｎがｎ＝１（図７）であるので、仮説生成部２１１１の出力する記号列ｏ[ｅ１]を選択して仮説生成部２１１２に入力する。仮説補正部２１２１は、空の補助仮説リストＬ２を生成する（ステップＳ５０２）。そして、入力された記号列ｏ[ｅ１]がε（空）でないので、仮説生成部２１１２の処理であるステップＳ５０３に進む。
【００３６】
仮説生成部２１１２は、式（１）の計算を行って重みの補正項ＡＷ[ｆ１]を求める。
【００３７】
【数１】
2014081516.tif 000003
【００３８】
この場合ＡＷ[ｆ１]＝０となる。仮説生成部２１１２は、補助仮説リストＬ[ｆ１]＝{（０，φ，０，{０，φ，０，φ}）}から補助仮説ｇ２＝（０，φ，０，{０，φ，０，φ}）を取り出し、仮説生成規則Ｔ２（ひらがな−漢字変換規則格納部２１０２）から入力記号がｏ[ｅ１]＝“あ”の遷移可能な状態遷移〈０→１，あ：雨／０〉，〈０→２，あ：飴／０〉を含むリストＥ２を作成する（ステップＳ５０４）。
【００３９】
Ｅ２＝φ（内容が無い）ではないので（ステップＳ５０５のＮ）、リストＥ２から状態遷移〈０→１，あ：雨／０〉を取り出してリストｅ２とし（ステップＳ５０６）、補助仮説ｆ２＝（１，雨，０{（０，φ，０，φ）}を生成する（ステップＳ５０７）。
【００４０】
この時点でｍ＝２，Ｍ＝３なのでｍ＜Ｍであることからｍをインクリメントしてｍ＝３として、３段目の仮説生成部２１１３が動作を開始する。入力記号選択部２１４２は、入出力記号列配置記憶部２１５を参照してｍ＝３の入力記号段番号ｎがｎ＝１（図７）であるので、仮説生成部２１１１の出力する記号列ｏ[ｅ１]を選択して仮説生成部２１１３に入力する。仮説補正部２１２３は、空の補助仮説リストＬ３を生成する（ステップＳ５０２）。そして、入力された記号列ｏ[ｅ１]がε（空）でないので、仮説生成部２１１３の処理であるステップＳ５０３に進む。
【００４１】
仮説生成部２１１３は、式（１）の計算を行って重みの補正項ＡＷ[ｆ２]を求める。この場合ＡＷ[ｆ２]＝０となる。仮説生成部２１１３は、補助仮説リストＬ[ｆ２]＝{（０，φ，０，φ）}から補助仮説ｇ３＝（０，φ，０，φ）を取り出し、仮説生成規則Ｔ３（ひらがな−カタカナ変換規則格納部２１０３）から入力記号がｏ[ｅ１]＝“あ”の遷移可能な状態遷移〈０→０，あ：ア／０〉を含むリストＥ３を作成する（ステップＳ５０４）。
【００４２】
Ｅ３＝φ（内容が無い）ではないので（ステップＳ５０５のＮ）、リストＥ３から状態遷移〈０→０，あ：ア／０〉を取り出してリストｅ３とし、補助仮説ｆ３＝（０，ア，０，φ）を生成する（ステップＳ５０７）。
【００４３】
ステップＳ５０８でｍ＝３，Ｍ＝３なのでｍ＜Ｍでないことから、次段の仮説生成部は存在しないので、仮説生成部２１１３は補助仮説ｆ３を補助仮説リストＬ３に挿入する（ステップＳ５０９）。この結果リストＥ３は空（φ）になる。
【００４４】
リストＥ３＝φになると、仮説補正部２１２３が動作を開始する。そして、補助仮説リストＬ[ｆ２]＝φなので、補助仮説リストＬ３の要素{０，ア，０，φ）}を、前段の仮説補正部２１２２の補助仮説リストＬ[ｆ２]に移す（ステップＳ５１１）。
【００４５】
補助仮説リストＬ[ｆ２]の補助仮説の累積重みは０なのでＷ[ｆ２]＝０とした後に、補助仮説ｆ２＝（１，雨，０{（０，φ，０，φ）}の補正を終了し、ｍを１減らしてｍ＝２とした後（ステップＳ５１３）、ステップＳ５０８に戻る（ステップＳ５１４）。
【００４６】
ステップＳ５０８におけるｆ２の補正手順の後、ステップＳ５０９に進む。ステップＳ５０９では、ｆ２をＬ２に挿入し、ステップＳ５０５に戻る。ステップＳ５０５でＥ２＝φではないのでステップＳ５０６に進む。リストＥ２から状態遷移〈０→２，あ：飴／０〉を取り出しリストｅ２とし、ステップＳ５０７で補助仮説ｆ２＝（２，飴，０，{（０，φ，０，φ）}）を生成する。ステップＳ５０８で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やしてｍ＝３に設定する。
【００４７】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がφでないのでステップＳ５０３に進む。ステップＳ５０３でＡＷ[ｆ２]＝０となる。
【００４８】
ステップＳ５０４で補助仮説リストＬ[ｆ２]＝{（０，φ，０，φ）}から補助仮説ｇ３＝（０，φ，０，φ）を取り出し、仮説生成規則Ｔ３の状態０から入力記号がｏ[ｅ１]＝“あ”の遷移可能な状態遷移〈０→０，あ：ア／０〉を含むリストＥ３を作る。
【００４９】
ステップＳ５０５でＥ３＝φではないのでステップＳ５０６に進む。Ｅ３から状態遷移〈０→０，あ：ア／０〉を取り出しｅ３とし、ステップＳ５０７で補助仮説ｆ３＝（０，ア，０，φ）を生成する。ステップＳ５０８でｍ＝３かつＭ＝３なのでｍ＜Ｍではないから、ステップＳ５０９に進み、補助仮説ｆ３をリストＬ３に挿入する。ステップＳ５０５に戻り、Ｅ３＝φなのでステップＳ５１０に進む。
【００５０】
ステップＳ５１０で、補助仮説リストＬ[ｆ２]＝φなのでステップＳ５１１に進む。ステップＳ５１１で、補助仮説リストＬ３の要素を全て補助仮説リストＬ[ｆ２]に移す
ステップＳ５１２で、Ｌ[ｆ２]の補助仮説中の累積重み最小の補助仮説ｇ３′の累積重みは０なのでＷ[ｆ２]＝０とする。ステップＳ５１３でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５０８に戻る。
【００５１】
ステップＳ５０８におけるｆ２の補正手順の後、ステップＳ５０９に進む。ステップＳ５０９では、ｆ２をＬ２に挿入し、ステップＳ５０５に戻る。ステップＳ５０５でＥ２＝φであるため、ステップＳ５１０に進む。ステップＳ５１０で、Ｌ[ｆ１]＝φなので、ステップＳ５１１に進む。ステップＳ５１１で、補助仮説リストＬ２の要素をすべてＬ[ｆ１]に移す。ステップＳ５１２で、Ｌ[ｆ１]＝｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝の補助仮説の累積重みはどちらも０なのでＷ[ｆ１]＝０とする。ステップＳ５１４で補助仮説ｆ１の補正を終了し、ステップＳ４０９に戻る。
【００５２】
ステップＳ４０９における仮説ｆ１の補正手順の後、ステップＳ４１０に進む。ステップＳ４１０では、仮説ｆ１を仮説リストＨ’に挿入し、ステップＳ４０６に戻る。ステップＳ４０６で状態遷移リストＥ１＝φなので、ステップＳ４１１に進む。ステップＳ４１１で仮説リストＨ＝φなので、ステップＳ４１２に進み、Ｈ’の要素｛（０，あ，０，｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝）｝を仮説リストＨに移す。ステップＳ４１３に進み、次の入力記号が存在するので、ステップＳ４０４に戻る。
【００５３】
〔“ｍ”の処理〕
ステップＳ４０４で記号“ｍ”を読み込み、ステップＳ４０５において仮説リストＨから仮説ｈ＝（０，あ，０，｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝）を取り出す。この仮説の仮説生成規則Ｔ１の現状態０から入力記号が“ｍ”の状態遷移＜０→１，ｍ：ε／０＞を含むリストＥ１を作る。
【００５４】
ステップＳ４０６でＥ１＝φではないのでステップＳ４０７に進み、状態遷移リストＥ１から状態遷移＜０→０，ｍ：ε／０＞を取り出しｅ１とし、ステップＳ４０８で新たな仮説ｆ１＝（１，あ，０，｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝）を生成する。ステップＳ４０９で仮説ｆ１を補正するステップＳ５０１に進む。このときｍ＝２に設定する。
【００５５】
ステップＳ５０２（ｍ＝２）で空の補助仮説リストＬ２を生成する。ステップＳ５２１（ｍ＝２）で、入出力記号列配置記憶部２１５を参照してｍ＝２への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεなのでステップＳ５２２（ｍ＝２）に進む。ステップＳ５２２（ｍ＝２）で補助仮説リストＬ[ｆ１]＝｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝から補助仮説ｆ２＝（１，雨，０，｛（０，ア，０，φ）｝）を取り出す。
【００５６】
ステップＳ５２３（ｍ＝２）で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。
【００５７】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεなのでステップＳ５２２（ｍ＝３）に進む。ステップＳ５２２（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，ア，０，φ）｝から補助仮説ｆ３＝（０，ア，０，φ）｝を取り出す。
【００５８】
ステップＳ５２３（ｍ＝３）で、ｍ＝３でＭ＝３なのでｍ＜Ｍでないから、ステップＳ５２４（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。ステップＳ５２５（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１に進む。ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素｛（０，ア，０，φ）｝をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは０なのでＷ[ｆ２]＝０とする。ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５２３（ｍ＝２）に戻る。
【００５９】
ステップＳ５２３（ｍ＝２）におけるｆ２の補正手順の後、ステップＳ５２４（ｍ＝２）に進む。ステップＳ５２４（ｍ＝２）でｆ２をＬ２に挿入する。ステップＳ５２５でL［ｆ１］がφでないので、ステップＳ５２２（ｍ＝２）に戻る。ステップＳ５２２（ｍ＝２）で補助仮説リストＬ[ｆ１]＝｛（２，飴，０，｛（０，ア，０，φ）｝）｝から補助仮説ｆ２＝（２，飴，０，｛（０，ア，０，φ）｝）を取り出す。ステップＳ５２３（ｍ＝２）で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。
【００６０】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεなのでステップＳ５２２（ｍ＝３）に進む。ステップＳ５２２（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，ア，０，φ）｝から補助仮説ｆ３＝（０，ア，０，φ）｝を取り出す。
【００６１】
ステップＳ５２３（ｍ＝３）で、ｍ＝３でＭ＝３なのでｍ＜Ｍでないから、ステップＳ５２４（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。ステップＳ５２５（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１に進む。ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素｛（０，ア，０，φ）｝をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは０なのでＷ[ｆ２]＝０とする。ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５２３（ｍ＝２）に戻る。ステップＳ５２３（ｍ＝２）におけるｆ２の補正手順の後、ステップＳ５２４（ｍ＝２）に進む。ステップＳ５２４（ｍ＝２）では、ｆ２をＬ２に挿入し、ステップＳ５２２（ｍ＝２）に戻る。
【００６２】
ステップＳ５２２（ｍ＝２）で補助仮説リストＬ[ｆ１]＝｛（２，飴，０，｛（０，ア，０，φ）｝）｝から補助仮説ｆ２＝（２，飴，０，｛（０，ア，０，φ）｝）を取り出す。ステップＳ５２５（ｍ＝２）で、Ｌ[ｆ１]＝φなので、ステップＳ５１１（ｍ＝２）に進む。ステップＳ５１１（ｍ＝２）で、補助仮説リストＬ２の要素をすべてＬ[ｆ１]に移す。ステップＳ５１２（ｍ＝２）で、Ｌ[ｆ１]＝｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝の補助仮説の累積重みはどちらも０なのでＷ[ｆ１]＝０とする。ステップＳ５１４（ｍ＝２）で補助仮説ｆ１の補正を終了し、ステップＳ４０９に戻る。
【００６３】
ステップＳ４０９における仮説ｆ１の補正手順の後、ステップＳ４１０に進む。ステップＳ４１０では仮説ｆ１を仮説リストＨ’に挿入し、ステップＳ４０６に進む。ステップＳ４０６では状態遷移リストＥ１＝φなのでステップＳ４１１に進み、仮説リストＨ＝φなのでステップＳ４１２に進む。ステップＳ４１２では仮説リストＨ’の要素｛（１，あ，０，｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝）｝をすべて仮説リストＨに移す。ステップＳ４１３に進み、次の入力記号が存在するので、ステップＳ４０４に戻る。
【００６４】
〔“ｅ”の処理〕
ステップＳ４０４で記号“ｅ”に読み込み、ステップＳ４０５において仮説リストＨから仮説ｈ＝（１，あ，０，｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝）を取り出す。この仮説の仮説生成規則Ｔ１の現状態０から入力記号が“ｅ”の状態遷移＜１→０，ｅ：め／０＞を含む状態遷移リストＥ１を作る。
【００６５】
ステップＳ４０６でＥ１＝φではないのでステップＳ４０７に進み、Ｅ１から状態遷移＜１→０，ｅ：め／０＞を取り出しｅ１とし、ステップＳ４０８で新たな仮説ｆ１＝（０，あめ，０，｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝）を生成する。ステップＳ４０９で仮説ｆ１を補正するステップＳ５０１に進む。このときｍ＝２に設定する。
【００６６】
ステップＳ５０２で空の補助仮説リストＬ２を生成する。ステップＳ５２１で、入出力記号列配置記憶部２１５を参照してｍ＝２への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεでないのでステップＳ５０３に進むステップＳ５０３でＡＷ[ｆ１]＝０となる。
ステップＳ５０４で補助仮説リストＬ[ｆ１]＝｛（１，雨，０，｛（０，ア，０，φ）｝），（２，飴，０，｛（０，ア，０，φ）｝）｝から補助仮説ｇ２＝（１，雨，０，｛（０，ア，０，φ）｝）を取り出し、仮説生成規則Ｔ２の状態１から入力記号“め”で遷移可能な状態遷移＜１→５，め：ε／１＞を含む状態遷移リストＥ２を作る。
【００６７】
ステップＳ５０５で状態遷移Ｅ２＝φではないのでステップＳ５０６に進む。状態遷移リストＥ２から状態遷移＜１→５，め：ε／１＞を取り出しｅ２とし、ステップＳ５０７でＷ［ｆ２］＝０＋０＋１＝１である補助仮説ｆ２＝（５，雨，１，｛（０，ア，０，φ）｝）を生成する。
【００６８】
ステップＳ５０８で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。
【００６９】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がφでないのでステップＳ５０３に進む。ステップＳ５０３（ｍ＝３）でＡＷ[ｆ２]＝１−０＝１となる。
【００７０】
ステップＳ５０４（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，ア，０，φ）｝から補助仮説ｇ３＝（０，ア，０，φ）を取り出し、仮説生成規則Ｔ３の状態０から入力記号がｏ[ｅ１]=“め”の遷移可能な状態遷移＜０→０，め：メ／０＞を含むリストＥ３を作る。ステップＳ５０５（ｍ＝３）でＥ３＝φではないのでステップＳ５０６（ｍ＝３）に進む。Ｅ３から状態遷移＜０→０，め：メ／０＞を取り出しｅ３とし、ステップＳ５０７（ｍ＝３）でＷ［ｆ３］＝０＋１＋０＝１となる補助仮説ｆ３＝（０，アメ，１，φ）を生成する。
【００７１】
ステップＳ５０８（ｍ＝３）でｍ＝３かつＭ＝３なのでｍ＜Ｍではないから、ステップＳ５０９（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。ステップＳ５０５（ｍ＝３）に戻り、Ｅ３＝φなので、ステップＳ５１０（ｍ＝３）に進む。ステップＳ５１０（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１（ｍ＝３）に進む。ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは１なのでＷ[ｆ２]＝１とする。ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５０８に戻る。
【００７２】
ステップＳ５０８におけるｆ２の補正手順の後、ステップＳ５０９に進む。ステップＳ５０９では、ｆ２をＬ２に挿入し、ステップＳ５０５に戻る。ステップＳ５０５でＥ２＝φであるため、ステップＳ５１０に進む。ステップＳ５１０で、Ｌ[ｆ１]＝φでないので、ステップＳ５０４に戻る。
【００７３】
ステップＳ５０４で補助仮説リストＬ[ｆ１]＝｛（２，飴，０，｛（０，ア，０，φ）｝）｝から補助仮説ｇ２＝（２，飴，０，｛（０，ア，０，φ）｝）を取り出し、仮説生成規則Ｔ２の状態２から入力記号“め”で遷移可能な状態遷移＜２→５，め：ε／２＞を含む状態遷移リストＥ２を作る。
【００７４】
ステップＳ５０５で状態遷移Ｅ２＝φではないのでステップＳ５０６に進む。状態遷移リストＥ２から状態遷移＜２→５，め：ε／２＞を取り出しｅ２とし、ステップＳ５０７でＷ［ｆ２］＝０＋０＋２＝２である補助仮説ｆ２＝（５，飴，２，｛（０，ア，０，φ）｝）を生成する。
【００７５】
ステップＳ５０８で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がφでないのでステップＳ５０３に進む。ステップＳ５０３（ｍ＝３）でＡＷ[ｆ２]＝２−０＝２となる。
【００７６】
ステップＳ５０４（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，ア，０，φ）｝から補助仮説ｇ３＝（０，ア，０，φ）を取り出し、仮説生成規則Ｔ３の状態０から入力記号がｏ[ｅ１]=“め”の遷移可能な状態遷移＜０→０，め：メ／０＞を含むリストＥ３を作る。
【００７７】
ステップＳ５０５（ｍ＝３）でＥ３＝φではないのでステップＳ５０６（ｍ＝３）に進む。Ｅ３から状態遷移＜０→０，め：メ／０＞を取り出しｅ３とし、ステップＳ５０７（ｍ＝３）でＷ［ｆ３］＝０＋２＋０＝２となる補助仮説ｆ３＝（０，アメ，２，φ）を生成する。
【００７８】
ステップＳ５０８（ｍ＝３）でｍ＝３かつＭ＝３なのでｍ＜Ｍではないから、ステップＳ５０９（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。ステップＳ５０５（ｍ＝３）に戻り、Ｅ３＝φなので、ステップＳ５１０（ｍ＝３）に進む。ステップＳ５１０（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１（ｍ＝３）に進む。ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは１なのでＷ[ｆ２]＝１とする。ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５０８に戻る。ステップＳ５０８におけるｆ２の補正手順の後、ステップＳ５０９に進む。ステップＳ５０９では、ｆ２をＬ２に挿入し、ステップＳ５０５に戻る。但し、Ｌ２には既に補助仮説（５，雨，１，｛（０，アメ，１，φ）｝）が存在し、仮説生成規則Ｔ２における到達状態が５であるため、累積重みの小さい補助仮説（５，雨，１，｛（０，アメ，１，φ）｝）を残し、（５，飴，２，｛（０，アメ，２，φ）｝）は削除する。このとき、それぞれの補助仮説の補助仮説リストは累積重みを修正して連結させ（５，雨，１，｛（０，アメ，１，φ），（０，アメ，２，φ）｝）とする。さらに、この補助仮説の補助仮説リストに仮説生成規則Ｔ３における到達状態が０であるため、累積重みの小さい補助仮説（０，アメ，１，φ）を残し、（５，雨，１，｛（０，アメ，１，φ）｝）とする。
【００７９】
また、状態５に到達した補助仮説は、状態遷移＜５→０，ε：ε／０＞経由して、入力記号なしで状態０に到達するので、補助仮説リストＬ２には補助仮説、（０，雨，１，｛（０，アメ，１，φ）｝）が残る。ステップＳ５０５でＥ２＝φであるため、ステップＳ５１０に進む。ステップＳ５１０で、Ｌ[ｆ１]＝φなので、ステップＳ５１１に進む。ステップＳ５１１で、Ｌ２の要素をすべてＬ[ｆ１]に移す。ステップＳ５１２で、Ｌ[ｆ１]の補助仮説の累積重みは１なのでＷ[ｆ１]＝１とする。ステップＳ５１４で補助仮説ｆ１の補正を終了し、ステップＳ４０９に戻る。ステップＳ４０９における仮説ｆ１の補正手順の後、ステップＳ４１０に進む。ステップＳ４１０では、仮説ｆ１を仮説リストＨ’に挿入し、ステップＳ４０６に戻る。ステップＳ４０６で状態遷移リストＥ１＝φなので、ステップＳ４１１に進む。ステップＳ４１１で仮説リストＨ＝φなので、ステップＳ４１２に進み、Ｈ’の要素｛（０，あめ，１，｛（０，雨，１，｛（０，アメ，１，φ）｝）｝を仮説リストＨに移す。ステップＳ４１３に進み、次の入力記号が存在するので、ステップＳ４０４に戻る。
【００８０】
〔“ｄ”の処理〕
ステップＳ４０４で記号“ｄ”を読み込み、ステップＳ４０５において仮説リストＨから仮説ｈ＝（０，あめ，１，｛（０，雨，１，｛（０，アメ，１，φ）｝）を取り出す。この仮説の仮説生成規則Ｔ１の現状態０から入力記号が“ｍ”の状態遷移＜０→３，ｄ：ε／０＞を含むリストＥ１を作る。ステップＳ４０６でＥ１＝φではないのでステップＳ４０７に進み、状態遷移リストＥ１から状態遷移＜０→3，ｄ：ε／０＞を取り出しｅ１とし、ステップＳ４０８で新たな仮説ｆ１＝（３，あめ，１，｛（０，雨，１，｛（０，アメ，１，φ）｝）を生成する。ステップＳ４０９で仮説ｆ１を補正するステップＳ５０１に進む。このときｍ＝２に設定する。
【００８１】
ステップＳ５０２（ｍ＝２）で空の補助仮説リストＬ２を生成する。ステップＳ５２１（ｍ＝２）で、入出力記号列配置記憶部２１５を参照してｍ＝２への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεなのでステップＳ５２２（ｍ＝２）に進む。ステップＳ５２２（ｍ＝２）で補助仮説リストＬ[ｆ１]＝｛（０，雨，１，｛（０，アメ，１，φ）｝から補助仮説ｆ２＝（０，雨，１，｛（０，アメ，１，φ）を取り出す。ステップＳ５２３（ｍ＝２）で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。
【００８２】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεなのでステップＳ５２２（ｍ＝３）に進む。ステップＳ５２２（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，アメ，１，φ）｝から補助仮説ｆ３＝（０，アメ，１，φ）を取り出す。ステップＳ５２３（ｍ＝３）で、ｍ＝３でＭ＝３なのでｍ＜Ｍでないから、ステップＳ５２４（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。ステップＳ５２５（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１に進む。
【００８３】
ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素｛（０，アメ，１，φ）｝をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは１なのでＷ[ｆ２]＝１とする。ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５２３（ｍ＝２）に戻る。
【００８４】
ステップＳ５２３（ｍ＝２）におけるｆ２の補正手順の後、ステップＳ５２４（ｍ＝２）に進む。ステップＳ５２４（ｍ＝２）でｆ２をＬ２に挿入する。ステップＳ５２５（ｍ＝２）で、Ｌ[ｆ１]＝φなので、ステップＳ５１１（ｍ＝２）に進む。ステップＳ５１１（ｍ＝２）で、補助仮説リストＬ２の要素をすべてＬ[ｆ１]に移す。ステップＳ５１２（ｍ＝２）で、Ｌ[ｆ１]＝｛（０，雨，１，｛（０，アメ，１，φ）｝）｝の補助仮説の累積重みは１なのでＷ[ｆ１]＝１とする。ステップＳ５１４（ｍ＝２）で補助仮説ｆ１の補正を終了し、ステップＳ４０９に戻る。
【００８５】
ステップＳ４０９における仮説ｆ１の補正手順の後、ステップＳ４１０に進む。ステップＳ４１０では仮説ｆ１を仮説リストＨ’に挿入し、ステップＳ４０６に進む。ステップＳ４０６では状態遷移リストＥ１＝φなのでステップＳ４１１に進み、仮説リストＨ＝φなのでステップＳ４１２に進む。ステップＳ４１２では仮説リストＨ’の要素｛（３，あめ，１，｛（０，雨，１，｛（０，アメ，１，φ）｝）｝）｝をすべて仮説リストＨに移す。ステップＳ４１３に進み、次の入力記号が存在するので、ステップＳ４０４に戻る。
【００８６】
〔“ａ”の処理〕
ステップＳ４０４で記号“a”に読み込み、ステップＳ４０５において仮説リストＨから仮説ｈ＝（３，あめ，１，｛（０，雨，１，｛（０，アメ，１，φ）｝）｝）を取り出す。この仮説の仮説生成規則Ｔ１の現状態０から入力記号が“ｅ”の状態遷移＜３→０，a：だ／０＞を含む状態遷移リストＥ１を作る。ステップＳ４０６でＥ１＝φではないのでステップＳ４０７に進み、Ｅ１から状態遷移＜１→０，ｅ：め／０＞を取り出しｅ１とし、ステップＳ４０８で新たな仮説ｆ１＝（０，あめだ，１，｛（０，雨，１，｛（０，アメ，１，φ）｝）｝）を生成する。ステップＳ４０９で仮説ｆ１を補正するステップＳ５０１に進む。このときｍ＝２に設定する。
【００８７】
ステップＳ５０２で空の補助仮説リストＬ２を生成する。ステップＳ５２１で、入出力記号列配置記憶部２１５を参照してｍ＝２への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεでないのでステップＳ５０３に進むステップＳ５０３でＡＷ[ｆ１]＝０となる。
ステップＳ５０４で補助仮説リストＬ[ｆ１]＝｛（０，雨，１，｛（０，アメ，１，φ）｝）｝から補助仮説ｇ２＝（０，雨，１，｛（０，アメ，１，φ）｝）を取り出し、仮説生成規則Ｔ２の状態１から入力記号ｏ[ｅ１]＝“だ”で遷移可能な状態遷移＜０→４，だ：玉／１＞を含む状態遷移リストＥ２を作る。
【００８８】
ステップＳ５０５で状態遷移Ｅ２＝φではないのでステップＳ５０６に進む。状態遷移リストＥ２から状態遷移＜０→４，だ：玉／１＞を取り出しｅ２とし、ステップＳ５０７でＷ［ｆ２］＝１＋０＋１＝２である補助仮説ｆ２＝（４，雨玉，２，｛（０，アメ，１，φ）｝）を生成する。ステップＳ５０８で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。
【００８９】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がφでないのでステップＳ５０３に進む。ステップＳ５０３（ｍ＝３）でＡＷ[ｆ２]＝２−１＝１となる。
【００９０】
ステップＳ５０４（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，アメ，１，φ）｝から補助仮説ｇ３＝（０，アメ，１，φ）を取り出し、仮説生成規則Ｔ３の状態０から入力記号ｏ[ｅ１]＝“だ”の遷移可能な状態遷移＜０→０，だ：ダ／０＞を含むリストＥ３を作る。
【００９１】
ステップＳ５０５（ｍ＝３）でＥ３＝φではないのでステップＳ５０６（ｍ＝３）に進む。Ｅ３から状態遷移＜０→０，だ：ダ／０＞を取り出しｅ３とし、ステップＳ５０７（ｍ＝３）でＷ［ｆ３］＝１＋１＋０＝２となる補助仮説ｆ３＝（０，アメダ，２，φ）を生成する。
【００９２】
ステップＳ５０８（ｍ＝３）でｍ＝３かつＭ＝３なのでｍ＜Ｍではないから、ステップＳ５０９（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。ステップＳ５０５（ｍ＝３）に戻り、Ｅ３＝φなので、ステップＳ５１０（ｍ＝３）に進む。ステップＳ５１０（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１（ｍ＝３）に進む。ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは２なのでＷ[ｆ２]＝２とする。
【００９３】
ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５０８に戻る。ステップＳ５０８におけるｆ２の補正手順の後、ステップＳ５０９に進む。ステップＳ５０９では、ｆ２をＬ２に挿入し、ステップＳ５０５に戻る。ステップＳ５０５でＥ２＝φであるため、ステップＳ５１０に進む。ステップＳ５１０で、Ｌ[ｆ１]＝φなので、ステップＳ５１１に進む。ステップＳ５１１で、Ｌ２の要素をすべてＬ[ｆ１]に移す。ステップＳ５１２で、Ｌ[ｆ１]の補助仮説の累積重みは２なのでＷ[ｆ１]＝２とする。ステップＳ５１４で補助仮説ｆ１の補正を終了し、ステップＳ４０９に戻る。ステップＳ４０９における仮説ｆ１の補正手順の後、ステップＳ４１０に進む。ステップＳ４１０では、仮説ｆ１を仮説リストＨ’に挿入し、ステップＳ４０６に戻る。ステップＳ４０６で状態遷移リストＥ１＝φなので、ステップＳ４１１に進む。ステップＳ４１１で仮説リストＨ＝φなので、ステップＳ４１２に進み、Ｈ’の要素｛（０，あめだ，２，｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）｝を仮説リストＨに移す。ステップＳ４１３に進み、次の入力記号が存在するので、ステップＳ４０４に戻る。
【００９４】
〔“ｍ”の処理〕
ステップＳ４０４で記号“ｄ”を読み込み、ステップＳ４０５において仮説リストＨから仮説ｈ＝（０，あめだ，２，｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）を取り出す。この仮説の仮説生成規則Ｔ１の現状態０から入力記号が“ｍ”の状態遷移＜０→１，ｍ：ε／０＞を含むリストＥ１を作る。
【００９５】
ステップＳ４０６でＥ１＝φではないのでステップＳ４０７に進み、状態遷移リストＥ１から状態遷移＜０→１，ｍ：ε／０＞を取り出しｅ１とし、ステップＳ４０８で新たな仮説ｆ１＝（１，あめだ，２，｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）を生成する。ステップＳ４０９で仮説ｆ１を補正するステップＳ５０１に進む。このときｍ＝２に設定する。
【００９６】
ステップＳ５０２（ｍ＝２）で空の補助仮説リストＬ２を生成する。ステップＳ５２１（ｍ＝２）で、入出力記号列配置記憶部２１５を参照してｍ＝２への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεなのでステップＳ５２２（ｍ＝２）に進む。ステップＳ５２２（ｍ＝２）で補助仮説リストＬ[ｆ１]＝｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）｝から補助仮説ｆ２＝（４，雨玉，２，｛（０，アメダ，２，φ）｝）を取り出す。ステップＳ５２３（ｍ＝２）で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。
【００９７】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεなのでステップＳ５２２（ｍ＝３）に進む。ステップＳ５２２（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，アメダ，２，φ）｝から補助仮説ｆ３＝（０，アメダ，２，φ）を取り出す。ステップＳ５２３（ｍ＝３）で、ｍ＝３でＭ＝３なのでｍ＜Ｍでないから、ステップＳ５２４（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。
【００９８】
ステップＳ５２５（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１に進む。
【００９９】
ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素｛（０，アメダ，２，φ）｝をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは１なのでＷ[ｆ２]＝１とする。ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５２３（ｍ＝２）に戻る。ステップＳ５２３（ｍ＝２）におけるｆ２の補正手順の後、ステップＳ５２４（ｍ＝２）に進む。ステップＳ５２４（ｍ＝２）でｆ２をＬ２に挿入する。
【０１００】
ステップＳ５２５（ｍ＝２）で、Ｌ[ｆ１]＝φなので、ステップＳ５１１（ｍ＝２）に進む。ステップＳ５１１（ｍ＝２）で、補助仮説リストＬ２の要素をすべてＬ[ｆ１]に移す。ステップＳ５１２（ｍ＝２）で、Ｌ[ｆ１]＝｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）｝の補助仮説の累積重みは２なのでＷ[ｆ１]＝２とする。ステップＳ５１４（ｍ＝２）で補助仮説ｆ１の補正を終了し、ステップＳ４０９に戻る。ステップＳ４０９における仮説ｆ１の補正手順の後、ステップＳ４１０に進む。ステップＳ４１０では仮説ｆ１を仮説リストＨ’に挿入し、ステップＳ４０６に進む。
【０１０１】
ステップＳ４０６では状態遷移リストＥ１＝φなのでステップＳ４１１に進み、仮説リストＨ＝φなのでステップＳ４１２に進む。ステップＳ４１２では仮説リストＨ’の要素｛（１，あめだ，２，｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）｝をすべて仮説リストＨに移す。ステップＳ４１３に進み、次の入力記号が存在するので、ステップＳ４０４に戻る。
【０１０２】
〔“ａ”の処理〕
ステップＳ４０４で記号“a”に読み込み、ステップＳ４０５において仮説リストＨから仮説ｈ＝（１，あめだ，２，｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）を取り出す。この仮説の仮説生成規則Ｔ１の現状態０から入力記号が“ｅ”の状態遷移＜１→０，a：ま／０＞を含む状態遷移リストＥ１を作る。
【０１０３】
ステップＳ４０６でＥ１＝φではないのでステップＳ４０７に進み、Ｅ１から状態遷移＜１→０，a：ま／０＞を取り出しｅ１とし、ステップＳ４０８で新たな仮説ｆ１＝（０，あめだま，２，｛（４，雨玉，２，｛（０，アメダ，２，φ）｝）を生成する。ステップＳ４０９で仮説ｆ１を補正するステップＳ５０１に進む。このときｍ＝２に設定する。
【０１０４】
ステップＳ５０２で空の補助仮説リストＬ２を生成する。ステップＳ５２１で、入出力記号列配置記憶部２１５を参照してｍ＝２への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がεでないのでステップＳ５０３に進むステップＳ５０３でＡＷ[ｆ１]＝０となる。
【０１０５】
ステップＳ５０４で補助仮説リストＬ[ｆ１]＝｛（４，雨玉，２，｛（０，アメダ，２，φ）｝から補助仮説ｇ２＝（４，雨玉，２，｛（０，アメダ，２，φ）を取り出し、仮説生成規則Ｔ２の状態１から入力記号ｏ[ｅ１]=“ま”で遷移可能な状態遷移＜４→５，ま：ε／１＞を含む状態遷移リストＥ２を作る。
【０１０６】
ステップＳ５０５で状態遷移Ｅ２＝φではないのでステップＳ５０６に進む。状態遷移リストＥ２から状態遷移＜４→５，ま：ε／１＞を取り出しｅ２とし、ステップＳ５０７でＷ［ｆ２］＝２＋０＋１＝3である補助仮説ｆ２＝（５，雨玉，３，｛（０，アメダ，２，φ）｝）を生成する。ステップＳ５０８で、ｍ＝２でＭ＝３なのでｍ＜Ｍであることから、補助仮説ｆ２を補正するステップＳ５０１（ｍ＝３）に進む。このときｍを１増やして、ｍ＝３に設定する。
【０１０７】
ステップＳ５０２（ｍ＝３）で空の補助仮説リストＬ３を生成する。ステップＳ５２１（ｍ＝３）で、入出力記号列配置記憶部２１５を参照してｍ＝３への入力とする段番号ｎ＝１の出力記号ｏ[ｅ１]がφでないのでステップＳ５０３に進むステップＳ５０３（ｍ＝３）でＡＷ[ｆ２]＝３−２＝１となる。ステップＳ５０４（ｍ＝３）で補助仮説リストＬ[ｆ２]＝｛（０，アメダ，２，φ）｝から補助仮説ｇ３＝（０，アメダ，２，φ）を取り出し、仮説生成規則Ｔ３の状態０から入力記号ｏ[ｅ１]=“ま”の遷移可能な状態遷移＜０→０，ま：マ／０＞を含むリストＥ３を作る。
【０１０８】
ステップＳ５０５（ｍ＝３）でＥ３＝φではないのでステップＳ５０６（ｍ＝３）に進む。Ｅ３から状態遷移＜０→０，ま：マ／０＞を取り出しｅ３とし、ステップＳ５０７（ｍ＝３）でＷ［ｆ３］＝２＋１＋０＝３となる補助仮説ｆ３＝（０，アメダマ，３，φ）を生成する。ステップＳ５０８（ｍ＝３）でｍ＝３かつＭ＝３なのでｍ＜Ｍではないから、ステップＳ５０９（ｍ＝３）に進み、補助仮説ｆ３をリストＬ３に挿入する。
ステップＳ５０５（ｍ＝３）に戻り、Ｅ３＝φなので、ステップＳ５１０（ｍ＝３）に進む。
【０１０９】
ステップＳ５１０（ｍ＝３）で、補助仮説リストＬ[ｆ２]＝φなので、ステップＳ５１１（ｍ＝３）に進む。ステップＳ５１１（ｍ＝３）で、補助仮説リストＬ３の要素をすべて補助仮説リストＬ[ｆ２]に移す。ステップＳ５１２（ｍ＝３）で、Ｌ[ｆ２]の補助仮説の累積重みは３なのでＷ[ｆ２]＝３とする。ステップＳ５１３（ｍ＝３）でｍを１減らしてｍ＝２とし、ステップＳ５１４で補助仮説ｆ２の補正を終了し、ステップＳ５０８に戻る。
【０１１０】
ステップＳ５０８におけるｆ２の補正手順の後、ステップＳ５０９に進む。ステップＳ５０９では、ｆ２をＬ２に挿入し、ステップＳ５０５に戻る。ステップＳ５０５でＥ２＝φであるため、ステップＳ５１０に進む。ステップＳ５１０で、Ｌ[ｆ１]＝φなので、ステップＳ５１１に進む。ステップＳ５１１で、Ｌ２の要素をすべてＬ[ｆ１]に移す。ステップＳ５１２で、Ｌ[ｆ１]の補助仮説の累積重みは３なのでＷ[ｆ１]＝３とする。ステップＳ５１４で補助仮説ｆ１の補正を終了し、ステップＳ４０９に戻る。
【０１１１】
ステップＳ４０９における仮説ｆ１の補正手順の後、ステップＳ４１０に進む。ステップＳ４１０では、仮説ｆ１を仮説リストＨ’に挿入し、ステップＳ４０６に戻る。ステップＳ４０６で状態遷移リストＥ１＝φなので、ステップＳ４１１に進む。ステップＳ４１１で仮説リストＨ＝φなので、ステップＳ４１２に進み、Ｈ’の要素｛（０，あめだま，３，｛（５，雨玉，３，｛（０，アメダマ，３，φ）｝）｝を仮説リストＨに移す。ステップＳ４１３に進み、次の入力記号が存在しないので、ステップＳ４１４に進む。ステップＳ４１４のＦｍは、ｍ段目の仮説生成規則の終了状態を表す集合である。
【０１１２】
ステップＳ４１４で、Ｈ内の仮説ｈ１＝（０，あめだま，３，｛（５，雨玉，３，｛（０，アメダマ，３，φ）｝）｝）が終了状態に到達した唯一の仮説であり、その補助仮説ｈ２＝（５，雨玉，３，｛（０，アメダマ，３，φ）｝）、およびその補助仮説ｈ３＝（０，アメダマ，３，φ）とすると、累積重みＷ[ｈ２]＝３＋(３−３)＋０＝３，Ｗ[ｈ３]＝３＋(３−３)＋０＝３となる。ステップＳ４２１で、入出力記号列配置記憶部２１５を参照して補助仮説ｈ２の出力記号列“雨玉”と補助仮説ｈ３の出力記号列“アメダマ”を変換結果として出力し、ステップＳ４１５で記号列変換処理を終了する。
【０１１３】
このように、仮説のスコアを補正する際に、補助仮説の入力記号を、直前だけでなくそれ以前の仮説生成部の出力記号を入力とすることで、元々、合成あるいは縦続接続不可能な仮説生成規則を従属可能にすることができ、記号列変換装置の汎用性を高めることが可能になる。また、入出力記号列配置記憶部１５に記憶された情報に基づいて複数の補助仮説を外部に出力するか否かを選択できるので、複数の変換結果を同時に得ることが出来る効果も奏する。
【実施例２】
【０１１４】
上記したこの発明の記号列変換装置を、クラス言語モデルを用いた音声認識に適用した音声認識装置３００について説明する。音声認識装置３００は、クラス言語モデルを用いた音声認識装置の後段に、言い換え処理を追加した場合の実施例である。
【０１１５】
クラス言語モデルとは、単語単位の言語モデルが単語の連接のし易さ（例えば確率値）を与えるのに対し、類似する単語をクラスと呼ばれるグループに割り当て、クラスの連接のし易さを与えるものである。言語モデルを学習する際のテキストコーパスが十分に与えられない場合や、テキストコーパスにない単語を追加する場合に用いられる。言い換え処理とは、音声認識を行いながら、その発話内容を別の文章スタイルに変換することである。例えば、話し言葉の文を、書き言葉のスタイルに書き換える処理である。
【０１１６】
図１２に、音声認識装置３００の機能構成例を示す。音声認識装置３００は、上記した記号列変換装置１００を変形した記号列変換装置１００′と音声特徴記号列抽出部３１とを組み合わせて音声認識装置を構成したものである。記号列変換装置１００′は、記号列変換装置１００に対して仮説生成部１１の段数ｍをｍ＝５の５段構成にすると共に、入出力記号列配置記憶部１５′が記憶する情報が、その段数に対応した内容に変更されている部分のみが異なる。よって、図１２では仮説生成部１１１′〜１１５′とそれに付随する仮説生成規則格納部１０１′〜１０６′のみ表記して他の構成部である仮説補正部１２′と仮説絞込み部１３′と入出力記号列配置記憶部１５′の表記は省略している。
【０１１７】
音声特徴記号列抽出部３１は、音声信号を入力として音声の短時間音響パターンの時系列から音響特徴記号列を抽出する。１段目の仮説生成部１１１′は、音響モデル用仮説生成規則格納部１０１′に格納された音声固定単位（例えば要素）の標準的特徴の音声信号を短時間（例えば１０ミリ秒）ごとに分析して得られる音響パターンと、単語発話辞書用仮説生成規則格納部１０２′に格納された種々の単語の発音を音声固定単位の系列に対応させる単語発話辞書とを読み込み、音響特徴記号列を単語系の記号列とする仮説ｆ１を生成する。
【０１１８】
図示しない入力記号選択部１４１′は、入出力記号列配置記憶部１５′（図１３）を参照して段番号ｍ＝２の入力記号段番号ｎがｎ＝１であるので、仮説生成部１１１′の出力する単語列を選択して、２段目の仮説生成部１１２′に入力する。仮説生成部１１２′は、クラス変換用仮説生成規則格納部１０３′に格納された単語が属するクラス変換規則に対応させて単語列が属するクラスを補助仮説ｆ２として生成する。仮説生成部１１２′に付随する仮説絞込み部１３１′は、入出力記号列配置記憶部１５′を参照して出力情報はTrueであるので抽出した補助仮説ｆ２を外部に出力する。
【０１１９】
入力記号選択部１４２′は、入出力記号列配置記憶部１５′のｍ＝３の入力記号段番号ｎがｎ＝２であるので、仮説生成部１１２′の出力するクラス列を３段目の仮説生成部１１３′に入力する。仮説生成部１１３′は、クラス言語モデル仮説生成規則格納部１０４′に格納された単語が属するクラスの連接のし易さを与えるクラス言語モデル変換規則に対応させてクラス列に重み（確率）を付与したクラス列を補助仮説ｆ３として生成する。
【０１２０】
入力記号選択部１４３′は、入出力記号列配置記憶部１５′のｍ＝４の入力記号段番号ｎがｎ＝１であるので、仮説生成部１１１′の出力する単語列を４段目の仮説生成部１１４′に入力する。仮説生成部１１４′は、言い換え用仮説生成規則格納部１０４′に格納された単語を言い換え用の単語に変換する規則に対応させて単語列に対応する言い換え単語列を補助仮説ｆ４として生成する。
【０１２１】
入力記号選択部１４４′は、入出力記号列配置記憶部１５′のｍ＝５の入力記号段番号ｎがｎ＝４であるので、仮説生成部１１４′の出力する言い換え単語列を５段目の仮説生成部１１５′に入力する。仮説生成部１１５′は、言い換え先単語言語モデル仮説生成規則格納部１０５′に格納された単語を単語の連接のし易さを与える言い換え先言語モデルに変換する規則に対応させて、言い換え単語に重みを付与した言い換え単語列を補助仮説ｆ５として生成する。仮説生成部１１５′に付随する仮説絞込み部１３５′は、入出力記号列配置記憶部１５′を参照して出力情報はTrueであるので抽出した補助仮説ｆ５を外部に出力する。
【０１２２】
上記したように、言い換え用の仮説生成規則は単語列を入力とするため、従来の方法ではクラス言語モデル用の仮説生成規則の後に縦続接続することができないが、この発明の方法によれば入力記号選択部１１′と入出力記号列配置記憶部１５′の働きによって縦続接続を可能とし、クラス言語モデルの利用においても言い換え処理を可能にする。また、出力記号列として補助仮説ｆ２（言い換え前単語）とｆ５（言い換え後単語）の２つの単語列を同時に出力することができる。
【０１２３】
なお、１段目の仮説生成部１１１′が、２つの仮説生成規則を読み込んで処理する例で説明を行ったが、仮説生成規則の数に対応させた数の仮説生成部を用いて音声認識装置を構成しても良い。
【０１２４】
また、上記において言い換え先単語言語モデル用仮説生成規則を言い換え先クラス言語モデル用仮説生成規則に置換え、直前に言い換え先クラス変換用仮説生成規則を挿入することで、言い換え先の言語モデルについてもクラス言語モデルを利用することが可能である。
【０１２５】
その際、言い換え先クラス変換用仮説生成規則の入力は単語発話辞書用仮説生成規則の出力である単語列であり、言い換え先クラス言語モデル用仮説生成規則の入力は、言い換え先クラス変換用仮説生成規則の出力であるクラス列である。
【０１２６】
クラス言語モデルは、例えば、Peter F. Brown他 “Classbased ngram models of natural language”, Computational Linguistics 18(4), 467-479, 1992に記載がある。
音声認識用の単語発音辞書や言語モデルを重み付き有限状態遷移規則によって記述する方法は、例えば、国際会議ＡＳＲ２０００における、M.Mohri,F.Pereira,M.Riley著“Weighted finite-state transducers in speech recognition”，Proceeding of ASR2000, pp.97-106,2000に開示されている。
【０１２７】
種々の音声固定単位（例えば音素）の標準的な音響パターン系列の集合を表す音響モデルとしては、例えば、それら音響パターンの系列の集合を確率・統計理論に基づいてモデル化する隠れマルコフモデル法（Hidden Markov Model、以後ＨＭＭと呼ぶ）が主流である。このＨＭＭ法の詳細は、例えば、社団法人電子情報通信学会編、中川聖一著「確率モデルによる音声認識」に開示されている。
【０１２８】
音響パターンには、短い時間（例えば１０ミリ秒）ごとに音声信号を分析することにより得られるメルケプストラム（mel-frequency cepstral coefficients、ＭＦＣＣと呼ばれる）、デルタＭＦＣＣ、ＬＰＣケプストラム、対数パワーなどがある。
【０１２９】
音声を認識しながら同時に文のスタイルを変換して出力するために用いる個々の仮説生成部に関する説明は、例えば、参考文献（特開２００４−１１０６７３号公報「文章スタイル変換方法，文章スタイル変換装置，文章スタイル変換プログラム，文章スタイル変換プログラムを格納した記憶媒体」）に開示されている。
【０１３０】
上記装置における処理手段をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各装置における処理手段がコンピュータ上で実現される。
【０１３１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVD（Digital Versatile Disc）、DVD-RAM（Random Access Memory）、CD-ROM（Compact Disc Read Only Memory）、CD-R（Recordable）/RW（ReWritable）等を、光磁気記録媒体として、MO（Magneto Optical disc）等を、半導体メモリとしてEEP-ROM（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１３２】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記録装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１３３】
また、各手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2014081516.tif 000004
【図２】
2014081516.tif 000005
【図３】
2014081516.tif 000006
【図４】
2014081516.tif 000007
【図５】
2014081516.tif 000008
【図６】
2014081516.tif 000009
【図７】
2014081516.tif 000010
【図８】
2014081516.tif 000011
【図９】
2014081516.tif 000012
【図１０】
2014081516.tif 000013
【図１１】
2014081516.tif 000014
【図１２】
2014081516.tif 000015
【図１３】
2014081516.tif 000016
【図１４】
2014081516.tif 000017