From 2cb224de7db49b761ac06b031090fe7f846744fe Mon Sep 17 00:00:00 2001 From: graehl Date: Sat, 24 Jul 2010 21:18:01 +0000 Subject: FSA: simpler Scan1 ScanT1 methods, otherewise also expose edge to full Scan git-svn-id: https://ws10smt.googlecode.com/svn/trunk@399 ec762483-ff6d-05da-a07a-a48fb63a330f --- Makefile.am | 1 + decoder/ff.cc | 8 +- decoder/ff.h | 5 +- decoder/ff_from_fsa.h | 15 +-- decoder/ff_fsa.h | 65 ++++++++----- decoder/ff_sample_fsa.h | 26 +++-- decoder/hash.h | 35 +++++++ decoder/hg.cc | 4 +- decoder/hg.h | 2 +- decoder/hg_io.cc | 3 +- decoder/murmur_hash.h | 237 ++++++++++++++++++++++----------------------- decoder/oracle_bleu.h | 2 +- decoder/scfg_translator.cc | 8 +- decoder/sparse_vector.h | 72 ++++++++------ decoder/trule.h | 6 +- 15 files changed, 277 insertions(+), 212 deletions(-) diff --git a/Makefile.am b/Makefile.am index a8b411b7..e82e2352 100644 --- a/Makefile.am +++ b/Makefile.am @@ -3,3 +3,4 @@ AUTOMAKE_OPTIONS = foreign ACLOCAL_AMFLAGS = -I m4 AM_CPPFLAGS = -D_GLIBCXX_PARALLEL + diff --git a/decoder/ff.cc b/decoder/ff.cc index 4f1a3d32..9fc2dbd8 100644 --- a/decoder/ff.cc +++ b/decoder/ff.cc @@ -13,10 +13,8 @@ using namespace std; FeatureFunction::~FeatureFunction() {} -void FeatureFunction::FinalTraversalFeatures(const void* ant_state, - SparseVector* features) const { - (void) ant_state; - (void) features; +void FeatureFunction::FinalTraversalFeatures(const void* /* ant_state */, + SparseVector* /* features */) const { } string FeatureFunction::usage_helper(std::string const& name,std::string const& params,std::string const& details,bool sp,bool sd) { @@ -225,7 +223,7 @@ void ModelSet::AddFinalFeatures(const std::string& state, Hypergraph::Edge* edge int spos = model_state_pos_[i]; ant_state = &state[spos]; } - ff.FinalTraversalFeatures(smeta, ant_state, &edge->feature_values_); + ff.FinalTraversalFeatures(smeta, *edge, ant_state, &edge->feature_values_); } edge->edge_prob_.logeq(edge->feature_values_.dot(weights_)); } diff --git a/decoder/ff.h b/decoder/ff.h index 9ff67dd8..b8ca71c4 100644 --- a/decoder/ff.h +++ b/decoder/ff.h @@ -64,8 +64,9 @@ protected: virtual void FinalTraversalFeatures(const void* residual_state, FeatureVector* final_features) const; public: - //override either this or above. (no need to do both) - virtual void FinalTraversalFeatures(const SentenceMetadata& smeta, + //override either this or one of above. + virtual void FinalTraversalFeatures(const SentenceMetadata& /* smeta */, + const Hypergraph::Edge& /* edge */, const void* residual_state, FeatureVector* final_features) const { FinalTraversalFeatures(residual_state,final_features); diff --git a/decoder/ff_from_fsa.h b/decoder/ff_from_fsa.h index 75b99f52..20e7c5ca 100755 --- a/decoder/ff_from_fsa.h +++ b/decoder/ff_from_fsa.h @@ -58,7 +58,7 @@ public: } else { WordID ew=e[j]; FSAFFDBG(' '< fsa(ff,smeta); + FsaScanner fsa(ff,smeta,edge); TRule const& rule=*edge.rule_; Sentence const& e = rule.e(); for (int j = 0; j < e.size(); ++j) { // items in target side of rule @@ -141,23 +141,24 @@ public: //FIXME: it's assumed that the final rule is just a unary no-target-terminal rewrite (same as ff_lm) virtual void FinalTraversalFeatures(const SentenceMetadata& smeta, + const Hypergraph::Edge& edge, const void* residual_state, FeatureVector* final_features) const { ff.init_features(final_features); Sentence const& ends=ff.end_phrase(); if (!ssz) { - AccumFeatures(ff,smeta,begin(ends),end(ends),final_features,0); + AccumFeatures(ff,smeta,edge,begin(ends),end(ends),final_features,0); return; } SP ss=ff.start_state(); WP l=(WP)residual_state,lend=left_end(residual_state); SP rst=fsa_state(residual_state); - FSAFFDBG("(FromFsa) Final "< "<") + AccumFeatures(ff,smeta,edge,begin(ends),end(ends),final_features,rst); // e.g. [ctx for last M words] score("") FSAFFDBG(" right: "< "<"< @@ -13,7 +15,40 @@ # define HASH_MAP_RESERVED(h,empty,deleted) # define HASH_MAP_EMPTY(h,empty) #endif + #include +// assumes C is POD +template +struct murmur_hash +{ + typedef MurmurInt return_type; + typedef C /*const&*/ argument_type; + return_type operator()(argument_type const& c) const { + return MurmurHash((void*)&c,sizeof(c)); + } +}; + +// murmur_hash_array isn't std guaranteed safe (you need to use string::data()) +template <> +struct murmur_hash +{ + typedef MurmurInt return_type; + typedef std::string /*const&*/ argument_type; + return_type operator()(argument_type const& c) const { + return MurmurHash(c.data(),c.size()); + } +}; + +// uses begin(),size() assuming contiguous layout and POD +template +struct murmur_hash_array +{ + typedef MurmurInt return_type; + typedef C /*const&*/ argument_type; + return_type operator()(argument_type const& c) const { + return MurmurHash(&*c.begin(),c.size()*sizeof(*c.begin())); + } +}; #endif diff --git a/decoder/hg.cc b/decoder/hg.cc index 5a33fc97..e7a86c5b 100644 --- a/decoder/hg.cc +++ b/decoder/hg.cc @@ -100,7 +100,7 @@ prob_t Hypergraph::ComputeEdgePosteriors(double scale, vector* posts) co ScaledTransitionEventWeightFunction>(*this, &pv, weight, w2); posts->resize(edges_.size()); for (int i = 0; i < edges_.size(); ++i) - (*posts)[i] = prob_t(pv.value(i)); + (*posts)[i] = prob_t(pv.get(i)); return prob_t(inside); } @@ -113,7 +113,7 @@ prob_t Hypergraph::ComputeBestPathThroughEdges(vector* post) const { ViterbiTransitionEventWeightFunction>(*this, &pv); post->resize(edges_.size()); for (int i = 0; i < edges_.size(); ++i) - (*post)[i] = pv.value(i).v_; + (*post)[i] = pv.get(i).v_; return viterbi_weight.v_; } diff --git a/decoder/hg.h b/decoder/hg.h index 53b5a53d..b3bfd19c 100644 --- a/decoder/hg.h +++ b/decoder/hg.h @@ -4,8 +4,8 @@ #include #include +#include "feature_vector.h" #include "small_vector.h" -#include "sparse_vector.h" #include "wordid.h" #include "trule.h" #include "prob.h" diff --git a/decoder/hg_io.cc b/decoder/hg_io.cc index d6e73b8a..65c2c382 100644 --- a/decoder/hg_io.cc +++ b/decoder/hg_io.cc @@ -556,6 +556,7 @@ void HypergraphIO::PLFtoLattice(const string& plf, Lattice* pl) { ReadFromPLF(plf, &g, 0); const int num_nodes = g.nodes_.size() - 1; l.resize(num_nodes); + int fid0=FD::Convert("Feature_0"); for (int i = 0; i < num_nodes; ++i) { vector& alts = l[i]; const Hypergraph::Node& node = g.nodes_[i]; @@ -564,7 +565,7 @@ void HypergraphIO::PLFtoLattice(const string& plf, Lattice* pl) { for (int j = 0; j < num_alts; ++j) { const Hypergraph::Edge& edge = g.edges_[node.out_edges_[j]]; alts[j].label = edge.rule_->e_[1]; - alts[j].cost = edge.feature_values_.value(FD::Convert("Feature_0")); + alts[j].cost = edge.feature_values_.get(fid0); alts[j].dist2next = edge.head_node_ - node.id_; } } diff --git a/decoder/murmur_hash.h b/decoder/murmur_hash.h index 8ddad339..8dbd7807 100755 --- a/decoder/murmur_hash.h +++ b/decoder/murmur_hash.h @@ -3,126 +3,124 @@ //NOTE: quite fast, nice collision properties, but endian dependent hash values -#include +#include "have_64_bits.h" +typedef uintptr_t MurmurInt; // MurmurHash2, by Austin Appleby static const uint32_t DEFAULT_SEED=2654435769U; -#if sizeof(void *)==8 -typedef uint64_t MurmurInt; +#if HAVE_64_BITS //MurmurInt MurmurHash(void const *key, int len, uint32_t seed=DEFAULT_SEED); inline uint64_t MurmurHash64( const void * key, int len, unsigned int seed=DEFAULT_SEED ) { - const uint64_t m = 0xc6a4a7935bd1e995; - const int r = 47; + const uint64_t m = 0xc6a4a7935bd1e995; + const int r = 47; - uint64_t h = seed ^ (len * m); + uint64_t h = seed ^ (len * m); - const uint64_t * data = (const uint64_t *)key; - const uint64_t * end = data + (len/8); + const uint64_t * data = (const uint64_t *)key; + const uint64_t * end = data + (len/8); - while(data != end) - { - uint64_t k = *data++; + while(data != end) + { + uint64_t k = *data++; - k *= m; - k ^= k >> r; - k *= m; + k *= m; + k ^= k >> r; + k *= m; - h ^= k; - h *= m; - } + h ^= k; + h *= m; + } - const unsigned char * data2 = (const unsigned char*)data; + const unsigned char * data2 = (const unsigned char*)data; - switch(len & 7) - { - case 7: h ^= uint64_t(data2[6]) << 48; - case 6: h ^= uint64_t(data2[5]) << 40; - case 5: h ^= uint64_t(data2[4]) << 32; - case 4: h ^= uint64_t(data2[3]) << 24; - case 3: h ^= uint64_t(data2[2]) << 16; - case 2: h ^= uint64_t(data2[1]) << 8; - case 1: h ^= uint64_t(data2[0]); - h *= m; - }; + switch(len & 7) + { + case 7: h ^= uint64_t(data2[6]) << 48; + case 6: h ^= uint64_t(data2[5]) << 40; + case 5: h ^= uint64_t(data2[4]) << 32; + case 4: h ^= uint64_t(data2[3]) << 24; + case 3: h ^= uint64_t(data2[2]) << 16; + case 2: h ^= uint64_t(data2[1]) << 8; + case 1: h ^= uint64_t(data2[0]); + h *= m; + }; - h ^= h >> r; - h *= m; - h ^= h >> r; + h ^= h >> r; + h *= m; + h ^= h >> r; - return h; + return h; } -inline uint32_t MurmurHash2(void const *key, int len, uint32_t seed=DEFAULT_SEED) +inline uint32_t MurmurHash32(void const *key, int len, uint32_t seed=DEFAULT_SEED) { return (uint32_t) MurmurHash64(key,len,seed); } -typedef uint64_t MurmurInt; inline MurmurInt MurmurHash(void const *key, int len, uint32_t seed=DEFAULT_SEED) { return MurmurHash64(key,len,seed); } -#else // 32-bit -typedef uint32_t MurmurInt; - +#else +// 32-bit // Note - This code makes a few assumptions about how your machine behaves - // 1. We can read a 4-byte value from any address without crashing // 2. sizeof(int) == 4 -inline uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed=DEFAULT_SEED) +inline uint32_t MurmurHash32 ( const void * key, int len, uint32_t seed=DEFAULT_SEED) { - // 'm' and 'r' are mixing constants generated offline. - // They're not really 'magic', they just happen to work well. + // 'm' and 'r' are mixing constants generated offline. + // They're not really 'magic', they just happen to work well. - const uint32_t m = 0x5bd1e995; - const int r = 24; + const uint32_t m = 0x5bd1e995; + const int r = 24; - // Initialize the hash to a 'random' value + // Initialize the hash to a 'random' value - uint32_t h = seed ^ len; + uint32_t h = seed ^ len; - // Mix 4 bytes at a time into the hash + // Mix 4 bytes at a time into the hash - const unsigned char * data = (const unsigned char *)key; + const unsigned char * data = (const unsigned char *)key; - while(len >= 4) - { - uint32_t k = *(uint32_t *)data; + while(len >= 4) + { + uint32_t k = *(uint32_t *)data; - k *= m; - k ^= k >> r; - k *= m; + k *= m; + k ^= k >> r; + k *= m; - h *= m; - h ^= k; + h *= m; + h ^= k; - data += 4; - len -= 4; - } + data += 4; + len -= 4; + } - // Handle the last few bytes of the input array + // Handle the last few bytes of the input array - switch(len) - { - case 3: h ^= data[2] << 16; - case 2: h ^= data[1] << 8; - case 1: h ^= data[0]; - h *= m; - }; + switch(len) + { + case 3: h ^= data[2] << 16; + case 2: h ^= data[1] << 8; + case 1: h ^= data[0]; + h *= m; + }; - // Do a few final mixes of the hash to ensure the last few - // bytes are well-incorporated. + // Do a few final mixes of the hash to ensure the last few + // bytes are well-incorporated. - h ^= h >> 13; - h *= m; - h ^= h >> 15; + h ^= h >> 13; + h *= m; + h ^= h >> 15; - return h; + return h; } inline MurmurInt MurmurHash ( const void * key, int len, uint32_t seed=DEFAULT_SEED) { @@ -133,55 +131,56 @@ inline MurmurInt MurmurHash ( const void * key, int len, uint32_t seed=DEFAULT_S inline uint64_t MurmurHash64 ( const void * key, int len, uint32_t seed=DEFAULT_SEED) { - const uint32_t m = 0x5bd1e995; - const int r = 24; - - uint32_t h1 = seed ^ len; - uint32_t h2 = 0; - - const uint32_t * data = (const uint32_t *)key; - - while(len >= 8) - { - uint32_t k1 = *data++; - k1 *= m; k1 ^= k1 >> r; k1 *= m; - h1 *= m; h1 ^= k1; - len -= 4; - - uint32_t k2 = *data++; - k2 *= m; k2 ^= k2 >> r; k2 *= m; - h2 *= m; h2 ^= k2; - len -= 4; - } - - if(len >= 4) - { - uint32_t k1 = *data++; - k1 *= m; k1 ^= k1 >> r; k1 *= m; - h1 *= m; h1 ^= k1; - len -= 4; - } - - switch(len) - { - case 3: h2 ^= ((unsigned char*)data)[2] << 16; - case 2: h2 ^= ((unsigned char*)data)[1] << 8; - case 1: h2 ^= ((unsigned char*)data)[0]; - h2 *= m; - }; - - h1 ^= h2 >> 18; h1 *= m; - h2 ^= h1 >> 22; h2 *= m; - h1 ^= h2 >> 17; h1 *= m; - h2 ^= h1 >> 19; h2 *= m; - - uint64_t h = h1; - - h = (h << 32) | h2; - - return h; + const uint32_t m = 0x5bd1e995; + const int r = 24; + + uint32_t h1 = seed ^ len; + uint32_t h2 = 0; + + const uint32_t * data = (const uint32_t *)key; + + while(len >= 8) + { + uint32_t k1 = *data++; + k1 *= m; k1 ^= k1 >> r; k1 *= m; + h1 *= m; h1 ^= k1; + len -= 4; + + uint32_t k2 = *data++; + k2 *= m; k2 ^= k2 >> r; k2 *= m; + h2 *= m; h2 ^= k2; + len -= 4; + } + + if(len >= 4) + { + uint32_t k1 = *data++; + k1 *= m; k1 ^= k1 >> r; k1 *= m; + h1 *= m; h1 ^= k1; + len -= 4; + } + + switch(len) + { + case 3: h2 ^= ((unsigned char*)data)[2] << 16; + case 2: h2 ^= ((unsigned char*)data)[1] << 8; + case 1: h2 ^= ((unsigned char*)data)[0]; + h2 *= m; + }; + + h1 ^= h2 >> 18; h1 *= m; + h2 ^= h1 >> 22; h2 *= m; + h1 ^= h2 >> 17; h1 *= m; + h2 ^= h1 >> 19; h2 *= m; + + uint64_t h = h1; + + h = (h << 32) | h2; + + return h; } #endif +//32bit #endif diff --git a/decoder/oracle_bleu.h b/decoder/oracle_bleu.h index 2ccace61..4dc86bc7 100755 --- a/decoder/oracle_bleu.h +++ b/decoder/oracle_bleu.h @@ -41,7 +41,7 @@ struct Translation { out< #include -#include #include #include #include "hg.h" @@ -169,13 +169,15 @@ struct SCFGTranslatorImpl { typedef std::pair StateSplit; typedef std::pair StateSplitPair; - typedef std::tr1::unordered_map > Split2Node; - typedef std::tr1::unordered_map > Splits; + typedef HASH_MAP > Split2Node; + typedef HASH_MAP > Splits; bool RefineForest(Hypergraph* forest) { Hypergraph refined_forest; Split2Node s2n; + HASH_MAP_RESERVED(s2n,StateSplit(-1,-1),StateSplit(-2,-2)); Splits splits; + HASH_MAP_RESERVED(splits,-1,-2); Hypergraph::Node& coarse_goal_node = *(forest->nodes_.end()-1); bool refined_goal_node = false; foreach(Hypergraph::Node& node, forest->nodes_){ diff --git a/decoder/sparse_vector.h b/decoder/sparse_vector.h index e58485c0..ec623c6e 100644 --- a/decoder/sparse_vector.h +++ b/decoder/sparse_vector.h @@ -15,7 +15,25 @@ use SparseVectorList (pair smallvector) for feat funcs / hypergraphs (you rarely need random access; just append a feature to the list) */ /* hack: index 0 never gets printed because cdyer is creative and efficient. features which have no weight got feature dict id 0, see, and the models all clobered that value. nobody wants to see it. except that vlad is also creative and efficient and stored the oracle bleu there. */ +/* NOTE: zero vals may or may not be dropped from map (sparse, but not guaranteed to be so). + I rely on !v the same as !((bool)v) the same as v==0 and v() same as v(0). + + one exception: + + a local: + T sum = 0; + is used instead of + T sum; + + because T may be a primitive type, and + + T sum(); + + is parsed as a function decl :( + + the alternative T sum=T() is also be reasonable. i've switched to that. +*/ // this is a modified version of code originally written // by Phil Blunsom @@ -78,31 +96,35 @@ public: // warning: exploits the fact that 0 values are always removed from map. change this if you change that. bool nonzero(int index) const { - return values_.find(index) != values_.end(); + typename MapType::const_iterator found = values_.find(index); + return found==values_.end() || !found->second; } - T operator[](int index) const { + T get(int index) const { typename MapType::const_iterator found = values_.find(index); - if (found == values_.end()) - return 0; - else - return found->second; + return found==values_.end()?T():found->second; } - T value(int index) const { - return (*this)[index]; + // same as above but may add a 0 entry. TODO: check that people relying on no entry use get + T & operator[](int index){ + return values_[index]; } void set_value(int index, const T &value) { values_[index] = value; } - T const& add_value(int index, const T &value) { + void add_value(int index, const T &value) { + if (!value) return; +#if 1 + values_[index]+=value; +#else + // this is not really going to be any faster, and we already rely on default init = 0 init std::pair art=values_.insert(std::make_pair(index,value)); T &val=art.first->second; if (!art.second) val += value; // already existed - return val; +#endif } @@ -125,7 +147,7 @@ public: // dot product with a unit vector of the same length // as the sparse vector T dot() const { - T sum = 0; + T sum = T(); for (typename MapType::const_iterator it = values_.begin(); it != values_.end(); ++it) sum += it->second; @@ -146,7 +168,7 @@ public: template S dot(const SparseVector &vec) const { - S sum = 0; + S sum = S(); for (typename MapType::const_iterator it = values_.begin(); it != values_.end(); ++it) { @@ -160,7 +182,7 @@ public: template S dot(const std::vector &vec) const { - S sum = 0; + S sum = S(); for (typename MapType::const_iterator it = values_.begin(); it != values_.end(); ++it) { @@ -173,7 +195,7 @@ public: template S dot(const S *vec) const { // this is not range checked! - S sum = 0; + S sum = S(); for (typename MapType::const_iterator it = values_.begin(); it != values_.end(); ++it) sum += it->second * vec[it->first]; @@ -182,7 +204,7 @@ public: } T l1norm() const { - T sum = 0; + T sum = T(); for (typename MapType::const_iterator it = values_.begin(); it != values_.end(); ++it) sum += fabs(it->second); @@ -190,7 +212,7 @@ public: } T l2norm_sq() const { - T sum = 0; + T sum = T(); for (typename MapType::const_iterator it = values_.begin(); it != values_.end(); ++it) sum += it->second * it->second; @@ -214,7 +236,7 @@ public: { // T v = (values_[it->first] += it->second); -// if (v == 0) values_.erase(it->first); +// if (!v) values_.erase(it->first); } return *this; } @@ -225,7 +247,7 @@ public: { // T v = (values_[it->first] -= it->second); -// if (v == 0) values_.erase(it->first); +// if (!v) values_.erase(it->first); } return *this; } @@ -294,7 +316,7 @@ public: for (typename MapType::const_iterator it = values_.begin(); it != values_.end(); ++it) { // by definition feature id 0 is a dummy value - if (it->first == 0) continue; + if (!it->first) continue; if (with_semi) { (*os) << (first ? "" : ";") << FD::Convert(it->first) << '=' << it->second; @@ -316,7 +338,7 @@ public: bool at_equals(int i,T const& val) const { const_iterator it=values_.find(i); - if (it==values_.end()) return val==0; + if (it==values_.end()) return !val; return it->second==val; } @@ -395,19 +417,17 @@ class SparseVectorList { SparseVectorList() { } template SparseVectorList(I i,I const& end) { - const T z=0; int c=0; for (;i const& v) { - const T z=0; for (unsigned i=0;i FeatureVectorList; -typedef SparseVector FeatureVector; -typedef SparseVector WeightVector; -typedef std::vector DenseWeightVector; template SparseVector operator+(const SparseVector& a, const SparseVector& b) { SparseVector result = a; diff --git a/decoder/trule.h b/decoder/trule.h index 3bc96165..6b98a8fa 100644 --- a/decoder/trule.h +++ b/decoder/trule.h @@ -121,7 +121,7 @@ class TRule { int Arity() const { return arity_; } bool IsUnary() const { return (Arity() == 1) && (f_.size() == 1); } const SparseVector& GetFeatureValues() const { return scores_; } - double Score(int i) const { return scores_[i]; } + double Score(int i) const { return scores_.get(i); } WordID GetLHS() const { return lhs_; } void ComputeArity(); @@ -133,8 +133,8 @@ class TRule { SparseVector scores_; char arity_; - - // these attributes are application-specific and should probably be refactored + + // these attributes are application-specific and should probably be refactored TRulePtr parent_rule_; // usually NULL, except when doing constrained decoding // this is only used when doing synchronous parsing -- cgit v1.2.3