基于Huffman编码的压缩软件的Python实现

哈夫曼编码是利用贪心算法进行文本压缩的算法,其算法思想是首先统计文件中各字符出现的次数,保存到数组中,然后将各字符按照次数升序排序,挑选次数最小的两个元素进行连结形成子树,子树的次数等于两节点的次数之和,接着把两个元素从数组删除,将子树放入数组,重新排序,重复以上步骤。为了解压,在压缩时首先往文件中填入huffman编码的映射表的长度,该表的序列化字符串,编码字符串分组后最后一组的长度(编码后字符串长度模上分组长度),最后再填充编码后的字符串。本算法中以一个字节,8位作为分组长度,将编码后二进制字符串一一分组。代码如下:

__author__ = 'linfuyuan'
import struct
import pickle

type = int(raw_input('please input the type number(0 for compress, 1 for decompress):'))
file = raw_input('please input the filepath:')


class Node:
    def __init__(self):
        self.value = ''
        self.left = None
        self.right = None
        self.frequency = 0
        self.code = ''


# let the unique value be the key in the map
def change_value_to_key(huffmap):
    map = {}
    for (key, value) in huffmap.items():
        map[value] = key
    return map


if type == 0:
    origindata = ''
    # count the frequency of each letter
    lettermap = {}

    def give_code(node):
        if node.left:
            node.left.code = '%s%s' % (node.code, '0')
            give_code(node.left)
        if node.right:
            node.right.code = '%s%s' % (node.code, '1')
            give_code(node.right)


    def print_code(node):
        if not node.left and not node.right:
            print "%s %s" % (node.value, node.code)
        if node.left:
            print_code(node.left)
        if node.right:
            print_code(node.right)


    def save_code(map, node):
        if not node.left and not node.right:
            map[node.value] = node.code
        if node.left:
            save_code(map, node.left)
        if node.right:
            save_code(map, node.right)


    with open(file)as f:
        for line in f.readlines():
            origindata += line
            for j in line:
                if lettermap.get(j):
                    lettermap[j] += 1
                else:
                    lettermap[j] = 1
    nodelist = []
    for (key, value) in lettermap.items():
        node = Node()
        node.value = key
        node.frequency = value
        nodelist.append(node)
    nodelist.sort(cmp=lambda n1, n2: cmp(n1.frequency, n2.frequency))
    for i in range(len(nodelist) - 1):
        node1 = nodelist[0]
        node2 = nodelist[1]
        node = Node()
        node.left = node1
        node.right = node2
        node.frequency = node1.frequency + node2.frequency
        nodelist[0] = node
        nodelist.pop(1)
        nodelist.sort(cmp=lambda n1, n2: cmp(n1.frequency, n2.frequency))
    # give the code
    root = nodelist[0]
    give_code(root)
    huffman_map = {}
    # save the node code to a map
    save_code(huffman_map, root)
    code_data = ''
    for letter in origindata:
        code_data += huffman_map[letter]
    output_data = ''
    f = open('%s_compress' % file, 'wb')
    huffman_map_bytes = pickle.dumps(huffman_map)
    f.write(struct.pack('I', len(huffman_map_bytes)))
    f.write(struct.pack('%ds' % len(huffman_map_bytes), huffman_map_bytes))
    f.write(struct.pack('B', len(code_data) % 8))
    for i in range(0, len(code_data), 8):
        if i + 8 < len(code_data):
            f.write(struct.pack('B', int(code_data[i:i + 8], 2)))
        else:
            # padding
            f.write(struct.pack('B', int(code_data[i:], 2)))
    f.close()
    print 'finished compressing'
if type == 1:
    f = open(file, 'rb')
    size = struct.unpack('I', f.read(4))[0]
    huffman_map = pickle.loads(f.read(size))
    left = struct.unpack('B', f.read(1))[0]
    data = f.read(1)
    datalist = []

    while not data == '':
        bdata = bin(struct.unpack('B', data)[0])[2:]
        datalist.append(bdata)
        data = f.read(1)
    f.close()
    for i in range(len(datalist) - 1):
        datalist[i] = '%s%s' % ('0' * (8 - len(datalist[i])), datalist[i])
    datalist[-1] = '%s%s' % ('0' * (left - len(datalist[-1])), datalist[-1])
    encode_data = ''.join(datalist)
    current_code = ''
    huffman_map = change_value_to_key(huffman_map)
    f = open('%s_origin' % file, 'w')
    for letter in encode_data:
        current_code += letter
        if huffman_map.get(current_code):
            f.write(huffman_map[current_code])
            current_code = ''
    f.close()

    print 'finished decompressing'
raw_input('please press any key to quit')

代码中有用到pickle模块进行对象序列化,还有struct模块进行读写二进制文件。

由于算法中运算量最⼤的地⽅在于循环⾥嵌套了排序,故算法的时间复杂度是O(n2logn)。

经过压缩后,文件大⼩小分别为110KB和931KB。原来⼤⼩为190KB和 2.1MB,压缩效果明显。

希望对大家有用。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏烂笔头

Python正则表达式:最短匹配

目录[-] 最短匹配应用于:假如有一段文本,你只想匹配最短的可能,而不是最长。 例子 比如有一段html片段,<a>this is first label<...

43570
来自专栏python成长之路

集合常用操作

17640
来自专栏Java Web

最大子段和问题

问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

42650
来自专栏yl 成长笔记

UML 类图基础

定义:两个类之间的强依赖关系, 可以为单向,亦可为双向。常见表现形式 为 A 类中有 B 类型的成员变量。

11440
来自专栏CDA数据分析师

excel公式中14种运算符,帮你整理齐了

文 | 赵志东 运算符是公式中最主要的组成部分,包括数学运算符、逻辑运算符和连接运算符等,下面我们就全面学习一下excel公式里的运算符。 一、运算符 1、 数...

21550
来自专栏开发技术

排序之冒泡排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

9640
来自专栏云霄雨霁

排序----选择排序

16800
来自专栏搞前端的李蚊子

JS使用循环按指定倍数分割数组组成新的数组的方法

 今天一个新人同事问了我一个问题,就是有一个像下边这种不知道具体长度的数组,想以每4个为一组,重新组合为一个二维数组,很简单的需求只需要用到一个循环再去取余数就...

46870
来自专栏九彩拼盘的叨叨叨

学习纲要:JavaScript 基础语法

11930
来自专栏kalifaの日々

C++构造无向图&求最短路径源码

用vector<edge> es[MAX]表示点,每个点队列里放着点的相邻边和到边的距离。 以下源码经过测试可运行 #include <iostream> #i...

32450

扫码关注云+社区

领取腾讯云代金券