标签图作为一种重要的数据表示模型,广泛应用于生物化学、社交网络、知识图谱等领域,子图匹配作为图数据管理的一个重要操作,引起了研究者的普遍关注。本文针对标签图的子图匹配问题进行研究,分别给出了无重复标签图的子图匹配算法k~2-MDD-SubM和有重复标签图的子图匹配算法LCCP_SubM。本文的主要工作如下:(1)针对无重复标签图,引入k~2-MDD对其进行高效紧凑的表示以减小查询规模,同时结合符号计算的逻辑运算,给出一种子图匹配算法k~2-MDD-SubM,该算法将原始的子图匹配问题转化为基于k~2-MDD的布尔函数逻辑运算。以Graemlin和PPI数据集为例进行实验,对于Graemlin数据集,实验结果表明k~2-MDD-SubM所需存储的结点数仅为RI算法的35.83%,当模式图大小一定时,随着模式图密度的逐渐减小,算法的查询时间逐渐减少,且当模式图与目标图相同时,其查询效率优于RI算法。验证了k~2-MDD-SubM算法存储和查询性能的优越性;对于PPI数据集,实验结果表明k~2-MDD-SubM所需存储的结点数仅为RI算法的57.19%,同样随着模式图密度的减小,查询时间逐渐减少,进一步验证了算法性能的有效性。(2)针对有重复标签图,设计一种新的静态变量排序策略,该排序策略为了尽可能地减少搜索空间和回溯次数,依次考虑顶点局部聚类系数、标签概率等启发式规则,同时结合顶点标签等简单的约束过滤条件,保证匹配结果的正确性以及对不满足匹配的分支进行修剪,从而给出一种子图匹配算法LCCP_SubM。以AIDS和NASA两个真实数据集为例进行实验,在AIDS数据集下,分别从匹配数量、搜索空间、匹配时间和总时间四个方面对比分析LCCP_SubM和RI算法的性能,实验结果表明,在匹配数量相同的情况下,LCCP_SubM算法的搜索空间较RI算法具有明显的减小,匹配时间和总时间也优于RI算法,验证了该变量排序策略的有效性和算法的高效性。在NASA数据集下,实验结果表明,LCCP_SubM的搜索空间大小较RI算法同样具有明显减小,进一步验证了LCCP_SubM算法中变量排序策略的有效性。