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

文章目录

    • 前言
    • 参考目录
    • 学习笔记
      • 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.rhkb.cn/news/295158.html

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

相关文章

备考ICA----Istio实验15---开启 mTLS 自动双向认证实验

备考ICA----Istio实验15—开启mTLS自动双向认证实验 在某些生成环境下,我们希望微服务和微服务之间使用加密通讯方式来确保不被中间人代理. 默认情况下Istio 使用 PERMISSIVE模式配置目标工作负载,PERMISSIVE模式时,服务可以使用明文通讯.为了只允许双向 TLS 流量&#xff0c;…

37.HarmonyOS鸿蒙系统 App(ArkUI) 创建第一个应用程序hello world

HarmonyOS App(ArkUI) 创建第一个应用程序helloworld 线性布局 1.鸿蒙应用程序开发app_hap开发环境搭建 3.DevEco Studio安装鸿蒙手机app本地模拟器 打开DevEco Studio,点击文件-》新建 双击打开index.ets 复制如下代码&#xff1a; import FaultLogger from ohos.faultL…

大数据分析与内存计算——Spark安装以及Hadoop操作——注意事项

一、Spark安装 1.相关链接 https://dblab.xmu.edu.cn/blog/4322/ 2.安装Spark&#xff08;Local模式&#xff09; 按照文章中的步骤安装即可 遇到问题&#xff1a;xshell以及xftp不能使用 解决办法&#xff1a; 在linux使用镜像网站进行下载&#xff1a;wget https://mi…

uniapp-打包app-图标配置

依次找到manifest->App图标配置&#xff0c;然后点击浏览&#xff0c;从本地文件夹中选择你们项目的logo&#xff0c;然后点击自动生成所有图标并替换&#xff0c;即可&#xff1a;

微信小程序自定义弹窗组件

业务背景&#xff1a;弹窗有时字体较多&#xff0c;超过7个字&#xff0c;不适用wx.showToast. 组件代码 <view class"toast-box {{isShow? show:}}" animation"{{animationData}}"><view class"toast-content" ><view class&q…

【工具分享】一键抠图,很不错

在吾爱破解找到大神做的抠图工具&#xff0c;觉得很好分享出来 1、工具应解压&#xff0c;不可有中文路径 2、完整解压后&#xff0c;运行main.exe。将单个/多个图片拖入工具&#xff0c;等待提示完成后&#xff0c;在运行目录下的out目录内可找到扣好的图片。 3、如果需要al…

iOS开发进阶(十四):xcodebuild 命令应用详解

文章目录 一、前言二、xcodebuild 命令汇总三、xcodebuild 可选命令四、exportOptionsPlist文件内容配置说明五、项目实操六、拓展阅读 一、前言 关于iOS组包&#xff0c;详参博文《ReactNative进阶&#xff08;三十四&#xff09;&#xff1a;Jenkins 流水线 组包 iOS 应用包…

3D模型格式转换工具HOOPS Exchange如何将3D文件加载到PRC数据结构中?

HOOPS Exchange是一款高效的数据访问工具&#xff0c;专为开发人员设计&#xff0c;用于在不同的CAD&#xff08;计算机辅助设计&#xff09;系统之间进行高保真的数据转换和交换。由Tech Soft 3D公司开发&#xff0c;它支持广泛的CAD文件格式&#xff0c;包括但不限于AutoCAD的…

Java设计之道:色即是空,空即是色

0.引子 我们的这个世界上&#xff0c;存在这么一种东西&#xff1a; 第一&#xff1a;它不占据任何3D之体积&#xff0c;即它没有Volume第二&#xff1a;它也不占据任何2D之面积&#xff0c;即它没有Area第三&#xff1a;它也不占据任何1D之长度&#xff0c;即它没有Length 总…

01-​JVM学习记录-类加载器

一、类加载器子系统 1. 作用-运输工具&#xff08;快递员&#xff09; 负责从文件系统或者网络中加载Class文件&#xff08;DNA元数据模板&#xff09;&#xff0c;Class文件开头有特定标识&#xff0c;魔术&#xff0c;咖啡杯壁&#xff08;class文件存于本地硬盘&#xff0c…

