03馬爾可夫鏈算法

1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)是程序構(gòu)造過程的中心環(huán)節(jié)。一旦數(shù)據(jù)結(jié)構(gòu)安排好了，算法就像 是瓜熟蒂落，編碼也比較容易。這種觀點(diǎn)雖然有點(diǎ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ī)模的程序。我們將說明被處理的問題將如何影響數(shù)據(jù) 結(jié)構(gòu)，從這里還可以看到，一旦數(shù)據(jù)結(jié)構(gòu)安排好之后，代碼將會如何自然地隨之而 來。我們要選擇的問題并不是很常見的，但它在基本形式上又是非常典型的：一些 數(shù)據(jù)進(jìn)去，另一些數(shù)據(jù)出來，其處理過程并不依賴于多少獨(dú)創(chuàng)性。準(zhǔn)備做的就是產(chǎn)生一些隨機(jī)的可以讀的英語文本。如果隨便扔出來一些隨機(jī)字 母或隨機(jī)

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

3、多個(gè)詞構(gòu)成的前綴，另一部分是只包含一個(gè)詞的 后綴。馬爾可夫鏈算法能夠生成輸出短語的序列，其方法是依據(jù)（在我們的情況下） 原文本的統(tǒng)計(jì)性質(zhì)，隨機(jī)性地選擇跟在前綴后面的特定后綴。采用三個(gè)詞的短語就能夠工作得很一利用連續(xù)兩個(gè)詞構(gòu)成的前綴來選擇作 為后綴的一個(gè)詞：設(shè)置W1和w2為文本的前兩個(gè)詞輸出W和W循環(huán)：隨機(jī)地選出W3，它是文本中W1W2的后綴中的一個(gè)打印W 3把W1和W2分別換成W2和W3重復(fù)循環(huán)為了說明問題，用一個(gè)實(shí)際的例子來說明。Show your flowcharts and conceal your tables and r will be mystified. Show your ta

4、bles and your flowcharts will be obvious (rnd)采用兩詞前綴，下面是一些輸入的詞對和跟隨它們之后的詞:輸入前綴Show your your flowcharts flowcharts and fl owe harts will your tables will be be mystified be obvious.跟隨的后正伺 flowcharts tables and willconcealbeand andmystified, obvious. ShowQend)處理這個(gè)文本的馬爾可夫算法將首先打印出Show your，然后隨機(jī)取出flowcha

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

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

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

8、況的另一方面也很明顯，輸入必須被分解成詞。如果另用一個(gè)指向文本中各 詞的指針數(shù)組，輸出的生成將很簡單：產(chǎn)生一個(gè)詞，掃描輸入中的詞，看看剛輸出 的前綴有哪些可能的后綴，然后隨機(jī)選取一個(gè)。但是，這個(gè)方法意味著生成每個(gè)詞 都需要掃描100000個(gè)輸入詞。1000個(gè)輸出就意味著上億次字符串比較。這樣做肯 定快不了。另一種可能性是存儲單個(gè)的詞，給每個(gè)詞關(guān)聯(lián)一個(gè)鏈表，指出該詞在文本中的 位置。這樣就可以對詞進(jìn)行快速定位。在這里可以使用第2章提出的散列表。但是， 這種方式并沒有直接觸及到馬爾可夫算法的需要。在這里最需要的是能夠由前綴出 發(fā)快速地確定對應(yīng)的后綴。我們需要有一種數(shù)據(jù)結(jié)構(gòu)，它能較好地表示前綴以及與

9、之相關(guān)聯(lián)的后綴。程序 將分兩部分，第一部分是輸入，它構(gòu)造表示短語的整個(gè)數(shù)據(jù)結(jié)構(gòu)；第二部分是隨后 的輸出，它使用這個(gè)數(shù)據(jù)結(jié)構(gòu)，生成隨機(jī)的輸出。這兩部分都需要（快速地）查詢前 綴：輸入過程中需要更新與前綴相關(guān)的后綴；輸出時(shí)需要對可能后綴做隨機(jī)選擇。 這些分析提醒我們使用一種散列結(jié)構(gòu)，其關(guān)鍵碼是前綴，其值是對應(yīng)于該前綴的所 有可能后綴的集合。為了描述的方便，我們將假定采用二詞前綴，在這種情況下，每個(gè)輸出詞都是 根據(jù)它前面的一對詞得到的。前綴中詞的個(gè)數(shù)對設(shè)計(jì)本身并沒有影響，程序應(yīng)該能 對付任意的前綴長度，但給定一個(gè)數(shù)能使下面的討論更具體些。我們把一個(gè)前綴和 它所有可能后綴的集合放在一起，稱其為一個(gè)狀態(tài)

