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

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)。实验结果表明,该文算法在模拟数据集和真实数据集上的表现显著优于现有算法。