引論：我們為您整理了13篇匹配算法論文范文，供您借鑒以豐富您的創作。它們是您寫作時的寶貴資源，期望它們能夠激發您的創作靈感，讓您的文章更具深度。

篇1

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

引言

雙目視覺是一種通過兩幅圖像獲取物體三維信息的方法，具有通過二維圖像認知物體三維立體信息的能力，其關鍵技術就是要解決兩幅圖像中對應點的匹配問題［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

1 引言

在現有的畢業論文選題系統中，一個學生只能選擇一個題目作為自己最終的題目，同樣，一個題目只能分配給一個學生。如果最后題目由學生自己確定，那就會出現先選的學生具有更大的選擇余地，后選的學生由于不能再選已經選定的題目，所以其可選擇的題目會越來越少，這對很多學生來說很不公平。如果學生選擇自己的志愿，最終題目由老師來定，這不但加大了老師的工作量，而且還是不能保證每位同學的公平性。如何采用計算機智能輔助選題，設計最優匹配算法實現學生與題目的整體最優匹配，會大大提高選題的效率。

湯穎曾在《畢業設計立項與選題管理及其支持系統》中提出，采用模糊匹配技術進行學生-題目的自動匹配；潘志方在《一種改進的Ford-Fulkenson算法在選題系統中的應用研究》中將題目與學生的匹配抽象為二分圖的匹配，并采用改進的Ford-Fulkenson算法實現題目與學生的自動匹配。以上兩種方法只考慮了學生與題目之間的最大匹配值，并沒有考慮學生的整體滿意度最優的情況。

本文將通過采用最優匹配算法（KM）確定一種匹配方案，使得學生的整體滿意度最高。具體方法概括如下：學生預選多個題目，并根據自己對題目的滿意度由高到底排序，這樣，滿意度成為二分圖的一分值，如圖1所示：

2 系統功能模塊設計

根據前期的可行性分析，本系統主要進行以下模塊的設計：系統管理員模塊、專業負責人管理模塊、指導教師管理模塊和學生選題模塊。

系統管理員模塊主要負責對系統參數的設置及用戶的管理。主要實現以下功能：

（1）系統設置：對系統標題、畢業生、選題參數設置；

（2）學院及專業設置：完成學院、專業的添加、刪除、修改操作；

（3）數據字典的維護：教師信息、選題難度、選題方向燈信息的維護；

（4）教師和學生的管理：完成教師、學生信息的添加、刪除和修改操作；

（5）文件文化建設管理：日志文件查看、上傳文件的管理。

專業負責人管理模塊與系統管理員權限相似，但操作的數據只能針對于指定專業，無法瀏覽及操作整個學院的課題及學生信息。最重要的功能是實現題目的審核。

導師管理模塊主要用于選題以及選擇自己選題學生的審核確認。

（1）個人中心管理：如信息修改及密碼重置；

（2）選題管理：選題的增加、修改、刪除以及選題類型的設置；

（3）學生選題查詢及審核。

學生模塊主要實現學生選題的選擇及確認。

（1）學生個人信息的修改；

（2）學生選題及確認信息查詢；

（3）學生留言及咨詢。

3 KM算法在系統中的實現

KM算法由Kuhn和Munkras分別提出來，這是一種問題。經典的算法。該算法由通過每個頂點一個頂標（A[i][j]）來求最大權匹配的問題轉化為不斷尋找增廣道路以使二分圖的匹配數達到最大的完備匹配。KM算法的關鍵在于不斷尋找二分圖中的可增廣道路。如果找到一條可增廣道路，就可以額將屬于和不屬于相等子圖的邊取相反，從而相等子圖里就是增加一條邊，一直到所有的頂點都進入相等子圖為止。

KM算法可以很好地解決選題系統中，題目與學生最優匹配的問題。下面以國際商學院09級本科學生選題為例。

在匹配過程中，設學生的集合為X={X1，X2，X3……Xn}，選題的集合設置為Y={Y1，Y2，Y3……Yn}，學生對自己選題的滿意度為二維矩陣Z[m][n]，其他題目規定權值為0。系統規定學生最多可預選3個題目，并按照滿意度分別設置0.9，0.7，0.5。以下表1是對國際經濟與貿易專業使用不同算法得出的學生滿意程度。

下面對以上數據進行說明。如采用手工分配的方式，使得681名學生中414名同學分的了題目，滿意度為60.82%；如果采用最大匹配算法進行分配，可以使分配數達到最大，有517名學生分得題目，滿意度上升為79.99%；最有用最有匹配算法進行分配，使總體滿意度達到78.24%，533人。需要說明的一點是，KM算法只是找到了整體最優匹配而不是最大數匹配，如果整體最優情況下匹配數和最大匹配數相差得太大的話，那么整體最優方案顯得不太可取。所以，最好的情況就是同時考慮最優匹配和最大匹配來同時控制兩者的大小。

4 結語

本系統實現了畢業論文選系統工作的各個管理功能，通過實現教師與學生的雙向選擇，使用KM算法，提高選題的質量和效率，為學院充分利用網絡完成畢業論文選題工作提供了便利的平臺。

參考文獻：

[1]湯穎.畢業設計立項與選題管理及支持系統[J].合肥工業大學學報，2006，29（5）.

篇4

1 引言

突發公共衛生事件應急系統的建立對于保障公共安全，建設社會主義和諧社會具有特殊重要的現實意義。目前國內外在應急響應領域已經取得了很大的進步，但對應急預案系統的研究才剛剛處于起步階段。作為整個系統中最為基礎和根本的一環，應急預案對于應急響應的實施具有重要作用。

本文通過對現有應急預案和應急響應過程的分析，通過框架技術對應急預案的知識進行表示，研究了預案的匹配算法，給出了預案相似度以及價值評估的計算方法。

2 智能預案匹配

應急預案是應急事件處置的領域知識來源。應急預案管理系統可以在對處置預案、資源分布轉臺、事件處置狀態自動初步生成事件處置方案。再經過處置人員對初步方案進行調整，經過認可后即可作為高效地應急響應處理的指導方案。

2.1 基于框架的匹配

預案采用框架的智能化存儲結構表示，預案的智能匹配自然和框架體系的匹配息息相關。基于框架體系的匹配系統一般由兩大部分組成：

（1）由框架及其相互關聯構成的知識庫。提供求解問題所需要的知識；

（2）由一組解釋程序構成的框架推理機。針對用戶提出的問題，通過運用知識庫中的相關知識完成求解問題的任務，給出問題的解；

2.2 匹配過程及算法

3.2 數據相似度研究

預案是介于數據與知識之間的一種知識存在形式，存儲預案的框架結構具有不同數據類型的槽和側面屬性。計算不同數據類型屬性的相似度，首先要討論屬性即槽值和側面值的數據類型。一般來說，屬性的數據類型分為以下三個大類。針對以上三大類型，分別來討論其相似度算法。

4 結論

本文主要論述了智能預案框架表示與預案知識匹配機制。通過對現有應急預案和應急響應過程的分析，提出一個對應急預案的描述方法。利用框架結構完整的描述預案實體單元，依據各框架間的縱向聯系和橫向聯系，從而形成框架網絡。利用框架知識表示，研究了預案的智能匹配與相似度比對。最后討論了預案相似度算法，給出了預案相似度以及價值評估的計算方法，討論了預案框架中不同數據類型屬性的相似度算法，重點研究了數值類型和文本類型的屬性相似度算法。

參考文獻

[1]Nilsson NJ. Artificial Intelligence： A New Synthesis[M].Copyrighted Matenal，2000.

[2]Sui YF，Gro Y， Cao CG.Ontologies， Frames and Logical Theories in NKI[J].Journal of Software，2005，16（12）.

[3]李晨陽，曹忠升，馮玉才.一種基于框架和中間件模型的知識庫系統[J].計算機應用，2000（12）：1298-1300.

[4]張榮梅.基于CBR與MAS的智能決策支持系統研究及應用[D]：[碩士學位論文].北京：北京科技大學，2001.

[5]劉義剛.基于預案庫的快速智能決策支持系統的研究[D]：[碩士學位論文].北京：北京理工大學，2001.

[6]楊健，趙秦怡.基于案例的推理技術研究進展及應用[J].計算機工程與設計，2008，29（3）：710.

篇5

摘要：分析了畢業論文選題系統的特點，引入了學生及指導教師對選題結果的滿意度，建立了一個以總體滿意度最大為目標的畢業論文選題系統模型，并在此基礎上設計實現了基于web的本科畢業論文選題系統。實際應用表明，該系統可以有效的提高畢業論文選題的總體滿意度及選題質量。

