python - 优化二叉树函数，霍夫曼树

Question

所以场景是你认识的人给你一棵哈夫曼树，但它不是最优的(我知道所有哈夫曼树都是最优的，只是假设它不是最​​优的，但确实遵循只有叶子有值的哈夫曼风格)。

该函数应该在不改变树的实际“形状”的情况下，借助字典将每个符号映射到它在您正在压缩的假设文本中出现的次数，尽可能地改进树。该函数通过交换节点来实现这一点。所以最终的结果不一定是最优的树，但会尽可能地改进。例如......

Class Node:
    def __init__(self, item = None, left = None, right = None):
        self.item = item
        self.left = left
        self.right = right

     def __repr__(self):
         return 'Node({}, {}, {})'.format(self.item, self.left, self.right)

字典 = {54: 12, 101: 34, 29: 22, 65: 3, 20: 13}

你的 friend 给你...

节点(无，节点(无，节点(20)，节点(54))，节点(无，节点(65)，节点(无，节点(101)，节点(29)))

或者...

               None  
          /     |     \
     None       |       None
   /      \     |     /      \
20          54  |  65       None
                |         /      \
                |      101        29

想要的结果是......

节点(无，节点(无，节点(20)，节点(29))，节点(无，节点(101)，节点(无，节点(65)，节点(54)))

或者...

               None  
          /     |     \
     None       |       None
   /      \     |     /      \
20          29  |  101       None
                |         /      \
                |       65        54

如何定位叶节点，然后找到它应该在的位置，交换它，然后对所有其他叶节点执行此操作，同时确保树的形状相同，无论它是否是最佳的？这也是Python中的。

Answer 1

来自basic technique在构造哈夫曼树时，值概率最小的节点是第一个链接到父节点的节点。这些节点在霍夫曼树中出现得比其中的任何其他节点更深。由此，我们可以推断出这样一个事实:树越深入，遇到的值就越少。

这个类比对于开发优化函数至关重要，因为我们不需要执行各种交换，当我们可以通过以下方式第一次就正确时:获取树中按深度排序的所有项目的列表，并且它们的匹配值按顺序排列；当有叶子时，将它们插入各自的深度。这是我编码的解决方案:

def optimize_tree(tree, dictionary):

    def grab_items(tree):
        if tree.item:
            return [tree.item]
        else:
            return grab_items(tree.left) + grab_items(tree.right)

    def grab_depth_info(tree):
        def _grab_depth_info(tree,depth):
            if tree.item:
                return {depth:1}
            else:
                depth_info_list = [_grab_depth_info(child,depth+1) for child in [tree.left, tree.right]]
                depth_info = depth_info_list[0]
                for depth in depth_info_list[1]:
                    if depth in depth_info:
                        depth_info[depth] += depth_info_list[1][depth]
                    else:
                        depth_info[depth] = depth_info_list[1][depth]
                return depth_info

        return _grab_depth_info(tree,0)

    def make_inverse_dictionary(dictionary):
        inv_dictionary = {}
        for key in dictionary:
            if dictionary[key] in inv_dictionary:
                inv_dictionary[dictionary[key]].append(key)
            else:
                inv_dictionary[dictionary[key]] = [key]

        for key in inv_dictionary:
            inv_dictionary[key].sort()

        return inv_dictionary

    def get_depth_to_items(depth_info,actual_values):
        depth_to_items = {}
        for depth in depth_info:
            depth_to_items[depth] = []
            for i in range(depth_info[depth]):
                depth_to_items[depth].append(actual_values[i])

            depth_to_items[depth].sort()
            del actual_values[:depth+1]

        return depth_to_items

    def update_tree(tree,depth_to_items,reference):
        def _update_tree(tree,depth,depth_to_items,reference):
            if tree.item:
                tree.item = reference[depth_to_items[depth].pop(0)].pop(0)
            else:
                for child in [tree.left,tree.right]:
                    _update_tree(child,depth+1,depth_to_items,reference)
        _update_tree(tree,0,depth_to_items,reference)

    items = grab_items(tree)
    depth_info = grab_depth_info(tree)
    actual_values = [dictionary[item] for item in items]
    actual_values.sort(reverse=True)
    inv_dictionary = make_inverse_dictionary(dictionary)

    depth_to_items = get_depth_to_items(depth_info,actual_values)

    update_tree(tree,depth_to_items,inv_dictionary)

说明:

optimize_tree 函数要求用户传入两个参数:

• tree:哈夫曼树的根节点。
• 字典:将符号映射到其频率的字典。

该函数首先定义四个内部函数:

• grab_items 是一个函数，它接受树并返回其中所有项目的列表。
• grab_depth_info 返回一个字典，其中键是深度级别，值是该级别的节点数。
• make_inverse_dictionary 返回给定字典的逆字典。 (它可以处理值可以映射到两个键的情况。)
• get_depth_to_items 返回一个字典，其中键是深度级别，值是实际值列表(来自字典)，这些值应该位于该级别以便优化树.
• update_tree 将项目插入到应有的位置，以便优化树。

注意:grab_depth_info 和 update_tree 中定义了一个内部函数，以便它们的功能可以递归地工作。

以下算法需要这四个内部函数:

1. 首先，该函数从树中获取项目列表和深度信息。
2. 然后它使用项目列表从给定字典中获取实际值列表，并按降序排列。 (以便将最不频繁的值与步骤 4 中的最大深度级别相匹配。)
3. 接下来，它对给定的字典进行逆操作，其中键和值被交换。 (这有助于完成第 5 步。)
4. 完成这些准备工作后，该函数会将深度信息和实际值列表传递给 get_depth_to_items 函数，以获取深度级别字典到 inorder 值列表。
5. 最后，该函数将树、上一步中创建的字典以及倒排字典传入 update_tree 函数，该函数将使用其内部函数递归地访问树并使用倒排字典中的原始键更新项目属性。

使用该算法的结果将使您传入的树处于最优化的状态，而不会改变它的实际形状。

<小时/>

我可以通过执行以下代码行来确认这是否有效:

tree = Node(None, Node(None, Node(20), Node(29)), Node(None, Node(101), Node(None, Node(65), Node(54))))
dictionary = {54: 12, 101: 34, 29: 22, 65: 3, 20: 13}
optimize_tree(tree,dictionary)
print(tree)

其输出是:

Node(None, Node(None, Node(20, None, None), Node(29, None, None)), Node(None, Node(101, None, None), Node(None, Node(65, None, None), Node(54, None, None))))