入力信号から抽出された特徴パラメータと、認識パタンが木構造で表現された確率的な状態遷移モデルとを照合し、前記特徴パラメータに対する確率モデルの各状態の尤度を計算しながら状態仮説を遷移させ、最尤な状態遷移パスを認識パタンとするパタン認識装置において、入力信号の特徴パラメータに基づいて、前記状態遷移モデルの探索空間で尤度計算を実行する探索手段と、前記探索空間を、確率モデルの状態から分岐して終端の状態に到達するパタン総数に基づいて、仮想的に複数の領域に分割する領域分割手段と、同一時刻で遷移する状態仮説を前記分割された領域のいずれかに振り分ける状態仮説振分手段と、前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域別枝刈り手段とを具備したことを特徴とするパタン認識装置。前記分割された領域ごとに枝刈り条件を設定する枝刈り条件設定手段をさらに含むことを特徴とする請求項1に記載のパタン認識装置。前記領域分割手段は、探索空間を、各状態が当該状態以降に分岐して終端の状態に到達するパタン総数に基づいて分割することを特徴とする請求項1または2に記載のパタン認識装置。前記枝刈り条件設定手段は、分岐するパタン総数が少ない領域ほど枝刈り条件を厳しくすることを特徴とする請求項3に記載のパタン認識装置。前記領域分割手段は、木構造の各根から分岐するパタン総数が当該各根の種類に応じて特異的な探索空間を当該根ごとに分割することを特徴とする請求項1または2に記載のパタン認識装置。前記枝刈り条件設定手段は、パタン総数が少ない領域ほど枝刈り条件を厳しくすることを特徴とする請求項5に記載のパタン認識装置。音声信号からフレーム単位で音響特徴パラメータを抽出する音響分析手段をさらに含み、前記音響特徴パラメータに基づいて音声認識を行うことを特徴とする請求項1ないし6のいずれかに記載のパタン認識装置。コンピュータが、入力信号から抽出された特徴パラメータと、認識モデルが木構造で表現された確率的な状態遷移モデルとを照合し、前記特徴パラメータに対する確率モデルの各状態の尤度を計算しながら状態仮説を遷移させ、最尤な状態遷移パスを認識パタンとするパタン認識方法において、コンピュータが、入力信号の特徴パラメータに基づいて、前記状態遷移モデルの探索空間で尤度計算を実行する手順と、コンピュータが、前記探索空間を、確率モデルの状態から分岐して終端の状態に到達するパタン総数に基づいて、仮想的に複数の領域に分割する手順と、コンピュータが、同一時刻で遷移する状態仮説を前記いずれかの領域に振り分ける手順と、前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域枝刈り手順とを含むことを特徴とするパタン認識方法。前記請求項8に記載のパタン認識方法を、コンピュータに実行させるためのパタン認識プログラム。前記請求項9に記載したパタン認識プログラムをコンピュータが読み取り可能に記憶した記録媒体。枝刈りの目的は、最終的に最尤となるパスを見いだせるように、木構造辞書の広い探索空間を少ない状態仮説で効率的に探索することである。上記した従来の枝刈り方法では、木構造辞書の一部の領域に状態仮説が集中して残り、それ以外の広い領域に状態仮説が残らないことがあり、これでは効率的な探索が行われているといえない。上記した従来技術Aに属する改良手法を適用しても、上記の問題は根本的に解決されない。従来技術Bに属する技術では、複数の音響モデルを併用する場合の枝刈りが効率化されるものの、単一の木構造辞書における枝刈りを効率化できない。本発明の目的は、上記した従来技術の課題を解決し、単一の木構造辞書であっても、木構造辞書の構造的な特徴を生かして、認識率を低下させることなく、状態仮説を効率良く枝刈りできるパタン認識方法および装置ならびにパタン認識プログラムおよびその記録媒体を提供することにある。上記の目的を達成するために、本発明は、入力信号から抽出された特徴パラメータと、認識パタンが木構造で表現された確率的な状態遷移モデルとを照合し、特徴パラメータに対する確率モデルの各状態の尤度を計算しながら状態仮説を遷移させ、最尤な状態遷移パスを認識パタンとするパタン認識装置において、以下のような構成を具備した点に特徴がある。入力信号の特徴パラメータに基づいて、前記状態遷移モデルの探索空間で尤度計算を実行する探索手段と、前記探索空間を、確率モデルの状態から分岐するパタン総数に基づいて、仮想的に複数の領域に分割する領域分割手段と、同一時刻で遷移する状態仮説を前記分割された領域のいずれかに振り分ける状態仮説振分手段と、前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域別枝刈り手段とを設けた。分割された領域ごとに枝刈り条件を設定する枝刈り条件設定手段をさらに設けた。上記の特徴によれば、状態遷移モデルの探索空間が、分岐するパタン総数に基づいて複数の領域に分割され、領域ごとに独立して枝刈りが実行されるので、分岐するパタン総数が多い領域と少ない領域とで独立して累積尤度が上位の状態仮説を残すことができる。したがって、一の領域に属する各状態仮説の累積尤度が他の一の領域に属する各状態仮説の累積尤度よりも相対的に高く、一の領域と他の一の領域とを分割せずに一括して枝刈りしたときには累積尤度が上位とならない他の一の領域の状態仮説も、領域ごとに枝刈りを行うことにより残すことが可能になる。上記の特徴によれば、状態遷移モデルの探索空間を、各状態から分岐するパタン総数に基づいて複数の領域に分割できるので、分岐するパタン総数が多い領域よりも少ない領域を厳しく枝刈りすれば、パタン総数を抑えながら、将来的に多数のパタンが分岐する状態仮説を確実に残せるようになり、その結果、認識率を低下させることなく、状態仮説をさらに効率良く枝刈りできるようになる。以下、図面を参照して本発明の基本的な概念について説明する。ここでは初めに、図1に示した音素列aで始まる地名の木構造辞書を例にして説明する。音素列aiで始まる地名のうち、音素列aioで始まる地名は相生に限定されるので、状態仮説が音素列aioの探索空間を過ぎれば単語パタンが確定する。同様に、音素列aikaで始まる地名は秋鹿町、相川および愛環梅坪の3つであるが、音素列aikamで始まる地名は秋鹿町に限定されるので、状態仮説が音素列aikamの探索空間を過ぎれば単語が確定する。ここで、ある時刻で自己遷移またはLR遷移した全N1個の状態仮説を対象に枝刈りを行うとき、従来技術であれば、N1個の全ての状態仮説を対象に枝刈りが行われ、ビーム幅や最大許容仮説数で決まる上位n1個の状態仮説のみが残る。このとき、状態仮説が多くの単語に到達する可能性を残すためには、探索空間の広い範囲にわたって、その状態仮説が上位n1個の中に漏れなく残るようにすることが望ましい。しかしながら、実際には単語が確定する領域の状態仮説のみが上位を占めてしまうような場合があり、このような場合には、多くの単語に到達する可能性が一度に失われてしまう。これに対して、探索空間を、例えば単語が確定される領域と単語が確定されない領域とに分割し、各領域において別々に枝刈りを行い、領域ごとに上位の状態仮説を残せば上記したような技術課題を解決できる。すなわち、同一時刻で自己遷移またはLR遷移した全N1個の状態仮説のうち、一方の領域にある全N2個の状態仮説のみを対象に枝刈りを行って、その上位n2個の状態仮説を残すと共に、これとは別に、他方の領域にある全N3個の状態仮説を対象に枝刈りを行って、その上位n3個の状態仮説を残す。このようにすれば、探索空間の一部領域のみに状態仮説が偏在することが無くなるので、認識率を低下させることなく全体の状態仮説数を削減できるようになる。本発明では、このような考察に基づいて、探索空間を複数の領域に分割し、領域ごとに、同一領域内で同一時刻に遷移する状態仮説間で尤度を計算し、尤度の低い状態仮説を枝刈りすることによって、認識率を低下させることなく全体の状態仮説数を削減できるようにしている。図2は、本発明のパタン認識方法を適用した音声認識装置の主要部の構成を示したブロック図である。音声信号入力部11は、入力された音声信号をデジタル信号に変換する。音響分析部12は、音声デジタル信号を音響分析して音響特徴パラメータを抽出し、これをパラメータ記憶部13に記憶する。音響特徴パラメータとは、入力音声を一定時間間隔例えば10ms:以下、フレームと表現する毎に分析して得られる特徴ベクトルである。したがって、音声信号は特徴ベクトルの系列X=x1x2...xTに変換される。探索データベース14には、探索用の文法および木構造辞書音素モデルの確率的な状態遷移モデルが予め記憶されている。音響モデルデータベース17には、予め作成された音響モデルが登録されている。探索部15は、前記探索用の文法、木構造辞書および音響モデルに音響特徴パラメータの時系列データを照合させて音響的な尤度を算出し、この尤度を時間方向に累積して累積尤度を求める尤度計算部151と、探索過程で各状態仮説を自己遷移させる自己遷移部152およびLR遷移させるLR遷移部153と、探索過程で尤度の低い状態仮説を探索対象から除外する枝刈り部154と、単語末尾まで進んだ状態仮説の単語仮説を出力する単語仮説出力部155とを含む。なお、文法の制約から木構造辞書の状態系列が複数に枝分れする場合、探索部15は枝の数だけ状態仮説を複製し、枝ごとに状態仮説を進行させて尤度を計算する。認識結果判定部16は、文法上の最後のHMM状態まで到達した全ての状態仮説を累積尤度に基づいてソートし、累積尤度が最も高い状態系列にバックトレースを実行して認識結果を判定する。図3は、前記枝刈り部154の主要部の構成を示した機能ブロック図であり、状態遷移モデルの探索空間を複数の領域に分割する領域分割部154aと、同一時刻で遷移する状態仮説を前記分割された領域のいずれかに振り分ける状態仮説振り分け部154bと、前記分割された各領域の枝刈り条件を設定する枝刈り条件設定部154cと、前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域別枝刈り部154dとを含む。前記領域別枝刈り部154dは、実用時間内での処理が可能ならば、一つの枝刈り部で領域ごとに枝刈りを繰り返すようにしても良いし、複数の枝刈り部を設けて、これらで並列的に枝刈りを行うようにしても良い。図4は、本発明のパタン認識方法を適用した音声認識の手順を示したフローチャートであり、主に前記探索部15の動作を示している。ここでは、音声信号入力部11に入力された認識対象の音声信号が音響分析部12でフレームごとに音響分析され、各フレームの音響特徴パラメータがパラメータ記憶部13に蓄積されている状態から説明を始める。また、前記領域分割部154aにより、図1に示したように、探索空間が、分岐するパタン数が少ない単語確定領域および多い単語未確定領域に分割されているものとする。ステップS1では、探索処理の初期化として、文法の先頭の単語の先頭の状態に遷移する仮想的な状態仮説が設定される。ステップS2では、前記パラメータ記憶部13に記憶されている音響特徴パラメータが、記音声区間の先頭フレームから正順で取り込まれる。ステップS3では、有効な状態仮説の一つが今回の計算対象として選択される。ステップS4では自己遷移が実施され、その尤度が計算更新される。ステップS5では、今回のタイミングに対応した全ての状態仮説に関して自己遷移および尤度計算が完了したか否かが判定される。完了していなければステップS3へ戻り、今回のタイミングで遷移すべき他の状態仮説についても上記した各処理が繰り返される。今回のタイミングに対応した全ての状態仮説に関して自己遷移および尤度計算が完了するとステップS6へ進み、改めて今回のタイミングに対応した有効な状態仮説の一つが計算対象として選択される。ステップS7では各状態仮説がLR遷移される。ステップS8ではViterbi探索が実行される。ステップS9では、今回のタイミングで遷移すべき全ての状態仮説に関して、上記したLR遷移およびViterbi探索が完了したか否かが判定される。完了していなければステップS6へ戻り、今回のタイミングで遷移すべき他の状態仮説についても上記した各処理が繰り返される。その後、今回のタイミングで遷移すべき全ての状態仮説について上記した各処理が完了するとステップS10へ進み、領域ごとに枝刈りを独立して行う領域別枝刈り処理が実行される。図5は、前記領域別枝刈り処理の手順を示したフローチャートであり、ステップS101では、今回のタイミングに対応した有効な状態仮説の一つが計算対象として選択される。ステップS102では、前記選択された今回の状態仮説がいずれかの領域に振り分けられる。ステップS103では、全ての状態仮説に関して前記振り分けが完了したか否かが判定され、完了していなければ、ステップS101へ戻って上記した振り分け処理が繰り返される。その後、全ての状態仮説がいずれかの領域に振り分けられると、ステップS104では、分割された領域の一つが、今回の枝刈り領域として選択される。ステップS105では、領域内の全ての状態仮説の累積尤度に基づいて枝刈り条件が設定される。ステップS106では、領域内の状態仮説の一つが今回の枝刈り対象として選択される。ステップS107では、累積尤度が前記枝刈り条件よりも高い状態仮説のみを残して他の状態仮説を次の探索から除外する枝刈りが行われる。本実施形態では、時刻t、状態jの各尤度αjを、探索空間の領域ごとに全状態仮説の中で最大の尤度αmaxと比較し、次式を満足する状態仮説を次の時刻の探索空間に残し、次式を満足する状態仮説を次の時刻の探索空間から除外する。θpruningはビーム幅であり、前記枝刈り条件設定部154cは、領域ごとに同一のビーム幅を設定しても良いし、あるいは異なるビーム幅を設定しても良い。なお、上記のように探索空間を、分岐するパタン数が少ない単語確定領域と多い単語未確定領域とに分割するのであれば、単語確定領域の枝刈り条件を単語未確定領域の枝刈り条件よりも厳しくすることにより、認識率を低下させることなく、状態仮説を効率良く枝刈りできるようになる。ステップS108では、今回の領域内の全ての状態仮説に関して上記した処理が完了したか否かが判定され、完了していなければ、ステップS106へ戻って状態仮説を変更しながら上記した各処理が繰り返される。ステップS109では、全ての領域に関して上記した処理が完了したか否かが判定され、完了していなければステップS104へ戻り、領域を変更しながら上記した各処理が繰り返される。図4へ戻り、ステップS11では、枝刈り後に残った状態仮説の一つが選択される。ステップS12では、選択された状態仮説が単語末尾の状態仮説であるか否かが判定され、単語末尾の状態仮説であれば、ステップS13へ進んで単語仮説が出力される。ステップS14では、文法の上の次の単語の先頭の状態に遷移する仮想的な状態仮説が設定される。ステップS15では、枝刈り後に残った全ての状態仮説に関して上記した処理が完了したか否かが判定される。完了していなければ前記ステップS11へ戻り、状態仮説を変更しながら上記した各処理が繰り返される。ステップS16では、次フレームの有無が判定され、次フレームが存在すればステップS2へ戻って次フレームの音響特徴パラメータを取り込んで上記した各処理が繰り返される。全てのフレームに関して上記した各処理が終了して探索が文末フレームまで到達すると、ステップS17では、これまでに文法上の最後のHMM状態まで到達した全ての状態仮説が、その累積尤度の昇順にソートされる。ステップS18では、累積尤度が上位の複数または唯一の状態仮説にバックトレースが実施され、認識結果が出力される。なお、上記の実施形態では、本発明を状態仮説がビーム幅に基づいて枝刈りされる場合を例にして説明したが、本発明はこれのみに限定されるものではなく、状態仮説の累積尤度をヒストグラム化し、最大許容仮説数に基づいて枝刈りする場合にも同様に適用できる。また、上記した実施形態では、本発明を音声認識を例にして説明したが、ゲノム解析におけるタンパク質配列の探索など、他のパタン認識にも同様に適用できる。さらに、上記の実施形態では探索空間を、分岐するパタン数が少ない単語確定領域および分岐するパタン数が多い単語未確定領域に2分割し、領域ごとに独立して枝刈りを実行するものとして説明したが、本発明はこれのみに限定されるものではなく、探索空間を分岐するパタン数に応じて複数分割できるならば、以下のような規則の一つまたは複数の組み合わせに基づいてに分割しても良い。図6に示したように、探索空間を、各HMM状態が当該状態以降に分岐して終端の状態に到達するパタンの総数ごとに分割する。このとき、領域ごとに枝刈り条件を異ならせるのであれば、パタン総数が少ない領域ほどビーム幅を狭めて枝刈り条件を厳しくすることが望ましい。図示した例では、第1領域から分岐するパタン総数は7個であり、第2領域から分岐するパタン総数は3個であり、第3領域から分岐するパタン総数は4個である。したがって、ビーム幅や最大許容仮説数が第1領域>第3領域>第2領域となり、第2領域の枝刈り条件が最も厳しくなる。図7に示したように、探索空間を木構造辞書の根の種類ここでは、単語先頭の音素に基づいて当該根ごとに複数の領域に分割する。このとき、領域ごとに枝刈り条件を異ならせるのであれば、各グループを同一領域としてグループごとにビーム幅を設定することが望ましい。このような分割方法は、木構造辞書の根の内容に応じて、その後に分岐するパタン総数が特異的であるような場合に有効である。