JP6301664B2 - 変換装置、パターン認識システム、変換方法およびプログラム - Google Patents

Description

本発明の実施形態は、変換装置、パターン認識システム、変換方法およびプログラムに関する。

有限状態オートマトン（ＦＳＡ）が知られている。ＦＳＡは、有限オートマトン（ＦＡ）および有限状態機械（ＦＳＭ）と呼ばれる場合もある。また、遷移に重みが割り当てられているＦＳＡは、重み付き有限状態オートマトン（ＷＦＳＡ）と呼ばれる。

音声認識、手書き文字認識、ＯＣＲ（Ｏｐｔｉｃａｌ Ｃｈａｒａｃｔｅｒ Ｒｅｃｏｇｎｉｔｉｏｎ）等の系列データをパターン認識するパターン認識装置が知られている。パターン認識装置は、一例として、入力された系列データに対応する最も尤もらしい１つの認識結果または１番目からＮ番目までに良いＮ個の認識結果を出力する。

また、パターン認識装置は、ラティスを認識結果として出力する場合もある。ラティスは、ラベル（入力記号）と、それぞれのラベル（入力記号）の出現位置が付与された重み付き有向グラフである。すなわち、ラティスは、出現位置付きＷＦＳＡであるといえる。出現位置とは、ラベル（入力記号）に対応するパターン認識装置に入力された系列データの位置を表す。

入力記号が単語であるラティスは、一般に、単語ラティスと呼ばれる。入力記号が音素であるラティスは、一般に、音素ラティスと呼ばれる。入力記号がＨＭＭ（Ｈｉｄｄｅｎ Ｍａｒｋｏｖ Ｍｏｄｅｌ）の状態であるラティスは、一般に、ＨＭＭ状態ラティスと呼ばれる。

例えば音声データをパターン認識するパターン認識装置は、モデルとしてＨＭＭが用いられる場合がある。このようなパターン認識装置は、認識処理中に通過したＨＭＭの状態系列をラティス形式で記録して、入力記号がＨＭＭの状態であるＨＭＭ状態ラティスを認識結果として出力する。

ところで、パターン認識装置は、入力記号を単語、ＨＭＭの状態と重みとの組を重みとした単語付きＨＭＭ状態ラティスを、出現位置付きＷＦＳＡで出力する場合がある。このような出現位置付きＷＦＳＡには、同一の出現位置に対して同一の入力記号が割り当てられた複数の経路、並びに空遷移（ε遷移）が多数含まれる。そこで、このような出現位置付きＷＦＳＡを出力するパターン認識装置の後段に、空遷移（ε遷移）の除去処理と決定化処理とを一括して実行する変換装置を設け、不要な経路を取り除く必要がある。

しかし、このような出現位置付きＷＦＳＡは、同一の出現位置であり且つ同一の入力記号が割り当てられている経路であっても、元となるＨＭＭの状態が異なる場合がある。例えば、同一の入力記号が割り当てられている経路であっても、入力記号の発音が異なる場合には、元となるＨＭＭの状態が異なる。しかし、従来の変換装置では、このような複数の経路を１つの経路にまとめてしまっていた。

