给定两个字符串列表 A 和 B，请找出最短的正则表达式，它匹配了 A 中的所有字符串但不匹配 B 中的任何字符串。请注意，此正则表达式可以匹配/不匹配其他不在 A 和 B 中的字符串。为简单起见，我们可以假设字母表大小为 2 个字符 - 0 和 1。只允许使用以下运算符：
* - 零个或多个
? - 零个或一个
+ - 一个或多个
() - 括号
为简单起见，不允许使用正则表达式非运算符。我不知道是否允许使用 or 运算符（|）会简化问题。当然，A 和 B 没有共同元素。以下是一些示例：
A=[00,01,10]
B=[11]
answer = 1*0+1*
A=[00,01,11]
B=[10]
answer = 0*1*
private static void GenerateRegex(IEnumerable<string> target, IEnumerable<string> dontMatch)
{
string distinctSymbols = new String(target.SelectMany(x => x).Distinct().ToArray());
string genes = distinctSymbols + "?*()+";
Func<string, uint> calcFitness = str =>
{
if (str.Count(x => x == '(') != str.Count(x => x == ')'))
{
return Int32.MaxValue;
}
if ("?*+".Any(x => str[0] == x))
{
return Int32.MaxValue;
}
if ("?*+?*+".ToArray().Permute(2)
.Any(permutation => str.IndexOf(new string(permutation.ToArray())) != -1))
{
return Int32.MaxValue;
}
Regex regex;
try
{
regex = new Regex("^" + str + "$");
}
catch (Exception)
{
return Int32.MaxValue;
}
uint fitness = target.Aggregate<string, uint>(0, (current, t) => current + (regex.IsMatch(t) ? 0U : 1));
uint nonFitness = dontMatch.Aggregate<string, uint>(0, (current, t) => current + (regex.IsMatch(t) ? 10U : 0));
return fitness + nonFitness;
};
for (int targetGeneLength = distinctSymbols.Length; targetGeneLength < genes.Length * 2; targetGeneLength++)
{
string best = new GeneticSolver(50).GetBestGenetically(targetGeneLength, genes, calcFitness, true);
if (calcFitness(best) != 0)
{
Console.WriteLine("-- not solved with regex of length " + targetGeneLength);
continue;
}
Console.WriteLine("solved with: " + best);
break;
}
}
应用它到你的样本中的结果：
public void Given_Sample_A()
{
var target = new[] { "00", "01", "10" };
var dontMatch = new[] { "11" };
GenerateRegex(target, dontMatch);
}
输出：
Generation 1 best: 10 (2)
Generation 2 best: 0+ (2)
Generation 5 best: 0* (2)
Generation 8 best: 00 (2)
Generation 9 best: 01 (2)
-- not solved with regex of length 2
Generation 1 best: 10* (2)
Generation 3 best: 00* (2)
Generation 4 best: 01+ (2)
Generation 6 best: 10+ (2)
Generation 9 best: 00? (2)
Generation 11 best: 00+ (2)
Generation 14 best: 0?1 (2)
Generation 21 best: 0*0 (2)
Generation 37 best: 1?0 (2)
Generation 43 best: 10? (2)
Generation 68 best: 01* (2)
Generation 78 best: 1*0 (2)
Generation 79 best: 0*1 (2)
Generation 84 best: 0?0 (2)
Generation 127 best: 01? (2)
Generation 142 best: 0+1 (2)
Generation 146 best: 0+0 (2)
Generation 171 best: 1+0 (2)
-- not solved with regex of length 3
Generation 1 best: 1*0+ (1)
Generation 2 best: 0+1* (1)
Generation 20 best: 1?0+ (1)
Generation 31 best: 1?0* (1)
-- not solved with regex of length 4
Generation 1 best: 1*00? (1)
Generation 2 best: 0*1?0 (1)
Generation 3 best: 1?0?0 (1)
Generation 4 best: 1?00? (1)
Generation 8 best: 1?00* (1)
Generation 12 best: 1*0?0 (1)
Generation 13 best: 1*00* (1)
Generation 41 best: 0*10* (1)
Generation 44 best: 1*0*0 (1)
-- not solved with regex of length 5
Generation 1 best: 0+(1)? (1)
Generation 36 best: 0+()1? (1)
Generation 39 best: 0+(1?) (1)
Generation 61 best: 1*0+1? (0)
solved with: 1*0+1?
第二个样例：
public void Given_Sample_B()
{
var target = new[] { "00", "01", "11" };
var dontMatch = new[] { "10" };
GenerateRegex(target, dontMatch);
}
输出：
Generation 1 best: 00 (2)
Generation 2 best: 01 (2)
Generation 7 best: 0* (2)
Generation 12 best: 0+ (2)
Generation 33 best: 1+ (2)
Generation 36 best: 1* (2)
Generation 53 best: 11 (2)
-- not solved with regex of length 2
Generation 1 best: 00* (2)
Generation 2 best: 0+0 (2)
Generation 7 best: 0+1 (2)
Generation 12 best: 00? (2)
Generation 15 best: 01* (2)
Generation 16 best: 0*0 (2)
Generation 19 best: 01+ (2)
Generation 30 best: 0?0 (2)
Generation 32 best: 0*1 (2)
Generation 42 best: 11* (2)
Generation 43 best: 1+1 (2)
Generation 44 best: 00+ (2)
Generation 87 best: 01? (2)
Generation 96 best: 0?1 (2)
Generation 125 best: 11? (2)
Generation 126 best: 1?1 (2)
Generation 135 best: 11+ (2)
Generation 149 best: 1*1 (2)
-- not solved with regex of length 3
Generation 1 best: 0*1* (0)
solved with: 0*1*
A中，并使B为空以简化问题。我想知道那时速度会有多快。当你不需要精确解决方案时，遗传算法往往效果更好，否则它们通常相当低效。 - IVlad这个项目可以从给定的单词列表生成正则表达式： https://github.com/bwagner/wordhierarchy
然而，它只使用了"|"、非捕获组"(?:)"和选项"?"。
示例用法：
java -jar dist/wordhierarchy.jar 00 01 10
-> 10|0(?:1|0)
java -jar dist/wordhierarchy.jar 00 01 11
-> 0(?:0|1)|11
java -jar dist/wordhierarchy.jar 000 001 010 011 100 101 110 111
-> 1(?:0(?:0|1)|1(?:0|1))|0(?:1(?:1|0)|0(?:1|0))
java -jar dist/wordhierarchy.jar 000 001 010 100 101 110 111
-> 1(?:0(?:0|1)|1(?:1|0))|0(?:10|0(?:1|0))
如果这是一个作业问题，那就像是“一份作业，得到整个班的A”类型的。 我认为这个问题中缺少了“或”运算符。
有一个显而易见的解决方案是A0|A1|A2|...，但在尝试找到最短解决方案时似乎更难。
我建议使用递归来尝试缩短正则表达式，但这并不是一个理想的解决方案。
"当不确定时，就使用暴力算法。"
import re
def learn(ayes, noes, max_size=7):
def is_ok(rx):
rx += '$'
return (all(re.match(rx, s) for s in ayes)
and not any(re.match(rx, s) for s in noes))
return find(find(gen_sized(size), is_ok)
for size in range(max_size + 1))
def find(xs, ok=lambda x: x):
for x in xs:
if ok(x):
return x
def gen_sized(size):
if 0 == size:
yield ''
if 0 < size:
for rx in gen_sized(size-1):
yield rx + '0'
yield rx + '1'
if rx and rx[-1] not in '*?+':
yield rx + '*'
yield rx + '?'
yield rx + '+'
if 5 < size:
for rx in gen_sized(size-3):
yield '(%s)*' % rx
yield '(%s)?' % rx
yield '(%s)+' % rx
这将为第一个问题生成一个不同但同样好的答案：0 * 1? 0 *。它检查了1241个试验正则表达式以解决两个测试用例（总计）。
搜索有一个大小限制--由于这个问题的通用正则表达式版本是NP-hard的，任何针对它的程序都会在足够复杂的输入上遇到麻烦。我承认我没有真正考虑过这个简化问题。我很想看到一些巧妙而不明显的答案。
[0, 00, 0000, 00000]和[000, 0000000]。 - Anon.