|
對(duì)于上述問題采用傳統(tǒng)的深度優(yōu)先策略時(shí)，搜索樹如圖1所示，為了簡(jiǎn)化繪圖，只給出n=3，m=3的情況。若能與規(guī)則匹配的是 S_=[G12, G22, G32]，則要經(jīng)過(guò)14次搜索才能搜索到目標(biāo)，最壞情況下要搜索33=27次。
圖1 相關(guān)對(duì)象組合按深度優(yōu)先搜索
如果我們能夠解除對(duì)象之間的相關(guān)關(guān)系，相當(dāng)于把規(guī)則中的變量都改為常量，即實(shí)現(xiàn)解耦，如圖2所示，問題將大為簡(jiǎn)化。
圖2 相關(guān)對(duì)象組合的解耦遞解智能搜索
這里，解耦處理后的搜索已變成三個(gè)獨(dú)立的搜索。若機(jī)器不能并行處理，最壞的情況下也只要搜索3×3=9次。當(dāng)n和m取更大值時(shí)，開銷的減少更顯著，從nm次減為n m次。本文提出“閉環(huán)消除法”，先將相關(guān)關(guān)系寫入規(guī)則，然后消去不滿足相關(guān)約束的那些數(shù)據(jù)，剩下的全部滿足相關(guān)約束。匹配時(shí)就只需考慮數(shù)據(jù)中那些已知常量的匹配，也就實(shí)現(xiàn)了解耦，只需順序搜索了。由于消去一些數(shù)據(jù)，順序搜索次數(shù)也更少一些。
3 閉環(huán)消除法算法
（1） 按閉環(huán)消除法處理相關(guān)約束時(shí)，我們將規(guī)則T和對(duì)象G1～Gm中的數(shù)據(jù)都構(gòu)成閉環(huán)，如圖3所示。
（2）引入規(guī)則知識(shí)作為搜索引導(dǎo)：對(duì)T_ 中的x、y、z用xij、yij、zij代替。這里，字符i,j指明：T_中的本位字符應(yīng)與后面鄰近Ti中的第j位字符相等（即相關(guān)約束條件）。例如，在（4）式T1中的x就寫作x43，T4中的x則寫作x56，T5中的x則寫作x12 。
（3）對(duì)第一個(gè)變量 x 執(zhí)行消除法：在規(guī)則閉環(huán)中，找到第一個(gè)出現(xiàn)xij 的項(xiàng) Tp，然后對(duì)Gi 中的n個(gè)數(shù)據(jù)逐個(gè)判斷，若能在前一項(xiàng)Gp 的n個(gè)數(shù)據(jù)中搜尋到一個(gè)數(shù)據(jù)，其中的g pq = g ij ，則將Gi 的這個(gè)數(shù)據(jù)保留，否則消去。這一過(guò)程從G1到Gm往后推進(jìn)，凡遇有變量x就按此處理，否則保留全部數(shù)據(jù)。
（4）第二次執(zhí)行數(shù)據(jù)的閉環(huán)消除：當(dāng)處理進(jìn)行到Gm后，還不能保證把全部不滿足相關(guān)約束的數(shù)據(jù)消去。這時(shí)，按圖3再返回到G1，把已得到的信息（即經(jīng)消除處理后在最后一個(gè)相關(guān)對(duì)象中保留下來(lái)的數(shù)據(jù)）反饋到起始點(diǎn)處。再作消除工作，往下進(jìn)行，到Gm-1為止。
（5）對(duì)其余變量進(jìn)行閉環(huán)消除工作： x 變量的消除完成后，再對(duì)y、z照樣進(jìn)行。當(dāng)對(duì)一個(gè)變量進(jìn)行消除工作時(shí)，權(quán)把其它變量當(dāng)作常量。
（6）自動(dòng)生成子規(guī)則：在對(duì)象知識(shí)庫(kù)中對(duì)x，y，z 搜索到滿足相關(guān)約束條件的代碼后，用這些已知代碼替換x，y，z，于是規(guī)則中全是常量，解除了耦合。若搜索得到多個(gè)結(jié)果，則將形成多條子規(guī)則。
圖3 閉環(huán)消除法
將以上方法用于第2節(jié)的英文句子時(shí)，先將T3中的x用x42 ，T4 中的x用x34代替。對(duì)x執(zhí)行消除法只涉及規(guī)則和對(duì)象的兩個(gè)項(xiàng)，在電子詞典的相應(yīng)位置搜索到 g34 = g 42 = 9（表示性質(zhì)的代碼），將規(guī)則T中的x 換作9。對(duì)y 的操作也類似，不贅述。
4 閉環(huán)消除法的證明
命題：采用閉環(huán)消除法處理模型1問題后，在所有相關(guān)對(duì)象中若還剩余數(shù)據(jù)，則它們?nèi)繚M足全局相關(guān)約束條件。
證明：
我們先討論對(duì)某一相關(guān)參數(shù)（如x）作消除工作。
設(shè)問題中的相關(guān)對(duì)象(相對(duì)于x)依次為Gi、Gj、Gk、… Gs、Gt，。從Gi出發(fā)，對(duì)Gj進(jìn)行消除處理后，則Gj中剩余的全部數(shù)據(jù)定能在Gi中找到相應(yīng)的數(shù)據(jù)，使它們之間滿足局部相關(guān)約束（因?yàn)椴幌嚓P(guān)的數(shù)據(jù)已經(jīng)消去）。我們把這一特性稱作相關(guān)包含（意指滿足局部相關(guān)的數(shù)據(jù)包含在Gi的若干數(shù)據(jù)中），用符號(hào) ∝ 表示，記作
Gj ∝ Gi （7）
上一頁(yè) [1] [2] [3] 下一頁(yè)
|
