JPH11282488A - マッチング方法及び装置及び記憶媒体 - Google Patents

Abstract

(57)【要約】 【課題】 マッチング処理の精度を維持しながら、成長
する可能なマッチングの数を効果的に減少させるため
の、より効果的な刈り込み技術を提供する。 【解決手段】第１の信号を表わす第１信号パターン列と
第２の信号を表わす第２信号パターン列とをマッチング
させる方法及び装置が提供される。システムは複数の異
なる刈り込み閾値（ｔｈ）を用いて、第２信号パターン
の列と処理中の現第１信号パターンまでの第１信号パタ
ーンの列との間の可能なマッチングを表わすパスの成長
を制御する。特に、与えられたパスに対して該現第１信
号パターンの処理の間に用いられる刈り込み閾値は、第
２の信号を表わすパターン列内における、処理中の現第
１信号パターンに対して得られたパスが終端とする第２
信号パターンの位置に依存する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、パターンマッチン
グ方法および装置に関する。本発明は特に、これに限ら
れるものではないが、動的計画法によるマッチング技術
において用いられる刈り込み閾値の調整に関するもので
ある。典型的な実施形態においては、動的計画法による
パターンマッチング技術が音声認識システムに用いられ
る。

【０００２】

【従来の技術】音声認識は、未知の発声を特定する処理
である。現在、いくつかの異なるタイプの有用な音声認
識システムがあり、いくつかの方法でカテゴリに分類さ
れている。たとえば、いくつかのシステムは話者依存型
であり、他は話者非依存である。いくつかのシステム
は、大量の語彙（＞１００００語）を用いて稼動し、他
のものは限定された語彙量（＜１０００語）で稼動す
る。いくつかのシステムは独立した語を認識することの
みが可能であり、他のシステムは接続された一連の語を
含むフレーズを認識できる。

【０００３】語彙の限定されたシステムでは、音声認識
は未知の発声の特徴と、データベースに格納された既知
の語の特徴を比較することにより実行される。既知の語
の特徴は学習（トレーニング）セッションの間に決定さ
れる。この学習セッションでは、１つあるいは複数の既
知の語が、それらに対する基準パターンを生成するのに
用いられる。

【０００４】未知の発声を認識するために、音声認識装
置はその発声からパターン（あるいは特徴）を抽出し、
データベースに格納された各基準パターンと比較する。
入力発声を表わすパターンを基準パターンと比較する一
つの方法は、動的計画法を用いることであり、これは基
準パターンの各々と未知の発声から抽出されたパターン
との間の最適な時間的配列を提供する。これは、パター
ンのペア間における最適なマッチングが得られるまで、
一方のパターンの時間軸を局所的に縮めたり伸ばしたり
することで達成される。最良のマッチングを提供する基
準パターンもしくは基準パターン列が、入力発声に最も
よく対応しそうな単語或いは単語列を特定する。

【０００５】動的計画法によるマッチング技術における
一つの問題は、入ってくる発声と各基準モデルとの間の
多くの可能なマッチングに関して判定することを含むた
め、計算的に高価となる（多くの計算時間を費やす）こ
とである。

【０００６】マッチング処理の間、各可能なマッチング
には、そのマッチングの近さに依存するスコアが与えら
れる。動的計画法によるマッチング技術において必要と
なる計算量を制限するための一つの方法は、悪いスコア
を有するマッチングに関する処理を止めることである。
音声認識の技術分野において、この技術は刈り込み（pr
uning）として知られている。しかしながら、刈り込み
技術を用いることの問題は、いくつかの可能なマッチン
グは無視し得ないほどに変化し、利用可能な固定された
メモリ量に対して、メモリのオーバーフローが生じる可
能性があることである。

【０００７】ＥＰ−Ａ−０５２５６４０（富士通
（株））は、各時点において処理される可能なマッチン
グの数が所定の最小値及び最大値の間にあるように閾値
を変化させることにより、この問題を解決する。特に、
次の時点において処理されなければならないであろう可
能なマッチングの数を予想し、その予想された数に依存
して刈り込み閾値が変化される。ここで、予想数は、現
時点で処理されていた可能なマッチングの数と、先行す
る時点で処理された可能なマッチングの数の線形外挿法
により得られる。ＥＰ−Ａ−０５２５６４０において用
いられている処理は、与えられた閾値に対する可能なマ
ッチングの数をカウントし、満足な状態となるまでその
閾値を調整することにより、各時点の実際の可能なマッ
チングの数が与えられた最少及び最大数の範囲に入るこ
とを確実にする。

【０００８】また、ＥＰ−Ａ−０７８９３４８は、刈り
込み閾値を調整するための類似のシステムを開示する。
ただし、このシステムでは、次の時点で処理されること
になるであろう可能なマッチングの数を見積もるのでは
なく、現時点まで延びているパスを次の時点へ成長させ
るための動的計画法の制約を用い、次の時点へ成長し、
破棄されなかった動的計画法パスの数をカウントする。

【０００９】

【発明が解決しようとする課題】本発明は、マッチング
処理の精度を維持しながら、成長する可能なマッチング
の数を効果的に減少させるための、より効果的な刈り込
み技術を提供することを目的とする。

【００１０】

【課題を解決するための手段】本発明の一態様によれ
ば、以下のパターンマッチング方法が提供される。すな
わち、第１の信号を表わす第１信号パターン列と第２の
信号を表わす第２信号パターン列とをマッチングさせる
方法であって、前記第１の信号と前記第２の信号をマッ
チング処理を用いてマッチングし、該マッチング処理は
各第１信号パターンを順次に処理して複数のパスを成長
させ、各パスは第２信号パターンの列と第１信号パター
ンの列との間の可能なマッチングを表わし、各パスは夫
々にそのマッチングの近さを表わす累積値を有し、第１
信号パターンの各々の処理の間に前記累積値を刈り込み
値と比較し、該比較ステップの結果に基づいてパスを破
棄することにより、前記マッチングを制御し、現第１信
号パターンの処理の間の前記制御ステップにおいて複数
の異なる刈り込み値が用いられ、与えられたパスに対し
て該現第１信号パターンの処理の間に用いられるその刈
り込み値は、前記第２の信号を表わすパターン列内にお
ける、処理中の現第１信号パターンに対して与えられた
パスが終端とする第２信号パターンの位置に依存する。

【００１１】このように、異なる刈り込み閾値を用いる
ことにより、システムの精度を保ちながら、各時点で成
長するパスの数を減少することができる。特に、これ
は、最良のパスと局所的な最小値の間の差が、最良のパ
スが第２信号の最初のいくつかのパターンを横切るとき
に最大となる傾向にあることが観察されるからである。

【００１２】好ましくは、柔軟な刈り込み技術が実行さ
れ、それにより対応する刈り込み値よりも悪い累積値を
有するいくつかのパスが破棄されずに残る。このこと
は、最良のパスが刈り出された場合に、その最良のパス
に近いスコアを有するであろう隣接するパスが刈り込ま
れずに維持されるという利益をもたらす。従って、たと
え最良のパスが刈り出されても、その最良のパスに十分
に近いパスは保持され、刈り込みの処理が認識エラーの
原因となることを防止する。

【００１３】

【発明の実施の形態】以下、添付の図面を参照して本発
明の好適な実施形態を説明する。

【００１４】本発明の実施形態は、コンピュータハード
ウエアにおいて実現され得るが、以下に記載される実施
形態では、パーソナルコンピュータ、ワークステーショ
ン、複写機、ファクシミリ装置等のような処理ハードウ
エアに関連して稼動されるソフトウエアにおいて実現さ
れる場合を説明する。

【００１５】図１は、本発明の実施形態を実現させるべ
くプログラムされたパーソナルコンピュータ（ＰＣ）１
を示す。キーボード３、ポインティングデバイス５、マ
イク７及び電話回線９がインターフェース１１を介して
接続されている。キーボード３とポインティングデバイ
ス５はユーザによるシステムのコントロールを可能とす
るものである。マイク７はユーザの音響的な音声信号を
装置上の電気信号に変換し、これを処理のためにＰＣ１
に提供する。この実施形態において、処理すべき入力音
声の始点と終点は入力発声の間キーボード３のスペース
キーを押下しておくことにより、ユーザによって特定さ
れる。このような方法を用いた場合、システムは処理す
べく特定された入力発声を処理するだけである。なお、
内蔵モデムと音声受信回路（不図示）が、遠隔のコンピ
ュータもしくは遠隔のユーザと通信できるように電話回
線９に接続されてもよい。

【００１６】なお、本発明に従ってＰＣ１を稼動させる
ためのプログラムの命令（プログラムコード）は、磁気
ディスク１３のような格納デバイスからＰＣ１による実
行のためにＰＣ１に供給されてもよいし、電話回線１９
を介して遠隔コンピュータと通信する内部モデムを介し
て供給されてもよい。

【００１７】以下、図２を参照して、本実施形態による
限定語彙連続音声認識システムの動作を説明する。例え
ば、マイク７から入力された音声を表す電気信号は、プ
リプロセッサ１５に入力される。プリプロセッサ１５は
入力音声信号をパラメータフレームのシーケンスに変換
する。ここで、各パラメータフレームは、入力音声信号
に対応する時間フレームを表す。各パラメータフレーム
におけるパラメータは典型的には、ケプストラル（ceps
tral）係数と、パワー／エネルギー係数とを含み、これ
らは入力音声信号の特徴を表す重要な情報を提供する。
パラメータフレームのシーケンスは認識ブロック１７に
供給される。認識ブロック１７は、パラメータフレーム
の入力シーケンスを基準モデル、すなわち単語モデル１
９と比較することにより音声を認識する。ここで、各モ
デルは、認識されるべき入力音声のパラメータと同じ種
類のパラメータによって表されたパラメータフレームシ
ーケンスを備える。

【００１８】また、言語モデル２１とノイズモデル２３
も、認識処理の補助のために認識ブロック１７へ供給さ
れる。ノイズモデル２３は無音声ノイズもしくはバック
グランドノイズを表わし、本実施形態においては、それ
らは認識されるべき入力音声信号と同じタイプの単一の
パラメータフレームを備える。また、言語モデル２１
は、認識ブロック１７から出力された、認識結果として
許可される単語シーケンスを、そのシステムにとって既
知の単語シーケンスに適合するように制限するのに用い
られる。認識ブロック１７から出力される単語シーケン
スは、例えば文書処理アプリケーションにおける使用の
ために提供されてもよいし、あるいは、ＰＣ１の動作を
開始したり、止めたり変更したりするためのオペレータ
コマンドとしても用いられ得るものである。

【００１９】プリプロセッサ１５、バッファ１６、単語
モデル１９や言語モデル２１やノイズモデル２３を生成
するための当該システムの学習、新しいフレーズが加え
られた際の言語モデルの更新、そして単語モデルの適用
に関するより詳細な説明は、ＥＰ−Ａ−０７８９３４９
に示されており、その内容は本願の参照として組み込ま
れる。以下、基準モデルと認識ブロック１７についてよ
り詳細に説明する。

【００２０】［基準モデル］上述したように、プリプロ
セッサ１５からの出力信号によって表される単語が何で
あるかを決定するために、これらの出力信号は基準モデ
ルと比較される。この基準モデルは、当該システムにと
って既知の単語及び当該システムをとりまく音響環境を
モデル化して格納したものである。なお、特定の単語に
関連する各モデルは、上述したプリプロセッサ１５から
出力されるパラメータフレームと同じタイプのパラメー
タフレームシーケンスを備える。

【００２１】本実施形態において、言語モデル２１はバ
イグラムモデル（Bigram model）に類似するものであ
り、メッシュ状にノードを相互接続するものである。こ
こで、それら相互接続は、当該システムに既知の単語を
表わす。しかしながら、それら相互接続は、例えば、正
しい英語の使用に関するようないかなる文法規則をも含
むものではなく、そのシステムにとって既知のフレーズ
に基づいてどの単語が他のどの単語に続くことができる
かを規制するのみである。図３は、当該システムによっ
て以下のフレーズが学習されたときに派生する言語モデ
ル２１を表わす図である。

【００２２】 get an image −フレーズ１ get the erth −フレーズ２ get the fjord −フレーズ３ get the map −フレーズ４ get the coin −フレーズ５ save an image −フレーズ６ load an image −フレーズ７ make it smaller −フレーズ８ make it larger −フレーズ９ make it brighter −フレーズ１０ make it more red −フレーズ１１ make it more yellow −フレーズ１２ make it more green −フレーズ１３ make it more cyan −フレーズ１４ make it more blue −フレーズ１５ make it more magenta −フレーズ１６ quit −フレーズ１７。

【００２３】この場合、図３に示されるように、スター
トノードＮ₀、エンドノードＮ_n、及び８個の中間ノード
Ｎ₁〜Ｎ₈がある。認識されるべき入力フレーズのため
に、システムはスタートノードＮ₀からエンドノードＮ_n
までのパスを見出さねばならない。しかしながら、シス
テムは学習した中において、合理的な範囲でフレキシブ
ルである。例えば、ユーザが"make it smaller"のかわ
りに"make smaller"というフレーズを入力すると、シス
テムはこの入力フレーズを"make it smaller"と解釈す
る。しかし、システムはたとえフレーズ内の個々の単語
が既知であっても、そのフレーズが当該システムに未知
のフレーズであった場合には、システムはそのフレーズ
を認識しない。例えば、上述の言語モデルにおいて、ユ
ーザが"save the image"と言った場合、システムにとっ
て"save"、"the"、"image"の各々は既知であるが、シス
テムはこのフレーズを認識しない。

【００２４】［動的計画法（ＤＰ）］効果的な手法で２
つのパラメータフレーム列を整合させるために、この種
の整合処理は、例えば単語が孤立して話された場合と、
連続的に話されたフレーズ内に単語が埋め込まれている
場合とのように、単語が話された際の異なる速さを補間
できなければならない。動的計画法（ＤＰ）による整合
処理は、全てのポイントで最良のマッチングを達成する
ために、最適で非線型のタイム−スケール歪を適用し
て、一つの単語を他の単語上にマッチングさせることの
できる方法の一つである。

【００２５】ＤＰマッチング処理の概要について、図４
〜図６を参照して以下に説明する。図４は、横座標軸に
入力された単語を表わすパラメータフレーム列を取り、
縦座標軸に単語モデルを表わすパラメータフレーム列を
とった様子を表わす。単語モデルと入力単語との間の差
の合計を見出すために、最小の累積距離を与える、図４
における左下と右上の間のあらゆるパスに沿ったフレー
ムの各ペア間の全距離の合計を計算する必要がある。こ
のような決定方法によれば、確実に、類似する単語の対
応フレームを正しく整合させることができるであろう。
このような全距離計算方法の一つは、全ての可能なパス
を考慮し、各パスに沿った各ポイントに対してｄ（k，
j）（フレームｋとフレームｊの間の距離）を加算する
ものである。そして、それら２つの単語の間で測定され
た距離として、獲得された累積距離の中から最小の値が
採用される。この方法は正しい答えを与えるが，有効な
パスの数が非常に多くなり、実用的な音声認識システム
にとっては実現不可能な計算量となってしまう。

