基於變進位編碼技術的快速詞義排歧方法

2023-06-15 16:48:16

專利名稱：基於變進位編碼技術的快速詞義排歧方法
技術領域：
本發明屬於自然語言處理技術領域。
背景技術：
詞義排歧(Word Sense Disambiguation，WSD)是自然語言處理研究領域的重要基礎技術，在自然語言處理的各個應用領域，包括機器翻譯、信息檢索、文本分類等，都有重要的應用價值。
概括地說，詞義排歧的處理目標就是確定句子中每個詞語的準確義項。為此，需要進行以下兩階段的處理1)確定每個詞語的所有可能義項，這可以通過對每個詞語的各個義項進行了語義解釋或編碼的語義詞典體現出來；2)基於詞語的語言使用環境確定合適的意義描述，這可以利用各個詞語義項所聯繫的外部知識源，包括其詞彙語義知識和百科知識，並通過局部語境中不同詞語的意義相關性計算得到。文獻[1]對目前的典型詞義排歧技術進行了簡單綜述。
在目前的各種詞義排歧技術中，Guo(2002)提出的WSD技術有其處理特點。在詞語義項定義方面，通過對目前電子詞典的釋義文本的自動處理，提取形成各個義項釋義的原語(Primitive)描述集合，大大提高了義項描述提取的自適應性[2]；在詞語相關度計算方面，可以直接計算不同義項的源語描述集中不同源語的語義相關度，從而降低了語義相關性知識的獲取難度。同時，通過考慮語境中所有義項組合的總體意義貢獻情況，取得了較好的整體排歧效果[3]。其處理方法簡要描述如下假設兩個詞語的義項釋義的原語描述集分別為P1，P2，......，Pm和Q1，Q2，......，Qn，我們可以定義x=1my=1nPrimitive_Rev(Px,Qy)]]>為這兩個義項間的語義相關值。其中Primitive_Rev(Px，Qy)表示兩個原語之間的語義相關度計算值。
這樣，如果句子中有k個詞，每個詞有ni個義項，分別通過不同的原語描述集進行描述，那麼詞義排歧時共需考慮M=i=0k-1ni]]>種可能的義項排列組合。對於每一種可能的排列組合中的k個義項，對任意兩個義項按照上面的公式計算它們之間的語義相關度，這樣共會求出Ck2(即 )個語義相關值，然後求出這Ck2個值的總和，作為這種可能排列組合的概念距離。詞義排歧的處理目標，就是從所有義項排列組合中選擇概念距離最小的組合路徑。
由於在這個計算過程中，我們需要對所有的義項排列組合路徑進行一次窮舉搜索，全部計算量為k(k-1)2MP2]]>(假設每個義項釋義的源語描述集長度都為P)，即時間複雜度為O(n2)。隨著k的增大，計算量是非常大的。因此，目前在使用該算法對實際句子進行處理過程中，一般將完整的句子分成幾個片段，每段大約5個詞，分別對每段應用上述算法，最後將所有段的結果綜合在一起作為最終結果。這種做法無疑大大降低了整個算法的處理準確性。

