前缀码471的含义 前缀码
大家好，我是小典，我来为大家解答以上问题。前缀码471的含义，前缀码，很多人还不知道，现在让我们一起来看看吧！
前缀码
在计算机及通信中，常用二进制编码来表示字符。例如，可用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
很复杂啊,但工夫不负有心人,努力研究啊!!!
本文到此讲解完毕了，希望对大家有帮助。