后缀树 SEMALAYALAMS ALAM 12345678910 ALAYALAM YALAM LAM LA M LAYALAM MALAYALAM M 10 YALAM 99 6 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 16
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 S = M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 YA $ LAM$ M $ ALAYALAM$$M YALAM$ $M YALAM$ $M YALAM$ A AL LA 6 2 8 47 3 1 9 5 10 后缀树 A L A M A L A Y A L A M A M A Y A L A M L A M L A Y A L A M M A L A Y A L A M M Y A L A M $
边信息 SEMALAYALAMS 12345678910 10 8 7 3 2 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 17
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 (5 (10, 10) , 10) ( 1 , 1 ) (10, 10) (2, 10) (3, 4) (5, 10) (9, 10) (2, 2) (5, 10) (9, 10) (3, 4) (9, 10) (5, 10) 6 2 8 4 7 31 9 5 10 边信息 S = M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10
建树算法 ■对于长度为n的语料建立后缀树,直 接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 1976年 McCreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法 北京大学信息学院张铭编写@版权所有,转载或翻印必究 18
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 建树算法 对于长度为n的语料建立后缀树，直 接的方法时间复杂度为O（n*n） 1973年Weiner提出线性时间算法 1976年McCreigh提出更节约内存 的算法 1995年Ukkonen提出线性时间建 树算法
●对于长度为n的字符串建立后缀树 直接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 1976年 McCreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 19
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 z 对于长度为n的字符串建立后缀树， 直接的方法时间复杂度为O（n*n） z 1973年Weiner提出线性时间算法 z 1976年McCreigh提出更节约内存 的算法 z 1995年Ukkonen提出线性时间建 树算法
GST一通用后缀树( Generalized WINDOWS INDIGOS 1234567 1234567 (1,7) 7) (2,3)(1,4)(2,4 2,2)(1,3)(1,5)(2,6 (1,6) (1,1) 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 20
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 GST——通用后缀树(Generalized) $ O ND W I $OG D $OGI OW$ $OG ND $OGI OW$ $OGI OW$ $W $ INDO$ W$ (2, 3) (1, 4) (2, 5) (2, 4) (2, 1) (1, 2) (2, 2) (1, 3) (1, 5) (2, 6) (1, 6) (1, 1) (1, 7) (2, 7) WINDOW$ INDIGO$ 1234567 1234567