陳子軒 何震瀛 荊一楠

1(復(fù)旦大學(xué)軟件學(xué)院 上海 201203)2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)

0 引 言

近年來(lái)，大規(guī)模數(shù)據(jù)圖開(kāi)始在各種各樣的應(yīng)用中扮演重要的角色。許多大型知識(shí)圖譜如YAGO[1]、Freebase[2]、Probase[3]等均被構(gòu)建出來(lái)，為許多應(yīng)用提供知識(shí)支持。隨著越來(lái)越多的大規(guī)模數(shù)據(jù)圖在應(yīng)用中被使用到，快速地對(duì)這些圖中所包含的數(shù)據(jù)信息進(jìn)行處理與分析成為了一件十分有意義的事情。

考慮到在大型數(shù)據(jù)圖上，與某個(gè)數(shù)據(jù)點(diǎn)相關(guān)的其他數(shù)據(jù)其實(shí)是非常局限在某個(gè)范圍內(nèi)的，因此，若能將每個(gè)數(shù)據(jù)點(diǎn)在數(shù)據(jù)圖上的位置特征(該點(diǎn)在圖上的位置、鄰居數(shù)據(jù)點(diǎn)范圍等)表示出來(lái)，則可以在處理具體應(yīng)用任務(wù)時(shí)，只考慮某個(gè)范圍內(nèi)的相關(guān)數(shù)據(jù)點(diǎn)，而不是在大型數(shù)據(jù)圖的全圖上進(jìn)行檢索，從而可以節(jié)省下大量時(shí)間，甚至加強(qiáng)圖上應(yīng)用的準(zhǔn)確性。

為成功刻畫(huà)每個(gè)數(shù)據(jù)點(diǎn)的位置特征，本文提出一種基于樹(shù)分解算法(本文中使用的樹(shù)分解算法來(lái)源于Wei[4]的工作)的圖上節(jié)點(diǎn)區(qū)間編碼方法，用來(lái)為圖上每個(gè)節(jié)點(diǎn)(在本文中存在兩種節(jié)點(diǎn)，分別為圖上節(jié)點(diǎn)即數(shù)據(jù)點(diǎn)與樹(shù)上節(jié)點(diǎn)，在可能存在混淆時(shí)文中區(qū)別使用，避免歧義理解；在不存在混淆的情況下，僅稱(chēng)節(jié)點(diǎn))賦予一個(gè)區(qū)間編碼，由開(kāi)始編碼與結(jié)束編碼組成。

對(duì)于一個(gè)給定的數(shù)據(jù)圖，可以使用樹(shù)分解算法將這幅圖分解成一棵特殊的分解樹(shù)。這棵分解樹(shù)上的所有節(jié)點(diǎn)均為一個(gè)由圖上節(jié)點(diǎn)組成的集合且具有以下性質(zhì)：(1) 對(duì)于圖上的每個(gè)節(jié)點(diǎn)，包含它的樹(shù)上節(jié)點(diǎn)之間在樹(shù)上保持連續(xù)，可以形成一棵節(jié)點(diǎn)子樹(shù)；(2) 對(duì)于在圖上連接在一起的兩個(gè)點(diǎn)，一定會(huì)至少共同出現(xiàn)在樹(shù)上的同一個(gè)節(jié)點(diǎn)一次。而因?yàn)橐陨蟽牲c(diǎn)性質(zhì)，對(duì)于任意兩個(gè)在數(shù)據(jù)圖上由邊連接在一起的數(shù)據(jù)點(diǎn)，其在分解樹(shù)上對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)一定會(huì)存在互相之間的祖先-后代關(guān)系。

基于這棵分解樹(shù)，可以為圖上所有節(jié)點(diǎn)賦予一個(gè)區(qū)間編碼，由開(kāi)始編碼與結(jié)束編碼組成，其中開(kāi)始編碼為此圖上節(jié)點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)在樹(shù)上的先序遍歷序號(hào)，而結(jié)束編碼為此圖上節(jié)點(diǎn)的開(kāi)始編碼加上其對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)的樹(shù)上后代節(jié)點(diǎn)數(shù)。對(duì)于兩個(gè)圖上數(shù)據(jù)點(diǎn)，若其對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)互相之間存在祖先-后代關(guān)系，則意味著這兩個(gè)數(shù)據(jù)點(diǎn)的區(qū)間編碼會(huì)存在互相包含的關(guān)系。因此，若圖上兩個(gè)數(shù)據(jù)點(diǎn)之間有邊，則其區(qū)間編碼必定存在互相包含關(guān)系；反之，若兩個(gè)數(shù)據(jù)點(diǎn)的區(qū)間編碼之間不存在互相包含關(guān)系，則這兩個(gè)數(shù)據(jù)點(diǎn)在數(shù)據(jù)圖上相互之間不可能有邊。

