---

## 一、Huffman 編碼

**Huffman 編碼**是一種無損數據壓縮技術，通過分配變長的前綴碼來表示不同的符號，從而根據符號的出現頻率實現壓縮。頻率較高的符號分配較短的碼，頻率較低的符號分配較長的碼。

### 流程步驟：

1. **計算符號頻率**：
- 分析待編碼數據，統計每個符號出現的次數或概率。
- 例如，對字符串 `"ABBCCC"` 進行頻率統計：
- A: 1 次
- B: 2 次
- C: 3 次

2. **建立優先隊列（最小堆）**：
- 將所有符號作為節點，根據頻率從小到大排列，形成優先隊列。
- 使用最小堆結構以便於每次取出頻率最低的兩個節點。

3. **構建 Huffman 樹**：
- 當隊列中節點數量大於1時，重複以下步驟：
- 從隊列中取出兩個頻率最低的節點。
- 創建一個新的內部節點，其頻率為這兩個節點頻率之和，並將這兩個節點作為新節點的左右子節點。
- 將新節點插回隊列中。
- 重複此過程，直到只剩下一個節點，該節點即為 Huffman 樹的根節點。

4. **生成編碼**：
- 從根節點開始，左分支標記為 '0'，右分支標記為 '1'，遍歷整棵樹，為每個葉子節點（即原始符號）分配一個唯一的二進制碼。

### 詳細範例：

假設有五個符號及其頻率：

| 符號 | 頻率 |
|------|------|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |

#### 步驟 1：初始化優先隊列

A(5), B(9), C(12), D(13), E(16), F(45)

#### 步驟 2：構建 Huffman 樹

1. 合併 A(5) 和 B(9) → AB(14)
2. 合併 AB(14) 和 C(12) → ABC(26)
3. 合併 D(13) 和 E(16) → DE(29)
4. 合併 ABC(26) 和 DE(29) → ABCDE(55)
5. 合併 ABCDE(55) 和 F(45) → ABCDEF(100)

#### 步驟 3：生成編碼

graph TD
    ABCDEF["ABCDE (100)"]
    ABCDE["ABCDE (55)"]
    F["F (45)"]
    ABC["ABC (26)"]
    DE["DE (29)"]
    AB["AB (14)"]
    C["C (12)"]
    D["D (13)"]
    E["E (16)"]
    A["A (5)"]
    B["B (9)"]

    ABCDEF --> ABCDE
    ABCDEF --> F
    ABCDE --> ABC
    ABCDE --> DE
    ABC --> AB
    ABC --> C
    DE --> D
    DE --> E
    AB --> A
    AB --> B

#### 步驟 4：分配編碼

- 從根節點開始：
- 左分支標記為 '0'，右分支標記為 '1'

| 符號 | 編碼 |
|------|-------|
| F | 1 |
| A | 000 |
| B | 001 |
| C | 01 |
| D | 100 |
| E | 101 |

### 解碼過程：

給定編碼 `00000101100101`：

1. **000** → A
2. **001** → B
3. **01** → C
4. **100** → D
5. **101** → E

解碼結果：`ABCDE`

### Huffman 編碼的優點與缺點：

**優點**：
- **最優性**：在符號獨立且符號頻率已知的情況下，Huffman 編碼是最優的前綴碼編碼。
- **效率高**：能有效減少平均編碼長度，特別是當符號頻率差異較大時。

**缺點**：
- **靜態性**：需要在編碼前預先知道符號的頻率，對於動態或未知頻率的數據不適用。
- **不適合連續符號依賴**：不考慮符號之間的依賴關係。

### Huffman 編碼的應用場景：

- **壓縮文件格式**：如 ZIP、JPEG 等。
- **通信協議**：在帶寬受限的環境中減少數據傳輸量。

---

## 二、自適應 Huffman 編碼

