基于一次排序动态编码的Huffman编码算法  

A SORT-ONCE AND DYNAMIC ENCODING (SODE) BASED HUFFMAN CODING ALGORITHM

作　　者：刘燕清[1] 龚声蓉[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《计算机应用与软件》2009年第12期86-88,176,共4页Computer Applications and Software

基　　金：江苏省高校自然科学基金(07KJD520186)

摘　　要：Huffman编码作为一种高效的不等长编码技术正日益广泛地在文本、图像、视频等数据压缩、存储及通信等领域得到应用。为了有效提高时空效率、简化编码思想和操作,首先研究了传统Huffman编码的算法及具体做法,并针对性地提出了一种基于一次排序动态编码的Huffman编码算法。与传统的Huffman算法及近年来国内外文献中提出的改进算法相比,该方法从编码思想上将构树简化为线性编码,在空间复杂度相近的情况下,不仅时间复杂度上有明显降低,而且编码步骤和相关操作更简洁,更利于程序的实现和移植。实验结果验证了算法的有效性。As an efficient and simple variable-length coding technique, Huffman codes are being widely used in compression, transmission and storage areas for text,image and video data and so on. To improve spatiotemporal efficiency and simplify encoding procedure, a Huffman coding algorithm based on SODE is proposed in this paper in pertinence to the study of the traditional Huffman coding algorithm （THCA） and its implementation. Compared with THCA and other improved algorithms in literatures at home and abroad recently, the proposed algorithm simplifies the Huffman tree construction to linear encoding proceeding from the encoding conception,so it has much lower complexity in time and more concise encoding procedure and related operation though with almost the same space complexity, these make the program easier to be implemented and transplanted. Experimental results have verified the validity of the proposed algorithm.

关 键 词：数据压缩 动态编码 线性编码 HUFFMAN树 编码算法 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TN919.81[自动化与计算机技术—计算机科学与技术]