基于機器學習的英漢字典模糊查詢畢業(yè)論文

1、 . . . A 基礎理論 B 應用研究 C 調(diào)查報告 D 其他本科生畢業(yè)設計（論文）基于機器學習的英漢字典模糊查詢目 錄1引言21.1研究背景與其意義21.2研究容和目標22研究與實現(xiàn)中的關鍵技術22.1機器學習的基本原理22.2有趣模式的提取22.3有趣模式集的優(yōu)化32.4使用動態(tài)規(guī)劃的最長公共子序列33系統(tǒng)設計43.1總體結構43.2 業(yè)務流程設計43.3 數(shù)據(jù)結構設計53.3.1 宏定義53.3.2 結構體53.3.3 文件64實施應用64.1 開發(fā)環(huán)境64.1.1 硬件平臺64.1.2 軟件平臺64.2 開發(fā)環(huán)境的搭建和配置64.3 編寫代碼74.3.1最長公共子序列長度核心代碼74

2、.3.2機器學習模型的c語言實現(xiàn)85測試與分析145.1 精確查詢的實現(xiàn)145.2 一般模糊查詢的實現(xiàn)155.3 基于動態(tài)規(guī)劃的模糊查詢實現(xiàn)165.4 機器學習模型對于LCS模糊查詢的優(yōu)化165.5 機器學習模型的自動優(yōu)化176結論19參考文獻19致1922 / 24基于機器學習的英漢字典模糊查詢作者 家輝 指導教師 蔡廣基副教授 （師學院信息科學與技術學院， 524048）摘 要：本文研究機器學習的基本原理和實現(xiàn)方法，對一個使用動態(tài)規(guī)劃實現(xiàn)的英漢字典模糊查詢系統(tǒng)構建一個機器學習模型。該模型實現(xiàn)了對用戶的檢索習慣進行分析，提取用戶檢索數(shù)據(jù)中的有趣模式，并通過統(tǒng)計頻度對模式集進行自動優(yōu)化，為用戶

3、的模糊查詢提供智能化的查詢結果。關鍵詞：機器學習模型，動態(tài)規(guī)劃，模糊查詢Fuzzy query of an English-Chinese dictionary based on machine learningSu JiahuiSchool of information science and technology, ZhanjiangNormalUniversity, Zhanjiang,524048 ChinaAbstract：Based on the machine learningtheory , a model of the fuzzy query of an English-Ch

4、inese 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 between the data, recording the mining models, applies them to the fuzzy query set during anon-accurate searching, and automatically

5、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 programming algorithm; fuzzy query;1引言1.1研究背景與其意義機器學習是現(xiàn)代人工智能研究、發(fā)展的重要領域，它通過研究計算機如何模擬或實現(xiàn)人類的學習行為，通過分析、歸納、綜合建立人類學習過程的計算模型或認識模型，基于已有數(shù)據(jù)

6、識別復雜模式，做出智能化的決策，并將其應用于實際問題中，為解決問題提供可行決策和方案支持1。自1980年在卡基梅隆大學召開第一屆機器學習研討會以來，機器學習的研究工作發(fā)展迅猛，已成為人工智能領域研究的中心課題之一。隨著機器學習的蓬勃發(fā)展，人們在工作中累積了大量可供測試算法的數(shù)據(jù)集或者超大數(shù)據(jù)集，機器學習工作者在此基礎上可以進行更精準的研究。目前機器學習已經(jīng)廣泛應用于智能搜索、數(shù)據(jù)分析等領域，如許多大型的搜索引擎的智能化的用戶體驗都是基于機器學習等研究成果實現(xiàn)的。在大數(shù)據(jù)時代，機器學習研究將會得到更大的發(fā)展。1.2研究容和目標研究機器學習模型的生成過程，構建機器學習的模型，將其應用到英漢字典模糊

