Open-source speech recognition toolkit for training, inference, streaming ASR, VAD, punctuation, speaker diarization pipelines, and OpenAI-compatible/MCP serving.
Python asraudiochineseemotion-recognitionfunasrmcp-servermultilingual-asropenai-compatible-apiparaformerpunctuationpytorchreal-time-asrspeaker-diarizationspeech-recognitionspeech-to-textstreaming-asrtranscriptionvllmvoice-activity-detectionwhisper-alternative
// See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Functions and classes to compute the union of two FSTs.
#ifndef FST_UNION_H_
#define FST_UNION_H_
#include <algorithm>
#include <utility>
#include <vector>
#include <fst/mutable-fst.h>
#include <fst/rational.h>
namespace fst {
// Computes the union (sum) of two FSTs. This version writes the union to an
// output MutableFst. If A transduces string x to y with weight a and B
// transduces string w to v with weight b, then their union transduces x to y
// with weight a and w to v with weight b.
//
// Complexity:
//
// Time: (V_2 + E_2)
// Space: O(V_2 + E_2)
//
// where Vi is the number of states, and Ei is the number of arcs, in the ith
// FST.
template <class Arc>
void Union(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) {
using Weight = typename Arc::Weight;
// Checks for symbol table compatibility.
if (!CompatSymbols(fst1->InputSymbols(), fst2.InputSymbols()) ||
!CompatSymbols(fst1->OutputSymbols(), fst2.OutputSymbols())) {
FSTERROR() << "Union: Input/output symbol tables of 1st argument "
<< "do not match input/output symbol tables of 2nd argument";
fst1->SetProperties(kError, kError);
return;
}
const auto numstates1 = fst1->NumStates();
const bool initial_acyclic1 = fst1->Properties(kInitialAcyclic, true);
const auto props1 = fst1->Properties(kFstProperties, false);
const auto props2 = fst2.Properties(kFstProperties, false);
const auto start2 = fst2.Start();
if (start2 == kNoStateId) {
if (props2 & kError) fst1->SetProperties(kError, kError);
return;
}
if (fst2.Properties(kExpanded, false)) {
fst1->ReserveStates(numstates1 + CountStates(fst2) +
(initial_acyclic1 ? 0 : 1));
}
for (StateIterator<Fst<Arc>> siter(fst2); !siter.Done(); siter.Next()) {
const auto s1 = fst1->AddState();
const auto s2 = siter.Value();
fst1->SetFinal(s1, fst2.Final(s2));
fst1->ReserveArcs(s1, fst2.NumArcs(s2));
for (ArcIterator<Fst<Arc>> aiter(fst2, s2); !aiter.Done(); aiter.Next()) {
auto arc = aiter.Value(); // Copy intended.
arc.nextstate += numstates1;
fst1->AddArc(s1, std::move(arc));
}
}
const auto start1 = fst1->Start();
if (start1 == kNoStateId) {
fst1->SetStart(start2);
fst1->SetProperties(props2, kCopyProperties);
return;
}
if (initial_acyclic1) {
fst1->AddArc(start1, Arc(0, 0, Weight::One(), start2 + numstates1));
} else {
const auto nstart1 = fst1->AddState();
fst1->SetStart(nstart1);
fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start1));
fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start2 + numstates1));
}
fst1->SetProperties(UnionProperties(props1, props2), kFstProperties);
}
// Computes the union of two FSTs, modifying the RationalFst argument.
template <class Arc>
void Union(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
fst1->GetMutableImpl()->AddUnion(fst2);
}
using UnionFstOptions = RationalFstOptions;
// Computes the union (sum) of two FSTs. This version is a delayed FST. If A
// transduces string x to y with weight a and B transduces string w to v with
// weight b, then their union transduces x to y with weight a and w to v with
// weight b.
//
// Complexity:
//
// Time: O(v_1 + e_1 + v_2 + e_2)
// Space: O(v_1 + v_2)
//
// where vi is the number of states visited, and ei is the number of arcs
// visited, in the ith FST. Constant time and space to visit an input state or
// arc is assumed and exclusive of caching.
template <class A>
class UnionFst : public RationalFst<A> {
public:
using Arc = A;
using StateId = typename Arc::StateId;
using Weight = typename Arc::Weight;
UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
GetMutableImpl()->InitUnion(fst1, fst2);
}
UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
const UnionFstOptions &opts)
: RationalFst<Arc>(opts) {
GetMutableImpl()->InitUnion(fst1, fst2);
}
// See Fst<>::Copy() for doc.
UnionFst(const UnionFst<Arc> &fst, bool safe = false)
: RationalFst<Arc>(fst, safe) {}
// Gets a copy of this UnionFst. See Fst<>::Copy() for further doc.
UnionFst<Arc> *Copy(bool safe = false) const override {
return new UnionFst<Arc>(*this, safe);
}
private:
using ImplToFst<internal::RationalFstImpl<Arc>>::GetImpl;
using ImplToFst<internal::RationalFstImpl<Arc>>::GetMutableImpl;
};
// Specialization for UnionFst.
template <class Arc>
class StateIterator<UnionFst<Arc>> : public StateIterator<RationalFst<Arc>> {
public:
explicit StateIterator(const UnionFst<Arc> &fst)
: StateIterator<RationalFst<Arc>>(fst) {}
};
// Specialization for UnionFst.
template <class Arc>
class ArcIterator<UnionFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
public:
using StateId = typename Arc::StateId;
ArcIterator(const UnionFst<Arc> &fst, StateId s)
: ArcIterator<RationalFst<Arc>>(fst, s) {}
};
using StdUnionFst = UnionFst<StdArc>;
} // namespace fst
#endif // FST_UNION_H_