> bwt | transform | compress <
// Burrows-Wheeler 变换 —— 通过可逆重排优化文本压缩效果
0 字符
0 字符
>> 功能亮点
[REVERSIBLE]
完全可逆
无损变换，支持从结果精确恢复原始文本。
[CLUSTERING]
字符聚类
将相似字符聚集在一起，为后续编码器创造更好的压缩条件。
[BZIP2]
bzip2 的核心步骤
广泛应用于 bzip2 等基于 BWT 的压缩算法。
>> 技术说明
BWT 的工作原理
Burrows-Wheeler 变换会构造输入字符串的所有循环位移，将这些字符串按字典序排序，并返回排序矩阵的最后一列以及原始字符串所在行的索引。这样的重排会把相似字符聚在一起，使输出非常适合结合 RLE、Move-to-Front 和熵编码进行压缩。
BWT 示例
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
为什么使用 BWT
- 显著提升文本数据的可压缩性
- 算法本身完全可逆且无损
- 将相似上下文重排为连续区间
- 是 bzip2 压缩算法的基础组件
- 可作为其他编码步骤之前的高效预处理
>> 常见问题
什么是 Burrows-Wheeler 变换？
Burrows-Wheeler 变换（BWT）是一种可逆算法，它通过重新排列字符串，使同一字符在结果中形成更长的连续区间。该算法由 Michael Burrows 和 David Wheeler 于 1994 年提出，常作为 bzip2 等压缩器的预处理步骤，以提升压缩率。
BWT 为什么有利于压缩？
BWT 会把在相似上下文中出现的字符聚集在一起，使输出中同一符号往往连续出现。这类“长跑长度”非常适合结合游程编码、Move-to-Front 和 Huffman 等熵编码进行高效压缩。
EOF 标记有什么作用？
EOF（End Of File）标记通常使用 '$' 或其他唯一字符，用来保证所有循环位移互不相同，并帮助定位原始字符串所在行。如果没有 EOF，有些输入串可能没有唯一的表示。在逆变换时，该标记会被移除。
BWT 本身是一个完整的压缩算法吗？
不是。BWT 本身并不直接压缩数据，而是将数据变换成更适合压缩的形式。实际应用中，它通常与 Move-to-Front、RLE 和 Huffman 编码一起构成类似 bzip2 的压缩方案。