【００２６】動的計画法は，全ての可能なパスに沿った
累積距離を計算することなく最適なパスに沿った累積距
離を見つけるための数学的なテクニックである。累積距
離が決定されるパスの数は、ＤＰ処理にある制約を設け
ることによって著しく減少させることができる。このよ
うな制約の一つとして、最適なパスは常に非負の傾斜を
有して前進するというものが挙げられる。この制約がな
いと、ある単語において、他のものと時間的に逆転した
ものとなってしまうからである。また、ＤＰ処理に設け
られ得る他の制約としては，入力された単語の基準単語
に対応する時間的伸縮の最大量を制限することである。
この制約は，マッチング処理においてスキップもしくは
繰り返すことのできるフレームの数を制限することによ
って実現され得る。例えば、図５において、フレームｆ
_kがフレームｆ_j ^mとマッチングする場合、フレームｆ_k+1
はフレームｆ_j ^m、ｆ_j+1 ^m、ｆ_j+2 ^mあるいはｆ_j+3 ^mとマッ
チングし得るようにフレームシーケンスが制約される。
従って，入力単語のパラメータフレームｆ_kと単語モデ
ルのパラメータフレームｆ_j ^mが最適なパス上にある場
合、上述の制約によれば、この最適なパス上のこのポイ
ント（k,j）に続くポイントは図６に示すように（k-1,
j）、（k-1,j-1）、（k-1,j-2）あるいは（k-1,j-3）の
どれかでなければならない。

【００２７】また、図４では、入力された単語と単語モ
デルの間の可能なマッチングが表わされており、フレー
ムｆ_k-1まで成長した“有効パス”が表わされている。
フレームｆ_kが認識ユニット１７に供給されたとき、現
フレームｆ_kと各有効パスの終端に位置する単語モデル
のフレームとの間にはローカル距離が存在し、そのロー
カル距離は対応する有効パスの累積距離に加えられる。
複数のパスが同一のポイントで出会った場合は、最小の
累積距離を有する有効パスが継続され、他のものは破棄
される。例えば、図４において、パスＡ、Ｂ、Ｃがポイ
ント（k,j）で出会った場合、最も小さい累積距離を有
するパス（Ａ、Ｂ或いはＣ）が継続され、他の２つは破
棄されることになる。

【００２８】従って、Ｄ（k,j）を、その単語の最初か
らポイント（k,j）までの有効パスに沿った累積距離を
表わすとすると、Ｄ（k,j）は、

【００２９】

【数１】 と表わされる。

【００３０】そして、上述の制約を加味することによ
り、Ｄ（k,j）は、

【００３１】

【数２】 と表わされる。

【００３２】上述の制約で、全ての可能なパスはｄ（0,
0）、ｄ（1,0）、ｄ（2,0）もしくはｄ（3,0）から始ま
らなければならないので、Ｄ（0,0）はこれらのポイン
トのいずれかに等しくなければならない。従って、これ
らの開始点の一つから開始し、Ｄ（k,j）の値は再帰的
な処理ルーチンを経て決定され得る。処理がマッチング
されるべき単語の終わりに到達したとき、ＤＰ処理によ
って計算された最小の累積距離が当該２つの単語を最良
の形態でマッチングした場合に対応するスコアを表わし
ている。認識されるべき入力発声が単語のシーケンスを
有している場合、採用された方向を表わすのにバックポ
インタが用いられなければならない。ＤＰ処理が最適な
パスの終了を特定した後に、そのバックポインタを通し
て逆追跡することにより、入力発声を認識することを可
能とするためである。

【００３３】上述したＤＰ処理は、全ての可能なパスを
余すところなくサーチする場合に比べて著しく計算量を
低減するものであるが、依然としてその計算量はかなり
多いものとなり得る。特に、入ってくる単語の各々は、
マッチングのために多くの単語モデルと比較されなけれ
ばならない。それゆえ、認識結果の精度に重要な影響を
及ぼさないような計算についてその計算量を削ることは
望ましいことである。成長するパスは木の枝に似ている
ので、これは、しばしば刈り込み（pruning）と称され
る。この方法でパスを刈り込むことにより、最良なパス
の両側を含む狭いバンド内において、可能なパスが考慮
されることになる。そのような刈り込みが用いられる場
合には、動的計画法の処理が必ず最適なパスを見つける
ということをもはや保証することはできないが、しかし
ながら、例えば、５〜１０のファクターによって計算の
平均量を減少させる閾値では、単語が非常によく似てい
る正しいパスはほとんど常に得られることは、当業者に
は十分に理解できることであろう。

【００３４】この実施形態においては、認識されるべき
発声に対するパラメータフレーム列を単語モデル１９及
びノイズモデル２３とマッチングするために、図２に示
される認識ブロック１７は上述したものに類似の動的計
画法処理を用いる。

【００３５】［認識サーチ］本実施形態による音声認識
システムの特徴の一つは、動的計画法処理が実現される
方法にある。特に、本実施形態は、上述の式（２）にお
いて実行される最小値の計算、すなわち、

【００３６】

【数３】 が処理中の現在フレームｆ_kに依存しないということを
利用する。従って、式（２）のこの部分は前フレームｆ
_k-1が処理されているときに計算しておくことができ
る。

【００３７】次に、動的計画法処理が利用される方法に
ついて図７〜１７を参照して以下に説明する。なお、単
語モデルのフレームと入力された認識すべき発声のフレ
ームとの混同を避けるために、単語モデルのフレームを
以降ではステートと称することにする。

【００３８】図７は、入力された発声を認識するときの
認識ブロック１７において実行される処理を示すフロー
チャートである。システムは、プリプロセッサ１５によ
って生成される順番で入力発声のパラメータフレームを
順次に処理する。この目的のために、フレームカウンタ
変数ｋが用いられる。変数ｋは、ステップＳ４１におい
てゼロに初期化され、各フレームが処理された後にステ
ップＳ６１において順次インクリメントされる。処理中
の各フレームは、ステップＳ４７において、各単語モデ
ル内の残存する有効パスの累積距離を更新するために用
いられる。ここで、各単語モデルを処理する目的のため
に、単語カウンタｗが用いられる。この単語カウンタｗ
は、ステップＳ４３においてゼロに初期化され、ステッ
プＳ４７の処理の後にステップＳ４９においてインクリ
メントされる。ステップＳ４５において、システムは、
現フレームに関して全ての単語モデルが処理されたかど
うかをチェック、すなわち、単語カウンタｗがシステム
に既知の単語の数ｎ_ｗより小さいかどうかをチェックす
る。

【００３９】現フレームｆ_kに関して各単語モデルに対
する処理が終わると、処理はステップＳ５１へ進む。ス
テップＳ５１においては、図３に示される言語モデル２
１のノードが現フレームを用いて処理される。ステップ
Ｓ５１で実行される処理は、現在のパラメータフレーム
が入力音声の開始もしくは終端の無音声部分、もしくは
入力音声における単語の許容されたシーケンス間に存在
する無音声部分に対応する状況を考慮する。この処理に
おいても、有効パスのみが単語の許容されたシーケンス
を通して成長することを確実にする。

【００４０】ステップＳ５１においてノードが処理され
た後、各単語モデルの開始、すなわち、“入り口ステー
ト（エントリステート）”の一つで終わる有効パスのた
めの累積距離がステップＳ５７において更新される。こ
の処理は、現在のパラメータｆ_kが別の単語モデルの終
端にマッチする場合に、次のパラメータフレームｆ_k+1
が別の単語モデルの開始とマッチするという状況に対処
するものである。これを達成するために、単語カウンタ
ｗはステップＳ５３において再度ゼロに初期化され、ス
テップＳ５５においてシステムは全ての単語モデルが処
理されたかどうかをチェックする。そして、システム
は、ステップＳ５７において、現在の単語モデルの入り
口ステートに対する累積距離を更新する。そして、単語
カウンタｗがステップＳ５９においてインクリメントさ
れる。その後、処理はステップＳ５５へ戻る。

【００４１】現在のパラメータフレームｆ_kに対して全
ての単語モデルがステップＳ５７で処理された後、パラ
メータフレームカウンタ変数ｋがステップＳ６１にてイ
ンクリメントされる。次に、ステップＳ６３において、
システムは処理されるべき入力発声のパラメータフレー
ムがあるかどうかを判断する。これは、ステップＳ６３
においてｋをシステムリミット（LIMIT）及び発声終端
識別子（EOS）と比較することによりなされる。システ
ムリミットは、プリプロセッサ１５によって行われる処
理に先立ってスピーチサンプルを格納するのに用いられ
るバッファ（不図示）のサイズによって定義される。

【００４２】入力発声の全てのパラメータフレームが処
理された後、ＤＰ処理は完了し、バックトラックアルゴ
リズムが最適のパスを決定し、認識結果を決定するため
に用いられる。一方、ステップＳ６３において処理され
るべきパラメータフレームがまだ存在するとシステムが
判断した場合、システムはステップＳ６５において刈り
込みの閾値を調整する。すなわち、次の入力フレームが
処理される間のステップＳ４７、Ｓ５１及びＳ５７にお
いて処理される有効パスの数を制限するための刈り込み
閾値ＴｈがステップＳ６５で調節される。そして、処理
はステップＳ４３に戻る。

【００４３】以下、図７のステップＳ４７において実行
される処理について、単語モデルの特定の例を挙げなが
ら、図８〜図１３を参照してより詳細に説明する。図８
は、トレーニング中に派生したステートＳ₀からＳ₈のシ
ーケンス、出口ステートＳ_D、そして単語モデル２０１
の終端にある番人（sentinel）ステートＳ_SENを備える
単語モデル２０１の例を示す。なお、出口ステートと番
人ステートの目的は後述する。

【００４４】単語モデル２０１の各ステートＳは、その
ステートまで成長した有効パスの累積距離を格納する累
積距離格納部Ｄ[S]を有する。この実施形態において、
単語モデル２０１は、これに関連する、現在フレームｆ
_kのための現アクティブリスト２０３も有する。このリ
ストには、現フレームｆ_kにおいて有効パスの終端とな
っている単語モデル２０１内のステートが、降順で登録
されている。従って、現アクティブリスト２０３に登録
されている各ステートはそのステートまで延びている有
効パスの累積距離を格納することになる。ここで説明す
る特定の例においては、現フレームｆ_kのための現アク
ティブリスト２０３には、Ｓ₇、Ｓ₅、Ｓ₄、Ｓ₃、Ｓ₂、
Ｓ₁そしてＳ_SENが登録されている。現アクティブリスト
２０３に登録されている各ステートはアクティブステー
トと称される。また、本実施形態において、単語モデル
２０１はこれに関連する新アクティブリスト２０５を有
する。この新アクティブリストは、ステップＳ４７にお
いて実行される処理の間に完成され、次のフレームｆ
_k+1において有効パスの終端が存在することになるであ
ろう単語モデル２０１内のステートを登録する。

【００４５】次に、上述の現アクティブリスト２０３と
新アクティブリスト２０５の意味について、図９を参照
して説明する。ここで、図９は現フレームｆ_kまでの入
力単語と単語モデル２０１との間の６種類の可能なマッ
チングを表すものであり、特に６つの有効パスＰ１〜Ｐ
６を示している。図示のように６つの有効パスＰ１〜Ｐ
６の各々は単語モデル２０１のステートＳ₇、Ｓ₅、
Ｓ₄、Ｓ₃、Ｓ₂及びＳ₁を終端としており、これら有効パ
スの各終端ステートが現アクティブリスト２０３におい
て（番人ステートとともに）降順に登録されることにな
る。一方、新アクティブリスト２０５に入るべきステー
トを決定するために、すなわち次の入力フレームｆ_k+1
のために残されるべきパスを決定するために、一つの入
力パラメータフレームから次の入力パラメータフレーム
への許容されたステートの遷移、すなわち動的計画法に
よるマッチング処理に設けられた制約が考慮される。

【００４６】まず、入ってくる発声に対する基準モデル
の時間的圧縮の最大量は、入ってくる発声の隣接するフ
レーム間でスキップし得るステートの最大数によって決
定される。本実施形態においてこの最大数は“２”にセ
ットされる。すなわち、ＤＰ処理は図５で示した状態遷
移に従う。また、入ってくる発声に対する基準モデルの
時間的伸長の最大量は、連続して入ってくるフレームを
いくつまで同一ステートにマッチングさせ得るかによっ
て定義される。しかしながら、これは、繰り返しの数を
カウントする手段と繰り返し数が許容された最大数と等
しいかどうかをチェックするための判断を要求する。発
明者らは、各繰り返しのたびに単にペナルティを課する
ことが効果的で、処理時間の短縮化を実現することを見
出した。以上のような制約により、例えば、パスＰ５は
図９に破線で示されるパス２０７の１つ或いは全てに沿
って成長し得る。図９に示されている他のパスＰ１〜Ｐ
４及びＰ６も同様の方法で成長し、パスの成長先となり
得るステートが新しいアクティブリスト２０５へ降順で
加えられる。同じポイントにて２つ以上のパスが出会っ
た場合は、最小の累積距離を有するパスが維持され他の
ものは破棄される。さらに、パスの累積距離が刈り込み
閾値より大きくなった場合、そのパスも破棄される。こ
のようにして、新しいパスが連続的に生成され、その一
方で他のパスが破棄されていく。なお、刈り込み閾値の
目的は、各入力パラメータフレームに関して処理される
有効パスの数を制限し、これによってアルゴリズムに必
要となる時間及びメモリの量を制限することにある。

