王 興, 吳 藝, 林 劼, 卓一帆

1(中南大學(xué) 信息科學(xué)與工程學(xué)院,長(zhǎng)沙 410075)

2(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福州 350108)

序列數(shù)據(jù)挖掘是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)研究熱點(diǎn),序列數(shù)據(jù)廣泛存在于各個(gè)領(lǐng)域[1-3],如交通路網(wǎng)中的出租車出行軌跡序列、用戶的網(wǎng)上購(gòu)物行為序列、生物DNA序列等,如何精確且高效地建模和挖掘序列數(shù)據(jù)蘊(yùn)含的模式特征,具有重要意義. 馬爾科夫模型是一種經(jīng)典的概率統(tǒng)計(jì)模型,具有良好的統(tǒng)計(jì)特征和狀態(tài)的無(wú)后向性等優(yōu)點(diǎn),常用來(lái)對(duì)序列數(shù)據(jù)建模,進(jìn)行位置預(yù)測(cè)、用戶推薦、DNA分類等研究,該模型在實(shí)際應(yīng)用中[4,5],注重解決兩個(gè)問(wèn)題：一是模型的階長(zhǎng)問(wèn)題,二是模型實(shí)現(xiàn)的時(shí)間和空間效率問(wèn)題. 針對(duì)第一個(gè)問(wèn)題,傳統(tǒng)的固定階模型,低階模型由于未能充分使用更多的歷史狀態(tài)信息,存在精度不高問(wèn)題,高階模型隨著階數(shù)的增長(zhǎng),狀態(tài)空間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng),存在空間膨脹問(wèn)題,同時(shí)階數(shù)過(guò)高,歷史樣本數(shù)據(jù)覆蓋率低. 高階模型存在樣本數(shù)據(jù)覆蓋率不足問(wèn)題. 為了兼顧建模的精度和復(fù)雜度,學(xué)者們引入變階的思想,提出了變階馬爾科夫模型[6],能建立任意階長(zhǎng)的馬爾科夫鏈模型,根據(jù)實(shí)際情況動(dòng)態(tài)自適應(yīng)使用合適的階長(zhǎng)進(jìn)行計(jì)算,模型自提出后得到廣泛的研究[7,8]與應(yīng)用[9-11]. 對(duì)于第二個(gè)問(wèn)題,模型實(shí)現(xiàn)的效率問(wèn)題,當(dāng)前的各類研究與應(yīng)用中,一類研究側(cè)重模型的建模細(xì)節(jié)本身,未涉及具體的模型實(shí)現(xiàn),如文獻(xiàn)[12]使用變階馬爾科夫模型預(yù)測(cè)移動(dòng)位置,其實(shí)質(zhì)是一種歷史模式匹配的方法,根據(jù)最大匹配的階長(zhǎng)來(lái)使用,不能實(shí)現(xiàn)真正意義上的變階切換計(jì)算;另一類研究針對(duì)具體應(yīng)用情況給出實(shí)現(xiàn)方法,如文獻(xiàn)[13,14]給出了一種概率后綴樹(shù)的實(shí)現(xiàn)算法,解決生物序列分類問(wèn)題,但其實(shí)現(xiàn)復(fù)雜度較高,且算法需要預(yù)設(shè)模型的階長(zhǎng); 還有一類研究從純算法實(shí)現(xiàn)的角度,引入概率后綴樹(shù)數(shù)據(jù)結(jié)構(gòu)快速構(gòu)造模型[15]. 針對(duì)概率后綴樹(shù)實(shí)現(xiàn)算法時(shí)空復(fù)雜度高的問(wèn)題,文獻(xiàn)[15]從理論上證明了在線性時(shí)間與空間復(fù)雜度內(nèi)構(gòu)建概率后綴樹(shù)的可行性,可在線性時(shí)間內(nèi)構(gòu)造一個(gè)等價(jià)的自動(dòng)機(jī),而文獻(xiàn)[16]從概率后綴數(shù)組的角度提出了變階馬爾可夫模型的一種等價(jià)概率后綴樹(shù)的線性實(shí)現(xiàn).

