(57)【要約】【課題】有向グラフの経路を探索して重複しない記号列を出力する。【解決手段】探索装置は、仮説記憶部と、取出部と、仮説展開部とを備える。仮説記憶部は、入力記号列と、入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態とを保持する情報である１以上の仮説を記憶する。取出部は、１以上の仮説のうち、各仮説に対応する探索済みの経路の重みに、当該経路の先頭の状態から終了状態に至る最良の経路の重みを加えた重みが最良となる、探索済みの経路に対応する入力記号列を保持する１つの仮説を、対象仮説として取り出す。仮説展開部は、対象仮説が保持する１以上の状態から探索を進めた新たな仮説を生成して、仮説記憶部に書き込む。仮説展開部は、対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を対象仮説に追加した後に、探索を進めて新たな仮説を生成する。【選択図】図１
2015121708.tif 000002
【特許請求の範囲】
【請求項１】
入力記号および重みが割り当てられた有向グラフの経路を探索する探索装置であって、
前記有向グラフの経路を初期状態から探索することにより得られる入力記号列と、前記入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態とを保持する情報である１以上の仮説を記憶する仮説記憶部と、
前記仮説記憶部が記憶する１以上の仮説のうち、各仮説に対応する探索済みの経路の重みに、当該経路の先頭の状態から終了状態に至る最良の経路の重みを加えた重みが最良となる、前記探索済みの経路に対応する入力記号列を保持する１つの仮説を、対象仮説として取り出す取出部と、
取り出した前記対象仮説が、終了状態まで探索が済んだ終了仮説ではない場合、前記対象仮説が保持する１以上の状態から、１つの入力記号分探索を進めた経路上の入力記号列を保持する新たな１以上の仮説を生成して、前記仮説記憶部に書き込む仮説展開部と、
を備え、
前記取出部は、予め定められた個数の前記終了仮説を取り出すまで、前記仮説記憶部から前記対象仮説を繰り返して取り出し、
前記仮説展開部は、前記対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を前記対象仮説に追加した後に、探索を進めて前記新たな１以上の仮説を生成する
探索装置。
【請求項２】
取り出した前記対象仮説が前記終了仮説であることを条件として、前記対象仮説が保持する前記入力記号列を出力する出力部をさらに備え、
前記取出部は、取り出した仮説が前記終了仮説ではない場合には、前記仮説展開部が新たな仮説を前記仮説記憶部に書き込んだことに応じて、次の前記対象仮説を取り出し、取り出した仮説が前記終了仮説の場合、即時に次の前記対象仮説を取り出す
請求項１に記載の探索装置。
【請求項３】
前記有向グラフは、重み付き有限状態オートマトンである
請求項１に記載の探索装置。
【請求項４】
前記仮説展開部は、
取り出した前記対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を、前記対象仮説に追加する空遷移処理部と、
前記空遷移処理部による処理後において、前記対象仮説が保持している１以上の状態に終了状態が含まれる場合、前記対象仮説が保持している入力記号列と、前記対象仮説が保持している１以上の状態のうちの終了状態とを保持する新たな仮説を、前記終了仮説として生成して、前記仮説記憶部に書き込む終了生成部と、
前記空遷移処理部による処理後において、前記対象仮説が保持する入力記号列の後に新たな入力記号を連結した入力記号列と、前記対象仮説が保持する１以上の状態のそれぞれから前記新たな入力記号が割り当てられた遷移に従って到達する１以上の状態とを保持する１以上の新たな仮説を生成して、前記仮説記憶部に書き込む仮説生成部と、
を有する請求項２に記載の探索装置。
【請求項５】
前記仮説は、保持している１以上の状態のそれぞれを通過するときに、保持している入力記号列を得ることができる、１以上の経路における初期状態から終了状態までの重みを累積した値のうちの最良の値を、経路値として保持し、
前記取出部は、前記経路値が最も良い仮説を前記対象仮説として取り出す
請求項４に記載の探索装置。
【請求項６】
前記仮説生成部は、前記経路値をさらに保持する新たな仮説を生成して、前記仮説記憶部に書き込む
請求項５に記載の探索装置。
【請求項７】
前記仮説記憶部は、探索開始段階において、空の入力記号列と、前記有向グラフの１以上の初期状態とを保持する仮説を記憶する
請求項１に記載の探索装置。
【請求項８】
前記仮説展開部は、当該状態から空遷移を辿って到達する状態のうち、終了状態、および、少なくとも１つの空遷移以外の遷移が出ている状態を、前記対象仮説に追加する
請求項１に記載の探索装置。
【請求項９】
前記仮説は、保持している１以上の状態のそれぞれに対応して、前記仮説が保持する入力記号列を得ることができる、初期状態から当該状態までの最良の経路の累積重みを保持する
請求項８に記載の探索装置。
【請求項１０】
前記仮説展開部は、前記対象仮説が保持している状態に対応する累積重みと、前記対象仮説が保持している状態から空遷移を辿って到達する１以上の経路のうちの最良の経路の累積重みとを合計した値を、対応する累積重みとして前記対象仮説に追加する
請求項９に記載の探索装置。
【請求項１１】
前記有向グラフに含まれる状態のそれぞれについて、その状態から終了状態までの最良の経路の重みを予め取得する取得部をさらに備える
請求項１に記載の探索装置。
【請求項１２】
入力記号および重みが割り当てられた有向グラフの経路を探索する探索方法であって、
前記有向グラフの経路を初期状態から探索することにより得られる入力記号列と、前記入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態とを保持する情報である１以上の仮説を仮説記憶部が記憶する記憶ステップと、
前記仮説記憶部が記憶する１以上の仮説のうち、各仮説に対応する探索済みの経路の重みに、当該経路の先頭の状態から終了状態に至る最良の経路の重みを加えた重みが最良となる、前記探索済みの経路に対応する入力記号列を保持する１つの仮説を、対象仮説として取り出す取出ステップと、
取り出した前記対象仮説が、終了状態まで探索が済んだ終了仮説ではない場合、前記対象仮説が保持する１以上の状態から、１つの入力記号分探索を進めた経路上の入力記号列を保持する新たな１以上の仮説を生成して、前記仮説記憶部に書き込む仮説展開ステップと、
を含み、
前記取出ステップは、予め定められた個数の前記終了仮説を取り出すまで、前記仮説記憶部から前記対象仮説を繰り返して取り出し、
前記仮説展開ステップでは、前記対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を前記対象仮説に追加した後に、探索を進めて前記新たな１以上の仮説を生成する
探索方法。
【請求項１３】
コンピュータを、入力記号および重みが割り当てられた有向グラフの経路を探索する探索装置として機能させるためのプログラムであって、
前記コンピュータを、
前記有向グラフの経路を初期状態から探索することにより得られる入力記号列と、前記入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態とを保持する情報である１以上の仮説を記憶する仮説記憶部と、
前記仮説記憶部が記憶する１以上の仮説のうち、各仮説に対応する探索済みの経路の重みに、当該経路の先頭の状態から終了状態に至る最良の経路の重みを加えた重みが最良となる、前記探索済みの経路に対応する入力記号列を保持する１つの仮説を、対象仮説として取り出す取出部と、
取り出した前記対象仮説が、終了状態まで探索が済んだ終了仮説ではない場合、前記対象仮説が保持する１以上の状態から、１つの入力記号分探索を進めた経路上の入力記号列を保持する新たな１以上の仮説を生成して、前記仮説記憶部に書き込む仮説展開部
として機能させ、
前記取出部は、予め定められた個数の前記終了仮説を取り出すまで、前記仮説記憶部から前記対象仮説を繰り返して取り出し、
前記仮説展開部は、前記対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を前記対象仮説に追加した後に、探索を進めて前記新たな１以上の仮説を生成する
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、有向グラフの経路を探索する探索装置、探索方法およびプログラムに関する。
【背景技術】
【０００２】
パターン認識においては、入力された信号に対するパターン認識結果の候補を、ＷＦＳＡ（重み付き有限状態オートマトン）またはＷＦＳＡと等価なモデルで出力する場合がある。例えば、音声認識においては、入力された音声を認識した結果として単語ラティスを出力する場合がある。単語ラティスは、単語スコアを重みに、単語を入力記号に割り当てることにより、ＷＦＳＡで表現できる。
【０００３】
パターン認識においては、入力された信号に対応する最も尤もらしい結果を１つだけ出力するのではなく、１番目からＮ番目（Ｎは２以上の整数）に尤もらしい結果を出力する場合がある。Ｎ個の結果を出力することで、１番目に尤もらしい結果が誤っている場合であっても、２番目以降の結果をユーザが選択することで誤りを訂正することができる。また、別のモデルを使って尤もらしさを再計算することで１番目に尤もらしい結果を入れ替えることもできる。Ｎ個の結果を出力するためには、入力された信号から得られるＷＦＳＡを探索して、初期状態から終了状態に至る経路のうちＮ番目に良い経路を見つけなければならない。
【０００４】
また、パターン認識以外でも、Ｎ番目に良い経路が必要な場合がある。例えば、ある駅から別の駅までの経路を、移動時間が短い順にＮ個表示したい場合等がある。このような場合、駅間の移動時間を重みに、駅名を入力記号に割り当てたＷＦＳＡ、または、このＷＦＳＡと等価なモデルを作成して、Ｎ番目に良い経路を見つけることができる。
【０００５】
ＷＦＳＡには、同一の入力記号列を得ることができる経路が、複数含まれる場合がある。このようなＷＦＳＡを非決定性重み付き有限状態オートマトン（非決定性ＷＦＳＡ）という。このような非決定性ＷＦＳＡから重みが良い順にＮ個の経路を見つけたとしても、入力記号列が異なる経路はＮ個より少なくなることがある。通常、Ｎ個の結果が必要な場合は、異なるＮ個の入力記号列を出力しなければならない。例えば、パターン認識の結果としてユーザに３個の結果、つまり、３つの入力記号列を選択候補として表示する場合を考える。もし、表示される３つの結果が全て同一であると、何れの候補を選択しても結果は同じとなり、候補を表示する意味がない。従って、対応する経路の重みが良い方から順に、重複を含まない複数個の入力記号列を出力しなければならない。
【０００６】
しかしながら、ＷＦＳＡに空（ε）の入力記号が割り当てられている場合、重複を含まない複数個の入力記号列を見つけ出すことが困難であった。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第８２３４１１５号明細書
【特許文献２】米国特許第６５８７８４４号明細書
【非特許文献】
【０００８】
【非特許文献１】G.  Saon，  D.Pover  and  G.Zweig，  “Anatomy  of  an  extremely  fast  LVCSR  decoder”，  in  Proceedings  of  INTERSPEECH，  2005，  PP.549-552
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明が解決しようとする課題は、入力記号および重みが割り当てられた有向グラフの経路を探索して、初期状態から終了状態までの累積した重みが最良の経路から順に、重複しない複数個の入力記号列を見つけ出すことにある。
【課題を解決するための手段】
【００１０】
実施形態の探索装置は、入力記号および重みが割り当てられた有向グラフの経路を探索する。前記探索装置は、仮説記憶部と、取出部と、仮説展開部と、を備える。前記仮説記憶部は、前記有向グラフの経路を初期状態から探索することにより得られる入力記号列と、前記入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態とを保持する情報である１以上の仮説を記憶する。前記取出部は、前記仮説記憶部が記憶する１以上の仮説のうち、各仮説に対応する探索済みの経路の重みに、当該経路の先頭の状態から終了状態に至る最良の経路の重みを加えた重みが最良となる、前記探索済みの経路に対応する入力記号列を保持する１つの仮説を、対象仮説として取り出す。前記仮説展開部は、取り出した前記対象仮説が、終了状態まで探索が済んだ終了仮説ではない場合、前記対象仮説が保持する１以上の状態から、１つの入力記号分探索を進めた経路上の入力記号列を保持する新たな１以上の仮説を生成して、前記仮説記憶部に書き込む。さらに、前記取出部は、予め定められた個数の前記終了仮説を取り出すまで、前記仮説記憶部から前記対象仮説を繰り返して取り出す。前記仮説展開部は、前記対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を前記対象仮説に追加した後に、探索を進めて前記新たな１以上の仮説を生成する。
【図面の簡単な説明】
【００１１】
【図１】実施形態に係る探索装置の構成を示す図。
【図２】仮説記憶部が記憶する仮説を示す図。
【図３】実施形態に係る探索装置の処理フローを示す図。
【図４】実施形態に係る探索装置の処理内容を表す擬似コードを示す図。
【図５】関数の処理内容を表す擬似コードを示す図。
【図６】ＷＦＳＡの一例を示す図。
【図７】実施形態に係る探索装置のハードウェア構成を示す図。
【図８】実施形態に係るパターン認識装置の構成を示す図。
【図９】実施形態に係るパターン認識装置の処理フローを示す図。
【発明を実施するための形態】
【００１２】
＜前提＞
まず、本実施形態の前提となる技術および定義等について説明する。
【００１３】
本実施形態では、入力記号および重みが割り当てられた有向グラフの一例である重み付き有限状態オートマトン（ＷＦＳＡ）を探索する。
【００１４】
ＷＦＳＡは、遷移に入力記号が割り当てられ、遷移に重みが割り当てられる。ＷＦＳＡは、状態の集合Ｑ、遷移の集合Ｅ、入力記号の集合Σ、重みの集合Ｋ、初期状態の集合Ｉ、終了状態の集合Ｆ、初期重み関数λ、および終了重み関数ρの８つの要素の組（Ｑ，Ｅ，Σ，Ｋ，Ｉ，Ｆ，λ，ρ）で構成される。遷移は、４つの要素の組（前状態，次状態，入力記号，重み）で構成される。
【００１５】
本実施形態では、遷移の入力記号には、入力記号の集合Σに含まれる記号の他に、εを割り当てることができる。εは、記号が空であることを意味する。εはΣに含まれないものとする。遷移をした結果として得られる入力記号がεである遷移、すなわち、本実施形態においてεが入力記号として割り当てられている遷移を、空遷移またはε遷移と呼ぶ。
【００１６】
入力記号列は、ＷＦＳＡに割り当てられた入力記号を０個以上連結した記号列である。なお、０個の記号を連結した入力記号列とは、まだ記号が１つも連結されておらず、空の記号列を意味する。
【００１７】
本実施形態では、遷移ｅの前状態をｐ（ｅ）と表し、遷移ｅの次状態をｎ（ｅ）と表し、入力記号をｉ（ｅ）と表し、重みをｗ（ｅ）と表す。また、本実施形態では、遷移の集合Ｅに含まれる遷移の次状態から成る集合をｎ（Ｅ）と表す。本実施形態では、空集合を｛｝と表す。後述する疑似コードでは、空集合を０に／を重ねた文字で表す。本実施形態では、集合Ｂの要素の数を｜Ｂ｜と表す。
【００１８】
状態ｑｘから状態ｑｙへの経路πｘｙは、遷移で構成される。この経路を構成する遷移をｅ１，ｅ２，…，ｅｎ∈Ｅとする場合、πｘｙ＝ｅ１ｅ２…ｅｎである。ここで、ｑｘ＝ｐ（ｅ１）、ｎ（ｅｉ）＝ｐ（ｅｉ＋１）、ｎ（ｅｎ）＝ｑｙ、ｉ＝１，…，ｎ−１である。
【００１９】
重みの集合Ｋは、一例として、整数全体の集合、実数全体の集合、複素数全体の集合、行列、ブーリアン（０および１）の集合等である。重みの集合Ｋは、正でない実数の集合または負でない実数の集合等であってもよい。本実施形態では、初期状態ｑｉ∈Ｉに対応する初期重みをλ（ｑｉ）と表し、終了状態ｑｆ∈Ｆに対応する終了重みをρ（ｑｆ）と表す。なお、初期重みρ（ｑｉ）が無くてもよい。また、終了重みρ（ｑｆ）も無くてもよい。この場合、初期状態λ（ｑｉ）＝１＃、終了状態λ（ｑｆ）＝１＃として処理がされる。１＃については後述する。
【００２０】
本実施形態では、重みの集合Ｋは、半環（ｓｅｍｉｒｉｎｇ）と呼ばれる条件を満たしている。具体的に、集合Ｋが半環を満たすとは、次の４つの条件を満たすことをいう。
【００２１】
条件１：Ｋが２項演算（＋）に対して可換モノイドであり、その単位元が０＃である。
条件２：Ｋが２項演算（×）に対してモノイドであり、その単位元が１＃である。
条件３：任意のｘ、ｙ、ｚ∈Ｋに対して分配法則が成り立つ。つまり、ｘ（×）（ｙ（＋）ｚ）＝（ｘ（×）ｙ）（＋）（ｘ（×）ｚ）、および、（ｙ（＋）ｚ）（×）ｘ＝（ｙ（×）ｘ）（＋）（ｚ（×）ｘ）を満たす。
条件４：任意のｘ∈Ｋに対して、０＃（×）ｘ＝ｘ（×）０＃＝０＃が成り立つ。
【００２２】
従って、本実施形態では、集合Ｋに含まれる任意の要素を、２項演算（＋）および（×）で合成することができる。なお、後述する擬似コードでは、２項演算（＋）を＋を丸で囲った記号で表し、２項演算（×）を×を丸で囲った記号で表す。また、本実施形態では、集合Ｋに、定数０＃および１＃を含めることができる。
【００２３】
半環の一例には、トロピカル半環（ｔｒｏｐｉｃａｌ  ｓｅｍｉｒｉｎｇまたはｍｉｎ-ｐｌｕｓ  ｓｅｍｉｒｉｎｇ）がある。トロピカル半環を満たす集合Ｋは、集合Ｋが負でない実数Ｒ＋に無限大（∞）を加えた集合であり、（＋）がｍｉｎ、（×）が＋、０＃が∞、１＃が０と定義される。集合Ｋが負でない整数Ｎ＋に∞を加えた集合も、同様にトロピカル半環を満たす。集合Ｋが正でない実数Ｒ−に−∞を加えた集合であり、（＋）がｍａｘ、（×）が＋、０＃が−∞、１＃が０と定義される半環も存在する。また、トロピカル半環の（＋）の計算をｘ（＋）ｙ＝−ｌｏｇ（ｅ−ｘ＋ｅ−ｙ）に置き換えた対数半環（ｌｏｇ  ｓｅｍｉｒｉｎｇ）も存在する。他にも様々な半環が存在する。
【００２４】
また、本実施形態では、集合Ｗに含まれる全ての要素を（＋）で合成することを、下記の式のように表す。
【数１】
2015121708.tif 000003
【００２５】
すなわち、式（１）は、集合Ｗに含まれる要素をｗ１，ｗ２，ｗ３，…，ｗ｜Ｗ｜とした場合、ｗ１（＋）ｗ２（＋）ｗ３（＋）…（＋）ｗ｜Ｗ｜を演算することを表す。
【００２６】
本実施形態において、重みの最良値とは、対象となる重みの要素について演算（＋）を行った結果が最良となる値を意味する。対象となる重みが同じであっても使用する半環が異なると重みの最良値が異なる場合がある。例えば重みの集合｛１，２，３｝に対して（＋）がｍｉｎであるような半環を用いている場合は、重みの最良値は１になる。（＋）がｍａｘであるような半環を用いている場合は重みの最良値は３になる。
【００２７】
なお、初期状態に入力記号または重みが割り当てられている場合は、ＷＦＳＡに新たな１つの初期状態と、その新たな初期状態から元々の初期状態への遷移とを追加する。そして、その遷移に元々の初期状態に割り当てられている入力記号および重みを割り当て、元々の初期状態を初期状態でない状態にするように変形すればよい。
【００２８】
また、本実施形態では、重みを状態に割り当てた重み付き有向グラフの経路を探索してもよい。この場合、探索対象の有向グラフを、予めＷＦＳＡに変換すればよい。具体的には、探索対象の有向グラフの状態ｑの重みをｗ（ｑ）とした場合、この探索対象の有向グラフを、遷移ｅの重みをｗ（ｎ（ｅ））とするＷＳＦＡに変換すればよい。なお、予め変換せずに、ｗ（ｅ）をｗ（ｎ（ｅ））に置き換えてもよい。
【００２９】
また、本実施形態では、入力記号を状態に割り当てた重み付き有向グラフの経路を探索してもよい。この場合も、探索対象の有向グラフを、予めＷＦＳＡに変換すればよい。具体的には、探索対象の有向グラフの状態ｑの入力記号をｉ（ｑ）とした場合、遷移ｅの入力記号をｉ（ｎ（ｅ））とするＷＳＦＡに変換すればよい。なお、予め変換せずに、ｉ（ｅ）をｉ（ｎ（ｅ））に置き換えてもよい。
【００３０】
（探索装置１０の構成）
図１は、実施形態に係る探索装置１０の構成を示す図である。図２は、仮説記憶部２４が記憶する仮説を示す図である。
【００３１】
探索装置１０は、入力記号および重みが割り当てられた有向グラフの一例であるＷＦＳＡの経路を探索する。探索装置１０は、初期状態から終了状態までの経路上の入力記号を連結した入力記号列を、重みの累積値が最良となる経路から順に、重複無しに予め定められた個数（Ｎ個）見つけ出す。そして、探索装置１０は、例えば、見つけ出したＮ個の入力記号列、または、Ｎ番目の入力記号列を出力する。
【００３２】
探索装置１０は、取得部２１と、有向グラフ記憶部２２と、最良経路重み記憶部２３と、仮説記憶部２４と、取出部２５と、出力部２６と、仮説展開部２７とを備える。
【００３３】
取得部２１は、外部からＷＦＳＡを取得する。取得部２１は、一例として、後述するデコーダ等からＷＦＳＡを取得する。そして、取得部２１は、取得したＷＦＳＡを有向グラフ記憶部２２に記憶させる。
【００３４】
また、取得部２１は、ＷＦＳＡに含まれる状態のそれぞれについて、その状態から終了状態までの最良の経路の重みを、最良経路重み記憶部２３に記憶させる。取得部２１は、一例として、ＷＦＳＡを生成するデコーダ等から、ＷＦＳＡに含まれる状態のそれぞれについての最良経路の重みを予め取得してもよい。また、取得部２１は、有向グラフ記憶部２２に記憶されているＷＦＳＡに基づき、ＷＦＳＡに含まれる状態のそれぞれについての最良経路の重みを計算してもよい。
【００３５】
例えば、取得部２１は、ＷＦＳＡの終了状態から逆方向に経路を辿って、それぞれの状態までの重みの最良値を計算する。より具体的には、取得部２１は、Ｄｉｊｋｓｔｒａのアルゴリズム、Ｂｅｌｌｍａｎ−Ｆｏｒｄのアルゴリズム、ｇｅｎｅｒｉｃ  ｓｉｎｇｌｅ−ｓｏｕｒｃｅ  ｓｈｏｒｔｅｓｔ  ｄｉｓｔａｎｃｅアルゴリズム等を用いて、終了状態からその状態までの重みの最良値を計算する。また、ＷＦＳＡに循環する経路が含まれていなければ、非循環有効グラフ（Ｄｉｒｅｃｔｅｄ  Ａｃｙｃｌｉｃ  Ｇｒａｐｈ）に使用できる距離計算アルゴリズムを用いて、終了状態からその状態までの重みの最良値を計算してもよい。
【００３６】
有向グラフ記憶部２２は、取得部２１が取得したＷＦＳＡを記憶する。有向グラフ記憶部２２は、仮説展開部２７から常時アクセスが可能なように、ＷＦＳＡを記憶する。
【００３７】
最良経路重み記憶部２３は、ＷＦＳＡに含まれる状態のそれぞれについて、その状態から終了状態までの最良の経路の重みを記憶する。最良経路重み記憶部２３は、仮説展開部２７から状態が指定された場合に、対応する最良経路重みを返す。最良経路重み記憶部２３は、一例として、連想配列を用いて、それぞれの状態と最良経路重みとを対応付けて記憶する。また、状態が番号で識別できる場合であれば、配列を用いて、それぞれの状態と最良経路重みとを対応付けて記憶してもよい。
【００３８】
仮説記憶部２４は、１以上の仮説を記憶する。仮説は、図２に示すように、複数の状態と、複数の累積重みと、経路値と、終了フラグと、入力記号列とを保持する情報である。
【００３９】
入力記号列は、有向グラフ記憶部２２に記憶されたＷＦＳＡの経路を、初期状態からある状態まで探索することにより得られる経路上の入力記号を連結した列である。入力記号列は、１つの入力記号分の探索が進むと、その入力記号が後ろに連結される。従って、入力記号列は、ＷＦＳＡの探索が進むにつれて、長くなる。ただし、入力記号が空（ε）の場合には、その入力記号は連結されない。入力記号列は、配列やリンクリストで表すことができる。入力記号列そのものではなく、入力記号列に対応する経路を仮説に保持しておき、出力部２６が出力する直前に、保持している経路に対応する入力記号列を出力するようにしてもよい。この場合、仮説に保持されている経路は入力記号列を表現する一形態であるといえる。
【００４０】
複数の状態のそれぞれは、当該仮説が保持する入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態を示す情報である。すなわち、複数の状態のそれぞれは、同一の入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態である。従って、当該仮説が保持する入力記号列は、初期状態から、当該仮説が保持するそれぞれの状態までの何れかの経路上の入力記号列と一致する。
【００４１】
複数の累積重みのそれぞれは、複数の状態のそれぞれに一対一で対応して保持されている。ある状態に対応する累積重みは、初期状態から当該状態までの当該仮説が保持する入力記号列が得られる最良の経路の累積重みである。すなわち、ある状態に対応する累積重みは、初期状態から当該状態までの当該仮説が保持する入力記号列が得られる１以上の経路における重みの累積値のうち、最良値である。
【００４２】
経路値は、保持している１以上の状態のそれぞれを通過する１以上の経路における初期状態から終了状態までの重みを累積した値のうちの最良の値である。
【００４３】
例えば、ある状態について、当該状態に対応する累積重みと、当該状態から終了状態までの最良経路の重みとを合計した値を合計値とする。この場合において、経路値は、当該仮説が保持する１以上の状態のそれぞれの合計値のうち、最も良い合計値となる。なお、当該仮説が保持する１以上の状態のそれぞれにおける、当該状態に対応する累積重みは、当該仮説が保持している。また、当該仮説が保持する１以上の状態のそれぞれにおける、当該状態から終了状態までの最良経路の重みは、最良経路重み記憶部２３に記憶されている。
【００４４】
終了フラグは、終了状態まで経路の探索が済んだ終了仮説であるか否かを示す。より具体的には、終了フラグは、当該仮説が保持する１以上の状態の全てが終了状態の場合に、Ｔｒｕｅとなる。また、終了フラグは、当該仮説が保持する１以上の状態の何れか１つが終了状態でない場合に、Ｆａｌｓｅとなる。
【００４５】
このような仮説記憶部２４は、探索開始段階において、初期仮説を記憶する。初期仮説は、空の入力記号列と、ＷＦＳＡに含まれる１以上の初期状態（状態）と、１以上の初期状態のそれぞれに対応した初期重み（累積重み）と、１以上の初期状態のそれぞれに対応する最良経路の重みのうちの最良値（経路値）と、終了状態まで探索が完了していないことを示す終了フラグ（Ｆａｌｓｅの終了フラグ）とを保持する。仮説記憶部２４に記憶された仮説は、探索が進むと、ＷＦＳＡの経路の分岐に従って分岐される。従って、仮説記憶部２４は、探索が進むに連れて、記憶する仮説の数が増加する。
【００４６】
取出部２５は、仮説記憶部２４から、１つの仮説を対象仮説として取り出して、出力部２６および仮説展開部２７に渡す。この場合において、取出部２５は、仮説記憶部２４が記憶する１以上の仮説のうち、各仮説に対応する探索済みの経路の重みに、当該経路の先頭の状態から終了状態に至る最良の経路の重みを加えた重みが最良となる、探索済みの経路に対応する入力記号列を保持する１つの仮説を、対象仮説として取り出す。すなわち、仮説記憶部２４は、経路値が最も良い仮説を、対象仮説として取り出す。また、取出部２５は、取り出した仮説を仮説記憶部２４から削除する。
【００４７】
従って、取出部２５は、経路値を優先度とした優先度付きキューとして、仮説記憶部２４を動作させている。例えば、ヒープ、連想配列、配列、２分木またはリスト等により仮説を記憶することにより、優先度付きキューを実装する。
【００４８】
取出部２５は、取り出した仮説が終了仮説ではない場合には、仮説展開部２７が新たな仮説を仮説記憶部２４に書き込んだことに応じて、次の１つの仮説を対象仮説として取り出して、出力部２６および仮説展開部２７に渡す。取出部２５は、取り出した仮説が終了仮説の場合、即時に次の１つの仮説を対象仮説として取り出して、出力部２６および仮説展開部２７に渡す。取出部２５は、Ｎ個の終了仮説を取り出すまで、仮説記憶部２４から対象仮説を繰り返して取り出す。
【００４９】
出力部２６は、取出部２５が取り出した対象仮説が、終了仮説であることを条件として（より具体的には、対象仮説の終了フラグがＴｒｕｅであることを条件として）、対象仮説が保持する入力記号列を出力する。出力部２６は、対象仮説が終了仮説ではない場合、何ら処理をしない。
【００５０】
なお、出力部２６は、Ｎ個の入力記号列が得られるまで、すなわち、Ｎ個の終了仮説が取り出されるまで入力記号列を記憶しておき、Ｎ個の入力記号列が得られた後にＮ個分の入力記号列をまとめて出力してよい。また、出力部２６は、Ｎ個の入力記号列が得られるまで入力記号列を出力せずに、Ｎ個の入力記号列が得られたのちに、Ｎ番目の入力記号列のみを出力してもよい。また、出力部２６は、終了仮説が取り出された場合に、即時に１つの入力記号列を出力してもよい。
【００５１】
仮説展開部２７は、取出部２５が取り出した対象仮説が終了仮説ではない場合（より具体的には、対象仮説の終了フラグがＦａｌｓｅである場合）、対象仮説が保持する１以上の状態から、１つの入力記号分探索を進めた経路上の入力記号列を保持する新たな１以上の仮説を生成する。そして、仮説展開部２７は、生成した新たな１以上の仮説を仮説記憶部２４に書き込む。
【００５２】
この場合において、仮説展開部２７は、対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を対象仮説に追加した後に、探索を進めて新たな１以上の仮説を生成する。なお、仮説展開部２７は、対象仮説が終了仮説である場合、何ら処理をしない。
【００５３】
仮説展開部２７は、空遷移処理部３１と、終了生成部３２と、仮説生成部３３とを有する。
【００５４】
空遷移処理部３１は、取り出した対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を、対象仮説に追加する。なお、空遷移処理部３１は、対象仮説が保持する状態から、２つ以上の空遷移を辿って到達する状態が存在する場合には、その２以上の空遷移を辿って到達する状態も対象仮説に追加する。
【００５５】
また、空遷移処理部３１は、空遷移を辿って到達する状態であっても、その状態から出て行く遷移が全て空遷移であり、且つ、その状態が終了状態でない場合には、対象仮説に追加しなくてもよい。すなわち、この場合、空遷移処理部３１は、対象仮説が保持する状態から空遷移を辿って到達する状態のうち、終了状態、および、少なくとも１つの空遷移以外の遷移が出ている状態を、対象仮説に追加する。
【００５６】
また、空遷移処理部３１は、追加する状態に対応させて、累積重みも対象仮説に追加する。具体的には、空遷移処理部３１は、対象仮説が保持している状態に対応する累積重みと、対象仮説が保持している状態から空遷移を辿って到達する１以上の経路のうちの最良の経路の累積重みとを合計した値を、対応する累積重みとして対象仮説に追加する。
【００５７】
終了生成部３２は、空遷移処理部３１による処理後において、対象仮説が保持している１以上の状態に終了状態が含まれる場合、終了仮説を生成する。具体的には、終了生成部３２は、対象仮説が保持している入力記号列と、対象仮説が保持している１以上の状態のうちの終了状態と、対象仮説が保持している経路値と、終了状態まで探索が完了したことを示す終了フラグ（Ｔｒｕｅ）とを保持する新たな仮説を、終了仮説として生成する。そして、終了生成部３２は、生成した終了仮説を仮説記憶部２４に書き込む。
【００５８】
仮説生成部３３は、空遷移処理部３１による処理後において、対象仮説が保持する入力記号列の後に、対象仮説が保持する１以上の状態から出ている遷移に従って得られる新たな１つの入力記号を連結した入力記号列を保持する新たな仮説を生成する。
【００５９】
この場合において、仮説生成部３３は、対象仮説が保持する１以上の状態のそれぞれから新たな入力記号が割り当てられた遷移に従って到達する１以上の状態を、新たな仮説に保持させる。また、仮説生成部３３は、経路値を算出して、生成した新たな仮説に保持させる。また、仮説生成部３３は、終了状態ではないことを示す終了フラグ（Ｆａｌｓｅの終了フラグ）を、生成した新たな仮説に保持させる。
【００６０】
さらに、仮説生成部３３は、対象仮説が保持する１以上の状態から、異なる入力記号が割り当てられた複数の遷移が出ている場合には、入力記号の数だけ対象仮説を分岐させて、複数の新たな仮説を生成する。そして、仮説生成部３３は、このように生成した新たな仮説を仮説記憶部２４に書き込む。
【００６１】
（処理フロー）
図３は、実施形態に係る探索装置１０の処理フローを示す図である。つぎに、探索装置１０の処理手順を説明する。
【００６２】
まず、ステップＳ１０１において、探索装置１０は、ＷＦＳＡを取得する。なお、取得部２１は、既にＷＦＳＡを取得している場合には、ステップＳ１０１の処理を実行しなくてよい。
【００６３】
続いて、ステップＳ１０２において、探索装置１０は、ＷＦＳＡに含まれる状態のそれぞれについて、その状態から終了状態までの最良の経路の重みを取得する。探索装置１０は、ＷＦＳＡを生成したデコーダ等から対応する値を取得してもよい。また、探索装置１０は、ＷＦＳＡを参照して対応する値を計算することにより、対応する値を取得してもよい。なお、探索装置１０は、既に対応する値を取得している場合には、ステップＳ１０２の処理を実行しなくてよい。
【００６４】
続いて、ステップＳ１０３において、探索装置１０は、ＷＦＳＡおよび最良の経路の重みにアクセスしながら、ＷＦＳＡを探索して、Ｎ番目に良い入力記号列を見つけ出す。すなわち、仮説展開部２７は、初期状態から終了状態までの経路上の入力記号列を、重みの累積値が最良となる経路から順に、重複無しにＮ個見つけ出す。
【００６５】
この場合において、探索装置１０は、優先度付きキュー（仮説記憶部２４）から優先度が最も高い（すなわち、保持している経路値が最も良い）１つの仮説を取り出し、取り出した仮説を分岐させ、再度優先度付きキュー（仮説記憶部２４）に書き込む処理を繰り返すことにより、入力記号列を見つけ出す。
【００６６】
そして、ステップＳ１０４において、出力部２６は、見つけ出したＮ個の入力記号列を出力する。なお、出力部２６は、Ｎ個の入力記号列をまとめて出力してもよいし、最良の経路の入力記号列が見つけ出される毎にその都度１つずつ入力記号列を出力してもよい。また、出力部２６は、Ｎ番目の入力記号列のみを出力してもよい。
【００６７】
（擬似コード）
図４は、実施形態に係る探索装置１０の処理内容を表す擬似コードを示す図である。つぎに、擬似コードを参照して、探索装置１０のステップＳ１０３の詳細な処理例を説明する。
【００６８】
擬似コードでは、状態ｑから終了状態までの最良の経路の重みを、関数ｗｐｒｅｄ（ｑ）で得ることができる。擬似コードでは、出力する入力記号列の集合をＲと表す。擬似コードでは、出力すべき入力記号列の数をＮと表す。Ｎ＝３の場合、探索装置１０は、最も良い経路上の入力記号列と、２番目に良い経路上の入力記号列と、３番目に良い経路上の入力記号列とを出力する。
【００６９】
また、本例では、探索する経路の始端は初期状態、終端は終了状態である。他の状態を始端または終端とする場合には、それらの状態をそれぞれ初期状態および終了状態とするように、ＷＦＳＡを予め変形すればよい。また、逆向きに探索したい場合には、ＷＦＳＡの遷移の向きを逆向きにし、初期状態と終了状態と入れ替えればよい。
【００７０】
また、本例のＷＦＳＡでは、重みの集合はトロピカル半環を満たす。トロピカル半環の場合、重みは小さい方が良い。
【００７１】
また、擬似コードでは、１以上の仮説を記憶する優先度付きキューをＳで表す。擬似コードでは、仮説は、４つの要素の組（ｓ，経路値，終了フラグ（ｆ），入力記号列（ｒ））で表される。ｓは、状態ｑと対応する累積重みｗとの組の集合を表す。また、本例では、重みの集合がトロピカル半環を満たすので、Ｓは、仮説の取り出し要求を受けた場合、経路値が最も小さい仮説を、優先度が最も高い仮説として出力する。なお、このような優先度付きキューＳにより、探索装置１０は、有向グラフの経路を初期状態から探索することにより得られる入力記号列と、入力記号列を得ることができる１以上の経路のそれぞれの先頭の状態とを保持する情報である１以上の仮説を記憶する仮説記憶部２４を実装することができる。
【００７２】
まず、１行目では、探索装置１０は、初期状態と初期重みとの２つの組の集合を、ｓに代入する。
【００７３】
２行目では、探索装置１０は、次のような４つの要素の組を仮説として生成してＳに追加する。
【００７４】
仮説の１つ目の要素は、１行目で生成したｓである。仮説の２つ目の要素は、ｓに含まれるそれぞれの状態ｑと累積重みｗの組について、ｗ（×）ｗｐｒｅｄ（ｑ）を全て計算し、それらの値を（＋）で合成した結果である。本例の場合、（＋）がｍｉｎであるので、２つ目の要素は、ｗ＋ｗｐｒｅｄ（ｑ）の値の中で最も小さい値となる。３つ目の要素は、ｆａｌｓｅである。つまり、この仮説は、終了状態まで探索が完了しておらず、まだ展開されることを表す。４つ目の要素はεである。探索開始段階においては、何れの遷移も通過しておらず、入力記号列に連結されるべき入力記号が存在しないので、入力記号列はεとなる。
【００７５】
３行目は、Ｓが空集合ではない間、４行目から１７行目の処理を繰り返すことを示す。Ｓが空集合の場合、探索装置１０は、処理を１８行目に進める。Ｓが空集合ではない場合、探索装置１０は、処理を４行目に進める。
【００７６】
４行目では、探索装置１０は、Ｓに含まれる仮説のうち、優先度が最も高い仮説を対象仮説として取り出す。本例では、探索装置１０は、２番目の要素の経路値が最も小さい仮説をＳから取り出す。なお、４行目以降の処理では、２つめの要素（経路値）を使用しない。従って、擬似コードの４行目は、取り出した対象仮説の２つ目の要素の値を、何れの値も割り当てないこと示す“・”で表している。４行目を実行することにより、探索装置１０は、仮説記憶部２４が記憶する１以上の仮説のうち、終了状態まで累積した重みが最良となる可能性のある経路から得られる入力記号列を保持する１つの仮説を、対象仮説として取り出すことができる。
【００７７】
５行目では、探索装置１０は、取り出した対象仮説の３つ目の要素の終了フラグｆが、ｔｒｕｅか否かを判定する。すなわち、探索装置１０は、対象仮説が終了仮説であるか否かを判定する。探索装置１０は、ｆがｔｒｕｅである場合、６行目から８行目を処理する。探索装置１０は、ｆがｔｒｕｅではない場合、１０行目から１７行目を処理する。
【００７８】
６行目では、探索装置１０は、見つけた結果を、Ｒに追加する。Ｒは、２つの要素の組の集合である。２つの要素の組のうち、１つ目の要素は、得られた入力記号列ｒの順位である。最初に見つけた結果、つまり、対応する経路の累積重みが最も良かった入力記号列の順位は、１になる。２つ目の要素は得られた入力記号列ｒである。６行目を実行することにより、探索装置１０は、取り出した対象仮説が、終了状態まで探索が完了した終了仮説であることを条件として、対象仮説が保持する入力記号列を出力することができる。
【００７９】
７行目では、探索装置１０は、Ｒに含まれる要素の数が、取得したい入力記号列の数Ｎとなったか否かを判断する。すなわち、探索装置１０は、取得したい入力記号列の数Ｎだけ、結果が得られたかを判断する。Ｎ個の結果が得られていない場合、探索装置１０は、処理を３行目に戻す。Ｎ個の結果が得られた場合、探索装置１０は、８行目を処理して、この擬似コードの処理結果として、Ｒを返す。そして、擬似コードの処理を終了する。７行目および８行目を実行することにより、探索装置１０は、予め定められた個数（Ｎ個）の終了仮説を取り出すまで、仮説記憶部２４から対象仮説を繰り返して取り出すことができる。
【００８０】
１０行目では、探索装置１０は、詳細を後述する関数ｅｐｓ＿ｓｈｏｒｔｅｓｔを呼び出す。関数ｅｐｓ＿ｓｈｏｒｔｅｓｔの引数は、ｓである。関数ｅｐｓ＿ｓｈｏｒｔｅｓｔは、ｓに含まれるそれぞれの状態のそれぞれから出ていく遷移にε遷移が含まれる場合、その状態からε遷移を辿って到達する新たな状態ｑをｓに追加する。さらに、ｓに新たな状態ｑを追加した場合には、追加した状態ｑに対応する累積重みｗも追加する関数である。関数ｅｐｓ＿ｓｈｏｒｔｅｓｔの処理結果は、ｓに代入して返される。
【００８１】
関数ｅｐｓ＿ｓｈｏｒｔｅｓｔを実行することにより、探索装置１０は、対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を対象仮説に追加することができる。さらに、探索装置１０は、対象仮説が保持している状態に対応する累積重みと、対象仮説が保持している状態から空遷移を辿って到達する１以上の経路のうちの最良の経路の累積重みとを合計した値を、対応する累積重みとして対象仮説に追加することができる。
【００８２】
１１行目では、探索装置１０は、ｓの要素である２つの要素の組の１つ目の要素に終了状態が含まれている場合、その終了状態と対応する累積重みを、２つの要素の組からなる集合ｓｆに代入する。
【００８３】
１２行目では、探索装置１０は、ｓｆが空集合か否かを判定する。探索装置１０は、ｓｆが空集合である場合、処理を１４行目に進める。ｓｆが空集合でない場合、探索装置１０は、処理を１３行目に進める。
【００８４】
１３行目では、探索装置１０は、次のような４つの要素の組を終了仮説として生成してＳに追加する。
【００８５】
終了仮説の１つ目の要素は、１１行目で生成したｓｆである。仮説の２つ目の要素は、ｓｆに含まれるそれぞれの終了状態ｑと累積重みｗの組について、ｗ（×）ρ（ｑ）を全て計算し、それらの値を（＋）で合成した結果である。本例の場合（＋）がｍｉｎであるので、２つ目の要素は、ｗ＋ρ（ｑ）の値の中で最も小さい値となる。３つ目の要素は、ｔｒｕｅである。つまり、この終了仮説は、終了状態まで探索が完了したことを表す。４つ目の要素は、４行目でＳから取り出した対象仮説に保持されている入力記号列ｒである。
【００８６】
１３行目を実行することにより、探索装置１０は、対象仮説が保持している１以上の状態に終了状態が含まれる場合、対象仮説が保持している入力記号列と、対象仮説が保持している１以上の状態のうちの終了状態とを保持する新たな仮説を、終了仮説として生成して、仮説記憶部２４に書き込むことができる。探索装置１０は、１３行目の処理を終えると、処理を１４行目に進める。
【００８７】
１４行目は、Σに含まれる全ての入力記号に対して、１５行目から１７行目の処理を行うことを示す。Σに代えて、ｓに含まれるそれぞれの状態から出ていくそれぞれの遷移に割り当てられている入力記号のうち、Σに含まれる入力記号からなる集合としてもよい。言い換えると、ｓに含まれるそれぞれの状態から出ていくそれぞれの遷移に割り当てられているεを除く入力記号の集合としてもよい。この場合には、探索装置１０は、１６行目を実行しなくてよい。
【００８８】
１５行目では、探索装置１０は、処理対象の入力記号をａとしたときに、ｓに含まれる２つの要素の組（ｑ，ｗ）に対して、次の処理を行う。
【００８９】
まず、探索装置１０は、ｑから出ていく遷移のうちの入力記号ａが割り当てられた遷移をｅとする場合、１つ目の要素をｅの次状態とし、２つ目の要素をｗ（×）ｗ（ｅ）とする２つの要素の組を生成する。
【００９０】
本例では、重みの集合がトロピカル半環を満たすので、２つ目の要素のｗ（×）ｗ（ｅ）は、ｗと遷移ｅの重みとを加算した値となる。ｓａはこのようにして得られた２つの要素の組の集合となる。
【００９１】
１６行目では、探索装置１０は、ｓａが空集合か否かを判定して、空集合でなければ１７行目の処理を行う。
【００９２】
１７行目では、探索装置１０は、次のような４つの要素の組を新たな仮説として生成してＳに追加する。
【００９３】
仮説の１つ目の要素は、１５行目で生成したｓａである。仮説の２つ目の要素は、ｓａに含まれるそれぞれの状態ｑと累積重みｗの組について、ｗ（×）ｗｐｒｅｄ（ｑ）を全て計算し、それらの値を（＋）で合成した結果である。３つ目の要素は、ｆａｌｓｅである。つまり、この仮説は、終了状態まで探索が完了しておらず、まだ展開されることを表す。４つ目の要素は、４行目でＳから取り出した対象仮説に保持されている入力記号列ｒの後ろに、入力記号ａを連結した記号列である。
【００９４】
１７行目を実行することにより、探索装置１０は、対象仮説が保持する入力記号列の後に新たな入力記号を連結した入力記号列と、対象仮説が保持する１以上の状態のそれぞれから新たな入力記号が割り当てられた遷移に従って到達する１以上の状態とを保持する１以上の新たな仮説を生成して、仮説記憶部２４に書き込むことができる。探索装置１０は、全ての入力記号について１５行目から１７行目の処理を繰り返し、全ての入力記号について処理を終えると、処理を３行目に戻す。
【００９５】
１８行目では、探索装置１０は、得られた結果Ｒを返して、本擬似コードの処理を終える。３行目でＳが空集合の場合、探索装置１０は、１８行目を処理する。１８行目で擬似コードを終える場合は、Ｎ個の候補がＷＦＳＡに存在しなかったことを表す。
【００９６】
なお、この擬似コードでは、１番目からＮ番目までの結果を返すようにしている。しかし、Ｎ番目に良い結果のみが必要な場合には、探索装置１０は、Ｒに含まれる２つの要素の組のうち、１番目の値がＮである２つの要素の組のみを結果として返せばよい。
【００９７】
図５は、ｅｓｐ＿ｓｈｏｒｔｅｓｔ（ｓ）関数の処理内容を表す擬似コードを示す図である。つぎに、関数ｅｐｓ＿ｓｈｏｒｔｅｓｔの詳細について説明する。
【００９８】
なお、本例の関数ｅｐｓ＿ｓｈｏｒｔｅｓｔは、Ｄｉｊｋｓｔｒａのアルゴリズムに基づく処理を探索装置１０に実行させる。しかし、関数ｅｐｓ＿ｓｈｏｒｔｅｓｔは、Ｂｅｌｌｍａｎ−Ｆｏｒｄのアルゴリズム、ｇｅｎｅｒｉｃ  ｓｉｎｇｌｅ−ｓｏｕｒｃｅ  ｓｈｏｒｔｅｓｔ  ｄｉｓｔａｎｃｅアルゴリズムに基づく処理を探索装置１０に実行させてもよい。また、ＷＦＳＡに循環する経路が含まれていなければ、関数ｅｐｓ＿ｓｈｏｒｔｅｓｔは、非循環有効グラフのみに使用できる距離計算アルゴリズムに基づく処理を探索装置１０に実行させてもよい。
【００９９】
また、関数ｅｐｓ＿ｓｈｏｒｔｅｓｔでは、それぞれの状態に重みを１つ割り当てることができる。状態ｑに割り当てられる重みをｗε［ｑ］と表す。
【０１００】
１行目および２行目では、探索装置１０は、それぞれの状態ｑに対してｗε［ｑ］を０＃で初期化する。重みの集合がトロピカル半環を満たす場合は、探索装置１０は、ｗε［ｑ］を∞で初期化する。探索装置１０は、一例として、ｗε［ｑ］を重みの最大値で初期化する。なお、本例では、探索装置１０は、集合Ｑに含まれる全ての状態ｑについて初期化をしている。しかし、探索装置１０は、ｓに含まれる状態からε遷移のみで到達できる状態のみを初期化してもよい。
【０１０１】
３行目では、探索装置１０は、結果として出力される状態の集合Ｑｒを空集合で初期化する。
【０１０２】
４行目では、探索装置１０は、ｓに含まれる２つの要素の組（ｑ，ｗ）について５行目と６行目を処理することを表す。５行目では、探索装置１０は、ｗε［ｑ］にｗを代入する。６行目では、探索装置１０は、優先度付きキューΨにｑを追加する。優先度付きキューΨには、同一の状態が重複して書き込まれない。優先度付きキューΨの優先度は、ｗε［ｑ］の値である。重みの集合がトロピカル半環を満たす場合、ｗε［ｑ］が小さいほどｑの優先度が高くなる。優先度付きキューΨは、関数ｅｐｓ＿ｓｈｏｒｔｅｓｔが呼び出される毎に空集合で初期化される。一例として、優先度付きキューΨは、３行目で初期化される。
【０１０３】
７行目では、Ψが空ではない間、８行目から１５行目を繰り返すことを示す。探索装置１０は、Ψが空である場合、処理を１６行目へ進める。Ψが空ではない場合、探索装置１０は、処理を８行目に進める。
【０１０４】
８行目では、探索装置１０は、Ψに含まれる状態のうち、最も優先度が高い状態を取り出して、ｑに代入する。
【０１０５】
９行目では、探索装置１０は、ｑが終了状態である、または、ｑから出ていく遷移に入力記号がεではない遷移が１本以上含まれている場合には、処理を１０行目に進める。ｑが終了状態ではなく、且つ、ｑから出ていく遷移が全て入力記号がεの遷移である場合には、１０行目の処理を実行せずに、処理を１１行目に進める。
【０１０６】
なお、探索装置１０は、９行目の判定処理を無くして、常に１０行目を処理してもよい。常に１０行目を処理したとしても、９行目の判定処理により除かれるべき状態は図４の１５行目で処理されないので、結果は同一となる。もっとも、９行目の判定処理を実行することで、１６行目で返す集合に含まれる要素数が条件判定を入れない場合に比べて同じか小さくなるので、図４の擬似コードでの処理量を削減することができる。
【０１０７】
１０行目では、探索装置１０は、Ｑｒにｑを追加する。
【０１０８】
１１行目は、ｑから出ていく遷移のうち、入力記号がεである遷移ｅに対して、１２行目から１５行目を処理することを示す。
【０１０９】
１２行目では、探索装置１０は、ｗε［ｑ］とｗ（ｅ）とを（×）で演算し、その結果をｗに代入する。
【０１１０】
１３行目は、ｗとｗε［ｎ（ｅ）］とを（＋）で演算した結果がｗε［ｎ（ｅ）］に一致しない場合には、１４行目および１５行目を処理することを示す。重みの集合がトロピカル半環を満たす場合、（＋）は最小値を返す演算となるので、ｗε［ｎ（ｅ）］よりｗが小さければ、探索装置１０は、１４行目および１５行目を処理する。
【０１１１】
１４行目では、探索装置１０は、ｗε［ｎ（ｅ）］にｗを代入する。１５行目では、探索装置１０は、ｎ（ｅ）、つまり遷移ｅの次状態をΨに追加する。
【０１１２】
１６行目では、探索装置１０は、Ｑｒに含まれるそれぞれの状態ｑと、それぞれの状態に割り当てられている重みｗε［ｑ］とを２つの要素の組とした集合を結果として返す。
【０１１３】
探索装置１０は、以上のような関数ｅｐｓ＿ｓｈｏｒｔｅｓｔを実行することにより、対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を対象仮説に追加することができる。さらに、探索装置１０は、対象仮説が保持している状態に対応する累積重みと、対象仮説が保持している状態から空遷移を辿って到達する１以上の経路のうちの最良の経路の累積重みとを合計した値を、対応する累積重みとして対象仮説に追加することができる。
【０１１４】
（具体的な処理例）
図６は、ＷＦＳＡの一例を示す図である。探索装置１０が、１番目に良い入力記号列からＮ番目に良い入力記号列をどのように出力するのかを、図６に示すＷＦＳＡを参照して説明する。
【０１１５】
なお、図６に示すＷＦＳＡは、重みの集合がトロピカル半環を満たす。また、図６では、丸が状態を示し、太線の丸が初期状態を示し、二重丸が終了状態を示し、矢印が遷移を示す。また、図６では、矢印付近の文字のうち／の左側が入力記号を示し、右側が重みを示す。
【０１１６】
また、図６では、丸の中の数字が状態の番号を示し、状態番号の右下の小さい数字が、それぞれの状態から終了状態に至る最良経路の重みを示す。また、図６のＷＦＳＡは、初期重みが０である。
【０１１７】
また、図６のＷＦＳＡは、終了状態５、６、７の終了重みが０であり、終了状態８の終了重みが２である。従って、終了状態に最良経路の重みとして割り当てられている値は、状態５、６、７については０となる。状態８については、状態８から出ていく遷移が無いので、終了重みが最良経路の重みとなる。つまり、状態８に割り当てられる累積重みは２となる。また、本例では、Ｎ＝３である。
【０１１８】
まず、探索装置１０は、図３のステップＳ１０１において、図６に示したＷＦＳＡを有向グラフ記憶部２２に記憶させる。また、探索装置１０は、図３のステップＳ１０２において、ＷＦＳＡに含まれるそれぞれの状態に対して、終了状態からの最良経路の重みを割り当てる。その結果、ｗｐｒｅｄ（０）＝２、ｗｐｒｅｄ（１）＝１、ｗｐｒｅｄ（２）＝２、ｗｐｒｅｄ（３）＝２、ｗｐｒｅｄ（４）＝３、ｗｐｒｅｄ（５）＝０、ｗｐｒｅｄ（６）＝０、ｗｐｒｅｄ（７）＝０、ｗｐｒｅｄ（８）＝２となる。
【０１１９】
続いて、探索装置１０は、図３のステップＳ１０３において、図４の擬似コードに従って処理を実行する。以下、擬似コードに従った処理を説明する。
【０１２０】
まず、１行目で、ｓ＝｛（０，０）｝となる。２行目で、優先度付きキューＳに、４つ要素の組である仮説（｛（０，０），２，ｆａｌｓｅ，ε｝）が追加される。仮説の２つ目の要素は、ｗ（×）ｗｐｒｅｄ（０）＝ｗ＋ｗｐｒｅｄ（０）＝０＋２＝２で計算される。
【０１２１】
３行目で、Ｓが空集合ではないので、４行目が処理される。４行目でＳから仮説が取り出される。４行目で取り出される値は、ｓ＝｛（０，０）｝、ｆ＝ｆａｌｓｅ、ｒ＝εとなる。ｆがｆａｌｓｅなので、処理が１０行目に進み、関数ｅｐｓ＿ｓｈｏｒｔｅｓｔ（０）が実行される。
【０１２２】
関数ｅｐｓ＿ｓｈｏｒｔｅｓｔ（０）の処理では、まず、図５の１行目から３行目で、変数の初期化が行われる。４行目から６行目の処理が完了すると、ｗε［０］＝０、Ψ＝｛０｝となる。８行目で、ｑ＝０、Ψ＝｛｝となる。状態０は９行目の条件を満たすので、１０行目でＱｒ＝｛０｝となる。状態０から状態１への遷移について、１２行目から１５行目までの処理が実行される。１２行目でｗ＝１となる。１３行目の左辺がｗ（＋）ｗε［１］＝１（＋）∞＝ｍｉｎ（１，∞）＝１であり、右辺が∞である。従って、１４行目でｗε［ｎ（ｅ）］＝ｗε［１］＝１となり、１５行目でΨ＝｛１｝となる。同様に、状態０から状態２への遷移について、１２行目から１５行目までの処理が実行される。この結果、ｗε［２］＝２、Ψ＝｛１，２｝となる。
【０１２３】
Ψが空集合ではないので、図５の８行目に戻ってΨから状態が１つ取り出される。ｗε［１］とｗε［２］とを比べると、ｗε［１］の方が小さいので、状態１の優先度が高くなる。従って、まず、状態１が取り出される。状態１には、ε遷移以外の出ていく遷移が存在するので、Ｑｒ＝｛０，１｝となる。状態１から出ていく遷移にε遷移は含まれないので、状態１について、１２行目から１５行目までの処理はされない。
【０１２４】
続いて、Ψが空集合ではないので、図５の８行目に戻ってΨから状態２が取り出される。状態２は９行目の条件を満たすので、１０行目でＱｒ＝｛０，１，２｝となる。状態２から出ていく遷移が存在するので、１２行目から１５行目の処理がされる。この結果、ｗε［３］＝５、Ψ＝｛３｝となる。Ψが空集合ではないので、８行目に戻って状態３が取り出される。状態３は９行目の条件を満たすので、１０行目でＱｒ＝｛０，１，２，３｝となる。状態３に出ていくε遷移は無いので、１２行目から１５行目までの処理がされず、１６行目で結果が返される。
【０１２５】
図４の１０行目で、関数ｅｐｓ＿ｓｈｏｒｔｅｓｔ（０）の結果がｓに代入される。この結果、ｓ＝｛（０，０），（１，１），（２，２），（３，５）｝となる。ｓに含まれる状態に終了状態は存在しないので、ｓｆ＝｛｝となる。
【０１２６】
続いて、入力記号ｂとｃについて、１５行目から１７行目までの処理がされる。まず、ａ＝ｂの場合、１５行目の処理で、ｓａ＝｛（５，２）｝となる。入力記号がｂである出ていく遷移が存在する状態は、状態１のみである。状態１に対応する累積重みは１であるので、状態１から状態５の遷移の重みを、累積重みに加算して１＋１＝２となる。ｓａが空集合ではないので、１７行目で、Ｓ＝｛（｛（５，２）｝，２，ｆａｌｓｅ，ｂ）｝となる。ａ＝ｃの場合、１５行目から１７行目を処理すると、ｓａ＝｛（４，２），（６，４），（７，７）｝となり、Ｓ＝｛（｛（５，２）｝，２，ｆａｌｓｅ，ｂ），（｛（４，２），（６，４），（７，７）｝，４，ｆａｌｓｅ，ｃ｝）｝となる。新たに追加した仮説の２つ目の要素は、（２（×）ｗｐｒｅｄ（４））（＋）（４（×）ｗｐｒｅｄ（６））（＋）（７（×）ｗｐｒｅｄ（７））＝（２＋３）（＋）（４＋０）（＋）（７＋０）＝ｍｉｎ（ｍｉｎ（５，４），７）＝４と計算される。
【０１２７】
Ｓが空集合ではないので、処理が４行目に戻される。４行目では、優先度が高い仮説、すなわち、２つ目の要素が小さい仮説がＳから取り出される。４行目で取り出される値は、ｓ＝｛（５，２）｝，ｆ＝ｆａｌｓｅ，ｒ＝ｂとなる。１０行目では、ｓは変化せず、１１行目では、ｓｆ＝｛（５，２）｝となる。ｓｆが空集合ではないので、１３行目が処理され、Ｓ＝｛（｛（５，２）｝，２，ｔｒｕｅ，ｂ），（｛（４，２），（６，４），（７，７）｝，４，ｆａｌｓｅ，ｃ｝）｝となる。状態５には出ていく遷移は無いので、１４行目から１７行目の処理がされても、なにも起きない。
【０１２８】
続いて、Ｓが空集合ではないので、処理が４行目に戻される。次に、Ｓから取り出された結果は、ｓ＝｛（５，２）｝，ｆ＝ｔｒｕｅ，ｒ＝ｂとなる。６行目では、Ｒ＝｛（１，ｂ）｝となる。Ｎ＝３なので、７行目の条件は満たさない。
【０１２９】
続いて、Ｓが空集合ではないので、処理が４行目に戻される。次に、Ｓから取り出された結果は、ｓ＝｛（４，２），（６，４），（７，７）｝，ｆ＝ｆａｌｓｅ，ｒ＝ｃとなる。状態４、６、７から出ていく遷移にε遷移は無いので、１０行目の処理を行ってもｓは変化しない。１１行目でｓｆ＝｛（６，４），（７，７）｝となる。
【０１３０】
１２行目の条件を満たすので、１３行目で、Ｓ＝｛（｛（６，４），（７，７）｝，４，ｔｒｕｅ，ｃ）｝となる。１４行目から１７行目までの処理がされると、Ｓ＝｛（｛（６，４），（７，７）｝，４，ｔｒｕｅ，ｃ），（｛（７，８），（８，３）｝，５，ｆａｌｓｅ，ｃｃ）｝となる。
【０１３１】
続いて、Ｓが空集合ではないので、処理が４行目に戻される。次に、Ｓから取り出された結果は、ｓ＝｛（６，４），（７，７）｝，ｆ＝ｔｒｕｅ，ｒ＝ｃとなる。６行目でＲ＝｛（１，ｂ），（２，ｃ）｝となる。
【０１３２】
続いて、Ｓが空集合ではないので、処理が４行目に戻される。次に、Ｓから取り出された結果は、ｓ＝｛（７，８），（８，３）｝、ｆ＝ｆａｌｓｅ、ｒ＝ｃｃとなる。状態７と状態８とから出ていく遷移は無いので、１０行目の処理ではｓは変化しない。１３行目で、Ｓ＝｛（｛（７，８），（８，５）｝，５，ｔｒｕｅ，ｃｃ）｝となる。状態７と状態８とから出ていく遷移は無いので、１４行目から１７行目の処理では何も起きない。
【０１３３】
続いて、Ｓが空集合ではないので、処理が４行目に戻される。次に、Ｓから取り出された結果は、ｓ＝｛（７，８），（８，５）｝、ｆ＝ｔｒｕｅ、ｒ＝ｃｃとなる。６行目でＲ＝｛（１，ｂ），（２，ｃ），（３，ｃｃ）｝となる。｜Ｒ｜＝３なので７行目の条件を満たし、結果を８行目で返す。
【０１３４】
最後に、図３のステップＳ１０４で結果を出力する。探索装置１０は、画面に処理結果を表示してもよいし、次段の装置に処理結果を渡してもよい。
【０１３５】
（ハードウェア構成）
図７は、実施形態に係る探索装置１０のハードウェアブロック図である。探索装置１０は、ＣＰＵ（Central  Processing  Unit）１０１と、操作部１０２と、表示部１０３と、マイクロフォン１０４と、ＲＯＭ（Read  Only  Memory）１０５と、ＲＡＭ（Random  Access  Memory）１０６と、記憶部１０７と、通信装置１０８と、バス１０９とを備える。各部は、バス１０９により接続される。
【０１３６】
ＣＰＵ１０１は、ＲＡＭ１０６の所定領域を作業領域としてＲＯＭ１０５または記憶部１０７に予め記憶された各種プログラムとの協働により各種処理を実行し、探索装置１０を構成する各部の動作を統括的に制御する。また、ＣＰＵ１０１は、ＲＯＭ１０５または記憶部１０７に予め記憶されたプログラムとの協働により、操作部１０２、表示部１０３、マイクロフォン１０４および通信装置１０８等を実現させる。
【０１３７】
操作部１０２は、マウスやキーボード等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をＣＰＵ１０１に出力する。
【０１３８】
表示部１０３は、ＬＣＤ（Liquid  Crystal  Display）等の表示装置である。表示部１０３は、ＣＰＵ１０１からの表示信号に基づいて、各種情報を表示する。例えば、表示部１０３は、探索装置１０が出力する入力記号列を表示する。なお、通信装置１０８または記憶部１０７等に入力記号列を出力する場合には、探索装置１０は、表示部１０３を備えなくてもよい。マイクロフォン１０４は、音声信号を入力するデバイスである。探索装置１０が処理するＷＦＳＡが記憶部１０７に記録されている場合や通信装置から入力される場合には、マイクロフォン１０４は備えなくてもよい。
【０１３９】
ＲＯＭ１０５は、探索装置１０の制御に用いられるプログラムおよび各種設定情報等を書き換え不可能に記憶する。ＲＡＭ１０６は、ＳＤＲＡＭ（Synchronous  Dynamic  Random  Access  Memory）等の揮発性の記憶媒体である。ＲＡＭ１０６は、ＣＰＵ１０１の作業領域として機能する。具体的には、探索装置１０が用いる各種変数およびパラメータ等を一時記憶するバッファ等として機能する。
【０１４０】
記憶部１０７は、フラッシュメモリ等の半導体による記憶媒体、磁気的または光学的に記録可能な記憶媒体等の書き換え可能な記録装置である。記憶部１０７は、探索装置１０の制御に用いられるプログラムおよび各種設定情報等を記憶する。また、記憶部１０７は、ＷＦＳＡに係る各種の情報、および、出力される入力記号列等を記憶する。なお、探索装置１０が備える有向グラフ記憶部２２、最良経路重み記憶部２３および仮説記憶部２４は、ＲＯＭ１０５、ＲＡＭ１０６および記憶部１０７の何れにより実現されてもよい。
【０１４１】
通信装置１０８は、外部の機器と通信して、ＷＦＳＡ等の入力および入力記号列の出力等に用いられる。予め記録されたＷＦＳＡを用いる場合であり、入力記号列を表示部１０３または記憶部１０７に出力する場合には、探索装置１０は、通信装置１０８を備えなくてもよい。
【０１４２】
本実施形態の探索装置１０で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１４３】
また、本実施形態の探索装置１０で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施形態の探索装置１０で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、本実施形態の探索装置１０で実行されるプログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１４４】
本実施形態の探索装置１０で実行されるプログラムは、上述した探索装置１０の各部（取得部２１、有向グラフ記憶部２２、最良経路重み記憶部２３、仮説記憶部２４、取出部２５、出力部２６および仮説展開部２７）を含むモジュール構成となっており、ＣＰＵ１０１（プロセッサ）が記憶媒体等からプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、探索装置１０（取得部２１、有向グラフ記憶部２２、最良経路重み記憶部２３、仮説記憶部２４、取出部２５、出力部２６および仮説展開部２７）が主記憶装置上に生成されるようになっている。なお、探索装置１０の一部または全部がハードウェアにより構成されていてもよい。
【０１４５】
（効果）
以上のように、本実施形態に係る探索装置１０は、対象仮説が保持する１以上の状態のそれぞれから出ていく遷移に空遷移が含まれる場合、当該状態から空遷移を辿って到達する状態を対象仮説に追加した後に、探索を進めて新たな１以上の仮説を生成する。これにより、本実施形態に係る探索装置１０によれば、初期状態から終了状態までの累積した重みが最良の経路から順に、重複する入力記号列を含まないＮ個の入力記号列を見つけ出すことができる。
【０１４６】
（パターン認識装置）
図８は、実施形態に係るパターン認識装置５０の構成を示す。以下、実施形態に係るパターン認識装置５０を説明する。
【０１４７】
パターン認識装置５０は、入力された信号のパターンを認識し、Ｎ個の記号列を認識結果として出力する。パターン認識装置５０に入力される信号は、パターンを表す信号であればどのような信号であってもよい。入力される信号は、一例として、音声信号、筆跡を表す信号、文字を表す画像信号または手話等のジェスチャを表す動画像信号等である。
【０１４８】
パターン認識装置５０は、特徴抽出部５１と、デコーダ５２と、探索装置１０とを備える。
【０１４９】
特徴抽出部５１は、パターンを表す信号を入力して、一定時間毎に、信号の特徴量を取得する。そして、特徴抽出部５１は、取得した信号の特徴量をデコーダ５２に渡す。なお、特徴量は、複数の値から構成される場合もある。この場合、複数の特徴量の組は、特徴ベクトルと呼ばれる。本実施形態では、複数の値から構成される場合も含めて特徴量と呼ぶ。
【０１５０】
特徴量は、その信号の区間毎の特徴を表す情報であり、デコーダ５２が信号スコアを算出するために用いられる。音声信号を入力する場合、特徴抽出部５１は、一例として、１０ミリ秒単位（フレーム）毎に、特徴量を取得する。
【０１５１】
デコーダ５２は、特徴抽出部５１から特徴量が入力される毎に、パターンを特定するために必要となる各種モデルを用いてパターン認識を行う。そして、デコーダ５２は、認識結果をＷＦＳＡとして出力する。なお、デコーダ５２から出力されるＷＦＳＡは、ラティスと呼ばれる場合もある。
【０１５２】
探索装置１０は、図１から図７を参照して説明した装置であり、詳細な説明を省略する。探索装置１０は、デコーダ５２からＷＦＳＡを取得する。また、探索装置１０は、デコーダ５２から、ＷＦＳＡのそれぞれの状態について、その状態から終了状態までに至る最良の経路の重みを取得する。
【０１５３】
デコーダ５２は、モデルに含まれる経路のうち重みが良い経路を見つける処理を行う過程で、デコーダ５２の処理の開始状態からそれぞれの状態に至る経路の重みを計算する。デコーダ５２の処理の開始状態を終了状態とし、デコーダ５２の処理が完了した状態を初期状態とするＷＦＳＡをデコーダ５２が生成するようにデコーダ５２を構成すれば、探索装置１０は、それぞれの状態から終了状態までの最良経路の重みを別途計算することなく得ることができる。なぜなら、デコーダ５２により、処理の開始状態からそれぞれの状態までの最良経路の重みが計算済みであるからである。この場合、探索装置１０に入力されるＷＦＳＡの遷移の向きは、デコーダ５２が入力される特徴量の順序とは逆向きとなる。つまり、後から入力された特徴量に対応する入力記号ほどＷＦＳＡの初期状態に近い遷移に割り当てられることになる。そこで、入力記号列を出力する直前に入力記号列の並びを反転するように探索装置１０を構成してもよい。
【０１５４】
そして、探索装置１０は、最良の経路から順にＮ個の入力記号列を、重複無しに出力する。
【０１５５】
パターン認識の一つとして音声認識を例に挙げる。この場合、特徴抽出部５１が入力する信号は、音声信号である。デコーダ５２が用いるモデルは、音響モデル、単語辞書および言語モデル等である。音声信号を処理してラティスを出力するデコーダ５２については、例えば、非特許文献１に記載されている。
【０１５６】
パターン認識装置５０は、記憶装置に記録された音声信号、マイクロフォン１０４が収集した音声信号、および、通信装置１０８から受信した音声信号等を取得することができる。デコーダ５２が出力するラティスは、例えば、単語ラティスまたは音素ラティス等である。単語ラティスをＷＦＳＡとして処理する場合、ＷＦＳＡの入力記号は単語となる。また、音素ラティスをＷＦＳＡとして処理する場合、ＷＦＳＡの入力記号は音素となる。
【０１５７】
なお、手書き文字のパターン認識を行う場合には、パターン認識装置５０は、筆跡信号をパターン信号として出力する筆跡入力装置をさらに備える。また、ＯＣＲ（Optical  Character  Recognition）を行う場合には、パターン認識装置５０は、画像信号をパターン信号として取り込むスキャナまたはカメラ等をさらに備える。また、ジェスチャ認識、手信号の認識または手話認識を行う場合には、パターン認識装置５０は、動画像信号をパターン信号として取り込むビデオカメラをさらに備える。これらの場合、音声信号は不要であるので、マイクロフォン１０４は備えなくてもよい。
【０１５８】
（処理フロー）
図９は、実施形態に係るパターン認識装置５０の処理順序を示すフローチャートである。まず、信号の入力が開始されると、ステップＳ２０１において、パターン認識装置５０は、信号を取得する。
【０１５９】
続いて、ステップＳ２０２において、特徴抽出部５１は、取得した信号から特徴量を抽出してデコーダ５２に供給する。続いて、ステップＳ２０３において、デコーダ５２は、モデルを探索して、特徴量に対応するＷＦＳＡを生成する。
【０１６０】
続いて、ステップＳ２０４において、探索装置１０は、ＷＦＳＡを探索して、最良経路から順にＮ個の入力記号列を見つけ出す。そして、ステップＳ２０５において、パターン認識装置５０は、見つけ出したＮ個の入力記号列を認識結果として出力する。
【０１６１】
なお、パターン認識装置５０は、図７に示した構成と同様のハードウェア構成により実現される。また、パターン認識装置５０は、図７に示した構成と同様のハードウェア構成がプログラムを実行することにより、実現されてもよい。パターン認識装置５０で実行されるプログラムは、特徴抽出部５１、デコーダ５２および探索装置１０を含むモジュール構成となっており、ＣＰＵ１０１（プロセッサ）が記憶媒体等からプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、パターン認識装置５０（特徴抽出部５１、デコーダ５２および探索装置１０）が主記憶装置上に生成されるようになっている。なお、パターン認識装置５０の一部または全部がハードウェアにより構成されていてもよい。
【０１６２】
以上のような実施形態に係るパターン認識装置５０は、図１から図７を参照して説明した探索装置１０を用いてＮ個の記号列を認識結果として出力することができる。これにより、パターン認識装置５０によれば、認識結果として、重複しないＮ個の記号列を出力することができる。
【０１６３】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１６４】
１０  探索装置
２１  取得部
２２  有向グラフ記憶部
２３  最良経路重み記憶部
２４  仮説記憶部
２５  取出部
２６  出力部
２７  仮説展開部
３１  空遷移処理部
３２  終了生成部
３３  仮説生成部
５０  パターン認識装置
５１  特徴抽出部
５２  デコーダ
１０１  ＣＰＵ
１０２  操作部
１０３  表示部
１０４  マイクロフォン
１０５  ＲＯＭ
１０６  ＲＡＭ
１０７  記憶部
１０８  通信装置
【図１】
2015121708.tif 000004
【図２】
2015121708.tif 000005
【図３】
2015121708.tif 000006
【図４】
2015121708.tif 000007
【図５】
2015121708.tif 000008
【図６】
2015121708.tif 000009
【図７】
2015121708.tif 000010
【図８】
2015121708.tif 000011
【図９】
2015121708.tif 000012