状态压缩DP

哈密顿路径问题&#xff1a; 一般设 表示 状态下&#xff0c;为最后一个最值情况 。 一般有两种稍微不同的写法&#xff0c;单纯就是写法不同&#xff0c;思路方法都相同。 第一个例题为第一种转移方法&#xff0c;有当前转移后面。 后面的都是由前面转移目前。 G. Shuff…

App测试中ios和Android的区别

1、Android长按home键呼出应用列表和切换应用&#xff0c;然后右滑则终止应用&#xff1b; 2、多分辨率测试&#xff0c;Android端20多种&#xff0c;ios较少&#xff1b; 3、手机操作系统&#xff0c;Android较多&#xff0c;ios较少且不能降级&#xff0c;只能单向升级&…

vscode shadertoy插件,非常方便的glsl着色器编写工具

很著名的shadertoy网站&#xff0c;集合了非常多大神利用数学写出美妙的shader效果。像shadertoy创始人之一的IQ大神它在这方面有很多的建树。他的利用光线步进和躁声可以创建很多不可思议的3D场景。 vscode有一件shadertoy的插件&#xff0c;安装后可以新建一个*.glsl文件&am…

unity shader学习练笔日记(一)

1、简单顶点/片元着色器 Shader "Unity Shaders Study/Day One/Simple Shader" {Properties{//声明一个Color类型的属性_Color ("Color Tint", Color) (1.0, 1.0, 1.0, 1.0)}SubShader{Pass{CGPROGRAM#pragma vertex vert#pragma fragment frag//在CG代码…

聚观早报 | 蔚来推出油车置换补贴;iPhone 16 Pro细节曝光

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 4月02日消息 蔚来推出油车置换补贴 iPhone 16 Pro细节曝光 小米SU7创始版第二轮追加开售 OpenAI将在日本设立办事…

二百二十九、离线数仓——离线数仓Hive从Kafka、MySQL到ClickHouse的完整开发流程

一、目的 为了整理离线数仓开发的全流程&#xff0c;算是温故知新吧 离线数仓的数据源是Kafka和MySQL数据库&#xff0c;Kafka存业务数据&#xff0c;MySQL存维度数据 采集工具是Kettle和Flume&#xff0c;Flume采集Kafka数据&#xff0c;Kettle采集MySQL数据 离线数仓是Hi…

分布式任务调度框架XXL-JOB

1、概述 XXL-JOB是一个分布式任务调度平台&#xff0c;其核心设计目标是开发迅速、学习简单、轻量级、易扩展。现已开放源代码并接入多家公司线上产品线&#xff0c;开箱即用。 官方文档&#xff1a;https://www.xuxueli.com/xxl-job/#%E4%BA%8C%E3%80%81%E5%BF%AB%E9%80%9F%E…

ENSP DHCP 配置不同网段

配置不同网段。 配置&#xff1a;192.168.80.254 192.168.10.254 192.168.20.254 给绑定信息选择网卡&#xff0c;出端口编号改为2&#xff0c;勾选双向通道&#xff0c;点击增加。 接下来把vmnet 1和vmnet 2 都按上图所示。 打开路由器&#xff0c;就开始配置。

文本自动粘贴编辑器:支持自动粘贴并筛选手机号码,让信息处理更轻松

在信息时代的浪潮中&#xff0c;文本处理已成为我们日常工作与生活的重要组成部分。无论是商务沟通、社交互动还是个人事务处理&#xff0c;手机号码的筛选与粘贴都显得尤为关键。然而&#xff0c;传统的文本处理方式效率低下、易出错&#xff0c;已无法满足现代人的高效需求。…

MegaSeg Pro for Mac v6.3.1 注册激活版 音视频DJ混音工具

MegaSeg Pro for Mac是一款专业的DJ和广播自动化软件&#xff0c;旨在为音乐专业人士提供强大的音乐播放和演播功能。这款软件具有多种功能&#xff0c;包括强大的音乐库管理&#xff0c;支持导入和组织大量音乐文件&#xff0c;可以轻松管理你的音乐收藏。它支持广泛的音频格式…