Storage Optimization And Tree Vertical Merging Algorithm Of Tai Tree Editing Distance Algorithm

Aiming at Tai’s tree edit distance algorithm which space complexity was too high and using the approach were data hierarchical storage and data filtering, storage optimization algorithm was presented. Which can increased the space complexity from O(V*V’*L2* L’2) to O(V*V’*L* L’), V and V are the numbers of nodes respectively of two trees.and L and L’ are the maximum depths respectively of two trees. The improved algorithm is more economical than the original algorithm of space complexity and time complexity.In addition, serialization of solution is given when the number of nodes in the tree is very big that lead to memory insufficient.Aiming at Tai’s and Zhang & Shasha’s tree edit distance algorithm in computing the parse tree which depth is too large of XML similarity, the time complexity of algorithm is too high.The longitudinal merge algorithm of tree is proposed. Based on longitudinal merge algorithm, can increased the time complexity of Tai’s tree edit distance algorithm from O (V*V’*L2* L’*2) to O (V*V) and the time complexity of Zhang & Shasha’s tree edit distance algorithm from O (V*V’* min (L, leaves (T1))* min (L’,leaves (T2))) to O (V*V’). depth (T1) and depth (T2) are the maximum depths of two trees respectively.