一.介紹
數據壓縮是現代計算機科學和通信技術中不可或缺的組成部分，它通過減少數據表示所需的存儲空間和傳輸帶寬，極大地提高了系統效率和資源利用率。壓縮算法可分為兩大類：無損壓縮和有損壓縮。
無損壓縮算法能夠在解壓縮後完全恢復原始數據，適用於對數據完整性要求極高的場景；而有損壓縮算法則通過犧牲部分次要信息來獲得更高的壓縮比，適用於對數據精度要求相對較低的場景，如多媒體數據處理。
本文將首先介紹壓縮算法的基本概念和理論基礎，然後分別詳細討論無損壓縮算法和有損壓縮算法，並提供 Golang 的函數實現示例，最後對這些算法進行比較和總結。
二.壓縮算法基礎理論
信息熵與壓縮極限
根據香農信息論，數據壓縮的理論極限由信息熵決定。對於一個離散隨機變量 X，其概率分佈為 P (x)，則其信息熵 H (X) 定義為：
\( H(X) = -\sum_{x} P(x) \log_2 P(x) \)
信息熵表示了數據中包含的平均信息量，也是無損壓縮能夠達到的理論下限。實際壓縮算法的性能通常用壓縮比來衡量，即原始數據大小與壓縮後數據大小的比值。
無損壓縮與有損壓縮的區別
無損壓縮算法確保解壓縮後的數據與原始數據完全一致，適用於文本、程序代碼、醫療圖像等對數據完整性要求高的場景。有損壓縮算法則允許在解壓縮後的數據與原始數據之間存在一定差異，通過犧牲部分信息來換取更高的壓縮比，適用於音頻、視頻、普通圖像等場景。
壓縮算法的主要分類
根據壓縮原理，常見的壓縮算法可分為以下幾類：
- 基於統計的編碼：如霍夫曼編碼、算術編碼
- 基於字典的編碼：如 LZ77、LZ78、LZW
- 基於變換的編碼：如離散餘弦變換 (DCT)、離散小波變換 (DWT)
- 混合編碼：結合多種壓縮技術，如 DEFLATE、JPEG、MP3
三.無損壓縮算法詳解
1. 霍夫曼編碼 (Huffman Coding)
數學原理
霍夫曼編碼是一種基於貪心算法的最優前綴編碼方法，由 David Huffman 於 1952 年發明。其核心思想是讓出現頻率高的字符使用較短的編碼，出現頻率低的字符使用較長的編碼，從而使整體編碼長度最短。
根據香農信息論，最優編碼長度應滿足：
\( 碼長L(c) ≈ -\log_2(P(c)) \)
其中 P (c) 是字符 c 出現的概率。霍夫曼編碼通過貪心算法逼近這一理論極限。
霍夫曼編碼的具體步驟如下：
- 統計字符頻率：統計輸入數據中每個字符的出現頻率
- 構建優先隊列：將每個字符作為獨立節點，按頻率優先級構建優先隊列
- 合併節點：循環合併頻率最小的兩個節點，創建新的父節點，直到只剩一個根節點
- 生成編碼：從根節點到每個葉子節點的路徑決定了字符的編碼，左路徑為 0，右路徑為 1
霍夫曼編碼的數學證明表明，這種自底向上構建樹的方法能夠保證得到最優編碼，不同於香農 - 範諾編碼在某些情況下可能無法得到最優解的情況。
霍夫曼編碼的期望碼長 L 滿足：
\( H(X) ≤ L < H(X) + 1 \)
其中 H (X) 是信息熵。
Golang 實現
package main
import (
"container/heap"
"fmt"
)
type Node struct {
char rune
freq int
left *Node
right *Node
}
// 實現heap.Interface接口
type PriorityQueue []*Node
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{}) {
node := x.(*Node)
*pq = append(*pq, node)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
node := old[n-1]
*pq = old[0 : n-1]
return node
}
func buildHuffmanTree(text string) *Node {
// 統計字符頻率
freq := make(map[rune]int)
for _, c := range text {
freq[c]++
}
// 初始化優先隊列
var pq PriorityQueue
for c, f := range freq {
pq = append(pq, &Node{char: c, freq: f})
}
heap.Init(&pq)
// 合併節點直到只剩一個根節點
for pq.Len() > 1 {
left := heap.Pop(&pq).(*Node)
right := heap.Pop(&pq).(*Node)
merged := &Node{
freq: left.freq + right.freq,
left: left,
right: right,
}
heap.Push(&pq, merged)
}
return pq[0]
}
func generateCodes(root *Node) map[rune]string {
codes := make(map[rune]string)
var generate func(node *Node, currentCode string)
generate = func(node *Node, currentCode string) {
if node == nil {
return
}
if node.char != 0 {
codes[node.char] = currentCode
return
}
generate(node.left, currentCode+"0")
generate(node.right, currentCode+"1")
}
generate(root, "")
return codes
}
func huffmanEncode(text string, codes map[rune]string) string {
encoded := ""
for _, c := range text {
encoded += codes[c]
}
return encoded
}
func huffmanDecode(encoded string, root *Node) string {
decoded := []rune{}
current := root
for _, bit := range encoded {
if bit == '0' {
current = current.left
} else {
current = current.right
}
if current.char != 0 {
decoded = append(decoded, current.char)
current = root
}
}
return string(decoded)
}
func main() {
text := "ABACDA"
root := buildHuffmanTree(text)
codes := generateCodes(root)
encoded := huffmanEncode(text, codes)
decoded := huffmanDecode(encoded, root)
fmt.Printf("Original: %s\n", text)
fmt.Printf("Encoded: %s\n", encoded)
fmt.Printf("Decoded: %s\n", decoded)
}2. 算術編碼 (Arithmetic Coding)
數學原理
算術編碼是另一種熵編碼方法，與霍夫曼編碼不同，它將整個消息編碼為一個介於 0 和 1 之間的實數，而不是將每個字符獨立編碼為不同的碼字。
算術編碼的基本原理是：
- 初始化區間：從初始區間 \( [0, 1) \) 開始
- 符號處理：逐個處理輸入符號，根據符號的概率分佈不斷縮小當前區間
- 區間劃分：每個符號對應一個子區間，其長度與符號的概率成正比
- 輸出結果：最終的區間內的任意一個點都可以表示整個消息
具體來説，假設當前編碼區間為 \( [low, high) \)，對於輸入符號 s，其概率區間為 \( [Ps\_low, Ps\_high) \)，則新的區間更新為：
\( new\_low = low + (high - low) \times Ps\_low \)
\( new\_high = low + (high - low) \times Ps\_high \)
算術編碼的數學本質是通過連續分割區間來表示整個輸入消息，其壓縮效率理論上可以更接近香農熵極限。
算術編碼的優勢在於：
- 對於出現概率非常低的符號，無需分配較長的碼字
- 可以處理任意長度的符號序列，而不需要像霍夫曼編碼那樣將數據分割成固定大小的塊
- 更接近理論最優壓縮性能
Golang 實現
package main
import (
"fmt"
)
type Range struct {
low float64
high float64
}
func arithmeticEncode(symbols []rune, symbolRanges map[rune][2]float64) string {
rangeMap := make(map[rune][2]float64)
for c, r := range symbolRanges {
rangeMap[c] = r
}
currentRange := Range{0, 1}
for _, s := range symbols {
symRange := rangeMap[s]
delta := currentRange.high - currentRange.low
currentRange.low = currentRange.low + delta*symRange[0]
currentRange.high = currentRange.low + delta*symRange[1]
}
// 選擇區間中的一個點進行二進制表示
mid := (currentRange.low + currentRange.high) / 2
return floatToBinary(mid)
}
func floatToBinary(x float64) string {
binary := "0."
for i := 0; i < 32; i++ {
x *= 2
if x >= 1 {
binary += "1"
x -= 1
} else {
binary += "0"
}
if x == 0 {
break
}
}
return binary
}
func main() {
symbols := []rune{'A', 'B', 'E', 'R', 'R'}
symbolRanges := map[rune][2]float64{
'A': {0.0, 0.2},
'B': {0.2, 0.4},
'E': {0.4, 0.6},
'R': {0.6, 1.0},
}
encoded := arithmeticEncode(symbols, symbolRanges)
fmt.Println("Encoded:", encoded)
}3. LZ77 算法
數學原理
LZ77 是一種基於字典的無損壓縮算法，由 Abraham Lempel 和 Jacob Ziv 於 1977 年提出。它的核心思想是利用數據的重複結構信息來進行數據壓縮，通過查找滑動窗口內的最長匹配子串，並將其替換為指向窗口內位置的指針和匹配長度。
LZ77 算法的基本原理可以用以下數學模型描述：
假設當前處理位置為 i，滑動窗口大小為 W，預讀緩衝區大小為 L。算法在滑動窗口內尋找與預讀緩衝區中最長的匹配子串。如果匹配長度大於最小匹配長度，則輸出三元組 <長度，距離，下一個字符>；否則輸出 < 0, 0, 當前字符 >。
具體步驟如下：
- 滑動窗口維護：維護一個固定大小的滑動窗口，包含之前處理過的字符
- 預讀緩衝區：包含當前處理位置之後的字符
- 最長匹配查找：在滑動窗口中查找與預讀緩衝區中最長的匹配子串
- 輸出編碼：根據匹配結果輸出相應的編碼
LZ77 的數學模型可以表示為：
\( C = f(D, S) \)
其中 C 表示壓縮後的數據，D 表示重複子字符串的長度，S 表示非重複子字符串的長度。
值得注意的是，LZ77 嚴格意義上來説不是一種具體的算法，而是一種編碼理論，定義了原理但未規定具體實現方式。基於這一理論實現的算法才稱為 LZ77 算法或 LZ77 變種。
Golang 實現
package main
import (
"fmt"
"math"
)
type LZ77Output struct {
length int
distance int
nextChar byte
}
func lz77Compress(data []byte, windowSize int) []LZ77Output {
var output []LZ77Output
remaining := len(data)
i := 0
for i < remaining {
// 確定當前窗口的範圍
start := int(math.Max(float64(0), float64(i - windowSize)))
end := i
// 查找最長匹配
bestLength := 0
bestDistance := 0
for j := start; j < end; j++ {
currentLength := 0
for currentLength < remaining - i &&
currentLength < end - j &&
data[i + currentLength] == data[j + currentLength] {
currentLength++
}
if currentLength > bestLength {
bestLength = currentLength
bestDistance = i - j
}
}
if bestLength > 0 {
// 確保不超過窗口範圍
bestDistance = int(math.Min(float64(bestDistance), float64(windowSize)))
// 處理下一個字符
if i + bestLength < remaining {
output = append(output, LZ77Output{bestLength, bestDistance, data[i + bestLength]})
i += bestLength + 1
} else {
output = append(output, LZ77Output{bestLength, bestDistance, 0})
i += bestLength
}
} else {
output = append(output, LZ77Output{0, 0, data[i]})
i++
}
}
return output
}
func main() {
data := []byte("ABABABABABCABABABC")
windowSize := 10
compressed := lz77Compress(data, windowSize)
for _, out := range compressed {
fmt.Printf("<%d, %d, %c>\n", out.length, out.distance, out.nextChar)
}
}4. LZW 算法
數學原理
LZW (Lempel-Ziv-Welch) 算法是 LZ78 算法的改進版本，由 Terry Welch 於 1984 年提出。它的核心思想是動態構建字典，將輸入數據中的字符序列轉換為字典中的索引值。
LZW 算法與 LZ78 的主要區別在於初始化字典的方式：LZW 在編碼前預先初始化字典，包含所有可能的單字符輸入，而 LZ78 則根據輸入逐步構建字典。
LZW 算法的數學原理可以通過以下步驟描述：
- 字典初始化：初始化字典，包含所有單字符輸入
- 當前字符串維護：維護一個當前字符串，初始為空
- 字符處理：逐個處理輸入字符：
- 如果當前字符串加上當前字符在字典中，則更新當前字符串
- 否則，輸出當前字符串對應的字典索引，將當前字符串加上當前字符添加到字典中，重置當前字符串為當前字符
- 結束處理：處理結束後，輸出當前字符串對應的字典索引
LZW 算法的壓縮效率取決於字典的更新策略和字符串匹配的長度，其數學模型可以表示為：
\( C = \sum_{i=1}^{n} \log_2(M_i) \)
其中 C 表示壓縮後的數據長度，M_i 表示第 i 個字典條目的大小。
Golang 實現
package main
import (
"fmt"
)
func lzwCompress(data []byte) []int {
// 初始化字典，包含所有256個可能的單字節字符
dict := make(map[string]int)
for i := 0; i < 256; i++ {
dict[string([]byte{byte(i)})] = i
}
var result []int
currentString := ""
for _, c := range data {
char := string(c)
combined := currentString + char
if idx, exists := dict[combined]; exists {
currentString = combined
} else {
result = append(result, dict[currentString])
dict[combined] = len(dict)
currentString = char
}
}
if currentString != "" {
result = append(result, dict[currentString])
}
return result
}
func main() {
data := []byte("TOBEORNOTTOBEORTOBEORNOT")
compressed := lzwCompress(data)
fmt.Println("Compressed data:", compressed)
}5. DEFLATE 算法
數學原理
DEFLATE 算法是一種混合壓縮算法，結合了 LZ77 和霍夫曼編碼，是 gzip 和 zlib 的核心算法。它首先使用 LZ77 算法進行數據壓縮，生成一系列的匹配長度和距離，然後對這些輸出進行霍夫曼編碼，進一步提高壓縮效率。
DEFLATE 算法的數學原理可以分解為兩個主要步驟：
- LZ77 壓縮：將輸入數據轉換為一系列的 LZ77 編碼塊
- 霍夫曼編碼：對 LZ77 的輸出進行霍夫曼編碼，生成最終的壓縮數據
DEFLATE 算法的壓縮效率取決於兩個階段的協同工作：LZ77 能夠有效地捕獲數據中的重複模式，而霍夫曼編碼則能夠根據這些模式的出現頻率生成高效的二進制表示。
Golang 實現
由於 DEFLATE 算法較為複雜，這裏僅提供一個簡化的概念性實現：
package main
import (
"fmt"
)
func deflateCompress(data []byte, windowSize int) []int {
// 第一步：LZ77壓縮
lz77Output := lz77Compress(data, windowSize)
// 第二步：霍夫曼編碼
// 為簡化起見，這裏將LZ77輸出轉換為字符串形式
// 實際實現需要更復雜的處理
var symbols []rune
for _, out := range lz77Output {
symbols = append(symbols, rune(out.length))
symbols = append(symbols, rune(out.distance))
symbols = append(symbols, rune(out.nextChar))
}
// 構建霍夫曼樹
root := buildHuffmanTree(string(symbols))
codes := generateCodes(root)
// 編碼符號
var encoded []int
for _, c := range symbols {
code := codes[c]
// 這裏可以將二進制字符串轉換為整數列表表示
// 為簡化起見，直接存儲二進制字符串的長度
encoded = append(encoded, len(code))
}
return encoded
}
func main() {
data := []byte("ABABABABABCABABABC")
windowSize := 10
compressed := deflateCompress(data, windowSize)
fmt.Println("Compressed:", compressed)
}四.有損壓縮算法詳解
1. 離散餘弦變換 (DCT)
數學原理
離散餘弦變換 (Discrete Cosine Transform, DCT) 是一種廣泛應用於有損壓縮算法中的數學變換，特別在 JPEG 圖像壓縮和 MP3 音頻壓縮中發揮着核心作用。DCT 將時域或空域信號轉換為頻域表示，使得大部分能量集中在少數低頻係數中，從而實現高效的壓縮。
一維 DCT 的數學公式為：
\( X_k = \alpha(k) \sum_{n=0}^{N-1} x_n \cos\left(\frac{\pi}{N} \left(n + \frac{1}{2}\right)k\right) \)
其中：
- X_k是第 k 個 DCT 係數
- x_n是輸入信號的第 n 個樣本
- N是輸入信號的長度
- \( \alpha(k) \)是歸一化因子，定義為：
\( \alpha(k)=
\begin{cases}
\sqrt{\dfrac{1}{N}}, & k=0\[6pt]
\sqrt{\dfrac{2}{N}}, & k=1,2,\ldots,N-1
\end{cases} \)
二維 DCT 的數學公式為：
\( DCT(u, v) = \alpha(u)\alpha(v) \sum_{x=0}^{N-1} \sum_{y=0}^{M-1} f(x,y) \cos\left(\frac{\pi(2x+1)u}{2N}\right) \cos\left(\frac{\pi(2y+1)v}{2M}\right) \)
其中：
- \( f(x,y) \)是輸入圖像的像素值
- u和v是頻域座標
- \( \alpha(u) \)和\( \alpha(v) \)是歸一化因子
DCT 的逆變換 (IDCT) 公式為：
\( f(x,y) = \sum_{u=0}^{N-1} \sum_{v=0}^{M-1} \alpha(u)\alpha(v) DCT(u,v) \cos\left(\frac{\pi(2x+1)u}{2N}\right) \cos\left(\frac{\pi(2y+1)v}{2M}\right) \)
DCT 的數學本質是將信號分解為不同頻率的餘弦波分量，這些分量的振幅表示了對應頻率成分在原始信號中的貢獻程度。通過保留主要的低頻分量並丟棄次要的高頻分量，可以在幾乎不影響感知質量的情況下實現數據壓縮。
Golang 實現
package main
import (
"fmt"
"math"
)
func dct(input []float64) []float64 {
N := len(input)
output := make([]float64, N)
alpha := make([]float64, N)
for k := 0; k < N; k++ {
if k == 0 {
alpha[k] = math.Sqrt(1.0 / float64(N))
} else {
alpha[k] = math.Sqrt(2.0 / float64(N))
}
}
for k := 0; k < N; k++ {
sum := 0.0
for n := 0; n < N; n++ {
angle := math.Pi * float64(n + 0.5) * float64(k) / float64(N)
sum += input[n] * math.Cos(angle)
}
output[k] = alpha[k] * sum
}
return output
}
func main() {
input := []float64{1, 2, 3, 4}
output := dct(input)
fmt.Println("DCT coefficients:", output)
}2. JPEG 圖像壓縮算法
數學原理
JPEG (Joint Photographic Experts Group) 是一種廣泛應用的有損圖像壓縮標準，它利用人類視覺系統的特性，通過丟棄部分高頻信息來實現高壓縮比。JPEG 的核心算法基於離散餘弦變換 (DCT) 和量化技術。
JPEG 壓縮的數學原理可以通過以下步驟描述：
-
顏色空間轉換：將圖像從 RGB 顏色空間轉換為 YCbCr 顏色空間，分離亮度和色度信息：
\( Y = 0.299R + 0.587G + 0.114B \)
\( Cb = -0.1687R - 0.3313G + 0.5B + 128 \)
\( Cr = 0.5R - 0.4187G - 0.0813B + 128 \)
- 分塊處理：將圖像分割為 8x8 像素的塊，便於 DCT 處理
- DCT 變換：對每個 8x8 塊應用二維 DCT，將像素值轉換為頻域係數
-
量化：使用量化矩陣對 DCT 係數進行量化，減少精度：
\( Q(u,v) = \left\lfloor \frac{DCT(u,v)}{quant\_matrix(u,v)} + 0.5 \right\rfloor \)
其中 quant_matrix 是預定義的量化矩陣，通常對亮度和色度使用不同的矩陣
- Zig-Zag 掃描：將二維繫數矩陣轉換為一維序列，按頻率排序，使得低頻係數在前，高頻係數在後
- 熵編碼：對量化後的係數進行熵編碼，通常使用霍夫曼編碼
JPEG 壓縮的數學模型可以表示為：
\( C = Q(DCT(I)) \)
其中 C 表示壓縮後的數據，I 表示原始圖像，Q 表示量化操作，DCT 表示離散餘弦變換。
JPEG 的逆過程，即解壓縮，通過逆量化、逆 DCT 和顏色空間轉換實現：
\( I' = IDCT(Q^{-1}(C)) \)
其中 I' 是解壓縮後的圖像，\( Q^{-1} \) 表示逆量化操作，IDCT 表示逆離散餘弦變換。
Golang 實現
由於 JPEG 算法較為複雜，這裏僅提供核心步驟的簡化實現：
package main
import (
"fmt"
"math"
)
func jpegCompress(image [][]float64, quantMatrix [][]float64) [][]int {
// 分塊處理（假設圖像是8x8的）
// 應用二維DCT
dctResult := dct2D(image)
// 量化
quantized := quantize(dctResult, quantMatrix)
// Zig-Zag掃描
zigzag := zigzagScan(quantized)
// 這裏可以繼續進行熵編碼處理
// 為簡化起見，直接返回量化後的係數
return quantized
}
func dct2D(image [][]float64) [][]float64 {
N := len(image)
M := len(image[0])
output := make([][]float64, N)
for i := range output {
output[i] = make([]float64, M)
}
// 對每一行進行一維DCT
for i := 0; i < N; i++ {
output[i] = dct(image[i])
}
// 對每一列進行一維DCT
for j := 0; j < M; j++ {
var column []float64
for i := 0; i < N; i++ {
column = append(column, output[i][j])
}
columnDCT := dct(column)
for i := 0; i < N; i++ {
output[i][j] = columnDCT[i]
}
}
return output
}
func quantize(dctCoeff [][]float64, quantMatrix [][]float64) [][]int {
N := len(dctCoeff)
M := len(dctCoeff[0])
quantized := make([][]int, N)
for i := range quantized {
quantized[i] = make([]int, M)
}
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
quantized[i][j] = int(math.Round(dctCoeff[i][j] / float64(quantMatrix[i][j])))
}
}
return quantized
}
func zigzagScan(matrix [][]int) []int {
order := [][2]int{
{0,0}, {0,1}, {1,0}, {2,0}, {1,1}, {0,2}, {0,3}, {1,2},
{2,1}, {3,0}, {4,0}, {3,1}, {2,2}, {1,3}, {0,4}, {0,5},
{1,4}, {2,3}, {3,2}, {4,1}, {5,0}, {6,0}, {5,1}, {4,2},
{3,3}, {2,4}, {1,5}, {0,6}, {0,7}, {1,6}, {2,5}, {3,4},
{4,3}, {5,2}, {6,1}, {7,0}, {7,1}, {6,2}, {5,3}, {4,4},
{3,5}, {2,6}, {1,7}, {2,7}, {3,6}, {4,5}, {5,4}, {6,3},
{7,2}, {7,3}, {6,4}, {5,5}, {4,6}, {3,7}, {4,7}, {5,6},
{6,5}, {7,4}, {7,5}, {6,6}, {5,7}, {6,7}, {7,6}, {7,7},
}
result := make([]int, 64)
for i := 0; i < 64; i++ {
x, y := order[i][0], order[i][1]
result[i] = matrix[x][y]
}
return result
}
func main() {
// 假設輸入是一個8x8的灰度圖像塊
image := [][]float64{
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
{10, 10, 10, 10, 10, 10, 10, 10},
}
// 標準亮度量化矩陣
quantMatrix := [][]float64{
{16, 11, 10, 16, 24, 40, 51, 61},
{12, 12, 14, 19, 26, 58, 60, 55},
{14, 13, 16, 24, 40, 57, 69, 56},
{14, 17, 22, 29, 51, 87, 80, 62},
{18, 22, 37, 56, 68, 109, 103, 77},
{24, 35, 55, 64, 81, 104, 113, 92},
{49, 64, 78, 87, 103, 121, 120, 101},
{72, 92, 95, 98, 112, 100, 103, 99},
}
compressed := jpegCompress(image, quantMatrix)
fmt.Println("Compressed coefficients:")
for _, row := range compressed {
fmt.Println(row)
}
}3. MP3 音頻壓縮算法
數學原理
MP3 (MPEG-1 Audio Layer 3) 是一種廣泛應用的有損音頻壓縮標準，它利用人類聽覺系統的感知特性，通過丟棄不可感知的音頻信息來實現高壓縮比。
MP3 的數學原理可以通過以下步驟描述：
- 感知音頻編碼：基於心理聲學模型，分析音頻信號的掩蔽效應，確定哪些頻率成分可以安全地丟棄
- 混合濾波器組：將音頻信號分解為多個子帶，通常為 32 個子帶，每個子帶覆蓋不同的頻率範圍
- 修正的離散餘弦變換 (MDCT)：對每個子帶應用 MDCT，將時域信號轉換為頻域表示
- 量化和編碼：根據心理聲學模型確定的掩蔽閾值，對 MDCT 係數進行量化和編碼
MP3 編碼的核心數學變換是修正的離散餘弦變換 (MDCT)，其數學公式為：
\( MDCT[k] = \sqrt{\frac{2}{N}} \sum_{n=0}^{N-1} x[n] \cos\left(\frac{\pi}{N} \left(n + \frac{N}{4} + 0.5\right) \left(k + \frac{1}{2}\right)\right) \)
其中 N 是變換塊的大小，通常為 1024 或 512。
MP3 的逆過程，即解碼，通過逆 MDCT 和濾波器組重建時域音頻信號。
Golang 實現
由於 MP3 算法較為複雜，這裏僅提供 MDCT 部分的簡化實現：
package main
import (
"fmt"
"math"
)
func mdct(input []float64) []float64 {
N := len(input)
output := make([]float64, N/2)
for k := 0; k < N/2; k++ {
sum := 0.0
for n := 0; n < N; n++ {
angle := math.Pi * float64(n + N/4 + 0.5) * float64(k + 0.5) / float64(N)
sum += input[n] * math.Cos(angle)
}
output[k] = math.Sqrt(2.0/float64(N)) * sum
}
return output
}
func main() {
// 假設輸入是一個長度為1024的音頻樣本塊
input := make([]float64, 1024)
for i := range input {
input[i] = math.Sin(2 * math.Pi * float64(i) * 440.0 / 44100.0)
}
mdctResult := mdct(input)
fmt.Println("MDCT coefficients length:", len(mdctResult))
}五.現代壓縮算法進展
基於深度學習的壓縮算法
近年來，基於深度學習的壓縮算法取得了顯著進展，特別是在圖像和視頻壓縮領域。這些算法通常基於自編碼器架構，通過神經網絡學習數據的高效表示。
2025 年的研究表明，基於 Transformer 的對稱 Transformer 模型 (STF) 在無損圖像壓縮方面取得了顯著成果，其壓縮效率超過了傳統方法如 IVPF、Gollic 和 MSPSM。該模型結合了以下創新點：
- 對稱 Transformer 架構：在編碼器和解碼器中都使用 Transformer 塊，增強對局部和全局特徵的捕獲能力
- 多變量混合分佈通道條件 (MMCC) 熵模型：通過建模圖像通道間的複雜關係提高像素依賴預測的準確性
- 自動搜索最優核形狀 (SOKS)：動態配置卷積層的核大小，優化不同圖像區域的處理
- 條帶剪枝 (SWP)：在壓縮過程中有選擇地剪枝不重要的特徵，降低計算複雜度和內存使用
這些技術的組合在標準數據集上實現了顯著的壓縮效率提升，例如在 Kodak 數據集上達到 3.06 bpd (每維度比特數)，相比傳統方法有明顯優勢。
語義壓縮新範式
2025 年提出的 "理解即壓縮" 理論開創了壓縮技術的新範式。該理論認為，一個能夠 "理解" 各種文件、照片、音頻、視頻的大模型，必然藴含強大的壓縮能力。這一理論通過實驗得到了驗證：
- 大模型預測：大模型預測下一個 token 的概率分佈
- 算術編碼：基於這些概率分佈，使用算術編碼進行無損壓縮和解壓
這種方法被稱為 LMCompress，它對大模型幾乎沒有限制，只要是自迴歸生成式大模型，都可以 "即插即用"。實驗結果表明，LMCompress 在四種媒體類型 (文本、圖像、視頻和音頻) 上都表現出了壓倒性的優勢，比最優傳統無損壓縮的效率提升 2 倍以上。
六.總結
這次我們淺層瞭解了多種經典的無損和有損壓縮算法的數學原理，並提供了 Golang 語言的函數實現示例。
通過理解這些壓縮算法的數學原理和實現方式，我們可以更好地選擇和應用適合特定場景的壓縮技術，優化數據存儲和傳輸效率。同時，本文提供的 Golang 實現代碼可以作為進一步學習和開發的基礎，幫助讀者構建自己的壓縮應用。
——By 愚人貓(Idiomeo)
2025.8.27
博客原文
