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

有效

• 申請號: 201711425017.1
• 申請日: 2017-12-25
• 公開（公告）號: CN107992481B
• 公開（公告）日: 2021-05-04
• 發明（設計）人: 李德彥;晉耀紅;林謖
• 申請（專利權）人: 鼎富智能科技有限公司
• 主分類號: G06F40/284
• 分類號: G06F40/284;G06F40/247
• 代理公司: 北京弘權知識產權代理有限公司 11363
• 代理人: 逯長明;許偉群

1.一種基于多叉樹的正則表達式匹配方法，其特征在于，所述方法包括：

獲取正則表達式的簡化樹；所述簡化樹包含至少一條路徑和至少一層節點，每個節點中包含常量字符；

將所述簡化樹進行節點融合，生成多叉樹，所述多叉樹包含多個根節點，每個根節點對應一個子樹；

從所述多叉樹中提取每個節點的常量字符，生成關鍵詞詞典；

根據所述關鍵詞詞典，獲取目標文本的分詞結果，所述分詞結果包括目標文本的分詞序列和每個分詞的位置信息；

根據所述分詞結果，獲取所述多叉樹中與目標文本匹配的命中路徑，將所述命中路徑對應的正則表達式添加至命中集合。

2.根據權利要求1所述的方法，其特征在于，所述獲取正則表達式的簡化樹；所述簡化樹包含至少一條路徑和至少一層節點，每個節點中包含常量字符的步驟，包括：

順序提取正則表達式中的所有常量字符；

根據常量字符對應的算子字符，去除常量字符中的非必須字符，以及，確定所述簡化樹的路徑分叉點；

根據每個正則表達式去除非必須字符后剩余常量字符的順序和所述簡化樹的所述路徑分叉點，獲取每個正則表達式的所述簡化樹。

3.根據權利要求2所述的方法，其特征在于，所述將所述簡化樹進行節點融合，生成多叉樹，所述多叉樹包含多個根節點，每個根節點對應一個子樹的步驟，包括：

從所有所述簡化樹中，獲取具有相同根節點的同源簡化樹；

從所述同源簡化樹的根節點逐層向下進行節點匹配；

如果被匹配的節點相同，融合節點，并進行下一層節點匹配；

如果被匹配的節點不同，將上一層被融合的節點作為所述多叉樹的所述路徑分叉點。

4.根據權利要求1所述的方法，其特征在于，所述從所述多叉樹中提取每個節點的常量字符，生成關鍵詞詞典的步驟，包括：

從所述多叉樹的根節點開始，逐層提取每個節點的常量字符；

查找當前提取到的常量字符在所述關鍵詞詞典中是否存在；

如果當前提取到的常量字符在所述關鍵詞詞典中不存在，將當前提取到的常量字符添加至所述關鍵詞詞典中；

如果當前提取到的常量字符在所述關鍵詞詞典中存在，放棄當前提取到的常量字符。

5.根據權利要求1所述的方法，其特征在于，所述根據所述關鍵詞詞典，獲取目標文本的分詞結果，所述分詞結果包括目標文本的分詞序列和每個分詞的位置信息的步驟，包括：

對所述目標文本進行字符分割，生成每個分詞中只包含一個字符的分詞序列；

將所述分詞序列中，與所述關鍵詞詞典匹配的相鄰字符合并為一個分詞；

根據每個分詞在所述分詞序列中的位置，獲取每個分詞的所述位置信息。

6.根據權利要求1所述的方法，其特征在于，根據所述關鍵詞詞典，獲取目標文本的分詞結果，所述分詞結果包括目標文本的分詞序列和每個分詞的位置信息的步驟之后，還包括：

根據所述分詞結果中所述目標文本的分詞和每個分詞的所述位置信息，創建分詞與所述位置信息的映射表。

7.根據權利要求1所述的方法，其特征在于，所述根據所述分詞結果，獲取所述多叉樹中與目標文本匹配的命中路徑，將所述命中路徑對應的正則表達式添加至命中集合的步驟，包括：

根據所述分詞結果，從所述多叉樹的所述子樹中獲取與目標文本匹配的目標子樹；

從根節點開始，逐層查找所述目標子樹的節點是否與所述目標文本的分詞存在分詞匹配；

如果存在所述分詞匹配，根據分詞的所述位置信息分析是否繼續查找；

如果查找成功抵達葉子節點，獲取從根節點抵達葉子節點的路徑，作為所述命中路徑；

將所述命中路徑對應的正則表達式添加至所述命中集合。