[發(fā)明專利]偏序數(shù)據(jù)的處理方法、裝置、系統(tǒng)及存儲(chǔ)介質(zhì)

在審

• 申請(qǐng)?zhí)枺?/td>: 201910538902.3
• 申請(qǐng)日: 2019-06-20
• 公開（公告）號(hào): CN112115304A
• 公開（公告）日: 2020-12-22
• 發(fā)明（設(shè)計(jì)）人: 陳冠霖;李世雷;王軼凡;張釙
• 申請(qǐng)（專利權(quán)）人: 百度（中國(guó)）有限公司
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901;G06F16/903
• 代理公司: 北京同立鈞成知識(shí)產(chǎn)權(quán)代理有限公司 11205
• 代理人: 朱穎;劉芳

1.一種偏序數(shù)據(jù)的處理方法，其特征在于，包括：

獲取數(shù)據(jù)集合對(duì)應(yīng)的偏序關(guān)系有向圖；

將所述偏序關(guān)系有向圖切分成相互獨(dú)立的子圖；

若所述子圖上存在噪聲數(shù)據(jù)對(duì)應(yīng)的環(huán)狀結(jié)構(gòu)，則根據(jù)預(yù)設(shè)的策略對(duì)所述環(huán)狀結(jié)構(gòu)的邊進(jìn)行減除處理，得到消除噪聲的偏序數(shù)據(jù)。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，獲取數(shù)據(jù)集合對(duì)應(yīng)的偏序關(guān)系有向圖，包括：

根據(jù)數(shù)據(jù)集合中數(shù)據(jù)之間的偏序關(guān)系，構(gòu)建偏序關(guān)系有向圖；其中，所述偏序關(guān)系有向圖中的節(jié)點(diǎn)與所述數(shù)據(jù)集合中的數(shù)據(jù)標(biāo)識(shí)對(duì)應(yīng)；所述偏序關(guān)系有向圖中連接所述節(jié)點(diǎn)的邊用于表示所述節(jié)點(diǎn)之間的偏序關(guān)系。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，將所述偏序關(guān)系有向圖切分成相互獨(dú)立的子圖，包括：

按照查詢，將所述偏序關(guān)系有向圖切分成相互獨(dú)立的子圖；其中，每個(gè)所述查詢對(duì)應(yīng)一個(gè)子圖。

4.根據(jù)權(quán)利要求1-3中任一項(xiàng)所述的方法，其特征在于，還包括：

判斷所述子圖上是否存在噪聲數(shù)據(jù)對(duì)應(yīng)的環(huán)狀結(jié)構(gòu)。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述判斷所述子圖上是否存在噪聲數(shù)據(jù)對(duì)應(yīng)的環(huán)狀結(jié)構(gòu)，包括：

采用遍歷所述子圖上的節(jié)點(diǎn)來(lái)確定所述子圖上是否存在環(huán)狀結(jié)構(gòu)；或者，獲取所述子圖的鄰接表，根據(jù)所述鄰接表中節(jié)點(diǎn)的接續(xù)關(guān)系，確定所述子圖上是否存在環(huán)狀結(jié)構(gòu)。

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，根據(jù)預(yù)設(shè)的策略對(duì)所述環(huán)狀結(jié)構(gòu)的邊進(jìn)行減除處理，得到消除噪聲的偏序數(shù)據(jù)，包括：

采用分布式處理方式對(duì)所述子圖中的所述環(huán)狀結(jié)構(gòu)進(jìn)行遍歷處理；所述遍歷處理是指以所述環(huán)狀結(jié)構(gòu)中的任一節(jié)點(diǎn)為起點(diǎn)，依次遍歷所述環(huán)狀結(jié)構(gòu)的其他節(jié)點(diǎn)，得到所述環(huán)狀結(jié)構(gòu)的所有邊，以及每個(gè)邊的權(quán)重值；

按照權(quán)重的從小到大的順序，剪除所有子圖的所述環(huán)狀結(jié)構(gòu)中的至少一條邊，直到所述子圖中不存在環(huán)狀結(jié)構(gòu)。

7.根據(jù)權(quán)利要求6所述的方法，其特征在于，還包括：若所述環(huán)狀結(jié)構(gòu)中存在權(quán)重相同的邊，則按照剪除次數(shù)最少的原則進(jìn)行邊的剪除。

8.一種偏序數(shù)據(jù)的處理裝置，其特征在于，包括：

獲取模塊，用于獲取數(shù)據(jù)集合對(duì)應(yīng)的偏序關(guān)系有向圖；

切分模塊，用于將所述偏序關(guān)系有向圖切分成相互獨(dú)立的子圖；

處理模塊，用于在所述子圖上存在噪聲數(shù)據(jù)對(duì)應(yīng)的環(huán)狀結(jié)構(gòu)時(shí)，根據(jù)預(yù)設(shè)的策略對(duì)所述環(huán)狀結(jié)構(gòu)的邊進(jìn)行減除處理，得到消除噪聲的偏序數(shù)據(jù)。

9.一種偏序數(shù)據(jù)的處理系統(tǒng)，其特征在于，包括：存儲(chǔ)器和處理器，存儲(chǔ)器中存儲(chǔ)有所述處理器的可執(zhí)行指令；其中，所述處理器配置為經(jīng)由執(zhí)行所述可執(zhí)行指令來(lái)執(zhí)行權(quán)利要求1-7所述的偏序數(shù)據(jù)的處理方法。

10.一種計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)，其上存儲(chǔ)有計(jì)算機(jī)程序，其特征在于，該程序被處理器執(zhí)行時(shí)實(shí)現(xiàn)權(quán)利要求1-7任一項(xiàng)所述的偏序數(shù)據(jù)的處理方法。