00001 #include "search/edge_generator.hh"
00002
00003 #include "lm/left.hh"
00004 #include "lm/model.hh"
00005 #include "lm/partial.hh"
00006 #include "search/context.hh"
00007 #include "search/vertex.hh"
00008
00009 #include <numeric>
00010
00011 namespace search {
00012
00013 namespace {
00014
00015 template <class Model> void FastScore(const Context<Model> &context, Arity victim, Arity before_idx, Arity incomplete, const PartialVertex &previous_vertex, PartialEdge update) {
00016 lm::ngram::ChartState *between = update.Between();
00017 lm::ngram::ChartState *before = &between[before_idx], *after = &between[before_idx + 1];
00018
00019 float adjustment = 0.0;
00020 const lm::ngram::ChartState &previous_reveal = previous_vertex.State();
00021 const PartialVertex &update_nt = update.NT()[victim];
00022 const lm::ngram::ChartState &update_reveal = update_nt.State();
00023 if ((update_reveal.left.length > previous_reveal.left.length) || (update_reveal.left.full && !previous_reveal.left.full)) {
00024 adjustment += lm::ngram::RevealAfter(context.LanguageModel(), before->left, before->right, update_reveal.left, previous_reveal.left.length);
00025 }
00026 if ((update_reveal.right.length > previous_reveal.right.length) || (update_nt.RightFull() && !previous_vertex.RightFull())) {
00027 adjustment += lm::ngram::RevealBefore(context.LanguageModel(), update_reveal.right, previous_reveal.right.length, update_nt.RightFull(), after->left, after->right);
00028 }
00029 if (update_nt.Complete()) {
00030 if (update_reveal.left.full) {
00031 before->left.full = true;
00032 } else {
00033 assert(update_reveal.left.length == update_reveal.right.length);
00034 adjustment += lm::ngram::Subsume(context.LanguageModel(), before->left, before->right, after->left, after->right, update_reveal.left.length);
00035 }
00036 before->right = after->right;
00037
00038 for (lm::ngram::ChartState *cover = after; cover < between + incomplete; ++cover) {
00039 *cover = *(cover + 1);
00040 }
00041 }
00042 update.SetScore(update.GetScore() + adjustment * context.LMWeight());
00043 }
00044
00045 }
00046
00047 template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context) {
00048 assert(!generate_.empty());
00049 PartialEdge top = generate_.top();
00050 generate_.pop();
00051 PartialVertex *const top_nt = top.NT();
00052 const Arity arity = top.GetArity();
00053
00054 Arity victim = 0;
00055 Arity victim_completed;
00056 Arity incomplete;
00057 unsigned char lowest_niceness = 255;
00058
00059 {
00060 Arity completed = 0;
00061 for (Arity i = 0; i != arity; ++i) {
00062 if (top_nt[i].Complete()) {
00063 ++completed;
00064 } else if (top_nt[i].Niceness() < lowest_niceness) {
00065 lowest_niceness = top_nt[i].Niceness();
00066 victim = i;
00067 victim_completed = completed;
00068 }
00069 }
00070 if (lowest_niceness == 255) {
00071 return top;
00072 }
00073 incomplete = arity - completed;
00074 }
00075
00076 PartialVertex old_value(top_nt[victim]);
00077 PartialVertex alternate_changed;
00078 if (top_nt[victim].Split(alternate_changed)) {
00079 PartialEdge alternate(partial_edge_pool_, arity, incomplete + 1);
00080 alternate.SetScore(top.GetScore() + alternate_changed.Bound() - old_value.Bound());
00081
00082 alternate.SetNote(top.GetNote());
00083 alternate.SetRange(top.GetRange());
00084
00085 PartialVertex *alternate_nt = alternate.NT();
00086 for (Arity i = 0; i < victim; ++i) alternate_nt[i] = top_nt[i];
00087 alternate_nt[victim] = alternate_changed;
00088 for (Arity i = victim + 1; i < arity; ++i) alternate_nt[i] = top_nt[i];
00089
00090 memcpy(alternate.Between(), top.Between(), sizeof(lm::ngram::ChartState) * (incomplete + 1));
00091
00092
00093 generate_.push(alternate);
00094 }
00095
00096 #ifndef NDEBUG
00097 Score before = top.GetScore();
00098 #endif
00099
00100 FastScore(context, victim, victim - victim_completed, incomplete, old_value, top);
00101
00102 generate_.push(top);
00103 assert(lowest_niceness != 254 || top.GetScore() == before);
00104
00105
00106 return PartialEdge();
00107 }
00108
00109 template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::RestProbingModel> &context);
00110 template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ProbingModel> &context);
00111 template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::TrieModel> &context);
00112 template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantTrieModel> &context);
00113 template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ArrayTrieModel> &context);
00114 template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantArrayTrieModel> &context);
00115
00116 }