2015年赫尔辛基大学数据压缩讲座1：香农定理介绍

在2015年1月13日的University of Helsinky计算机科学课程中，Travis Gagie教授开始了关于数据压缩技术的第一讲——香农定理（Shannon's Theorem）。课程旨在为学生提供一个理论基础，使他们理解信息压缩的重要性和方法。数据压缩自古已有之，但直到1948年香农提出信息论，才为其奠定了坚实的数学基础。 香农的关键贡献在于为信息量的定义和测量提供了精确且客观的标准，避免了哲学争论。他通过考虑Alice和Bob之间的交互来阐述问题：假设Alice和Bob都知道随机变量X可能取值的概率分布P，其中p1到pn是每个值的概率。当Alice得知X的具体值并告知Bob时，她传递的信息量如何衡量？ 香农提出了三个基本假设或公理： 1. 期望传达的信息量应是概率分布连续函数的结果。这意味着随着概率值的微小变化，信息量的变化也是连续的。 2. 如果所有概率都相等，即p1 = p2 = ... = pn，信息量应该达到最小，因为在这种情况下，每个值提供的信息是一样的。 3. 信息量应该是非负的，并且只有当随机事件发生时才会传递信息，概率为零的事件不会传递任何信息。 香农的信息熵（Shannon entropy）概念就是基于这些公理，它用来量化一个随机变量的信息量。信息熵H(X)定义为： \[ H(X) = -\sum_{i=1}^{n} p_i \log_2(p_i) \] 这个公式表明，信息熵与每个可能值的概率成对数关系，概率越大，信息熵越小；相反，概率越小，信息熵越大。香农定理不仅在数据压缩中至关重要，还广泛应用于编码理论、通信系统设计、密码学等领域，因为它是理解和优化信息传输效率的基础。 在本课程中，学生们将学习如何利用香农定理分析和设计数据压缩算法，如熵编码（如霍夫曼编码），以及如何评估不同编码方法的有效性和效率。课程还将涉及实际应用中的数据压缩技术，如无损压缩（如LZW）和有损压缩（如JPEG），以及压缩算法的编码效率与压缩比之间的权衡。通过参与课堂讨论和实践活动，学生们将深化对数据压缩技术的理解，并为最终考试做好准备。