开发者社区> sjf0115> 正文

[算法系列之二十四]后缀树(Suffix Tree)

简介:
+关注继续查看

之前有篇文章([算法系列之二十]字典树(Trie))我们详细的介绍了字典树。有了这些基础我们就能更好的理解后缀树了。

一 引言 模式匹配问题

给定一个文本text[0…n-1], 和一个模式串 pattern[0…m-1],写一个函数 search(char pattern[], char text[]), 打印出pattern在text中出现的所有位置(n > m)。

这个问题已经有两个经典的算法:KMP算法 ,有限自动机,前者是对模式串pattern做预处理,后者是对待查证文本text做预处理。在进行完预处理后,可以到达O(n)的时间复杂度,n是text的长度。

后缀树可以用对text进行预处理,构造一个text的后缀树,就可以在 O(m) 的时间内搜索任意一个pattern,m是模式串pattern的长度。

二 简介

后缀树提出的目的是用来支持有效的字符串匹配和查询,例如上面的问题。后缀树(Suffix tree)是一种数据结构,能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner 于1973年提出,既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改进完善。

总结一句:一个给定的文本text的后缀树就是一个压缩的后缀字典树。

前面一篇文章我们已经讨论了 字典树(Trie),下面先让我们来了解一下压缩字典树( Compressed Trie)

三 压缩字典树( Compressed Trie)

我们以一下一组单词来介绍一下什么是压缩字典树:

{bear, bell, bid, bull, buy, sell, stock, stop}

我们以上面一组单词构建一个字典树如下:

这里写图片描述

下面就是压缩字典树。压缩字典树是从字典树转换而来,把字典树中的单节点链条进行压缩。即一个没有分叉的单边,进行压缩。

这里写图片描述

四 后缀压缩字典树

经过以上讨论,我们知道后缀树是文本text所有后缀的压缩字典树。一个后缀树的生成经过一下几步:
(1)生成给定文本text的所有后缀。
(2)视所有后缀为有效单词,生成一个压缩字典树。

我们以”banana\0”(’\0’是结束字符)为例,字符串的所有后缀为:

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

假设我们考虑以上字符串的所有后缀均为有效单词,构造一个字典树如下:

这里写图片描述

如果我们合并单节点链条,我们得到如下压缩字典树,即给定文本”banana\0”的后缀树。

这里写图片描述

至此,我们已经了解了什么是后缀树了。

五 后缀树应用

(1)从目标串S中判断是否包含模式串T(Pattern Searching)

方案:用S构造后缀树,按在Trie中搜索子串的方法搜索T即可。
原理:若T在S中,则T必然是S的某个后缀的前缀。
例如:S = "leconte" T = "con",查找T是否在S中,则T(con)必然是S(leconte)的后缀之一"conte"的前缀。

(2)从目标串S中查找串T重复次数

方案:用S+'$'构造后缀树,搜索T节点下的叶节点数目即为重复次数
原理:如果T在S中重复了两次,则S应有两个后缀以T为前缀,重复次数就自然统计出来了。

(3)从目标串S中查找最长的重复子串(Finding the longest repeated substring)

方案:原理同2,具体做法就是找到最深的非叶节点。
这个深是指从root所经历过的字符个数,最深非叶节点所经历的字符串起来就是最长重复子串。
为什么要非叶节点呢?因为既然是要重复,当然叶节点个数要>=2。

(4)从目标串T和S中查找最长公共子串(Finding the longest common substr ing)

方案:将S1#S2$作为字符串压入后缀树,找到最深的非叶节点,且该节点的叶节点既有#也有$(无#)。

(5)从目标串T中查找最长的回文子串(Finding the longest palindrome in a string)

引用:

Pattern Searching | Set 8 (Suffix Tree Introduction)
Trie

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
29065 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20681 0
《机器学习实战》k最近邻算法(K-Nearest Neighbor,Python实现)
============================================================================================ 《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记,包含对其中算法的理解和算法的Pyt...
1742 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23576 0
+关注
sjf0115
Stay Hungry, Stay Foolish---我们必须用谦虚者的自觉,饥饿者的渴望的求职态度,来拥抱我们的未来。
788
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载