基于子结构匹配方法的多规则L系统反演研究

基于子结构匹配方法的多规则L系统反演研究Researchontheinverseproblemofmutil-rulesLindenmayerSystembasedonsubstructurematching朱元伟摘要:由已知的L系统的结果字符串寻找出原来的初始公理和产生式规则集是L系统反演的主要工作。本文以L系统的自相似特点为基础,通过子结构的分层匹配算法实现带有两个限定条件的L系统字符串的反演，能够简便准确获取L系统初始公理和产生式规则集。算法主要包含4个步骤:分割最终字符串并建立子结构池;对子结构池中包含其他子结构的字符串进行进一步分割；通过与各层次回溯得到的子结构匹配，取得子结构与产生式前驱之间的对应关系；通过回溯迭代过程得到其最简形式，获得初始字符串；试验中，所有被测试的字符串都可以被反演到等价L系统规则集。关键词:L系统;虚拟植物;L系统反演;子结构匹配Abstract—FindingoutthesetoforiginalrulesisthemainworkoftheinversionofLindermayersystem.ThealgorithmofthispaperobtainasetofrulesfromalongLindenmayerstringwithtwoconditionsbymatchingsub-structures.Thealgorithmconsistsoffivesteps：dividetheLindenmayerstringintosubstringsrecursivelyandpushthemintothesub-structurebufferpool;furtherdividethesub-structurewhichcontainsothersinthepool;replacethesub-structuresinLindenmayerbytheidentifierinthepoolthendorepeatasinthepreviousstep.Usingthenewlyobtainedsub-structurematchstructuresinbufferpooltogetthemaprelationshipbetweensub-structuresandpredecessors;replacingrepeatedstringwithapredecessorcharthatmarkingthesamestringinthepool,andcontinuingthisprocessrecursivelyuntilgettheoriginalaxiom.Inthetestscarriedout,alltheLindenmayerstringscouldberevertedtoasetofLindenmayerrulesthatidenticaltotheoriginalrulesusedtogeneratethestring.Key-words：L-system;virtualplant;Inverseproblems;substructurematchingProblems引言：L系统不仅被用于植物的形态模拟[1]，还被用于数据压缩[2]、加密解密[3][4]、音乐生成[5][6]、IP网络流量工程（TrafficengineeringofIPnetworks）[7]等领域。这些问题都需要用到L系统的反演过程。自L系统1968年诞生以来[8],其有诸多学者研究了其反演过程。其中，在文[9]提出GLP（GeneticL-SystemProgramming）思想之后，文[10][11][12][13]通过GLP对特定植物结构形态的L系统反演进行了有益的探索。但GLP需要大量计算、比较，结果也具有不稳定性。文[14]则提出一种基于统计规律的方法。统计方法可以显著减少计算量，但作者提出的算法只能应用于单符号的二维DOL系统。文[15]提出了基于裂解法获取L系统初始公理和产生式集合的方法。裂解法具有较好的精度，但需要经过复杂的裂解过程，只能处理容量不大的数据,要将这些结果组织为可以识别的形式还需某些额外的开销。文[16]对单个产生式的DOL系统提出了一种通过回溯迭代过程获得初始公理和产生式组的方法。这种方法具有比较高的效率，但是只能解决单个产生式规则的情况。本文受植物结构自相似特点的启发，提出了一种子结构分层匹配的算法。该方法充分利用L系统整体结构与子结构的相似性，可以在不考虑迭代次数的情况下，寻找到具有等价效果的多规则L系统的产生式规则集。最后，本文给出了一个算法的应用举例。1.L系统基础。L系统是由一条初始公理和若干条产生式规则组成的并行重写系统,能够很好的描述具有自相似特征的植物的拓扑结构和生长规律。L系统有多种类型，主要有DOL系统、随机L系统、参数L系统、微分L系统以及上下文相关L系统等。下面以DOL系统为例说明其基本原理，一个DOL系统是一个三元式：L=V，ω，PV是一个字母表，V中的元素用来组成表示图形命令的字符串；ω是初始公理，用以确定L系统及其对应图形的起始状态，并且ω∈V；P是产生式的有限集合，形式为a-x，分别称字符a和字符串x为产生式的前驱和后继。如果没有明确的为a∈v指定重写产生式，则a-a，且产生式(a，a)∈P。L系统从一个初始公理开始，应用产生式规则进行有限次，最终得到一个表达分形图的字符串。例如：初始公式ω：F产生式P：F-F[-F][+F]F表一L系统的迭代过程示例迭代步数迭代结果0F1F[-F][+F]F2F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F3F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F[-F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F][+F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F]F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F为使获得的最终字符串能描绘出图形，需要对其进行适当的几何解释，即对字符串中的每个字符赋予一个特定的图形含义。最常用的方法称为“龟图解释”。二维平面上的龟图解释通常会将字符定义为表二的动作:表二龟图解释中字符对应的动作字符动作说明F龟向前移动一步，步长为d，并从原先位置到当前位置画一直线。d为预先定义的一个步长长度。+前进方向逆时针旋转δ°。δ为预先定义的角度。-前进方向顺时针旋转δ°。[将当前状态压入堆栈。当前状态一般包括位置和前进方向]从堆栈中弹出一个状态作为当前状态。图1是在角度δ=30°，迭代次数n=0,1,2时，使用如下初始公式和产生式所生成的图形。初始公理ω：F产生式P：F-F[-F][+F]Fn=0,δ=30°n=1,δ=30°n=2,δ=30°图一，L系统产生的图形示例2.L系统的图形子结构与字符串子结构子结构是个相对的概念,也是个递归的概念，植物主干上的一个侧枝便是植物的一个子结构。文献[17]中最早提出子结构思想。现在学者多将子结构算法作为一种提高计算机的仿真速度的途径。其算法是首先产生一个(对于确定性L系统)或若干个(对于随机L系统)具有相同属性的子结构，当这些子结构出现在其他子结构中时，不需要重复计算，直接使用已有的子结构中的信息[18]。子结构在图形表现为上植物的分支结构，在图形对应的字符串上则表现为这个字符串的一个子串。例如：图2（b）是图2（a）的子结构。对应的字符串为（一个连续的下划线表示一个子结构）：F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F[-F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F][+F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F]F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F图2（c）是图2（b）的子结构，对应的字符串为（一个连续的下划线表示一个子结构）：F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F(a)(b)(c)图二子结构的图形示意图3.多规则L系统的反演方法3.1定义最小子结构：当一个结构不再包含与自己相同形式的子结构时，称为对这个形式的最小子结构。在本文中对应于一个L系统产生式的后继字符串。次最小子结构：与最小子结构对应的，最小子结构通过按一定次序组合产生的子结构。最小子结构的组合：最小子结构对应的字符串通过一定的次序排列而产生的字符串序列。等价L系统：如果两个不同的L系统，通过各自的迭代，可以产生相同的结果字符串，则称这两个L系统为等价L系统。图三最小子结构示意图（椭圆区域为最小子结构）L系统规则的反演是L系统迭代的逆过程。必须指出，不同的L系统规则集合可能推出完全相同的字符串序列。而且,任意非空字符串S,都可以是某个规则集合的结果字符串。只需定义ω:A，A-S，经过一步推导即可。虽然对任意非空串都可以定义逆过程,但它所推得的L系统不惟一，我们的目标是获得一个通过够迭代产生S字符串的产生式规则集合。3.2字符串的反演算法限定条件说明：1.产生式有且只有一层括号，且以非终结符开始。2.在2次迭代字符串中包含所有非终结符，反演字符串是2次迭代以后的结果。因为每个产生式的前驱都会出现在最终字符串中，所以具有如下结论：定理1：L系统迭代的最终字符串，包含所有的最小子结构并且完全是由最小子结构字符串通过组合而成。证明（归纳法）：设iter为迭代次数，S为迭代iter次的结果字符串。则（1）证明当iter=2时满足上述定理。由于iter=1时，S是某个产生式的后继，并且根据限定条件2，包含所有的非终结符。通过并行将所有的非终结符替换为后继，所以iter=2的S包含所有产生式后继，并且完全由产生式后继组合而成。（2）假设当iter=n时满足条件，证明当iter=n+1时也满足条件。因iter=n时，S是由最小子结构组合而成，又因为最小子结构是由产生式前驱构成，并且包含所有非终结符。经过一次迭代产生的iter=n+1的字符串S，则是由非终结符被对应的产生式后继替换而得到，所以iter=n+1时，S是由产生式后继组合而成，并且包含所有的产生式后继。定理2：通过对每层子结构递归使用至少具有两层的括号分割，可以得到完整的最小子结构或者最小子结构的组合。证明：由限定条件可知，所有的产生式括号层次最多为一层。所以至少具有两层的括号内的字符串至少经过了一次替换，括号内所有的非终结符已被替换为完整的最小子结构。同样，由于替换是并行进行的，括号外的非终结符也全部被替换为完整的最小子结构。所以，以至少为两层的括号为界分割的子结构，是完整的最小子结构或者最小子结构的组合。在匹配过程中需要一个子结构缓冲池保存各个阶段产生的子结构字符序列。子结构缓冲池结构如下：子结构标识字符串非终结符个数最小子结构序列多产生式DOL系统字符串的反演算法：1.获取各级子结构中包含的最小子结构以及次小子结构。以高于当前括号层次两层的括号为分割符，递归取分割字符串S；将字符串保存到子结构缓冲池中，同时将原串中对应的字符串用缓冲池中的标识Pi(i=1,2,3...)替换形成字符串SS。2.测试子结构池中的子结构之间的整体包含情况。对缓冲池中的所有字符串Pi（i=1,2,3...）与其他字符串进行包含测试。其中，不包含其他字符串的子结构暂时设定为为最小子结构。通过再次匹配获得其他子结构中的最小子结构组成序列，替换字符串SS中的相应标识，使SS只由临时最小子结构的标识符组成；更改缓冲池中相应的数据。3.通过对由（2）获得SS字符串进一步分割，确定非终结符与最小子结构的对应关系。将字符串SS赋给S，并将分割符去掉。进行（1）（2）操作，将得