[發明專利]對象歸集方法和裝置

有效

• 申請號: 201710726102.5
• 申請日: 2017-08-22
• 公開（公告）號: CN110069671B
• 公開（公告）日: 2023-07-21
• 發明（設計）人: 賀勇;李楠;李屾;龔堅;張凱
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F16/36;G06F18/22;G06Q30/0201;G06Q40/10
• 代理公司: 北京博浩百睿知識產權代理有限責任公司 11134
• 代理人: 宋子良

1.一種對象歸集方法，其特征在于，包括：

獲取目標對象之間的相似度；

根據所述目標對象之間的相似度，獲取所述目標對象的有向圖，其中，所述有向圖用于指示所述目標對象之間的關系；

根據所述有向圖確定所述目標對象所屬的集合；

其中，根據所述目標對象之間的相似度，獲取所述目標對象的所述有向圖，包括：如果兩個目標對象中，任意一個目標對象的第一字符串為另一個目標對象的第二字符串的子字符串，且所述子字符串出現在所述第二字符串中的位置滿足預設位置條件，則在所述兩個目標對象之間構建有向邊，其中，所述有向邊由字符串長度較長的目標對象指向字符串長度較短的目標對象，在所述第一字符串和所述第二字符串的長度相等時，所述有向邊按照字符串的編碼排序，由排序在后的字符串指向排序在前的字符串。

2.根據權利要求1所述的方法，其特征在于，在獲取目標對象之間的相似度之前，所述方法還包括：

對所述目標對象進行預處理，其中，所述預處理用于過濾所述目標對象中的無效信息。

3.根據權利要求2所述的方法，其特征在于，在獲取目標對象之間的相似度之前，所述方法還包括：

對所述預處理之后的目標對象進行分桶；

其中，獲取目標對象之間的相似度為獲取同一分桶內的目標對象之間的相似度。

4.根據權利要求3所述的方法，其特征在于，對所述預處理之后的目標對象進行分桶，包括如下之一：

對于僅包含一個字符的目標對象，分配至包含所述一個字符的桶標識字符所對應的桶中；

對于包含多個字符的目標對象，分配至所述多個字符包含的桶標識字符所對應的桶中。

5.根據權利要求1所述的方法，其特征在于，獲取目標對象之間的相似度，包括：

獲取字符串和所述字符串的字段長度，其中，所述字符串用于表征所述目標對象；

根據所述字符串和所述字符串的字段長度，確定所述目標對象之間的相似度。

6.根據權利要求5所述的方法，其特征在于，根據所述字符串和所述字符串的字段長度，確定所述目標對象之間的相似度，包括：

根據所述字符串獲取所述字符串的最長公共子序列；

根據所述最長公共子序列的長度和所述字符串的字段長度確定所述目標對象之間的相似度。

7.根據權利要求6所述的方法，其特征在于，根據所述目標對象之間的相似度，獲取所述目標對象的有向圖，還包括如下之一：

如果兩個目標對象中，任意一個目標對象的第一字符串為另一個目標對象的第二字符串的子字符串，且所述子字符串出現在所述第二字符串中的位置不滿足所述預設位置條件，則確定所述兩個目標對象之間不存在相連的邊；

如果所述兩個目標對象對應的字符串均不為對方字符串的子字符串，且所述兩個目標對象的相似度大于預設閾值，則在所述兩個目標對象之間構建有向邊，其中，所述有向邊由字符串長度較長的目標對象指向字符串長度較短的目標對象，在第一字符串和第二字符串的長度相等時，有向邊按照字符串的編碼排序，由排序在后的字符串指向排序在前的字符串；

如果所述兩個目標對象之間的相似度小于或等于預設閾值，則確定所述兩個目標對象之間不存在相連的邊。

8.根據權利要求1所述的方法，其特征在于，根據所述有向圖確定所述目標對象所屬的集合，包括：

獲取第一節點通過所述有向圖中的有向邊達到的所有第二節點，其中，所述第一節點為非零出度節點，所述第二節點為零出度節點；

獲取所述第一節點與所述第二節點的相似度；

確定與所述第一節點相似度最大的第二節點對應的目標對象，為所述第一節點對應的目標對象所屬的集合。

9.根據權利要求8所述的方法，其特征在于，獲取所述第一節點與所述第二節點的相似度，包括：

獲取所述第二節點對應的字符串中，每個字符在所述第一節點對應的字符串中的位置信息；

根據所述位置信息和所述第二節點對應的字符串長度，確定所述第一節點與所述第二節點的相似度。