高效前缀约简的三维Hilbert空间填充曲线编解码算法  

3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction

作　　者：贾连印[1,2] 范瑶 丁家满 李晓武[1] 游进国[1] JIA Lianyin;FAN Yao;DING Jiaman;LI Xiaowu;YOU Jinguo(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;Key Laboratory of Computer Technology Application of Yunnan Province,Kunming 650500,China)

机构地区：[1]昆明理工大学信息与自动化学院,昆明650500 [2]云南省计算机应用重点实验室,昆明650500

出　　处：《电子与信息学报》2024年第2期633-642,共10页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(62262035,62262034,62062046)。

摘　　要：3维Hilbert空间填充曲线(3D HSFC)的编码和解码效率对空间查询处理、图像处理等领域的应用举足轻重。现有的3维编解码算法独立编解码每一个点,忽略了Hilbert曲线的局部保持特性。为了提高编解码效率,该文设计了高效的3D状态视图,并提出一种新的前缀约简的3D HSFC编码算法(PR-3HE)和前缀约简3D HSFC解码算法(PR-3HD),这两个算法通过公共前缀的定义和识别、公共前缀约简及多种优化技术来最小化需要编码的阶数,从而提高3D HSFC的编解码效率。理论上证明:当编码或解码一个k阶的窗体(窗体内总共含有2k×2k×2k个点)时,PR-3HE平均每个点的编码阶数不超过2,PR-3HD平均解码阶数不超过8/7。相对于传统的基于迭代的方法,编解码时间复杂度从O(k)降低到了O(1)。实验结果表明,该文算法在模拟数据集和真实数据集上的表现显著优于现有算法。The encoding and decoding efficiency of 3D Hilbert Space Filling Curve(3D HSFC)is key for the application of spatial query processing,image processing.The existing 3D encoding and decoding algorithms encode and decode each point independently,ignoring the local preservation characteristic of Hilbert curve.To improve the efficiency of encoding and decoding,an efficient 3D state view is designed in this paper,and a new Prefix Reduction 3D HSFC Encoding Algorithm(PR-3HE)and Prefix Reduction 3D HSFC Decoding Algorithm(PR-3HD)are proposed.These two algorithms minimize the orders to be processed through the definition and identification of common prefix,common prefix reduction and various optimization techniques,thus improving 3D HSFC encoding and decoding efficiency.Theoretical proof is provided in this paper,2k×2k×2kdemonstrating that when encoding or decoding a k-order window(all points in a window),PR-3HE passively encodes no more than 2 orders for each coordinate on average,while PR-3HD passively decodes no more than 8/7 orders for each Hilbert code on average.The encoding and decoding time complexity can be O(k)O(1)reduced from to.Experimental results show on both synthetic and real dataset the benefits of our algorithms over the other counterparts.

关 键 词：3维Hilbert空间填充曲线 3维状态视图 前缀约简 3D HSFC编码算法 3D HSFC解码算法 

分 类 号：TN911.2[电子电信—通信与信息系统] TP301.6[电子电信—信息与通信工程]