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
|
#ifndef SEARCH_VERTEX_GENERATOR__
#define SEARCH_VERTEX_GENERATOR__
#include "search/edge.hh"
#include "search/types.hh"
#include "search/vertex.hh"
#include "util/exception.hh"
#include <boost/unordered_map.hpp>
#include <boost/version.hpp>
namespace lm {
namespace ngram {
class ChartState;
} // namespace ngram
} // namespace lm
namespace search {
class ContextBase;
#if BOOST_VERSION > 104200
// Parallel structure to VertexNode.
struct Trie {
Trie() : under(NULL) {}
VertexNode *under;
boost::unordered_map<uint64_t, Trie> extend;
};
void AddHypothesis(ContextBase &context, Trie &root, const NBestComplete &end);
#endif // BOOST_VERSION
// Output makes the single-best or n-best list.
template <class Output> class VertexGenerator {
public:
VertexGenerator(ContextBase &context, Vertex &gen, Output &nbest) : context_(context), gen_(gen), nbest_(nbest) {
gen.root_.InitRoot();
}
void NewHypothesis(PartialEdge partial) {
nbest_.Add(existing_[hash_value(partial.CompletedState())], partial);
}
void FinishedSearch() {
#if BOOST_VERSION > 104200
Trie root;
root.under = &gen_.root_;
for (typename Existing::iterator i(existing_.begin()); i != existing_.end(); ++i) {
AddHypothesis(context_, root, nbest_.Complete(i->second));
}
existing_.clear();
root.under->SortAndSet(context_);
#else
UTIL_THROW(util::Exception, "Upgrade Boost to >= 1.42.0 to use incremental search.");
#endif
}
const Vertex &Generating() const { return gen_; }
private:
ContextBase &context_;
Vertex &gen_;
typedef boost::unordered_map<uint64_t, typename Output::Combine> Existing;
Existing existing_;
Output &nbest_;
};
// Special case for root vertex: everything should come together into the root
// node. In theory, this should happen naturally due to state collapsing with
// <s> and </s>. If that's the case, VertexGenerator is fine, though it will
// make one connection.
template <class Output> class RootVertexGenerator {
public:
RootVertexGenerator(Vertex &gen, Output &out) : gen_(gen), out_(out) {}
void NewHypothesis(PartialEdge partial) {
out_.Add(combine_, partial);
}
void FinishedSearch() {
gen_.root_.InitRoot();
NBestComplete completed(out_.Complete(combine_));
gen_.root_.SetEnd(completed.history, completed.score);
}
private:
Vertex &gen_;
typename Output::Combine combine_;
Output &out_;
};
} // namespace search
#endif // SEARCH_VERTEX_GENERATOR__
|
