后缀树( Suffix tree MALAYALAM$的后缀 后辍树是表示一个字符串S所有后缀申的树 MALAYALAM 结点表示开始的字符(或压缩字符串) ALAYALAM 边标注为子串—该字符申在原串中的起止位置 S LAYALA M 所有根到树叶结点的路径,可以表示率S的所有后氧 AYALAM YALAM 压Tre,得到字符串的后树 M 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 对后缀串排序 后缀树 s· MALAYALAMS ALA M ALAM 12345678910 ALAYALAM ALAYALAM AYALAM AYALAM LAYALAM MALAYALAM MALAYALAM YALAM YALAM 北京大学值歌张写所有即究 边信息 s· MALAYALAMS 建树算法 2345678910 ■对于长度为n的语料建立后缀树,直 接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 1976年 McCreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 后缀树(Suffix Tree) „ 后缀树是表示一个字符串 S 所有后缀串的树 „ 结点表示开始的字符(或压缩字符串) „ 边标注为子串——该字符串在原串中的起止位置 „ 边表示不同字符分支 „ 所有根到树叶结点的路径，可以表示串 S 的所有后缀串 „ 通俗地说： „ 一个字符串的所有后缀 „ 这些后缀组成Trie „ 压缩Trie，得到字符串的后缀树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 MALAYALAM$ 的后缀 „ M A L A Y A L A M „ A L A Y A L A M „ L A Y A L A M „ A Y A L A M „ Y A L A M „ A L A M „ L A M „ A M „ M „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 对后缀串排序 „ 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 „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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 „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 (10, (5 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 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 建树算法 „ 对于长度为n的语料建立后缀树，直 接的方法时间复杂度为O（n*n） „ 1973年Weiner提出线性时间算法 „ 1976年McCreigh提出更节约内存 的算法 „ 1995年Ukkonen提出线性时间建 树算法