基于狀態(tài)轉(zhuǎn)移矩陣的Hilbert碼快速生成算法

1 引言

空間填充曲線的線性映射可將多維數(shù)據(jù)序列化為一維數(shù)據(jù)，便于多維數(shù)據(jù)在磁盤上的存儲與索引[1]，這種映射模式在影像壓縮、行程編碼形式的柵格數(shù)據(jù)表達(dá)、空間劃分[2-6]、空間查詢[7]、空間索引[8]、計(jì)算幾何中的啟發(fā)式搜索等領(lǐng)域應(yīng)用廣泛?？臻g排列碼(Spatial Ordering Code)以連續(xù)整數(shù)與空間填充曲線實(shí)體集元素建立起一一對應(yīng)的可逆對應(yīng)關(guān)系，奠定了空間填充曲線相關(guān)算法的基礎(chǔ)。目前，應(yīng)用最廣泛的空間排列方法包括 Morton 碼、Gray碼及 Hilbert 碼。經(jīng)大量應(yīng)用驗(yàn)證，Hilbert 空間排列碼具有最好的空間聚集及空間連續(xù)性[7-10]因此，本文提出一種基于狀態(tài)轉(zhuǎn)移矩陣的快速 Hilbert 碼計(jì)算方法，減少了算法過程中的遞歸和迭代次數(shù)，提升了 Hilbert 碼的計(jì)算效率，有利于 Hilbert 碼的推廣及深入應(yīng)用。

2 Hilbert 空間填充曲線及其空間排列碼算法

2.1 Hilbert空間填充曲線

Hilbert 空間填充曲線屬于 Peano 曲線族，具有FASS(Space Filling, Self-Avoiding, Simple and Self-Similar)特征，Hilbert 曲線可以不間斷、不自交地通過柵格所有格元，且每一格元僅被通過一次[11-12]。 Hilbert 曲線對完整空間作逐級雙向等分分割，第 1次分割可得到4個(gè)區(qū)域，將每個(gè)區(qū)域稱為格元，經(jīng)過k 次分割后可得到k 個(gè)子格元，每個(gè)子格元的邊長為 原 完 整 空 間 邊 長 的 2- k。 將 這 些 格 元 記 為Ak i i= 1,2,…,4k)

2.2 Hilbert空間排列碼算法

二進(jìn)制位操作的 Hilbert 空間排列碼生成算法，由 Faloutsos 和 Roseman 在 1989 年提出并通過計(jì)算機(jī)實(shí)現(xiàn)[1]，它基于格網(wǎng)行列坐標(biāo)進(jìn)行二進(jìn)制位操作，需進(jìn)行迭代循環(huán)，其算法時(shí)間復(fù)雜度為 O(n2) 。陸鋒等在 2001 年提出基于空間層次分解的生成算法[13]，王筍等在 2006 年提出基于曲線掃描矩陣的生成算法[14]。鑒此，本文提出了一種基于狀態(tài)轉(zhuǎn)移矩陣的 Hilbert 碼快速生成算法，避免了算法中的嵌套循環(huán)，將 Hilbert 碼生成算法的時(shí)間復(fù)雜度降為穩(wěn)定的 O(n) ;同時(shí)，通過引入位域結(jié)構(gòu)體，避免了計(jì)算過程中的數(shù)值與字符串間的類型轉(zhuǎn)換，進(jìn)而提高了Hilbert碼生成算法的性能。

更多內(nèi)容請下載附件查看