00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include <iostream>
00023 #include <limits>
00024 #include <vector>
00025 #include <algorithm>
00026
00027 #include "TranslationOption.h"
00028 #include "TranslationOptionCollection.h"
00029 #include "Hypothesis.h"
00030 #include "Util.h"
00031 #include "SquareMatrix.h"
00032 #include "StaticData.h"
00033 #include "InputType.h"
00034 #include "Manager.h"
00035 #include "IOWrapper.h"
00036 #include "moses/FF/FFState.h"
00037 #include "moses/FF/StatefulFeatureFunction.h"
00038 #include "moses/FF/StatelessFeatureFunction.h"
00039
00040 #include <boost/foreach.hpp>
00041
00042 using namespace std;
00043
00044 namespace Moses
00045 {
00046
00047
00048 Hypothesis::
00049 Hypothesis(Manager& manager, InputType const& source, const TranslationOption &initialTransOpt, const Bitmap &bitmap, int id)
00050 : m_prevHypo(NULL)
00051 , m_sourceCompleted(bitmap)
00052 , m_sourceInput(source)
00053 , m_currSourceWordsRange(
00054 m_sourceCompleted.GetFirstGapPos()>0 ? 0 : NOT_FOUND,
00055 m_sourceCompleted.GetFirstGapPos()>0 ? m_sourceCompleted.GetFirstGapPos()-1 : NOT_FOUND)
00056 , m_currTargetWordsRange(NOT_FOUND, NOT_FOUND)
00057 , m_wordDeleted(false)
00058 , m_futureScore(0.0f)
00059 , m_estimatedScore(0.0f)
00060 , m_ffStates(StatefulFeatureFunction::GetStatefulFeatureFunctions().size())
00061 , m_arcList(NULL)
00062 , m_transOpt(initialTransOpt)
00063 , m_manager(manager)
00064 , m_id(id)
00065 {
00066
00067
00068
00069
00070
00071 const vector<const StatefulFeatureFunction*>& ffs = StatefulFeatureFunction::GetStatefulFeatureFunctions();
00072 for (unsigned i = 0; i < ffs.size(); ++i)
00073 m_ffStates[i] = ffs[i]->EmptyHypothesisState(source);
00074 }
00075
00076
00077
00078
00079 Hypothesis::
00080 Hypothesis(const Hypothesis &prevHypo, const TranslationOption &transOpt, const Bitmap &bitmap, int id)
00081 : m_prevHypo(&prevHypo)
00082 , m_sourceCompleted(bitmap)
00083 , m_sourceInput(prevHypo.m_sourceInput)
00084 , m_currSourceWordsRange(transOpt.GetSourceWordsRange())
00085 , m_currTargetWordsRange(prevHypo.m_currTargetWordsRange.GetEndPos() + 1,
00086 prevHypo.m_currTargetWordsRange.GetEndPos()
00087 + transOpt.GetTargetPhrase().GetSize())
00088 , m_wordDeleted(false)
00089 , m_futureScore(0.0f)
00090 , m_estimatedScore(0.0f)
00091 , m_ffStates(prevHypo.m_ffStates.size())
00092 , m_arcList(NULL)
00093 , m_transOpt(transOpt)
00094 , m_manager(prevHypo.GetManager())
00095 , m_id(id)
00096 {
00097
00098
00099 m_currScoreBreakdown.PlusEquals(transOpt.GetScoreBreakdown());
00100 m_wordDeleted = transOpt.IsDeletionOption();
00101 }
00102
00103 Hypothesis::
00104 ~Hypothesis()
00105 {
00106 for (unsigned i = 0; i < m_ffStates.size(); ++i)
00107 delete m_ffStates[i];
00108
00109 if (m_arcList) {
00110 ArcList::iterator iter;
00111 for (iter = m_arcList->begin() ; iter != m_arcList->end() ; ++iter) {
00112 delete *iter;
00113 }
00114 m_arcList->clear();
00115
00116 delete m_arcList;
00117 m_arcList = NULL;
00118 }
00119 }
00120
00121 void
00122 Hypothesis::
00123 AddArc(Hypothesis *loserHypo)
00124 {
00125 if (!m_arcList) {
00126 if (loserHypo->m_arcList) {
00127 this->m_arcList = loserHypo->m_arcList;
00128 loserHypo->m_arcList = 0;
00129 } else {
00130 this->m_arcList = new ArcList();
00131 }
00132 } else {
00133 if (loserHypo->m_arcList) {
00134 size_t my_size = m_arcList->size();
00135 size_t add_size = loserHypo->m_arcList->size();
00136 this->m_arcList->resize(my_size + add_size, 0);
00137 std::memcpy(&(*m_arcList)[0] + my_size, &(*loserHypo->m_arcList)[0], add_size * sizeof(Hypothesis *));
00138 delete loserHypo->m_arcList;
00139 loserHypo->m_arcList = 0;
00140 } else {
00141
00142 }
00143 }
00144 m_arcList->push_back(loserHypo);
00145 }
00146
00147
00148
00149
00150 void
00151 Hypothesis::
00152 EvaluateWhenApplied(float estimatedScore)
00153 {
00154 const StaticData &staticData = StaticData::Instance();
00155
00156
00157
00158
00159
00160
00161
00162
00163 const vector<const StatelessFeatureFunction*>& sfs =
00164 StatelessFeatureFunction::GetStatelessFeatureFunctions();
00165 for (unsigned i = 0; i < sfs.size(); ++i) {
00166 const StatelessFeatureFunction &ff = *sfs[i];
00167 if(!staticData.IsFeatureFunctionIgnored(ff)) {
00168 ff.EvaluateWhenApplied(*this, &m_currScoreBreakdown);
00169 }
00170 }
00171
00172 const vector<const StatefulFeatureFunction*>& ffs =
00173 StatefulFeatureFunction::GetStatefulFeatureFunctions();
00174 for (unsigned i = 0; i < ffs.size(); ++i) {
00175 const StatefulFeatureFunction &ff = *ffs[i];
00176 if(!staticData.IsFeatureFunctionIgnored(ff)) {
00177 FFState const* s = m_prevHypo ? m_prevHypo->m_ffStates[i] : NULL;
00178 m_ffStates[i] = ff.EvaluateWhenApplied(*this, s, &m_currScoreBreakdown);
00179 }
00180 }
00181
00182
00183 m_estimatedScore = estimatedScore;
00184
00185
00186 m_futureScore = m_currScoreBreakdown.GetWeightedScore() + m_estimatedScore;
00187 if (m_prevHypo) m_futureScore += m_prevHypo->GetScore();
00188 }
00189
00190 const Hypothesis* Hypothesis::GetPrevHypo()const
00191 {
00192 return m_prevHypo;
00193 }
00194
00198 void
00199 Hypothesis::
00200 PrintHypothesis() const
00201 {
00202 if (!m_prevHypo) {
00203 TRACE_ERR(endl << "NULL hypo" << endl);
00204 return;
00205 }
00206 TRACE_ERR(endl << "creating hypothesis "<< m_id <<" from "<< m_prevHypo->m_id<<" ( ");
00207 int end = (int)(m_prevHypo->GetCurrTargetPhrase().GetSize()-1);
00208 int start = end-1;
00209 if ( start < 0 ) start = 0;
00210 if ( m_prevHypo->m_currTargetWordsRange.GetStartPos() == NOT_FOUND ) {
00211 TRACE_ERR( "<s> ");
00212 } else {
00213 TRACE_ERR( "... ");
00214 }
00215 if (end>=0) {
00216 Range range(start, end);
00217 TRACE_ERR( m_prevHypo->GetCurrTargetPhrase().GetSubString(range) << " ");
00218 }
00219 TRACE_ERR( ")"<<endl);
00220 TRACE_ERR( "\tbase score "<< (m_prevHypo->m_futureScore - m_prevHypo->m_estimatedScore) <<endl);
00221 TRACE_ERR( "\tcovering "<<m_currSourceWordsRange.GetStartPos()<<"-"<<m_currSourceWordsRange.GetEndPos()
00222 <<": " << m_transOpt.GetInputPath().GetPhrase() << endl);
00223
00224 TRACE_ERR( "\ttranslated as: "<<(Phrase&) GetCurrTargetPhrase()<<endl);
00225
00226 if (m_wordDeleted) TRACE_ERR( "\tword deleted"<<endl);
00227
00228
00229
00230 TRACE_ERR( "\tscore "<<m_futureScore - m_estimatedScore<<" + future cost "<<m_estimatedScore<<" = "<<m_futureScore<<endl);
00231 TRACE_ERR( "\tunweighted feature scores: " << m_currScoreBreakdown << endl);
00232
00233 }
00234
00235 void
00236 Hypothesis::
00237 CleanupArcList(size_t nBestSize, bool distinctNBest)
00238 {
00239
00240 SetWinningHypo(this);
00241
00242 if (!m_arcList) return;
00243
00244
00245
00246
00247
00248
00249 if (!distinctNBest && m_arcList->size() > nBestSize * 5) {
00250
00251 NTH_ELEMENT4(m_arcList->begin(), m_arcList->begin() + nBestSize - 1,
00252 m_arcList->end(), CompareHypothesisTotalScore());
00253
00254
00255 ArcList::iterator i = m_arcList->begin() + nBestSize;
00256 while (i != m_arcList->end()) delete *i++;
00257 m_arcList->erase(m_arcList->begin() + nBestSize, m_arcList->end());
00258 }
00259
00260
00261 ArcList::iterator iter = m_arcList->begin();
00262 for (; iter != m_arcList->end() ; ++iter) {
00263 Hypothesis *arc = *iter;
00264 arc->SetWinningHypo(this);
00265 }
00266 }
00267
00268 TargetPhrase const&
00269 Hypothesis::
00270 GetCurrTargetPhrase() const
00271 {
00272 return m_transOpt.GetTargetPhrase();
00273 }
00274
00275 void
00276 Hypothesis::
00277 GetOutputPhrase(Phrase &out) const
00278 {
00279 if (m_prevHypo != NULL)
00280 m_prevHypo->GetOutputPhrase(out);
00281 out.Append(GetCurrTargetPhrase());
00282 }
00283
00284 TO_STRING_BODY(Hypothesis)
00285
00286
00287 ostream& operator<<(ostream& out, const Hypothesis& hypo)
00288 {
00289 hypo.ToStream(out);
00290
00291 out << "[" << hypo.m_sourceCompleted << "] ";
00292
00293
00294 out << " [total=" << hypo.GetFutureScore() << "]";
00295 out << " " << hypo.GetScoreBreakdown();
00296
00297
00298 out << " " << hypo.GetCurrTargetPhrase().GetAlignNonTerm();
00299
00300 return out;
00301 }
00302
00303
00304 std::string
00305 Hypothesis::
00306 GetSourcePhraseStringRep(const vector<FactorType> factorsToPrint) const
00307 {
00308 return m_transOpt.GetInputPath().GetPhrase().GetStringRep(factorsToPrint);
00309 }
00310
00311 std::string
00312 Hypothesis::
00313 GetTargetPhraseStringRep(const vector<FactorType> factorsToPrint) const
00314 {
00315 return (m_prevHypo
00316 ? GetCurrTargetPhrase().GetStringRep(factorsToPrint)
00317 : "");
00318 }
00319
00320 std::string
00321 Hypothesis::
00322 GetSourcePhraseStringRep() const
00323 {
00324 vector<FactorType> allFactors(MAX_NUM_FACTORS);
00325 for(size_t i=0; i < MAX_NUM_FACTORS; i++)
00326 allFactors[i] = i;
00327 return GetSourcePhraseStringRep(allFactors);
00328 }
00329
00330 std::string
00331 Hypothesis::
00332 GetTargetPhraseStringRep() const
00333 {
00334 vector<FactorType> allFactors(MAX_NUM_FACTORS);
00335 for(size_t i=0; i < MAX_NUM_FACTORS; i++)
00336 allFactors[i] = i;
00337 return GetTargetPhraseStringRep(allFactors);
00338 }
00339
00340 size_t
00341 Hypothesis::
00342 OutputAlignment(std::ostream &out, bool recursive=true) const
00343 {
00344 WordAlignmentSort const& waso = m_manager.options()->output.WA_SortOrder;
00345 TargetPhrase const& tp = GetCurrTargetPhrase();
00346
00347
00348 size_t trg_off = recursive && m_prevHypo ? m_prevHypo->OutputAlignment(out) : 0;
00349 size_t src_off = GetCurrSourceWordsRange().GetStartPos();
00350
00351 typedef std::pair<size_t,size_t> const* entry;
00352 std::vector<entry> alnvec = tp.GetAlignTerm().GetSortedAlignments(waso);
00353 BOOST_FOREACH(entry e, alnvec)
00354 out << e->first + src_off << "-" << e->second + trg_off << " ";
00355 return trg_off + tp.GetSize();
00356 }
00357
00358 void
00359 Hypothesis::
00360 OutputInput(std::vector<const Phrase*>& map, const Hypothesis* hypo)
00361 {
00362 if (!hypo->GetPrevHypo()) return;
00363 OutputInput(map, hypo->GetPrevHypo());
00364 map[hypo->GetCurrSourceWordsRange().GetStartPos()]
00365 = &hypo->GetTranslationOption().GetInputPath().GetPhrase();
00366 }
00367
00368 void
00369 Hypothesis::
00370 OutputInput(std::ostream& os) const
00371 {
00372 size_t len = this->GetInput().GetSize();
00373 std::vector<const Phrase*> inp_phrases(len, 0);
00374 OutputInput(inp_phrases, this);
00375 for (size_t i=0; i<len; ++i)
00376 if (inp_phrases[i]) os << *inp_phrases[i];
00377 }
00378
00379 std::map<size_t, const Factor*>
00380 Hypothesis::
00381 GetPlaceholders(const Hypothesis &hypo, FactorType placeholderFactor) const
00382 {
00383 const InputPath &inputPath = hypo.GetTranslationOption().GetInputPath();
00384 const Phrase &inputPhrase = inputPath.GetPhrase();
00385
00386 std::map<size_t, const Factor*> ret;
00387
00388 for (size_t sourcePos = 0; sourcePos < inputPhrase.GetSize(); ++sourcePos) {
00389 const Factor *factor = inputPhrase.GetFactor(sourcePos, placeholderFactor);
00390 if (factor) {
00391 std::set<size_t> targetPos = hypo.GetTranslationOption().GetTargetPhrase().GetAlignTerm().GetAlignmentsForSource(sourcePos);
00392 UTIL_THROW_IF2(targetPos.size() != 1,
00393 "Placeholder should be aligned to 1, and only 1, word");
00394 ret[*targetPos.begin()] = factor;
00395 }
00396 }
00397
00398 return ret;
00399 }
00400
00401 size_t Hypothesis::hash() const
00402 {
00403 size_t seed;
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413 seed = m_sourceCompleted.hash();
00414
00415
00416 for (size_t i = 0; i < m_ffStates.size(); ++i) {
00417 const FFState *state = m_ffStates[i];
00418 size_t hash = state->hash();
00419 boost::hash_combine(seed, hash);
00420 }
00421 return seed;
00422 }
00423
00424 bool Hypothesis::operator==(const Hypothesis& other) const
00425 {
00426
00427 if (&m_sourceCompleted != &other.m_sourceCompleted) {
00428 return false;
00429 }
00430
00431
00432 for (size_t i = 0; i < m_ffStates.size(); ++i) {
00433 const FFState &thisState = *m_ffStates[i];
00434 const FFState &otherState = *other.m_ffStates[i];
00435 if (thisState != otherState) {
00436 return false;
00437 }
00438 }
00439 return true;
00440 }
00441
00442 bool
00443 Hypothesis::
00444 beats(Hypothesis const& b) const
00445 {
00446 if (m_futureScore != b.m_futureScore)
00447 return m_futureScore > b.m_futureScore;
00448 else if (m_estimatedScore != b.m_estimatedScore)
00449 return m_estimatedScore > b.m_estimatedScore;
00450 else if (m_prevHypo)
00451 return b.m_prevHypo ? m_prevHypo->beats(*b.m_prevHypo) : true;
00452 else return false;
00453
00454
00455
00456 }
00457
00458 }
00459