An Optimal Algorithm for Prufer Codes
An Optimal Algorithm for Prufer Codes
复制标题
Prufer码的优化算法
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Yingjie Wu
中科院分区：
文献类型：
--
作者：
Xiaodong Wang;Lei Wang;Yingjie Wu
本文研究了标记树Prufer码的编解码算法。文献中对标记树的Prufer码进行编码和解码的算法通常需要时间。尽管存在类似 Prufer 码的线性时间算法 [1,2,3]，但这些算法利用整数排序算法。利用待排序整数的特殊范围，得到线性时间整数排序算法。普鲁弗码问题被简化为整数排序。在本文中，我们从不同的角度和更直接的方式考虑普鲁弗码问题。我们从一个简单的算法开始，然后逐步改进它，最终得到一个非常实用的线性时间算法。我们在本文中使用的技术本身就很有趣。
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 time usually. Although there exist linear time algorithms for Prufer-like codes [1,2,3], 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 naive algorithm, then improved it gradually and finally we obtain a very practical linear time algorithm. The techniques we used in this paper are of interest in their own right.