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

《2022年机器学习的英汉字典模糊查询研究与设计开发.docx》由会员分享，可在线阅读，更多相关《2022年机器学习的英汉字典模糊查询研究与设计开发.docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - A 基础理论B 应用讨论C 调查报告D 其他本科生毕业设计（论文）基于机器学习的英汉字典模糊查询二级学院： 信息科学与技术学院名师归纳总结 专业 ： 运算机科学与技术第 1 页,共 23 页年级 ： 2022 级学号 ： 2022344369作者姓名： 苏家辉指导老师： 蔡广基副教授完成日期：2022年 5 月 24日- - - - - - -精选学习资料 - - - - - - - - - 基于机器学习的英汉字典模糊查询专业名称：运算机科学与技术 作者姓名：苏家辉 指导老师：蔡广基论文答辩小组组长 ：蔡广基成员 ：王晓晔 关怀论文成果：名师归

2、纳总结 - - - - - - -第 2 页,共 23 页精选学习资料 - - - - - - - - - 目 录1 引言 11.1 讨论背景及其意义 11.2 讨论内容和目标 12 讨论与实现中的关键技术 12.1 机器学习的基本原理 12.2 好玩模式的提取 12.3 好玩模式集的优化 22.4 使用动态规划的最长公共子序列 23 系统设计 33.1 总体结构 33.2 业务流程设计 33.3 数据结构设计 43.3.1 宏定义 43.3.2 结构体 43.3.3 文件 54 实施应用 54.1 开发环境 54.1.1 硬件平台 54.1.2 软件平台 54.2 开发环境的搭建和配置 54

3、.3 编写代码 64.3.1最长公共子序列长度核心代码6154.3.2机器学习模型的c 语言实现 75 测试与分析135.1 精确查询的实现135.2 一般模糊查询的实现145.3 基于动态规划的模糊查询实现155.4 机器学习模型对于LCS模糊查询的优化5.5 机器学习模型的自动优化166 结论 18参考文献 18致谢 18名师归纳总结 - - - - - - -第 3 页,共 23 页精选学习资料 - - - - - - - - - 基于机器学习的英汉字典模糊查询作者 苏家辉 指导老师 蔡广基副教授（湛江师范学院信息科学与技术学院,湛江 524048 ）摘 要： 本文讨论机器学习的基本原理

4、和实现方法,对一个使用动态规划实现的英汉字典模糊查询系统构建一个机器学习模型；该模型实现了对用户的检索习惯进行分析,提取用户检索数据中的好玩模式,并通过统计频度对模式集进行自动优化,为用户的模糊查询供应智能化的查询结果；关键词： 机器学习模型,动态规划,模糊查询Fuzzy query of an English-Chinese dictionary based on machine learning Su Jiahui School of information science and technology, Zhanjiang Normal University, Zhanjiang,524

5、048 China Abstract： Based on the machine learningtheory , 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 use r s fuzzy query data and finds out the connections between the data, recording th

6、e mining models, applies them to the fuzzy query set during anon-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 programming algorithm ；

7、fuzzy query ；名师归纳总结 - - - - - - -第 4 页,共 23 页精选学习资料 - - - - - - - - - 1 引言1.1 讨论背景及其意义机器学习是现代人工智能讨论、进展的重要领域,它通过讨论运算机如何模拟或实现人类 的学习行为,通过分析、归纳、综合建立人类学习过程的运算模型或熟悉模型,基于已有数据 识别复杂模式,做出智能化的决策,并将其应用于实际问题中,为解决问题供应可行决策和方案支持 1；自 1980 年在卡内基梅隆高校召开第一届机器学习研讨会以来,机器学习的讨论工作 进展迅猛,已成为人工智能领域讨论的中心课题之一；随着机器学习的蓬勃进展,人们在工作 中累