**自適應 Huffman 編碼**（Adaptive Huffman Coding）是一種動態調整 Huffman 樹的編碼方法，適用於流式數據或無法預先獲取符號頻率的情況。它在編碼過程中即時更新樹結構，以適應符號頻率的變化。

### 流程步驟：

1. **初始化**：
- 建立一個特殊的「尚未傳輸」節點（NYT，Not Yet Transmitted），代表尚未出現的符號。
- 初始時，樹只有一個 NYT 節點。

2. **逐符號處理**：
- 對於每個輸入符號，進行以下處理：
- **新符號**：
- 發送 NYT 節點的當前編碼，然後發送符號的固定長度二進制表示（例如，8 位）。
- 將新符號加入 Huffman 樹中，並更新樹結構。
- **已出現符號**：
- 發送該符號當前在 Huffman 樹中的編碼。
- 增加該符號的頻率，並根據需要調整樹結構以保持 Huffman 樹的屬性。

3. **更新樹結構**：
- 使用特定的算法（如 FGK 或 Vitter 算法）來更新樹，使得頻率增加的符號移動到更高的節點，維持樹的最優性。

### FGK 算法示意：

**FGK（Faller-Gallager-Knuth）算法**是自適應 Huffman 編碼中常用的更新算法。其主要步驟包括：

1. **尋找節點**：
- 對於當前符號，找到其在樹中的節點。
- 如果是新符號，則創建新的節點並插入。

2. **交換節點**：
- 為了維持樹的順序性，可能需要交換節點的位置。
- 確保每個節點的權重（頻率）滿足從上到下、從左到右的順序。

3. **增量更新**：
- 增加該符號的頻率。
- 遍歷從葉節點到根節點的路徑，更新每個節點的頻率並調整樹結構。

### 詳細範例：

考慮輸入序列 `"ABACA"`，逐步構建自適應 Huffman 樹。

#### 步驟 1：初始化

- 樹僅有 NYT 節點。

#### 步驟 2：處理第一個符號 'A'

- **新符號**：
- 發送 NYT 的編碼（空碼） + 'A' 的固定編碼（假設 8 位）`01000001`。
- 更新樹：NYT → A 和新的 NYT。

graph TD
    Root["Root"]
    NYT1["NYT"]
    A["A (1)"]

    Root --> A
    Root --> NYT1

#### 處理第二個符號 'B'

- **新符號**：
- 發送 NYT1 的編碼 `1` + 'B' 的固定編碼 `01000010`。
- 更新樹：Root → A 和 B，然後再添加 NYT。

graph TD
    Root["Root"]
    A["A (1)"]
    B["B (1)"]
    NYT2["NYT"]

    Root --> A
    Root --> B
    B --> NYT2

#### 處理第三個符號 'A'

- **已出現符號**：
- 發送 'A' 的編碼 `0`。
- 增加 'A' 的頻率至 2。
- 更新樹結構，使 'A' 位於更高的位置。

graph TD
    Root["Root"]
    A["A (2)"]
    B["B (1)"]
    NYT2["NYT"]

    Root --> A
    Root --> B
    B --> NYT2

#### 處理第四個符號 'C'

- **新符號**：
- 發送 NYT2 的編碼 `11` + 'C' 的固定編碼 `01000011`。
- 更新樹：插入 'C' 並調整頻率。

graph TD
    Root["Root"]
    A["A (2)"]
    B["B (1)"]
    C["C (1)"]
    NYT3["NYT"]

    Root --> A
    Root --> B
    B --> C
    B --> NYT3

#### 處理第五個符號 'A'

- **已出現符號**：
- 發送 'A' 的編碼 `0`。
- 增加 'A' 的頻率至 3。
- 更新樹結構。

graph TD
    Root["Root"]
    A["A (3)"]
    B["B (1)"]
    C["C (1)"]
    NYT3["NYT"]

    Root --> A
    Root --> B
    B --> C
    B --> NYT3