本文針對(duì)變階馬爾科夫模型的樹(shù)結(jié)構(gòu)實(shí)現(xiàn)過(guò)程中存在的復(fù)雜度高問(wèn)題,從后綴結(jié)構(gòu)的角度,提出了基于后綴數(shù)組和后綴自動(dòng)機(jī)的變階馬爾科夫模型實(shí)現(xiàn)算法,算法借助于后綴鏈能在線性時(shí)間和空間復(fù)雜度內(nèi)構(gòu)建模型,通過(guò)對(duì)比實(shí)驗(yàn)表明,算法具有較好的效率,能夠?qū)崿F(xiàn)在線建模學(xué)習(xí)和應(yīng)用.

1 變階馬爾科夫模型

馬爾科夫模型(Markov Model,MM)是一個(gè)經(jīng)典的概率模型,假設(shè)S是一個(gè)由有限個(gè)狀態(tài)序列組成的集合. 令S={Xi,i=1,2,3},則有：

該馬爾科夫模型稱為L(zhǎng)階馬爾科夫模型. 當(dāng)前狀態(tài)序列的概率由過(guò)去的L個(gè)已知狀態(tài)序列的概率決定,L=1時(shí)為標(biāo)準(zhǔn)馬爾科夫模型.

其中,算式右邊的每項(xiàng)累乘項(xiàng),概率P的計(jì)算均對(duì)應(yīng)某階長(zhǎng)的馬爾科夫過(guò)程,如為4階模型,若樣本中未能發(fā)現(xiàn)滿足此序列的概率分布,則需調(diào)整階長(zhǎng),采用3階模型計(jì)算概率,若依然為0,則變階為2階計(jì)算,以此類推. 計(jì)算過(guò)程體現(xiàn)了變階馬爾科夫模型的靈活性.

因此,變階馬爾科夫模型需要索引各子序列的概率分布及其后綴序列之間的轉(zhuǎn)移跳轉(zhuǎn)關(guān)系,從而快速實(shí)現(xiàn)變階長(zhǎng)度的子序列概率計(jì)算.

2 變階馬爾科夫模型的實(shí)現(xiàn)

變階馬爾科夫模型擁有后綴特性,此特性使得可以用樹(shù)結(jié)構(gòu)來(lái)表示模型,在后綴結(jié)構(gòu)當(dāng)中,每個(gè)節(jié)點(diǎn)都表示一個(gè)對(duì)應(yīng)的后綴串,后綴鏈指向的是最長(zhǎng)能匹配的并且以相同后綴結(jié)尾的后綴子串的位置. 使用變階馬爾科夫模型計(jì)算序列概率時(shí),在利用后綴數(shù)據(jù)結(jié)構(gòu)構(gòu)造好的字符串上查找失配時(shí),只需要通過(guò)后綴鏈跳轉(zhuǎn)到對(duì)應(yīng)位置,實(shí)現(xiàn)快速降階計(jì)算.

本文主要提出了3種表達(dá)后綴結(jié)構(gòu)的模型及算法原理與實(shí)現(xiàn).

2.1 基于字典樹(shù)的變階馬爾科夫模型

字典樹(shù)(Trie Tree,TT)又稱單詞查找樹(shù),能充分利用字符串的公共前綴減少查詢時(shí)間,減少字符串比較,其特征為：除根節(jié)點(diǎn)為空字符,其它節(jié)點(diǎn)都表示一個(gè)字符,從根節(jié)點(diǎn)遍歷到樹(shù)上某一節(jié)點(diǎn),路徑所對(duì)應(yīng)的字符串,即為該節(jié)點(diǎn)所表示的字符串.

模型構(gòu)建過(guò)程包括兩部分：1)構(gòu)建后綴字典樹(shù),2)添加后綴鏈.

2.1.1 構(gòu)建后綴字典樹(shù)

