最近发现了一个非常有意思的算法：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
在当前的列之前添加 BWT 结果
a\$
na
na
ba
\$b
an
an
重复上述步骤
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
觉得这个算法有意思的地方，可能并不是它的实用价值。这里有一个非常有意思：为什么这样排序了几次之后，就会回到最初的矩阵
这里蕴藏了一个非常有意思的字符串排序逻辑。
通常情况下，我们会使用字符串从第一个字符开始比较，如果相同则比下一个字符
而在这个问题下，假定所有字符串长度相同，那其实完全可以从最后一位比起，然后逐次比较新增加的字符，可以实现类似桶排序的方式，达成最终排序结果
由于后排序的结果会覆盖先排序的结果，使得实际上达成了“从第一个字符开始比较，如果相同则比下一个字符”的效果
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。