计算机是否可以通过用户提供的示例"学习"正则表达式？

Question

计算机是否可以通过用户提供的示例"学习"正则表达式？

澄清:

• 我不是想学正则表达式.
• 我想创建一个程序,通过从用户交互提供的示例"学习"正则表达式,可能是从文本中选择部分或选择开始或结束标记.

可能吗？我可以使用Google的算法,关键字等吗？

编辑:谢谢你的答案,但我对提供此功能的工具不感兴趣.我正在寻找理论信息,如论文,教程,源代码,算法名称,所以我可以为自己创造一些东西.

Answer 1

" 计算学习理论导论 "一书包含了一种学习有限自动机的算法.由于每种常规语言都等同于有限自动机,因此可以通过程序学习一些正则表达式.Kearns和Valiant展示了一些无法学习有限自动机的情况.一个相关的问题是学习隐马尔可夫模型,它是可以描述字符序列的概率自动机.请注意,编程语言中使用的大多数现代"正则表达式"实际上比常规语言更强大,因此有时难以学习.

Answer 2

是的,有可能,我们可以从示例生成正则表达式(文本 - >所需的提取).这是一个有效的在线工具:http://regex.inginf.units.it/

Regex Generator ++在线工具使用GP搜索算法从提供的示例生成正则表达式.GP算法由多目标适应性驱动,这导致更高的性能和更简单的解决方案结构(Occam的Razor).该工具是Trieste Univeristy(Universitàdeglistudi 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"

您必须提供其他示例,以便更好地描述匹配内容以及不匹配的内容: - ie:

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

电话号码不是产品ID,这可能是一个重要的证明.

Answer 3

任何计算机程序都无法仅根据有效匹配列表生成有意义的正则表达式.让我告诉你原因.

假设您提供示例111111和999999,如果计算机生成:

1. 一个正则表达式恰好匹配这两个例子: (111111|999999)
2. 匹配6个相同数字的正则表达式 (\d)\1{5}
3. 正则表达式匹配6个和9个 [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