From 2af5a445f3905c69c42be5c758c52a2f21b17446 Mon Sep 17 00:00:00 2001 From: graehl Date: Tue, 31 Aug 2010 01:08:42 +0000 Subject: l2r bugfixes git-svn-id: https://ws10smt.googlecode.com/svn/trunk@634 ec762483-ff6d-05da-a07a-a48fb63a330f --- decoder/apply_fsa_models.cc | 86 +++++++++++++++++------- decoder/cfg.h | 10 ++- training/online_optimizer.h | 3 +- utils/d_ary_heap.h | 4 +- utils/hash.h | 27 +++++++- utils/intern_pool.h | 26 +++++++- utils/show.h | 12 +++- utils/stringlib.h | 4 -- utils/tdict.h | 3 +- utils/wordid.h | 6 ++ utils/writer.h | 155 ++++++++++++++++++++++++++++++++++++++++++++ 11 files changed, 301 insertions(+), 35 deletions(-) create mode 100644 utils/writer.h diff --git a/decoder/apply_fsa_models.cc b/decoder/apply_fsa_models.cc index dddbddd9..4a928206 100755 --- a/decoder/apply_fsa_models.cc +++ b/decoder/apply_fsa_models.cc @@ -1,13 +1,16 @@ -#include #include "apply_fsa_models.h" +#include +#include +#include +#include + +#include "writer.h" #include "hg.h" #include "ff_fsa_dynamic.h" #include "ff_from_fsa.h" #include "feature_vector.h" #include "stringlib.h" #include "apply_models.h" -#include -#include #include "cfg.h" #include "hg_cfg.h" #include "utoa.h" @@ -16,7 +19,7 @@ #include "d_ary_heap.h" #include "agenda.h" #include "show.h" -#include +#include "string_to.h" #define DFSA(x) x //fsa earley chart @@ -24,7 +27,7 @@ #define DPFSA(x) x //prefix trie -#define DBUILDTRIE(x) x +#define DBUILDTRIE(x) #define PRINT_PREFIX 1 #if PRINT_PREFIX @@ -101,23 +104,54 @@ struct TrieBackP { FsaFeatureFunction const* print_fsa=0; CFG const* print_cfg=0; -inline void print_cfg_rhs(std::ostream &o,WordID w) { - if (print_cfg) - print_cfg->print_rhs_name(o,w); +inline ostream& print_cfg_rhs(std::ostream &o,WordID w,CFG const*pcfg=print_cfg) { + if (pcfg) + pcfg->print_rhs_name(o,w); else CFG::static_print_rhs_name(o,w); + return o; +} + +inline std::string nt_name(WordID n,CFG const*pcfg=print_cfg) { + if (pcfg) return pcfg->nt_name(n); + return CFG::static_nt_name(n); +} + +template +ostream& print_by_nt(std::ostream &o,V const& v,CFG const*pcfg=print_cfg,char const* header="\nNT -> X\n") { + o< "< +ostream& print_map_by_nt(std::ostream &o,V const& v,CFG const*pcfg=print_cfg,char const* header="\nNT -> X\n") { + o<first,pcfg) << " -> "<second<<"\n"; + } + return o; } + struct PrefixTrieEdge { -// PrefixTrieEdge() { } + PrefixTrieEdge() + // : dest(0),w(TD::max_wordid) + {} + PrefixTrieEdge(WordID w,NodeP dest) + : dest(dest),w(w) + {} // explicit PrefixTrieEdge(best_t p) : p(p),dest(0) { } - best_t p;// viterbi additional prob, i.e. product over path incl. p_final = total rule prob + + best_t p;// viterbi additional prob, i.e. product over path incl. p_final = total rule prob. note: for final edge, set this. //DPFSA() // we can probably just store deltas, but for debugging remember the full p // best_t delta; // NodeP dest; bool is_final() const { return dest==0; } - WordID w; // for lhs, this will be nonneg NTHandle instead. // not set if is_final() // actually, set to lhs nt index + best_t p_dest() const; + WordID w; // for root and and is_final(), this will be (negated) NTHandle. // for sorting most probable first in adj; actually >(p) inline bool operator <(PrefixTrieEdge const& o) const { @@ -218,7 +252,7 @@ public: for (int i=0,e=adj.size();i!=e;++i) { PrefixTrieEdge const& edge=adj[i]; // assert(edge.p.is_1()); // actually, after done_building, e will have telescoped dest->p/p. - NTHandle n=edge.w; + NTHandle n=-edge.w; assert(n>=0); SHOWM3(DPFSA,"index_lhs",i,edge,n); v[n]=edge.dest; @@ -228,7 +262,10 @@ public: template void done_root(PV &v) { assert(is_root()); + SHOWM1(DBUILDTRIE,"done_root",OSTRF1(print_map_by_nt,edge_for)); done_building_r(); //sets adj + SHOWM1(DBUILDTRIE,"done_root",OSTRF1(print_by_nt,adj)); +// SHOWM1(DBUILDTRIE,done_root,adj); // index_adj(); // we want an index for the root node?. don't think so - index_lhs handles it. also we stopped clearing edge_for. index_lhs(v); // uses adj } @@ -244,7 +281,7 @@ public: // for done_building; compute incremental (telescoped) edge p PrefixTrieEdge /*const&*/ operator()(PrefixTrieEdgeFor::value_type & pair) const { PrefixTrieEdge &e=pair.second;//const_cast(pair.second); - e.p=(e.dest->p)/p; + e.p=e.p_dest()/p; return e; } @@ -265,6 +302,7 @@ public: // (*this)(*i); } #endif + SHOWM1(DBUILDTRIE,"done building adj",prange(adj.begin(),adj.end(),true)); assert(adj.size()==edge_for.size()); // if (final) p_final/=p; std::sort(adj.begin(),adj.end()); @@ -287,18 +325,18 @@ public: inline NodeP build(W w,best_t rulep) { return build(lhs,w,rulep); } - inline NodeP build_lhs(NTHandle w,best_t rulep) { - return build(w,w,rulep); + inline NodeP build_lhs(NTHandle n,best_t rulep) { + return build(n,-n,rulep); } NodeP build(NTHandle lhs_,W w,best_t rulep) { PrefixTrieEdgeFor::iterator i=edge_for.find(w); if (i!=edge_for.end()) return improve_edge(i->second,rulep); - PrefixTrieEdge &e=i->second; NodeP r=new PrefixTrieNode(lhs_,rulep); IF_PRINT_PREFIX(r->backp=BP(w,this)); - e.dest=r; +// edge_for.insert(i,PrefixTrieEdgeFor::value_type(w,PrefixTrieEdge(w,r))); + add(edge_for,w,PrefixTrieEdge(w,r)); SHOWM4(DBUILDTRIE,"built node",this,w,*r,r); return r; } @@ -306,7 +344,7 @@ public: void set_final(NTHandle lhs_,best_t pf) { assert(no_adj()); final=true; - PrefixTrieEdge &e=edge_for[-1]; + PrefixTrieEdge &e=edge_for[null_wordid]; e.p=pf; e.dest=0; e.w=lhs_; @@ -335,6 +373,10 @@ public: PRINT_SELF(PrefixTrieNode) }; +inline best_t PrefixTrieEdge::p_dest() const { + return dest ? dest->p : p; // for final edge, p was set (no sentinel node) +} + //Trie starts with lhs (nonneg index), then continues w/ rhs (mixed >0 word, else NT) // trie ends with final edge, which points to a per-lhs prefix node @@ -358,7 +400,9 @@ struct PrefixTrie { SHOWM2(DBUILDTRIE,"PrefixTrie()",rulesp->size(),lhs2.size()); cfg.VisitRuleIds(*this); root.done_root(lhs2); - SHOWM4(DBUILDTRIE,"done w/ PrefixTrie: ",root,root.adj.size(),lhs2.size(),lhs2[0]); + SHOWM3(DBUILDTRIE,"done w/ PrefixTrie: ",root,root.adj.size(),lhs2.size()); + DBUILDTRIE(print_by_nt(cerr,lhs2,cfgp)); + SHOWM1(DBUILDTRIE,"lhs2",OSTRF2(print_by_nt,lhs2,cfgp)); } void operator()(int ri) { @@ -526,12 +570,8 @@ struct Chart { } else { break; } - } - - } - } Chart(CFG &cfg,SentenceMetadata const& smeta,FsaFF const& fsa,unsigned reserve=FSA_AGENDA_RESERVE) diff --git a/decoder/cfg.h b/decoder/cfg.h index 95cb5fd7..8cb29bb9 100755 --- a/decoder/cfg.h +++ b/decoder/cfg.h @@ -77,8 +77,16 @@ struct CFG { if (w<=0) return nt_name(-w); else return TD::Convert(w); } + static void static_print_nt_name(std::ostream &o,NTHandle n) { + o<<'['<& s, - size_t training_instances) : schedule_(s), k_(), N_(training_instances) {} + size_t training_instances) + : N_(training_instances),schedule_(s),k_() {} void UpdateWeights(const SparseVector& approx_g, SparseVector* weights) { ++k_; const double eta = schedule_->eta(k_); diff --git a/utils/d_ary_heap.h b/utils/d_ary_heap.h index 10d04782..eee8efe0 100644 --- a/utils/d_ary_heap.h +++ b/utils/d_ary_heap.h @@ -8,8 +8,8 @@ #define D_ARY_UP_GRAEHL 0 // untested #define D_ARY_APPEND_ALWAYS_PUSH 1 // heapify (0) is untested. otherwise switch between push and heapify depending on size (cache effects, existing items vs. # appended ones) -#define D_ARY_TRACK_OUT_OF_HEAP 0 // shouldn't need to track, because in contains() false positives looking up stale or random loc map values are impossible - we just check key -#define D_ARY_VERIFY_HEAP 0 +#define D_ARY_TRACK_OUT_OF_HEAP 1 // shouldn't need to track, because in contains() false positives looking up stale or random loc map values are impossible - we just check key +#define D_ARY_VERIFY_HEAP 1 // This is a very expensive test so it should be disabled even when NDEBUG is not defined /* adapted from boost/graph/detail/d_ary_heap.hpp diff --git a/utils/hash.h b/utils/hash.h index 2062578f..2290bc34 100755 --- a/utils/hash.h +++ b/utils/hash.h @@ -95,7 +95,6 @@ typename H::mapped_type & get_or_call(H &ht,K const& k,F const& f) { } } - // the below could also return a ref to the mapped max/min. they have the advantage of not falsely claiming an improvement when an equal value already existed. otherwise you could just modify the get_default and if equal assume new. template bool improve_mapped_max(H &ht,K const& k,typename H::mapped_type const& v) { @@ -110,6 +109,32 @@ bool improve_mapped_max(H &ht,K const& k,typename H::mapped_type const& v) { return false; } + +// return true if there was no old value. like ht[k]=v but lets you know whether it was a new addition +template +bool put(H &ht,K const& k,typename H::mapped_type const& v) { + std::pair inew=ht.insert(typename H::value_type(k,v)); + if (inew.second) + return true; + inew.first->second=v; + return false; +} + +// does not update old value (returns false) if one exists, otherwise add +template +bool maybe_add(H &ht,K const& k,typename H::mapped_type const& v) { + std::pair inew=ht.insert(typename H::value_type(k,v)); + return inew.second; +} + +// ht[k] must not exist (yet) +template +void add(H &ht,K const& k,typename H::mapped_type const& v) { + bool fresh=maybe_add(ht,k,v); + assert(fresh); +} + + template bool improve_mapped_min(H &ht,K const& k,typename H::mapped_type const& v) { std::pair inew=ht.insert(typename H::value_type(k,v)); diff --git a/utils/intern_pool.h b/utils/intern_pool.h index d9890ae6..7c739add 100755 --- a/utils/intern_pool.h +++ b/utils/intern_pool.h @@ -57,6 +57,30 @@ struct compose_indirect { } +}; + +template +struct equal_indirect { + typedef Arg *argument_type; // we also accept Arg & + KeyF kf; + F f; + typedef bool result_type; + + result_type operator()(Arg const& a1,Arg const& a2) const { + return f(kf(a1),kf(a2)); + } + result_type operator()(Arg & a1,Arg & a2) const { + return f(kf(a1),kf(a2)); + } + result_type operator()(Arg * a1,Arg * a2) const { + return a1==a2||(a1&&a2&&f(kf(*a1),kf(*a2))); + } + template + result_type operator()(V const& v,W const&w) const { + return v==w||(v&&w&&f(kf(*v),kf(*w))); + } + + }; /* @@ -79,7 +103,7 @@ struct intern_pool : Pool { typedef typename KeyF::result_type Key; typedef Item *Handle; typedef compose_indirect HashDeep; - typedef compose_indirect EqDeep; + typedef equal_indirect EqDeep; typedef HASH_SET Canonical; typedef typename Canonical::iterator CFind; typedef std::pair CInsert; diff --git a/utils/show.h b/utils/show.h index 1b645c83..95cad253 100755 --- a/utils/show.h +++ b/utils/show.h @@ -1,12 +1,19 @@ #ifndef UTILS__SHOW_H #define UTILS__SHOW_H + +//usage: string s=OSTR(1<<" "<(ostringstream()<(f(ostringstream()<(f(ostringstream()<(f(ostringstream()< #define SHOWS std::cerr #endif - #define SELF_TYPE_PRINT \ template \ inline friend std::basic_ostream & operator <<(std::basic_ostream &o, self_type const& me) \ @@ -26,6 +33,8 @@ #define PRINT_SELF(self) typedef self self_type; SELF_TYPE_PRINT_OSTREAM + + #undef SHOWALWAYS #define SHOWALWAYS(x) x @@ -62,6 +71,7 @@ careful: none of this is wrapped in a block. so you can't use one of these macr #define SHOW7(IF,x,y0,y1,y2,y3,y4,y5) SHOW1(IF,x) SHOW6(IF,y0,y1,y2,y3,y4,y5) #define SHOWM(IF,m,x) SHOWP(IF,m<<": ") SHOW(IF,x) +#define SHOWM1(IF,m,x) SHOWM(IF,m,x) #define SHOWM2(IF,m,x0,x1) SHOWP(IF,m<<": ") SHOW2(IF,x0,x1) #define SHOWM3(IF,m,x0,x1,x2) SHOWP(IF,m<<": ") SHOW3(IF,x0,x1,x2) #define SHOWM4(IF,m,x0,x1,x2,x3) SHOWP(IF,m<<": ") SHOW4(IF,x0,x1,x2,x3) diff --git a/utils/stringlib.h b/utils/stringlib.h index 4f79eb31..8022bb88 100644 --- a/utils/stringlib.h +++ b/utils/stringlib.h @@ -1,10 +1,6 @@ #ifndef CDEC_STRINGLIB_H_ #define CDEC_STRINGLIB_H_ -//usage: string s=MAKESTRE(1<<" "<(ostringstream()< #define SLIBDBG(x) do { std::cerr<<"DBG(stringlib): "<"; static char const* const se_str; //=""; static char const* const unk_str; //=""; diff --git a/utils/wordid.h b/utils/wordid.h index fb50bcc1..714dcd0b 100644 --- a/utils/wordid.h +++ b/utils/wordid.h @@ -1,6 +1,12 @@ #ifndef _WORD_ID_H_ #define _WORD_ID_H_ +#include + typedef int WordID; +//namespace { +static const WordID null_wordid=std::numeric_limits::max(); +//} + #endif diff --git a/utils/writer.h b/utils/writer.h new file mode 100644 index 00000000..d21b74d6 --- /dev/null +++ b/utils/writer.h @@ -0,0 +1,155 @@ +#ifndef WRITER_H +#define WRITER_H + +#include + +struct Writer +{ + template + std::basic_ostream& + operator()(std::basic_ostream& o,const value_type &l) const { + return o << l; + } +}; + +struct LineWriter +{ + template + std::basic_ostream& + operator()(std::basic_ostream& o,const Label &l) const { + return o << l << std::endl; + } +}; + +template inline +std::ios_base::iostate write_range_iostate(O& o,T begin, T end,W writer,bool multiline=false,bool parens=true,char open_paren='(',char close_paren=')',char space=' ') +{ + static const char *const MULTILINE_SEP="\n"; + if (parens) { + o << open_paren; + if (multiline) + o << MULTILINE_SEP; + } + if (multiline) { + for (;begin!=end;++begin) { + o << space; + writer(o,*begin); + o << MULTILINE_SEP; + } + } else { + for (T i=begin;i!=end;++i) { + if (i!=begin) o< +struct range_formatter { + Ib i; + Ie e; + W w; + bool multiline; + bool parens; + range_formatter(Ib i,Ie e,W w=W(),bool multiline=false,bool parens=true) : + i(i),e(e),w(w),multiline(multiline),parens(parens) {} + + template + std::basic_ostream & + operator()(std::basic_ostream &o) const { + write_range_iostate(o,i,e,w,multiline,parens); + return o; + } + + template + friend inline + std::basic_ostream & + operator<<(std::basic_ostream &o,range_formatter const& w) { + return w(o); + } +}; + +template +range_formatter +wrange(Ib i,Ie e,W const& w,bool multiline=false,bool parens=true) +{ + return range_formatter(i,e,w,multiline,parens); +} + +template +range_formatter +prange(Ib i,Ie e,bool multiline=false,bool parens=true) +{ + return range_formatter(i,e,Writer(),multiline,parens); +} + + +template inline +std::basic_ostream & write_range(std::basic_ostream& o,T begin, T end,W writer,bool multiline=false,bool parens=true,char open_paren='(',char close_paren=')') +{ + write_range_iostate(o,begin,end,writer,multiline,parens,open_paren,close_paren); + return o; +} + +template +inline std::ios_base::iostate print_range(O& o,T begin,T end,bool multiline=false,bool parens=true,char open_paren='(',char close_paren=')') { + return write_range_iostate(o,begin,end,Writer(),multiline,parens,open_paren,close_paren); +} + +template +inline std::ios_base::iostate print_range_i(O& o,C const&c,unsigned from,unsigned to,bool multiline=false,bool parens=true,char open_paren='(',char close_paren=')') { + return write_range_iostate(o,c.begin()+from,c.begin()+to,Writer(),multiline,parens,open_paren,close_paren); +} + + +template +struct bound_printer +{ + O *po; + template + void operator()(T const& t) const + { + *po << t; + } +}; + +template +bound_printer +make_bound_printer(O &o) +{ + bound_printer ret; + ret.po=&o; + return ret; +} + +template +struct bound_writer +{ + W const& w; + bound_writer(W const& w) : w(w) {} + bound_writer(bound_writer const& o) :w(o.w) {} + template + void operator()(O &o,V const& v) const + { + v.print(o,w); + } +}; + + +template +bound_writer +make_bound_writer(W const& w) +{ + return bound_writer(w); +} + + + +#endif -- cgit v1.2.3