黑名單快速匹配算法的研究

戴琳琳，張晨陽，苗 凡，閻志遠

（中國鐵道科學研究院 電子計算技術研究所，北京 100081）

隨著互聯網技術的深入發展,中國鐵路客票系統也實現了互聯網在線售票，目前中國鐵路互聯網注冊用戶達7 000多萬，每天用戶的平均登錄數達數百萬,高峰時可達千萬。在互聯網售票中，惡意購票者或被政府管理機構定義為惡意用戶，將被列入黑名單。如何實現在百萬級乃至千萬級的黑名單中，快速定位給定的用戶信息成為影響用戶體驗至關重要的環節。黑名單（Blacklist）指記錄惡意用戶的信息列表，用戶信息可以是電話號碼、身份證號、IP地址或用戶名等，本文以電話號碼黑名單的快速匹配為例，闡述其相應的實現算法。

1 問題引入

問題假設給定了電話號碼黑名單集合，需要判定一個給定號碼是否落在黑名單中。

黑名單的輸入有以下3種形式：

（1）給定1個完整號碼，如13500001234。

（2）給定1個號碼前綴，如1381010XXXX。

（3）給定1個號碼區間，如[15901015555，15901023333]。

每秒鐘可能有幾十萬次的匹配請求。每次請求的輸入是一個完整的電話號碼，系統輸出‘是’或‘否’，表示該號碼是否在黑名單中。

2 二分查找定位算法

2.1 黑名單描述

如何在系統里存儲和表示黑名單，是解決黑名單問題的關鍵之一。一個最簡單的想法是用位圖來描述所有可能的電話號碼。假定最大的電話號碼是19999999999，那么它需要內存、空間開銷很大。不同國家的電話號碼長度不一樣，采用位圖的算法很難保持通用性。

更形象的做法是把黑名單表示為數軸上一些區間的集合。對于數軸上給定的一個點，問題轉化一個穿刺查詢（Stabbing Query）；若該點落在任意一個區間里，則返回‘是’，否則返回‘否’。

很明顯，第2種描述方式將會使用更少的空間。對于黑名單輸入的3種方式都能很容易地換化為區間，為保持通用性，使用64位整數表示電話號碼。使用C++描述黑名單區間數據結構如下：

2.2 區間扁平化

在開始查詢前對區間數據進行預處理能夠有效提高查詢效率。下面的算法能將原始輸入中所有相交的或者相鄰的區間合并，并按照順序排列。這里使用到的算法是采用特化的模板less用于對黑名單區間集合進行排序，排序的標準是黑名單區間的左端點的比較，那么相交或相鄰的區間就會依序排序到一起，方便合并，使用C++描述黑名單區間扁平化算法如下：

例如：

輸入區間：[100, 500] [300, 600] [100, 150][601, 601] [700, 900]

輸出區間：[100, 601] [700, 900]

2.3 算法實現

算法基本思路是：需要查找的黑名單已經處理為既不相交、也不相鄰、并按順序排列的區間集合，用二分查找可以較快定位待查詢的號碼。使用C++描述二分查找定位算法如下，其中，disjoint為黑名單區間集合，q為待查詢的號碼數值。

算法優點：實現簡單。目前C++標準std庫的組件都支持二分查找法，實現更為方便。

算法缺點：

（1）比較次數為O（logN），其中N為區間的數目。

（2）無法有效支持黑名單的動態增加或刪除，如果需要增加新的黑名單，需要重新生成黑名單。

（3）若給出的待查號碼為字符串，沒有考慮將串轉化為UINT64的開銷。

3 字典樹算法

3.1 黑名單描述

算法基本思路是：將黑名單轉化為前綴集合，使用字典樹（Trie）進行最長前綴匹配（Longest Prefix Match）。

構造5位數字電話號碼前綴字典樹的例子如圖1所示，包括95588，9526X，766XX。其中X表示任意一個數字。

圖1 構造5位數字電話號碼前綴字典樹示例

從圖1可以看出，對于號碼前綴的公共部分，其存儲空間是共享的。匹配時，從根節點出發，沿著邊的指示前進，如果遇到葉子節點（橘色），說明匹配成功，號碼屬于黑名單；否則匹配失敗。

3.2 構建前綴集合

對于黑名單輸入中給定完整號碼和前綴的情況很容易構建前綴集合，但如果給定號碼區間，需要用下面的算法將其轉化為一系列前綴。

例如輸入[95588, 96600]，輸出結果如下：

[95589, 95589] Prefix = 95589

[95590, 95599] Prefix = 9559

[95600, 95699] Prefix = 956

[95700, 95799] Prefix = 957

[95800, 95899] Prefix = 958

[95900, 95999] Prefix = 959

[96000, 96099] Prefix = 960

[96100, 96199] Prefix = 961

[96200, 96299] Prefix = 962

