每日算法 — 使用java实现算术编码：区间细分与自适应概率模型

算术编码（Arithmetic Coding）是一种高效的无损熵编码技术，由Jorma Rissanen在1976年提出。与哈夫曼编码每次为整个符号分配整数位不同，算术编码将整个消息编码为一个位于[0,1)区间内的浮点数，可以实现 fractional bit allocation（小数位分配），在理论上无限接近信息熵极限。

算法核心思想

算术编码的核心思想是将整个输入序列映射到[0,1)区间内的一个子区间。每个符号根据其在当前概率模型中的概率占据对应比例的子区间。随着符号逐个处理，区间不断细分，最终输出该区间的二进制表示。

编码过程

1. 初始化当前区间为[low, high) = [0, 1)
2. 对于每个输入符号：
3. 根据概率模型将该区间按比例划分为若干子区间
4. 选择对应符号的子区间作为新的当前区间
5. 处理完所有符号后，输出当前区间内的任意一个数（通常取区间中点）的二进制表示

解码过程

1. 读取编码值（一个[0,1)区间内的数）
2. 初始化区间为[0, 1)
3. 循环：
4. 根据当前区间和概率模型确定该编码值对应的符号
5. 输出该符号
6. 将该符号对应的子区间作为新的当前区间
7. 重复直到解码出完整消息

Java完整实现

import java.util.*;

/**
 * 算术编码实现
 * 基于区间细分的熵编码，支持静态和自适应概率模型
 */
public class ArithmeticCoding {

    // 使用整数运算避免浮点精度问题
    // 用[0, WHOLE)表示[0, 1)区间
    private static final long WHOLE = 1L << 32; // 2^32
    private static final long HALF = WHOLE / 2;
    private static final long QUARTER = WHOLE / 4;

    /**
     * 频率表：统计每个符号的出现次数
     */
    public static class FrequencyTable {
        private final long[] frequencies;
        private long total;

        public FrequencyTable(int symbolCount) {
            this.frequencies = new long[symbolCount];
            // 初始化每个符号至少出现1次（避免零概率）
            for (int i = 0; i < symbolCount; i++) {
                frequencies[i] = 1;
            }
            this.total = symbolCount;
        }

        public void increment(int symbol) {
            frequencies[symbol]++;
            total++;
        }

        public long getLow(int symbol) {
            long sum = 0;
            for (int i = 0; i < symbol; i++) {
                sum += frequencies[i];
            }
            return sum;
        }

        public long getHigh(int symbol) {
            return getLow(symbol) + frequencies[symbol];
        }

        public long getTotal() {
            return total;
        }

        public int getSymbol(long value, long scale) {
            long target = value * total / scale;
            long sum = 0;
            for (int i = 0; i < frequencies.length; i++) {
                sum += frequencies[i];
                if (target < sum) {
                    return i;
                }
            }
            return frequencies.length - 1;
        }
    }

    /**
     * 算术编码结果
     */
    public static class EncodedResult {
        public final byte[] data;
        public final long length;
        public final int symbolCount;

        public EncodedResult(byte[] data, long length, int symbolCount) {
            this.data = data;
            this.length = length;
            this.symbolCount = symbolCount;
        }
    }

