String index structure: suffix automaton

10th May 2013
18 min read
Tags:
data structure,
stringology,
suffix automaton

Suffix automaton
定义
一些引理
- 引理1
- 引理2
- 引理3
性质
构建
性质
辅助数据结构
应用
相关数据结构
- Factor automaton
- Suffix oracle和factor oracle
其他类似数据结构
- Position heap
参考文献

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)\)，把\(R_w(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 \equiv_w 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}\)与\(R_w\)的关系知\(R_{wa}(u)=R_{wa}(v)\)。

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

引理3

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

下面的引理则说明，\(w\)中与\(z\)等价的集合，在\(w\)末尾添加新字符\(a\)后是怎样变化的：

\(u \equiv_w 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 \equiv_w z, |u| > |z| \implies u \equiv_{wa} z'\)，其中\(z'\)为满足\(z' \equiv_w z\)的\(w\)中最长子串，且不是\(wa\)的后缀。
- \(u\)和\(z'\)都不是\(wa\)的后缀
- \(R_{wa}(u) = R_{w}(u) = R_w(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(q)\)，则存在\(u \equiv_w z, |u|=l(q)+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}\)可能有两种取值，需要注意。

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。

其他类似数据结构

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

String index structure: suffix automaton

Table of Contents

Suffix automaton

定义

一些引理

引理1

引理2

引理3

性质

构建

性质

辅助数据结构

应用

相关数据结构

Factor automaton

Suffix oracle和factor oracle

其他类似数据结构

Position heap

参考文献