压缩后缀数组

从显式 SA 到导航排列 ​

显式后缀数组公理库后缀数组Suffix array按字典序排列字符串全部后缀起始位置的数组索引。的每个条目需要 $\lceil \log n\rceil$ bits，总计 $\mathrm{\Theta }(n\log n)$ bits。压缩后缀数组不逐项保存 $SA$，而编码相邻文本位置在后缀序中的关系，并稀疏采样绝对位置。

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

$$\mathrm{\Psi }(i)=ISA[(SA[i]+1)modn],$$

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

$$LF(i)=ISA[(SA[i]-1)modn]$$

令起点后退一字符，因此 $LF={\mathrm{\Psi }}^{-1}$。在 BWT公理库Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。 上，$LF$ 可由 $C[c]+ran{k}_c(L,i)$ 计算。

SA 值采样与恢复 ​

固定采样步长 $s\ge 1$，保存所有满足

$$SA[i]\equiv 0(\mathrm{mod}s)$$

的行及其 SA 值，并用采样 bit-vector 的 rank公理库Rank 与 Select 查询Rank and select在位串上计算前缀频数或定位第 j 次出现，并固定端点和索引约定。把行映射到紧凑样本数组。样本约有 $n/s$ 个，占

$$O((n/s)\log n)\text{bits}$$

外加 bit-vector 索引。

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

$$SA[i]=(SA[j]+t)modn.$$

若一次 LF/rank 为 $t_{LF}$，一次 SA access 最坏 $O(s{t}_{LF})$。减小 $s$ 提速但增加 samples，必须连同时间和 bit 空间一起报告。

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$。若把“每第 $s$ 行采样”误写成“SA 值模 $s$ 采样”，这个至多 $s-1$ 步的不变量就不再成立。

ISA 采样与文本位置访问 ​

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

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

与 FM-index 组合后的 Locate ​

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

$$O(|P|t_{rank}+occ\cdot s{t}_{LF}).$$

这个 locate 界包含搜索、逐输出恢复和实际输出数。CSA 本身的核心接口是压缩 SA/ISA access；没有 BWT rank 结构时，它不会凭空获得 backward search。

FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。把 BWT、rank、$C$ 表和 SA/ISA 采样组织成完整自索引，另外定义 count、locate 与 extract。CSA 强调压缩后缀排列访问；二者可共享 LF/采样组件，却不能把 FM-index 的所有操作都归给 CSA。

空间界的组成 ​

一个完整空间式至少分为：BWT 或 $\mathrm{\Psi }$ 的压缩表示、rank/select 辅助索引、SA/ISA samples、字母表和终止符元数据。主体可达到 $O(n\log \sigma )$ bits，进一步版本按 $n{H}_k(T)+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.