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

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

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

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

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