基于本文提出的區(qū)間編碼方法，數(shù)據(jù)圖上的每一個(gè)數(shù)據(jù)點(diǎn)均有一個(gè)對(duì)應(yīng)的區(qū)間編碼，用來(lái)表達(dá)其在圖上的相關(guān)范圍，從而刻畫(huà)出此節(jié)點(diǎn)在圖上的位置信息與鄰居信息。利用每個(gè)節(jié)點(diǎn)的區(qū)間編碼，許多在大型數(shù)據(jù)圖上的應(yīng)用可以得到加速，甚至得到更高的效果保證。舉例來(lái)說(shuō)，對(duì)于在知識(shí)圖譜上的查詢處理，利用每個(gè)節(jié)點(diǎn)的區(qū)間編碼可以快速判斷兩個(gè)數(shù)據(jù)點(diǎn)之間是否有可能存在一條邊，從而加快在查詢處理中JOIN操作的速度。除此之外，對(duì)于基于知識(shí)圖譜的智能問(wèn)答系統(tǒng)，使用區(qū)間編碼可以快速進(jìn)行一部分的實(shí)體消歧，提高整個(gè)智能問(wèn)答的效率，對(duì)于在智能問(wèn)答上的應(yīng)用，本文后面的實(shí)驗(yàn)部分通過(guò)實(shí)驗(yàn)驗(yàn)證了本文方法的有效性與實(shí)用性。

本文的貢獻(xiàn)可以總結(jié)如下：

(1) 本文提出一種基于樹(shù)分解的圖上點(diǎn)區(qū)間編碼方法，用來(lái)表示圖上節(jié)點(diǎn)的位置特征。

(2) 本文提出針對(duì)YAGO數(shù)據(jù)集的問(wèn)答問(wèn)題100句，并使用這些問(wèn)題進(jìn)行了消歧實(shí)驗(yàn)，證明了本文提出的區(qū)間編碼在實(shí)際應(yīng)用中的有效性。

1 圖上的樹(shù)分解

1.1 基本定義

樹(shù)分解是一種將一幅圖映射到一棵樹(shù)上的圖上算法，通過(guò)這種算法，一些圖上的特定問(wèn)題可以得到加速解決。樹(shù)分解的概念最早由Robertson等[5]提出。

定義2(節(jié)點(diǎn)子樹(shù))對(duì)于一幅圖G=(V,E)及在該圖上的一個(gè)樹(shù)分解TG=({Xi|i∈I},T)，定義Tv為所有包含點(diǎn)v的Xi及這些Xi之間在分解樹(shù)上的連接關(guān)系所組成的數(shù)據(jù)結(jié)構(gòu)，若Tv能夠形成一棵樹(shù)結(jié)構(gòu)，則稱(chēng)其為v對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)。

根據(jù)以上定義，可以得出以下重要引理，該引理為本文方法的基礎(chǔ)。

引理1對(duì)于一幅圖G=(V,E)及在該圖上的一個(gè)樹(shù)分解TG=({Xi|i∈I},T)，v與u為V中的兩個(gè)點(diǎn)，令Rv、Ru分別為v與u在分解樹(shù)T上的對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)，若(v,u)∈E，則Rv與Ru在分解樹(shù)T上必定存在祖先-后代關(guān)系。

對(duì)于引理1的證明如下：

根據(jù)定義1中分解樹(shù)T的性質(zhì)2可知，若對(duì)于兩點(diǎn)v、u，滿足(v,u)∈E，則在樹(shù)T上必存在一個(gè)節(jié)點(diǎn)使得其上對(duì)應(yīng)的圖上節(jié)點(diǎn)集合Xi滿足v,u∈Xi。而根據(jù)定義1中分解樹(shù)T的性質(zhì)2與定義2可知，該樹(shù)上節(jié)點(diǎn)必定同時(shí)存在于點(diǎn)v對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)Tv與點(diǎn)u對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)Tu上，因此該節(jié)點(diǎn)同時(shí)是點(diǎn)v對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)根節(jié)點(diǎn)Rv與點(diǎn)u對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)根節(jié)點(diǎn)Ru的后代節(jié)點(diǎn)。而因?yàn)樵谝豢梅纸鈽?shù)上，一個(gè)節(jié)點(diǎn)至多只能存在一個(gè)父親節(jié)點(diǎn)，因此Rv與Ru之間必定存在祖先-后代關(guān)系。引理1證畢。

1.2 樹(shù)分解算法

