Может ли компьютер «выучить» регулярное выражение на предоставленных пользователем примерах?

Question

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

Для уточнения:

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

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

РЕДАКТИРОВАТЬ : Спасибо за ответы, но мне не интересны инструменты, которые предоставляют эту функцию. Я ищу теоретическую информацию, такую ​​как статьи, учебные пособия, исходный код, названия алгоритмов, чтобы я мог создать что-то для себя.

Answer 1

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

Answer 2

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

Regex Generator ++ онлайн инструмент генерирует регулярное выражение из предоставленных примеров, используя алгоритм поиска GP. Алгоритм GP основан на мультиобъективной пригодности, которая приводит к более высокой производительности и более простой структуре решения (Razor Оккама). Этот инструмент является демонстрационным приложением Лаборатории машинного обучения, Университет Триеста (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"

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

"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

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

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

Answer 6

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

Answer 7

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

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

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

Answer 8

Я провел некоторые исследования в Google и CiteSeer и нашел следующие методы / документы:

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

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

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

Answer 9

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

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

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

Answer 10

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