【００４７】図１０は、図７のステップＳ４７において
実行される処理のより詳細を示すフローチャートであ
る。まず、ステップＳ７１において、ポインタＮＡが初
期化され、単語モデルの出口ステートにおいて格納され
た累積距離、すなわちＤ［Ｓ_D］が特大値、HUGEにセッ
トされる。ポインタＮＡは、新アクティブリスト２０５
に登録されている最後のアクティブステートに続く次の
ステートを指すのに用いられる。当業者は、それゆえ、
ポインタＮＡが新アクティブリストに加えられるべき次
のステートとなる可能性があるステートを指すことにな
ることを理解するであろう。処理の最初において、新ア
クティブリスト２０５にはアクティブステートがなく、
そのためポインタＮＡは出口ステートＳ_Dを指すように
セットされるのである。ステップＳ７３において、シス
テムは、現アクティブリスト２０３にアクティブステー
トがあるかどうかを見るべくチェックする。換言すれ
ば、現フレームｆ_kに対して、現在の単語内のステート
を終端とする有効パスがあるかどうかを見るためのチェ
ックを行う。本例においては、現アクティブリスト２０
３において７つのアクティブステート（番人ステートＳ
_SENを含む）があり、システムはこれらステートの各々
を順次処理する。ここで、カウント変数ｉが提供され
る。カウント変数ｉは、現アクティブリスト２０３上の
アクティブステートを通してカウントするのに用いられ
るもので、ステップＳ７５においてゼロにセットされ、
ステップＳ７７において、現アクティブリスト２０３内
の全てのアクティブステートが処理されるまでステップ
Ｓ７９においてインクリメントされる。

【００４８】現アクティブリスト２０３上の全てのアク
ティブステートが処理されると、ステップＳ８３へ進
む。ステップＳ８３では、ステップＳ７７の処理の間に
生成された新アクティブリスト２０５が処理されるべき
入力発声の次のフレームｆ_k+1のための現アクティブリ
スト２０３に変更される。この変更は、実際には、２つ
のアクティブリストを指すために用いられる２つのポイ
ンタを入れ替えることによって達成される。従って、古
くなった現アクティブリストは、次の入力フレームｆ
_k+1の処理の間に新アクティブリストとして上書きされ
る。そして、ステップＳ８５において、最後にアクティ
ベートされ、最後に新アクティブリスト２０５（番人ス
テートＳ_SENを含まない）に登録された、ポインタＬＡ
によって指定される最終ステートが、図７に示されるス
テップＳ５７における使用のために格納される。なお、
ステップＳ５７については、以下に更に詳細に説明す
る。

【００４９】ステップＳ７７において実行される処理の
概要を、アクティブステートＳ₇とＳ₅を例として用いて
説明する。これらＳ₇とＳ₅は、図９に示したように、そ
れぞれパスＰ１とＰ２の終わりにある。図１１は２つの
有効パスＰ１とＰ２の一部を示すもので、これらはそれ
ぞれ現フレームｆ_kにて、ステートＳ₇とＳ₅を終端とし
ている。図１１に示される破線は、２つのパスＰ１とＰ
２の各々が次のフレームｆ_k+1において成長し得る道を
表わしている。破線２１３と２１５によって示されるよ
うに、フレームｆ_k+1においてパスＰ１が別の単語の中
へ伸びていくことも可能である。従って、パスＰ１の累
積距離（それはアクティブステートＳ ₇に格納される）
は、出口ステートＳ_Dの中にコピーされる。また、破線
２１７と２１９によって示されるように、パスＰ１はス
テートＳ₈およびステートＳ₇のそれぞれにも成長でき
る。従って、パスＰ１の累積距離はこれらのステートに
もコピーされる。こうして、図１２ａに示されるよう
に、ステートＳ₈とＳ₇が新しいアクティブリスト２０５
に降順で加えられる（しかしながら、入ってくるフレー
ムと実際に比較されることがなく、その単語を出て行く
全てのパスの累積距離のうちの最小のものを格納するた
めだけに用いられる出口ステートは新アクティブリスト
２０５には加えられない）。そして、更に、最終アクテ
ィブポインタＬＡが最後に加えられたステート、すなわ
ちステートＳ₇を指すべくセットされ、次アクティブポ
インタＮＡがステートＳ₆を指すようにセットされる。

【００５０】パスＰ１が処理されると、次に、システム
はパスＰ２を処理する。破線２２１，２２３，２２５及
び２２７によって示されているように、パスＰ２はステ
ートＳ₈、ステートＳ₇、ステートＳ₆及びステートＳ₅の
それぞれに成長し得る。しかしながら、パスＰ２の累積
距離（それはアクティブステートＳ₅に格納されてい
る）は、これらステートの全てに単純にコピーされるも
のではない。なぜなら、ステートＳ₈とステートＳ₇の２
つのステートは、このときすでに次のフレームｆ _k+1に
対する累積距離を有しているからである。従って、これ
ら２つのステートのために、すでにその中に格納されて
いる累積距離とパスＰ２による累積距離との比較がなさ
れ、最小のものがそれら２つのステートにコピーされ
る。換言すれば、アクティブリストＳ₅の処理後の、図
１１に示されるパスに対してＳ₈とＳ₇に格納される累積
距離は、ｍｉｎ（Ｄ［Ｓ₇］，Ｄ［Ｓ₅］）によって与え
られる。一方、次のフレームｆ_k+1のための累積距離は
ステートＳ₆内にはまだ格納されていないので、アクテ
ィブステートＳ₅に格納された累積距離は、ステートＳ₆
に直接的にコピーされ得る。この結果、図１２ｂに示さ
れるように、２つのステートＳ₆とＳ₅が新アクティブリ
スト２０５に加えられ、最終アクティブポインタＬＡが
ステートＳ₅を指すようにセットされ、次アクティブポ
インタＮＡがステートＳ₄を指すようにセットされる。
現アクティブリスト２０３における、番人ステートＳ
_SENを除く全ての残りのアクティブステートも同じ方法
で処理される。そして、システムが、処理されるべき次
のステートが番人ステートであると判定した場合に、新
アクティブリスト２０５に番人ステートＳ_SENを加え、
処理は図１０に示されるステップＳ８３に進む。このよ
うに、現アクティブリストの終端を特定するために番人
ステートＳ_SENを用いることの利点については後述す
る。以下に述べるステップＳ７７のより詳細な説明から
明らかであるように、最終アクティブポインタＬＡと次
アクティブポインタＮＡは、システムが比較を必要とす
るステートとそうでないステートとを特定するために新
アクティブリスト２０５をチェックする必要をなくすた
めに提供されている。特に、処理対象のステートが次ア
クティブポインタＮＡによって示されるステートを超え
ている場合は比較が必要であり、そうでなければ累積距
離は単純にそのステートにコピーされ得る。

【００５１】ここで、Ｓを次に処理されるべきアクティ
ブステートであるとすると、本実施形態において適用さ
れた動的計画法の制約によって４つの異なる状況が存在
する。それらの異なる状況とは、次アクティブポインタ
ＮＡに関連づけて考慮されるものである。すなわち、 i）次アクティブポインタＮＡがステートＳを指す状
態、 ii）次アクティブポインタＮＡがステートＳ＋２を超え
るステートを指す状態 iii）次アクティブポインタＮＡがステートＳ＋１を指
す状態 iv）次アクティブポインタＮＡがステートＳ＋２を指す
状態である。

【００５２】発明者らは、上記の第１番目の状態が最も
起こりやすいこと、上記の第２番目の状態が２番目に起
こりやすいこと、そして他の２つの状態はめったに起こ
らないことを確認している。探索アルゴリズムは、それ
ゆえ、これらの状況をこの順番で考慮する。このように
して、発生しそうもない状態が、発生しそうな状態が失
敗（false）に終わった場合にのみ考慮されるように
し、探索アルゴリズムの高速化を図る。

【００５３】また、発明者らは、本実施形態の動的計画
の制約のために、Ｓが処理中の現在のアクティブステー
トである場合には、以下のことが保証されることを確認
している。

【００５４】

【数４】

【００５５】このことから、現アクティブステートに格
納された累積距離、すなわちＤ［Ｓ］がＤ［Ｓ＋１］よ
りも大きい場合には、Ｄ［Ｓ］をＤ［Ｓ＋２］及びＤ
［Ｓ＋３］と比較する必要はないことがわかる。同様
に、Ｄ［Ｓ］がＤ［Ｓ＋１］よりも小さく、Ｄ［Ｓ＋
２］よりも大きい場合は、Ｄ［Ｓ］とＤ［Ｓ＋３］を比
較する必要がない。しかしながら、現アクティブステー
トＳがその単語の終わりから３つのステート以内のもの
である場合には、注意が必要である。このような場合
は、ステートＳ＋３が存在しないからである。この場合
の明確なテストは、単語の終りに番人ステートＳ_SENを
用いることにより回避され得る。より具体的には、番人
ステートＳ_SENに格納される累積距離をゼロにセットす
ることにより、Ｄ［Ｓ］がＤ［Ｓ_SEN］よりも小さくな
り得ないことを保証することができる。

【００５６】次に、図１０に示されるステップＳ７７に
おいて、各ステートに対して実行される処理について、
図１３ａから図１３ｅのフローチャートを参照して詳細
に説明する。図１３ａのステップＳ９１において、シス
テムは、現アクティブステートＳを終端としている有効
パスの累積距離と刈り込み閾値Ｔｈとを比較する。すな
わち、Ｄ［Ｓ］とＴｈを比較する。Ｄ［Ｓ］が刈り込み
閾値Ｔｈよりも大きい場合、現アクティブステートで終
わるパスは破棄され、処理は図１０のステップＳ７９に
戻る。一方、Ｄ［Ｓ］が刈り込み閾値Ｔｈよりも小さい
場合は、処理はステップＳ９２へ進む。ステップＳ９２
で、システムは、Ｄ［Ｓ］がゼロであるかどうかをチェ
ックする。すなわち、処理中である現アクティブステー
トＳが番人ステートＳ_SENであるか否かをチェックす
る。

【００５７】本実施形態においては、上述したように、
処理されるべき現アクティブリスト上に別のアクティブ
ステートが存在しないことをステップＳ９２において特
定できるように、番人ステートがアクティブリストの終
わりに加えられている。なお、そのステートが現アクテ
ィブリスト上の最後であるかどうかを調べるために、あ
る特定のテストが各アクティブステートを処理した後に
実行されてもよい。しかしながら、この方法において番
人ステートを用いることの利点は、ステップＳ９１にお
いて刈り出されたステートに対してテストを実行しない
ことであり、それにより要求される処理量を節約できる
ことである。

【００５８】さて、現ステートが番人ステートでない場
合（Ｄ[S]≠０の場合）、処理はステップＳ９３へ進
む。ステップＳ９３において、変数ACOUNTがインクリメ
ントされる。このACOUNTは、現フレームｆ_kに対して処
理されるアクティブステートの総数のカウント値を保持
するのに用いられる。次に、システムは、ステップＳ９
４において、処理中の現アクティブステートＳと処理中
の現フレームｆ_kとの間のローカル距離を計算し、それ
を現アクティブステートに格納された累積距離Ｄ［S］
に加える。

【００５９】本実施形態において、現フレームｆ_kと現
アクティブステートＳとの間のローカル距離を算出する
ために、以下のような大きさの総計（マグニチュードの
サム）が用いられる。

【００６０】

【数５】

【００６１】ここで、ｍは、プリプロセッサ１５によっ
て入力音声から抽出された各フレーム/ステートにおけ
るパラメータの数である。例えば、ユークリッド距離計
測のような、他の距離計測も使用可能である。しかしな
がら、上記のような大きさの総計によれば、積算を必要
とせず、加算と減算のみで距離計算を行い得る。そのた
め、本実施形態ではこの手法を用いている。

【００６２】この距離計算がＣＰＵの占有とうい観点か
らみて、認識サーチの主要な構成要素の一つであるとい
う点を当業者は理解するであろう。

【００６３】個人用オルガナイザのような、メモリ容量
及び処理能力が制限され、ステート及び入力されるフレ
ームの各パラメータが単一のバイトで格納される低価格
アプリケーションにおいて、上記の距離計算はルックア
ップテーブルを用いて実現することができる。差分Ｓ^p
−ｆ_k ^pが５１１個の異なる値のうちのひとつをとるから
である。この方法でルックアップテーブルを用いること
は、差分Ｓ^p−ｆｐ_k ^pが正であるか負であるかの判断を
不要とする。それゆえ、距離計算は、

【００６４】

【数６】 のようになる。

【００６５】テーブルエントリは−２５５から＋２５５
の間ではなく、１から５１１の間となるように、２５６
がルックアップテーブル（ＬＵＴ）のアドレッシングに
おいて含まれていることを当業者等は理解できるであろ
う。

【００６６】距離計算にルックアップテーブルが用いら
れる場合、同じ入力フレームｆ_kが多数の単語ステート
Ｓに対して比較されるということに着目することによ
り、高速化が達成される。それゆえ、各フレームｆ_kに
対して、ＴＰ^pがテーブルエレメント［２５６−ｆ_k ^p］
をアドレスするようにテーブルポインタＴＰが計算され
得る。それゆえ、距離計算は以下のようになる。

【００６７】

【数７】

【００６８】ステップＳ９４において累積距離が更新さ
れた後、システムは、ステップＳ９５からＳ９７におい
て上述した４つの状況についてチェックする。すなわ
ち、まず、ステップＳ９５において、現アクティブステ
ートＳにて終わる有効パスが次アクティブポインタＮＡ
によって指定されているステートであるかどうかをチェ
ックする。もしそうならば、処理は、図１３ｂに示され
るステップＳ９８へ進む。また、次のアクティブポイン
タＮＡが現アクティブステートＳを指定していない場
合、処理はステップＳ９６へ進む。ステップＳ９６にお
いて、システムは、次アクティブポインタＮＡが、処理
中の現アクティブステートを３つ以上超えるステートを
指定しているかどうかチェックする。もしそうであるな
らば、処理は図１３ｃのステップＳ１０９に進む。ステ
ップＳ１０９以降の処理については、図１３ｃにおいて
より詳細に説明される。一方、ステップＳ９６で否と判
定されたならば、処理はステップＳ９７へ進む。ステッ
プＳ９７では、次アクティブポインタＮＡが現アクティ
ブステートに続くステートを指定しているかどうかチェ
ックする。もしそうであれば、処理は図１３ｄにおいて
示されるステップＳ１１５に進む。一方、ステップＳ９
７において否と判断された場合は、次のアクティブポイ
ンタＮＡがステートＳ＋２を指していることを意味して
いるので、処理は図１３ｅに示されるステップＳ１２５
へ進む。

【００６９】次に図１３ｂから１３ｅにおける各ステッ
プで実行される処理について説明する。図１３ｂは、次
アクティブポインタＮＡが、処理されている現アクティ
ブステートＳを指定する状況において実行される処理ス
テップを示す。上述してきた説明から当業者には明らか
であるように、上述の動的計画の制約で、この状況にお
いては、現アクティブステートＳで終わる有効パスの累
積距離は、現アクティブステートＳに続く３つのステー
ト、Ｓ＋１、Ｓ＋２、Ｓ＋３に格納された累積距離と比
較されなければならない。これらのステートはすでに新
しいアクティブリストにすでに存在するからである。

【００７０】しかしながら、この比較に先立って、シス
テムは、ステップＳ９８において、現在のアクティブス
テートＳを新アクティブリスト２０５の次の位置に加え
る。そして、システムは、ステップＳ９９において、次
アクティブポインタＮＡがステートＳ−１を指すように
セットする。

