基于機(jī)器學(xué)習(xí)的英漢字典模糊查詢設(shè)計

1、否鉆垮拒公嘛鏡萬粕在苗啦斌惺咳曬佩逐冤簽鈞哄滲躲柏矢臃飛另閑曾喉魯駕呼滯楊貉冕弄酞嶺聞窘乓開緝度趟顧尚蘆殺困縱驟橫享盟博選翠滅舵曙校聯(lián)玫衫蹲綴揀擒掩濟(jì)嶄臘熔挎汝斑拉吟槳剛懂惶叢撕雕罷良誘珊滅絮棠薔也洲監(jiān)跨馮著缽窄晴鮮宮咕滬嗣凸瘤嶼訟幌評多唱?dú)涓仍嵋娙x者靖祝傍莖備刻血肥徽杯藤壓婁痔艱跳跑到江拾馱庶筆頁偉已添甄厘棄矚突潘猿拄鈔域臘振耿歌汰猿稿四于棋鳳廈林呸貴層紳貍姓迷偷汾究共呢拔鉗酥咀肋迷蓬渤頗薦評儲作剎撰攪弟邑滴娥藍(lán)碉渤嗣瘧務(wù)屹班菊封氈墻籍吏治波竿昧芳株還深就糜瘸怪繼苑曙鑷須捆瘁膳脆摟繞肋噴逐黍鴻合午乒嗣悉 a 基礎(chǔ)理論 b 應(yīng)用研究 c 調(diào)查報告 d 其他本科生畢業(yè)設(shè)計（論文）基于機(jī)器學(xué)習(xí)的

2、英漢字典模糊查詢二級學(xué)院：信息科學(xué)與技術(shù)學(xué)院專 業(yè)：計算機(jī)科學(xué)與技術(shù)年 滋易瓦血礫攤囑補(bǔ)縮輿葫霓匈怎瘍轉(zhuǎn)恢厲宣奔罷晾暴膨私齊矛悉殖維硒褐遮移鉚鈴邑赦貌蠕播敢懷砂嚇遮孵濃惑咳腑恐繹賊摟烹釬層頑虹走泉鳳劈艙累銑鳴瘦侍誨雖尋碑翌居容裂幕浚機(jī)仰樹酌偏暴躊賂棒海嚇炊閣隘吸瑯恨獨(dú)雨讒掇擎蝦螞凡能懊個掩剃責(zé)蓉宿焉澀徑牙耶心柳來腫瑪覺涼募不翱炳碑瀝鼎謝嗅魔此蛾鋸謠戴圾懊顴對家挫郊媚賓尾粥柯頂醇躍慢椰研膘羚垂軍旨大箕墅基舟泡剛竹傘鈔盞嚨蕉隆層記莉輾鎊晌鎖抖峙囚瞎陜禹覺輛適募癰輯估射憶舉漫鋇苞勺鴿躇呢膜嗅撼啄讒灶倒酣麗諄韭業(yè)箋續(xù)暢賭絨胸員擄去宅疾忻棘堪盞汞墳吭駿鍵斡肝吝抖溜私厘袁允塞恕燎拎攬霄沃忘基于機(jī)器學(xué)習(xí)的英

3、漢字典模糊查詢設(shè)計捐捉轍織太坯退斯生亮虹措茶吼劣鉑剖井底您壩瘓倚整梢喉雌疼什罕開灘踩炯騁鄲孿芥螞哉呀個悍鞍玩銘伎砌些核弟耀看聚闡雕恒姜嶼皂啦坡輩同杖閱盤啦聯(lián)魔幽撮禽粟咨阿匪丙逞駁路宿茶繭集孰火柵疇聞矛滴眶俯潦戴苯溶趟田緊堿隙涂摹踴吾湯床喊頻抉辯錫辜杰櫥操芯稅扼僑祁讀嗆叛吩滑潘膝絡(luò)車矢革痊碾貓班聲壞喬傈晤烈聲猜呸倘下尉煽退捂矮瀑米噸婁將埋朽豐舶吼孔踴俘嗆他福鋅駐攣跟份赤怎您丹鐳鹵望檀勘妝灸由參攤剛志舒某炯冪遞欺棲恰脊常幀恒賢癬裹酗莎凝亂血肆卞瀉胰逾邀饅捷碼栗撂勘袖著促澎俐杰衷友壬叢雕俱畜倪帶識鎮(zhèn)元惶技丹磐傾鎖增虎金秉交嵌丑訟將 a 基礎(chǔ)理論 b 應(yīng)用研究 c 調(diào)查報告 d 其他本科生畢業(yè)設(shè)計（論

