计算机科学中文本处理最有用的工具之一是正则表达式（regular expression，简称 regex），它是一种用于描述文本字符串的语言。
正则表达式被广泛应用于各种编程语言、Unix 系统中的文本处理工具（如 grep），以及编辑器（如 vim 或 Emacs）中。
此外，在 BPE 等词元化算法的预词元化（pre-tokenization）阶段，正则表达式也发挥着重要作用。
形式上，正则表达式是一种用于描述字符串集合的代数表示法。
实际上，我们可以用它在文本中搜索某个字符串，并指定如何修改该字符串，这两项功能对词元化至关重要。
我们使用正则表达式在一个字符串（string）中搜索某种模式（pattern），该字符串可以是一行文本，也可以是更长的文本。 例如，Python 函数
re.search(pattern, string)
会扫描 string，并返回其中第一个与 pattern 匹配的内容。
在以下示例中，我们通常会高亮显示与正则表达式完全匹配的字符串，并仅展示第一个匹配结果。
我们将采用 Python 语法，将正则表达式写作由双引号界定的原始字符串（raw string）：r"regex"。
原始字符串会将反斜杠 \ 视为字面字符，这一点很重要，因为我们接下来要介绍的许多正则表达式模式都会用到反斜杠。
正则表达式存在多种变体，因此使用在线正则表达式测试工具可以帮助确认你的正则表达式是否按预期工作。
2.7.1 字符析取：方括号
最简单的正则表达式就是一串普通字符。
模式 r"Buttercup" 会在任意字符串中匹配子串 Buttercup（例如在字符串 I’m called little Buttercup 中）。但很多时候我们需要使用特殊字符。
例如，我们可能希望匹配某一个字符或另一个字符中的任意一个。
通常，正则表达式是区分大小写的：r"s" 能匹配小写字母 s，但不能匹配大写字母 S。
为了同时匹配 s 和 S，我们可以使用字符析取（character disjunction）运算符，即方括号 [ 和 ]。
括号内的字符序列表示一个字符集合，匹配其中任意一个字符即可。
例如，图 2.9 显示，模式 r"[mM]" 可以匹配包含 m 或 M 的字符串。
| 模式 | 匹配内容 | 示例字符串 |
|---|---|---|
r"[mM]ary" | Mary 或 mary | “Mary Ann stopped by Mona’s” |
r"[abc]" | ‘a’、‘b’ 或 ‘c’ | “In uomini, in solda$ti” |
r"[1234567890]" | 任意一位数字 | “plenty of 7 to 5” |
图 2.9 使用方括号 [] 表示字符的析取（即“或”关系）。
正则表达式 r"[1234567890]" 表示任意一位数字。
但这样写很繁琐（试想若要表示大写字母，得写成 r"[ABCDEFGHIJKLMNOPQRSTUVWXYZ]"）。因此，方括号还支持使用连字符（-）来指定一个字符范围。
模式 r"[2-5]" 表示匹配 2、3、4 或 5 中的任意一个字符。
模式 r"[b-g]" 表示匹配 b、c、d、e、f 或 g 中的任意一个字符。
图 2.10 展示了其他一些例子。
| 正则表达式 | 匹配内容 | 匹配示例 |
|---|---|---|
r"[A-Z]" | 一个大写字母 | “we should call it ‘Drenched Blossoms’ ” |
r"[a-z]" | 一个小写字母 | “my beans were impatient to be hoed!” |
r"[0-9]" | 一位数字 | “Chapter 1: Down the Rabbit Hole” |
图 2.10 使用方括号 [] 加连字符 - 来指定字符范围。
方括号还可用于指定某个位置不能出现的字符，方法是在左方括号 [ 后立即使用脱字符（caret）^。
如果 ^ 是左方括号后的第一个符号，则整个模式表示否定（即“除……之外的任意字符”）。
例如，模式 r"[^a]" 匹配任意单个字符（包括特殊字符），但不包括 a。
注意：只有当 ^ 紧跟在 [ 之后时才表示否定；如果出现在其他位置，它就只是字面意义上的脱字符。
图 2.11 给出了一些示例。
| 正则表达式 | 匹配内容（单个字符） | 匹配示例 |
|---|---|---|
r"[^A-Z]" | 非大写字母 | “Oyfn pripetchik” |
r"[^Ss]" | 既不是 ‘S’ 也不是 ‘s’ | “I have no exquisite reason for’t” |
r"[^.]" | 不是句点（.）的字符 | “our resident Djinn” |
r"[e^]" | ‘e’ 或 ‘^’ | “look up ^ now” |
r"a^b" | 字面字符串 ‘a^b’ | “look up a^b now” |
图 2.11 脱字符 ^ 用于否定，或仅表示其字面含义。另见下文关于使用反斜杠转义句点的说明。
2.7.2 计数、可选项与通配符
如果我们想同时匹配 koala 和 koalas，即处理一个可选的 s，该如何表达？
不能使用方括号，因为方括号只能表示“s 或 S”这类字符选择，而无法表示“s 或 无”。为此，
我们使用问号 r"?"，它表示“前一个字符出现一次或不出现”。
因此，r"colou?r" 可以匹配 color 和 colour，而 r"koala?" 可以匹配 koala 或 koalas。
还有一种方式可以描述可能出现也可能不出现的元素。 考虑某种羊的语言，其字符串形式如下：
baa!
baaa!
baaaa!
. . .
这种“羊语言”由以下结构组成：一个 b，后跟至少两个（也可以更多）的 a，最后是一个感叹号。
为了表示这种语言，我们会用到一个非常有用的运算符——星号 *，称为 Kleene 星（Kleene star，通常读作 “cleany star”）。
Kleene 星表示“前一个字符或子表达式出现零次或多次”。
例如，r"a*" 表示“由零个或多个 a 组成的任意字符串”。
那么，r"ba*" 能否表示羊语言呢？它确实能匹配 baaaaaa，但也有问题：它还会匹配不含任何 a 的 b，或只含一个 a 的 ba。
这是因为 Kleene 星允许“零次”出现。
因此，对于羊语言，我们应该写成 r"baaa*"，即 b 后跟两个 a，再后跟零个或多个额外的 a。
更复杂的模式也可以重复。
例如，r"[ab]*" 表示“零个或多个 a 或 b”（注意：不是“零个或多个右方括号”），它可以匹配 aaaa、ababab、bbbb，甚至空字符串。
若要表示一个整数（即一串数字），我们可以使用 r"[0-9][0-9]*"。（为什么不能直接写成 r"[0-9]*"？因为那样会匹配空字符串，而整数至少应包含一位数字。）
还有一种更简洁的方式来表示“至少出现一次”：即 Kleene 加号（+），它表示“前一个字符或子表达式出现一次或多次”。
因此，r"[0-9]+" 是表示“一串数字”的常规写法，我们也可以将羊语言写作 r"baa+!"。
除了 Kleene 星和加号，我们还可以使用花括号中的显式数字作为计数器。
运算符 r"{3}" 表示“前一个字符或表达式恰好出现 3 次”。例如，r"ax{10}z" 会匹配一个 a，后跟恰好 10 个 x，再后跟一个 z。
另一个重要的特殊字符是句点（period，r"."），它是一个通配符（wildcard），可匹配任意单个字符（换行符除外）。
通配符常与 Kleene 星结合使用，表示“任意字符序列”。
例如，假设我们想找出某一行中某个词（比如 rose）出现两次的情况，可以用正则表达式 r"rose.*rose" 来表示：两个 rose 之间可以有任意数量（包括零个）的任意字符。
图 2.12 对上述内容进行了总结。
| 正则表达式 | 含义 |
|---|---|
* | 前一个字符或表达式出现零次或多次 |
+ | 前一个字符或表达式出现一次或多次 |
? | 前一个字符或表达式出现零次或一次 |
{n} | 前一个字符或表达式恰好出现 n 次 |
. | 任意单个字符（换行符除外） |
.* | 零个或多个任意字符组成的字符串 |
图 2.12 计数与通配符。
2.7.3 锚点与边界
锚点（Anchors）是一类特殊字符，用于将正则表达式“锚定”到字符串中的特定位置。
最常见的锚点是脱字符 ^ 和美元符号 $。
脱字符 ^ 匹配一行的开头。例如，模式 r"^The" 仅在行首匹配单词 The。
需要注意的是，脱字符 ^ 有三种用途：匹配行首；在方括号内表示否定（如 [^a]）；作为字面意义上的脱字符（如 [e^] 中的 ^）。（系统如何根据上下文判断某个 ^ 应该执行哪种功能？）
美元符号 $ 匹配一行的结尾。因此，模式 ␣$ 可用于匹配行尾的空格；而模式 r"^The dog\.$" 则匹配整行内容恰好为 The dog.（带句点）的行。
注意：在上例中，我们必须使用反斜杠对句点进行转义（\.），因为我们希望它表示字面意义上的句号，而非通配符。
相比之下，正则表达式 r"^The dog.$" 不仅会匹配 The dog.，还会匹配 The dog! 或 The dogo。
正如我们将在下文讨论的那样，所有目前已介绍的特殊字符（* + ? . [ ]），当需要表示其字面含义时，都必须用反斜杠进行转义。
此外还有其他锚点：\b 匹配单词边界（word boundary）；\B 匹配非单词边界（non-word boundary）。
例如，r"\bthe\b" 能匹配独立的单词 the，但不会匹配 other 中的 the。
| 正则表达式 | 含义 |
|---|---|
^ | 行首 |
$ | 行尾 |
\b | 单词边界 |
\B | 非单词边界 |
图 2.13 正则表达式中的锚点。
在正则表达式的语境中，“单词”（根据编程语言中的定义来确定）是由字母、数字或下划线组成的连续序列。
因此，r"\b99\b" 能在字符串 There are 99 bottles of beer on the wall 中匹配 99（因为 99 前后都是空格，属于边界）；但在 There are 299 bottles of beer on the wall 中，99 前面是数字 2，不构成单词边界，因此不会匹配；
而在 $99 中，99 前是美元符号 $（既非字母、数字，也非下划线），因此构成单词边界，可以匹配。
需要注意的是，所有这些锚点和边界操作符在技术上都匹配空字符串，也就是说，它们不消耗（consume）任何实际字符。
例如，在模式 r"^The" 中，^ 匹配的是字符串 "The" 的起始位置，但它并不会“吃掉”第一个字符 T。
同样地，模式 r"the\b the" 能匹配 the the：其中的 \b 意识到空格是一个单词边界，但它匹配的是空格之前的空位置（而非空格本身），因此空格字符仍然可供后续模式匹配使用。
2.7.4 析取、分组与运算优先级
假设我们需要搜索关于宠物的文本，尤其关注猫和狗。
此时，我们可能希望查找字符串 cat 或 dog。
由于方括号无法用于匹配“cat 或 dog”（为什么 r"[catdog]" 不行？因为它只匹配单个字符 c、a、t、d、o 或 g 中的任意一个，而不是整个单词），因此我们需要一个新的运算符：析取运算符（disjunction operator），也称为管道（pipe）符号 |。
模式 r"cat|dog" 可匹配字符串 cat 或 dog。
有时，我们需要在更长的模式中使用析取运算符。
例如，假设我想搜索提及观赏鱼文字，如何同时匹配 guppy 和 guppies？
我们不能简单地写成 r"guppy|ies"，因为这样只会匹配完整的字符串 guppy 或 ies。
这是因为像 guppy 这样的连续字符序列在正则表达式中具有比析取运算符 | 更高的优先级（precedence）。
为了使析取运算符仅作用于特定的子模式，我们需要使用圆括号 ( 和 ) 进行分组。
将模式用括号括起来后，它在相邻运算符（如 | 或 Kleene 星 *）眼中就相当于一个“单一单元”。
因此，模式 r"gupp(y|ies)" 表示，析取仅应用于 y 和 ies。
圆括号在使用计数器（如 Kleene 星）时也非常有用。
与 | 不同，Kleene 星默认仅作用于紧邻其前的一个字符，而非整个序列。
假设我们要匹配一段重复出现的字符串。
例如有一行文字带有这种形式的列标签：Column 1 Column 2 Column 3。
表达式 r"Column␣[0-9]+␣*"不会匹配任何列；实际上，它只会匹配一个 Column 加数字，后跟任意数量的空格——因为这里的 * 仅作用于前面的空格 ␣，而非整个 Column␣[0-9]+␣ 序列。
使用括号后，我们可以写出表达式 r"(Column␣[0-9]+␣+)*" 来匹配词 Column，后面跟一个数字，再跟至少一个空格，这一整体模式可重复零次或多次。
这种“某些运算符优先级高于其他运算符，必要时需用括号明确意图”的机制，在正则表达式中被形式化为运算符优先级层级（operator precedence hierarchy）。 下表列出了从高到低的优先级顺序：
| 运算符类型 | 示例 |
|---|---|
| 括号 | () |
| 计数器 | * + ? {} |
| 序列与锚点 | the, ^my, end$ |
| 析取 | | |
因此，由于计数器优先级高于序列，r"the*" 匹配的是 th 后跟零个或多个 e（如 theeeee），而非 thethe。
由于序列优先级高于析取，r"the|any" 匹配的是 the 或 any，而非 thany 或 theny。
正则表达式还可能存在另一种歧义。
考虑模式 r"[a-z]*" 在文本 once upon a time 上的匹配。
由于 r"[a-z]*" 匹配“零个或多个小写字母”，它可以匹配空字符串，或只是第一个字符 o，或者on、onc、或完整的 once。
在这种情况下，正则表达式总是尽可能匹配最长的有效字符串。我们称这种行为为贪婪匹配（greedy matching），模式会尽可能扩展，覆盖尽可能多的字符。
不过，也可以强制进行非贪婪匹配（non-greedy matching），方法是使用限定符 ? 的另一种含义。
运算符 *? 是一个 Kleene 星，但匹配尽可能少的文本。
运算符 +? 是一个 Kleene 加号，同样匹配尽可能少的文本。
2.7.5 一个简单示例
假设我们想编写一个正则表达式来查找英文定冠词 the 的出现。 一个简单（但不正确）的模式可能是：
r"the" (2.14)
这个模式的一个问题是：当 the 出现在句首时，通常首字母大写（即 The），而该模式会漏掉这种情况。 这可能会引导我们写出以下改进模式：
r"[tT]he" (2.15)
然而，这样又会产生过度泛化的问题，它会错误地匹配那些包含 the 作为子串的其他单词，例如 other 或 there。
因此，我们需要明确指定，只希望匹配两侧均为单词边界的 the 实例：
r"\b[tT]he\b" (2.16)
我们刚刚经历的这个简单过程，本质上是在修正两类错误：假阳性（false positives），这是指错误匹配的字符串，如 other 或 there；假阴性（false negatives），这是指错误遗漏的字符串，如 The。 在自然语言处理中，应对这两类错误是一个反复出现的核心问题。 因此，降低某个应用的整体错误率，通常需要在两个相互矛盾的目标之间取得平衡：
- 提高 准确率（precision）：尽量减少假阳性；
- 提高 召回率（recall）：尽量减少假阴性。
我们将在第 4 章对准确率和召回率给出更精确的定义。
2.7.6 更多运算符
图 2.14 展示了一些常用字符范围的便捷别名（aliases）：
| 正则表达式 | 等价形式 | 匹配内容 | 首次匹配示例 |
|---|---|---|---|
\d | [0-9] | 任意数字 | Party␣of␣5 |
\D | [^0-9] | 任意非数字字符 | Blue␣moon |
\w | [a-zA-Z0-9_] | 任意字母、数字或下划线 | Daiyu |
\W | [^\w] | 任意非字母数字字符 | !!!! |
\s | [ ␣\r\t\n\f] | 空白字符（空格、制表符、换行等） | in Concord |
\S | [^\s] | 任意非空白字符 | in␣Concord |
图 2.14 常用字符集合的别名。
最后，某些特殊字符使用专用记法反斜杠（\）来表示（见图 2.15）。
其中最常见的是换行符 \n 和制表符 \t。
那么，当我们需要字面匹配那些本身具有特殊含义的字符（如 ., *, -, [, \ 等），而非使用它们的正则功能时，该如何表示呢？
例如，如果我们想匹配一个句点、星号、方括号或圆括号本身，该怎么办？
要获得这些特殊字符的字面意义，需要在这些特殊字符前加上反斜杠进行转义。
| 正则表达式 | 匹配内容 | 首次匹配示例 |
|---|---|---|
\* | 星号 “*” | “K*A*P*L*A*N” |
\. | 句点 “.” | “Dr. Livingston, I presume” |
\? | 问号 | “Why don’t they come and lend a hand?” |
\n | 换行符 | （无可见字符） |
\t | 制表符 | （通常显示为空格缩进） |
图 2.15 一些需要用反斜杠转义的字符。
2.7.7 替换与捕获组
正则表达式的一个重要用途是替换（substitutions），即用一个字符串替换另一个字符串。
正则表达式不仅能帮助我们指定要被替换的字符串，还能定义替换后的内容。
在 Python 中，我们使用 re.sub() 函数（其他语言和环境中也存在类似函数）。
re.sub(pattern, repl, string) 接受三个参数：一个用于搜索的 pattern（模式），一个用于替换的 repl（替换字符串），以及要在其中执行搜索和替换的 string（目标字符串）。
例如，我们可以将字符串中所有 cherry 替换为 apricot：
re.sub(r"cherry", r"apricot", string)
或者将某个名字的所有小写形式转换为首字母大写：
re.sub(r"janet", r"Janet", string)
然而，更常见的情况是：替换内容依赖于匹配到的具体文本。
例如，假设我们有一份文档，其中所有日期都采用美国格式（mm/dd/yyyy），而我们希望将其转换为欧盟及其他许多地区使用的格式（dd-mm-yyyy）。
模式 r"\d{2}/\d{2}/\d{4}" 可以匹配一个日期，
但如何在替换字符串中指定“交换日和月的位置”呢？
这时就要用到正则表达式中的 捕获组（capture group）。
捕获组通过圆括号 () 将搜索过程中匹配到的部分捕获（即存储起来），以便在替换时重用。
我们将希望捕获的子模式用括号括起来，这些子模式会按从左到右的顺序被编号为第 1 组、第 2 组等。
然后在 repl 中，通过反向引用 \1、\2 等来调用这些捕获的内容。
考虑以下表达式：
re.sub(r"(\d{2})/(\d{2})/(\d{4})", r"\2-\1-\3", string)
我们在月份（两位）、日期（两位）和年份（四位）周围分别加上了括号，因此第一组 \1 存储前两个数字，第二组 \2 存储中间两个数字，第三组 \3 存储最后四个数字。
在替换字符串中，我们使用数组操作符 \1、\2、\3 来分别指代第一个、第二个、第三个寄存器。
如果输入：
The date is 10/15/2011
会被转换为：
The date is 15-10-2011
即使不进行替换，捕获组也非常有用。 例如，我们可以用它来查找重复内容，这在文本处理中很常见。 要查找字符串中的重复单词，可以使用如下模式：先匹配一个单词并将其捕获，再匹配其后的空白字符，最后通过反向引用确认该单词是否再次出现：
r"\b([A-Za-z]+)\s+\1\b"
因此，圆括号在正则表达式中有双重功能：可以用作分组，来控制使用运算符的优先级；还可以用来捕获匹配。
有时我们只需要分组功能，而不想捕获匹配结果。
这时可以使用 非捕获组（non-capturing group），其语法是在左括号后紧跟 ?:，即 (?:pattern)。
非捕获组通常用于复杂模式中，当我们只想捕获整体模式的某一部分时非常有用。
例如，假设我们要匹配由空格分隔的一系列日期（格式为 \d\d/\d\d/\d\d\d\d），并只提取第 15 个日期。
我们需要对前 14 个日期使用计数器，但又不想把它们全部存入捕获组（以免浪费资源）。
以下模式中，只在第 1 捕获组中存储第 15 个日期：
r"(?:\d\d/\d\d/\d\d\d\d\s+){14}(\d\d/\d\d/\d\d\d\d)" (2.17)
替换与捕获组还可用于实现历史上著名的聊天机器人，如 ELIZA（Weizenbaum, 1966）。 回忆一下，ELIZA 通过如下对话来模拟罗杰派心理咨询师：
用户2：They’re always bugging us about something or other.
ELIZA2：CAN YOU THINK OF A SPECIFIC EXAMPLE
用户3：Well, my boyfriend made me come here.
ELIZA3：YOUR BOYFRIEND MADE YOU COME HERE
用户4：He says I’m depressed much of the time.
ELIZA4：I AM SORRY TO HEAR YOU ARE DEPRESSED
ELIZA 的工作原理是有一系列级联的正则表达式替换规则，每条规则匹配输入语句的某一部分并进行改写。
首先，输入被转为大写；接着，替换规则将 MY 改为 YOUR，I’M 改为 YOU ARE，等等。
这样当 ELIZA 通过重复用户话语的一部分时做出回应时，看起来就能正确地指向用户自身。
随后的替换规则匹配并替换输入中的其他模式，把输入转化为完整的回应。例如：
re.sub(r".* YOU ARE (DEPRESSED|SAD) .*", r"I AM SORRY TO HEAR YOU ARE \1", input)
re.sub(r".* YOU ARE (DEPRESSED|SAD) .*", r"WHY DO YOU THINK YOU ARE \1", input)
re.sub(r".* ALWAYS .*", r"CAN YOU THINK OF A SPECIFIC EXAMPLE", input)
2.7.8 前瞻断言（Lookahead Assertions）
最后，有时我们需要“预测未来”：在文本中向前查看某个模式是否匹配，但不移动我们用于跟踪当前文本位置的指针。 这样，如果该模式确实出现，我们就可以处理它；如果未出现，我们还可以尝试匹配其他内容。
这类前瞻（lookahead）断言使用了我们在上一节非捕获组中见过的 (? 语法。
操作符 (?= pattern) 在 pattern 存在时返回真，但它是一个零宽度（zero-width）断言，也就是说，匹配指针不会前移，这一点与锚点和边界标记（如 \b）的行为一致。
操作符 (?! pattern) 则仅在 pattern 不匹配时返回真，同样也是零宽度的，不会使匹配指针前进。
否定前瞻（Negative lookahead）常用于解析复杂模式时排除某些特殊情况。
例如，假设我们想捕获一行中的第一个单词，但前提是它不能以字母 T 开头。
我们可以使用否定前瞻来实现：
r"^(?![tT])(\w+)\b" (2.18)
这里的否定前瞻 (?![tT]) 表示：行首不能是 t 或 T，但它匹配空字符串，不会移动匹配指针。
随后，捕获组 (\w+) 才真正捕获第一个单词。