【００７１】その後、処理は、ステップＳ１００へ進
む。ステップＳ１００において、システムは、現アクテ
ィブステートＳに格納された累積距離がステートＳ＋１
に格納された累積距離よりも小さいかどうかをチェック
する。このチェック結果が否であった場合は、式（４）
により、現アクティブステートＳに格納された累積距離
をステートＳ＋２或いはＳ＋３に格納された累積距離と
比較する必要はなく、処理をステップＳ１０８へ進める
ことができる。一方、現アクティブステートＳに格納さ
れた累積距離がステートＳ＋１に格納された累積距離よ
りも小さい場合は、処理はステップＳ１０１へ進む。ス
テップＳ１０１においては、ステートＳ＋１に格納され
た累積距離を現アクティブステートＳに格納された累積
距離と等しくする。換言すれば、現アクティブステート
を終端としているパスをステートＳ＋１へ成長させる。
システムは、ステップＳ１０２において現アクティブス
テートＳに格納された累積距離がステートＳ＋２に格納
された累積距離よりも小さいかどうかをチェックする。
このチェックの結果が否であれば、処理はそのままステ
ップＳ１０８へ進む。一方、現アクティブステートＳに
格納された累積距離がステートＳ＋２に格納された累積
距離よりも小さい場合、処理はステップＳ１０３へ進
む。ステップＳ１０３では、ステートＳ＋２に格納され
た累積距離を現アクティブステートＳに格納された累積
距離と同じにする。そして、処理はステップＳ１０４へ
進む。ステップＳ１０４では、システムは、現アクティ
ブステートＳに格納された累積距離が、ステートＳ＋３
に格納された累積距離よりも小さいかどうかをチェック
する。このチェックの結果が否であれば、処理はステッ
プＳ１０８へ進む。一方、現アクティブステートＳに格
納された累積距離が、ステートＳ＋３に格納された累積
距離よりも小さい場合は、処理はステップＳ１０５へ進
む。ステップＳ１０５では、ステートＳ＋３に格納され
た累積距離を現アクティブステートＳに格納された累積
距離と同じにする。

【００７２】以上のようにして、現アクティブステート
に格納された累積距離がこれに続く３つのすべてのステ
ートにコピーされた場合、システムは、ステップＳ１０
６において、現アクティブステートＳに格納された累積
距離が、全単語中の現フレームｆ_kまで成長した全有効
パスに関する最小累積距離（MINSCORE）よりも小さいか
どうかをチェックする。チェックの結果が否であれば、
処理はステップＳ１０８へ進む。一方、現アクティブス
テートＳに格納された累積距離が、MINSCOREよりも小さ
いのであれば、ステップＳ１０７において、MINSCORE
を、現アクティブステートＳに格納されている累積距離
でもって置き換える。そして、処理はステップＳ１０８
へ進み、ペナルティ（PEN）が現アクティブステートに
格納された累積距離に加えられる。上述のように、ペナ
ルティは、基準モデルの過度の時間的伸張を防止するた
めに加えられる。こうして処理は終了し、図１０に示さ
れるステップＳ７９へ戻る。ステップＳ７９では、ステ
ップＳ７７において現アクティブリストの次のステート
が処理されるように、ステートカウンタｉがインクリメ
ントされる。

【００７３】一方、図１３ａに示されるステップＳ９６
において、次アクティブポインタＮＡが現アクティブス
テートＳより２ステートを超えたステートを指定する場
合、処理は図１３ｃに示されるステップＳ１０９へ進
む。ステップＳ１０９においては、ステートＳ＋３、Ｓ
＋２、Ｓ＋１、Ｓが新アクティブリストにその順番で加
えられる。そして、処理はステップＳ１１０へ進み、次
のアクティブポインタＮＡがＳ−１を指すようにセット
する。次に処理は、ステップＳ１１１へ進み、現アクテ
ィブステートＳに格納された累積距離が、現フレームｆ
_kまで成長している全単語中の全有効パスに関する最小
累積距離MINSCOREよりも小さいかどうかをチェックす
る。このチェックの結果が否の場合は、処理はステップ
Ｓ１１３へ進む。一方、現アクティブステートＳに格納
された累積距離がMINSCOREよりも小さい場合は、ステッ
プＳ１１２において、MINSCOREが現アクティブステート
Ｓに格納された累積距離によって置き換えられる。

【００７４】上述のように、図１３ａに示されるステッ
プＳ９６からステップＳ１０９へ進む状況では、次アク
ティブポインタＮＡは、現アクティブステートを２つよ
り多く超えるステートを指定していたはずである。この
状況において、本実施形態で用いられる動的計画の制約
で、どのような累積距離とも比較する必要がないこと
は、上記の説明から当業者には理解され得ることであろ
う。現アクティブステートが成長する先となるステート
のいずれもが新アクティブリスト上にはまだ存在しない
からである。従って、ステップＳ１１３において、シス
テムは、ステートＳ＋１、Ｓ＋２、Ｓ＋３に格納された
累積距離を現アクティブステートＳに格納されている累
積距離とする。そして、処理は、ステップＳ１１４に進
む。ステップＳ１１４では、上述したペナルティが現ア
クティブステートＳに格納された累積距離に加えられ
る。次に、処理は終了し、図１０に示されるステップＳ
７９に戻る。

【００７５】次に、図１３ａに示されるステップＳ９７
において、システムが、次アクティブポインタＮＡがス
テートＳ＋１を指定していると判断した場合、処理は図
１３ｄに示されるステップＳ１１５へ進む。ステップＳ
１１５では、ステートＳ＋１とＳを、その順番で新アク
ティブリストに追加する。次に、ステップＳ１１６にお
いて、次のアクティブポインタＮＡがステートＳ−１を
指すようにセットされる。次に、システムは、ステップ
Ｓ１１７において、ステートＳ＋１に格納されている累
積距離を現アクティブステートＳに格納されている累積
距離にする。ステートＳ＋１はステップＳ１１５よりも
前では新アクティブリスト上に存在していないので、シ
ステムは、ステートＳ＋１に格納された累積距離を現ア
クティブステートＳに格納された累積距離と比較する必
要が無い。この点は、上記の説明から当業者には理解さ
れうるであろう。そして処理はステップＳ１１８〜ステ
ップＳ１２４へ進む。これらのステップは、図１３ｂに
示されるステップＳ１０２〜Ｓ１０８と同じであるの
で、ここではその説明を省略する。

【００７６】更に、図１３ａに示される、ステップＳ９
７において、次アクティブポインタＮＡがステートＳ＋
１を指定していないと判断された場合、本実施形態にお
いて用いられている動的計画法による処理の制約のた
め、次アクティブポインタはステートＳ＋２を指定して
いなければならない。従って、処理は、図１３ｅに示さ
れるステップＳ１２５へ進む。ステップＳ１２５におい
て、ステートＳ＋２、Ｓ＋１及びＳは、その順序で新ア
クティブリストに加えられる。次に、処理はステップＳ
１２６へ進み、次アクティブポインタＮＡがステートＳ
−１を指すようにセットされる。次に、ステップＳ１２
７において、システムは、ステートＳ＋１とＳ＋２に格
納されている累積距離を現アクティブステートＳに格納
されている累積距離と同じにする。ここで現アクティブ
ステートＳに格納された累積距離とステートＳ＋１及び
Ｓ＋２に格納された累積距離との比較を行う必要が無い
ことは、当業者には明らかであろう。ステップＳ１２５
よりも前の時点で、新アクティブリスト上にこれらのス
テートは存在しないからである。ステップＳ１２８にお
いて、システムは現アクティブステートに格納された累
積距離がステートＳ＋３に格納された累積距離よりも小
さいかどうかを判断する。現アクティブステートＳに格
納された累積距離がステートＳ＋３に格納されている累
積距離よりも小さくない場合、処理はステップＳ１３２
へ進む。一方、現アクティブステートＳに格納された累
積距離がステートＳ＋３に格納されている累積距離より
も小さい場合は、処理はステップＳ１２９へ進み、ステ
ートＳ＋３に格納されている累積距離を現アクティブス
テートＳに格納されている値とする。そして、システム
は、ステップＳ１３０にて、現アクティブステートＳに
格納されている累積距離がMINSCOREよりも小さいかどう
かを判断する。ステップＳ１３０のチェック結果が否の
場合、処理はステップＳ１３２へ進む。一方、ステップ
Ｓ１３０のチェック結果が肯定の場合には、ステップＳ
１３１において、システムは、MINSCOREを現アクティブ
ステートＳに格納されている累積距離とする。そして、
処理はステップＳ１３２へ進み、上述のペナルティＰＥ
Ｎが現アクティブステートＳに格納されている累積距離
に加えられる。そして、本処理を終了し、図１０に示さ
れるステップＳ７９へ戻る。

【００７７】上述した処理はアクティブリスト中の全て
のステートに対して実行される。しかし、現アクティブ
リスト上の最後のアクティブステートが処理される場
合、それは番人ステートＳ_SENであるので、図１３ａに
示されるステップＳ９２からステップＳ１３３へ処理が
進む。ステップＳ１３３では、番人ステートＳ_SENが新
アクティブリストに加えられる。ステートＳ＋３、Ｓ＋
２、Ｓ＋１に格納されている累積距離を現アクティブス
テートＳに格納された累積距離とした場合にのみ、MINS
CORE（処理中の現フレームｆ_kまでに全単語中の全有効
パスにおける最小の累積距離を表わす）が、図１３ｂ、
図１３ｃ及び図１３ｄに示される処理ステップにおいて
更新されることが、当業者には理解されよう。しかしな
がら、本実施形態において、現アクティブステートＳが
その単語の終端から３ステート以内にある場合にはこれ
は起こり得ないので、出口ステートＳ_Dに格納された累
積距離がMINSCOREより小さいかどうかを判断するため
に、ステップＳ１３４においてエクストラなテストが実
行されるのである。このテストの判断結果が否の場合
は、処理はそのまま図１０に示されるステップＳ８３へ
戻る。一方、肯定の場合は、図１０に示されるステップ
Ｓ８３に戻る前に、ステップＳ１３５においてMINSCORE
が終端ステートＳ_Dに格納された累積距離に設定され
る。

【００７８】以上説明した図１３の処理について、図８
に示されるアクティブリスト２０３における最初の２つ
のアクティブステートを処理する場合を例に挙げて更に
説明する。処理されるべき最初のアクティブステートは
ステートＳ₇である。ステップＳ９１において、システ
ムはステートＳ₇に格納されている累積距離が刈り込み
閾値Ｔｈよりも小さいかどうかを判断する。否の場合、
このアクティブステートの処理は終了し、次のアクティ
ブステートの処理が開始される。一方、肯定であれば、
処理はステップＳ９２へ進む。ステートＳ₇は番人ステ
ートＳ_SENではないので、このステートに格納される累
積距離はゼロではない（ゼロ値は、番人ステートＳ_SEN
のためにリザーブされるものである）。従って、処理は
ステップＳ９３へ進み、変数ACOUNTがインクリメントさ
れる。ステップＳ９４において、現アクティブステート
Ｓ₇と現フレームｆ_kとのローカル距離が計算され、ステ
ートＳ₇に格納されている累積距離に加算される。

【００７９】ステートＳ₇は、処理すべき最初のアクテ
ィブステートであるので、次アクティブポインタＮＡは
出口ステートＳ_Dを指すことになる。この出口ステート
Ｓ_Dは、図８に示される単語モデル２０１からわかるよ
うに、ステートＳ₇よりも２ステート離れている。従っ
て、処理はステップＳ９５、Ｓ９６、Ｓ９７を通って、
図１３ｅに示されるステップＳ１２５に進む。ステップ
Ｓ１２５では、ステートＳ₈とＳ₇が、その順序で新アク
ティブリスト２０５に加えられる。しかしながら、なお
も出口ステートＳ_Dはその新アクティブリストに加えら
れない。出口ステートＳ_Dは、その単語を出て行く全て
のパスのうちの最小の累積距離を格納するのに使われる
だけだからである。次に、ステップＳ１２６において、
ステートＳ ₆を指すように次のアクティブポインタＮＡ
がセットされ、ステップＳ１２７においてステートＳ₈
とＳ_Dに格納されている累積距離を現アクティブステー
トＳ₇に格納されている累積距離と同じにする。次に、
処理は、ステップＳ１２８に進み、システムは、ステー
トＳ₇に格納されている累積距離が番人ステートＳ_SENに
格納されている累積距離より小さいかチェックする。番
人ステートＳ_SENに格納されている累積距離はゼロであ
るので、処理はステップＳ１３２に進むことになる。ス
テップＳ１３２では、システムは、ステートＳ₇に格納
されている累積距離にペナルティを加える。こうして図
１３ｅに示される処理は終了し、図１０に示されるステ
ップＳ７９へ進む。ステップＳ７９において、カウント
変数ｉが、次のアクティブステートＳ₅が処理されるよ
うに、インクリメントされる。

【００８０】ステートＳ₅の処理は、以下を除いて、ス
テートＳ₇に対する処理と同じである。すなわち、ステ
ップＳ９７において、図１３ｅに示されるステップＳ１
２５へ進む代わりに、処理は、図１３ｄに示されるステ
ップＳ１１５へ進む。これは、次のアクティブポインタ
ＮＡがアクティブステートＳ₇の処理の間にステップＳ
１２６においてステートＳ₆を指すようにセットされる
からである。従って、ステップＳ１１５において、シス
テムはステートＳ₆とＳ₅を新アクティブリスト２０５へ
この順序で追加する。そして、処理は、ステップＳ１１
６へ進み、次のアクティブポインタＮＡがステートＳ₄
を指すようにセットされる。次に、ステップＳ１１７に
おいて、ステートＳ₆に格納された累積距離を現アクテ
ィブステートＳ₅に格納された累積距離と同じにする。
次に、ステップＳ１１８において、システムは現アクテ
ィブステートＳ₅に格納されている累積距離を、ステー
トＳ₇に格納されている累積距離と比較する。現アクテ
ィブステートＳ₅に格納されている累積距離がステート
Ｓ₇に格納されている累積距離よりも大きい場合は、処
理はそのままステップＳ１２４へ進む。一方、ステート
Ｓ₇に格納されている累積距離よりもステートＳ₅に格納
されている累積距離のほうが小さい場合は、処理はステ
ップＳ１１９へ進む。ステップＳ１１９において、ステ
ートＳ₇に格納されている累積距離を現アクティブステ
ートＳ₅に格納されている累積距離で更新する。同様の
比較と更新が、ステップＳ１２０とステップＳ１２１に
おいて、ステートＳ₈に格納されている累積距離につい
て行われる。そして、ステートＳ₈に格納されている累
積距離がステップＳ１２１で更新された場合、システム
はステップＳ１２２において、現アクティブステートＳ
₅に格納されている累積距離がMINSCOREよりも小さいか
どうかを判断する。否であれば、処理はステップＳ１２
４へ進み、一方、肯定であれば、ステップＳ１２４へ進
む前の現アクティブステートＳ₅に格納されている累積
距離でもってMINSCOREに格納されている累積距離を置き
かえる。ステップＳ１２４では、現アクティブステート
Ｓ₅に格納されている累積距離にペナルティPENが加えら
れる。そして、処理は、図１０のステップＳ７９へ戻
り、次のアクティブステートＳ₄が処理されるように、
カウント変数ｉをインクリメントする。

