應(yīng)用于大數(shù)據(jù)的Trie樹排序算法

趙林潔，肖 英+，張 宇

(1.中國計量大學(xué) 信息工程學(xué)院，浙江 杭州 310018；2.中國計量大學(xué) 浙江省電磁波信息技術(shù)與計量 檢測重點實驗室，浙江 杭州 310018；3.杭州代碼哥智能科技有限公司 研發(fā)中心，浙江 杭州 310018)

0 引 言

據(jù)統(tǒng)計，2018年全球數(shù)據(jù)量總和33 ZB(1 ZB=1萬GB)，國際數(shù)據(jù)公司發(fā)布的最新版白皮書《Data Age 2025》預(yù)測2025年全球數(shù)據(jù)量總和將達(dá)到175 ZB[1]，該數(shù)據(jù)總量正在以指數(shù)級速率增長，這意味著數(shù)據(jù)分析和處理對算法提出了更高的要求，排序是數(shù)據(jù)處理的核心運算，涉及到人工智能[2]、機器學(xué)習(xí)[3]、模式識別[4]和大數(shù)據(jù)[5]等領(lǐng)域，然而面對數(shù)據(jù)量劇增的現(xiàn)象現(xiàn)有的排序算法已經(jīng)無法滿足當(dāng)下數(shù)據(jù)處理的需求，迫切需要一個在動態(tài)增加數(shù)據(jù)的場景下時間、空間性能更優(yōu)的排序算法。

排序是將一個任意序列重新排成一個按某種規(guī)則排列的有序序列[6]。如冒泡排序、選擇排序、插入排序等傳統(tǒng)排序算法以兩兩之間的比較為基礎(chǔ)，時間復(fù)雜度為O(n2)，這些基于“比較”的排序算法在最壞情況下能達(dá)到的最優(yōu)時間復(fù)雜度為O(nlogn)[7]?？焖倥判蛩惴ㄊ遣捎梅种尾呗?，通過遞歸的方式將待排數(shù)據(jù)根據(jù)基準(zhǔn)值分割成大小兩部分，直到數(shù)據(jù)變成有序序列[8]，其時間復(fù)雜度為O(nlogn)。該算法結(jié)構(gòu)簡單，平均性能較佳，是多數(shù)排序應(yīng)用的最佳選擇[9]，但是如果在排序過程中動態(tài)添加和刪除數(shù)據(jù)時，該算法性能大大降低。而堆排序算法是利用堆積樹結(jié)構(gòu)設(shè)計的一個完全二叉樹，時間復(fù)雜度為O(nlogn)[10]。該算法通過樹形結(jié)構(gòu)保存部分比較結(jié)果，從而減少了比較次數(shù)，但是在實際應(yīng)用中頻繁更新數(shù)據(jù)時，每次更新都需要重做一遍堆的維護(hù)，這非常費時[11]。文獻(xiàn)[12]中的AVL樹(Adelson-Velsky-Landis Tree)解決了數(shù)據(jù)頻繁更新的問題，該結(jié)構(gòu)所有節(jié)點左右子樹的高度差不超過1，插入時間復(fù)雜度為O(nlogn)。雖然AVL樹支持?jǐn)?shù)據(jù)動態(tài)更新，但其追求絕對平衡，每次插入新節(jié)點后旋轉(zhuǎn)次數(shù)無法預(yù)知，且為維護(hù)AVL樹高度平衡付出的代價太大[13]，故而不實用。文獻(xiàn)[14]中提出的紅黑樹是AVL樹的變形，該算法只追求大致平衡，保證每次插入節(jié)點最多3次旋轉(zhuǎn)達(dá)到平衡，與AVL樹時間復(fù)雜度相差不大，應(yīng)用更為廣泛，是多種編程語言底層實現(xiàn)采納較多的數(shù)據(jù)結(jié)構(gòu)，如實現(xiàn)C++、Java、C#等類庫中的Map、Set結(jié)構(gòu)的底層[15]。然而紅黑樹的高度隨著數(shù)據(jù)量的增加而增加，紅黑樹的查找性能會逐漸降低，且每次進(jìn)行插入、刪除時都需要自底向上調(diào)整使新的二叉樹滿足紅黑樹的性質(zhì)，耗時較多。因而，需要一種在海量數(shù)據(jù)下查找性能穩(wěn)定且空間效率更高的算法結(jié)構(gòu)。

