数据结构与算法：Python语言描述 字符串

本资源由会员分享，可在线阅读，更多相关《数据结构与算法：Python语言描述 字符串（65页珍藏版）》请在人人文库网上搜索。

3，字符串字符串的相关概念Python 字符串（回顾）字符串匹配和算法进一步的模式匹配问题正则表达式Python 的正则表达式应用举例字符串讨论字符串，首先要有一个确定的字符集“字符”是一个抽象概念，字符集是有穷的一组字符构成的集合人们经常考虑在计算机里使用的标准字符集，实际上，完全可以拿任意数据元素的集合作为字符集字符串（简称串）是特殊的线性表，表中元素取自选定的字符集其不同于一般表的特点是支持一组以串为对象的操作长度：串中字符的个数称为串的长度长度为 0 的串称为空串在任意一个字符集里，只有唯一的一个空串与一般的表类似：字符串里的字符顺序排列，串里的每个字符有其确定位置我们用 0 开始的自然数表示位置字符串串相等：串的相等基于字符集里的字符定义s1 和 s2 相等，如果其长度相等，而且对应位置的各对字符分别相同假定字符集中的字符有一个全序，串的字典序定义如下：对于串定义 s1 < s2，如果存在一个 k

使 ai = bi (i = 0,1, … k-1) 而且 ak < bk

　　　　或者 n < m

而且对 i = 0,1, … n-1

都有 ai = bi显然，字典序是字符串集合上的一个全序串与串的最重要运算是拼接（concatenate）上面 s1

和 s2

的拼接是串 显然，s

的长度等于 s1

和 s2

的长度之和在 Python 里拼接运算用 + 表示字符串两个串之间还有一个重要的关系是“子串关系”称 s1

为 s2

的一个子串，如果存在两个串 s 和 s' 使下式成立s2 = s + s1 + s' （借用 Python 的写法）子串也是串。直观看，子串是原串中连续的一段字符序列形成的串。显然，一个串可以是或者不是另一个串的子串如果 s1

是 s2

的子串，也说 s1

在 s2

里出现，称 s2

里与 s1

相同的字符段的第一个字符的位置为 s1

在 s2

里出现的位置s2

里可能出现多个与 s1

相同的段，这时说 s1

在 s2

里多次出现注意：s1 在 s2 中的多个出现可能不独立，相互重叠。例如babb 在 babbabbbbabb 里有三个出现，前两个有重叠根据定义，很显然，空串是任何字符串的子串；另一方面，任何字符串 s 也都是该串本身的子串字符串两种特殊子串：如果存在 s' 使 s2 = s1 + s'，称 s1

为 s2

的一个前缀如果存在 s 使得 s2 = s + s1，称 s1

为 s2

的一个后缀直观说，一个串的前缀就是该串开头的一段字符构成的子串，后缀就是该串最后的一段字符构成的子串显然，空串和 s 既是 s 的前缀，也是 s 的后缀其他有用的串运算：串 s 的 n 次幂 sn

是连续 n 个 s 拼接而成的串（在 Python 语言里用 s * n 表示）串替换，指将一个串里的一些（互不重叠的）子串代换为另一些串得到的结果（由于可能重叠，需规定代换的顺序，如从左到右）还有许多有用的串运算，可以参考 Python 的 str 类型，或其他语言的字符串类型（经典是 SNOBOL 语言）字符串的理论字符串集合和拼接操作构成了一种代数结构空串是拼接操作的“单位元” （幺元） 有结合律，无交换律串集合加上拼接操作，构成一个半群一种典型的非交换半群有单位元，因此是一个幺半群关于串的理论有许多研究工作基于串和串替换，研究者提出了 post 系统这是一种与图灵机等价的计算模型（串）重写系统（rewriting system）是计算机理论的一个研究领域，一直非常活跃，有许多重要结果和应用字符串抽象数据类型可以考虑下面的字符串抽象数据类型：ADT String: String(self, sseq)　# 基于字符序列sseq建立一个字符串

is_empty(self) # 判断本字符串是否空串

len(self)　# 取得字符串的长度

char(self, index) # 取得字符串中位置index的字符

substr(self, a, b)　# 取得字符串中 [a:b] 的子串，左闭右开区间

match(self, string) # 查找串string在本字符串中第一个出现的位置

concat(self, string) # 做出本字符串与另一字符串string的拼接串

subst(self, str1, str2) # 做出将本字符串里的子串str1

