假设我们必须为文本中的每一个字符赋予一串称为代码字(codeword)的比特位，对 $n$ 个不同字符组成的文本进行编码，并且这些字符都来自于某张字母表。例如，我们可以使用一种定长编码(fxed-length encoding)，对每个字符赋予一个长度同为 $m (m≥ log_2 n)$ 的位串。
这就是标准ASCII码的原理。为了产生平均长度最短的位串，有一种基于古老思想的编码 生成方案，它把较短的代码字分配给更常用的字符，把较长的代码字分配给较不常用的字 符。[具体来说，19世纪中叶塞缪尔●摩斯(Samuel Morse)发明的电报码中就应用了这个思想。在摩斯码中，像e(·)和a(-)这样的常用字符被赋予了点划组成的短序列，而像q(---) 和z(--·)这样的不常用字符则赋予了长序列。]
如果使用变长编码(variable-length encoding)，则会遇到定长编码不曾有的一种问题，它要求对不同的字符赋予长度不同的代码字。也就是说，如何能知道编码文本中用了多少位来代表第一一个字符(或者更一般地来说， 是第 $i$ 个字符)呢? 为了防止问题复杂化，我们只讨论自由前缀码(prefix-free code，或者简称为prefix code，即前缀码)。在前缀码中，所有的代码字都不是另一个字符代码字的前缀。因此，经过这样的编码，可以简单地扫描一个位串，直到得到一组等于某个字符代码字的比特位，用该字符替换这些比特位，然后重复上述操作，直到达到位串的末尾。
如果打算对某个字母表创建一套二进制前缀码，很自然地可以把字母表中的字符和一 棵二叉树的叶子联系起来，树中所有的左向边都标记为 $0$，而所有的右向边都标记为 $1$。可以通过记录从根到字符叶子的简单路径上的标记来获得-个字符的代码字。因为从一个叶 子到另一个叶子的连续简单路径不存在，所以一个代码字不可能是另一个代码字的前缀， 也就是说，任何这样的树都会生成一套前缀码。 如果已知字符的出现概率，可以按照这种方式构造许多棵代表给定字母表的树，但如. 何构造一棵将较短位串分配给高频字符，将较长位串分配给低频字符的树呢?我们可以根 据下面的贪婪算法来构造：
哈夫曼算法
- 第一步: 初始化n个单节点的树，并为它们标上字母表中的字符。把每个字符的概率记在树的根中，用来指出树的权重(更一般地来说，树的权重等于树中所有叶子的概率之和)。
- 第二步: 重复下面的步骤，直到只剩一棵单独的树。找到两棵权重最小的树(对于权重相同的树，可任意选择其一)。把它们作为新树中的左右子树，并把其权重之和作为新的权重记录在新树的根中。
根据给定的出现概率和求得的代码字的长度，在这套编码中，每个字符的平均位长是 $2\times 0.35+ 3 \times 0.1+ 2 \times 0.2+ 2 \times 0.2 +3 \times 15= 2.25$ 如果我们用定长编码表示相同的字母表，对于每一一个字符至少要用 3位来表示。因此，对 于这个简单的例子，哈夫曼编码实现的压缩率(compression ratio，这是压缩算法效率的一种 标准度量指标)是$[(3 - 2.25)/3]\times100% = 25%$。换句话说，我们可以指望一个文本的哈夫曼编码要比其定长编码少占用25%的存储空间(哈夫曼编码的大量实验告诉我们，这种方法的压缩率一般为20%~80%，这依赖于所压缩文本中的字符)。
必须知道，哈夫曼算法的应用并不仅限于数据压缩。假设有 $n$ 个正数 $w_1，w_2，...，w_n$， 要把它们分配给一棵二叉树的 $n$ 个叶子，每个叶子一个数。如果把**加权路径长度(weighted path length)**定义为 $\sum_{i=1}^{n}l_iw_i$ ，其中 $l_i$ 是从根到第 $i$ 个叶子的简单路径的长度，如何构造一棵具有最小加权路径长度的二叉树呢? 这正是哈夫曼算法要解决的一一个更一般性的问题。(对于 编码问题来说，$l_i$ 和$w_i$分别是代码字的长度和第 $i$ 个字符的出现概率。)
这种问题出现在包括决策在内的许多场合。作为一个例子，考虑从 $n$ 个可能目标中猜测一个选定目标的游戏(例如猜测一个$1 \sim n$的整数)，玩家可以问一些能够回答是或者否的问题。由于玩这个游戏的策略不同，可以建立不同的**决策树(decision tree)**模型，就像下图给出的 $n=4$ 的树。在这样的树中，从根到一个叶子的最短路径长度，就是为了确定叶子所代表的数字需要提问的问题个数。如果数字 $i$ 被选中的概率为 $p_i$， 求和式 $\sum_{i=1}^{n}l_ip_i$ (其中 $l_i$是 $i=1$ 从根到第 $i$ 个叶子的路径长度)表示根据决策树代表的游戏策略，为了“猜出”选定的数字平均需要问的问题个数。如果每个数字被选中的概率都是$1/n$，最佳的策略就是像二叉树那样，连续把候选元素消去一半(或者几乎一 半)。但对于任意 $p_i$ 来说，情况可能并不是这 样的(例如，如果 $n=4$ 并且 $p_1=0.1， p_2=0.2， p_3=0.3， p_4= 0.4$，它的最小加权路径树就是下图中最右面的那一稞)。因此，为了在一般的情况下解题，我们需要使用哈夫曼算法。