Burrows-Wheeler 变换详解（小白也能看懂的 C 语言实现指南）

BWT 为什么有用？

虽然 BWT 本身不压缩数据，但它能将相似字符聚集在一起，极大提升后续压缩算法（如 MTF + RLE + Huffman）的效率。这也是为什么 数据压缩领域广泛采用 BWT 作为预处理步骤。

C 语言实现 BWT

下面我们一步步用 C 语言实现 BWT。我们将假设输入字符串以 '\0' 结尾，并手动在末尾添加 '$' 作为结束符（确保它是字典序最小的字符）。

步骤 1：生成所有循环移位

对于长度为 n 的字符串（含 $），共有 n 个不同的循环移位。

步骤 2：对这些移位进行字典序排序

步骤 3：提取每行最后一个字符组成 BWT 结果

下面是完整的 C 代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>// 比较函数，用于 qsortint compare(const void *a, const void *b) {    return strcmp(*(const char **)a, *(const char **)b);}char* bwt_transform(const char* input) {    int len = strlen(input);    // 添加结束符 $    char* str_with_dollar = malloc(len + 2);    strcpy(str_with_dollar, input);    strcat(str_with_dollar, "$");    len++;    // 生成所有循环移位    char** rotations = (char**)malloc(len * sizeof(char*));    for (int i = 0; i < len; i++) {        rotations[i] = (char*)malloc((len + 1) * sizeof(char));        for (int j = 0; j < len; j++) {            rotations[i][j] = str_with_dollar[(i + j) % len];        }        rotations[i][len] = '\0';    }    // 排序    qsort(rotations, len, sizeof(char*), compare);    // 构建 BWT 结果    char* bwt_result = (char*)malloc((len + 1) * sizeof(char));    for (int i = 0; i < len; i++) {        bwt_result[i] = rotations[i][len - 1];    }    bwt_result[len] = '\0';    // 释放内存    free(str_with_dollar);    for (int i = 0; i < len; i++) {        free(rotations[i]);    }    free(rotations);    return bwt_result;}int main() {    const char* input = "banana";    char* result = bwt_transform(input);    printf("原始字符串: %s\n", input);    printf("BWT 结果: %s\n", result);    free(result);    return 0;}

运行上述程序，输出可能如下（取决于排序稳定性）：

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

注意事项

• 为了保证 BWT 可逆，必须使用唯一的结束符（如 $），且其字典序应小于所有其他字符。
• 实际应用中，BWT 常与逆变换（IBWT）配合使用，才能完整还原原始数据。
• 本实现适用于教学目的；工业级实现会优化内存和速度（例如不显式存储所有旋转）。

总结

通过本教程，你已经掌握了 Burrows-Wheeler变换的基本原理，并用 C语言实现了一个简单版本。理解 BWT 是深入学习现代 数据压缩技术的重要一步。希望你能在此基础上继续探索 BWT 的逆变换以及它在 bzip2 中的实际应用！

记住，BWT 虽然看起来神奇，但本质只是巧妙地重排字符，让后续的 BWT算法更高效。多动手写代码，你会理解得更深刻！