因此，本文提出了一種16-bit Trie樹排序算法，該算法借助16-bit Trie樹結(jié)構(gòu)利用鄰居節(jié)點找到臨近的鏈節(jié)點指針進(jìn)行插入排序。在構(gòu)造Trie樹時，該算法使用動態(tài)數(shù)組存儲子節(jié)點指針，避免了固定數(shù)組存儲子節(jié)點時的空間浪費，并且引入了詞綴壓縮方法使該算法在處理大規(guī)模數(shù)據(jù)時更具突出優(yōu)勢。

1 16-bit Trie 樹排序算法

16-bit Trie樹結(jié)構(gòu)在構(gòu)造Trie樹時使用16 bit表示子節(jié)點信息，每個節(jié)點至多有16個子節(jié)點，因此，命名為16-bit Trie樹。16-bit Trie樹排序算法是在16-bit Trie樹結(jié)構(gòu)上利用鄰居節(jié)點保存的鏈節(jié)點指針L，將新增加的鏈節(jié)點指針插入到鏈節(jié)點L處完成排序。接下來，本節(jié)將具體介紹16-bit Trie樹排序算法進(jìn)行數(shù)據(jù)排序的過程。

1.1 基本定義

16-bit Trie樹結(jié)構(gòu)的節(jié)點信息定義見表1。

根據(jù)表1描述16-bit Trie樹結(jié)構(gòu)從父節(jié)點索引到子節(jié)點。首先，構(gòu)建一個二維數(shù)組LeafsInfoMap映射表見表2，

表1 節(jié)點信息定義

行表示子節(jié)點狀態(tài)，列表示當(dāng)前節(jié)點狀態(tài)下第i個子節(jié)點(i=0表示子節(jié)點不存在)。關(guān)于LeafsInfoMap映射表有兩種操作：LeafsInfoMap[leafsInfo][nodeValue]表示在leafsInfo狀態(tài)下值為nodeValue的子節(jié)點位置，LeafsInfoMap[leafsInfo][17]表示leafsInfo的子節(jié)點總數(shù)。其次，根據(jù)表1中的兩個數(shù)組leafsInfo和leafs，構(gòu)建父節(jié)點、子節(jié)點，leafsInfo和leafs是對應(yīng)關(guān)系。例如，父節(jié)點的leafsInfo為5(二進(jìn)制為0000 0000 0000 0101)，表示父節(jié)點有兩個子節(jié)點，值為0的子節(jié)點和值為2的子節(jié)點，分別存儲在leafs[0]和leafs[1]。由于子節(jié)點存儲在leafs數(shù)組中，通過leafs[LeafsInfoMap[leafsInfo][nodeValue]-1]可以從父節(jié)點索引到值為nodeValue的子節(jié)點。如上述例子，父節(jié)點的leafsInfo為5，如表2所示，通過LeafsInfoMap[5][0]=1可以找到值為0的子節(jié)點是父節(jié)點的第1個子節(jié)點，保存在leafs[0]中；通過LeafsInfoMap[5][2]=2可以找到值為2的子節(jié)點是父節(jié)點的第2個子節(jié)點，保存在leafs[1]中。以上可以看出，利用leafsInfoMap映射表和節(jié)點的leafsInfo信息可查詢當(dāng)前節(jié)點下的所有子節(jié)點信息。

