LZW压缩算法详解（C++语言实现LZW无损数据压缩与解压缩）

LZW压缩的基本步骤

1. 初始化字典：将所有可能的单字符（如 ASCII 0-255）加入字典，编号为 0-255。
2. 读取输入流，从第一个字符开始，尝试匹配当前最长的已在字典中的字符串。
3. 当发现一个新字符串（即当前字符串 + 下一个字符不在字典中）时：
• 输出当前字符串对应的字典编号；
• 将这个新字符串加入字典（分配新编号）；
• 从下一个字符重新开始匹配。
4. 重复直到输入结束，最后输出剩余字符串的编号。

C++实现LZW压缩

下面是一个完整的 C++ 实现，包含压缩和解压缩两个部分。我们使用 std::map 来模拟字典，使用 std::vector<int> 存储输出的编码序列。

#include <iostream>#include <map>#include <vector>#include <string>using namespace std;vector<int> lzw_compress(const string& input) {    map<string, int> dict;    int dict_size = 256;    // 初始化字典：所有单字符    for (int i = 0; i < 256; ++i) {        dict[string(1, char(i))] = i;    }    vector<int> result;    string w = "";    for (char c : input) {        string wc = w + c;        if (dict.find(wc) != dict.end()) {            w = wc;        } else {            result.push_back(dict[w]);            dict[wc] = dict_size++;            w = string(1, c);        }    }    if (!w.empty()) {        result.push_back(dict[w]);    }    return result;}

C++实现LZW解压缩

解压缩过程是压缩的逆操作。它不需要传输字典，因为解压端可以根据压缩码流重建相同的字典。

string lzw_decompress(const vector<int>& compressed) {    vector<string> dict(256);    int dict_size = 256;    // 初始化字典    for (int i = 0; i < 256; ++i) {        dict[i] = string(1, char(i));    }    string result = dict[compressed[0]];    string w = result;    for (size_t i = 1; i < compressed.size(); ++i) {        int k = compressed[i];        string entry;        if (k < dict_size) {            entry = dict[k];        } else if (k == dict_size) {            entry = w + w[0];        } else {            throw runtime_error("Invalid compressed data");        }        result += entry;        dict.push_back(w + entry[0]);        dict_size++;        w = entry;    }    return result;}

完整测试示例

int main() {    string text = "ABABABAABABABBABABABBBABABAAABABABCCC";    cout << "原始文本: " << text << endl;    // 压缩    vector<int> compressed = lzw_compress(text);    cout << "压缩结果: ";    for (int code : compressed) {        cout << code << " ";    }    cout << endl;    // 解压缩    string decompressed = lzw_decompress(compressed);    cout << "解压文本: " << decompressed << endl;    if (text == decompressed) {        cout << "✅ 压缩/解压成功！" << endl;    } else {        cout << "❌ 失败！" << endl;    }    return 0;}

总结

通过本教程，你已经掌握了 LZW压缩算法 的核心原理，并用 C++语言实现LZW 完成了压缩与解压缩功能。LZW 是一种高效的 无损数据压缩 方法，适用于文本、日志、简单图像等重复模式较多的数据。

记住，LZW 的优势在于无需传输字典，解压端可自行重建，这使得它非常适合网络传输和存储优化。如果你正在学习数据压缩或准备面试，掌握 LZW编码解码 将是一个非常有价值的技能！

希望这篇教程对你有帮助！欢迎动手实践并修改代码以适应你的项目需求。