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

在審

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

1.一種字符串距離計算方法，其特征在于，所述方法用于由候選字符串集合中選擇與給定的目標字符串相似的候選字符串；所述方法包括：

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

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

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

2.根據權利要求1所述的方法，其特征在于，當獲取的所述關聯位圖信息包括：分別對應候選字符串和目標字符串的兩個字符串位圖的位圖權重時；

所述根據關聯位圖信息，篩除掉候選字符串集合中與目標字符串的距離在距離閾值范圍之外的候選字符串，包括：

如果所述候選字符串對應的字符串位圖的位圖權重，與目標字符串對應的字符串位圖的位圖權重的差值在距離閾值范圍之外，則將候選字符串篩除。

3.根據權利要求1所述的方法，其特征在于，當關聯位圖信息包括：分別對應候選字符串和目標字符串的兩個字符串位圖的位圖差的位圖權重時；

所述根據關聯位圖信息，篩除掉候選字符串集合中與目標字符串的距離在距離閾值范圍之外的候選字符串，包括：

如果所述兩個字符串位圖的位圖差的位圖權重在距離閾值范圍之外，則 將所述候選字符串篩除。

4.根據權利要求1所述的方法，其特征在于，所述候選字符串集合中的每個候選字符串的字符串位圖及對應的位圖權重，被預先計算并存儲；

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

當給定所述目標字符串時，計算所述目標字符串的字符串位圖和對應的位圖權重；

在候選字符串集合中，根據預先存儲的候選字符串的字符串位圖的位圖權重，如果候選字符串對應的位圖權重與目標字符串對應的位圖權重的差值在距離閾值之外，則將所述候選字符串篩除，剩余的候選字符串構成第一候選字符串集合；

在所述第一候選字符串集合中，分別計算各個候選字符串與目標字符串的兩個字符串位圖的位圖差，以及所述位圖差的位圖權重；如果候選字符串和目標字符串的兩個字符串位圖的位圖差的位圖權重在距離閾值范圍之外，則將所述候選字符串篩除，得到第二候選字符串集合；

分別計算目標字符串與所述第二候選字符串集合中的各個候選字符串之間的字符串距離。

5.一種字符串距離計算方法，其特征在于，所述方法用于由候選字符串集合中選擇與給定的目標字符串相似的候選字符串；所述方法包括：

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

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

6.根據權利要求5所述的方法，其特征在于，所述獲取所述候選字符串和目標字符串中所包含字符的字符差異信息，包括：

獲取第一字符數目和第二字符數目，所述第一字符數目表示所述候選字 符串中包含的不同字符的數量，所述第二字符數目表示所述目標字符串中包含的不同字符的數量；

計算所述第一字符數目和第二字符數目的差值，作為所述字符差異信息。

7.根據權利要求5所述的方法，其特征在于，所述獲取所述候選字符串和目標字符串中所包含字符的字符差異信息，包括：

獲取第三字符數目，所述第三字符數目表示：在所述候選字符串和目標字符串中，只包含于其中一個字符串的字符的數量；

將所述第三字符數目作為所述字符差異信息。