8、积了大量可供测试算法的数据集或者超大数据集,机器学习工作者在此基础上可以进行更 精准的讨论；目前机器学习已经广泛应用于智能搜寻、数据分析等领域,如很多大型的搜寻引 擎网站的智能化的用户体验都是基于机器学习等讨论成果实现的；在大数据时代,机器学习研 究将会得到更大的进展；1.2 讨论内容和目标讨论机器学习模型的生成过程,构建机器学习的模型,将其应用到英汉字典模糊查询中；第 2 节介绍机器学习和模糊查询中的基本思路和实现方法,第3 节详细介绍算法实现的设计和数据的处理,第4 节编码实现构想,第5 节通过一些测试用例验证、完善算法的基本功能,最终一节对本讨论做出总结并提出新展望；2 讨论与实现中的关

9、键技术2.1 机器学习的基本原理机器学习是从已有或动态的数据中提取有用的新学问 过程为： 1. 收集学习材料,即猎取的数据； 2. 分析数据,从中提取好玩的模式；2,并将其应用到问题的决策中,其基本 3. 基于数据分析猎取好玩的模式,生成学问库,制定决策； 4. 通过学习新学问检验学问库数据的有效性,修改、完善学问库；在步骤 1 中猎取的学问是原始的数据或材料,他们看起来可能是杂乱无章的,因此在步骤 2 需要对数据进行分析,挖掘复杂的隐匿的模式,使用朴实的贝叶斯分类、噪声处理等方法对数据进行分别、提取,然后在将来的决策（步骤3）中使用这些模式去供应方案；但是提取出来的模式也可能是无效的,这就需

10、要步骤 4 不断地学习新的学问,判定模式是否有效,修改完善知识库；2.2 好玩模式的提取如何从原始数据中提取有用的模式,挖掘那些隐匿的好玩学问？分类是数据分析的一种重要的形式,通过它可以提取重要的数据类型；分类第一要基于现有数据建立一个分类模型,然后依据模型对数据进行分类；分类模型有决策树分类器、贝叶斯分类器和基于规章的分类器等名师归纳总结 - - - - - - -第 5 页,共 23 页精选学习资料 - - - - - - - - - 3；在英汉字典模糊查询系统,使用的是基于规章的分类器-形如 IF-THEN 的分类器；规章的IF 部分是前提条件,THEN 部分是结论；假如用户的某些输入满

11、意特定的条件就可认为是好玩模式；一般情形下,假如用户本次输入的数据在上一次模糊查询的结果集中,就可认为上一次为用户供应的结果集中的对应项是好玩的；假如不满意这一条件就可认为上一次的模糊结果集对用户没有帮忙,即为无效数据,丢弃之；英汉字典模糊查询系统的规章分类器实现大体如下：本次是否为精确查询？YESNO 上一次是否有模糊结果集？非好玩模式YESNO本次输入在上一次模糊结果集中？非好玩模式YES NO 好玩模式 非好玩模式图 2.1 规章分类器的实现2.3 好玩模式集的优化好玩模式集中的记录都是用户感爱好的,但是对于一个非精确的输入可能存在多个用户感爱好的挑选项,如何确定最优的挑选项呢？在统计学

12、上,使用概率表示一件事情在大量测试下发生的可能性 4；假设 A 代表用户的一个模糊输入,X 1, ,X i 代表 A 输入所对应的用户感兴趣的挑选项,设 pA|X i为用户输入 A 后挑选 X i的概率,分别计每一个挑选项 Xi 的 pA|X i,将具有最大值的挑选项排在最前面,即为最优的挑选项；用户每次输入A 后挑选 Xi 都是对 AX i 模式的一次强化；pA|X i=nX i/nA, 在该式中 nX i表示 X i被挑选的次数,nA 表示输入 A 的总次数,对于运算 A 的全部挑选项的 pA|X i,分母都是相同的,因此在详细的实现中,只需要为每一个挑选项项添加一个频度计数,这样具有最大

13、频度计数的挑选项即为最优的挑选项；2.4 使用动态规划的最长公共子序列名师归纳总结 动态规划5采纳自底向上的递推求值,把中间的结果储备起来并用于后面的运算,对于改善第 6 页,共 23 页蛮力搜寻的时间复杂度是比较有效的,假设an,bm 分别表示长度为n,m 的两个字符串,就a0, ,an-1 中的任意组合表示a 的子序列, b0 bm-1 中的任意组合表示b 的子序列 ,假如要求这两个字符串的最长公共子序列,采纳简洁的线性规划的方法是：列举a 的全部全部2 的 n 次方个子序列,观察它与bm 的最长公共子序列长度,采纳这种方法的时间复杂度是指数级的- - - - - - -精选学习资料 -

