介绍后缀树(Suffix Tree)

yuanhsh

浏览: 555824 次
性别:
来自: 上海

最近访客更多访客>>

loginboot

Michael_113

z164974775

梦风云

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Data Structure

The following is an attempt to describe the Ukkonen algorithm by first showing what it does when the string is simple (i.e. does not contain any repeated characters), and then extending it to the full algorithm.

First, a few preliminary statements.

What we are building, is basically like a search trie. So there is a root node, edges going out of it leading to new nodes, and further edges going out of those, and so forth
But: Unlike in a search trie, the edge labels are not single characters. Instead, each edge is labeled using a pair of integers [from,to]. These are pointers into the text. In this sense, each edge carries a string label of arbitrary length, but takes only O(1) space (two pointers).

Basic principle

I would like to first demonstrate how to create the suffix tree of a particularly simple string, a string with no repeated characters:

abc

The algorithm works in steps, from left to right. There is one step for every character of the string. Each step might involve more than one individual operation, but we will see (see the final observations at the end) that the total number of operations is O(n).

So, we start from the left, and first insert only the single character a by creating an edge from the root node (on the left) to a leaf, and labeling it as [0,#], which means the edge represents the substring starting at position 0 and ending at the current end. I use the symbol # to mean the current end, which is at position 1 (right after a).

So we have an initial tree, which looks like this:

And what it means is this:

Now we progress to position 2 (right after b). Our goal at each step is to insert all suffixes up to the current position. We do this by

expanding the existing a-edge to ab
inserting one new edge for b

In our representation this looks like

enter image description here

And what it means is:

We observe two things:

The edge representation for ab is the same as it used to be in the initial tree: [0,#]. Its meaning has automatically changed because we updated the current position # from 1 to 2.
Each edge consumes O(1) space, because it consists of only two pointers into the text, regardless of how many characters it represents.

Next we increment the position again and update the tree by appending a c to every existing edge and inserting one new edge for the new suffix c.

In our representation this looks like

And what it means is:

We observe:

The tree is the correct suffix tree up to the current position after each step
There are as many steps as there are characters in the text
The amount of work in each step is O(1), because all existing edges are updated automatically by incrementing #, and inserting the one new edge for the final character can be done in O(1) time. Hence for a string of length n, only O(n) time is required.

First extension: Simple repetitions

Of course this works so nicely only because our string does not contain any repetitions. We now look at a more realistic string:

abcabxabcd

It starts with abc as in the previous example, then ab is repeated and followed by x, and then abc is repeated followed by d.

Steps 1 through 3: After the first 3 steps we have the tree from the previous example:

Step 4: We move # to position 4. This implicitly updates all existing edges to this:

and we need to insert the final suffix of the current step, a, at the root.

Before we do this, we introduce two more variables (in addition to #), which of course have been there all the time but we haven't used them so far:

The active point, which is a triple (active_node,active_edge,active_length)
The remainder, which is an integer indicating how many new suffixes we need to insert

The exact meaning of these two will become clear soon, but for now let's just say:

In the simple abc example, the active point was always (root,'\0x',0), i.e. active_nodewas the root node, active_edge was specified as the null character '\0x', and active_length was zero. The effect of this was that the one new edge that we inserted in every step was inserted at the root node as a freshly created edge. We will see soon why a triple is necessary to represent this information.
The remainder was always set to 1 at the beginning of each step. The meaning of this was that the number of suffixes we had to actively insert at the end of each step was 1 (always just the final character).

Now this is going to change. When we insert the current final character a at the root, we notice that there is already an outgoing edge starting with a, specifically: abca. Here is what we do in such a case:

We do not insert a fresh edge [4,#] at the root node. Instead we simply notice that the suffix a is already in our tree. It ends in the middle of a longer edge, but we are not bothered by that. We just leave things the way they are.
We set the active point to (root,'a',1). That means the active point is now somewhere in the middle of outgoing edge of the root node that starts with a, specifically, after position 1 on that edge. We notice that the edge is specified simply by its first character a. That suffices because there can be only one edge starting with any particular character (confirm that this is true after reading through the entire description).
We also increment remainder, so at the beginning of the next step it will be 2.

Observation: When the final suffix we need to insert is found to exist in the tree already, the tree itself is not changed at all (we only update the active point and remainder). The tree is then not an accurate representation of the suffix tree up to the current position any more, but itcontains all suffixes (because the final suffix a is contained implicitly). Hence, apart from updating the variables (which are all of fixed length, so this is O(1)), there was no work done in this step.

Step 5: We update the current position # to 5. This automatically updates the tree to this:

And because remainder is 2, we need to insert two final suffixes of the current position: ab and b. This is basically because:

The a suffix from the previous step has never been properly inserted. So it has remained, and since we have progressed one step, it has now grown from a to ab.
And we need to insert the new final edge b.

In practice this means that we go to the active point (which points to behind the a on what is now the abcab edge), and insert the current final character b. But: Again, it turns out that b is also already present on that same edge.

So, again, we do not change the tree. We simply:

Update the active point to (root,'a',2) (same node and edge as before, but now we point to behind the b)
Increment the remainder to 3 because we still have not properly inserted the final edge from the previous step, and we don't insert the current final edge either.

To be clear: We had to insert ab and b in the current step, but because ab was already found, we updated the active point and did not even attempt to insert b. Why? Because if ab is in the tree, every suffix of it (including b) must be in the tree, too. Perhaps only implicitly, but it must be there, because of the way we have built the tree so far.

We proceed to step 6 by incrementing #. The tree is automatically updated to:

Because remainder is 3, we have to insert abx, bx and x. The active point tells us where abends, so we only need to jump there and insert the x. Indeed, x is not there yet, so we split the abcabx edge and insert an internal node:

The edge representations are still pointers into the text, so splitting and inserting an internal node can be done in O(1) time.

So we have dealt with abx and decrement remainder to 2. Now we need to insert the next remaining suffix, bx. But before we do that we need to update the active point. The rule for this, after splitting and inserting an edge, will be called Rule 1 below, and it applies whenever the active_node is root (we will learn rule 3 for other cases further below). Here is rule 1:

After an insertion from root,

active_node remains root
active_edge is set to the first character of the new suffix we need to insert, i.e. b
active_length is reduced by 1

Hence, the new active-point triple (root,'b',1) indicates that the next insert has to be made at the bcabx edge, behind 1 character, i.e. behind b. We can identify the insertion point in O(1) time and check whether x is already present or not. If it was present, we would end the current step and leave everything the way it is. But x is not present, so we insert it by splitting the edge:

Again, this took O(1) time and we update remainder to 1 and the active point to (root,'x',0) as rule 1 states.

But there is one more thing we need to do. We'll call this Rule 2:

If we split an edge and insert a new node, and if that is not the first node created during the current step, we connect the previously inserted node and the new node through a special pointer, a suffix link. We will later see why that is useful. Here is what we get, the suffix link is represented as a dotted edge:

We still need to insert the final suffix of the current step, x. Since the active_length component of the active node has fallen to 0, the final insert is made at the root directly. Since there is no outgoing edge at the root node starting with x, we insert a new edge:

As we can see, in the current step all remaining inserts were made.

We proceed to step 7 by setting #=7, which automatically appends the next character, a, to all leaf edges, as always. Then we attempt to insert the new final character to the active point (the root), and find that it is there already. So we end the current step without inserting anything and update the active point to (root,'a',1).

In step 8,, #=8, we append b, and as seen before, this only means we update the active point to (root,'a',2) and increment remainder without doing anything else, because b is already present. However, we notice (in O(1) time) that the active point is now at the end of an edge. We reflect this by re-setting it to (node1,'\0x',0). Here, I use node1 to refer to the internal node the ab edge ends at.

Then, in step #=9, we need to insert 'c' and this will help us to understand the final trick:

Second extension: Using suffix links

As always, the # update appends c automatically to the leaf edges and we go to the active point to see if we can insert 'c'. It turns out 'c' exists already at that edge, so we set the active point to (node1,'c',1), increment remainder and do nothing else.

Now in step #=10, remainder is 4, and so we first need to insert abcd (which remains from 3 steps ago) by inserting d at the active point.

Attempting to insert d at the active point causes an edge split in O(1) time:

The active_node, from which the split was initiated, is marked in red above. Here is the final rule,Rule 3:

After splitting an edge from an active_node that is not the root node, we follow the suffix link going out of that node, if there is any, and reset the active_node to the node it points to. If there is no suffix link, we set the active_node to the root. active_edge and active_lengthremain unchanged.

So the active point is now (node2,'c',1), and node2 is marked in red below:

Since the insertion of abcd is complete, we decrement remainder to 3 and consider the next remaining suffix of the current step, bcd. Rule 3 has set the active point to just the right node and edge so inserting bcd can be done by simply inserting its final character d at the active point.

Doing this causes another edge split, and because of rule 2, we must create a suffix link from the previously inserted node to the new one:

We observe: Suffix links enable us to reset the active point so we can make the next remaining insert at O(1) effort. Look at the graph above to confirm that indeed node at label ab is linked to the node at b (its suffix), and the node at abc is linked to bc.

The current step is not finished yet. remainder is now 2, and we need to follow rule 3 to reset the active point again. Since the current active_node (red above) has no suffix link, we reset to root. The active point is now (root,'c',1).

Hence the next insert occurs at the one outgoing edge of the root node whose label starts with c:cabxabcd, behind the first character, i.e. behind c. This causes another split:

And since this involves the creation of a new internal node,we follow rule 2 and set a new suffix link from the previously created internal node:

(I am using Graphviz Dot for these little graphs. The new suffix link caused dot to re-arrange the existing edges, so check carefully to confirm that the only thing that was inserted above is a new suffix link.)

With this, remainder can be set to 1 and since the active_node is root, we use rule 1 to update the active point to (root,'d',0). This means the final insert of the current step is to insert a single d at root:

That was the final step and we are done. There are number of final observations, though:

In each step we move # forward by 1 position. This automatically updates all leaf nodes in O(1) time.
But it does not deal with a) any suffixes remaining from previous steps, and b) with the one final character of the current step.
remainder tells us how many additional inserts we need to make. These inserts correspond one-to-one to the final suffixes of the string that ends at the current position #. We consider one after the other and make the insert. Important: Each insert is done in O(1) time since the active point tells us exactly where to go, and we need to add only one single character at the active point. Why? Because the other characters are contained implicitly (otherwise the active point would not be where it is).
After each such insert, we decrement remainder and follow the suffix link if there is any. If not we go to root (rule 3). If we are at root already, we modify the active point using rule 1. In any case, it takes only O(1) time.
If, during one of these inserts, we find that the character we want to insert is already there, we don't do anything and end the current step, even if remainder>0. The reason is that any inserts that remain will be suffixes of the one we just tried to make. Hence they are all implicitin the current tree. The fact that remainder>0 makes sure we deal with the remaining suffixes later.
What if at the end of the algorithm remainder>0? This will be the case whenever the end of the text is a substring that occurred somewhere before. In that case we must append one extra character at the end of the string that has not occurred before. In the literature, usually the dollar sign $ is used as a symbol for that. Why does that matter? --> If later we use the completed suffix tree to search for suffixes, we must accept matches only if they end at a leaf. Otherwise we would get a lot of spurious matches, because there are many strings implicitlycontained in the tree that are not actual suffixes of the main string. Forcing remainder to be 0 at the end is essentially a way to ensure that all suffixes end at a leaf node. However, if we want to use the tree to search for general substrings, not only suffixes of the main string, this final step is indeed not required, as suggested by the OP's comment below.
So what is the complexity of the entire algorithm? If the text is n characters in length, there are obviously n steps (or n+1 if we add the dollar sign). In each step we either do nothing (other than updating the variables), or we make remainder inserts, each taking O(1) time. Since remainder indicates how many times we have done nothing in previous steps, and is decremented for every insert that we make now, the total number of times we do something is exactly n (or n+1). Hence, the total complexity is O(n).
However, there is one small thing that I did not properly explain: It can happen that we follow a suffix link, update the active point, and then find that its active_length component does not work well with the new active_node. For example, consider a situation like this:

(The dashed lines indicate the rest of the tree. The dotted line is a suffix link.)

Now let the active point be (red,'d',3), so it points to the place behind the f on the defgedge. Now assume we made the necessary updates and now follow the suffix link to update the active point according to rule 3. The new active point is (green,'d',3). However, the d-edge going out of the green node is de, so it has only 2 characters. In order to find the correct active point, we obviously need to follow that edge to the blue node and reset to (blue,'f',1).

In a particularly bad case, the active_length could be as large as remainder, which can be as large as n. And it might very well happen that to find the correct active point, we need not only jump over one internal node, but perhaps many, up to n in the worst case. Does that mean the algorithm has a hidden O(n²) complexity, because in each step remainder is generally O(n), and the post-adjustments to the active node after following a suffix link could be O(n), too?

No. The reason is that if indeed we have to adjust the active point (e.g. from green to blue as above), that brings us to a new node that has its own suffix link, and active_length will be reduced. As we follow down the chain of suffix links we make the remaining inserts, active_length can only decrease, and the number of active-point adjustments we can make on the way can't be larger than active_length at any given time. Since active_length can never be larger than remainder, and remainder is O(n) not only in every single step, but the total sum of increments ever made to remainder over the course of the entire process is O(n) too, the number of active point adjustments is also bounded by O(n).

中文翻译：

接下来我将通过一个简单的字符串（不包含重复的字符）来试着分析Ukkonen算法，接着来讲述完整的算法框架。

首先，一点简单的事前描述

1. 我们构建的是一个简单的类似搜索字典类（search trie）结构，所以存在一个根节点（root node)。树的边（edges)指向一个新的节点，直到叶节点。

