贪心算法是一种启发式(Heuristic)算法, 它的基本思想是在每一步决策时选择局部最优的策略. 贪心算法一般在设计和实现上比较容易, 因此在求解实际问题中应用广泛.

编码问题

考虑如下的编码问题: 给定字符的集合$C$, 例如 C = { a , b , c , d , e } C=\{a, b, c, d, e\} C={a,b,c,d,e}. 每个字符$\alpha \in C$的使用频次为$f_{\alpha }$. 我们需要给每个字符$\alpha \in C$进行二进制编码(字符$\alpha$对应的编码长度记作$l_{\alpha }$). 总的编码长度的计算公式为: $L={\sum }_{\alpha \in C}{f}_{\alpha }\cdot l_{\alpha }$. 我们的目标是设计一种编码使得总的编码长度最小.

	a	b	c	d	e	f
频次	45	13	12	16	9	5
定长编码	000	001	010	011	100	101
变长编码	0	101	100	111	1101	1100

如上表所示, 考虑两种编码: 定长编码和变长编码. 其中变长编码为前缀码: 任一字符的编码不是另一字符编码的前缀.

• 定长编码总长度: 300bits
• 变长编码总长度: 224bits

变长编码的解码过程如下: 根据字符编码构造一棵二叉树, 每一个二进制位代表一个分支(和对应的节点), 其中0代表向左分支, 1代表向右分支, 叶子节点代表字符. 解码时从根节点开始搜索直到叶子节点, 则完成一个字符的解码. 例如: 110001001101 = face.

Huffman编码

为了方便理解, 我们把上述编码问题换一种表达方式. 令$T$代表变长码对应的二叉树, $d_{\alpha }^T$代表叶子节点$\alpha$的深度(Depth, 即编码长度). 我们的目标是构造二叉树$T^{\ast }$, 使得${\sum }_{\alpha \in C}{d}_{\alpha }^{T^{\ast }}{f}_{\alpha }$最小化.

通过分析(过程省略, 详细请参考¹), 我们有如下结论

• Lemma1. $T^{\ast }$的每个内部点(即非叶子节点)有两个节点. （反证法)
• Lemma2. $T^{\ast }$有|C|个叶子节点(对应每个字符)和$|C|-1$个内部点(Lemma1).

根据Lemma2, 我们从下到上构建二叉树. 注意到节点的深度代表了编码的长度, 因此频次越低的字符所在的节点越深.

算法

从$C$中弹出2个频次最低的字符$\alpha ,\beta$, 并构造新的节点$\alpha \beta$, $f_{\alpha \beta }=f_{\alpha }+f_{\beta }$, 作为$\alpha$和$\beta$的父节点, 再把$\alpha \beta$加入到$C$中. 循环执行上述步骤直到$C$为空(注意: 循环次数为$n-1$次).

Python实现

定义二叉树的节点类Node.

class Node(object):

    def __init__(self):
        # data
        self.char = None  # character
        self.freq = None  # frequency
        # pointers
        self.left = None  # left child
        self.right = None  # right child

HuffmanCodes类实现对字符串的编码与解码. 编码本质上是按照上述贪心算法自下而上构建二叉树(参考HuffmanCodes._build_binary_tree()). 解码时从二叉树的根节点搜索到叶子节点(0-代表left child, 1代表-right child), 从而得到对应的字符(HuffmanCodes._decode).

import queue


