用带权重的pq-gram算法计算XML文档相似度

doi:10.3969/j.issn.1006-2475.2015.03.005

计算机与现代化

用带权重的pq-gram算法计算XML文档相似度

南京航空航天大学计算机科学与技术学院，江苏南京210016

收稿日期:2014-11-20 出版日期:2015-03-23 发布日期:2015-03-26
作者简介:王成勇(1989-),男,山东临沂人,南京航空航天大学计算机科学与技术学院硕士研究生,研究方向:数据挖掘; 杜庆伟(1974-),男,河南郑州人,副教授,硕士生导师,博士,研究方向:计算机网络; 孙静(1981-),女,甘肃山丹人,硕士研究生,研究方向:计算机网络; 孙振(1982-),男,山东济南人,研究方向:卫星通信。
基金资助:
国家自然科学基金资助项目(61202350)

Calculating Similarity of XML Documents by Weighted Pq-gram Algorithm

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Received:2014-11-20 Online:2015-03-23 Published:2015-03-26

摘要/Abstract

摘要： XML文档聚类是高效管理XML文档的重要手段，XML文档相似度计算正是其中的关键步骤。pq-gram算法是解决XML文档相似度计算问题的有效手段，但忽略了XML文档结点的有序性。带权重的pq-gram算法是在此基础上，依据XML文档的结构性，首先为结点赋予相应权重，然后基于结点的权重对pq-gram赋予权重，最后将设定的权重应用到XML文档相似度计算中。实验结果表明，带权重的pq-gram算法更好地描述结点在XML文档相似度计算中的贡献度，提高了XML文档相似度计算的精度。

关键词: XML文档, 计算相似度, pq-gram, 权重

Abstract: Clustering for XML documents is an important method for efficiently managing XML documents, and calculating similarity of XML documents is the pivotal step. Pq-gram algorithm is an efficient method to solve the problem of calculating similarity of XML documents. However, it ignores that the nodes of XML documents are ordered. Based on the pq-gram algorithm, weighted pq-gram algorithm, in accordance with the structural characteristics of XML documents, sets weight for nodes, and sets weight for pq-grams based on the weight of nodes, then applies the weight to the method of calculating similarity of XML documents. Experimental results show that the weighted pq-gram algorithm describes the contribution of nodes better in the process of calculating similarity of XML documents, and improves the precision of calculating of XML documents.

Key words: XML documents, calculate similarity, pq-gram, weight

中图分类号:

TP391

王成勇，杜庆伟，孙静，孙振. 用带权重的pq-gram算法计算XML文档相似度[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2015.03.005.

WANG Cheng-yong, DU Qing-wei, SUN Jing, SUN Zhen. Calculating Similarity of XML Documents by Weighted Pq-gram Algorithm[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2015.03.005.

参考文献

［1]Algergawy A, Mesiti M, Nayak R, et al. XML data clustering: An overview［J]. ACM Computing Surveys, 2011,43(4):Article No. 25.
［2]Tai K C. The tree-to-tree correction problem［J]. Journal of the ACM, 1979,6(3):422-433.
［3]Zhang Kaizhong, Statman R, Shasha D. On the editing distance between unordered labeled trees［J]. Information Processing Letters, 1992,42(3):133-139.
［4]Zhang Kaizhong, Shasha D. Simple fast algorithms for the editing distance between trees and related problems［J]. SIAM Journal on Computing, 1989,18(6):1245-1262.
［5]Jiang Tao, Wang Lusheng, Zhang Kaizhong. Alignment of trees—an alternative to tree edit［J]. Theoretical Computer Science, 1995,143(1):137-148.
［6]Zhang Kaizhong. Algorithms for the constrained editing distance between ordered labeled trees and related problems［J]. Pattern Recognition, 1995,28(3):463-474.
［7]Guha S, Jagadish H V, Koudas N, et al. Approximate XML joins［C]// Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. 2002:287-298.
［8]Augsten N, Bhlen M, Gamper J. Approximate matching of hierarchical data using pq-grams［C]// Proceedings of the 31st International Conference on Very Large Data Bases. 2005:301-312.
［9]Augsten N, Bhlen M, Gamper J. The pq-gram distance between ordered labeled trees［J]. ACM Transactions on Database Systems, 2010,35(1):1-16.
［10]〖JP2〗Chawathe S S. Comparing hierarchical data in external memory［C]// Proceedings of the 25th International Conference on Very Large Data Bases. 1999:90-101.
［11]Tekli J, Chbeir R, Yetongnon K. An overview on XML similarity: Background, current trends and future directions［J]. Computer Science Review, 2009,3(3):151-173.
［12]Nierman A, Jagadish H V. Evaluating structural similarity in XML documents［C]// Proceedings of the 5th International Workshop on the Web and Database. 2002:61-66.
［13]Dalamagas T, Cheng T, Winkel K J, et al. A methodology for clustering XML documents by structure［J]. Information Systems, 2006,31(3):187-228.
［14]The DBLP Team. DBLP DataSet［DB/OL]. http://dblp.uni-trier.de/xml/, 2014-11-01.
［15]Association for Computing Machinery. Sidmod DataSet［DB/OL]. http://www.sigmod.org/publications/sigmod-record/1312, 2014-11-01.
［16]Expasy Website. UniProtKB/Swiss-Prot ［DB/OL]. http://us.expasy.org/sprot/, 2014-11-01.
［17]刘晨. XML文档聚类的研究［D]. 大连:大连理工大学, 2010.
［18]Posonia A M, Jyothi V L. Structural-based clustering technique of XML documents［C]// Proceedongs of the 2013 International Conference on Circuits, Power and Computing Technologies. 2013:1239-1242.

