搜索
前缀码在计算机及通信中，常用二进制编码来表示字符。例如，可用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为前缀码（PrefixedCode）。若符号串ai（i=1,2…,m）中，只出现0和1两个符号，则称A为二元前缀码（BinaryPrefixedCode）。例如{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很复杂啊,但工夫不负有心人,努力研究啊!!!