10、，這是馬爾可夫算法的標(biāo)準(zhǔn)術(shù)語。對于一個(gè)特定前綴，我們需要存儲所有能跟隨它的后綴，以便將來取用。這些 后綴是無序的，一次一個(gè)地加進(jìn)去。我們不知道后綴將會有多少，因此，需要一種 能容易且高效地增長的數(shù)據(jù)結(jié)構(gòu)，例如鏈表或者動(dòng)態(tài)數(shù)組。在產(chǎn)生輸出的時(shí)候，我 們要能從關(guān)聯(lián)于特定前綴的后綴集合中隨機(jī)地選出一個(gè)后綴。還有，數(shù)據(jù)項(xiàng)絕不會 被刪除。如果一個(gè)短語出現(xiàn)多次，那么又該怎么辦？例如，短語might appear twicew 可能在文本里出現(xiàn)兩次，而“ might appear once ”只出現(xiàn)了一次。這個(gè)情況有兩 種可能的表示方式：或者在might appear ”的后綴表里放兩個(gè)twice ”；或者

11、是只放一個(gè)，但還要給它附帶一個(gè)計(jì)數(shù)值為2的計(jì)數(shù)器。我們對用或不用計(jì)數(shù)器的 方式都做過試驗(yàn)。不用計(jì)數(shù)器的情況處理起來比較簡單，因?yàn)樵诩尤牒缶Y時(shí)不必檢 查它是否已經(jīng)存在。試驗(yàn)說明這兩種方式在執(zhí)行時(shí)間上的差別是微不足道的?？偨Y(jié)一下：每個(gè)狀態(tài)由一個(gè)前綴和一個(gè)后綴鏈表組成。所有這些信息存在一個(gè) 散列表里，以前綴作為關(guān)鍵碼。每個(gè)前綴是一個(gè)固定大小的詞集合。如果一個(gè)后綴 在給定前綴下的出現(xiàn)多于一次，則每個(gè)出現(xiàn)都單獨(dú)包含在有關(guān)鏈表里。下面的問題是如何表示詞本身。最簡單的方法是把它們存儲為獨(dú)立的字符串。 在一般文本里總是有許多反復(fù)出現(xiàn)的詞，如果為單詞另外建一個(gè)散列表有可能節(jié)約 存儲，因?yàn)樵谶@種情況下每個(gè)詞只需要

12、存儲一次。此外，這樣做還能加快前綴散列 的速度，因?yàn)檫@時(shí)每個(gè)詞都只有一個(gè)惟一地址，可以直接比較指針而不是比較詞里 的各個(gè)字符。我們把這種做法留做練習(xí)。下面采用每個(gè)詞都分開存放的方式。3在C中構(gòu)造數(shù)據(jù)結(jié)構(gòu)現(xiàn)在開始考慮c語言中的實(shí)現(xiàn)。首先是定義一些常數(shù)：const int NPREF = 3;const int NHASH = 4093;const int MAXGEN = 10000;const int MULTIPLIER = 5;這個(gè)聲明定義了前綴中詞的個(gè)數(shù)(NPREF)，散列表數(shù)組的大小(NHASH)，生成 詞數(shù)的上界(MAXGEN)。如果NPREF是個(gè)編譯時(shí)的常數(shù)而不是運(yùn)行時(shí)的變量，程序

13、 里的存儲管理將會更簡單些。數(shù)組的規(guī)模設(shè)得相當(dāng)大，因?yàn)槲覀冾A(yù)計(jì)程序可能處理 很大的輸入文件，或許是整本書。選擇NHASH=4093，這樣，即使輸入里有10000個(gè)不同前綴(詞對)，平均鏈長 仍然會很短，大約兩個(gè)到三個(gè)前綴。數(shù)組越大，鏈的期望長度越短，查詢進(jìn)行得也越快。實(shí)際上，這個(gè)程序還仍然是個(gè)擺設(shè)，因此其性能并不那么關(guān)鍵。另一方面, 如果選用的數(shù)組太小，程序?qū)o法在合理時(shí)間里處理完可能的輸入。而如果它太大， 又可能無法放進(jìn)計(jì)算機(jī)的存儲器中。前綴可以用詞的數(shù)組的方式存儲。散列表的元素用State （狀態(tài)）數(shù)據(jù)類型表 示，它是前綴與Suffix （后綴）鏈表的關(guān)聯(lián):typedef struct S

