Может ли компьютер «выучить» регулярное выражение на примерах, предоставленных пользователем?
Чтобы уточнить:
- Я не хочу изучать регулярные выражения.
- Я хочу создать программу, которая «изучает» регулярное выражение на примерах, которые интерактивно предоставляются пользователем, возможно, путем выбора частей из текста или выбора маркеров начала или конца.
Является ли это возможным? Есть ли алгоритмы, ключевые слова и т. Д., По которым я могу использовать Google?
РЕДАКТИРОВАТЬ : Спасибо за ответы, но меня не интересуют инструменты, которые предоставляют эту функцию. Я ищу теоретическую информацию, такую как статьи, руководства, исходный код, названия алгоритмов, чтобы я мог создать что-то для себя.
regex
artificial-intelligence
theory
automata
Даниэль Риковски
источник
источник
Ответы:
Книга Введение в теорию вычислительного обучения содержит алгоритм обучения конечного автомата. Поскольку любой регулярный язык эквивалентен конечному автомату, некоторые регулярные выражения можно выучить с помощью программы. Кернс и Валиант показывают некоторые случаи, когда невозможно изучить конечный автомат. Смежная проблема - изучение скрытых марковских моделей , которые представляют собой вероятностные автоматы, которые могут описывать последовательность символов. Обратите внимание, что большинство современных «регулярных выражений», используемых в языках программирования, на самом деле сильнее обычных языков, и поэтому иногда их труднее выучить.
источник
Да, это возможно, мы можем генерировать регулярные выражения из примеров (текст -> желаемые извлечения). Это рабочий онлайн-инструмент, который выполняет свою работу: http://regex.inginf.units.it/
Онлайн-инструмент Regex Generator ++ генерирует регулярное выражение из предоставленных примеров, используя алгоритм поиска GP. Алгоритм GP управляется многокритериальной пригодностью, что приводит к более высокой производительности и более простой структуре решения (бритва Оккама). Этот инструмент является демонстрационным приложением Лаборатории Машин Лернинга, Университет Триеста (Università degli studi di Trieste). Пожалуйста, посмотрите видеоурок здесь .
Это исследовательский проект, поэтому вы можете прочитать об используемых алгоритмах здесь .
Вот! :-)
Найти осмысленное регулярное выражение / решение из примеров возможно тогда и только тогда, когда предоставленные примеры хорошо описывают проблему. Рассмотрим эти примеры, которые описывают задачу извлечения, мы ищем конкретные коды товаров; примеры - пары текст / извлечение:
"The product code is 467-345A" -> "467-345A" "The item 789-345B is broken" -> "789-345B"Парень (человек), глядя на примеры, может сказать: «Коды товаров - это такие вещи, как \ d ++ - 345 [AB]»
Когда код товара более допустим, но мы не предоставили других примеров, у нас нет доказательств, чтобы хорошо понять проблему. При применении созданного человеком решения \ d ++ - 345 [AB] к следующему тексту это не удается:
"On the back of the item there is a code: 966-347Z"Вы должны предоставить другие примеры, чтобы лучше описать совпадение, а что нет: --ie:
"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"Номер телефона не является идентификатором продукта, это может быть важным доказательством.
источник
Никакая компьютерная программа никогда не сможет сгенерировать осмысленное регулярное выражение, основанное исключительно на списке допустимых совпадений. Позвольте мне показать вам, почему.
Предположим, вы предоставили примеры 111111 и 999999, если компьютер сгенерирует:
(111111|999999)(\d)\1{5}[19]{6}\d{6}\b\d{6}\b(?<!\d)\d{6}(?!\d)Как видите, существует множество способов обобщения примеров в регулярное выражение. Единственный способ для компьютера построить предсказуемое регулярное выражение - это потребовать от вас перечислить все возможные совпадения. Затем он может сгенерировать шаблон поиска, который точно соответствует этим совпадениям.
Если вы не хотите перечислять все возможные совпадения, вам нужно описание более высокого уровня. Именно для этого предназначены регулярные выражения. Вместо того, чтобы предоставлять длинный список из 6-значных чисел, вы просто говорите программе сопоставить «любые шесть цифр». В синтаксисе регулярных выражений это становится \ d {6}.
Любой метод предоставления высокоуровневого описания, столь же гибкого, как регулярные выражения, также будет таким же сложным, как и регулярные выражения. Все инструменты, подобные RegexBuddy, могут облегчить создание и тестирование высокоуровневого описания. Вместо прямого использования краткого синтаксиса регулярных выражений, RegexBuddy позволяет использовать простые английские строительные блоки. Но он не может создать для вас высокоуровневое описание, поскольку не может волшебным образом знать, когда ему следует обобщать ваши примеры, а когда нет.
Конечно, можно создать инструмент, который использует образец текста вместе с рекомендациями, предоставляемыми пользователем, для создания регулярного выражения. Сложная часть в разработке такого инструмента заключается в том, как он запрашивает у пользователя направляющую информацию, которая ему нужна, не усложняя при этом инструмент для изучения, чем сами регулярные выражения, и не ограничивая инструмент общими заданиями регулярных выражений или простыми регулярными выражениями.
источник
Да, конечно «возможно»; Вот псевдокод:
string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>) { if HasIntersection(<listOfPosExamples>, <listOfNegExamples>) return <IntersectionError> string regex = ""; foreach(string example in <listOfPosExamples>) { if(regex != "") { regex += "|"; } regex += DoRegexEscaping(example); } regex = "^(" + regex + ")$"; // Ignore <listOfNegExamples>; they're excluded by definition return regex; }Проблема в том, что существует бесконечное количество регулярных выражений, которые будут соответствовать списку примеров. Этот код предоставляет самое простое / самое глупое регулярное выражение в наборе, в основном соответствующее чему-либо в списке положительных примеров (и ничего больше, включая любые отрицательные примеры).
Я полагаю, что реальной проблемой было бы найти кратчайшее регулярное выражение, которое соответствует всем примерам, но даже в этом случае пользователь должен будет предоставить очень хорошие входные данные, чтобы убедиться, что полученное выражение было «правильным».
источник
Я считаю, что это термин «индукция». Вы хотите научить вас правильной грамматике.
Я не думаю, что это возможно с ограниченным набором примеров (положительных или отрицательных). Но, если я правильно помню, это можно сделать, если есть Oracle, с которым можно проконсультироваться. (По сути, вы должны позволить программе задавать пользователю вопросы типа «да / нет», пока она не будет удовлетворена.)
источник
Возможно, вы захотите немного поиграть с этим сайтом, это довольно круто и похоже, что он делает что-то похожее на то, о чем вы говорите: http://txt2re.com
источник
Для подобных проблем есть язык, основанный на прологе. Это называется прогол .
Как уже упоминали другие, основная идея - это индуктивное обучение, которое в кругах ИИ часто называется ILP ( индуктивное логическое программирование ).
Вторая ссылка - это вики-статья по ILP, которая содержит много полезных исходных материалов, если вы хотите узнать больше по этой теме.
источник
@Yuval прав. Вы смотрите на теорию вычислительного обучения или «индуктивный вывод».
Вопрос сложнее, чем вы думаете, поскольку определение «учиться» нетривиально. Одно из распространенных определений состоит в том, что учащийся может выкладывать ответы, когда захочет, но в конечном итоге он должен либо перестать выплевывать ответы, либо всегда выдавать один и тот же ответ. Это предполагает бесконечное количество входных данных и не дает абсолютно никаких гарантий относительно того, когда программа достигнет своего решения. Кроме того, вы не можете сказать, когда он ПРИНЯЛ свое решение, потому что он все еще может вывести что-то другое позже.
По этому определению я почти уверен, что обычные языки можно выучить. По другим определениям не очень ...
источник
Я провел небольшое исследование в Google и CiteSeer и нашел следующие методы / статьи:
Также многообещающим кажется «Изучение регулярных множеств на основе запросов и контрпримеров» Даны Англуин, но мне не удалось найти версию в PS или PDF, только цитирование и семинары.
Кажется, это непростая задача даже на теоретическом уровне.
источник
Если человек может выучить регулярное выражение, то в принципе это возможно и для программы. Однако эта программа должна быть правильно запрограммирована, чтобы иметь возможность учиться. К счастью, это довольно ограниченное пространство логики, поэтому это не будет так сложно, как научить программу видеть объекты или что-то в этом роде.
источник