03馬爾可夫鏈算法

《03馬爾可夫鏈算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)是程序構(gòu)造過(guò)程的中心環(huán)節(jié)。一旦數(shù)據(jù)結(jié)構(gòu)安排好了，算法就像是瓜熟蒂落，編碼也比較容易。這種觀點(diǎn)雖然有點(diǎn)過(guò)于簡(jiǎn)單化，但也有一定道理。在數(shù)據(jù)結(jié)構(gòu)中有關(guān)各種基本數(shù)據(jù)結(jié)構(gòu)，是許多程序的基本構(gòu)件。在這一章中，我們將組合這些結(jié)構(gòu)，要完成的工作是設(shè)計(jì)和實(shí)現(xiàn)一個(gè)中等規(guī)模的程序。我們將說(shuō)明被處理的問(wèn)題將如何影響數(shù)據(jù)結(jié)構(gòu)，從這里還可以看到，一旦數(shù)據(jù)結(jié)構(gòu)安排好之后，代碼將會(huì)如何自然地隨之而來(lái)。我們要選擇的問(wèn)題并不是很常見(jiàn)的，但它在基本形式上又是非常典型的：一些數(shù)據(jù)進(jìn)去，另一些數(shù)據(jù)出來(lái)，其處理過(guò)程并不依賴于多少獨(dú)創(chuàng)性。準(zhǔn)備做的就是產(chǎn)生一些隨機(jī)的可以讀的英語(yǔ)文本。如果隨便扔出來(lái)一些隨機(jī)字母或隨機(jī)的詞，結(jié)果

2、當(dāng)然是毫無(wú)意義的。為了得到更好一些的結(jié)果，我們需要一個(gè)帶有更多內(nèi)在結(jié)構(gòu)，例如包含著各短語(yǔ)出現(xiàn)頻率的統(tǒng)計(jì)模型。但是，我們?cè)趺床拍艿玫竭@種統(tǒng)計(jì)呢？我們當(dāng)然可以抓來(lái)一大堆英語(yǔ)材料，仔細(xì)地研究。但是，實(shí)際上有一種更簡(jiǎn)單也更有意思的方法。這里有一個(gè)關(guān)鍵性的認(rèn)識(shí)：用任何一個(gè)現(xiàn)成的某種語(yǔ)言的文本，可以構(gòu)造出由這個(gè)文本中的語(yǔ)言使用情況而形成的統(tǒng)計(jì)模型。通過(guò)該模型生成的隨機(jī)文本將具有與原文本類似的統(tǒng)計(jì)性質(zhì)。1馬爾可夫鏈算法完成這種處理有一種非常漂亮的方法，那就是使用一種稱為馬爾可夫鏈算法的技術(shù)。我們可以把輸入想像成由一些互相重疊的短語(yǔ)構(gòu)成的序列，而該算法把每個(gè)短語(yǔ)分割為兩個(gè)部分：一部分是由多個(gè)詞構(gòu)成的前綴，

3、另一部分是只包含一個(gè)詞的后綴。馬爾可夫鏈算法能夠生成輸出短語(yǔ)的序列，其方法是依據(jù)(在我們的情況下)原文本的統(tǒng)計(jì)性質(zhì)，隨機(jī)性地選擇跟在前綴后面的特定后綴。采用三個(gè)詞的短語(yǔ)就能夠工作得很好——利用連續(xù)兩個(gè)詞構(gòu)成的前綴來(lái)選擇作為后綴的一個(gè)詞：設(shè)置w1和w2為文本的前兩個(gè)詞輸出w1和w2循環(huán)：隨機(jī)地選出w3，它是文本中w1w2的后綴中的一個(gè)打印w3把w1和w2分別換成w2和w3重復(fù)循環(huán)為了說(shuō)明問(wèn)題，用一個(gè)實(shí)際的例子來(lái)說(shuō)明。采用兩詞前綴，下面是一些輸入的詞對(duì)和跟隨它們之后的詞：處理這個(gè)文本的馬爾可夫算法將首先打印出Showyour，然后隨機(jī)取出flowcharts或table。如果選中了前者，那么現(xiàn)

