本篇讲解Minimization算法。
Minimization的作用是用最少的states等效表达原WFST，这样做使WFST的states数目减少，更加紧凑。算法的大体思路是获取WFST图的一个Partition，这个Partition对所有states进行分裂，最终所有等效的states在一个block里作为新的states。每个block含1个或多个states，这样最后minimize后的WFST的states数目小于等于原WFST。
算法有很多，这里以Hopcroft’s algorithm为例子做讲解。伪代码如下：
首先按照final states和非final states将所有states分为两部分，不同的final weight当然不等效， 所以然后对final states的集合根据 final weight进一步细分， 放入队列W中(line 1 - line7). 取出队列W中第一个元素，也就是一个states集合（line 9），对于每个进入states集合的转移上的input label， output label， weight，三元祖集合作为R，对于P中block B，将被R分为B1（R和B的交集）和B2（B - B1)（line12 - 14），更新P中的集合，即将B换成B1和B2（line15）如果B原本在W里，则删除B，将入B1 ，B2进队列，否则将B1和B2中较小的放入队列W中（line19 - line23），到这里完成了Partition。line 28将Q′作为partition，line 29 - line 31将对于WFST中每个转移起点终点的StateId分别换为Partition分好的Block ID。line32-line35，对新的新的States的final weight重新赋值。最后line36 输出新的WFST。
给出一个实际例子如下：