首先需要指出的是，對(duì)于一幅數(shù)據(jù)圖，存在著不止一種滿足定義1的樹(shù)分解，本文旨在提出結(jié)合樹(shù)分解算法和區(qū)間編碼算法的可能與應(yīng)用前景，對(duì)于各種樹(shù)分解孰優(yōu)孰劣，在本文中不予探討。本工作中采用的樹(shù)分解方法來(lái)源于Wei[4]的工作，該工作通過(guò)將一幅圖分解至一棵分解樹(shù)上，利用分解樹(shù)的特性實(shí)現(xiàn)了高效地圖上最短路徑查詢，是一次使用樹(shù)分解算法的極有意義的應(yīng)用。

算法1介紹了本文中使用的樹(shù)分解算法的具體內(nèi)容。圖1為該算法過(guò)程的一個(gè)示例，可以參考圖1理解算法1的內(nèi)容。算法1可分為兩個(gè)部分，即從數(shù)據(jù)圖將數(shù)據(jù)點(diǎn)分解至分解棧中(圖1(a)到圖1(b))與根據(jù)分解棧建立分解樹(shù)(圖1(b)到圖1(c))。

圖1 圖上的樹(shù)分解過(guò)程示例

算法1樹(shù)分解算法

輸入：數(shù)據(jù)圖G。

輸出：分解樹(shù)TG。

1) 新建分解棧S；

2) while數(shù)據(jù)圖上所剩的點(diǎn)未形成完全圖do：

3) 找到圖上具有最小度的點(diǎn)v；

4) 得出點(diǎn)v的鄰居節(jié)點(diǎn)集合U={u1,u2,…,un}；

5) 將U中所有點(diǎn)兩兩連接起來(lái)；

6) 將集合{v,u1,u2,…,un}壓入棧S中；

7) 刪除點(diǎn)v及與點(diǎn)v相連的所有邊；

8) 將圖上所有剩余點(diǎn)組成的集合壓入棧S中；

9) 從分解棧中的棧頂點(diǎn)集出棧，并使其作為分解樹(shù)TG的根節(jié)點(diǎn)，開(kāi)始構(gòu)建分解樹(shù)；

10) while分解棧S非空do：

11) 從棧頂將第i個(gè)分解棧中的節(jié)點(diǎn)集合Xi={vi,ui1,ui2,…,uim}出棧；

12) 找到滿足包含{ui1,ui2,…,uim}的最大的k(k

13) 將Xi作為Xk對(duì)應(yīng)的分解樹(shù)TG上節(jié)點(diǎn)的子節(jié)點(diǎn)。

首先介紹圖上的分解過(guò)程。第一步需要初始化一個(gè)分解棧S，用來(lái)承裝每次被分解產(chǎn)生出來(lái)的數(shù)據(jù)點(diǎn)集合(行1)。在算法1中分解過(guò)程設(shè)置為持續(xù)進(jìn)行直至圖上剩余點(diǎn)共同構(gòu)成一個(gè)完全圖(行2)，值得注意的是，此條件并非分解算法的必要內(nèi)容，分解過(guò)程的進(jìn)度同樣可以設(shè)置閾值控制，如設(shè)置當(dāng)數(shù)據(jù)圖上所剩數(shù)據(jù)點(diǎn)個(gè)數(shù)小于某個(gè)閾值時(shí)停止分解或當(dāng)數(shù)據(jù)圖中所剩數(shù)據(jù)點(diǎn)的平均度數(shù)高于某個(gè)閾值時(shí)停止分解。設(shè)置閾值控制分解進(jìn)度的好處在于樹(shù)分解算法本身的時(shí)間代價(jià)是非常高的，同時(shí)，隨著分解過(guò)程的進(jìn)行，數(shù)據(jù)圖變得更加稠密，使得每次分解的時(shí)間代價(jià)逐步提高，因此，通過(guò)設(shè)置閾值，可以在保持所需要的分解成果的前提下，減少樹(shù)分解過(guò)程的時(shí)間消耗。對(duì)于每次分解，首先找到圖上度最小的點(diǎn)v，對(duì)于度相同的點(diǎn)，則根據(jù)預(yù)先為該點(diǎn)設(shè)置的節(jié)點(diǎn)編號(hào)大小來(lái)決定分解順序(行3)。樹(shù)分解算法在該次分解中將點(diǎn)v分解掉，也將其及與其相連的所有邊刪除，并將點(diǎn)v與其所有鄰居節(jié)點(diǎn)組成的數(shù)據(jù)點(diǎn)集合壓入棧中(行6-行7)。但僅僅刪除掉點(diǎn)v有可能破壞原數(shù)據(jù)圖中存在的數(shù)據(jù)信息。舉例說(shuō)明，若圖上存在三個(gè)點(diǎn)v、u、w,三個(gè)點(diǎn)滿足關(guān)系v與u、w分別相連，而u與w之間無(wú)連接關(guān)系，直接刪除v可能導(dǎo)致u和w兩點(diǎn)之間的連通性消失，從而破壞了原數(shù)據(jù)圖中包含的數(shù)據(jù)信息。因此，在刪除點(diǎn)v的同時(shí)，需要將點(diǎn)v的所有鄰居節(jié)點(diǎn)兩兩連接在一起，以保持原圖中所有的連通性與位置信息被保存下來(lái)(行4-行5)。最后，將圖上所有剩余點(diǎn)組成的點(diǎn)集壓入棧中(行8)。

