Huffman 树的编码和解码

时间：2006-11-07 来源：rockylinux

     今天终于搞定了,Huffman树的编码和解码,不过现在还有一个问题,就是还没有把它放到字节中去,还是一个字符一个字符的存储的,不过感觉还是有进步的,作出来了,心里还是比较高兴的,不是这些天我不来写,而是我真的上不来了,本来速度就很慢,现在不用代理就上不了,所以只有晚上很晚才能登上来看看,现在时间真的是很紧张.      下面是Huffman编码的代码,我用python写的,python用起来还是比较简单的,比C++方便很多,实现比较简单,下面是代码: def select(li,n):
    t = []
    for i in li:
        if i[1] == 0:
            t.append(i)
    t.sort()
    return (li.index(t[0]),li.index(t[1])) def HuffmanCoding(lis):
    li = []
    for i in range(15):
        if i < 8:
            li.append([lis[i],0,0,0])
        else:
            li.append([0,0,0,0])     for i in range(8,15):
        s1,s2 = select(li[:i],i - 1)
        li[s1][1],li[s2][1] = i,i
        li[i][2],li[i][3] = s1,s2
        li[i][0] = li[s1][0] + li[s2][0]
    return li,lis def Single_Code(li,lis):
    huf = []
    for i in range(8):
        s = ''
        while(li[i][1]):
            if li[li[i][1]][2] == i:
                s += '0'
            else:
                s += '1'
            i = li[i][1]
        s = list(s)
        s.reverse()
        s = ''.join(s)
        huf.append(s)
    return huf def Coding(s,l):
    res = ''
    d = dict(l)
    for t in s:
        res += d.get(t)
    return res def DeCoding(s,li):
    s = list(s)
    res = ''
    while(s):
        i = -1
        while(li[i][2] or li[i][3]):
            if s:
                x = s.pop(0)
                if x == '0':
                    i = li[i][2]
                elif x == '1':
                    i = li[i][3]
            else:
                break
        res += target[i]
    return res

if __name__ == "__main__":
    lis = [5,29,7,8,14,23,3,11]
    li,lis = HuffmanCoding(lis)
    huf = Single_Code(li,lis)
    target = ['a','b','c','d','e','f','g','h']
    print '************************'
    print "char,weight,code"
    for i in zip(zip(target,lis),huf):
        print i
    l = zip(target,huf)
    s = 'abcdefgh'
    print '************************'
    print 'Before coding:' + s
    s = Coding(s,l)
    print "After coding :" + s
    s = DeCoding(s,li)
    print 'Now Decoding :' + s
    print '************************'
打印的输出结果是: ************************
char,weight,code
(('a', 5), '0001')
(('b', 29), '10')
(('c', 7), '1110')
(('d', 8), '1111')
(('e', 14), '110')
(('f', 23), '01')
(('g', 3), '0000')
(('h', 11), '001')
************************
Before coding:abcdefgh
After coding :00011011101111110010000001
Now Decoding :abcdefgh
************************ 用python写几十行就搞定了,用C++只写了一个编码就用了150行左右,看来python还是比较方便的,等有时间了在改成用字节存储的,今天太晚了,睡了.