记得在毕业前去找工作,应聘康佳集团移动应用工程师的笔试题出了这么一道题。
传输文本字符”BADCADFEED”,只能出现”ABCDEF”这六个字符,使用以下的编码方式:
如传输字符:BADCADFEED 接收编码:001000011010000011101100100011
接收方可以根据每3个bit进行一次字符解码的方式还原文本传输的信息,但是这样的传输效率太低了,需要30bit才发送10个字符。如何编码来提高传输以及接收效率???请写出你的编码方式以及算法思想。
我当时并没有想到解决方法,GG了。最近运用到霍夫曼树,现在回想起来不就是这个算法吗,哈哈哈,太好了。在这里总结一下。
引入:
要提高效率,必须要从编码方式去改变,这是无疑的。这里运用了避免每一个字符都占有相同的bit位。如
如传输字符:BADCADFEED 接收编码:1001010010101001000111100
改进编码方式之后,可以看到发送相同的字符,需要25bit位就可以表示10个字符了。这种编码明显是有很大优势的。
问题:这个编码方式有什么规律呢?怎么得到呢?又是如何在接收方解码的呢?下面来揭开神奇的面纱。
假定经过统计得出ABCDEF在所需传输报文出现的概率如下:
霍夫曼树算法:
给定实数w1,w2,···,wt且 w1<=w2<=···<=wt
(1)连接w1,w2为权的两片树叶,得一分支点,其权为w1+w2 ;
(2)在w1+w2, w3+···+wt中选出两个最小的权,连接它们对应的顶点(不一定都是树叶),得分支点及所带的权;
(3)重复(2),直到形成t – 1个分支点,t片树叶为止
或者这样描述算法:
1、给定n个数值{ v1, v2, …, vn}
2.