summaryrefslogtreecommitdiff
path: root/decoder
diff options
context:
space:
mode:
authorgraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-09-01 00:05:14 +0000
committergraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-09-01 00:05:14 +0000
commitc57dda7e1e8bcc13dff508752f778c1c95c9f895 (patch)
tree3775eed1c9510541268ff4a4e25f7a9adebf7a39 /decoder
parent89a162041f1b335d0dbb286013ccca5716e0a595 (diff)
fsa notes
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@638 ec762483-ff6d-05da-a07a-a48fb63a330f
Diffstat (limited to 'decoder')
-rwxr-xr-xdecoder/apply_fsa_models.README21
-rwxr-xr-xdecoder/apply_fsa_models.cc21
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.