[發明專利]有限狀態自動機生成方法、關鍵字匹配方法及裝置和設備

無效

• 申請號: 201010289023.0
• 申請日: 2010-09-20
• 公開（公告）號: CN101944121A
• 公開（公告）日: 2011-01-12
• 發明（設計）人: 黃凱明
• 申請（專利權）人: 北京星網銳捷網絡技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 郭潤湘

1.一種有限狀態自動機的生成方法，其特征在于，包括：

針對待生成的有限狀態自動機DFA的每個狀態，在為該狀態分配的內存空間中為該狀態生成第一狀態對應表，所述第一狀態對應表用于記錄向所述待生成的DFA輸入ASCII字符表的每個字符時，所述待生成的DFA的下一狀態的值為0或者為非0；

針對所述待生成的DFA的每個狀態，在為該狀態分配的內存空間中為該狀態生成第二狀態對應表，所述第二狀態對應表用于記錄所述第一狀態對應表記錄的下一狀態的值為非0時該下一狀態的值；

將所有狀態的第一狀態對應表和第二狀態對應表作為所述待生成的DFA。

2.如權利要求1所述的方法，其特征在于，所述生成第一對應表，包括：

針對所述待生成的DFA的每個狀態，將為該狀態分配的存儲空間起始的N個比特分別記錄為第一標識位或第二標識位；其中，第n+1個比特記錄的第一標識位用于指示在該狀態下，向所述待生成的DFA輸入ASCII字符表中十進制為n的字符時所述待生成的DFA的下一個狀態的值為0；第n+1個比特位記錄的第二標識位用于指示在該狀態下，向所述待生成的DFA輸入ASCII字符表中十進制為n的字符時所述待生成的DFA的下一個狀態的值為非0；所述n的取值范圍為[0，N-1]，所述N等于ASCII字符表的字符總數；

將所述N個比特位的記錄作為第一對應表。

3.如權利要求1或2所述的方法，其特征在于，生成第二狀態對應表，包括：

針對所述待生成的DFA的每個狀態，按照每個下一狀態的值為非0的記錄在第一狀態對應表中的先后順序，將為該狀態分配的存儲空間起始的N個比特之后的M個字節分別記錄為與所述每個下一狀態為非0的記錄對應的下一狀態的值；所述M等于第一狀態對應表中所有下一狀態為非0的記錄的總數；

將所述M個字節的記錄作為第二狀態對應表。

4.一種使用有限狀態自動機進行關鍵字匹配的方法，其特征在于，包括：

在當前狀態下，接收輸入的待查詢的關鍵字中的一個字符；

在當前狀態的第一狀態對應表中查詢與該字符對應的有限狀態自動機DFA下一狀態的記錄；

若查詢到的記錄為下一狀態的值為0，則跳轉至狀態0，等待接收所述待查詢的關鍵字中的下一個字符；

若查詢到的記錄為下一狀態的值為非0，在當前狀態的第二狀態對應表中查詢該字符對應的下一個狀態的值，根據查詢的結果跳轉至相應的下一狀態，等待接收所述待查詢的關鍵字中的下一個字符；

輸出所述待查詢的關鍵字的匹配結果。

5.如權利要求4所述的方法，其特征在于，在當前狀態的第一狀態對應表中查詢該字符對應的下一狀態的記錄，包括：

確定該字符在ASCII字符表中對應的十進制的字符n；所述n的取值范圍為[0，N-1]，所述N為ASCII字符表的字符總數；

從所述第一狀態對應表中，獲取第n+1個比特位記錄的第一標識位或第二標識位；所述第一標識位用于指示向所述DFA輸入ASCII字符表中十進制為n的字符時所述DFA的下一個狀態的值為0；所述第二標識位用于指示向所述DFA輸入ASCII字符表中十進制為n的字符時所述DFA的下一個狀態的值為非0。

6.如權利要求4或5所述的方法，其特征在于，所述在當前狀態的第二狀態對應表中查詢該字符對應的下一個狀態的值，包括：

確定該字符對應的DFA的下一個狀態的記錄在所述第一狀態對應表中所有DFA下一狀態的值為非0的記錄中的位序；

在所述第二狀態對應表中，獲取相同位序的字節記錄的該字符對應的DFA的下一個狀態的值。

7.一種有限狀態自動機的生成裝置，其特征在于，包括：

第一狀態對應表生成單元，用于針對待生成的有限狀態自動機DFA的每個狀態，在為該狀態分配的內存空間中為該狀態生成第一狀態對應表，所述第一狀態對應表用于記錄向所述待生成的DFA輸入ASCII字符表的每個字符時，所述DFA的下一狀態的值為0或者為非0；

第二狀態對應表生成單元，用于針對所述待生成的DFA的每個狀態，在為該狀態分配的內存空間中為該狀態生成第二狀態對應表，所述第二狀態對應表用于記錄所述第一狀態對應表記錄的下一狀態的值為非0時該下一狀態的值；

DFA生成單元，用于將所有狀態的第一狀態對應表和第二狀態對應表作為所述待生成的DFA。