FST (Finite State Transducer) 合成の実行方法
https://stackoverflow.com/questions/2649474
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
次の FST を考慮してください。
T1
0 1 a : b
0 2 b : b
2 3 b : b
0 0 a : a
1 3 b : a
T2
0 1 b : a
1 2 b : a
1 1 a : d
1 2 a : c
これら 2 つの FST で合成操作を実行するにはどうすればよいですか (すなわち、T1 O T2）いくつかのアルゴリズムを見ましたが、あまり理解できませんでした。誰かがそれを簡単に説明できれば、それは大きな助けになるでしょう。
これは宿題ではないことに注意してください。この例は、解決策が記載されている講義スライドから抜粋されたものですが、その解決方法がわかりませんでした。
解決
入力形式を指定しなかったため、0 が初期状態であると仮定します。最初の列ではなく 2 番目の列に表示される整数は状態を受け入れます (T1 の場合は 3、T2 の場合は 2)。各行は次のようになります。前の状態、次の状態、入力文字、出力文字を与える遷移関係の要素。
FST に対する操作はすべて新しい FST を生成する必要があるため、状態、入力アルファベット、出力アルファベット、初期状態、最終状態、遷移関係が必要です (以下の FST A、B、W の仕様はこの順序で与えられます) ）。FST が次のようになっていると仮定します。
A = (Q, Σ, Γ, Q0, QF, α) B = (P, Γ, Δ, P0, PF, β)
そして私たちは見つけたいのです
W = (R, Σ, Δ, R0, RF, ω) = A ∘ B
W のアルファベットを決定する必要がないことに注意してください。合成の定義がそれを行います。
A と B を直列に実行し、A の出力テープが B の入力テープとして供給されることを想像してください。結合された FST の状態は、単に A と B の状態を結合したものになります。言い換えれば、合成の状態は、個々の FST の状態の外積になります。
R = Q × P
あなたの例では、W の状態は整数のペアになります。
R = {(0,0), (0,1), ... (3, 2)}
ただし、これらに番号を付け直して、(たとえば) を取得することもできます。
R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}
同様に、合成された FST の初期状態と受け入れ状態は、コンポーネント FST の状態の外積になります。特に、R は文字列を受け入れます。 もし A と B はどちらも文字列を受け入れます。
R0 = Q0 × P0 RF = QF × PF
この例では、R0 = {00} および RF = {32}.
残っているのは、遷移関係 ω を決定することだけです。このために、A の各遷移ルールと、適用される可能性のある B のすべての遷移ルールを組み合わせます。つまり、A の各遷移規則を結合します。 (q私, σ) → (qj, γ) 入力文字として「γ」を含む B のすべてのルールを使用します。
ω = { ((q私,ph), σ) → ((qj, pk), δ) : (q私, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}
この例では、これは (例) を組み合わせることを意味します。 0 1 a : b T1の 0 1 b : a そして 1 2 b : a T2 の次のものを取得します。
00 11 a : a 01 12 a : a
同様に、次のように組み合わせます。 0 2 b : b T1のそれらと同じもの 0 1 b : a そして 1 2 b : a T2の、 0 0 a : a T1の 1 1 a : d そして 1 2 a : c T2 など
到達不可能な状態 (「次の」状態として決して表示されない状態) や、決して発生しない遷移 (到達不可能な状態からの状態) が存在する可能性があることに注意してください。最適化の手順として、これらの状態と遷移を削除できます。ただし、これらをそのままにしても、構築の正確さには影響しません。それは単なる最適化です。
他のヒント
グラフィカルな説明に適している場合、次のスライドのセットは、実際の構成アルゴリズムのインクリメンタルなグラフィカルな例を提供し、コンポーネントトランスデューサーのイプシロン遷移の議論も含めています。 Epsilon遷移は組成プロセスを複雑にし、Outisの回答に記載されているアルゴリズムは、使用されているセミングに応じて、この場合に正しい結果を生成しない場合があります。
いくつかのグラフィカルな例については、スライド10〜35を参照してください。
