summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorgraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-08-31 01:08:42 +0000
committergraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-08-31 01:08:42 +0000
commit2af5a445f3905c69c42be5c758c52a2f21b17446 (patch)
treeb970b770210046d6a1b41d3385084dd7d4d06961
parent61be4c3048df90d7decdbe4caf91d7ed80433a3f (diff)
l2r bugfixes
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@634 ec762483-ff6d-05da-a07a-a48fb63a330f
-rwxr-xr-xdecoder/apply_fsa_models.cc86
-rwxr-xr-xdecoder/cfg.h10
-rw-r--r--training/online_optimizer.h3
-rw-r--r--utils/d_ary_heap.h4
-rwxr-xr-xutils/hash.h27
-rwxr-xr-xutils/intern_pool.h26
-rwxr-xr-xutils/show.h12
-rw-r--r--utils/stringlib.h4
-rw-r--r--utils/tdict.h3
-rw-r--r--utils/wordid.h6
-rw-r--r--utils/writer.h155
11 files changed, 301 insertions, 35 deletions
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 <queue>
#include "apply_fsa_models.h"
+#include <stdexcept>
+#include <cassert>
+#include <queue>
+#include <stdint.h>
+
+#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 <stdexcept>
-#include <cassert>
#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 <stdint.h>
+#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 <class V>
+ostream& print_by_nt(std::ostream &o,V const& v,CFG const*pcfg=print_cfg,char const* header="\nNT -> X\n") {
+ o<<header;
+ for (int i=0;i<v.size();++i)
+ o << nt_name(i,pcfg) << " -> "<<v[i]<<"\n";
+ return o;
+}
+
+template <class V>
+ostream& print_map_by_nt(std::ostream &o,V const& v,CFG const*pcfg=print_cfg,char const* header="\nNT -> X\n") {
+ o<<header;
+ for (typename V::const_iterator i=v.begin(),e=v.end();i!=e;++i) {
+ print_cfg_rhs(o,i->first,pcfg) << " -> "<<i->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 <class PV>
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<PrefixTrieEdge&>(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<<'['<<n<<']';
+ }
+ static std::string static_nt_name(NTHandle w) {
+ std::ostringstream o;
+ static_print_nt_name(o,w);
+ return o.str();
+ }
static void static_print_rhs_name(std::ostream &o,WordID w) {
- if (w<=0) o<<'['<<-w<<']';
+ if (w<=0) static_print_nt_name(o,-w);
else o<<TD::Convert(w);
}
static std::string static_rhs_name(WordID w) {
diff --git a/training/online_optimizer.h b/training/online_optimizer.h
index 0cd748c4..d2718f93 100644
--- a/training/online_optimizer.h
+++ b/training/online_optimizer.h
@@ -50,7 +50,8 @@ class OnlineOptimizer {
public:
virtual ~OnlineOptimizer();
OnlineOptimizer(const std::tr1::shared_ptr<LearningRateSchedule>& 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<double>& approx_g, SparseVector<double>* 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 <class H,class K>
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 <class H,class K>
+bool put(H &ht,K const& k,typename H::mapped_type const& v) {
+ std::pair<typename H::iterator,bool> 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 <class H,class K>
+bool maybe_add(H &ht,K const& k,typename H::mapped_type const& v) {
+ std::pair<typename H::iterator,bool> inew=ht.insert(typename H::value_type(k,v));
+ return inew.second;
+}
+
+// ht[k] must not exist (yet)
+template <class H,class K>
+void add(H &ht,K const& k,typename H::mapped_type const& v) {
+ bool fresh=maybe_add(ht,k,v);
+ assert(fresh);
+}
+
+
template <class H,class K>
bool improve_mapped_min(H &ht,K const& k,typename H::mapped_type const& v) {
std::pair<typename H::iterator,bool> 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
@@ -59,6 +59,30 @@ struct compose_indirect {
};
+template <class KeyF,class F,class Arg=typename KeyF::argument_type>
+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 <class V,class W>
+ result_type operator()(V const& v,W const&w) const {
+ return v==w||(v&&w&&f(kf(*v),kf(*w)));
+ }
+
+
+};
+
/*
template <class F>
@@ -79,7 +103,7 @@ struct intern_pool : Pool {
typedef typename KeyF::result_type Key;
typedef Item *Handle;
typedef compose_indirect<KeyF,HashKey,Item> HashDeep;
- typedef compose_indirect<KeyF,EqKey,Item> EqDeep;
+ typedef equal_indirect<KeyF,EqKey,Item> EqDeep;
typedef HASH_SET<Handle,HashDeep,EqDeep> Canonical;
typedef typename Canonical::iterator CFind;
typedef std::pair<CFind,bool> 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<<" "<<c);
+#define OSTR(expr) ((dynamic_cast<ostringstream &>(ostringstream()<<std::dec<<expr)).str())
+#define OSTRF(f) ((dynamic_cast<ostringstream &>(f(ostringstream()<<std::dec))).str())
+#define OSTRF1(f,x) ((dynamic_cast<ostringstream &>(f(ostringstream()<<std::dec,x))).str())
+#define OSTRF2(f,x1,x2) ((dynamic_cast<ostringstream &>(f(ostringstream()<<std::dec,x1,x2))).str())
+// std::dec (or seekp, or another manip) is needed to convert to std::ostream reference.
+
#ifndef SHOWS
#include <iostream>
#define SHOWS std::cerr
#endif
-
#define SELF_TYPE_PRINT \
template <class Char,class Traits> \
inline friend std::basic_ostream<Char,Traits> & operator <<(std::basic_ostream<Char,Traits> &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<<" "<<c);
-#define MAKESTR(expr) ((dynamic_cast<ostringstream &>(ostringstream()<<std::dec<<expr)).str())
-// std::dec (or seekp, or another manip) is needed to convert to std::ostream reference.
-
#ifdef STRINGLIB_DEBUG
#include <iostream>
#define SLIBDBG(x) do { std::cerr<<"DBG(stringlib): "<<x<<std::endl; } while(0)
diff --git a/utils/tdict.h b/utils/tdict.h
index a7b3ee1c..dd7f0237 100644
--- a/utils/tdict.h
+++ b/utils/tdict.h
@@ -21,7 +21,8 @@ struct TD {
}
*/
static const WordID max_wordid=0x7fffffff;
- static const WordID none=(WordID)-1; // Vocab_None
+ static const WordID null=max_wordid-1;
+ static const WordID none=(WordID)-1; // Vocab_None - this will collide with mixed node/variable id / word space, though. max_wordid will be distinct (still positive)
static char const* const ss_str; //="<s>";
static char const* const se_str; //="</s>";
static char const* const unk_str; //="<unk>";
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 <limits>
+
typedef int WordID;
+//namespace {
+static const WordID null_wordid=std::numeric_limits<WordID>::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 <iostream>
+
+struct Writer
+{
+ template <class Ch, class Tr,class value_type>
+ std::basic_ostream<Ch,Tr>&
+ operator()(std::basic_ostream<Ch,Tr>& o,const value_type &l) const {
+ return o << l;
+ }
+};
+
+struct LineWriter
+{
+ template <class Ch, class Tr,class Label>
+ std::basic_ostream<Ch,Tr>&
+ operator()(std::basic_ostream<Ch,Tr>& o,const Label &l) const {
+ return o << l << std::endl;
+ }
+};
+
+template <class O, class T,class W> 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<<space;
+ writer(o,*i);
+ }
+ }
+ if (parens) {
+ o << close_paren;
+ if (multiline)
+ o << MULTILINE_SEP;
+ }
+ return std::ios_base::goodbit;
+}
+
+
+template <class Ib,class Ie,class W=Writer>
+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 <class Ch, class Tr>
+ std::basic_ostream<Ch,Tr> &
+ operator()(std::basic_ostream<Ch,Tr> &o) const {
+ write_range_iostate(o,i,e,w,multiline,parens);
+ return o;
+ }
+
+ template <class Ch, class Tr>
+ friend inline
+ std::basic_ostream<Ch,Tr> &
+ operator<<(std::basic_ostream<Ch,Tr> &o,range_formatter<Ib,Ie,W> const& w) {
+ return w(o);
+ }
+};
+
+template <class Ib,class Ie,class W>
+range_formatter<Ib,Ie,W>
+wrange(Ib i,Ie e,W const& w,bool multiline=false,bool parens=true)
+{
+ return range_formatter<Ib,Ie,W>(i,e,w,multiline,parens);
+}
+
+template <class Ib,class Ie>
+range_formatter<Ib,Ie>
+prange(Ib i,Ie e,bool multiline=false,bool parens=true)
+{
+ return range_formatter<Ib,Ie,Writer>(i,e,Writer(),multiline,parens);
+}
+
+
+template <class Ch, class Tr, class T,class W> inline
+std::basic_ostream<Ch,Tr> & write_range(std::basic_ostream<Ch,Tr>& 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 <class O, class T>
+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 <class O, class C>
+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 <class O>
+struct bound_printer
+{
+ O *po;
+ template <class T>
+ void operator()(T const& t) const
+ {
+ *po << t;
+ }
+};
+
+template <class O>
+bound_printer<O>
+make_bound_printer(O &o)
+{
+ bound_printer<O> ret;
+ ret.po=&o;
+ return ret;
+}
+
+template <class W>
+struct bound_writer
+{
+ W const& w;
+ bound_writer(W const& w) : w(w) {}
+ bound_writer(bound_writer const& o) :w(o.w) {}
+ template <class O,class V>
+ void operator()(O &o,V const& v) const
+ {
+ v.print(o,w);
+ }
+};
+
+
+template <class W>
+bound_writer<W>
+make_bound_writer(W const& w)
+{
+ return bound_writer<W>(w);
+}
+
+
+
+#endif