每日算法 — 使用java实现数据压缩：LZ77滑动窗口与字典编码策略

引言

数据压缩是计算机科学中的经典课题，广泛应用于文件归档、网络传输和多媒体存储等领域。与已介绍过的霍夫曼编码（基于统计频率的变长编码）不同，LZ77算法采用基于字典的策略，通过查找重复出现的字符串片段来实现压缩。LZ77是现代无损压缩格式（如ZIP、GZIP、PNG）的核心基础。本文将用Java实现一个简化版LZ77压缩器，深入讲解滑动窗口、三元组编码与解码还原的完整流程。

LZ77算法原理

LZ77由Lempel和Ziv于1977年提出，其核心思想是：利用已经处理过的数据作为”字典”，将当前数据表示为对字典中已有片段的引用。

算法维护三个关键区域：

搜索缓冲区（Search Buffer）：已编码的历史数据，作为查找重复串的字典。大小通常为几千字节。
前瞻缓冲区（Lookahead Buffer）：待编码的未处理数据。
滑动窗口：搜索缓冲区与前瞻缓冲区的总和，随着编码推进而向前滑动。

编码输出：对于前瞻缓冲区中的每个位置，算法尝试在搜索缓冲区中找到最长的匹配前缀。如果找到匹配，输出三元组 (offset, length, nextChar)：
– offset：匹配串在搜索缓冲区中的起始位置距离当前位置的偏移量
– length：匹配串的长度
– nextChar：匹配后紧跟的下一个字符（解决零长度匹配问题）

如果没有找到匹配，输出 (0, 0, currentChar)。

编码示例

以字符串 "ABABABAB" 为例：

步骤	搜索缓冲区	前瞻缓冲区	最长匹配	输出三元组
1	空	ABABABAB	无	(0, 0, ‘A’)
2	A	BABABAB	无	(0, 0, ‘B’)
3	AB	ABABAB	“AB” @ offset=2, len=2	(2, 2, ‘A’)
4	ABAB	ABAB	“ABAB” @ offset=4, len=4	(4, 4, EOF)

原始8字节被压缩为3个三元组，若每个三元组占少量字节，则压缩效果显著。

解码过程

解码器维护一个输出缓冲区，对每一个输入三元组：
1. 若 offset == 0，直接输出 nextChar
2. 否则，从输出缓冲区的 offset 位置向前拷贝 length 个字符，再输出 nextChar

由于三元组引用的是已解码的数据，解码过程不需要额外的字典结构，且可以流式处理。

Java实现

以下是一个功能完整的简化版LZ77编解码器：

import java.util.*;

/**
 * LZ77数据压缩算法实现：滑动窗口 + 字典编码
 * 简化版：使用固定大小的搜索缓冲区和前瞻缓冲区
 */
public class LZ77Compressor {

    // LZ77三元组
    static class Token {
        int offset;    // 匹配偏移量（距离当前位置的偏移）
        int length;    // 匹配长度
        char nextChar; // 下一个字符（字面量）

        Token(int offset, int length, char nextChar) {
            this.offset = offset;
            this.length = length;
            this.nextChar = nextChar;
        }

        @Override
        public String toString() {
            return String.format("(%d,%d,%s)", offset, length,
                nextChar == '\0' ? "EOF" : "'" + nextChar + "'");
        }
    }

    // LZ77编码器
    static class Encoder {
        private final int windowSize;      // 滑动窗口大小（搜索缓冲区+前瞻缓冲区）
        private final int lookaheadSize;   // 前瞻缓冲区大小

        Encoder(int windowSize, int lookaheadSize) {
            this.windowSize = windowSize;
            this.lookaheadSize = lookaheadSize;
        }

