5分钟快速了解霍夫曼编码

　　阅读时间&＃xff1a;3分钟

　　霍夫曼编码算法是许多压缩算法&＃xff08;例如DEFLATE&＃xff09;的基石&＃xff0c;PNG图像格式和GZIP都是用的它。

　　您是否想知道&＃xff1a;我们如何压缩某些东西而又不丢失任何数据&＃xff1f;为什么有些东西压缩得比其他东西好&＃xff1f;GZIP如何工作&＃xff1f;5分钟以内

　　霍夫曼编码可以用于任何数据&＃xff0c;字符串是很好的例子&＃xff0c;霍夫曼编码利用了最常用的字符比不常用的字符占用更少的空间这一特性。

　　编码字符串

　　让我们使用霍夫曼编码来压缩12个字符的“do or do not”字符串。

　　它有几个重复的字符&＃xff0c;我们假设存储每个字符需要8位&＃xff0c;共96位&＃xff0c;但是使用Huffman编码可以做得更好&＃xff01;

　　我们从建立树形结构开始。我们数据中最常见的字符更接近树的根&＃xff0c;而离根最远的节点表示次要字符。&＃xff08;如下图&＃xff09;

　　字符串中最常见的字符是&＃39;o&＃39;&＃xff08;代表4个字符&＃xff09;和空格&＃xff08;代表3个字符&＃xff09;。请注意&＃xff0c;到那些字符的路径离根只有两步之遥&＃xff0c;而对于最不常见的字符&＃xff08;&＃39;t&＃39;&＃xff09;则只有三步之遥。

　　现在&＃xff0c;我们可以存储字符的路径&＃xff0c;而不是存储字符本身。

　　我们用第一个字母d来举例&＃xff0c;我们从买游戏平台根节点开始&＃xff0c;然后沿着树一直向着要编码的字符前进。走右边存一个1&＃xff0c;走左边存一个0&＃xff0c;如下图所示&＃xff1a;

　　最终结果是1 0 0&＃xff0c;是3位而不是8位&＃xff0c;这是一个很大的改进&＃xff01;

　　整个编码后的字符串如下所示&＃xff1a;

　　总共是29位而不是96位&＃xff0c;没有数据丢失&＃xff0c;是不是被震撼到了&＃xff1f;

　　解码字符串

　　要解码我们的文本&＃xff0c;我们只需跟随路径傻瓜前行就可以还原我们的字母&＃xff0c;比如0 0 表示O&＃xff0c;然后从顶部重新开始查找&＃xff1a;

　　发送编码的文本

　　当我们将编码后的文本发送给其他人时&＃xff0c;他们不也需要树吗&＃xff1f;是的&＃xff01;另一端需要相同的霍夫曼树才能正确解码文本。

　　最简单但效率最低的方法是将树与压缩文本一起发送。

　　我们也可以先约定同一棵树&＃xff0c;然后在对任何字符串进行编码或解码时都使用该树。