字符串匹配算法new

計(jì)算機(jī)技術(shù)與軟件學(xué)院王佰玲信息內(nèi)容平安技術(shù)第6章信息內(nèi)容平安處理——字符串匹配算法本章內(nèi)容6.1信息處理技術(shù)背景6.2串匹配算法概念6.3模式匹配算法分類單模式匹配算法BF算法KMP算法BM算法多模式匹配算法AC算法Agrep算法6.1.1字符串匹配與信息處理數(shù)據(jù)經(jīng)過(guò)高性能數(shù)據(jù)捕包和協(xié)議分析與復(fù)原之后,就可以復(fù)原成相應(yīng)的內(nèi)容。例如,如果捕獲到的數(shù)據(jù)經(jīng)過(guò)協(xié)議的復(fù)原,成為一個(gè)完整的網(wǎng)頁(yè)；經(jīng)過(guò)smtp協(xié)議復(fù)原后成為一封完整的郵件；之后，根據(jù)需要進(jìn)行相應(yīng)的分析,即使用字符串匹配技術(shù)串匹配〔stringmatching〕，也叫模式匹配〔patternmatching〕，可以簡(jiǎn)單地定義為在給定的字符流中查找出滿足某些指定屬性的字符串。這是計(jì)算機(jī)科學(xué)中最古老也最普遍的問(wèn)題之一，計(jì)算機(jī)科學(xué)中串匹配的應(yīng)用可以說(shuō)隨處可見(jiàn)。近年來(lái)，隨著計(jì)算機(jī)技術(shù)〔各種應(yīng)用〕的蓬勃開展，尤其是信息檢索和生物計(jì)算領(lǐng)域中的許多共同需求，極大激發(fā)了人們對(duì)串匹配算法的研究興趣。大概我們最熟悉的應(yīng)用是文本編輯中所使用的查找替換，這是一種最簡(jiǎn)單的串匹配問(wèn)題。6.1.2串匹配應(yīng)用背景在生物計(jì)算領(lǐng)域在一個(gè)DNA鏈上查找某些特定特征，或者比較兩個(gè)基因序列有多大差異，可以簡(jiǎn)單地歸結(jié)為在“文本〞中查找特定的“模式〞的串匹配問(wèn)題。在信號(hào)處理領(lǐng)域語(yǔ)音識(shí)別的一般情形可以大致描述為確定一個(gè)語(yǔ)音信號(hào)是否符合某些特征。只要事先把語(yǔ)音信號(hào)轉(zhuǎn)化為特定形式的數(shù)字信息，就可以應(yīng)用串匹配算法來(lái)解決識(shí)別問(wèn)題。6.1.2串匹配應(yīng)用領(lǐng)域在自然語(yǔ)言處理方面信息檢索在網(wǎng)絡(luò)平安方面發(fā)現(xiàn)具有某些特征碼的有害信息病毒和入侵檢測(cè)NID〔NetworkIntrusionDetection〕串匹配問(wèn)題不僅在各種實(shí)際應(yīng)用中有著廣泛的需要，而且在計(jì)算機(jī)理論研究中也占有著十分重要的地位，它可以不斷地提出非常具有挑戰(zhàn)性的理論問(wèn)題。6.1.2串匹配應(yīng)用領(lǐng)域(cont.)本章內(nèi)容6.1信息處理技術(shù)背景6.2串匹配算法概念6.3模式匹配算法分類單模式匹配算法BF算法KMP算法BM算法多模式匹配算法AC算法Agrep算法文本：由假設(shè)干個(gè)字符組成的有限序列，設(shè)為y={y1y2y3…yn},其中n為文本長(zhǎng)度，即文本中總的字符個(gè)數(shù)。模式：也稱為關(guān)鍵字，由假設(shè)干個(gè)字符組成的有限序列k={k1k2k3…km}，其中m為模式長(zhǎng)度，即模式中字符總數(shù)。模式集：指所有需要匹配的模式形成的集合，記為P={p1,p2,p3,…,pr}，其中pi是模式集中第i個(gè)模式。記模式集中所有模式長(zhǎng)度的總和為|P|。最小模式長(zhǎng)度：假設(shè)模式集中各個(gè)模式長(zhǎng)度分別為l1,l2,…lr,那么最小模式長(zhǎng)度是指所有模式長(zhǎng)度的最小值，即minlen=min{l1,l2,…lr}。前綴：兩個(gè)字符串p和x，假設(shè)存在字符串v〔v可為空串〕，使得p=xv成立，稱x為p的前綴。6.2.1串匹配概念6.后綴：兩個(gè)字符串p和x,假設(shè)存在字符串u〔u可為空串〕,使得p=ux成立，稱x為p的后綴。7.子串：兩個(gè)字符串p和x,假設(shè)存在字符串u,v〔u,v可以為空串〕，使得p=uxv成立，稱x為p的子串。8.字符集：在模式或文本中所有可能出現(xiàn)的字符形成的集合，記為Σ，其大小記為|Σ|。6.2.1串匹配概念(cont.)6.2.2模式匹配的分類模式匹配的模式數(shù)目單模式多模式匹配方式精確匹配近似匹配匹配的具體內(nèi)容單詞匹配字符類匹配正則表達(dá)匹配文本的角度實(shí)時(shí)(on-line)文本:文本可以動(dòng)態(tài)地更新例如:網(wǎng)絡(luò)入侵監(jiān)測(cè)非實(shí)時(shí)(off-line)文本:被查找文本是靜態(tài)的例如:搜索引擎中查找的數(shù)據(jù)6.2.2模式匹配的分類單模式匹配單模式匹配可定義為：在一個(gè)文本text(設(shè)長(zhǎng)度為n)中查找某個(gè)特定的子串pattern(設(shè)長(zhǎng)度為m)。如果在text中找到等于pattern的子串，那么稱匹配成功，函數(shù)返回pattern在text中出現(xiàn)的位置(或序號(hào))，否那么匹配失敗。多模式匹配多模式匹配可定義為：在一個(gè)文本text(設(shè)長(zhǎng)度為n)中查找某些特定的子串patterns(設(shè)長(zhǎng)度為m)。如果在text中找到等于patterns中的某些子串，那么稱匹配成功，函數(shù)返回pattern在text中出現(xiàn)的位置(或序號(hào))，否那么匹配失敗。6.2.3單模匹配vs多模匹配本章內(nèi)容6.1信息處理技術(shù)背景6.2串匹配算法概念6.3模式匹配算法分類單模式匹配算法BF算法KMP算法BM算法多模式匹配算法AC算法Agrep算法單模式匹配算法——BF算法BF〔Brute-Force〕算法(又稱Naive算法)是最早出現(xiàn)的單關(guān)鍵字匹配算法思想簡(jiǎn)單理論上的時(shí)間復(fù)雜度很差實(shí)際使用效果尚可ANSIC中提供的strstr函數(shù)就是使用這種算法的改進(jìn)版本。由于BF算法掃描字符串時(shí)常常需要回溯，這樣當(dāng)文本難于隨機(jī)訪問(wèn)時(shí)，就顯得特別不方便。單模式匹配算法——BF算法主要思想：BF算法是出現(xiàn)最早的一種算法，其思想非常簡(jiǎn)單：從左向右，依次比較，每次移動(dòng)一個(gè)字符位置。比較方向可以任意選定。無(wú)預(yù)處理階段。原理：在主串s中從第i(i的初值為start)個(gè)字符起，并且長(zhǎng)度和t串相等的子串和t比較，假設(shè)相等，那么求得函數(shù)值為i,否那么i增1，直至串s中不存在從i開始和t相等的子串為止。BF算法舉例：文本：GCATCGCAGAGAGTATACAGTACG模式：GCAGAGAGFirstattempt

