The quadratic problem nobody fixed
2 months ago
- #algorithm
- #regex
- #performance
- 正则表达式引擎在查找所有匹配时存在O(n²)复杂度问题，这是自1970年代就存在的长期难题
- RE2、Go的regexp和Rust的regex crate等引擎承诺的线性时间匹配仅适用于单个匹配，而非全部匹配
- 当处理类似'.*a|b'的模式和'bbbb...'这类输入时，会出现三角累加工作量，导致平方级复杂度
- Aho-Corasick算法(1975)针对固定字符串能以线性时间解决问题，但不适用于正则表达式
- Hyperscan/Vectorscan采用'最早匹配'语义实现线性时间，但会改变匹配结果
- RE#引入双通道算法，在不改变语义的前提下实现线性时间全局匹配
- RE#提供'加固'模式，即使面对对抗性输入也能保证线性时间，但会牺牲部分性能
- 由于更高效的DFA缓存处理，RE#在处理大型字典时性能优于Aho-Corasick
- RE#暂不支持捕获组和惰性量词，专注于POSIX语义和布尔运算
- 名为're'的grep工具利用RE#的布尔运算符实现高级搜索功能