下面介紹如何由一個(gè)分解完成的分解棧構(gòu)建一棵滿足要求的分解樹(shù)。首先，將圖中剩余的所有點(diǎn)合成一個(gè)數(shù)據(jù)點(diǎn)集，使其作為分解樹(shù)的根節(jié)點(diǎn)，也將分解棧棧頂?shù)狞c(diǎn)集作為分解樹(shù)的根節(jié)點(diǎn)(行9)。隨后，每次從分解棧中出棧一個(gè)數(shù)據(jù)點(diǎn)集Xi，找到包含該點(diǎn)集除了第一個(gè)數(shù)據(jù)點(diǎn)(即在該次分解中被分解掉的那個(gè)數(shù)據(jù)點(diǎn))以外的所有點(diǎn)的最近出棧的點(diǎn)集Xk，令Xi作為Xk的子節(jié)點(diǎn)。以此方式不斷進(jìn)行，構(gòu)建出整棵分解樹(shù)(行10-行13)。

圖1為一個(gè)完整的圖上樹(shù)分解過(guò)程示例，參考圖1可以更好地理解算法1的過(guò)程。首先，原始數(shù)據(jù)圖中有6個(gè)點(diǎn)與6條邊，目標(biāo)是將該圖分解成為一棵分解樹(shù)。第一步是將該圖分解入棧，在第一次分解過(guò)程中找到當(dāng)時(shí)圖上度最小的點(diǎn)4，將點(diǎn)4與其鄰居3組成的點(diǎn)集入棧，因鄰居個(gè)數(shù)為1，所以不需要在鄰居中添加邊；繼續(xù)此過(guò)程，最終當(dāng)圖上剩下1、2、6三個(gè)點(diǎn)時(shí)形成完全圖，將點(diǎn)1、2、6組成的點(diǎn)集壓入分解棧中。然后則是構(gòu)建分解樹(shù)的過(guò)程。首先將棧頂?shù)狞c(diǎn)集{1,2,6}出棧，使其作為分解樹(shù)的根節(jié)點(diǎn)。之后繼續(xù)在分解棧中執(zhí)行出棧操作，點(diǎn)集{5,2}被出棧，需要找到包含{2}的最近被出棧的節(jié)點(diǎn)，即根節(jié)點(diǎn)，因此{(lán)5,2}作為根節(jié)點(diǎn)的子節(jié)點(diǎn)；繼續(xù)此過(guò)程，構(gòu)建出如圖1所示的分解樹(shù)。

在此示例中回想引理1，圖1(a)中的所有邊上的兩個(gè)數(shù)據(jù)點(diǎn)在圖1(c)中的分解樹(shù)中完全滿足引理1。舉例來(lái)說(shuō)，點(diǎn)3與點(diǎn)4在圖1(a)中互為鄰居，在圖1(c)的分解樹(shù)中，點(diǎn)4對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)為點(diǎn)3對(duì)應(yīng)的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)的子節(jié)點(diǎn)。

2 區(qū)間編碼

2.1 基本定義

區(qū)間編碼方法[6]是在許多數(shù)據(jù)管理問(wèn)題中都被使用到的熱門(mén)方法。此方法被廣泛應(yīng)用在XML文檔的查詢當(dāng)中[7-9]，使用區(qū)間編碼方法可以有效地表示出XML文檔中的嵌套關(guān)系，并通過(guò)比較兩個(gè)XML文檔中兩個(gè)節(jié)點(diǎn)的區(qū)間包含關(guān)系快速判斷此兩個(gè)節(jié)點(diǎn)的結(jié)構(gòu)關(guān)系。