【００８１】この再帰的な処理ルーチンは、システムに
既知の全基準単語において、全ての現アクティブステー
トに対して実行される。

【００８２】現フレームｆ_kについて上記方法で各単語
を処理した後、言語モデル２１の各ノードが順次に処理
される。上述のように、言語モデル２１は、許容できる
単語のシーケンスを決定する。この情報は、ノードによ
って定義され、詳細には、特にその入力と出力に接続さ
れる単語によって定義される。図７におけるステップＳ
５１でのノードの処理は、許容された単語列の範囲のみ
で有効パスが成長することを確実にするものである。次
に、図１４を参照して、ステップＳ５１で実行される処
理についてより詳細に説明する。

【００８３】最初に、ノードのどれかを処理するに先立
って、バックグランドノイズを表わすフレームと現フレ
ームｆ_kとのローカル距離（即ち、ｄ（noise,ｆ_k））が
ステップＳ１５１で計算される。次に、ステップＳ１５
３において、ノードポインタｖがスタートノードＮ₀を
指すように初期化される。次に、ステップＳ１５５にお
いて、ノードポインタｖによって指定されるノードに格
納されている累積距離、即ちＤ［ｖ］を、刈り込み閾値
Ｔｈと比較する。Ｄ［ｖ］が刈り込み閾値Ｔｈよりも小
さい場合、処理はステップＳ１５７へ進み、ｄ（noise,
ｆ_k）が処理中である現ノードｖに格納されている累積
距離に加えられる。次に、ステップＳ１５９において、
システムは、Ｄ［ｖ］を最小値格納部MINSCOREに格納さ
れている値と比較する。そして、Ｄ［ｖ］のほうが小さ
ければ、ステップＳ１６１においてＤ［ｖ］の値をMINS
COREにコピーする。そして、ステップＳ１６３におい
て、カウンタACOUNT（それは現フレームについて処理さ
れているアクティブステートとノードの数を表わす）が
インクリメントされ、処理は、ステップＳ１６５へ進
む。一方、ステップＳ１５５において、Ｄ［ｖ］が刈り
込み閾値Ｔｈよりも大きい場合は、ステップＳ１６７に
進み、特大値HUGEがＤ［ｖ］にセットされ、処理はステ
ップＳ１６５へ進む。

【００８４】ステップＳ１６５とＳ１６８において実行
される処理について、図１５に例示されるノードＮを用
いて説明する。このノードＮは、３つの単語、“ge
t“、“save”及び“load”をその入力側に接続し、“a
n”と“the”をその出力側に接続している。図３におい
てそのようなノードは示されていないが、本実施形態の
動的計画法による処理が、より複雑な言語モデルに関し
て稼動することを示すために選択された例である。特
に、ノードが図１５に示されるものに似ている、有限の
ステート文法はありふれたものである。

【００８５】ステップＳ１６５において、システムは、
ノードＮの入力に接続されている単語の出口ステート
（Ｓ_D）、即ち、“get”、“save”、“load”という単
語の出口ステートに格納された全累積距離のうちの最小
のものを判断する。一般にこの計算は以下のように表わ
される。

【００８６】

【数８】

【００８７】ここで、Ｉw［ｖ］はノードｖの入力に接
続される全ての単語を表わす。システムが、ノードＮに
対するこの最小の累積距離を決定した後、その値が既に
そこ（ノードＮ）に格納されている累積距離（Ｄ
［Ｎ］）よりも小さい場合、その値はノードＮに格納さ
れた累積距離Ｄ［Ｎ］にコピーされる。実際のところ、
これは、そのノードの入力に接続された単語の一つから
来る有効パスにおいて、当該ノードにおいて成長中であ
るパスの累積距離よりも小さい累積距離を有するものが
あるかどうかの判断である。

【００８８】フレーズ中の単語の前、中間、終端にバッ
クグランドノイズフレームとマッチするギャップが含ま
れている可能性があるので、有効パスがノード内を成長
することもありうる。この一つの入力フレームから次の
フレームへの有効パスがノード内に残ることの可能性
は、図１５においてノードＮより出てノードＮに戻る矢
印２３１によって表わされている。パスは連続して入力
されるいかなる数のフレームに対しても、ノード内に残
ってよい。システムがステップＳ１６５の処理を実行し
た後、ステップＳ１６８において、ノードＮに格納され
ている累積距離が、一時的な格納場所INSCOREに既に格
納されている値よりも小さい場合、その累積距離がINSC
OREにコピーされる。単語“an”と“the”のそれぞれに
ついて、INSCOREがボックス２３３と２３５によって表
わされる。単語が２つ以上のノードの出力に接続され得
るので、比較は必須である。そして、最少の累積距離を
有するパスのみが接続単語へ成長される。単語の一時的
格納場所INSCOREに格納された累積距離は、図７に示さ
れるステップＳ５７における処理の間に、その単語のエ
ントリステートを更新するのに用いられる。

【００８９】次に、システムは、ステップＳ１６９にお
いて、Ｄ［ｖ］が特大値HUGEに等しいかどうかをチェッ
クする。等しい場合、これは、そこで終了する有効パス
が無く、また、次のフレームｆ_k+1にて現ノードｖを通
ってこれに接続される単語へ通じる有効パスも無いこと
を表わしている。一方、Ｄ［ｖ］が特大値HUGEよりも小
さい場合、有効パスがそのノードｖで終るか、有効パス
がそれを通り抜けてそれに接続されている単語へ通じる
かのいずれかである。従って、次の入力フレームｆ_k+1
にて潜在的なアクティブステート（およびノード）の数
を表わすカウンタPACOUNTが、ステップＳ１７１でイン
クリメントされる。ノードに関連する無音ステートが次
の入力フレームｆ_k+1でアクティブとなることがあるか
らである。ノードポインタｖは、その後、ステップＳ１
７３でインクリメントされ、ノードポインタｖは言語モ
デル２１における次のノードを指すこととなる。次にシ
ステムは、ステップＳ１７５において、言語モデル２１
における全てのノードが処理されたかどうかをチェック
する。これは、ノードポインタｖが言語モデル２１のノ
ードＮnを超えたノードを指しているかどうかをチェッ
クすることでなされる。システムが全てのノードの処理
を終えていない場合、処理はステップＳ１５５へ戻る。
一方、全てのノードの処理が終っていれば、処理は図７
に示されるステップＳ５３へ戻る。

【００９０】次に、図７に示されるステップＳ５７にお
いて実行される処理について、図１６及び図１７を参照
しながら、図８に示される単語モデル２０１と図９に示
される動的計画法によるパスに関して、より詳細に説明
する。図１６において、ステップＳ１８１で、システム
は、INSCOREに格納されている累積距離が特大値HUGEと
等しいかどうかをチェックする。等しい場合、それは、
次回のポイントにおいてこの単語に入る有効パスが存在
しないことを意味する。従って、この単語は再び処理さ
れる必要は無く、よって、処理はそのままステップＳ２
０７へ進む。ステップＳ２０７においては、次に入力さ
れるフレームｆ_k+1に関して処理される単語のためのア
クティブステートの数（それは、図１０に示されるステ
ップＳ８３によって現アクティブリスト２０３となった
りスト中に登録されているステートの数から決定され
る）が、カウンタPACOUNTに加えられる。次に処理は、
図７に示されるステップＳ５９へ戻り、単語カウンタを
インクリメントし、次の単語モデルが処理されるように
する。

【００９１】一方、ステップＳ１８１にて、INSCOREが
特大値HUGEと等しくない場合、これは、有効パスがすぐ
前の単語を出て、処理中の現単語へ入る可能性があるこ
とを意味する。よって、他の単語モデルから伸びるパス
によって到達され得る現単語モデルのステート（これ
は、以下ではエントリステート称される）が、INSCORE
に格納されている累積距離を用いて更新されなければな
らない。本実施形態に於いては、上述の動的計画法の制
約で、エントリステートはＳ₀、Ｓ₁およびＳ₂のいずれ
かである。この更新は、図１３を参照して説明したのと
類似の処理テクニックを用いても達成され得るが、本実
施形態においては以下の方法が用いられる。

【００９２】まず、ステップＳ１８３において、システ
ムは、処理中の現単語を表す単語モデルが３つ以上のス
テート（出口ステートＳ_Dや番人ステートＳ_SENは含まな
い）を含むかどうかチェックする。３つ以上のステート
があった場合は、ステップＳ１８５において、ステート
ポインタｊがステートＳ₂を指すようにセットされる。
一方、現単語中に３つ未満のステートしか存在しない場
合は、ステップＳ１８７においてステートポインタｊが
出口ステートＳ_Dを指すようにセットされる。次に処理
は、ステップＳ１８９へ進み、ポインタｊによって指定
されるステートが最終アクティブポインタＬＡによって
示されるステートと比較される。ポインタｊによって指
定されるステートが最終アクティブポインタＬＡによっ
て指定されるステートを超えている場合、当該ステート
に既に格納されている累積距離とINSCOREに格納されて
いる累積距離との間で比較がなされなければならない。
図９に示されるパス、例えばパスＰ６は、次のフレーム
ｆ_k+1で、ステートＳ₁、Ｓ ₂、Ｓ₃及びＳ₄に成長し得
る。従って、この例において、図１０に示されるフロー
チャートに従って現アクティブリスト２０３上の全ての
アクティブステートを処理した後、最終アクティブポイ
ンタＬＡはステートＳ₁を指すようになる。

【００９３】図１７は、図８に示されている単語モデル
２０１のエントリステート（即ち、最初の３つのステー
ト）を示す。図１７に示されているように、最終アクテ
ィブポインタＬＡはステートＳ₁を指す。単語モデル２
０１には、３つより多いステートがあるので、ステート
ポインタｊはステートＳ₂を指す。従って、システムは
ステップＳ１８９において、ポインタｊによって指定さ
れているステートが最終アクティブポインタＬＡによっ
て指定されているステート、即ちステートＳ₁を超えて
いると判断する。それゆえ、処理はステップＳ１９１へ
進む。ステップＳ１９１において、システムは、ステー
トＳ₂に格納されている累積距離と単語モデル２０１に
関連する一時的な格納部INSCOREに格納されている累積
距離とを比較する。なお、INSCOREは、図１７において
矩形ボックス２４１によって表されている。INSCOREに
格納されている累積距離がステートＳ₂に格納されてい
る累積距離よりも小さい場合、ステップＳ１９３におい
てINSCOREの値がステートＳ₂にコピーされる。そして、
処理は、ステップＳ１９３へ進む。INSCOREに格納され
ている累積距離がステートＳ₂に格納されている累積距
離よりも大きい場合は、ステートＳ₂に格納されている
累積距離は変更されず、処理はステップＳ１９７へ進
む。ステップＳ１９７において、ポインタｊは、デクリ
メントされ、ステートＳ₁を指定する。その後、処理は
ステップＳ１８９へ戻り、ステートＳ₁に対して同じ処
理が実行される。

【００９４】ステートＳ₁を処理した後、ステップＳ１
９７において、ポインタｊがステートＳ₀を指定するよ
うに再度決定される。ステップＳ１８９の後、処理はス
テップＳ１９８に進む。ステップＳ１９８において、シ
ステムは処理すべき更なるステートがあるかどうかをチ
ェックする。本例の場合、ステートＳ₀がなお処理され
るべきであるので、システムはステップＳ１９９へ進
み、INSCOREに格納された累積距離がステートＳ₀にコピ
ーされる。ここで、ステートＳ₀は最終のアクティブポ
インタによって指定されている最後のアクティブステー
トの前のステートなので、ステートＳ₀に関して累積距
離の比較を実行する必要はない。そして、システムは、
ステップＳ２０１において、図１３ａに示されるステッ
プＳ１３３において現アクティブリストへ加えられるべ
き最終ステートであった番人ステートＳ_SENに上書きし
て、ステートＳ₀を、現アクティブリスト（図１０のス
テップＳ８３より前では新アクティブリスト２０５であ
ったもの）に加える。次にシステムは、ステップＳ２０
３において、ポインタｊをデクリメントし、ステートＳ
_-1を指定するようにする。処理はステップＳ１９８に戻
り、システムは現単語にはこれ以上の処理すべきエント
リステートが存在しないと判断する。そして、処理は、
ステップＳ２０４へ進み、番人ステートＳ_SENが現アク
ティブリストの終わりに再び加えられる。これは、番人
ステートＳ_SENがステップＳ２０１で上書きされてしま
っているからである。そして、ステップＳ２０４の後、
処理はステップＳ２０５へ進み、対応する一時的格納場
所INSCOREに格納されている累積距離を特大値HUGEにリ
セットする。現アクティブリスト上のステートの数は、
ステップＳ２０７においてカウンタPACOUNTに加えら
れ、処理は図７に示されるステップＳ５９へ戻る。

【００９５】［刈り込み］再び図７を参照すると、ステ
ップＳ６３においてシステムがさらに処理すべき入力フ
レームがあると判断した場合、処理はステップＳ６５へ
進み、刈り込み閾値Ｔｈが調整される。刈り込みを用い
ることの目的は、同時に一つのポイントから次のポイン
トへ成長する動的計画法のパスの数を制限することであ
る。特に、本実施形態は、実際に処理されるアクティブ
ステートの数が実質的に前もって決められた制限内に収
まるように、刈り込み閾値を調整することを目的とす
る。この制限は、作業メモリ容量と許容される処理時間
とにより定められる。さらに、本実施形態は、高価な計
算的なオーバーヘッド無しにこれを達成することも目的
としている。

