基于機器學(xué)習(xí)的英漢字典模糊查詢畢業(yè)設(shè)計論文

1、0A基礎(chǔ)理論B應(yīng)用研究OC調(diào)查報告0D其他本科生畢業(yè)設(shè)計（論文）基于機器學(xué)習(xí)的英漢字典模糊查詢二級學(xué)院 專 業(yè) 年 級 學(xué) 號作者姓名指導(dǎo)教師信息科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)2010 級2010344369蘇家輝蔡廣基副教授完成日期：2014年5月24日基于機器學(xué)習(xí)的英漢字典模糊查詢專業(yè)名稱：計算機科學(xué)與技術(shù)作者姓名：蘇家輝指導(dǎo)教師：蔡廣基論文答辯小組組長:蔡廣基成員：王曉曄關(guān)心論文成績：目錄1引言1矚慫潤厲侈瘞睞板庇賴。1.1研究背景及其意義1聞創(chuàng)溝熠鐺險愛禮譴凈。1.2研究內(nèi)容和目標(biāo)1殘鴛樓靜鏈瀨濟淑塹籟。2研究與實現(xiàn)中的關(guān)鍵技術(shù)irffl極額閉鎮(zhèn)檜豬訣錐。2.1機器學(xué)習(xí)的基本原理1彈貿(mào)

2、攝爾霽斃攬磚鹵庇。2.2有趣模式的提取1謀養(yǎng)技篋飆鐸慰類蔣薔。2.3有趣模式集的優(yōu)化2廈礴懇蹣駢時盡繼價騷。2.4使用動態(tài)規(guī)劃的最長公共子序列 2煢楨廣鯽飾選塊網(wǎng)羈淚。3系統(tǒng)設(shè)計 3鵝婭盡損鶴慘歷蘢絹賴。3.1總、體結(jié)木勾 3籟叢媽超為贍債蛭練淨(jìng)。3.2業(yè)務(wù)流程設(shè)計4預(yù)頌圣鉉債歲齦訝驊汆。3.3數(shù)據(jù)結(jié)木勾設(shè)i十4滲鉛嗆儼勻譴繁調(diào)硯錦。3.3.1宏定義 4銃誅臥瀉嗾圣騁呪頂廡。3.3.2結(jié)構(gòu)體 4擁締鳳襪備訊顎輪爛薔。3.3.3文件5贓熱俁|詢歲匱閶鄴稼騷。4實施應(yīng)用 5壇搏鄉(xiāng)囂懺萎銀鈴氈淚。4.1開發(fā)環(huán)境5蠟變膠癟報佞鉉錨鋪贅。4.1.1硬件平臺5買鯛鵰諧曇盧遙閆擷凄。4.1.2軟件平臺5綾鋪

3、鯛駕襯鵬蹤韋耀羅。4.2開發(fā)環(huán)境的搭建和配置 6驅(qū)蹶髏彥泱綏譎飴憂錦。4.3編寫代碼 6貓蛋驢繪燈鮒誅髏祝庇。4.3.1最長公共子序列長度核心、代碼6鍬籟饗逕瑣筆襖鷗婭薔。432機器學(xué)習(xí)模型的c語言實現(xiàn) 7構(gòu)氽頑簧碩飩弄齦話鷲。5測試與分析 13輒峰陽槿鰭涼網(wǎng)儂號栄。5.1 精確查詢的實現(xiàn) 13堯側(cè)閏繭絳闕絢勵覘贅。5.2 般模糊查詢的實現(xiàn)14識饒鎂錠縊濫覚?quán)羶皽D。5.3 基于動態(tài)規(guī)劃的模糊查詢實現(xiàn) 15凍跛鉞勞臘錯癇婦脛汆。5.4 機器學(xué)習(xí)模型對于LCS模糊查詢的優(yōu)化15恥誇銷滅縈歡煬鞏鷲錦。5.5 機器學(xué)習(xí)模型的自動優(yōu)化16裟腎鑰訛褪鉀澇懼統(tǒng)庫。6結(jié)論18碩癘鄴頑諂撞檸攜驟敎。參考文獻18

