String index structure: suffix automaton

Suffix automaton

Deterministic acyclic finite state automaton,也叫directed acyclic word graph(DAWG),是一个识别若干字串的无环DFA。识别若干字串的所有DAWG中,存在唯一一个状态数最少的DAWG,称作minimal DAWG,即识别这个字串集的DFA。

DAWG在有些文献中也指识别一个字串的所有后缀的自动机,这种用法有个更常见的名称:suffix automaton,此时该自动机可以看做是字串所有后缀的DAWG。

定义

  • Factor,即子串。

  • $\mathit{factor}(z)$,$z$的所有子串。比如$\mathit{factor}(ab)={\epsilon,a,b,ab}$。

  • $\mathit{suff}(z)$表示$z$的所有后缀的集合。比如$\mathit{suff}(abc)={abc,bc,c,\epsilon}$。

  • $R_w(z)$表示$w$中$z$所有出现位置右边的串的集合。比如对于$w=”abcde”$,其$R_w(“bc”)=”de”$。

  • $u \equiv_w v$表示$w$中$u$和$v$的出现位置集合相同,即$R_w(u)=R_w(v)$。

  • $s_w(z)$为串$w$中子串$z$的suffix function:$z$的最长后缀$y$,满足$y \not\equiv_w z$。
    $s_w(\epsilon)$无定义。当$s_w$定义在$w$的所有后缀上时就得到了suffix link,因此suffix function是suffix link的推广,用于处理factor的集合。

  • 用上标表示函数应用的次数,即$s_w^0(z)=z$,$s_w^1(z)=s_w(z)$,$s_w^2(z)=s_w(s_w(z))$……

一些引理

在考虑$w$时,对于$w$的两个子串$u$和$v$,定义$u$和$v$在一个集合中当且仅当$R_w(u)\equiv R_w(v)$,把$Rw(u)$看作一个状态。
添加一个新字符后,易知会产生一个新状态$R
{wa}={\epsilon}$,因为它与已有的集合都不相同。
下面的三条引理说明了添加字符后,$R{w}$集合是如何演变为$R{wa}$的,从而知道大多数状态不会发生变化,状态不会合并,且最多只有一个状态会分裂成两个。

引理1

给$w$添加字符$a$后$R{wa}$的变化:
$$
R
{wa}(u) = \begin{cases}
{\epsilon} \cup R_w(u), & \text{if } u \text{ is a suffix of } wa\
R_w(u), & \text{otherwise}
\end{cases}
$$

对于$w$的一个子串$x$,若$x$的最后一个字符不是$a$,则添加字符后$x$所属状态没有发生变化。

引理2

令$z$为在$w$中出现过的$wa$的最长后缀,那么对于$w$的任意两个子串$u,v$:
$$
u \equiv_w v, not (u \equivw z) \implies u \equiv{wa} v
$$

证明:

  • 若$u \in \mathit{suff}(wa)$,则$u$是$w$中出现过的$wa$的一个后缀,由$z$定义知$u \in \mathit{suff}(z)$。
  • 存在最大的非负整数$i$使得$|u| \leq |s_w^i(z)|$,
    由$s_w$性质有$u \equiv_w s_w^i(z)$,
    又$u \equiv_w v$,故$v \equiv_w s_w^i(z)$。
    因此$v \in \mathit{suff}(z)$即$v \in \mathit{suff}(wa)$。
  • 因此$u \in \mathit{suff}(wa) \implies v \in \mathit{suff}(wa)$。对称地,$v \in \mathit{suff}(wa) \implies u \in \mathit{suff}(wa)$。
    所以$u$和$v$同时在$\mathit{suff}(wa)$中或同时不在。
  • 根据引理1,即$R_{wa}$与$Rw$的关系知$R{wa}(u)=R_{wa}(v)$。

这条引理说明,对于$wa$的一个后缀$x$,若$x \not\equiv_w z$,则添加字符后$x$所属状态没有发生变化。

引理3

依旧令$z$表示在$w$中出现过的$wa$的最长后缀。

下面的引理则说明,$w$中与$z$等价的集合,在$w$末尾添加新字符$a$后是怎样变化的:

  • $u \equivw z, |u| \leq |z| \implies u \equiv{wa} z$。

    • 由引理1和$z \in \mathit{suff}(wa)$知$R{wa}(z) = {\epsilon} \cup R{w}(z)$
    • 由$|u| \leq |z|$知$u \in \mathit{suff}(z)$,故$u \in \mathit{suff}(wa)$。因此$R{wa}(u) = {\epsilon} \cup R{u}$
    • 前两式得$R{wa}(z) = R{wa}(u)$
  • $u \equivw z, |u| > |z| \implies u \equiv{wa} z’$,其中$z’$为满足$z’ \equiv_w z$的$w$中最长子串,且不是$wa$的后缀。

    • $u$和$z’$都不是$wa$的后缀
    • $R{wa}(u) = R{w}(u) = Rw(z’) = R{wa}(z’)$