　　　　　　　　　　　　　　　　　　　　　# 都替换为str2的结果串最后两个操作可以实现为变动操作或非变动操作（生成满足需要的新串）这里的大部分操作都很简单，只有match和subst操作比较复杂。易见，subst 的基础也是 match，因为要找 str1 在串里的出现子串检索（子串匹配）是字符串的核心操作，后面将详细研究字符串的实现串是字符的线性序列：可采用线性表的实现方式，用顺序表示和链接表示。例如用能动态变化大小的顺序表作为实现方式（如果需要表示可变的字符串）还可以根据串本身的特点和串操作的特点，考虑其他表示方式。当然，无论如何还是基于顺序存储或/和链接关键问题：表示方式应能很好支持串的管理和相关操作的实现字符串表示的两个问题：串内容存储。两个极端：1，连续存储在一块存储区；2，一个字符存入一个独立存储块，链接起来。也可以采用某种中间方式，把串中字符分段保存在一组存储块里，链接起这些存储块串结束的表示，不同字符串长度可能不同，必须表示串到哪里结束。两种基本方式：1，用专门数据域记录字符串长度；2，用一个特殊符号表示串结束（例如 C 语言的字符串采用这种方式）字符串的实现现在考虑字符串的操作许多串操作是线性表操作的具体实例，包括串拼接下面考虑一个特殊的操作串替换牵涉到三个串：被处理的主串 s，作为被替换对象需要从 s 中替换掉的子串 t，以及用于代换 t 的 t'由于 t 可能在 s 中出现多次，因此需要通过一系列具体的子串代换完成整个替换由于多次出现可能重叠（回忆前面的例子），只能规定一种代换顺序（例如从左到右），一次代换破坏的子串不应再代入新串一次子串代换后，应该从代入的新串之后继续工作。即使代入新串之后形成的部分能与 t 匹配，也不应在本次替换中考虑很容易看到：串替换的关键是找到匹配实际语言里的字符串许多语言提供了标准的字符串功能，如C语言标准库有一组字符串函数（string.h），一些C语言系统提供的扩展的字符串库；C++ 语言标准库里的字符串库 <string>Java 标准库的字符串库许多脚本语言（包括 Python）提供了功能丰富的字符串库许多实际字符串库用动态顺序表结构作为字符串的表示方式这样既能支持任意长的字符串又能比较有效地实现各种重要的字符串操作实际上，支持不同的字符串操作，可能需要不同的实现，例如有些计算工作需要记录和处理极长的字符串，如支持操作 MB（大约为 106）或更长的字符串，采用连续存储可能带来管理问题被编辑文本也是字符串，实现编辑器操作要考虑专门的字符串表示Python 字符串Python 内部类型 str 是抽象字符串概念的一个实现str 是不变类型，str 对象创建后的内容（和长度）不变但不同的 str 对象长度不同，需要记录Python 采用一体式的连续形式表示 str 对象，见下图其他长度len串内容存储区...str 对象的操作分为两类：获取 str 对象的信息，如得到串长，检查串内容是否全为数字等基于 str 对象构造新的 str 对象，包括切片，构造小写/大写拷贝，各种格式化等。切分是构造包含多个字符串的表一些操作属子串匹配，如 count 检查子串出现次数，endwith 检查后缀，find/index 找子串位置等。这类操作最重要，后面专门讨论字符串操作的实现检查字符串内容的操作可以分为两类O(1) 时间的简单操作，包括 len 和定位访问（也构造新字符串）其他都需要扫描整个串的内容，包括不变序列的共有操作（in、not in、min/max），各种字符类型判断（如是否全为数字）需通过一个循环逐个检查串中字符完成工作，O(n) 操作子串查找和匹配的问题后面讨论需要构造新字符串的操作情况比较复杂，基本模式都包括两部分工作1, 为新构造的串安排一块存储2, 根据被操作串（和可能的参数串）构造出一个新串以 s[a:b:k] 为例，算法：1, 根据 a、b、k 算出新字符串的长度2, for i in range(a, b, k) : 拷贝 s[i] 到新串里的下一个空位字符串匹配（子串查找）最重要的字符串操作是子串匹配，称为字符串匹配（string matching）或字符串查找（string searching）

【有教科书称为模式匹配（pattern match），但实际上模式匹配是内涵更广的概念】wiki：/wiki/String_searching_algorithm字符串匹配问题：假设有两个串（ti, pj

是字符）

t = t0t1t2 … tn-1

称为目标串

p = p0p1p2 … pm-1

称为模式串通常有 m << n。字符串匹配就是在 t 中查找与等于 p 的子串的过程（这一定义可以推广，后面讨论）如前所述，串匹配是最重要的字符串操作，也是其他许多重要字符串操作的基础。实际中 n 可能非常大，m 也可以有一定规模，也可能需要做许多模式串和/或许多目标串的匹配，有关算法的效率非常重要串匹配许多计算机应用的最基本操作是字符串匹配。如用编辑器或字处理系统工作时，在文本中查找单词或句子（中文字或词语），在程序里找拼写错误的标识符等email 程序的垃圾邮件过滤器，google 等网络检索系统各种防病毒软件，主要靠在文件里检索病毒模式串在分子生物学领域：DNA 细胞核里的一类长分子，在遗传中起着核心作用。DNA 内有四种碱基：腺嘌吟(adenine)，胞嘧啶(cytosine)，鸟嘌吟(guanine)，胸腺嘧啶(thymine)。它们的不同组合形成氨基酸、蛋白质和其他更高级的生命结构DNA 片段可看作是a,c,g,t构成的模式，如 acgatactagacagt考查在蛋白质中是否出现某个 DNA 片段，可看成与该 DNA 片段的串匹配问题。DNA 分子可以切断和拼接，切断动作由各种酶完成，酶也是采用特定的模式确定剪切位置串匹配实际中模式匹配的规模（n 和 m）可能非常大，而且有时间要求被检索的文本可能很大网络搜索需要处理亿万的网页防病毒软件要在合理时间内检查数以十万计的文件（以 GB 计）运行在服务器上的邮件过滤程序，可能需要在一秒钟的时间内扫描数以万计的邮件和附件为疾病/药物研究/新作物培养等生物学工程应用，需要用大量 DNA模式与大量 DNA 样本（都是 DNA 序列）匹配由于在计算机科学、生物信息学等许多领域的重要应用，串模式匹配问题已成为一个极端重要的计算问题。高效的串匹配算法非常重要有几个集中关注字符串匹配问题的国际学术会议，曾经有过专门的国际竞赛（见 wiki 页和万维网）目前全世界一大半的计算能力是在做串模式匹配（做 DNA 分析）串匹配和算法还需注意不同的实际需要，如用一个模式在很长的目标串里反复匹配（确定出现位置）一组（可能很多）模式，在一个或一组目标串里确定是否有匹配不同算法在处理不同实际情况时可能有不同的表现人们已经开发出一批有意义的（有趣）算法（进一步情况见 wiki）粗看，字符串匹配是一个很简单的问题字符串是简单数据（字符）的简单序列，结构也最简单（顺序）很容易想到最简单而直接的算法但事实是：直接而简单的算法并不是高效的算法因为它可能没有很好利用问题的内在结构字符串匹配貌似简单，但人们已开发出许多“大相径庭的”算法串匹配的朴素算法串匹配的基础是逐个比较字符如果从目标串的某个位置开始，模式串的每个字符都与目标串里的对应字符相同，这就是一个匹配如果出现一对不同字符，就是不匹配算法设计的关键：1，怎样比较字符；2，发现不匹配后下一步怎么做对上述两点采用不同的策略，就形成了不同的算法从下面两个例子可以看到一些情况，更多实例见 wiki朴素匹配算法：1，从左到右匹配；2，发现不匹配时，考虑目标串里的下一位置是否存在匹配

