字符编码
编码指把相同信息在不同的形式间转化,例如把图片储存为像素(x,y,r,g,b),把直角坐标方程改写为极坐标方程,把26个字母用26个二进制数表示,把明文转为密码和密文等等。无论信息形式如何变化,它们依然是同样的信息。字符编码研究如何用二进制形式表示某种语言的字符,其可被分类为定长编码与变长编码。基础ASCII码是种定长编码,无论是英文逗号、空格、回车、换行甚至响铃都有自己的ASCII码。其定长策略是在所有二进制数(编码)前补0,保证每个编码都是7-Bit。强国官方编码GB18030是种变长编码,其有1/2/4字节三种长度,1字节长度的是ASCII的超集,2字节长度的是GBK的超集,4字节长度的是其他新加入的生僻的中文字符与中文符号。
前缀编码
对任意字符串的任意前缀编码方案,每个字符的编码都不是其他编码的前缀。任何前缀编码方案都可用二叉树(如上图)表示,其非叶节点的左/右边表示0/1,从根节点出发可根据编码方案“生成”编码树。由于前缀码间互不为前缀,故字符不会出现在非叶节点,故叶节点必为被编码字符本身。对字符串\(S\)与其前缀编码二叉树\(T\),设\(f(c)\)为字符\(c\)的出现次数,\(d(c)\)为字符\(c\)在前缀编码二叉树的深度,编码二叉树所对应的代价为\(B(T)=\sum f(c)d(c)\),然后研究如何找到最低代价(最优压缩率)的前缀编码方案。首先给出一些有用的引理:
1) 任意字符串都存在能达到其最优压缩率的前缀编码方案;
2) 最优压缩率的前缀编码二叉树必为满二叉树(所有节点出度都不等于1);
证明:若存在\(x\)只有单孩子\(y\),用\(y\)顶替\(x\)的位置可使\(y\)子树上所有叶节点的编码位数下降。
3) 将任意满二叉树的叶节点数目计为\(z\),则其非叶节点数目为\(z-1\);
证明:将任意非空二叉树的2/1/0出度节点数计为\(x\)/\(y\)/\(z\)。利用边数与节点数可建立等式\(x+y+z=2x+y+1\),所以有\(z=x+1\)。对于满二叉树恒有\(y=0\),所以非叶节点数为\(x=z-1\)。
利用上述引理,求字符串的最优编码的问题可以转化为求非空的满二叉树问题。
哈夫曼编码
哈夫曼编码是求字符串最优前缀编码的算法,编码方案对应的二叉树称为哈夫曼树。在讨论算法前给出引理:
1) 设\(x,y(x\leq y)\)为字符串\(S\)中出现次数最少的其中2个字符,那么\(S\)必然存在某个最优前缀编码树\(T\),在\(T\)中\(x\)与\(y\)为兄弟叶节点(\(x\)与\(y\)的编码的位数相等且仅仅在最末位不等);
证明:设\(a,b(a\leq b)\)为\(T\)深度最大非叶节点的双叶节点,则\(f(x) \leq f(a),f(y) \leq f(b)\),注意不同字母可能指代同个节点。交换\(a,x\)位置可得树\(T’\),代价差\(B(T)-B(T’)=f(x)d_T(x)+f(a)d_T(a)-f(x)d_T(a)-f(a)d_T(x)\),进一步整理得\(B(T)-B(T’)=(f(a)-f(x))(d_T(a)-d_T(x)) \geq 0\)。同理可交换\(T’\)中\(b\)与\(y\)得到编码树\(T’’\)满足\(B(T’)-B(T’’) \geq 0\)。由于\(T\)最优故\(T’’\)必为最优。
2) 设\(x,y(x\leq y)\)为字符串\(S\)中出现次数最少的其中2个字符,用\(S\)不包含的字符\(z\)替换\(x\)与\(y\)得到新的字符串\(S’\)。设\(T’\)为\(S’\)的最优编码二叉树,若将\(T’\)中\(z\)对应叶节点新增左右孩子\(x\)与\(y\)得到新树\(T\),则\(T\)为\(S\)的其中一个最优树;
证明:首先考虑把\(B(T)\)用\(B(T’)\)来表示,\(f(x)d_T(x)+f(y)d_T(y)=(f(x)+f(y))(1+d_{T’}(z))\)。由于两树的其他部分相同,故\(B(T)=B(T’)+f(x)+f(y)\)。假设\(T\)非\(S\)的最优树,根据上述引理设\(T’’\)为\(S\)的最优树且\(x\)与\(y\)为\(T’’\)的一对兄弟叶节点。同理用\(z\)替换\(x\)与\(y\)的父节点得到\(T’’’\)则\(B(T’’’)=B(T’’)-f(x)-f(y)\)。整理上述结果可得\(B(T’’’)=B(T’’)-f(x)-f(y)<B(T)-f(x)-f(y)=B(T’)\)。由于\(T’\)为最优树,故假设不成立。
利用上述引理可以给出如下的算法流程:
1) 遍历整理字符串\(S\)为编码二叉树的节点,约定\(node.c\)为字符,\(node.f\)为字符在字符串的出现次数;
2) 将上述节点放入按\(node.f\)排序的最小优先队列\(Q\);
3) 从\(Q\)出队2个节点计为\(a\)与\(b\),将其作为新节点\(x\)的左右子树,并令\(x.f=a.f+b.f\),最后将\(x\)入队\(Q\)。持续的循环该步骤,直到\(Q\)中仅剩下1个节点,此时算法结束,该节点即哈夫曼树树根;
在使用二叉堆实现的优先队列时,该算法的时间复杂度显然是\(O(nlgn)\),其具体实现如下。该实现使用Python提供的堆(heapq)模块。对于二叉树节点(Node),code属性是与节点一一映射的入边代表的二进制值。
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 | from heapq import ( heapify, heappop, heappush ) class Node: def __init__(self,key): self.key = key self.freq = 0 self.parent = None self.code = None def __lt__(self, other): return self.freq < other.freq def huffman(msg): queue = {} for i in msg: if not queue.get(i): queue[i] = Node(i) queue[i].freq += 1 queue = list(queue.values()) leafs = queue[:] heapify(queue) while len(queue) >= 2: x = heappop(queue) y = heappop(queue) z = Node(None) z.freq = x.freq + y.freq x.parent = z x.code = '0' y.parent = z y.code = '1' heappush(queue,z) codes = {} for n in leafs: k = n.key l = [] while n.parent: l.append(n.code) n = n.parent l.reverse() codes[k] = ''.join(l) return codes |