fsa notes

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

2 files changed, 28 insertions, 14 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.
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 <stdexcept>
 #include <cassert>
@@ -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 <class K,class V,class Hash>
 struct fsa_map_type {
-  typedef std::map<K,V> type;
+  typedef std::map<K,V> type; // change to HASH_MAP ?
 };
-//template typedef
+//template typedef - and macro to make it less painful
 #define FSA_MAP(k,v) fsa_map_type<k,v,boost::hash<k> >::type
-typedef WordID LHS; // so this will be -NTHandle.
-
-struct get_second {
-  template <class P>
-  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<<"{"<<p<<"}->"<<dest;
   }
-
 };
 
-
 //note: ending a rule is handled with a special final edge, so that possibility can be explored in best-first order along with the rest (alternative: always finish a final rule by putting it on queue).  this edge has no symbol on it.
 struct PrefixTrieNode {
   best_t p; // viterbi (max prob) of rule this node leads to - when building.  telescope later onto edges for best-first.