A*解碼算法與Viterbi算法不同，它將依靠完全的向前算法而不依靠近似值。另外，A*解碼算法還允許我們使用任何語言模型。A*解碼算法是對于格（lattice）和樹（tree）的一種最佳優(yōu)先搜索，而格和樹隱含地定義了一種語言中可允許單詞的序列?？紤]圖1中的樹。這個樹的根在左邊的START結點上。這個樹中的每條路徑定義了該語言的一個句子；沿著從START到葉子的路徑，把路徑中所有的單詞毗連起來，就可以形成一個句子。我們這里對于樹的表示不很明顯，但棧解碼算法隱含地使用樹作為構造解碼搜索的一種手段。

算法從樹的根開始向葉子進行搜索，查找概率最大的路徑，而概率最大的路徑就代表概率最大的句子。當我們從根向葉子進行搜索時，離開給定單詞的結點的每個枝所表示的單詞，可能跟隨在這個當前給定的單詞之后。每個這樣的枝上都有概率，這個概率表示在我們前面所看到句子給定部分的條件之下，下面一個單詞出現(xiàn)的條件概率。此外，我們將使用向前算法給每個單詞指派一個產生所觀察聲學數(shù)據(jù)的某個部分的似然度。因此，A*解碼算法必須找出從根到概率最大的葉子之間的路徑（單詞序列），而該路徑的概率可以由語言模型的先驗概率和它與聲學數(shù)據(jù)匹配的似然度的乘積來確定。這可以通過保持部分路徑優(yōu)先隊列（priority queue）的辦法來實現(xiàn)。這個優(yōu)先隊列也就是句子中帶有分數(shù)（score）標注的前面部分（prefix of sentence）。在一個優(yōu)先隊列中，每個成分都打了一個分數(shù)，上托（pop）操作返回分數(shù)高的成分。A*解碼算法反復地選擇最佳的句子前面部分，對于這個部分，計算它后面所有可能出現(xiàn)的下一個單詞，把句子加以延伸，并把這些延伸了的句子加到優(yōu)先隊列中。圖2給出了一個完全的算法。

圖1 定義一種語言的可容許單詞序列的隱含格的可視表示。一種語言中句子的集合很大，不可能明顯地表示出來，但這個格作為一個比喻可以幫助我們探索這些句子的各種子符號串

圖2 A*解碼算法（Paul,1991;Jelinek,1997）修改得到。這里沒有完全地定義用于計算句子分數(shù)的評估函數(shù)；可能的評估函數(shù)將在下面討論

我們來研究A*解碼算法的一個追求時尚的例子，這個例子處理的波形所對應的正確轉寫是半句時髦話：“If music be the food of love”（如果音樂是愛情的食糧）。圖3說明了解碼算法檢查了從根開始的第一段長度為1的路徑之后的搜索空間的情況。我們使用快速匹配（fast match）的辦法來選擇下面一個或多個最可能的單詞?？焖倨ヅ涫且环N試探性的方法，用于篩選下面可能的單詞的數(shù)目。在通常的情況下，要計算出前面概率的近似值（參看后面對快速匹配的討論）。