排序算法之：Burrows-Wheeler 变换（BWT）与数据压缩中的排序应用

题目描述
假设你有一个字符串 S，例如 "banana\("，其中 '\)' 是一个特殊的结束符，且字典序小于任何其他字符。Burrows-Wheeler 变换（BWT）通过以下步骤生成一个新的字符串：

1. 生成字符串 S 的所有循环后缀（或循环移位），并将每个循环后缀视为一个字符串。
2. 将这些循环后缀按字典序排序。
3. 取排序后每个字符串的最后一个字符，按顺序组成一个新字符串 L。

例如，对于 S = "banana\("，其 BWT 结果为 "annb\)aa"。请你设计一个算法，给定一个字符串 S（包含结束符 '$'），计算其 BWT 结果 L。要求算法时间复杂度尽量低，并解释 BWT 在数据压缩（如 bzip2）中的作用。

解题过程循序渐进讲解

第一步：理解循环后缀的生成
对于长度为 n 的字符串 S（包含 '\('），其循环后缀是通过将 S 不断循环左移生成的 n 个字符串。更准确地说，第 i 个循环后缀是 S[i:] + S[:i]（0 ≤ i < n）。但通常我们考虑的是 S 的所有后缀（suffixes），然后对它们进行排序。在 BWT 的标准定义中，我们实际处理的是 S 的所有循环移位（cyclic rotations），但由于 '\)' 是唯一的结束符且最小，循环移位的排序等价于对 S 的所有后缀（加上 $ 的前缀）进行排序。

以 S = "banana\(" 为例（n=7）： 生成所有循环移位（在末尾隐式添加 '\)' 的影响，实际上我们直接处理字符串的所有后缀）：
0: "banana\(" 1: "anana\)b" (但注意：更准确的做法是，我们考虑所有以 S 的每个位置开始到末尾，再从头到该位置之前的字符串，但 '$' 保证了唯一性)
实际上，标准 BWT 构造是：

1. 在 S 末尾添加 '$'（如果还没有）。
2. 生成 S 的所有循环移位（即 n 个长度为 n 的字符串）。
3. 按字典序排序这些循环移位。
4. 取每个循环移位的最后一个字符，形成 L。

但更高效的实现不需要显式生成所有循环移位，而是利用后缀数组。

第二步：通过后缀数组高效计算 BWT
给定 S = "banana\("，我们先构建 S 的所有后缀的列表： 后缀（从位置 i 开始到末尾）： i=0: "banana\)"
i=1: "anana\(" i=2: "nana\)"
i=3: "ana\(" i=4: "na\)"
i=5: "a\(" i=6: "\)"

然后对这些后缀按字典序排序：
6: "\(" 5: "a\)"
3: "ana\(" 1: "anana\)"
0: "banana\(" 4: "na\)"
2: "nana$"

现在，BWT 的结果 L 是：对于排序后的每个后缀，取它原始字符串中的前一个字符（循环意义上）。
定义：对于排序后第 k 个后缀，它的起始位置是 SA[k]（后缀数组中的值）。那么该循环移位的最后一个字符是 S[(SA[k] - 1 + n) % n]。

对于上例：
SA = [6, 5, 3, 1, 0, 4, 2]
S = "banana\(" 计算 L： k=0: SA[0]=6, 前一个字符位置 (6-1+7)%7=5, S[5]='a' → L[0]='a' k=1: SA[1]=5, 前一个位置 4, S[4]='n' → 'n' k=2: SA[2]=3, 前一个位置 2, S[2]='n' → 'n' k=3: SA[3]=1, 前一个位置 0, S[0]='b' → 'b' k=4: SA[4]=0, 前一个位置 6, S[6]='\)' → '\(' k=5: SA[5]=4, 前一个位置 3, S[3]='a' → 'a' k=6: SA[6]=2, 前一个位置 1, S[1]='a' → 'a' 所以 L = "annb\)aa"，与例子一致。

第三步：算法步骤总结

1. 输入字符串 S，保证末尾有特殊字符 '$'（且唯一，字典序最小）。
2. 构建 S 的后缀数组 SA。构建后缀数组有 O(n log n) 或 O(n) 的算法（如 SA-IS 算法）。
3. 对于每个 i 从 0 到 n-1，计算 L[i] = S[(SA[i] - 1 + n) % n]。
4. 输出字符串 L。

时间复杂度：取决于后缀数组的构建。简单方法用排序所有后缀 O(n² log n)（因为比较后缀要 O(n)），但用倍增法或 SA-IS 可做到 O(n log n) 或 O(n)。空间复杂度 O(n)。

第四步：BWT 在数据压缩中的作用
BWT 本身并不压缩数据，而是一种重排，使相同字符聚集在一起，从而提高后续压缩步骤（如 Move-To-Front + 哈夫曼编码）的效率。
BWT 的可逆性：给定 L 和原始字符串中 '\(' 的位置（通常记录为 primary index，即 SA 中对应后缀 '\)' 的索引），可以通过以下步骤恢复原字符串 S：

1. 计算 F = 排序后的 L（即所有循环移位的第一列字符）。
2. 构建 T 数组，记录 L 中每个字符在 F 中的对应关系（通过 LF mapping）。
3. 从 primary index 开始，反复应用 LF mapping 重构原串。

由于 BWT 使字符局部相似，后续的 MTF 编码会产生大量小整数，再用熵编码（如哈夫曼或算术编码）压缩率很高。bzip2 压缩工具就采用了 BWT + MTF + 哈夫曼编码的流程。

第五步：示例验证可逆性（简要）
已知 L="annb\(aa"，primary index=4（因为 L[4]='\)'）。

1. F = 排序 L = "$aaabnn"。
2. 对每个字符 c，记录在 F 和 L 中的出现次数，构建 Next 数组，使得可以从 F 中字符找到在 L 中对应的位置。
3. 从 index=4 开始，T[4]='\('，在 F 中 '\)' 是第 0 个，对应 L 中... 逐步回溯可得 "banana$"。

这个恢复过程证明了 BWT 是唯一可逆的变换（给定 primary index）。

总结
BWT 的计算核心是后缀数组的构建，之后按规则取字符即可。它在数据压缩中作为预处理步骤，使字符串局部有序，便于后续编码获得高压缩比。本题的算法实现重点在于高效构建后缀数组，并理解 BWT 的原理与应用。