summaryrefslogtreecommitdiff
path: root/decoder/apply_fsa_models.README
blob: d487c96d6c4057e374c6b75c61f6cb8898b3383a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
trie root and trie lhs2[lhs-nodeid] -> trie node

trie node edges (adj) - list of w,dest,p.  dest==0 means it's a completed rule (note: p is redundant with node e.dest->p-p, except in case of dest=0).  we will also use null_wordid (max_int) for dest=0 edges, but that doesn't matter

we intersect by iterating over adj and scoring w/ fsa.  TODO: index for sparse fsa; for now we assume smoothed ngram fsa where all items are scorable.

predicted items: we don't make copies of the pending predictions as we scan toward completion; instead, item backpointers are followed until the prediction (where backpointer=0).  such backpointer=0 items have a queue of prediction-originating items.

reusing completed items using a lookup on pair [NT,a] -> all [NT,a,b] lazy best-first.  b-next (right state) index in lazy index.

perhaps predictors need to register the # of items it has already mated with. (b-next index)

comb-like (cube) t-next (position in trie node edge list), b-next?  or just check chart and don't redup.  depends on whether we want just 1best or kbest deriv - diff. ways of reaching same result are good in kbest.

types of chart items:

A->t.*,a,b (trie node t) with mutable state t-next for generating successor lazily (vs. all at once)

A->t.B,a,b (t-next of A->t.* points to (B,t')): mutable state b-next for choosing which B->b,? to use.  note: such an item can't be queued immediately on its own, but can be added to the pending list of B->b,?

A->a,? - list of all known (b,inside prob) such that A[a,b].  we may also choose to represent this as A->.*,a,a.