Abstract: The thesis analyzed the characteristics of graduation projects' selection system, introduced the satisfaction of student and instructor with the results on the topics, established a model of graduation projects' selection system which took the overall satisfaction as the goal, and on this basis, designed and implemented graduation projects' selection system for undergraduates based on web. The application showed that this system could effectively improve the overall satisfaction of thesis topics and the quality.

關鍵詞：滿意度 畢業設計 選題系統 web

Key words: satisfaction；graduation project；selection systems；web

中圖分類號：TP39 文獻標識碼：A文章編號：1006-4311（2011）29-0147-02

0引言

畢業設計（論文）是高校培養學生的重要環節，隨著高校的擴招，畢業論文選題的工作量也越來越大，以往的手工選題的方式已經遠遠不能滿足高校畢業論文選題的需求。一個有效的方法是采用計算機智能選題系統，在畢業論文選題系統中，一個學生只能選擇一個題目作為自己的最終論文題目；同樣，一個題目也只能分配給一個學生。如果最終題目由學生自己確定，那么就會出現這樣的情況：先選的學生具有更大的選擇余地，后選的學生由于不能再選已經選定的題目，所以其可選擇的題目會越來越少，這對很多學生來說是很不公平的。如果學生選擇自己的志愿，而最終題目由老師來定，這不但加大了老師的工作量，而且還是不能保證每位同學的公平性。如果采用計算機智能輔助選題，設計最優匹配算法實現學生與題目的整體最優匹配，無疑將大大提高選題的效率。

一些學者曾對題目的智能化匹配作過比較深入的研究，如湯穎采用模糊匹配技術進行學生一題目的自動匹配[1]；潘志方將題目與學生的匹配抽象為二分圖的匹配，并采用改進的Ford-Fulkenson算法實現了題目與學生的自動匹配[2]；楊勝超等將學生的滿意度引入到了畢業論文選題中[3]。但是，他們只是考慮了題目與學生的最大匹配數，并沒有同時考慮學生和教師整體滿意度最優的情況，而教師的滿意度往往對選題質量的控制起著關鍵作用。

本文在畢業論文選題系統中引入了學生和教師的滿意度，建立了在最有匹配基礎上的以滿意度最大為目標的選題系統模型，給出了算法實現并將其應用到了本科畢業論文選題系統的設計中，最后給出了畢業論文選題系統的具體實現，并進行了實際測試。測試結果表明，該選題的應用可以提高選題的總體滿意度和選題質量。

1選題系統最大滿意度模型

設S為學生的集合，有sm屬于S，m屬于[1，M]，其中M為學生數。設T為題目的集合，有tn屬于T，n屬于[1，N]，其中N為論文題目總數。那么對于所有的選題情況有集合Anm，對于某一具體選題，學生滿意度Xnm，教師滿意度Ynm，那么Xnm+Ynm有最大值，max(Xnm+Ynm)。因此，該問題變成了求解滿意度最大值問題，并能確定在取得最大值情況下Anm的集合，也就是具體的每一個學生的對應的唯一的選題。

2畢業論文選題系統的設計實現

2.1 系統用例該系統的用戶主要有三類，分別是系統管理員、普通教師和學生，系統用例說明如表1所示。

2.2系統流程設計基于最大滿意度的畢業設計選題系統，充分考慮了學生確定自己論文題目的自由性：學生可以自主命題由老師來審核，如果審核通過則可作為自己的最終論文題目，如果未通過審核還可以反過來參加預選或者再次自主命題（有最大自主命題數限制）。同時將教師對選題情況的評價引入，更加合理。同時還優化了題目預選的匹配：通過管理員啟動最大滿意度匹配算法，確定出學生與題目的最優匹配方案，這樣便大大減輕了老師的工作量，提高了選題的效率。最后，如果通過以上兩個步驟還有學生沒有定題，就只有通過老師手動確定學生的最終題目。

2.3 系統數據庫設計基于前邊的分析設計，我們需要設計到下列各表，這些表之間相互關聯，共同存儲著系統所需要的數據。在設計數據庫表的過程中，應遵循以下幾條原則，數據庫設計一個表最好值存儲一個實體或對象的相關信息，不同的實體最好存儲在不同的數據表中，如果實體還可以再分，實體的劃分原則是最好能夠比當前系統要開發的實體的顆粒度要小，數據表的信息結構一定要合適的，表的字段的數量一定不要過多，擴充信息和動態變化的信息一定要分開在不同的表里，對于多對多這樣的表關系系統盡量不出現。該系統中主要的數據表如表2-表5。

普通教師參數表保存的是用戶參數，UserID是用戶注冊時輸入的，作為該表的主鍵，表中記錄的用戶編號是不會相同的，這要求在用戶注冊時檢查欲注冊的用戶名是否已經被注冊過，這是必要的一步。（故部分系統在注冊時要求用個人Email地址作為用戶ID，這樣重復的幾率非常低，但也是需要檢查的。）且UserID在其他表中也會用到。（表2）

學生參數表保存的是用戶參數，StID是用戶注冊時輸入的，作為該表的主鍵，表中記錄的用戶編號是不會相同的，這要求在用戶注冊時檢查欲注冊的用戶名是否已經被注冊過，這是必要的一步。（表3）管理員參數表是管理員的一些注冊信息，其中Adminid是管理員編號，是該表的主鍵。其余各字段與普通教師參數表中的字段意義相同。（表4）

題目信息參數表是信息的各種參數，包括題目的編號（系統自動生成），是該表的主鍵。題目的詳細內容是對該題目的簡單介紹，題目類別根據需要進行設置。（表5）

2.4 系統實現最后，系統采用asp+access進行了實現，具體實現過程由于篇幅所限，不再贅述。

3系統測試

該系統設計完成后，在榆林學院信息工程學院2010屆本科畢業生的畢業論文選題過程中進行了實際的測試，測試數據如表6。

在此次測試中，共有學生96人，題目107個，從表中可以看出，采用手工分配方案，只有74個學生可以分得選題，而采用智能最大滿意度方案，有91人分得了選題（其余學生采用手工分配）；在滿意度方面，采用最大滿意度方案后，學生的整體滿意度和教師的整體滿意度均有較大提高。

4結束語

按照以上描述的設計思路和算法，采用Asp技術+Access后臺數據庫實現了畢業論文選題系統。該系統將選題結果學生和教師整體滿意度最大作為目標，不但大大降低了整個選題過程的工作量，而且大大提高了學生及教師對選題結果的整體滿意度，從而提高了選題質量。該系統在榆林學院信息工程學院2010屆計算機科學與技術專業本科畢業生的畢業論文選題中進行了應用，取得了良好的效果。

參考文獻：

篇6

Research of the Text Subjective Question's Auto Remarking Algorithm Based on Word Segmentation Algorithm &VSM

LI Xue-jun

(Southwest University of Science and Technology, Mianyang 621010, China)

Abstract: The paper makes use of the studied results(such as Vector Space Model (VSM), Word Segmentation algorithm and so on) of the native language understanding, and applys them in processing the text subjective question's answer (including the standard answer and the student's answer), and then it used the text_charactered vector matching algorithm to auto remark those student's examining paper by the computer system. According to the experiment, the algorithm has accuracy of remarking and some valuable domains of application.

Key words: Auto-remarking; Word Segmentation algorithm; Vector Space Model (VSM); Text character matched

隨著計算機技術和互聯網技術迅猛發展，傳統教育模式發生了變化，越來越多的課程提出了在線考試的需求。計算機可以很好地完成客觀題（如選擇題、判斷題）的判分工作，其判分策略、關鍵技術及其應用實例詳見文獻[1]至文獻[3]。亦即把考生作答的結果和題目標準答案進行精確匹配從而得到考生的得分。文獻[4]提出了一種近似串匹配算法來對文本錄入題的自動評分算法，其本質還是進行文本的比較，與客觀題的判分原理基本是相同的。

計算機自動評分是指利用計算機程序來模擬人工評分的標準和內部過程。對客觀題的評分是通過把試題的標準答案與考生的答案做一個精確比較，并據此作為是否給學生相應的題目分值；對于主觀題，目前一般是讓考生把其作答的結果形成一個文件（答案文件），再通過網絡把考生的答案文件上傳到考試服務器中的專用目錄中，科任教師在考試結束后對考生的答案文件進行人工評判來進行給分；最后把考生客觀題的計算機自動評分結果和主觀題的人工評分結果累加起來作為考生的最終成績。對于客觀題可以完全不要人工干預，而主觀題就必須在人工干預下才能完成。

因此本文就此提出將人工智能的自然語言理解技術（主要是分詞算法）、文本的空間向量模型表示和知識的框架表示內容應用到網絡考試系統中的主觀題的自動評分過程中。

