為了對(duì)付算法的破壞性的歸并，我們增加了代表輸入特征結(jié)構(gòu)的DAG的復(fù)雜性。在使用DAG來表示特征結(jié)構(gòu)時(shí)，增加一個(gè)邊或域（field）。具體地說，每個(gè)特征結(jié)構(gòu)包括兩個(gè)域：一個(gè)稱為內(nèi)容域（CONTENT field），一個(gè)稱為指針域（POINTER field）。內(nèi)容域可以為空，或者可以包含一個(gè)普通的特征結(jié)構(gòu)。類似地，指針域可以為空，或者包含一個(gè)指向其他特征結(jié)構(gòu)的指針。如果DAG的指針域?yàn)榭?，那么DAG的內(nèi)容域就包含實(shí)際被處理的特征結(jié)構(gòu)。另一方面，如果指針域不為空，則指針的方向就代表了實(shí)際被處理的特征結(jié)構(gòu)。合一運(yùn)算的合并可以通過在處理過程中改變DAG的指針域來實(shí)現(xiàn)。

為了具體說明我們的方法，下面討論特征結(jié)構(gòu)的擴(kuò)充DAG表示方法。

這個(gè)矩陣圖的擴(kuò)充DAG表示要把CONTENT域和POINTER域作為普通的特征來處理，這種擴(kuò)充DAG可以表示為如下矩陣：

圖11.4 是這樣的擴(kuò)充DAG表示圖。注意，這個(gè)擴(kuò)充DAG表示在特征的最上層既包括內(nèi)容域，也包括與內(nèi)容域相連接的指針域。對(duì)于每個(gè)嵌入的特征結(jié)構(gòu)，也采用同樣的表示方法，一直表示到原子值。

在研究合一算法的細(xì)節(jié)之前，將采用這樣的擴(kuò)充DAG來表示如下的例子。這個(gè)合一項(xiàng)目的原來的擴(kuò)充表示如圖11.5所示。

在最高一層，我們只是說，合一的結(jié)果造出了一個(gè)新的結(jié)構(gòu)，這個(gè)結(jié)構(gòu)包含來自原來的兩個(gè)項(xiàng)目的信息的并。從擴(kuò)充DAG表示可以看出，怎樣對(duì)原來的項(xiàng)目進(jìn)行相加，怎樣把某些指針從一個(gè)結(jié)構(gòu)改變到另一個(gè)結(jié)構(gòu)中，使得它們最后都包含相同的內(nèi)容。在這個(gè)例子中，首先給第一個(gè)項(xiàng)目加上一個(gè)PERSON特征，然后把它的指針指向第二個(gè)項(xiàng)目中的適當(dāng)位置并填充第一個(gè)項(xiàng)目的PERSON特征的指針域，從而給它指派一個(gè)值。

但是，處理過程還沒有完成。從圖11.6可以清楚地看出，第一個(gè)項(xiàng)目現(xiàn)在已經(jīng)包含了所有的正確信息，但第二個(gè)項(xiàng)目還沒有包含所有的正確信息，這個(gè)項(xiàng)目還缺少NUMBER特征。當(dāng)然，這時(shí)我們大概可以把指針指向第一個(gè)項(xiàng)目中的適當(dāng)位置，給第二個(gè)項(xiàng)目增加NUMBER特征。這樣改變的結(jié)果將引起兩個(gè)項(xiàng)目具有從合一得到的全部正確信息?？上н@樣的解決辦法是不恰當(dāng)?shù)?，因?yàn)檫@種辦法并不能滿足把兩個(gè)項(xiàng)目真正合一的要求。由于這兩個(gè)項(xiàng)目在最頂一層沒有完全地合一，其中一個(gè)項(xiàng)目的進(jìn)一步的合一將不會(huì)在另一個(gè)項(xiàng)目中表現(xiàn)出來。對(duì)于這個(gè)問題的解決辦法是，簡單地把第二個(gè)項(xiàng)目的指針域指向第一個(gè)項(xiàng)目的頂端。這樣做的結(jié)果使得兩個(gè)項(xiàng)目中進(jìn)一步的任何改變都可以馬上在它們兩者中同時(shí)得到反映。這種改變的結(jié)果如圖11.7所示。

責(zé)任編輯：admin