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
|
#include "ff_klm.h"
#include <cstring>
#include "hg.h"
#include "tdict.h"
#include "lm/model.hh"
#include "lm/enumerate_vocab.hh"
using namespace std;
string KLanguageModel::usage(bool param,bool verbose) {
return "KLanguageModel";
}
struct VMapper : public lm::ngram::EnumerateVocab {
VMapper(vector<lm::WordIndex>* out) : out_(out), kLM_UNKNOWN_TOKEN(0) { out_->clear(); }
void Add(lm::WordIndex index, const StringPiece &str) {
const WordID cdec_id = TD::Convert(str.as_string());
if (cdec_id >= out_->size())
out_->resize(cdec_id + 1, kLM_UNKNOWN_TOKEN);
(*out_)[cdec_id] = index;
}
vector<lm::WordIndex>* out_;
const lm::WordIndex kLM_UNKNOWN_TOKEN;
};
class KLanguageModelImpl {
// returns the number of unscored words at the left edge of a span
inline int UnscoredSize(const void* state) const {
return *(static_cast<const char*>(state) + unscored_size_offset_);
}
inline void SetUnscoredSize(int size, void* state) const {
*(static_cast<char*>(state) + unscored_size_offset_) = size;
}
static inline const lm::ngram::Model::State& RemnantLMState(const void* state) {
return *static_cast<const lm::ngram::Model::State*>(state);
}
inline void SetRemnantLMState(const lm::ngram::Model::State& lmstate, void* state) const {
// if we were clever, we could use the memory pointed to by state to do all
// the work, avoiding this copy
memcpy(state, &lmstate, ngram_->StateSize());
}
lm::WordIndex IthUnscoredWord(int i, const void* state) const {
const lm::WordIndex* const mem = reinterpret_cast<const lm::WordIndex*>(static_cast<const char*>(state) + unscored_words_offset_);
return mem[i];
}
void SetIthUnscoredWord(int i, lm::WordIndex index, void *state) const {
lm::WordIndex* mem = reinterpret_cast<lm::WordIndex*>(static_cast<char*>(state) + unscored_words_offset_);
mem[i] = index;
}
bool HasFullContext(const void *state) const {
return *(static_cast<const char*>(state) + is_complete_offset_);
}
void SetHasFullContext(bool flag, void *state) const {
*(static_cast<char*>(state) + is_complete_offset_) = flag;
}
public:
double LookupWords(const TRule& rule, const vector<const void*>& ant_states, double* pest_sum, void* remnant) {
double sum = 0.0;
double est_sum = 0.0;
int len = rule.ELength() - rule.Arity();
int num_scored = 0;
int num_estimated = 0;
lm::ngram::Model::State state = ngram_->NullContextState();
const vector<WordID>& e = rule.e();
bool context_complete = false;
for (int j = 0; j < e.size(); ++j) {
if (e[j] < 1) {
const void* astate = (ant_states[-e[j]]);
int unscored_ant_len = UnscoredSize(astate);
for (int k = 0; k < unscored_ant_len; ++k) {
const lm::WordIndex cur_word = IthUnscoredWord(k, astate);
const lm::ngram::Model::State scopy(state);
const double p = ngram_->Score(scopy, cur_word, state);
++num_scored;
if (!context_complete) {
if (num_scored >= order_) context_complete = true;
}
if (context_complete) {
sum += p;
} else {
if (remnant)
SetIthUnscoredWord(num_estimated, cur_word, remnant);
++num_estimated;
est_sum += p;
}
}
if (HasFullContext(astate)) { // this is equivalent to the "star" in Chiang 2007
state = RemnantLMState(astate);
context_complete = true;
}
} else {
const lm::WordIndex cur_word = MapWord(e[j]);
const lm::ngram::Model::State scopy(state);
const double p = ngram_->Score(scopy, cur_word, state);
++num_scored;
if (!context_complete) {
if (num_scored >= order_) context_complete = true;
}
if (context_complete) {
sum += p;
} else {
if (remnant)
SetIthUnscoredWord(num_estimated, cur_word, remnant);
++num_estimated;
est_sum += p;
}
}
}
if (pest_sum) *pest_sum = est_sum;
if (remnant) {
state.ZeroRemaining();
SetRemnantLMState(state, remnant);
SetUnscoredSize(num_estimated, remnant);
SetHasFullContext(context_complete || (num_scored >= order_), remnant);
}
return sum;
}
//FIXME: this assumes no target words on final unary -> goal rule. is that ok?
// for <s> (n-1 left words) and (n-1 right words) </s>
double FinalTraversalCost(const void* state) {
SetRemnantLMState(ngram_->BeginSentenceState(), dummy_state_);
SetHasFullContext(1, dummy_state_);
SetUnscoredSize(0, dummy_state_);
dummy_ants_[1] = state;
return LookupWords(*dummy_rule_, dummy_ants_, NULL, NULL);
}
lm::WordIndex MapWord(WordID w) const {
if (w >= map_.size())
return 0;
else
return map_[w];
}
public:
KLanguageModelImpl(const std::string& param) {
lm::ngram::Config conf;
VMapper vm(&map_);
conf.enumerate_vocab = &vm;
ngram_ = new lm::ngram::Model(param.c_str(), conf);
order_ = ngram_->Order();
cerr << "Loaded " << order_ << "-gram KLM from " << param << " (MapSize=" << map_.size() << ")\n";
state_size_ = ngram_->StateSize() + 2 + (order_ - 1) * sizeof(lm::WordIndex);
unscored_size_offset_ = ngram_->StateSize();
is_complete_offset_ = unscored_size_offset_ + 1;
unscored_words_offset_ = is_complete_offset_ + 1;
// special handling of beginning / ending sentence markers
dummy_state_ = new char[state_size_];
dummy_ants_.push_back(dummy_state_);
dummy_ants_.push_back(NULL);
dummy_rule_.reset(new TRule("[DUMMY] ||| [BOS] [DUMMY] ||| [1] [2] </s> ||| X=0"));
}
~KLanguageModelImpl() {
delete ngram_;
delete[] dummy_state_;
}
int ReserveStateSize() const { return state_size_; }
private:
lm::ngram::Model* ngram_;
int order_;
int state_size_;
int unscored_size_offset_;
int is_complete_offset_;
int unscored_words_offset_;
char* dummy_state_;
vector<const void*> dummy_ants_;
vector<lm::WordIndex> map_;
TRulePtr dummy_rule_;
};
KLanguageModel::KLanguageModel(const string& param) {
pimpl_ = new KLanguageModelImpl(param);
fid_ = FD::Convert("LanguageModel");
SetStateSize(pimpl_->ReserveStateSize());
}
Features KLanguageModel::features() const {
return single_feature(fid_);
}
KLanguageModel::~KLanguageModel() {
delete pimpl_;
}
void KLanguageModel::TraversalFeaturesImpl(const SentenceMetadata& /* smeta */,
const Hypergraph::Edge& edge,
const vector<const void*>& ant_states,
SparseVector<double>* features,
SparseVector<double>* estimated_features,
void* state) const {
double est = 0;
features->set_value(fid_, pimpl_->LookupWords(*edge.rule_, ant_states, &est, state));
estimated_features->set_value(fid_, est);
}
void KLanguageModel::FinalTraversalFeatures(const void* ant_state,
SparseVector<double>* features) const {
features->set_value(fid_, pimpl_->FinalTraversalCost(ant_state));
}
|