1 文本主觀題自動評分原理

對于在線考試系統來說，其自動評分是在特定范圍內的，不需要讓其理解所有的自然語言，只需要理解標準答案即可。因此，應該使用某種算法使標準答案轉化成機器能夠理解的形式，將考生答案也按照一定的規則轉化成計算機可以理解的形式，然后再將其和標準答案進行匹配并評分。其關鍵是如何將評分規則轉化為可以被機器理解的知識庫。主觀題的自動評分原理如圖1所示。

2 自動分詞算法簡介

2.1 最大匹配分詞算法

匹配分詞法是按照一定的策略將待切分的漢字串與一個“充分大的”機器詞典（如金山詞霸等）中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配。按照不同長度優先匹配的情況，可以分為最大（最長）匹配和最?。ㄗ疃蹋┢ヅ?。最大匹配分詞法即先確定一個最大的詞的長度，然后從左（正向）或從右（逆向）取該長度的詞串，將詞串與詞典中的詞條匹配，如果沒有該詞則去掉一個字符繼續匹配，以此類推，直到達到匹配或剩下一個單字為止。

2.2 最大概率分詞算法

最大概率分詞算法的基本思想是：假設一個待切分的漢字串可能包含多種分詞結果，將其中概率最大的那個作為該字串的分詞結果。例如，有一個句子S＝“有意見分歧”，第一種分詞路徑W1＝“有/意見/分歧/”，第二種分詞路徑W2＝“有意/見/分歧/”，如圖2所示。到底應該選擇哪一種為最后的分詞結果呢？

根據概率分詞算法的基本思想，需要計算每一種方法出現的選取概率的作為最后結果，即計算Max(P(W1|S), P(W2|S))。概率計算方法如圖3所示。

每一個詞匯出現的概率P(wi) 可以在帶詞頻的詞典中查出。通過查詞典可以得到每個詞的概率為：P(有)=0.0180，P(有意)=0.0005，P(意見)=,0.0010，P(見) =0.0002，P(分歧)=0.0001。

對于第一種分詞方法：P(w1) = P(有) * P(意見) * P(分歧) = 1.8×10-9；

對于第二種分詞方法：P(w2) = P(有意) * P(見) * P(分歧) = 1×10-11；

由上所示，P(w1) > P(w2)，所以取第一種方法作為分詞結果。

3 文本矢量特征匹配算法

主觀試題的答案以文本方式存儲，經過分詞后的文本如何表示才能更加容易地被計算機處理關系到文本處理的準確性，因此文本表示方法是自動評分算法的一個關鍵問題。近年來，在Web文本信息特征獲取算法的研究中，矢量空間模型(Vector Space Model，VSM )[5-6]是應用較多且效果較好的方法之一，本算法借鑒了該模型的思想。在矢量空間模型中，文本被看作由一組正交詞條所生成的矢量空間。根據這個思想，同時考慮到考試評分中經常將試題答案分為幾個要點，因此提出主觀題成績評判模型為：

首先，答案文本是由一些要點組成，如果把答案文本（Answer text 用A來表示）看成一個由n個要點（Pi）組成的集合，則可以這樣表示答案：A={P1,P2,…,Pi,…,Pn}；設每個要點Pi的分值為Mi，則該答案的總分M為：；按照VSM思想，將標準答案每一個要點Pi被看成是由Ki個特征詞（wj）組成的向量P：；設每個特征詞的權重是wj（由經驗豐富的任課教師人工設置），則其歸一化權重為：；設考生答案的每一個要點Pi'也被看成是由Ki'個特征詞（wj'）組成的向量P'：；通過計算考生答案和標準答案的向量間的距離并據此計算考生可得到到該要點的分值，即：(如果向量間的距離為0，則說明考生答案和標準答案完全匹配，考生可以拿到該要點的所有分值)；考生所得總分M'為：。

4 算法測試及結論

本論文采用oracle作為后臺數據庫管理系統（因為系統所用的詞典數據庫都比較大），基于B/S模式設計了基于文本的主觀題自動評分測試軟件。通過對不同名詞解釋題目（答案長度及復雜度不同）的評測，再將本算法評得的分數與人工評分相比，分數的容差在（－0.5～＋0.5），可以測得其評分的準確度在86.93％。通過實際的數據測試可以看出，答案越復雜，要點越多，評分的準確性越差；相反，要點越少，答案越簡單，評分的準確性越好。而且人工設置關鍵詞和權重也有利有弊，人工設置固然增強了系統的準確程度，但是其前提是設置人必須是有經驗的老師，如果是沒有經驗的老師設置，則給算法增加了人為的誤差。該算法具有一定的實用性，但還有待進一步的完善。

參考文獻：

[1] 華蕊. 自動組卷及評分系統的設計[J]. 中國電化教育.2002,(2):84-85.

[2] 朱映輝, 江玉珍.計算機自動評卷策略分析與研究[J]. 電腦知識與技術,2005,(35):30-32.

[3] 李丁. 計算機考試系統中自動評分策略的研究與實現[J]. 廣東廣播電視大學學報,2002,11(4):30-32.

篇7

Key words: immune theory clonal selection antibodies circulating complement

一、引言

人工免疫系統是一個新興的計算智能研究領域。近年來,人工免疫系統及其應用已逐漸成為了智能信息系統中的研究熱點。生物免疫系統的免疫識別過程能在較短的時間內利用數量相對有限的抗體去識別近乎無限多的抗原,從信息處理的角度看,這是在資源受限條件下的一整套高效問題求解機制。克隆選擇學說的基因重組、親和度成熟、受體編輯等機制較好地從個體層次上闡述了這種高效問題求解能力的形成,因而成為多種人工免疫系統模型和算法的重要思想來源,免疫算法就是一種借鑒該系統特性而形成的啟發式搜索算法.它具有保持種群分布多樣性的特性,避免陷入局部最優解的優點。

二、克隆選擇原理

克隆選擇是生物免疫系統理論的重要學說,其原理(如下圖1所示)的基本思想是只有那些能夠識別抗原的細胞才進行擴增,只有這些細胞才能被選擇并保留下來,而那些不能識別抗原的細胞則不選擇,也不進行擴增。骨髓中微小的“休眠”的B細胞每一個都載有一個不同的抗體類型。這些細胞載有對于抗原特異的受體,擴增分化成漿細胞和記憶細胞。

免疫系統在成長的克隆中也是自適應的,同時也呈現了一種變異機制,在對抗體特異編碼的基因中產生極高頻率點變異。該機制(體細胞高頻變異)與為改進抗原結合而進行的選擇,共同導致細胞與抗原具有極高的親和力匹配。

根據免疫系統中的克隆選擇學說的思想,該算法在抗體種群和抗體優秀決定基中進行克隆選擇操作,全面的模擬了生物免疫系統克隆選擇的過程,很好的保持了抗體種群的多樣性。

三、克隆選擇算法

3.1 抗體/抗原匹配算法

要確定一個B細胞對象與提呈的抗原結合得有多好,在抗原上任何點開始匹配;匹配算法計算每一位,在抗原與抗體之間以互補的方式進行匹配,得出匹配值,再從匹配分值得到結合值,根據抗體的結合值的大小可以看出抗體和抗原是否結合的完美,并且可以判定出結合完美的抗體中哪些決定基起到了關鍵的作用。

對于一個抗體結合一個抗原,結合必須是穩定的,也就是匹配分值在匹配發生之前必須超過一定的閾值。該設定閾值為抗體大小的一半。該方法是Hightower的匹配算法的修改,只是多種偽生物匹配的一種。

抗體/抗原匹配算法的描述:

(1)初始化抗體群,針對抗體與抗原的決定基逐位進行異或操作,若抗體和抗原相對應的決定基相同為0,不同為1,結果統記為c;

(2)將抗體與抗原的決定基逐位進行異或操作結果的累積和記為(公式一);

(3)對由兩個或者更多個1組成的每一區域記錄長度為l;

(4)記抗體的結合度為(公式二);

(5)定義閾值為

(6)抗體Ab 移位一位。

3.2 克隆選擇算法的實現

克隆選擇算法的實質是在進化過程中,在每一代最優解的附近,根據親和度的大小進行克隆,產生一個變異解的群體,從而擴大了搜索范圍(即增加了抗體的多樣性),有助于防止進化的早熟和搜索限于局部極小值,同時通過克隆選擇來加快收斂速度。其基本思想為:隨機生成N個抗體組成的抗體群,對這些抗體進行一些操作后,選出抗體中優秀的決定基片段,針對這些優秀的決定基片段進行克隆操作,從而形成子抗體?？寺∵x擇操作只是在優秀的抗體決定基中進行,而不是在抗體的所有決定基中。

