【信息技术】 霍夫曼编码实现方法的研究 张成林 （重庆三峡学院计算机科学与工程学院，重庆４００４００） 摘要：在信息爆炸的今天，数据压缩的重要性不言而喻，基本过程有三步：建模表达、二次量化和熵编码。其中熵编 码又称为冗余度压缩。而统计编码又是熵编码的重要内容，其主要包括霍夫曼（Ｈｕｆｆｍａｎ）编码、游程编码、二进制信源编 码、算术编码、Ｌｚｗ编码等。本文以Ｈｕ伍ｎａｎ编码作为熵编码的一种代表，介绍关于ＨｕｆｆｍａｎＮ码的具体实现方法。 关键词：Ｈｕｆｆｍａｎ编码；二叉树；权值 中图分类号：Ｇ６４２．０ 一文献标志码：Ａ 文章编号：１６７４—９３２４（２０１３）２６—０２４８—０２ 、引言 １．数值传输系统模型如图１所示。 短的异字头码字，属于无损压缩编码。Ｈｕｆｆｍａｎ编码的码长 是变化的，对于出现概率高的信息，编码的长度较短；而对 于出现概率低的信息，编码长度较长。这样，处理全部信息 的总码长一定小于实际信息的符号长度闭。方法、步骤：（１） 将信号源的符号出现的概率（在此称为权值）ｗ．，Ｗ …．， ｗｎ｝构造成１１棵二叉树集合Ｆ＝ｆＴ ，Ｔ …．，ＴＩ１１，其中每棵二叉 树Ｔｉ中只有一个带权为ｗｉ的根结点，其左右子树均为空。 （２）在Ｆ中选取两棵根结点的权值最小的树作为左右子树 构造一棵新的二叉树，且置新的二叉树的根结点的权值为 图１数字传输系统模型 其左、右子树上根结点的权值之和。（３）在Ｆ中删除这两棵 树，同时将新得到的二叉树加入Ｆ中。（４）重复（２）和（３），直 到Ｆ只含一棵树为止。这棵树便是霍夫曼（Ｈｕｆｆｍａｎ）树。（５） 在合并中约定权值小的根结点在左子树上，权值大的在右 子树上。然后在每个左分支上标记为…０’，右分支上标记为 …１’。最后记录从霍夫曼（Ｈｕｆｆｍａｎ）树的根结点到每个叶子 结点所经过的分支上的“０”或“１”的序列，从而得到每个符 号的Ｈｕｆｆｍａｎ编码。［３１ ２．信源编码：主要是解决有效性的问题。通过对信源 的压缩、扰乱、加密等一系列处理，力求用最少的数码传递 最大的信息量，使信号更适宜传输。 ３．数据压缩：就是以最少的数码表示信源所发的信 号，减少容纳给定消息集合或数据采样集合的信号空间。 二、统计编码 对于各种信源都通用的可逆压缩（无失真编码）方法， 因为大多数计算机文件都不允许在压缩过程中丢失信息。 这类方法主要利用信息或信息序列出现的概率的分布特 性，注重寻找概率与码字长度问题的最优匹配，这叫做统 计编码或概率匹配编码。而霍夫曼（Ｈｕｆｆｍａｎ）编码就是其 中具有代表性的一种编码方案Ｉｌ＿。 三、霍夫曼（Ｈｕ什ｍａｎ）编码原理 Ｈｕｆｆｍａｎ编码是１９５２年为文本文件而建立的，是一种 统计编码。它完全依据字符出现的概率来构造平均长度最 图２ Ｈｕｆｆｍａｎ编码过程实例 流，利用网络交流的非面对面性，倾听学生心底的真实声 音，帮助学生解决学习生活中的实际问题。 ３．海纳百川，有容乃大——建设以新媒体技术为媒介 的教学资源共享平台。从建设一个以新媒体技术为媒介的 教学资源共享平台人手，能全面带动学风、教风建设。高校 可以整合全校教学资源，建立“媒体资源库”，提供教学理 念、教学技巧、学习评量等教学咨询及服务，并充实网络教 材资源。在协助教师即时掌握新媒体使用的同时推广网络 辅助教学，运用网络教学平台进行同步、非同步课程。这个 “媒体资源库”中期开始可以稳步持续力推网络精品特色 示范课程，通过新媒体平台广泛传播的精品特色课程能有 效牵引和带动学校的综合办学实力、人才培养质量及全面 提升学校的社会知名度与美誉度，形成能引起关注的“眼 球热力”。在高校教学活动中，教师应与时俱进，改变传统 的灌输式教学方法，巧妙地把新媒体技术运用到自己的课 一堂上，并且不局限于Ｐ 板书式的照本宣科，应用现代化 的教学工具，全方位引入多种教学手段，最大限度地刺激 学生的视觉、听觉等感官，从而调动学生上课的积极性和 参与性，让学生跟随自己的兴趣，在实际的摸索中学习知 识、掌握技巧，最终引起学生感情上的共鸣，给学生带来心 智上的启迪。 参考文献： 、 【１】许鹏．论新媒体艺术研究的特殊内容与方＇ａ－Ｕ］．中国人民大学 学报，２００７，（１）． 【２】张伟佳．新媒体时代高校校园文化建设研究Ｕ１．现代企业教 育，２００９，（２２）． 【３】颜秉忠，王晓玲，葛春颖．论新媒体对校园文化的构建卟传媒 观察，２０１２，（９）． 『４１康志 贤．新媒体视域下高校校园文化建设面临的挑战及对策 【Ｉ１＿大观周刊，２０１２，（４１）． ２４８— 【信息技术】 如何在信息技术教学中培养创新型人才 ——信息技术教学过程中培养学生研究、实践、创新能力浅析 张庆 （贵州省安顺市实验学校，贵州安顺５６１０００） 摘要：２１世纪一个国家的科技水平高低取决于创新型人才的培养，而培养创新型人才即是培养学生的信息素养。当 前如何在信息技术教学中培养人才的信息素养呢？首先正确认识信息技术课程的特征，树立信息技术教学的培养目标； 其次从我国目前信息技术教学的现状着手，分析出信息技术教学应从培养学生的“使用能力”转变为培养学生的“应用 能力”，即培养学生自主探究学习的能力，培养学生对信息的敏锐感悟力和正误判断力，以及学生对信息技术的实践使 用能力；最后总结信息技术教学过程中应采用的一些具体方法以培养上述三种能力。 关键词：创新人才；信息素养；信息技术教学；信息技术；使用；应用 中图分类号：Ｇ６３３．６７ 文献标志码：Ａ 文章编号：１６７４—９３２４（２０１３）２６—０２４９—０２ 人类在迈入２１世纪的同时，也步人了信息技术飞速发 二、正确理解信息技术教育培养目标 展的知识经济时代，在这个时代，科技知识将是一个国家 随着新课程改革在中小学全面实施，而新课程又十分 的经济发展和社会进步的决定因素，是国际竞争的重点， 重视中小学生信息素养的培养。信息素养已经成为继读、 而一个国家的科技水平和科技能力高低关键在人才，我 写、算之后的第四种基本能力。只有负责任地使用信息技 们的社会需要德、智、体全面发展的人才，这里的“智”不能 术，把信息技术作为支持终身学习和合作学习的手段，形 单纯地理解为科学文化水平，而重要的因素应该是他们 成良好的信息素养，才能为适应信息社会的学习、工作和 的学习和研究的能力、观察和发现问题的能力、解决问题 生活打下必要的基础。１９９８年美国图书馆协会和美国教育 和实践的能力、创新精神和创新能力。信息技术作为一门 传播与技术协会（ＡＬＡ＆ＡＥＣＴ）在其出版的《信息能力：创 专门以计算机为主导的知识性与技能性相结合的基础工 建学习的伙伴》一书中制定了学生学习的九大信息素养标 具课程，必将对未来社会人才的培养产生了深远影响。 准。这一标准从信息素养、学习和社会责任三个方面 一、正确认识信息技术课程的特征 进行了表述，进一步明确和丰富了信息素养在技能、态度、 １．中小学信息技术课程具有学科性，在中小学开设信 品德等方面的要求。①信息素养：能够有效地、高效地获取 息技术课程是时代发展的需要，它的任务是提高学生的 信息；能够熟练地、批判性地评价信息；能够精确地、创造 科学文化素质，普及以计算机技术、微电子技术和现代通 性地使用信息；②学习：能探求与个人兴趣有关的信 信技术为特征的信息技术知识，使学生掌握计算机的基 息；能欣赏作品和其他对信息进行创造性表达的内容；③ 础知识和基本操作技能。作为与语文、数学、英语课同等 社会责任：能认识信息对民主化社会的重要性；能履行与 重要的一门课程，信息技术课有其特定的教学目标、教学 信息和信息技术相关的符合伦理道德的行为规范。 内容、教学方法和考试、考核办法。因此，应当重视其学科 三、如何在信息技术教学中培养创新人才 性特点。 虽然信息技术学科是培养学生信息素养的主要基础 ２．中小学信息由于多媒体辅助教学、计算机网络的广 学科，而目前我国在信息技术教学中的现状是：信息技术 泛应用，为实施素质教育，大面积提高教学质量提供了技 课时少，学习时间短，很多老师只看到了信息技术课的工 术支持和物质保障，因此学生可以利用计算机在互联网 具性，认为只要按照书本的知识点教学，让学生在学习过 上获取所需的信息资料，打破时空，与专家、朋友交 程中掌握某种软件的使用即可，即对信息技术的“使用”能 流，从而得到提高。这便体现了信息技术学科的工具性。 力培养，这样的教学即使让大部分学生掌握了信息技术的 上述编码的平均码字长度Ｒ：（２＋２＋２＋３＋３）／５＝２．４。说 ｝ｆｒｅｅ（ｃｄ）； 明：由于“１”和…０’的指定是任意的，故由上述过程编出的 ｝／／ＨｕｆｆｍａｎＣｏｄｉｎｇ 最佳码不是唯一的，但其平均码长是一样的，故不影响编 五、结论 码效率与数据压缩性能。 Ｈｕｆｆａｍｎ编码的实现方法有很多种，本文只是概述了 四、Ｈｕ仟ｍａｎ编码的具体实现 基于数据结构的Ｈｕｆｆｍａｎ编码的算法思想。 ， ／，一一以下部分代码是在Ｈｕｆｆｍａｎ树上从根逆向求每 虽然Ｈｕｆｆｍａｎ编码优点非常突出，但通过作者的研究 个字符的Ｈｕｆｆｍａｎ编码——一ＨＣ＝（ＨｕｆｆｍａｎＣｏｄｅ ｍａ１１ｏｃ 发现，在具体的实现过程中，其局限性也不容忽视。因此， （（ｎ＋１）＊ｓｉｚｅｏｆ（ｃｈａｒ＊））； 在今后对Ｈｕｆｆｍａｎ编码的研究与应用中，应该扬长避短，更 ｃｄ＝（ｃｈａｒ＊）ｍａｌｌｏｃ（ｎ＊ｓｉｚｅｏｆ（ｃｈａｒ））；ｃｄｎ—１］＝“．ｐａｒｅｎｔ；ｆ！ 好发挥此编码的自身优势。 ：０；ｃ＝ｆ，ｆ＝ＨＴｆ］．ｐａｒｅｎｔ） 参考文献： ｉｆ（ＨＴＯ．１ｃｈｉｌｄ＝＝ｃ）ｃｄ——ｓｔａｎ］＝…０’；ｅｌｓｅｃｄ——ｓｔａ州＝ ［１】吴乐南．数据压缩［Ｍ】．北京：电子工业出版社，２００３． …１’； 【２】严蔚敏，吴伟民．数据结构（ｃ语言版）［Ｍ】．北京：清华大学出版 ＨＣｉｌ＝（ｃｈａｒ ）ｍａｌｌｏｃ（ｎ—ｓｔａｒｔ）＊ｓｉｚｅｏｆ（ｃｈａｒ））； 社。１９９７． Ｓｔｒｃｐｙ（ＨＣｉ］，＆ｃｄｓｔａｒｔ】）； ［３】王永刚．奇妙的二叉树【Ｄ】．程序员，２００３，（９）． 一２４９—
