Suffix Trie
:
又称后缀Trie或后缀树。它与Trie树的最大不同在于,后缀Trie的字符串集合是由指定字符串的后缀子串构成的。比如、完整字符串"minimize"的后缀子串组成的集合S分别如下:
s1=minimize
s2=inimize
s3=nimize
s4=imize
s5=mize
s6=ize
s7=ze
s8=e
然后把这些子串的公共前缀作为内部结点构成一棵"minimize"的后缀树,如图所示,其中上图是Trie树的字符表示,下图是压缩表示(详细见《Trie树
》)。可见Suffic Trie是一种很适合操作字符串子串的数据结构。
它和PAT tree在这一点上类似。
Suffix Trie的创建
标准Tire树的每一个内部结点只有一个字符,也就是说公共前缀每一次只找一个。而Suffix Trie的公共前缀可以是多个字符,因此在创建Suffix Trie的时候,每插入一个后缀子串,就可能对内部结点造成一次分类。下面我们我们看一种后缀树构造算法。以"minimize"为例:
当插入子串时,发现叶子结点中的关键字与子串有公共前缀,则需要将该叶子结点分裂。如上图第3到4步。否则,重新创建一个叶子结点来存放后缀,如上图第1到2步
Suffix Trie的子串查询
如果在后缀树T中查找子串P,我们需要这样的过程:
(1) 从根结点root出发,遍历所有的根的孩子结点:N1,N2,N3....
(2) 如果所有孩子结点中的关键字的第一个字符都和P的第一个字符不匹配,则没有这个子串,查找结束。
(3) 假如N3结点的关键字K3第一个字符与P的相同,则匹配K3和P。
若 K3.length>=P.length 并且K3.subString(0,P.length-1)=P,则匹配成功,否则匹配失败。
若 K3.length<=P.length 并且K3=P.subString(0, K3.length-1),则将子串P1=P.subString(K3.length, P.length); 即取出P中排除K3之后的子串。然后P1以N3为根结点继续重复(1)~(3)的步骤。直到匹配完P1的所有字符,则匹配成功。否则匹配失败。
查询效率:很显然,在上面的算法中。匹配成功正好比较了P.length次字符。而定位结点的孩子指针,和Trie情况类似,假如字母表数量为d。则查询效率为O(d*m),实际上,d是固定常数,如果使用Hash表直接定位,则d=1.
因此,后缀树查询子串P的时间复杂度为O(m),其中m为P的长度。
Suffix Trie的应用
标准Trie树只适合前缀匹配和全字匹配,并不适合后缀和子串匹配。而后缀树在这方面则非常合适。
另外后缀树也可以进行前缀匹配。
如果模式串P是字符串S的前缀的话,那么从根结点出发遍历后缀树,一定能够寻找到一条路径完全匹配完P。比如上图: 模式串P=“mini”,主串S="minimize"。P从根节点出发,首先匹配到结点mi,然后再匹配孩子结点nimize。直到P中所有的字符都找到为止。所以P是S的前缀。
分享到:
相关推荐
后缀tire树(tire图),用于多字符串匹配。
...关于string的小结 kmp extend_kmp ac+trie 后缀数组
...var trie = new UkkonenTrie ( 3 );// var trie = new SuffixTrie(3);trie . Add ( " hello " , 1 );trie . Add ( " world " , 2 );trie . Add ( " hell " , 3 );var result = trie . Retrieve ( " hel " );更新...
KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。KMP算法由D.E.Knuth,J.H.Morris和V.R.Pratt在 Brute-Force算法的基础上提出的模式匹配的改进算法。因此人们称它为...
Martin Farach-colton Suffix tree slide。 最详尽深刻易懂的后缀树讲义。五星推荐。
Boyer Moore 算法是字符串匹配(模式搜索)的主要高效算法之一。 Boyer-Moore(BM)算法被认为最高效的字符串搜索算法,它由Bob Boyer和J Strother Moore于1977年设计实现。通常情况下,Boyer Moore 算法比KMP算法...
针对目前程序动态度量研究...采用后缀树结构设计实时特征度量匹配算法(feature matching with updating suffix tree,FMUS),实现了程序运行过程中的实时特征匹配。实验表明,该方法具有较高的准确率和低时间耗费比。
suffix tree is very good,i like it
matlab开发-SuffixArray。目的是说明后缀数组的计算。这不包括搜索操作。
suffix tree源代码,有注释!大家一起努力学习吧
后缀树是类似字符串处理的有用的数据结构和算法。
Js Suffix Trie 是一个后缀 trie 实现,最初是用编写的,但也可以使用 JavaScript 编译。 您可以安装来编译 CoffeeScript,使用或尝试在线转换器。 关于后缀尝试 后缀树(不要与后缀树混淆)以树状方式存储唯一的...
Constructing Compressed Suffix Arrays with Large Alphabets 生物信息论文
后缀 使用后缀尝试重新组合文本片段的简单示例 要使用 Java 7 进行编译,请从 src 目录执行以下操作 javac片段/提交/ Keexa.java 然后运行 java片段/提交/ Keexa YOUR_TEXT_FILE.txt YOUR_TEXT_FILE.txt 的一个...
正常来说暴力的思路是先匹配前缀pre和后缀suf,找到第一个不匹配的l和r,然后在由l开始从左向右求最长的回文串palindrome,以及由r开始从右向左求最长的回文串palindrome,那么pre+palindrome+suf就是答案。...
SuffixArray 扩展(以单词为单位) 源码
适用于Python的公共后缀... 此模块将公共后缀列表构建为Trie结构,从而使其比用于相同目的的其他基于字符串的模块更有效。 它可以在大规模分布式环境(例如PySpark)中有效使用。 该Python模块随附了公共后缀列表(P
A new method for on-line string searches by U. Manber and G. Myers(1993) Simple linear work suffix array construction by J. Karkkainen and P. Sanders(2002)
CSA是SA(suffix-array)的隐式表达,具有快速模式匹配的能力,占用空间小。 你可以为一个文档建立一个 CSA 索引,然后你主要有以下操作:计数:计算文档中出现了多少个模式。 定位:定位所有图案出现的位置。 解压:...