From c57dda7e1e8bcc13dff508752f778c1c95c9f895 Mon Sep 17 00:00:00 2001 From: graehl Date: Wed, 1 Sep 2010 00:05:14 +0000 Subject: fsa notes git-svn-id: https://ws10smt.googlecode.com/svn/trunk@638 ec762483-ff6d-05da-a07a-a48fb63a330f --- decoder/apply_fsa_models.README | 21 +++++++++++++++++++++ decoder/apply_fsa_models.cc | 21 +++++++-------------- utils/d_ary_heap.h | 2 +- 3 files changed, 29 insertions(+), 15 deletions(-) create mode 100755 decoder/apply_fsa_models.README 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. diff --git a/decoder/apply_fsa_models.cc b/decoder/apply_fsa_models.cc index 4431643f..bffd7033 100755 --- a/decoder/apply_fsa_models.cc +++ b/decoder/apply_fsa_models.cc @@ -1,3 +1,7 @@ +//see apply_fsa_models.README for notes on the l2r earley fsa+cfg intersection +//implementation in this file (also some comments in this file) +#define SAFE_VALGRIND 1 + #include "apply_fsa_models.h" #include #include @@ -21,7 +25,6 @@ #include "show.h" #include "string_to.h" -#define SAFE_VALGRIND 1 #define DFSA(x) x //fsa earley chart @@ -78,20 +81,13 @@ I'm using option 1. */ // if we don't greedy-binarize, we want to encode recognized prefixes p (X -> p . rest) efficiently. if we're doing this, we may as well also push costs so we can best-first select rules in a lazy fashion. this is effectively left-branching binarization, of course. + template struct fsa_map_type { - typedef std::map type; + typedef std::map type; // change to HASH_MAP ? }; -//template typedef +//template typedef - and macro to make it less painful #define FSA_MAP(k,v) fsa_map_type >::type -typedef WordID LHS; // so this will be -NTHandle. - -struct get_second { - template - typename P::second_type const& operator()(P const& p) const { - return p.second; - } -}; struct PrefixTrieNode; typedef PrefixTrieNode *NodeP; @@ -136,7 +132,6 @@ ostream& print_map_by_nt(std::ostream &o,V const& v,CFG const*pcfg=print_cfg,cha return o; } - struct PrefixTrieEdge { PrefixTrieEdge() // : dest(0),w(TD::max_wordid) @@ -164,10 +159,8 @@ struct PrefixTrieEdge { print_cfg_rhs(o,w); o<<"{"<"<