【Algorithms 4】算法(第4版)学习笔记 23 - 5.4 正则表达式

news/2024/4/19 21:10:13/

文章目录

    • 前言
    • 参考目录
    • 学习笔记
      • 1:正则表达式
      • 1.1:表示
      • 1.2:快捷表示
      • 2:正则表达式与非确定有限状态自动机 REs and NFAs
      • 2.1:二元性
      • 2.2:模式匹配实现
      • 2.3:非确定有限状态自动机 Nondeterministic finite-state automata
      • 2.4:非确定性
      • 3:NFA 模拟
      • 3.1:demo 演示
      • 3.2:Java 实现
      • 3.3:分析
      • 4:NFA 构造
      • 4.1:构造与正则表达式对应的 NFA
      • 4.2:实现
      • 4.3:demo 演示
      • 4.4:Java 实现
      • 4.5:分析
      • 5:非正则表达式
      • 6:背景
      • 7:小结

前言

本篇主要内容包括:正则表达式非确定有限状态自动机 NFA

建议在学习本篇之前先行学习或回顾上一篇子字符串查找的内容。

参考目录

  • B站 普林斯顿大学《Algorithms》视频课
    (请自行搜索。主要以该视频课顺序来进行笔记整理,课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。)
  • 微信读书《算法(第4版)》
    (本文主要内容来自《5.4 正则表达式》)
  • 官方网站
    (有书本配套的内容以及代码)

学习笔记

注1:下面引用内容如无注明出处,均是书中摘录。
注2:所有 demo 演示均为视频 PPT demo 截图。
注3:如果 PPT 截图中没有翻译,会在下面进行汉化翻译,因为内容比较多,本文不再一一说明。

1:正则表达式

1.1:表示

![L20-54RegularExpressions_06]

对应书本章节:《5.4.1 使用正则表达式描述模式》

  • 5.4.1.1 连接操作
  • 5.4.1.2 或操作
  • 5.4.1.3 闭包操作
  • 5.4.1.4 括号

1.2:快捷表示

![L20-54RegularExpressions_07]

对应书本章节:《5.4.2 缩略写法》

  • 5.4.2.1 字符集描述符
  • 5.4.2.2 闭包的简写
  • 5.4.2.3 转义序列

2:正则表达式与非确定有限状态自动机 REs and NFAs

2.1:二元性

![L20-54RegularExpressions_16]

RE(正则表达式): 简洁描述一组字符串的方法。
DFA(确定有限状态自动机): 一种机器,用于判断给定的字符串是否属于预定义的字符串集合。

克林宁定理(Kleene’s theorem):

  • 对于任何确定有限状态自动机(DFA),都存在一个能够描述相同字符串集合的正则表达式(RE)。
  • 对于任何正则表达式(RE),都存在一个能够识别相同字符串集合的确定有限状态自动机(DFA)。

2.2:模式匹配实现

![L20-54RegularExpressions_18]

类似于 KMP 算法:

  • 不需要文本输入流回溯。
  • 确保二次时间复杂度(通常为线性时间)。

基础抽象概念: 非确定有限状态自动机(NFA)。

基本策略:[应用克林宁定理]

  • 从正则表达式构建 NFA。
  • 使用文本作为输入模拟 NFA。

2.3:非确定有限状态自动机 Nondeterministic finite-state automata

![image-20240402093803403]

对应书本章节:《5.4.4 非确定有限状态自动机》。

![image-20240402094701193]

也有可能进入错误状态并停滞:

![image-20240402095141143]

![image-20240402095201507]

2.4:非确定性

![L20-54RegularExpressions_23]

Q. 如何确定一个字符串是否被自动机所匹配?
DFA(确定有限状态自动机): 判定较为简单,因为对于每个状态和输入字符,恰好有一个适用的转换。
NFA(非确定有限状态自动机): 可能存在多个适用的转换;需要正确选择其中一个!

Q. 如何模拟 NFA?
A. 系统地考虑所有可能的转换序列来进行模拟。

3:NFA 模拟

3.1:demo 演示

![image-20240402163328370]

![image-20240402163446270]

该 demo 建议多观看几遍视频理解操作步骤。

3.2:Java 实现

edu.princeton.cs.algs4.NFA

![image-20240402164427969]
edu.princeton.cs.algs4.NFA#NFA