4、圏擻轅嬪諫遷擇槓秘驚。致謝18氫嗆躅竄貿(mào)懇彈濾頷泉?；跈C器學(xué)習(xí)的英漢字典模糊查詢作者蘇家輝指導(dǎo)教師蔡廣基副教授（湛江師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，湛江524048 ）摘要：本文研究機器學(xué)習(xí)的基本原理和實現(xiàn)方法，對一個使用動態(tài)規(guī)劃實現(xiàn)的英漢字典模糊查詢系統(tǒng) 構(gòu)建一個機器學(xué)習(xí)模型。該模型實現(xiàn)了對用戶的檢索習(xí)慣進行分析，提取用戶檢索數(shù)據(jù)中的有趣模式，并通 過統(tǒng)計頻度對模式集進行自動優(yōu)化，為用戶的模糊查詢提供智能化的查詢結(jié)果。銃鴿資贏車贖孫滅獅贅。關(guān)鍵詞：機器學(xué)習(xí)模型，動態(tài)規(guī)劃，模糊查詢Fuzzy query of an English-Chinese dictionary based on mach

5、inelearning慫闡譜鮫逕辱嘯畫長涼。Su JiahuiSchool of information science and technology, Zhanjiang Normal University, Zhanjiang, 524048 China諺辭調(diào)擔(dān)銃諂動禪瀉類。Abstract: Based on the machine learning theory, a model of the fuzzy query of an English-Chinese dictionary system, which is fulfilled by the dynamic programmin

6、g algorithm is given. The model analyses the user Yuszzy query data and finds out the connections between the data, recording the mining models, applies them to the fuzzy query set during a non-accurate searching, and automatically improves the mining models set according to the statistics at freque

7、ncies of user, providing intelligent solutions for the fuzzy query嘰覲註縹暢囁偽純輪鏈。Key words: Machine learning; dynamic programming algorithm; fiizzy query; 川；師爾次庫。41引言1.1研究背景及其意義機器學(xué)習(xí)是現(xiàn)代人工智能研究、發(fā)展的重要領(lǐng)域，它通過研究計算機如何模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)行為，通過分析、歸納、綜合建立人類學(xué)習(xí)過程的計算模型或認識模型，基于已有數(shù)據(jù)識別復(fù)雜模式，做出智 能化的決策，并將其應(yīng)用于實際問題屮，為解決問題提供可行決策和方案支持嘰自

8、1980年在卡內(nèi)基梅隆大 學(xué)召開第一屆機器學(xué)習(xí)研討會以來，機器學(xué)習(xí)的研究工作發(fā)展迅猛，已成為人工智能領(lǐng)域研究的中心課題之一。隨著機器學(xué)習(xí)的蓬勃發(fā)展，人們在工作屮累積了大量可供測試算 法的數(shù)據(jù)集或者超大數(shù)據(jù)集，機器學(xué)習(xí)工作者在此基礎(chǔ)上可以進行更精準(zhǔn)的研究。目前機器學(xué)習(xí)已經(jīng)廣泛應(yīng) 用于智能搜索、數(shù)據(jù)分析等領(lǐng)域，如許多大型的搜索引擎網(wǎng)站的智能化的用戶體驗都是基于機器學(xué)習(xí)等研究 成果實現(xiàn)的。在大數(shù)據(jù)時代，機器學(xué)習(xí)研究將會得到更大的發(fā)展。鵜漬蟆偉閱劍鹼腎邏蔽。1.2研究內(nèi)容和目標(biāo)研究機器學(xué)習(xí)模型的生成過程，構(gòu)建機器學(xué)習(xí)的模型，將其應(yīng)用到英漢字典模糊查詢屮。第2節(jié)介紹機器學(xué)習(xí)和模糊查詢中的基本思路和實現(xiàn)方

