Revisiting the tree edit distance and its backtracing: A tutorial

Paaßen B (Draft)
arXiv:1805.06869.

Preprint | Entwurf | Englisch
 
Abstract / Bemerkung
Almost 30 years ago, Zhang and Shasha published a seminal paper describing an efficient dynamic programming algorithm computing the tree edit distance, that is, the minimum number of node deletions, insertions, and replacements that are necessary to transform one tree into another. Since then, the tree edit distance has had widespread applications, for example in bioinformatics and intelligent tutoring systems. However, the original paper of Zhang and Shasha can be challenging to read for newcomers and it does not describe how to efficiently infer the optimal edit script. In this contribution, we provide a comprehensive tutorial to the tree edit distance algorithm of Zhang and Shasha. We further prove metric properties of the tree edit distance, and describe efficient algorithms to infer the cheapest edit script, as well as a summary of all cheapest edit scripts between two trees.
Erscheinungsjahr
2018
Zeitschriftentitel
arXiv:1805.06869
Page URI
https://pub.uni-bielefeld.de/record/2919918

Zitieren

Paaßen B. Revisiting the tree edit distance and its backtracing: A tutorial. arXiv:1805.06869. Draft.
Paaßen, B. (Draft). Revisiting the tree edit distance and its backtracing: A tutorial. arXiv:1805.06869
Paaßen, B. (Draft). Revisiting the tree edit distance and its backtracing: A tutorial. arXiv:1805.06869.
Paaßen, B., Draft. Revisiting the tree edit distance and its backtracing: A tutorial. arXiv:1805.06869.
B. Paaßen, “Revisiting the tree edit distance and its backtracing: A tutorial”, arXiv:1805.06869, Draft.
Paaßen, B.: Revisiting the tree edit distance and its backtracing: A tutorial. arXiv:1805.06869. (Draft).
Paaßen, Benjamin. “Revisiting the tree edit distance and its backtracing: A tutorial”. arXiv:1805.06869 (Draft).
Link(s) zu Volltext(en)
Access Level
OA Open Access

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Quellen

arXiv: 1805.06869

Suchen in

Google Scholar