如果第二个分类不为空,则$w$中与$z$等价的集合会分裂成两个集合:$z$的等价类和$z’$的等价类,从而多出一个状态。

性质

长度$n$为1的串的suffix automaton,其状态数为2。新增字符$a$后,会多出一个新状态$R_{wa}$。根据引理3,$z$所属状态可能会分裂成两个状态。因此添加一个字符会使状态数增加1或2。对于$n>1$,suffix automaton的状态数$\mathit{st}(y)\le 3+2(n-2)=2n-1$。而状态数的下界为$n+1$,当串$y$为全a时即可取到下界。

另外对于$n>2$,边数的下界为$n$,上界为$3n-4$。

记$f_y(p)$为$p$节点的suffix function,它表示$s_y(u)$的等价类,其中$u$是$p$表示的等价类中的任意一个串。

构建

采用一个在线算法构建字串$y$的suffix automaton,从从空串对应的suffix automaton(仅含一个顶点)出发,逐个添加$y$中的字符。维护变量$\mathit{last}$表示最后添加的顶点,它表示当前已添加的字串$w$的所属状态。
每个状态$x$记录$f(x)$,表示$x$表示的串的suffix function对应的状态。另外记录$l(x)$,表示$x$的等价类中最长串的长度。

添加字符$a$时有下面两种情况:

  • $a$未在$w$中出现
    只多了一个状态$R_{wa}$,该状态的suffix function为起始状态。
    $w$所有后缀的状态都应添加在字符$a$上的转移,指向新状态。方法是从$\mathit{last}$出发,追溯$\mathit{SP}(\mathit{last})$得到的所有状态都添加指向新状态的边。

  • $a$在$w$中出现
    从$\mathit{last}$出发,追溯$\mathit{SP}(\mathit{last})$,直到遇到第一个顶点$p$存在字符$a$上的转移,设转移到$q$。
    $p$表示的最长串(长度为$l(p)$)后添加$a$就是$z$(长度为$l(p)+1$)。
    $q$的等价类则表示$w$中与$z$等价的所有$u$。
    然后再分两种情况:

    • 若$l(p)+1=l(q)$,则$z$的长度大于等于$w$中与$z$等价的任一$u$。$z$的等价类(表示为状态$q$)不会分裂。Suffix automaton只多了一个表示$wa$等价类的状态$x$,$l(x)=|wa|$,其$R{wa}(wa)={\epsilon}$,包含与$R{wa}(q)={\epsilon} \cup R_{w}(q)$,因此设置$f(x)=q$。
    • 若$l(p)+1 l(p)+1=|z|$,$q$需要拆分为两个状态,分别表示$z’$(状态$q$)和$z$(新状态$v$),$v$继承$q$的所有边,$l(v)=l(p)+1$,$f(q)$需要修改为$v$。另外还要沿着$SP(p)$,把沿路状态在$a$上的转移改为$v$。

稍作修改该算法即可用于多串suffix automaton的构建。处理新字串时,把$\mathit{last}$重置为起始状态,每次添加字符时,转移至的状态可能已在automaton中,无需创建。添加完字符后,$\mathit{last}$可能有两种取值,需要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct Node
{
Node *f, *c[26];
int len;
} pool[2*N], *tail, *pit;
void extend(int c)
{
bool created = false;
Node *p = tail, *x;
if (p->c[c])
x = p->c[c];
else {
created = true;
x = pit++;
x->len = p->len+1;
for (; p && ! p->c[c]; p = p->f)
p->c[c] = x;
}
if (! p)
x->f = pool;
else if (p->len+1 == p->c[c]->len) {
if (created)
x->f = p->c[c];
} else {
Node *q = p->c[c], *r = pit++;
*r = *q;
r->len = p->len+1;
for (; p && p->c[c] == q; p = p->f)
p->c[c] = r;
q->f = r;
if (created)
x->f = r;
else
x = r;
}
tail = x;
}
{
// string 0
tail = pool;
extend(0); extend(1); extend(2);
// string 1
tail = pool;
extend(0); extend(2); extend(2);
// string 2
tail = pool;
extend(2); extend(1); extend(1);
}

性质

  • 另$SP(p)$表示从$p$开始,沿著$f$函数回溯得到的所有状态,accepting states是$SP(last)$。

  • Suffix automaton中所有边$(u, s_w(u))$形成一棵spanning tree。

  • $|s_w(u)| < |u|$,所以对于suffix automaton中任意顶点$p$,$l(f(p)) < l(p)$

  • 对于边$(p,q)$,$l(p)+1 \leq l(q)$,所以可以对所有顶点的$l$值做计数排序,达到拓扑排序的效果。

