// expand.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
// Expand a PDT to an FST.
#ifndef FST_EXTENSIONS_PDT_EXPAND_H__
#define FST_EXTENSIONS_PDT_EXPAND_H__
#include <vector>
using std::vector;
#include <fst/extensions/pdt/pdt.h>
#include <fst/extensions/pdt/paren.h>
#include <fst/extensions/pdt/shortest-path.h>
#include <fst/extensions/pdt/reverse.h>
#include <fst/cache.h>
#include <fst/mutable-fst.h>
#include <fst/queue.h>
#include <fst/state-table.h>
#include <fst/test-properties.h>
namespace fst {
template <class Arc>
struct ExpandFstOptions : public CacheOptions {
bool keep_parentheses;
PdtStack<typename Arc::StateId, typename Arc::Label> *stack;
PdtStateTable<typename Arc::StateId, typename Arc::StateId> *state_table;
ExpandFstOptions(
const CacheOptions &opts = CacheOptions(),
bool kp = false,
PdtStack<typename Arc::StateId, typename Arc::Label> *s = 0,
PdtStateTable<typename Arc::StateId, typename Arc::StateId> *st = 0)
: CacheOptions(opts), keep_parentheses(kp), stack(s), state_table(st) {}
};
// Properties for an expanded PDT.
inline uint64 ExpandProperties(uint64 inprops) {
return inprops & (kAcceptor | kAcyclic | kInitialAcyclic | kUnweighted);
}
// Implementation class for ExpandFst
template <class A>
class ExpandFstImpl
: public CacheImpl<A> {
public:
using FstImpl<A>::SetType;
using FstImpl<A>::SetProperties;
using FstImpl<A>::Properties;
using FstImpl<A>::SetInputSymbols;
using FstImpl<A>::SetOutputSymbols;
using CacheBaseImpl< CacheState<A> >::PushArc;
using CacheBaseImpl< CacheState<A> >::HasArcs;
using CacheBaseImpl< CacheState<A> >::HasFinal;
using CacheBaseImpl< CacheState<A> >::HasStart;
using CacheBaseImpl< CacheState<A> >::SetArcs;
using CacheBaseImpl< CacheState<A> >::SetFinal;
using CacheBaseImpl< CacheState<A> >::SetStart;
typedef A Arc;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
typedef StateId StackId;
typedef PdtStateTuple<StateId, StackId> StateTuple;
ExpandFstImpl(const Fst<A> &fst,
const vector<pair<typename Arc::Label,
typename Arc::Label> > &parens,
const ExpandFstOptions<A> &opts)
: CacheImpl<A>(opts), fst_(fst.Copy()),
stack_(opts.stack ? opts.stack: new PdtStack<StateId, Label>(parens)),
state_table_(opts.state_table ? opts.state_table :
new PdtStateTable<StateId, StackId>()),
own_stack_(opts.stack == 0), own_state_table_(opts.state_table == 0),
keep_parentheses_(opts.keep_parentheses) {
SetType("expand");
uint64 props = fst.Properties(kFstProperties, false);
SetProperties(ExpandProperties(props), kCopyProperties);
SetInputSymbols(fst.InputSymbols());
SetOutputSymbols(fst.OutputSymbols());
}
ExpandFstImpl(const ExpandFstImpl &impl)
: CacheImpl<A>(impl),
fst_(impl.fst_->Copy(true)),
stack_(new PdtStack<StateId, Label>(*impl.stack_)),
state_table_(new PdtStateTable<StateId, StackId>()),
own_stack_(true), own_state_table_(true),
keep_parentheses_(impl.keep_parentheses_) {
SetType("expand");
SetProperties(impl.Properties(), kCopyProperties);
SetInputSymbols(impl.InputSymbols());
SetOutputSymbols(impl.OutputSymbols());
}
~ExpandFstImpl() {
delete fst_;
if (own_stack_)
delete stack_;
if (own_state_table_)
delete state_table_;
}
StateId Start() {
if (!HasStart()) {
StateId s = fst_->Start();
if (s == kNoStateId)
return kNoStateId;
StateTuple tuple(s, 0);
StateId start = state_table_->FindState(tuple);
SetStart(start);
}
return CacheImpl<A>::Start();
}
Weight Final(StateId s) {
if (!HasFinal(s)) {
const StateTuple &tuple = state_table_->Tuple(s);
Weight w = fst_->Final(tuple.state_id);
if (w != Weight::Zero() && tuple.stack_id == 0)
SetFinal(s, w);
else
SetFinal(s, Weight::Zero());
}
return CacheImpl<A>::Final(s);
}
size_t NumArcs(StateId s) {
if (!HasArcs(s)) {
ExpandState(s);
}
return CacheImpl<A>::NumArcs(s);
}
size_t NumInputEpsilons(StateId s) {
if (!HasArcs(s))
ExpandState(s);
return CacheImpl<A>::NumInputEpsilons(s);
}
size_t NumOutputEpsilons(StateId s) {
if (!HasArcs(s))
ExpandState(s);
return CacheImpl<A>::NumOutputEpsilons(s);
}
void InitArcIterator(StateId s, ArcIteratorData<A> *data) {
if (!HasArcs(s))
ExpandState(s);
CacheImpl<A>::InitArcIterator(s, data);
}
// Computes the outgoing transitions from a state, creating new destination
// states as needed.
void ExpandState(StateId s) {
StateTuple tuple = state_table_->Tuple(s);
for (ArcIterator< Fst<A> > aiter(*fst_, tuple.state_id);
!aiter.Done(); aiter.Next()) {
Arc arc = aiter.Value();
StackId stack_id = stack_->Find(tuple.stack_id, arc.ilabel);
if (stack_id == -1) {
// Non-matching close parenthesis
continue;
} else if ((stack_id != tuple.stack_id) && !keep_parentheses_) {
// Stack push/pop
arc.ilabel = arc.olabel = 0;
}
StateTuple ntuple(arc.nextstate, stack_id);
arc.nextstate = state_table_->FindState(ntuple);
PushArc(s, arc);
}
SetArcs(s);
}
const PdtStack<StackId, Label> &GetStack() const { return *stack_; }
const PdtStateTable<StateId, StackId> &GetStateTable() const {
return *state_table_;
}
private:
const Fst<A> *fst_;
PdtStack<StackId, Label> *stack_;
PdtStateTable<StateId, StackId> *state_table_;
bool own_stack_;
bool own_state_table_;
bool keep_parentheses_;
void operator=(const ExpandFstImpl<A> &); // disallow
};
// Expands a pushdown transducer (PDT) encoded as an FST into an FST.
// This version is a delayed Fst. In the PDT, some transitions are
// labeled with open or close parentheses. To be interpreted as a PDT,
// the parens must balance on a path. The open-close parenthesis label
// pairs are passed in 'parens'. The expansion enforces the
// parenthesis constraints. The PDT must be expandable as an FST.
//
// This class attaches interface to implementation and handles
// reference counting, delegating most methods to ImplToFst.
template <class A>
class ExpandFst : public ImplToFst< ExpandFstImpl<A> > {
public:
friend class ArcIterator< ExpandFst<A> >;
friend class StateIterator< ExpandFst<A> >;
typedef A Arc;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
typedef StateId StackId;
typedef CacheState<A> State;
typedef ExpandFstImpl<A> Impl;
ExpandFst(const Fst<A> &fst,
const vector<pair<typename Arc::Label,
typename Arc::Label> > &parens)
: ImplToFst<Impl>(new Impl(fst, parens, ExpandFstOptions<A>())) {}
ExpandFst(const Fst<A> &fst,
const vector<pair<typename Arc::Label,
typename Arc::Label> > &parens,
const ExpandFstOptions<A> &opts)
: ImplToFst<Impl>(new Impl(fst, parens, opts)) {}
// See Fst<>::Copy() for doc.
ExpandFst(const ExpandFst<A> &fst, bool safe = false)
: ImplToFst<Impl>(fst, safe) {}
// Get a copy of this ExpandFst. See Fst<>::Copy() for further doc.
virtual ExpandFst<A> *Copy(bool safe = false) const {
return new ExpandFst<A>(*this, safe);
}
virtual inline void InitStateIterator(StateIteratorData<A> *data) const;
virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
GetImpl()->InitArcIterator(s, data);
}
const PdtStack<StackId, Label> &GetStack() const {
return GetImpl()->GetStack();
}
const PdtStateTable<StateId, StackId> &GetStateTable() const {
return GetImpl()->GetStateTable();
}
private:
// Makes visible to friends.
Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }
void operator=(const ExpandFst<A> &fst); // Disallow
};
// Specialization for ExpandFst.
template<class A>
class StateIterator< ExpandFst<A> >
: public CacheStateIterator< ExpandFst<A> > {
public:
explicit StateIterator(const ExpandFst<A> &fst)
: CacheStateIterator< ExpandFst<A> >(fst, fst.GetImpl()) {}
};
// Specialization for ExpandFst.
template <class A>
class ArcIterator< ExpandFst<A> >
: public CacheArcIterator< ExpandFst<A> > {
public:
typedef typename A::StateId StateId;
ArcIterator(const ExpandFst<A> &fst, StateId s)
: CacheArcIterator< ExpandFst<A> >(fst.GetImpl(), s) {
if (!fst.GetImpl()->HasArcs(s))
fst.GetImpl()->ExpandState(s);
}
private:
DISALLOW_COPY_AND_ASSIGN(ArcIterator);
};
template <class A> inline
void ExpandFst<A>::InitStateIterator(StateIteratorData<A> *data) const
{
data->base = new StateIterator< ExpandFst<A> >(*this);
}
//
// PrunedExpand Class
//
// Prunes the delayed expansion of a pushdown transducer (PDT) encoded
// as an FST into an FST. In the PDT, some transitions are labeled
// with open or close parentheses. To be interpreted as a PDT, the
// parens must balance on a path. The open-close parenthesis label
// pairs are passed in 'parens'. The expansion enforces the
// parenthesis constraints.
//
// The algorithm works by visiting the delayed ExpandFst using a
// shortest-stack first queue discipline and relies on the
// shortest-distance information computed using a reverse
// shortest-path call to perform the pruning.
//
// The algorithm maintains the same state ordering between the ExpandFst
// being visited 'efst_' and the result of pruning written into the
// MutableFst 'ofst_' to improve readability of the code.
//
template <class A>
class PrunedExpand {
public:
typedef A Arc;
typedef typename A::Label Label;
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
typedef StateId StackId;
typedef PdtStack<StackId, Label> Stack;
typedef PdtStateTable<StateId, StackId> StateTable;
typedef typename PdtBalanceData<Arc>::SetIterator SetIterator;
// Constructor taking as input a PDT specified by 'ifst' and 'parens'.
// 'keep_parentheses' specifies whether parentheses are replaced by
// epsilons or not during the expansion. 'opts' is the cache options
// used to instantiate the underlying ExpandFst.
PrunedExpand(const Fst<A> &ifst,
const vector<pair<Label, Label> > &parens,
bool keep_parentheses = false,
const CacheOptions &opts = CacheOptions())
: ifst_(ifst.Copy()),
keep_parentheses_(keep_parentheses),
stack_(parens),
efst_(ifst, parens,
ExpandFstOptions<Arc>(opts, true, &stack_, &state_table_)),
queue_(state_table_, stack_, stack_length_, distance_, fdistance_) {
Reverse(*ifst_, parens, &rfst_);
VectorFst<Arc> path;
reverse_shortest_path_ = new SP(
rfst_, parens,
PdtShortestPathOptions<A, FifoQueue<StateId> >(true, false));
reverse_shortest_path_->ShortestPath(&path);
balance_data_ = reverse_shortest_path_->GetBalanceData()->Reverse(
rfst_.NumStates(), 10, -1);
InitCloseParenMultimap(parens);
}
~PrunedExpand() {
delete ifst_;
delete reverse_shortest_path_;
delete balance_data_;
}
// Expands and prunes with weight threshold 'threshold' the input PDT.
// Writes the result in 'ofst'.
void Expand(MutableFst<A> *ofst, const Weight &threshold);
private:
static const uint8 kEnqueued;
static const uint8 kExpanded;
static const uint8 kSourceState;
// Comparison functor used by the queue:
// 1. states corresponding to shortest stack first,
// 2. among stacks of the same length, reverse lexicographic order is used,
// 3. among states with the same stack, shortest-first order is used.
class StackCompare {
public:
StackCompare(const StateTable &st,
const Stack &s, const vector<StackId> &sl,
const vector<Weight> &d, const vector<Weight> &fd)
: state_table_(st), stack_(s), stack_length_(sl),
distance_(d), fdistance_(fd) {}
bool operator()(StateId s1, StateId s2) const {
StackId si1 = state_table_.Tuple(s1).stack_id;
StackId si2 = state_table_.Tuple(s2).stack_id;
if (stack_length_[si1] < stack_length_[si2])
return true;
if (stack_length_[si1] > stack_length_[si2])
return false;
// If stack id equal, use A*
if (si1 == si2) {
Weight w1 = (s1 < distance_.size()) && (s1 < fdistance_.size()) ?
Times(distance_[s1], fdistance_[s1]) : Weight::Zero();
Weight w2 = (s2 < distance_.size()) && (s2 < fdistance_.size()) ?
Times(distance_[s2], fdistance_[s2]) : Weight::Zero();
return less_(w1, w2);
}
// If lenghts are equal, use reverse lexico.
for (; si1 != si2; si1 = stack_.Pop(si1), si2 = stack_.Pop(si2)) {
if (stack_.Top(si1) < stack_.Top(si2)) return true;
if (stack_.Top(si1) > stack_.Top(si2)) return false;
}
return false;
}
private:
const StateTable &state_table_;
const Stack &stack_;
const vector<StackId> &stack_length_;
const vector<Weight> &distance_;
const vector<Weight> &fdistance_;
NaturalLess<Weight> less_;
};
class ShortestStackFirstQueue
: public ShortestFirstQueue<StateId, StackCompare> {
public:
ShortestStackFirstQueue(
const PdtStateTable<StateId, StackId> &st,
const Stack &s,
const vector<StackId> &sl,
const vector<Weight> &d, const vector<Weight> &fd)
: ShortestFirstQueue<StateId, StackCompare>(
StackCompare(st, s, sl, d, fd)) {}
};
void InitCloseParenMultimap(const vector<pair<Label, Label> > &parens);
Weight DistanceToDest(StateId state, StateId source) const;
uint8 Flags(StateId s) const;
void SetFlags(StateId s, uint8 flags, uint8 mask);
Weight Distance(StateId s) const;
void SetDistance(StateId s, Weight w);
Weight FinalDistance(StateId s) const;
void SetFinalDistance(StateId s, Weight w);
StateId SourceState(StateId s) const;
void SetSourceState(StateId s, StateId p);
void AddStateAndEnqueue(StateId s);
void Relax(StateId s, const A &arc, Weight w);
bool PruneArc(StateId s, const A &arc);
void ProcStart();
void ProcFinal(StateId s);
bool ProcNonParen(StateId s, const A &arc, bool add_arc);
bool ProcOpenParen(StateId s, const A &arc, StackId si, StackId nsi);
bool ProcCloseParen(StateId s, const A &arc);
void ProcDestStates(StateId s, StackId si);
Fst<A> *ifst_; // Input PDT
VectorFst<Arc> rfst_; // Reversed PDT
bool keep_parentheses_; // Keep parentheses in ofst?
StateTable state_table_; // State table for efst_
Stack stack_; // Stack trie
ExpandFst<Arc> efst_; // Expanded PDT
vector<StackId> stack_length_; // Length of stack for given stack id
vector<Weight> distance_; // Distance from initial state in efst_/ofst
vector<Weight> fdistance_; // Distance to final states in efst_/ofst
ShortestStackFirstQueue queue_; // Queue used to visit efst_
vector<uint8> flags_; // Status flags for states in efst_/ofst
vector<StateId> sources_; // PDT source state for each expanded state
typedef PdtShortestPath<Arc, FifoQueue<StateId> > SP;
typedef typename SP::CloseParenMultimap ParenMultimap;
SP *reverse_shortest_path_; // Shortest path for rfst_
PdtBalanceData<Arc> *balance_data_; // Not owned by shortest_path_
ParenMultimap close_paren_multimap_; // Maps open paren arcs to
// balancing close paren arcs.
MutableFst<Arc> *ofst_; // Output fst
Weight limit_; // Weight limit
typedef unordered_map<StateId, Weight> DestMap;
DestMap dest_map_;
StackId current_stack_id_;
// 'current_stack_id_' is the stack id of the states currently at the top
// of queue, i.e., the states currently being popped and processed.
// 'dest_map_' maps a state 's' in 'ifst_' that is the source
// of a close parentheses matching the top of 'current_stack_id_; to
// the shortest-distance from '(s, current_stack_id_)' to the final
// states in 'efst_'.
ssize_t current_paren_id_; // Paren id at top of current stack
ssize_t cached_stack_id_;
StateId cached_source_;
slist<pair<StateId, Weight> > cached_dest_list_;
// 'cached_dest_list_' contains the set of pair of destination
// states and weight to final states for source state
// 'cached_source_' and paren id 'cached_paren_id': the set of
// source state of a close parenthesis with paren id
// 'cached_paren_id' balancing an incoming open parenthesis with
// paren id 'cached_paren_id' in state 'cached_source_'.
NaturalLess<Weight> less_;
};
template <class A> const uint8 PrunedExpand<A>::kEnqueued = 0x01;
template <class A> const uint8 PrunedExpand<A>::kExpanded = 0x02;
template <class A> const uint8 PrunedExpand<A>::kSourceState = 0x04;
// Initializes close paren multimap, mapping pairs (s,paren_id) to
// all the arcs out of s labeled with close parenthese for paren_id.
template <class A>
void PrunedExpand<A>::InitCloseParenMultimap(
const vector<pair<Label, Label> > &parens) {
unordered_map<Label, Label> paren_id_map;
for (Label i = 0; i < parens.size(); ++i) {
const pair<Label, Label> &p = parens[i];
paren_id_map[p.first] = i;
paren_id_map[p.second] = i;
}
for (StateIterator<Fst<Arc> > siter(*ifst_); !siter.Done(); siter.Next()) {
StateId s = siter.Value();
for (ArcIterator<Fst<Arc> > aiter(*ifst_, s);
!aiter.Done(); aiter.Next()) {
const Arc &arc = aiter.Value();
typename unordered_map<Label, Label>::const_iterator pit
= paren_id_map.find(arc.ilabel);
if (pit == paren_id_map.end()) continue;
if (arc.ilabel == parens[pit->second].second) { // Close paren
ParenState<Arc> paren_state(pit->second, s);
close_paren_multimap_.insert(make_pair(paren_state, arc));
}
}
}
}
// Returns the weight of the shortest balanced path from 'source' to 'dest'
// in 'ifst_', 'dest' must be the source state of a close paren arc.
template <class A>
typename A::Weight PrunedExpand<A>::DistanceToDest(StateId source,
StateId dest) const {
typename SP::SearchState s(source + 1, dest + 1);
VLOG(2) << "D(" << source << ", " << dest << ") ="
<< reverse_shortest_path_->GetShortestPathData().Distance(s);
return reverse_shortest_path_->GetShortestPathData().Distance(s);
}
// Returns the flags for state 's' in 'ofst_'.
template <class A>
uint8 PrunedExpand<A>::Flags(StateId s) const {
return s < flags_.size() ? flags_[s] : 0;
}
// Modifies the flags for state 's' in 'ofst_'.
template <class A>
void PrunedExpand<A>::SetFlags(StateId s, uint8 flags, uint8 mask) {
while (flags_.size() <= s) flags_.push_back(0);
flags_[s] &= ~mask;
flags_[s] |= flags & mask;
}
// Returns the shortest distance from the initial state to 's' in 'ofst_'.
template <class A>
typename A::Weight PrunedExpand<A>::Distance(StateId s) const {
return s < distance_.size() ? distance_[s] : Weight::Zero();
}
// Sets the shortest distance from the initial state to 's' in 'ofst_' to 'w'.
template <class A>
void PrunedExpand<A>::SetDistance(StateId s, Weight w) {
while (distance_.size() <= s ) distance_.push_back(Weight::Zero());
distance_[s] = w;
}
// Returns the shortest distance from 's' to the final states in 'ofst_'.
template <class A>
typename A::Weight PrunedExpand<A>::FinalDistance(StateId s) const {
return s < fdistance_.size() ? fdistance_[s] : Weight::Zero();
}
// Sets the shortest distance from 's' to the final states in 'ofst_' to 'w'.
template <class A>
void PrunedExpand<A>::SetFinalDistance(StateId s, Weight w) {
while (fdistance_.size() <= s) fdistance_.push_back(Weight::Zero());
fdistance_[s] = w;
}
// Returns the PDT "source" state of state 's' in 'ofst_'.
template <class A>
typename A::StateId PrunedExpand<A>::SourceState(StateId s) const {
return s < sources_.size() ? sources_[s] : kNoStateId;
}
// Sets the PDT "source" state of state 's' in 'ofst_' to state 'p' in 'ifst_'.
template <class A>
void PrunedExpand<A>::SetSourceState(StateId s, StateId p) {
while (sources_.size() <= s) sources_.push_back(kNoStateId);
sources_[s] = p;
}
// Adds state 's' of 'efst_' to 'ofst_' and inserts it in the queue,
// modifying the flags for 's' accordingly.
template <class A>
void PrunedExpand<A>::AddStateAndEnqueue(StateId s) {
if (!(Flags(s) & (kEnqueued | kExpanded))) {
while (ofst_->NumStates() <= s) ofst_->AddState();
queue_.Enqueue(s);
SetFlags(s, kEnqueued, kEnqueued);
} else if (Flags(s) & kEnqueued) {
queue_.Update(s);
}
// TODO(allauzen): Check everything is fine when kExpanded?
}
// Relaxes arc 'arc' out of state 's' in 'ofst_':
// * if the distance to 's' times the weight of 'arc' is smaller than
// the currently stored distance for 'arc.nextstate',
// updates 'Distance(arc.nextstate)' with new estimate;
// * if 'fd' is less than the currently stored distance from 'arc.nextstate'
// to the final state, updates with new estimate.
template <class A>
void PrunedExpand<A>::Relax(StateId s, const A &arc, Weight fd) {
Weight nd = Times(Distance(s), arc.weight);
if (less_(nd, Distance(arc.nextstate))) {
SetDistance(arc.nextstate, nd);
SetSourceState(arc.nextstate, SourceState(s));
}
if (less_(fd, FinalDistance(arc.nextstate)))
SetFinalDistance(arc.nextstate, fd);
VLOG(2) << "Relax: " << s << ", d[s] = " << Distance(s) << ", to "
<< arc.nextstate << ", d[ns] = " << Distance(arc.nextstate)
<< ", nd = " << nd;
}
// Returns 'true' if the arc 'arc' out of state 's' in 'efst_' needs to
// be pruned.
template <class A>
bool PrunedExpand<A>::PruneArc(StateId s, const A &arc) {
VLOG(2) << "Prune ?";
Weight fd = Weight::Zero();
if ((cached_source_ != SourceState(s)) ||
(cached_stack_id_ != current_stack_id_)) {
cached_source_ = SourceState(s);
cached_stack_id_ = current_stack_id_;
cached_dest_list_.clear();
if (cached_source_ != ifst_->Start()) {
for (SetIterator set_iter =
balance_data_->Find(current_paren_id_, cached_source_);
!set_iter.Done(); set_iter.Next()) {
StateId dest = set_iter.Element();
typename DestMap::const_iterator iter = dest_map_.find(dest);
cached_dest_list_.push_front(*iter);
}
} else {
// TODO(allauzen): queue discipline should prevent this never
// from happening; replace by a check.
cached_dest_list_.push_front(
make_pair(rfst_.Start() -1, Weight::One()));
}
}
for (typename slist<pair<StateId, Weight> >::const_iterator iter =
cached_dest_list_.begin();
iter != cached_dest_list_.end();
++iter) {
fd = Plus(fd,
Times(DistanceToDest(state_table_.Tuple(arc.nextstate).state_id,
iter->first),
iter->second));
}
Relax(s, arc, fd);
Weight w = Times(Distance(s), Times(arc.weight, fd));
return less_(limit_, w);
}
// Adds start state of 'efst_' to 'ofst_', enqueues it and initializes
// the distance data structures.
template <class A>
void PrunedExpand<A>::ProcStart() {
StateId s = efst_.Start();
AddStateAndEnqueue(s);
ofst_->SetStart(s);
SetSourceState(s, ifst_->Start());
current_stack_id_ = 0;
current_paren_id_ = -1;
stack_length_.push_back(0);
dest_map_[rfst_.Start() - 1] = Weight::One(); // not needed
cached_source_ = ifst_->Start();
cached_stack_id_ = 0;
cached_dest_list_.push_front(
make_pair(rfst_.Start() -1, Weight::One()));
PdtStateTuple<StateId, StackId> tuple(rfst_.Start() - 1, 0);
SetFinalDistance(state_table_.FindState(tuple), Weight::One());
SetDistance(s, Weight::One());
SetFinalDistance(s, DistanceToDest(ifst_->Start(), rfst_.Start() - 1));
VLOG(2) << DistanceToDest(ifst_->Start(), rfst_.Start() - 1);
}
// Makes 's' final in 'ofst_' if shortest accepting path ending in 's'
// is below threshold.
template <class A>
void PrunedExpand<A>::ProcFinal(StateId s) {
Weight final = efst_.Final(s);
if ((final == Weight::Zero()) || less_(limit_, Times(Distance(s), final)))
return;
ofst_->SetFinal(s, final);
}
// Returns true when arc (or meta-arc) 'arc' out of 's' in 'efst_' is
// below the threshold. When 'add_arc' is true, 'arc' is added to 'ofst_'.
template <class A>
bool PrunedExpand<A>::ProcNonParen(StateId s, const A &arc, bool add_arc) {
VLOG(2) << "ProcNonParen: " << s << " to " << arc.nextstate
<< ", " << arc.ilabel << ":" << arc.olabel << " / " << arc.weight
<< ", add_arc = " << (add_arc ? "true" : "false");
if (PruneArc(s, arc)) return false;
if(add_arc) ofst_->AddArc(s, arc);
AddStateAndEnqueue(arc.nextstate);
return true;
}
// Processes an open paren arc 'arc' out of state 's' in 'ofst_'.
// When 'arc' is labeled with an open paren,
// 1. considers each (shortest) balanced path starting in 's' by
// taking 'arc' and ending by a close paren balancing the open
// paren of 'arc' as a meta-arc, processes and prunes each meta-arc
// as a non-paren arc, inserting its destination to the queue;
// 2. if at least one of these meta-arcs has not been pruned,
// adds the destination of 'arc' to 'ofst_' as a new source state
// for the stack id 'nsi' and inserts it in the queue.
template <class A>
bool PrunedExpand<A>::ProcOpenParen(StateId s, const A &arc, StackId si,
StackId nsi) {
// Update the stack lenght when needed: |nsi| = |si| + 1.
while (stack_length_.size() <= nsi) stack_length_.push_back(-1);
if (stack_length_[nsi] == -1)
stack_length_[nsi] = stack_length_[si] + 1;
StateId ns = arc.nextstate;
VLOG(2) << "Open paren: " << s << "(" << state_table_.Tuple(s).state_id
<< ") to " << ns << "(" << state_table_.Tuple(ns).state_id << ")";
bool proc_arc = false;
Weight fd = Weight::Zero();
ssize_t paren_id = stack_.ParenId(arc.ilabel);
slist<StateId> sources;
for (SetIterator set_iter =
balance_data_->Find(paren_id, state_table_.Tuple(ns).state_id);
!set_iter.Done(); set_iter.Next()) {
sources.push_front(set_iter.Element());
}
for (typename slist<StateId>::const_iterator sources_iter = sources.begin();
sources_iter != sources.end();
++ sources_iter) {
StateId source = *sources_iter;
VLOG(2) << "Close paren source: " << source;
ParenState<Arc> paren_state(paren_id, source);
for (typename ParenMultimap::const_iterator iter =
close_paren_multimap_.find(paren_state);
iter != close_paren_multimap_.end() && paren_state == iter->first;
++iter) {
Arc meta_arc = iter->second;
PdtStateTuple<StateId, StackId> tuple(meta_arc.nextstate, si);
meta_arc.nextstate = state_table_.FindState(tuple);
VLOG(2) << state_table_.Tuple(ns).state_id << ", " << source;
VLOG(2) << "Meta arc weight = " << arc.weight << " Times "
<< DistanceToDest(state_table_.Tuple(ns).state_id, source)
<< " Times " << meta_arc.weight;
meta_arc.weight = Times(
arc.weight,
Times(DistanceToDest(state_table_.Tuple(ns).state_id, source),
meta_arc.weight));
proc_arc |= ProcNonParen(s, meta_arc, false);
fd = Plus(fd, Times(
Times(
DistanceToDest(state_table_.Tuple(ns).state_id, source),
iter->second.weight),
FinalDistance(meta_arc.nextstate)));
}
}
if (proc_arc) {
VLOG(2) << "Proc open paren " << s << " to " << arc.nextstate;
ofst_->AddArc(
s, keep_parentheses_ ? arc : Arc(0, 0, arc.weight, arc.nextstate));
AddStateAndEnqueue(arc.nextstate);
Weight nd = Times(Distance(s), arc.weight);
if(less_(nd, Distance(arc.nextstate)))
SetDistance(arc.nextstate, nd);
// FinalDistance not necessary for source state since pruning
// decided using the meta-arcs above. But this is a problem with
// A*, hence:
if (less_(fd, FinalDistance(arc.nextstate)))
SetFinalDistance(arc.nextstate, fd);
SetFlags(arc.nextstate, kSourceState, kSourceState);
}
return proc_arc;
}
// Checks that shortest path through close paren arc in 'efst_' is
// below threshold, if so adds it to 'ofst_'.
template <class A>
bool PrunedExpand<A>::ProcCloseParen(StateId s, const A &arc) {
Weight w = Times(Distance(s),
Times(arc.weight, FinalDistance(arc.nextstate)));
if (less_(limit_, w))
return false;
ofst_->AddArc(
s, keep_parentheses_ ? arc : Arc(0, 0, arc.weight, arc.nextstate));
return true;
}
// When 's' in 'ofst_' is a source state for stack id 'si', identifies
// all the corresponding possible destination states, that is, all the
// states in 'ifst_' that have an outgoing close paren arc balancing
// the incoming open paren taken to get to 's', and for each such
// state 't', computes the shortest distance from (t, si) to the final
// states in 'ofst_'. Stores this information in 'dest_map_'.
template <class A>
void PrunedExpand<A>::ProcDestStates(StateId s, StackId si) {
if (!(Flags(s) & kSourceState)) return;
if (si != current_stack_id_) {
dest_map_.clear();
current_stack_id_ = si;
current_paren_id_ = stack_.Top(current_stack_id_);
VLOG(2) << "StackID " << si << " dequeued for first time";
}
// TODO(allauzen): clean up source state business; rename current function to
// ProcSourceState.
SetSourceState(s, state_table_.Tuple(s).state_id);
ssize_t paren_id = stack_.Top(si);
for (SetIterator set_iter =
balance_data_->Find(paren_id, state_table_.Tuple(s).state_id);
!set_iter.Done(); set_iter.Next()) {
StateId dest_state = set_iter.Element();
if (dest_map_.find(dest_state) != dest_map_.end())
continue;
Weight dest_weight = Weight::Zero();
ParenState<Arc> paren_state(paren_id, dest_state);
for (typename ParenMultimap::const_iterator iter =
close_paren_multimap_.find(paren_state);
iter != close_paren_multimap_.end() && paren_state == iter->first;
++iter) {
const Arc &arc = iter->second;
PdtStateTuple<StateId, StackId> tuple(arc.nextstate, stack_.Pop(si));
dest_weight = Plus(dest_weight,
Times(arc.weight,
FinalDistance(state_table_.FindState(tuple))));
}
dest_map_[dest_state] = dest_weight;
VLOG(2) << "State " << dest_state << " is a dest state for stack id "
<< si << " with weight " << dest_weight;
}
}
// Expands and prunes with weight threshold 'threshold' the input PDT.
// Writes the result in 'ofst'.
template <class A>
void PrunedExpand<A>::Expand(
MutableFst<A> *ofst, const typename A::Weight &threshold) {
ofst_ = ofst;
ofst_->DeleteStates();
ofst_->SetInputSymbols(ifst_->InputSymbols());
ofst_->SetOutputSymbols(ifst_->OutputSymbols());
limit_ = Times(DistanceToDest(ifst_->Start(), rfst_.Start() - 1), threshold);
flags_.clear();
ProcStart();
while (!queue_.Empty()) {
StateId s = queue_.Head();
queue_.Dequeue();
SetFlags(s, kExpanded, kExpanded | kEnqueued);
VLOG(2) << s << " dequeued!";
ProcFinal(s);
StackId stack_id = state_table_.Tuple(s).stack_id;
ProcDestStates(s, stack_id);
for (ArcIterator<ExpandFst<Arc> > aiter(efst_, s);
!aiter.Done();
aiter.Next()) {
Arc arc = aiter.Value();
StackId nextstack_id = state_table_.Tuple(arc.nextstate).stack_id;
if (stack_id == nextstack_id)
ProcNonParen(s, arc, true);
else if (stack_id == stack_.Pop(nextstack_id))
ProcOpenParen(s, arc, stack_id, nextstack_id);
else
ProcCloseParen(s, arc);
}
VLOG(2) << "d[" << s << "] = " << Distance(s)
<< ", fd[" << s << "] = " << FinalDistance(s);
}
}
//
// Expand() Functions
//
template <class Arc>
struct ExpandOptions {
bool connect;
bool keep_parentheses;
typename Arc::Weight weight_threshold;
ExpandOptions(bool c = true, bool k = false,
typename Arc::Weight w = Arc::Weight::Zero())
: connect(c), keep_parentheses(k), weight_threshold(w) {}
};
// Expands a pushdown transducer (PDT) encoded as an FST into an FST.
// This version writes the expanded PDT result to a MutableFst.
// In the PDT, some transitions are labeled with open or close
// parentheses. To be interpreted as a PDT, the parens must balance on
// a path. The open-close parenthesis label pairs are passed in
// 'parens'. The expansion enforces the parenthesis constraints. The
// PDT must be expandable as an FST.
template <class Arc>
void Expand(
const Fst<Arc> &ifst,
const vector<pair<typename Arc::Label, typename Arc::Label> > &parens,
MutableFst<Arc> *ofst,
const ExpandOptions<Arc> &opts) {
typedef typename Arc::Label Label;
typedef typename Arc::StateId StateId;
typedef typename Arc::Weight Weight;
typedef typename ExpandFst<Arc>::StackId StackId;
ExpandFstOptions<Arc> eopts;
eopts.gc_limit = 0;
if (opts.weight_threshold == Weight::Zero()) {
eopts.keep_parentheses = opts.keep_parentheses;
*ofst = ExpandFst<Arc>(ifst, parens, eopts);
} else {
PrunedExpand<Arc> pruned_expand(ifst, parens, opts.keep_parentheses);
pruned_expand.Expand(ofst, opts.weight_threshold);
}
if (opts.connect)
Connect(ofst);
}
// Expands a pushdown transducer (PDT) encoded as an FST into an FST.
// This version writes the expanded PDT result to a MutableFst.
// In the PDT, some transitions are labeled with open or close
// parentheses. To be interpreted as a PDT, the parens must balance on
// a path. The open-close parenthesis label pairs are passed in
// 'parens'. The expansion enforces the parenthesis constraints. The
// PDT must be expandable as an FST.
template<class Arc>
void Expand(
const Fst<Arc> &ifst,
const vector<pair<typename Arc::Label, typename Arc::Label> > &parens,
MutableFst<Arc> *ofst,
bool connect = true, bool keep_parentheses = false) {
Expand(ifst, parens, ofst, ExpandOptions<Arc>(connect, keep_parentheses));
}
} // namespace fst
#endif // FST_EXTENSIONS_PDT_EXPAND_H__