Huffman的底层编码解码实现与压缩解压文件实操

Huffman的底层编码解码实现与压缩解压实操，文件已添加在项目中，可一键运行

AI Studio

573人浏览 · 2022-09-18 11:55:52

AI Studio · 2022-09-18 11:55:52 发布

1.Huffman简介

哈夫曼(Huffman)编码问题也就是最优编码问题，通过比较权值逐步构建一颗Huffman树，再由Huffman树进行编码、解码。

其步骤是先构建一个包含所有节点的线性表，每次选取最小权值的两个节点，生成一个父亲节点，该父亲节点的权值等于两节点权值之和，然后将该父亲节点加入到该线性表中，再重复上述步骤，直至构成一个二叉树，注意已经使用过的节点不参与

把每个字符看作一个单节点子树放在一个树集合中，每棵子树的权值等于相应字符的频率。每次取权值最小的两棵子树合成一棵新树，并重新放到集合中。新树的权值等于两棵子树权值之和。

其使用了贪心的思想，设和是频率最小的两个字符，则存在前缀码使得和具有相同码长，且仅有最后一位编码不同。换句话说，贪心选择保留了最优解。

算法步骤与思想如下

2.实现流程

2.1 定义结点类

import os
import pickle 
# 可对Python的原生对象进行打包存储
import struct
from paddle import inverse
# 用来存取二进制数据
import copy

# 定义结点类
class Node(object):
    def __init__(self,left=None,right=None,symbol='', weight = 0):
        """
        Args:
            left (_type_, optional): 左子树 Defaults to None.
            right (_type_, optional): 右子树 Defaults to None.
            symbol (str, optional): 字符 Defaults to ''.
            weight (int, optional): 权值 Defaults to 0.
        """
        self.left = left
        self.right = right
        self.symbol = symbol
        self.weight = weight
    
    #判断是否为叶子结点
    def isLeaf(self):
        if self.left==None and self.right==None:
            return True
        return False


# 字符与其编码
huffman_code = {}
# 根节点
huffman_root_node = Node()
# 字符及其出现次数
letter_frequency  = {}

2.2 从文件中读入一串字符串，统计每个字符的出现次数

2功能由readFile函数完成

def readFile(file_path):
    """
    Args:
        file_path (_type_): 文件路径
    在函数体内部把字符及其频率存入全局字典
    Returns:
        _type_: 总的文件字符串
    """
    with open(file_path,'r', encoding="utf-8") as f:
        text = ""
        for line in f.readlines():
            text += line
            for char in line:
                letter_frequency[char] = letter_frequency.get(char,0)+1
    return text

2.3 构建Huffman二叉树

3功能由createHuffmanTree函数完成

创建哈夫曼树，采用非递归的方式，步骤如下

1.将所有叶子节点的信息，（字符与频率）收集到一个list中

2.对list依照频率排升序

3.循环list的长度-1次

4.每次从list头部取出两个元素，即为最小的元素，将其权值合并后产生一个父节点

5.将父节点压入list，重复上述操作

6.最终list中仅剩一个节点，赋值给全局根节点

def createHuffmanTree():
    """
    创建哈夫曼树，并赋值给全局的根节点
    """
    global huffman_root_node
    n = len(letter_frequency)
    nodes_list = []
    for char,frequency in letter_frequency.items():
        nodes_list.append(Node(symbol=char,weight=frequency))
        
    for _ in range(n - 1):
        nodes_list.sort(key = (lambda n: n.weight))
        # 每次取出最小的元素
        left = nodes_list.pop(0)
        right = nodes_list.pop(0)
        # 合并为新的节点
        parent = Node("", left.weight + right.weight)
        # 新的节点作为父节点
        parent.left = left
        parent.right = right
        nodes_list.append(parent)
        
    if nodes_list:
        huffman_root_node=(nodes_list[0])

2.4 遍历二叉树，获得每个字符对应的编码表

4功能由getHuffmanMap函数完成

def getHuffmanMap(node, code=""):
    """
    递归给哈夫曼树的节点编码
    Args:
        node (_type_): 哈夫曼树的节点
        code (str, optional): 要编码的值（左侧+'0' 右侧+'1'）. Defaults to "".
    """
    if node.isLeaf():
        huffman_code[node.symbol] = code
    else:
        if node.left:
            getHuffmanMap(node.left, code + "0")
        if node.right:
            getHuffmanMap(node.right, code + "1")

2.5 展示与编码

根据编码表对读入字符串进行编码，并以二进制方式将全局的编码表和编码后的字符串写入二进制文件

借助pickle.dumps与struct.pack进行持久化到二进制文件的操作

将全局的letter_frequency和编码后的coded_data转为二进制，并写入new_file（注意：pickle只能以二进制格式存储数据到文件）

pickle模块实现了python的所有数据序列化和反序列化。它不是用于多种语言间的传输，它仅作为python对象的持久化或者python程序间进行互相传输对象的。

5功能由encode函数完成

def showTree(tree):
    """
    遍历一整颗树，并在叶子节点打印信息
    Args:
        tree (_type_): _description_
    """
    if tree:
        if tree.isLeaf():
            print(f'{tree.symbol}--{huffman_code[tree.symbol]}--{tree.weight}')
        showTree(tree.left)
        showTree(tree.right)


