時(shí)間：2022-04-29 17:56:56
序論：在您撰寫匹配算法論文時(shí)，參考他人的優(yōu)秀作品可以開闊視野，小編為您整理的7篇范文，希望這些建議能夠激發(fā)您的創(chuàng)作熱情，引導(dǎo)您走向新的創(chuàng)作高度。
關(guān)鍵詞串匹配，前綴函數(shù)，KMP算法
在計(jì)算機(jī)科學(xué)領(lǐng)域，串的模式匹配（以下簡稱為串匹配）算法一直都是研究焦點(diǎn)之一。在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測、計(jì)算機(jī)病毒特征碼匹配以及DNA序列匹配等應(yīng)用中，都需要進(jìn)行串匹配。串匹配就是在主串中查找模式串的一個(gè)或所有出現(xiàn)。在本文中主串表示為S=s1s2s3…sn，模式串表示為T=t1t2…tm。串匹配從方式上可分為精確匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改進(jìn)算法。本文主要在精確匹配方面對(duì)KMP算法進(jìn)行了討論并對(duì)它做一些改進(jìn)以及利用改進(jìn)的KMP來實(shí)現(xiàn)多次模式匹配。
1KMP算法
最簡單的樸素串匹配算法(BF算法)是從主串的第一個(gè)字符和模式串的第一個(gè)字符進(jìn)行比較，若相等則繼續(xù)逐個(gè)比較后續(xù)字符，否則從主串的第二個(gè)字符起再重新和模式串的第一個(gè)字符進(jìn)行比較。依次類推，直至模式串和主串中的一個(gè)子串相等，此時(shí)稱為匹配成功，否則稱為匹配失敗。樸素模式匹配算法匹配失敗重新比較時(shí)只能向前移一個(gè)字符，若主串中存在和模式串只有部分匹配的多個(gè)子串，匹配指針將多次回溯，而回溯次數(shù)越多算法的效率越低，它的時(shí)間復(fù)雜度一般情況下為O((n-m+1)m)（注：n和m分別為主串和模式串的長度），最壞的情況下為O(m*n)，最好的情況下為O(m+n)。KMP模式匹配算法正是針對(duì)上述算法的不足做了實(shí)質(zhì)性的改進(jìn)。其基本思想是：當(dāng)一趟匹配過程中出現(xiàn)失配時(shí)，不需回溯主串，而是充分利用已經(jīng)得到的部分匹配所隱含的若干個(gè)字符，過濾掉那些多余的比較，將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較，從而提高模式匹配的效率，該算法的時(shí)間復(fù)雜度為O(m+n)。
那么如何確定哪些是多余的比較？在KMP算法中通過引入前綴函數(shù)f(x)來確定每次匹配不需要比較的字符，保證了匹配始終向前進(jìn)行，無須回溯。假設(shè)主串為s1s2，sn.，模式串為t1t2，tm.，其中m≦n，從si+1開始的子串遇到一個(gè)不完全的匹配，使得：
(1.1)
如果我們能確定一個(gè)最小的整數(shù)，使得：
(1.2)
其中，所以確定i''''等價(jià)于確定k，這里的k值就是我們要求的前綴函數(shù)f(x)。由式1.1和1.2中K值與主串s無關(guān)，只與給定的模式串t中與主串匹配的q有關(guān)，即k=f(q)，
f(q)=max{i|0iq且t[1..i]是t[1..q]的后綴}(1.3)
確定KMP前綴函數(shù)的算法如下：
#defineMAXSIZE100
Typedefunsignedcharstring[MAXSIZE+1];//0號(hào)單元用來存放串的長度
voidf(sstringt,int*array)
{
m=t[0];//m為當(dāng)前模式串的長度
array=(int*)malloc((m+1)*sizeof(int));//0號(hào)元不用
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;
}
}
關(guān)于KMP算法的前綴函數(shù)f(x)的示例見表1。
當(dāng)模式串中有i個(gè)字符串匹配成功，第i+1個(gè)字符不匹配時(shí)，則從i-f(i)個(gè)字符重新開始比較，這樣不僅無須回溯，而且一次可以向前滑動(dòng)i-f(i)個(gè)字符，大大提高了模式匹配的效率。下面給出樸素匹配算法和KMP匹配算法的比較，見表2。
表2樸素匹配算法和KMP匹配算法比較表
樸素算法KMP算法
時(shí)間復(fù)雜度O((n-m+1)m)O(m+n)
向前移動(dòng)字符個(gè)數(shù)1q-f(q)
回溯次數(shù)q-1無
其中：n為主串長度，m為模式串長度，q為匹配成功的字符個(gè)數(shù)
2KMP算法的改進(jìn)
在KMP算法的實(shí)際應(yīng)用中，發(fā)現(xiàn)該算法也存在著不足，結(jié)合下面的表一來論述KMP模式匹配算法的改進(jìn)。假設(shè)模式串前4個(gè)字符與主串的第i+1..i+4匹配成功，第5個(gè)字符匹配失敗，此時(shí)前綴函數(shù)f(4)=1，下一次匹配將從第i+4開始，并直接將模式串中的第2個(gè)字符與主串中的第i+5個(gè)字符進(jìn)行比較，從表1中可知，匹配必將失敗，此次比較是多余的。這說明此時(shí)的前綴函數(shù)f(x)并不是最優(yōu)，需要對(duì)前綴函數(shù)進(jìn)行改進(jìn)。實(shí)質(zhì)上，所謂對(duì)KMP算法的改進(jìn)就是對(duì)其前綴函數(shù)的改進(jìn)。
4結(jié)語
本文給出的算法較樸素匹配算法在效率上有了較大的提高，尤其是對(duì)重復(fù)字符出現(xiàn)較少的數(shù)據(jù)段進(jìn)行模式匹配可取得較高的查找效率。應(yīng)用于大型數(shù)據(jù)庫的數(shù)據(jù)查詢，會(huì)更加有效地縮短查找時(shí)間。
參考文獻(xiàn)
[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2001
[2]傅清祥，王曉東.算法與數(shù)據(jù)結(jié)構(gòu)[M].電子工業(yè)出版社，1998
【關(guān)鍵詞】深度挖掘匹配算法 畢業(yè)論文管理 應(yīng)用
在畢業(yè)論文管理工作不斷加強(qiáng)的情況下，注重管理模式的更新和合理選用，提高匹配算法的針對(duì)性，才能真正提高高校教務(wù)管理水平。因此，對(duì)深度挖掘匹配算法在畢業(yè)論文管理中的應(yīng)用有比較全面的了解，才能為高校教務(wù)管理工作提供可靠參考依據(jù)。
1 深度挖掘匹配算法的相關(guān)分析
根據(jù)深度挖掘匹配算法在畢業(yè)論文管理中的應(yīng)用情況進(jìn)行全面分析來看，其主要包括如下兩個(gè)方面：
1.1 志愿自動(dòng)匹配算法的相關(guān)分析
對(duì)學(xué)生和課題的選擇關(guān)系進(jìn)行合理分析可知，兩者的最優(yōu)、最大匹配，最好是根據(jù)學(xué)生的實(shí)際情況量身定做，才能真正實(shí)現(xiàn)課題與學(xué)生的最完美匹配。因此，教師提出相關(guān)題目時(shí)，需要對(duì)學(xué)生的情況、特性和要求等進(jìn)行全面分析，才能在學(xué)生對(duì)課題的特性、關(guān)聯(lián)性等有一定了解的情況下，提高課題與學(xué)生的匹配概率，最終讓學(xué)生選定最合適的課題。在實(shí)踐過程中，志愿自動(dòng)匹配算法的合理運(yùn)用，需要根據(jù)畢業(yè)論文的管理流程，從教師出題開始。一般情況下，教師應(yīng)該先提出大題讓學(xué)生自由選擇，在匹配學(xué)生確定好以后將大題分成幾個(gè)小題，從而將每個(gè)小題分配給合適的學(xué)生。在這種情況下，教師設(shè)定的課題需要從修讀課程達(dá)到的分?jǐn)?shù)、難度、所屬類別等多個(gè)方面確定，并從教務(wù)管理系統(tǒng)中獲取學(xué)生的成績和選題積分點(diǎn)等，才能根據(jù)分?jǐn)?shù)線來判定學(xué)生是否符合相關(guān)選題。其中，選題的難度在簡單、一般、難、很難和非常難幾個(gè)等級(jí)，對(duì)應(yīng)的成績是及格、良好、優(yōu)秀、極好。在實(shí)際進(jìn)行選題時(shí)，學(xué)生可以根據(jù)自己的情況選擇三個(gè)題目作為志愿，以在系統(tǒng)完成匹配后，自定將題目下發(fā)給學(xué)生。在實(shí)踐過程中，初始化志愿顯示的是學(xué)生的第一志愿，在經(jīng)過while、if、else、break、continue等流程后，系統(tǒng)會(huì)將題目和學(xué)生進(jìn)行適當(dāng)分類，以確保題目與學(xué)生的匹配最合理、最科學(xué)。由此可見，志愿自動(dòng)匹配算法是優(yōu)先對(duì)具有課題相關(guān)能力的學(xué)生進(jìn)行匹配的，在學(xué)生人數(shù)低于匹配數(shù)量的情況下，可繼續(xù)為積分點(diǎn)高、能力稍差的學(xué)生進(jìn)行匹配，對(duì)于確保課程成績與積分點(diǎn)的完美結(jié)合有著極大影響。
1.2 調(diào)劑學(xué)生算法的相關(guān)分析
在經(jīng)過上述算法進(jìn)行匹配后，根據(jù)學(xué)生的實(shí)際情況進(jìn)行深層挖掘，可以實(shí)現(xiàn)課題與剩余學(xué)生的完美調(diào)劑。因此，對(duì)上述階段中匹配失敗的學(xué)生志愿所選的教師、課題類別、難度等因素進(jìn)行深度挖掘，并將搜索結(jié)果作為匹配課題的依據(jù)，才能在縮小搜索范圍的情況下，找到與剩余學(xué)生最合適的課題。如果出現(xiàn)相近課題較多的情況，則需要有學(xué)生、工作人員共同協(xié)商，以確定最終和最適合學(xué)生的課堂。在實(shí)踐應(yīng)用中，調(diào)劑學(xué)生算法的運(yùn)用需要對(duì)需要調(diào)劑的學(xué)生進(jìn)行合理分析，并通過if、else、return、while、continue、else等多個(gè)流程，才能真正匹配出最適合學(xué)生的課題。
2 深度挖掘匹配算法在畢業(yè)論文管理中的實(shí)際應(yīng)用
根據(jù)深度挖掘匹配算法的實(shí)際應(yīng)用來看，在畢業(yè)論文管理中學(xué)生可以了解到最適合自己的課題信息，教師可以根據(jù)學(xué)生的積分點(diǎn)和成績等確定課題，從而避免選擇某一課題的學(xué)生過多或過少的情況出現(xiàn)，對(duì)于提高第一志愿自動(dòng)匹配成功率有著極大作用。因此，在實(shí)際應(yīng)用中，注重教師、課題類別、難度的合理設(shè)定，確保它們的排序科學(xué)，將課堂與學(xué)生的匹配關(guān)系看作是二分圖，并且，每個(gè)學(xué)生可以選擇的課題有三個(gè)，系統(tǒng)可以根據(jù)學(xué)生的實(shí)際情況進(jìn)行自動(dòng)匹配，最終深度挖掘與學(xué)生志愿匹配的課題。例如：志愿自動(dòng)匹配和調(diào)劑學(xué)生的總數(shù)都為102人，通過深度挖掘匹配算法匹配成功的人數(shù)分別為72人和90人，成功率達(dá)到了70%、88%。在不使用任何算法進(jìn)行匹配的情況下，兩者的成功率是52%左右。由此可見，在畢業(yè)論文管理系統(tǒng)中，深度挖掘匹配算法在科學(xué)應(yīng)用，可以為教務(wù)管理工作提供可靠參考依據(jù)，對(duì)于提高畢業(yè)論文管理工作人員的工作效率有著重要影響。
3 結(jié)語
綜上所述，在深度挖掘匹配算法不斷推廣的情況下，其在畢業(yè)論文管理中的實(shí)際應(yīng)用受到了很多教務(wù)管理工作人員的青睞。因此，充分發(fā)揮深度挖掘匹配算法的作用，提高深度挖掘匹配算法在畢業(yè)論文管理中的應(yīng)用效果，才能更好的滿足學(xué)生的選題需求。
參考文獻(xiàn)
[1]馮麗慧，馮立智.數(shù)據(jù)挖掘在畢業(yè)論文成績管理中的應(yīng)用研究[J].電腦知識(shí)與技術(shù)，2012，30：7150-7153.
[2]徐章韜.用信息技術(shù)深度挖掘課程內(nèi)容――以數(shù)學(xué)學(xué)科為例[J].教育發(fā)展研究，2015，12：29-33.
[3]連伊娜.深度挖掘高校檔案文化內(nèi)涵，更好為教育事業(yè)發(fā)展服務(wù)[J].黑龍江史志，2013，11：104-105.
作者簡介
劉冰潔（1983-），女，江西省南昌市人。工程碩士學(xué)位?，F(xiàn)為江西交通職業(yè)技術(shù)學(xué)院副教授。研究方向?yàn)榇髷?shù)據(jù)、系統(tǒng)集成、智能化技術(shù)。
【關(guān)鍵詞】藏文分詞 匹配算法 哈希表 詞典機(jī)制
1 引言
藏文信息處理存在著分詞的問題，而藏文分詞是對(duì)藏文詞性標(biāo)注、藏語音合成、機(jī)器翻譯、大型語料庫建設(shè)和信息檢索等藏文信息處理的基礎(chǔ)。藏文分詞的效果會(huì)對(duì)進(jìn)一步研究的藏文詞性標(biāo)注、藏語音合成、機(jī)器翻譯、大型語料庫建設(shè)和信息檢索等藏文信息處理軟件的性能和效果產(chǎn)生影響。
為了提高分詞的準(zhǔn)確率，需要有一個(gè)足夠大的詞庫，面對(duì)足夠大的詞庫，對(duì)詞庫中的詞語的搜索技術(shù)就顯得十分重要，對(duì)詞庫中詞語的搜索速度直接關(guān)系到分詞系統(tǒng)的性能。詞庫目前主要是采用索引的機(jī)制來實(shí)現(xiàn)的，一般用到的索引結(jié)構(gòu)的包括線性索引、倒排表、Trie樹、二叉樹等。線性索引、倒排表都是靜態(tài)的索引結(jié)構(gòu)，不利于插入、刪除等操作。
2 分詞
2.1 詞典機(jī)制算法
本系統(tǒng)采用的是基于Hash索引的分詞詞典。分詞詞典機(jī)制可以看作包含三個(gè)部分：首字Hash表、詞索引表、詞典正文。詞典正文是以詞為單位txt文件，匹配過程是一個(gè)全詞匹配的過程。首先，通過首字Hash表確定該詞在詞典中的大概位置，然后根據(jù)詞索引表進(jìn)行定位，進(jìn)而找到在詞典正文中的具置。該系統(tǒng)是采用Myeclipse10平臺(tái)，使用Java語言進(jìn)行實(shí)現(xiàn)的，直接調(diào)用Java里的hashmap創(chuàng)建函數(shù)，找到該詞之后，然后進(jìn)行字符串匹配。
2.2 基于匹配算法分詞
主流的分詞方法有三種：分別為基于語言學(xué)規(guī)則的方法、基于大規(guī)模語料庫的機(jī)器學(xué)習(xí)方法、基于規(guī)則與統(tǒng)計(jì)相結(jié)合的方法，鑒于目前藏文方面還沒有超大型的句子語料庫。該系統(tǒng)便采用了基于語言學(xué)規(guī)則的根據(jù)詞典進(jìn)行匹配的方法對(duì)藏文進(jìn)行分詞。
根據(jù)匹配的方向不同，分為正向和逆向兩種匹配算法。本系統(tǒng)采用的是正逆向匹配算法相結(jié)合的減字匹配法對(duì)藏文進(jìn)行分詞的，因?yàn)椴匚脑诿總€(gè)字的結(jié)束時(shí)，都會(huì)以“”作為分界；每個(gè)句子會(huì)以“”或者“” 作為分界。因此，對(duì)藏文進(jìn)行分詞的減字算法首先以藏文的字符“”或者“”切分出句子，如此一來，原文就被分為相應(yīng)的若干個(gè)句子了。接下來，再對(duì)每一個(gè)句子進(jìn)行詞典的匹配，如果沒有匹配成功就根據(jù)藏文字符中“”從句末尾減去一個(gè)字符，然后再次進(jìn)行匹配，直到匹配成功為止。對(duì)每個(gè)句子重復(fù)這些流程，直到每個(gè)句子全部分解為詞為止。逆向最大匹配是從句子的末尾選擇計(jì)算最大詞的長度，從后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。
為了提高切分的精度，該系統(tǒng)使用的是正向最大匹配和逆向最大匹配相結(jié)合的方法進(jìn)行分詞，先分別采用兩種方法分詞，然后根據(jù)概率比較兩種分詞結(jié)果，選擇概率較大的那種匹配算法作為分詞結(jié)果。
本系統(tǒng)的逆向最大匹配和正向最大匹配均是采用減字匹配算法，減字算法實(shí)現(xiàn)簡單，切分效果也比較理想，流程如圖1所示。
正向最大匹配（MM） 對(duì)于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判別CD是否屬于W，若是，則就切分為AB/CD，如果不是，則切分為AB/C/D。其中W 為分詞的詞典。逆向最大匹配對(duì)于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W為分詞的詞典，那么就取切分 AB/CD，根據(jù)藏文詞組最長的為6個(gè)字符組成的，所以進(jìn)行匹配算法的時(shí)候，初始化藏文最大字符串長度為6，流程圖如圖2所示。而逆向最大匹配算法是從句子的末尾開始進(jìn)行匹配，其核心算法與正向最大匹配算法相同，只不過開始匹配的方向不同而已。
無論是正向匹配（MM）算法還是逆向匹配（RMM）算法都會(huì)產(chǎn)生大量的歧義字段。我們很容易舉出這樣的例子，如：（五十六個(gè)民族心連心）這一句藏語，采用正向匹配算法分詞的結(jié)果為：，采用逆向匹配算法的分詞結(jié)果為：，在采用逆向匹配的時(shí)候，將會(huì)被劃分為，而（五十六）實(shí)際是一個(gè)詞，不該劃分，諸如此類的藏文句子還有很多，例如 等，無論使用正向最大匹配算法或者使用逆向最大匹配算法都會(huì)產(chǎn)生歧義，這種歧義稱為組合歧義。為了減少這種歧義的影響，本系統(tǒng)使用兩種分詞方法相結(jié)合的方式。首先分別使用兩種算法進(jìn)行分詞，然后通過統(tǒng)計(jì)的方法消除部分歧義。具體實(shí)現(xiàn)為：設(shè)正向最大匹配算法所切分的n個(gè)詞分別為，則這個(gè)句子切分的頻率則為；設(shè)逆向最大匹配算法所切分的n個(gè)詞分別為，則這個(gè)句子切分的頻率則為。如果，則選擇正向最大匹配算法所切分的結(jié)果，反之，則選擇逆向最大匹配算法所切分的結(jié)果。
3 結(jié)果和分析
結(jié)合26個(gè)大小不同的實(shí)驗(yàn)文本，對(duì)基于哈希表索引和匹配算法的分詞系統(tǒng)的準(zhǔn)確率進(jìn)行了分析，準(zhǔn)確率如圖3所示。結(jié)果顯示，該分詞系統(tǒng)的準(zhǔn)確率在92%以上。由此可得基于哈希表索引和匹配算法的分詞系統(tǒng)在準(zhǔn)確率上有不錯(cuò)的效果。
參考文獻(xiàn)
[1]華卻才讓.基于樹到串藏語機(jī)器翻譯若干關(guān)鍵技術(shù)研究[D].陜西師范大學(xué)，2014.
[2]石方夏，邱瑞，張|，任帥.藏文信息隱藏技術(shù)綜述[J].物聯(lián)網(wǎng)技術(shù)，2014，12：28-32.
[3]王思力，張華平，王斌.雙數(shù)組Trie樹算法優(yōu)化及其應(yīng)用研究[J].中文信息學(xué)報(bào)，2006，05：24-30.
[4]陳碩，桂騰葉，周張穎等.信息檢索在論文寫作和項(xiàng)目申報(bào)中的應(yīng)用[J].科技展望，2015，13：274-275.
[5]黃昌寧，趙海.中文分詞十年回顧[J]. 中文信息學(xué)報(bào)，2007，03：8-19.
[6]奉國和，鄭偉.國內(nèi)中文自動(dòng)分詞技術(shù)研究綜述[J].圖書情報(bào)工作，2011，02：41-45.
[7]賀艷艷.基于詞表結(jié)構(gòu)的中文分詞算法研究[D].中國地質(zhì)大學(xué)（北京），2007.
[8]戴上靜，石春，吳剛.中文分詞中的正向增字最大匹配算法研究[J].微型機(jī)與應(yīng)用，2014，17：15-18.
[9]劉遙峰，王志良，王傳經(jīng).中文分詞和詞性標(biāo)注模型[J].計(jì)算機(jī)工程，2010，04：17-19.
作者簡介
陳碩（1995-），男，自治區(qū)拉薩市人。本科在讀，主研領(lǐng)域?yàn)樽匀徽Z言處理，數(shù)學(xué)建模及其應(yīng)用。
周歡歡（1994-），女，湖南省衡陽市人。本科在讀，研究方向?yàn)閿?shù)學(xué)建模及其應(yīng)用、交通運(yùn)輸規(guī)劃與管理。
通訊作者簡介
趙棟材（1976-），男，現(xiàn)為大學(xué)藏文信息技術(shù)研究中心副教授。主要研究方向?yàn)椴匚男畔⑻幚怼?/p>
作者單位
關(guān)鍵詞：Rete算法，智能防火墻，規(guī)則，快速，匹配
Rete算法是一個(gè)快速的模式匹配算法，它通過形成一個(gè)Rete網(wǎng)絡(luò)進(jìn)行模式匹配，利用基于規(guī)則的系統(tǒng)的兩個(gè)特征，即時(shí)間冗余性（Temporalredundancy）和結(jié)構(gòu)相似性（structural similarity），提高系統(tǒng)模式匹配效率。
一、模式匹配的基本概念
1、可滿足規(guī)則：一個(gè)規(guī)則稱為可滿足的，若規(guī)則的每一模式均能在當(dāng)前工作存儲(chǔ)器中找到可匹配的事實(shí)，且模式之間的同一變量能取得統(tǒng)一的約束值。形式化地說，規(guī)則
if P1,P2,…Pmthen A1,A2,…An
稱為可滿足的，若存在一個(gè)通代σ，使得對(duì)每一個(gè)模式Pi，在工作存儲(chǔ)器中有一個(gè)元素Wi滿足
Piσ=Wii=1,2,3 …m
這里，σ作用在某個(gè)模式的結(jié)果稱為模式實(shí)例，σ作用在整個(gè)規(guī)則的結(jié)果稱為規(guī)則實(shí)例。在專家系統(tǒng)中，可滿足的規(guī)則稱為標(biāo)志規(guī)則。
2、沖突集：由全體規(guī)則實(shí)例構(gòu)成的集合稱為沖突集，也稱上程表。免費(fèi)論文參考網(wǎng)。
3、模式匹配算法的任務(wù)是：給定規(guī)則庫，根據(jù)工作存儲(chǔ)器的當(dāng)前狀態(tài)，通過與規(guī)則模式的匹配，把可滿足規(guī)則送入沖突集，把不可滿足的規(guī)則從沖突集中刪去。
二、Rete算法的依據(jù)和基本思想
Rete算法快速匹配的重要依據(jù)是：
1、時(shí)間冗余性。免費(fèi)論文參考網(wǎng)。工作存儲(chǔ)器中的內(nèi)容在推理過程中的變化是緩慢的，即在每個(gè)執(zhí)行周期中，增刪的事實(shí)只占很小的比例，因此，受工作存儲(chǔ)器變化而影響的規(guī)則也只占很小的比例。由產(chǎn)生式系統(tǒng)的折射性，只要在每個(gè)執(zhí)行周期中記住哪些事實(shí)是已經(jīng)匹配的，需要考慮的就僅僅是修改的事實(shí)對(duì)匹配過程的影響。
2、結(jié)構(gòu)相似性。許多規(guī)則常常包含類似的模式和模式組。
Rete算法的基本思想是：保存過去匹配過程中留下的全部信息，以空間代價(jià)來換取產(chǎn)生式系統(tǒng)的執(zhí)行效率。
三、Rete匹配網(wǎng)絡(luò)結(jié)構(gòu)與過程
Rete算法的核心是建立Rete匹配網(wǎng)絡(luò)結(jié)構(gòu)，其由模式網(wǎng)絡(luò)和連接網(wǎng)絡(luò)兩部分構(gòu)成。其中，模式網(wǎng)絡(luò)記錄每一模式各域的測試條件，每一測試條件對(duì)應(yīng)于網(wǎng)絡(luò)的一個(gè)域結(jié)點(diǎn)，每一模式的所有域結(jié)點(diǎn)依次連起來，構(gòu)成模式網(wǎng)絡(luò)的一條匹配鏈。
Rete網(wǎng)絡(luò)匹配過程由模式網(wǎng)絡(luò)上的模式匹配和連接網(wǎng)絡(luò)上的部分匹配構(gòu)成。在模式網(wǎng)絡(luò)的機(jī)器內(nèi)部表示中，我們把共享一個(gè)父結(jié)點(diǎn)的所有結(jié)點(diǎn)表示成一條共享鏈。同時(shí)，把每一模式匹配鏈中的結(jié)點(diǎn)表示成一條下拉鏈，于是，每一結(jié)點(diǎn)由共享鏈和下拉鏈指向其后繼結(jié)點(diǎn)，模式網(wǎng)絡(luò)就是一棵可以使用典型遍歷算法進(jìn)行測試的二叉樹。
四、智能防火墻Rete算法設(shè)計(jì)
Rete快速匹配算法，函數(shù)Rete設(shè)計(jì)為:取IP地址、端口號(hào)各部分折疊、異或運(yùn)算后，以Rete長度取模。免費(fèi)論文參考網(wǎng)。算法如下(無關(guān)或部分無關(guān)稱為集合A，相關(guān)、包含相等和相等的稱為集合B):
1、Addr=sa+da sa:源地址 da:目的地址
2、Port=sp+dp sp:源端口號(hào) dp:目的端口號(hào)
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表長度
防火墻初始化時(shí)，首先從規(guī)則集A用該散列函數(shù)構(gòu)造Rete表R為
Void Initialization(RULE-SET A){
FOR(r∈A)DO{ \r為每條規(guī)則
idx=Rete(r.addr,r.port)；
R[idx]=&r； \R代表規(guī)則集合A
}}
因?yàn)镽ete表的長度有限，但是如果設(shè)計(jì)太大會(huì)浪費(fèi)存儲(chǔ)空間，也降低了查找速度，所以免不了會(huì)出現(xiàn)沖突。解決沖突的方法是:如果兩條規(guī)則經(jīng)過散列后落到同一位置，則把這兩條規(guī)則按照插入順序組成一個(gè)鏈表結(jié)構(gòu)。主要算法如下:
if(R[Rete(r.addr,r.port)]=NULL)\R為Rete表,r為規(guī)則
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;}
數(shù)據(jù)包匹配流程：當(dāng)防火墻收到一個(gè)數(shù)據(jù)包以后，用算法Match查找規(guī)則集(A和B)。
Match(IP-Packet p) { \p為數(shù)據(jù)包
Int idx=Rete(p.addr,p.port) ； \首先用Rete算法查找A類規(guī)則
IF (R[idx].addr≧p.addr&& R[idx].port=p.port) \找到匹配規(guī)則
return R[idx] ；
Else {int idex I =halfquery(p.addr) ； \利用折半查找索引表
J=L[indexl] ； \L代表規(guī)則集合B
While(j!=NULL){\順序匹配找到的規(guī)則鏈
IF (Matchrule(p)) return j； \ Matchrule為規(guī)則匹配函數(shù)
Else j=j->next；
}}
Return(Norulematch)；
}
參考文獻(xiàn)：
[1] 閆麗萍，潘正運(yùn). RETE算法的改進(jìn)與實(shí)現(xiàn).微計(jì)算機(jī)信息，2006 (36）
[2] 龐偉正，金瑞琪，王成武. 一種規(guī)則引擎的實(shí)現(xiàn)方法.哈爾濱工程大學(xué)學(xué)報(bào)，2005(03)
[3] 江建國，張景中. 基于Rete算法的幾何自動(dòng)推理系統(tǒng). 四川大學(xué)學(xué)報(bào)（工程科學(xué)版）， 2006(03)
關(guān)鍵詞：雙目視覺 立體匹配 導(dǎo)航定位 機(jī)器人
中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416(2011)12-0059-02
引言
雙目視覺是一種通過兩幅圖像獲取物體三維信息的方法，具有通過二維圖像認(rèn)知物體三維立體信息的能力，其關(guān)鍵技術(shù)就是要解決兩幅圖像中對(duì)應(yīng)點(diǎn)的匹配問題［1］。立體匹配一直都是機(jī)器視覺領(lǐng)域中的難點(diǎn)和熱點(diǎn)，論文根據(jù)結(jié)合變電站及巡檢機(jī)器人雙目視覺系統(tǒng)的特點(diǎn)，運(yùn)用匹配輔助區(qū)域匹配算法實(shí)現(xiàn)立體匹配，獲得密集準(zhǔn)確的深度圖。
1、立體匹配原理
立體匹配基于視差原理，如圖1所示。其中基線距B=兩攝像機(jī)的投影中心連線的距離；攝像機(jī)焦距為f。設(shè)兩攝像機(jī)在同一時(shí)刻觀看空間物體的同一特征點(diǎn)，分別在“左眼”和“右眼”上獲取了點(diǎn)的圖像，它們的圖像像素坐標(biāo)分別為
采用平行攝像機(jī)模型，兩攝像機(jī)的圖像在同一個(gè)平面上，并且特征點(diǎn)p的圖像坐標(biāo)y坐標(biāo)在左右圖像平面上相同，
可以得到：
要想根據(jù)左右圖像對(duì)完成立體匹配任務(wù)，就把只需計(jì)算左右圖像對(duì)的立體視差，立體視差是景物點(diǎn)在左右圖像中圖像像素的橫坐標(biāo)之差，即：
從而就可以建立立體視差圖(又稱深度圖)。所建立的立體視差圖可以細(xì)分為兩個(gè)子區(qū)域，零視差子區(qū)域和非零視差子區(qū)域，零視差子區(qū)域?yàn)闄C(jī)器人可以自由行走的無障礙平坦區(qū)域；非零視差子區(qū)域?yàn)槠教箙^(qū)域上的凸出區(qū)域，可能是障礙物存在的區(qū)域。
根據(jù)式(3)及立體視差原理，可以方便地計(jì)算世界坐標(biāo)下的特征點(diǎn)在攝像機(jī)坐標(biāo)系下的三維坐標(biāo)：
左攝像機(jī)像面上的任意一點(diǎn)只要能在右攝像機(jī)像面上找到對(duì)應(yīng)的匹配點(diǎn)，就可以確定出該點(diǎn)的三維坐標(biāo)。這種方法是完全的點(diǎn)對(duì)點(diǎn)運(yùn)算，像面上所有點(diǎn)只要存在相應(yīng)的匹配點(diǎn)，就可以根據(jù)式(5)計(jì)算出對(duì)應(yīng)的三維坐標(biāo)。
2、立體匹配設(shè)計(jì)
經(jīng)過圖像預(yù)處理，可以為立體匹配提供較理想立體圖像對(duì)，降低了匹配算法的難度。論文結(jié)合變電站、檢機(jī)器人雙目視覺系統(tǒng)的特點(diǎn)，運(yùn)用特征輔助區(qū)域匹配算法實(shí)現(xiàn)立體匹配，該算法結(jié)合特征匹配算法及區(qū)域匹配算法的優(yōu)點(diǎn)，可以在計(jì)算量不大的情況下，生成密集準(zhǔn)確的立體視差圖。
算法的總體上分三步：
2.1 匹配初始化階段
匹配初始化階段需要完成以下工作：對(duì)雙目攝像機(jī)參數(shù)的標(biāo)定；對(duì)攝像機(jī)所采用的圖像運(yùn)用高斯―拉普拉斯模板進(jìn)行圖像預(yù)處理；對(duì)預(yù)處理的圖像運(yùn)用加速主成分分析法實(shí)現(xiàn)圖像的特征提??；這些過程都是為后面的立體匹配做準(zhǔn)備，為之提供較理想的立體圖像對(duì)。
2.2 特征匹配階段
根據(jù)各種匹配準(zhǔn)則縮小匹配點(diǎn)的搜索范圍，利用特征匹配算法確定正確的匹配點(diǎn)。
2.3 區(qū)域匹配階段
由于前面特征提取算法限制，不可能把景物所有特征點(diǎn)全部提取到，所以特征點(diǎn)匹配完成后，還存在一些有價(jià)值的非特征點(diǎn)未被匹配。但是這些未被匹配點(diǎn)被已匹配點(diǎn)限制在較小的范圍內(nèi)，對(duì)這些小范圍點(diǎn)的匹配就是區(qū)域匹配算法的工作。
對(duì)多個(gè)可能的候選匹配點(diǎn)比較時(shí)，可能使用的依據(jù)有灰度、曲率、拉普拉斯變換、梯度等。結(jié)合變電站實(shí)際環(huán)境，運(yùn)用連續(xù)性約束準(zhǔn)則和灰度、x方向的灰度梯度、梯度方向唯一確定匹配點(diǎn)［2］。思路如下：
①┍算視覺連續(xù)性約束相關(guān)系數(shù)
其中d為已匹配點(diǎn)的視差均值，d為當(dāng)前候選匹配點(diǎn)的視差。若，1為預(yù)先設(shè)定視覺連續(xù)性約束相關(guān)系數(shù)閾值，排除此候選匹配點(diǎn)，重復(fù)執(zhí)行此步直到時(shí)，執(zhí)行第2步；否則直接執(zhí)行第2步執(zhí)行。
②計(jì)算候選匹配點(diǎn)與待匹配點(diǎn)的灰度相關(guān)值Vcorr、x方向的灰度梯度接近程度系數(shù)Kgard_r、梯度方向相關(guān)系數(shù)式(7)-(8)中，K_gard_x、K_gard_y為基準(zhǔn)圖像上特征點(diǎn)x和y方向的梯度，Rgrad_x、Rgrad_y為候選匹配點(diǎn)x和y方向的梯度，fl、fr為左右圖像的灰度函數(shù)，、為特征點(diǎn)和候選匹配點(diǎn)在窗口(2N+2M+1)中灰度均、為兩點(diǎn)在窗口中灰度標(biāo)準(zhǔn)差。若有Vcorr
③計(jì)算總判斷依據(jù)
計(jì)算出所有候選匹配點(diǎn)的Iall值，其Iall值最大者即認(rèn)為是最佳候選匹配點(diǎn)，即特征點(diǎn)Pleft在右圖像中的匹配點(diǎn)。
要匹配固定大小的圖像窗口中的像素，相似約束準(zhǔn)則是兩幅圖像在窗口中的相關(guān)性度量，當(dāng)被搜索區(qū)域的點(diǎn)與待匹配點(diǎn)間相似約束準(zhǔn)則最大化時(shí)，認(rèn)為搜索區(qū)域的點(diǎn)是待匹配點(diǎn)的匹配點(diǎn)［3］。
設(shè)有立體圖像對(duì)IMG1、IMGr，Pl、Pr為兩幅圖像中的像素點(diǎn)，相關(guān)窗口大小為，為圖像IMGl中像素點(diǎn)Pl在圖像3、實(shí)驗(yàn)與結(jié)果
圖2中左右兩圖像，是左右攝像機(jī)對(duì)同一景物拍攝所得。
根據(jù)上圖的左右兩圖，運(yùn)用立體匹配算法求得立體視差圖。實(shí)驗(yàn)結(jié)果如圖3所示，其中左圖像素深度圖，右圖是對(duì)左圖經(jīng)median處理后的效果圖，看起來對(duì)左圖清晰了不少，但不能顯示真實(shí)圖像視差關(guān)系。此算法消耗較長時(shí)間，將在以后工作中改進(jìn)。
參考文獻(xiàn)
［1］楊俊,賈秀芳.變電站防火防盜圖像識(shí)別的研究.中國高等學(xué)校電力系統(tǒng)及其自動(dòng)化專業(yè)第20屆學(xué)術(shù)年會(huì)，2004.7.
［2］林琳.機(jī)器人雙目視覺定位技術(shù)研究［D］．西安電子科技大學(xué)碩士學(xué)位論文,2009.
［3］薛長松．基于DM642的雙目視覺控制系統(tǒng)研究［D］.河南大學(xué)碩士學(xué)位論文,2007.
>> 算法與模型 快速圖像匹配算法及其水下導(dǎo)航應(yīng)用 芻議華帝戰(zhàn)略選擇與匹配 入侵檢測模式匹配算法的研究與改進(jìn) 論文相似度匹配算法的研究與實(shí)現(xiàn) 字符串匹配算法比較與分析 正向最大匹配分詞算法的分析與改進(jìn) 基于模擬退火算法的P2P借貸平臺(tái)的債權(quán)匹配模型 基于輪廓特征點(diǎn)的三維模型相似性匹配算法 一種基于語言學(xué)特征的本體匹配改進(jìn)算法 動(dòng)作與音樂的節(jié)奏特征匹配模型研究 基于SIFT算法與RANSAC算法的X射線圖像匹配研究 電影語言與影片風(fēng)格的匹配問題 基于啟發(fā)式算法的品牌模型的選擇 軟件可靠性模型選擇的SRMS算法 雙目立體視覺區(qū)域局部匹配算法的改進(jìn)及其實(shí)現(xiàn) 軟件工程過程模型及其選擇 混合Copula模型選擇及其應(yīng)用 模式匹配查詢算法研究 指紋快速匹配算法研究 常見問題解答 當(dāng)前所在位置：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. （周水庚，關(guān)佶紅，胡運(yùn)發(fā)，等.一個(gè)無需詞典支持和切詞處理的中文文檔分類系統(tǒng)[J].計(jì)算機(jī)研究與發(fā)展，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. （高振峰，李錫祚.基于滑動(dòng)窗口的特征提取方法在文本分類中的應(yīng)用[J].科技信息：學(xué)術(shù)版，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.
關(guān)鍵詞：入侵檢測；模式匹配；算法。
中圖分類號(hào)：TP309.08 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2013）06-0135-02
1 引言
在基于主機(jī)入侵檢測技術(shù)中，應(yīng)用比較多的是誤用檢測技術(shù)，其核心多采用字符串搜索算法模式匹配技術(shù)。通過對(duì)目前廣泛應(yīng)用的BM算法[1]和AC_ BM算法[2]的分析，提出基于AC_ BM算法的改進(jìn)的多模式匹配算法NAC_ BM算法。該算法綜合了BM算法和AC_ BM算法的優(yōu)點(diǎn)，改進(jìn)了BM算法跳躍步長，使得每次匹配獲得最大的步長，同時(shí)應(yīng)用AC算法有限狀態(tài)機(jī)模式匹配自動(dòng)機(jī)構(gòu)造模式樹，匹配過程中移動(dòng)模式樹，減少了規(guī)則匹配次數(shù)，為基于主機(jī)的入侵檢測模式匹配技術(shù)提供了一種優(yōu)化方法。
2 多模式字符串匹配算法
由于BM算法是一種單模式字符串匹配算法，它每次只能完成對(duì)一個(gè)模式的匹配工作，效率較低。雖然研究者對(duì)BM改進(jìn)算法很多，但是這些算法都沒有改變BM算法的基本思想，因此不能解決效率問題。
為了提高效率，研究者提出了多模式匹配問題[3]，多模式匹配問題可以抽象描述為：設(shè)是一個(gè)模式集合，模式串Pi 中的字母來自于一個(gè)固定的字母表。多模式匹配問題是發(fā)現(xiàn)P中所有模式在文本T中的所有出現(xiàn)，。
3 AC_BM算法的改進(jìn)—NAC_BM算法
4 仿真實(shí)驗(yàn)分析
為了對(duì)各個(gè)算法的性能、效率做具體的評(píng)測，在同一臺(tái)計(jì)算機(jī)上分別對(duì)單模式匹配算法和多模式匹配算法進(jìn)行了仿真測試。
在本測試中采用的搜索文件是來自麻省理工學(xué)院林肯實(shí)驗(yàn)室提供的“1999DARPA入侵檢測測試數(shù)據(jù)集”[4]，長度為10000000Bytes的文本，而匹配的模式串是隨機(jī)抽取的。
由于對(duì)于單模式和多模式而言，各有其不同的特點(diǎn)，比如對(duì)于單模式匹配算法，它的時(shí)
間開銷與模式串的個(gè)數(shù)成正比，不能用它們解決多模式匹配的性能問題。而對(duì)于絕大多數(shù)多模式匹配算法都要在執(zhí)行搜索操作前，對(duì)模式串集合進(jìn)行預(yù)處理，構(gòu)造某種數(shù)據(jù)結(jié)構(gòu)，以便為搜索過程提供支持；相對(duì)于單模式匹配算法對(duì)空間需求可以根據(jù)模式串的長度而估算出來。本實(shí)驗(yàn)對(duì)匹配的模式個(gè)數(shù)對(duì)各種匹配算法性能的影響進(jìn)行了仿真并給出對(duì)比分析。
圖5中“*”號(hào)表示該項(xiàng)未測試。對(duì)于模式串為1（即單模式串）時(shí)，AC算法、AC_BM算法和NAC_BM算法沒有必要測試它們對(duì)單模式匹配的性能。當(dāng)模式個(gè)數(shù)大于1時(shí)，多模式匹配算法掃描對(duì)象文本一遍，而單模式匹配算法則要掃描對(duì)象文本多遍，即對(duì)每一個(gè)模式串掃描一遍對(duì)象文本。對(duì)于模式串個(gè)數(shù)為1000時(shí)，對(duì)單模式匹配算法是十分費(fèi)時(shí)，且其耗費(fèi)時(shí)間也可估算出來。
從圖5的結(jié)果來看，多模式匹配算法比單模式匹配算法的匹配速度快得多。三種多模式匹配算法仍然比其他單模式匹配算法速度快，而且AC_ BM算法和NAC_ BM算法比AC算法快，這兩個(gè)算法隨著模式串?dāng)?shù)目的增加，所耗費(fèi)的時(shí)間僅有很小的增加，而不是成比例地增長。從表中可以看出，NAC_ BM算法比AC_BM算法在效率上有一定程度的提高。
5 結(jié)語
本文提出了一種改進(jìn)的AC_BM算法：NAC_BM算法。該算法一是在BM算法的基礎(chǔ)上，改進(jìn)了跳躍步長，使得每次匹配獲得最大的步長，二是應(yīng)用AC算法有限狀態(tài)機(jī)模式匹配自動(dòng)機(jī)構(gòu)造模式樹，匹配過程中移動(dòng)模式樹，減少了規(guī)則匹配次數(shù)。最后通過仿真實(shí)驗(yàn)對(duì)比得知：NAC_BM算法效率優(yōu)于BM和AC_BM算法。
參考文獻(xiàn)
[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]楊武，方濱興，云曉春等.入侵檢測系統(tǒng)中高效模式匹配算法的研究.計(jì)算機(jī)工程，2004，30（13）.92-94.
