A fast algorithm for optimal alignment between similar ordered trees
Författare
Summary, in English
We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with S and T nodes, respectively. If there exists an optimal alignment between S and T which uses at most d blank symbols and d is known in advance, it can be constructed in O(n log n (.) (maxdeg)(3) (.) d(2)) time, where n = max{S, T} and maxdeg is the maximum degree of all nodes in S and T. If d is not known in advance, we can construct an optimal alignment in O(n log n (.) (maxdeg)(3 .) f(2)) time, where f is the difference between the highest possible score for any alignment between two trees having a total of S + T nodes and the score of an optimal alignment between S and T, if the scoring scheme satisfies some natural assumptions. In particular, if the degrees of both input trees are bounded by a constant, the running times reduce to o(n log n (.) d(2)) and O(n log n (.) f(2)), respectively.
Avdelning/ar
- Computer Science
Publiceringsår
2003
Språk
Engelska
Sidor
105-120
Publikation/Tidskrift/Serie
Fundamenta Informaticae
Volym
56
Issue
1-2
Dokumenttyp
Artikel i tidskrift
Förlag
IOS Press
Ämne
- Computer Science
Status
Published
Projekt
- VR 2002-4049
ISBN/ISSN/Övrigt
- ISSN: 0169-2968