对一个给定的文本文件,对其进行哈夫曼编码,并计算压缩率。

时间: 2024-05-16 17:15:04 浏览: 39
哈夫曼编码是一种无损数据压缩算法,它根据不同字符出现的频率,分配不同长度的编码来压缩数据。压缩率取决于文本中不同字符出现的频率。如果文本中存在大量重复的字符,则压缩率会更高。 下面是对文本文件进行哈夫曼编码的步骤: 1. 统计文本中不同字符出现的频率,并按照频率从小到大排序。 2. 构建哈夫曼树。将频率最小的两个字符合并成一个节点,其权重为它们的频率之和。重复此过程,直到所有节点合并为一棵树。 3. 给哈夫曼树的左分支编码为0,右分支编码为1。从根节点开始,沿着树走到每个叶子节点,记录下路径上的编码,即为该字符的哈夫曼编码。 4. 将文本中每个字符替换为它的哈夫曼编码,并将多个编码拼接成一个二进制字符串。 5. 将二进制字符串转换为字节数组,并将其写入到输出文件中。 6. 计算压缩率。压缩率 = 原始文件大小 / 压缩后文件大小。 下面是 Python 实现: ```python import heapq, os class HuffmanCoding: def __init__(self, file_path): self.file_path = file_path self.heap = [] self.codes = {} self.reverse_mapping = {} class HeapNode: def __init__(self, char, freq): self.char = char self.freq = freq self.left = None self.right = None def __lt__(self, other): return self.freq < other.freq def __eq__(self, other): if(other == None): return False if(not isinstance(other, HeapNode)): return False return self.freq == other.freq def make_frequency_dict(self, text): frequency = {} for char in text: if char not in frequency: frequency[char] = 0 frequency[char] += 1 return frequency def make_heap(self, frequency): for key in frequency: node = self.HeapNode(key, frequency[key]) heapq.heappush(self.heap, node) def merge_nodes(self): while(len(self.heap)>1): node1 = heapq.heappop(self.heap) node2 = heapq.heappop(self.heap) merged = self.HeapNode(None, node1.freq + node2.freq) merged.left = node1 merged.right = node2 heapq.heappush(self.heap, merged) def make_codes_helper(self, root, current_code): if(root == None): return if(root.char != None): self.codes[root.char] = current_code self.reverse_mapping[current_code] = root.char return self.make_codes_helper(root.left, current_code + "0") self.make_codes_helper(root.right, current_code + "1") def make_codes(self): root = heapq.heappop(self.heap) current_code = "" self.make_codes_helper(root, current_code) def get_encoded_text(self, text): encoded_text = "" for char in text: encoded_text += self.codes[char] return encoded_text def pad_encoded_text(self, encoded_text): extra_padding = 8 - len(encoded_text) % 8 for i in range(extra_padding): encoded_text += "0" padded_info = "{0:08b}".format(extra_padding) encoded_text = padded_info + encoded_text return encoded_text def get_byte_array(self, padded_encoded_text): if(len(padded_encoded_text) % 8 != 0): print("Encoded text not padded properly") exit(0) b = bytearray() for i in range(0, len(padded_encoded_text), 8): byte = padded_encoded_text[i:i+8] b.append(int(byte, 2)) return b def compress(self): file_name, file_extension = os.path.splitext(self.file_path) output_path = file_name + ".bin" with open(self.file_path, 'r+') as file, open(output_path, 'wb') as output: text = file.read() text = text.rstrip() frequency = self.make_frequency_dict(text) self.make_heap(frequency) self.merge_nodes() self.make_codes() encoded_text = self.get_encoded_text(text) padded_encoded_text = self.pad_encoded_text(encoded_text) b = self.get_byte_array(padded_encoded_text) output.write(bytes(b)) print("Compressed file path: " + output_path) return output_path """ functions for decompression """ def remove_padding(self, padded_encoded_text): padded_info = padded_encoded_text[:8] extra_padding = int(padded_info, 2) padded_encoded_text = padded_encoded_text[8:] encoded_text = padded_encoded_text[:-1*extra_padding] return encoded_text def decode_text(self, encoded_text): current_code = "" decoded_text = "" for bit in encoded_text: current_code += bit if(current_code in self.reverse_mapping): character = self.reverse_mapping[current_code] decoded_text += character current_code = "" return decoded_text def decompress(self, input_path): file_name, file_extension = os.path.splitext(self.file_path) output_path = file_name + "_decompressed" + ".txt" with open(input_path, 'rb') as file, open(output_path, 'w') as output: bit_string = "" byte = file.read(1) while(byte != b""): byte = ord(byte) bits = bin(byte)[2:].rjust(8, '0') bit_string += bits byte = file.read(1) encoded_text = self.remove_padding(bit_string) decoded_text = self.decode_text(encoded_text) output.write(decoded_text) print("Decompressed file path: " + output_path) return output_path ``` 使用示例: ```python h = HuffmanCoding("example.txt") output_path = h.compress() h.decompress(output_path) ``` 其中 `example.txt` 是需要压缩的文本文件。该程序会在同一目录下生成一个名为 `example.bin` 的压缩文件,以及一个名为 `example_decompressed.txt` 的解压缩文件。压缩率可以通过比较原始文件大小和压缩文件大小来计算。

