RTED

摘要: We consider the classical tree edit distance between ordered labeled trees, which is defined as minimum-cost sequence of node operations that transform one into another. The state-of-the-art solutions for are not satisfactory. main competitors in field either have optimal worst-case complexity, but worst case happens frequently, or they very efficient some shapes, degenerate others. This leads to unpredictable and often infeasible runtimes. There no obvious way choose algorithms.In this paper we present RTED, a robust algorithm. asymptotic complexity RTED smaller equal best any input instance, i.e., both optimal. introduce class LRH (Left-Right-Heavy) algorithms, includes fastest algorithms presented literature. prove outperforms all previously proposed terms runtime complexity. In our experiments on synthetic real world data empirically evaluate solution compare it state-of-the-art.