前缀码的相关问题.doc

前缀码 在计算机及通信中，常用二进制编码来表示字符例如，可用 00、01、10、11 分别表示字母 A、B、C、D如果字母 A、B、C、D 出现的 频率是一样的，传输 100 个字母用 200 个二进制位但实际上字母出现的频率 很不一样，如 A 出现的频率为 50％，B 出现的频率为 25％，C 出现的频率为 20％，D 出现的频率为 5％能否用不等长的二进制序列表示字母 A、B、C、D，使传输的信息的二进制位尽可能少呢？事实上，可用 000 表示 字母 D，用 001 表示字母 C，01 表示 B，1 表示 A这样表示，传输 100 个字 母所用的二进制位为3×5 + 3×20 + 2×25 + 1×50 = 175这种表示比用等长的二进制序列表示法好，节省了二进制位但当我们用 1 表 示 A，用 00 表示 B，用 001 表示 C，用 000 表示 D 时，如果接收到的信息为 001000，则无法辨别它是 CD 还是 BAD因而，不能用这种二进制序列表示 A、B、C、D要寻找另外的表示法设 a1a2…an-1an 为长度为 n 的符号串，称其子串 a1，a1a2，…,a1a2…an-1 分别为 a1a2…an-1an 的长度为 1，2，…，n-1 的前缀（Prefix）。

定义 14.1 设 A = {a1,a2,…,am}是一个符号串集合，若对任意ai,aj∈A，ai≠aj，ai 不是 aj 的前缀，aj 也不是 ai 的前缀，则称 A 为前缀码（Prefixed Code）若符号串 ai（i = 1,2…,m）中，只出现 0 和 1 两个符号， 则称 A 为二元前缀码（Binary Prefixed Code）例如{1,01,001,000}是前缀码，而{1,11,001,0011}不是前缀码那么如何产生前 缀码呢？可用一棵二元树来产生一个二元前缀码给定一棵二元树 T，假设它有 t 片树 叶设 v 是 T 任意一个分支点，则 v 至少有一个儿子至多有两个儿子若 v 有 两个儿子，则在由 v 引出的两条边上，左边的标上 0，右边的标上 1；若 v 只 有一个儿子，在 v 引出的边上可标 0 也可标 1设 vi 为 T 的任意一片树叶，从 树根到 vi 的通路上各边的标号组成的符号串放在 vi 处，t 片树叶处的 t 个符号 串组成的集合为一个二元前缀码由上述作法可知，vi 中的符号串的前缀均在 vi 所在的通路上，因而所得集合为二元（0 和 1 组成）前缀码。

由此法可知， 若 T 存在带一个儿子的分支点，则由 T 产生的前缀码不惟一，但 T 若为完全二 元树，则 T 产生的前缀码就是惟一的了图 14-6 中所示的二元树产生的前缀码为：{1,00,010,011}当知道了传输的符号出现的频率时，如何选择前缀码，使传输的二进制位尽可 能地少呢？这就要先产生一棵最优二元树 T，然后用 T 产生二元前缀码，能使传输的二进 制位最少下面通过一个例子来说明最优前缀码的产生过程已知字母 A、B、C、D、E、F 出现的频率如下：A——30％，B——25％，C——20％，D——10％，E——10％，F——5％1）求带权 30，25，20，10，10，5 的最优二元树 T（2）在 T 上求一个前缀码3）设树叶 vi 带权为 w％×100 = w，则 vi 处的符号串表示出现频率为 w％的 字母A = {01,10,11,001,0001,0000}为一前缀码，其中0000 表示 F，0001 表示 E，001 表示 D，01 表示 C，10 表示 B，11 表示 A传输 100 个这样的字母所用的二进制位为4×(5 + 10) + 3×10 + 2×(20 + 25 + 30) = 240很复杂啊,但工夫不负有心人,努力研究啊!!!。