Yes, all longest regex matches in linear time is possible
2 months ago
- #algorithms
- #regex
- #performance
- 像RE2、Go和Rust这样的正则表达式引擎宣称单次匹配具有线性时间复杂度，但查找所有匹配可能导致平方级复杂度。
- 问题源于重叠的匹配候选位置以及需要从每个位置重新开始搜索。
- 最早匹配语义可以避免平方级复杂度，但会改变结果，产生比最左最长语义更短的匹配项。
- RE#引入了加固模式，通过两轮扫描算法保证所有匹配都在线性时间内完成，且不改变语义。
- 加固模式需要主动启用，因为存在性能权衡——大多数实际场景的模式不会触发平方级复杂度。
- RE#包含AVX2和NEON等CPU指令集优化，加速字符跳转，提升文字密集型模式的性能。
- 流式处理语义受限于最左最长匹配原则，可能需要无限缓冲，但分块处理方案可以缓解该问题。
- RE#不支持捕获组或惰性量词，专注于最左最长(POSIX)语义和线性时间复杂度保证。