### 自適應 Huffman 編碼的優點與缺點：

**優點**：
- **適應性強**：不需要事先知道符號頻率，適用於動態數據。
- **即時壓縮**：適合流式數據壓縮，如實時傳輸。

**缺點**：
- **計算複雜度高**：每處理一個符號都需要更新樹結構，增加了計算負擔。
- **初始階段壓縮效率低**：由於頻率信息不足，初始壓縮效率可能較低。

### 自適應 Huffman 編碼的應用場景：

- **實時數據壓縮**：如視頻流、音頻流。
- **無法預測數據頻率的情況**：如加密通信。

### 進階圖示：自適應 Huffman 編碼的動態更新

graph TD
    Root1["Root"]
    NYT1["NYT"]

    Root1 --> NYT1

    %% 插入A
    Root2["Root"]
    A1["A (1)"]
    NYT2["NYT"]

    Root2 --> A1
    Root2 --> NYT2

    %% 插入B
    Root3["Root"]
    A1["A (1)"]
    B1["B (1)"]
    NYT3["NYT"]

    Root3 --> A1
    Root3 --> B1
    B1 --> NYT3

    %% 更新A frequency
    Root4["Root"]
    A2["A (2)"]
    B1["B (1)"]
    NYT3["NYT"]

    Root4 --> A2
    Root4 --> B1
    B1 --> NYT3

    %% 插入C
    Root5["Root"]
    A2["A (2)"]
    B1["B (1)"]
    C1["C (1)"]
    NYT4["NYT"]

    Root5 --> A2
    Root5 --> B1
    B1 --> C1
    B1 --> NYT4

    %% 更新A frequency
    Root6["Root"]
    A3["A (3)"]
    B1["B (1)"]
    C1["C (1)"]
    NYT4["NYT"]

    Root6 --> A3
    Root6 --> B1
    B1 --> C1
    B1 --> NYT4

---

## 三、Tunstall 編碼

**Tunstall 編碼**是一種將變長符號序列（短語）映射到固定長度二進制碼的編碼方法。與 Huffman 編碼不同，Tunstall 編碼將變長的短語編碼為固定長度的碼，這在某些應用場景中具有優勢，如需要固定碼長的硬件實現。

### 流程步驟：

1. **初始化**：
- 建立一個單一的根節點，代表空字符串。

2. **生成短語樹**：
- 持續擴展樹，將最不可能的葉節點擴展為其所有可能的子節點，根據符號的概率進行分支。
- 這一過程持續進行，直到達到所需的固定碼長，即生成的短語數量等於 \(2^n\)，其中 \(n\) 是固定碼長。

3. **分配固定長碼**：
- 為每個生成的短語分配一個唯一的固定長度二進制碼。

4. **編碼與解碼**：
- **編碼**：將輸入數據分割為預先定義的短語，然後用對應的固定長碼替換。
- **解碼**：將固定長碼轉換回相應的短語，並重組為原始數據。

### 詳細範例：

假設符號集為 {A, B, C}，並假設每個符號的概率為：

| 符號 | 機率 |
|------|-------|
| A | 0.5 |
| B | 0.3 |
| C | 0.2 |

選擇固定碼長 \(n = 2\)，即需要 \(2^2 = 4\) 個短語。

#### 步驟 1：初始化

- 根節點為空字符串 `""`。

#### 步驟 2：生成短語樹

1. 將根節點展開，生成所有可能的第一級短語：
- A
- B
- C

2. 根據機率選擇最不可能的短語進行擴展，直到生成 4 個短語：
- 展開 C（機率最低 0.2），生成 CA 和 CB
- 現在短語集為：A, B, CA, CB

#### 步驟 3：分配固定長碼

| 短語 | 固定長碼 |
|------|----------|
| A | 00 |
| B | 01 |
| CA | 10 |
| CB | 11 |

#### 步驟 4：編碼與解碼

**編碼示例**：