克隆選擇算法是根據克隆選擇原理和親和度的成熟發展而來的,其主要考慮了免疫方面的如下幾個方面:

(1)保持功能性的細胞從指令系統中分離;

(2)受刺激最強的個體進行選擇和克隆;

(3)為受刺激的細胞死亡;

(4)親和力度較好的克隆個體重新選擇;

(5)多樣化的產生和保持。

克隆選擇算法的實現步驟(流程圖如圖2所示):

(1)初始化。隨機產生初始的抗體群(P);

(2)計算抗體與抗原的結合度。本文采用的抗體和抗原是否完美結合的匹配算法,是由Hightower提出的,對抗體和抗原逐位進行異或操作,即抗體和抗原的決定基位相同記為0,不同記為1,若抗體和抗原結合,則其為1,根據公式一得出該抗體的匹配值,然后根據公式二可得到該組抗體和抗原的結合強度值(M);

(3)挖掘一個抗體中優秀的決定基片段。根據抗體和抗原的結合的匹配程度,我們可以看出抗體與抗原能夠結合上的決定基位,算法中提到必須是兩個或者更多個連續結合的決定基片段才進行挖掘提取(Pm)。

(4)對選擇出抗體的優秀決定基的片段進行克隆操作,產生一個暫時的克隆群體(C);

(5)隨機生成新的編碼融合進暫時的克隆群體中,形成新的抗體群(Pn)。

3.3 抗體的循環補充

生物免疫系統中為了保持抗體的多樣性,每天都會產生大量的新的抗體注入到免疫系

統中,其中大多數抗體決定基的片段會因為結合度太低而遭受到抑制,但仍有少數的抗體片段跟抗原具有很好的結合,獲得了克隆擴增機會。為了模擬這一抗體循環補充機制,我們在每次對優秀抗體決定基片段的提取之后,再隨機產生的抗體決定基注入到提取出來的優秀抗體決定基片段中,形成新的抗體進入到克隆擴增以及結合度成熟的過程中,以提高抗體的多樣性,實現全局范圍內的搜索優化,避免陷入局部最優解。

四、克隆選擇算法運行結果

圖3(a)中我們可以清楚的看到抗原與抗體是怎樣結合的,并找到了能夠完美結合的抗體中優秀的決定基片段,根據算法的運行可得出抗體與抗原的結合度為156。圖3(b)中可以看出算法能夠對這些優秀決定基片段進行了挖掘。圖3(c)中算法實現克隆。圖3

(d)中隨機生成新的編碼融合進暫時的克隆群體中,形成新的抗體群。

五、結束語

借鑒了生物免疫系統中的克隆選擇原理,從而設計了本算法。在文中詳細闡述了算法的實現步驟,并且該算法通過調試能正確的完成其功能輸出。但是該算法還沒有通過實例驗證,在接下來的工作中,將本算法應用到實例中,來判定算法的性能。

參考文獻:

[1]韋巍,張國宏.人工免疫系統及其在控制系統中的應用.控制理論與應用,2002,19 (2):157-160

[2]莫宏偉.人工免疫系統原理與應用.哈爾濱工業大學出版社.2003.1390

篇8

1、積相關算法概述

以圖像匹配為基礎的電視跟蹤方法,習慣上稱為電視圖像相關跟蹤,簡稱為相關跟蹤。積相關算法是常見的相關算法中的一種,也叫歸一化相關算法:

相似性度量(x0,y0)的表達式為:

n~(x0,y0)=m-1X=0m-1y=0f(x,y)t(x+x0,y+y0)m-1X=0m-1y=0f2(x,y)m-1X=0m-1y=0t2(x+x0,y+y0)

其中,0≤x0≤n-m, 0≤y0≤n-m。如果把f(x,y)和t(x,y)分別看作兩個歐式空間里的矢量,那么積相關算法的度量值表達式正是這兩個矢量在歐式空間里夾角的余弦。這是一個非常有用的性質,它的實際意義是,當環境光強發生變換時。應用積相關算法可以不受干擾。

2、跟蹤穩定性的研究

所謂跟蹤的穩定性是指匹配點的位置是否能夠唯一確定或者在一個極小的范圍內滑動。研究系統跟蹤的穩定性具有十分重要的意義。

2.1圖像預處理對跟蹤穩定性的影響

在智能電視跟蹤系統中實現積相關算法時,采取必要的圖像預處理是非常必要和有益的。對模板和實時圖像進行灰度均衡,使相關峰變得尖銳,從而提高跟蹤性能;增大圖像的對比度,也可以使相關峰變得尖銳,從而提高跟蹤性能;對圖像進行灰度最小化處理,使相關峰變得尖銳,提高跟蹤性能。

2.2模板選取對跟蹤穩定性的影響

積相關跟蹤算法的模板需要人工在視場范圍內進行鎖定,這個初始的第一個模板對跟蹤效果也是有影響的。為了得到良好的跟蹤效果,相關峰應當盡量選擇在圖像比較復雜并且沒有規律的區域內。

2.3奇偶場對跟蹤穩定性的影響

系統采用的攝像頭是按照PAL-D制式進行隔行掃描按照奇偶場產生圖像的。對一幅靜止的圖像如果采用隔場匹配,那么一個模板始終與奇數場或者偶數場的實時圖像進行匹配,此時跟蹤點就始終是穩定的。對于動態的、連續的圖像,應該在算法中加入一些處理措施,比如對模板進行刷新,否則可能造成跟蹤不穩定。

3、簡化的快速積相關圖像匹配算法

基于前面給出的簡化歸一化積相關度量方法,為了進一步減少匹配算法匹配時間,提高匹配效率,且同時保證一定的匹配精度與匹配概率,設計了先粗后精的分層匹配控制策略。

3.1先粗后精的分層匹配控制策略

下圖中給出了匹配控制策略的設計框圖。

這種匹配控制策略首先是進行粗匹配,確定匹配點的大概位置或候選位置,接著進行精匹配,確定匹配點的精確位置或最佳位置。精匹配是在粗匹配的結果---候選匹配子圖中完成的,因而搜索范圍大大減少,提高了匹配速度。

對于本文算法,使用該方案需要注意以下三點。

(1) 粗匹配階段,為了保證精匹配階段的有效性,必須確保粗篩選后所保留的預選點包含有匹配點。

(2) 門限法實現起來難度較大,多數是靠大量實驗及經驗獲取,且僅在特定的情況下可以采用。實際中,可以考慮采用3~5點篩選法,即直接取粗匹配階段度量值最優的3~5個匹配點作為精匹配基準點。

(3) 圖像的預處理是指對匹配圖像的灰度數據進行一定的壓縮或特征提取。在粗匹配階段,可以考慮隔像素取值且隔像素搜索。而在精匹配階段,像素值及搜索范圍均要適當擴展。

3.2算法設計

結合簡化的度量方法及前面給出的先粗后精的分層匹配控制方案,設計了簡化的快速歸一化積相關圖像匹配算法。

(1) 粗匹配階段

