规则引擎建库工具

我们已使用 terark.com 进行商业化运营

这个工具使用了一个非常高效的算法,用来匹配多个高级正则表达式。经过预处理,仅用 O(n) 的时间复杂度,就可以识别出一个输入字符串(长度为n)能匹配哪些(可能是多个)正则表达式。算法的详细内容可参见:

  1. 多正则表达式匹配(Multiple Regular Expression Matching)
  2. 多正则表达式匹配(Multiple Regular Expression Matching) 中的动态 DFA 算法

算法的原理请参考: 多正则表达式匹配(Multiple Regular Expression Matching)

作为一个完整的解决方案,这个程序包括两部分:

  • 一个离线 Build 程序:regex_build
    1. regex_build 会把输入的正则表达式编译成一个 DFA  ( 正则表达式的编译使用了 re2 的前端 Parser )
    2. 如果使用二进制模式,还会生成一个 binmeta 文本文件,用来描述 DFA 的元信息
      • 该文件生成后不可被更改,否则会产生未定义行为
      • 目前应该首选二进制模式
  • 一个动态库,提供匹配接口
    1. 从 (regex_build生成的) DFA 文件 和 binmeta(二进制模式) 文件 加载 并 创建出 用来执行匹配 的 对象
    2. 在二进制模式下,构造 MultiRegexFullMatch 对象执行全匹配,此时不获取 Submatch,仅返回能匹配上的正则表达式 ID:MultiRegexFullMatch示例程序
    3. 在二进制模式下,构造 MultiRegexSubmatch 对象执行匹配:MultiRegexSubmatch示例程序
      • MultiRegexSubmatch 仅能获取 one-pass 正则的 submatch
      • one-pass 正则的判断直接调用了 re2 的判断函数 IsOnePass
        • 很不幸,该函数会将正则表达式 从([^到]+)到([^怎]+)怎么走 判为非 one-pass,但实际上,在 unicode 字符集内,它的确是 one-pass,只是 re2 的底层引擎是基于字节的,所以它认不出来
        • 如果你愿意冒险,regex_build 给你一个选择,将所有的正则表达式标为 one-pass,MultiRegexSubmatch::match_utf8 在搜索完之后,会按 utf8 编码规则做一个边界修正,就可以正确提取出 从([^到]+)到([^怎]+)怎么走 中的 submatch 了

Compile (现在已闭源,只能下载编译好的程序)

regex_builder 使用方法

regex_builder.exe 将很多个正则表达式 offline build成一个DFA文件,online程序使用时,先加载DFA文件,当匹配文本时,可以获知匹配到了哪些正则表达式,同一个文本可能匹配多个正则表达式。

匹配接口分文本接口于二进制接口两种,目前二进制接口已经有了很友好的封装,推荐使用。

文本接口的使用方法与之前的DFA词表完全相同(match_key接口)。

该程序使用 re2 的parser前端,生成 febird 自己的 DFA 文件

命令行选项与参数

命令行: regex_build.exe Options [Regex-TXT-File]

Options 命令行选项 说明
-O regex_dfa_file 生成的 DFA 文件 (-O大写)
-o regex_dfa_file 生成一种优化的 DFA (使用了虚拟机思想的 DFA),尺寸小且匹配速度快 (-小写)
-a 从所有位置开始匹配,相当于在所有正则表达式之前加 .* ,这会加快匹配速度,因为不需要重新
从输入文本的每个位置开始搜索,但会大大增加内存用量(20倍以上),build消耗的时间也会显著增加
-A 在所有正则表达式合并之后加 .* ,仅用于测试
-b binmeta_file 生成 binmeta_file,是在 Binary 模式下获取 Submatch 时使用的元信息
-g 为每个正则表达式生成三个 dot 文件,该文件用来可视化正则表达式自动机的状态图NFA/DFA/MinimizedDFA
-G 生成整个DFA的dot文件,通常情况下,该文件会很大
-L 不使用UTF8,使用Latin1;不加该选项时(默认情况)使用的是UTF8
Latin1 是字节模式,例如 [^汉字] 是排除了 汉字 这个两个字对应的所有二进制字节的其他字节值
例如在做深度包检测(Deep Packet Inspection)时,就需要这个选项做二进制匹配
-c conflict_report_file 当同一个文本会被多个正则表达式匹配时,此时称为冲突,该选项将冲突的正则表达式的id写到conflict_report_file
很多时候冲突是不可避免的,但是,根据 confict_report_file,可以修改正则表达式,尽可能减小冲突的可能性
-s 捕获 submatch,也就是 () 中的部分,默认情况下不捕获 submatch
-t dfa_type 默认dfa_type=d, 表示 DenseDFA,专为正则表达式优化的DFA
d以外的其它字符,表示DFA类型为一般DFA,主要为词表DFA优化
-D 构建动态DFA以节省内存和构建时间,在某些情况下,构建完整DFA甚至是不可能的,
(2014-11-04日)新增了一个优化:在该选项中,使用一种启发式的策略来合并DFA,大大提高了动态DFA匹配的速度并减小内存用量
如果没指定该选项,程序有可能花费很长时间并最终耗尽内存也无法构建出DFA,最后异常终止
-I 正则表达式忽略大小写
-T timeout1:timeout2
(2014-08-29 新增功能)
NFA 转 DFA 的 超时时间对于一些病态的正则表达式,NFA 转 DFA有可能发生超时
timeout1 单个正则表达式的超时时间,单位是毫秒,默认值是 1000
timeout2 所有正则表达式的超时时间,单位是该参数是可选的,默认0,表示不限超时

