summaryrefslogtreecommitdiff
path: root/klm/search/edge_generator.cc
blob: eacf5de5cdaebb30b4e4685284ced6c71b8156bd (plain)
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
#include "search/edge_generator.hh"

#include "lm/left.hh"
#include "lm/model.hh"
#include "lm/partial.hh"
#include "search/context.hh"
#include "search/vertex.hh"

#include <numeric>

namespace search {

namespace {

template <class Model> void FastScore(const Context<Model> &context, Arity victim, Arity before_idx, Arity incomplete, const PartialVertex &previous_vertex, PartialEdge update) {
  lm::ngram::ChartState *between = update.Between();
  lm::ngram::ChartState *before = &between[before_idx], *after = &between[before_idx + 1];

  float adjustment = 0.0;
  const lm::ngram::ChartState &previous_reveal = previous_vertex.State();
  const PartialVertex &update_nt = update.NT()[victim];
  const lm::ngram::ChartState &update_reveal = update_nt.State();
  if ((update_reveal.left.length > previous_reveal.left.length) || (update_reveal.left.full && !previous_reveal.left.full)) {
    adjustment += lm::ngram::RevealAfter(context.LanguageModel(), before->left, before->right, update_reveal.left, previous_reveal.left.length);
  }
  if ((update_reveal.right.length > previous_reveal.right.length) || (update_nt.RightFull() && !previous_vertex.RightFull())) {
    adjustment += lm::ngram::RevealBefore(context.LanguageModel(), update_reveal.right, previous_reveal.right.length, update_nt.RightFull(), after->left, after->right);
  }
  if (update_nt.Complete()) {
    if (update_reveal.left.full) {
      before->left.full = true;
    } else {
      assert(update_reveal.left.length == update_reveal.right.length);
      adjustment += lm::ngram::Subsume(context.LanguageModel(), before->left, before->right, after->left, after->right, update_reveal.left.length);
    }
    before->right = after->right;
    // Shift the others shifted one down, covering after.  
    for (lm::ngram::ChartState *cover = after; cover < between + incomplete; ++cover) {
      *cover = *(cover + 1);
    }
  }
  update.SetScore(update.GetScore() + adjustment * context.LMWeight());
}

} // namespace

template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context) {
  assert(!generate_.empty());
  PartialEdge top = generate_.top();
  generate_.pop();
  PartialVertex *const top_nt = top.NT();
  const Arity arity = top.GetArity();

  Arity victim = 0;
  Arity victim_completed;
  Arity incomplete;
  // Select victim or return if complete.   
  {
    Arity completed = 0;
    unsigned char lowest_length = 255;
    for (Arity i = 0; i != arity; ++i) {
      if (top_nt[i].Complete()) {
        ++completed;
      } else if (top_nt[i].Length() < lowest_length) {
        lowest_length = top_nt[i].Length();
        victim = i;
        victim_completed = completed;
      }
    }
    if (lowest_length == 255) {
      return top;
    }
    incomplete = arity - completed;
  }

  PartialVertex old_value(top_nt[victim]);
  PartialVertex alternate_changed;
  if (top_nt[victim].Split(alternate_changed)) {
    PartialEdge alternate(partial_edge_pool_, arity, incomplete + 1);
    alternate.SetScore(top.GetScore() + alternate_changed.Bound() - old_value.Bound());

    alternate.SetNote(top.GetNote());

    PartialVertex *alternate_nt = alternate.NT();
    for (Arity i = 0; i < victim; ++i) alternate_nt[i] = top_nt[i];
    alternate_nt[victim] = alternate_changed;
    for (Arity i = victim + 1; i < arity; ++i) alternate_nt[i] = top_nt[i];

    memcpy(alternate.Between(), top.Between(), sizeof(lm::ngram::ChartState) * (incomplete + 1));

    // TODO: dedupe?  
    generate_.push(alternate);
  }

  // top is now the continuation.
  FastScore(context, victim, victim - victim_completed, incomplete, old_value, top);
  // TODO: dedupe?  
  generate_.push(top);

  // Invalid indicates no new hypothesis generated.  
  return PartialEdge();
}

template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::RestProbingModel> &context);
template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ProbingModel> &context);
template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::TrieModel> &context);
template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantTrieModel> &context);
template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ArrayTrieModel> &context);
template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantArrayTrieModel> &context);

} // namespace search