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

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

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

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

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

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

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

責任編輯：admin