模式识别与人工智能
Friday, Apr. 4, 2025 Home      About Journal      Editorial Board      Instructions      Ethics Statement      Contact Us                   中文
  2011, Vol. 24 Issue (6): 816-824    DOI:
Orignal Article Current Issue| Next Issue| Archive| Adv Search |
Semantic Edit Distance between Two Directed Labeled and Rooted Trees
KANG Qi, MA Jun
School of Computer Science and Technology, Shandong University, Jinan 250101

Download: PDF (507 KB)   HTML (1 KB) 
Export: BibTeX | EndNote (RIS)      
Abstract  In graph theory, the tree edit distance (TED) between two directed labeled and rooted trees is a popular research issue. As a combination optimization problem, calculating TED is widely used in the detection of the structural similarity of semi-structural documents. In this paper, a concept named tree semantic edit distance (TSED) with the corresponding formula is proposed. Then a distance measure based on both TED and TSED is presented. The proposed distance is applied in clustering the document object model (DOM) trees of extensible markup language (XML) documents. Experimental results show the proposed measure is better than those used TED only in terms of clustering precision and recall. The time complexity of the proposed algorithm is the same as those of algorithms for TED based on dynamic programming.
Key wordsTree Edit Distance      Document Clustering      Structural Similarity      Semantic Similarity     
Received: 17 June 2010     
ZTFLH: TP391.4  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
KANG Qi
MA Jun
Cite this article:   
KANG Qi,MA Jun. Semantic Edit Distance between Two Directed Labeled and Rooted Trees[J]. , 2011, 24(6): 816-824.
URL:  
http://manu46.magtech.com.cn/Jweb_prai/EN/      OR     http://manu46.magtech.com.cn/Jweb_prai/EN/Y2011/V24/I6/816
Copyright © 2010 Editorial Office of Pattern Recognition and Artificial Intelligence
Address: No.350 Shushanhu Road, Hefei, Anhui Province, P.R. China Tel: 0551-65591176 Fax:0551-65591176 Email: bjb@iim.ac.cn
Supported by Beijing Magtech  Email:support@magtech.com.cn