GCATCGCAGAGAGTATACAGTACG1234

GCAGAGAG

Secondattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Thirdattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Fourthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Fifthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

BF算法舉例(cont.)：Sixthattempt

GCATCGCAGAGAGTATACAGTACG

12345678

GCAGAGAG

Seventhattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Eighthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAGBF算法舉例(cont.)：Ninthattempt

GCATCGCAGAGAGTATACAGTACG

12

GCAGAGAG

Tenthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Eleventhattempt

GCATCGCAGAGAGTATACAGTACG

12

GCAGAGAG

BF算法舉例(cont.)：Twelfthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Thirteenthattempt

GCATCGCAGAGAGTATACAGTACG

12

GCAGAGAG

Fourteenthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

BF算法舉例(cont.)：Fifteenthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Sixteenthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Seventeenthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAGBF算法舉例(cont.)：voidBF(char*x,intm,char*y,intn){inti,j;/*Searching*/for(j=0;j<=n-m;++j){for(i=0;i<m&&x[i]==y[i+j];++i);if(i>=m)OUTPUT(j);}}

單模式匹配算法——BF代碼單模式匹配算法——KMPKMP〔D.E.Knuth,J.H.Morris,andV.R.Pratt〕主要是基于對(duì)BF算法的改進(jìn)：BF算法只是簡(jiǎn)單的每次移動(dòng)一個(gè)字符位置，并沒(méi)有考慮已匹配成功局部的信息。其實(shí)這些信息是可以利用的，此即所謂的“前綴模式〞——模式中不同局部存在的相同子串。KMP算法根據(jù)前綴模式可以使模式向前推進(jìn)假設(shè)干字符位置〔依前綴模式長(zhǎng)度而定〕，而不只是一個(gè)字符，防止了重復(fù)比較，同時(shí)也實(shí)現(xiàn)了文本指針的無(wú)回朔。假定試探第j個(gè)位置時(shí)，匹配失敗發(fā)生在模式字符x[i]=a和文本字符y[i+j]=b，即x[i+1...m-1]=y[i+j+1..j+m-1]=u且x[i]

