每日算法 — 使用java实现Burrows-Wheeler变换：可逆字符串重排与Move-To-Front编码

Burrows-Wheeler变换（BWT）是1994年由Michael Burrows和David Wheeler提出的一种字符串变换算法。它本身并不压缩数据，但通过将输入字符串重排为具有更多重复字符的形式，使得后续的压缩算法（如游程编码）能够取得更好的效果。BWT是bzip2压缩工具的核心组件。

算法核心思想

BWT的核心洞察是：如果对一个字符串的所有循环移位按字典序排序，那么排序后最后一列（Last Column）会出现大量相同的连续字符。这种”聚类”效应使得后续压缩更加高效。

变换过程

1. 对待变换字符串添加一个唯一的结束标记（如'\0'），该标记字典序最小
2. 生成该字符串的所有循环移位（rotation）
3. 将所有循环移位按字典序排序
4. 取排序后矩阵的最后一列，即为BWT变换结果

逆变换原理

逆变换的关键性质：第一列（First Column）是最后一列的排序结果。利用这一性质，可以通过”最后一列到第一列”的映射（LF-mapping）逐步还原原始字符串。

具体步骤：
1. 对最后一列排序得到第一列
2. 结合两列构建映射关系：相同字符在第i次出现时，对应原字符串中的位置关系一致
3. 从结束标记所在行开始，沿着映射反复跳转，即可还原原字符串

Java完整实现

import java.util.*;

/**
 * Burrows-Wheeler变换实现
 * 可逆字符串重排变换，使相似字符聚集以提升压缩率
 */
public class BurrowsWheelerTransform {

    // 字符串结束标记，字典序最小且唯一
    private static final char EOF = '\0';

    /**
     * BWT正向变换
     * @param input 原始字符串
     * @return 变换结果，包含BWT字符串和主索引（原始字符串在排序矩阵中的行号）
     */
    public BWTResult transform(String input) {
        // 添加结束标记
        String text = input + EOF;
        int n = text.length();

        // 生成所有循环移位的起始索引
        Integer[] suffixes = new Integer[n];
        for (int i = 0; i < n; i++) {
            suffixes[i] = i;
        }

        // 按循环移位的字典序排序
        // 使用自定义比较器比较两个循环移位
        Arrays.sort(suffixes, (a, b) -> {
            for (int i = 0; i < n; i++) {
                char ca = text.charAt((a + i) % n);
                char cb = text.charAt((b + i) % n);
                if (ca != cb) {
                    return ca - cb;
                }
            }
            return 0;
        });

        // 构建BWT结果（取每行最后一个字符）
        StringBuilder bwt = new StringBuilder();
        int primaryIndex = -1;

        for (int i = 0; i < n; i++) {
            int suffixStart = suffixes[i];
            // 最后一个字符是起始索引前一个位置的字符
            char lastChar = text.charAt((suffixStart + n - 1) % n);
            bwt.append(lastChar);

            // 记录原始字符串（以EOF开头）所在的行号
            if (suffixStart == 0) {
                primaryIndex = i;
            }
        }

        return new BWTResult(bwt.toString(), primaryIndex);
    }

    /**
     * BWT逆变换
     * @param result 变换结果
     * @return 原始字符串（不含结束标记）
     */
    public String inverseTransform(BWTResult result) {
        String bwt = result.bwtString;
        int primaryIndex = result.primaryIndex;
        int n = bwt.length();

        // 构建LF映射
        // 对于Last Column中的每个字符，找到其在First Column中的对应位置

        // 统计每个字符的出现次数
        int[] count = new int[256];
        for (int i = 0; i < n; i++) {
            count[bwt.charAt(i)]++;
        }

        // 计算每个字符在First Column中的起始位置（累积计数）
        int[] starts = new int[256];
        int sum = 0;
        for (int i = 0; i < 256; i++) {
            starts[i] = sum;
            sum += count[i];
        }

        // 计算Last Column中每个位置的"排名"（该字符第几次出现）
        int[] occurrences = new int[256];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) {
            char c = bwt.charAt(i);
            rank[i] = occurrences[c]++;
        }

        // LF映射: LF(i) = starts[c] + rank[i]，其中c = bwt[i]
        int[] lf = new int[n];
        for (int i = 0; i < n; i++) {
            char c = bwt.charAt(i);
            lf[i] = starts[c] + rank[i];
        }

        // 从primaryIndex开始，沿着LF映射回溯
        StringBuilder original = new StringBuilder();
        int idx = primaryIndex;
        for (int i = 0; i < n - 1; i++) { // 排除EOF
            idx = lf[idx];
            original.append(bwt.charAt(idx));
        }