class HuffmanCodes(object):

    def __init__(self, c, f):
        """
        :param c: characters, str list
        :param f: frequencies, int list
        """
        self._c = c
        self._f = f
        self._n = len(self._c)
        self._q = self._init_priority_queue()
        self._root = None  # encoding tree
        self._huffman_codes = {}  # 编码结果
        self._build_binary_tree() # 构建二叉树
        self._format_huffman_codes()  # 保存编码结果

    def _init_priority_queue(self):
        """ 初始化优先队列.
        priority = frequency, value = node
        使用优先队列可以在O(log n)内返回队列的最小值(代价是插入元素的耗时为O(log n)).
        """
        q = queue.PriorityQueue()
        for item in zip(self._c, self._f):
            v = Node()
            v.char, v.freq = item[0], item[1]
            q.put((v.freq, v))
        return q

    def _build_binary_tree(self):
        """ 自下而上构建二叉树.
        Greedy: 每一步从未被连接的节点中, 选择频次(frequency)最小的两个节点合并(作为新的节点).
        """
        for i in range(self._n - 1):
            z = Node()
            # 从队列里弹出两个最小权重的节点,合并成新的节点z
            z.left = self._q.get()[1]
            z.right = self._q.get()[1]
            z.freq = z.left.freq + z.right.freq
            # 把z插入到队列中
            self._q.put((z.freq, z))
        # 执行n-1步之后, 队列q剩下一个元素,即二叉树的根节点.
        self._root = self._q.get()[1]

    def _format_huffman_codes(self):
        """ 把每一个字符对应的编码保存在字典中(self._huffman_codes)
   		"""
        temp = []

        def traverse(v, res):
            if v.left is None and v.right is None:
                self._huffman_codes[v.char] = ''.join(res)
                return
            res.append('0')
            traverse(v.left, res)
            res.pop(-1)
            res.append('1')
            traverse(v.right, res)
            res.pop(-1)

        traverse(self._root, temp)

    def encode(self, chars):
        """ 把字符串chars转换成Huffman codes.
        """
        return ''.join([self._huffman_codes[c] for c in chars])

    def decode(self, codes):
        """ 把0/1编码(字符串格式)转换成字符串.
        """
        res = []
        v = self._root
        for c in codes:
            if c == '0':
                v = v.left
            elif c == '1':
                v = v.right
            if v.left is None and v.right is None:
                res.append(v.char)
                v = self._root

        return ''.join(res)

完整代码

Remark

为了更好的理解贪心算法, 我们考虑两个问题:

1. 给定一个问题$P$和求解$P$的贪心算法$A$. $A$是否返回$P$的最优解？

基本的思路是采用反证法. 假设$A$得到的解不是最优解, 那么存在$k>0$, 算法$A$在第$k$步决策时没有采用局部最优策略, 按照这个思路如果得出矛盾, 那么最有性得证. 具体的例子可以参考教材算法导论(Introduction to Algorithms)¹（23章-最小生成树, 16章-贪心算法).

2. 贪心算法适用于哪些优化问题?(返回最优解)

独立集

设$S$是一个有限集, $\mathcal{I}\in 2^S$. $(S,\mathcal{I})$称为一个独立集系统当它满足两个条件: i. 非空性: $\varnothing \in \mathcal{I}$; ii. 继承性: 如果$I\in \mathcal{I}$, $J\subseteq I$, 那么$J\in \mathcal{I}$. 我们把$I\in \mathcal{I}$称为独立集(Independent Set).

独立集上的优化问题

给定权重函数$w:S\to \mathbb{R}$, 我们的目标是找到$I\in \mathcal{I}$使得$I$的总权重$w(I)={\sum }_{x\in I}w(x)$最大.

贪心算法

从$M=\varnothing$开始, 每次从$S$中弹出权重最大的元素$e$, 如果 M ∪ { e } ∈ I M\cup \{e\} \in\mathcal{I} M∪{e}∈I, 则把$e$添加到$M$中, 否则丢弃$e$(直到$S$为空).

结论

考虑独立集上的优化问题. 贪心算法求得最优解当且仅当独立集系统是 拟阵(Matroid)², $(S,\mathcal{I})$满足条件: 如果$I,J\in \mathcal{I},|J|<|I|$, 那么存在$x\in J\backslash I$使得 I ∪ { x } ∈ I I\cup\{x\} \in \mathcal{I} I∪{x}∈I.

参考文献

---

1. T.H. Cormen, C. E. Leiserson, R.L. Rivest and C. Stein. Introduction to Algorithms. Third edition. The MIT Press, 2009. ↩︎ ↩︎

2. https://en.wikipedia.org/wiki/Matroid ↩︎