t

a

b

b

b

a

a

p

a

b

a

a

b

a

a

b

a

a

b

a

串匹配的朴素算法朴素的串匹配算法的一个实现：def naive_nmatching(t, p):　　m, n = len(p), len(t)　　i, j = 0, 0　　while i < m and j < n:　# i==m说明找到了匹配

if p[i] == t[j]:　　# 字符相同! 考虑下一对字符

i, j = i + 1, j + 1　　　　else:　　　　　　　　# 字符不同! 考虑t中下一位置

i, j = 0, j - i + 1　　if i == m:　 # 找到匹配, 返回其开始下标

return j - i　　return -1　 # 无匹配, 返回特殊值朴素匹配算法简单，易理解，但效率低造成效率的主要操作是执行中可能出现的回溯：遇字符不等时将模式串 p 右移一个字符，再次从 p0（重置 j = 0 后）开始比较串匹配的朴素算法最坏情况是每趟比较都在最后出现不等，最多比较 n－m＋1 趟，总比较次数为 m*(n－m＋1)，所以算法时间复杂性为 O(m*n)最坏情况的一个实例目标串：00000000000000000000000000000000000000001模式串：00000001朴素算法效率低的原因：把每次字符比较看作完全独立的操作完全没有利用字符串本身的特点（每个字符串都是特殊的）没有利用前面已做过的字符比较得到的信息从数学上看，这样做相当于认为目标串和模式串里的字符都是随机量，而且有无穷多可能取值，两次字符比较相互无关也不可借鉴实际字符串取值来自一个有穷集合每个串都有穷。特别是模式串通常不太长，而且可能反复使用无回溯匹配：KMP算法KMP 算法是一个高效串匹配算法。由 D. E. Knuth 和 V. R. Pratt 提出，J. H. Morris 几乎同时发现，因此称 KMP 算法。这是本课程中第一个非平凡算法，基于对问题的深入分析，算法不易理解但效率高要理解 KMP 算法，首先需要了解朴素算法的缺陷。现在仔细考察朴素算法的执行过程。设目标串 t: ababcabcacbab，模式串 p: abcac第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配a b a b c a b c a c b a ba b c a c第四趟匹配a b a b c a b c a c b a ba b c a c第五趟匹配a b a b c a b c a c b a ba b c a c第六趟匹配a b a b c a b c a c b a ba b c a c模式串为匹配前已知，在匹配中反复使用若先对模式串做细致分析，记录有用信息（ 静态预处理），有可能加快匹配无回溯匹配：KMP算法KMP 算法的基本想法：在匹配失败时，利用已做匹配得到的信息，把模式串尽可能前移。匹配中只做不得不做的字符比较，不回溯处理同一个实例：第一趟匹配a b a b c a b c a c b a ba b c a c第二趟匹配a b a b c a b c a c b a ba b c a c第三趟匹配a b a b c a b c a c b a b(a)b c a c这里的匹配绝不回溯，如果匹配到 tj

失败（设遇到 pi

 tj），就去找到某个 pki，0  ki < i，下一步用 pki

去与 tj

比较要正确前移，对模式 p 的每个 pi，都应能找到相应的 pki。问题是，无论对怎样的 tj

失败，对相应的 i，对应 ki

都一样吗？无回溯匹配：分析关键认识：在 pi

匹配失败时，所有 pk（0  k< i）都已匹配成功（否则不会考虑 pi

的匹配）。也就是说：tj

之前的 i-1 个字符就是 p 的前 i-1 个字符！：原本应该根据 t 的情况确定前移方式，但实际上可以根据 p 本身的情况确定，可以通过对模式串本身的分析在匹配之前做好结论：对 p 中的每个 i，有一个唯一确定的 ki，与被匹配的串无关。通过对模式串 p 的预分析，可以得到每个 i 对应的 ki

值（  ）设 p 的长度为 m，需要对每个 i (0  i < m) 算出一个 ki

值并保存，以便在匹配中使用。考虑把这 m 个值（i 和ki

的对应关系）存入一个表 pnext，用 pnext[i] 表示与 i 对应的 ki

值特殊情况：在 pi

匹配失败时，有可能发现用 pi

之前的所有 p 字符与 t 字符的比较都没有利用价值，下一步应该从头开始，用 p0

与 tj+1

