Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems

By Kaizhong Zhang, Dennis E. Shasha. 1989

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Polyjuice: Generating Counterfactuals for Explaining, Evaluating, and Improving Models (2021, methodology): “As shown in Table 2, Polyjuice generates counterfactuals that are close to the original instance, measured by syntactic tree (Zhang and Shasha, 1989) and Levenshtein edit distance (Levenshtein, 1966).”
Does String-Based Neural MT Learn Source Syntax? (2016, methodology): “The zxx package4 to calculate Tree edit distance (TED) (Zhang and Shasha, 1989).”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “(2007) tackles the more complex variant of the tree edit distance (Zhang and Shasha, 1989), which allows the insertion and deletion of single nodes instead of entire subtrees only.”
A survey on tree edit distance and related problems (2005, methodology): “In particular, the problem of comparing trees occurs in several diverse areas such as computational biology, structured text databases, image analysis, automatic theorem proving, and compiler optimization [43,55,22,24,16,35,56].”
of the European Chapter of the Association for Computational Linguistics (2006, methodology): “RNA analysis) there is a high interest in methods to measure the similarity between trees (Tai, 1979; Zhang and Shasha, 1989; Klein, 1998; Chen, 2001; H¨ ochsmann et al., 2003).”
DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones (2007, background): “1More precisely, for two trees T1 andT2 the complexity isO(|T1| × |T2|×d1 × d2), where|Ti| is the size ofTi anddi is the minimum of the depth ofTi and the number of leaves of Ti [24].”
OCR-Free Document Understanding Transformer (2021, methodology): “We evaluate the models with two metrics; field-level F1 score [22,65,18] and Tree Edit Distance (TED) based accuracy [68,70,23].”
Global Explainability of BERT-Based Evaluation Metrics by Disentangling along Linguistic Factors (2021, methodology): “We normalized the TED to ensure comparability between sentences with different lengths (Zhang and Shasha, 1989).”
A content-driven reputation system for the wikipedia (2007, methodology): “For two versions v, v0, the edit distance d(v; v0) is a measure of how many word insertions, deletions, replacements, and displacements are required to change v into v0. Wikipedia pages contain markup, and possibly the most accurate way to measure edit distance would treat page versions as structure”
Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions (2010, background): “A popular method for such tasks is Tree Edit Distance (TED), which models sentence pairs by ﬁnding a low or minimal cost sequence of editing operations to transform a tree representation of one sentence (e.g., a dependency or phrase structure parse tree) into a tree for the other.”
X-Diff: an effective change detection algorithm for XML documents (2003, methodology): “Our X-Diff algorithm uses the notions of matching and editing distance, which are introduced in [ZS89](2), adding special criteria that apply to XML documents.”
A survey of graph edit distance (2010, background): “The edit distance between strings can be evaluated by dynamic programming [5], which has been extended to compare trees and graphs on a global level [22, 23].”
Automatic Cost Estimation for Tree Edit Distance Using Particle Swarm Optimization (2009, methodology): “This method was implemented by (Kouylekov and Magnini, 2005), based on TED algorithm (Zhang and Shasha, 1989).”
A Survey of Paraphrasing and Textual Entailment Methods (2009, background): “Another approach is to use no particular B (meaning postulates and common sense knowledge), and measure how difficult it is to satisfy both φT and φH , in the case of textual entailment recognition, compared to satisfying φT on its own.”
Recognition of Shapes by Editing Shock Graphs (2001, methodology): “The notion of edit distance has been generalized to comparing ordered, rooted trees [22].”
Recognition of shapes by editing their shock graphs (2004, methodology): “This method is due to Zhang and Shasha [51], though the formulation presented here is different.”
A comprehensive comparison of comparative RNA structure prediction approaches (2004, methodology): “The concept of a similarity measurement via edit operations, a standard procedure for string comparisons, has been generalised to trees [30–33].”
Large-scale malware indexing using function-call graphs (2009, background): “However, because computing graph-edit distance is NP-hard [38], using exact graph-edit distance is feasible only for small graphs.”
Tree2Vector: Learning a Vectorial Representation for Tree-Structured Data (2018, background): “Various tree edit distance algorithms mainly differ in the set of allowed edit operations [3]–[5].”