[科普中国]-菲诺算法

菲诺由Fano音译而来，又常被译为费诺。费诺(菲诺)算法是由Fano 提出的一种编码算法。

编码概述早期的数据压缩来自于人们对概率的了解。当对文字信息进行编码时，如果 出现概率较高的字幕赋予较短的编码，为出现概率较低的字母赋予较的编码，平均编码长度就能缩短不少。著名的Morse电码就是一个范例。信息论之父C.E.Shannon曾指出，任何信息都存在冗余，冗余大小与信息中个符号出现概率（不确定性）有关。他所提出的无失真信源编码定理奠定了数据压缩的理论基础。数据压缩的目的就是要消除冗余，信息论是运用率论与数理统计的方法研究信息、信源熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。

从DVD到个人电脑，从卫星通信到文，在我们今天的生活中，信息几乎在每个领域都扮演者重要角色。工程师克劳德·香农于1948年奠定了信息论的基础，他指出了通信的极限。基于这理论产生了数据压缩技术、纠错技术等各个应用技术，这些技术提高了数据传输和存储的效率。信息论将信息的传递作为一种统计现象来考虑，给了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源—信道隔离定理相互联系。当然信息论的重大应用远不止于此。DNA是一种信息存储物质，正事信息论帮助人们解开了生物因组密码之谜。简单地说信息论包含了生命、宇宙乃至一切。

信息论对现代社会的影响是多方面的。首先，在理论研究方面，信息论所处的地位已远远超出了香农当年所界定的“通信的数学理论”的范畴，得到了不断的扩充和发展，出现了语义信息、语法信息与语用信息等研究与信息的意义有关的学科，以及面向智能研究的全信息理论。如今，信息已成为与物质、能量并列的宇宙中的三个基本要素，世间万物的发展变化可归结为物质、能量和信息的传递和转化过程。另一方面，在科学和技术高度发展的今天，信息的概念也被渗透到许多不同的学科和领域，深入到了社会生活的各个方面，成为可与相对论和量子力学并驾齐驱的新一代边缘交叉学科的重要组成部分。特别是以信息论、控制论、和系统论为代表的“老三论”以及以普利高津的耗散结构理论，哈肯的协同学和托姆的突变论或艾根的超循环理论为代表的“新三论”的出现，标志着一代新的边缘交叉学科的兴起。它们的形成和发展对现代科学的研究具有重要的方法论上的指导意义。

编码是信息从一种形式或格式转换为另一种形式的过程也称为计算机编程语言的代码简称编码。用预先规定的方法将文字、数字或其它对象编成码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。在计算机硬件中，编码（coding）是指用码来表示各组数据资料，使其成为可利用计算机进行处理和分析的信息。代码是用来表示事物的记号，它可以用数字、字母、特殊的符号或它们之的组合来表示，将数据转换为代码或编码字符，并能译为原数据形式。是计算机书写指令的过程，程序设计中的一部分。在地图自动制图按一定规则用数字与字母表示地图内容的过程，通过编码，使计算机能识别地图的各地理要素。

编码分为信源编码和信道编码，其中信源编码又为无失真和限失真。由于这些定力都要求符号数很大，以便其值接近所规定的值，因而这些定力被称为极限定理。一般称无失真信源编码定力为第极限定理；信道编码（包括离散和连续信道）称为第二极限定理；限失真信源编码定力称为第三极限定理1。

费诺编码基本原理费诺编码就是通过使编码中各个句号出现的概率大致相等，实现概率均匀化，从而减少冗余度，提高编码效率。凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。在编N进制码时首先将信源消息符号按其出现的额概率一次又小到大排列开来，并将排列好的心愿符号按概率值分N大组，使N组的概率之和近似相同，并对各组赋予一个N进制码元0、1...N-1。之后再针对每一个大组内的心愿符号做如上处理，即再分为概率相同的N组，赋予N进制码元。如此重复，直到每组只剩下一个心愿符号为止。此时每个信源符号所对应的码字即为费诺码。针对同一个心愿，费诺码比香农码平均码长小，消息出书速率大，编码效率高。费诺编码是一种信源编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高。但它属于概率匹配编码它不是最佳的编码方法。

费诺编码特点费诺编码是一种信源编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高。但它属于概率匹配编码，它不是最佳的编码方法。

费诺编码属于概率匹配编码，具有如下特点：

（1）概率大，则分解次数少；概率小则分解次数多，这符合最佳编码原则。

（2）码字集合是唯一的。

（3）分解之后先得码字后得码长。1

费诺编码算法1.将信源消息符号按其出现的概率大小依次排列。

2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。

3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。

4.如此重复，直至每个组只剩下一个信源符号为止。

5.信源符号所对应的码字即为费诺码。1

费诺编码过程示例

|| ||