// See www.openfst.org for extensive documentation on this weighted
|
// finite-state transducer library.
|
//
|
// Class to compute the intersection of two FSAs.
|
|
#ifndef FST_INTERSECT_H_
|
#define FST_INTERSECT_H_
|
|
#include <algorithm>
|
#include <vector>
|
|
#include <fst/log.h>
|
|
#include <fst/cache.h>
|
#include <fst/compose.h>
|
|
|
namespace fst {
|
|
using IntersectOptions = ComposeOptions;
|
|
template <class Arc, class M = Matcher<Fst<Arc>>,
|
class Filter = SequenceComposeFilter<M>,
|
class StateTable =
|
GenericComposeStateTable<Arc, typename Filter::FilterState>>
|
struct IntersectFstOptions
|
: public ComposeFstOptions<Arc, M, Filter, StateTable> {
|
IntersectFstOptions() {}
|
|
explicit IntersectFstOptions(const CacheOptions &opts, M *matcher1 = nullptr,
|
M *matcher2 = nullptr, Filter *filter = nullptr,
|
StateTable *state_table = nullptr)
|
: ComposeFstOptions<Arc, M, Filter, StateTable>(opts, matcher1, matcher2,
|
filter, state_table) {}
|
};
|
|
// Computes the intersection (Hadamard product) of two FSAs. This version is a
|
// delayed FST. Only strings that are in both automata are retained in the
|
// result.
|
//
|
// The two arguments must be acceptors. One of the arguments must be
|
// label-sorted.
|
//
|
// Complexity: same as ComposeFst.
|
//
|
// Caveats: same as ComposeFst.
|
template <class A>
|
class IntersectFst : public ComposeFst<A> {
|
public:
|
using Arc = A;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
using ComposeFst<A>::CreateBase;
|
using ComposeFst<A>::CreateBase1;
|
using ComposeFst<A>::Properties;
|
|
IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
|
const CacheOptions &opts = CacheOptions())
|
: ComposeFst<Arc>(CreateBase(fst1, fst2, opts)) {
|
const bool acceptors =
|
fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
|
if (!acceptors) {
|
FSTERROR() << "IntersectFst: Input FSTs are not acceptors";
|
GetMutableImpl()->SetProperties(kError);
|
}
|
}
|
|
template <class M, class Filter, class StateTable>
|
IntersectFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
|
const IntersectFstOptions<Arc, M, Filter, StateTable> &opts)
|
: ComposeFst<Arc>(CreateBase1(fst1, fst2, opts)) {
|
const bool acceptors =
|
fst1.Properties(kAcceptor, true) && fst2.Properties(kAcceptor, true);
|
if (!acceptors) {
|
FSTERROR() << "IntersectFst: input FSTs are not acceptors";
|
GetMutableImpl()->SetProperties(kError);
|
}
|
}
|
|
// See Fst<>::Copy() for doc.
|
IntersectFst(const IntersectFst<Arc> &fst, bool safe = false)
|
: ComposeFst<Arc>(fst, safe) {}
|
|
// Get a copy of this IntersectFst. See Fst<>::Copy() for further doc.
|
IntersectFst<Arc> *Copy(bool safe = false) const override {
|
return new IntersectFst<Arc>(*this, safe);
|
}
|
|
private:
|
using ImplToFst<internal::ComposeFstImplBase<A>>::GetImpl;
|
using ImplToFst<internal::ComposeFstImplBase<A>>::GetMutableImpl;
|
};
|
|
// Specialization for IntersectFst.
|
template <class Arc>
|
class StateIterator<IntersectFst<Arc>> : public StateIterator<ComposeFst<Arc>> {
|
public:
|
explicit StateIterator(const IntersectFst<Arc> &fst)
|
: StateIterator<ComposeFst<Arc>>(fst) {}
|
};
|
|
// Specialization for IntersectFst.
|
template <class Arc>
|
class ArcIterator<IntersectFst<Arc>> : public ArcIterator<ComposeFst<Arc>> {
|
public:
|
using StateId = typename Arc::StateId;
|
|
ArcIterator(const IntersectFst<Arc> &fst, StateId s)
|
: ArcIterator<ComposeFst<Arc>>(fst, s) {}
|
};
|
|
// Useful alias when using StdArc.
|
using StdIntersectFst = IntersectFst<StdArc>;
|
|
// Computes the intersection (Hadamard product) of two FSAs. This version
|
// writes the intersection to an output MurableFst. Only strings that are in
|
// both automata are retained in the result.
|
//
|
// The two arguments must be acceptors. One of the arguments must be
|
// label-sorted.
|
//
|
// Complexity: same as Compose.
|
//
|
// Caveats: same as Compose.
|
template <class Arc>
|
void Intersect(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
|
MutableFst<Arc> *ofst,
|
const IntersectOptions &opts = IntersectOptions()) {
|
using M = Matcher<Fst<Arc>>;
|
// In each case, we cache only the last state for fastest copy.
|
switch (opts.filter_type) {
|
case AUTO_FILTER: {
|
CacheOptions nopts;
|
nopts.gc_limit = 0;
|
*ofst = IntersectFst<Arc>(ifst1, ifst2, nopts);
|
break;
|
}
|
case SEQUENCE_FILTER: {
|
IntersectFstOptions<Arc> iopts;
|
iopts.gc_limit = 0;
|
*ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
|
break;
|
}
|
case ALT_SEQUENCE_FILTER: {
|
IntersectFstOptions<Arc, M, AltSequenceComposeFilter<M>> iopts;
|
iopts.gc_limit = 0;
|
*ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
|
break;
|
}
|
case MATCH_FILTER: {
|
IntersectFstOptions<Arc, M, MatchComposeFilter<M>> iopts;
|
iopts.gc_limit = 0;
|
*ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
|
break;
|
}
|
case NO_MATCH_FILTER: {
|
IntersectFstOptions<Arc, M, NoMatchComposeFilter<M>> iopts;
|
iopts.gc_limit = 0;
|
*ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
|
break;
|
}
|
case NULL_FILTER: {
|
IntersectFstOptions<Arc, M, NullComposeFilter<M>> iopts;
|
iopts.gc_limit = 0;
|
*ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
|
break;
|
}
|
case TRIVIAL_FILTER: {
|
IntersectFstOptions<Arc, M, TrivialComposeFilter<M>> iopts;
|
iopts.gc_limit = 0;
|
*ofst = IntersectFst<Arc>(ifst1, ifst2, iopts);
|
break;
|
}
|
}
|
if (opts.connect) Connect(ofst);
|
}
|
|
} // namespace fst
|
|
#endif // FST_INTERSECT_H_
|
