[發(fā)明專(zhuān)利]圖的相似度計(jì)算系統(tǒng)、方法以及程序

有效

• 申請(qǐng)?zhí)枺?/td>: 201080010259.4
• 申請(qǐng)日: 2010-06-09
• 公開(kāi)（公告）號(hào): CN102341802A
• 公開(kāi)（公告）日: 2012-02-01
• 發(fā)明（設(shè)計(jì)）人: 比戶(hù)將平;鹿島久嗣
• 申請(qǐng)（專(zhuān)利權(quán)）人: 國(guó)際商業(yè)機(jī)器公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京市中咨律師事務(wù)所 11247
• 代理人: 于靜;楊曉光

1.一種方法，通過(guò)計(jì)算機(jī)的處理計(jì)算在各節(jié)點(diǎn)賦予離散標(biāo)簽的兩個(gè)圖之間的相似度，包括：

在各自的所述兩個(gè)圖，向給定的節(jié)點(diǎn)及其相鄰的節(jié)點(diǎn)賦予標(biāo)簽值使得不同的值對(duì)應(yīng)于不同的離散標(biāo)簽的步驟；

在所述兩個(gè)圖依次搜索節(jié)點(diǎn)的步驟；

在搜索所述節(jié)點(diǎn)的期間，通過(guò)正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值和與該正訪問(wèn)的節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的標(biāo)簽值的散列計(jì)算來(lái)計(jì)算新的標(biāo)簽值，通過(guò)該新的標(biāo)簽值更新該正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值的步驟；以及

基于向所述兩個(gè)圖的節(jié)點(diǎn)賦予的、一致的標(biāo)簽列的個(gè)數(shù)，計(jì)算所述兩個(gè)圖之間的相似度的步驟。

2.如權(quán)利要求1所述的方法，其中：

所述標(biāo)簽值是固定寬度的位串。

3.如權(quán)利要求2所述的方法，其中：

對(duì)所述正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值位移后的值以及所述相鄰的節(jié)點(diǎn)的標(biāo)簽值異或后的值進(jìn)行異或來(lái)進(jìn)行所述散列計(jì)算。

4.如權(quán)利要求3所述的方法，其中：

對(duì)所述正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值位旋轉(zhuǎn)后的值，以及將所述相鄰的節(jié)點(diǎn)的標(biāo)簽值排序計(jì)數(shù)、對(duì)重復(fù)度計(jì)數(shù)、對(duì)計(jì)數(shù)值加法計(jì)算、位旋轉(zhuǎn)計(jì)數(shù)值的量和異或后的值進(jìn)行異或，進(jìn)行所述散列計(jì)算。

5.如權(quán)利要求4所述的方法，其中：

所述排序是基數(shù)排序。

6.如權(quán)利要求1所述的方法，其中：

所述兩個(gè)圖中的一個(gè)圖是包含給定的圖的第一節(jié)點(diǎn)的第一部分圖，所述兩個(gè)圖中的一個(gè)圖是包含該給定的圖的第二節(jié)點(diǎn)的第二部分圖，

計(jì)算出的所述兩個(gè)圖間的相似度視為該第一節(jié)點(diǎn)和第二節(jié)點(diǎn)之間的相似度。

7.一種系統(tǒng)，通過(guò)計(jì)算機(jī)的處理計(jì)算在各節(jié)點(diǎn)賦予離散標(biāo)簽的兩個(gè)圖之間的相似度，包括：

在各自的所述兩個(gè)圖，向給定的節(jié)點(diǎn)及其相鄰的節(jié)點(diǎn)賦予標(biāo)簽值使得不同的值對(duì)應(yīng)于不同的離散標(biāo)簽的單元；

在所述兩個(gè)圖依次搜索節(jié)點(diǎn)的單元；

在搜索所述節(jié)點(diǎn)的期間，通過(guò)正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值和與該正訪問(wèn)的節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的標(biāo)簽值的散列計(jì)算來(lái)計(jì)算新的標(biāo)簽值，通過(guò)該新的標(biāo)簽值更新該正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值的單元；以及

基于向所述兩個(gè)圖的節(jié)點(diǎn)賦予的、一致的標(biāo)簽列的個(gè)數(shù)，計(jì)算所述兩個(gè)圖之間的相似度的單元。

8.如權(quán)利要求7所述的系統(tǒng)，其中：

所述標(biāo)簽值是固定寬度的位串。

9.如權(quán)利要求8所述的系統(tǒng)，其中：

對(duì)所述正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值位移后的值以及所述相鄰的節(jié)點(diǎn)的標(biāo)簽值異或后的值進(jìn)行異或來(lái)進(jìn)行所述散列計(jì)算。

10.如權(quán)利要求8所述的系統(tǒng)，其中：

對(duì)所述正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值位旋轉(zhuǎn)后的值，以及將所述相鄰的節(jié)點(diǎn)的標(biāo)簽值排序計(jì)數(shù)、對(duì)重復(fù)度計(jì)數(shù)、對(duì)計(jì)數(shù)值加法計(jì)算、位旋轉(zhuǎn)計(jì)數(shù)值的量和異或后的值進(jìn)行異或，進(jìn)行所述散列計(jì)算。

11.如權(quán)利要求10所述的系統(tǒng)，其中：

所述排序是基數(shù)排序。

12.如權(quán)利要求7所述的系統(tǒng)，其中：

所述兩個(gè)圖中的一個(gè)圖是包含給定的圖的第一節(jié)點(diǎn)的第一部分圖，所述兩個(gè)圖中的一個(gè)圖是包含該給定的圖的第二節(jié)點(diǎn)的第二部分圖，

計(jì)算出的所述兩個(gè)圖間的相似度視為該第一節(jié)點(diǎn)和第二節(jié)點(diǎn)之間的相似度。

13.一種程序，通過(guò)計(jì)算機(jī)的處理計(jì)算在各節(jié)點(diǎn)賦予離散標(biāo)簽的兩個(gè)圖之間的相似度，使計(jì)算機(jī)執(zhí)行如下步驟：

在各自的所述兩個(gè)圖，向給定的節(jié)點(diǎn)及其相鄰的節(jié)點(diǎn)賦予標(biāo)簽值使得不同的值對(duì)應(yīng)于不同的離散標(biāo)簽的步驟；

在所述兩個(gè)圖依次搜索節(jié)點(diǎn)的步驟；

在搜索所述節(jié)點(diǎn)的期間，通過(guò)正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值和與該正訪問(wèn)的節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的標(biāo)簽值的散列計(jì)算來(lái)計(jì)算新的標(biāo)簽值，通過(guò)該新的標(biāo)簽值更新該正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值的步驟；以及

基于向所述兩個(gè)圖的節(jié)點(diǎn)賦予的、一致的標(biāo)簽列的個(gè)數(shù)，計(jì)算所述兩個(gè)圖之間的相似度的步驟。

14.如權(quán)利要求13所述的系統(tǒng)，其中：

所述標(biāo)簽值是固定寬度的位串。

15.如權(quán)利要求14所述的系統(tǒng)，其中：

對(duì)所述正訪問(wèn)的節(jié)點(diǎn)的標(biāo)簽值位移后的值以及所述相鄰的節(jié)點(diǎn)的標(biāo)簽值異或后的值進(jìn)行異或來(lái)進(jìn)行所述散列計(jì)算。