Huffman Tree

定义 Definition

Huffman tree（哈夫曼树）：一种用于无损数据压缩的二叉树结构，通过让高频符号使用更短的二进制编码、低频符号使用更长的编码，实现接近最优的前缀码（prefix code）编码方案。常见于 Huffman coding（哈夫曼编码）。

发音 Pronunciation (IPA)

/ˈhʌfmən triː/

例句 Examples

A Huffman tree helps compress text by assigning shorter codes to common letters.
哈夫曼树通过给常见字母分配更短的编码来帮助压缩文本。

In many compressors, the Huffman tree is built from symbol frequencies, and decoding works by walking the tree bit by bit.
在许多压缩器中，哈夫曼树根据符号频率构建，解码时则按位读取并在树上逐步遍历。

词源 Etymology

“Huffman”来自提出该算法的美国计算机科学家 David A. Huffman（大卫·哈夫曼），他在 1952 年发表的经典论文中给出了构造最小冗余（minimum-redundancy）编码的方法；“tree”指该方法用树形结构来表示前缀码的分支与叶子（符号）。

相关词 Related Words

• Binary Tree
• Prefix Code
• Huffman Coding
• Entropy
• Frequency
• Lossless Compression
• Greedy Algorithm
• Codeword

文学与作品 Literary Works

• A Method for the Construction of Minimum-Redundancy Codes（1952，David A. Huffman）——提出哈夫曼编码及其树的构造思想。
• Introduction to Algorithms（常称 CLRS）——在贪心算法/编码相关章节中常以哈夫曼树作为经典案例。
• Data Compression: The Complete Reference（David Salomon 等）——系统介绍哈夫曼树在压缩格式与实现中的应用。