Prufer编解码的最优算法  

Optimal Algorithm for Coding and Decoding Prufer Codes

作　　者：王晓东[1] 吴英杰[1] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002

出　　处：《小型微型计算机系统》2008年第4期687-690,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60172017)资助;福建省自然科学基金项目(A0510008)资助

摘　　要：讨论标号树的Prufer编码的编解码算法.文献中常见的Prufer编解码算法需要O(nlogn)时间.文献[1,2,4,9]提出了Prufer编解码的线性时间算法.这些算法都用到了整数排序算法,利用待排序整数的取值特殊性,得到线性时间整数排序算法.由此将Prufer编解码问题的计算归结为整数排序问题.本文从更直接的角度考察Prufer编解码问题,从简单算法出发,挖掘问题的本质特征,逐步简化,得到Prufer编码的一个非常简单实用的线性时间最优编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.This paper studies the algorithms for coding and decoding Prufer codes of a labeled tree. The algorithms for coding and decoding Prufer codes of a labeled tree in the literatures require O（n log n） time usually. Although there exist linear time algorithms for Prufer-like codes[-1,2,4,9], the algorithms utilize the integer sorting algorithms. The special range of the integers to be sorted is utilized to obtain a linear time integer sorting algorithm. The Prufer code problem is reduced to integer sorting. In this paper we consider the Prufer code problem in a different angle and a more direct manner. We start from a na？ ve algorithm, then improved it gradually and finally we obtain a very practical linear time algorithm. The techniques we used in this paper are interesting themselves.

关 键 词：标号树 Prufer编码 整数排序 最优算法 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]