相关推荐

最新推荐

recommend-type

哈夫曼编码-译码器课程设计报告.docx

设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。 基本要求: (1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中) (2)分别采用动态和静态存储...
recommend-type

运用哈夫曼编码压缩解压文件源代码

运用哈夫曼编码压缩解压文件源代码,代码有详细的注释,很好的压缩解压的源代码
recommend-type

aiohttp-3.9.2-cp310-cp310-musllinux_1_1_aarch64.whl

Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。
recommend-type

pyzmq-25.1.2-cp37-cp37m-macosx_10_9_x86_64.whl

Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。
recommend-type

CIC Compiler v4.0 LogiCORE IP Product Guide

CIC Compiler v4.0 LogiCORE IP Product Guide是Xilinx Vivado Design Suite的一部分,专注于Vivado工具中的CIC(Cascaded Integrator-Comb滤波器)逻辑内核的设计、实现和调试。这份指南涵盖了从设计流程概述、产品规格、核心设计指导到实际设计步骤的详细内容。 1. **产品概述**: - CIC Compiler v4.0是一款针对FPGA设计的专业IP核,用于实现连续积分-组合(CIC)滤波器,常用于信号处理应用中的滤波、下采样和频率变换等任务。 - Navigating Content by Design Process部分引导用户按照设计流程的顺序来理解和操作IP核。 2. **产品规格**: - 该指南提供了Port Descriptions章节,详述了IP核与外设之间的接口,包括输入输出数据流以及可能的控制信号,这对于接口配置至关重要。 3. **设计流程**: - General Design Guidelines强调了在使用CIC Compiler时的基本原则,如选择合适的滤波器阶数、确定时钟配置和复位策略。 - Clocking和Resets章节讨论了时钟管理以及确保系统稳定性的关键性复位机制。 - Protocol Description部分介绍了IP核与其他模块如何通过协议进行通信,以确保正确的数据传输。 4. **设计流程步骤**: - Customizing and Generating the Core讲述了如何定制CIC Compiler的参数,以及如何将其集成到Vivado Design Suite的设计流程中。 - Constraining the Core部分涉及如何在设计约束文件中正确设置IP核的行为,以满足具体的应用需求。 - Simulation、Synthesis and Implementation章节详细介绍了使用Vivado工具进行功能仿真、逻辑综合和实施的过程。 5. **测试与升级**: - Test Bench部分提供了一个演示性的测试平台,帮助用户验证IP核的功能。 - Migrating to the Vivado Design Suite和Upgrading in the Vivado Design Suite指导用户如何在新版本的Vivado工具中更新和迁移CIC Compiler IP。 6. **支持与资源**: - Documentation Navigator and Design Hubs链接了更多Xilinx官方文档和社区资源,便于用户查找更多信息和解决问题。 - Revision History记录了IP核的版本变化和更新历史,确保用户了解最新的改进和兼容性信息。 7. **法律责任**: - 重要Legal Notices部分包含了版权声明、许可条款和其他法律注意事项,确保用户在使用过程中遵循相关规定。 CIC Compiler v4.0 LogiCORE IP Product Guide是FPGA开发人员在使用Vivado工具设计CIC滤波器时的重要参考资料,提供了完整的IP核设计流程、功能细节及技术支持路径。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB矩阵奇异值分解(SVD)应用指南:从降维到图像处理,5个实用案例

