基于前缀码的快速编码算法研究  

Fast encoding algorithm research based on prefix codes

作　　者：王防修[1] 

机构地区：[1]武汉轻工大学数学与计算机学院,湖北武汉430023

出　　处：《武汉轻工大学学报》2015年第4期60-64,共5页Journal of Wuhan Polytechnic University

基　　金：国家自然科学基金资助项目(61179032)

摘　　要：针对目前符号序列的编码存在编码速度慢的问题,提出了一种通过减少平均查找长度来提高编码速度的算法。根据符号概率的大小,设计了顺序查找、大概率优先查找和小概率优先查找三种编码算法。通过对这三种编码算法的平均查找长度的分析比较,结果表明:大概率优先查找算法的平均查找长度最短。根据符号本身的大小,设计了折半查找和二叉排序树查找两种编码算法。通过对这两种编码算法的平均查找长度的分析比较,结果表明折半查找编码算法的平均查找长度最短。因此,最优的编码算法应从大概率优先查找算法和折半查找算法之中选择其一。算例表明,为了提高符号序列的编码速度,对同一符号序列的编码,应从大概率优先查找算法和折半查找算法中选择平均查找长度最短的算法作为编码算法。In view of the current symbol sequence encoding having the problem of slow encoding speed, this paper proposes an algorithm to improve the encoding speed by reducing the average search length. According to the symbol probability, it designs three coding algorithm that are a sequential search, big probability priority first search and small probability priority first search. Through the analysis and comparison of the average search length of the three coding algorithm, teh results show that the average search length is the shortest for the big probability priority search algorithm. According to the size of the symbol itself, it designs two kinds of coding algorithm, one binary search and the other two binary sort tree search. Through the analysis of the average search length of the two coding algorithm, the results show that the average search length of the binary search algorithm is the shortest. Therefore, the optimal coding algorithm must be selected from one of big probability priority search algorithm and binary search algorithm. Examples show that, in order to improve the encoding speed of the symbol sequence , for the same symbol sequences, one must be chosn between big probability priority search algorithm and binary search algorithm which has the shortest average search length as the coding algorithm.

关 键 词：顺序查找 折半查找 二叉排序树查找 平均查找长度 编码速度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]