[發(fā)明專利]一種基于流量高頻內(nèi)容的模式匹配算法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 202110291361.6
• 申請(qǐng)日: 2021-03-18
• 公開（公告）號(hào): CN113065419B
• 公開（公告）日: 2022-05-24
• 發(fā)明（設(shè)計(jì)）人: 余翔湛;劉立坤;韋賢葵;史建燾;葉麟;葛蒙蒙;李精衛(wèi);石開宇;車佳臻;王久金;馮帥;趙躍;宋赟祖
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)
• 主分類號(hào): G06V30/41
• 分類號(hào): G06V30/41;G06V30/418;G06V30/146;G06V30/19;G06V10/75;G06K9/62
• 代理公司: 哈爾濱市偉晨專利代理事務(wù)所(普通合伙) 23209
• 代理人: 韓立巖

1.一種基于流量高頻內(nèi)容的模式匹配算法，其特征在于，包括以下步驟：

S1.創(chuàng)建自動(dòng)機(jī)；

S1.1.根據(jù)模式集構(gòu)建自動(dòng)機(jī)，首先創(chuàng)建根節(jié)點(diǎn)；

S1.2.按字符順序輸入模式，輸入下一個(gè)字符，如果不存在該字符的邊，則執(zhí)行步驟S1.3，否則，執(zhí)行步驟S1.4；當(dāng)所有模式的所有字符都插入到自動(dòng)機(jī)中，執(zhí)行步驟S1.5，所述字符為流量里包含的字符；

S1.3.創(chuàng)建新節(jié)點(diǎn)，設(shè)置邊值為掃描字符，返回步驟S1.2；

S1.4.自動(dòng)機(jī)狀態(tài)沿著該邊跳轉(zhuǎn)到下一個(gè)節(jié)點(diǎn)，返回步驟S1.2；

S1.5.深度遍歷自動(dòng)機(jī)，給每個(gè)節(jié)點(diǎn)添加失敗指針；

S1.6.提取高頻內(nèi)容的所有模式的首字符，去掉重復(fù)字符，形成映射集，每個(gè)字符為一個(gè)獨(dú)立節(jié)點(diǎn)；

S1.7.遍歷自動(dòng)機(jī)，找到映射集字符，當(dāng)邊值與映射集字符相同，則將當(dāng)前節(jié)點(diǎn)與映射集字符關(guān)聯(lián)；

S1.8.映射集每個(gè)字符關(guān)聯(lián)高頻內(nèi)容，形成高頻內(nèi)容集，通過計(jì)算哈希值代表高頻內(nèi)容，n個(gè)字符對(duì)應(yīng)n個(gè)高頻內(nèi)容集；

S1.9.每個(gè)高頻內(nèi)容集計(jì)算哈希值并存儲(chǔ)；

S1.10.高頻內(nèi)容與自動(dòng)機(jī)關(guān)聯(lián)，自動(dòng)機(jī)掃描高頻內(nèi)容，遍歷到最深的節(jié)點(diǎn)作為高頻內(nèi)容命中后返回自動(dòng)機(jī)的狀態(tài)節(jié)點(diǎn)；

S2.自動(dòng)機(jī)掃描；

S2.1.將流量解析后的數(shù)據(jù)輸入到自動(dòng)機(jī)中；

S2.2.掃描當(dāng)前字符，在映射集中搜索當(dāng)前字符，如果沒有找到，執(zhí)行下一步驟，否則執(zhí)行步驟S2.4；如果當(dāng)前字符是待掃描字符串的結(jié)尾字符，掃描終止；

S2.3.當(dāng)前字符掃描完成自動(dòng)機(jī)跳轉(zhuǎn)到下一個(gè)字符，執(zhí)行步驟S2.2；

S2.4.根據(jù)映射集字符選擇對(duì)應(yīng)的高頻內(nèi)容集，以哈希長(zhǎng)度為窗口計(jì)算待匹配字符串哈希值，與高頻內(nèi)容哈希值比較，如果不匹配則返回到自動(dòng)機(jī)當(dāng)前節(jié)點(diǎn)，執(zhí)行步驟S2.2，如果匹配則執(zhí)行下一步驟；

S2.5.判斷字符串是否滿足判斷條件，當(dāng)滿足判斷條件時(shí)，跳轉(zhuǎn)到保存在高頻內(nèi)容中的自動(dòng)機(jī)節(jié)點(diǎn)，執(zhí)行步驟S2.2，當(dāng)不滿足判斷條件時(shí)執(zhí)行下一步驟；假設(shè)當(dāng)前字符為映射集中的p_i,下標(biāo)表示字符在待掃描字符串中的位置，對(duì)應(yīng)的高頻內(nèi)容的窗口大小為k，自動(dòng)機(jī)繼續(xù)掃描待匹配字符串，直到掃描字節(jié)p_i+j，其在AC自動(dòng)機(jī)的深度小于或等于j時(shí)，滿足判斷條件；

S2.6.自動(dòng)機(jī)掃描下一個(gè)字符，如果已經(jīng)是高頻內(nèi)容結(jié)尾，執(zhí)行步驟S2.2，否則執(zhí)行步驟S2.5。

2.根據(jù)權(quán)利要求1所述的一種基于流量高頻內(nèi)容的模式匹配算法，其特征在于，步驟S2.4所述映射集具體是由高頻內(nèi)容集合中所有字符串的第一個(gè)字符去重后構(gòu)成的集合。

3.根據(jù)權(quán)利要求2所述的一種基于流量高頻內(nèi)容的模式匹配算法，其特征在于，步驟S2.4所述高頻內(nèi)容集生成方法為：設(shè)置高頻內(nèi)容集設(shè)置重復(fù)字符串p的閾值T；在一定時(shí)間t內(nèi)，統(tǒng)計(jì)輸入流量中重復(fù)字符串p₁,p₂,...p_k出現(xiàn)次數(shù)n₁,n₂,...n_k，當(dāng)n_j≥T,1≤j≤k時(shí)，將p_j添加到高頻內(nèi)容集中P_UHC＝P_UHC∪p_j。

4.根據(jù)權(quán)利要求1所述的一種基于流量高頻內(nèi)容的模式匹配算法，其特征在于，步驟S2.4所述以哈希長(zhǎng)度為窗口計(jì)算待匹配字符串哈希值，用多項(xiàng)式函數(shù)計(jì)算待匹配字符串的長(zhǎng)度。