基于狀態(tài)視圖的高效Hilbert編碼和解碼算法
doi: 10.11999/JEIT190501
-
1.
昆明理工大學(xué)信息與自動(dòng)化學(xué)院 昆明 650500
-
2.
云南省計(jì)算機(jī)應(yīng)用重點(diǎn)實(shí)驗(yàn)室 昆明 650500
-
3.
云南師范大學(xué)圖書館技術(shù)部 昆明 650500
State View Based Efficient Hilbert Encoding and Decoding Algorithms
-
1.
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
-
2.
Key Laboratory of Computer Technologies Application of Yunnan Province, Kunming 650500, China
-
3.
Library of Yunnan Normal University, Kunming 650500, China
-
摘要:
Hilbert曲線是高維降到1維的重要方法,具有較好的空間聚集和空間連續(xù)性,在地理信息系統(tǒng)、空間數(shù)據(jù)庫(kù)、信息檢索等方面有廣泛的應(yīng)用?,F(xiàn)有Hilbert編碼或解碼算法未考慮輸入數(shù)據(jù)對(duì)編碼或解碼效率的影響,因此將不同輸入數(shù)據(jù)同等對(duì)待。為此,該文通過(guò)設(shè)計(jì)高效的狀態(tài)視圖并結(jié)合快速置位檢測(cè)算法提出高效的免計(jì)前0的Hilbert編碼算法(FZF-HE)和免計(jì)前0的Hilbert解碼算法(FZF-HD),可快速識(shí)別輸入數(shù)據(jù)前部為0而無(wú)需迭代計(jì)算的部分,從而降低迭代查詢次數(shù)及算法復(fù)雜度,提高編解碼效率。實(shí)驗(yàn)結(jié)果表明,F(xiàn)ZF-HE算法和FZF-HD算法在數(shù)據(jù)均勻分布時(shí)效率稍高于現(xiàn)有算法,而在數(shù)據(jù)偏斜分布時(shí)效率遠(yuǎn)高于現(xiàn)有算法。
-
關(guān)鍵詞:
- 狀態(tài)視圖 /
- 免計(jì)前0的Hilbert編碼算法 /
- 免計(jì)前0的Hilbert解碼算法 /
- Hilbert曲線
Abstract: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.
-
表 1 編碼狀態(tài)視圖
狀態(tài) 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 坐標(biāo) 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 編碼 00 01 11 10 00 11 01 10 10 11 01 00 10 01 11 00 下階狀態(tài) 1 0 3 0 0 2 1 1 2 1 2 3 3 3 0 2 下載: 導(dǎo)出CSV
表 2 解碼狀態(tài)視圖
狀態(tài) 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 編碼 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 坐標(biāo) 00 01 11 10 00 10 11 01 11 10 00 01 11 01 00 10 下階狀態(tài) 1 0 0 3 0 1 1 2 3 2 2 1 2 3 3 0 下載: 導(dǎo)出CSV
表 3 FZF-HE算法
輸入:X,橫坐標(biāo) Y,縱坐標(biāo) n,階 輸出:Hilbert編碼$Z$ (1) Z←0 (2) $p$←${\rm{msb}}(\max(X,Y))$//置位檢測(cè) (3) $t$←($n$-$p$-1)%2//計(jì)算第$n$-$p$階狀態(tài) (4) for $i$ from $n$-$p$ to $n$ (5) $Z{\rm{ = }}Z{{ < < 2 | {\rm{Key}}[}}t{\rm{][}}{x_i}{\rm{][}}{y_i}{\rm{] }}$//查Key視圖 (6) $t{\rm{ = Type[}}t{\rm{][}}{x_i}{\rm{][}}{y_i}{\rm{]}}$//查Type視圖 下載: 導(dǎo)出CSV
表 4 FZF-HD算法
輸入:$Z$,Hilbert編碼 n,階 輸出:X,橫坐標(biāo) Y,縱坐標(biāo) (1) $X$, $Y$←0 (2) $p$←${\rm{msb}}(Z)$//置位檢測(cè) (3) $t$←($n$-$p$/2-1)//計(jì)算第$n$-$p$/2階狀態(tài) (4) for $i$ from $n$-$p$/2 to $n$ (5) ${\rm{coord}} = {\rm{InvKey}}[t][{z_{2i - 1}}{z_{2i}}]$ //查InvKey視圖 (6) $ Y = Y < < 1 | {\rm{coord}} \& 0{\rm{x}}1 $ $ X = X < < 1 | {\rm{coord}} > > 1\& 0{\rm{x}}1 $ (7) $t = {\rm{InvType}}[t][{z_{2i - 1}}{z_{2i}}]$//查InvType視圖 下載: 導(dǎo)出CSV
-
GUNTHER S and STOCCO L. Generation of spatial orders and space-filling curves[J]. IEEE Transactions on Image Processing, 2015, 24(6): 1791–1800. doi: 10.1109/TIP.2015.2409571 周映虹, 馬爭(zhēng)鳴. 基于層次模型的重要性編碼算法[J]. 電子與信息學(xué)報(bào), 2009, 31(6): 1497–1500.ZHOU Yinghong and MA Zhengming. A significance coding algorithm based on layer model[J]. Journal of Electronics &Information Technology, 2009, 31(6): 1497–1500. CHEN Lu, GAO Yunjun, LI Xinhan, et al. Efficient metric indexing for similarity search and similarity joins[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(3): 556–571. doi: 10.1109/TKDE.2015.2506556 SINGH H and BAWA S. A survey of traditional and mapReduceBased spatial query processing approaches[J]. ACM SIGMOD Record, 2017, 46(2): 18–29. doi: 10.1145/3137586.3137590 ABDULJABBAR M, MARKOMANOLIS G S, IBEID H, et al. Communication reducing algorithms for distributed hierarchical N-Body problems with boundary distributions[C]. The 32nd International Supercomputing Conference, Frankfurt, Germany, 2017: 79–96. LIU Hui, WANG Kun, YANG Bo, et al. Dynamic load balancing using hilbert space-filling curves for parallel reservoir simulations[C]. The SPE Reservoir Simulation Conference, Montgomery, USA, 2017. doi: 10.2118/182613-MS. HAN Guangjie, XUAN Xuan, LIU Li, et al. A disaster management-oriented path planning for mobile anchor node-based localization in wireless sensor networks[J]. IEEE Transactions on Emerging Topics in Computing, 2020, 8(1): 115–125. doi: 10.1109/TETC.2017.2687319 KONG Lingping, PAN J S, SUNG T W, et al. An energy balancing strategy based on hilbert curve and genetic algorithm for wireless sensor networks[J]. Wireless Communications and Mobile Computing, 2017, 2017: 5720659. BOHM C, PERDACHER M, and PLANT C. A novel hilbert curve for cache-locality preserving loops[J]. IEEE Transactions on Big Data, To be published. doi: 10.1109/TBDATA.2018.2830378 MORTON G M. A computer oriented geodetic data base and a new technique in file sequencing[EB/OL]. https://domino.research.ibm.com/library/cyberdig.nsf/0/0dabf9473b9c86d48525779800566a39?OpenDocument, 1966. BUTZ A R. Alternative algorithm for Hilbert's space-filling curve[J]. IEEE Transactions on Computers, 1971, C-20(4): 424–426. doi: 10.1109/T-C.1971.223258 MOON B, JAGADISH H V, FALOUTSOS C, et al. Analysis of the clustering properties of the hilbert space-filling curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124–141. doi: 10.1109/69.908985 NAGARKAR P, CANDAN K S, and BHAT A. Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads[J]. Proceedings of The VLDB Endowment, 2015, 8(12): 1382–1393. doi: 10.14778/2824032.2824038 CHRISTOFORAKI M, HE Jinru, DIMOPOULOS C, et al. Text vs. space: Efficient geo-search query processing[C]. The 20th ACM International Conference on Information and Knowledge Management, Glasgow, UK, 2011: 423–432. FISHER A J. A new algorithm for generating Hilbert curves[J]. Practice and Experience, 1986, 16(1): 5–12. doi: 10.1002/spe.4380160103 李紹俊, 鐘耳順, 王少華, 等. 基于狀態(tài)轉(zhuǎn)移矩陣的Hilbert碼快速生成算法[J]. 地球信息科學(xué)學(xué)報(bào), 2014, 16(6): 846–851.LI Shaojun, ZHONG Ershun, WANG Shaohua, et al. An algorithm for Hilbert ordering code based on state-transition matrix[J]. Journal of Geo-Information Science, 2014, 16(6): 846–851. XCTORRES. Hilbert_spatial_index[EB/OL]. https://github.com/xcTorres/hilbert_spatial_index, 2017. BURKARDT J. HILBERT_CURVE convert between 1D and 2D coordinates of Hilbert curve[EB/OL]. http://people.math.sc.edu/Burkardt/c_src/hilbert_curve/hilbert_curve.html, 2015. MOORE D. Fast Hilbert curve generation, sorting, and range queries[EB/OL]. https://github.com/Cheedoong/hilbert, 2016. 曹雪峰, 萬(wàn)剛, 張宗佩. 緊致的Hilbert曲線Gray碼索引算法[J]. 測(cè)繪學(xué)報(bào), 2016, 45(S1): 90–98. doi: 10.11947/j.AGCS.2016.F010CAO Xuefeng, WAN Gang, and ZHANG Zongpei. Compact Hilbert curve index algorithm based on Gray code[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1): 90–98. doi: 10.11947/j.AGCS.2016.F010 LI R. Hilbert range query decomosition[EB/OL]. https://github.com/cloudray8580/Hilbert RangeQueryDecomosition, 2019. ZHANG Jian and KAMATA S I. A generalized 3-D Hilbert scan using look-up tables[J]. Journal of Visual Communication and Image Representation, 2012, 23(3): 418–425. doi: 10.1016/j.jvcir.2011.12.005 LIU Hui, CUI Tao, LENG Wei, et al. Encoding and decoding algorithms for arbitrary dimensional Hilbert order[J]. 2016, arXiv: 1601.01274. 劉輝, 冷偉, 崔濤. 高維Hilbert曲線的編碼與解碼算法設(shè)計(jì)[J]. 數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用, 2015, 36(1): 42–58.LIU Hui, LENG Wei, and CUI Tao. Development of encoding and decoding algorithms for high dimensional Hilbert curves[J]. Journal on Numerical Methods and Computer Applications, 2015, 36(1): 42–58. ROSETTA. Find first and last set bit of a long integer[EB/OL]. http://rosettacode.org/wiki/Find_first_and_last_set_bit_of_a_long_integer, 2019. -