BUAA CST Spring 2019 Information Theory Experiment

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

• Python 3
• scipy
• decimal

（赶着DDL写出来的，原理对了就行）

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

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

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

python aep.py

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

• Python 3
• queue
• argparse
• matplotlib

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

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

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

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

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

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

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

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

显示帮助：

python huffman.py -h

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

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

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

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

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

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

• Python 3
• argparse
• matplotlib

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

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

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

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

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

（优化 Go Away）

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

显示帮助：

python lz78.py -h

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

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

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

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

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

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

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

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