！=

y[i+j]。當(dāng)轉(zhuǎn)移的時(shí)候，模式集的V能夠與文本中的u的一些后綴相匹配，最長(zhǎng)的V我們定義為u的邊界標(biāo)記〔taggedborder〕。kmpNext[i]定義為x[0..i-1]的最長(zhǎng)邊界，kmpNext[0]定義為-1。

單模式匹配算法——KMP原理舉例：文本：GCATCGCAGAGAGTATACAGTACG模式：GCAGAGAG計(jì)算kmpNext[i]i012345678x[i]GCAGAGAGkmpNext[i]-100010101kmpNext表Firstattempt

Shiftby:4(i-kmpNext[i]=3--1)GCATCGCAGAGAGTATACAGTACG1234

GCAGAGAG

Secondattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Secondattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Shiftby:1(i-kmpNext[i]=0--1)Thirdattempt

GCATCGCAGAGAGTATACAGTACG

12345678

GCAGAGAG

Shiftby:7(i-kmpNext[i]=8-1)Fourthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Shiftby:1(i-kmpNext[i]=1-0)Fifthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Shiftby:1(i-kmpNext[i]=0--1)Sixthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Shiftby:1(i-kmpNext[i]=0--1)Seventhattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Shiftby:1(i-kmpNext[i]=0--1)Eighthattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAGShiftby:1(i-kmpNext[i]=0--1)KMPNext表生成voidpreKmp(char*x,intm,intkmpNext[]){inti,j;i=0;j=kmpNext[0]=-1;while(i<m){while(j>-1&&x[i]!=x[j])j=kmpNext[j];i++;j++;if(x[i]==x[j])kmpNext[i]=kmpNext[j];elsekmpNext[i]=j;}}j=KMP函數(shù)實(shí)現(xiàn)代碼voidKMP(char*x,intm,char*y,intn){inti,j,kmpNext[XSIZE];/*Preprocessing*/preKmp(x,m,kmpNext);/*Searching*/i=j=0;while(j<n){while(i>-1&&x[i]!=y[j])

i=kmpNext[i];i++;j++;if(i>=m){OUTPUT(j-i);i=kmpNext[i];}}}