對(duì)于長(zhǎng)度為N的字符串S,共有N個(gè)后綴串,定義Suffix(i)表示以i為開(kāi)頭的后綴串,新建一棵字典樹(shù),字典樹(shù)的每個(gè)節(jié)點(diǎn)要統(tǒng)計(jì)這個(gè)節(jié)點(diǎn)所表示的字符串出現(xiàn)次數(shù),因此每個(gè)節(jié)點(diǎn)存放一個(gè)cnt用來(lái)計(jì)數(shù). 將Suffix(1),…,Suffix(N)這N個(gè)后綴串插入到字典樹(shù)中,插入每個(gè)后綴串的同時(shí),將這個(gè)后綴串所經(jīng)過(guò)的節(jié)點(diǎn)的cnt值加1,全部后綴串插入完畢即得到一棵索引了樣本所有后綴串的字典樹(shù). 以cactt的所有后綴串為例構(gòu)造字典樹(shù),將cactt的5個(gè)后綴串全部插入,并同時(shí)計(jì)算每個(gè)節(jié)點(diǎn)的cnt值(節(jié)點(diǎn)下標(biāo)按照插入順序),如圖1所示.

圖1 cactt后綴字典樹(shù)

效率分析：長(zhǎng)度為N的字符串,共有N個(gè)后綴串,長(zhǎng)度分別為1,2,…,N,所有后綴串的字符總個(gè)數(shù)為N(N+1)/2,字典樹(shù)對(duì)于每次插入后綴串,最壞情況下需要新建該后綴串長(zhǎng)度個(gè)數(shù)的節(jié)點(diǎn),因此時(shí)間和空間復(fù)雜度均為O(N2),算法偽代碼如算法1.

2.1.2 添加后綴鏈

為了實(shí)現(xiàn)后綴序列之間的快速跳轉(zhuǎn),需要建立鏈接關(guān)系,算法思想為：每個(gè)節(jié)點(diǎn)定義一個(gè)指針slink,指向后綴鏈跳轉(zhuǎn)的節(jié)點(diǎn),利用一個(gè)隊(duì)列進(jìn)行層次遍歷,遍歷的過(guò)程不斷計(jì)算后綴鏈,通過(guò)這種順序,當(dāng)需要計(jì)算一個(gè)節(jié)點(diǎn)的后綴鏈時(shí),其父親節(jié)點(diǎn)的后綴鏈信息將已經(jīng)被計(jì)算出來(lái),而當(dāng)前節(jié)點(diǎn)表示的后綴串,前綴必然是包含了他父親節(jié)點(diǎn)所表示的后綴串的,且當(dāng)前節(jié)點(diǎn)表示的后綴串去掉第一個(gè)字符所表示的后綴串,必然也是存在的,那么可以利用父親節(jié)點(diǎn)的后綴鏈信息進(jìn)行跳轉(zhuǎn),跳轉(zhuǎn)之后進(jìn)入該字符的下一個(gè)節(jié)點(diǎn),則該節(jié)點(diǎn)即為當(dāng)前節(jié)點(diǎn)后綴鏈所要指向的節(jié)點(diǎn). cactt后綴字典樹(shù)添加后綴鏈后如圖2所示.

圖2 cactt的后綴字典樹(shù)(虛線為后綴鏈)

在算法2中,代碼第3-10行單獨(dú)處理根節(jié)點(diǎn)的兒子節(jié)點(diǎn)的后綴鏈信息,做法與第14-20行代碼基本一致.

2.2 基于后綴數(shù)組的變階馬爾可夫模型

后綴數(shù)組(Suffix Array,SA)是后綴樹(shù)的一個(gè)等價(jià)模型,在空間開(kāi)銷上優(yōu)于后綴樹(shù),常運(yùn)用于詞頻統(tǒng)計(jì)與處理字符串的后綴信息.

模型構(gòu)建過(guò)程包括兩部分：1)利用后綴數(shù)組構(gòu)造后綴樹(shù),2)添加后綴鏈.

2.2.1 后綴數(shù)組構(gòu)造后綴樹(shù)