2. 但是，不同于搜索字典类（search trie)，边标签（edge label)不是单个字符，相反，每一个边被标记为一对整数[from, to]。这一对整数是输入字符串的索引(index）。这样，每一个边记录了任意长度的子字符（substring)，但是只需要O(1)空间复杂度（一对整数索引）。

基本约定

下面我将用一个没有重复字符的字符串来说明如何创建一颗后缀树(suffix tree):

abc

本算法将从字符串的左边向右边一步一步的执行。每一步处理输入字符串的一个字符，并且每一步抑或涉及不止一种的操作，但是所有的操作数和是O(n)时间复杂度的。

好，我们现在将字符串左边的a插入到后缀树，并且将此边标记为[0, #]，它的意思是此边代表了从索引0开始，在#索引结束的子字符串（我使用符号#表示当前结束索引，现在的值是1，恰好在a位置后面）。

所以，我们有初始化后的后缀树：

其意思是：

现在我们处理索引2，字符b。我们每步的目的是将所有后缀(suffixes）的结束索引更新当前的索引。我们可以这样做：

1. 拓展存在的a边，使其成为ab;

2. 为b插入一条新边。

然后变成这样：

其意思是：

我们观察到了二点：

表示ab的边同我们初始化的后缀树：[0, #]。它意味着将会自动改变，我们仅仅更新#，使其成为2即可；
每一步只需要O(1)的空间复杂度，因为我们只记录了一对整数索引而已。

接下来，我们继续自增#索引，现在我们需要插入字符c了。我们将c插入到后缀树中的每一条边，然后在为后缀c插入一条新边。

它们像下面：

其意思是：

我们注意到：

在每一步后，恰好都是一颗正确的后缀树;
总共需要字符串长度的数量的操作;
所有的操作都是O(1)。

第一次拓展：简单的重复字符串

上面的算法工作的非常正确，接下来我们来看看更加复杂的字符串：

abcabxabcd

步骤1至3：正如之前的例子：

步骤4：我们自增#到索引4。这将自动的更新所有已存在的边：

接着，我们需要将当前步骤的后缀a(suffix a), 插入到根节点。

在此之前，我们引入另外二个变量（不包括之前的变量#):

active point, 其实一个三元组(active_node, active_edge, active_length)；
remainder, 一个用来记录还有剩余多少新的后缀需要插入的整数数量。

这二个变量的准确意义将在后面愈来愈清楚，至于现在我们可以这样来解说：

在abc这个例子中，active point始终都是(root, None, 0), 其作用也就是说，如果有一条新边需要插入，那么都插入到根节点下。
remainder变量在每一步的开始都始终设为1。其意思是，我们必须要插入的后缀数量是1，也就是待插入单个字符本身。

现在这二个变量将有所改变。当我们在root节点插入当前的最后一个字符a时，我们注意到已经存在了一条以a开头的边了，它就是abca。所以，出现这种情况下，我们需要如下做：

我们不在根节点插入新的节点；
相反，我们注意到后缀a已经存在了我们的树中，所以我们不管它；
修改active point为（root， ‘a’, 1）。它的意思是现在active point如今指向从根节点出发的一条以a开头的边上，并且在索引1后面。
我们增加remainder的值，现在其为2了。

注意：当我们最后一个需要插入的后缀如果已经存在在这颗树种，那么我们什么都不做，只是更新active point和remainder即可。现在这棵树已经不在非常标准的后缀树了，但是它包含所有的后缀，只是最后一个后缀a被隐式的包含了。

步骤5：我们更新当前的索引#为5. 这将自动的进行如下更新：

因为remainder是2，我们需要插入二个当前索引的最后二个后缀：ab和b。这是因为：

上一步的后缀a并没有合适的插入，只是被隐式包含在abca边中。所以，它需要被保留，而且，在当前这步，它已经从a变成了ab了。
我们需要插入新的边b。

实际上，这意味着我们需到active point节点（它指向边abcab的索引1，在a的后面位置）插入最后字符b，但是恰好b也已经存在在同一条边了。

所以，我们什么也不做，仅仅：

更新active point为(root, ‘a’, 2)（同一个节点和边，但是我们指向b的后面，所以active point的长度变成了2，指向b的后面）
增加remainder为3，因为我们也没有插入。

当然，我们不得不在当前步骤插入ab和b，但是因为ab已经存在，所以我们更新active point并且我们不插入b。为什么？因为ab在这颗树中，那么它的每一个后缀必定存在这个树中。也许它是隐士被包含的，但是，它一定存在，因为我们是一步一步如此建这颗树的。

步骤6：增加#为6，这棵树自动更新为：

因为remainder是3，所以我们不得不插入abx，bx和x。active point告诉我们ab在哪里结束，所以我们仅仅只需要跳到此节点，然后插入x。更加准确的说，x如果也不存在，我们需要分隔边abcabx，并且插入一个内部节点：

边的表示还是用一对整数索引表示，所以分隔和插入只需要O(1)时间复杂度。

到目前为止，我们处理了后缀abx，并且remainder减少到了2. 好，我们还要继续插入接下来的后缀bx。但是在我们插入之前，我们需要更新active point。

这里有一个规则，其是在分隔和插入一条边后，叫做Rule1，它将起作用当active node是根节点时，至于其他的情况，我们有Rule3, 后面将会介绍。
这里是Rule1，在从root插入之后：

active_node 依然不变；
active_edge 被设置为下一个新后缀的第一个字符，本例中是b；
active_length 自减。

到现在为止，新active point三元组（root, ‘b’, 1）表示下一步插入将在边bcabx发生，本例中是在b的后面。我们检查x是否已经存在，如果存在，我们将结束当前步骤，什么都不做；如果不存在，我们分隔此边，插入该字符。

它将花费O(1)的时间，更新remainder为1，并且根据Rule1更新active point为(root, ‘x’, 0）。

我们还有其他事需要做，接着我们介绍Rule2:

如果我们分隔一条边并且插入一个新的节点，而且这个新的节点不是在当前步骤中第一个新的节点，我们需要将之前创建的节点指向这个新创建的节点，这条边称为 suffix link。我们将在后面发现其非常有用，这里使用虚线表示 suffix link。

在插入后缀bx后，加上suffix link后：

到这里，我们还有后缀x还没有插入。因为active point(root, ‘x’, 0）中active_length是0，所以，最后一个后缀x直接从root插入，因为这里没有一个边以x作为前缀。

从上图看，之前遗留的三个后缀abx，bx和x已悉数插入。

步骤7：更新#为7，其将自动的添加下一个字符a到所有的叶边（leaf edges). 然后，我们试着插入新的最后字符到active point（root，’x', 0），但是发现字符a已经存在，所以我们什么也不做，只是更新active point为（root, ‘a’, 1)和自增remainder，此时为2。

步骤8：#=8，我们需要插入ab和b，因为remainder为2。我们插入ab，正如之前的例子，这个也只需要更新update point为(root, ‘a’, 2）即可，并且自增remainder，因为b已经。这是我们发现active point现在处于一条边的终端。我们设此节点为node1，然后active point可以变为（node1， None， 0）。这里我使用node1表示边ab的终结点。

步骤9：#=9，我们将要理解后缀树中最后一个难点。

第二次拓展：使用suffix link

现在，#已经更新到了字符c，它将会自动的添加到叶边（leaf edges),并且我们跳到active point是否我们能插入字符c。结果被证明c已经存在，所以我们设active point为(node1, ‘c’, 1)，自增remainder，不需要做什么。

步骤10：经过几步的自增remainder，现在其值已经是4.所以在步骤10，我们首先需要通过向active point插入d来实现插入abcd（其值追溯到前三步，它们分别插入abc）.

将d插入到active point。