辅助数据结构

设$p=\delta(q_0, x)$有定义(在自动机中),

$maxContext(p)$表示$p$对应的$R_y(x)$集合中的最长串长度,即第一次出现的位置的右边串长度。计算方式如下:

$$maxContext(p)=\begin{cases}
0, & \text{if } deg(p) = 0 \
\max_{(p,q) \in F}{1 + maxContext(q)}, & otherwise
\end{cases}$$

$n-maxContext(p)-|x|$是$x$第一次出现的位置。

$minContext(p)$表示$p$对应的$R_y(x)$集合中的最短串长度,即最后一次出现的位置的右边串长度。计算方式如下:

$$minContext(p)=\begin{cases}
0, & \text{if } p \in [last,f(last),f^2(last),\ldots] \
\min_{(p,q) \in F}{1 + minContext(q)}, & otherwise
\end{cases}$$

$n-minContext(p)-|x|$是$x$最后一次出现的位置。

$$cnt(p)=\begin{cases}
1, & \text{if } deg(p) = 0 \
\sum_{(p, q) \in F}{cnt(q)}, & otherwise
\end{cases}$$

$cnt(p)$是$x$在串里的出现次数。

对所有状态拓扑排序后,根据其逆序计算即可求出各个状态的$maxContext$、$minContext$和$cnt$值。

应用

  • 列出模式串在文本串中所有匹配位置(all occurrences)。
  • 求出最长的出现至少$k$次的子串。寻找最深的节点$x$满足$cnt(x)>=k$,其深度即为答案。
  • Ending factors。给定两个串$x$和$y$,对于$x$的所有前缀$p$,求出$p$的最长后缀为$y$的子串。可用于计算两串的最长公共子串。
  • Searching for rotations。给定两个串$x$和$y$,$x$的任意rotation(或称为conjugate)在$y$中出现的位置。技巧是把$x$和自身拼接,得到$xx$,它包含$x$的$|x|$个rotation,转化为$xx$和$y$的ending factors问题。
  • $n$个串的最长公共子串。求$n-1$次ending factors。

相关数据结构

Factor automaton

Suffix automaton有个类似的数据结构,称作factor automaton,它识别一个字串的所有子串,可以看作识别所有子串的minimal DAWG。

求出$S$的suffix automaton后,把所有状态标记为accept state后就得到了识别所有子串的DAWG,但可能不是最简的,做minimize即可得到factor automaton,而acyclic DFA可以用Revuz’s algorithm在$O(状态数+边数+|字符集|)$时间内求最简表示。

反过来,可以通过factor automaton获得suffix automaton。参见Maxime Crochemore、Christophe Hancart的《Automata for Matching Patterns》中的FA-to-SA。

Suffix oracle和factor oracle

Suffix oracle是一种简化的suffix automaton。

某次添加字符$a$时,令$z$表示在$w$中出现过的$wa$的最长后缀,如果存在$u \equiv_w z, |u| > |z|$,那么suffix automaton中会进行状态分裂,而factor oracle不分裂,相当于把两个状态合并了。

Suffix oracle可以看作是suffix automaton合并了一些状态后得到的自动机。其接受的串的集合是suffix automaton接受的串的集合的超集,也就是说它不会遗漏suffix automaton接受的串,但可能会有误判。

Suffox oracle的优点是节点数为$n+1$,比最坏情况下的suffix automaton大致少一半。边数为$n$到$2n-1$。

把suffix oracle的所有状态标记为可接受即得到factor oracle,且已是最简形态,无法minimize。

其他类似数据结构

Position heap

比suffix tree简单,存在一个$O(n\log n)$离线构造算法,但实现复杂度不比suffix automaton低。

参考文献

Allauzen C., Crochemore M., Raffinot M., Factor oracle: a new structure for pattern matching; Proceedings of SOFSEM’99; Theory and Practice of Informatics.

@article{Revuz:1992:MAD:135853.135907,
author = {Revuz, Dominique},
title = {Minimisation of Acyclic Deterministic Automata in Linear Time},
journal = {Theor. Comput. Sci.},
issue_date = {Jan. 6, 1992},
volume = {92},
number = {1},
month = jan,
year = {1992},
issn = {0304-3975},
pages = {181–189},
numpages = {9},
url = {http://dx.doi.org/10.1016/0304-3975(92)90142-3},
doi = {10.1016/0304-3975(92)90142-3},
acmid = {135907},
publisher = {Elsevier Science Publishers Ltd.},
address = {Essex, UK},
}