The Burrows-Wheeler Transform 块排序压缩算法

前言

最近发现了一个非常有意思的算法：The Burrows-Wheeler Transform（块排序压缩算法），所以稍微花点时间简单记录一下

说是一个压缩算法，实际上这个算法主要做的事情是把数据重排序，实际上并没有减少数据的长度（通常反而因为增加了行尾标识而增长了）

但是它完成了一个非常有意思的效果：在几乎不增加字符串长度的情况下，把一个字符串的重复的部分尽可能聚合到一块了

而 Gzip 压缩算法基于Deflate算法，通过结合LZ77算法（查找并替换重复字符串）和霍夫曼编码，通过将接近的字符串聚合到一块，能够有效增加压缩率

算法操作方式

我做了一个简单的演示工具，我们就用经典的 banana 作为示例

在原串后添加结束结束符号$，且此符号认为是最小的字符

banana\$

生成字符串的全部循环序列

banana\$
anana\$b
nana\$ba
ana\$ban
na\$bana
a\$banan
\$banana

将这几个字符串排序

\$banana
a\$banan
ana\$ban
anana\$b
banana\$
na\$bana
nana\$ba

取出最后一列字符串

\$banana
a\$banan
ana\$ban
anana\$b
banana\$
na\$bana
nana\$ba

得到结果

annb\$aa

下面将进行还原操作

annb\$aa

将结果排成一列

a
n
n
b
\$
a
a

排序

\$
a
a
a
b
n
n

在当前的列之前添加 BWT 结果

a\$
na
na
ba
\$b
an
an

再次排序

\$b
a\$
an
an
ba
na
na

重复上述步骤

a\$b
na\$
nan
ban
\$ba
ana
ana

再次排序

\$ba
a\$b
ana
ana
ban
na\$
nan

重复上述步骤

a\$ba
na\$b
nana
bana
\$ban
ana\$
anan

再次排序

\$ban
a\$ba
ana\$
anan
bana
na\$b
nana

重复上述步骤

a\$ban
na\$ba
nana\$
banan
\$bana
ana\$b
anana

再次排序

\$bana
a\$ban
ana\$b
anana
banan
na\$ba
nana\$

重复上述步骤

a\$bana
na\$ban
nana\$b
banana
\$banan
ana\$ba
anana\$

再次排序

\$banan
a\$bana
ana\$ba
anana\$
banana
na\$ban
nana\$b

重复上述步骤

a\$banan
na\$bana
nana\$ba
banana\$
\$banana
ana\$ban
anana\$b

再次排序

\$banana
a\$banan
ana\$ban
anana\$b
banana\$
na\$bana
nana\$ba

回到最初的矩阵

\$banana
a\$banan
ana\$ban
anana\$b
banana\$
na\$bana
nana\$ba

上一步

下一步

算法原理

觉得这个算法有意思的地方，可能并不是它的实用价值。这里有一个非常有意思：为什么这样排序了几次之后，就会回到最初的矩阵

这里蕴藏了一个非常有意思的字符串排序逻辑。

通常情况下，我们会使用字符串从第一个字符开始比较，如果相同则比下一个字符

而在这个问题下，假定所有字符串长度相同，那其实完全可以从最后一位比起，然后逐次比较新增加的字符，可以实现类似桶排序的方式，达成最终排序结果

由于后排序的结果会覆盖先排序的结果，使得实际上达成了“从第一个字符开始比较，如果相同则比下一个字符”的效果