[發明專利]字符串相似度的計算方法和裝置

在審

• 申請號: 201410766683.1
• 申請日: 2014-12-11
• 公開（公告）號: CN104484391A
• 公開（公告）日: 2015-04-01
• 發明（設計）人: 侯明午
• 申請（專利權）人: 北京國雙科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/27
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 吳貴明;張永明

1.一種字符串相似度的計算方法，其特征在于，包括：

切割第一字符串和第二字符串，得到所述第一字符串的第一子串和所述第二字符串的第二子串；

對比所述第二子串和所述第一字符串以刪除所述第一字符串中與所述第二子串相同的部分，得到第一差異串，并對比所述第一子串和所述第二字符串以刪除所述第二字符串中與所述第一子串相同的部分，得到第二差異串；以及

根據所述第一字符串的長度、所述第二字符串的長度、所述第一差異串的長度和所述第二差異串的長度計算所述第一字符串和所述第二字符串的相似度。

2.根據權利要求1所述的計算方法，其特征在于，所述第一子串的數量為m，所述第二子串的數量為n，m和n均為2以上的自然數，其中：

對比所述第二子串和所述第一字符串以刪除所述第一字符串中與所述第二子串相同的部分，得到第一差異串包括重復執行第一判斷步驟和第一刪除步驟，直至i＝n，得到所述第一差異串，其中，i的初始值為1：

所述第一判斷步驟：判斷所述第一字符串是否包含第二子串S2i；以及

所述第一刪除步驟：在判斷出所述第一字符串包括所述第二子串S2i的情況下，從所述第一字符串中刪除與所述第二子串S2i相同的部分，并設置i＝i+1，

對比所述第一子串和所述第二字符串以刪除所述第二字符串中與所述第一子串相同的部分，得到第二差異串包括重復執行第二判斷步驟和第二刪除步驟，直至j＝m，得到所述第二差異串，其中，j的初始值為1：

所述第二判斷步驟：判斷所述第二字符串是否包含第一子串S1j；以及

所述第二刪除步驟：在判斷出所述第二字符串包括所述第一子串S1j的情況下，從所述第二字符串中刪除與所述第一子串S1j相同的部分，并設置j＝j+1。

3.根據權利要求2所述的計算方法，其特征在于，在對比所述第二子串和所述第一字符串以刪除所述第一字符串中與所述第二子串相同的部分，得到第一差異串，并對比所述第一子串和所述第二字符串以刪除所述第二字符串中與所述第一子串相同的部分，得到第二差異串之前，所述計算方法還包括：

獲取每個所述第一子串的長度，并獲取每個所述第二子串的長度；以及

按照長度由高到低的順序分別對m個所述第一子串排序，得到第一子串S11至第一子串S1m，并按照長度由高到低的順序分別對n個所述第二子串排序，得到第二子串S21至第二子串S2n。

4.根據權利要求1所述的計算方法，其特征在于，根據所述第一字符串的長度、所述第二字符串的長度、所述第一差異串的長度和所述第二差異串的長度計算所述第一字符串和所述第二字符串的相似度包括：

按照公式計算所述相似度，其中，L(S1)為所述第一字符串的長度，L(S2)為所述第二字符串的長度，L(DS1)為所述第一差異串的長度，L(DS2)為所述第二差異串的長度，A為所述相似度。

5.一種字符串相似度的計算裝置，其特征在于，包括：

切割單元，用于切割第一字符串和第二字符串，得到所述第一字符串的第一子串和所述第二字符串的第二子串；

處理單元，用于對比所述第二子串和所述第一字符串以刪除所述第一字符串中與所述第二子串相同的部分，得到第一差異串，并對比所述第一子串和所述第二字符串以刪除所述第二字符串中與所述第一子串相同的部分，得到第二差異串；以及

計算單元，用于根據所述第一字符串的長度、所述第二字符串的長度、所述第一差異串的長度和所述第二差異串的長度計算所述第一字符串和所述第二字符串的相似度。