[發明專利]一種字符串匹配方法及裝置有效
| 申請號： | 201611237454.6 | 申請日： | 2016-12-28 |
| 公開（公告）號： | CN108255836B | 公開（公告）日： | 2020-12-25 |
| 發明（設計）人： | 閆繼東 | 申請（專利權）人： | 普天信息技術有限公司 |
| 主分類號： | G06F16/33 | 分類號： | G06F16/33;G06F16/35;G06F16/903 |
| 代理公司： | 北京路浩知識產權代理有限公司 11002 | 代理人： | 李相雨 |
| 地址： | 100080 北京*** | 國省代碼： | 北京;11 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 字符串 匹配 方法 裝置 | ||
1.一種字符串匹配方法，其特征在于，包括：
獲取待匹配字符串以及所述待匹配字符串對應的至少1個關鍵字符串，計算所述關鍵字符串的匹配值，所述待匹配字符串包括第一字符串和第二字符串；
計算所述第一字符串和所述第二字符串的最大前綴匹配字符串長度；
根據所述最大前綴匹配字符串長度，利用預設規則計算所述第一字符串和所述第二字符串的第一編輯距離；
根據所述第一編輯距離和所述匹配值獲得所述第一字符串和所述第二字符串的相似度；
所述利用預設規則計算所述第一字符串和所述第二字符串的編輯距離，包括：
計算所述第一字符串和所述第二字符串的匹配長度、換位數目以及所述第一字符串對應的第一字符串長度和所述第二字符串對應的第二字符串長度，并根據所述匹配長度、所述換位數目、所述第一字符串長度和所述第二字符串長度計算第二編輯距離；
計算所述最大前綴匹配字符串長度與所述第一字符串長度的第一比值，以及所述最大前綴匹配字符串長度與所述第二字符串長度的第二比值；
若所述最大前綴匹配字符串長度大于等于預設閾值，則所述前綴匹配字符串長度為預設閾值，否則所述前綴匹配字符串長度等于最大前綴匹配字符串長度；
若所述第一比值與所述第二比值之和的1/2倍小于所述前綴匹配字符串長度與恒定縮放因子的乘積，則根據所述第二編輯距離和所述前綴匹配字符串長度與所述恒定縮放因子的乘積計算所述第一編輯距離；
若所述第一比值與所述第二比值之和的1/2倍大于等于所述前綴匹配字符串長度與所述恒定縮放因子的乘積，則根據所述第二編輯距離和所述第一比值與所述第二比值之和的1/2倍計算所述第一編輯距離。
2.根據權利要求1所述的方法，其特征在于，所述計算所述關鍵字符串的匹配值，包括：
獲取所述第一字符串中所述關鍵字符串之前預設個數的第一字符以及所述第二字符串中所述關鍵字符串之前所述預設個數的第二字符；
若判斷獲知所述第一字符與所述第二字符相同，則所述第一字符串和所述第二字符串匹配；
根據所述第一字符串和所述第二字符串的匹配情況獲得所述匹配值。
3.根據權利要求1所述的方法，其特征在于，所述計算所述第一字符串和所述第二字符串的最大前綴匹配字符串長度，包括：
計算所述第一字符串對應的第一字符串長度和所述第二字符串對應的第二字符串長度，并初始化所述最大前綴匹配字符串長度；
判斷所述第一字符串中的第一個字符和所述第二字符串中的第一個字符是否相同，若相同，則所述最大前綴匹配字符串長度加1，并繼續判斷下一個字符是否相同；
依次判斷所述第一字符串和所述第二字符串對應的字符是否相同，直到所述第一字符串和所述第二字符串對應的字符不相同為止，或判斷完所述第一字符串長度和所述第二字符串長度中較小的待匹配字符串中的最后一個字符為止；
獲得所述最大前綴匹配字符串長度。
4.根據權利要求1所述的方法，其特征在于，所述利用預設規則計算所述第一字符串和所述第二字符串的編輯距離，包括：
所述第一編輯距離為：
其中，Wij為所述第一編輯距離；Dij為所述第二編輯距離；l為所述前綴匹配字符串長度；p為所述恒定縮放因子，且p＝0.1；Lij為所述最大前綴匹配字符串長度，|Si|為所述第一字符串長度，|Sj|為所述第二字符串長度。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于普天信息技術有限公司，未經普天信息技術有限公司許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201611237454.6/1.html，轉載請聲明來源鉆瓜專利網。
- 上一篇：一種產品數據生成器及生成方法、導航系統
- 下一篇：一種SQL解析器及方法