輸入序列 `"ACAABCB"` 分割為短語：
- "A", "C", "AA", "B", "CB"

由於 "AA" 不在短語集中，需進一步調整或重新定義短語集。為了保持固定碼長，通常需要更大的短語集或更高的固定碼長。

**調整後的短語集**（假設 \(n = 3\)，需 \(2^3 = 8\) 個短語）：

1. A, B, C
2. 展開最不可能的 C → CA, CB
3. 展開 CA → CAA, CAB
4. 展開 CB → CBA, CBB

最終短語集：A, B, CAA, CAB, CBA, CBB, CA, CB

**分配固定長碼**：

| 短語 | 固定長碼 |
|------|----------|
| A | 000 |
| B | 001 |
| CA | 010 |
| CB | 011 |
| CAA | 100 |
| CAB | 101 |
| CBA | 110 |
| CBB | 111 |

**編碼示例**：

輸入 `"ACAABCB"` 分割為：
- "A", "C", "A", "A", "B", "C", "B"

根據短語集，可分割為：
- "A", "CA", "A", "B", "CB"

對應編碼為：
- "000", "010", "000", "001", "011"

最終編碼：`000 010 000 001 011`

### Tunstall 編碼的優點與缺點：

**優點**：
- **固定碼長**：所有短語的編碼長度相同，便於硬件實現和並行處理。
- **高壓縮效率**：通過使用變長短語，可以有效地壓縮具有高頻率短語的數據。

**缺點**：
- **靜態性**：需要在編碼前預先分析符號的頻率，並生成短語樹。
- **短語生成複雜度高**：生成短語樹可能較為複雜，特別是符號集較大時。

### Tunstall 編碼的應用場景：

- **硬件實現**：需要固定碼長的場景，如某些通信協議中的硬件編碼器。
- **並行處理**：固定碼長便於並行處理，提高編碼和解碼速度。

### 進階圖示：Tunstall 編碼的短語樹

graph TD
    Root[""]
    A["A (0.5)"]
    B["B (0.3)"]
    C["C (0.2)"]

    Root --> A
    Root --> B
    Root --> C

    C --> CA["CA (0.2)"]
    C --> CB["CB (0.2)"]

    CA --> CAA["CAA (0.2)"]
    CA --> CAB["CAB (0.2)"]

    CB --> CBA["CBA (0.2)"]
    CB --> CBB["CBB (0.2)"]

---

## 四、Golomb 編碼

**Golomb 編碼**是一種無損編碼方法，特別適用於服從幾何分布或類似稀疏分布的整數。它通過將整數分為商和餘數兩部分來實現高效編碼，特別適合於編碼運行長度或具有重複模式的數據。

### 流程步驟：

1. **選擇參數 \(m\)**：
- 根據數據的分布特性選擇適當的參數 \(m\)。
- \(m\) 通常是正整數，決定了編碼的分割方式。
- 對於幾何分布，最佳 \(m\) 能夠最小化平均編碼長度。

2. **編碼每個整數 \(k\)**：
- 對於每個待編碼的正整數 \(k\)：
- 計算商 \(q = \lfloor k / m \rfloor\)。
- 計算餘數 \(r = k \mod m\)。
- 編碼方式：
- **商 \(q\)**：使用 \(q\) 個 '1'，後接一個 '0' 作為分隔符。
- **餘數 \(r\)**：
- 如果 \(m\) 是 \(2^n\)，則使用固定長度的 \(n\) 位二進制表示。
- 如果 \(m\) 不是 \(2^n\)，則使用更複雜的餘數編碼方法，如使用不等長度的碼或擴展碼來保持唯一性。

3. **組合編碼**：
- 將商的編碼與餘數的編碼連接起來，形成最終的 Golomb 編碼。

### 詳細範例：

假設選擇 \(m = 3\)，編碼數字 \(k = 7\)：

