0023算法笔记——【贪心算法】哈夫曼编码问题

0023 算法笔记 贪心算法 哈夫曼编码问题 1 问题描述 问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法 其 压缩率通常在 20 90 之间 哈夫曼编码算法算法用字符在文件中出现 的频率表来建立一个用 0 1 串表示各字符的最优表示方式 一个包含 100 000 个字符的文件 各字符出现频率不同 如下表所示 有多种方式表示文件中的信息 若用 0 1 码表示字符的方法 即每 个字符用唯一的一个 0 1 串表示 若采用定长编码定长编码表示 则需要 3 位表 示一个字符 整个文件编码需要 300 000 位 若采用变长编码变长编码表示 给给 频率高的字符较短的编码 频率低的字符较长的编码 达到整体编码减少的目的频率高的字符较短的编码 频率低的字符较长的编码 达到整体编码减少的目的 则整 个文件编码需要 45 1 13 3 12 3 16 3 9 4 5 4 1000 224 000 位 由此可见 变长码比定长码方案好 总码长减小 约 25 前缀码前缀码 对每一个字符规定一个 0 1 串作为其代码 并要求任一字符 的代码都不是其他字符代码的前缀 这种编码称为前缀码 编码的前 缀性质可以使译码方法非常简单 例如 001011101 可以唯一的分解为 0 0 101 1101 因而其译码为 aabe 译码过程需要方便的取出编码的前缀 因此需要表示前缀码的合适 的数据结构数据结构 为此 可以用二叉树作为前缀码的数据结构 树叶表示 给定字符 从树根到树叶的路径当作该字符的前缀码 代码中每一位 的 0 或 1 分别作为指示某节点到左儿子或右儿子的 路标 从上图可以看出 表示最优前缀码的二叉树总是一棵完全二叉树 即树中任意节点都有 2 个儿子 图 a 表示定长编码方案不是最优的 其编码的二叉树不是一棵完全二叉树 在一般情况下 若 C 是编码字 符集 表示其最优前缀码的二叉树中恰有 C 个叶子 每个叶子对应于 字符集中的一个字符 该二叉树有 C 1 个内部节点 给定编码字符集 C 及频率分布 f 即 C 中任一字符 c 以频率 f c 在数 据文件中出现 C 的一个前缀码编码方案对应于一棵二叉树 T 字符 c 在树 T 中的深度记为 dT c dT c 也是字符 c 的前缀码长 则平均码长平均码长 定义为 使平均码长达到最小的前缀码编码方案称使平均码长达到最小的前缀码编码方案称 为为C的最优前缀码的最优前缀码 2 构造哈弗曼编码 构造哈弗曼编码 哈夫曼提出构造最优前缀码的贪心算法 由此产生的编码方案称为 哈夫曼编码 其构造步骤如下 1 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T 2 算法以 C 个叶结点开始 执行 C 1 次的 合并 运算后产生最终 所要求的树 T 3 假设编码字符集中每一字符 c 的频率是 f c 以 f 为键值的优先 队列 Q 用在贪心选择时有效地确定算法当前要合并的 2 棵具有最小频 率的树 一旦 2 棵具有最小频率的树合并后 产生一棵新的树 其频 率为合并的 2 棵树的频率之和 并将新树插入优先队列 Q 经过 n 1 次的合并后 优先队列中只剩下一棵树 即所要求的树 T 构造过程如图所示 具体代码实现如下 1 4d4 cpp 程序主文件 cpp view plain copy 1 4d4 贪心算法 哈夫曼算法 2 include stdafx h 3 include BinaryTree h 4 include MinHeap h 5 include 6 using namespace std 7 8 const int N 6 9 10 template class Huffman 11 12 template 13 BinaryTree HuffmanTree Type f int n 14 15 template 16 class Huffman 17 18 friend BinaryTree HuffmanTree Type int 19 public 20 operator Type const 21 22 return weight 23 24 private 25 BinaryTree tree 26 Type weight 27 28 29 int main 30 31 char c 0 a b c d e f 32 int f 0 45 13 12 16 9 5 下标从 1 开始 33 BinaryTree t HuffmanTree f N 34 35 cout 各字符出现的对应频率分别为 endl 36 for int i 1 i N i 37 38 cout c i f i 39 40 cout endl 41 42 cout 生成二叉树的前序遍历结果为 endl 43 t Pre Order 44 cout endl 45 46 cout 生成二叉树的中序遍历结果为 endl 47 t In Order 48 cout endl 49 50 t DestroyTree 51 return 0 52 53 54 template 55 BinaryTree HuffmanTree Type f int n 56 57 生成单节点树 58 Huffman w new Huffman n 1 59 BinaryTree z zero 60 61 for int i 1 i n i 62 63 z MakeTree i zero zero 64 w i weight f i 65 w i tree z 66 67 68 建优先队列 69 MinHeap Huffman Q n 70 for int i 1 i n i Q Insert w i 71 72 反复合并最小频率树 73 Huffman x y 74 for int i 1 i n i 75 76 x Q RemoveMin 77 y Q RemoveMin 78 z MakeTree 0 x tree y tree 79 x weight y weight 80 x tree z 81 Q Insert x 82 83 84 x Q RemoveMin 85 86 delete w 87 88 return x tree 89 2 BinaryTree h 二叉树实现 cpp view plain copy 1 include 2 using namespace std 3 4 template 5 struct BTNode 6 7 T data 8 BTNode lChild rChild 9 10 BTNode 11 12 lChild rChild NULL 13 14 15 BTNode const T 18 lChild Childl 19 rChild Childr 20 21 22 BTNode CopyTree 23 24 BTNode nl nr nn 25 26 if 28 29 nl lChild CopyTree 30 nr rChild CopyTree 31 32 nn new BTNode data nl nr 33 return nn 34 35 36 37 38 template 39 class BinaryTree 40 41 public 42 BTNode root 43 BinaryTree 44 BinaryTree 45 46 void Pre Order 47 void In Order 48 void Post Order 49 50 int TreeHeight const 51 int TreeNodeCount const 52 53 void DestroyTree 54 void MakeTree T pData BinaryTree leftTree BinaryTree rightTree 55 void Change BTNode r 56 57 private 58 void Destroy BTNode 59 void PreOrder BTNode r 60 void InOrder BTNode r 61 void PostOrder BTNode r 62 63 int Height const BTNode r const 64 int NodeCount const BTNode r const 65 66 67 template 68 BinaryTree BinaryTree 69 70 root NULL 71 72 73 template 74 BinaryTree BinaryTree 75 76 77 78 79 template 80 void BinaryTree Pre Order 81 82 PreOrder root 83 84 85 template 86 void BinaryTree In Order 87 88 InOrder root 89 90 91 template 92 void BinaryTree Post Order 93 94 PostOrder root 95 96 97 template 98 int BinaryTree TreeHeight const 99 100 return Height root 101 102 103 template 104 int BinaryTree TreeNodeCount const 105 106 return NodeCount root 107 108 109 template 110 void BinaryTree DestroyTree 111 112 Destroy root 113 114 115 template 116 void BinaryTree PreOrder BTNode r 117 118 if r NULL 119 120 cout data lChild 122 PreOrder r rChild 123 124 125 126 template 127 void BinaryTree InOrder BTNode r 128 129 if r NULL 130 131 InOrder r lChild 132 cout data rChild 134 135 136 137 template 138 void BinaryTree PostOrder BTNode r 139 140 if r NULL 141 142 PostOrder r lChild 143 PostOrder r rChild 144 cout data 145 146 147 148 template 149 int BinaryTree NodeCount const BTNode r const 150 151 if r NULL 152 return 0 153 else 154 return 1 NodeCount r lChild NodeCount r rChild 155 156 157 template 158 int BinaryTree Height const BTNode r const 159 160 if r NULL 161 return 0 162 else 163 164 int lh rh 165 lh Height r lChild 166 rh Height r rChild 167 return 1 lh rh lh rh 168 169 170 171 template 172 void BinaryTree Destroy BTNode 177 Destroy r rChild 178 delete r 179 r NULL 180 181 182 183 template 184 void BinaryTree Change BTNode r 将二叉树 bt 所有结点的左右子树交换 185 186 BTNode p 187 if r 188 p r lChild 189 r lChild r rChild 190 r rChild p 左右子女交换 191 Change r lChild 交换左子树上所有结点的左右子树 192 Change r rChild 交换右子树上所有结点的左右子树 193 194 195 196 template 197 void BinaryTree MakeTree T pData BinaryTree leftTree BinaryTree r ightTree 198 199 root new BTNode 200 root data pData 201 root lChild leftTree root 202 root rChild rightTree root 203 3 MinHeap h 最小堆实现 cpp view plain copy 1 include 2 using namespace std 3 template 4 class MinHeap 5 6 private 7 T heap 元素数组 0 号位置也储存元素 8 int CurrentSize 目前元素个数 9 int MaxSize 可容纳的最多元素个数 10 11 void FilterDown const int start const int end 自上往下调整 使关键 字小的节点在上 12 void FilterUp int start 自下往上调整 13 14 public 15 MinHeap int n 1000 16 MinHeap 17 bool Insert const T 插入元素 18 19 T RemoveMin 删除最小元素 20 T GetMin 取最小元素 21 22 bool IsEmpty const 23 bool IsFull const 24 void Clear 25 26 27 template 28 MinHeap MinHeap int n 29 30 MaxSize n 31 heap new T MaxSize 32 CurrentSize 0 33 34 35 template 36 MinHeap MinHeap 37 38 delete heap 39 40 41 template 42 void MinHeap FilterUp int start 自下往上调整 43 44 int j start i j 1 2 i 指向 j 的双亲节点 45 T temp heap j 46 47 while j 0 48 49 if heap i temp 50 break 51 else 52 53 heap j heap i 54 j i 55 i i 1 2 56 57 58 heap j temp 59 60 61 template 62 void MinHeap FilterDown const int start const int end 自上往下调整 使 关键字小的节点在上 63 64 int i start j 2 i 1 65 T temp heap i 66 while j end 67 68 if jheap j 1 69 j 70 if temp heap j 71 break 72 else 73 74 heap i heap j 75 i j 76 j 2 j 1 77 78 79 heap i temp 80 81 82 template 83 bool MinHeap Insert const T 87 88 heap CurrentSize x 89 FilterUp CurrentSize 90 91 CurrentSize 92 return true 93 94 95 template 96 T MinHeap RemoveMin 97 98 T x heap 0 99 heap 0 heap CurrentSize 1 100 101 CurrentSize 102 FilterDown 0 CurrentSize 1 调整新的根节点 103 104 return x 105 106 107 template 108 T MinHeap GetMin 109 110 return heap 0 111 112 113 template 114 bool MinHeap IsEmpty const 115 116 return CurrentSize 0 117 118 119