52運行安全-檢測

1、網(wǎng)絡(luò)與信息平安技術(shù)主講人：張宏莉 余翔湛課程內(nèi)容信息平安概述網(wǎng)絡(luò)平安面臨的威脅信息平安體系結(jié)構(gòu)物理平安運行平安數(shù)據(jù)平安信息內(nèi)容平安信息平安標(biāo)準(zhǔn)、法律法規(guī)運行平安技術(shù)主機系統(tǒng)運行平安風(fēng)險評估防火墻與訪問控制網(wǎng)絡(luò)系統(tǒng)運行平安系統(tǒng)生存性評估檢測大規(guī)模網(wǎng)絡(luò)運行平安平安態(tài)勢評估檢測、響應(yīng)與控制 提綱惡意代碼傳統(tǒng)檢測機制誤用檢測異常檢測典型的網(wǎng)絡(luò)平安事件入侵網(wǎng)絡(luò)攻擊木馬病毒網(wǎng)絡(luò)蠕蟲僵尸網(wǎng)絡(luò)DDOS攻擊惡意代碼惡意代碼Malicious code、惡意軟件MalwareMalicious Software該軟件違背計算機信息系統(tǒng)用戶的意愿，執(zhí)行時某些代碼以破壞、竊取、惡意利用等為目的。假設(shè)某程序代碼集合中包

2、含了一段此類的代碼，那么稱此代碼為惡意代碼或惡意軟件。惡意的目的本身是程序通過執(zhí)行發(fā)生作用 不必要代碼不必要代碼Unwanted Code是指沒有作用卻會帶來危險的代碼，一個最平安的定義是把所有不必要的代碼都看作是惡意的，不必要代碼比惡意代碼具有更寬泛的含義，包括所有可能與某個組織平安策略相沖突的軟件。 惡意代碼的檢測與控制惡意代碼入侵、攻擊、病毒、木馬、掃描等等我們所關(guān)注的是網(wǎng)絡(luò)平安事件尤其是大規(guī)模網(wǎng)絡(luò)平安事件所涉及的網(wǎng)絡(luò)惡意代碼。群體性突發(fā)性廣范性，規(guī)模大檢測與控制的層面主機層面網(wǎng)絡(luò)層面大規(guī)模網(wǎng)絡(luò)層面蠕蟲行為模式分類 蠕蟲行為模式一般包括：掃描行為、攻擊行為、命令控制行為、文件傳輸行為和激

3、活行為 掃描行為(Scan):蠕蟲發(fā)出一系列數(shù)據(jù)報文來掃描目標(biāo)主機是否在線，或者是否開啟相應(yīng)效勞，或者是否存在漏洞，這樣的一系列事件被稱為蠕蟲的掃描行為。 掃描的順序一般也是蠕蟲復(fù)制、傳播的順序過程。攻擊行為(Attack):蠕蟲利用目標(biāo)主機效勞存在的漏洞，以進入目標(biāo)主機并獲得一定權(quán)限為目的的一系列事件被稱為蠕蟲的攻擊行為。 命令控制行為(Control):蠕蟲利用攻擊目標(biāo)主機漏洞的結(jié)果和目標(biāo)主機建立控制連接，從而可以在目標(biāo)主機的shell環(huán)境下執(zhí)行命令。蠕蟲建立控制連接、向目標(biāo)主機下達命令的過程被稱為蠕蟲的命令控制行為。 文件傳輸行為(Transmit)：蠕蟲利用TFTP等傳輸方式將蠕蟲副本

4、、攻擊工具等傳到目標(biāo)主機上的過程稱為文件傳輸行為。從傳輸協(xié)議的角度來看，文件傳輸行為可以是一個單獨的傳輸連接。需要說明的是，蠕蟲副本可以以文件傳輸?shù)姆绞竭M行，也可以嵌入到攻擊行內(nèi)進行傳輸即攻擊成功完成的同時蠕蟲副本傳輸也成功完成。比方Blaster利用TFTP向目標(biāo)主機傳輸蠕蟲副本，蠕蟲CodeRed的蠕蟲副本和攻擊行為結(jié)合在一起進行傳播。 激活行為(Provoke)：是指目標(biāo)主機已經(jīng)獲得蠕蟲副本，攻擊者通過命令控制或者攻擊等方式激活目標(biāo)主機上的蠕蟲的過程稱為激活行為。比方蠕蟲Nimda通過執(zhí)行類似“GET /scripts/Admin.dll HTTP/1.0來激活目標(biāo)主計上的蠕蟲，蠕蟲Sa

5、sser和Blaster通過控制連接激活目標(biāo)主機上的蠕蟲。蠕蟲的掃描擴散隨機掃描本地優(yōu)先掃描順序掃描基于目標(biāo)列表的掃描分治掃描策略被動式擴散隨機掃描擴散均勻隨機掃描均勻隨機擴散是指從掃描空間內(nèi)隨機抽取一個IP地址作為目標(biāo)傳播，掃描空間可以為整個IPv4地址空間算法簡單、易實現(xiàn)，會產(chǎn)生大量異常的流量，容易在早期就被檢測系統(tǒng)發(fā)現(xiàn)。選擇性隨機掃描 目標(biāo)地址按照一定的算法隨機生成，但對公網(wǎng)中不可能出現(xiàn)的地址塊進行標(biāo)識，防止掃描這些地址。算法簡單、易實現(xiàn)的特點，假設(shè)與本地優(yōu)先原那么結(jié)合，那么能到達更好的傳播效果。但選擇性隨機掃描容易引起網(wǎng)絡(luò)阻塞，使得網(wǎng)絡(luò)蠕蟲在爆發(fā)之前易被發(fā)現(xiàn)，隱蔽性差 CodeRed蠕

6、蟲、Slapper蠕蟲、Slammer蠕蟲本地優(yōu)先掃描主導(dǎo)思想：優(yōu)先選擇本地或者與本地相近的網(wǎng)絡(luò)進行掃描。被感染主機上蠕蟲的生成目標(biāo)地址和所在主機的IP地址在同一個子網(wǎng)的概率比較大。如：Nimda蠕蟲生成的目標(biāo)地址有50%的概率在當(dāng)前機器IP所在的B類地址范圍內(nèi)產(chǎn)生，有25%的概率在當(dāng)前機器IP所在的A類范圍內(nèi)產(chǎn)生，另25%的概率是隨機IP地址。這種擴散策略的支持者認(rèn)為，一個主機被感染蠕蟲之后，這個主機所在的子網(wǎng)的IP地址被分配出去并且被使用的概率比較大，從而能夠增加發(fā)現(xiàn)漏洞主機的概率。將互聯(lián)網(wǎng)地址空間中未分配的或者保存的地址塊排除在掃描之列實現(xiàn)簡單，傳播速度與概率P的選取、地址空間數(shù)目相關(guān)比