1. **計算商和餘數**：
- \(q = \lfloor 7 / 3 \rfloor = 2\)
- \(r = 7 \mod 3 = 1\)

2. **編碼商 \(q = 2\)**：
- 使用兩個 '1'，後接一個 '0' → `'110'`

3. **編碼餘數 \(r = 1\)**：
- 由於 \(m = 3\) 不是 \(2^n\)，需要使用更複雜的餘數編碼。
- Golomb 編碼通常採用對 \(r\) 進行分段編碼，確保唯一性。
- 例如，餘數 \(r\) 的編碼可以使用如下方式：
- 當 \(m\) 不是 \(2^n\) 時，可以使用“截斷法”：
- 計算 \(k = \lceil \log_2 m \rceil = 2\) 位。
- 如果 \(r < m - 2^k\), 使用 \(k\) 位表示。
- 否則，重新編碼餘數。
- 具體實現視需求而定。

4. **最終編碼**：
- 商的編碼 `'110'` + 餘數的編碼 `'01'`（假設使用 2 位表示） → `'11001'`

### Golomb 編碼的優點與缺點：

**優點**：
- **高效性**：對於幾何分布或類似稀疏分布的數據，Golomb 編碼具有較高的壓縮效率。
- **參數靈活**：通過調整參數 \(m\)，可適應不同的數據分布。

**缺點**：
- **靜態性**：需要事先了解數據的分布特性以選擇合適的 \(m\)。
- **實現複雜度**：當 \(m\) 不是 \(2^n\) 時，餘數編碼變得複雜。

### Golomb 編碼的應用場景：

- **運行長度編碼**：如圖像壓縮中的連續相同像素值編碼。
- **無線通信**：特別是在數據稀疏的情況下，如稀疏信號壓縮。

### 進階範例：不同 \(m\) 值的 Golomb 編碼

#### 範例 1：\(m = 2\)（Rice 編碼）

當 \(m = 2\) 時，Golomb 編碼稱為 **Rice 編碼**，其餘數編碼簡單為固定長度。

**編碼數字 \(k = 5\)**：

1. **計算商和餘數**：
- \(q = \lfloor 5 / 2 \rfloor = 2\)
- \(r = 5 \mod 2 = 1\)

2. **編碼商 \(q = 2\)**：
- `'11'`（兩個 '1'） + `'0'` → `'110'`

3. **編碼餘數 \(r = 1\)**：
- 1 位二進制表示 → `'1'`

4. **最終編碼**：
- `'110' + '1'` → `'1101'`

#### 範例 2：\(m = 4\)

**編碼數字 \(k = 6\)**：

1. **計算商和餘數**：
- \(q = \lfloor 6 / 4 \rfloor = 1\)
- \(r = 6 \mod 4 = 2\)

2. **編碼商 \(q = 1\)**：
- `'1'`（一個 '1'） + `'0'` → `'10'`

3. **編碼餘數 \(r = 2\)**：
- \(m = 4\) 是 \(2^2\)，使用 2 位二進制表示 → `'10'`

4. **最終編碼**：
- `'10' + '10'` → `'1010'`

### Golomb 編碼的實現考量：

- **選擇最佳 \(m\)**：
- \(m\) 的選擇對壓縮效率至關重要。通常，根據數據的平均值和分布選擇 \(m\)。
- 常見方法包括使用最大似然估計來選擇最佳 \(m\)。

- **餘數編碼策略**：
- 當 \(m\) 不是 \(2^n\) 時，需要使用更複雜的餘數編碼方法，如截斷法或擴展碼法，以確保餘數的唯一性和最小化編碼長度。

### Golomb 編碼的應用實例：

考慮一個無線通信系統，其中大多數數據包的長度較短（稀疏分布）。使用 Golomb 編碼可以高效地壓縮這些數據包長度，減少傳輸所需的位數。

---

## 五、差異化總結