7、查詢中。第2節(jié)介紹機器學習和模糊查詢中的基本思路和實現(xiàn)方法，第3節(jié)具體介紹算法實現(xiàn)的設計和數(shù)據(jù)的處理，第4節(jié)編碼實現(xiàn)構想，第5節(jié)通過一些測試用例驗證、完善算法的基本功能，最后一節(jié)對本研究做出總結并提出新展望。2研究與實現(xiàn)中的關鍵技術2.1機器學習的基本原理 機器學習是從已有或動態(tài)的數(shù)據(jù)中提取有用的新知識2，并將其應用到問題的決策中，其基本過程為： 1. 收集學習材料，即獲取的數(shù)據(jù)； 2. 分析數(shù)據(jù)，從中提取有趣的模式； 3. 基于數(shù)據(jù)分析獲取有趣的模式，生成知識庫，制定決策； 4. 通過學習新知識檢驗知識庫數(shù)據(jù)的有效性，修改、完善知識庫。在步驟1中獲取的知識是原始的數(shù)據(jù)或材料，他們看起來可能是

8、雜亂無章的，因此在步驟2需要對數(shù)據(jù)進行分析，挖掘復雜的隱藏的模式，使用樸素的貝葉斯分類、噪聲處理等方法對數(shù)據(jù)進行分離、提取，然后在將來的決策（步驟3）中使用這些模式去提供方案。但是提取出來的模式也可能是無效的，這就需要步驟4不斷地學習新的知識，判定模式是否有效，修改完善知識庫。2.2有趣模式的提取如何從原始數(shù)據(jù)中提取有用的模式，挖掘那些隱藏的有趣知識？分類是數(shù)據(jù)分析的一種重要的形式，通過它可以提取重要的數(shù)據(jù)類型。分類首先要基于現(xiàn)有數(shù)據(jù)建立一個分類模型，然后根據(jù)模型對數(shù)據(jù)進行分類。分類模型有決策樹分類器、貝葉斯分類器和基于規(guī)則的分類器等3。在英漢字典模糊查詢系統(tǒng)，使用的是基于規(guī)則的分類器-形如I

9、F-THEN的分類器。規(guī)則的IF部分是前提條件，THEN部分是結論。假如用戶的某些輸入滿足特定的條件則可認為是有趣模式。一般情況下，如果用戶本次輸入的數(shù)據(jù)在上一次模糊查詢的結果集中，則可認為上一次為用戶提供的結果集中的對應項是有趣的。如果不滿足這一條件則可認為上一次的模糊結果集對用戶沒有幫助，即為無效數(shù)據(jù)，丟棄之。英漢字典模糊查詢系統(tǒng)的規(guī)則分類器實現(xiàn)大體如下：本次是否為精確查詢？YESNO上一次是否有模糊結果集？非有趣模式YESNO本次輸入在上一次模糊結果集中？非有趣模式YES NO 有趣模式 非有趣模式 圖2.1規(guī)則分類器的實現(xiàn)2.3有趣模式集的優(yōu)化有趣模式集中的記錄都是用戶感興趣的，但是對

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

11、項項添加一個頻度計數(shù)，這樣具有最大頻度計數(shù)的選擇項即為最優(yōu)的選擇項。2.4使用動態(tài)規(guī)劃的最長公共子序列動態(tài)規(guī)劃5采用自底向上的遞推求值，把中間的結果存儲起來并用于后面的計算，對于改善蠻力搜索的時間復雜度是比較有效的，假設an，bm分別表示長度為n,m的兩個字符串，則a0,an-1中的任意組合表示a的子序列，b0bm-1中的任意組合表示b的子序列,如果要求這兩個字符串的最長公共子序列，采用簡單的線性規(guī)劃的方法是：列舉a的所有所有2的n次方個子序列，察看它與bm的最長公共子序列長度，采用這種方法的時間復雜度是指數(shù)級的(n2)，如果采用動態(tài)規(guī)劃的方法可以使解決最初公共子序列問題優(yōu)化到（n log n

12、）。假設Lnm表示a的前n個字符與b的前m個字符之間的最長公共子序列長度，則Lnm的遞推公式如下：LCSflag初始值為0，用于標記當n或m為0時，前面是否有a的子序列與b的子序列相等的情況。對于n=0或m=0,若an=am,則Lnm=LCSflag=1,如果an!=am,若LCSflag=1則，Lnm=1，否則Lnm=0； 對于n和m都不等于0的情況：若an=bm則Lnm= Ln-1m-1+1；若an!=bm則Lnm= Ln-1m和Lnm-1中的最大值。3系統(tǒng)設計3.1總體結構 系統(tǒng)的主要功能包括以下部分 1. 用戶輸入 接收用戶輸入的單詞或詞組，它們可能是精確的輸入，也可能是存在拼寫錯誤的

