《数据结构与算法-Python语言描述》读书笔记（4）第4章字符串（关键词：数据结构/算法/Python/字符串）_《数据结构——python语言描述》张光河 读后感

第4章 字符串

4.1 字符集 、字符串和字符串操作

字符串可以看做是一类特殊的线性表，表中元素取自选定的字符集（如ASCII字符集或者Unicode字符集）。

4.1.1 字符串的相关概念

与字符串有关的一些主要概念：
- 字符串的长度
- 字符在字符串里的位置
- 字符串相等
- 字典序（读者笔记：完整概念见书上。这里写下我的理解：
就是两个字符串，从左向右看，比较它们下标相同的各对字符，遇到第一对不同字符的字符序，就决定了这两个字符串的顺序。举两个例子吧：
abc < abcd，虽然abc和abcd的前3个字符相同，但后者较长。
abc < add，虽然abc和add两个字符串的长度相同，但后者的第2个字符比前者大。
）
- 字符串拼接：Python语言里加号（+）可以用来表示字符串的拼接。
- 子串关系：（读者笔记：完整解释见书上。）空串是任何一个字符串的子串；任何字符串也是其自身的子串。
- 前缀和后缀是两种特殊子串：
- 其他有用的串运算如：拼接、串替换。
与字符串有关的一些研究
(s1 + s2) + s3 = s1 + (s2 + s3)

4.1.2 字符串抽象数据类型

Python中，字符串定义为一种不变数据类型。下面是一个简单的字符串ADT，其中定义了一些字符串操作：

4.2 字符串的实现

4.2.1 基本实现问题和技术

字符串是字符的线性序列，可以采用线性表的各种实现技术实现，用顺序表或链接表的形式表示。

（读者笔记：书上这里分析的很详细，建议仔细看书。）

4.2.2 实际语言里的字符串

4.2.3 Python的字符串

（读者：书上分析的很详细！！）

4.3 字符串匹配（子串查找）

4.3.1 字符串匹配

应用

• 使用编辑器时，在文本中查找单词或句子，程序里找拼写错误
• 对于Email服务器和客户端的程序的垃圾邮件过滤器
• 谷歌等搜索引擎。。
• 防病毒软件。。

实际的串匹配问题

4.3.2 串匹配和朴素匹配算法

串匹配算法

朴素的串匹配算法

最简单的朴素匹配算法采用最直观可行的策略：
①从左到右逐个字符匹配；
②发现不匹配时，转去考虑目标串里的下一个位置是否与模式串匹配。
（读者：抄代码。。）

def naive_matching(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                      # 无匹配，返回特殊值
1
2
3
4
5
6
7
8
9
10
11

（读者笔记：原书中，对朴素的串匹配算法的缺点进行了分析，值得一读。）

4.3.3 无回溯串匹配算法（KMP算法）

（读者笔记：高能预警！！！这个算法比较复杂，不太容易理解！！！）

基本考虑

（读者笔记：好好看书上的分析！！！）

问题分析

（读者笔记：没看懂。。）

KMP算法

（读者：抄代码）
核心的匹配循环：

while j < n and i < m:         # i==m说明找到匹配
    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]
1
2
3
4
5
6
7

前两个if分支合并、简化：

while j < n and i < m:              # i==m说明找到匹配
    if i == -1 or t[j] == p[i]:     # 比较下一对字符
        j, i = j+1, i+1
    else:                           # 从penxt取得p的下一字符位置
        i = pnext[i]
1
2
3
4
5

下面是基于上述循环的匹配函数定义：

def matching_KMP(t, p, pnext):
    """ KMP串匹配, 主函数. """
    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-1
    return -1                        # 无匹配，返回特殊值
1
2
3
4
5
6
7
8
9
10
11
12

构造pnext表：分析

（读者：先跳过吧，这么多符号文字。。）

递推计算最长相等前后缀的长度

（读者：先跳过吧，这么多符号文字。。）

pnext表构造算法

（读者：继续抄代码。。）

def gen_pnext(p):
    """生成针对p中各位置i的下一检查位置表，用于KMP算法"""
    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    
1
2
3
4
5
6
7
8
9
10
11

函数开始时建立一个元素值全为-1的表，循环中为下标0之后的各元素赋值。

pnext生成算法的改进

def gen_pnext(p):
    """生成针对p中各位置i的下一检查位置表，用于KMP算法，
    有少许修改的优化版本。
    """
    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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

KMP算法的时间复杂性及其他

4.4 字符串匹配问题

4.4.1 串匹配/搜索的不同需要

模式，字符串和串匹配（串检索）

通配符和简单模式语言

正则表达式

4.4.2 一种简化的正则表达式

模式语言

• 圆点“.”可以匹配任意字符。
• “^”只匹配目标串的开头，不匹配任何具体字符。
• “$”只匹配目标串的结束，不匹配任何具体字符。
• “*”表示其前面那个字符可匹配0个或任意多个相同字符。

匹配算法

（读者：详细看书。。抄代码）

