现实任务中，我们得到的大量信息都具有很高的不确定性，比如语言识别的结果取N-best的lattice网络，其中就包括了N种可能的带权序列。在对这种不确定信息的检索不同于以往确定信息中的检索模式（显然是权值相关的）。
我们可以将这些不确定的序列统一的用一个加权自动机（状态节点和带权的转移边）表示，那么这个问题就可以抽象成一个对加权自动机的索引构造算法。
提前弄清楚一个概念，之前也说过，因子（factor）。可以简单的理解成子串，前缀（prefix）或者后缀（suffix）都是因子。这种索引算法可以看成是后缀自动机和因子自动机的一种泛化。加权自动机索引构造的主要思想是：
对于$n$个句子，每个句子$u_i$可以用一个带权自动机$A_i$表示（其实就是解码的lattice）。可以构建一个带权转换器$T$，这个转换器可以检出这些自动机集合${A_1, A_2, \dots, A_n}$所接受的所有字符的因子。比如给出一个因子$x$，转换器$T$可以给出$x$出现的自动机集合下标和在对应的自动机中出现期望（的负log）：
其中$P_i$是$A_i$的概率分布，$C_x$是因子$x$在$u_i$中出现的次数。
由于是WFST框架，符号定义在WFST入门中已经说明了。索引构造的思想很简单，和后缀自动机十分类似，其中的很多优化过程直接使用WFST的标准操作就OK。主要分为两步骤，依次处理$A_i \to T_i$，最后$T = \bigcup T_i$即可。对于第一步，为自动机接受的字符的每一个后缀建立一条转移路径，路径输出是自动机的下标和对应的权值，输入就是后缀。权值通过前向-后向算法进行：
定义$A_i$中状态$q$的前向和后向概率是$f_i[q], b_i[q]$：
那么，因子$x$在$T_i$中出现的概率表示为：
$A_i \to T_i$分为如下几步：
- 预处理：对$A_i$进行weight-push转换为$B_i$
- 因子选择：因为$B_i$还是一个acceptor，没有输出，所以先将$B_i$中每条弧的输出初始化为$\epsilon$，之后新增初始节点$s_i$和终止节点$e_i$，为$B_i$中的每一个状态$q$增加两条弧$(s_i, \epsilon, \epsilon, d_i[q], q)$和$(q, \epsilon, i, f_i[q], e_i)$
- 优化操作，即$\epsilon$-remove，确定化和最小化
$T_i$的输出信息只有下标$i$，所以将它放在终止边上就行。第三步的优化操作得到和原先等价的转换器，只是在空间复杂度更低，搜索效率更高。得到$T_i$之后，通过$T = \bigcup T_i$和进一步的确定化，得到最终整体的索引转换器。用户的查询表示可以用自动机$X$表示，查询结果$R$有下式给出：
举个例子，在论文General Suffix Automaton Construction Algorithm and Space Bounds中实现了从String Acceptor到后缀自动机的通用构造算法，得到后缀自动机之后，将每一个状态设置为final，再执行一些简化操作就可以得到因子自动机了（acceptor），只是没有权值信息。实际上这个构造过程也可以用上面的方式进行，原文给出的例子如下：
按照上面的流程，先对左边的Acceptor进行因子选择：
由于加入的都是$\epsilon$边，所以因子选择实际上构建出了对输入自动机接受的字符串集合的所有因子的索引，只是不够简化而已，接下来对其进行简化操（等价操作）就可以得到最终的索引自动机。首先去除$\epsilon$边。
上面的结果不是确定的，执行确定化操作：
这个结果实际上就是将后缀自动机的每一个状态设为final之后的结果，但是还有优化空间，最小化之后得到最终的形式：
查询操作可以抽象为Compose操作，比如给出$cab$子串，查询结果为$cab$，如果是$cdb$，那么查询结果为$\epsilon$，表示子串不存在。
以上说明没有考虑权值，加权因子索引构造的因子选择是要在$\epsilon$边上加上权值信息的，权值信息可由前向-后向算法完成。
最后说一下TFT，整体看来kaldi-kws的TFT时间因子转换器完全继承了这套方法的衣钵，理解这部分之后再看TFT就相对容易一些。而且这个框架在论文中也提到，具有很高的通用性。TFT的修正在于，1) 将时间间隔信息带入权值之中，以便给出关键词出现的时间区间，2) 加入了聚类标识符，索引不相交的因子。