2013-05-10

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中，无需创建。添加完字符后，可能有两种取值，需要注意。

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。

其他类似数据结构

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}, }

MaskRay