我们是否必须创建一个树,其中所有节点都有3个子节点？

Question

构建霍夫曼树输入的步骤是独特字符的数组以及它们的出现频率和输出是霍夫曼树.

1. 为每个唯一字符创建一个叶节点,并构建所有叶节点的最小堆(Min Heap用作优先级队列.频率字段的值用于比较最小堆中的两个节点.最初,最不频繁的字符位于根)

2. 从最小堆中提取具有最小频率的两个节点.

3. 创建一个频率等于两个节点频率之和的新内部节点.将第一个提取的节点作为其左子节点,将另一个提取的节点作为其右子节点.将此节点添加到最小堆.

4. 重复步骤#2和#3,直到堆只包含一个节点.其余节点是根节点,树已完成.

在堆中,一个节点最多可以有2个子节点,对吧？

因此,如果我们想对三元系统中的编码字(即使用符号0,1和2的编码字)推广霍夫曼算法,我们能做什么？我们是否必须创建一个树,其中所有节点都有3个子节点？

编辑:

我认为它会如下.

构建霍夫曼树输入的步骤是独特字符的数组以及它们的出现频率和输出是霍夫曼树.

1. 为每个唯一字符创建一个叶节点,并构建所有叶节点的最小堆

2. 从最小堆中提取具有最小频率的三个节点.

3. 创建一个频率等于三个节点频率之和的新内部节点.将第一个提取的节点作为其左子节点,将第二个提取的节点作为其中间子节点,将第三个提取的节点作为其右子节点.将此节点添加到最小堆.

4. 重复步骤#2和#3,直到堆只包含一个节点.其余节点是根节点,树已完成.

我们如何证明该算法产生最优的三元码？

编辑2:假设我们的频率为5,9,12,13,16,45.

它们的数量是偶数,所以我们添加一个频率为0的虚节点.我们把它放在数组的末尾吗？那么,它会如下吗？

那么我们会有以下堆吗？

然后:

然后:

或者我明白错了？

Answer 1

是! 你必须创建3个孩子的所有节点.为什么3？你也可以n-ary huffman coding使用n子节点.树看起来像这样 - (对于n = 3)

    *
  / | \
 *  *  *
   /|\
  * * *

三元码字的霍夫曼算法

我给出的算法很容易参考.

HUFFMAN_TERNARY(C)
{
   IF |C|=EVEN 
   THEN ADD DUMMY CHARACTER Z WITH FREQUENCY 0.

   N=|C|
   Q=C;  //WE ARE BASICALLY HEAPIFYING THE CHARACTERS

   FOR I=1 TO floor(N/2)
   {
     ALLOCATE NEW_NODE;
     LEFT[NEW_NODE]= U= EXTRACT_MIN(Q)
     MID[NEW_NODE] = V= EXTRACT_MIN(Q)
     RIGHT[NEW_NODE]=W= EXTRACT_MIN(Q)
     F[NEW_NODE]=F[U]+F[V]+F[W];
     INSERT(Q,NEW_NODE);
   }
   RETURN EXTRACT_MIN(Q);
  } //END-OF-ALGO

Why are we adding extra nodes?使节点数奇数.(为什么？)因为我们想在Q中只有一个节点离开for循环.

Why floor(N/2)? 起初我们需要3个节点.然后用它替换1个节点.有N-2个节点.之后我们总是占用3个节点(如果不可用1个节点,由于虚节点,永远不可能获得2个节点)并替换为1.在每次迭代中,我们将它减少2个节点.这就是我们使用这个词的原因floor(N/2).

使用一些示例字符集在纸上自行检查.你会明白的.

正确性

我在这里参考Cormen,Rivest的"算法导论".

证明:一步一步的数学证明太长了,无法在此发布,但它与本书中给出的证据非常相似.

理念

任何optimal tree一个在最低级别具有最低的三个频率.(我们必须证明这一点).(使用矛盾)假设情况并非如此,那么我们可以从最低级别切换具有较高频率的叶子,其中一个叶子是最低的三个叶子之一并获得较低的平均长度.在不失一般性的情况下,我们可以假设所有三个最低频率都是同一节点的子节点.如果它们处于同一水平,则无论频率在何处,平均长度都不会改变).它们只在代码字的最后一位有所不同(一个是0,1或2).

再次作为二进制代码字,我们必须收缩三个节点并从中创建一个新的字符frequency=total of three node's(character's) frequencies.像二进制霍夫曼代码一样,我们看到最优树的成本是树与三个符号之contracted和以及eliminated sub-tree在收缩之前具有节点的总和.由于已经证明子树必须存在于最终的最优树中,因此我们可以使用签约的新创建的节点在树上进行优化.

例

• 假设字符集包含频率5,9,12,13,16,45.

• 现在N = 6->偶数.所以添加freq = 0的虚拟角色

• 现在N = 7,C中的频率为0,5,9,12,13,16,45

• 现在使用min priority queueget 3值.0然后5呢9.

• 添加它们在优先级队列中插入freq = 0 + 9 + 5的新char.这种方式继续.

树将是这样的

         100
        / | \
       /  |  \
      /   |   \
     39   16  45  step-3
   /  | \
  14  12 13  step-2
/ | \  
0 5 9   step-1

最后证明一下

我现在将直接模仿Cormen的证据.

引理1.令C为字母表,其中属于C的每个字符d具有频率c.freq.令x,y和z为具有最低频率的C中的三个字符.然后存在用于C的最佳前缀码,其中x,y和z的码字具有相同的长度并且仅在最后一位中不同.

证明:

理念

