// See www.openfst.org for extensive documentation on this weighted
|
// finite-state transducer library.
|
//
|
// Utilities to convert strings into FSTs.
|
|
#ifndef FST_STRING_H_
|
#define FST_STRING_H_
|
|
#include <memory>
|
#include <sstream>
|
#include <string>
|
#include <vector>
|
|
#include <fst/flags.h>
|
#include <fst/log.h>
|
|
#include <fst/compact-fst.h>
|
#include <fst/icu.h>
|
#include <fst/mutable-fst.h>
|
#include <fst/util.h>
|
|
|
DECLARE_string(fst_field_separator);
|
|
namespace fst {
|
|
enum StringTokenType { SYMBOL = 1, BYTE = 2, UTF8 = 3 };
|
|
namespace internal {
|
|
template <class Label>
|
bool ConvertSymbolToLabel(const char *str, const SymbolTable *syms,
|
Label unknown_label, bool allow_negative,
|
Label *output) {
|
int64 n;
|
if (syms) {
|
n = syms->Find(str);
|
if ((n == -1) && (unknown_label != kNoLabel)) n = unknown_label;
|
if (n == -1 || (!allow_negative && n < 0)) {
|
LOG(ERROR) << "ConvertSymbolToLabel: Symbol \"" << str
|
<< "\" is not mapped to any integer label, symbol table = "
|
<< syms->Name();
|
return false;
|
}
|
} else {
|
char *p;
|
n = strtoll(str, &p, 10);
|
if (p < str + strlen(str) || (!allow_negative && n < 0)) {
|
LOG(ERROR) << "ConvertSymbolToLabel: Bad label integer "
|
<< "= \"" << str << "\"";
|
return false;
|
}
|
}
|
*output = n;
|
return true;
|
}
|
|
template <class Label>
|
bool ConvertStringToLabels(const string &str, StringTokenType token_type,
|
const SymbolTable *syms, Label unknown_label,
|
bool allow_negative, std::vector<Label> *labels) {
|
labels->clear();
|
if (token_type == StringTokenType::BYTE) {
|
labels->reserve(str.size());
|
return ByteStringToLabels(str, labels);
|
} else if (token_type == StringTokenType::UTF8) {
|
return UTF8StringToLabels(str, labels);
|
} else {
|
std::unique_ptr<char[]> c_str(new char[str.size() + 1]);
|
str.copy(c_str.get(), str.size());
|
c_str[str.size()] = 0;
|
std::vector<char *> vec;
|
const string separator = "\n" + FLAGS_fst_field_separator;
|
SplitString(c_str.get(), separator.c_str(), &vec, true);
|
for (const char *c : vec) {
|
Label label;
|
if (!ConvertSymbolToLabel(c, syms, unknown_label, allow_negative,
|
&label)) {
|
return false;
|
}
|
labels->push_back(label);
|
}
|
}
|
return true;
|
}
|
|
// The sep string is used as a separator between symbols, unless it is nullptr,
|
// in which case the last character of FLAGS_fst_field_separator is used.
|
template <class Label>
|
bool LabelsToSymbolString(const std::vector<Label> &labels, string *str,
|
const SymbolTable &syms,
|
const string *sep = nullptr) {
|
std::stringstream ostrm;
|
string delim = "";
|
for (auto label : labels) {
|
ostrm << delim;
|
const string &symbol = syms.Find(label);
|
if (symbol.empty()) {
|
LOG(ERROR) << "LabelToSymbolString: Label " << label
|
<< " is not mapped onto any textual symbol in symbol table "
|
<< syms.Name();
|
return false;
|
}
|
ostrm << symbol;
|
delim = sep != nullptr ? *sep : string(1, FLAGS_fst_field_separator.back());
|
}
|
*str = ostrm.str();
|
return !!ostrm;
|
}
|
|
} // namespace internal
|
|
// TODO(kbg): Move this just before StringPrinter.
|
// Converts an FST to a vector of output labels. To get input labels, use
|
// Project or Invert. Returns true on success. Use only with string FSTs; may
|
// loop for non-string FSTs.
|
template <class Arc>
|
bool StringFstToOutputLabels(const Fst<Arc> &fst,
|
std::vector<typename Arc::Label> *labels) {
|
labels->clear();
|
auto s = fst.Start();
|
if (s == kNoStateId) {
|
LOG(ERROR) << "StringFstToOutputLabels: Invalid start state";
|
return false;
|
}
|
while (fst.Final(s) == Arc::Weight::Zero()) {
|
ArcIterator<Fst<Arc>> aiter(fst, s);
|
if (aiter.Done()) {
|
LOG(ERROR) << "StringFstToOutputLabels: Does not reach final state";
|
return false;
|
}
|
const auto &arc = aiter.Value();
|
labels->push_back(arc.olabel);
|
s = arc.nextstate;
|
aiter.Next();
|
if (!aiter.Done()) {
|
LOG(ERROR) << "StringFstToOutputLabels: State has multiple outgoing arcs";
|
return false;
|
}
|
}
|
if (fst.NumArcs(s) != 0) {
|
LOG(ERROR) << "FstToOutputLabels: Final state has outgoing arc(s)";
|
return false;
|
}
|
return true;
|
}
|
|
// TODO(kbg): Move this just before StringPrinter.
|
// Converts a list of symbols to a string. Returns true on success. If the token
|
// type is SYMBOL and sep is provided, it is used to separate textual symbols.
|
// If the token type is SYMBOL and it is not provided, the last character of
|
// FLAGS_fst_field_separator is used.
|
template <class Label>
|
bool LabelsToString(const std::vector<Label> &labels, string *str,
|
StringTokenType ttype = BYTE,
|
const SymbolTable *syms = nullptr,
|
const string *sep = nullptr) {
|
switch (ttype) {
|
case StringTokenType::BYTE: {
|
return LabelsToByteString(labels, str);
|
}
|
case StringTokenType::UTF8: {
|
return LabelsToUTF8String(labels, str);
|
}
|
case StringTokenType::SYMBOL: {
|
return internal::LabelsToSymbolString(labels, str, *syms, sep);
|
}
|
}
|
return false;
|
}
|
|
// Functor for compiling a string in an FST.
|
template <class Arc>
|
class StringCompiler {
|
public:
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
explicit StringCompiler(StringTokenType token_type,
|
const SymbolTable *syms = nullptr,
|
Label unknown_label = kNoLabel,
|
bool allow_negative = false)
|
: token_type_(token_type),
|
syms_(syms),
|
unknown_label_(unknown_label),
|
allow_negative_(allow_negative) {}
|
|
// Compiles string into an FST.
|
template <class FST>
|
bool operator()(const string &str, FST *fst) const {
|
std::vector<Label> labels;
|
if (!internal::ConvertStringToLabels(str, token_type_, syms_,
|
unknown_label_, allow_negative_,
|
&labels)) {
|
return false;
|
}
|
Compile(labels, fst);
|
return true;
|
}
|
|
template <class FST>
|
bool operator()(const string &str, FST *fst, Weight weight) const {
|
std::vector<Label> labels;
|
if (!internal::ConvertStringToLabels(str, token_type_, syms_,
|
unknown_label_, allow_negative_,
|
&labels)) {
|
return false;
|
}
|
Compile(labels, fst, std::move(weight));
|
return true;
|
}
|
|
private:
|
void Compile(const std::vector<Label> &labels, MutableFst<Arc> *fst,
|
Weight weight = Weight::One()) const {
|
fst->DeleteStates();
|
while (fst->NumStates() <= labels.size()) fst->AddState();
|
for (StateId i = 0; i < labels.size(); ++i) {
|
fst->AddArc(i, Arc(labels[i], labels[i], Weight::One(), i + 1));
|
}
|
fst->SetStart(0);
|
fst->SetFinal(labels.size(), std::move(weight));
|
}
|
|
template <class Unsigned>
|
void Compile(const std::vector<Label> &labels,
|
CompactStringFst<Arc, Unsigned> *fst) const {
|
fst->SetCompactElements(labels.begin(), labels.end());
|
}
|
|
template <class Unsigned>
|
void Compile(const std::vector<Label> &labels,
|
CompactWeightedStringFst<Arc, Unsigned> *fst,
|
const Weight &weight = Weight::One()) const {
|
std::vector<std::pair<Label, Weight>> compacts;
|
compacts.reserve(labels.size() + 1);
|
for (StateId i = 0; i < static_cast<StateId>(labels.size()) - 1; ++i) {
|
compacts.emplace_back(labels[i], Weight::One());
|
}
|
compacts.emplace_back(!labels.empty() ? labels.back() : kNoLabel, weight);
|
fst->SetCompactElements(compacts.begin(), compacts.end());
|
}
|
|
const StringTokenType token_type_;
|
const SymbolTable *syms_; // Symbol table (used when token type is symbol).
|
const Label unknown_label_; // Label for token missing from symbol table.
|
const bool allow_negative_; // Negative labels allowed?
|
|
StringCompiler(const StringCompiler &) = delete;
|
StringCompiler &operator=(const StringCompiler &) = delete;
|
};
|
|
// Helpers for StringPrinter.
|
|
// Functor for printing a string FST as a string.
|
template <class Arc>
|
class StringPrinter {
|
public:
|
using Label = typename Arc::Label;
|
|
explicit StringPrinter(StringTokenType token_type,
|
const SymbolTable *syms = nullptr)
|
: token_type_(token_type), syms_(syms) {}
|
|
// Converts the FST into a string. With SYMBOL token type, sep is used as a
|
// separator between symbols, unless it is nullptr, in which case the last
|
// character of FLAGS_fst_field_separator is used. Returns true on success.
|
bool operator()(const Fst<Arc> &fst, string *str,
|
const string *sep = nullptr) const {
|
std::vector<Label> labels;
|
return (StringFstToOutputLabels(fst, &labels) &&
|
LabelsToString(labels, str, token_type_, syms_, sep));
|
}
|
|
private:
|
const StringTokenType token_type_;
|
const SymbolTable *syms_;
|
|
StringPrinter(const StringPrinter &) = delete;
|
StringPrinter &operator=(const StringPrinter &) = delete;
|
};
|
|
} // namespace fst
|
|
#endif // FST_STRING_H_
|