在通過(guò)圖上的樹(shù)分解方法將一幅數(shù)據(jù)圖分解成一棵分解樹(shù)之后，一幅數(shù)據(jù)圖被以樹(shù)的形式表示出來(lái)。XML數(shù)據(jù)因其特殊的樹(shù)型結(jié)構(gòu)特征，使得區(qū)間編碼方法可以在其上得到有效利用；同樣地，當(dāng)我們用一棵分解樹(shù)來(lái)表示一幅數(shù)據(jù)圖之后，區(qū)間編碼方法同樣可以使用在這樣的一棵分解樹(shù)上，去表示數(shù)據(jù)圖上的位置信息與連接信息。因此，本文在通過(guò)樹(shù)分解算法將一幅數(shù)據(jù)圖分解為一棵分解樹(shù)之后，進(jìn)一步采用區(qū)間編碼方法為分解樹(shù)編碼，再?gòu)臉?shù)上編碼中得到每個(gè)數(shù)據(jù)圖上的數(shù)據(jù)點(diǎn)相對(duì)應(yīng)的區(qū)間編碼。本文希望將引理1的性質(zhì)通過(guò)區(qū)間編碼量化出來(lái)，以達(dá)到若兩個(gè)數(shù)據(jù)點(diǎn)互為鄰居，其區(qū)間編碼互相包含。

下面給出本工作中對(duì)于樹(shù)上編碼與圖中節(jié)點(diǎn)編碼的定義。

定義3(樹(shù)編碼)對(duì)于一棵樹(shù)T，對(duì)于樹(shù)T上的每個(gè)節(jié)點(diǎn)X，均有一組一一對(duì)應(yīng)的區(qū)間編碼(start,end)，其中：start為該樹(shù)上節(jié)點(diǎn)對(duì)應(yīng)的起始編碼；end為該樹(shù)上節(jié)點(diǎn)對(duì)應(yīng)的結(jié)束編碼。每個(gè)樹(shù)上節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間編碼稱(chēng)作該節(jié)點(diǎn)的樹(shù)編碼。

定義4(數(shù)據(jù)點(diǎn)區(qū)間編碼)對(duì)于一幅數(shù)據(jù)圖G=(V,E)，對(duì)于圖上的每個(gè)數(shù)據(jù)點(diǎn)v∈V，均有該點(diǎn)對(duì)應(yīng)的區(qū)間編碼(start,end)，其中：start為該數(shù)據(jù)點(diǎn)對(duì)應(yīng)的起始編碼；end為該數(shù)據(jù)點(diǎn)對(duì)應(yīng)的結(jié)束編碼。此區(qū)間編碼稱(chēng)作該數(shù)據(jù)點(diǎn)的數(shù)據(jù)點(diǎn)區(qū)間編碼。需要注意的是，此區(qū)間編碼與數(shù)據(jù)點(diǎn)并非一一對(duì)應(yīng)關(guān)系，即不同數(shù)據(jù)點(diǎn)可能對(duì)應(yīng)著相同的一段區(qū)間編碼。

2.2 區(qū)間編碼算法

算法2介紹了本文中使用的區(qū)間編碼算法的過(guò)程。圖2為該算法過(guò)程的一個(gè)示例，在此示例中使用的分解樹(shù)對(duì)應(yīng)圖1示例中產(chǎn)生的分解樹(shù)，可以參考圖2理解算法2的內(nèi)容。算法2可分為兩個(gè)部分，即樹(shù)編碼過(guò)程(圖2(a))與數(shù)據(jù)點(diǎn)區(qū)間編碼過(guò)程(圖2(b))。

圖2 區(qū)間編碼過(guò)程示例

算法2區(qū)間編碼算法

輸入：分解樹(shù)TG。

輸出：數(shù)據(jù)圖G上編碼點(diǎn)集V*(即在點(diǎn)集V的基礎(chǔ)上對(duì)V中每個(gè)數(shù)據(jù)點(diǎn)v均補(bǔ)充上了其數(shù)據(jù)點(diǎn)區(qū)間編碼信息)。

1) 對(duì)分解樹(shù)TG進(jìn)行先序遍歷，記錄每個(gè)樹(shù)上節(jié)點(diǎn)的先序遍歷序號(hào)及每個(gè)樹(shù)上節(jié)點(diǎn)的后代節(jié)點(diǎn)數(shù)量；

2) foreach分解樹(shù)上節(jié)點(diǎn)Xdo

3)X.start=該樹(shù)上節(jié)點(diǎn)的先序遍歷序號(hào)；

4)X.end=X.start+該樹(shù)上節(jié)點(diǎn)的后代節(jié)點(diǎn)數(shù)；

5) foreach不在樹(shù)上根節(jié)點(diǎn)XR中的數(shù)據(jù)點(diǎn)vdo

6) 將v的區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)對(duì)應(yīng)的樹(shù)編碼；

7) foreach在樹(shù)上根節(jié)點(diǎn)XR中的數(shù)據(jù)點(diǎn)udo

8) 將u的開(kāi)始區(qū)間編碼設(shè)置為0；

9) 將u的結(jié)束區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹(shù)中除了根節(jié)點(diǎn)(此處所說(shuō)的根節(jié)點(diǎn)既是其節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)同時(shí)也是整棵分解樹(shù)的根節(jié)點(diǎn))以外的其他節(jié)點(diǎn)的樹(shù)編碼中的最大結(jié)束區(qū)間編碼，需要注意的是若u的節(jié)點(diǎn)子樹(shù)只包含根節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)，那么其結(jié)束區(qū)間編碼設(shè)置為0。

