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,即子串。

  • 的所有子串。比如

  • 表示的所有后缀的集合。比如

  • 表示所有出现位置右边的串的集合。比如对于,其

  • 表示的出现位置集合相同,即

  • 为串中子串的suffix function:的最长后缀,满足无定义。当定义在的所有后缀上时就得到了suffix link,因此suffix function是suffix link的推广,用于处理factor的集合。

  • 用上标表示函数应用的次数,即……

一些引理

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

引理1

添加字符的变化:

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

引理2

为在中出现过的的最长后缀,那么对于的任意两个子串

证明:

  • ,则中出现过的的一个后缀,由定义知
  • 存在最大的非负整数使得, 由性质有, 又,故。 因此
  • 因此。对称地,。 所以同时在中或同时不在。
  • 根据引理1,即的关系知

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

引理3

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

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

    • 由引理1和
    • ,故。因此
    • 前两式得
  • ,其中为满足中最长子串,且不是的后缀。

    • 都不是的后缀

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

性质

长度为1的串的suffix automaton,其状态数为2。新增字符后,会多出一个新状态。根据引理3,所属状态可能会分裂成两个状态。因此添加一个字符会使状态数增加1或2。对于,suffix automaton的状态数。而状态数的下界为,当串为全a时即可取到下界。

另外对于,边数的下界为,上界为

节点的suffix function,它表示的等价类,其中表示的等价类中的任意一个串。

构建

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

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

  • 未在中出现 只多了一个状态,该状态的suffix function为起始状态。 所有后缀的状态都应添加在字符上的转移,指向新状态。方法是从出发,追溯得到的所有状态都添加指向新状态的边。

  • 中出现 从出发,追溯,直到遇到第一个顶点存在字符上的转移,设转移到表示的最长串(长度为)后添加就是(长度为)。 的等价类则表示中与等价的所有。 然后再分两种情况:

    • ,则的长度大于等于中与等价的任一的等价类(表示为状态)不会分裂。Suffix automaton只多了一个表示等价类的状态,其,包含与,因此设置
    • ,则存在需要拆分为两个状态,分别表示(状态)和(新状态),继承的所有边,需要修改为。另外还要沿着,把沿路状态在上的转移改为

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

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);
}

性质

  • 表示从开始,沿著函数回溯得到的所有状态,accepting states是

  • Suffix automaton中所有边形成一棵spanning tree。

  • ,所以对于suffix automaton中任意顶点

  • 对于边,所以可以对所有顶点的值做计数排序,达到拓扑排序的效果。

辅助数据结构

有定义(在自动机中),

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

第一次出现的位置。

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

最后一次出现的位置。

在串里的出现次数。

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

应用

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

相关数据结构

Factor automaton

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

求出的suffix automaton后,把所有状态标记为accept state后就得到了识别所有子串的DAWG,但可能不是最简的,做minimize即可得到factor automaton,而acyclic DFA可以用Revuz's algorithm在时间内求最简表示。

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

Suffix oracle和factor oracle

Suffix oracle是一种简化的suffix automaton。

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

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

Suffox oracle的优点是节点数为,比最坏情况下的suffix automaton大致少一半。边数为

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

其他类似数据结构

Position heap

比suffix tree简单,存在一个离线构造算法,但实现复杂度不比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}, }