机器学习的英汉字典模糊查询研究与设计开发

机器学习的英汉字典模糊查询研究与设计开发○○A基础理论●B应用研究○C调查报告○D其他本科生毕业论基于机器学习的英汉字典模糊查询二级学院：信息科学与技术学院专业：计算机科学与技术年级：2010级学号：2010344369作者姓名：苏家辉指导教师：蔡广基副教授完成日期：2014年5月24日基于机器学习的英汉字典模糊查询专业名称：计算机科学与技术作者姓名：苏家辉指导教师：蔡广基论文答辩小组组长：蔡广基成员：王晓晔关心论文成绩：given.Themodelanalysestheuser’sfuzzyquerydataandfindsouttheconnectionsbetweenthedata,recordingtheminingmodels,appliesthemtothefuzzyquerysetduringanon-accuratesearching,andautomaticallyimprovestheminingmodelssetaccordingtothestatisticsatfrequenciesofuser,providingintelligentsolutionsforthefuzzyquery.Keywords:Machinelearning。dynamicprogrammingalgorithm。fuzzyquery。1引言1.1研究背景及其意义机器学习是现代人工智能研究、发展的重要领域，它通过研究计算机如何模拟或实现人类的学习行为，通过分析、归纳、综合建立人类学习过程的计算模型或认识模型，基于已有数据识别复杂模式，做出智能化的决策，并将其应用于实际问题中，为解决问题提供可行决策和方案支持[1]。自1980年在卡内基梅隆大学召开第一届机器学习研讨会以来，机器学习的研究工作发展迅猛，已成为人工智能领域研究的中心课题之一。随着机器学习的蓬勃发展，人们在工作中累积了大量可供测试算法的数据集或者超大数据集，机器学习工作者在此基础上可以进行更精准的研究。目前机器学习已经广泛应用于智能搜索、数据分析等领域，如许多大型的搜索引擎网站的智能化的用户体验都是基于机器学习等研究成果实现的。在大数据时代，机器学习研究将会得到更大的发展。1.2研究内容和目标研究机器学习模型的生成过程，构建机器学习的模型，将其应用到英汉字典模糊查询中。第2节介绍机器学习和模糊查询中的基本思路和实现方法，第3节具体介绍算法实现的设计和数据的处理，第4节编码实现构想，第5节通过一些测试用例验证、完善算法的基本功能，最后一节对本研究做出总结并提出新展望。2研究与实现中的关键技术2.1机器学习的基本原理机器学习是从已有或动态的数据中提取有用的新知识[2]，并将其应用到问题的决策中，其基本过程为：1.收集学习材料，即获取的数据；2.分析数据，从中提取有趣的模式；3.基于数据分析获取有趣的模式，生成知识库，制定决策；4.通过学习新知识检验知识库数据的有效性，修改、完善知识库。在步骤1中获取的知识是原始的数据或材料，他们看起来可能是杂乱无章的，因此在步骤2需要对数据进行分析，挖掘复杂的隐藏的模式，使用朴素的贝叶斯分类、噪声处理等方法对数据进行分离、提取，然后在将来的决策（步骤3）中使用这些模式去提供方案。但是提取出来的模式也可能是无效的，这就需要步骤4不断地学习新的知识，判定模式是否有效，修改完善知识库。2.2有趣模式的提取如何从原始数据中提取有用的模式，挖掘那些隐藏的有趣知识？分类是数据分析的一种重要的形式，通过它可以提取重要的数据类型。分类首先要基于现有数据建立一个分类模型，然后根据模型对数据进行分类。分类模型有决策树分类器、贝叶斯分类器和基于规则的分类器等[3]。在英汉字典模糊查询系统，使用的是基于规则的分类器--形如IF-THEN的分类器。规则的IF部分是前提条件，THEN部分是结论。假如用户的某些输入满足特定的条件则可认为是有趣模式。一般情况下，如果用户本次输入的数据在上一次模糊查询的结果集中，则可认为上一次为用户提供的结果集中的对应项是有趣的。如果不满足这一条件则可认为上一次的模糊结果集对用户没有帮助，即为无效数据，丢弃之。英汉字典模糊查询系统的规则分类器实现大体如下：本次是否为精确查询？YESNO上一次是否有模糊结果集？非有趣模式YESNO本次输入在上一次模糊结果集中？非有趣模式YESNO有趣模式非有趣模式图2.1规则分类器的实现2.3有趣模式集的优化有趣模式集中的记录都是用户感兴趣的，但是对于一个非精确的输入可能存在多个用户感兴趣的选择项，如何确定最优的选择项呢？在统计学上，使用概率表示一件事情在大量测试下发生的可能性[4]。假设A代表用户的一个模糊输入，X1，…，Xi代表A输入所对应的用户感兴趣的选择项，设p(A|Xi)为用户输入A后选择Xi的概率，分别计每一个选择项Xi的p(A|Xi),将具有最大值的选择项排在最前面，即为最优的选择项。用户每次输入A后选择Xi都是对A—Xi模式的一次强化。p(A|Xi)=n(Xi)/n(A),在该式中n(Xi)表示Xi被选择的次数，n(A)表示输入A的总次数，对于计算A的所有选择项的p(A|Xi)，分母都是相同的，因此在具体的实现中，只需要为每一个选择项项添加一个频度计数，这样具有最大频度计数的选择项即为最优的选择项。2.4使用动态规划的最长公共子序列动态规划[5]采用自底向上的递推求值，把中间的结果存储起来并用于后面的计算，对于改善蛮力搜索的时间复杂度是比较有效的，假设a[n]，b[m]分别表示长度为n,m的两个字符串，则a[0],…,a[n-1]中的任意组合表示a的子序列，b[0]…b[m-1中的任意组合表示b的子序列,如果要求这两个字符串的最长公共子序列，采用简单的线性规划的方法是：列举a的所有所有2的n次方个子序列，察看它与b[m]的最长公共子序列长度，采用这种方法的时间复杂度是指数级的Ο(n^2)，如果采用动态规划的方法可以使解决最初公共子序列问题优化到Ο（nlogn）。假设L[n][m]表示a的前n个字符与b的前m个字符之间的最长公共子序列长度，则L[n][m]的递推公式如下：LCSflag初始值为0，用于标记当n或m为0时，前面是否有a的子序列与b的子序列相等的情况。对于n=0或m=0,若a[n]=a[m],则L[n][m]=LCSflag=1,如果a[n]!=a[m],若LCSflag=1则，L[n][m]=1，否则L[n][m]=0；对于n和m都不等于0的情况：若a[n]=b[m]则L[n][m]=L[n-1][m-1]+1；若a[n]!=b[m]则L[n][m]={L[n-1][m]和L[n][m-1]中的最大值}。3系统设计3.1总体结构系统的主要功能包括以下部分1.用户输入接收用户输入的单词或词组，它们可能是精确的输入，也可能是存在拼写错误的单词或词组，如“department”和“deparmen”等。2.精确查询在字典的索引文件中查找查看是否存在，如果存在，则去词库的译义文件中读取，并将结果输出给用户。3.一般模糊查询如果通过精确查找无法查出该单词/词组，这种可能是由于单词的单复数，动词过去式，现在分词的ing形式类等造成，因此一般模糊查询就是对以上形式的单词进行简单的处理，如去掉词尾的‘s’、‘d’等，然后再对处理之后的单词进行精确查询。4.基于最长公共子序列的模糊查询（以下简称lcs查询）如果基于一般模糊查询仍无法查出，则使用lcs查询，该查询是基于全文的检索，找出与输入单词最为相近的单词，即与输入单词的最长公共子序列是在全文中的最大值的单词，并将其作为选择项输出给用户。5.机器学习的模块开始时候，用户的使用记录为空。在一次lcs查询之后，可以将lcs模糊查询的结果集记录起来，如果用户下一次查询的输入与lcs模糊查询的结果集记录有匹配项，则认为它们是一个有趣模式，并把其加入到有趣模式集中。每一次模糊查询给用户输出的结果集都会与模式结果集中的结果进行匹配，如果找到，则把模式结果集中的匹配数据与模糊结果集，匹配数据优先放到结果集前，去除重复的项，生成最终结果集（决策），最后输出给用户。3.2业务流程设计系统的业务流程如下：图3.1业务流程图是是3.3数据结构设计3.3.1宏定义宏定义含义#defineWORDCOUNT59372词库中单词的个数#defineWORDLEN24单词的最大长度#defineError(msg){perror(msg)。eXit(1)。}出错处理#definePRENUM5对于每个用户输入可以提取的有效模式的最大个数3.3.2结构体1.单词索引记录typedefstruct{ charword[WORDLEN]。 intoffset。 intlength。 }Node。其中word表示单词，offset是该单词在词库文件中的索引，length是该单词的释义的长度2.用户的偏好记录typedefstruct{ charword[WORDLEN]。 intcount。}Preference。其中word表示用户偏好的单词，count是该单词的的支持度计数，即在用户的输入中该单词被选中的频数。3.模式记录集typedefstruct{ charinput[WORDLEN]。//用户输入的单词 Preferencepres[MAXPRES]。//最多记录5个偏好}Record。其中input是用户的非精确单词，pres是该单词对应的用户偏好单词数组，最多5个记录。3.3.3文件1.单词的索引文件star.ndx存放的是一个个Node类型的数据，每个单词/词组都有一个对应的Node，这些数据按照单词的英文次序升序排列，因此在查找单词时可使用二分查找快速检索。2.词库文件star.dict存放单词的释义3.用户输入记录文件search.dat存放用户输入的非精确单词，及该单词对应的lcs模糊查询结果集4.模式记录文件record.dat存放的是有趣模式记录，这些记录也是按用户的输入非精确单词升序排序，这样方便在进行记录查找时使用二分查找，快速的查询某一记录是否存在，在记录的内部是按照模式的有效次数降序按序的。4实施应用4.1开发环境4.1.1硬件平台CPU：i5-4200h2.8GHz；内存：256MB及以上。4.1.2软件平台操作系统：Windows虚拟机VMware10.0下的ubuntulinux。开发工具：gcc,vim4.2开发环境的搭建和配置安装vim在linux终端输入

sudoapt-getinstallvim-gtk，然后输入root用户密码等待完成vim工具的安装vim的基本配置在linux终端输入vi~/.vimrc按如下方式配置setnusetts=4setsw=4setcindentsetautoident3．环境变量的设置在终端输入vi~/.bashrc添加以下行：exportPATH="$PATH:./"保存之后在命令行输入source.bashrc4.3编写代码4.3.1最长公共子序列长度核心代码intLCS(char*a,char*b){intn,m,i,j。intflag=0。n=strlen(a)-1。m=strlen(b)-1。intL[100][100]={0}。for(i=0。i<=n。i++){ if(flag||(a[i]==b[0])) { L[i][0]=1。 flag=1。 } elseL[i][0]=0。 }flag=0。for(j=0。j<=m。j++){ if(flag||(a[0]==b[j])) { L[0][j]=1。 flag=1。 } elseL[0][j]=0。}//chara[100],b[100]。for(i=1。i<=n。i++)for(j=1。j<=m。j++){if(a[i]==b[j])L[i][j]=L[i-1][j-1]+1。elseif(L[i][j-1]>=L[i-1][j])L[i][j]=L[i][j-1]。else L[i][j]=L[i-1][j]。}returnL[n][m]。}4.3.2机器学习模型的c语言实现1.在learn.h中的定义#ifndef_LEARN_H#define_LEARN_H#include"dict.h"#include<stdlib.h>#include<string.h>#include<stdio.h>#defineMAXPRES5//用户偏好的最大个数#defineWORDLEN24//单词最大长度#definePRENUM5//有效模式的个数typedefstruct{ charword[WORDLEN]。//用户偏好 intcount。//次数}Preference。typedefstruct{ charinput[WORDLEN]。//用户选择项 Preferencepres[MAXPRES]。//最多记录5个偏好}Record。//intRecordsize=sizeof(Record)。//一个记录的大小voidRecordData(char*word,Node*nodes)。voidNewRecord(char*word,char*match_word)。voidAnalyse(char*word)。voidSolution(char*newData,Node*nodes)。voidDecision(Node*dst_node,Node*src_node)。//用于快速查找查询记录或对记录快排intRecordcmp(constvoid*dst,constvoid*src)。intPrescmp(constvoid*dst,constvoid*src)。#endif主要函数解释：RecordData：用于记录用户每次输入的非精确单词及其使用lcs模糊查询得到的结果集。Analyse：分析用户的输入和lcs模糊结果集间的关系，提取有趣模式。NewRecord:记录有趣模式。Solution：提取与用户输入的非精确单词相关的模式记录。Decision：根据历史模式记录，生成最终的决策方案。2.在learn.c中主要函数的实现voidRecordData(char*word,Node*nodes){//word代表用户的输入，nodes是模糊查询的结果集 FILE*fd=fopen("./search.dat","w+b")。//打开并清空上一次的结果 if(!fd) return。 intnode_len=0。 intlen=strlen(word)。 fwrite(&len,sizeof(int),1,fd)。 fwrite(word,1,len,fd)。while(strlen(nodes[node_len].word)>0) node_len++。 fwrite(&node_len,sizeof(int),1,fd)。 fwrite(nodes,sizeof(Node),node_len,fd)。 fclose(fd)。}intRecordcmp(constvoid*dst,constvoid*src){ Record*d=(Record*)dst。 Record*s=(Record*)src。 returnstrcmp(d->input,s->input)。}//对用户偏好按降序排序intPrescmp(constvoid*dst,constvoid*src){ Preference*d=(Preference*)dst。 Preference*s=(Preference*)src。 return(d->count)<(s->count)。}voidNewRecord(char*word,char*match_word){FILE*fd=fopen("./record.dat","a+b")。 if(!fd) return。intRecordCount=0。。Record*matched=NULL。charch。fseek(fd,0,SEEK_SET)。fread(&ch,1,1,fd)。if(ch==EOF)//即初始状态，空文件{ RecordCount=1。 fseek(fd,0,SEEK_SET)。 fwrite(&RecordCount,sizeof(int),1,fd)。 RecordnewRcd={0}。 strcpy(newRcd.input,word)。 strcpy(newRcd.pres[0].word,match_word)。 newRcd.pres[0].count=1。fwrite(&newRcd,sizeof(Record),1,fd)。 //checkthefirstrecord 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,records,RecordCount,Recordsize,Recordcmp)。//是已有记录if(matched!=NULL){ intnum=0,i。//用于标识是否找到 while(strlen(matched->pres[num].word)>0) num++。//计算当前用户偏好的数目 for(i=0。i<num。i++) { if(!strcmp(match_word,matched->pres[i].word)){ matched->pres[i].count++。 qsort(matched->pres,num,sizeof(Preference),Prescmp)。 break。 } } if(!(i<num))//匹配项不在偏好数组中 { PreferencenewPre={0}。 strcpy(newPre.word,match_word)。 newPre.count=1。 if(i<MAXPRES) matched->pres[i]=newPre。 elsematched->pres[i-1]=newPre。 }}//新记录else{RecordCount++。 RecordnewRcd={0}。 strcpy(newRcd.input,word)。 strcpy(newRcd.pres[0].word,match_word)。 newRcd.pres[0].count=1。 records[RecordCount-1]=newRcd。 //对record数组重新排序 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(fw)。}}voidAnalyse(char*match_word){FILE*fd=fopen("./search.dat","rb")。 if(!fd) return。intlen=0。fread(&len,sizeof(int),1,fd)。charword[len+1]。fread(word,1,len,fd)。word[len]='\0'。//printf("valueinAnalyse:%s\n,%d",word,len)。intnode_len=0。fread(&node_len,sizeof(int),1,fd)。Nodenodes[node_len]。fread(nodes,sizeof(Node),node_len,fd)。fclose(fd)。inti=0。//判断是否为有趣模式for(i=0。i<node_len。i++){ if(!strcmp(nodes[i].word,match_word)) { NewRecord(word,match_word)。 break。 }}}voidSolution(char*newData,Node*nodes){FILE*fd=fopen("./record.dat","rb")。 if(!fd) return。intRecordCount=0。charch。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)。Record*matched=(Record*)bsearch(newData,records,RecordCount,Recordsize,Recordcmp)。if(!matched){//无历史记录 free(records)。 //printf("Solutioncalledailues\n")。 return。}//读出有效模式，最多5个intnum=0。while(strlen(matched->pres[num].word)){ //printf("presvalue:%s\n",matched->pres[num].word)。 num++。}//printf("匹配记录中的pres:%d\n",num)。if(num>PRENUM) num=PRENUM。inti。for(i=0。i<num。i++) strcpy(nodes[i].word,matched->pres[i].word)。free(records)。}//计算结点数目intNodenum(Node*nodes){ inti=0。while(strlen(nodes[i].word)) i++。returni。}//结点数组拷贝voidNodecpy(Node*dst_node,Node*src_node){ intsrc_count=Nodenum(src_node)。 inti=0。 for(i=0。i<src_count。i++) {strcpy(dst_node[i].word,src_node[i].word)。}}//结点查找intFindNode(char*word,Node*nodes,intnum){ inti=0。 for(i=0。i<num。i++) if(!strcasecmp(word,nodes[i].word))//找到 return1。 return0。}//src_node:nodesfromrecordfile,des_node:finalnodesarraytodualsearchvoidDecision(Node*dst_node,Node*src_node){//src_node表示从历史数据中获取的数据，des_node本次模糊匹配结果 intsrc_count=Nodenum(src_node)。intdst_count=Nodenum(dst_node)。 Nodetemp[dst_count]。 NodenilNode={0}。//用于结点初始化 Nodecpy(temp,dst_node)。 NodenewNodes[src_count+dst_count]。//合并 intj=0。 for(j=0。j<(src_count+dst_count)。j++) newNodes[j]=nilNode。// Nodecpy(newNodes,src_node)。 intnewCount=Nodenum(newNodes)。 inti=0。 for(i=0。i<dst_count。i++) {if(!FindNode(temp[i].word,src_node,src_count)) {newNodes[newCount]=temp[i]。 newCount++。 } } Nodecpy(dst_node,newNodes)。}5测试与分析在编写好所有的代码之后，在终端输入命令gcc*.c即可编译生成可执行文件，然后在终端输入./a.out按以下用例测试。5.1精确查询的实现测试用例1：word:mopmopn.拖把,鬼脸乱蓬蓬的头发vt.用拖把洗擦,擦,拭vi.做鬼脸测试结果分析：用户输入“mop”进行搜索，该单词在索引文件中找到，则从词库中读取其释义并输出。测试用例2：word:youyoupron.你,你们。一个人,任何人测试结果分析：用户输入“you”进行搜索，该单词在索引文件中找到，则从词库中读取其释义并输出测试用例3：word:movemoven.移动,迁居,步骤vt.移动,开动,感动,鼓动vi.移动,离开,运行,迁移,行动测试结果分析：同上，可以精确查出“move”的释义。查询的限制：用户检索的英文单词长度不能超过24个有效字符，无法对空输入进行查询。5.2一般模糊查询的实现测试用例4：word:movedmoven.移动,迁居,步骤vt.移动,开动,感动,鼓动vi.移动,离开,运行,迁移,行动测试结果分析，在第一次精确查询时，由于词库中并没有“moved”，这是由于用户的拼写错误照成的，本例中用户输入的是单词的过去式，可进行一般的处理，去掉词尾的“d”,再进行精确查询，可输出“move”对应的英译汉释义。测试用例5：word:jumppingjumpn.跳跃,跳动,上涨,惊跳vt.跳越,跃过,突升,使跳跃vi.跳跃,跳,跳动,暴涨测试结果分析：用户输入的是“jumpping”,这个单词也无法使用精确查询，该单词为ing形式，可以先去掉词尾的“ing”查看是否可以找不到，若找不到再尝试由于元音+辅音结尾的形如mop--mopping形式的规则，再去掉词尾的一个字符，再次进行精确查找，输出单词“jump”的释义。测试用例6：word:flowersflowern.花,精华,盛时vi.开花,旺盛,成熟vt.使开花测试结果分析：同上，flowers并不在词库中，是flower的复数形式，采用一般模糊查询，输出flower的释义。5.3基于动态规划的模糊查询实现测试用例7：word:loto您是否要搜索：lotsofplotoutblotoutalotofpilotboat测试结果分析：用户输入“lotof”，由于词库中不存在该单词，也不是由于词尾如动名词、单复数、过去式等原因造成的错误，使用一般模糊查找也无法确定出单词的释义。解决思路之一：使用基于全文的最长公共子序列搜索，遍历单词索引文件中的所有单词，找出与“loto”具有最长公共子序列最大值的5个单词或词组。但是由于基于动态规划算法得出的最长公共子序列长度并不是基于连续子序列的（尽管它在算法的效率上是较优的），因此还要使用机器学习模型对查询结果集作进一步优化。5.4机器学习模型对于LCS模糊查询的优化测试用例8：（由于机器学习的过程是连续，以下测试结果是紧密关联的）1.word:departmen您是否要搜索：departeddepartureapartmentdepartmentdeportment2.word:departmentdepartmentn.部,部门。学部,系。司,局,处,科3.word:departmen您是否要搜索：departmentdeparteddepartureapartmentdeportment4.word:deportmentdeportmentn.行为,举止5.word:departmen您是否要搜索：departmentdeportmentdeparteddepartureapartment测试结果分析：步骤1开始时不存在模式文件，输入“departmen”查找，会进入到LCS查找，得出来的模糊结果集是：{departed,departure,apartment,department,deportment},不够精确。步骤2用户根据提示输入了“department”得到释义，并且“department”在上一次LCS查找的模糊结果集中，因此“departmen”和“department”将会作为一个有趣模式被提取出来并记录到模式文件中。步骤3再次输入“departmen”查询，这时已存在记录“department”，会优先输出“department”，得到优化的模糊结果集：{department，departed,departure,apartment,deportment}。步骤4接着用户选择输了“deportm