将列表映射到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

我将用工作代码充实马克·阿德勒所说的话。他说的每一句话都是对的：-）要点：

1. 不能使用浮点权重或任何其他丢失权重信息的方案。使用整数。简单而正确。例如，如果你有3位数的浮动概率，通过int(round(the_probability * 1000))将每一个概率转换成一个整数，那么也许可以调整它们以确保总和正好是1000。在
2. heapq堆不是“稳定的”：如果多个项具有相同的最小权重，则不会定义弹出哪个项。在
3. 所以你在建树的时候就不能得到你想要的东西。在
4. “规范哈夫曼密码”的一个小变种似乎是你想要的。为此构建一棵树是一个冗长的过程，但每一步都足够简单。构建的第一棵树被丢弃：从中获取的唯一信息是分配给每个符号的代码的长度。在

运行中：

syms = ['a','b','c','d','e']
weights = [30, 25, 20, 15, 10]
t = encode(syms, weights)
print t

打印此文件（格式化以便于阅读）：

^{pr2}$

据我所知，这正是你想要的。如果不是，就抱怨；-）

编辑：在规范代码的赋值中有一个错误，除非权重非常不同，否则不会显示出来；修复了它。在

class Node(object):
    def __init__(self, data=None, weight=None,
                       left=None, right=None,
                       code=None):
        self.data = data
        self.weight = weight
        self.left = left
        self.right = right
        self.code = code

    def is_symbol(self):
        return self.left is self.right is None

    def __repr__(self):
        return "[%s,%s,(%s),(%s)]" % (self.data,
                                      self.code,
                                      self.left,
                                      self.right)

    def __cmp__(self, a):
        return cmp(self.weight, a.weight)

def encode(syms, weights):
    from heapq import heapify, heappush, heappop

    tree = [Node(data=s, weight=w)
            for s, w in zip(syms, weights)]
    sym2node = {s.data: s for s in tree}
    heapify(tree)
    while len(tree) > 1:
        a, b = heappop(tree), heappop(tree)
        heappush(tree, Node(weight=a.weight + b.weight,
                            left=a, right=b))

    # Compute code lengths for the canonical coding.
    sym2len = {}
    def assign_codelen(node, codelen):
        if node is not None:
            if node.is_symbol():
                sym2len[node.data] = codelen
            else:
                assign_codelen(node.left, codelen + 1)
                assign_codelen(node.right, codelen + 1)
    assign_codelen(tree[0], 0)

    # Create canonical codes, but with a twist:  instead
    # of ordering symbols alphabetically, order them by
    # their position in the `syms` list.
    # Construct a list of (codelen, index, symbol) triples.
    # `index` breaks ties so that symbols with the same
    # code length retain their original ordering.
    triples = [(sym2len[name], i, name)
                for i, name in enumerate(syms)]
    code = oldcodelen = 0
    for codelen, _, name in sorted(triples):
        if codelen > oldcodelen:
            code <<= (codelen - oldcodelen)
        sym2node[name].code = format(code, "0%db" % codelen)
        code += 1
        oldcodelen = codelen

    # Create a tree corresponding to the new codes.
    tree = Node(code="")
    dir2attr = {"0": "left", "1": "right"}
    for snode in sym2node.values():
        scode = snode.code
        codesofar = ""
        parent = tree
        # Walk the tree creating any needed interior nodes.
        for d in scode:
            assert parent is not None
            codesofar += d
            attr = dir2attr[d]
            child = getattr(parent, attr)
            if codesofar == scode:
                # We're at the leaf position.
                assert child is None
                setattr(parent, attr, snode)
            elif child is not None:
                assert child.code == codesofar
            else:
                child = Node(code=codesofar)
                setattr(parent, attr, child)
            parent = child

    # Finally, paste the `data` attributes together up
    # the tree.  Why?  Don't know ;-)
    def paste(node):
        if node is None:
            return ""
        elif node.is_symbol():
            return node.data
        else:
            result = paste(node.left) + paste(node.right)
            node.data = result
            return result
    paste(tree)

    return tree

重复符号

Could I swap the sym2node dict to an ordereddict to deal with repeated 'a'/'b's etc?

不，有两个原因：

1. 没有映射类型支持重复键；并且
2. “重复符号”的概念对哈夫曼编码毫无意义。在

所以，如果你下定决心要追求这个目标，首先你必须确保符号是唯一的。只需在函数的开头添加以下行：

        syms = list(enumerate(syms))

例如，如果传入的syms是：

['a', 'b', 'a']

将更改为：

[(0, 'a'), (1, 'b'), (2, 'a')]

现在所有的符号都是2元组，而且显然是唯一的，因为每个符号都以唯一的整数开头。算法关心的唯一问题是符号可以用作dict键；它不关心它们是字符串、元组还是任何其他支持等式测试的散列类型。在

所以算法中没有什么需要改变的。但在结束之前，我们要恢复原来的符号。只需在paste()函数之前插入：

    def restore_syms(node):
        if node is None:
            return
        elif node.is_symbol():
            node.data = node.data[1]
        else:
            restore_syms(node.left)
            restore_syms(node.right)
    restore_syms(tree)

它只需遍历树并从符号的.data成员中去掉前导整数。或者，也许更简单，只需迭代sym2node.values()，并转换每个成员的.data成员。在

Answer 2

通常的做法是使用哈夫曼算法只生成代码长度。然后使用规范化过程从长度中生成代码。这棵树被丢弃了。代码按从短代码到长代码的顺序分配，在代码中，符号被排序。这将给出您期望的代码，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总是分配给右边。你需要做些不同的事情。在

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