def encode(all_string, file):
    """
    Args:
        all_string (_type_):文件txt中所有字符
        file (_type_):要存储的文件路径
    """
    #  编码
    coded_data = ""
    for letter in all_string:
        # print(letter)
        # print(huffman_code[letter])
        # break
        coded_data += huffman_code[letter]
        
    # 将全局的letter_frequency和编码后的coded_data转为二进制，并写入new_file
    # pickle只能以二进制格式存储数据到文件
    huffman_map_bytes = pickle.dumps(huffman_code)

    # pickle模块实现了python的所有数据序列化和反序列化。它不是用于多种语言间的传输，
    # 它仅作为python对象的持久化或者python程序间进行互相传输对象的。
    with open(file, "wb") as f:
        #  存储全局的huffman_map
        # I unsigned int
        # s char[]
        # 存入两个数值，一个是len(huffman_map_bytes)使用unsigned int存储，一个是huffman_map_bytes，使用char存储
        # print(len(huffman_map_bytes))
        f.write(struct.pack('I%ds'%(len(huffman_map_bytes),),len(huffman_map_bytes),huffman_map_bytes))
        
        #  存储编码后数据coded_data
        # B unsigned char
        f.write(struct.pack('B',len(coded_data)%8))

        # print(len(coded_data)%8)
        # q long long
        # print(len(coded_data)//8)
        f.write(struct.pack('q',len(coded_data)//8))

        for index in range(0, len(coded_data),8):
            if index + 8 < len(coded_data):
                # print(coded_data[index:index+16])
                # break
                #  将8位二进制字符串（占8字节）转换为1位十进制（占1字节）整型
                f.write(struct.pack('B',int(coded_data[index:index+8],2)))
            else:
                #  最后若干位（<=8）转换成一个十进制整型
                f.write(struct.pack('B',int(coded_data[index:],2)))

2.6 从文件中解码

从二进制编码文件中读出存入的全局编码表和编码后的字符串，将编码表key，value对掉以便于解码，获得解码后的字符串，将字符串写入文件

但是这里有一个问题，存入时是8位bit存入，如果存入00000000，真正存入的是十进制数0，解码为2进制数后还是0，但是此时为1位的宽度，则在哈夫曼树解码时会遇到问题，因为原本是8位宽度存入，因此需要用zfill在左侧填充数据0

为了解码，需要将原有字典的key与value反转

6功能由decompress函数完成

def decompress(file):
    """
    Args:
        file (_type_): 二进制文件地址
    Returns:
        _type_:解码后的字符串
    """
    with open(file,"rb") as f:
        #  读取huffman_map
        length = struct.unpack('I',f.read(4))[0] #  前四个字节存储了huffman_map
        # print(length)
        huffman_map_byte = pickle.loads(f.read(length))

        moded_bytes = struct.unpack('B',f.read(1))[0]
        # print(moded_bytes)
        len_bytes = struct.unpack('q',f.read(8))[0]
        # print(len_bytes)

        bin_str_all=''
        # 读取完整部分数据（可以被8整除部分
        for index in range(0, len_bytes):
            byte_str = struct.unpack('B',f.read(1))[0]
            # print(byte_str)
            # 在左边填充0，知道填充至8位
            bin_str=bin(byte_str)[2:].zfill(8)
            bin_str_all+=bin_str
        # 读取不完整部分数据（不可以被8整除部分
        byte_str = struct.unpack('B',f.read(1))[0]
        # 主要区别体现在zfill(moded_bytes)部分，在左边填充0
        bin_str=bin(byte_str)[2:].zfill(moded_bytes)
        bin_str_all+=bin_str

        # print(len(bin_str_all))
        # 将原有字典key value对调
        inverse_mappint={}
        for k,v in huffman_map_byte.items():
            inverse_mappint[v]=k
        
        # print(inverse_mappint)

        # 解码后的字符串
        decode_str=''
        temp_str=''
        for s in bin_str_all:
            temp_str+=s
            # 因为没用公众前缀，因此只要出现在字典中，就可以成功解码
            if temp_str in inverse_mappint:
                decode_str+=inverse_mappint[temp_str]
                temp_str=''

        return decode_str

2.7 结果演示

其中发现了一个很大的问题，就是这里是对中文文本进行的编码，但是中文种类太多了，编码长度过长，还不如不编码，因此后面均换成英文文本进行处理

print('样例输入：如本路径下存在一个叫做en.txt的文件，只需要输入en即可')
name=input('请输入统一路径下的txt文件名[不包含.txt]：')
text=readFile(f'./{name}.txt')

# 创建哈夫曼树
createHuffmanTree()
# 获取编码与字符映射关系
getHuffmanMap(huffman_root_node)
# 打印树与其编码
showTree(huffman_root_node)

encode(text,f'./{name}_encode.hfm')
decode_str=decompress(f'./{name}_encode.hfm')

with open(f'./{name}_decode.txt','w') as f:
    f.write(decode_str)

样例输入：如本路径下存在一个叫做en.txt的文件，只需要输入en即可
请输入统一路径下的txt文件名[不包含.txt]：–--00000000000000000000000000--3
j--00000000000000000000000001--13
M--0000000000000000000000001--14
I--000000000000000000000001--15
2--00000000000000000000001--15
P--0000000000000000000001--15
J--000000000000000000001--17
C--00000000000000000001--18
S--0000000000000000001--22
F--000000000000000001--23
A--00000000000000001--25
E--0000000000000001--33
T--000000000000001--36
'--00000000000001--46

--0000000000001--47
.--000000000001--77
,--00000000001--100
m--0000000001--156
f--000000001--164
p--00000001--183
c--0000001--195
s--000001--497
i--00001--516
t--0001--673
a--001--674
 --01--1705
e--1--4734