[發明專利]一種字符串距離計算方法和裝置

在審

• 申請號: 201610096589.9
• 申請日: 2016-02-22
• 公開（公告）號: CN107102998A
• 公開（公告）日: 2017-08-29
• 發明（設計）人: 范曉鋒
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06K9/62
• 代理公司: 北京博思佳知識產權代理有限公司11415
• 代理人: 靳玫

技術領域

本申請涉及網絡技術，特別涉及一種字符串距離計算方法和裝置。

背景技術

字符串距離計算，可以應用于判斷兩個字符串的相似性。例如，對于一個給定的目標字符串，需要在一個字符串集合中找到與該目標字符串相似的字符串時，就可以將目標字符串與集合中的各個字符串逐個計算距離，將距離小于預設的距離閾值的字符串，確定為與目標字符串相似的字符串。但是這種方式，當字符串集合中的字符串數量較多時，運行的時間代價也較高，比如，在一個包括上千萬條地址的數據庫中，尋找一個與給定地址相似的記錄時，要運行很長時間，無法滿足某些需要快速獲得結果的應用的需求。

發明內容

有鑒于此，本申請提供一種字符串距離計算方法和裝置，以在候選字符串集合中通過計算字符串距離尋找相似字符串時，提高計算效率。

具體地，本申請是通過如下技術方案實現的：

第一方面，提供一種字符串距離計算方法，所述方法用于由候選字符串集合中選擇與給定的目標字符串相似的候選字符串；所述方法包括：

獲取所述候選字符串和目標字符串的關聯位圖信息，所述關聯位圖信息包括如下兩項中的至少一項：分別對應候選字符串和目標字符串的兩個字符串位圖的位圖權重，或者，所述兩個字符串位圖的位圖差的位圖權重；

根據所述關聯位圖信息，篩除掉所述候選字符串集合中與目標字符串的 字符串距離在距離閾值范圍之外的候選字符串，并分別計算剩余的候選字符串與所述目標字符串的字符串距離；

所述字符串位圖包括多個標識位，所述標識位的取值包括第一取值和第二取值，所述第一取值表示該標識位對應的預設標準字符包含在字符串中，所述第二取值表示所述標識位對應的預設標準字符未包含在字符串中；所述字符串位圖的位圖權重表示所述字符串位圖中的第一取值的數量；所述位圖差是將兩個字符串位圖中對應位置的標識位的取值分別進行異或運算得到，所述位圖差的位圖權重表示所述位圖差中異或取值為真的標識位的數量。

第二方面，提供一種字符串距離計算方法，所述方法用于由候選字符串集合中選擇與給定的目標字符串相似的候選字符串；所述方法包括：

獲取所述候選字符串和目標字符串中所包含字符的字符差異信息；

若所述字符差異信息大于差異閾值，則將所述候選字符串由候選字符串集合中篩除，并計算所述候選字符串集合中剩余的候選字符串與所述目標字符串的字符串距離。

第三方面，提供一種字符串距離計算裝置，所述裝置用于由候選字符串集合中選擇與給定的目標字符串相似的候選字符串；所述裝置包括：

信息獲取模塊，用于獲取所述候選字符串和目標字符串的關聯位圖信息，所述關聯位圖信息包括如下兩項中的至少一項：分別對應候選字符串和目標字符串的兩個字符串位圖的位圖權重，或者，所述兩個字符串位圖的位圖差的位圖權重；所述字符串位圖包括多個標識位，所述標識位的取值包括第一取值和第二取值，所述第一取值表示該標識位對應的預設標準字符包含在字符串中，所述第二取值表示標識位對應的預設標準字符未包含在字符串中；所述字符串位圖的位圖權重表示所述字符串位圖中的第一取值的數量；所述位圖差是將兩個字符串位圖中對應位置的標識位的取值分別進行異或運算得到，所述位圖差的位圖權重表示所述位圖差中異或取值為真的標識位的數量；

篩選處理模塊，用于根據所述關聯位圖信息，篩除掉所述候選字符串集合中與目標字符串的字符串距離在距離閾值范圍之外的候選字符串，并分別 計算剩余的候選字符串與所述目標字符串的字符串距離。

第四方面，提供一種字符串距離計算裝置，所述裝置用于由候選字符串集合中選擇與給定的目標字符串相似的候選字符串；所述裝置包括：

差異獲取模塊，用于獲取所述候選字符串和目標字符串中所包含字符的字符差異信息；

距離計算模塊，用于若所述字符差異信息大于差異閾值，則將所述候選字符串由候選字符串集合中篩除，并計算所述候選字符串集合中剩余的候選字符串與所述目標字符串的字符串距離。

本申請提供的字符串距離計算方法和裝置，通過根據候選字符串和目標字符串中所包含字符的字符差異信息，例如，兩者的關聯位圖信息，由候選字符串集合中預先篩除掉一部分候選字符串，再計算剩余的候選字符串與目標字符串的字符串距離，使得在候選字符串集合中通過計算字符串距離尋找相似字符串時，集合的規模得到了大大減小，從而提高了計算效率。

附圖說明

圖1是本申請一示例性實施例示出的一種字符串距離計算方法的流程圖；