13、單詞或詞組，如“department”和“deparmen”等。 2. 精確查詢 在字典的索引文件中查找查看是否存在，如果存在，則去詞庫的譯義文件中讀取，并將結果輸出給用戶。 3. 一般模糊查詢 如果通過精確查找無法查出該單詞/詞組，這種可能是由于單詞的單復數(shù)，動詞過去式，現(xiàn)在分詞的ing形式類等造成，因此一般模糊查詢就是對以上形式的單詞進行簡單的處理，如去掉詞尾的s、d等，然后再對處理之后的單詞進行精確查詢。 4. 基于最長公共子序列的模糊查詢（以下簡稱lcs查詢） 如果基于一般模糊查詢?nèi)詿o法查出，則使用lcs查詢，該查詢是基于全文的檢索，找出與輸入單詞最為相近的單詞，即與輸入單詞的最長公共

14、子序列是在全文中的最大值的單詞，并將其作為選擇項輸出給用戶。 5. 機器學習的模塊開始時候，用戶的使用記錄為空。在一次lcs查詢之后，可以將lcs模糊查詢的結果集記錄起來，如果用戶下一次查詢的輸入與lcs模糊查詢的結果集記錄有匹配項，則認為它們是一個有趣模式，并把其加入到有趣模式集中。每一次模糊查詢給用戶輸出的結果集都會與模式結果集中的結果進行匹配，如果找到，則把模式結果集中的匹配數(shù)據(jù)與模糊結果集，匹配數(shù)據(jù)優(yōu)先放到結果集前，去除重復的項，生成最終結果集（決策），最后輸出給用戶。3.2 業(yè)務流程設計系統(tǒng)的業(yè)務流程如下： 圖3.1業(yè)務流程圖 是 3.3 數(shù)據(jù)結構設計3.3.1 宏定義宏定義含義#d

15、efine WORDCOUNT 59372詞庫中單詞的個數(shù)#define WORDLEN 24單詞的最大長度#define Error(msg) perror(msg); eXit(1);出錯處理#define PRENUM 5對于每個用戶輸入可以提取的有效模式的最大個數(shù)3.3.2 結構體 1. 單詞索引記錄typedef struct char wordWORDLEN; int offset; int length; Node;其中word表示單詞，offset是該單詞在詞庫文件中的索引，length是該單詞的釋義的長度 2. 用戶的偏好記錄typedef structchar wordWO

16、RDLEN;int count;Preference;其中word表示用戶偏好的單詞，count是該單詞的的支持度計數(shù)，即在用戶的輸入中該單詞被選中的頻數(shù)。 3. 模式記錄集typedef structchar inputWORDLEN;/用戶輸入的單詞Preference presMAXPRES;/最多記錄5個偏好Record;其中input是用戶的非精確單詞，pres是該單詞對應的用戶偏好單詞數(shù)組，最多5個記錄。3.3.3 文件1. 單詞的索引文件star.ndx 存放的是一個個Node類型的數(shù)據(jù)，每個單詞/詞組都有一個對應的Node，這些數(shù)據(jù)按照單詞的英文次序升序排列，因此在查找單詞時可

17、使用二分查找快速檢索。2. 詞庫文件star.dict存放單詞的釋義3. 用戶輸入記錄文件search.dat存放用戶輸入的非精確單詞，與該單詞對應的lcs模糊查詢結果集4. 模式記錄文件record.dat存放的是有趣模式記錄，這些記錄也是按用戶的輸入非精確單詞升序排序，這樣方便在進行記錄查找時使用二分查找，快速的查詢某一記錄是否存在，在記錄的部是按照模式的有效次數(shù)降序按序的。4實施應用4.1 開發(fā)環(huán)境4.1.1 硬件平臺 CPU：i5-4200h 2.8GHz； 存：256MB與以上。4.1.2 軟件平臺 操作系統(tǒng)：Windows虛擬機VMware 10.0下的ubuntu linux。

18、開發(fā)工具：gcc ,vim4.2 開發(fā)環(huán)境的搭建和配置1 安裝vim 在linux終端輸入 sudo apt-get install vim-gtk，然后輸入root用戶密碼等待完成vim工具的安裝2 vim的基本配置 在linux終端輸入vi /.vimrc按如下方式配置set nuset ts=4set sw=4set cindentset autoident3環(huán)境變量的設置在終端輸入vi /.bashrc添加以下行：export PATH="$PATH:./ "保存之后在命令行輸入source .bashrc 4.3 編寫代碼4.3.1最長公共子序列長度核心