【００９６】設定された数のアクティブステートだけが
各入力フレームのために処理されることを確実にするた
めの一つの方法は、まさに処理される入力フレームに関
する全てのアクティブリスト上にあるアクティブステー
トを、それらに格納された累積距離の増大する順番にソ
ートし、最小の累積距離を持つものから所望の数のステ
ートを処理することである。しかしながら、このテクニ
ックでは、アクティブステートをソートするのに多大な
計算時間が必要となる。本実施形態において用いられる
テクニックでは、この計算的に高価な並べ替えを実行す
るのではなく、最終の入力フレームを処理した後に有効
な情報を用いる。特に本実施形態において、差分値（PR
UNING）は、次の処理されるべき入力フレームに対して
潜在的にアクティブなステートの数（PACOUNTに格納さ
れる）に依存して、実際に処理されるステートの数を２
つの閾値の間に存在するべく維持するために変化する。
以下、差分値PRUNINGを変化させる方法について図１８
を参照して詳細に説明する。

【００９７】ステップＳ２１１において、システムは処
理されるべき次のフレームに関して潜在的にアクティブ
なステートの数（PACOUNTに格納されている）と、ステ
−ト閾値（STATETH）とを比較する。ここで、ステート
閾値STATETHは、有用なワークメモリの量によって決定
される絶対的に最大のステート閾値よりも小さいがそれ
に近い値にセットされる。PACOUNTに格納される値がSTA
TETHよりも小さい場合は、これは、全ての潜在的にアク
ティブなステートが処理され得ることを意味し、それゆ
え、前回のポイントで使用された差分値PRUNINGを増加
させることができる。従って、ステップＳ２１３におい
て、調整定数ｄｐ１が現在の差分値PRUNINGに加えられ
る。ｄｐ１の値は、あらゆるリーズナブルなローカル距
離よりも大きく設定される。よって、全てではないにし
ろ、潜在的なアクティブステートの大部分が処理され
る。

【００９８】次に、PRUNINGに格納されている値は、ス
テップＳ２１５において高い刈り込み閾値HIGHPRTHと比
較される。それより上に到達する必要のありえない最大
の差分値が存在すると仮定されるので、その上限が差分
値PRUNINGに設けられる。PRUNINGに格納されている値
が、HIGHPRTHよりも小さい場合は、処理はステップＳ２
１９へ進む。PRUNINGに格納されている値がHIGHPRTHよ
りも大きい場合は、ステップＳ２１７においてPRUNING
がHIGHPRTHと同じ値にセットされる。ステップＳ２１５
或いはＳ２１７の後、システムは刈り込み閾値Ｔｈをセ
ットする。そして、処理は図７に示されるステップＳ４
３へ戻る。

【００９９】一方、ステップＳ２１１にて、システムが
次のフレームに対する潜在的にアクティブなステートの
数、PACOUNTが、STATETHよりも大きいと判断した場合、
システムはステップＳ２２１において、前回の入力フレ
ームの処理の間アクティブで処理されたステートの数
（ACOUNTに格納されている）と、低ステート閾値LOWSTT
Hとを比較する。LOWSTTHの値は、ACOUNTがLOWSTTHより
小さい場合に多くの時間やメモリを使うことなく次の入
力フレームに対する全ての潜在的なアクティブステート
を処理可能であるようにし、それを確実に保証するべく
セットされる。従って、ACOUNTがLOWSTTHより小さい場
合、処理はステップＳ２２１からステップＳ２１３へ進
む。ステップＳ２１３では、差分値PRUNINGが調整さ
れ、処理は上述のように進む。一方、ACOUNTがLOWSTTH
より大きい場合は、全ての潜在的なアクティブステート
が処理される場合に多くの時間やメモリを処理に費やさ
ないという保証がない。したがって、差分値PRUNINGを
減らす必要がある。

【０１００】差分値PRUNINGが減少される必要があるか
どうかを判断するために、システムはステップＳ２２３
においてACOUNTをSTATETHと比べる。ACOUNTがSTATETHよ
りも小さい場合、システムはステップＳ２２４におい
て、差分値PRUNINGがHIGHPRTHと等しいかどうかをチェ
ックする。もしも、HIGHPRTHと等しければ、このことは
システムが全てのアクティブステートを処理しようとし
ていることを表し、従って、次の入力フレームに関して
処理されるであろうアクティブステートの数が処理にお
いて極めて長い時間もしくは極めて大きいメモリ量を要
することになる可能性は低い。従って、差分値PRUNING
は変更せず、処理はステップＳ２１９へ進み、刈り込み
閾値がセットされる。一方、差分値PRUNINGがHIGHPRTH
と等しくない場合（その場合、PRUNINGはHIGHPRTHより
小さくなければならない）、次の入力フレームに関して
処理されることになるアクティブステートの数が非常に
長い時間と非常に大量のメモリを費やすであろうことが
予測される。従って、処理されるべきアクティブステー
トの実際の数を計算し、見積もらなければならない。こ
れは、変更されていない差分値PRUNINGを用いてステッ
プＳ２３１においてセットされた刈り込み閾値を用い
て、ステップＳ２３３にて実行される。

【０１０１】ステップＳ２２３に戻り、ACOUNTがSTATET
Hよりも大きいとシステムが判断した場合、差分値PRUNI
NGがステップＳ２２５において調整定数ｄｐ１だけ減じ
られる。差分値PRUNINGがステップＳ２２５において減
少させられた後、システムは、ステップＳ２２７におい
て、その差分値PRUNINGが低刈り込み閾値LOWPRTHより小
さいか否かを判断する。低刈り込み閾値は、次の入力フ
レームに関して処理されるであろうアクティブステート
の数が設定された緊急ステート閾値EMGSTTHより大きく
なることを確実にするために用いられる。この理由は、
刈り込みがきついと動的計画処理が失敗に終わるという
ことが見出されていることによる。差分値PRUNINGが低
刈り込み閾値LOWPRTHよりも小さい場合、ステップＳ２
２９において、差分値PRUNINGはLOWPRTHと同じ値にセッ
トされる。そして、ステップＳ２３１において、刈り込
み閾値Ｔｈが調整された差分値PRUNINGを用いて設定さ
れる。続いて、ステップＳ２３３において、システムは
次の入力フレームに関して処理されるであろうアクティ
ブステート（及びノード）の数をみつもる。この見積も
りは、まず、直前の入力フレームの処理の間に処理され
たアクティブステートの数、即ち、ACOUNTを、直前の入
力フレームの処理の間に用いられたPRUNINGの値で割る
ことによりステート密度を見積もり、次に、見積もられ
たステート密度にPRUNINGの新たな値を乗ずることによ
って、次の入力フレームに関して処理されるであろうア
クティブステートの数を見積もることでなされる。

【０１０２】見積もられた数Ｅｎ_saが、緊急ステート閾
値EMGSTTHよりも小さい場合、セットされている刈り込
み閾値は小さすぎであり、処理はステップＳ２１３に戻
り、差分値PRUNINGが増加され、刈り込み閾値が再設定
される。Ｅｎ_saがEMGSTTHよりも小さくない場合、Ｅｎ
_saはステップＳ２３７においてlowstthと比較される。
Ｅｎ_saがLOWSTTHよりも大きい場合は、これは、ステッ
プＳ２３１でセットされた刈り込み閾値Ｔｈが受け入れ
うるものであることを意味する。そして、処理は終了
し、図７に示されるステップＳ４３に戻る。一方、Ｅｎ
_saがLOWSTTHよりも小さい場合、刈り込み閾値は増加さ
せ得るものであり、よって、ステップＳ２３９において
第２の調整定数ｄｐ２が差分値PRUNINGに加えられ、刈
り込み閾値がステップＳ２１９にて再度設定される。な
お、本実施形態において、第２の調整定数ｄｐ２は、調
整定数ｄｐ１の１／２に設定されている。

【０１０３】図１８に示されるステップＳ２１９とＳ２
３１において、刈り込み閾値Ｔｈが設定される。この設
定は、まさに処理された入力フレームに対して決定され
た最終的な（全体の）最小累積距離MINSCOREに、まさに
計算された変数差分値（PRUNING）を加えることにより
なされ得る。しかしながら、発明者等は、全体として最
適なパスが、正しい単語の最初の少数のステートを横切
る場合、全体として最適なパスと局所的な最小値との間
の差が最大になる傾向があることを見いだした。従っ
て、本実施形態においては、刈り込み閾値は単語の始め
に近い部分でより大きく、その単語の終わりに向かって
より小さくなるように調整される。本実施形態におい
て、これは、図１９に示されるように、各単語の最初の
５つのステートに対して第１の刈り込み閾値Ｔｈ₁を用
い、各単語の次の５つのステートに対して第２の刈り込
み閾値Ｔｈ₂を用い、各単語の残りのステートに対して
第３の刈り込み閾値Ｔｈ₃を用いることにより実現され
る。本実施形態において、３つの刈り込み閾値Ｔｈ₁、
Ｔｈ₂、Ｔｈ₃は以下のようにして決定される。即ち、 Ｔｈ₁＝MINSCORE＋PRUNING Ｔｈ₂＝MINSCORE＋0.75・PRUNING Ｔｈ₁＝MINSCORE＋0.5・PRUNING。

【０１０４】当業者は理解するであろうが、実行されて
いる刈り込みは各パスについてさらに成長すべきか否か
に関して厳密な決定を行う。特に、刈り込み閾値よりも
低い全てのものが処理され、高いものは刈り込まれる。
そのような厳密な刈り込みテクニックを実行するに際し
ての問題は、認識結果のエラーにつながる刈り込み誤差
の可能性の増加にある。これは、全体として最適化され
たパスに関する累積距離が刈り込み閾値よりも大きい場
合、全体として最適なパスが刈り込まれてしまったその
時点で、全体として最適なパスの現ステートの近隣にあ
るステートはこれに類似の累積距離を有し、それらもま
たこのハードな刈り込みテクニックによって刈り込まれ
てしまうことになるということによる。従って、より柔
軟な刈り込みテクニックを適用することにより改良され
た刈り込みが達成され得る。この柔軟な刈り込みでは、
閾値を囲む領域を設け、その領域に入る全てではないい
くつかのパスが刈り込まれることになる。従って、たと
え最適なパスが刈り込まれてしまっても、最適パスに十
分に近いパスが残ることになり、刈り込みが認識エラー
に帰結することをなくす。

【０１０５】そのような柔軟な刈り込みテクニックは、
いくつかの異なる方法で達成され得る。例えば、所定の
範囲内の累積距離を有するパスの中からランダムに刈り
込まれるべきパスを選ぶのに、乱数発生器が用いられ得
る。しかしながら、そのような刈り込みの決定は全ての
アクティブステートに対して毎ステップ行われる必要が
あるので、できる限り単純にすべきである。さもない
と、刈り込みテクニックが過大な処理時間を必要として
しまう。本実施形態では、刈り込み閾値のベクトルＴ
［ｓ］が各入力フレームｆ_kに関して計算される。ベク
トルにおける刈り込み閾値の値は、まず、上述の３つの
刈り込み閾値Ｔｈ₁、Ｔｈ₂、Ｔｈ₃を計算し、図２０に
示されるように、ステート２、５、８等に対する適切な
刈り込み閾値から定数δを減算し、ステート０、３、６
等に対する適切な刈り込み閾値から２δを減算すること
で計算される。発明者等は、この３レベルの柔軟な刈り
込みが、１レベルの厳密な刈り込みテクニックと同じ刈
り込みエラー率で、処理されるべきアクティブステート
の数を３０％減少させることを確認している。

【０１０６】当業者は理解するであろうが、使用される
刈り込みレベルの数と各レベルの変更は、たとえ最適パ
スが刈り込まれても最適パスに十分に近いパスが残るよ
うに、使用されている動的計画法の制約に関連して選択
されるべきものである。

【０１０７】また、当業者は気づくことであろうが、刈
り込み閾値を変化させる上述の方法は、計算的に高価で
はなく、割り当てられた処理時間とメモリが超過される
ことのないように、各ポイントの時点で処理されるアク
ティブステートの数を限定するというように、刈り込み
閾値を調整可能とするものである。

【０１０８】図７に示される処理ステップのシーケンス
を用いて入力シーケンスにおける全てのフレームが処理
された後、動的計画処理によって決定された最適化パス
によって取られる正しいパスを決定するために、バック
トラッキングルーチンが要求される。本実施形態におい
て、バックトラッキングルーチンは、各パスがそれを通
って成長する、単語シーケンスを表すバックポインタを
追跡する。バックトラッキングルーチンが実行される方
法の詳細と、ポインタが発生される方法は音声認識の当
業者には周知であり、更なる説明は行わない。

【０１０９】［初期化］システムが入力発声の認識を試
みる前に、認識処理の間に用いられるシステムの閾値と
変数が初期化されなければならない。これは以下の方法
で達成される。まず、スタートノードＮ₀に格納された
累積距離がnominal値にセットされ、他の全ノードに格
納される累積距離が同一の大きい値HUGEにセットされ
る。次に、各単語モデルに関連して潜在的なアクティブ
ステートの数をカウントするカウンタPACOUNTをゼロに
セットし、各単語モデルに関連する一時的格納INSCORE
を大きな値HUGEにセットする。次に、全てのノードが処
理され、単語の入力に接続されるすべてのノードの累積
距離の最小値が、その単語に関連する一時的格納INSCOR
Eにコピーされる。これは、スタートノードＮ₀に接続さ
れる各単語の一時的格納INSCOREがnominal値にセットさ
れることを確実にする。最後に、各単語のINSCOREに格
納された値は、各単語モデルのエントリステートをアク
ティベートし初期化するために用いられる。処理ステッ
プは、各単語のモデルのエントリステートを初期化する
ために、図１６を参照して上述したエントリステートを
更新するために用いられる処理ステップに対して同一で
ある。刈り込み閾値と差分値PRUNINGも、最初の入力フ
レームの処理に先立って初期化される。特に、刈り込み
閾値Ｔｈ₁、Ｔｈ₂、Ｔｈ₃は大きな値HUGEにセットさ
れ、差分値PRUNINGは、高い刈り込み閾値HIGHPRTHにセ
ットされる。

【０１１０】［他の実施形態］いくつかの変形が、本発
明のコンセプトから外れることなく、上述の音声認識に
対してなし得る。これら変形のいくつかについて、以下
に説明する。

【０１１１】上述の実施形態においては、全発声が、処
理される前に受信される。しかしながら、システムは、
処理される発声を受信しながら漸進的に稼動するように
してもよい。そのような実施形態においては、入力バッ
ファは必要とされるが、１フレームに対応する入力音声
を格納することができるものであればよい。当業者は気
づくであろうが、このシステムを稼動させるために、入
力スピーチのフレームの全処理（プロセッサと認識ブロ
ックにより）が、入力音声の次のフレームを処理する準
備ができる前に完了しなければならない。

【０１１２】第１の実施形態においては、動的計画パス
の終わりにあった単語モデルのステートは、その単語モ
デルに関連するアクティブリストにリストされていた。
変形例においては、全単語モデルの全アクティブステー
トがリストされる単一のグローバルなアクティブリスト
が提供されてもよい。そのような変形例においては、ど
の単語モデルがその特定のアクティブステートに属する
かを示すために、グローバルなアクティブリストに関連
して情報が格納されなければならないであろう。

