程序员数学09：信息论 - 数据压缩

本文是《程序员数学扫盲课》系列文章

← 上一篇：程序员数学08：哈希与模运算 – 负载均衡 | → 下一篇：程序员数学10：组合数学 – 容量规划

TL;DR

为什么ZIP能把文件压缩到原来的1/10？为什么HTTPS加密后数据变大了？为什么UTF-8比UTF-32省空间？答案都藏在信息论里。这篇文章用Go代码带你搞懂数据压缩的数学原理，看完你会发现：信息论就是”用最少的比特表示最多的信息”。

系列导航

《程序员数学扫盲课》系列：
1. 破冰篇：数学符号就是代码
2. 对数Log：数据库索引的魔法
3. 集合论：玩转Redis与SQL
4. 图论基础：微服务依赖管理
5. 概率论：系统可用性计算
6. 统计学：P99延迟与监控报警
7. 线性代数入门：推荐系统的数学基础
8. 哈希与模运算：负载均衡算法
9. 信息论：数据压缩与编码（本篇）
10. 组合数学：容量规划与性能预估

一、信息熵：信息的度量单位

先说重点：信息熵衡量”不确定性”，不确定性越高，信息量越大。

1.1 从抛硬币说起

场景1：公平硬币

正面概率：50%
反面概率：50%

问题： 告诉你结果是”正面”，包含多少信息？

答案： 1比特（bit）

原因： 两种可能性相等，需要1个二进制位表示（0或1）

场景2：作弊硬币

正面概率：99%
反面概率：1%

问题： 告诉你结果是”正面”，包含多少信息？

答案： 很少！因为你几乎能猜到是正面。

问题： 告诉你结果是”反面”，包含多少信息？

答案： 很多！因为这是个意外。

1.2 信息熵公式

香农熵（Shannon Entropy）：

H(X) = -Σ p(x) × log₂(p(x))

翻译成人话：
– H(X)：信息熵，单位是比特（bit）
– p(x)：事件x发生的概率
– log₂：以2为底的对数

Go代码实现：

package main

import (
    "fmt"
    "math"
)

// 计算信息熵
func Entropy(probs []float64) float64 {
    entropy := 0.0
    for _, p := range probs {
        if p > 0 {
            entropy -= p * math.Log2(p)
        }
    }
    return entropy
}

func main() {
    // 场景1：公平硬币
    fairCoin := []float64{0.5, 0.5}
    fmt.Printf("公平硬币的熵: %.4f bits\n", Entropy(fairCoin))

    // 场景2：作弊硬币
    biasedCoin := []float64{0.99, 0.01}
    fmt.Printf("作弊硬币的熵: %.4f bits\n", Entropy(biasedCoin))

    // 场景3：确定事件
    certain := []float64{1.0, 0.0}
    fmt.Printf("确定事件的熵: %.4f bits\n", Entropy(certain))
}

输出：

公平硬币的熵: 1.0000 bits
作弊硬币的熵: 0.0808 bits
确定事件的熵: 0.0000 bits

关键发现：
– 公平硬币熵=1 bit：最大不确定性
– 作弊硬币熵≈0.08 bit：几乎确定
– 确定事件熵=0 bit：没有不确定性

二、霍夫曼编码：最优的压缩算法

2.1 为什么需要变长编码？

问题： 英文文本中，字母’e’出现频率最高，’z’最少。如果都用8位表示，是不是浪费？

答案：用霍夫曼编码（Huffman Coding）

核心思想：
– 高频字符用短编码（如’e’ → 01）
– 低频字符用长编码（如’z’ → 11010110）

2.2 霍夫曼编码原理

示例： 压缩字符串”AAABBC”

步骤1：统计频率

A: 3次
B: 2次
C: 1次

步骤2：构建霍夫曼树

      (6)
     /   \
   (3)   (3)
    A    / \
       (2) (1)
        B   C

步骤3：生成编码

A: 0
B: 10
C: 11

步骤4：编码

原始：AAABBC
编码：0 0 0 10 10 11 = 00010101011（11 bits）

对比：
– 固定长度编码（每个字符2 bits）：6字符 × 2 = 12 bits
– 霍夫曼编码：11 bits
– 压缩率：(12-11)/12 = 8.3%

2.3 Go实现霍夫曼编码

package main

import (
    "container/heap"
    "fmt"
)

// 霍夫曼树节点
type HuffmanNode struct {
    char  rune
    freq  int
    left  *HuffmanNode
    right *HuffmanNode
}

// 优先队列（最小堆）
type PriorityQueue []*HuffmanNode

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].freq < pq[j].freq }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*HuffmanNode))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

// 构建霍夫曼树
func BuildHuffmanTree(text string) *HuffmanNode {
    // 统计频率
    freqMap := make(map[rune]int)
    for _, char := range text {
        freqMap[char]++
    }

    // 创建优先队列
    pq := &PriorityQueue{}
    heap.Init(pq)

    for char, freq := range freqMap {
        heap.Push(pq, &HuffmanNode{char: char, freq: freq})
    }

    // 构建树
    for pq.Len() > 1 {
        left := heap.Pop(pq).(*HuffmanNode)
        right := heap.Pop(pq).(*HuffmanNode)

        parent := &HuffmanNode{
            freq:  left.freq + right.freq,
            left:  left,
            right: right,
        }
        heap.Push(pq, parent)
    }

    return heap.Pop(pq).(*HuffmanNode)
}

