[發(fā)明專(zhuān)利]一種快速進(jìn)行多字符串匹配的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201911068908.5
• 申請(qǐng)日: 2019-11-04
• 公開(kāi)（公告）號(hào): CN110825925B
• 公開(kāi)（公告）日: 2023-05-26
• 發(fā)明（設(shè)計(jì)）人: 沈華偉
• 申請(qǐng)（專(zhuān)利權(quán)）人: 沈華偉
• 主分類(lèi)號(hào): G06F16/903
• 分類(lèi)號(hào): G06F16/903
• 代理公司: 上海思牛達(dá)專(zhuān)利代理事務(wù)所(特殊普通合伙) 31355
• 代理人: 雍常明

1.一種快速進(jìn)行多字符串匹配的方法，其特征在于，包括以下步驟：

S1、當(dāng)程序在獲取到關(guān)鍵詞表之后自動(dòng)產(chǎn)生并構(gòu)造一張字符定位表，所述字符定位表的每一行是所述關(guān)鍵詞表里各個(gè)關(guān)鍵詞內(nèi)所有可能出現(xiàn)的字符，以字典順序(A～Z,a～z,0～9)保存，第N列是該字符在要進(jìn)行匹配的關(guān)鍵詞中出現(xiàn)在第N位的關(guān)鍵詞的編號(hào)集合；

S2、程序自左向右逐個(gè)掃描輸入字符，并執(zhí)行運(yùn)算過(guò)程；

所述運(yùn)算過(guò)程包括以下步驟：

(1)、定義候選集合s＝()；定義臨時(shí)候選集temp_s＝()；定義單詞內(nèi)位置指示器idx＝0；定義輸入字符串中，各個(gè)單詞之間的分隔符為空白符(ASCII?0x20)；

(2)、從輸入流中讀取一個(gè)字符，針對(duì)該字符，執(zhí)行以下運(yùn)算，若：

該字符為分隔符，執(zhí)行運(yùn)算步驟(3)；

該字符為非分隔符，執(zhí)行運(yùn)算步驟(4)；

該字符為輸入串末尾(0x00)，完成運(yùn)算，退出匹配程序；

(3)、針對(duì)候選集s的情況，分別進(jìn)行以下運(yùn)算，若：

候選集s為空集合，匹配失敗，將臨時(shí)候選集temp_s重置為空集合，單詞內(nèi)位置指示器idx重置為0，連續(xù)讀取輸入字符直到讀取到分隔符，執(zhí)行運(yùn)算步驟(2)；

候選集s為非空集合，查找s中保存的關(guān)鍵詞編號(hào)所對(duì)應(yīng)的關(guān)鍵詞中，是否存在一個(gè)關(guān)鍵詞w，其長(zhǎng)度與當(dāng)前的單詞內(nèi)位置指示器idx的值相等；若存在，則匹配成功，匹配到關(guān)鍵詞w，將臨時(shí)候選集temp_s重置為空集合，單詞內(nèi)位置指示器idx重置為0，執(zhí)行運(yùn)算步驟(2)；若s中保存的關(guān)鍵詞編號(hào)所對(duì)應(yīng)的關(guān)鍵詞中，不存在長(zhǎng)度與當(dāng)前的單詞內(nèi)位置指示器idx的值相等的關(guān)鍵詞，則匹配失敗；連續(xù)讀取輸入字符直到讀取到分隔符，將候選集s與臨時(shí)候選集temp_s全部重置為空集合，單詞內(nèi)位置指示器idx重置為0，執(zhí)行運(yùn)算步驟(2)；

(4)、由于字符定位表在構(gòu)造時(shí)以字典順序(A～Z,a～z,0～9)保存，故可以常數(shù)時(shí)間復(fù)雜度O(1)查找到當(dāng)前讀取到的字符在字符定位表中的行，以及當(dāng)前讀取到的字符在當(dāng)前單詞中的位置idx所對(duì)應(yīng)的列，由此得到字符定位表中對(duì)應(yīng)的單元格中，該字符出現(xiàn)在idx位置的關(guān)鍵詞集合d；針對(duì)集合d執(zhí)行以下運(yùn)算，若：

集合d為空集合，執(zhí)行運(yùn)算步驟(3)；

集合d為非空集合，將集合d與候選集s取交集，賦予臨時(shí)候選集temp_s，temp_s＝d∩s，執(zhí)行運(yùn)算步驟(5)；

(5)、針對(duì)臨時(shí)候選集temp_s，若:

臨時(shí)候選集temp_s為空集合，執(zhí)行運(yùn)算步驟(3)；

臨時(shí)候選集temp_s為非空集合，將臨時(shí)候選集temp_s賦予候選集s，形成新的候選集s,s＝temp_s，單詞內(nèi)位置指示器idx的值加1，idx＝idx+1，執(zhí)行運(yùn)算步驟(2)。

2.根據(jù)權(quán)利要求1所述的一種快速進(jìn)行多字符串匹配的方法，其特征在于：針對(duì)上述運(yùn)算步驟(3)，根據(jù)匹配策略進(jìn)行調(diào)整，若算法要求的匹配策略為貪心匹配，則如上文所述，在候選集s中找到長(zhǎng)度與當(dāng)前idx值相等的關(guān)鍵字，即為匹配的關(guān)鍵字；若算法要求的匹配策略為非貪心匹配，則必須在當(dāng)前讀取輸入流的字符為分隔符時(shí)，從s中查找與當(dāng)前idx值相等的關(guān)鍵字，找到即為匹配成功，未找到即為匹配失敗，繼續(xù)上述運(yùn)算步驟(2)。

3.根據(jù)權(quán)利要求1所述的一種快速進(jìn)行多字符串匹配的方法，其特征在于：本方法的輸入之一是一張關(guān)鍵詞表，關(guān)鍵詞表的每一行有且僅有一個(gè)關(guān)鍵詞，關(guān)鍵詞表的每一行被單獨(dú)賦予一個(gè)從0開(kāi)始的編號(hào)，關(guān)鍵詞表中的每一行同時(shí)記錄關(guān)鍵詞的長(zhǎng)度。