Edytuj odległość na drzewach

Ten artykuł jest szkicem o komputerach .

Możesz dzielić się swoją wiedzą doskonaląc ją ( jak? ) Zgodnie z zaleceniami odpowiednich projektów .

W informatyce teoretycznej w biochemii, a także w zastosowaniach w wizji komputerowej , na przykład odległość edycji drzewa (w języku angielskim odległość edycji drzewa ) jest miarą, która ocenia, pod względem liczby przekształceń elementarnych, liczbę wymaganych operacji i ich koszt przenosić się z jednego drzewa na drugie. Jest to pojęcie, które rozszerza na drzewa odległość edycji (lub odległość Levenshteina ) między ciągami znaków. Odległość pomaga na przykład porównać drugorzędową strukturę RNA lub drzewa filogenetyczne w biologii, a nawet kierować zaleceniami dotyczącymi edycji dla uczniów w inteligentnych systemach nauczania.

Istnieje kilka wariantów tego pojęcia, w zależności od charakteru rozważanych drzew. Ogólnie rzecz biorąc, są to drzewa abstrakcyjne; bardziej restrykcyjnie, rozważamy platany, to znaczy takie, że sąsiednie wierzchołki wierzchołka są uporządkowane. Jeszcze bardziej szczególny jest przypadek platanów ukorzenionych: takie drzewo składa się z korzenia i uporządkowanej serii poddrzew. Tak jest w przypadku opisanym poniżej. Przegląd zawiera artykuł Benjamina Paaßena.

Podstawowe operacje transformacji drzewa są, tak jak w przypadku łańcuchów znaków, usuwanie , wstawianie i zmiana nazwy , stosowane do węzła drzewa.

Notacje

Traktujemy drzewa jako struktury rekurencyjne: drzewo składa się z węzła głównego , a las jest serią drzew. Odległość edit dwóch drzew i jest to minimalna liczba insercji, delecji lub zmienia nazwy węzłów, zauważył , niezbędne do przekształcenia się . Obliczanie odległości edycyjnej na drzewie jest podobne do obliczania na ciągach. Jednak wybór kolejności rekurencji może znacząco zmienić złożoność czasową obliczeń. ${\ styl wyświetlania A = r (F)}$ $r$ $fa$ $W$ $W'$ ${\ styl wyświetlania \ delta (A, A ')}$ $W$ $W'$

Strategie dekompozycji

Poniższa dyskusja pochodzi z artykułu Dulucqa i Touzeta. Niech i bądź dwoma niepustymi drzewami. Obliczenie odbywa się w następujący sposób: ${\ styl wyświetlania A = r (F)}$ ${\ styl wyświetlania A '= r' (F ')}$ ${\ styl wyświetlania \ delta (A, A ')}$

{\ displaystyle \ delta (A, A ') = \ min \ {(c_ {i} (r') + \ delta (A, F '), (c_ {s} (r) + \ delta (F, A) '), (c_ {r} (r, r') + \ delta (F, F ') \}}

gdzie (odp. , odp. ) oznacza koszt związany z usunięciem (odp. wstawieniem, odp. zmianą nazwy) węzła. $c_ {s}$ $to}$ ${\ styl wyświetlania c_ {r}}$

