一種基于樹分解的圖上點(diǎn)區(qū)間編碼方法及應(yīng)用

陳子軒 何震瀛 荊一楠

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

0 引 言

近年來，大規(guī)模數(shù)據(jù)圖開始在各種各樣的應(yīng)用中扮演重要的角色。許多大型知識圖譜如YAGO[1]、Freebase[2]、Probase[3]等均被構(gòu)建出來，為許多應(yīng)用提供知識支持。隨著越來越多的大規(guī)模數(shù)據(jù)圖在應(yīng)用中被使用到，快速地對這些圖中所包含的數(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)范圍等)表示出來，則可以在處理具體應(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)確性。

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

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

基于這棵分解樹，可以為圖上所有節(jié)點(diǎn)賦予一個(gè)區(qū)間編碼，由開始編碼與結(jié)束編碼組成，其中開始編碼為此圖上節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)子樹的根節(jié)點(diǎn)在樹上的先序遍歷序號，而結(jié)束編碼為此圖上節(jié)點(diǎn)的開始編碼加上其對應(yīng)的節(jié)點(diǎn)子樹的樹上后代節(jié)點(diǎn)數(shù)。對于兩個(gè)圖上數(shù)據(jù)點(diǎn)，若其對應(yīng)的節(jié)點(diǎn)子樹的根節(jié)點(diǎn)互相之間存在祖先-后代關(guān)系，則意味著這兩個(gè)數(shù)據(jù)點(diǎn)的區(qū)間編碼會存在互相包含的關(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è)對應(yīng)的區(qū)間編碼，用來表達(dá)其在圖上的相關(guān)范圍，從而刻畫出此節(jié)點(diǎn)在圖上的位置信息與鄰居信息。利用每個(gè)節(jié)點(diǎn)的區(qū)間編碼，許多在大型數(shù)據(jù)圖上的應(yīng)用可以得到加速，甚至得到更高的效果保證。舉例來說，對于在知識圖譜上的查詢處理，利用每個(gè)節(jié)點(diǎn)的區(qū)間編碼可以快速判斷兩個(gè)數(shù)據(jù)點(diǎn)之間是否有可能存在一條邊，從而加快在查詢處理中JOIN操作的速度。除此之外，對于基于知識圖譜的智能問答系統(tǒng)，使用區(qū)間編碼可以快速進(jìn)行一部分的實(shí)體消歧，提高整個(gè)智能問答的效率，對于在智能問答上的應(yīng)用，本文后面的實(shí)驗(yàn)部分通過實(shí)驗(yàn)驗(yàn)證了本文方法的有效性與實(shí)用性。

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

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

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

1 圖上的樹分解

1.1 基本定義

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

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

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

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

對于引理1的證明如下：

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

1.2 樹分解算法

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

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

圖1 圖上的樹分解過程示例

算法1樹分解算法

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

輸出：分解樹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)兩兩連接起來；

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

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

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

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

10) while分解棧S非空do：

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

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

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

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

下面介紹如何由一個(gè)分解完成的分解棧構(gòu)建一棵滿足要求的分解樹。首先，將圖中剩余的所有點(diǎn)合成一個(gè)數(shù)據(jù)點(diǎn)集，使其作為分解樹的根節(jié)點(diǎn)，也將分解棧棧頂?shù)狞c(diǎn)集作為分解樹的根節(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)建出整棵分解樹(行10-行13)。

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

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

2 區(qū)間編碼

2.1 基本定義

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

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

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

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

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

2.2 區(qū)間編碼算法

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

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

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

輸入：分解樹TG。

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

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

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

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

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

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

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

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

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

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

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

下一步根據(jù)樹編碼來對數(shù)據(jù)圖上的每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行區(qū)間編碼。對于所有未在分解樹的根節(jié)點(diǎn)中出現(xiàn)的數(shù)據(jù)點(diǎn)，將其區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹的根節(jié)點(diǎn)對應(yīng)的樹編碼(行5-行6)。而對于所有出現(xiàn)在樹上根節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)，則需要特殊考慮，首先將它們的開始區(qū)間編碼均設(shè)置為0，那么無論其結(jié)束區(qū)間編碼為何值，這些根節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)的區(qū)間編碼均會互相包含(行8)。下一步還需滿足對于根節(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)，它們的區(qū)間編碼需要包含其節(jié)點(diǎn)子樹中所有節(jié)點(diǎn)的區(qū)間編碼，因此，將這些在根節(jié)點(diǎn)中出現(xiàn)的數(shù)據(jù)點(diǎn)的結(jié)束區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹中除了根節(jié)點(diǎn)以外的其他節(jié)點(diǎn)的樹編碼中的最大結(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ū)間編碼過程示例，首先對于分解樹進(jìn)行編碼，舉例來說，對于包含{3,2}的該樹上節(jié)點(diǎn)，其先序遍歷序號為1，有一個(gè)后代節(jié)點(diǎn)，因此其樹編碼為(1,2)。下一步對每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行區(qū)間編碼，對于不在根節(jié)點(diǎn)上的數(shù)據(jù)點(diǎn)，如數(shù)據(jù)點(diǎn)5，其區(qū)間編碼設(shè)定為對應(yīng)節(jié)點(diǎn)子樹根節(jié)點(diǎn)的樹編碼，即(3,3)；對于在根節(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)在分解樹上不止出現(xiàn)一次，則將其開始區(qū)間編碼設(shè)置為0，結(jié)束區(qū)間編碼設(shè)置為其節(jié)點(diǎn)子樹中除根節(jié)點(diǎn)外的其他節(jié)點(diǎn)中的最大結(jié)束編碼，如數(shù)據(jù)點(diǎn)2，其在分解樹中除根節(jié)點(diǎn)外還出現(xiàn)在其他節(jié)點(diǎn)中，其中最大的結(jié)束編碼出現(xiàn)在包含{5,2}的該樹上節(jié)點(diǎn)的樹編碼(3,3)，因此將其區(qū)間編碼設(shè)置為(0,3)。

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

引理2對于一幅圖G=(V,E)及在該圖上的一個(gè)樹分解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)子樹的根節(jié)點(diǎn)必定存在祖先-后代關(guān)系。若v與u的節(jié)點(diǎn)子樹的根節(jié)點(diǎn)為同一個(gè)樹上節(jié)點(diǎn)(在本文的分解樹中盡可能是同為分解樹的根節(jié)點(diǎn))，則v與u的區(qū)間編碼開始編碼均為0，結(jié)束編碼無論為何，v與u的區(qū)間編碼均會存在包含關(guān)系；若v與u的節(jié)點(diǎn)子樹的根節(jié)點(diǎn)為不同節(jié)點(diǎn)，v的節(jié)點(diǎn)子樹根節(jié)點(diǎn)為u的節(jié)點(diǎn)子樹根節(jié)點(diǎn)祖先節(jié)點(diǎn)時(shí)，根據(jù)算法2，可知v的區(qū)間編碼必定包含u的區(qū)間編碼；u的節(jié)點(diǎn)子樹根節(jié)點(diǎn)為v的節(jié)點(diǎn)子樹根節(jié)點(diǎn)祖先節(jié)點(diǎn)時(shí)同理可以證明。引理2證畢。

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

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

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

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

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

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

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

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

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

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

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

3.3 消歧應(yīng)用

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

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

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

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

4 結(jié) 語

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