19、代碼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; 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) Li

20、j=Li-1j-1+1; else if (Lij-1>=Li-1j) Lij=Lij-1; else Lij=Li-1j;return Lnm;4.3.2機器學習模型的c語言實現(xiàn) 1.在learn.h中的定義#ifndef _LEARN_H#define _LEARN_H#include "dict.h"#include <stdlib.h>#include <string.h>#include <stdio.h>#define MAXPRES 5/用戶偏好的最大個數(shù)#define WORDLEN 24/單詞最大長度#define

21、 PRENUM 5 /有效模式的個數(shù)typedef structchar wordWORDLEN;/用戶偏好int count;/次數(shù)Preference;typedef structchar inputWORDLEN;/用戶選擇項Preference presMAXPRES;/最多記錄5個偏好Record;/int Recordsize=sizeof(Record);/一個記錄的大小void RecordData(char* word,Node* nodes);void NewRecord(char* word,char* match_word);void Analyse(char* wor

22、d);void Solution(char* newData,Node* nodes);void Decision(Node* dst_node,Node* src_node);/用于快速查找查詢記錄或對記錄快排int Recordcmp(const void * dst,const void * src);int Prescmp(const void * dst,const void * src);#endif 主要函數(shù)解釋： RecordData：用于記錄用戶每次輸入的非精確單詞與其使用lcs模糊查詢得到的結果集。 Analyse：分析用戶的輸入和lcs模糊結果集間的關系，提取有趣模式。