比较。遇到这种特殊情况就在 pnext[i] 里记录 –1显然，对任何模式都有：pnext [0] = -1KMP算法假设已经根据模式串 p 做出了 pnext 表，考虑 KMP 算法的实现匹配循环很容易写出，如下：while j < n and i < m:　# i==m means a matching　　if i == -1 :　　　　　# 遇到 –1，比较下一对字符　　　　j, i = j+1, i+1　　elif t[j] == p[i]:　# 字符相等，比较下一对字符　　　　j, i = j+1, i+1　　else:　　　　　　　　 # 从 pnext 取得 p 下一字符的位置　　　　i = pnext[i]if 的前两个分支可以合并：while j < n and i < m:　# i==m means a matching　　if i == -1 or t[j] == p[i]:　 # 比较下一对字符　　　　j, i = j+1, i+1　　else:　　　　　　　　 # 从 pnext 取得 p 下一字符的位置　　　　i = pnext[i]KMP算法匹配函数的定义：def matching_KMP(t, p, pnext):　　j, i = 0, 0　　n, m = len(t), len(p)　　while j < n and i < m:　# i==m说明找到了匹配

if i == -1 or t[j] == p[i]:　# 考虑p中下一字符

j, i = j+1, i+1　　　　else:　　　　　　　 # 失败! 考虑pnext决定的下一字符

i = pnext[i]　　if i == m:　　　# 找到匹配, 返回其下标

return j-i　　return -1　　　# 无匹配, 返回特殊值算法复杂性的关键是循环。注意循环中 j 的值递增，但加一的总次数不多于 n = len(t)。而且 j 递增时 i 值也递增。另一方面 i = pnext[i] 总使 i 值减小，但条件保证其值不小于 –1，因此 i = pnext[i] 的执行次数不会多于 i 值递增的次数。循环次数是 O(n)，算法复杂性也是 O(n)新位置的前缀子串应该与匹配失败字符之前同长度的子串相同如果在模式串匹配失败时，前面一段里满足上述条件的位置不止一处，只能移到最近的那个位置（保证不遗漏可能的匹配）KMP算法：生成 pnext 表第二趟匹配a b a b c a b c a c b a ba b c a c(a)b c a c现在考虑 pnext 表的构造，以下面情况为例已知 ki 值只依赖于 p 本身的前i个字符

t0…tj-i-1tj-i…tj-1

tj…　　　　　　　　　　　　　　 p0…pi-1pi…　　　　　　　　t0…tj-i-1p0…pi-1 tj…‖‖设匹配到 pi/tj

时失败t 中位置 j 之前的 i 个字符就是 p 的前 i 个字符KMP算法：生成 pnext 表正确 k 值由

p 前 i 个字符形成的子串里相等的前缀和后缀决定取这种前后缀中最长的（前移最短），就能保证不忽略可能的匹配如果 p0…pi-1

最长相等前后缀（不包括 p0…pi-1

本身但可为空）的长度为 k (0  k < i-1)。当 pi

 tj

时 p 应右移 i - k 位，随后比较 pk

与 tj也就是说，应该把 pnext[i] 设置为 k求 pnext 的问题变成对每个 i 求 p 的（前缀）子串 p0…pi-1

的最长相等前后缀的长度。KMP 提出了一种巧妙的递推算法正确 k 值的情况看下面图示

前缀

后缀t0…tj-i-1 p0…pk-1…pi-k…pi-1 tj…　　　　　　　　　　　　　　　 p0　…pk-1pk…

前缀模式串的正确前移位置移位，必须保证其前缀 p0 …pk-1与 t 中对应那些字符匹配，而这实际上也就是与 pi-k …pi-1 匹配KMP算法：生成 pnext 表利用已知 pnext[0]= -1 直至 pnext[i] 求 pnext[i+1] 的算法：假设 next [i] = k。若pk = pi，则 p0… pi-k…pi

的最大相同前后缀的长度就是 k+1，记入 pnext[i+1]，将 i 值加一后继续递推（循环）若pk

 pi

设 k 为 pnext[k] 的值（设 k 为 pnext[k]，也就是去考虑前一个更短的保证匹配的前缀，从那里继续检查）若 k 值为 -1（一定来自 pnext），得到 p0… pi-k…pi

中最大相同前后缀的长度为 0，设 pnext [i+1] = 0，将 i 值加一后继续递推针对 i 递推计算最长相等前后缀的长度。设对 i-1 已经算出，于是p0… … … pk-1 … pi-k… … … pi-1 pi pi+1

…　　　　　　　　　　　　　　　 p0　… … … pk-1pk pk+1

…‖‖？如果 pi = pk，pnext[i] 应该为 k，继续否则把 p0...pk-1的最长相同前缀移过来继续检查KMP算法：生成 pnext 表生成 pnext 表的 Python 函数定义def gen_pnext(p):　　i, k, m = 0, -1, len(p)　　pnext = [-1] * m　　# 初始数组元素全为 -1　　while i < m-1:　　　 # 生成下一个pnext元素值

if k == -1 or p[i] == p[k]:　　　　　　i, k = i+1, k+1　　　　　　pnext[i] = k　 # 设置pnext元素

else:　　　　　　k = pnext[k]　# 退到更短相同前缀

return pnext求模式串 p 在目标串 t 里的匹配，可以写：i = matching_KMP(t, p, gen_pnext(p))上述 pnext 的生成算法还可以改进，下面讨论生成 pnext 表：改进设置 pnext[i] 时有一点情况可以考虑：t0…tj-i-1p0…pj-1tj…　　　　　　 p0…pi-1pi…‖‖在 pi



tj 时（假设 pnext[i] = k），如果发现 pi = pk，那么一定 pk 

tj 。所以模式串应右移到

pnext[k]，下一步用

pnext[k] 与

