Алгоритм создания регулярных выражений из примеров

Question

AFAIK никто не реализовал алгоритм, который принимает набор строк и подстрок и возвращает одно или несколько регулярных выражений, которые бы соответствовали заданным подстрокам внутри строк. Так, например, если бы я дал своему алгоритму два примера:

string1 = "fwef 1234 asdfd"
substring1 = "1234"

string2 = "asdf456fsdf"
substring2 = "456"

Алгоритм вернул бы мне регулярное выражение "[0-9] *". Я знаю, что это может дать более одного регулярного выражения или даже никакого возможного регулярного выражения, и вы можете найти 1000 причин, по которым такой алгоритм будет почти невозможно реализовать до совершенства. Но что самое близкое?

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

Answer 1

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

С этим я предлагаю вам взглянуть на txt2re , который может разбивать образцы текста один за другим и помогать создавать регулярные выражения.

Answer 2

Flash Заполните новую функцию MS Excel 2013, которая будет выполнять именно ту задачу, которую вы хотите, но она не дает регулярного выражения. Это NP-полная проблема и открытый вопрос для практических целей. Если вам интересно, как синтезировать манипуляции со строками из нескольких примеров, зайдите на официальный веб-сайт Flash * Fill и прочитайте несколько статей. У них есть псевдокод и демо. фильмы тоже.

Answer 3

На самом деле таких алгоритмов много. Эта область исследований называется «Грамматический вывод».

Я знаю RPNI, например. (Вы также можете посмотреть на вероятностную ветвь, алергию, MDI, DEES). Эти алгоритмы генерируют DSA (детерминированные автоматы состояний). На самом деле вам абсолютно не нужно вводить строки в вашем примере. Только подстроки.

Есть также несколько алгоритмов для генерации непосредственно недетерминированных автоматов.

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

Основные идеи просты:

Создайте PTSA (автоматы состояния префикса дерева) из вашего образца.

Затем вы должны попытаться "объединить" некоторые состояния. В результате слияния будут возникать циклы (т. Е. * В регулярном выражении). Вся сложность заключается в том, чтобы выбрать правильное правило для слияния.

Answer 4

Вот, пожалуйста:

re = '|'.join(substrings)

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

• Соответствует всем простым числам
• Соответствует шестнадцатеричным строкам, но в образце набора
• нет строк, содержащих 'f'Совпадение с одной и той же строкой, повторенной дважды
• Совпадение с любой четной строкой

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