Burrows-Wheeler变换详解（C++实现与数据压缩原理）

BWT的基本步骤

1. 在原始字符串末尾添加一个特殊结束符（通常是 '$'），确保字符串唯一可逆。
2. 生成该字符串的所有循环移位（即旋转）。
3. 将这些移位后的字符串按字典序排序。
4. 取排序后每一行的最后一个字符，拼接成BWT结果。

C++实现Burrows-Wheeler变换

下面是一个完整的C++代码示例，展示了如何实现BWT正向变换：

#include <iostream>#include <vector>#include <algorithm>#include <string>std::string bwt_encode(const std::string& input) {    // 步骤1：添加结束符    std::string s = input + "$";    int n = s.length();    // 步骤2：生成所有循环移位    std::vector<std::string> rotations;    for (int i = 0; i < n; ++i) {        rotations.push_back(s.substr(i) + s.substr(0, i));    }    // 步骤3：字典序排序    std::sort(rotations.begin(), rotations.end());    // 步骤4：提取每行最后一个字符    std::string bwt_result = "";    for (const auto& rotation : rotations) {        bwt_result += rotation.back();    }    return bwt_result;}int main() {    std::string original = "banana";    std::string encoded = bwt_encode(original);        std::cout << "原始字符串: " << original << std::endl;    std::cout << "BWT结果: " << encoded << std::endl;        return 0;}

运行上述代码，输入 banana，输出将是：

原始字符串: bananaBWT结果: annb$aa

可以看到，BWT结果中出现了连续的 aa，这比原始字符串更有利于压缩。这就是Burrows-Wheeler变换提升压缩效率的关键所在。

为什么BWT对数据压缩有用？

BWT本身并不压缩数据，但它通过重排字符，使得相同字符聚集在一起。这种“局部有序性”极大提升了后续压缩阶段（如游程编码或Move-to-Front变换）的效率。这也是为什么数据压缩技术中常常将BWT作为预处理步骤。

注意事项与优化

上面的实现使用了显式构造所有旋转字符串的方法，时间复杂度为 O(n² log n)，空间复杂度为 O(n²)，适用于教学和小规模数据。在实际应用中（如bzip2），会使用后缀数组等高级数据结构将复杂度优化到 O(n log n) 或更低。

此外，BWT是可逆的！虽然本教程聚焦于编码，但你也可以通过BWT结果和原始字符串长度，配合LF映射等技术还原原始数据。这是BWT算法实现完整性的体现。

总结

通过本教程，你已经掌握了Burrows-Wheeler变换的基本原理和C++实现方法。无论你是学习C++字符串压缩的新手，还是想深入了解数据压缩技术的开发者，BWT都是一个值得深入研究的经典算法。动手试试修改代码，用不同字符串测试效果吧！