tj 比较改造的算法只有循环体最后的语句不同：def gen_pnext(p):　　i, k, m = 0, -1, len(p)　　pnext = [-1] * m　　while i < m-1:　# 生成下一个pnext元素

if k == -1 or p[i] == p[k]:　　　　　　i, k = i+1, k+1　　　　　　if p[i] == p[k] :　　　　　　　　pnext[i] = pnext[k]　　　　　　else:　　　　　　　　pnext[i] = k　　　　else:　　　　　　k = pnext[k]　　return pnext生成 pnext 表：复杂性算法复杂性的主要因素是循环与 KMP 主算法的分析类似：i 值递增，但不超过 p 的长度 m，说明大循环体执行 m 次i 加一时 k 也加一，说明 k 值加一 m 次内层循环执行总导致 k 值减小，但不会小于 –1上面情况说明循环体的执行次数为 O(m)，算法复杂性也是 O(m)KMP 算法包括 pnext 表构造和实际匹配，O(m+n)。通常情况 m << n，因此可认为算法复杂性为 O(n)。显然优于 O(m*n)KMP 算法KMP 算法的一个重要优点是执行中不回溯。在处理从外部（外存/网络等）获取的文本时这种特性特别有价值，因为可以一边读一边匹配，不回头重读就不需要保存被匹配串KMP 算法的优势KMP 算法特别适合需要多次使用一个模式串的情况和存在许多匹配的情况（如在大文件里反复找一个单词）相应 pnext 表只需建立一次。这种情况下可以考虑定义一个模式类型，将 pnext 表作为模式的一个成分人们还提出了其他的模式匹配算法（参看 wiki）另一经典算法由 Boyer 和 Moore 提出，采用自右向左的匹配方式。如果字符集较大且匹配很罕见（许多实际情况如此，如在文章里找单词，在邮件里找垃圾过滤关键字），其速度可能远高于KMP算法有兴趣的同学可以自己找相关材料读一读模式匹配问题前面讨论的串匹配基于最简单的字符比较以常规的字符串作为模式比较的一方是模式串，另一方是一个字符串的所有可能子串匹配中考察的是模式串与目标串的所有可能子串之间的相等关系基本串匹配有很广泛的应用，前面举过一些例子，如正文编辑器中最常用的操作是查找和替换网络搜索引擎，基本功能就是在网页中检查检索串的匹配实际使用中，存在着许多不同的场景，如用一个模式串，在目标串里反复检索，找出一些或者所有出现在一个目标串里检查是否出现了一组模式串中的任何一个在一批目标串里检查一个或一组模式串是否出现，等等模式匹配的进一步问题实际中还经常需要（希望）考虑一些更一般的问题，例如一个目录下所有以 .py 结尾的文件名文件里所有形为 href="…" 的段（HTML网页里的网页链接）DNA片段里以某碱基段开始以另一碱基段结束的片段计算机可执行文件中的某种片段模式（例如检查病毒），以一种形式的片段开始到另一片段结束，其中出现了某些片段等等这种匹配中考虑的不是一个字符串，而是一集字符串可能有穷，也可能无穷罗列（枚举）的方式不适合这里的需要，因为可能很多或无穷多要处理这种匹配问题，就需要考虑字符串集合的描述问题，以及是否属于一个字符串集合的匹配问题模式匹配的进一步问题有关字符串集合的描述和匹配，需要考虑两个问题：怎样描述被考虑的那个串集合？需要一种严格描述方式，能描述很多（所有？）有用的字符串集合。“系统化的” 描述方式就是一种描述串检索模式的语言（简单串匹配的“模式语言”就是字符串本身）如何（或，是否可能）高效实现所希望的检查（匹配）模式描述语言的功能很强，就可能描述更多更复杂的模式（对应的，字符串集合），但匹配算法的复杂性也会提高。这方面有许多理论结果模式语言变得比较复杂以后，或许只能做出具有指数复杂性的匹配算法，这种情况使模式语言变得没有实用意义如果模式语言进一步复杂，模式匹配问题甚至可能变为不可计算问题。也就是说，根本不可能写出完成匹配的算法。这样的描述语言就完全没有实际价值了有意义的模式描述语言是描述能力和处理效率之间的合理平衡模式匹配的进一步问题如果大家对 DOS 操作系统或者 Windows 命令窗口（cmd）有些了解，可能会知道描述文件名的“通配符”在 Windows 系统里搜索文件，也会用到Windows/DOS 的文件名描述中可以使用两个通配符 * 和 ?写在文件名字符串里的 ? 可以与任何实际字符匹配* 可与任意一串字符匹配例：*.py 与所有以 py 为扩展名的文件名匹配在普通字符串的基础上增加通配符，形成了一种功能更强的模式语言一个模式描述一集字符串，例如 a?b 描述所有 3 个字符的串，其首字符为 a，尾字符为 b，中间字符任意能描述无穷字符串集合，例如 a* 描述了所有以 a 开头的字符串但，只是加入了通配符的模式语言还不够灵活（描述能力不够强）正则表达式一种很有意义的实用模式语言是正则表达式（Regular Expression, 或称 regex、regexp、RE、re），由逻辑学家 Kleene 提出一个具体的正则表达式，描述字符集上的一个字符串集合正则表达式语言的基本成分是字符集里的普通字符，另外还有几种特殊的组合结构（以及表示组合的括号）正则表达式里的普通字符只与该字符本身匹配顺序组合 ：若 

匹配 s，

匹配 t，那么  匹配 st选择组合  | ：若 

匹配 s，

匹配 t，

 |  匹配 s 也匹配 t星号 *：与 0 段或者任意多段与 