14、- - - - - - - - n2 ,假如采纳动态规划的方法可以使解决最初公共子序列问题优化到 （ n log n）；假设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

15、 ；如 an.=bm 就 Lnm= Ln-1m 和 Lnm-1 中的最大值 ；3 系统设计3.1 总体结构系统的主要功能包括以下部分 1. 用户输入接收用户输入的单词或词组,它们可能是精确的输入,也可能是存在拼写错误的单词或词组,如“department” 和“deparmen” 等； 2. 精确查询在字典的索引文件中查找查看是否存在,假如存在,就去词库的译义文件中读取,并将结果输出给用户； 3. 一般模糊查询假如通过精确查找无法查出该单词/词组,这种可能是由于单词的单复数,动词过去式,现在分词的 ing 形式类等造成,因此一般模糊查询就是对以上形式的单词进行简洁的处理,如去掉词尾的s、d等,

16、然后再对处理之后的单词进行精确查询； 4. 基于最长公共子序列的模糊查询（以下简称 lcs 查询）假如基于一般模糊查询仍无法查出,就使用lcs 查询,该查询是基于全文的检索,找出与输入单词最为相近的单词,即与输入单词的最长公共子序列是在全文中的最大值的单词,并将其作 为挑选项输出给用户； 5. 机器学习的模块开头时候,用户的使用记录为空；在一次lcs 查询之后,可以将lcs 模糊查询的结果集记录起来,假如用户下一次查询的输入与lcs 模糊查询的结果集记录有匹配项,就认为它们是一个有趣模式,并把其加入到好玩模式集中；每一次模糊查询给用户输出的结果集都会与模式结果集 中的结果进行匹配,假如找到,就

17、把模式结果集中的匹配数据与模糊结果集,匹配数据优先放 到结果集前,去除重复的项,生成最终结果集（决策）,最终输出给用户；3.2 业务流程设计系统的业务流程如下：名师归纳总结 - - - - - - -第 7 页,共 23 页精选学习资料 - - - - - - - - - 图 3.1 业务流程图3.3 数据结构设计3.3.1 宏定义宏定义 含义#define WORDCOUNT 59372 词库中单词的个数#define WORDLEN 24 单词的最大长度#define Errormsg perrormsg ； eXit1 ； 出错处理#define PRENUM 5 3.3.2 结构体 1

18、. 单词索引记录typedef struct 对于每个用户输入可以提取的有效模式的最 大个数名师归纳总结 char wordWORDLEN；length是该单词的释义的长度是第 8 页,共 23 页 int offset； int length； Node；其中 word 表示单词, offset是该单词在词库文件中的索引, 2. 用户的偏好记录typedef struct - - - - - - -精选学习资料 - - - - - - - - - char wordWORDLEN；int count；count是该单词的的支持度计数,即在用户的输入中该单词被Preference；其中 wor

19、d 表示用户偏好的单词,选中的频数； 3. 模式记录集typedef struct char inputWORDLEN；/ 用户输入的单词Preference presMAXPRES；/ 最多记录 5 个偏好Record；其中 input 是用户的非精确单词,pres 是该单词对应的用户偏好单词数组,最多 5 个记录；3.3.3 文件1. 单词的索引文件 star.ndx 存放的是一个个 Node 类型的数据,每个单词 /词组都有一个对应的 Node,这些数据依据单词的英文次序升序排列,因此在查找单词时可使用二分查找快速检索；2. 词库文件 star.dict 存放单词的释义3. 用户输入记录

20、文件 search.dat 存放用户输入的非精确单词,及该单词对应的 lcs 模糊查询结果集4. 模式记录文件 record.dat 存放的是好玩模式记录,这些记录也是按用户的输入非精确单词升序排序,这样便利在进行记录查找时使用二分查找,快速的查询某一记录是否存在,在记录的内部是依据模式的有效次数降序按序的；4 实施应用4.1 开发环境4.1.1 硬件平台 CPU ：i5-4200h 2.8GHz ；内存： 256MB 及以上；4.1.2 软件平台操作系统： Windows 虚拟机 VMware 10.0 下的 ubuntu linux ；开发工具： gcc ,vim 4.2 开发环境的搭建和

