FST(Finite State Transducers, 有限状态转换器)简介及示例

大家好，欢迎来到IT知识分享网。

一、简介

二、相关概念

有限自动机（Finite Automata, FA） 是由一组有限的状态和状态转移的集合组成，其每一个转移都至少有一个标签。最基本的FA是有限状态接收器（Finite State Acceptor，FSA）。对于给定的输入序列，FSA返回“接收”或者“不接收”两种状态。

图1（a）是一个FSA的示例，其节点和弧分别对应状态与状态的转移。例如，FSA可通过0,1,1,2,5接收一个符号序列“a,b,c,d”，但是无法接收到“a,b,d”序列，因此FSA表示了一组能被接收到的符号序列集合。图1（a）的FSA对应于正则表达式ab*cd|bcd*。我们假设状态0代表初始状态，状态5代表终止状态，如果不特别指出，本文中粗线单线圆代表初始状态，细线双线圆代表终止状态。
有限状态转移器（Finite State Transducers, FST） 是FSA的扩展，其每一次状态转移时都有一个输出标签，叫做输入输出标签对，如图1（b）就是一个FST的例子。通过这样的标签对，FST可描述一组规则的转换或一组符号序列到另一组符号序列的转换。图1（b）的FST将符号序列“a,b,c,d”转换为另一个符号序列“z,y,x,w”。
加权有限状态接收机（Weighted Finite-State Acceptors, WFSA） 在每一次状态转移时都有一个权重，在每次的初始状态都有初始权重，在每次的终止状态都有终止权重，权重一般是转移或初始/终止状态的概率或损失，权重会延每条路径进行累积，并在不同路径进行累加。图1（c）是一个WFSA的例子，每次状态转移的权重表示为“输入-标签/权重”，而初始和终止状态的权重表示为“状态 数量/权重”，在上图中，初始状态0的初始权重为0.5，终止状态5的终止权重为0.1。例如，上图中的WFSA沿着转移状态“0,1,1,2,5”以累积权重0.51.20.732*0.1=0.252接收到一个序列“a,b,c,d”。
加权有限状态转移器（Weighted Finite-State Transducers, WFST） 在每次状态转移时同时具有输出标签和权重，同时具有FST和WFSA的特性，图1（d）是一个WFST的例子，这里每次的状态转移标签都以“输入-标签: 输出-标签/权重”的形式进行转移，初始和终止状态也相应的分类了权重。在该图中的WFST，将符号序列“a,b,c,d”以0.252的累积权重转换为序列“z,y,x,w”。
WFST通过一个8元组 (∑,Λ,Q,I,F,E,λ,ρ) 定义：

通过以上定义，图1（d）的WFST可以被定义如下：

其中 E 中的每次转移由（源状态，输入标签，输出标签，权重，目标状态）组成，可以从以上描述中可知，FSA, FST, WFSA都是WFST的特殊形式，这些形式也可以由上述相似的元组表示。

三、创建和存储FST举例

如果当前节点存在含此label的边，则 如果Value包含该边的out值，则 Value = Value – out 否则 令temp=out–Value； out =Value并使下一个节点的所有边out都加上temp。 如果下一节点是Final节点 则FinalOut += temp 进入下一个节点 否则： 新建一个节点令其out = Value， Value = 0。 

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

四、在NLP中的FST的创建举例

FST在一些NLP task里面特别有用，比如说我给出以下三个规则：

1. 当c后紧接x时，将c变为b cx→bx
2. 当a前面是rs时，将a变为b rsa→rsb
3. 当b前面是rs，后面是xy时,将b变为a rsbxy→rsaxy

所以当我们的input string是rsaxyrscxy时，根据以上三个规则，我们就可以做出以下的变换：

rsaxyrscxy→rsaxyrsbxy rsaxyrsbxy→rsbxyrsbxy rsbxyrsbxy→rsaxyrsaxy