7、方Blaster蠕蟲和Nimda蠕蟲，順序掃描順序掃描(sequential scan)：是指被感染主機上蠕蟲會隨機選擇一個C類網(wǎng)絡(luò)地址進行傳播。根據(jù)本地優(yōu)先原那么，蠕蟲一般會選擇它所在網(wǎng)絡(luò)內(nèi)的IP地址。假設(shè)蠕蟲掃描的目標(biāo)地址IP為A，那么掃描的下一個地址IP為A+1或者A1。一旦掃描到具有很多漏洞主機的網(wǎng)絡(luò)時就會到達很好的傳播效果。該策略的缺乏是對同一臺主機可能重復(fù)掃描，引起網(wǎng)絡(luò)擁塞。所以盡量防止父節(jié)點與自節(jié)點的掃描空間相重合。多采用隨機策略選擇初始節(jié)點，掃描速度等價于隨機策略W32.Blaster是典型的順序掃描蠕蟲?；谀繕?biāo)列表的掃描擴散算法 基于目標(biāo)列表的擴散是指網(wǎng)絡(luò)蠕蟲在尋找受感染的

8、目標(biāo)之前預(yù)先生成一份可能易傳染的目標(biāo)列表，然后對該列表進行攻擊嘗試和傳播目標(biāo)列表生成方法有兩種：通過小規(guī)模的掃描或者互聯(lián)網(wǎng)的共享信息產(chǎn)生目標(biāo)列表；通過分布式掃描可以生成全面的列表的數(shù)據(jù)庫。 基于目標(biāo)列表的擴散提高了蠕蟲的傳播速度，缺乏是網(wǎng)絡(luò)蠕蟲傳播時必須攜帶一個IP地址庫，使得蠕蟲負(fù)載量增大。分治掃描策略的另一個缺乏是存在“壞點問題。在蠕蟲傳播的過程中，如果一臺感染蠕蟲的主機死機或崩潰，那么其所對應(yīng)的剩余掃描列表中主機就會失去被感染的時機。并且，這個問題發(fā)生得越早，影響就越大。分治掃描分治掃描(divide-conquer scan)：網(wǎng)絡(luò)蠕蟲之間相互協(xié)作、快速搜索易感染主機的一種策略。網(wǎng)絡(luò)蠕

9、蟲發(fā)送地址庫的一局部給每臺被感染的主機，然后每臺主機再去掃描它所獲得的地址。主機A感染了主機B以后，主機A將它自身攜帶的地址分出一局部給主機B，然后主機B開始掃描這一局部地址。防止重復(fù)掃描，缺點：一旦節(jié)點失效，掃描中斷掃描策略評價在理想情況下，當(dāng)漏洞主機均勻分布在網(wǎng)絡(luò)中的時候。蠕蟲采用均勻隨機擴散策略時傳播速度比采用本地優(yōu)先策略傳播速度快 基于目標(biāo)列表的擴散策略當(dāng)列表小于6M字節(jié)時，蠕蟲傳播速度比均勻隨機掃描快 實際中仍然主要是隨機掃描和順序掃描兩種方式，使用其它的傳播策略的蠕蟲還很少。通常蠕蟲對目標(biāo)列表的掃描，以及局域網(wǎng)內(nèi)的順序掃描都僅僅是在蠕蟲傳播的早期，大量的隨機掃描那么范圍大，持續(xù)時間

10、長，構(gòu)成了蠕蟲傳播的主體，例如，曾經(jīng)大肆泛濫造成巨大危害的：Code Red、Code Red II、Slammer、Blaster、Sasser、Welchia等蠕蟲被動式擴散算法 被動式傳播蠕蟲那么不需要主動掃描就能夠傳播。被動式蠕蟲通過潛伏在已感染主機中，等待潛在的攻擊對象來主動接觸它們，或者通過監(jiān)聽網(wǎng)絡(luò)數(shù)據(jù)報文，獲取其它用戶活動信息，從而發(fā)現(xiàn)新的攻擊目標(biāo)。由于它們需要目標(biāo)觸發(fā)，所以當(dāng)目標(biāo)數(shù)量少或者掃描頻率低的時候傳播速度很慢，但當(dāng)目標(biāo)造成的掃描頻率很高，那么傳播速度會很快。這類蠕蟲在發(fā)現(xiàn)目標(biāo)的過程中并不會引起通信異常，這使得它們自身有更強的平安性。Contagion和CRClean都是

11、被動式蠕蟲，Contagion通過監(jiān)聽正常的通信來發(fā)現(xiàn)新的攻擊對象；CRClean那么通過等待CodeRed II的掃描活動來發(fā)現(xiàn)新的攻擊對象，當(dāng)它發(fā)現(xiàn)有CodeRed II向自己所在主機掃描時，就發(fā)起一個反攻來回應(yīng)該CodeRed，如果反攻成功，它就刪除CodeRed II，并在目標(biāo)主機上建立CRClean副本。僵尸網(wǎng)絡(luò)Botnet 定義僵尸網(wǎng)絡(luò)是可被攻擊者遠程控制的被攻陷主機所組成的網(wǎng)絡(luò)。 CNCERT/CC的定義：僵尸網(wǎng)絡(luò)指的是攻擊者利用互聯(lián)網(wǎng)秘密建立的可以集中控制的計算機群。其組成通常包括被植入“僵尸程序的計算機群，一個或多個控制效勞器，控制者的控制終端等。僵尸網(wǎng)絡(luò)是攻擊者處于惡意目標(biāo)