23、NewRecord:記錄有趣模式。 Solution：提取與用戶輸入的非精確單詞相關的模式記錄。 Decision：根據(jù)歷史模式記錄，生成最終的決策方案。 2. 在learn.c中主要函數(shù)的實現(xiàn)void RecordData(char* word,Node* nodes)/word 代表用戶的輸入，nodes是模糊查詢的結果集FILE* fd=fopen("./search.dat","w+b");/打開并清空上一次的結果if(!fd)return;int node_len=0;int len=strlen(word);fwrite(&len,s

24、izeof(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(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-&

25、gt;input);/對用戶偏好按降序排序int Prescmp(const void * dst,const void * src)Preference* d=(Preference*)dst;Preference* s=(Preference*)src;return (d->count) < (s->count);void NewRecord(char* word,char* match_word) FILE* fd=fopen("./record.dat","a+b");if(!fd)return; int RecordCount

26、=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(&RecordCount,sizeof(int),1,fd); Record newRcd=0; strcpy(newRcd.input,word); strcpy(newRcd.pres0.word,match_word); newRcd.pres0.count=1; fwrite(&new

27、Rcd,sizeof(Record),1,fd); /check the first record fclose(fd); return; else fseek(fd,0,SEEK_SET); fread(&RecordCount,sizeof(int),1,fd); Record* records=(Record*)malloc(RecordCount+1)*Recordsize); fread(records,Recordsize,RecordCount,fd); fclose(fd); /a+模式從文件頭讀，從文件尾寫 matched=(Record*)bsearch(word,

28、records,RecordCount,Recordsize,Recordcmp); /是已有記錄 if(matched!=NULL) int num=0,i;/用于標識是否找到while(strlen(matched->presnum.word)>0)num+;/計算當前用戶偏好的數(shù)目 for(i=0;i<num;i+) if(!strcmp(match_word,matched->presi.word) matched->presi.count+;qsort(matched->pres,num,sizeof(Preference),Prescmp);br

29、eak; if(!(i<num)/匹配項不在偏好數(shù)組中 Preference newPre=0; strcpy(newPre.word,match_word); newPre.count=1; if(i<MAXPRES) matched->presi=newPre; else matched->presi-1=newPre; /新記錄 else RecordCount+; Record newRcd=0; strcpy(newRcd.input,word); strcpy(newRcd.pres0.word,match_word); newRcd.pres0.count

30、=1; recordsRecordCount-1=newRcd; /對record數(shù)組重新排序 qsort(records,RecordCount,sizeof(Record),Recordcmp); /寫回記錄文件 FILE* fw=fopen("./record.dat","r+b"); fseek(fw,0,SEEK_SET); fwrite(&RecordCount,sizeof(int),1,fw); fwrite(records,sizeof(Record),RecordCount,fw); free(records); fclose

31、(fw); void Analyse(char* match_word) FILE* fd=fopen("./search.dat","rb");if(!fd)return; int len=0; fread(&len,sizeof(int),1,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_le

32、n,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(!strcmp(nodesi.word,match_word) NewRecord(word,match_word); break; void Solution(char* newData,Node* nodes) FILE* fd=fopen("./record.dat","rb&qu

33、ot;);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); fread(&RecordCount,sizeof(int),1,fd); Record* records=(Record*)malloc(RecordCount*Recordsize); fread(records,Recordsize,RecordCount,fd); fclose(fd); R

34、ecord* matched=(Record*)bsearch(newData,records,RecordCount,Recordsize,Recordcmp); if(!matched) /無歷史記錄 free(records); /printf("Solution called ailuesn"); return; /讀出有效模式，最多5個 int num=0; while(strlen(matched->presnum.word) /printf("pres value:%sn",matched->presnum.word); num

35、+; /printf("匹配記錄中的pres:%dn",num); if(num > PRENUM) num=PRENUM; int i; for(i=0;i<num;i+) strcpy(nodesi.word,matched->presi.word); free(records);/計算結點數(shù)目int Nodenum(Node* nodes)int i=0; while(strlen(nodesi.word) i+; return i;/結點數(shù)組拷貝void Nodecpy(Node* dst_node,Node* src_node)int src_c

36、ount=Nodenum(src_node);int i=0;for(i=0;i<src_count;i+) strcpy(dst_nodei.word,src_nodei.word); /結點查找int FindNode(char* word,Node* nodes,int num)int 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 sea

37、rchvoid Decision(Node* dst_node,Node* src_node)/src_node表示從歷史數(shù)據(jù)中獲取的數(shù)據(jù)，des_node本次模糊匹配結果int src_count=Nodenum(src_node); int dst_count=Nodenum(dst_node);Node tempdst_count;Node nilNode=0;/用于結點初始化Nodecpy(temp,dst_node);Node newNodessrc_count+dst_count;/合并int j=0;for(j=0;j<(src_count+dst_count);j+)ne

38、wNodesj=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_count) newNodesnewCount=tempi; newCount+; Nodecpy(dst_node,newNodes);5測試與分析在編寫好所有的代碼之后，在終端輸入命令gcc *.c 即可編譯生成可執(zhí)行文件，然后在終端輸入./a.out按以下用例測試。5.1 精確查詢的實現(xiàn)測試用例1：

39、word:mopmopn. 拖把,鬼臉亂蓬蓬的頭發(fā)vt. 用拖把洗擦,擦,拭vi. 做鬼臉測試結果分析：用戶輸入“mop”進行搜索，該單詞在索引文件中找到，則從詞庫中讀取其釋義并輸出。 測試用例2：word:youyoupron. 你,你們;一個人,任何人測試結果分析：用戶輸入“you”進行搜索，該單詞在索引文件中找到，則從詞庫中讀取其釋義并輸出測試用例3：word:movemoven. 移動,遷居,步驟vt. 移動,開動,感動,鼓動vi. 移動,離開,運行,遷移,行動測試結果分析：同上，可以精確查出“move”的釋義。查詢的限制：用戶檢索的英文單詞長度不能超過24個有效字符，無法對空輸入進行

40、查詢。5.2 一般模糊查詢的實現(xiàn) 測試用例4：word:movedmoven. 移動,遷居,步驟vt. 移動,開動,感動,鼓動vi. 移動,離開,運行,遷移,行動測試結果分析，在第一次精確查詢時，由于詞庫中并沒有“moved”，這是由于用戶的拼寫錯誤照成的，本例中用戶輸入的是單詞的過去式，可進行一般的處理，去掉詞尾的“d”,再進行精確查詢，可輸出“move”對應的英譯漢釋義。測試用例5：word:jumppingjumpn. 跳躍,跳動,上漲,驚跳vt. 跳越,躍過,突升,使跳躍vi. 跳躍,跳,跳動,暴漲測試結果分析：用戶輸入的是“jumpping”,這個單詞也無法使用精確查詢，該單詞為in

41、g形式，可以先去掉詞尾的“ing”查看是否可以找不到，若找不到再嘗試由于元音+輔音結尾的形如mop-mopping形式的規(guī)則，再去掉詞尾的一個字符，再次進行精確查找，輸出單詞“jump”的釋義。測試用例6：word:flowersflowern. 花,精華,盛時vi. 開花,旺盛,成熟vt. 使開花測試結果分析：同上，flowers并不在詞庫中，是flower的復數(shù)形式，采用一般模糊查詢，輸出flower的釋義。5.3 基于動態(tài)規(guī)劃的模糊查詢實現(xiàn)測試用例7：word:lot o您是否要搜索： lots of plot out blot out a lot of pilot boat測試結果分析

42、：用戶輸入“l(fā)ot of”，由于詞庫中不存在該單詞，也不是由于詞尾如動名詞、單復數(shù)、過去式等原因造成的錯誤，使用一般模糊查找也無法確定出單詞的釋義。解決思路之一：使用基于全文的最長公共子序列搜索，遍歷單詞索引文件中的所有單詞，找出與“l(fā)ot o”具有最長公共子序列最大值的5個單詞或詞組 。但是由于基于動態(tài)規(guī)劃算法得出的最長公共子序列長度并不是基于連續(xù)子序列的（盡管它在算法的效率上是較優(yōu)的），因此還要使用機器學習模型對查詢結果集作進一步優(yōu)化。5.4 機器學習模型對于LCS模糊查詢的優(yōu)化測試用例8：（由于機器學習的過程是連續(xù)，以下測試結果是緊密關聯(lián)的）1. word:departmen您是否要搜索

43、： departed departure apartment department deportment2. word:departmentdepartmentn. 部,部門;學部,系;司,局,處,科3. word:departmen您是否要搜索： department departed departure apartment deportment4. word:deportmentdeportmentn. 行為,舉止5. word:departmen您是否要搜索： department deportment departed departure apartment 測試結果分析： 步驟1開始

44、時不存在模式文件，輸入“departmen”查找，會進入到LCS查找，得出來的模糊結果集是：departed,departure,apartment,department,deportment,不夠精確。 步驟2用戶根據(jù)提示輸入了“department”得到釋義，并且“department”在上一次LCS查找的模糊結果集中，因此“departmen”和“department”將會作為一個有趣模式被提取出來并記錄到模式文件中。 步驟3再次輸入“departmen”查詢，這時已存在記錄“department”，會優(yōu)先輸出“department”，得到優(yōu)化的模糊結果集： department，dep

45、arted,departure,apartment,deportment。 步驟4接著用戶選擇輸了“deportment”，它也在上一次LCS模糊集，所以“departmen”和“deportment”也會作為一個有趣模式被提取和保存。 步驟5再次輸入“departmen”查詢，模式記錄中已有“department”和“deportment”，最終得到的優(yōu)化模糊結果集為：department，deportment，departed,departure,apartment；5.5 機器學習模型的自動優(yōu)化測試用例9：（以下測試步驟也是緊密關聯(lián)的。）1. word:pople您是否要搜索： pope

46、 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 pr

47、ole apple測試結果分析： 步驟1和2是對模式記錄“pople”-“people”的提取，步驟3和4是對模式記錄“pople”-“popple”的提取，步驟5、6則是對“pople”-“popple”記錄的進一步強化，這樣根據(jù)樸素的貝葉斯分類，用戶輸入“pople”之后選擇“people”的次數(shù)是1，選擇“popple”的次數(shù)是2，這樣可以認為“pople”-“popple”模式是強于“pople”-“people”模式的，因此在步驟7中再次輸入“pople”查詢時會將“popple”提到“people”之前。同理，在大量的操作下，該機器學習模型也可以實現(xiàn)對模糊集的自動優(yōu)化。6結論本文基于機器學習的原理，對一個使用動態(tài)規(guī)劃的英漢字典模糊查詢系統(tǒng)構建一個機器學習的模型。該模型實現(xiàn)了學習用戶的搜索習慣，分析、提取有趣的模式，并基于歷史數(shù)據(jù)中的有趣模式，為用戶的模糊查詢提供智能化的結果集，并且基于統(tǒng)計學分析，實現(xiàn)自動優(yōu)化結果集，達到了良好的效果。參考文獻1 Drew Conway & White.J.R.機器