劉禹鋒,楊 帆,劉 健
(南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院,南京 210046)
圖文法是可視化語(yǔ)言的一種直觀規(guī)范的描述工具。作為字符文法的二維擴(kuò)展,圖文法產(chǎn)生式(圖重寫(xiě)規(guī)則)的左右端均為符合圖論定義的點(diǎn)邊圖。類似于一維字符文法,圖文法主要分為推導(dǎo)和歸約兩種工作流程,其中,推導(dǎo)可以從初始圖出發(fā)生成各類可視化語(yǔ)言,歸約可用來(lái)驗(yàn)證輸入圖與給定文法之間的歸屬關(guān)系,并且已被廣泛應(yīng)用于可視化語(yǔ)言配置[1]、軟件系統(tǒng)分析[2-3]、模式識(shí)別[4-5]等任務(wù)??傮w而言,圖文法的多數(shù)實(shí)際應(yīng)用所涉及的主要工作流是歸約,推導(dǎo)的作用更多體現(xiàn)在可視化語(yǔ)言的形式定義上。目前,多數(shù)圖文法應(yīng)用的大致流程為:根據(jù)實(shí)際需求場(chǎng)景設(shè)計(jì)一組產(chǎn)生式,再根據(jù)這些產(chǎn)生式分析輸入圖的語(yǔ)法結(jié)構(gòu)及語(yǔ)義模型完成具體任務(wù)。以圖文法在實(shí)體-關(guān)系(E-R)圖中的應(yīng)用為例,若設(shè)計(jì)一組描述E-R 圖的產(chǎn)生式,使用這些產(chǎn)生式對(duì)一個(gè)任意E-R 圖進(jìn)行歸約可以用來(lái)驗(yàn)證該E-R 圖語(yǔ)法語(yǔ)義上的合法性,而E-R 圖的生成主要由數(shù)據(jù)庫(kù)設(shè)計(jì)人員在概念設(shè)計(jì)階段進(jìn)行繪制而不是由初始圖推導(dǎo)生成。因此,多數(shù)圖文法框架都會(huì)配備一個(gè)分析算法用于歸約流程的實(shí)際執(zhí)行,而將推導(dǎo)僅視作分析算法的反方向流程來(lái)定義各類可視化語(yǔ)言。
作為一個(gè)具有雙向工作流的形式化方法,圖文法的推導(dǎo)操作具有不少潛在應(yīng)用場(chǎng)景,其中最直接的應(yīng)用方向應(yīng)屬圖樣本的自動(dòng)生成。圖樣本生成技術(shù)是為了應(yīng)對(duì)現(xiàn)實(shí)世界中圖樣本數(shù)量不足的挑戰(zhàn)。一部分圖樣本生成方法依據(jù)統(tǒng)計(jì)方法進(jìn)行圖的生成操 作,例 如Erdos-Renyi[6]、Barabasi-Albert[7]以 及Watts-Strogatz[8],這些方法的應(yīng)用流程為:首先確定圖結(jié)點(diǎn)數(shù)量,然后根據(jù)特定概率在結(jié)點(diǎn)之間進(jìn)行邊的連接;另一部分圖樣本生成方法將圖生成相關(guān)問(wèn)題建模成函數(shù),并通過(guò)圖深度模型進(jìn)行學(xué)習(xí)處理,例如GCPN[9]、GraphRNN[10]、GRANs[11]、MolGAN[12]、L-MolGAN[13]以及MoFlow[14]??傮w而言,這些方法所生成均為真實(shí)圖的模擬或近似圖。與之相比,通過(guò)圖文法的產(chǎn)生式依據(jù)嚴(yán)格的圖匹配和嵌入轉(zhuǎn)換要求所生成的圖樣本的歸屬關(guān)系是確定的,生成結(jié)果具有其他方法難以比擬的準(zhǔn)確性,在一些場(chǎng)景下也可以作為其他圖生成模型的補(bǔ)充方法。例如,若使用圖文法進(jìn)行E-R 圖的生成,只要產(chǎn)生式的設(shè)計(jì)符合規(guī)范,那么根據(jù)這些產(chǎn)生式正確推導(dǎo)所生成的圖的語(yǔ)法結(jié)構(gòu)和語(yǔ)義模型一定是合法的,即屬于文法定義的語(yǔ)言。然而,推導(dǎo)工作流在實(shí)際應(yīng)用中存在的主要問(wèn)題為:1)圖文法形式框架為了歸約算法能夠順利停機(jī),規(guī)定了產(chǎn)生式規(guī)模遞增約束,即產(chǎn)生式右圖結(jié)點(diǎn)數(shù)量或終結(jié)點(diǎn)數(shù)量大于左圖,而這種規(guī)模遞增約束在推導(dǎo)操作中導(dǎo)致了圖規(guī)??梢詿o(wú)限制增加,反而會(huì)出現(xiàn)算法無(wú)法停機(jī)的情況;2)歸約是一個(gè)基于回溯過(guò)程窮舉產(chǎn)生式和圖柄(產(chǎn)生式一端在圖中的匹配子圖)的過(guò)程。對(duì)于一個(gè)給定主圖和一組產(chǎn)生式,只要存在任意一條可歸約到初始結(jié)點(diǎn)的通路即可證明該圖的合法性。相比之下,推導(dǎo)過(guò)程并不存在一個(gè)明確的目標(biāo)圖,而從一個(gè)初始圖出發(fā)可生成圖的空間是無(wú)限大的,過(guò)程中所產(chǎn)生的不確定性給產(chǎn)生式和圖柄的選擇帶來(lái)了一定的困難。
針對(duì)上述問(wèn)題,本文對(duì)圖文法的自動(dòng)推導(dǎo)技術(shù)進(jìn)行研究,在EGG 圖文法[15]的基礎(chǔ)上提出一種自動(dòng)推導(dǎo)算法,以解決圖文法在自動(dòng)推導(dǎo)過(guò)程中所面臨的問(wèn)題,并可作為一種新型的邏輯型圖樣本生成方法供用戶使用。
類似于一維字符文法,圖文法可以分為上下文無(wú)關(guān)文法和上下文相關(guān)文法。上下文無(wú)關(guān)文法的產(chǎn)生式左端只能包含一個(gè)結(jié)點(diǎn),因此具有簡(jiǎn)潔而直觀的優(yōu)點(diǎn),例如NCE[16]和HRG[17]。與之相比,上下文相關(guān)文法沒(méi)有這樣的限制,其產(chǎn)生式左端可以是一個(gè)具有任意數(shù)量結(jié)點(diǎn)的圖,因此具有更強(qiáng)的表達(dá)能力。以E-R 圖配置為例,若要設(shè)計(jì)一個(gè)可以在圖中已有實(shí)體之間添加聯(lián)系的文法,這對(duì)上下文無(wú)關(guān)文法而言非常困難[18],而上下文相關(guān)文法可以將多個(gè)實(shí)體都放入產(chǎn)生式左端以解決該問(wèn)題,常見(jiàn)的上下文相關(guān)文法包括LGG[18]和RGG[19]。此外,為了擴(kuò)展圖文法的應(yīng)用范圍,一部分研究者嘗試在文法框架中引入時(shí)間、空間等語(yǔ)義信息,例如SGG[20]、CGG[21]、TEGG[22]以及TGGG[23]。
作為一種基于規(guī)則的系統(tǒng)[24],圖文法的基本操作為L(zhǎng)/R-application,即使用產(chǎn)生式右圖/左圖替換左圖/右圖在主圖中所匹配的子圖(圖柄)的過(guò)程,構(gòu)成了推導(dǎo)或歸約工作流。在替換過(guò)程中,新圖的嵌入和舊圖的刪除都要嚴(yán)格依據(jù)文法上下文進(jìn)行。因此,上下文描述是圖文法形式框架的一個(gè)重要問(wèn)題。按照上下文的形式,圖文法可以分為隱式文法和顯式文法。顯式文法將上下文以結(jié)點(diǎn)的形式定義在產(chǎn)生式中,例如LGG 將上下文以結(jié)點(diǎn)的方式放置在產(chǎn)生式中,語(yǔ)義上通過(guò)通配符的方式管理結(jié)點(diǎn)標(biāo)號(hào)的匹配。相比之下,隱式文法的產(chǎn)生式中不包含上下文結(jié)點(diǎn)。例如,RGG 的產(chǎn)生式中不包含上下文結(jié)點(diǎn),形式更為簡(jiǎn)潔[25],而圖轉(zhuǎn)換的操作都是通過(guò)結(jié)點(diǎn)中內(nèi)嵌的頂點(diǎn)進(jìn)行。對(duì)比兩種類型的圖文法,顯式文法更加直觀但產(chǎn)生式規(guī)模較大,隱式文法不夠直觀但形式簡(jiǎn)潔易于設(shè)計(jì)。不同于這些方法,EGG 使用了隱式文法和顯式文法的一種折中形式的上下文描述形式。具體而言,EGG 產(chǎn)生式中雖然不包含上下文結(jié)點(diǎn),但是保留了一條只有一個(gè)端點(diǎn)和結(jié)點(diǎn)相連接的邊——懸邊,來(lái)描述產(chǎn)生式的上下文。懸邊僅考慮了上下文的結(jié)構(gòu)信息而忽略了語(yǔ)義信息,因此EGG 可以在保留直觀性的同時(shí)也具有較高的文法抽象性。圖1 是一個(gè)EGG 產(chǎn)生式,產(chǎn)生式的兩端各有兩條懸邊,并通過(guò)標(biāo)號(hào)“1”和“2”構(gòu)成雙射關(guān)系。圖2 是一個(gè)使用圖1 產(chǎn)生式進(jìn)行一步推導(dǎo)的實(shí)例,其中,圖2 的上部是一個(gè)主圖,虛線框內(nèi)為產(chǎn)生式左端在主圖中匹配的子圖,即圖柄,圖的下部是使用產(chǎn)生式右端替換圖柄產(chǎn)生的新主圖。在L-application 操作過(guò)程中,懸邊及其標(biāo)號(hào)是替換操作的連接依據(jù),保證了新主圖中不會(huì)出現(xiàn)懸邊。
圖1 一個(gè)EGG 產(chǎn)生式Fig.1 An EGG production
圖2 EGG 一步推導(dǎo)Fig.2 One-step derivation of EGG
如上文所述,產(chǎn)生式規(guī)模遞增約束為圖文法歸約工作流的可停機(jī)性提供了保障,卻給推導(dǎo)的自動(dòng)化工作流程帶來(lái)了一定的困難。一種較為直接的解決方案是進(jìn)行主圖規(guī)模約束,即為主圖的結(jié)點(diǎn)數(shù)量設(shè)定一個(gè)最大值,從而使主圖的規(guī)模不會(huì)在推導(dǎo)過(guò)程中無(wú)限制增加。然而,這種方案依然存在著不足之 處。如 圖3 所 示,標(biāo)號(hào)為“begin”、“end”、“statement”的結(jié)點(diǎn)為終結(jié)點(diǎn),標(biāo)號(hào)為“stat”的結(jié)點(diǎn)是非終結(jié)點(diǎn)。在該情況下,若設(shè)定主圖的規(guī)模不能大于4,則無(wú)論使用哪一條產(chǎn)生式進(jìn)行推導(dǎo)都會(huì)導(dǎo)致規(guī)模超過(guò)4。若將當(dāng)前主圖作為輸出,由于存在非終結(jié)點(diǎn)“stat”,因此不符合語(yǔ)法上圖句子的概念。針對(duì)該問(wèn)題,為每個(gè)非終結(jié)點(diǎn)增加終結(jié)產(chǎn)生式。具體而言,由于每個(gè)非終結(jié)點(diǎn)都是一個(gè)子結(jié)構(gòu)的抽象,因此將每個(gè)非終結(jié)點(diǎn)作為一個(gè)產(chǎn)生式的左端,右端為其終結(jié)形式。例如,在圖4 中產(chǎn)生式p3 是一個(gè)終結(jié)產(chǎn)生式,其右端是左端非終結(jié)點(diǎn)的終結(jié)形式。需要注意的是,為了應(yīng)對(duì)不同上下文,每個(gè)終結(jié)產(chǎn)生式(初始圖為左端以及改進(jìn)前存在的產(chǎn)生式除外)的懸邊均使用通配懸邊的形式,即在主圖中可以匹配任意數(shù)量的邊。如圖4 所示,在限制主圖規(guī)模不大于4 的情況下,使用終結(jié)產(chǎn)生式p3 可以生成所有結(jié)點(diǎn)均為終結(jié)點(diǎn)的主圖。
圖3 EGG 遞增約束Fig.3 Size-increasing restriction of EGG
圖4 終結(jié)產(chǎn)生式的應(yīng)用Fig.4 Application of terminal productions
在推導(dǎo)的自動(dòng)化過(guò)程中還存在產(chǎn)生式和圖柄的選擇問(wèn)題。由于推導(dǎo)不需要?dú)w約過(guò)程中的窮舉和回溯,為每個(gè)產(chǎn)生式p 綁定一個(gè)應(yīng)用概率a,而同一個(gè)產(chǎn)生式的不同圖柄具有相等的替換概率。具體而言:在一個(gè)文法中,具有相同左端的不同產(chǎn)生式概率之和等于1,而不同左端的產(chǎn)生式組具有相等的總應(yīng)用概率。例如,圖5 是一個(gè)由4 個(gè)EGG 產(chǎn)生式構(gòu)成的文法,其中產(chǎn)生式p2、p3、p4 具有相等的左端,它們的應(yīng)用概率之和等于1,而p1 是唯一包含初始圖λ為左端的產(chǎn)生式,因此產(chǎn)生式p1 的應(yīng)用概率等于1。具有相同左端不同產(chǎn)生式的具體概率可以通過(guò)先驗(yàn)知識(shí)或者圖數(shù)據(jù)學(xué)習(xí)而來(lái)。由于實(shí)例產(chǎn)生式所描述對(duì)象為程序流程圖,在語(yǔ)法結(jié)構(gòu)上可以分為順序、選擇、循環(huán)3 種具備同等重要性的基本結(jié)構(gòu),因此假定相同左端的產(chǎn)生式在設(shè)計(jì)階段具有相等的初始概率,而實(shí)際應(yīng)用概率可以根據(jù)具體場(chǎng)景以及統(tǒng)計(jì)數(shù)據(jù)進(jìn)行調(diào)整。此外,由于推導(dǎo)過(guò)程中匹配的是產(chǎn)生式左端,因此在產(chǎn)生式設(shè)計(jì)時(shí)應(yīng)盡可能減少左端結(jié)點(diǎn)數(shù)量,以提高圖柄查找效率。
給定一個(gè)文法,經(jīng)過(guò)上述的改進(jìn)操作后,便可以執(zhí)行圖自動(dòng)推導(dǎo)算法,如算法1 所示。具體而言,輸入主圖G、產(chǎn)生式集合P、初始圖λ以及圖樣本最大結(jié)點(diǎn)數(shù)m,輸出一個(gè)樣本圖,算法執(zhí)行過(guò)程可以大致分為以下4 步:
步驟1判斷G中所有結(jié)點(diǎn)是否均為終結(jié)點(diǎn),如果所有結(jié)點(diǎn)均為終結(jié)點(diǎn)則返回主圖;如果所有結(jié)點(diǎn)均不符合要求,則執(zhí)行步驟2。
步驟2對(duì)產(chǎn)生式集合P中每一個(gè)滿足GsizepL.size+pR.size≤m的產(chǎn)生式,查找其左端在主圖中的圖柄:如果所有產(chǎn)生式均滿足要求,則在產(chǎn)生式附加屬性RedexSet 中記錄產(chǎn)生式的圖柄,并在MatchedPSet集合中記錄該產(chǎn)生式,執(zhí)行步驟3;如果所有產(chǎn)生式均不滿足要求,則輸入文法錯(cuò)誤,算法終止。
步驟3在MatchedPSet 集合中根據(jù)產(chǎn)生式應(yīng)用概率挑選一個(gè)產(chǎn)生式及其圖柄,執(zhí)行步驟4。
步驟4根據(jù)選中的產(chǎn)生式及圖柄對(duì)主圖執(zhí)行L-application 操作,并返回步驟1。
算法1圖自動(dòng)推導(dǎo)算法
定理1基于EGG 圖自動(dòng)推導(dǎo)算法的圖樣本生成方法的最壞時(shí)間復(fù)雜度為O(ml+1),其中,m是圖樣本的最大規(guī)模,l是產(chǎn)生式左端的最大結(jié)點(diǎn)數(shù)。
證明首先,循環(huán)Loop 1 和Loop 3 均需要|P|次迭代,|P|是產(chǎn)生式數(shù)量,Loop 2 需要m次迭代;其次,在Loop 1 和Loop 2 中,循環(huán)體一次執(zhí)行需要的計(jì)算次數(shù)分別為常數(shù)c1和c2,在Loop 3 中,函數(shù)FindRedex()從規(guī)模為m的主圖中為規(guī)模為l的左圖查找圖柄,最多需要次計(jì)算,循環(huán)體內(nèi)其余代碼開(kāi)銷為常數(shù)c3;函數(shù)L-application()用產(chǎn)生式右端替換圖柄,最多需要m次計(jì)算,剩下代碼的開(kāi)銷為常數(shù)c4;最后,該算法是一個(gè)遞歸函數(shù),由于產(chǎn)生式規(guī)模遞增約束,該函數(shù)的最大遞歸次數(shù)為2m-1,其中,m-1 次遞歸用于增加結(jié)點(diǎn),m次遞歸用于非終結(jié)點(diǎn)到終結(jié)點(diǎn)的轉(zhuǎn)換。綜上所述,所提方法的最壞時(shí)間復(fù)雜度可表示如下:
由于產(chǎn)生式集是在設(shè)計(jì)階段確定的,其產(chǎn)生式數(shù)量|P|在推導(dǎo)階段可以看作一個(gè)常數(shù),因此時(shí)間復(fù)雜度t=O(|P|×ml+1)=O(ml+1),證明結(jié)束。
通過(guò)上述證明過(guò)程可以發(fā)現(xiàn),所提方法的時(shí)間開(kāi)銷在一定程度上受到產(chǎn)生式數(shù)量|P|的影響,因此終結(jié)產(chǎn)生式的增加帶來(lái)了額外的時(shí)間開(kāi)銷,然而并沒(méi)有影響其數(shù)量級(jí)。此外,終結(jié)產(chǎn)生式的最大數(shù)量是非終結(jié)點(diǎn)的數(shù)量,而抽象自子結(jié)構(gòu)的非終結(jié)點(diǎn)的數(shù)量通常小于語(yǔ)義信息更豐富的終結(jié)點(diǎn),因此文法中終結(jié)產(chǎn)生式在產(chǎn)生式組中的數(shù)量占比通常也較小。表1 列出了所提方法和5 種常見(jiàn)圖樣本生成方法的時(shí)間復(fù)雜度。由于左端結(jié)點(diǎn)數(shù)量大于等于1,因此所提方法的時(shí)間復(fù)雜度大于等于Erdos-Renyi[6]、Barabasi-Albert[7]、Watts-Strogatz[8]和GraphRNN[9]且大于GRANs[10]。然而,由于產(chǎn)生式左圖結(jié)點(diǎn)數(shù)在推導(dǎo)階段是一個(gè)常數(shù),所提方法的時(shí)間復(fù)雜度仍然位于多項(xiàng)式級(jí)。與之相比,圖文法歸約算法則多數(shù)需要指數(shù)級(jí)的時(shí)間開(kāi)銷,根本原因在于歸約中產(chǎn)生的大量回溯,而推導(dǎo)過(guò)程并不存在一個(gè)具體的目標(biāo)圖,因而避免了回溯的發(fā)生。此外,若按照上下文無(wú)關(guān)文法的要求設(shè)計(jì)產(chǎn)生式,即產(chǎn)生式左端有且只有一個(gè)非終結(jié)點(diǎn),則所提方法的時(shí)間復(fù)雜度可進(jìn)一步降為O(m2),與Erdos-Renyi、Barabasi-Albert、Watts-Strogatz 以 及GraphRNN 方法相等。
表1 不同圖樣本生成方法的時(shí)間復(fù)雜度比較Table 1 Comparison of time complexity of different graph sample generation methods
本節(jié)給出一個(gè)將EGG 圖自動(dòng)推導(dǎo)算法應(yīng)用在程序流程圖樣本生成中的實(shí)際案例。選擇程序流程圖作為案例的原因在于:程序流程圖是一種較典型的可視化語(yǔ)言,包含了多數(shù)可視化語(yǔ)言所依賴的順序、選擇、循環(huán)3 種控制結(jié)構(gòu)。圖6 是一組用于描述程序流程圖的EGG 產(chǎn)生式,其中,非終結(jié)點(diǎn)的標(biāo)號(hào)為{λ,stat},終結(jié)點(diǎn) 的標(biāo)號(hào) 為{begin,end,if,endif,while,endwhile,T-loop,T-fork,statement}。由于產(chǎn)生式中不存在非終結(jié)點(diǎn)“λ”(文法初始圖)的終結(jié)產(chǎn)生式,因此在文法改進(jìn)時(shí)增加一條終結(jié)產(chǎn)生式,如圖7 所示。
圖6 一組描述程序流程圖的EGG 產(chǎn)生式Fig.6 A group of EGG productions for program flowchart
圖7 增加的終結(jié)產(chǎn)生式Fig.7 Added terminal production
使用上述產(chǎn)生式可以執(zhí)行EGG 圖自動(dòng)推導(dǎo)算法,從而生成限制規(guī)模下(在該模塊中規(guī)模為10)的程序流程圖樣本。如圖8 所示(彩色效果見(jiàn)《計(jì)算機(jī)工程》官網(wǎng)HTML 版),在EGGSS 環(huán)境中開(kāi)發(fā)了一個(gè)新模塊用于演示該過(guò)程,其中在每一步推導(dǎo)過(guò)程中可以通過(guò)點(diǎn)擊“隨機(jī)選擇產(chǎn)生式”按鈕隨機(jī)選擇一條左端在主圖中存在圖柄的產(chǎn)生式,點(diǎn)擊“隨機(jī)圖柄”按鈕可以隨機(jī)選擇一個(gè)圖柄,并用紅色邊框標(biāo)識(shí)該圖柄,隨后點(diǎn)擊下一步按鈕可以執(zhí)行L-application,生成一個(gè)規(guī)模不大于10 的新主圖。圖9 是在該模塊下使用圖6 和圖7 產(chǎn)生式推導(dǎo)生成的一組程序流程圖樣本,其中每個(gè)結(jié)點(diǎn)都是終結(jié)點(diǎn)且每個(gè)圖的規(guī)模(即結(jié)點(diǎn)數(shù)量)不超過(guò)10。
圖8 一個(gè)程序流程圖樣本的生成過(guò)程Fig.8 Generation process of a program flowchart sample
圖9 一組程序流程圖樣本Fig.9 A group of program flowchart samples
在未涉及先驗(yàn)知識(shí)和統(tǒng)計(jì)數(shù)據(jù)的情況下,相同左端不同產(chǎn)生式的應(yīng)用概率具有相等的初始值。例如,在圖6 中每個(gè)產(chǎn)生式左端為“stat”結(jié)點(diǎn)產(chǎn)生式的應(yīng)用概率均為1/6≈16.67%。為了根據(jù)實(shí)際應(yīng)用場(chǎng)景及時(shí)調(diào)整應(yīng)用概率,通過(guò)該模塊推導(dǎo)出了100 個(gè)圖樣本,并對(duì)其圖樣本規(guī)模(即結(jié)點(diǎn)數(shù)量)分布進(jìn)行統(tǒng)計(jì)與分析。如圖10(a)所示,53%的圖樣本規(guī)模等于1,即僅通過(guò)圖7 中終結(jié)產(chǎn)生式執(zhí)行一次推導(dǎo)操作生成了只包含終結(jié)點(diǎn)“empty”的圖,而在剩下47 個(gè)圖樣本中包含規(guī)模為3 的圖樣本的比例為21/47≈44.68%,即初始圖在使用圖6 中產(chǎn)生式p1 進(jìn)行推導(dǎo)后,直接使用p5、p6、p7 中的任意一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)而生成的圖樣本。顯然,該分布情形與多數(shù)實(shí)際工程不符:首先工程中通常不存在如此高比例的空程序(僅含結(jié)點(diǎn)“empty”的流程圖);其次在規(guī)模限制為10 的情況下,規(guī)模不大于3 的圖樣本比例達(dá)到了74%,樣本的平均規(guī)模過(guò)小,僅為3.16??傮w而言,出現(xiàn)上述現(xiàn)象的原因在于:
圖10 圖樣本規(guī)模分布Fig.10 Size distribution of graph samples
1)在圖6 和圖7 中左端為初始圖λ的產(chǎn)生式僅有2 個(gè),它們的應(yīng)用概率分別為50%,導(dǎo)致推導(dǎo)出50%左右的單結(jié)點(diǎn)樣本。
2)當(dāng)初始圖通過(guò)產(chǎn)生式p1 推導(dǎo)出規(guī)模為3 的主圖時(shí),下一步推導(dǎo)可以使用所有左端為“stat”結(jié)點(diǎn)的產(chǎn)生式(數(shù)量為6),每個(gè)產(chǎn)生式的應(yīng)用概率為1/6≈16.67%,而在這些產(chǎn)生式中可以直接將“stat”結(jié)點(diǎn)轉(zhuǎn)換成終結(jié)點(diǎn)的產(chǎn)生式有3 個(gè)(p5、p6、p7),因此在它們應(yīng)用概率相等的情況下這一步生成圖規(guī)模為3 的概率達(dá)到(1/6)×3=50%。
上述問(wèn)題可以通過(guò)調(diào)整產(chǎn)生式應(yīng)用概率來(lái)解決。一方面大幅度降低圖7 中終結(jié)產(chǎn)生式的應(yīng)用概率,在左端為λ的產(chǎn)生式中,將產(chǎn)生式p1 的應(yīng)用概率從50%調(diào)整為90%,而終結(jié)產(chǎn)生式的應(yīng)用概率從50%降為10%;另一方面適當(dāng)降低產(chǎn)生式p5、p6、p7的應(yīng)用概率,在左端為結(jié)點(diǎn)“stat”的產(chǎn)生式中,將p2、p3、p4 的應(yīng)用 概率分別從1/6≈16.67% 調(diào)整為25%,產(chǎn)生式p5、p6、p7 的應(yīng)用概率從1/6≈16.67%分別降為1/12≈8.33%。圖10(b)描述了根據(jù)調(diào)整后應(yīng)用概率進(jìn)行推導(dǎo)所生成的圖樣本規(guī)模分布,可以看出規(guī)模為1 的圖樣本比例從53%降為9%,規(guī)模為3 的圖在規(guī)模2~9 中的圖樣本比例也由原來(lái)的接近21/47≈44.68%降到了24/91≈26.37%左右,圖樣本的平均規(guī)模也由3.16 增長(zhǎng)至6.87。若實(shí)際需求場(chǎng)景要求圖樣本的平均規(guī)模進(jìn)一步增加,則可按照該方式繼續(xù)調(diào)整產(chǎn)生式應(yīng)用概率。
圖文法的應(yīng)用聚焦于圖語(yǔ)法語(yǔ)義的分析,而圖推導(dǎo)工作流僅作為圖語(yǔ)言的形式定義存在,其原因在于推導(dǎo)過(guò)程中存在停機(jī)問(wèn)題以及產(chǎn)生式和圖柄選擇問(wèn)題。本文提出一種基于EGG 圖文法的圖自動(dòng)推導(dǎo)算法,并將其用于圖樣本生成。首先,設(shè)計(jì)一種圖文法改進(jìn)方法,通過(guò)為非終結(jié)符定義終結(jié)產(chǎn)生式解決推導(dǎo)的停機(jī)問(wèn)題。其次,為每個(gè)可匹配的產(chǎn)生式及其圖柄關(guān)聯(lián)概率,這些概率來(lái)自先驗(yàn)知識(shí)或樣本學(xué)習(xí),再根據(jù)這些概率進(jìn)行圖的自動(dòng)推導(dǎo)。分析推導(dǎo)算法的時(shí)間復(fù)雜度得到算法時(shí)間復(fù)雜度是多項(xiàng)式級(jí)的,遠(yuǎn)小于多數(shù)圖文法歸約算法的指數(shù)級(jí)時(shí)間開(kāi)銷。此外,給出一個(gè)在EGGSS 環(huán)境中開(kāi)發(fā)的圖樣本生成模塊,使用該模塊可以有效生成一定規(guī)模內(nèi)的圖樣本,并通過(guò)程序流程圖的樣本生成作為案例演示了推導(dǎo)算法執(zhí)行的詳細(xì)過(guò)程。實(shí)驗(yàn)結(jié)果表明,與其他圖樣本生成方法相比,所提方法具有較高的準(zhǔn)確性,原因在于只要是嚴(yán)格按照產(chǎn)生式推導(dǎo)生成的圖,就一定是產(chǎn)生式所屬文法所定義的語(yǔ)言,并且所提方法非常適用于對(duì)準(zhǔn)確性要求較高的應(yīng)用場(chǎng)景,也可作為傳統(tǒng)統(tǒng)計(jì)方法的一種補(bǔ)充方法使用。
一般特定專業(yè)領(lǐng)域的設(shè)計(jì)人員通常不了解文法產(chǎn)生式,常見(jiàn)的解決方案是提升產(chǎn)生式形式的直觀性,例如形狀文法[26-27]使用形狀作為產(chǎn)生式的基本元素,在建筑分析、場(chǎng)景重構(gòu)以及藝術(shù)設(shè)計(jì)領(lǐng)域取得了廣泛的應(yīng)用[28],然而形狀文法由于格式上不符合圖論定義而不屬于圖文法的范疇,其語(yǔ)法語(yǔ)義的分析能力不足,在未來(lái)研究中將嘗試研究產(chǎn)生式的自動(dòng)提取技術(shù),降低設(shè)計(jì)人員的工作量和難度。此外,需要進(jìn)一步規(guī)范和統(tǒng)一產(chǎn)生式和圖柄的選擇概率及探索基于邏輯的圖文法和機(jī)器學(xué)習(xí)方法的融合應(yīng)用,從而滿足更多實(shí)際應(yīng)用場(chǎng)景的需求。