發明內容
本發明的目的在於提供一種可大大降低計算複雜度、提高計算效率的基於變進位編碼技術的快速詞義排歧方法。
本發明的特徵在於它依次含有以下步驟(1)計算機初始化設定描述具有k個詞的輸入語句中各個詞wi的ni個義項的義項狀態空間它的列由k個詞wi從左到右排列而成，i∈
，它的行由各個詞wi的ni個義項從上到下排列而成，ni＝0，1，...，ni-1，具長度可變，ni從電子語義詞典提取；TS狀態空間中所有義項描述總數，TS=i=0k-1ni;]]>狀態路徑s0s1...sk-1，si∈
，表示句子中第i個詞的第si個義項編號，路徑總數M=i=0k-1ni;]]>狀態路徑的變進位編碼p=i=0k-1(si*x=i+1k-1nx);]]>狀態路徑的變進位解碼 義項內容描述數組Sense[]順序存儲句子中k個詞語的所有TS個義項描述，所述之義項描述從外部語義詞典提取；狀態路徑中任意兩個義項Sense[a]和Sense[b]之間的語義相關值Sense_Rev(Sense[a],Sense[b])=x=1my=1nPrimitive_Rev(Px,Qy),]]>其中兩個義項的原語描述集分別為P1，P2，......，Pm和Q1，Q2，......，Qn；所述之Primitive_Rev(Px，Qy)從外部語義知識庫提取；Ni，j是一個二維到一維的映射函子，表示把狀態空間中第i列第j行的義項狀態映射到義項內容描述數組Sense[]的特定下標，具體映射公式為Ni,j=a=0i-1na+j;]]>path(i，p)路徑編碼為p的路徑上第i列位置上的義項狀態描述，即si＝path(i，p)，i∈
；total_path(i)狀態空間中第i列之前的所有可能路徑總數，total_path(i)=a=0i-1na;]]>概念距離狀態路徑中任意兩個義項之間的語義相關值的總和；(2)輸入需要進行詞義排歧的語句；(3)詞語義項查詢，它依次含有以下步驟(3.1)初始化i＝0，j＝0；(3.2)若i＜k，則從語義詞典中查出句子中第i個詞的所有ni個義項描述，且順序保存在義項內容描述數組Sense[]中的[j，j+ni]位置上；(3.3)令i＝i+1，j＝j+ni，重複步驟(3.2)，直到i＝k，終止；(4)構造輸入語句中各義項之間的語義相關數據表，它依次含有以下步驟(4.1)設初始義項a＝0；(4.2)若a＜TS，則設另一義項b＝0；(4.3)若b＜TS，則調用語義相關值計算公式計算義項a、b之間的語義相關值relation_value[a][b]=Sense_Rev(Sense[a],Sense[b])=x=1my=1nPrimitive_Rev(Px,Qy);]]>(4.4)令b＝b+1，重複步驟(4.3)，一直到b不再小於TS；(4.5)令a＝a+1，重複步驟(4.1--4.3)；(4.6)若a不再小於TS，終止；(5)詞語義項排歧，它依次含有以下步驟(5.1)用變進位編碼描述狀態空間中的所有狀態路徑路徑編碼從0開始，按照變進位數的進位方式，每次加1得到新的路徑編碼，一直加到M-1，順序得到所有的路徑編碼。再利用變進位編碼與狀態路徑描述之間的一一對應關係，得到各自相應的路徑描述；(5.2)利用變進位編碼的進位特點，將相鄰路徑的狀態變化分解成互相獨立的三大部分，通過考慮它們之間的相互影響，形成四張概念距離修正值表設第i列是產生直接進位的部分，稱為第二部分，該列的義項編號從m進位為m+1；第0列到第i-1列是不發生改變的部分，稱為第一部分；第i+1列到第k-1列是產生進位傳遞的部分，稱為第三部分，其中各列的義項編號從nx-1變為0，x∈[i+1，k-1]；所述的四張概念距離修正值表為表1存儲第二部分的變動對第一部分產生影響的修正值，用rev_value_1[i][j][m]表示；
表2存儲第三部分的變動對第一部分產生影響的修正值，用rev_value_2[i][j]表示；表3存儲第三部分的變動對第二部分產生影響的修正值，用rev_value_3[i][m]表示；表4存儲第三部分的變動對自身產生影響的修正值，用，用rev_value_4[i]表示；(5.3)構造步驟(5.2)所述的四張修正值表(5.31)構造rev_value_1[i][j][m]表當1≤i≤(k-1)，且在i確定的條件下，0≤j≤(total_path(i)-1)，0≤m≤(ni-2)時，它依次含有以下步驟(5.311)設i＝0；(5.312)若i＜k，則令j＝0；(5.313)若j＜total_path(i)，則令m＝0；(5.314)若m＜ni-2，則計算rev_value_1[i][j][m]=a=0i-1{relation_value(Na,path(a,j),Ni,m+1)-relation_value(Na,path(a,j),Ni,m)}]]>其中，Na，path(a，j)是第a列中編碼為j的路徑上的義項；Ni，m、Ni，m+1分別是第i列中產生直接進位的第m行和第m+1行處的義項；(5.315)令m＝m+1，重複步驟(5.314)；(5.316)若m不再小於ni-2，則令j＝j+1，重複步驟(5.313)--(5.315)；(5.317)若j不再小於total_path(i)，則令i＝i+1，重複步驟(5.312)-(5.316)，一直到i不再小於k，終止；(5.32)構造rev_value_2[i][j]表當1≤i≤(k-2)，且在i確定的條件下，0≤j≤(total_path(i)-1)時，它依次含有以下步驟(5.321)設i＝1；(5.322)若i＜k-1，則令j＝0；(5.323)若j＜total_path(i)，則計算rev_value_2[i][j]=a=0i-1b=i+1k-1{relation_value(Na,path(a,j),Nb,0)-relation_value(Na,path(a,j),Nb,nb-1)]]>其中，Na，path(a，j)是第a列中編碼為j的路徑上的義項；Nb，0、Nb，nb-1分別是第b列中產生進位傳遞的第0行和第nb-1行處的義項；(5.324)令j＝j+1，重複步驟(5.323)；(5.325)若j不再小於total_path(i)，則令i＝i+1，重複步驟(5.322)-(5.324)，一直到i不再小於k-1，終止；
(5.33)構造rev_value_3[i][m]表當0≤i≤(k-2)，且在i確定的條件下，0≤m≤(ni-1)時，它依次含有以下步驟(5.331)設i＝0；(5.332)若i＜k-1，則令m＝0；(5.333)若m＜ni-1，則計算rev_value_3[i][m]=a=i+1k-1{relation_value(Ni,m+1,Na,0)-relation_value(Ni,m,Na,na-1)}]]>其中，Ni，m、Ni，m+1分別是第i列第m行和第m+1行處的義項；Na，0、Na，na-1分別是第a列第0行和第na-1行處的義項；(5.334)令m＝m+1，重複步驟(5.333)；(5.335)若m不再小於ni-1，則令i＝i+1，重複步驟(5.332)--(5.334)，一直到i不再小於k-1，終止；(5.34)構造rev_value_4[i]表當0≤i≤(k-1)時，它依次含有以下步驟(5.341)設i＝0；(5.342)若i＜k-1，則計算rev_value_4[i]=a=i+1k-1b=a+1k-1{relation_value(Na,0,Nb,0)-relation_value(Na,na-1,Nb,nb-1)}]]>其中，Nb，0、Nb，nb-1分別是第b列第0行和第nb-1行處的義項；Na，0、Na，na-1分別是第a列第0行和第na-1行處的義項；(5.343)令i＝i+1，重複步驟(5.342)，一直到i不再小於k-1，終止；(5.4)詞義排歧，它依次含有以下步驟(5.41)計算編碼p＝0的狀態路徑的概念距離；(5.42)令p＝p+1，形成新路徑的編碼；(5.43)通過變進位解碼得到這條路徑的具體義項狀態表示；(5.44)進行新路徑的概念距離修正計算，它依次含有以下步驟(5.441)找到路徑中發生直接進位的那一列，確定基本參數i，j，m；(5.442)若第一部分為空，則修正值＝rev_value_3[i][m]+rev_value_4[i]；(5.443)若第三部分為空，則修正值＝rev_value_1[i][j][m]；(5.444)若第一、三部分都不為空，則修正值＝rev_value_1[i][j][m]+rev_value_2[i][j]+rev_value_3[i][m]+rev_value_4[i]；(5.445)新路徑的概念距離＝舊路徑的概念距離+修正值；
(5.45)在目前得到的所有路徑中選擇概念距離最小的路徑作為最佳路徑，並保存相應的最佳路徑編碼；(5.46)重複步驟(5.42)--(5.45)，直到p＞＝M；(5.47)通過路徑解碼得到最佳路徑的具體義項表示，處理結束；(5.5)最佳義項標註為句子中的每個詞語賦予最佳義項描述；(5.6)結束。
針對詞義排歧問題，我們實現了兩種算法1)全排列枚舉算法；2)變進位優化算法。然後，在一般的PC兼容機上進行了一個性能比較實驗。機器的基本配置是CPU為Intel奔騰III處理器，主頻約500MHz，內存為256M。
表1顯示了具體的實驗數據，從中可以清楚地看到，對於變進位優化算法，它的複雜度隨著輸入文本的長度增加，增長得並不快，而全排列枚舉算法的複雜度隨著輸入文本的長度增加，增長的速度是非常快的，對於包含10個詞的句子，如果某些詞的義項稍微多一點的話，就會變得很難得到結果了。這些結果驗證了我們提出的優化算法的處理有效性。
表1兩種不同的詞義排歧算法的性能比較(表中記錄了每個句子的平均用時數據)


