> tunstall | 变长 | 定长 <
// Tunstall 编码——变长到定长的最优压缩
0 字符
0 字符
[变长→定长]
V2F 编码
将变长符号序列映射为定长二进制码字。
[最优]
基于概率
根据符号概率分布构建最优字典。
[易于解码]
解码简单
定长码字使解码逻辑简单、实现高效。
>> 技术细节
Tunstall 编码的工作原理:
Tunstall 编码首先从单字符开始构建字典，将变长符号序列映射到定长二进制码字。算法每一步选出当前概率最高的序列，用在其末尾拼接字符集中的所有符号来扩展字典，从而得到一个变长到定长的最优码，其中更高概率的序列拥有独立的码字。
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 编码？:
- ▸输出为固定长度码字，便于传输和缓冲
- ▸解码算法简单、易于在嵌入式或硬件中实现
- ▸没有前缀码那样的同步问题
- ▸适合语音、图像等需要稳定码率的场景
- ▸对无记忆信源在理论上是最优的变量到定长编码方案之一
>> 常见问题
什么是 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 编码常用于语音压缩、图像编码以及需要固定输出速率的自适应系统。对需要硬实时和流水线处理的硬件实现尤其友好。