English 中文(简体)
How to perform FST (Finite State Transducer) composition
原标题:

Consider the following FSTs :

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

How do I perform the composition operation on these two FSTs (i.e. T1 o T2) I saw some algorithms but couldn t understand much. If anyone could explain it in a easy way it would be a major help.

Please note that this is NOT a homework. The example is taken from the lecture slides where the solution is given but I couldn t figure out how to get to it.

最佳回答

Since you didn t specify the input format, I m assuming that 0 is the initial state, any integers that appear in the second column but not the first are accepting states (3 for T1 and 2 for T2), and each row is an element of the transition relation, giving the the previous state, the next state, the input letter and the output letter.

Any operation on FSTs needs to produce a new FST, so we need states, an input alphabet, an output alphabet, initial states, final states and a transition relation (the specifications of the FSTs A, B and W below are given in this order). Suppose our FSTs are:

A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)

and we want to find

W = (R, Σ, Δ, R0, RF, ω) = A ∘ B

Note that we don t need to determine the alphabets of W; the definition of composition does that.

Imagine running A and B in series, with A s output tape fed as B s input tape. The state of the combined FST is simply the combined states of A and B. In other words, the states of the composition are in the cross product of the states of the individual FSTs.

R = Q × P

In your example, the states of W would be pairs of integers:

R = {(0,0), (0,1), ... (3, 2)}

though we could renumber these and get (for example):

R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}

Similarly, initial and accepting states of the composed FST are the cross products of those in the component FSTs. In particular, R accepts a string iff A and B both accept the string.

R0 = Q0 × P0
RF = QF × PF

In the example, R0 = {00} and RF = {32}.

All that remains is to determine the transition relationship ω. For this, combine each transition rule for A with every transition rule for B that might apply. That is, combine each transition rule of A (qi, σ) → (qj, γ) with every rule of B that has a "γ" as the input character.

ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α, 
                                     (ph, γ) → (pk, δ) ∈ β}

In the example, this means combining (e.g.) 0 1 a : b of T1 with 0 1 b : a and 1 2 b : a of T2 to get:

00 11 a : a
01 12 a : a

Similarly, you d combine 0 2 b : b of T1 with those same 0 1 b : a and 1 2 b : a of T2, 0 0 a : a of T1 with 1 1 a : d and 1 2 a : c of T2 &c.

Note that you might have unreachable states (those that never appear as a "next" state) and transitions that will never occur (those from unreachable states). As an optimization step, you can remove those states and transitions. However, leaving them in will not affect the correctness of the construction; it s simply an optimization.

问题回答

If you are more amenable to graphical explanations, the following set of slides provides incremental, graphical examples of the composition algorithm in practice, and also includes discussion of epsilon transitions in the component transducers. Epsilon transitions complicate the composition process, and the algorithm described in outis answer may not generate the correct result in this case, depending on the semiring being used.

See slides 10~35 for some graphical examples:

http://www.gavo.t.u-tokyo.ac.jp/~novakj/wfst-algorithms.pdf

T1 and T2T1 and T2

Composition of T1 and T2T1.T2( composition

The states of the composition T are pairs of a T1 state and a T2 state. T satisfies the following conditions:

  1. its initial state is the pair of the initial state of T1 and the initial state of T2
  2. Its final states are pairs of a final state of T1 and a final state of T2
  3. There is a transition t from (q1, q2) to (r1, r2) for each pair of transitions T1 from q1 to r1 and T2 from q2 to r2 such that the output label of T1 matches the input label of T2. The transition T takes its input label from T1, its output label from T2, and its weight is the combination of the weights of T1 and T2 done with the same operation that combines weights along a path.

Since there are no weights we can ignore this. Above was picked up exactly from a following beautiful paper. Link here





相关问题
Java Stanford NLP: Part of Speech labels?

The Stanford NLP, demo d here, gives an output like this: Colorless/JJ green/JJ ideas/NNS sleep/VBP furiously/RB ./. What do the Part of Speech tags mean? I am unable to find an official list. Is it ...

Java Stanford NLP: Find word frequency?

I m using the Stanford NLP Parsing toolkit. Given a word in the lexicon, how can I find its frequency*? Or, given a frequency rank, how can I determine the corresponding word? *in the entire language,...

c/c++ NLP library [closed]

I am looking for an open source Natural Language Processing library for c/c++ and especially i am interested in Part of speech tagging.

Clustering text in Python [closed]

I need to cluster some text documents and have been researching various options. It looks like LingPipe can cluster plain text without prior conversion (to vector space etc), but it s the only tool I ...

Natural language rendering

Do you know any frameworks that implement natural language rendering concept ? I ve found several NLP oriented frameworks like Anthelope or Open NLP but they have only parsers but not renderers or ...

热门标签