Metric Normalized Tree Edit Distance

LI Yu-jian; ZHANG Chen-guang

Journal of Beijing University of Technology > 2011 > 37(4): 576-582.

LI Yu-jian, ZHANG Chen-guang. Metric Normalized Tree Edit Distance[J]. Journal of Beijing University of Technology, 2011, 37(4): 576-582.

Citation:

LI Yu-jian, ZHANG Chen-guang. Metric Normalized Tree Edit Distance[J]. Journal of Beijing University of Technology, 2011, 37(4): 576-582.

Citation:

LI Yu-jian, ZHANG Chen-guang. Metric Normalized Tree Edit Distance[J]. Journal of Beijing University of Technology, 2011, 37(4): 576-582.

PDF (522 KB)

Metric Normalized Tree Edit Distance

College of Computer Science, Beijing University of Technology, Beijing 100124, China

More Information

Received Date: March 03, 2009
Available Online: November 18, 2022

Graphical Abstract

Abstract

Abstract

Using a simple function of the sizes of two trees and the edit distance between them,this paper presents a normalized tree edit distance,which not only satisfies the triangle inequality,but also is a genuine metric valued in [0,1] under the condition that the weight function is a metric over the set of elementary edit operations with all costs of insertions/deletions of the same weight.Moreover,the distance can be directly computed through tree edit distances and it has the same computing time complexity with the tree edit distance.Handwritten digits recognition experiments show that the metric normalization can reach 91.6%,which is 0.2% and 0.8% better than that of the other two existing methods respectively when the AESA is used.
- metric,
- tree edit distance,
- triangle inequality,
- approximating and eliminating search algorithm (AESA)

FullText(HTML)

References (17)

References

[1]	ZHANG K, SHASHA D, WANG J T L. Approximate tree matching in the presence of variable length don't cares [J]. J Algorithms, 1994, 16(1): 33- 66.
[2]	TAI Kuo-chung. The tree-to-tree correction problem[J]. J ACM, 1979, 26: 422- 433.
[3]	ZHANG K, SHASHA D. Simple fast algorithms for the editing distance between trees and related problems [J]. SIAM J Comput, 1989, 18: 1245- 1262.
[4]	KILPELINEN P,MANNILA H.Ordered and unordered tree inclusion[J].SIAM J Comput,1995,24:340-356.
[5]	KLEIN P, TIRTHAPURA S, SHARVIT D, et al. A tree-edit-distance algorithm for comparing simple, closed shapes[J]. Proceedings of 11th Annuat ACM-SIAM Symp on Discrete Algorithms (SODA). New York: ACM & SIAM, 2000: 696- 704.
[6]	HOFFMANNC M, O'DONELL M J. Pattern matching in trees[J]. J ACM, 1982, 29(1): 68- 95.
[7]	RAMESH R, RAMAKRISHNAN I V. Nonlinear pattern matching in trees[J]. J ACM, 1992, 39(2): 295- 316.
[8]	BILLE P. A survey on tree edit distance and related problems[J]. Theoretical Computer Science, 2005, 337: 217- 239.
[9]	LEVENSHTEIN A. Binary codes capable of correcting deletions, insertions and reversals[J]. Soviet Physics Doklady, 1966, 10(8): 707- 710.
[10]	SELLERS P H. On the theory and computation of evolutionary distances[J]. SIAM J Applied Math, 1974, 26(4): 787- 793.
[11]	WAGNERR A, FISCHER M J. The string-to-string correction problemp[J]. J ACM, 1974, 21(1): 168- 173.
[12]	MARZAL A, VIDAL E. Computation of normalized edit distance and applications[J]. IEEE Trans Pattern Analysis and Machine Intelligence, 1993, 15(9): 926- 932.
[13]	LI Yu-jian, LIU Bo. A normalized levenshtein distance metric[J]. IEEE Trans Pattern Analysis and Machine Intelligence, 2007, 29(6): 1091- 1095.
[14]	SCHROEDER M, SCHWEIMEIER R. Argument and misunderstandings: fuzzy unification for negotiating agents[J]. Electronic Notes in Theoretical Computer Science, 2002, 5: 1- 19.
[15]	JUAN Ramon Rico-juan, MICO L. Comparison of AESA and LAESA search algorithms using string and tree-edit-distance[J]. Pattern Recognition Letters, 2003, 24: 1417- 1426.
[16]	LECUN Y, BOTTOU L, BEGIO Y, et al. Gradient-based learning applied to document recognition [J]. Proceedings of the IEEE, 1998, 86(11): 2278- 2324.
[17]	CARRASCO R C, FORCADA M L. A note on the Nagen-draprasad-Wang-Gupta thining algorithm[J]. Pattern Recognition Letters, 1995, 16: 539- 541.

Cited By

Get Citation

PDF

XML

Article views (32) PDF downloads (11)

Turn off MathJax

Article Contents

Abstract

References

Metric Normalized Tree Edit Distance

Abstract

References

Catalog

Export File

Citation

Format

Content