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

news/2024/6/24 8:59:07/文章来源:https://blog.csdn.net/Michelle_Zhong/article/details/137287900

文章目录

    • 前言
    • 参考目录
    • 学习笔记
      • 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.luyixian.cn/news_show_1034503.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python课后习题二

题目&#xff1a; 1. 2. 解题过程&#xff1a; 1. # 有序吗&#xff1f; ls input("请输入一个列表&#xff08;空格隔开&#xff09;&#xff1a;").split() ls_list list(ls) ls_listnew sorted(ls_list) if ls_listnew ls_list:print("列表已排序&quo…

Autodesk Maya 2025---智能建模与动画创新,重塑创意工作流程

Autodesk Maya 2025是一款顶尖的三维动画软件&#xff0c;广泛应用于影视广告、角色动画、电影特技等领域。新版本在功能上进行了全面升级&#xff0c;新增了对Apple芯片的支持&#xff0c;建模、绑定和角色动画等方面的功能也更加出色。 在功能特色方面&#xff0c;Maya 2025…

【AI数字人】根据音频生成带动画的数字人

这是一个从音频和蒙面手势生成全身人体手势的框架,包括面部、局部身体、手和整体动作。为了实现这一目标,我们首先引入 BEATX (BEAT-SMPLXFLAME),一个新的网格级整体协同语音数据集。 BEATX 将 MoShed SMPLX 身体与 FLAME 头部参数相结合,进一步细化头部、颈部和手指运动的…

DolphinScheduler on k8s 云原生部署实践

文章目录 前言利用Kubernetes技术云原生平台初始化迁移基于Argo CD添加GitOpsDolphinScheduler 在 k8s 上的服务自愈可观测性集成服务网格云原生工作流调度从HDFS升级到S3文件技术总结 前言 DolphinScheduler 的高效云原生部署模式&#xff0c;比原始部署模式节省了95%以上的人…

谷粒商城实战(008 缓存)

Java项目《谷粒商城》架构师级Java项目实战&#xff0c;对标阿里P6-P7&#xff0c;全网最强 总时长 104:45:00 共408P 此文章包含第151p-第p157的内容 简介 数据库承担落盘&#xff08;持久化&#xff09;工作 拿map做缓存 这种是本地缓存&#xff0c;会有一些问题 分布…

VMware虚拟机共享主机v2rayN

目录 &#x1f33c;前言 &#x1f33c;解释 &#x1f6a9;操作 1&#xff09;VMware -- 虚拟网络编辑器 2&#xff09;VMware -- 网络适配器 3&#xff09;主机 IP 地址 4&#xff09;v2rayN 代理端口 5&#xff09;VMware -- 网络代理(Network proxy) &#x1f382;结…

【面试八股总结】传输控制协议TCP(三)

参考资料 &#xff1a;小林Coding、阿秀、代码随想录 一、TCP拥塞控制⭐ 1. 慢启动 – Slow Start 慢启动是指TCP连接刚建立&#xff0c;一点一点地提速&#xff0c;试探一下网络的承受能力&#xff0c;以免直接扰乱了网络通道的秩序。 慢启动算法&#xff1a; 初始拥塞窗口…

探索设计模式的魅力:AI大模型如何赋能C/S模式,开创服务新纪元

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 AI大模型如何赋能C/S模式&#xff0c;开创服务新纪元 数字化飞速发展的时代&#xff0c;AI大模型…

提升常州小程序软件开发的搜索排名:关键步骤解析

在移动互联网的浪潮中&#xff0c;小程序作为连接用户与服务的桥梁&#xff0c;其重要性日益凸显。对于常州的小程序软件开发企业来说&#xff0c;如何让自己的产品在浩如烟海的互联网信息中脱颖而出&#xff0c;提升搜索排名&#xff0c;成为了亟待解决的问题。本文将为您解析…

C++面向对象程序设计 - 访问对象中成员的3种方法