        List<Token> encode(String input) {
            List<Token> tokens = new ArrayList<>();
            int pos = 0;
            int n = input.length();

            while (pos < n) {
                // 搜索缓冲区范围：[max(0, pos - windowSize + lookaheadSize), pos)
                int searchStart = Math.max(0, pos - windowSize + lookaheadSize);
                int searchEnd = pos;

                // 前瞻缓冲区范围：[pos, min(n, pos + lookaheadSize))
                int lookaheadEnd = Math.min(n, pos + lookaheadSize);

                int bestOffset = 0;
                int bestLength = 0;

                // 在搜索缓冲区中查找最长匹配
                for (int i = searchStart; i < searchEnd; i++) {
                    int len = 0;
                    // 尝试从位置i开始匹配前瞻缓冲区
                    while (pos + len < lookaheadEnd &&
                           i + len < searchEnd + len && // 允许匹配串跨越搜索缓冲区边界（自引用）
                           input.charAt(i + len) == input.charAt(pos + len)) {
                        len++;
                        // 限制匹配长度不超过前瞻缓冲区
                        if (len >= lookaheadSize) break;
                    }
                    if (len > bestLength) {
                        bestLength = len;
                        bestOffset = pos - i; // 偏移量为当前位置到匹配起点的距离
                    }
                }

                // 确定下一个字符
                char nextChar;
                if (pos + bestLength < n) {
                    nextChar = input.charAt(pos + bestLength);
                } else {
                    nextChar = '\0'; // EOF标记
                }

                tokens.add(new Token(bestOffset, bestLength, nextChar));
                pos += bestLength + (bestLength == 0 ? 1 : 1);
                // 注意：即使bestLength>0，也至少前进1个字符（nextChar已被编码）
                if (bestLength > 0) pos = Math.min(pos, n);
            }

            return tokens;
        }
    }

    // LZ77解码器
    static class Decoder {
        String decode(List<Token> tokens) {
            StringBuilder output = new StringBuilder();
            for (Token token : tokens) {
                if (token.offset == 0) {
                    // 无匹配，直接输出字面量
                    if (token.nextChar != '\0') {
                        output.append(token.nextChar);
                    }
                } else {
                    // 从输出缓冲区中回溯拷贝
                    int startPos = output.length() - token.offset;
                    for (int i = 0; i < token.length; i++) {
                        output.append(output.charAt(startPos + i));
                    }
                    if (token.nextChar != '\0') {
                        output.append(token.nextChar);
                    }
                }
            }
            return output.toString();
        }
    }

    // 计算压缩率
    static double compressionRatio(String original, List<Token> tokens) {
        // 假设每个token在二进制格式中占用固定字节
        // offset: 2 bytes, length: 1 byte, nextChar: 1 byte = 4 bytes/token
        int compressedBits = tokens.size() * 32;
        int originalBits = original.length() * 16; // Java char = 2 bytes
        return (double) compressedBits / originalBits;
    }

    // 计算更精确的压缩比（基于哈夫曼编码的token表示会更优）
    static void printStatistics(String original, List<Token> tokens) {
        System.out.printf("原始长度: %d 字符%n", original.length());
        System.out.printf("Token数量: %d%n", tokens.size());
        System.out.printf("Tokens: %s%n", tokens);

        // 理论压缩大小估算
        int maxOffset = tokens.stream().mapToInt(t -> t.offset).max().orElse(0);
        int offsetBits = 32 - Integer.numberOfLeadingZeros(Math.max(maxOffset, 1));
        int lengthBits = 8; // 1 byte for length
        int charBits = 16;  // 2 bytes for char
        int bitsPerToken = offsetBits + lengthBits + charBits;
        int totalBits = bitsPerToken * tokens.size();
        int originalBits = original.length() * 16;

        System.out.printf("估算压缩大小: %d bits (%d bytes)%n", totalBits, (totalBits + 7) / 8);
        System.out.printf("原始大小: %d bytes%n", original.length() * 2);
        System.out.printf("压缩率: %.2f%%%n", (double) totalBits / originalBits * 100);
    }