【０１１３】第１の実施形態においては、次回のステッ
プに対して各単語内で有効な動的計画法によるパスを成
長するのに含まれる処理を高速化するために、式（４）
が利用される。加えて、最も可能性の高いものが低いも
のよりも先にチェックされるようにサーチが組織され
た。１つの単語から次の単語へ有効な動的計画パスを成
長させるのに、類似の処理テクニックが用いられ得る。

【０１１４】第１の実施形態において、単語モデルのス
テートは、時間的継続において、認識されるべき入力音
声に対応する。変形例においては、単語モデルの各ステ
ートは、継続時間において、例えば、入力音声の３つの
連続するフレームと等価にしてもよい。そのような変形
例においては、入力フレームは３つのグループにおいて
平均化され、単語モデルのステートとともに並べられ得
る。

【０１１５】第１の実施形態においては、単語モデルを
通る一つの最良の動的計画パスが決定される。当業者に
よって理解されるように、Ｎ個の最良のマッチングを決
定するように容易にアルゴリズムを適用できる。よっ
て、認識結果にエラーがある場合、システムは、２回目
の認識のためにフレーズを再入力する必要なしに、代替
を提示することができる。

【０１１６】更に他の変形例において、単語モデルは統
計的なモデルであってもよい。統計モデルとしては、例
えば、音声認識の当業者にはよく知られた隠れマルコフ
モデルが挙げられる。そのような実施形態においては、
入力発音と単語モデルのシーケンスとの間の最小の累積
距離を決定するのではなく、隠れマルコフモデルの特定
のシーケンスにより入力シーケンスが生成されることの
最大の確率が決定される。

【０１１７】第１の実施形態において、使用される基準
モデルは全単語に対応する。当業者には明らかであろう
が、このことは本質的なことではない。基準モデルは、
例えば音節（syllable）のような単語の部分に対応して
もよいし、複数の単語に対応してもよいし、個々の音素
（phoneme）に対応してもよい。しかしながら、音素に
対応する基準モデルを使用することの欠点は、システム
が言語依存になることである。更に、全単語に等価な基
準モデルは、全フレーズに等価なものに対して好まし
い。時間に関するポテンシャルと計算量の節約があるた
めである。特に、フレーズ内の単語をモデル化すること
により、そして言語モデルを用いることにより、システ
ムに、適度な量の（handful）単語のみを用いて多くの
異なるフレーズを教えることが可能である。一方、全フ
レーズに対応された基準モデルの場合、基準モデルは、
システムによって学習されるべき種々のフレーズの各々
に要求されるであろう。この利点に加えて、単語に対応
する基準モデルの使用はフレーズ内の単語間のギャップ
によるシステムの柔軟性を増加させる。これは、フレー
ズの開始と終了及びフレーズ内の単語間にも現れ得る環
境モデルのおかげで可能である。

【０１１８】更にもう一つの変形例において、モデルの
連続するフレームが類似している場合、基準モデルは圧
縮されてもよい。このような状況が発生する場合、連続
する類似フレームは単一のフレームによって置き換えら
れる。

【０１１９】図１７に示される言語モデルにおいて、２
つの異なる単語が続き得る単語の場合、その単語に続く
２つの単語上には優先度（preference）は与えられな
い。しかしながら、他の実施形態において、いくつかの
単語シーケンスに他のものよりも好適に重み付けするこ
とが可能である。例えば、図１７ａにおいて示されるフ
レーズに関してフレーズ“make it more”（coulourが
後続する）が、フレーズ“make it smaller”、或いは
“make it larger”或いは“make it brighter”よりも
一般的である。従って、ノードＮ₇からノードＮ₈への遷
移は、ノードＮ₇から終端ノードＮ_nへの遷移に比べて強
い。これはノードＮ₇から単語“more”、“smaller”、
“larger”及び“brighter”の入力へ成長する累積距離
に重みをつける重み係数を用いることで達成される。

【０１２０】また、当業者には明らかであるように、許
容される単語のシーケンスを定義するのに用いられる言
語モデルは、ビグラム（Bigram）モデルである必要はな
く、例えば限定的なステートの文法モデルのような、周
知のいかなるタイプの言語モデルであってもよい。使用
される言語モデルのタイプが変更された場合、上述した
動的計画法マッチング処理にいくらかの変形が必要とな
るであろうが、そのような変形は音声認識の分野におけ
る当業者には明らかであろう。しかしながら、あらゆる
パターンマッチング処理に適するように設計されている
ので、マッチング処理の本質的な特徴は変化しない。

【０１２１】加えて、動的計画法によるマッチング処理
を実現する方法は、他のタイプのパターンマッチングに
も利用可能である事は、パターンマッチングの分野にお
ける当業者には明らかである。例えば、上述したパター
ンマッチング処理を、手書き文字認識や他のパターンマ
ッチングアプリケーションに利用することが考えられ
る。

【０１２２】連続的な単語音声認識システムが、上述の
第１の実施形態で説明されているが、上述のシステム型
の種類の音声認識システムに等価的に適用し得ることは
当業者には明らかであろう。

【０１２３】第１の実施形態において説明された音声認
識システムは、例えば、表計算パッケージ、グラフィッ
クパッケージ、文書処理パッケージ等の、多くの異なる
ソフトウエアアプリケーションに関連して用いることが
できる。音声認識システムがそのような複数のソフトウ
エアアプリケーションと共に用いられる場合、各アプリ
ケーションに関して別々の単語及び言語モデルを有する
ことが望ましい。特に、各アプリケーションで用いられ
るフレーズが異なる場合にはなおさらである。その理由
は、単語モデルの数が増加するにつれて、そして言語モ
デルのサイズが増加するにつれて、システムが入力音声
を認識するのに必要な時間が増えてしまうからである。
従って、各アプリケーションについて、個別の単語及び
言語モデルを持つことにより、音声認識システムの処理
スピードは維持され得る。加えて、いくつかの単語及び
言語モデルは各アプリケーションで共通に用いられる。

【０１２４】更に当業者にとって好ましいことに、上述
の音声認識システムは多くの異なるタイプのハードウエ
アにも適用可能である。例えば、パーソナルコンピュー
タ等における明白な使用とは別に、音声認識処理は、フ
ァクシミリ装置、電話、プリンタ、複写機、或いはマン
マシンインターフェースを有する他のあらゆる装置のユ
ーザインターフェースとして利用できる。

【０１２５】本発明は、上述の典型的な実施形態によっ
て限定されるものではなく、当業者には明らかであるよ
うに、他の種々の変形及び実施形態が可能である。

【０１２６】

【発明の効果】以上説明したように、本発明によれば、
マッチング処理の精度を維持しながら、成長する可能な
マッチングの数を効果的に減少させる、より効果的な刈
り込み処理が提供される。

【図面の簡単な説明】

【図１】本発明に係る実施形態が動作するためにプログ
ラムされ得るコンピュータの外観を示す図である。

【図２】音声認識システムの概要を示す図である。

【図３】例示的な複数の入力フレーズに関するトレーニ
ングプロセスの間に生成される言語モデルを表わす図で
ある。

【図４】動的計画法を用いて単語モデルに入力単語が連
携された場合において実行される処理を表わす図であ
る。

【図５】一つの入力フレームから次のフレームへの、許
容された状態遷移シーケンスを表わす図である。

【図６】図５に示される許容されたステート遷移シーケ
ンスを表わす図である。

【図７】第１の実施形態において用いられる、動的計画
法による整合技術を実現する処理手順を示すフローチャ
ートである。

【図８】単語モデル及び現アクティブリストと、それに
関連する新アクティブリストを示す図である。

【図９】基準モデル内で成長する動的計画法によるパス
のいくつかの例を示す図である。

【図１０】図７に示されるステップＳ４７において実行
される処理を示すフローチャートである。

【図１１】図９に示される２つの動的計画法によるパス
が現入力フレームから次の入力フレームへ成長する様子
を示す図である。

【図１２ａ】図８に示される単語モデルに関する現アク
ティブリスト中の最初のステートが処理された後の、図
８に示される新アクティブリストの内容を示す図であ
る。

【図１２ｂ】図８に示される単語モデルに関する現アク
ティブリスト中の２番目のステートが処理された後の、
図８に示される新アクティブリストの内容を示す図であ
る。

【図１３ａ】図１０に示されるステップＳ７７において
実行される処理を示すフローチャートである。

【図１３ｂ】図１０に示されるステップＳ７７において
実行される処理を示すフローチャートである。

【図１３ｃ】 図１０に示されるステップＳ７７におい
て実行される処理を示すフローチャートである。

【図１３ｄ】 図１０に示されるステップＳ７７におい
て実行される処理を示すフローチャートである。

【図１３ｅ】 図１０に示されるステップＳ７７におい
て実行される処理を示すフローチャートである。

【図１４】図７に示されるステップＳ５１において実行
される処理を示すフローチャートである。

【図１５】図１４において示される処理の間に、ノード
Ｎに対して実行される処理を示す図である。

【図１６】図７に示されるステップＳ５７において実行
される処理を示すフローチャートである。

【図１７】図８において示される単語モデルのエントリ
ステートを説明する図である。

【図１８】図７のステップＳ６５において実行される処
理を示すフローチャートである。

【図１９】各単語のステートに対して用いられる異なる
刈り込み閾値をプロットした図である。

【図２０】各単語のステートに対して用いられる刈り込
み閾値の好ましいバリエーションをプロットした図であ
る。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 エリ ツィケル−ハンコック イギリス国 ジーユー２ ５ワイジェイ サリー， ギルドフォード， サリー リ サーチ パーク， オッカム ロード， オッカム コート １ キヤノン リサー チ センター ヨーロッパ リミテッド内 (72)発明者 ジュリアン リチャード シーワッド イギリス国 ジーユー２ ５ワイジェイ サリー， ギルドフォード， サリー リ サーチ パーク， オッカム ロード， オッカム コート １ キヤノン リサー チ センター ヨーロッパ リミテッド内

Claims (53)

【特許請求の範囲】
1. 【請求項１】 第１の信号を表わす第１信号パターン列
   と第２の信号を表わす第２信号パターン列とをマッチン
   グさせる方法であって、 前記第１の信号と前記第２の信号をマッチング処理を用
   いてマッチングし、該マッチング処理は各第１信号パタ
   ーンを順次に処理して所定のパス成長に関する制約を用
   いて複数のパスを成長させ、各パスは第２信号パターン
   の列と処理中の現第１信号パターンまでの第１信号パタ
   ーンの列との間の可能なマッチングを表わし、各パスは
   夫々にそのマッチングの近さを表わす累積値を有し、 第１信号パターンの各々の処理の間に前記累積値を刈り
   込み値と比較し、該比較ステップの結果に基づいてパス
   を破棄することにより、前記マッチングを制御し、 現第１信号パターンの処理の間の前記制御ステップにお
   いて複数の異なる刈り込み値が用いられ、与えられたパ
   スに対して該現第１信号パターンの処理の間に用いられ
   る刈り込み値は、前記第２の信号を表わすパターン列内
   における、処理中の現第１信号パターンに対して与えら
   れたパスが終端とする第２信号パターンの位置に依存す
   ることを特徴とするマッチング方法。
2. 【請求項２】 後続する第１信号パターンについての前
   記比較ステップにおいて用いられる刈り込み値が、現第
   １信号パターンを処理した後に残る全てのパスの最少累
   積値に、前記位置に基づいて変化する変数を加えること
   により決定されることを特徴とする請求項１に記載のマ
   ッチング方法。
3. 【請求項３】 前記第２信号パターン列は複数のサブシ
   ーケンスグループにに分割され、現第１信号パターンの
   処理の間に前記比較ステップが各グループに対して異な
   る刈り込み値を用いることを特徴とする請求項１または
   ２に記載のマッチング方法。
4. 【請求項４】 現第１信号パターンの処理の間に、前記
   比較ステップは、最初のｎ個の第２信号パターンの一つ
   で終わるパスに対して第１の刈り込み値を用い、次のｍ
   個の第２信号パターンの一つで終わるパスに対して第２
   の刈り込み値を用い、残りの第２信号パターンの一つで
   終わるパスに対して第３の刈り込み値を用いることを特
   徴とする請求項１乃至３のいずれかに記載のマッチング
   方法。
5. 【請求項５】 現第１信号パターンの処理の間に、前記
   比較ステップは、前記第２の信号の終わりの方で終わる
   パスよりも、該第２の信号の始まりの方で終わるパスに
   対してより大きな刈り込み値を用いることを特徴とする
   請求項１乃至４のいずれかに記載のマッチング方法。
6. 【請求項６】 前記制御ステップは、厳密な刈り込み処
   理を実行し、それにより、対応する刈り込み値よりも悪
   い累積値を有するパスが破棄されることを特徴とする請
   求項１乃至５のいずれかに記載のマッチング方法。
7. 【請求項７】 前記制御ステップは、柔軟な刈り込み処
   理を実行し、それにより対応する刈り込み値よりも悪い
   累積値を有するいくつかのパスが破棄されずに残ること
   を特徴とする請求項１乃至５のいずれかに記載のマッチ
   ング方法。
8. 【請求項８】 前記制御ステップは、対応する刈り込み
   値を含む所定範囲内にある累積値を有するパスに対して
   前記柔軟な刈り込みを実行することを特徴とする請求項
   ７に記載のマッチング方法。
9. 【請求項９】 前記制御ステップは、対応する刈り込み
   値を含む所定範囲内にある累積値を有するパスをランダ
   ムに破棄することを特徴とする請求項８に記載のマッチ
   ング方法。
10. 【請求項１０】 前記制御ステップは、前記対応する刈
    り込み値に関連する前記累積値の値に基づいて、対応す
    る刈り込み値の所定範囲内にある累積値を有するパスを
    破棄することを特徴とする請求項８に記載のマッチング
    方法。
11. 【請求項１１】 前記第２信号パターンの列は複数のサ
    ブシーケンスに分割され、現在の第１信号パターンの処
    理の間に、前記比較ステップは前記グループの各々に対
    して異なる複数の刈り込み値を用いることを特徴とする
    請求項８に記載のマッチング方法。
12. 【請求項１２】 第２信号パターンの第１グループに関
    連する複数の刈り込み値は該第２信号パターンの後続の
    グループに対して用いられる複数の刈り込み値よりも大
    きいことを特徴とする請求項１１に記載のマッチング方
    法。
