压缩后缀数组 | Codeboy's Blog

形式陈述

从显式 SA 到导航排列

压缩后缀数组以后缀数组的置换访问为接口，压缩保存其导航信息。对 $n\ge2$ ，显式 $SA$ 的每个条目用 $\lceil\log_2 n\rceil$ 位，总计 $\Theta(n\log n)$ 位；单元素情形单独直接表示。压缩表示通常编码相邻文本位置在后缀序中的关系，并稀疏采样绝对位置。下文选取 BWT 上的 LF 导航方案，也说明与 $\Psi$ 方案的对应。

对父接口给定的任意文本 $T$ ，记其长度为 $N\ge0$ 。选择一个未出现在 $T$ 中且小于原字母表全部字符的终止符 $\$$ ，建立 $S=T\$$ ，本页导航长度为 $n=N+1$ 。终止符单独组成最小后缀，其余后缀的相对字典序保持不变，因此原文本的排列访问由 $SA_T[i]=SA_S[i+1]$ （ $0\le i<N$ ）恢复，即去掉终止符行； $N=0$ 时返回空后缀数组。若还配备下文独立的 ISA 访问结构，则对 $p<N$ 有 $ISA_T[p]=ISA_S[p]-1$ 。原任务的空模式仍按全部 $N+1$ 个边界另行报告。

令 $ISA$ 为 $SA$ 的逆排列。对带唯一终止符的长度 $n\ge1$ 文本，定义

\Psi(i)=ISA[(SA[i]+1)\bmod n],

它从某个后缀行跳到文本起点前进一字符的行。反向排列

LF(i)=ISA[(SA[i]-1)\bmod n]

令起点后退一字符，因此 $LF=\Psi^{-1}$ 。在 BWT 上， $LF$ 可由 $C[c]+rank_c(L,i)$ 计算。

SA 值采样与恢复

固定整数采样步长 $1\le s\le n$ ，保存所有满足

SA[i]\equiv0\pmod s

的行及其 SA 值，并用采样 bit-vector 的 rank把行映射到紧凑样本数组。样本恰有 $\lceil n/s\rceil$ 个，占

O(\lceil n/s\rceil\log(n+1))\ \text{bits}

外加采样标记 bit-vector 的存储与索引。用普通稠密标记要 $n+o(n)$ 位；若希望稀疏样本连同标记都更小，还需相应的压缩位向量。

恢复 $SA[i]$ 时反复做 $j\leftarrow LF(j)$ ，直到命中样本行。每步令 SA 值减一模 $n$ ，至多 $s-1$ 步后到达同余为零的位置；若共走 $t$ 步，则

SA[i]=(SA[j]+t)\bmod n.

令 $t_{LF}\ge1$ 包括读取 BWT 字符、字符 rank、 $C$ 访问，以及采样标记的 access/rank；一次 SA access 最坏为 $O(s\,t_{LF})$ 。减小 $s$ 提速但增加 samples，必须连同时间和 bit 空间一起报告。

直觉

显式后缀数组为每一行保存绝对文本位置，CSA 则只稀疏保留锚点，并用 LF 或 $\Psi$ 表示相邻文本位置在后缀序中的移动。采样步长决定离锚点最远要走多少步，因此空间与访问时间的交换直接对应“保存多少绝对坐标、其余坐标走多远恢复”。

未采样后缀行沿 LF 走到 SA 样本并恢复绝对位置 — 压缩后缀数组的采样恢复

例子与边界

`banana$` 的恢复轨迹

banana$ 的

SA=(6,5,3,1,0,4,2).

取 $s=3$ ，采样 SA 值为 $6,3,0$ 的行，即行 $0,2,4$ 。行 $3$ 的 SA 值实际为 $1$ ；执行一次 $LF(3)=4$ 到达样本 $SA[4]=0$ ，所以恢复为 $0+1=1$ 。