9、法，第3節(jié)具體介紹算法實現(xiàn)的設(shè)計和數(shù)據(jù)的處理，第4節(jié)編碼實現(xiàn)構(gòu)想，第5節(jié)通過一些測試用例驗證、完善算法的基本功能，最后一節(jié)對本 研究做出總結(jié)并提岀新展望。紂憂蔣氤頑蓋驅(qū)藥憫鶯。2研究與實現(xiàn)中的關(guān)鍵技術(shù)2.1機器學(xué)習(xí)的基本原理機器學(xué)習(xí)是從已有或動態(tài)的數(shù)據(jù)屮提取有用的新知識，并將其應(yīng)用到問題的決策屮，其基本過程為：1. 收集學(xué)習(xí)材料，即獲取的數(shù)據(jù)；2. 分析數(shù)據(jù)，從中提取有趣的模式；3. 基于數(shù)據(jù)分析獲取有趣的模式，生成知識庫，制定決策；4. 通過學(xué)習(xí)新知識檢驗知識庫數(shù)據(jù)的有效性，修改、完善知識庫。在步驟1屮獲取的知識是原始的數(shù)據(jù)或材料，他們看起來可能是雜亂無章的，因此在步驟2需要對數(shù)據(jù) 進行分析

10、，挖掘復(fù)雜的隱藏的模式，使用樸素的貝葉斯分類、噪聲處理等方法對數(shù)據(jù)進行分離、提取，然后 在將來的決策（步驟3）屮使用這些模式去提供方案。但是提取出來的模式也可能是無效的，這就需要步驟 4不斷地學(xué)習(xí)新的知識，判定模式是否有效，修改完善知識庫。穎芻莖峽殍億頓裊賠滋。2.2有趣模式的提取如何從原始數(shù)據(jù)屮提取有用的模式，挖掘那些隱藏的有趣知識？分類是數(shù)據(jù)分析的一種重要的形式， 通過它可以提取重要的數(shù)據(jù)類型。分類首先要基于現(xiàn)有數(shù)據(jù)建立一個分類模型，然后根據(jù)模型對數(shù)據(jù)進行分 類。分類模型有決策樹分類器、貝葉斯分類器和基于規(guī)則的分類器等國。濫駿膽閉驟徑閘詔寢膊。在英漢字典模糊查詢系統(tǒng)，使用的是基于規(guī)則的分類

11、器形如IF-THEN的分類器。規(guī)則的IF部分是前提條件，THEN部分是結(jié)論。假如用戶的某些輸入滿足特定的條件則可認為是有趣模式。一般情況 下，如果用戶本次輸入的數(shù)據(jù)在上一次模糊查詢的結(jié)果集屮，則可認為上一次為用戶提供的結(jié)果集屮的對應(yīng) 項是有趣的。如果不滿足這一條件則可認為上一次的模糊結(jié)果集對用戶沒有幫助，即為無效數(shù)據(jù)，丟棄之。英漢字典模糊查詢系統(tǒng)的規(guī)則分類器實現(xiàn)大體如下：銚錦級呀鰻鴻銀謎諏涼。本次是否為精確查詢?歸有趣模式4本次輸入在上一次模糊結(jié)果集屮？非有趣模式有趣模式非有趣模式圖2JL規(guī)則分類器的實現(xiàn)2.3有趣模式集的優(yōu)化有趣模式集屮的記錄都是用戶感興趣的，但是對于一個非精確的輸入可能存在

