哈夫曼树是一种重要的数据结构，用于压缩和编码数据。它由经典的数学家和计算机科学家大卫哈夫曼在20世纪50年代发明。哈夫曼树的目的是为了在编码和解码数据中，尽可能地减少所需的比特数。换句话说，它可以将大量数据压缩为在传输过程中所需的最小比特数。

在NLP领域的词向量开篇制作Word2Vec中用到了一种softmax优化方法——层次softmax，就是将词频编码成哈夫曼树的形式，然后，（以skip-gram为例）在样本[v, w]进入模型前，将周围词w，基于哈夫曼树映射成从根到叶路径两个方向路径right_path=[p1, p2]; left_path=[n1, n2]，最终组成[[v, p1], [v, p2]]; [[v, n1], [v, n2]，最后以v, p, v, n 四个一维向量的方式进入模型。

一、哈夫曼树构建伪代码

哈夫曼树的构建过程非常简单，可以分为以下几个步骤：

1. 根据数据出现的频率创建叶子节点，频率越高的字母对应的节点越靠近根节点。
2. 对于两个字符的节点（由频率最低的字符所对应的节点）之间创建一个父节点。父节点的权重等于其两个子节点权重之和。
3. 重复步骤2，直到所有的节点都被合并到同一个根节点下。

哈夫曼树构建图示

二、哈夫曼树构建python

借助优先队列headq 便于快速输出最小的2个节点

import heapq class Node: def __init__(self, idx, freq, char, left, right):self.idx = idxself.freq = freqself.char = charself.left = leftself.right = rightdef __lt__(self, other): return self.freq < other.freq def __str__(self):return f'Node([{self.idx}]({self.char}/{self.freq}), left={self.left}, right={self.right})'def __repr__(self):return str(self)def build_huffman_tree(data=None, freq_map=None): if freq_map is None:freq_map = dict() for char in data: freq_map[char] = freq_map.get(char, 0) + 1 print(freq_map)word_map = [Node(idx, freq, char, None, None) for idx, (char, freq) in enumerate(freq_map.items())] min_node = min(word_map)print(min_node)print('len(word_map)=', len(word_map))# 初始化 因为heappop 会先输出第一个元素node_heap = [min_node] + [Node(idx, freq, char, None, None) for idx, (char, freq) in enumerate(freq_map.items()) if char != min_node.char] # 构建哈夫曼树while len(node_heap) > 1: # 优先队列， 弹出最小的2个left_node = heapq.heappop(node_heap) right_node = heapq.heappop(node_heap) freq_sum = left_node.freq + right_node.freq idx = len(word_map)# 左大右小combined_node = Node(idx, freq_sum, None, right_node, left_node) heapq.heappush(node_heap, combined_node) word_map.append(combined_node)# 哈夫曼树最后print('len(word_map)=', len(word_map))return node_heap[0], word_mapif __name__ == "__main__":test_dict = {'a': 6, 'b': 3,'c': 4, 'd': 2}huffman_tree, total_word_map = build_huffman_tree(freq_map=test_dict) print(huffman_tree)

结果

res = """
Node([6](None/15), left=Node([5](None/9), left=Node([4](None/5), left=Node([1](b/3), left=None, right=None), right=Node([3](d/2), left=None, right=None)), right=Node([2](c/4), left=None, right=None)), right=Node([0](a/6), left=None, right=None)
)
"""