陳子軒 何震瀛 荊一楠

1(復(fù)旦大學(xué)軟件學(xué)院 上海 201203)2(復(fù)旦大學(xué)計算機科學(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ù)圖上，與某個數(shù)據(jù)點相關(guān)的其他數(shù)據(jù)其實是非常局限在某個范圍內(nèi)的，因此，若能將每個數(shù)據(jù)點在數(shù)據(jù)圖上的位置特征(該點在圖上的位置、鄰居數(shù)據(jù)點范圍等)表示出來，則可以在處理具體應(yīng)用任務(wù)時，只考慮某個范圍內(nèi)的相關(guān)數(shù)據(jù)點，而不是在大型數(shù)據(jù)圖的全圖上進(jìn)行檢索，從而可以節(jié)省下大量時間，甚至加強圖上應(yīng)用的準(zhǔn)確性。

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

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

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

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

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

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

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

1 圖上的樹分解

1.1 基本定義

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

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

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

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

對于引理1的證明如下：

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

1.2 樹分解算法

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

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

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

算法1樹分解算法

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

輸出：分解樹TG。

1) 新建分解棧S；

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

3) 找到圖上具有最小度的點v；

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

5) 將U中所有點兩兩連接起來；

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

7) 刪除點v及與點v相連的所有邊；

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

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

10) while分解棧S非空do：

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

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

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

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

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

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

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

2 區(qū)間編碼

2.1 基本定義

區(qū)間編碼方法[6]是在許多數(shù)據(jù)管理問題中都被使用到的熱門方法。此方法被廣泛應(yīng)用在XML文檔的查詢當(dāng)中[7-9]，使用區(qū)間編碼方法可以有效地表示出XML文檔中的嵌套關(guān)系，并通過比較兩個XML文檔中兩個節(jié)點的區(qū)間包含關(guān)系快速判斷此兩個節(jié)點的結(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ū)間編碼方法為分解樹編碼，再從樹上編碼中得到每個數(shù)據(jù)圖上的數(shù)據(jù)點相對應(yīng)的區(qū)間編碼。本文希望將引理1的性質(zhì)通過區(qū)間編碼量化出來，以達(dá)到若兩個數(shù)據(jù)點互為鄰居，其區(qū)間編碼互相包含。

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

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

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

2.2 區(qū)間編碼算法

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

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

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

輸入：分解樹TG。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

引理2的證明如下。

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

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

3 實 驗

3.1 實驗設(shè)置

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

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

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

3.2 實驗結(jié)果

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

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

表1 歧義消除實驗結(jié)果

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

3.3 消歧應(yīng)用

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

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

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

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

4 結(jié) 語

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