基于圖文法的邏輯型圖樣本生成方法

劉禹鋒，楊 帆，劉 健

（南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院，南京 210046）

0 概述

圖文法是可視化語(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)題，并可作為一種新型的邏輯型圖樣本生成方法供用戶使用。

1 圖文法

類似于一維字符文法，圖文法可以分為上下文無(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

2 圖樣本生成方法

2.1 圖文法改進(jìn)

如上文所述，產(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ù)量，以提高圖柄查找效率。

2.2 圖自動(dòng)推導(dǎo)算法

給定一個(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)算法

2.3 時(shí)間復(fù)雜度分析

定理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

3 程序流程圖樣本生成案例

本節(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)用概率。

4 結(jié)束語(yǔ)

圖文法的應(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)景的需求。