c++ - 检查一个正则表达式是否覆盖另一个正则表达式

Question

我正在尝试实现文本聚类算法。该算法通过将相似的原始文本行替换为正则表达式来对其进行聚类，并汇总与每个正则表达式匹配的模式数量，以便提供输入文本的简洁摘要，而不是显示输入文本中的重复模式。在这次尝试中，我遇到了查找一个正则表达式是否覆盖另一个正则表达式的需要。

假设我们只关注带有“*”和“+”通配符的正则表达式，即“*”表示字母表出现零次或多次，而“+”表示出现一次或多次的字母表。还假定字符集为 ASCII。

例如:

1. AB covers AB
      This is straightforward.
2. ABC* covers ABC
      Because ABC* can generate: ABC, ABCC, ABCCC etc.
3. A*B+C* covers AB+C*
      Because A*B+C* can generate ABBC, AABBC, AABBCC etc. which covers
      all strings generated by AB+C*.
4. A+M+BC* covers AMM+B+C+M+BC*
      Similar to case [3] above.

基本上我正在寻找以下方法的有效实现，该方法告诉 strA(可能包含正则表达式)是否覆盖 strB(可能包含正则表达式)。请注意，还应该有一种方法可以转义输入字符串 strA 和 strB 中的正则表达式字符“*”和“+”。

C++ 中的方法签名:

bool isParentRegex(const string& strA, const string& strB)

我的想法是需要递归的方式来实现，可能会有点复杂。但我很想知道我是否可以重用现有的实现而不是重新发明轮子，或者是否有任何其他直接的方法可以做到这一点。

Answer 1

考虑到您提出的简单正则表达式语法，解决方案相当简单。

举个更复杂的例子，A+M+BC* 涵盖 AMM+B+C+M+BC* 您可以将其重写为 A{1,}M{1,}B{1,1}C{0,} 覆盖 A{1,1}M{2,}B{ 1,}C{1,}M{1,}B{1,1}C{0,}

这引出了一个简单的规则:R1 覆盖 R2 如果所有符号以相同顺序出现，则 R1 的所有下界是小于或等于R2的上界，R1的上界大于或等于R2的上界。

现在简单规则有一个小问题。 AB*C 覆盖了 AC，即可选符号有可能出现在 R1 而不是 R2 中。当 R1 中的(可选)符号未出现在 中的等效位置时，您可以通过在 R2 中插入 {0,0} 来解决此问题R2。例如。 AB*C 确实覆盖了 AB{0,0}C。

“可选符号”规则是一种优化。如果 R1 中的符号不​​是可选的，那么 R1 肯定不会覆盖 R2。例如。 AB+C 不覆盖 AC。因此无需插入 B{0,0}。但如果这样做，您会发现 A{1,1}B{1,}C{1,1} 不包含 A{1,1}B{0 ,0}C{1,1} 因为 B (1) 上的 R1 下界大于 R2 下界绑定(bind)到 B (0)