3-后缀树的构建.ppt
- 文档编号:16255113
- 上传时间:2023-07-12
- 格式:PPT
- 页数:98
- 大小:1.37MB
3-后缀树的构建.ppt
《3-后缀树的构建.ppt》由会员分享,可在线阅读,更多相关《3-后缀树的构建.ppt(98页珍藏版)》请在冰点文库上搜索。
生物信息学概论讲义,第3章后缀树,后缀树介绍nave的后缀树构建Ukk的后缀树构建算法Weiner的后缀树构建算法McC的后缀树构建算法广义后缀树后缀数组,生物信息学概论讲义,后缀树介绍,什么是后缀树(suffixtree)?
一个例子,字符串:
xabxac,对应的后缀树,生物信息学概论讲义,后缀树介绍,后缀树的发展历史suffixtrie名称起源于retrieval特点:
每条边上标记一个字符,生物信息学概论讲义,后缀树介绍,后缀树的发展历史Weiner1973(positiontree)P.Weiner.Linearpatternmatchingalgorithms.Proc.ofthe14thIEEESymp.OnSwitchingandAutomataTheory,pp.1-11,1973McCreight1976E.M.McCreight.ASpace-economicalsuffixtreeconstructionalgorithm.J.ACM,23:
262-72,1976Ukkonen1995E.Ukkonen.On-lineconstructionofsuffix-trees.Algorithmica,14:
249-60,1995.后缀数组,生物信息学概论讲义,后缀树介绍,后缀树的用途许多字符串相关的问题(线性时间)精确匹配最长公共子串最长重复子串最长公共前缀发现回文,生物信息学概论讲义,后缀树介绍,后缀树的用途一个关于精确匹配的例子给定模式P=aw,字符串T=awyawxawxz,找到T中所有匹配模式P的部分,z,生物信息学概论讲义,后缀树介绍,后缀树的用途进一步理解基于后缀树的精确匹配P在字符串T的位置j处出现,j,P,k,P是子串Tj.m的前缀,P匹配根到叶子j的路径的部分起始标记,生物信息学概论讲义,后缀树介绍,后缀树的用途进一步理解基于后缀树的精确匹配时间复杂度仍然是O(n+m)不同阶段的任务分配不同以前,O(n)预处理P,O(m)搜索现在,O(m)预处理T,O(n+k)搜索,n模式P的长度m文本T的长度kP在T中的出现次数,生物信息学概论讲义,后缀树介绍,后缀树的定义给定一个长度为m的字符串S,其对应的后缀树T是一棵有向的根树,树的m个叶子分别标记为1到m。
除了根节点,每个内部节点至少有两个孩子节点,每条边标记为S的一个非空子串。
不存在从同一个节点扇出且具有相同起始标记字符的边。
对每个叶子节点i,从根节点到i的路径上所有边标记的连接恰好对应于字符串S起始于位置i处的后缀Si.m。
生物信息学概论讲义,后缀树介绍,后缀树的定义根到叶子i的标记=suffixi,字符串:
xabxac,对应的后缀树,生物信息学概论讲义,后缀树介绍,后缀树的定义定义完备吗?
xa是xabxa的前缀,a是abxa的前缀,xa,a,定义没有保证任意给定的字符串都存在对应的后缀树,生物信息学概论讲义,后缀树介绍,后缀树的定义定义完备吗?
问题的症结字符串S的一个后缀匹配S的另一个后缀的前缀解决的办法,在字符串S的末尾增添一个不会在S中出现的字符(比如:
$),生物信息学概论讲义,后缀树介绍,一些其它的基本定义节点的路径标记(path-label)根到节点的(有序)子串连接节点的字符串深度(string-depth)节点路径标记中的字符个数分裂点的路径标记,生物信息学概论讲义,nave的后缀树构建,总体框架首先,插入后缀S1.m$,即整个字符串然后,对i从2到m,依次插入后缀Si.m细节假定插入suffixi后的中间结果树Ni已建立,如何构建插入suffixi+1后的树Ni+1?
从Ni的根出发,依次向下匹配后缀Si+1.m中的字符匹配终结在某个节点w,或某条边(u,v)的内部如果终结在(u,v)的内部,插入新节点w,标记(u,w)和(w,v);创建新边(w,i+1),标记新边,生物信息学概论讲义,nave的后缀树构建,构建过程,xabxac$,suffix1=xabxac$,suffix2=abxac$,abxac$,suffix3=bxac$,$caxb,suffix4=xac$,c$,w,suffix5=ac$,c$,u,suffix6=c$,c$,suffix7=$,$,1,2,3,4,5,6,7,字符串xabxac$,时间复杂度O(m2),生物信息学概论讲义,Ukk的后缀树构建算法,Ukk算法的特点节省了空间具有“在线”属性易于理解,生物信息学概论讲义,Ukk的后缀树构建算法,隐后缀树定义字符串S$的后缀树经过以下操作后得到的结果,称为字符串S的隐后缀树
(1)移除后缀树边标记中的终结符$
(2)移除没有标记的边(3)移除孩子节点少于两个的节点符号表示Ii代表字符串S1.i对应的隐后缀树,生物信息学概论讲义,Ukk的后缀树构建算法,隐后缀树一个例子,xa,bxa,1,$,4,a,bxa,2,$,5,$,6,axb,3,字符串xabxa的后缀树,$,$,$,字符串xabxa的隐后缀树,特点后缀不一定终结在叶节点隐含了所有的后缀信息,生物信息学概论讲义,Ukk的后缀树构建算法,隐后缀树隐后缀树和后缀树的关系,字符串:
xabxac,若字符串末尾的字符从未在之前的字串中出现过,那么对应的隐后缀树和后缀树是相同的,生物信息学概论讲义,Ukk的后缀树构建算法,基本思想从i=1开始,构建字符串S1.m的每个前缀S1.i对应的隐后缀树Ii(im)转换最后一棵隐后缀树Im为S1.m的真实后缀树,时间复杂度O(m),生物信息学概论讲义,Ukk的后缀树构建算法,构建过程(假定字符串长度为m)分为m个阶段:
I1,I2,Ii,Im阶段i+1分为i+1次扩展,1,2,3,4,5,i+1,i,m,Ii+1=S1.i+1,I1,I2,I3,Ii,j,S(i+1),生物信息学概论讲义,Ukk的后缀树构建算法,构建框架(假定字符串长度为m)构建I1Forifrom1tom1doBegin(i+1)th阶段Forjfrom1toi+1Beginjth扩展从Ii的根向下,匹配Sj.i如果有必要,在标识为Sj.i的路径尾追加S(i+1)EndEnd,生物信息学概论讲义,Ukk的后缀树构建算法,后缀扩展规则假定Ii中,Sj.i=,如何扩展为S(i+1)规则1若终结在某个叶节点,则直接将S(i+1)添加到该叶节点对应的边标记的尾端,S(i+1),生物信息学概论讲义,Ukk的后缀树构建算法,后缀扩展规则假定Ii中,Sj.i=,如何扩展为S(i+1)规则2非终结在叶节点且之后没有起始标识为S(i+1)的路径,则在之后创建一个节点(如果不存在),并由该节点引出一条标记为S(i+1)的边,指向新的叶节点j。
S(i+1),生物信息学概论讲义,Ukk的后缀树构建算法,后缀扩展规则假定Ii中,Sj.i=,如何扩展为S(i+1)规则3之后存在起始标识为S(i+1)的路径,则无需任何操作。
S(i+1),S(i+1),生物信息学概论讲义,Ukk的后缀树构建算法,后缀扩展规则一个实例,axabx,axabx,bx,bx,xabx,1,2,3,4,b,b,b,b,b,b,5,生物信息学概论讲义,Ukk的后缀树构建算法,加速构建过程关键问题快速定位S1.i的i+1个后缀nave解决办法每次扩展,从根向下进行次比较O()阶段i+1的第j次扩展比较i+1-j次从Ii构建Ii+1的时间复杂度O(i2)构建Im的最终时间复杂度O(m3),O(m3)=O(m)?
生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速什么是后缀链?
若x代表一个字符串,其中x为一个单独的字符,为一个子串(可能为空),则对一个路径标识为x的内部节点v而言,如果存在另一个路径标识为的节点s(v),那么从节点v到s(v)的指针被称为后缀链。
生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速一个例子,xa,bxa,1,$,4,a,bxa,2,$,5,$,6,axb,3,$,$,$,=a,生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速几个需要说明的问题为空,内部节点v的后缀链指向根节点根节点没有后缀链每个内部节点都有一个后缀链,1,$,4,a,bxa,2,$,5,$,6,axb,3,$,$,xa,bxa,$,生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速定理如果在阶段(i+1)的jth扩展中创建了一个路径标识为x的内部节点v,那么或者在当前的树中已经存在路径标识为的内部节点,或者在下一次(j+1)th)扩展中,将创建路径标识为的内部节点。
证明:
x,S(i+1),j,v,S(i+1),j+1,生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速推论1Ukk算法中,任何新创建的内部节点在截至下一次后缀扩展时,都会有一条指向其它节点的后缀链推论2在任何隐后缀树Ii中,如果存在某个路径标识为x的内部节点v,那么必定存在一个对应的节点s(v),其路径标识为,生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速沿着后缀链构建Ii+1问题描述:
在阶段i+1的第j次扩展中,如何定位隐后缀树Ii中的后缀Sj.i,Ii=Ii+1,j,j-1,生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速沿着Ii中的后缀链构建Ii+1过程描述,j=1,x=S1.i,root,1,v,s(v),(的前缀),j=2,S(i+1),x,生物信息学概论讲义,Ukk的后缀树构建算法,基于后缀链的加速沿着后缀链构建Ii+1过程描述,扩展Sj.i到Sj.i+1,root,1,v,s(v),(的前缀),j1,应用扩展规则,右图中,已插入Sj-1.i+1如何插入Sj.i+1?
最多上移一个节点(想一想,为什么?
),生物信息学概论讲义,Ukk的后缀树构建算法,基本扩展算法(SEA)发现路径Sj-1,i之上(或之处)的第一个节点v,并令代表节点v与路径Sj-1,i末端之间的字符串如果v不是根,则沿着v的后缀链移动到节点s(v),然后从s(v)向下匹配字符串;如果v是根,从根向下匹配字符串Sj.i基于3种扩展规则,在当前的树中添加Sj.iS(i+1),如果扩展j-1创建了一个新的内部节点w,添加从w到S(w)的后缀链,生物信息学概论讲义,Ukk的后缀树构建算法,其它的加速技巧跳过/计数技巧,x,v,zabcdefghy,后缀j-1的尾,s(v),za,bc,def,xyhg,后缀j的尾,生物信息学概论讲义,Ukk的后缀树构建算法,其它的加速技巧跳过/计数技巧令g=|,g为s(v)下起始字符为首字符的边对应的字符数。
如果gg,则算法SEA可以直接跳至该边的末尾(节点),并设g=g-g,h=g+1,然后确定首字符匹配中第h个字符的下一条边,依此向下递推(g=g-g,h=h+g)。
当gg时,算法跳至边上的第g个字符。
隐含的小技巧:
(1)预先统计每条边上的字符数
(2)常量时间抽取字符串S中指定位置处的字符,生物信息学概论讲义,Ukk的后缀树构建算法,其它的加速技巧跳过/计数技巧,x,v,zabcdefghy,后缀j-1的尾,s(v),za,bc,def,xyhg,后缀j的尾,g=10,g=2,g=10-2=8,h=2+1=3,g=8-2=6,h=3+2=5,g=6-3=3,h=5+3=8,g=43,终止于y后,生物信息学概论讲义,Ukk的后缀树构建算法,一个重要的性质令(v,s(v)为Ukk算法中的某条后缀链,则v的节点深度至多比s(v)的节点深度大1。
其中,v的节点深度是指从根到节点v的路径上节点的个数。
跳过/计数策略使Ukk算法的时间复杂度变为O(m2),生物信息学概论讲义,Ukk的后缀树构建算法,一个重要的性质,x,ab,cd,efg,h,ij,ab,c,d,e,fg,h,i,j,生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速后缀树的构建时间复杂度能否降至O(m)?
算法的时间至少与输出为相同数量级,例S=abcdefghijklmnopqrstuvwxyz,S对应的后缀树中,一共包含(2627/2)个字符,生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速边标记压缩不记录真正的字符串,用一对索引值指定对应字符串在S中的起始和终止位置,例S=abcdefabcuvw,生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速边标记压缩(加速技巧1)利用索引对,检索目标字符串,进行匹配基于边标记压缩的扩展规则扩展规则1(p,i)=(p,i+1)扩展规则2标记新创建的边(i+1,i+1)边数最多2m-1,标记的存储空间O(m),生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速小观察:
扩展“终结者”规则3如果阶段i+1中的第j次扩展符合扩展规则3的要求,那么阶段i+1中的所有后继扩展(j+1i+1)都将应用扩展规则3。
证明:
第j次扩展应用了扩展规则3,则路径Sj.i后必有字符S(i+1).同理,路径Sj+1.i,Sj+2.i,Si+1.i也如此.,j,i,注意:
第i+1次扩展,生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速巧用规则3(加速技巧2)如果在阶段i+1的第j次扩展时,首次应用了扩展规则3,那么没有必要再显式地发现所有后继扩展,即Sk.i(kj)的尾,整个阶段i+1结束。
kj时,Sk.iS(i+1)为显式扩展,kj时,Sk.iS(i+1)为隐式扩展,生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速小观察:
一旦为叶,“终身”为叶如果Ukk算法在某个位置创建了叶子节点j,那么在所有后继的树创建过程中,该节点j仍然保证为叶节点。
证明:
回想三个扩展规则。
没有任何一个能够达到该效果。
生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速小观察:
一旦为叶,“终身”为叶,阶段i的所有扩展=一系列的规则1或规则2+一次规则3(可能没有),若ji代表阶段i的最后一次规则1或规则2扩展,则必有jiji+1,阶段i+1可以避免从1到ji的所有显式扩展,生物信息学概论讲义,Ukk的后缀树构建算法,进一步的加速避免无必要的显式扩展(加速技巧3)如果在阶段i+1中创建了一条叶边,其对应的子串为Sp.i+1,则将该边标记为(p,e),其中e代表当前阶段尾字符的位置。
在阶段i+1中,扩展1ji必定应用扩展规则1,因此只需对ji+1之后的扩展进行显式扩展,而对前ji次扩展只需花费常量时间增长变量e的值(隐式扩展)。
生物信息学概论讲义,Ukk的后缀树构建算法,加速后的算法(SPA)阶段i+1的实现增加e为i+1(根据技巧3,实现隐式扩展1ji)显式地计算从ji+1至j*的扩展或直至所有扩展结束(根据技巧2,扩展j*+1i+1隐式实现)设ji+1为j*1,准备下一阶段的扩展,生物信息学概论讲义,Ukk的后缀树构建算法,SPA的特点两个连续的阶段最多共享一个公共的索引(j*)每个阶段中的第一个显式扩展可在常量时间内完成,12345678,891011,111213141516,1617,阶段i,阶段i+1,阶段i+2,阶段i+3,时间复杂度O(m),生物信息学概论讲义,Ukk的后缀树构建算法,创建真实的后缀树转换隐后缀树Im为真实的后缀树添加终结符$至字符串S的末尾,继续进行Ukk算法替换每条边上的索引e为m结论Ukk算法能在O(m)时间复杂度内构建字符串S对应的显式后缀树(包括所有的后缀链),生物信息学概论讲义,Weiner的后缀树构建算法,Weiner与Ukk的差异Weiner算法首先插入S(m)$,然后插入Sm-1,m$,最后插入完整的字符串S$(离线特性)Ukk算法首先插入S
(1),然后插入S1.2,插入S1.m,最后插入S1.m$(在线特性),1,2,3,m,$,生物信息学概论讲义,Weiner的后缀树构建算法,几个简单的定义Suffi代表字符串S中起始于位置i处的后缀Si.m例如:
Suff1代表整个字符串S,Suffm代表单个字符S(m)Ti代表有m-i+2个且标记分别为i到m+1的叶子节点的后缀树。
其中,从根到任一叶子节点j的路径的标识为Suffj$,ijm+1。
Head(i)代表Si.m中匹配字符串Si+1.m$的任一子串的最长前缀,Ti是一棵包含且仅包含字符串Si.m$所有后缀的树,即字符串Si.m$的后缀树,Head(m)为空,生物信息学概论讲义,Weiner的后缀树构建算法,NaveWeiner算法,t$,$,at$,2,3,4,T2,t$,$,at$,2,3,4,T1,at$,字符串S=tat$,生物信息学概论讲义,Weiner的后缀树构建算法,NaveWeiner算法根据Ti+1构建Ti的过程描述从Ti+1的根向下匹配Suffi$的前缀(确定Head(i)在匹配终止处创建新节点w(如果w事先不存在),节点w的标识为Head(i)添加新叶边(w,i),对应的标识为Suffi$中未匹配的部分,即Suffi$的后m-i+2-|Head(i)|个字符,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法边标记压缩假设插入Suffi时,匹配一直进行到标记为s,t的边(u,z)上的第k个字符。
那么,新创建的节点w将边(u,z)“分裂”为(u,w)和(w,z)两部分,而且需要创建一条从w到叶子i的边。
其中,边(u,w)的标记为s,s+k1,边(w,z)的标记为s+k,t,边(w,i)的标记为i+d(w),m$,d(w)代表节点w的字符串深度(字符串的个数)。
生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法边标记压缩,root,u,z,Ss.t,Ss,s+k-1,Ss+k,t,Si+d(w),m$,字符串深度d(w),d(w),d(w)=d(u)+k,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法快速地发现Head(i)指示向量I对任意字符x,Ti+1中节点u处指示向量I的值Iu(x)=1,当且仅当Ti+1中存在一条起始于根且标记为x的路径。
其中,为节点u的路径标识。
连接向量L对任意字符x,Ti+1中节点u处连接向量L的值Lu(x)指向另一个内部节点u,当且仅当u的路径标识为x。
其中,为节点u的路径标识。
生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法快速地发现Head(i),Iu(x)=1Lu(x)=w,Iw(b)=1Lw(b)=,一个例子,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法快速地发现Head(i)指示向量I和连接向量L的几个性质每个非叶节点(包括根节点)处都维护两个向量I和L每个向量的长度都等于字符表的大小Lu(x)非空,则必有Iu(x)=1。
反之,不成立如果Iu(x)=1,则对u的任一祖先节点v,必有Iv(x)=1Tm中,Ir(S(m)=1,Lr(S(m)=null,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法Weiner算法的基本思想Ti+1已经建立,如何构建Ti?
从叶子i+1出发,向上查找第一个满足条件Iv(S(i)=1的节点v如果v存在,继续向上查找满足条件Lv(S(i)的第一个节点v,思考:
为什么一定要从叶子i+1出发,而不是从其它的叶子,如i+2,i+3,出发呢?
生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法,思考:
为什么一定要从叶子i+1出发,而不是从其它的叶子,如i+2,i+3,出发呢?
123ii+1m,v,v,找到Iv(S(i)=1的首个节点v,相当于确定了Head(i)的值,找到Lv(S(i)的节点v,相当于找到了确定Head(i)所在路径的“后缀链”,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法“乐观”情况下的Weiner算法节点v和v都存在“悲观”情况下的Weiner算法节点v和v都不存在节点v存在,但是v不存在,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法“乐观”情况下的Weiner算法定理1如果节点v存在,且其路径标识为,则字符串S(i)就是Head(i)证明:
假设Head(i)=S(i),Suffi=S(i)a,Suffk=S(i)b那么,Suffi+1=a,Suffk+1=b,即Ti+1中存在标记为的节点u,且Iu(S(i)=1。
进一步,u必定在从根至叶i+1的路径上。
S(i)为Head(i)的前缀,u=v或u在v之下(为的前缀)。
Iu(S(i)=1,u在v之下的情况不成立(反证法.v是第一个满足Iv(S(i)=1的节点)。
生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法“乐观”情况下的Weiner算法定理2假设节点v和v都存在,li代表路径(v,v)上的字符个数,Lv(S(i)指向节点v。
那么,如果li=0,Head(i)终结在节点v;否则,Head(i)在节点v之下某条路径的li个字符后终结.证明:
li0时,Head(i)能否终结在节点z?
v,v,v,z,Head(i)=S(i),z不可能是叶节点(反证法),v必为分枝节点(与v的选取矛盾),li0时,Head(i)能否终结在节点z之下?
z,z,S(i),同理,Head(i)不能否终结在节点z之下,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法“乐观”情况下的Weiner算法确定Head(i)的终止位置li=0,Head(i)终止在vli0,Head(i)终止在边(v,z)之间的第li个字符在Head(i)的终止位置创建节点w(如果需要),添加叶边(w,i),并做相应的标记,生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法两种“悲观”情况下的Weiner算法情况1Ir(S(i)=0节点v不存在,S中任何大于i的位置处都不会出现字符S(i)情况2Iv(S(i)=1,但是v不存在从v点的向上“移动”,一直进行到根,且Lr(S(i)=。
Head(i)终止在根之下某条路径的第ti+1个字符处(ti代表根节点r与节点v之间的字符个数),生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法完整的Weiner算法1.从Ti+1的叶子i+1出发,向根移动,发现第一个满足Iv(S(i)=1的节点v2.如果移动一直进行到根节点,且Ir(S(i)=0,那么Head(i)终止在根节点。
执行第4步3.从节点v向上,继续寻找第一个满足Lv(S(i)的节点v如果移动一直进行到根节点,且Lr(S(i)=,则从根节点开始,向下匹配S(i)开头的ti+1个字符如果v存在,根据Lr(S(i)找到v。
如果li=0,Head(i)终止在节点v;否则,终止在节点v下某条边路径的第li个字符处在Head(i)的“尾”创建节点w,添加叶边(w,i),并做相应标记(即suffi的后m-i+1-|Head(i)|个字符加上“$”),生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法向量I和向量L的更新(suffi插入)L向量的更新如果v存在,Lv(S(i)应该被设置为指向w。
而且,如果w是新创建的,则其对应的L向量中每个入口项为空.I向量的更新从根节点至叶子节点的路径上的每个节点u,都应该有Iu(S(i)=1(实际只用修改位于节点v之下的u节点),生物信息学概论讲义,Weiner的后缀树构建算法,更有效的Weiner算法向量I和向量L的更新(suffi插入)I向量的更新(续)定理当在边(v,z)的内部创建了新节点w时,w的I向量可以直接设置为z的I向量的拷贝证明:
显然,Iz(x)=1,必有Iw(x)=1。
反过来,Iw(x)=1,是否
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 后缀 构建