压缩的原理及有限性
在计算机导论中简要介绍过几种压缩的算法，原理十分简单，便是利用更短、熵更高的字符串来代替一些重复率高，熵较低的字符串，从而实现缩短字节量，减小文件的体积的目的。步骤大致如下：
- 得到文件的概率分布，统计频次高的以及频次低的部分；
- 结合统计结果对源文件重新编码，用短字符代替重复的长字符。
举个例子：
AAAAAAAAAA => 10A // 用 3 个字符代表 10 个字符，压缩比 30%
ABCABCABCABCABCABCABCABC => 8ABC // 用 4 个字符代表 24 个字符，压缩比 16.7%
显而易见，越是重复率高的文件，就意味着能够压缩的量就越大，体积也自然能够越小；反之，如果一个文件的重复率低，也就越难压缩。所以每一个文件的熵不同，压缩比率也会不尽相同。
那么，压缩有一定的限度吗？
当然，在信息论中我们学到过，无损压缩实现的前提是输出和输入必须要严格一一对应，也就是不能够出现多对一的映射。我们可以假设任意文件都能够压缩到 $n$ bits，那么就能够产生 $2^n$ 种可能的压缩结果。这便意味着如果有 $2^n+m$ 个不同的文件，就会导致有 $m+1$ 个文件出现了重复，所以压缩一定存在着极限。
压缩的极限
一个文件的压缩极限可以通过计算文件的平均信息熵大小，从而推导出来。当然这个最小值仅仅是理论最小值，并不一定能够达到，下面我将用浅显的方式做一些推导。
在不同的文件格式中可能存在着不同的计算方法，比如文本文件可能就会根据文本中的字符计算信息熵，图片会使用 RGB 排列来计算信息熵等。我这里使用了一个通用的方法——将任意文件按字节的形式进行读取，统计不同字节的信息熵。
计算平均信息熵的公式为：
$$H(X)=\sum P_n * \log(\frac{1}{P_n})$$
$P_n$ 为每一个字节在文件中出现的概率，计算方法如下：
$$P_n=\frac{N_{freq}}{N_{all}}$$
$N_{freq}$ 为该字节在文件中出现的次数，$N_{all}$ 文件的总字节量。
其中的 $log$ 在信息论中是默认以 2 为底的（在通信原理中是默认以 10 为底），通常会做省略处理。
最后求出来的 $H(X)$ 是文件每一个字节的平均信息熵，如果乘以总字节数就可以得到理论的压缩极限大小：
$$Size_{min}=H(X) * N_{all}$$
信息熵的含义
- 信息熵只反映内容的随机性，与内容本身无关。不管是什么文件，服从同样的概率分布就会得到同样的信息熵。
- 信息熵越大，表示占用的二进制位越长，可以表达更多的符号。即信息熵越大，信息量就越大，但这并不代表所获得的的信息越大。
代码实现 (Python)
import sys
from math import log
from argparse import ArgumentParser
from os.path import dirname, abspath, realpath
def main():
# Initialization
real_path = dirname(realpath(sys.executable))
parser = ArgumentParser()
parser.add_argument('address')
args = parser.parse_args()
path = abspath(real_path + '\\' + args.address)
file_format = path.split('.')[-1]
# Read the file
try:
f = open(path, "rb")
byteArr = list(f.read())
fileSize = len(byteArr)
f.close()
except IOError:
path = args.address
f = open(path, "rb")
byteArr = list(f.read())
fileSize = len(byteArr)
f.close()
# core algorithm for shannon entropy
ent = 0
for b in range(256):
ctr = 0
for byte in byteArr:
if byte == b:
ctr += 1
freq = ctr / fileSize
if freq > 0:
ent = ent - freq * log(freq, 2)
# print the information
print('\n==================== File Information ====================')
print('Location: ', path)
print(' Format: ', file_format)
print(' Size: ', fileSize, 'Bytes')
print('\n================= Amount of Information =================')
print('Average: ', round(ent, 2))
print(' Total: ', round(ent * fileSize, 2))
if __name__ == '__main__':
main()
代码直接使用命令行运行即可，格式为
python main.py test.txt。其中test.txt为你需要计算信息熵的文件。 代码对地址作了处理，使用绝对路径和相对路径皆可。