單模式匹配算法——BM算法BM算法被盛譽(yù)為速度最快的算法。主要思想：算法對(duì)模式從最右端自右向左掃描。在不匹配〔或完全匹配〕時(shí)，用兩個(gè)預(yù)先計(jì)算的函數(shù)badcharacter和goodsuffix來(lái)確定指針在正文中移動(dòng)的距離。BM算法的關(guān)鍵是找出不必要的比較。進(jìn)行比較時(shí)從字符串的右端而不是左端開始比較，當(dāng)比較不匹配時(shí)，可直接向右移假設(shè)干個(gè)位置；當(dāng)被比較的字符相等時(shí)，那么比較其前面的字符。如果成功次數(shù)等于模式串長(zhǎng)度，那么匹配成功。BM算法原理如果正在比較的主串中的字符在模式串中不存在，并且也不存在局部匹配，那么應(yīng)右移的位置數(shù)等于模式的長(zhǎng)度〔如第一種情況〕如果正在比較的主串中的字符在模式串不存在，但存在局部匹配，那么右移的位置數(shù)等于模式串長(zhǎng)度減去局部匹配的字符個(gè)數(shù)〔如第二種情況〕如果正在比較的主串中的字符出現(xiàn)在模式串中，那么右移的位置數(shù)應(yīng)為從模式串的最右端到模式串中該字符的距離〔如第三種情況〕BM算法原理具體實(shí)現(xiàn)該算法時(shí)，可以設(shè)計(jì)一張表，表中包含每一個(gè)可能比較的字符元素，表中的每個(gè)紀(jì)錄存貯的是相應(yīng)字符的移動(dòng)計(jì)數(shù)。對(duì)于那些未出現(xiàn)在模式串中的字符，移動(dòng)的計(jì)數(shù)等于模式串的長(zhǎng)度。對(duì)于那些出現(xiàn)在模式串中的字符，移動(dòng)的計(jì)數(shù)等于從模式串中最右端到該字符在模式串中出現(xiàn)的最右位置之間的距離，在模式匹配的過(guò)程中，當(dāng)出現(xiàn)字符不匹配的情況下，只需查一下該表，就可以知道右移的位置數(shù)。BM算法實(shí)現(xiàn)Thebad-charactershift,boccursinx.Thebad-charactershift,bdoesnotoccurinx.BM算法實(shí)現(xiàn)Badcharacter計(jì)算出字符集中每個(gè)字符的偏移值bmBC[i],對(duì)于未在模式中出現(xiàn)的字符，偏移為m,否那么取m-i-1,(其中i為字符在模式中的位置),即取此字符在模式中出現(xiàn)的最右位置和文本中此字符位置對(duì)齊，假設(shè)字符未在模式中出現(xiàn)，那么可將模式向前推m個(gè)字符位置。但是，在某些情況下這種偏移可能是負(fù)的。實(shí)際的偏移值取得是兩者中值較大者。Thegood-suffixshift,ure-occursprecededbyacharactercdifferentfroma.Thegood-suffixshift,onlyasuffixofure-occursinx.Goodsuffix的思想來(lái)源于KMP算法，即一個(gè)模式中在不同局部可能又存在相同的子串的性質(zhì)?？梢岳靡呀?jīng)成功完成的字符匹配，把已匹配局部看作整個(gè)模式的子模式，考慮模式前面一段中是否有與此子模式相匹配的片斷。這樣，就有可能把模式串向前推更遠(yuǎn)的距離〔在算法中是向前移動(dòng)文本指針〕。由于BM算法是從右向左比較的，所以構(gòu)造出的不是前綴數(shù)組，而是后綴數(shù)組。舉例：文本：GCATCGCAGAGAGTATACAGTACG模式：GCAGAGAGcACGTbmBc[c]1628計(jì)算bmBc[c]i01234567x[i]GCAGAGAGbmGs[i]77727471計(jì)算bmGs[i]Firstattempt

GCATCGCAGAGAGTATACAGTACG

1

GCAGAGAG

Secondattempt

GCATCGCAGAGAGTATACAGTACG

321

GCAGAGAG

Thirdattempt

GCATCGCAGAGAGTATACAGTACG

87654321

GCAGAGAG

Fifthattempt

GCATCGCAGAGAGTATACAGTACG

21

GCAGAGAGFourthattempt

GCATCGCAGAGAGTATACAGTACG

321

GCAGAGAG

算法比較BF算法

Stringlength:24Patternlength:8Attempts:17Charactercomparisons:30KMP算法

Attempts:8Charactercomparisons:18BM算法

