介绍
retree
可以将正则表达式解析为正则节点链,然后再将多个正则节点链合并为一颗正则节点树,在数据结构上,它与我们熟知的字典树trie
比较相似。
简单来讲,正则表达式会被解析为这样的节点链:
\d+a\W
会被解析为CurlyNode(\d+) -> CharNode(a) -> CharNode(\W)
\d+\s\W
会被解析为CurlyNode(\d+) -> CharNode(\s) -> CharNode(\W)
我们可以将节点链理解为组成字典树的字典String
。
retree
可以将大量的节点链合并为一颗节点树,然后在正则匹配时借助于trie
树的特点,避免不必要的字符串扫描和节点匹配,减少正则匹配过程中的回溯,从而提高批量正则表达式并发匹配的性能。
Maven依赖
可以通过这个maven
坐标引入retree
依赖:
1 | <dependency> |
用法
这个例子展示了retree
的用法,它与java.util.regex
比较相似:
1 | String[] res = {"(\\d{4}-\\d{1,2}-\\d{1,2})", "<b>(?<name>.*)</b>", "(\\w+@\\w+\\.[a-z]+(\\.[a-z]+)?)"}; |
在这个例子里面,我们只需要扫描input
一次,就可以完成三个正则表达式的匹配:
(\d{4}-\d{1,2}-\d{1,2})
<b>(?<name>.*)</b>
(\\w+@\\w+\\.[a-z]+(\\.[a-z]+)?)
它的性能,比三个正则表达式循环匹配要更好一些。且随着正则表达式的增加,它的性能优势就会更加明显。
使用场景
dateparser
是一个非常智能且高性能的日期解析工具,它支持成百上千种不同的日期格式,基本上可以覆盖我们日常用到的所有格式。
dateparser
内置了许多预定义的正则表达式,分别用于解析不同格式的年、月、日、时、分、秒、时区等等。它使用retree
将全部正则表达式合并起来,然后对输入字符串的进行自动的匹配。
即是dateparser
内部有几百个预定义的正则表达式,但是仍然可以非常高性能地解析字符串,平均一次解析仅耗时1微秒。
性能与Benchmark
TODO
多语言支持
接下来我会考虑将retree
移植至golang
和javascript
语言.