两棵树的公共子树查找算法综述

A survey on finding maximal common subtree of two trees

本文通过对基于两棵树中的公共子树查找问题在有根、带标记、有序树中的主要算法及相关历史的回顾,结合算法思想将公共子树查找问题分为主要3类。本文深入探讨了每类算法中的代表算法,其中根据数据挖掘中枚举树相关技术提出了一种可能的公共子树查找算法的思想。最后比较了文中主要算法的效率,同时较为深入地分析和讨论了公共子树的相关研究及未来可能的研究发展方向。

This paper reviews the algorithms and their history of finding maximal common subtrees of two ones,which are rooted,labeled,ordered trees.The common subtree algorithms can be classified into three categories according to their working principles,for each category a representative algorithm is discussed thoroughly.Among these three categories a possible common subtree algorithm is presented based on the enumeration tree technique of data mining domain.In addition,it provides an efficienct comparison of important common subtree algorithms.Related works and future works are also analyzed and discussed in this paper.