python - 将列表映射到霍夫曼树，同时保留相对顺序

Question

我在哈夫曼树上的搜索算法有问题:对于给定的概率分布，无论输入数据的排列如何，我都需要哈夫曼树是相同的。

这是正在发生的事情与我想要的事情的对比图:

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

作为引用，我使用哈夫曼树根据概率划分生成子组，以便我可以运行下面的 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)

使用以下类:

class Node(object):
    left = None
    right = None
    weight = None
    data = None
    code = None

    def __init__(self, w,d):
        self.weight = w
        self.data = d

    def set_children(self, ln, rn):
        self.left = ln
        self.right = rn

    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 merge(self, other):
        total_freq = self.weight + other.weight
        new_data = self.data + other.data
        return Node(total_freq,new_data)

    def index(self, node):
        return node.weight

def encode(symbfreq):
    pdb.set_trace()
    tree = [Node(sym,wt) for wt,sym in symbfreq]
    heapify(tree)
    while len(tree)>1:
        lo, hi = heappop(tree), heappop(tree)
        n = lo.merge(hi)
        n.set_children(lo, hi)
        heappush(tree, n)
    tree = tree[0]

    def assign_code(node, code):
        if node is not None:
            node.code = code
        if isinstance(node, Node):
            assign_code(node.left, code+'0')
            assign_code(node.right, code+'1')

    assign_code(tree, '')
    return tree

我得到:

'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 .

这样做的主要原因是为了让霍夫曼码的传输更加紧凑。无需将每个符号的代码与压缩数据一起发送，您只需发送每个符号的代码长度。然后在另一端重构代码进行解压。

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

至于你的树，当频率相等时会做出任意选择。特别是，在第二步中，拉出的第一个节点是 c概率为 0.2，拉出的第二个节点是 b概率为 0.25。然而，拉取而不是 b 也同样有效。 ，第一步制作的节点，(e,d) ，其概率也是 0.25。事实上，这就是您希望达到的最终状态。 las，您已经放弃了对 heapq 的任意选择的控制。图书馆。

(注意:由于您使用的是浮点值，因此 0.1 + 0.15 不一定完全等于 0.25。尽管事实证明是。再举一个例子，0.1 + 0.2 不等于0.3. 如果你想看看当频率总和等于其他频率或频率总和时会发生什么，你最好使用整数作为频率。例如 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在 c 之前.那么排序是adebc .

现在想想，就算你选(e,d)在 b ，例如通过设置 b 的概率到 0.251，你仍然没有得到你想要的完整订单。不管怎样，(e,d)的概率(0.25) 大于 c 的概率(0.2)。所以即使在那种情况下，最终的排序也是(通过上面的修复)abdec而不是你想要的 abcde .因此，不可能得到你想要的东西，假设树排序和位分配与符号组的概率一致。例如，假设对于每个分支，左边的东西比右边的东西有更大或相等的概率，0 总是分配给左边，1 总是分配给右边。您需要做一些不同的事情。

想到的不同的事情是我在答案开头所说的。使用霍夫曼算法只是为了获得代码长度。然后您可以按照您喜欢的任何顺序将代码分配给符号，并构建一棵新树。这比试图想出某种方案来强制原始树成为您想要的并证明它在所有情况下都有效要容易得多。