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

無效

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

1.一種分段模式匹配方法，其特征在于，

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

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

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

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

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

2.根據(jù)權(quán)利要求1所述的一種分段模式匹配方法，其特征在于所述步驟3中，使用哈希算法或者二分法將待處理字符串片段與節(jié)點(diǎn)分支條件進(jìn)行字符串之間的匹配。

3.根據(jù)權(quán)利要求1所述的一種分段模式匹配方法，其特征在于還包括一排序步驟，

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

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

4.根據(jù)權(quán)利要求1所述的一種分段模式匹配方法，其特征在于還包括一合并步驟：

在步驟1中，將模式字符串分段后，按照下述合并規(guī)則由一合并單元將所述關(guān)鍵字字符串片段合并成新的關(guān)鍵字字符串片段：將所述關(guān)鍵字樹同一支路中相鄰的只具有一個分支的節(jié)點(diǎn)合并；或者將上述合并的節(jié)點(diǎn)與其最后一個節(jié)點(diǎn)相鄰的，并且具有至少兩個分支的節(jié)點(diǎn)合并；合并后輸入所述編譯器，由編譯器重新生成關(guān)鍵字樹；

在步驟2中，將待處理字符串分段后，按照上述合并規(guī)則，由所述合并單元將所述待處理字符串片段合并成由至少一個待處理字符串片段組成的新的待處理字符串片段，作為所述狀態(tài)機(jī)的輸入。

5.根據(jù)權(quán)利要求3所述的一種分段模式匹配方法，其特征在于還包括一合并步驟：

在步驟1中，將所述關(guān)鍵字字符串片段排序后，按照下述合并規(guī)則由一合并單元將所述關(guān)鍵字字符串片段合并成新的關(guān)鍵字字符串片段：將所述關(guān)鍵字樹同一支路中相鄰的只具有一個分支的節(jié)點(diǎn)合并；或者將上述合并的節(jié)點(diǎn)與其最后一個節(jié)點(diǎn)相鄰的，并且具有至少兩個分支的節(jié)點(diǎn)合并；合并后輸入所述編譯器，由編譯器重新生成關(guān)鍵字樹；

在步驟2中，將所述待處理字符串片段排序后，按照上述合并規(guī)則由所述合并單元將所述待處理字符串片段合并成由至少一個待處理字符串片段組成的新的待處理字符串片段，作為所述狀態(tài)機(jī)的輸入。

6.根據(jù)權(quán)利要求3所述的一種分段模式匹配方法，其特征在于所述預(yù)定順序包括，按照所述關(guān)鍵字字符串片段和所述待處理字符串片段讀入的先后順序，或者片段的語法結(jié)構(gòu)進(jìn)行排序，排序后所述鍵字字符串片段和所述待處理字符串片段的順序相同。

7.一種分段模式匹配裝置，其特征在于包括，

分段器，用于根據(jù)模式字符串中的特殊符號或者根據(jù)語言結(jié)構(gòu)將模式字字符串和待處理字符串分段；

編譯器，與狀態(tài)機(jī)相連接，用于將所述關(guān)鍵字字符串片段生成關(guān)鍵字樹；

所述狀態(tài)機(jī)，接收所述分段器傳送的待處理字符串片段，利用現(xiàn)有匹配算法將所述待處理字符串片段在所述關(guān)鍵字樹節(jié)點(diǎn)中進(jìn)行匹配操作；

輸出單元與所述狀態(tài)機(jī)相連接，用于輸出與所述待處理字符串的匹配模式編號。

8.根據(jù)權(quán)利要求7所述的一種分段模式匹配裝置，其特征在于還包括一排序單元，用于將由所述分段器輸出的至少2個待處理字符串片段和所述關(guān)鍵字字符串片段按照預(yù)定順序分別進(jìn)行排序，將排序后的所述待處理字符串片段輸入所述狀態(tài)機(jī)，將排序后的所述關(guān)鍵字字符串片段輸入所述編譯器。

9.根據(jù)權(quán)利要求7所述的一種分段模式匹配裝置，其特征在于還包括一合并單元，用于合并所述待處理字符串片段并傳送給所述狀態(tài)機(jī)，合并所述關(guān)鍵字字符串片段并傳送給所述編譯器。

10.根據(jù)權(quán)利要求7所述的一種分段模式匹配裝置，其特征在于還包括一合并單元，用于合并所述經(jīng)過排序單元的待處理字符串片段，并傳送給所述狀態(tài)機(jī)，合并所述經(jīng)過排序單元的關(guān)鍵字字符串片段，并傳送給所述編譯器。