算法思想：對(duì)于一個(gè)長(zhǎng)度為N的字符串S,先用構(gòu)造后綴數(shù)組的DC3算法,線性構(gòu)造出該字符串的后綴數(shù)組Sa,后綴最長(zhǎng)公共前綴數(shù)組Lcp,利用隊(duì)列擴(kuò)展后綴樹(shù),首先放入根節(jié)點(diǎn),表示排名[1,N]的后綴串,長(zhǎng)度為0. 每次從隊(duì)列取出一個(gè)節(jié)點(diǎn),該節(jié)點(diǎn)表示排名[l,r]的相同后綴串,長(zhǎng)度為len,此節(jié)點(diǎn)能表示該后綴串的個(gè)數(shù)為(r-l+1). 之后將區(qū)間劃分為[l,r1],[r1,r2],…,[rx,r],每個(gè)區(qū)間具有l(wèi)eni長(zhǎng)度的公共前綴,將具有相同公共前綴的區(qū)間進(jìn)行合并,并將這些區(qū)間新建一個(gè)節(jié)點(diǎn),放入隊(duì)列中繼續(xù)拓展,這樣每個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)個(gè)數(shù)就是劃分出的區(qū)間個(gè)數(shù),并且個(gè)數(shù)是不大于字符集的. 以字符串cactt為例,如圖3所示.

圖3 cactt的后綴樹(shù)結(jié)構(gòu)

1) 利用DC3算法構(gòu)造后綴數(shù)組,得到cactt的后綴數(shù)組信息,如表1所示.

表1 cactt后綴數(shù)組信息

2) 利用后綴數(shù)組統(tǒng)計(jì)得到各個(gè)排名后綴串與前一排名后綴串的最長(zhǎng)公共前綴Lcp,如表2所示.

表2 cactt最長(zhǎng)公共前綴數(shù)組信息

3) 每個(gè)節(jié)點(diǎn)表示的信息為(l,r,len),其中第一個(gè)節(jié)點(diǎn)Root(0,4,0),加入隊(duì)列處理后可拓展出3個(gè)節(jié)點(diǎn)信息,并將新的節(jié)點(diǎn)信息加入到隊(duì)列之中,節(jié)點(diǎn)信息如表3所示.

表3 結(jié)點(diǎn)及后綴信息

4) 重復(fù)步驟3),直到隊(duì)列中的不存在任何節(jié)點(diǎn),可得最終的后綴樹(shù)如圖4所示.

圖4 cactt的后綴樹(shù)

效率分析：定義字符集大小為|C|,構(gòu)造出的后綴樹(shù)的節(jié)點(diǎn)個(gè)數(shù)是O(N)級(jí)別,隊(duì)列的每次擴(kuò)展對(duì)于一個(gè)節(jié)點(diǎn)只會(huì)入隊(duì)出隊(duì)一次,每次擴(kuò)展到后繼節(jié)點(diǎn),需要做|C|次二分查找,每次效率為log(N),由于字符串的字符集較小,近似于常數(shù),因此總體時(shí)間復(fù)雜度為O(Nlog(N)),空間復(fù)雜度為O(N). 實(shí)際上,二分查找過(guò)程,可以采用線性枚舉,理論上最壞的時(shí)間復(fù)雜度退化到O(N2),實(shí)際上除了一些特殊序列(例如整個(gè)序列都是同一個(gè)字符)會(huì)達(dá)到這個(gè)最差復(fù)雜度,大部分隨機(jī)序列的構(gòu)造效率趨近于線性O(shè)(N).

代碼1,2行,通過(guò)DC3算法構(gòu)造后綴數(shù)組,再統(tǒng)計(jì)出最長(zhǎng)公共前綴; 第3-5行,建隊(duì)列并初始化root節(jié)點(diǎn)信息加入隊(duì)列; 第13-15行,查找具有公共前綴的最大區(qū)間范圍[pre,v],并計(jì)算出公共前綴長(zhǎng)度,新建節(jié)點(diǎn)信息加入至隊(duì)列當(dāng)中.

2.2.2 后綴數(shù)組添加后綴鏈

