[發明專利]號碼集合的存儲、查詢方法及其裝置

有效

• 申請號: 201310199286.6
• 申請日: 2013-05-24
• 公開（公告）號: CN103345469A
• 公開（公告）日: 2013-10-09
• 發明（設計）人: 劉勝
• 申請（專利權）人: 聯動優勢科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 黃志華

技術領域

本發明涉及計算機數據結構領域，具體地，涉及一種號碼集合的存儲、查詢方法及其裝置。

背景技術

在計算機信息系統中，通常用由一串號碼（例如數字和字母的組合）表示的某種ID來標識一類關鍵信息，比如，手機號、銀行卡號、身份證號、人民幣鈔票編號等。為了防范風險，在很多重要的業務中，需要判斷這些ID是否在某個集合中，如黑名單或白名單。

如果要判斷一個元素是不是在一個集合里，通常是將所有元素保存起來作為元素集合，然后將待判元素和存儲的元素集合進行比較，從而確定待判元素是否在元素集合中。鏈表、樹、散列表（又稱哈希表，Hash?table）等數據結構都是采用這種思路，這三種數據結構的空間復雜度都是O（n），而檢索時間復雜度分別為O（n），O（log?n），O（1）。從時間效率來看，這三種數據結構中只有哈希表的檢索速度是固定的，不會隨集合大小增加而增加。從存儲空間上來看，三者都會隨集合大小增加而增加，當集合數據總量大到一定程度時候，其存儲結構所占用的空間太大，甚至會超出了普通單一主機的物理內存的容量，而導致無法完成檢索。

針對這種情況，一般可通過如下幾個方案來改善其空間存儲效率：

方案一：將集合數據存放到外部存儲空間中，如外部文件、外部單一數據庫、外部多個數據庫等，從而減少占用所需占用本機內存空間。

方案二：采用布隆過濾器（Bloom?Filter）算法，其原理是，當一個元素被加入集合時，通過k個哈希函數將這個元素映射成一個位尾號列表（Bit?Array）中的k個點，把它們置為1。檢索時：如果所有點都是1的話，那么元素可能在集合內；如果有0的話，元素則肯定不在集合內。相比于其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數O（k）。其最大的缺點是存在一定的錯誤率，即當其判斷結果為“在集合內”時，可能是誤判。

但是，上述方案均存在一些技術問題。

上述第一種方案，有如下技術缺點：從空間上，本質無改進，只是從本機的內存空間移出到了外部。使用單一數據庫時，所能存放的黑名單數據容量依然有限。而使用多個數據庫時，雖然空間容量接近無限，但是訪問操作會比較復雜。從時間上，由于需要頻繁訪問外部存儲空間，降低了訪問操作的效率。不管是單庫還是多庫，訪問性能都會隨著數據量的增大而降低，響應延遲不斷增加，最終導致不可訪問。

上述第二種方案，有如下技術缺點：這種算法是通過犧牲了一定的準確率來提高空間存儲效率和查詢效率。主要體現在：只有其判斷結果為“不在集合內”時，可確保是正確判斷；而當其判斷結果為“在集合內”時，則可能是誤判。

在另一方面，在某些如支付之類的重要實時交易中，往往需要對海量黑名單數據進行精確判斷。

上述第一方案，訪問時間效率上不符合要求，需要頻繁訪問外部存儲。

上述第二方案，在準確率上不符合精確判斷的要求。

可見，目前在對諸如白名單或黑名單的號碼集合進行存儲和查詢的技術方案中，存在訪問時間效率和空間存儲效率低下，查詢準確率低的問題。

發明內容

有鑒于此，本發明實施例提供了一種號碼集合的存儲、查詢方法及其裝置，用以解決現有技術中號碼集合的存儲和查詢方案中存在的訪問時間效率和空間存儲效率低下、查詢準確率低的問題。

本發明實施例技術方案如下：

一種號碼集合的存儲方法，包括：根據預定號碼格式識別出號碼集合中各個號碼所包括的號段，所述預定號碼格式為號碼包括號段和尾號；分別建立與所識別出的不同號段對應的尾號列表，根據預定的尾號的位數和尾號的計數進制確定尾號列表中的列表元素的數量，并按照尾號的計數順序設置尾號列表中的列表元素的序號；依次讀取號碼集合中的號碼，對于當前號碼，在當前號碼的號段所對應的尾號列表中將序號為當前號碼的尾號的列表元素的值設置為預定標識，該預定標識表示號碼集合中存儲有當前號碼；分別存儲號段和與號段對應的尾號列表。