圖1.狀態空間中相鄰編碼的路徑變化情況圖2.語義相關數據表構建流程3.建立修正值表1的流程4.建立修正值表2的流程5.建立修正值表3的流程6.建立修正值表4的流程7.基於變進位編碼技術的快速詞義排歧算法流程8.路徑概念距離修正處理流程9.具體實施例描述10.完整的句子詞義排歧處理流程11.詞語義項查詢流程圖
具體實施例方式
為了便於理解，我們對詞義排歧問題進一步定義如下假設句子中有k個詞wi，每個詞wi有ni個義項，i∈
，每個義項稱為一個狀態。這樣，如果把句子中的k個詞，按照詞序從左到右排成0，1，...，k-1列，把其中第i個詞的ni個義項從上到下排成0，1，...，ni-1行(可變長度)，我們就形成一個義項描述的狀態空間(參見圖1描述)，其中每個詞語的義項相互之間的排列組合就形成一條狀態路徑，其總數為M=i=0k-1ni]]>條。每條路徑上任意兩個義項狀態的語義相關值之和(總數為Ck2=k(k-1)2]]>個)形成了路徑的概念距離。詞義排歧處理目標，就是從所有狀態路徑中選擇概念距離最小的路徑。
通過對這個複雜計算問題進行深入研究，我們提出了一套新的優化計算技術，就是尋找一種合適的狀態路徑分解技術，把一些可能重複的狀態路徑概念距離的計算結果保存起來。其主要內容包括1)引入變進位編碼技術，對不同狀態路徑進行統一編碼，使路徑和編碼一一對應起來；2)路徑編碼從0開始，按照變進位數的進位方式，每次加1得到新的路徑編碼。通過編碼順序調整方便地完成整個狀態空間的路徑遍歷；3)利用變進位編碼的進位特點，將相鄰路徑的狀態變化情況合理地分解成互相獨立的三大部分，通過考慮它們之間的相互影響，形成四張概念距離修正值表的優化計算機制；4)設計精巧的數據結構，計算並保存相鄰路徑狀態變化中的概念距離修正值；5)根據相鄰路徑的不同狀態變化情況，通過檢索四張修正值表並進行簡單的加法運算，方便地計算出不同路徑的概念距離；這個優化算法通過空間換時間，以很小的內存空間消耗，使整體的時間複雜度從O(n2)降到基本上為線性常量的O(h*M)，大大提高了計算效率。
我們使用了「變進位」技術對目前的狀態路徑進行編碼。它的基本處理機制與通常的二進位、十進位等進位制類似，唯一不同的是，這些進位制中每一位的進位值是一樣的，比如二進位數，它的每一位都是逢二進一。而對於變進位下的數，每一位的進位值則不盡相同。這非常適合我們目前需要處理的句子中不同詞語的義項狀態數目不斷變化的情況。
如果把k個詞語的不同義項組成的狀態路徑描述看成是一個k位的變進位數，它的每一位進位值按從高到低分別確定為各個詞語的義項總數n0、n1......，nk-1。那麼利用通常的編碼解碼機制，我們就可以建立狀態路徑描述和變進位路徑編碼之間的一一對應關係。即假設狀態路徑描述為s0s1...sk-1，其中si∈
，表示句子中第i個詞的第si個義項編號。那麼其相應的變進位路徑編碼p就可以由下式計算得到p=i=0k-1(si*x=i+1k-1nx)]]>反之，對得到的變進位路徑編碼p進行解碼操作，則可以得到相應的狀態路徑中的各個義項編號，具體計算公式為 其中，運算符 表示下界取整操作。
在此條件下，可以很方便地通過編碼調整完成對所有可能的M條狀態路徑的遍歷路徑編碼從0開始，按照變進位數的進位方式，每次加1得到新的路徑編碼，一直加到M-1，從而順序得到所有的路徑編碼。然後利用變進位編碼與狀態路徑描述之間的一一對應關係，得到各自相應的路徑描述。
在這樣的遍歷順序下，相鄰編碼的兩條狀態路徑的變化情況呈現出很強的規律性，其典型變化情況如圖1所示。其中，實線表示的狀態路徑(編碼為p)，通過變進位進位，變為虛線表示的狀態路徑(編碼為p+1)。從第i+1列到第k-1列是產生進位傳遞的情況，具體狀態變化為義項編號從nj-1變為0，j∈[i+1，k-1]。第i列是產生直接進位的情況，具體狀態變化為義項編號從m進位為m+1。從第0列到第i-1列是不發生改變的情況。這樣，這種進位狀況很自然地把相鄰路徑的變化情況分拆為三個部分第一部分從第0列到第i-1列；第二部分第i列；第三部分第i+1列到第k-1列。如圖1所示。
對於每次相鄰路徑改變，三個部分中發生變化的只有第二部分和第三部分，第一部分是不發生改變的。這種情況類似與十進位下的路徑編碼15399到15400的變化情況。其中第一部分為不變的情況15，第二部分為產生直接進位的情況3→4，第三部分為產生進位傳遞的情況99→00。
這樣，如果我們計算並保存了某一改變部分對其餘部分及其自身的影響而產生的路徑概念距離的修正值，就可以通過對前一條路徑的概念距離的修正直接得到後一條路徑的概念距離，從而避免了大量重複計算。
下面，我們分別考慮第二部分和第三部分的變動對所有三部分的影響。通過簡單的排列組合(2*3)，我們可以得到如下的六種可能影響A.第二部分的變動對第一部分的影響；B.第二部分的變動對自身的影響；C.第二部分的變動對第三部分的影響；D.第三部分的變動對第一部分的變動的影響；E.第三部分的變動對第二部分的影響；F.第三部分的變動對自身的影響。
第二部分只有一列，從我們的算法可知，一列的變化對自身是沒有影響的，所以可能的影響B是可以排除的；對於可能影響C和E，其效果是一樣的，所以只需要取其中的一種就可以了。所以最後只需要考慮以下四種影響所產生的修正值
A.第二部分的變動對第一部分的影響；B.第三部分的變動對第一部分的變動的影響；C.第三部分的變動對第二部分的影響；D.第三部分的變動對自身的影響。
順著這個思路，我們很容易想到，對於每一次相鄰路徑變化，需要的修正值都包括了這四種值中的幾種或是全部，所以可以提前把這所有的四種修正值都計算出來，存入數據表中，到時就可以直接從表中查找修正值來從前一條路徑值計算得到後一條路徑值了。
這種修正值計算的具體處理流程為首先通過預處理，計算並保存句子中任意兩個義項狀態之間的語義相關值，形成語義相關數據表。這是進行路徑概念距離修正計算的基礎。然後，設計四張修正值表，分別計算並存儲以下信息表1存儲第二部分的變動對第一部分產生影響的修正值表2存儲第三部分的變動對第一部分產生影響的修正值表3存儲第三部分的變動對第二部分產生影響的修正值表4存儲第三部分的變動對自身產生影響的修正值下面詳細說明這些表的數據結構設計和具體計算方法。首先給出一些基本符號的定義●k，ni定義同前，不再重複；●TS表示句子中k個詞語的所有義項描述總數，即TS=i=0k-1ni]]>●Sense[]是一個一維義項內容描述數組，順序存儲句子中k個詞語的所有TS個義項描述。這些義項描述可以通過詞語義項查詢流程從語義詞典中獲取(詳見圖11說明)●Sense_Rev(Sense[a]，Sense[b])表示句子中任意兩個義項描述Sense[a]和Sense[b]之間的語義相關值。假設這兩個義項的原語描述集分別為P1，P2，......，Pm和Q1，Q2，......，Qn，那麼Sense_Rev(Sense[a],Sense[b])=x=1my=1nPrimitive_Rev(Px,Qy).]]>●Primitive_Rev(P1，P2)表示兩個原語P1和P2之間的語義相關度值，它們可以在系統預處理時從外部語義知識庫中獲取得到。
●Ni，j是一個二維到一維的映射函子，表示把狀態空間中第i列第j行的義項狀態映射到義項內容描述數組的特定下標，從而得到相應的義項描述信息(即上文提到的原語描述集)。具體映射公式為Ni,j=a=0i-1na+j.]]>●path(i，p)表示路徑編碼為p的路徑上第i列位置上的義項狀態描述。它建立了狀態路徑編碼p與相應的狀態路徑描述s0s1...sk-1之間的一一對應關係，即si＝path(i，p)，i∈
。
●total_path(i)表示狀態空間中第i列之前的所有可能路徑總數，計算公式為total_path(i)=a=0i-1na.]]>它將在下面的修正值表1和表2的計算控制中發揮作用。
(0)語義相關數據表的設計修正值表計算的預處理該表的數據結構由一個二維數組構成，relation_value[a][b]，存儲句子的義項內容描述數組Sense[]中任意兩個義項描述之間的語義相關值，其中a，b∈
。具體計算公式為relation_value[a][b]=Sense_Rev(Sense[a],Sense[b])=x=1my=1nPrimitive_Rev(Px,Qy).]]>這是下面四張修正值表計算的重要基礎數據。
完整的計算過程是一個二重循環，基本流程見圖2。
(1)修正值表1的設計考慮第二部分變動對第一部分的影響表1的數據結構由一個三維數組構成，rev_value_1[i][j][m]，其中i表示發生直接進位的狀態列序號，j表示狀態空間中第i列之前(左邊)的一條路徑(通過編碼表示)，m表示在第i列發生直接進位變化的狀態，即m→m+1。下同。
由於此時第三部分可以為空，而第一部分不能為空，因此直接進位發生列，即第二部分的變動範圍是1≤i≤(k-1)。在i確定的條件下，j和m的變動範圍是0≤j≤(total_path(i)-1)，0≤m≤(ni-2)。因為第i列共有ni-1種進位可能。
具體計算時，需要考慮第二部分中每種進位變化對第一部分所有路徑的影響。計算公式rev_value_1[i][j][m]=a=0i-1{relation_value(Na,path(a,j),Ni,m+1)-relation_value(Na,path(a,j),Ni,m)}]]>完整的計算過程是一個三重循環，基本流程見圖3。
(2)修正值表2的設計考慮第三部分變動對第一部分的影響表2的數據結構由一個二維數組構成，rev_value_2[i][j]，其中i，j的意義描述同表1。
由於此時第一部分、第三部分均不為空，因此直接進位發生列，即第二部分的變動範圍是1≤i≤(k-2)。在i確定的條件下，j的變動範圍是0≤j≤(total_path(i)-1)。
具體計算時，需考慮第三部分中第b列(b∈[i+1，k-1])的進位傳遞變化(狀態從nb-1變化為0)對第一部分各列的影響，並將這些影響累加起來作為第b列對第一部分的總的影響。因此，這是一個雙重累加過程。計算公式為
rev_value_2[i][j]=a=0i-1b=i+1k-1{relation_value(Na,path(a,j),Nb,0)-relation_value(Na,path(a,j),Nb,nb-1)}]]>完整的計算過程是一個二重循環，基本流程見圖4。
(3)修正值表3的設計考慮第三部分變動對第二部分的影響表3的數據結構由一個二維數組構成，rev_value_3[i][m]，其中i，m的意義描述同表1。
由於此時第三部分不為空，第一部分可以為空，因此直接進位發生列，即第二部分的變動範圍是0≤i≤(k-2)。在i確定的條件下，m的變動範圍是0≤m≤(ni-1)。
當第i列從第m個狀態進位到第m+1個狀態時，需分別計算第i+1、i+2、......、k-1列的進位傳遞變化(狀態從nx-1變化為0)對第i列的影響。計算公式為rev_value_3[i][m]=a=i+1k-1{relation_value(Ni,m+1,Na,0)-relation_value(Ni,m,Na,na-1)}]]>完整的計算過程是一個二重循環，基本流程見圖5。
(4)修正值表4的設計考慮第三部分變動對自身的影響表4的數據結構為一個一維數組rev_value_4[i]，其中i的意義描述同表1。
由於此時第三部分和第一部分均可以為空，因此直接進位發生列，即第二部分的變動範圍是0≤i≤(k-1)。
當直接進位發生在第i列時，需要分別計算第三部分中第b列(b∈[i+1，k-1])的進位傳遞變化(狀態從nb-1變化為0)對自身的影響。計算公式為rev_value_4[i]=a=i+1k-1b=a+1k-1{relation_value(Na,0,Nb,0)-relation_value(Na,na-1,Nb,nb-1)}]]>完整的計算過程是一個二重循環，基本流程見圖6。
可以證明，按照上述方法計算得到的修正值表內容很好地反映了相鄰路徑調整時的概念距離變化情況，具體證明過程可參閱附件。另外，通過對以上四張修正值表的計算複雜度進行深入分析，我們得到了以下結果算法總的時間複雜度為O(h*M),278h578.,]]>總的空間複雜度為O(2M)。其中M＝n0n1...nk-1。與原始的全排列計算方法相比，雖然花費了一定的內存空間，但時間複雜度卻從O(k2*M)降到O(h*M)，從而大大提高了處理效率。
利用上面形成的修正值計算表，我們就可以形成完整的路徑優化處理算法。圖7顯示了這種優化算法的基本處理流程。首先計算得到一條完整的狀態路徑(編碼p＝0)的概念距離，這是以後進行狀態路徑概念距離修正的出發點。然後通過調整路徑編碼得到下一條狀態路徑，通過變進位解碼技術得到這條路徑的具體義項狀態表示。接著根據其中的不同進位情況選擇不同的修正值表進行路徑概念距離修正，快速得到這條新路徑的概念距離。
一般情況下，新路徑的概念距離＝舊路徑的概念距離+表1的修正值+表2的修正值+表3的修正值+表4的修正值。圖8給出了路徑概念距離修正的具體處理過程。據此可以與已有的路徑概念距離進行比較，選擇確定到目前為止最佳的狀態路徑。這個過程不斷重複進行，直至處理完所有可能的狀態路徑。最終將得到整個狀態空間中概念距離最小的路徑作為最佳路徑。
我們以一個具體實施例來詳細介紹我們算法的處理流程假設一個句子中有5個詞，從左到右每個詞的義項數分別為2、2、3、2、4。那麼它的全部義項排列路徑將有2*2*3*2*4＝96條。下面，我們考察在圖7的優化算法處理流程中，路徑編碼從31(舊路徑)變化到32(新路徑)時形成的概念距離修正處理情況(即圖7的主循環部分)。
首先，通過變進位解碼技術，得到這兩條路徑的具體路徑表示，分別為舊路徑01013，解碼過程為 新路徑01100，解碼過程為 根據兩條路徑的進位狀態分析，可確定三個部分為第一部分第0、1列；第二部分第2列；第三部分第3、4列。參見圖9。
根據圖8的路徑概念距離修正處理流程進行分析，發現需要檢索四張表得到路徑距離修正值。具體過程如下1)從表1查修正值表1計算公式中的i第二部分是第二列，因此i＝2；表1計算公式中的j第一部分共有2*2＝4條路徑，目前是第(0*2+1*1＝)1條路徑，因此j＝1；表1計算公式中的m從第2列的第0行變動到第1行，因此m＝0；得到修正值1rev_value_1[2][1]
2)從表2查修正值表2計算公式中的i和j與表1計算公式中的i和j相同，分別是2和1。
得到修正值2rev_value_1[2][1]3)從表3查修正值表3計算公式中的i和m與表1計算公式中的i和m相同，分別是2和0。
得到修正值3rev_value_3[2]
4)從表4查修正值
表4計算公式中的i與表1計算公式中的i相同，是2。
得到修正值4rev_value_4[2]這樣，總的路徑概念距離修正值(舊路徑31→新路徑32)為rev_value(31，32)＝rev_value_1[2][1]
+rev_value_1[2][1]+rev_value_3[2]
+rev_value_4[2]從而，我們得到新路徑(p＝32)的概念距離為舊路徑(p＝31)的概念距離+rev_value(31，32)利用Guo(2002)提出的詞義排歧技術，我們實現了一個完整的自動詞義排歧處理系統。首先通過系統初始化，讀入原語描述集中任意兩個原語P1和P2之間的語義相關度值Primitive_Rev(P1，P2)，它們是整個系統進行詞義排歧處理的基礎數據。然後，針對每個待處理的句子，進行其中各個詞語的義項排歧和標註處理。圖10顯示了完整的句子詞義排歧處理流程。通過詞語義項檢索、語義相關數據表和修正值表計算、詞語義項排歧等階段的處理，可以得到句子中各個詞語的最佳義項描述結果。
圖11顯示了其中的第一階段詞語義項檢索基本處理流程。通過檢索語義詞典，我們可以得到句子中k個詞的所有TS個義項描述，並順序保存在義項內容描述數組Sense[]中。而上面介紹的優化處理技術主要集中在其中的第二、三階段。首先通過預處理(基本流程見圖2)，利用檢索得到的義項內容描述，計算得到句子中任意兩個義項描述之間的語義相關值，保存在語義相關數據表relation_value[][]中。然後順序計算得到4張修正值表(基本流程分別見圖3、圖4、圖5和圖6)。在此基礎上，就可以運行我們提出的路徑優化處理算法，完成對句子的詞語義項自動排歧工作(相關的處理流程可參閱圖7和圖8)。
這個自動詞義排歧處理系統可以在任何PC兼容機上，用標準C/C++程序設計語言實現。
參考文獻[1]Nancy Ide，Jean Veronis(1998)Word Sense DisambiguationThe State of the Art.Computational Linguistics，24(1)，p1-41. Guo Chengming(1989)Deriving a Natural Set of Semantic Primitives from Longman Dictionary ofContemporary English.PhD dissertation.New Mexico State University. Guo Chengming(2002)Chinese sense taggging.In Proc.of Seminar on linguistic meaning representation andtheir applications over the World Wide Web(http//utmk.cs.usm.my/preCo102/papers％5CGuo-preColing.doc)
權利要求
1.基於變進位編碼技術的快速詞義排歧方法，其特徵在於，它依次含有以下步驟(1)計算機初始化設定描述具有k個詞的輸入語句中各個詞wi的ni個義項的義項狀態空間它的列由k個詞wi從左到右排列而成，i∈
，它的行由各個詞wi的ni個義項從上到下排列而成，ni＝0，1，...，ni-1，具長度可變，ni從電子語義詞典提取；TS狀態空間中所有義項描述總數，TS=i=0k-1ni;]]>狀態路徑s0s1...sk-1，si∈
，表示句子中第i個詞的第si個義項編號，路徑總數M=i=0k-1ni;]]>狀態路徑的變進位編碼p=i=0k-1(si*x=i+1k-1nx);]]>狀態路徑的變進位解碼 義項內容描述數組Sense[]順序存儲句子中k個詞語的所有TS個義項描述，所述之義項描述從外部語義詞典提取；狀態路徑中任意兩個義項Sense[a]和Sense[b]之間的語義相關值Sense_Rev(Sense[a],Sense[b])=x=1my=1nPrimitive_Rev(Px,Qy),]]>其中兩個義項的原語描述集分別為P1，P2，......，Pm和Q1，Q2，......，Qn；所述之Primitive_Rev(Px，Qy)從外部語義知識庫提取；Ni，j是一個二維到一維的映射函子，表示把狀態空間中第i列第j行的義項狀態映射到義項內容描述數組Sense[]的特定下標，具體映射公式為Ni,j=a=0i-1na+j;]]>path(i，p)路徑編碼為p的路徑上第i列位置上的義項狀態描述，即si＝path(i，p)，i∈
；total_path(i)狀態空間中第i列之前的所有可能路徑總數，total_path(i)=a=0i-1na;]]>概念距離狀態路徑中任意兩個義項之間的語義相關值的總和；(2)輸入需要進行詞義排歧的語句；(3)詞語義項查詢，它依次含有以下步驟(3.1)初始化i＝0，j＝0；(3.2)若i＜k，則從語義詞典中查出句子中第i個詞的所有ni個義項描述，且順序保存在義項內容描述數組Sense[]中的[j，j+ni]位置上；(3.3)令i＝i+1，j＝j+ni，重複步驟(3.2)，直到i＝k，終止；(4)構造輸入語句中各義項之間的語義相關數據表，它依次含有以下步驟(4.1)設初始義項a＝0；(4.2)若a＜TS，則設另一義項b＝0；(4.3)若b＜TS，則調用語義相關值計算公式計算義項a、b之間的語義相關值relation_value[a][b]＝Sense_Rev(Sense[a]，Sense[b])=x=1my=1nPrimitive_Rev(Px,Qy);]]>(4.4)令b＝b+1，重複步驟(4.3)，一直到b不再小於TS；(4.5)令a＝a+1，重複步驟(4.1--4.3)；(4.6)若a不再小於TS，終止；(5)詞語義項排歧，它依次含有以下步驟(5.1)用變進位編碼描述狀態空間中的所有狀態路徑路徑編碼從0開始，按照變進位數的進位方式，每次加1得到新的路徑編碼，一直加到M-1，順序得到所有的路徑編碼。再利用變進位編碼與狀態路徑描述之間的一一對應關係，得到各自相應的路徑描述；(5.2)利用變進位編碼的進位特點，將相鄰路徑的狀態變化分解成互相獨立的三大部分，通過考慮它們之間的相互影響，形成四張概念距離修正值表設第i列是產生直接進位的部分，稱為第二部分，該列的義項編號從m進位為m+1；第0列到第i-1列是不發生改變的部分，稱為第一部分；第i+1列到第k-1列是產生進位傳遞的部分，稱為第三部分，其中各列的義項編號從nx-1變為0，x∈[i+1，k-1]；所述的四張概念距離修正值表為表1存儲第二部分的變動對第一部分產生影響的修正值，用rev_value_1[i][j][m]表示；表2存儲第三部分的變動對第一部分產生影響的修正值，用rev_value_2[i][j]表示；表3存儲第三部分的變動對第二部分產生影響的修正值，用rev_value_3[i][m]表示；表4存儲第三部分的變動對自身產生影響的修正值，用，用rev_value_4[i]表示；(5.3)構造步驟(5.2)所述的四張修正值表(5.31)構造rev_value_1[i][j][m]表當1≤i≤(k-1)，且在i確定的條件下，0≤j≤(total_path(i)-1)，0≤m≤(ni-2)時，它依次含有以下步驟(5.311)設i＝0；(5.312)若i＜k，則令j＝0；(5.313)若j＜total_path(i)，則令m＝0；(5.314)若m＜ni-2，則計算rev_value_1[i][j][m]=a=0i-1{relation_value(Na,path(a,j),Ni,m+1)-relation_value(Na,path(a,j),Ni,m)}]]>其中，Na，path(a，j)是第a列中編碼為j的路徑上的義項；Ni，m、Ni，m+1分別是第i列中產生直接進位的第m行和第m+1行處的義項；(5.315)令m＝m+1，重複步驟(5.314)；(5.316)若m不再小於ni-2，則令j＝j+1，重複步驟(5.313)--(5.315)；(5.317)若j不再小於total_path(i)，則令i＝i+1，重複步驟(5.312)-(5.316)，一直到i不再小於k，終止；(5.32)構造rev_value_2[i][j]表當1≤i≤(k-2)，且在i確定的條件下，0≤j≤(total_path(i)-1)時，它依次含有以下步驟(5.321)設i＝1；(5.322)若i＜k-1，則令j＝0；(5.323)若j＜total_path(i)，則計算rev_value_2[i][j]=a=0i-1b=i+1k-1{relation_value(Na,path(a,j),Nb,0)-relation_value(Na,path(a,j),Nb,nb-1)}]]>其中，Na，path(a.j)是第a列中編碼為j的路徑上的義項；Nb，0、Nb，nb-1分別是第b列中產生進位傳遞的第0行和第nb-1行處的義項；(5.324)令j＝j+1，重複步驟(5.323)；(5.325)若j不再小於total_path(i)，則令i＝i+1，重複步驟(5.322)-(5.324)，一直到i不再小於k-1，終止；(5.33)構造rev_value_3[i][m]表當0≤i≤(k-2)，且在i確定的條件下，0≤m≤(ni-1)時，它依次含有以下步驟(5.331)設i＝0；(5.332)若i＜k-1，則令m＝0；(5.333)若m＜ni-1，則計算rev_value_3[i][m]=a=i+0k-1{relation_value(Ni,m+1,Na,0)-relation_value(Ni,m,Na,na-1)}]]>其中，Ni，m、Ni，m+1分別是第i列第m行和第m+1行處的義項；Na，0、Na，na-1分別是第a列第0行和第na-1行處的義項；(5.334)令m＝m+1，重複步驟(5.333)；(5.335)若m不再小於ni-1，則令i＝i+1，重複步驟(5.332)--(5.334)，一直到i不再小於k-1，終止；(5.34)構造rev_value_4[i]表當0≤i≤(k-1)時，它依次含有以下步驟(5.341)設i＝0；(5.342)若i＜k-1，則計算rev_value_4[i]=a=i+1k-1b=a+1k-1{relation_value(Na,0,Nb,0)-relation_value(Na,na-1,Nb,nb-1)}]]>其中，Nb，0、Nb，nb-1分別是第b列第0行和第nb-1行處的義項；Na，0、Na，na-1分別是第a列第0行和第na-1行處的義項；(5.343)令i＝i+1，重複步驟(5.342)，一直到i不再小於k-1，終止；(5.4)詞義排歧，它依次含有以下步驟(5.41)計算編碼p＝0的狀態路徑的概念距離；(5.42)令p＝p+1，形成新路徑的編碼；(5.43)通過變進位解碼得到這條路徑的具體義項狀態表示；(5.44)進行新路徑的概念距離修正計算，它依次含有以下步驟(5.441)找到路徑中發生直接進位的那一列，確定基本參數i，j，m；(5.442)若第一部分為空，則修正值＝rev_value_3[i][m]+rev_value_4[i]；(5.443)若第三部分為空，則修正值＝rev_value_1[i][j][m]；(5.444)若第一、三部分都不為空，則修正值＝rev_value_1[i][j][m]+rev_value_2[i][j]+rev_value_3[i][m]+rev_value_4[i]；(5.445)新路徑的概念距離＝舊路徑的概念距離+修正值；(5.45)在目前得到的所有路徑中選擇概念距離最小的路徑作為最佳路徑，並保存相應的最佳路徑編碼；(5.46)重複步驟(5.42)--(5.45)，直到p＞＝M；(5.47)通過路徑解碼得到最佳路徑的具體義項表示，處理結束；(5.5)最佳義項標註為句子中的每個詞語賦予最佳義項描述；(5.6)結束。
全文摘要
基於變進位編碼技術的快速詞義排歧方法，屬於自然語言處理技術領域，其特徵在於引入變進位編碼技術，對不同狀態路徑進行統一編碼，使義項的狀態路徑與變進位編碼一一對應起來；按照變進位進位方式，通過編碼順序調整方便地完成整個狀態空間的路徑遍歷，同時以直接進位列為分界，將相鄰路徑的狀態變化合理地分解成互相獨立的三大部分，通過考慮它們之間的相互影響形成四張概念距離修正值表；根據相鄰路徑的不同狀態變化情況，通過檢索四張修正值表對前一路徑概念距離進行修正，方便地計算出新路徑的概念距離；本發明以空間換時間，大大降低了計算複雜度，提高了計算效率。
文檔編號G06F17/30GK1598812SQ20041000946
公開日2005年3月23日 申請日期2004年8月20日 優先權日2004年8月20日
發明者周強, 陳祖舜, 梅立軍, 徐偉平 申請人:清華大學