12、，傳播僵尸程序?qū)⒋罅恐鳈C感染成僵尸主機，并通過一對多的命令和控制信道所組成的網(wǎng)絡(luò)。 僵尸網(wǎng)絡(luò)典型結(jié)構(gòu)僵尸網(wǎng)絡(luò):是由Bot、命令控制效勞器和控制者組成的可通信、可控制的網(wǎng)絡(luò)。僵尸網(wǎng)絡(luò)的特點：僵尸網(wǎng)絡(luò)是一個可控的網(wǎng)絡(luò)，這個網(wǎng)絡(luò)并不是物理意義上具有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，而是具有一定分布性，隨著Bot程序不斷被傳播有新的計算機參加的一個動態(tài)變化的網(wǎng)絡(luò)。僵尸網(wǎng)絡(luò)是通過一定的傳播手段形成的，如主動的漏洞攻擊、電子郵件病毒和蠕蟲等傳播手段。僵尸網(wǎng)絡(luò)可以執(zhí)行一對多的控制關(guān)系，發(fā)起惡意行為。比方說，指揮bots對某一個目標(biāo)站點發(fā)起DDos攻擊。隱蔽性分布式拒絕效勞攻擊 (DDos，2000年)拒絕效勞攻擊Deni

13、al-of-Service；DoS已成為網(wǎng)絡(luò)攻擊的主要方式之一，但結(jié)合蠕蟲、特洛伊木馬、僵尸網(wǎng)絡(luò)等，那么能夠采用更大規(guī)模的攻擊手法DDos 攻擊，形成對企業(yè)、網(wǎng)站更長時間的“封鎖，造成更大的損失。影響比較大的此類平安事件主要有2000年2月Yahoo宣告因為遭受分布式拒絕效勞攻擊而徹底崩潰，之后，Amazon ，CNN，eBay，ZDNet等其它七大知名網(wǎng)站也幾乎在同一時間徹底崩潰；2001年，紅色代碼Code Red蠕蟲曾對微軟IIS Server展開DDoS攻擊；2004年1月底，Yahoo、Google等搜尋引擎網(wǎng)站更受到MyDoom蠕蟲的DDoS攻擊。2021年，韓國政府網(wǎng)站遭受攻擊商

14、業(yè)化、政治化的色彩越來越強檢測什么？控制什么？前提非法行為和合法行為是可區(qū)分的核心問題如何區(qū)分非法行為和合法行為檢測方法的分類按照分析方法誤用檢測模型Misuse Detection)：收集非正常操作的行為特征，建立相關(guān)的特征庫，當(dāng)監(jiān)測的網(wǎng)絡(luò)行為與庫中的記錄相匹配時，就認(rèn)為是惡意網(wǎng)絡(luò)行為 異常檢測模型Anomaly Detection ):首先總結(jié)正常網(wǎng)絡(luò)行為應(yīng)該具有的特征用戶輪廓，當(dāng)用戶活動與正常行為有重大偏離時即被認(rèn)為是惡意網(wǎng)絡(luò)行為 前提：所有的入侵行為都有可被檢測到的特征 攻擊特征庫: 當(dāng)監(jiān)測的用戶或系統(tǒng)行為與庫中的記錄相匹配時，系統(tǒng)就認(rèn)為這種行為是入侵 過程 監(jiān)控 特征提取 匹配 判定

15、 指標(biāo):誤報低、漏報高 誤用檢測經(jīng)典的IDS誤用檢測技術(shù)Snort檢測機制協(xié)議分析協(xié)議分析去除噪聲數(shù)據(jù)根據(jù)協(xié)議的定義可以丟棄很多無效數(shù)據(jù)，減少分析壓力。復(fù)原真實內(nèi)容確保IDS具有接近操作系統(tǒng)和應(yīng)用效勞器對于網(wǎng)絡(luò)數(shù)據(jù)的理解能力，降低誤報率和漏報率。實際必須考慮分析層次、范圍與系統(tǒng)性能的平衡分析與檢測一般交替進行網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)協(xié)議解析EthernetARPRARPIPTCPUDPICMPIGMPSMBDNSFTPTELNETHTTP復(fù)原處理：IP碎片重組、TCP會話會聚、編碼處理等檢測過程示意 協(xié)議分析 協(xié)議分析網(wǎng)絡(luò)數(shù)據(jù)中間數(shù)據(jù)應(yīng)用數(shù)據(jù)網(wǎng)絡(luò)數(shù)據(jù)入侵檢測入侵檢測協(xié)議分析加命令解析技術(shù)是一種新的入侵檢測

16、技術(shù)，它結(jié)合高速數(shù)據(jù)包捕捉、協(xié)議分析和命令解析來進行入侵檢測。協(xié)議分析 + 命令解析命令解析入侵檢測引擎包括了多種不同的命令語法解析器解析器是一個命令解釋程序，它能對不同的高層協(xié)議如Telnet、FTP、HTTP、SMTP、SNMP、DNS等的用戶命令進行詳細的分析。命令解析器具有讀取攻擊串及其所有可能的變形，并開掘其本質(zhì)含義的能力。在攻擊特征庫中只需要一個特征，就能檢測這一攻擊所有可能的變形。解析器在開掘出命令的真實含義后將給惡意命令做好標(biāo)記，主機將會在這些包到達操作系統(tǒng)、應(yīng)用程序之前丟棄它們。深層次協(xié)議分析深層協(xié)議分析。數(shù)據(jù)包經(jīng)過協(xié)議解析后，被分流到不同的檢測方法集中。經(jīng)過細顆粒的協(xié)議分析

17、解析后，需要匹配的規(guī)那么數(shù)大大減少，所以提高了入侵分析的效率和準(zhǔn)確性，并能檢測檢測到某些協(xié)議異常的未知攻擊。狀態(tài)分析：引擎不只是檢測單個連接，而是將一個會話的所有流量作為一個整體來考察。很多網(wǎng)絡(luò)攻擊的行為包含在多個請求中，僅靠檢測單一的連接請求或響應(yīng)是不準(zhǔn)確的，會引起誤警或漏警。高效的匹配算法高效的算法和高效的處理結(jié)構(gòu)能大大增強IDS檢測引擎的性能盡管協(xié)議分析技術(shù)可以減少內(nèi)容匹配負(fù)擔(dān)，但不能防止模式匹配單模匹配算法：BM算法Boyer-Moore多模匹配算法：如改進的BM算法snort中提供多種多模匹配算法可參考引擎的結(jié)構(gòu)、處理流程、規(guī)那么特征、必須與算法高度配合才能到達最好的效果，甚至到達增

