图解BWT(Burrows-Wheeler Transform) 算法

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".

再举一些例子:

从这些例子可以看出, 相同的字母容易成块出现.

代码实现

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}