![MATLAB矩阵奇异值分解(SVD)应用指南:从降维到图像处理,5个实用案例](https://img-blog.csdnimg.cn/20200302213423127.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDEzMjAzNQ==,size_16,color_FFFFFF,t_70) # 1. 矩阵奇异值分解(SVD)简介** 矩阵奇异值分解(SVD)是一种强大的线性代数技术,用于将矩阵分解为三个
recommend-type

HAL_GPIO_TogglePin(GPIOC, GPIO_PIN_0); HAL_Delay(200);是什么意思

这段代码是针对STM32F4xx系列的GPIO库函数,用于控制GPIOC的0号引脚的电平状态。具体来说,HAL_GPIO_TogglePin函数用于翻转GPIO引脚的电平状态,即如果该引脚原来是高电平,则变为低电平,反之亦然。而HAL_Delay函数则是用于延时200毫秒。因此,这段代码的作用是每200毫秒翻转一次GPIOC的0号引脚的电平状态。
recommend-type

G989.pdf

"这篇文档是关于ITU-T G.989.3标准,详细规定了40千兆位无源光网络(NG-PON2)的传输汇聚层规范,适用于住宅、商业、移动回程等多种应用场景的光接入网络。NG-PON2系统采用多波长技术,具有高度的容量扩展性,可适应未来100Gbit/s或更高的带宽需求。" 本文档主要涵盖了以下几个关键知识点: 1. **无源光网络(PON)技术**:无源光网络是一种光纤接入技术,其中光分配网络不包含任何需要电源的有源电子设备,从而降低了维护成本和能耗。40G NG-PON2是PON技术的一个重要发展,显著提升了带宽能力。 2. **40千兆位能力**:G.989.3标准定义的40G NG-PON2系统提供了40Gbps的传输速率,为用户提供超高速的数据传输服务,满足高带宽需求的应用,如高清视频流、云服务和大规模企业网络。 3. **多波长信道**:NG-PON2支持多个独立的波长信道,每个信道可以承载不同的服务,提高了频谱效率和网络利用率。这种多波长技术允许在同一个光纤上同时传输多个数据流,显著增加了系统的总容量。 4. **时分和波分复用(TWDM)**:TWDM允许在不同时间间隔内分配不同波长,为每个用户分配专用的时隙,从而实现多个用户共享同一光纤资源的同时传输。 5. **点对点波分复用(WDMPtP)**:与TWDM相比,WDMPtP提供了一种更直接的波长分配方式,每个波长直接连接到特定的用户或设备,减少了信道之间的干扰,增强了网络性能和稳定性。 6. **容量扩展性**:NG-PON2设计时考虑了未来的容量需求,系统能够灵活地增加波长数量或提高每个波长的速率,以适应不断增长的带宽需求,例如提升至100Gbit/s或更高。 7. **应用场景**:40G NG-PON2不仅用于住宅宽带服务,还广泛应用于商业环境中的数据中心互联、企业网络以及移动通信基站的回传,为各种业务提供了高性能的接入解决方案。 8. **ITU-T标准**:作为国际电信联盟电信标准化部门(ITU-T)的一部分,G.989.3建议书为全球的电信运营商和设备制造商提供了一套统一的技术规范,确保不同厂商的产品和服务之间的兼容性和互操作性。 9. **光接入网络**:G.989.3标准是接入网络技术的一个重要组成部分,它与光纤到户(FTTH)、光纤到楼(FTTB)等光接入方案相结合,构建了高效、可靠的宽带接入基础设施。 ITU-T G.989.3标准详细规定了40G NG-PON2系统的传输汇聚层,为现代高速网络接入提供了强大的技术支持,推动了光通信技术的持续进步。
recommend-type

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依