Neville编解码问题的线性时间算法  

Optimal Algorithm for Coding and Decoding Neville Codes

作　　者：林志庆[1] 吴英杰[2] 王晓东[2,3] 

机构地区：[1]福州大学现代教育技术中心,福建福州350002 [2]福州大学数学与计算机学院,福建福州350002 [3]泉州师范学院计算机系,福建泉州362000

出　　处：《小型微型计算机系统》2010年第10期1984-1988,共5页Journal of Chinese Computer Systems

基　　金：福建省自然科学基金项目(2009J01295)资助;福建省高校服务海西建设重点项目(A099)资助

摘　　要：讨论标号树的Neville编码的编解码算法.文献中常见的第2种Neville编解码算法需要O(nlogn)时间.近期研究文献指出至今尚未找到第2种Neville编解码的线性时间算法.本文对第2种Neville编解码问题的本质特征进行较深入的分析,从简单算法出发,逐步简化,得到一个非常简单实用的O(n)时间Neville编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.Studied the algorithms for coding and decoding Neville＇s second codes of a labeled tree. The algorithms for coding and decoding Neville＇s second codes of a labeled tree in the literatures require O（ n log n） time usually. As stated in [ 1 ] [ 2 ], no linear time algorithms for the Neville＇s second codes. In this paper we consider the Neville＇s second 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.

关 键 词：标号树 Neville编码 深度优先搜索 最优算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]