Introduction

网格(lattice)是某个特定语句的最可能的可选词序列的表示。为了更好地理解网格，你应该了解 WFST框架下的解码图（见 Decoding graph construction in Kaldi）。本节中我们概述 Kaldi网格的相关问题，并在本页后面的部分详细地解释它们。读者可能也想读这一篇文献“Generating exact lattices in the WFST framework”, D.Povey, M.Hannemann et.al, ICASSP 2012 (submitted)，其中给出了更多网格是如何与以前的算法相联系的内容。本页更侧重于编程的方面。

Kaldi 中的网格有两种表示。第一种是 Lattice。这是一个FST，权重包含两个浮点权值（图代价(the graph cost)和声学代价(the acoustic cost)），输入符号是 transition-ids （近似于上下文无关的 HMM状态），输出符号是词（一般来讲，它们表示解码图的输出符号）。

第二种是 CompactLattice。它本质上包含了和 Lattice相同的信息，但是形式不同：它是一个 acceptor（意味着输出输出符号始终相同），输出输出符号代表词，而 transition-ids序列作为了权重的一部分（注意 OpenFst有一个很通用的权重概念；满足半环公理的都可以作为权值）。CompactLattice 中的权重包括一对浮点数和一个整数序列（代表 transition-ids）。我们会在后面描述半环。

因为 Lattice和 CompactLattice都代表同样的信息，它们在 I/O意义上是等价的，即读 Lattice的代码也可以读 CompactLattice，反之亦然。举例来说，如果用SequentialLatticeReader来读由 utterance-id索引的 lattice集合，不论 archive中实际上是 Lattice还是 CompactLattice，处理上都是一样的。然而，我们通常把 lattices写出为 CompactLattice。对于需要在两者之间进行转换的程序，可以使用 ConvertLattice()。

Lattice和 CompactLattice类型中的权重包括两个浮点数，即 graph cost和 acoustic cost。graph cost是 LM代价，（加权）转移概率和任何发音代价的和。它们被混在了一起，所以在做 LM重打分时，我们先要减去旧的 LM代价再加上新的 LM代价。如果我们把这两个浮点数叫做 (a,b)，Lattice中的半环像字典半环 (a+b,a-b)（见 OpenFst文档中的解释）。 也就是说，当我们“加”（在半环中）这样的两对儿数时，我们得到具有最低 (graph + acoustic) cost的一对，如果它们相等，选用 (graph - acoustic)来打破平局。这在“取最优路径”的意义上是合理的。实际上，它只有在 acoustic weights适当缩放时才是合理的。我们的惯例是在外部存储（e.g. 磁盘）时，acoustic costs不缩放，在算法比较权重时应用缩放（在写出 lattice时再缩放回来）。

Lattice 和 CompactLattice类型被当做数据结构来表示传统的网格，也用于表示 N-best列表。生成网格的算法有很精确的特性。设定 lattice-delta为一个数值（通常为10左右）。网格生成算法可保证（modulo beam pruning）每个词序列的最优对齐的代价，在当前网格中最优路径的 lattice-delta范围内，而且是具有最可能的对齐和权值。同时，每个词序列只在网格中出现一次。要达到这一点，首先创建一个状态级的网格然后适当剪枝(pruning)，然后用一个特殊的半环 determinize（或者，如果你愿意，可以认为这是一个总是选择最可能路径的 non-functional FSTs的特殊 determinization算法）。下面我们会解释这是如何实现的。

我们始终确保写出到磁盘的网格，每个词序列只有一条路径。这对某些算法（如 LM重打分）是必要的。Being determinized (on the word labels, in the CompactLattice format) is a sufficient condition for this.

我们从不在 Kaldi代码中附加符号表给 FSTs。为了查看包含实际词的最自然的形式的网格的 archives，我们用脚本来完成这一转换（例子见 egs/rm/s1/steps/decode_tri1_latgen.sh）