Shiroha白羽的博客
·
The Burrows-Wheeler Transform 块排序压缩算法
💡
原文中文，约1900字，阅读约需5分钟。
📝
内容提要
Burrows-Wheeler变换是一种重排序算法，通过聚合重复字符串来提高压缩效率。虽然不减少数据长度，但能显著提升后续压缩算法（如Gzip）的效果。该算法的排序逻辑独特，从字符串末尾开始比较，最终实现有效排序。
🎯
关键要点
- Burrows-Wheeler变换是一种重排序算法，主要通过聚合重复字符串来提高压缩效率。
- 该算法并不减少数据长度，通常会因为增加行尾标识而增长。
- Burrows-Wheeler变换能够在几乎不增加字符串长度的情况下，将重复部分聚合。
- Gzip压缩算法基于Deflate算法，通过结合LZ77算法和霍夫曼编码来提高压缩率。
- 算法通过对字符串进行循环序列生成和排序，最终提取出最后一列字符串。
- 该算法的排序逻辑独特，从字符串末尾开始比较，逐步实现有效排序。
- 经过多次排序后，字符串能够回到最初的矩阵，体现了有趣的排序逻辑。
➡️
