单词粒度的后缀树 ●“Ⅰ know you know$ know you know you know you know know 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 21
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 单词粒度的后缀树 z “I know you know $
后缀树的应用 查找字符串中的子串 统计S中出现T的次数 找出s中最长的重复子串 出现了两次以上的子串 两个字符串的公共子串 最长共同前缀(LcP 回文串 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 22
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 后缀树的应用 查找字符串中的子串 统计S中出现T的次数 找出S中最长的重复子串 出现了两次以上的子串 两个字符串的公共子串 最长共同前缀(LCP) 回文串
后缀树的应用 中文切词 ■关联分析 发现经常共同出现的短语 ■频繁模式挖掘 STc聚类 基因/蛋白序列对比/分类 ■■■■■ 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 23
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 后缀树的应用 中文切词 关联分析 发现经常共同出现的短语 频繁模式挖掘 STC 聚类 基因/蛋白序列对比/分类 ……
后缀数组 字符串S的后缀数组SA 对S的所有后缀的指针排序 即后缀树叶结点的字典序 后缀树ST=后缀数组SA+ LcP数组 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 24
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 后缀数组 字符串S的后缀数组SA 对S的所有后缀的指针排序 即后缀树叶结点的字典序 后缀树ST = 后缀数组SA + LCP数组
数组( Suffix Array 6ALAM$ M ALAM S 2 ALAYALAM$ 12345678910 8AM$ 4AYALAM$ 62847319510 7LAM$ 后缀数组 3LAYALAMS 1 MALAYALAM$ 311 020100- 9M$ ↑最长公共前缀数组 5YALAM$ 10 后缀6和2共享"ALA 后缀2和8共享"A" LCP总是相邻的 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 2
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 数组(Suffix Array) 10 $ 5 YALAM$ 9 M$ 1 MALAYALAM$ 3 LAYALAM$ 7 LAM$ 4 AYALAM$ 8 AM$ 2 ALAYALAM$ 6 ALAM$ M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 6 2 8 4 7 3 1 9 5 10 后缀数组 3 1 1 0 2 0 1 0 0 - 最长公共前缀数组 后缀6和2共享 “ALA” 后缀2和8共享 “A” LCP总是相邻的