每日算法 — 使用java实现LZW压缩：字典编码与动态字符串表构建

LZW（Lempel-Ziv-Welch）压缩算法是一种经典的无损数据压缩算法，由Terry Welch在1984年提出。它通过动态构建字典来替换重复出现的字符串模式，实现高效压缩。与早期的LZ77和LZ78不同，LZW不需要在压缩输出中保留原始字符串，而是完全依赖动态字典进行编解码。

算法核心思想

LZW的核心思想是：在压缩过程中维护一个字符串字典，初始时字典包含所有单字符。然后扫描输入数据，不断寻找字典中已有的最长字符串，输出该字符串的索引，并将其扩展一个字符后加入字典。解码端通过相同的规则重建字典，从而还原原始数据。

压缩过程

1. 初始化字典，包含所有可能的单字符（如ASCII 0-255）
2. 读取输入数据，维护当前前缀字符串w
3. 读取下一个字符c，如果w+c在字典中，则w = w+c
4. 如果w+c不在字典中，输出w的索引，将w+c加入字典，然后w = c
5. 重复步骤3-4直到输入结束，最后输出w的索引

解码过程

1. 初始化相同的单字符字典
2. 读取第一个编码值，输出对应的字符串，设其为old
3. 读取下一个编码值：
4. 如果该编码在字典中，输出对应字符串str，将old + str[0]加入字典
5. 如果不在字典中（特殊情况），输出old + old[0]，并将其加入字典
6. 更新old = str，重复步骤3

Java完整实现

import java.util.*;

/**
 * LZW压缩算法实现
 * 基于动态字典的无损数据压缩
 */
public class LZWCompressor {

    // 字典最大容量，12位编码可表示4096个条目
    private static final int MAX_DICT_SIZE = 4096;
    private static final int INIT_DICT_SIZE = 256; // ASCII字符集

    /**
     * 压缩输入字节数组
     * @param input 原始数据
     * @return 压缩后的编码列表
     */
    public List<Integer> compress(byte[] input) {
        // 初始化字典：单字符映射到编码
        Map<String, Integer> dictionary = new HashMap<>();
        for (int i = 0; i < INIT_DICT_SIZE; i++) {
            dictionary.put(String.valueOf((char) i), i);
        }

        List<Integer> result = new ArrayList<>();
        String w = "";
        int dictSize = INIT_DICT_SIZE;

        for (byte b : input) {
            String c = String.valueOf((char) (b & 0xFF));
            String wc = w + c;

            if (dictionary.containsKey(wc)) {
                // 扩展当前匹配串
                w = wc;
            } else {
                // 输出当前匹配串的编码
                result.add(dictionary.get(w));

                // 将新字符串加入字典（如果未满）
                if (dictSize < MAX_DICT_SIZE) {
                    dictionary.put(wc, dictSize++);
                }

                // 从当前字符重新开始匹配
                w = c;
            }
        }

        // 输出最后剩余的部分
        if (!w.isEmpty()) {
            result.add(dictionary.get(w));
        }

        return result;
    }

    /**
     * 解压缩编码列表
     * @param compressed 压缩后的编码
     * @return 原始字节数组
     */
    public byte[] decompress(List<Integer> compressed) {
        // 初始化字典：编码映射到字符串
        Map<Integer, String> dictionary = new HashMap<>();
        for (int i = 0; i < INIT_DICT_SIZE; i++) {
            dictionary.put(i, String.valueOf((char) i));
        }

        List<Byte> result = new ArrayList<>();
        int dictSize = INIT_DICT_SIZE;

        // 读取第一个编码
        Integer oldCode = compressed.get(0);
        String oldStr = dictionary.get(oldCode);
        appendBytes(result, oldStr);

        for (int i = 1; i < compressed.size(); i++) {
            Integer newCode = compressed.get(i);
            String str;

            if (dictionary.containsKey(newCode)) {
                // 编码存在于字典中
                str = dictionary.get(newCode);
            } else {
                // 特殊情况：编码刚好是下一个要加入的条目
                str = oldStr + oldStr.charAt(0);
            }

            appendBytes(result, str);

            // 将旧串 + 新串首字符加入字典
            if (dictSize < MAX_DICT_SIZE) {
                dictionary.put(dictSize++, oldStr + str.charAt(0));
            }

            oldStr = str;
        }

        // 转换为字节数组
        byte[] output = new byte[result.size()];
        for (int i = 0; i < result.size(); i++) {
            output[i] = result.get(i);
        }
        return output;
    }

