[發(fā)明專(zhuān)利]一種文本查找的方法和裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201410191247.6
• 申請(qǐng)日: 2014-05-07
• 公開(kāi)（公告）號(hào): CN104008136A
• 公開(kāi)（公告）日: 2014-08-27
• 發(fā)明（設(shè)計(jì)）人: 劉超;姜建國(guó);李敏;仇新梁;喻民;胡波;黃超;王菲飛;王冉晴;趙雙;劉坤穎;夏劍鋒
• 申請(qǐng)（專(zhuān)利權(quán)）人: 中國(guó)科學(xué)院信息工程研究所
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京路浩知識(shí)產(chǎn)權(quán)代理有限公司 11002
• 代理人: 李迪

1.一種文本查找的方法，其特征在于，包括：

建立有限狀態(tài)自動(dòng)機(jī)，存儲(chǔ)每個(gè)狀態(tài)的單鏈表；

存儲(chǔ)扇出系數(shù)大于指定閾值的單鏈表V_i的字符域和狀態(tài)域，其中i為單鏈表節(jié)點(diǎn)狀態(tài)域的值，i≥0且取整數(shù)，將其轉(zhuǎn)化為線性表L_i且釋放所述單鏈表V_i的存儲(chǔ)空間，對(duì)所述線性表L_i的字符域進(jìn)行排序；

計(jì)算所述有限狀態(tài)自動(dòng)機(jī)的跳轉(zhuǎn)函數(shù)、失效函數(shù)和輸出函數(shù)，其中，計(jì)算所述跳轉(zhuǎn)函數(shù)時(shí)，若當(dāng)前狀態(tài)等于所述單鏈表V_i的狀態(tài)域，對(duì)所述線性表L_i進(jìn)行二分查找；

完成文本的匹配和查找。

2.根據(jù)權(quán)利要求1所述的文本查找方法，其特征在于，所述存儲(chǔ)每個(gè)狀態(tài)的單鏈表還包括：

建立頂點(diǎn)表，記錄所述單鏈表的表頭地址，形成鄰接鏈表。

3.根據(jù)權(quán)利要求1所述的文本查找方法，其特征在于，所述計(jì)算所述有限狀態(tài)自動(dòng)機(jī)的跳轉(zhuǎn)函數(shù)還包括：

若當(dāng)前狀態(tài)不在所述單鏈表V_i的狀態(tài)域中時(shí)，直接搜索當(dāng)前狀態(tài)后的單鏈表。

4.根據(jù)權(quán)利要求1至3中任一項(xiàng)所述的文本查找方法，其特征在于，所述完成文本的匹配和查找包括：

根據(jù)所述文本的當(dāng)前狀態(tài)，利用所述跳轉(zhuǎn)函數(shù)、失效函數(shù)和輸出函數(shù)完成文本的匹配和查找。

5.一種文本查找裝置，其特征在于，包括順序相連的存儲(chǔ)單元、轉(zhuǎn)化單元、計(jì)算單元和查找單元，其中：

存儲(chǔ)單元，用于存儲(chǔ)有限狀態(tài)自動(dòng)機(jī)中每個(gè)狀態(tài)的單鏈表；

轉(zhuǎn)化單元，用于存儲(chǔ)有限狀態(tài)自動(dòng)機(jī)中扇出系數(shù)大于指定閾值的單鏈表V_i的字符域和狀態(tài)域，其中i為單鏈表節(jié)點(diǎn)狀態(tài)域的值，i≥0且取整數(shù)，將其轉(zhuǎn)化為線性表L_i且釋放所述單鏈表V_i的存儲(chǔ)空間，對(duì)所述線性表L_i的字符域進(jìn)行排序；

計(jì)算單元，用于計(jì)算所述有限狀態(tài)自動(dòng)機(jī)的跳轉(zhuǎn)函數(shù)、失效函數(shù)和輸出函數(shù)，其中，計(jì)算所述跳轉(zhuǎn)函數(shù)時(shí)，若當(dāng)前狀態(tài)等于所述單鏈表V_i的狀態(tài)域，對(duì)所述線性表L_i進(jìn)行二分查找；

查找單元，用于完成文本的匹配和查找。

6.根據(jù)權(quán)利要求5所述的文本查找裝置，其特征在于，所述存儲(chǔ)單元還用于：

建立頂點(diǎn)表，記錄所述單鏈表的表頭地址，形成鄰接鏈表。

7.根據(jù)權(quán)利要求5所述的文本查找裝置，其特征在于，所述計(jì)算單元還用于：

若當(dāng)前狀態(tài)不在所述單鏈表V_i的狀態(tài)域中時(shí)，直接搜索當(dāng)前狀態(tài)后的單鏈表。

8.根據(jù)權(quán)利要求5至7中任一項(xiàng)所述的文本查找裝置，其特征在于，所述查找單元還用于：

根據(jù)所述文本的當(dāng)前狀態(tài)，利用所述跳轉(zhuǎn)函數(shù)、失效函數(shù)和輸出函數(shù)完成文本的匹配和查找。