1700506647
1700506648
1700506649
1700506650
1700506651
图9-5 二进制振幅监控信号波形
1700506652
1700506653
这些对于编码的纠错和调整,都已经由通信领域的科学家们研究清楚,并将功能植入上网的模块中了,所以这类模块才能以极低的价格量产,并在实际应用中适应各种恶劣的环境。这是数据科学在通信和信息领域的一种完美体现。
1700506654
1700506655
1700506656
1700506657
1700506659
数据科学家养成手册 9.5 编码与压缩
1700506660
1700506661
有了信息熵公式以后,信息学的发展就变得与原来大为不同。为了提高存储和传输的效率,越来越多的科学家致力于研究通过高效的编码算法和压缩算法来保证在不丢失信息的情况下使占用的空间或信道最少的问题。
1700506662
1700506663
早在20世纪50年代,美国的信息学教授戴维·哈夫曼(4)(如图9-6所示)还在麻省理工学院读博士的时候,在一篇名为A Method for the Construction of Minimum-Redundancy Codes的论文中就提出了一种编码方式,这就是著名的哈夫曼编码(Huffman Coding)。
1700506664
1700506665
在哈特莱提出的I=log2m的信息量计算公式中,通过信源种类m的数量可以得出使用多少位介质来表示一个信息。以1字节的二进制数据为例,它有8bit,最多可以表示m为256的情况。如果要传输1000字节,则需要在信道上传输1000组诸如01010101、10100111、11000110这样的8位编码,共8000bit。
1700506666
1700506667
1700506668
1700506669
1700506670
图9-6 戴维·哈夫曼
1700506671
1700506672
而根据香农的信息熵公式
1700506673
1700506674
1700506675
1700506676
1700506677
可以很快得出一个推论,那就是:只要每种信源产生的概率不均等,那么在刚刚这种场景中,传输1000组编码理论上肯定可以使用少于8000bit的数据,方法就是用比较短的编码来表示高频出现的字符。
1700506678
1700506679
我们以传输6种不同的字符信息为例(如表9-1所示)。
1700506680
1700506681
表9-1 6种不同的信源字符
1700506682
1700506683
1700506684
1700506685
1700506686
如果要传输1000组3bit定长编码信息,那就是需要传输3000bit的数据。但是,如果按照出现的概率不同,把大概率的数字换成较短的编码,情况会有所不同。
1700506687
1700506688
1700506689
1700506690
1700506691
在以上场景中,通过更换编码,可以把原先需要用3000bit传完信息用2300bit传完,起到了一定的压缩作用。
1700506692
1700506693
哈夫曼编码要保证一个叫作“前缀编码”的原则,即任何一个编码不能是另一个编码的前缀。原因在于,这种方式在接收到编码后进行解码时,由于无法判断当前接收到的编码是否为一个信息的结束标志,所以会产生困惑。
1700506694
1700506695
由于消息中产生的冗余信息会导致存储和传输效率低下,所以涌现出了一大批着力解决这方面问题的优秀算法。根据算法压缩时所涉及的场景,可以分为两大类,一类是无损压缩,另一类是有损压缩。
1700506696
[
上一页 ]
[ :1.700506647e+09 ]
[
下一页 ]