匹配的序列的拼接串匹配例：abc 只与串 abc 匹配a(b*)(c*) 与所有一个 a 之后任意个 b 再后任意个 c 的串匹配a((b|c)*) 与所有一个 a 后任意个 b 和 c 组成的序列匹配正则表达式这里不需要通配符通配符 ? 可以用 | 描述（由于字符集是有穷集）通配符 * 可以通过 | 和星号描述正则表达式在实际的信息处理中非常有用人们以各种形式将其纳入编程语言或者语言的标准库存在很多不同设计，它们都是理论的正则表达式的子集或变形，基于对易用性和实现效率等方面的考虑，还可能有些扩充许多脚本语言提供正则表达式功能，一些常规语言正在或计划把正则表达式纳入标准库，C/C++/Java 等语言也有正则表达式包经过在 Perl 语言里的精炼，基本形成了一套比较标准的形式可以看到许多有关正则表达式的书籍或文章，把正则表达式说成是程序员必备的重要武器，等等。网上的讨论很热闹，有若干书籍正则表达式有关书籍Python 正则表达式Python 的正则表达式功能由标准包 re 提供。正则表达式可以帮助我们实现一些复杂的字符串操作。正确使用这个包需要理解正则表达式的描述规则和效用理解使用正则表达式的各种方法正则表达式采用 Python 字符串的形式描述（引号括起的字符序列）在用于一些特殊的操作时，一个具有正则表达式形式的字符串代表一种字符串模式，它能与特定的一集字符串匹配正则表达式的描述形式实际上构成一种特殊的“小语言”语法：re 规定的特殊描述规则语义：一个正则表达式所描述的那一集字符串Python 文档 HOWTO 里有一节 Regular Expression HOWTO。网上有些介绍 Python 正则表达式的网页，一些 Python 书籍里有讨论原始字符串在介绍 Python 正则表达式前，先介绍原始字符串（文字量）的概念原始字符串（raw string）是 Python 里一种写字符串文字量的形式，其值（和普通文字量一样）就是 str 类型的对象原始字符串的形式是在普通字符串文字量前加 r 或 R 前缀，如R"abcdefg"　　 r"C:\courses\pathon\progs"原始字符串里的 \ 不作为换意符，在相应 str 对象里原样保留除了位于单/双引号前的反斜线符号引入原始字符串机制，只是为了使一些字符串的写法简单r"C:\courses\pathon\progs" 的等价写法是：

"C:\\courses\\pathon\\progs"写模式匹配正文里的 \ 时情况更麻烦，匹配一个 \ 需要写 \\\\有关详情见 Python 文档的 HOWYO。后面将提到两个常用情况正则表达式Python 正则表达式包 re 规定了一组特殊字符，称为“元字符”。它们在匹配字符串时起着特殊的作用。这种字符一共 14 个. ^ $ * + ? \ | { } [ ] ( )

注意：这些字符在（常规）字符串里都是普通字符（“\”除外），只有在把字符串作为正则表达式使用时，它们有特殊的意义非特殊字符称为常规字符，是描述正则表达式的基础正则表达式串里的常规字符在匹配中只与自己匹配如果一个正则表达式串只包含常规字符，它就只能与自己匹配。也就是说，常规字符串是最基本的正则表达式在介绍正则表达式元字符的使用之前，先介绍 re 包提供的几个操作可以通过这些操作去使用正则表达式（还有其他方式，后面介绍）在下面函数说明中，参数表里的 pattern

表示描述正则表达式的字符串（模式串），string

表示被处理的字符串，repl

表示替换串正则表达式生成正则表达式对象：pile( pattern, flag = 0)从 pattern 生成对应的正则表达式对象。可用于下面几个操作。例：r1 = pile("abc") 生成 "abc" 对应的正则表达式对象赋给变量 r1re 包的操作都有 flag 选项。re 专门提供了一组特殊标记，这里不考虑实际上，下面几个操作都能自动从 pattern 串生成正则表达式对象。用 compile 生成 对象并记入变量，可以避免在重复使用中重复生成。下面函数的 pattern 参数都可以用正则表达式串或对象作为实参检索：re.search( pattern, string, flag = 0)在 string

里检索与 pattern

匹配的子串。如找到就返回一个 match 类型的对象；没找到时返回 Nonematch 对象里记录成功匹配的相关信息，可以根据需要取出和使用。也可以简单地把它作为一个真值用于逻辑判断正则表达式匹配：re.match( pattern, string, flag=0)检查 string 是否有与 pattern 匹配的前缀，匹配成功时返回相应的 match 对象，否则返回 None。例：re.search( r1, "aaabcbcbabcb") 成功，但re.match( r1, "aaabcbcbabcb") 返回 None分割：re.split( pattern, string, maxsplit=0, flags=0)以 pattern 作为分割串将 string 分段，maxsplit 指明分割数，0 表示做完整个 string。函数返回分割得到的字符串的表。例

re.split(' ', "abc abb are not the same")

得到： ['abc', 'abb', 'are', 'not', 'the', 'same']

re.split(" ", "1 2　3　 4") # 分割出了几个空串

得到： ['1', '2', '', '3', '', '', '4']正则表达式找到所有匹配串：re.findall( pattern, string, flags=0 )本函数返回一个表，其元素按顺序给出 string 里与 pattern 匹配的（从左到右非重叠的）各个子串如果模式里只有常规字符，做这种匹配的价值不大，因为结果表里所有的字符串相同。但用一般的正则表达式模式，情况就会不同还有操作后面介绍，下面逐步介绍正则表达式的情况。正则表达式的描述如前所说，Python 标准库包 re 的正则表达式就是一类特殊形式的字符串，可用于 re 里定义的一些函数，完成一些字符串操作正则表达式的最基本组合是顺序组合 ，若



