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

来源：电子与信息学报杂志2024年第2期北京时间：

作者：贾连印, 范瑶, 丁家满, 李晓武, 游进国

单位：1.昆明理工大学信息与自动化学院 昆明 6505002.云南省计算机应用重点实验室 昆明 650500

摘要：3维Hilbert空间填充曲线(3D HSFC)的编码和解码效率对空间查询处理、图像处理等领域的应用举足轻重。现有的3维编解码算法独立编解码每一个点，忽略了Hilbert曲线的局部保持特性。为了提高编解码效率，该文设计了高效的3D状态视图，并提出一种新的前缀约简的3D HSFC编码算法(PR-3HE)和前缀约简3D HSFC解码算法(PR-3HD)，这两个算法通过公共前缀的定义和识别、公共前缀约简及多种优化技术来最小化需要编码的阶数，从而提高3D HSFC的编解码效率。理论上证明：当编码或解码一个\begin{document}$k$\end{document}阶的窗体(窗体内总共含有\begin{document}${2^k} imes {2^k} imes {2^k}$\end{document}个点)时，PR-3HE平均每个点的编码阶数不超过2，PR-3HD平均解码阶数不超过8/7。相对于传统的基于迭代的方法，编解码时间复杂度从\begin{document}$O(k)$\end{document}降低到了\begin{document}$O(1)$\end{document}。实验结果表明，该文算法在模拟数据集和真实数据集上的表现显著优于现有算法。

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

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