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

Вам предоставляется 2 списка строк - A и B. Найдите кратчайшее регулярное выражение, которое соответствует всем строкам в и ни одному из B. Обратите внимание, что это регулярное выражение может соответствовать/не соответствовать другим строкам, которые не находятся в A, а не в Б. Для простоты можно предположить, что наш размер алфавита всего 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*

Ответ 1

Один из способов решения этой проблемы - генетический алгоритм. У меня, оказывается, есть генетический решатель, поэтому я применил его к вашей проблеме со следующим алгоритмом:

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

Здесь моя реализация в С#

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*

Ответ 2

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

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

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

Ответ 3

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

Ответ 4

"Если вы сомневаетесь, используйте грубую силу".

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