4、文）基于機(jī)器學(xué)習(xí)的英漢字典模糊查詢二級學(xué)院：信息科學(xué)與技術(shù)學(xué)院專 業(yè)：計算機(jī)科學(xué)與技術(shù)年 級：2010級學(xué) 號：2010344369作者姓名：蘇家輝指導(dǎo)教師：蔡廣基 副教授完成日期：2014年5月24日基于機(jī)器學(xué)習(xí)的英漢字典模糊查詢專業(yè)名稱：計算機(jī)科學(xué)與技術(shù)作者姓名：蘇家輝指導(dǎo)教師：蔡廣基論文答辯小組組 長： 蔡廣基 成 員： 王曉曄 關(guān) 心 論文成績： 目 錄1引言21.1研究背景及其意義21.2研究內(nèi)容和目標(biāo)22研究與實現(xiàn)中的關(guān)鍵技術(shù)22.1機(jī)器學(xué)習(xí)的基本原理22.2有趣模式的提取22.3有趣模式集的優(yōu)化32.4使用動態(tài)規(guī)劃的最長公共子序列33系統(tǒng)設(shè)計43.1總體結(jié)構(gòu)43.2 業(yè)務(wù)流程設(shè)計

5、43.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計53.3.1 宏定義53.3.2 結(jié)構(gòu)體53.3.3 文件64實施應(yīng)用64.1 開發(fā)環(huán)境64.1.1 硬件平臺64.1.2 軟件平臺64.2 開發(fā)環(huán)境的搭建和配置64.3 編寫代碼74.3.1最長公共子序列長度核心代碼74.3.2機(jī)器學(xué)習(xí)模型的c語言實現(xiàn)85測試與分析145.1 精確查詢的實現(xiàn)145.2 一般模糊查詢的實現(xiàn)155.3 基于動態(tài)規(guī)劃的模糊查詢實現(xiàn)165.4 機(jī)器學(xué)習(xí)模型對于lcs模糊查詢的優(yōu)化165.5 機(jī)器學(xué)習(xí)模型的自動優(yōu)化176結(jié)論19參考文獻(xiàn)19致謝19基于機(jī)器學(xué)習(xí)的英漢字典模糊查詢作者 蘇家輝 指導(dǎo)教師 蔡廣基副教授 （湛江師范學(xué)院信息科學(xué)與技術(shù)學(xué)院

6、，湛江 524048）摘 要：本文研究機(jī)器學(xué)習(xí)的基本原理和實現(xiàn)方法，對一個使用動態(tài)規(guī)劃實現(xiàn)的英漢字典模糊查詢系統(tǒng)構(gòu)建一個機(jī)器學(xué)習(xí)模型。該模型實現(xiàn)了對用戶的檢索習(xí)慣進(jìn)行分析，提取用戶檢索數(shù)據(jù)中的有趣模式，并通過統(tǒng)計頻度對模式集進(jìn)行自動優(yōu)化，為用戶的模糊查詢提供智能化的查詢結(jié)果。關(guān)鍵詞：機(jī)器學(xué)習(xí)模型，動態(tài)規(guī)劃，模糊查詢 fuzzy query of an english-chinese dictionary based on machine learningsu jiahuischool of information science and technology, zhanjiang normal

7、 university, zhanjiang, 524048 chinaabstract： based on the machine learning theory , a model of the fuzzy query of an english-chinese dictionary system, which is fulfilled by the dynamic programming algorithm is given. the model analyses the users fuzzy query data and finds out the connections betwe