Attempts:5Charactercomparisons:17本章內(nèi)容6.1信息處理技術(shù)背景6.2串匹配算法概念6.3模式匹配算法分類單模式匹配算法BF算法KMP算法BM算法多模式匹配算法AC算法Agrep算法AC算法——有限狀態(tài)機(jī)問(wèn)題：文本abfabcda……關(guān)鍵字abcd、abd、bfg確定關(guān)鍵字在文本中位置自動(dòng)機(jī)〔Automata〕：確定型有限自動(dòng)機(jī)DFA(Deterministicfiniteautomata)是一個(gè)五元組M={S,Σ,δ,s0,S1},包括:狀態(tài)集S輸入的字符集Σ狀態(tài)轉(zhuǎn)換函數(shù)δ起始狀態(tài)s0終止?fàn)顟B(tài)集S1AC算法實(shí)現(xiàn)拆分關(guān)鍵字生成狀態(tài)圖abcdabdbfgaababcabcdabdbbfbfg01…abc…z…012345678AC算法第一步：初始化狀態(tài)機(jī)拆分關(guān)鍵字生成狀態(tài)圖abcdabdbfgaababcabcdabdbbfbfg01…abcd..g…01234567800160……0…00120……0…00003…E..0…00000…E..0…00160…...0…00160…...0…00060…..70…00000……E…00160…...0…AC算法第二步：使用狀態(tài)機(jī)aababcabcdabdbbfbfg01…abcd..g…01234567800160……0…00120……0…00003…E..0…00000…E..0…00160…...0…00160…...0…00060…..70…00000……E…00160…...0…問(wèn)題：文本abfabcda，確定關(guān)鍵字abcd、abd、bfg在文本中位置。Char*txt=“sadfasdfsadfsadf〞;Inttxtlen=strlen(txt);Intstatnum=9;Intstat[9][257];Intmatch(char*txt){ inti,j; i=0; j=0; intk=0; while(k<txtlen) { j=txt[k]; i=stat[i][j]; if(stat[i][256]!=-1) returnstat[i][256]; else k++; }}多模式匹配算法多模式匹配問(wèn)題在生物計(jì)算、信息檢索及信號(hào)處理領(lǐng)域有著非常廣泛的應(yīng)用。最早也是最著名的以線性時(shí)間復(fù)雜度解決這個(gè)問(wèn)題的算法是1975年Aho-Corasick提出的AC75；對(duì)于單模式還有非常好高效的算法BM77,由BM中的跳躍思想衍生出了許多變種，應(yīng)用于單模式和多模式匹配中。Commentz-Walter就是在結(jié)合AC和BM的思想產(chǎn)生的一種多模式匹配算法，另外，1992年Wu.Sum和Udi.manber提出的agrep是最好的多模算法之一。近年來(lái)，由于后綴樹〔suffixtree〕和后綴自動(dòng)機(jī)(suffixauromaton)的引入，又出現(xiàn)了DAWG－MATCH和MultiBDM。有限自動(dòng)機(jī)多模式匹配——AC算法Aho-Corasick自動(dòng)機(jī)算法〔簡(jiǎn)稱AC自動(dòng)機(jī)〕1975年產(chǎn)生于貝爾實(shí)驗(yàn)室。該算法應(yīng)用有限自動(dòng)機(jī)巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。該算法的根本思想是這樣的：在預(yù)處理階段，AC自動(dòng)機(jī)算法建立了三個(gè)函數(shù)，轉(zhuǎn)向函數(shù)goto，失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個(gè)樹型有限自動(dòng)機(jī)。在搜索查找階段，那么通過(guò)這三個(gè)函數(shù)的交叉使用掃描文本，定位出關(guān)鍵字在文本中的所有出現(xiàn)位置。此算法有兩個(gè)特點(diǎn)，一個(gè)是掃描文本時(shí)完全不需要回溯，另一個(gè)是時(shí)間復(fù)雜度為O(n)，時(shí)間復(fù)雜度與關(guān)鍵字的數(shù)目和長(zhǎng)度無(wú)關(guān)。樹型有限自動(dòng)機(jī)包含一組狀態(tài)，每個(gè)狀態(tài)用一個(gè)數(shù)字代表。狀態(tài)機(jī)讀入文本串y中的字符，然后通過(guò)產(chǎn)生狀態(tài)轉(zhuǎn)移或者偶爾發(fā)送輸出的方式來(lái)處理文本。樹型有限自動(dòng)機(jī)的行為通過(guò)三個(gè)函數(shù)來(lái)指示：轉(zhuǎn)向函數(shù)g，失效函數(shù)f和輸出函數(shù)output。

