regex - 自动查找短正则表达式来匹配一组单词？

Question

我不是在寻找特定的正则表达式，而是在寻找可以找到它们的软件。

假设我有一个文件 A 和一个文件 B:如何找到一个匹配 A 中所有单词但不匹配 A 中任何单词的正则表达式？

如果 A 包含“truit Fruit”而 B 包含“ridiculous”，则软件可能会返回类似“.ru.”但仅返回“.r.”的内容将是无效的。

这是另一个问题 [1] 的“实用”方面，尽管我感兴趣的是找到一个能够在实践中解决该问题的实际软件。

感谢您的帮助，

内森

[1] https://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem

Answer 1

没有算法可以以某种方式从示例中“巧妙地导出”正则表达式。您只能通过 A 中单词的公共(public)子串的所有排列来实现迭代的强力尝试，并对其进行测试 B 直到找到解决方案。但不能保证您能找到解决方案。

对于 A 中所有单词没有公共(public)子串的情况，您可以扩展该方法以在正则表达式中引入“or”运算符。但这种方式真的很丑陋而且很慢。

如果这没有找到解决方案，那么您必须继续扩展您的尝试，以便通过迭代 B 中的所有单词并从中创建反模式，将排除规则添加到表达式中。可怕的尝试。

正如所说:永远不能保证你能找到解决方案。

<小时/>

但是有一件事:

如果您对最终正则表达式的外观不感兴趣，您可以这样做:创建一个正则表达式，只需将“A 的空白填充版本”中的所有单词与“或”操作组合起来(因此在您的示例中为 \struit\s|\sfruit\s )。显然，这种尝试创造了巨大的表达。然后，您必须小心排除 B 中可能再次出现的确切子字符串。这可能会导致表达式仍然更长。

<小时/>

底线:对此没有真正优雅的解决方案。仅仅是因为这个问题不允许这样做。问题是:为什么它必须是正则表达式？为什么不能简单地进行字符串比较？在这样一个模糊定义的场景中，无论如何这可能不会更昂贵......