基于A星的图编辑距离计算研究

基于A星的图编辑距离计算研究

论文摘要

图作为一种灵活且应用范围广的数据模型,可以有效表示生物医学、社交网络、模式识别等各种领域中的复杂数据。图编辑距离用于度量两个图之间的结构相似性,在解决图查询等实际应用问题时有广泛的应用场景。然而,现有的图编辑距离计算方法存在NP难的时间复杂度,因而处理效率异常低下。本文针对图编辑距离的计算问题进行研究,具体内容如下。首先,针对基本算法时间和空间代价较高的问题,提出了基于层级映射的图编辑距离计算方法。该方法根据扩展进度对大量中间结果进行层级存储,解决了当优先队列规模增大时效率急速下降的问题,加速了查找合适执行策略和扩展的过程。同时,通过加速初始阶段最优代价的生成过程,提高了图编辑距离计算的效率。其次,提出了新的基于邻接半边估计的代价函数。该函数用边抽离策略计算已遍历的实际代价,实现了对边处理过程的简化;用预存储的状态数据来分析并加速预估代价的计算。和基于层级映射的图编辑距离计算方法相结合,进一步提升了图编辑距离的计算速度。最后,本文采用与化学结构相关的真实数据集,从处理数据图的规模、映射扩展耗时、映射数量等方面进行比较,实验结果验证了本文所提出的图编辑距离计算的高效性。

论文目录

  • 摘要
  • Abstract
  • 第1章 绪论
  •   1.1 研究背景
  •   1.2 研究现状
  •   1.3 研究内容
  •   1.4 组织结构
  • 第2章 基础知识概述
  •   2.1 图编辑距离相关概念
  •   2.2 A星算法思想
  •   2.3 基于A星的GED基本算法
  •     2.3.1 图顶点遍历序列
  •     2.3.2 映射与代价函数
  •     2.3.3 最优代价值映射
  •   2.4 本章小结
  • 第3章 基于层级映射的GED算法
  •   3.1 问题分析
  •   3.2 层级映射基本思想
  •   3.3 算法描述
  •     3.3.1 基准顶点序列
  •     3.3.2 层级映射存储
  •   3.4 算法分析
  •   3.5 本章小结
  • 第4章 基于邻接半边估计的GED算法
  •   4.1 问题分析
  •   4.2 邻接半边估计基本思想
  •   4.3 算法描述
  •     4.3.1 实际代价边抽离
  •     4.3.2 映射状态预存储
  •     4.3.3 估计代价值计算
  •   4.4 算法分析
  •   4.5 本章小结
  • 第5章 实验结果与分析
  •   5.1 实验介绍
  •   5.2 实验环境
  •     5.2.1 软硬件配置
  •     5.2.2 数据集
  •     5.2.3 测评指标
  •   5.3 性能比较与分析
  •     5.3.1 扩展过滤效果
  •     5.3.2 映射处理数量
  •     5.3.3 标签数量影响
  •     5.3.4 算法整体性能
  •   5.4 本章小结
  • 结论
  • 参考文献
  • 攻读硕士学位期间承担的科研任务与主要成果
  • 致谢
  • 文章来源

    类型: 硕士论文

    作者: 李凯

    导师: 周军锋

    关键词: 图编辑距离,星算法,映射,代价函数

    来源: 燕山大学

    年度: 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)

    标签:;  ;  ;  ;  

    基于A星的图编辑距离计算研究
    下载Doc文档

    猜你喜欢