本篇目录

通过阅读本篇文章你可以学习到:

1. 什么是LWZ压缩算法
2. 发展历程
3. 实现思路
4. Java代码实现

什么是LWZ压缩算法

LWZ 是一种通过建立字符串字典, 用较短的代码来表示较长的字符串来实现压缩的无损压缩算法, 由 Lempel-Ziv-Welch三人共同创造

发展历程

在信息论之父 C.E.Shannon利用数学语言阐明了概率与数据冗余度的关系之后(1984发表的论文 "A Mathematical Theory of Communication"), 工程技术人员便开始尝试实现具体的算法来进行高效, 快速的压缩.

1952年, D. A. Huffman在论文 "A Method for the Construction of Minimum Redundancy Codes"中提出了计算机界著名的哈弗曼编码: 一种完全依据字符出现概率来构造异字头的平均长度最短的码字的算法.

Hoffman编码效率高, 速度快, 实现方式灵活, 至今仍在数据压缩领域被广泛应用.

但是Hoffman编码仍旧不是数据压缩算法的终点. 1976年, J. Rissanen提出了算术编码, 并在后来跟部分匹配预测模型(PPM)相结合, 开发出了压缩效果近乎完美的算法. 如PPMC, PPMD或PPMZ之类的通用压缩算法都是这一思路的具体实现.

PPM模型和算术编码相结合最大程度地逼近了压缩的极限, 但由于算法的复杂性, 运行速度令人汗颜.

在1977年, 两位思维敏捷的犹太人 J. Ziv 和 A. Lempel 另辟奇径, 完全脱离Huffman及算术编码的设计思路, 创造出了一系列比Huffman编码更有效, 比算术编码更快速的压缩算法, LZ系列算法. 而在1984年, T. A. Welch在其发表的论文"A Technique for High Performance Data Compression"中描述了他对于LZ算法的改进, 也就是本文所讲的LZW算法.

如今, LZ77, LZ78, LZW算法以及他们的各种变体几乎垄断了整个通用数据压缩领域, 我们熟悉的PKZIP, WinZIP, WinRAR等压缩工具都是LZ系列算法的受益者.

实现思路

编码过程

1.初始状态, 用ASCII码表初始化字典. P(previous) 和 C(current)为空

2.读入新的字符C, 与P结合形成字符串 C + P

3.在字典里查找C + P, 如果:

--C+P在字典里, 则令P = C+P

--C+P不在字典里, 将P在字典中的索引输出, 在字典中为C+P建立一个新索引, 更新P = C

4.返回步骤2重复, 直至读完原字符串中所有字符.

解码过程

1.初始状态, 用ASCII码初始化字典. P 和 C为空

2.读入第一个编码, 解码输出

3.赋值P = C, 读入下一个编码并赋值给current

4.在字典中查找current, 如果:

--该编码在字典中

a) 令 s = dict[current]

b) 输出s

c) 新增字典条目 dict[previous] + s[0] (前一个编码的字符 + 当前编码字符的第一个字符)

--该编码不在字典中

a) 令s = dict[previous] + dict[previous][0]

b) 输出s

c) 新增字典条目s

5.返回步骤3重复, 直至读完所有记号.

Java代码实现

import java.util.ArrayList;

public class LZWcompressor {
    ArrayList dict;//字典
    int dictSize;//字典大小

    //初始化字典
    public void initDict() {
        dict = new ArrayList();
        //用ASCII码表初始化字典
        for(int i = 0; i <= 255; i++) {
            dict.add(String.valueOf(Character.toChars(i)));
        }
        dictSize = dict.size();
    }

    //压缩
    public String compress(String text) {
        //打印输入时内容
        System.out.println("压缩前: \n" + text);

        initDict();//初始化字典

        StringBuilder result = new StringBuilder();//用于存放压缩后的编码
        int i = 0;
        String previous = "";//存放前字符
        String current = "";//存放当前字符
        String sumStr = "";//存放P + C
        boolean isContain;//是否包含

        while(i <= text.length()) {//当读取索引指向字符串外的时候, 停止循环
            if(i == text.length()) {//当指针超出字符串时, 说明扫描到了末尾, 则将最后一个字符输出
                result.append(String.valueOf(dict.indexOf(previous)));
                break;
            }
            //读入新字符, 并查询是否存在于字典中
            current = String.valueOf(text.charAt(i));
            sumStr = previous + current;
            isContain = dict.contains(sumStr);
            if(isContain) {//如果当前字符包含在字典中, 则读取下一个字符并拼接在一起
                previous = sumStr;
            } else {
                dict.add(dictSize++, sumStr);//将这个新字符串添加到字典中
                result.append(String.valueOf(dict.indexOf(previous)) + " ");//输出未添加前的字符串的索引
                previous = current;//重置previous
            }
            i++;//指针后移
        }      
        //输出压缩效果
        System.out.println("压缩后: ");
        System.out.println(result); 
        // System.out.println("---------字典----------");
        // for (int j = 0; j < dict.size(); j++) {
        //     System.out.println(j + "\t" + dict.get(j));
        // }
        return result.toString();
    }

    //解压
    public String expand(String target) {
        initDict();//初始化字典

        //将目标按空格分割
        String[] compressed = target.split(" ");
        StringBuilder result = new StringBuilder();//用于存储解压后结果
        String current = compressed[0];//当前元素
        result.append(dict.get(Integer.parseInt(current)));//将第一个元素存入result, 因为第一个元素肯定存在字典中
        String previous = current;//前一个元素
        boolean isContain;

        for (int i = 1; i < compressed.length; i++) {
            current = compressed[i];
            isContain = dict.contains(dict.get(Integer.parseInt(current)));//判断当前元素是否存在字典中
            if(isContain) {//如果存在字典中, 则将当前元素存入result, 并在字典中新增条目
                String temp = dict.get(Integer.parseInt(current));
                result.append(temp);
                //将前一个元素和当前元素的第一位拼接, 存入字典中
                String s = dict.get(Integer.parseInt(previous)) + temp.charAt(0);
                dict.add(dictSize++, s);
            } else {
                String s = dict.get(Integer.parseInt(previous)) + dict.get(Integer.parseInt(previous)).charAt(0);
                result.append(s);
                dict.add(dictSize++, s);//往字典添加条目
            }
            previous = current;
        }
        System.out.println("解压后: ");
        System.out.println(result.toString());

        return result.toString();
    }
}

import java.util.ArrayList;
//测试代码
public class test {
    public static void main(String[] args) {
       LZWcompressor compressor = new LZWcompressor();
       String compressed = compressor.compress("HSX is a lovely girl, I love her so much");
       String expanded = compressor.expand(compressed);
    }
}

/**
输出结果: 

压缩前: 
HSX is a lovely girl, I love her so much
压缩后:
72 83 88 32 105 115 32 97 32 108 111 118 101 108 121 32 103 105 114 108 44 32 73 264 266 101 32 104 101 114 32 115 111 32 109 117 99 104
解压后: 
HSX is a lovely girl, I love her so much
**/

参考:

https://mp.weixin.qq.com/s/UnV3cJAVCXmrWB03jd47GA?forceh5=1

https://mp.weixin.qq.com/s/LdZm0NOhTlNEjiUiTkHj4Q