本系统开发工具：C++
本设计包含内容：源代码+可执行程序+毕业论文+开题报告+答辩稿
论文大概：
前言
一千多年前的中国学者就知道用“班马”这样的缩略语来指代班固和司马迁,这种崇尚简约的风俗一直延续到了今天的 Internet 时代：当我们在 BBS
上用“ 7456 ”代表“气死我了”,或是用“ B4
”代表“ Before
”的时候,我们至少应该知道,这其实就是一种最简单的数据压缩呀。
严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码时,如果为出现概率较高的字母赋予较短的编码,为出现概率较低的字母赋予较长的编码,总的编码长度就能缩短不少。远在计算机出现之前,著名的 Morse 电码就已经成功地实践了这一准则。在 Morse
码表中,每个字母都对应于一个唯一的点划组合,出现概率最高的字母 e
被编码为一个点“ . ”,而出现概率较低的字母 z 则被编码为“ --..
”。显然,这可以有效缩短最终的电码长度。
信息论之父 C. E. Shannon 第一次用数学语言阐明了概率与信息冗余度的关系。在 1948 年发表的论文“通信的数学理论（ A Mathematical Theory of Communication ）”中, Shannon
指出,任何信息都存在冗余,冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。Shannon 借鉴了热力学的概念,把信息中排除了冗余后的平均信息量称为“信息熵”,并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作,信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲,数据压缩的目的就是要消除信息中的冗余,而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵公式,人们可以计算出信息编码的极限,即在一定的概率模型下,无损压缩的编码长度不可能小于信息熵公式给出的结果。
有了完备的理论,接下来的事就是要想办法实现具体的算法,并尽量使算法的输出接近信息熵的极限了。当然,大多数工程技术人员都知道,要将一种理论从数学公式发展成实用技术,就像仅凭一个 E=mc 2 的公式就要去制造核武器一样,并不是一件很容易的事。
数学游戏
设计具体的压缩算法的过程通常更像是一场数学游戏。开发者首先要寻找一种能尽量精确地统计或估计信息中符号出现概率的方法,然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效,迄今为止,人们已经陆续实现了静态模型、半静态模型、自适应模型、 Markov
模型、部分匹配预测模型等概率统计模型。相对而言,编码方法的发展历程更为曲折一些。
1948
年, Shannon
在提出信息熵理论的同时,也给出了一种简单的编码方法—— Shannon
编码。 1952 年, R. M.
Fano 又进一步提出了 Fano
编码。这些早期的编码方法揭示了变长编码的基本规律,也确实可以取得一定的压缩效果,但离真正实用的压缩算法还相去甚远。
第一个实用的编码方法是由 D. A. Huffman 在 1952
年的论文“最小冗余度代码的构造方法（ A
Method for the Construction of Minimum Redundancy Codes
）”中提出的。直到今天,许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为 Huffman 编码的方法。 Huffman
编码在计算机界是如此著名,以至于连编码的发明过程本身也成了人们津津乐道的话题。据说,1952 年时,年轻的 Huffman
还是麻省理工学院的一名学生,他为了向老师证明自己可以不参加某门功课的期末考试,才设计了这个看似简单,但却影响深远的编码方法。
Huffman 编码效率高,运算速度快,实现方式灵活,从 20
世纪 60 年代至今,在数据压缩领域得到了广泛的应用。例如,早期 UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT
实际就是 Huffman 0 阶自适应编码的具体实现。 20 世纪 80 年代初, Huffman 编码又出现在 CP/M
和 DOS 系统中,其代表程序叫 SQ
。今天,在许多知名的压缩工具和压缩算法（如 WinRAR 、 gzip 和 JPEG ）里,都有 Huffman 编码的身影。不过, Huffman
编码所得的编码长度只是对信息熵计算结果的一种近似,还无法真正逼近信息熵的极限。正因为如此,现代压缩技术通常只将 Huffman 视作最终的编码手段,而非数据压缩算法的全部。