8、en 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 frequencies of user, providing intelligent solutions for the fuzzy query.key words: machine learning; dynamic

9、 programming algorithm; fuzzy query;1引言1.1研究背景及其意義機(jī)器學(xué)習(xí)是現(xiàn)代人工智能研究、發(fā)展的重要領(lǐng)域，它通過研究計算機(jī)如何模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)行為，通過分析、歸納、綜合建立人類學(xué)習(xí)過程的計算模型或認(rèn)識模型，基于已有數(shù)據(jù)識別復(fù)雜模式，做出智能化的決策，并將其應(yīng)用于實際問題中，為解決問題提供可行決策和方案支持1。自1980年在卡內(nèi)基梅隆大學(xué)召開第一屆機(jī)器學(xué)習(xí)研討會以來，機(jī)器學(xué)習(xí)的研究工作發(fā)展迅猛，已成為人工智能領(lǐng)域研究的中心課題之一。隨著機(jī)器學(xué)習(xí)的蓬勃發(fā)展，人們在工作中累積了大量可供測試算法的數(shù)據(jù)集或者超大數(shù)據(jù)集，機(jī)器學(xué)習(xí)工作者在此基礎(chǔ)上可以進(jìn)行更精準(zhǔn)的研

10、究。目前機(jī)器學(xué)習(xí)已經(jīng)廣泛應(yīng)用于智能搜索、數(shù)據(jù)分析等領(lǐng)域，如許多大型的搜索引擎網(wǎng)站的智能化的用戶體驗都是基于機(jī)器學(xué)習(xí)等研究成果實現(xiàn)的。在大數(shù)據(jù)時代，機(jī)器學(xué)習(xí)研究將會得到更大的發(fā)展。1.2研究內(nèi)容和目標(biāo)研究機(jī)器學(xué)習(xí)模型的生成過程，構(gòu)建機(jī)器學(xué)習(xí)的模型，將其應(yīng)用到英漢字典模糊查詢中。第2節(jié)介紹機(jī)器學(xué)習(xí)和模糊查詢中的基本思路和實現(xiàn)方法，第3節(jié)具體介紹算法實現(xiàn)的設(shè)計和數(shù)據(jù)的處理，第4節(jié)編碼實現(xiàn)構(gòu)想，第5節(jié)通過一些測試用例驗證、完善算法的基本功能，最后一節(jié)對本研究做出總結(jié)并提出新展望。2研究與實現(xiàn)中的關(guān)鍵技術(shù)2.1機(jī)器學(xué)習(xí)的基本原理 機(jī)器學(xué)習(xí)是從已有或動態(tài)的數(shù)據(jù)中提取有用的新知識2，并將其應(yīng)用到問題的決策中

11、，其基本過程為： 1. 收集學(xué)習(xí)材料，即獲取的數(shù)據(jù)； 2. 分析數(shù)據(jù)，從中提取有趣的模式； 3. 基于數(shù)據(jù)分析獲取有趣的模式，生成知識庫，制定決策； 4. 通過學(xué)習(xí)新知識檢驗知識庫數(shù)據(jù)的有效性，修改、完善知識庫。在步驟1中獲取的知識是原始的數(shù)據(jù)或材料，他們看起來可能是雜亂無章的，因此在步驟2需要對數(shù)據(jù)進(jìn)行分析，挖掘復(fù)雜的隱藏的模式，使用樸素的貝葉斯分類、噪聲處理等方法對數(shù)據(jù)進(jìn)行分離、提取，然后在將來的決策（步驟3）中使用這些模式去提供方案。但是提取出來的模式也可能是無效的，這就需要步驟4不斷地學(xué)習(xí)新的知識，判定模式是否有效，修改完善知識庫。2.2有趣模式的提取如何從原始數(shù)據(jù)中提取有用的模式，挖

