Ch02 正则表达式 与 自动机

正则表达式（regular expression, RE）：描述文本序列的标准记录方式。在文本检索和信息抽取的各种类型的应用中，都使用正则表达式来描述文本中的符号串。

有限状态自动机（finite state automaton）：不仅是一种用来实现正则表达式的数学工具，也是计算机语言学中最为有用的工具。

正则表达式

正则表达式是一种用于描述文本搜索符号串的语言。是专用语言中用于描述符号串（）的简单类别的一个公式。

• 符号串是符号的序列。对于大多数的基于文本的检索技术来说，符号串就是字母数字字符（字母、数字、空白、表、标点符号）的任意序列。

从形式上讲，正则表达式是用来刻画符号串集合的一个代数表述。

正则表达式的搜索需要提供的数据：搜索的模式（pattern）和被搜索的文本语料库（corpus）。

基本的正则表达式模式

正则表达式是由简单字符构成的一个序列，表达式是区分大小写的。

方括号[]内部的字符符号串表示字符是析取（disjunction）的。

• 连字符-：表示在某一范围内的任何字符。

• 脱字符^：如果是方括号内使用，表示否定后续的模式，即不出现某些字符；如果在方括号外使用，只表示字符本身。

• 通配符（wildcard）：点号.。表示任何与单个字符（回车符除外）相匹配的字符。点号常常与星号共用。

• 计数符：

  • 问号?：表示前面一个字符存在或者不存在。

  • 星号*：称为Kleene *，其前面的字符或正则表达式出现零次或者多次。

  • 加号+：称为Kleene +，其前面的字符或正则表达式出现一次或者多次。

  • 大括号{m,n}：表示前面的字符至少出现m次，至多出现n次。

• 锚号（anchors）：把正则表达式锚在符号串中某个特定位置的特殊字符。

  • 脱字符^：与行的开始相匹配；

  • 美元符$：与行的结束相匹配。

  • \b：表示词界；

  • \B：表示非（不是）词界。

正则表达式的基本算符

析取符（pipe symbol）|：析取算符（disjunction operator）。

圆括号()：表示优先关系。把一个模式括在圆括号中使得它就像一个单独的字符来使用，而且在其中可以使用析取符和 Kleene * 等算符。例如，表达式「gupp(y|ies)」表示析取符仅应用于后缀 y 和 ies。

算符优先层级（operator precedence hierarchy）：圆括号＞计数符＞序列与锚＞析取符

贪心模式：正则表达式尽可能与最长的符号串匹配。

正则表达式的简单例子和复杂例子

错误类型：

• 正面错误（false positives）：错误地匹配的字符串

• 负面错误（false negatives）：错误地遗漏的字符串

处理目标：（两个目标是矛盾的）

• 增加准确率（accuracy）：把正面错误减少到最低限度。

• 增加覆盖率（coverage）：把负面错误减少到最低限度。

正则表达式的高级算符

高级算符可以用简单算符来表达，高级算符可以简化表达式的内容，更加方便阅读和理解。

• \d = [0-9]：任何数字字符

• \D = [^0-9]：任何非数字字符

• \w = [a-zA-Z0-9_]：任何字母字符、数字字符或者空白字符

• \W = [^\w]：一个非字母字符、数字字符或者空白字符

• \s = [ \r \t \n \f]：空白区域（空白字符、制表字符、换行字符、回车字符）

• \S = [^\s]：非空白区域

正则表达式的实际操作

替换（substitution）是正则表达式的用途之一。用正则表达式描述的符号串替换另一个用正则表达式描述的字符串。

在第一个模式的两侧加上圆括号，在第二个模式中使用数字算符（number operator）\1就可以回过头去参照第一个模式，从而实现替换。

数字算符使用数字存储器保存前面的模式，这些数字存储器称为寄存器（registers）。

有限状态自动机（FSA）

正则表达式

• 是一种用于文本搜索的元语言。

• 是描述有限状态自动机（Finite-State Automaton，FSA）的一种方法。

  • FSA 是语言计算的理论基础，任何正则表达式都可以使用有限状态自动机来实现

• 是刻画正则语言（regular language）的一种方法。

  • 正则语言是形式语言中的一种。正则语言可以使用正则表达式、有限状态自动机和正则语法（regular
    grammar）进行描述，即三者是等价的。

FSA的表示方式

自动机（automaton），也叫有限自动机，或者叫有限状态自动机，能够识别由符号串构成的集合。

自动机的表示方法：

• 图表示：结点表示状态，弧表示转移；

• 状态转移表（state-transition table）表示。

自动机需要5个参数实现形式化定义：

• $Q=q_0,q_1,\cdots,q_{N-1}$：$N$ 中状态的有限集合
• $\Sigma$：有限的输入符号字母表
• $q0$：初始状态
• $F$：终极状态集合，$F\subseteq Q$
• $\sigma(q,i)$：状态之间的转移函数或者转移矩阵

D-RECOGNIZE 算法：确定性的识别器。确定性算法是一种没有选择点的算法，对于任何的输入，算法总是知道怎样工作。

FSA 中的形式语言

形式语言（formal language）：是一个模型，这个模型能够而且只能够用来生成或者识别满足形式语言定义所要求的某一种形式语言的符号串。

形式语言是符号串的集合，而每一个符号串是由字母表（alphabet）中的有限的符号的集合组合而成。基于形式语言定义的自动机可以在封闭的形式中表示无限的集合。

