基于改进编辑距离的字符串相似度求解算法

本文作者：姜华；韩安琪；王美佳；王峥；吴雲玲；成功正常投稿发表论文到《计算机工程》2014年01期,引用请注明来源400期刊网！

【摘要】：编辑距离(LD)算法在求解两个字符串的相似问题时只考虑了编辑操作次数,未考虑字符串之间的公共子串对相似度的影响。为此,提出一种基于改进编辑距离的字符串相似度求解算法,对字符串相似度度量公式及Levenshtein矩阵计算方法进行改进。在计算编辑距离时,以原有矩阵求出两字符串的最长公共子串及所有LD回溯路径。选取一个单词作为源串,一组与源串不同程度相似的单词为目标串,将改进的相似度度量公式与现有的字符串相似度计算方法进行比较,改进公式减少了进入胜者表的目标串数,相似度的样本极差和标准差分别为0.331和0.150。实验结果表明,改进算法在不改变空间复杂度的情况下,计算字符串相似度的准确性更高,且查询方式更灵活。
【论文正文预览】：1概述字符串相似问题在文本比较、信息处理等领域,具有非常广泛的应用背景。求解2个字符串之间相似度的方法按照所依据特征的不同通常可以划分为3类[1]:基于字面相似的方法,基于统计关联的方法,基于语义相似的方法。其中,基于字面相似的方法主要有基于编辑距离的方法和基于相
【文章分类号】：TP301.6;TP391.1
【稿件关键词】：编辑距离LD算法回溯路径最长公共子串相似度模糊查询
【参考文献】:

