这几天生病了，很难受，更新的事情搁置了几天。

言归正传，之前建议大家看Mohri的paper因为那是Kaldi官网WFST那一章的作者推荐的，但是现在发现有一本更好的书推荐给大家，这本书深入浅出，讲的更详细，更适合入门的人，尤其是WFST是怎么用在语音识别中的部分讲的特别棒。还有这本书的作者好像是个日本人，所以文笔很适合我们亚洲人的思维。下面是这本书的封面，强力推荐给想入门语音识别解码部分的童鞋。

上一章节主要介绍了半环（semiring）理论和WFST的一些基础概念，本章节介绍Composition算法。
Composition是WFST中最最重要的算法，它是将两个不同级的WFST进行组合，举个例子，语音识别中发音词典的WFST是音素对词的映射，而语言模型的WFST是词对受语法约束的词的映射，那么两个WFST进行Composition后就变成了音素对受语法约束的词的映射。那么其实语音识别的WFST的最基本的框架也很简单，就是HCLG四个不同级的WFST进行依次Composition最后形成了HMM的状态对受语法约束的词的映射。（当然实际不可能这么简单啦，还有很多优化的操作，这个后面几章会详细得介绍，这里不多说）

我们先来看一下Composition的效果，图（a）和图（b）Composition后生成了图（c），从这么简单的效果图我们大致可以看出来其实这个操作就是找出满足下面这个条件的转移：第一个WFST的某个转移上的输出标签等于第二个WFST的某个转移上的输入标签，然后把这些转移上的label和weight分别进行操作：

当然上面的大白话肯定是不严谨、不完全正确的，下面我们将结合下伪代码来介绍正确的生成方式。需要注意的是，这里是一个epsilon-free的算法，即第一个WFST的任意转移上的输出label不能为空（ε<script type="math/tex" id="MathJax-Element-4089">\varepsilon</script>）并且第二个WFST的任意转移上的输入label也不能为空（ε<script type="math/tex" id="MathJax-Element-4090">\varepsilon</script>）。

这个算法使用了一个队列S，它的特点数据结构中都学过——先进先出；
对两个WFST T1和T2：
第1行第2行把两个WFST的初始状态赋给Q和S，
Q用来统计出现过的所有状态对的集合，
S用来记录此时的状态对能达到的所有状态对的集合；
第3行如果S不为空，则执行下面4到16行的代码：
第4行第5行把队列S的头元素赋给状态对（q1，q2），删除该元素，刚开始肯定是初始状态对，所以肯定会执行第6到8行；
第6到11行是为了判断一下是否为初始状态和结束状态；
第12到16行是核心部分：
找出所有离开T1中:状态q1的所有转移和离开T2中的状态q2的所有转移，并且对比T1的这些转移的输出label是否等于T2的这些转移的输入label（o[e1]=i[e2]<script type="math/tex" id="MathJax-Element-4091">o[e_1]=i[e_2]</script>），
如果等于的话则则判断他们的目的状态是否在Q中（之前说了Q是统计所有出现过的状态，那么此时的含义就是判断是否出现了新状态），
如果是新状态的话则将它加入到Q和S的集合中，
然后完成16行compostion的操作，状态对（q1，q2）到状态对（n[e1],n[e2]<script type="math/tex" id="MathJax-Element-4092">n[e_1],n[e_2]</script>）的转移，转移上的输入标签是i[e1]<script type="math/tex" id="MathJax-Element-4093">i[e_1]</script>，输出标签是o[e2]<script type="math/tex" id="MathJax-Element-4094">o[e_2]</script>，权重是w[e1]⨂w[e2]<script type="math/tex" id="MathJax-Element-4095">w[e_1]\bigotimes w[e_2]</script>，⨂<script type="math/tex" id="MathJax-Element-4096">\bigotimes </script>这个操作第一章讲过了，那么如果是Tropical半环（语音识别中一般用这个）的话即为权重值相加。
如果不是新状态的话则直接完成16行composition的操作。

下图做了个流程的示范，笔写比较方便一点。其实只要认真看懂了上面的伪代码这边就可以跳过不看了。

接下来我们考虑更一般的情况就是包括epsilons的情况，我们需要对它进行特殊的处理，即把T1中转移上输出标签为ε<script type="math/tex" id="MathJax-Element-4097">\varepsilon</script>的符号统一换为εo<script type="math/tex" id="MathJax-Element-4098">\varepsilon_o</script>并且把每个状态加上一个自循环（self-loop），转移路径上的标签为ε：εi<script type="math/tex" id="MathJax-Element-4099">\varepsilon：\varepsilon_i</script>；把T2中转移上输入标签为ε<script type="math/tex" id="MathJax-Element-4100">\varepsilon</script>的符号统一换为εi<script type="math/tex" id="MathJax-Element-4101">\varepsilon_i</script>，并且同样地把每个状态加上一个自循环（self-loop），转移路径上的标签为εo：ε<script type="math/tex" id="MathJax-Element-4102">\varepsilon_o：\varepsilon</script>，如下图所示：

我们把εi,εo<script type="math/tex" id="MathJax-Element-4103">\varepsilon_i,\varepsilon_o</script>看作是常规的符号，那么就可以进行composition的操作了，但是这样会产生冗余的路径（redundant paths），我们引入了filter的概念来解决这个问题，即设计一个叫filter的WFST——F，然后先把WFST T1和F进行Composition，接着把产生的结果再和T2进行Composition，如下图所示：

2状态的filter和3状态的filter的选择是根据我们的需求来的：如果我们想要空转移的数目和原来相同的话我们就选择2状态，如果我们想要一个更简化的WFST的话我们就选择3状态的。

好了，这就是WFST中的最基本的Composition操作，下一章将会介绍WFST的优化，这在语音识别中是非常重要的，可以减小计算机的负担。