Huffman 编码压缩算法
jopen 12年前
<div id="news_body"> <p> 前两天发布那个 rsync 算法后，想看看数据压缩的算法，知道一个经典的压缩算法 Huffman 算法。你应该听说过 <a title="David Huffman" href="/misc/goto?guid=4958340787168949053" target="_blank">David Huffman</a> 和他的经典的压缩算法—— <a href="/misc/goto?guid=4958340787979227603" target="_blank">Huffman Code</a>，这是一种通过字符出现频率，<a href="/misc/goto?guid=4958201811718581969" target="_blank">Priority Queue</a>，和二叉树来进行的一种压缩算法，这种二叉树又叫 Huffman 二叉树 —— 一种带权重的树。但是网上查了一下，中文社区内好像没有把这个算法说得很清楚的文章，尤其是树的构造，而正好看到一篇国外的文章《<a href="/misc/goto?guid=4958340789514184193" target="_blank">A Simple Example of Huffman Code on a String</a>》，其中的例子浅显易懂，相当不错，我就转了过来。注意，我没有对此文完全翻译。</p> <p> 我们直接来看示例，如果我们需要来压缩下面的字符串：</p> <p> <strong> “beep boop beer!” </strong></p> <p> 首先，我们先计算出每个字符出现的次数，我们得到下面这样一张表 :</p> <center> <table class="ke-zeroborder"> <tbody> <tr> <td>字符</td> <td>次数</td> </tr> <tr> <td>‘b’</td> <td>3</td> </tr> <tr> <td>‘e’</td> <td>4</td> </tr> <tr> <td>‘p’</td> <td>2</td> </tr> <tr> <td>‘ ‘</td> <td>2</td> </tr> <tr> <td>‘o’</td> <td>2</td> </tr> <tr> <td>‘r’</td> <td>1</td> </tr> <tr> <td>‘!’</td> <td>1</td> </tr> </tbody> </table> </center> <p> 然后，我把把这些东西放到 Priority Queue 中（用出现的次数据当 priority），我们可以看到，Priority Queue 是以 Prioirry 排序一个数组，如果 Priority 一样，会使用出现的次序排序：下面是我们得到的 Priority Queue：</p> <p style="text-align:center;"><a><img title="coada1" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/16038d94b555e23a962724d21154b21e.jpg" width="440" height="61" /></a></p> <p> 接下来就是我们的算法——把这个 Priority Queue 转成二叉树。我们始终从 queue 的头取两个元素来构造一个二叉树（第一个元素是左结点，第二个是右结点），并把这两个元素的 priority 相加，并放回 Priority 中（再次注意，这里的 Priority 就是字符出现的次数），然后，我们得到下面的数据图表：</p> <p style="text-align:center;"><a><img title="coada2" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/6f5e21e8b7c96ea7183839e3c0cc7fe1.jpg" width="411" height="151" /></a></p> <p> 同样，我们再把前两个取出来，形成一个 Priority 为2+2=4的结点，然后再放回 Priority Queue 中 :</p> <p style="text-align:center;"><a><img title="coada3" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/119b41a9b8c6c5c6418b21df2e4a4108.jpg" width="325" height="201" /></a></p> <p> 继续我们的算法（我们可以看到，这是一种自底向上的建树的过程）：</p> <p style="text-align:center;"><a><img title="coada4" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/2e104f61a23327a5e80b819da4c38c74.jpg" width="326" height="221" /></a></p> <p style="text-align:center;"><a><img title="coada5" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/64979431efb2e37ae924bc5eb7e339e9.jpg" width="347" height="207" /></a></p> <p style="text-align:center;"><a><img title="coada6" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/839b045c2fe7465f6c20b6fa4b1093bb.jpg" width="344" height="273" /></a></p> <p> 最终我们会得到下面这样一棵二叉树：</p> <p style="text-align:center;"><a><img title="arbore_final" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/e51c5554bcb49a63b00f63d8e45ebc67.jpg" width="452" height="304" /></a></p> <p> 此时，我们把这个树的左支编码为0，右支编码为1，这样我们就可以遍历这棵树得到字符的编码，比如：‘b’的编码是 00，’p'的编码是 101， ‘r’的编码是 1000。<strong>我们可以看到出现频率越多的会越在上层，编码也越短，出现频率越少的就越在下层，编码也越长</strong>。</p> <p style="text-align:center;"><a><img title="arbore_final_numerotat" alt="Huffman 编码压缩算法" src="https://simg.open-open.com/show/6ab0e7bd893c266abca3647a6510d811.jpg" width="452" height="304" /></a></p> <p> 最终我们可以得到下面这张编码表：</p> <center> <table class="ke-zeroborder"> <tbody> <tr> <td>字符</td> <td>编码</td> </tr> <tr> <td>‘b’</td> <td>00</td> </tr> <tr> <td>‘e’</td> <td>11</td> </tr> <tr> <td>‘p’</td> <td>101</td> </tr> <tr> <td>‘ ‘</td> <td>011</td> </tr> <tr> <td>‘o’</td> <td>010</td> </tr> <tr> <td>‘r’</td> <td>1000</td> </tr> <tr> <td>‘!’</td> <td>1001</td> </tr> </tbody> </table> </center> <p> 这里需要注意一点，当我们 encode 的时候，我们是按“bit”来 encode，decode 也是通过 bit 来完成，比如，如果我们有这样的 bitset “1011110111″ 那么其解码后就是 “pepe”。所以，我们需要通过这个二叉树建立我们 Huffman 编码和解码的字典表。</p> <p> 这里需要注意的一点是，我们的 Huffman 对各个字符的编码是不会冲突的，也就是说，<strong>不会存在某一个编码是另一个编码的前缀</strong>，不然的话就会大问题了。因为 encode 后的编码是没有分隔符的。</p> <p> 于是，对于我们的原始字符串 beep boop beer!</p> <p> 其对就能的二进制为 : 0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 0001</p> <p> 我们的 Huffman 的编码为： 0011 1110 1011 0001 0010 1010 1100 1111 1000 1001</p> <p> 从上面的例子中，我们可以看到被压缩的比例还是很可观的。</p> <p> 作者给出了源码你可以看看（ C99 标准） <a href="/misc/goto?guid=4958340790306137724">Download the source files</a></p> <div id="come_from"> 来自: <a id="link_source2" href="/misc/goto?guid=4958340791108702827" target="_blank">coolshell.cn</a> </div> </div>