此外，16-bit Trie樹結(jié)構(gòu)在構(gòu)造Trie樹時使用動態(tài)數(shù)組leafs存儲子節(jié)點指針，其數(shù)組大小隨著子節(jié)點數(shù)的變化而變化。如上例中，父節(jié)點再添加值為1的子節(jié)點時，leafsInfo變?yōu)?000 0000 0000 0111，而leafs數(shù)組長度變?yōu)?，分別存儲3個子節(jié)點指針。

1.2 算法描述

16-bit Trie樹排序算法是利用16-bit Trie樹中的鄰居節(jié)點查找鄰近的鏈節(jié)點指針L，將新鏈節(jié)點指針插入到鏈節(jié)點L處，從而完成鏈表排序。傳統(tǒng)的Trie樹是先構(gòu)建后遍歷完成數(shù)據(jù)排序，而16-bit Trie樹排序是邊構(gòu)建邊排序，完成構(gòu)建樹的同時完成鏈表排序。為了進(jìn)一步提高16-bit Trie樹排序算法的時間性能，引入詞綴壓縮方法，在能區(qū)分不同關(guān)鍵字的情況下，最大限度地減少構(gòu)建的節(jié)點數(shù)，從而提升排序速度，16-bit Trie樹排序算法的流程如圖1所示，具體實施步驟如下：

表2 LeafsInfoMap映射

圖1 算法流程

例如，關(guān)鍵字集合K={‘de’，‘fg’，‘dec’，‘dea’，‘ta’} 進(jìn)行16-bit Trie樹排序的過程。首先初始化16-bit Trie樹結(jié)構(gòu)和排序鏈表如圖2(a)和圖2(b)所示，正方形表示根節(jié)點，圓形表示鏈節(jié)點。在圖2(a)中根節(jié)點Root沒有子節(jié)點，leafsInfo占16 bit的空間其值為0，由于沒有子節(jié)點leafs數(shù)組不占用空間，其leafsInfo、leafs數(shù)組，如圖3(a)所示。

圖2 16-bit Trie樹結(jié)構(gòu)和空鏈表

圖3 節(jié)點信息的變化情況

插入第一個關(guān)鍵字‘de’，如圖4(a)所示構(gòu)建16-bit Trie樹結(jié)構(gòu)，圖中六邊形表示子節(jié)點，十六角型表示多值節(jié)點，在16-bit Trie樹結(jié)構(gòu)上實現(xiàn)排序的具體步驟如下：

(1)獲取關(guān)鍵字‘de’，當(dāng)前節(jié)點定位至根節(jié)點Root；

(2)判斷關(guān)鍵字‘de’并未完全插入；

(3)取d的高4位記作d high_4bits，將根節(jié)點leafsInfo的第d high_4bits位置1，在根節(jié)點leafs數(shù)組的第LeafsInfoMap[leafsInfo][d high_4bits]-1個位置保存節(jié)點1，根節(jié)點的leafsInfo、leafs數(shù)組由圖3(a)變到圖3(b)；

(4)當(dāng)前節(jié)點定位至節(jié)點1，取d的低4位記作d low_4bits，判斷關(guān)鍵字長度大于1，創(chuàng)建一個多值節(jié)點2，將leafsInfo的第d low_4bits位置1，leafs中的第LeafsInfoMap[leafsInfo][d low_4bits]-1個位置保存節(jié)點2，在節(jié)點2的AdressNode數(shù)組中存儲詞綴‘e’，節(jié)點1的leafsInfo、leafs數(shù)組如圖3(b)所示，轉(zhuǎn)至(5)；

(5)當(dāng)前節(jié)點定位至節(jié)點2，由于父節(jié)點不存在，新建鏈節(jié)點‘de’，在節(jié)點2的leafs[0]中存入鏈節(jié)點指針‘de’，將鏈節(jié)點‘de’插入到頭節(jié)點‘Head’之后尾節(jié)點‘Rear’之前，節(jié)點2的leafsInfo、leafs數(shù)組如圖3(b)所示，鏈表排序結(jié)果如圖4(b)所示。

