[發(fā)明專利]一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510515497.5
• 申請(qǐng)日: 2015-08-20
• 公開（公告）號(hào): CN105260354B
• 公開（公告）日: 2018-08-21
• 發(fā)明（設(shè)計(jì)）人: 司冰
• 申請(qǐng)（專利權(quán)）人: 及時(shí)標(biāo)訊網(wǎng)絡(luò)信息技術(shù)（北京）有限公司
• 主分類號(hào): G06F17/27
• 分類號(hào): G06F17/27
• 代理公司: 北京風(fēng)雅頌專利代理有限公司 11403
• 代理人: 李陽

1.一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，包括：

獲取所有關(guān)鍵詞，將所有所述關(guān)鍵詞編碼，并將所有所述關(guān)鍵詞按其關(guān)鍵詞編碼的字符順序排列；

建立字典樹，并將所有所述關(guān)鍵詞按字符排列順序加入所述字典樹中；

為所述字典樹中的每個(gè)非虛根節(jié)點(diǎn)加入前綴指針，若被指定的所述非虛根節(jié)點(diǎn)為虛根的子節(jié)點(diǎn)，則為被指定的所述非虛根節(jié)點(diǎn)加入一根指向虛根的前綴指針；

為所述字典樹中的每個(gè)非虛根節(jié)點(diǎn)加入失敗指針；

獲取待檢測(cè)文章，根據(jù)包括前綴指針與失敗指針的字典樹在所述待檢測(cè)文章中查詢并記錄下所有的關(guān)鍵詞。

2.根據(jù)權(quán)利要求1所述的一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，將所有所述關(guān)鍵詞編碼，為將所有所述關(guān)鍵詞按照指定的漢字編碼方式以數(shù)字組合的形式表示；將所有所述關(guān)鍵詞按其關(guān)鍵詞編碼的字符順序排列，為將所有所述關(guān)鍵詞按其編碼后每個(gè)字符所對(duì)應(yīng)數(shù)字的大小順序?qū)λ嘘P(guān)鍵詞進(jìn)行排列。

3.根據(jù)權(quán)利要求2所述的一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，所述數(shù)字組合為十六進(jìn)制數(shù)字的數(shù)字組合；所述指定的漢字編碼方式為以下之一：GB2312、GBK、BIG5、UTF-8。

4.根據(jù)權(quán)利要求2所述的一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，所述建立字典樹為指定一虛根，并根據(jù)所述虛根建立字典樹。

5.根據(jù)權(quán)利要求4所述的一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，將所有所述關(guān)鍵詞按字符排列順序加入所述字典樹中包括：

根據(jù)字符排列順序依次指定每個(gè)關(guān)鍵詞；

為被指定的關(guān)鍵詞建立一個(gè)樹枝，并為被指定的關(guān)鍵詞編碼的每一位在樹枝上建立一個(gè)節(jié)點(diǎn)，每一位都是其前一位的子節(jié)點(diǎn)，每一位都是其后一位的父節(jié)點(diǎn)，父子節(jié)點(diǎn)在樹枝上相鄰；

從虛根開始，將所述被指定的關(guān)鍵詞的樹枝與現(xiàn)有所述字典樹上字符相同的節(jié)點(diǎn)合并，直到出現(xiàn)不同的節(jié)點(diǎn)為止；

依次指定每個(gè)關(guān)鍵詞直到所有所述關(guān)鍵詞均加入所述字典樹中。

6.根據(jù)權(quán)利要求5所述的一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，為被指定的關(guān)鍵詞編碼的每一位在樹枝上建立一個(gè)節(jié)點(diǎn)時(shí)，按照編碼從首位到末位的順序建立節(jié)點(diǎn)，先建立父節(jié)點(diǎn)后建立子節(jié)點(diǎn)，且為每個(gè)節(jié)點(diǎn)賦予編號(hào)，其中，所述每個(gè)非虛根節(jié)點(diǎn)的編號(hào)為關(guān)鍵詞加入字典樹的過程中該節(jié)點(diǎn)被創(chuàng)建的順序數(shù)字，所述虛根編號(hào)為零。

7.根據(jù)權(quán)利要求6所述的一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，為所述字典樹中的每個(gè)非虛根節(jié)點(diǎn)加入失敗指針包括：

根據(jù)節(jié)點(diǎn)編號(hào)順序依次指定所述每個(gè)非虛根節(jié)點(diǎn)；

分別對(duì)于每一個(gè)被指定的節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)編號(hào)的數(shù)字進(jìn)位制依次指定可能出現(xiàn)的每個(gè)數(shù)字；

檢查被指定的所述非虛根節(jié)點(diǎn)是否為一個(gè)具有指定子節(jié)點(diǎn)的父節(jié)點(diǎn)，其中，非虛根父節(jié)點(diǎn)到該子節(jié)點(diǎn)的樹枝方向數(shù)字與被指定的數(shù)字相同，若否，則給被指定的所述非虛根節(jié)點(diǎn)建立一個(gè)收到被指定的數(shù)字后的失敗指針；

分別對(duì)于每一個(gè)被指定的節(jié)點(diǎn)，依次指定每個(gè)數(shù)字直到進(jìn)位制中的所有數(shù)字均被指定過；

依次指定所述每個(gè)非虛根節(jié)點(diǎn)直到所有所述非虛根節(jié)點(diǎn)均具有失敗指針。

8.根據(jù)權(quán)利要求7所述的一種基于關(guān)鍵詞字典樹構(gòu)造的中文AC自動(dòng)機(jī)工作方法，其特征在于，給被指定的所述非虛根節(jié)點(diǎn)建立一個(gè)收到被指定的數(shù)字后的失敗指針，所述非虛根節(jié)點(diǎn)在收到所述被指定的數(shù)字后會(huì)按照所述失敗指針的指向方向確定后續(xù)狀態(tài)。