哪里做百度网站营销软文广告

当前位置： 首页 > news >正文

哪里做百度网站,营销软文广告,网站建设需要考虑因素,wordpress能建商城吗文章目录 [toc]哈夫曼编码不同编码方式对比前缀码构造哈夫曼编码哈夫曼算法的正确性贪心选择性质证明 最优子结构性质证明 总结 Python实现时间复杂性 哈夫曼编码 哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法#xff0c;其压缩率通常为 20 % 20\% 20%到 90 % 90\%… 文章目录 [toc]哈夫曼编码不同编码方式对比前缀码构造哈夫曼编码哈夫曼算法的正确性贪心选择性质证明 最优子结构性质证明 总结 Python实现时间复杂性
哈夫曼编码 哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法其压缩率通常为 20 % 20\% 20%到 90 % 90\% 90%哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用 0 0 0、 1 1 1串表示各字符的最优表示方式 不同编码方式对比 假设有一个数据文件包含 100000 100000 100000个字符要用压缩的方式存储它该文件中共有 6 6 6个不同字符出现各字符出现的频率如下表所示 a a a b b b c c c d d d e e e f f f频率千次 45 45 45 13 13 13 12 12 12 16 16 16 9 9 9 5 5 5 有多种方法表示文件中的信息考察用 0 0 0、 1 1 1码串表示字符的方法即每个字符用唯一的一个 0 0 0、 1 1 1串表示若使用定长码则表示 6 6 6个不同的字符需要 3 3 3位 a 000 a 000 a000 b 001 b 001 b001 ⋯ \cdots ⋯ f 101 f 101 f101用这种方法对整个文件进行编码需要 300000 300000 300000位使用变长码要比使用定长码好得多给出现频率高的字符较短的编码出现频率较低的字符以较长的编码可以大大缩短总码长下表给出了一种变长码编码方案其中 a a a用一位串 0 0 0表示而字符 f f f用 4 4 4位串 1100 1100 1100表示 a a a b b b c c c d d d e e e f f f变长码 0 0 0 101 101 101 100 100 100 111 111 111 1101 1101 1101 1100 1100 1100 用这种编码方案整个文件的总码长为 ( 45 × 1 13 × 3 12 × 3 16 × 3 9 × 4 5 × 4 ) × 1000 224000 (45 \times 1 13 \times 3 12 \times 3 16 \times 3 9 \times 4 5 \times 4) \times 1000 224000 (45×113×312×316×39×45×4)×1000224000位比用定长码方案好总码长减小约 25 % 25\% 25%事实上这是该文件的最优编码方案 前缀码 对每一个字符规定一个 0 0 0、 1 1 1串作为其代码并要求任一字符的代码都不是其他字符代码的前缀这种编码称为前缀码编码的前缀性质可以使译码方法非常简单由于任一字符的代码都不是其他字符代码的前缀从编码文件中不断取出代表某一字符的前缀码转换为原始字符串即可逐个译出文件中的所有字符 例如上表中的变长码就是一种前缀码对于给定的 0 0 0、 1 1 1串 001011101 001011101 001011101可以唯一地分解为 0 0 0、 0 0 0、 101 101 101、 1101 1101 1101因而其译码为 a a b e aabe aabe 译码过程需要方便地取出编码的前缀因此需要表示前缀码的合适的数据结构为此可以用二叉树作为前缀编码的数据结构在表示前缀码的二叉树中树叶代表给定的字符并将每个字符的前缀码看作从树根到代表该字符的树叶的一条路径定长编码的二叉树表示 最优前缀编码的二叉树表示 最优前缀码的二叉树总是一棵完全二叉树即树中任意结点都有 2 2 2个儿子在一般情况下若 C C C是字符集表示其最优前缀码的二叉树中恰有 ∣ C ∣ |C| ∣C∣个叶子每个叶子对应字符集中的一个字符该二叉树恰有 ∣ C ∣ − 1 |C| - 1 ∣C∣−1个内部结点给定编码字符集 C C C及其频率分布 f f f即 C C C中任一字符 c c c以频率 f ( c ) f© f©在数据文件中出现 C C C的一个前缀码编码方案对应一棵二叉树 T T T字符 c c c在树中的深度记为 d T ( c ) d{T}© dT​© d T ( c ) d{T}{©} dT​©也是字符 c c c的前缀码长该编码方案的平均码长定义为 B ( T ) ∑ c ∈ C f ( c ) d T ( c ) B(T) \displaystyle\sum\limits{c \in C}{f© d{T}©} B(T)c∈C∑​f©dT​©使平均码长达到最小的前缀码编码方案称为 C C C的最优前缀码 构造哈夫曼编码 哈夫曼提出了构造最优前缀码的贪心算法由此产生的编码方案称为哈夫曼算法 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T T T 算法以 ∣ C ∣ |C| ∣C∣个叶节点开始执行 ∣ C ∣ − 1 |C| - 1 ∣C∣−1次的“合并”运算后产生最终要求的树 T T T 首先用字符集 C C C中每个字符 c c c的频率 f ( c ) f© f©初始化优先队列 Q Q Q然后不断地从优先队列 Q Q Q中取出具有最小频率的两棵树 x x x和 y y y f ( x ) ≤ f ( y ) f(x) \leq f(y) f(x)≤f(y)将它们合并为一棵新树 z z z z z z的频率是 x x x和 y y y的频率之和新树 z z z以 x x x为其左儿子以 y y y为其右儿子经过 n − 1 n - 1 n−1次的合并后优先队列中只剩下一棵树即所要求的树 T T T 哈夫曼算法的正确性 要证明哈夫曼算法的正确性只要证明最优前缀码问题具有贪心选择性质和最优子结构性质 贪心选择性质 设 C C C是编码字符集 C C C中字符 c c c的频率为 f ( c ) f© f©又设 x x x和 y y y是 C C C中具有最小频率的两个字符则存在 C C C的最优前缀码使 x x x和 y y y具有相同码长且仅最后一位编码不同 证明 设二叉树 T T T表示 C C C的任意一个最优前缀码下面证明可以对 T T T进行适当修改后得到一棵新的二叉树 T ′ ′ T^{} T′′使得在新树中 x x x和 y y y是最深叶子且为兄弟同时新树 T ′ ′ T^{} T′′表示的前缀码也是 C C C的最优前缀码如果能做到则 x x x和 y y y在 T ′ ′ T^{} T′′表示的最优前缀码中就具有相同的码长且仅最后一位编码不同设 b b b和 c c c是二叉树 T T T的最深叶子且为兄弟不失一般性可设 f ( b ) ≤ f ( c ) f(b) \leq f© f(b)≤f© f ( x ) ≤ f ( y ) f(x) \leq f(y) f(x)≤f(y)由于 x x x和 y y y是 C C C中具有最小频率的两个字符故 f ( x ) ≤ f ( b ) f(x) \leq f(b) f(x)≤f(b) f ( y ) ≤ f ( c ) f(y) \leq f© f(y)≤f©首先在树 T T T中交换叶子 b b b和 x x x的位置得到树 T ′ T^{} T′然后在树 T ′ T^{} T′中再交换叶子 c c c和 y y y的位置得到树 T ′ ′ T^{} T′′如下图所示 由此可知树 T T T和 T ′ T^{} T′表示的前缀码的平均码长之差为 B ( T ) − B ( T ′ ) ∑ c ∈ C f ( c ) d T ( c ) − ∑ c ∈ C f ( c ) d T ′ ( c ) f ( x ) d T ( x ) f ( b ) d T ( b ) − f ( x ) d T ′ ( x ) − f ( b ) d T ′ ( b ) f ( x ) d T ( x ) f ( b ) d T ( b ) − f ( x ) d T ( b ) − f ( b ) d T ( x ) ( f ( b ) − f ( x ) ) ( d T ( b ) − d T ( x ) ) ≥ 0 \begin{aligned} B(T) - B(T^{}) \displaystyle\sum\limits{c \in C}{f© d{T}©} - \displaystyle\sum\limits{c \in C}{f© d{T^{}}©} \ f(x) d{T}{(x)} f(b) d{T}{(b)} - f(x) d{T^{}}(x) - f(b) d{T^{}}(b) \ f(x) d{T}{(x)} f(b) d{T}{(b)} - f(x) d{T}(b) - f(b) d{T}(x) \ (f(b) - f(x))(d{T}(b) - d{T}(x)) \geq 0 \end{aligned} B(T)−B(T′)​c∈C∑​f©dT​©−c∈C∑​f©dT′​©f(x)dT​(x)f(b)dT​(b)−f(x)dT′​(x)−f(b)dT′​(b)f(x)dT​(x)f(b)dT​(b)−f(x)dT​(b)−f(b)dT​(x)(f(b)−f(x))(dT​(b)−dT​(x))≥0​ 类似地可以证明在 T ′ T^{} T′中交换 y y y与 c c c的位置也不增加平均码长即 B ( T ′ ) − B ( T ′ ′ ) B(T^{}) - B(T^{}) B(T′)−B(T′′)也是非负的由此可知 B ( T ′ ′ ) ≤ B ( T ′ ) ≤ B ( T ) B(T^{}) \leq B(T^{}) \leq B(T) B(T′′)≤B(T′)≤B(T)另一方面 T T T表示的前缀码是最优的故 B ( T ) ≤ B ( T ′ ′ ) B(T) \leq B(T^{}) B(T)≤B(T′′)因此 B ( T ) B ( T ′ ′ ) B(T) B(T^{}) B(T)B(T′′)即 T ′ ′ T^{} T′′表示的前缀码也是最优前缀码且 x x x和 y y y具有最长的码长同时仅最后一位编码不同 最优子结构性质 设 T T T是表示字符集 C C C的一个最优前缀码的完全二叉树 C C C中字符 c c c的出现频率为 f ( c ) f© f©设 x x x和 y y y是树 T T T中的两个叶子且为兄弟 z z z是它们的父亲若将 z z z看作具有频率 f ( z ) f ( x ) f ( y ) f(z) f(x) f(y) f(z)f(x)f(y)的字符则树 T ′ T − { x , y } T^{} T - \set{x , y} T′T−{x,y}表示字符集 C ′ ( C − { x , y } ) ∪ { z } C^{} (C - \set{x , y}) \cup \set{z} C′(C−{x,y})∪{z}的一个最优前缀码 证明 首先证明 T T T的平均码长 B ( T ) B(T) B(T)可用 T ′ T^{} T′的平均码长 B ( T ′ ) B(T^{}) B(T′)来表示事实上对任意 c ∈ C − { x , y } c \in C - \set{x , y} c∈C−{x,y}有 d T ( c ) d T ′ ( c ) d{T}© d{T^{}}© dT​©dT′​©故 f ( c ) d T ( c ) f ( c ) d T ′ ( c ) f© d{T}© f© d{T^{}}© f©dT​©f©dT′​©另一方面 d T ( x ) d T ( y ) d T ′ ( z ) 1 d{T}(x) d{T}(y) d{T^{}}(z) 1 dT​(x)dT​(y)dT′​(z)1故 f ( x ) d T ( x ) f ( y ) d T ( y ) ( f ( x ) f ( y ) ) ( d T ′ ( z ) 1 ) f ( x ) f ( y ) f ( z ) d T ′ ( z ) \begin{aligned} f(x) d{T}(x) f(y) d{T}(y) (f(x) f(y))(d{T^{}}(z) 1) \ f(x) f(y) f(z) d_{T^{}}(z) \end{aligned} f(x)dT​(x)f(y)dT​(y)​(f(x)f(y))(dT′​(z)1)f(x)f(y)f(z)dT′​(z)​由此可知 B ( T ) B ( T ′ ) f ( x ) f ( y ) B(T) B(T^{}) f(x) f(y) B(T)B(T′)f(x)f(y)若 T ′ T^{} T′表示的字符集 C ′ C^{} C′的前缀码不是最优的则有 T ′ ′ T^{} T′′表示的 C ′ C^{} C′的前缀码使得 B ( T ′ ′ ) B ( T ′ ) B(T^{}) B(T^{}) B(T′′)B(T′)由于 z z z被看作 C ′ C^{} C′中的一个字符故 z z z在 T ′ ′ T^{} T′′中是一树叶若将 x x x和 y y y加入树 T ′ ′ T^{} T′′中作为 z z z的儿子则得到表示字符集 C C C的前缀码的二叉树 T ′ ′ ′ T^{} T′′′且有 B ( T ′ ′ ′ ) B ( T ′ ′ ) f ( x ) f ( y ) B ( T ′ ) f ( x ) f ( y ) B ( T ) B(T^{}) B(T^{}) f(x) f(y) B({T^{}}) f(x) f(y) B(T) B(T′′′)B(T′′)f(x)f(y)B(T′)f(x)f(y)B(T)这与 T T T的最优性矛盾故 T ′ T^{} T′表示的 C ′ C^{} C′的前缀码是最优的 总结 由贪心选择性质和最优子结构性质立即推出哈夫曼算法是正确的即哈夫曼算法产生 C C C的一棵最优前缀编码树 Python实现 from heapq import heappop, heappush from collections import defaultdictclass HuffmanNode:def init(self, char, freq, leftNone, rightNone):self.char char # 节点代表的字符self.freq freq # 节点对应字符的频率self.left left # 左子节点self.right right # 右子节点def lt(self, other):return self.freq other.freqdef build_frequency_table(text):frequency_table defaultdict(int) # 存储字符频率的字典, 默认值为 0for char in text:frequency_table[char] 1 # 统计字符频率return frequency_tabledef build_huffman_tree(frequency_table):priority_queue [] # 存储 Huffman 节点的优先队列(最小堆)for char, freq in frequency_table.items():node HuffmanNode(char, freq)heappush(priority_queue, node) # 将每个字符的频率作为优先级, 构建最小堆while len(priority_queue) 1:left_node heappop(priority_queue) # 弹出频率最小的节点作为左子节点right_node heappop(priority_queue) # 弹出频率次小的节点作为右子节点parent_freq left_node.freq right_node.freq # 父节点的频率是左右子节点频率之和parent_node HuffmanNode(None, parent_freq, left_node, right_node)heappush(priority_queue, parent_node) # 将父节点插入优先队列return heappop(priority_queue) # 返回最后剩余的根节点def generate_codes(node, current_code, codes):if node.char:codes[node.char] current_code # 如果节点代表一个字符, 将字符和对应的编码存入字典else:generate_codes(node.left, current_code 0, codes) # 递归生成左子树编码, 将当前编码加上 0generate_codes(node.right, current_code 1, codes) # 递归生成右子树编码, 将当前编码加上 1def huffman_encoding(text):frequency_table build_frequency_table(text) # 构建字符频率表huffman_tree build_huffman_tree(frequency_table) # 构建 Huffman 树codes {} # 存储字符和对应的 Huffman 编码的字典generate_codes(huffman_tree, , codes) # 生成 Huffman 编码encoded_text .join(codes[char] for char in text) # 将文本编码为 Huffman 编码return encoded_text, huffman_treedef huffman_decoding(encoded_text, huffman_tree):decoded_text current_node huffman_treefor bit in encoded_text:if bit 0:current_node current_node.left # 如果是 0, 移动到左子节点else:current_node current_node.right # 如果是 1, 移动到右子节点if current_node.char: # 如果当前节点代表一个字符decoded_text current_node.char # 将字符添加到解码文本中current_node huffman_tree # 重置当前节点为根节点return decoded_texttext Hello, Huffman! print(f原始文本: {text})encoded_text, huffman_tree huffman_encoding(text) print(f编码后的文本: {encoded_text})decoded_text huffman_decoding(encoded_text, huffman_tree) print(f解码后的文本: {decoded_text})原始文本: Hello, Huffman! 编码后的文本: 01110100010010100010110110111000111111000110111001001 解码后的文本: Hello, Huffman!时间复杂性 算法用最小堆实现优先队列 Q Q Q初始化优先队列需要 O ( n ) O(n) O(n)计算时间由于最小堆的删除结点和插入结点运算均需 O ( log ⁡ n ) O(\log{n}) O(logn)时间 n − 1 n - 1 n−1次的合并共需要 O ( n log ⁡ n ) O(n \log{n}) O(nlogn)计算时间因此关于 n n n个字符的哈夫曼算法的计算时间为 O ( n log ⁡ n ) O(n \log{n}) O(nlogn)