00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include <algorithm>
00023 #include <limits>
00024 #include <utility>
00025
00026 #include "BitmapContainer.h"
00027 #include "HypothesisStackCubePruning.h"
00028 #include "moses/FF/DistortionScoreProducer.h"
00029 #include "TranslationOptionList.h"
00030 #include "Manager.h"
00031
00032 namespace Moses
00033 {
00034
00035 class HypothesisScoreOrdererNoDistortion
00036 {
00037 public:
00038 bool operator()(const Hypothesis* hypoA, const Hypothesis* hypoB) const {
00039 const float scoreA = hypoA->GetScore();
00040 const float scoreB = hypoB->GetScore();
00041
00042 if (scoreA > scoreB) {
00043 return true;
00044 } else if (scoreA < scoreB) {
00045 return false;
00046 } else {
00047 return hypoA < hypoB;
00048 }
00049 }
00050 };
00051
00052 class HypothesisScoreOrdererWithDistortion
00053 {
00054 private:
00055 bool m_deterministic;
00056
00057 public:
00058 HypothesisScoreOrdererWithDistortion(const Range* transOptRange,
00059 const bool deterministic = false)
00060 : m_deterministic(deterministic)
00061 , m_transOptRange(transOptRange) {
00062 m_totalWeightDistortion = 0;
00063 const StaticData &staticData = StaticData::Instance();
00064
00065 const std::vector<const DistortionScoreProducer*> &ffs = DistortionScoreProducer::GetDistortionFeatureFunctions();
00066 std::vector<const DistortionScoreProducer*>::const_iterator iter;
00067 for (iter = ffs.begin(); iter != ffs.end(); ++iter) {
00068 const DistortionScoreProducer *ff = *iter;
00069
00070 float weight =staticData.GetAllWeights().GetScoreForProducer(ff);
00071 m_totalWeightDistortion += weight;
00072 }
00073 }
00074
00075 const Range* m_transOptRange;
00076 float m_totalWeightDistortion;
00077
00078 bool operator()(const Hypothesis* hypoA, const Hypothesis* hypoB) const {
00079 UTIL_THROW_IF2(m_transOptRange == NULL, "Words range not set");
00080
00081
00082 const float distortionScoreA = DistortionScoreProducer::CalculateDistortionScore(
00083 *hypoA,
00084 hypoA->GetCurrSourceWordsRange(),
00085 *m_transOptRange,
00086 hypoA->GetWordsBitmap().GetFirstGapPos()
00087 );
00088 const float distortionScoreB = DistortionScoreProducer::CalculateDistortionScore(
00089 *hypoB,
00090 hypoB->GetCurrSourceWordsRange(),
00091 *m_transOptRange,
00092 hypoB->GetWordsBitmap().GetFirstGapPos()
00093 );
00094
00095
00096 const float scoreA = hypoA->GetScore() + distortionScoreA * m_totalWeightDistortion;
00097 const float scoreB = hypoB->GetScore() + distortionScoreB * m_totalWeightDistortion;
00098
00099
00100 if (scoreA > scoreB) {
00101 return true;
00102 } else if (scoreA < scoreB) {
00103 return false;
00104 } else {
00105 if (m_deterministic) {
00106
00107 return (hypoA->GetCurrTargetPhrase().Compare(hypoB->GetCurrTargetPhrase()) < 0);
00108 }
00109
00110 return hypoA < hypoB;
00111 }
00112 }
00113
00114 };
00115
00117
00119
00120 BackwardsEdge::BackwardsEdge(const BitmapContainer &prevBitmapContainer
00121 , BitmapContainer &parent
00122 , const TranslationOptionList &translations
00123 , const SquareMatrix &estimatedScores,
00124 const InputType& itype,
00125 const bool deterministic)
00126 : m_initialized(false)
00127 , m_prevBitmapContainer(prevBitmapContainer)
00128 , m_parent(parent)
00129 , m_translations(translations)
00130 , m_estimatedScores(estimatedScores)
00131 , m_deterministic(deterministic)
00132 , m_seenPosition()
00133 {
00134
00135
00136 if(m_prevBitmapContainer.GetHypotheses().size() == 0 || m_translations.size() == 0) {
00137 VERBOSE(3, "Empty cube on BackwardsEdge" << std::endl);
00138 return;
00139 }
00140
00141
00142
00143 int maxDistortion = itype.options()->reordering.max_distortion;
00144
00145 if (maxDistortion == -1) {
00146 for (HypothesisSet::const_iterator iter = m_prevBitmapContainer.GetHypotheses().begin(); iter != m_prevBitmapContainer.GetHypotheses().end(); ++iter) {
00147 m_hypotheses.push_back(*iter);
00148 }
00149 return;
00150 }
00151
00152 const Range &transOptRange = translations.Get(0)->GetSourceWordsRange();
00153
00154 HypothesisSet::const_iterator iterHypo = m_prevBitmapContainer.GetHypotheses().begin();
00155 HypothesisSet::const_iterator iterEnd = m_prevBitmapContainer.GetHypotheses().end();
00156
00157 while (iterHypo != iterEnd) {
00158 const Hypothesis &hypo = **iterHypo;
00159
00160
00161
00162 if (hypo.GetWordsBitmap().GetNumWordsCovered() == 0) {
00163 if ((int)transOptRange.GetStartPos() <= maxDistortion)
00164 m_hypotheses.push_back(&hypo);
00165 } else {
00166 int distortionDistance = itype.ComputeDistortionDistance(hypo.GetCurrSourceWordsRange()
00167 , transOptRange);
00168
00169 if (distortionDistance <= maxDistortion)
00170 m_hypotheses.push_back(&hypo);
00171 }
00172
00173 ++iterHypo;
00174 }
00175
00176 if (m_translations.size() > 1) {
00177 UTIL_THROW_IF2(m_translations.Get(0)->GetFutureScore() < m_translations.Get(1)->GetFutureScore(),
00178 "Non-monotonic future score: "
00179 << m_translations.Get(0)->GetFutureScore() << " vs. "
00180 << m_translations.Get(1)->GetFutureScore());
00181 }
00182
00183 if (m_hypotheses.size() > 1) {
00184 UTIL_THROW_IF2(m_hypotheses[0]->GetFutureScore() < m_hypotheses[1]->GetFutureScore(),
00185 "Non-monotonic total score"
00186 << m_hypotheses[0]->GetFutureScore() << " vs. "
00187 << m_hypotheses[1]->GetFutureScore());
00188 }
00189
00190 HypothesisScoreOrdererWithDistortion orderer (&transOptRange, m_deterministic);
00191 std::sort(m_hypotheses.begin(), m_hypotheses.end(), orderer);
00192
00193
00194 }
00195
00196 BackwardsEdge::~BackwardsEdge()
00197 {
00198 m_seenPosition.clear();
00199 m_hypotheses.clear();
00200 }
00201
00202
00203 void
00204 BackwardsEdge::Initialize()
00205 {
00206 if(m_hypotheses.size() == 0 || m_translations.size() == 0) {
00207 m_initialized = true;
00208 return;
00209 }
00210
00211 const Bitmap &bm = m_hypotheses[0]->GetWordsBitmap();
00212 const Range &newRange = m_translations.Get(0)->GetSourceWordsRange();
00213 m_estimatedScore = m_estimatedScores.CalcEstimatedScore(bm, newRange.GetStartPos(), newRange.GetEndPos());
00214
00215 Hypothesis *expanded = CreateHypothesis(*m_hypotheses[0], *m_translations.Get(0));
00216 m_parent.Enqueue(0, 0, expanded, this);
00217 SetSeenPosition(0, 0);
00218 m_initialized = true;
00219 }
00220
00221 Hypothesis *BackwardsEdge::CreateHypothesis(const Hypothesis &hypothesis, const TranslationOption &transOpt)
00222 {
00223
00224 IFVERBOSE(2) {
00225 hypothesis.GetManager().GetSentenceStats().StartTimeBuildHyp();
00226 }
00227 const Bitmap &bitmap = m_parent.GetWordsBitmap();
00228 Hypothesis *newHypo = new Hypothesis(hypothesis, transOpt, bitmap, hypothesis.GetManager().GetNextHypoId());
00229 IFVERBOSE(2) {
00230 hypothesis.GetManager().GetSentenceStats().StopTimeBuildHyp();
00231 }
00232 newHypo->EvaluateWhenApplied(m_estimatedScore);
00233
00234 return newHypo;
00235 }
00236
00237 bool
00238 BackwardsEdge::SeenPosition(const size_t x, const size_t y)
00239 {
00240 boost::unordered_set< int >::iterator iter = m_seenPosition.find((x<<16) + y);
00241 return (iter != m_seenPosition.end());
00242 }
00243
00244 void
00245 BackwardsEdge::SetSeenPosition(const size_t x, const size_t y)
00246 {
00247 UTIL_THROW_IF2(x >= (1<<17), "Error");
00248 UTIL_THROW_IF2(y >= (1<<17), "Error");
00249
00250 m_seenPosition.insert((x<<16) + y);
00251 }
00252
00253
00254 bool
00255 BackwardsEdge::GetInitialized()
00256 {
00257 return m_initialized;
00258 }
00259
00260 const BitmapContainer&
00261 BackwardsEdge::GetBitmapContainer() const
00262 {
00263 return m_prevBitmapContainer;
00264 }
00265
00266 void
00267 BackwardsEdge::PushSuccessors(const size_t x, const size_t y)
00268 {
00269 Hypothesis *newHypo;
00270
00271 if(y + 1 < m_translations.size() && !SeenPosition(x, y + 1)) {
00272 SetSeenPosition(x, y + 1);
00273 newHypo = CreateHypothesis(*m_hypotheses[x], *m_translations.Get(y + 1));
00274 if(newHypo != NULL) {
00275 m_parent.Enqueue(x, y + 1, newHypo, (BackwardsEdge*)this);
00276 }
00277 }
00278
00279 if(x + 1 < m_hypotheses.size() && !SeenPosition(x + 1, y)) {
00280 SetSeenPosition(x + 1, y);
00281 newHypo = CreateHypothesis(*m_hypotheses[x + 1], *m_translations.Get(y));
00282 if(newHypo != NULL) {
00283 m_parent.Enqueue(x + 1, y, newHypo, (BackwardsEdge*)this);
00284 }
00285 }
00286 }
00287
00288
00290
00292
00293 BitmapContainer::BitmapContainer(const Bitmap &bitmap
00294 , HypothesisStackCubePruning &stack
00295 , bool deterministic)
00296 : m_bitmap(bitmap)
00297 , m_stack(stack)
00298 , m_numStackInsertions(0)
00299 , m_deterministic(deterministic)
00300 {
00301 m_hypotheses = HypothesisSet();
00302 m_edges = BackwardsEdgeSet();
00303 m_queue = HypothesisQueue();
00304 }
00305
00306 BitmapContainer::~BitmapContainer()
00307 {
00308
00309
00310 while (!m_queue.empty()) {
00311 HypothesisQueueItem *item = m_queue.top();
00312 m_queue.pop();
00313
00314 delete item->GetHypothesis();
00315 delete item;
00316 }
00317
00318
00319 RemoveAllInColl(m_edges);
00320
00321 m_hypotheses.clear();
00322 m_edges.clear();
00323 }
00324
00325
00326 void
00327 BitmapContainer::Enqueue(int hypothesis_pos
00328 , int translation_pos
00329 , Hypothesis *hypothesis
00330 , BackwardsEdge *edge)
00331 {
00332
00333 const TargetPhrase *target_phrase = m_deterministic ? &(hypothesis->GetCurrTargetPhrase()) : NULL;
00334 HypothesisQueueItem *item = new HypothesisQueueItem(hypothesis_pos
00335 , translation_pos
00336 , hypothesis
00337 , edge
00338 , target_phrase);
00339 IFVERBOSE(2) {
00340 item->GetHypothesis()->GetManager().GetSentenceStats().StartTimeManageCubes();
00341 }
00342 m_queue.push(item);
00343 IFVERBOSE(2) {
00344 item->GetHypothesis()->GetManager().GetSentenceStats().StopTimeManageCubes();
00345 }
00346 }
00347
00348 HypothesisQueueItem*
00349 BitmapContainer::Dequeue(bool keepValue)
00350 {
00351 if (!m_queue.empty()) {
00352 HypothesisQueueItem *item = m_queue.top();
00353
00354 if (!keepValue) {
00355 m_queue.pop();
00356 }
00357
00358 return item;
00359 }
00360
00361 return NULL;
00362 }
00363
00364 HypothesisQueueItem*
00365 BitmapContainer::Top() const
00366 {
00367 return m_queue.top();
00368 }
00369
00370 size_t
00371 BitmapContainer::Size()
00372 {
00373 return m_queue.size();
00374 }
00375
00376 bool
00377 BitmapContainer::Empty() const
00378 {
00379 return m_queue.empty();
00380 }
00381
00382 const HypothesisSet&
00383 BitmapContainer::GetHypotheses() const
00384 {
00385 return m_hypotheses;
00386 }
00387
00388 size_t
00389 BitmapContainer::GetHypothesesSize() const
00390 {
00391 return m_hypotheses.size();
00392 }
00393
00394 const BackwardsEdgeSet&
00395 BitmapContainer::GetBackwardsEdges()
00396 {
00397 return m_edges;
00398 }
00399
00400 void
00401 BitmapContainer::AddHypothesis(Hypothesis *hypothesis)
00402 {
00403 bool itemExists = false;
00404 HypothesisSet::const_iterator iter = m_hypotheses.begin();
00405 HypothesisSet::const_iterator iterEnd = m_hypotheses.end();
00406
00407
00408 while (iter != iterEnd) {
00409 if (*iter == hypothesis) {
00410 itemExists = true;
00411 break;
00412 }
00413
00414 ++iter;
00415 }
00416 UTIL_THROW_IF2(itemExists, "Duplicate hypotheses");
00417 m_hypotheses.push_back(hypothesis);
00418 }
00419
00420 void
00421 BitmapContainer::AddBackwardsEdge(BackwardsEdge *edge)
00422 {
00423 m_edges.insert(edge);
00424 }
00425
00426 void
00427 BitmapContainer::InitializeEdges()
00428 {
00429 BackwardsEdgeSet::iterator iter = m_edges.begin();
00430 BackwardsEdgeSet::iterator iterEnd = m_edges.end();
00431
00432 while (iter != iterEnd) {
00433 BackwardsEdge *edge = *iter;
00434 edge->Initialize();
00435
00436 ++iter;
00437 }
00438 }
00439
00440 void
00441 BitmapContainer::EnsureMinStackHyps(const size_t minNumHyps)
00442 {
00443 while ((!Empty()) && m_numStackInsertions < minNumHyps) {
00444 ProcessBestHypothesis();
00445 }
00446 }
00447
00448 void
00449 BitmapContainer::ProcessBestHypothesis()
00450 {
00451 if (m_queue.empty()) {
00452 return;
00453 }
00454
00455
00456 HypothesisQueueItem *item = Dequeue();
00457
00458
00459 UTIL_THROW_IF2(item == NULL, "Null object");
00460
00461
00462 if (!Empty()) {
00463 HypothesisQueueItem *check = Dequeue(true);
00464 UTIL_THROW_IF2(item->GetHypothesis()->GetFutureScore() < check->GetHypothesis()->GetFutureScore(),
00465 "Non-monotonic total score: "
00466 << item->GetHypothesis()->GetFutureScore() << " vs. "
00467 << check->GetHypothesis()->GetFutureScore());
00468 }
00469
00470
00471 IFVERBOSE(3) {
00472 item->GetHypothesis()->PrintHypothesis();
00473 }
00474
00475
00476 const bool newstackentry = m_stack.AddPrune(item->GetHypothesis());
00477 if (newstackentry)
00478 m_numStackInsertions++;
00479
00480 IFVERBOSE(3) {
00481 TRACE_ERR("new stack entry flag is " << newstackentry << std::endl);
00482 }
00483
00484
00485 item->GetBackwardsEdge()->PushSuccessors(item->GetHypothesisPos(), item->GetTranslationPos());
00486
00487
00488 delete item;
00489 }
00490
00491 void
00492 BitmapContainer::SortHypotheses()
00493 {
00494 std::sort(m_hypotheses.begin(), m_hypotheses.end(), HypothesisScoreOrderer(m_deterministic));
00495 }
00496
00497 }
00498