[發(fā)明專利]一種多模匹配方法和裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201810040194.6
• 申請(qǐng)日: 2018-01-16
• 公開（公告）號(hào): CN108287887A
• 公開（公告）日: 2018-07-17
• 發(fā)明（設(shè)計(jì)）人: 王銘
• 申請(qǐng)（專利權(quán)）人: 北京奇藝世紀(jì)科技有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京潤澤恒知識(shí)產(chǎn)權(quán)代理有限公司 11319
• 代理人: 莎日娜

本發(fā)明實(shí)施例提供了一種多模匹配方法和裝置，該方法和裝置應(yīng)用于Ach?Corasick自動(dòng)機(jī)或運(yùn)行該自動(dòng)機(jī)的電子設(shè)備，具體為接收需要匹配的待匹配字符；將待匹配字符輸入到預(yù)先根據(jù)failure表生成的跳轉(zhuǎn)表中進(jìn)行匹配運(yùn)算，得到待匹配字符的匹配結(jié)果，跳轉(zhuǎn)表包括多個(gè)狀態(tài)，還包括每個(gè)狀態(tài)在每種輸入字符下的跳轉(zhuǎn)狀態(tài)。由于本申請(qǐng)?zhí)峁┑姆椒ㄖ袪顟B(tài)跳轉(zhuǎn)僅與當(dāng)前狀態(tài)和當(dāng)前輸入字符有關(guān)，當(dāng)待匹配字符給定后狀態(tài)必然是有限且確定的，因此，進(jìn)行匹配時(shí)就不需回退，從而降低了字符匹配的時(shí)間復(fù)雜度，進(jìn)而有效提高了匹配效率。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)技術(shù)領(lǐng)域，特別是涉及一種多模匹配方法和裝置。

背景技術(shù)

Aho-Corasick自動(dòng)機(jī)又稱為AC自動(dòng)機(jī)，其1975年產(chǎn)生于貝爾實(shí)驗(yàn)室。AC自動(dòng)機(jī)巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移，其有兩個(gè)特點(diǎn)，一個(gè)是掃描文本時(shí)完全不需要回溯，另一個(gè)是時(shí)間復(fù)雜度與關(guān)鍵字的數(shù)目和長度無關(guān)。現(xiàn)有的Aho-Corasick自動(dòng)機(jī)是基于trie樹進(jìn)行多模匹配的，在匹配失敗時(shí)會(huì)使用failure表進(jìn)行回退，當(dāng)trie樹上的節(jié)點(diǎn)比較多時(shí)，可能會(huì)造成一次失敗需要回退多次才能到達(dá)目標(biāo)狀態(tài)，因此會(huì)大大降低匹配速度，假設(shè)有N個(gè)模式串，平均長度為L；文章長度為M，則匹配時(shí)時(shí)間復(fù)雜度為O(M*L)。由此可以看出，目前的匹配方法的時(shí)間復(fù)雜度較高，造成匹配效率較低。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明提供了一種多模匹配方法和裝置，用于降低字符匹配的時(shí)間復(fù)雜度，從而有效提高匹配效率。

為了解決上述問題，本發(fā)明公開了一種多模匹配方法，應(yīng)用于Ach-Corasick自動(dòng)機(jī)，所述多模匹配方法包括步驟：

接收需要匹配的待匹配字符；

將所述待匹配字符輸入到預(yù)先根據(jù)failure表生成的跳轉(zhuǎn)表中進(jìn)行匹配運(yùn)算，得到所述待匹配字符的匹配結(jié)果，所述跳轉(zhuǎn)表包括多個(gè)狀態(tài)，還包括每個(gè)所述狀態(tài)在每種輸入字符下的跳轉(zhuǎn)狀態(tài)。

可選的，所述跳轉(zhuǎn)表的生產(chǎn)步驟包括：

生成goto表和failure表；

將所述failure表與所述goto表進(jìn)行合并，得到所述跳轉(zhuǎn)表。

可選的，所述將所述待匹配字符輸入到預(yù)先根據(jù)failure表生成的跳轉(zhuǎn)表中進(jìn)行匹配運(yùn)算，得到所述待匹配字符的匹配結(jié)果，包括：

將所述待匹配字符輸入所述跳轉(zhuǎn)表中進(jìn)行查找運(yùn)算，得到運(yùn)算結(jié)果；

生成output表；

所述運(yùn)算結(jié)果輸入到所述output表中進(jìn)行查找運(yùn)算，得到所述匹配結(jié)果。

相應(yīng)的，為了保證上述方法的實(shí)施，本發(fā)明還提供了一種多模匹配裝置，應(yīng)用于Ach-Corasick自動(dòng)機(jī)，所述多模匹配裝置包括：

字符接收模塊，用于接收需要匹配的待匹配字符；

匹配運(yùn)算模塊，用于將所述待匹配字符輸入到預(yù)先根據(jù)failure表生成的跳轉(zhuǎn)表中進(jìn)行匹配運(yùn)算，得到所述待匹配字符的匹配結(jié)果，所述跳轉(zhuǎn)表包括多個(gè)狀態(tài)，還包括每個(gè)所述狀態(tài)在每種輸入字符下的跳轉(zhuǎn)狀態(tài)。

可選的，還包括：

跳轉(zhuǎn)表生成模塊，用于生成所述跳轉(zhuǎn)表。

可選的，所述跳轉(zhuǎn)表生成模塊包括：

第一表生成單元，用于生成goto表和failure表；

表合并單元，用于將所述failure表與所述goto表進(jìn)行合并，得到所述跳轉(zhuǎn)表。

可選的，所述匹配運(yùn)算模塊包括：

第一查找單元，用于將所述待匹配字符輸入所述跳轉(zhuǎn)表中進(jìn)行查找運(yùn)算，得到運(yùn)算結(jié)果；