每個(gè)后綴鏈為一個(gè)二元組信息(to,len)表示在當(dāng)前節(jié)點(diǎn)失配len長(zhǎng)度時(shí),跳轉(zhuǎn)到to指針指向的節(jié)點(diǎn)位置. 其構(gòu)造思想為：利用隊(duì)列層次遍歷構(gòu)造完成的后綴樹(shù),隊(duì)列中存放元素為指向節(jié)點(diǎn)的指針u,訪問(wèn)節(jié)點(diǎn)u時(shí),判斷節(jié)點(diǎn)u的所有字符是否均已匹配完畢,如果匹配完畢,則匹配下一個(gè)節(jié)點(diǎn),否則,在當(dāng)前節(jié)點(diǎn)繼續(xù)匹配. 遍歷過(guò)程中每次利用父節(jié)點(diǎn)或者同一個(gè)節(jié)點(diǎn)上一個(gè)字符的位置,所保存的后綴鏈信息,去構(gòu)造出當(dāng)前位置的后綴鏈信息.

通過(guò)上述過(guò)程,可得cactt后綴樹(shù)每個(gè)節(jié)點(diǎn)的后綴鏈信息為表4,加入后綴鏈的cactt后綴樹(shù)結(jié)構(gòu)可見(jiàn)圖5.

表4 cactt后綴鏈信息

圖5 cactt帶后綴鏈的后綴樹(shù)(虛線為后綴鏈)

在算法4中,第3行,給根節(jié)點(diǎn)Root添加后綴鏈信息,其中-1表示無(wú)跳轉(zhuǎn)對(duì)應(yīng)節(jié)點(diǎn); 第 4行,initSlinksToRootChild函數(shù)用來(lái)初始化根節(jié)點(diǎn)的兒子節(jié)點(diǎn)的后綴鏈信息,同第8-22行代碼基本一致,不再贅述.

在字符集較大的情況下訪問(wèn)節(jié)點(diǎn)v時(shí),如果直接遍歷節(jié)點(diǎn)中的每個(gè)字符會(huì)影響算法執(zhí)行效率,為此,結(jié)合后綴樹(shù)的特點(diǎn),本文提出使用子串長(zhǎng)度匹配法來(lái)實(shí)現(xiàn)節(jié)點(diǎn)數(shù)據(jù)的訪問(wèn). 以圖4中的節(jié)點(diǎn)1為例,a失配跳轉(zhuǎn)至根節(jié)點(diǎn)0,c失配跳轉(zhuǎn)至節(jié)點(diǎn)2. 此時(shí)節(jié)點(diǎn)1還剩下tt長(zhǎng)度為2,由于節(jié)點(diǎn)5的長(zhǎng)度為2,且字符t開(kāi)頭,所以此時(shí)只需要添加一個(gè)后綴鏈即可,無(wú)需考慮結(jié)尾的t. 第8-22行代碼,從隊(duì)列中讀取當(dāng)前需要處理的節(jié)點(diǎn)位置,并遍歷所有可能的兒子節(jié)點(diǎn),為其添加后綴鏈信息. 其中g(shù)etCharIndex函數(shù)用來(lái)查找某節(jié)點(diǎn)某位置的字符.

2.3 基于后綴自動(dòng)機(jī)的變階馬爾可夫模型

后綴自動(dòng)機(jī)(Suffix Automaton,SAM)[17]是一種有向無(wú)環(huán)詞圖.

定理1. 設(shè)字符串y的長(zhǎng)度為n,st(y)為A(y)的狀態(tài)個(gè)數(shù). 對(duì)于n=0,st(y)=1; 對(duì)于n=1,st(y)=2; 對(duì)于n>1,則可以得到：

并且當(dāng)且僅當(dāng)y是abn-1(a,b是不同字符)這種形式的字符串時(shí),st(y)達(dá)到上限.

定理2. 設(shè)字符串y為非空字符串,ed(y)為A(y)的邊數(shù). 可以得到：ed(y) ≤ st(y) +n- 2.