12、多個用戶感興趣的選擇項，如何確定最優(yōu)的選擇項呢？在統(tǒng)計學(xué)上，使用概率表示一件事情在大量測試下發(fā)生的可能性。假設(shè)A代表用戶的一個模糊輸入，Xi,Xi代表A輸入所對應(yīng)的用戶感興趣的選擇項，設(shè)p(A兇)為用戶輸入A后選擇Xi的概率，分別計每一個選擇項Xi的p(A|X)將具有最大值的選擇項排在最前面，即為最優(yōu)的選擇項。用戶每次輸入A后選擇Xi都是對A-Xi模式的一次強化。p(A|XXn(Xi)/n(A),在該式中n(Xi)表示Xi被選擇的次數(shù)，n(A)表示輸入A的總次數(shù)，對于計算A 的所有選擇項的p(A|Xi),分母都是相同的，因此在具體的實現(xiàn)中，只需要為每一個選擇項項添加一個頻度 計數(shù)，這樣具有最大

13、頻度計數(shù)的選擇項即為最優(yōu)的選擇項。擠貼綬電麥結(jié)銃贖 嘵類。2.4使用動態(tài)規(guī)劃的最長公共子序列動態(tài)規(guī)劃采用自底向上的遞推求值，把中間的結(jié)果存儲起來并用于后面的計算，對于改善蠻力搜索的時間復(fù)雜度是比較有效的，假設(shè)an, bm分別表示長度為n,m的兩個字符串，則a0,3nl中的任意組合表示3的子序列，bO.bm-l中的任意組合表示b的子序列，如果要求這兩個字 符串的最長公共子序列，采用簡單的線性規(guī)劃的方法是：列舉耳的所有所有2的n次方 個子序列，察看它與bm的最長公共子序列長度，采用這種方法的時間復(fù)雜度是指數(shù)級的0(22),如果采用動態(tài)規(guī)劃的方法可以使解決最初公共子序列問題優(yōu)化到0 (n logn)

14、o假設(shè)Lnm表示a的前n個字符與b的前m個字符之間的最長公共子序列長度，則Lnm的遞推公式如下：賠荊紳謖侖驟遼 輩襪銭。LCSflag初始值為0,用于標(biāo)記當(dāng)n或m為0時，前面是否有3的子序列與b的子序列相等的情況。對 于 n=0 或 m二0,若 an=am,貝 U Lnm=LCSflag=l,如果 an!=am,若 LCSflag=l 貝 U, Lnm=l ,否則 Lnm=0 ；塡礙籟饋決穩(wěn)賽針冊庫。對于n和m都不等于0的情況：若 an=bm則 Lnm=Ln-lm-l+l ；若 an!=bm則 Lnm=Ln-lm和 Lnm-1中的最大值。裊樣祕廬廂顫諺釧羋藺。3系統(tǒng)設(shè)計3.1總體結(jié)構(gòu)系統(tǒng)的主要

15、功能包括以下部分1. 用戶輸入接收用戶輸入的單詞或詞組，它們可能是精確的輸入，也可能是存在拼寫錯誤的單詞或詞組，如 department和deparmen等。倉嫗盤継囑瓏詁鍬齊驚。2. 精確查詢在字典的索引文件屮查找查看是否存在，如果存在,則去詞庫的譯義文件屮讀取，并將結(jié)果 輸出給用戶。3. 一般模糊查詢?nèi)绻ㄟ^精確查找無法查出該單詞/詞組，這種可能是由于單詞的單復(fù)數(shù)，動詞過去式，現(xiàn)在分詞的ing形式類等造成，因此一般模糊查詢就是對以上形式的單詞進行簡單的處理,如去掉詞尾的0 d等，然 后再對處理之后的單詞進行精確查詢。綻萬璉轆娛閥蛭鬭紹瀧。4. 基于最長公共子序列的模糊查詢(以下簡稱les查

16、詢)如果基于一般模糊查詢?nèi)詿o法查出，則使用les查詢，該查詢是基于全文的檢索，找出與輸入單詞最為相近的單詞，即與輸入單詞的最長公共子序列是在全文中的最大值的單詞，并將其作為選擇項輸出 給用戶。驍顧禪鸚疏瀆蕪領(lǐng)fflWo5. 機器學(xué)習(xí)的模塊開始時候，用戶的使用記錄為空。在一次les查詢之后，可以將les模糊查詢的結(jié)果集記錄起來，如果用 戶下一次查詢的輸入與les模糊查詢的結(jié)果集記錄有匹配項，則認為它們是一個有趣模式,并把其加入到有趣模 式集屮。每一次模糊查詢給用戶輸岀的結(jié)果集都會與模式結(jié)果集屮的結(jié)果進行匹配，如果找到,則把模式結(jié)果 集屮的匹配數(shù)據(jù)與模糊結(jié)果集，匹配數(shù)據(jù)優(yōu)先放到結(jié)果集前,去除重復(fù)的