4、在前綴就變成yourflowcharts，而下一個(gè)詞應(yīng)該是and或will。如果它選取tables，下一個(gè)詞就應(yīng)該是and。這樣繼續(xù)下去，直到產(chǎn)生出足夠多的輸出，或者在找后綴時(shí)遇到了結(jié)束標(biāo)志。程序?qū)⒆x入一段英語(yǔ)文本，并利用馬爾可夫鏈算法，基于文本中固定長(zhǎng)度的短語(yǔ)的出現(xiàn)頻率，產(chǎn)生一段新文本。前綴中詞的數(shù)目是個(gè)參數(shù)，上面用的是2。如果將前綴縮短，產(chǎn)生出來(lái)的東西將趨向于無(wú)聊詞語(yǔ)，更加缺乏內(nèi)聚力；如果加長(zhǎng)前綴，則趨向于產(chǎn)生原始輸入的逐字拷貝。對(duì)于英語(yǔ)文本而言，用兩個(gè)詞的前綴選擇第三個(gè)是一個(gè)很好的折衷方式。看起來(lái)它既能重現(xiàn)輸入的風(fēng)味，又能加上程序的古怪潤(rùn)飾。而對(duì)于中文，可以選擇更大一些。什么是一個(gè)詞

5、？最明顯的回答是字母表字符的一個(gè)序列。這里我們更愿意把標(biāo)點(diǎn)符號(hào)也附著在詞后，把“words”和“words.”看成是不同的詞，這樣做將有利于改進(jìn)閑話生成的質(zhì)量。加上標(biāo)點(diǎn)符號(hào)，以及(間接的)語(yǔ)法將影響詞的選擇，雖然這種做法也可能會(huì)產(chǎn)生不配對(duì)的引語(yǔ)和括號(hào)。我們將把“詞”定義為任何實(shí)際位于空格之間的內(nèi)容，這對(duì)輸入語(yǔ)言并沒(méi)有造成任何限制，但卻將標(biāo)點(diǎn)符號(hào)附到了詞上。許多語(yǔ)言里都有把文本分割成“空白界定的詞”的功能，這個(gè)功能也很容易自己實(shí)現(xiàn)。中文中，為了簡(jiǎn)單，以字為單位。輸入前綴跟隨的后綴詞根據(jù)這里所采用的方法，輸出中所有的詞、所有的兩詞短語(yǔ)以及所有三個(gè)詞的短語(yǔ)都必然是原來(lái)輸入中出現(xiàn)過(guò)的，但是，也會(huì)有

6、許多四個(gè)詞或更多個(gè)詞的短語(yǔ)將被組合產(chǎn)生出來(lái)。2數(shù)據(jù)結(jié)構(gòu)的選擇有多少輸入需要處理？程序應(yīng)該運(yùn)行得多快？要求程序讀完一整本書并不是不合理的，因此我們需要準(zhǔn)備對(duì)付輸入規(guī)模n=100000個(gè)詞甚至更多的情況。輸出將包括幾百甚至幾千個(gè)詞，而程序的運(yùn)行應(yīng)該在若干秒內(nèi)完成，而不是幾分鐘。假定輸入文本有100000個(gè)詞，n已經(jīng)相當(dāng)大了，因此，如果還要求程序運(yùn)行得足夠快，這個(gè)算法就不會(huì)太簡(jiǎn)單。馬爾可夫算法必須在看到了所有輸入之后才能開(kāi)始產(chǎn)生輸出。所以它必須以某種形式存儲(chǔ)整個(gè)輸入。一個(gè)可能的方式是讀完整個(gè)輸入，將它存為一個(gè)長(zhǎng)長(zhǎng)的字符串。情況的另一方面也很明顯，輸入必須被分解成詞。如果另用一個(gè)指向文本中各詞的指

7、針數(shù)組，輸出的生成將很簡(jiǎn)單：產(chǎn)生一個(gè)詞，掃描輸入中的詞，看看剛輸出的前綴有哪些可能的后綴，然后隨機(jī)選取一個(gè)。但是，這個(gè)方法意味著生成每個(gè)詞都需要掃描100000個(gè)輸入詞。1000個(gè)輸出就意味著上億次字符串比較。這樣做肯定快不了。另一種可能性是存儲(chǔ)單個(gè)的詞，給每個(gè)詞關(guān)聯(lián)一個(gè)鏈表，指出該詞在文本中的位置。這樣就可以對(duì)詞進(jìn)行快速定位。在這里可以使用第2章提出的散列表。但是，這種方式并沒(méi)有直接觸及到馬爾可夫算法的需要。在這里最需