Spaces:
Running on Zero
Running on Zero
File size: 8,608 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 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 | // Incremental version of ctc_fast_decoder.cpp (exact flashlight-text 0.0.7 LexiconFreeDecoder
// best path, CTC, no silence token) for streaming. Same search per frame (best-first previous hypotheses, early break on the emission
// bound, candidatesStore merge); the beam is kept between calls so every committed frame is searched once.
// step(frames) : extend the beam by T committed frames
// peek(frames) : best collapsed tokens if T more frames were appended, without committing them (provisional text for the lookahead)
// best() : collapsed tokens of the current best hypothesis (no LM end-of-sentence)
// finish() : LM end-of-sentence + best collapsed tokens (= FastCTCDecoder.decode on all frames of the segment); then reset()
// rebase() : keep only the best hypothesis (its LM state and CTC state) as the new start; returns its collapsed tokens and frees
// the history (long speech without pauses: bounded memory, the LM context carries over)
// Collapsed tokens = frame path with repeats merged and blank / start dropped (itertools.groupby on the frame path, blanks dropped).
#include <pybind11/pybind11.h>
#include <pybind11/stl.h>
#include <algorithm>
#include <cmath>
#include <deque>
#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 streamdec {
struct State {
double score; LMStatePtr lmState; const State* parent; int token; bool prevBlank;
State(double s, const LMStatePtr& l, const State* p, int t, bool b) : score(s), lmState(l), parent(p), token(t), prevBlank(b) {}
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 StreamCTCDecoder {
public:
StreamCTCDecoder(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) {
reset();
}
void reset() {
hyp_.clear(); hyp_.emplace_back();
hyp_[0].emplace_back(0.0, lm_->start(false), nullptr, -1, false);
}
void step(uintptr_t ptr, int T, int N) {
const float* em = reinterpret_cast<const float*>(ptr);
for (int t = 0; t < T; t++) frame(em + (size_t)t * N, N);
}
std::vector<int> peek(uintptr_t ptr, int T, int N) {
const float* em = reinterpret_cast<const float*>(ptr);
const size_t keep = hyp_.size();
for (int t = 0; t < T; t++) frame(em + (size_t)t * N, N);
std::vector<int> out = collapse(bestState());
while (hyp_.size() > keep) hyp_.pop_back();
return out;
}
std::vector<int> best() const { return collapse(bestState()); }
std::vector<int> finish() {
reset_cand();
for (auto& prev : hyp_.back()) {
auto ls = lm_->finish(prev.lmState);
add(prev.score + lmw_ * ls.second, ls.first, &prev, -1, false);
}
std::vector<State> fin; store(fin, true);
std::vector<int> out = fin.empty() ? std::vector<int>() : collapse(&fin[0]);
reset();
return out;
}
std::vector<int> rebase() {
const State* b = bestState();
std::vector<int> out = collapse(b);
State s(0.0, b->lmState, nullptr, b->token, b->prevBlank);
hyp_.clear(); hyp_.emplace_back(); hyp_[0].push_back(s); // carried CTC state: a repeat of its token stays merged
return out;
}
int frames() const { return (int)hyp_.size() - 1; }
private:
void frame(const float* e, int N) {
const int K = std::min(beamToken_, N);
idx_.resize(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]; });
const double lmBonusMax = std::max(0.0, lmw_ * lmUpper_);
reset_cand();
order_.clear();
for (auto& h : hyp_.back()) 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 score = prev->score + e[n];
if (score + lmBonusMax < best_ - thr_) break;
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);
} else if (n == blank_) {
add(score, prev->lmState, prev, n, true);
} else {
add(score, prev->lmState, prev, n, false);
}
}
}
hyp_.emplace_back(); store(hyp_.back(), false);
}
const State* bestState() const {
const auto& v = hyp_.back(); const State* b = &v[0];
for (auto& s : v) if (s.score > b->score) b = &s;
return b;
}
std::vector<int> collapse(const State* s) const {
std::vector<int> rev;
for (; s; s = s->parent) rev.push_back(s->token);
std::vector<int> out;
int prev = -2; bool first = true; // the first path element is the start state or, after rebase(), the carried state (already returned)
for (auto it = rev.rbegin(); it != rev.rend(); ++it) {
int t = *it;
if (first) { first = false; prev = t; continue; } // start / carried state
if (t != prev && t != blank_ && t >= 0) out.push_back(t);
prev = t;
}
return out;
}
void reset_cand() { best_ = -std::numeric_limits<double>::infinity(); cand_.clear(); ptrs_.clear(); }
void add(double score, const LMStatePtr& l, const State* p, int t, bool b) {
if (score >= best_) best_ = score;
if (score >= best_ - thr_) cand_.emplace_back(score, l, p, t, b);
}
void store(std::vector<State>& out, bool sorted) { // candidatesStore
out.clear(); ptrs_.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::deque<std::vector<State>> hyp_; // deque: frames never move, so parent pointers stay valid
std::vector<State> cand_; std::vector<State*> ptrs_; std::vector<const State*> order_; std::vector<int> idx_;
double best_ = 0;
};
} // namespace streamdec
PYBIND11_MODULE(ctc_stream_decoder, m) {
py::module_::import("flashlight.lib.text.decoder");
py::class_<streamdec::StreamCTCDecoder>(m, "StreamCTCDecoder")
.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("reset", &streamdec::StreamCTCDecoder::reset)
.def("step", &streamdec::StreamCTCDecoder::step, py::call_guard<py::gil_scoped_release>())
.def("peek", &streamdec::StreamCTCDecoder::peek, py::call_guard<py::gil_scoped_release>())
.def("best", &streamdec::StreamCTCDecoder::best)
.def("finish", &streamdec::StreamCTCDecoder::finish)
.def("rebase", &streamdec::StreamCTCDecoder::rebase)
.def("frames", &streamdec::StreamCTCDecoder::frames);
}
|