[發(fā)明專利]一種基于有限狀態(tài)自動(dòng)機(jī)的字符串匹配方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200910167292.7
• 申請(qǐng)日: 2009-09-02
• 公開（公告）號(hào): CN101639861A
• 公開（公告）日: 2010-02-03
• 發(fā)明（設(shè)計(jì)）人: 黃凱明
• 申請(qǐng)（專利權(quán)）人: 福建星網(wǎng)銳捷網(wǎng)絡(luò)有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京同達(dá)信恒知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 郭潤(rùn)湘

1.一種用于內(nèi)容過濾設(shè)備的基于有限狀態(tài)自動(dòng)機(jī)的字符串匹配方法，其 特征在于，包括：

確定用戶輸入的關(guān)鍵字在設(shè)定的關(guān)鍵字組中時(shí)，調(diào)用所述關(guān)鍵字組對(duì)應(yīng)的 有限狀態(tài)自動(dòng)機(jī)DFA程序代碼，所述DFA程序代碼為根據(jù)程序代碼的允許大 小，選取所述DFA中包含的與初始狀態(tài)具有衍生關(guān)系的部分狀態(tài)，生成的僅 包含已選取的部分狀態(tài)作為當(dāng)前狀態(tài)時(shí)，輸入字符后所對(duì)應(yīng)的輸出狀態(tài)的程序 代碼，其中所選取的部分狀態(tài)的出現(xiàn)頻率之和大于設(shè)定的閾值；

執(zhí)行所述程序代碼，依次輸入待搜索數(shù)據(jù)庫(kù)中包含的字符，并根據(jù)當(dāng)前狀 態(tài)和輸入字符，確定輸出狀態(tài)；所述輸出狀態(tài)即為下次輸入字符時(shí)的當(dāng)前狀態(tài)；

根據(jù)所述輸出狀態(tài)輸出字符匹配結(jié)果。

2.如權(quán)利要求1所述的方法，其特征在于，所述程序代碼僅包含已選取 的部分狀態(tài)作為當(dāng)前狀態(tài)，輸入字符后所對(duì)應(yīng)的輸出狀態(tài)時(shí)；其余未被選取的 狀態(tài)作為當(dāng)前狀態(tài)時(shí)，輸入字符后所對(duì)應(yīng)的輸出狀態(tài)仍從系統(tǒng)主內(nèi)存中獲取。

3.如權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述輸出狀態(tài)輸出 字符匹配結(jié)果，具體包括：

根據(jù)采用Aho-Corasick算法得到的各輸出狀態(tài)所對(duì)應(yīng)的字符匹配結(jié)果的 對(duì)應(yīng)關(guān)系，查詢所述輸出狀態(tài)所對(duì)應(yīng)的字符匹配結(jié)果；

當(dāng)確定所述字符匹配結(jié)果為某個(gè)關(guān)鍵字命中時(shí)，輸出字符匹配結(jié)果；否則 無輸出。

4.如權(quán)利要求1-3任一所述的方法，其特征在于，所述設(shè)定的關(guān)鍵字組 根據(jù)設(shè)定時(shí)間段內(nèi)的關(guān)鍵字使用情況的統(tǒng)計(jì)結(jié)果定期更新；

相應(yīng)的，根據(jù)更新后的關(guān)鍵字組，生成對(duì)應(yīng)的DFA程序代碼。

5.一種用于內(nèi)容過濾設(shè)備的基于有限狀態(tài)自動(dòng)機(jī)的字符串匹配裝置，其 特征在于，包括：

生成模塊，用于根據(jù)程序代碼的允許大小，選取有限狀態(tài)自動(dòng)機(jī)DFA中 包含的與初始狀態(tài)具有衍生關(guān)系的部分狀態(tài)，生成僅包含已選取的部分狀態(tài)作 為當(dāng)前狀態(tài)時(shí)，輸入字符后所對(duì)應(yīng)的輸出狀態(tài)的程序代碼，其中所選取的部分 狀態(tài)的出現(xiàn)頻率之和大于設(shè)定的閾值；

調(diào)用模塊，用于確定用戶輸入的關(guān)鍵字在所述關(guān)鍵字組中，調(diào)用所述生成 模塊生成的與所述關(guān)鍵字組對(duì)應(yīng)的DFA程序代碼；

執(zhí)行模塊，用于執(zhí)行所述程序代碼，依次輸入待搜索數(shù)據(jù)庫(kù)中包含的字符，并根據(jù) 當(dāng)前狀態(tài)和輸入字符，確定輸出狀態(tài)；所述輸出狀態(tài)即為下次輸入字符時(shí)的當(dāng)前狀態(tài)；

輸出模塊，用于根據(jù)所述輸出狀態(tài)輸出字符匹配結(jié)果。

6.如權(quán)利要求5所述的裝置，其特征在于，所述執(zhí)行模塊，還用于：

當(dāng)所述生成模塊所生成的程序代碼中僅包含已選取的部分狀態(tài)作為當(dāng)前 狀態(tài)，輸入字符后所對(duì)應(yīng)的輸出狀態(tài)時(shí)，從系統(tǒng)主內(nèi)存中獲取未被選取的狀態(tài) 作為當(dāng)前狀態(tài)時(shí)，輸入字符后所對(duì)應(yīng)的輸出狀態(tài)。

7.如權(quán)利要求5所述的裝置，其特征在于，所述輸出模塊，具體包括：

查詢單元，用于根據(jù)采用Aho-Corasick算法得到的各輸出狀態(tài)所對(duì)應(yīng)的字 符匹配結(jié)果的對(duì)應(yīng)關(guān)系，查詢所述輸出狀態(tài)所對(duì)應(yīng)的字符匹配結(jié)果；

輸出單元，用于當(dāng)確定所述字符匹配結(jié)果為某個(gè)關(guān)鍵字命中時(shí)，輸出字符 匹配結(jié)果；否則無輸出。

8.如權(quán)利要求5-7任一所述的裝置，其特征在于，還包括：

更新模塊，用于根據(jù)設(shè)定時(shí)間段內(nèi)的關(guān)鍵字使用情況的統(tǒng)計(jì)結(jié)果定期更新 所述設(shè)定的關(guān)鍵字組；

相應(yīng)的，所述生成模塊，還用于根據(jù)更新后的關(guān)鍵字組，生成對(duì)應(yīng)的DFA 程序代碼。

9.一種內(nèi)容過濾設(shè)備，其特征在于，在該內(nèi)容過濾設(shè)備中設(shè)置如權(quán)利要 求5-8任一所述的基于有限狀態(tài)自動(dòng)機(jī)的字符串匹配裝置。