V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
daxin945
V2EX  ›  Python

每条字符串数据都要循环匹配大概 200 左右的正则表达式,怎么做速度可以快点?

  •  1
     
  •   daxin945 · 2023-07-06 16:51:24 +08:00 · 3024 次点击
    这是一个创建于 512 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我定义了一个数组,长度目前是 200 ,未来应该会更长,数组内元素都是 re.compile 大概长这样 _list = [ (re.compile("正则表达式 1", re.IGNORECASE), (re.compile("正则表达式 2", re.IGNORECASE), ]

    正则表达式中有若干 .* 的操作,但是能避免的都避免了 在取值的时候我用的 re.findall()

    每来一个新的字符串,都要遍历一遍数组,再加上正则表达式,感觉速度很慢 想请教有没有什么更好的方法

    23 条回复    2023-07-07 20:02:40 +08:00
    Yuan2One
        1
    Yuan2One  
       2023-07-06 16:55:10 +08:00 via Android
    类似于前缀树一样写匹配树?但是好麻烦,要重新设计树结构,还得写匹配方法
    billlee
        2
    billlee  
       2023-07-06 16:55:37 +08:00 via Android   ❤️ 2
    去调 C++ 的 hyperscan.
    mervinmemory
        3
    mervinmemory  
       2023-07-06 17:15:45 +08:00   ❤️ 1
    来自 gpt 的回复:


    对于每次来的新字符串都要遍历整个正则表达式数组,这可能导致性能下降。如果你希望提高匹配速度,可以考虑使用更高效的数据结构,如字典( Dictionary )或者前缀树( Trie )。

    下面是一种可能的优化方法:

    1. 使用字典替代列表:将正则表达式和相应的操作存储在字典中,其中键为正则表达式字符串,值为对应的操作。这样可以通过正则表达式快速查找到对应的操作,而无需遍历整个列表。

    2. 在字典中使用前缀树:将正则表达式作为前缀树的键,操作作为对应节点的值。前缀树可以提高匹配效率,特别是当正则表达式存在共同前缀时,可以减少不必要的匹配操作。

    这是一个示例代码,展示了如何使用字典和前缀树进行优化:

    ```python
    import re
    from collections import defaultdict

    class TrieNode:
    def __init__(self):
    self.children = defaultdict(TrieNode)
    self.operations = []

    def insert(root, regex, operation):
    node = root
    for char in regex:
    node = node.children[char]
    node.operations.append(operation)

    def find_operations(root, text):
    results = []
    node = root
    for char in text:
    if char in node.children:
    node = node.children[char]
    results.extend(node.operations)
    elif '*' in node.children:
    node = node.children['*']
    results.extend(node.operations)
    else:
    node = root
    return results

    # 构建前缀树
    root = TrieNode()
    for regex, operation in _list:
    insert(root, regex.pattern, operation)

    # 搜索匹配操作
    text = "待匹配的字符串"
    matching_operations = find_operations(root, text)

    # 对匹配操作进行处理
    for operation in matching_operations:
    # 处理匹配操作
    ```

    注意,这只是一种优化思路,并且需要根据你的具体需求进行适当的调整。如果正则表达式的数量非常庞大,可能需要使用更高级的算法和数据结构来进一步提高性能。
    aloxaf
        4
    aloxaf  
       2023-07-06 17:31:12 +08:00
    发一下你的正则长啥样?
    200+ 个正则,这是在搞敏感词过滤?
    coderxy
        5
    coderxy  
       2023-07-06 17:39:26 +08:00
    首先,多个正则规则可以写到一起,用|分开。
    coderxy
        6
    coderxy  
       2023-07-06 17:41:29 +08:00   ❤️ 1
    其次, 用正则做这种性能不好,如果是敏感词后期可能有十几万个, 要改用 DFA 去实现
    skyrim61
        7
    skyrim61  
       2023-07-06 17:54:59 +08:00   ❤️ 1
    来自 newbing 的回复
    如果你需要在一个字符串中查找多个正则表达式模式,可以考虑以下几种方法来提高性能:

    避免使用过于复杂的正则表达式。正则表达式中的某些特殊字符(如 .* 和 .+)可能会导致回溯,从而降低匹配速度。尽量使用简单的正则表达式,避免使用过多的特殊字符。

    将多个正则表达式合并为一个。如果你需要在一个字符串中查找多个正则表达式模式,可以考虑将这些模式合并为一个正则表达式,然后一次性进行匹配。例如,你可以使用 | 字符将多个模式连接起来,形成一个新的正则表达式。

    使用第三方库。Python 标准库中的 re 模块提供了基本的正则表达式功能,但是在某些情况下可能不够高效。你可以考虑使用第三方库(如 regex ),它们通常提供了更快的匹配速度和更多的功能。

    希望这些建议能够帮助你提高正则表达式匹配的性能。如果你有其他问题,欢迎随时咨询我
    iOCZ
        8
    iOCZ  
       2023-07-06 17:57:38 +08:00
    没办法
    lasuar
        9
    lasuar  
       2023-07-06 18:57:31 +08:00
    参考 #5
    NoOneNoBody
        10
    NoOneNoBody  
       2023-07-06 19:34:16 +08:00
    这种非 IO 的最适合多进程并发了,不过 200 体现不出优势
    volvo007
        11
    volvo007  
       2023-07-06 21:51:41 +08:00
    我想到的也是多线程,拆成 10 份每个 20 不是瞬间做完。这个案例也不用加锁
    flyqie
        12
    flyqie  
       2023-07-06 22:04:56 +08:00
    解决方法就是并发,当然这个是用资源换时间。。
    harrozze
        13
    harrozze  
       2023-07-06 22:13:39 +08:00
    @coderxy #6 以前做过你在 #5 说的方式,用 python 做一个论坛的过滤还是能行的。DFA 是一种方式,还有一种方式是分级处理。如果 OP 也是要做敏感词过滤的话。也就是说,对于非卡脖子的敏感词,用先发后审的方式分布式处理。
    dqzcwxb
        14
    dqzcwxb  
       2023-07-06 22:16:16 +08:00
    DFA
    GeruzoniAnsasu
        15
    GeruzoniAnsasu  
       2023-07-06 22:16:24 +08:00   ❤️ 2
    参考之前的一万个正则的处理方式:

    https://www.v2ex.com/t/828016#r_11270571
    xiangyuecn
        16
    xiangyuecn  
       2023-07-06 22:40:47 +08:00   ❤️ 4
    用 Trie 树,.*这种的简单正则表达式完全可以转换成多个关键词的匹配,复杂的也不怕 尽量提取出关键词 先高速判断这个正则是确定要参与匹配计算 过滤掉不参与的正则,那 200 个正则瞬间 从 1 秒 变成 1 毫秒💪
    est
        17
    est  
       2023-07-06 22:57:29 +08:00
    intel hyperscan
    jiulang
        18
    jiulang  
       2023-07-06 23:28:12 +08:00
    如果是域名匹配,记录可以放到哈希表,输入的字符串做子域名切割(分词)来逐一匹配
    0xWalker
        19
    0xWalker  
       2023-07-07 09:04:51 +08:00   ❤️ 1
    hyperscan 正解,并行匹配还有指令优化
    liangxin1998
        20
    liangxin1998  
       2023-07-07 09:33:09 +08:00   ❤️ 1
    以下是来自 GPT4 的回复:

    在 Python 中,正则表达式确实可能是相当消耗资源的,特别是当你处理大量的数据或者复杂的正则表达式时。这是因为正则表达式的匹配机制是回溯的,也就是当一个匹配失败时,它会返回上一个状态并尝试其他可能的匹配方式。而使用 "." 和 "*" 这样的通配符可以增加正则表达式的复杂度,使得匹配过程变得更慢。

    根据你的描述,你似乎在对每一个新的字符串遍历这个长度可能会增长到 200 以上的正则表达式列表。这种情况下,优化的方式可能依赖于你的具体应用场景。以下是一些可能的优化建议:

    尽可能使正则表达式更简单:越复杂的正则表达式需要的计算资源就越多,尤其是当你有许多复杂的正则表达式需要匹配时。尽可能地避免使用 ".*" 和其他可能导致大量回溯的模式。

    考虑预处理字符串:如果可能的话,考虑在正则表达式匹配之前对字符串进行预处理,以减小正则表达式的复杂性。这可能包括删除或替换不必要的字符,将字符串切分成较小的部分,或者将字符串转换为更容易处理的格式。

    使用编译的正则表达式:Python 的 re 模块提供了一个 compile 函数,可以用来预编译正则表达式。这样做可以让你的代码在匹配正则表达式时运行得更快。

    考虑使用其他字符串匹配算法:如果你的问题可以通过其他的字符串匹配算法来解决,那么可能会更有效率。例如,如果你只是在寻找特定的字串,那么使用 KMP ,Boyer-Moore 或 Rabin-Karp 这样的字符串匹配算法可能会更快。

    使用多线程或多进程:如果你有大量的字符串需要处理,你可以考虑使用 Python 的 multiprocessing 或 threading 模块来并行处理这些字符串。

    如果你的正则表达式是有序的,你可以在匹配时使用二分搜索:这样做的前提是你的正则表达式可以按照一定的规则排序,这样你可以在匹配时使用二分搜索而不是遍历整个列表。

    这只是一些可能的优化方法,并不能保证在所有情况下都有效。具体的优化方法需要根据你的应用场景和需求来定。
    yesterdaysun
        21
    yesterdaysun  
       2023-07-07 09:48:48 +08:00
    我支持合并正则的方案, 在以前的类似的案例里面, 把一批 200 个左右的正则合成 1 个, 能够提高 30 倍左右的效率, 当然这个和具体的数据有关系, 但是说明这个方案是可行的.

    原理我猜应该就是合并后的正则, 引擎编译时会自动优化形成类似 DFA 的数据结构或者算法, 合并正则可能也要一定的优化, 比如排序, 尽可能让有相同前缀的放在一组, 然后也要优化一些.*这样的写法, 就不同的方案都简单试试, 套入实际数据看看那种效率会变高
    snylonue
        22
    snylonue  
       2023-07-07 17:18:09 +08:00
    rust 的 regex 有 RegexSet ,可以找找有没有 python 绑定
    kaneg
        23
    kaneg  
       2023-07-07 20:02:40 +08:00 via iPhone
    还有一个思路,如果说这些正则匹配率差异比较大,可以给正则按照匹配的命中率动态排序,这样可以尽可能早地匹配到。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1091 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 23:18 · PVG 07:18 · LAX 15:18 · JFK 18:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.