首先，需要對(duì)分解樹(shù)上的每個(gè)樹(shù)上節(jié)點(diǎn)進(jìn)行區(qū)間編碼。具體編碼方法為，將分解樹(shù)上每個(gè)節(jié)點(diǎn)的開(kāi)始節(jié)點(diǎn)編碼設(shè)置為其在該分解樹(shù)上的先序遍歷序號(hào)，其結(jié)束節(jié)點(diǎn)編碼設(shè)置為該節(jié)點(diǎn)的開(kāi)始節(jié)點(diǎn)編碼加上該節(jié)點(diǎn)的后代節(jié)點(diǎn)數(shù)量(行1-行4)。

下一步根據(jù)樹(shù)編碼來(lái)對(duì)數(shù)據(jù)圖上的每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行區(qū)間編碼。對(duì)于所有未在分解樹(shù)的根節(jié)點(diǎn)中出現(xiàn)的數(shù)據(jù)點(diǎn)，將其區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)對(duì)應(yīng)的樹(shù)編碼(行5-行6)。而對(duì)于所有出現(xiàn)在樹(shù)上根節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)，則需要特殊考慮，首先將它們的開(kāi)始區(qū)間編碼均設(shè)置為0，那么無(wú)論其結(jié)束區(qū)間編碼為何值，這些根節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)的區(qū)間編碼均會(huì)互相包含(行8)。下一步還需滿足對(duì)于根節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)，它們的區(qū)間編碼需要包含其節(jié)點(diǎn)子樹(shù)中所有節(jié)點(diǎn)的區(qū)間編碼，因此，將這些在根節(jié)點(diǎn)中出現(xiàn)的數(shù)據(jù)點(diǎn)的結(jié)束區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹(shù)中除了根節(jié)點(diǎn)以外的其他節(jié)點(diǎn)的樹(shù)編碼中的最大結(jié)束區(qū)間編碼。同時(shí)需要注意的是，若某數(shù)據(jù)點(diǎn)出現(xiàn)在根節(jié)點(diǎn)中，但同時(shí)它又只出現(xiàn)在根節(jié)點(diǎn)中，那么將其結(jié)束區(qū)間編碼也設(shè)置為0，因?yàn)樵摂?shù)據(jù)點(diǎn)的區(qū)間不需要包含任何不在根節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)的區(qū)間(行9)。

圖2為一個(gè)完整的區(qū)間編碼過(guò)程示例，首先對(duì)于分解樹(shù)進(jìn)行編碼，舉例來(lái)說(shuō)，對(duì)于包含{3,2}的該樹(shù)上節(jié)點(diǎn)，其先序遍歷序號(hào)為1，有一個(gè)后代節(jié)點(diǎn)，因此其樹(shù)編碼為(1,2)。下一步對(duì)每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行區(qū)間編碼，對(duì)于不在根節(jié)點(diǎn)上的數(shù)據(jù)點(diǎn)，如數(shù)據(jù)點(diǎn)5，其區(qū)間編碼設(shè)定為對(duì)應(yīng)節(jié)點(diǎn)子樹(shù)根節(jié)點(diǎn)的樹(shù)編碼，即(3,3)；對(duì)于在根節(jié)點(diǎn)上出現(xiàn)的數(shù)據(jù)點(diǎn)，若該數(shù)據(jù)點(diǎn)只出現(xiàn)在根節(jié)點(diǎn)中，如數(shù)據(jù)點(diǎn)1，將其區(qū)間編碼設(shè)置為(0,0)；若該數(shù)據(jù)點(diǎn)在分解樹(shù)上不止出現(xiàn)一次，則將其開(kāi)始區(qū)間編碼設(shè)置為0，結(jié)束區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹(shù)中除根節(jié)點(diǎn)外的其他節(jié)點(diǎn)中的最大結(jié)束編碼，如數(shù)據(jù)點(diǎn)2，其在分解樹(shù)中除根節(jié)點(diǎn)外還出現(xiàn)在其他節(jié)點(diǎn)中，其中最大的結(jié)束編碼出現(xiàn)在包含{5,2}的該樹(shù)上節(jié)點(diǎn)的樹(shù)編碼(3,3)，因此將其區(qū)間編碼設(shè)置為(0,3)。

基于以上區(qū)間編碼方法，提出引理2。

引理2對(duì)于一幅圖G=(V,E)及在該圖上的一個(gè)樹(shù)分解TG=({Xi|i∈I},T)，v與u為V中的兩個(gè)點(diǎn)，若(v,u)∈E，則v與u的區(qū)間編碼必定存在包含關(guān)系。

