哈夫曼编码 -- 来自 Wolfram MathWorld

一种无损数据压缩算法，它使用少量比特来编码常用字符。哈夫曼编码将每个字符的概率近似为 1/2 的幂，以避免使用非整数比特来编码字符的实际概率所带来的复杂性。

哈夫曼编码处理权重列表 ${w_i}$ ，方法是构建一个具有最小加权扩展二叉树外部路径长度，并逐步找到两个最小的，即和，将它们视为外部节点，并用权重为的内部节点替换它们。重复此步骤，直到到达根节点。然后，可以通过 0（左分支）和 1（右分支）的二进制字符串对单个外部节点进行编码。

下面总结了前 13 个素数 2、3、5、7、11、13、17、19、23、29、31、37 和 41 的权重过程，结果树如上所示（Knuth 1997，pp. 402-403）。从图中可以清楚地看出，较大权重的路径比较小权重的路径短。在本例中，数字 13 将被编码为 1010。

2	3	5	7	11	13	17	19	23	29	31	37	41
	5	5	7	11	13	17	19	23	29	31	37	41
		10	7	11	13	17	19	23	29	31	37	41
			17	11	13	17	19	23	29	31	37	41
			17		24	17	19	23	29	31	37	41
					24	34	19	23	29	31	37	41
					24	34		42	29	31	37	41
						34		42	53	31	37	41
								42	53	65	37	41
								42	53	65		78
									95	65		78
									95			143
												238

以下Wolfram 语言代码可用于构建内部节点列表和迭代表

  HuffmanStep[l0_List] := Module[
    {
      l = l0,
      s2 = Take[Select[Sort[l0], Positive], 2]
    },
    l[[Take[Flatten[Position[l, #]& /@ s2], 2]]] = 0;
    l[[Last[Position[l, 0]]]] = Plus @@ s2;
    {l, s2}
  ]
  HuffmanList[l_List] := Module[{},
    Plus @@@ Last /@ NestWhileList[
      HuffmanStep[First[#]]&,
        HuffmanStep[l], Length[Union[First[#]]] > 2&]
  ]
  HuffmanTable[l_List] :=
    NestWhileList[First[HuffmanStep[#]]&, l,
      Length[Union[#]] > 2&]

哈夫曼编码

用 Wolfram|Alpha 探索

参考文献

在 Wolfram|Alpha 上引用

引用此内容为

主题分类

2	3	5	7	11	13	17	19	23	29	31	37	41
	5	5	7	11	13	17	19	23	29	31	37	41
		10	7	11	13	17	19	23	29	31	37	41
			17	11	13	17	19	23	29	31	37	41
			17		24	17	19	23	29	31	37	41
					24	34	19	23	29	31	37	41
					24	34		42	29	31	37	41
						34		42	53	31	37	41
								42	53	65	37	41
								42	53	65		78
									95	65		78
									95			143
												238

2	3	5	7	11	13	17	19	23	29	31	37	41
	5	5	7	11	13	17	19	23	29	31	37	41
		10	7	11	13	17	19	23	29	31	37	41
			17	11	13	17	19	23	29	31	37	41
			17		24	17	19	23	29	31	37	41
					24	34	19	23	29	31	37	41
					24	34		42	29	31	37	41
						34		42	53	31	37	41
								42	53	65	37	41
								42	53	65		78
									95	65		78
									95			143
												238

2	3	5	7	11	13	17	19	23	29	31	37	41
	5	5	7	11	13	17	19	23	29	31	37	41
		10	7	11	13	17	19	23	29	31	37	41
			17	11	13	17	19	23	29	31	37	41
			17		24	17	19	23	29	31	37	41
					24	34	19	23	29	31	37	41
					24	34		42	29	31	37	41
						34		42	53	31	37	41
								42	53	65	37	41
								42	53	65		78
									95	65		78
									95			143
												238