生成语法（generative grammar）：表示形式语言的语法，即自动机定义的能够生成一切可能的符号串的语言。

非确定的 FSA（NFSA）

非确定的有限自动机（Non-deterministic FSA，NFSA），一种是带有两难的判定点的自动机，另一种存在概率转移（ε-转移，ε-transition）的有概率的有限自动机（Probabilistic FSA，PFSA），。

相对应的自动机也可以称之为确定的有限自动机（Deterministic FSA，DFSA），当确定的自动机在识别的时候，当它处于某一个状态以及要查找某一个符号时，它的行为是完全确定的。

NFSA 接收符号串

三种非确定问题的解决方案（solution to the problem of non-determinism）：

• 回退（backup）：在选择点做记号，记录位置和状态，当遇到错误的选择时可以回退到选择点，从而试探其他的路径

  • 在每个选择点上，需要记住所有不同的选择

  • 对于不同的选择，需要存储足够的信息，以便在需要的时候返回

  • 结点与位置的结合体称为识别算法的搜索状态（search-state）。

  • 自动机的状态称为结点（node）或者机器状态（machine-state）。

• 前瞻（look-ahead）：在输入中向前看，预测性地判断应该选择哪条路径

• 并行（parallelism）：在选择点上并行探查每条不同的路径。

FSA 识别就是搜索

状态空间搜索（state-space search）算法：系统地探索自动机中所有可能的路径，从而正确地识别正则语言中的符号串。如果探索找到了一条路径以接收状态结束，那么自动机就接收该符号串，否则就拒绝这个符号串。搜索状态包括由机器状态和输入带子上的位置组成的偶对（pairing）。状态空间由给定自动机中一切可能的机器状态和带子位置的偶对所组成。搜索的目标就是从一个状态到另一个状态的探索这个空间，查找出由接收状态和带子位置的终点所组成的偶对。

• 深度优先搜索（depth-first search）策略，即后进先出（Last In First Out，LIFO）策略，使下一次需要考虑的状态成为当前需要处理的状态，把马上需要处理的状态放在进程表的前端，进程表可以用栈（stack）来实现。在某些情况下，可能会导致无限的环路。
  • 一种情况是当状态空间建立时，搜索状态被再次访问
  • 一种情况是存在着无限数目的搜索状态
• 广度优先搜索（breadth-first search）策略，即先进先出（First In First Out，FIFO）策略，按照状态建立时的呔进行处理，把新建立的状态放在进程表的后面，进程表可以用队列（queue）来实现。当状态空间是无限的时候，搜索可能永远无法停止。
• 规模较大的问题，更加复杂的搜索技术：动态规划（dynamic programming）（Ref：Ch13）和 A*搜索算法（Ref：Ch10）。

DFSA与NFSA之间的关系

使用算法可以把 NFSA 转换为等价的 DFSA，因此 NFSA 与 DFSA 是完全等价的。

正则语言与有限状态自动机

正则语言的两个概念：

• 字母表 $\Sigma$，是语言中所有符号的集合
• 空符号串 $\varepsilon$，不能包括在 $\Sigma$ 中；空集 $\Phi$

在 $\Sigma$ 上的正则语言的类（或者正则集）的形式化定义：

• $\Phi$ 是正则语言

• $\forall a\in \Sigma \cup \varepsilon$，${a}$ 是正则语言

• 如果L1和L2是正则语言，那么

  • L1和L2的毗连也是正则语言

  • L1和L2的并或者析取也是正则语言

  • L1的Kleene闭包也是正则语言

正则语言的运算：

• 交：如果L1和L2是正则语言，那么L1 ∩ L2也是正则语言

• 差：如果L1和L2是正则语言，那么L1 - L2也是正则语言

• 补：如果L1是正则语言，那么Σ* - L1也是正则语言

• 逆：如果L1是正则语言，那么L1^(-1)也是正则语言

正则表达式与自动机的等价转换，即正则表达式的每个基本操作都可以通过自动机模拟。

小结

本章重点：有限自动机（finite automaton）和正则表达式（regular expression）。

• 正则表达式语言是模式匹配的有力工具。

• 正则表达式的基本运算

  • 符号的毗连

  • 符号的析取（[]，|，.）

  • 记数符（*，+，{m,n}）

  • 锚号（^，$）

  • 前于运算符（(,)）。

• 正则表达式等价有限状态自动机，任何正则表达式都可以转换为有限自动机。

• 存储器（\1和()）是一种高级运算，经常作为正则表达式的一部分，可以实现替换功能，但是不能实现为有限自动机。

• 形式语言被隐含地定义为在任何的词汇（符号集）中自动机所接收的符号串的集合。

• 确定的自动机（DFSA）的行为完全由它的状态决定。

• 非确定的自动机（NFSA）的行为有时必须在多条路径之间依据概率进行选择。

• 任何一个NFSA都可以转换成为等价的DFSA，即NFSA和DFSA是等价的。

• NFSA的进程表中搜索下一个状态的顺序决定了搜索策略：

  • 深度优先或者后进先出（LIFO）策略相当于把进程表看成堆栈；

  • 广度优先或者先进先出（FIFO）策略相当于把进程表看成队列。

• 任何的正则表达式都可以自动地编译为NFSA，即可以自动地编译为DFSA。