行 $6$ 的值为 $2$ 。沿 LF 依次到 SA 值 $1$ 的行、再到行 $4$ 的样本值 $0$ ，共两步，恢复 $SA[6]=2$ 。若把“SA 值模 $s$ 采样”改成“每第 $s$ 行采样”，这个至多 $s-1$ 步的不变量就不再成立：LF 改变的是文本位置，不会按排序后的行号减一。

ISA 采样与文本位置访问

要恢复 $ISA[p]$ ，可在文本位置 $q=s\lfloor p/s\rfloor$ 保存 $ISA[q]$ ，再从该样本行应用 $\Psi$ 共 $p-q<s$ 次。于是 ISA access 同样有 $O(s\,t_\Psi)$ 时间和 $O(\lceil n/s\rceil\log(n+1))$ bit 样本成本。

SA sampling 按“后缀行查文本位置”，ISA sampling 按“文本位置查后缀行”；两张样本表服务不同方向。只保存一张却声称两种 access 都有同一界，通常漏掉了逆向导航代价。

推论与应用

与 FM-index 组合后的 Locate

若另有 BWT backward search，不含终止符的模式 $P$ 得到后缀区间 $[l,r)$ 。对其中每一行恢复 SA 值即可定位 occurrence，时间形如

O(1+|P|\,t_{rank}+occ\cdot s\,t_{LF}).

这个 locate 界包含搜索、逐输出恢复和实际输出数。CSA 的核心是压缩后缀排列访问；若要再支持模式计数，还需给出搜索算法。例如， $\Psi$ 在首字符相同的后缀区间内单调，也能通过二分完成反向区间搜索，时间取决于 $\Psi$ 的访问成本。BWT rank 是这里采用的另一条直接实现路线。

FM-index把 BWT、rank、 $C$ 表和 SA/ISA 采样组织成完整自索引，另外定义 count、locate 与 extract。CSA 强调压缩后缀排列访问；二者可共享 LF/采样组件，却不能把 FM-index 的所有操作都归给 CSA。

空间界的组成

一个完整空间式至少分为：BWT 或 $\Psi$ 的压缩表示、rank/select 辅助索引、SA/ISA samples、字母表和终止符元数据。导航主体可达到 $O(n\log\sigma)$ 位；采用合适的压缩序列或上下文分块构造，还可得到经验熵相关的界。阶数、字母表范围和访问成本须与选定构造配套，样本项仍要显式相加。

“压缩”应与显式 SA 的 $n\log n$ bits 比较，而不是只说 $O(n)$ 个 machine words。构建算法的峰值工作空间也可能远高于最终 CSA，不能从最终 bit 界反推构建内存。

失败边界

唯一终止符固定模 $n$ 导航的锚点；多终止符或字符序不一致会改变 BWT 行和 LF。Rank 半开/闭区间约定若与 $C$ 表不配套，会让每步导航错一行。

采样只改变访问速度，不修复近似匹配、动态文本更新或正则搜索。向文本中插一字符会全局改变后缀序与 BWT，静态 CSA 不能靠局部数组插入维护。

参考资料

Roberto Grossi and Jeffrey Scott Vitter, “Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching,” SIAM Journal on Computing 35(2), 2005.
Paolo Ferragina and Giovanni Manzini, “Indexing Compressed Text,” Journal of the ACM 52(4), 2005.
Gonzalo Navarro and Veli Mäkinen, “Compressed Full-Text Indexes”, ACM Computing Surveys 39(1), 2007，作者技术报告的 §§4.3–4.4、8、9.2：采样、 $\Psi$ 与反向搜索的不同实现。

形式陈述 ​

从显式 SA 到导航排列 ​

SA 值采样与恢复 ​

banana$ 的恢复轨迹 ​

ISA 采样与文本位置访问 ​

与 FM-index 组合后的 Locate ​

空间界的组成 ​

失败边界 ​

反向链接