[發(fā)明專利]一種基于向量的數(shù)據(jù)比對(duì)方法、終端設(shè)備及存儲(chǔ)介質(zhì)

在審

• 申請(qǐng)?zhí)枺?/td>: 202111371252.1
• 申請(qǐng)日: 2021-11-18
• 公開(kāi)（公告）號(hào): CN114281862A
• 公開(kāi)（公告）日: 2022-04-05
• 發(fā)明（設(shè)計(jì)）人: 陳秀容;李山;林肖凡;梁瑞彬;張永光;周利民
• 申請(qǐng)（專利權(quán)）人: 廈門(mén)市美亞柏科信息股份有限公司
• 主分類號(hào): G06F16/2458
• 分類號(hào): G06F16/2458;G06F16/22
• 代理公司: 廈門(mén)市精誠(chéng)新創(chuàng)知識(shí)產(chǎn)權(quán)代理有限公司 35218
• 代理人: 趙薇

本發(fā)明涉及一種基于向量的數(shù)據(jù)比對(duì)方法、終端設(shè)備及存儲(chǔ)介質(zhì)，該方法中包括：S1：接收用于比對(duì)的數(shù)據(jù)，針對(duì)接收的每個(gè)數(shù)據(jù)，通過(guò)k種哈希算法分別進(jìn)行哈希運(yùn)算，得到對(duì)應(yīng)的k個(gè)哈希向量，將k個(gè)哈希向量均通過(guò)格式歸一化處理后，以格式歸一化處理后的k個(gè)哈希向量為地址、地址中的值為特征值構(gòu)建比對(duì)數(shù)據(jù)庫(kù)；S2：當(dāng)接收到待比對(duì)數(shù)據(jù)時(shí)，通過(guò)k種哈希算法分別對(duì)待比對(duì)數(shù)據(jù)進(jìn)行哈希運(yùn)算，得到對(duì)應(yīng)的k個(gè)哈希向量；將k個(gè)哈希向量均通過(guò)格式歸一化處理后，以格式歸一化處理后的k個(gè)哈希向量為地址，從比對(duì)數(shù)據(jù)庫(kù)中查找對(duì)應(yīng)地址的值是否均為特征值，如果是，判定可能存在于比對(duì)數(shù)據(jù)庫(kù)內(nèi)。本發(fā)明能夠在不損失查找速率的情況下，減少了數(shù)據(jù)內(nèi)存占用率。

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

本發(fā)明涉及數(shù)據(jù)查找領(lǐng)域，尤其涉及一種基于向量的數(shù)據(jù)比對(duì)方法、終端設(shè)備及存儲(chǔ)介質(zhì)。

背景技術(shù)

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)和云數(shù)據(jù)產(chǎn)業(yè)以及大數(shù)據(jù)戰(zhàn)略的加速落地，高需求數(shù)據(jù)處理性能計(jì)算以及數(shù)據(jù)處理要求也呈現(xiàn)增長(zhǎng)趨勢(shì)。隨著GPU的更新?lián)Q代和FPGA芯片對(duì)數(shù)據(jù)的處理速度加快，快速查找對(duì)應(yīng)運(yùn)算結(jié)果的算法成為了一個(gè)提升速度的重點(diǎn)關(guān)注問(wèn)題。

常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)中，鏈表、樹(shù)、映射中key和value沒(méi)有關(guān)聯(lián)性，這樣，必須查找所有的key來(lái)找到對(duì)應(yīng)的value，隨著數(shù)據(jù)集元素的增加，需求的存儲(chǔ)空間也會(huì)增長(zhǎng)，最終達(dá)到存儲(chǔ)瓶頸，同時(shí)查找速度也會(huì)相應(yīng)越來(lái)越慢。如公開(kāi)號(hào)為CN107729577A的中國(guó)發(fā)明專利《一種基于多維哈希表的數(shù)據(jù)查找方法、終端設(shè)備及存儲(chǔ)介質(zhì)》中說(shuō)明了基于多維哈希表的數(shù)據(jù)查找方法，但對(duì)大批量數(shù)據(jù)情況，哈希表占用空間仍然較大，對(duì)FPGA這種既嚴(yán)格又緊缺的內(nèi)存規(guī)劃仍然不足。

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

為了解決上述問(wèn)題，本發(fā)明提出了一種基于向量的數(shù)據(jù)比對(duì)方法、終端設(shè)備及存儲(chǔ)介質(zhì)。

具體方案如下：

一種基于向量的數(shù)據(jù)比對(duì)方法，包括以下步驟：

S1：接收用于比對(duì)的數(shù)據(jù)，針對(duì)接收的每個(gè)數(shù)據(jù)，通過(guò)k種哈希算法分別進(jìn)行哈希運(yùn)算，得到對(duì)應(yīng)的k個(gè)哈希向量，將k個(gè)哈希向量均通過(guò)格式歸一化處理后，以格式歸一化處理后的k個(gè)哈希向量為地址、地址中的值為特征值構(gòu)建比對(duì)數(shù)據(jù)庫(kù)；

S2：當(dāng)接收到待比對(duì)數(shù)據(jù)時(shí)，通過(guò)k種哈希算法分別對(duì)待比對(duì)數(shù)據(jù)進(jìn)行哈希運(yùn)算，得到對(duì)應(yīng)的k個(gè)哈希向量；將k個(gè)哈希向量均通過(guò)格式歸一化處理后，以格式歸一化處理后的k個(gè)哈希向量為地址，從比對(duì)數(shù)據(jù)庫(kù)中查找對(duì)應(yīng)地址的值是否均為特征值，如果是，判定待比對(duì)數(shù)據(jù)可能存在于比對(duì)數(shù)據(jù)庫(kù)內(nèi)；否則，判定待比對(duì)數(shù)據(jù)不可能存在于比對(duì)數(shù)據(jù)庫(kù)內(nèi)。

進(jìn)一步的，哈希向量進(jìn)行格式歸一化處理的方法為：將哈希向量與格式特征碼進(jìn)行與運(yùn)算，其中格式特征碼的二進(jìn)制格式中所有位均為1。

進(jìn)一步的，格式特征碼為16位的二進(jìn)制數(shù)。

進(jìn)一步的，比對(duì)數(shù)據(jù)庫(kù)中包含2¹⁶個(gè)地址，且每個(gè)地址初始化設(shè)定為0。

進(jìn)一步的，特征值為1。

進(jìn)一步的，k的大小根據(jù)誤判率p進(jìn)行確定，當(dāng)誤判率p小于預(yù)設(shè)的閾值時(shí)，判定k的大小符合要求；

誤判率p的計(jì)算公式為：

其中，e為自然底數(shù)，n表示接收的用于比對(duì)的數(shù)據(jù)的個(gè)數(shù)，l表示格式歸一化處理后的哈希向量包括l個(gè)比特。

進(jìn)一步的，還包括：對(duì)判定可能存在于比對(duì)數(shù)據(jù)庫(kù)內(nèi)的待比對(duì)數(shù)據(jù)與接收的所有用于比對(duì)的數(shù)據(jù)進(jìn)行一一比對(duì)。

一種基于向量的數(shù)據(jù)比對(duì)終端設(shè)備，包括處理器、存儲(chǔ)器以及存儲(chǔ)在所述存儲(chǔ)器中并可在所述處理器上運(yùn)行的計(jì)算機(jī)程序，所述處理器執(zhí)行所述計(jì)算機(jī)程序時(shí)實(shí)現(xiàn)本發(fā)明實(shí)施例上述的方法的步驟。