LZW 压缩算法深入解析

一、算法背景与理论基础

1. 压缩的核心思想

LZW（Lempel–Ziv–Welch）算法是一种 无损数据压缩算法，由 Terry Welch 于 1984 年基于 LZ78 算法 改进提出。它的主要思想是：

用较短的编码（整数索引）替代重复出现的字符串模式，通过动态构建字典实现压缩。

与霍夫曼（Huffman）编码依赖统计频率不同，LZW 完全基于模式发现（pattern discovery），属于 基于词典（dictionary-based） 的压缩算法。

二、算法设计思想

LZW 的核心是“最长前缀匹配 + 自适应字典增长”。

1. 关键设计思想

• 字典初始化：字典中预存所有基本符号（例如 ASCII 码 0–255）。
• 最长匹配搜索：在当前输入流中找到最长的、已存在于字典中的字符串 w。
• 输出编码：输出 w 对应的字典编码。
• 扩展字典：将 w + c（c 为下一个新字符）加入字典。

这种机制确保字典逐步学习数据模式。

2. 压缩伪代码

Initialize dictionary with all single characters
w = ""                        // 当前匹配串
for each character c in input:
    if w + c in dictionary:
        w = w + c
    else:
        output code(w)
        add (w + c) to dictionary
        w = c
output code(w)

3. 解压伪代码

Initialize dictionary with all single characters
read first code k
output string(k)
w = string(k)
for each code k in remaining input:
    if k in dictionary:
        entry = string(k)
    else:
        entry = w + w[0]   // 处理未定义情况
    output entry
    add (w + entry[0]) to dictionary
    w = entry

三、压缩流程详解

TOBEORNOTTOBEORTOBEORNOT 这是 LZW 教材中经典的例子（因为它能充分展示字典的自适应增长过程）。 下面我们将从初始化字典 → 逐步压缩 → 输出编码 → 字典扩展全面展开。

一、实验环境与规则设定 字母表采用标准 ASCII（0–255）

为了便于展示，我们仅展示涉及到的字符及其对应字典索引 （初始字典中每个 ASCII 字符对应它的 ASCII 值）

每新增的字符串项从编码 256 开始编号

二、输入字符串：T O B E O R N O T T O B E O R T O B E O R N O T 

三、初始字典

🧠 四、压缩过程详解（逐步匹配） 我们从头扫描字符串，每次找“最长匹配的字符串 w”，输出其编码，并将“w + 下一个字符”加入字典。

📦 五、输出编码序列 根据上表输出： 84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263 也就是： T, O, B, E, O, R, N, O, T, TO, BE, OR, TOB, EO, RN, OT

四、解压流程详解

由于字典是动态的，解码端必须与压缩端同步构建相同字典。

关键问题：

• 解压时可能遇到**“字典中还未出现的编码”**；
• 这发生在某个字典项刚被添加但编码尚未输出之前。

解决方案：

当遇到未知编码 k 时，用 w + w[0] 作为解码结果。

示例：

已知 w = AB
当前编码 k = 8（未定义）
推测 entry = w + w[0] = AB + A = ABA

五、现实应用与影响力

LZW 在实际工业与标准中影响深远。

它被应用在多个领域与协议中：