V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Aruforce
V2EX  ›  程序员

存在 A、B 两个正则表达式描述的数据集合 A1、B1,是否存在一种通用的方式判断 A1 完全是 B1 的子集?

  •  
  •   Aruforce · 2023-02-20 11:39:02 +08:00 · 1075 次点击
    这是一个创建于 402 天前的主题,其中的信息可能已经有所发展或是发生改变。
    比如\d 必定是*的子集。
    搜索了下应该涉及编译相关的东西...半路出家完全不会啊...
    有成熟的工具么?
    14 条回复    2023-02-20 20:43:25 +08:00
    zhuangjia
        1
    zhuangjia  
       2023-02-20 11:51:14 +08:00
    感觉这种场景比较适合使用 chatGPT 了
    lookStupiToForce
        2
    lookStupiToForce  
       2023-02-20 12:03:42 +08:00
    要满足题述要求的完备,需要对 A 和 B 这两个正则做形式化证明( A 可转化为 B ,属于 B 的特例,B 则不可转化为 A )
    感觉这种工作得看学计算理论的那帮人有没有造出相应的轮子
    Aruforce
        3
    Aruforce  
    OP
       2023-02-20 12:09:48 +08:00
    @lookStupiToForce A1 == B1 也行...
    lookStupiToForce
        4
    lookStupiToForce  
       2023-02-20 12:16:19 +08:00
    英文讨论可以用 regex expression true subset 做关键词搜,不过搜出来的多是 SO 的问答或者其他讨论串

    中文倒是有人写过代码解决方法,原理用的有限自动机判断是否等价 /包含(判断此人是个计算理论 /编译原理大神😂)
    wu-kan[.]cn/2020/07/03/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%85%B3%E7%B3%BB%E5%88%A4%E5%AE%9A/

    OP 你有心思可以就着参考实现一下
    learningman
        5
    learningman  
       2023-02-20 12:33:46 +08:00
    简单的可以展开成 DFA 然后 dfs ,但是如果带环的话就不太好判了
    ALLROBOT
        6
    ALLROBOT  
       2023-02-20 12:40:57 +08:00
    把捕获组转换 python 的 list 、字典、字符串等数据格式,然后 if 判断完事
    lyhang
        7
    lyhang  
       2023-02-20 13:25:42 +08:00
    import re

    def is_subset(A1, B1):
    """
    判断 A1 是否完全是 B1 的子集
    参数:
    A1: 列表,表示数据集合 A1
    B1: 列表,表示数据集合 B1
    返回值:
    如果 A1 完全是 B1 的子集,返回 True ,否则返回 False
    """
    # 将 B1 中的所有正则表达式编译成 pattern 对象
    patterns = [re.compile(b) for b in B1]
    # 遍历 A1 中的所有元素,看是否能被 B1 中的正则表达式匹配
    for a in A1:
    matched = False
    for p in patterns:
    if p.match(a):
    matched = True
    break
    # 如果 A1 中的某个元素不能被 B1 中的任何正则表达式匹配,那么 A1 不是 B1 的子集
    if not matched:
    return False
    # 如果 A1 中的所有元素都能被 B1 中的正则表达式匹配,那么 A1 是 B1 的子集
    return True
    mascteen
        8
    mascteen  
       2023-02-20 13:29:59 +08:00 via Android
    感觉可以用上范畴论了
    iamqk
        9
    iamqk  
       2023-02-20 13:34:55 +08:00
    如果有 set 容器的话
    把两个 set 合并,如果数目是 B1 的话
    就可以判断了
    xuanbg
        10
    xuanbg  
       2023-02-20 13:46:03 +08:00
    单从正则字符串本身来判断的话,除非只是定义,否则应该是不准确的。因为特定目标数据会导致 A 和 B 符合定义上的交集,但实际上没有相交的数据,变成并集;或者 A 完全包含 B ,变成 B 是 A 的子集。
    Aruforce
        11
    Aruforce  
    OP
       2023-02-20 20:32:49 +08:00
    @lookStupiToForce 周末 再仔细看下。。感觉有点像。。。
    Aruforce
        12
    Aruforce  
    OP
       2023-02-20 20:40:45 +08:00
    @ALLROBOT 没太看懂 但感觉不是
    Aruforce
        13
    Aruforce  
    OP
       2023-02-20 20:41:21 +08:00
    @lyhang 你理解错意思了
    Aruforce
        14
    Aruforce  
    OP
       2023-02-20 20:43:25 +08:00
    @xuanbg 入参 只有 A 和 B 两个正则本身
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1769 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 16:34 · PVG 00:34 · LAX 09:34 · JFK 12:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.