[發(fā)明專利]基于TCAM的非確定性有限自動(dòng)機(jī)的匹配方法和裝置

有效

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

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

對(duì)非確定性有窮狀態(tài)自動(dòng)機(jī)NFA的狀態(tài)和活躍狀態(tài)子集進(jìn)行編碼，將所述NFA的每個(gè)狀態(tài)轉(zhuǎn)移邊用一個(gè)三態(tài)內(nèi)容尋址存儲(chǔ)器TCAM條目表示，每個(gè)TCAM條目由匹配域和目的域組成，所述匹配域包括：源狀態(tài)域、輸入字符域，所述目的域包括目的狀態(tài)域或者包括目的狀態(tài)域和掩碼域；

將所述NFA的源活躍狀態(tài)子集的編碼和輸入字符的編碼的拼接作為搜索關(guān)鍵詞，按照所述搜索關(guān)鍵字在所述NFA的所有TCAM條目的匹配域中進(jìn)行搜索，將獲取的目的活躍狀態(tài)子集的編碼作為輸出結(jié)果，所述源活躍狀態(tài)子集為所述NFA當(dāng)前所有同時(shí)活躍的狀態(tài)的集合，所述目的活躍狀態(tài)子集為在所述NFA中輸入所述輸入字符、進(jìn)行狀態(tài)轉(zhuǎn)換后，得到的同時(shí)活躍的狀態(tài)的集合。

2.根據(jù)權(quán)利要求1所述的基于TCAM的非確定性有窮狀態(tài)自動(dòng)機(jī)的匹配方法，其特征在于，對(duì)所述NFA的狀態(tài)和活躍狀態(tài)子集進(jìn)行編碼，包括：

將所述活躍狀態(tài)子集編碼為一個(gè)活躍向量，該活躍向量由所述活躍狀態(tài)子集中包括的每個(gè)狀態(tài)所歸屬的兼容組中的活躍碼進(jìn)行拼接得到，所述兼容組是由若干NFA狀態(tài)組成的集合，該集合中的狀態(tài)兩兩之間都不能同時(shí)活躍，每個(gè)自循環(huán)狀態(tài)單獨(dú)組成一個(gè)自循環(huán)兼容組，所述自循環(huán)狀態(tài)是NFA中轉(zhuǎn)移到自身的邊超過了一定閾值的狀態(tài)，所述活躍碼為所述兼容組為組內(nèi)每個(gè)狀態(tài)各自分配的一個(gè)唯一的非全0的編碼。

3.根據(jù)權(quán)利要求1所述的基于TCAM的非確定性有窮狀態(tài)自動(dòng)機(jī)的匹配方法，其特征在于，所述的將非確定性有窮狀態(tài)自動(dòng)機(jī)NFA的每個(gè)狀態(tài)轉(zhuǎn)移邊用一個(gè)三態(tài)內(nèi)容尋址存儲(chǔ)器TCAM條目表示，每個(gè)TCAM條目由匹配域和目的域組成，包括：

將所述TCAM條目的目的域分兩種方法表示：方法一，所述目的域僅由目的狀態(tài)域組成，所述目的狀態(tài)域存放的是目的活躍狀態(tài)子集的活躍向量；方法二，所述目的域由目的狀態(tài)域和掩碼域組成，所述掩碼域的長(zhǎng)度為自循環(huán)兼容組的數(shù)目，即為每個(gè)自循環(huán)兼容組依次分配一個(gè)比特；若所述自循環(huán)兼容組在所述掩碼域中的掩碼值為“1”，則在目的狀態(tài)域中存儲(chǔ)所述自循環(huán)兼容組在目的活躍狀態(tài)子集中的活躍碼與所述自循環(huán)兼容組在源活躍狀態(tài)子集中的活躍碼的異或結(jié)果，否則直接存儲(chǔ)所述自循環(huán)兼容組在目的活躍狀態(tài)子集中的活躍碼；

所述編碼NFA中所有的狀態(tài)轉(zhuǎn)移的方法為：

枚舉所述NFA中所有的狀態(tài)轉(zhuǎn)移，將每一個(gè)狀態(tài)轉(zhuǎn)移所對(duì)應(yīng)的源狀態(tài)域、輸入字符域和目的域存儲(chǔ)在一個(gè)TCAM條目中，所述源狀態(tài)域中存儲(chǔ)源狀態(tài)的編碼，所述輸入字符域中存儲(chǔ)輸入字符的編碼，所述目的域中的目的狀態(tài)域中存儲(chǔ)目的狀態(tài)的編碼；

或者；

獲取所述NFA中的每個(gè)輸入字符c的有效集E_c，該E_c是所有自循環(huán)狀態(tài)以及所有對(duì)所述輸入字符有轉(zhuǎn)移邊的NFA狀態(tài)的集合，針對(duì)每個(gè)輸入字符計(jì)算E_c與所述NFA中每一個(gè)活躍狀態(tài)子集S的交集，這些交集組成的集合記為I_c，即I_c＝∪_s(E_c∩S)，將I_c中的各個(gè)交集按集合大小的非遞增順序進(jìn)行排序；

依次處理排過序的所述I_c中的每一個(gè)交集E_c∩S，為每一個(gè)交集E_c∩S生成一個(gè)新的TCAM條目，在所述新的TCAM條目的輸入字符域中存儲(chǔ)輸入字符的編碼；

所述E_c∩S的活躍向量按如下方式生成，對(duì)E_c∩S中的每一個(gè)狀態(tài)s，設(shè)置s所在的兼容組的編碼為s的活躍碼，對(duì)每一個(gè)自循環(huán)狀態(tài)s′，若s′∈E_c但則設(shè)置s′所在的兼容組的編碼為“0”，其他的兼容組的編碼均設(shè)置為全“＊”，將所有兼容組的編碼組合成活躍向量，在所述新的TCAM條目的源狀態(tài)域中存儲(chǔ)所述活躍向量；

對(duì)E_c∩S中的所有狀態(tài)，計(jì)算它們經(jīng)過所述輸入字符所轉(zhuǎn)移到的目的狀態(tài)的集合記為D，在所述新的TCAM條目的目的狀態(tài)域中存儲(chǔ)所述D的活躍向量；

當(dāng)所述目的域中包含掩碼域時(shí)，則對(duì)E_c∩S中的每一個(gè)自循環(huán)狀態(tài)s′，在掩碼域中為s′分配一個(gè)比特，判斷s′是否存在一條邊經(jīng)過所述輸入字符轉(zhuǎn)移到自身，如果是，則在s′的掩碼域中設(shè)置s′所在的兼容組的編碼為1；否則，在s′的掩碼域中設(shè)置s′所在的兼容組的編碼為0；

當(dāng)所述目的域包含掩碼域時(shí)，則對(duì)E_c∩S中的每一個(gè)自循環(huán)狀態(tài)s′，若s′所在的兼容組在掩碼域中的值為1，則s′的目的狀態(tài)域中存儲(chǔ)s′在目的狀態(tài)域中的編碼與s′在源狀態(tài)域中的編碼的異或結(jié)果。