1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
|
#include "KBestExtractor.h"
#include "moses/ScoreComponentCollection.h"
#include "moses/StaticData.h"
#include <boost/scoped_ptr.hpp>
#include <vector>
namespace Moses
{
namespace Syntax
{
// Extract the k-best list from the search graph.
void KBestExtractor::Extract(
const std::vector<boost::shared_ptr<SVertex> > &topLevelVertices,
std::size_t k, KBestVec &kBestList)
{
kBestList.clear();
if (topLevelVertices.empty()) {
return;
}
// Create a new SVertex, supremeVertex, that has the best top-level SVertex as
// its predecessor and has the same score.
std::vector<boost::shared_ptr<SVertex> >::const_iterator p =
topLevelVertices.begin();
SVertex &bestTopLevelVertex = **p;
boost::scoped_ptr<SVertex> supremeVertex(new SVertex());
supremeVertex->pvertex = 0;
supremeVertex->best = new SHyperedge();
supremeVertex->best->head = supremeVertex.get();
supremeVertex->best->tail.push_back(&bestTopLevelVertex);
supremeVertex->best->label.futureScore =
bestTopLevelVertex.best->label.futureScore;
supremeVertex->best->label.deltas = bestTopLevelVertex.best->label.deltas;
supremeVertex->best->label.translation = 0;
// For each alternative top-level SVertex, add a new incoming hyperedge to
// supremeVertex.
for (++p; p != topLevelVertices.end(); ++p) {
// Check that the first item in topLevelVertices really was the best.
UTIL_THROW_IF2((*p)->best->label.futureScore >
bestTopLevelVertex.best->label.futureScore,
"top-level SVertices are not correctly sorted");
// Note: there's no need for a smart pointer here: supremeVertex will take
// ownership of altEdge.
SHyperedge *altEdge = new SHyperedge();
altEdge->head = supremeVertex.get();
altEdge->tail.push_back((*p).get());
altEdge->label.futureScore = (*p)->best->label.futureScore;
altEdge->label.deltas = (*p)->best->label.deltas;
altEdge->label.translation = 0;
supremeVertex->recombined.push_back(altEdge);
}
// Create the target vertex then lazily fill its k-best list.
boost::shared_ptr<KVertex> targetVertex = FindOrCreateVertex(*supremeVertex);
LazyKthBest(targetVertex, k, k);
// Copy the k-best list from the target vertex, but drop the top edge from
// each derivation.
kBestList.reserve(targetVertex->kBestList.size());
for (std::vector<boost::weak_ptr<Derivation> >::const_iterator
q = targetVertex->kBestList.begin();
q != targetVertex->kBestList.end(); ++q) {
const boost::shared_ptr<Derivation> d(*q);
assert(d);
assert(d->subderivations.size() == 1);
kBestList.push_back(d->subderivations[0]);
}
}
// Generate the target-side yield of the derivation d.
Phrase KBestExtractor::GetOutputPhrase(const Derivation &d)
{
FactorType placeholderFactor = StaticData::Instance().options()->input.placeholder_factor;
Phrase ret(ARRAY_SIZE_INCR);
const TargetPhrase &phrase = *(d.edge->shyperedge.label.translation);
const AlignmentInfo::NonTermIndexMap &nonTermIndexMap =
phrase.GetAlignNonTerm().GetNonTermIndexMap();
for (std::size_t pos = 0; pos < phrase.GetSize(); ++pos) {
const Word &word = phrase.GetWord(pos);
if (word.IsNonTerminal()) {
std::size_t nonTermInd = nonTermIndexMap[pos];
const Derivation &subderivation = *d.subderivations[nonTermInd];
Phrase subPhrase = GetOutputPhrase(subderivation);
ret.Append(subPhrase);
} else {
ret.AddWord(word);
if (placeholderFactor == NOT_FOUND) {
continue;
}
// FIXME
UTIL_THROW2("placeholders are not currently supported by the S2T decoder");
/*
std::set<std::size_t> sourcePosSet =
phrase.GetAlignTerm().GetAlignmentsForTarget(pos);
if (sourcePosSet.size() == 1) {
const std::vector<const Word*> *ruleSourceFromInputPath =
hypo.GetTranslationOption().GetSourceRuleFromInputPath();
UTIL_THROW_IF2(ruleSourceFromInputPath == NULL,
"Source Words in of the rules hasn't been filled out");
std::size_t sourcePos = *sourcePosSet.begin();
const Word *sourceWord = ruleSourceFromInputPath->at(sourcePos);
UTIL_THROW_IF2(sourceWord == NULL,
"Null source word at position " << sourcePos);
const Factor *factor = sourceWord->GetFactor(placeholderFactor);
if (factor) {
ret.Back()[0] = factor;
}
}
*/
}
}
return ret;
}
// Generate the target tree of the derivation d.
TreePointer KBestExtractor::GetOutputTree(const Derivation &d)
{
const TargetPhrase &phrase = *(d.edge->shyperedge.label.translation);
if (const PhraseProperty *property = phrase.GetProperty("Tree")) {
const std::string *tree = property->GetValueString();
TreePointer mytree (boost::make_shared<InternalTree>(*tree));
//get subtrees (in target order)
std::vector<TreePointer> previous_trees;
for (size_t pos = 0; pos < phrase.GetSize(); ++pos) {
const Word &word = phrase.GetWord(pos);
if (word.IsNonTerminal()) {
size_t nonTermInd = phrase.GetAlignNonTerm().GetNonTermIndexMap()[pos];
const Derivation &subderivation = *d.subderivations[nonTermInd];
const TreePointer prev_tree = GetOutputTree(subderivation);
previous_trees.push_back(prev_tree);
}
}
mytree->Combine(previous_trees);
return mytree;
} else {
UTIL_THROW2("Error: TreeStructureFeature active, but no internal tree structure found");
}
}
// Look for the vertex corresponding to a given SVertex, creating
// a new one if necessary.
boost::shared_ptr<KBestExtractor::KVertex>
KBestExtractor::FindOrCreateVertex(const SVertex &v)
{
// KVertex nodes should not be created for terminal nodes.
assert(v.best);
VertexMap::value_type element(&v, boost::shared_ptr<KVertex>());
std::pair<VertexMap::iterator, bool> p = m_vertexMap.insert(element);
boost::shared_ptr<KVertex> &sp = p.first->second;
if (!p.second) {
return sp; // KVertex was already in m_vertexMap.
}
sp.reset(new KVertex(v));
// Create the 1-best derivation and add it to the vertex's kBestList.
boost::shared_ptr<KHyperedge> bestEdge(new KHyperedge(*(v.best)));
bestEdge->head = sp;
std::size_t kTailSize = 0;
for (std::size_t i = 0; i < v.best->tail.size(); ++i) {
const SVertex *pred = v.best->tail[i];
if (pred->best) {
++kTailSize;
}
}
bestEdge->tail.reserve(kTailSize);
for (std::size_t i = 0; i < v.best->tail.size(); ++i) {
const SVertex *pred = v.best->tail[i];
if (pred->best) {
bestEdge->tail.push_back(FindOrCreateVertex(*pred));
}
}
boost::shared_ptr<Derivation> bestDerivation(new Derivation(bestEdge));
#ifndef NDEBUG
std::pair<DerivationSet::iterator, bool> q =
#endif
m_derivations.insert(bestDerivation);
assert(q.second);
sp->kBestList.push_back(bestDerivation);
return sp;
}
// Create the 1-best derivation for each edge in BS(v) (except the best one)
// and add it to v's candidate queue.
void KBestExtractor::GetCandidates(boost::shared_ptr<KVertex> v, std::size_t k)
{
// Create 1-best derivations for all of v's incoming edges except the best.
// The 1-best derivation for that edge will already have been created.
for (std::size_t i = 0; i < v->svertex.recombined.size(); ++i) {
const SHyperedge ­peredge = *(v->svertex.recombined[i]);
boost::shared_ptr<KHyperedge> bestEdge(new KHyperedge(shyperedge));
bestEdge->head = v;
// Count the number of incoming vertices that are not terminals.
std::size_t kTailSize = 0;
for (std::size_t j = 0; j < shyperedge.tail.size(); ++j) {
const SVertex *pred = shyperedge.tail[j];
if (pred->best) {
++kTailSize;
}
}
bestEdge->tail.reserve(kTailSize);
for (std::size_t j = 0; j < shyperedge.tail.size(); ++j) {
const SVertex *pred = shyperedge.tail[j];
if (pred->best) {
bestEdge->tail.push_back(FindOrCreateVertex(*pred));
}
}
boost::shared_ptr<Derivation> derivation(new Derivation(bestEdge));
#ifndef NDEBUG
std::pair<DerivationSet::iterator, bool> q =
#endif
m_derivations.insert(derivation);
assert(q.second);
v->candidates.push(derivation);
}
}
// Lazily fill v's k-best list.
void KBestExtractor::LazyKthBest(boost::shared_ptr<KVertex> v, std::size_t k,
std::size_t globalK)
{
// If this is the first visit to vertex v then initialize the priority queue.
if (v->visited == false) {
// The 1-best derivation should already be in v's k-best list.
assert(v->kBestList.size() == 1);
// Initialize v's priority queue.
GetCandidates(v, globalK);
v->visited = true;
}
// Add derivations to the k-best list until it contains k or there are none
// left to add.
while (v->kBestList.size() < k) {
assert(!v->kBestList.empty());
// Update the priority queue by adding the successors of the last
// derivation (unless they've been seen before).
boost::shared_ptr<Derivation> d(v->kBestList.back());
LazyNext(*v, *d, globalK);
// Check if there are any derivations left in the queue.
if (v->candidates.empty()) {
break;
}
// Get the next best derivation and delete it from the queue.
boost::weak_ptr<Derivation> next = v->candidates.top();
v->candidates.pop();
// Add it to the k-best list.
v->kBestList.push_back(next);
}
}
// Create the neighbours of Derivation d and add them to v's candidate queue.
void KBestExtractor::LazyNext(KVertex &v, const Derivation &d,
std::size_t globalK)
{
for (std::size_t i = 0; i < d.edge->tail.size(); ++i) {
boost::shared_ptr<KVertex> pred = d.edge->tail[i];
// Ensure that pred's k-best list contains enough derivations.
std::size_t k = d.backPointers[i] + 2;
LazyKthBest(pred, k, globalK);
if (pred->kBestList.size() < k) {
// pred's derivations have been exhausted.
continue;
}
// Create the neighbour.
boost::shared_ptr<Derivation> next(new Derivation(d, i));
// Check if it has been created before.
std::pair<DerivationSet::iterator, bool> p = m_derivations.insert(next);
if (p.second) {
v.candidates.push(next); // Haven't previously seen it.
}
}
}
// Construct the 1-best Derivation that ends at edge e.
KBestExtractor::Derivation::Derivation(const boost::shared_ptr<KHyperedge> &e)
{
edge = e;
const TargetPhrase *translation = edge->shyperedge.label.translation;
// Every hyperedge should have an associated target phrase, except for
// incoming hyperedges of the 'supreme' vertex.
if (translation) {
scoreBreakdown = translation->GetScoreBreakdown();
}
const std::size_t arity = edge->tail.size();
backPointers.resize(arity, 0);
subderivations.reserve(arity);
for (std::size_t i = 0; i < arity; ++i) {
const KVertex &pred = *(edge->tail[i]);
assert(pred.kBestList.size() >= 1);
boost::shared_ptr<Derivation> sub(pred.kBestList[0]);
subderivations.push_back(sub);
scoreBreakdown.PlusEquals(sub->scoreBreakdown);
}
scoreBreakdown.PlusEquals(edge->shyperedge.label.deltas);
score = scoreBreakdown.GetWeightedScore();
}
// Construct a Derivation that neighbours an existing Derivation.
KBestExtractor::Derivation::Derivation(const Derivation &d, std::size_t i)
{
edge = d.edge;
backPointers = d.backPointers;
subderivations = d.subderivations;
std::size_t j = ++backPointers[i];
scoreBreakdown = d.scoreBreakdown;
// Deduct the score of the old subderivation.
scoreBreakdown.MinusEquals(subderivations[i]->scoreBreakdown);
// Update the subderivation pointer.
boost::shared_ptr<Derivation> newSub(edge->tail[i]->kBestList[j]);
subderivations[i] = newSub;
// Add the score of the new subderivation.
scoreBreakdown.PlusEquals(subderivations[i]->scoreBreakdown);
score = scoreBreakdown.GetWeightedScore();
}
} // namespace Syntax
} // namespace Moses
|