A*解码算法与Viterbi算法不同，它将依靠完全的向前算法而不依靠近似值。另外，A*解码算法还允许我们使用任何语言模型。A*解码算法是对于格（lattice）和树（tree）的一种最佳优先搜索，而格和树隐含地定义了一种语言中可允许单词的序列。考虑图1中的树。这个树的根在左边的START结点上。这个树中的每条路径定义了该语言的一个句子；沿着从START到叶子的路径，把路径中所有的单词毗连起来，就可以形成一个句子。我们这里对于树的表示不很明显，但栈解码算法隐含地使用树作为构造解码搜索的一种手段。

算法从树的根开始向叶子进行搜索，查找概率最大的路径，而概率最大的路径就代表概率最大的句子。当我们从根向叶子进行搜索时，离开给定单词的结点的每个枝所表示的单词，可能跟随在这个当前给定的单词之后。每个这样的枝上都有概率，这个概率表示在我们前面所看到句子给定部分的条件之下，下面一个单词出现的条件概率。此外，我们将使用向前算法给每个单词指派一个产生所观察声学数据的某个部分的似然度。因此，A*解码算法必须找出从根到概率最大的叶子之间的路径（单词序列），而该路径的概率可以由语言模型的先验概率和它与声学数据匹配的似然度的乘积来确定。这可以通过保持部分路径优先队列（priority queue）的办法来实现。这个优先队列也就是句子中带有分数（score）标注的前面部分（prefix of sentence）。在一个优先队列中，每个成分都打了一个分数，上托（pop）操作返回分数高的成分。A*解码算法反复地选择最佳的句子前面部分，对于这个部分，计算它后面所有可能出现的下一个单词，把句子加以延伸，并把这些延伸了的句子加到优先队列中。图2给出了一个完全的算法。

图1 定义一种语言的可容许单词序列的隐含格的可视表示。一种语言中句子的集合很大，不可能明显地表示出来，但这个格作为一个比喻可以帮助我们探索这些句子的各种子符号串

图2 A*解码算法（Paul,1991;Jelinek,1997）修改得到。这里没有完全地定义用于计算句子分数的评估函数；可能的评估函数将在下面讨论

我们来研究A*解码算法的一个追求时尚的例子，这个例子处理的波形所对应的正确转写是半句时髦话：“If music be the food of love”（如果音乐是爱情的食粮）。图3说明了解码算法检查了从根开始的第一段长度为1的路径之后的搜索空间的情况。我们使用快速匹配（fast match）的办法来选择下面一个或多个最可能的单词。快速匹配是一种试探性的方法，用于筛选下面可能的单词的数目。在通常的情况下，要计算出前面概率的近似值（参看后面对快速匹配的讨论）。