Возможно ли, чтобы компьютер “выучил” регулярное выражение по предоставленным пользователем примерам?

Question

Возможно ли, чтобы компьютер "выучил" регулярное выражение по предоставленным пользователем примерам?

Чтобы прояснить:

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

Возможно ли это?Существуют ли алгоритмы, ключевые слова и т.д.что я могу найти в Google?

Редактировать:Спасибо вам за ответы, но меня не интересуют инструменты, которые обеспечить эта особенность.Я ищу теоретическую информацию, такую как статьи, учебные пособия, исходный код, названия алгоритмов, чтобы я мог создать что-то для себя.

Answer 1

Книга Введение в теорию вычислительного обучения содержит алгоритм для обучения конечного автомата.Поскольку каждый регулярный язык эквивалентен конечному автомату, с помощью программы можно выучить некоторые регулярные выражения. Кернс и Вэлиант покажите несколько случаев, когда невозможно выучить конечный автомат.Связанной с этим проблемой является изучение скрытых Марковских моделей, которые являются вероятностными автоматами, которые могут описывать последовательность символов.Обратите внимание, что большинство современных "регулярных выражений", используемых в языках программирования, на самом деле сильнее обычных языков, и поэтому иногда их сложнее выучить.

Answer 2

Да, это возможно, мы можем генерировать регулярные выражения из примеров (текст -> желаемые извлечения).Это работающий онлайн-инструмент, который выполняет свою работу: http://regex.inginf.units.it/

Онлайн-инструмент Regex Generator ++ генерирует регулярное выражение из предоставленных примеров, используя алгоритм поиска GP.Алгоритм GP основан на многозадачности, что приводит к повышению производительности и упрощению структуры решения (Бритва Оккама).Этот инструмент представляет собой демонстрационное приложение Лаборатории машинного обучения Университета Триеста (Università degli studi di Trieste).Пожалуйста, посмотрите видеоурок здесь.

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

Узрите! :-)

Возможно найти значимое регулярное выражение / решение из примеров тогда и только тогда, когда приведенные примеры хорошо описывают проблему.Рассмотрим эти примеры, которые описывают задачу извлечения, мы ищем конкретные коды элементов;примерами являются пары текст / извлечение:

"The product code il 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"

Вы должны привести другие примеры, чтобы лучше описать, что является совпадением, а что нежелательным совпадением:--то есть:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

Номер телефона не является идентификатором продукта, это может быть важным доказательством.

Answer 3

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

Предположим, вы предоставляете примеры 111111 и 999999, если компьютер сгенерирует:

1. Регулярное выражение, в точности соответствующее этим двум примерам: (111111|999999)
2. Регулярное выражение, соответствующее 6 идентичным цифрам (\d)\1{5}
3. Регулярное выражение, соответствующее 6 единицам и девяткам [19]{6}
4. Регулярное выражение, соответствующее любым 6 цифрам \d{6}
5. Любой из вышеперечисленных трех, с границами слов, например \b\d{6}\b
6. Любой из первых трех, которому не предшествует и за которым не следует цифра, например(?<!\d)\d{6}(?!\d)

Как вы можете видеть, существует много способов, с помощью которых примеры могут быть обобщены в регулярное выражение.Единственный способ для компьютера создать предсказуемое регулярное выражение - это потребовать от вас перечислить ВСЕ возможные совпадения.Затем он мог бы сгенерировать шаблон поиска, который точно соответствует этим совпадениям.

Если вы не хотите перечислять все возможные совпадения, вам нужно описание более высокого уровня.Это именно то, для чего предназначены регулярные выражения.Вместо того чтобы предоставлять длинный список из 6-значных чисел, вы просто указываете программе, чтобы она соответствовала "любым шести цифрам".В синтаксисе регулярного выражения это становится \d{6}.

Любой метод предоставления описания более высокого уровня, который является таким же гибким, как регулярные выражения, также будет таким же сложным, как регулярные выражения.Все инструменты, такие как RegexBuddy Регулярное выражение что можно сделать, так это упростить создание и тестирование высокоуровневого описания.Вместо непосредственного использования краткого синтаксиса регулярных выражений RegexBuddy позволяет вам использовать простые английские строительные блоки.Но он не может создать высокоуровневое описание для вас, поскольку он не может волшебным образом знать, когда ему следует обобщать ваши примеры, а когда нет.

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

Answer 4

Да, это, безусловно, "возможно".;Вот псевдокод:

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;
}

Проблема в том, что существует бесконечное количество регулярных выражений, которые будут соответствовать списку примеров.Этот код предоставляет самое простое / глупое регулярное выражение в наборе, в основном соответствующее чему-либо в списке положительных примеров (и ничему другому, включая любой из отрицательных примеров).

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

Answer 5

Я полагаю, что этот термин называется "индукция".Вы хотите создать обычную грамматику.

Я не думаю, что это возможно с конечным набором примеров (положительных или отрицательных).Но, если я правильно помню, это можно сделать, если есть Оракул, к которому можно обратиться.(В принципе, вам нужно было бы позволить программе задавать пользователю вопросы "да" / "нет" до тех пор, пока это не будет удовлетворено.)

Answer 6

Возможно, вы захотите немного поиграть с этим сайтом, он довольно крутой и, похоже, делает что-то похожее на то, о чем вы говорите: http://txt2re.com

Answer 7

Существует язык, посвященный подобным проблемам, основанный на prolog.Это называется прогол.

Как упоминали другие, основная идея - индуктивное обучение, часто называемое ILP (индуктивное логическое программирование) в кругах искусственного интеллекта.

Вторая ссылка - это вики-статья об ILP, которая содержит много полезного исходного материала, если вам интересно узнать больше об этой теме.

Answer 8

@Yuval прав.Вы смотрите на вычислительную теорию обучения, или "индуктивный вывод."

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

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

Answer 9

Я провел кое-какие исследования в Google и Ситесер и нашел эти методы / статьи:

• Идентификация языка в пределе
• Вероятно, приблизительно правильное обучение

Также книга Даны Англуин "Изучение регулярных наборов на основе запросов и контрпримеров" кажется многообещающей, но я не смог найти PS или PDF-версию, только цитаты и материалы семинаров.

Похоже, что это сложная проблема даже на теоретическом уровне.

Answer 10

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