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

Ответ 1

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

Ответ 2

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

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

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

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

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

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

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

Ответ 3

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

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

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

Вот!: -)

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

"The product code il 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Человек (человек), смотрящий на примеры, может сказать --i.e: "коды предметов - это такие вещи, как \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"

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

Ответ 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;
}

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

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

Там есть язык, посвященный таким проблемам, основанный на прологе. Он назывался progol.

Как уже упоминалось, основная идея - это индуктивное обучение, часто называемое ILP (

Ответ 8

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

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

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

Ответ 9

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

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

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

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

Ответ 10

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