樹型有限自動(dòng)機(jī)例如：對(duì)應(yīng)模式集{he,she,his,hers}的樹型有限自動(dòng)機(jī)圖1a〕轉(zhuǎn)向函數(shù)g圖1b〕失效函數(shù)f圖1c〕輸出函數(shù)output樹型有限自動(dòng)機(jī)3.轉(zhuǎn)向，失效和輸出函數(shù)的構(gòu)建現(xiàn)在說(shuō)明如何根據(jù)一個(gè)關(guān)鍵字集建立正確的轉(zhuǎn)向、失效和輸出函數(shù)。整個(gè)構(gòu)建包含兩個(gè)局部，在第一局部確定狀態(tài)和轉(zhuǎn)向函數(shù)，在第二局部我們計(jì)算失效函數(shù)。輸出函數(shù)的計(jì)算那么是穿插在第一局部和第二局部中完成。為了構(gòu)建轉(zhuǎn)向函數(shù)，我們需要建立一個(gè)狀態(tài)轉(zhuǎn)移圖。開始，這個(gè)圖只包含一個(gè)代表狀態(tài)0。然后，通過(guò)添加一條從起始狀態(tài)出發(fā)的路徑的方式，依次向圖中輸入每個(gè)關(guān)鍵字p。新的頂點(diǎn)和邊被參加到圖表中，以致于產(chǎn)生了一條能拼寫出關(guān)鍵字p的路徑。關(guān)鍵字p會(huì)被添加到這條路徑的終止?fàn)顟B(tài)的輸出函數(shù)中。當(dāng)然只有必要時(shí)才會(huì)在圖表中增加新的邊。例如:對(duì)關(guān)鍵字集{he,she,his,hers}建立轉(zhuǎn)向函數(shù)。向圖表中添加第一個(gè)關(guān)鍵字，得到：從狀態(tài)0到狀態(tài)2的路徑拼寫出了關(guān)鍵字“he〞，我們把輸出“he〞和狀態(tài)2相關(guān)聯(lián)。添加第二個(gè)關(guān)鍵字“she〞，得到：輸出“she〞和狀態(tài)5相關(guān)聯(lián)。增加第三個(gè)關(guān)鍵字“his〞，我們得到了下面這個(gè)圖。注意到當(dāng)我們?cè)黾雨P(guān)鍵字“his〞時(shí)，已經(jīng)存在一條從狀態(tài)0到狀態(tài)1標(biāo)記著h的邊了，所以我們不必另外添加一條同樣的邊。輸出“his〞是和狀態(tài)7相關(guān)聯(lián)的添加第四個(gè)關(guān)鍵字“hers〞，可以得到：輸出“hers〞和狀態(tài)9相關(guān)聯(lián)。在這里，我們能夠使用已有的兩條邊：一條是從狀態(tài)0到1標(biāo)記著h的邊；一條是從狀態(tài)1到2標(biāo)記著e的邊。

這樣，圖已經(jīng)成為一棵帶根的樹。為了完成轉(zhuǎn)向函數(shù)的構(gòu)建，我們對(duì)除了h和s外的其他每個(gè)字符，都增加一個(gè)從狀態(tài)0到狀態(tài)0的循環(huán)。這樣，我們得到了如圖1a)所示的狀態(tài)轉(zhuǎn)移圖，這個(gè)圖就代表轉(zhuǎn)向函數(shù)。算法1：建立轉(zhuǎn)向函數(shù)g。輸入：關(guān)鍵字集P={p1,p2,p3,…,pr}。輸出：轉(zhuǎn)向函數(shù)g和局部的output函數(shù)。方法:

圖2建立轉(zhuǎn)向函數(shù)g的偽代碼失效函數(shù)是根據(jù)轉(zhuǎn)向函數(shù)建立的。首先，我們定義狀態(tài)轉(zhuǎn)移圖中狀態(tài)s的深度為從狀態(tài)0到狀態(tài)s的最短路徑。例如圖1a)起始狀態(tài)的深度是0，狀態(tài)1和3的深度是1，狀態(tài)2，4，和6的深度是2，等等。

圖1a)d(0)=0;d(1)=