[1]	夏煌智, 陈丽敏, 毛雪迪, . 融入动态学习与高斯变异的自适应秃鹰搜索算法[J]. 计算机与现代化, 2024, 0(01): 117-126.
[2]	卢磊, 贺智明, 黄志成. 基于多策略改进的麻雀搜索算法[J]. 计算机与现代化, 2023, 0(10): 23-31.
[3]	雷依翰, 曹利峰, 韩孟达, 韩雪. 软件定义天地一体化网络安全切换架构与方法[J]. 计算机与现代化, 2023, 0(08): 119-126.
[4]	袁甜甜, 李志华, 邱阳. 基于辅助学习的改进端到端合成语音检测方法[J]. 计算机与现代化, 2023, 0(05): 52-57.
[5]	缪梓敬, 梅欣. 基于多词汇特征增强的中文事件检测方法[J]. 计算机与现代化, 2022, 0(09): 13-18.
[6]	李茹, 范冰冰. 基于混合策略改进的鲸鱼优化算法[J]. 计算机与现代化, 2022, 0(06): 13-20.
[7]	卢赛, 庄毅. 基于自适应专家权重的信息系统风险评估模型[J]. 计算机与现代化, 2021, 0(08): 85-93.
[8]	程凯强, 张旭, 寇旭鹏. 基于SSD的小目标检测改进算法[J]. 计算机与现代化, 2021, 0(07): 77-82.
[9]	樊志强, 曹江, 牛婵, 王丽婷. 一种基于Inf-ProA框架的能力满足度计算方法[J]. 计算机与现代化, 2021, 0(06): 12-17.
[10]	李锐, 李晓卉, 李小钰, 丁月民. 基于优化的非等间距灰色模型对健康的预测[J]. 计算机与现代化, 2020, 0(06): 101-.
[11]	曹帅帅，陈雪鑫，苗圃，卜庆凯. 基于PSO与K-均值聚类算法优化结合的图像分割方法[J]. 计算机与现代化, 2020, 0(01): 22-.
[12]	杨万里1,2，周雪婷1，陈孟娜1. 基于Logistic映射的新型混沌简化PSO算法[J]. 计算机与现代化, 2019, 0(12): 15-.
[13]	任静敏，潘大志. 带权重的贪心萤火虫算法求解0-1背包问题[J]. 计算机与现代化, 2019, 0(05): 86-.
[14]	陈宏伟，王万成，王继拓 . 混合自适应粒子群算法在电力经济调度中的应用[J]. 计算机与现代化, 2019, 0(03): 45-.
[15]	刘永洛1，王文强2，马立武2. 自适应权重CV模型在超声相控阵图像分割中的应用[J]. 计算机与现代化, 2019, 0(02): 37-.

用带权重的pq-gram算法计算XML文档相似度

Calculating Similarity of XML Documents by Weighted Pq-gram Algorithm

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价