[發明專利]分類方法、查找方法和設備

有效

• 申請號: 201410373639.4
• 申請日: 2014-07-31
• 公開（公告）號: CN105302838B
• 公開（公告）日: 2019-01-15
• 發明（設計）人: 虞志益;周力君;施煒勁;周海捷
• 申請（專利權）人: 華為技術有限公司;復旦大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/27
• 代理公司: 北京龍雙利達知識產權代理有限公司 11329
• 代理人: 王君;肖鸝

1.一種分類方法，其特征在于，所述分類方法用于分布式系統中，所述分布式系統包括一個主節點和X個節點，所述方法包括：

第一節點將所述主節點分配的待分類數據進行哈希編碼得到多個哈希碼，所述第一節點為所述X個節點之一；

所述第一節點將所述多個哈希碼根據高m位存儲到所述第一節點的s個第一存儲桶中，使得所述s個第一存儲桶中的每個第一存儲桶中的哈希碼具有相同的高m位，并且所述s個第一存儲桶中的不同第一存儲桶中的哈希碼具有不同的高m位；

所述第一節點與所述X個節點中的第二節點交換各自的s個第一存儲桶中的哈希碼，使得所述X個節點中的每個節點的第二存儲桶存儲所述X個節點中的具有相同高m位的哈希碼，并且所述X個節點中的不同節點的第二存儲桶中存儲的哈希碼具有不同的高m位；

所述第一節點將所述X個節點中與所述第一節點對應的具有相同高m位的哈希碼存儲到所述第一節點的第二存儲桶中。

2.根據權利要求1所述的分類方法，其特征在于，所述第一節點與所述X個節點中的第二節點交換各自的s個第一存儲桶中的哈希碼，使得所述X個節點中的每個節點的第二存儲桶存儲所述X個節點中的具有相同高m位的哈希碼，包括：

所述第一節點確定所述第二節點對應的哈希碼的高m位，將與所述第二節點對應的哈希碼的高m位相同的第一節點的第p個存儲桶中的哈希碼發送至所述第二節點，以便所述第二節點將所述第一節點的第p個存儲桶中的哈希碼與具有相同高m位的第二節點的第q個存儲桶中的哈希碼存儲在所述第二節點的第二存儲桶中；

所述第一節點接收所述第二節點發送的第x個存儲桶中的哈希碼，

其中，所述第一節點將所述X個節點中與所述第一節點對應的具有相同高m位的哈希碼存儲到所述第一節點的第二存儲桶中，包括：

所述第一節點將所述第二節點發送的所述第x個存儲桶中的哈希碼與具有相同高m位的所述第一節點的第y個存儲桶中的哈希碼存儲在所述第一節點的第二存儲桶中，使得具有相同高m位的哈希碼唯一對應所述X個節點中的一個節點。

3.根據權利要求1或2所述的分類方法，其特征在于，還包括：

所述第一節點將所述第一節點的第二存儲桶中的哈希碼根據次高n位存儲到t個第三個存儲桶中，其中所述t個第三存儲桶中的每個第三存儲桶中的哈希碼具有相同的高m位和次高n位，并且所述t個第三存儲桶中的不同第三存儲桶中的哈希碼具有不同的高m位和次高n位。

4.根據權利要求3所述的分類方法，其特征在于，還包括：

所述第一節點將所述t個第三存儲桶中的每個第三存儲桶中的哈希碼排序；

所述第一節點獲取所述每個第三存儲桶中的預設哈希碼和所述預設哈希碼在所述第三存儲桶中的位置信息；

所述第一節點根據所述每個第三存儲桶中的預設哈希碼和所述預設哈希碼在第三存儲桶中的位置信息生成查找表，以便所述第一節點根據所述查找表確定待查找的哈希碼在所述第三存儲桶中的位置。

5.根據權利要求3所述的分類方法，其特征在于，所述n和所述t滿足以下關系：t＝2ⁿ。

6.根據權利要求1或2所述的分類方法，其特征在于，所述待分類數據為待分類文本中的多個單詞，在所述第一節點將所述主節點分配的待分類文本中的多個單詞根據哈希編碼得到多個哈希碼之后，所述分類方法還包括：

所述第一節點確定所述多個哈希碼分別對應的多個P位碼，所述多個P位碼分別表示所述多個哈希碼對應的所述多個單詞的統計頻次；

所述第一節點將所述多個P位碼與對應的所述多個哈希碼分別結合為多個第一碼，使得所述多個P位碼分別為所述多個第一碼的低P位。

7.根據權利要求6所述的分類方法，其特征在于，在所述第一節點將所述X個節點中與所述第一節點對應的具有相同高m位的哈希碼存儲到所述第一節點的第二存儲桶中之后，所述方法還包括：

所述第一節點將所述第二存儲桶中具有相同哈希碼的第一碼的低P位相加。