Решаема ли проблема создания регулярного выражения, соответствующего некоторому входному набору?

Question

Я предоставляю некоторый набор входных данных, который содержит известное количество разделенных текстовых блоков.

Я хочу создать программу, которая автоматически генерирует 1 или более регулярных выражений, каждое из которых соответствует каждому текстовому блоку во входном наборе.

Я вижу несколько относительно простых способов реализовать поиск методом перебора. Но я не эксперт в теории компиляторов. Вот почему мне любопытно:

1) разрешима ли эта проблема? или есть какая-то принципиальная невозможность сделать такой алгоритм?

2) возможно ли достичь полиномиальной сложности для этого алгоритма и избежать грубого форсирования?

Answer 1

". *" - это одно или несколько регулярных выражений, которые будут соответствовать каждому текстовому блоку во входном наборе. ; -)

Answer 2

Проблема в том, что существует огромное количество регулярных выражений (на самом деле, бесконечное число), которые будут соответствовать заданному набору входных данных. Они варьируются от очень «жадных» выражений, которые будут соответствовать всему

.*

К очень не "жадному" выражению, которое будет точно соответствовать входному набору

InputA OR inputB OR inputC etc

В промежутке между этими двумя выражениями вы можете изменять выражение различными способами, чтобы сделать его все более и менее жадным (например, заменять определенные цифры выражением, соответствующим любой цифре и т. Д.).

Вам нужно будет рассказать нам немного больше о проблеме, чтобы мы знали, где из этого диапазона возможных ответов правильный;)

Answer 3

Хорошо, в комментарии вы пояснили, что хотите сопоставить все строки, которые либо равны одной из строк во входном наборе, либо отличаются только от одной из них в рамках заданного уровня «вариации». Поскольку вы не определили «вариацию» точно, я собираюсь использовать расстояние Левенштейна .

Учитывая строку s и целое число n, вы можете построить регулярное выражение, которое точно соответствует всем строкам, у которых расстояние Левенштейна составляет n или меньше, до этой строки, например:

Сначала мы напишем функцию, которая с учетом s и n возвращает список простых регулярных выражений, которые при совместном сопоставлении всех строк на расстоянии n или меньше равны s. Здесь «простое регулярное выражение» означает регулярное выражение, которое содержит только буквенные символы и подстановочные знаки.

Для n=0 эта функция просто возвращает [s]. В противном случае он вычисляет список для n-1 и затем просматривает каждый элемент в нем. Для каждого элемента r и каждой позиции i, где 0 <= i < length(r), в список добавляется следующее регулярное выражение:

• Регулярное выражение, где . было добавлено к r в позиции i.
• Регулярное выражение, в котором i-й символ r был удален.
• Регулярное выражение, в котором i-й символ r был заменен на ..

Теперь, чтобы вычислить регулярное выражение для заданного набора строк и заданное значение для n, мы вычисляем список для каждой строки, а затем or все регулярные выражения вместе в одно большое регулярное выражение.

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

Answer 4

http://txt2re.com/ может быть тем, что вы хотите.