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

基于子结构匹配方法的多规则L系统反演研究Research on the inverse problem of mutil-rules Lindenmayer System based on substructure matching朱元伟摘要:由已知的L系统的结果字符串寻找出原来的初始公理和产生式规则集是L系统反演的主要工作。本文以L系统的自相似特点为基础, 通过子结构的分层匹配算法实现带有两个限定条件的L系统字符串的反演，能够简便准确获取L系统初始公理和产生式规则集。算法主要包含4个步骤:分割最终字符串并建立子结构池;对子结构池中包含其他子结构的字符串进行进一步分割；通过与各层次回溯得到的子结构匹配，取得子结构与产生式前驱之间的对应关系；通过回溯迭代过程得到其最简形式，获得初始字符串；试验中，所有被测试的字符串都可以被反演到等价L系统规则集。关键词: L系统;虚拟植物; L系统反演;子结构匹配AbstractFinding out theset of originalrules is the main work of the inversionof Lindermayer system.The algorithm of this paper obtain a set of rules from a long Lindenmayer string with two conditions by matching sub-structures. The algorithm consists of five steps：divide the Lindenmayer string into substrings recursively and push them into the sub-structure buffer pool;further divide the sub-structure which contains others in the pool;replace the sub-structures in Lindenmayer by the identifier in the pool then do repeat as in the previous step.Using the newly obtained sub-structure match structures in buffer pool to get the map relationship between sub-structures and predecessors; replacing repeated string with a predecessor char that marking the same string in the pool, and continuing this process recursively until get the original axiom. In the tests carried out, all the Lindenmayer strings could be reverted to a set of Lindenmayer rules that identical to the original rules used to generate the string.Key-words：L-system; virtualplant; Inverse problems; substructure matching Problems 引言：L系统不仅被用于植物的形态模拟 1，还被用于数据压缩2、加密解密34、音乐生成5 6、IP网络流量工程（Traffic engineering of IP networks）7等领域。这些问题都需要用到L系统的反演过程。自L系统1968年诞生以来8,其有诸多学者研究了其反演过程。其中，在文9提出GLP（Genetic L-System Programming）思想之后，文10111213通过GLP对特定植物结构形态的L系统反演进行了有益的探索。但GLP需要大量计算、比较，结果也具有不稳定性。文14则提出一种基于统计规律的方法。统计方法可以显著减少计算量，但作者提出的算法只能应用于单符号的二维DOL系统。文15提出了基于裂解法获取L系统初始公理和产生式集合的方法。裂解法具有较好的精度，但需要经过复杂的裂解过程，只能处理容量不大的数据, 要将这些结果组织为可以识别的形式还需某些额外的开销。文16对单个产生式的DOL系统提出了一种通过回溯迭代过程获得初始公理和产生式组的方法。这种方法具有比较高的效率，但是只能解决单个产生式规则的情况。本文受植物结构自相似特点的启发，提出了一种子结构分层匹配的算法。该方法充分利用L系统整体结构与子结构的相似性，可以在不考虑迭代次数的情况下，寻找到具有等价效果的多规则L系统的产生式规则集。最后，本文给出了一个算法的应用举例。1.L系统基础。L 系统是由一条初始公理和若干条产生式规则组成的并行重写系统,能够很好的描述具有自相似特征的植物的拓扑结构和生长规律。 L系统有多种类型，主要有DOL系统、随机L系统、参数L系统、微分L系统以及上下文相关 L 系统等。下面以DOL系统为例说明其基本原理，一个DOL系统是一个三元式：L=V是一个字母表，V中的元素用来组成表示图形命令的字符串；是初始公理，用以确定L系统及其对应图形的起始状态，并且V；P是产生式的有限集合，形式为a-x，分别称字符a和字符串x为产生式的前驱和后继。如果没有明确的为av指定重写产生式，则a-a，且产生式(a，a)P。L系统从一个初始公理开始，应用产生式规则进行有限次，最终得到一个表达分形图的字符串。例如：初始公式：F产生式 P：F-F-F+FF表一 L系统的迭代过程示例迭代步数迭代结果0F1F-F+FF2F-F+FF-F-F+FF+F-F+FF F-F+FF3F-F+FF-F-F+FF+F-F+FFF-F+FF-F-F+FF-F-F+FF+F-F+FFF-F+FF+F-F+FF-F-F+FF+F-F+FFF-F+FFF-F+FF-F-F+FF+F-F+FFF-F+FF为使获得的最终字符串能描绘出图形，需要对其进行适当的几何解释，即对字符串中的每个字符赋予一个特定的图形含义。最常用的方法称为“龟图解释”。二维平面上的龟图解释通常会将字符定义为表二的动作: 表 二 龟图解释中字符对应的动作字符动作说明F龟向前移动一步，步长为d，并从原先位置到当前位置画一直线。d 为预先定义的一个步长长度。+前进方向逆时针旋转。为预先定义的角度。-前进方向顺时针旋转。将当前状态压入堆栈。当前状态一般包括位置和前进方向从堆栈中弹出一个状态作为当前状态。图1是在角度=30，迭代次数n=0,1,2时，使用如下初始公式和产生式所生成的图形。初始公理：F产生式 P：F-F-F+FF n=0 , =30 n=1 , =30 n=2 , =30图一 ，L系统产生的图形示例2.L系统的图形子结构与字符串子结构 子结构是个相对的概念 ,也是个递归的概念，植物主干上的一个侧枝便是植物的一个子结构。文献17中最早提出子结构思想。现在学者多将子结构算法作为一种提高计算机的仿真速度的途径。其算法是首先产生一个(对于确定性L系统)或若干个(对于随机L系统)具有相同属性的子结构，当这些子结构出现在其他子结构中时，不需要重复计算，直接使用已有的子结构中的信息18。子结构在图形表现为上植物的分支结构，在图形对应的字符串上则表现为这个字符串的一个子串。例如：图2（b）是图2（a）的子结构。对应的字符串为（一个连续的下划线表示一个子结构）：F-F+FF-F-F+FF+F-F+FFF-F+FF - F-F+FF-F-F+FF+F-F+FFF-F+FF+ F-F+FF-F-F+FF+F-F+FFF-F+FFF-F+FF-F-F+FF+F-F+FFF-F+FF图2（c）是图2（b）的子结构，对应的字符串为（一个连续的下划线表示一个子结构）：F-F+FF-F-F+FF+F-F+FFF-F+FF (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）操作，将得到的关于Pi的字符串放入缓冲池中；根据各个子结构非终结符个数和对应的”“,”,”+”,”-”字符位置匹配缓冲池中的子结构。如果匹配成功，则可以通过位置对应确定可迭代字符与最小子结构的对应关系。如果不成功，说明当前得到的子结构是比缓冲池中已有子结构更小的单元。转到（2）操作，将原有子结构进一步分解为更小的结构。4. 回溯迭代过程，获得初始公理。由于已经获得了组成当前字符串S的各个临时产生式后继，可以通过递归方法，把当前字符串按（1）进行分割，通过与子结构池中匹配，替换为相应非终结符的方法进行回溯。当回溯结果只有一层括号并且不能在子结构池中匹配到相同结构时停止，这个字符串就是初始公理。5. 通过上述步骤完整的获得了初始公理和产生式组。在算法步骤（1）中，由定理二可以得到其S字符串的最小子结构或者最小子结构的组合。而步骤（2）对包含另一个子结构的子结构字符串进行分割。步骤（3）（4）则进一步分割包含在回溯过程中产生的新字符串的子结构字符串。由限制条件2以及定理1可知，缓冲池中的字符串已经包含所有的产生式后继，所以回溯过程中获得的子结构一定是缓冲池中的结构或者是缓冲池中结构的子结构。通过匹配、分拆，最终可得到一个可产生被反演字符串S的产生式规则集合。4.应用实例需要反演的字符串：F-F+FF-F-F+FF+F-F+FFF-F+FF+F-F+FF-F-F+FF+F-F+FFF-F+FFF-F+FF+F-F+FFF+FXF-X+FXF-F+FF-F+FXF-X+FX+F-F+FFF+FXF-X+FXF-F+FF-F-F+FF+F-F+FFF-F+FF-F-F+FF+F-F+FFF+FXF-X+FXF-F+FF-F+FXF-X+FX+F-F+FFF+FXF-X+FX+F-F+FF-F-F+FF+F-F+FFF-F+FFF-F+FF+F-F+FFF+FXF-X+FXF-F+FF-F+FXF-X+FX+F-F+FFF+FXF-X+FX（1）将字符串S按照括号层次进行递归分割为子结构之后的结果。“，”为分隔符。F-F+FF，-F-F+FF，+F-F+FF，F-F+FF+F-F+FF，-F-F+FF，+F-F+FF，F-F+FFF-F+FF，+F-F+FFF+FXF-X+FX，F-F+FF，-F+FXF-X+FX，+F-F+FFF+FXF-X+FX，F-F+FF，-F-F+FF，+F-F+FF，F-F+FF-F-F+FF，+F-F+FFF+FXF-X+FX，F-F+FF，-F+FXF-X+FX，+F-F+FFF+FXF-X+FX，+F-F+FF，-F-F+FF，+F-F+FF，F-F+FFF-F+FF，+F-F+FFF+FXF-X+FX，F-F+FF，-F+FXF-X+FX，+F-F+FFF+FXF-X+FX子结构标识字符串非终结符个数最小子结构序列P1F-F+FF4P1P2F-F+FFF-F+FF8P2P3F-F+FF F+FXF-X+FX11P3P4F+FXF-X+FX7P4用缓冲池中标识替换对应字符串后的结果：P1，-P1，+P1，P1+P1，-P1，+P1，P2，+P3，P1，-P4，+P3，P1，-P1，+P1，P1-P1，+P3，P1，-P4，+P3，+P1，-P1，+P1，P2，+P3，P1，-P4，+P3。（2）最小子结构判别之后的缓冲池状态。子结构标识字符串非终结符个数最小子结构序列P1F-F+FF4P1P2F-F+FF F-F+FF8P1P1P3F-F+FF F+FXF-X+FX11P1P4P4F+FXF-X+FX7P4只由最小子结构组成的字符串SS：P1-P1+P1P1+P1-P1+P1P1P1+P1P4P1-P4+ P1P4P1-P1+P1P1-P1+P1P4P1-P4+P1P4+P1-P1+P1P1 P1+P1P4P1-P4+ P1P4。（3）获取SS中最小子结构并且经过判别之后的缓冲池状态。子结构标识字符串非终结符个数最小子结构序列P1F-F+FF4P1P2F-F+FF F-F+FF8P1P1P3F-F+FF F+FXF-X+FX11P1P4P4F+FXF-X+FX7P4P5P1-P1+P1P14P5P6P1+P1P4P1-P4+P1P47P6通过匹配可得P1-P1+P1P1 对应于F-F+FF，P1+P1P4P1-P4+P1P4对应于F-F+FF F+FXF-X+FX。通过取对应位置的字符，可知道 子结构P1的前驱为F，P4的前驱为X。所以获得的产生式组为：F-F-F+FF,X- F+FXF-X+FX。（4）获得初始公理的回溯过程。在（3）步骤中，已经获得了第一次回溯结果，将Pi替换为对应的字符得到：F-F+FF+F-F+FFF+FXF-X+ FXF-F+FF-F+FXF-X+FX+F-F+FF F+FXF-X+ FX。第二次回溯结果：F+FXF-X+FX第三层回溯结果：X第三次回溯只有一个字符，所以初始公理为 X。通过上述的步骤，获得的示例的初始公理和产生式组为：初始公理：X产生式：F-F-F+FF,X- F+FXF-X+FX。5.结论本文提出的将不同层次的子结构进行匹配、分拆成临时最小子结构，并通过回溯得到最初公理。算法既利用了L系统树形结构的自相似特点识别最小子结构，又利用了子结构匹配中的计算的简单快捷。对多规则L系统的反演具有非常。但需要注意的是通过本文算法得到的不一定是原L系统规则集，而是其等价L系统。今后的工作包括：更宽松限定条件的L系统字符串的反演；三维L系统字符串的反演；以及将反演算法应用于对现实中树形结构L系统产生式的自动获取过程。参考文献：1 胡包钢，赵星，严红平植物生长建模与可视化-回顾与展望J自动化学报，2001，27(6)：819-8212 Nevill-Manning, C.G., Witten, Ian H. Identifying Hierarchical Structure in Sequences: A linear-time algorithm. Journal of Articial Intelligence Re-search 7, 6782, 1997.3 A.Salomaa,S.Yu.: On a public-key cryptosystem based on iterated morphisms and substitutions. Theoretical Computer Science,1986,283-296.4 谭敬潘, 基于L系统的公钥密码体制的密钥生成和存储技术研究G,中山大学,2008.5 P. Prusinkiewicz, “Score generation with L-systems,”Proceedings of the 1986 International Computer Music Conference, 1986. 455457.6 B. F. Lourenco, J. C. L. Ralha, M. C. P. Brandao,L-Systems, Scores, and Evolutionary Techniques,Proceedings of 6th Sound and Music Computing Conference, Portugal, 2009, 113-118.7 Salvador, P., Nogueira, A., Valadas, R.: Modeling multifractal IPtraffic: Characterization of packet arrivals and packet sizes using stochastic L-Systems. In: 10th International Conference on Telecommunication Systems, Modeling and Analysis, 577587 (2002)8 Lindenmay AMathematical models for cellular interaction in development，Parts I andIIJJournal ofTheoretical Biology,1968,18:280-315.9 Jacob, C. Genetic L-System Programming: Breeding and Evolving Articial Flowers with Mathematica, IMS 95, Proc. First International Mathematica Symposium, Southampton, Great Britain,ComputationalMechanics Publications, Southampton, UK, pp. 215-222, 1995.10Humera Farooq, M.Nordin Zakaria, Mohd. Fadzil Hassan, and Suziah Sulaiman,:An Approach to Derive Parametric L-System Using Genetic Algorithm.H. Badioze Zaman et al. (Eds.): IVIC 2009, LNCS 5857, pp. 455466, 2009. Springer-Verlag Berlin Heidelberg 200911D.wang, D.J.Kerbyson, G.J.King, G.R.Nudd.: Realistic image synthesis of plant structures for genetic analysis.Image and Vision Computing 19(2001) 517-522.12 Runqiang Bian, Jim Hanan, Norishige Chiba,Statistical data directed evolution of L-system models for botanical trees,4th International Workshop on Functional-Structural Plant