18、加規(guī)那么數(shù)而不影響處理速度?；谔卣鞔a的匹配方法檢測的兩個關(guān)鍵特征碼的匹配技術(shù)串匹配(模式匹配)有限狀態(tài)自動機特征碼的提取特征碼的唯一性特征碼的優(yōu)化 串匹配string matching，也叫模式匹配pattern matching，可以簡單地定義為在給定的字符流中查找出滿足某些指定屬性的字符串。 這是計算機科學(xué)中最古老也最普遍的問題之一，計算機科學(xué)中串匹配的應(yīng)用可以說隨處可見。近年來，在網(wǎng)絡(luò)平安方面，有一個很重要的問題，就是快速發(fā)現(xiàn)具有某些特征碼的有害信息，及早地防范于未然。病毒和入侵檢測NIDNetwork Intrusion Detection都可以淋漓盡致地發(fā)揮串匹配算法的優(yōu)勢。 大

19、概我們最熟悉的應(yīng)用是文本編輯中所使用的查找替換，這是一種最簡單的串匹配問題。 文本：由假設(shè)干個字符組成的有限序列，設(shè)為y=y1y2y3yn,其中n為文本長度，即文本中總的字符個數(shù)。模式：也稱為關(guān)鍵字，由假設(shè)干個字符組成的有限序列p=k1k2k3km，其中m為模式長度，即模式中字符總數(shù)。模式集：指所有需要匹配的模式形成的集合，記為P=p1,p2,p3,pr，其中pi是模式集中第i個模式。記模式集中所有模式長度的總和為|P|。最小模式長度：假設(shè)模式集中各個模式長度分別為l1,l2,lr,那么最小模式長度是指所有模式長度的最小值，即minlen = minl1,l2,lr。前綴：兩個字符串 p和x，

20、假設(shè)存在字符串vv可為空串，使得p=xv成立，稱x為p的前綴。概 念6.后綴：兩個字符串p和x,假設(shè)存在字符串uu可為空串,使得p=ux成立x，稱為p的后綴。7.子串：兩個字符串p和x,假設(shè)存在字符串u,vu,v可以為空串，使得p=uxv成立，稱x為p的子串。8.字符集：在模式或文本中所有可能出現(xiàn)的字符形成的集合，記為，其大小記為|。9.自動機Automata： 一個包括狀態(tài)集S，輸入的字符集，狀態(tài)轉(zhuǎn)換函數(shù)，起始狀態(tài)s0和終止?fàn)顟B(tài)集S1的五元組M = S,s0,S1，我們主要討論的是確定型有限自動機DFA(Deterministic finite automata)。 匹配方法的分類 模式匹配

21、的模式數(shù)目單模式多模式匹配方式精確匹配近似匹配匹配的具體內(nèi)容單詞匹配字符類匹配正則表達匹配單模式匹配單模式匹配可定義為：在一個文本text(設(shè)長度為n)中查找某個特定的子串pattern(設(shè)長度為m)。如果在text中找到等于pattern的子串，那么稱匹配成功，函數(shù)返回pattern在text中出現(xiàn)的位置(或序號)，否那么匹配失敗。多模式匹配多模式匹配可定義為：在一個文本text(設(shè)長度為n)中查找某些特定的子串patterns(設(shè)長度為m)。如果在text中找到等于patterns中的某些子串，那么稱匹配成功，函數(shù)返回pattern在text中出現(xiàn)的位置(或序號)，否那么匹配失敗。 BFB

22、rute-Force算法 (又稱Naive算法) 是最早出現(xiàn)的單關(guān)鍵字匹配算法，思想簡單，雖然理論上的時間復(fù)雜度很差，但是實際使用效果尚可，因此還被采用。ANSI C中提供的strstr函數(shù)就是使用這種算法的改進版本。由于BF算法掃描字符串時常常需要回溯，效果顯得不好。 1970年，理論上證明了串匹配問題可以在O(m+n) 線性時間內(nèi)解決，隨后和仿照的證明構(gòu)造了一個算法，與此同時，也得到相類似的算法，這樣就產(chǎn)生了第一種線性時間復(fù)雜度的模式匹配算法Knuth-Morris-Pratt 算法簡稱為KMP算法。此種算法不僅時間復(fù)雜度良好，而且不需要回溯，這對于處理實時輸入的文本有很大的好處。單模式匹

23、配 算法 1977年，和兩人設(shè)計了一種新的算法簡稱BM算法，該算法可以實現(xiàn)跳躍查尋，大多數(shù)情況下只需掃描文本中的一局部字符。盡管它的時間復(fù)雜度并不是最好，但是實際效果卻常常是最快的。因此，BM算法得到了很好的研究，衍生出許多變種，如Horspool-BM, Tuned-BM和QS等，這些算法至今都是最活潑的算法。 KMP算法是充分利用已經(jīng)比較過的字符信息來提高效率，而BM算法那么是從利用匹配失敗時獲得的信息出發(fā)提高效率，這也是模式匹配算法提高效率的兩條最主要途徑。 BF 算法主要思想：BF算法是出現(xiàn)最早的一種算法，其思想非常簡單：從左向右，依次比較，每次移動一個字符位置。比較方向可以任意選定。

24、無預(yù)處理階段。原理：在主串 s 中從第 i ( i 的 初值為 start)個字符起，并且長度和 t 串相等的子串和 t 比較，假設(shè)相等，那么求得函數(shù)值為 i , 否那么 i 增1 ，直至串 s 中不存在從 i 開始和 t 相等的子串為止。舉例：文本：GCATCGCAGAGAGTATACAGTACG模式：GCAGAGAGFirst attempt GCATCGCAGAGAGTATACAGTACG1234GCAGAGAGSecond attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGThird attempt GCATCGCAGAGAGTATACAGTACG1GC

25、AGAGAGFourth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGFifth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGSixth attempt GCATCGCAGAGAGTATACAGTACG12345678GCAGAGAGSeventh attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGEighth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGNinth attempt GCATCGCAGAGAGTATACAGTACG12GCAGAGAG

26、Tenth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGEleventh attempt GCATCGCAGAGAGTATACAGTACG12GCAGAGAGTwelfth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGThirteenth attempt GCATCGCAGAGAGTATACAGTACG12GCAGAGAGFourteenth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGFifteenth attempt GCATCGCAGAGAGTATACAGTACG1GCAGA

