压缩后缀数组

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

banana$ 的恢复轨迹 ​

banana$ 的

取 $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，时间形如

这个 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 不能靠局部数组插入维护。