引理2的證明如下。

根據(jù)引理1，可知數(shù)據(jù)點(diǎn)v與u的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)必定存在祖先-后代關(guān)系。若v與u的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)為同一個(gè)樹(shù)上節(jié)點(diǎn)(在本文的分解樹(shù)中盡可能是同為分解樹(shù)的根節(jié)點(diǎn))，則v與u的區(qū)間編碼開(kāi)始編碼均為0，結(jié)束編碼無(wú)論為何，v與u的區(qū)間編碼均會(huì)存在包含關(guān)系；若v與u的節(jié)點(diǎn)子樹(shù)的根節(jié)點(diǎn)為不同節(jié)點(diǎn)，v的節(jié)點(diǎn)子樹(shù)根節(jié)點(diǎn)為u的節(jié)點(diǎn)子樹(shù)根節(jié)點(diǎn)祖先節(jié)點(diǎn)時(shí)，根據(jù)算法2，可知v的區(qū)間編碼必定包含u的區(qū)間編碼；u的節(jié)點(diǎn)子樹(shù)根節(jié)點(diǎn)為v的節(jié)點(diǎn)子樹(shù)根節(jié)點(diǎn)祖先節(jié)點(diǎn)時(shí)同理可以證明。引理2證畢。

完成區(qū)間編碼后，每個(gè)圖上節(jié)點(diǎn)均有了一個(gè)對(duì)應(yīng)的區(qū)間編碼，且對(duì)于互為鄰居的兩個(gè)圖上節(jié)點(diǎn)，其區(qū)間編碼必存在包含關(guān)系。此性質(zhì)可以被使用在許多大型數(shù)據(jù)圖上的應(yīng)用中，如知識(shí)圖譜查詢、基于知識(shí)庫(kù)的智能問(wèn)答等應(yīng)用。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

在智能問(wèn)答應(yīng)用中，基于知識(shí)圖譜的實(shí)體歧義消除得到了廣泛應(yīng)用[10-11]。為驗(yàn)證本文方法的有效性，本文使用真實(shí)知識(shí)圖譜數(shù)據(jù)集YAGO[4]，并人工構(gòu)建了在其上適用的100句智能問(wèn)答問(wèn)題。YAGO數(shù)據(jù)集是一個(gè)大型知識(shí)庫(kù)，本文中使用的是其第一版的數(shù)據(jù)，共包含1 281萬(wàn)數(shù)據(jù)點(diǎn)及連接它們的1 901萬(wàn)條邊。

實(shí)驗(yàn)對(duì)問(wèn)句中可能出現(xiàn)歧義的實(shí)體利用區(qū)間編碼進(jìn)行歧義消除，并計(jì)算消歧率。具體消歧方法為：利用問(wèn)句中出現(xiàn)的其他確定實(shí)體對(duì)應(yīng)的數(shù)據(jù)點(diǎn)的區(qū)間編碼去與可能出現(xiàn)歧義的實(shí)體的候選數(shù)據(jù)點(diǎn)的區(qū)間編碼進(jìn)行比對(duì)，刪除掉肯定不符合條件(即與確定數(shù)據(jù)點(diǎn)的區(qū)間編碼不存在區(qū)間包含關(guān)系)的數(shù)據(jù)點(diǎn)，從而進(jìn)行一部分的消歧工作。需要注意的是，采用本文提出的區(qū)間編碼方法，并不保證能夠完全將歧義消除，但本文方法因其快速比較區(qū)間編碼的能力，比在自然語(yǔ)言處理中使用的歧義消除方法效率要高得多，因此可以幫助消歧工作提高效率。

為比較本文方法的歧義消除能力，在實(shí)驗(yàn)中我們?cè)O(shè)計(jì)了另一組基線方法，在該方法中，隨機(jī)為所有圖上數(shù)據(jù)點(diǎn)賦予一個(gè)序號(hào)值，對(duì)于某個(gè)數(shù)據(jù)點(diǎn)，其區(qū)間編碼設(shè)置為其鄰居數(shù)據(jù)點(diǎn)的最小序號(hào)值至最大序號(hào)值的范圍區(qū)間。判斷兩個(gè)數(shù)據(jù)點(diǎn)是否可能互為鄰居的方法則是分別觀察這兩個(gè)數(shù)據(jù)點(diǎn)的序號(hào)是否落在另一個(gè)數(shù)據(jù)點(diǎn)的區(qū)間編碼范圍內(nèi)。

