[發明專利]一種基于有限狀態自動機的字符串匹配方法及裝置

有效

• 申請號: 200910167292.7
• 申請日: 2009-09-02
• 公開（公告）號: CN101639861A
• 公開（公告）日: 2010-02-03
• 發明（設計）人: 黃凱明
• 申請（專利權）人: 福建星網銳捷網絡有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達信恒知識產權代理有限公司
• 代理人: 郭潤湘

技術領域

本發明涉及檢索技術領域，尤指一種基于有限狀態自動機(DeterministicFinite?State?Automaton，DFA)的字符串匹配方法及裝置。?

背景技術

Aho-Corasick算法于1975年由貝爾實驗室的Aho和Corasick在《EfficientString?Matching：An?Aid?to?Bibliographic?Search》中提出，其核心是一個涵蓋所有查詢關鍵字的有限狀態自動機(Deterministic?Finite?State?Automaton，DFA)。待搜索的數據庫中的每個字符逐個輸入到DFA中，當某個查詢關鍵字命中，DFA輸出報告。?

通過Aho-Corasick算法得到DFA的過程中，需要構造三個函數：GOTO，FAILURE和OUTPUT。構造這三個函數的流程包括：?

1.1構造GOTO函數。?

該過程需要輸入的是：要查詢的關鍵字集合。例如：輸入的關鍵字集合是K＝{y1，y2，…，yk}。?

輸出的是：GOTO函數和部分完成的OUTPUT函數。?

1.2構造FAILURE函數?

該過程需要輸入的是：上述過程1.1中得到的GOTO函數及部分完成的OUTPUT函數。?

輸出的是：FAILURE函數和完成的OUTPUT函數。?

1.3構造OUTPUT函數。?

該過程將GOTO函數和FAILURE函數進一步合并，得到DFA。?

所以該過程輸入的是：上述過程1.1中得到的GOTO函數及過程1.2中得?到的FAILURE函數。?

輸出的是：構造完成的DFA。?

DFA中包含了在當前狀態、輸入字符后所對應的各種可能的下一狀態。以及各個狀態和命中的關鍵字的對應關系。當命中某一關鍵字時，能夠及時的輸出命中結果。?

應用DFA進行字符匹配時，待搜索數據庫中的每個字符在DFA中能夠觸發一次且僅能夠觸發一次狀態轉換。所以，Aho-Corasick的算法應用的優勢在于其算法復雜度僅與待搜索數據庫的長度有關，而與查詢關鍵字的長度及數目都無關。因此，在字符串匹配的各種已有算法中，Aho-Corasick是迄今為止最快的算法。?

在實際應用過程中，DFA通常以一維數組的形式存放在系統主內存中。雖然系統在運行過程中，CPU會把在最近幾個時間段內經常訪問的內容存入高速緩存(Cache)；高速緩存即高速緩沖存儲器，位于CPU和主存儲器DRAM(主內存)之間的存儲容量較小但速度很高的存儲器。但由于高速緩存容量有限，DFA與系統中其他頻繁訪問CPU的數據之間存在競爭關系，不能保證訪問頻度高的部分(或全部)DFA總能駐留在一級數據緩存中，當不在緩存中時則必須到內存中去獲取。?

所以當使用DFA搜索數據庫或者過濾網絡數據流時，最壞情況下，可能會出現每輸入一個字節，則必須訪問一次主內存，才能得到下一個狀態。而訪問主內存來獲取下一個狀態會造成很大的時延，導致字符匹配過程的時延很長，嚴重影響了匹配的速度和效率。因此，頻繁的主內存訪問已經成為基于DFA搜索的系統整體性能的瓶頸。?

發明內容

本發明實施例提供一種基于有限狀態自動機的字符串匹配方法及裝置，解決現有技術中存在的字符匹配速度慢、時延長的問題。?

一種用于內容過濾設備的基于有限狀態自動機的字符串匹配方法，包括：?

確定用戶輸入的關鍵字在設定的關鍵字組中時，調用所述關鍵字組對應的有限狀態自動機DFA程序代碼；所述程序代碼為根據采用Aho-Corasick算法針對所述關鍵字組確定的當前狀態、輸入字符和輸出狀態的對應關系預先生成的；?

執行所述程序代碼，依次輸入待搜索數據庫中包含的字符，并根據當前狀態和輸入字符，確定輸出狀態；所述輸出狀態即為下次輸入字符時的當前狀態；?

根據所述輸出狀態輸出字符匹配結果。?

本發明的上述方法，還包括：根據程序代碼的允許大小，選取所述DFA中包含的與初始狀態具有衍生關系的部分狀態，所選取的部分狀態的出現頻率之和大于設定的閾值；?

生成僅包含已選取的部分狀態作為當前狀態時，輸入字符后所對應的輸出狀態的程序代碼。?

根據本發明的上述方法，所述程序代碼僅包含已選取的部分狀態作為當前狀態，輸入字符后所對應的輸出狀態時；其余未被選取的狀態作為當前狀態時，輸入字符后所對應的輸出狀態仍從系統主內存中獲取。?