在C程序中访问对象的成员变量和成员函数&#xff0c;有三种方法&#xff1a; 通过对象名和成员运算符访问对象中的成员&#xff1b;通过指向对象的指针访问对象中的成员&#xff1b;通过对象的引用变量访问对象中的成员 在了解访问对象中成员的3种方法前&#xff0c;先了解下C…

稀碎从零算法笔记Day37-LeetCode:所有可能的真二叉树

今天的每日一题&#xff0c;感觉理解的还不够深&#xff0c;有待加深理解 题型&#xff1a;树、分治、递归 链接&#xff1a;894. 所有可能的真二叉树 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述 给你一个整数 n &#xff0c;请你找出所有…

第五篇:3.4 用户归因和受众(User attribution and audience) - IAB/MRC及《增强现实广告效果测量指南1.0》

翻译计划 第一篇概述—IAB与MRC及《增强现实广告效果测量指南》之目录、适用范围及术语第二篇广告效果测量定义和其他矩阵之- 3.1 广告印象&#xff08;AD Impression&#xff09;第三篇广告效果测量定义和其他矩阵之- 3.2 可见性 &#xff08;Viewability&#xff09;第四篇广…

解析Flutter应用在iOS环境中的性能优化技巧

本文探讨了使用Flutter开发的iOS应用能否上架&#xff0c;以及上架的具体流程。苹果提供了App Store作为正式上架渠道&#xff0c;同时也有TestFlight供开发者进行内测。合规并通过审核后&#xff0c;Flutter应用可以顺利上架。但上架过程可能存在一些挑战&#xff0c;因此可能…

STM32-03基于HAL库(CubeMX+MDK+Proteus)输入检测案例(按键控制LED)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的按键检测代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 搭建完成开发STM32开发环境之后&#xff0c;开始GPIO…

【嵌入式硬件】光耦

1.光耦作用 光耦一般用于信号的隔离。当两个电路的电源参考点不相关时,使用光耦可以保证在两边不共地的情况下,完成信号的传输。 2.光耦原理 光耦的原理图如下所示,其内部可以看做一个特殊的“三极管”; 一般的三极管是通过基极B和发射极E间的电流,去控制集电极C和发射极…

01 Python进阶:正则表达式

re.match函数 使用 Python 中的 re 模块时&#xff0c;可以通过 re.match() 函数来尝试从字符串的开头匹配一个模式。以下是一个简单的详解和举例&#xff1a; import re# 定义一个正则表达式模式 pattern r^[a-z] # 匹配开头的小写字母序列# 要匹配的字符串 text "h…

牛客2024年愚人节比赛(A-K)

比赛链接 毕竟是娱乐场&#xff0c;放平心态打吧。。。 只有A一个考了数学期望&#xff0c;其他的基本都是acmer特有的脑筋急转弯&#xff0c;看个乐呵即可。 A 我是欧皇&#xff0c;赚到盆满钵满&#xff01; 思路&#xff1a; 我们有 p 1 p_1 p1​ 的概率直接拿到一件实…

使用Excel连接Azure DevOps自动退出的问题

Azure DevOps Server (原名TFS)是微软公司的软件开发管理平台&#xff0c;也是著名的软件开发过程管理工具&#xff1b;系统中记录了软件开发过程中的需求、问题、缺陷和迭代计划等各种软件开发工作项数据。 对于工作项数据的批量操作(例如新增和编辑)&#xff0c;Excel是一个非…

DevOps与CI/CD简介

DevOps 是一种软件开发和运维的文化、实践和方法论&#xff0c;旨在通过加强开发团队和运维团队之间的合作和沟通&#xff0c;实现快速、高效、可靠的软件交付和运维。DevOps 是由 Development&#xff08;开发&#xff09;和 Operations&#xff08;运维&#xff09;两个单词组…

【随笔】Git -- 高级命令(下篇)(八)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…