个性化信息服务通过了解用户的兴趣爱好,为不同的用户提供不同的信息服务。XML是一种标示语言,是Web文档表示和交换的常用相关标准,因此XML文档之间相似度计算问题对于个性化推荐与信息检索非常重要,为此提出了一个计算XML文档之间的语义和结构相似度的方法XMLSim。首先,基于节点标记对之间的语义相似度和编辑距离计算节点标记对之间的相似度;在分析了路径上节点具有的偏序关系之后,将路径之间相似度问题抽象为最大相似子序列(MSS,Maximal Similar Subsequence)问题,并利用动态规划对MSS问题求解得到路径相似度NpathSim。最后,XML文档之间的相似度XMLSim通过路径集合之间的最大NPathSim的平均值得到。
Abstract
XML is a markup language that has emerged as the most relevant standardization effort for document representation and exchange on the Web. Similarity measure for XML documents plays important role in personalized recommendations and information retrieval. A novel approach to compute semantic and structural similarity between XML documents, XMLSim, is proposed in this paper. Firstly, a similarity between node tags is created based on semantic similarity and string similarity. After analyzing partial relationship among node tags, the path similarity is abstracted as Maximal Similar Subsequence (MSS) problem. The result of NPathSim is obtained by the solution of MSS with dynamic programming. Finally, XMLSim is the average of the best NPathSim value among path sets.
Key wordsXML similarity; dynamic programming; semantics and structure
关键词
XML相似度 /
动态规划 /
语义和结构
{{custom_keyword}} /
Key words
XML similarity /
dynamic programming /
semantics and structure
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 郑仕辉, 周傲英, 张龙. XML文档的相似测度和结构索引研究[J]. 计算机学报, 2003, (9) : 1116-1122.
[2] Zhang K, Statman R, Shasha D. On the editing distance between unordered labeled trees[J]. Information Processing Letters. 1992, 42(3): 133-139.
[3] Nierman A, Jagadish H V. Evaluating Structural Simi-larity in XML Documents[DB/OL]. 2002, citeseerx.ist.psu.edu,61-66.
[4] Nayak R. Investigating Semantic Measures in XML Clustering[C]//Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence, 2006: 1042-1045.
[5] Joshi S, Agrawal N, Krishnapuram R, et al. A bag of paths model for measuring structural similarity in Web documents[C]//Proceedings of Knowledge Discovery and Data Mining. Washington, D.C., ACM Press, 2003: 577-582.
[6] Nayak R, Iryadi W. XML schema clustering with semantic and hierarchical similarity measures[J]. Knowledge-Based Systems. 2007, 20(4): 336-349.
[7] 赵嫣, 马军, 李森. 一种计算结构化文档相关度的方法[C]//第二届中国分类技术及应用学术会议.郑州: 20070527. 350-355.
[8] Jeong B, Lee D, Cho H, et al. A novel method for measuring semantic similarity for XML schema match-ing[J]. Expert Systems with Applications. 2008, 34(3): 1651-1658.
[9] Levenshtein V. Binary codes capable of correcting deletions, insertions, and reversals[J]. Soviet Physics Doklady. 1966, 10(8): 707-710.
[10] Princeton University. WordNet[DB/OL]. 2011, http://wordnet.princeton.edu/.
[11] Ling Song, Jun Ma, Jingsheng Lei, et al. A Fuzzy Approach for Measuring the Semantic Similarity Between words in WordNet[J]. Journal of Information & Computational Science,2009,6(3): 1673-1680.
[12] Song Ling, Ma Jun, Lian Li, et al. Fuzzy Similarity from Conceptual Relations[C]//Proceedings of 2006 Asia-Pacific Services Computing Conference,2006: 3-10.
[13] Alexander R. Vinson,Carlos A. Heuser, Altigran S. da Silva, et al. An Approach to XML Path Matching. Workshop On Web Information And Data Mana-gement[C]//Proceedings of the 9th annual ACM international workshop on Web information and data management. SESSION: XML and semi-structured data,2007:17-24.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金资助项目(61170052); 山东省高等教育学会“十二五”高等教育科学研究课题(YBKT2011063); 山东建筑大学博士基金(XNBS1028)
{{custom_fund}}
PDF(900 KB)
