前缀码、Huffman编码算法:
前缀码:给定一个序列的集合,若不存在一个序列是另一个序列的前缀,则该序列集合称为前缀码。
哈夫曼(Huffman)算法可用来设计前缀编码,用该算法构造一棵有n个叶子(每个叶子具有一个权值)的二叉树的过程如下:
(1)根据n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空。
(2)在F中选取两棵根结点的权值最小的树作为左右子树来构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权值之和。
(3)在F中删除这两棵树,同时将新得到的二叉树加入F中。
(4)重复(2)和(3),直到F中只含一棵树时为止。称这棵树为最优二叉树(或哈夫曼树)。
如果约定将每个结点的左分支表示字符“0”,右分支表示字符“1”,则可以把从根结点到某叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。
对于所有可能传输的字符,令每个字符对应一个叶结点,权值为其出现的频率,那么根据哈夫曼算法构造出二叉树后,就得到了每个字符的二进制编码。
根据构造过程可知,这种编码方案得到的字符的编码长度的数学期望值为最小,因此这种编码方案是一个最优前缀码。在构造过程中,每次都是选取两棵最小权值的二叉树进行合并,作出的是贪心选择。