17、項，生成最終結(jié)果集(決策)，最后輸出給 用戶。瑣針濺曖憚銀編馭篩涼。3.2業(yè)務(wù)流程設(shè)計系統(tǒng)的業(yè)務(wù)流程如下:是一*讀取釋義僕取釋義1取上次埠働結(jié)舉集灘加到凈式集圖3.1業(yè)務(wù)流程圖3.3數(shù)據(jù)結(jié)構(gòu)設(shè)計3.3.1宏定義宏定義含義#define WORDCOUNT 59372詞庫中單詞的個數(shù)#defi ne WORDLEN 24單詞的取人長度#defi ne Error(msg) perror(msg); eXit(l);出錯處理#defi ne PRENUM 5對于每個用戶輸入可以提取的有效模式的最大個數(shù)3.3.2結(jié)構(gòu)體1. 單詞索引記錄typedef structchar wordWORDLEN;i

18、nt offset;int len gth;Node;其+ word表示單詞，offset是該單詞在詞庫文件中的索引，length是該單詞的釋義的長度2. 用戶的偏好記錄typedef stnictchar wordWORDLEN;int count;Preference;其+word表示用戶偏好的單詞，count是該單詞的的支持度計數(shù)，即在用戶的輸入中該單詞被選屮的頻 數(shù)。鈿詩涇艷損樓紺養(yǎng)錫類。3. 模式記錄集typedef structchar inputWORDLEN;/用戶輸入的單詞Preference presMAXPRES;/最多記錄 5 個偏好Record;其中input是用戶的

19、非精確單詞，pres是該單詞對應(yīng)的用戶偏好單詞數(shù)組，最多5個記錄。3.3.3文件1. 單詞的索引文件star.ndx存放的是一個個Node類型的數(shù)據(jù)，每個單詞/詞組都有一個對應(yīng)的Node,這些數(shù)據(jù)按照單詞的英文次 序升序排列，因此在查找單詞時可使用二分查找快速檢索。櫛纏歐鋤棗鈕種鵰瑤鎂。2. 詞庫文件star.dict存放單詞的釋義3. 用戶輸入記錄文件search.dat存放用戶輸入的非精確單詞，及該單詞對應(yīng)的les模糊查詢結(jié)果集4. 模式記錄文件record.dat存放的是有趣模式記錄，這些記錄也是按用戶的輸入非精確單詞升序排序， 這樣方便在進行記錄查找時使用二分查找，快速的查詢某一記錄是

20、否存在，在記錄的內(nèi)部是按照模式的有效 次數(shù)降序按序的。轡烽楝剛殮攬瑤麗鬧應(yīng)。4實施應(yīng)用生1開發(fā)環(huán)境4.1.1 硬件平臺CPU： i5-4200h 2.8GHz ；內(nèi)存：256MB及以上。4.1.2 軟件平臺操作系統(tǒng)：Windows 虛擬機 VMware 10.0 卜的 ubuntu linux。開發(fā)工具：gcc,vim4.2開發(fā)環(huán)境的搭建和配置1 安裝vim在linux終端輸入sudo apt-get in stall vim-gtk撚后輸入root用戶密碼等待完成vim匸具的安裝山見揚爛滾澗輻i聶 興渙亂2. vim的基本配置在linux終端輸入vi /.vimrc按如下方式配置set nu