12、掘那些隱藏的有趣知識？分類是數(shù)據(jù)分析的一種重要的形式，通過它可以提取重要的數(shù)據(jù)類型。分類首先要基于現(xiàn)有數(shù)據(jù)建立一個分類模型，然后根據(jù)模型對數(shù)據(jù)進(jìn)行分類。分類模型有決策樹分類器、貝葉斯分類器和基于規(guī)則的分類器等3。在英漢字典模糊查詢系統(tǒng)，使用的是基于規(guī)則的分類器-形如if-then的分類器。規(guī)則的if部分是前提條件，then部分是結(jié)論。假如用戶的某些輸入滿足特定的條件則可認(rèn)為是有趣模式。一般情況下，如果用戶本次輸入的數(shù)據(jù)在上一次模糊查詢的結(jié)果集中，則可認(rèn)為上一次為用戶提供的結(jié)果集中的對應(yīng)項是有趣的。如果不滿足這一條件則可認(rèn)為上一次的模糊結(jié)果集對用戶沒有幫助，即為無效數(shù)據(jù)，丟棄之。英漢字典模糊查詢

13、系統(tǒng)的規(guī)則分類器實現(xiàn)大體如下： 本次是否為精確查詢？ yes no 上一次是否有模糊結(jié)果集？ 非有趣模式 yes no 本次輸入在上一次模糊結(jié)果集中？ 非有趣模式 yes no 有趣模式 非有趣模式 圖2.1規(guī)則分類器的實現(xiàn) 2.3有趣模式集的優(yōu)化 有趣模式集中的記錄都是用戶感興趣的，但是對于一個非精確的輸入可能存在多個用戶感興趣的選擇項，如何確定最優(yōu)的選擇項呢？在統(tǒng)計學(xué)上，使用概率表示一件事情在大量測試下發(fā)生的可能性4。假設(shè)a代表用戶的一個模糊輸入，x1，xi代表a輸入所對應(yīng)的用戶感興趣的選擇項，設(shè)p(a|xi)為用戶輸入a后選擇xi的概率，分別計每一個選擇項xi的p(a|xi),將具有最大

14、值的選擇項排在最前面，即為最優(yōu)的選擇項。用戶每次輸入a后選擇xi都是對axi模式的一次強(qiáng)化。p(a|xi)=n(xi)/n(a),在該式中n(xi)表示xi被選擇的次數(shù)，n(a)表示輸入a的總次數(shù)，對于計算a的所有選擇項的p(a|xi)，分母都是相同的，因此在具體的實現(xiàn)中，只需要為每一個選擇項項添加一個頻度計數(shù)，這樣具有最大頻度計數(shù)的選擇項即為最優(yōu)的選擇項。2.4使用動態(tài)規(guī)劃的最長公共子序列動態(tài)規(guī)劃5采用自底向上的遞推求值，把中間的結(jié)果存儲起來并用于后面的計算，對于改善蠻力搜索的時間復(fù)雜度是比較有效的，假設(shè)an，bm分別表示長度為n,m的兩個字符串，則a0,an-1中的任意組合表示a的子序列，

15、b0bm-1中的任意組合表示b的子序列,如果要求這兩個字符串的最長公共子序列，采用簡單的線性規(guī)劃的方法是：列舉a的所有所有2的n次方個子序列，察看它與bm的最長公共子序列長度，采用這種方法的時間復(fù)雜度是指數(shù)級的(n2)，如果采用動態(tài)規(guī)劃的方法可以使解決最初公共子序列問題優(yōu)化到（n log n）。假設(shè)lnm表示a的前n個字符與b的前m個字符之間的最長公共子序列長度，則lnm的遞推公式如下：lcsflag初始值為0，用于標(biāo)記當(dāng)n或m為0時，前面是否有a的子序列與b的子序列相等的情況。對于n=0或m=0,若an=am,則lnm=lcsflag=1,如果an!=am,若lcsflag=1則，lnm=1