d(3)=1;d(2)=d(6)=d(4)=2d(8)=d(7)=d(5)=3;d(9)=4計(jì)算思路：先計(jì)算所有深度是1的狀態(tài)的失效函數(shù)值，然后計(jì)算所有深度為2的狀態(tài)，以此類推，直到所有狀態(tài)〔除了狀態(tài)0，因?yàn)樗纳疃葲](méi)有定義〕的失效函數(shù)值都被計(jì)算出。計(jì)算方法：用于計(jì)算某個(gè)狀態(tài)失效函數(shù)值的算法在概念上是非常簡(jiǎn)單的。首先，令所有深度為1的狀態(tài)s的函數(shù)值為f(s)=0。假設(shè)所有深度小于d的狀態(tài)的f值都已經(jīng)被算出了，那么深度為d的狀態(tài)的失效函數(shù)值將根據(jù)深度小于d的狀態(tài)的失效函數(shù)值來(lái)計(jì)算。為了計(jì)算深度為d狀態(tài)的失效函數(shù)值，我們考慮每個(gè)深度為d-1的狀態(tài)r，執(zhí)行以下步驟：Step1：如果對(duì)所有狀態(tài)a的g(r,a)=fail，那么什么都不做Step2：否那么，對(duì)每個(gè)使得g(r,a)=s存在的狀態(tài)s，執(zhí)行以下操作記state=f(r)。零次或者屢次令state=f(state)，直到出現(xiàn)一個(gè)狀態(tài)使得g(state,a)!=fail〔注意到，因?yàn)閷?duì)任意字符a，g(0,a)!=fail，所以這種狀態(tài)一定能夠找到〕Step2：記f(s)=g(state,a)

以圖1a)為例說(shuō)明計(jì)算的失效函數(shù)f；先令f(1)=f(3)=0，因?yàn)?和3是深度為1的狀態(tài)。計(jì)算深度為2的狀態(tài)2，6和4的失效函數(shù)。

計(jì)算f(2)，令state=f(1)=0；由于g(0,a)=0，得到f(2)=0。計(jì)算f(6)，令state=f(1)=0；由于g(0,i)=0，得到f(6)=0。計(jì)算f(4)，令state=f(3)=0；由于g(0,h)=1，得到f(4)=1。按這種方式繼續(xù)，最終得到了如圖1b)

所示的失效函數(shù)f。

在計(jì)算失效函數(shù)的過(guò)程中，也更新了輸出函數(shù)。當(dāng)求出f(s)=

s，時(shí)，我們把狀態(tài)s的輸出和狀態(tài)s，的輸出合并到一起。對(duì)于上文中的例子，從圖1a)

我們求出f(5)=2。這時(shí)，把狀態(tài)2的輸出集，也就是{he}，增加到狀態(tài)5的輸出集中，這樣就得到了新的輸出集合{he,she}。最終各狀態(tài)的非空輸出集如圖1c)

所示。