21、 set ts=4set sw=4set cindentset autoide nt3 環(huán)境變量的設(shè)置在終端輸入vi /.bashrc添加以下行：export PATH=“$PATH:./“保存Z后在命令行輸入 source .bashrc生3編寫代碼4.3.1最長公共子序列長度核心代碼int LCS(char* a,char* b)int nni j;int flag二0;n=strle n(a)-l;m=strle n(b)-l；intL100100=0);for(i=0;i=n ;i+)if(flag|(ai=bO)Li0=l；flag=l;else Li 0=0;flag 二 0;fo

22、 叩二 O;jv 二 m;j+)if(nag|(aO=bD)LOD=1；flag; else LOj=O;/char a100,b100;for(i=l;i=n;i+) for(j=l;j=m;j+)=Li-lDJLiD=Lij-l;elseLiD=Li-lD;return Ln m;4.3.2 機器學(xué)習(xí)模型的(:語言實現(xiàn)1.在learn.h屮的定義#ifndef_LEARN_H #define _LEARN_H #inelude dict.h #inelude #include #inelude #define MAXPRES 5/ #define WORDLEN 24/ #define P

23、RENUM 5 / typedef structchar wordWORDLEN;/ 用戶偏好 int count;/ 次數(shù)Preference;typedef structcharinputWORDLEN;/用戶選擇用戶偏好的最大個數(shù)項單詞最大長度有效模Preference式的個數(shù)presMAXPRES;/最多記錄5個偏好jRecord;/int Recordsize二sizeof(Record);/ 個記錄的大小 void RecordDatafchar* word,Node* nodes); void Ne wRecord (char* word,char* m3tch_word);vo

24、id Analysefchar* word);void Solutionfchar* newData,Node* nodes);void Decision(Node* dst_node,Node* srejiode);/用于快速查找查詢記錄或?qū)τ涗浛炫舏nt Recordcmp (const void * dst,const void * sre);int Prescmp (const void * dst,const void * sre);#endif主要函數(shù)解釋：RecordData :用于記錄用戶每次輸入的非精確單詞及其使用les模糊查詢得到的結(jié)果集。Analyse :分析用戶的輸入和

25、les模糊結(jié)果集間的關(guān)系，提取有趣模式。NewRecord:記錄有趣模式。Solution :提取與用戶輸入的非精確單詞相關(guān)的模式記錄。Decision :根據(jù)歷史模式記錄，生成最終的決策方案。2.在learn.c中主要函數(shù)的實現(xiàn)void RecordDatafchar* wordNode* nodes)/word代表用戶的輸入，nodes是模糊查詢的結(jié)果集FILE* fdfopenC./search.datVw+b);/打開并清空上一次的結(jié)果if(!fd)return;int nodejen=0;int len=strlen(word); fwritef&len,sizeof(int),lf

26、d); fwritefwordjjen/d);while(strlen(nodesnodeen.word)0)nodejen+; fwrite(&nodejen.sizeof(int),l,fd); fvrite(nodes,sizeof(Node),nodeJen/d); fclose(fd);int Recordcmp(const void * dst.const void * src)input,s-input);對用戶偏好按降序排序int Prescmp(const void * dst,const void * src)count) count);void Ne wReco rd (

27、char* word,cha r* m3tch_word)presnum.word)0) num+; 計算當(dāng)前用戶偏好 的數(shù)目 for(i=0;ipresi.word)matche d-pres i .count+;10脹鰻彈奧秘孫qsort(matched pres,nuinsizeof(Preference),P rescmp);戶李鎧膊。break;if(!(ipresi=newPre;else matchedpresi二newPre;/新記錄elseRecordCount+;Record newRcd 二0;strcpyCnewRcd.inputword); strcpy(newRcd

28、pres0wordmatch_word);newRcd.pres 0. count= 1;recordsRecordCount-l=newRcd;鮑躋峽禱紉誦幫廢掃對record數(shù)組重新排序 qsort(records,RecordCount,sizeof(Record),Recordcmp;/寫回記錄文件FILE* fw=fopenC./record.dat/r+b); fseek(fw,O,SEEK_SET);fwrite(&RecordCount,sizeof(int),l,fv/);fwritetrecordssizeofCRecordJRecordCountfw); free(rec

29、ords);fclose(fw);void Analysefchar * mmtch_word)FILE* fd=fopenC./search.dat，7rb);if(!fd)return;int len=0;freadC&len.sizeofQntJ.l/d);char wordlen+l;1fre ad (word, lje n, fd);wordlen=0;/printf(nvalue in An31yse:%sii%d：worden);int nodeen二0; fread(&nodeen,sizeof(int),l,fd);Node nodes nodeen;freadfnodess