圖4 添加關(guān)鍵字‘de’

為了觀察當(dāng)前節(jié)點如何借助鄰居節(jié)點完成鏈表排序，插入第二個關(guān)鍵字‘fg’，如圖5(a)所示。根節(jié)點Root的leafsInfo、leafs數(shù)組保持不變，節(jié)點1的子節(jié)點是節(jié)點2和節(jié)點3，leafs數(shù)組長度為2，節(jié)點1的leafsInfo、leafs數(shù)組由圖3(b)變到圖3(c)。節(jié)點3是多值節(jié)點，其數(shù)組AdressNode保存詞綴‘g’，新建鏈節(jié)點指針‘fg’，通過父節(jié)點(節(jié)點1)查找到鄰居節(jié)點(節(jié)點2)，取節(jié)點2上的鏈節(jié)點指針‘de’，將新建的鏈節(jié)點指針‘fg’插到鏈節(jié)點指針‘de’之后，如圖5(b)所示完成鏈表排序，最后將鏈節(jié)點指針‘fg’保存在節(jié)點3的leafs[0]中。

圖5 添加關(guān)鍵字‘fg’

按上述方法插入集合K中所有數(shù)據(jù)，16-bit Trie樹結(jié)構(gòu)和鏈表排序結(jié)果如圖6(a)和圖6(b)所示，圖中用菱形表示有效節(jié)點，各節(jié)點的leafsInfo、leafs數(shù)組如圖3(d)所示。由于關(guān)鍵字‘de’和‘dea’共用一條路徑，為了區(qū)分關(guān)鍵字‘de’和‘dea’，設(shè)置了有效節(jié)點標(biāo)記位，如圖6(a)所示，節(jié)點6、節(jié)點9分別是‘de’和‘dea’的有效節(jié)點，從根節(jié)點到有效節(jié)點代表一條完整的路徑，即可根據(jù)有效節(jié)點區(qū)分同一路徑上不同的關(guān)鍵字‘de’和‘dea’。多值節(jié)點是特殊的有效節(jié)點，是保存了詞綴的有效節(jié)點，在必要情況下需要取多值節(jié)點的詞綴再構(gòu)建新節(jié)點。

圖6 16-bit Trie結(jié)構(gòu)和16-bit Trie排序鏈表

2 結(jié)果分析

本文的測試環(huán)境為Windows操作系統(tǒng)Intel(R) Core(TM) i7-8700CPU @3.20 GHz 3.19 16 GB內(nèi)存的PC機上測試，編譯器為Visual Studio 2019，使用C++語言編程，用GetTickCount()函數(shù)來統(tǒng)計實驗中各操作所消耗的時間，為了減小測試誤差，測試的時間均取5次測試的平均值。

本文采用與快速排序算法、傳統(tǒng)Trie樹對比的方式來評估16-bit Trie樹排序算法的時間性能?？焖倥判蛩惴ú捎肅標(biāo)準(zhǔn)庫函數(shù)qsort實現(xiàn)動態(tài)數(shù)據(jù)排序，傳統(tǒng)Trie樹采用26叉樹實現(xiàn)字符串排序。本文的測試數(shù)據(jù)是使用MATLAB生成的由英文字母a-z組成的任意長度的隨機字符串，測試數(shù)據(jù)分為定長、定量2種數(shù)據(jù)，定長數(shù)據(jù)是字符長度均為15字符的隨機數(shù)據(jù)；定量數(shù)據(jù)是指數(shù)據(jù)量固定、字符長度變化的數(shù)據(jù)。通過以上2種測試數(shù)據(jù)對快速排序、16-bit Trie樹排序、傳統(tǒng)Trie樹的排序時間進(jìn)行測試并分析其時間性能。

2.1 定長數(shù)據(jù)

