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

数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/1/3，字符串字符串的相关概念Python字符串（回顾）字符串匹配和算法进一步的模式匹配问题正则表达式Python的正则表达式应用举例数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/2/字符串讨论字符串，首先要有一个确定的字符集“字符”是一个抽象概念，字符集是有穷的一组字符构成的集合人们经常考虑在计算机里使用的标准字符集，实际上，完全可以拿任意数据元素的集合作为字符集字符串（简称串）是特殊的线性表，表中元素取自选定的字符集其不同于一般表的特点是支持一组以串为对象的操作长度：串中字符的个数称为串的长度长度为0的串称为空串在任意一个字符集里，只有唯一的一个空串与一般的表类似：字符串里的字符顺序排列，串里的每个字符有其确定位置我们用0开始的自然数表示位置数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/3/字符串串相等：串的相等基于字符集里的字符定义s1和s2相等，如果其长度相等，而且对应位置的各对字符分别相同假定字符集中的字符有一个全序，串的字典序定义如下：对于串定义s1s2，如果存在一个k使ai=bi(i=0,1,…k-1)而且akbk或者nm而且对i=0,1,…n-1都有ai=bi显然，字典序是字符串集合上的一个全序11021101,mnbbbsaaas串与串的最重要运算是拼接（concatenate）上面s1和s2的拼接是串显然，s的长度等于s1和s2的长度之和在Python里拼接运算用+表示110110mnbbbaaas数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/4/字符串两个串之间还有一个重要的关系是“子串关系”称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也都是该串本身的子串数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/5/字符串两种特殊子串：如果存在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语言）数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/6/字符串的理论字符串集合和拼接操作构成了一种代数结构空串是拼接操作的“单位元”（幺元）有结合律，无交换律串集合加上拼接操作，构成一个半群一种典型的非交换半群有单位元，因此是一个幺半群关于串的理论有许多研究工作基于串和串替换，研究者提出了post系统这是一种与图灵机等价的计算模型（串）重写系统（rewritingsystem）是计算机理论的一个研究领域，一直非常活跃，有许多重要结果和应用数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/7/字符串抽象数据类型可以考虑下面的字符串抽象数据类型：ADTString: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在串里的出现子串检索（子串匹配）是字符串的核心操作，后面将详细研究数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/8/字符串的实现串是字符的线性序列：可采用线性表的实现方式，用顺序表示和链接表示。例如用能动态变化大小的顺序表作为实现方式（如果需要表示可变的字符串）还可以根据串本身的特点和串操作的特点，考虑其他表示方式。当然，无论如何还是基于顺序存储或/和链接关键问题：表示方式应能很好支持串的管理和相关操作的实现字符串表示的两个问题：串内容存储。两个极端：1，连续存储在一块存储区；2，一个字符存入一个独立存储块，链接起来。也可以采用某种中间方式，把串中字符分段保存在一组存储块里，链接起这些存储块串结束的表示，不同字符串长度可能不同，必须表示串到哪里结束。两种基本方式：1，用专门数据域记录字符串长度；2，用一个特殊符号表示串结束（例如C语言的字符串采用这种方式）数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/9/字符串的实现现在考虑字符串的操作许多串操作是线性表操作的具体实例，包括串拼接下面考虑一个特殊的操作串替换牵涉到三个串：被处理的主串s，作为被替换对象需要从s中替换掉的子串t，以及用于代换t的t'由于t可能在s中出现多次，因此需要通过一系列具体的子串代换完成整个替换由于多次出现可能重叠（回忆前面的例子），只能规定一种代换顺序（例如从左到右），一次代换破坏的子串不应再代入新串一次子串代换后，应该从代入的新串之后继续工作。即使代入新串之后形成的部分能与t匹配，也不应在本次替换中考虑很容易看到：串替换的关键是找到匹配数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/10/实际语言里的字符串许多语言提供了标准的字符串功能，如C语言标准库有一组字符串函数（string.h），一些C语言系统提供的扩展的字符串库；C++语言标准库里的字符串库stringJava标准库的字符串库许多脚本语言（包括Python）提供了功能丰富的字符串库许多实际字符串库用动态顺序表结构作为字符串的表示方式这样既能支持任意长的字符串又能比较有效地实现各种重要的字符串操作实际上，支持不同的字符串操作，可能需要不同的实现，例如有些计算工作需要记录和处理极长的字符串，如支持操作MB（大约为106）或更长的字符串，采用连续存储可能带来管理问题被编辑文本也是字符串，实现编辑器操作要考虑专门的字符串表示数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/11/Python字符串Python内部类型str是抽象字符串概念的一个实现str是不变类型，str对象创建后的内容（和长度）不变但不同的str对象长度不同，需要记录Python采用一体式的连续形式表示str对象，见下图其他长度len串内容存储区...str对象的操作分为两类：获取str对象的信息，如得到串长，检查串内容是否全为数字等基于str对象构造新的str对象，包括切片，构造小写/大写拷贝，各种格式化等。切分是构造包含多个字符串的表一些操作属子串匹配，如count检查子串出现次数，endwith检查后缀，find/index找子串位置等。这类操作最重要，后面专门讨论数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/12/字符串操作的实现检查字符串内容的操作可以分为两类O(1)时间的简单操作，包括len和定位访问（也构造新字符串）其他都需要扫描整个串的内容，包括不变序列的共有操作（in、notin、min/max），各种字符类型判断（如是否全为数字）o需通过一个循环逐个检查串中字符完成工作，O(n)操作o子串查找和匹配的问题后面讨论需要构造新字符串的操作情况比较复杂，基本模式都包括两部分工作1,为新构造的串安排一块存储2,根据被操作串（和可能的参数串）构造出一个新串以s[a:b:k]为例，算法：1,根据a、b、k算出新字符串的长度2,foriinrange(a,b,k):拷贝s[i]到新串里的下一个空位数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/13/字符串匹配（子串查找）最重要的字符串操作是子串匹配，称为字符串匹配（stringmatching）或字符串查找（stringsearching）【有教科书称为模式匹配（patternmatch），但实际上模式匹配是内涵更广的概念】wiki：字符串匹配问题：假设有两个串（ti,pj是字符）t=t0t1t2…tn-1称为目标串p=p0p1p2…pm-1称为模式串通常有mn。字符串匹配就是在t中查找与等于p的子串的过程（这一定义可以推广，后面讨论）如前所述，串匹配是最重要的字符串操作，也是其他许多重要字符串操作的基础。实际中n可能非常大，m也可以有一定规模，也可能需要做许多模式串和/或许多目标串的匹配，有关算法的效率非常重要数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/14/串匹配许多计算机应用的最基本操作是字符串匹配。如用编辑器或字处理系统工作时，在文本中查找单词或句子（中文字或词语），在程序里找拼写错误的标识符等email程序的垃圾邮件过滤器，google等网络检索系统各种防病毒软件，主要靠在文件里检索病毒模式串在分子生物学领域：DNA细胞核里的一类长分子，在遗传中起着核心作用。DNA内有四种碱基：腺嘌吟(adenine)，胞嘧啶(cytosine)，鸟嘌吟(guanine)，胸腺嘧啶(thymine)。它们的不同组合形成氨基酸、蛋白质和其他更高级的生命结构DNA片段可看作是a,c,g,t构成的模式，如acgatactagacagt考查在蛋白质中是否出现某个DNA片段，可看成与该DNA片段的串匹配问题。DNA分子可以切断和拼接，切断动作由各种酶完成，酶也是采用特定的模式确定剪切位置数据结构和算法（Python语言版）：字符串裘宗燕，2020/6/27-/15/串匹配实际中模式匹配的规模（n和m）可能非常大，而且有时间要求被检索的文本可能很大网络搜索需要处理亿万的网页防病毒软件要在合理时间内检查数以十万计的文件（以GB计）运行在服务器上的邮件过滤程序，可能需要在一秒钟的时间内扫描数以万计的邮件和附件为疾病/药物研究/新作物培养等生物学工程应用，需要用大量DNA模式与大量DNA样本（都是DNA序列）匹配由于在计算机科学、生物信息学等许多领域的重要应用，串模式匹配问题已成为一个极端重要的计算问题。高效的串匹配算法非常重要有几个集中关注字符串匹配问题的国际学术会议，曾经有过专门的国际竞赛（见wiki页和万维网）目前全世界一大半的计算能力是在做串模式匹配（做DN