21、配置1安装 vim 名师归纳总结 在 linux 终端输入 sudo apt-get install vim-gtk ,然后输入root 用户密码等待完成vim 工具的安第 9 页,共 23 页- - - - - - -精选学习资料 - - - - - - - - - 装2vim 的基本配置在 linux 终端输入 vi /.vimrc 按如下方式配置set nu set ts=4 set sw=4 set cindent set autoident3环境变量的设置在终端输入 vi /.bashrc添加以下行：export PATH=$PATH:./ 储存之后在命令行输入 source .ba

22、shrc 4.3 编写代码4.3.1 最长公共子序列长度核心代码int LCSchar* a,char* b int n,m,i,j； int flag=0； n=strlena-1； m=strlenb-1； int L100100=0； fori=0；i=n ；i+ ifflag|ai=b0 Li0=1； flag=1 else Li0=0； flag=0； forj=0；j=m ；j+ ifflag|a0=bj L0j=1； flag=1 else L0j=0； 名师归纳总结 - - - - - - -第 10 页,共 23 页精选学习资料 - - - - - - - - - /char

23、 a100,b100；fori=1；i=n ； i+ forj=1；j=Li-1j Lij=Lij-1； else Lij=Li-1j； return Lnm； 4.3.2 机器学习模型的 c 语言实现 1. 在 learn.h 中的定义#ifndef _LEARN_H #define _LEARN_H #include dict.h #include #include #include #define MAXPRES 5/ 用户偏好的最大个数#define WORDLEN 24/ 单词最大长度#define PRENUM 5 / 有效模式的个数typedef struct char word

24、WORDLEN；/用户偏好int count；/ 次数Preference；typedef struct char inputWORDLEN；/ 用户挑选项Preference presMAXPRES；/ 最多记录 5 个偏好Record；/int Recordsize=sizeofRecord；/ 一个记录的大小void RecordDatachar* word,Node* nodes；void NewRecordchar* word,char* match_word；void Analysechar* word；void Solutionchar* newData,Node* nodes；

25、void DecisionNode* dst_node,Node* src_node；/ 用于快速查找查询记录或对记录快排名师归纳总结 int Recordcmpconst void * dst,const void * src；第 11 页,共 23 页- - - - - - -精选学习资料 - - - - - - - - - int Prescmpconst void * dst,const void * src；#endif 主要函数说明： RecordData：用于记录用户每次输入的非精确单词及其使用 lcs 模糊查询得到的结果集； Analyse：分析用户的输入和 lcs 模糊结果集

26、间的关系,提取好玩模式； NewRecord: 记录好玩模式； Solution：提取与用户输入的非精确单词相关的模式记录； Decision：依据历史模式记录,生成最终的决策方案； 2. 在 learn.c 中主要函数的实现void RecordDatachar* word,Node* nodes /word 代表用户的输入,nodes是模糊查询的结果集FILE* fd=fopen./search.dat,w+b if.fd return；int node_len=0int len=strlenword；/ 打开并清空上一次的结果fwrite&len,sizeofint,1,fd；fwrit

27、eword,1,len,fd whilestrlennodesnode_len.word0 node_len+；fwrite&node_len,sizeofint,1,fdfwritenodes,sizeofNode,node_len,fdfclosefd； int Recordcmpconst void * dst,const void * src Record* d=Record*dst；Record* s=Record*src；return strcmpd-input,s-input / 对用户偏好按降序排序 int Prescmpconst void * dst,const void

28、* src Preference* d=Preference*dst；Preference* s=Preference*src；return d-count count； void NewRecordchar* word,char* match_word FILE* fd=fopen./record.dat,a+b；if.fd 名师归纳总结 - - - - - - -第 12 页,共 23 页精选学习资料 - - - - - - - - - return； int RecordCount=0； Record* matched=NULL； char ch； fseekfd,0,SEEK_SET；

