[發(fā)明專利]字符串搜索方法、裝置、計算機設(shè)備及介質(zhì)

有效

• 申請?zhí)枺?/td>: 202010568627.2
• 申請日: 2020-06-19
• 公開（公告）號: CN111581461B
• 公開（公告）日: 2023-04-25
• 發(fā)明（設(shè)計）人: 成賢斌
• 申請（專利權(quán)）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F40/289
• 代理公司: 北京三高永信知識產(chǎn)權(quán)代理有限責任公司 11138
• 代理人: 張所明

1.一種字符串搜索方法，其特征在于，所述方法包括：

獲取輸入的模式字符串；

獲取主字符串以及容錯閾值，所述主字符串的長度大于所述模式字符串的長度；

將所述模式字符串和所述主字符串中的等長子串進行逐字符的匹配；

響應(yīng)于所述模式字符串和所述等長子串存在不匹配字符、所述模式字符串中的不匹配字符不是首字符且已刪除字符數(shù)未達到所述容錯閾值，對所述主字符串中的不匹配字符進行刪除，確定長度與所述模式字符串的剩余字符長度相同的下一個等長子串，從所述不匹配字符開始對所述模式字符串的剩余字符和所述等長子串進行繼續(xù)匹配；

響應(yīng)于所述模式字符串中的字符在所述主字符串中均存在匹配字符，將所述主字符串輸出為所述模式字符串的搜索結(jié)果。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

響應(yīng)于所述模式字符串和所述等長子串存在不匹配字符、所述模式字符串中的不匹配字符不是首字符且已刪除字符數(shù)達到所述容錯閾值，確定本輪匹配過程中的已匹配字符的最長公共前后綴；

將所述模式字符串中的剩余字符向后移動指定長度，所述指定長度等于所述已匹配字符的長度減去所述最長公共前后綴的長度，或者，所述指定長度等于一；

響應(yīng)于所述主字符串中存在長度與所述模式字符串中的剩余字符長度相同的下一個等長子串，從所述不匹配字符開始對所述模式字符串的剩余字符和所述等長子串進行繼續(xù)匹配。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

響應(yīng)于所述模式字符串和所述等長子串存在不匹配字符、且所述模式字符串中的不匹配字符是首字符；

將所述模式字符串向后移動一位；

響應(yīng)于所述主字符串中存在長度與所述模式字符串對應(yīng)的下一個等長子串，再次執(zhí)行所述將所述模式字符串和所述等長子串進行逐字符的匹配的步驟。

4.根據(jù)權(quán)利要求1至3任一所述的方法，其特征在于，所述方法還包括：

將所述不匹配字符在所述主字符串中進行刪除后，將所述已刪除字符數(shù)加一，所述已刪除字符數(shù)的初始值為零。

5.根據(jù)權(quán)利要求1至3任一所述的方法，其特征在于，所述方法還包括：

對所述模式字符串和所述主字符串按照相同的分詞方式進行分詞；

將所述模式字符串和所述主字符串分詞得到的各個詞語分別映射為單個字符；

其中，不同的詞語對應(yīng)不同的字符，相同的詞語對應(yīng)相同的字符。

6.根據(jù)權(quán)利要求5所述的方法，其特征在于，所述主字符串屬于候選字符串庫；所述對所述模式字符串和所述主字符串按照相同的分詞方式進行分詞，包括：

對所述模式字符串采用目標詞典進行分詞，得到所述模式字符串的每個分詞；對所述主字符串采用所述目標詞典進行分詞，得到所述主字符串的每個分詞；

其中，所述目標詞典是根據(jù)所述候選字符串庫中的詞語構(gòu)建的分詞詞典。

7.根據(jù)權(quán)利要求1至3任一所述的方法，其特征在于，所述主字符串屬于候選字符串庫；所述方法還包括：

計算所述候選字符串庫中各個字符串的平均長度；

根據(jù)所述平均長度設(shè)置所述容錯閾值。

8.根據(jù)權(quán)利要求1至3任一所述的方法，其特征在于，所述方法還包括：

根據(jù)輸入的參數(shù)值，設(shè)置所述容錯閾值。