多媒体实验1：算术编码的 python 实现

发表于 更新于 分类于 Disqus： 本文字数： 1.4k

前言

算术编码是一种编码算法，它比哈夫曼编码更高效。

由哈夫曼编码说起

哈夫曼编码对于更高频的符号，使用更短的编码。由于编码的前缀是不一致的（短编码不是长编码的前缀），所以我们可以保证唯一确定一个编码的长度不发生混淆。 可以通过构造一个特殊的二叉树的方式求哈夫曼编码，这个树就是哈夫曼树。下面是一个哈夫曼树示例。

哈夫曼树

香农的信息熵公式指出 $$H(x)=-\sum\limits_{x} P(x)log_{2}[P(x)]$$

其中 H(x)H(x) 为信息熵， P(x)P(x) 为每个符号出现的频次（概率）。

哈夫曼采用整数进行符号编码的，使得其不能更好的逼近信息熵极限。 例如，如果 A 的出现频次是 0.5，B 的出现频次是 0.4，C 的出现频次是 0.1。那么我们应该期待 B 的编码长度接近于 A，而不是 C，但是事实上 B 的编码长度和 C 一样长，是 A 的编码的两倍长。因此，其达不到最佳的编码长度。

一个更好的办法是：改用算术编码。

算术编码的原理

算术编码的本质思想，也是对于高频的字符进行短编码。但是具体实现并不相同。

设想一个区间被划分若干段。任给一个数字，通过比较我们就不难判断出其属于哪一个段。现在我们统计每个字符的频次，并将其依次对应到 [0,1)[0,1) 区间内同样长度的一段内。编码一个字符，我们就找出对应的区间，并把区间内的一个数字作为编码值，就能唯一确定这个编码。

例如: 假设对字符 A、B、C，有

  • P(A) = 0.5
  • P(B) = 0.4
  • P© = 0.1

则对应到区间如下 A:[0,0.5) B:[0.5,0.9) C:[0.9,1)A:[0, 0.5)\ B:[0.5, 0.9)\ C:[0.9, 1)

假设有编码值 E = 0.75，由于 0.75 在区间 [0.5,0.9)[0.5, 0.9) 之间，所以对 E 进行解码就有解码值 D = “B”

在一个字符串内，我们重复这个过程，每次都在之前的编码区间内继续按比例进行划分。这样，我们就得到了为一确定了一个区间可以代表原来的文本。在区间里，按"取二进制值最短的数作为编码值"的原则取编码，就能得到算术编码的编码值。

解码的时候，我们进行上述操作的逆操作即可：不断划分区间，看编码在那个区间内，就继续对齐划分区间。

特别需要注意的是，在取编码值的时候，我们只考虑其编码值最短，这会引起一个解码时的问题，即我们不知道能解码多少位。因为所有以 MSG 为前缀的信息 MSG’ 都处在 MSG 的编码区间内，我们难以确定是否 E 是 E(MSG),还是 E(MSGA) 或者 E(MSGB)。（吗）

算术编码的实现

下面给出我的算术编码代码思路。

  • decimal库：算术编码需要高精度的小数，在通常的浮点数运算中，很容易出现精度不够或者计算误差的情况（例如本应得到 0.3 但是实际内存中的值是 0.2999999999 或 0.3000000000041）。我们通过引入库 decimal 来解决计算位数和精度上的问题。
  • 预设的比例区间
  • 编码函数 encode：在上述区间内计算，得到一个结果区间。
  • 解码函数 decode：对编码值转换为十进制，在上述区间内计算，确定属于什么区间，不断解码出信息。
  • 十、二进制转换函数：我们使用十进制进行表示和计算，但是最终希望得到的编码是二进制值，因此，我们需要二者间的进制转换作为编码与解码的基础。特别的，bin() 求解的是区间（value。valueUp）区间内的最短值。具体来说，我们对左右区间不断转换二进制并比较，检查到二者的第一个相异位，此时左边界此为 0，右边界为1。我们取此位为 1。则得到最短编码值。只要我们认定编码值均小于等于右侧边界，就不会造成问题

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import decimal
# use Decimal for high precision

def bin(value, valueRange):
    result = list()
    valueUp = D(value+valueRange)
    value = D(value)

    while 1:
        value *= D("2")
        valueUp *= D("2")
        # 均大于
        if value >= 1:
            value -= D('1')
            valueUp -= D('1')
            result.append(1)
        # 均小于
        elif valueUp < 1:
            result.append(0)
        # low0up1
        else:
            if valueUp == D('1'):
                result.append(0)
            result.append(1)
            break
    while 1:
        i = result.pop()
        if i:
            result.append(i)
            break
    return result

def dec(value: list) -> decimal.Decimal:
    w = D('1')
    result = D('0')
    for i in range(0, len(value)):
        w *= D('0.5')
        result += w*value[i]
    return result

def encode():
    encode_str = input()
    low = [D('0')]

    for i in range(0, len(distribute)):
        low.append(D(distribute[i])+D(low[i]))
    nowRange = D('1')
    l = D('0')
    for i in encode_str:
        index = chars.index(i)
        l = l+nowRange*low[index]
        nowRange = nowRange*(low[index+1]-low[index])
    return bin(l, nowRange)
    # h = thedict.get(encode_str[i])
    # print(h)

def decode(codebin: list, codelenth):
    codedec = dec(codebin)
    result = str()
    low = [D('0')]
    for i in range(0, len(distribute)):
        low.append(D(distribute[i])+D(low[i]))
    nowRange = D('1')
    l = D('0')
    st = D('0')
    for j in range(0, codelenth):
        for i in range(1, len(low)):
            st = (low[i])*nowRange+l
            # ed = st + nowRange
            if codedec < st:
                index = i-1
                # index = chars.index(i)
                l = l+nowRange*low[index]
                nowRange = nowRange*(low[index+1]-low[index])
                result += chars[index]
                break
    return result

if __name__ == '__main__':
    D = decimal.Decimal
    decimal.getcontext().prec = 32

    chars = input("Dict:").split(',')
    # if default
    if chars[0] == "0":
        chars = ["A", "B", "C", "D"]
        distribute = [D('0.1'), D('0.4'), D('0.2'), D('0.3')]
    else:
        distribute = input("Distribute:").split(",")
    ans = encode()

    print(str(ans))

    ans = decode(ans, 7)

    print(ans)

参考资料