文档介绍：会计学
1
算术编码的基本思想
回顾：扩展的Huffman编码
基本思想：
考虑对两个字母序列而不是单个字母编码
Letter
Probability
Code
aa
0
ab
111
ac
100
ba
1101
bb
110011
bc
110001
ca
101
cb
110010
cc
110000
l = =
冗余 = bits/symbol
（27%）
第2页/共65页
回顾：扩展的Huffman编码
该思想还可以继续扩展
考虑长度为n的所有可能的mn 序列 (已做了32)
理论上：考虑更长的序列能提高编码性能
实际上：
字母表的指数增长将使得这不现实
例如：对长度为3的ASCII序列：2563 = 224 = 16M
需要对长度为n的所有序列产生码本
很多序列的概率可能为0
分布严重不对称是真正的大问题：
A = {a, b, c}, P(a) = , P(b) = , P(c) =
H = bits/symbol
l1 = , l2 = , …
当n = 8时编码性能才变得可接受
但此时|alphabet| = 38 = 6561 !!!
第3页/共65页
算术编码（Arithmetic Coding）
算术编码：从另一种角度对很长的信源符号序列进行有效编码
对整个序列信源符号串产生一个唯一的标识（ tag ）
直接对序列进行编码（不是码字的串联）：非分组码
不用对该长度所有可能的序列编码
标识是[0,1)之间的一个数（二进制小数，可作为序列的二进制编码）
第4页/共65页
概率复****br/>随机变量：
将试验的输出映射到实数
用数字代替符号
X(ai) = i, 其中 ai A (A = {ai}, i = 1..n)
给定信源的概率模型P
概率密度函数（probability density function, pdf）
累积密度函数（cumulative density function, cdf）
第5页/共65页
产生标识
定义一一映射：
ak [FX(k-1), FX(k)], k = 1..m, FX(0) = 0
[FX(k-1), FX(k)]区间内的任何数字表示 ak
对2字母序列ak aj编码
对ak ，选择[FX(k-1), FX(k)]
然后将该区间按比例分割并选取第j个区间：
将[0, 1)分为m个区间：
第6页/共65页
产生标识：例
考虑对a1a2a3编码：
A = {a1, a2, a3}, P = {, , )
映射：a1 1, a2 2, a3 3
cdf: FX(1) = , FX(2) = , FX(3) = 1 .0
第7页/共65页
映射成实数
A = {a1, a2, …, am}
对公平掷骰子的例子：{1, 2, 3, 4, 5, 6}
第8页/共65页
词典顺序（ Lexicographic order ）
字符串的词典顺序：
其中 表示“在字母顺序中，y在x的前面”
n 为序列的长度
第9页/共65页
词典顺序：例
考虑两轮连续的骰子：
输出 = {11, 12, …, 16, 21, 22, …, 26, …, 61, 62, …, 66}
注意：
为了产生13的标识，我们不必对产生其他标识
但是，为了产生长度为n的字符串的标识，我们必须知道比其短的字符串的概率
这与产生所有的码字一样繁重！
应该想办法来避免此事
第10页/共65页