6.3 Suffix Arrays：后缀排序、LCP、LRS与KWIC

6.3 · Suffix Arrays覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“6.3 · Suffix Arrays”如何以排序后缀与 LCP 支持最长重复子串、上下文关键词和最长公共前缀查询
  • 能逐项核对 后缀数组、后缀排序、最长重复子串、上下文关键词查找、最长公共前缀，并区分作者站内容与本页独立补充
  • 能按“二分后缀数组定位长度 M 模式需 O(M log N) 字符比较，匹配输出另计”手算一个最小输入，逐步检查“suffix array 是 0..N-1 的全排列且对应后缀字典序递增；LCP 与相邻后缀一致”
  • 能注入“后缀比较器把 substring 分配成本藏在常数里，或 LCP 索引偏移一位越过文本末端”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“6·3 · Suffix Arrays”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“6·3 · Suffix Arrays”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“6·3 · Suffix Arrays”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：6.3 · Suffix Arrays

  • 1. 后缀数组：在本页通过“生成后缀索引”连接解释、交互状态和练习验收。
  • 2. 后缀排序：在本页通过“按字符比较后缀”连接解释、交互状态和练习验收。
  • 3. 最长重复子串：在本页通过“形成有序 SA”连接解释、交互状态和练习验收。
  • 4. 上下文关键词查找：在本页通过“计算相邻 LCP”连接解释、交互状态和练习验收。
  • 5. 最长公共前缀：在本页通过“执行 LRS/KWIC 查询”连接解释、交互状态和练习验收。

从“所有substring问题，都能转成suffix之间的邻近关系吗”开始

长度N的text有N个nonempty suffixes：

Si=text[i..N),0≤i<NS_i=text[i..N),\qquad 0\le i\lt N

后缀数组（suffix arrays）把重叠的strings变成一个ordered index。

先预测：BANANA 的最长重复substring ANA 出现在offsets 1与3。为何不必比较all (O(N^2)) suffix pairs？因为共享long prefix的suffixes在lexicographic order中聚在一起；最优重复prefix一定能在某对adjacent sorted suffixes之间看到。

6.3.1 Offset view：不要复制N个suffix strings

Naively materialize：

∑i=0N−1(N−i)=N(N+1)2\sum_{i=0}^{N-1}(N-i)=\frac{N(N+1)}2

characters，space quadratic。Modern Java的substring()也不保证constant-time shared backing storage，所以不能依赖old Java 6 behavior。

Official SuffixArray用small Suffix object保存same text reference和offset；SuffixArrayX更进一步只保存int[] index。Character access为 text.charAt(offset + d)。

private static class Suffix implements Comparable<Suffix> {
    private final String text;
    private final int index;
 
    char charAt(int d) { return text.charAt(index + d); }
    int length() { return text.length() - index; }
}

Index itself是O(N) offsets；原文另占O(N)。select(i)若materialize string仍花suffix length time/space，所以官方建议主要用于debug。Production APIs优先返回offset+length view。

6.3.2 Suffix sorting：lexicographic order与sentinel

后缀排序（suffix sorting）比较两个offset i、j：

  1. 从d=0逐character比较 text[i+d] 与 text[j+d]。
  2. First mismatch决定order。
  3. 若一个suffix先结束，shorter suffix较小。
int compareSuffix(int i, int j) {
    int n = Math.min(text.length() - i, text.length() - j);
    for (int d = 0; d < n; d++) {
        if (text.charAt(i + d) < text.charAt(j + d)) return -1;
        if (text.charAt(i + d) > text.charAt(j + d)) return +1;
    }
    return (text.length() - i) - (text.length() - j);
}

SuffixArray API：

  • length()：N。
  • index(i)：rank i suffix的original offset，O(1)。
  • select(i)：rank i suffix string，cost proportional to suffix length。
  • lcp(i)：ranks i-1与i的longest common prefix length。
  • rank(query)：strictly less than query的suffix count，也就是insertion position。

Core identity：

rank⁡(select⁡(i))=i\operatorname{rank}(\operatorname{select}(i))=i

当all suffixes distinct时成立；suffixes因different end offsets天然distinct。Certificate可用它发现bad rank/search boundary。

Character comparison unit必须明确。Official Java使用UTF-16 code units，不是Unicode code points、grapheme clusters或locale collation。Index offsets和context slicing必须使用同一unit。