    /**
     * 静态算术编码
     * @param input 输入字节数组
     * @return 编码结果
     */
    public EncodedResult encode(byte[] input) {
        if (input.length == 0) {
            return new EncodedResult(new byte[0], 0, 256);
        }

        // 构建静态频率表
        FrequencyTable freq = new FrequencyTable(256);
        for (byte b : input) {
            freq.increment(b & 0xFF);
        }

        // 重新初始化用于编码（保持相同比例）
        long low = 0;
        long high = WHOLE;
        long pendingBits = 0;

        StringBuilder bitStream = new StringBuilder();

        for (byte b : input) {
            int symbol = b & 0xFF;
            long range = high - low;

            long symbolLow = freq.getLow(symbol);
            long symbolHigh = freq.getHigh(symbol);
            long total = freq.getTotal();

            // 区间细分
            high = low + range * symbolHigh / total;
            low = low + range * symbolLow / total;

            // 输出确定的位（E1/E2缩放）
            while (true) {
                if (high <= HALF) {
                    // E1: 区间完全在下半部分
                    bitStream.append('0');
                    appendPendingBits(bitStream, pendingBits, '1');
                    pendingBits = 0;
                    low = low * 2;
                    high = high * 2;
                } else if (low >= HALF) {
                    // E2: 区间完全在上半部分
                    bitStream.append('1');
                    appendPendingBits(bitStream, pendingBits, '0');
                    pendingBits = 0;
                    low = (low - HALF) * 2;
                    high = (high - HALF) * 2;
                } else if (low >= QUARTER && high <= 3 * QUARTER) {
                    // E3: 区间跨越中点
                    pendingBits++;
                    low = (low - QUARTER) * 2;
                    high = (high - QUARTER) * 2;
                } else {
                    break;
                }
            }
        }

        // 输出最终区间信息
        pendingBits++;
        if (low <= QUARTER) {
            bitStream.append('0');
            appendPendingBits(bitStream, pendingBits, '1');
        } else {
            bitStream.append('1');
            appendPendingBits(bitStream, pendingBits, '0');
        }

        // 将位流转为字节数组
        byte[] data = bitsToBytes(bitStream.toString());
        return new EncodedResult(data, input.length, 256);
    }

    /**
     * 算术解码
     */
    public byte[] decode(EncodedResult encoded, long originalLength) {
        String bitStream = bytesToBits(encoded.data);

        // 重建频率表（假设均匀初始化，实际应与编码端一致）
        FrequencyTable freq = new FrequencyTable(encoded.symbolCount);
        // 注：实际应用中频率表需要随解码同步更新或预先传输

        byte[] result = new byte[(int) originalLength];
        long low = 0;
        long high = WHOLE;
        long value = 0;

        // 读取前32位初始化value
        int bitPos = 0;
        for (int i = 0; i < 32 && i < bitStream.length(); i++) {
            value = (value << 1) | (bitStream.charAt(i) - '0');
            bitPos++;
        }

        for (int i = 0; i < originalLength; i++) {
            long range = high - low;
            long total = freq.getTotal();

            // 确定当前value对应的符号
            int symbol = freq.getSymbol(value - low, range);
            result[i] = (byte) symbol;

            // 更新区间
            long symbolLow = freq.getLow(symbol);
            long symbolHigh = freq.getHigh(symbol);

            high = low + range * symbolHigh / total;
            low = low + range * symbolLow / total;

            // E1/E2/E3缩放
            while (true) {
                if (high <= HALF) {
                    low = low * 2;
                    high = high * 2;
                    value = value * 2;
                    if (bitPos < bitStream.length()) {
                        value |= (bitStream.charAt(bitPos++) - '0');
                    }
                } else if (low >= HALF) {
                    low = (low - HALF) * 2;
                    high = (high - HALF) * 2;
                    value = (value - HALF) * 2;
                    if (bitPos < bitStream.length()) {
                        value |= (bitStream.charAt(bitPos++) - '0');
                    }
                } else if (low >= QUARTER && high <= 3 * QUARTER) {
                    low = (low - QUARTER) * 2;
                    high = (high - QUARTER) * 2;
                    value = (value - QUARTER) * 2;
                    if (bitPos < bitStream.length()) {
                        value |= (bitStream.charAt(bitPos++) - '0');
                    }
                } else {
                    break;
                }
            }
        }

        return result;
    }

    private void appendPendingBits(StringBuilder sb, long count, char bit) {
        for (int i = 0; i < count; i++) {
            sb.append(bit);
        }
    }

    private byte[] bitsToBytes(String bits) {
        int byteLength = (bits.length() + 7) / 8;
        byte[] result = new byte[byteLength];
        for (int i = 0; i < bits.length(); i++) {
            if (bits.charAt(i) == '1') {
                result[i / 8] |= (1 << (7 - (i % 8)));
            }
        }
        return result;
    }

    private String bytesToBits(byte[] data) {
        StringBuilder sb = new StringBuilder();
        for (byte b : data) {
            for (int i = 7; i >= 0; i--) {
                sb.append((b >> i) & 1);
            }
        }
        return sb.toString();
    }

