Как автоматически генерировать регулярное выражение из заданного списка строк?

Question

Вам предоставляется 2 списка строк - A и B. Найдите кратчайшее регулярное выражение, которое соответствует всем строкам в A и ни одному из B. Обратите внимание, что это регулярное выражение может соответствовать/не соответствовать другим строкам, которые не находятся в A, а не в B Для простоты можно предположить, что размер нашего алфавита составляет всего 2 символа - 0 и 1. Также допускаются только следующие операторы:

* - 0 или более
? - 0 или 1
+ - 1 или более
() - кронштейны

Для простоты регулярное выражение не оператор не допускается. Я не знаю, разрешило бы или оператор (|) упростить проблему или нет. А и B, конечно, не имели бы общих элементов. Вот некоторые примеры:

A=[00,01,10] 
B=[11] 
answer = 1*0+1* 

A=[00,01,11] 
B=[10] 
answer = 0*1* 

Answer 1

Если бы это была проблема домашних заданий, было бы как «один домашнее задание, получить А в классе» типа. Я думаю, что в этом вопросе отсутствует оператор «или».

Существует очевидное решение, которое является A0 | A1 | A2 | ..., но при попытке найти самое короткое решение кажется более сложным.

Я бы предложил использовать рекурсию, чтобы попытаться сократить регулярное выражение, но это не идеальное решение.

Answer 2

Один из способов решить это с помощью генетического алгоритма.Я случайно иметь genetic solver laying around так что я применил его к вашей проблеме со следующим алгоритмом:

• получить различные маркера от требуемых входов в качестве генов
• добавить Regex специальных генам
• для фитнеса алгоритм
  • убедитесь, что генерируется строка является допустимым регулярное выражение
  • получить фитнес-значение основано на том, сколько желательно все это соответствует и как много нежелательных вещей, я т соответствует
• пока успешный Regex не будет найден
  • начиная с числа различных маркеров и приращением по мере необходимости
  • попытке создать Regex той длины, которая проходит требование фитнес

Вот моя реализация в C#

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* 

Answer 3

«Если есть сомнения, используйте грубую силу».

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, любая программа для нее будет сталкиваться с проблемами на достаточно сложных входах. Я постараюсь не подумать об этой упрощенной проблеме. Мне бы хотелось увидеть некоторые аккуратные менее очевидные ответы.

Answer 4

Этот проект генерирует регулярное выражение из заданного списка слов: 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))