    public static void main(String[] args) {
        System.out.println("=== LZ77滑动窗口压缩算法演示 ===\n");

        Encoder encoder = new Encoder(4096, 18); // 4KB窗口，18字节前瞻
        Decoder decoder = new Decoder();

        // 示例1：高重复性字符串
        String test1 = "ABABABABABABABAB";
        System.out.println("--- 测试1：高重复字符串 ---");
        System.out.println("原始: " + test1);
        List<Token> tokens1 = encoder.encode(test1);
        printStatistics(test1, tokens1);
        String decoded1 = decoder.decode(tokens1);
        System.out.println("解码验证: " + decoded1);
        System.out.println("一致性: " + test1.equals(decoded1) + "\n");

        // 示例2：包含重复单词的文本
        String test2 = "the quick brown fox jumps over the lazy dog. " +
                       "the quick brown fox jumps over the lazy dog. " +
                       "the quick brown fox jumps over the lazy dog.";
        System.out.println("--- 测试2：重复文本 ---");
        System.out.println("原始: " + test2.substring(0, Math.min(80, test2.length())) + "...");
        List<Token> tokens2 = encoder.encode(test2);
        printStatistics(test2, tokens2);
        String decoded2 = decoder.decode(tokens2);
        System.out.println("一致性: " + test2.equals(decoded2) + "\n");

        // 示例3：低重复性随机文本（压缩效果差）
        String test3 = "abcdefghijklmnopqrstuvwxyz1234567890!@#$%^&*()";
        System.out.println("--- 测试3：低重复字符串 ---");
        System.out.println("原始: " + test3);
        List<Token> tokens3 = encoder.encode(test3);
        printStatistics(test3, tokens3);
        String decoded3 = decoder.decode(tokens3);
        System.out.println("一致性: " + test3.equals(decoded3) + "\n");

        // 示例4：二进制风格数据
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 100; i++) sb.append("0011001100110011");
        String test4 = sb.toString();
        System.out.println("--- 测试4：周期性二进制数据 ---");
        System.out.println("原始: " + test4.substring(0, 32) + "... (共" + test4.length() + "字符)");
        List<Token> tokens4 = encoder.encode(test4);
        printStatistics(test4, tokens4);
        String decoded4 = decoder.decode(tokens4);
        System.out.println("一致性: " + test4.equals(decoded4));
    }
}

关键设计要点解析

自引用匹配：LZ77的一大特点是允许匹配串跨越搜索缓冲区与前瞻缓冲区的边界，即引用尚未完全编码的数据。解码器在解码时按顺序处理，因此引用”未来”数据实际上引用的是”当前正在构建的缓冲区前端”。实现中通过 output.append(output.charAt(startPos + i)) 在解码时动态处理。

滑动窗口大小权衡：窗口越大，能找到更长匹配的概率越高，压缩率越好。但也会增加编码时的搜索时间和内存占用。GZIP使用32KB窗口和258字节最大匹配长度，是工程实践中的经典参数。

前瞻缓冲区大小：决定了单次编码输出的最大匹配长度。若前瞻缓冲区太小，可能截断长匹配；太大则会增加搜索开销。实际应用中通常设为几十到几百字节。

匹配搜索优化：朴素实现的时间复杂度为 O(W·L)（W 为窗口大小，L 为前瞻大小）。工程实现中通常使用哈希链或后缀树将单次搜索优化到 O(1) 或 O(log W)。

复杂度分析

编码（朴素实现）：最坏情况 O(n · W · L)，其中 n 为输入长度，W 为窗口大小，L 为前瞻大小。对于随机数据，实际接近 O(n · W)。
编码（哈希优化）：使用哈希表记录三元组出现位置，可优化至 O(n) 平均时间。
解码：严格 O(n)，线性扫描三元组并输出。
空间复杂度：编码器 O(W + L)，解码器 O(n)（输出缓冲区）。

与霍夫曼编码的结合

单独使用LZ77通常只能达到中等压缩率。现代压缩工具（如DEFLATE，ZIP和GZIP的核心算法）将LZ77与霍夫曼编码结合：

第一阶段（LZ77）：将原始数据转换为三元组序列，消除重复模式
第二阶段（霍夫曼）：对三元组中的 offset、length 和 literal 分别构建霍夫曼编码表，进一步压缩

这种组合被称为 LZ77 + 霍夫曼，兼顾了字典编码的重复消除能力和统计编码的熵压缩能力。

扩展方向

LZ78与LZW：LZ77的改进版本，使用显式字典表而非滑动窗口，被应用于GIF和早期PDF格式。
BWT（Burrows-Wheeler变换）：与LZ系列不同，BWT通过排序相邻字符提升后续游程编码的效率，用于bzip2。
字典预处理：对于已知数据类型（如XML、JSON），可预加载常用模式到字典中，实现更高压缩率。

Tagged with: 字典编码字符串匹配数据压缩滑动窗口