Skip to content

Latest commit

 

History

History
157 lines (91 loc) · 5 KB

README.md

File metadata and controls

157 lines (91 loc) · 5 KB

信息论课程实验

BUAA CST Spring 2019 Information Theory Experiment

懒得用英文了,反正就是三个很水的小程序,但是还蛮好玩的。

Requirement

  • Python 3
  • scipy
  • decimal

Introduction

(赶着DDL写出来的,原理对了就行)

验证了随机信源序列的渐近等同分割性(Asymptotic Equipartition Property, AEP):

当随机变量的序列足够长时,其中一部分序列出现的概率近乎相等,每个信源符号的平均信息量接近于信源的熵H(U),且这部分序列出现的概率和趋近于1,称为典型序列集,而其余的非典型序列集出现的概率和趋近于0。典型序列又称为渐近等概序列或AEP序列。实质上就是大数定律在信息论里的应用吧。

实验中使用的是离散无记忆信源输出的消息序列,因为浮点数精度问题用了高精度模块计算,实验现象与理论吻合。

Usage

python aep.py

Results

参数:epsilon=0.05, P(X=1)=0.6

序列长度 典型集概率和 典型序列数量 典型序列数量占比
25 0.69 1.6*10^7 0.48
50 0.81 5.0*10^14 0.44
100 0.92 4.8*10^29 0.38
200 0.99 5.8*10^59 0.36
500 0.99 8.2*10^149 0.25
1000 0.99 1.9*10^300 0.18

Requirement

  • Python 3
  • queue
  • argparse
  • matplotlib

Introduction

使用Huffman最佳不等长编码对文件进行编码(压缩)和译码(解压缩)。由于我们并不知道信源的真正分布,所以只能通过文件中的统计规律近似其分布。

编码过程基本就是构造Huffman树,然后遍历树得到每个符号的不等长编码,对文件进行编码。同时还需要把码字对照表存到文件里用于译码,由于存储文件时需要字节对齐,所以要在后面对填充,为了避免填充的符号使译码时候中产生困惑,也同时记录了文件大小。最后模仿传统压缩文件,把文件名也记录了进去,最终压缩文件的存储结构是:

文件名|0x00|文件大小|0x00|对应码表|文件内容编码|00...

由于我们将每个字节视为一个信源符号,所以共有256个信源符号,每个符号都按序存在码字对照表中,按序可以省去我们存储信源符号的空间,存储结构是:

码字长度|对应码字|00...

译码过程首先恢复码字对照表,然后按照一般异字头编码的译码规则即可。

最终也是由于时间原因,优化应该没有做到头,至少原理是没错的,Python的优化也是各种玄学。(还是因为自己对Python底层懂得太少)

Usage

python huffman.py -p file_path -j [encode|decode|eval] -b show_bar -i display_info

显示帮助:

python huffman.py -h

Results

为了写实验报告,我对许多文件做了测试,但是不在这里一一贴出来了,大致说一下程序性能:

英文文本文件的压缩率:~60%

位图文件的压缩率:~65%

其余已经经过压缩的文件格式(pdf/docx/jpg/png/mp3/mp4):~100%

编码速度:850KB/s±200KB/s

译码速度:300KB/s±50KB/s

Requirement

  • Python 3
  • argparse
  • matplotlib

Introduction

使用LZ78算法对文件进行编码(压缩)和译码(解压缩),LZ系列算法并不需要预先知道信源的分布,利用的是字典技术,而且字典本身不需要传输,所以是一种很巧妙的方法,与Huffman编码算法一样可以逼近信息熵的极限。

编码过程是首先将输入序列分段,分段规则是与之前分段均不相同的最短序列,然后从分段数量得到段号的码长,结合符号的编码,对每个分段进行编码。具体算法不再赘述,可以参考《信息论与编码 第二版》(王育民著)中的介绍。

最终压缩文件的存储结构是:

文件名|0x00|文件大小|0x00|段号码长|0x00|文件内容编码|00...

译码时候一边译码一边建立字典,从而恢复出文件内容。

优化 Go Away

Usage

python lz78.py -p file_path -j [encode|decode|eval] -b show_bar -i display_info

显示帮助:

python lz78.py -h

Results

英文文本文件的压缩率:~50%

位图文件的压缩率:~50%

其余已经经过压缩的文件格式(pdf/docx/jpg/png/mp3/mp4):~100%

编码速度:450KB/s±200KB/s

译码速度:550KB/s±50KB/s

(为什么编码速度浮动这么大?不等长编码下由于信源分布不同导致?)

Example

放几个编码程序的运行效果图=w=

编码

encode

评估

eval

License

This project is licensed under the terms of the MIT license.