表3對3種算法在數(shù)據(jù)長度為15字符時的排序時間進(jìn)行了記錄。從表3可以計算出，當(dāng)數(shù)據(jù)量從150萬增加到550萬時，3種算法的排序時間分別增加了68.6倍、14.4倍、3.9倍。傳統(tǒng)Trie樹排序增長倍數(shù)最小，但初始排序時間開銷較大，整體排序時間用時較多；16-bit Trie樹排序次之，而快速排序在數(shù)據(jù)動態(tài)增加時排序時間增長最快。

表3 定長數(shù)據(jù)的排序時間/ms

圖7是數(shù)據(jù)長度為15字符時快速排序、16-bit Trie樹排序和傳統(tǒng)Trie樹排序從初始50萬數(shù)據(jù)量逐次增加50萬至550萬時花費的排序時間。如圖7所示，傳統(tǒng)Trie樹、16-bit Trie樹都需要構(gòu)建Trie樹且排序時間都呈線性增長，16-bit Trie樹的增幅比傳統(tǒng)Trie樹的增幅小，且整體排序時間開銷也較少。與快速排序相比，16-bit Trie樹排序算法在數(shù)據(jù)量較小時耗時多，是因為構(gòu)建16-bit Trie樹結(jié)構(gòu)花費較多時間，而快速排序算法無需構(gòu)建直接進(jìn)行排序，故而快速排序算法在數(shù)據(jù)量較小時耗時少。從圖7可以發(fā)現(xiàn)，當(dāng)數(shù)據(jù)量動態(tài)增加到250萬時，16-bit Trie樹排序算法的時間開銷與快速排序接近；當(dāng)數(shù)據(jù)量動態(tài)增加到400萬時，比快速排序快27%；當(dāng)數(shù)據(jù)量進(jìn)一步增加到550萬時，比快速排序快45%。

圖7 定長數(shù)據(jù)的排序時間

從圖7可見，16-bit Trie樹的排序時間遠(yuǎn)低于傳統(tǒng)Trie樹的排序時間，這說明16-bit Trie樹排序比傳統(tǒng)Trie樹通過遍歷樹完成排序的性能更好。傳統(tǒng)Trie樹不需要額外空間，通過遍歷整個Trie樹完成字典樹排序，時間開銷會很大。16-bit Trie樹排序算法是在構(gòu)建Trie樹時借助鄰近節(jié)點完成鏈表排序，不需要遍歷大量節(jié)點，故而節(jié)省很多時間。而快速排序與16-bit Trie樹排序的時間差值隨著數(shù)據(jù)量的增加而增加，這說明16-bit Trie樹排序算法在處理大規(guī)模動態(tài)數(shù)據(jù)時更具優(yōu)勢。相比快速排序，16-bit Trie樹排序算法優(yōu)勢逐漸突顯有兩點原因:一是支持動態(tài)添加數(shù)據(jù)，當(dāng)添加新數(shù)據(jù)時只需要對新增加的數(shù)據(jù)進(jìn)行排序，而快速排序算法的排序時間隨著數(shù)據(jù)量的增加而增加，這是因為當(dāng)添加新數(shù)據(jù)時快速排序算法必須另辟一個能裝下原始數(shù)據(jù)和新增加數(shù)據(jù)的大空間進(jìn)行重排序；二是16-bit Trie樹結(jié)構(gòu)有公共前綴的特性，該特性減少了構(gòu)建的節(jié)點數(shù)，必然節(jié)省排序時間。