Koszt obliczenia odległości edycyjnej na drzewach odbywa się dzięki odległości edycyjnej na lasach, zawsze odnotowywanej . Obliczenie odległości edycji w lasach można wykonać na dwa sposoby, faworyzując lewą lub prawą stronę: obliczenie dotyczy dwóch serii drzew, zaznaczonych i , gdzie i są drzewami oraz i zestawami szczątków. Pozując i , strategie to: $\delta$ ${\ styl wyświetlania A \ circ T}$ ${\ displaystyle A '\ circ T}$ $W$ $W'$ $T$ $T '$ ${\ styl wyświetlania A = r (F)}$ ${\ displaystyle A '= r (F')}$

w lewo :

{\ displaystyle \ delta (A \ circ T, A '\ circ T') = \ min \ left \ {{\ zacząć {tablica} {ll} c_ {i} (r ') + \ delta (A \ circ T , F '\ circ T'); \\ c_ {s} (r) + \ delta (F \ circ T, A '\ circ T'); \\\ delta (A, A ') + \ delta (T , T '); \ end {tablica}} \ prawo.}

w prawo :

{\ displaystyle \ delta (T \ circ A, T '\ circ A') = \ min \ left \ {{\ zacząć {tablica} {ll} \ delta (T \ circ A, T '\ circ F') + c_ {i} (r '); \\\ delta (T \ circ F, T' \ circ A ') + c_ {s} (r); \\\ delta (T, T') + \ delta (A , A ') \ end {tablica}} \ prawo.}

Strategia dekompozycja jest sukcesja wyborów między rozkładem po lewej lub po prawej stronie rozkładu. Każdy algorytm oparty na dekompozycji ma w najgorszym przypadku złożoność w czasie co najmniej w . Algorytmy programowania dynamicznego można badać za pomocą strategii dekompozycji. Dwie z najczęściej stosowanych strategii to strategie Zhang-Shasha (1989) i Klein (1998): ${\ displaystyle \ Omega (n \ log (n) m \ log (m))}$

Zhang-Shasha

Strategia dekompozycji Zhang-Shasha polega na systematycznym stosowaniu dekompozycji lewostronnej.

Zhang i Shasha wykazali, że złożoność czasowa ich algorytmu obliczania odległości edycji dwóch drzew i wynosi w , gdzie jest sumą rozmiarów dwóch drzew. Z drugiej strony złożoność tego algorytmu jest w . $W$ $W'$ $O (n ^ 4)$ $nie$ ${\ styl wyświetlania O (n ^ {2})}$

Klein

Strategia dekompozycji Kleina wykorzystuje pojęcie ścieżki ciężkiej . Wybór rozkładu jest „po lewej”, jeśli pierwsze prawe dziecko A znajduje się na ciężkiej ścieżce, a „po prawej” w pozostałych przypadkach.

Złożoność czasowa tego algorytmu wynosi . $O (n ^ {3} \ log (n))$

Wariant

Demaine i jego współautorzy zaproponowali algorytm obliczania odległości edycji na drzewach w oparciu o strategię dekompozycji Dulucqa i Touzeta : Algorytm ten ma najgorszy przypadek złożoności czasowej w i wewnątrz złożoności w przestrzeni. $O (n ^ {3})$ $O (n ^ 2)$

Uwagi i referencje

Paaß w 2018 roku .
Dulucq i Touzet 2003 .
Zhang i Shasha 1989 .
Klein 1998 .
Erik D. Demaine, Shay Mozes, Benjamin Rossmann i Oren Weimann, „ Optymalny algorytm dekompozycji dla odległości edycji drzewa ”, ACM Transactions on Algorithms , tom. 6, n O 1, 2009( DOI 10.1145 / 1644015.1644017 ).

Bibliografia

Benjamin Paaßen, „Revising the tree edit distance and its backtracing: A tutorial ”, Materiał uzupełniający do artykułu ICML 2018: Tree Edit Distance Learning via Adaptive Symbol Embeddings ,26 października 2018( arXiv 1805.06869 ).
Serge Dulucq i Hélène Touzet, „Analiza odległości edycji drzewa” , w Combinatorial Pattern Matching CPM 2003 , Springer, coll. „Notatki z wykładu z informatyki 2676”,2003( ISSN 0302-9743 , DOI 10.1007 / 3-540-44888-8_7 , prezentacja online ) , s. 83-95.
K. Zhang i D. Shasha, „ Proste szybkie algorytmy do edytowania odległości między drzewami i powiązanych problemów ”, SIAM Journal of Computing , tom. 18 N O 4,1989, s. 1245-1262.
Philip N. Klein, „ Computing the edit-distance entre order unrooted trees ”, „ Proceedings of the 6th European Symposium on Algorithms” ,1998, s. 91-102 ( czytaj online , skonsultowano 13 stycznia 2019 r. ).

Link zewnętrzny

„Z łatwością porównaj swoje drzewa” na Uniwersytecie w Salzburgu