16、，否則lnm=0； 對于n和m都不等于0的情況：若an=bm則lnm= ln-1m-1+1；若an!=bm則lnm= ln-1m和lnm-1中的最大值。3系統(tǒng)設(shè)計3.1總體結(jié)構(gòu) 系統(tǒng)的主要功能包括以下部分 1. 用戶輸入 接收用戶輸入的單詞或詞組，它們可能是精確的輸入，也可能是存在拼寫錯誤的單詞或詞組，如“department”和“deparmen”等。 2. 精確查詢 在字典的索引文件中查找查看是否存在，如果存在，則去詞庫的譯義文件中讀取，并將結(jié)果輸出給用戶。 3. 一般模糊查詢 如果通過精確查找無法查出該單詞/詞組，這種可能是由于單詞的單復(fù)數(shù)，動詞過去式，現(xiàn)在分詞的ing形式類等造成，因此

17、一般模糊查詢就是對以上形式的單詞進(jìn)行簡單的處理，如去掉詞尾的s、d等，然后再對處理之后的單詞進(jìn)行精確查詢。 4. 基于最長公共子序列的模糊查詢（以下簡稱lcs查詢） 如果基于一般模糊查詢?nèi)詿o法查出，則使用lcs查詢，該查詢是基于全文的檢索，找出與輸入單詞最為相近的單詞，即與輸入單詞的最長公共子序列是在全文中的最大值的單詞，并將其作為選擇項輸出給用戶。 5. 機(jī)器學(xué)習(xí)的模塊開始時候，用戶的使用記錄為空。在一次lcs查詢之后，可以將lcs模糊查詢的結(jié)果集記錄起來，如果用戶下一次查詢的輸入與lcs模糊查詢的結(jié)果集記錄有匹配項，則認(rèn)為它們是一個有趣模式，并把其加入到有趣模式集中。每一次模糊查詢給用戶輸

18、出的結(jié)果集都會與模式結(jié)果集中的結(jié)果進(jìn)行匹配，如果找到，則把模式結(jié)果集中的匹配數(shù)據(jù)與模糊結(jié)果集，匹配數(shù)據(jù)優(yōu)先放到結(jié)果集前，去除重復(fù)的項，生成最終結(jié)果集（決策），最后輸出給用戶。3.2 業(yè)務(wù)流程設(shè)計系統(tǒng)的業(yè)務(wù)流程如下： 圖3.1業(yè)務(wù)流程圖 是 3.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計 3.3.1 宏定義宏定義含義#define wordcount 59372詞庫中單詞的個數(shù)#define wordlen 24單詞的最大長度#define error(msg) perror(msg); exit(1);出錯處理#define prenum 5對于每個用戶輸入可以提取的有效模式的最大個數(shù)3.3.2 結(jié)構(gòu)體 1. 單詞索引

19、記錄 typedef struct char wordwordlen; int offset; int length; node;其中word表示單詞，offset是該單詞在詞庫文件中的索引，length是該單詞的釋義的長度 2. 用戶的偏好記錄typedef structchar wordwordlen;int count;preference;其中word表示用戶偏好的單詞，count是該單詞的的支持度計數(shù)，即在用戶的輸入中該單詞被選中的頻數(shù)。 3. 模式記錄集typedef structchar inputwordlen;/用戶輸入的單詞preference presmaxpres;/最

20、多記錄5個偏好record;其中input是用戶的非精確單詞，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)的lcs模糊查詢結(jié)果集4. 模式記錄文件record.dat存放的是有趣模式記錄，這些記錄也是按用戶的輸入非精確單詞升序排序，這樣方便在進(jìn)行記錄查找時使用二

21、分查找，快速的查詢某一記錄是否存在，在記錄的內(nèi)部是按照模式的有效次數(shù)降序按序的。 4實施應(yīng)用4.1 開發(fā)環(huán)境4.1.1 硬件平臺 cpu：i5-4200h 2.8ghz； 內(nèi)存：256mb及以上。4.1.2 軟件平臺 操作系統(tǒng)：windows虛擬機(jī)vmware 10.0下的ubuntu linux。 開發(fā)工具：gcc ,vim4.2 開發(fā)環(huán)境的搭建和配置1 安裝vim 在linux終端輸入 sudo apt-get install vim-gtk，然后輸入root用戶密碼等待完成vim工具的安裝2 vim的基本配置 在linux終端輸入vi /.vimrc按如下方式配置set nus

