本体演化的波及效应计算优化研究  

Improved method for ripple effect calculation in ontology evolution

作　　者：陈晶 刘钊[1,2] 顾进广[1,2,3,4] 刘宇[1,2,3,4] Chen Jing;Liu Zhao;Gu Jinguang;Liu Yu(School of Computer Science&Technology,Wuhan University of Science&Technology,Wuhan 430065,China;Key Laboratory of Intelligent Information Processing&Real-time Industrial System in Hubei Province,Wuhan University of Science&Technology,Wuhan 430065,China;Institute of Big Data Science&Engineering,Wuhan University of Science&Technology,Wuhan 430065,China;Key Laboratory of Rich-media Knowledge Organization&Service of Digital Publishing Content,National Press&Publication Administration,Beijing 100038,China)

机构地区：[1]武汉科技大学计算机科学与技术学院,武汉430065 [2]武汉科技大学智能信息处理与实时工业系统湖北省重点实验室,武汉430065 [3]武汉科技大学大数据科学与工程研究院,武汉430065 [4]国家新闻出版署富媒体数字出版内容组织与知识服务重点实验室,北京100038

出　　处：《计算机应用研究》2020年第8期2366-2370,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61673304);国家社会科学基金重大计划资助项目(11&ZD189)。

摘　　要：鉴于使用Floyd-Warshall算法对规模较大的本体评估具有时间复杂度与空间复杂度较高且未考虑本体演化过程中各版本之间的关联,提出基于邻接表的SPFA(shortest path faster algorithm)优化波及效应的计算。该算法不仅在大规模本体计算中具有计算效率的优势,而且可以简化版本迭代过程中波及效应的计算过程。实验结果表明,使用SPFA在计算本体的波及效应相比于基于邻接矩阵的方式具有一定的时间优势,并且这种优势随着时间的变化逐渐增加;在本体演化的波及效应计算时间中,本体演化后版本的计算时间大约与原有方法相差较少,证明了优化计算的有效性。In view of the use of Floyd-Warshall algorithm,the large-scale ontology evaluation had higher time complexity and higher space complexity and didn’t consider the association between versions in the ontology evolution process,this paper proposed the calculation of the ripple effect optimized by the SPFA(shortest path faster algorithm) algorithm based on the adjacency list.The algorithm not only had the advantage of computational efficiency in large-scale ontology calculation,but also could simplify the calculation process of the ripple effect in the iterative process.The experimental results show that the SPFA has a certain time advantage in calculating the ontology ripple effect compared with the adjacency matrix based method,and this advantage gradually increases with time.In the ontology evolution ripple effect calculation time,the calculation time of the evolved version is about the original method,which proves the effectiveness of the optimization calculation.

关 键 词：本体演化 波及效应 SPFA 邻接表 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]