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

在審

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

技術領域

本發明涉及數據處理領域，具體而言，涉及一種字符串相似度的計算方法和裝置。

背景技術

字符串相似在文本分析中具有重要意義。現有的字符串相似度計算方法比較成熟的是計算最小編輯距離的Levenshtein方法。Levenshtein方法是指兩個字符串之間，由一個轉化為另一個字符串所需的最少編輯步驟。編輯操作包括替換、刪除、插入。該方法基于字符編輯，均在一定誤差，并且進行相似度計算的路徑較為復雜，導致字符串相似度計算的效率偏低。

針對現有技術中計算字符串相似度的效率低的問題，目前尚未提出有效的解決方案。

發明內容

本發明的主要目的在于提供一種字符串相似度的計算方法和裝置，以解決現有技術中計算字符串相似度的效率低的問題。

為了實現上述目的，根據本發明實施例的一個方面，提供了一種字符串相似度的計算方法。

根據本發明的字符串相似度的計算方法包括：切割第一字符串和第二字符串，得到所述第一字符串的第一子串和所述第二字符串的第二子串；對比所述第二子串和所述第一字符串以刪除所述第一字符串中與所述第二子串相同的部分，得到第一差異串，并對比所述第一子串和所述第二字符串以刪除所述第二字符串中與所述第一子串相同的部分，得到第二差異串；以及根據所述第一字符串的長度、所述第二字符串的長度、所述第一差異串的長度和所述第二差異串的長度計算所述第一字符串和所述第二字符串的相似度。

進一步地，所述第一子串的數量為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。

進一步地，在對比所述第二子串和所述第一字符串以刪除所述第一字符串中與所述第二子串相同的部分，得到第一差異串，并對比所述第一子串和所述第二字符串以刪除所述第二字符串中與所述第一子串相同的部分，得到第二差異串之前，所述計算方法還包括：獲取每個所述第一子串的長度，并獲取每個所述第二子串的長度；以及按照長度由高到低的順序分別對m個所述第一子串排序，得到第一子串S11至第一子串S1m，并按照長度由高到低的順序分別對n個所述第二子串排序，得到第二子串S21至第二子串S2n。

進一步地，根據所述第一字符串的長度、所述第二字符串的長度、所述第一差異串的長度和所述第二差異串的長度計算所述第一字符串和所述第二字符串的相似度包括：按照公式計算所述相似度，其中，L(S1)為所述第一字符串的長度，L(S2)為所述第二字符串的長度，L(DS1)為所述第一差異串的長度，L(DS2)為所述第二差異串的長度，A為所述相似度。

為了實現上述目的，根據本發明實施例的另一方面，提供了一種字符串相似度的計算裝置。

根據本發明的字符串相似度的計算裝置包括：切割單元，用于切割第一字符串和第二字符串，得到所述第一字符串的第一子串和所述第二字符串的第二子串；處理單元，用于對比所述第二子串和所述第一字符串以刪除所述第一字符串中與所述第二子串相同的部分，得到第一差異串，并對比所述第一子串和所述第二字符串以刪除所述第二字符串中與所述第一子串相同的部分，得到第二差異串；以及計算單元，用于根據所述第一字符串的長度、所述第二字符串的長度、所述第一差異串的長度和所述第二差異串的長度計算所述第一字符串和所述第二字符串的相似度。