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

2023-02-20 11:39:02 +08:00
 Aruforce
比如\d 必定是*的子集。
搜索了下应该涉及编译相关的东西...半路出家完全不会啊...
有成熟的工具么?
1109 次点击
所在节点    程序员
14 条回复
zhuangjia
2023-02-20 11:51:14 +08:00
感觉这种场景比较适合使用 chatGPT 了
lookStupiToForce
2023-02-20 12:03:42 +08:00
要满足题述要求的完备,需要对 A 和 B 这两个正则做形式化证明( A 可转化为 B ,属于 B 的特例,B 则不可转化为 A )
感觉这种工作得看学计算理论的那帮人有没有造出相应的轮子
Aruforce
2023-02-20 12:09:48 +08:00
@lookStupiToForce A1 == B1 也行...
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
2023-02-20 12:33:46 +08:00
简单的可以展开成 DFA 然后 dfs ,但是如果带环的话就不太好判了
ALLROBOT
2023-02-20 12:40:57 +08:00
把捕获组转换 python 的 list 、字典、字符串等数据格式,然后 if 判断完事
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
2023-02-20 13:29:59 +08:00
感觉可以用上范畴论了
iamqk
2023-02-20 13:34:55 +08:00
如果有 set 容器的话
把两个 set 合并,如果数目是 B1 的话
就可以判断了
xuanbg
2023-02-20 13:46:03 +08:00
单从正则字符串本身来判断的话,除非只是定义,否则应该是不准确的。因为特定目标数据会导致 A 和 B 符合定义上的交集,但实际上没有相交的数据,变成并集;或者 A 完全包含 B ,变成 B 是 A 的子集。
Aruforce
2023-02-20 20:32:49 +08:00
@lookStupiToForce 周末 再仔细看下。。感觉有点像。。。
Aruforce
2023-02-20 20:40:45 +08:00
@ALLROBOT 没太看懂 但感觉不是
Aruforce
2023-02-20 20:41:21 +08:00
@lyhang 你理解错意思了
Aruforce
2023-02-20 20:43:25 +08:00
@xuanbg 入参 只有 A 和 B 两个正则本身

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

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

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

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

© 2021 V2EX