00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include "ChartKBestExtractor.h"
00021
00022 #include "ChartHypothesis.h"
00023 #include "ScoreComponentCollection.h"
00024 #include "StaticData.h"
00025
00026 #include <boost/scoped_ptr.hpp>
00027
00028 #include <vector>
00029
00030 using namespace std;
00031
00032 namespace Moses
00033 {
00034
00035
00036 void ChartKBestExtractor::Extract(
00037 const std::vector<const ChartHypothesis*> &topLevelHypos, std::size_t k,
00038 KBestVec &kBestList)
00039 {
00040 kBestList.clear();
00041 if (topLevelHypos.empty()) {
00042 return;
00043 }
00044
00045
00046
00047 std::vector<const ChartHypothesis*>::const_iterator p = topLevelHypos.begin();
00048 const ChartHypothesis &bestTopLevelHypo = **p;
00049 boost::scoped_ptr<ChartHypothesis> supremeHypo(
00050 new ChartHypothesis(bestTopLevelHypo, *this));
00051
00052
00053
00054
00055 for (++p; p != topLevelHypos.end(); ++p) {
00056
00057 UTIL_THROW_IF2((*p)->GetFutureScore() > bestTopLevelHypo.GetFutureScore(),
00058 "top-level hypotheses are not correctly sorted");
00059
00060
00061 ChartHypothesis *altHypo = new ChartHypothesis(**p, *this);
00062 supremeHypo->AddArc(altHypo);
00063 }
00064
00065
00066 boost::shared_ptr<Vertex> targetVertex = FindOrCreateVertex(*supremeHypo);
00067 LazyKthBest(*targetVertex, k, k);
00068
00069
00070
00071 kBestList.reserve(targetVertex->kBestList.size());
00072 for (std::vector<boost::weak_ptr<Derivation> >::const_iterator
00073 q = targetVertex->kBestList.begin();
00074 q != targetVertex->kBestList.end(); ++q) {
00075 const boost::shared_ptr<Derivation> d(*q);
00076 assert(d);
00077 assert(d->subderivations.size() == 1);
00078 kBestList.push_back(d->subderivations[0]);
00079 }
00080 }
00081
00082
00083 Phrase ChartKBestExtractor::GetOutputPhrase(const Derivation &d)
00084 {
00085 FactorType placeholderFactor = StaticData::Instance().options()->input.placeholder_factor;
00086
00087 Phrase ret(ARRAY_SIZE_INCR);
00088
00089 const ChartHypothesis &hypo = d.edge.head->hypothesis;
00090 const TargetPhrase &phrase = hypo.GetCurrTargetPhrase();
00091 const AlignmentInfo::NonTermIndexMap &nonTermIndexMap =
00092 phrase.GetAlignNonTerm().GetNonTermIndexMap();
00093 for (std::size_t pos = 0; pos < phrase.GetSize(); ++pos) {
00094 const Word &word = phrase.GetWord(pos);
00095 if (word.IsNonTerminal()) {
00096 std::size_t nonTermInd = nonTermIndexMap[pos];
00097 const Derivation &subderivation = *d.subderivations[nonTermInd];
00098 Phrase subPhrase = GetOutputPhrase(subderivation);
00099 ret.Append(subPhrase);
00100 } else {
00101 ret.AddWord(word);
00102 if (placeholderFactor == NOT_FOUND) {
00103 continue;
00104 }
00105 std::set<std::size_t> sourcePosSet =
00106 phrase.GetAlignTerm().GetAlignmentsForTarget(pos);
00107 if (sourcePosSet.size() == 1) {
00108 const std::vector<const Word*> *ruleSourceFromInputPath =
00109 hypo.GetTranslationOption().GetSourceRuleFromInputPath();
00110 UTIL_THROW_IF2(ruleSourceFromInputPath == NULL,
00111 "Source Words in of the rules hasn't been filled out");
00112 std::size_t sourcePos = *sourcePosSet.begin();
00113 const Word *sourceWord = ruleSourceFromInputPath->at(sourcePos);
00114 UTIL_THROW_IF2(sourceWord == NULL,
00115 "Null source word at position " << sourcePos);
00116 const Factor *factor = sourceWord->GetFactor(placeholderFactor);
00117 if (factor) {
00118 ret.Back()[0] = factor;
00119 }
00120 }
00121 }
00122 }
00123
00124 return ret;
00125 }
00126
00127
00128 boost::shared_ptr<ScoreComponentCollection>
00129 ChartKBestExtractor::GetOutputScoreBreakdown(const Derivation &d)
00130 {
00131 const ChartHypothesis &hypo = d.edge.head->hypothesis;
00132 boost::shared_ptr<ScoreComponentCollection> scoreBreakdown(new ScoreComponentCollection());
00133 scoreBreakdown->PlusEquals(hypo.GetDeltaScoreBreakdown());
00134 const TargetPhrase &phrase = hypo.GetCurrTargetPhrase();
00135 const AlignmentInfo::NonTermIndexMap &nonTermIndexMap =
00136 phrase.GetAlignNonTerm().GetNonTermIndexMap();
00137 for (std::size_t pos = 0; pos < phrase.GetSize(); ++pos) {
00138 const Word &word = phrase.GetWord(pos);
00139 if (word.IsNonTerminal()) {
00140 std::size_t nonTermInd = nonTermIndexMap[pos];
00141 const Derivation &subderivation = *d.subderivations[nonTermInd];
00142 scoreBreakdown->PlusEquals(*GetOutputScoreBreakdown(subderivation));
00143 }
00144 }
00145
00146 return scoreBreakdown;
00147 }
00148
00149
00150 TreePointer ChartKBestExtractor::GetOutputTree(const Derivation &d)
00151 {
00152 const ChartHypothesis &hypo = d.edge.head->hypothesis;
00153 const TargetPhrase &phrase = hypo.GetCurrTargetPhrase();
00154 if (const PhraseProperty *property = phrase.GetProperty("Tree")) {
00155 const std::string *tree = property->GetValueString();
00156 TreePointer mytree (boost::make_shared<InternalTree>(*tree));
00157
00158
00159 std::vector<TreePointer> previous_trees;
00160 for (size_t pos = 0; pos < phrase.GetSize(); ++pos) {
00161 const Word &word = phrase.GetWord(pos);
00162 if (word.IsNonTerminal()) {
00163 size_t nonTermInd = phrase.GetAlignNonTerm().GetNonTermIndexMap()[pos];
00164 const Derivation &subderivation = *d.subderivations[nonTermInd];
00165 const TreePointer prev_tree = GetOutputTree(subderivation);
00166 previous_trees.push_back(prev_tree);
00167 }
00168 }
00169
00170 mytree->Combine(previous_trees);
00171 mytree->Unbinarize();
00172 return mytree;
00173 } else {
00174 UTIL_THROW2("Error: k-best tree output active, but no internal tree structure found");
00175 }
00176 }
00177
00178
00179 ChartKBestExtractor::UnweightedHyperarc ChartKBestExtractor::CreateEdge(
00180 const ChartHypothesis &h)
00181 {
00182 UnweightedHyperarc edge;
00183 edge.head = FindOrCreateVertex(h);
00184 const std::vector<const ChartHypothesis*> &prevHypos = h.GetPrevHypos();
00185 edge.tail.resize(prevHypos.size());
00186 for (std::size_t i = 0; i < prevHypos.size(); ++i) {
00187 const ChartHypothesis *prevHypo = prevHypos[i];
00188 edge.tail[i] = FindOrCreateVertex(*prevHypo);
00189 }
00190 return edge;
00191 }
00192
00193
00194
00195 boost::shared_ptr<ChartKBestExtractor::Vertex>
00196 ChartKBestExtractor::FindOrCreateVertex(const ChartHypothesis &h)
00197 {
00198 VertexMap::value_type element(&h, boost::shared_ptr<Vertex>());
00199 std::pair<VertexMap::iterator, bool> p = m_vertexMap.insert(element);
00200 boost::shared_ptr<Vertex> &sp = p.first->second;
00201 if (!p.second) {
00202 return sp;
00203 }
00204 sp.reset(new Vertex(h));
00205
00206 UnweightedHyperarc bestEdge;
00207 bestEdge.head = sp;
00208 const std::vector<const ChartHypothesis*> &prevHypos = h.GetPrevHypos();
00209 bestEdge.tail.resize(prevHypos.size());
00210 for (std::size_t i = 0; i < prevHypos.size(); ++i) {
00211 const ChartHypothesis *prevHypo = prevHypos[i];
00212 bestEdge.tail[i] = FindOrCreateVertex(*prevHypo);
00213 }
00214 boost::shared_ptr<Derivation> bestDerivation(new Derivation(bestEdge));
00215 #ifndef NDEBUG
00216 std::pair<DerivationSet::iterator, bool> q =
00217 #endif
00218 m_derivations.insert(bestDerivation);
00219 assert(q.second);
00220 sp->kBestList.push_back(bestDerivation);
00221 return sp;
00222 }
00223
00224
00225
00226 void ChartKBestExtractor::GetCandidates(Vertex &v, std::size_t k)
00227 {
00228
00229
00230
00231
00232 const ChartArcList *arcList = v.hypothesis.GetArcList();
00233 if (arcList) {
00234 for (std::size_t i = 0; i < arcList->size(); ++i) {
00235 const ChartHypothesis &recombinedHypo = *(*arcList)[i];
00236 boost::shared_ptr<Vertex> w = FindOrCreateVertex(recombinedHypo);
00237 assert(w->kBestList.size() == 1);
00238 v.candidates.push(w->kBestList[0]);
00239 }
00240 }
00241 }
00242
00243
00244 void ChartKBestExtractor::LazyKthBest(Vertex &v, std::size_t k,
00245 std::size_t globalK)
00246 {
00247
00248 if (v.visited == false) {
00249
00250 assert(v.kBestList.size() == 1);
00251
00252 GetCandidates(v, globalK);
00253 v.visited = true;
00254 }
00255
00256
00257 while (v.kBestList.size() < k) {
00258 assert(!v.kBestList.empty());
00259
00260
00261 boost::shared_ptr<Derivation> d(v.kBestList.back());
00262 LazyNext(v, *d, globalK);
00263
00264 if (v.candidates.empty()) {
00265 break;
00266 }
00267
00268 boost::weak_ptr<Derivation> next = v.candidates.top();
00269 v.candidates.pop();
00270
00271 v.kBestList.push_back(next);
00272 }
00273 }
00274
00275
00276 void ChartKBestExtractor::LazyNext(Vertex &v, const Derivation &d,
00277 std::size_t globalK)
00278 {
00279 for (std::size_t i = 0; i < d.edge.tail.size(); ++i) {
00280 Vertex &pred = *d.edge.tail[i];
00281
00282 std::size_t k = d.backPointers[i] + 2;
00283 LazyKthBest(pred, k, globalK);
00284 if (pred.kBestList.size() < k) {
00285
00286 continue;
00287 }
00288
00289 boost::shared_ptr<Derivation> next(new Derivation(d, i));
00290
00291 std::pair<DerivationSet::iterator, bool> p = m_derivations.insert(next);
00292 if (p.second) {
00293 v.candidates.push(next);
00294 }
00295 }
00296 }
00297
00298
00299 ChartKBestExtractor::Derivation::Derivation(const UnweightedHyperarc &e)
00300 {
00301 edge = e;
00302 std::size_t arity = edge.tail.size();
00303 backPointers.resize(arity, 0);
00304 subderivations.reserve(arity);
00305 for (std::size_t i = 0; i < arity; ++i) {
00306 const Vertex &pred = *edge.tail[i];
00307 assert(pred.kBestList.size() >= 1);
00308 boost::shared_ptr<Derivation> sub(pred.kBestList[0]);
00309 subderivations.push_back(sub);
00310 }
00311 score = edge.head->hypothesis.GetFutureScore();
00312 }
00313
00314
00315 ChartKBestExtractor::Derivation::Derivation(const Derivation &d, std::size_t i)
00316 {
00317 edge.head = d.edge.head;
00318 edge.tail = d.edge.tail;
00319 backPointers = d.backPointers;
00320 subderivations = d.subderivations;
00321 std::size_t j = ++backPointers[i];
00322 score = d.score;
00323
00324 score -= subderivations[i]->score;
00325
00326 boost::shared_ptr<Derivation> newSub(edge.tail[i]->kBestList[j]);
00327 subderivations[i] = newSub;
00328
00329 score += subderivations[i]->score;
00330 }
00331
00332 }