匹配 s，

匹配 t，那么  匹配 s+t（s, t 为字符串，Python 写法 s+t 是两个字符串的拼接）注意，在正则表达式里，同样可以（也常常需要）写普通 Python 字符串使用的换意字符，如 \n 表示换行，\t 表示制表符等正则表达式里的空格也是常规字符，它只与自己匹配下面分门别类介绍一些特殊的描述形式，需要注意两点：　一种表达式（或元符号）的构造形式（描述形式）　这种表达式能匹配怎样的字符串（集合）字符组字符组表达式 [...] 匹配括号中列出的任一个字符[abc]

可以匹配字符 a 或 b 或 c区间形式 [0-9] 是顺序列出的缩写，匹配所有十进制数字字符[0-9a-zA-Z]

匹配所有字母（英文字母）和数字[^...] 中的 ^ 表示求补，这种模式匹配所有未在括号里列出的字符[^0-9] 匹配所有非十进制数字的字符[^ \t\v\n\f\r]

匹配所有非空白字符（非空格/制表符/换行符）如果需要在字符组里包括 ^，就不能放在第一个位置，或者写 \^；如果需要在字符组包括 -

]，也必须写 \- 或 \]圆点字符 . 匹配任意一个字符a..b 匹配所有以 a 开头 b 结束的四字符串a[1-9][0-9] 匹配 a10, a11, ..., a99常用字符组为了方便，re 用换意串形式定义了几个常用字符组，包括：\d：与十进制数字匹配，等价于 [0-9]\D：与非十进制数字的所有字符匹配，等价于 [^0-9]\s：与所有空白字符匹配，等价于 [ \t\v\n\f\r]\S：与所有非空白字符匹配，等价于 [^ \t\v\n\f\r]\w：与所有字母数字字符匹配，等价于 [0-9a-zA-Z]\W：与所有非字母数字字符匹配，等价于 [^0-9a-zA-Z]还有些类似描述，提供这些只是为了使用方便p\w\w\w 与 p 开头随后三个字母数字字符的串匹配重复常希望写重复匹配的模式（部分），任意次或若干次重复基本重复运算符是 *，* 与 

的 0 次或任意多次出现匹配re.split('[ ,]*', s)

将串按空格和逗号（任意个）切分re.split('[ ,]*', '1 2, 3　 4, , 5')

得到 ['1', '2', '3', '4', '5']re.split('a*', 'abbaaabbdbbabbababbabb')

得到 ['', 'bb', 'bbdbb', 'bb', 'b', 'bb', 'bb']注意，re.match('ab*', 'abbbbbbc') 时，模式可以与 a 匹配，与 ab 匹配，等等，它究竟匹配那个串？两种可能贪婪匹配：与有可能匹配的最长子串匹配在这里 ab* 匹配 abbbbbb，* 运算符做贪婪匹配非贪婪匹配：与有可能匹配的最短子串匹配重复与 * 略微不同的重复运算符 + 表示 1 次或多次重复例：描述正整数的一种简单模式 '\d+'，等价于 '\d\d*'可选（片段）用 ? 运算符表示?

表示 0 次或 1 次重复例，描述整数（表示整数的字符串）的一种简单模式 '-?\d+'确定次数的重复用 {n} 表示，{n} 与 

匹配的串的 n 次重复匹配描述北京常规的固话号码：'(010-)?[2-9][0-9]{7}'注意：这种表达式描述的通常是实际字符串集合的超集，但可以用注意：上面描述中出现了圆括号，描述 ? 的作用范围*, ?, {3}

有作用范围问题（优先级），它们作用于最小表达式'010-?' 表示其中的 '–' 可选，'(010-)?' 表示整个段可选重复重复范围用 {m,n} 表示，{m,n} 与 

匹配的串的 m 到 n 次重复匹配a{3,7} 与 3 到 7 个 a 构成的串匹配go{2,10}gle 与 google, gooogle, ..., goooooooooogle 匹配重复范围中的 m 和 n 均可以省略，{,n} 表示 {0,n}，而 {m,} 表示 {m,infinity}。另外几种重复都可以用这个形式表示：{n} 等价于 {n,n}，? 等价于 {0,1}* 等价于 {0,infinity}，+ 等价于 {1,infinity} * + ? {m,n}

都采取贪婪匹配策略，与被匹配串中最长的合适子串匹配（因为它们可能出现更大的模式里，要照顾上下文的需要）与这些运算符对应的有一组非贪婪匹配运算符*? +? ?? {m,n}?（各运算符后增加一个问号）的语义与上面几个运算符分别对应，但采用非贪婪匹配（最小匹配）的策略选择选择运算符 | 描述两种或多种情况之一的匹配。如果 

或者  与一个串匹配，那么

| 就与之匹配a|b|c

可以匹配 a 或者 b 或者 c，[abc]

可以看作其简写。后者更简洁方便，有时还能简写如 [a-z]，但只能用于单字符选择'0+|[1-9]\d*'

匹配 Python 程序的十进制整数（注意，Python 把负号看作运算符）。如果已知为独立字段，就可以用这个模式。但它会与 0123 的前段 0 匹配。进一步考虑还有上下文要求（如需排除 abc123,

a123b 里的 123），这方面的问题后面考虑| 的结合力最弱，比顺序组合还弱。上面描述不需要括号实例：匹配国内固定电话号码：'0\d{2}-\d{8}|0\d{3}-\d{7,8}'注意，这个正则表达式描述的是实际集合的超集，如两位区号实际上只有 010/020/021/022，这段可写为

