web2.0时代的到来,不仅为互联网和计算机科学领域带来了海量数据,还带来了新的数据类型。树结构正是这些新出现的数据类型的一种,它在计算机科学、语言学、生物学、图形学等领域的数据组成上占有重要的地位。而在这些领域中,用户更想通过度量不同树结构数据之间的相似性来完成一些特定检索、匹配等任务。但目前树结构相似度计算方面仍然存在着许多挑战:一、数据量大导致计算耗时严重;二、算法运行占用空间大;三、计算结果误差大。虽然针对上述树结构存在的问题,已经提出了很多算法,比如树编辑距离算法,树核算法以及利用数据特性的算法等等,而这些算法也对该问题的解决起到了一定的作用,但是却仍然存在着一些其他问题。对于无序树结构,树编辑距离算法是NP-hard问题,其他算法却又存在着误差大、计算耗时,占用空间大的问题;而对于有序树结构,树编辑距离算法被证明时间复杂度最低只能为立方时间,其他算法也由于难以捕获结构信息,导致计算精确度较低。针对上述问题,本文主要做了下面两部分的研究工作:（1）针对无序树结构数据,提出了一种基于最小哈希算法的保结构的子路径签名算法。而本研究的创新点为:1)提出了一种保结构的子路径签名算法,可以将树结构数据转换为一个具有保结构特性的子路径签名,然后利用其计算相似度。同时通过理论证明了它的保结构特性;2)利用了最小哈希算法,可以较好地解决数据量太大导致的计算耗时的问题,并降低了运行的占用空间。（2）针对于有序树结构数据,提出了基于子路径签名算法的多维序列算法。在本研究中,创新点包括:1)将多维序列框架与子路径签名算法结合,实现了序列相似度快速计算;2)利用动态时间规整算法将树结构的空间信息得到使用,使计算出的相似度结果更准确。