后綴自動(dòng)機(jī)本身是一個(gè)DAG(有向無(wú)環(huán)圖),每個(gè)節(jié)點(diǎn)表示的是一些可以接收的子串,并且維護(hù)step,right,pre值：

step：表示該狀態(tài)能夠接受的最長(zhǎng)的字符串長(zhǎng)度,一個(gè)節(jié)點(diǎn)u能表示的子串在字符串中出現(xiàn)的個(gè)數(shù)為stepu-steppreu.

per：指向一個(gè)能夠表示當(dāng)前狀態(tài)表示的所有字符串的最長(zhǎng)公共后綴的節(jié)點(diǎn). 所有的狀態(tài)的pre指針構(gòu)成了一棵樹(shù),恰好是字符串的逆序的后綴樹(shù).

right：表示當(dāng)前節(jié)點(diǎn)的狀態(tài),在原字符串中的出現(xiàn)次數(shù).

2.3.1 后綴自動(dòng)機(jī)的構(gòu)造

算法思想：長(zhǎng)度為N的字符串S,遍歷字符插入到后綴自動(dòng)機(jī)中,后綴自動(dòng)機(jī)根據(jù)規(guī)則相應(yīng)新建節(jié)點(diǎn),插入后,利用一個(gè)計(jì)數(shù)排序處理出后綴自動(dòng)機(jī)中所有節(jié)點(diǎn)的拓?fù)湫?后綴自動(dòng)機(jī)的pre指針構(gòu)成DAG (有向無(wú)環(huán)圖),因此在拓?fù)湫蛏暇哂袩o(wú)后效性,統(tǒng)計(jì)出每個(gè)節(jié)點(diǎn)的right集大小. 以字符串cactt為例.

1)后綴自動(dòng)機(jī)遍歷字符串一次插入,得到cactt的后綴自動(dòng)機(jī),如圖6所示.

圖6 cactt的后綴自動(dòng)機(jī)

2)后綴自動(dòng)機(jī)中的pre指針由虛線指出,統(tǒng)計(jì)各個(gè)后綴自動(dòng)機(jī)的right集大小后,得到完整的后綴自動(dòng)機(jī),如圖7所示.

圖7 cactt的完整后綴自動(dòng)機(jī)

效率分析：后綴自動(dòng)機(jī)的插入效率是線性的,利用計(jì)數(shù)排序得到拓?fù)湫?以及得到right集大小,對(duì)于每個(gè)節(jié)點(diǎn)只會(huì)遍歷一次,因此總的時(shí)間和空間復(fù)雜度均為線性的O(|S|).

第1行代碼對(duì)后綴自動(dòng)機(jī)初始化,生成root節(jié)點(diǎn)信息; 第2-25行代碼,根據(jù)后綴自動(dòng)機(jī)的字符插入規(guī)則更新后綴自動(dòng)機(jī); 第26行代碼,對(duì)構(gòu)建的后綴自動(dòng)機(jī)中每個(gè)節(jié)點(diǎn)的step作為參考生成拓?fù)渑判驍?shù)組; 第27行代碼,按照拓?fù)渑判蚰嫦蚪y(tǒng)計(jì)出right集大小.

2.3.2 后綴自動(dòng)機(jī)添加后綴鏈

與樹(shù)形結(jié)構(gòu)的字典樹(shù)和后綴樹(shù)相比,后綴自動(dòng)機(jī)較為特殊,后綴自動(dòng)機(jī)的每個(gè)節(jié)點(diǎn)存放一些字符串可以接受的后綴串,構(gòu)造后綴自動(dòng)機(jī)時(shí)pre指針,指向與當(dāng)前節(jié)點(diǎn)所表示可以接收的公共后綴最長(zhǎng)的節(jié)點(diǎn),可以實(shí)現(xiàn)快速跳轉(zhuǎn)到下一個(gè)可以匹配的后綴串節(jié)點(diǎn),因此后綴自動(dòng)機(jī)的pre指針可以用來(lái)替代后綴鏈.

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境介紹