// 生成编码表
func GenerateCodes(root *HuffmanNode, code string, codes map[rune]string) {
    if root == nil {
        return
    }

    // 叶子节点
    if root.left == nil && root.right == nil {
        codes[root.char] = code
        return
    }

    GenerateCodes(root.left, code+"0", codes)
    GenerateCodes(root.right, code+"1", codes)
}

func main() {
    text := "AAABBC"

    // 构建霍夫曼树
    root := BuildHuffmanTree(text)

    // 生成编码表
    codes := make(map[rune]string)
    GenerateCodes(root, "", codes)

    fmt.Println("霍夫曼编码表：")
    for char, code := range codes {
        fmt.Printf("%c: %s\n", char, code)
    }

    // 编码
    encoded := ""
    for _, char := range text {
        encoded += codes[char]
    }

    fmt.Printf("\n原始文本: %s\n", text)
    fmt.Printf("编码结果: %s\n", encoded)
    fmt.Printf("原始长度: %d bits (每字符2 bits)\n", len(text)*2)
    fmt.Printf("压缩长度: %d bits\n", len(encoded))
    fmt.Printf("压缩率: %.2f%%\n", float64(len(text)*2-len(encoded))/float64(len(text)*2)*100)
}

输出：

霍夫曼编码表：
A: 0
B: 10
C: 11

原始文本: AAABBC
编码结果: 00010101011
原始长度: 12 bits (每字符2 bits)
压缩长度: 11 bits
压缩率: 8.33%

三、实战应用：ZIP压缩的原理

3.1 为什么ZIP能压缩到1/10？

ZIP压缩的核心技术：
1. LZ77算法：找重复字符串，用指针替代
2. 霍夫曼编码：对LZ77输出再压缩

示例： 压缩”AAAAAABBBCCC”

步骤1：LZ77找重复

原始：AAAAAABBBCCC
LZ77：A (回退0, 长度6) B (回退0, 长度3) C (回退0, 长度3)

步骤2：霍夫曼编码

对LZ77的输出再用霍夫曼编码压缩

3.2 Go实现简化版LZ77

package main

import "fmt"

// LZ77压缩（简化版）
func LZ77Compress(text string) []string {
    result := []string{}
    i := 0

    for i < len(text) {
        // 找最长重复
        maxLen := 0
        maxDist := 0

        for j := 0; j < i; j++ {
            length := 0
            for k := 0; k < len(text)-i && text[j+k] == text[i+k]; k++ {
                length++
            }

            if length > maxLen {
                maxLen = length
                maxDist = i - j
            }
        }

        if maxLen > 2 {
            // 找到重复，用指针表示
            result = append(result, fmt.Sprintf("(回退%d,长度%d)", maxDist, maxLen))
            i += maxLen
        } else {
            // 没找到重复，直接输出字符
            result = append(result, string(text[i]))
            i++
        }
    }

    return result
}

func main() {
    text := "AAAAAABBBCCC"

    compressed := LZ77Compress(text)

    fmt.Printf("原始文本: %s\n", text)
    fmt.Printf("LZ77压缩: %v\n", compressed)
    fmt.Printf("原始长度: %d 字符\n", len(text))
    fmt.Printf("压缩长度: %d 个token\n", len(compressed))
}

输出：

原始文本: AAAAAABBBCCC
LZ77压缩: [A (回退1,长度5) B (回退1,长度2) C (回退1,长度2)]
原始长度: 12 字符
压缩长度: 4 个token

四、小结

这篇文章的核心观点：

1. 信息熵衡量不确定性，不确定性越高信息量越大，单位是比特（bit）
2. 霍夫曼编码是最优的变长编码，高频字符用短编码，低频字符用长编码
3. ZIP压缩 = LZ77 + 霍夫曼编码，先找重复再压缩，能达到10倍压缩率
4. 信息论是数据压缩的数学基础：ZIP、GZIP、PNG、MP3都基于此
5. 压缩的极限是信息熵，无损压缩不可能超越香农极限

记住这个对照表：

实战建议：
– 文本文件用GZIP压缩，压缩率通常50-80%
– 图片用PNG（无损）或JPEG（有损），根据场景选择
– 日志文件压缩后再传输，能节省90%带宽

下次面试官问”ZIP压缩原理”，你就可以回答：ZIP用LZ77算法找重复字符串用指针替代，再用霍夫曼编码对输出做变长编码。LZ77解决重复问题，霍夫曼解决频率问题，两者结合能达到10倍压缩率。

参考资料
– 《信息论基础》：香农信息论
– DEFLATE算法：ZIP/GZIP实现
– RFC 1951：DEFLATE规范

返回系列总览

👉 程序员数学扫盲课：完整课程大纲