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

2016-08-06 15:41:00 +08:00
 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 次幂化简算法等等都跟朋友有过一些讨论,的确是非常有意思的一个课题,有想法的朋友请不吝赐教

3094 次点击
所在节点    程序员
14 条回复
mayokaze
2016-08-06 15:42:02 +08:00
啊...发现发错区了...请 @livid 移动到技术区去吧
mayokaze
2016-08-06 15:44:32 +08:00
自己移好了...实在抱歉没认真看
mayokaze
2016-08-06 15:46:01 +08:00
啊发现排版一塌糊涂忘了写 md_(:з」∠)_ 可是已经来不及编辑了....
Livid
2016-08-06 16:54:08 +08:00
@mayokaze 下次可以在发布之前用一下预览功能:

https://www.v2ex.com/new
iEverX
2016-08-06 17:13:50 +08:00
不是很懂什么意思啊
mayokaze
2016-08-06 17:33:26 +08:00
重新排版编辑了,简单来说是一个用 Haskell 写的可以对正则表达式求交集,子集和相等性的库,实际适用场景是像有海量正则需要同时过滤的时候用于消除冗余逻辑, 不过其实比起实际价值这种用抽象代数的方法计算正则表达式的形式更加值得关注。
7sDream
2016-08-06 18:20:20 +08:00
有点高端啊,如果是转换成 NFA 之类的再判断倒是不难,不过这种不产生自动机,用数学方法的应该效率更高吧。

虽然目前不知道使用场景,不过还是支持一下!
fy
2016-08-06 18:59:39 +08:00
好强啊 正则还可以求微分
mayokaze
2016-08-06 19:55:09 +08:00
@7sDream 其实 NFA 转 DFA 状态是会指数爆炸的,现在主流的 dfa 引擎像 Google 的 re2 都只是做了部分转换也只能 handle 不超过三位数的并行匹配,对于更大数量的 Google re2 的做法是构建一个 ac 自动机,将每条正则的元字符组成字串塞进去,当一个 input 进来的时候如果匹配就将他加入 potential match list 最后匹配这个 list ,总之做法非常工程非常“ low ”(并不
murmur
2016-08-06 23:09:10 +08:00
好屌。。这种东西我第一想法肯定是调用 matlab 混合编程
murmur
2016-08-06 23:13:18 +08:00
@7sDream 我也怀疑需求,符号计算是难点的难点,这东西数学是无限复杂的,你能写出来的你写不出来的微分套积分积分又套积分还可以对。。
matlab 这么屌的东西都是买的符号计算
yangxin0
2016-08-07 00:11:04 +08:00
@mayokaze google 有算法可以通过分组压缩状态到最优
mayokaze
2016-08-07 02:27:56 +08:00
@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
2016-08-08 05:42:21 +08:00
樓主是研究生麼? Brzozowski derivative 應該是很理論的內容了…… 另外本文其實應該發去 https://www.v2ex.com/go/re 因為本節點裡,能看懂的人不多……

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/297572

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX