压缩 PATRICIA结构 Xxxxx xxxXX OOxxxX Olxxxx 10xXXX ixxxx 000xx(2 17 63 lXxx 1010xx 0000xX 0001xx 941 45 2 编码:2:0000105:0001019:001001 17:01000141:10100145:10110163:11111l 北京大学信息学院张铭编写@版权所有,转载或翻印必究 1
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 11 压缩PATRICIA 结构 17 01xxxx 10xxxx 001xxx 0000xx 0001xx 编码:2:000010 5:000101 9:001001 17:010001 41:101001 45:101101 63:111111 0 1 1 2 3 3 0xxxxx 1xxxxx 00xxxx 11xxxx 2 5 9 41 63 45 1011xx 1010xx 000xxx
PATRICIA的特点 改进后的压缩 PATRICIA树是满二叉树 每个内部结点都代表一个位的比较 ■必然产生两个子结点 一次检索不超过关键码的位个数 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 12
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 12 PATRICIA的特点 改进后的压缩PATRICIA树是满二叉树 每个内部结点都代表一个位的比较 必然产生两个子结点 一次检索不超过关键码的位个数
后缀树( Suffix tree) 后缀树是表示一个字符串S所有后缀串的树 结点表示开始的字符(或压缩字符串) 边标注为子串—该字符串在原串中的起止位置 边表示不同字符分支 所有根到树叶结点的路径,可以表示串S的所有后缀串 ■通俗地说 个字符串的所有后缀 这些后缀组成Tre 压缩Trie,得到字符串的后缀树 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 13
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 13 后缀树(Suffix Tree) 后缀树是表示一个字符串 S 所有后缀串的树 结点表示开始的字符(或压缩字符串) 边标注为子串——该字符串在原串中的起止位置 边表示不同字符分支 所有根到树叶结点的路径,可以表示串 S 的所有后缀串 通俗地说: 一个字符串的所有后缀 这些后缀组成Trie 压缩Trie,得到字符串的后缀树
MALAYALAM$的后缀 MALAYALAM ALAYALAM LAYALAM AYALAM YALAM ALAM LAM A M M $ 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 14
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 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 $
对后缀串排序 ALAM ALAYALAM AM AYALAM LAM LAYALAM MALAYALAM YALAM $ 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 15
北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 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 $