14、tate State;typedef struct Suffix Suffix;Statechar *prefNPREF;Suffix *suf;State *next;Suffixchar *word;Suffix *next;State *statetabNHASH;現(xiàn)在看一看圖示，整個(gè)數(shù)據(jù)結(jié)構(gòu)將具有下面的樣子:我們需要一個(gè)作用于前綴的散列函數(shù)，前綴的形式是字符串?dāng)?shù)組，顯然不難對第2章的字符串散列函數(shù)做一點(diǎn)修改，使之可用于字符串的數(shù)組。下面的函數(shù)對數(shù) 組里所有字符串的拼接做散列：unsigned int hash( char *sNPREF)(unsigned int h;unsigned

15、 char *p; int i;h=0;for( i=0; inext )for( i=0; iprefi ) != 0 ) break;if( i=NPREF ) return sp;if( create )sp = (State*)malloc( sizeof(State);for( i=0; iprefi = prefixi;sp-suf = NULL;sp-next = statetabh;statetabh = sp;return sp;注意，lookup在建立新狀態(tài)時(shí)并不做輸入字符串的拷貝。它只是向 sppref里存入一個(gè)指針。這實(shí)際上要求調(diào)用lookup的程序必須保證這些數(shù) 據(jù)不

16、會被覆蓋。例如，如果字符串原來存放在I/O緩沖區(qū)里，那么在調(diào)用lookup 前必須先做一個(gè)拷貝。否則后面的輸入就會把散列表指針?biāo)傅臄?shù)據(jù)覆蓋掉。對于 跨越某個(gè)界面的共享資源，常常需要確定它的擁有者到底是誰。作為下一步，我們需要在讀入文件的同時(shí)構(gòu)造散列表：void build( char *prefixNPREF, FILE *f )char buf10;while( fscanf( f, %2s”, buf ) != EOF )/ 處理漢字add( prefix, strdup(buf);函數(shù)build有兩個(gè)參數(shù)，一個(gè)是prefix數(shù)組，用于保存前面的NPREF個(gè)輸 入詞；另一個(gè)是個(gè)FILE指

17、針。函數(shù)把prefix和讀入詞的一個(gè)拷貝送給add，該 函數(shù)在散列表里加入一個(gè)新項(xiàng)，并更新前綴數(shù)組：void add( char *prefixNPREF, char *suffix )State *sp;sp = lookup( prefix, 1 );addsuffix( sp, suffix );memmove( prefix, prefix+1, (NPREF-1)*sizeof(prefix0); prefixNPREF-1 = suffix;對memmove的調(diào)用是在數(shù)組里做刪除的一個(gè)慣用法。該操作把前綴數(shù)組里從1 到NPREF1的元素向下搬，移到從0到NPREF2的位置。這也就刪

18、去了第一個(gè) 前綴詞，并為新來的一個(gè)在后面騰出了位置。函數(shù)addsuffix把一個(gè)新后綴加進(jìn)去：void addsuffix( State *sp, char *suffix )Suffix *suf;suf = (Suffix *)malloc( sizeof(Suffix);suf-word = suffix;suf-next = sp-suf;sp-suf = suf;這里的狀態(tài)更新操作分由兩個(gè)函數(shù)實(shí)現(xiàn)：add完成給有關(guān)前綴加入一個(gè)后綴的 一般性工作，addsuffix做的是由特定實(shí)現(xiàn)方式?jīng)Q定的動(dòng)作，把一個(gè)詞具體地加 進(jìn)后綴鏈表里。函數(shù)add由build調(diào)用，而addsuffix只在add

19、內(nèi)部使用，因 為這里牽涉到的是一個(gè)實(shí)現(xiàn)細(xì)節(jié)，這個(gè)細(xì)節(jié)今后也可能會變化。所以，雖然該操作 只在這一個(gè)地方用，最好也將它建立為一個(gè)獨(dú)立的函數(shù)。4生成輸出數(shù)據(jù)結(jié)構(gòu)構(gòu)造好之后，下一步就是產(chǎn)生輸出。這里的基本思想與前面類似：給 定一個(gè)前綴，隨機(jī)地選出它的某個(gè)后綴，打印輸出并更新前綴。當(dāng)然，這里說的是 處理過程的穩(wěn)定狀態(tài)，還需要弄清算法應(yīng)該如何開始和結(jié)束。如果我們已經(jīng)記錄了 文中第一個(gè)前綴，操作就非常簡單了：直接從它們起頭。結(jié)束也容易。我們需要一 個(gè)標(biāo)志字來結(jié)束算法，在所有正常輸入完成之后，我們可以加進(jìn)一個(gè)結(jié)束符，一個(gè) 保證不會在任何輸入里出現(xiàn)的“詞”。NONWORD應(yīng)該是某個(gè)不可能在正規(guī)輸入里遇到的值。

20、由于輸入詞是由空白界定 的，一個(gè)空白的“詞”總能扮演這個(gè)角色，比如用一個(gè)換行符號“ n”我們可以用一個(gè)偽造的前綴來初始化數(shù)據(jù)結(jié)構(gòu)構(gòu)造和輸出生成過程，這樣就能 保證程序的輸入總是足夠的。在做循環(huán)準(zhǔn)備時(shí)，我們把前綴數(shù)組裝滿NONWORD詞。 這樣做有一個(gè)非常好的效果：輸入文件里的第一個(gè)詞將總是這個(gè)偽造前綴的第一個(gè) 后綴。這樣，生成循環(huán)要打印的全都是它自己生成的后綴。如果輸出非常長，我們可以在產(chǎn)生了一定數(shù)目的詞之后終止程序；另一種情況 是程序遇到了后綴NONWORD。最終看哪個(gè)情況先出現(xiàn)。在數(shù)據(jù)的最后加上幾個(gè)NONWORD,可以大大簡化程序的主處理循環(huán)。這是一種 常用技術(shù)的又一個(gè)實(shí)例：給數(shù)據(jù)加上哨衛(wèi)

21、，用以標(biāo)記數(shù)據(jù)的界限。作為編程的一個(gè)規(guī)則，我們總應(yīng)該設(shè)法處理數(shù)據(jù)中各種可能的非正常情況、意 外情況和特殊情況。編出正確代碼很不容易，因此應(yīng)該盡量使控制流簡單和規(guī)范。函數(shù)generate采用的就是前面已經(jīng)給出了輪廓的算法。它產(chǎn)生每行一個(gè)詞的 輸出，用文字處理程序可以把它們匯成長的行。借助于數(shù)據(jù)開始和結(jié)束的NONWORD串，generate也很容易開始和結(jié)束：void generate( int n )State *sp;Suffix *suf;char *prefixNPREF, *w;int i, nmatch;for( i=0; iNPREF; i+ )prefixi = NONWORD;f

22、or( i=0; isuf; suf != NULL; suf = suf-next )if( (rand() % +nmatch) = 0 )w = suf-word;if( strcmp( w, NONWORD ) = 0 )break;printf( %s ”, w );memmove( prefix, prefix+1, (NPREF-1)*sizeof(prefix0);prefixNPREF-1 = w;注意，算法需要在不知道到底有多少個(gè)項(xiàng)的情況下隨機(jī)地選取一個(gè)項(xiàng)。變量 nmatch用于在掃描后綴表的過程中記錄匹配的個(gè)數(shù)。表達(dá)式：(rand() % +nmatch) = 0增加nmatch的值，而且使它為真的概率總是1/nmatch。這樣，第一個(gè)匹配 的項(xiàng)被選中的概率為1,第二個(gè)將有1/2的概率取代它，第3個(gè)將以1/3的概率取 代前面選擇后留下的項(xiàng)，依此類推。在任何時(shí)刻，前面匹配的k個(gè)項(xiàng)中的每一個(gè)都 有1/k的被選概率。在算法開始時(shí)，prefix已經(jīng)被設(shè)為初始值，可以保證散列表中一定有它。這 樣得到的第一個(gè)suffix值就是文件里的第一個(gè)詞，因?yàn)樗歉S初始前綴的惟一 后綴。在此之后，算法隨機(jī)地選擇后綴：循環(huán)中調(diào)用lookup，查出當(dāng)前prefix 對應(yīng)的散列表項(xiàng)，然后隨機(jī)地選出一個(gè)對應(yīng)后綴，打印它并更新前綴。如果選出