以下表格總結了 **Huffman 編碼**、**自適應 Huffman 編碼**、**Tunstall 編碼** 及 **Golomb 編碼** 的主要特性與差異：

| **特性** | **Huffman 編碼** | **自適應 Huffman 編碼** | **Tunstall 編碼** | **Golomb 編碼** |
|------------------------|--------------------------------|-----------------------------------|----------------------------------|----------------------------------|
| **編碼類型** | 變長前綴碼 | 變長前綴碼 | 變長短語到固定長碼 | 整數的無損編碼 |
| **靜態 vs 動態** | 靜態（需預先統計頻率） | 動態（即時更新樹結構） | 靜態（根據頻率生成短語） | 靜態（根據分布選參數 \(m\)） |
| **適用數據類型** | 一般符號集 | 流式數據或頻率未知的數據 | 需要固定碼長的應用場景 | 幾何分布或稀疏分布的整數 |
| **壓縮效率** | 高，基於最佳前綴碼理論 | 隨數據量增大而提升 | 在固定碼長需求下效率高 | 對特定分布數據效率高 |
| **實現複雜度** | 相對簡單 | 較高，需頻繁更新樹結構 | 中等，需生成短語樹 | 較低，主要依賴參數選擇 |
| **延遲性** | 無 | 可能有初始壓縮效率低的延遲 | 無，編碼固定碼長 | 無 |
| **靈活性** | 需要預先統計 | 高，適應不同數據流 | 受限於固定碼長 | 高，通過參數 \(m\) 調整 |
| **最佳應用場景** | 文件壓縮、通信協議 | 實時數據壓縮、動態頻率數據 | 硬件實現、並行處理 | 運行長度編碼、無線通信 |

### 主要差異：

1. **編碼方式**：
- **Huffman** 和 **自適應 Huffman** 都是基於頻率的變長前綴碼，但後者能動態調整。
- **Tunstall** 則是將變長的短語映射到固定長的碼，適用於需要固定碼長的應用場景。
- **Golomb** 主要針對特定分布的整數進行高效編碼，特別適合稀疏數據或運行長度編碼。

2. **靜態 vs 動態**：
- **Huffman** 和 **Tunstall** 是靜態編碼，需要預先分析數據。
- **自適應 Huffman** 和 **Golomb** 可以根據數據實時調整或選擇參數（Golomb 的 \(m\) 雖然是靜態的，但能根據數據分布靈活選擇）。

3. **應用場景**：
- **Huffman** 適用於大多數一般數據壓縮，如文件壓縮和通信協議。
- **自適應 Huffman** 適用於流式或未知頻率的數據，如實時傳輸和加密通信。
- **Tunstall** 適用於需要固定碼長的應用，如某些硬件實現和並行處理。
- **Golomb** 適用於具有幾何分布或類似稀疏分布的數據，如運行長度編碼和無線通信。

4. **壓縮效率與實現複雜度**：
- **Huffman** 通常具有較高的壓縮效率，實現較為簡單。
- **自適應 Huffman** 提供靈活性但增加了實現複雜度。
- **Tunstall** 在固定碼長需求下效率高，但生成短語樹較為複雜。
- **Golomb** 對特定數據分布效率極高，實現相對簡單，特別是當 \(m\) 為 \(2^n\) 時。

### 總結：

這四種編碼方法各有優缺點，適用於不同的應用場景和數據類型。選擇合適的編碼方法需根據具體需求、數據特性以及實現的複雜度進行權衡：

- **Huffman 編碼** 是通用的無損壓縮方法，適合大多數需要高壓縮效率的場景。
- **自適應 Huffman 編碼** 適合於數據流或頻率未知的動態環境，提供即時壓縮能力。
- **Tunstall 編碼** 適合於需要固定碼長的應用，如硬件實現和並行處理環境。
- **Golomb 編碼** 在處理幾何分布或稀疏分布數據時表現最佳，適用於運行長度編碼和無線通信等場景。