基于状态视图的高效Hilbert编码和解码算法

State View Based Efficient Hilbert Encoding and Decoding Algorithms

Hilbert曲线是高维降到1维的重要方法,具有较好的空间聚集和空间连续性,在地理信息系统、空间数据库、信息检索等方面有广泛的应用。现有Hilbert编码或解码算法未考虑输入数据对编码或解码效率的影响,因此将不同输入数据同等对待。为此,该文通过设计高效的状态视图并结合快速置位检测算法提出高效的免计前0的Hilbert编码算法(FZF-HE)和免计前0的Hilbert解码算法(FZF-HD),可快速识别输入数据前部为0而无需迭代计算的部分,从而降低迭代查询次数及算法复杂度,提高编解码效率。实验结果表明,FZF-HE算法和FZF-HD算法在数据均匀分布时效率稍高于现有算法,而在数据偏斜分布时效率远高于现有算法。

Hilbert curve is an important method for high-dimensional reduction to one-dimensional.It has good characteristics of spatial aggregation and spatial continuity and is widely used in geographic information system,spatial databases and information retrieval.Existing Hilbert encoding or decoding algorithms do not consider the differences between input data,thus treating them equally.To this end,an efficient Hilbert coding algorithm Front-Zero-Free Hilbert Encoding(FZF-HE)and an efficient decoding algorithm Front-Zero-Free Hilbert Decoding(FZF-HD)are proposed.FZF-HE and FZF-HD can quickly identify the 0 s of the front part of input data before iterative calculation by combining efficient state views and first bit-1 detection algorithm,thus reducing the number of iterations and the complexity of the algorithm,and improving the encoding and decoding efficiency.The experimental results show that efficiencies of these two algorithms are slightly higher than existing algorithms for uniform distributed data,and are much higher than existing algorithms for skew distributed data.