主题对照

正则引擎与回溯性能

比较DFA与NFA引擎、回溯与匹配优先/忽略优先、有序多选的行为,以及提取前缀、固化分组、消除循环等避免灾难性回溯的优化方法。

15 张卡片 · 2 本书

本层 15 张卡片 · 含下级覆盖 15 张卡片

本主题的卡片

精通正则表达式(第3版)

引擎类型决定结果

本书把引擎粗分为DFA、传统型NFA和POSIX NFA,用来讨论匹配选择及成本:实现方式与必须符合的结果规则是不同维度,混合系统还可按模式选择执行路径。书中NFA主要指回溯式实现,并非所有NFA算法都如此;Thompson NFA模拟也能同时推进状态集合。术语补充依据:Russ Cox原文。具体工具、特性和版本须分别核对,不能仅凭书中的旧版本表预测现代结果。

本节图片专栏“NFA理论与现实”也明确区分数学上的NFA与实践中沿用的引擎称呼;另一专栏说明混合系统会按是否需要反向引用、捕获等切换路径。因此术语外延的限定既有原书依据,也有外部算法资料核对。

查看卡片与原书出处

精通正则表达式(第3版)

NFA需要设计

在本书的回溯式NFA语境中,表达式的层级、分支顺序与量词组织会决定尝试路径。失败后可能在相同文本上换另一条路径,因而两种接受相同文本的表达式仍可能有不同成本。这里讨论的是回溯式实现,不把所有NFA算法归入它。重写时还须核对捕获接口:即使最终匹配范围相同,括号数量和提取结果也可能改变。关联:[[回溯保存选择]]。

查看卡片与原书出处

精通正则表达式(第3版)

回溯保存选择

回溯式引擎在分支或可选重复处保留未走的选择。备用状态包含模式中的继续位置、文本中的位置,以及需要恢复的捕获等状态;局部失败时,优先回到最近保留的选择,即后进先出。当前起点所有路均失败后,普通搜索才可能换到下一个起点,后者与表达式内部回溯是两层动作。成功的局部匹配不保证全式成功,捕获也不能保留已经被放弃路径上的旧结果。

查看卡片与原书出处

精通正则表达式(第3版)

贪婪不是最长

在本书的回溯式模型中,贪婪量词先尝试较多重复,后续失败时可按备用路径交还内容,直到全式成功或选择耗尽。贪婪描述组件的尝试顺序,不保证整个结果全局最长。比如.*在前、数字重复在后时,前者可能只交还足够让后者成功的末位。第1章<.*>跨过多个标记的例子也说明:量词偏好不能替代对输入内部结构的限制。关联:[[引擎类型决定结果]]。

查看卡片与原书出处

精通正则表达式(第3版)

懒惰也会回溯

懒惰量词先选择少匹配或跳过,并保存以后扩张的选择;后续失败时仍会回溯并尝试更多内容。ab??c在abc上先跳过b,因c无法匹配b而返回尝试b,最终仍可成功。它改变的是路径先后,并不保证只取最短目标或只检查一次。要排除某种内部内容,应明确约束允许的字符或结构,而不是仅靠懒惰偏好。

查看卡片与原书出处

精通正则表达式(第3版)

有序多选能表达策略

传统回溯式引擎按书写顺序尝试多选分支。先成功的分支若已能完成整个模式,后面即使可能更长也不再尝试;若后续失败,仍可回到后面的分支。tour|to|tournament因此可能只取tour,而非tournament。有序多选表达的是“先试哪个”,不是全局最长或最短保证;输入起点的搜索优先级又是另一层。

查看卡片与原书出处

精通正则表达式(第3版)

性能依赖数据

一次模式改写的收益取决于实际数据、成功/失败分布、调用数、引擎版本和已经生效的优化。新增预查可能省去很多失败尝试,也可能只是重复引擎已做的工作;常见位置靠前或靠后,又会改变不同扫描方式的成本。以有代表性的数据验证语义和计时范围,不把旧版单例倍数当作普遍结论。

查看卡片与原书出处

精通正则表达式(第3版)

避免重复编译

模式使用前需检查并形成内部表示,未变化的模式可复用它。对象式接口可将编译对象移到循环外;集成式或函数式接口也可能自动缓存,不能假定每次调用都重新编译。动态插值可能需要重新生成并比较模式,工作集超过缓存容量又可能反复淘汰。按实际接口核对缓存与模式变化,分别衡量编译、查缓存和匹配成本。

原书Perl进一步区分无插值文字的直接缓存,以及插值后比较新旧模式、必要时重编译。两者都不是把缓存保留到下一次进程运行;嵌入代码变量不是普通模式插值,闭包生命周期又需另查。

Java需要反复使用相同模式时,可先编译Pattern,再为输入创建或重置Matcher。Pattern.matcher只建立模式和输入的关联,不会提前执行查找。书中成本判断是避免重复准备的原则,具体收益仍依真实调用范围。

查看卡片与原书出处