27、GAGSixteenth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGSeventeenth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGKMP算法主要思想：KMP 主要是基于對BF算法的改進：BF算法只是簡單的每次移動一個字符位置，并沒有考慮已匹配成功局部的信息。其實這些信息是可以利用的，此即所謂的“前綴模式-模式中不同局部存在的相同子串。根據(jù)前綴模式可以使模式向前推進假設(shè)干字符位置依前綴模式長度而定，而不只是一個字符，防止了重復(fù)比較，同時也實現(xiàn)了無回朔。 假定試探第j個位置時，匹配失敗發(fā)生在模式字符xi=a ，文本

28、字符 yi+j=b； 當(dāng)轉(zhuǎn)移的時候，模式集的V能夠與文本中的u的一些后綴相匹配，最長的V我們定義為u的邊界標(biāo)記tagged border 。kmpNexti 定義為x0 . i-1 的最長邊界， kmpNext0 定義為-1 。 1 kmpNext0= -1 任何串的第一個字符的kmpNext規(guī)定為-1。2 kmpNextj= -1 模式串T中下標(biāo)為j的字符，如果與首字符相同，且j的前面的k個字符與開頭的k個字符不等(或者相等但Tk=Tj (1kj)。如：T=abCabCad 那么 kmpNext6=-13 kmpNextj=k 模式串T中下標(biāo)為j的字符，如果j的前面k個字符與開頭的k個字符相

29、等，且Tj != Tk 1kj。 即T0T1T2。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1 且Tj != Tk.1kj;如：T=abCabhad ，那么 kmpNext5=2(4) kmpNextj=0 意義：除123的其他情況。舉例：文本：GCATCGCAGAGAGTATACAGTACG模式：GCAGAGAG計算kmpNextii012345678xiGCAGAGAGkmpNexti-100-11-11-11kmpNext表First attempt Shift by: 4 (i-kmpNexti=3- -1)GCATCGCAGAGAGTATACAGTACG1234GCAGAGAG

30、Second attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGShift by: 1 (i-kmpNexti=0- -1)Third attempt GCATCGCAGAGAGTATACAGTACG12345678GCAGAGAGShift by: 7 (i-kmpNexti=8-1)Fourth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGShift by: 1 (i-kmpNexti=1-0)Fifth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGShift by: 1 (i-km

31、pNexti=0- -1)Sixth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGShift by: 1 (i-kmpNexti=0- -1)Seventh attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGShift by: 1 (i-kmpNexti=0- -1)Eighth attempt GCATCGCAGAGAGTATACAGTACG1GCAGAGAGShift by: 1 (i-kmpNexti=0- -1)BM算法 BM算法被盛譽為速度最快的算法。 BM算法的關(guān)鍵是找出不必要的比較。進行比較時從字符串的右端而不

32、是左端開始比較，當(dāng)比較不匹配時，可直接向右移假設(shè)干個位置；當(dāng)被比較的字符相等時，那么繼續(xù)比較其前面的字符。如果成功次數(shù)等于模式串長度，那么匹配成功。主要思想：算法對模式從最右端自右向左掃描。在不匹配或完全匹配時，用兩個預(yù)先計算的函數(shù)bad character和good suffix 來確定指針在正文中移動的距離。BM算法的根本流程:文本串T，長度n。模式串為P，長度設(shè)為m。首先將T與P進行左對齊，然后進行從右向左比較。假設(shè)是某趟比較不匹配時，BM算法就采用兩條啟發(fā)式規(guī)那么，即Bad-Character和Good-Suffix，來計算模式串P向右移動的步長，直到整個匹配過程的結(jié)束。1壞字符規(guī)那么

33、 Bad-characterBM 算法在上圖中從右向左匹配中第一個出現(xiàn)不一致的字符，此時需要采用兩種情況來處理：如果T 中不匹配字符E 在模式P 中沒有出現(xiàn)，那么我們很容易就能理解為E開始的m 長度的字符串不可能匹配到P,我們可以直接把P 跳過E，匹配后面的內(nèi)容。如果E 在模式P 中未進行匹配的字段中出現(xiàn)了，那么以該字符E 進行對齊。壞字符啟發(fā)例如1移動前：模式串：one plus twoe文本串： two plus three equals five移動后：模式串： one plus twoe文本串： two plus three equals five每次比較從開始，從右至左移動。壞字符啟

34、發(fā)例如2移動前：模式串：one plur twoe文本串： two plus three equals five移動后：模式串： one plur twoe文本串： two plus three equals five每次比較從開始，從右至左移動。2好后綴Good Suffix假設(shè)發(fā)現(xiàn)某個字符不匹配的同時，已有局部字符匹配成功，那么按如下兩種情況進行:如果在P中位置t處已經(jīng)匹配局部P在P中某位置t也出現(xiàn)，且位置t的前一個字符與位置t的前一個字符不相同，那么將P右移使t對應(yīng)t所在的位置。如果P中任何位置已經(jīng)匹配局部P沒有再出現(xiàn)，那么找到與P的后綴P相同的P的最長前綴x，向右移動P，使x對應(yīng)剛剛P

35、后綴所在位置好后綴啟發(fā)例如1移動前：模式串：atwo plus two文本串： acount to two hundred thirty移動后：模式串： atwo plus two文本串： acount to two hundred thirty每次比較從開始，從右至左移動。好后綴啟發(fā)例如2移動前：模式串：two plus ltwo文本串： count to ltwo hundred thirty移動后：模式串： two plus ltwo 文本串： count to ltwo hundred thirty每次比較從開始，從右至左移動。Good suffix的思想來源于KMP算法，即一個模式中

36、在不同局部可能又存在相同的子串的性質(zhì)?？梢岳靡呀?jīng)成功完成的字符匹配，把已匹配局部看作整個模式的子模式，考慮模式前面一段中是否有與此子模式相匹配的片斷。這樣，就有可能把模式串向前推更遠的距離在算法中是向前移動文本指針。由于BM算法是從右向左比較的，所以構(gòu)造出的不是前綴數(shù)組，而是后綴數(shù)組。 The good-suffix shift, u re-occurs preceded by a character c different from a.The good-suffix shift, only a suffix of u re-occurs in x.The bad-character sh

37、ift, b occurs in x.The bad-character shift, b does not occur in x.First attempt GAGAGACG1GCATGACATATGAGAGACGCTACG舉例：文本：GCATCGCAGAGAGTATACAGTACG模式：GCAGAGAGSecond attempt GCATCGCAGAGAGTATACAGTACG321GCAGAGAGThird attempt GCATCGCAGAGAGTATACAGTACG87654321GCAGAGAGFouth attempt Fifth attempt GAGAGACG123456

