《前缀码的相关问题.doc》由会员分享，可在线阅读，更多相关《前缀码的相关问题.doc（3页珍藏版）》请在金锄头文库上搜索。
1、前缀码在计算机及通信中，常用二进制编码来表示字符。例如，可用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个字母所用的二进制位为35 + 320 + 225 + 150 = 175这种表示比用等长的二进制序列表示法好，节省了二进制位
2、。但当我们用1表示A，用00表示B，用001表示C，用000表示D时，如果接收到的信息为001000，则无法辨别它是CD还是BAD。因而，不能用这种二进制序列表示A、B、C、D。要寻找另外的表示法。设a1a2an-1an为长度为n的符号串，称其子串a1，a1a2，,a1a2an-1分别为a1a2an-1an的长度为1，2，n-1的前缀（Prefix）。定义14.1 设A = a1,a2,am是一个符号串集合，若对任意ai,ajA，aiaj，ai不是aj的前缀，aj也不是ai的前缀，则称A为前缀码（Prefixed Code）。若符号串ai（i = 1,2,m）中，只出现0和1两个符号，则称A为
3、二元前缀码（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所在的通路上，因而所得集
4、合为二元（0和1组成）前缀码。由此法可知，若T存在带一个儿子的分支点，则由T产生的前缀码不惟一，但T若为完全二元树，则T产生的前缀码就是惟一的了。图14-6中所示的二元树产生的前缀码为：1,00,010,011。当知道了传输的符号出现的频率时，如何选择前缀码，使传输的二进制位尽可能地少呢？这就要先产生一棵最优二元树T，然后用T产生二元前缀码，能使传输的二进制位最少。下面通过一个例子来说明最优前缀码的产生过程。已知字母A、B、C、D、E、F出现的频率如下：A30，B25，C20，D10，E10，F5。（1）求带权30，25，20，10，10，5的最优二元树T （2）在T上求一个前缀码。（3）设树叶vi带权为w100 = 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) + 310 + 2(20 + 25 + 30) = 240很复杂啊,但工夫不负有心人,努力研究啊!