計算總的匹配搜索次數(如對于大小分別為m×m和n×n的基準圖與實時圖,則總的搜索次數為(m-n+1)×(m-n+1),進行循環遞推匹配。匹配準則如下。

①每隔n1像素從基準圖左上角開始掃描獲取各個基準子圖,并在實時圖及所選的基準子圖中隔n2個像素取其滅度值,組成用于相關匹配的維數較小的灰度矢量。

②利用簡化的歸一化積相關度量方法比較基準子圖與實時圖灰度矢量的相似性。

③采用遞歸比較的方法得到3~5個最優的匹配點,對應的基準子圖作為候選配子圖。

(2) 精匹配階段

在粗匹配階段得到的各個匹配點周圍適當展開進行搜索匹配(若粗匹配階段是隔n1像素進行搜索的,則在各匹配點周圍展開的幅值為應在n1/2到n1的范圍內)。

①利用簡化的積相關度量方法逐一取候選子圖,并在其擴展的范圍內進行灰度匹配。

②所有度量值中,Rs(u,v)值最大的匹配位置便是最終的匹配結果。

4、提高跟蹤實時性

經過大量的實驗,采用快速的簡化積相關算法進行匹配仿真實驗可得出如下結論:

第一是積相關及本文簡化快速積相關算法在智能電視跟蹤系統中出項的穩定性干擾以及較小的幾何畸變具有良好的抑制作用,且實時圖像越大,其抑制能力越好。

第二是對未經選定的圖像,可以考慮對匹配數據及搜索方案進行適當調整以獲得滿意的匹配效率。對于經過選定的圖像,采用本文提出簡化的積相關度量方法及先粗后精的分層匹配控制策略,有效地提高了匹配效率。

第三是減少匹配次數。在匹配時,進行一次粗匹配和二次精匹配。一次粗匹配時將步長設為2個像素,這樣可以使計算量減少為原來的1/4。需要指出的是,采取上述的參數進行積相關處理時,一次粗匹配的過程中,可能會遺漏實際的最佳匹配點,但是最佳匹配區域不會被遺漏,也就是說,最佳匹配點可以在二次精匹配中找回。

總之,通過上述方法可以在有限的硬件條件下,有效地提高了系統跟蹤的穩定和實時性。

參考文獻:

[1] Franz Matthias O, Bernhard. Scene-based homing by image matching[J].Biol. Cybern,1998:191-202.

[2]劉揚,趙峰偉,等.景像匹配區選擇方法研究[J].紅外與激光工程, 2001, 30(3): 168-170.

[3]任仙怡,廖云濤,張桂林等.一種新的相關跟蹤方法研究[J].中國圖象圖形學報(A版),2002,7(6):553~557.

[4]劉嘉.應用隨機過程[M].北京:科學出版社,2002:12~13.

[5]彭架雄,雷達圖像匹配制導技術,華中理工大學.

[6]孔丹,李介谷.亞像元精度的圖像匹配技術[J].紅外與激光工程,1999,27(1): 29-32.

[7]李尊民.電視圖像自動跟蹤的基本原理.國防工業出版社.1998.

[8]齊文寧.導彈上圖象處理機的研制及邊緣提取算法的研究.東南大學碩士學位論文.1997.

篇9

影像匹配實際上就是兩幅（或者多幅）影像之間識別同名點，它是計算機視覺及數字攝影測量的核心問題。我們知道要匹配的點的同名像點肯定在其同名核線上。在進行最小二乘影像匹配之前，需要先進行粗匹配。然后在粗匹配的基礎上用最小二乘法進行精匹配。我們這次討論的是利用一維搜索的方法來進行粗匹配。這就是利用同名核線來進行同名像點的粗匹配。這相對于二維匹配來說速度更快。

1.1基于數字影像幾何糾正法提取核線，利用共面條件來確定同名核線

我們知道，核線在航空攝影測量上是相互不平行的，它們相交于一點---核點。但是如果將影像上的核線投影（或者稱為糾正）到一對“相對水平”-------平行于攝影基線的影像對上后，則核線相互平行。正是由于“水平”的像片具有這么一特性，我們就有可能在“水平”像片上建立規則的格網，它的行就是核線，核線上像元素（坐標為xt、yt）的灰度可由它對應的實際像片的像元素的坐標為x，y的灰度求的 ，即g（xt，yt）=g（x，y）。

根據前邊的共線方程，同一攝站點攝取的水平像片與傾斜像片，其水平和傾斜像片的坐標之間的關系為：

(1-1-1)

(1-1-2)

上邊的式子中a1,a2…,c3為左片的九個方向余弦，是該像片的外方位角素的函數，f為像片主距。顯然在水平像片上，當yt為常數的時候，則為核線,將yt=c代入（1-1-1）和（1-1-2）式經整理，得：

（1-1-3）

其中：

e3=d3

若在“水平”像片上以等間隔獲取一系列xt值 ，(k+1)*,(k+2)*…,可以得到一系列的像片坐標（x1，y1），（x2，y2），（x3，y3），…，這些點就位于傾斜像片p的核線上。

同樣以yt=c 代入右邊的共線方程：

(1-1-4)

(1-1-5)

其中， ， ，… 右方像片的對于單獨像對像空間輔助坐標的角方位元素的函數，由此可得右片上的同名核線。

1.2核線的重排列（重新采樣）

已知原始的影像的灰度序列，為求待定的平行于基線的“水平”影像。這就需要進行核線的灰度重采樣。按照式（1-1-1）和（1-1-2）將“水平”像片上的坐標u，v反算到原始影像上的x，y。但是由于所求得的像點不一定恰好都落在原始影像采樣的像元中心，這就必須進行灰度的內插-----重采樣。通常所用到的是雙線形插值法，取臨近的四個像元點的灰度的數值進行待求點的灰度的計算。

圖1-2-1雙線形重采樣

本公式中y1代P點到g1，g4連線的距離，x1代表P點到g3,g2連線的距離的大小

1.3數字影像匹配的基本算法

本論文講述的相關系數法主要是對于一維影像相關的。

如圖1-3-1所示是一維影像相關的目標區和搜索區（這里取m=n）。設g代表目標區內的點組的灰度值，g’代表搜索區內相應點組的灰度值，則每個點組共取得了n個點的灰度值的均值為

圖1-3-1一維相關目標和搜索區域

，（i=0，1，2…n） （1-3-1）

兩個點組的方差 ， 分別為：

， （1-3-2）

兩個點組的協方差 為：

（1-3-3）

則兩個點組的相關系數 為：

（0,1,… -n） （1-3-4）

在搜索區內沿核線尋找同名像點，每次移動一個像素，按照（1-3-4）來依次相關系數 ，取其中的最大的數值，其對應的相關窗口的中心像素就被認為是目標點的同名像點。

1.4用相關系數的拋物線擬合來提高相關精度

為了把同名點求的更為準確一些，可以把相關系數的最大點i點左右若干點（一般取左右個兩個點）聯系起來，從而將其函數的最大值k處的作為尋求的同名點的位置，結果會更好一些。

圖1-4-1拋物線擬合

如圖1-4-1所示設有相鄰像元素系處的5個相關系數，用一個二次拋物線方程式來擬合，取用的拋物線方程，代表相應S位置處灰度的數值。

（1-4-1）

式中的參數A，B，C用間接平差方法求的。此時拋物線頂點k處的位置為：

（1-4-2）

由相關系數拋物線擬合可以使相關精度提高到0.15-0.2個子像素（當信噪比較高的時候），但是相關精度和信噪比近似成反比例關系。當信噪比比較小的時候，采用相關系數拋物線擬合也不能提高相關精度。

2僅考慮相對位移的一維最小二乘影像匹配

2.1一維最小二乘影像匹配原理

在本次僅僅考慮相對位移的一維最小二乘影像相關。在一維影像相關中是在傾斜影像相對應的水平影像坐標系中沿x軸方向尋求同名點，若在最小二乘算法中把搜索區像點移動的位移量作為一個幾何參數引入，就可以直接解算像點的位移。

設有兩個一維灰度函數 ， ，除了隨機噪聲 ， 外， 相對于 存在位移量 。如圖4-3-1所示，則

（2-1-1）

則（2-1-2）

圖 2-1-1 僅考慮相對位移的一維最小二乘影像相關

為了解求相對位移量，需要對（2-1-2）式子進行線性化：

（2-1-3）

對離散的數字影像，灰度函數的導數 可以由差分 代替，即

（2-1-4）

其中 采樣間隔。令 ，則誤差方程式可以寫為；

（2-1-5）

為了解求 ，取一個窗口，對窗口內的每個像元素都可以列出一個誤差方程式，按照的原則，則可以求得影像的相對位移的量 ：

（2-1-6）

因為解算都是線性化的結果得到的，因此，解算需要迭代進行。解得 后，對 進行重新采樣，各迭代計算時，系數 以及常數項 均采用重新采樣后的灰度值進行計算。

2.2計算最佳的匹配點位

我們知道，影像匹配的目的是為了尋求獲得同名點。通常以待定的目標點建立一個目標窗口，窗口的中心點就是目標點。但是，在高精度影像相關中，必須考慮目標窗口的中心點是否是最佳的匹配點。根據最小二乘法影像匹配的精度理論可以知道：影像匹配中的精度取決于影像灰度的梯度 ， 。因此，可以用梯度的平方為權，在左方影像窗口中內對坐標做加權平均：

（2-2-1）

以它作為目標點坐標，它的同名點坐標可以由最小二乘法影像匹配所求得的幾何變換參數求得；

（2-2-2）

隨著以最小二乘法為基礎的高精度數字影像匹配算法的發展，為了近一步提高起可靠性與精度，攝影測量工作者進而有提出了各種帶有約束條件的最小二乘影像匹配的算法。例如，附帶有共線條件的最小二乘相關以及與VLL法相結合的最小二乘影像匹配方法都得到了廣泛的應用和研究。

3 最小二乘影像匹配的精度分析

篇10

鍵，在分布式環境下加速后綴數組的構造需要充分考慮到通信對算法性能的影響。串匹配問題是計算機科學中研究得最廣泛的問題之一，在文字編輯與處理、圖像處理、信息檢索、分子生物學等領域都有很廣泛的應用。本文解決的是分布式存儲環境下的精確串匹配問題。在串匹配的許多實際應用中一個確定的文本常常被查詢很多次(比如對非常長的基因序列的查詢)。針對這種情況，Manber.U和E.W.Myers提出建立后綴數組(suffixarrays)〔1〕來提高查詢的性能論文，而后綴數組最大的不足是它的構造時間過長。因此一直以來，如何快速有效地構造后綴數組成了提高基于后綴數組的串匹配算法性能的關

2USAA算法

假設N，M為文本串和模式串的長度，P為處理器數，算法設計思路如下:

(1)將長為N的文本串A均勻劃分成互不重盛的P段，分布于處理器。~(P一l)中，且使相鄰的文本段分布在相鄰的處理器中，顯然每個處理器中局部文本段的長度為〔N/P〕。

(2)除了處理器O外，其它每個處理器利用KMP算法計算分配到自己的文本串的頭個字符與模式串，基金項目:國家自然科學基金重點項目(60533020)的匹配信息。如果存在匹配情況，就向相鄰的前一個處理器發送最大匹配后綴長度Maxsuffixlen，否則就發送一個負數。每個處理器可獨立地計算和發送該值，所以這一步的計算復雜度為O(M)，通信復雜度為O(1)。

(3)處理器1~(P-l)接收前一個處理器的信息。

(4)利用Manber.U和E.W.Myers在文獻〔〔1〕中的算法各處理器并行地構造局部文本段的后綴數組。

(5)利用Manber.U和E.W.Myers在文獻〔1〕中的算法各處理器并行地進行模式申的匹配。算法的計算復雜度為O((N/P(109109(N/P)))，通信復雜度為0(1)，大大降低了通信復雜度。

3實驗結果及分析

我們在基于分布存儲的32節點HPRX2600高性能機群系統上測試了上述算法，比較了USAA和目前理論值最好的MMsortlz〕算法之間的性能，其計算復雜度為，通信復雜度為。

圖1給出了當M一16、P~2時，N的取值對算法執行時間的影響。從圖中看出當時，由于N、P的取值成了影響算法復雜度的主項，因此在實際應用中USAA算法比MMsort算法表現要好。

圖2給出了當N變大時，USAA算法和MMsort算法的通信時間比較?？梢钥闯觯S著文本串的規模變大，由于處理器間需要進行的通信量增加，MMsort算法的通信時間有明顯的上升，而USAA算法的上升幅度要顯著小于MMsort。

4結論

本文提出的USAA算法通過采取均勻的后綴分配方式來降低處理段間匹配時的通信消耗，在(N/P)M的情況下使算法在保持計算復雜度的同時大大降低了通信復雜度。通過實驗結果可以看到，USAA算法很好地解決了在分布式存儲環境下降低后級數組構造中的通信復雜度的問題。

參考文獻

篇11

Components Based Graduation Design Managing Information System

YANG Zu-qiao1, LIU Gui-mei2

(1.College of Mathematics & Computer Science, HuangGang Normal University, Huanggang 438000, China; 2.Educational Technology Center, HuangGang Normal University，Huanggang 438000 , China)

Abstract: According to construction status of digital campus and the actual demands of graduation design management in our school, the basic modules of the projection management system is designed based on the Java Web Component technology. To achieve the functions of user registration, teacher questions, student topics, upload documents, download information, tutoring etc., and selected theme matching algorithm and system security are discussed mainly. Application the system can regulate the graduation designs selection and management process, improve work efficiency, economize the human resources and management costs, improve the management level of graduate de? sign.

Key words: Java Web component；management information system; graduate design；matching algorithm; Workflow

長期以來，畢業設計管理全過程基本上是手工或計算機輔助打印等方式完成，這種管理方式效率較低，容易出錯，不能適應高校信息化的要求。因此需要一個針對此流程進行管理的系統，使得此過程更加方便，更加透明，更加高效，以節省更多的人力和不必要的工作?，F在有許多高校已經設計并開發了畢業設計管理系統，方便了學生和教師，提高了管理效率，但是，部分系統還是沒有從根本上改變畢業設計管理工作的總體流程和管理理念，存在信息孤立、交互方式單調等問題，也還有以下幾個待改進的方面：1）過多關注于畢業設計的選題管理，對畢業設計的過程管理的重視不夠；2）部分系統在可維護性、執行效率和可擴展性等方面還存在一些問題[1]；3）系統信息的安全性有待進一步提高[2]。

作為J2EE體系中的重要一環，JSP為創建高度動態的Web應用提供了一個獨特的開發環境[3]。JSP設計目標是為了使動態頁面編寫更容易，更簡單。到處可執行，JSP技術完全與平臺無關的設計，包含它的動態網頁和底層Server元件設計，加強元件功能，更容易建立動態網頁。由于Java Web組件技術具有以下優點：

1）可重復使用跨平臺的組件(如：JavaBean或Enterprise JavaBean組件)來執行更復雜的運算、數據處理；

2）組件可以跨平臺使用；

3）組件是基于二進制代碼編碼，運行效率高，安全性好。

該文利用Java Web組件技術開發一個適合地方計算機類專業的畢業設計管理系統，實現畢業設計全過程的信息化管理。

1系統設計

軟件體系結構的設計是整個軟件開發過程中的關鍵點。B/S架構在客戶端使用瀏覽器就可以訪問到系統，大大簡化了客戶端載荷，減輕了系統維護與升級的成本和工作量，降低了用戶的總體成本。系統總體任務是對學生和指導教師進行管理，在仔細分析管理流程和已有系統的特色基礎上，本系統采用三層B/S架構，包括瀏覽器、Web服器和數據庫服務器，如圖1所示。

第二個問題是系統的安全性問題。本系統中采用隨機登錄驗證碼機制防止惡意注冊和MD5加密機制保護用戶的密碼，可以實現對消息完整性的保護。這兩種安全措施可以有效保證用戶的密碼安全，從而提高系統的安全性能。

實現高校畢業設計及論文管理網絡化，為教師、學生以及學校管理都提供了極大便利，本系統有較強的針對性及實用性，能夠解決本校論文管理存在一系列問題，在投入使用后，為教師、學生和管理人員提供了交流溝通的平臺，實現管理人員、教師和學生的交流與互動，有效解決高校畢業設計中存在的一些問題，規范畢業設計流程，提高畢業設計的質量。系統在具體使用過程中，肯定還會出現這樣那樣一些問題，但隨著新技術不斷發展以及設計者對軟件體系不斷更新與完善，相信隨著本系統日漸成熟，給學校的教學管理及發展帶來方便。

[1]張敬普,婁鵬宇.工作流技術在畢業設計系統中的應用[J].數字技術與應用,2010 (8):35-35.

[2]曾小平,吳暾華.本科畢業設計管理系統的設計與實現[J].微型機與應用, 2011 ,30(18):83-85.

篇12

1 緒論

圖像拼接技術有悠久的研究歷史。早期用于航空遙感照片合成，在20世紀90年代Heung——Yeung Shum研究了同心圓拼圖(柱面全景圖)， 20世紀90年代中期，微軟研究院的Szeliski教授提出基于運動的全景圖像拼接模型，將8參數減低為4參數，2003年M.Brown發表了全自動的圖像拼接算法的文章，使用捆綁調整技術，同時，魚眼鏡頭拍攝圖像生成球面全景圖的繪制技術也得到廣泛研究。

2 全景圖像拼接技術的概述

2.1 全景圖的模式分類

全景圖根據圖像投影方式的不同，存在幾種全景圖像：一種是球面全景圖像，一種是多面體全景圖像，還有一種是最常用的柱面全景圖像。柱面全景處理起來比球面全景與多面體全景簡單得多，因而應用面比較廣。

2.2 全景圖的生成流程

全景圖的聲稱流程如下：圖像的采集，圖像的預處理，圖像的變換，圖像匹配，圖像的平滑處理。

3 基于特征匹配的柱面全景圖拼接技術的研究

3.1 原始圖像的采集和幾何校正

3.1.1 拍攝方法和原則

照相機拍攝時一般有三種情況：

1.旋轉照相機拍攝

在這種情況下，放置照相機的三腳架在拍攝過程中一直在同一位置。照相機繞垂直軸旋轉，每旋轉一定的角度，拍攝一張照片。拍攝得到一系列照片中相鄰兩張必須有部分重疊。建議相鄰圖像之間重疊比例達到50%。重疊比例越大，拼接就越容易。

2.平移照相機拍攝

平移照相機指的是照相機在一個平行于成像平面的方向上平移。這種情況的缺點：拍攝的相片在一個平面上，拍攝的三維感覺不如旋轉拍攝的。科技論文。

3.手持照相機拍攝

這種方法比較容易做到，手持照相機原地旋轉拍攝。但是，拼接手持照相機拍攝的照片是很困難的，因為在拍攝過程中，照相機的運動非常復雜。可以增加重疊比例，使照相機旋轉角度、平移減小，因而減小相鄰圖像之間的不連續程度。

用照相機拍攝全景圖像，要取得較好的效果，必須注意以下幾個方面的原則：

3.2 圖像的變換

將一幅圖像與另一幅圖像匹配，常需要對一幅圖像進行一系列的變換，這些變換可分為剛體變換、仿射變換、投影變換和非線性變換。

3.3 圖像的匹配

3.3.1圖像拼接算法的原理

一般情況下，經過柱面投影變換得到的具有重疊區域的柱面全景圖中相鄰的兩幅待拼接圖像間的重疊[2]范圍大約在30%-50%之間。為了減少在特征區域提取時候的盲目性，我們可以先對灰度圖像進行圖像輪廓的提取，盡量的讓選擇的特征區域包含獨特的信息，容易識別。

在圖像匹配過程中，希望匹配點要準確，即關峰尖銳，定位精度高，因此在實驗過程中用邊緣檢測的方法提取圖像的邊緣從而使圖像的輪廓更為清晰，這樣有利于提高匹配的精度和降低偽匹配的可能性。

3.3.2 基于特征區域的提取和匹配算法的實現

本文采用Moravec[3]算子進行特征區域的提取，窗口的大小可以采用55到2121。窗口越大，抗噪聲能力越強，同時運算量也越大。

特征區域的匹配過程步驟如下：

1.將匹配圖像重疊部分的像素灰度值和位置信息讀入數據矩陣B，矩陣B讀入的是匹配圖像重疊部分的數據。

2.設置一個或者多個二維循環，通過對循環條件的設置或者分段設置循環，使搜索路徑可以沿著預處理之后提取的輪廓邊沿進行，將整個圖像的重疊區域全部搜索一遍?？萍颊撐摹?/p>

3.沿著搜索的路徑提取矩陣B的55，并且對矩陣內部的元素進行運算，分別計算該矩陣和單位矩陣的元素的均方差和灰度差的絕對值之和，分別把它們賦給兩個變量。

4.將記錄的當時搜索區域和單位矩陣的均方差和灰度差的絕對值之和跟之前的記錄值作比較（記錄值的初值的均方差為0，灰度值的絕對值之和為10），記錄均方差的最大值和灰度值的絕對值之和的最小值，并且分別記錄它們的坐標位置。科技論文。

5.搜索矩陣下移，再次重復步驟2和步驟3。

6.搜索結束，就得到了在矩陣B中令均方差最小且灰度值的絕對值之和最大的區域，記錄該區域的位置和中心點的坐標位置。

在本課題的實現過程中，待拼接的圖像已經經過了預處理和輪廓提取，所以在拼接的過程中，只需要將算子的中心沿著重疊部分圖像的輪廓進行就可以了。

3.4圖像的平滑處理

在拍攝柱面全景圖時，周圍環境和相機本身引起的最大問題就是相鄰圖像之間的光照變化較大，會出現帶狀痕，為了消除這種拼接區域帶狀痕影響，提出了一種直方圖處理方法：

1.對于24位色圖，首先將RGB圖像轉換成HIS類型圖像，針對其I分量進行處理，等同于對灰度圖像的灰度值進行處理。

2.將兩幅圖像的1/3公共部分作為重疊區域，注意要保證兩個重疊區域像素數目一致。

3.分別計算左、右兩邊重疊區域的I分量或灰度圖像灰度值的和sum1與sum2。

4.Differ=sum1/sum2，將圖像2的每一個像素的I分量或者灰度圖像2的每一個像素的值與參數Differ相乘加權。這樣做的目的是將兩幅圖像的亮度均值統一，使得重疊區域在拼接時能夠平滑過渡。

4 總結與展望

隨著虛擬現實技術的不斷發展，虛擬現實技術開始走向大眾化，并應用于網上購物、網上旅游、網上教育和在線游戲等領域，虛擬現實系統將會成為未來世界一個不可缺少的重要組成部分。

【參考文獻】

[1]王玉珍.基于特征區域的圖像拼接技術.蘭州大學碩士學位論文，2001：

3-10

[2]蘭培真,馬越,邱志雄,金一垂.不同視點重疊圖像自動拼接算法.中國航海，2001，(2)：41-45

篇13

〔中圖分類號〕TP391 〔文獻標識碼〕A 〔文章編號〕1008-0821（2016）02-0140-05

〔Abstract〕Text mining is an important aspect of data mining technology.According to the features of syntactic rules，the paper uses the text mining technology，and puts forward the design model based on the syntactic rules text knowledge mining.It analyzes the working principles of the data preparation，the syntactic rules knowledge structure，the text preprocessing，the text mining and the evaluation of mining results.Meanwhile it expounds the process of the construction of the syntax rules.At last，the paper identifies the model after some physical experiments.All in all，the design has certain research significance and application value to implement the intelligent of the text knowledge mining.

〔Key words〕text mining；syntactic rules；pattern matching；text pretreatment

隨著信息技術、網絡技術和各種數字化資源的建設，人們正面臨著海量、快速增長的文本數據資源，傳統的搜索引擎和查找技術已遠遠不能滿足人們的需求。如何從大量原始的、未經處理的文本數據集合中挖掘出潛在未知的知識，滿足人們獲取各種信息和知識的需要，已成為一個重要的研究課題。

1 文本挖掘及句法規則概述

文本挖掘（Text Mining，TM）是在數據挖掘的基礎上發展起來的一個分支，它以文本數據作為挖掘對象，主要任務是對隱藏于海量文本中沒有檢測到的非結構化知識進行提取的過程[1]。文本挖掘處理的對象是由多數據源組成的大量文本文檔，包括新聞文章、研究論文、書籍期刊、報告會議、檔案文獻、Internet網絡信息等半結構化或者高度非結構化的數據[2]。

漢語句子的結構非常自由，但其蘊含的基本規則相對穩定，句法規則是從漢語本身的屬性特點出發，將構成句子的詞或詞組按一定的語法關系和句子結構，組合成能夠表達完整意思的規則[3]，如詞語的分類、句式結構的確定、句法描述體系和句法構成元素的建立等，它是對句子結構的抽象概括，通過組合和聚合關系造出無數合格的句子，是對句子分析的一種總結結果。

2 基于句法規則的文本知識挖掘技術的分析與設計

本文采用句法規則構造實現文本知識挖掘，主要設計如下：首先，根據知識的表示和用戶的不同需求，構造出能全面準確表達文本內容的句法規則；其次，針對多源文本數據的特點和存在的問題進行預處理操作，為核心挖掘提供干凈、準確、簡潔的目標數據；再次，基于模式匹配算法，執行句法規則與目標文本數據的匹配，得出滿足句法規則條件的挖掘結果；最后，通過一定的指標對挖掘結果進行評價，將滿足用戶需求的知識可視化表達到用戶界面，供其選擇和使用，具體過程如圖1所示：

2.1 數據準備

數據準備主要是多源文本數據的獲取，它通過多種數據源獲取用于文本知識挖掘的數據，并存儲在本地硬盤中[4]。文本數據的獲取有多種途徑，主要來源是Internet網絡信息、研究成果、各種專題數據，以及其他文獻資料。選擇文本數據的數據源需要遵循以下原則：一是能為對象提供詳細、準確數據；二是要考慮數據的可整合性、可挖掘性和現勢性。文本知識的挖掘是一種基于句法規則的集中式挖掘，務必要求多源文本數據在結構上能夠整合到同一平臺框架下，并且保持一定的現勢性，從而簡化挖掘操作，提高知識獲取的準確度。

2.2 句法規則構造

句法規則構造是根據知識的表示方法和漢語的句法組成結構，通過對表達語料庫的的詳細分析，將知識規則化，為核心挖掘提供模式匹配的基礎條件。它主要分為3個層次：模板元素、句法規則、規則庫。建立用于構造句法規則和約束文本分詞、詞性標注的模板元素，構造出用于模式匹配的句法規則，構建相應的規則樹。從模板元素建立到句法規則構造，再到規則庫的構建帶有明顯的層次性和結構性。

句法規則構造過程分為以下幾步：一是收集并提煉出資料中的模板元素并建立相應的模板元素庫；二是根據語法要求和句法結構將模板元素組合成句法規則；三是把句法規則存放入規則庫。

2.2.1 句法規則的模板元素

模板元素是用戶作為約束文本預處理結果的一種擴充詞典，各個模板元素之間相互作用、相互影響構成了表達文本內容的句法規則。在這里借鑒漢語句法結構組成和本體概念的構建方法，將構成規則的每個〈詞語〉抽象為詞性，每種詞性下面包含了能夠反映該詞性性質的元素，稱為模板元素，規則中的每個模板元素都是該事件的參與者，一個句法規則看作是一個句子的語義的某種抽象化表示[5]，用模板元素表示該句子的語義，具體表示為：

從式（1）可以看出，多個模板元素根據漢語句子的語法要求和句法結構組合，即可構成能夠表示特定文本知識的規則，我們稱這種表示知識的規則為句法規則。因此，本文的句法規則是以模板元素為基本單位，根據人們表達習慣將多個模板元素按照語法關系組合成能夠表達知識的句子。模板元素作為句法規則的組成，是一種類似本體的表達類型，可表示為屬性（內容1，內容2，…，內容n），其中屬性抽象為能夠表達該領域知識的任意一種詞性，如“詞性：名詞”，內容則表示該模板元素范圍內包含的所有詞的集合。

本文在采用中科院ICTCLAS分詞系統漢語詞性標記統計的基礎上，提出了多個屬性類別選項以描述模板元素，具體如表1所示：

然后，對各詞類內容進行具體劃分，如以謂詞表為例：

2.2.2 句法規則構造

句法規則是模式匹配的邏輯核心，是知識表示內容的形式化概要，起到把要挖掘的知識內容類型化和結構化的作用。一條句法規則通常指出模板元素之間的關系，當句法規則與目標文本進行匹配時，必須合理約束各模板元素之間的語法關系和句法結構，嚴格按照每個模板元素在句法規則中的出現順序對其進行匹配[4]。例如：北京是中國的首都，與天津市相鄰，它的句法化表達為：〈主語〉+〈謂詞〉+〈地名〉，〈連詞〉+〈地名〉+〈謂詞〉，它的句法規則為：n/v/ns/f/w2/cc/ns/v。

2.2.3 規則庫

規則庫是用戶需求與目標文本之間進行問題求解的基礎，用于描述相應領域內知識概要的產生式集合[6]，它包含了所有能反應和表達實體文本知識的方法和表現形式，能夠為用戶提供不同的抽象描述，形成不同的推理鏈，得出不同的挖掘結果。本文規則庫采用規則樹結構存儲，如圖2所示：

圖2中，規則庫作為樹的根結點，共包含24個子結點，分別代表本文構造的24條句法規則。按照結點所在層次由高到低分別定義為一級、二級、三級和四級規則。該規則樹構建的基本策略是：

（1）將所有的句法規則置于一個集合中，即規則庫作為規則樹的根結點；

（2）根據句法規則的組成結構對其進行劃分，將相互獨立并且不被包含的句法規則按編號順序（從A到X）依次作為第二層的子結點，定義為一級規則；

（3）將其余句法規則根據包含與被包含的關系，依次劃分到相應子結點下面，并分別定義為二級、三級和四級規則。

采用以上樹結構存儲句法規則，結構清晰，便于執行與目標文本的匹配，減少部分句法規則與目標文本之間不必要的匹配。

2.3 文本預處理

文本預處理是文本挖掘的基礎，主要對目標對象的多源文本數據進行操作，將多數據源中獲取的文本數據進行處理，為下一步的文本知識挖掘提供比較“滿意”的目標數據。預處理主要包括文本快速整合、文本分詞和詞性標注、目標文本存儲等，本文采用中科院的開源ICTCLAS分詞系統對文本進行分詞和詞性標注。

文本預處理主要分為3個步驟：

（1）多源文本數據快速整合。將目標對象的多源文本數據集成到同一文本文檔中。

（2）中文分詞和詞性標注。將經過整合的目標對象文本數據分詞、標注詞性。

（3）目標文本存儲。將目標文本以段為單位編碼并索引標記，建立兩個二維表分開存儲目標文本分詞結果和目標文本詞性標注結果。例如，對于預處理之后的目標文本：南京/n位于/v江蘇省/ns中部/f，我們采用表3和表4所示存儲：

2.4 文本知識挖掘

文本預處理完成以后，即可進行文本挖掘操作。文本知識挖掘是采用模式匹配算法，將規則庫中的句法規則和目標文本執行精確匹配，得出符合規則條件的文本結果，并將其保存。它的主要任務是通過各種算法挖掘出用戶需要的信息，主要包括特征提取、文本分類、文本聚類、文本提取、關聯分析等[7]。本文采用KMP（Knuth-Morris-Pratt）算法進行模式匹配，基本思想是：當匹配過程中出現字符比較不相等時，模式串利用已經得到的“部分匹配”結果將模式串向右“滑動”，重新開始下一趟的匹配。例如對于主串“acabaabaabcac”，模式串“abaabcac”，利用KMP算法進行匹配的過程如下：

具體挖掘流程如圖3：

基于句法規則的模式匹配的執行步驟為：

（1）讀取句法規則庫，輸入目標文本詞性和目標文本分詞，啟動基于句法規則的模式匹配。

（2）對規則庫中的句法規則按照由高到低級別依次和所有編碼的目標文本詞性執行匹配。采用匹配算法遍歷目標文本詞性執行精確匹配，直到所有句法規則與目標文本詞性執行完匹配，輸出所有句法規則匹配結果。若無句法規則匹配結果，則匹配失敗，結束整個模式匹配。

（3）將所有句法規則匹配結果轉換為對應文本字符。根據二維表編碼關聯返回到對應目標文本分詞中，根據索引標記將句法規則匹配結果轉換成相對應的文本字符，該文本字符即為文本知識挖掘結果。

（4）輸出所有基于句法規則的挖掘結果，匹配結束。

2.5 挖掘結果評價和知識表達

評價是指通過一定的評價標準對挖掘結果進行評估，把符合條件的結果返回到可視化模塊。知識表達是將評價后的結果表達到用戶界面，供用戶選擇使用，最終經過可視化表達的結果即為用戶期待已久的知識。文本挖掘質量評估是對挖掘結果的整體衡量，若挖掘結果滿足評價指標，則挖掘完成，否則重新挖掘。

3 實驗結果驗證

下面我們以鄭州市地理信息文本知識的挖掘為例，利用VisualStudio 2010作為開發平臺，介紹整個挖掘實現過程。

3.1 數據選取

打開數據源接口，通過Internet搜索引擎選取30篇鄭州市地理信息數據，并保存到“F：＼鄭州市地理信息文本數據”中。

3.2 文本預處理

對以上選取的文本數據進行預處理。在ICTCLAS分詞系統上進行設置，通過選擇文本、添加用戶詞典、分詞并標注詞性、結果保存，實現文本快速整合、分詞和詞性標注。對預處理后的目標文本設置過濾功能，將對應的目標文本分詞和目標文本詞性以段為單位編碼同時用索引標記，分開存儲。存儲結果如下圖所示：

3.3 文本知識挖掘

文本知識挖掘是在本文2.2句法規則構造的基礎上進行，主要分為3個過程：匹配條件提交、匹配實現和結果轉換。匹配條件提交指讀取規則庫、輸入目標文本詞性和目標文本分詞，匹配實現通過執行模式匹配算法代碼來實現，結果轉換利用句法規則匹配結果的編碼和索引標記將其轉換為對應的目標文本分詞字符，實現挖掘結果。挖掘結果分別如圖6所示：

3.4 評價和表達

在完成文本知識挖掘以后，便對挖掘結果進行評價，并按相對優劣次序將地理位置文本知識可視化表達，并可導出為常用的EXCEL、WORD等文檔格式，如圖7所示：

通過以上實例可以看出，采用基于句法規則的文本挖掘方法，能夠為用戶在挖掘結果中得到比較滿意的信息，從而較好的達到設計的目的。

4 結束語

隨著文本數據資源的不斷增長，僅僅通過簡單的搜索引擎和數據篩選功能已經無法滿足人們對信息和知識的需求，迫切需要高效率的信息分析方法。采用基于句法規則的文本知識挖掘設計方案，能夠從句法規則設計入手，利用現有文本挖掘技術，從眾多文本數據中快速地獲取用戶需求的知識，對實現文本知識智能化挖掘具有一定的借鑒意義。

參考文獻

[1]Antonis Spinakis.Text Mining A Powerful Tool for Knowledge Management[EB/OL].http：∥/articles/TextMining.pdf，2010，（7）.

[2]張雯雯，許鑫.文本挖掘工具述評[J].圖書情報工作，2012，（4）：26.

[3]楊暉.言語實踐中的句法認知[J].吉林師范大學學報：人文社會科學版，2007，（4）：64-66.

[4]馬紹龍.基于句法規則的地理位置文本知識挖掘[C].鄭州：信息工程大學論文集，2014（4）：170-173.