D. Povey， et al.， "GENERATING EXACT LATTICES IN THE WFST FRAMEWORK"， Proceedings of the International Conference on Acoustics， Speech， and Signal Processing (ICASSP '12)， 2012， pp. 4213-4216 A. Serralheiro， et al.， "Towards a Repository of Digital Talking Books"， EUROSPEECH， 2003， pp. 1605-1608

本発明が解決しようとする課題は、重み付き有限状態オートマトンから不要な経路を除く場合に、異なる経路を通過して生成された同一の入力記号を異なる遷移に割り当てることである。

実施形態に係る変換装置は、第１オートマトンを第２オートマトンに変換する変換装置であって、指定部と、探索部と、遷移登録部とを備える。前記第１オートマトンは、入力記号が割り当てられた経路の境界、前記境界の出現位置、および、併合可能な経路を識別する識別子を付与した重み付き有限状態オートマトンである。前記第２オートマトンは、少なくとも一部の不要な経路を除いた重み付き有限状態オートマトンである。前記指定部は、前記第１オートマトンにおける、初期状態から探索済み経路の先端の状態までの累積重みと、当該探索済み経路の先端の状態から終了状態に至る最良経路の重みとを加えた合成重みが最良となる前記探索済み経路における先端の状態を、開始位置として指定する。前記探索部は、前記識別子毎に、前記第１オートマトンにおける前記開始位置から次の境界までの重みが最良となる経路を探索する。前記遷移登録部は、前記開始位置から次の境界まで探索が達した場合、探索して得られた経路における開始位置と先端の状態とに対応して、前記第２オートマトンに新たな遷移を登録する。

実施形態に係る変換装置の構成図。 実施形態に係る変換装置の処理フローを示す図。 経路を探索する処理を説明するための擬似コードを示す図。 開始位置を指定する処理を説明するための擬似コードを示す図。 第１オートマトンの一例を示す図。 第２オートマトンの一例を示す図。 実施形態に係る変換装置のハードウェア構成を示す図。 変形例に係る擬似コードを示す図。 実施形態に係るパターン認識システムの構成を示す図。 実施形態に係るパターン認識システムの処理フローを示す図。

（前提）
まず、本実施形態の前提となる技術および定義等について説明する。

重み付き有限状態オートマトン（ＷＦＳＡ）は、遷移に入力記号および重みが割り当てられる。ＷＦＳＡは、状態の集合Ｑ、遷移の集合Ｅ、入力記号の集合Σ、重みの集合Ｋ、初期状態の集合Ｉ、終了状態の集合Ｆ、初期重み関数λ、および終了重み関数ρの８つの要素の組（Ｑ，Ｅ，Σ，Ｋ，Ｉ，Ｆ，λ，ρ）で構成される。遷移は、４つの要素の組（前状態，次状態，入力記号，重み）で構成される。

本実施形態では、遷移には、入力記号の集合Σに含まれる記号の他に、εを割り当てることができる。εは、記号が空であることを意味する。εはΣに含まれないものとする。遷移をした結果として得られる入力記号がεである遷移、すなわち、本実施形態においてεが入力記号として割り当てられている遷移を、空遷移またはε遷移と呼ぶ。

入力記号列は、ＷＦＳＡに割り当てられた入力記号を０個以上連結した記号列である。なお、０個の記号を連結した入力記号列とは、まだ記号が１つも連結されておらず、空の記号列を意味する。

本実施形態では、遷移ｅの前状態をｐ（ｅ）と表し、遷移ｅの次状態をｎ（ｅ）と表し、遷移ｅに割り当てられている入力記号をｉ（ｅ）と表し、遷移ｅに割り当てられている重みをｗ（ｅ）と表す。本実施形態では、空集合を｛｝と表す。後述する疑似コードでは、空集合を０に／を重ねた文字で表す。

重みの集合Ｋは、一例として、整数全体の集合、実数全体の集合、複素数全体の集合、行列、ブーリアン（０および１）の集合等である。重みの集合Ｋは、正でない実数の集合または負でない実数の集合等であってもよい。本実施形態では、初期重みおよび終了重みは、０であるものとする。初期重みおよび終了重みが含まれるＷＦＳＡは、初期重みおよび終了重みの無いＷＦＳＡに変換すればよい。具体的には、ＷＦＳＡの初期状態に対して、新たな初期状態と、新たな初期状態から元の初期状態へと向かう１つの遷移とを追加し、そして、追加した遷移に元々の初期重みを割り当てれば、初期重みを０としたＷＦＳＡに変換することができる。終了重みについても同様である。

拡張ＷＦＳＡは、境界フラグ、出現位置、および識別子を付与したＷＦＳＡである。本実施形態では、拡張ＷＦＳＡを第１オートマトンとも呼ぶ。

境界フラグは、入力記号が割り当てられた経路の境界を示す。すなわち、境界フラグは、拡張ＷＦＳＡから不要な経路を除去した場合に、１本の遷移に置き換えられる経路の境界の位置を示す。なお、ある経路の終端の境界は、続く他の経路の始端の境界となる。従って、経路の範囲の始端を示す境界と、続く経路の範囲の終端を示す境界とは、１つの境界フラグにより特定される。

境界フラグは、一例として、拡張ＷＦＳＡを生成するパターン認識装置等により付与される。例えば、パターン認識装置が音声認識装置であり、認識結果として入力記号が単語である拡張ＷＦＳＡを出力する場合、ある音声を認識した単語が対応する拡張ＷＦＳＡ上の経路の始端と終端とを表す情報が、境界フラグとなる。また、パターン認識装置がＯＣＲであり、認識結果として入力記号が文字である拡張ＷＦＳＡを出力する場合、ある画像を認識した文字が対応する拡張ＷＦＳＡ上の経路の始端と終端とを表す情報が、境界フラグとなる。

出現位置は、境界フラグにより表される境界の出現位置を表す。例えば、出現位置は、パターン認識装置が入力した系列データにおける、境界に対応するデータ位置である。また、パターン認識装置が音声認識装置である場合には、出現位置は、境界が発生した時刻またはフレーム番号であってもよい。また、パターン認識装置がＯＣＲである場合には、出現位置は、画像上における境界部分の座標であってもよい。

識別子は、併合可能な経路を識別するための値または記号である。すなわち、ある境界から始まる複数の経路のうち、１本の遷移に置き換えることが可能な経路を識別する値または記号である。従って、拡張ＷＦＳＡから不要な経路を除去する場合において、ある境界から始まる複数の経路のうち識別子が同一となる複数の経路は、不要な経路を除去した後のＷＦＳＡでは１本の遷移に置き換えられる。

例えば、識別子は、その識別子が割り当てられている拡張ＷＦＳＡの状態または遷移の元となっている探索ネットワーク上の状態または遷移を特定する情報である。例えば、拡張ＷＦＳＡを出力したパターン認識装置が参照した探索ネットワーク（例えば、重み付き有限状態トランスデューサ，ＷＦＳＴ）の状態を特定する情報（例えば、ＨＭＭの状態番号または探索ネットワークの状態番号等）であってもよい。

本実施の形態では、境界フラグは、拡張ＷＦＳＡの遷移に割り当てられる。本実施形態では、境界フラグが割り当てられた遷移の前状態が、直前の経路の終端の境界、および、続く経路の始端の境界を表す。

また、本実施の形態では、境界の出現位置は、対応する境界フラグが割り当てられた遷移の前状態となる。また、本実施の形態では、識別子は、境界フラグが割り当てられた遷移の次状態に割り当てられる。従って、ある境界から始まる複数の経路のうち、境界フラグが割り当てられた遷移の次状態に割り当てられた識別子が同一の経路が、１つの遷移に置き換える。なお、識別子は、他の状態にも割り当てられていてもよいが、遷移の次状態以外の状態に割り当てられた識別子は、本実施の形態では参照されない。

本実施形態では、遷移ｅに境界フラグが割り当てられているか否かをｂ（ｅ）と表す。ｂ（ｅ）がｔｒｕｅの場合、遷移ｅに境界フラグが割り当てられている。ｂ（ｅ）がｆａｌｓｅの場合、遷移ｅに境界フラグが割り当てられていない。また、本実施形態では、状態ｑに対応する出現位置をｔ（ｑ）と表し、状態ｑに対応する識別子をｉｄ（ｑ）と表す。

なお、境界フラグを状態に割り当てるように拡張ＷＦＳＡを構成することもできる。例えば、遷移ｅの前状態に境界フラグを割り当てるならばｂ（ｐ（ｅ））と、次状態に境界フラグを割り当てるならばｂ（ｎ（ｅ））とすることで、遷移に境界フラグを割り当てている場合と同様に、境界フラグの有無を判定することができる。同様に、出現位置および識別子を遷移に割り当てるように拡張ＷＦＳＡを構成してもよい。

また、入力記号が割り当てられた経路の境界を境界フラグにより明示的に表すのではなく、別の表現で境界を表してもよい。例えば、全ての状態に出現位置を割り当てるのではなく、境界となる遷移の前状態にのみ出現位置を割り当てることにより、ある遷移ｅの前状態ｐ（ｅ）に出現位置が割り当てられていれば、ｂ（ｅ）＝ｔｒｕｅ、割り当てられていなければｂ（ｅ）＝ｆａｌｓｅとすることができる。また、他にも、境界となる遷移の次状態にのみに識別子を割り当てることにより、ある遷移ｅの次状態ｎ（ｅ）に出現位置が割り当てられていればｂ（ｅ）＝ｔｒｕｅ、割り当てられていなければｂ（ｅ）＝ｆａｌｓｅとすることができる。従って、境界か否かを示す値は、境界フラグにより明示的に表されるだけでなく、別の情報を用いて表すこともできる。

出現位置付きＷＦＳＡは、出現位置が付与されたＷＦＳＡである。本実施形態では、出現位置付きＷＦＳＡを第２オートマトンとも呼ぶ。出現位置付きＷＦＳＡは、拡張ＷＦＳＡから、空遷移を除去し且つ同一の出現位置の同一の識別子の経路を１つの遷移に併合して不要な経路を除くことにより生成される。

出現位置付きＷＦＳＡのそれぞれの状態には、拡張ＷＦＳＡにおける、対応する境界の出現位置が付与される。これにより、出現位置付きＷＦＳＡは、入力記号の発生位置（データ位置、時刻、座標等）を特定させることができる。例えば、音声認識装置から出力された拡張ＷＦＳＡを変換して生成された出現位置付きＷＦＳＡは、単語が発生された時刻を特定することができる。また、ＯＣＲから出力された拡張ＷＦＳＡを変換して生成された出現位置付きＷＦＳＡは、文字の画像上の座標を特定することができる。

（変換装置２０の構成）
図１は、実施形態に係る変換装置２０の構成を示す図である。つぎに、変換装置２０の構成を説明する。

変換装置２０は、拡張ＷＦＳＡである第１オートマトンを入力し、入力した第１オートマトンの少なくとも一部の不要な経路を除いて、出現位置付きＷＦＳＡである第２オートマトンに変換する。そして、変換装置２０は、変換した第２オートマトンを出力する。

変換装置２０は、第１オートマトン記憶部２１と、最良経路重み算出部２２と、最良経路重み記憶部２３と、第２オートマトン記憶部２４と、変換部２５と、第１優先度付きキュー２６と、第２優先度付きキュー２７とを備える。

第１オートマトン記憶部２１は、外部から受け取った第１オートマトンを記憶する。第１オートマトン記憶部２１は、変換部２５から常時アクセスが可能なように第１オートマトンを記憶する。

最良経路重み算出部２２は、第１オートマトンに含まれる状態のそれぞれについて、当該状態から終了状態までに至る最良経路の重みを算出する。最良経路重み算出部２２は、一例として、第１オートマトンの終了状態から逆方向に経路を辿って、それぞれの状態までの重みの最良値を計算する。より具体的には、最良経路重み算出部２２は、Ｄｉｊｋｓｔｒａのアルゴリズム、Ｂｅｌｌｍａｎ−Ｆｏｒｄのアルゴリズム、ｇｅｎｅｒｉｃ ｓｉｎｇｌｅ−ｓｏｕｒｃｅ ｓｈｏｒｔｅｓｔ ｄｉｓｔａｎｃｅアルゴリズム等を用いて、終了状態からその状態までの重みの最良値を計算する。また、第１オートマトンに循環する経路が含まれていなければ、非循環有向グラフ（Ｄｉｒｅｃｔｅｄ Ａｃｙｃｌｉｃ Ｇｒａｐｈ）に使用できる距離計算アルゴリズムを用いて、終了状態からその状態までの重みの最良値を計算してもよい。なお、最良経路重み算出部２２は、第１オートマトンに含まれる状態のそれぞれについての最良経路の重みを、外部から取得してもよい。

最良経路重み記憶部２３は、最良経路重み算出部２２により算出された、第１オートマトンに含まれる状態のそれぞれについて、その状態から終了状態までの最良の経路の重みを記憶する。最良経路重み記憶部２３は、変換部２５から状態が指定された場合に、対応する最良経路重みを返す。最良経路重み記憶部２３は、一例として、連想配列を用いて、それぞれの状態と最良経路重みとを対応付けて記憶する。また、状態が番号で識別できる場合であれば、配列を用いて、それぞれの状態と最良経路重みとを対応付けて記憶してもよい。

第２オートマトン記憶部２４は、第２オートマトンを記憶する。第２オートマトン記憶部２４は、変換部２５から常時アクセスが可能なように第２オートマトンを記憶する。第２オートマトン記憶部２４は、変換部２５による変換処理が完了した後において、完成した第２オートマトンを外部に出力する。

変換部２５は、第１オートマトンを第２オートマトンに変換する。より具体的には、変換部２５は、第１オートマトン記憶部２１および第２オートマトン記憶部２４に対して常時アクセスしながら、第１オートマトンにおける少なくとも一部の不要な経路を除去して第２オートマトンを生成する。

変換部２５は、指定部４１と、探索部４２と、状態登録部４３と、遷移登録部４４と、出現位置登録部４５とを有する。

指定部４１は、第１オートマトンの１つの状態を、探索の開始位置として指定する。探索部４２は、指定部４１により開始位置が指定されると、識別子毎に、第１オートマトンにおける、指定された開始位置から次の境界までの重みが最良となる経路を探索する。つまり、指定部４１は、指定された開始位置から次の境界までの経路のうち、経路の重みと次の境界から終了状態までの最良の経路とを合成した重みが最良となる経路を、識別子毎に探索する。そして、探索部４２は、指定した開始位置から始まる全ての経路について次の境界まで探索が完了すると、識別子毎の探索済み経路の先端の状態を指定部４１に返す。

以後、指定部４１は、探索部４２によって探索が完了する毎に、新たな開始位置を指定する。具体的には、指定部４１は、第１オートマトンにおける、初期状態から探索済み経路の先端の状態までの累積重みと、当該探索済み経路の先端の状態から終了状態に至る最良経路の重みとを加えた合成重みが最良となる探索済み経路における先端の状態を、開始位置として指定する。なお、指定部４１は、変換開始時においては、初期状態のみで構成される経路を探索済み経路であるとして合成重みを算出して、開始位置を指定する。そして、指定部４１は、全ての経路の探索が終了状態まで完了した場合、処理を完了する。

状態登録部４３は、探索部４２による探索開始時において、第１オートマトンのそれぞれの初期状態に対応して、第２オートマトンに新たな初期状態を登録する。これにより、状態登録部４３は、第２オートマトンに初期状態を追加することができる。

また、状態登録部４３は、探索部４２による探索において、開始位置から次の境界まで探索が達した場合、探索して得られた経路の先端の状態に対応して、第２オートマトンに新たな状態を登録する。すなわち、状態登録部４３は、探索部４２による探索において、開始位置から次の境界までの重みが最良となる経路の探索が完了するたびに第２オートマトンに新たな状態を登録する。これにより、状態登録部４３は、第１オートマトンの境界位置に対応させて、第２オートマトンに状態を追加することができる。

また、状態登録部４３は、探索部４２による探索において、開始位置から終了状態まで探索が達した場合、探索して得られた経路の先端の状態に対応して、第２オートマトンに新たな終了状態を登録する。これにより、状態登録部４３は、第２オートマトンに終了状態を追加することができる。

ただし、状態登録部４３は、既に対応する新たな状態または終了状態が第２オートマトンに既に登録されている場合は、新たな状態および新たな終了状態は登録しない。これにより、状態登録部４３は、探索部４２が同一の状態を探索する場合には、第２オートマトンに同一の状態を重複して登録しないようにすることができる。

遷移登録部４４は、探索部４２による探索において、開始位置から次の境界まで探索が達した場合、探索して得られた経路における開始位置と先端の状態とに対応して、第２オートマトンに新たな遷移を登録する。すなわち、遷移登録部４４は、探索部４２による探索において、開始位置から次の境界までの重みが最良となる経路の探索が完了するたびに第２オートマトンに新たな遷移を登録する。また、遷移登録部４４は、探索部４２による探索において、開始位置から終了状態まで探索が達した場合、探索して得られた経路における開始位置と終了状態とに対応して、第２オートマトンに新たな遷移を登録する。これにより、遷移登録部４４は、第２オートマトンに遷移を追加することができる。

より具体的には、遷移登録部４４は、前状態、後状態、重み、および、入力記号列を、遷移として第２オートマトンに登録する。前状態は、開始位置の状態に対応して、第２オートマトンに登録された状態である。また、後状態は、探索して得られた重みが最良の経路の先端の状態（終了状態まで探索が達した場合には終了状態）に対応して、第２オートマトンに登録された状態である。また、重みは、探索して得られた重みが最良の経路における、累積重みである。また、入力記号列は、探索して得られた重みが最良の経路に割り当てられた入力記号列である。

出現位置登録部４５は、第２オートマトンに新たな状態が登録される毎に（すなわち、開始位置から次の境界まで探索が達する毎に）、第１オートマトンに付与されている、対応する出現位置を、第２オートマトンに登録する。これにより、出現位置登録部４５は、第２オートマトンの境界の出現位置を、第２オートマトンに付与することができる。

第１優先度付きキュー２６および第２優先度付きキュー２７のそれぞれは、内部に記憶している要素を優先度が高い順に出力する。

具体的には、第１優先度付きキュー２６は、第１オートマトンにおける、探索部４２による探索済み経路の先端の状態と、初期状態から探索済み経路の先端の状態までの累積重みとを含む情報の組を要素として記憶する。そして、第１優先度付きキュー２６は、合成重みが最良となる探索済み経路の先端の状態を含む要素から順に出力する。なお、合成重みは、初期状態から探索済み経路の先端の状態までの累積重みと、当該探索済み経路の先端の状態から終了状態に至る最良経路の重みとを加えた重みである。

第２優先度付きキュー２７は、第１オートマトンにおける、探索中の経路の先端の状態と、開始位置から探索途中の状態までの経路重みとを含む情報の組を要素として記憶する。そして、第２優先度付きキュー２７は、経路重みと、当該探索途中の経路の先端の状態から終了状態に至る最良の経路の重みとを加えた重みが最良となる、探索中の経路の先端の状態を含む要素から順に出力する。

そして、指定部４１および探索部４２は、一例として、このような第１優先度付きキュー２６および第２優先度付きキュー２７のそれぞれにアクセスして、開始位置の指定および探索を進める。具体的には、開始位置から次の境界まで探索が達した場合、探索部４２は、第１優先度付きキュー２６に要素を書き込む。続いて、指定部４１は、第１優先度付きキュー２６から要素を１つ取り出す。そして、指定部４１は、取り出した要素に含まれる探索済み経路の先端の状態を、次の開始位置として指定する。これにより、指定部４１は、合成重みが最良となる探索済み経路における先端の状態を、開始位置として指定することができる。

また、探索部４２は、第２優先度付きキュー２７から要素を１つ取り出す。そして、探索部４２は、取り出した要素に含まれる探索途中の状態から出る全ての遷移のそれぞれについて、次の状態を探索途中の状態とする新たな要素を生成し、生成した新たな要素を第２優先度付きキュー２７に書き込むことにより探索を進める。これにより、探索部４２は、開始位置から次の境界まで経路の探索を進める場合において、最良の経路から順に探索を進めることができる。

（処理フロー）
図２は、実施形態に係る変換装置２０の処理フローを示す図である。つぎに、変換装置２０の処理手順の概略を説明する。

まず、ステップＳ１１において、変換装置２０は、第１オートマトンを取得する。続いて、ステップＳ１２において、変換装置２０は、第１オートマトンのそれぞれの状態について、最良経路重みを算出する。変換装置２０は、最良経路重みを外部から取得する場合には、算出処理をしなくてもよい。

続いて、ステップＳ１３において、変換装置２０は、第１オートマトンの初期状態のそれぞれに対応させて、第２オートマトンに初期状態を登録する。続いて、ステップＳ１４において、変換装置２０は、第２オートマトンに登録した初期状態に対して、第１オートマトンの対応する初期状態に付与されている出現位置を登録する。

続いて、変換装置２０は、ステップＳ１５とステップＳ２０との間のループ処理を実行する。ステップＳ１５において、変換装置２０は、合成重みが最良となる探索済み経路における先端の状態を開始位置として指定する。なお、変換開始時においては、変換装置２０は、初期状態のみで構成される経路を探索済み経路として合成重みを算出して、開始位置を指定する。

開始位置を指定すると、続いて、変換装置２０は、ステップＳ１６とステップＳ１９との間のループ処理を実行する。まず、ステップＳ１６において、変換装置２０は、識別子毎に、開始位置から次の境界までの重みが最良となる経路を探索する。続いて、ステップＳ１７において、変換装置２０は、それぞれの識別子について、第２オートマトンに新たな遷移および新たな状態を登録する。続いて、ステップＳ１８において、変換装置２０は、それぞれの識別子について、第２オートマトンに登録した状態に対して、第１オートマトンに付与されている対応する出現位置を登録する。

ステップＳ１９において、変換装置２０は、全ての識別子について開始位置から始まる全ての経路を次の境界まで探索完了した場合には、内側のループを抜けて処理を外側のループに戻す。

続いて、ステップＳ２０において、変換装置２０は、第１オートマトンの開始状態から終了状態まで全ての経路について、探索完了した場合には、外側のループも抜けて、処理をステップＳ２１に進める。そして、ステップＳ２１において、変換装置２０は、生成した第２オートマトンを出力して処理を終了する。

（擬似コード）
図３は、指定された開始位置から次の境界までの最良の経路を探索する処理を説明するための擬似コードを示す図である。図４は、開始位置を指定する処理を説明するための擬似コードを示す図である。

第１オートマトン（拡張ＷＦＳＡ）をＡ＝（Ｑ，Ｅ，Σ，Ｋ，Ｉ，Ｆ，λ，ρ）と表す。また、変換後の第２オートマトン（出現位置付きＷＦＳＡ）をＡ’＝（Ｑ’，Ｅ’，Σ^＊，Ｋ，Ｉ’，Ｆ’，λ’，ρ’）と表す。

なお、Σ^＊の要素は、Σの要素から構成される列である。例えば、｛ａ，ｂ｝∈Σであれば、｛ε，ａ，ｂ，ａａ，ａｂ，ｂａ，ｂｂ，ａａａ，・・・｝∈Σ^＊である。また、本実施の形態では、第１オートマトンおよび第２オートマトンの初期重みおよび終了重みは０である。また、本実施の形態では、重みが小さい経路ほど良い経路であるとする。

擬似コードでは、状態ｑから終了状態の集合Ｆに含まれる状態までの最良の経路の重みを、ｗ（ｑ）で得ることができる。本実施形態においては、ｗ（ｑ）は、図１に示す最良経路重み記憶部２３に予め記憶されている。

また、擬似コードにおいて、Ｂは、識別子の集合を表す。Ｐは、探索済みの状態の集合を表す。Ｍは、３つの値の組（Ｑに含まれる状態、Ｑ’に含まれる状態、境界フラグが割り当てられている遷移の重み）の集合である。変換装置２０は、探索が境界を通過する毎に必要に応じて３つの値の組を集合Ｍに追加する。

また、擬似コードにおいて、Ｓは、７つの値の組（状態，前の状態，重み，前の重み，入力記号列，前の入力記号，境界フラグ）を要素として記憶する優先度付きキューである。本実施形態においては、本実施形態においては、Ｓは、図１で示した第２優先度付きキュー２７により実現される。

Ｓは、１つ目の値である状態をｑ、３つ目の値である重みをｗ_ｑとする場合、ｗ_ｑ＋ｗ（ｑ）が優先度となる。ｐｏｐ（Ｓ）は、Ｓから最も優先度の高い要素を取り出す操作を表し、ｐｕｓｈ（Ｓ，７つの値の組）は、Ｓに７つの値の組を要素として追加する操作を表す。本実施の形態では、重みが小さいほど良いので、ｐｏｐ（Ｓ）の操作により、優先度（ｗ_ｑ＋ｗ（ｑ））が最も小さい要素が取り出される。もし、重みが大きいほど良い経路であるとする場合には、ｐｏｐ（Ｓ）の操作により、優先度（ｗ_ｑ＋ｗ（ｑ））が最も大きい要素が取り出される。

また、擬似コードにおいて、Ｓ_ｓｙｍは、５つの値の組（状態，前の状態，累積重み，重み，入力記号列）を要素として記憶する優先度付きキューである。Ｓ_ｓｙｍは、図１で示した第１優先度付きキュー２６により実現される。

Ｓ_ｓｙｍは、１つ目の値である状態をｑ、３つ目の値である累積重みをｗ_ｑとする場合、ｗ_ｑ＋ｗ（ｑ）が優先度となる。ｐｏｐ（Ｓ_ｓｙｍ）は、Ｓ_ｓｙｍから最も優先度の高い要素を取り出す操作を表し、ｐｕｓｈ（Ｓ_ｓｙｍ，５つの値の組）はＳ_ｓｙｍに５つの値の組を要素として追加する操作を表す。本実施の形態では、重みが小さいほど良いので、ｐｏｐ（Ｓ_ｓｙｍ）の操作により、優先度（ｗ_ｑ＋ｗ（ｑ））が最も小さい要素が取り出される。もし、重みが大きいほど良い経路であるとする場合には、ｐｏｐ（Ｓ_ｓｙｍ）の操作により、優先度（ｗ_ｑ＋ｗ（ｑ））が最も大きい要素が取り出される。

変換装置２０は、後述する図４に示される擬似コードから、図３に示される擬似コードを呼び出す。この場合において、優先度付きキューＳ_ｓｙｍ，集合Ｍ，ｑ_ｉ，ｑ_ｐｉ，ｗ_ｉ，ｘ_ｉが引き渡される。ここで、ｑ_ｉは、指定された開始位置となる状態である。ｑ_ｐｉは、開始位置となる状態の前状態である。ただし、ｑ_ｉが初期状態の場合、前の状態はないため、ｑ_ｐｉにはｑ_ｉを割り当てる。ｗ_ｉは、ｑ_ｐｉからｑ_ｉまでの最良の経路の累積重みである。ｘ_ｉは、ｑ_ｐｉからｑ_ｉまでの最良の経路上の入力記号列である。

まず、図３に示す擬似コードを参照して、指定された開始位置から次の境界までの最良の経路を探索する処理を説明する。

１行目では、変換装置２０は、集合Ｂと集合Ｐを空集合で初期化する。

２行目では、変換装置２０は、状態ｑ_ｉに対応する第２オートマトンＡ’の状態を集合Ｍから取り出して、ｑ’_ｉとする。

３行目では、変換装置２０は、優先度付きキューＳを初期化する。初期化に使う７つの値の組の１番目の値はｑ_ｉ、２番目の値はｑ_ｐｉ、３番目の値はｗ_ｉ、４番目の値は０、５番目の値はｘ_ｉ、６番目の値はε、７番目の値はｆａｌｓｅである。

４行目では、変換装置２０は、優先度付きキューＳが空集合か否かを判定する。変換装置２０は、優先度付きキューＳが空集合でない場合、５行目から３４行目までを繰り返して処理し、優先度付きキューＳが空集合である場合、処理を３５行目に進める。

５行目では、変換装置２０は、優先度付きキューＳから要素を１つ取り出し、１番目の値をｑ、２番目の値をｑ_ｐ、３番目の値をｗ、４番目の値をｗ_ｐ、５番目の値をｘ、６番目の値をｘ_ｐ、７番目の値をｂとする。

６行目では、変換装置２０は、ｑが集合Ｐに含まれているか否かを判断する。変換装置２０は、ｑが集合Ｐに含まれていない場合、７行目から３４行目までを処理し、ｑが集合Ｐに含まれている場合、処理を４行目に戻す。

７行目では、変換装置２０は、ｑを集合Ｐに追加する。６行目および７行目の処理により、変換装置２０は、本擬似コードが呼び出されてから処理を終えるまでの間において、同じ状態に対して、７行目から３４行目までを重複して処理することを防ぐことができる。これにより、変換装置２０は、ｑが既に探索が完了した状態である場合、ｑからの探索を中止して計算量を削減することができる。

８行目では、変換装置２０は、ｑが終了状態の集合Ｆに含まれるか否か、つまり、ｑが終了状態であるか否かを判定する。すなわち、ここでは、変換装置２０は、探索が終了状態まで達したか否かを判定している。変換装置２０は、ｑが終了状態の集合Ｆに含まれる場合、９行目から１５行目を処理する。変換装置２０は、ｑが終了状態の集合Ｆに含まれない場合、処理を１６行目に進める。

１６行目では、変換装置２０は、ｂがｔｒｕｅか否かを判定する。ｂがｔｒｕｅである場合、探索が境界を通過したことを意味する。従って、ここでは、変換装置２０は、探索が境界まで達したか否かを判定している。変換装置２０は、ｂがｔｒｕｅの場合、１７行目から２７行目を処理する。変換装置２０は、ｂがｔｒｕｅではない場合、２９行目から３４行目を処理する。

まず、２９行目から３４行目の処理を説明する。すなわち、探索が終了状態まで達しておらず、且つ、探索が境界まで達していない場合における変換装置２０の処理を説明する。

２９行目は、Ｅに含まれる遷移ｅのうち、前状態ｐ（ｅ）がｑであるそれぞれの遷移、つまり、ｑから出ていくそれぞれの遷移について３０行目から３４行目を処理することを表す。従って、変換装置２０は、ｑから出ていくそれぞれの遷移について３０行目から３４行目を処理する。

３０行目では、変換装置２０は、ｅの次状態ｎ（ｅ）が集合Ｐに含まれているか否かを判定する。ｅの次状態ｎ（ｅ）が集合Ｐに含まれていない場合、変換装置２０は、３１行目から３４行目を処理する。ｅの次状態ｎ（ｅ）が集合Ｐに含まれている場合、次の遷移ｅについて、３０行目から３４行目の処理をする。なお、変換装置２０は、６行目で同一の目的の判定処理を実行するので、３０行目の判定処理を実行してなくてもよい。しかし、変換装置２０は、３０行目の判定処理を実行することにより、無駄な要素を優先度付きキューＳに追加しなくてよく、計算量を少なくできる。

３１行目では、変換装置２０は、遷移ｅの境界フラグｂ（ｅ）がｔｕｒｅか否かを判定する。変換装置２０は、遷移ｅの境界フラグｂ（ｅ）がｔｕｒｅの場合、３２行目を処理し、遷移ｅの境界フラグｂ（ｅ）がｔｕｒｅでない場合、３４行目を処理する。

３２行目では、変換装置２０は、優先度付きキューＳに、新たな７つの値の組（ｅの次状態ｎ（ｅ），ｑ，ｗ＋ｗ（ｅ），ｗ（ｅ），ｘ，ｉ（ｅ），ｔｒｕｅ）を追加する。

３４行目では、変換装置２０は、優先度付きキューＳに、新たなＳに７つの値の組（ｅの次状態ｎ（ｅ），ｑ，ｗ＋ｗ（ｅ），０，ｘ・ｉ（ｅ），ε，ｆａｌｓｅ）を追加する。なお、ｘ・ｉ（ｅ）は、入力記号列ｘの後ろに、遷移ｅに割り当てられている入力記号を連結する処理を表す。例えば、ｘ＝ａｂ、ｉ（ｅ）＝ｃであれば、ｘ・ｉ（ｅ）＝ａｂｃとなる。

続いて、１７行目から２７行目の処理を説明する。すなわち、探索が終了状態まで達しておらず、且つ、探索が境界まで達している場合における変換装置２０の処理を説明する。

１７行目では、変換装置２０は、ｉｄ（ｑ）が集合Ｂに含まれているか否かを判定する。変換装置２０は、ｉｄ（ｑ）が集合Ｂに含まれていない場合、１８行目から２７行目までを処理し、ｉｄ（ｑ）が集合Ｂに含まれている場合、処理を４行目に戻す。

１８行目では、変換装置２０は、ｉｄ（ｑ）を集合Ｂに追加する。１７行目および１８行目の処理により、変換装置２０は、本擬似コードが呼び出されてから処理を終えるまでの間において、同一の識別子に対して、１８行目から２７行目までを重複して処理することを防ぐことができる。これにより、変換装置２０は、同一の識別子については、優先度の最も高い経路、すなわち、最良の経路に対してのみ、１９行目から２７行目の処理を実行することができる。

１９行目では、変換装置２０は、１番目の値がｑである３つの値の組が集合Ｍに含まれているか否かを判定する。変換装置２０は、１番目の値がｑである３つの値の組が集合Ｍに含まれている場合、２０行目と２１行目を処理し、含まれていない場合、２３行目から２６行目を処理する。

２０行目では、変換装置２０は、１番目の値がｑである３つの値の組の２番目の値と３番目の値を集合Ｍから取り出し、それぞれｑ’_ｎとｗ_ｍとする。

２１行目では、変換装置２０は、第２オートマトンＡ’の遷移の集合であるＥ’に、新たな遷移を追加する。新たな遷移の前状態はｑ’_ｉ、次状態はｑ’_ｎ、入力記号列はｘ、重みはｗ−ｗ_ｍである。２１行目を処理した後、変換装置２０は、２７行目を処理する。

２３行目では、変換装置２０は、第２オートマトンＡ’の状態の集合であるＱ’に含まれない、新たな状態ｑ’_ｎを作成する。

２４行目では、変換装置２０は、第１オートマトンＡのｑ_ｐに割り当てられている出現位置を、新たな状態ｑ’_ｎに割り当てる。

２５行目では、変換装置２０は、第２オートマトンＡ’の状態の集合であるＱ’に、新たな状態ｑ’_ｎを追加する。さらに、集合Ｍに３つの値の組（ｑ，ｑ’_ｎ，ｗ_ｐ）を追加する。

２６行目では、変換装置２０は、第２オートマトンＡ’の遷移の集合であるＥ’に、新たな遷移を追加する。新たな遷移の前状態はｑ’_ｉ、次状態はｑ’_ｎ、入力記号列はｘ、重みはｗ−ｗ_ｐである。２６行目を処理した後、変換装置２０は、２７行目を処理する。

２７行目では、変換装置２０は、優先度付きキューＳ_ｓｙｍに、新たな５つの値の組（ｑ，ｑ_ｐ，ｗ，ｗ_ｐ，ｘ_ｐ）を追加する。

続いて、９行目から１５行目の処理を説明する。すなわち、探索が終了状態まで達している場合における変換装置２０の処理を説明する。

９行目では、変換装置２０は、３つの値の組の１番目の値がｑである要素が、集合Ｍに含まれているかを判定する。変換装置２０は、３つの値の組の１番目の値がｑである要素が集合Ｍに含まれている場合、１０行目を処理し、含まれていない場合、１２行目から１４行目を処理する。

１０行目では、変換装置２０は、１番目の値がｑである３つの値の組の２番目の値を集合Ｍから取り出し、ｑ’_ｎとする。１０行目を処理した後、変換装置２０は、１５行目を処理する。

１２行目では、変換装置２０は、第２オートマトンＡ’の状態の集合であるＱ’に含まれない、新たな状態ｑ’_ｎを作成する。

１３行目では、変換装置２０は、第１オートマトンＡのｑに割り当てられている出現位置を、新たな状態ｑ’_ｎに割り当てる。

１４行目では、変換装置２０は、第２オートマトンＡ’の状態の集合Ｑ’と終了状態の集合Ｆ’に、新たな状態ｑ’_ｎを追加する。また、集合Ｍに、新たな３つの値の組（ｑ，ｑ’_ｎ，０）を追加する。１４行目を処理した後、変換装置２０は、１５行目を処理する。

１５行目では、変換装置２０は、第２オートマトンＡ’の遷移の集合であるＥ’に、新たな遷移を追加する。新たな遷移の前状態はｑ_ｉ’、次状態はｑ’_ｎ、入力記号列はｘ、重みはｗである。

そして、変換装置２０は、４行目の処理の結果、優先度付きキューＳに何ら要素が含まれなくなると、最後に３５行目を処理する。３５行目では、変換装置２０は、処理結果として、Ｓ_ｓｙｍと集合Ｍとを返す。

つぎに、図４に示す擬似コードを参照して、開始位置を指定する処理を説明する。変換装置２０は、第１オートマトンＡを取得した後に、図４の１０１行目からの変換処理を開始する。なお、第２オートマトンＡ’は、変換処理を実行することにより作成されるので、開始時点においては状態および遷移を含まない。より具体的には、Ｑ’、Ｅ’、Ｉ’、Ｆ’は、開始時点では空集合である。

１０１行目では、変換装置２０は、Ｓ_ｓｙｍと集合Ｍを空集合で初期化する。

１０２行目は、初期状態の集合Ｉに含まれるそれぞれの状態について１０３行目から１０６行目を処理することを表す。従って、変換装置２０は、初期状態の集合Ｉに含まれるそれぞれの状態ｑについて、１０３行目から１０６行目を処理する。

１０３行目では、変換装置２０は、第２オートマトンＡ’の状態の集合であるＱ’に含まれない、新たな状態ｑ’_ｎを作成する。

１０４行目では、変換装置２０は、第１オートマトンＡのｑに割り当てられている出現位置を、新たな状態ｑ’_ｎに割り当てる。

１０５行目では、変換装置２０は、第２オートマトンＡ’の状態の集合Ｑ’に、新たな状態ｑ’_ｎを追加する。また、変換装置２０は、第２オートマトンＡ’の初期状態の集合Ｉ’に、新たな状態ｑ’_ｎを追加する。さらに、変換装置２０は、集合Ｍに３つの値の組（ｑ，ｑ’_ｎ，０）を追加する。

１０６行目では、変換装置２０は、優先度付きキューＳ_ｓｙｍに、新たな５つの値の組（ｑ，ｑ，０，０，ε）を追加する。

１０７行目では、変換装置２０は、優先度付きキューＳ_ｓｙｍが空集合か否かを判定する。変換装置２０は、優先度付きキューＳ_ｓｙｍが空集合でない場合、１０８行目から１０９行目までを繰り返して処理し、優先度付きキューＳ_ｓｙｍが空集合である場合、本擬似コードの処理を終了する。

１０８行目では、変換装置２０は、Ｓ_ｓｙｍから５つの値の組を取り出し、１番目の値をｑ_ｉ、２番目の値をｑ_ｐｉ、４番目の値をｗ_ｉ、５番目の値をｘ_ｉとする。

１０９行目では、変換装置２０は、第１引数をＳ_ｓｙｍ、第２引数を集合Ｍ、第３引数をｑ_ｉ、第４引数をｑ_ｐｉ、第５引数をｗ_ｉ、第６引数をｘ_ｉとして、図３に示した擬似コードを呼び出す。そして、図３に示した擬似コードの戻り値として、優先度付きキューＳ_ｓｙｍおよび集合Ｍが返される。従って、変換装置２０は、戻された値により、Ｓ_ｓｙｍおよび集合Ｍを更新する。

（具体的な処理例）
図５は、第１オートマトン（拡張ＷＦＳＡ）の一例を示す。図６は、図５に示す第１オートマトンを、変換装置２０により不要な経路の削減をしたことにより生成される第２オートマトン（出現位置付きオートマトン）の一例を示す。

以下、変換装置２０が、擬似コードに従って、図５の第１オートマトンを図６の第２オートマトンに変換する場合における、具体的な処理例を説明する。

図５および図６の丸は状態を表す。丸の中の数字は状態番号を表す。太線の丸は初期状態を表す。本例では、状態１が初期状態である。二重丸は終了状態を表す。図５の例では、状態１４が終了状態である。図６の例では、状態４が終了状態である。

矢印は遷移を表す。矢印の元が前状態、矢印の指す先が次状態である。矢印付近に記載された文字列の／の左側は入力記号を表し、右側は重みを表す。それぞれの状態の丸に重ねて記載された小さな破線の丸の中の数字は、状態に割り当てられた出現位置を表す。本例では、遷移が１つ進む毎に値が１増えるように出現位置を割り当てているが、遷移が１つ進む毎に値が増加または減少するのであれば他の方法で出現位置を割り当ててもよい。また、出現位置が２次元の画像上の座標である場合、出現位置は２つの値から構成される。また、状態の近くに記載された四角の中の数字は識別子を表す。入力記号の上の＾は境界フラグを表す。例えば、図５の状態３から状態９への遷移をｅ３→９とした場合、ｂ（ｅ３→９）＝ｔｒｕｅとなる。

なお、第１オートマトンと区別すため、本例の説明では、第２オートマトンの状態番号に’を付ける。変換処理を行う前における第２オートマトンは空であるので、Ｑ’＝｛｝、Ｅ’＝｛｝、Ｉ’＝｛｝、Ｆ’＝｛｝となる。

まず、変換処理に先立って、第１オートマトンのそれぞれの状態について、その状態から終了状態までの最良経路の重みを計算しておく。本例では、ｗ（１）＝６、ｗ（２）＝５、ｗ（３）＝４、ｗ（４）＝３、ｗ（５）＝４、ｗ（６）＝６、ｗ（７）＝３、ｗ（８）＝４、ｗ（９）＝３、ｗ（１０）＝２、ｗ（１１）＝２、ｗ（１２）＝２、ｗ（１３）＝１、ｗ（１４）＝０となる。

変換処理が開始されると、まず、図４の１０１行目で、ＭとＳ_ｓｙｍが初期化される。初期状態は状態１であるので、１０２行目でｑ＝１となる。１０３行目で新しい状態を作成し、ｑ’_ｎ＝１’とする。この新しい状態は図６の状態１に対応する。ｔ（ｑ）＝ｔ（１）＝１であるので、１０４行目でｔ（１’）＝１となる。１０５行目で、Ｑ’＝｛１’｝、Ｉ＝｛１’｝、Ｍ＝｛（１，１’，０）｝となる。１０６行目でＳ_ｓｙｍに５つの値の組を追加すると、Ｓ_ｓｙｍ＝｛（１，１，０，０，ε）｝となる。Ｓ_ｓｙｍは空集合ではないので、１０８行目に進む。１０８行目で、ｑ_ｉ＝１、ｑ_ｐｉ＝１、ｗ_ｉ＝０、ｘ_ｉ＝ε、Ｓ_ｓｙｍ＝｛｝となる。１０９行目で、図３の擬似コードを呼び出す。

図３の１行目でＢとＰが空集合で初期化される。２行目でｑ’_ｉ＝１’となる。３行目で、Ｓに７つの値の組が追加され、Ｓ＝｛（１，１，０，０，ε，ε，ｆａｌｓｅ）｝となる。Ｓは空集合ではないので、５行目に進む。Ｓには１つしか要素がないので、優先度にかかわらず５行目で、ｑ＝１、ｑ_ｐ＝１、ｗ＝０、ｗ_ｐ＝０、ｘ＝ε、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなる。Ｓから要素が１つ取り出されたので、Ｓ＝｛｝である。今、ｑ＝１であり、Ｐに１は含まれていない。従って、７行目に進む。７行目で、Ｐに１が追加され、Ｐ＝｛１｝となる。状態１は終了状態ではないので、１６行目に進む。ｂはｆａｌｓｅであるので、１６行目の条件は満たさない。従って、２９行目に進む。状態１から出ていく遷移は１本のみなので、その遷移について３０行目から３４行目が処理される。ｎ（ｅ）＝２であるが、Ｐ＝｛１｝であるので３０行目の条件を満たし、３１行目へ進む。状態１から状態２への遷移の入力記号には＾はないので、ｂ（ｅ）＝ｆａｌｓｅである。従って、３４行目で、Ｓ＝｛（２，１，１，０，ε，ε，ｆａｌｓｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。５行目で、ｑ＝２、ｑ_ｐ＝１、ｗ＝１、ｗ_ｐ＝０、ｘ＝ε、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなる。また、Ｓ＝｛｝となる。Ｐに２は含まれていないので、７行目に進み、そこでＰ＝｛１，２｝となる。状態２は終了状態ではなく、ｂ＝ｆａｌｓｅであるので、２９行目に進む。状態２から出ていく遷移は２本あるので、まず、次状態が状態３である遷移について３０行目から３４行目を処理する。ｎ（ｅ）＝３であるので、３０行目の条件は満たす。ｂ（ｅ）＝ｆａｌｓｅであるので、３１行目の条件は満たさない。従って、３４行目でＳ＝｛（３，２，２，０，Ａ，ε，ｆａｌｓｅ）｝となる。５番目の値がＡであるのは、εは空記号列であるのでε・Ａ＝Ａとなるためである。次に、次状態が状態５である遷移について同様に処理する。すると、３４行目で、Ｓ＝｛（３，２，２，０，Ａ，ε，ｆａｌｓｅ），（５，２，３，０，Ｂ，ε，ｆａｌｓｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。１番目の値が３であるＳの要素の優先度は、２＋ｗ（３）＝２＋４＝６であり、１番目の値が５であるＳの要素の優先度は、３＋ｗ（５）＝３＋４＝７である。値が小さい方が優先度が高いので、５行目で、ｑ＝３、ｑ_ｐ＝２、ｗ＝２、ｗ_ｐ＝０、ｘ＝Ａ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなり、Ｓ＝｛（５，２，３，０，Ｂ，ε，ｆａｌｓｅ）｝となる。Ｐに３は含まれていないので７行目でＰ＝｛１，２，３｝となる。状態３は終了状態ではなく、ｂ＝ｆａｌｓｅであるので２９行目に進む。状態３から出ていく遷移は２本あるので、まず、次状態が状態４である遷移について３０行目から３４行目を処理する。ｎ（ｅ）＝４であるので、３０行目の条件は満たす。ｂ（ｅ）＝ｆａｌｓｅであるので、３１行目の条件は満たさない。

従って、３４行目でＳ＝｛（５，２，３，０，Ｂ，ε，ｆａｌｓｅ），（４，３，３，０，Ａ，ε，ｆａｌｓｅ）｝となる。次に、次状態が状態９である遷移について同様に処理する。ｂ（ｅ）＝ｔｒｕｅであるため、３２行目で、Ｓ＝｛（５，２，３，０，Ｂ，ε，ｆａｌｓｅ），（４，３，３，０，Ａ，ε，ｆａｌｓｅ），（９，３，４，２，Ａ，Ｃ，ｔｒｕｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。１番目の値が５であるＳの要素の優先度は３＋ｗ（５）＝３＋４＝７、１番目の値が４であるＳの要素の優先度は３＋ｗ（４）＝３＋３＝６、１番目の値が９であるＳの要素の優先度は４＋ｗ（９）＝４＋３＝７である。従って、５行目で、ｑ＝４、ｑ_ｐ＝３、ｗ＝３、ｗ_ｐ＝０、ｘ＝Ａ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなり、Ｓ＝｛（５，２，３，０，Ｂ，ε，ｆａｌｓｅ），（９，３，４，２，Ａ，Ｃ，ｔｒｕｅ）｝となる。７行目でＰ＝｛１，２，３，４｝となる。状態４は終了状態ではなく、ｂ＝ｆａｌｓｅであるので、２９行目に進む。状態４から出ていく遷移は１本のみである。３２行目で、Ｓ＝｛（５，２，３，０，Ｂ，ε，ｆａｌｓｅ），（９，３，４，２，Ａ，Ｃ，ｔｒｕｅ），（１０，４，４，１，Ａ，Ｃ，ｔｒｕｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。新たに追加されたＳの要素の優先度は４＋ｗ（１０）＝４＋２＝６であるので、５行目で、ｑ＝１０、ｑ_ｐ＝４、ｗ＝４、ｗ_ｐ＝１、ｘ＝Ａ、ｘ_ｐ＝Ｃ、ｂ＝ｔｒｕｅとなり、Ｓ＝｛（５，２，３，０，Ｂ，ε，ｆａｌｓｅ），（９，３，４，２，Ａ，Ｃ，ｔｒｕｅ）｝となる。７行目で、Ｐ＝｛１，２，３，４，１０｝となる。状態１０は終了状態ではなく、ｂ＝ｔｒｕｅであるので、１７行目に進む。今、Ｂは空集合であるので、１８行目に進む。ｉｄ（１０）＝７であるので、Ｂ＝｛７｝となる。１番目の値が１０である３つの値の組はＭには含まれていないので、２３行目に進む。新しく状態を作成し、ｑ’_ｎ＝２’とする。新しく状態ｑ’_ｎ＝２’は、図６の状態２に対応する。ｔ（ｑ_ｐ）＝ｔ（４）＝４であることから、２４行目でｔ（２’）＝４となる。２５行目で、Ｑ’＝｛１’，２’｝、Ｍ＝｛（１，１’，０），（１０，２’，１）｝となる。２６行目で遷移（１’，２’，Ａ，３）をＥ’に追加する。２７行目でＳ_ｓｙｍ＝｛（１０，４，４，１，Ｃ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。Ｓに含まれる２つの要素の優先度は何れも７である。どちらから処理してもよいが、ここでは、１番目の値が９である要素をｐｏｐ（Ｓ）でＳから取り出すこととする。すると、ｑ＝９、ｑ_ｐ＝３、ｗ＝４、ｗ_ｐ＝２、ｘ＝Ａ、ｘ_ｐ＝Ｃ、ｂ＝ｔｒｕｅとなり、Ｓ＝｛（５，２，３，０，Ｂ，ε，ｆａｌｓｅ）｝となる。７行目でＰ＝｛１，２，３，４，９，１０｝となる。状態９は終了状態ではなく、ｂ＝ｔｒｕｅであるので、１７行目に進む。ｉｄ（９）＝７であり、Ｂ＝｛７｝であるので、１７行目の条件を満たさない。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。Ｓの要素は１つであるので、ｑ＝５、ｑ_ｐ＝２、ｗ＝３、ｗ_ｐ＝０、ｘ＝Ｂ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅ、Ｓ＝｛｝となる。７行目でＰ＝｛１，２，３，４，５，９，１０｝となる。状態５は終了状態ではなく、ｂ＝ｆａｌｓｅであるので、２９行目に進む。状態５から出ていく遷移は２本あるので、まず、次状態が状態６である遷移について３０行目から３４行目を処理する。ｎ（ｅ）＝６であるので、３０行目の条件は満たす。ｂ（ｅ）＝ｆａｌｓｅであるので、３１行目の条件は満たさない。従って、３４行目でＳ＝｛（６，５，４，０，Ｂ，ε，ｆａｌｓｅ）｝となる。次に、次状態が状態７である遷移について同様に処理する。ｂ（ｅ）＝ｔｒｕｅであるため、３２行目で、Ｓ＝｛（６，５，４，０，Ｂ，ε，ｆａｌｓｅ），（７，５，４，１，Ｂ，ε，ｔｒｕｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。１番目の値が６であるＳの要素の優先度は４＋ｗ（６）＝４＋６＝１０、１番目の値が７であるＳの要素の優先度は４＋ｗ（７）＝４＋３＝７である。従って、５行目で、ｑ＝７、ｑ_ｐ＝５、ｗ＝４、ｗ_ｐ＝１、ｘ＝Ｂ、ｘ_ｐ＝ε、ｂ＝ｔｒｕｅとなり、Ｓ＝｛（６，５，４，０，Ｂ，ε，ｆａｌｓｅ）｝となる。７行目でＰ＝｛１，２，３，４，５，７，９，１０｝となる。状態７は終了状態ではなく、ｂ＝ｔｒｕｅであるので、１７行目に進む。ｉｄ（７）＝６、Ｂ＝｛７｝であるので１８行目に進み、Ｂ＝｛６，７｝となる。１番目の値が７である３つの値の組はＭには含まれていないので、２３行目に進む。新しく状態を作成し、ｑ’_ｎ＝３’とする。新しい状態ｑ’_ｎ＝３は、図６の状態３に対応する。ｔ（ｑ_ｐ）＝ｔ（５）＝３であることから、２４行目でｔ（３’）＝３となる。２５行目で、Ｑ’＝｛１’，２’，３’｝、Ｍ＝｛（１，１’，０），（１０，２’，１），（７，３’，１）｝となる。２６行目で遷移（１’，３’，Ｂ，３）をＥ’に追加する。２７行目でＳ_ｓｙｍ＝｛（１０，４，４，１，Ｃ），（７，５，４，１，ε）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。Ｓの要素は１つであるので、ｑ＝６、ｑ_ｐ＝５、ｗ＝４、ｗ_ｐ＝０、ｘ＝Ｂ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなり、Ｓ＝｛｝となる。７行目でＰ＝｛１，２，３，４，５，６，７，９，１０｝となる。状態６は終了状態ではなく、ｂ＝ｆａｌｓｅであるので、２９行目に進む。状態１から出ていく遷移は１本のみなので、その遷移について３０行目から３４行目が処理される。ｎ（ｅ）＝８であるので３０行目の条件を満たし、３１行目へ進む。ｂ（ｅ）＝ｔｒｕｅであるため、３２行目で、Ｓ＝｛（８，６，６，２，Ｂ，ε，ｔｒｕｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。Ｓの要素は１つであるので、ｑ＝８、ｑ_ｐ＝６、ｗ＝６、ｗ_ｐ＝２、ｘ＝Ｂ、ｘ_ｐ＝ε、ｂ＝ｔｒｕｅとなり、Ｓ＝｛｝となる。７行目でＰ＝｛１，２，３，４，５，６，７，８，９，１０｝となる。状態８は終了状態ではなく、ｂ＝ｔｒｕｅであるので、１７行目に進む。ｉｄ（８）＝６であり、Ｂ＝｛６，７｝であるので、１７行目の条件を満たさない。

４行目に戻る。Ｓが空集合なので３５行目に進み、Ｓ_ｓｙｍとＭを戻り値として、図４の擬似コードの１０９行目に処理が戻る。そして、Ｓ_ｓｙｍとＭが更新される。Ｓ_ｓｙｍ＝｛（１０，４，４，１，Ｃ），（７，５，４，１，ε）｝、Ｍ＝｛（１，１’，０），（１０，２’，１），（７，３’，１）｝である。

図４の１０７行目に戻る。Ｓ_ｓｙｍは空集合ではないので、１０８行目に進む。優先度は１番目の値と３番目の値から計算される。１番目の値が１０のＳ_ｓｙｍの要素の優先度は、３番目の値が４であるので、４＋ｗ（１０）＝４＋２＝６となる。同様に、１番目の値が７のＳ_ｓｙｍの要素の優先度は４＋ｗ（７）＝４＋３＝７である。従って、ｑ_ｉ＝１０，ｑ_ｐｉ＝４，ｗ_ｉ＝１，ｘ_ｉ＝Ｃとなる。１０９行目で図３の擬似コードを呼び出す。

図３の１行目でＢとＰが空集合で初期化される。２行目で、ｑ’_ｉ＝２’となる。３行目で、Ｓに７つの値の組が追加され、Ｓ＝｛（１０，４，１，０，Ｃ，ε，ｆａｌｓｅ）｝となる。Ｓは空集合ではないので、５行目に進む。Ｓには１つしか要素がないので、ｑ＝１０、ｑ_ｐ＝４、ｗ＝１、ｗ_ｐ＝０、ｘ＝Ｃ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅ、Ｓ＝｛｝となる。今、ｑ＝１０であるので、Ｐに１０は含まれていない。

従って、７行目に進む。７行目で、Ｐに１０が追加され、Ｐ＝｛１０｝となる。状態１０は終了状態ではなく、ｂはｆａｌｓｅであるので、２９行目に進む。状態２から出ていく遷移は２本あるので、まず、次状態が状態１１である遷移について３０行目から３４行目を処理する。ｎ（ｅ）＝１１であるので、３０行目の条件は満たす。ｂ（ｅ）＝ｆａｌｓｅであるので、３１行目の条件は満たさない。従って、３４行目でＳ＝｛（１１，１０，３，０，Ｃ，ε，ｆａｌｓｅ）｝となる。次に、次状態が状態１３である遷移について同様に処理する。すると、３４行目で、Ｓ＝｛（１１，１０，３，０，Ｃ，ε，ｆａｌｓｅ），（１３，１０，２，０，Ｃ，ε，ｆａｌｓｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。１番目の値が１１であるＳの要素の優先度は３＋ｗ（１１）＝３＋２＝５、１番目の値が１３であるＳの要素の優先度は２＋ｗ（１３）＝２＋１＝３である。従って、５行目で、ｑ＝１３、ｑ_ｐ＝１０、ｗ＝２、ｗ_ｐ＝０、ｘ＝Ｃ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなり、Ｓ＝｛（１１，１０，３，０，Ｃ，ε，ｆａｌｓｅ）｝となる。７行目でＰ＝｛１０，１３｝となる。状態１３は終了状態ではなく、ｂ＝ｆａｌｓｅであるので、２９行目に進む。状態１３から出ていく遷移は１本のみである。３４行目で、Ｓ＝｛（１１，１０，３，０，Ｃ，ε，ｆａｌｓｅ），（１４，１３，３，０，Ｃ，ε，ｆａｌｓｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。１番目の値が１１であるＳの要素の優先度は３＋ｗ（１１）＝３＋２＝５、１番目の値が１４であるＳの要素の優先度は３＋ｗ（１４）＝３＋０＝３である。従って、５行目で、ｑ＝１４、ｑ_ｐ＝１３、ｗ＝３、ｗ_ｐ＝０、ｘ＝Ｃ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなり、Ｓ＝｛（１１，１０，３，０，Ｃ，ε，ｆａｌｓｅ）｝となる。７行目でＰ＝｛１０，１３，１４｝となる。状態１４は終了状態であるので９行目に進む。 Ｍ＝｛（１，１’，０），（１０，２’，１），（７，３’，１）｝であるので９行目は満たさないので１２行目に進む。１２行目で新しい状態を作成し、ｑ’_ｎ＝４’とする。新しい状態ｑ’_ｎ＝４’は図６の状態４に対応する。１３行目では、ｔ（ｑ_ｐ）＝ｔ（１４）＝７であるのでｔ（４’）＝７となる。１４行目でＱ’＝｛１’，２’，３’，４’｝、Ｆ’＝｛４’｝、Ｍ＝｛（１，１’，０），（１０，２’，１），（７，３’，１），（１４，４’，０）｝となる。１５行目で遷移（２’，４’，Ｃ，３）をＥ’に追加する。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。Ｓの要素は１つであるので、ｑ＝１１、ｑ_ｐ＝１０、ｗ＝３、ｗ_ｐ＝０、ｘ＝Ｃ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなり、Ｓ＝｛｝となる。７行目でＰ＝｛１０，１１，１３，１４｝となる。状態１１は終了状態ではなく、ｂ＝ｆａｌｓｅであるので、２９行目に進む。状態１１から出ていく遷移は１本のみである。３４行目で、Ｓ＝｛（１４，１１，５，０，Ｃ，ε，ｆａｌｓｅ）｝となる。

４行目に戻る。Ｓは空集合ではないので、５行目に進む。Ｓの要素は１つであるので、ｑ＝１４、ｑ_ｐ＝１１、ｗ＝５、ｗ_ｐ＝０、ｘ＝Ｃ、ｘ_ｐ＝ε、ｂ＝ｆａｌｓｅとなり、Ｓ＝｛｝となる。Ｐに１４が含まれているため、６行目を満たさない。

４行目に戻る。Ｓが空集合なので３５行目に進み、Ｓ_ｓｙｍとＭを戻り値として、図４の１０９行目に処理が戻る。そして、Ｓ_ｓｙｍとＭが更新される。Ｓ_ｓｙｍ＝｛（７，５，４，１，ε）｝、Ｍ＝｛（１，１’，０），（１０，２’，１），（７，３’，１），（１４，４’，０）｝である。

図４の１０７行目に戻る。Ｓ_ｓｙｍは空集合ではないので、１０８行目に進む。Ｓ_ｓｙｍの要素は１つであるので、ｑ_ｉ＝７，ｑ_ｐｉ＝５，ｗ_ｉ＝１，ｘ_ｉ＝εとなる。１０９行目で、図３の擬似コードを呼び出す。これまでと同様に処理を進めると、遷移（３’，４’，Ｃ，４）がＥ’に追加される。

図４の１０７行目に戻る。Ｓ_ｓｙｍは空集合なので、図４の擬似コードの処理は完了する。以上により、冗長な経路が取り除かれた第２オートマトンが図６のように作成される。

なお、本例では、図５のように、第１オートマトンの全ての状態に出現位置を割り当てたが、利用するのは初期状態と終了状態と境界フラグが割り当てられている遷移の前状態の出現位置のみであるので、これらに対応する状態にのみ出現位置を割り当てるようにしてもよい。また、本例では、識別子を必要な状態にのみ割り当てたが、全ての状態に識別子を割り当ててもよい。

（ハードウェア構成）
図７は、実施形態に係る変換装置２０のハードウェアブロック図である。変換装置２０は、ＣＰＵ（Central Processing Unit）１０１と、操作部１０２と、表示部１０３と、ＲＯＭ（Read Only Memory）１０５と、ＲＡＭ（Random Access Memory）１０６と、記憶部１０７と、通信装置１０８と、バス１０９とを備える。各部は、バス１０９により接続される。

ＣＰＵ１０１は、ＲＡＭ１０６の所定領域を作業領域としてＲＯＭ１０５または記憶部１０７に予め記憶された各種プログラムとの協働により各種処理を実行し、変換装置２０を構成する各部の動作を統括的に制御する。また、ＣＰＵ１０１は、ＲＯＭ１０５または記憶部１０７に予め記憶されたプログラムとの協働により、操作部１０２、表示部１０３および通信装置１０８等を実現させる。

操作部１０２は、マウスやキーボード等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をＣＰＵ１０１に出力する。

表示部１０３は、ＬＣＤ（Liquid Crystal Display）等の表示装置である。表示部１０３は、ＣＰＵ１０１からの表示信号に基づいて、各種情報を表示する。例えば、表示部１０３は、変換装置２０が出力する入力記号列を表示する。なお、通信装置１０８または記憶部１０７等に入力記号列を出力する場合には、変換装置２０は、表示部１０３を備えなくてもよい。

ＲＯＭ１０５は、変換装置２０の制御に用いられるプログラムおよび各種設定情報等を書き換え不可能に記憶する。ＲＡＭ１０６は、ＳＤＲＡＭ（Synchronous Dynamic Random Access Memory）等の揮発性の記憶媒体である。ＲＡＭ１０６は、ＣＰＵ１０１の作業領域として機能する。具体的には、変換装置２０が用いる各種変数およびパラメータ等を一時記憶するバッファ等として機能する。

記憶部１０７は、フラッシュメモリ等の半導体による記憶媒体、磁気的または光学的に記録可能な記憶媒体等の書き換え可能な記録装置である。記憶部１０７は、変換装置２０の制御に用いられるプログラムおよび各種設定情報等を記憶する。また、記憶部１０７は、第１オートマトンおよび第２オートマトンに係る各種の情報等を記憶する。なお、変換装置２０が備える第１オートマトン記憶部２１、最良経路重み記憶部２３、第２オートマトン記憶部２４、第１優先度付きキュー２６および第２優先度付きキュー２７は、ＲＯＭ１０５、ＲＡＭ１０６および記憶部１０７の何れにより実現されてもよい。

通信装置１０８は、外部の機器と通信して、第１オートマトンおよび第２オートマトン等の入力および出力等に用いられる。予め記録された第１オートマトンを用いる場合であり、第２オートマトンを表示部１０３または記憶部１０７に出力する場合には、変換装置２０は、通信装置１０８を備えなくてもよい。

本実施形態の変換装置２０で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。

また、本実施形態の変換装置２０で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施形態の変換装置２０で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、本実施形態の変換装置２０で実行されるプログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。

本実施形態の変換装置２０で実行されるプログラムは、上述した変換装置２０の各部（第１オートマトン記憶部２１、最良経路重み算出部２２、最良経路重み記憶部２３、第２オートマトン記憶部２４、変換部２５（指定部４１、探索部４２、状態登録部４３、遷移登録部４４および出現位置登録部４５）、第１優先度付きキュー２６および第２優先度付きキュー２７）を含むモジュール構成となっており、ＣＰＵ１０１（プロセッサ）が記憶媒体等からプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、変換装置２０（第１オートマトン記憶部２１、最良経路重み算出部２２、最良経路重み記憶部２３、第２オートマトン記憶部２４、変換部２５（指定部４１、探索部４２、状態登録部４３、遷移登録部４４および出現位置登録部４５）、第１優先度付きキュー２６および第２優先度付きキュー２７）が主記憶装置上に生成されるようになっている。なお、変換装置２０の一部または全部がハードウェアにより構成されていてもよい。

（効果）
以上のように、本実施形態に係る変換装置２０は、第１オートマトンから不要な経路を除いた第２オートマトンを生成することができる。この際に、変換装置２０は、第１オートマトンにおける同一の出現位置に対して同一の入力記号が割り当てられている複数の経路を、識別子毎に１つの経路に併合して、第２オートマトンを生成する。これにより、変換装置２０によれば、同一の入力記号であっても、元となる探索ネットワークにおいて異なる経路を通過して生成された入力記号を（例えば、通過したＨＭＭの状態が異なる場合）、経路を併合せずに別個の遷移に割り当てることができる。

さらに、変換装置２０は、第１オートマトンにおける境界毎に探索を行って最良の経路を検出するので、境界毎に遷移を生成することができるとともに、それぞれの境界の出現位置を第２オートマトンに付与することができる。これにより変換装置２０によれば、境界が発生したデータ位置、時刻または順番等を表す出現位置を保持した第２オートマトンを生成することができる。

（変形例）
図８は、変形例に係る変換装置２０において実行される擬似コードを示す。

次に、変形例に係る変換装置２０について説明する。第１オートマトン（拡張ＷＦＳＡ）は、同一の識別子を有する複数の経路上に異なる入力記号が割り当てられていてもよい。この場合、探索部４２は、入力記号と識別子との組毎に、第１オートマトンにおける開始位置から次の境界までの重みが最良となる経路を探索する。これにより、探索部４２は、最良の経路に割り当てられている入力記号とは異なる、最良の経路ではない経路に割り当てられている入力記号も、第２オートマトンに割り当てることができる。

入力記号と識別子との組毎に重みが最良となる経路を探索する場合、図３の擬似コードにおけるＰおよびＢに記憶させる要素を変更すればよい。具体的には、Ｐには、状態および入力記号列の２つの値の組を要素として記憶させる。また、Ｂには、識別子および入力記号列の２つの組を要素として記憶させる。

さらに、図３に示した擬似コードにおける、６行目、７行目、１７行目、１８行目、２７行目、３０行目を変更する。以下、擬似コードの相違点について説明する。本変形例の以下の説明で用いる行番号は、特に記載をしない限り、変更後の疑似コードである図８を指すものとする。

６行目では、変換装置２０は、（ｑ，ｘ・ｘ_ｐ）の組が集合Ｐに含まれているか否かを判断する。変換装置２０は、（ｑ，ｘ・ｘ_ｐ）の組が集合Ｐに含まれていない場合、７行目から３５行目までを処理し、（ｑ，ｘ・ｘ_ｐ）の組が集合Ｐに含まれている場合、処理を４行目に戻す。

７行目では、変換装置２０は、（ｑ，ｘ・ｘ_ｐ）の組を集合Ｐに追加する。

１７行目では、変換装置２０は、（ｉｄ（ｑ），ｘ・ｘ_ｐ）の組が集合Ｂに含まれているか否かを判定する。変換装置２０は、（ｉｄ（ｑ），ｘ・ｘ_ｐ）の組が集合Ｂに含まれていない場合、１８行目から２８行目までを処理し、（ｉｄ（ｑ），ｘ・ｘ_ｐ）の組が集合Ｂに含まれている場合、処理を４行目に戻す。

２０行目では、変換装置２０は、（ｉｄ（ｑ），ｘ・ｘ_ｐ）の組を集合Ｂに追加する。

図３における２７行目は、図８の１８行目と１９行目の２行に分けて処理をする。１８行目では、変換装置２０は、１番目の値がｉｄ（ｑ）である組が集合Ｂに含まれているか否かを判定する。１番目の値がｉｄ（ｑ）である組が集合Ｂに含まれている場合、変換装置２０は、１９行目を処理し、含まれていない場合には何ら処理をしない。１９行目では、元の２７行目と同一の処理をする。すなわち、図８の１９行目では、変換装置２０は、優先度付きキューＳ_ｓｙｍに、新たな５つの値の組（ｑ，ｑ_ｐ，ｗ，ｗ_ｐ，ｘ_ｐ）を追加する。すなわち、変換装置２０は、入力記号列を考慮せずに識別子がＢに含まれていない場合にのみ元の２７行目を処理している。

３１行目では、変換装置２０は、（ｎ（ｅ），ｘ・ｉ（ｅ））の組が集合Ｐに含まれているか否かを判定する。（ｎ（ｅ），ｘ・ｉ（ｅ））の組が集合Ｐに含まれていない場合、変換装置２０は、３２行目から３５行目を処理する。（ｎ（ｅ），ｘ・ｉ（ｅ））の組が集合Ｐに含まれている場合、次の遷移ｅについて、３１行目から３５行目の処理をする。３１行目で行われる処理は、省略してもよい。

このような処理をすることにより、変形例に係る変換装置２０は、最良の経路に割り当てられている入力記号とは異なる、最良の経路ではない経路に割り当てられている入力記号も、第２オートマトンに割り当てることができる。

（パターン認識装置）
図９は、実施形態に係るパターン認識システム２００の構成を示す。以下、実施形態に係るパターン認識システム２００を説明する。

パターン認識システム２００は、入力された系列データのパターンを認識し、認識結果を第２オートマトン（出現位置付きＷＦＳＡ）で出力する。なお、パターン認識システム２００は、第２オートマトンから最良の経路上の１つの記号列を検出してユーザに提示してもよいし、第２オートマトンからＮ番目（Ｎは２以上の整数）までに良い経路上のＮ個の記号列を検出してユーザに提示してもよい。

パターン認識システム２００は、パターン認識装置２１０と、変換装置２０とを備える。パターン認識装置２１０は、系列データを入力してパターン認識をし、第１オートマトン（拡張ＷＦＳＡ）を出力する。変換装置２０は、パターン認識装置２１０が出力した第１オートマトンを第２オートマトンに変換する。変換装置２０は、図１から図８を参照して説明した装置であり、詳細な説明を省略する。

パターン認識システム２００に入力される系列データは、パターンを表す系列データであればどのような系列データであってもよい。入力される系列データは、一例として、音声データ、筆跡を表すデータ、文字を表す画像データまたは手話等のジェスチャを表す動画像データ等である。

パターン認識装置２１０は、特徴抽出部２１１と、デコーダ２１２とを有する。

特徴抽出部２１１は、パターンを表す系列データを入力して、一定時間毎に、系列データの特徴量を取得する。そして、特徴抽出部２１１は、取得した系列データの特徴量をデコーダ２１２に渡す。なお、特徴量は、複数の値から構成される場合もある。この場合、複数の特徴量の組は、特徴ベクトルと呼ばれる。

特徴量は、その系列データの区間毎の特徴を表す情報であり、デコーダ２１２がスコアを算出するために用いられる。音声データを入力する場合、特徴抽出部２１１は、一例として、１０ミリ秒単位（フレーム）毎に、特徴量を取得する。

デコーダ２１２は、特徴抽出部２１１から特徴量が入力される毎に、パターン認識を行い、認識結果を第１オートマトン（拡張ＷＦＳＡ）として出力する。この場合において、デコーダ２１２は、系列データのモデル（ＨＭＭ、Ｇａｕｓｓｉａｎ Ｍｉｘｔｕｒｅ Ｍｏｄｅｌ、Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋ等）と、モデルのつながり方が記録された探索ネットワーク（例えば、重み付き有限状態トランスデューサ，ＷＦＳＴ）とを用いてパターン認識を行う。

例えば、パターン認識システム２００が音声認識装置であれば、系列データは音声データである。モデルは例えば音節、音素、または、音素より細かい単位の音声をモデル化したデータである。モデルとして音素を表すモデルを用いる場合、デコーダ２１２はモデルを用いて、入力された音声に最も対応する音素を得ることができる。重み付き有限状態トランスデューサ（ＷＦＳＴ）を用いるデコーダを用いる場合、探索ネットワークはＷＦＳＴである。ＷＦＳＴは、音素を表すモデルの並び、単語に対応する音素の並び、および、単語の並びの確率モデルを含むことができる。認識の単位が単語である場合、第１オートマトンは、単語ラティスとなる。

また、パターン認識システム２００がＯＣＲ装置であれば、認識したい画像から抽出した行が系列データとなる。英語であれば左から右に読むので、行を縦方向にスライスした画像データが左から右に順にパターン認識システム２００に入力される。パターン認識システム２００が手書き文字認識装置であれば、筆跡が系列データとなる。パターン認識システム２００がＯＣＲ装置または手書き文字認識装置である場合、認識の単位は、一例として、単語または文字である。他は、音声認識装置の場合と同様である。

デコーダ２１２が、境界フラグ、出現位置、および識別子を付与した拡張ＷＦＳＡを出力する方法について説明する。例えば非特許文献１および非特許文献２に記載されているように、従来技術を用いることでデコーダ２１２は、単語、文字、音素またはＨＭＭの状態等の出現位置、つまり、それらが対応する入力された系列データの位置を出力することができる。従って、デコーダ２１２は、出力する拡張ＷＦＳＡに出現位置を埋め込むことができる。また、非特許文献２に記載されているように、デコーダ２１２は、拡張ＷＦＳＡの入力記号間の境界を検出することができる。例えば、入力記号が単語であれば、デコーダ２１２は、単語と単語の境界を検出することができる。従って、デコーダ２１２は、拡張ＷＦＳＡに境界フラグを埋め込むことができる。また、デコーダ２１２は、非特許文献１に記載された技術を用いることにより、ＨＭＭ状態ラティスを出力できる。

デコーダ２１２は、探索ネットワーク（例えばＷＦＳＴ）を探索しながら、最良の経路に対応するＨＭＭ状態ラティスの経路を作成する。従って、デコーダ２１２は、ＨＭＭ状態ラティスのそれぞれの状態がＷＦＳＴのどの状態を通った時に作成されたかを記録することができる。従って、例えば、デコーダ２１２は、ＨＭＭ状態ラティスの状態に対応するＷＦＳＴの状態を、識別子として付与してもよい。つまり、この場合、識別子はＷＦＳＴの状態を示す番号等であり、ＨＭＭ状態ラティスのそれぞれの状態に識別子が割り当てられているということである。なお、デコーダ２１２は、ＨＭＭ状態ラティスのそれぞれの状態がＷＦＳＴのどの遷移を通った時に作成されたかを記録することも、状態を記録するのと同様に行うことができる。従って、デコーダ２１２は、識別子をＷＦＳＴの状態に代えて遷移としてもよい。このようにしてデコーダ２１２は、境界フラグ、出現位置、識別子をＨＭＭ状態ラティスに割り当てることができる。

デコーダ２１２は、モデルに含まれる経路のうち重みが良い経路を見つける処理を行う過程で、デコーダ２１２の処理の開始状態からそれぞれの状態に至る経路の重みを計算する。デコーダ２１２の処理の開始状態を終了状態とし、デコーダ２１２の処理が完了した状態を初期状態とするＷＦＳＡをデコーダ２１２が生成するようにデコーダ２１２を構成すれば、変換装置２０は、それぞれの状態から終了状態までの最良経路の重みを別途計算することなく得ることができる。なぜなら、デコーダ２１２により、処理の開始状態からそれぞれの状態までの最良経路の重みが計算済みであるからである。この場合、変換装置２０に入力されるＷＦＳＡの遷移の向きは、デコーダ２１２が入力される特徴量の順序とは逆向きとなる。つまり、後から入力された特徴量に対応する入力記号ほどＷＦＳＡの初期状態に近い遷移に割り当てられることになる。そこで、入力記号列を出力する直前に入力記号列の並びを反転するように変換装置２０を構成してもよい。

（処理フロー）
図１０は、実施形態に係るパターン認識システム２００の処理順序を示すフローチャートである。

まず、系列データの入力が開始されると、ステップＳ１０１において、パターン認識システム２００は、系列データを取得する。続いて、ステップＳ１０２において、特徴抽出部２１１は、取得した系列データから特徴量を抽出してデコーダ２１２に供給する。

続いて、ステップＳ１０３において、デコーダ２１２は、探索ネットワークおよびモデルを用いて、入力した系列データの特徴量に対応する第１オートマトン（拡張ＷＦＳＡ）を生成する。続いて、ステップＳ１０４において、変換装置２０は、第１オートマトンを第２オートマトン（出現位置付きＷＦＳＡ）に変換する。続いて、ステップＳ１０５において、変換装置２０は、第２オートマトンを出力する。

なお、パターン認識システム２００は、図７に示した構成と同様のハードウェア構成により実現される。また、パターン認識システム２００は、図７に示した構成と同様のハードウェア構成がプログラムを実行することにより、実現されてもよい。パターン認識システム２００で実行されるプログラムは、パターン認識モジュール（特徴抽出モジュールおよびデコーダモジュール）および変換モジュールを含むモジュール構成となっており、ＣＰＵ１０１（プロセッサ）が記憶媒体等からプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、パターン認識システム２００（パターン認識装置２１０および変換装置２０）が主記憶装置上に生成されるようになっている。なお、パターン認識システム２００の一部または全部がハードウェアにより構成されていてもよい。

以上のような実施形態に係るパターン認識システム２００は、系列データのパターン認識をして、不要な経路を含まず、さらに、出現位置が付いたＷＦＳＡを生成することができる。これにより、パターン認識システム２００は、ＷＦＳＡからユーザに提示する記号列を生成する処理の計算量を低減させることができる。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。

２０ 変換装置
２１ 第１オートマトン記憶部
２２ 最良経路重み算出部
２３ 最良経路重み記憶部
２４ 第２オートマトン記憶部
２５ 変換部
２６ 第１優先度付きキュー
２７ 第２優先度付きキュー
４１ 指定部
４２ 探索部
４３ 状態登録部
４４ 遷移登録部
４５ 出現位置登録部
１０１ ＣＰＵ
１０２ 操作部
１０３ 表示部
１０５ ＲＯＭ
１０６ ＲＡＭ
１０７ 記憶部
１０８ 通信装置
１０９ バス
２００ パターン認識システム
２１０ パターン認識装置
２１１ 特徴抽出部
２１２ デコーダ

Claims (16)

1. 入力記号が割り当てられた経路の境界、前記境界の出現位置、および、併合可能な経路を識別する識別子を付与した重み付き有限状態オートマトンである第１オートマトンを、少なくとも一部の不要な経路を除いた重み付き有限状態オートマトンである第２オートマトンに変換する変換装置であって、
   前記第１オートマトンにおける、初期状態から探索済み経路の先端の状態までの累積重みと、当該探索済み経路の先端の状態から終了状態に至る最良経路の重みとを加えた合成重みが最良となる前記探索済み経路における先端の状態を、開始位置として指定する指定部と、
   前記識別子毎に、前記第１オートマトンにおける前記開始位置から次の境界までの重みが最良となる経路を探索する探索部と、
   前記開始位置から次の境界まで探索が達した場合、探索して得られた経路における開始位置と先端の状態とに対応して、前記第２オートマトンに新たな遷移を登録する遷移登録部と、
   を備える変換装置。
2. 前記開始位置から次の境界まで探索が達した場合、探索して得られた経路の先端の状態に対応して、前記第２オートマトンに新たな状態を登録する状態登録部と、
   をさらに備える請求項１に記載の変換装置。
3. 前記指定部は、指定した前記開始位置から始まる全ての経路について次の境界まで探索が完了する毎に、新たな前記開始位置を指定する
   請求項１に記載の変換装置。
4. 前記第２オートマトンに新たな状態が登録される毎に、対応する前記出現位置を、前記第２オートマトンに登録する出現位置登録部をさらに備える
   請求項１に記載の変換装置。
5. 前記状態登録部は、探索開始時において、前記第１オートマトンのそれぞれの初期状態に対応して、前記第２オートマトンに新たな初期状態を登録する
   請求項２に記載の変換装置。
6. 前記状態登録部は、前記開始位置から終了状態まで探索が達した場合、探索して得られた経路の先端の状態に対応して、前記第２オートマトンに新たな終了状態を登録する
   請求項２に記載の変換装置。
7. 前記遷移登録部は、前記開始位置から終了状態まで探索が達した場合、探索して得られた経路における開始位置と終了状態とに対応して、前記第２オートマトンに新たな遷移を登録する
   請求項６に記載の変換装置。
8. 前記状態登録部は、前記開始位置から次の境界まで探索が達した場合、または、前記開始位置から終了状態まで探索が達した場合であって、既に対応する新たな状態または終了状態が前記第２オートマトンに登録されている場合、新たな状態および新たな終了状態を登録しない
   請求項６に記載の変換装置。
9. 前記第１オートマトンにおける、探索済み経路の先端の状態と、初期状態から前記探索済み経路の先端の状態までの累積重みとを含む情報の組を要素として記憶し、前記合成重みが最良となる前記要素から順に出力する第１優先度付きキューを
   さらに備え、
   前記指定部は、
   前記第１優先度付きキューから前記要素を１つ取り出し、
   取り出した要素に含まれる前記探索済み経路の先端の状態を、次の前記開始位置として指定する
   請求項１に記載の変換装置。
10. 前記第１オートマトンにおける、探索中の経路の先端の状態と、開始位置から探索途中の経路の先端の状態までの経路重みとを含む情報の組を要素として記憶し、前記経路重みと、前記探索途中の経路の先端の状態から終了状態に至る最良の経路の重みとを加えた重みが最良となる前記要素から順に出力する第２優先度付きキューを
    さらに備え、
    前記探索部は、
    前記第２優先度付きキューから前記要素を１つ取り出し、
    取り出した要素に含まれる前記探索途中の状態から出る全ての遷移のそれぞれについて、次の状態を探索途中の状態とする新たな要素を生成し、生成した新たな要素を前記第２優先度付きキューに書き込むことにより探索を進める
    請求項９に記載の変換装置。
11. 前記探索部は、前記入力記号と前記識別子との組毎に、前記第１オートマトンにおける前記開始位置から次の境界までの重みが最良となる経路を探索する
    請求項１に記載の変換装置。
12. 系列データを入力し、入力した系列データを探索ネットワークを用いてパターン認識をして前記第１オートマトンを生成するパターン認識装置と、
    前記パターン認識装置により生成された前記第１オートマトンを前記第２オートマトンに変換する請求項１に記載の変換装置と、
    を備えるパターン認識システム。
13. 前記出現位置は、前記パターン認識装置に入力される前記系列データの対応する位置を示す
    請求項１２に記載のパターン認識システム。
14. 前記識別子は、前記探索ネットワークにおける対応する状態を特定する情報である
    請求項１２に記載のパターン認識システム。
15. 入力記号が割り当てられた経路の境界、前記境界の出現位置、および、併合可能な経路を識別する識別子を付与した重み付き有限状態オートマトンである第１オートマトンを、少なくとも一部の不要な経路を除いた重み付き有限状態オートマトンである第２オートマトンに変換する変換方法であって、
    指定部が、前記第１オートマトンにおける、初期状態から探索済み経路の先端の状態までの累積重みと、当該探索済み経路の先端の状態から終了状態に至る最良経路の重みとを加えた合成重みが最良となる前記探索済み経路における先端の状態を、開始位置として指定する指定ステップと、
    探索部が、前記識別子毎に、前記第１オートマトンにおける前記開始位置から次の境界までの重みが最良となる経路を探索する探索ステップと、
    遷移登録部が、前記開始位置から次の境界まで探索が達した場合、探索して得られた経路における開始位置と先端の状態とに対応して、前記第２オートマトンに新たな遷移を登録する遷移登録ステップと、
    を含む変換方法。
16. コンピュータを、入力記号が割り当てられた経路の境界、前記境界の出現位置、および、併合可能な経路を識別する識別子を付与した重み付き有限状態オートマトンである第１オートマトンを、少なくとも一部の不要な経路を除いた重み付き有限状態オートマトンである第２オートマトンに変換する変換装置として機能させるためのプログラムであって、
    前記コンピュータを、
    前記第１オートマトンにおける、初期状態から探索済み経路の先端の状態までの累積重みと、当該探索済み経路の先端の状態から終了状態に至る最良経路の重みとを加えた合成重みが最良となる前記探索済み経路における先端の状態を、開始位置として指定する指定部と、
    前記識別子毎に、前記第１オートマトンにおける前記開始位置から次の境界までの重みが最良となる経路を探索する探索部と、
    前記開始位置から次の境界まで探索が達した場合、探索して得られた経路における開始位置と先端の状態とに対応して、前記第２オートマトンに新たな遷移を登録する遷移登録部と、
    して機能させるプログラム。

Images