38、78GCATGACATATGAGAGACGCTACGGAGAGACG12345678GCATGACATATGAGAGACGCTACGSixth attempt Seventh attempt GAGAGACG12345678GCATGACATATGAGAGACGCTACGGAGAGACG12345678GCATGACATATGAGAGACGCTACGBF算法 String length: 24 Pattern length: 8 Attempts: 17 Character comparisons: 30KMP算法 Attempts: 8 Character comparisons: 18BM

39、 算法 Attempts: 7 Character comparisons: 15具體實現(xiàn)該算法時，可以設(shè)計查表，表中包含每一個可能比較的字符元素，表中的每個紀(jì)錄存貯的是相應(yīng)字符的移動計數(shù)。壞字符移動表 bmBCi,好后綴移動表 shFitjBad character計算出字符集中每個字符的偏移值bmBCi,對于未在模式中出現(xiàn)的字符，偏移為m,否那么取m-i-1,(其中i為字符在模式中的位置)即取此字符在模式中出現(xiàn)的最右位置和文本中此字符位置對齊，假設(shè)字符未在模式中出現(xiàn)，那么可將模式向前推m個字符位置。 在搜索過程中大多數(shù)情況下只利用了bad-character表，這個表是BM算法的核心，ba

40、d-character思想不僅表達簡練而且非常實用。因為在實際自然語言文本搜索中，字符比較失敗的概率很大，所以出現(xiàn)大距離跳躍的幾率很大，另外隨著模式的變長，可能跳躍的距離也將變長。因此，BM家族算法在實際應(yīng)用中的速度是很快的。 后來的變種如Horspool-BM，Tuned-BM，QS等大都只保存了bad-character思想，所作的工作只是簡化算法實現(xiàn)和提高跳躍幾率，因為在模式匹配中，字符比較是最費時的操作。 多模式匹配算法多模式匹配問題在生物計算、信息檢索及信號處理領(lǐng)域有著非常廣泛的應(yīng)用。最早也是最著名的以線性時間復(fù)雜度解決這個問題的算法是1975年Aho-Corasick提出的AC75

41、；對于單模式還有非常好高效的算法BM77,由BM中的跳躍思想衍生出了許多變種，應(yīng)用于單模式和多模式匹配中。AC算法-有限自動機的多模式匹配算法Aho-Corasick自動機算法簡稱AC自動機1975年產(chǎn)生于貝爾實驗室。該算法應(yīng)用有限自動機巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。是一種樹型有限自動機，包含一組狀態(tài)，每個狀態(tài)用一個數(shù)字代表。狀態(tài)機讀入文本串y中的字符，然后通過產(chǎn)生狀態(tài)轉(zhuǎn)移或者偶爾發(fā)送輸出的方式來處理文本。樹型有限自動機的行為通過三個函數(shù)來指示：轉(zhuǎn)向函數(shù)g，失效函數(shù)f和輸出函數(shù)output。例如：對應(yīng)模式集he, she, his, hers的樹型有限自動機圖1 a 轉(zhuǎn)向函數(shù)g圖1 b 失

42、效函數(shù)f 圖1 c 輸出函數(shù)output AC算法的根本思想是這樣的：在預(yù)處理階段，AC自動機算法建立了三個函數(shù)，轉(zhuǎn)向函數(shù)goto，失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個樹型有限自動機。在搜索查找階段，那么通過這三個函數(shù)的交叉使用掃描文本，定位出關(guān)鍵字在文本中的所有出現(xiàn)位置。此算法有兩個特點，一個是掃描文本時完全不需要回溯，另一個是時間復(fù)雜度為O(n)，時間復(fù)雜度與關(guān)鍵字的數(shù)目和長度無關(guān)。 3. 轉(zhuǎn)向，失效和輸出函數(shù)的構(gòu)建 現(xiàn)在說明如何根據(jù)一個關(guān)鍵字集建立正確的轉(zhuǎn)向、失效和輸出函數(shù)。整個構(gòu)建包含兩個局部，在第一局部確定狀態(tài)和轉(zhuǎn)向函數(shù)，在第二局部我們計算失效函數(shù)。輸出函數(shù)的

43、計算那么是穿插在第一局部和第二局部中完成。 為了構(gòu)建轉(zhuǎn)向函數(shù)，我們需要建立一個狀態(tài)轉(zhuǎn)移圖。開始，這個圖只包含一個代表狀態(tài)0。然后，通過添加一條從起始狀態(tài)出發(fā)的路徑的方式，依次向圖中輸入每個關(guān)鍵字p。新的頂點和邊被參加到圖表中，以致于產(chǎn)生了一條能拼寫出關(guān)鍵字p的路徑。關(guān)鍵字p會被添加到這條路徑的終止?fàn)顟B(tài)的輸出函數(shù)中。當(dāng)然只有必要時才會在圖表中增加新的邊。例如: 對關(guān)鍵字集he, she, his, hers建立轉(zhuǎn)向函數(shù)。 向圖表中添加第一個關(guān)鍵字，得到： 從狀態(tài)0到狀態(tài)2的路徑拼寫出了關(guān)鍵字“he，我們把輸出“he和狀態(tài)2相關(guān)聯(lián)。 添加第二個關(guān)鍵字“she，得到：輸出“she和狀態(tài)5相關(guān)聯(lián)。 增

44、加第三個關(guān)鍵字“his，我們得到了下面這個圖。注意到當(dāng)我們增加關(guān)鍵字“his時，已經(jīng)存在一條從狀態(tài)0到狀態(tài)1標(biāo)記著h的邊了，所以我們不必另外添加一條同樣的邊。輸出“his是和狀態(tài)7相關(guān)聯(lián)的 添加第四個關(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)建，我們對除了h和s外的其他每個字符，都增加一個從狀態(tài)0到狀態(tài)0的循環(huán)。這樣，我們得到了如圖1 a) 所示的狀態(tài)轉(zhuǎn)移圖，這個圖就代表轉(zhuǎn)向函數(shù)。圖1 a)算法1：建立轉(zhuǎn)向函數(shù)g。輸入：關(guān)鍵字集P

