V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
timi
V2EX  ›  问与答

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

  •  1
     
  •   timi · 2022-01-13 14:51:34 +08:00 · 2761 次点击
    这是一个创建于 805 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    27 条回复    2023-07-07 09:52:41 +08:00
    icyalala
        1
    icyalala  
       2022-01-13 14:54:55 +08:00
    看着很奇葩的问题啊,最初的需求是什么?
    murmur
        2
    murmur  
       2022-01-13 14:57:37 +08:00
    应该是敏感词过滤吧,
    这个只能老老实实匹配,漏一个问题就大了,不要想着诀窍,真出了问题大事
    timi
        3
    timi  
    OP
       2022-01-13 14:58:53 +08:00
    @icyalala 类似于根据不同的 URL 进行路由,但是简单的字符串匹配满足不了……
    ebingtel
        4
    ebingtel  
       2022-01-13 14:59:55 +08:00
    搞个多进程的 daemon 服务,每个进程负责 部分正则
    dallaslu
        5
    dallaslu  
       2022-01-13 15:01:18 +08:00
    如果不是正则的话,可以构造一个包含一万个节点的匹配树。如果是正则的话,好像也有可能啊,怕不是要自己魔改一个正则实现来构造匹配树
    nekoneko
        6
    nekoneko  
       2022-01-13 15:03:32 +08:00
    多线程并发呗
    java 直接 parallelStream
    ch2
        7
    ch2  
       2022-01-13 15:05:48 +08:00
    与每个模式串的复杂度有关,如果模式串复杂度都很低,那么 1 万次匹配也是秒出
    dallaslu
        8
    dallaslu  
       2022-01-13 15:07:50 +08:00
    chihiro2014
        9
    chihiro2014  
       2022-01-13 15:08:31 +08:00
    前缀树?
    murmur
        10
    murmur  
       2022-01-13 15:10:14 +08:00
    @dallaslu AC 自动机不能完成所有东西,比如我要匹配(拼音是 sha 的所有汉字)(2-5 个任意非中文字符)(拼音为 b 的所有汉字)

    你的 AC 自动机怎么弄
    murmur
        11
    murmur  
       2022-01-13 15:10:58 +08:00
    @dallaslu 回错了,我没看楼主突然回了

    路由这个东西还要自己做的,啥库不支持模糊路由啊
    shyrock
        12
    shyrock  
       2022-01-13 15:22:56 +08:00   ❤️ 2
    正则就是匹配条件吧?所以要想保持匹配结果不变,又想提升效率。要么并行、要么提升单次匹配的效率。
    对了,还有一个思路是利用已经匹配的正则所加入的信息,也就是说要先分析这一万个正则的相关性,把匹配 A 的必然匹配 B 这种关系找出来;或者匹配 C 的必然不匹配 D 。这样可以构建一个匹配的顺序,尽量减少匹配次数。
    lianyue
        13
    lianyue  
       2022-01-13 15:35:27 +08:00
    如果只需要某一个匹配的结果那

    吧 10000 个正则 合并成 一个正则 用 `|` 分开 并且每个正则分组好(?<id1>正则规则 1) (?<id2>正则规则 2)
    然后 响应结果 看哪个下标不为 null 就知道是哪个正则匹配成功了
    ys2016814
        14
    ys2016814  
       2022-01-13 15:36:02 +08:00
    FST
    lianyue
        15
    lianyue  
       2022-01-13 15:37:31 +08:00
    (?<id1>原始的正则规则 1)|(?<id2>原始的正则规则 2)
    GeruzoniAnsasu
        16
    GeruzoniAnsasu  
       2022-01-13 16:20:07 +08:00   ❤️ 6
    …… 你应该尝试把那 1w 个正则编译到一起去

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

    虽然编译要跑一个小时,但是运行快啊(
    wszgrcy
        17
    wszgrcy  
       2022-01-13 16:56:23 +08:00
    把 1w 个正则合并成一个正则,让引擎自己优化?[doge]
    litmxs
        18
    litmxs  
       2022-01-13 17:00:21 +08:00 via Android
    试试 Intel 的 hyperscan ,多模正则库
    Chinsung
        19
    Chinsung  
       2022-01-13 17:45:20 +08:00
    给正则构建一个树,一万个正则之间肯定有互斥的和包含关系,根据正则之间的关系简单分组,在正则树上匹配查找。
    SteveWoo
        20
    SteveWoo  
       2022-01-13 18:42:38 +08:00
    弄 1w 台主机,发给 1w 个主机,算完了给你结果
    popvlovs
        21
    popvlovs  
       2022-01-13 18:50:41 +08:00
    hyperscan
    jianhua
        22
    jianhua  
       2022-01-13 18:58:10 +08:00
    包括:
    1. 缓存匹配结果和类型。记录上次匹配结果和特征,引入特征查找算法。
    2. 通过分析正则的含义,打标签(数字、字母、字符等匹配规则):
    2.1 通过建立离线测试集,暴力测试正则的匹配含义
    2.2 通过分析正则语法
    基于正则的标签,优化原始数据特征提取和检索算法。最简单的,当你知道输入字符串是一个数字,那么应该排除掉所有字母、字符类的正则。
    timi
        23
    timi  
    OP
       2022-01-13 20:40:56 +08:00
    @GeruzoniAnsasu 感觉路子很野但是又很有道理😂
    timi
        24
    timi  
    OP
       2022-01-13 20:45:21 +08:00
    @murmur 其实不是路由,更接近于给某个 URL 贴个标签这样的,场景比较特殊不变透露但基本就是酱紫
    paopjian
        25
    paopjian  
       2022-01-14 09:53:26 +08:00
    @GeruzoniAnsasu 第一次看到这么厉害的库,英语都没怎么读懂,好难
    seanzxx
        26
    seanzxx  
       2022-01-14 11:44:52 +08:00
    @GeruzoniAnsasu 我也是第一时间想到了 ragel ,以前拿这个来重写了一堆手写的正则匹配,真的很好用
    yesterdaysun
        27
    yesterdaysun  
       266 天前
    合并正则+多线程
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4129 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 05:26 · PVG 13:26 · LAX 22:26 · JFK 01:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.