写了一个基于正则求偏微分的正则逻辑运算库

[mayokaze]

https://github.com/mayokaze/Aoba

编译： ghc -O2 aoba.hs RE.hs 使用方法大致如下： ./aoba -i re1 re2 -- 交集 ./aoba -c re1 re2 -- 子集 ./aoba -e re1 re2 -- 相等

比起传统的 thompson 构建算法，求导算法不构建自动机，而且能够支持本应属于正则语言的 and 和 not 运算 关于集合运算的效率，和传统的 epsilon closure 同样是 n^2,不过传统 nfa 还多了 nfa to regex 一步所以求导算法应该是占优的 Google 有写过类似的项目： https://github.com/google/redgrep 但是他们只用到了 derive 而且他们的目的是构建自动机做匹配最终编译成 llvm bc. 如果纯求导算法做 match 的话工程上用不会太实用主要是因为 unicode 字符集爆炸的问题. 具体的原理见这篇论文： Valentin M. Antimirov: Partial Derivatives of Regular Expressions and Finite Automaton Constructions. Theor. Comput. Sci. 155(2): 291-319 (1996) 其他一些更高级的讨论例如正则求（偏）导和实函数求（偏）导的内在关联，自动机代数能否套用群论（环）的定义， n 次幂化简算法等等都跟朋友有过一些讨论，的确是非常有意思的一个课题，有想法的朋友请不吝赐教

Aoba

简单来说是一个用Haskell写的可以对正则表达式求交集，子集和相等性的库，稍作扩展也可以用来做正则匹配
https://github.com/mayokaze/Aoba

编译： ghc -O2 aoba.hs RE.hs
使用方法大致如下：

• ./aoba -i "a" "a*" -- 交集
• ./aoba -c "a+" "a*" -- 子集
• ./aoba -e "aa*" "a+" -- 相等

比起传统的 thompson 构建算法，求导算法不构建自动机，而且能够支持本应属于正则语言的 and 和 not 运算.
关于集合运算的效率，和传统的 epsilon closure 同样是 n^2,不过传统 nfa 还多了 nfa to regex 一步所以求导算法应该是占优的

Google 有写过类似的项目： https://github.com/google/redgrep 但是他们只用到了 derive 而且他们的目的是构建自动机做匹配最终编译成 llvm bc.
如果纯求导算法做 match 的话工程上用不会太实用主要是因为 unicode 字符集爆炸的问题.

具体的原理见这篇论文： Valentin M. Antimirov: Partial Derivatives of Regular Expressions and Finite Automaton Constructions. Theor. Comput. Sci. 155(2): 291-319 (1996)

其他一些更高级的讨论例如正则求（偏）导和实函数求（偏）导的内在关联，自动机代数能否套用群论（环）的定义， n 次幂化简算法等等都跟朋友有过一些讨论，的确是非常有意思的一个课题，有想法的朋友请不吝赐教

[mayokaze]

啊...发现发错区了...请 @livid 移动到技术区去吧

[mayokaze]

自己移好了...实在抱歉没认真看

[mayokaze]

啊发现排版一塌糊涂忘了写 md_(:з」∠)_ 可是已经来不及编辑了....

[Livid]

@mayokaze 下次可以在发布之前用一下预览功能：

https://www.v2ex.com/new

[iEverX]

不是很懂什么意思啊

[mayokaze]

重新排版编辑了，简单来说是一个用 Haskell 写的可以对正则表达式求交集，子集和相等性的库，实际适用场景是像有海量正则需要同时过滤的时候用于消除冗余逻辑， 不过其实比起实际价值这种用抽象代数的方法计算正则表达式的形式更加值得关注。

[7sDream]

有点高端啊，如果是转换成 NFA 之类的再判断倒是不难，不过这种不产生自动机，用数学方法的应该效率更高吧。

虽然目前不知道使用场景，不过还是支持一下！

[fy]

好强啊 正则还可以求微分

[mayokaze]

@7sDream 其实 NFA 转 DFA 状态是会指数爆炸的，现在主流的 dfa 引擎像 Google 的 re2 都只是做了部分转换也只能 handle 不超过三位数的并行匹配，对于更大数量的 Google re2 的做法是构建一个 ac 自动机，将每条正则的元字符组成字串塞进去，当一个 input 进来的时候如果匹配就将他加入 potential match list 最后匹配这个 list ，总之做法非常工程非常“ low ”（并不

[murmur]

好屌。。这种东西我第一想法肯定是调用 matlab 混合编程

[murmur]

@7sDream 我也怀疑需求，符号计算是难点的难点，这东西数学是无限复杂的，你能写出来的你写不出来的微分套积分积分又套积分还可以对。。
matlab 这么屌的东西都是买的符号计算

[yangxin0]

@mayokaze google 有算法可以通过分组压缩状态到最优

[mayokaze]

@yangxin0 https://github.com/google/re2/blob/ee55a8f64d253bdf5bfa98e8d09901a5fb9ee13c/re2/set.cc 这是 re2 的统一自动机构建
https://github.com/google/re2/blob/ee55a8f64d253bdf5bfa98e8d09901a5fb9ee13c/re2/filtered_re2.cc
这是我前面提到的大量正则过滤模式
一般来说超过三位数的正则 filtered_re2 性能就要好于 set 了

[franklinyu]

樓主是研究生麼？ Brzozowski derivative 應該是很理論的內容了…… 另外本文其實應該發去 https://www.v2ex.com/go/re 因為本節點裡，能看懂的人不多……