0(10|20|21|22|23)-\d{8}，另一段可以精化为 0[3-9]\d{2}-\d{7,8}首尾匹配行首匹配：以 ^ 符号开头的模式，只能与一行的前缀子串匹配re.search('^for', 'books for children') 得到 None行尾匹配：以 $ 符号结尾的模式，只与一行的后缀匹配re.search('fish$', 'cats like to eat fishes') 得到 None注意，“一行的”前缀/后缀包括整个被匹配串的前缀和后缀。如串里有换行符，还包括换行符前的子串（一行的后缀）和其后的子串（前缀）串首匹配：\A 开头的模式只与被匹配串的前缀匹配串尾匹配：\Z 结束的模式只与被匹配串的后缀匹配至此我们已经介绍了所有 14 个元字符应特别提出换意字符 \，以它作为引导符定义了一批换意元字符，如 \d, \D

等。它还用于在模式串里写非打印字符（如 \t, \n, ...）和\\ 等，在 [] 里写 \^, \-, \]单词边界两个换意元字符用于描述特殊子串的边界\b 描述单词边界，它表示单词边界匹配一个空串。单词是字母数字的连续序列，边界就是非字母数字字符或无字符（串开头/结束）这里有个糟糕的问题：在 Python 字符串中 \b 表示退格符，而在 re 的正则表达式里 \b 表示单词边界。两种办法：将 \ 双写，它表示把 \ 本身送给 pile ，如 '\\b123\\b'不匹配 abc123a 等里的 123，但匹配 (123,123) 里的 123用 Python 原始字符串，其中的 \ 不换意。上面的模式可写为 r'\b123\b'实例：匹配 Python 整数的模式可写为 '\\b(0+|[1-9]\d*)\\b'用原始字符串可简单地写 r'\b(0+|[1-9]\d*)\b'。例如写 re_int = r'\b(0+|[1-9]\d*)\b'单词边界实例：一般的可能带正负号的整数，可以考虑用模式'[+-]?\\b(0+|[1-9]\d*)\\b'但它匹配 x+5

里的 +5，但不匹配 3 + - 5 里的 - 5。写这种表达式和使用时，都需要考虑被匹配对象的情况例：求一个 Python 程序里出现的所有整数之和def sumInt(fname):　　re_int = '\\b(0+|[1-9]\d*)\\b'　　inf = open(fname)　　if inf == None:　　　　return 0　　ilist = map(int, re.findall(re_int, inf.read())) # 可改为分行读入　　s = 0　　for n in ilist:　　　　s += n　　return s边界\B 是 \b 的补，也是匹配空串，但要求相应位置是字母或数字实例：>>> re.findall('py.\B', 'python, py2, py342, py1py2py4')['pyt', 'py3', 'py1', 'py2']匹配对象（match 对象）许多匹配函数在匹配成功时返回一个 match 对象，对象里记录了所完成匹配的有关信息，可以取出使用。下面介绍这方面的情况首先，这样的匹配结果可以用于逻辑判断，成功时得到的 match 对象总表示逻辑真，不成功得到的 None 表示假。例如match1 = re.search( pt, text)if match1:　　... match1 ... text ... # 使用 match 对象的处理操作match 对象提供了一组方法，用于检查与匹配有关的信息。下面介绍一些基本用法，更多信息（包括可选参数）见 re 包文档在下面介绍中，mat

表示通过匹配得到的一个 match 对象取得被匹配的子串：mat.group()在一次成功匹配中，所用的正则表达式匹配了目标串的一个子串，操作 mat.group() 给出这个子串匹配对象（match 对象）在目标串里的匹配位置：mat.start()得到 mat

代表的成功匹配在目标串里的实际匹配位置，这是目标串的一个字符位置（下标）目标串里被匹配子串的结束位置：mat.end()这个位置采用常规表示方式。设 text 是目标串，有如下关系：mat.group() == text[mat.start():mat.end()]目标串里被匹配的区间：mat.span()得到匹配的开始和结束位置形成的二元组mat.span() == mat.start(), mat.end()mat.re 和 mat.string 分别取得得到这个 match 对象所做匹配的正则表达式对象和目标串应用实例见后模式里的组（group）正则表达式描述中的另一个重要概念是组（group）圆括号括起的模式段 (...) 也是模式，它与被括子模式匹配的串匹配。但在此同时还确定了一个被匹配的“组”（字符段）成功匹配得到的组从 0 开始编号，可以通过 mat.group(n) 获取组 0 就是整个模式匹配的串，用 mat.group() 获得（默认参数）模式里每对圆括号确定一个组，按开括号的顺序编号，例如m = re.search('.((.)e)f', 'abcdef') # 执行后：m.group() 是 'cdef'，m.group(1) 是 'de'，m.group(2) 是 'd'm.groups() 得到包含从编号 1 开始的各组的序对m.groups() 得到 ('de', 'd')成功匹配确定的各个组可用 \n

形式在模式里其他地方“引用”，表示要求在这个位置匹配同一个子串。这里的 n 表示一个整数序号模式里的组例：r'(.{2}) \1'

可匹配 'ok ok'

或 'no no'，不匹配 'no oh'注意，组编号应该是 \1, \2 等，但在普通字符串里，\1 表示二进制编码为 1（经常可以看到被写成 0x01）的那个（特殊）字符，而现在需要模式串里出现 \1, \2 等为此上面模式需要写成 '(.{2}) \\1'，或者用原始字符串形式简化写法，写为　r'(.{2}) \1'(?...) 形式的片段称为“扩充表示”，