// lookahead-matcher.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 to add lookahead to FST matchers, useful e.g. for improving
// composition efficiency with certain inputs.
#ifndef FST_LIB_LOOKAHEAD_MATCHER_H__
#define FST_LIB_LOOKAHEAD_MATCHER_H__
#include <fst/add-on.h>
#include <fst/const-fst.h>
#include <fst/fst.h>
#include <fst/label-reachable.h>
#include <fst/matcher.h>
DECLARE_string(save_relabel_ipairs);
DECLARE_string(save_relabel_opairs);
namespace fst {
// LOOKAHEAD MATCHERS - these have the interface of Matchers (see
// matcher.h) and these additional methods:
//
// template <class F>
// class LookAheadMatcher {
// public:
// typedef F FST;
// typedef F::Arc Arc;
// typedef typename Arc::StateId StateId;
// typedef typename Arc::Label Label;
// typedef typename Arc::Weight Weight;
//
// // Required constructors.
// LookAheadMatcher(const F &fst, MatchType match_type);
// // If safe=true, the copy is thread-safe (except the lookahead Fst is
// // preserved). See Fst<>::Cop() for further doc.
// LookAheadMatcher(const LookAheadMatcher &matcher, bool safe = false);
//
// Below are methods for looking ahead for a match to a label and
// more generally, to a rational set. Each returns false if there is
// definitely not a match and returns true if there possibly is a
// match.
// // LABEL LOOKAHEAD: Can 'label' be read from the current matcher state
// // after possibly following epsilon transitions?
// bool LookAheadLabel(Label label) const;
//
// // RATIONAL LOOKAHEAD: The next methods allow looking ahead for an
// // arbitrary rational set of strings, specified by an FST and a state
// // from which to begin the matching. If the lookahead FST is a
// // transducer, this looks on the side different from the matcher
// // 'match_type' (cf. composition).
//
// // Are there paths P from 's' in the lookahead FST that can be read from
// // the cur. matcher state?
// bool LookAheadFst(const Fst<Arc>& fst, StateId s);
//
// // Gives an estimate of the combined weight of the paths P in the
// // lookahead and matcher FSTs for the last call to LookAheadFst.
// // A trivial implementation returns Weight::One(). Non-trivial
// // implementations are useful for weight-pushing in composition.
// Weight LookAheadWeight() const;
//
// // Is there is a single non-epsilon arc found in the lookahead FST
// // that begins P (after possibly following any epsilons) in the last
// // call LookAheadFst? If so, return true and copy it to '*arc', o.w.
// // return false. A trivial implementation returns false. Non-trivial
// // implementations are useful for label-pushing in composition.
// bool LookAheadPrefix(Arc *arc);
//
// // Optionally pre-specifies the lookahead FST that will be passed
// // to LookAheadFst() for possible precomputation. If copy is true,
// // then 'fst' is a copy of the FST used in the previous call to
// // this method (useful to avoid unnecessary updates).
// void InitLookAheadFst(const Fst<Arc>& fst, bool copy = false);
//
// };
//
// LOOK-AHEAD FLAGS (see also kMatcherFlags in matcher.h):
//
// Matcher is a lookahead matcher when 'match_type' is MATCH_INPUT.
const uint32 kInputLookAheadMatcher = 0x00000010;
// Matcher is a lookahead matcher when 'match_type' is MATCH_OUTPUT.
const uint32 kOutputLookAheadMatcher = 0x00000020;
// A non-trivial implementation of LookAheadWeight() method defined and
// should be used?
const uint32 kLookAheadWeight = 0x00000040;
// A non-trivial implementation of LookAheadPrefix() method defined and
// should be used?
const uint32 kLookAheadPrefix = 0x00000080;
// Look-ahead of matcher FST non-epsilon arcs?
const uint32 kLookAheadNonEpsilons = 0x00000100;
// Look-ahead of matcher FST epsilon arcs?
const uint32 kLookAheadEpsilons = 0x00000200;
// Ignore epsilon paths for the lookahead prefix? Note this gives
// correct results in composition only with an appropriate composition
// filter since it depends on the filter blocking the ignored paths.
const uint32 kLookAheadNonEpsilonPrefix = 0x00000400;
// For LabelLookAheadMatcher, save relabeling data to file
const uint32 kLookAheadKeepRelabelData = 0x00000800;
// Flags used for lookahead matchers.
const uint32 kLookAheadFlags = 0x00000ff0;
// LookAhead Matcher interface, templated on the Arc definition; used
// for lookahead matcher specializations that are returned by the
// InitMatcher() Fst method.
template <class A>
class LookAheadMatcherBase : public MatcherBase<A> {
public:
typedef A Arc;
typedef typename A::StateId StateId;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
LookAheadMatcherBase()
: weight_(Weight::One()),
prefix_arc_(kNoLabel, kNoLabel, Weight::One(), kNoStateId) {}
virtual ~LookAheadMatcherBase() {}
bool LookAheadLabel(Label label) const { return LookAheadLabel_(label); }
bool LookAheadFst(const Fst<Arc> &fst, StateId s) {
return LookAheadFst_(fst, s);
}
Weight LookAheadWeight() const { return weight_; }
bool LookAheadPrefix(Arc *arc) const {
if (prefix_arc_.nextstate != kNoStateId) {
*arc = prefix_arc_;
return true;
} else {
return false;
}
}
virtual void InitLookAheadFst(const Fst<Arc>& fst, bool copy = false) = 0;
protected:
void SetLookAheadWeight(const Weight &w) { weight_ = w; }
void SetLookAheadPrefix(const Arc &arc) { prefix_arc_ = arc; }
void ClearLookAheadPrefix() { prefix_arc_.nextstate = kNoStateId; }
private:
virtual bool LookAheadLabel_(Label label) const = 0;
virtual bool LookAheadFst_(const Fst<Arc> &fst,
StateId s) = 0; // This must set l.a. weight and
// prefix if non-trivial.
Weight weight_; // Look-ahead weight
Arc prefix_arc_; // Look-ahead prefix arc
};
// Don't really lookahead, just declare future looks good regardless.
template <class M>
class TrivialLookAheadMatcher
: public LookAheadMatcherBase<typename M::FST::Arc> {
public:
typedef typename M::FST FST;
typedef typename M::Arc Arc;
typedef typename Arc::StateId StateId;
typedef typename Arc::Label Label;
typedef typename Arc::Weight Weight;
TrivialLookAheadMatcher(const FST &fst, MatchType match_type)
: matcher_(fst, match_type) {}
TrivialLookAheadMatcher(const TrivialLookAheadMatcher<M> &lmatcher,
bool safe = false)
: matcher_(lmatcher.matcher_, safe) {}
// General matcher methods
TrivialLookAheadMatcher<M> *Copy(bool safe = false) const {
return new TrivialLookAheadMatcher<M>(*this, safe);
}
MatchType Type(bool test) const { return matcher_.Type(test); }
void SetState(StateId s) { return matcher_.SetState(s); }
bool Find(Label label) { return matcher_.Find(label); }
bool Done() const { return matcher_.Done(); }
const Arc& Value() const { return matcher_.Value(); }
void Next() { matcher_.Next(); }
virtual const