精华内容
下载资源
问答
  • 1 哈夫曼编码综述在计算机科学和信息论,哈夫曼编码是一种特殊类型的最优前缀码(prefix code),通常用于无损数据压缩(英文文本,更一般地说 ASCII 码位于 0-255 位的文本)。哈夫曼编码是一种变长编码,相比使用定长...

    1 哈夫曼编码综述

    在计算机科学和信息论,哈夫曼编码是一种特殊类型的最优前缀码(prefix code),通常用于无损数据压缩(英文文本,更一般地说 ASCII 码位于 0-255 位的文本)。哈夫曼编码是一种变长编码,相比使用定长的 ASCII 码,哈夫曼编码可以节省很多的空间 (试想如果一篇文章中全为同一种字符,对应的哈夫曼编码为 "0" ,那么原先表达 1 个字符的 1 字节就能用来表示 8 个字符)。

    哈夫曼压缩对频数最高的字符赋予较短的编码,实现压缩效率最大化

    哈夫曼编码以二叉树为基础实现的,二叉树到每一个叶子节点的路径是唯一的,对应的编码也就唯一。

    哈夫曼编码的前缀码唯一,从图 1 中可以看出,各编码的前缀码都是唯一的,这就保证了在字符表确定下,不断搜索一定可以定位到对应的字符。图 1 示例文本长度为 17,占用空间17字节。使用哈夫曼编码进行转码,对应的转码文本为:10110110001000111111111001000000000 ,长度为 35,按照 8 位一字节进行切割后,正文文本就变成了 5 字节 (不足 8 位需要补 0)

    对转码文本进行还原时,读取 1 位字符,对其后的字符搜索。如读取 "1" 后接着读取 "0" 变成了 "10" ,编码表中没有 "10",则继续向后读取 "101",此时码表中有 "101"项,对文本进行还原得到 "a",继续向后搜索,直到匹配完全文。图 1 哈夫曼树及编码示例

    2 哈夫曼压缩及解压基本原理

    哈夫曼压缩基本思想是将二进制代码分配给字符,用于减少编码这些符号的字符串比特数(如上图 1 中,原先表达一个字符 "e",需要1字节数据 "01100101",而在哈夫曼编码中,只需要1位数据 "0" 即可表达)。构造过程可以参考图 1 ,简书中较好的资料详细介绍了算法原理(但是代码运行不了,报错...)。

    算法的主要过程分为:构造哈夫曼编码表、转码压缩、转码解压。

    压缩与解压中,数据根据哈夫曼编码表进行转换,因此写入编码表信息是必须的。此外,字节位数不足 8 位时,需要补充 "0" 达到 8 位,而补 "0" 的情况又对解码信息有影响,还需要在文件中声明补 "0"情况。每一步的大致过程如下所示(在本文第 4 部分结合代码有更详细的示例):构造哈夫曼编码表

    Step1 遍历需要处理的字符串,得到每个字符出现的次数(频数)

    Step2 将频数最低的两位字符作为叶子节点,左子树频数大于右子树,构造分支节点,同时将分支节点作为新的字符,频数即为子叶频数之和,进行重新排序(如图 1 中,将 "bd" 作为新字符,进行重新排序)

    Step3 重复 Step1 和 Step2,直到所有字符编码完成

    Step4 从树的顶端开始编码,左子树编为 0,右子树编为 1,直到树的底端

    Step5 根据编码情况构造哈夫曼编码表转码压缩

    Step1 根据哈夫曼编码表将正文转换为 0-1 编码

    Step2 每 8 位编码进行一次切割,作为 1 个字节数据写入压缩文件

    Step3 文末不足 8 位则需要补 "0",直到刚好达到 8 位编码

    Step4 解码时避免补 "0" 干扰,需要将补 0 情况写入压缩文件中

    Step5 将码表写入压缩文件转码解压

    Step1 根据补 0 情况,删减文本

    Step2 读取哈夫曼编码表,作为转码对照表

    Step3 读取正文文本,与转码对照表进行比对,还原信息

    3 分析及扩展应用

    3.1 为什么哈夫曼编码是最优的?

    参考:维基百科香农源编码定理https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem​en.wikipedia.org

    (其实也很像运筹学课本上提到的最优带权连接图,但是证明实在是太长了。。。)

    也可以这样考虑:对频数最多的字符赋予最少的字符长度,依次类推。

    3.2 其他压缩算法的"后端"

    哈夫曼压缩作为数据流压缩的“先驱者”,由于哈夫曼编码简单、高速且无数据损失,常常被用于其他压缩算法的“后端”。如DEFLATE和多媒体编码器(如图像的JPEG,音频的MP3)都有自己的压缩算法,但都应用到了这种前缀码的思想。尽管大多数无损压缩算法都使用预定义的可变长度(如 LZW 算法)而不是使用哈夫曼算法,但这写算法也通常被称为 "Huffman codes"。

    3.3 层次聚类算法聚类树构造

    哈夫曼树构造过程与层次聚类算法思想也极其相似,将权值改为“样本距离”,并重新定义节点权值更新函数,即可得到层次聚类的聚类树构造。下图中展示了笔者使用哈夫曼树实现的层次聚类,并进行可视化的效果。图 2 经典层次聚类(Hierarchical Clustering)算法图 3 使用哈夫曼树构造的聚类树(试验数据为17年国赛建模B题数据,使用欧式距离度量权值)

    3.4 数据加密

    哈夫曼压缩中,最重要的哈夫曼编码表是能否解读数据关键。在压缩的时候,将码表与文本分离(或者打乱码表的表头、表文顺序,自定义一定规则进行匹配),可以实现数据加密。同时,若将码表的表头与表文、表文长度进行分别处理,则可以实现多端口数据加密验证。

    3.5 流式数据压缩

    哈夫曼编码可以认为是基于统计的压缩算法,统计过程是算法的核心,而流式数据随着文本不断扩展,权值可能发生变化,此时使用哈夫曼压缩不一定能取得很好的压缩效果,但在特定场景下,通过预先设定字符编码,也能取得较好的情况。如据统计,在英文小说中,文本使用 "e"、"t"、"a" 等字符的频数较高,则可以对这些字符进行预先编码,再根据各文本差异进行后续编码扩充。当然,其他编码算法如 LZW 编码、RLE 算法也给出了更好的实现方案,这些算法压缩效果好、速度快,但是性能不够好。

    3.6 压缩汉字构思

    汉字在 GB2312 编码存储占 2 字节,而英文文本、数字占 1 字节,因此可以考虑在 GB2312 编码下构造汉字映射表,实现汉字压缩。(只是构思,写不写的出来就不知道咯~)

    4 python3逐步实现哈夫曼压缩(附注 2 提供测试数据及完整源码)

    4.1 说明

    学习哈夫曼压缩过程中参考了许多资料,其中不少简书、CSDN 博文都给出了很漂亮的代码示例,但是也存在一些问题,如 python2 代码、结构混乱、使用类思想不便于新手理解(python的编程风格不同于JAVA)、没有给出压缩解压细节等。因此,本文以算法思想为蓝本逐步用代码进行实现,并在本文对每个部分的功能进行了详细说明。部分代码语句可能较为啰嗦,结构也不完美,但是可读性较强,便于理解。(完整代码见附注 2)

    使用的编程语言:python3.6.4 (Anaconda3)

    使用的编辑器:pycharm

    使用的模块:os、six、tkinteros 模块:使用了 os 模块的 path.splitext 函数,用于分割文件名与扩展名。如"test.txt",分割为 ('test', '.txt'),实现重写扩展名功能

    six 模块:使用了 six 模块的 int2byte 函数,用于将数字转化为字节存入文件

    tkinter 模块:选用,使用了 tkinter 模块的 filedialog.askopenfilenames 函数,用于实现弹窗打开文件的功能 (如图4)图 4 tkinter.filedialog.askopenfilenames 弹窗打开文件

    4.2 导入模块

    import os

    import six

    import tkinter

    4.3 打开文件

    f = open(file_name, 'r') # file_name为文件名

    file_data = check_binary(f.read())

    f.close()

    由于本文实现的是英文文本的压缩,此处仅考虑 ASCII 码在 [0, 255] 范围内的字符。自定义函数 check_binary 进行字符检查替换。check_binary:用于检查文件字符 ASCII 编码是否在 [0, 255] 范围,不在此范围则替换为空格

    def check_binary(input_data):

    # 检查文件编码,ASCII码超出255的字符替换为空格

    output_data = ''

    for word_index in range(len(input_data)):

    if ord(input_data[word_index]) >= 256:

    output_data += ' '

    else:

    output_data += input_data[word_index]

    return output_data

    4.4 统计各字符出现的频数

    统计各字符出现的频数,并保存在字典 char_freq 中setdefault(word, 0):创建键为 word,,初始值为 0 的对象,若字典中已存在此键,则不产生影响。

    char_freq = {}

    for word in file_data:

    char_freq.setdefault(word, 0)

    char_freq[word] += 1

    4.5 编码哈夫曼树

    编码哈夫曼树两个重要的过程:更新字符频数排序,更新字符编码,对这两个过程分别自定义函数 sort_tuple 和 get_coding_schedulesort_tuple(dist):传入一个字典 dist ,按照值大小顺序进行排序,并返回元组

    def sort_tuple(dist):

    # 传入字典,按照键大小顺序重排序

    return sorted(dist.items(), key=lambda x: x[1], reverse=True)get_coding_schedule(end1, end2, sort_list, code_schedule):传入排序表中频数最低的两位字符的 (键, 值) 元组、剔除传入的 end1, end2 后的字符排序列表、哈夫曼编码表,返回更新后的哈夫曼编码表哈夫曼表构造过程解析传入 end1 作为右子树,end2 作为左子树

    分别判断 end1 和 end2 的字符长度,如果长度为 1 说明该字符是叶子节点,否则说明该字符是分支节点如果 end1 是叶子节点,则设置编码值为 "1",如果 end2 是叶子节点,则设置编码值为 "0"

    如果 end1 是分支节点,则根据分支节点的字符串进行遍历,为每一个子叶编码值都添加前缀字符 "1",如果 end2 是分支节点,则根据分支节点的字符串进行遍历,为每一个子叶编码值都添加前缀字符 "0"

    在 sort_list 中添加由 end1 和 end2 构成的分支节点信息,结点信息包含所有子叶字符,所有子叶累计频数

    def get_coding_schedule(end1, end2, sort_list, code_schedule):

    # 传入 末端2位字符组 频数 序列列表(剔除末端字符) 哈夫曼编码表

    if len(end1[0]) == 1:

    code_schedule.setdefault(end1[0], '1')

    else:

    for k in end1[0]:

    code_schedule[k] = '1' + code_schedule[k]

    if len(end2[0]) == 1:

    code_schedule.setdefault(end2[0], '0')

    else:

    for k in end2[0]:

    code_schedule[k] = '0' + code_schedule[k]

    sort_list.append((end2[0] + end1[0], end1[1] + end2[1]))

    return code_schedule

    通过调用上面两个函数,完成哈夫曼编码的构造

    # 初始 字符--频数 列表

    sort_list = sort_tuple(char_freq)

    # 初始化哈夫曼编码表

    code_schedule = {}

    # 不断重排序,更新哈夫曼编码表及节点信息

    for i in range(len(sort_list) - 1):

    sort_list = sort_tuple(dict(sort_list))

    code_schedule = get_coding_schedule(sort_list.pop(), sort_list.pop(), sort_list, code_schedule)图 5 哈夫曼压缩及编码示例

    以图 5 为例,展示哈夫曼树及哈夫曼编码的构造过程:初次排序:[('e', 9), ('c', 4), ('a', 2), ('b', 2), ('d', 1)]

    传入 end1 = ('d', 1), end2 = ('b', 2), sort_list = [('e', 9), ('c', 4), ('a', 2)], code_schedule = {}

    end1 和 end2 的字符长度都为 1 ,分别设置编码 "1", "0"

    得到 sort_list = [('e', 9), ('c', 4), ('a', 2), ('bd', 3)], code_schedule = {'d': '1', 'b': '0'}

    第二次排序:[('e', 9), ('c', 4), ('bd', 3), ('a', 2)]

    传入 end1 = ('a', 2), end2 = ('bd', 3), sort_list = [('e', 9), ('c', 4)], code_schedule = {'d': '1', 'b': '0'}

    end1 字符长度为 1,设置编码 "1";end2 字符长度为 2 ,取 end2 的字符 "bd" ,对子叶的字符编码分别加上前缀字符 "0"

    得到 sort_list = [('e', 9), ('c', 4), ('bda', 5)], code_schedule = {'d': '01', 'b': '00', 'a': '1'}

    第三次排序:[('e', 9), ('bda', 5), ('c', 4)]

    传入 end1 = ('c', 4), end2 = ('bda', 5), sort_list = [('e', 9)], code_schedule = {'d': '01', 'b': '00', 'a': '1'}

    end1 字符长度为 1,设置编码 "1";end2 字符长度为 3,取 end2 的字符 "bda",对子叶的字符编码分别加上前缀字符 "0"

    得到 sort_list = [('e', 9), ('bdac', 9)], code_schedule = {'d': '001', 'b': '000', 'a': '01', 'c': '1'}

    第四次排序:[('e', 9), ('bdac', 9)]

    传入 end1 = ('bdac', 9), end2 = ('e', 9), sort_list = [], code_schedule = {'d': '001', 'b': '000', 'a': '01', 'c': '1'}

    end1 字符长度为 4,取 end1 的字符 "bdac",对子叶的字符编码分别加上前缀字符 "1";end2 字符长度为 1,设置编码 "0"

    得到 sort_list = [('ebdac', 18)],code_schedule = {'d': '1001', 'b': '1000', 'a': '101', 'c': '11', 'e': '0'}

    通过上面四次重复过程即完成了哈夫曼树及哈夫曼编码的构造

    4.6 文本信息转哈夫曼编码

    在 4.5 中构造了哈夫曼编码表,接下来要做的工作就是对照哈夫曼编码表,将文本信息转码并保存。要写入作为正文的信息有哈夫曼编码表、正文编码、补 0 。其中哈夫曼编码表只需要写入表文信息,正文部分需要进行转码处理,补 0 根据哈夫曼编码表表文信息+正文编码信息长度确定。如图 5 案例中,哈夫曼编码表表文长度 14,正文转码长度35,需要补 7 个 0 。正文信息存储结构如图 6 所示:图 6 待写入的文本信息

    # 文本信息转哈夫曼码

    # 哈夫曼 0-1 编码转码 + 正文文本

    code = ''.join(list(code_schedule.values()))

    for word in file_data:

    code += code_schedule[word]

    # 不足 8 位补 0,记录在 code_sup 中

    code_sup = 8 - len(code) % 8

    code += code_sup * '0'

    4.7 创建压缩文件并写入信息

    python 默认的存储数据以字符串形式存入,若要进行字节文件写入,需要使用二进制文件格式打开,还需要使用 six 模块下的 int2byte 函数对信息进行转码。

    依次将:补 0 情况,码表总长度,每一个字符的表文长度,表头字符写入文件,作为文件头,用于声明信息。随后再将 4.6 中正文文本信息写入文件。图 6 待写入文件头信息

    # 1.创建压缩文件

    f = open(os.path.splitext(file_name)[0] + '.qlh', 'wb')

    # 2.写入补 0 情况

    f.write(six.int2byte(code_sup))

    # 3.写入哈夫曼编码表(总长度+每一个编码长度+每一个编码对应的字符+转码信息)

    # 3.1 码表总长度(字符个数,与指针读取定位有关,分割码表与正文)

    f.write(six.int2byte(len(code_schedule)))

    # 3.2 储存每一个哈夫曼编码的位长

    for v in code_schedule.values():

    f.write(six.int2byte(len(v)))

    # 3.3 储存每一个哈夫曼编码配对字符 字符 ==> ASCII 码

    for k in code_schedule.keys():

    f.write(six.int2byte(ord(k)))

    # 3.4 以 8 为长度单位,将 0-1 字符转为对应的十进制数,映射为 ASCII 符号,写入正文文本

    for i in range(len(code) // 8):

    f.write(six.int2byte(int(code[8 * i:8 + 8 * i], 2)))

    # 4.关闭文件

    f.flush()

    f.close()

    print('压缩完成', file_name, '>>', os.path.splitext(file_name)[0] + '.qlh')

    4.8 实验示例

    本次使用英文 txt 文件 5 部作品进行实验测试:图 7 实验原文件,作品分别为:《哈利波特》4-6,《共产党宣言》,《一千零一夜》

    压缩效果:图 8 压缩效果对比

    可以看到,压缩效果显著。

    4.9 解压的实现

    解压是压缩的逆过程,怎么写入的就怎么读取。按照写入的过程分别读取以下信息:补 0 情况,用于删除正文信息中末尾补充的 "0"

    码表总长度(设为

    )

    码表表文长度:表文长度以 1 字节形式存储在文件中,根据码表总长度向后截取

    个字节即得到所有码表表文长度

    码表表头:码表表文长度之后就是码表表文(编码对应的原字符),也是向后继续截取

    个字节,每一个字节对应的 ASCII 码都对应着一个字符,将其转译作为哈夫曼编码表的表头信息

    码表表文:根据表文长度,在码表表头之后不断搜索截取表文长度指示的位数,获取到每个表头对应的表文,写入哈夫曼编码表。

    正文信息:所有表文读取结束后即复原了哈夫曼编码表,根据补 0 情况删除末尾的字符,剩余的文本即为原始文本信息。对于原始文本信息,每次对编码向后搜索、拼接,并与哈夫曼编码表进行匹配,若编码存在哈夫曼编码表表文中,则使用自定义函数 get_keys 进行转译得到对应的表头

    def get_keys(dict, value):

    # 传入字典,值,获取对应的键

    for k, v in dict.items():

    if v == value:

    return k

    解码过程不涉及太多技术性问题,此处直接给出所有的代码及简要注释,按照写入方式逆向操作就能还原文本。

    import os

    # 1.打开文件

    f = open(file_name, 'rb')

    # 2.读取信息

    file_data = f.read()

    f.close()

    # 3.分割信息

    # 3.1 获取补 0 位数

    code_sup = file_data[0]

    # 3.2 获取码表长度

    code_schedule_length = file_data[1]

    # 3.3 指针跳过 补0+码长+码符

    pointer = 2 * code_schedule_length + 2

    # 3.4 获取码表中每一个编码的长度

    code_word_len = [file_data[2 + i] for i in range(code_schedule_length)]

    # 3.5 编码表中字符长度总和,用于切割码表与正文

    sum_code_word_len = sum(code_word_len) // 8 + 1 if sum(code_word_len) % 8 != 0 else sum(code_word_len) // 8

    # 4.还原码表

    # 4.1 码表转译

    code_schedule_msg = ''

    for i in range(sum_code_word_len):

    code_schedule_msg += '0' * (10 - len(bin(file_data[pointer + i]))) + bin(file_data[pointer + i])[2:]

    # 4.2 初始化指针

    pointer = 0

    # 4.3 创建码表

    code_schedule = {}

    for i in range(code_schedule_length):

    code_word = chr(file_data[code_schedule_length + 2 + i]) # 码符

    code_schedule[code_word] = code_schedule_msg[pointer:pointer + code_word_len[i]] # 码符码文匹配,还原码表

    pointer += code_word_len[i]

    # 5.提取正文

    code = code_schedule_msg[pointer:]

    pointer = 2 * code_schedule_length + 2 + sum_code_word_len

    for number in file_data[pointer:]:

    code += '0' * (10 - len(bin(number))) + bin(number)[2:]

    # 删去补0

    code = code[:-code_sup]

    # 6.文本转译

    pointer = 0 # 指针归零

    # 初始化文本

    letter = ''

    # 限制最大搜索长度,提高效率

    max_length = max([len(list(code_schedule.values())[i]) for i in range(len(code_schedule.values()))])

    while pointer != len(code):

    for i in range(max_length):

    if code[pointer:pointer + i + 1] in code_schedule.values():

    letter += get_keys(code_schedule, code[pointer:pointer + i + 1])

    pointer += i + 1

    break

    # 7.创建解压文件

    f = open(os.path.splitext(file_name)[0] + '.txt', 'w+')

    f.write(letter)

    print('解压完成', file_name, '>>', os.path.splitext(file_name)[0] + '.txt')

    将上文中的压缩函数命名为 compress,解压函数命名为 decompress,并引入 tkinter 模块中的 filedialog.askopenfilenames 函数,即可实现弹窗点击文件并压缩、解压的功能。此外,通过自定义函数 compress_all、decompress_all、get_request 函数,进一步实现批量文件压缩解压功能。

    def compress_all(file_names):

    # 批量压缩文件

    for file_name in file_names:

    compress(file_name)

    def decompress_all(file_names):

    # 批量解压文件

    for file_name in file_names:

    decompress(file_name)

    class Inputerror(Exception):

    # 自定义异常

    def __init__(self, messages):

    super().__init__(messages)

    def get_request():

    file_name = tkinter.filedialog.askopenfilenames()

    ask = input('Compress or Decompress ? (C/D)').lower()

    if ask == 'd':

    decompress_all(file_name) # 解压文件

    elif ask == 'c':

    compress_all(file_name) # 压缩文件

    else:

    raise Inputerror("accept unknown command ,routine haven't started doing anything, please run it again")

    写在运行当前文件中执行的部分

    if __name__ == '__main__':

    import tkinter.filedialog

    get_request()

    while input('Continue ? (Y/N)').lower() == 'y':

    get_request()

    4.10 实验示例

    继续对 4.8 中的文件进行解压。先前提到,本文中的程序是对 ASCII 范围在 [0,255] 的字符进行压缩,并对超过范围的字符进行空格替换处理,因此文件中出现的少量数据损失属于正常现象。(哈利波特 5 文件中没有超过范围的字符,因此实现了完整的数据还原)图 9 压缩前与解压后文件对比

    5 附注 1:罗塞塔代码提供的哈夫曼编码树构造

    from heapq import heappush, heappop, heapify

    from collections import defaultdict

    def encode(symb2freq):

    """Huffman encode the given dict mapping symbols to weights"""

    heap = [[wt, [sym, ""]] for sym, wt in symb2freq.items()]

    heapify(heap)

    while len(heap) > 1:

    lo = heappop(heap)

    hi = heappop(heap)

    for pair in lo[1:]:

    pair[1] = '0' + pair[1]

    for pair in hi[1:]:

    pair[1] = '1' + pair[1]

    heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    return sorted(heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

    txt = "this is an example for huffman encoding"

    symb2freq = defaultdict(int)

    for ch in txt:

    symb2freq[ch] += 1

    huff = encode(symb2freq)

    print ("Symbol\tWeight\tHuffman Code")

    for p in huff:

    print("%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1]))

    测试文本:this is an example for huffman encoding

    输出结果:

    6 附注 2:实验数据及程序

    附件为百度网盘链接。其中,对 "data/实验数据" 中的文件进行压缩可以得到 "data/压缩文件" 中的文件,对 "data/压缩文件" 中的文件进行解压可以得到 "data/解压效果" 中的文件https://pan.baidu.com/s/1dgIAnIS-hW4QNFUWlo6YJQ​pan.baidu.com

    7 附注 3:LZW 算法简单实现

    LZW 对流式数据具有较好的压缩性能,基本思想为进一步对连续字符进行压缩替换(如 "abcd832abcd841abcd818" ,若用 "e" 代替 "abcd8" ,则原文本可以转化为 "e32e41e18",从而实现压缩),下面是压缩算法代码的简单实现。在上述测试数据中压缩效果表现不理想(重复文本过少),删去 write_file 部分(即不初始化码表)则性能极优,但是只能输出配对字符。这里产生的问题可能是我对 LZW 的存储机制理解有误,也可能是写入码表的方式赘余太严重。以后有时间改改再回来填坑~

    def get_keys(dict, value):

    # 传入字典,值,获取对应的键

    for k, v in dict.items():

    if v == value:

    return k

    def check_binary(input_data):

    # 检查文件编码,ASCII码超出255的字符替换为空格

    output_data = ''

    for word_index in range(len(input_data)):

    if ord(input_data[word_index]) >= 256:

    output_data += ' '

    else:

    output_data += input_data[word_index]

    return output_data

    def write_file(f,code_schedule,code):

    import six

    # 声明码表长度

    code_schedule_len = '0' * (18 - len(bin(len(code_schedule)))) + bin(len(code_schedule))[2:]

    f.write(six.int2byte(int(code_schedule_len[:8], 2))) # 声明码表长度 1

    f.write(six.int2byte(int(code_schedule_len[8:], 2))) # 声明码表长度 2

    # 声明符长(1 字节),以 1 字节储存字符,前255位不需要声明 字符 ==> ASCII 码

    # 文本转码 2 字节

    for letter in code:

    letter_code = '0' * (18 - len(bin(letter))) + bin(letter)[2:]

    f.write(six.int2byte(int(letter_code[:8], 2))) # 文本长度 1

    f.write(six.int2byte(int(letter_code[8:], 2))) # 文本长度 2

    # 使用 -1 作为分隔符

    f.write(six.int2byte(ord('-')))

    f.write(six.int2byte(ord('1')))

    def compress(file_name):

    import os

    # 1.打开文件

    f = open(file_name, 'r')

    # 2.读取信息

    file_data = check_binary(f.read())

    f.close()

    # 3.创建压缩文件

    f = open(os.path.splitext(file_name)[0] + '.qlh', 'wb')

    # 创建初始码表,储存 0-255 ASCII 码表信息

    code_schedule = dict([[chr(i), i] for i in range(256)])

    code_size = 255

    code = []

    prefix = '' # 前缀词

    for postfix in file_data:

    vocabulary = prefix + postfix # 前缀+后缀构成匹配词组

    if vocabulary in code_schedule.keys():

    prefix = vocabulary

    else:

    if len(code_schedule) <= 65535:

    code.append(code_schedule[prefix])

    code_size += 1

    code_schedule[vocabulary] = code_size

    prefix = postfix

    else:

    write_file(f, code_schedule, code)

    # 初始化

    code_schedule = dict([[chr(i), i] for i in range(256)])

    code_size = 255

    code = []

    prefix = ''

    if code != []:

    write_file(f, code_schedule, code)

    # 关闭文件

    f.flush()

    f.close()

    print('压缩完成', file_name, '>>', os.path.splitext(file_name)[0] + '.qlh')

    本人第 1 篇技术博客,仅是分享个人学习心得及相关代码。在算法实现上,如果有更好的优化方式,欢迎同我联系探讨。

    作者:张柳彬

    如有疑问,请联系QQ:965579168

    转载请声明出处

    展开全文
  • 1 哈夫曼编码综述在计算机科学和信息论,哈夫曼编码是一种特殊类型的最优前缀码(prefix code),通常用于无损数据压缩(英文文本,更一般地说 ASCII 码位于 0-255 位的文本)。哈夫曼编码是一种变长编码,相比使用定长...

    0d956078f2dfc7d5d99a3bb06ddc4487.png

    1 哈夫曼编码综述

    在计算机科学和信息论,哈夫曼编码是一种特殊类型的最优前缀码(prefix code),通常用于无损数据压缩(英文文本,更一般地说 ASCII 码位于 0-255 位的文本)。

    • 哈夫曼编码是一种变长编码,相比使用定长的 ASCII 码,哈夫曼编码可以节省很多的空间 (试想如果一篇文章中全为同一种字符,对应的哈夫曼编码为 "0" ,那么原先表达 1 个字符的 1 字节就能用来表示 8 个字符)。
    • 哈夫曼压缩对频数最高的字符赋予较短的编码,实现压缩效率最大化
    • 哈夫曼编码以二叉树为基础实现的,二叉树到每一个叶子节点的路径是唯一的,对应的编码也就唯一。
    • 哈夫曼编码的前缀码唯一,从图 1 中可以看出,各编码的前缀码都是唯一的,这就保证了在字符表确定下,不断搜索一定可以定位到对应的字符。
      • 图 1 示例文本长度为 17,占用空间17字节。使用哈夫曼编码进行转码,对应的转码文本为:10110110001000111111111001000000000 ,长度为 35,按照 8 位一字节进行切割后,正文文本 就变成了 5 字节 (不足 8 位需要补 0)
      • 对转码文本进行还原时,读取 1 位字符,对其后的字符搜索。如读取 "1" 后接着读取 "0" 变成了 "10" ,编码表中没有 "10",则继续向后读取 "101",此时码表中有 "101"项,对文本进行还原得到 "a",继续向后搜索,直到匹配完全文。

    e1052c09dba1da7075107a9d22e1d83d.png
    图 1 哈夫曼树及编码示例

    2 哈夫曼压缩及解压基本原理

    哈夫曼压缩基本思想是将二进制代码分配给字符,用于减少编码这些符号的字符串比特数(如上图 1 中,原先表达一个字符 "e",需要1字节数据 "01100101",而在哈夫曼编码中,只需要1位数据 "0" 即可表达)。构造过程可以参考图 1 ,简书中较好的资料详细介绍了算法原理(但是代码运行不了,报错...)。

    算法的主要过程分为:构造哈夫曼编码表、转码压缩、转码解压。

    压缩与解压中,数据根据哈夫曼编码表进行转换,因此写入编码表信息是必须的。此外,字节位数不足 8 位时,需要补充 "0" 达到 8 位,而补 "0" 的情况又对解码信息有影响,还需要在文件中声明补 "0"情况。每一步的大致过程如下所示(在本文第 4 部分结合代码有更详细的示例):

    • 构造哈夫曼编码表

    Step1 遍历需要处理的字符串,得到每个字符出现的次数(频数)

    Step2 将频数最低的两位字符作为叶子节点,左子树频数大于右子树,构造分支节点,同时将分支节点作为新的字符,频数即为子叶频数之和,进行重新排序(如图 1 中,将 "bd" 作为新字符,进行重新排序)

    Step3 重复 Step1 和 Step2,直到所有字符编码完成

    Step4 从树的顶端开始编码,左子树编为 0,右子树编为 1,直到树的底端

    Step5 根据编码情况构造哈夫曼编码表

    • 转码压缩

    Step1 根据哈夫曼编码表将正文转换为 0-1 编码

    Step2 每 8 位编码进行一次切割,作为 1 个字节数据写入压缩文件

    Step3 文末不足 8 位则需要补 "0",直到刚好达到 8 位编码

    Step4 解码时避免补 "0" 干扰,需要将补 0 情况写入压缩文件中

    Step5 将码表写入压缩文件

    • 转码解压

    Step1 根据补 0 情况,删减文本

    Step2 读取哈夫曼编码表,作为转码对照表

    Step3 读取正文文本,与转码对照表进行比对,还原信息

    3 分析及扩展应用

    3.1 为什么哈夫曼编码是最优的?

    参考:维基百科香农源编码定理

    https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theoremen.wikipedia.org

    (其实也很像运筹学课本上提到的最优带权连接图,但是证明实在是太长了。。。)

    也可以这样考虑:对频数最多的字符赋予最少的字符长度,依次类推。

    3.2 其他压缩算法的"后端"

    哈夫曼压缩作为数据流压缩的“先驱者”,由于哈夫曼编码简单、高速且无数据损失,常常被用于其他压缩算法的“后端”。如DEFLATE和多媒体编码器(如图像的JPEG,音频的MP3)都有自己的压缩算法,但都应用到了这种前缀码的思想。尽管大多数无损压缩算法都使用预定义的可变长度(如 LZW 算法)而不是使用哈夫曼算法,但这写算法也通常被称为 "Huffman codes"。

    3.3 层次聚类算法聚类树构造

    哈夫曼树构造过程与层次聚类算法思想也极其相似,将权值改为“样本距离”,并重新定义节点权值更新函数,即可得到层次聚类的聚类树构造。下图中展示了笔者使用哈夫曼树实现的层次聚类,并进行可视化的效果。

    80c13d5cac1c638f9f1b875ed62df196.png
    图 2 经典层次聚类(Hierarchical Clustering)算法

    e1bd8663d0f885ce7fe5e08a55afb257.png
    图 3 使用哈夫曼树构造的聚类树(试验数据为17年国赛建模B题数据,使用欧式距离度量权值)

    3.4 数据加密

    哈夫曼压缩中,最重要的哈夫曼编码表是能否解读数据关键。在压缩的时候,将码表与文本分离(或者打乱码表的表头、表文顺序,自定义一定规则进行匹配),可以实现数据加密。同时,若将码表的表头与表文、表文长度进行分别处理,则可以实现多端口数据加密验证。

    3.5 流式数据压缩

    哈夫曼编码可以认为是基于统计的压缩算法,统计过程是算法的核心,而流式数据随着文本不断扩展,权值可能发生变化,此时使用哈夫曼压缩不一定能取得很好的压缩效果,但在特定场景下,通过预先设定字符编码,也能取得较好的情况。如据统计,在英文小说中,文本使用 "e"、"t"、"a" 等字符的频数较高,则可以对这些字符进行预先编码,再根据各文本差异进行后续编码扩充。当然,其他编码算法如 LZW 编码、RLE 算法也给出了更好的实现方案,这些算法压缩效果好、速度快,但是性能不够好。

    3.6 压缩汉字构思

    汉字在 GB2312 编码存储占 2 字节,而英文文本、数字占 1 字节,因此可以考虑在 GB2312 编码下构造汉字映射表,实现汉字压缩。(只是构思,写不写的出来就不知道咯~)

    4 python3逐步实现哈夫曼压缩(附注 2 提供测试数据及完整源码)

    4.1 说明

    学习哈夫曼压缩过程中参考了许多资料,其中不少简书、CSDN 博文都给出了很漂亮的代码示例,但是也存在一些问题,如 python2 代码、结构混乱、使用类思想不便于新手理解(python的编程风格不同于JAVA)、没有给出压缩解压细节等。因此,本文以算法思想为蓝本逐步用代码进行实现,并在本文对每个部分的功能进行了详细说明。部分代码语句可能较为啰嗦,结构也不完美,但是可读性较强,便于理解。(完整代码见附注 2)

    使用的编程语言:python3.6.4 (Anaconda3)

    使用的编辑器:pycharm

    使用的模块:os、six、tkinter

    • os 模块:使用了 os 模块的 path.splitext 函数,用于分割文件名与扩展名。如"test.txt",分割为 ('test', '.txt'),实现重写扩展名功能
    • six 模块:使用了 six 模块的 int2byte 函数,用于将数字转化为字节存入文件
    • tkinter 模块:选用,使用了 tkinter 模块的 filedialog.askopenfilenames 函数,用于实现弹窗打开文件的功能 (如图4)

    bd060f844d61dea7d9b807293ce1fe33.png
    图 4 tkinter.filedialog.askopenfilenames 弹窗打开文件

    4.2 导入模块

    import os
    import six
    import tkinter

    4.3 打开文件

    f = open(file_name, 'r')    # file_name为文件名
    file_data = check_binary(f.read())
    f.close()

    由于本文实现的是英文文本的压缩,此处仅考虑 ASCII 码在 [0, 255] 范围内的字符。自定义函数 check_binary 进行字符检查替换。

    • check_binary:用于检查文件字符 ASCII 编码是否在 [0, 255] 范围,不在此范围则替换为空格
    def check_binary(input_data):
        # 检查文件编码,ASCII码超出255的字符替换为空格
        output_data = ''
        for word_index in range(len(input_data)):
            if ord(input_data[word_index]) >= 256:
                output_data += ' '
            else:
                output_data += input_data[word_index]
        return output_data

    4.4 统计各字符出现的频数

    统计各字符出现的频数,并保存在字典 char_freq 中

    • setdefault(word, 0):创建键为 word,,初始值为 0 的对象,若字典中已存在此键,则不产生影响。
    char_freq = {}
    for word in file_data:
        char_freq.setdefault(word, 0)
        char_freq[word] += 1

    4.5 编码哈夫曼树

    编码哈夫曼树两个重要的过程:更新字符频数排序,更新字符编码,对这两个过程分别自定义函数 sort_tuple 和 get_coding_schedule

    • sort_tuple(dist):传入一个字典 dist ,按照值大小顺序进行排序,并返回元组
    def sort_tuple(dist):
        # 传入字典,按照键大小顺序重排序
        return sorted(dist.items(), key=lambda x: x[1], reverse=True)
    • get_coding_schedule(end1, end2, sort_list, code_schedule):传入排序表中频数最低的两位字符的 (键, 值) 元组、剔除传入的 end1, end2 后的字符排序列表、哈夫曼编码表,返回更新后的哈夫曼编码表
      • 哈夫曼表构造过程解析
        • 传入 end1 作为右子树,end2 作为左子树
        • 分别判断 end1 和 end2 的字符长度,如果长度为 1 说明该字符是叶子节点,否则说明该字符是分支节点
          • 如果 end1 是叶子节点,则设置编码值为 "1",如果 end2 是叶子节点,则设置编码值为 "0"
          • 如果 end1 是分支节点,则根据分支节点的字符串进行遍历,为每一个子叶编码值都添加前缀字符 "1",如果 end2 是分支节点,则根据分支节点的字符串进行遍历,为每一个子叶编码值都添加前缀字符 "0"
        • 在 sort_list 中添加由 end1 和 end2 构成的分支节点信息,结点信息包含所有子叶字符,所有子叶累计频数
    def get_coding_schedule(end1, end2, sort_list, code_schedule):
        # 传入 末端2位字符组 频数 序列列表(剔除末端字符) 哈夫曼编码表
        if len(end1[0]) == 1:
            code_schedule.setdefault(end1[0], '1')
        else:
            for k in end1[0]:
                code_schedule[k] = '1' + code_schedule[k]
        if len(end2[0]) == 1:
            code_schedule.setdefault(end2[0], '0')
        else:
            for k in end2[0]:
                code_schedule[k] = '0' + code_schedule[k]
        sort_list.append((end2[0] + end1[0], end1[1] + end2[1]))
        return code_schedule

    通过调用上面两个函数,完成哈夫曼编码的构造

    # 初始 字符--频数 列表
    sort_list = sort_tuple(char_freq)
    # 初始化哈夫曼编码表
    code_schedule = {}
    # 不断重排序,更新哈夫曼编码表及节点信息
    for i in range(len(sort_list) - 1):
        sort_list = sort_tuple(dict(sort_list))
        code_schedule = get_coding_schedule(sort_list.pop(), sort_list.pop(), sort_list, code_schedule)

    2cb12e92f05551b49176413c57054b47.png
    图 5 哈夫曼压缩及编码示例

    以图 5 为例,展示哈夫曼树及哈夫曼编码的构造过程:

    • 初次排序:[('e', 9), ('c', 4), ('a', 2), ('b', 2), ('d', 1)]
    • 传入 end1 = ('d', 1), end2 = ('b', 2), sort_list = [('e', 9), ('c', 4), ('a', 2)], code_schedule = {}
    • end1 和 end2 的字符长度都为 1 ,分别设置编码 "1", "0"
    • 得到 sort_list = [('e', 9), ('c', 4), ('a', 2), ('bd', 3)], code_schedule = {'d': '1', 'b': '0'}
    • 第二次排序:[('e', 9), ('c', 4), ('bd', 3), ('a', 2)]
    • 传入 end1 = ('a', 2), end2 = ('bd', 3), sort_list = [('e', 9), ('c', 4)], code_schedule = {'d': '1', 'b': '0'}
    • end1 字符长度为 1,设置编码 "1";end2 字符长度为 2 ,取 end2 的字符 "bd" ,对子叶的字符编码分别加上前缀字符 "0"
    • 得到 sort_list = [('e', 9), ('c', 4), ('bda', 5)], code_schedule = {'d': '01', 'b': '00', 'a': '1'}
    • 第三次排序:[('e', 9), ('bda', 5), ('c', 4)]
    • 传入 end1 = ('c', 4), end2 = ('bda', 5), sort_list = [('e', 9)], code_schedule = {'d': '01', 'b': '00', 'a': '1'}
    • end1 字符长度为 1,设置编码 "1";end2 字符长度为 3,取 end2 的字符 "bda",对子叶的字符编码分别加上前缀字符 "0"
    • 得到 sort_list = [('e', 9), ('bdac', 9)], code_schedule = {'d': '001', 'b': '000', 'a': '01', 'c': '1'}
    • 第四次排序:[('e', 9), ('bdac', 9)]
    • 传入 end1 = ('bdac', 9), end2 = ('e', 9), sort_list = [], code_schedule = {'d': '001', 'b': '000', 'a': '01', 'c': '1'}
    • end1 字符长度为 4,取 end1 的字符 "bdac",对子叶的字符编码分别加上前缀字符 "1";end2 字符长度为 1,设置编码 "0"
    • 得到 sort_list = [('ebdac', 18)],code_schedule = {'d': '1001', 'b': '1000', 'a': '101', 'c': '11', 'e': '0'}

    通过上面四次重复过程即完成了哈夫曼树及哈夫曼编码的构造

    4.6 文本信息转哈夫曼编码

    在 4.5 中构造了哈夫曼编码表,接下来要做的工作就是对照哈夫曼编码表,将文本信息转码并保存。要写入作为正文的信息有哈夫曼编码表、正文编码、补 0 。其中哈夫曼编码表只需要写入表文信息,正文部分需要进行转码处理,补 0 根据哈夫曼编码表表文信息+正文编码信息长度确定。如图 5 案例中,哈夫曼编码表表文长度 14,正文转码长度35,需要补 7 个 0 。正文信息存储结构如图 6 所示:

    70d2f35130426e7a5ac14e1c0969509e.png
    图 6 待写入的文本信息
    # 文本信息转哈夫曼码
    # 哈夫曼 0-1 编码转码 + 正文文本
    code = ''.join(list(code_schedule.values()))
    for word in file_data:
        code += code_schedule[word]
    # 不足 8 位补 0,记录在 code_sup 中
    code_sup = 8 - len(code) % 8
    code += code_sup * '0'

    4.7 创建压缩文件并写入信息

    python 默认的存储数据以字符串形式存入,若要进行字节文件写入,需要使用二进制文件格式打开,还需要使用 six 模块下的 int2byte 函数对信息进行转码。

    依次将:补 0 情况,码表总长度,每一个字符的表文长度,表头字符写入文件,作为文件头,用于声明信息。随后再将 4.6 中正文文本信息写入文件。

    3236d7c74fb86c3c9781319bf7ff1ad1.png
    图 6 待写入文件头信息
    # 1.创建压缩文件
    f = open(os.path.splitext(file_name)[0] + '.qlh', 'wb')
    # 2.写入补 0 情况
    f.write(six.int2byte(code_sup))
    # 3.写入哈夫曼编码表(总长度+每一个编码长度+每一个编码对应的字符+转码信息)
    # 3.1 码表总长度(字符个数,与指针读取定位有关,分割码表与正文)
    f.write(six.int2byte(len(code_schedule)))
    # 3.2 储存每一个哈夫曼编码的位长
    for v in code_schedule.values():
        f.write(six.int2byte(len(v)))
    # 3.3 储存每一个哈夫曼编码配对字符        字符 ==> ASCII 码
    for k in code_schedule.keys():
        f.write(six.int2byte(ord(k)))
    # 3.4 以 8 为长度单位,将 0-1 字符转为对应的十进制数,映射为 ASCII 符号,写入正文文本
    for i in range(len(code) // 8):
        f.write(six.int2byte(int(code[8 * i:8 + 8 * i], 2)))
    # 4.关闭文件
    f.flush()
    f.close()
    print('压缩完成', file_name, '>>', os.path.splitext(file_name)[0] + '.qlh')

    4.8 实验示例

    本次使用英文 txt 文件 5 部作品进行实验测试:

    21af1dc3f86bef2cab85ee0e8f5da209.png
    图 7 实验原文件,作品分别为:《哈利波特》4-6,《共产党宣言》,《一千零一夜》

    压缩效果:

    6df066fc8b6881f2d75c41e3121a13fc.png
    图 8 压缩效果对比

    可以看到,压缩效果显著。

    4.9 解压的实现

    解压是压缩的逆过程,怎么写入的就怎么读取。按照写入的过程分别读取以下信息:

    • 补 0 情况,用于删除正文信息中末尾补充的 "0"
    • 码表总长度(设为
      )
    • 码表表文长度:表文长度以 1 字节形式存储在文件中,根据码表总长度向后截取
      个字节即得到所有码表表文长度
    • 码表表头:码表表文长度之后就是码表表文(编码对应的原字符),也是向后继续截取
      个字节,每一个字节对应的 ASCII 码都对应着一个字符,将其转译作为哈夫曼编码表的表头信息
    • 码表表文:根据表文长度,在码表表头之后不断搜索截取表文长度指示的位数,获取到每个表头对应的表文,写入哈夫曼编码表。
    • 正文信息:所有表文读取结束后即复原了哈夫曼编码表,根据补 0 情况删除末尾的字符,剩余的文本即为原始文本信息。对于原始文本信息,每次对编码向后搜索、拼接,并与哈夫曼编码表进行匹配,若编码存在哈夫曼编码表表文中,则使用自定义函数 get_keys 进行转译得到对应的表头
    def get_keys(dict, value):
        # 传入字典,值,获取对应的键
        for k, v in dict.items():
            if v == value:
                return k

    解码过程不涉及太多技术性问题,此处直接给出所有的代码及简要注释,按照写入方式逆向操作就能还原文本。

    import os
    # 1.打开文件
    f = open(file_name, 'rb')
    # 2.读取信息
    file_data = f.read()
    f.close()
    
    # 3.分割信息
    # 3.1 获取补 0 位数
    code_sup = file_data[0]
    # 3.2 获取码表长度
    code_schedule_length = file_data[1]
    # 3.3 指针跳过 补0+码长+码符
    pointer = 2 * code_schedule_length + 2
    # 3.4 获取码表中每一个编码的长度
    code_word_len = [file_data[2 + i] for i in range(code_schedule_length)]
    # 3.5 编码表中字符长度总和,用于切割码表与正文
    sum_code_word_len = sum(code_word_len) // 8 + 1 if sum(code_word_len) % 8 != 0 else sum(code_word_len) // 8
    
    # 4.还原码表
    # 4.1 码表转译
    code_schedule_msg = ''
    for i in range(sum_code_word_len):
        code_schedule_msg += '0' * (10 - len(bin(file_data[pointer + i]))) + bin(file_data[pointer + i])[2:]
    # 4.2 初始化指针
    pointer = 0
    # 4.3 创建码表
    code_schedule = {}
    for i in range(code_schedule_length):
        code_word = chr(file_data[code_schedule_length + 2 + i])  # 码符
        code_schedule[code_word] = code_schedule_msg[pointer:pointer + code_word_len[i]]  # 码符码文匹配,还原码表
        pointer += code_word_len[i]
    
    # 5.提取正文
    code = code_schedule_msg[pointer:]
    pointer = 2 * code_schedule_length + 2 + sum_code_word_len
    for number in file_data[pointer:]:
        code += '0' * (10 - len(bin(number))) + bin(number)[2:]
    # 删去补0
    code = code[:-code_sup]
    
    # 6.文本转译
    pointer = 0  # 指针归零
    # 初始化文本
    letter = ''
    # 限制最大搜索长度,提高效率
    max_length = max([len(list(code_schedule.values())[i]) for i in range(len(code_schedule.values()))])
    while pointer != len(code):
        for i in range(max_length):
            if code[pointer:pointer + i + 1] in code_schedule.values():
                letter += get_keys(code_schedule, code[pointer:pointer + i + 1])
                pointer += i + 1
                break
    
    # 7.创建解压文件
    f = open(os.path.splitext(file_name)[0] + '.txt', 'w+')
    f.write(letter)
    print('解压完成', file_name, '>>', os.path.splitext(file_name)[0] + '.txt')

    将上文中的压缩函数命名为 compress,解压函数命名为 decompress,并引入 tkinter 模块中的 filedialog.askopenfilenames 函数,即可实现弹窗点击文件并压缩、解压的功能。此外,通过自定义函数 compress_all、decompress_all、get_request 函数,进一步实现批量文件压缩解压功能。

    def compress_all(file_names):
        # 批量压缩文件
        for file_name in file_names:
            compress(file_name)
    
    def decompress_all(file_names):
        # 批量解压文件
        for file_name in file_names:
            decompress(file_name)
    
    class Inputerror(Exception):
        # 自定义异常
        def __init__(self, messages):
            super().__init__(messages)
    
    def get_request():
        file_name = tkinter.filedialog.askopenfilenames()
        ask = input('Compress or Decompress ? (C/D)').lower()
        if ask == 'd':
            decompress_all(file_name)  # 解压文件
        elif ask == 'c':
            compress_all(file_name)  # 压缩文件
        else:
            raise Inputerror("accept unknown command ,routine haven't started doing anything, please run it again")

    写在运行当前文件中执行的部分

    if __name__ == '__main__':
        import tkinter.filedialog
    
        get_request()
        while input('Continue ? (Y/N)').lower() == 'y':
            get_request()

    4.10 实验示例

    继续对 4.8 中的文件进行解压。先前提到,本文中的程序是对 ASCII 范围在 [0,255] 的字符进行压缩,并对超过范围的字符进行空格替换处理,因此文件中出现的少量数据损失属于正常现象。(哈利波特 5 文件中没有超过范围的字符,因此实现了完整的数据还原)

    9bf128db4ae3d6b996a184dec11f9a0a.png
    图 9 压缩前与解压后文件对比

    5 附注 1:罗塞塔代码提供的哈夫曼编码树构造

    from heapq import heappush, heappop, heapify
    from collections import defaultdict
     
    def encode(symb2freq):
        """Huffman encode the given dict mapping symbols to weights"""
        heap = [[wt, [sym, ""]] for sym, wt in symb2freq.items()]
        heapify(heap)
        while len(heap) > 1:
            lo = heappop(heap)
            hi = heappop(heap)
            for pair in lo[1:]:
                pair[1] = '0' + pair[1]
            for pair in hi[1:]:
                pair[1] = '1' + pair[1]
            heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
        return sorted(heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
     
    txt = "this is an example for huffman encoding"
    symb2freq = defaultdict(int)
    for ch in txt:
        symb2freq[ch] += 1
    huff = encode(symb2freq)
    print ("SymboltWeighttHuffman Code")
    for p in huff:
        print("%st%st%s" % (p[0], symb2freq[p[0]], p[1]))

    测试文本:this is an example for huffman encoding

    输出结果:

    6 附注 2:实验数据及程序

    附件为百度网盘链接。其中,对 "data/实验数据" 中的文件进行压缩可以得到 "data/压缩文件" 中的文件,对 "data/压缩文件" 中的文件进行解压可以得到 "data/解压效果" 中的文件

    https://pan.baidu.com/s/1dgIAnIS-hW4QNFUWlo6YJQpan.baidu.com

    7 附注 3:LZW 算法简单实现

    LZW 对流式数据具有较好的压缩性能,基本思想为进一步对连续字符进行压缩替换(如 "abcd832abcd841abcd818" ,若用 "e" 代替 "abcd8" ,则原文本可以转化为 "e32e41e18",从而实现压缩),下面是压缩算法代码的简单实现。在上述测试数据中压缩效果表现不理想(重复文本过少),删去 write_file 部分(即不初始化码表)则性能极优,但是只能输出配对字符。这里产生的问题可能是我对 LZW 的存储机制理解有误,也可能是写入码表的方式赘余太严重。以后有时间改改再回来填坑~

    def get_keys(dict, value):
        # 传入字典,值,获取对应的键
        for k, v in dict.items():
            if v == value:
                return k
    
    def check_binary(input_data):
        # 检查文件编码,ASCII码超出255的字符替换为空格
        output_data = ''
        for word_index in range(len(input_data)):
            if ord(input_data[word_index]) >= 256:
                output_data += ' '
            else:
                output_data += input_data[word_index]
        return output_data
    
    def write_file(f,code_schedule,code):
        import six
        # 声明码表长度
        code_schedule_len = '0' * (18 - len(bin(len(code_schedule)))) + bin(len(code_schedule))[2:]
        f.write(six.int2byte(int(code_schedule_len[:8], 2)))  # 声明码表长度 1
        f.write(six.int2byte(int(code_schedule_len[8:], 2)))  # 声明码表长度 2
        # 声明符长(1 字节),以 1 字节储存字符,前255位不需要声明        字符 ==> ASCII 码
        # 文本转码 2 字节
        for letter in code:
            letter_code = '0' * (18 - len(bin(letter))) + bin(letter)[2:]
            f.write(six.int2byte(int(letter_code[:8], 2)))  # 文本长度 1
            f.write(six.int2byte(int(letter_code[8:], 2)))  # 文本长度 2
        # 使用 -1 作为分隔符
        f.write(six.int2byte(ord('-')))
        f.write(six.int2byte(ord('1')))
    
    def compress(file_name):
        import os
        # 1.打开文件
        f = open(file_name, 'r')
        # 2.读取信息
        file_data = check_binary(f.read())
        f.close()
    
        # 3.创建压缩文件
        f = open(os.path.splitext(file_name)[0] + '.qlh', 'wb')
    
        # 创建初始码表,储存 0-255 ASCII 码表信息
        code_schedule = dict([[chr(i), i] for i in range(256)])
        code_size = 255
        code = []
        prefix = '' # 前缀词
        for postfix in file_data:
            vocabulary = prefix + postfix       # 前缀+后缀构成匹配词组
            if vocabulary in code_schedule.keys():
                prefix = vocabulary
            else:
                if len(code_schedule) <= 65535:
                    code.append(code_schedule[prefix])
                    code_size += 1
                    code_schedule[vocabulary] = code_size
                    prefix = postfix
                else:
                    write_file(f, code_schedule, code)
                    # 初始化
                    code_schedule = dict([[chr(i), i] for i in range(256)])
                    code_size = 255
                    code = []
                    prefix = ''
        if code != []:
            write_file(f, code_schedule, code)
        # 关闭文件
        f.flush()
        f.close()
        print('压缩完成', file_name, '>>', os.path.splitext(file_name)[0] + '.qlh')

    本人第 1 篇技术博客,仅是分享个人学习心得及相关代码。在算法实现上,如果有更好的优化方式,欢迎同我联系探讨。

    作者:张柳彬

    如有疑问,请联系QQ:965579168

    转载请声明出处

    展开全文
  • 一、哈夫曼压缩原理 哈夫曼压缩是一种无损的压缩算法,在压缩过程中不会损失信息熵,因此常用哈夫曼算法去压缩一些重要的文件资料。 哈夫曼压缩是通过采用特定长度的位序列去替代原来的个体符号(如字节)。对于...

    本文主要介绍如何实现哈夫曼压缩以及提高哈夫曼压缩过程的读写速率,对于哈夫曼树的概念及其构造则没有介绍,感兴趣的朋友可以先百度一下了解相关知识。

    一、哈夫曼压缩原理

    哈夫曼压缩是一种无损的压缩算法,在压缩过程中不会损失信息熵,因此常用哈夫曼算法去压缩一些重要的文件资料。

    哈夫曼压缩是通过采用特定长度的位序列去替代原来的个体符号(如字节)。对于一些高频率出现的字节,使用短字节表示,而对于一些低频率出现的字节,则采用较长的位序列来代替,这从而降低整个文本的位序列长度,达到压缩目的。

    二、哈夫曼压缩与解压缩过程

    要实现哈夫曼压缩,我们需要做如下工作:

    1、读取文本;

    2、统计文本中各字节出现的次数;

    3、根据第二步统计出来结果构造哈夫曼树;

    4、生成哈夫曼编码;

    5、将文件转换为哈夫曼编码格式的字节文件;

    6、写入哈夫曼编码。

    哈夫曼解压缩是压缩的逆过程,其主要步骤如下:

    1、读取压缩文件;

    2、还原哈夫曼编码;

    3、根据哈夫曼编码还原文件。

    三、哈夫曼压缩

    压缩思路:

    1、int [ ] byteCount和String [ ] charCode

    创建两个数组分别保存各字节出现的次数和哈夫曼编码,由于本文压缩的是英文文本,只需要用基础ASCII码(0-127),所以数组长度均设为128位,利用数组索引来存储对应的字节,索引位置的值存储相应信息;

    2、采用优先队列来构建哈夫曼树,通过调用poll( )方法可快速构建哈夫曼树,需要注意的是,这里需要加入一个比较器,重写compare()方法,采用按字节出现次数排序(从小到大);

    3、读写数据时采用字节缓冲流加字节数组的方法提高读写效率,减少对磁盘文件的操作;

    4、本文将编码文件与文件编码合并后一起生成字节文件后,再一次性写入压缩文件;

    5、生成字节文件时,最后一个字节不足8位时,加0补齐8位生成字节写入;

    6、压缩文件格式:

            本文压缩文件分为三段,分别为: 

            a.各字节编码长度( 0-127);

            b.末位补0数(128);

            c.字节编码文件(含编码字节);

    7、整型数据转换为字节方法:new Integer( int value).byteValue

    package com.liao.Huffman0830v1;
    
    import java.io.BufferedInputStream;
    import java.io.BufferedOutputStream;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.io.IOException;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class HufTree {
    	private static final int LEN = 128;
    	private int[] byteCount = new int[LEN];// 统计各字节出现次数
    	private String[] charCode = new String[LEN];// 记录各字节哈夫曼编码
    	private PriorityQueue<hufNode> nodeQueue = new PriorityQueue<>(LEN, new Comparator<hufNode>() {
    		@Override
    		public int compare(hufNode o1, hufNode o2) {
    			return o1.count - o2.count;// 按次数排序
    		}
    	});
    
    	// 成员内部类
    	private static class hufNode {
    		private hufNode lchild;// 左分支
    		private hufNode rchild;// 右分支
    		private String str;// 记录字符
    		private int count;// 统计次数
    		// 构造方法
    
    		public hufNode(String str, int count) {
    			super();
    			this.str = str;
    			this.count = count;
    		}
    	}
    
    	// 主函数
    	public static void main(String[] args) {
    		File file = new File("file\\01.txt");
    		File file2 = new File("file\\压缩文件.txt");
    		new HufTree().compress(file, file2);// 压缩文件
    		System.out.println("原文件大小:" + file.length() + "b");
    		System.out.println("压缩文件大小:" + file2.length() + "b");
    	}
    
    	// 压缩文件
    	private void compress(File file, File file2) {
    		byte[] bs = readFile(file);// 读取文件
    		countChar(bs);// 统计词频
    		hufNode root = createTree();// 创建哈夫曼树
    		generateCode(root, "");// 生成哈夫曼编码
    		printCode();// 打印哈夫曼编码
    		writeFile(bs, file2);// 写入压缩文件
    	}
    
    	// 将文件转换为字节数组保存
    	private byte[] readFile(File file) {
    		byte[] bs = new byte[(int) file.length()];// 创建字节数组
    		BufferedInputStream bis = null;// 声明字节缓冲流
    		try {
    			bis = new BufferedInputStream(new FileInputStream(file));
    			bis.read(bs);// 将文件读取到字节数组中
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			try {
    				if (bis != null)
    					bis.close();// 关闭输入流
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    		return bs;
    	}
    
    	// 统计词频
    	private void countChar(byte[] bs) {
    		for (int i = 0, length = bs.length; i < length; i++) {
    			byteCount[bs[i]]++;
    		}
    	}
    
    	// 创建哈夫曼树
    	private hufNode createTree() {
    		for (int i = 0; i < LEN; i++) {
    			if (byteCount[i] != 0) {// 使用优先队列保存
    				nodeQueue.add(new hufNode((char) i + "", byteCount[i]));
    			}
    		}
    		// 构建哈夫曼树
    		while (nodeQueue.size() > 1) {
    			hufNode min1 = nodeQueue.poll();// 获取并移除队列头元素
    			hufNode min2 = nodeQueue.poll();
    			hufNode result = new hufNode(min1.str + min2.str, min1.count + min2.count);
    			result.lchild = min1;
    			result.rchild = min2;
    			nodeQueue.add(result);// 加入左节点
    		}
    		return nodeQueue.peek();// 返回根节点
    	}
    
    	// 生成哈夫曼编码
    	private void generateCode(hufNode root, String s) {
    		// 叶子节点
    		if (root.lchild == null && root.rchild == null) {
    			// 保存至编码数组对应位置
    			charCode[(int) root.str.charAt(0)] = s;
    		}
    		if (root.lchild != null) {// 左边加0
    			generateCode(root.lchild, s + "0");
    		}
    		if (root.rchild != null) {// 右边加1
    			generateCode(root.rchild, s + "1");
    		}
    	}
    
    	// 写入压缩文件 :1、各字节编码长度 2、各字节编码 3、编码后的文件
    	private void writeFile(byte[] bs, File file2) {
    		BufferedOutputStream bos = null;// 声明字符缓冲流
    		try {
    			// 创建字符缓冲流
    			bos = new BufferedOutputStream(new FileOutputStream(file2));
    			// 写入各字节编码长度
    			String binaryCode = writeCodeLength(file2, bos);
    			// 字节数组文件转码成二进制文件
    			String binaryFile = transFile(bs);
    			// 合并二进制编码及文件
    			String codeAndFile = binaryCode + binaryFile;
    			// 生成字节并写入合并后二进制文件
    			generateFile(bos, codeAndFile);
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			try {
    				if (bos != null)
    					bos.close();// 关闭输入流
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    	}
    
    	// 写入各字节编码长度
    	private String writeCodeLength(File file2, BufferedOutputStream bos) throws IOException {
    		StringBuilder sb = new StringBuilder();// 创建字符缓冲流
    		for (int i = 0; i < LEN; i++) {
    			if (charCode[i] == null) {
    				bos.write(0);
    			} else {
    				sb.append(charCode[i]);// 存储哈夫曼编码
    				bos.write(charCode[i].length());
    			}
    		}
    		return sb.toString();// 返回各字节哈夫曼编码
    	}
    
    	// 文件转码
    	private String transFile(byte[] bs) {
    		StringBuilder sb = new StringBuilder();
    		for (int i = 0, length = bs.length; i < length; i++) {
    			sb.append(charCode[bs[i]]);
    		}
    		return sb.toString();
    	}
    
    	// 生成字节文件
    	private void generateFile(BufferedOutputStream bos, String codeAndFile) throws IOException {
    		int lastZero = 8 - codeAndFile.length() % 8;// 补0数
    		int len = codeAndFile.length() / 8 + 1;// 取商+1
    		if (lastZero != 8) {// 余数不为0,则补加1位
    			len = len + 1;
    			for (int i = 0; i < lastZero; i++) {
    				codeAndFile += "0";// 加0补齐8位
    			}
    		}
    		// 创建字符数组,保存字节
    		byte[] bv = new byte[len];
    		bv[0] = new Integer(lastZero).byteValue();
    		for (int i = 1; i < len; i++) {
    			// 先将8位01字符串二进制数据转换为十进制整型数据,再转为一个byte
    			byte bytes = new Integer(changeString(codeAndFile.substring(0, 8))).byteValue();
    			bv[i] = bytes;// 加入到数组中
    			codeAndFile = codeAndFile.substring(8);// 去除前8个字节
    		}
    		// 写入文件
    		bos.write(bv);
    	}
    
    	// 8位01字符串转换为十进制整型数据
    	private int changeString(String str) {
    		return (int) (str.charAt(0) - 48) * 128 + (str.charAt(1) - 48) * 64 + (str.charAt(2) - 48) * 32
    				+ (str.charAt(3) - 48) * 16 + (str.charAt(4) - 48) * 8 + (str.charAt(5) - 48) * 4
    				+ (str.charAt(6) - 48) * 2 + (str.charAt(7) - 48);
    	}
    
    	// 打印编码
    	private void printCode() {
    		for (int i = 0; i < LEN; i++) {
    			if (charCode[i] != null) {
    				System.out.println("(" + i + "," + (char) i + "," + byteCount[i] + "," + charCode[i] + ","
    						+ charCode[i].length() + ")");
    			}
    		}
    	}
    }

    四、哈夫曼解压缩

    解压缩思路:

    1、利用String类的substring()方法和Arrays类的copyOfRange方法对字符串进行复制及截取;

    2、利用BigInteger类的 new BigInteger(1, byte [ ]).toString(2)方法将字节数组转换为二进制字符串形式;

    package com.liao.Huffman0830v1;
    
    import java.io.BufferedInputStream;
    import java.io.BufferedOutputStream;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.io.IOException;
    import java.math.BigInteger;
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Decompress {
    	private final static int LEN = 128;// 编码字节个数
    	private String[] charCode = new String[LEN];
    
    	// 主函数
    	public static void main(String[] args) {
    		File file = new File("file\\压缩文件.txt");
    		File file3 = new File("file\\解压文件.txt");
    		new Decompress().decompress(file, file3);
    		System.out.println("解压前文件大小:" + file.length() + "b");
    		System.out.println("解压后文件大小:" + file3.length() + "b");
    	}
    
    	// 解压文件
    	private void decompress(File file, File file3) {
    		// 读取文件
    		byte[] bs = readFile(file);
    		// 获取各字节编码长度并返回哈夫曼编码总长度
    		int codeLengths = getCodeLength(bs);
    		// 截取记录哈夫曼编码长度部分
    		byte[] CodeLength = Arrays.copyOfRange(bs, 0, LEN);
    		// 末位补0数
    		int lastZero = bs[LEN];		
    		// 截取二进制数据部分
    		bs = Arrays.copyOfRange(bs, LEN+1, bs.length);
    		// 将字节数组转换为二进制字符串
    		String codeAndFile =processData(bs);
    		// 截取编码表部分
    		String binaryCode = codeAndFile.substring(0, codeLengths);
    		// 截取文件部分(增补0)
    		String binaryFile = codeAndFile.substring(codeLengths, codeAndFile.length() - lastZero);
    		// 还原编码表
    		restoreCode(binaryCode, CodeLength);
    		// 将二进制文件转换为字节数组
    		byte[] byteArray = restoreFile(binaryFile);
    		// 写入文件
    		writeFile(file3, byteArray);
    	}
    
    	// 将文件转换为字节数组保存
    	private byte[] readFile(File file) {
    		byte[] bs = new byte[(int) file.length()];// 创建字节数组
    		BufferedInputStream bis = null;// 声明字节缓冲流
    		try {
    			bis = new BufferedInputStream(new FileInputStream(file));
    			bis.read(bs);// 将文件读取到字节数组中
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			try {
    				if (bis != null)
    					bis.close();// 关闭输入流
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    		return bs;
    	}
    
    	//数据处理(转为二进制)
    	private String processData(byte [] bs) {
    		//将数据转换为二进制
    		String codeAndFile =new BigInteger(1, bs).toString(2);
    		//判断首位是否需要补0
    		if(bs[0]>0) {
    			//转为二进制,根据位数得到补0数
    			int firstZero=8-Integer.toBinaryString(bs[0]).length();
    			for(int i=0;i<firstZero;i++) {
    				codeAndFile="0" + codeAndFile;
    			}
    		}
    		return codeAndFile;
    	}
    
    	
    	// 获取各字节编码长度并返回哈夫曼编码总长度
    	private int getCodeLength(byte[] bs) {
    		int codeLengths = 0;
    		for (int i = 0; i < LEN; i++) {
    			if (bs[i] != 0) {
    				codeLengths += bs[i];// 统计哈夫曼编码总长度
    			}
    		}
    		return codeLengths;
    	}
    
    	// 还原编码
    	private void restoreCode(String binaryCode, byte[] CodeLength) {
    		for (int i = 0; i < LEN; i++) {
    			charCode[i] = binaryCode.substring(0, CodeLength[i]);// 存储该编码
    			binaryCode = binaryCode.substring(CodeLength[i]);// 更新编码文件
    			if (CodeLength[i] != 0) {
    				System.out.println("(" + i + "," + (char) i + "," + charCode[i] + "," + CodeLength[i] + ")");
    			}
    		}
    	}
    
    	// 将二进制文件转换为字符串
    	private byte[] restoreFile(String binaryFile) {
    		ArrayList<Byte> byteList = new ArrayList<>();// 创建字节队列保存读取字节
    		for (int i = 0; i < binaryFile.length(); i++) {
    			String charcode = binaryFile.substring(0, i + 1);
    			for (int j = 0; j < LEN; j++) {
    				if (charcode.equals(charCode[j])) {
    					byteList.add(new Integer(j).byteValue());
    					// 更新参数
    					binaryFile = binaryFile.substring(i + 1);
    					i = 0;
    					break;
    				}
    			}
    		}
    		// 将字节队列数据转移至数组中
    		byte[] byteArray = new byte[byteList.size()];
    		for (int i = 0, len = byteList.size(); i < len; i++) {
    			byteArray[i] = byteList.get(i);
    		}
    		return byteArray;
    	}
    
    	// 写入文件
    	private void writeFile(File file3, byte[] byteArray) {
    		BufferedOutputStream bos = null;
    		try {
    			bos = new BufferedOutputStream(new FileOutputStream(file3));
    			bos.write(byteArray);
    			bos.flush();
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			if (bos != null) {
    				try {
    					bos.close();
    				} catch (IOException e) {
    					e.printStackTrace();
    				}
    			}
    		}
    
    	}
    }
    

    五、测试类

    通过压缩文件与解压缩文件内容对比测试压缩是否成功:

    package com.liao.Huffman0830v1;
    
    import java.io.BufferedInputStream;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.util.Arrays;
    
    public class Test {
    
    	public static void main(String[] args) throws IOException {
    		File file1 = new File("file\\001.txt");
    		File file2 = new File("file\\解压文件.txt");
    		File file3 = new File("file\\压缩文件.txt");
    		BufferedInputStream bis1 = new BufferedInputStream(new FileInputStream(file1));
    		BufferedInputStream bis2 = new BufferedInputStream(new FileInputStream(file2));
    		byte[] bs1 = new byte[(int) file1.length()];
    		byte[] bs2 = new byte[(int) file2.length()];
    		bis1.read(bs1);
    		bis2.read(bs2);
    		bis1.close();
    		bis2.close();
    		System.out.println(Arrays.equals(bs1, bs2) );
    		System.out.println("原文件大小:" + file1.length() / 1000 + "kb" + "----" + "压缩文件大小:"
    				+ file3.length() / 1000 + "kb");
    	}
    }
    

    测试结果:

    根据测试结果,可以看出文件压缩成功,压缩率约为57% 。

    六、注意事项

    1、本文只适用于英文文本压缩,对于中文文本压缩,下篇会介绍;

    2、本文基本上都是用一个字符串或字节数组保存整篇文档,然后再进行读写操作(获得更高效的读写速率),对于较大的文件(超过100Mb)可考虑将文件分成若干段再进行相关操作;

    3、为进一步提高压缩与解压缩效率,可考虑使用多线程,但须注意数据同步的问题。

    展开全文
  • 一、 哈夫曼编码开关、 二、 哈夫曼编码原理、 三、 libjpeg-turbo 函数库、 四、 libjpeg-turbo 函数库下载



    【Android 内存优化】图片文件压缩 ( Android 原生 API 提供的图片压缩功能能 | 图片质量压缩 | 图片尺寸压缩 ) 简要介绍了 图片文件压缩格式 , 以及 Android 提供的图片质量 , 尺寸压缩原生 API ;


    【Android 内存优化】Android 原生 API 图片压缩代码示例 ( PNG 格式压缩 | JPEG 格式压缩 | WEBP 格式压缩 | 动态权限申请 | Android10 存储策略 ) 主要使用了上述 Android 原生 API 压缩图片功能进行图片压缩 ;


    【Android 内存优化】Android 原生 API 图片压缩原理 ( 图片质量压缩方法 | 查找 Java 源码中的 native 方法对应的 C++ 源码 ) 中主要查找 Bitmap.java 对应的 Native 层的 C++ 类 Bitmap.cpp 源码文件 , 并分析了其动态注册 Native 方法的过程 ;


    【Android 内存优化】Android 原生 API 图片压缩原理 ( Bitmap_compress 方法解析 | Skia 二维图形库 | libjpeg 函数库 | libpng 函数库 ) 博客中分析了 Bitmap.cpp 中的 Bitmap_compress 方法 ;






    一、 哈夫曼编码开关



    上一篇博客 【Android 内存优化】Android 原生 API 图片压缩原理 ( Bitmap_compress 方法解析 | Skia 二维图形库 | libjpeg 函数库 | libpng 函数库 ) 分析到了 实际的图片压缩方法是由 Skia 图形库执行的 , Skia 图形库根据不同的压缩格式 , 选择不同的函数库进行压缩 , 如果压缩格式是 JPEG 格式 , 那么使用 libjpeg 库进行图片压缩 , 如果压缩格式是 PNG 库 , 那么使用 libpng 库进行压缩 ;


    1. 哈夫曼编码 : 在 libjpeg 中提供了图片哈夫曼编码功能 , 该功能非常消耗 CPU 性能 , 因此早期的 Android 版本禁用了该功能 , 在 7.0 之后的版本 , 此时 Android 设备上的 CPU 性能很高 , 这时才将哈夫曼编码功能打开 ; ( SkImageDecoder_libjpeg.cpp 代码参考 )


    2. 打开哈夫曼编码 : 将 jpeg_compress_struct 结构体的 optimize_coding 成员设置成 TRUE ; 作用是 通知 libjpeg-turbo 为图像计算最佳的哈夫曼编码表 , 该操作可以 提高图片压缩比例 , 代价是编码速度较慢 ;


    3. 源码参考 :

    SkImageDecoder_libjpeg.cppSkJPEGImageEncoder 类 ( SkImageEncoder 对应的 JPEG 格式图片压缩实现类 ) 中的 onEncode 方法 , 在 7.0 以后的版本 , 打开图片压缩哈夫曼编码功能 ;

    // 该类是 SkImageEncoder 的子类 , 在 Bitmap.cpp 中使用的就是
    class SkJPEGImageEncoder : public SkImageEncoder {
    protected:
        virtual bool onEncode(SkWStream* stream, const SkBitmap& bm, int quality) {
    		// ... 
    		jpeg_compress_struct    cinfo;
    		// ... 
            // 打开哈夫曼编码 
            // 通知 libjpeg-turbo 为图像计算最佳的哈夫曼编码表
            // 该功能可以提高压缩比例 , 代价是编码速度较慢
            cinfo.optimize_coding = TRUE;
            // ... 
            return true;
        }
    };
    
    

    源码位置 7.0.0/external/skia/src/images/SkImageDecoder_libjpeg.cpp ( 7.0.0 以后的源码才添加了上述功能 )





    二、 哈夫曼编码原理



    在 libjpeg 编码中 , 如果没有开启哈夫曼编码 , 采用的是定长的编码方式 , 如果打开了哈夫曼编码 , 采用的就是变长哈夫曼编码 , 可以大幅度压缩数据大小 ;


    简介 : 哈夫曼编码是字符编码 , 适用于数据文件压缩场景 , 能大幅度压缩文件大小 ;


    哈夫曼编码原理 : 每个数据的编码长度可变 , 文件中出现较多的字符使用短编码 , 出现较少的字符使用长编码 , 另外额外维护一张哈夫曼编码表 , 用于维护字符与编码的对应关系 , 总体的文件大小会降低 20% 至 90% ;





    三、 libjpeg-turbo 函数库



    使用哈夫曼编码进行图片压缩 , 能最大幅度压缩图片大小 , 但是 Android 原生编码中只有 7.0 以后的系统才打开了哈夫曼编码功能 , 目前的主流应用都要向下兼容到 android-17 平台版本 , 对应的系统版本是 Android 4.2 Jelly Bean , 这里就需要引入第三方库 libjpeg-turbo 函数库 , 进行哈夫曼编码图片压缩 , 该函数库是由 C 语言开发 , 需要在 Ubuntu 中进行交叉编译成 ARM 架构的函数库 ( 动态库 / 静态库 ) , 然后导入到 Android Studio 中使用 ;


    Android 源码中有 libjpeg-turbo 库 , 但是Java 框架中提供的 Bitmap.java 只能调用 Bitmap.cpp 中的代码 , Bitmap.cpp 中通过 Skia 2D 图形库调用 libjpeg 库 , 在该 C++ 代码中是固定的 , 开发者无法修改框架层的源码 , 因此该函数库无法被开发者调用到 ;


    NDK 交叉编译开发参考 : Android NDK 开发 专栏





    四、 libjpeg-turbo 函数库下载



    1. libjpeg-turbo 相关资源链接 :


    ① libjpeg-turbo 官方网站 : https://libjpeg-turbo.org/

    ② GitHub 地址 : libjpeg-turbo/libjpeg-turbo

    ③ libjpeg-turbo 文档 : 文档地址



    2. 下载发布版本 :


    在 Android 工程中使用该函数库 , 尽量下载发布的稳定版本 , 最好不要直接下载开发中的 DEBUG 版本 , 可能存在 BUG ;

    如下图 , 找到 release 发布版本界面 , 下载最新的发布版本 ; 或者直接点击 libjpeg-turbo/libjpeg-turbo 项目的 Release 发布版本地址 进入该界面 ;

    在这里插入图片描述


    进入 Release 界面后 , 查看到目前最新的发布版本是 2.0.5 版本 , 直接下载该源码 ; 之后需要到 Ubuntu 中进行交叉编译 ;

    在这里插入图片描述


    下载这个 Source code (tar.gz) 源码 , 到 Ubuntu 中进行交叉编译 ; ( 也可以直接点击上述连接下载 )

    在这里插入图片描述

    展开全文
  • 哈夫曼树(HuffManTree)是用来压缩数据的一种数据结构,它适合压缩数据重复率较高的情况。 文本A:123456789,这串文本重复率为0,因为每个字符都是唯一的,没有重复率而言; 文本B:111222334,这串文本重复率明显...
  • 哈夫曼压缩

    2015-08-31 11:31:34
     以前也学习过哈夫曼的算法结构,但是没有自己去写代码实现,这次再学习了一遍,更加深刻理解哈夫曼压缩原理,如何真正实现文件的压缩节省内存资源。下面梳理下我的代码和分析逻辑。  第一步是打开文件,读取...
  • 哈夫曼压缩与解压缩(java版) 一哈夫曼树以及文件压缩原理: 1.哈夫曼树 : 2.如何利用haffman编码实现文件压缩: 二主要技术点: 三实现过程: 四运行展示: 哈夫曼压缩与解压缩(java版) 一哈夫曼树以及...
  • 一、哈夫曼压缩原理 我们知道计算机中的文件采用二进制编码,为了使文件尽可能的缩短(压缩),可以对文件中每个字节出现的次数进行统计,设法让出现次数多的字节的二进制码短些,而让那些很少出现的字节的二进制码长...
  • 哈夫曼压缩软件

    2018-05-03 23:54:19
    利用哈夫曼编码的原理,编写一个压缩软件。可以压缩基本的文件,如doc、docx、excel、ppt、pptx、pdf、txt等文档,也可以压缩png、gif、jpg、mp3、mov、mp4等图片、声音、视频等文件。
  • 哈夫曼原理、画法和具体例子

    千次阅读 2020-04-08 21:03:34
    1.哈夫曼压缩原理 当各种指令出现的频度不均等时,对出现频度最高的指令用最短的位数表示,出现频度较低的则用较长的位数表示,从而使指令的平均长度缩短。 构造哈夫曼树核心思想:最小概率合并。 2.构造哈夫曼树...
  • 哈夫曼压缩与解压缩(c语言版)

    千次阅读 2019-09-29 19:18:13
    学过数据结构的同学,应该都听过哈夫曼树,和哈夫曼压缩算法,今天小编向大家讲解哈夫曼压缩与压缩的过程以及代码也算是记录一下自己所学所做的东西。 哈夫曼压缩,其实效率不是很高,一般情况下压缩率1...
  • 1、哈夫曼树 1.1哈夫曼树基本介绍 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl) 达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree) 路径:在一棵树中,从一个结点往...
  • 精讲哈夫曼压缩算法

    千次阅读 2016-01-13 09:58:35
    哈夫曼压缩算法编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的...哈夫曼压缩算法之原理 我不打算探究哈夫曼编码的所有实际的细节,但基本的原理是为每个符号找到新的二
  • 哈夫曼压缩与解压

    2017-12-09 21:24:01
    压缩过程(不对哈夫曼编码原理进行详细解释): 1:读取文件内容到StringBuffer中,并使用hashmap统计每个字符出现的频率,按字符出现的频率升序排序(并保存在文件,备解压使用)。 2:对排序结束的字符频率建立...
  • 哈夫曼压缩/解压缩(控制台,C++)

    千次阅读 2016-11-20 16:53:50
    即是如此,在初步了解哈夫曼原理之后,我只是隐隐约约的了解它的原理,在完成它的过程之中,依旧遇到了许多的问题,但是一切都已经成功的克服,下面我会简单的介绍哈夫曼编码的压缩和解压缩原理。Ⅰ.哈夫曼原理 ...
  • java实现哈夫曼压缩

    2012-07-20 16:41:50
    哈夫曼压缩原理: 通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码. 其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短; 出现频率越低的...
  • 哈夫曼编码原理

    千次阅读 2016-06-28 13:51:48
    哈夫曼(Huffman)编码是一种常用的压缩编码方法,是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同。这些代码都是二...
  • 哈夫曼压缩思路

    2011-01-17 23:21:14
    正准备利用哈夫曼原理做一个压缩软件。现在现将我的思路记录下来,大家如果有好的意见可以评论给我,大家一起学习!!! :) 首先先解释一下为什么可以用利用哈夫曼树做压缩软件。我们都知道哈夫曼树有一个特点:...
  • 浅谈哈夫曼压缩

    2012-08-24 12:50:39
    所以自己在理解或者是理清思路上费了很大的劲,才弄明白哈夫曼的压缩与解压每一步到底是怎么实现的,或者说他的原理是什么,不管怎样,在分参考了前辈的代码及努力之下,我的哈夫曼压缩终于完成啦。。。。 首先,先...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 277
精华内容 110
关键字:

哈夫曼压缩原理