如何利用正则表达式来处理字符串

正则表达式(regular expression记为RE)常用于文本检索和计算生物学中，它可以表示比单字符串、字符串集合、扩展字符串更复杂的搜索模式。

正则表达式有三种最基本的运算：并、连接、闭包。分别记为“｜”、“.”、“*”。如果RE₁ 和RE₂ 都是正则表达式，则(RE₁ . RE₂)、（RE₁ | RE₂）、（RE₁ *）也都是正则表达式。

如图1是利用正则表达式知识来处理字符串的经典方法。

 

    首先，正则表达式被解析成一棵表达式树，然后将表达式树转换成非确定有限自动机。然后就是5.1节所讲的利用自动机处理字符串。在这里，其实从NFA直接处理也是

可行的，但由于要保存活动状态列表，并且每读入一个新文本字符都要更新这个列表，因此这个算法处理速度通常较慢。

图2是一个正则表达式(AB|BA)(AA)*的解析树表示。

Thompson构造法是一种从正则表达式构造自动机的方法.它使用自动机直接表示一个正则表达式对应的树表示,并且使用 -转移来简化这个表示过程。

Thompson构造法的核心思想是形成正则表达式RE对应的树表示Tre，然后自底向上地对树Tre的每个节点v，构造一个自动机Th(v)来识别以v为根的子树所表达的语言。根据不同类型的中间节点和叶节点，有不同的自动机构造方法，具体情况如下：

①：空字的构造方法。自动机由 -转移连接两个节点而组成。

 

②：单字符a的构造方法，它与空词的构造方法类化，只不过转移是使用字符来标识，而不是空字符串。

 

        ③：连接节点的构造法。瘵两个子节点v_l和v_r 对应的Thompson自动机合并，即第一个自动机和终止状态成为第二个自动机的初始状态。

   

    ④：并节点的构造法：就像电路图中的并联一样，必须通过两个子节点对应的自动机v_l和v_r中的一个。这种构造需要 -转移，在构造中，要添加二个状态，一个初始状态I，从它有二个 -转移分别到Th(vl)和Th(vr)的初始状态；另一个是终止状态F，从自动机Th(vl)和Th(vr)的终止状态分别由 -转移到达终止状态F。

    

     ⑤：星节点的构造法：因为节点的唯一子节点v*可以被重复任意多次，所以需要创建一个从自动机Th(v*)的终止状态指向其初始状态的 -转移。但是，星符号也意味着自动机Th(v*)也可能被忽略。因此，需要创建初始节点I和终结节点F，并用一个 -转移将他们连接起来。另外，再创建两条 -转移分别用来从节点I指向Th(v*)的初始状态以及从Th(v*)的终止状态指向F。如图。

     

 

正则表达式和自动机密切相关，都是处理字符串问题的重要工具。