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

有效

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

本申請(qǐng)公開(kāi)了一種字符串搜索方法、裝置、設(shè)備及介質(zhì)，涉及虛擬環(huán)境領(lǐng)域。該方法包括：獲取輸入的模式字符串；將所述模式字符串和所述主字符串進(jìn)行逐字符的匹配；響應(yīng)于所述模式字符串和所述主字符串存在不匹配字符、所述模式字符串中的不匹配字符不是首字符且已刪除字符數(shù)未達(dá)到所述容錯(cuò)閾值，將所述主字符串中的不匹配字符進(jìn)行刪除后，對(duì)所述模式字符串中的不匹配字符和所述主字符串中的剩余字符進(jìn)行繼續(xù)匹配；響應(yīng)于所述模式字符串中的字符在所述主字符串均存在匹配字符，將所述主字符串輸出為所述模式字符串的搜索結(jié)果。本申請(qǐng)可以實(shí)現(xiàn)模糊匹配。

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

本申請(qǐng)實(shí)施例涉及視覺(jué)編譯領(lǐng)域，特別涉及一種字符串搜索方法、裝置、計(jì)算機(jī)設(shè)備及介質(zhì)。

背景技術(shù)

字符串搜索是在各種搜索工具中較為常用的技術(shù)。

以俱樂(lè)部名字搜索為例，用戶輸入關(guān)鍵字“蒼狼”，計(jì)算機(jī)設(shè)備采用BF(BruteForce，暴力破解)算法在已有的字符串庫(kù)中，查詢出含有“蒼狼”的俱樂(lè)部名字“蒼狼俱樂(lè)部”。BF算法是對(duì)“蒼狼”和“蒼狼俱樂(lè)部”進(jìn)行逐個(gè)字符的比較來(lái)搜索的。

當(dāng)俱樂(lè)部名字的字符較多且用戶只記得其中一部分離散的詞語(yǔ)時(shí)，上述算法無(wú)法準(zhǔn)確搜索出俱樂(lè)部名詞。比如俱樂(lè)部名字為“黑暗之約蒼狼銀月俱樂(lè)部”時(shí)，用戶輸入“黑暗蒼狼”或“黑暗銀月”時(shí)，無(wú)法搜索出該俱樂(lè)部名字。

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

本申請(qǐng)實(shí)施例提供了一種字符串搜索方法、裝置、設(shè)備及介質(zhì)，可以實(shí)現(xiàn)模糊匹配。所述技術(shù)方案如下：

根據(jù)本申請(qǐng)的一個(gè)方面，提供了一種字符串搜索方法，所述方法包括：

獲取輸入的模式字符串；

獲取主字符串以及容錯(cuò)閾值，所述主字符串的長(zhǎng)度大于所述模式字符串的長(zhǎng)度；

將所述模式字符串和所述主字符串中的等長(zhǎng)子串進(jìn)行逐字符的匹配；

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

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

根據(jù)本申請(qǐng)的另一方面，提供了一種字符串搜索裝置，所述裝置包括：

輸入模塊，用于獲取輸入的模式字符串；

獲取模塊，用于獲取主字符串以及容錯(cuò)閾值，所述主字符串的長(zhǎng)度大于所述模式字符串的長(zhǎng)度；

匹配模塊，用于將所述模式字符串和所述主字符串中的等長(zhǎng)子串進(jìn)行逐字符的匹配；

容錯(cuò)模塊，用于響應(yīng)于所述模式字符串和所述等長(zhǎng)子串存在不匹配字符、所述模式字符串中的不匹配字符不是首字符且已刪除字符數(shù)未達(dá)到所述容錯(cuò)閾值，對(duì)所述主字符串中的不匹配字符進(jìn)行刪除，確定長(zhǎng)度與所述模式字符串的剩余字符相同的下一個(gè)等長(zhǎng)子串，從所述不匹配字符開(kāi)始對(duì)所述模式字符串的剩余字符和所述等長(zhǎng)子串進(jìn)行繼續(xù)匹配；

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