[發明專利]一種文本查找的方法和裝置

在審

• 申請號: 201410191247.6
• 申請日: 2014-05-07
• 公開（公告）號: CN104008136A
• 公開（公告）日: 2014-08-27
• 發明（設計）人: 劉超;姜建國;李敏;仇新梁;喻民;胡波;黃超;王菲飛;王冉晴;趙雙;劉坤穎;夏劍鋒
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 李迪

技術領域

本發明涉及計算機技術領域，尤其涉及一種文本查找的方法和裝置。

背景技術

對于文件檢查，主要是對文本中出現的關鍵字段進行快速匹配查找并定位相應文件。通常計算機里存儲有數以萬計各類型的文本文件，為了快速準確地查找關鍵字段需要應用一些模式匹配算法。對于入侵檢測系統，模式匹配算法通常應用于誤用檢測，著名的開放源碼的入侵檢測系統Snort就是基于模式匹配。模式匹配算法的性能直接影響入侵檢測系統的檢測效率。在高速網絡環境下,如果模式匹配算法來不及處理大量的實時網絡數據包,必然會丟棄部分數據包,而這些被丟棄的數據包中就可能包含入侵信息。常用的模式匹配算法有BF算法、KMP算法、BM算法、BMH算法、AC算法等。由于AC算法的簡單高效，所以它的應用范圍比較廣。

AC算法是一種經典的多模式匹配算法。對于給定的長度為n的文本，和模式集合P{p1,p2,...pm}，在O(n)時間復雜度內，找到文本中的所有目標模式，而與模式集合的規模m無關，即能快速有效的在指定文本中查找匹配特定的關鍵字符或字段。AC算法使用的數據結構是Trie樹，是一種用于快速查找的多叉樹結構。其核心思想是以空間換時間，利用字符串的公共前綴來減少查詢時間以提高效率，主要采用完全Hash表方式來存儲跳轉狀態。但是，如果當系統中存在大量字段且這些字段也都沒有公共前綴的話，那么相應的Trie樹就會非常耗費內存。這在中文文本查找來說尤為明顯，對于英文目標字符串的字符數最大是256，但對于中文文本來說，匹配的目標字符串最大數目到達256*256，隨著目標字符串增大，Trie樹結構也隨之增大，存儲空間急劇膨脹，巨大的存儲空間會使得AC算法的時效性大大降低。

發明內容

(一)要解決的技術問題

本發明提供一種文本查找的方法和裝置，以解決現有技術中AC算法的存儲空間過大，時效性較低的技術問題。

(二)技術方案

為解決上述技術問題，本發明提供一種文本查找的方法，包括：

建立有限狀態自動機，存儲每個狀態的單鏈表；

存儲扇出系數大于指定閾值的單鏈表V_i的字符域和狀態域，其中i為單鏈表節點狀態域的值，i≥0且取整數，將其轉化為線性表L_i且釋放所述單鏈表V_i的存儲空間，對所述線性表L_i的字符域進行排序；

計算所述有限狀態自動機的跳轉函數、失效函數和輸出函數，其中，計算所述跳轉函數時，若當前狀態等于所述單鏈表V_i的狀態域，對所述線性表L_i進行二分查找；

完成文本的匹配和查找。

進一步地，所述存儲每個狀態的單鏈表還包括：

建立頂點表，記錄所述單鏈表的表頭地址，形成鄰接鏈表。

進一步地，所述計算所述有限狀態自動機的跳轉函數還包括：

若當前狀態不在所述單鏈表V_i的狀態域中時，直接搜索當前狀態后的單鏈表。

進一步地，所述完成文本的匹配和查找包括：

根據所述文本的當前狀態，利用所述跳轉函數、失效函數和輸出函數完成文本的匹配和查找。

另一方面，本發明還提供一種文本查找裝置，包括順序相連的存儲單元、轉化單元、計算單元和查找單元，其中：

存儲單元，用于存儲有限狀態自動機中每個狀態的單鏈表；

轉化單元，用于存儲有限狀態自動機中扇出系數大于指定閾值的單鏈表V_i的字符域和狀態域，其中i為單鏈表節點狀態域的值，i≥0且取整數，將其轉化為線性表L_i且釋放所述單鏈表V_i的存儲空間，對所述線性表L_i的字符域進行排序；

計算單元，用于計算所述有限狀態自動機的跳轉函數、失效函數和輸出函數，其中，計算所述跳轉函數時，若當前狀態等于所述單鏈表V_i的狀態域，對所述線性表L_i進行二分查找；

查找單元，用于完成文本的匹配和查找。

進一步地，所述存儲單元還用于：

建立頂點表，記錄所述單鏈表的表頭地址，形成鄰接鏈表。

進一步地，所述計算單元還用于：

若當前狀態不在所述單鏈表V_i的狀態域中時，直接搜索當前狀態后的單鏈表。

進一步地，所述查找單元還用于：

根據所述文本的當前狀態，利用所述跳轉函數、失效函數和輸出函數完成文本的匹配和查找。