In Place Huffman算法

paper网上下不到，不过找到了一份C语言实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

void calculate_minimum_redundancy(int A[], int n) {
        int root;                  /* next root node to be used */
        int leaf;                  /* next leaf to be used */
        int next;                  /* next value to be assigned */
        int avbl;                  /* number of available nodes */
        int used;                  /* number of internal nodes */
        int dpth;                  /* current depth of leaves */

        /* check for pathological cases */
        if (n==0) { return; }
        if (n==1) { A[0] = 0; return; }

        /* first pass, left to right, setting parent pointers */
        A[0] += A[1]; root = 0; leaf = 2;
        for (next=1; next < n-1; next++) {
                /* select first item for a pairing */
                if (leaf>=n || A[root]<A[leaf]) {
                        A[next] = A[root]; A[root++] = next;
                } else
                        A[next] = A[leaf++];

                /* add on the second item */
                if (leaf>=n || (root<next && A[root]<A[leaf])) {
                        A[next] += A[root]; A[root++] = next;
                } else
                        A[next] += A[leaf++];
        }

        /* second pass, right to left, setting internal depths */
        A[n-2] = 0;
        for (next=n-3; next>=0; next--)
                A[next] = A[A[next]]+1;

        /* third pass, right to left, setting leaf depths */
        avbl = 1; used = dpth = 0; root = n-2; next = n-1;
        while (avbl>0) {
                while (root>=0 && A[root]==dpth) {
                        used++; root--;
                }
                while (avbl>used) {
                        A[next--] = dpth; avbl--;
                }
                avbl = 2*used; dpth++; used = 0;
        }
}

下面写一些我对这个算法的证明与理解。首先明确这个算法的输入和输出：

  • 算法的输入为一个已经排好序的数组，其中数组的元素由小到大排列，为对应的symbol所占的概率（这里实质上为频数，是个整数）
  • 算法的输出为霍夫曼编码每个symbol的codeword对应的长度，这个长度可以通过简单推导还原出的原本的霍夫曼编码

首先明确这个算法是由三部分组成的：

  1. 将这个数组填充为一个霍夫曼树的内部节点的组成的数组。每个数组元素对应霍夫曼树中的一个内部节点（不包含叶节点）。每个数组元素的值保存的是其父节点在该数组中对应元素的index
  2. 通过遍历整个树，将整个数组中每个内部节点对应的元素的值更改为该内部节点的深度
  3. 最后通过这些内部节点的深度信息推导出该霍夫曼树中所有叶节点的深度，我们知道霍夫曼树中每个叶节点对应一个霍夫曼编码，且其深度即为霍夫曼编码的长度

phase 1

第一阶段的算法其实是最重要的，后面两个阶段的算法严重依赖于第一阶段算法的几个性质。该阶段实质上是利用了滚动数组的方式实现了In-place霍夫曼树的生成。从算法证明角度，整个数组实质上是分成了三个部分：

  • [0, root)：该区域的每一个数组元素表示一个霍夫曼树的内部节点，且数组元素中保存的值为其父节点对应元素在数组中的index
  • [root, next)：该区域中的每一个元素也表示一个内部节点，但是与上面不同的是，元素中保存的值为该内部节点对应的概率（这里是没有正则化的整数）
  • [leaf, n)：这个区域实质上是原先的叶节点

算法中实质上维持了几个不变式，亦即几个比较重要的属性，后面要用到：

  • [root, next)区域中的元素是递增的
  • [leaf, n)区域中的元素的值是递增的

后者显而易见。而前者需要观察一下循环部分进行的操作，循环中将A[next]变成了一个新的内部节点，而这个节点实质上是在当前的节点范围([root, next)和[leaf, n))中找到最小的两个节点合并（概率相加）所得。实质上问题就是，在一个有限整数集合中取出两个最小的数a, b，然后将a+b放回这个集合，此时集合中最小的两个数相加一定大于a+b，所以第一个不变式也是成立的。

我们先定义“合并”操作为霍夫曼树构建中的将当前最小的两个节点合并成一个新的内部节点的过程。那么算法的初始条件就比较好定义了，首先将数组中的前两个（0,1）叶节点合并，合并后的内部节点用于当作[root, next)区域的第一个内部节点，然后将next设置为1，leaf设置为2。此时三个区域分别为[0]， []， [2, n)。然后算法开始从左到右以next为索引遍历整个数组：

  • 每个next指向的数组元素都是由[leaf, n)区域取出叶节点之后腾出来的空间，是可以安全写入的，我们向里面保存一个新的内部节点，然后将其加入[root, next)区域
  • 内部节点是通过霍夫曼算法得出的，实质上就是[leaf, n)区域和[root, next)区域中最小的节点合并而成的（以这个节点为子节点创建新的内部节点）。注意前面提到过这两个区域内的元素都是递增的，所以实质上只需要做两次比较就能选出这两个节点。
  • 每从[leaf, n)区域拿出一个节点不需要做额外操作，只需要将leaf指针自增一即可。而从[root, next)区域拿去节点时，需要将root指针自增一，即将该节点放入[0, root)，同时由于节点已经根其他节点合并，那么他保存的概率也就不需要了，此时可以安全写入指向其父节点的索引，即当前next的值

重复上面这一过程，最终[0, root)区域扩大到[0, n-2]（后面证明），得到一棵霍夫曼树。

phase 2

前面提到[0, n-2]已经是一颗霍夫曼树，这是由于如果一颗完全的二叉树的叶节点个树为L，那么其内部节点的个数就是L-1。因此算法的第一阶段结束后，[0, n-2]就是一颗霍夫曼树，且A[n-2]为其根节点。接下来可以通过遍历的方式得到每一个内部节点的深度，首先我们注意到一个内部节点的索引一定小于其父节点，那么我们可以通过从右向左的方式遍历整个树，此时我们能保证一个内部节点的父节点一定会先于其被遍历。可以将根节点的值修改为0，然后在遍历时将节点的值修改为其深度：A[next] = A[A[next]]+1，即子结点的深度为其父节点的深度加1。

phase 3

在我们知道了所有内部节点的深度之后，是可以推算出所有叶节点的深度的。对于每一个深度为D的内部节点，它可以伸展出2*D个深度为D+1的节点，将2*D减去深度为D+1的内部节点个数就可以得到深度为D+1的叶节点个数。

上面的原理只能说明现内部节点的深度可以推算出所有叶节点的深度，但是想要高效实现这个算法还需要证明在算法第二阶段完成后，存在：A[x] >= A[x+1]这一性质，亦即A[x]是x的不增函数。用反证法，首先假设A[x]不是x的不增函数，则必然存在0 <= i < j <= n-1，使得A[i] < A[j]。我们假设j是满足这个条件的最大数，首先可以注意到i和j肯定不是根节点，否则0 <= A[i] < A[j] = 0，矛盾。因此i与j必然存在父节点i’和j’，我们有A[i'] = A[i] - 1和A[j'] = A[j] - 1，但A[i] < A[j]，所以A[i'] < A[j']。由第一阶段算法的队列操作方式（root指针和next指针单向增长）以及i < j，我们知道i' <= j'。但是如果i' = j'那么A[i] = A[j]，因为他们的深度是一样的，所以必有i' < j'。由于i' < j'且A[i'] < A[j']，j’和i’也是满足前面性质的两个数，但是j' > j，与原先假设j是最大满足该性质的数相矛盾，这就证明了A[x]是x的不增函数。