[發(fā)明專利]一種基于多叉樹的正則表達式匹配方法、裝置及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201711425017.1
• 申請日: 2017-12-25
• 公開（公告）號: CN107992481B
• 公開（公告）日: 2021-05-04
• 發(fā)明（設(shè)計）人: 李德彥;晉耀紅;林謖
• 申請（專利權(quán)）人: 鼎富智能科技有限公司
• 主分類號: G06F40/284
• 分類號: G06F40/284;G06F40/247
• 代理公司: 北京弘權(quán)知識產(chǎn)權(quán)代理有限公司 11363
• 代理人: 逯長明;許偉群

本申請實施例提供了一種基于多叉樹的正則表達式匹配方法、裝置及系統(tǒng)，通過對正則表達式的簡化樹進行節(jié)點融合，生成多叉樹；然后，從多叉樹中提取每個節(jié)點的常量字符，生成關(guān)鍵詞詞典，并根據(jù)關(guān)鍵詞詞典對目標文本進行分詞；最后，根據(jù)目標文本的分詞結(jié)果，從多叉樹中匹配出命中路徑，并將命中路徑對應(yīng)的正則表達式添加至命中集合。其中，多叉樹將單獨存在正則表達式聚類到了多叉樹中的各個子樹中，實現(xiàn)了節(jié)點總量的減少和同源表達式的聚類。在匹配命中路徑時，由于每個子樹的根節(jié)點不同，根據(jù)根節(jié)點能迅速定位到待匹配的子樹，使后續(xù)的匹配過程僅會在待匹配的子樹中進行，不再需要對正則表達式進行逐條匹配，減小了匹配量，提高了匹配效率。

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

本申請涉及自然語言處理技術(shù)領(lǐng)域，尤其涉及一種基于多叉樹的正則表達式匹配方法、裝置及系統(tǒng)。

背景技術(shù)

在自然語言處理技術(shù)領(lǐng)域，正則表達式是用來描述、匹配一系列的匹配某個句法規(guī)則的字符串，常被用于文本檢索、文本匹配或文本替換。正則表達式由常量字符(也稱普通字符)和算子字符(也稱為特殊字符、元字符、模式字符等)組成；其中常量字符用于在文本檢索、文本匹配或文本替換中匹配文本，算子用于定義常量字符用于匹配文本時的運算規(guī)則。

現(xiàn)有技術(shù)中在進行文本檢索、文本匹配或文本替換的過程中，有時會涉及到大量的文本，因此，使用的正則表達式的數(shù)量也非常大。在實際應(yīng)用中，為了從大量的正則表達式中尋找能夠匹配某一特定文本表達形式的正則表達式集合，需要對大量的正則表達式進行匹配和分類。

圖1為現(xiàn)有技術(shù)的一種正則表達式匹配方法，從圖1可以看出，現(xiàn)有技術(shù)在進行正則表達式匹配時，利用能夠?qū)崿F(xiàn)正則表達式匹配的算法，將一段目標文本與所有待匹配的正則表達式逐一進行匹配，如果匹配命中，則命中的正則表達式能夠匹配該目標文本對應(yīng)的表達形式，將命中的正則表達式加入到正則表達式集合中。但是，在實際應(yīng)用中，待匹配的正則表達式的數(shù)量非常大，甚至能夠達到數(shù)十萬之多，而在正則表達式集合中，對應(yīng)某個目標文本的正則表達式的數(shù)量通常只有幾十個，因此，現(xiàn)有技術(shù)中的逐一匹配正則表達式的方法，在匹配過程中的數(shù)據(jù)匹配量巨大，匹配效率低下，無法滿足實際應(yīng)用需求。

因此，如何能夠提高正則表達式在匹配分類過程中的匹配效率，成為本領(lǐng)域技術(shù)人員亟待解決的技術(shù)問題。

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

本申請實施例提供了一種基于多叉樹的正則表達式匹配方法、裝置及系統(tǒng)，以解決現(xiàn)有技術(shù)中存在的問題。

第一方面，本申請實施例提供了一種基于多叉樹的正則表達式匹配方法，所述方法包括：獲取正則表達式的簡化樹；所述簡化樹包含至少一條路徑和至少一層節(jié)點，每個節(jié)點中包含常量字符；將所述簡化樹進行節(jié)點融合，生成多叉樹，所述多叉樹包含多個根節(jié)點，每個根節(jié)點對應(yīng)一個子樹；從所述多叉樹中提取每個節(jié)點的常量字符，生成關(guān)鍵詞詞典；根據(jù)所述關(guān)鍵詞詞典，獲取目標文本的分詞結(jié)果，所述分詞結(jié)果包括目標文本的分詞序列和每個分詞的位置信息；根據(jù)所述分詞結(jié)果，獲取所述多叉樹中與目標文本匹配的命中路徑，將所述命中路徑對應(yīng)的正則表達式添加至命中集合。

第二方面，本申請實施例提供了一種基于多叉樹的正則表達式匹配裝置，所述裝置包括：獲取模塊，用于獲取正則表達式的簡化樹；所述簡化樹包含至少一條路徑和至少一層節(jié)點，每個節(jié)點中包含常量字符；融合模塊，用于將所述簡化樹進行節(jié)點融合，生成多叉樹，所述多叉樹包含多個根節(jié)點，每個根節(jié)點對應(yīng)一個子樹；取詞模塊，用于從所述多叉樹中提取每個節(jié)點的常量字符，生成關(guān)鍵詞詞典；分詞模塊，用于根據(jù)所述關(guān)鍵詞詞典，獲取目標文本的分詞結(jié)果，所述分詞結(jié)果包括目標文本的分詞序列和每個分詞的位置信息；匹配模塊，用于根據(jù)所述分詞結(jié)果，獲取所述多叉樹中與目標文本匹配的命中路徑，將所述命中路徑對應(yīng)的正則表達式添加至命中集合。