[發(fā)明專利]一種分段模式匹配方法及其裝置

無效

• 申請?zhí)枺?/td>: 200610159310.3
• 申請日: 2006-09-27
• 公開（公告）號: CN101154228A
• 公開（公告）日: 2008-04-02
• 發(fā)明（設計）人: 張若淵;闕開良
• 申請（專利權）人: 西門子公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市柳沈律師事務所
• 代理人: 張亮

技術領域

本發(fā)明涉及計算機領域，特別涉及字符串模式匹配領域，具體來講是一種分段模式匹配方法及其裝置。

背景技術

現(xiàn)在，通過互聯(lián)網(wǎng)，每一個人都能非常容易地發(fā)布自己的信息，這同時也意味著在互聯(lián)網(wǎng)上充斥著海量的信息，而且這些信息是各種各樣的。在這些信息當中，有許多有價值的信息，但是同時，更多的是一些垃圾信息，比如垃圾郵件等等。

在實際生活中，人們通常只是想閱讀自己感興趣的東西，而不想去閱讀自己不感興趣的東西。不幸的是，互聯(lián)網(wǎng)本身并沒有提供這種機制，所以，互聯(lián)網(wǎng)的用戶直接面臨著在網(wǎng)上無限制傳播的大量信息，會很容易地被信息流所淹沒。面對這海量的信息，過濾是幫助人們獲得有價值信息的有用工具，通過過濾，互聯(lián)網(wǎng)的用戶只需要花很少的時間就能獲得自己感興趣的信息；網(wǎng)絡設備可以過濾掉有害信息，或者識別出特別的重要信息。模式匹配的算法解決了這個問題，在模式匹配中找到匹配集中最合適的關鍵字是十分重要的。多模式的匹配即是有K個模式P[1]...P[K]和一個文本T，尋找K個模式中的任何一個模式在T中是否出現(xiàn)以及出現(xiàn)的位置，1975年由A.V.Aho和M.J.Corasick公開了一種有限子動機的多模式匹配算法(AC算法)，能夠有效的對文本進行匹配和過濾，以使文獻檢索變得更加迅速。

圖1為現(xiàn)有AC算法的模式匹配集和示意圖。圖中虛線方框內的就是匹配的模式。規(guī)定模式的集合為：

P1：^*/movie/^*

P2：^*/music/^*

P3：^*/root/public/^*

P4：^*/movie/comedy/^*

其中通配符“*”在兩端的意思為，以這些模式為關鍵字，可能出現(xiàn)在一個字符串或者文本的任意部分。對于AC算法來說，它的處理方法是基于一個關鍵字樹，這個關鍵字樹由匹配集合中的所有關鍵字構成，每個節(jié)點分支的判斷條件都是一個字符。當對一字符串進行分析時，該字符串逐字符穿過關鍵字樹直到整個字符串都被分析完成為止。由一個狀態(tài)機對關鍵字樹進行匹配操作，關鍵字樹的每一個節(jié)點都為有限狀態(tài)機的一個可能狀態(tài)。其中，節(jié)點為靜態(tài)的，是可能的狀態(tài)的描述，而狀態(tài)是狀態(tài)機在某一特定時刻的描述。

中國專利200410023142，一種基于特征值的多模式匹配算法及硬件實現(xiàn)專利，公開了一種對信息進行兩次匹配的方法，先濾除一些不重要的信息，對感興趣的信息進行第二次濾除，但是該方法需的存儲器容量也很大，并且該方法的匹配速度不夠理想。

發(fā)明內容

為了解決以上問題，本發(fā)明提供一種分段模式匹配方法，將格式化的字符串進行分段并進行模式匹配，以達到更快速的效果。

為了解決以上問題，本發(fā)明提供一種分段模式匹配裝置，將字符串分段，并進行模式匹配以達到對硬件要求低的效果。

一種分段模式匹配方法，包括，

步驟1，根據(jù)模式字符串中的特殊符號或者根據(jù)語言結構將模式字符串劃分成至少一個關鍵字字符串片段，由編譯器利用現(xiàn)有匹配算法規(guī)則將所述關鍵字字符串片段生成關鍵字樹，所述關鍵字樹的每個節(jié)點都包含至少一個關鍵字字符串片段，該節(jié)點的分支條件是另一個關鍵字字符串片段；

步驟2，根據(jù)模式字符串中的特殊符號或者根據(jù)語言結構將用戶輸入的待處理字符串劃分成至少一個待處理字符串片段，作為狀態(tài)機的輸入；

步驟3，由所述狀態(tài)機根據(jù)所述現(xiàn)有匹配算法將所述待處理字符串片段在所述關鍵字樹節(jié)點中進行匹配操作；

步驟4，如果在匹配的所述關鍵字樹節(jié)點的數(shù)據(jù)結構中具有模式匹配成功的標志，則記錄或者輸出該匹配的模式ID；

步驟5，如果所有所述待處理的字符串片段處理完畢，則結束，否則在所述狀態(tài)機中處理下一個所述待處理字符串片段，重復步驟3-5。

所述步驟3中，使用哈希算法或者二分法將待處理字符串片段與節(jié)點分支條件進行字符串之間的匹配。

還包括一排序步驟，

在步驟1中，將待處理字符串分段后，由一排序單元將所述關鍵字字符串片段按照預定的順序排序，并輸入所述編譯器，由所述編譯器生成關鍵字樹；

在步驟2中，將待處理字符串分割成至少一個待處理字符串片段后，由所述排序單元將所述待處理字符串片段按照所述預定順序輸入所述狀態(tài)機，以進行步驟3至步驟5。

還包括一合并步驟：