Burrows-Wheeler Transform (BWT) 是一种数据转换算法, 主要用于数据压缩领域. 它由 Michael Burrows 和 David Wheeler 在 1994 年提出, 广泛应用于无损数据压缩算法(如 bzip2)中. BWT 的核心思想是通过重新排列输入数据, 使得相同的字符更容易聚集在一起, 从而提高后续压缩算法的效率.
1. BWT 的基本概念
BWT 是一种可逆的变换, 它不会改变数据的内容, 而是通过重新排列数据的顺序, 使得数据更容易被压缩. BWT 的主要特点是:
- 局部相似性增强: 将输入字符串中的相似字符聚集在一起.
- 可逆性: 变换后的数据可以通过逆变换恢复为原始数据.
2. BWT 的算法步骤
2.1 Naive 方法
BWT 的算法步骤如下:
步骤 1: 生成所有循环移位
假设输入字符串为 S, 长度为 n. 首先, 生成 S 的所有循环移位(cyclic rotations).
例如, 对于字符串 "banana$"($符号是结束符, 不存在于输入串中), 其循环移位包括:
banana$
anana$b
nana$ba
ana$ban
na$bana
a$banan
$banana
这里请读者思考一个问题: 如果没有结束符$, 那么是否能够恢复原始字符串?
步骤 2: 按字典序排序
将所有循环移位按字典序排序. 排序后得到的结果被称为BW矩阵. 对于 "banana$", 排序后的结果为:
$banana
a$banan
ana$ban
anana$b
banana$
na$bana
nana$ba
步骤 3: 提取最后一列
从排序后的循环移位中提取最后一列字符, 形成 BWT 变换后的字符串. 对于 "banana$", 最后一列是:
$banan[a]
a$bana[n]
ana$ba[n]
anana$[b]
banana[$]
na$ban[a]
nana$b[a]
因此, BWT 变换后的结果为 "annb$aa".
再举一些例子:
| 字符串 | BWT |
|---|---|
"mississippi$" |
"ipssm$pissii" |
a_friend_in_need_is_a_friend_indeed$" |
"dsaadddn$_enneneednii__rr___ieei_ffi" |
"It_was_the_best_of_times,_it_was_the_worst_of_times$" |
"ss$e,ttssfftteww_hhmmbootttt_ii__woeeaaressIi_______" |
从这些例子可以看出, 相同的字母容易成块出现.
代码实现
def bwt_transform(s):
"""对字符串 s 进行 BWT 变换"""
s = s + '$'
n = len(s)
# 生成所有循环移位
rotations = [s[i:] + s[:i] for i in range(n)]
# 按字典序排序
rotations_sorted = sorted(rotations)
# 提取最后一列
last_column = ''.join([row[-1] for row in rotations_sorted])
return last_column
2.2 使用 SA 数组高效计算 BWT
观察上面的例子, 可以发现: 由于'$'符号的 ASCII 小于任何一个字母(a-z,包含大小写), 这意味着比较时不会用到$符号之后的字符串, 可以删去他们. 排序结果等价于后缀数组.
解决了排序问题之后接着需要关注第二个问题, 即最后的字母的确定. 这个问题比较简单, 因为所有的序列都是循环产生的, 所以序列的最后一位字母其实就是首字母的左侧字母. 用公式表示就是:
B W T [ i ] = { S [ S A [ i ] − 1 ] if S A [ i ] > 0 $ if S A [ i ] = 0 BWT[i] = \begin{cases} S[SA[i] - 1] & \text{if } SA[i] > 0 \\ \$ & \text{if } SA[i] = 0 \end{cases}