45、=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的最短路徑。例如圖1 a)起始狀態(tài)的深度是0，狀態(tài)1和3的深度是1，狀態(tài)2，4，和6的深度是2，等等。 圖1 a)d(0) = 0; d(1) = d(3) = 1; d(2) = d(6) = d(4) = 2 d(8) = d(7) = d(5) = 3; d(9) = 4 計算思路：先計算所有深度是1的狀態(tài)的失效函數(shù)值，然后計算所有深度為2的狀態(tài)，以此類推，直到所有狀態(tài)除了狀態(tài)0，因為它的深度沒有定

46、義的失效函數(shù)值都被計算出。 計算方法：用于計算某個狀態(tài)失效函數(shù)值的算法在概念上是非常簡單的。首先，令所有深度為1的狀態(tài)s的函數(shù)值為f(s) = 0。假設(shè)所有深度小于d的狀態(tài)的f值都已經(jīng)被算出了，那么深度為d的狀態(tài)的失效函數(shù)值將根據(jù)深度小于d的狀態(tài)的失效函數(shù)值來計算。 為了計算深度為d的s狀態(tài)的失效函數(shù)值，我們考慮深度為d-1的狀態(tài)r，存在某個輸入a，使得g(r, a) = s。執(zhí)行以下步驟：Step1：state = f(r)。Step2：記f(s) = g(state, a)0128967345h,shersisshe失效函數(shù)g(r,a)=rstate=f(r)f(r)=g(state,a)

47、d=1 1,3f(1)=0,f(3)=0d=22=g(1,e),state=f(1)=0, f(2)=g(state,e)=06=g(1,i),state=f(1)=0, f(6)=g(state,i)=04=g(3,h),state=f(3)=0, f(4)=g(state,h)=g(0,h)=1失效函數(shù)g(r,a)=rstate=f(r) if g(state,a)=fails state=f(r)f(r)=g(state,a)f(6)=0 f(2)=0 f(4)=1d=38=g(2,r) state=f(2)=0, f(8)=g(state,r)=07=g(6,s) state=f(6)

48、=0,f(7)=g(state,s)=g(0,s)=35=g(4,e) state=f(4)=1,f(5)=g(1,e)=2d=49=g(8,s) state=f(8)=0,f(9)=g(0,s)=3輸出函數(shù)在計算失效函數(shù)的過程中，也更新了輸出函數(shù)。當(dāng)求出f(s) = s時，我們把狀態(tài)s的輸出和狀態(tài)s的輸出合并到一起。對于上面的例子，f(5) = 2。這時，把狀態(tài)2的輸出集，也就是he，增加到狀態(tài)5的輸出集中，這樣就得到了5的新的輸出集合he, she。算法2：建立失效函數(shù)f。輸入：轉(zhuǎn)向函數(shù)g和局部的輸出函數(shù)output。輸出：失效函數(shù)f和完整的輸出函數(shù)output。方法:圖3 建立失效函數(shù)f

49、的偽代碼 4. 轉(zhuǎn)向函數(shù)的構(gòu)建 圖1中樹型自動機的狀態(tài)有0, 1, , 9。某個狀態(tài)通常是0狀態(tài)被指定為起始狀態(tài)。 轉(zhuǎn)向函數(shù)把一個由狀態(tài)和輸入字符組成的二元組映射成另一個狀態(tài)或者一條失敗消息。 圖1 a) 的狀態(tài)圖代表轉(zhuǎn)向函數(shù)g。比方,從0到1標(biāo)記著h 的邊表示g(0, h) = 1，如果缺省箭頭那么表示失敗?？梢?，對除e和i之外的其他輸入字符，都有g(shù)(1, h) = fail。所有的樹型有限自動機都有一個共同的特點，即對任何輸入字符a, 都有g(shù)(0, a) != fail。我們將看到，轉(zhuǎn)向函數(shù)在0狀態(tài)上的這種性質(zhì)確保每個輸入字符都可以在狀態(tài)機的一個操作循環(huán)內(nèi)被處理。 舉個例子，記樹型有限自動

50、機為狀態(tài)機M。狀態(tài)機M利用圖1的函數(shù)去處理輸入文本“ushers，圖4顯示了M在處理文本串時產(chǎn)生的狀態(tài)轉(zhuǎn)移情況?？紤]M在狀態(tài)4，且當(dāng)前輸入字符為e時的操作循環(huán)。由于g(4, e) = 5，狀態(tài)機進入狀態(tài)5，文本指針將前進到下一個輸入字符，并且輸出output(5)。這個輸出說明狀態(tài)機已經(jīng)發(fā)現(xiàn)輸入文本的第四個位置是“she和“he出現(xiàn)的結(jié)束位置。在狀態(tài)5上輸入字符r，狀態(tài)機M在此次操作循環(huán)中將產(chǎn)生兩次狀態(tài)轉(zhuǎn)移。由于g(5, r) = fail，M進入狀態(tài)2 = f(5)。然后因為g(2, r) = 8，M進入狀態(tài)8，同時前進到下一個輸入字符。在這次操作循環(huán)中沒有輸出產(chǎn)生。圖4 掃描“ushers

51、時的狀態(tài)轉(zhuǎn)換序列 記s為狀態(tài)機的當(dāng)前狀態(tài)，a為輸入文本y的當(dāng)前輸入字符。樹型有限自動機的一次操作循環(huán)可以定義如下： 如果g(s, a) = s，那么樹型有限自動機將做一個轉(zhuǎn)向動作。自動機進入狀態(tài)s，而且y的下一個字符變成當(dāng)前的輸入字符。另外，如果output(s)不為空，那么狀態(tài)機將輸出與當(dāng)前輸入字符位置相對應(yīng)的一組關(guān)鍵字。 如果g(s, a) = fail，狀態(tài)機將詢問失效函數(shù)f并且進行失效轉(zhuǎn)移。如果 f(s) = s，那么狀態(tài)機將以s，作為當(dāng)前狀態(tài)，a為當(dāng)前輸入字符重復(fù)這個操作循環(huán)。 算法3：樹型有限狀態(tài)機。輸入：一個字符串y=y1y2y3yn其中yi是一個輸入字符；一臺 包含上述轉(zhuǎn)向函數(shù)

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