實(shí)驗(yàn)硬件平臺(tái)為：Intel(R) Core(TM) i5-4200H CPU 2.8 GHz (4 CPUs),內(nèi)存為12 GB. 軟件平臺(tái)為win 10,VisualStudio,C++語(yǔ)言. 實(shí)驗(yàn)DNA數(shù)據(jù)集,從http：//www.ncbi.nlm.nih.gov/(一個(gè)DNA基因數(shù)據(jù)庫(kù))中,下載幾類DNA數(shù)據(jù). 對(duì)于同一類的DNA通過(guò)拼接的方法,得到DNA長(zhǎng)度為 1000、10 000、100 000、1 000 000、10 000 000級(jí)別的樣本數(shù)據(jù).

3.2 算法時(shí)空復(fù)雜度對(duì)比

1)理論分析

根據(jù)前文對(duì)幾種不同算法的理論分析和偽代碼描述,算法的時(shí)間、空間復(fù)雜度對(duì)比情況如表5所示.

2)實(shí)驗(yàn)結(jié)果分析

分別實(shí)現(xiàn)幾種不同算法,在相同數(shù)據(jù)集下,測(cè)試結(jié)果如表6、表7及圖8至圖11所示.

表5 不同算法的時(shí)空復(fù)雜度對(duì)比

表6 不同模型訓(xùn)練耗時(shí)對(duì)比分析(單位：s)

表7 不同模型訓(xùn)練空間消耗對(duì)比分析

圖8 3種算法的時(shí)間消耗對(duì)比圖

圖9 兩種線性算法的時(shí)間消耗對(duì)比圖

圖10 3種算法的空間消耗對(duì)比圖

圖11 兩種線性算法的空消耗對(duì)比圖

通過(guò)以上圖表分析可知,由于字典樹(shù)的時(shí)空復(fù)雜度均為O(N2),隨著訓(xùn)練數(shù)據(jù)的增加,出現(xiàn)時(shí)空消耗膨脹問(wèn)題,因此字典樹(shù)構(gòu)造動(dòng)階馬爾科夫模型更適用于小數(shù)據(jù)的情形下. 后綴樹(shù)與后綴自動(dòng)機(jī)的時(shí)間空間復(fù)雜度均為線性的O(N),由于后綴樹(shù)算法過(guò)程較為復(fù)雜,過(guò)程中運(yùn)算常數(shù)較大,效率上稍微劣于后綴自動(dòng)機(jī),但是后綴樹(shù)的實(shí)現(xiàn)方式更為直觀易懂并且易于描述,并且同樣也是一個(gè)線性的實(shí)現(xiàn)方法,可作為動(dòng)階馬爾科夫模型的一個(gè)高效實(shí)現(xiàn)方法.

4 結(jié)束語(yǔ)

馬爾科夫模型是一種適用性廣的概率統(tǒng)計(jì)模型,廣泛運(yùn)用在語(yǔ)音識(shí)別、生物序列分析、位置預(yù)測(cè)等領(lǐng)域,具有重要意義. 本文分析了傳統(tǒng)馬爾科夫模型存在的局限性,對(duì)相關(guān)理論知識(shí)進(jìn)行研究探討,從后綴結(jié)構(gòu)的角度,提出了基于后綴數(shù)組和后綴自動(dòng)機(jī)的變階馬爾科夫模型實(shí)現(xiàn)算法,給出了算法的設(shè)計(jì)思想和復(fù)雜度分析過(guò)程,以DNA數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)表明,算法能在線性時(shí)間和空間復(fù)雜度內(nèi)構(gòu)建模型,有效解決傳統(tǒng)馬爾科夫高階模型狀態(tài)空間膨脹問(wèn)題,具有較好的效率,能為在線建模學(xué)習(xí)和應(yīng)用提供解決方案. 下一步工作將從兩個(gè)方面展開(kāi)研究,一方面是將模型應(yīng)用到相關(guān)的領(lǐng)域,如交通數(shù)據(jù)處理,購(gòu)物模式,公眾出行規(guī)律研究等. 另一方面是從大數(shù)據(jù)建模的角度,引入分布式計(jì)算平臺(tái),實(shí)現(xiàn)基于Hadoop和Spark框架下的并行計(jì)算算法,進(jìn)一步提高算法的計(jì)算能力,為大規(guī)模的數(shù)據(jù)挖掘和分析提供基礎(chǔ).

