時間：2022-04-29 17:56:56
序論：在您撰寫匹配算法論文時，參考他人的優秀作品可以開闊視野，小編為您整理的7篇范文，希望這些建議能夠激發您的創作熱情，引導您走向新的創作高度。
關鍵詞串匹配，前綴函數，KMP算法
在計算機科學領域，串的模式匹配（以下簡稱為串匹配）算法一直都是研究焦點之一。在拼寫檢查、語言翻譯、數據壓縮、搜索引擎、網絡入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等應用中，都需要進行串匹配。串匹配就是在主串中查找模式串的一個或所有出現。在本文中主串表示為S=s1s2s3…sn，模式串表示為T=t1t2…tm。串匹配從方式上可分為精確匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改進算法。本文主要在精確匹配方面對KMP算法進行了討論并對它做一些改進以及利用改進的KMP來實現多次模式匹配。
1KMP算法
最簡單的樸素串匹配算法(BF算法)是從主串的第一個字符和模式串的第一個字符進行比較，若相等則繼續逐個比較后續字符，否則從主串的第二個字符起再重新和模式串的第一個字符進行比較。依次類推，直至模式串和主串中的一個子串相等，此時稱為匹配成功，否則稱為匹配失敗。樸素模式匹配算法匹配失敗重新比較時只能向前移一個字符，若主串中存在和模式串只有部分匹配的多個子串，匹配指針將多次回溯，而回溯次數越多算法的效率越低，它的時間復雜度一般情況下為O((n-m+1)m)（注：n和m分別為主串和模式串的長度），最壞的情況下為O(m*n)，最好的情況下為O(m+n)。KMP模式匹配算法正是針對上述算法的不足做了實質性的改進。其基本思想是：當一趟匹配過程中出現失配時，不需回溯主串，而是充分利用已經得到的部分匹配所隱含的若干個字符，過濾掉那些多余的比較，將模式串向右“滑動”盡可能遠的一段距離后，繼續進行比較，從而提高模式匹配的效率，該算法的時間復雜度為O(m+n)。
那么如何確定哪些是多余的比較？在KMP算法中通過引入前綴函數f(x)來確定每次匹配不需要比較的字符，保證了匹配始終向前進行，無須回溯。假設主串為s1s2，sn.，模式串為t1t2，tm.，其中m≦n，從si+1開始的子串遇到一個不完全的匹配，使得：
(1.1)
如果我們能確定一個最小的整數，使得：
(1.2)
其中，所以確定i''''等價于確定k，這里的k值就是我們要求的前綴函數f(x)。由式1.1和1.2中K值與主串s無關，只與給定的模式串t中與主串匹配的q有關，即k=f(q)，
f(q)=max{i|0iq且t[1..i]是t[1..q]的后綴}(1.3)
確定KMP前綴函數的算法如下：
#defineMAXSIZE100
Typedefunsignedcharstring[MAXSIZE+1];//0號單元用來存放串的長度
voidf(sstringt,int*array)
{
m=t[0];//m為當前模式串的長度
array=(int*)malloc((m+1)*sizeof(int));//0號元不用
array[1]=0;k=0;
for(q=2;q<=m;q++)
{while(k>0&&t[k+1]!=t[q])k=array[k];
if(t[k+1]==t[q])k=k+1;
array[q]=k;
}
}
關于KMP算法的前綴函數f(x)的示例見表1。
當模式串中有i個字符串匹配成功，第i+1個字符不匹配時，則從i-f(i)個字符重新開始比較，這樣不僅無須回溯，而且一次可以向前滑動i-f(i)個字符，大大提高了模式匹配的效率。下面給出樸素匹配算法和KMP匹配算法的比較，見表2。
表2樸素匹配算法和KMP匹配算法比較表
樸素算法KMP算法
時間復雜度O((n-m+1)m)O(m+n)
向前移動字符個數1q-f(q)
回溯次數q-1無
其中：n為主串長度，m為模式串長度，q為匹配成功的字符個數
2KMP算法的改進
在KMP算法的實際應用中，發現該算法也存在著不足，結合下面的表一來論述KMP模式匹配算法的改進。假設模式串前4個字符與主串的第i+1..i+4匹配成功，第5個字符匹配失敗，此時前綴函數f(4)=1，下一次匹配將從第i+4開始，并直接將模式串中的第2個字符與主串中的第i+5個字符進行比較，從表1中可知，匹配必將失敗，此次比較是多余的。這說明此時的前綴函數f(x)并不是最優，需要對前綴函數進行改進。實質上，所謂對KMP算法的改進就是對其前綴函數的改進。
4結語
本文給出的算法較樸素匹配算法在效率上有了較大的提高，尤其是對重復字符出現較少的數據段進行模式匹配可取得較高的查找效率。應用于大型數據庫的數據查詢，會更加有效地縮短查找時間。
參考文獻
[1]嚴蔚敏，吳偉民.數據結構[M].清華大學出版社，2001
[2]傅清祥，王曉東.算法與數據結構[M].電子工業出版社，1998
【關鍵詞】深度挖掘匹配算法 畢業論文管理 應用
在畢業論文管理工作不斷加強的情況下，注重管理模式的更新和合理選用，提高匹配算法的針對性，才能真正提高高校教務管理水平。因此，對深度挖掘匹配算法在畢業論文管理中的應用有比較全面的了解，才能為高校教務管理工作提供可靠參考依據。
1 深度挖掘匹配算法的相關分析
根據深度挖掘匹配算法在畢業論文管理中的應用情況進行全面分析來看，其主要包括如下兩個方面：
1.1 志愿自動匹配算法的相關分析
對學生和課題的選擇關系進行合理分析可知，兩者的最優、最大匹配，最好是根據學生的實際情況量身定做，才能真正實現課題與學生的最完美匹配。因此，教師提出相關題目時，需要對學生的情況、特性和要求等進行全面分析，才能在學生對課題的特性、關聯性等有一定了解的情況下，提高課題與學生的匹配概率，最終讓學生選定最合適的課題。在實踐過程中，志愿自動匹配算法的合理運用，需要根據畢業論文的管理流程，從教師出題開始。一般情況下，教師應該先提出大題讓學生自由選擇，在匹配學生確定好以后將大題分成幾個小題，從而將每個小題分配給合適的學生。在這種情況下，教師設定的課題需要從修讀課程達到的分數、難度、所屬類別等多個方面確定，并從教務管理系統中獲取學生的成績和選題積分點等，才能根據分數線來判定學生是否符合相關選題。其中，選題的難度在簡單、一般、難、很難和非常難幾個等級，對應的成績是及格、良好、優秀、極好。在實際進行選題時，學生可以根據自己的情況選擇三個題目作為志愿，以在系統完成匹配后，自定將題目下發給學生。在實踐過程中，初始化志愿顯示的是學生的第一志愿，在經過while、if、else、break、continue等流程后，系統會將題目和學生進行適當分類，以確保題目與學生的匹配最合理、最科學。由此可見，志愿自動匹配算法是優先對具有課題相關能力的學生進行匹配的，在學生人數低于匹配數量的情況下，可繼續為積分點高、能力稍差的學生進行匹配，對于確保課程成績與積分點的完美結合有著極大影響。
1.2 調劑學生算法的相關分析
在經過上述算法進行匹配后，根據學生的實際情況進行深層挖掘，可以實現課題與剩余學生的完美調劑。因此，對上述階段中匹配失敗的學生志愿所選的教師、課題類別、難度等因素進行深度挖掘，并將搜索結果作為匹配課題的依據，才能在縮小搜索范圍的情況下，找到與剩余學生最合適的課題。如果出現相近課題較多的情況，則需要有學生、工作人員共同協商，以確定最終和最適合學生的課堂。在實踐應用中，調劑學生算法的運用需要對需要調劑的學生進行合理分析，并通過if、else、return、while、continue、else等多個流程，才能真正匹配出最適合學生的課題。
2 深度挖掘匹配算法在畢業論文管理中的實際應用
根據深度挖掘匹配算法的實際應用來看，在畢業論文管理中學生可以了解到最適合自己的課題信息，教師可以根據學生的積分點和成績等確定課題，從而避免選擇某一課題的學生過多或過少的情況出現，對于提高第一志愿自動匹配成功率有著極大作用。因此，在實際應用中，注重教師、課題類別、難度的合理設定，確保它們的排序科學，將課堂與學生的匹配關系看作是二分圖，并且，每個學生可以選擇的課題有三個，系統可以根據學生的實際情況進行自動匹配，最終深度挖掘與學生志愿匹配的課題。例如：志愿自動匹配和調劑學生的總數都為102人，通過深度挖掘匹配算法匹配成功的人數分別為72人和90人，成功率達到了70%、88%。在不使用任何算法進行匹配的情況下，兩者的成功率是52%左右。由此可見，在畢業論文管理系統中，深度挖掘匹配算法在科學應用，可以為教務管理工作提供可靠參考依據，對于提高畢業論文管理工作人員的工作效率有著重要影響。
3 結語
綜上所述，在深度挖掘匹配算法不斷推廣的情況下，其在畢業論文管理中的實際應用受到了很多教務管理工作人員的青睞。因此，充分發揮深度挖掘匹配算法的作用，提高深度挖掘匹配算法在畢業論文管理中的應用效果，才能更好的滿足學生的選題需求。
參考文獻
[1]馮麗慧，馮立智.數據挖掘在畢業論文成績管理中的應用研究[J].電腦知識與技術，2012，30：7150-7153.
[2]徐章韜.用信息技術深度挖掘課程內容――以數學學科為例[J].教育發展研究，2015，12：29-33.
[3]連伊娜.深度挖掘高校檔案文化內涵，更好為教育事業發展服務[J].黑龍江史志，2013，11：104-105.
作者簡介
劉冰潔（1983-），女，江西省南昌市人。工程碩士學位?，F為江西交通職業技術學院副教授。研究方向為大數據、系統集成、智能化技術。
【關鍵詞】藏文分詞 匹配算法 哈希表 詞典機制
1 引言
藏文信息處理存在著分詞的問題，而藏文分詞是對藏文詞性標注、藏語音合成、機器翻譯、大型語料庫建設和信息檢索等藏文信息處理的基礎。藏文分詞的效果會對進一步研究的藏文詞性標注、藏語音合成、機器翻譯、大型語料庫建設和信息檢索等藏文信息處理軟件的性能和效果產生影響。
為了提高分詞的準確率，需要有一個足夠大的詞庫，面對足夠大的詞庫，對詞庫中的詞語的搜索技術就顯得十分重要，對詞庫中詞語的搜索速度直接關系到分詞系統的性能。詞庫目前主要是采用索引的機制來實現的，一般用到的索引結構的包括線性索引、倒排表、Trie樹、二叉樹等。線性索引、倒排表都是靜態的索引結構，不利于插入、刪除等操作。
2 分詞
2.1 詞典機制算法
本系統采用的是基于Hash索引的分詞詞典。分詞詞典機制可以看作包含三個部分：首字Hash表、詞索引表、詞典正文。詞典正文是以詞為單位txt文件，匹配過程是一個全詞匹配的過程。首先，通過首字Hash表確定該詞在詞典中的大概位置，然后根據詞索引表進行定位，進而找到在詞典正文中的具置。該系統是采用Myeclipse10平臺，使用Java語言進行實現的，直接調用Java里的hashmap創建函數，找到該詞之后，然后進行字符串匹配。
2.2 基于匹配算法分詞
主流的分詞方法有三種：分別為基于語言學規則的方法、基于大規模語料庫的機器學習方法、基于規則與統計相結合的方法，鑒于目前藏文方面還沒有超大型的句子語料庫。該系統便采用了基于語言學規則的根據詞典進行匹配的方法對藏文進行分詞。
根據匹配的方向不同，分為正向和逆向兩種匹配算法。本系統采用的是正逆向匹配算法相結合的減字匹配法對藏文進行分詞的，因為藏文在每個字的結束時，都會以“”作為分界；每個句子會以“”或者“” 作為分界。因此，對藏文進行分詞的減字算法首先以藏文的字符“”或者“”切分出句子，如此一來，原文就被分為相應的若干個句子了。接下來，再對每一個句子進行詞典的匹配，如果沒有匹配成功就根據藏文字符中“”從句末尾減去一個字符，然后再次進行匹配，直到匹配成功為止。對每個句子重復這些流程，直到每個句子全部分解為詞為止。逆向最大匹配是從句子的末尾選擇計算最大詞的長度，從后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。
為了提高切分的精度，該系統使用的是正向最大匹配和逆向最大匹配相結合的方法進行分詞，先分別采用兩種方法分詞，然后根據概率比較兩種分詞結果，選擇概率較大的那種匹配算法作為分詞結果。
本系統的逆向最大匹配和正向最大匹配均是采用減字匹配算法，減字算法實現簡單，切分效果也比較理想，流程如圖1所示。
正向最大匹配（MM） 對于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判別CD是否屬于W，若是，則就切分為AB/CD，如果不是，則切分為AB/C/D。其中W 為分詞的詞典。逆向最大匹配對于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W為分詞的詞典，那么就取切分 AB/CD，根據藏文詞組最長的為6個字符組成的，所以進行匹配算法的時候，初始化藏文最大字符串長度為6，流程圖如圖2所示。而逆向最大匹配算法是從句子的末尾開始進行匹配，其核心算法與正向最大匹配算法相同，只不過開始匹配的方向不同而已。
無論是正向匹配（MM）算法還是逆向匹配（RMM）算法都會產生大量的歧義字段。我們很容易舉出這樣的例子，如：（五十六個民族心連心）這一句藏語，采用正向匹配算法分詞的結果為：，采用逆向匹配算法的分詞結果為：，在采用逆向匹配的時候，將會被劃分為，而（五十六）實際是一個詞，不該劃分，諸如此類的藏文句子還有很多，例如 等，無論使用正向最大匹配算法或者使用逆向最大匹配算法都會產生歧義，這種歧義稱為組合歧義。為了減少這種歧義的影響，本系統使用兩種分詞方法相結合的方式。首先分別使用兩種算法進行分詞，然后通過統計的方法消除部分歧義。具體實現為：設正向最大匹配算法所切分的n個詞分別為，則這個句子切分的頻率則為；設逆向最大匹配算法所切分的n個詞分別為，則這個句子切分的頻率則為。如果，則選擇正向最大匹配算法所切分的結果，反之，則選擇逆向最大匹配算法所切分的結果。
3 結果和分析
結合26個大小不同的實驗文本，對基于哈希表索引和匹配算法的分詞系統的準確率進行了分析，準確率如圖3所示。結果顯示，該分詞系統的準確率在92%以上。由此可得基于哈希表索引和匹配算法的分詞系統在準確率上有不錯的效果。
參考文獻
[1]華卻才讓.基于樹到串藏語機器翻譯若干關鍵技術研究[D].陜西師范大學，2014.
[2]石方夏，邱瑞，張|，任帥.藏文信息隱藏技術綜述[J].物聯網技術，2014，12：28-32.
[3]王思力，張華平，王斌.雙數組Trie樹算法優化及其應用研究[J].中文信息學報，2006，05：24-30.
[4]陳碩，桂騰葉，周張穎等.信息檢索在論文寫作和項目申報中的應用[J].科技展望，2015，13：274-275.
[5]黃昌寧，趙海.中文分詞十年回顧[J]. 中文信息學報，2007，03：8-19.
[6]奉國和，鄭偉.國內中文自動分詞技術研究綜述[J].圖書情報工作，2011，02：41-45.
[7]賀艷艷.基于詞表結構的中文分詞算法研究[D].中國地質大學（北京），2007.
[8]戴上靜，石春，吳剛.中文分詞中的正向增字最大匹配算法研究[J].微型機與應用，2014，17：15-18.
[9]劉遙峰，王志良，王傳經.中文分詞和詞性標注模型[J].計算機工程，2010，04：17-19.
作者簡介
陳碩（1995-），男，自治區拉薩市人。本科在讀，主研領域為自然語言處理，數學建模及其應用。
周歡歡（1994-），女，湖南省衡陽市人。本科在讀，研究方向為數學建模及其應用、交通運輸規劃與管理。
通訊作者簡介
趙棟材（1976-），男，現為大學藏文信息技術研究中心副教授。主要研究方向為藏文信息處理。
作者單位
關鍵詞：Rete算法，智能防火墻，規則，快速，匹配
Rete算法是一個快速的模式匹配算法，它通過形成一個Rete網絡進行模式匹配，利用基于規則的系統的兩個特征，即時間冗余性（Temporalredundancy）和結構相似性（structural similarity），提高系統模式匹配效率。
一、模式匹配的基本概念
1、可滿足規則：一個規則稱為可滿足的，若規則的每一模式均能在當前工作存儲器中找到可匹配的事實，且模式之間的同一變量能取得統一的約束值。形式化地說，規則
if P1,P2,…Pmthen A1,A2,…An
稱為可滿足的，若存在一個通代σ，使得對每一個模式Pi，在工作存儲器中有一個元素Wi滿足
Piσ=Wii=1,2,3 …m
這里，σ作用在某個模式的結果稱為模式實例，σ作用在整個規則的結果稱為規則實例。在專家系統中，可滿足的規則稱為標志規則。
2、沖突集：由全體規則實例構成的集合稱為沖突集，也稱上程表。免費論文參考網。
3、模式匹配算法的任務是：給定規則庫，根據工作存儲器的當前狀態，通過與規則模式的匹配，把可滿足規則送入沖突集，把不可滿足的規則從沖突集中刪去。
二、Rete算法的依據和基本思想
Rete算法快速匹配的重要依據是：
1、時間冗余性。免費論文參考網。工作存儲器中的內容在推理過程中的變化是緩慢的，即在每個執行周期中，增刪的事實只占很小的比例，因此，受工作存儲器變化而影響的規則也只占很小的比例。由產生式系統的折射性，只要在每個執行周期中記住哪些事實是已經匹配的，需要考慮的就僅僅是修改的事實對匹配過程的影響。
2、結構相似性。許多規則常常包含類似的模式和模式組。
Rete算法的基本思想是：保存過去匹配過程中留下的全部信息，以空間代價來換取產生式系統的執行效率。
三、Rete匹配網絡結構與過程
Rete算法的核心是建立Rete匹配網絡結構，其由模式網絡和連接網絡兩部分構成。其中，模式網絡記錄每一模式各域的測試條件，每一測試條件對應于網絡的一個域結點，每一模式的所有域結點依次連起來，構成模式網絡的一條匹配鏈。
Rete網絡匹配過程由模式網絡上的模式匹配和連接網絡上的部分匹配構成。在模式網絡的機器內部表示中，我們把共享一個父結點的所有結點表示成一條共享鏈。同時，把每一模式匹配鏈中的結點表示成一條下拉鏈，于是，每一結點由共享鏈和下拉鏈指向其后繼結點，模式網絡就是一棵可以使用典型遍歷算法進行測試的二叉樹。
四、智能防火墻Rete算法設計
Rete快速匹配算法，函數Rete設計為:取IP地址、端口號各部分折疊、異或運算后，以Rete長度取模。免費論文參考網。算法如下(無關或部分無關稱為集合A，相關、包含相等和相等的稱為集合B):
1、Addr=sa+da sa:源地址 da:目的地址
2、Port=sp+dp sp:源端口號 dp:目的端口號
int Rete(long addr, int port)
{int addrxor,key；\地址折疊異或
addrxor=(addr&～(～0﹤﹤16))∧((addr﹥﹥16)&～(～0﹤﹤16))；
key=addrxor∧port； \與端口異或
return(key % max)； }\max為Rete表長度
防火墻初始化時，首先從規則集A用該散列函數構造Rete表R為
Void Initialization(RULE-SET A){
FOR(r∈A)DO{ \r為每條規則
idx=Rete(r.addr,r.port)；
R[idx]=&r； \R代表規則集合A
}}
因為Rete表的長度有限，但是如果設計太大會浪費存儲空間，也降低了查找速度，所以免不了會出現沖突。解決沖突的方法是:如果兩條規則經過散列后落到同一位置，則把這兩條規則按照插入順序組成一個鏈表結構。主要算法如下:
if(R[Rete(r.addr,r.port)]=NULL)\R為Rete表,r為規則
R[Rete(r.addr,r.port)]=&r；\沒有沖突，則插入Rete表
Else{J=R[Rete(r.addr,r.port)]；\沖突解決方法
while (j->next!=NULL) {j=j->next；} \插入鏈表末尾
j->next=&r;}
數據包匹配流程：當防火墻收到一個數據包以后，用算法Match查找規則集(A和B)。
Match(IP-Packet p) { \p為數據包
Int idx=Rete(p.addr,p.port) ； \首先用Rete算法查找A類規則
IF (R[idx].addr≧p.addr&& R[idx].port=p.port) \找到匹配規則
return R[idx] ；
Else {int idex I =halfquery(p.addr) ； \利用折半查找索引表
J=L[indexl] ； \L代表規則集合B
While(j!=NULL){\順序匹配找到的規則鏈
IF (Matchrule(p)) return j； \ Matchrule為規則匹配函數
Else j=j->next；
}}
Return(Norulematch)；
}
參考文獻：
[1] 閆麗萍，潘正運. RETE算法的改進與實現.微計算機信息，2006 (36）
[2] 龐偉正，金瑞琪，王成武. 一種規則引擎的實現方法.哈爾濱工程大學學報，2005(03)
[3] 江建國，張景中. 基于Rete算法的幾何自動推理系統. 四川大學學報（工程科學版）， 2006(03)
關鍵詞：雙目視覺 立體匹配 導航定位 機器人
中圖分類號：TP242 文獻標識碼：A 文章編號：1007-9416(2011)12-0059-02
引言
雙目視覺是一種通過兩幅圖像獲取物體三維信息的方法，具有通過二維圖像認知物體三維立體信息的能力，其關鍵技術就是要解決兩幅圖像中對應點的匹配問題［1］。立體匹配一直都是機器視覺領域中的難點和熱點，論文根據結合變電站及巡檢機器人雙目視覺系統的特點，運用匹配輔助區域匹配算法實現立體匹配，獲得密集準確的深度圖。
1、立體匹配原理
立體匹配基于視差原理，如圖1所示。其中基線距B=兩攝像機的投影中心連線的距離；攝像機焦距為f。設兩攝像機在同一時刻觀看空間物體的同一特征點，分別在“左眼”和“右眼”上獲取了點的圖像，它們的圖像像素坐標分別為
采用平行攝像機模型，兩攝像機的圖像在同一個平面上，并且特征點p的圖像坐標y坐標在左右圖像平面上相同，
可以得到：
要想根據左右圖像對完成立體匹配任務，就把只需計算左右圖像對的立體視差，立體視差是景物點在左右圖像中圖像像素的橫坐標之差，即：
從而就可以建立立體視差圖(又稱深度圖)。所建立的立體視差圖可以細分為兩個子區域，零視差子區域和非零視差子區域，零視差子區域為機器人可以自由行走的無障礙平坦區域；非零視差子區域為平坦區域上的凸出區域，可能是障礙物存在的區域。
根據式(3)及立體視差原理，可以方便地計算世界坐標下的特征點在攝像機坐標系下的三維坐標：
左攝像機像面上的任意一點只要能在右攝像機像面上找到對應的匹配點，就可以確定出該點的三維坐標。這種方法是完全的點對點運算，像面上所有點只要存在相應的匹配點，就可以根據式(5)計算出對應的三維坐標。
2、立體匹配設計
經過圖像預處理，可以為立體匹配提供較理想立體圖像對，降低了匹配算法的難度。論文結合變電站、檢機器人雙目視覺系統的特點，運用特征輔助區域匹配算法實現立體匹配，該算法結合特征匹配算法及區域匹配算法的優點，可以在計算量不大的情況下，生成密集準確的立體視差圖。
算法的總體上分三步：
2.1 匹配初始化階段
匹配初始化階段需要完成以下工作：對雙目攝像機參數的標定；對攝像機所采用的圖像運用高斯―拉普拉斯模板進行圖像預處理；對預處理的圖像運用加速主成分分析法實現圖像的特征提?。贿@些過程都是為后面的立體匹配做準備，為之提供較理想的立體圖像對。
2.2 特征匹配階段
根據各種匹配準則縮小匹配點的搜索范圍，利用特征匹配算法確定正確的匹配點。
2.3 區域匹配階段
由于前面特征提取算法限制，不可能把景物所有特征點全部提取到，所以特征點匹配完成后，還存在一些有價值的非特征點未被匹配。但是這些未被匹配點被已匹配點限制在較小的范圍內，對這些小范圍點的匹配就是區域匹配算法的工作。
對多個可能的候選匹配點比較時，可能使用的依據有灰度、曲率、拉普拉斯變換、梯度等。結合變電站實際環境，運用連續性約束準則和灰度、x方向的灰度梯度、梯度方向唯一確定匹配點［2］。思路如下：
①┍算視覺連續性約束相關系數
其中d為已匹配點的視差均值，d為當前候選匹配點的視差。若，1為預先設定視覺連續性約束相關系數閾值，排除此候選匹配點，重復執行此步直到時，執行第2步；否則直接執行第2步執行。
②計算候選匹配點與待匹配點的灰度相關值Vcorr、x方向的灰度梯度接近程度系數Kgard_r、梯度方向相關系數式(7)-(8)中，K_gard_x、K_gard_y為基準圖像上特征點x和y方向的梯度，Rgrad_x、Rgrad_y為候選匹配點x和y方向的梯度，fl、fr為左右圖像的灰度函數，、為特征點和候選匹配點在窗口(2N+2M+1)中灰度均、為兩點在窗口中灰度標準差。若有Vcorr
③計算總判斷依據
計算出所有候選匹配點的Iall值，其Iall值最大者即認為是最佳候選匹配點，即特征點Pleft在右圖像中的匹配點。
要匹配固定大小的圖像窗口中的像素，相似約束準則是兩幅圖像在窗口中的相關性度量，當被搜索區域的點與待匹配點間相似約束準則最大化時，認為搜索區域的點是待匹配點的匹配點［3］。
設有立體圖像對IMG1、IMGr，Pl、Pr為兩幅圖像中的像素點，相關窗口大小為，為圖像IMGl中像素點Pl在圖像3、實驗與結果
圖2中左右兩圖像，是左右攝像機對同一景物拍攝所得。
根據上圖的左右兩圖，運用立體匹配算法求得立體視差圖。實驗結果如圖3所示，其中左圖像素深度圖，右圖是對左圖經median處理后的效果圖，看起來對左圖清晰了不少，但不能顯示真實圖像視差關系。此算法消耗較長時間，將在以后工作中改進。
參考文獻
［1］楊俊,賈秀芳.變電站防火防盜圖像識別的研究.中國高等學校電力系統及其自動化專業第20屆學術年會，2004.7.
［2］林琳.機器人雙目視覺定位技術研究［D］．西安電子科技大學碩士學位論文,2009.
［3］薛長松．基于DM642的雙目視覺控制系統研究［D］.河南大學碩士學位論文,2007.
>> 算法與模型 快速圖像匹配算法及其水下導航應用 芻議華帝戰略選擇與匹配 入侵檢測模式匹配算法的研究與改進 論文相似度匹配算法的研究與實現 字符串匹配算法比較與分析 正向最大匹配分詞算法的分析與改進 基于模擬退火算法的P2P借貸平臺的債權匹配模型 基于輪廓特征點的三維模型相似性匹配算法 一種基于語言學特征的本體匹配改進算法 動作與音樂的節奏特征匹配模型研究 基于SIFT算法與RANSAC算法的X射線圖像匹配研究 電影語言與影片風格的匹配問題 基于啟發式算法的品牌模型的選擇 軟件可靠性模型選擇的SRMS算法 雙目立體視覺區域局部匹配算法的改進及其實現 軟件工程過程模型及其選擇 混合Copula模型選擇及其應用 模式匹配查詢算法研究 指紋快速匹配算法研究 常見問題解答 當前所在位置：l 德國
[4]
ZAKI T， ESSAADY Y， MAMMASS D， et al. A hybrid method ngramsTFIDF with radial basis for indexing and classification of Arabic document [J]. International Journal of Software Engineering and Its Applications， 2014， 8（2）： 127-144.
[5]
SIDOROV G， VELASQUEZ F， STAMATATOS E， et al. Syntactic dependencybased ngrams as classification features [C]// MICAI 2012： Proceedings of the 11th Mexican International Conference on Artificial Intelligence， LNCS 7630. Berlin： Springer， 2013： 1-11.
[6]
YI Y， GUAN J， ZHOU S. Effective clustering of microRNA sequences by ngrams and feature weighting [C] // Proceedings of the 2012 IEEE 6th International Conference on Systems Biology. Piscataway： IEEE， 2012： 203-210.
[7]
BOURAS C， TSOGKAS V. Enhancing news articles clustering using word ngrams [C] // DATA 2013： Proceedings of the 2nd International Conference on Data Technologies and Applications. London： dblp Computer Science Bibliography， 2013： 53-60.
[8]
GHANNAY S， BARRAULT L. Using hypothesis selection based features for confusion network MT system combination [C] // EACL 2014： Proceedings of the 3rd Workshop on Hybrid Approaches to Translation （HyTra）. Stroudsburg： Association for Computational Linguistics， 2014： 2-6.
[9]
SIDOROV G， VELASQUEZ F， STAMATAOS E， et al. Syntactic ngrams as machine learning features for natural language processing [J]. Expert Systems with Applications， 2014， 41（3）： 853-860.
[10]
HAN Q， GUO J， SCHTZE H. CodeX： combining an SVM classifier and character ngram language models for sentiment analysis on Twitter text [C]// SemEval 2013： Proceedings of the Second Joint Conference on Lexical and Computational Semantics （*SEM）， Volume 2： Proceedings of the Seventh International Workshop on Semantic Evaluation. Stroudsburg： Association for Computational Linguistics， 2013： 520-524.
http：//p.nus.edu.sg/～antho/S/S13/S13-2086.pdf
[11]
BESPALOY D， BAI B， QI Y， et al. Sentiment classification based on supervised latent ngram analysis [C] // CIKM 11： Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 375-382.
[12]
MILLER Z， DICKINSON B， HU W. Gender prediction on Twitter using stream algorithms with ngram character features [J]. International Journal of Intelligence Science， 2012， 2（4A）： 143-148.
[13]
WRIGHT J， LLOYDTHOMAS H. A robust language model incorporating a substring parser and extended ngrams [C] // ICASSP 1994： Proceedings of the 1994 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 1994： 361-364.
[14]
HACIOGLU K， WARD W. Dialogcontext dependent language modeling combining ngrams and stochastic contextfree grammars [C] // ICASSP 2001： Proceedings of the 2001 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 2001， 1： 537-540.
[15]
SIU M， OSTENDORF M. Variable ngrams and extensions for conversational speech language modeling [J]. Speech and Audio Processing， 2000， 1（8）： 63-75.
[16]
ZHOU S， GUAN J， HU Y， et al. A Chinese document categorization system without dictionary support and segmentation processing [J]. Journal of Computer Research and Development， 2001， 38（7）： 839-844. （周水庚，關佶紅，胡運發，等.一個無需詞典支持和切詞處理的中文文檔分類系統[J].計算機研究與發展，2001，38（7）：839-844）
[17]
GAO Z， LI X. Feature extraction method based on sliding window application in text classification[J]. Science & Technology Information， 2008（34）： 23-24. （高振峰，李錫祚.基于滑動窗口的特征提取方法在文本分類中的應用[J].科技信息：學術版，2008（34）：23-24.）
[18]
PENG H， LONG F， DING C. Feature selection based on mutual information： criteria of maxdependency， maxrelevance， and minredundancy [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（8）： 1226-1238.
關鍵詞：入侵檢測；模式匹配；算法。
中圖分類號：TP309.08 文獻標識碼：A 文章編號：1007-9416（2013）06-0135-02
1 引言
在基于主機入侵檢測技術中，應用比較多的是誤用檢測技術，其核心多采用字符串搜索算法模式匹配技術。通過對目前廣泛應用的BM算法[1]和AC_ BM算法[2]的分析，提出基于AC_ BM算法的改進的多模式匹配算法NAC_ BM算法。該算法綜合了BM算法和AC_ BM算法的優點，改進了BM算法跳躍步長，使得每次匹配獲得最大的步長，同時應用AC算法有限狀態機模式匹配自動機構造模式樹，匹配過程中移動模式樹，減少了規則匹配次數，為基于主機的入侵檢測模式匹配技術提供了一種優化方法。
2 多模式字符串匹配算法
由于BM算法是一種單模式字符串匹配算法，它每次只能完成對一個模式的匹配工作，效率較低。雖然研究者對BM改進算法很多，但是這些算法都沒有改變BM算法的基本思想，因此不能解決效率問題。
為了提高效率，研究者提出了多模式匹配問題[3]，多模式匹配問題可以抽象描述為：設是一個模式集合，模式串Pi 中的字母來自于一個固定的字母表。多模式匹配問題是發現P中所有模式在文本T中的所有出現，。
3 AC_BM算法的改進—NAC_BM算法
4 仿真實驗分析
為了對各個算法的性能、效率做具體的評測，在同一臺計算機上分別對單模式匹配算法和多模式匹配算法進行了仿真測試。
在本測試中采用的搜索文件是來自麻省理工學院林肯實驗室提供的“1999DARPA入侵檢測測試數據集”[4]，長度為10000000Bytes的文本，而匹配的模式串是隨機抽取的。
由于對于單模式和多模式而言，各有其不同的特點，比如對于單模式匹配算法，它的時
間開銷與模式串的個數成正比，不能用它們解決多模式匹配的性能問題。而對于絕大多數多模式匹配算法都要在執行搜索操作前，對模式串集合進行預處理，構造某種數據結構，以便為搜索過程提供支持；相對于單模式匹配算法對空間需求可以根據模式串的長度而估算出來。本實驗對匹配的模式個數對各種匹配算法性能的影響進行了仿真并給出對比分析。
圖5中“*”號表示該項未測試。對于模式串為1（即單模式串）時，AC算法、AC_BM算法和NAC_BM算法沒有必要測試它們對單模式匹配的性能。當模式個數大于1時，多模式匹配算法掃描對象文本一遍，而單模式匹配算法則要掃描對象文本多遍，即對每一個模式串掃描一遍對象文本。對于模式串個數為1000時，對單模式匹配算法是十分費時，且其耗費時間也可估算出來。
從圖5的結果來看，多模式匹配算法比單模式匹配算法的匹配速度快得多。三種多模式匹配算法仍然比其他單模式匹配算法速度快，而且AC_ BM算法和NAC_ BM算法比AC算法快，這兩個算法隨著模式串數目的增加，所耗費的時間僅有很小的增加，而不是成比例地增長。從表中可以看出，NAC_ BM算法比AC_BM算法在效率上有一定程度的提高。
5 結語
本文提出了一種改進的AC_BM算法：NAC_BM算法。該算法一是在BM算法的基礎上，改進了跳躍步長，使得每次匹配獲得最大的步長，二是應用AC算法有限狀態機模式匹配自動機構造模式樹，匹配過程中移動模式樹，減少了規則匹配次數。最后通過仿真實驗對比得知：NAC_BM算法效率優于BM和AC_BM算法。
參考文獻
[1]A Pattern Matching Model for Misuse Intrusion Detection[A]. Sandeep Kumar， Eugene Spafford. In Proceedings of the 17th National Computer Security Conference[C]，1995， 11-21.
[2]楊武，方濱興，云曉春等.入侵檢測系統中高效模式匹配算法的研究.計算機工程，2004，30（13）.92-94.