53、如果轉(zhuǎn)移失敗那么詢問失效函數(shù)，自動機狀態(tài)轉(zhuǎn)為失效函數(shù)定義的狀態(tài)。每次的狀態(tài)轉(zhuǎn)移都要檢查輸出函數(shù)。AC算法的特點自動機的構(gòu)建是建立在深度優(yōu)先的根底上算法構(gòu)建不受模式集內(nèi)容變化的影響模式集內(nèi)容可動態(tài)變化掃描檢測的時間復(fù)雜度與待測文本長度有關(guān)掃描的效率與模式的長度掃描深度有關(guān)算法構(gòu)建與掃描時存在內(nèi)存浪費AC算法的內(nèi)存占用問題：轉(zhuǎn)向函數(shù)ABCDEFGHIJKLMNOPQRSTUVW0 NULL NULL 1 31 NULL NULL 2 62 NULL NULL 8內(nèi)存的占用ASCII碼集合作為待檢測文本的輸入與模式集呢？每個狀態(tài)的轉(zhuǎn)向函數(shù)至少2564字節(jié)=1K不包括failure，output實際上

54、，大量的轉(zhuǎn)向是指向Null的怎么減少無用轉(zhuǎn)向的內(nèi)存占用呢？AC算法改進轉(zhuǎn)向函數(shù)中引入雙數(shù)組：Base表，Check表Base表：當(dāng)前狀態(tài)的Base值+ASCII輸入=下一個狀態(tài)的偏移。Check表：當(dāng)前狀態(tài)的父狀態(tài)信息父狀態(tài)是唯一的自動機構(gòu)建是建立在廣度優(yōu)先的根底上算法的初始化：轉(zhuǎn)向函數(shù)：Next表，Base表、Check表；output函數(shù)；Failure函數(shù)轉(zhuǎn)向函數(shù)：廣度優(yōu)先Next表Base表Check表output函數(shù)與AC算法一樣Failure函數(shù)與轉(zhuǎn)向函數(shù)一起構(gòu)造Base表、Check表Next為轉(zhuǎn)向函數(shù)表數(shù)組、鏈表，下標(biāo)是位置偏移量，輸出是狀態(tài)值。Base表數(shù)組，下標(biāo)是狀態(tài)值，輸

55、出是Base值。Next表中當(dāng)前狀態(tài)為s，輸入為c時，假設(shè)應(yīng)跳轉(zhuǎn)為狀態(tài)t，狀態(tài)t在Next表中的位置=狀態(tài)S的位置+狀態(tài)S的Base值+輸入c的ASCII碼值。Check表數(shù)組，下標(biāo)是狀態(tài)值，輸出是下標(biāo)狀態(tài)的父狀態(tài)的值。轉(zhuǎn)向函數(shù)： Next表，Base表、Check表Next表初始化，模式集輸入廣度優(yōu)先，模式集中所有模式的第一個輸入作為第一層，考慮構(gòu)建Next表。 ASCII碼輸入可能有256種，就申請256個存儲單元。每個模式的第一個輸入的字符按小到大排序，最小的輸入字符，其在Next表中的偏移量為1，其他的輸入字符按他的位置對應(yīng)相應(yīng)的偏移。0123456789100123cfg如0狀態(tài)有3

56、個輸入c，f，g;Next表Base表： base0=-98Check表：Check1=0 Check2=0; Check3=0 012345678910-98相應(yīng)的查找算法:狀態(tài)S，輸入為C，求跳轉(zhuǎn)狀態(tài)next statet := Next&s+bases + c;ifcheckt = s thennext state := t elsefail endif轉(zhuǎn)向函數(shù)： Next表，Base表、Check表Next表，Base表，Check表的構(gòu)建重復(fù)前面的步驟。模式集中的所有第2個輸入，第3個輸入。每次都從Next的開始局部查找空閑的空間，看是否夠分，如果不夠分，再申請256的空間。Outp

57、ut函數(shù)、 Failure函數(shù)構(gòu)建與AC相同。例子：構(gòu)建模式集he, she, his, hers的有限自動機模式集第一層h,s模式集第二層e,h,i模式集第三層e,s,r模式集第四層s模式集he, she, his, hers012345678910111213141516171819012hsASCII碼h=104;s=115;e=101;i=105;r=114第一層h,sNext表:產(chǎn)生2個新狀態(tài)，狀態(tài)1，2Base表：Base0=-103Check表：Check1=0; Check2=0;ASCII碼h=104;s=115;e=101;i=105;r=114模式集第二層e,h,iNex

58、t表:產(chǎn)生3個新狀態(tài)，狀態(tài)3，4，5Base表：1狀態(tài)：he,hi;Base1=-1002狀態(tài)： sh；Base2=-103Check表：Check3=1; Check4=1; Check5=2;模式集he, she, his, hers012345678910111213141516171819013542hehisASCII碼h=104;s=115;e=101;i=105;r=114模式集第三層e,s,rNext表:產(chǎn)生3個新狀態(tài)，狀態(tài)6，7，8Base表：3狀態(tài)：her; 6狀態(tài)Base3=-1124狀態(tài)： his；7狀態(tài)Base4=-1165狀態(tài)： she；8狀態(tài)Base5=-97Ch

59、eck表：Check6=3; Check7=4; Check8=5;模式集he, she, his, hers012345678910111213141516171819013567482hehrsiesASCII碼h=104;s=115;e=101;i=105;r=114模式集第四層sNext表:產(chǎn)生1個新狀態(tài)，狀態(tài)9Base表：6狀態(tài)：hers; 9狀態(tài)Base6=-111Check表：Check9=6; 模式集he, she, his, hers0123456789101112131415161718190135674892hehrsiess習(xí)題：構(gòu)建模式集he, she, his, h

60、ers的有限狀態(tài)自動機習(xí)題：構(gòu)建模式集them,the,her的有限狀態(tài)自動機基于后綴的多模式匹配如何將BM算法的思想引入到多模式匹配中？WM算法！116如何這種思想應(yīng)用到多模式匹配問題中？如果有多個模式，例如可能要支持成千上萬個模式，那么可能文本中大多數(shù)字符與某些模式最后一個字符相匹配，那么這種移動跳躍的幾率就很小。怎么減小后綴匹配的概率不再一個字符一個字符地匹配，而是按塊，每次匹配B個字符。多模式“合并 ，即要求所有的模式長度相同，計算模式集X的最小模式長度m，以后對模式集處理時只關(guān)注每個模式的前m個字符。 117Wu-Manber算法-快速的多模式匹配算法Wu-Manber算法是92年臺