def match(re, text):
    def match_here(re, i, text, j):
        """检查从text[j]开始的正文是否与re[i]开始的模式匹配"""
        while True:
            if i == rlen:
                return True
            if re[i] == '$':
                return i+1 == rlen and j ==tlen
            if i+1 < rlen and re[i+1] == '*':
                return match_star(re[i], re, i+2, text, j)
            if j == tlen or (re[i] != '.' and re[i] != text[j]):
                return False
            i, j = i+1, j+1

    def match_star(c, re, i, text, j):
        """在text里跳过0个或多个c后检查匹配"""
        for n in range(j, tlen):
            if match_here(re, i, text, n):
                return True
            if text[n] != c and c != '.':
                break
        return False

    rlen, tlen = len(re), len(text)
    if re[0] == '^':
        if match_here(re, 1, text, 0):
            return 1
    for n in range(tlen):
        if match_here(re, 0, text, n):
            return n
    return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

（读者：以下注释没好好看。。）

4.5 Python正则表达式

4.5.1 概况

4.5.2 基本情况

原始字符串

原始字符串（raw string，也是文字量）是在Python里书写字符串文字量的一种形式，这种文字量的值和普通文字量一样，就是str类型的字符串对象。形式是在普通字符串文字量前加r或R前缀，例如：
R”abcdefg” r”C:\python\”

元字符（特殊字符）

（读者：去读原书吧）

4.5.3 主要操作

在下面的函数说明中，参数表里的pattern表示模式串（描述正则表达式的字符串），string表示被处理的字符串，repl表示替换串，即操作中使用的另一个字符串。
- 生成正则表达式对象：re.compile(pattern, flag=0)，例如：
r1 = re.compile(“abc”)
- re.search(pattern, string, flag=0)
在string里检索与pattern匹配的子串。如找到就返回一个match类型的对象（读者：这里我有疑问，什么是match类型的对象？？）；否则返回None。match对象里记录成功匹配的相关信息，可以根据需要检查和使用。也可以把match对象简单作为真值用于逻辑判断。
- 匹配：re.match(pattern, string, flag=0)
检查string是否存在一个与patter匹配的前缀。匹配成功时返回相应的match对象，否则返回None。例如：
re.search(r1, “aaabcbcbabcb”) # 将匹配成功
re.match(r1,”aaabcbcbabcb”) # 返回None
- 分割：re.split(pattern, string, maxsplit=0, flags=0)

• 找出所有匹配字符串：re.findall(pattern, string,flags=0)

4.5.4 正则表达式的构造

字符组

字符组描述符：

与方括号中列出的字符序列中的任一字符匹配。字符组里字符的排列顺序并不重要。例如，[abc]可以与字符a或b或c匹配。
还有一些其他形式：
- 区间形式（顺序列出字符形式的）是字符组描述的缩写形式：
例如字符组[0-9]匹配所有十进制数字字符；
[0-9a-zA-Z]能匹配所有的数字和字母（英文字母）；
[34ad-fs-z]什么意思自己猜啊。。
- 特殊形式[^…]表示对^之后列出的字符组求补。
例如：字符组[^0-9]匹配非十进制数字的所有字符。

圆点字符(.)：圆点是“通配符”，能匹配任何字符。

模式串a..b匹配所有以a开头b结束的4字符串。

为了方便，re采用转移串的形式定义了一些常用字符组，包括：

重复

重复描述符：

re正则表达式的基本重复运算符是“*”，模式α*要求匹配模式α能匹配的字符串的0次或任意多次重复。例如，re.split(‘[ ,]*’, s)将按（任意多个）空格和逗号切分字符串s。例如：

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

可选描述符：

“？”是可选（片段）描述符表示，“α？”可以与空串或α匹配的字符串匹配，即，它要求与α匹配的字符串的0次或1次重复匹配。

重复次数描述符：

确定次数的重复用{n}描述，α{n}与α匹配的串的n次重复匹配。

重复次数的范围描述符：

重复次数的范围用{m,n}描述。例如，α{m,n}与α匹配的串的m到n次重复匹配，包括m次和n次。
例如，a{3,7}与3个到7个a构成的串匹配。

选择

选择描述符：

描述符“|”描述与两种或多种情况之一的匹配。如果α或者β与一个串匹配，那么α | β也与这个串匹配。

首尾描述符

行首描述符：

以“^”符号开头的模式，只能与一行的前缀子串匹配。
re.search(‘^for’, ‘books for children’)将得到None；
re.search(‘^for’, ‘books\nfor children’)将匹配成功。

行尾描述符：

以“$”符号结尾的模式只与一行的后缀子串匹配。
（读者：例子见书上）

串首描述符：

\A开头的模式只与整个被匹配串的前缀匹配。

串尾描述符：

\Z结束的模式只与整个被匹配串的后缀匹配。

单词边界

再介绍两个转义元字符，用于描述特殊子串的边界。
\b描述单词边界，它在实际单词边界位置匹配空串（不匹配实际字符）。单词是字母数字的任意连续序列，其边界就是非字母数字的字符或者无字符（串的开头/结束）。

匹配对象（match对象）

许多匹配函数在匹配成功时返回一个match对象，其中记录了所完成的匹配中得到的信息，可以根据需要取用。
下面的介绍中，mat总表示通过匹配得到的一个match对象。
- 取得被匹配的子串：mat.group()
- 在目标串里的匹配位置：mat.start()
- 目标串里被匹配子串的结束位置：mat.end()
- 目标串里被匹配的区间：mat.span()
- 其他，mat.re和mat.string（这两个表达式是数据域访问，不是函数）

模式里的组（group）

（读者：这一部分看的很迷糊。。）

其他匹配操作

正则表达式对象

4.5.5 正则表达式的使用

本章总结

练习

参考文献：
1.《数据结构与算法-Python语言描述》。