北京工业大学研究生算法作业(三)——哈夫曼编码

2023-09-23 30 0

Readme

运行环境:
win10 + pycharm + python3.7

数据文件:
input_assign03_01.dat,input_assign03_02.dat,input_assign03_03.dat,input_assign03_04.dat,input_assign03_05.dat,input_assign03_06.dat,input_assign03_07.dat

运行过程说明:
在CMD命令窗口下,运行python huffman.py+标志位+要操作的文件名称。
或者在命令窗口下,运行huffman.exe+标志位+要操作的文件名称。
标志位输入0则为压缩当前文件,输入1则为解压当前文件。
可以对已有测试用例执行仅可以执行压缩操作,无法执行解压缩操作,因为它是非压缩文件。
执行压缩和会在目录下生成对应文件,对该文件可以执行解压缩操作,并在目录下生成解压缩文件。

算法设计
一、构造huffman树
1. 创建n个初始化的Huffman树,每个树只包含单一的叶节点,叶节点纪录对应的字母和该字母出现的频率(weight);
2. 按照weight从小到大对其进行所有的Huffman树进行排序,取出其中weight最小的两棵树,构造一个新的Huffman树,新的Huffman树的weight等于两棵子树的weight之和,然后再加入到原来的Huffman树数组当中;
3. 反复上面的2中的操作,直到该数组当中只剩下一棵Huffman树,那么最后剩下来的那棵Huffman树就是我们构造好的Huffman编码树;
二、类的说明
class HuffNode(object):
定义一个HuffNode虚类,里面包含两个虚方法:
1. 获取节点的权重函数
2. 获取此节点是否是叶节点的函数
class LeafNode(HuffNode):
树叶节点类
class IntlNode(HuffNode):
中间节点类
class HuffTree(object):
哈夫曼树

代码

