102

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

澄清：

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

是否可以？是否有算法、关键字等可供我使用 Google 搜索？

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

4

10 回答 10

51

是的，有可能，我们可以从示例中生成正则表达式（文本 -> 所需的提取）。这是一个可以完成这项工作的在线工具：http ://regex.inginf.units.it/

Regex Generator++ 在线工具使用 GP 搜索算法从提供的示例生成正则表达式。GP 算法由多目标适应度驱动，从而导致更高的性能和更简单的解决方案结构（奥卡姆剃刀）。该工具是的里雅斯特大学 (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"

您必须提供其他示例，以便更好地描述什么是匹配，什么不是所需的匹配：--ie：

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

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

于 2014-12-22T19:59:49.577 回答
47

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

于 2009-03-05T20:18:21.050 回答
36

没有计算机程序能够仅根据有效匹配列表生成有意义的正则表达式。让我告诉你为什么。

假设您提供示例 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 不是直接使用简洁的正则表达式语法，而是让您能够使用简单的英语构建块。但它无法为您创建高级描述，因为它无法神奇地知道何时应该概括您的示例，何时不应该概括。

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

于 2009-03-07T01:42:42.713 回答
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;
}

问题是有无数的正则表达式可以匹配示例列表。此代码提供了集合中最简单/最愚蠢的正则表达式，基本上匹配正面示例列表中的任何内容（没有其他内容，包括任何负面示例）。

我想真正的挑战是找到与所有示例匹配的最短正则表达式，但即便如此，用户也必须提供非常好的输入以确保生成的表达式是“正确的”。

于 2009-03-05T19:46:51.500 回答
7

我相信这个词是“感应”。你想诱导一个规则的语法。

我认为有限的示例集（正面或负面）是不可能的。但是，如果我没记错的话，如果有可以咨询的 Oracle 就可以做到。（基本上你必须让程序问用户是/否问题，直到它满足为止。）

于 2009-03-05T19:40:42.967 回答
5

你可能想玩一下这个网站，它很酷，听起来和你所说的类似：http: //txt2re.com

于 2009-03-05T19:36:41.930 回答
4

有一种基于 prolog 的语言专门用于解决此类问题。它被称为progol。

正如其他人所提到的，基本思想是归纳学习，在 AI 圈子中通常称为 ILP（归纳逻辑编程）。

第二个链接是关于 ILP 的 wiki 文章，如果您有兴趣了解有关该主题的更多信息，其中包含许多有用的源材料。

于 2009-03-07T01:53:24.433 回答
3

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

这个问题比你想象的要复杂，因为“学习”的定义并不简单。一个常见的定义是学习者可以随时吐出答案，但最终，它必须要么停止吐出答案，要么总是吐出相同的答案。这假设输入的数量是无限的，并且绝对不会给出程序何时会做出决定的保证。此外，您无法判断它何时做出决定，因为它可能稍后仍会输出不同的内容。

根据这个定义，我很确定常规语言是可以学习的。根据其他定义，没有那么多...

于 2009-03-06T21:19:04.220 回答
2

我对 Google 和CiteSeer做了一些研究，发现了这些技术/论文：

此外，Dana Angluin 的“Learning regular sets from queries and counterexamples”似乎很有希望，但我找不到 PS 或 PDF 版本，只有引用和研讨会论文。

即使在理论上，这似乎也是一个棘手的问题。

于 2009-03-07T13:04:30.700 回答
0

如果一个人可以学习一个正则表达式，那么它从根本上来说是一个程序是可能的。但是，该程序需要正确编程才能学习。幸运的是，这是一个相当有限的逻辑空间，所以它不会像教程序能够看到对象或类似的东西那么复杂。

于 2009-03-05T19:43:59.103 回答