    private void appendBytes(List<Byte> list, String str) {
        for (char c : str.toCharArray()) {
            list.add((byte) c);
        }
    }

    /**
     * 将编码列表打包为字节数组（每个编码占2字节）
     */
    public byte[] packCodes(List<Integer> codes) {
        byte[] packed = new byte[codes.size() * 2];
        for (int i = 0; i < codes.size(); i++) {
            int code = codes.get(i);
            packed[i * 2] = (byte) (code >> 8);
            packed[i * 2 + 1] = (byte) code;
        }
        return packed;
    }

    /**
     * 从字节数组解包编码列表
     */
    public List<Integer> unpackCodes(byte[] packed) {
        List<Integer> codes = new ArrayList<>();
        for (int i = 0; i < packed.length; i += 2) {
            int code = ((packed[i] & 0xFF) << 8) | (packed[i + 1] & 0xFF);
            codes.add(code);
        }
        return codes;
    }

    /**
     * 计算压缩率
     */
    public double compressionRatio(byte[] original, List<Integer> compressed) {
        int originalBits = original.length * 8;
        int compressedBits = compressed.size() * 12; // 12位编码
        return 1.0 - (double) compressedBits / originalBits;
    }

    public static void main(String[] args) {
        LZWCompressor compressor = new LZWCompressor();

        // 测试数据：包含大量重复模式的文本
        String testData = "TOBEORNOTTOBEORTOBEORNOT" +
                         "TOBEORNOTTOBEORTOBEORNOT" +
                         "TOBEORNOTTOBEORTOBEORNOT";
        byte[] input = testData.getBytes();

        System.out.println("原始数据长度: " + input.length + " 字节");
        System.out.println("原始数据: " + testData.substring(0, 50) + "...");

        // 压缩
        List<Integer> compressed = compressor.compress(input);
        System.out.println("\n压缩后编码数: " + compressed.size());
        System.out.println("压缩编码: " + compressed.subList(0, Math.min(20, compressed.size())) + "...");

        // 打包为字节
        byte[] packed = compressor.packCodes(compressed);
        System.out.println("打包后长度: " + packed.length + " 字节");

        // 计算压缩率
        double ratio = compressor.compressionRatio(input, compressed);
        System.out.printf("压缩率: %.2f%%\n", ratio * 100);

        // 解压验证
        List<Integer> unpacked = compressor.unpackCodes(packed);
        byte[] decompressed = compressor.decompress(unpacked);
        String output = new String(decompressed);

        System.out.println("\n解压后长度: " + decompressed.length + " 字节");
        System.out.println("数据一致性: " + testData.equals(output));
    }
}

算法优化与变体

字典重置策略

当字典达到最大容量时，可以选择：
– 静态字典：停止添加新条目，继续使用现有字典
– 字典重置：清空字典重新开始，适用于数据特征发生变化的场景
– 清除不常用条目：LRU策略淘汰低频使用的模式

编码位数自适应

初期使用9位编码，随着字典增长逐步增加到10位、11位、12位，可以在字典较小时节省空间。

实际应用

LZW算法广泛应用于：
– GIF图像格式：采用变长LZW编码
– TIFF图像格式：支持LZW压缩选项
– PDF文档：可选的LZW压缩过滤器
– Unix compress工具：经典的.Z文件格式

复杂度分析

总结

LZW算法通过动态字典实现了高效的无损压缩，其核心优势在于：
1. 无需预扫描：一遍完成压缩，实时构建字典
2. 自适应性强：自动识别数据中的重复模式
3. 编解码对称：解码端可以独立重建相同的字典

理解LZW有助于深入学习现代压缩算法如DEFLATE（ZIP格式核心），后者正是结合了LZ77和哈夫曼编码的优势。