将列表映射到Huffman树，同时保留相对ord

Question

我对Huffman树上的搜索算法有一个问题：对于给定的概率分布，我需要Huffman树是相同的，而不考虑输入数据的排列。在

下面是一张正在发生的事情与我想要的结果的对比图：

基本上，我想知道是否可以保留从列表到树的项目的相对顺序。如果没有，为什么会这样？在

作为参考，我使用Huffman树根据概率的划分生成子组，以便我可以运行下面的search（）过程。请注意，merge（）子例程中的数据与权重一起组合。码字本身没有树那么重要（树应该保持相对顺序）。在

例如，如果我生成以下哈夫曼代码：

probabilities = [0.30, 0.25, 0.20, 0.15, 0.10]
items = ['a','b','c','d','e']
items = zip(items, probabilities)
t = encode(items)
d,l = hi.search(t)
print(d)

使用以下类：

^{pr2}$

我得到：

'a'->11
'b'->01
'c'->00
'd'->101
'e'->100

然而，我在搜索算法中做的一个假设是，更多可能的项目会被推到左边：也就是说，我需要'a'来包含'00'码字-不管'abcde'序列的任何排列，都应该是这样。输出示例如下：

codewords = {'a':'00', 'b':'01', 'c':'10', 'd':'110', 'e':111'}

（注意，即使“c”的代码字是“d”的后缀，这也没问题）。在

为了完整起见，以下是搜索算法：

def search(tree):
    print(tree)
    pdb.set_trace()
    current = tree.left
    other = tree.right
    loops = 0
    while current:
        loops+=1
        print(current)
        if current.data != 0 and current is not None and other is not None:
            previous = current
            current = current.left
            other = previous.right
        else:
            previous = other
            current = other.left
            other = other.right
    return previous, loops

它的工作原理是在一组0和1中搜索“最左边的”1—哈夫曼树必须将更多可能的项目放在左边。例如，如果我使用上述概率和输入：

items = [1,0,1,0,0]

那么算法返回的项的索引是2—这不是应该返回的值（0应该，因为它是最左边的）。在

Answer 1

通常的做法是使用哈夫曼算法只生成代码长度。然后使用规范化过程从长度中生成代码。这棵树被丢弃了。代码按从短代码到长代码的顺序分配，在代码中，符号被排序。这将给出您期望的代码，a = 00，b = 01，等等，这称为Canonical Huffman code。在

这样做的主要原因是为了使哈夫曼代码的传输更紧凑。您只需发送每个符号的代码长度，而不必随压缩数据一起发送每个符号的代码。然后可以在另一端重建代码进行解压缩。在

哈夫曼树通常也不用于解码。对于规范代码，通过简单的比较来确定下一个代码的长度，使用代码值的索引将直接指向符号。或者表驱动的方法可以避免搜索长度。在

至于你的树，当频率相等时，会有任意的选择。具体地说，在第二步中，拉入的第一个节点是概率为0.2的c，被拉的第二个节点是概率为0.25的{}。然而，同样有效的方法是拉取第一步中生成的节点，而不是b，其概率为也0.25。事实上，这就是你想要的最终状态。唉，您已经将任意选择的控制权交给了heapq库。在

（注意：由于使用的是浮点值，0.1+0.15不一定完全等于0.25。尽管事实证明是这样。作为另一个例子，0.1+0.2等于0.3。如果你想知道当频率之和等于其他频率或频率之和时会发生什么，最好对频率使用整数。E、 g.6,5,4,3,2.）

一些错误的顺序可以通过纠正一些错误来修复：将lo.merge(high)改为hi.merge(lo)，并将位的顺序颠倒为：assign_code(node.left, code+'1')，然后再assign_code(node.right, code+'0')。那么至少a被赋值为00，d在e之前，b在{}之前。顺序是adebc。在

现在我想一想，即使你选择(e,d)而不是b，例如通过将b的概率设置为0.251，你仍然得不到你所追求的完整顺序。不管怎样，(e,d)（0.25）的概率大于{}的概率（0.2）。因此，即使在这种情况下，最终的顺序也是（通过上面的修复）abdec，而不是您想要的abcde。因此，不可能得到您想要的结果，假设与符号组的概率有关的树排序和位分配是一致的。E、 g.假设对于每个分支，左边的东西比右边的东西有更大或相等的概率，0总是分配给左边，1总是分配给右边。你需要做些不同的事情。在

我想到的另一件事是我在答案开始时说的话。使用哈夫曼算法只是为了得到代码长度。然后你可以把代码按你喜欢的顺序分配给符号，然后建立一个新的树。这比试图想出某种方案来强迫原始树成为您想要的并证明它在所有情况下都有效要容易得多。在