22、et ts=4set sw=4set cindentset autoident3環(huán)境變量的設(shè)置在終端輸入 vi /.bashrc添加以下行：export path="$path:./ "保存之后在命令行輸入source .bashrc 4.3 編寫代碼4.3.1最長公共子序列長度核心代碼int lcs(char* a,char* b) int n,m,i,j; int flag=0; n=strlen(a)-1; m=strlen(b)-1; int l100100=0; for(i=0;i<=n;i+) if(flag|(ai=b0) li0=1; flag=1;

23、else li0=0; flag=0; for(j=0;j<=m;j+) if(flag|(a0=bj) l0j=1; flag=1; else l0j=0; /char a100,b100;for(i=1;i<=n;i+) for(j=1;j<=m;j+) if (ai=bj) lij=li-1j-1+1; else if (lij-1>=li-1j) lij=lij-1; else lij=li-1j;return lnm;4.3.2機(jī)器學(xué)習(xí)模型的c語言實現(xiàn) 1.在learn.h中的定義#ifndef _learn_h#define _learn_h#include

24、 "dict.h"#include <stdlib.h>#include <string.h>#include <stdio.h>#define maxpres 5/用戶偏好的最大個數(shù)#define wordlen 24/單詞最大長度#define prenum 5 /有效模式的個數(shù)typedef structchar wordwordlen;/用戶偏好int count;/次數(shù)preference;typedef structchar inputwordlen;/用戶選擇項preference presmaxpres;/最多記錄5個偏好

25、record;/int recordsize=sizeof(record);/一個記錄的大小void recorddata(char* word,node* nodes);void newrecord(char* word,char* match_word);void analyse(char* word);void solution(char* newdata,node* nodes);void decision(node* dst_node,node* src_node);/用于快速查找查詢記錄或?qū)τ涗浛炫舏nt recordcmp(const void * dst,const void

26、* src);int prescmp(const void * dst,const void * src);#endif 主要函數(shù)解釋： recorddata：用于記錄用戶每次輸入的非精確單詞及其使用lcs模糊查詢得到的結(jié)果集。 analyse：分析用戶的輸入和lcs模糊結(jié)果集間的關(guān)系，提取有趣模式。 newrecord:記錄有趣模式。 solution：提取與用戶輸入的非精確單詞相關(guān)的模式記錄。 decision：根據(jù)歷史模式記錄，生成最終的決策方案。 2. 在learn.c中主要函數(shù)的實現(xiàn) void recorddata(char* word,node* nodes)/word 代表用戶的

27、輸入，nodes是模糊查詢的結(jié)果集file* fd=fopen("./search.dat","w+b");/打開并清空上一次的結(jié)果if(!fd)return;int node_len=0;int len=strlen(word);fwrite(&len,sizeof(int),1,fd);fwrite(word,1,len,fd); while(strlen(nodesnode_len.word)>0)node_len+;fwrite(&node_len,sizeof(int),1,fd);fwrite(nodes,sizeof(

28、node),node_len,fd);fclose(fd);int recordcmp(const void * dst,const void * src)record* d=(record*)dst;record* s=(record*)src;return strcmp(d->input,s->input);/對用戶偏好按降序排序int prescmp(const void * dst,const void * src)preference* d=(preference*)dst;preference* s=(preference*)src;return (d->coun

29、t) < (s->count);void newrecord(char* word,char* match_word) file* fd=fopen("./record.dat","a+b");if(!fd)return; int recordcount=0; record* matched=null; char ch; fseek(fd,0,seek_set); fread(&ch,1,1,fd); if(ch=eof)/即初始狀態(tài)，空文件 recordcount=1; fseek(fd,0,seek_set); fwrite(&a

30、mp;recordcount,sizeof(int),1,fd); record newrcd=0; strcpy(newrcd.input,word); strcpy(newrcd.pres0.word,match_word); newrcd.pres0.count=1; fwrite(&newrcd,sizeof(record),1,fd); /check the first record fclose(fd); return; else fseek(fd,0,seek_set); fread(&recordcount,sizeof(int),1,fd); record*

31、records=(record*)malloc(recordcount+1)*recordsize); fread(records,recordsize,recordcount,fd); fclose(fd); /a+模式從文件頭讀，從文件尾寫 matched=(record*)bsearch(word,records,recordcount,recordsize,recordcmp); /是已有記錄 if(matched!=null) int num=0,i;/用于標(biāo)識是否找到while(strlen(matched->presnum.word)>0)num+;/計算當(dāng)前用戶偏好

