1. openfst 介绍
OpenFst是一个用于构造，组合，优化和搜索加权有限状态转换器（FST）的库。
FST在语音识别和合成，机器翻译，光学字符识别，模式匹配，字符串处理，机器学习，信息提取和检索等方面具有关键应用。
通常，加权转换器用于表示概率模型（例如，n元语法模型，发音模型）。可以通过确定和最小化来优化FST，可以将模型应用于假设集（也表示为自动机）或通过有限状态组成进行级联，并且可以通过最短路径算法选择最佳结果。
1.1 openfst相关资源
关于FST的算法调研，可以查看 "Weighted automata algorithms"
FST库的设计原则，可以查看 "The Design Principles of a Weighted Finite-State Transducer Library"
FST在语音识别中的应用：
- "Weighted Finite-State Transducers in Speech Recognition"
- "Speech recognition with weighted finite-state transducers"
有用的FST Tutorial: http://www.openfst.org/twiki/bin/view/FST/FstHltTutorial
2. OpenFst快速入门
2.1 查找和使用库
OpenFst库是C++模板库。在C++代码中，在include目录中包含<fst/fstlib.h>，并在库目录中链接到libfst.so，如果需要公共OpenFst类的前向声明，请包含<fst/fst-decl.h>。
安装目录的bin目录中有shell命令，可对FST的文件表示形式进行操作。
2.2 FST例子
如图，是一个FST
初始状态是0，终止状态是2且带有3.5权重， 任何带有非无限最终权重的状态都是最终状态，从0到1的状态转换，输入a，输出x，权重0.5。
这个FST将字符串ac转换为xz且权重为6.5（边和最终状态权重之和）。
2.3 创建FST
FST可以利用C++的构造和装饰器或者用shell在从文本文件中创建，下面将介绍这两种方法。
2.3.1 利用C++创建FST
// A vector FST is a general mutable FST
StdVectorFst fst;
// Adds state 0 to the initially empty FST and make it the start state.
fst.AddState(); // 1st state will be state 0 (returned by AddState)
fst.SetStart(0); // arg is state ID
// Adds two arcs exiting state 0.
// Arc constructor args: ilabel, olabel, weight, dest state ID.
fst.AddArc(0, StdArc(1, 1, 0.5, 1)); // 1st arg is src state ID
fst.AddArc(0, StdArc(2, 2, 1.5, 1));
// Adds state 1 and its arc.
fst.AddState();
fst.AddArc(1, StdArc(3, 3, 2.5, 2));
// Adds state 2 and set its final weight.
fst.AddState();
fst.SetFinal(2, 3.5); // 1st arg is state ID, 2nd arg weight
We can save this FST to a file with:
fst.Write("binary.fst");
2.3.2 利用文本文件在shell下创建FST
文本FST的格式遵循 AT&T FSM 规范，AT&T FSM 规范如下：
- 边(弧)：src dest ilabel olabel [weight]
- 终止状态： state [weight]
- 初始状态必须在首行，其他行顺序不要求
- 缺省权重0
首先创建文本FST text.fst如下：
0 1 a x .5
0 1 b y 1.5
1 2 c z 2.5
2 3.5
输入输出符号表文件
isyms.txt
<eps> 0
a 1
b 2
c 3
osyms.txt
<eps> 0
x 1
y 2
z 3
可以使用任何字符串作为符号，符号对应的ID为非负整数
零ID为epsilon符号保留，它是空字符串。即使示例中未使用0，我们也将其包含在表中。
由于后续的FST操作可能会添加ε，因此最好在其中添加一个符号。
创建二进制FST
# 符号表转换为整数
fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst
# 保留符号
fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst
二进制binary.fst创建完后，可以通过命令行使用，也可以利用C++接口读取StdFst *fst = StdFst::Read("binary.fst");
2.4 读取FST
读取FST可以用C++也可以用命令行。
2.4.1 C++读取
# 弧的结构体表示
struct StdArc {
typedef int Label;
typedef TropicalWeight Weight; // see "FST Weights" below
typedef int StateId;
Label ilabel;
Label olabel;
Weight weight;
StateId nextstate;
};
typedef StdArc::StateId StateId;
# Gets the initial state; if == kNoState => empty FST.
StateId initial_state = fst.Start();
# Get state i's final weight; if == Weight::Zero() => non-final.
Weight weight = fst.Final(i);
# Iterates over the FSTs states.
for (StateIterator<StdFst> siter(fst); !siter.Done(); siter.Next())
StateId state_id = siter.Value();
# Iterates over state i's arcs.
for (ArcIterator<StdFst> aiter(fst, i); !aiter.Done(); aiter.Next())
const StdArc &arc = aiter.Value();
# Iterates over state i's arcs that have input label l (FST must support this -
# in the simplest cases, true when the input labels are sorted).
Matcher<StdFst> matcher(fst, MATCH_INPUT);
matcher.SetState(i);
if (matcher.Find(l))
for (; !matcher.Done(); matcher.Next())
const StdArc &arc = matcher.Value();
2.4.2 从Shell打印，绘制和汇总FST
从二进制格式输出FST为文本格式
fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst
利用Graphviz画出FST
fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst binary.dot
# 转换为pdf文件
dot -Tps binary.dot > binary.ps
ps2pdf binary.ps binary.pdf
# 直接转换,如果中文显示乱码，请添加中文字体支持
dot -Tpdf binary.dot > binary.pdf
利用fstinfo binary.fst可以获得fst的各种信息
2.5 FST 操作
2.5.1 FST 操作
可以在C++或从Shell命令调用FST操作。
2.5.1.1 C++操作
首先需要了解fst的类继承关系
FST类接口包含下面抽象类：
- Fst<Arc>: 支持弧相关操作
- ExpandedFst<Arc>: 额外支持NumStates()的Fst
- MutableFst<Arc>:一个ExpandedFst,支持各种变异操作，例如AddStates()和SetStart()
特定的非抽象FST包括以下类模板： - VectorFst<Arc>: 通用可变FST
- ConstFst<Arc>: 通用扩展的，不变的FST
- ComposeFst<Arc>: 两个FST的不可扩展，延迟组合
这些类在弧上模板化以允许自定义。StdFst类是Fst <StdArc>的typedef。上述所有模板都存在类似的typedef。
对于状态和弧迭代器，如果将最具体的FST类指定为迭代器模板参数（例如，已知的StdVectorFst的ArcIterator <StdVectorFst>而不是ArcIterator <StdFst>），则将获得最高的效率。
C++ FST操作以三种通用形式出现： - 破坏性的：当某个操作(如Connect)修改其输入时，其形式为：
void Connect(MutableFst<Arc> *fst);
- 建设性的：当一个操作(如Reverse)创建新的扩展Fst时，其形式为：
void Reverse(const Fst<Arc> &infst, MutableFst<Arc> *outfst);
- 延迟性的：当一个操作（如ComposeFst）创建一个惰性求值的Fst时，它是形式为新的未扩展Fst类：
ComposeFst<Arc>(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
延迟的Fst具有常量时间类构造函数。通过Fst接口访问延迟的Fst的组件时，将动态构建自动机，足以响应所请求的访问。
2.5.1.2 从Shell调用FST操作
Shell级FST操作通常读取一个或多个输入二进制FST文件，在内部调用相应的C++操作，然后写入输出二进制FST文件。
如果省略输出文件，则使用标准输出。 如果输入文件也被省略（单数形式）或为“-”，则使用标准输入。 具体来说，它们具有以下形式：
#Unary Operations:
fstunaryop in.fst out.fst
fstunaryop <in.fst >out.fst
#Binary Operations:
fstbinaryop in1.fst in2.fst out.fst
fstbinaryop - in2.fst <in1.fst >out.fst
2.5.2 FST应用
组合是最有用的有限状态运算之一，它产生两个转换的关系组合。例如，它可以用于将转换应用于某些输入。
2.5.2.1 C++ 形式
#include <fst/fstlib.h>
namespace fst {
// Reads in an input FST.
StdVectorFst *input = StdVectorFst::Read("input.fst");
// Reads in the transduction model.
StdVectorFst *model = StdVectorFst::Read("model.fst");
// The FSTs must be sorted along the dimensions they will be joined.
// In fact, only one needs to be so sorted.
// This could have instead been done for "model.fst" when it was created.
ArcSort(input, StdOLabelCompare());
ArcSort(model, StdILabelCompare());
// Container for composition result.
StdVectorFst result;
// Creates the composed FST.
Compose(*input, *model, &result);
// Just keeps the output labels.
Project(&result, PROJECT_OUTPUT);
// Writes the result FST to a file.
result.Write("result.fst");
}
2.5.2.2 shell 形式
# FSTs 在组合前必须排序，事实上，组合的任一个Fst是排序的即可
$ fstarcsort --sort_type=olabel input.fst input_sorted.fst
$ fstarcsort --sort_type=ilabel model.fst model_sorted.fst
# 创建组合FST.
$ fstcompose input_sorted.fst model_sorted.fst comp.fst
# 保留输出符号
$ fstproject --project_output comp.fst result.fst
# 用一行命令
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst
2.6 FST权重
FST中的弧上的权重是进行转换的代价。OpenFst库支持多种类型的权重-实际上，可以将满足各种属性的任何C++类用作Fst的Arc模板参数中指定的权重类型。
库中的权重的属性中，必须具有关联的二元运算⊕和⊗以及元素零元和幺元。这些由权重类型实现，该权重类型具有函数Plus(x,y)和Times(x,y)以及静态成员函数Zero()和One()。 它们必须形成一个半环。 有关这些操作的约束以及权重的其他属性，请参见此处。 ⊕用于合并两个标记相同的替代路径的权重，而⊗用于合并沿路径的权重或在合成或相交中匹配路径时的权重。
下表是一些权重类型：
| Name | Set | ⊕ (Plus) | ⊗(Times) | 0(Zero) | 1(One) |
|---|---|---|---|---|---|
| Boolean | {0, 1} | ∨ | ∧ | 0 | 1 |
| Real | [0, ∞] | + | * | 0 | 1 |
| Log | [-∞, ∞] | -log(e-x + e-y) | + | ∞ | 0 |
| Tropical | [-∞, ∞] | min | + | ∞ | 0 |
Boolean权重类型用于未加权自动机。real权重类型适用于权重表示概率时。log权重类型适用于转换权重是负log概率（在log()下，对数权重比同构数更稳定，）。热带权重类型适用于最短路径操作，并且与log权重类型相同，不同之处在于，它对Plus操作使用min。
OpenFst库预定义了TropicalWeight fst::TropicalWeightTpl和LogWeight fst::LogWeightTpl 以及相应的StdArc和LogArc。 这些权重类在作为构造函数参数的单个精度浮点数中表示其权重。可以使用成员函数Value()直接访问float值。 对于非加权自动机，在此库中方便且习惯使用限制为Zero()和One()的TropicalWeight。
从shell中，可以在fstcompile中使用--arc_type标志指定FST弧类型。 默认是StdArc。
