// fst.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.
//
// Author: riley@google.com (Michael Riley)
//
// \file
// Finite-State Transducer (FST) - abstract base class definition,
// state and arc iterator interface, and suggested base implementation.
#ifndef FST_LIB_FST_H__
#define FST_LIB_FST_H__
#include "fst/lib/arc.h"
#include "fst/lib/compat.h"
#include "fst/lib/properties.h"
#include "fst/lib/register.h"
#include "fst/lib/symbol-table.h"
#include "fst/lib/util.h"
namespace fst {
class FstHeader;
template <class A> class StateIteratorData;
template <class A> class ArcIteratorData;
struct FstReadOptions {
string source; // Where you're reading from
const FstHeader *header; // Pointer to Fst header (if non-zero)
const SymbolTable* isymbols; // Pointer to input symbols (if non-zero)
const SymbolTable* osymbols; // Pointer to output symbols (if non-zero)
explicit FstReadOptions(const string& src = "<unspecified>",
const FstHeader *hdr = 0,
const SymbolTable* isym = 0,
const SymbolTable* osym = 0)
: source(src), header(hdr), isymbols(isym), osymbols(osym) {}
};
struct FstWriteOptions {
string source; // Where you're writing to
bool write_header; // Write the header?
bool write_isymbols; // Write input symbols?
bool write_osymbols; // Write output symbols?
explicit FstWriteOptions(const string& src = "<unspecifed>",
bool hdr = true, bool isym = true,
bool osym = true)
: source(src), write_header(hdr),
write_isymbols(isym), write_osymbols(osym) {}
};
//
// Fst HEADER CLASS
//
// This is the recommended Fst file header representation.
//
class FstHeader {
public:
enum {
HAS_ISYMBOLS = 1, // Has input symbol table
HAS_OSYMBOLS = 2 // Has output symbol table
} Flags;
FstHeader() : version_(0), flags_(0), properties_(0), start_(-1),
numstates_(0), numarcs_(0) {}
const string &FstType() const { return fsttype_; }
const string &ArcType() const { return arctype_; }
int32 Version() const { return version_; }
int32 GetFlags() const { return flags_; }
uint64 Properties() const { return properties_; }
int64 Start() const { return start_; }
int64 NumStates() const { return numstates_; }
int64 NumArcs() const { return numarcs_; }
void SetFstType(const string& type) { fsttype_ = type; }
void SetArcType(const string& type) { arctype_ = type; }
void SetVersion(int32 version) { version_ = version; }
void SetFlags(int32 flags) { flags_ = flags; }
void SetProperties(uint64 properties) { properties_ = properties; }
void SetStart(int64 start) { start_ = start; }
void SetNumStates(int64 numstates) { numstates_ = numstates; }
void SetNumArcs(int64 numarcs) { numarcs_ = numarcs; }
bool Read(istream &strm, const string &source);
bool Write(ostream &strm, const string &source) const;
private:
string fsttype_; // E.g. "vector"
string arctype_; // E.g. "standard"
int32 version_; // Type version #
int32 flags_; // File format bits
uint64 properties_; // FST property bits
int64 start_; // Start state
int64 numstates_; // # of states
int64 numarcs_; // # of arcs
};
//
// Fst INTERFACE CLASS DEFINITION
//
// A generic FST, templated on the arc definition, with
// common-demoninator methods (use StateIterator and ArcIterator to
// iterate over its states and arcs).
template <class A>
class Fst {
public:
typedef A Arc;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
virtual ~Fst() {}
virtual StateId Start() const = 0; // Initial state
virtual Weight Final(StateId) const = 0; // State's final weight
virtual size_t NumArcs(StateId) const = 0; // State's arc count
virtual size_t NumInputEpsilons(StateId)
const = 0; // State's input epsilon count
virtual size_t NumOutputEpsilons(StateId)
const = 0; // State's output epsilon count
// If test=false, return stored properties bits for mask (some poss. unknown)
// If test=true, return property bits for mask (computing o.w. unknown)
virtual uint64 Properties(uint64 mask, bool test)
const = 0; // Property bits
virtual const string& Type() const = 0; // Fst type name
// Get a copy of this Fst.
virtual Fst<A> *Copy() const = 0;
// Read an Fst from an input stream; returns NULL on error
static Fst<A> *Read(istream &strm, const FstReadOptions &opts) {
FstReadOptions ropts(opts);
FstHeader hdr;
if (ropts.header)
hdr = *opts.header;
else {
if (!hdr.Read(strm, opts.source))
return 0;
ropts.header = &hdr;
}
FstRegister<A> *registr = FstRegister<A>::GetRegister();
const typename FstRegister<A>::Reader reader =
registr->GetReader(hdr.FstType());
if (!reader) {
LOG(ERROR) << "Fst::Read: Unknown FST type \"" << hdr.FstType()
<< "\" (arc type = \"" << A::Type()
<< "\"): " << ropts.source;
return 0;
}
return reader(strm, ropts);
};
// Read an Fst from a file; return NULL on error
static Fst<A> *Read(const string &filename) {
ifstream strm(filename.c_str());
if (!strm) {
LOG(ERROR) << "Fst::Read: Can't open file: " << filename;
return 0;
}
return Read(strm, FstReadOptions(filename));
}
// Write an Fst to an output stream; return false on error
virtual bool Write(ostream &strm, const FstWriteOptions &opts) const {
LOG(ERROR) << "Fst::Write: No write method for " << Type() << " Fst type";
return false;
}
// Write an Fst to a file; return false on error
virtual bool Write(const string &filename) const {
LOG(ERROR) << "Fst::Write: No write method for "
<< Type() << " Fst type: "
<< (filename.empty() ? "standard output" : filename);
return false;
}
// Return input label symbol table; return NULL if not specified
virtual const SymbolTable* InputSymbols() const = 0;
// Return output label symbol table; return NULL if not specified
virtual const SymbolTable* OutputSymbols() const = 0;
// For generic state iterator construction; not normally called
// directly by users.
virtual void InitStateIterator(StateIteratorData<A> *) const = 0;
// For generic arc iterator construction; not normally called
// directly by users.
virtual void InitArcIterator(StateId s, ArcIteratorData<A> *) const = 0;
};
//
// STATE and ARC ITERATOR DEFINITIONS
//
// State iterator interface templated on the Arc definition; used
// for StateIterator specializations returned by InitStateIterator.
template <class A>
class StateIteratorBase {
public:
typedef A Arc;
typedef typename A::StateId StateId;
virtual ~StateIteratorBase() {}
virtual bool Done() const = 0; // End of iterator?
virtual StateId Value() const = 0; // Current state (when !Done)
virtual void Next() = 0; // Advance to next state (when !Done)
virtual void Reset() = 0; // Return to initial condition
};
// StateIterator initialization data
template <class A> struct StateIteratorData {
StateIteratorBase<A> *base; // Specialized iterator if non-zero
typename A::StateId nstates; // O.w. total # of states
};
// Generic state iterator, templated on the FST definition
// - a wrapper around pointer to specific one.
// Here is a typical use: \code
// for (StateIterator<StdFst> siter(fst);
// !siter.Done();
// siter.Next()) {
// StateId s = siter.Value();
// ...
// } \endcode
template <class F>
class StateIterator {
public:
typedef typename F::Arc Arc;
typedef typename Arc::StateId StateId;
explicit StateIterator(const F &fst) : s_(0) {
fst.InitStateIterator(&data_);
}
~StateIterator() { if (data_.base) delete data_.base; }
bool Done() const {
return data_.base ? data_.base->Done() : s_ >= data_.nstates;
}
StateId Value() const { return data_.base ? data_.base->Value() : s_; }
void Next() {
if (data_.base)
data_.base->Next();
else
++s_;
}
void Reset() {
if (data_.base)
data_.base->Reset();
else
s_ = 0;
}
private:
StateIteratorData<Arc> data_;
StateId s_;
DISALLOW_EVIL_CONSTRUCTORS(StateIterator);
};
// Arc iterator interface, templated on the Arc definition; used
// for Arc iterator specializations that are returned by InitArcIterator.
template <class A>
class ArcIteratorBase {
public:
typedef A Arc;
typedef typename A::StateId StateId;
virtual ~ArcIteratorBase() {}
virtual bool Done() const = 0; // End of iterator?
virtual const A& Value() const = 0; // Current state (when !Done)
virtual void Next() = 0; // Advance to next arc (when !Done)
virtual void Reset() = 0; // Return to initial condition
virtual void Seek(size_t a) = 0; // Random arc access by position
};
// ArcIterator initialization data
template <class A> struct ArcIteratorData {
ArcIteratorBase<A> *base; // Specialized iterator if non-zero
const A *arcs; // O.w. arcs pointer
size_t narcs; // ... and arc count
int *ref_count; // ... and reference count if non-zero
};
// Generic arc iterator, templated on the FST definition
// - a wrapper around pointer to specific one.
// Here is a typical use: \code
// for (ArcIterator<StdFst> aiter(fst, s));
// !aiter.Done();
// aiter.Next()) {
// StdArc &arc = aiter.Value();
// ...
// } \endcode
template <class F>
class ArcIterator {
public:
typedef typename F::Arc Arc;
typedef typename Arc::StateId StateId;
ArcIterator(const F &fst, StateId s) : i_(0) {
fst.InitArcIterator(s, &data_);
}
~ArcIterator() {
if (data_.base)
delete data_.base;
else if (data_.ref_count)
--(*data_.ref_count);
}
bool Done() const {
return data_.base ? data_.base->Done() : i_ >= data_.narcs;
}
const Arc& Value() const {
return data_.base ? data_.base->Value() : data_.arcs[i_];
}
void Next() {
if (data_.base)
data_.base->Next();
else
++i_;
}
void Reset() {
if (data_.base)
data_.base->Reset();
else
i_ = 0;
}
void Seek(size_t a) {
if (data_.base)
data_.base->Seek(a);
else
i_ = a;
}
private:
ArcIteratorData<Arc> data_;
size_t i_;
DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
};
// A useful alias when using StdArc.
typedef Fst<StdArc> StdFst;
//
// CONSTANT DEFINITIONS
//
const int kNoStateId = -1; // Not a valid state ID
const int kNoLabel = -1; // Not a valid label
const int kPhiLabel = -2; // Failure transition label
const int kRhoLabel = -3; // Matches o.w. unmatched labels (lib. internal)
const int kSigmaLabel = -4; // Matches all labels in alphabet.
//
// Fst IMPLEMENTATION BASE
//
// This is the recommended Fst implementation base class. It will
// handle reference counts, property bits, type information and symbols.
//
template <class A> class FstImpl {
public:
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
FstImpl()
: properties_(0), type_("null"), isymbols_(0), osymbols_(0),
ref_count_(1) {}
FstImpl(const FstImpl<A> &impl)
: properties_(impl.properties_), type_(impl.type_),
isymbols_(impl.isymbols_ ? new SymbolTable(impl.isymbols_) : 0),
osymbols_(impl.osymbols_ ? new SymbolTable(impl.osymbols_) : 0),
ref_count_(1) {}
~FstImpl() {
delete isymbols_;
delete osymbols_;
}
const string& Type() const { return type_; }
void SetType(const string &type) { type_ = type; }
uint64 Properties() const { return properties_; }
uint64 Properties(uint64 mask) const { return properties_ & mask; }
void SetProperties(uint64 props) { properties_ = props; }
void SetProperties(uint64 props, uint64 mask) {
properties_ &= ~mask;
properties_ |= props & mask;
}
const SymbolTable* InputSymbols() const { return isymbols_; }
const SymbolTable* OutputSymbols() const { return osymbols_; }
SymbolTable* InputSymbols() { return isymbols_; }
SymbolTable* OutputSymbols() { return osymbols_; }
void SetInputSymbols(const SymbolTable* isyms) {
if (isymbols_) delete isymbols_;
isymbols_ = isyms ? isyms->Copy() : 0;
}
void SetOutputSymbols(const SymbolTable* osyms) {
if (osymbols_) delete osymbols_;
osymbols_ = osyms ? osyms->Copy() : 0;
}
int RefCount() const { return ref_count_; }
int IncrRefCount() { return ++ref_count_; }
int DecrRefCount() { return --ref_count_; }
// Read-in header and symbols, initialize Fst, and return the header.
// If opts.header is non-null, skip read-in and use the option value.
// If opts.[io]symbols is non-null, read-in but use the option value.
bool ReadHeaderAndSymbols(istream &strm, const FstReadOptions& opts,
int min_version, FstHeader *hdr) {
if (opts.header)
*hdr = *opts.header;
else if (!hdr->Read(strm, opts.source))
return false;
if (hdr->FstType() != type_) {
LOG(ERROR) << "FstImpl::ReadHeaderAndSymbols: Fst not of type \""
<< type_ << "\": " << opts.source;
return false;
}
if (hdr->ArcType() != A::Type()) {
LOG(ERROR) << "FstImpl::ReadHeaderAndSymbols: Arc not of type \""
<< A::Type()
<< "\": " << opts.source;
return false;
}
if (hdr->Version() < min_version) {
LOG(ERROR) << "FstImpl::ReadHeaderAndSymbols: Obsolete "
<< type_ << " Fst version: " << opts.source;
return false;
}
properties_ = hdr->Properties();
if (hdr->GetFlags() & FstHeader::HAS_ISYMBOLS)
isymbols_ = SymbolTable::Read(strm, opts.source);
if (hdr->GetFlags() & FstHeader::HAS_OSYMBOLS)
osymbols_ =SymbolTable::Read(strm, opts.source);
if (opts.isymbols) {
delete isymbols_;
isymbols_ = opts.isymbols->Copy();
}
if (opts.osymbols) {
delete osymbols_;
osymbols_ = opts.osymbols->Copy();
}
return true;
}
// Write-out header and symbols.
// If a opts.header is false, skip writing header.
// If opts.[io]symbols is false, skip writing those symbols.
void WriteHeaderAndSymbols(ostream &strm, const FstWriteOptions& opts,
int version, FstHeader *hdr) const {
if (opts.write_header) {
hdr->SetFstType(type_);
hdr->SetArcType(A::Type());
hdr->SetVersion(version);
hdr->SetProperties(properties_);
int32 file_flags = 0;
if (isymbols_ && opts.write_isymbols)
file_flags |= FstHeader::HAS_ISYMBOLS;
if (osymbols_ && opts.write_osymbols)
file_flags |= FstHeader::HAS_OSYMBOLS;
hdr->SetFlags(file_flags);
hdr->Write(strm, opts.source);
}
if (isymbols_ && opts.write_isymbols) isymbols_->Write(strm);
if (osymbols_ && opts.write_osymbols) osymbols_->Write(strm);
}
protected:
uint64 properties_; // Property bits
private:
string type_; // Unique name of Fst class
SymbolTable *isymbols_; // Ilabel symbol table
SymbolTable *osymbols_; // Olabel symbol table
int ref_count_; // Reference count
void operator=(const FstImpl<A> &impl); // disallow
};
} // namespace fst;
#endif // FST_LIB_FST_H__
