[發(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
• 代理人: 雍常明

本發(fā)明公開(kāi)了一種快速進(jìn)行多字符串匹配的方法，包括以下步驟，當(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)集合；本申請(qǐng)描述的方法可在隨機(jī)的字節(jié)流里發(fā)現(xiàn)關(guān)鍵詞表內(nèi)提及的所有關(guān)鍵詞，可使用經(jīng)典模式匹配算法及其變種KMP算法，其時(shí)間復(fù)雜度將為O(N2)甚至O(N3)，相較于基于自動(dòng)機(jī)的詞法分析器方法以及正則表達(dá)式方法，有著自動(dòng)機(jī)構(gòu)造簡(jiǎn)單，代碼編寫(xiě)和維護(hù)便捷，生成的程序體積小，編譯時(shí)間短，效率高等特點(diǎn)。

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

本發(fā)明屬于多字符串匹配技術(shù)領(lǐng)域，具體涉及一種快速進(jìn)行多字符串匹配的方法。

背景技術(shù)

字符串匹配是計(jì)算機(jī)科學(xué)的基本問(wèn)題，解決字符串匹配問(wèn)題的方法被廣泛引用到文本編輯、搜索引擎、高級(jí)程序設(shè)計(jì)語(yǔ)言編譯器當(dāng)中。

現(xiàn)今解決字符串匹配問(wèn)題的方法有：經(jīng)典模式匹配算法及其變種KMP算法；基于自動(dòng)機(jī)的詞法分析器算法；基于正則表達(dá)式的匹配與提取算法，使用基于自動(dòng)機(jī)的詞法分析器方法，存在自動(dòng)機(jī)構(gòu)造復(fù)雜，代碼編寫(xiě)和維護(hù)困難，生成的程序體積較大等缺點(diǎn)；使用正則表達(dá)式方法，當(dāng)關(guān)鍵詞表規(guī)模較大時(shí)，存在正則表達(dá)式編寫(xiě)困難，編譯時(shí)間長(zhǎng)，運(yùn)行效率低等缺點(diǎn)，本文描述一種不同于上述算法的方法，用以在字符流中快速匹配關(guān)鍵詞表內(nèi)所有詞匯并給出匹配結(jié)果，并提出一種快速進(jìn)行多字符串匹配的方法。

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

本發(fā)明的目的在于提供一種快速進(jìn)行多字符串匹配的方法，以解決上述背景技術(shù)中提出的問(wèn)題。

為實(shí)現(xiàn)上述目的，本發(fā)明提供如下技術(shù)方案：一種快速進(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ōu)選的，所述運(yùn)算過(guò)程包括以下步驟：

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

(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)鍵詞中，不存在這樣一個(gè)關(guān)鍵詞，其長(zhǎng)度與當(dāng)前的單詞內(nèi)位置指示器idx的值相等，則匹配失敗。連續(xù)讀取輸入字符直到讀取到分隔符，將候選集s與臨時(shí)候選集temp_s全部重置為空集合，單詞內(nèi)位置指示器idx重置為0，執(zhí)行運(yùn)算步驟(2)；