1 Wang BN,Hu YH,Shou GC,et al. Trajectory prediction in campus based on Markov chains. In：Wang Y,Yu G,Zhang YY,et al. eds. Big Data Computing and Communications.Cham：Springer,2016.

2 Illescas G,Martínez M,Mora-Soto A,et al. How to think like a data scientist：Application of a variable order Markov model to indicators management. In：Mejia J,Munoz M,Rocha á,et al. eds. Trends and Applications in Software Engineering. Cham：Springer,2016.

3 Goreac D,Kobylanski M,Martinez M. A piecewise deterministic Markov toy model for traffic/maintenance and associated Hamilton-Jacobi integrodifferential systems on networks. Applied Mathematics & Optimization,2016,74(2)：375-421.

4 Asahara A,Maruyama K,Sato A,et al. Pedestrianmovement prediction based on mixed Markov-chain model.Proceedings of the 19 th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago,IL,USA. 2011. 25-33.

5 Gambs S,Killijian MO,del Prado Cortez MN. Next place prediction using mobility Markov chains. Proceedings of the 1st Workshop on Measurement,Privacy,and Mobility. Bern,Switzerland. 2012. 3.

6 Rissanen J. A universal data compression system. IEEE Transactions on Information Theory,1983,29(5)：656-664.[doi：10.1109/TIT.1983.1056741]

7 Ron D,Singer Y,Tishby N. Learning probabilistic automata with variable memory length. Proceedings of the 7 th Annual Conference on Computational Learning Theory. New Brunswick,NJ,USA. 1994. 35-46.

8 Chin YS,Chen TL. Minimizing variable selection criteria by Markov chain Monte Carlo. Computational Statistics,2016,31(4)：1263-1286. [doi：10.1007/s00180-016-0649-3]

9 Melikov AZ,Ponomarenko LA,Bagirova SA. Markov models of queueing-inventory systems with variable order size. Cybernetics and Systems Analysis,2017,53(3)：373-386. [doi：10.1007/s10559-017-9937-3]

10 Nagata Y. Population diversity measures based on variableorder Markov models for the traveling salesman problem.Proceedings of the 14 th International Conference on Parallel Problem Solving from Nature. Edinburgh,UK. 2016.973-983.

11 Mao B,Cao J,Wu ZA,et al. Predicting driving direction with weighted Markov model. In：Zhou SG,Zhang SM,Karypis G,eds. Advanced Data Mining and Applications.Berlin Heidelberg：Springer,2012. 407-418.

12 Chen M,Liu Y,Yu XH. Predicting next locations with object clustering and trajectory clustering. In：Cao T,Lim EP,Zhou ZH,et al. eds. Advances in Knowledge Discovery and Data Mining. Cham：Springer,2015. 344-356.

13 Bejerano G,Yona G. Variations on probabilistic suffix trees：Statistical modeling and prediction of protein families.Bioinformatics,2001,17(1)：23-43. [doi：10.1093/bioinfor matics/17.1.23]

14 Leonardi FG. A generalization of the PST algorithm：Modeling the sparse nature of protein sequences. Bioinformatics,2006,22(11)：1302-1307. [doi：10.1093/bioin formatics/btl088]

15 Apostolico A,Bejerano G. Optimal amnesic probabilistic automata or how to learn and classify proteins in linear time and space. Journal of Computational Biology,2004,7(3-4)：381-393.

16 Lin J,Adjeroh D,Jiang BH. Probabilistic suffix array：Efficient modeling and prediction of protein families.Bioinformatics,2012,28(10)：1314-1323. [doi：10.1093/bioin formatics/bts121]

17 Lothaire M. Applied Combinatorics on Words. Cambridge：Cambridge University Press,2005.