基于状态转移矩阵的Hilbert码快速生成算法

1 引言

空间填充曲线的线性映射可将多维数据序列化为一维数据，便于多维数据在磁盘上的存储与索引[1]，这种映射模式在影像压缩、行程编码形式的栅格数据表达、空间划分[2-6]、空间查询[7]、空间索引[8]、计算几何中的启发式搜索等领域应用广泛。空间排列码(Spatial Ordering Code)以连续整数与空间填充曲线实体集元素建立起一一对应的可逆对应关系，奠定了空间填充曲线相关算法的基础。目前，应用最广泛的空间排列方法包括 Morton 码、Gray码及 Hilbert 码。经大量应用验证，Hilbert 空间排列码具有最好的空间聚集及空间连续性[7-10]因此，本文提出一种基于状态转移矩阵的快速 Hilbert 码计算方法，减少了算法过程中的递归和迭代次数，提升了 Hilbert 码的计算效率，有利于 Hilbert 码的推广及深入应用。

2 Hilbert 空间填充曲线及其空间排列码算法

2.1 Hilbert空间填充曲线

Hilbert 空间填充曲线属于 Peano 曲线族，具有FASS(Space Filling, Self-Avoiding, Simple and Self-Similar)特征，Hilbert 曲线可以不间断、不自交地通过栅格所有格元，且每一格元仅被通过一次[11-12]。 Hilbert 曲线对完整空间作逐级双向等分分割，第 1次分割可得到4个区域，将每个区域称为格元，经过k 次分割后可得到k 个子格元，每个子格元的边长为 原 完 整 空 间 边 长 的 2- k。 将 这 些 格 元 记 为Ak i i= 1,2,…,4k)

2.2 Hilbert空间排列码算法

二进制位操作的 Hilbert 空间排列码生成算法，由 Faloutsos 和 Roseman 在 1989 年提出并通过计算机实现[1]，它基于格网行列坐标进行二进制位操作，需进行迭代循环，其算法时间复杂度为 O(n2) 。陆锋等在 2001 年提出基于空间层次分解的生成算法[13]，王笋等在 2006 年提出基于曲线扫描矩阵的生成算法[14]。鉴此，本文提出了一种基于状态转移矩阵的 Hilbert 码快速生成算法，避免了算法中的嵌套循环，将 Hilbert 码生成算法的时间复杂度降为稳定的 O(n) ;同时，通过引入位域结构体，避免了计算过程中的数值与字符串间的类型转换，进而提高了Hilbert码生成算法的性能。

更多内容请下载附件查看