logo标签列表

计算机能否通过用户提供的示例“学习”正则表达式？

regexartificial-intelligencetheoryautomatagrammar-induction
110

计算机是否能够通过用户提供的样例来“学习”正则表达式？

澄清一下：

  • 我不想学习正则表达式。
  • 我想创建一个程序，该程序可以从用户交互提供的示例中“学习”正则表达式，例如通过从文本中选择部分或选择起始或结束标记。

是否有可能？ 有没有算法、关键词等可供Google搜索？

编辑: 感谢各位的回答，但我对提供此功能的工具不感兴趣。 我正在寻找理论信息，如论文、教程、源代码、算法名称，以便我可以为自己创建一些东西。

6
我很惊讶没有人提到Regex::PreSuf。 - tripleee
有人知道是否有Python等效于Regex :: PreSuf吗？ - Brad
10个回答
55

是的，我们可以根据示例（文本->期望的提取结果）生成正则表达式。这是一个在线工具，可以完成此工作：http://regex.inginf.units.it/

Regex Generator++在线工具使用GP搜索算法从提供的示例生成正则表达式。该GP算法受多目标适应度驱动，可导致更高的性能和更简单的解决方案结构（奥卡姆剃刀）。这个工具是Trieste大学（Università degli studi di Trieste）机器学习实验室的演示应用程序。请在这里查看视频教程。

这是一个研究项目，因此您可以在这里阅读所使用的算法。

请注意！ :-)

如果所提供的示例很好地描述了问题，那么从示例中找到有意义的正则表达式/解决方案是可能的当且仅当。请考虑下面描述提取任务的示例，我们正在寻找特定的项目代码; 示例是文本/提取对：

"The product code is 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"

电话号码不是产品ID，这可能是一个重要的证据。

7
这应该是最佳答案。这是可行的，并且这证明了它的可行性。源码在这里：https://github.com/MaLeLabTs/RegexGenerator - rjurney
你提供的产品代码示例说明了为什么人们应该查阅产品代码规范并根据规范编写正则表达式，而不是试图从有限的样本产品代码中推断出正则表达式（无论是人还是程序都是如此）。 - Jan Goyvaerts
3
这是正确的做事方式。我的例子只是一种概念上解释问题的方法。有时候没有具体要求，或者那个人就是无法独立编写正则表达式（缺乏知识）。 - Fabiano Tarlao
更加准确和明确一点，"This is the right way to do things" 可以翻译为 "你是对的，你的方法是最好的，尽可能从规格开始"。 - Fabiano Tarlao
3
“从示例中推断正则表达式进行文本提取”的文章包含了该算法的详细解释。http://machinelearning.inginf.units.it/publications/international-journal-publications/inferenceofregularexpressionsfortextextractionfromexamples - mimmuz
49

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

37
没有任何计算机程序能够仅基于有效匹配列表生成有意义的正则表达式。下面我会向您展示原因。
假设您提供了111111和999999这两个例子，那么计算机应该生成：
1. 精确匹配这两个例子的正则表达式：(111111|999999) 2. 匹配6个相同数字的正则表达式：(\d)\1{5} 3. 匹配6个1或9的正则表达式：[19]{6} 4. 匹配任意6个数字的正则表达式：\d{6} 5. 上述三种中的任何一种，带有单词边界，例如：\b\d{6}\b 6. 上述前三种中的任何一种，不被数字前后跟随，例如：(?<!\d)\d{6}(?!\d) 正如您所看到的，有许多方法可以将示例概括为正则表达式。 计算机建立可预测的正则表达式的唯一方法是要求您列出所有可能的匹配项。 然后它可以生成一个搜索模式，精确地匹配这些匹配项。
如果您不想列出所有可能的匹配项，则需要更高级别的描述。 这正是正则表达式的设计目的。 您只需告诉程序匹配“任何六个数字”，而不是提供一长串6位数字列表。 在正则表达式语法中，这变成了\d{6}。
任何提供与正则表达式一样灵活的高级描述的方法都将像正则表达式一样复杂。像RegexBuddy这样的工具只能使创建和测试高级描述更容易。 RegexBuddy使您可以使用普通英语构建模块，而不是直接使用简洁的正则表达式语法。但它无法为您创建高级描述，因为它不能神奇地知道何时应该概括您的示例，何时不应该概括。

当然可以创建一个工具，它使用用户提供的指南和示例文本来生成正则表达式。设计这样一个工具的难点在于如何询问用户需要的指导信息，而不使工具比学习正则表达式本身更难，并且不限制工具仅适用于常见的正则表达式任务或简单的正则表达式。

