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

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

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

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

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

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

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

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

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

Regex Generator++ online tool генерирует регулярное выражение из приведенных примеров с использованием алгоритма поиска 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"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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