信息论与熵

熵是随机变量不确定性的度量：分布越均匀，熵越高；分布越集中，熵越低。

香农熵：信息量的下界

package main

import (
    "fmt"
    "math"
)

// 香农熵：H(X) = -Σ p(x) log₂ p(x)
func entropy(probs []float64) float64 {
    h := 0.0
    for _, p := range probs {
        if p > 0 {
            h -= p * math.Log2(p)
        }
    }
    return h
}

// KL 散度：D_KL(P||Q) = Σ p(x) log(p(x)/q(x))
// 衡量 P 和 Q 的差异（非对称！）
func klDivergence(p, q []float64) float64 {
    kl := 0.0
    for i := range p {
        if p[i] > 0 {
            kl += p[i] * math.Log(p[i]/q[i])
        }
    }
    return kl
}

// 交叉熵：H(P,Q) = H(P) + D_KL(P||Q) = -Σ p(x) log q(x)
// 机器学习的分类损失函数
func crossEntropy(trueLabels, predicted []float64) float64 {
    ce := 0.0
    for i := range trueLabels {
        if trueLabels[i] > 0 {
            ce -= trueLabels[i] * math.Log(predicted[i])
        }
    }
    return ce
}

func main() {
    // 均匀分布：熵最大
    uniform := []float64{0.25, 0.25, 0.25, 0.25}
    fmt.Printf("均匀分布熵: %.4f bits（最大）\n", entropy(uniform))

    // 确定性分布：熵为 0
    certain := []float64{1.0, 0, 0, 0}
    fmt.Printf("确定性分布熵: %.4f bits（最小）\n", entropy(certain))

    // 英语字母分布（近似）：熵 ≈ 4.18 bits < log₂(26) = 4.7 bits
    // 这正是为什么英文可以压缩
    skewed := []float64{0.4, 0.3, 0.2, 0.1}
    fmt.Printf("偏斜分布熵: %.4f bits\n", entropy(skewed))

    // 交叉熵损失：真实标签 [1,0,0]，预测 [0.7,0.2,0.1]
    truth := []float64{1, 0, 0}
    pred := []float64{0.7, 0.2, 0.1}
    fmt.Printf("交叉熵损失: %.4f\n", crossEntropy(truth, pred))
    // 预测 [0.9,0.05,0.05] 时损失更小：
    pred2 := []float64{0.9, 0.05, 0.05}
    fmt.Printf("更好预测的损失: %.4f\n", crossEntropy(truth, pred2))
}

Huffman 编码：最优前缀码

Huffman 编码是无损压缩的理论最优：出现频率高的字符用短编码，频率低的用长编码。平均码长接近香农熵下界。ZIP、gzip、JPEG 的熵编码阶段都用它（或变体）。

package main

import (
    "container/heap"
    "fmt"
)

type HNode struct {
    char        rune
    freq        int
    left, right *HNode
}

type HHeap []*HNode

func (h HHeap) Len() int            { return len(h) }
func (h HHeap) Less(i, j int) bool  { return h[i].freq < h[j].freq }
func (h HHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *HHeap) Push(x interface{}) { *h = append(*h, x.(*HNode)) }
func (h *HHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func buildHuffman(freq map[rune]int) *HNode {
    h := &HHeap{}
    for ch, f := range freq {
        heap.Push(h, &HNode{char: ch, freq: f})
    }
    for h.Len() > 1 {
        l := heap.Pop(h).(*HNode)
        r := heap.Pop(h).(*HNode)
        heap.Push(h, &HNode{freq: l.freq + r.freq, left: l, right: r})
    }
    return heap.Pop(h).(*HNode)
}

func buildCodes(node *HNode, prefix string, codes map[rune]string) {
    if node == nil { return }
    if node.left == nil && node.right == nil {
        codes[node.char] = prefix
        return
    }
    buildCodes(node.left, prefix+"0", codes)
    buildCodes(node.right, prefix+"1", codes)
}

func main() {
    text := "abracadabra"
    freq := map[rune]int{}
    for _, c := range text { freq[c]++ }

    root := buildHuffman(freq)
    codes := map[rune]string{}
    buildCodes(root, "", codes)

    fmt.Println("Huffman 编码:")
    totalBits := 0
    for ch, code := range codes {
        bits := len(code) * freq[ch]
        totalBits += bits
        fmt.Printf("  '%c'(freq=%d): %s (%d bits)\n", ch, freq[ch], code, bits)
    }
    fmt.Printf("总位数: %d（固定 3bit 编码需 %d 位）\n", totalBits, len(text)*3)
}

信息论的香农极限

香农信源编码定理：无损压缩的极限是信源的熵。英文文本的熵约 1.3 bits/字符（而非 ASCII 的 8 bits），这是 gzip 能压缩到 12% 的数学根基。任何无损压缩算法都不能低于这个极限——这是信息论给出的绝对下界。

信息就是惊讶。最意外的消息，承载最多信息。

— Claude Shannon, 1948