你说得对，我在发布问题后发现许多学习算法都需要正面和负面信息。据我所知，并不需要明确的“高级描述”，因为用户通过回答问题来提供它。 - Daniel Rikowski
如果一个工具提出问题，那么问题和给出的答案的组合形成了更高层次的描述。这类工具的质量在很大程度上取决于它所提出的问题。 - Jan Goyvaerts
这很愚蠢，因为如果你提供另一个例子，那么你可以排除一些可能性。再举一个例子会排除更多的可能性。 - Cris
2
@Cris：原则不变，不管提供多少样本。只是改变了可能性。例如，添加123456将#2更改为(\d)\1{5}|123456，将#3更改为[19]{6}|123456。或者可以将#3更改为[1-69]{6}。甚至可能是所需模式匹配6个相同数字或6个数字，其中每个数字比前一个数字大一。即使您提供10,000个6位数字的样本，程序也无法在没有用户额外指示的情况下区分#1、#4、#5或#6。 - Jan Goyvaerts
我认为这个问题可以很容易地解决，方法如下：程序尽可能通用（在合理范围内），然后给出它认为匹配的其他事物的示例。通过简单地告诉它所提出的匹配是否正确，您可以帮助它了解您实际想要捕获的范围。我希望在文本编辑器中看到一个使用这个概念并从当前打开的文件中提出匹配的工具。 - Jon McClung
确实，从单词的子集中你永远无法得到一个100％正确的正则表达式。但是对于许多应用程序，我们可以应对近似匹配。我们只需要一个额外的参数来控制我们希望正则表达式有多宽或紧。介于仅匹配给定单词和匹配“.*”之间。我猜如果我们假设字符类别的某些分布，它可以被构建成一个似然概率。 - Celelibi
8

是的，这当然是“可能的”；以下是伪代码：

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

问题在于，会有无限多的正则表达式可以匹配一个示例列表。这段代码提供了最简单/最愚蠢的一种正则表达式，基本上是匹配任何在正例列表中的内容（包括任何负例，但不匹配其他内容）。
我想，真正的挑战将是找到与所有示例匹配的最短的正则表达式，但即使如此，用户也必须提供非常好的输入才能确保生成的表达式是“正确的”。
3
当用户输入正样本和负样本时，事情开始变得有趣起来。正则表达式需要匹配正样本，而不能匹配负样本。请注意，不能改变原意。 - user55400
@blixtor - 其实，这很容易。只需不将任何负面示例放入构建的正则表达式中，它们就会被拒绝。请记住，代码构建的那个只匹配正面示例；负面示例（以及其他任何东西）都是根据定义排除在外的！ - Daniel LeCheminant
丹尼尔是正确的。如果没有更高层次的描述，从示例列表中可以一致准确地推断出的只有备选项列表。 - Jan Goyvaerts
7
我相信这个术语是“归纳”。“您想归纳一个规则语法”。
我认为用有限的正面或反面示例不可能做到。但是，如果我记得正确，如果有一个可以查询的Oracle，则可以完成此操作。（基本上，您必须允许程序询问用户是/否问题，直到它满意）。
是的，这就是我想做的，与用户进行交互式询问。 - Daniel Rikowski
Yuval F的参考资料似乎是我所想要的，我建议您查看一下。 - Jay Kominek
为了生成一个匹配有限字符串集的正则表达式，我会使用DFA学习算法。 - Anderson Green
5

你可能想要尝试一下这个网站，它非常酷，听起来与你所讨论的内容相似：http://txt2re.com

4

有一种专门解决这类问题的语言，基于Prolog。它被称为progol。

正如其他人所提到的，基本思想是归纳学习，在人工智能领域通常称为ILP（归纳逻辑编程）。

第二个链接是关于ILP的维基百科文章，如果您对该主题有兴趣，其中包含许多有用的来源材料。

我找到了一篇论文，描述了使用归纳逻辑编程进行语法归纳的方法，但我从未在Progol中看到过这种方法的实现。 - Anderson Green
3

@Yuval是正确的。您正在查看计算学习理论或“归纳推理”。

这个问题比您想象的要复杂，因为“学习”的定义并不是微不足道的。一个常见的定义是，学习者可以随时吐出答案，但最终必须停止吐出答案或始终吐出相同的答案。这假定有无限数量的输入，并且对程序何时达到决策没有任何保证。此外，您无法确定它何时已经做出决定，因为它可能稍后仍会输出不同的内容。

按照这个定义，我相信常规语言是可以被学习的。但根据其他定义，情况就不一定了...

2
我在Google和CiteSeer上进行了一些研究，并找到了以下技术/论文： 此外，Dana Angluin的“从查询和反例中学习正则集”似乎很有前途，但我没有找到PS或PDF版本，只有引用和研讨会论文。
即使在理论层面上，这似乎也是一个棘手的问题。
0
如果一个人能够学习正则表达式，那么程序基本上也可以学习。然而，该程序需要被正确编程才能学习。幸运的是，这是一个相当有限的逻辑空间，因此它不会像教授程序看对象之类的东西那样复杂。
1
不是这样的，你应该查找那些在图灵机上无法判定的问题。 - Stephen Curial
公平地说，我曾经说过一个人能学会正则表达式，机器也能。但我并不是通常意义上的这个意思。 - cjk
@scurial，我不认为有人类可以解决但图灵机无法判定的问题，对吧？ - Sunny88
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接