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

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

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

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

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

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

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

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

Да, это, конечно, "возможно"; вот псевдокод:

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

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

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

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

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

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

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

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

Вторая ссылка является статьей Wiki о ILP, который содержит много полезного исходного материала, если Вы интересуетесь получением дополнительной информации о теме.

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

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

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

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

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

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

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

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