/*** Initializes the NFA from the specified regular expression.** @param  regexp the regular expression*/public NFA(String regexp) {this.regexp = regexp;m = regexp.length();Stack<Integer> ops = new Stack<Integer>();graph = new Digraph(m+1);for (int i = 0; i < m; i++) {int lp = i;if (regexp.charAt(i) == '(' || regexp.charAt(i) == '|')ops.push(i);else if (regexp.charAt(i) == ')') {int or = ops.pop();// 2-way or operatorif (regexp.charAt(or) == '|') {lp = ops.pop();graph.addEdge(lp, or+1);graph.addEdge(or, i);}else if (regexp.charAt(or) == '(')lp = or;else assert false;}// closure operator (uses 1-character lookahead)if (i < m-1 && regexp.charAt(i+1) == '*') {graph.addEdge(lp, i+1);graph.addEdge(i+1, lp);}if (regexp.charAt(i) == '(' || regexp.charAt(i) == '*' || regexp.charAt(i) == ')')graph.addEdge(i, i+1);}if (ops.size() != 0)throw new IllegalArgumentException("Invalid regular expression");}

edu.princeton.cs.algs4.NFA#recognizes

/*** Returns true if the text is matched by the regular expression.** @param  txt the text* @return {@code true} if the text is matched by the regular expression,*         {@code false} otherwise*/public boolean recognizes(String txt) {DirectedDFS dfs = new DirectedDFS(graph, 0);Bag<Integer> pc = new Bag<Integer>();for (int v = 0; v < graph.V(); v++)if (dfs.marked(v)) pc.add(v);// Compute possible NFA states for txt[i+1]for (int i = 0; i < txt.length(); i++) {if (txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')')throw new IllegalArgumentException("text contains the metacharacter '" + txt.charAt(i) + "'");Bag<Integer> match = new Bag<Integer>();for (int v : pc) {if (v == m) continue;if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.')match.add(v+1);}if (match.isEmpty()) continue;dfs = new DirectedDFS(graph, match);pc = new Bag<Integer>();for (int v = 0; v < graph.V(); v++)if (dfs.marked(v)) pc.add(v);// optimization if no states reachableif (pc.size() == 0) return false;}// check for accept statefor (int v : pc)if (v == m) return true;return false;}

3.3:分析

![L20-54RegularExpressions_32]

对应书本命题 Q:

![image-20240402164943402]

4:NFA 构造

4.1:构造与正则表达式对应的 NFA

![L20-54RegularExpressions_34]

状态: 为正规表达式(RE)中的每个符号创建一个状态,同时添加一个接受状态。

![L20-54RegularExpressions_35]

连接操作: 从字母表中字符对应的当前状态添加匹配转换边至下一个状态。

![L20-54RegularExpressions_36]

括号: 从括号所在的状态添加一条 ε - 转换边至下一个状态。

![L20-54RegularExpressions_37]

闭包操作: 对于每一个运算符,添加三条 ε - 转换边。

![L20-54RegularExpressions_38]

或表达式: 对于每一个 |(逻辑或)操作符,添加两条 ε - 转换边。

4.2:实现

![L20-54RegularExpressions_39]

目标: 编写一个程序来构建 ε - 转换有向图。

挑战: 记忆左括号以实现闭包和逻辑或;记忆逻辑或符号 | 以实现逻辑或操作。

解决方案: 维护一个栈结构。

  • 遇到 ( 符号时:将 ( 入栈。
  • 遇到 | 符号时:将 | 入栈。
  • 遇到 ) 符号时:弹出与之配对的 ( 及其间的所有 | 符号;然后根据闭包和逻辑或的规则,添加相应的 ε - 转换边。

4.3:demo 演示

![image-20240402173630494]

4.4:Java 实现

![L20-54RegularExpressions_42]

4.5:分析

![L20-54RegularExpressions_43]

对应书本命题 R:

![image-20240402174323446]

5:非正则表达式

![L20-54RegularExpressions_53]

反向引用:

  • \1 表示法用于匹配先前已匹配到的子表达式。
  • 这一特性在典型的正则表达式实现中得到支持。

某些非正则表达式的例子:

  • 形如 ww 的字符串,其中 w 是任意字符串,例如 beriberi
  • 包含复合数量 1 的单字符字符串,例如 111111
  • 含有相同数量 0 和 1 的二进制字符串,例如 01110100
  • Watson-Crick 互补的回文串,例如 atttcggaaat

注解: 使用反向引用进行模式匹配的问题属于难解问题(不可行或计算复杂度较高)。

6:背景

![L20-54RegularExpressions_54]

抽象机、语言及非确定性概念:

  • 是计算理论的基础。
  • 自20世纪30年代以来就被深入研究。
  • 是现代编程语言的基础。

编译器:

  • 编译器是一种程序,负责将源程序翻译成机器码。
  • KMP 算法处理的字符串模式可以转换为确定有限自动机(DFA)。
  • grep 工具使用的正则表达式可以转换为非确定有限自动机(NFA)。
  • javac 编译器将 Java 语言源代码编译为 Java 字节码。

7:小结

![L20-54RegularExpressions_55]

程序员:

  • 通过 DFA 模拟实现子串搜索功能。
  • 通过 NFA 模拟实现正则表达式模式匹配。

理论学者:

  • 正则表达式是描述一组字符串的紧凑表示方法。
  • NFA 是非确定性抽象机,其功能等价于正则表达式。
  • DFA、NFA 以及正则表达式都有其局限性。

你: 实际应用计算机科学的核心原理。

举例说明计算机科学中的关键范例:

  • 构建中间抽象层。
  • 挑选恰当的抽象模型!
  • 解决重要的实际问题。

(完)


http://www.ppmy.cn/news/1405458.html

相关文章

go: go.mod file not found in current directory or any parent directory.如何解决?

这个错误表明你正在执行 go get 命令&#xff0c;但是当前目录或任何父目录中都找不到 go.mod 文件。这可能是因为你的项目还没有使用 Go Modules 进行管理。 要解决这个问题&#xff0c;有几种方法&#xff1a; go mod init <module-name> 其中 <module-name>…

Quill文档(五):Delta格式

富文本编辑器缺乏一种表达其自身内容的规范。直到最近&#xff0c;大多数富文本编辑器甚至不知道它们自己的编辑区域中有什么内容。这些编辑器只是传递用户的HTML&#xff0c;以及解析和解释这些HTML的负担。在任何给定的时间&#xff0c;这种解释都会与主要浏览器供应商的解释…

OpenCV与AI深度学习 | OpenCV中八种不同的目标追踪算法

本文来源公众号“OpenCV与AI深度学习”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;OpenCV中八种不同的目标追踪算法 目标跟踪作为机器学习的一个重要分支&#xff0c;加之其在日常生活、军事行动中的广泛应用&#xff0c;受到…

深入理解计算机系统 家庭作业 2.70

/* 网上很多都是错的,有些甚至题目都没读对 该题的意思是,x可以用多少位的补码表示. x -2时,最少用n2位补码就可以表示了 即 10 这道题求的是n 函数的核心思路: 用左右移位后的结果&一个n位的掩码就得到 x的最少位.移位没造出数字丢失时,x的最少位可以再通过移位还原成…

pygame--坦克大战(一)

项目搭建 本游戏主要分为两个对象,分别是我方坦克和敌方坦克。用户可以通过控制我方的坦克来摧毁敌方的坦克保护自己的“家”,把所有的敌方坦克消灭完达到胜利。敌方的坦克在初始的时候是默认5个的(这可以自己设置),当然,如果我方坦克被敌方坦克的子弹打中,游戏结束。从…

Redission--分布式锁

Redission的锁的好处 Redission分布式锁的底层是setnx和lua脚本(保证原子性) 1.是可重入锁。 2.Redisson 锁支持自动续期功能&#xff0c;这可以帮助我们合理控制分布式锁的有效时长&#xff0c;当业务逻辑执行时间超出了锁的过期时间&#xff0c;锁会自动续期&#xff0c;避免…

【大数据运维】Hbase shell 常见操作

文章目录 一. DDL1. 表的DDL1.1. 创建表1.2. 删除表 2. 列族的DDL2.1. 增加一个列簇2.2. 删除列族2.3. 修改列族版本&#xff08;ing&#xff09; 二. DML1. 插入与更新数据2. 删除数据3. 清空表 三. DQL1. scan&#xff1a;查一批数据1.1. 查询全部1.2. 过滤rowkey1.3. 过滤列…

CS架构---Socket基础

目录 一、Socket简介1.1 通信模型1.2 类型1.3 创建和使用&#xff1a;1.4 地址族 二、客户/服务器模式2.1 服务器端&#xff08;Server Side&#xff09;2.2 客户端&#xff08;Client Side&#xff09;2.3 通信方式2.4 角色分工2.5 优点 三、Socket实战四、常见应用场景 一、S…

C语言程序10题

第101题 &#xff08;10.0分&#xff09; 难度:易 第2章 /*------------------------------------------------------- 【程序填空】 --------------------------------------------------------- 功能&#xff1a;计算平均成绩并统计90分以上人数。 --…

【微服务篇】深入理解分布式消息队列系统

分布式消息队列是一种在多个服务器、应用或服务之间进行消息传递的技术。它使得各个独立的组件可以通过异步消息进行通信&#xff0c;提高了系统的可扩展性、解耦性和可靠性。 典型应用场景 1. 异步处理 在许多系统中&#xff0c;某些任务的处理可能需要较长时间&#xff0c…

Stable Diffusion 推荐硬件配置和本地化布署

Stable Diffusion简介 Stable Diffusion是由Stability AI开发的一种强大的文本到图像(Text-to-Image)生成模型,它能够根据用户提供的文本描述,生成与之相关的高质量、高分辨率图像。下面我从原理、特点、应用三个方面对Stable Diffusion作简要介绍: 1、原理:Stable Diffusion…

什么是智慧驿站?智慧驿站有哪些功能?创新型智慧公厕解说

近年来&#xff0c;随着智能科技的迅速发展&#xff0c;人们对于城市生活的期望也逐渐提升。作为城市基础设施的一部分&#xff0c;智慧驿站应运而生。它不仅是一座智慧公厕&#xff0c;更是集合了多种功能&#xff0c;给我们带来全新的城市生活体验。本文以智慧驿站智慧公厕源…

前端调试工具之Chrome Elements、Network、Sources、TimeLine调试

常用的调试工具有Chrome浏览器的调试工具&#xff0c;火狐浏览器的Firebug插件调试工具&#xff0c;IE的开发人员工具等。它们的功能与使用方法大致相似。Chrome浏览器简洁快速&#xff0c;功能强大这里主要介绍Chrome浏览器的调试工具。 打开 Google Chrome 浏览器&#xff0c…

第N6周:使用Word2vec实现文本分类

import torch import torch.nn as nn import torchvision from torchvision import transforms,datasets import os,PIL,pathlib,warnings #忽略警告信息 warnings.filterwarnings("ignore") # win10系统 device torch.device("cuda"if torch.cuda.is_ava…

20240328金融读报:国内金融安全网与银行适老化实例

1、国内金融安全网&#xff08;原则&#xff1a;事前防范金融风险过度积累&#xff0c;事中、事后快速高效处置风险&#xff09;&#xff1a;1&#xff09;强化金融机构的公司治理和风险管理&#xff08;如重组与否&#xff09;2&#xff09;二加强金融监管&#xff08;各种存贷…

视频剪辑软件哪个好?2024会声会影怎么样呢?

随着科技的不断发展&#xff0c;视频制作已经不再是专业人士的专属领域&#xff0c;越来越多的人开始使用各种视频制作软件来记录生活、创作内容。其中&#xff0c;会声会影是被广泛使用的一款视频制作软件&#xff0c;其旗舰版更是备受关注。 视频剪辑软件哪个好&#xff1f;…

SnapGene 5 for Mac 分子生物学软件

SnapGene 5 for Mac是一款专为Mac操作系统设计的分子生物学软件&#xff0c;以其强大的功能和用户友好的界面&#xff0c;为科研人员提供了高效、便捷的基因克隆和分子实验设计体验。 软件下载&#xff1a;SnapGene 5 for Mac v5.3.1中文激活版 这款软件支持DNA构建和克隆设计&…

C++的字节对齐

什么是字节对齐 参考什么是字节对齐&#xff0c;为什么要对齐? 现代计算机中&#xff0c;内存空间按照字节划分&#xff0c;理论上可以从任何起始地址访问任意类型的变量。但实际中在访问特定类型变量时经常在特定的内存地址访问&#xff0c;这就需要各种类型数据按照一定的规…

每日一题 --- 有效的括号[力扣][Go]

有效的括号 题目&#xff1a;20. 有效的括号 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序…

【Python基础知识点】Python的浅拷贝和深拷贝

概述 本文主要通过两个简单的代码小例子理解深拷贝和浅拷贝 主体内容 copy 模块提供了浅拷贝和深拷贝的功能。它的主要函数有: copy(x): 返回对象 x 的浅拷贝。 deepcopy(x): 返回对象 x 的深拷贝。 浅拷贝使用 copy(x) 函数,它只复制了最外层的对象,但内层的对象仍然是引用…