# -*- coding:utf-8 -*-
import six
import sysclass HuffNode(object):"""定义一个HuffNode虚类,里面包含两个虚方法:1. 获取节点的权重函数2. 获取此节点是否是叶节点的函数"""def get_wieght(self):raise NotImplementedError("The Abstract Node Class doesn't define 'get_wieght'")def isleaf(self):raise NotImplementedError("The Abstract Node Class doesn't define 'isleaf'")class LeafNode(HuffNode):"""树叶节点类"""def __init__(self, value=0, freq=0, ):"""初始化 树节点 需要初始化的对象参数有 :value及其出现的频率freq"""super(LeafNode, self).__init__()# 节点的值self.value = valueself.wieght = freqdef isleaf(self):"""基类的方法,返回True,代表是叶节点"""return Truedef get_wieght(self):"""基类的方法,返回对象属性 weight,表示对象的权重"""return self.wieghtdef get_value(self):"""获取叶子节点的 字符 的值"""return self.valueclass IntlNode(HuffNode):"""中间节点类"""def __init__(self, left_child=None, right_child=None):"""初始化 中间节点 需要初始化的对象参数有 :left_child, right_chiled, weight"""super(IntlNode, self).__init__()# 节点的值self.wieght = left_child.get_wieght() + right_child.get_wieght()# 节点的左右子节点self.left_child = left_childself.right_child = right_childdef isleaf(self):"""基类的方法,返回False,代表是中间节点"""return Falsedef get_wieght(self):"""基类的方法,返回对象属性 weight,表示对象的权重"""return self.wieghtdef get_left(self):"""获取左孩子"""return self.left_childdef get_right(self):"""获取右孩子"""return self.right_childclass HuffTree(object):"""huffTree"""def __init__(self, flag, value=0, freq=0, left_tree=None, right_tree=None):super(HuffTree, self).__init__()if flag == 0:self.root = LeafNode(value, freq)else:self.root = IntlNode(left_tree.get_root(), right_tree.get_root())def get_root(self):"""获取huffman tree 的根节点"""return self.rootdef get_wieght(self):"""获取这个huffman树的根节点的权重"""return self.root.get_wieght()def traverse_huffman_tree(self, root, code, char_freq):"""利用递归的方法遍历huffman_tree,并且以此方式得到每个 字符 对应的huffman编码保存在字典 char_freq中"""if root.isleaf():char_freq[root.get_value()] = codeprint(("it = %c  and  freq = %d  code = %s") % (chr(root.get_value()), root.get_wieght(), code))return Noneelse:self.traverse_huffman_tree(root.get_left(), code + '0', char_freq)self.traverse_huffman_tree(root.get_right(), code + '1', char_freq)def buildHuffmanTree(list_hufftrees):"""构造huffman树"""while len(list_hufftrees) > 1:# 1. 按照weight 对huffman树进行从小到大的排序list_hufftrees.sort(key=lambda x: x.get_wieght())# 2. 跳出weight 最小的两个huffman编码树temp1 = list_hufftrees[0]temp2 = list_hufftrees[1]list_hufftrees = list_hufftrees[2:]# 3. 构造一个新的huffman树newed_hufftree = HuffTree(1, 0, 0, temp1, temp2)# 4. 放入到数组当中list_hufftrees.append(newed_hufftree)# last.  数组中最后剩下来的那棵树,就是构造的Huffman编码树return list_hufftrees[0]def compress(inputfilename, outputfilename):"""压缩文件,参数有inputfilename:被压缩的文件的地址和名字outputfilename:压缩文件的存放地址和名字"""# 1. 以二进制的方式打开文件f = open(inputfilename, 'rb')filedata = f.read()# 获取文件的字节总数filesize = f.tell()# 2. 统计 byte的取值[0-255] 的每个值出现的频率# 保存在字典 char_freq中char_freq = {}for x in range(filesize):# tem = six.byte2int(filedata[x]) #python2.7 versiontem = filedata[x]  # python3.0 versionif tem in char_freq.keys():char_freq[tem] = char_freq[tem] + 1else:char_freq[tem] = 1# 输出统计结果for tem in char_freq.keys():print(tem, ' : ', char_freq[tem])# 3. 开始构造原始的huffman编码树 数组,用于构造Huffman编码树list_hufftrees = []for x in char_freq.keys():# 使用 HuffTree的构造函数 定义一棵只包含一个叶节点的Huffman树tem = HuffTree(0, x, char_freq[x], None, None)# 将其添加到数组 list_hufftrees 当中list_hufftrees.append(tem)# 4. 步骤2中获取到的 每个值出现的频率的信息# 4.1. 保存叶节点的个数length = len(char_freq.keys())output = open(outputfilename, 'wb')# 一个int型的数有四个字节,所以将其分成四个字节写入到输出文件当中a4 = length & 255length = length >> 8a3 = length & 255length = length >> 8a2 = length & 255length = length >> 8a1 = length & 255output.write(six.int2byte(a1))output.write(six.int2byte(a2))output.write(six.int2byte(a3))output.write(six.int2byte(a4))# 4.2  每个值 及其出现的频率的信息# 遍历字典 char_freqfor x in char_freq.keys():output.write(six.int2byte(x))#temp = char_freq[x]# 同样出现的次数 是int型,分成四个字节写入到压缩文件当中a4 = temp & 255temp = temp >> 8a3 = temp & 255temp = temp >> 8a2 = temp & 255temp = temp >> 8a1 = temp & 255output.write(six.int2byte(a1))output.write(six.int2byte(a2))output.write(six.int2byte(a3))output.write(six.int2byte(a4))# 5. 构造huffman编码树,并且获取到每个字符对应的 编码tem = buildHuffmanTree(list_hufftrees)tem.traverse_huffman_tree(tem.get_root(), '', char_freq)# 6. 开始对文件进行压缩code = ''for i in range(filesize):# key = six.byte2int(filedata[i]) #python2.7 versionkey = filedata[i]  # python3 versioncode = code + char_freq[key]out = 0while len(code) > 8:for x in range(8):out = out << 1if code[x] == '1':out = out | 1code = code[8:]output.write(six.int2byte(out))out = 0# 处理剩下来的不满8位的codeoutput.write(six.int2byte(len(code)))out = 0for i in range(len(code)):out = out << 1if code[i] == '1':out = out | 1for i in range(8 - len(code)):out = out << 1# 把最后一位给写入到文件当中output.write(six.int2byte(out))# 6. 关闭输出文件,文件压缩完毕output.close()def decompress(inputfilename, outputfilename):"""解压缩文件,参数有inputfilename:压缩文件的地址和名字outputfilename:解压缩文件的存放地址和名字"""# 读取文件f = open(inputfilename, 'rb')filedata = f.read()# 获取文件的字节总数filesize = f.tell()# 1. 读取压缩文件中保存的树的叶节点的个数# 一下读取 4个 字节,代表一个int型的值# python2.7 version# a1 = six.byte2int(filedata[0])# a2 = six.byte2int(filedata[1])# a3 = six.byte2int(filedata[2])# a4 = six.byte2int(filedata[3])# python3 versiona1 = filedata[0]a2 = filedata[1]a3 = filedata[2]a4 = filedata[3]j = 0j = j | a1j = j << 8j = j | a2j = j << 8j = j | a3j = j << 8j = j | a4leaf_node_size = j# 2. 读取压缩文件中保存的相信的原文件中 [0-255]出现的频率的信息# 构造一个 字典 char_freq 一遍重建 Huffman编码树char_freq = {}for i in range(leaf_node_size):# c = six.byte2int(filedata[4+i*5+0]) # python2.7 versionc = filedata[4 + i * 5 + 0]  # python3 vesion# 同样的,出现的频率是int型的,读区四个字节来读取到正确的数值# python3a1 = filedata[4 + i * 5 + 1]a2 = filedata[4 + i * 5 + 2]a3 = filedata[4 + i * 5 + 3]a4 = filedata[4 + i * 5 + 4]j = 0j = j | a1j = j << 8j = j | a2j = j << 8j = j | a3j = j << 8j = j | a4print(c, j)char_freq[c] = j# 3. 重建huffman 编码树,和压缩文件中建立Huffman编码树的方法一致list_hufftrees = []for x in char_freq.keys():tem = HuffTree(0, x, char_freq[x], None, None)list_hufftrees.append(tem)tem = buildHuffmanTree(list_hufftrees)tem.traverse_huffman_tree(tem.get_root(), '', char_freq)# 4. 使用步骤3中重建的huffman编码树,对压缩文件进行解压缩output = open(outputfilename, 'wb')code = ''currnode = tem.get_root()for x in range(leaf_node_size * 5 + 4, filesize):# python3c = filedata[x]for i in range(8):if c & 128:code = code + '1'else:code = code + '0'c = c << 1while len(code) > 24:if currnode.isleaf():tem_byte = six.int2byte(currnode.get_value())output.write(tem_byte)currnode = tem.get_root()if code[0] == '1':currnode = currnode.get_right()else:currnode = currnode.get_left()code = code[1:]# 4.1 处理最后 24位sub_code = code[-16:-8]last_length = 0for i in range(8):last_length = last_length << 1if sub_code[i] == '1':last_length = last_length | 1code = code[:-16] + code[-8:-8 + last_length]while len(code) > 0:if currnode.isleaf():tem_byte = six.int2byte(currnode.get_value())output.write(tem_byte)currnode = tem.get_root()if code[0] == '1':currnode = currnode.get_right()else:currnode = currnode.get_left()code = code[1:]if currnode.isleaf():tem_byte = six.int2byte(currnode.get_value())output.write(tem_byte)currnode = tem.get_root()# 4. 关闭文件,解压缩完毕output.close()if __name__ == '__main__':# 1. 获取用户的输入# FLAG 0 代表压缩文件 1代表解压缩文件# INPUTFILE: 输入的文件名# OUTPUTFILE:输出的文件名if len(sys.argv) != 3:print("please input the filename!!!")exit(0)else:FLAG = sys.argv[1]INPUTFILE = sys.argv[2]# 压缩文件if FLAG == '0':print('compress file')compress(INPUTFILE, 'compress_'+INPUTFILE)# 解压缩文件else:print('decompress file')decompress(INPUTFILE, 'decompress_'+INPUTFILE)
代码编程
赞赏

相关文章

关于红外相机热成像相机的一些sdk使用方法
typedef 函数指针用法
树莓派安装线性代数库 armadillo(debian系统)
树莓派下编译多个.cpp文件
泛在电力物联网、能源互联网与虚拟电厂
树莓派上跑一个opencv小程序(没有使用makefile)