[發明專利]一種字符串匹配方法及裝置

有效

• 申請號: 201611237454.6
• 申請日: 2016-12-28
• 公開（公告）號: CN108255836B
• 公開（公告）日: 2020-12-25
• 發明（設計）人: 閆繼東
• 申請（專利權）人: 普天信息技術有限公司
• 主分類號: G06F16/33
• 分類號: G06F16/33;G06F16/35;G06F16/903
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 李相雨

本發明實施例提供一種字符串匹配方法及裝置。所述方法包括：獲取待匹配字符串以及所述待匹配字符串對應的至少1個關鍵字符串，計算關鍵字符串的匹配值，待匹配字符串包括第一字符串和第二字符串；計算第一字符串和第二字符串的最大前綴匹配字符串長度；根據最大前綴匹配字符串長度，利用預設規則計算第一字符串和第二字符串的第一編輯距離；根據第一編輯距離和匹配值獲得第一字符串和第二字符串的相似度。所述裝置用于執行所述方法。本發明實施例通過計算關鍵字符串的匹配值，并利用預設規則計算第一字符串和第二字符串的第一編輯距離，最后，根據第一編輯距離和匹配值獲得相似度，提高了字符串匹配的準確度。

技術領域

本發明實施例涉及文本分類處理技術領域，尤其涉及一種字符串匹配方法及裝置。

背景技術

Jaro-Winkler算法用于計算兩個字符串之間的相似度，是目前衡量字符串匹配程度的主流算法。

是Jaro-Winkler算法的計算方法如公式(1)所示：

W_ij＝D_ij+lp(1-D_ij) (1)

其中：W_ij為待匹配的字符串S_i和S_j的編輯距離；l為待匹配的字符串S_i和S_j的共有前綴字段的長度，上限為4；p為一個恒定的縮放因子，p＝0.1，D_ij為jaro距離，數據編輯距離的一類。

D_ij的計算方法如公式(2)所示：

其中，m_ij為待匹配的字符串S_i和S_j中匹配的字符數；|S_i|為待匹配的字符串S_i的字符長度，|S_j|待匹配的字符串S_j的字符長度；T_ij為字符串中換位數目的一半，即，若在字符串的第i位出現了a,b，在第j位又出現了b,a，則表示兩者出現了換位。對于m_ij，來自兩個待匹配的字符串中兩個字符匹配的條件是字符相同，并且兩個字符在字符串中的位置差不大于d_max，d_max為匹配窗口，其計算方法如公式(3)所示：

現有的Jaro-Winkler算法重點計算兩個字符串的字符匹配和編輯距離(僅考慮換位)，算法給予了起始部分就相同的字符串更高的相似度，尤其適合計算短字符串的相似度。

但是，這種方法依然將字符串中的字符同等對待，不考慮字符串信息內容，而往往字符串中的某些關鍵字符(如數字、地名等)對字符串的性質有著決定性作用，對于所有字符串，公式中l和p不能進行精確度量。例如：若按照兩個字符串相似度大于0.8的認為來自同一工程，如“長沙市軌道交通6號線工程”和“長沙市軌道交通3號線工程”，根據現有的Jaro-Winkler算法計算出相似度為0.9583，即被識別為一個工程，是匹配的，顯然并不正確。再如：“長沙市軌道交通1號線一期工程南門口站、黃土嶺站曲線站臺防夾裝置競爭性談判項目延期公告”、“長沙市軌道交通1號線一期工程運營期監測項目延期公告”來自同一個大工程，兩者應當匹配，可是兩者相似度僅僅為0.6119。可見僅僅依靠編輯距離計算得到的相似度來衡量字符串匹配情況，對于度量長度較小、不含數字及特有名稱的字符串正確率較高，而對于含有數字、字符串間長短差距過大及帶有特有名稱的字符串誤差太大。

發明內容

針對現有技術存在的問題，本發明實施例提供一種字符串匹配方法及裝置。

一方面，本發明實施例提供一種字符串匹配方法，包括：