算法2：建立失效函數(shù)f。輸入：轉(zhuǎn)向函數(shù)g和局部的輸出函數(shù)output。輸出：失效函數(shù)f和完整的輸出函數(shù)output。方法:圖3建立失效函數(shù)f的偽代碼4.轉(zhuǎn)向函數(shù)的構(gòu)建圖1中樹型自動(dòng)機(jī)的狀態(tài)有0,1,…,9。某個(gè)狀態(tài)〔通常是0狀態(tài)〕被指定為起始狀態(tài)。轉(zhuǎn)向函數(shù)把一個(gè)由狀態(tài)和輸入字符組成的二元組映射成另一個(gè)狀態(tài)或者一條失敗消息。圖1a)的狀態(tài)圖代表轉(zhuǎn)向函數(shù)g。比方,從0到1標(biāo)記著h的邊表示g(0,h)=1，如果缺省箭頭那么表示失敗。可見(jiàn)，對(duì)除e和i之外的其他輸入字符，都有g(shù)(1,h)=fail。所有的樹型有限自動(dòng)機(jī)都有一個(gè)共同的特點(diǎn)，即對(duì)任何輸入字符a,都有g(shù)(0,a)!=fail。我們將看到，轉(zhuǎn)向函數(shù)在0狀態(tài)上的這種性質(zhì)確保每個(gè)輸入字符都可以在狀態(tài)機(jī)的一個(gè)操作循環(huán)內(nèi)被處理。舉個(gè)例子，記樹型有限自動(dòng)機(jī)為狀態(tài)機(jī)M。狀態(tài)機(jī)M利用圖1的函數(shù)去處理輸入文本“ushers〞，圖4顯示了M在處理文本串時(shí)產(chǎn)生的狀態(tài)轉(zhuǎn)移情況?？紤]M在狀態(tài)4，且當(dāng)前輸入字符為e時(shí)的操作循環(huán)。由于g(4,e)=5，狀態(tài)機(jī)進(jìn)入狀態(tài)5，文本指針將前進(jìn)到下一個(gè)輸入字符，并且輸出output(5)。這個(gè)輸出說(shuō)明狀態(tài)機(jī)已經(jīng)發(fā)現(xiàn)輸入文本的第四個(gè)位置是“she〞和“he〞出現(xiàn)的結(jié)束位置。在狀態(tài)5上輸入字符r，狀態(tài)機(jī)M在此次操作循環(huán)中將產(chǎn)生兩次狀態(tài)轉(zhuǎn)移。由于g(5,r)=fail，M進(jìn)入狀態(tài)2=f(5)。然后因?yàn)間(2,r)=8，M進(jìn)入狀態(tài)8，同時(shí)前進(jìn)到下一個(gè)輸入字符。在這次操作循環(huán)中沒(méi)有輸出產(chǎn)生。圖4掃描“ushers〞時(shí)的狀態(tài)轉(zhuǎn)換序列

記s為狀態(tài)機(jī)的當(dāng)前狀態(tài)，a為輸入文本y的當(dāng)前輸入字符。樹型有限自動(dòng)機(jī)的一次操作循環(huán)可以定義如下：如果g(s,a)=s，，那么樹型有限自動(dòng)機(jī)將做一個(gè)轉(zhuǎn)向動(dòng)作。自動(dòng)機(jī)進(jìn)入狀態(tài)s，而且y的下一個(gè)字符變成當(dāng)前的輸入字符。另外，如果output(s，)不為空，那么狀態(tài)機(jī)將輸出與當(dāng)前輸入字符位置相對(duì)應(yīng)的一組關(guān)鍵字。如果g(s,a)=fail，狀態(tài)機(jī)將詢問(wèn)失效函數(shù)f并且進(jìn)行失效轉(zhuǎn)移。如果f(s)=s，，那么狀態(tài)機(jī)將以s，作為當(dāng)前狀態(tài)，a為當(dāng)前輸入字符重復(fù)這個(gè)操作循環(huán)。

算法3：樹型有限狀態(tài)機(jī)。輸入：一個(gè)字符串y={y1y2y3…yn}〔其中yi是一個(gè)輸入字符〕；一臺(tái)包含上述轉(zhuǎn)向函數(shù)g，失效函數(shù)f和輸出函數(shù)output的樹型有限自動(dòng)機(jī)。輸出：關(guān)鍵字在y中出現(xiàn)的位置。

圖5建立樹型有限自動(dòng)機(jī)的算法偽代碼5.AC自動(dòng)機(jī)預(yù)處理階段：轉(zhuǎn)向函數(shù)把一個(gè)由狀態(tài)和輸入字符組成的二元組映射成另一個(gè)狀態(tài)或者一條失敗消息。失效函數(shù)把一個(gè)狀態(tài)映射成另一個(gè)狀態(tài)。當(dāng)轉(zhuǎn)向函數(shù)報(bào)告失效時(shí)，失效函數(shù)就會(huì)被詢問(wèn)。輸出狀態(tài)，它們表示已經(jīng)有一組關(guān)鍵字被發(fā)現(xiàn)。輸出函數(shù)通過(guò)把一組關(guān)鍵字集〔可能是空集〕和每個(gè)狀態(tài)相聯(lián)系的方法，使得這種輸出狀態(tài)的概念形式化。搜索查找階段：文本掃描開始時(shí)，初始狀態(tài)置為狀態(tài)機(jī)的當(dāng)前狀態(tài)，而輸入文本y的首字符作為當(dāng)前輸入字符。然后，樹型有限自動(dòng)