Understanding Tree Edit Distance in Labeled Trees
Explore the concept of tree edit distance for labeled trees, covering operations like deleting, inserting, and relabeling nodes. Discover key algorithms and solutions for this comparison problem, along with related aspects such as alignment distance and inclusion issues.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A survey on tree edit distance and related problems Philip Bille, IT University of Copenhagen Theoretical Computer Science, vol 337, Issues 1-3, pp. 217-239, June 9, 2005 Presenter: Syuan-Chung Chiou Date:2016/1/5
Abstract We survey the problem of comparing labeled trees based on simple local operations of deleting, inserting and relabeling nodes. These operations lead to the tree edit distance, alignment distance and inclusion problem. For each problem we review the results available and present, in detail, one or more of the central algorithms for solving the problem.
Introduction Relabel insert delete
Edit operations and edit mappings We represent each edit operation by (?1 ?2). Relabel ?1 ?2 ?1,?2 ? Delete ?1 ? Insert ? ?2
Edit operations and edit mappings For any pair ?1,?1,(?2,?2) ? 1. ?1= ?2iff ?1= ?2. 2. ?1is an ancestor of ?2iff ?1is an ancestor of ?2. 3. ?1is to the left of ?2iff ?1is to the left of ?2.
Edit operations and edit mappings ? ? = ?(? ?) + ?(? ?) + ?(? ?) (?,?) ? ? ?1 ? ?2
A simple algorithm Lemma 1 Let ?1??? ?2?? ??????? ??????? and ? ?? ? ?????? ???? ???????? ??????? ?? ??????.??? ? ??? ? ?? ? ? ??? ????? ?? ??? ????? ?? ? ? ????? ?? ?1??? ?2????????????. ?? ???, ? ?,? = 0 ? ?1,? = ? ?1 ?,? + ? ? ? ? ?,?2 = ? ?,?2 ? + ?(? ?) ? ?1 ?,?2 + ? ? ? ? ?1,?2 ? + ?(? ?) ? ?1,?2 = min ? ?1(?),?2(?) + ? ?1 ?1? ,?2 ?2(?) + ? ? ?
Zhang and Shashas algorithm Define ???????? ? = ???? ? Lemma 2 ??? ??? ???? ? ? ? ,? ? ?? ? ???????? ??????????. Lemma 3 ??? ?? ??????? ???? ? ? ? # ?? ???????? ???????????, ??? ??????? ?? ? ? ???????? ?? ??????? ?? ? ? ????? ? . ? ? ? ? ?? ? ???? ???????} |?(?)| < |?(?)| = ????? (?) ? ????????(?) ? ????????(?) ? ?(?) ????? (?) = ? ????? ? ? ?(?) Lemma 4 ??? ? ???? ?,????? (?) min{???? ? ,??????(?)}
Kleins algorithm Decomposition of a rooted tree ? into disjoint paths called heavy paths. Root is light For each internal node ? we pick a child ? of ? of maximum size among the children of ? and classify ? as heavy. The remaining children are light. An edge to a light child is light edge, to a heavy child is heavy edge. ????? (?), is the # of light edges on the path from ? to the root.
Kleins algorithm Lemma 5 ??? ??? ???? ? ??? ? ? ? ,????? ? log ? + ? 1 . Lemma 6 ??? ?? ??????? ???? ? ? ? # ?? ???????? ??????????? ??? ??????? ?? ? ? ??? ? ????? ?? ??????? ?? ? ? ????? ? .
Constrained edit distance ??(?1,?2) is defined as a minimum cost mapping (??,?1,?2) , for all ?1,?1, ?2,?2,(?3,?3) ?? ???(?1,?2) is a proper ancestor of ?3 iff ???(?1,?2) is a proper ancestor of ?3. ??(?1,?2) is defined as a minimum cost mapping (??,?1,?2) , for all ?1,?1, ?2,?2,(?3,?3) ??such that none of ?1, ?2and ?3is an ancestor of the others. ??? ?1,?2 = ???(?1,?3) iff ??? ?1,?2 = ???(?1,?3).
Constrained edit distance ??(?1,?2) is defined as a minimum cost mapping (??,?1,?2) , for all ?1,?1, ?2,?2,(?3,?3) ??such that none of ?1, ?2and ?3is an ancestor of the others. ???? (??? ?1,?2) ???? (??? ?1,?3) and also ??? ?1,?2 = ??? ?1,?3 iff ???? (??? ?1,?2) ???? (??? ?1,?3) and also ??? ?1,?2 = ??? ?1,?3
Tree Alignment Distance Lemma 7 ??? ? ? ?1 ??? ? ? ?2 ??? ? ?????? ?1, ,????? ?1, ,??????????????. ? ?? , ? ?,? = 0 ? ?1? ,? = ? ?1? ,? + ? ?,? ? ?,?2? = ? ?,?2? + ? ?,? ? ? ?1? ,? = ?(?1??,?) ?=1 ? ? ?,?2? = ?(?,?2??) ?=1
Tree Alignment Distance Lemma 8 ??? ? ? ?1 ??? ? ? ?2 ??? ? ?????? ?1, ,????? ?1, ,??????????????. ? ??, ? ?1? ,?2(?) + ?(?,?) + min 1 ? ?{? ?1? ,?2?? ? ?1? ,? + min ? ?,?2? ?(?,?2(??))} ? ?1(?),?2(?) = min 1 ? ?{? ?1??,?2? ?(?1??,?)}
Tree Alignment Distance A?,?= ? ?1??,??,?2??,?? ? ? ? ? ? ? ? + ? ? ? ? ?,? ? ?} = ? ?? ? + ? The time to compute both A?,1 and A1,? ,1 ? ? ??? 1 ? ?, is bounded by ?(??(? + ?)2).
Tree Inclusion Define an ??????? ????????? (?,?1,?2) as an infective function ? ?(?1) ? ?2 such that for all nodes ?,? ? ?1, ????? ? = ????? ? ? . ? is an ancestor of ? iff ?(?) is an ancestor of f(?). ? is to the left of ? iff ?(?) is to the left of f(?).
Kilpelinen and Mannilas algorithm { ? ?? ? ? ?(?1(?),?2(? ))} { }} ? ?,? = min
