有 1 个输入字符串，和 1 万个正则，如何找到哪个正则匹配

[timi]

循环 1 万次是不是性能很 low ，有什么优化解吗

[icyalala]

看着很奇葩的问题啊，最初的需求是什么？

[murmur]

应该是敏感词过滤吧，
这个只能老老实实匹配，漏一个问题就大了，不要想着诀窍，真出了问题大事

[timi]

@icyalala 类似于根据不同的 URL 进行路由，但是简单的字符串匹配满足不了……

[ebingtel]

搞个多进程的 daemon 服务，每个进程负责 部分正则

[dallaslu]

如果不是正则的话，可以构造一个包含一万个节点的匹配树。如果是正则的话，好像也有可能啊，怕不是要自己魔改一个正则实现来构造匹配树

[nekoneko]

多线程并发呗
java 直接 parallelStream

[ch2]

与每个模式串的复杂度有关，如果模式串复杂度都很低，那么 1 万次匹配也是秒出

[dallaslu]

AC 自动机： https://www.cnblogs.com/nullzx/p/7499397.html

[chihiro2014]

前缀树？

[murmur]

@dallaslu AC 自动机不能完成所有东西，比如我要匹配(拼音是 sha 的所有汉字)(2-5 个任意非中文字符)(拼音为 b 的所有汉字)

你的 AC 自动机怎么弄

[murmur]

@dallaslu 回错了，我没看楼主突然回了

路由这个东西还要自己做的，啥库不支持模糊路由啊

[shyrock]

正则就是匹配条件吧？所以要想保持匹配结果不变，又想提升效率。要么并行、要么提升单次匹配的效率。
对了，还有一个思路是利用已经匹配的正则所加入的信息，也就是说要先分析这一万个正则的相关性，把匹配 A 的必然匹配 B 这种关系找出来；或者匹配 C 的必然不匹配 D 。这样可以构建一个匹配的顺序，尽量减少匹配次数。

[lianyue]

如果只需要某一个匹配的结果那

吧 10000 个正则 合并成 一个正则 用 `|` 分开 并且每个正则分组好(?<id1>正则规则 1) (?<id2>正则规则 2)
然后 响应结果 看哪个下标不为 null 就知道是哪个正则匹配成功了

[ys2016814]

FST

[lianyue]

(?<id1>原始的正则规则 1)|(?<id2>原始的正则规则 2)

[GeruzoniAnsasu]

…… 你应该尝试把那 1w 个正则编译到一起去

既然是路由分发，那么这些正则就必然是静态的，你完全可以把时间都放到编译期。
之前做过一些极重规则的东西，数以万计内置规则，我们用了这个
http://www.colm.net/open-source/ragel/

虽然编译要跑一个小时，但是运行快啊（

[wszgrcy]

把 1w 个正则合并成一个正则,让引擎自己优化?[doge]

[litmxs]

试试 Intel 的 hyperscan ，多模正则库

[Chinsung]

给正则构建一个树，一万个正则之间肯定有互斥的和包含关系，根据正则之间的关系简单分组，在正则树上匹配查找。

[SteveWoo]

弄 1w 台主机，发给 1w 个主机，算完了给你结果

[popvlovs]

hyperscan

[jianhua]

包括：
1. 缓存匹配结果和类型。记录上次匹配结果和特征，引入特征查找算法。
2. 通过分析正则的含义，打标签（数字、字母、字符等匹配规则）：
2.1 通过建立离线测试集，暴力测试正则的匹配含义
2.2 通过分析正则语法
基于正则的标签，优化原始数据特征提取和检索算法。最简单的，当你知道输入字符串是一个数字，那么应该排除掉所有字母、字符类的正则。

[timi]

@GeruzoniAnsasu 感觉路子很野但是又很有道理😂

[timi]

@murmur 其实不是路由，更接近于给某个 URL 贴个标签这样的，场景比较特殊不变透露但基本就是酱紫

[paopjian]

@GeruzoniAnsasu 第一次看到这么厉害的库,英语都没怎么读懂,好难

[seanzxx]

@GeruzoniAnsasu 我也是第一时间想到了 ragel ，以前拿这个来重写了一堆手写的正则匹配，真的很好用

[yesterdaysun]

合并正则+多线程