    /**
     * 简化版：仅用于演示核心逻辑的浮点实现
     */
    public String encodeSimplified(String input) {
        // 统计频率
        int[] freq = new int[256];
        for (char c : input.toCharArray()) {
            freq[c]++;
        }

        double low = 0.0;
        double high = 1.0;

        for (char c : input.toCharArray()) {
            double range = high - low;

            // 计算累积分布
            double cumProb = 0.0;
            double charLow = 0.0;
            double charHigh = 0.0;

            for (int i = 0; i < 256; i++) {
                double p = (double) freq[i] / input.length();
                if (i == c) {
                    charLow = cumProb;
                    charHigh = cumProb + p;
                }
                cumProb += p;
            }

            high = low + range * charHigh;
            low = low + range * charLow;
        }

        return String.format("区间: [%.20f, %.20f), 中点: %.20f", low, high, (low + high) / 2);
    }

    public static void main(String[] args) {
        ArithmeticCoding ac = new ArithmeticCoding();

        // 简化版演示
        System.out.println("=== 简化版算术编码演示 ===");
        String simpleText = "AAB";
        System.out.println("输入: " + simpleText);
        System.out.println(ac.encodeSimplified(simpleText));

        // 完整编码演示
        System.out.println("\n=== 完整算术编码测试 ===");
        String testData = "ARITHMETIC_ENCODING_IS_EFFICIENT";
        byte[] input = testData.getBytes();
        System.out.println("原始数据: " + testData);
        System.out.println("原始长度: " + input.length + " 字节 = " + (input.length * 8) + " 位");

        EncodedResult encoded = ac.encode(input);
        System.out.println("编码后长度: " + encoded.data.length + " 字节 = " + (encoded.data.length * 8) + " 位");

        double ratio = 1.0 - (double) (encoded.data.length * 8) / (input.length * 8);
        System.out.printf("压缩率: %.2f%%\n", ratio * 100);

        // 计算信息熵
        double entropy = calculateEntropy(input);
        System.out.printf("信息熵理论下限: %.2f 位/符号\n", entropy);
        System.out.printf("实际编码: %.2f 位/符号\n", (double) (encoded.data.length * 8) / input.length);

        // 解码验证
        byte[] decoded = ac.decode(encoded, input.length);
        String decodedStr = new String(decoded);
        System.out.println("\n解码结果: " + decodedStr);
        System.out.println("数据一致性: " + testData.equals(decodedStr));
    }

    private static double calculateEntropy(byte[] data) {
        int[] freq = new int[256];
        for (byte b : data) {
            freq[b & 0xFF]++;
        }

        double entropy = 0.0;
        for (int f : freq) {
            if (f > 0) {
                double p = (double) f / data.length;
                entropy -= p * (Math.log(p) / Math.log(2));
            }
        }
        return entropy;
    }
}

算法原理深入

为什么算术编码优于哈夫曼？

哈夫曼编码为每个符号分配整数位。如果某个符号概率为0.4，其信息量为-log₂(0.4) ≈ 1.32位，但哈夫曼只能分配1位或2位。算术编码通过将多个符号一起编码，可以实现更精确的概率分配。

精度问题与整数实现

浮点实现存在精度溢出问题。实际应用中：
– 使用整数运算模拟[0, 2^N)区间
– 当区间缩小到无法区分符号时，输出已确定的位并重置区间
– 上述代码中的E1/E2/E3缩放就是这一机制

自适应模型

编码过程中动态更新频率表，可以更好地适应数据特征变化。解码端需要同步更新相同的模型。

复杂度分析

实际应用

算术编码是以下标准的核心组件：
– JPEG 2000图像：使用自适应算术编码替代哈夫曼
– H.264/H.265视频：CABAC（上下文自适应二进制算术编码）
– Bzip2：最后的编码阶段使用算术编码
– WebP图像：可选的算术编码模式

总结

算术编码代表了熵编码的理论极限：
1. 最优压缩率：无限接近香农熵
2. 灵活性高：支持静态和自适应概率模型
3. 实现复杂：需要处理精度问题和区间缩放

理解算术编码是掌握现代多媒体压缩标准（JPEG 2000、H.265）的必经之路。