1 基本原理
香农-法诺编码是一种基于符号出现概率的无损数据压缩算法，由克劳德·香农和罗伯特·法诺在20世纪40年代末独立提出。其核心思想是将符号按概率降序排列，然后递归地将符号集划分为两个近似等概率的子集，并为每个子集分配二进制码字（0或1），从而生成前缀码（即时码）。虽然该方法在理论上接近最优，但实际中未必能像霍夫曼编码那样保证最短平均码长，但作为早期熵编码的代表，它为现代信息论和压缩技术奠定了基础。
1.1 熵编码与信息论背景
熵编码是数据压缩领域的基础技术，其依据是信息论中克劳德·香农提出的“信息熵”概念。信息熵刻画出符号集合中每个符号所含平均信息量的下限，即无损压缩理论上的最短平均码长。香农-法诺编码与霍夫曼编码、算术编码共同构成三大经典熵编码方法。在20世纪40年代末，香农与其同事法诺几乎同时发现了这种通过递归二分构建即时码的思路，尽管它并非总能达到熵界，却直观地展示了“概率越高的符号编码越短”这一原则。
1.2 概率排序与递归划分
该算法的核心步骤是：先对符号按概率从大到小排序，然后反复将当前符号集分割成两个子集，使得两个子集的概率总和尽可能接近相等。这种分割方式模拟了二分搜索树的结构——每个节点对应一个符号子集，左子集赋予码字“0”，右子集赋予码字“1”，由此每个符号的码字即为从根到叶子的路径上“0”和“1”的拼接。
1.2.1 平分原则：子集概率尽可能相等
分割点的选择至关重要。算法从概率排序列表的某一位置切开，使得左子集（靠前的高概率符号）的总概率与右子集（靠后的低概率符号）的总概率之差最小。理论上，若每次分割都能达到绝对相等（即两个子集概率均为0.5），则生成的码字将完美匹配概率分布，平均码长等于信息熵。但现实中，离散的符号概率难以实现精确平分，这种近似妥协正是导致其非最优性的根源。
1.2.2 码字分配：左子集赋0，右子集赋1
每完成一次分割，就为左子集的所有符号在当前码字后追加一个“0”，为右子集追加“1”。该过程递归进行，直到每个子集仅包含一个符号为止。例如，若符号A、B概率分别为0.6、0.4，则第一次分割后左子集（A）获得初始码字“0”，右子集（B）获得“1”，完成编码。
1.3 前缀码特性与可解码性
由于每个符号对应唯一的叶子节点，且编码过程中任何码字都不是其他码字的前缀（因为递归分割确保了不同路径不可能重叠），香农-法诺编码天然具备前缀码性质。这意味着解码器无需分隔符即可顺序读取二进制流并唯一确定源符号序列，这是所有熵编码实用化的基本要求。
2 算法流程
2.1 输入与预处理
输入为待编码的符号集及其概率分布（或频次）。预处理阶段需检查概率总和是否为1（或频次数值），若有向零逼近的概率符号，通常需要合并或舍入处理以避免极端编码深度。同时，需将符号与概率绑定后存入一个有序数据结构（如列表、数组）。
2.2 递归构建步骤
2.2.1 符号按概率降序排列
将符号按照概率从大到小排序。若存在概率相等的符号，可任意决定排列顺序（通常按出现顺序或字典序）。排序后的序列作为递归函数的输入。
2.2.2 找到最优分割点
从列表的某个位置（从第一个元素之后到倒数第二个元素之间）进行切割，计算每个候选分割点下左子集总概率与右子集总概率之差的绝对值。选择差值最小的点作为正式分割点。若有多处差值相同，通常选择靠左的分割点（使得高概率符号先分配码字）。这一“最优分割点”即为下一层递归的边界。
2.2.3 递归处理左右子集
对左子集（下标范围[0, split]）和右子集（下标范围[split+1, n-1]）分别重复步骤2.2.1至2.2.3，直至每个子集仅含一个符号。递归过程中，当前码字按层积累：进入左子集时在原码字末尾追加“0”，进入右子集时追加“1”。最终每个符号获得一个唯一的二进制码字。
2.3 码表生成与输出
递归完成后，将每个符号及其对应的码字记录成码表（例如字典或映射表）。输出部分包括码表本身以及原始数据编码后的二进制流。码表通常被嵌入压缩文件头部或单独存储，以便解码端重建树结构。
3 性能分析
3.1 平均码长与信息熵的关系
香农-法诺编码的平均码长定义为各符号码长与概率的加权和。根据信息论，平均码长的理论下界为信息熵 H = -∑p(i)·log₂p(i)。该编码的平均码长大多比熵高出一个较小的固定值（通常不超过1比特/符号），但并非总能严格逼近熵界。
3.1.1 最坏情况举例：概率不均等时的低效
考虑一个极端分布：符号A概率0.99，B概率0.01。按香农-法诺排序：A在前，B在后，第一次分割时左子集总概率0.99，右子集0.01，无法平分（差值0.98）。此时A获得码字“0”，B获得码字“1”，平均码长为1比特。而信息熵约为0.08比特，理论上可用算术编码达到接近0.08。此例中香农-法诺编码比最优码多出近0.92比特/符号，效率极低。
3.1.2 最佳情况：逼近熵边界
当符号概率恰好呈现精确的二分幂次（如0.5、0.25、0.125等）时，香农-法诺编码的每次分割都能实现完美平分，码长等于-log₂p(i)，平均码长正好等于熵。例如一个包含两个等概率符号的集合（各0.5）时，码字分别为“0”和“1”，平均码长1比特，熵也为1比特，达到理论最优。
3.2 与霍夫曼编码的对比
3.2.1 树形结构差异
霍夫曼编码采用自底向上合并最小概率符号的策略，构造出二叉树后从根到叶子逐层赋值0/1；香农-法诺编码则自顶向下分割。两者生成的码树往往不同：霍夫曼树通常更平衡，而香农-法诺树可能在概率不均时出现某侧深度过大的“瘦高”分支。例如对符号概率{0.35,0.20,0.20,0.15,0.10}，霍夫曼码长分布为{2,2,2,3,3}，香农-法诺码长可能为{2,2,3,3,3}，平均码长稍长。
3.2.2 最优性证明的缺失
霍夫曼编码已被证明对于给定概率分布总能产生最小平均码长的前缀码（最优性定理）。而香农-法诺编码缺乏类似严格证明——其分割点选择仅基于“尽可能平分”的启发式，未考虑全局最优。某些概率分布下，香农-法诺的平均码长甚至比霍夫曼编码高出一个比特以上。这使其在实用压缩中几乎被霍夫曼编码取代。
3.3 空间与时间复杂度评价
算法的时间复杂度主要取决于排序过程（若使用快速排序为O(n log n)）以及递归分割过程中每次计算分割点时的候选检查（朴素实现需O(n²)总复杂度，但可通过前缀和优化降至O(n log n)）。空间复杂度为O(n)，用于存储符号列表和递归栈（最大深度不超过n）。在现代硬件上，其速度通常劣于动态规划实现的霍夫曼编码（后者可在O(n log n)内完成且代码简洁），但作为教学算法仍具价值。
4 应用与变体
4.1 早期文本压缩应用（如纸质电报）
在20世纪50至60年代，香农-法诺编码被用于一些早期的电报编码器和机械式压缩设备中。由于当时计算资源有限，二分法递归实现简单，且硬件可通过模拟比较器完成分割，因此在纯文本（如英文单词、莫尔斯电码的二次编码）中有过应用。但随着霍夫曼编码的算法化推广，它很快让出了主流位置。
4.2 现代混合压缩算法中的影子（如JPEG中的子集划分思想）
虽然原始香农-法诺编码现已不常作为独立压缩步骤，但其“递归二分、近似等概率”的思想深刻影响了现代算法。例如JPEG压缩中的“熵编码”阶段（霍夫曼编码后处理）虽直接采用霍夫曼，但离散余弦变换系数分块后的“之字形重排”与“零游程编码”中，对非零系数子集的分割思路与香农-法诺的二分逻辑有相似之处。此外，部分图像编码标准（如早期的JPEG-2000测试模型）曾探索过将系数按概率分层后继续使用类似二分划分的方法。
4.3 香农-法诺-埃利斯码（Shannon-Fano-Elias Coding）简介
香农-法诺-埃利斯码是香农-法诺编码的改进变体，由法诺和P.埃利斯于20世纪60年代独立提出。其主要区别在于：不再强行将符号集分裂为两个严格子树，而是将符号概率视为区间，通过累加概率映射到[0,1)区间内，然后取区间中点的二进制展开前L位作为码字（L = ⌈-log₂p(s)⌉ + 1）。这种方法保证了平均码长严格小于H+2比特，且适用于连续分布，为算术编码的诞生奠定了理论基础。它虽然比原始香农-法诺更接近最优，但实现复杂度较高，在实践中被算术编码取代。
4.4 教学与理论工具价值（“虽然不完美，但让我们看清了最优码的模样”）
在信息论和数据结构教材中，香农-法诺编码常被用作“最优前缀码的直觉推导”案例。它直观地展示了“概率排序-递归划分-码字赋值”这一思想链条，帮助学生理解为什么霍夫曼编码是最优的，以及最优码需要满足怎样的树形性质。很多教师会调侃道：“香农-法诺编码就像一位老练的棋手，每一步都力求位置均衡，但有时少算了一步后续的杀招——直到霍夫曼这位更聪明的后辈发明了全局最优策略。”
5 相关条目与延伸阅读
5.1 信息论经典概念
5.1.1 熵
熵是信息论的核心度量，由克劳德·香农于1948年定义，衡量随机变量不确定性（或平均信息量）的大小。其计算公式为H(X)= -∑p(x)log₂p(x)。熵给出了无失真压缩的下界，也是所有熵编码算法追求的目标。
5.1.2 霍夫曼编码
霍夫曼编码是1952年由大卫·霍夫曼提出的最优前缀码构造算法，它通过贪心合并最小概率符号构造二叉树，保证了对于给定概率分布的平均码长最短。它是现代压缩软件（如ZIP、JPEG）的核心组件。
5.1.3 算术编码
算术编码是一种将整个消息映射到[0,1)区间一个实数上的熵编码方法，可以逼近任意精度的熵界（尤其是非整数比特情况）。它克服了香农-法诺和霍夫曼“码长必须为整数”的局限，因此常用于高压缩比场合（如JPEG-2000、H.264视频编码的上下文自适应算术编码）。
5.2 历史趣闻：香农与法诺的“打字机旁争论”
据传闻，1948年香农在贝尔实验室提出信息论后，与同事罗伯特·法诺在一次午餐后的即兴讨论中，法诺在黑板上画出了一个二分分割草图，香农则指出这种分割方式可能导致不平衡树。两人在打字机上反复打印符号概率和码表，经过多次迭代才整理出如今流传的香农-法诺算法。有趣的是，法诺当时并未完全认同香农对“最优性”的怀疑，直到霍夫曼（香农的博士生）于1952年提交了一篇课程论文，才用严格证明展示了更优的构造方法。香农后来打趣道：“当时我们俩围着打字机吵了三天三夜，结果最好的那个答案正坐在我的教室里听课呢。”