3.2 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，統(tǒng)計(jì)了包括歧義消除率與有效消除問(wèn)題數(shù)等多種體現(xiàn)區(qū)間編碼方法表現(xiàn)的數(shù)據(jù)。對(duì)于單個(gè)問(wèn)題，其消歧率定義為消除掉的歧義數(shù)據(jù)點(diǎn)與所有歧義數(shù)據(jù)點(diǎn)的比值，若對(duì)于一個(gè)問(wèn)題，所有歧義干擾項(xiàng)均被消除，只剩下一個(gè)對(duì)應(yīng)的數(shù)據(jù)點(diǎn)，則稱(chēng)所用方法在此問(wèn)題上完成完美消歧；若對(duì)于一個(gè)問(wèn)題，能夠消除一部分歧義數(shù)據(jù)點(diǎn)，則稱(chēng)所用方法在此問(wèn)題上形成部分消歧；所有部分消歧與完美消歧合稱(chēng)為有效消歧。

表1展示了歧義消除率與歧義消除問(wèn)題數(shù)的實(shí)驗(yàn)結(jié)果。其中，總消歧率表示的是對(duì)于所有100個(gè)問(wèn)題的平均消歧率(包括完美消歧問(wèn)題、無(wú)效消歧問(wèn)題、部分消歧問(wèn)題)；有效消歧率表示的是對(duì)于有效消歧的問(wèn)題的消歧率。可以看出，本文方法表現(xiàn)遠(yuǎn)超基線方法且有著不錯(cuò)的消歧率。同時(shí)，從表中歧義消除問(wèn)題數(shù)的數(shù)據(jù)可以看出無(wú)論是對(duì)于完美消歧問(wèn)題數(shù)還是有效消歧問(wèn)題數(shù)，本文方法的表現(xiàn)都遠(yuǎn)超基線方法，且對(duì)于超過(guò)60%的問(wèn)題均能形成有效消歧。

表1 歧義消除實(shí)驗(yàn)結(jié)果

綜合上述數(shù)據(jù)，可以看出本文方法表現(xiàn)遠(yuǎn)高于基線方法，且在實(shí)際的歧義消除應(yīng)用中有著不錯(cuò)的表現(xiàn)。通過(guò)本文中的實(shí)驗(yàn)，初步證明了本文方法能夠在基于大型數(shù)據(jù)圖的實(shí)際應(yīng)用中發(fā)揮提高效率的作用。

3.3 消歧應(yīng)用

下面用一個(gè)示例來(lái)說(shuō)明本文方法是如何幫助進(jìn)行消歧的。

以下問(wèn)句是一個(gè)需要進(jìn)行實(shí)體消歧的問(wèn)句：

“復(fù)旦大學(xué)在浦東新區(qū)的那個(gè)校區(qū)的面積是多大？”

對(duì)于這個(gè)問(wèn)句，簡(jiǎn)單的實(shí)體識(shí)別技術(shù)會(huì)從句子中提取出“復(fù)旦大學(xué)”這一實(shí)體，但是復(fù)旦大學(xué)存在著多個(gè)校區(qū)，即對(duì)應(yīng)著多個(gè)歧義項(xiàng)。從句中可以得知需要問(wèn)的這個(gè)實(shí)體在數(shù)據(jù)圖上是與“浦東新區(qū)”該點(diǎn)互為鄰居，因此，此處可以使用“浦東新區(qū)”該實(shí)體的區(qū)間編碼與“復(fù)旦大學(xué)”各個(gè)校區(qū)所代表的實(shí)體的區(qū)間編碼利用引理2進(jìn)行快速比對(duì)，從而可以幫助消歧。需要注意的是，這種消歧方法大多時(shí)候并不保證能夠完成消歧，可能仍需要使用傳統(tǒng)自然語(yǔ)言的消歧方法對(duì)剩余歧義項(xiàng)進(jìn)行消除，但是使用本文方法消除每一個(gè)歧義項(xiàng)的效率遠(yuǎn)高于傳統(tǒng)消歧方法，因此只要能夠形成有效消歧，應(yīng)用本文提出的區(qū)間編碼就能加速歧義消除的過(guò)程。

4 結(jié) 語(yǔ)

本文提出一種基于樹(shù)分解的圖上節(jié)點(diǎn)區(qū)間編碼方法，利用此方法為圖上每個(gè)點(diǎn)添加表示位置特征的區(qū)間編碼屬性，從而提供了將許多在大型圖上的應(yīng)用問(wèn)題轉(zhuǎn)化到一定范圍的局部?jī)?nèi)進(jìn)行解決的可能。本文在真實(shí)數(shù)據(jù)集上進(jìn)行了智能問(wèn)答中實(shí)體消歧的實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法的有效性與實(shí)用性。當(dāng)然本文旨在提出此區(qū)間編碼的方法，拋磚引玉，并沒(méi)有深入探討其在各種應(yīng)用場(chǎng)景下的使用前景與方法，希望未來(lái)能夠有更多的工作一起探索。