6.3.3 Construction choices与worst case

Basic SuffixArray创建N个offset views后调用Arrays.sort。Comparator一次可能扫描long common prefix，worst-case character work可很大；all-same-character text使suffix comparisons expensive。

SuffixArrayX在offset array上做3-way radix quicksort：

char pivot = text[index[lo] + d];
while (i <= gt) {
    char current = text[index[i] + d];
    if      (current < pivot) exch(lt++, i++);
    else if (current > pivot) exch(i, gt--);
    else                      i++;
}
sort(lo, lt - 1, d);
if (pivot > 0) sort(lt, gt, d + 1);
sort(gt + 1, hi, d);

它追加NUL sentinel并要求input不含NUL；equal partition才进入next character depth。

该实现practice中快、memory少，但对N copies of same character可表现很差。Manber-Myers repeated doubling维护length (2^k) prefixes的ranks，每轮按rank pairs排序；配合合适sort可达O(N log N)。Kasai algorithm在suffix array已知后可O(N)构建完整LCP array。

不能只标“suffix array O(N log N)”而不说明construction algorithm、alphabet、comparison cost与workspace。

6.3.4 Longest common prefix array

最长公共前缀（longest common prefix）：

lcp⁡(i)=max⁡{ℓ:SSA[i−1][0..ℓ)=SSA[i][0..ℓ)}\operatorname{lcp}(i) =\max\{\ell:S_{SA[i-1]}[0..\ell)=S_{SA[i]}[0..\ell)\}

Basic implementation逐character扫adjacent suffixes，time proportional toactual LCP：

int lcp(int leftOffset, int rightOffset) {
    int length = 0;
    while (leftOffset + length < N && rightOffset + length < N) {
        if (text.charAt(leftOffset + length)
            != text.charAt(rightOffset + length)) break;
        length++;
    }
    return length;
}

Exact LCP certificate需证明两面：

  1. 前length个characters确实equal。
  2. 下一characters different，或至少一个suffix结束。

只检查first condition会接受under-reported LCP，导致LRS过短；只检查next mismatch会接受prefix内部已不同的nonsense value。

6.3.5 Longest repeated substring：最大adjacent LCP

最长重复子串（longest repeated substring）等于maximum adjacent LCP。

String best = "";
for (int i = 1; i < N; i++) {
    int length = suffixArray.lcp(i);
    if (length > best.length())
        best = text.substring(suffixArray.index(i),
                              suffixArray.index(i) + length);
}

Why adjacent suffices：假设substring P是two suffixes A、B的common prefix。所有以P开头的suffixes在sorted order中形成contiguous interval；该interval中至少一对adjacent suffixes也共享P。因此global optimum出现在某个adjacent LCP。

Overlapping occurrences合法，例如nine A characters的LRS是eight A characters。若application要求non-overlap，maximum LCP还不够，需同时约束offset distance：

ℓ≤∣SA[i]−SA[j]∣\ell\le |SA[i]-SA[j]|

并可能考虑非adjacent witnesses。

6.3.6 Rank：query在suffix order中的lower bound

rank(query)返回strictly smaller suffix count。Basic binary search每次比较query与middle suffix：

int lo = 0, hi = N - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    int cmp = compare(query, suffix[mid]);
    if      (cmp < 0) hi = mid - 1;
    else if (cmp > 0) lo = mid + 1;
    else return mid;
}
return lo;

Query length K，每次comparison最多K characters，binary search O(log N) comparisons，所以basic cost O(K log N)。若缓存query与lo/hi suffix的LCP，可跳过已知equal prefixes；更完整LCP/RMQ machinery可实现O(K+log N) query。

Rank不是substring occurrence本身；它给first possible lexicographic location。必须再检查suffix是否starts with query。

6.3.7 Keyword in context：prefix matches形成连续区间

上下文关键词查找（keyword in context）也称KWIC/KWIK。

Algorithm：

  1. start = rank(query)。
  2. 从start向右scan suffix ranks。
  3. 当suffix不再以query开头时stop。
  4. 对每个match offset输出clamped context window。
for (int i = suffixArray.rank(query); i < N; i++) {
    int offset = suffixArray.index(i);
    int end = Math.min(N, offset + query.length());
    if (!query.equals(text.substring(offset, end))) break;
    print(text.substring(Math.max(0, offset - context),
                         Math.min(N, offset + query.length() + context)));
}

