Huffman 树的编码和解码
今天终于搞定了,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
for i in range(8,15):
s1,s2 = select(li[:i],i - 1)
li[s1][1],li[s2][1] = i,i
li[2],li[3] = s1,s2
li[0] = li[s1][0] + li[s2][0]
return li,lis
def Single_Code(li,lis):
huf = []
for i in range(8):
s = ''
while(li[1]):
if li[li[1]][2] == i:
s += '0'
else:
s += '1'
i = li[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[2] or li[3]):
if s:
x = s.pop(0)
if x == '0':
i = li[2]
elif x == '1':
i = li[3]
else:
break
res += target
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还是比较方便的,等有时间了在改成用字节存储的,今天太晚了,睡了.