複数の状態および接続アークを有する、単語レベル有限状態トランスデューサFSTに新しい文を追加する方法であって、前記新しい文のプレフィックス部分に一致する、既存の前記FST内の状態およびアークのプレフィックスサブセットを判定するステップと、前記FSTに、前記プレフィックス部分の後の前記新しい文の残りに対応する状態およびアークの新しいシーケンスを加えるステップと、前記新しい文のサフィックス部分に対応する、前記FST内の既存の状態およびアークのサフィックスサブセットを判定するステップと、前記サフィックス部分の前の前記新しいシーケンスの部分を前記サフィックスサブセットに接続し、前記新しい文を含み、全体的最適化基準を満たさない、修正されたFSTを生成するステップとを含む、方法。前記FSTは、音声アプリケーションFSTである、請求項1に記載の方法。前記新しい文は、音声アプリケーションのオンライン動作の間、FSTに動的に追加される、請求項2に記載の方法。前記新しい文は、オフライコンンパイルプロセスの間、FSTに追加される、請求項2に記載の方法。音声アプリケーションで使用するための修正されたFSTを動的に拡張するステップをさらに含む、請求項2に記載の方法。ハッシュテーブルは、プレフィックスサブセットを判定するために使用される、請求項1に記載の方法。前記ハッシュテーブルは、サフィックスサブセットを判定するために使用される、請求項1に記載の方法。複数の状態および接続アークを有する、単語レベル有限状態トランスデューサFSTから既存の文を除去する方法であって、前記既存の文のプレフィックス部分に一致し、前記FSTの少なくとも1つの他の文に対応する、前記FST内の状態およびアークのプレフィックスサブセットを判定するステップと、前記既存の文のサフィックス部分に一致し、前記FSTの少なくとも1つの他の文に対応する、前記FST内の状態およびアークのサフィックスサブセットを判定するステップと、前記FSTから、前記プレフィックスサブセットと前記サフィックスサブセットとの間の任意のアークおよび状態を除去し、前記既存の文を伴わず、全体的最適化基準を満たしていない、修正されたFSTを生成するステップとを含む、方法。前記FSTは、音声アプリケーションFSTである、請求項8に記載の方法。既存の文は、音声アプリケーションのオンライン動作の間、前記FSTから動的に除去される、請求項9に記載の方法。前記新しい文は、オフラインコンパイル動作の間、前記FSTに追加される、請求項9に記載の方法。音声アプリケーションで使用するための前記修正されたFSTを動的に拡張するステップをさらに含む、請求項9に記載の方法。前記ステップは、部分的一致プロセスを1回以上繰り返し、既存の文の複数のインスタンスをFSTから除去する、請求項8に記載の方法。前記ハッシュテーブルは、プレフィックスサブセットを判定するために使用される、請求項8に記載の方法。前記ハッシュテーブルは、サフィックスサブセットを判定するために使用される、請求項8に記載の方法。本発明の実施形態は、文を追加および除去するための単語レベル有限状態トランスデューサFSTを漸次的に修正する方法を対象とする。FST内の状態およびアークのプレフィックスサブセットは、文のプレフィックス部分に一致すると判定される。FST内の状態およびアークのサフィックスサブセットは、文のサフィックス部分に一致すると判定される。新しい文が、次いで、プレフィックスとサフィックスとの間の文の残りに対応するFST状態およびアークの新しいシーケンスをFSTに付与することによって、追加されることができる。既存の文は、プレフィックスサブセットとサフィックスサブセットとの間の任意のアークおよび状態を除去することによって、FSTから除去されることができる。結果として生じる修正されたFSTは、局所的に効率的であるが、極小化等の全体的最適化基準を満たさない。FSTは、音声アプリケーションFSTであってもよく、文は、音声アプリケーションのオンライン動作の間、動的に追加される、またはFSTから除去されてもよい。既存の文を除去するために、ステップは、部分的一致プロセスファジー除去において、1回以上、繰り返され、既存の文の複数のインスタンスをFSTから除去してもよい。ハッシュテーブル、例えば、特殊両用ハッシュテーブルが、プレフィックスサブセットおよび/またはサフィックスサブセットを判定するために使用されてもよい。全体的最適化基準は、FST極小化基準を含んでもよい。本発明の種々の実施形態は、全体的最適化より若干低度の局所最適化、例えば、漸次的局所極小化に基づく、文の単語レベルFSTへの追加および除去を使用して、FSTの動的修正を効率的に可能にするための技法を対象とする。局所極小化の特性は、全状態が、1を超えないアークのファンアウトを有するサフィックス経路にのみ適用する、極小化のより低度のバージョンである。長さNの文を前提とすると、本発明の実施形態は、ONのならし計算量に基づいて、FSTに追加/そこから除去を行なう、すなわち、これは、cNステップを超えないがcは、実装に対して一定であるが、N2ステップではない。これは、FSTを漸次的に構成し、全体的に最適化されたFSTとほぼ同じくらい効率的に音声をテキストにデコードするために使用され、また、FSTのオフライン静的コンパイルのためのメモリ消費を削減するのに役立ち得る。以下の議論は、音声認識アプリケーションの観点から提示されるが、本概念は、テキスト/音声、テキスト処理等の時間または空間効率的FSTを漸次的に構築する必要がある、任意のアプリケーションに拡張されることができる。図2A-Cは、本発明の一実施形態による、新しい文のプレフィックスおよびサフィックスの既存のFST内に既に存在するものとの共有に基づいて、線形時間計算量を伴う、文をFSTに追加する実施例を示す。注:再び、前述のように、FSAとFSTとの間の形式的区別は、実際には、本文脈では、むしろ些細なものであって、FSTからの入力/出力アークラベル対は、図を簡単にするために、単一ラベルが与えられる。図2Aは、文ABCのための単純な既存の単語レベルFSTを示す。新しい文ADCを本FSTに追加するために、最初に、FST内の状態およびアークのプレフィックスサブセットが、新しい文のプレフィックス部分に一致すると判定される。本具体的場合には、新しい文ADCを追加するための既存のプレフィックスサブセットは、既存の状態0および1およびその接続アークAであると判定されるであろう図2B。次に、FST内の状態およびアークのサフィックスサブセットは、新しい文のサフィックス部分に一致すると判定される。新しい文ADCの場合、サフィックスサブセットは、既存の状態2および3およびその接続アークCとなるであろう。新しい文は、次いで、プレフィックスとサフィックスとの間の文の残りに対応するFST状態およびアークの新しいシーケンスをFSTに加えることによって、追加されることができる。ADCを追加する場合、これは、アークDを状態1と2との間に追加することによって行なわれることができる図2C。結果として生じる修正されたFSTは、非既存の状態/アークのみ、追加されるが、極小化等の全体的最適化基準を満たさないという点において、局所的に効率的である。代わりに、少なくとも、より低度の漸次的極小化を満たす。ハッシュテーブルが、プレフィックスサブセットおよび/またはサフィックスサブセットを判定するために使用されてもよい。例えば、O1線形時間計算量のプレフィックスハッシュテーブルが、f状態、アークラベル→標的状態となるように使用され、それによって、全体的計算量が、ONほど悪化しないように保証することができる。また、種々のステップが行なわれる具体的順序は、重要ではない。図3A-Cは、共有サフィックスのために、新しい状態を既存のFSTに追加する別の実施例を示す。図3Aは、文AAAのための既存のFSTを示す。新しい文BAを追加するために、サフィックスAは、状態2を使用して、新しいアークBを状態0から状態2に追加することによって共有されることができる図3B。次いで、別の新しい文AABを追加するために、新しい状態4が、追加され、プレフィックスサブセットAAを受信し、状態2から状態3の既存のアークAが、状態4から状態3に複製され既存の文AAAを解析する、新しいアーク4B3が、新しい経路AABを完了するように追加される図3C。そのようなアプローチは、局所的に効率的となるであろうが、いくつかの点において、拡大するFSTは、全体的には非極小となる。例えば、図3Cにおいて修正されたFSTが、次いで、追加される別の新しい文BBを有する場合、既存のBプレフィックスが、識別され、新しいアークBが、状態2から状態3に追加されるであろう図4A。しかし、本新しいFSTは、状態4が、もはや要求されず、図4Bに示されるように、除去され得るため、全体的に極小化されず、依然として、AAA、BA、AAB、およびBBの全てかつそれらのみを正しく解析する。しかし、プロセスの容易性は、全体的非極小性の僅かな漸次的損失に勝る。既存のFSTへの文の追加に加え、既存の文はまた、例えば、後の使用のためのフリーリストによって、プレフィックスサブセットとサフィックスサブセットとの間の任意のアークおよび状態を除去することによって、FSTから除去されることができる。ハッシュテーブルが、そのような除去プロセスに関連して有用であり得る。例えば、プレフィックスハッシュテーブルは、潜在的一致の開始状態に素早くアクセスすることができる。したがって、p→Opは、入力ラベルpに一致するハッシュテーブルにアクセスする。もう使われていないアークのみ、除去される必要がある。既存のFSTから文を除去するための具体的プロセスの1つは、図5A-Bに示されるように、完全一致アプローチに基づいてもよい。図5Aは、文AAAおよびBAを解析する、既存のFSTを示す。文を除去するために、任意の残りのプレフィックスおよび/またはサフィックスが、最初に、判定され、留保されなければならない。例えば、文AAAを除去および、BAを留保するために、留保すべきプレフィックスは存在しないが、BAのAサフィックスが、識別され、留保され、したがって、サフィックスサブセット2、A、3は、留保されるすなわち、状態2および3ならびにそれらの間のアークエッジAは:である一方、AAのための経路の残りは、除去される:状態1ならびに図5Bに示されるように、-1。アーク/状態除去ステップは、部分的一致プロセスにおいて、1回以上、繰り返され例えば、繰り返しのための試験は、ハッシュテーブル内の衝突の検査に基づいてもよい、既存の文または文の断片の複数のインスタンスをFSTから除去してもよい。例えば、図6Aは、文AAAおよびBAを解析する、図5Aにおけるような既存のFSTを示す。既存の部分的文Aを除去するために、第1のインスタンスが、アーク内に見出され、除去され-1、次いで、部分的文Aの全インスタンスが識別され、除去されるまで、本方法を繰り返し、次に、を除去する図6B。再び、ハッシュテーブルが、本実装のために有用であり得る。例えば、修正されたプレフィックスハッシュ関数fアークラベル→標的状態を使用する。そのような部分的一致アプローチは、文追加が、もはや十分に効率的ではなくなり得るように、衝突の数を大幅に増加させ得る。結果として生じるデータ構造が、唯一、ハッシュ関数だけ異なるように、慎重に選定されたハッシュ関数およびグループアクセス追加、除去を使用することが有用となり得る。図7は、本発明の一実施形態による、修正されたFST配列を使用するシステムの実施形態、この場合、音声アプリケーションFSTのための基本アーキテクチャを示し、これは、音声アプリケーションのオンライン動作の間、文を動的に追加および除去する、すなわち、システムは、ランタイム時に修正されることができる。コンパイラ703は、HMMユニットシーケンス702すなわち、音響モデルを伴う、漸次的に極小化される単語レベルFST701すなわち、言語モデルのランタイム拡張を行い、音声アプリケーションにおける未知の音声入力の音声認識のために、HMM-ユニット/単語FST704その上で、コンパイラ703はまた、決定化および局所極小化も行なうを生成する。また、HMM-ユニット/単語FST704が、厳密に全体的に極小化されるのではなく、前述のように、漸次的に構築される間すなわち、認識の間、依然として、商業用途に有益であるために十分にコンパクトかつ効率的であって、付加的計算は、回避される。いくつかの実施形態では、ランタイム拡張は、行なわれてもよい、または行なわれなくてもよい、随意のステップであってもよい。HMM-ユニット/単語FSTはまた、直接、漸次的極小化を使用して構築されることもできる。しかしながら、冗長な発音等の種々の要因のためかつ、1回以上、使用され得る、本アプローチは、追加/除去ステップのために、より多くのオーバーヘッドを要求し得る。したがって、具体的実施形態は、本理由から、認識の間、音訳を動的に拡張するように選定してもよい。本発明の実施形態は、任意の従来のコンピュータプログラミング言語内に全体的または部分的に実装されてもよい。例えば、好ましい実施形態は、手続き型プログラミング言語例えば、Cまたはオブジェクト指向プログラミング言語例えば、C、Python内に実装されてもよい。本発明の代替実施形態は、事前にプログラムされたハードウェア要素、他の関連構成要素、またはハードウェアおよびソフトウェア構成要素の組み合わせとして実装されてもよい。実施形態は、コンピュータシステムと併用するためのコンピュータプログラム製品として、全体的または部分的に実装されることができる。そのような実装は、コンピュータ可読媒体例えば、ディスケット、CD-ROM、ROM、フラッシュROMのような電気的に消去可能なROM、または固定ディスク等の有形媒体上に固定されるか、あるいはモデムまたは他のインターフェースデバイス、例えば、媒体を経由してネットワークに接続される通信アダプタ等を介して、コンピュータシステムに伝送可能であるかのいずれかである、一連のコンピュータ命令を含んでもよい。媒体は、有形媒体例えば、光学またはアナログ通信回線あるいは無線技法例えば、マイクロ波、赤外線、または他の伝送技法を用いて実装される媒体のいずれかであってもよい。一連のコンピュータ命令は、システムに関して、本明細書に前述された機能性の全部または一部を具現化する。当業者は、そのようなコンピュータ命令が、多くのコンピュータアーキテクチャまたはオペレーティングシステムと併用するために、いくつかのプログラミング言語で書かれることができることを理解するはずである。さらに、そのような命令は、任意のメモリデバイス、例えば、半導体、磁気、光学、または他のメモリデバイス内に記憶されてもよく、任意の通信技術、例えば、光学、赤外線、マイクロ波、または他の伝送技術を使用して伝送されてもよい。そのようなコンピュータプログラム製品は、付随の印刷または電子文書を伴う可撤性媒体例えば、市販のソフトウェアとして流通される、コンピュータシステムにプリインストールされる例えば、システムROMまたは固定ディスク上、あるいはサーバまたは電子掲示板から、ネットワーク例えば、インターネットまたはWorldWideWebを経由して流通され得ることが予期される。当然ながら、本発明のいくつかの実施形態は、ソフトウェア例えば、コンピュータプログラム製品およびハードウェアの両方の組み合わせとして実装されてもよい。さらに、本発明の他の実施形態は、全体的にハードウェアとして、または全体的にソフトウェア例えば、コンピュータプログラム製品として、実装される。本発明の種々の例示的実施形態が開示されたが、本発明の真の範囲から逸脱することなく、本発明の利点のいくつかを達成するであろう、種々の変更および修正が行なわれ得ることは、当業者に明白となるはずである。