13数字化用户 2013 年第 10 期 user网络通信构造移动通信中降低能耗的前缀码的动态规划加速研究刘磊 （ 张家口 市桥东区宝善街81号移动公司 河北 张家口 ）【摘要】 动态规划属算法设计方案， 多 用 在寻找问问题最优解方面。 若把动态规划的所有子问题皆看作有向图 的节点， 则动态规划便可被考虑成对应的有向无圈图。 针对某些具有特殊结构的有向无圈图， 其往往可以为动态规划提供更大的便捷度。 移动通信通常采用 优化通信编码方案， 已达到控制宿主能耗的目 的。 本文就移动通信内 降低能耗的前缀码的动态规划加速问题展开讨论。【关键词】 移动通信前缀码动态规划时间复杂度一、 前缀码 所谓前缀码， 其一直被定性为计算机科学和信息论领域的经典问题。 如果要对n个符号予以二进制编码， 则编码仅需依托贪婪算法和O(nlgn) 的时间复杂度便可获取该组符号的最优编码。 编码亦可用来推到r个码元的最优编码。 如果单词以排序状态出现频率， 编码算法可把时间复杂度控制到O(m) 阶段。 针对前缀码问题， 诸多学者皆做了大量的研究。

研究证实， 编码后字符串内码元的分布位置对对应码元的长度起决定性的作用。 基于此， 本文引入了一种构造前缀码的动态规划改进法， 即把动态规划的状态集合以若干批次呈现出来， 而状态结合间呈相互依赖关系。 通过对各状态值予以成批量计算后， 便可把计算各状态的平摊时间复杂度控制到O(1) 。二、 预备知识（一） 问题定义为了实现对问题的形式化定义， 本文引入如下参数量：N为待编码的符号集合； n为符号集合的取值； pi为各符号的分布概率。 本文认为概率的排序问题对算法时间复杂度的影响并不大。 基于此， 本文假定概率已排序（p1≥p2≥p3……≥pn） , 编码后的字符串集合记做W=﹛ w1, w2, w3……, wn w1的长度记做的期望长度可表示为：1本文讨论的问题为： 移动任一可行编码的宿主， 由此发出的任一单词wi的耗能皆存有上界U， 其中时， 本文需要从整个编码W内挑选出一个满足的W 。（二） 最优树性质若编码为二进制， 则一个前缀码通常可映射到一棵二叉树， 其中二叉树的叶节点与前缀码的待编码符号呈一一对应关系。 针对二叉树的边， 本文把向左的边记做1， 向右的边记做0， 此时可把叶节点与根节点间分布的01字符串假定为叶节点对应符号的编码。 就节点v而言， 如果节点与根节点间的距离长约i， 则该节点便被看作分布在第i层。 如果仅对二叉树第i层及以上部分作出考虑， 则此情况可被称作i层数或i层部分树。 本文把i层树的节点深度表述为d(v) ， 而通常把节点与根节点间分布的1的...