二叉树与赫夫曼图片压缩实践vscode

### 使用VSCode进行基于二叉树和赫夫曼编码的图像压缩

#### 安装必要的扩展和库
为了在 VSCode 中实现赫夫曼编码算法并处理图像文件，建议安装 Python 扩展以及一些常用的科学计算库：

1. 安装Python插件以便支持代码编写与调试功能。
2. 通过命令 `pip install numpy pillow` 来安装 NumPy 和 Pillow 库用于矩阵运算及图像读取。

#### 赫夫曼编码原理简介
赫夫曼编码是一种变长编码方法，其核心在于构建一颗最优前缀码树——即赫夫曼树。该过程涉及统计字符频率、创建节点对象并将它们组合成一棵具有最小加权路径长度的二叉树[^1]。

#### 实现赫夫曼编码的核心函数
下面是一个简单的 Python 函数来展示如何利用字典结构模拟赫夫曼表，并定义了几个辅助类来进行数据封装:

import heapq
from collections import defaultdict, Counter


class Node(object):
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        return self.freq < other.freq
    

def build_huffman_tree(frequencies):
    heap = [Node(char=c, freq=f) for c,f in frequencies.items()]
    heapq.heapify(heap)

    while len(heap) != 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        
        merged_node = Node(left=lo, right=hi, freq=(lo.freq + hi.freq))
        heapq.heappush(heap, merged_node)

    return heap[0]


def generate_codes(node, prefix="", codebook={}):
    if node is not None:
        if node.char is not None:
            codebook[node.char] = prefix
        
        generate_codes(node.left , prefix+"0", codebook)
        generate_codes(node.right, prefix+"1", codebook)

    return codebook

此部分实现了赫夫曼树的建立及其对应的编码映射关系生成逻辑[^2]。

#### 图像预处理与转换
对于彩色图像而言，在应用赫夫曼编码之前通常会先将其转化为灰度图以简化问题复杂度；接着可以将像素值视为待编码的信息源，进而调用上述编解码接口完成整个流程。

from PIL import Image
import numpy as np


def image_to_grayscale(image_path):
    img = Image.open(image_path).convert('L')
    pixels = list(img.getdata())
    
    width, height = img.size
    pixel_matrix = np.array(pixels).reshape((height, width))

    return pixel_matrix.flatten().tolist(), (width, height)


def grayscale_to_image(pixel_list, size):
    array = np.array(pixel_list).reshape(size[::-1])
    img = Image.fromarray(array.astype(np.uint8), 'L')

    return img

这些工具函数可以帮助加载图片资源并对之执行基本变换操作[^3]。

#### 编写完整的图像压缩程序
最后一步就是把前面提到的功能模块串联起来形成一套完整的解决方案。这里提供了一个简化的版本供参考学习用途：

if __name__ == "__main__":
    # 加载原始图像并转为一维列表形式
    flat_pixels, original_size = image_to_grayscale("example.png")

    # 统计各颜色出现次数作为权重输入给赫夫曼算法
    frequency_dict = dict(Counter(flat_pixels))

    # 构建赫夫曼树并获取对应编码规则
    huffman_root = build_huffman_tree(frequency_dict)
    codes_table = generate_codes(huffman_root)

    encoded_data = ''.join([codes_table[pixel] for pixel in flat_pixels])

    print("Original Size:", len(flat_pixels)*8,"bits")
    print("Compressed Size:",len(encoded_data),"bits")

这段脚本展示了从准备阶段到最终输出压缩效果评估的整体工作流[^4]。