> tunstall | 變長 | 定長 <
// Tunstall 編碼——由變長至定長的最佳壓縮
0 字元
0 字元
[變長→定長]
V2F 編碼
將變長符號序列對應到固定長度的二進位碼字。
[最佳化]
機率驅動
依據符號機率分佈建立最適化字典。
[易於解碼]
簡單解碼流程
固定長度碼字讓解碼流程簡單、容易實作。
>> 技術細節
Tunstall 編碼原理:
Tunstall 編碼從單一符號開始建立字典，將變長符號序列映射到固定長度的二進位碼字。演算法每一步會找到目前機率最高的序列，將其從字典移除，再把該序列與字母表中所有符號做一次延伸，加入新的條目，如此反覆直到字典大小達到目標（n 位元碼對應 2^n 個碼字）。
Tunstall 編碼範例:
文字："aabaa"，其中 P(a)=0.8，P(b)=0.2 字典建立（3 位元碼）： 初始：a, b 展開「a」：aa, ab 展開「aa」：aaa, aab 展開「ab」：aba, abb 最終字典（8 個碼字）： aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 編碼：「aabaa」→ 001 100（aab + aa）
為什麼要使用 Tunstall 編碼？:
- ▸輸出為固定長度碼字，利於串流與緩衝控制
- ▸解碼邏輯簡單，適合硬體實作與嵌入式系統
- ▸不易出現前綴碼的同步問題
- ▸常用於語音壓縮、影像編碼等需固定碼率的場景
- ▸對無記憶（memoryless）來源可達到理論上接近最優的效能
>> 常見問題
什麼是 Tunstall 編碼？
Tunstall 編碼是一種「變長輸入、定長輸出」的熵編碼方式。不同於 Huffman（定長輸入、變長輸出），Tunstall 會將變長來源序列映射為固定長度碼字，非常適合需要固定位元率的通訊與儲存系統。
Tunstall 和 Huffman 有何差異？
Huffman：固定長度輸入 → 變長輸出（例如「a」→「0」，「b」→「10」）；Tunstall：變長輸入 → 固定長度輸出（例如「aa」→「000」，「ab」→「001」）。Tunstall 在硬體實作與同步控制上較有優勢，但壓縮率通常略低於 Huffman。
Tunstall 字典是如何建立的？
從單一符號開始，反覆進行：1）找出目前機率最高的序列；2）將該序列自字典移除；3）將此序列與所有可能的一個符號延伸後加入字典；4）直到字典大小達到目標（n 位元碼約對應 2^n 個條目）。
Tunstall 編碼通常用在什麼場合？
Tunstall 編碼常見於語音壓縮、影像與多媒體編碼，以及各種需要定長輸出的即時系統，特別適合以硬體或 FPGA 實作的編碼器。