30、izeoffNodeJjiode Jen/d);fclose(fd);int i=0;/判斷是否為有趣模式for(i=0;inode_len;i+)if(!strcmp(nodesiwordm3tch_word)NewReco rd (word,match_word);break;void Solution(char* newData,Node* nodes)pres numword)澇氣嘮懸萇鑿鑿梆涔/printf(npres value:%snmatched-presnum.word);應(yīng)。num+;/printf(匹配記錄中的 pres:%dnnum);iffnum PRENUM)num

31、 二 PRENUM;int i;for(i=0;ipresi.word); free (re cords);計算結(jié)點數(shù)目int Nodenum(Node* nodes)結(jié)點數(shù)組拷貝void Nodecpy(Node* dst_node,Node* src.node)intsrc_count=Nodenum(src_node);inti 二 0;for(i=0;isrccount;i+)(strcpy(dst_nodei.word,src_node i.word);結(jié)點查找int FindNodefchar* wordNode* nodesjnt num)int i=0;for(i=0;inum

32、;i+) iffJstrcasecmpfwordjiodesfil.word)/ 找到 return 1;return 0;/src.node: nodes from record filedes.node: final nodes array to dual search 做嵐縣纟侯虜榮產(chǎn)濤團藺。 void DecisionfNode* dstjiodeNode* src.node)/src_node表示從歷史數(shù)據(jù)屮獲取的數(shù)據(jù)，des_node本次模糊匹配結(jié)果int src_count=Nodenum(srcjiode);int dsLcount=Nodenum(dst_node);Node

