自己来写压缩算法——LZW
Oct 24, 2017
3 minute read

之前用哈夫曼算法,把固定长的字符编码根据其出现次数,编码为不固定长的编码。而这次介绍的算法恰恰相反,该算法是把不等长的字符串,编码为固定长的编码。

LZW

蓝博-立夫-卫曲编码法(Lempel-Ziv-Welch,缩写LZW),是亚伯拉罕·蓝波、杰可布·立夫与泰瑞·卫曲共同提出的一种无损数据压缩演算法。与霍夫曼编码相比,LZW把不同长度的字符串转换为固定长的编码。该方法不需要事先对数据做任何分析,所以可以流式地对文件进行处理。

原理

编码

首先先将单字符建立成一个字符串编码表,分别给予编号。

| string | code |
|--------|------|
| a      | 1    |
| b      | 2    |
| c      | 3    |

若数据为aabcaac,进过LZW编码后结果为112343,过程如下

| No. | cur | prefix | prefix in str->code | code | str->code |
|-----|-----|--------|---------------------|------|-----------|
| 1   | a   |        |                     |      |           |
| 2   | a   | a      | 1                   |      |           |
| 3   | b   | aa     | 0                   | 1    | aa -> 4   |
| 4   | c   | ab     | 0                   | 1    | ab -> 5   |
| 5   | a   | bc     | 0                   | 2    | bc -> 6   |
| 6   | a   | ca     | 0                   | 3    | ca -> 7   |
| 7   | c   | aa     | 1                   |      |           |
| 8   |     | aac    | 0                   | 4    | aac -> 8  |
| 9   |     | c      | 1                   | 3    |           |

整个算法过程如下:

  1. 取一个字符c
  2. 若字符串p + 字符c 字符串编码表中,字符串p += 字符c
  3. 若字符串p + 字符c 不在 字符串编码表中:
    1. 获取 字符串p 的编码
    2. 将 字符串p + 字符c 存入字符串编码表
    3. 字符串p = 字符c
  4. 重复以上步骤
  5. 最后 获取 字符串p 的编码

解码

一开始的字符串编码都是同一个,那么如何把112343解码为aabcaac

| string | code |
|--------|------|
| a      | 1    |
| b      | 2    |
| c      | 3    |

解码过程如下:

| No. | cur | str | prefix | prefix in str->code | str->code |
|-----|-----|-----|--------|---------------------|-----------|
| 1   | 1   | a   |        |                     |           |
| 2   | 1   | a   | a      | 1                   |           |
| 3   | 2   | b   | aa     | 0                   | aa -> 4   |
| 4   | 3   | c   | ab     | 0                   | ab -> 5   |
| 5   | 4   | aa  | bc     | 0                   | bc -> 6   |
| 6   |     | a   | ca     | 0                   | ca -> 7   |
| 7   | 3   | c   | aa     | 1                   |           |
| 8   |     |     | aac    | 0                   | aac -> 8  |

整个算法过程如下:

  1. 取一个编码k
  2. 对照 字符串编码表 取得字符串cs
    1. 从字符串cs中取得字符c
    2. 若字符串p + 字符c 字符串编码表中,字符串p += 字符c
    3. 若字符串p + 字符c 不在 字符串编码表中:
      1. 将 字符串p + 字符c 存入字符串编码表
      2. 字符串p = 字符c
    4. 重复以上步骤
  3. 重复以上步骤

实现

核心代码

照着算法步骤,我们很容易地写出以下的代码:

from six import int2byte


# 初始字符串编码表
# str  -> code
original_cdict = {b'a': 0, b'b': 1, b'c': 2}
# code -> str
original_kdict = [b'a', b'b', b'c']


def encode(data):
    '''
    >>> encode(b'aabcaac')
    [0, 0, 1, 2, 3, 2]
    '''
    cdict = original_cdict.copy()
    rv = []
    prefix = b''
    for c in data:
        if prefix + int2byte(c) in cdict:
            prefix += int2byte(c)
        else:
            rv.append(cdict[prefix])
            cdict[prefix + int2byte(c)] = len(cdict)
            prefix = int2byte(c)
    rv.append(cdict[prefix])
    return rv


def decode(data):
    '''
    >>> decode([0, 0, 1, 2, 3, 2])
    b'aabcaac'
    '''
    cdict = original_cdict.copy()
    kdict = original_kdict.copy()
    prefix = b''
    rv = b''
    for key in data:
        cs = kdict[key]
        for c in cs:
            if prefix + int2byte(c) in cdict:
                prefix += int2byte(c)
            else:
                cdict[prefix + int2byte(c)] = len(cdict)
                kdict.append(prefix + int2byte(c))
                prefix = int2byte(c)
        rv += cs
    return rv

以上就是LZW压缩算法的核心代码。若是要应用到文件上,还是有挺多步要走的。

读写文件

如何写一个真正实用的压缩程序

要做到压缩、解压缩,如何保存其压缩结果是一个躲避不了的问题。有了之前处理自己来写压缩算法——哈夫曼算法 哈夫曼算法的经验,我们知道要把压缩后的编码列表写入文件过程。先是将其变换成比特流,然后再把比特流写入到文件里。那么一个编码以多少长度写入文件里呢? 如果要压缩一个文件,初始字符串编码表长度就是256($2^8$)个。为了使LZW算法起到应有的作用,一个编码的长度应该大于8。长度为9,就能保存$2^9 = 512$个编码;长度为10,就能保存$2^{10} = 1024$个编码;长度为16,就能保存$2^{16} = 65536$个编码。若是选择长度短的,那么怎么压缩大文件呢;若是选择长度长的,那么目标文件更大呢;总不能选个超级长的长度,最后是能压缩大多数文件了,可哪能叫压缩吗(压缩结果大小反而大过源文件)。

面对这种情况,要增加一个“哨兵”。我们以长度16来保存编码,当字符串编码表长度快超过能保存的界限时,重置字符串编码表,从这个位置重新开始算法过程。哈,这个“哨兵”值肯定就是$2^{16} - 1 = 65535$。

新增的压缩处理过程:

  1. 编码结果转换为比特流,再写入文件(如何写入文件)
  2. 设置字符串编码表重置“哨兵”值(如何解决字符串编码表无节制增长)

核心代码加上以上的处理过程,就能写出一个真正实用的压缩程序了!

动态编码长度

让压缩结果大小再小点

当字符串编码表的长度为1024($2^{10}$)时,在此之前出现的所有编码都小于1024($2^{10}$),若用长度16来保存编码未免也太浪费空间了。 只有动态地改变保存长度,才能更加有效地利用存储空间,使压缩效果更好。 那如何做到这一点呢?还是利用用“哨兵”就能做到。

比如字符串编码表长度为512($2^9$)时,设立一个“变长哨兵值”为$2^{10} - 1 = 1023$,当字符串编码长度达到这个“变长哨兵值”之前,以长度10来保存,达到之后以长度11来保存,且生成新的“变长哨兵值”,如此重复,最后达到“重置哨兵值”

完整代码

GIST: LZW Encoding and Data Compression. | linw1995

参考



comments powered by Disqus