【串和序列处理 4】Suffix Trie 子串匹配结构

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的前缀。

 

 

评论

2 楼 漂泊一剑客 2014-11-08  

对啊， 想这样我们可以直接用正则表达式匹配的， 这种算法与正则表达式有什么关系吗，是不是java的正则表达式就是用这种算法实现的？

1 楼 maxint 2010-08-07  

找到另一个不错学习资源，其中提到了正则表达式应用
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic7/