[發(fā)明專利]基數(shù)統(tǒng)計方法、裝置、系統(tǒng)、設(shè)備和計算機可讀存儲介質(zhì)

有效

• 申請?zhí)枺?/td>: 202010339945.1
• 申請日: 2020-04-26
• 公開（公告）號: CN111563109B
• 公開（公告）日: 2023-09-01
• 發(fā)明（設(shè)計）人: 杜紅光;羅華林;何凱;夏春偉
• 申請（專利權(quán)）人: 北京奇藝世紀科技有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/22
• 代理公司: 北京華夏泰和知識產(chǎn)權(quán)代理有限公司 11662
• 代理人: 張麗穎

本發(fā)明實施例提供了一種基數(shù)統(tǒng)計方法、裝置、系統(tǒng)、設(shè)備和計算機可讀存儲介質(zhì)。該方法在數(shù)據(jù)節(jié)點側(cè)獲取目標數(shù)據(jù)和目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)；利用哈希算法，對目標數(shù)據(jù)進行哈希計算，獲得目標數(shù)據(jù)對應(yīng)的哈希值；利用位圖算法，為目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)生成位圖數(shù)組；利用預(yù)設(shè)的哈希表，對應(yīng)存儲目標數(shù)據(jù)對應(yīng)的哈希值和為目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)生成的位圖數(shù)組；將哈希表向預(yù)設(shè)的計算節(jié)點發(fā)送。該方法在計算節(jié)點側(cè)接收多個數(shù)據(jù)節(jié)點分別發(fā)送的哈希表；合并多個數(shù)據(jù)節(jié)點分別發(fā)送的哈希表，在合并后得到的哈希表中，對多個位圖數(shù)組按照比特位執(zhí)行基數(shù)統(tǒng)計處理。本發(fā)明通過兩層哈希的方式可以節(jié)省數(shù)據(jù)的存儲空間并且快速、準確的完成基數(shù)統(tǒng)計。

技術(shù)領(lǐng)域

本發(fā)明涉及計算機技術(shù)領(lǐng)域，特別是涉及一種基數(shù)統(tǒng)計方法、裝置、系統(tǒng)、設(shè)備和計算機可讀存儲介質(zhì)。

背景技術(shù)

基數(shù)統(tǒng)計用于統(tǒng)計一批數(shù)據(jù)中的不重復(fù)元素數(shù)據(jù)的個數(shù)。基數(shù)統(tǒng)計常見于計算獨立用戶數(shù)（Unique?Visitor，簡稱UV）、維度的獨立取值數(shù)等應(yīng)用場景中。在實際生產(chǎn)環(huán)境中，經(jīng)常會遇到要求基數(shù)統(tǒng)計精準的場景。例如：在對網(wǎng)站的訪問入口分別進行兩種方式的調(diào)整（如入口外觀不同）之后，需要對這兩種入口進行AB實驗，在AB實驗中，需要精確統(tǒng)計預(yù)設(shè)時間段內(nèi)這兩種入口分別對應(yīng)的獨立用戶訪問量，以便對這兩種入口進行上線前的數(shù)據(jù)分析。

目前，在分布式計算環(huán)境下，常用的基數(shù)統(tǒng)計算法為HyberLogLog算法。

針對HyberLogLog算法而言，由于元素數(shù)據(jù)的數(shù)量級和存儲空間為正比關(guān)系，所以HyberLogLog算法為了在有限的存儲空間中標記足夠多的元素數(shù)據(jù)，在存儲元素數(shù)據(jù)時，對元素數(shù)據(jù)進行了壓縮處理，但是，該壓縮處理使得元素數(shù)據(jù)本身出現(xiàn)了數(shù)據(jù)損失，元素數(shù)據(jù)出現(xiàn)數(shù)據(jù)損失使得HyberLogLog算法的計算精確性較低，誤差較大，無法滿足精確統(tǒng)計的要求。

發(fā)明內(nèi)容

本發(fā)明實施例的目的在于提供一種基數(shù)統(tǒng)計方法、裝置、系統(tǒng)、設(shè)備和計算機可讀存儲介質(zhì)，以解決現(xiàn)有的基數(shù)統(tǒng)計方式的統(tǒng)計精度較低的問題。

針對上述技術(shù)問題，本發(fā)明實施例的具體技術(shù)方案如下：

在本發(fā)明實施的第一方面，首先提供了一種基數(shù)統(tǒng)計方法，在數(shù)據(jù)節(jié)點側(cè)執(zhí)行的步驟，包括：獲取目標數(shù)據(jù)以及所述目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)；利用預(yù)設(shè)的哈希算法，對所述目標數(shù)據(jù)進行哈希計算，以便獲得所述目標數(shù)據(jù)對應(yīng)的哈希值；利用預(yù)設(shè)的位圖算法，為所述目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)生成位圖數(shù)組；其中，所述位圖數(shù)組中的每個比特位映射一個待基數(shù)統(tǒng)計的維度元素；利用預(yù)設(shè)的哈希表，對應(yīng)存儲所述目標數(shù)據(jù)對應(yīng)的哈希值以及為所述目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)生成的位圖數(shù)組；將所述哈希表向預(yù)設(shè)的計算節(jié)點發(fā)送，以便所述計算節(jié)點根據(jù)接收到的所述哈希表中的位圖數(shù)組，按照比特位執(zhí)行基數(shù)統(tǒng)計處理。

其中，所述目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)中包括：所述目標數(shù)據(jù)的多個維度值；所述利用預(yù)設(shè)的位圖算法，為所述目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)生成位圖數(shù)組，包括：查詢預(yù)先為所述數(shù)據(jù)節(jié)點對應(yīng)設(shè)置的映射關(guān)系表，確定所述維度數(shù)據(jù)中的多個維度值對應(yīng)的維度元素；其中，所述映射關(guān)系表用于記錄至少一個維度元素以及每個所述維度元素在位圖數(shù)組中映射的比特位；根據(jù)所述維度數(shù)據(jù)中的多個維度值對應(yīng)的維度元素，在所述位圖數(shù)組中所述多個維度值對應(yīng)的維度元素映射的比特位標識第一比特值，在其他比特位標識第二比特值，得到所述維度數(shù)據(jù)對應(yīng)的位圖數(shù)組。

其中，所述利用預(yù)設(shè)的哈希表，對應(yīng)存儲所述目標數(shù)據(jù)對應(yīng)的哈希值以及所述目標數(shù)據(jù)的維度數(shù)據(jù)對應(yīng)的位圖數(shù)組，包括：在Java語言環(huán)境中，利用Trove包將所述目標數(shù)據(jù)對應(yīng)的哈希值以及為所述目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)生成的位圖數(shù)組對應(yīng)存儲到所述哈希表中。

其中，在所述利用預(yù)設(shè)的哈希表，對應(yīng)存儲所述目標數(shù)據(jù)對應(yīng)的哈希值以及為所述目標數(shù)據(jù)對應(yīng)的維度數(shù)據(jù)生成的位圖數(shù)組之后，在所述將所述哈希表向預(yù)設(shè)的計算節(jié)點發(fā)送之前，還包括：在所述哈希表中，查詢是否存在相同的哈希值；如果在所述哈希表中存在相同的哈希值，則對所述相同的哈希值對應(yīng)的多個位圖數(shù)組進行聚合處理。