File size: 7,192 Bytes
e3a3acf
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
// Exact re-implementation of flashlight-text 0.0.7 LexiconFreeDecoder (CTC, no silence token, no ASG) that returns the
// same best hypothesis with less work. Three changes, none of which alters which candidates survive:
//  1. Hypotheses of the previous frame are visited best first, so the running best score (and with it the beam threshold) rises early.
//  2. For each hypothesis the tokens are visited in descending emission order (as before). A candidate can score at most
//     prev + emission + lm_weight * lm_upper (lm_upper = the largest score the LM can return, i.e. the token bonus for KenLM log10 <= 0).
//     If that bound is below best - threshold, candidatesAdd would drop this and every later (lower-emission) token of the hypothesis,
//     so the loop stops without querying the LM.
//  3. Only the best final hypothesis is built and returned (flashlight returns all of them as Python lists).
// Ties in score are the only case where order could matter; flashlight already orders candidates by LM-state address there.
#include <pybind11/pybind11.h>
#include <pybind11/stl.h>
#include <algorithm>
#include <cmath>
#include <limits>
#include <numeric>
#include <vector>
#include "flashlight/lib/text/decoder/lm/LM.h"

namespace py = pybind11;
using fl::lib::text::LMPtr;
using fl::lib::text::LMStatePtr;

namespace fastdec {

struct State {
  double score; LMStatePtr lmState; const State* parent; int token; bool prevBlank; double amScore, lmScore;
  State(double s, const LMStatePtr& l, const State* p, int t, bool b, double am, double lm)
      : score(s), lmState(l), parent(p), token(t), prevBlank(b), amScore(am), lmScore(lm) {}
  int compareNoScoreStates(const State* o) const {   // same order as LexiconFreeDecoderState
    int c = lmState->compare(o->lmState);
    if (c != 0) return c > 0 ? 1 : -1;
    if (token != o->token) return token > o->token ? 1 : -1;
    if (prevBlank != o->prevBlank) return prevBlank > o->prevBlank ? 1 : -1;
    return 0;
  }
};

class FastCTCDecoder {
 public:
  FastCTCDecoder(int beam, int beamToken, double threshold, double lmWeight, LMPtr lm, int blank, double lmUpper, bool logAdd)
      : beam_(beam), beamToken_(beamToken), thr_(threshold), lmw_(lmWeight), lm_(std::move(lm)), blank_(blank), lmUpper_(lmUpper), logAdd_(logAdd) {}

  std::vector<int> decode(uintptr_t ptr, int T, int N) {
    const float* em = reinterpret_cast<const float*>(ptr);
    hyp_.assign(T + 2, {});
    hyp_[0].emplace_back(0.0, lm_->start(false), nullptr, -1, false, 0.0, 0.0);
    const int K = std::min(beamToken_, N);
    std::vector<int> idx(N);
    const double lmBonusMax = std::max(0.0, lmw_ * lmUpper_);
    for (int t = 0; t < T; t++) {
      const float* e = em + (size_t)t * N;
      std::iota(idx.begin(), idx.end(), 0);
      if (N > beamToken_) std::partial_sort(idx.begin(), idx.begin() + beamToken_, idx.end(), [e](int l, int r) { return e[l] > e[r]; });
      reset();
      order_.clear();
      for (auto& h : hyp_[t]) order_.push_back(&h);
      std::sort(order_.begin(), order_.end(), [](const State* a, const State* b) { return a->score > b->score; });
      for (const State* prev : order_) {
        for (int r = 0; r < K; ++r) {
          const int n = idx[r];
          const double am = e[n];
          const double score = prev->score + am;
          if (score + lmBonusMax < best_ - thr_) break;   // this and all lower-emission tokens would be dropped
          if (n != blank_ && (n != prev->token || prev->prevBlank)) {
            auto ls = lm_->score(prev->lmState, n);
            add(score + lmw_ * ls.second, ls.first, prev, n, false, prev->amScore + am, prev->lmScore + ls.second);
            if (ls.second > maxLm_) maxLm_ = ls.second;
          } else if (n == blank_) {
            add(score, prev->lmState, prev, n, true, prev->amScore + am, prev->lmScore);
          } else {
            add(score, prev->lmState, prev, n, false, prev->amScore + am, prev->lmScore);
          }
        }
      }
      store(hyp_[t + 1], false);
    }
    reset();   // decodeEnd: LM finish, sil_ = -1 token
    for (auto& prev : hyp_[T]) {
      auto ls = lm_->finish(prev.lmState);
      add(prev.score + lmw_ * ls.second, ls.first, &prev, -1, false, prev.amScore, prev.lmScore + ls.second);
    }
    store(hyp_[T + 1], true);
    std::vector<int> tokens;
    if (hyp_[T + 1].empty()) return tokens;
    std::vector<int> rev;
    for (const State* s = &hyp_[T + 1][0]; s; s = s->parent) rev.push_back(s->token);
    tokens.assign(rev.rbegin(), rev.rend());   // frame-aligned like DecodeResult.tokens (index 0 = start state)
    return tokens;
  }
  double maxLm_ = -std::numeric_limits<double>::infinity();

