fsa notes

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@638 ec762483-ff6d-05da-a07a-a48fb63a330f

1 files changed, 21 insertions, 0 deletions

diff --git a/decoder/apply_fsa_models.README b/decoder/apply_fsa_models.README
new file mode 100755
index 00000000..d487c96d
--- /dev/null
+++ b/decoder/apply_fsa_models.README
@@ -0,0 +1,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.