相关疑难解决方法(0)

我有一个庞大的正则表达式集合,当匹配时调用一个特定的http处理程序.一些较旧的正则表达式是无法访问的(例如a.c* ? abc*),我想修剪它们.

是否有一个库给出两个正则表达式会告诉我第二个是否是第一个的子集？

我一开始并不确定这是否具有可判定性(它的气味就像一个不同名称的停止问题).但事实证明它是可判定的.

我正在寻找类似于Redis KEYS命令所接受的匹配的glob样式模式.引用:

• h？llo匹配hello,hallo和hxllo
• h*llo匹配hllo和heeeello
• h [ae] llo匹配hello和hallo,但不匹配hillo

但是我没有匹配文本字符串,而是将模式与另一个模式匹配,所有运算符都在两端都有意义.

例如,这些模式应该在同一行中相互匹配:

prefix*       prefix:extended*
*suffix       *:extended:suffix
left*right    left*middle*right
a*b*c         a*b*d*b*c
hello*        *ok
pre[ab]fix*   pre[bc]fix*

这些不应该匹配:

prefix*       wrong:prefix:*
*suffix       *suffix:wrong
left*right    right*middle*left
pre[ab]fix*   pre[xy]fix*
?*b*?         bcb

所以我想知道......

• 如果可以这样做(实施验证算法),如果有的话？
• 如果不可能,正则表达式的哪个子集是可能的？(即禁止*通配符？)
• 如果它确实可能,什么是有效的算法？
• 需要什么时间复杂度？

编辑:在RegEx子集上找到这个其他问题,但这与单词hello*和*ok匹配不是彼此的子集/超集的单词不完全相同,但它们相交.

所以我想从数学角度来看,这可能是用来表达的; 是否有可能确定地检查一个模式匹配的一组单词与另一个模式匹配的一组单词相交,导致非空集？

编辑:朋友@neizod绘制了这个消除表,它可以整齐地显示可能是潜在/部分解决方案:消除规则

编辑:将为那些也可以提供工作代码(使用任何语言)和测试用例证明它的人增加额外的奖励.

编辑:添加？*b*？@DanielGimenez在评论中发现的测试用例.

有没有办法找出两个任意正则表达式是否相同？看起来像复杂的问题,但可能有一些DFA简化机制或什么？

如何验证一个XSD架构是否是另一个XSD架构的子集？

我们正在使用一系列"蓝图"XSD架构(定义子组件可用的所有可能输入或输出)创建系统系统应用程序.正在实现许多子组件,这些子组件使用XML文件在它们之间传递数据.每个子组件创建相关蓝图XSD架构的子集(以指示它选择实现哪些可能的输入或输出).任何针对子集XSD架构验证的XML数据文件也必须针对蓝图XSD架构进行验证,但反之则不然(因为子集XSD架构可能不包含蓝图XSD架构中的所有"可选"或"选择"XML元素,并且它可以选择进一步限制现有XML标记上的允许数据值).系统将针对该子组件的子集XSD架构验证子组件的所有XML输入(标记任何错误输入并隔离数据相关问题的来源).

在测试期间,我们打算验证每个子组件的子集XSD架构是否真的是关联蓝图XSD架构的子集,但我们没有自动执行此验证的方法.这些XSD架构相当庞大且难以手动进行此类测试.有一种"验证XSD文件1对XSD文件2"命令会很好,类似于Java如何根据XSD架构执行XML文件验证.我们要确认每个子组件的子集XSD架构都不允许任何违反蓝图XSD架构的XML输入/输出组合.使用这种模式到模式功能,验证子组件A的输出XML是否适合用作子组件B的输入也是非常有用的(我们可以轻松地针对XSD模式验证单个输出XML,但是我们想确认子组件A的所有可能的XML输出都将针对子组件B的XSD架构进行验证.

有用的信息:这个应用程序是一个Java 6应用程序的集合,实现为OSGi包,并使用Maven 2.2.1编译/执行.使用任何特定的开发IDE都没有要求.该系统正在Microsoft Windows XP环境中进行测试,但也有计划在其他环境中执行此系统(因此首选跨平台解决方案).

背景:

我有一个小的(目前不到100个)但正在增长的正则表达式集合,我想优化确定给定文本字符串的过程我的集合中哪些RE与文本字符串匹配.

一些RE有一个排序关系 - 例如,如果我知道字符串$ t匹配/ windows/i,那么我也知道$ t匹配/windows.*2000/i.因此,当我对我的集合中的RE测试$ t时,我可以跳过测试/ windows/i,如果我已经针对/windows.*2000/i测试了$ t并找到了匹配(尽管如果/windows.*2000/i确实如此)不匹配当然我不能跳过对/ windows/i的测试.

请注意,我的集合中的所有RE都不是完全等效的(对于任何一对RE,至少有一个匹配一个的文本字符串与另一个不匹配).

战略:

我想构建一个有向图G,其中有一个节点用于我的集合中的每个RE,并且每对RE的有向边具有排序关系(A - > B表示"匹配A意味着与B匹配"),并找到一个图的节点的"最小生成集"(节点S的最小集合,使得G中的每个节点位于源自S的有向路径上).

简单的部分:

有很多免费的算法可用于定向非循环图.因此,一旦为我的RE集合构建了图形G(这是不同的,应该保证G是非循环的),我不希望找到一个合适的算法来寻找G的最小生成集.

在哪里我需要帮助:

我想找到一种有效的方法来查找我的集合中的RE之间的所有排序关系 - 也许还要确保集合中没有两个RE是等价的(我需要一种方法来自动验证这个,因为新的RE是添加).

因此,我的(基本上是随机的)网络搜索至少提出了一个合理的说法,即确定两个RE之间存在什么(如果有的话)排序关系的合理方法确实存在,但尚未发现任何完整算法的描述.

有没有人知道现有的实现(用于比较RE),这些实现是合理有效的,可免费获得的,并且(理想情况下)是用一种流行的脚本语言或C/C++实现的？