导读:本文包含了树编辑距离论文开题报告文献综述及选题提纲参考文献，主要关键词:Zhang-shasha算法,等高线树,拓扑相似性,相似性度量
树编辑距离论文文献综述
郭文月,刘海砚,孙群,余岸竹,季晓林[1]（2019）在《利用树编辑距离的等高线拓扑相似性度量方法》一文中研究指出已有的拓扑相似性度量方法主要通过目标之间拓扑关系统计均值的差值,衡量目标之间的拓扑相似程度,在拓扑变化复杂区域由于拓扑关系的增减互补易产生度量误差。为此,提出一种顾及拓扑结构差异的等高线群拓扑相似性度量方法;引入Zhang-shasha算法将等高线群之间的拓扑变化转化为等高线树之间的转换编辑操作;构建基于树结构的拓扑差异表达;并利用动态规划方法求解等高线树之间的转换编辑距离;进而量化度量等高线群间的拓扑结构相似度。模拟数据实验和真实数据实验表明,该方法顾及了拓扑结构差异,能够有效度量多源多尺度等高线数据之间的拓扑相似程度,减少度量误差。(本文来源于《测绘科学技术学报》期刊2019年01期）
刘晓波[2]（2015）在《基于树编辑距离的网页信息抽取》一文中研究指出近年来,随着国际互联网的高速发展,电子商务行业得到极大扩展,国内的天猫、京东网以及亚马逊网的发展更为突出显着。电子商务网站的网页往往对商品的信息进行了描述,多数网页都提供用户查询的接口,并通过数据库将数据以列表的方式呈现于网页,这令从网页中抽取大量半结构化商品记录信息、整合成结构化信息并应用成为可能。本文介绍了信息抽取技术的发展历程和国内外现状,阐述了在这一段时间内出现的比较经典的算法,分析了它们的基本思想、优点和不足。现有的信息抽取方法在定位主数据区域方面存在很多问题,本文针对这些问题提出了新的分离数据记录的方法,以便于数据的集成和其它的增值服务。该方法主要包含两个步骤:(1)定位主数据区域;(2)分离数据记录。在第一步中,利用启发式规则和视觉信息相结合的方法,寻找包含所有相似数据记录子树的公共根节点。第二步,提出了一种新的方案,改进了树编辑距离算法,结合自上而下的凝聚型聚类算法将网页中的数据记录分类,缩小数据记录属性的可能组合方式的数量。在此过程中,提出了树编辑距离的计算公式,利用它来量化树与树之间的相似度。分别计算各个组合方案的平均相似度,取具有最高平均值的方案作为最佳方案。最后,针对需要抽取的数据记录属性在某些情况下会有缺失的问题,采用了星序列比对算法来补全缺失的属性,抽取初始选定属性的数据作为最终结果。通过对电子商务网站中具有大量列表的网页进行实验,结果表明,本文方法具有较好的查全率和查准率。(本文来源于《中国石油大学(华东)》期刊2015-05-01）
韦龙宝[3]（2015）在《Tai树编辑距离算法的存储优化与树的纵向归并算法》一文中研究指出针对Tai树编辑距离算法空间复杂度太高的问题,运用数据分层次存储和数据筛选方法,提出了存储优化算法,可以使原本为O(V*V'*L2*L'2)的空间复杂度降为O(V*V'*L*L'),其中V和V’分别为两棵树的节点数,L和L’分别为两棵树的最大深度。改进后的算法,比原来的算法更节约存储空间和运算时间。此外,当树的节点数很大而导致内存不足时,给出了序列化的解决方案。针对Tai和Zhang & Shasha的树编辑距离算法在计算解析树深度较大的XML文本的相似度时,时间复杂度太高的问题,提出了树纵向归并算法。基于纵向归并算法,可使Tai树编辑距离算法时间复杂度从O(V*V'*L2*L'2)降为O(V*V’),可使Zhang & Shasha树编辑距离算法时间复杂度从O(V*V'*min(L,leaves(T1))*min(L',leaves(T2)))也降为O(V*V’)。其中leaves(T1)和leaves(T2)分别为两棵树的叶子节点数。(本文来源于《中国工程物理研究院》期刊2015-04-09）
宫丽娜,祝美莲[4]（2013）在《基于树编辑距离的聚类算法数据记录抽取》一文中研究指出本文研究了如何从列表页面中抽取数据记录.系统分为两个阶段:第一步采用叁种启发式方法相结合的方法,识别主数据区域的根节点;第二步将数据记录分离,提出了一种新的基于树编辑距离的聚类算法,来减少候选分割方案的数量,然后根据公式计算相似度,找出最佳分割方案.本文通过对大量不同领域的网页进行测试,结果表明本文方法具有较高的准确率.(本文来源于《赤峰学院学报(自然科学版)》期刊2013年12期）
贾楠[5]（2013）在《基于树编辑距离的工作流聚类应用研究》一文中研究指出工作流是一种反映业务流程的计算机化的模型,在办公自动化系统、电子政务系统、企业经营等领域中都起到了举足轻重的作用,能够帮助企业实现业务过程建模、业务过程优化等。随着工作流的广泛应用,出现了大量的工作流模型库,库中的工作流模型随着现实需求的变动而不断地被更新,并且新的工作流模型在不断加入,因此一个能系统的分析和改进工作流的方法就变得十分重要。近年来,许多学者开始关注工作流的发现和聚类。工作流聚类是将物理或抽象工作流集合分组成为由类似的工作流分成的多个簇的过程。引入工作流聚类,我们可以快速、准确的对工作流库中的模型进行查找和分析,提高工作效率。由于不同的工作流间结构互不相同,表达的内容也不相同,因此需要找到一个适用于工作流聚类的理论和方法,以满足业务的需要。本文的主要工作就是根据工作流结构性强、语义内容丰富的特点提出了一个新的工作流距离度量方法,并在此方法基础上进行工作流聚类。首先本文提出一种基于树编辑距离的工作流距离度量方法。在这种方法中,将每一个结构化工作流转化为一个流程结构树,利用树编缉距离和WordNet语义距离进行求解。基于结构树的工作流距离度量方法将工作流的结构和语义统一考虑,保证了距离的有效性和准确性。然后,采用层次聚类的方法对工作流模型库中的工作流进行聚类。层次聚类简单易用,而且对于输入记录的顺序不敏感,使用范围较广。最后,本文完成一个支持工作流聚类的原型系统,该系统采用C/S结构,使用Java语言和JBPM规范实现。系统由用户选择需要聚类的工作流集合,支持批量导入工作流,同时,由用户决定聚类的集合数,可以有效实现工作流聚类功能。通过实验证实,本文的提出的基于树编辑距离的工作流距离度量方法是可行、有效的,将其应用于工作流聚类活动中时,可以准确地得到符合用户需求的聚类集合,并且可以广泛应用于流程重构等领域。(本文来源于《昆明理工大学》期刊2013-03-01）
贾楠,付晓东,黄袁,刘晓燕,代志华[6]（2012）在《基于树编辑距离的工作流距离度量方法》一文中研究指出在工作流的发现和聚类等应用中,需要对两个工作流模型的距离进行度量。因此,提出一种计算两个不同结构化工作流的距离定量度量方法。首先介绍了结构化工作流,并将每一个结构化工作流转换为流程结构树;然后基于两个结构树之间的树编辑距离来计算工作流之间的距离及相应相似度。该距离度量方法满足距离度量的3个属性,即同实体不可区分性、对称性和叁角不等式性质。这些属性使得该距离度量方法可以在工作流模型管理活动中作为定量分析工具。实验结果表明,基于树编辑距离的工作流度量方法是可行的。同时,与基于邻接矩阵的距离度量方法相比,该方法考虑了不同结构之间的语义距离,有效验证了此方法的合理性。(本文来源于《计算机应用》期刊2012年12期）
李玉鉴,张晨光[7]（2011）在《满足度量性质的归一化树编辑距离》一文中研究指出利用树大小和树编辑距离的简单函数提出了一种归一化树编辑距离,在权重函数具有度量性质且所有插入和删除操作的权重都相等时,不仅能完全满足叁角不等式,而且是一种取值在[0,1]的度量.这种距离可以由树编辑距离直接计算得到,其计算时间复杂度与树编辑距离相同.通过手写数字识别实验说明,AESA算法利用该距离获得的识别率为91.6%,比其他2种归一化树编辑距离分别高0.2%和0.8%.(本文来源于《北京工业大学学报》期刊2011年04期）
聂卉,黄贵鹏[8]（2010）在《树编辑距离在Web信息抽取中的应用与实现》一文中研究指出引入编辑距离的概念,探讨如何构造标签树,并利用标签树匹配算法来量化网页结构相似度。该算法被应用于Web信息抽取,通过URL相似度算法进行样本网页的粗聚类,进一步采用树的相似度匹配算法实现细聚类,从而获取模板网页。在模板网页的基础上,再次引入结构相似度算法并结合基于模板网页的抽取规则实现网页的自动化抽取。实验证明,该算法的引入能够有效提高包装器的抽取精度和半自动化能力。(本文来源于《现代图书情报技术》期刊2010年05期）
朱南丽,朱晓鸣,叶五梅[9]（2010）在《Web信息抽取中基于结点权重的树编辑距离匹配法研究》一文中研究指出提出一种改进的树匹配算法,通过考量HTML特性,对树编辑距离方法进行改进,根据不同HTML树结点在浏览器中所显示的相关数据的不同权重赋以不同的权重值。算法由HTML数据对象构造具有结点权重的HTML树,模式识别通过取得两棵构造树的最大映射值达成。通过基于商用网站的实验对算法有效性进行了证实。(本文来源于《计算机时代》期刊2010年03期）
姜波,丁岳伟[10]（2009）在《基于约束树编辑距离与导航树的信息采集》一文中研究指出介绍基于网站和网页结构的信息采集算法,提出一种基于约束树编辑距离的导航树算法。该算法通过提取网页的HTML的重要标记生成网页结构的标签树,对网页进行结构分析,通过约束树编辑距离算法判断爬行到的网页与主题的相关性,并根据网站基于URL的拓扑结构,提出基于导航树的信息采集约束信息采集器的爬行路径,提高了目标页面采集的效率和准确率。(本文来源于《计算机工程》期刊2009年14期）
树编辑距离论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
近年来,随着国际互联网的高速发展,电子商务行业得到极大扩展,国内的天猫、京东网以及亚马逊网的发展更为突出显着。电子商务网站的网页往往对商品的信息进行了描述,多数网页都提供用户查询的接口,并通过数据库将数据以列表的方式呈现于网页,这令从网页中抽取大量半结构化商品记录信息、整合成结构化信息并应用成为可能。本文介绍了信息抽取技术的发展历程和国内外现状,阐述了在这一段时间内出现的比较经典的算法,分析了它们的基本思想、优点和不足。现有的信息抽取方法在定位主数据区域方面存在很多问题,本文针对这些问题提出了新的分离数据记录的方法,以便于数据的集成和其它的增值服务。该方法主要包含两个步骤:(1)定位主数据区域;(2)分离数据记录。在第一步中,利用启发式规则和视觉信息相结合的方法,寻找包含所有相似数据记录子树的公共根节点。第二步,提出了一种新的方案,改进了树编辑距离算法,结合自上而下的凝聚型聚类算法将网页中的数据记录分类,缩小数据记录属性的可能组合方式的数量。在此过程中,提出了树编辑距离的计算公式,利用它来量化树与树之间的相似度。分别计算各个组合方案的平均相似度,取具有最高平均值的方案作为最佳方案。最后,针对需要抽取的数据记录属性在某些情况下会有缺失的问题,采用了星序列比对算法来补全缺失的属性,抽取初始选定属性的数据作为最终结果。通过对电子商务网站中具有大量列表的网页进行实验,结果表明,本文方法具有较好的查全率和查准率。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
树编辑距离论文参考文献
[1].郭文月,刘海砚,孙群,余岸竹,季晓林.利用树编辑距离的等高线拓扑相似性度量方法[J].测绘科学技术学报.2019
[2].刘晓波.基于树编辑距离的网页信息抽取[D].中国石油大学(华东).2015
[3].韦龙宝.Tai树编辑距离算法的存储优化与树的纵向归并算法[D].中国工程物理研究院.2015
[4].宫丽娜,祝美莲.基于树编辑距离的聚类算法数据记录抽取[J].赤峰学院学报(自然科学版).2013
[5].贾楠.基于树编辑距离的工作流聚类应用研究[D].昆明理工大学.2013
[6].贾楠,付晓东,黄袁,刘晓燕,代志华.基于树编辑距离的工作流距离度量方法[J].计算机应用.2012
[7].李玉鉴,张晨光.满足度量性质的归一化树编辑距离[J].北京工业大学学报.2011
[8].聂卉,黄贵鹏.树编辑距离在Web信息抽取中的应用与实现[J].现代图书情报技术.2010
[9].朱南丽,朱晓鸣,叶五梅.Web信息抽取中基于结点权重的树编辑距离匹配法研究[J].计算机时代.2010
[10].姜波,丁岳伟.基于约束树编辑距离与导航树的信息采集[J].计算机工程.2009
标签：Zhang-shasha算法; 等高线树; 拓扑相似性; 相似性度量;