算法概述
LZ78是由 Abraham Lempel 和 Jacob Ziv 于1978年提出的经典无损压缩算法，是LZ系列压缩算法的第二个里程碑。与1977年提出的LZ77采用滑动窗口策略不同，LZ78采用动态字典机制：在编码过程中维护一个从空开始逐步增长的字符串表，用较短的索引号替代重复出现的字符串，从而实现数据压缩。
LZ78及其变种（如LZW）广泛应用于GIF图像格式、Unix compress工具、V.42bis调制解调器标准等场景，是理解现代压缩算法的必修内容。
核心思想
编码过程
- 初始化字典：仅包含空字符串（索引0）
- 从输入读取字符，尝试在字典中找到最长匹配的前缀
- 输出匹配前缀的索引 + 下一个新字符
- 将”匹配前缀 + 新字符”加入字典
- 重复直到输入处理完毕
解码过程
- 初始化相同的空字典
- 读取每个编码对（索引, 字符）
- 根据索引从字典中取出字符串，追加字符后输出
- 将刚输出的完整字符串加入字典
- 重复直到所有编码对处理完毕
关键特性
- 字典自增长：无需预先传输字典，编码器和解码器同步构建
- 前缀性质：字典中每个字符串都是某个更早条目的前缀扩展，保证解码一致性
- 贪婪匹配：总是寻找最长匹配，最大化压缩效率
Java完整实现
import java.util.*;
/**
* LZ78压缩算法实现
* 核心：动态字典编码，用索引替代重复字符串
*/
public class LZ78 {
/**
* LZ78编码对：字典索引 + 下一个字符
*/
public static class CodePair {
public final int index; // 字典中匹配前缀的索引
public final char next; // 新字符
public CodePair(int index, char next) {
this.index = index;
this.next = next;
}
@Override
public String toString() {
return "(" + index + ", '" + next + "')";
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof CodePair)) return false;
CodePair other = (CodePair) o;
return index == other.index && next == other.next;
}
@Override
public int hashCode() {
return 31 * index + next;
}
}
/**
* LZ78编码器
*/
public static class Encoder {
/**
* 编码输入字符串为LZ78编码序列
* @param input 原始字符串
* @return 编码对列表
*/
public List<CodePair> encode(String input) {
List<CodePair> result = new ArrayList<>();
if (input == null || input.isEmpty()) {
return result;
}
// 字典：索引 -> 字符串
// 索引0表示空字符串
List<String> dictionary = new ArrayList<>();
dictionary.add(""); // 索引0：空字符串
int i = 0;
while (i < input.length()) {
// 寻找最长匹配前缀
int longestIndex = 0;
int longestLen = 0;
for (int idx = 1; idx < dictionary.size(); idx++) {
String dictStr = dictionary.get(idx);
int len = dictStr.length();
if (len > longestLen && i + len <= input.length()
&& input.substring(i, i + len).equals(dictStr)) {
longestIndex = idx;
longestLen = len;
}
}
// 下一个字符
char nextChar;
if (i + longestLen < input.length()) {
nextChar = input.charAt(i + longestLen);
} else {
// 到达末尾，用特殊标记
nextChar = '\0';
}
result.add(new CodePair(longestIndex, nextChar));
// 将新字符串加入字典
String newEntry = dictionary.get(longestIndex) + nextChar;
if (!newEntry.equals("\0") && !dictionary.contains(newEntry)) {
dictionary.add(newEntry);
}
i += longestLen + 1;
}
return result;
}
/**
* 优化的编码器：使用Trie树加速最长前缀匹配
* 时间复杂度从O(n^2)优化到O(n * L)，L为最长匹配长度
*/
public List<CodePair> encodeOptimized(String input) {
List<CodePair> result = new ArrayList<>();
if (input == null || input.isEmpty()) {
return result;
}
// 使用Trie树存储字典，加速前缀匹配
TrieNode root = new TrieNode();
// 插入空字符串（索引0）
root.index = 0;
int dictSize = 1; // 当前字典大小
int i = 0;
while (i < input.length()) {
TrieNode node = root;
int matchedIndex = 0;
int matchedLen = 0;
// 在Trie中查找最长匹配
for (int j = i; j < input.length(); j++) {
char c = input.charAt(j);
TrieNode child = node.children.get(c);
if (child == null) {
break;
}
node = child;
matchedIndex = node.index;
matchedLen = j - i + 1;
}
char nextChar = (i + matchedLen < input.length())
? input.charAt(i + matchedLen) : '\0';
result.add(new CodePair(matchedIndex, nextChar));
// 将新字符串插入Trie
if (nextChar != '\0') {
TrieNode newNode = new TrieNode();
newNode.index = dictSize++;
node.children.put(nextChar, newNode);
}
i += matchedLen + 1;
}
return result;
}
// Trie树节点
private static class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
int index = -1; // 在字典中的索引
}
}
/**
* LZ78解码器
*/
public static class Decoder {
/**
* 解码LZ78编码序列为原始字符串
* @param codes 编码对列表
* @return 原始字符串
*/
public String decode(List<CodePair> codes) {
if (codes == null || codes.isEmpty()) {
return "";
}
StringBuilder result = new StringBuilder();
// 字典同步构建
List<String> dictionary = new ArrayList<>();
dictionary.add(""); // 索引0：空字符串
for (CodePair code : codes) {
if (code.index < 0 || code.index >= dictionary.size()) {
throw new IllegalArgumentException("Invalid code index: " + code.index);
}
String prefix = dictionary.get(code.index);
String entry = prefix + code.next;
result.append(entry);
// 加入字典（避免重复）
if (!dictionary.contains(entry)) {
dictionary.add(entry);
}
}
return result.toString();
}
}
/**
* 将编码对序列序列化为字节数组（用于存储/传输）
*/
public static class Serializer {
/**
* 序列化为紧凑的字节表示
* 使用变长编码存储索引
*/
public byte[] serialize(List<CodePair> codes) {
// 简化实现：使用Java序列化
// 实际应用中应使用位打包等紧凑格式
StringBuilder sb = new StringBuilder();
for (CodePair cp : codes) {
sb.append(cp.index).append(',').append((int)cp.next).append(';');
}
return sb.toString().getBytes();
}
/**
* 从字节数组反序列化
*/
public List<CodePair> deserialize(byte[] data) {
List<CodePair> result = new ArrayList<>();
String str = new String(data);
if (str.isEmpty()) return result;
String[] pairs = str.split(";");
for (String pair : pairs) {
if (pair.isEmpty()) continue;
String[] parts = pair.split(",");
int index = Integer.parseInt(parts[0]);
char next = (char) Integer.parseInt(parts[1]);
result.add(new CodePair(index, next));
}
return result;
}
}
/**
* 计算压缩比
*/
public static double compressionRatio(String original, List<CodePair> compressed) {
int originalBits = original.length() * 16; // UTF-16
// 假设索引用12位，字符用16位
int compressedBits = compressed.size() * (12 + 16);
return (double) compressedBits / originalBits;
}
public static void main(String[] args) {
Encoder encoder = new Encoder();
Decoder decoder = new Decoder();
// 示例1：简单重复字符串
System.out.println("=== Test 1: Simple Repetition ===");
String test1 = "ABABABABAB";
List<CodePair> encoded1 = encoder.encode(test1);
System.out.println("Original: " + test1);
System.out.println("Encoded: " + encoded1);
String decoded1 = decoder.decode(encoded1);
System.out.println("Decoded: " + decoded1);
System.out.println("Match: " + test1.equals(decoded1));
System.out.printf("Compression ratio: %.2f%%%n",
compressionRatio(test1, encoded1) * 100);
// 示例2：自然语言文本
System.out.println("\n=== Test 2: Natural Language ===");
String test2 = "TOBEORNOTTOBEORTOBEORNOT";
List<CodePair> encoded2 = encoder.encode(test2);
System.out.println("Original: " + test2);
System.out.println("Encoded: " + encoded2);
String decoded2 = decoder.decode(encoded2);
System.out.println("Decoded: " + decoded2);
System.out.println("Match: " + test2.equals(decoded2));
System.out.printf("Compression ratio: %.2f%%%n",
compressionRatio(test2, encoded2) * 100);
// 示例3：高度重复的DNA序列
System.out.println("\n=== Test 3: DNA Sequence ===");
String test3 = "ATCGATCGATCGATCGATCGATCG";
List<CodePair> encoded3 = encoder.encode(test3);
System.out.println("Original: " + test3);
System.out.println("Encoded: " + encoded3);
String decoded3 = decoder.decode(encoded3);
System.out.println("Decoded: " + decoded3);
System.out.println("Match: " + test3.equals(decoded3));
System.out.printf("Compression ratio: %.2f%%%n",
compressionRatio(test3, encoded3) * 100);
// 示例4：对比优化版本
System.out.println("\n=== Test 4: Optimized vs Standard ===");
String test4 = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG " +
"THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG";
long start = System.nanoTime();
List<CodePair> standard = encoder.encode(test4);
long standardTime = System.nanoTime() - start;
start = System.nanoTime();
List<CodePair> optimized = encoder.encodeOptimized(test4);
long optimizedTime = System.nanoTime() - start;
System.out.println("Standard encoding time: " + standardTime / 1000 + "μs");
System.out.println("Optimized encoding time: " + optimizedTime / 1000 + "μs");
System.out.println("Standard result size: " + standard.size());
System.out.println("Optimized result size: " + optimized.size());
System.out.println("Results match: " + standard.equals(optimized));
// 示例5：长文本压缩测试
System.out.println("\n=== Test 5: Long Text Performance ===");
StringBuilder longText = new StringBuilder();
String phrase = "COMPRESSION ALGORITHMS ARE FUN AND USEFUL ";
for (int i = 0; i < 1000; i++) {
longText.append(phrase);
}
String test5 = longText.toString();
start = System.nanoTime();
List<CodePair> encoded5 = encoder.encodeOptimized(test5);
long encodeTime = System.nanoTime() - start;
start = System.nanoTime();
String decoded5 = decoder.decode(encoded5);
long decodeTime = System.nanoTime() - start;
System.out.println("Original length: " + test5.length() + " chars");
System.out.println("Encoded pairs: " + encoded5.size());
System.out.println("Encode time: " + encodeTime / 1_000_000 + "ms");
System.out.println("Decode time: " + decodeTime / 1_000_000 + "ms");
System.out.println("Correctness: " + test5.equals(decoded5));
System.out.printf("Compression ratio: %.2f%%%n",
compressionRatio(test5, encoded5) * 100);
// 展示字典增长
System.out.println("\n=== Dictionary Growth (Test 2) ===");
List<String> dict = new ArrayList<>();
dict.add("");
for (CodePair cp : encoded2) {
String entry = dict.get(cp.index) + cp.next;
if (!entry.equals("\0") && !dict.contains(entry)) {
dict.add(entry);
}
}
System.out.println("Final dictionary size: " + dict.size());
System.out.println("Dictionary entries: " + dict.subList(0, Math.min(15, dict.size())));
}
}
关键要点解析
1. LZ77 vs LZ78 vs LZW 对比
| 特性 | LZ77 | LZ78 | LZW |
|---|---|---|---|
| 核心机制 | 滑动窗口 | 动态字典 | 静态字典（扩展版LZ78） |
| 输出格式 | (偏移, 长度, 字符) | (索引, 字符) | 纯索引 |
| 字典管理 | 隐式窗口 | 显式字符串表 | 预初始化ASCII表 |
| 典型应用 | gzip, deflate | Unix compress | GIF, TIFF |
2. Trie树优化
标准实现中，每次查找最长匹配需要遍历整个字典，时间复杂度为 $O(n^2)$。使用Trie树（前缀树）可将查找优化到 $O(L)$，其中 $L$ 为最长匹配长度，整体编码复杂度降至 $O(n \cdot L)$。
3. 字典爆炸问题
LZ78的字典会无限增长。实际应用中需要设置字典上限（如LZW限定为4096条目），当字典满时采用清空策略或冻结策略控制内存。
复杂度分析
| 指标 | 标准实现 | Trie优化 |
|---|---|---|
| 编码时间 | $O(n^2)$ | $O(n \cdot L)$ |
| 解码时间 | $O(n \cdot D)$ | $O(n \cdot D)$ |
| 空间复杂度 | $O(n)$ | $O(n)$ |
其中 $n$ 为输入长度，$L$ 为最长匹配长度，$D$ 为字典平均条目长度。
应用场景
- 文本压缩：重复模式明显的文本数据
- 日志压缩：结构化日志中的重复字段
- DNA序列：生物信息学中重复碱基序列的压缩
- 协议数据：网络协议中的重复头部信息
- 教学演示：理解字典编码和压缩原理的最佳入门算法
LZ78以”动态字典”替代”滑动窗口”，用显式的字符串积累替代隐式的历史回溯，为后续LZW、DEFLATE等现代压缩算法奠定了理论基础。
