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

王防修

(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)



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

王防修

(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)

摘要：针对目前符号序列的编码存在编码速度慢的问题，提出了一种通过减少平均查找长度来提高编码速度的算法。根据符号概率的大小，设计了顺序查找、大概率优先查找和小概率优先查找三种编码算法。通过对这三种编码算法的平均查找长度的分析比较，结果表明：大概率优先查找算法的平均查找长度最短。根据符号本身的大小，设计了折半查找和二叉排序树查找两种编码算法。通过对这两种编码算法的平均查找长度的分析比较，结果表明折半查找编码算法的平均查找长度最短。因此，最优的编码算法应从大概率优先查找算法和折半查找算法之中选择其一。算例表明，为了提高符号序列的编码速度，对同一符号序列的编码，应从大概率优先查找算法和折半查找算法中选择平均查找长度最短的算法作为编码算法。

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

1引言

作为一种即时码，前缀码[1]在信息编码过程中得到广泛应用。其中，哈夫曼编码[2]、香农编码[3]和费诺编码是最常见的前缀码。设符号序列X=x1x2…xm包含n个互异符号ci(i=1,2,…,n)，即∀xi∈X，有xi∈{c1,c2,…,cn}。bi是对应ci的前缀码，pi是ci在X中出现的概率，li是bi的码长。所谓编码，就是将X中的每个符号用对应的码字替换。对于符号序列X中的每个符号xi,如果存在cj=xi,则用码字bi替换X中的xi。……