// compose-filter.h
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Classes for filtering the composition matches, e.g. for correct epsilon
// handling.
#ifndef FST_LIB_COMPOSE_FILTER_H__
#define FST_LIB_COMPOSE_FILTER_H__
#include <fst/fst.h>
#include <fst/fst-decl.h> // For optional argument declarations
#include <fst/matcher.h>
namespace fst {
// COMPOSITION FILTER STATE - this represents the state of
// the composition filter. It has the form:
//
// class FilterState {
// public:
// // Required constructors
// FilterState();
// FilterState(const FilterState &f);
// // An invalid filter state.
// static const FilterState NoState();
// // Maps state to integer for hashing.
// size_t Hash() const;
// // Equality of filter states.
// bool operator==(const FilterState &f) const;
// // Inequality of filter states.
// bool operator!=(const FilterState &f) const;
// // Assignment to filter states.
// FilterState& operator=(const FilterState& f);
// };
// Filter state that is a signed integral type.
template <typename T>
class IntegerFilterState {
public:
IntegerFilterState() : state_(kNoStateId) {}
explicit IntegerFilterState(T s) : state_(s) {}
static const IntegerFilterState NoState() { return IntegerFilterState(); }
size_t Hash() const { return static_cast<size_t>(state_); }
bool operator==(const IntegerFilterState &f) const {
return state_ == f.state_;
}
bool operator!=(const IntegerFilterState &f) const {
return state_ != f.state_;
}
T GetState() const { return state_; }
void SetState(T state) { state_ = state; }
private:
T state_;
};
typedef IntegerFilterState<signed char> CharFilterState;
typedef IntegerFilterState<short> ShortFilterState;
typedef IntegerFilterState<int> IntFilterState;
// Filter state that is a weight (class).
template <class W>
class WeightFilterState {
public:
WeightFilterState() : weight_(W::Zero()) {}
explicit WeightFilterState(W w) : weight_(w) {}
static const WeightFilterState NoState() { return WeightFilterState(); }
size_t Hash() const { return weight_.Hash(); }
bool operator==(const WeightFilterState &f) const {
return weight_ == f.weight_;
}
bool operator!=(const WeightFilterState &f) const {
return weight_ != f.weight_;
}
W GetWeight() const { return weight_; }
void SetWeight(W w) { weight_ = w; }
private:
W weight_;
};
// Filter state that is the combination of two filter states.
template <class F1, class F2>
class PairFilterState {
public:
PairFilterState() : f1_(F1::NoState()), f2_(F2::NoState()) {}
PairFilterState(const F1 &f1, const F2 &f2) : f1_(f1), f2_(f2) {}
static const PairFilterState NoState() { return PairFilterState(); }
size_t Hash() const {
size_t h1 = f1_.Hash();
size_t h2 = f2_.Hash();
const int lshift = 5;
const int rshift = CHAR_BIT * sizeof(size_t) - 5;
return h1 << lshift ^ h1 >> rshift ^ h2;
}
bool operator==(const PairFilterState &f) const {
return f1_ == f.f1_ && f2_ == f.f2_;
}
bool operator!=(const PairFilterState &f) const {
return f1_ != f.f1_ || f2_ != f.f2_;
}
const F1 &GetState1() const { return f1_; }
const F2 &GetState2() const { return f2_; }
void SetState(const F1 &f1, const F2 &f2) {
f1_ = f1;
f2_ = f2;
}
private:
F1 f1_;
F2 f2_;
};
// COMPOSITION FILTERS - these determine which matches are allowed to
// proceed. The filter's state is represented by the type
// ComposeFilter::FilterState. The basic filters handle correct
// epsilon matching. Their interface is:
//
// template <class M1, class M2>
// class ComposeFilter {
// public:
// typedef typename M1::FST1 FST1;
// typedef typename M1::FST2 FST2;
// typedef typename FST1::Arc Arc;
// typedef ... FilterState;
// typedef ... Matcher1;
// typedef ... Matcher2;
//
// // Required constructors.
// ComposeFilter(const FST1 &fst1, const FST2 &fst2,
// // M1 *matcher1 = 0, M2 *matcher2 = 0);
// // If safe=true, the copy is thread-safe. See Fst<>::Copy()
// // for further doc.
// ComposeFilter(const ComposeFilter<M1, M2> &filter,
// // bool safe = false);
// // Return start state of filter.
// FilterState Start() const;
// // Specifies current composition state.
// void SetState(StateId s1, StateId s2, const FilterState &f);
//
// // Apply filter at current composition state to these transitions.
// // If an arc label to be matched is kNolabel, then that side
// // does not consume a symbol. Returns the new filter state or,
// // if disallowed, FilterState::NoState(). The filter is permitted to
// // modify its inputs, e.g. for optimizations.
// FilterState FilterArc(Arc *arc1, Arc *arc2) const;
// // Apply filter at current composition state to these final weights
// // (cf. superfinal transitions). The filter may modify its inputs,
// // e.g. for optimizations.
// void FilterFinal(Weight *final1, Weight *final2) const;
//
// // Return resp matchers. Ownership stays with filter. These
// // methods allow the filter to access and possibly modify
// // the composition matchers (useful e.g. with lookahead).
// Matcher1 *GetMatcher1();
// Matcher2 *GetMatcher2();
//
// // This specifies how the filter affects the composition result
// // properties. It takes as argument the properties that would
// // apply with a trivial composition fitler.
// uint64 Properties(uint64 props) const;
// };
// This filter requires epsilons on FST1 to be read before epsilons on FST2.
template <class M1, class M2>
class SequenceComposeFilter {
public:
typedef typename M1::FST FST1;
typedef typename M2::FST FST2;
typedef typename FST1::Arc Arc;
typedef CharFilterState FilterState;
typedef M1 Matcher1;
typedef M2 Matcher2;
typedef typename Arc::StateId StateId;
typedef typename Arc::Label Label;
typedef typename Arc::Weight Weight;
SequenceComposeFilter(const FST1 &fst1, const FST2 &fst2,
M1 *matcher1 = 0, M2 *matcher2 = 0)
: matcher1_(matcher1 ? matcher1 : new M1(fst1, MATCH_OUTPUT)),
matcher2_(matcher2 ? matcher2 : new M2(fst2, MATCH_INPUT)),
fst1_(matcher1_->GetFst()),
s1_(kNoStateId),
s2_(kNoStateId),
f_(kNoStateId) {}
SequenceComposeFilter(const SequenceComposeFilter<M1, M2> &filter,
bool safe = false)
: matcher1_(filter.matcher1_->Copy(safe)),
matcher2_(filter.matcher2_->Copy(safe)),
fst1_(matcher1_->GetFst()),
s1_(kNoStateId),
s2_(kNoStateId),
f_(kNoStateId) {}
~SequenceComposeFilter() {
delete matcher1_;
delete matcher2_;
}
FilterState Start() const { return FilterState(0); }
void SetState(StateId s1, StateId s2, const FilterState &f) {
if (s1_ == s1 && s2_ == s2 && f == f_)
return;
s1_ = s1;
s2_ = s2;
f_ = f;
size_t na1 = internal::NumArcs(fst1_, s1);
size_t ne1 = internal::NumOutputEpsilons(fst1_, s1);
bool fin1 = internal::Final(fst1_, s1) != Weight::Zero();
alleps1_ = na1 == ne1 && !fin1;
noeps1_ = ne1 == 0;
}
FilterState FilterArc(Arc