精通正则表达式(第3版)

共享前缀要提取

this|that可组织为th(?:is|at),让公共前缀只在概念上检查一次,并暴露给可能的字面预查优化;公共后缀也可提取。改写仍须保持分支优先级、捕获接口和模式范围,现代引擎也可能已自动完成相同优化。共享结构的表达通常更清楚,但具体速度收益需绑定实现和数据。

查看卡片与原书出处

精通正则表达式(第3版)

非捕获减少状态

(?:…)只把子表达式组合成一个单元,不创建捕获编号。不需要提取或反向引用这部分内容时,可减少捕获记账,并避免公共组件使外部编号漂移。它不自动减少所有回溯分支,也不能保证在每个实现上更快;旧版优化可能对捕获和非捕获形状有不同处理。先确认消费者不依赖该捕获,再判断清晰度与实际成本。

查看卡片与原书出处

精通正则表达式(第3版)

固化剪掉回溯

(?>…)在其内部仍可正常尝试和回溯,但成功退出时会丢弃内部尚可回退的选择。外部后续失败不能再进入这些选择;外部更早的状态却仍可放弃整个组或重新应用它。它可能保持原结果、改变结果或使原本成功的匹配失败,也可能减少无效失败尝试。价格例把“可选第三位”固化,是为了防止已经保留的非零第三位再被交还,并非无条件提速。

查看卡片与原书出处

精通正则表达式(第3版)

消除循环套路

消除循环将逐字符多选重复改写成“普通段后接若干特殊单元加普通段”,常见形状是opening normal* (special normal) closing。普通段连续处理常见文本,特殊单元成为明确检查点。必须核对起始互斥、重复能推进,以及特殊片段不会被多轮歧义分割;不能只把模板中的名字换掉。不同文法可能要求普通段非空,性能收益也取决于实现。

查看卡片与原书出处

精通正则表达式(第3版)

引导扫描跳过噪声

若只寻找目标片段,搜索器可能从不应处理的上下文内部重试。原书删除注释时也识别完整引文,一次消费并原样保留它,避免从其中的/*开始误取注释。可以把保留分支捕获后放回,让目标分支替换为空;还需明确支持哪些字符常量、转义和注释形式。这是引导扫描上下文的办法,不等于完整语言解析或安全源码改写。

查看卡片与原书出处

精通正则表达式(第3版)

嵌套量词引爆回溯

当内部重复和外部重复都能分配同一串字符时,如普通字符段+再被外部*重复,同一文本可有大量不同分段。首条成功路径看起来很快,缺少闭合符等失败输入却可能迫使回溯遍历这些分割,工作量随长度急剧增长。问题是重叠的分配选择,不是看到嵌套符号就必定指数,也不能凭成功样例排除失败风险。实际优化、上限与输入结构会改变表现。

查看卡片与原书出处

万亿级流量转发 BFE核心技术与实现 2021 · BFE的转发模型

条件表达式

重构前,BFE用正则表达式描述转发条件,暴露出两个问题:难读,一个人写的条件别人很难接手;性能有隐患,一条写得不当的正则曾让服务从每秒几千请求降到几十。新设计的条件表达式在函数名里明确指出匹配哪个HTTP字段,并以精确、前缀、后缀等低复杂度匹配为主。面向业务的配置语言应限制表达能力。

查看卡片与原书出处
辅助阅读:卢曼编号

按卢曼编号阅读

点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。

  • 展开或收起下级: 1912 引擎类型决定结果 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 展开或收起下级: 1912.a NFA需要设计 主题成员 精通正则表达式(第3版) 理解等级:未标注
      • 1912.a.1 回溯保存选择 主题成员 精通正则表达式(第3版) 理解等级:未标注
      • 1912.a.2 贪婪不是最长 主题成员 精通正则表达式(第3版) 理解等级:未标注
      • 1912.a.3 懒惰也会回溯 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 1912.b 有序多选能表达策略 主题成员 精通正则表达式(第3版) 理解等级:未标注
  • 展开或收起下级: 1914 性能依赖数据 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 1914.a 避免重复编译 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 1914.b 共享前缀要提取 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 1914.c 非捕获减少状态 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 1914.d 固化剪掉回溯 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 展开或收起下级: 1914.e 消除循环套路 主题成员 精通正则表达式(第3版) 理解等级:未标注
    • 1914.f 嵌套量词引爆回溯 主题成员 精通正则表达式(第3版) 理解等级:未标注
  • 展开或收起下级: 2629 四级转发模型 路径上下文 万亿级流量转发 BFE核心技术与实现 2021 · BFE的转发模型 理解等级:未标注
    • 2629.c 条件表达式 主题成员 万亿级流量转发 BFE核心技术与实现 2021 · BFE的转发模型 理解等级:未标注

来源书籍

主题索引

服务发现与网关

比较服务发现范式、注册中心的 CAP 取舍与实现路线、网关与 BFF,以及地域与区域的流量边界。

286 张卡片 · 70 本书