29、 fread&ch,1,1,fd； ifch=EOF/ 即初始状态,空文件 RecordCount=1； fseekfd,0,SEEK_SET； fwrite&RecordCount,sizeofint,1,fd Record newRcd=0； strcpynewRcd.input,word； strcpynewRcd.pres0.word,match_word newRcd.pres0.count=1； fwrite&newRcd,sizeofRecord,1,fd /check the first record fclosefd； return else fseekfd,0,SEEK_S

30、ET； fread&RecordCount,sizeofint,1,fd； Record* records=Record*mallocRecordCount+1*Recordsize； freadrecords,Recordsize,RecordCount,fd； fclosefd； /a+ 模式从文件头读,从文件尾写matched=Record*bsearchword,records,RecordCount,Recordsize,Recordcmp ； / 是已有记录 ifmatched.=NULL int num=0,i；/用于标识是否找到whilestrlenmatched-presnu

31、m.word0 num+ ；/ 运算当前用户偏好的数目 fori=0；ipresi.word matched-presi.count+；qsortmatched-名师归纳总结 pres,num,sizeofPreference,Prescmp；第 13 页,共 23 页- - - - - - -精选学习资料 - - - - - - - - - break； if.inum/ 匹配项不在偏好数组中 Preference newPre=0； strcpynewPre.word,match_word newPre.count=1； ifipresi=newPre； else matched-pres

32、i-1=newPre； / 新记录 else RecordCount+； Record newRcd=0； strcpynewRcd.input,word； strcpynewRcd.pres0.word,match_word newRcd.pres0.count=1； recordsRecordCount-1=newRcd； /对 record数组重新排序 qsortrecords,RecordCount,sizeofRecord,Recordcmp / 写回记录文件 FILE* fw=fopen./record.dat,r+b； fseekfw,0,SEEK_SET； fwrite&Rec

33、ordCount,sizeofint,1,fw fwriterecords,sizeofRecord,RecordCount,fw freerecords； fclosefw； void Analysechar* match_word FILE* fd=fopen./search.dat,rb；if.fd 名师归纳总结 return；第 14 页,共 23 页 int len=0； fread&len,sizeofint,1,fd char wordlen+1； freadword,1,len,fd wordlen=0；- - - - - - -精选学习资料 - - - - - - - - -

34、 /printfvalue in Analyse:%sn,%d,word,len； int node_len=0； fread&node_len,sizeofint,1,fd Node nodesnode_len； freadnodes,sizeofNode,node_len,fd fclosefd； int i=0； /判定是否为好玩模式 fori=0；ipresnum.word /printfpres value:%sn,matched-presnum.word； num+； /printf匹配记录中的pres:%dn,num； ifnum PRENUM num=PRENUM ； int

35、i； fori=0；ipresi.word； freerecords； / 运算结点数目int NodenumNode* nodes int i=0； whilestrlennodesi.word return i i+； / 结点数组拷贝void NodecpyNode* dst_node,Node* src_node int src_count=Nodenumsrc_node；int i=0；fori=0； isrc_count；i+ strcpydst_nodei.word,src_nodei.word； / 结点查找int FindNodechar* word,Node* nodes,

36、int num int i=0；找到fori=0； inum ；i+ return 0if.strcasecmpword,nodesi.word/return 1； /src_node: nodes from record file,des_node: final nodes array to dual search void DecisionNode* dst_node,Node* src_node 名师归纳总结 - - - - - - -第 16 页,共 23 页精选学习资料 - - - - - - - - - /src_node表示从历史数据中猎取的数据,des_node本次模糊匹配结果

37、int src_count=Nodenumsrc_node； int dst_count=Nodenumdst_node；Node tempdst_count；Node nilNode=0；/ 用于结点初始化Nodecpytemp,dst_node；Node newNodessrc_count+dst_count；/ 合并int j=0；forj=0； jsrc_count+dst_count；j+ newNodesj=nilNode；/ NodecpynewNodes,src_node；int newCount=NodenumnewNodes；int i=0；fori=0； idst_count；