文档介绍：第8章 数据压缩技术基础
第一页，共45页。
第8章 数据压缩技术基础
数据压缩（data compression）是一种在保持传输帧原意的基础上减少传输比特数的技术，它对于降低传输费用、减少数据发送时间、提高信道有效数的二进制表示。
算术压缩算法的过程是逐步产生长度递减的子区间，每一次所产生的子区间由当前字符以及它们的频率唯一确定。字符串中字符越多，对应的子区间越小。当处理完最后一个字符后，字符串与一个子区间对应，该子区间中任意一个实数（例如中点）表示相应的字符串。
第六页，共45页。
算术压缩算法的基本思想描述如下：
1）按照各字符出现的频率将区间[x，y]=[0，1] 划分成若干子区间；
2）查看当前字符，根据它的频率确定对应的子区间[p，q]；
3）对区间[x，y]重新定义，缩小[x，y]。即：
新x值＝现在x值＋w×p 新y值＝现在x值＋w×q
其中 w ＝ y－x 表示区间[x，y]的宽度；
4）查看下一字符，根据其频率再次决定[x，y]的正确子区间；
5）对字符串中的每一字符重复第2步～第4步。
例如，假定字符串CABACADA…中各字符的频率如表8-2所示：
字符
频率（％）
子区间[p，q]
A
25
[0，]
B
15
[，]
C
10
[，]
D
20
[，]
E
30
[，]
第七页，共45页。
字符串CABA……的压缩码计算过程如下：初始时x=0，y=1，w=1
p=
q=
x=0
y=1
确定C的子区间
确定A的子区间
确定B的子区间
x=x+w×p=0+1×=
y=x+w×q=0+1×=
x=x+w×p=+×0=
y=x+w×q=+×=
确定A的子区间
p=0
q=
w=
p=
q=
w=
x=x+w×p=+×=
x=x+w×p=+×=
w=
p=0
q=
第八页，共45页。
表8-3 字符串CABA……算术编码的步骤
步骤
1
2
3
4
5
字符串
－
C
CA
CAB
CABA
下一字符
C
A
B
A
C
目前区间
[x, y]
[0, 1]
[, ]
[, ]
[, ]
[,
]
[p，q]
[, ]
[0, ]
[, ]
[0, ]
[, ]
区间长度
w=y-x
计算新x
x=x+w×p
0+1×
=
+×0
=
+×
=
+
×0
=
+
×
=
计算新y
y=x+w×q
0+1×
=
+×
=
+×
=
+
×
=
+
×
=
由上表可知，字符串“CABAC…”落在区间[， ]中，换言之，该区间任一实数均可表示该字符串。
第九页，共45页。
现在的问题是：从一个已知的实数，如何对上述过程进行逆转，得到其对应的字符串？基本思路是，从首字符开始，依次判断各字符所在区间。
例如，假设有实数N=，它落在[，]区间内，由此知，实数N对应的字符串的首字符必为C（任何其他字符只能落在该区间以外）。
下一步确定第二个字符所在区间，为此用实数N减去p，然后除以区间长度w，即：（N-p）/w＝(-)/=，该数落在区间[0，]，。
同样的道理求出（-0)/=∈[，]，可知第三个字符为B。
……依此类推，。如表