• 赵作鹏;尹志民;王潜平;许新征;江海峰;;一种改进的编辑距离算法及其在数据处理中的应用[J];计算机应用;2009年02期
• 周汉平;;Levenshtein距离在编程题自动评阅中的应用研究[J];计算机应用与软件;2011年05期
• 陶佳燕;李银红;石东源;覃松涛;郑发林;蒙亮;;EMS与继电保护定值校核系统实时数据匹配新方法[J];电力系统自动化;2012年10期
• 文必龙;肖波;陈新荣;;石油勘探开发数据元管理技术[J];大庆石油学院学报;2012年01期
• 刘书一;;基于文本相似度的网页消重策略[J];计算机应用与软件;2011年11期
• 肖磊;陈小荷;;古籍版本异文的自动发现[J];中文信息学报;2010年05期
• 李林;王红;付宇;杨璇;王静;;民航突发事件应急案例语义检索方法研究[J];计算机工程与设计;2011年03期
• 刘荣辉;郑建国;王翔;;采用最小DFS的Deep Web结构化数据抽取[J];图书情报工作;2010年14期
• 叶焕倬;吴迪;;基于改进编辑距离的相似重复记录清理算法[J];现代图书情报技术;2011年Z1期
• 王健;哈力木拉提·买买提;;印刷体维吾尔文识别后处理[J];新疆大学学报(自然科学版);2011年02期
• 文必龙;付玥;;数据集成中数据项与数据元匹配算法[J];计算机系统应用;2012年03期
• 钱苏林;李炜;王晶;;一种基于特征值的短信过滤匹配算法[J];计算机系统应用;2012年05期
• 王育红;陈军;;GIS客户数据库更新自动化实施算法研究[A];中国测绘学会第九次全国会员代表大会暨学会成立50周年纪念大会论文集[C];2009年
• 秦岭;面向企业用户的在线推荐算法研究[D];东华大学;2011年
• 梅筱;视频特征及其描述词汇的对齐研究[D];北京邮电大学;2011年
• 张利;词汇专家模块的研究与实现[D];北京邮电大学;2011年
• 王欣;抄袭C源代码可视化智能检测方法与实现[D];大连理工大学;2011年
• 秦英;问答系统中文输入纠错技术研究[D];山东大学;2012年
• 陈忱;DBFS技术及其在远洋运输业务邮件管理中的应用研究[D];南京航空航天大学;2012年
• 陶佳燕;继电保护在线校核EMS实时数据匹配及断点问题研究[D];华中科技大学;2012年
• 韩安琪;基于改进编辑距离的字符串相似算法研究[D];东北师范大学;2013年
• 刘霞;脚本类测试题自动评阅系统[D];东华大学;2014年
• 吉胜军;;基于Levenshtein distance算法的句子相似度计算[J];电脑知识与技术;2009年09期
• 曹恬;周丽;张国煊;;一种基于词共现的文本相似度计算[J];计算机工程与科学;2007年03期
• 郭庆琳;李艳梅;唐琦;;基于VSM的文本相似度计算的研究[J];计算机应用研究;2008年11期
• 李珩,朱靖波,姚天顺;基于SVM的中文组块分析[J];中文信息学报;2004年02期
• 程金宏;刘东升;;程序代码相似度自动度量技术研究综述[J];内蒙古师范大学学报(自然科学汉文版);2006年04期
• 余建明;徐波;薛一波;;基于网络处理器的高速字符串匹配[J];清华大学学报(自然科学版)网络.预览;2008年04期
• 邓爱萍;;程序代码相似度度量算法研究[J];计算机工程与设计;2008年17期
• 佘石泉;周肆清;;正则表达式在编程题自动阅卷中的应用[J];计算机技术与发展;2007年07期
• 龚安;刘华山;;基于编辑距离的XML文档结构聚类的改进算法[J];微计算机应用;2008年02期
• 王建冬;王继民;田飞佳;;一种基于内容规则的网页去噪算法[J];现代图书情报技术;2008年03期
• 张凯兵;;基于编辑距离的手写数字Freeman链码匹配算法[J];孝感学院学报;2009年06期
• 聂卉;;基于网页结构相似度的Web信息抽取[J];情报学报;2011年03期
• 陈伟,丁秋林;一种XML相似重复数据的清理方法研究[J];北京航空航天大学学报;2004年09期
• 刘劼;;一种文档页面的样式分类方法[J];科技创新导报;2009年15期
• 赵莉;;基于OCR的拼写校正系统[J];兵工自动化;2010年09期
• 郑仕辉,周傲英,张龙;XML文档的相似测度和结构索引研究[J];计算机学报;2003年09期
• 郭浩,欧宗瑛,何洋;一个新的基于细节特征的指纹匹配方法[J];大连理工大学学报;2005年01期
• 刘守群;朱明;谭晓彬;;一种基于树匹配的网页语义块挖掘算法[J];小型微型计算机系统;2009年08期
• 王斌;郭庆;李中博;杨晓春;;支持块编辑距离的索引结构[A];第26届中国数据库学术会议论文集（A辑）[C];2009年
• 李刚;郭崇慧;林鸿飞;杨志豪;唐焕文;;基于词典法和机器学习法相结合的蛋白质名识别[A];大连理工大学生物医学工程学术论文集（第2卷）[C];2005年
• 王洁;宋柔;;HSK动态作文语料库偏误标注方法研究[A];第四届全国学生计算语言学研讨会会议论文集[C];2008年
• 杨洋;杨新武;李玉鉴;;一种基于特征串比较的自动眉毛识别方法[A];图像图形技术研究与应用2009——第四届图像图形技术与应用学术会议论文集[C];2009年
• 宋锐;林鸿飞;;面向中文新闻领域的移动摘要系统[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年
• 吴闯;吴宏林;张俐;刘绍明;;基于文本-模板直接匹配的机器翻译系统[A];中国计算机语言学研究前沿进展（2007-2009）[C];2009年
• 卢延科;尹宝生;张桂平;苗雪雷;白宇;;基于伪LCS的中文专利句子相似度计算方法[A];第五届全国信息检索学术会议论文集[C];2009年
• 郑仕辉;何奇;张龙;梁宇奇;周傲英;;XML文档的相似测度研究[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年
• 龚才春;黄玉兰;许洪波;白硕;;基于多重索引模型的大规模词典近似匹配算法[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年
• 李璐;王宏志;李建中;高宏;;Ed-Sjoin:一种优化的字符串相似连接算法[A];第26届中国数据库学术会议论文集（B辑）[C];2009年
• PALADIN;编程沙龙[N];电脑报;2003年
• 王洁;汉语中介语偏误的计算机处理方法研究[D];北京语言大学;2008年
• 戴东波;序列数据的相似性查询研究[D];复旦大学;2009年
• 常桂松;生物序列分析中若干概率模型研究及应用[D];大连理工大学;2011年
• 刘卫红;垃圾邮件检测与过滤关键技术研究[D];华南理工大学;2010年
• 胡伟;面向MEMS产品概念设计的多模式实例检索与评价方法研究[D];华南理工大学;2012年
• 杨连平;生物序列的相对特征分析及Burrows-Wheeler方法[D];大连理工大学;2011年
• 肖冰;人脸画像—照片的合成与识别方法研究[D];西安电子科技大学;2010年
• 张天成;实时数据流相关性分析与挖掘技术研究[D];东北大学;2008年
• 张巍;融合FAQ、本体和推理技术的问答系统研究[D];太原理工大学;2011年
• 袁培森;基于LSH的Web数据相似性查询研究[D];复旦大学;2011年
• 韩安琪;基于改进编辑距离的字符串相似算法研究[D];东北师范大学;2013年
• 李星秀;非规则平面碎片匹配关键技术研究[D];西北大学;2006年
• 和彦莉;基于图编辑距离的画像识别[D];西安电子科技大学;2010年
• 齐彩霞;基于图编辑距离的图匹配算法研究[D];西安建筑科技大学;2013年
• 宋建昌;基于图编辑距离的自然景物识别[D];北京工业大学;2013年
• 高宇;编辑距离及其在Penna模型中的应用[D];大连理工大学;2007年
• 汪贤龙;基于编辑距离的文本零水印算法研究[D];兰州大学;2013年
• 严铭清;双排序互关联后继树模型的若干应用研究[D];复旦大学;2008年
• 曹海;基于编辑距离的字符串相似连接的研究[D];哈尔滨工业大学;2012年
• 左新强;时间序列的相似性查找方法研究[D];清华大学;2007年

【稿件标题】：基于改进编辑距离的字符串相似度求解算法
【作者单位】：东北师范大学计算机科学与信息技术学院;东北师范大学智能信息处理吉林省高校重点实验室;
【发表期刊期数】：《计算机工程》2014年01期
【期刊简介】：《计算机工程》杂志是由中华人民共和国新闻出版总署、正式批准公开发行的优秀期刊，计算机工程杂志具有正规的双刊号，其中国内统一刊号：CN31-1289/TP，国际刊号：ISSN1000-3428。计算机工程杂志社由中国电子科技集团公司主管、主办，本刊为月刊。自创刊以来......更多计算机工程杂志社(http://www.400qikan.com/qk/6013/)投稿信息
【版权所有人】：姜华；韩安琪；王美佳；王峥；吴雲玲；

更多科技类论文详细信息: 基于改进编辑距离的字符串相似度求解算法 论文代写
http://m.400qikan.com/lw-16158 论文代发

相关专题：中南大学学报医学版 什么是同课异构