LZW压缩算法详解（C语言实现LZW编码与解码完整教程）

什么是LZW压缩算法？

LZW由Abraham Lempel、Jacob Ziv和Terry Welch共同提出，其核心思想是：通过构建一个“字典”来记录已经出现过的字符串，并用较短的代码代替重复出现的字符串，从而实现压缩。

例如，原始字符串 ABABABA 中，“AB”重复出现。LZW会先将“AB”加入字典，之后再遇到“AB”就用一个数字（比如256）代替，从而减少数据量。

LZW的核心原理

• 初始化字典：包含所有单字符（如ASCII 0-255）。
• 读取输入流，不断扩展当前匹配的字符串。
• 当发现当前字符串不在字典中时，输出前缀的编码，并将新字符串加入字典。
• 解压时，根据接收到的编码动态重建字典。

C语言实现LZW压缩

下面是一个简化但完整的LZW数据压缩实现。我们使用哈希表模拟字典，为便于理解，这里限制最大字典大小为4096（12位编码）。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_DICT_SIZE 4096#define INIT_DICT_SIZE 256typedef struct {    char* str;    int code;} DictEntry;// 简易哈希函数unsigned int hash(const char* s) {    unsigned int h = 0;    while (*s) h = h * 31 + *s++;    return h % MAX_DICT_SIZE;}// 在字典中查找字符串int find_in_dict(DictEntry dict[], const char* s) {    unsigned int idx = hash(s);    // 线性探测处理冲突    while (dict[idx].str != NULL) {        if (strcmp(dict[idx].str, s) == 0)            return dict[idx].code;        idx = (idx + 1) % MAX_DICT_SIZE;    }    return -1;}// 添加新条目到字典void add_to_dict(DictEntry dict[], const char* s, int code) {    if (code >= MAX_DICT_SIZE) return;    unsigned int idx = hash(s);    while (dict[idx].str != NULL)        idx = (idx + 1) % MAX_DICT_SIZE;    dict[idx].str = malloc(strlen(s) + 1);    strcpy(dict[idx].str, s);    dict[idx].code = code;}// LZW 压缩函数void lzw_compress(const char* input, FILE* out) {    DictEntry dict[MAX_DICT_SIZE] = {0};        // 初始化字典：0-255 对应 ASCII 字符    for (int i = 0; i < INIT_DICT_SIZE; i++) {        char s[2] = {i, '\0'};        add_to_dict(dict, s, i);    }        int next_code = INIT_DICT_SIZE;    char current[100] = "";        for (int i = 0; input[i] != '\0'; i++) {        char next[100];        sprintf(next, "%s%c", current, input[i]);                if (find_in_dict(dict, next) != -1) {            strcpy(current, next);        } else {            // 输出 current 的编码            int code = find_in_dict(dict, current);            fwrite(&code, sizeof(int), 1, out);                        // 将 next 加入字典            if (next_code < MAX_DICT_SIZE) {                add_to_dict(dict, next, next_code++);            }                        // 重置 current 为当前字符            sprintf(current, "%c", input[i]);        }    }        // 输出最后一个字符串的编码    if (strlen(current) > 0) {        int code = find_in_dict(dict, current);        fwrite(&code, sizeof(int), 1, out);    }}

LZW解压实现

解压过程不需要传输字典，而是根据压缩码流动态重建。这是LZW的巧妙之处！

// LZW 解压函数void lzw_decompress(FILE* in, FILE* out) {    char dict[MAX_DICT_SIZE][100] = {0};        // 初始化字典    for (int i = 0; i < INIT_DICT_SIZE; i++) {        dict[i][0] = (char)i;        dict[i][1] = '\0';    }        int next_code = INIT_DICT_SIZE;    int prev_code, current_code;        // 读取第一个编码    if (fread(&prev_code, sizeof(int), 1, in) == 0) return;    fprintf(out, "%s", dict[prev_code]);        while (fread(¤t_code, sizeof(int), 1, in)) {        char* entry;        if (current_code < next_code) {            entry = dict[current_code];        } else if (current_code == next_code) {            // 特殊情况：当前编码等于下一个可用编码            char temp[100];            sprintf(temp, "%s%c", dict[prev_code], dict[prev_code][0]);            entry = temp;        } else {            fprintf(stderr, "错误：无效编码 %d\n", current_code);            return;        }                fprintf(out, "%s", entry);                // 将新字符串加入字典        if (next_code < MAX_DICT_SIZE) {            sprintf(dict[next_code], "%s%c", dict[prev_code], entry[0]);            next_code++;        }                prev_code = current_code;    }}

使用示例

你可以这样调用上述函数：

int main() {    const char* text = "ABABABA";        // 压缩    FILE* comp = fopen("compressed.lzw", "wb");    lzw_compress(text, comp);    fclose(comp);        // 解压    FILE* decomp = fopen("decompressed.txt", "w");    FILE* input = fopen("compressed.lzw", "rb");    lzw_decompress(input, decomp);    fclose(input);    fclose(decomp);        printf("压缩与解压完成！\n");    return 0;}

总结

通过本教程，你已经掌握了LZW压缩算法的基本原理，并用C语言实现LZW完成了压缩与解码。虽然实际应用中需考虑更多边界情况（如字典溢出、跨平台兼容性等），但这个简化版本足以帮助你理解核心逻辑。

记住，LZW编码解码的关键在于动态构建字典，而LZW数据压缩的优势在于无需预先知道数据统计特性，非常适合通用场景。

现在，你可以尝试优化这段代码，比如改用更高效的哈希表、支持二进制文件、或增加命令行接口！