关于 -d 选项    该选项现在已删除,不再支持

一开始 febird DFA 通过 match_key 接口来实现正则表达式匹配,必须在 byte 的取值范围 [0, 256) 之间取一个作为分隔符。后来,经过仔细考虑,通过扩充自动机的字符集(r1303),从而 delimeter 可以在 [0, 256) 之外取值,于是就不再需要从 [0, 256) 取一个特殊值来作为分隔符。

这样,正则表达式匹配就可以有更广的适用范围。另一方面,表面上看,似乎去除一个特殊byte值作为delimeter会影响二进制模式的匹配,其实一点也不会。正则表达式相当于key,正则表达式的 id 相当于是 value,delimeter 不能出现在 key 中,但可以出现在 value 中,从而,value可以是任意二进制数据。实际上,二进制匹配接口的实现是先于 r1303 的。

Regex-TXT-File

如果命令行未指定 Regex-TXT-File,就从标准输入读取

Regex-TXT-File 的格式:  composed regexp \t id

第一列是正则表达式(re2语法),如果行首字符是 *,表示忽略该正则表达式的 one pass 属性,无条件获取 submatch,用 * 做标志的原因是以 * 开头的正则表达式是非法的正则,从而不会引发歧义,也不会减少表达能力。

第二列是正则表达式的id,该id可以是任意字符串,用来标识这条规则。多个正则表达式可以有相同的id,此时等效于将多个正则表达式或起来放在一行。

2014-8-31 日新加了一个功能,就是上面强调的 composed regexp:可以是多个正则表达式的并交差,还有连接重复,语法很简单:

Inter 表示 Intersection 或 Difference,求交集(&&),或者差集(&!),Union 表示求并集(||),所有操作符都是左结合,重复(?,*,+,{min,max})的优先级最高,接下来是连接连接不需要操作符,然后是集合操作,&&&! 的优先级相同,比 || 高,圆括号 ( ) 用来强制结合。

值得一提的是,{{}},用来括住正则表达式(re2语法),一个语法正确并且规范的正则表达式中不会出现 {{ 和 }},只有一个例外:\{{,这个例外很容易处理。其实严格讲,语法正确的正则表达式中可以出现 {{ 和 }},但这样正则表达式往往是有问题的,和 用作非元字符时,需要转义(\{\}),而 和 不转义时是元字符,不会出现 {{ 和 }}。这样,composed regexp 中的 composed 部分的编译可以和 regexp 部分的编译完全分离开来,composed 部分用简单地递归下降就可以解决,regexp部分直接用re2的前端。整个 composed regexp 中可以没有 {{ 和 }} ,此时它就是一个简单正则,简单正则支持取括号(submatch), composed regexp 则不支持取括号。

最开始我用{{{}}}表示正则语法的分界,并且只实现了并交差,但后来要增加连接重复,发现{{{}}}在视觉上太别扭,就简化成了{{}},并处理例外情况。

一个示例的Regex.txt :

这其中有多个 composed regexp,为了便于测试,我做了一个页面: 正则表达式图形化

非常重要!注意事项!

谨慎使用 .* ,特别是当 .* 处于正则表达式开头时

普通字符串(不包括正则表达式的元字符)也可以放进Regex.txt,可以为所有普通字符串赋予一个相同的id,这样就将正则表达式和普通字符串build到同一个DFA中了,普通字符串在DFA中占的空间相对要小得多,如果普通字符串很多,可以尝试用 -t x选项,看生成的DFA文件是否更小。

匹配接口: 二进制模式

MultiRegexFullMatch

参考 MultiRegexFullMatch示例程序

MultiRegexSubMatch

参考 MultiRegexSubmatch示例程序

匹配接口: 文本模式(现在已删除,不再支持)

匹配接口使用方法可以参考 DFA_Interface::match_key 示例程序

直接去 febird-trunk/samples/automata/abstract_api/ 目录运行 make即可编译,编译输出在 rls 和 dbg 目录下

编译出来的 match_key 程序可用来测验匹配(match_key程序使用的 delimiter是 \t ):

febird-trunk/samples/automata/abstract_api/rls/match_key -t abcccb < samples.dfa 输出:

输出的 str=1 str=2 str= a-dot-star-b就是匹配到了id为1、2、a-dot-star-b的正则表达式

使用 match_key 接口,正则表达式匹配和词典匹配就完全相同。

我们已使用 terark.com 进行商业化运营

作者:
该日志由 csdn-whinah 于2013年12月17日发表在自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 规则引擎建库工具
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

1 个回复

  1. alvininchina说道:

    赞,这个工具大神准备开源不?或者对外提供lib库?相信很多人都需要

发表评论

您必须 登录 后才能发表评论。