[發(fā)明專利]一種統(tǒng)計TopK-Frequency信息的方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201811441696.6
• 申請日: 2018-11-29
• 公開（公告）號: CN111241146B
• 公開（公告）日: 2023-09-19
• 發(fā)明（設(shè)計）人: 劉一雄;汪海;叢磊
• 申請（專利權(quán)）人: 北京數(shù)安鑫云信息技術(shù)有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/22;G06F16/2455
• 代理公司: 北京名華博信知識產(chǎn)權(quán)代理有限公司 11453
• 代理人: 苗源;白瑩

1.一種統(tǒng)計TopK-Frequency信息的方法，其特征在于，所述方法包括：

獲取一元素及對應(yīng)的出現(xiàn)次數(shù)；

判斷所述元素是否存在于用于存儲元素及出現(xiàn)次數(shù)的數(shù)據(jù)結(jié)構(gòu)中，若存在，則用獲取的出現(xiàn)次數(shù)更新所述數(shù)據(jù)結(jié)構(gòu)中已記錄的所述元素的出現(xiàn)次數(shù)；若不存在，則將獲取的所述元素及所述出現(xiàn)次數(shù)存儲至所述數(shù)據(jù)結(jié)構(gòu)中，所述數(shù)據(jù)結(jié)構(gòu)為一個限制最大容量的哈希表，所述最大容量為內(nèi)存使用量；

從所述數(shù)據(jù)結(jié)構(gòu)中選擇出現(xiàn)次數(shù)最高的k個元素，k為大于等于1的正整數(shù)；

其中，將獲取的所述元素及所述出現(xiàn)次數(shù)存儲至所述數(shù)據(jù)結(jié)構(gòu)中包括：

判斷所述數(shù)據(jù)結(jié)構(gòu)中已存儲的元素個數(shù)是否達(dá)到可存儲元素的最大容量，若未達(dá)到，則將獲取的所述元素及所述出現(xiàn)次數(shù)存儲至所述數(shù)據(jù)結(jié)構(gòu)中；若已達(dá)到，則確定所述數(shù)據(jù)結(jié)構(gòu)中最低出現(xiàn)次數(shù)及對應(yīng)的元素，從所述數(shù)據(jù)結(jié)構(gòu)中刪除所述最低出現(xiàn)次數(shù)及對應(yīng)的元素后，將獲取的所述元素及所述出現(xiàn)次數(shù)存儲至所述數(shù)據(jù)結(jié)構(gòu)中；

所述數(shù)據(jù)結(jié)構(gòu)包括n個數(shù)據(jù)集合，出現(xiàn)次數(shù)相同的元素被存儲至相同的數(shù)據(jù)集合中，并且所述n個數(shù)據(jù)集合按照出現(xiàn)次數(shù)的順序進(jìn)行排序，其中n是大于等于1的正整數(shù)；

若獲取的所述元素存在于所述數(shù)據(jù)結(jié)構(gòu)中則用獲取的出現(xiàn)次數(shù)更新所述數(shù)據(jù)結(jié)構(gòu)中已記錄的出現(xiàn)次數(shù)包括：

在存儲的元素出現(xiàn)次數(shù)比所述數(shù)據(jù)結(jié)構(gòu)已存儲的所述元素出現(xiàn)次數(shù)大的數(shù)據(jù)集合中，判斷是否存在存儲的出現(xiàn)次數(shù)相同于獲取的所述出現(xiàn)次數(shù)的數(shù)據(jù)集合，若存在，則將所述元素及所述出現(xiàn)次數(shù)存儲至存儲的出現(xiàn)次數(shù)相同于獲取的所述出現(xiàn)次數(shù)的數(shù)據(jù)集合的尾部，并將所述元素從當(dāng)前數(shù)據(jù)集合中刪除；若不存在，則在所述數(shù)據(jù)結(jié)構(gòu)中創(chuàng)建新的數(shù)據(jù)集合，將所述元素及所述出現(xiàn)次數(shù)存儲至該新數(shù)據(jù)集合中，并將所述元素從當(dāng)前數(shù)據(jù)集合中刪除，更新所述數(shù)據(jù)結(jié)構(gòu)中所有數(shù)據(jù)集合的順序，以使得所有數(shù)據(jù)集合按照其中存儲的元素的出現(xiàn)次數(shù)順序排序。

2.如權(quán)利要求1所述的方法，其特征在于，若獲取的所述元素不存在于所述數(shù)據(jù)結(jié)構(gòu)中，將獲取的所述元素及所述出現(xiàn)次數(shù)存儲至所述數(shù)據(jù)結(jié)構(gòu)中還包括：

在所述數(shù)據(jù)結(jié)構(gòu)的所述數(shù)據(jù)集合中，判斷是否存在存儲的出現(xiàn)次數(shù)相同于獲取的所述出現(xiàn)次數(shù)的數(shù)據(jù)集合，若存在，則將所述元素及所述出現(xiàn)次數(shù)存儲至存儲的出現(xiàn)次數(shù)相同于獲取的所述出現(xiàn)次數(shù)的數(shù)據(jù)集合的尾部；若不存在，則在所述數(shù)據(jù)結(jié)構(gòu)中創(chuàng)建新的數(shù)據(jù)集合，將所述元素及所述出現(xiàn)次數(shù)存儲至該新數(shù)據(jù)集合中，并更新所述數(shù)據(jù)結(jié)構(gòu)中所有數(shù)據(jù)集合的順序，以使得所有數(shù)據(jù)集合按照其中存儲的元素的出現(xiàn)次數(shù)順序排序。

3.如權(quán)利要求1所述的方法，其特征在于，確定所述數(shù)據(jù)結(jié)構(gòu)中最低出現(xiàn)次數(shù)及對應(yīng)的元素包括：

將位于所述數(shù)據(jù)結(jié)構(gòu)中存儲最低出現(xiàn)次數(shù)的數(shù)據(jù)集合的尾部的元素確定為最低出現(xiàn)次數(shù)對應(yīng)的元素。

4.如權(quán)利要求1所述的方法，其特征在于，從所述數(shù)據(jù)結(jié)構(gòu)中選擇出現(xiàn)次數(shù)最高的k個元素包括：

按照所述n個數(shù)據(jù)集合存儲元素的出現(xiàn)次數(shù)由大到小的順序，從所述n個數(shù)據(jù)集合中選擇前k個元素。