• 首先考虑任何树T生成任意最优前缀码.

• 然后我们将修改它以使树形成另一个最佳前缀,使得字符x,y,z在最大深度处显示为兄弟节点.

• 如果我们可以构造这样一个树,那么x,y和z的代码字将具有相同的长度,并且仅在最后一位有所不同.

证明 -

• 设a,b,c为三个字符,即T中最大深度的兄弟叶.

• 不失一般性,我们假设a.freq < b:freq < c.freq和x.freq < y.freq < z.freq.由于x.freq和y.freq以及z.freq是3个最低叶频率,因此在order(means there are no frequencies between them)和a.freq中,b.freq和c.freq是两个任意频率,按顺序,we have x.freq < a:freq and y.freq < b.freq and z.freq< c.freq.

在证明的其余部分,我们可以得到x.freq = a.freq或y.freq = b.freq或z.freq = c.freq.但如果x.freq = b.freq或x.freq = c.freq或y.freq = c.freq则所有这些都是相同的.为什么？？让我们来看看.假设x!=y,y!=z,x!=z但是z = c并且x<y<z按顺序而aa <b <c.也x!=a. --> x<a y!=b. --> y<b z!=c. --> z<c不过z=c是给出.这与我们的假设相矛盾.(因此证明).这个引理很简单.因此,我们假设x!= b和x!= c.

 T1

     *                       |
   / | \                     |
  *  *  x                    +---d(x)
/ | \                        |
y *  z                           +---d(y) or d(z)
 /|\                         |
a b c                        +---d(a) or d(b) or d(c) actually d(a)=d(b)=d(c)

T2
     *              
   / | \
  *  *  a
/ | \
y *  z
 /|\
x b c               

T3

     *              
   / | \
  *  *  x
/ | \
b *  z
 /|\
x y c

T4
     *              
   / | \
  *  *  a
/ | \
b *  c
 /|\
x y z


In case of T1 costt1= x.freq*d(x)+ cost_of_other_nodes + y.freq*d(y) + z.freq*d(z) + d(a)*a.freq + b.freq*d(b) + c.freq*d(c)
In case of T2 costt2= x.freq*d(a)+ cost_of_other_nodes + y.freq*d(y) + z.freq*d(z) + d(x)*a.freq + b.freq*d(b) + c.freq*d(c)
       costt1-costt2= x.freq*[d(x)-d(a)]+0             +    0        +     0       + a.freq[d(a)-d(x)]+0       +    0
                    = (a.freq-x.freq)*(d(a)-d(x))
                    >= 0      
So costt1>=costt2.                    --->(1)

Similarly we can show costt2 >= costt3--->(2)

And                   costt3 >= costt4--->(3)

From (1),(2) and (3) we get 

costt1>=costt4.-->(4)

But T1 is optimal.

So costt1<=costt4 -->(5)

From (4) and (5) we get costt1=costt2.

SO, T4 is an optimal tree in which x,y,and z appears as sibling leaves at maximum depth, from which the lemma follows.

引理-2

令C为给定字母表,其中频率c.freq为属于C的每个字符c定义.令x,y,z为C中具有最小频率的三个字符.假设C1为字母C,删除了字符x和y,并添加了新的字符z1 C1 = C - {x,y,z} union {z1}.将f为C1作为C,所不同的是 z1.freq=x.freq+y.freq+z.freq.令T1为表示字母C1的最佳前缀码的任何树.然后,通过用具有x,y和z作为子节点的内部节点替换z的叶节点而从T1获得的树T表示字母C的最佳前缀码.

证明.:

看看我们正在从T1-> T进行过渡.所以我们必须找到一种方法来表达成本,即成本1.

     *                            *              
   / | \                        / | \
  *  *  *                      *  *  *
/ | \                           / | \
* *  *        ---->             * z1 *
 /|\                            
x y z                                          

对于属于(C- {x,y,z})的c,dT(c)= dT1(c).[深度对应T和T1树]

因此c.freq*dT(c)=c.freq*dT1(c).

以来 dT(x)=dT(y)=dT(z)=dT1(z1)+1

So we have `x.freq*dT(x)+y.freq*dT(y)+z.freq*dT(z)=(x.freq+y.freq+z.freq)(dT1(z)+1)`
                                                  = `z1.freq*dT1(z1)+x.freq+y.freq+z.freq`
Adding both side the cost of other nodes which is same in both T and T1.
x.freq*dT(x)+y.freq*dT(y)+z.freq*dT(z)+cost_of_other_nodes= z1.freq*dT1(z1)+x.freq+y.freq+z.freq+cost_of_other_nodes

So costt=costt1+x.freq+y.freq+z.freq
or equivalently

  costt1=costt-x.freq-y.freq-z.freq ---->(1)

现在我们通过矛盾来证明这个引理.

我们现在通过矛盾来证明这个引理.假设T不表示C的最佳前缀码.那么存在最佳树T2 costt2 < costt.在不失一般性的情况下(通过引理1),T2具有x,y和z作为兄弟.令T3为树T2,其中x的公共父和y和z由具有频率z1.freq=x.freq+y.freq+z.freqThen 的叶z1替换

costt3 = costt2-x.freq-y.freq-z.freq
       <  costt-x.freq-y.freq-z.freq
       =  costt1  (From 1)

与T1代表C1的最佳前缀代码的假设产生矛盾.因此,T必须代表字母C的最佳前缀代码.

-Proved.

过程HUFFMAN生成最佳前缀代码.证据:立即从Lemmas 1和2.

注意:术语来自简介算法第3版Cormen Rivest