33、 tempdsLcount;Node nilNode二0;/用于結(jié)點初始化Nodecpy(temp,dst_node);Node newNodessrc_count+dsCcount;/合并int j=0; forO=0;j(src_count+dst_count);j+) newNodesj=nilNode;/Nodecpy(newNodes,src_node);int newCount=Nodenum(newNodes);int i 二 0;for(i 二 0;ivdst_count;i+)if(! FindN ode (temp i .wordsrc.node.srccount)newN

34、odesnewCount二 temp i;newCount+;Nodecpy(dst_node,newNodes);5測試與分析在編寫好所有的代碼之后，在終端輸入命令gcc *.C即可編譯生成可執(zhí)行文件，然后在終端輸入./3.0址按 以下用例測試。誡俠劑鈍觸樂鵬燼禪騁。5.1精確查詢的實現(xiàn)測試用例1:word:mopmopn.拖把，鬼臉亂蓬蓬的頭發(fā)vt.用拖把洗擦，擦，拭vi.做鬼臉測試結(jié)果分析：用戶輸入“mop進行搜索，該單詞在索引文件屮找到，則從詞庫屮讀取其釋義并輸出。測試用例2：word:youyoupron.你,你們;一個人，任何人測試結(jié)果分析：用戶輸入“you”進行搜索，該單詞在索引

35、文件中找到，則從詞庫中讀取其釋義并輸出測試用例3：word:movemoven.移動，遷居，步驟vt.移動，開動，感動，鼓動vi.移動，離開，運行，遷移，行動測試結(jié)果分析：同上，可以精確查出“move，的釋義。查詢的限制：用戶檢索的英文單詞長度不能超過24個有效字符，無法對空輸入進行查詢。5.2 一般模糊查詢的實現(xiàn)測試用例4：word:moved moven.移動，遷居，步驟vt.移動，開動，感動，鼓動vi.移動，離開，運行，遷移，行動測試結(jié)果分析，在第一次精確查詢時，由于詞庫中并沒有“moved”，這是由于用戶的拼寫錯誤照成的，本例中用戶輸入的是單詞的過去式，可進行一般的處理，去掉詞尾的“d

36、”,再進行精確查詢，可輸出“move“對應(yīng)的英譯漢釋義。護飽兗爭詣繚飴癩別濾。測試用例5：word:jumppingjumpn.跳躍，跳動，上漲，驚跳 vt跳越，躍過，突升，使跳躍Vi.跳躍，跳，跳動，暴漲測試結(jié)果分析：用戶輸入的是“jumpping”，這個單詞也無法使用精確查詢，該單詞為ing形式，可以先去掉詞尾的“ing”查看是否可以找不到，若找不到再嘗試由于元音+輔音結(jié)尾的形如mop-mopping形式的規(guī)則，再去掉詞尾的一個字符，再次進行精確查找，輸出單詞jump的釋義。禺鉉們歟謙搗餃競蕩賺。測試用例6：word:flowers flowern.花，精華，盛時vi.開花，旺盛，成熟Vt

37、.使開花測試結(jié)果分析：同上，flowers并不在詞庫屮，是flower的復(fù)數(shù)形式，采用一般模糊查詢，輸出flower的 釋義。瑩諧齷薪賞組需纟芻嚴減。5.3基于動態(tài)規(guī)劃的模糊查詢實現(xiàn)測試用例7：worddot o您是否要搜索：lots ofplot outblot out a lot of pilot boat測試結(jié)果分析：用戶輸入“l(fā)ot of”，由于詞庫中不存在該單詞，也不是由于詞尾如動名詞、單復(fù)數(shù)、過去 式等原因造成的錯誤，使用一般模糊查找也無法確定出單詞的釋義。解決思路之一：使用基于全文的最長公 共子序列搜索，遍歷單詞索引文件中的所有單詞，找出與Toto”具有最長公共子序列最大值的5個

38、單詞或詞 組。但是由于基于動態(tài)規(guī)劃算法得岀的最長公共子序列長度并不是基于連續(xù)子序列的（盡管它在算法的效率 上是較優(yōu)的），因此還要使用機器學(xué)習(xí)模型對查詢結(jié)果集作進一步優(yōu)化。隸肅鵬毓轎驟鐐縛綢耀。5.4機器學(xué)習(xí)模型對于LCS模糊查詢的優(yōu)化測試用例8：（由于機器學(xué)習(xí)的過程是連續(xù)，以下測試結(jié)果是緊密關(guān)聯(lián)的）1. word:departmen 您是否要搜索: departed departure apartment department deportment2. word:departmentdepartmentn.部，部門;學(xué)部，系;司，局,處科3. word:departmen 您是否要搜索: de

39、partment departed departure apartment deportment4. word:deportment deportmentn.行為，舉止5. word:departmen 您是否要搜索: department deportment departed departure apartment測試結(jié)果分析：步驟1開始時不存在模式文件，輸入departmen 查找，會進入到LCS查找，得出來的模糊結(jié)果集是：departed,departure,apartment,department,deportment,不夠精確。納疇鰻吶祁禎錮膩鰲鏤。步驟2用戶根據(jù)提示輸入了“ de

40、partmentH得到釋義，并且department H在上一次LCS查找的模糊結(jié)果集 中，因此departmen 和“ departmentH將會作為一個有趣模式被提取出來并記錄到模式文件屮。風(fēng)攆鮪貓鐵頻鈣 薊糾廟。步驟3再次輸入departmen 查詢，這時已存在記錄department ”，會優(yōu)先輸出departmentn,得到優(yōu) 化的模糊結(jié)果集：滅曖駭諭鋅獵輛靚謖藹。department , departed,departure,apartment,deportment)。鎊鵰餉飾繚閱費渾癱騙。步驟4接著用戶選擇輸了 deportment它也在上一次LCS模糊集，所以departmen 和deportmentn 也會作為一個有趣模式被提取和保存。攪関頻蝶陣澇諭譴隴瀘。步驟5再次輸入departmen 查詢，模式記錄屮已有department和deportment最終得到的優(yōu)化模 糊結(jié)果集為：趕輾雛紈顆錚討躍滿賺。department , deportment , de pa rte d, dep ar tu re ,ap