13. 【請求項１３】 グループの数、各グループに関連する
    異なる刈り込み値の数、そしてグループに関連する刈り
    込み値の間の差が、前記パスの成長に関する制約に基づ
    いて決定されることを特徴とする請求項１１または１２
    に記載のマッチング方法。
14. 【請求項１４】 与えられたパスに対して用いられる刈
    り込み値は、該与えられたパスの終端にある第２信号パ
    ターンに隣接する第２信号パターンで終わるパスに対し
    て用いられた刈り込み値に基づいて設定されることを特
    徴とする請求項１乃至１３のいずれかに記載のマッチン
    グ方法。
15. 【請求項１５】 前記変数は、直前の第１信号パターン
    の処理の間に成長したパスの数によっても変化すること
    を特徴とする請求項２に従属する記載のマッチング方
    法。
16. 【請求項１６】 前記マッチングステップは動的計画法
    によるマッチング処理を実行することを特徴とする請求
    項１乃至１５のいずれかに記載のマッチング方法。
17. 【請求項１７】 前記第１の信号は音声信号を表わし、
    前記第２の信号は基準音声信号を表わし、前記パターン
    の各々は、対応する時間フレームの間の音声信号に対応
    する音響的特徴を表わす複数のパラメータを備えること
    を特徴とする請求項１乃至１６のいずれかに記載のマッ
    チング方法。
18. 【請求項１８】 第１の信号を第２の信号にマッチング
    する、動的計画法によるパターンマッチングシステムで
    あって、可能なマッチングのために用いられる刈り込み
    閾値が該可能なマッチングの前記第２の信号における位
    置に基づいて設定されることを特徴とするパターンマッ
    チングシステム。
19. 【請求項１９】 第１の信号を表わす第１信号パターン
    列と第２の信号を表わす第２信号パターン列とをマッチ
    ングさせるマッチング装置であって、 前記第１の信号と前記第２の信号をマッチング処理を用
    いてマッチングし、該マッチング処理は各第１信号パタ
    ーンを順次に処理して所定のパス成長に関する制約を用
    いて複数のパスを成長させるマッチング手段と、各パス
    は第２信号パターンの列と処理中の現第１信号パターン
    までの第１信号パターンの列との間の可能なマッチング
    を表わし、各パスは夫々にそのマッチングの近さを表わ
    す累積値を有し、 第１信号パターンの各々の処理の間に前記累積値を刈り
    込み値と比較する比較手段と、 前記比較手段による比較の結果に基づいてパスを破棄す
    ることにより、前記マッチングを制御する制御手段とを
    備え、 前記制御手段が現第１信号パターンを処理する間におい
    て複数の異なる刈り込み値が用いられ、与えられたパス
    に対して該現第１信号パターンの処理の間に用いられる
    刈り込み値は、前記第２の信号を表わすパターン列内に
    おける、処理中の現第１信号パターンに対して与えられ
    たパスが終端とする第２信号パターンの位置に依存する
    ことを特徴とするマッチング装置。
20. 【請求項２０】 後続する第１信号パターンについての
    前記比較手段に用いられる刈り込み値が、現第１信号パ
    ターンを処理した後に残る全てのパスの最少累積値に、
    前記位置に基づいて変化する変数を加えることにより決
    定されることを特徴とする請求項１９に記載のマッチン
    グ装置。
21. 【請求項２１】 前記第２信号パターン列は複数のサブ
    シーケンスグループにに分割され、前記比較手段は、現
    第１信号パターンの処理の間に各グループに対して異な
    る刈り込み値を用いることを特徴とする請求項１９また
    は２０に記載のマッチング装置。
22. 【請求項２２】 現第１信号パターンの処理の間に、前
    記比較手段は、最初のｎ個の第２信号パターンの一つで
    終わるパスに対して第１の刈り込み値を用い、次のｍ個
    の第２信号パターンの一つで終わるパスに対して第２の
    刈り込み値を用い、残りの第２信号パターンの一つで終
    わるパスに対して第３の刈り込み値を用いることを特徴
    とする請求項１９乃至２１のいずれかに記載のマッチン
    グ装置。
23. 【請求項２３】 現第１信号パターンの処理の間に、前
    記比較手段は、前記第２の信号の終わりの方で終わるパ
    スよりも、該第２の信号の始まりの方で終わるパスに対
    してより大きな刈り込み値を用いることを特徴とする請
    求項１９乃至２２のいずれかに記載のマッチング装置。
24. 【請求項２４】 前記制御手段は、厳密な刈り込み処理
    を実行し、それにより、対応する刈り込み値よりも悪い
    累積値を有するパスが破棄されることを特徴とする請求
    項１９乃至２３のいずれかに記載のマッチング装置。
25. 【請求項２５】 前記制御手段は、柔軟な刈り込み処理
    を実行し、それにより対応する刈り込み値よりも悪い累
    積値を有するいくつかのパスが破棄されずに残ることを
    特徴とする請求項１９乃至２３のいずれかに記載のマッ
    チング装置。
26. 【請求項２６】 前記制御手段は、対応する刈り込み値
    を含む所定範囲内にある累積値を有するパスに対して前
    記柔軟な刈り込みを実行することを特徴とする請求項２
    ５に記載のマッチング装置。
27. 【請求項２７】 前記制御手段は、対応する刈り込み値
    を含む所定範囲内にある累積値を有するパスをランダム
    に破棄することを特徴とする請求項２６に記載のマッチ
    ング装置。
28. 【請求項２８】 前記制御手段は、前記対応する刈り込
    み値に関連する前記累積値の値に基づいて、対応する刈
    り込み値の所定範囲内にある累積値を有するパスを破棄
    することを特徴とする請求項２６に記載のマッチング装
    置。
29. 【請求項２９】 前記第２信号パターンの列は複数のサ
    ブシーケンスに分割され、現在の第１信号パターンの処
    理の間に、前記比較手段は前記グループの各々に対して
    異なる複数の刈り込み値を用いることを特徴とする請求
    項２６に記載のマッチング装置。
30. 【請求項３０】 第２信号パターンの第１グループに関
    連する複数の刈り込み値は該第２信号パターンの後続の
    グループに対して用いられる複数の刈り込み値よりも大
    きいことを特徴とする請求項２９に記載のマッチング装
    置。
31. 【請求項３１】 グループの数、各グループに関連する
    異なる刈り込み値の数、そしてグループに関連する刈り
    込み値の間の差が、前記パスの成長に関する制約に基づ
    いて決定されることを特徴とする請求項２９または３０
    に記載のマッチング装置。
32. 【請求項３２】 与えられたパスに対して用いられる刈
    り込み値は、該与えられたパスの終端にある第２信号パ
    ターンに隣接する第２信号パターンで終わるパスに対し
    て用いられた刈り込み値に基づいて設定されることを特
    徴とする請求項１９乃至３１のいずれかに記載のマッチ
    ング装置。
33. 【請求項３３】 前記変数は、直前の第１信号パターン
    の処理の間に成長したパスの数によっても変化すること
    を特徴とする請求項３０に記載のマッチング装置。
34. 【請求項３４】 前記マッチング手段は動的計画法によ
    るマッチング処理を実行することを特徴とする請求項１
    ９乃至３３のいずれかに記載のマッチング装置。
35. 【請求項３５】 前記第１の信号は音声信号を表わし、
    前記第２の信号は基準音声信号を表わし、前記パターン
    の各々は、対応する時間フレームの間の音声信号に対応
    する音響的特徴を表わす複数のパラメータを備えること
    を特徴とする請求項１９乃至３４のいずれかに記載のマ
    ッチング装置。
36. 【請求項３６】 コンピュータによって、第１の信号を
    表わす第１信号パターン列と第２の信号を表わす第２信
    号パターン列とをマッチングさせるマッチング処理を実
    行させるための処理プログラムを格納する記憶媒体であ
    って、該処理プログラムの備える処理ステップが、 前記第１の信号と前記第２の信号をマッチング処理を用
    いてマッチングし、該マッチング処理は各第１信号パタ
    ーンを順次に処理して所定のパス成長に関する制約を用
    いて複数のパスを成長させ、各パスは第２信号パターン
    の列と処理中の現第１信号パターンまでの第１信号パタ
    ーンの列との間の可能なマッチングを表わし、各パスは
    夫々にそのマッチングの近さを表わす累積値を有し、 第１信号パターンの各々の処理の間に前記累積値を刈り
    込み値と比較し、該比較ステップの結果に基づいてパス
    を破棄することにより、前記マッチングを制御し、 現第１信号パターンの処理の間の前記制御ステップにお
    いて複数の異なる刈り込み値が用いられ、与えられたパ
    スに対して該現第１信号パターンの処理の間に用いられ
    る刈り込み値は、前記第２の信号を表わすパターン列内
    における、処理中の現第１信号パターンに対して与えら
    れたパスが終端とする第２信号パターンの位置に依存す
    ることを特徴とする記憶媒体。
37. 【請求項３７】 後続する第１信号パターンについての
    前記比較ステップにおいて用いられる刈り込み値が、現
    第１信号パターンを処理した後に残る全てのパスの最少
    累積値に、前記位置に基づいて変化する変数を加えるこ
    とにより決定されることを特徴とする請求項３６に記載
    の記憶媒体。
38. 【請求項３８】 前記第２信号パターン列は複数のサブ
    シーケンスグループにに分割され、現第１信号パターン
    の処理の間に前記比較ステップが各グループに対して異
    なる刈り込み値を用いることを特徴とする請求項３６ま
    たは３７に記載の記憶媒体。
39. 【請求項３９】 現第１信号パターンの処理の間に、前
    記比較ステップは、最初のｎ個の第２信号パターンの一
    つで終わるパスに対して第１の刈り込み値を用い、次の
    ｍ個の第２信号パターンの一つで終わるパスに対して第
    ２の刈り込み値を用い、残りの第２信号パターンの一つ
    で終わるパスに対して第３の刈り込み値を用いることを
    特徴とする請求項３６乃至３８のいずれかに記載の記憶
    媒体。
40. 【請求項４０】 現第１信号パターンの処理の間に、前
    記比較ステップは、前記第２の信号の終わりの方で終わ
    るパスよりも、該第２の信号の始まりの方で終わるパス
    に対してより大きな刈り込み値を用いることを特徴とす
    る請求項３６乃至３９のいずれかに記載の記憶媒体。
41. 【請求項４１】 前記制御ステップは、厳密な刈り込み
    処理を実行し、それにより、対応する刈り込み値よりも
    悪い累積値を有するパスが破棄されることを特徴とする
    請求項３６乃至４０のいずれかに記載の記憶媒体。
42. 【請求項４２】 前記制御ステップは、柔軟な刈り込み
    処理を実行し、それにより対応する刈り込み値よりも悪
    い累積値を有するいくつかのパスが破棄されずに残るこ
    とを特徴とする請求項３６乃至４０のいずれかに記載の
    記憶媒体。
43. 【請求項４３】 前記制御ステップは、対応する刈り込
    み値を含む所定範囲内にある累積値を有するパスに対し
    て前記柔軟な刈り込みを実行することを特徴とする請求
    項４２に記載の記憶媒体。
44. 【請求項４４】 前記制御ステップは、対応する刈り込
    み値を含む所定範囲内にある累積値を有するパスをラン
    ダムに破棄することを特徴とする請求項４３に記載の記
    憶媒体。
45. 【請求項４５】 前記制御ステップは、前記対応する刈
    り込み値に関連する前記累積値の値に基づいて、対応す
    る刈り込み値の所定範囲内にある累積値を有するパスを
    破棄することを特徴とする請求項４３に記載の記憶媒
    体。
46. 【請求項４６】 前記第２信号パターンの列は複数のサ
    ブシーケンスに分割され、現在の第１信号パターンの処
    理の間に、前記比較ステップは前記グループの各々に対
    して異なる複数の刈り込み値を用いることを特徴とする
    請求項４３に記載の記憶媒体。
47. 【請求項４７】 第２信号パターンの第１グループに関
    連する複数の刈り込み値は該第２信号パターンの後続の
    グループに対して用いられる複数の刈り込み値よりも大
    きいことを特徴とする請求項４６に記載の記憶媒体。
48. 【請求項４８】 グループの数、各グループに関連する
    異なる刈り込み値の数、そしてグループに関連する刈り
    込み値の間の差が、前記パスの成長に関する制約に基づ
    いて決定されることを特徴とする請求項４６または４７
    に記載の記憶媒体。
49. 【請求項４９】 与えられたパスに対して用いられる刈
    り込み値は、該与えられたパスの終端にある第２信号パ
    ターンに隣接する第２信号パターンで終わるパスに対し
    て用いられた刈り込み値に基づいて設定されることを特
    徴とする請求項３６乃至４８のいずれかに記載の記憶媒
    体。
50. 【請求項５０】 前記変数は、直前の第１信号パターン
    の処理の間に成長したパスの数によっても変化すること
    を特徴とする請求項３７に従属する請求項のいずれかに
    記載の記憶媒体。
51. 【請求項５１】 前記マッチングステップは動的計画法
    によるマッチング処理を実行することを特徴とする請求
    項３６乃至５０のいずれかに記載の記憶媒体。
52. 【請求項５２】 前記第１の信号は音声信号を表わし、
    前記第２の信号は基準音声信号を表わし、前記パターン
    の各々は、対応する時間フレームの間の音声信号に対応
    する音響的特徴を表わす複数のパラメータを備えること
    を特徴とする請求項３６乃至５１のいずれかに記載の記
    憶媒体。
53. 【請求項５３】 第１の信号を表わす第１信号パターン
    列と第２の信号を表わす第２信号パターン列とをマッチ
    ングさせるパターンマッチング処理を遂行するための、
    コンピュータによって実行可能な処理ステップを搬送す
    る信号であって、該処理ステップが、 前記第１の信号と前記第２の信号をマッチング処理を用
    いてマッチングし、該マッチング処理は各第１信号パタ
    ーンを順次に処理して所定のパス成長に関する制約を用
    いて複数のパスを成長させ、各パスは第２信号パターン
    の列と処理中の現第１信号パターンまでの第１信号パタ
    ーンの列との間の可能なマッチングを表わし、各パスは
    夫々にそのマッチングの近さを表わす累積値を有し、 第１信号パターンの各々の処理の間に前記累積値を刈り
    込み値と比較し、該比較ステップの結果に基づいてパス
    を破棄することにより、前記マッチングを制御し、 現第１信号パターンの処理の間の前記制御ステップにお
    いて複数の異なる刈り込み値が用いられ、与えられたパ
    スに対して該現第１信号パターンの処理の間に用いられ
    る刈り込み値は、前記第２の信号を表わすパターン列内
    における、処理中の現第１信号パターンに対して与えら
    れたパスが終端とする第２信号パターンの位置に依存す
    ることを特徴とするコンピュータのための処理ステップ
    搬送信号。