Jak automatycznie wygenerować wyrażenie regularne z podanej listy ciągów?

Question

Otrzymujesz dwie listy ciągów - A i B. Znajdź najkrótsze wyrażenie, które pasuje do wszystkich ciągów w A i żadne w B. Pamiętaj, że to wyrażenie może pasować/nie pasować do innych ciągów, które nie są w A, a nie w B Dla uproszczenia możemy założyć, że rozmiar naszego alfabetu wynosi tylko 2 znaki - 0 i 1. Również tylko te operatory są dozwolone: ​​

* - 0 lub więcej
? - 0 lub 1
+ - jeden lub więcej
() - wsporniki

dla uproszczenia nie regex operator nie jest dozwolony. Nie wiem, czy pozwolenie operatorowi (|) uprościłoby problem, czy też nie. A i B nie miałyby wspólnych elementów. Oto kilka przykładów:

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

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

Answer 1

Jeśli to był problem pracy domowej, byłoby jak "jedna praca domowa, uzyskać A w klasie" typu. Myślę, że gdzieś w tym pytaniu brakuje "lub" operatora.

Istnieje oczywiste rozwiązanie, które jest A0 | A1 | A2 | ..., ale wydaje się znacznie trudniejsze rozwiązanie, starając się znaleźć najkrótszy.

Proponuję użyć rekursji, aby spróbować skrócić wyrażenie regularne, ale to nie jest idealne rozwiązanie.

Answer 2

Jednym ze sposobów rozwiązania tego problemu jest algorytm genetyczny.Zdarza mi się mieć genetic solver laying around więc zastosować je do swojego problemu z następującym algorytmem:

• uzyskać wyraźne znaki od pożądanego wejść jak geny
• dodać regex dania z genami
• o przydatności algorytm
  • upewnić wygenerowany ciąg jest prawidłowy regex
  • uzyskać wartość biznesowe w oparciu o liczbę pożądane rzeczy pasuje i jak wiele niepożądanych rzeczy T odpowiada
• aż sukces Regex znajduje
  • zaczynając od liczby różnych znaczników i zwiększając to konieczne
  • próby wygenerowania Regex tej długości, która przechodzi przez wymaganie biznesowe

Oto moja implementacja w 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; 
    } 
} 

a wynik jego zastosowania do próbek:

public void Given_Sample_A() 
{ 
    var target = new[] { "00", "01", "10" }; 
    var dontMatch = new[] { "11" }; 

    GenerateRegex(target, dontMatch); 
} 

wyjściowa:

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? 

druga próbka:

public void Given_Sample_B() 
{ 
    var target = new[] { "00", "01", "11" }; 
    var dontMatch = new[] { "10" }; 

    GenerateRegex(target, dontMatch); 
} 

wyjściowa:

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

"W razie wątpliwości użyj brutalnej siły."

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 

To daje inną, ale równie dobrą odpowiedź na pierwszy: 0*1?0*. Sprawdza 1241 próbnych wyrażeń regularnych, aby rozwiązać dwa przypadki testowe (łącznie).

Wyszukiwanie ma ograniczenie rozmiaru - ponieważ wersja ogólnego regex tego problemu jest NP-trudna, każdy program będzie miał kłopoty z wystarczająco złożonymi danymi wejściowymi. Będę gliniarzem, żeby nie pomyśleć o tym uproszczonym problemie. Chciałbym zobaczyć kilka mniej oczywistych odpowiedzi.

Answer 4

Ten projekt generuje regexp z danej listy słów: https://github.com/bwagner/wordhierarchy

Jednak tylko używa „|”, zakaz robienia grupę „(?:)” i wybrać opcję „?”.

wykorzystanie próbki:

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))