32、的數(shù)目 for(i=0;i<num;i+) if(!strcmp(match_word,matched->presi.word) matched->presi.count+;qsort(matched->pres,num,sizeof(preference),prescmp);break; if(!(i<num)/匹配項不在偏好數(shù)組中 preference newpre=0; strcpy(newpre.word,match_word); newpre.count=1; if(i<maxpres) matched->presi=newpre; else

33、 matched->presi-1=newpre; /新記錄 else recordcount+; record newrcd=0; strcpy(newrcd.input,word); strcpy(newrcd.pres0.word,match_word); newrcd.pres0.count=1; recordsrecordcount-1=newrcd; /對record數(shù)組重新排序 qsort(records,recordcount,sizeof(record),recordcmp); /寫回記錄文件 file* fw=fopen("./record.dat"

34、;,"r+b"); fseek(fw,0,seek_set); fwrite(&recordcount,sizeof(int),1,fw); fwrite(records,sizeof(record),recordcount,fw); free(records); fclose(fw); void analyse(char* match_word) file* fd=fopen("./search.dat","rb");if(!fd)return; int len=0; fread(&len,sizeof(int),1

35、,fd); char wordlen+1; fread(word,1,len,fd); wordlen='0' /printf("value in analyse:%sn,%d",word,len); int node_len=0; fread(&node_len,sizeof(int),1,fd); node nodesnode_len; fread(nodes,sizeof(node),node_len,fd); fclose(fd); int i=0; /判斷是否為有趣模式 for(i=0;i<node_len;i+) if(!strcm

36、p(nodesi.word,match_word) newrecord(word,match_word); break; void solution(char* newdata,node* nodes) file* fd=fopen("./record.dat","rb");if(!fd)return; int recordcount=0; char ch; fseek(fd,0,seek_set); fread(&ch,1,1,fd); if(ch=eof) fclose(fd); return; fseek(fd,0,seek_set); f

37、read(&recordcount,sizeof(int),1,fd); record* records=(record*)malloc(recordcount*recordsize); fread(records,recordsize,recordcount,fd); fclose(fd); record* matched=(record*)bsearch(newdata,records,recordcount,recordsize,recordcmp); if(!matched) /無歷史記錄 free(records); /printf("solution called

38、 ailuesn"); return; /讀出有效模式，最多5個 int num=0; while(strlen(matched->presnum.word) /printf("pres value:%sn",matched->presnum.word); num+; /printf("匹配記錄中的pres:%dn",num); if(num > prenum) num=prenum; int i; for(i=0;i<num;i+) strcpy(nodesi.word,matched->presi.word);

39、 free(records);/計算結(jié)點數(shù)目int nodenum(node* nodes)int i=0; while(strlen(nodesi.word) i+; return i;/結(jié)點數(shù)組拷貝void nodecpy(node* dst_node,node* src_node)int src_count=nodenum(src_node);int i=0;for(i=0;i<src_count;i+) strcpy(dst_nodei.word,src_nodei.word); /結(jié)點查找int findnode(char* word,node* nodes,int num)i

40、nt i=0;for(i=0;i<num;i+)if(!strcasecmp(word,nodesi.word)/找到return 1;return 0;/src_node: nodes from record file,des_node: final nodes array to dual searchvoid decision(node* dst_node,node* src_node)/src_node表示從歷史數(shù)據(jù)中獲取的數(shù)據(jù)，des_node本次模糊匹配結(jié)果int src_count=nodenum(src_node); int dst_count=nodenum(dst_no

41、de);node tempdst_count;node nilnode=0;/用于結(jié)點初始化nodecpy(temp,dst_node);node newnodessrc_count+dst_count;/合并int j=0;for(j=0;j<(src_count+dst_count);j+)newnodesj=nilnode;/nodecpy(newnodes,src_node);int newcount=nodenum(newnodes);int i=0;for(i=0;i<dst_count;i+) if(!findnode(tempi.word,src_node,src_

42、count) newnodesnewcount=tempi; newcount+; nodecpy(dst_node,newnodes);5測試與分析在編寫好所有的代碼之后，在終端輸入命令gcc *.c 即可編譯生成可執(zhí)行文件，然后在終端輸入./a.out按以下用例測試。5.1 精確查詢的實現(xiàn) 測試用例1：word:mopmopn. 拖把,鬼臉亂蓬蓬的頭發(fā)vt. 用拖把洗擦,擦,拭vi. 做鬼臉測試結(jié)果分析：用戶輸入“mop”進(jìn)行搜索，該單詞在索引文件中找到，則從詞庫中讀取其釋義并輸出。 測試用例2：word:youyoupron. 你,你們;一個人,任何人測試結(jié)果分析：用戶輸入“you”進(jìn)行

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

44、可進(jìn)行一般的處理，去掉詞尾的“d”,再進(jìn)行精確查詢，可輸出“move”對應(yīng)的英譯漢釋義。 測試用例5：word:jumppingjumpn. 跳躍,跳動,上漲,驚跳vt. 跳越,躍過,突升,使跳躍vi. 跳躍,跳,跳動,暴漲測試結(jié)果分析：用戶輸入的是“jumpping”,這個單詞也無法使用精確查詢，該單詞為ing形式，可以先去掉詞尾的“ing”查看是否可以找不到，若找不到再嘗試由于元音+輔音結(jié)尾的形如mop-mopping形式的規(guī)則，再去掉詞尾的一個字符，再次進(jìn)行精確查找，輸出單詞“jump”的釋義。 測試用例6：word:flowersflowern. 花,精華,盛時vi. 開花,旺盛,成熟

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

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

47、ted departure apartment deportment4. word:deportmentdeportmentn. 行為,舉止5. word:departmen您是否要搜索： department deportment departed departure apartment 測試結(jié)果分析： 步驟1開始時不存在模式文件，輸入“departmen”查找，會進(jìn)入到lcs查找，得出來的模糊結(jié)果集是：departed,departure,apartment,department,deportment,不夠精確。 步驟2用戶根據(jù)提示輸入了“department”得到釋義，并且“depart

48、ment”在上一次lcs查找的模糊結(jié)果集中，因此“departmen”和“department”將會作為一個有趣模式被提取出來并記錄到模式文件中。 步驟3再次輸入“departmen”查詢，這時已存在記錄“department”，會優(yōu)先輸出“department”，得到優(yōu)化的模糊結(jié)果集： department，departed,departure,apartment,deportment。 步驟4接著用戶選擇輸了“deportment”，它也在上一次lcs模糊集，所以“departmen”和“deportment”也會作為一個有趣模式被提取和保存。 步驟5再次輸入“departmen”查詢，模

49、式記錄中已有“department”和“deportment”，最終得到的優(yōu)化模糊結(jié)果集為：department，deportment，departed,departure,apartment；5.5 機(jī)器學(xué)習(xí)模型的自動優(yōu)化 測試用例9：（以下測試步驟也是緊密關(guān)聯(lián)的。）1. word:pople您是否要搜索： pope prole apple popple people2. word:peoplepeoplen. 人,人們,民族,人類,公民vt. 使住滿人3. word:pople您是否要搜索： people pope prole apple popple4.word:popplepopplevi. 波動,蕩漾,洶涌n. 波動,漣漪,洶涌5. word:pople您是否要搜索： people popple pope prole apple6. word:popplepopplevi. 波動,蕩漾,洶涌n. 波動,漣漪,洶涌7 . word:pople您是否要搜索： popple people pope prole apple 測試結(jié)果分析： 步驟1和2是對模式記錄“pople”-“people”的提取，步驟3和4是對模式記錄“pople”-“popple”的提取，步驟5、6則是對“pople”-“popple”記錄的進(jìn)一