All query-prefix suffixes contiguous，因为lexicographic order把same prefix聚在一起。Output order是suffix lexicographic order，不是original offset order；若UI要求document order，应收集offsets后numeric sort。

Text normalization也是contract。Official KWIK把whitespace runs压成single spaces，因此reported offsets属于normalized text，不是original file bytes。若需source highlighting，必须维护normalization-to-source offset map。

6.3.8 Other adjacent-order applications

Suffix array还支持：

  • Longest common substring：合并两texts并标记source，观察相邻cross-source suffixes的LCP。
  • k-gram frequency：对query prefix求lower/upper suffix ranks，区间size即count。
  • Longest k-repeated substring：LCP windows of k suffixes的minimum。
  • Burrows-Wheeler transform与FM-index的构建基础。
  • Shortest unique substring：结合neighbor LCP求超过both neighbors的minimum prefix。

这些扩展共享同一证据链：offset permutation、suffix order与LCP must be correct；application只在该ordered substrate上聚合。

6.3.9 Independent certificate

Suffix-array candidate的independent validator：

  1. Permutation：array length N，每个offset 0至N-1 exactly once。
  2. Order：每对adjacent suffixes strictly increasing。
  3. LCP exactness：prefix equal + next mismatch/end。
  4. Inverse：rank(select(i)) == i。
  5. Query：rank是lower bound；all earlier suffixes less，all later suffixes not less。
  6. Applications：LRS substring有two witness offsets；KWIC每个context offset确实startsWith query。
assert(isPermutation(sa, 0, N));
for (let i = 1; i < N; i++) {
  assert(compareSuffix(sa[i - 1], sa[i]) < 0);
  assert(lcp[i] === referenceLcp(sa[i - 1], sa[i]));
}
for (let i = 0; i < N; i++) assert(rank(text.slice(sa[i])) === i);

Differential corpus应含empty、single character、all same, periodic, all distinct, NUL boundary、Unicode surrogate pairs与large repetitive text。Empty suffix是否included必须明确；official API只索引N个nonempty suffixes。

6.3.10 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“6.3 · Suffix Arrays”的两个最小情境间切换，再逐项选择正式概念。预测“二分后缀数组定位长度 M 模式需 O(M log N) 字符比较，匹配输出另计”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

6.3 · Suffix Arrays：对象、操作与不变量

以排序后缀与 LCP 支持最长重复子串、上下文关键词和最长公共前缀查询

选择最小情境

切换正式概念

输入合同操作证书algs4-6.3 · 先给前提，再执行，再验收当前概念：1/6
最长重复
文本 banana
当前观察
suffix arrays：相邻后缀的最大 LCP 为 ana，并能返回对应两个起点
二分后缀数组定位长度 M 模式需 O(M log N) 字符比较，匹配输出另计

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 后缀数组：在实验 1 中指出对应状态，并写出一个通过条件。
  • 后缀排序：在实验 2 中指出对应状态，并写出一个通过条件。
  • 最长重复子串：在实验 3 中指出对应状态，并写出一个通过条件。
  • 上下文关键词查找：在实验 1 中指出对应状态，并写出一个通过条件。
  • 最长公共前缀：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“二分后缀数组定位长度 M 模式需 O(M log N) 字符比较，匹配输出另计”不是孤立结论？

问题 3：故障恢复。 怎样证明“后缀比较器把 substring 分配成本藏在常数里，或 LCP 索引偏移一位越过文本末端”已经修复？

小结

  • Suffix arrays保存all nonempty suffixes的lexicographic rank-to-offset mapping。
  • Offset views使index space O(N)；复制all suffix strings会产生quadratic characters。
  • Suffix sorting必须按明确character unit比较，shorter exhausted suffix排在longer prefix suffix之前。
  • Longest common prefix array记录adjacent sorted suffixes的exact shared-prefix lengths。
  • Longest repeated substring就是maximum adjacent LCP，official problem允许overlap。
  • Rank以binary search求query insertion position，basic cost O(K log N)。
  • Keyword in context从rank(query)开始扫描one contiguous startsWith interval。
  • Basic comparison sort、3-way radix和doubling algorithms有不同worst cases与memory tradeoffs。
  • Independent certificate检查offset permutation、strict suffix order、exact LCP和rank/select inverse。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…