        // 由于我们是从后往前构建的，需要反转
        return original.reverse().toString();
    }

    /**
     * Move-To-Front编码：将BWT结果进一步压缩
     * 利用BWT的聚类特性，将重复字符编码为较小的数字
     */
    public List<Integer> moveToFront(String input) {
        // 初始化符号表（按字典序排列所有可能出现的字符）
        List<Character> symbols = new ArrayList<>();
        for (int i = 0; i < 256; i++) {
            symbols.add((char) i);
        }

        List<Integer> result = new ArrayList<>();

        for (char c : input.toCharArray()) {
            int index = symbols.indexOf(c);
            result.add(index);

            // 将该字符移到表头
            symbols.remove(index);
            symbols.add(0, c);
        }

        return result;
    }

    /**
     * Move-To-Front解码
     */
    public String inverseMoveToFront(List<Integer> codes) {
        List<Character> symbols = new ArrayList<>();
        for (int i = 0; i < 256; i++) {
            symbols.add((char) i);
        }

        StringBuilder result = new StringBuilder();
        for (int index : codes) {
            char c = symbols.get(index);
            result.append(c);
            symbols.remove(index);
            symbols.add(0, c);
        }

        return result.toString();
    }

    /**
     * BWT结果封装类
     */
    public static class BWTResult {
        public final String bwtString;
        public final int primaryIndex;

        public BWTResult(String bwtString, int primaryIndex) {
            this.bwtString = bwtString;
            this.primaryIndex = primaryIndex;
        }
    }

    /**
     * 完整压缩流程：BWT + MTF + RLE（简化版）
     */
    public List<Integer> compress(String input) {
        // 1. BWT变换
        BWTResult bwtResult = transform(input);

        // 2. MTF编码
        List<Integer> mtf = moveToFront(bwtResult.bwtString);

        return mtf;
    }

    /**
     * 完整解压流程
     */
    public String decompress(List<Integer> mtfCodes, int primaryIndex) {
        // 1. MTF解码
        String bwtString = inverseMoveToFront(mtfCodes);

        // 2. BWT逆变换
        BWTResult result = new BWTResult(bwtString, primaryIndex);
        return inverseTransform(result);
    }

    public static void main(String[] args) {
        BurrowsWheelerTransform bwt = new BurrowsWheelerTransform();

        // 测试数据：具有重复模式的文本
        String testData = "banana_bandana_canada_nabanana";

        System.out.println("原始字符串: " + testData);
        System.out.println("原始长度: " + testData.length());

        // 正向变换
        BWTResult result = bwt.transform(testData);
        System.out.println("\nBWT变换结果: " + result.bwtString);
        System.out.println("主索引: " + result.primaryIndex);

        // 分析BWT结果的聚类特性
        int runLength = calculateMaxRun(result.bwtString);
        System.out.println("最大连续重复字符长度: " + runLength);

        // MTF编码
        List<Integer> mtf = bwt.moveToFront(result.bwtString);
        System.out.println("\nMTF编码结果: " + mtf);

        // 统计MTF编码的分布（小数字越多说明压缩潜力越大）
        int smallCodes = 0;
        for (int code : mtf) {
            if (code < 5) smallCodes++;
        }
        System.out.printf("MTF小编码(<5)比例: %.2f%%\n", 
            100.0 * smallCodes / mtf.size());

        // 完整解压验证
        String recovered = bwt.decompress(mtf, result.primaryIndex);
        System.out.println("\n解压后字符串: " + recovered);
        System.out.println("数据一致性: " + testData.equals(recovered));
    }

    private static int calculateMaxRun(String s) {
        if (s.isEmpty()) return 0;
        int maxRun = 1, currentRun = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                currentRun++;
                maxRun = Math.max(maxRun, currentRun);
            } else {
                currentRun = 1;
            }
        }
        return maxRun;
    }
}

算法原理深入

为什么BWT能产生聚类效果？

考虑字符串”banana”的所有循环移位：

banana$
anana$b
nana$ba
ana$ban
na$bana
a$banan
$banana

排序后（$为最小字符）：

$banana
a$banan
ana$ban
anana$b
banana$
na$bana
nana$ba

最后一列是”annb$aa”——注意字符’a’被聚集在一起。这是因为以相同前缀开头的行，它们的最后一个字符往往也相同。

LF映射的数学本质

LF映射利用了排序的稳定性：在Last Column中第k次出现的字符X，对应于First Column中第k次出现的字符X。这一一对应关系使得逆变换成为可能。

复杂度分析

实际应用

BWT广泛应用于：
– bzip2压缩工具：BWT + MTF + 哈夫曼编码的组合
– 生物信息学：DNA序列压缩与模式匹配（如Bowtie比对工具）
– 全文索引：FM-Index基于BWT构建，支持高效子串查询

总结

Burrows-Wheeler变换的精妙之处在于：
1. 完全可逆：不丢失任何信息，是确定性的排列
2. 聚类效应：使相似字符聚集，便于后续压缩
3. 与后缀数组等价：BWT本质上编码了后缀数组的信息

掌握BWT是理解现代压缩算法（bzip2）和生物信息学工具（Bowtie、BWA）的基础。