以上測試發(fā)現(xiàn)另辟空間、重排序影響快速排序的時間性能，接下來，在相同數(shù)據(jù)量時測試排序次數(shù)對快速排序與16-bit Trie樹排序的影響力。圖8表示兩種算法從初始50萬數(shù)據(jù)量逐次增加50萬至550萬時使用一次排序和分兩次進(jìn)行排序的時間，曲線1是使用一次快速排序，曲線2是使用一次16-bit Trie樹排序，曲線3是分兩次進(jìn)行快速排序，曲線4是分兩次進(jìn)行16-bit Trie樹排序。如圖8所示，隨著數(shù)據(jù)量增加曲線1比曲線3耗時更少，快速排序算法使用一次快速排序比分兩次進(jìn)行排序用時更少，這說明另辟空間、重排序?qū)焖倥判蛩惴ㄓ休^大影響，重排次數(shù)越多排序耗時越多。而曲線2、曲線4基本重合，使用一次排序和分兩次進(jìn)行排序?qū)?6-bit Trie樹排序算法基本沒有影響，這表明數(shù)據(jù)動態(tài)增加對16-bit Trie樹排序算法并無太大影響，16-bit Trie樹排序算法支持動態(tài)添加數(shù)據(jù)。

圖8 使用一次快速排序和兩次快速排序的排序時間

2.2 定量數(shù)據(jù)

圖9是3種算法在初始100萬數(shù)據(jù)量再動態(tài)增加20個數(shù)據(jù)的場景下數(shù)據(jù)長度為3-15字符時的排序時間。從圖9可以看出，傳統(tǒng)Trie樹在數(shù)據(jù)長度為3-15字符時其排序時間隨著字符長度的增加而增加，這是因為傳統(tǒng)Trie樹每增加一個字符，在構(gòu)建和遍歷Trie樹時就需要多構(gòu)建和遍歷一個節(jié)點，故而隨著字符長度的增加排序時間也逐漸增加。對于快速排序與16-bit Trie樹排序，當(dāng)數(shù)據(jù)長度為3-5字符時，兩種算法的時間增幅都很大，但當(dāng)數(shù)據(jù)長度為6-15字符時，16-bit Trie樹排序算法基本沒有增長趨勢，快速排序算法有增長但增幅相比之前變小。在6-15字符范圍內(nèi)，增加數(shù)據(jù)長度并沒有對16-bit Trie樹排序算法產(chǎn)生很大影響，這是因為引入詞綴壓縮方法優(yōu)化了16-bit Trie樹結(jié)構(gòu)，減少構(gòu)建的節(jié)點數(shù)量，故而在數(shù)據(jù)量相同時增加數(shù)據(jù)長度并不會對排序時間產(chǎn)生較大影響。而快速排序算法在6-15字符范圍內(nèi)有增長但增幅變小，是因為使用前5個字符就可以區(qū)分100萬數(shù)據(jù)量，故而在數(shù)據(jù)長度為6-15字符時增幅變小。

圖9 定量數(shù)據(jù)的排序時間

從圖9可以發(fā)現(xiàn)，在測試數(shù)據(jù)相同的情況下快速排序與16-bit Trie樹排序的排序時間相差較大，快速排序算法耗時很多，是因為動態(tài)增加20個數(shù)據(jù)共進(jìn)行20次快速排序，另辟空間、重排序使快速排序的時間開銷很大，而16-bit Trie樹排序算法直接對增加的20個數(shù)據(jù)進(jìn)行排序，故而用時較少。

3 結(jié)束語

本文基于鄰居節(jié)點提出了一種16-bit Trie樹排序算法，該算法支持動態(tài)增加數(shù)據(jù)，引入了詞綴壓縮方法減少了構(gòu)建的節(jié)點數(shù)，從而提高了整體排序速度。16-bit Trie樹排序算法在構(gòu)造16-bit Trie樹時，使用動態(tài)數(shù)組存儲子節(jié)點，避免了固定數(shù)組存儲子節(jié)點時的空間浪費。

結(jié)果表明，相比其它兩種算法，傳統(tǒng)Trie樹通過遍歷整個Trie樹完成字典樹排序的時間開銷最大；16-bit Trie樹排序算法在數(shù)據(jù)動態(tài)增加時耗時最少，而快速排序在數(shù)據(jù)量較小時耗時較少，隨著數(shù)據(jù)量的動態(tài)增加排序時間極速增加，這表明16-bit Trie樹排序算法在處理大規(guī)模動態(tài)數(shù)據(jù)時更具優(yōu)勢。