跳到主要内容
uencoder

BWT

BWT 是 Burrows-Wheeler 变换的缩写,将文本变换为相似字符聚集的形式,是 bzip2 的第一阶段。

用途

作为可逆预处理提升后续压缩率,使相同字符聚集便于 RLE 与熵编码。

机制

构造所有循环移位排序矩阵取末列,记录原始行号。逆变换通过 LF 映射从末列与行号恢复原文本。

用例

  • bzip2 压缩
  • 基因组比对
  • 全文索引

相关工具

参考链接