[發明專利]一種模式匹配方法、裝置和用于模式匹配的裝置

有效

• 申請號: 202010183402.5
• 申請日: 2020-03-16
• 公開（公告）號: CN111400563B
• 公開（公告）日: 2023-08-01
• 發明（設計）人: 孫浩
• 申請（專利權）人: 北京搜狗科技發展有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F40/289
• 代理公司: 北京潤澤恒知識產權代理有限公司 11319
• 代理人: 鄭傲日

1.一種模式匹配方法，其特征在于，所述方法包括：

對待匹配的模式串進行分詞，得到所述模式串對應的第一分詞集合；

對所述第一分詞集合中的各分詞進行編碼，得到編碼后的模式串；

在所述編碼后的模式串的長度大于預設的分組長度時，按照所述分組長度，對所述編碼后的模式串進行劃分，得到劃分后的各個子串；

在所述各個子串中，確定目標子串；

分配所述編碼后的模式串對應的位向量表，所述位向量表中的位用于表示相應分詞在所述模式串中是否出現；

根據所述位向量表，基于位并行算法對所述模式串與待匹配的文本串進行匹配；

所述分配所述編碼后的模式串對應的位向量表，包括：

分配所述目標子串對應的位向量表；

所述根據所述位向量表，基于位并行算法對所述模式串與待匹配的文本串進行匹配，包括：

根據所述目標子串對應的位向量表，基于位并行算法對所述目標子串與所述文本串進行匹配，得到匹配串在所述文本串中的位置；

根據所述匹配串在所述文本串中的位置，查詢所述文本串是否命中所述目標子串對應的模式串。

2.根據權利要求1所述的方法，其特征在于，所述根據所述位向量表，基于位并行算法對所述模式串與待匹配的文本串進行匹配之前，所述方法還包括：

對所述文本串進行分詞，得到所述文本串對應的第二分詞集合；

對所述第二分詞集合中的各分詞進行編碼，得到編碼后的文本串；

所述根據所述位向量表，基于位并行算法對所述模式串與待匹配的文本串進行匹配，包括：

根據所述位向量表，基于位并行算法對所述編碼后的模式串與所述編碼后的文本串進行匹配。

3.根據權利要求1所述的方法，其特征在于，所述在所述各個子串中，確定目標子串，包括：

在所述各個子串中，確定詞頻最小的子串為目標子串。

4.根據權利要求1所述的方法，其特征在于，所述根據所述匹配串在所述文本串中的位置，查詢所述文本串是否命中所述目標子串對應的模式串，包括：

若所述目標子串存在碰撞模式串，則分別計算每個碰撞模式串的詞頻；

根據所述匹配串在所述文本串中的位置，按照碰撞模式串詞頻從大到小的順序，依次查詢所述文本串是否命中所述碰撞模式串。

5.根據權利要求1所述的方法，其特征在于，若所述待匹配的模式串的個數n大于1，所述分配所述編碼后的模式串對應的位向量表，包括：

確定位向量表的分組個數m；

將n個編碼后的模式串分配到包含m個分組的位向量表中。

6.根據權利要求5所述的方法，其特征在于，所述將n個編碼后的模式串分配到包含m個分組的位向量表中，包括：

確定將第i個編碼后的模式串分配到第j個分組產生的誤判字符串集合；其中，i的取值為1～n，j的取值為1～m；

根據所述誤判字符串集合中各誤判字符串的詞頻，確定將所述第i個編碼后的模式串分配到所述第j個分組產生的第一損失增益；

將所述第i個編碼后的模式串分配到第一損失增益最小的分組，直到第n個編碼后的模式串分配完成。