[ReTree]支持正则表达式的Trie树

发表于 | 更新于 | 分类于

介绍

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
2
3
4
5
<dependency>
    <groupId>com.github.sisyphsu</groupId>
    <artifactId>retree</artifactId>
    <version>1.0.4</version>
</dependency>

用法

这个例子展示了retree的用法，它与java.util.regex比较相似：

1
2
3
4
5
6
7
8
9
10
11
12
13
String[] res = {"(\\d{4}-\\d{1,2}-\\d{1,2})", "<b>(?<name>.*)</b>", "(\\w+@\\w+\\.[a-z]+(\\.[a-z]+)?)"};
String input = "Today is 2019-09-05, from <b>sulin</b> (sisyphsu@gmail.com).";
ReMatcher matcher = new ReMatcher(new ReTree(res), input);

assert matcher.find();
assert "2019-09-05".contentEquals(matcher.group());

assert matcher.find();
assert "<b>sulin</b>".contentEquals(matcher.group());
assert "sulin".contentEquals(matcher.group("name"));

assert matcher.find();
assert "sisyphsu@gmail.com".contentEquals(matcher.group());

在这个例子里面，我们只需要扫描input一次，就可以完成三个正则表达式的匹配：

  • (\d{4}-\d{1,2}-\d{1,2})
  • <b>(?<name>.*)</b>
  • (\\w+@\\w+\\.[a-z]+(\\.[a-z]+)?)

它的性能，比三个正则表达式循环匹配要更好一些。且随着正则表达式的增加，它的性能优势就会更加明显。

使用场景

dateparser

dateparser是一个非常智能且高性能的日期解析工具，它支持成百上千种不同的日期格式，基本上可以覆盖我们日常用到的所有格式。

dateparser内置了许多预定义的正则表达式，分别用于解析不同格式的年、月、日、时、分、秒、时区等等。它使用retree将全部正则表达式合并起来，然后对输入字符串的进行自动的匹配。

即是dateparser内部有几百个预定义的正则表达式，但是仍然可以非常高性能地解析字符串，平均一次解析仅耗时1微秒。

性能与Benchmark

TODO

多语言支持

接下来我会考虑将retree移植至golang和javascript语言.