[發(fā)明專利]基于TCAM的確定性有窮狀態(tài)自動機(jī)DFA的匹配方法和裝置

有效

• 申請?zhí)枺?/td>: 201210071338.7
• 申請日: 2012-03-16
• 公開（公告）號: CN103294734B
• 公開（公告）日: 2016-11-16
• 發(fā)明（設(shè)計(jì)）人: 董群峰;彭坤楊
• 申請（專利權(quán)）人: 中國科學(xué)技術(shù)大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京凱特來知識產(chǎn)權(quán)代理有限公司 11260
• 代理人: 鄭立明;黃曉軍

1.一種基于TCAM的確定性有窮狀態(tài)自動機(jī)DFA的匹配方法，其特征在于，包括：

將確定性有窮狀態(tài)自動機(jī)DFA的每個狀態(tài)用若干三態(tài)內(nèi)容尋址存儲器TCAM條目表示，每個TCAM條目由源狀態(tài)域、輸入字符域和目的狀態(tài)域三個域組成，所述源狀態(tài)域由模板ID域和私有ID域兩個子域組成，分別用于存儲源狀態(tài)的模板ID編碼和私有ID編碼，所述目的狀態(tài)域由模板ID域和私有ID域兩個子域組成，所述模板ID域用于存儲目的狀態(tài)的模板ID編碼和源狀態(tài)的模板ID編碼的異或結(jié)果，所述私有ID域用于存儲目的狀態(tài)的私有ID編碼；

以具體的所述源狀態(tài)域和輸入字符域的拼接作為搜索關(guān)鍵詞，按照所述搜索關(guān)鍵字在所述DFA的所有TCAM條目中進(jìn)行搜索，獲取搜索得到的目的狀態(tài)域，將所述目的狀態(tài)域中的模板ID域的值與所述搜索關(guān)鍵詞中的模板ID域的值進(jìn)行異或，將所述異或結(jié)果作為所述目的狀態(tài)域中的最終的模板ID域的值。

2.根據(jù)權(quán)利要求1所述的基于TCAM的確定性有窮狀態(tài)自動機(jī)DFA的匹配方法，其特征在于，所述的將確定性有窮狀態(tài)自動機(jī)DFA的每個狀態(tài)用若干三態(tài)內(nèi)容尋址存儲器TCAM條目表示，包括：

若對于某個輸入字符，狀態(tài)i和狀態(tài)j各有一條出邊經(jīng)過該輸入字符轉(zhuǎn)移到某個相同的目的狀態(tài)，則這兩條出邊是狀態(tài)i和狀態(tài)j之間的“共享邊”；若對于某個輸入字符，狀態(tài)i和狀態(tài)j各有一條出邊經(jīng)過該輸入字符轉(zhuǎn)移到不同的目的狀態(tài)，則狀態(tài)i的這條出邊是關(guān)于狀態(tài)j的“非共享邊”，且狀態(tài)j的這條出邊是關(guān)于狀態(tài)i的“非共享邊”；

每個DFA狀態(tài)均用一對狀態(tài)ID進(jìn)行編號，所述狀態(tài)ID對為模板ID和私有ID，全部的DFA狀態(tài)被劃分成多個狀態(tài)集合，每個狀態(tài)集合包含的是全部擁有相同私有ID的狀態(tài)，且該狀態(tài)集合以這個私有ID命名；如果兩個狀態(tài)分屬于兩個狀態(tài)集合，且所述兩個狀態(tài)集合共享相同的模板ID，則所述兩個狀態(tài)集合互為彼此的親屬狀態(tài)；

對于私有ID為K的狀態(tài)集合，若私有ID為J的狀態(tài)集合同時滿足下述條件，則狀態(tài)集合K的所有狀態(tài)都各自選擇它們在狀態(tài)集合J中的親屬狀態(tài)作為模板狀態(tài)：J＜K；對于集合K中的每一個狀態(tài)，其在集合J中都存在一個親屬狀態(tài)；在所有滿足上述兩個條件的候選狀態(tài)集合中，集合J與集合K的相似度最大；

每個DFA狀態(tài)最多只有一個模板狀態(tài)，對于自循環(huán)狀態(tài)不為之分配模板；

若一個DFA狀態(tài)有模板狀態(tài)時，則該DFA狀態(tài)的狀態(tài)轉(zhuǎn)移邊只需存儲該DFA狀態(tài)關(guān)于其模板狀態(tài)的非共享邊；若一個DFA狀態(tài)沒有模板狀態(tài)，則該DFA狀態(tài)需要存儲其全部的狀態(tài)轉(zhuǎn)移邊；

存在模板關(guān)系的兩個DFA狀態(tài)生成的TCAM條目之間的存儲順序如下：若狀態(tài)i以狀態(tài)j為模板，則狀態(tài)i的狀態(tài)轉(zhuǎn)移邊都必須存儲在狀態(tài)j的狀態(tài)轉(zhuǎn)移邊之前；

不存在模板關(guān)系的兩個DFA狀態(tài)生成的TCAM條目之間的存儲順序是任意的。

3.根據(jù)權(quán)利要求1所述的基于TCAM的確定性有窮狀態(tài)自動機(jī)DFA的匹配方法，其特征在于，所述的源狀態(tài)域由模板ID域和私有ID域兩個子域組成，分別用于存儲源狀態(tài)的模板ID編碼和私有ID編碼，包括：

將轉(zhuǎn)移到自身的出邊的數(shù)目超過了一定的閾值的狀態(tài)定義為自循環(huán)狀態(tài)，每個DFA狀態(tài)有且僅有唯一的(模板ID，私有ID)對；

為每個自循環(huán)狀態(tài)分配一個唯一的模板ID，為所有的自循環(huán)狀態(tài)分配一個相同的私有ID；

對于每個非自循環(huán)狀態(tài)，其模板ID的取值為與其相似度最大的自循環(huán)狀態(tài)的模板ID；其私有ID的取值按如下寬度遍歷過程迭代進(jìn)行：

維護(hù)一個狀態(tài)集合的隊(duì)列，嘗試為所有在同一個狀態(tài)集合中的狀態(tài)分配相同的私有ID，初始將由所有自循環(huán)狀態(tài)組成的狀態(tài)集合入隊(duì)，并將該狀態(tài)集合標(biāo)記為已訪問，每次取出隊(duì)首的狀態(tài)集合S直至隊(duì)列為空：依次迭代檢查S經(jīng)每一個字符所達(dá)到的目的狀態(tài)集合D：

從D中刪去所有自循環(huán)狀態(tài)；若D中存在多個狀態(tài)共享相同的模板ID，則只留下其中一個狀態(tài)，其余的狀態(tài)從D中刪去；

若存在一個已訪問過的狀態(tài)集合S’，使得則跳出本次迭代；

若存在一個已訪問過的狀態(tài)集合S’，S’中所有的狀態(tài)已被分配相同的私有ID，使得則將S’中狀態(tài)所分配的私有ID分配給D中所有狀態(tài)；否則，D中所有狀態(tài)分配一個尚未被分配過的私有ID；

將D中所有狀態(tài)從所有已訪問的狀態(tài)集合中刪除；標(biāo)記集合D為已訪問；D入隊(duì)。