[發(fā)明專利]一種基于字典樹(shù)剪枝搜索的協(xié)議關(guān)鍵字識(shí)別方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201611051833.6
• 申請(qǐng)日: 2016-11-23
• 公開(kāi)（公告）號(hào): CN106713273B
• 公開(kāi)（公告）日: 2019-08-09
• 發(fā)明（設(shè)計(jì)）人: 衣龍騰;齊維孔;周鈉;李明;劉曉暉
• 申請(qǐng)（專利權(quán)）人: 中國(guó)空間技術(shù)研究院
• 主分類號(hào): H04L29/06
• 分類號(hào): H04L29/06;G06F16/22
• 代理公司: 中國(guó)航天科技專利中心 11009
• 代理人: 陳鵬

1.一種基于字典樹(shù)剪枝搜索的協(xié)議關(guān)鍵字識(shí)別方法，其特征在于包括如下步驟：

(1)獲取需要進(jìn)行協(xié)議關(guān)鍵字識(shí)別的數(shù)據(jù)流，建立長(zhǎng)度為24的循環(huán)隊(duì)列buffer，將迭代器index定位在數(shù)據(jù)流第1位，建立變量DataCount記錄掃描過(guò)的數(shù)據(jù)流長(zhǎng)度，建立變量NodeNum記錄字典樹(shù)中節(jié)點(diǎn)數(shù)量，建立字典樹(shù)root， 其中，DataCount的初值為0，NodeNum的初值為0；

(2)將以index為起點(diǎn)的數(shù)據(jù)流中的24位數(shù)據(jù)存入循環(huán)隊(duì)列buffer，將buffer中存放的數(shù)據(jù)字符串記為A(a₁a₂...a₂₄)，從a₁開(kāi)始掃描字符串，將當(dāng)前掃描的字符記為a_i，若字典樹(shù)root中某個(gè)節(jié)點(diǎn)存放的字符與a_i相同，則將當(dāng)前節(jié)點(diǎn)的計(jì)數(shù)值count加1，并將該字符賦值給當(dāng)前節(jié)點(diǎn)，然后繼續(xù)掃描字符串A(a₁a₂...a₂₄)，若字典樹(shù)root中任何節(jié)點(diǎn)對(duì)應(yīng)的字符都與a_i不同，i＝1，2，3…24，則將a_ia_i+1…a₂₄中的字符分別作為24-i+1個(gè)節(jié)點(diǎn)，并連接在字符為a_i-1的節(jié)點(diǎn)上，包括字符a_j的節(jié)點(diǎn)的深度depth為j、計(jì)數(shù)值count為1，NodeNum＝NodeNum+(24-i+1)，j＝i，i+1，…24，其中，存儲(chǔ)字符為a₀的節(jié)點(diǎn)為根節(jié)點(diǎn)；

(3)index＝index+1，DataCount＝DataCount+1；

(4)判斷變量NodeNum、DataCount，如果NodeNum>MaxNodeNum或者DataCount％CycleTime＝0，則轉(zhuǎn)入步驟(5)，否則轉(zhuǎn)入步驟(2)，直至DataCount+24等于數(shù)據(jù)流長(zhǎng)度，轉(zhuǎn)入步驟(7)；其中，符號(hào)％代表求模運(yùn)算；

(5)計(jì)算得到深度為depth的節(jié)點(diǎn)的剪枝閾值MinCountList[depth]＝DataCount/(2^depth)*10；

(6)從字典樹(shù)的根節(jié)點(diǎn)開(kāi)始遍歷字典樹(shù)，將當(dāng)前遍歷到的節(jié)點(diǎn)temp的深度記為depth_t、計(jì)數(shù)值記為count_t，如果count_t小于MinCountList[depth_t]，則將temp節(jié)點(diǎn)、temp節(jié)點(diǎn)的所有子節(jié)點(diǎn)從字典樹(shù)中刪除，否則繼續(xù)遍歷字典樹(shù)直至遍歷完畢，并轉(zhuǎn)入步驟(2)；

(7)用字符串列表StrList記錄協(xié)議關(guān)鍵字，獲取精煉比例PurifyRate，從根節(jié)點(diǎn)開(kāi)始遍歷字典樹(shù)，將當(dāng)前遍歷到節(jié)點(diǎn)記為temp，節(jié)點(diǎn)temp的深度記為depth_t、計(jì)數(shù)值記為count_t，節(jié)點(diǎn)temp的直接父節(jié)點(diǎn)記為parent，節(jié)點(diǎn)parent深度記為depth_p、計(jì)數(shù)值記為count_p，若count_t/count_p<PurifyRate，則將根節(jié)點(diǎn)到節(jié)點(diǎn)parent的分支上的所有節(jié)點(diǎn)記錄的字符組成字符串，加入到StrList中，完成關(guān)鍵字識(shí)別。

2.根據(jù)權(quán)利要求1所述的一種基于字典樹(shù)剪枝搜索的協(xié)議關(guān)鍵字識(shí)別方法，其特征在于：所述的CycleTime為數(shù)據(jù)流長(zhǎng)度的二十分之一到十分之一。

3.根據(jù)權(quán)利要求1或2所述的一種基于字典樹(shù)剪枝搜索的協(xié)議關(guān)鍵字識(shí)別方法，其特征在于：所述的MaxNodeNum的取值為1000000。

4.根據(jù)權(quán)利要求1或2所述的一種基于字典樹(shù)剪枝搜索的協(xié)議關(guān)鍵字識(shí)別方法，其特征在于：所述的精煉比例PurifyRate取值為一個(gè)大于0小于1的實(shí)數(shù)。