應用于大數據的Trie樹排序算法

趙林潔，肖 英+，張 宇

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

0 引 言

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

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

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

1 16-bit Trie 樹排序算法

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

1.1 基本定義

16-bit Trie樹結構的節點信息定義見表1。

根據表1描述16-bit Trie樹結構從父節點索引到子節點。首先，構建一個二維數組LeafsInfoMap映射表見表2，

表1 節點信息定義

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

此外，16-bit Trie樹結構在構造Trie樹時使用動態數組leafs存儲子節點指針，其數組大小隨著子節點數的變化而變化。如上例中，父節點再添加值為1的子節點時，leafsInfo變為0000 0000 0000 0111，而leafs數組長度變為3，分別存儲3個子節點指針。

1.2 算法描述

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

表2 LeafsInfoMap映射

圖1 算法流程

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

圖2 16-bit Trie樹結構和空鏈表

圖3 節點信息的變化情況

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

(1)獲取關鍵字‘de’，當前節點定位至根節點Root；

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

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

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

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

圖4 添加關鍵字‘de’

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

圖5 添加關鍵字‘fg’

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

圖6 16-bit Trie結構和16-bit Trie排序鏈表

2 結果分析

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

本文采用與快速排序算法、傳統Trie樹對比的方式來評估16-bit Trie樹排序算法的時間性能。快速排序算法采用C標準庫函數qsort實現動態數據排序，傳統Trie樹采用26叉樹實現字符串排序。本文的測試數據是使用MATLAB生成的由英文字母a-z組成的任意長度的隨機字符串，測試數據分為定長、定量2種數據，定長數據是字符長度均為15字符的隨機數據；定量數據是指數據量固定、字符長度變化的數據。通過以上2種測試數據對快速排序、16-bit Trie樹排序、傳統Trie樹的排序時間進行測試并分析其時間性能。

2.1 定長數據

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

表3 定長數據的排序時間/ms

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

圖7 定長數據的排序時間

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

以上測試發現另辟空間、重排序影響快速排序的時間性能，接下來，在相同數據量時測試排序次數對快速排序與16-bit Trie樹排序的影響力。圖8表示兩種算法從初始50萬數據量逐次增加50萬至550萬時使用一次排序和分兩次進行排序的時間，曲線1是使用一次快速排序，曲線2是使用一次16-bit Trie樹排序，曲線3是分兩次進行快速排序，曲線4是分兩次進行16-bit Trie樹排序。如圖8所示，隨著數據量增加曲線1比曲線3耗時更少，快速排序算法使用一次快速排序比分兩次進行排序用時更少，這說明另辟空間、重排序對快速排序算法有較大影響，重排次數越多排序耗時越多。而曲線2、曲線4基本重合，使用一次排序和分兩次進行排序對16-bit Trie樹排序算法基本沒有影響，這表明數據動態增加對16-bit Trie樹排序算法并無太大影響，16-bit Trie樹排序算法支持動態添加數據。

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

2.2 定量數據

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

圖9 定量數據的排序時間

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

3 結束語

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

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