 private:
  void reset() { best_ = -std::numeric_limits<double>::infinity(); cand_.clear(); ptrs_.clear(); }
  void add(double score, const LMStatePtr& l, const State* p, int t, bool b, double am, double lm) {
    if (score >= best_) best_ = score;
    if (score >= best_ - thr_) cand_.emplace_back(score, l, p, t, b, am, lm);
  }
  void store(std::vector<State>& out, bool sorted) {   // candidatesStore
    out.clear();
    if (cand_.empty()) return;
    const double threshold = best_ - thr_;
    for (auto& c : cand_) if (c.score >= threshold) ptrs_.push_back(&c);
    std::sort(ptrs_.begin(), ptrs_.end(), [](const State* a, const State* b) {
      int c = a->compareNoScoreStates(b); return c == 0 ? a->score > b->score : c > 0; });
    int m = 1;
    for (size_t i = 1; i < ptrs_.size(); i++) {
      if (ptrs_[i]->compareNoScoreStates(ptrs_[m - 1]) != 0) ptrs_[m++] = ptrs_[i];
      else {
        double mx = std::max(ptrs_[m - 1]->score, ptrs_[i]->score);
        if (logAdd_) { double mn = std::min(ptrs_[m - 1]->score, ptrs_[i]->score); ptrs_[m - 1]->score = mx + std::log1p(std::exp(mn - mx)); }
        else ptrs_[m - 1]->score = mx;
      }
    }
    ptrs_.resize(m);
    auto byScore = [](const State* a, const State* b) { return a->score > b->score; };
    int nValid = ptrs_.size(), fin = std::min(nValid, beam_);
    if (!sorted && nValid > beam_) std::nth_element(ptrs_.begin(), ptrs_.begin() + fin, ptrs_.begin() + nValid, byScore);
    else if (sorted) std::partial_sort(ptrs_.begin(), ptrs_.begin() + fin, ptrs_.begin() + nValid, byScore);
    out.reserve(fin);
    for (int i = 0; i < fin; i++) out.emplace_back(std::move(*ptrs_[i]));
  }
  int beam_, beamToken_; double thr_, lmw_; LMPtr lm_; int blank_; double lmUpper_; bool logAdd_;
  std::vector<std::vector<State>> hyp_;
  std::vector<State> cand_; std::vector<State*> ptrs_; std::vector<const State*> order_;
  double best_ = 0;
};

}  // namespace fastdec

PYBIND11_MODULE(ctc_fast_decoder, m) {
  py::module_::import("flashlight.lib.text.decoder");
  py::class_<fastdec::FastCTCDecoder>(m, "FastCTCDecoder")
      .def(py::init<int, int, double, double, LMPtr, int, double, bool>(), py::arg("beam"), py::arg("beam_token"), py::arg("threshold"),
           py::arg("lm_weight"), py::arg("lm"), py::arg("blank"), py::arg("lm_upper"), py::arg("log_add") = true)
      .def("decode", &fastdec::FastCTCDecoder::decode, py::call_guard<py::gil_scoped_release>())
      .def_readonly("max_lm", &fastdec::FastCTCDecoder::maxLm_);
}