论文摘要
图作为一种灵活且应用范围广的数据模型,可以有效表示生物医学、社交网络、模式识别等各种领域中的复杂数据。图编辑距离用于度量两个图之间的结构相似性,在解决图查询等实际应用问题时有广泛的应用场景。然而,现有的图编辑距离计算方法存在NP难的时间复杂度,因而处理效率异常低下。本文针对图编辑距离的计算问题进行研究,具体内容如下。首先,针对基本算法时间和空间代价较高的问题,提出了基于层级映射的图编辑距离计算方法。该方法根据扩展进度对大量中间结果进行层级存储,解决了当优先队列规模增大时效率急速下降的问题,加速了查找合适执行策略和扩展的过程。同时,通过加速初始阶段最优代价的生成过程,提高了图编辑距离计算的效率。其次,提出了新的基于邻接半边估计的代价函数。该函数用边抽离策略计算已遍历的实际代价,实现了对边处理过程的简化;用预存储的状态数据来分析并加速预估代价的计算。和基于层级映射的图编辑距离计算方法相结合,进一步提升了图编辑距离的计算速度。最后,本文采用与化学结构相关的真实数据集,从处理数据图的规模、映射扩展耗时、映射数量等方面进行比较,实验结果验证了本文所提出的图编辑距离计算的高效性。
论文目录
文章来源
类型: 硕士论文
作者: 李凯
导师: 周军锋
关键词: 图编辑距离,星算法,映射,代价函数
来源: 燕山大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 燕山大学
分类号: O157.5
DOI: 10.27440/d.cnki.gysdu.2019.000343
总页数: 56
文件大小: 2288K
下载量: 36
相关论文文献
- [1].侗台语族语言的编辑距离分类[J]. 计算机工程与应用 2018(19)
- [2].图编辑距离概述[J]. 计算机科学 2018(04)
- [3].基于中文文本的编辑距离算法的改进[J]. 青岛大学学报(自然科学版) 2017(03)
- [4].一种新颖的编辑距离限制下的相似性确认算法[J]. 东北大学学报(自然科学版) 2019(11)
- [5].基于自动纠错的最小编辑距离优化算法[J]. 网络安全技术与应用 2019(12)
- [6].基于编辑距离的序列聚类算法的优化[J]. 计算机技术与发展 2018(03)
- [7].融合音素串编辑距离的随机段模型解码算法[J]. 计算机工程与应用 2015(06)
- [8].满足度量性质的归一化树编辑距离[J]. 北京工业大学学报 2011(04)
- [9].基于改进编辑距离和依存文法的汉语句子相似度计算[J]. 计算机应用与软件 2008(07)
- [10].编辑距离在语言分类研究中的应用[J]. 现代语文 2018(05)
- [11].基于树编辑距离的聚类算法数据记录抽取[J]. 赤峰学院学报(自然科学版) 2013(12)
- [12].有向标记根树之间的语义编辑距离[J]. 模式识别与人工智能 2011(06)
- [13].基于异或编辑距离算法的航班号相似度研究[J]. 湘潭大学自然科学学报 2015(02)
- [14].编辑距离与语言分类[J]. 宁波大学学报(人文科学版) 2018(05)
- [15].基于变迁图编辑距离的流程相似性算法[J]. 计算机应用研究 2020(04)
- [16].基于图编辑距离的恶意代码检测[J]. 武汉大学学报(理学版) 2013(05)
- [17].编辑距离算法在中文文本相似度计算中的优化与实现[J]. 韶关学院学报 2015(12)
- [18].一种度量图像相似性和计算图编辑距离的新方法[J]. 电子学报 2009(10)
- [19].支持块编辑距离的索引结构[J]. 计算机研究与发展 2010(01)
- [20].基于编辑距离相似度的文本校验技术研究与应用[J]. 飞行器测控学报 2015(04)
- [21].基于约束树编辑距离与导航树的信息采集[J]. 计算机工程 2009(14)
- [22].基于改进编辑距离算法的保护装置测试模板开发[J]. 广东电力 2018(10)
- [23].基于权重编辑距离的XML查询[J]. 兰州交通大学学报 2010(03)
- [24].Web信息抽取中基于结点权重的树编辑距离匹配法研究[J]. 计算机时代 2010(03)
- [25].编辑距离的数控机床故障诊断案例推理方法[J]. 中国工程机械学报 2017(04)
- [26].基于字符串编辑距离的图像检索算法[J]. 信息通信 2015(07)
- [27].LCS算法与编辑距离算法的研究[J]. 信息通信 2015(05)
- [28].基于自适应编辑距离的颜料光谱匹配识别方法[J]. 激光与光电子学进展 2018(11)
- [29].一种节点加权的相似重复XML数据检测算法[J]. 计算机光盘软件与应用 2014(02)
- [30].一种新的手写体数字识别方法[J]. 科技信息(学术研究) 2008(25)