[96300, 96399] Prefix = 963

[96400, 96499] Prefix = 964

[96500, 96599] Prefix = 965

[96600, 96600] Prefix = 96600

3.3 算法實現

傳統字典樹的實現主要考慮以下2種情況：

（1）對于樹節點的分支比較少的情況，可以在每個節點中分配固定數目的分支指針。這樣做的好處是查詢快速，但是空間浪費大。

（2）對于節點的分支比較多的情況，可以將分支組織成鏈表甚至散列表，目的是節省空間，但是查詢分支效率受到影響。

在電話號碼黑名單匹配的這種應用中，其分支數目為10，以上2種實現方式都有很大缺點。

采用三叉樹（TST，Ternary Search Tree）可以比較好地解決這個問題。三叉樹結合了查找二叉樹（BST）和字典樹（trie）的優點，能夠實現前綴匹配操作，并保持較小的空間消耗。在效率方面，可以理解為TST在節點中尋找下一路徑指針時進行了一次二分查找。平均而言，由于實際的分支因子（Branching Factor）遠小于10，因此查詢的效率仍然很高。

三叉樹與傳統的二叉樹相比，區別是三叉樹有3個字節點，分別是左節點（left），中間節點（mid），右節點（right）。插入關鍵字（key） 的時候，從樹根作為當前節點開始（樹為空的時候樹根為nil），一個字符一個字符的遞歸執行下面過程：

（1）如果當前節點為 nil，則創建一個新的節點，將當前字符保存在節點中，將其設置為當前節點。

（2）如果當前字符和當前節點保存的字符都為‘/0’，將數據存于當前節點，終止調用。

（3）如果當前字符小于當前節點保存的字符，那么遞歸將當前字符插入節點的左子節點，大于則插入右子節點；相等則將下一個字符插入當前節點的中間子節點。

搜索的過程和插入類似，把關鍵字一個字符一個字符的和樹中節點保存的字符進行比較，同樣從樹根開始遞歸執行。

（1）如果當前節點為 nil，則查找失敗。

（2）如果當前字符比節點中的小，遞歸對左子節點查找，依然比較當前字符。

（3）如果當前字符比節點中的大，遞歸對右子節點查找，依然比較當前字符。

（4）如果當前字符與節點中的相等且都為‘/0’，則這個節點中就存著關鍵字對應的值，終止調用。如果相等但是不是‘/0’，則遞歸對中間子節點查找，比較字符為下一個字符。

存儲 ‘42’，‘766’，‘767’，‘9526’，‘95588’串的TST樹如圖2所示。

圖2 TST樹示例圖

類似于其他字典樹數據結構，三叉樹里每個節點代表存儲串的一個前綴，所有存儲在一個節點的中間樹的串都以該節點的字符為前綴。

類似于二叉樹，三叉樹依賴于存儲串的插入次序，可以是平衡的或非平衡的。在一個存儲n個串的平衡三叉樹中查找一個m長度的串，需要O（m+log n）次字符的比較。同時，TST也可以使用節點壓縮方法來減少節點數，比如節點‘4-2’，‘7-6’，‘9-5’，‘5-8-8’，在壓縮的三叉樹中，每當插入一個新節點，最多一個現有的節點需要分裂。

算法優點：

（1）時間復雜度O（m+log n），節點訪問次數不會超過電話號碼的長度。

（2）對于匹配失敗的情況（號碼不在黑名單中），數字比較次數往往遠小于號碼長度。

（3）能夠有效支持黑名單的動態增加和刪除。

（4）若給出的待查號碼為字符串，無須將其顯式轉化為UINT64。

算法缺點：

（1）實現復雜。

（2）每匹配一個數字都要進行一次內存訪問。克服的辦法是采用路徑壓縮，將無分支的路徑壓縮成一條邊，只有真正產生區分的數字才分裂出節點，如圖3所示。

圖3 路徑壓縮示例圖

4 結束語

雖然在理論上使用字典樹數據結構進行前綴查找非常有效，但實際應用中由于其實現的復雜性，同時由于需要分配大量固定長度的節點，會使標準的堆空間分配（如C++中的new）遭受性能和空間上的雙重損失，因此如果在查找時間要求不是太苛刻的情況下，二分查找法是比較通用和簡便的算法，該算法目前已在實驗系統中實現，查詢效率比較理想，在1 000多萬條電話號碼的黑名單中，查詢給定的號碼所需時間小于0.5 s，但還需要在實際應用中繼續完善。本文所述的算法還可以應用在IP地址前綴匹配、身份證號碼前綴匹配等問題中。

[1] 劉春煌. 鐵道部客票中心系統的設計與關鍵技術的實現[J].中國鐵道科學，2001，22（2）：15-22.

[2] 唐 堃.中間件技術在客票系統中的實現及應用[J].中國鐵道科學，2004，25（3）：103-107.