哈夫曼文件加密与压缩算法Python实现

突然对压缩算法感兴趣,当然要拜HBO《硅谷》所赐。

该剧描述四个不善社交但绝顶聪明的计算机程序员受到依靠互联网站发家的百万富翁的特殊照顾。他们可以免费住在他家中,但他们的项目日后如果获得成功,他要拿10%的股份。刚开始这些人没能说动一名亿万富翁投资他们的项目,于是各自回到原先的工作岗位。这名亿万富翁和其中一名计算机程序员供职的公司很快意识到他们的新型文件压缩算法则具有无法估量的商业潜力,于是一场白热化的争夺战开始了。

先简单介绍一下哈夫曼编码

(1) 以权值分别为W1,W2...Wn的n各结点,构成n棵二叉树T1,T2,...Tn并组成森林F={T1,T2,...Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点;
(2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树,并且置新二叉树根结点权值为左右子树上根结点的权值之和(根结点的权值=左右孩子权值之和,叶结点的权值= Wi)
(3) 从F中删除这两棵二叉树,同时将新二叉树加入到F中;
(4) 重复(2)、(3)直到F中只含一棵二叉树为止,这棵二叉树就是Huffman树。

Python代码:

代码修改自:https://www.jianshu.com/p/4cbbfed4160b

测试:

首先有一个2.41M的txt文件

压缩后生成一个out.xyz的文件(加密过,类型为.xyz)

压缩后的大小时原来的66%,用txt文件打开发现是乱码,说明加密成功。

解压及还原的文件:

三个文件:

读者评分
[评分人数: 2 平均分: 5]

评论

OmegaXYZ