diff options
Diffstat (limited to 'decoder/dwarf.h')
| -rw-r--r-- | decoder/dwarf.h | 286 |
1 files changed, 286 insertions, 0 deletions
diff --git a/decoder/dwarf.h b/decoder/dwarf.h new file mode 100644 index 00000000..83a0cae9 --- /dev/null +++ b/decoder/dwarf.h @@ -0,0 +1,286 @@ +#ifndef DWARF_H +#define DWARF_H + +#include <cstdlib> +#include <vector> +#include <map> +#include <string> +#include <ostream> +#include "wordid.h" +#include "lattice.h" +#include "trule.h" +#include "tdict.h" +#include <boost/functional/hash.hpp> +#include <tr1/unordered_map> +#include <boost/tuple/tuple.hpp> + +using namespace std; +using namespace std::tr1; +using namespace boost::tuples; +using namespace boost; + +const static bool DEBUG = false; + +class CountTable { +public: + int* ultimate; + map<WordID,int*> model; + int mode; + int numColumn; + const void print(); + void setup(int _numcolumn, int _mode) { + mode = _mode; numColumn = _numcolumn; + } +}; + +class Alignment { +/* Alignment represents an alignment object in a 2D format to support function word-based models calculation + + A note about model's parameter estimation: + ========================================== + The model is estimated as a two-level Dirichlet process. + For orientation model, the first tier estimation is: + P(o|f,e) where *o* is the orientation value to estimate, *f* is the source function word aligned to *e* + its second tier is: P(o|f), while its third tier is P(o) + For dominance model, the first tier estimation is: + P(d|f1,f2,e1,e2) where *d* is a dominance value to estimate, *f1,f2* are the neighboring function words on the source + aligned to *e1,e2* on the target side + its second tier is: P(d|f1,f2) while its third tier is P(d) + + Taking orientation model as a case in point, a two level estimation proceeds as follow: + P(o|f,e) = c(o,f,e) + alpha { c(o,f) + beta [ c (o) / c(.) ] } + ------------------------------ + c(f) + beta + ------------------------------------------------- + c(f,e) + alpha + where c() is a count function, alpha and beta are the concentration parameter + of the first and second Dirichlet process respectively + To encourage or penalize the use of second and third tier statistics, bo1 and bo2 binary features are introduced +*/ +public: + const static int MAX_WORDS = 200; + const static int MINIMUM_INIT = 1000; + const static int MAXIMUM_INIT = -1000; + const static int MAX_ARITY = 2; + WordID kSOS; + WordID kEOS; + WordID kUNK; + double alpha_oris; // 1st concentration parameter for orientation model + double beta_oris; // 2nd concentration parameter for orientation model + double alpha_orit; // 1st concentration parameter for orientation model + double beta_orit; // 2nd concentration parameter for orientation model + double alpha_doms; // idem as above but for dominance model + double beta_doms; + double alpha_domt; // idem as above but for dominance model + double beta_domt; + + // ACCESS to alignment + void set(int j,int i); // j is the source index, while i is the target index + void reset(int j,int i); // idem as above + inline bool at(int j, int i) { return _matrix[j][i]; }; + inline int getJ() {return _J;}; // max source of the current alignment + inline int getI() {return _I;}; // max target of the current alignment + inline void setI(int I) { _I = I; }; + inline void setJ(int J) { _J = J; }; + inline void setF(vector<WordID> f) { _f=f;}; + inline void setE(vector<WordID> e) { _e=e;}; + inline WordID getF(int id) { if (id<0) return TD::Convert("<s>"); if (id>=_f.size()) return TD::Convert("</s>"); return _f[id];}; + inline WordID getE(int id) { if (id<0) return TD::Convert("<s>"); if (id>=_e.size()) return TD::Convert("</s>"); return _e[id];}; + void clearAls(int prevJ=200, int prevI=200); + int sourceOf(int i, int start = -1); + int targetOf(int j, int start = -1); + inline int minSSpan(int i) { return _sSpan[i][0];} + inline int maxSSpan(int i) { return _sSpan[i][1];} + inline int minTSpan(int j) { return _tSpan[j][0];} + inline int maxTSpan(int j) { return _tSpan[j][1];} + static inline int link(int s, int t) { return (s << 16) | t; } + static inline int source(int st) {return st >> 16; } + static inline int target(int st) {return st & 0xffff; } + inline void setAlphaOris(double val) { alpha_oris=val; } + inline void setAlphaOrit(double val) { alpha_orit=val; } + inline void setAlphaDoms(double val) { alpha_doms=val; } + inline void setAlphaDomt(double val) { alpha_domt=val; } + inline void setBetaOris(double val) { beta_oris=val; } + inline void setBetaOrit(double val) { beta_orit=val; } + inline void setBetaDoms(double val) { beta_doms=val; } + inline void setBetaDomt(double val) { beta_domt=val; } + inline void setFreqCutoff(int val) { cout << _freq_cutoff << " to " << val << endl; _freq_cutoff=val; } + string AsString(); + string AsStringSimple(); + int* SOS(); + int* EOS(); + + // Model related function + Alignment(); + // Given the current *rule* and its antecedents, construct an alignment space and mark the function word alignments + // according *sfw* and *tfw* + bool prepare(TRule& rule, const std::vector<const void*>& ant_contexts, + const map<WordID,int>& sfw, const map<WordID,int>& tfw, const Lattice& sourcelattice, int spanstart, int spanend); + + // Compute orientation model score which parameters are stored in *table* and pass the values accordingly + // will call Orientation(Source|Target) and ScoreOrientation(Source|Target) + void computeOrientationSource(const CountTable& table, double *cost, double *bonus, double *bo1, + double *bo1_bonus, double *bo2, double *bo2_bonus); + void computeOrientationSourcePos(const CountTable& table, double *cost, double *bonus, + double *bo1, double *bo1_bonus, double *bo2, double *bo2_bonus, int maxfwidx, int maxdepth1, int maxdepth2); + void computeOrientationSourceGen(const CountTable& table, double *cost, double *bonus, double *bo1, + double *bo1_bonus, double *bo2, double *bo2_bonus, const map<WordID,WordID>& tags); + void computeOrientationSourceBackward(const CountTable& table, double *cost, double *bonus, double *bo1, + double *bo1_bonus, double *bo2, double *bo2_bonus); + void computeOrientationSourceBackwardPos(const CountTable& table, double *cost, double *bonus, double *bo1, + double *bo1_bonus, double *bo2, double *bo2_bonus, int maxfwidx, int maxdepth1, int maxdepth2); + void computeOrientationTarget(const CountTable& table, double *cost, double *bonus, double *bo1, + double *bo1_bonus, double *bo2, double *bo2_bonus); + void computeOrientationTargetBackward(const CountTable& table, double *cost, double *bonus, double *bo1, + double *bo1_bonus, double *bo2, double *bo2_bonus); + // Get the orientation value of a function word at a particular index *fw* + // assign the value to either *oril* or *orir* accoring to *Lcompute* and *Rcompute* + void OrientationSource(int fw, int*oril, int* orir, bool Lcompute=true, bool Rcompute=true); + void OrientationSource(int fw0, int fw1, int*oril, int* orir, bool Lcompute=true, bool Rcompute=true); + int OrientationSource(int* left, int* right); + void OrientationTarget(int fw, int*oril, int* orir, bool Lcompute=true, bool Rcompute=true); + void OrientationTarget(int fw0, int fw1, int*oril, int* orir, bool Lcompute=true, bool Rcompute=true); + + vector<int> OrientationSourceLeft4Sampler(int fw0, int fw1); + vector<int> OrientationSourceLeft4Sampler(int fw); + vector<int> OrientationSourceRight4Sampler(int fw0, int fw1); + vector<int> OrientationSourceRight4Sampler(int fw); + vector<int> OrientationTargetLeft4Sampler(int fw0, int fw1); + vector<int> OrientationTargetLeft4Sampler(int fw); + vector<int> OrientationTargetRight4Sampler(int fw0, int fw1); + vector<int> OrientationTargetRight4Sampler(int fw); + + // Given an orientation value *ori*, estimate the score accoding to *cond1*, *cond2* + // and assign the value accordingly according to *isBonus* and whether the first or the second tier estimation + // is used or not + void ScoreOrientationRight(const CountTable& table, int ori, WordID cond1, WordID cond2, + bool isBonus, double *cost, double *bonus, double *bo1, double *bo1_bonus, + double *bo2, double *bo2_bonus, double alpha1, double beta1); + void ScoreOrientationLeft(const CountTable& table, int ori, WordID cond1, WordID cond, + bool isBonus, double *cost, double *bonus, double *bo1, double *bo1_bonus, + double *bo2, double *bo2_bonus, double alpha1, double beta1); + double ScoreOrientationRight(const CountTable& table, int ori, WordID cond1, WordID cond2); + double ScoreOrientationLeft(const CountTable& table, int ori, WordID cond1, WordID cond); + void ScoreOrientationRightBackward(const CountTable& table, int ori, WordID cond1, WordID cond2, + bool isBonus, double *cost, double *bonus, double *bo1, double *bo1_bonus, + double *bo2, double *bo2_bonus, double alpha1, double beta1); + void ScoreOrientationLeftBackward(const CountTable& table, int ori, WordID cond1, WordID cond, + bool isBonus, double *cost, double *bonus, double *bo1, double *bo1_bonus, + double *bo2, double *bo2_bonus, double alpha1, double beta1); + double ScoreOrientationRightBackward(const CountTable& table, int ori, WordID cond1, WordID cond2); + double ScoreOrientationLeftBackward(const CountTable& table, int ori, WordID cond1, WordID cond); + void ScoreOrientation(const CountTable& table, int offset, int ori, WordID cond1, WordID cond2, + bool isBonus, double *cost, double *bonus, double *bo1, double *bo1_bonus, + double *bo2, double *bo2_bonus, double alpha1, double beta1); + double ScoreOrientation(const CountTable& table, int offset, int ori, WordID cond1, WordID cond2); + + // idem as above except these are for dominance model + void computeDominanceSource(const CountTable& table, WordID lfw, WordID rfw, double *cost, double *bonus, + double *bo1, double *bo1_bonus, double *bo2, double *bo2_bonus); + void computeDominanceSourcePos(const CountTable& table, WordID lfw, WordID rfw, double *cost, double *bonus, + double *bo1, double *bo1_bonus, double *bo2, double *bo2_bonus, int maxfwidx, int maxdepth1, int maxdepth2); + void computeDominanceTarget(const CountTable& table, WordID lfw, WordID rfw, double *cost, double *bonus, + double *bo1, double *bo1_bonus, double *bo2, double *bo2_bonus); + void computeBorderDominanceSource(const CountTable& table, double *cost, double *bonus, + double *state_mono, double *state_nonmono, + TRule &rule, const std::vector<const void*>& ant_contexts, const map<WordID,int>& sfw); + int DominanceSource(int fw1, int fw2); + int DominanceTarget(int fw1, int fw2); + vector<int> DominanceSource4Sampler(int fw1, int fw2); + vector<int> DominanceTarget4Sampler(int fw1, int fw2); + void ScoreDominance(const CountTable& table, int dom, WordID s1, WordID s2, WordID t1, WordID t2, + double *cost, double *bo1, double *bo2, bool isBonus, double alpha2, double beta2); + double ScoreDominance(const CountTable& table, int dom, WordID s1, WordID s2, WordID t1, WordID t2); + + // Remove all function word alignments except those at the borders + // May result in more than two function word alignments at each side, because this function + // will continue keeping function word alignments until the first aligned word at each side + void BorderingSFWsOnly(); + void BorderingTFWsOnly(); + void simplify(int *ret); // preparing the next state + void simplify_nofw(int *ret); // preparing the next state when no function word appears + // set the first part of the next state, which concerns with function word + // fas, las, fat, lat is the (f)irst or (l)ast function word alignments either on the (s)ource or (t)arget + // these parameters to anticipate cases where there are more than two function word alignments + void FillFWIdxsState(int *state, int fas, int las, int fat, int lat); + + // Helper function to obtain the aligned words on the other side + // WARNING!!! Only to be used if the als are in sync with either source or target sentences + WordID F2EProjectionFromExternal(int idx, const vector<AlignmentPoint>& als, const string& delimiter=" "); + WordID E2FProjectionFromExternal(int idx, const vector<AlignmentPoint>& als, const string& delimiter=" "); + // WARNING!!! Only to be used in dwarf_main.cc + // These two function words assume that the alignment contains phrase boundary + // but the source and target sentences do not + WordID F2EProjection(int idx, const string& delimiter=" "); + WordID E2FProjection(int idx, const string& delimiter=" "); + void SetCurrAlVector(); + int* blockSource(int fw1, int fw2); + int* blockTarget(int fw1, int fw2); + void ToArrayInt(vector<int>* arr); + int* neighborLeft(int startidx, int endidx, bool* found); + int* neighborRight(int startidx, int endidx, bool* found); +private: + // Hash to avoid redundancy + unordered_map<vector<int>, int, boost::hash<vector<int> > > oris_hash; + unordered_map<vector<int>, int, boost::hash<vector<int> > > orit_hash; + unordered_map<vector<int>, int, boost::hash<vector<int> > > doms_hash; + unordered_map<vector<int>, int, boost::hash<vector<int> > > domt_hash; + unordered_map<vector<int>, vector<int>, boost::hash<vector<int> > > simplify_hash; + unordered_map<vector<int>, vector<int>, boost::hash<vector<int> > > prepare_hash; + + int _J; // effective source length; + int _I; // effective target length; + bool _matrix[MAX_WORDS][MAX_WORDS]; // true if aligned + short _sSpan[MAX_WORDS][2]; //the source span of a target index; 0->min, 1->max + short _tSpan[MAX_WORDS][2]; //the target span of a source index; 0->min, 2->max + int _freq_cutoff; + int SourceFWRuleIdxs[40]; //the indexes of function words in the rule; + // The following applies to all *FW*Idxs + // *FW*Idxs[0] = size + // *FW*Idxs[idx*3-2] = index in the alignment, where idx starts from 1 to size + // *FW*Idxs[idx*3-1] = source WordID + // *FW*Idxs[idx*3] = target WordID + int SourceFWRuleAbsIdxs[40]; + int TargetFWRuleIdxs[40]; //the indexes of function words in the rule; zeroth element is the count + int ** SourceFWAntsIdxs; //the indexes of function words in antecedents + int ** SourceFWAntsAbsIdxs; + int ** TargetFWAntsIdxs; //the indexes of function words in antecedents + int SourceRuleIdxs[40]; //the indexes of SOURCE tokens (zeroth element is the number of source tokens) + //>0 means terminal, -i means the i-th Xs + int TargetRuleIdxs[40]; //the indexes of TARGET tokens (zeroth element is the number of target tokens) + int ** SourceAntsIdxs; //the array of indexes of a particular antecedent's SOURCE tokens + int ** TargetAntsIdxs; //the array of indexes of a particular antecedent's TARGET tokens + int SourceFWIdxs[40]; + int SourceFWAbsIdxs[40]; + int TargetFWIdxs[40]; + // *sort* and *quickSort* are used to sort *FW*Idxs + void sort(int* num); + void quickSort(int arr[], int top, int bottom); + + // *block(Source|Target)* finds the minimum block that containts two indexes (fw1 and fw2) + inline int least(int i1, int i2) { return (i1<i2)?i1:i2; } + inline int most(int i1, int i2) { return (i1>i2)?i1:i2; } + void simplifyBackward(vector<int *>*blocks, int* block, const vector<int>& danglings); + // used in simplify to check whether an atomic block according to source function words is also atomic according + // to target function words as well, otherwise break it + // the resulting blocks are added into *blocks* + int _Arity; + std::vector<WordID> _f; // the source sentence of the **current** rule (may not consistent with the current alignment) + std::vector<WordID> _e; // the target sentence of the **current** rule + int RuleAl[40]; + int **AntsAl; + int firstSourceAligned(int start); + int firstTargetAligned(int start); + int lastSourceAligned(int end); + int lastTargetAligned(int end); + int fas, las, fat, lat; // first aligned source, last aligned source, first aligned target, last aligned target + bool MemberOf(int* FWIdxs, int pos1, int pos2); // whether FWIdxs contains pos1 and pos2 consecutively + // Convert the alignment to vector form, will be used for hashing purposes + vector<int> curr_al; + int GetFWGlobalIdx(int idx, const Lattice& sourcelattice, vector<WordID>& sources, int spanstart, int spanend, const std::vector<const void*>& ant_contexts, const map<WordID,int>& sfw); + int GetFirstFWIdx(int spanstart,int spanend, const Lattice& sourcelattice, const map<WordID,int>& sfw); + int GetLastFWIdx(int spanstart,int spanend, const Lattice& sourcelattice, const map<WordID,int>& sfw); + WordID generalize(WordID original, const map<WordID,WordID>& tags, bool pos=false); +}; + +#endif |